【正文】 ：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)]= 則信息增益為： – = 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)]= 則信息增益為： – =綜上所述，由于按特征紅的比按特征圓的劃分的信息增益大，所以特征紅的為最優(yōu)劃分特征。為了便于理解，用表1所示數(shù)據(jù)集進行詳細說明。關于基尼指數(shù)的詳細內容會在下一篇文章介紹。除了可以使用信息增益和信息增益比來選擇最優(yōu)劃分特征之外，基尼指數(shù)也可以用來實現(xiàn)這個目的。為信息增益 g(D,A) 與數(shù)據(jù)集 D 關于特征 A 的取值的熵 HA(D) 的比值，即其中,其中，n 是特征 A 取值的個數(shù)。特征 A 對數(shù)據(jù)集 D 的信息增益 g(D,A)為 D 的信息熵與按特征 A 進行劃分后 D 的信息熵之差，即其中， . 信息增益比 – 用于 決策樹信息增益比為了避免傾向于選擇屬性值多的特征作為最優(yōu)特征這個問題，在信息增益的基礎上引入了類似懲罰因子的概念。. 信息增益用于ID3決策樹信息增益，顧名思義就是原數(shù)據(jù)集的信息熵比劃分后數(shù)據(jù)集的信息熵大的程度。. 決策樹原理. 選擇最優(yōu)特征決策樹通過不斷選擇最優(yōu)特征劃分數(shù)據(jù)集，對劃分后的子數(shù)據(jù)集不斷迭代得選擇最優(yōu)特征劃分，直到所有的數(shù)據(jù)集屬于同一個類別，或者沒有特征可以選擇為止。信息增益比可以很好的解決這個問題。這種缺陷體現(xiàn)在信息增益對選擇屬性取值多的特征更有利。用這種方法選擇的特征是使得信息增益比最大的特征。用所有類別所有可能值包含的信息期望值表示信息熵，計算方法如下：ID3 決策樹利用了信息增益來選擇最優(yōu)特征，用這種方法選擇的特征是使得信息熵增益最大的特征。我們都知道物理中的熵用來衡量混亂程度，熵越大說明越混亂，熵越小說明越單一。衡量數(shù)據(jù)的混亂程度就必須提到信息和信息熵的概念。這兩種決策樹的不同之處是劃分數(shù)據(jù)集的最優(yōu)特征選擇方法不同。不圓的不是蘋果。圖 12 決策樹示例圖1所示決策樹用來將數(shù)據(jù)分為兩類，是蘋果和非蘋果。注意本文中提到的特征和屬性是同一個概念。決策樹利用了樹型結構進行決策，是經(jīng)典的 ifthen 結構。而CART決策樹，即分類回歸樹，直接支持連續(xù)型屬性值。6. 決策樹基本原理決策樹算法又分很多種，常用的有ID3， 和 CART 決策樹。study39。campus39。book39。已知：如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1) )，則 P(C0|X) P(C1|X)，可得 X 屬于 C0 類；如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1) )，則 P(C0|X) P(C1|X)，可得 X 屬于 C1 類。然后，需要將文本列表轉換成詞向量列表，文本中的詞在詞向量中出現(xiàn)為 1，未出現(xiàn)為 0, 如表格 表格 7所示：表格 6 訓練文本詞向量列表類別訓練文本1[1, 1, 1, 1, 0, 0, 0, 0]0[0, 0, 0, 0, 1, 1, 1, 0]1[1, 0, 1, 0, 0, 0, 0, 0]0[0, 0, 0, 0, 1, 0, 0, 1]表格 7 測試文本詞向量列表類別訓練文本？[1, 0, 1, 1, 0, 0, 0, 0]. 從詞向量到條件概率和先驗概率由上一章知，條件概率 P(X|C) =P(X0|C) *P(X1|C) *P(X2|C) *P(X3|C) *… *P(Xn|C),為防止概率為 0 影響結果，加入拉普拉斯平滑后 P(Xi|C) = (|Dc,xi| + 1) / (|Dc,x| + 2),先驗概率 P(C) = |Dc| / |D|。others39。book39。campus39。yes39。sky39。game39。others39。study39。campus39。student39。book39。. 從文本到詞向量首先需要將文本表示成詞向量，去掉重復的詞。, 39。, 39。表格 5 示例測試數(shù)據(jù)集類別訓練文本？39。, 39。039。, 39。139。, 39。, 39。039。, 39。, 39。, 39。表格 4 示例訓練數(shù)據(jù)集類別訓練文本139。最終比較 P(C0|X)、P(C1|X)大小得到 X 屬于 C0 類還是 C1 類。P(C1) ) = log(P(X|C1)) + log(P(C1)) = log(P(X0|C1)) + log(P(X1|C1)) + log(P(X2|C1)) + …+ log(P(Xn|C1)) + log(P(C1))。鑒于此，往往在實際運算中，會借助 log 函數(shù)，比較 log(P(X|C0) *P(C0)) 和 log(P(X|C1) *P(C1))的大小來判斷 X 所屬類別。至此，通過 P(X|C0) *P(C0) 和P(X|C1) *P(C1)的大小比較，可得 X 所屬類別。為了避免 P(Xi|C)為 0 造成 P(X|C)為 0 而影響分類結果，在此引入拉普拉斯平滑，本文分別給分子和分母加上 1 和 2，即 P(Xi|C) = (|Dc,xi| + 1) / (|Dc,x| + 2)。由上述可知，需要計算 P(X|C)和 P(C)。其中 P(C)稱為先驗概率，P(X|C)是條件概率，P(C|X)稱為后驗概率，將后驗概率最大的類作為 X 的類別輸出。. 樸素貝葉斯原理樸素貝葉斯模型主要利用貝葉斯公式進行展開。這種情況需要考慮半樸素貝葉斯，即放松屬性之間條件獨立這一假設，一定程度上考慮屬性之間的依賴關系。這樣就完成了文本到數(shù)值上的轉化，方便后期計算條件概率和先驗概率。詞向量的每一項是該詞出現(xiàn)的頻數(shù)。樸素貝葉斯模型主要應用在文本分類方面。5. NaiveBayes基本原理樸素貝葉斯模型主要用來分類，但是與 SVM 模型不同的的是，樸素貝葉斯模型不需要針對目標變量建立模型，而是借助貝葉斯公式計算樣本屬于各個類別的概率，然后取概率值大的類別作為分類類別。以頻繁項集{a,b,c}為例，構建所有可能的規(guī)則：{b,c} {a}, {a,c} ,{a,b} {c},{c} {a,b}, {a,c},{a} {b,c}。圖 11 b元素的前綴路徑構成的條件FP樹將其他元素 a,b,d 同樣按照上述對 c 的操作，得到表格 3所示頻繁項集。由于元素 b 也是頻繁項，所以{c,b}也是頻繁項集。2. 對元素 b，獲得前綴路徑{a}，則將前綴路徑創(chuàng)建成條件 FP 樹，如圖 11所示。圖 10 c元素的前綴路徑構成的條件 FP 樹注意此時頭指針表中包含兩個元素，所以對每個元素，需要獲得前綴路徑，并將前綴路徑創(chuàng)建成條件 FP 樹，直到條件 FP 樹中只包含一個元素時返回。首先，獲得以 c 元素的前綴路徑{a:2,b:2}，注意此處 a 和 b 的頻數(shù)為 2 是因為 c 的頻數(shù)為 2，所以與 c 共同出現(xiàn)的 a 和 b 的頻數(shù)就都為 2。不斷迭代，直到條件 FP 樹中只包含一個頻繁項為止。具體過程為：首先獲得頻繁項的前綴路徑，然后將前綴路徑作為新的數(shù)據(jù)集，以此構建前綴路徑的條件 FP 樹。注意，F(xiàn)P 樹的根節(jié)點是 null。創(chuàng)建 FP 樹時，當待添加的記錄與 FP 樹中的路徑相同，則只需更新元素對應的頻數(shù)；如果待添加的記錄與 FP 樹存在不一致，則在不一致的地方分叉，創(chuàng)建新的結點。接著，將出現(xiàn)次數(shù)小于最小支持度 2 的元素（即 e）在數(shù)據(jù)集中刪除，并將數(shù)據(jù)集按出現(xiàn)次數(shù)由高到低排序，得表格 2。下面用上文提到的數(shù)據(jù)集展開說明，假設最小支持度為 2。表格 1 示例數(shù)據(jù)集數(shù)據(jù)集a,b,cc,d,b,ad,e,ab,a. 構建 FP 樹構建 FP 樹時，首先統(tǒng)計數(shù)據(jù)集中各個元素出現(xiàn)的頻數(shù)，將頻數(shù)小于最小支持度的元素刪除，然后將數(shù)據(jù)集中的各條記錄按出現(xiàn)頻數(shù)排序，剩下的這些元素稱為頻繁項；接著，用更新后的數(shù)據(jù)集中的每條記錄構建 FP 樹，同時更新頭指針表。. 頻繁項集挖掘原理頻繁項集挖掘分為構建 FP 樹，和從 FP 樹中挖掘頻繁項集兩步。}，該規(guī)則的置信度為 。} {39。39。如規(guī)則{39?，F(xiàn)實場景中可以用來發(fā)現(xiàn)很多規(guī)律，下面舉個例子。}的置信度為 / = 。} {39。, 39。}的支持度為 ，則{39。, 39。}的支持度為 ，{39。, 39。, 39。假設{39。面包39。雞蛋39。牛奶39。面包39。雞蛋39。牛奶39。面包39。雞蛋39。. 置信度 Confidence置信度是針對某個關聯(lián)規(guī)則定義的。面包39。雞蛋39。面包39。雞蛋39。. 支持度 Support支持度指某頻繁項集在整個數(shù)據(jù)集中的比例。關聯(lián)規(guī)則可以用來發(fā)現(xiàn)很多有趣的規(guī)律。牛奶39。面包39。雞蛋39。通俗來說，就是如果 A 發(fā)生了，那么 B 也很有可能會發(fā)生。. 關聯(lián)規(guī)則簡介關聯(lián)規(guī)則是在頻繁項集的基礎上得到的。FP 樹是一種前綴樹，由頻繁項的前綴構成，具體細節(jié)會在頻繁項集挖掘原理一節(jié)介紹。FPgrowth，即 Frequent Pattern Growth，它通過構建 FP 樹(即 Frequent Pattern Tree)這樣的數(shù)據(jù)結構，巧妙得將數(shù)據(jù)存儲在 FP 樹中，只需要在構建 FP 樹時掃描數(shù)據(jù)庫兩次，后續(xù)處理就不需要再訪問數(shù)據(jù)庫了。主流的頻繁項集挖掘算法有 Apriori 和 FPgrowth。3. 用于發(fā)現(xiàn)事物的熱點信息。也就是說，在大量的用戶搜索記錄中，頻繁項集和置信度共同出現(xiàn)在了大多數(shù)的搜索記錄中。這種場景其實我們經(jīng)常會遇到。還可用于制定打折促銷活動，給買了啤酒和尿布的客戶打折，也可以增加銷量。那么發(fā)現(xiàn)這些頻繁項集有什么意義呢？1. 用于制定營銷策略。這就引出了本文的主題之一，即頻繁項集。有研究發(fā)現(xiàn)，在超市的訂單記錄中，啤酒和尿布總是頻繁共同出現(xiàn)在同一條訂單記錄里。關聯(lián)分析分為頻繁項集挖掘和關聯(lián)規(guī)則挖掘。第一篇中的 SVM 就屬于分類。4. 頻繁項集與關聯(lián)規(guī)則FPgrowth基本原理. 從啤酒和尿布引出的頻繁項集在上一節(jié)中，主要介紹了支持向量機 SVM 模型的原理和實現(xiàn)。有朋友就會問，求出 alpha 之后呢？如何判斷新樣本數(shù)據(jù)屬于 1 還是1 呢？別忘了，在最優(yōu)化求解一節(jié)，我們得到了如下：若 f(x)大于 0，則新樣本數(shù)據(jù)屬于 1；否則，新樣本數(shù)據(jù)屬于1。那么問題來了，如何選擇 alpha1 和 alpha2 呢？選擇違背下列 KKT 條件推導結果的 alpha 作為 alpha1： 為了讓每次變化盡可能大，alpha2 的選擇滿足如下式子最大，即步長最大化：其中 E 是上面提到過的預測值和真實值差值的絕對值，也就是誤差值。下面是詳細的 SMO 過程。說直白些，SMO 就是在約束條件下對目標函數(shù)的優(yōu)化求解算法。由于目標變量中自變量 alp