數(shù)據(jù)挖掘分類(課堂PPT)課件(PPT 106頁)

1、第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實值預(yù)測 與分類有關(guān)的問題 2022/7/221.第1頁，共106頁。分類的流程 根據(jù)現(xiàn)有的知識，我們得到了一些關(guān)于爬行動物和鳥類的信息，我們能否對新發(fā)現(xiàn)的物種，比如動物A，動物B進行分類？2022/7/222.第2頁，共106頁。分類的流程 步驟一：將樣本轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提?。?。所有樣本必須具有相同數(shù)量的特征兼顧特征的全面性和獨立性2022/7/223.第3頁，共106頁。分類的流程 步驟二：選擇與類別相關(guān)的特征（特征選擇）。比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰色代表完全無

2、關(guān)2022/7/224.第4頁，共106頁。分類的流程 步驟三：建立分類模型或分類器（分類）。分類器通?？梢钥醋饕粋€函數(shù)，它把特征映射到類的空間上2022/7/225.第5頁，共106頁。如何避免過度訓(xùn)練 分類也稱為有監(jiān)督學(xué)習(xí)(supervised learning),與之相對于的是無監(jiān)督學(xué)習(xí)(unsupervised learning),比如聚類。分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。建立分類模型需要學(xué)習(xí)一部分已知數(shù)據(jù)，如果訓(xùn)練時間過長，或者預(yù)測模型參數(shù)太多而樣本較少，將導(dǎo)致過度訓(xùn)練(overfitting)。2022/7/226.第6頁，共106

3、頁。如何避免過度訓(xùn)練 避免過度訓(xùn)練最重要一點是，模型的參數(shù)量應(yīng)遠小于樣本的數(shù)量。應(yīng)建立訓(xùn)練集(training set)和測試集(test set)。訓(xùn)練集應(yīng)用于建立分類模型測試集應(yīng)用于評估分類模型K折疊交叉驗證(K-fold cross validation)：將初始采樣分割成K個子樣本(S1，S2,.,Sk)，取K-1個做訓(xùn)練集，另外一個做測試集。交叉驗證重復(fù)K次，每個子樣本都作為測試集一次，平均K次的結(jié)果，最終得到一個單一估測。2022/7/227.第7頁，共106頁。分類模型的評估 真陽性(True Positive)： 實際為陽性 預(yù)測為陽性真陰性(True Negative)：實際

4、為陰性 預(yù)測為陰性假陽性(False Positive)： 實際為陰性 預(yù)測為陽性假陰性(False Negative)：實際為陽性 預(yù)測為陰性預(yù)測是否正確 預(yù)測結(jié)果比如預(yù)測未知動物是鳥類還是爬行動物，陽性代表爬行動物，陰性代表非爬行動物，請大家闡述 TP=10，TN=8，F(xiàn)N=3，F(xiàn)P=2是什么意義2022/7/228.第8頁，共106頁。分類模型的評估 靈敏度(Sensitivity)： TP/(TP+FN)也稱為查全率(Recall)數(shù)據(jù)集共有13只爬行動物，其中10只被正確預(yù)測為爬行動物，靈敏度為10/13特異度(Specificity): TN/(TN+FP)數(shù)據(jù)集有10只非爬行動物

5、，其中8只被預(yù)測為非爬行動物，特異度為8/10精度(Precision): TP/(TP+FP)分類器預(yù)測了12只動物為爬行動物，其中10只確實是爬行動物，精度為10/12準確率(Accuracy): (TP+TN)/(TP+TN+FN+FP)數(shù)據(jù)集包含23只動物，其中18只預(yù)測為正確的分類，準確率為18/232022/7/229.第9頁，共106頁。分類模型的評估 對于非平衡(unblanced)的數(shù)據(jù)集,以上指標并不能很好的評估預(yù)測結(jié)果。非平衡的數(shù)據(jù)集是指陽性數(shù)據(jù)在整個數(shù)據(jù)集中的比例很小。比如，數(shù)據(jù)集包含10只爬行動物，990只爬行動物，此時，是否預(yù)測正確爬行動物對準確率影響不大。更平衡的

6、評估標準包括馬修斯相關(guān)性系數(shù)(Matthews correlation coefficient)和ROC曲線。馬修斯相關(guān)性系數(shù)定義為2022/7/2210.第10頁，共106頁。分類模型的評估 ROC曲線通過描述真陽性率(TPR)和假陽性率(FPR)來實現(xiàn)，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。大部分分類器都輸出一個實數(shù)值(可以看作概率),通過變換閾值可以得到多組TPR與FPR的值。2022/7/2211.第11頁，共106頁。第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實值預(yù)測 與分類有關(guān)的問題 2022/7/2

