1、機器學習之分類目錄機器學習之分類1分類模型與算法1分類算法相關簡介14.1.14.1.24.1.3分類1聚類、監督學習、非監督學習1分類應用-文本挖掘場景24.2 常見分類算法與模型44.2.11.2.21.2.31.2.41.2.54.2.64.2.7線性判別法4距離判別法5分類器7決策樹11組合算法19支持向量機(svm)25神經網絡254.分類模型與算法4.1 分類算法相關簡介4.1.1分類分類是一種重要的數據挖掘技術。分類的目的是根據數據集的特點構造一個分類函數或分類模型(也常稱作分類器)。該模型能把未知類別的樣本進行分類，把樣本信息分配給指定類別的一種技術。4.1.2 聚類、監督學習

2、、非監督學習監督學習：從得到的訓練集中“學習”，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常稱作 supervised learning 監督學習。聚類與非監督學習：聚類就是把相似的東西分到一組，聚類時并不關心某一類是什么，需要實現的目標只是把相似的東西聚到一起，因此一個聚類算法通常只需要知道相似度就可以工作了，因此通常不需要使用訓練數據進行學習，這在 Machine learning 中被稱作unsupervised learning 非監督學習。4.1.3 分類應用-文本挖掘場景(1) 網頁自動分類自動化門戶系統（搜素引擎根據用戶，谷歌等）類型推送不同類別的搜索結果(2)郵

3、件判斷(3)評論自動分析(4)通過用戶內容判別用戶喜好4.2 常見分類算法與模型4.2.1 線性判別法(1)線性判別法用一條直線來劃分學習集（這條直線不一定存在），然后根據待測點在直線的哪一邊決定它的分類。(2) 實例展示天氣預報數據 G=c(1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)#“1”下雨 “2”不下雨 x1=c(-1.9,-6.9,5.2,5.0,7.3,6.8,0.9,-12.5,1.5,3.8,0.2,-0.1,0.4,2.7,2.1,-4.6,-1.7,-2.6,2.6,-2.8) x2=c(3.2,0.4,2.0,2.5,0.0,12.7

4、,-5.4,-2.5,1.3,6.8,6.2,7.5,14.6,8.3,0.8,4.3,10.9,13.1,12.8,10.0)#x1 濕度 x2 溫度a=data.frame(G,x1,x2)plot(x1,x2)text(x1,x2,G,adj=-0.5)library(MASS)Id=lda(Gx1+x2)ld#線性判別函數 lda()z=predict(Id)newG=z$classy=cbind(G,z$x,newG)y1.2.2 距離判別法(1)原理計算待測點與各類的距離，取最短者為所屬分類(2) 馬氏距離和歐式距離1）馬氏距離：的方法。計算函數 mahalanobis（）。2）歐

5、式距離：一個通常采用的距離定義，它是在 m中兩個點之間的真實距離。3）為什么不用歐式距離：定義距離時，要考慮隨確量方差的信息，歐式距離4）馬氏距離定義8.1 設 x，y 是服從均值為，協方差陣為的總體 X 中抽取的樣本，則總體 X 內兩點 x與 y 的 Mahalanobis 距離（簡稱馬氏距離）定義為表示數據的協方差距離。它是一種有效的計算兩個未知樣本集的相似度定義樣本 x 與總體 X 的 Mahalanobis 距離為5）判別函數*情形一（p445）兩個總體 X1 和 X2 的協方差相同時，即要判斷 x 屬于哪個總體，比較 x 到總體 X1 和 X2 的馬氏距離的平方得到判別準則令稱 w（

6、x）為兩總體距離的判別函數，因此判別準則變為*情形二（p447）對于樣本 x，在協方差不同的情況下，判別函數為(2)最近鄰算法 Knn算法基本：存在一個待測樣本點 n，找出離它最近的 k 個樣本點，k 一般取奇數，此例 k=5，觀測這 5 個樣本點中哪一類的樣本多，則將此樣本點歸為那一類，此例中 2 類點多于 1 類點 3:2 所以將待測樣本歸為 2 類，這也就解釋了為什么 k 常取奇數的原因。1.2.3分類器(1)定理后驗概率：p(H|X)，在條件 X 下，H 發生的概率。X 代表包含某種特征特定的樣本，即給定觀測樣本數據，比如一封具體的垃圾郵件中包含詞匯“促銷”，則可將這封郵件看成是一個樣

