數(shù)據(jù)挖掘-分類課件

第三章分類方法

內(nèi)容提要分類的基本概念與步驟

基于距離的分類算法決策樹分類方法貝葉斯分類實值預測與分類有關(guān)的問題2023/11/291數(shù)據(jù)挖掘--分類分類的流程根據(jù)現(xiàn)有的知識，我們得到了一些關(guān)于爬行動物和鳥類的信息，我們能否對新發(fā)現(xiàn)的物種，比如動物A，動物B進行分類？動物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動物豬大04否是爬行動物牛大04否是爬行動物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類動物A大02是無？動物B中22否是？2023/11/292數(shù)據(jù)挖掘--分類分類的流程步驟一：將樣本轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提?。?。所有樣本必須具有相同數(shù)量的特征兼顧特征的全面性和獨立性動物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動物豬大04否是爬行動物牛大04否是爬行動物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類2023/11/293數(shù)據(jù)挖掘--分類分類的流程步驟二：選擇與類別相關(guān)的特征（特征選擇）。比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰色代表完全無關(guān)動物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動物豬大04否是爬行動物牛大04否是爬行動物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類2023/11/294數(shù)據(jù)挖掘--分類分類的流程步驟三：建立分類模型或分類器（分類）。分類器通?？梢钥醋饕粋€函數(shù)，它把特征映射到類的空間上2023/11/295數(shù)據(jù)挖掘--分類如何避免過度訓練分類也稱為有監(jiān)督學習(supervisedlearning),與之相對于的是無監(jiān)督學習(unsupervisedlearning),比如聚類。分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。建立分類模型需要學習一部分已知數(shù)據(jù)，如果訓練時間過長，或者預測模型參數(shù)太多而樣本較少，將導致過度訓練(overfitting)。2023/11/296數(shù)據(jù)挖掘--分類如何避免過度訓練避免過度訓練最重要一點是，模型的參數(shù)量應遠小于樣本的數(shù)量。應建立訓練集(trainingset)和測試集(testset)。訓練集應用于建立分類模型測試集應用于評估分類模型K折疊交叉驗證(K-foldcrossvalidation)：將初始采樣分割成K個子樣本(S1，S2,...,Sk)，取K-1個做訓練集，另外一個做測試集。交叉驗證重復K次，每個子樣本都作為測試集一次，平均K次的結(jié)果，最終得到一個單一估測。2023/11/297數(shù)據(jù)挖掘--分類分類模型的評估真陽性(TruePositive)：實際為陽性預測為陽性真陰性(TrueNegative)：實際為陰性預測為陰性假陽性(FalsePositive)：實際為陰性預測為陽性假陰性(FalseNegative)：實際為陽性預測為陰性預測是否正確預測結(jié)果比如預測未知動物是鳥類還是爬行動物，陽性代表爬行動物，陰性代表非爬行動物，請大家闡述TP=10，TN=8，F(xiàn)N=3，F(xiàn)P=2是什么意義2023/11/298數(shù)據(jù)挖掘--分類分類模型的評估靈敏度(Sensitivity)：TP/(TP+FN)也稱為查全率(Recall)數(shù)據(jù)集共有13只爬行動物，其中10只被正確預測為爬行動物，靈敏度為10/13特異度(Specificity):TN/(TN+FP)數(shù)據(jù)集有10只非爬行動物，其中8只被預測為非爬行動物，特異度為8/10精度(Precision):TP/(TP+FP)分類器預測了12只動物為爬行動物，其中10只確實是爬行動物，精度為10/12準確率(Accuracy):(TP+TN)/(TP+TN+FN+FP)數(shù)據(jù)集包含23只動物，其中18只預測為正確的分類，準確率為18/232023/11/299數(shù)據(jù)挖掘--分類分類模型的評估對于非平衡(unblanced)的數(shù)據(jù)集,以上指標并不能很好的評估預測結(jié)果。非平衡的數(shù)據(jù)集是指陽性數(shù)據(jù)在整個數(shù)據(jù)集中的比例很小。比如，數(shù)據(jù)集包含10只爬行動物，990只爬行動物，此時，是否預測正確爬行動物對準確率影響不大。更平衡的評估標準包括馬修斯相關(guān)性系數(shù)(Matthewscorrelationcoefficient)和ROC曲線。馬修斯相關(guān)性系數(shù)定義為2023/11/2910數(shù)據(jù)挖掘--分類分類模型的評估ROC曲線通過描述真陽性率(TPR)和假陽性率(FPR)來實現(xiàn)，其中TPR=TP/(TP+FN),FPR=FP/(FP+TN)。大部分分類器都輸出一個實數(shù)值(可以看作概率),通過變換閾值可以得到多組TPR與FPR的值。2023/11/2911數(shù)據(jù)挖掘--分類第三章分類方法

內(nèi)容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法貝葉斯分類實值預測與分類有關(guān)的問題2023/11/2912數(shù)據(jù)挖掘--分類基于距離的分類算法的思路定義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)，

Cl∈C，Cl≠Cj，其中sim(ti，Cj)被稱為相似性。在實際的計算中往往用距離來表征，距離越近，相似性越大，距離越遠，相似性越小。距離的計算方法有多種，最常用的是通過計算每個類的中心來完成。2023/11/2913數(shù)據(jù)挖掘--分類

