數(shù)據(jù)挖掘分類

1、.1 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提要 n分類的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n實值預(yù)測 n與分類有關(guān)的問題 .2 分類的流程 n根據(jù)現(xiàn)有的知識，我們得到了一些關(guān)于爬行動物和鳥類的信息， 我們能否對新發(fā)現(xiàn)的物種，比如動物A，動物B進行分類？ 動物種動物種 類類 體型體型翅膀數(shù)量翅膀數(shù)量腳的只數(shù)腳的只數(shù)是否產(chǎn)蛋是否產(chǎn)蛋是否有毛是否有毛類別類別 狗中04否是爬行動物 豬大04否是爬行動物 牛大04否是爬行動物 麻雀小22是是鳥類 天鵝中22是是鳥類 大雁中22是是鳥類 動物A大02是無？ 動物B中22否是？ .3 分類的流程 n步驟一：將樣本

2、轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提?。?n所有樣本必須具有相同數(shù)量的特征 n兼顧特征的全面性和獨立性 動物種動物種 類類 體型體型翅膀數(shù)量翅膀數(shù)量腳的只數(shù)腳的只數(shù)是否產(chǎn)蛋是否產(chǎn)蛋是否有毛是否有毛類別類別 狗中04否是爬行動物 豬大04否是爬行動物 牛大04否是爬行動物 麻雀小22是是鳥類 天鵝中22是是鳥類 大雁中22是是鳥類 .4 分類的流程 n步驟二：選擇與類別相關(guān)的特征（特征選擇）。 n比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰 色代表完全無關(guān) 動物種動物種 類類 體型體型翅膀數(shù)量翅膀數(shù)量腳的只數(shù)腳的只數(shù)是否產(chǎn)蛋是否產(chǎn)蛋是否有毛是否有毛類別類別 狗中0 04 4否否是爬行動物 豬大0