7、本。H 是一個假設，比如假設這個郵件是一個郵件。P 表示概率，整個符號的意思通俗的解釋為，包含促銷這個詞的郵件是郵件的概率。先驗概率：p(H),H 發生的概率。(2)樸素分類樸素a)學習集（以郵件分類為例）名詞 x1名詞 x2名詞 x3等等郵件（100 封）正常（70 封）5（出現次數）5（）20（）對樣本進行分詞處理，把分出來的詞作為主要的特征（郵件的特征并不只是單純的依靠分出來的詞匯，有時也利用里面的其他特征，比如：是否包含的處理不限于分詞），此處舉例以分出來的詞作為判定的主要特征。等，因此對郵件計算公式X 中包含 X1，X2，X3 等詞，在計算 p(X|H)時沒有必要去把 X1，X2，X

8、3，在學習集共同出現的次數去統計。假設 X1，X2，X3 之間的出現是相互獨立，沒有聯系的則 P(X | H)=P(X1 | H)*P(X2 | H)*P(X3 | H) P(X)=P(X1)*P(X2)*P(X3)公式成立的前提是 X1,X2,X3,相互獨立，但事實有時并非如此，有時 X1，X2 同時出現，但為了降低計算量，只能降低一定的精度。這種假設的方式即樸素，上訴相乘只是近似處理段。b) 用戶流失電信運營戶案例通過對已經流失的或通過判定得知沒有流失的用戶提取一部分作為學習集，則可以總結出這些頻率出現的情況。上訴歸納的某些特征是對判定有價值的，但有些特征對判定是沒有價值的，沒有價值的變量

9、反映在流失與不流失的比例是大致相同的，此時可以剔除這一判定特征，提取那些統計意義特別明顯的特征，之后則可以利用這些特征，做一個類似于郵件判別的樸素斯分類器。通過公式計算擁有某些特征的測試樣本流失的可能性有多大。特征是否打過 10010話費是否減少話費暴漲.等等流失400（出現次數）500（出現次數）.不流失300（出現次數）500（出現次數）.（30 封）10（出現次數）10（）15（）c) 用戶系統例：運營商對用戶感的方面打1.2.獲得學習集利用公式計算，是者的可能性，是體育者的可能性，此時沒有必要選取最優的而排除其他的，可以設定一個值，例如 0.3，若高于 0.3 的可能性，則給該用戶打上

10、，若某用戶音樂、體育、的可能性都超過 0.3，則給該用戶打上 3 個。(3)信念網絡1）信念網絡分類器需要特征之間獨立的強條件，制約了模型的適用。樸素信念網絡是來說明聯合概率分布，它提供一種因果關系的圖形。2）定義*用有向無環圖表達變量之間的依賴關系，變量用節點表示，依賴關系用邊表示*祖先，父母和后代節點。網絡中的一個節點，如果它的父母節點已知，則它條件獨立于它的所有非后代節點（即沒有邊相連）*每個節點附帶一個條件概率表（CPT）表示該節點和父母節點的聯系概率3）CPT 計算特征是否在院打過在體育館打過節假日在外地大.等等體育旅游*如果節點x 沒有父母節點，則它的 CPT 中包含先驗概率 P（

11、x）*如果節點x 只有一個父母節點 y，則 CPT 中包含條件概率 P（x|y）*如果節點x 有多個父母節點 y1，y2.yk，則 CPT 中包含條件概率 P（x|y1，y2yk）先驗概率：指根據以往經驗和分析得到的概率。后驗概率：指通過或其他方式得到新信息，利用公式對先驗概率進行修正，而后得到的概率。4）展示其中鍛煉是心臟病的父母節點也稱雙親節點，血壓是心臟病的子代節點。飲食也是心臟病的雙親節點，所以節點的雙親節點不是唯一的。5）推理*從 CPT 中基于父母節點的條件概率推出某節點（變量）的概率*計算某節點基于后代節點的條件概率*計算某節點基于父母節點，后代節點的條件概率*其它非父母，非后代