基于距離的分類算法的一般性描述算法4-1通過對每個樣本和各個類的中心來比較，從而可以找出他的最近的類中心，得到確定的類別標記。算法4-1基于距離的分類算法輸入：每個類的中心C1，…，Cm；待分類的元組t。輸出：輸出類別c。（1）dist=∞；//距離初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←i；（5） dist←dist(ci，t)；（6） END.2023/11/2914數(shù)據(jù)挖掘--分類基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結(jié)果2023/11/2915數(shù)據(jù)挖掘--分類距離分類例題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)2023/11/2916數(shù)據(jù)挖掘--分類K-近鄰分類算法K-近鄰分類算法（KNearestNeighbors，簡稱KNN）通過計算每個訓練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個訓練數(shù)據(jù)，K個數(shù)據(jù)中哪個類別的訓練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個類別。算法4-2K-近鄰分類算法輸入：訓練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。輸出：輸出類別c。（1）N=

；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪1116166；（5）ELSE（6） IF

u∈Nsuchthatsim(t，u)〈sim(t，d)THEN

BEGIN（7） N=N-{u}；（8） N=N∪1616161；（9） END（10）END（11）c=classtowhichthemostu∈N.

2023/11/2917數(shù)據(jù)挖掘--分類KNN的例子姓名 性別身高(米) 類別 Kristina 女1.6矮 Jim 男2 高 Maggie 女1.83

高 Martha

女1.88 高 Stephanie 女1.7 矮 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

中等只使用身高做特征，K=3，對于樣本<kate,1.8,女>應屬于哪個類別？僅使用同性別樣本做訓練，K=3，對于樣本<kate,1.8,女>應屬于哪個類別？2023/11/2918數(shù)據(jù)挖掘--分類第三章分類方法

內(nèi)容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法

貝葉斯分類實值預測與分類有關(guān)的問題2023/11/2919數(shù)據(jù)挖掘--分類決策樹表示與例子年齡收入是否學生信用狀況是否買電腦<=30高否一般否30—40高否一般是>40中否一般是>40低是一般是>40低是良好否30—40低是良好是<=30中否一般否<=30低是一般是年齡？學生？是信用？<=3030—40>40否是良好一般是否是否2023/11/2920數(shù)據(jù)挖掘--分類決策樹表示與例子決策樹（DecisionTree）的每個內(nèi)部結(jié)點表示一個屬性（特征），每個分枝代表一個特征的一個（類）取值；每個樹葉結(jié)點代表類或類分布。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性的比較，從而判斷從該結(jié)點向下的分枝，在決策樹的葉結(jié)點得到結(jié)論。從決策樹的根到葉結(jié)點的一條路徑就對應著一條規(guī)則，整棵決策樹就對應著一組規(guī)則。決策樹分類模型的建立通常分為兩個步驟：決策樹生成決策樹修剪2023/11/2921數(shù)據(jù)挖掘--分類決策樹生成算法描述算法4-3Generate_decision_tree(samples,attribute_list)/*決策樹生成算法*/輸入：訓練樣本samples，由離散值屬性表示；輸出：一棵決策樹。（1）創(chuàng)建結(jié)點N；（2）IF

samples

都在同一個類C

THEN

返回N

作為葉結(jié)點，以類C標記；（3）IFattribute_list為空THEN

返回N作為葉結(jié)點，標記為samples中最普通的類；//多數(shù)表決（4）選擇attribute_list中具有最高信息增益的屬性test_attribute；（5）標記結(jié)點N為test_attribute；（6）FORtest_attribute的每個取值ai由結(jié)點N長出一個條件為test_attribute=ai的分枝；（7）設(shè)si是samples中test_attribute=ai的樣本的集合；//一個劃分（8）IF

si為空THEN

回退到test_attribute的其它取值；（9）ELSE

加上一個由Generate_decision_tree(si，attribute_list-test_attribute)返回的結(jié)點；2023/11/2922數(shù)據(jù)挖掘--分類決策樹修剪算法基本的決策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓練集擬合。在有噪聲情況下，將導致過分擬合（Overfitting），即對訓練數(shù)據(jù)的完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預測性能下降。比如每個樣本都是一個葉子節(jié)點?，F(xiàn)實世界的數(shù)據(jù)一般不可能是完美的，可能缺值（MissingValues）；數(shù)據(jù)不完整；含有噪聲甚至是錯誤的。剪枝是一種克服噪聲的基本技術(shù)，同時它也能使樹得到簡化而變得更容易理解。有兩種基本的剪枝策略。2023/11/2923數(shù)據(jù)挖掘--分類決策樹修剪算法預先剪枝（Pre-Pruning）：在生成樹的同時決定是繼續(xù)對不純的訓練子集進行劃分還是停機。后剪枝（Post-Pruning）：是一種擬合+化簡（fitting-and-simplifying）的兩階段方法。首先生成與訓練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時要用到一個測試數(shù)據(jù)集合（TuningSet或AdjustingSet），如果存在某個葉子剪去后能使得在測試集上的準確度或其他測度不降低（不變得更壞），則剪去該葉子；否則停機。理論上講，后剪枝好于預先剪枝，但計算復雜度大。2023/11/2924數(shù)據(jù)挖掘--分類決策樹修剪算法構(gòu)造好的決策樹的關(guān)鍵在于如何選擇屬性進行樹的拓展。研究結(jié)果表明，一般情況下,樹越小則樹的預測能力越強。由于構(gòu)造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略來進行。屬性選擇依賴于各種對例子子集的不純度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距離度量（DistanceMeasure）、J-measure等。2023/11/2925數(shù)據(jù)挖掘--分類ID3算法ID3是一個著名決策樹生成方法：決策樹中每一個非葉結(jié)點對應著一個非類別屬性(特征)，樹枝代表這個屬性的值。一個葉結(jié)點代表從樹根到葉結(jié)點之間的路徑對應的記錄所屬的類別屬性值。每一個非葉結(jié)點都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。采用信息增益來選擇能夠最好地將樣本分類的屬性。對ID3算法采用如下方式講解：給出信息增益對應的計算公式；通過一個例子來說明它的主要過程。2023/11/2926數(shù)據(jù)挖掘--分類信息增益的計算設(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ù)集的信息值。問題：信息值的取值范圍是什么？2023/11/2927數(shù)據(jù)挖掘--分類信息增益的計算例題：數(shù)據(jù)集有2個類，求該數(shù)據(jù)集的信息值。年齡收入是否學生信用狀況是否買電腦<=30高否良好否30—40高是良好是>40中是良好是>40低是良好是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是良好是2023/11/2928數(shù)據(jù)挖掘--分類信息增益的計算設(shè)屬性A具有個不同值{a1,a2,…,av}，可以用屬性A將樣本S劃分為{S1,S2,…,Sv}，設(shè)Sij是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出：有A進行分枝將獲得的信息增益可以由下面的公式得到：