7、212.第12頁，共106頁?；诰嚯x的分類算法的思路定義4-2 給定一個數(shù)據(jù)庫 D=t1，t2，tn和一組類C=C1，Cm。假定每個元組包括一些數(shù)值型的屬性值：ti=ti1，ti2，tik，每個類也包含數(shù)值性屬性值：Cj=Cj1，Cj2，Cjk，則分類問題是要分配每個ti到滿足如下條件的類Cj：sim(ti，Cj)=sim(ti，Cl) ，ClC，ClCj，其中sim(ti，Cj)被稱為相似性。在實際的計算中往往用距離來表征，距離越近，相似性越大，距離越遠，相似性越小。距離的計算方法有多種，最常用的是通過計算每個類的中心來完成。2022/7/2213.第13頁，共106頁。 基于距離的分類算

8、法的一般性描述算法 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.2022/7/2214.第14頁，共106頁。基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結(jié)果2022/7/2215.第15頁，共106頁。距離分類例題 C1=(3

9、,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)2022/7/2216.第16頁，共106頁。K-近鄰分類算法K-近鄰分類算法（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ù)T；近鄰數(shù)目K；待分類的元組t。 輸出： 輸出類別c。 （1）N=；（2）FOR each d

10、 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. 2022/7/2217.第17頁，共106頁。KNN的例子姓名 性別 身高(米)類別Kristina女 1.6 矮Jim 男 2高Maggie 女 1.83高Martha 女 1.88高Stephanie女 1.7矮Bob 男 1.85中等Kathy 女 1.6矮Da

11、ve 男 1.7矮Worth 男 2.2高Steven 男 2.1高Debbie 女 1.8高Todd 男 1.82中等Kim 女 1.7中等Amy 女 1.75中等Wynette 女 1.73中等只使用身高做特征，K=3，對于樣本應(yīng)屬于哪個類別？僅使用同性別樣本做訓(xùn)練，K=3，對于樣本應(yīng)屬于哪個類別？2022/7/2218.第18頁，共106頁。第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實值預(yù)測 與分類有關(guān)的問題 2022/7/2219.第19頁，共106頁。決策樹表示與例子年齡？學(xué)生？是信用？40否是良好一般是否是否2022/7/222

12、0.第20頁，共106頁。決策樹表示與例子決策樹（Decision Tree）的每個內(nèi)部結(jié)點表示一個屬性（特征），每個分枝代表一個特征的一個（類）取值；每個樹葉結(jié)點代表類或類分布。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性的比較，從而判斷從該結(jié)點向下的分枝，在決策樹的葉結(jié)點得到結(jié)論。從決策樹的根到葉結(jié)點的一條路徑就對應(yīng)著一條規(guī)則，整棵決策樹就對應(yīng)著一組規(guī)則。決策樹分類模型的建立通常分為兩個步驟：決策樹生成決策樹修剪2022/7/2221.第21頁，共106頁。決策樹生成算法描述算法 4-3 Generate_decision_tree(samples, attribute

13、_list) /*決策樹生成算法*/輸入：訓(xùn)練樣本samples，由離散值屬性表示；輸出：一棵決策樹。（1） 創(chuàng)建結(jié)點N；（2） IF samples 都在同一個類C THEN 返回N 作為葉結(jié)點，以類 C標記；（3） IF attribute_list為空 THEN 返回N作為葉結(jié)點，標記為samples中最普通的類；/多數(shù)表決（4） 選擇attribute_list中具有最高信息增益的屬性test_attribute；（5） 標記結(jié)點N為test_attribute；（6） FOR test_attribute的每個取值ai 由結(jié)點N長出一個條件為test_attribute=ai的分枝；

14、（7）設(shè)si是samples 中test_attribute =ai的樣本的集合；/一個劃分（8）IF si 為空 THEN 回退到test_attribute的其它取值；（9）ELSE 加上一個由Generate_decision_tree(si， attribute_list-test_attribute)返回的結(jié)點；2022/7/2222.第22頁，共106頁。決策樹修剪算法基本的決策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓(xùn)練集擬合。在有噪聲情況下，將導(dǎo)致過分擬合（Overfitting），即對訓(xùn)練數(shù)據(jù)的完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預(yù)測性能下降。比如每個樣本都是一個葉子節(jié)點。現(xiàn)

15、實世界的數(shù)據(jù)一般不可能是完美的，可能缺值（Missing Values）；數(shù)據(jù)不完整；含有噪聲甚至是錯誤的。剪枝是一種克服噪聲的基本技術(shù)，同時它也能使樹得到簡化而變得更容易理解。有兩種基本的剪枝策略。2022/7/2223.第23頁，共106頁。決策樹修剪算法預(yù)先剪枝（Pre-Pruning）：在生成樹的同時決定是繼續(xù)對不純的訓(xùn)練子集進行劃分還是停機。后剪枝（Post-Pruning）：是一種擬合+化簡（fitting-and-simplifying）的兩階段方法。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時要用到一個測試數(shù)據(jù)集合（Tuning Se