12、節點與該節點本身是條件獨立的1.2.4 決策樹(1)決策樹決策樹是一個模型；他代表的是對象屬性與對象值之間的一種關系。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根 節點到該葉節點所經歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復數輸出，可以建立獨立的決策樹以處理不同輸出。例子：套用俗語，決策樹分類的類似于找對象。現想象一個的母親要給這個介紹男朋友，于是有了下面的：女兒：多大年紀了？母親：26。女兒：長的帥不帥？母親：挺帥的。女兒：收入高不？母親：不算很高，中等情況。女兒：是不？母親：是，在稅務局上班呢。女兒：那好，我去見見。這個的決策過程就是

13、典型的分類樹決策。相當于通過、長相、收入和是否公對的要求是：30 歲以下、長相務員對將分為兩個類別：見和不見。假設這個中等以上并且是高收入者或中等以上收入的，那么這個可以用下圖表示的決策邏輯：決策樹較為擅長處理離散的情形（因子變量），即每一個變量是由一些字符值來組成，而不是由一些連續的數值來組成。如果是連續的數值，最好先變成離散的，比一些連續的數值，最好把它們分為少、中、老幾個階段，這樣有利于高效率地構建一顆決策樹。(2) 決策樹算法的問題1）按什么樣次序來選擇變量（屬性）首先選擇一個信息含量比較大的變量（即信息增益最大的，信息增益后面有介紹），如 果該變量能達到經過一次分類解決全部問題最好，

14、或者選定該變量（屬性）后，某些分支能很快結束，然后再選擇其他分支做進一步的判斷。總的來說，需要一個合理的次序，來盡量使這顆樹最矮，這意味著計算效率的提高。2）最佳分離點的判定若是離散的變量，分離點即是它的離散值。若是連續變量，則需要給它確定最佳的分離點，此時選擇信息增益最大的點為分離點。例一些數據： 、 、 、將大于的分為一組，稱它也就是說，決策樹的簡單策略就是，好比公司招聘面試過程中篩選一個人的簡歷，如果你的條件相當好比如說某 985/211 重點大學博士畢業，那么二話不說，直接叫過來面試，如果非重點大學畢業，但實際項目經驗豐富，那么也要考慮叫過來面試一下，即所謂具體情況具體分析、決策。但每

15、一個未知的選項都是可以歸類到已有的分類類別中的。為“成年”變量，小于 20 的為“少年”變量。同樣取大于 15 的分為“成年”變量，小于15 的為“少年”變量。然后計算 15 和 20 這兩個點哪一個的增益值大，增益值大的點即為最佳分離點。(3) 決策樹學習之 ID3 算法1）簡介 ID3 算法（Iterative Dichotomiser 3 迭代二叉樹 3 代）是一個由 Ross Quinlan 發明的 用于決策樹的算法。越是小型的決策樹越優于大的決策樹。盡管如此，該算法也不是總是生成最小的樹形結構，而是一個啟發式算法。2）最佳分類屬性a)信息增益度量的標準：熵信息增益(Informati

16、on Gain)是用來衡量給定的屬性區分訓練樣例的能力，而 ID3 算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性。為了精確地定義信息增益，先定義信息論中廣泛使用的一個度量標準，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關于某個目標概念的正反樣例的樣例集 S，那么 S 相對這個型分類的熵為：上述公式中，p+代表正樣例而 p-則代表反樣例(在有關熵的所有計算中定義 0log0為 0)。b)信息增益計算D 為總體樣本，Dj 為一種類別的樣本總數，pi 表示正例或反例占樣本的比例。信息增益計算例子：訓練數據期待輸出的結果：計算結果：Age 屬性的信息增益最高，

17、故先選擇這個變量3）缺點ID3 算法傾向于首先選擇因子數較多的變量，這樣有時會確。(4) ID3 算法的改進：C4.5 算法1）改進信息增益方法傾向于首先選擇因子數較多的變量，所以采用增益率來判別。一般來說率就是用來取平衡用的，就像方差起的作用差不多，比兩個跑步的人，一個起點是 10m/s樣的加速度。因此，C4.5 克服了 ID3 用信息增益選擇屬性時偏向選擇取值多的屬性的。2）增益率公式：增益率=信息增益/值 (信息用來衡量屬性數據的廣度和均勻)（增益率）（值）(5) CART 算法1）使用基尼指數選擇變量公式：基尼指數：總體內包含的類別越雜亂，GINI 指數就越大（跟熵的概念很相似）。比如