使用屬性后的信息值未使用屬性的信息值2023/11/2929數(shù)據(jù)挖掘--分類信息增益的計算例題：數(shù)據(jù)集有2個類。使用是否學生作為屬性，求該屬性的信息增益。使用信用狀況作為屬性，求該屬性的信息增益。年齡收入是否學生信用狀況是否買電腦<=30高否良好否30—40高是良好是>40中是良好是>40低是良好是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是良好是2023/11/2930數(shù)據(jù)挖掘--分類ID3算法的例子選擇信息增益最大的屬性特征作為根節(jié)點。Gain(年齡)=0.342Gain(收入)=0Gain(是否學生)=0.333Gain(信用狀況)=0年齡收入是否學生信用狀況是否買電腦<=30高否良好否30—40高是一般是>40中是一般是>40低是一般是<=30低是良好否30—40低是良好否<=30中否良好否<=30低是一般是年齡？？？是<=3030—40>402023/11/2931數(shù)據(jù)挖掘--分類ID3算法的例子對于<=30的分支Gain(收入)=0.315Gain(是否學生)=0.315Gain(信用狀況)=0.815對于30—40的分支Gain(收入)=1Gain(是否學生)=0Gain(信用狀況)=1年齡收入是否學生信用狀況是否買電腦<=30高否良好否<=30中否良好否<=30低是一般是<=30低是良好否30—40低是良好否30—40高是一般是年齡？信用狀況？收入？是<=3030—40>40否是是否良好一般高低2023/11/2932數(shù)據(jù)挖掘--分類ID3算法的性能分析ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間。ID3算法在搜索的每一步都使用當前的所有訓練樣例，大大降低了對個別訓練樣例錯誤的敏感性。因此，通過修改終止準則，可以容易地擴展到處理含有噪聲的訓練數(shù)據(jù)。2023/11/2933數(shù)據(jù)挖掘--分類ID3算法的性能分析ID3算法在搜索過程中不進行回溯。所以，它易受無回溯的爬山搜索中的常見風險影響：收斂到局部最優(yōu)而不是全局最優(yōu)。ID3算法只能處理離散值的屬性。信息增益度量存在一個內(nèi)在偏置，它偏袒具有較多值的屬性。例如，如果有一個屬性為日期，那么將有大量取值，這個屬性可能會有非常高的信息增益。假如它被選作樹的根結(jié)點的決策屬性則可能形成一顆非常寬的樹，這棵樹可以理想地分類訓練數(shù)據(jù)，但是對于測試數(shù)據(jù)的分類性能可能會相當差。ID3算法增長樹的每一個分支的深度，直到屬性的使用無法導致信息增益。當數(shù)據(jù)中有噪聲或訓練樣例的數(shù)量太少時，產(chǎn)生的樹會過渡擬合訓練樣例。問題：ID3樹可以導致過度擬合，那是否它一定能對訓練集完全正確的分類呢？2023/11/2934數(shù)據(jù)挖掘--分類C4.5算法對ID3的主要改進C4.5算法是從ID3算法演變而來，除了擁有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：用信息增益比例的概念；合并具有連續(xù)屬性的值；可以處理具有缺少屬性值的訓練樣本；通過使用不同的修剪技術(shù)以避免樹的過度擬合；K交叉驗證；規(guī)則的產(chǎn)生方式等。2023/11/2935數(shù)據(jù)挖掘--分類信息增益比例的概念信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來的，一個屬性的信息增益比例用下面的公式給出：其中假如我們以屬性A的值為基準對樣本進行分割的化，Splitl(A)就是前面熵的概念。

