機(jī)器學(xué)習(xí)簡(jiǎn)明原理

1、機(jī)器學(xué)習(xí)簡(jiǎn)明原理說(shuō)明：本文整理自IBM大數(shù)據(jù)學(xué)習(xí)文檔，原文作者：韓笑琳1. 關(guān)于機(jī)器學(xué)習(xí)的簡(jiǎn)介機(jī)器學(xué)習(xí)是從大量數(shù)據(jù)中學(xué)習(xí)出特定規(guī)律的算法。其中提到的規(guī)律有很多種， 比如分類(lèi)、聚類(lèi)、回歸、關(guān)聯(lián)分析等。分類(lèi)就是給定大量帶標(biāo)簽的數(shù)據(jù)，計(jì)算出未知標(biāo)簽樣本的標(biāo)簽取值。如年齡40歲以上、工科、研究生以上學(xué)歷，這類(lèi)人薪資水平是高收入；年齡20-30歲、文科、大專(zhuān)學(xué)歷，這類(lèi)人的薪資水平是低收入；現(xiàn)有一位23歲大專(zhuān)文科人士，求該人的薪資水平是哪類(lèi)？根據(jù)分類(lèi)建模，就可以知道這個(gè)人的薪資水平很可能是低收入。聚類(lèi)是將大量不帶標(biāo)簽的數(shù)據(jù)根據(jù)距離聚集成不同的簇，每一簇?cái)?shù)據(jù)有共同的特征。如電信行業(yè)可以根據(jù)用戶(hù)的月長(zhǎng)途電話(huà)分

2、鐘數(shù)、上網(wǎng)時(shí)長(zhǎng)、短信使用數(shù)、地理位置、月消費(fèi) 數(shù)，將所有用戶(hù)聚集成有典型特征的簇，聚集出的某簇特征可能是月長(zhǎng)途電話(huà)分鐘數(shù)長(zhǎng)、上網(wǎng)時(shí)間長(zhǎng)、地理位置變化不大、 月消費(fèi)數(shù)目低，分析可得這類(lèi)人極有可能是在校大學(xué)生，那 么電信公司就可以針對(duì)這類(lèi)特定人群制定有針對(duì)性的營(yíng)銷(xiāo)策略?；貧w是根據(jù)特征值、目標(biāo)變量擬合出特征值與目標(biāo)變量之間的函數(shù)關(guān)系，可用來(lái)估計(jì)特征值對(duì)應(yīng)的目標(biāo)變量的可能取值。舉個(gè)簡(jiǎn)單的例子，某市今年某100平米的房子價(jià)格是80萬(wàn)，某150平米房子價(jià)格是 120萬(wàn)，那么某200平米的房子價(jià)格的取值就可能是 200*0.8=160萬(wàn)左右。關(guān)聯(lián)分析是計(jì)算出大量數(shù)據(jù)之間的頻繁項(xiàng)集合。如超市訂單中有大量訂單同

3、時(shí)包含啤酒與尿布，這其中的頻繁項(xiàng)就是啤酒和尿布，那么超市就可以針對(duì)這個(gè)規(guī)律對(duì)啤酒和尿布進(jìn) 行組合促銷(xiāo)活動(dòng)。AdaBoost分類(lèi)算法主要包括 K近鄰、決策樹(shù)、樸素貝葉斯、邏輯回歸、支持向量機(jī)、等；回歸主要包括線(xiàn)性回歸、嶺回歸、lasso、樹(shù)回歸等；聚類(lèi)主要包括K-Means 以及它的各種變形算法；關(guān)聯(lián)分析主要包括Apriori、FP-growth等算法。支持向量機(jī)即 support vector machine（簡(jiǎn)稱(chēng)SVM），是機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)典的分類(lèi)算法。2. 關(guān)于SVM的簡(jiǎn)介支持向量是距離分類(lèi)超平面近的那些點(diǎn)，SVM的思想就是使得支持向量到分類(lèi)超平面的間隔最大化。出發(fā)點(diǎn)很容易理解，距離分類(lèi)超平

4、面近的那些點(diǎn)到該超平面的間隔最大化代表了該超平面對(duì)兩類(lèi)數(shù)據(jù)的區(qū)分度強(qiáng)，不容易出現(xiàn)錯(cuò)分的情況。如圖1所示，支持向量到超平面1的間隔大于支持向量到超平面2的間隔，因此超平面 1優(yōu)于超平面2。SVM 可以很好得解決二分類(lèi)問(wèn)題，對(duì)于多分類(lèi)情況，就需要對(duì)模型進(jìn)行改動(dòng)。如 one-versus-rest法，這種方法每次選擇一個(gè)類(lèi)別作為正樣本，剩下其他類(lèi)別作為負(fù)樣本，假設(shè)一共有3個(gè)類(lèi)別，這樣相當(dāng)于訓(xùn)練出了3個(gè)不同的SVM。然后將測(cè)試數(shù)據(jù)分別帶入3個(gè)SVM模型中，得到的3個(gè)結(jié)果中的最大值則為最終的分類(lèi)結(jié)果。支持向量到分類(lèi)超平面的間隔最大化的思路很完美，按這種思路得到的模型理論上是準(zhǔn)確度最高的一種模型。但是使用