18、體溫為恒溫時包含哺乳類 5 個、鳥類 2 個，則：（基尼指數）2）剪枝當分類回歸樹劃分得太細時，會對噪聲數據產生過擬合作用。因此要通過剪枝來解決。剪枝又分為前剪枝和后剪枝。前剪枝：前剪枝是指在構造樹的過程中就知道哪些節點可以剪掉。后剪枝：指構造出完整的決策樹之后再來考查哪些可以剪掉。的人、其 10s 后為 20m/s；另一個人起速是 1m/s、其 1s 后為 2m/s。如果緊緊算差值那么兩個差距就很大了，如果使用速度增加率(加速度，即都是為 1m/s2)來衡量，2 個人就是一因為剪下去的這棵的葉子節點有兩個類 B，所以剪完 A1 的右孩子為類 B。剪枝判斷方法在分類回歸樹中可以使用的后剪枝方法

19、有多種，比如：代價復雜性剪枝、最小誤差剪枝、悲觀誤差剪枝等等。這里只介紹代價復雜性剪枝法。代價復雜度：葉節點個數（裁剪對象）和樹的錯誤率的函數如果剪枝能使代價復雜度下降，則實施之。對于分類回歸樹中的每一個非葉子節點計算它的表面誤差率增益值 。是中包含的葉子節點個數;是節點 t 的誤差代價，如果該節點被剪枝;r(t)是節點 t 的誤差率;p(t)是節點 t 上的數據占所有數據的比例。是 Tt 的誤差代價，如果該節點不被剪枝。它等于 Tt 上所有葉子節點的誤差代價之和。比個非葉子節點 t4：已知所有的數據總共有 60 條，則節點 t4 的節點誤差代價為：誤差代價為：以 t4 為根節點的上葉子節點有

20、 3 個，最終：找到 值最小的非葉子節點，令其左右孩子為 NULL。當多個非葉子節點的 值同時(6) R 語言實現決策樹以鳶尾花數據集作為算例說明：library(rpart) #加載 rpart 包iris.rp = rpart(Species., data=iris, method=class)plot(iris.rp, uniform=T, branch=0, margin=0.1, main= Classification TreenIris Species by Petal and Sepal Length)text(iris.rp, use.n=T, fancy=T, col=bl

21、ue)最大的進行剪枝。達到最小時，取(7) 評估分類器效能TP、FP、TN、FN、T、P 分別代表：真正例、真負例、假正例、假負例、正和負樣本數。1.2.5 組合算法(1) 基本思路擁有一個總體樣本 D，通過對樣本進行抽樣，產生很多不同的樣本子集，即學習集，這些子集分別為 D1、D2、D3.Dk，k 個不同的子集。每個子集可能有交集，一模一樣的可能性很低。、支持向量機、決策樹等）分別對 Di 進行建模，形成用一種分類器算法（M1、M2.Mk 個分類器。把待測樣本分別投入這些分類器中，測出 k 個結果：yes or no 。通過簡單表決，看哪一種分類器選得最多。比選 yes。900 個分類器，5