2023/11/2936數(shù)據(jù)挖掘--分類信息增益比例的計算例題：數(shù)據(jù)集有2個類。使用是否學生作為屬性，求該屬性的信息增益比例。使用年齡作為屬性，求該屬性的信息增益比例。討論：信息增益和信息增益比例的差異在哪里？年齡收入是否學生信用狀況是否買電腦<=20高否良好否20—30高是良好是30—40中是良好是40—50低是良好是50—60低否良好否60—70低否良好否70—80中否良好否>80低是良好是2023/11/2937數(shù)據(jù)挖掘--分類C4.5處理連續(xù)值的屬性對于連續(xù)屬性值，C4.5其處理過程如下：根據(jù)屬性的值，對數(shù)據(jù)集排序；用不同的閾值將數(shù)據(jù)集動態(tài)的進行劃分；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值、增益及增益比；在每一個屬性會變?yōu)槿蓚€取值，即小于閾值或大于等于閾值。簡單地說，針對屬性有連續(xù)數(shù)值的情況，則在訓練集中可以按升序方式排列。如果屬性A共有n種取值，則對每個取值vj（j=1，2，┄，n），將所有的記錄進行劃分：一部分小于vj；另一部分則大于或等于vj。針對每個vj計算劃分對應的增益比率，選擇增益最大的劃分來對屬性A進行離散化。2023/11/2938數(shù)據(jù)挖掘--分類C4.5處理連續(xù)值的屬性例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。根據(jù)屬性的值，對數(shù)據(jù)集排序；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值、增益及增益比；在每一個屬性會變?yōu)槿蓚€取值，即小于閾值或大于等于閾值。收入是否買電腦2500否3000否3200否4050否4865是6770是9800是12000是2023/11/2939數(shù)據(jù)挖掘--分類C4.5處理連續(xù)值的屬性例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。選擇增益最大的劃分來對屬性A進行離散化。GainRatio(劃分：2750)=0.2GainRatio(劃分：3100)=0.39GainRatio(劃分：3625)=0.53GainRatio(劃分：4458)=1GainRatio(劃分：？)=0.53GainRatio(劃分：8285)=0.39GainRatio(劃分：10900)=0.2收入小于4458合并為收入低收入大于等于4458合并為收入高收入是否買電腦收入（離散化）2500否3000否3200否4050否4865是6770是9800是12000是2023/11/2940數(shù)據(jù)挖掘--分類C4.5的其他處理C4.5處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對屬性和每一個值賦予一個概率，取得這些概率，取得這些概率依賴于該屬性已知的值。規(guī)則的產(chǎn)生：一旦樹被建立，就可以把樹轉(zhuǎn)換成if-then規(guī)則。規(guī)則存儲于一個二維數(shù)組中，每一行代表樹中的一個規(guī)則，即從根到葉之間的一個路徑。表中的每列存放著樹中的結(jié)點。2023/11/2941數(shù)據(jù)挖掘--分類C4.5算法例子樣本數(shù)據(jù)天氣

溫度

濕度

風

網(wǎng)球Sunny Hot 85 false NoSunny Hot 90 true NoOvercast Hot 78 false YesRain Mild 96 false YesRain Cool 80 false YesRain Cool 70 true NoOvercast Cool 65 true YesSunny Mild 95 false NoSunny Cool 70 false YesRain Mild 80 false YesSunny Mild 70 true YesOvercast Mild 90 true YesOvercast Hot 75 false YesRain Mild 80 true No（1）首先對濕度進行屬性離散化，針對上面的訓練集合，通過檢測每個劃分而確定最好的劃分在75處，則這個屬性的范圍就變?yōu)閧（<=75，>75）}。（2）計算目標屬性打網(wǎng)球分類的期望信息：

（3）計算每個屬性的GainRatio：

2023/11/2942數(shù)據(jù)挖掘--分類C4.5算法例子（4）選取最大的GainRatio，根據(jù)天氣的取值，得到三個分枝。（5）再擴展各分枝節(jié)點，得到最終的決策樹（見課本圖4-7）。問題：就天氣=Sunny這一分支，請用C4.5算法構(gòu)造決策樹。樣本數(shù)據(jù)天氣

溫度

濕度

風

網(wǎng)球Sunny Hot 85 false NoSunny Hot 90 true NoSunny Mild 95 false NoSunny Cool 70 false YesSunny Mild 70 true Yes2023/11/2943數(shù)據(jù)挖掘--分類第三章分類方法

內(nèi)容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法貝葉斯分類實值預測與分類有關(guān)的問題2023/11/2944數(shù)據(jù)挖掘--分類貝葉斯分類定義4-3設(shè)X是類標號未知的數(shù)據(jù)樣本。設(shè)H為某種假定，如數(shù)據(jù)樣本X屬于某特定的類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為黃色的確信程度。2023/11/2945數(shù)據(jù)挖掘--分類樸素貝葉斯分類的工作原理觀測到的樣本具有屬性收入低是學生信用良好現(xiàn)在的問題相當于比較兩個條件概率的大小P(買電腦|收入低,是學生,信用良好)P(不買電腦|收入低,是學生,信用良好)收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是良好是低否良好否低否良好否中否良好否低是良好？2023/11/2946數(shù)據(jù)挖掘--分類樸素貝葉斯分類樸素貝葉斯分類的工作過程如下：(1)

每個數(shù)據(jù)樣本用一個n維特征向量X={x1，x2，……，xn}表示，分別描述對n個屬性A1，A2，……，An樣本的n個度量。(2)假定有m個類C1，C2，…，Cm，給定一個未知的數(shù)據(jù)樣本X（即沒有類標號），分類器將預測X屬于具有最高條件概率（條件X下）的類。也就是說，樸素貝葉斯分類將未知的樣本分配給類Ci（1≤i≤m）當且僅當P(Ci|X)>P(Cj|X)，對任意的j=1，2，…，m，j≠i。收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是良好是低否良好否低否良好否中否良好否低是良好？2023/11/2947數(shù)據(jù)挖掘--分類樸素貝葉斯分類(續(xù))根據(jù)貝葉斯定理：

由于P(X)對于所有類為常數(shù)，只需要P(X|Ci)*P(Ci)最大即可。注意，類的先驗概率可以用P(Ci)=Si/S計算，其中Si是類Ci中的訓練樣本數(shù)，而S是訓練樣本總數(shù)。因此問題就轉(zhuǎn)換為計算P(X|Ci)。

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