16、t或Adjusting Set），如果存在某個葉子剪去后能使得在測試集上的準確度或其他測度不降低（不變得更壞），則剪去該葉子；否則停機。理論上講，后剪枝好于預(yù)先剪枝，但計算復(fù)雜度大。2022/7/2224.第24頁，共106頁。決策樹修剪算法構(gòu)造好的決策樹的關(guān)鍵在于如何選擇屬性進行樹的拓展。研究結(jié)果表明，一般情況下,樹越小則樹的預(yù)測能力越強。由于構(gòu)造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略來進行。屬性選擇依賴于各種對例子子集的不純度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距離度量（Dista

17、nce Measure）、J-measure等。2022/7/2225.第25頁，共106頁。ID3算法ID3是一個著名決策樹生成方法：決策樹中每一個非葉結(jié)點對應(yīng)著一個非類別屬性(特征)，樹枝代表這個屬性的值。一個葉結(jié)點代表從樹根到葉結(jié)點之間的路徑對應(yīng)的記錄所屬的類別屬性值。每一個非葉結(jié)點都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。采用信息增益來選擇能夠最好地將樣本分類的屬性。對ID3算法采用如下方式講解：給出信息增益對應(yīng)的計算公式；通過一個例子來說明它的主要過程。2022/7/2226.第26頁，共106頁。信息增益的計算設(shè)S是s個數(shù)據(jù)樣本的集合，定義m個不同類Ci（i=1，2，m），設(shè)s

18、i是Ci類中的樣本的數(shù)量。對給定的樣本S所期望的信息值由下式給出：其中pi是任意樣本屬于Ci的概率： si / s 。 例題：數(shù)據(jù)集有4個類，分別有8個，4個，2個，2個樣本，求該數(shù)據(jù)集的信息值。問題：信息值的取值范圍是什么？2022/7/2227.第27頁，共106頁。信息增益的計算例題：數(shù)據(jù)集有2個類，求該數(shù)據(jù)集的信息值。2022/7/2228.第28頁，共106頁。信息增益的計算設(shè)屬性A具有個不同值a1, a2, , av ，可以用屬性A將樣本S劃分為 S1, S2, , Sv ，設(shè)Sij 是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出：有A進行分枝將獲得的信息增益可以由下面的公

19、式得到： 使用屬性后的信息值未使用屬性的信息值2022/7/2229.第29頁，共106頁。信息增益的計算例題：數(shù)據(jù)集有2個類。使用是否學(xué)生作為屬性，求該屬性的信息增益。使用信用狀況作為屬性，求該屬性的信息增益。2022/7/2230.第30頁，共106頁。ID3算法的例子選擇信息增益最大的屬性特征作為根節(jié)點。Gain(年齡)=0.342 Gain(收入)=0Gain(是否學(xué)生)=0.333 Gain(信用狀況)=0年齡？是402022/7/2231.第31頁，共106頁。ID3算法的例子對于=30的分支Gain(收入)=0.315 Gain(是否學(xué)生)=0.315 Gain(信用狀況)=0.

20、815對于30 40的分支Gain(收入)=1 Gain(是否學(xué)生)=0 Gain(信用狀況)=1年齡？信用狀況？收入？是40否是是否良好一般高低2022/7/2232.第32頁，共106頁。ID3算法的性能分析ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間。ID3算法在搜索的每一步都使用當前的所有訓(xùn)練樣例，大大降低了對個別訓(xùn)練樣例錯誤的敏感性。因此，通過修改終止準則，可以容易地擴展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。2022/7/2233.第33頁，共106頁。ID3算法的性能分析ID3算法在搜索過程中不進行回溯。所以，它易受無回溯的爬山搜索中的常見風(fēng)險影響：收斂

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

22、進C4.5算法是從ID3算法演變而來，除了擁有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：用信息增益比例的概念；合并具有連續(xù)屬性的值；可以處理具有缺少屬性值的訓(xùn)練樣本；通過使用不同的修剪技術(shù)以避免樹的過度擬合；K交叉驗證；規(guī)則的產(chǎn)生方式等。2022/7/2235.第35頁，共106頁。信息增益比例的概念信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來的，一個屬性的信息增益比例用下面的公式給出：其中假如我們以屬性A的值為基準對樣本進行分割的化，Splitl(A)就是前面熵的概念。 2022/7/2236.第36頁，共106頁。信息增益比例的計算例題：數(shù)據(jù)集有2個類。使用是否學(xué)生作為

23、屬性，求該屬性的信息增益比例。使用年齡作為屬性，求該屬性的信息增益比例。討論：信息增益和信息增益比例的差異在哪里？2022/7/2237.第37頁，共106頁。C4.5處理連續(xù)值的屬性對于連續(xù)屬性值，C4.5其處理過程如下：根據(jù)屬性的值，對數(shù)據(jù)集排序；用不同的閾值將數(shù)據(jù)集動態(tài)的進行劃分；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值、增益及增益比；在每一個屬性會變?yōu)槿蓚€取值，即小于閾值或大于等于閾值。簡單地說，針對屬性有連續(xù)數(shù)值的情況，則在訓(xùn)練集中可以按升序方式排列。如果屬性A共有n種取值，則對每個取值vj（j=1，2，n），將所有的記錄進行劃分：

