管理信息化人工智能機(jī)器學(xué)習(xí)簡(jiǎn)明原理

管理信息化人工智能機(jī)器學(xué)習(xí)簡(jiǎn)明原理支持向量機(jī)即supportvectormachine(簡(jiǎn)稱SVM)，是機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)典的分類算法。1.關(guān)于SVM的簡(jiǎn)介支持向量是距離分類超平面近的那些點(diǎn)，SVM的思想就是使得支持向量到分類超平面的間隔圖11的間隔大于支持向量到超平面2的間隔，因此超平面1優(yōu)于超平面2。圖1兩個(gè)超平面示例SVM可以很好得解決二分類問題，對(duì)于多分類情況，就需要對(duì)模型進(jìn)行改動(dòng)。如one-versus-rest法，這種方法每次選擇一個(gè)類別作為正樣本，剩下其他類別作為負(fù)樣本，假設(shè)一共有33個(gè)不同的SVM3個(gè)SVM模型中，得到的3個(gè)結(jié)果中的最大值則為最終的分類結(jié)果。SVMSVM算法的測(cè)試準(zhǔn)確度并不一定都很以及核函數(shù)的選擇等因素。任何模型都是優(yōu)點(diǎn)與缺點(diǎn)并存的。SVM的優(yōu)點(diǎn)是：1.可以解決線性不可分的情況。如圖2所示，兩類數(shù)據(jù)點(diǎn)根本無法用超平面分隔開;2.計(jì)算復(fù)雜度僅取決于少量支持向量，對(duì)于數(shù)據(jù)量大的數(shù)據(jù)集計(jì)算復(fù)雜度低。SVM的缺點(diǎn)是：1.經(jīng)典的SVM算法僅支持二分類，對(duì)于多分類問題需要改動(dòng)模型;2.不支持類別型數(shù)據(jù)，需在預(yù)處理階段將類別型數(shù)據(jù)轉(zhuǎn)換成離散型數(shù)據(jù)。類別型數(shù)據(jù)即"男"、"女"這類由字符串表示某類信息的數(shù)據(jù)，需將這類數(shù)據(jù)轉(zhuǎn)換成離散型數(shù)據(jù)如1、2。圖2線性不可分問題2.SVM基本原理SVM原理分為軟間隔最大化、拉格朗日對(duì)偶、最優(yōu)化問題求解、核函數(shù)、序列最小優(yōu)化SMO2.1.軟間隔最大化SVM的核心思路是最大化支持向量到分隔超平面的間隔。后面所有的推導(dǎo)都是以最大化此間SVM模型的目標(biāo)函數(shù)和約束條件。既然要最大化間隔，那么回顧下點(diǎn)x到超平面(w,b)的距離公式：其中超平面的公式為：由此可推出點(diǎn)x到超平面(w,b)的幾何間隔為：其中xi代表第i條數(shù)據(jù)，yi代表第i條數(shù)據(jù)對(duì)應(yīng)的目標(biāo)變量的取值，取值有+1和-1兩種。所以當(dāng)?shù)趇條數(shù)據(jù)被正確分類時(shí)，y取值和w*x+b取值的正負(fù)一致，幾何間隔為正；當(dāng)被錯(cuò)誤分類時(shí)，y取值和w*x+b取值的正負(fù)相反，幾何間隔為負(fù)。圖3樣本數(shù)關(guān)于w*x+b的取值符號(hào)定義幾何間隔中最小的為：由此，可以得到間隔最大化問題的目標(biāo)函數(shù)：并遵循如下約束條件：做如下變換：則目標(biāo)函數(shù)轉(zhuǎn)換為：相應(yīng)的約束條件變?yōu)椋鹤鋈缦伦儞Q：可得目標(biāo)函數(shù)和約束條件變?yōu)椋河捎趙,b成倍數(shù)變化并不會(huì)影響超平面的公式，所以：此時(shí)得到最終的間隔最大化的目標(biāo)函數(shù)和約束條件如下：outliers，這些數(shù)據(jù)點(diǎn)并不滿足上面推導(dǎo)出的約束條件，如圖4所示，圖中點(diǎn)A就是outlier特異點(diǎn)。圖4Outlier特異點(diǎn)為了解決這種問題，對(duì)每個(gè)樣本點(diǎn)引進(jìn)一個(gè)松弛變量，使得約束條件變?yōu)椋哼@樣給outlier的約束條件加上一個(gè)變量，使其可以滿足大于等于1變量變?yōu)椋浩渲蠧加入松弛變量的目標(biāo)函數(shù)就是軟間隔最大化。2.2.拉格朗日對(duì)偶函數(shù)如下：分析可知：則原最優(yōu)化問題轉(zhuǎn)換成：?jiǎn)栴}得到原問題的最優(yōu)解。原最優(yōu)化問題的對(duì)偶問題為：2.3.最優(yōu)化問題求解解關(guān)于拉格朗日函數(shù)的極小化問題。對(duì)三個(gè)變量分別求偏導(dǎo)得：將以上三式帶入拉格朗日函數(shù)中得：那么極大極小化拉格朗日函數(shù)轉(zhuǎn)換成：為求解方便，將極大轉(zhuǎn)換成極小得：2.4.核函數(shù)圖2將超平面換成超曲面，則可以將正負(fù)樣本正確分類，如圖5所示。圖5超曲面分離正負(fù)樣本我們知道曲面的公式是：映射到新坐標(biāo)如下：可將超曲面在新坐標(biāo)下表示成超平面：也就是將在二維空間(x1,x2)下線性不可分的問題轉(zhuǎn)換成了在五維空間(z1,z2,z3,z4,z5)下線性可分的問題。得映射后新坐標(biāo)下的內(nèi)積：有一核函數(shù)如下：可知成。那么為什么是映射到高維后的內(nèi)積運(yùn)算呢？這是因?yàn)樵谏瞎?jié)中我們得到了如下目標(biāo)函數(shù)：斯核可以將低維空間映射到無窮維。運(yùn)用核函數(shù)后，最優(yōu)化問題的目標(biāo)函數(shù)和約束條件變?yōu)椋?.5.序列最小優(yōu)化(Sequentialminimaloptimization)N個(gè)alpha自變量的目標(biāo)變量和兩個(gè)約束條件。由于目標(biāo)變量中自變量alpha有N個(gè)，為了便與求解，每次選出一對(duì)自變量alpha，然后求目標(biāo)函數(shù)關(guān)于其中一個(gè)alphaalphaalphaalpha并執(zhí)行上述操作，直到達(dá)到最大迭代數(shù)或沒有任何自變量alpha再發(fā)生變化為止，這就是SMO的基本思想。說直白些，SMO就是在約束條件下對(duì)目標(biāo)函數(shù)的優(yōu)化求解算法。為何不能每次只選一個(gè)自變量進(jìn)行優(yōu)化？那是因?yàn)橹贿x一個(gè)自變量alpha個(gè)約束條件，即所有alpha和y值乘積的和等于0。下面是詳細(xì)的SMO過程。假設(shè)選出了兩個(gè)自變量分別是alpha1和alpha2，除了這兩個(gè)自變量之外的其他自變量保持固定，則目標(biāo)變量和約束條件轉(zhuǎn)化為：將約束條件中的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)修剪的值：之所以說alpha2是未經(jīng)修剪的值是因?yàn)樗衋lpha都必須滿足大于等于0且小于等于C的約束條件，用此約束條件將alpha2進(jìn)行修剪，修剪過程如下：由此得：分兩種情況討論：情況1.當(dāng)y1等于y2時(shí)，有：情況2.當(dāng)y1不等于y2時(shí)，有：修剪后，可得alpha2的取值如下：由alpha2和alpha1的關(guān)系，可得：在完成alpha1和alpha2的一輪更新后，需要同時(shí)更新b的值，當(dāng)alpha1更新后的值滿足0<alpha1<C時(shí)，由KKT條件得：由于篇幅有限，在此就不把推導(dǎo)過程一一列舉，可得：同樣的道理，當(dāng)alpha2更新后的值滿足0<alpha1<C時(shí)可得：若更新后的alpha1和alpha2同時(shí)滿足大于0且小于C的條件，那么b就等于b1等于b2；否則，b取b1和b2的中點(diǎn)。那么問題來了，如何選擇alpha1和alpha2呢？選擇違背下列KKT條件推導(dǎo)結(jié)果的alpha作為alpha1：為了讓每次變化盡可能大，alpha2的選擇滿足如下式子最大，即步長最大化：其中E是上面提到過的預(yù)測(cè)值和真實(shí)值差值的絕對(duì)值，也就是誤差值。按上述方法不斷選擇一對(duì)alpha并更新，直到達(dá)到最大迭代次數(shù)或所有alpha都不再變化，則停止迭代。有朋友就會(huì)問，求出alpha之后呢？如何判斷新樣本數(shù)據(jù)屬于1還是-1呢？別忘了，在最優(yōu)化求解一節(jié)，我們得到了如下：若f(x)大于0，則新樣本數(shù)據(jù)屬于1；否則，新樣本數(shù)據(jù)屬于-1?？梢砸姷?，求出alpha后，所有問題都迎刃而解了。3.頻繁項(xiàng)集與關(guān)聯(lián)規(guī)則FP-growth基本原理3.1.從啤酒和尿布引出的頻繁項(xiàng)集在上一節(jié)中，主要介紹了支持向量機(jī)SVM學(xué)習(xí)主要分為四大類，分別是分類，聚類，回歸和關(guān)聯(lián)分析。第一篇中的SVM就屬于分類。那么下面筆者開始介紹關(guān)聯(lián)分析。關(guān)聯(lián)分析分為頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則挖掘。頻繁項(xiàng)集。頻繁項(xiàng)集是在數(shù)據(jù)庫中大量頻繁出現(xiàn)的數(shù)據(jù)集合。那么發(fā)現(xiàn)這些頻繁項(xiàng)集有什么意義呢？1.用于制定營銷策略。如同啤酒與尿布的例子，超市如果將啤酒和尿布放在相鄰的位置，加銷量。2."頻繁項(xiàng)集"時(shí)，瀏覽器自動(dòng)彈出如"頻繁項(xiàng)集置信度""頻繁項(xiàng)集關(guān)聯(lián)規(guī)則"瀏覽器的智能，其實(shí)這里的秘訣就是頻繁項(xiàng)集。也就是說，在大量的用戶搜索記錄中，"頻繁項(xiàng)集"和"置信度"共同出現(xiàn)在了大多數(shù)的搜索記錄中。同理，"頻繁項(xiàng)集"和"關(guān)聯(lián)規(guī)則"也頻繁得共同出現(xiàn)在搜索記錄中。3.頻繁項(xiàng)集挖掘算法可以得到該事物的熱點(diǎn)新聞。主流的頻繁項(xiàng)集挖掘算法有Apriori和FP-growth。其中Apriori算法需要多次掃描數(shù)據(jù)庫，F(xiàn)P-growthFrequentPatternGrowthFP樹(即FrequentPatternTree)這樣的數(shù)據(jù)結(jié)構(gòu)，巧妙得將數(shù)據(jù)存儲(chǔ)在FP樹中，只需要在構(gòu)建FPFP-growth算法比AprioriFP項(xiàng)集挖掘原理一節(jié)介紹。挖掘出頻繁項(xiàng)集后，可以從頻繁項(xiàng)集中進(jìn)一步挖掘關(guān)聯(lián)規(guī)則。3.2.關(guān)聯(lián)規(guī)則簡(jiǎn)介關(guān)聯(lián)規(guī)則是在頻繁項(xiàng)集的基礎(chǔ)上得到的。關(guān)聯(lián)規(guī)則指由集合A，可以在某置信度下推出集合BAB{'雞蛋','面包'}->{'牛奶'}0.9有90%的客戶還買了牛奶。關(guān)聯(lián)規(guī)則可以用來發(fā)現(xiàn)很多有趣的規(guī)律。這其中需要先闡明兩個(gè)概念：支持度和置信度。3.2.1.支持度Support支持度指某頻繁項(xiàng)集在整個(gè)數(shù)據(jù)集中的比例。假設(shè)數(shù)據(jù)集有10{'雞蛋','面包'}的有5條記錄，那么{'雞蛋','面包'}的支持度就是5/10=0.5。3.2.2.置信度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){'''多個(gè)ip地址同時(shí)發(fā)送數(shù)據(jù)'}->{'異常'}，該規(guī)則的置信度為0.85。這條規(guī)則表示，當(dāng)流量數(shù)據(jù)包大，并有多個(gè)ip地址同時(shí)向目標(biāo)ip發(fā)送數(shù)據(jù)時(shí)，則有85%的概率存在異常，需要觸發(fā)報(bào)警。3.3.頻繁項(xiàng)集挖掘原理頻繁項(xiàng)集挖掘分為構(gòu)建FPFP作為例子展開，該示例數(shù)據(jù)集共四條數(shù)據(jù)。表格1示例數(shù)據(jù)集數(shù)據(jù)集a,b,cc,d,b,ad,e,ab,a3.3.1.構(gòu)建FP樹構(gòu)建FP樹時(shí)，首先統(tǒng)計(jì)數(shù)據(jù)集中各個(gè)元素出現(xiàn)的頻數(shù)，將頻數(shù)小于最小支持度的元素刪除，的數(shù)據(jù)集中的每條記錄構(gòu)建FP樹，同時(shí)更新頭指針表。頭指針表包含所有頻繁項(xiàng)及它們的頻數(shù)，還有每個(gè)頻繁項(xiàng)指向下一個(gè)相同元素的指針，該指針主要在挖掘FP樹時(shí)使用。下面用上文提到的數(shù)據(jù)集展開說明，假設(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ù)集a,b,ca,b,c,da,da,b然后，用更新后的數(shù)據(jù)集中的記錄創(chuàng)建FPFP加的記錄與FPFP樹存在不一致，則在不一致的地方分叉，創(chuàng)建新的結(jié)點(diǎn)。如圖6~圖9所示。注意，F(xiàn)P樹的根節(jié)點(diǎn)是null。圖6向FP樹添加第一條記錄{a,b,c}圖7向FP樹添加第二條記錄{a,b,c,d}圖8向FP樹添加第三條記錄{a,d}圖9向FP樹添加第四條記錄{a,b}3.3.2.挖掘頻繁項(xiàng)集得到FP樹后，需要對(duì)每一個(gè)頻繁項(xiàng)，逐個(gè)挖掘頻繁項(xiàng)集。具體過程為：首先獲得頻繁項(xiàng)的FPFP樹中的每個(gè)頻繁項(xiàng)，獲得前綴路徑并以此構(gòu)建新的條件FPFP樹中只包含一個(gè)頻繁項(xiàng)為止。下面以元素c為例，從上文圖9創(chuàng)建好的FP樹中挖掘頻繁項(xiàng)集。首先，獲得以c元素的前綴路徑{a:2,b:2}，注意此處a和b的頻數(shù)為2是因?yàn)閏的頻數(shù)為2，所以與c共同出現(xiàn)的a和b的頻數(shù)就都為2。接著，創(chuàng)建條件FP樹，具體的創(chuàng)建過程和上一節(jié)創(chuàng)建FP樹的過程一樣，如圖10所示。圖10c元素的前綴路徑構(gòu)成的條件FP樹建成條件FP樹，直到條件FP樹中只包含一個(gè)元素時(shí)返回。1.對(duì)元素a，獲得前綴路徑為{}，則頻繁項(xiàng)集返回{c,a};2.對(duì)元素b{a}FP圖11條件FP{c,b,a}b{c,b}也是頻繁項(xiàng)集。再加上{c}本身就是頻繁項(xiàng)集，所以c對(duì)應(yīng)的頻繁項(xiàng)集有：{c}{c,a}{c,b}{c,b,a}。圖11b元素的前綴路徑構(gòu)成的條件FP樹將其他元素a,b,d同樣按照上述對(duì)c的操作，得到表格3所示頻繁項(xiàng)集。表格3元素a,b,c,d對(duì)應(yīng)的頻繁項(xiàng)集元素頻繁項(xiàng)集a{a}b{b,a}c{c}{c,a}{c,b}{c,b,a}dwpg85tv{d,a}3.4.關(guān)聯(lián)規(guī)則挖掘原理算置信度，輸出置信度大于最小置信度的所有規(guī)則。以頻繁項(xiàng)集{a,b,c}為例，構(gòu)建所有可能的規(guī)則：{b,c}->{a},{a,c}->,{a,b}->{c},{c}->{a,b},->{a,c},{a}->{b,c}。對(duì)每條規(guī)則計(jì)算置信度后，輸出滿足要求的規(guī)則即可。4.NaiveBayes基本原理SVM模型不同的的是，樸素貝葉斯模型不需要針對(duì)目該假設(shè)極大得簡(jiǎn)化了運(yùn)算，使得樸素貝葉斯模型變得非常簡(jiǎn)單。樣就完成了文本到數(shù)值上的轉(zhuǎn)化，方便后期計(jì)算條件概率和先驗(yàn)概率。學(xué)習(xí)，本文重點(diǎn)介紹樸素貝葉斯的原理和實(shí)現(xiàn)。4.1.樸素貝葉斯原理樸素貝葉斯模型主要利用貝葉斯公式進(jìn)行展開。貝葉斯公式如下：公式中P(C|X)表示X屬于類別C的概率，P(X|C)表示類別C中X出現(xiàn)的概率，P(C)表示類別CP(C)P(X|C)P(C|X)概率最大的類作為XC0和C1P(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類。由上述可知，需要計(jì)算P(X|C)和P(C)。樸素貝葉斯假設(shè)屬性之間條件獨(dú)立，可得：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個(gè)屬性上頻數(shù)總和除以類別為C的樣P(Xi|C)為0造成P(X|C)為01和2P(Xi|C)=(|Dc,xi|+1)/(|Dc,x|+2)。又有P(C)=|Dc|/|D|，表示類別為C的樣本集合大小除以數(shù)據(jù)集D的樣本集合大小。至此，通過P(X|C0)*P(C0)和P(X|C1)*P(C1)的大小比較，可得X所屬類別。但是小數(shù)連乘會(huì)造成所得值幾乎等于0loglog(P(X|C0)*P(C0))和log(P(X|C1)*P(C1))的大小來判斷X得：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(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))。4.2.用樸素貝葉斯進(jìn)行文本分類條件概率P(X|C)和先驗(yàn)概率P(C)P(X|C)與先驗(yàn)概率P(C)計(jì)算后驗(yàn)概率P(C0|X)P(C1|X)P(C0|X)P(C1|X)大小得到X屬于C0類還是C1表格4所示訓(xùn)練數(shù)據(jù)和表格5所示測(cè)試數(shù)據(jù)展開介紹。表格4示例訓(xùn)練數(shù)據(jù)集類別訓(xùn)練文本1'book','student','campus','study'0'others','game','sky'1'campus','book'0'others','yes'表格5示例測(cè)試數(shù)據(jù)集類別訓(xùn)練文本？'book','campus','study'4.2.1.從文本到詞向量首先需要將文本表示成詞向量，去掉重復(fù)的詞。將表1中示例數(shù)據(jù)集表示成詞向量如下：['book','student','campus','study','others','game','sky','yes']可以看出，重復(fù)的'campus','book','others'都只出現(xiàn)了一次。然后，需要將文本列表轉(zhuǎn)換成詞向量列表，文本中的詞在詞向量中出現(xiàn)為10,如表格6、表格7所示：表格6訓(xùn)練文本詞向量列表類別訓(xùn)練文本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測(cè)試文本詞向量列表類別訓(xùn)練文本？[1,0,1,1,0,0,0,0]4.2.2.從詞向量到條件概率和先驗(yàn)概率由上一章知，條件概率P(X|C)=P(X0|C)*P(X1|C)*P(X2|C)*P(X3|C)*…*P(Xn|C),為防止概率為0影響結(jié)果，加入拉普拉斯平滑后P(Xi|C)=(|Dc,xi|+1)/(|Dc,x|+2),先驗(yàn)概率P(C)=|Dc|/|D|。為防止小數(shù)連乘造成結(jié)果幾乎為0，引入log函數(shù)，由于測(cè)試文本只包含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)=-2.84log(P(X|C1)*P(C1))=log(3/8)+log(3/8)+log(2/8)+log(2/4)=-1.764.2.3.根據(jù)后驗(yàn)概率分類由上一章知，因此后驗(yàn)概率P(C0|X)只需考慮P(X|C0)*P(C0)，同理后驗(yàn)概率P(C1|X)只需考慮P(X|C1)*P(C1)。已知：如果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類。又由于-1.76>-2.84,所以log(P(X|C1)*P(C1))>log(P(X|C0)*P(C0)),即P(C1|X)>P(C0|X)，可得測(cè)試文本{'book','campus','study'}屬于類別1。5.決策樹基本原理決策樹算法又分很多種，常用的有ID3C4.5和CARTID3和C4.5決策樹更傾其劃分成離散型屬性值。而CART決策樹，即分類回歸樹，直接支持連續(xù)型屬性值。由于篇幅限制CART樹會(huì)放在下一篇文章進(jìn)行介紹，本文主要詳細(xì)介紹ID3和C4.5決策樹。決策樹利用了樹型結(jié)構(gòu)進(jìn)行決策，是經(jīng)典的if-then特征或?qū)傩?。注意本文中提到的特征和屬性是同一個(gè)概念。為了讓讀者有一個(gè)感性的認(rèn)識(shí)，請(qǐng)看圖12所示決策樹。圖12決策樹示例圖1果。不圓的不是蘋果。圓的但不紅的不是蘋果。本文將著重介紹ID3和C4.5兩種決策樹。決策樹需要選擇最優(yōu)特征劃分?jǐn)?shù)據(jù)集。這兩種決到信息和信息熵的概念。待分類的事物可能劃分在多個(gè)類別中，則符號(hào)Xi的信息是:可知P(Xi)越大，則I(Xi)越小，即Xi的概率越大，則Xi包含的信息越少。我們都知道物理中的熵用來衡量混亂程度，熵越大說明越混亂，熵越小說明越單一。同樣，信息熵用來衡量信息中的混亂程度。用所有類別所有可能值包含的信息期望值表示信息熵，計(jì)算方法如下：ID3決策樹利用了信息增益來選擇最優(yōu)特征，用這種方法選擇的特征是使得信息熵增益最大的特征。而C4.5決策樹利用了信息增益比來選擇最優(yōu)特征。用這種方法選擇的特征是使得信息增益比最大的特征。體現(xiàn)在信息增益對(duì)選擇屬性取值多的特征更有利。因?yàn)榘磳傩匀≈刀嗟奶卣鲃澐謹(jǐn)?shù)據(jù)集后，子的概念，對(duì)屬性取值多的特征會(huì)有一定懲罰。5.1.決策樹原理5.1.1.選擇最優(yōu)特征有很多種，ID3決策樹用信息增益選擇最優(yōu)特征，C4.5決策樹用信息增益比選擇最優(yōu)特征。5.1.2.信息增益-用于ID3決策樹大，說明劃分后的數(shù)據(jù)集信息熵更小，即該數(shù)據(jù)集類別更趨于一致。特征A對(duì)數(shù)據(jù)集D的信息增益g(D,A)為D的信息熵與按特征A進(jìn)行劃分后D的信息熵之差，即其中，5.1.3.信息增益比–用于C4.5決策樹上引入了類似懲罰因子的概念。特征A對(duì)數(shù)據(jù)集D的信息增益比gg(D,A)為信息增益g(D,A)與數(shù)據(jù)集D關(guān)于特征A的取值的熵HA(D)的比值，即其中,n是特征AHA(D)g(D,A)會(huì)比較大，但是數(shù)據(jù)集D關(guān)于特征A的取值的熵HA(D)會(huì)比較大，因而兩者的比值信息增益比gg(D,A)會(huì)比較小。個(gè)目的。基尼指數(shù)主要用于CART樹(即分類回歸樹)的分類樹中的特征選擇。關(guān)于基尼指數(shù)的詳細(xì)內(nèi)容會(huì)在下一篇文章介紹。5.2.用ID3決策樹進(jìn)行分類本節(jié)主要介紹用ID31用C4.5決策樹進(jìn)行分類的過程會(huì)在下節(jié)介紹。表格8示例數(shù)據(jù)集圓的紅的分類1111000100001005.2.1.ID3決策樹選擇最優(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(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"紅的"比按特征"圓的""紅的"為最優(yōu)劃分特征。5.2.2.按最優(yōu)特征劃分?jǐn)?shù)據(jù)集按特征"紅的":0,則分類:0;第二種為如果是紅的:1,則得到如下數(shù)據(jù)子集{圓的:1,分類：1;圓的:0,分類:0}接下來需要對(duì)數(shù)據(jù)子集{圓的:1,1;圓的:0,分類:0}繼續(xù)劃分。由于剩下一個(gè)特征，故按特征"圓的"劃分?jǐn)?shù)據(jù)子集。劃分后，如果是圓的:1，則分類:1:0,則分類:0。返回的決策樹用字典表示為：{'紅的':{0:'類別0',1:{'圓的':{0:'類別0',1:'類別1'}}}}5.3.用C4.5決策樹進(jìn)行分類為了讓讀者對(duì)ID3和C4.5C4.5決策樹進(jìn)行分類。為了便于理解，仍然使用表格8所示數(shù)據(jù)集進(jìn)行說明。5.3.1.C4.5決策樹選擇最優(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(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ù)集關(guān)于特征"圓的"的取值的熵為:-3/5*log(3/5)–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"紅的"比按特征"圓的""紅的"為最優(yōu)劃分特征。5.3.2.按最優(yōu)特征劃分?jǐn)?shù)據(jù)集C4.5決策樹按最優(yōu)特征劃分?jǐn)?shù)據(jù)集方法與上節(jié)ID3決策樹方法相同。6.分類回歸樹基本原理在上節(jié)中，主要介紹了ID3和C4.5決策樹。它們利用信息增益和信息增益比劃分?jǐn)?shù)據(jù)集。就導(dǎo)致了劃分過于迅速，從而影響分類結(jié)果。在這篇文章中將要介紹的CART（ClassificationAndRegressionTree）樹，即分類回歸樹利用二分策略，有效地避免了劃分過于迅速這一問題。而且二分策略可以直接處理連續(xù)型屬性值。CART征向量對(duì)應(yīng)的分類結(jié)果，回歸問題輸出特征向量對(duì)應(yīng)的預(yù)測(cè)值。分類樹和ID3C4.5決策樹相似，都用來處理分類問題。不同之處是劃分方法。分類樹利用基尼指數(shù)進(jìn)行二分。如圖13所示就是一個(gè)分類樹。圖13分類樹示例圖14所示就是一個(gè)回歸樹，其中sxy以看出圖14利用切分點(diǎn)s將特征空間進(jìn)行劃分，y是如何選擇切分點(diǎn)、如何利用切分點(diǎn)劃分?jǐn)?shù)據(jù)集、如何預(yù)測(cè)y的取值。圖14回歸樹示例6.1.CART樹原理6.1.1.分類樹二分分點(diǎn)值的數(shù)據(jù)劃分為右子樹?；嶂笖?shù)：同信息增益、信息增益比作用類似，不過基尼指數(shù)相對(duì)更快假設(shè)有N個(gè)類，樣本屬于第n類的概率為Pn，則基尼指數(shù)為：若數(shù)據(jù)集按特征A取值是否等于切分點(diǎn)值劃分為D1和D2AD的基尼指數(shù)為：6.1.2.回歸樹二分為左子樹，將特征值小于等于切分點(diǎn)值的數(shù)據(jù)劃分為右子樹。平方誤差為兩部分，則在特征A下，集合D的平方誤差為：6.2.用CART樹進(jìn)行分類和回歸本節(jié)主要用示例數(shù)據(jù)詳細(xì)說明如何用CART樹進(jìn)行分類和回歸。6.2.1.分類樹表格9示例數(shù)據(jù)集圓的紅的分類111100010000100選擇最優(yōu)特征按特征"圓的"=1劃分?jǐn)?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劃分?jǐn)?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"紅的"比特征"圓的""紅的"=1為切分點(diǎn)。按最優(yōu)特征劃分?jǐn)?shù)據(jù)集按特征"紅的":0,則分類:0;第二種為如果是紅的:1,則有如下數(shù)據(jù)子集{圓的:1,分類：1;圓的:0,分類:0}接下來需要對(duì)數(shù)據(jù)子集{圓的:1,1;圓的:0,分類:0}繼續(xù)劃分。由于剩下一個(gè)特征，故按特征"圓的"劃分?jǐn)?shù)據(jù)集。劃分后，如果是圓的:1，則分類:1；如果是圓的:0,則分類:0。返回的決策樹為：{'紅的':{0:'類別0',1:{'圓的':{0:'類別0',1:'類別1'}}}}6.2.2.回歸樹表格10示例數(shù)據(jù)集面積/平米價(jià)格/萬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ù)集，則平方誤差為：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劃分?jǐn)?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為切分點(diǎn)。按最優(yōu)特征劃分?jǐn)?shù)據(jù)集以特征"面積"=21為切分點(diǎn)，將數(shù)據(jù)切分為{面積=20,價(jià)格=40.1;面積=21,價(jià)格=40.3}，{面積=35,價(jià)格=70.4;面積=36,價(jià)格=70.2}兩個(gè)子集。其中子集{面積=20,價(jià)格=40.1;面積=21,價(jià)格=40.3}的目標(biāo)變量非常接近，故不繼續(xù)劃分，得葉節(jié)點(diǎn)值(40.1+40.3)/2=40.2；同理得子集{面積=35,價(jià)格=70.4;面積=36,價(jià)格=70.2}的葉節(jié)點(diǎn)值為(70.4+70.2)/2=70.3。7.Adaboost基本原理類在機(jī)器學(xué)習(xí)方向是應(yīng)用最廣的方向之一。本文將要介紹的是分類模型中的另一種模型，AdaBoost（adaptiveboosting），即自適應(yīng)提升算法。Boosting成起來，往往可以得到很好的效果。俗話說，"三個(gè)臭皮匠，頂個(gè)諸葛亮"，就是這個(gè)道理。這類boosting算法的特點(diǎn)是各個(gè)弱分類器之間是串行訓(xùn)練的，當(dāng)前弱分類器的訓(xùn)練依賴于上一輪弱分類器的訓(xùn)練結(jié)果。各個(gè)弱分類器的權(quán)重是不同的，效果好的弱分類器的權(quán)重大，AdaBoost練回歸模型。這需要將弱分類器替換成回歸模型，并改動(dòng)損失函數(shù)。本文將重點(diǎn)介紹用AdaBoost進(jìn)行分類的算法原理。AdaBoost樣訓(xùn)練的模型比單一設(shè)置模型的訓(xùn)練精度高。當(dāng)然，就如每一個(gè)算法都有自己的優(yōu)缺點(diǎn)一樣，AdaBoost也有自身的缺點(diǎn)。AdaBoost算法one-versus-rest的思想來訓(xùn)練多分類模型。關(guān)于one-verus-rest的細(xì)節(jié)可以參考本系列第一篇文章SVM。為了讓讀者有一個(gè)感性的認(rèn)識(shí)，在文章一開始先舉個(gè)AdaBoost訓(xùn)練出來的強(qiáng)分類器的例子，G(x)中包含三個(gè)弱分類器f(x),g(x)和z(x)分別為0.80,0.69和0.71。G(x)=sign(0.80*f(x)+0.69*g(x)+0.71*z(x))7.1.AdaBoost原理AdaBoost上一輪迭代的樣本權(quán)重。具體過程如下：7.1.1.訓(xùn)練當(dāng)前迭代最優(yōu)弱分類器最優(yōu)弱分類器是錯(cuò)誤率最小的那個(gè)弱分類器。錯(cuò)誤率的計(jì)算公式是：其中m=1,2,..,Mm輪迭代。i代表第i個(gè)樣本。w是樣本權(quán)重。I指示函數(shù)取值為1或0II函數(shù)結(jié)果為1I函數(shù)括號(hào)中的表達(dá)式為假時(shí)，I函數(shù)結(jié)果為0。取錯(cuò)誤率最低的弱分類器為當(dāng)前迭代的最優(yōu)弱分類器。注意，第一輪迭代計(jì)算時(shí)樣本權(quán)重初始化為總樣本數(shù)分之一。7.1.2.計(jì)算最優(yōu)弱分類器的權(quán)重最優(yōu)弱分類器的權(quán)重只與該弱分類器的錯(cuò)誤率有關(guān)。弱分類器的權(quán)重計(jì)算公式如下：可以看出，錯(cuò)誤率越小，則alpha值越大，即該弱分類器的權(quán)重越高；反之，錯(cuò)誤率越大，則alpha作用，并削弱精度低的弱分類器的作用。7.1.3.根據(jù)錯(cuò)誤率更新樣本權(quán)重樣本權(quán)重的更新與當(dāng)前樣本權(quán)重和弱分類器的權(quán)重有關(guān)。樣本權(quán)重更新公式如下：其中m=1,2,..,M，代表第m輪迭代。i代表第i個(gè)樣本。w是樣本權(quán)重。alpha是弱分類器y和Gmy和Gm而在下一輪迭代中得到重視。7.1.4.迭代終止條件不斷重復(fù)1,2,3率閾值或達(dá)到最大迭代次數(shù)。7.2.用例子解釋AdaBoost原理本節(jié)主要用示例數(shù)據(jù)詳細(xì)說明用上節(jié)介紹的AdaBoost原理進(jìn)行分類的過程。本例用到的數(shù)據(jù)集如表1所示。為方便說明，本文所用弱分類器為形如x<1.5,則y=1，否則y=-1的簡(jiǎn)單分類算法。熟悉了AdaBoost原理的讀者，可以使用其他分類算法作為弱分類器。如使用本系列上篇文章介紹的CART樹中的分類樹作為弱分類器，可訓(xùn)練出提升分類樹模型。表格11示例數(shù)據(jù)集x012345y11-1-11-17.2.1.第一輪迭代1.a選擇最優(yōu)弱分類器第一輪迭代時(shí)，樣本權(quán)重初始化為（0.167,0.167,0.167,0.167,0.167,0.167）。表格11數(shù)據(jù)集的切分點(diǎn)有0.5,1.5,2.5,3.5,4.5。若按0.5切分?jǐn)?shù)據(jù)，得弱分類器x<0.5,則y=1;x>0.5,則y=-1。此時(shí)錯(cuò)誤率為2*0.167=0.334。若按1.5切分?jǐn)?shù)據(jù)，得弱分類器x<1.5,則y=1;x>1.5,則y=-1。此時(shí)錯(cuò)誤率為1*0.167=0.167。若按2.5切分?jǐn)?shù)據(jù)，得弱分類器x<2.5,則y=1;x>2.5,則y=-1。此時(shí)錯(cuò)誤率為2*0.167=0.334。若按3.5切分?jǐn)?shù)據(jù)，得弱分類器x<3.5,則y=1;x>3.5,則y=-1。此時(shí)錯(cuò)誤率為3*0.167=0.501。若按4.5切分?jǐn)?shù)據(jù)，得弱分類器x<4.5,則y=1;x>4.5,則y=-1。此時(shí)錯(cuò)誤率為2*0.167=0.334。由于按1.5劃分?jǐn)?shù)據(jù)時(shí)錯(cuò)誤率最小為0.167，則最優(yōu)弱分類器為x<1.5,則y=1;x>1.5,則y=-1。1.b計(jì)算最優(yōu)弱分類器的權(quán)重alpha=0.5*ln((1–0.167)/0.167)=0.80471.c更新樣本權(quán)重x=0,1,2,3,5時(shí)，y分類正確，則樣本權(quán)重為：0.167*exp(-0.8047)=0.075x=4時(shí)，y分類錯(cuò)誤，則樣本權(quán)重為：0.167*exp(0.8047)=0.373新樣本權(quán)重總和為0.075*5+0.373=0.748規(guī)范化后，x=0,1,2,3,5時(shí)，樣本權(quán)重更新為：0.075/0.748=0.10x=4時(shí),樣本權(quán)重更新為：0.373/0.748=0.50綜上，新的樣本權(quán)重為(0.1,0.1,0.1,0.1,0.5,0.1)。此時(shí)強(qiáng)分類器為G(x)=0.8047*G1(x)G1(x)為x<1.5,則y=1;x>1.5,則y=-1錯(cuò)誤率為1/6=0.167。7.2.2.第二輪迭代2.a選擇最優(yōu)弱分類器若按0.5切分?jǐn)?shù)據(jù)，得弱分類器x>0.5,則y=1;x<0.5,則y=-1。此時(shí)錯(cuò)誤率為0.1*4=0.4。若按1.5切分?jǐn)?shù)據(jù)，得弱分類器x<1.5,則y=1;x>1.5,則y=-1。此時(shí)錯(cuò)誤率為1*0.5=0.5。若按2.5切分?jǐn)?shù)據(jù)，得弱分類器x>2.5,則y=1;x<2.5,則y=-1。此時(shí)錯(cuò)誤率為0.1*4=0.4。若按3.5切分?jǐn)?shù)據(jù)，得弱分類器x>3.5,則y=1;x<3.5,則y=-1。此時(shí)錯(cuò)誤率為0.1*3=0.3。若按4.5切分?jǐn)?shù)據(jù)，得弱分類器x<4.5,則y=1;x>4.5,則y=-1。此時(shí)錯(cuò)誤率為2*0.1=0.2。由于按4.5劃分?jǐn)?shù)據(jù)時(shí)錯(cuò)誤率最小為0.2x<4.5,則y=1;x>4.5,則y=-1。2.b計(jì)算最優(yōu)弱分類器的權(quán)重alpha=0.5*ln((1–0.2)/0.2)=0.6931。2.c更新樣本權(quán)重x=0,1,5時(shí)，y分類正確，則樣本權(quán)重為：0.1*exp(-0.6931)=0.05x=4時(shí)，y分類正確，則樣本權(quán)重為：0.5*exp(-0.6931)=0.25x=2,3時(shí)，y分類錯(cuò)誤，則樣本權(quán)重為：0.1*exp(0.6931)=0.20新樣本權(quán)重總和為0.05*3+0.25+0.20*2=0.8規(guī)范化后，x=0,1,5時(shí)，樣本權(quán)重更新為：0.05/0.8=0.0625x=4時(shí),樣本權(quán)重更新為：0.25/0.8=0.3125x=2,3時(shí),樣本權(quán)重更新為：0.20/0.8=0.250綜上，新的樣本權(quán)重為(0.0625,0.0625,0.250,0.250,0.3125,0.0625)。此時(shí)強(qiáng)分類器為G(x)=0.8047*G1(x)+0.6931*G2(x)。G1(x)為x<1.5,則y=1;x>1.5,則y=-1。G2(x)為x<4.5,則y=1;x>4.5,則y=-1。按G(x)分類會(huì)使x=4分類錯(cuò)誤，則強(qiáng)分類器的錯(cuò)誤率為1/6=0.167。7.2.3.第三輪迭代3.a選擇最優(yōu)弱分類器若按0.5切分?jǐn)?shù)據(jù)，得弱分類器x<0.5,則y=1;x>0.5,則y=-1。此時(shí)錯(cuò)誤率為0.0625+0.3125=0.375。若按1.5x<1.5,則y=1;x>1.5,則y=-11*0.3125=0.3125。若按2.5切分?jǐn)?shù)據(jù)，得弱分類器x>2.5,則y=1;x<2.5,則y=-1。此時(shí)錯(cuò)誤率為0.0625*2+0.250+0.0625=0.4375。若按3.5x>3.5,則y=1;x<3.5,則y=-10.0625*3=0.1875。若按4.5切分?jǐn)?shù)據(jù)，得弱分類器x<4.5,則y=1;x>4.5,則y=-1。此時(shí)錯(cuò)誤率為2*0.25=0.5。由于按3.5劃分?jǐn)?shù)據(jù)時(shí)錯(cuò)誤率最小為0.1875x>3.5,則y=1;x<3.5,則y=-1。3.b計(jì)算最優(yōu)弱分類器的權(quán)重alpha=0.5*ln((1–0.1875)/0.1875)=0.73323.c更新樣本權(quán)重x=2,3時(shí)，y分類正確，則樣本權(quán)重為：0.25*exp(-0.7332)=0.1201x=4時(shí)，y分類正確，則樣本權(quán)重為：0.3125*exp(-0.7332)=0.1501x=0,1,5時(shí)，y分類錯(cuò)誤，則樣本權(quán)重為：0.0625*exp(0.7332)=0.1301新樣本權(quán)重總和為0.1201*2+0.1501+0.1301*3=0.7806規(guī)范化后，x=2,3時(shí)，樣本權(quán)重更新為：0.1201/0.7806=0.1539x=4時(shí),樣本權(quán)重更新為：0.1501/0.7806=0.1923x=0,1,5時(shí),樣本權(quán)重更新為：0.1301/0.7806=0.1667綜上，新的樣本權(quán)重為(0.1667,0.1667,0.1539,0.1539,0.1923,0.1667)。此時(shí)強(qiáng)分類器為G(x)=0.8047*G1(x)+0.6931*G2(x)+0.7332*G3(x)。G1(x)為x<1.5,則y=1;x>1.5,則y=-1。G2(x)為x<4.5,則y=1;x>4.5,則y=-1。G3(x)為x>3.5,則y=1;x<3.5,則y=-1G(x)0/6=0終強(qiáng)分類器為G(x)=0.8047