3、 04 4否否是爬行動物 牛大0 04 4否否是爬行動物 麻雀小2 22 2是是是鳥類 天鵝中2 22 2是是是鳥類 大雁中2 22 2是是是鳥類 .5 分類的流程 n步驟三：建立分類模型或分類器（分類）。 n分類器通常可以看作一個函數(shù)，它把特征映射到類的空間 上 iiniiiyxxxxf),.,(321 .6 如何避免過度訓(xùn)練 n分類也稱為有監(jiān)督學習(supervised learning), 與之相對于的是無監(jiān)督學習(unsupervised learning),比如聚類。 n分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一 部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。 n建立分類模型需要學習一部分

4、已知數(shù)據(jù)，如果 訓(xùn)練時間過長，或者預(yù)測模型參數(shù)太多而樣本 較少，將導(dǎo)致過度訓(xùn)練(overfitting)。 .7 如何避免過度訓(xùn)練 n避免過度訓(xùn)練最重要一點是，模型的參數(shù)量應(yīng) 遠小于樣本的數(shù)量。 n應(yīng)建立訓(xùn)練集(training set)和測試集(test set)。 n訓(xùn)練集應(yīng)用于建立分類模型 n測試集應(yīng)用于評估分類模型 nK折疊交叉驗證(K-fold cross validation)：將初始 采樣分割成K個子樣本(S1，S2,.,Sk)，取K-1個做 訓(xùn)練集，另外一個做測試集。交叉驗證重復(fù)K次， 每個子樣本都作為測試集一次，平均K次的結(jié)果， 最終得到一個單一估測。 .8 分類模型的評估

5、n真陽性(T True P Positive)： 實際為陽性 預(yù)測為陽性 n真陰性(T True NNegative)：實際為陰性 預(yù)測為陰性 n假陽性(F False P Positive)： 實際為陰性 預(yù)測為陽性 n假陰性(F False NNegative)：實際為陽性 預(yù)測為陰性 n預(yù)測是否正確 預(yù)測結(jié)果 n比如預(yù)測未知動物是鳥類還是爬行動物，陽性代表爬 行動物，陰性代表非非爬行動物，請大家闡述 TP=10， TN=8，F(xiàn)N=3，F(xiàn)P=2是什么意義 .9 分類模型的評估 n靈敏度(Sensitivity)： TP/(TP+FN) n也稱為查全率(Recall) n數(shù)據(jù)集共有13只爬行

6、動物，其中10只被正確預(yù)測為爬行動物， 靈敏度為10/13 n特異度(Specificity): TN/(TN+FP) n數(shù)據(jù)集有10只非爬行動物，其中8只被預(yù)測為非爬行動物，特 異度為8/10 n精度(Precision): TP/(TP+FP) n分類器預(yù)測了12只動物為爬行動物，其中10只確實是爬行動 物，精度為10/12 n準確率(Accuracy): (TP+TN)/(TP+TN+FN+FP) n數(shù)據(jù)集包含23只動物，其中18只預(yù)測為正確的分類，準確率 為18/23 .10 分類模型的評估 n對于非平衡(unblanced)的數(shù)據(jù)集,以上指標并不能很好的 評估預(yù)測結(jié)果。 n非平衡的數(shù)

7、據(jù)集是指陽性數(shù)據(jù)在整個數(shù)據(jù)集中的比例很 小。比如，數(shù)據(jù)集包含10只爬行動物，990只爬行動物， 此時，是否預(yù)測正確爬行動物對準確率影響不大。 n更平衡的評估標準包括馬修斯相關(guān)性系數(shù)(Matthews correlation coefficient)和ROC曲線。 n馬修斯相關(guān)性系數(shù)定義為 .11 分類模型的評估 nROC曲線通過描述真陽性率(TPR)和假陽性率(FPR)來實 現(xiàn)，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。 n大部分分類器都輸出一個實數(shù)值(可以看作概率),通過變 換閾值可以得到多組TPR與FPR的值。 .12 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提

8、要 n分類的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n實值預(yù)測 n與分類有關(guān)的問題 .13 基于距離的分類算法的思路 n定義定義4-2 4-2 給定一個數(shù)據(jù)庫給定一個數(shù)據(jù)庫 D D=t t1 1，t t2 2，t tn n 和一和一 組類組類C C=C C1 1，C Cm m 。假定每個元組包括一些數(shù) 。假定每個元組包括一些數(shù) 值型的屬性值：值型的屬性值：t ti i=t ti1 i1，t ti2 i2， ，t tik ik ，每個類也包，每個類也包 含數(shù)值性屬性值：含數(shù)值性屬性值：C Cj j=C Cj1 j1，C Cj2 j2， ，C Cjk jk ，則分，則

9、分 類問題是要分配每個類問題是要分配每個t ti i到滿足如下條件的類到滿足如下條件的類C Cj j： simsim( (t ti i，C Cj j)=)=simsim( (t ti i，C Cl l) ) ， C Cl lC C，C Cl lC Cj j， 其中其中simsim( (t ti i，C Cj j) )被稱為相似性。被稱為相似性。 n在實際的計算中往往用在實際的計算中往往用距離距離來表征，距離越近，來表征，距離越近， 相似性越大，距離越遠，相似性越小。相似性越大，距離越遠，相似性越小。 n距離的計算方法有多種，最常用的是通過計算每距離的計算方法有多種，最常用的是通過計算每 個類的

10、中心來完成。個類的中心來完成。 .14 基于距離的分類算法的一般性描述 n算法 4-1通過對每個樣本和各個類的中心來比較， 從而可以找出他的最近的類中心，得到確定的類 別標記。 算法算法 4-1 基于距離的分類算法 輸入：每個類的中心C1，Cm；待分類的元組t。 輸出：輸出類別c。 （1）dist=；/距離初始化 （2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN （4）c i； （5）distdist(ci，t)； （6） END. .15 基于距離的分類方法的直觀解釋 （a）類定義 （b）待分類樣例（c）分類結(jié)果 .16 距離分類例題 n

11、C1=(3,3,4,2), C2=(8,5,-1,-7), C3=(-5,-7,6,10); 請用基于距離的算法給以下樣本分類： (5,5,0,0) (5,5,-5,-5) (-5,-5,5,5) .17 K-近鄰分類算法 nK-近鄰分類算法（K Nearest Neighbors，簡稱KNN）通過 計算每個訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組 距離最近的K個訓(xùn)練數(shù)據(jù)，K個數(shù)據(jù)中哪個類別的訓(xùn)練數(shù)據(jù) 占多數(shù)，則待分類元組就屬于哪個類別。 算法算法 4-2 K-近鄰分類算法近鄰分類算法 輸入：輸入： 訓(xùn)練數(shù)據(jù)訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目；近鄰數(shù)目K；待分類的元組；待分類的元組t。 輸出：輸出： 輸出

12、類別輸出類別c。 （1）N= ； （2）FOR each d T DO BEGIN （3） IF |N|K THEN （4） N=N d； （5） ELSE （6） IF u N such that sim(t，u)sim(t，d) THEN BEGIN （7） N=N - u； （8） N=N d； （9） END （10）END （11）c=class to which the most u N. .18 KNN的例子 姓名 性別 身高(米) 類別 Kristina女 1.6 矮 Jim 男 2高 Maggie 女 1.83高 Martha 女 1.88高 Stephanie女 1.7矮

13、Bob 男 1.85中等 Kathy 女 1.6矮 Dave 男 1.7矮 Worth 男 2.2高 Steven 男 2.1高 Debbie 女 1.8高 Todd 男 1.82中等 Kim 女 1.7中等 Amy 女 1.75中等 Wynette 女 1.73中等 n只使用身高做特征， K=3，對于樣本 應(yīng) 屬于哪個類別？ n僅使用同性別樣本 做訓(xùn)練，K=3，對 于樣本應(yīng)屬于哪個類 別？ .19 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提要 n分類的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n實值預(yù)測 n與分類有關(guān)的問題 .20 決策樹表示與例子 年齡年齡收

14、收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 40中否一般是是 40低是一般是是 40低是良好否否 3040低是良好是是 =30中否一般否否 =30低是一般是是 年齡年齡？ 學生學生？是是信用信用？ 40 否是良好 一般 是是否否是是否否 .21 決策樹表示與例子 n決策樹（Decision Tree）的每個內(nèi)部結(jié)點表示一 個屬性（特征），每個分枝代表一個特征的一個 （類）取值； n每個樹葉結(jié)點代表類或類分布。 n決策樹分類方法采用自頂向下的遞歸方式，在決 策樹的內(nèi)部結(jié)點進行屬性的比較，從而判斷從該 結(jié)點向下的分枝，在決策樹的葉結(jié)點得到結(jié)論。 n從決策樹的根到葉結(jié)點

15、的一條路徑就對應(yīng)著一條 規(guī)則，整棵決策樹就對應(yīng)著一組規(guī)則。 n決策樹分類模型的建立通常分為兩個步驟： n決策樹生成 n決策樹修剪 .22 決策樹生成算法描述 算法 4-3 Generate_decision_tree(samples, attribute_list) /* 決策樹生成算法*/ 輸入：訓(xùn)練樣本samples，由離散值屬性表示；輸出：一棵決策樹。 （1） 創(chuàng)建結(jié)點N； （2） IFIF samples 都在同一個類C THENTHEN 返回N 作為葉結(jié)點，以類 C標記； （3） IFIF attribute_list為空 THENTHEN 返回N作為葉結(jié)點，標記為samples中最

16、 普通的類；/多數(shù)表決 （4） 選擇attribute_list中具有最高信息增益的屬性test_attribute； （5） 標記結(jié)點N為test_attribute； （6） FORFOR test_attribute的每個取值ai 由結(jié)點N長出一個條件為 test_attribute=ai的分枝； （7）設(shè)si是samples 中test_attribute =ai的樣本的集合；/一個劃分 （8）IFIF si 為空 THENTHEN 回退到test_attribute的其它取值； （9）ELSEELSE 加上一個由Generate_decision_tree(si， attribute

17、_list- test_attribute)返回的結(jié)點； .23 決策樹修剪算法 n基本的決策樹構(gòu)造算法沒有考慮噪聲，因此生成 的決策樹完全與訓(xùn)練集擬合。在有噪聲情況下， 將導(dǎo)致過分擬合（Overfitting），即對訓(xùn)練數(shù)據(jù)的 完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預(yù)測性能下降。 n比如每個樣本都是一個葉子節(jié)點。 n現(xiàn)實世界的數(shù)據(jù)一般不可能是完美的，可能缺值 （Missing Values）；數(shù)據(jù)不完整；含有噪聲甚至 是錯誤的。 n剪枝是一種克服噪聲的基本技術(shù)，同時它也能使 樹得到簡化而變得更容易理解。有兩種基本的剪 枝策略。 .24 決策樹修剪算法 n預(yù)先剪枝（Pre-Pruning）：在生成樹的

18、同時決定 是繼續(xù)對不純的訓(xùn)練子集進行劃分還是停機。 n后剪枝（Post-Pruning）：是一種擬合+化簡 （fitting-and-simplifying）的兩階段方法。首先生 成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹 的葉子開始剪枝，逐步向根的方向剪。剪枝時要 用到一個測試數(shù)據(jù)集合（Tuning Set或Adjusting Set），如果存在某個葉子剪去后能使得在測試集 上的準確度或其他測度不降低（不變得更壞）， 則剪去該葉子；否則停機。理論上講，后剪枝好 于預(yù)先剪枝，但計算復(fù)雜度大。 .25 決策樹修剪算法 n構(gòu)造好的決策樹的關(guān)鍵在于如何選擇屬性進行樹 的拓展。研究結(jié)果表明，一般情況下

19、,樹越小則樹 的預(yù)測能力越強。由于構(gòu)造最小的樹是NP-難問題， 因此只能采取用啟發(fā)式策略來進行。 n屬性選擇依賴于各種對例子子集的不純度 （Impurity）度量方法，包括信息增益 （Informatin Gain）、信息增益比（Gain Ratio）、 Gini-index、距離度量（Distance Measure）、J- measure等。 .26 ID3算法 nID3是一個著名決策樹生成方法： n決策樹中每一個非葉結(jié)點對應(yīng)著一個非類別屬性(特征)， 樹枝代表這個屬性的值。一個葉結(jié)點代表從樹根到葉結(jié) 點之間的路徑對應(yīng)的記錄所屬的類別屬性值。 n每一個非葉結(jié)點都將與屬性中具有最大信息量的非

20、類別 屬性相關(guān)聯(lián)。 n采用信息增益來選擇能夠最好地將樣本分類的屬性。 n對ID3算法采用如下方式講解： n給出信息增益對應(yīng)的計算公式； n通過一個例子來說明它的主要過程。 .27 信息增益的計算 n設(shè)S是s個數(shù)據(jù)樣本的集合，定義m個不同類Ci（i=1，2， m），設(shè)si是Ci類中的樣本的數(shù)量。對給定的樣本S所期望 的信息值由下式給出： 其中pi是任意樣本屬于Ci的概率： si / s 。 例題：數(shù)據(jù)集有4個類，分別有8個，4個，2個，2個樣本， 求該數(shù)據(jù)集的信息值。 問題：信息值的取值范圍是什么？ m i iim ppsssI 1 221 )(log),.,( .28 信息增益的計算 例題：數(shù)

21、據(jù)集有2個類，求該 數(shù)據(jù)集的信息值。 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 40中是良好是是 40低是良好是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是良好是是 .29 信息增益的計算 n設(shè)屬性A具有個不同值a1, a2, , av ，可以用屬性A將樣本 S劃分為 S1, S2, , Sv ，設(shè)Sij 是Sj中Ci類的樣本數(shù)，則由A 劃分成子集的熵由下式給出： n有A進行分枝將獲得的信息增益可以由下面的公式得到： )s,.,s( I s s.s E(A)mjj v j mjj 1 1 1 E(A)s,.,s ,I(s

22、Gain(A)m21 使用屬性 后的信息值 未使用屬性 的信息值 .30 信息增益的計算 例題：數(shù)據(jù)集有2個類。 使用是否學生作為屬性，求 該屬性的信息增益。 使用信用狀況作為屬性，求 該屬性的信息增益。 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 40中是良好是是 40低是良好是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是良好是是 .31 ID3算法的例子 n選擇信息增益最大的屬性特征作為根節(jié)點。 nGain(年齡)=0.342 Gain(收入)=0 nGain(是否學生)=0.333 Gain(信用狀況)=0 年齡年齡

23、收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 40中是一般是是 40低是一般是是 =30低是良好否否 3040低是良好否否 =30中否良好否否 =30低是一般是是 年齡年齡？ ？是是 40 .32 ID3算法的例子 n對于=30的分支 nGain(收入)=0.315 Gain(是否學生)=0.315 Gain(信用狀況)=0.815 n對于30 40的分支 nGain(收入)=1 Gain(是否學生)=0 Gain(信用狀況)=1 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 =30高否良好否否 =30中否良好否否 =30低是

24、一般是是 =30低是良好否否 3040低是良好否否 3040 高是一般是 年齡？年齡？ 信用狀況？信用狀況？收入？收入？是是 40 否否是是是是否否 良好一般高低 .33 ID3算法的性能分析 nID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬 性的有限離散值函數(shù)的一個完整空間。 nID3算法在搜索的每一步都使用當前的所有訓(xùn)練樣例，大 大降低了對個別訓(xùn)練樣例錯誤的敏感性。因此，通過修改 終止準則，可以容易地擴展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。 .34 ID3算法的性能分析 nID3算法在搜索過程中不進行回溯。所以，它易受無回溯 的爬山搜索中的常見風險影響：收斂到局部最優(yōu)而不是全 局最優(yōu)。 nID

25、3算法只能處理離散值的屬性。 n信息增益度量存在一個內(nèi)在偏置，它偏袒具有較多值的屬 性。例如，如果有一個屬性為日期，那么將有大量取值， 這個屬性可能會有非常高的信息增益。假如它被選作樹的 根結(jié)點的決策屬性則可能形成一顆非常寬的樹，這棵樹可 以理想地分類訓(xùn)練數(shù)據(jù)，但是對于測試數(shù)據(jù)的分類性能可 能會相當差。 nID3算法增長樹的每一個分支的深度，直到屬性的使用無 法導(dǎo)致信息增益。當數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少 時，產(chǎn)生的樹會過渡擬合訓(xùn)練樣例。 n問題：ID3樹可以導(dǎo)致過度擬合，那是否它一定能對訓(xùn)練 集完全正確的分類呢？ .35 C4.5算法對ID3的主要改進 nC4.5算法是從ID3算法演變而

26、來，除了擁有ID3算 法的功能外，C4.5算法引入了新的方法和增加了 新的功能： n用信息增益比例的概念； n合并具有連續(xù)屬性的值； n可以處理具有缺少屬性值的訓(xùn)練樣本； n通過使用不同的修剪技術(shù)以避免樹的過度擬合； nK交叉驗證； n規(guī)則的產(chǎn)生方式等。 .36 信息增益比例的概念 n信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來 的，一個屬性的信息增益比例用下面的公式給出： 其中 假如我們以屬性A的值為基準對樣本進行分割的化， Splitl(A)就是前面熵的概念。 )( )( )( ASplitI AGain AGainRatio )(log)( 1 2j v j j ppASplitI .37

27、 信息增益比例的計算 例題：數(shù)據(jù)集有2個類。 使用是否學生作為屬性，求 該屬性的信息增益比例。 使用年齡作為屬性，求該屬 性的信息增益比例。 討論：信息增益和信息增益 比例的差異在哪里？ 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 80低是良好是是 .38 C4.5處理連續(xù)值的屬性 n對于連續(xù)屬性值，C4.5其處理過程如下： n根據(jù)屬性的值，對數(shù)據(jù)集排序； n用不同的閾值將數(shù)據(jù)集動態(tài)的進行劃分； n取兩個實際值中的中點作為一個閾值； n取兩個劃分，所有樣本都在這兩個劃分中； n得到所有可能的閾值、增益及增益比； n在每一個屬性會變?yōu)槿蓚€取值，即小于閾值

28、或大于等 于閾值。 n簡單地說，針對屬性有連續(xù)數(shù)值的情況，則在訓(xùn)練集中可 以按升序方式排列。如果屬性A共有n種取值，則對每個取 值vj（j=1，2，n），將所有的記錄進行劃分：一部分 小于vj；另一部分則大于或等于vj 。針對每個vj計算劃分 對應(yīng)的增益比率，選擇增益最大的劃分來對屬性A進行離 散化 。 .39 C4.5處理連續(xù)值的屬性 例題：使用C4.5算法將連續(xù)的屬性(收入) 轉(zhuǎn)化為離散的類。 n根據(jù)屬性的值，對數(shù)據(jù)集排序； n取兩個實際值中的中點作為一個閾值； n取兩個劃分，所有樣本都在這兩個劃分中； n得到所有可能的閾值、增益及增益比； n在每一個屬性會變?yōu)槿蓚€取值，即小于閾值或 大