24、一部分小于vj；另一部分則大于或等于vj 。針對每個vj計算劃分對應(yīng)的增益比率，選擇增益最大的劃分來對屬性A進行離散化 。 2022/7/2238.第38頁，共106頁。C4.5處理連續(xù)值的屬性例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。根據(jù)屬性的值，對數(shù)據(jù)集排序；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值、增益及增益比；在每一個屬性會變?yōu)槿蓚€取值，即小于閾值或大于等于閾值。2022/7/2239.第39頁，共106頁。C4.5處理連續(xù)值的屬性例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。選擇增益最大的劃分來對屬性A進

25、行離散化 。GainRatio(劃分：2750)=0.2GainRatio(劃分：3100)=0.39GainRatio(劃分：3625)=0.53GainRatio(劃分：4458)=1GainRatio(劃分：？)=0.53GainRatio(劃分：8285)=0.39GainRatio(劃分：10900)=0.2收入小于4458合并為收入低收入大于等于4458合并為收入高2022/7/2240.第40頁，共106頁。C4.5的其他處理 C4.5處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對屬性和每一個值

26、賦予一個概率，取得這些概率，取得這些概率依賴于該屬性已知的值。規(guī)則的產(chǎn)生：一旦樹被建立，就可以把樹轉(zhuǎn)換成if-then規(guī)則。規(guī)則存儲于一個二維數(shù)組中，每一行代表樹中的一個規(guī)則，即從根到葉之間的一個路徑。表中的每列存放著樹中的結(jié)點。 2022/7/2241.第41頁，共106頁。C4.5算法例子樣本數(shù)據(jù)天氣溫度濕度風(fēng)網(wǎng)球SunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95fa

27、lseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYesRainMild80trueNo（1）首先對濕度進行屬性離散化，針對上面的訓(xùn)練集合，通過檢測每個劃分而確定最好的劃分在75處，則這個屬性的范圍就變?yōu)椋?5）。（2）計算目標屬性打網(wǎng)球分類的期望信息： （3）計算每個屬性的GainRatio：2022/7/2242.第42頁，共106頁。C4.5算法例子（4）選取最大的GainRatio，根據(jù)天氣的取值，得到三個分枝。（5）再擴展各分枝節(jié)點，得到

28、最終的決策樹（見課本圖4-7 ）。問題：就天氣=Sunny這一分支，請用C4.5算法構(gòu)造決策樹。樣本數(shù)據(jù)天氣溫度濕度風(fēng)網(wǎng)球SunnyHot85falseNoSunnyHot90trueNoSunnyMild95falseNoSunnyCool70falseYesSunnyMild70trueYes2022/7/2243.第43頁，共106頁。第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實值預(yù)測 與分類有關(guān)的問題 2022/7/2244.第44頁，共106頁。貝葉斯分類定義4-3 設(shè)X是類標號未知的數(shù)據(jù)樣本。設(shè)H為某種假定，如數(shù)據(jù)樣本X屬于某特

29、定的類C。對于分類問題，我們希望確定P(H|X)，即給定觀測數(shù)據(jù)樣本X，假定H成立的概率。貝葉斯定理給出了如下計算P(H|X)的簡單有效的方法:P(X |H)代表假設(shè)H成立的情況下，觀察到X的概率。P(H| X )是后驗概率，或稱為X發(fā)生后觀測到H的條件概率。例如，假定數(shù)據(jù)樣本由一些人組成，假定X表示頭發(fā)顏色，H表示膚色，則P(H|X)反映當我們看到X是黑色時，我們對H為黃色的確信程度。2022/7/2245.第45頁，共106頁。樸素貝葉斯分類的工作原理觀測到的樣本具有屬性 收入低 是學(xué)生 信用良好現(xiàn)在的問題相當于比較兩個條件概率的大小P(買電腦|收入低,是學(xué)生, 信用良好)P(不買電腦|收

30、入低,是學(xué)生, 信用良好)2022/7/2246.第46頁，共106頁。樸素貝葉斯分類樸素貝葉斯分類的工作過程如下：(1) 每個數(shù)據(jù)樣本用一個n維特征向量X= x1，x2，xn表示，分別描述對n個屬性A1，A2，An樣本的n個度量。(2) 假定有m個類C1，C2，Cm，給定一個未知的數(shù)據(jù)樣本X（即沒有類標號），分類器將預(yù)測X屬于具有最高條件概率（條件X下）的類。也就是說，樸素貝葉斯分類將未知的樣本分配給類Ci（1im）當且僅當P(Ci|X) P(Cj|X)，對任意的j=1，2，m，ji。2022/7/2247.第47頁，共106頁。樸素貝葉斯分類(續(xù))根據(jù)貝葉斯定理：由于P(X)對于所有類為常