5、過(guò)SVM的朋友都知道，調(diào)用 SVM算法的測(cè)試準(zhǔn)確度并不一定都很高。這其中有很多原因，比如數(shù)據(jù)預(yù)處理的效果、訓(xùn)練集的大小、特征值的選擇、 參數(shù)設(shè)置以及核函數(shù)的選擇等因素。任何模型都是優(yōu)點(diǎn)與缺點(diǎn)并存的。SVM的優(yōu)點(diǎn)是：1. 可以解決線(xiàn)性不可分的情況。如圖2所示，兩類(lèi)數(shù)據(jù)點(diǎn)根本無(wú)法用超平面分隔開(kāi)2. 計(jì)算復(fù)雜度僅取決于少量支持向量，對(duì)于數(shù)據(jù)量大的數(shù)據(jù)集計(jì)算復(fù)雜度低。SVM 的缺點(diǎn)是：1. 經(jīng)典的SVM算法僅支持二分類(lèi)，對(duì)于多分類(lèi)問(wèn)題需要改動(dòng)模型；2. 不支持類(lèi)別型數(shù)據(jù)，需在預(yù)處理階段將類(lèi)別型數(shù)據(jù)轉(zhuǎn)換成離散型數(shù)據(jù)。類(lèi)別型數(shù)據(jù)即男、女這類(lèi)由字符串表示某類(lèi)信息的數(shù)據(jù)，需將這類(lèi)數(shù)據(jù)轉(zhuǎn)換成離散型數(shù)據(jù)女口 1、

6、2。 * X X八 X、八* + x X- 只 Z x. X X 圖2線(xiàn)性不可分問(wèn)題3. SVM基本原理SVM原理分為軟間隔最大化、拉格朗日對(duì)偶、最優(yōu)化問(wèn)題求解、核函數(shù)、序列最小優(yōu)化SMO等部分。雖然這些名詞看起來(lái)很晦澀， 但是深入探索后就會(huì)發(fā)現(xiàn)其中的思想并沒(méi)有 那么復(fù)雜。3.1. 軟間隔最大化SVM的核心思路是最大化支持向量到分隔超平面的間隔。后面所有的推導(dǎo)都是以最大化此間隔為核心思想展開(kāi)。般的機(jī)器學(xué)習(xí)問(wèn)題都是先得到模型的目標(biāo)函數(shù)和約束條件,后在約束條件下對(duì)目標(biāo)函數(shù)求得最優(yōu)解。因此，我們下面首先需要推導(dǎo)出SVM模型的目標(biāo)函數(shù)和約束條件。既然要最大化間隔，那么回顧下點(diǎn)x到超平面(w,b)的距離

7、公式：|w x + 2|d = Ikll其中超平面的公式為:x-l- b = 0由此可推出點(diǎn) x到超平面(w,b)的幾何間隔為:詡起十b其中xi代表第i條數(shù)據(jù)，yi代表第i條數(shù)據(jù)對(duì)應(yīng)的目標(biāo)變量的取值，取值有+1和-1兩種。所以當(dāng)?shù)趇條數(shù)據(jù)被正確分類(lèi)時(shí)，y取值和w*x+b取值的正負(fù)一致，幾何間隔為正； 當(dāng)被錯(cuò)誤分類(lèi)時(shí)，y取值和w*x+b取值的正負(fù)相反，幾何間隔為負(fù)。圖3樣本數(shù)關(guān)于 w*x + b的取值符號(hào)定義幾何間隔中最小的為:y = min苦由此，可以得到間隔最大化問(wèn)題的目標(biāo)函數(shù):HiSX y并遵循如下約束條件：/W 工：+做如下變換：禹Y則目標(biāo)函數(shù)轉(zhuǎn)換為：相應(yīng)的約束條件變?yōu)椋喝閠 y 0*1

8、 +町A事做如下變換：/ T可得目標(biāo)函數(shù)和約束條件變?yōu)椋簃axMg.t.y坷+撲）工1由于w, b成倍數(shù)變化并不會(huì)影響超平面的公式，所以:訶二 w ” br = b此時(shí)得到最終的間隔最大化的目標(biāo)函數(shù)和約束條件如下:maxiwT. Lyt （w珀 + b） 1但是，到這里并沒(méi)有真正得結(jié)束。考慮到現(xiàn)實(shí)生活中的真實(shí)數(shù)據(jù)，存在一些特異點(diǎn)即outliers ，這些數(shù)據(jù)點(diǎn)并不滿(mǎn)足上面推導(dǎo)出的約束條件，如圖4所示，圖中點(diǎn) A就是outlier 特異點(diǎn)。為了解決這種問(wèn)題，對(duì)每個(gè)樣本點(diǎn)引進(jìn)一個(gè)松弛變量，使得約束條件變?yōu)椋簓（w 工（+ b） + 片 1王0這樣給outlier的約束條件加上一個(gè)變量，使其可以滿(mǎn)足

9、大于等于1的條件。則相應(yīng)的目標(biāo)變量變?yōu)椋簃in扌|w（F +磴工嶺其中C為懲罰參數(shù)，它的目的是使得目標(biāo)變量最小即幾何間隔最大，且使得松弛變量最小化。加入松弛變量的目標(biāo)函數(shù)就是軟間隔最大化。32拉格朗日對(duì)偶對(duì)于凸二次優(yōu)化問(wèn)題， 通過(guò)引入拉格朗日乘子， 將目標(biāo)函數(shù)和約束條件整合到拉格朗日函數(shù)中，這樣能方便求解最值問(wèn)題。那么，對(duì)每個(gè)不等式約束引入拉格朗日乘子，得到拉格朗日函數(shù)如下：Lfw.b,&tx.|4)=十|加|卩 + 心 -嘰+ 肘一1+百)一m廠竊分析可知：= j|w|2 +- Ut )ft則原最優(yōu)化問(wèn)題轉(zhuǎn)換成：旳)上芒禪耳R)由于原最優(yōu)化問(wèn)題直接求解很困難，利用拉格朗日對(duì)偶性，可通過(guò)求解原

