機器學習簡明原理（DOC47頁）.docx

機器學習簡明原理說明：本文整理自IBM大數(shù)據(jù)學習文檔，原文作者：韓笑琳1. 關于機器學習的簡介機器學習是從大量數(shù)據(jù)中學習出特定規(guī)律的算法。其中提到的規(guī)律有很多種，比如分類、聚類、回歸、關聯(lián)分析等。分類就是給定大量帶標簽的數(shù)據(jù)，計算出未知標簽樣本的標簽取值。如年齡 40 歲以上、工科、研究生以上學歷，這類人薪資水平是高收入；年齡 20-30 歲、文科、大專學歷，這類人的薪資水平是低收入；現(xiàn)有一位 23 歲大專文科人士，求該人的薪資水平是哪類？根據(jù)分類建模，就可以知道這個人的薪資水平很可能是低收入。聚類是將大量不帶標簽的數(shù)據(jù)根據(jù)距離聚集成不同的簇，每一簇數(shù)據(jù)有共同的特征。如電信行業(yè)可以根據(jù)用戶的月長途電話分鐘數(shù)、上網(wǎng)時長、短信使用數(shù)、地理位置、月消費數(shù)，將所有用戶聚集成有典型特征的簇，聚集出的某簇特征可能是月長途電話分鐘數(shù)長、上網(wǎng)時間長、地理位置變化不大、月消費數(shù)目低，分析可得這類人極有可能是在校大學生，那么電信公司就可以針對這類特定人群制定有針對性的營銷策略?；貧w是根據(jù)特征值、目標變量擬合出特征值與目標變量之間的函數(shù)關系，可用來估計特征值對應的目標變量的可能取值。舉個簡單的例子，某市今年某 100 平米的房子價格是 80 萬，某 150 平米房子價格是 120 萬，那么某 200 平米的房子價格的取值就可能是 200*0.8=160 萬左右。關聯(lián)分析是計算出大量數(shù)據(jù)之間的頻繁項集合。如超市訂單中有大量訂單同時包含啤酒與尿布，這其中的頻繁項就是啤酒和尿布，那么超市就可以針對這個規(guī)律對啤酒和尿布進行組合促銷活動。分類算法主要包括K近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機、AdaBoost等；回歸主要包括線性回歸、嶺回歸、lasso、樹回歸等；聚類主要包括 K-Means 以及它的各種變形算法；關聯(lián)分析主要包括 Apriori、FP-growth 等算法。支持向量機即 support vector machine(簡稱 SVM)，是機器學習領域經(jīng)典的分類算法。2. 關于 SVM 的簡介支持向量是距離分類超平面近的那些點，SVM的思想就是使得支持向量到分類超平面的間隔最大化。出發(fā)點很容易理解，距離分類超平面近的那些點到該超平面的間隔最大化代表了該超平面對兩類數(shù)據(jù)的區(qū)分度強，不容易出現(xiàn)錯分的情況。如圖 1所示，支持向量到超平面1的間隔大于支持向量到超平面2的間隔，因此超平面1優(yōu)于超平面2。圖 1 兩個超平面示例SVM 可以很好得解決二分類問題，對于多分類情況，就需要對模型進行改動。如 one-versus-rest 法，這種方法每次選擇一個類別作為正樣本，剩下其他類別作為負樣本，假設一共有3個類別，這樣相當于訓練出了3個不同的SVM。然后將測試數(shù)據(jù)分別帶入3個SVM模型中，得到的3個結果中的最大值則為最終的分類結果。支持向量到分類超平面的間隔最大化的思路很完美，按這種思路得到的模型理論上是準確度最高的一種模型。但是使用過SVM的朋友都知道，調用SVM算法的測試準確度并不一定都很高。這其中有很多原因，比如數(shù)據(jù)預處理的效果、訓練集的大小、特征值的選擇、參數(shù)設置以及核函數(shù)的選擇等因素。任何模型都是優(yōu)點與缺點并存的。SVM的優(yōu)點是：1. 可以解決線性不可分的情況。如圖 2所示，兩類數(shù)據(jù)點根本無法用超平面分隔開;2. 計算復雜度僅取決于少量支持向量，對于數(shù)據(jù)量大的數(shù)據(jù)集計算復雜度低。SVM 的缺點是：1. 經(jīng)典的 SVM 算法僅支持二分類，對于多分類問題需要改動模型;2. 不支持類別型數(shù)據(jù)，需在預處理階段將類別型數(shù)據(jù)轉換成離散型數(shù)據(jù)。類別型數(shù)據(jù)即男、 女這類由字符串表示某類信息的數(shù)據(jù)，需將這類數(shù)據(jù)轉換成離散型數(shù)據(jù)如 1、2。圖 2 線性不可分問題3. SVM 基本原理SVM原理分為軟間隔最大化、拉格朗日對偶、最優(yōu)化問題求解、核函數(shù)、序列最小優(yōu)化SMO等部分。雖然這些名詞看起來很晦澀，但是深入探索后就會發(fā)現(xiàn)其中的思想并沒有那么復雜。3.1. 軟間隔最大化SVM的核心思路是最大化支持向量到分隔超平面的間隔。后面所有的推導都是以最大化此間隔為核心思想展開。一般的機器學習問題都是先得到模型的目標函數(shù)和約束條件，然后在約束條件下對目標函數(shù)求得最優(yōu)解。因此，我們下面首先需要推導出SVM模型的目標函數(shù)和約束條件。既然要最大化間隔，那么回顧下點x到超平面(w,b)的距離公式：其中超平面的公式為：由此可推出點 x 到超平面(w,b)的幾何間隔為： 其中 xi代表第i條數(shù)據(jù)，yi代表第i條數(shù)據(jù)對應的目標變量的取值，取值有+1 和-1 兩種。所以當?shù)?i條數(shù)據(jù)被正確分類時，y 取值和 w*x+b 取值的正負一致，幾何間隔為正；當被錯誤分類時，y 取值和 w*x+b 取值的正負相反，幾何間隔為負。圖 3 樣本數(shù)關于w*x + b的取值符號定義幾何間隔中最小的為：由此，可以得到間隔最大化問題的目標函數(shù)：并遵循如下約束條件： 做如下變換：則目標函數(shù)轉換為：相應的約束條件變?yōu)椋?做如下變換：可得目標函數(shù)和約束條件變?yōu)椋?由于 w, b 成倍數(shù)變化并不會影響超平面的公式，所以：此時得到最終的間隔最大化的目標函數(shù)和約束條件如下：但是，到這里并沒有真正得結束。考慮到現(xiàn)實生活中的真實數(shù)據(jù)，存在一些特異點即 outliers，這些數(shù)據(jù)點并不滿足上面推導出的約束條件，如圖 4所示，圖中點 A 就是 outlier 特異點。圖 4 Outlier特異點為了解決這種問題，對每個樣本點引進一個松弛變量，使得約束條件變?yōu)椋哼@樣給 outlier 的約束條件加上一個變量，使其可以滿足大于等于 1 的條件。則相應的目標變量變?yōu)椋浩渲?C 為懲罰參數(shù)，它的目的是使得目標變量最小即幾何間隔最大，且使得松弛變量最小化。加入松弛變量的目標函數(shù)就是軟間隔最大化。3.2. 拉格朗日對偶對于凸二次優(yōu)化問題，通過引入拉格朗日乘子，將目標函數(shù)和約束條件整合到拉格朗日函數(shù)中，這樣能方便求解最值問題。那么，對每個不等式約束引入拉格朗日乘子，得到拉格朗日函數(shù)如下：分析可知：則原最優(yōu)化問題轉換成： 由于原最優(yōu)化問題直接求解很困難，利用拉格朗日對偶性，可通過求解原最優(yōu)化問題的對偶問題得到原問題的最優(yōu)解。原最優(yōu)化問題的對偶問題為：3.3. 最優(yōu)化問題求解到此為止，已經(jīng)將目標函數(shù)和約束條件轉換成了極大極小化拉格朗日函數(shù)的問題了。首先求解關于拉格朗日函數(shù)的極小化問題。對三個變量分別求偏導得： 將以上三式帶入拉格朗日函數(shù)中得：那么極大極小化拉格朗日函數(shù)轉換成：為求解方便，將極大轉換成極小得： 3.4. 核函數(shù)對于線性不可分問題，如圖 2所示，這類問題是無法用超平面劃分正負樣本數(shù)據(jù)的。倘若能將超平面換成超曲面，則可以將正負樣本正確分類，如圖 5所示。圖 5 超曲面分離正負樣本我們知道曲面的公式是：映射到新坐標如下：可將超曲面在新坐標下表示成超平面：也就是將在二維空間(x1,x2)下線性不可分的問題轉換成了在五維空間(z1,z2,z3,z4,z5)下線性可分的問題。得映射后新坐標下的內積：有一核函數(shù)如下：可知 何為核函數(shù)？核函數(shù)在低維空間中完成了映射到高維空間后的內積運算。這點非常有用，利用核函數(shù)，無需先將變量一一映射到高維空間再計算內積，而是簡單得在低維空間中利用核函數(shù)完成這一操作。為什么說不用一一映射到高維空間很有用呢？原因就在于首先我們無法針對每種情況提供精確的映射函數(shù)，再者對于需要映射到無窮維的情況顯然無法一一映射完成。那么為什么是映射到高維后的內積運算呢？這是因為在上節(jié)中我們得到了如下目標函數(shù)： 正是因為該目標函數(shù)中包含自變量的內積運算，而映射到高維空間后的內積運算又恰好可以通過核函數(shù)在低維空間中直接求得，故而有了核函數(shù)的由來。較常用的核函數(shù)是高斯核，高斯核可以將低維空間映射到無窮維。運用核函數(shù)后，最優(yōu)化問題的目標函數(shù)和約束條件變?yōu)椋?3.5. 序列最小優(yōu)化 (Sequential minimal optimization)到目前為止，優(yōu)化問題已經(jīng)轉化成了一個包含 N 個 alpha 自變量的目標變量和兩個約束條件。由于目標變量中自變量 alpha 有 N 個，為了便與求解，每次選出一對自變量 alpha，然后求目標函數(shù)關于其中一個 alpha 的偏導，這樣就可以得到這一對 alpha 的新值。給這一對 alpha 賦上新值，然后不斷重復選出下一對 alpha 并執(zhí)行上述操作，直到達到最大迭代數(shù)或沒有任何自變量 alpha 再發(fā)生變化為止，這就是 SMO 的基本思想。說直白些，SMO 就是在約束條件下對目標函數(shù)的優(yōu)化求解算法。為何不能每次只選一個自變量進行優(yōu)化？那是因為只選一個自變量 alpha 的話，會違反第一個約束條件，即所有 alpha 和 y 值乘積的和等于 0。下面是詳細的 SMO 過程。假設選出了兩個自變量分別是 alpha1 和 alpha2，除了這兩個自變量之外的其他自變量保持固定，則目標變量和約束條件轉化為： 將約束條件中的 alpha1 用 alpha2 表示，并代入目標函數(shù)中，則將目標函數(shù)轉化成只包含 alpha2 的目標函數(shù)，讓該目標函數(shù)對 alpha2 的偏導等于 0： 可求得 alpha2 未經(jīng)修剪的值： 之所以說 alpha2 是未經(jīng)修剪的值是因為所有 alpha 都必須滿足大于等于 0 且小于等于 C 的約束條件，用此約束條件將 alpha2 進行修剪，修剪過程如下： 由此得： 分兩種情況討論：情況 1.當 y1 等于 y2 時，有： 情況 2.當 y1 不等于 y2 時，有：修剪后，可得 alpha2 的取值如下：由 alpha2 和 alpha1 的關系，可得：在完成 alpha1 和 alpha2 的一輪更新后，需要同時更新 b 的值，當 alpha1 更新后的值滿足 0alpha1C 時，由 KKT 條件得：由于篇幅有限，在此就不把推導過程一一列舉，可得：同樣的道理，當 alpha2 更新后的值滿足 0alpha1 牛奶，該規(guī)則的置信度是 0.9，意味著在所有買了雞蛋和面包的客戶中，有 90%的客戶還買了牛奶。關聯(lián)規(guī)則可以用來發(fā)現(xiàn)很多有趣的規(guī)律。這其中需要先闡明兩個概念：支持度和置信度。4.2.1. 支持度 Support支持度指某頻繁項集在整個數(shù)據(jù)集中的比例。假設數(shù)據(jù)集有 10 條記錄，包含雞蛋, 面包的有 5 條記錄，那么雞蛋, 面包的支持度就是 5/10 = 0.5。4.2.2. 置信度 Confidence置信度是針對某個關聯(lián)規(guī)則定義的。有關聯(lián)規(guī)則如雞蛋, 面包 - 牛奶，它的置信度計算公式為雞蛋, 面包, 牛奶的支持度/雞蛋, 面包的支持度。假設雞蛋, 面包, 牛奶的支持度為 0.45，雞蛋, 面包的支持度為 0.5，則雞蛋, 面包 - 牛奶的置信度為 0.45 / 0.5 = 0.9。關聯(lián)規(guī)則用于發(fā)現(xiàn) if - then 這樣的規(guī)則，并可以給出這條規(guī)則的可信度（即置信度）。現(xiàn)實場景中可以用來發(fā)現(xiàn)很多規(guī)律，下面舉個例子。在信息安全領域，需要根據(jù)已有流量數(shù)據(jù)制定規(guī)則，來判斷是否觸發(fā)安全報警。如規(guī)則數(shù)據(jù)包大，多個ip地址同時發(fā)送數(shù)據(jù) - 異常，該規(guī)則的置信度為 0.85。這條規(guī)則表示，當流量數(shù)據(jù)包大，并有多個ip地址同時向目標ip發(fā)送數(shù)據(jù)時，則有 85%的概率存在異常，需要觸發(fā)報警。4.3. 頻繁項集挖掘原理頻繁項集挖掘分為構建 FP 樹，和從 FP 樹中挖掘頻繁項集兩步。本節(jié)用如下表所示的數(shù)據(jù)集作為例子展開，該示例數(shù)據(jù)集共四條數(shù)據(jù)。表格 1 示例數(shù)據(jù)集數(shù)據(jù)集a,b,cc,d,b,ad,e,ab,a4.3.1. 構建 FP 樹構建 FP 樹時，首先統(tǒng)計數(shù)據(jù)集中各個元素出現(xiàn)的頻數(shù)，將頻數(shù)小于最小支持度的元素刪除，然后將數(shù)據(jù)集中的各條記錄按出現(xiàn)頻數(shù)排序，剩下的這些元素稱為頻繁項；接著，用更新后的數(shù)據(jù)集中的每條記錄構建 FP 樹，同時更新頭指針表。頭指針表包含所有頻繁項及它們的頻數(shù)，還有每個頻繁項指向下一個相同元素的指針，該指針主要在挖掘 FP 樹時使用。下面用上文提到的數(shù)據(jù)集展開說明，假設最小支持度為 2。首先，統(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 次。接著，將出現(xiàn)次數(shù)小于最小支持度 2 的元素（即 e）在數(shù)據(jù)集中刪除，并將數(shù)據(jù)集按出現(xiàn)次數(shù)由高到低排序，得表格 2。表格 2 示例數(shù)據(jù)集數(shù)據(jù)集a,b,ca,b,c,da,da,b然后，用更新后的數(shù)據(jù)集中的記錄創(chuàng)建 FP 樹，并同時更新頭指針表。創(chuàng)建 FP 樹時，當待添加的記錄與 FP 樹中的路徑相同，則只需更新元素對應的頻數(shù)；如果待添加的記錄與 FP 樹存在不一致，則在不一致的地方分叉，創(chuàng)建新的結點。如圖 6圖 9所示。注意，F(xiàn)P 樹的根節(jié)點是 null。圖 6 向FP樹添加第一條記錄 a,b,c 圖 7向FP樹添加第二條記錄 a,b,c,d 圖 8向FP樹添加第三條記錄 a ,d 圖 9向FP樹添加第四條記錄 a ,b 4.3.2. 挖掘頻繁項集得到 FP 樹后，需要對每一個頻繁項，逐個挖掘頻繁項集。具體過程為：首先獲得頻繁項的前綴路徑，然后將前綴路徑作為新的數(shù)據(jù)集，以此構建前綴路徑的條件 FP 樹。然后對條件 FP 樹中的每個頻繁項，獲得前綴路徑并以此構建新的條件 FP 樹。不斷迭代，直到條件 FP 樹中只包含一個頻繁項為止。下面以元素 c 為例，從上文圖 9創(chuàng)建好的 FP 樹中挖掘頻繁項集。首先，獲得以 c 元素的前綴路徑a:2,b:2，注意此處 a 和 b 的頻數(shù)為 2 是因為 c 的頻數(shù)為 2，所以與 c 共同出現(xiàn)的 a 和 b 的頻數(shù)就都為 2。接著，創(chuàng)建條件 FP 樹，具體的創(chuàng)建過程和上一節(jié)創(chuàng)建 FP 樹的過程一樣，如圖 10所示。圖 10 c元素的前綴路徑構成的條件 FP 樹注意此時頭指針表中包含兩個元素，所以對每個元素，需要獲得前綴路徑，并將前綴路徑創(chuàng)建成條件 FP 樹，直到條件 FP 樹中只包含一個元素時返回。1. 對元素 a，獲得前綴路徑為 ，則頻繁項集返回c,a;2. 對元素 b，獲得前綴路徑a，則將前綴路徑創(chuàng)建成條件 FP 樹，如圖 11所示。注意此時條件 FP 樹中只包含一個元素，故返回頻繁項集c,b,a。由于元素 b 也是頻繁項，所以c,b也是頻繁項集。再加上c本身就是頻繁項集，所以 c 對應的頻繁項集有：c c,a c,b c,b,a。圖 11 b元素的前綴路徑構成的條件FP樹將其他元素 a,b,d 同樣按照上述對 c 的操作，得到表格 3所示頻繁項集。表格 3 元素a,b,c,d對應的頻繁項集元素頻繁項集a a b b b,a c c c,a c,b c,b,a d d d,a 4.4. 關聯(lián)規(guī)則挖掘原理關聯(lián)規(guī)則挖掘首先需要對上文得到的頻繁項集構建所有可能的規(guī)則，然后對每條規(guī)則逐個計算置信度，輸出置信度大于最小置信度的所有規(guī)則。以頻繁項集a,b,c為例，構建所有可能的規(guī)則：b,c - a, a,c - b,a,b - c,c - a,b,b - a,c,a - b,c。對每條規(guī)則計算置信度后，輸出滿足要求的規(guī)則即可。5. NaiveBayes基本原理樸素貝葉斯模型主要用來分類，但是與 SVM 模型不同的的是，樸素貝葉斯模型不需要針對目標變量建立模型，而是借助貝葉斯公式計算樣本屬于各個類別的概率，然后取概率值大的類別作為分類類別。之所以稱之為樸素，是因為樸素貝葉斯模型假設各屬性之間是條件獨立的，該假設極大得簡化了運算，使得樸素貝葉斯模型變得非常簡單。樸素貝葉斯模型主要應用在文本分類方面。這里需要用到向量空間模型，即將文本轉換成詞向量。詞向量的每一項是該詞出現(xiàn)的頻數(shù)。在樸素貝葉斯中會將頻數(shù)進一步轉換成頻率。這樣就完成了文本到數(shù)值上的轉化，方便后期計算條件概率和先驗概率。樸素貝葉斯模型也有它的優(yōu)缺點，優(yōu)點是模型簡單，計算快；缺點是依賴于屬性之間條件獨立這一假設，但是現(xiàn)實場景下很多情況并不滿足這一假設，使得樸素貝葉斯的準確率受到影響。這種情況需要考慮半樸素貝葉斯，即放松屬性之間條件獨立這一假設，一定程度上考慮屬性之間的依賴關系。由于篇幅有限，對半樸素貝葉斯感興趣的話可自行參照文末參考資源學習，本文重點介紹樸素貝葉斯的原理和實現(xiàn)。5.1. 樸素貝葉斯原理樸素貝葉斯模型主要利用貝葉斯公式進行展開。貝葉斯公式如下：公式中 P(C|X)表示 X 屬于類別 C 的概率，P(X|C)表示類別 C 中 X 出現(xiàn)的概率，P(C)表示類別 C 出現(xiàn)的概率。其中 P(C)稱為先驗概率，P(X|C)是條件概率，P(C|X)稱為后驗概率，將后驗概率最大的類作為 X 的類別輸出。假設有 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) 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) -2.84, 所以 log(P(X|C1) *P(C1) ) log(P(X|C0) *P(C0) ), 即 P(C1|X) P(C0|X)，可得測試文本book, campus, study屬于類別 1。6. 決策樹基本原理決策樹算法又分很多種，常用的有ID3，C4.5 和 CART 決策樹。其中ID3和C4.5決策樹更傾向于處理類別型的離散屬性值，對于連續(xù)型屬性值，則需要額外利用連續(xù)屬性離散化技術將其劃分成離散型屬性值。而CART決策樹，即分類回歸樹，直接支持連續(xù)型屬性值。由于篇幅限制CART樹會放在下一篇文章進行介紹，本文主要詳細介紹 ID3 和 C4.5 決策樹。決策樹利用了樹型結構進行決策，是經(jīng)典的 if-then 結構。葉節(jié)點存儲類別，內部節(jié)點代表特征或屬性。注意本文中提到的特征和屬性是同一個概念。為了讓讀者有一個感性的認識，請看圖 12所示決策樹。圖 12 決策樹示例圖1所示決策樹用來將數(shù)據(jù)分為兩類，是蘋果和非蘋果。如圖中所示，圓的和紅的，就是蘋果。不圓的不是蘋果。圓的但不紅的不是蘋果。本文將著重介紹ID3和C4.5兩種決策樹。決策樹需要選擇最優(yōu)特征劃分數(shù)據(jù)集。這兩種決策樹的不同之處是劃分數(shù)據(jù)集的最優(yōu)特征選擇方法不同。用最優(yōu)特征劃分數(shù)據(jù)會使得數(shù)據(jù)集趨于更純，即數(shù)據(jù)集的類別數(shù)更單一，這樣的數(shù)據(jù)會更有序。衡量數(shù)據(jù)的混亂程度就必須提到信息和信息熵的概念。待分類的事物可能劃分在多個類別中，則符號 Xi 的信息是:可知P(Xi) 越大，則 I(Xi) 越小，即Xi的概率越大，則Xi包含的信息越少。我們都知道物理中的熵用來衡量混亂程度，熵越大說明越混亂，熵越小說明越單一。同樣，信息熵用來衡量信息中的混亂程度。用所有類別所有可能值包含的信息期望值表示信息熵，計算方法如下：ID3 決策樹利用了信息增益來選擇最優(yōu)特征，用這種方法選擇的特征是使得信息熵增益最大的特征。而 C4.5決策樹利用了信息增益比來選擇最優(yōu)特征。用這種方法選擇的特征是使得信息增益比最大的特征。為什么要提出信息增益比呢？這是因為只考慮信息增益來劃分數(shù)據(jù)集是有缺陷的。這種缺陷體現(xiàn)在信息增益對選擇屬性取值多的特征更有利。因為按屬性取值多的特征劃分數(shù)據(jù)集后，劃分后的各個子數(shù)據(jù)集的類別更單一，即更趨于有序，這就使得劃分后的信息熵更小，那么信息增益就會更大。信息增益比可以很好的解決這個問題。信息增益比通過引入類似懲罰因子的概念，對屬性取值多的特征會有一定懲罰。6.1. 決策樹原理6.1.1. 選擇最優(yōu)特征決策樹通過不斷選擇最優(yōu)特征劃分數(shù)據(jù)集，對劃分后的子數(shù)據(jù)集不斷迭代得選擇最優(yōu)特征劃分，直到所有的數(shù)據(jù)集屬于同一個類別，或者沒有特征可以選擇為止。選擇最優(yōu)特征的算法有很多種，ID3 決策樹用信息增益選擇最優(yōu)特征，C4.5 決策樹用信息增益比選擇最優(yōu)特征。6.1.2. 信息增益-用于ID3決策樹信息增益，顧名思義就是原數(shù)據(jù)集的信息熵比劃分后數(shù)據(jù)集的信息熵大的程度。信息增益越大，說明劃分后的數(shù)據(jù)集信息熵更小，即該數(shù)據(jù)集類別更趨于一致。特征 A 對數(shù)據(jù)集 D 的信息增益 g(D,A)為 D 的信息熵與按特征 A 進行劃分后 D 的信息熵之差，即其中， 6.1.3. 信息增益比 用于 C4.5 決策樹信息增益比為了避免傾向于選擇屬性值多的特征作為最優(yōu)特征這個問題，在信息增益的基礎上引入了類似懲罰因子的概念。特征 A 對數(shù)據(jù)集 D 的信息增益比gg(D,A)為信息增益 g(D,A) 與數(shù)據(jù)集 D 關于特征 A 的取值的熵 HA(D) 的比值，即其中,其中，n 是特征 A 取值的個數(shù)。HA(D) 就類似懲罰因子，對于屬性值多的特征，雖然信息增益 g(D,A) 會比較大，但是數(shù)據(jù)集 D 關于特征 A 的取值的熵 HA(D) 會比較大，因而兩者的比值信息增益比 gg(D,A) 會比較小。除了可以使用信息增益和信息增益比來選擇最優(yōu)劃分特征之外，基尼指數(shù)也可以用來實現(xiàn)這個目的。基尼指數(shù)主要用于 CART 樹(即分類回歸樹)的分類樹中的特征選擇。關于基尼指數(shù)的詳細內容會在下一篇文章介紹。6.2. 用 ID3 決策樹進行分類本節(jié)主要介紹用 ID3 決策樹進行分類。為了便于理解，用表1所示數(shù)據(jù)集進行詳細說明。利用 C4.5 決策樹進行分類的過程會在下節(jié)介紹。表格 8 示例數(shù)據(jù)集圓的紅的分類1111000100001006.2.1. ID3決策樹選擇最優(yōu)特征表格 8數(shù)據(jù)集的信息熵為:-1/5 * log(1/5) - 4/5 * log(4/5) = 0.2171. 按特征圓的劃分數(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)= 0.166則信息增益為：0.217 0.166 = 0.0512. 按特征紅的劃分數(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)= 0.120則信息增益為：0.217 0.120 =0.097綜上所述，由于按特征紅的比按特征圓的劃分的信息增益大，所以特征紅的為最優(yōu)劃分特征。6.2.2. 按最優(yōu)特征劃分數(shù)據(jù)集按特征紅的劃分數(shù)據(jù)集后，有兩種情況，第一種為如果是紅的:0,則分類:0; 第二種為如果是紅的:1, 則得到如下數(shù)據(jù)子集 圓的:1,分類：1; 圓的:0, 分類:0接下來需要對數(shù)據(jù)子集圓的:1,分類：1; 圓的:0, 分類:0繼續(xù)劃分。由于剩下一個特征，故按特征圓的劃分數(shù)據(jù)子集。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。返回的決策樹用字典表示為：紅的: 0: 類別0, 1: 圓的: 0: 類別0, 1: 類別16.3. 用 C4.5 決策樹進行分類為了讓讀者對 ID3 和 C4.5 決策樹的不同之處有更好的理解，本節(jié)介紹用 C4.5 決策樹進行分類。為了便于理解，仍然使用表格 8所示數(shù)據(jù)集進行說明。6.3.1. C4.5 決策樹選擇最優(yōu)特征表格 8數(shù)據(jù)集的信息熵為:-1/5 * log(1/5) - 4/5 * log(4/5) = 0.2171. 按特征圓的劃分數(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)= 0.166則信息增益為：0.217 0.166 = 0.051數(shù)據(jù)集關于特征圓的的取值的熵為:-3/5 * log(3/5) 2/5 * log(2/5) = 0.29則信息增益比為0.051 / 0.29 = 0.1762. 按特征紅的劃分數(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)= 0.120則信息增益為：0.217 0.120 =0.097數(shù)據(jù)集關于特征紅的的取值的熵為：-2/5 * log(2/5) 3/5 * log(3/5) = 0.29則信息增益比為 0.097 / 0.29 = 0.334綜上所述，由于按特征紅的比按特征圓的劃分的信息增益比大，所以特征紅的為最優(yōu)劃分特征。6.3.2. 按最優(yōu)特征劃分數(shù)據(jù)集C4.5 決策樹按最優(yōu)特征劃分數(shù)據(jù)集方法與上節(jié) ID3 決策樹方法相同。7. 分類回歸樹基本原理在上節(jié)中，主要介紹了 ID3 和 C4.5 決策樹。它們利用信息增益和信息增益比劃分數(shù)據(jù)集。但是這兩種決策樹是有缺陷的，即按某特征劃分后，該特征將不會在后面的劃分中出現(xiàn)。這就導致了劃分過于迅速，從而影響分類結果。在這篇文章中將要介紹的CART（Classification And Regression Tree）樹，即分類回歸樹利用二分策略，有效地避免了劃分過于迅速這一問題。而且二分策略可以直接處理連續(xù)型屬性值。CART樹（分類回歸樹）分為分類樹和回歸樹。顧名思義，分類樹用于處理分類問題；回歸樹用來處理回歸問題。我們知道分類和回歸是機器學習領域兩個重要的方向。分類問題輸出特征向量對應的分類結果，回歸問題輸出特征向量對應的預測值。分類樹和 ID3、C4.5決策樹相似，都用來處理分類問題。不同之處是劃分方法。分類樹利用基尼指數(shù)進行二分。如圖 13所示就是一個分類樹。圖 13 分類樹示例回歸樹用來處理回歸問題?；貧w將已知數(shù)據(jù)進行擬合，對于目標變量未知的數(shù)據(jù)可以預測目標變量的值。如圖 14所示就是一個回歸樹，其中 s 是切分點，x 是特征，y 是目標變量?？梢钥闯鰣D 14利用切分點s將特征空間進行劃分，y是在劃分單元上的輸出值?；貧w樹的關鍵是如何選擇切分點、如何利用切分點劃分數(shù)據(jù)集、如何預測y的取值。圖 14 回歸樹示例7.1. CART 樹原理7.1.1. 分類樹二分分類樹利用二分劃分數(shù)據(jù)。將特征值等于切分點值的數(shù)據(jù)劃分為左子樹，將特征值不等于切分點值的數(shù)據(jù)劃分為右子樹?；嶂笖?shù)：同信息增益、信息增益比作用類似，不過基尼指數(shù)相對更快假設有 N 個類，樣本屬于第 n 類的概率為Pn，則基尼指數(shù)為：若數(shù)據(jù)集按特征A取值是否等于切分點值劃分為D1和D2兩部分，則在特征A下，集合D的基尼指數(shù)為：7.1.2. 回歸樹二分回歸樹也利用二分劃分數(shù)據(jù)。與分類樹不同的是，回歸樹將特征值大于切分點值的數(shù)據(jù)劃分為左子樹，將特征值小于等于切分點值的數(shù)據(jù)劃分為右子樹。平方誤差不同于分類樹，回歸樹用平方誤差選擇切分點。若數(shù)據(jù)集按特征取值是否大于切分點值劃分為兩部分，則在特征A下，集合D的平方誤差為：7.2. 用 CART 樹進行分類和回歸本節(jié)主要用示例數(shù)據(jù)詳細說明如何用 CART 樹進行分類和回歸。7.2.1. 分類樹表格 9 示例數(shù)據(jù)集圓的紅的分類111100010000100選擇最優(yōu)特征按特征圓的 = 1 劃分數(shù)據(jù)集，則Gini為：3/5 * Gini(D1) + 2/5 * Gini(D0)= 3/5 * 1/3 * 2/3 + 2/3 * 1/3 + 2/5 * 0= 0.266按特征紅的 = 1 劃分數(shù)據(jù)集，則Gini為：2/5 * Gini(D1) + 3/5 * Gini(D0)= 2/5 * 1/2 * 1/2 + 1/2 * 1/2 + 3/5 * 0= 0.2綜上所述，由于按特征紅的比特征圓的劃分的基尼指數(shù)小，所以特征紅的 = 1 為切分點。按最優(yōu)特征劃分數(shù)據(jù)集按特征紅的劃分數(shù)據(jù)集后，有兩種情況，第一種為如果是紅的:0,則分類:0; 第二種為如果是紅的:1, 則有如下數(shù)據(jù)子集 圓的:1,分類：1; 圓的:0, 分類:0接下來需要對數(shù)據(jù)子集圓的:1,分類：1; 圓的:0, 分類:0繼續(xù)劃分。由于剩下一個特征，故按特征圓的劃分數(shù)據(jù)集。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。返回的決策樹為：紅的: 0: 類別 0, 1: 圓的: 0: 類別 0, 1: 類別 17.2.2. 回歸樹表格 10 示例數(shù)據(jù)集面積/平米價格/萬2040.12140.33570.43670.2選擇最優(yōu)特征1. 按特征面積 = 20 劃分數(shù)據(jù)集，y1 均值為 40.1，y2 均值為(40.3 + 70.4 + 70.2) / 3 = 60.3,則平方誤差為：0 + （40.3 60.3）2+ （70.4 60.3）2+（70.2 60.3）2 = 600.022. 按特征面積 = 21 劃分數(shù)據(jù)集，則平方誤差為：y1 均值為(40.1 + 40.3)/ 2 = 40.2，y2 均值為(70.4 + 70.2) / 2 = 70.3,則平方誤差為：（40.1 40.2）2+（40.3 40.2）2+ （70.4 70.3）2+（70.2 70.3）2 = 0.043. 3.按特征面積 = 35 劃分數(shù)據(jù)集，則平方誤差為：y1 均值為(40.1 + 40.3 + 70.4) / 3 = 50.27，y2 均值為 70.2,則平方誤差為：（40.1 50.27）2+ （40.3 50.27）2+（70.4 50.27）2+ 0 = 608.05綜上所述，由于按特征面積 = 21 比特征面積 = 20、面積 = 35 劃分的平方誤差小，所以特征面積 = 21 為切分點。按最優(yōu)特征劃分數(shù)據(jù)集以特征面積 = 21 為切分點，將數(shù)據(jù)切分為面積 = 20,價格 = 40.1; 面積 = 21, 價格 = 40.3， 面積 = 35,價格 = 70.4; 面積 = 36, 價格 = 70.2兩個子集。其中子集面積 = 20,價格 = 40.1; 面積 = 21, 價格 = 40.3的目標變量非常接近，故不繼續(xù)劃分，得葉節(jié)點值(40.1 + 40.3) / 2 = 40.2； 同理得子集面積 = 35,價格 = 70.4; 面積 = 36, 價格 = 70.2的葉節(jié)點值為 (70.4 + 70.2) / 2 = 70.3。8. Adaboost基本原理前面內容涵蓋了分類、回歸、關聯(lián)分析等諸多模型，其中分類模型被介紹得最多。原因是分類在機器學習方向是應用最廣的方向之一。本文將要介紹的是分類模型中的另一種模型，AdaBoost（adaptive boosting），即自適應提升算法。Boosting 是一類算法的總稱，這類算法的特點是通過訓練若干弱分類器，然后將弱分類器組合成強分類器進行分類。為什么要這樣做呢？因為弱分類器訓練起來很容易，將弱分類器集成起來，往往可以得到很好的效果。俗話說，三個臭皮匠，頂個諸葛亮，就是這個道理。這類 boosting 算法的特點是各個弱分類器之間是串行訓練的，當前弱分類器的訓練依賴于上一輪弱分類器的訓練結果。各個弱分類器的權重是不同的，效果好的弱分類器的權重大，效果差的弱分類器的權重小。值得注意的是，AdaBoost 不止適用于分類模型，也可以用來訓練回歸模型。這需要將弱分類器替換成回歸模型，并改動損失函數(shù)。本文將重點介紹用 AdaBoost 進行分類的算法原理。AdaBoost 算法有其獨特的優(yōu)點，那就是可以將不同的分類算法組合起來，形成強分類器。這就可以充分利用不同分類算法的優(yōu)勢進行建模。也可以將同一算法的不同設置進行組合，這樣訓練的模型比單一設置模型的訓練精度高。當然，就如每一個算法都有自己的優(yōu)缺點一樣，AdaBoos