31、數(shù)，只需要P(X|Ci)*P(Ci)最大即可。注意，類的先驗概率可以用P(Ci)=Si/S計算，其中Si是類Ci中的訓(xùn)練樣本數(shù)，而S是訓(xùn)練樣本總數(shù)。因此問題就轉(zhuǎn)換為計算P(X|Ci)。 2022/7/2248.第48頁，共106頁。樸素貝葉斯分類(續(xù))給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci)的計算量可能非常大且不易計算。為降低計算P(X|Ci)的難度，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性值相互條件獨立，即在屬性間，不存在依賴關(guān)系。這樣P(收入低,是學(xué)生, 信用良好|買電腦)= P(收入低|買電腦)*P(是學(xué)生|買電腦)*P(信用良好|買電腦) 2022/7/2249.第4

32、9頁，共106頁。樸素貝葉斯分類(續(xù))其中概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)可以由訓(xùn)練樣本估值。如果Ak是離散屬性，則P(xk|Ci)=sik|si，其中sik是在屬性Ak上具有值xk的類Ci的訓(xùn)練樣本數(shù)，而si是Ci中的訓(xùn)練樣本數(shù)。 如果Ak是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而， 是高斯分布函數(shù)， 而分別為平均值和標準差。 2022/7/2250.第50頁，共106頁。樸素貝葉斯分類(續(xù))例題：計算P(收入低|不買電腦)P(是學(xué)生|不買電腦)P(信用良好|不買電腦)假設(shè) 收入，是否學(xué)生，信用狀況互相獨立，計算 P(收入低，是學(xué)生，信用良好|不買電腦)2022

33、/7/2251.第51頁，共106頁。樸素貝葉斯分類(續(xù))對未知樣本X分類，也就是對每個類Ci，計算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當且僅當P(Ci|X) P(Cj|X)，1jm，ji，換言之，X被指派到其P(X|Ci)*P(Ci)最大的類。 2022/7/2252.第52頁，共106頁。樸素貝葉斯分類舉例數(shù)據(jù)樣本有屬性年齡，收入，是否學(xué)生和信用狀況。類標號屬性”是否買電腦“有兩個不同值是，否。設(shè)C1對應(yīng)于類”買電腦”；則C2對應(yīng)于類”不買電腦”。我們希望分類的未知樣本為:X=（”年齡=30”，”收入=中”，”是學(xué)生”，”信用一般”）2022/7/2253.第53頁，共106

34、頁。樸素貝葉斯分類舉例我們需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據(jù)訓(xùn)練樣本計算：P(C1)=P(買電腦）=P(C2)=P(不買電腦）=計算P(X|Ci)P（年齡=30,收入=中,是學(xué)生,信用一般|買電腦)P（年齡=30,收入=中,是學(xué)生,信用一般|不買電腦)2022/7/2254.第54頁，共106頁。樸素貝葉斯分類舉例P（年齡=30,收入=中,是學(xué)生,信用一般|買電腦)=P（年齡=30|買電腦)*P（收入=中|買電腦)*P（是學(xué)生|買電腦)*P（信用一般|買電腦)P（年齡=30,收入=中,是學(xué)生,信用一般|不買電腦)=P（年齡=30|不買電腦)*P

35、（收入=中|不買電腦)*P（是學(xué)生|不買電腦)*P（信用一般|不買電腦)2022/7/2255.第55頁，共106頁。樸素貝葉斯分類舉例假設(shè)屬性之間獨立P（年齡=30,收入=中,是學(xué)生,信用一般|買電腦)=0.222*0.444*0.667 *0.667=0.044；P（年齡P（X|不買電腦)，因此對于樣本X，樸素貝葉斯分類預(yù)測為是。2022/7/2256.第56頁，共106頁。第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 基于規(guī)則的分類 與分類有關(guān)的問題 2022/7/2257.第57頁，共106頁。使用IF-THEN規(guī)則分類使用規(guī)則的分類法

36、是使用一組IF-THEN規(guī)則進行分類。IF 條件 THEN 結(jié)論比如 IF (年齡20 AND 學(xué)生=是) THEN買電腦=是IF的部分稱為前提，THEN的部分稱為規(guī)則的結(jié)論規(guī)則可以用它的覆蓋率和準確率來評價ncovers是條件(前提)覆蓋的樣本數(shù)，ncorrect是規(guī)則正確分類的樣本數(shù)。2022/7/2258.第58頁，共106頁。使用IF-THEN規(guī)則分類規(guī)則(收入=低)(信用狀況良好)(是否買電腦=是)的覆蓋率為3/8,而它測準確率為1/3。規(guī)則(信用狀況=良好)(是否買電腦=否)的覆蓋率為7/8,而它測準確率為4/7。2022/7/2259.第59頁，共106頁。使用IF-THEN規(guī)則

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