22、00 個選 yes，400 個選 no，則最終結果總結：*基于學習數據集抽樣產生若干訓練集（對總體樣本 D 抽樣，的到若干樣本子集 Di）*使用訓練集產生若干分類器（每個子集訓練出一個分類器）*每個分類器分別進行，通過簡單多數，判定最終所屬分類（分類器最多的分類方法，選為最終的分類）(2）為什么組合方法能提高分類準確率？兩個圖對比左圖將實際的邊界通過一條直線來分類，顯然分類的準確率不高，然而右圖中，將所有的邊界組合起來，越多的分類器組合，邊界越像一條曲線，這樣明顯看出準確率的提高。(3)問題在原始數據集 D 中，通過隨機抽樣產生 K 個子學習集，如何抽樣？抽樣的方法是什么？數據被抽樣出來后形成

23、新的學習集，分類器如何把新的學習集訓練出來呢？采用什么樣的算比較好呢？(4) 組合方法的優勢a) 能明顯判別準確率對誤差和噪音更加魯棒性（健壯性）一定程度抵消過度擬合適合并行化計算(5) 重要的組合算法a)裝袋算法-bagging1.算法：裝袋為學習方案創建組合分類模型，其中每個模型給出等權重。2.偽代碼：輸入：*D：d 個分類元組的集合；（將總體樣本 D 抽出 d 個樣本子集）*k：組合分類器中的模型個數（用分類算法訓練出 k 個模型）*一種學習方案（例如：決策樹算法，向后等）輸出：組合分類器復合模型 M*方法：for i=1 to k do/創建k 個模型通過對 D 有放回抽樣，創建自助樣

24、本 Di（有放回抽樣就是抽完把它放回去，目的使每次抽樣條件獨立自助樣本是采用有放回抽樣方法得到的樣本，樣本數和總樣本數相同，可以有重復的樣本，是一種比較規范段）使用 Di 和學習方法導出模型 M（i 可以使用線性判別、決策樹等分類算法）Endfor使用組合分類器對元組 X 進行分類，讓 k 個模型都對元組 X 分類，并返回多數表決。3.基本思路：對樣本空間 D 進行 放回抽樣，得到樣本空間的一個子集 Di，由 Di 得到一個分類 器 Mi。不斷的重復上述過程，就可以得到一系列分類器 M1,M2,M3.Mi ，在分類時用這些分類器進行投票來決定分類。優勢：準確率明顯高于組合中任意一個分類器對于較

25、大的噪音， 表現不至于很差，并且具有魯棒性不容易過度擬合5.在 R 中實現library(ipred) #bagging 函數需要安裝的程序包m.bag=bagging(Species.,data=iris)m.bagbag.pre=predict(mplot(bag.pre).bag,iris)(boosting)算法b)1.算法基本(1)(2)(3)訓練集中的元組被分配權重（權重：權利的大小）權重影響抽樣，權重越大越可能被抽中迭代訓練若干個分類器一個分類器中被錯誤分類的元組，會被提高權重，使到它在后面建立的分類器中被更加“關注”（之前被分錯的先被分類）(4)最后分類也是有所有分類器投票，投

26、票權重取決于分類器的權重解釋：在抽樣時不會隨機抽樣，它會每一個加一個權重，如果某個在分類器里被正確判斷了，那它的權重就會降低；越靠后形成的分類器，它們訓練的更傾向于在早前誤判的那些，就是說如果有一些樣本在早期的分類器里被判錯了，那之后就會重點針對這些錯誤的數據進行判斷；除了訓練過程特別關注之外，最后作分類的時候也不是簡單的投票，通過學習集可以算出每一個分類器的準確率大概有多少，投票權重跟分類器準確率有關，二者成正比。2.adaboost 算法算法：Adaboost 一種偽代碼：方法：算法創建分類器的組合。每個給出一個投票將 D 中每個元組的權重初始化為 1/d（每個元組的權重都是 1/d）Fo

27、r i=1tokdo / 對于每一輪（從 1 到k，k 次循環）(3) 根據元組的權重從 D 中有放回抽樣，得到 Di (4)使用訓練集 Di 導出模型 Mi計算Mi 的錯誤率 error（Mi）If error（Mi）0.5 then （如果錯誤率大于 0.5 就回到步驟三，重新抽樣）轉步驟（3）重試EndifFor Di 的每個被正確分類的元組 do（如果都被正確分組，則停止循環）(10) 元組的權重乘以 error（Mi）/（1- error（Mi） (11)規范化每個元組的權重(12) Endfor部分偽代碼解釋：/更新權重d 為 D 中的個數；循環k 次，每一次都會創建一個分類器；從 D 中根據權重有放回抽樣的到一個學習集 Di，不只是有放回抽樣還跟權重有關系，權重越大的樣本越有可能被抽到；用新的學習集 Di 利用分類器（決策樹，（分類器）；等任一組）得到模型 Mi權重變化：每