10、最優(yōu)化問(wèn)題的對(duì)偶問(wèn)題得到原問(wèn)題的最優(yōu)解。原最優(yōu)化問(wèn)題的對(duì)偶問(wèn)題為：maxat - L （誡,虬 z cl3.3.最優(yōu)化問(wèn)題求解到此為止，已經(jīng)將目標(biāo)函數(shù)和約束條件轉(zhuǎn)換成了極大極小化拉格朗日函數(shù)的問(wèn)題了。首先求解關(guān)于拉格朗日函數(shù)的極小化問(wèn)題。對(duì)三個(gè)變量分別求偏導(dǎo)得：Vw Lfws, d ）二 w 工 - 0 Vb L（w,b,斗叫p）= 吟y嚴(yán)0 Ve LCw.b, w, cc 町=匚- pt = 0將以上三式帶入拉格朗日函數(shù)中得:血如LOb a. u）=齢吁兒片1巧）+齢那么極大極小化拉格朗日函數(shù)轉(zhuǎn)換成:訊妙的莊L伽讓闔卩）二悶 - |SSat卄方仗對(duì)斗ZX為求解方便，將極大轉(zhuǎn)換成極小得:max

11、amirbr L（wRla,Ef a.pgEE 毎礙處乃（處叼）一龜34核函數(shù)對(duì)于線(xiàn)性不可分問(wèn)題，如圖2所示，這類(lèi)問(wèn)題是無(wú)法用超平面劃分正負(fù)樣本數(shù)據(jù)的。倘若能將超平面換成超曲面，則可以將正負(fù)樣本正確分類(lèi)，如圖5所示。圖5超曲面分離正負(fù)樣本我們知道曲面的公式是：kjrJ + kjxji + Jts Xi 4- ic4a + ks也叫 += 0映射到新坐標(biāo)如下：可將超曲面在新坐標(biāo)下表示成超平面：XZ +氐N +叫N +虹N+嶋Z +耘二o也就是將在二維空間（x1,x2）下線(xiàn)性不可分的問(wèn)題轉(zhuǎn)換成了在五維空間（z1,z2,z3,z4,z5）下線(xiàn)性可分的問(wèn)題。得映射后新坐標(biāo)下的內(nèi)積：GppW（q）衍S/

12、+ 2阿餌+ 2利q尹2內(nèi)松心衍有一核函數(shù)如下：Kp.q） = （p qj + l）!?! I-Mj + 1）3Kpq）二十pjq,十2卩燦十2pm尹2pj旳q】如十九可知虬pq）= Gp（p）甲（吩）41何為核函數(shù)？核函數(shù)在低維空間中完成了映射到高維空間后的內(nèi)積運(yùn)算。這點(diǎn)非常有用,利用核函數(shù)，無(wú)需先將變量一一映射到高維空間再計(jì)算內(nèi)積，而是簡(jiǎn)單得在低維空間中利用核函數(shù)完成這一操作。為什么說(shuō)不用一一映射到高維空間很有用呢？原因就在于首先我們無(wú) 法針對(duì)每種情況提供精確的映射函數(shù)，再者對(duì)于需要映射到無(wú)窮維的情況顯然無(wú)法映射完成。那么為什么是映射到高維后的內(nèi)積運(yùn)算呢？這是因?yàn)樵谏瞎?jié)中我們得到了如下目標(biāo)

13、函數(shù)：maXaTTiin L（w,baix mina工眄 y創(chuàng)（兀廠巧）一 眄正是因?yàn)樵撃繕?biāo)函數(shù)中包含自變量的內(nèi)積運(yùn)算，而映射到高維空間后的內(nèi)積運(yùn)算又恰好可以通過(guò)核函數(shù)在低維空間中直接求得，故而有了核函數(shù)的由來(lái)。 較常用的核函數(shù)是高斯核，高斯核可以將低維空間映射到無(wú)窮維。運(yùn)用核函數(shù)后，最優(yōu)化問(wèn)題的目標(biāo)函數(shù)和約束條件變?yōu)?0 Or ?3.5.序列最小優(yōu)化 (Sequential minimal optimization)到目前為止，優(yōu)化問(wèn)題已經(jīng)轉(zhuǎn)化成了一個(gè)包含N個(gè)alpha自變量的目標(biāo)變量和兩個(gè)約束條件。由于目標(biāo)變量中自變量alpha 有N個(gè)，為了便與求解，每次選出一對(duì)自變量alpha，然后求目

14、標(biāo)函數(shù)關(guān)于其中一個(gè)alpha 的偏導(dǎo)，這樣就可以得到這一對(duì)alpha 的新值。給這一對(duì) alpha 賦上新值，然后不斷重復(fù)選出下一對(duì)alpha并執(zhí)行上述操作，直到達(dá)到最大迭代數(shù)或沒(méi)有任何自變量alpha 再發(fā)生變化為止，這就是 SMO的基本思想。說(shuō)直白些，SMO就是在約束條件下對(duì)目標(biāo)函數(shù)的優(yōu)化求解算法。為何不能每次只選一個(gè)自變量進(jìn)行優(yōu)化？那是因?yàn)橹贿x一個(gè)自變量alpha的話(huà)，會(huì)違反第一個(gè)約束條件，即所有 alpha和y值乘積的和等于 0。下面是詳細(xì)的 SMO 過(guò)程。假設(shè)選出了兩個(gè)自變量分別是alpha1 和alpha2，除了這兩個(gè)自變量之外的其他自變量保持固定，則目標(biāo)變量和約束條件轉(zhuǎn)化為：s.