其中概率P(x1|Ci)，P(x2|Ci)，……，P(xn|Ci)可以由訓練樣本估值。如果Ak是離散屬性，則P(xk|Ci)=sik|si，其中sik是在屬性Ak上具有值xk的類Ci的訓練樣本數(shù)，而si是Ci中的訓練樣本數(shù)。

如果Ak是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而，

是高斯分布函數(shù)，而分別為平均值和標準差。

2023/11/2950數(shù)據(jù)挖掘--分類樸素貝葉斯分類(續(xù))例題：計算P(收入低|不買電腦)P(是學生|不買電腦)P(信用良好|不買電腦)假設(shè)收入，是否學生，信用狀況互相獨立，計算P(收入低，是學生，信用良好|不買電腦)收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是良好是低否一般否低否良好否中否良好否低是良好？2023/11/2951數(shù)據(jù)挖掘--分類樸素貝葉斯分類(續(xù))對未知樣本X分類，也就是對每個類Ci，計算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當且僅當P(Ci|X)>P(Cj|X)，1≤j≤m，j≠i，換言之，X被指派到其P(X|Ci)*P(Ci)最大的類。

2023/11/2952數(shù)據(jù)挖掘--分類樸素貝葉斯分類舉例數(shù)據(jù)樣本有屬性年齡，收入，是否學生和信用狀況。類標號屬性”是否買電腦“有兩個不同值{是，否}。設(shè)C1對應于類”買電腦”；則C2對應于類”不買電腦”。我們希望分類的未知樣本為:X=（”年齡<=30”，”收入=中”，”是學生”，”信用一般”）年齡收入是否學生信用狀況是否買電腦<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2953數(shù)據(jù)挖掘--分類樸素貝葉斯分類舉例我們需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算：P(C1)=P(買電腦）=P(C2)=P(不買電腦）=計算P(X|Ci)P（"年齡<=30","收入=中","是學生","信用一般"|買電腦)P（"年齡<=30","收入=中","是學生","信用一般"|不買電腦)年齡收入是否學生信用狀況是否買電腦<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2954數(shù)據(jù)挖掘--分類樸素貝葉斯分類舉例P（"年齡<=30","收入=中","是學生","信用一般"|買電腦)=P（"年齡<=30"|買電腦)*P（"收入=中"|買電腦)*P（"是學生"|買電腦)*P（"信用一般"|買電腦)P（"年齡<=30","收入=中","是學生","信用一般"|不買電腦)=P（"年齡<=30"|不買電腦)*P（"收入=中"|不買電腦)*P（"是學生"|不買電腦)*P（"信用一般"|不買電腦)年齡收入是否學生信用狀況是否買電腦<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2955數(shù)據(jù)挖掘--分類樸素貝葉斯分類舉例假設(shè)屬性之間獨立P（"年齡<=30","收入=中","是學生","信用一般"|買電腦)=0.222*0.444*0.667*0.667=0.044；P（"年齡<=30","收入=中","是學生","信用一般"|不買電腦)=0.600*0.400*0.200*

0.400=0.019；P（X|買電腦)>P（X|不買電腦)，因此對于樣本X，樸素貝葉斯分類預測為"是"。年齡收入是否學生信用狀況是否買電腦<=30高否一般否<=30高否良好否31—40高否一般是>40中否一般是>40低是一般是>40低是良好否31—40低是良好是<=30中否一般否<=30低是一般是>40中是一般是<=30中是良好是31—40中否良好是31—40高是一般是>40中否良好否<=30中是一般？？？2023/11/2956數(shù)據(jù)挖掘--分類第三章分類方法

內(nèi)容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法貝葉斯分類基于規(guī)則的分類

