回歸算法
一、理解線性回歸模型
首先講回歸模型，回歸模型研究的是因變量（目標）和自變量（預測器）之間的關系，因變量可以是連續也可以離散，如果是離散的就是分類問題。思考房價預測模型，我們可以根據房子的大小、戶型、位置、南北通透等自變量預測出房子的售價，這是最簡單的回歸模型，在初中里面回歸表達式一般這樣寫，其中x是自變量，y是因變量，w是特征矩陣，b是偏置。
在機器學習推導里面引入線性代數的思想，將假設我們用一個表達式來描述放假預測模型，x代表一個房子的特征集，它是一個n×1的列向量，總共有m個特征集，θ是一個n×1的列向量，是我們想要求得未知數。
我們采用誤差最小的策略，比如有預測表達式：y工資=Θ1*學歷+Θ2*工作經驗+Θ3*技術能力+.......+Θn*x+基本工資，預測的y值和實際值y_存有差距，策略函數就是使得m個特征集的（真實值y-預測值）的平方和最小。（差值可能是負數，所以采用平方和）；
按照對于正規方程的求法，我們對θ 求偏導：
也就是，給定特征矩陣X和因變量y，即可以求使誤差率最小的θ值，滿足后續的回歸模型。了解線性代數的童靴可以看出來問題，在θ的表達式中有求逆運算，需要保證矩陣可逆，這一般是無法保證的，這樣就會造成θ無解，策略失效；
二、計算機的做法：梯度下降
常規的方程需要大量的矩陣運算，尤其是矩陣的逆運算，在矩陣很大的情況下，會大大增加計算復雜性。，且正規方程法對矩陣求偏導有一定的局限性（無法保證矩陣可逆），下面介紹梯度下降法，也就是計算機的解決方法，每次走一小步，保證這一小步是最有效的一步，可以想象自己正在下山，你不知道目的地（全局最小值）在哪，但是你能夠保證自己每次走的都是最陡峭的一步；
我們的策略仍然保持不變，就是使得m個特征集的（真實值y-預測值）的平方和最小：
梯度下降法實現：賦予初始θ 值，并根據公式逐步更新θ 使得J(θ) 不斷減少，最終至收斂，對應的參數θ 即為解。為了推導方便，首先研究只有一個訓練樣本時，如何計算推導公式。
推廣到m個訓練數據，參數更新公式為：
三、邏輯回歸模型
邏輯回歸與線性回歸同屬廣義線性模型，邏輯回歸是以線性回歸為理論支持，是一個二分類模型，也可以推廣多到分類問題，通過Sigmoid函數引入了非線性因素，因此可以輕松處理0/1分類問題，首先介紹一下Sigmoid函數：
sigmoid函數圖像是一個S曲線，取值在[0, 1]之間，在遠離0的地方函數的值會很快接近0或者1，sigmoid函數的求導特性是：
邏輯回歸的預測函數是下圖，只是在特征到結果的映射中加入了一層函數映射，先把特征線性求和，然后使用函數g(z)將最為假設函數來預測。g(z)可以將連續值映射到0到1之間：
通過求似然函數，兩邊取log后，對θ求偏導：
這樣我們就得到了梯度上升每次迭代的更新方向，那么θ的迭代表達式為：
四、回歸模型使用
數據是2014年5月至2015年5月美國King County的房屋銷售價格以及房屋的基本信息。數據分為訓練數據和測試數據，分別保存在kc_train.csv和kc_test.csv兩個文件中，其中訓練數據主要包括10000條記錄，14個字段：銷售日期,銷售價格,臥室數,浴室數,房屋面積,停車面積,樓層數,房屋評分,建筑面積,地下室面積,建筑年份,修復年份,緯度,經度。
import pandas as pd
from pandas import DataFrame
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import seaborn as sns
from sklearn.linear_model import LogisticRegression
from sklearn.ensemble import RandomForestClassifier
from sklearn.linear_model import LinearRegression
# 數據讀取
baseUrl="C:\Users\71781\Desktop\2020\ML-20200422\houre_price\"
house_df=pd.read_csv(baseUrl+'train.csv' )
test_df=pd.read_csv(baseUrl+'test.csv')
house_df.head()
# 刪除無關變量
house_df=house_df.drop(['saleTime','year','repairYear','latitude','longitude','buildingSize'],axis=1)
test_df=test_df.drop(['saleTime','year','repairYear','latitude','longitude','buildingSize'],axis=1)
# 模型建立
X_price=house_df.drop(['price'],axis=1)
# X_price.head()
Y_price=house_df['price']
Y_price.head()
LR_reg=LinearRegression()
LR_reg.fit(X_price, Y_price)
Y_pred = LR_reg.predict(test_df)
LR_reg.score(X_price, Y_price)
# 可以選擇進行特征縮放
#new_house=house_df.drop(['price'],axis=1)
#from sklearn.preprocessing import MinMaxScaler
#minmax_scaler=MinMaxScaler().fit(new_house) #進行內部擬合，內部參數會發生變化
#scaler_housing=pd.DataFrame(minmax_scaler.transform(new_house),columns=new_house.columns)
#mm=MinMaxScaler()
#mm.fit(test_df)
#scaler_t=mm.transform(test_df)
#scaler_t=pd.DataFrame(scaler_t,columns=test_df.columns)
02
決策樹
一、決策樹算法理解
決策樹是直觀運用概率分析的樹形分類器，是很常用的分類方法，屬于監管學習，決策樹分類過程是從根節點開始，根據特征屬性值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
比如說買瓜的時候，根據瓜的某些特征屬性直觀判斷瓜的好壞，下圖依次根據紋理清晰度、根蒂、色澤、觸感4個進行分類，生活中我們會將某個最重要或最明顯的分類屬性放在第一位，然后是次重要屬性，這很符合我們平常的判斷思維，這就是決策樹！
在特征屬性非常大的時候，就出現了首選哪個特征屬性進行分類？如何剪枝？分類的層次是多少？....系列問題，這些就是決策樹構建的核心問題，而且不可能再通過生活直覺判，這時候就要運用數學思維。根據上面問題的不同解決方案，決策樹又分為了ID3(熵增益)、C4.5(熵增益率)、CART幾種同類算法。
二、熵增益（ID3）
通信層面，信息熵衡量信息的不確定性，信息熵越大表明信息越不準確，可以用信息熵的減少值來衡量信息的價值。在決策樹模型中把信息確定性叫做熵增益，有了熵增益后，我們就可以根據熵增益來判斷特征值的重要程度，從而選取最重要的特征作為第一次切分，再根據相同的方法用其他特征進行切分，直到得到得到每個劃分的葉子節點。信息熵的定義是：
以某個特征屬性值切分后子集熵的和稱為條件A下的熵，也叫做條件熵，可以如下表示：
分類前的信息熵減去條件熵，得到熵增益：
比如說有以下數據集（相親結果表lol..）
6條數據中相中（4個）與不想中（2個），暫且不關系如何進行分類，我們首先計算這個分類結果的信息熵：
其次，我們計算“富”屬性的條件信息熵，6條數據中“富”與否各半，其中3個“富”都被分類到“相中”，3個“不富”都被分到“不想中”：
計算各個特征屬性的熵增益后，比較哪個熵增益最大，就選擇該屬性做第一分類特征。
3、熵增益率（C4.5）
按照熵增益最大準則的ID3算法，遇到全部都是非重復值（類似ID）屬性容易造成過擬合，因為如果根據ID這個屬性進行劃分發現此時的熵增益是最大的：
信息增益率定義為：
5、鳶尾花(iris)分類模型
數據分布探索：
4、剪枝處理
當訓練數據量大、特征數量較多時構建的決策樹過于龐大時，可能對訓練集依賴過多，也就是對訓練數據過度擬合。從訓練數據集上看，擬合效果很好，但對于測試數據集或者新的實例來說，并不一定能夠準確預測出其結果。因此，對于決策樹的構建還需要最后一步--決策樹的修剪，主要分為2種：預剪枝（Pre-Pruning）和后剪枝（Post-Pruning），這里先不講。
5、鳶尾花(iris)分類模型
Iris 鳶尾花數據集是一個經典數據集，在統計學習和機器學習領域都經常被用作示例。數據集內包含 3 類共 150 條記錄，每類各 50 個數據，每條記錄都有 4 項特征：花萼長度、花萼寬度、花瓣長度、花瓣寬度，可以通過這4個特征預測鳶尾花卉屬于（iris-setosa, iris-versicolour, iris-virginica）中的哪一品種，數據集地址：
https://github.com/yezonggang/iris
import pandas as pd
from pandas import DataFrame
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import seaborn as sns
from sklearn.tree import DecisionTreeClassifier
from sklearn import metrics
baseUrl="C:\Users\71781\Desktop\2020\ML-20200422\iris\"
iris_df=pd.read_csv(baseUrl+"iris.csv")
iris_df.head()
iris_df.describe()
數據分布探索：
# pandas 自帶的散點圖
iris_df.plot(kind="scatter", x="Sepal.Length", y="Sepal.Width")
# seaborn 的聯合分布圖
sns.jointplot(x="Sepal.Length", y="Sepal.Width", data=iris_df, height=5)
# 上面的兩個散點圖并不能顯示每一個點所屬的類別
# 所以，接下來用 seaborn 的 FacetGrid 函數按照Species花的種類來在散點圖上標上不同的顏色，hue英文是色彩的意思。
sns.FacetGrid(iris_df, hue="Species", height=5).map(plt.scatter, "Sepal.Length", "Sepal.Width").add_legend()
# 通過箱線圖來查看單個特征的分布
# 對 Numerical Variable，可以用 Box Plot 來直觀地查看不同花類型的分布。
sns.boxplot(x="Species", y="Sepal.Length", data=iris_df)
# 下面的操作，將每一個Species所屬的點加到對應的位置，加上散點圖，
# 振動值jitter=True 使各個散點分開，要不然會是一條直線
# 注意此處要將坐標圖用ax先保存起來，這樣第二次才會在原來的基礎上加上散點圖
ax = sns.boxplot(x="Species", y="Sepal.Length", data=iris_df)
ax = sns.stripplot(x="Species", y="Sepal.Length", data=iris_df, jitter=True, edgecolor="gray")
# violinplot 小提琴圖，查看密度分布，結合了前面的兩個圖，并且進行了簡化
# 數據越稠密越寬，越稀疏越窄
sns.violinplot(x="Species", y="Sepal.Length", data=iris_df, height=6)
# sns.kdeplot == kernel density 核密度圖（單個變量）
sns.FacetGrid(iris_df, hue="Species", height=6).map(sns.kdeplot, "Sepal.Length").add_legend()
# pairplot 任意兩個變量間的關系
sns.pairplot(iris_df, hue="Species", height=3)
# 模型構建比較簡單，關鍵是模型的調參
train_df=test_df=iris_df.sample(frac=0.8,replace=False, random_state=None)
train_X=train_df.drop(['Species'],axis=1)
train_Y=train_df['Species']
# 由于么有提供建模數據集，所以我們隨機從樣本集中選擇40%的數據集
# replace=False 無放回的抽取
# random-state 數據不能重復
test_df=iris_df.sample(frac=0.9,replace=False, random_state=None)
test_df.head()
test_X=test_df.drop(['Species'],axis=1)
test_Y=test_df['Species']
model=DecisionTreeClassifier()
model.fit(train_X, train_Y)
prediction = model.predict(test_X)
print('The accuracy of the Decision Tree is: {0}'.format(metrics.accuracy_score(prediction,test_Y)))
分類決策樹總共有12個參數可以自己調整，這么多參數一個個記起來太麻煩，我們可以把這些參數分成幾個類別：
1）分類策略：有兩個參數 ‘entropy’（熵） 和 ‘gini’（基尼系數）可選，默認為gini。
2）max_depth（樹的最大深度）：默認為None，此時決策樹在建立子樹的時候不會限制子樹的深度。也可以設置具體的整數，一般來說，數據少或者特征少的時候可以不管這個值。如果模型樣本量多，特征也多的情況下，推薦限制這個最大深度，具體的取值取決于數據的分布。常用的可以取值10-100之間。
3）min_samples_split（分割內部節點所需的最小樣本數）：意思就是只要在某個結點里有k個以上的樣本，這個節點才需要繼續劃分，這個參數的默認值為2，也就是說只要有2個以上的樣本被劃分在一個節點，如果這兩個樣本還可以細分，這個節點就會繼續細分
4）min_samples_leaf（葉子節點上的最小樣本數）：當你劃分給某個葉子節點的樣本少于設定的個數時，這個葉子節點會被剪枝，這樣可以去除一些明顯異常的噪聲數據。默認為1，也就是說只有有兩個樣本類別不一樣，就會繼續劃分。如果是int，那么將min_samples_leaf視為最小數量。如果為float，則min_samples_leaf為分數，ceil(min _ samples _ leaf * n _ samples)為每個節點的最小樣本數。
03
樸素貝葉斯
1、樸素貝葉斯算法
樸素貝葉斯算法依據概率論中貝葉斯定理建立模型，前提假設各個特征之間相互獨立（這也是正式“樸素”的含義），這個假設非常極端，因為實際場景中多個特征一般存在相關性，特征相對獨立的假設使得算法變得簡單，因此在特征值有強相關性的場景中容易出現分類不準的問題。
其數學原理很容易理解：如果你看到一個人總是做好事，則會推斷那個人多半會是一個好人。這就是說，當你不能準確判斷時候，可以依靠事物特定本質相關的事件出現的多少（概率）作為判斷依據，貝葉斯定理：
該公式表示在B發生的條件下A發生的條件概率，等于A事件發生條件下B事件發生的條件概率乘以A事件的概率，再除以B事件發生的概率。公式中，P(A)叫做先驗概率，P(A/B)叫做后驗概率。
舉個栗子：一個非常炎熱的夏天晚上，走在校園里面，伸手不見五指.......lol，這個時候迎面走來一個人，太遠看不清楚ta的性別，但我們知道ta的特征是“短褲+短發”，而且事先有一些學生的調查樣本，需要你根據某些特性大致判斷Ta的性別，請問你應該怎么分類？
這樣分析，我們首先計算求得P(boy|短褲短發)和P(girl|短褲短發)然后比較兩者大小，作為依據判定性別，也就是我們根據以往數據中穿著短褲短發的人中boy和girl的條件概率作為依據，來判斷當我們看見“短褲短發”人的性別，在這個例子中我們很明顯把ta判定是個boy，核心思想就是這么簡單：
2、拉普拉斯修正
由于特征空間較為稀疏，因此，常常會出現概率為0的情況，在這種情況下，需要對其進行一些修正。常用的修正方法是拉普拉斯修正法，就是使得計算條件概率時候分子+1，很容易理解；
蘑菇數據集
該數據集包含了8124個樣本和22個變量（如蘑菇的顏色、形狀、光滑度等），是機器學習分類算法算法不可多得的一個優質數據集。
3、數據探索
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
import numpy as np
# 修改baseUrl的路徑即可完成數據讀取修改
baseUrl="C:\Users\71781\Desktop\2020\ML-20200422\bayes\"
mushrooms=pd.read_csv(baseUrl+"mushrooms.csv")
mushrooms.columns=['class','cap-shape','cap-surface','cap-color','ruises','odor','gill-attachment','gill-spacing','gill-size','gill-color','stalk-shape','stalk-root','stalk-surface-above-ring','stalk-surface-below-ring','stalk-color-above-ring','stalk-color-below-ring','veil-type','veil-color','ring-number','ring-type','spore-print-color','population','habitat']
mushrooms.shape
pd.set_option("display.max_columns",100) #讓所有列都能加載出來
mushrooms.head()
# 可以發現，所有特征都是離散的，都屬于分類型
# class標識有毒無毒
np.unique(mushrooms['cap-shape'])
fig,(ax1,ax2)=plt.subplots(1,2,figsize=(15,5))
# 探究 形狀和顏色對于是否有毒的貢獻度，發現形狀為b的無毒蘑菇比例大
sns.countplot(x='cap-shape',data=mushrooms,hue='class',ax=ax1)
sns.countplot(x='cap-surface',data=mushrooms,hue='class',ax=ax2)
sns.countplot(x='cap-color',hue='class',data=mushrooms)
# 把有毒無毒換成0/1類型，1標識無毒
mushrooms['class'].replace('e',1,inplace=True)
mushrooms['class'].replace('p',0,inplace=True)
# 計算每個顏色無毒的概率
perc = mushrooms[["cap-color", "class"]].groupby(['cap-color'],as_index=False).mean()
perc
sns.barplot(x='cap-color',y='class',data=perc)
# 使用sklearn進行預處理
from sklearn.preprocessing import LabelEncoder
labelencoder=LabelEncoder()
for col in mushrooms.columns:
mushrooms[col] = labelencoder.fit_transform(mushrooms[col])
mushrooms.head()
sns.countplot(x='cap-shape',data=mushrooms,hue='class',)
4、建立模型
X=mushrooms.drop('class',axis=1) #Predictors
y=mushrooms['class'] #Response
#X.head()
#這里采用用啞變量編碼，為的是后面能更好的計算特征的各屬性的重要性，并且避免數值變量分類時偏向于數值大的屬性
X=pd.get_dummies(X,columns=X.columns,drop_first=True)
X.head()
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1234)
# 貝葉斯
from sklearn.naive_bayes import GaussianNB
from sklearn import metrics
model2 = GaussianNB()
model2.fit(X_train, y_train)
prediction2 = model2.predict(X_test)
print('The accuracy of the Decision Tree is: {0}'.format(metrics.accuracy_score(prediction2,y_test)))
04
K-means聚類
1、算法描述
所謂物以類聚-人以群分，“類”指的是具有相似性的集合，聚類是指將數據集劃分為若干類，使得各個類之內的數據最為相似，而各個類之間的數據相似度差別盡可能的大。聚類分析就是以相似性為基礎，在一個聚類中的模式之間比不在同一個聚類中的模式之間具有更多的相似性。對數據集進行聚類劃分，屬于無監督學習。
K-Means是最常用且簡單的聚類算法，最大特點是好理解，運算速度快，時間復雜度近于線性，適合挖掘大規模數據集。但是只能應用于連續型的數據，并且一定要在聚類前需要手工指定要分成幾類；
K-Means采用距離作為相似性指標，從而發現給定數據集中的K個類，且每個類的中心是根據類中所有數值的均值得到的，每個類的中心用聚類中心來描述。對于給定的一個（包含n個一維以及一維以上的數據點的）數據集X以及要得到的類別數量K，選取歐式距離作為相似度指標，聚類目標是使得類的聚類平方和最小，即最小化：
2、K-Means算法流程：
- 隨機選取K個樣本作為聚類中心；
- 計算各樣本與各個聚類中心的距離；
- 將各樣本回歸于與之距離最近的聚類中心；
- 求各個類的樣本的均值，作為新的聚類中心；
- 判定：若類中心不再發生變動或者達到迭代次數，算法結束，否則回到第二步。
from sklearn import datasets
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
URL="C:\Users\71781\Desktop\2020\ML-20200422\K-means\"
data=pd.read_csv(URL+"xigua.csv")
data.head()
data.describe()
fig,(axis1,axis2) = plt.subplots(1,2,figsize=(10,3))
sns.distplot(data["density"],ax=axis1)
sns.distplot(data["sugercontent"],ax=axis2)
sns_test=sns.scatterplot(x="density",y="sugercontent",data=data)
import sklearn.cluster as sc
# n_clusters: 聚類數
model = sc.KMeans(n_clusters=4)
# 不斷調整聚類中心，直到最終聚類中心穩定則聚類完成
model.fit(data)
# 獲取訓練結果的聚類中心
centers = model.cluster_centers_
n_clusters：整型，缺省值=8 ，生成的聚類數。
max_iter：整型，缺省值=300 ，執行一次k-means算法所進行的最大迭代數。
n_init：整型，缺省值=10 ，用不同的聚類中心初始化值運行算法的次數，最終解是在inertia意義下選出的最優結果。
init：有三個可選值：’k-means++’， ‘random’，或者傳遞一個ndarray向量，此參數指定初始化方法，默認值為 ‘k-means++’。（１）‘k-means++’ 用一種特殊的方法選定初始聚類，可加速迭代過程的收斂（２）‘random’ 隨機從訓練數據中選取初始質心。（３）如果傳遞的是一個ndarray，則應該形如 (n_clusters, n_features) 并給出初始質心。
precompute_distances：三個可選值，‘auto’，True 或者 False，預計算距離，計算速度更快但占用更多內存。（１）‘auto’：如果 樣本數乘以聚類數大于 12million 的話則不預計算距離。（２）True：總是預先計算距離。（３）False：永遠不預先計算距離。
tol：float類型，默認值= 1e-4 與inertia結合來確定收斂條件。
n_jobs：整形數。 指定計算所用的進程數。內部原理是同時進行n_init指定次數的計算。（１）若值為 -1，則用所有的CPU進行運算。若值為1，則不進行并行運算。（２）若值小于-1，則用到的CPU數為(n_cpus + 1 + n_jobs)。因此如果 n_jobs值為-2，則用到的CPU數為總CPU數減1。
random_state：整型或 numpy.RandomState 類型，可選，用于初始化質心的生成器（generator）。如果值為一個整數，則確定一個seed。此參數默認值為numpy的隨機數生成器。
copy_x：布爾型，默認值=True ，當我們precomputing distances時，將數據中心化會得到更準確的結果。如果把此參數值設為True，則原始數據不會被改變。如果是False，則會直接在原始數據上做修改并在函數返回值時將其還原。但是在計算過程中由于有對數據均值的加減運算，所以數據返回后，原始數據和計算前可能會有細小差別。
05
關聯規則挖掘
1、關聯規則簡介
關聯規則挖掘可以讓我們從數據集中發現項與項之間的關系，它在我們的生活中有很多應用場景，“購物籃分析”就是一個常見的場景，這個場景可以從消費者交易記錄中發掘商品與商品之間的關聯關系，進而通過商品捆綁銷售或者相關推薦的方式帶來更多的銷售量。
- 搞懂關聯規則中的幾個重要概念：支持度、置信度、提升度
- Apriori 算法的工作原理
- 在實際工作中，我們該如何進行關聯規則挖掘
2、關聯規則中重要的概念
我舉一個超市購物的例子，下面是幾名客戶購買的商品列表：
|
訂單編號 |
購買商品 |
|
1 |
牛奶、面包、尿布 |
|
2 |
可樂、面包、尿布、啤酒 |
|
3 |
牛奶、尿布、啤酒、雞蛋 |
|
4 |
面包、牛奶、尿布、啤酒 |
|
5 |
面包、牛奶、尿布、可樂 |
支持度
支持度是個百分比，它指的是某個商品組合出現的次數與總次數之間的比例。支持度越高，代表這個組合出現的頻率越大。
我們看啤酒出現了3次，那么5筆訂單中啤酒的支持度是3/5=0.6。同理，尿布出現了5次，那么尿布的支持度是5/5=1。尿布和啤酒同時出現的支持度是3/6=0.6。
置信度
它指的就是當你購買了商品 A，會有多大的概率購買商品 B。
我們可以看上面的商品，購買尿布的同時又購買啤酒的訂單數是3，購買啤酒的訂單數是3，那么（尿布->啤酒）置信度= 3/3=1。
再看購買了啤酒同時購買尿布的訂單數是3，購買尿布的訂單數是5，那么（啤酒->尿布）置信度=3/5=0.6。
提升度
提升度代表的是“商品 A 的出現，對商品 B 的出現概率提升的”程度。所以我們在做商品推薦的時候，重點考慮的是提升度。
我們來看提升度公式：
怎么解讀1.67這個數值呢？
- 提升度 (A→B)>1：代表有提升
- 提升度 (A→B)=1：代表有沒有提升，也沒有下降
- 提升度 (A→B)<1：代表有下降。
其實看上面提升度的公式，我們就可以理解，也就是AB同時出現的次數越多，單獨出現B的次數越少，那么支持度也就越大也就是B的出現總是伴隨著A的出現，那么A對B出現的概率就越有提升！
3、Apriori 的工作原理
我們一起來看下經典的關聯規則 Apriori 算法是如何工作的。
Apriori 算法其實就是查找頻繁項集 (frequent itemset) 的過程，所以我們需要先了解是頻繁項集。
頻繁項集就是支持度大于等于最小支持度閾值的項集，所以小于最小值支持度的項目就是非頻繁項集，而大于等于最小支持度的項集就是頻繁項集。
下面我們來舉個栗子：
假設我隨機指定最小支持度是0.2。首先，我們先計算單個商品的支持度：
|
購買商品 |
支持度 |
|
牛奶 |
4/5 |
|
面包 |
4/5 |
|
尿布 |
5/5 |
|
可樂 |
2/5 |
|
啤酒 |
3/5 |
|
雞蛋 |
1/5 |
因為最小支持度是 0.2，所以你能看到商品 雞蛋 是不符合最小支持度的，不屬于頻繁項集，于是經過篩選商品的頻繁項集如下：
|
購買商品 |
支持度 |
|
牛奶 |
4/5 |
|
面包 |
4/5 |
|
尿布 |
5/5 |
|
可樂 |
2/5 |
|
啤酒 |
3/5 |
在這個基礎上，我們將商品兩兩組合，得到兩個商品的支持度：
|
購買商品 |
支持度 |
|
牛奶、面包 |
3/5 |
|
牛奶、尿布 |
4/5 |
|
牛奶、可樂 |
1/5 |
|
牛奶、啤酒 |
2/5 |
|
面包、尿布 |
4/5 |
|
面包、可樂 |
2/5 |
|
面包、啤酒 |
2/5 |
|
尿布、可樂 |
2/5 |
|
尿布、啤酒 |
3/5 |
|
可樂、啤酒 |
1/5 |
篩選大于最小支持度（0.2）的數據后
|
購買商品 |
支持度 |
|
牛奶、面包 |
3/5 |
|
牛奶、尿布 |
4/5 |
|
牛奶、啤酒 |
2/5 |
|
面包、尿布 |
4/5 |
|
面包、可樂 |
2/5 |
|
面包、啤酒 |
2/5 |
|
尿布、可樂 |
2/5 |
|
尿布、啤酒 |
3/5 |
在這個基礎上，我們再將商品三個組合，得到三個商品的支持度：
|
購買商品 |
支持度 |
|
牛奶、面包、尿布 |
3/5 |
|
牛奶、面包、可樂 |
1/5 |
|
牛奶、面包、啤酒 |
1/5 |
|
面包、尿布、可樂 |
1/5 |
|
面包、尿布、啤酒 |
2/5 |
|
尿布、可樂、啤酒 |
1/5 |
篩選大于最小支持度（0.2）的數據后
|
購買商品 |
支持度 |
|
牛奶、面包、尿布 |
3/5 |
|
面包、尿布、啤酒 |
2/5 |
在這個基礎上，我們將商品四個組合，得到四個商品的支持度：
|
購買商品 |
支持度 |
|
牛奶、面包、尿布、可樂 |
1/5 |
|
牛奶、面包、尿布、啤酒 |
1/5 |
|
面包、尿布、可樂、啤酒 |
1/5 |
再次篩選大于最小支持度（0.2）數據的話，就全刪除了，那么，此時算法結束，上一次的結果就是我們要找的頻繁項，也就是{牛奶、面包、尿布}、{面包、尿布、啤酒}。
我們來總結一下上述Apriori算法過程：
- K=1，計算 K 項集的支持度
- 篩選掉小于最小支持度的項集
- 如果項集為空，則對應 K-1 項集的結果為最終結果
- 否則 K=K+1，重復 1-3 步
我們可以看到 Apriori 在計算的過程中有以下幾個缺點：
- 可能產生大量的候選集。因為采用排列組合的方式，把可能的項集都組合出來了
- 每次計算都需要重新掃描數據集，來計算每個項集的支持度
這就好比我們數據庫中的“全表掃描”查詢一樣，非常浪費IO和時間。在數據庫中我們都知道使用索引來快速檢索數據，那Apriori 能優化嗎？
4、Apriori 的改進算法：FP-Growth 算法
FP-growth算法是基于Apriori原理的，通過將數據集存儲在FP樹上發現頻繁項集，但不能發現數據之間的關聯規則。FP-growth算法只需要對數據庫進行兩次掃描，而Apriori算法在求每個潛在的頻繁項集時都需要掃描一次數據集，所以說Apriori算法是高效的。其中算法發現頻繁項集的過程是：(1)構建FP樹；(2)從FP樹中挖掘頻繁項集。
創建項頭表
概念知識不在這湊字數了，我們直接來干貨！假設我們從以下數據中來挖掘頻繁項。
首先創建，項頭表，這一步的流程是先掃描一遍數據集，對于滿足最小支持度的單個項按照支持度從高到低進行排序，這個過程中刪除了不滿足最小支持度的項（假設最小支持度是0.2）。
構建FP樹
整個流程是需要再次掃描數據集，對于每一條數據，按照支持度從高到低的順序進行創建節點（也就是第一步中項頭表中的排序結果），節點如果存在就將計數 count+1，如果不存在就進行創建。同時在創建的過程中，需要更新項頭表的鏈表。
先把原始數據按照支持度排序，那么原始數據變化如下：
下面我們把以上每行數據，按照順序插入到FP樹中，注意FP樹的根節點記為 NULL 節點。
接下來插入第二行數據，由于第二行數據第一個數據也是B，和已有的樹結構重合，那么我們保持原來樹結構中的B位置不變，同時計數加1，C、D是新增數據，那么就會有新的樹分叉，結果如下圖：
以此類推，讀取下面的三行數據到FP樹中
最后生成的FP數如下：
根據FP數挖掘頻繁項
我們終于把FP樹建立好了，那么如何去看這顆樹呢？得到 FP 樹后，需要對每一個頻繁項，逐個挖掘頻繁項集。具體過程為：首先獲得頻繁項的前綴路徑，然后將前綴路徑作為新的數據集，以此構建前綴路徑的條件 FP 樹。然后對條件 FP 樹中的每個頻繁項，獲得前綴路徑并以此構建新的條件 FP 樹。不斷迭代，直到條件 FP 樹中只包含一個頻繁項為止（反正我第一次看完這句話是沒理解）。
FP樹是從下往上看了，也就是根據子節點找父節點，接下來還是來圖解~
首先，我們看包含A的頻繁項：
我們可以看到包含A的樹有兩個，我們先看樹2，可以得到路徑{B:2,C:2}，此處的2是根據A出現的次數定的。接著我們創建FP樹，具體的創建過程和上面創建 FP 樹的過程一樣，如下圖：
注意此時頭指針表中包含兩個元素，所以對每個元素，需要獲得前綴路徑，并將前綴路徑創建成條件 FP 樹，直到條件 FP 樹中只包含一個元素時返回。
- 對元素 B，獲得前綴路徑為{}，則頻繁項集返回{A:2,B:2};
- 對元素 C，獲得前綴路徑{B:2}，則將前綴路徑創建成條件 FP 樹，如下圖 所示。
- 注意此時條件 FP 樹中只包含一個元素，故返回頻繁項集{A:2,C:2,B:2}。由于元素 C 也是頻繁項，所以{A:2,C:2}也是頻繁項集。
再加上{A:2}本身就是頻繁項集，所以 A 對應的頻繁項集有：{A:2},{A:2,C:2} ,{A:2,B:2},{A:2,C:2,B:2}。
同理，我們來看樹1，樹1比較簡單，就一個路徑{B:1}，根據上述方法我們得到此分支頻繁項為{A:1,B:1},{A:1}。
綜上，我們可以看到兩個分支都包含頻繁項{A,B},{A}的，此時我們進行合并兩個分支，得到包含A的頻繁項：{A:3},{A:3,B:3},{A:2,C:2} ,{A:2,C:2,B:2}，我們用出現的次數轉換下，即 (A,): 3, (A, B): 3, (A, C): 2, (A, B, C): 2。
同理，按照上述方法，我們可以依次找到包含B的頻繁項是(D): 2, (C, D): 2, (B, D): 2, (B, C, D): 2, (C): 4, (B, C): 4, (B): 5。
5、實踐總結
經典的算法，很多大神已經實現，我們直接拿來用就行了，比如上面的FP-GROWTH算法，介紹一款專門的包pyfpgrowth。