29、于等于閾值。 收入收入是否買是否買 電腦電腦 2500否否 3000否否 3200否否 4050否否 4865是是 6770是是 9800是是 12000是是 .40 C4.5處理連續(xù)值的屬性 例題：使用C4.5算法將連續(xù)的屬性 (收入)轉(zhuǎn)化為離散的類。 n選擇增益最大的劃分來對屬性A進行離散 化 。 nGainRatio(劃分：2750)=0.2 nGainRatio(劃分：3100)=0.39 nGainRatio(劃分：3625)=0.53 nGainRatio(劃分：4458)=1 nGainRatio(劃分：？)=0.53 nGainRatio(劃分：8285)=0.39 nGain

30、Ratio(劃分：10900)=0.2 n收入小于4458合并為收入低 n收入大于等于4458合并為收入高 收入收入是否買是否買 電腦電腦 收入（離收入（離 散化）散化） 2500否 3000否 3200否 4050否 4865是 6770是 9800是 12000是 .41 C4.5的其他處理 nC4.5處理的樣本中可以含有未知屬性值，其處理 方法是用最常用的值替代或者是將最常用的值分 在同一類中。 n具體采用概率的方法，依據(jù)屬性已知的值，對屬性和每 一個值賦予一個概率，取得這些概率，取得這些概率依 賴于該屬性已知的值。 n規(guī)則的產(chǎn)生：規(guī)則的產(chǎn)生：一旦樹被建立，就可以把樹轉(zhuǎn)換成 if-the