與分類有關(guān)的問題2023/11/2957數(shù)據(jù)挖掘--分類使用IF-THEN規(guī)則分類使用規(guī)則的分類法是使用一組IF-THEN規(guī)則進行分類。IF條件THEN結(jié)論比如IF(年齡<20AND學生=是)THEN買電腦=是IF的部分稱為前提，THEN的部分稱為規(guī)則的結(jié)論規(guī)則可以用它的覆蓋率和準確率來評價ncovers是條件(前提)覆蓋的樣本數(shù)，ncorrect是規(guī)則正確分類的樣本數(shù)。2023/11/2958數(shù)據(jù)挖掘--分類使用IF-THEN規(guī)則分類規(guī)則(收入=低)^(信用狀況良好)(是否買電腦=是)的覆蓋率為3/8,而它測準確率為1/3。規(guī)則(信用狀況=良好)(是否買電腦=否)的覆蓋率為7/8,而它測準確率為4/7。收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是良好是低否一般否低否良好否中否良好否低是良好否2023/11/2959數(shù)據(jù)挖掘--分類使用IF-THEN規(guī)則分類如果一個規(guī)則R被一個樣本X滿足，則稱規(guī)則R被X觸發(fā)。比如X=(年齡=18，是學生，信用良好)R為IF(年齡<20AND學生=是)THEN買電腦=是則X的類別為買電腦如果一個樣本X同時觸發(fā)了多個規(guī)則，我們需要制定解決沖突的策略。規(guī)模序激活具有最多屬性測試的觸發(fā)規(guī)則規(guī)則序?qū)⒁?guī)則按重要性進行排序，按順序進行促發(fā)如果一個樣本X無法促發(fā)任何規(guī)則建立一個缺省或者默認規(guī)則2023/11/2960數(shù)據(jù)挖掘--分類使用決策樹來提取規(guī)則決策樹的規(guī)則是互斥與窮舉的互斥意味著規(guī)則不會存在沖突，因此每個樣本只能促發(fā)一個規(guī)則窮舉意味著一個樣本總能促發(fā)一個規(guī)則由于每個樹葉對應一個一條規(guī)則，提取的規(guī)則并不比決策樹簡單。年齡？信用狀況？收入？是<=3030—40>40否是是否良好一般高低2023/11/2961數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納在提取規(guī)則時，一個現(xiàn)實的問題是是否需要對現(xiàn)有規(guī)則進行拓展，IF(年齡<20)THEN買電腦是否需要拓展為IF(年齡<20AND學生=是)THEN買電腦衡量規(guī)則好壞應同時考慮覆蓋度與準確率準確率太低覆蓋度太低2023/11/2962數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納有兩種衡量規(guī)則好壞的度量FOIL_Gain的定義如下分別對應于兩個規(guī)則R與R'。正在學習的類稱為正樣本(pos)，而其他類稱為負樣本(neg),pos(neg)為規(guī)則R覆蓋的正負樣本，而pos'(neg')為規(guī)則R'覆蓋的正負樣本。2023/11/2963數(shù)據(jù)挖掘--分類判斷規(guī)則(收入=低)(是否買電腦=否)是否需要拓展為規(guī)則(收入=低)^(信用狀況=良好)(是否買電腦=否)收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是一般是低否良好否低否良好否中否良好是低是良好否2023/11/2964數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納似然率統(tǒng)計量的的定義如下其中m是分類的類別數(shù)。fi為滿足規(guī)則的樣本中屬于類i的概率，ei為屬于類i的期望(基準)概率。似然率越高，說明規(guī)則越理想。2023/11/2965數(shù)據(jù)挖掘--分類分別計算規(guī)則(收入=低)(是否買電腦=否)與規(guī)則(收入=低)^(信用狀況=良好)(是否買電腦=否)的似然率。收入是否學生信用狀況是否買電腦高否良好否高是良好是中是良好是低是一般是低否良好否低否良好否中否良好是低是良好否2023/11/2966數(shù)據(jù)挖掘--分類

順序覆蓋算法終止條件包括，類c沒有樣本或者返回的規(guī)則質(zhì)量低于用戶指定的閾值等。輸入：D，類標記已知的樣本的集合。Att_vals,所有屬性與它們可能值得集合。輸出：IF-THEN規(guī)則的集合。（1）Rule_set={}；//規(guī)則的初始集為空集（2）FOR每個類cDO

（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）ENDFOR（9）返回Rule_Set2023/11/2967數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納Rule_set={}；選擇一個類“買電腦”；選擇一個包含一個屬性的規(guī)則(收入=低)

“買電腦”分別計算其它包含一個屬性的規(guī)則的相對于已選擇規(guī)則的FOIL_Gain(收入=高)“買電腦”(學生=是)

“買電腦”(學生=否)

“買電腦”(信用=良好)

“買電腦”(信用=一般)

“買電腦”收入是否學生信用狀況是否買電腦高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2968數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納分別計算規(guī)則的Foil_gain(收入=高)"買電腦"為1.74(學生=是)"買電腦"為0(學生=否)"買電腦"為0(信用=良好)"買電腦"為0(信用=一般)"買電腦"為0選擇Foil_gain最高的規(guī)則(收入=高)"買電腦"收入是否學生信用狀況是否買電腦高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2969數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納對最好的規(guī)則R進行拓展(收入=高)"買電腦"在規(guī)則R中添加一個屬性，得到拓展以后的規(guī)則R'(收入=高)^(學生=是)(收入=高)^(學生=否)(收入=高)^(信用=良好)(收入=高)^(信用=一般)分別計算這些規(guī)則的相對于R的Foil_gain收入是否學生信用狀況是否買電腦高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2970數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納分別計算規(guī)則的Foil_gain(收入=高)^(學生=是)為0.84(收入=高)^(學生=否)為-1.16(收入=高)^(信用=良好)為0.84(收入=高)^(信用=一般)為-1.16選擇Foil_gain最高的規(guī)則(收入=高)^(學生=是)

(收入=高)^(信用=良好)由于這兩個規(guī)則準確率已經(jīng)是100%，因此不用拓展收入是否學生信用狀況是否買電腦高否一般否高是一般是高是良好是高否良好是低否一般是低是良好否低是良好否低否一般否2023/11/2971數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納將規(guī)則覆蓋的樣本從數(shù)據(jù)集D中刪除，對剩下的正樣本生成規(guī)則收入是否學生信用狀況是否買電腦高否一般否低否一般是低是良好否低是良好否低否一般否2023/11/2972數(shù)據(jù)挖掘--分類使用順序覆蓋算法的規(guī)則歸納收入是否學生信用狀況是否買電腦高否一般否低是良好否低是良好否低否一般否選擇另外一個類“不買電腦”(生成其它類的規(guī)則)；選擇一個包含一個屬性的規(guī)則(收入=低)

“不買電腦”分別計算其它包含一個屬性的規(guī)則的相對于已選擇規(guī)則的FOIL_Gain(收入=高)“不買電腦”(學生=是)

“不買電腦”(學生=否)

“不買電腦”(信用=良好)

“不買電腦”(信用=一般)

“不買電腦”2023/11/2973數(shù)據(jù)挖掘--分類第三章分類方法

內(nèi)容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法貝葉斯分類基于規(guī)則的分類實值預測

2023/11/2974數(shù)據(jù)挖掘--分類實值預測分類：把樣本分配到若干類之一(離散的)。比如預測是普通員工、中層管理還是高級管理人員預測：預測樣本的某個屬性值(連續(xù)的)。比如預測收入工作年限周工作時間月薪14025004483000540350074040008484500640？948？2023/11/2975數(shù)據(jù)挖掘--分類實值預測實值預測方法有兩種線性回歸和多元回歸非線性回歸2023/11/2976數(shù)據(jù)挖掘--分類實值預測在回歸分析中，只包括一個自變量和一個因變量，且二者的關(guān)系可用一條直線近似表示，這種回歸分析稱為一元線性回歸分析。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};2023/11/2977數(shù)據(jù)挖掘--分類一元線性回歸模型給n個隨機樣本(Yi,Xi,)，則Y與X的線性回歸模型可以寫為其中b0