15、L 住+二氓=6a： C將約束條件中的alpha1 用alpha2表示，并代入目標(biāo)函數(shù)中，則將目標(biāo)函數(shù)轉(zhuǎn)化成只包含alpha2的目標(biāo)函數(shù)，讓該目標(biāo)函數(shù)對(duì)alpha2 的偏導(dǎo)等于 0 :可求得alpha2 未經(jīng)修剪的值:V2 (E, Fn)住 7i eiA-ftt n c 一 北 口1-圧 + -、-亠 _E=/r11+/f-2ffu7=*/0且小之所以說(shuō)alpha2是未經(jīng)修剪的值是因?yàn)樗衋lpha都必須滿(mǎn)足大于等于于等于C的約束條件，用此約束條件將alpha2進(jìn)行修剪，修剪過(guò)程如下:由此得:分兩種情況討論：情況1.當(dāng)y1等于y2時(shí)，有:odd口嚴(yán)0 a2neii C1 -血曲(0衛(wèi) Jd也

16、+ a.2 odd - C) H=點(diǎn)加+叫。如情況2.當(dāng)y1不等于y2時(shí)，有:口血-偽皿出 V C -+血H = minCE 兩&血十衍）修剪后，可得 alpha2 的取值如下：Lt J由 alpha2 和 alphal的關(guān)系，可得:嚴(yán)=応嚴(yán) 十對(duì)升S/*111 一如n嚨）在完成alphal 和alpha2的一輪更新后，需要同時(shí)更新b的值，當(dāng)alphal 更新后的值滿(mǎn)足 0alpha1C 時(shí)，由KKT條件得：叩血+ fr = Yi由于篇幅有限，在此就不把推導(dǎo)過(guò)程一一列舉，可得：g = 一足一山血二仗呻一口一光嚴(yán)宙一。網(wǎng)）+b頂同樣的道理，當(dāng) alpha2更新后的值滿(mǎn)足 0alpha1C時(shí)可得：

17、耳=一昂一旳心2嚴(yán)駛一銳J磯）-yK埠（圧嚴(yán)R -心。加）+肝2若更新后的alphal 和alpha2同時(shí)滿(mǎn)足大于 0且小于 C的條件，那么b就等于bl等于b2 ;否則，b取bl和b2的中點(diǎn)。那么問(wèn)題來(lái)了，如何選擇alphal 和alpha2 呢？a = J JGt |0 ： 牛奶,該規(guī)則的置信度是0.9，意味著在所有買(mǎi)了雞蛋和面包的客戶(hù)中，有 90%的客戶(hù)還買(mǎi)了牛奶。關(guān)聯(lián)規(guī)則可以用來(lái)發(fā)現(xiàn)很多有趣的規(guī)律。這其中 需要先闡明兩個(gè)概念：支持度和置信度。4.2.1. 支持度 Support支持度指某頻繁項(xiàng)集在整個(gè)數(shù)據(jù)集中的比例。假設(shè)數(shù)據(jù)集有10條記錄，包含雞蛋,面包的有5條記錄，那么雞蛋,面包的支持

18、度就是 5/10 = 0.5。422.置信度 Confidence置信度是針對(duì)某個(gè)關(guān)聯(lián)規(guī)則定義的。有關(guān)聯(lián)規(guī)則如雞蛋,面包 - 牛奶,它的置信度計(jì)算公式為雞蛋,面包,牛奶的支持度/雞蛋,面包的支持度。假設(shè)雞蛋,面包, 牛奶的支持度為 0.45，雞蛋,面包的支持度為0.5，則雞蛋,面包 - 牛奶的置信 度為 0.45 / 0.5 = 0.9。關(guān)聯(lián)規(guī)則用于發(fā)現(xiàn)if - then這樣的規(guī)則，并可以給出這條規(guī)則的可信度（即置信度）?，F(xiàn)實(shí)場(chǎng)景中可以用來(lái)發(fā)現(xiàn)很多規(guī)律，下面舉個(gè)例子。在信息安全領(lǐng)域，需要根據(jù)已有流量數(shù)據(jù)制定規(guī)則，來(lái)判斷是否觸發(fā)安全報(bào)警。如規(guī)則數(shù)據(jù)包大，多個(gè)ip地址同時(shí)發(fā)送數(shù)據(jù)-異常，該規(guī)則的置

19、信度為0.85。這條規(guī)則表示，當(dāng)流量數(shù)據(jù)包大，并有多個(gè)ip地址同時(shí)向目標(biāo)ip發(fā)送數(shù)據(jù)時(shí)，則有85%的概率存在異常，需要觸發(fā)報(bào)警。4.3. 頻繁項(xiàng)集挖掘原理頻繁項(xiàng)集挖掘分為構(gòu)建FP樹(shù)，和從FP樹(shù)中挖掘頻繁項(xiàng)集兩步。本節(jié)用如下表所示的數(shù)據(jù)集作為例子展開(kāi)，該示例數(shù)據(jù)集共四條數(shù)據(jù)。表格1示例數(shù)據(jù)集4.3.1. 構(gòu)建FP樹(shù)構(gòu)建FP樹(shù)時(shí)，首先統(tǒng)計(jì)數(shù)據(jù)集中各個(gè)元素出現(xiàn)的頻數(shù)，將頻數(shù)小于最小支持度的元素刪除，然后將數(shù)據(jù)集中的各條記錄按出現(xiàn)頻數(shù)排序，剩下的這些元素稱(chēng)為頻繁項(xiàng)；接著，用更新后的數(shù)據(jù)集中的每條記錄構(gòu)建FP樹(shù)，同時(shí)更新頭指針表。頭指針表包含所有頻繁FP樹(shù)項(xiàng)及它們的頻數(shù)，還有每個(gè)頻繁項(xiàng)指向下一個(gè)相同元素

20、的指針，該指針主要在挖掘 時(shí)使用。下面用上文提到的數(shù)據(jù)集展開(kāi)說(shuō)明，假設(shè)最小支持度為2。首先，統(tǒng)計(jì)數(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ù)集中的記錄創(chuàng)建FP樹(shù)，并同時(shí)更新頭指針表。倉(cāng)U建FP樹(shù)時(shí),當(dāng)待添加的記錄與 FP樹(shù)中的路徑相同，則只需更新元素對(duì)應(yīng)的頻數(shù)；如果待添加的記錄 與FP樹(shù)存在不一致，則在不一致的地方分叉， 創(chuàng)建新的結(jié)點(diǎn)。如圖6圖9所示。注意, FP樹(shù)的根節(jié)點(diǎn)是 null。圖6向FP樹(shù)添加第

21、一條記錄 a,b,c null圖7向FP樹(shù)添加第二條記錄 a,b,c,d 圖9向FP樹(shù)添加第四條記錄 a ,b 432. 挖掘頻繁項(xiàng)集得到FP樹(shù)后，需要對(duì)每一個(gè)頻繁項(xiàng)，逐個(gè)挖掘頻繁項(xiàng)集。具體過(guò)程為：首先獲得頻繁項(xiàng)的前綴路徑，然后將前綴路徑作為新的數(shù)據(jù)集，以此構(gòu)建前綴路徑的條件FP樹(shù)。然后對(duì)條件FP樹(shù)中的每個(gè)頻繁項(xiàng)，獲得前綴路徑并以此構(gòu)建新的條件FP樹(shù)。不斷迭代，直到條件FP樹(shù)中只包含一個(gè)頻繁項(xiàng)為止。下面以元素 c為例，從上文圖9創(chuàng)建好的FP樹(shù)中挖掘頻繁項(xiàng)集。首先，獲得以c元素的前綴路徑a:2,b:2，注意此處a和b的頻數(shù)為2是因?yàn)閏 的頻數(shù)為2，所以與c共同出現(xiàn)的 a和b的頻數(shù)就都為 2。接著

22、，創(chuàng)建條件 FP樹(shù)，具體的創(chuàng)建過(guò)程和上一節(jié)創(chuàng)建FP樹(shù)的過(guò)程一樣，如 圖10所示。圖10 c元素的前綴路徑構(gòu)成的條件FP樹(shù)注意此時(shí)頭指針表中包含兩個(gè)元素，所以對(duì)每個(gè)元素，需要獲得前綴路徑，并將前綴路徑創(chuàng)建成條件 FP樹(shù)，直到條件 FP樹(shù)中只包含一個(gè)元素時(shí)返回。1. 對(duì)元素a，獲得前綴路徑為 ，則頻繁項(xiàng)集返回c,a;2. 對(duì)元素b，獲得前綴路徑a，則將前綴路徑創(chuàng)建成條件FP樹(shù)，如圖11所示。注意此時(shí)條件 FP樹(shù)中只包含一個(gè)元素，故返回頻繁項(xiàng)集c,b,a。由于元素b也是頻繁項(xiàng)，所以c,b也是頻繁項(xiàng)集。再加上c本身就是頻繁項(xiàng)集，所以c對(duì)應(yīng)的頻繁項(xiàng)集有：c c,a c,b c,b,a頭指針表nulla

23、2圖11 b元素的前綴路徑構(gòu)成的條件FP樹(shù)將其他元素a,b,d同樣按照上述對(duì)c的操作，得到表格3所示頻繁項(xiàng)集表格3元素a,b,c,d對(duì)應(yīng)的頻繁項(xiàng)集丿元糸頻繁項(xiàng)集a a b b b,a c c c,a c,b c,b,a d d d,a 44關(guān)聯(lián)規(guī)則挖掘原理關(guān)聯(lián)規(guī)則挖掘首先需要對(duì)上文得到的頻繁項(xiàng)集構(gòu)建所有可能的規(guī)則，然后對(duì)每條規(guī)則逐個(gè)計(jì)算置信度，輸出置信度大于最小置信度的所有規(guī)則。以頻繁項(xiàng)集a,b,c為例，構(gòu)建所有可能的規(guī)則：b,c - a, a,c - b,a,b - c,c - a,b,b - a,c,a - b,c。對(duì)每條規(guī)則計(jì)算置信度后，輸出滿(mǎn)足要求的規(guī)則即可。5. NaiveBayes

24、 基本原理樸素貝葉斯模型主要用來(lái)分類(lèi)，但是與SVM 模型不同的的是，樸素貝葉斯模型不需要針對(duì)目標(biāo)變量建立模型， 而是借助貝葉斯公式計(jì)算樣本屬于各個(gè)類(lèi)別的概率，然后取概率值大的類(lèi)別作為分類(lèi)類(lèi)別。之所以稱(chēng)之為樸素，是因?yàn)闃闼刎惾~斯模型假設(shè)各屬性之間是條件獨(dú)立的，該假設(shè)極大得簡(jiǎn)化了運(yùn)算，使得樸素貝葉斯模型變得非常簡(jiǎn)單。樸素貝葉斯模型主要應(yīng)用在文本分類(lèi)方面。這里需要用到向量空間模型，即將文本轉(zhuǎn)換成詞向量。詞向量的每一項(xiàng)是該詞出現(xiàn)的頻數(shù)。在樸素貝葉斯中會(huì)將頻數(shù)進(jìn)一步轉(zhuǎn)換成頻率。這樣就完成了文本到數(shù)值上的轉(zhuǎn)化，方便后期計(jì)算條件概率和先驗(yàn)概率。樸素貝葉斯模型也有它的優(yōu)缺點(diǎn)，優(yōu)點(diǎn)是模型簡(jiǎn)單，計(jì)算快；缺點(diǎn)是依賴(lài)

25、于屬性之間條件獨(dú)立這一假設(shè)，但是現(xiàn)實(shí)場(chǎng)景下很多情況并不滿(mǎn)足這一假設(shè)，使得樸素貝葉斯的準(zhǔn)確率受到影響。這種情況需要考慮半樸素貝葉斯，即放松屬性之間條件獨(dú)立這一假設(shè)，一定程度上考慮屬性之間的依賴(lài)關(guān)系。由于篇幅有限，對(duì)半樸素貝葉斯感興趣的話(huà)可自行參照文末參考資源學(xué)習(xí)，本文重點(diǎn)介紹樸素貝葉斯的原理和實(shí)現(xiàn)。5.1. 樸素貝葉斯原理樸素貝葉斯 模型主要利用貝葉斯公式進(jìn)行展開(kāi)。貝葉斯公式如下:p(c |x)沖 |c) *p(e)公式中P(C|X)表示X屬于類(lèi)別 C的概率，P(X|C)表示類(lèi)別 C中X出現(xiàn)的概率，P(C)表示類(lèi)別 C出現(xiàn)的概率。其中 P(C)稱(chēng)為先驗(yàn)概率，P(X|C)是條件概率，P(C|X)稱(chēng)

26、為 后驗(yàn)概率，將后驗(yàn)概率最大的類(lèi)作為 X的類(lèi)別輸出。假設(shè)有 C0和C1兩個(gè)類(lèi)，由于P(X) 都是一樣的，所以不需要考慮 P(X),只需考慮如下：1. 如果 P(X|C0) *P(C0) P(X|C1) *P(C1)，貝y P(C0|X) P(C1|X)，可得 X 屬于C0類(lèi);2. 如果 P(X|C0) *P(C0) P(X|C1) *P(C1)，貝y P(C0|X) log(P(X|C1) *P(C1)，則P(C0|X) P(C1|X)，可得X屬于C0類(lèi)；如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1)，則P(C0|X) -2.84,所以 log(P(X|C

27、1) *P(C1) log(P(X|C0) *P(C0),即P(C1|X) P(CO|X)，可得測(cè)試文本book, campus, study屬于類(lèi)別1。6. 決策樹(shù)基本原理決策樹(shù)算法又分很多種，常用的有ID3 , C4.5和CART決策樹(shù)。其中ID3和C4.5決策樹(shù)更傾向于處理類(lèi)別型的離散屬性值，對(duì)于連續(xù)型屬性值，則需要額外利用連續(xù)屬性離散化技術(shù)將其劃分成離散型屬性值。而CART決策樹(shù)，即分類(lèi)回歸樹(shù)，直接支持連續(xù)型屬性值。由于篇幅限制 CART樹(shù)會(huì)放在下一篇文章進(jìn)行介紹，本文主要詳細(xì)介紹ID3和C4.5 決策樹(shù)。決策樹(shù)利用了樹(shù)型結(jié)構(gòu)進(jìn)行決策，是經(jīng)典的if-the n 結(jié)構(gòu)。葉節(jié)點(diǎn)存儲(chǔ)類(lèi)別，內(nèi)

28、部節(jié)點(diǎn)代表特征或?qū)傩浴Ｗ⒁獗疚闹刑岬降奶卣骱蛯傩允峭粋€(gè)概念。為了讓讀者有一個(gè)感性的認(rèn)識(shí)，請(qǐng)看圖12所示決策樹(shù)。r? i?：i fin圖1所示決策樹(shù)用來(lái)將數(shù)據(jù)分為兩類(lèi)，是蘋(píng)果和非蘋(píng)果。如圖中所示，圓的和紅的，就是蘋(píng)果。不圓的不是蘋(píng)果。圓的但不紅的不是蘋(píng)果。本文將著重介紹ID3和C4.5兩種決策樹(shù)。決策樹(shù)需要選擇最優(yōu)特征劃分?jǐn)?shù)據(jù)集。這兩種決策樹(shù)的不同之處是劃分?jǐn)?shù)據(jù)集的最優(yōu)特征選擇方法不同。用最優(yōu)特征劃分?jǐn)?shù)據(jù)會(huì)使得數(shù)據(jù)集趨于更純，即數(shù)據(jù)集的類(lèi)別數(shù)更單一， 這樣的數(shù)據(jù)會(huì)更有序。 衡量數(shù)據(jù)的混亂程度就 必須提到信息和信息熵的概念。待分類(lèi)的事物可能劃分在多個(gè)類(lèi)別中，則符號(hào) Xi的信息是：1(若)=可知P

29、(Xi)越大，貝U l(Xi)越小，即Xi的概率越大，則 Xi包含的信息越少。我們都知道物理中的熵用來(lái)衡量混亂程度，熵越大說(shuō)明越混亂， 熵越小說(shuō)明越單一。同樣，信息熵用來(lái)衡量信息中的混亂程度。用所有類(lèi)別所有可能值包含的信息期望值表示信息 熵，計(jì)算方法如下：H=為卩例)嚨卻0ID3決策樹(shù)利用了信息增益來(lái)選擇最優(yōu)特征，用這種方法選擇的特征是使得信息熵增益最大的特征。而 C4.5決策樹(shù)利用了信息增益比 來(lái)選擇最優(yōu)特征。用這種方法選擇的特征是使得信息增益比最大的特征。為什么要提出信息增益比呢？這是因?yàn)橹豢紤]信息增益來(lái)劃分?jǐn)?shù)據(jù)集是有缺陷的。這種 后，劃分后的各個(gè)子數(shù)據(jù)集的類(lèi)別更單一，即更趨于有序，這就使

30、得劃分后的信息熵更小，缺陷體現(xiàn)在信息增益對(duì)選擇屬性取值多的特征更有利。因?yàn)榘磳傩匀≈刀嗟奶卣鲃澐謹(jǐn)?shù)據(jù)集那么信息增益就會(huì)更大。信息增益比可以很好的解決這個(gè)問(wèn)題。信息增益比通過(guò)引入類(lèi)似懲罰因子的概念，對(duì)屬性取值多的特征會(huì)有一定懲罰。6.1. 決策樹(shù)原理6.1.1. 選擇最優(yōu)特征決策樹(shù)通過(guò)不斷選擇最優(yōu)特征劃分?jǐn)?shù)據(jù)集，對(duì)劃分后的子數(shù)據(jù)集不斷迭代得選擇最優(yōu)特征劃分，直到所有的數(shù)據(jù)集屬于同一個(gè)類(lèi)別，或者沒(méi)有特征可以選擇為止。選擇最優(yōu)特征的算法有很多種，ID3決策樹(shù)用信息增益選擇最優(yōu)特征，C4.5決策樹(shù)用信息增益比選擇最優(yōu)特征。6.1.2. 信息增益-用于ID3決策樹(shù)信息增益，顧名思義就是原數(shù)據(jù)集的信息熵比

31、劃分后數(shù)據(jù)集的信息熵大的程度。信息增益越大，說(shuō)明劃分后的數(shù)據(jù)集信息熵更小，即該數(shù)據(jù)集類(lèi)別更趨于一致。特征A對(duì)數(shù)據(jù)集 D的信息增益g(D,A)為D的信息熵與按特征 A進(jìn)行劃分后 D 的信息熵之差，即其中，6.1.3. 信息增益比-用于C4.5決策樹(shù)信息增益比為了避免傾向于選擇屬性值多的特征作為最優(yōu)特征這個(gè)問(wèn)題，在信息增益的 基礎(chǔ)上引入了類(lèi)似懲罰因子的概念。特征A對(duì)數(shù)據(jù)集D的信息增益比gg(D,A)為信息增益g(D,A)與數(shù)據(jù)集D關(guān)于特 征A的取值的熵 HA(D)的比值，即其中,其中，n是特征A取值的個(gè)數(shù)。HA(D)就類(lèi)似懲罰因子，對(duì)于屬性值多的特征，雖 然信息增益g(D,A)會(huì)比較大，但是數(shù)據(jù)集

32、 D關(guān)于特征 A的取值的熵 HA(D)會(huì)比較大, 因而兩者的比值信息增益比gg(D,A)會(huì)比較小。除了可以使用信息增益和信息增益比來(lái)選擇最優(yōu)劃分特征之外，基尼指數(shù)也可以用來(lái)實(shí)現(xiàn)這個(gè)目的。基尼指數(shù)主要用于CART樹(shù)(即分類(lèi)回歸樹(shù))的分類(lèi)樹(shù)中的特征選擇。關(guān)于基尼指數(shù)的詳細(xì)內(nèi)容會(huì)在下一篇文章介紹。6.2. 用ID3決策樹(shù)進(jìn)行分類(lèi)本節(jié)主要介紹用ID3決策樹(shù)進(jìn)行分類(lèi)。為了便于理解，用表1所示數(shù)據(jù)集進(jìn)行詳細(xì)說(shuō) 明。利用C4.5決策樹(shù)進(jìn)行分類(lèi)的過(guò)程會(huì)在下節(jié)介紹。表格8示例數(shù)據(jù)集圓的紅的分類(lèi)111100010000100621.ID3決策樹(shù)選擇最優(yōu)特征表格8數(shù)據(jù)集的信息熵為：-1/5 * log(1/5) -

33、 4/5 * log(4/5) = 0.2171. 按特征圓的劃分?jǐn)?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. 按特征紅的劃分?jǐn)?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

34、綜上所述，由于按特征紅的”比按特征”圓的”劃分的信息增益大，所以特征紅的為最優(yōu)劃分特征。6.2.2. 按最優(yōu)特征劃分?jǐn)?shù)據(jù)集按特征紅的劃分?jǐn)?shù)據(jù)集后，有兩種情況，第一種為如果是紅的：0,則分類(lèi)：o；第二種為如果是紅的：1,則得到如下數(shù)據(jù)子集圓的：1,分類(lèi)：1；圓的：0,分類(lèi)：0接下來(lái)需要對(duì)數(shù)據(jù)子集圓的：1,分類(lèi)：1；圓的o 分類(lèi)：0繼續(xù)劃分。由于剩下一個(gè)特征，故按特征圓的”劃分?jǐn)?shù)據(jù)子集。劃分后，如果是圓的：1，則分類(lèi)：1 ；如果是圓的：0,則分類(lèi)：0。返回的決策樹(shù)用字典表示為：紅的：0：類(lèi)別 0, 1： 圓的：0：類(lèi)別 0, 1：類(lèi)別 163用C4.5決策樹(shù)進(jìn)行分類(lèi)C4.5 決為了讓讀者對(duì)ID3和

35、C4.5決策樹(shù)的不同之處有更好的理解，本節(jié)介紹用 策樹(shù)進(jìn)行分類(lèi)。為了便于理解，仍然使用表格8所示數(shù)據(jù)集進(jìn)行說(shuō)明。6.3.1. C4.5決策樹(shù)選擇最優(yōu)特征表格8數(shù)據(jù)集的信息熵為：-1/5 * log(1/5) - 4/5 * log(4/5) = 0.2171. 按特征圓的劃分?jǐn)?shù)據(jù)集，則信息熵為：3/5 * H(D1) + 2/5 * H(DO)=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ù)集關(guān)于特征圓的”的取值的熵為：-3/5 * log(3/5)

36、- 2/5 * log(2/5) = 0.29則信息增益比為 0.051 / 0.29 = 0.1762. 按特征紅的劃分?jǐn)?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ù)集關(guān)于特征紅的”的取值的熵為：-2/5 * log(2/5) 3/5 * log(3/5) = 0.29則信息增益比為0.097 / 0.29 = 0.334綜上所述，由于按特征紅的”比按特征”圓的”劃分的信息增益比大，

37、所以特征紅的為最優(yōu)劃分特征。6.3.2. 按最優(yōu)特征劃分?jǐn)?shù)據(jù)集C4.5決策樹(shù)按最優(yōu)特征劃分?jǐn)?shù)據(jù)集方法與上節(jié)ID3決策樹(shù)方法相同。7. 分類(lèi)回歸樹(shù)基本原理在上節(jié)中，主要介紹了ID3和C4.5決策樹(shù)。它們利用信息增益和信息增益比劃分?jǐn)?shù)據(jù)集。但是這兩種決策樹(shù)是有缺陷的， 即按某特征劃分后，該特征將不會(huì)在后面的劃分中 出現(xiàn)。這就導(dǎo)致了劃分過(guò)于迅速，從而影響分類(lèi)結(jié)果。在這篇文章中將要介紹的CART(Classificati on And Regression Tree)樹(shù)，即分類(lèi)回歸樹(shù)利用二分策略，有效地避免了劃分過(guò)于迅速這一問(wèn)題。而且二分策略可以直接處理連續(xù)型屬性值。CART樹(shù)(分類(lèi)回歸樹(shù))分為分類(lèi)樹(shù)

38、和回歸樹(shù)。顧名思義，分類(lèi)樹(shù)用于處理分類(lèi)問(wèn)題；回歸樹(shù)用來(lái)處理回歸問(wèn)題。 我們知道分類(lèi)和回歸是機(jī)器學(xué)習(xí)領(lǐng)域兩個(gè)重要的方向。分類(lèi)問(wèn)題輸出特征向量對(duì)應(yīng)的分類(lèi)結(jié)果，回歸問(wèn)題輸出特征向量對(duì)應(yīng)的預(yù)測(cè)值。分類(lèi)樹(shù)和ID3、C4.5決策樹(shù)相似，都用來(lái)處理分類(lèi)問(wèn)題。不同之處是劃分方法。分類(lèi)圖13分類(lèi)樹(shù)示例回歸樹(shù)用來(lái)處理回歸問(wèn)題?；貧w將已知數(shù)據(jù)進(jìn)行擬合， 對(duì)于目標(biāo)變量未知的數(shù)據(jù)可以預(yù)測(cè)目標(biāo)變量的值。如 圖14所示就是一個(gè)回歸樹(shù)，其中s是切分點(diǎn)，x是特征，y是目標(biāo)變量?？梢钥闯?圖14利用切分點(diǎn)s將特征空間進(jìn)行劃分，y是在劃分單元上的輸出值?；?歸樹(shù)的關(guān)鍵是如何選擇切分點(diǎn)、如何利用切分點(diǎn)劃分?jǐn)?shù)據(jù)集、如何預(yù)測(cè)y的取值。圖

39、14回歸樹(shù)示例7.1. CART樹(shù)原理7.1.1. 分類(lèi)樹(shù)二分分類(lèi)樹(shù)利用二分劃分?jǐn)?shù)據(jù)。將特征值等于切分點(diǎn)值的數(shù)據(jù)劃分為左子樹(shù)，將特征值不等于切分點(diǎn)值的數(shù)據(jù)劃分為右子樹(shù)?；嶂笖?shù)：同信息增益、信息增益比作用類(lèi)似，不過(guò)基尼指數(shù)相對(duì)更快假設(shè)有N個(gè)類(lèi)，樣本屬于第 n類(lèi)的概率為Pn，則基尼指數(shù)為：GinifP）二騫3兀0. pj若數(shù)據(jù)集按特征 A取值是否等于切分點(diǎn)值劃分為 D1和D2兩部分，則在特征 A下， 集合D的基尼指數(shù)為：GiniDf A）=詈&誠(chéng)（DJ+ 詈 4加（7.1.2. 回歸樹(shù)二分回歸樹(shù)也利用二分劃分?jǐn)?shù)據(jù)。與分類(lèi)樹(shù)不同的是，回歸樹(shù)將特征值大于切分點(diǎn)值的數(shù)據(jù) 劃分為左子樹(shù)，將特征值小于等于

40、切分點(diǎn)值的數(shù)據(jù)劃分為右子樹(shù)。平方誤差不同于分類(lèi)樹(shù)，回歸樹(shù)用平方誤差選擇切分點(diǎn)。若數(shù)據(jù)集按特征取值是否大于切分點(diǎn)值 劃分為兩部分，則在特征 A下，集合D的平方誤差為：72用CART樹(shù)進(jìn)行分類(lèi)和回歸本節(jié)主要用示例數(shù)據(jù)詳細(xì)說(shuō)明如何用CART樹(shù)進(jìn)行分類(lèi)和回歸。7.2.1. 分類(lèi)樹(shù)表格9示例數(shù)據(jù)集圓的紅的分類(lèi)111100010000100選擇最優(yōu)特征按特征圓的=1劃分?jǐn)?shù)據(jù)集，則Gini為：3/5 * Gini(D1) + 2/5 * Gini(DO)=3/5 * 1/3 * 2/3 + 2/3 * 1/3 + 2/5 * 0=0.266按特征紅的” =1劃分?jǐn)?shù)據(jù)集，則 Gini為：2/5 * Gin i

41、(D1) + 3/5 * Gin i(D0)=2/5 * 1/2 * 1/2 + 1/2 * 1/2 + 3/5 * 0=0.2綜上所述，由于按特征紅的”比特征圓的”劃分的基尼指數(shù)小，所以特征”紅的” =1為切分點(diǎn)。按最優(yōu)特征劃分?jǐn)?shù)據(jù)集按特征紅的劃分?jǐn)?shù)據(jù)集后，有兩種情況，第一種為如果是紅的：0,則分類(lèi)：0；第二種為如果是紅的：1,則有如下數(shù)據(jù)子集圓的:1,分類(lèi)：1;圓的:0,分類(lèi):0接下來(lái)需要對(duì)數(shù)據(jù)子集圓的：1,分類(lèi)：1；圓的：0,分類(lèi)：0繼續(xù)劃分。由于剩下一個(gè)特征，故按特征圓的”劃分?jǐn)?shù)據(jù)集。劃分后，如果是圓的：1，則分類(lèi)：1 ；如果是圓的：0,則分類(lèi)：0。返回的決策樹(shù)為：紅的：0：類(lèi)別 0, 1： 圓的：0：類(lèi)別 0, 1：類(lèi)別 1722. 回歸樹(shù)表格10示例數(shù)據(jù)集面積/平米價(jià)格/萬(wàn)2040.12140.33570.43670.2選擇最優(yōu)特征1. 按特征面積=20劃分?jǐn)?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劃分?jǐn)?shù)據(jù)集，則平方誤差為：y2 均值為(70.4 + 70.2) / 2 = 70.3