38、規(guī)則并不比決策樹簡單。年齡？信用狀況？收入？是40否是是否良好一般高低2022/7/2261.第61頁，共106頁。使用順序覆蓋算法的規(guī)則歸納在提取規(guī)則時，一個現(xiàn)實的問題是是否需要對現(xiàn)有規(guī)則進行拓展， IF (年齡20) THEN買電腦 是否需要拓展為 IF (年齡20 AND 學(xué)生=是) THEN買電腦衡量規(guī)則好壞應(yīng)同時考慮覆蓋度與準確率 準確率太低 覆蓋度太低2022/7/2262.第62頁，共106頁。使用順序覆蓋算法的規(guī)則歸納有兩種衡量規(guī)則好壞的度量 FOIL_Gain的定義如下分別對應(yīng)于兩個規(guī)則R與R。正在學(xué)習(xí)的類稱為正樣本(pos)，而其他類稱為負樣本(neg), pos(neg)

39、為規(guī)則R覆蓋的正負樣本，而pos(neg)為規(guī)則R覆蓋的正負樣本。2022/7/2263.第63頁，共106頁。判斷規(guī)則(收入=低)(是否買電腦=否)是否需要拓展為規(guī)則(收入=低)(信用狀況=良好)(是否買電腦=否)2022/7/2264.第64頁，共106頁。使用順序覆蓋算法的規(guī)則歸納似然率統(tǒng)計量的的定義如下其中m是分類的類別數(shù)。fi為滿足規(guī)則的樣本中屬于類i的概率，ei為屬于類i的期望(基準)概率。似然率越高，說明規(guī)則越理想。2022/7/2265.第65頁，共106頁。分別計算規(guī)則(收入=低)(是否買電腦=否)與規(guī)則(收入=低)(信用狀況=良好)(是否買電腦=否)的似然率。2022/7/

40、2266.第66頁，共106頁。 順序覆蓋算法終止條件包括，類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 終止條件滿足； （7） Rule_set=Rule_set+Rule; /將新規(guī)則添加到規(guī)則集（8）END FOR（9）返回Rule_

41、Set2022/7/2267.第67頁，共106頁。使用順序覆蓋算法的規(guī)則歸納Rule_set=；選擇一個類“買電腦”；選擇一個包含一個屬性的規(guī)則(收入=低)“買電腦”分別計算其它包含一個屬性的規(guī)則的相對于已選擇規(guī)則的FOIL_Gain(收入=高)“買電腦”(學(xué)生=是)“買電腦”(學(xué)生=否)“買電腦”(信用=良好)“買電腦”(信用=一般)“買電腦”2022/7/2268.第68頁，共106頁。使用順序覆蓋算法的規(guī)則歸納分別計算規(guī)則的Foil_gain(收入=高)買電腦為1.74(學(xué)生=是)買電腦為0(學(xué)生=否)買電腦為0(信用=良好)買電腦為0(信用=一般)買電腦為0選擇Foil_gain最高

42、的規(guī)則(收入=高)買電腦2022/7/2269.第69頁，共106頁。使用順序覆蓋算法的規(guī)則歸納對最好的規(guī)則R進行拓展(收入=高)買電腦在規(guī)則R中添加一個屬性，得到拓展以后的規(guī)則R(收入=高)(學(xué)生=是)(收入=高)(學(xué)生=否)(收入=高)(信用=良好)(收入=高)(信用=一般)分別計算這些規(guī)則的相對于R的Foil_gain2022/7/2270.第70頁，共106頁。使用順序覆蓋算法的規(guī)則歸納分別計算規(guī)則的Foil_gain(收入=高)(學(xué)生=是) 為0.84(收入=高)(學(xué)生=否) 為-1.16(收入=高)(信用=良好) 為0.84(收入=高)(信用=一般) 為-1.16選擇Foil_ga

43、in最高的規(guī)則(收入=高)(學(xué)生=是) (收入=高)(信用=良好)由于這兩個規(guī)則準確率已經(jīng)是100%，因此不用拓展2022/7/2271.第71頁，共106頁。使用順序覆蓋算法的規(guī)則歸納將規(guī)則覆蓋的樣本從數(shù)據(jù)集D中刪除，對剩下的正樣本生成規(guī)則2022/7/2272.第72頁，共106頁。使用順序覆蓋算法的規(guī)則歸納選擇另外一個類“不買電腦” (生成其它類的規(guī)則)；選擇一個包含一個屬性的規(guī)則(收入=低)“不買電腦”分別計算其它包含一個屬性的規(guī)則的相對于已選擇規(guī)則的FOIL_Gain(收入=高)“不買電腦”(學(xué)生=是)“不買電腦”(學(xué)生=否)“不買電腦”(信用=良好)“不買電腦”(信用=一般)“不買