，b1是參數(shù)

是被稱為誤差項的隨機變量,這是由于我們建立的線性回歸模型可能是不完美的

工作年限月薪12500430005350074000845006？9？2023/11/2978數(shù)據(jù)挖掘--分類線性回歸模型的求解回歸模型的求解相當于求解β使得一元線性回歸分析的求解2023/11/2979數(shù)據(jù)挖掘--分類一元線性回歸模型例題：請建立右表的線性回歸模型。

工作年限月薪12500430005350074000845006？9？2023/11/2980數(shù)據(jù)挖掘--分類多元線性回歸模型給n個隨機樣本(Yi,Xi1,Xi2,...,Xip)，則Y與X的線性回歸模型可以寫為其中b0

，b1，b2，，bn是參數(shù)

是被稱為誤差項的隨機變量,這是由于我們建立的線性回歸模型可能是不完美的

工作年限周工作時間月薪240350044832005406500104058001248720018404300640？948？2023/11/2981數(shù)據(jù)挖掘--分類線性回歸模型的求解回歸模型的求解相當于求解β使得多元線性回歸分析的求解其中X為2023/11/2982數(shù)據(jù)挖掘--分類AQ算法多元回歸模型的求解在許多軟件中都可以得到，比如Matlab，SAS，SPSS，Weka等。2023/11/2983數(shù)據(jù)挖掘--分類AQR算法有關(guān)定義AQR為每一個分類推導出一條規(guī)則，每一條規(guī)則形式如下：if<cover>thenpredict<class>。在一個屬性上的基本測試被稱為一個Selector。下面是一些Selector的例子：<Cloudy=yes>或<Temp>60>。AQR允許測試做{=，≤，≥，≠}。Selectors的合取被稱為復合（Complex），Complexes之間的析取被稱為覆蓋（Cover）。如果一個表達式對某個樣本為真，則我們稱其為對這個樣本的一個覆蓋。這樣，一個空Complex覆蓋所有的樣本，而一個空Cover不覆蓋任何樣本。在AQR中，一個新樣本被區(qū)分是看其屬于哪個推導出來的規(guī)則。如果該樣本只滿足一條規(guī)則，則這個樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預測的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。2023/11/2984數(shù)據(jù)挖掘--分類AQR算法描述算法4-5AQR輸入：正例樣本POS；反例樣本NEG。輸出：覆蓋COVER。（1）COVER=Φ；//初始化COVER為空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；/選取一個種子SEED，例如沒有被COVER覆蓋的一個正樣例（4）CallprocedureSTAR（SEED，NEG）；//產(chǎn)生一個能覆蓋種子而同時排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；/*從星中選取一個最好的復合*/（6）AddBESTasanextradisjucttoCOVER/*把最好的復合與COVER合取，形成新的COVER*/（7）END（8）RETURNCOVER.在算法AQR中調(diào)用了過程STAR，來排除所有的反例，產(chǎn)生覆蓋種子的星。2023/11/2985數(shù)據(jù)挖掘--分類AQR算法描述(續(xù))算法4-6

STAR輸入：種子SEED；反例NEG。輸出：星STAR。（1）初始化STAR為空Complex（2）WHILEoneormoreComplexesinSTARcoverssomenegativeexamplesinNEGBEGIN/*如果STAR中的一個或多個Complex覆蓋NEG中的負樣例*/（3）SelectanegativeexampleEnegcoveredbyaComplexinSTAR；/*選取一個被STAR中的Complex覆蓋的負樣例*/（4）LetEXTENSIONbeallSelectorsthatcoverSEEDbutnotENEG；/*令EXTENSION為那些覆蓋SEED但不覆蓋ENEG的Selectors；*/（5）LetSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令STAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6）RemoveallComplexesinSTARsubsumedbyotherComplexesinSTAR；/*從STAR中除去被其他Complexes所包含的Complexes；*/（7）RemovetheworstComplexesfromSTARUNTILsizeofSTARislessthanorequaltouser-definedmaximum（maxstar）/*刪除STAR中最壞的Complex直到STAR的大小等于或小于用戶定義的最大數(shù)目maxstar*/（8）END（9）RETURNSTAR./*返回一系列覆蓋SEED但不覆蓋NEG的規(guī)則*/2023/11/2986數(shù)據(jù)挖掘--分類AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：micro，tiny，mid，big，huge，vast）type（屬性值：bicycle，motorcycle，car，prop，jet，glider）現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示：下面給出用AQR算法對giant2-wheeler類的規(guī)則進行獲取過程，具體步驟如下：（１）COVER={}。（２）空cover不覆蓋任何樣本，進入循環(huán)。（３）一開始COVER并沒有覆蓋任何正例，假定從正例中選取的SEED為{size=huge，type=bicycle}。（４）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個覆蓋SEED但不包含NEG的STAR集合；初始化STAR為空，即STAR={}。空的complex覆蓋所有樣例，STAR覆蓋多個負樣例，進入循環(huán)。

