【正文】 多次掃描數(shù)據(jù)庫，這就使得該算法本身不適合大數(shù)據(jù)量。這種特性使得 FPgrowth 算法比 Apriori 算法速度快。挖掘出頻繁項集后，可以從頻繁項集中進一步挖掘關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則指由集合 A，可以在某置信度下推出集合 B。舉個例子，有關(guān)聯(lián)規(guī)則如：{39。, 39。} {39。}，該規(guī)則的置信度是 ，意味著在所有買了雞蛋和面包的客戶中，有 90%的客戶還買了牛奶。這其中需要先闡明兩個概念：支持度和置信度。假設(shè)數(shù)據(jù)集有 10 條記錄，包含{39。, 39。}的有 5 條記錄，那么{39。, 39。}的支持度就是 5/10 = 。有關(guān)聯(lián)規(guī)則如{39。, 39。} {39。}，它的置信度計算公式為{39。, 39。, 39。}的支持度/{39。, 39。}的支持度。雞蛋39。面包39。牛奶39。雞蛋39。面包39。雞蛋39。面包39。牛奶39。關(guān)聯(lián)規(guī)則用于發(fā)現(xiàn) if then 這樣的規(guī)則，并可以給出這條規(guī)則的可信度（即置信度）。在信息安全領(lǐng)域，需要根據(jù)已有流量數(shù)據(jù)制定規(guī)則，來判斷是否觸發(fā)安全報警。數(shù)據(jù)包大39。多個ip地址同時發(fā)送數(shù)據(jù)39。異常39。這條規(guī)則表示，當流量數(shù)據(jù)包大，并有多個ip地址同時向目標ip發(fā)送數(shù)據(jù)時，則有 85%的概率存在異常，需要觸發(fā)報警。本節(jié)用如下表所示的數(shù)據(jù)集作為例子展開，該示例數(shù)據(jù)集共四條數(shù)據(jù)。頭指針表包含所有頻繁項及它們的頻數(shù)，還有每個頻繁項指向下一個相同元素的指針，該指針主要在挖掘 FP 樹時使用。首先，統(tǒng)計數(shù)據(jù)集中各元素出現(xiàn)的次數(shù)，得 a 出現(xiàn) 4 次, b 出現(xiàn) 3 次, c 出現(xiàn) 2 次, d 出現(xiàn) 2 次, e 出現(xiàn) 1 次。表格 2 示例數(shù)據(jù)集數(shù)據(jù)集a,b,ca,b,c,da,da,b然后，用更新后的數(shù)據(jù)集中的記錄創(chuàng)建 FP 樹，并同時更新頭指針表。如圖 6~圖 9所示。圖 6 向FP樹添加第一條記錄{ a,b,c }圖 7向FP樹添加第二條記錄{ a,b,c,d }圖 8向FP樹添加第三條記錄{ a ,d }圖 9向FP樹添加第四條記錄{ a ,b }. 挖掘頻繁項集得到 FP 樹后，需要對每一個頻繁項，逐個挖掘頻繁項集。然后對條件 FP 樹中的每個頻繁項，獲得前綴路徑并以此構(gòu)建新的條件 FP 樹。下面以元素 c 為例，從上文圖 9創(chuàng)建好的 FP 樹中挖掘頻繁項集。接著，創(chuàng)建條件 FP 樹，具體的創(chuàng)建過程和上一節(jié)創(chuàng)建 FP 樹的過程一樣，如圖 10所示。1. 對元素 a，獲得前綴路徑為{ }，則頻繁項集返回{c,a}。注意此時條件 FP 樹中只包含一個元素，故返回頻繁項集{c,b,a}。再加上{c}本身就是頻繁項集，所以 c 對應(yīng)的頻繁項集有：{c} {c,a} {c,b} {c,b,a}。表格 3 元素a,b,c,d對應(yīng)的頻繁項集元素頻繁項集a{ a }b{ b } { b,a }c{ c } { c,a } { c,b } { c,b,a }d{ d } { d,a }. 關(guān)聯(lián)規(guī)則挖掘原理關(guān)聯(lián)規(guī)則挖掘首先需要對上文得到的頻繁項集構(gòu)建所有可能的規(guī)則，然后對每條規(guī)則逐個計算置信度，輸出置信度大于最小置信度的所有規(guī)則。對每條規(guī)則計算置信度后，輸出滿足要求的規(guī)則即可。之所以稱之為樸素，是因為樸素貝葉斯模型假設(shè)各屬性之間是條件獨立的，該假設(shè)極大得簡化了運算，使得樸素貝葉斯模型變得非常簡單。這里需要用到向量空間模型，即將文本轉(zhuǎn)換成詞向量。在樸素貝葉斯中會將頻數(shù)進一步轉(zhuǎn)換成頻率。樸素貝葉斯模型也有它的優(yōu)缺點，優(yōu)點是模型簡單，計算快；缺點是依賴于屬性之間條件獨立這一假設(shè)，但是現(xiàn)實場景下很多情況并不滿足這一假設(shè)，使得樸素貝葉斯的準確率受到影響。由于篇幅有限，對半樸素貝葉斯感興趣的話可自行參照文末參考資源學習，本文重點介紹樸素貝葉斯的原理和實現(xiàn)。貝葉斯公式如下：公式中 P(C|X)表示 X 屬于類別 C 的概率，P(X|C)表示類別 C 中 X 出現(xiàn)的概率，P(C)表示類別 C 出現(xiàn)的概率。假設(shè)有 C0 和 C1 兩個類，由于 P(X)都是一樣的，所以不需要考慮 P(X),只需考慮如下：1. 如果P(X|C0) *P(C0) P(X|C1) *P(C1)，則 P(C0|X) P(C1|X)，可得 X 屬于 C0 類；2. 如果P(X|C0) *P(C0) P(X|C1) *P(C1)，則 P(C0|X) P(C1|X)，可得 X 屬于 C1 類。樸素貝葉斯假設(shè)屬性之間條件獨立，可得：P(X|C) =P(X0|C) *P(X1|C) *P(X2|C) *P(X3|C) *… *P(Xn|C)令 Dc 表示訓(xùn)練集 D 中第 C 類樣本組成的集合，可得：P(Xi|C) = |Dc,xi| / |Dc,x|，表示類別為 C 的樣本在第 i 個屬性上頻數(shù)總和除以類別為 C 的樣本集合中所有屬性頻數(shù)總和。又有 P(C) = |Dc| / |D|， 表示類別為 C 的樣本集合大小除以數(shù)據(jù)集 D 的樣本集合大小。但是小數(shù)連乘會造成所得值幾乎等于 0 的結(jié)果，從而無法比較大小。從而得：log(P(X|C0) *P(C0) ) = log(P(X|C0)) + log(P(C0)) = log(P(X0|C0)) + log(P(X1|C0)) + log(P(X2|C0)) + …+ log(P(Xn|C0)) + log(P(C0)),同理可得 log(P(X|C1) *. 用樸素貝葉斯進行文本分類利用樸素貝葉斯模型進行文本分類，首先需要將文本表示成詞向量，再從詞向量中計算得到條件概率 P(X|C)和先驗概率 P(C)，然后利用條件概率 P(X|C)與先驗概率 P(C)計算后驗概率 P(C0|X)、P(C1|X)。下面用表格 4所示訓(xùn)練數(shù)據(jù)和表格 5所示測試數(shù)據(jù)展開介紹。book39。student39。campus39。study39。others39。game39。sky39。campus39。 book 39。others39。yes39。book39。campus39。study39。將表 1 中示例數(shù)據(jù)集表示成詞向量如下：[ 39。, 39。, 39。, 39。, 39。, 39。, 39。, 39。 ]可以看出，重復(fù)的39。, 39。, 39。都只出現(xiàn)了一次。為防止小數(shù)連乘造成結(jié)果幾乎為 0，引入 log 函數(shù)，由于測試文本只包含 X0, X2, X3, 得:log(P(X|C0) *P(C0) ) = log(P(X0|C0)) + log(P(X2|C0)) + log(P(X3|C0)) + log(P(C0))log(P(X|C1) *P(C1) ) = log(P(X0|C1)) + log(P(X2|C1)) + log(P(X3|C1)) + log(P(C1))代入數(shù)據(jù)，得P(X0|C0) =P(X2|C0) =P(X3|C0) = (0 + 1) / (5 + 2) = 1/7,P(C0) =P(C1) = 2 / 4,P(X0|C1) =P(X2|C1) = (2 + 1) / (6 + 2) = 3/8,P(X3|C1) = (1 + 1) / (6 + 2) = 2/8,故可得:log(P(X|C0) *P(C0) ) = log(1/7) + log(1/7) + log(1/7) + log(2/4) = log(P(X|C1) *P(C1) ) = log(3/8) + log(3/8) + log(2/8) + log(2/4) = . 根據(jù)后驗概率分類由上一章知，因此后驗概率 P(C0|X)只需考慮 P(X|C0) *P(C0) ，同理后驗概率 P(C1|X)只需考慮 P(X|C1) *P(C1)。 , 所以 log(P(X|C1) *P(C1) ) log(P(X|C0) *P(C0) ), 即 P(C1|X) P(C0|X)，可得測試文本{39。, 39。, 39。}屬于類別 1。對于連續(xù)型屬性值，則需要額外利用連續(xù)屬性離散化技術(shù)將其劃分成離散型屬性值。由于篇幅限制CART樹會放在下一篇文章進行介紹，本文主要詳細介紹 ID3 和 決策樹。葉節(jié)點存儲類別，內(nèi)部節(jié)點代表特征或?qū)傩浴榱俗屪x者有一個感性的認識，請看圖 12所示決策樹。如圖中所示，圓的和紅的，就是蘋果。圓的但不紅的不是蘋果。決策樹需要選擇最優(yōu)特征劃分數(shù)據(jù)集。用最優(yōu)特征劃分數(shù)據(jù)會使得數(shù)據(jù)集趨于更純，即數(shù)據(jù)集的類別數(shù)更單一，這樣的數(shù)據(jù)會更有序。待分類的事物可能劃分在多個類別中，則符號 Xi 的信息是:可知P(Xi) 越大，則 I(Xi) 越小，即Xi的概率越大，則Xi包含的信息越少。同樣，信息熵用來衡量信息中的混亂程度。而 。為什么要提出信息增益比呢？這是因為只考慮信息增益來劃分數(shù)據(jù)集是有缺陷的。因為按屬性取值多的特征劃分數(shù)據(jù)集后，劃分后的各個子數(shù)據(jù)集的類別更單一，即更趨于有序，這就使得劃分后的信息熵更小，那么信息增益就會更大。信息增益比通過引入類似懲罰因子的概念，對屬性取值多的特征會有一定懲罰。選擇最優(yōu)特征的算法有很多種，ID3 決策樹用信息增益選擇最優(yōu)特征， 決策樹用信息增益比選擇最優(yōu)特征。信息增益越大，說明劃分后的數(shù)據(jù)集信息熵更小，即該數(shù)據(jù)集類別更趨于一致。特征 A 對數(shù)據(jù)集 D 的信息增益比gg(D,A)HA(D) 就類似懲罰因子，對于屬性值多的特征，雖然信息增益 g(D,A) 會比較大，但是數(shù)據(jù)集 D 關(guān)于特征 A 的取值的熵 HA(D) 會比較大，因而兩者的比值信息增益比 gg(D,A) 會比較小。基尼指數(shù)主要用于 CART 樹(即分類回歸樹)的分類樹中的特征選擇。. 用 ID3 決策樹進行分類本節(jié)主要介紹用 ID3 決策樹進行分類。利用 決策樹進行分類的過程會在下節(jié)介紹。. 按最優(yōu)特征劃分數(shù)據(jù)集按特征紅的劃分數(shù)據(jù)集后，有兩種情況，第一種為如果是紅的:0,則分類:0。 圓的:0, 分類:0}接下來需要對數(shù)據(jù)子集{圓的:1,分類：1。由于剩下一個特征，故按特征圓的劃分數(shù)據(jù)子集。返回的決策樹用字典表示為：{39。: {0: 39。, 1: {39。: {0: 39。, 1: 39。}}}}. 用 決策樹進行分類為了讓讀者對 ID3 和 決策樹的不同之處有更好的理解，本節(jié)介紹用 決策樹進行分類。. 決策樹選擇最優(yōu)特征表格 8數(shù)據(jù)集的信息熵為:1/5 * log(1/5) 4/5 * log(4/5) = 1. 按特征圓的劃分數(shù)據(jù)集，則信息熵為：3/5 * H(D1) + 2/5 * H(D0)= 3/5 * [1/3 * log(1/3) – 2/3 * log(2/3)] + 2/5 * [2/2 * log(2/2)]= 則信息增益為： – = 數(shù)據(jù)集關(guān)于特征圓的的取值的熵為:3/5 * log(3/5) – 2/5 * log(2/5) = / = 2. 按特征紅的劃分數(shù)據(jù)集，則信息熵為：2/5 * H(D1) + 3/5 * H(D0)= 2/5 * [1/2 * log(1/2) – 1/2 * log(1/2)] + 3/5 * [3/3*log(3/3)]= 則信息增益為： – =數(shù)據(jù)集關(guān)于特征紅的的取值的熵為：2/5 * log(2/5) – 3/5 * log(3/5) = 則信息增益比為