44、電腦”2022/7/2273.第73頁，共106頁。第三章 分類方法 內(nèi)容提要分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 基于規(guī)則的分類實值預(yù)測 2022/7/2274.第74頁，共106頁。實值預(yù)測分類：把樣本分配到若干類之一(離散的)。比如預(yù)測是普通員工、中層管理還是高級管理人員預(yù)測：預(yù)測樣本的某個屬性值(連續(xù)的)。比如預(yù)測收入2022/7/2275.第75頁，共106頁。實值預(yù)測 實值預(yù)測方法有兩種線性回歸和多元回歸非線性回歸2022/7/2276.第76頁，共106頁。實值預(yù)測在回歸分析中，只包括一個自變量和一個因變量，且二者的關(guān)系可用一條直線近似表示，這種回

45、歸分析稱為一元線性回歸分析。x=2,4,5,7,9; y=6,10,12,16,20;如果回歸分析中包括兩個或兩個以上的自變量，且因變量和自變量之間是線性關(guān)系，則稱為多元線性回歸分析。x=(2,4),(4,0),(5,6),(7,1),(9,-3); y=10,4,17,9,3;2022/7/2277.第77頁，共106頁。一元線性回歸模型給n個隨機樣本(Yi,Xi,)，則Y與X的線性回歸模型可以寫為其中 b0 ，b1是參數(shù) 是被稱為誤差項的隨機變量,這是由于我們建立的線性回歸模型可能是不完美的 2022/7/2278.第78頁，共106頁。線性回歸模型的求解回歸模型的求解相當于求解 使得一元

46、線性回歸分析的求解2022/7/2279.第79頁，共106頁。一元線性回歸模型例題：請建立右表的線性回歸模型。 2022/7/2280.第80頁，共106頁。多元線性回歸模型給n個隨機樣本(Yi,Xi1,Xi2,.,Xip)，則Y與X的線性回歸模型可以寫為其中 b0 ，b1，b2 ，bn是參數(shù) 是被稱為誤差項的隨機變量,這是由于我們建立的線性回歸模型可能是不完美的 2022/7/2281.第81頁，共106頁。線性回歸模型的求解回歸模型的求解相當于求解 使得多元線性回歸分析的求解其中X為2022/7/2282.第82頁，共106頁。 AQ算法多元回歸模型的求解在許多軟件中都可以得到，比如Ma

47、tlab，SAS，SPSS，Weka等。2022/7/2283.第83頁，共106頁。AQR算法有關(guān)定義AQR為每一個分類推導(dǎo)出一條規(guī)則，每一條規(guī)則形式如下：if then predict 。在一個屬性上的基本測試被稱為一個Selector。下面是一些Selector的例子：或60。AQR允許測試做=，。Selectors的合取被稱為復(fù)合（Complex），Complexes之間的析取被稱為覆蓋（Cover）。如果一個表達式對某個樣本為真，則我們稱其為對這個樣本的一個覆蓋。這樣，一個空Complex覆蓋所有的樣本，而一個空Cover不覆蓋任何樣本。在AQR中，一個新樣本被區(qū)分是看其屬于哪個推導(dǎo)

48、出來的規(guī)則。如果該樣本只滿足一條規(guī)則，則這個樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預(yù)測的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。2022/7/2284.第84頁，共106頁。 AQR算法描述算法 4-5 AQR輸入：正例樣本POS；反例樣本NEG。輸出：覆蓋COVER。（1） COVER= ；/初始化COVER為空集（2） WHILE COVER does not cover all positive examples in POS DO BEGIN（3） Select a SEED；/選取一個種子SEED，例如沒有被COVER

49、覆蓋的一個正樣例（4） Call procedure STAR（SEED，NEG）； /產(chǎn)生一個能覆蓋種子而同時排除所有反例的星（5） Select the best Complex BEST from the STAR according to user-defined criteria；/*從星中選取一個最好的復(fù)合*/（6） Add BEST as an extra disjuct to COVER /*把最好的復(fù)合與COVER合取，形成新的COVER*/（7） END（8） RETURN COVER.在算法AQR中調(diào)用了過程STAR，來排除所有的反例，產(chǎn)生覆蓋種子的星。2022/7/22

50、85.第85頁，共106頁。 AQR算法描述(續(xù))算法 4-6 STAR輸入：種子SEED；反例NEG。輸出：星STAR。 （1）初始化STAR為空Complex（2）WHILE one or more Complexes in STAR covers some negative examples in NEG BEGIN /*如果STAR中的一個或多個Complex覆蓋NEG中的負樣例*/（3）Select a negative example Eneg covered by a Complex in STAR；/*選取一個被STAR中的Complex覆蓋的負樣例*/（4）Let EXTEN

51、SION be all Selectors that cover SEED but not ENEG；/*令EXTENSION為那些覆蓋SEED但不覆蓋ENEG的Selectors；*/（5）Let STAR be the set xy|xSTAR，yEXTENSION；/*令STAR= xy|xSTAR，yEXTENSION；*/（6） Remove all Complexes in STAR subsumed by other Complexes in STAR；/*從STAR中除去被其他Complexes所包含的Complexes；*/（7）Remove the worst Comple