31、n規(guī)則。 n規(guī)則存儲于一個二維數(shù)組中，每一行代表樹中的一個規(guī) 則，即從根到葉之間的一個路徑。表中的每列存放著樹 中的結(jié)點。 .42 C4.5算法例子 樣本數(shù)據(jù) 天氣溫度濕度風網(wǎng)球 SunnyHot85falseNo SunnyHot90trueNo Overcast Hot78falseYes RainMild96falseYes RainCool80falseYes RainCool70trueNo Overcast Cool65trueYes SunnyMild95falseNo SunnyCool70falseYes RainMild80falseYes SunnyMild70trueY

32、es Overcast Mild90trueYes Overcast Hot75falseYes RainMild80trueNo （1）首先對濕度濕度進行屬性離散 化，針對上面的訓(xùn)練集合，通過 檢測每個劃分而確定最好的劃分 在75處，則這個屬性的范圍就變 為（75）。 （2）計算目標屬性打網(wǎng)球打網(wǎng)球分類 的期望信息： （3）計算每個屬性的GainRatio： 940. 0 14 5 log 14 5 14 9 log 14 9 )5 , 9(),( 2221 IssI 0.0483 )GainRatio( 0.0248 )GainRatio( 049. 0)(GainRatio 156. 0

33、 577. 1 2467. 0 )(GainRatio 濕度 ；溫度 ；風 ；天氣 .43 C4.5算法例子 （4）選取最大的GainRatio，根 據(jù)天氣天氣的取值，得到三個分 枝。 （5）再擴展各分枝節(jié)點，得到 最終的決策樹（見課本圖4- 7 ）。 問題：就天氣=Sunny這一分支， 請用C4.5算法構(gòu)造決策樹。 樣本數(shù)據(jù) 天氣溫度濕度風網(wǎng)球 SunnyHot85falseNo SunnyHot90trueNo SunnyMild95falseNo SunnyCool70falseYes SunnyMild70trueYes .44 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提要 n分類

34、的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n實值預(yù)測 n與分類有關(guān)的問題 .45 貝葉斯分類 n定義定義4-3 4-3 設(shè)設(shè)X X是類標號未知的數(shù)據(jù)樣本。設(shè)是類標號未知的數(shù)據(jù)樣本。設(shè)H H為某種假定，為某種假定， 如數(shù)據(jù)樣本如數(shù)據(jù)樣本X X屬于某特定的類屬于某特定的類C C。對于分類問題，我們希望。對于分類問題，我們希望 確定確定P(H|X)P(H|X)，即給定觀測數(shù)據(jù)樣本，即給定觀測數(shù)據(jù)樣本X X，假定，假定H H成立的概率。成立的概率。 貝葉斯定理給出了如下計算貝葉斯定理給出了如下計算P(H|X)P(H|X)的簡單有效的方法的簡單有效的方法: : nP(X |

35、H)P(X |H)代表假設(shè)代表假設(shè)H H成立的情況下，觀察到成立的情況下，觀察到X X的概率。的概率。P(H| P(H| X )X )是是后驗概率后驗概率，或稱為，或稱為X X發(fā)生后觀測到發(fā)生后觀測到H H的的條件概率條件概率。 n例如，假定數(shù)據(jù)樣本由一些人組成，假定例如，假定數(shù)據(jù)樣本由一些人組成，假定X X表示頭發(fā)顏色，表示頭發(fā)顏色，H H表示表示 膚色，則膚色，則P(H|X)P(H|X)反映當我們看到反映當我們看到X X是黑色時，我們對是黑色時，我們對H H為黃色的確為黃色的確 信程度。信程度。 )( )()|( )( )( )|( XP HPHXP XP XHP XHP .46 樸素貝葉

36、斯分類的工作原理 n觀測到的樣本具有屬性 收入低 是學生 信用良好 n現(xiàn)在的問題相當于比較兩 個條件概率的大小 P(買電腦|收入低,是學生, 信 用良好) P(不買電腦|收入低,是學生, 信用良好) 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否良好否否 低否良好否否 中否良好否否 低是良好？ .47 樸素貝葉斯分類 樸素貝葉斯分類的工作過程如下：樸素貝葉斯分類的工作過程如下： n(1) 每個數(shù)據(jù)樣本用一個n維特 征向量X= x1，x2，xn表 示，分別描述對n個屬性A 1， A2，An樣本的n個度量。

37、n(2) 假定有m個類C1，C2， Cm，給定一個未知的數(shù)據(jù)樣本X （即沒有類標號），分類器將 預(yù)測X屬于具有最高條件概率 （條件X下）的類。 n也就是說，樸素貝葉斯分類將 未 知 的 樣 本 分 配 給 類 C i （1im）當且僅當P(Ci|X) P(Cj|X)，對任意的j=1，2， m，ji。 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否良好否否 低否良好否否 中否良好否否 低低是是良好良好？ .48 樸素貝葉斯分類(續(xù)) 根據(jù)貝葉斯定理：根據(jù)貝葉斯定理： n由于由于P P( (X X) )對于所

38、有類為對于所有類為常數(shù)常數(shù)，只需要，只需要P P( (X X| |C Ci i) )* *P P( (C Ci i) )最大最大 即可。即可。 n注意，類的先驗概率可以用注意，類的先驗概率可以用P(CP(Ci i)=S)=Si i/S/S計算，其中計算，其中S Si i是類是類 C Ci i中的訓(xùn)練樣本數(shù)，而中的訓(xùn)練樣本數(shù)，而S S是訓(xùn)練樣本總數(shù)。是訓(xùn)練樣本總數(shù)。 n因此問題就轉(zhuǎn)換為計算因此問題就轉(zhuǎn)換為計算P P( (X X| |C Ci i) )。 )( )()|( )( )( )|( XP HPHXP XP XHP XHP .49 樸素貝葉斯分類(續(xù)) n給定具有許多屬性的數(shù)據(jù)集，計算給定

39、具有許多屬性的數(shù)據(jù)集，計算P P( (X X| |C Ci i) )的計算的計算 量可能非常大且不易計算。為降低計算量可能非常大且不易計算。為降低計算P P( (X X| |C Ci i) )的的 難度，可以做難度，可以做類條件獨立的樸素假定。給定樣本。給定樣本 的類標號，假定的類標號，假定屬性值相互條件獨立屬性值相互條件獨立，即在屬性，即在屬性 間，不存在依賴關(guān)系。這樣間，不存在依賴關(guān)系。這樣 nP(P(收入低收入低, ,是學生是學生, , 信用良好信用良好| |買電腦買電腦)=)= P( P(收入低收入低| |買電腦買電腦) )* *P(P(是學生是學生| |買電腦買電腦) )* *P(P

40、(信用良好信用良好 | |買電腦買電腦) ) )|()|( 1 i n k ki CxPCXP .50 樸素貝葉斯分類(續(xù)) 其中概率其中概率P P( (x x1 1| |C Ci i) )，P P( (x x2 2| |C Ci i) )，P P( (x xn n| |C Ci i) )可以由訓(xùn)練樣可以由訓(xùn)練樣 本估值。本估值。 n如果如果A Ak k是離散屬性，則是離散屬性，則P P( (x xk k| |C Ci i)=)=s sik ik| |s si i，其中 ，其中s sik ik是在屬性 是在屬性A Ak k 上具有值上具有值x xk k的類的類C Ci i的訓(xùn)練樣本數(shù)，而的訓(xùn)練

41、樣本數(shù)，而s si i是是C Ci i中的訓(xùn)練樣本數(shù)。中的訓(xùn)練樣本數(shù)。 n如果如果A Ak k是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因 而，而， 是高斯分布函數(shù)，是高斯分布函數(shù)， 而分別為平均值和標準差。而分別為平均值和標準差。 2 2 )( 2 1 ),()|( i i i ii c ck c cckik x exgCxP ),( ii cck xg ii cc , .51 樸素貝葉斯分類(續(xù)) n例題：計算 P(收入低|不買電腦) P(是學生|不買電腦) P(信用良好|不買電腦) n假設(shè) 收入，是否學生，信 用狀況互相獨立，計算 P(收入

42、低，是學生，信用 良好|不買電腦) 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否一般否否 低否良好否否 中否良好否否 低是良好？ .52 樸素貝葉斯分類(續(xù)) n對 未 知 樣 本對 未 知 樣 本X X分 類 ， 也 就 是 對 每 個 類分 類 ， 也 就 是 對 每 個 類C C i i ， 計 算， 計 算 P(P(X X| |C Ci i) )* *P(P(C Ci i) )。樣本。樣本X X被指派到類被指派到類C Ci i，當且僅當，當且僅當P(P(C Ci i| |X X) ) P(P(C

43、 C j j| |X X) )， ，11j jmm，j ji i，換言之，換言之，X X被指派到其被指派到其 P(P(X X| |C Ci i) )* *P(P(C Ci i) )最大的類。最大的類。 .53 樸素貝葉斯分類舉例 n數(shù)據(jù)樣本有屬性年齡，收 入，是否學生和信用狀況。 類標號屬性”是否買電腦 “有兩個不同值是，否。 設(shè)C1對應(yīng)于類”買電腦”； 則C2對應(yīng)于類”不買電 腦”。 n我們希望分類的未知樣本 為: X=（”年齡=30”，”收 入=中”，”是學生”，” 信用一般”） 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 =30高否一般否否 40中

44、否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ .54 樸素貝葉斯分類舉例 n我們需要最大化 P(X|Ci)*P(Ci)，i=1，2。 n每個類的先驗概率P(Ci)可 以根據(jù)訓(xùn)練樣本計算： P(C1)=P(買電腦）= P(C2)=P(不買電腦）= n計算P(X|Ci) P（年齡=30,收入=中, 是學生,信用一般|買電 腦) P（年齡=30,收入=中, 是學生,信用一般|不買 電腦) 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 =30高否一般

45、否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ .55 樸素貝葉斯分類舉例 nP（年齡=30,收入=中 ,是學生,信用一般|買 電腦)= P（年齡=30|買電腦)* P（收入=中|買電腦)* P（是學生|買電腦)* P（信用一般|買電腦) nP（年齡=30,收入=中 ,是學生,信用一般|不 買電腦)= P（年齡=30|不買電腦)* P（收入=中|不買電腦)* P（是學生|不買電腦)* P（信用一般|不買電腦) 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況