a)選取一個被STAR中的復合覆蓋的負樣例ENEG，假定被選取的是Eneg={size=tiny，type=motorcycle}。

b)使EXTENSION為所有覆蓋SEED但不覆蓋ENEG的選擇，則EXTENSION包括size=huge和type=bicycle，則又根據(jù)STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=huge

type=bicycle}。c)在這里定義maxstar為2，可不對STAR進行精簡。d)接著選取另一個被STAR中的復合覆蓋的負樣例ENEG，顯然已經(jīng)沒有這樣的負樣例，因此，STAR={size=huge

type=bicycle}。從STAR（SEED，NEG）返回。反例樣本sizetypeclassTinymotorcycleconventionaltransportationtinycarconventionaltransportationmidcarconventionaltransportationmicrojetfastplaneTinyjetfastplaneMidjetfastplane正例樣本sizetypeclassHugebicyclegiant2-wheelerHugemotorcyclegiant2-wheeler2023/11/2987數(shù)據(jù)挖掘--分類AQR算法舉例（5）BEST={size=huge

type=bicycle}，COVER={size=huge

type=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)使EXTENSION為所有覆蓋SEED但不覆蓋Eneg的選擇，則EXTENSION包括size=huge，則又根據(jù)STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=huge}；c)接著選取另一個被STAR中的復合覆蓋的負樣例Eneg，顯然已經(jīng)沒有這樣的負樣例，因此，STAR={size=huge}；d)接著選取另一個被STAR中的復合覆蓋的負樣例ENEG，顯然已經(jīng)沒有這樣的負樣例，因此，STAR={size=huge

type=bicycle}。從STAR（SEED，NEG）返回。（8）BEST={size=huge}，將BEST添加到COVER中，COVER={size=huge

type=bicycle

size=huge}={size=huge}。（9）這時，COVER已經(jīng)覆蓋到全部的正例，則算法結(jié)束。輸出規(guī)則為gaint2-wheeler

size=huge。假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：micro，tiny，mid，big，huge，vast）type（屬性值：bicycle，motorcycle，car，prop，jet，glider）現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示：反例樣本sizetypeclassTinymotorcycleconventionaltransportationtinycarconventionaltransportationmidcarconventionaltransportationmicrojetfastplaneTinyjetfastplaneMidjetfastplane正例樣本sizetypeclassHugebicyclegiant2-wheelerHugemotorcyclegiant2-wheeler2023/11/2988數(shù)據(jù)挖掘--分類CN2算法描述CN2使用一種基于噪音估計的啟發(fā)式方法，使用這種方法可以不用對所有的訓練樣本進行正確的區(qū)分，但是規(guī)約出的規(guī)則在對新數(shù)據(jù)的處理上有很好的表現(xiàn)。算法4-7CN2輸入：E/*E為訓練樣本*/輸出：RULE_LIST/*返回一個覆蓋若干樣例的規(guī)則*/（1）LetRULE_LISTbetheemptylist；/*初始化RULES_LIST為空；*/（2）REPEAT（3）LetBEST_CPXbeFind_Best_Complex（E）；/*尋找最佳的規(guī)則Find_Best_Complex（E）并將其結(jié)果放入BEST_CPX中；*/（4）IFBEST_CPXisnotnilTHENBEGIN（5）LetE’betheexamplescoveredbyBEST_CPX；/*令E’為BEST_CPX覆蓋的所有樣例*/（6）RemovefromEtheexamplesE′coveredbyBEST_CPX；/*從訓練樣本E中除去E’，即E=E-E’；*/（7） LetCbethemostcommonclassofexamplesinE’；/*令C為樣本子集E’中最頻繁的分類標號；*/（8）Addtherule‘ifBEST_CPXthenclass=C’totheendofRULE_LIST；/*將規(guī)則‘ifBEST_CPXthenclass=C’添加到RULES_LIST中*/（9）END（10）UNTILBEST_CPXisnilorEisempty./*直到BEST_CPX為空或者訓練樣本E為空*/（11）RETURNRULE_LIST算法CN2需要通過調(diào)用函數(shù)Find_Best_Complex，它的描述寫成下面算法4-8。2023/11/2989數(shù)據(jù)挖掘--分類CN2算法描述(續(xù))算法4-8Find_Best_Complex輸入：E/*E為訓練樣本*/輸出：BEST_CPX/*返回最佳的規(guī)則BEST_CPX*/（1）LetthesetSTARcontainonlytheemptyComplex；/*初始化集合STAR為空Complex；*/（2）LetBEST_CPXbenil；/*初始化BEST_CPX為空*/（3）LetSELECTORSbethesetofallpossibleSelectors；/*集合SELECTOR為所有可能的選擇*/（4）WHILESTARisnotemptyDOBEGIN（5） LetNEWSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令NEWSTAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6） RemoveallComplexesinNEWSTARthatareeitherinSTARorarenull；/*從NEWSTAR中除去包括在STAR中的Complex或者為空的Complex*/（7） FOReverycomplexCiinNEWSTAR（8）IFCiisstatisticallysignificantwhentestedonEandbetterthanBEST_CPX accordingtouser-definedcriteriawhentest