52、xes from STAR UNTIL size of STAR is less than or equal to user-defined maximum （maxstar）/*刪除STAR中最壞的Complex直到STAR的大小等于或小于用戶定義的最大數(shù)目maxstar*/（8）END（9）RETURN STAR. /*返回一系列覆蓋SEED但不覆蓋NEG的規(guī)則*/2022/7/2286.第86頁，共106頁。AQR算法舉例假設(shè)現(xiàn)有一個訓(xùn)練集，其包含兩種屬性：size （屬性值：micro，tiny，mid，big，huge，vast）type （屬性值：bicycle，motorcycl

53、e，car，prop，jet，glider）現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示： 下面給出用AQR算法對giant 2-wheeler類的規(guī)則進行獲取過程，具體步驟如下：（）COVER=。（）空cover不覆蓋任何樣本，進入循環(huán)。（）一開始COVER并沒有覆蓋任何正例，假定從正例中選取的SEED 為 size=huge，type =bicycle 。（）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個覆蓋SEED但不包含NEG的STAR集合；初始化STAR為空，即STAR=?？盏腸omplex覆蓋所有樣例，STAR覆蓋多個負樣例，進入循環(huán)。 a ) 選取一個被STAR中的復(fù)合覆蓋的負樣例

54、ENEG，假定被選取的是 Eneg= size= tiny， type = motorcycle 。 b ) 使EXTENSION為所有覆蓋SEED但不覆蓋ENEG的選擇，則EXTENSION包括size= huge和type =bicycle，則又根據(jù)STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=hugetype =bicycle 。 c ) 在這里定義maxstar為2，可不對STAR進行精簡。 d ) 接著選取另一個被STAR中的復(fù)合覆蓋的負樣例ENEG，顯然已經(jīng)沒有這樣的負樣例，因此，STAR= size=hugetype =bicycle 。從STAR

55、（SEED，NEG）返回。反例樣本size type classTiny motorcycle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例樣本size type classHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler2022/7/2287.第87頁，共1

56、06頁。AQR算法舉例（5）BEST= size=hugetype =bicycle ，COVER = size=hugetype =bicycle 。 （6）顯然COVER不能覆蓋所有的正例，從正例中選取另一個SEED= size=huge，type = motorcycle。 （7）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個覆蓋SEED但不包含NEG的STAR集合。 初始化STAR為空，即STAR=；空的complex覆蓋所有樣例， 所以STAR覆蓋負樣例，進入循環(huán)； a ) 假定被選取的是Eneg= size= tiny， type = motorcycle ； b ) 使EXTENSI

57、ON為所有覆蓋SEED但不覆蓋Eneg的選擇，則EXTENSION包括size= huge，則又根據(jù)STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=huge； c ) 接著選取另一個被STAR中的復(fù)合覆蓋的負樣例Eneg，顯然已經(jīng)沒有這樣的負樣例，因此，STAR= size=huge； d ) 接著選取另一個被STAR中的復(fù)合覆蓋的負樣例ENEG，顯然已經(jīng)沒有這樣的負樣例，因此，STAR= size=hugetype =bicycle 。從STAR（SEED，NEG）返回。（8）BEST=size=huge，將BEST添加到COVER中，COVER = size=

58、hugetype =bicycle size=huge= size=huge。 （9）這時，COVER已經(jīng)覆蓋到全部的正例，則算法結(jié)束。輸出規(guī)則為gaint 2-wheelersize=huge。假設(shè)現(xiàn)有一個訓(xùn)練集，其包含兩種屬性：size （屬性值：micro，tiny，mid，big，huge，vast）type （屬性值：bicycle，motorcycle，car，prop，jet，glider）現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示： 反例樣本size type classTiny motorcycle conventional transportation tiny car

59、 conventional transportation mid car conventional transportation micro jetfast planeTiny jetfast planeMid jetfast plane正例樣本size type classHuge bicycle giant 2-wheelerHuge motorcycle giant 2-wheeler2022/7/2288.第88頁，共106頁。CN2算法描述CN2使用一種基于噪音估計的啟發(fā)式方法，使用這種方法可以不用對所有的訓(xùn)練樣本進行正確的區(qū)分，但是規(guī)約出的規(guī)則在對新數(shù)據(jù)的處理上有很好的表現(xiàn)。算法

60、4-7 CN2輸入：E /*E為訓(xùn)練樣本*/輸出：RULE_LIST /*返回一個覆蓋若干樣例的規(guī)則*/（1） Let RULE_LIST be the empty list； /* 初始化RULES_LIST為空；*/（2） REPEAT（3） Let BEST_CPX be Find_Best_Complex（E）；/*尋找最佳的規(guī)則Find_Best_Complex（E）并將其結(jié)果放入BEST_CPX中；*/（4） IF BEST_CPX is not nil THEN BEGIN（5） Let E be the examples covered by BEST_CPX；/*令E為BES