46、是否買是否買 電腦電腦 =30高否一般否否 40中否一般是是 40低是一般是是 40低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ .56 樸素貝葉斯分類舉例 n假設(shè)屬性之間獨立 P（年齡=30,收入=中, 是學生,信用一般|買電 腦)=0.222*0.444*0.667 *0.667=0.044； P（年齡P（X|不買電 腦)，因此對于樣本X，樸素 貝葉斯分類預(yù)測為是。 年齡年齡收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 =30高否一般否否 40中否一般是是 40低是一般是是 40

47、低是良好否否 3140 低是良好是是 =30中否一般否否 40中是一般是是 40中否良好否否 =30=30中中是是一般一般 ？ .57 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提要 n分類的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n基于規(guī)則的分類 n與分類有關(guān)的問題 .58 使用IF-THEN規(guī)則分類 n使用規(guī)則的分類法是使用一組IF-THEN規(guī)則進行 分類。 nIF 條件 THEN 結(jié)論 n比如 IF (年齡20 AND 學生=是) THEN買電腦=是 nIF的部分稱為前提，THEN的部分稱為規(guī)則的結(jié)論 n規(guī)則可以用它的覆蓋率和準確率來評價 nncovers

48、是條件(前提)覆蓋的樣本數(shù)，ncorrect是規(guī)則 正確分類的樣本數(shù)。 | )covarage(R covers D n covers correct )accuracy(R n n .59 使用IF-THEN規(guī)則分類 n規(guī)則(收入=低)(信用狀況 良好)(是否買電腦=是) 的覆蓋率為3/8,而它測準 確率為1/3。 n規(guī) 則 ( 信 用 狀 況 = 良 好)(是否買電腦=否)的 覆蓋率為7/8,而它測準確 率為4/7。 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否良好否否 高是良好是是 中是良好是是 低是良好是是 低否一般否否 低否良好否否 中否良好否否

49、低是良好否否 .60 使用IF-THEN規(guī)則分類 n如果一個規(guī)則R被一個樣本X滿足，則稱規(guī)則R被 X觸發(fā)。 n比如X =(年齡=18，是學生，信用良好) R為 IF(年齡20 AND 學生=是) THEN買電腦=是 則X的類別為 買電腦 n如果一個樣本X同時觸發(fā)了多個規(guī)則，我們需要 制定解決沖突的策略。 n規(guī)模序 激活具有最多屬性測試的觸發(fā)規(guī)則 n規(guī)則序 將規(guī)則按重要性進行排序，按順序進行促發(fā) n如果一個樣本X無法促發(fā)任何規(guī)則 n建立一個缺省或者默認規(guī)則 .61 使用決策樹來提取規(guī)則 n決策樹的規(guī)則是互斥與 窮舉的 n互斥意味著規(guī)則不會存 在沖突，因此每個樣本 只能促發(fā)一個規(guī)則 n窮舉意味著一

50、個樣本總 能促發(fā)一個規(guī)則 n由于每個樹葉對應(yīng)一個 一條規(guī)則，提取的規(guī)則 并不比決策樹簡單。 年齡？年齡？ 信用狀況？信用狀況？收入？收入？是是 40 否否是是是是否否 良好一 般 高低 .62 使用順序覆蓋算法的規(guī)則歸納 n在提取規(guī)則時，一個現(xiàn)實的問題是是否需要對現(xiàn) 有規(guī)則進行拓展， n IF (年齡20) THEN買電腦 是否需要拓展為 IF (年齡 20 AND 學生=是) THEN買電腦 n衡量規(guī)則好壞應(yīng)同時考慮覆蓋度與準確率 n 準確率太低 覆蓋度太低 .63 使用順序覆蓋算法的規(guī)則歸納 n有兩種衡量規(guī)則好壞的度量 FOIL_Gain的定義如下 n分別對應(yīng)于兩個規(guī)則R與R。正在學習的類

51、稱為正樣 本(pos)，而其他類稱為負樣本(neg), pos(neg)為規(guī)則 R覆蓋的正負樣本，而pos(neg)為規(guī)則R覆蓋的正負 樣本。 )log(logFoil_Gain2 2 negpos pos negpos pos pos .64 n判斷規(guī)則(收入=低)(是否 買電腦=否) 是否需要拓展為 規(guī)則(收入=低)(信用狀況=良 好)(是否買電腦=否) 收收 入入 是否是否 學生學生 信用狀信用狀 況況 是否買電是否買電 腦腦 高否良好否否 高是良好是是 中是良好是是 低是一般是是 低否良好否否 低否良好否否 中否良好是是 低是良好否否 )log(logFoil_Gain2 2 negp

52、os pos negpos pos pos .65 使用順序覆蓋算法的規(guī)則歸納 n似然率統(tǒng)計量的的定義如下 n其中m是分類的類別數(shù)。fi為滿足規(guī)則的樣本中屬于 類i的概率，ei為屬于類i的期望(基準)概率。 n似然率越高，說明規(guī)則越理想。 m i i i i e f f 1 )log(2_RatioLikelihood .66 n分 別 計 算 規(guī) 則 ( 收 入 = 低)(是否買電腦=否) 與規(guī)則 (收入=低)(信用狀況=良 好)(是否買電腦=否) 的似然率。 收收 入入 是否學是否學 生生 信用狀信用狀 況況 是否買電是否買電 腦腦 高否良好否否 高是良好是是 中是良好是是 低是一般是是

53、低否良好否否 低否良好否否 中否良好是是 低是良好否否 m i i i i e f f 1 )log(2_RatioLikelihood .67 順序覆蓋算法 n終止條件包括，類c沒有樣本或者返回的規(guī)則質(zhì)量 低于用戶指定的閾值等。 輸入：D，類標記已知的樣本的集合。 Att_vals,所有屬性與它們可能值得集合。 輸出：IF-THEN規(guī)則的集合。 （1）Rule_set=；/規(guī)則的初始集為空集 （2）FOR 每個類 c DO （3） repeat （4） Rule=Learn_One_Rule(D,Att_vals,c); （5） 從D中刪除Rule覆蓋的樣本； （6） untile 終止條件

54、滿足； （7） Rule_set=Rule_set+Rule; /將新規(guī)則添加到規(guī)則集 （8）END FOR （9）返回Rule_Set .68 使用順序覆蓋算法的規(guī)則歸納 nRule_set=； n選擇一個類“買電腦”； n選擇一個包含一個屬性的 規(guī)則 n(收入=低)“買電腦” n分別計算其它包含一個屬 性的規(guī)則的相對于已選擇 規(guī)則的FOIL_Gain n(收入=高)“買電腦” n(學生=是)“買電腦” n(學生=否)“買電腦” n(信用=良好)“買電腦” n(信用=一般)“買電腦” 收收 入入 是否學是否學 生生 信用狀信用狀 況況 是否買電是否買電 腦腦 高否一般否否 高是一般是是 高是

55、良好是是 高否良好是是 低否一般是是 低是良好否否 低是良好否否 低否一般否否 )log(logFoil_Gain2 2 negpos pos negpos pos pos .69 使用順序覆蓋算法的規(guī)則歸納 分別計算規(guī)則的Foil_gain n(收入=高)買電腦為1.74 n(學生=是)買電腦為0 n(學生=否)買電腦為0 n(信用=良好)買電腦為0 n(信用=一般)買電腦為0 n選擇Foil_gain最高的規(guī)則 n(收入=高)買電腦 收收 入入 是否學是否學 生生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否一般否否 高是一般是是 高是良好是是 高否良好是是 低否一般是是 低是良好否否

56、 低是良好否否 低否一般否否 .70 使用順序覆蓋算法的規(guī)則歸納 n對最好的規(guī)則R進行拓展 n(收入=高)買電腦 n在規(guī)則R中添加一個屬性， 得到拓展以后的規(guī)則R n(收入=高)(學生=是) n(收入=高)(學生=否) n(收入=高)(信用=良好) n(收入=高)(信用=一般) 分別計算這些規(guī)則的相對于R 的Foil_gain 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否一般否否 高是一般是是 高是良好是是 高否良好是是 低否一般是是 低是良好否否 低是良好否否 低否一般否否 .71 使用順序覆蓋算法的規(guī)則歸納 n分別計算規(guī)則的Foil_gain n(收入=

57、高)(學生=是) 為0.84 n(收入=高)(學生=否) 為-1.16 n(收入=高)(信用=良好) 為0.84 n(收入=高)(信用=一般) 為-1.16 n選擇Foil_gain最高的規(guī)則 n(收入=高)(學生=是) n(收入=高)(信用=良好) n由于這兩個規(guī)則準確率已經(jīng) 是100%，因此不用拓展 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否一般否否 高是一般是是 高是良好是是 高否良好是是 低否一般是是 低是良好否否 低是良好否否 低否一般否否 .72 使用順序覆蓋算法的規(guī)則歸納 n將規(guī)則覆蓋的樣本從數(shù)據(jù)集D中 刪除，對剩下的正樣本生成規(guī) 則 收收

58、入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否一般否否 低否一般是是 低是良好否否 低是良好否否 低否一般否否 .73 使用順序覆蓋算法的規(guī)則歸納 收收 入入 是否是否 學生學生 信用信用 狀況狀況 是否買是否買 電腦電腦 高否一般否否 低是良好否否 低是良好否否 低否一般否否 n選擇另外一個類“不買電腦” (生成其它類的規(guī)則)； n選擇一個包含一個屬性的規(guī) 則 n(收入=低)“不買電腦” n分別計算其它包含一個屬性 的規(guī)則的相對于已選擇規(guī)則 的FOIL_Gain n(收入=高)“不買電腦” n(學生=是)“不買電腦” n(學生=否)“不買電腦” n(信用=良好)“

59、不買電腦” n(信用=一般)“不買電腦” .74 第三章第三章 分類方法分類方法 內(nèi)容提要內(nèi)容提要 n分類的基本概念與步驟 n基于距離的分類算法 n決策樹分類方法 n貝葉斯分類 n基于規(guī)則的分類 n實值預(yù)測 .75 實值預(yù)測 分類：把樣本分配到若干類 之一(離散的)。 n比如預(yù)測是普通員工、中層 管理還是高級管理人員 預(yù)測：預(yù)測樣本的某個屬性 值(連續(xù)的)。 n比如預(yù)測收入 工作年限工作年限周工作時周工作時 間間 月薪月薪 1402500 4483000 5403500 7404000 8484500 640？ 948？ .76 實值預(yù)測 n 實值預(yù)測方法有兩種 n線性回歸和多元回歸 n非線性

60、回歸 iiniiiyxxxxf),.,(321 .77 實值預(yù)測 n在回歸分析中，只包括一個自變量和一個因變量， 且二者的關(guān)系可用一條直線近似表示，這種回歸 分析稱為一元線性回歸分析。 nx=2,4,5,7,9; y=6,10,12,16,20; n如果回歸分析中包括兩個或兩個以上的自變量， 且因變量和自變量之間是線性關(guān)系，則稱為多元 線性回歸分析。 nx = ( 2 , 4 ) , ( 4 , 0 ) , ( 5 , 6 ) , ( 7 , 1 ) , ( 9 , - 3 ) ; y=10,4,17,9,3; .78 一元線性回歸模型 n給n個隨機樣本(Yi,Xi,)，則Y與X的線性 回歸模