大數(shù)據(jù)分析與數(shù)據(jù)挖掘-分類方法

23九月20241大數(shù)據(jù)分析與數(shù)據(jù)挖掘—分類方法

內容提要分類的基本概念與步驟

基于距離的分類算法決策樹分類方法貝葉斯分類規(guī)則歸納與分類有關的問題23九月20242分類是數(shù)據(jù)挖掘中重要的任務分類的目的是學會一個分類器（分類函數(shù)或模型），該分類器能把待分類的數(shù)據(jù)映射到給定的類別中。分類可用于預測。從利用歷史數(shù)據(jù)紀錄中自動推導出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進行類預測。分類具有廣泛的應用，例如醫(yī)療診斷、信用卡系統(tǒng)的信用分級、圖像模式識別等。分類器的構造依據(jù)的方法很廣泛：統(tǒng)計方法：包括貝葉斯法和非參數(shù)法等。機器學習方法：包括決策樹法和規(guī)則歸納法。神經(jīng)網(wǎng)絡方法。其他，如粗糙集等（在前面緒論中也介紹了相關的情況）。23九月20243分類方法的類型從使用的主要技術上看，可以把分類方法歸結為四種類型：基于距離的分類方法決策樹分類方法貝葉斯分類方法規(guī)則歸納方法。本章將擇選一些有代表性的方法和算法來介紹這四類分類方法。23九月20244分類問題的描述定義4-1給定一個數(shù)據(jù)庫D={t1，t2，…，tn}和一組類C={C1，…，Cm}，分類問題是去確定一個映射f:D

C，使得每個元組ti被分配到一個類中。一個類Cj包含映射到該類中的所有元組，即Cj={ti|f(ti)=Cj，1≤i≤n，而且ti

D}。例如，把學生的百分制分數(shù)分成A、B、C、D、F五類，就是一個分類問題：D是包含百分制分數(shù)在內的學生信息，C={A、B、C、D、F}。解決分類問題的關鍵是構造一個合適的分類器：從數(shù)據(jù)庫到一組類別集的映射。一般地，這些類是被預先定義的、非交疊的。23九月20245數(shù)據(jù)分類的兩個步驟1．建立一個模型，描述預定的數(shù)據(jù)類集或概念集數(shù)據(jù)元組也稱作樣本、實例或對象。為建立模型而被分析的數(shù)據(jù)元組形成訓練數(shù)據(jù)集。訓練數(shù)據(jù)集中的單個元組稱作訓練樣本，由于提供了每個訓練樣本的類標號，因此也稱作有指導的學習。通過分析訓練數(shù)據(jù)集來構造分類模型，可用分類規(guī)則、決策樹或數(shù)學公式等形式提供。2．使用模型進行分類首先評估模型（分類法）的預測準確率。如果認為模型的準確率可以接受，就可以用它對類標號未知的數(shù)據(jù)元組或對象進行分類。23九月20246第三章分類方法

內容提要分類的基本概念與步驟基于距離的分類算法

決策樹分類方法貝葉斯分類規(guī)則歸納與分類有關的問題23九月20247基于距離的分類算法的思路定義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)被稱為相似性。在實際的計算中往往用距離來表征，距離越近，相似性越大，距離越遠，相似性越小。距離的計算方法有多種，最常用的是通過計算每個類的中心來完成。23九月20248基于距離的分類算法的一般性描述算法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.23九月20249基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結果23九月202410K-近鄰分類算法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∪wzhfi0g；（5）ELSE（6） IF

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

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

23九月202411K-means算法：根據(jù)聚類中的均值進行聚類劃分：輸入：聚類個數(shù)k以及包含n個數(shù)據(jù)對象的數(shù)據(jù)庫。輸出：滿足方差最小標準的k個聚類。23九月202412處理流程：（1）從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心。（2）循環(huán)流程（3）到（4），直到每個聚類不再發(fā)生變化為止。（3）根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離，并根據(jù)最小距離重新對相應對象進行劃分。（4）重新計算每個有變化聚類的均值（中心對象）。23九月202413k-均值算法標準均方誤差：23九月202414聚類的分析過程23九月202415坐標表示5個點｛X1,X2,X3,X4,X5｝作為一個聚類分析的二維樣本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假設要求的簇的數(shù)量k=2。對這5個點進行分類。23九月202416k-均值算法的性能分析：優(yōu)點：K-均值算法是解決聚類問題的一種典型算法，這種算法簡單、快速；對處理大型數(shù)據(jù)集，該算法是相對可伸縮的和高效的；算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當結果簇是密集的，而簇與簇之間區(qū)別明顯時，效果是較好的。23九月202417k-均值算法的性能分析：（續(xù)）缺點：K-均值算法只有在簇的平均值在被定義的情況下才能使用。要求用戶事先必須拿出k，而且對初值不敏感，對于不同的初始值，可能會導致不同的聚類結果；不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇；對于“噪聲”與孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠對平均值產生極大影響。23九月202418K-mediods算法：根據(jù)聚類中的中心對象進行劃分：輸入：聚類個數(shù)k以及包含n個數(shù)據(jù)對象的數(shù)據(jù)庫。輸出：滿足基于各聚類中心對象的方差最小標準的k個聚類。PAM(PartitioningAroundMedoids圍繞中心點劃分)23九月202419處理流程：（1）從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心代表。（2）循環(huán)流程（3）到（5），直到每個聚類不再發(fā)生變化為止。（3）依據(jù)每個聚類的中心代表對象以及各對象與這些中心對象間距離，并根據(jù)最小距離重新對相應對象進行劃分。（4）任意選擇一個非中心對象，計算其與中心對象交換的整個成本S。（5）若S為負值則交換非中心對象與中心對象以構成新聚類的k個中心對象。23九月202420為了判定一個非代表對象Oh是否是當前一個代表對象Oi的好的替代。對于每一個非中心點對象Oj，下面的四種情況被考慮：假設Oi被Oh代替作為新的中心點，Oj當前隸屬于中心點對象Oi。如果Oj離某個中心點Om最近，im，那么Oj被重新分配給Om；假設Oi被Oh代替作為新的中心點，Oj當前隸屬于中心點對象Oi。如果Oj離這個新的中心點Oh最近，那么Oj被分配給Oh；假設Oi被Oh代替作為新的中心點，但是Oj當前隸屬于另一個中心點對象Om，im。如果Oj依然離Om最近，那么對象的隸屬不發(fā)生變化；假設Oi被Oh代替作為新的中心點，但是Oj當前隸屬于另一個中心點對象Om，im。如果Oj離這個新的中心點Oh最近，那么Oi被重新分配給Oh。23九月202421總代價定義：其中Cjih表示Oj在Oi被Oh代替后產生的代價。23九月202422代價的計算公式：OI與Om是兩個原中心點，Oh將代替Oi作為新的中心點。代價函數(shù)的計算方式如下：第一種情況：Oj當前隸屬于Oi，但Oh替換Oi后Oj被重新分配給Om，則代價函數(shù)為：Cjih=d(j,m)-d(j,i)第二種情況：Oj當前隸屬于Oi，但Oh替換Oi后Oj被重新分配給Oh，則代價函數(shù)為：Cjih=d(j,h)-d(j,i)第三種情況：Oj當前隸屬于另一個中心點對象Om，im，但Oh替換Oi后Oj的隸屬不發(fā)生變化，則代價函數(shù)為：Cjih=0第四種情況：Oj當前隸屬于另一個中心點對象Om，im，但Oh替換Oi后Oj被重新分配給Oh，則代價函數(shù)為：Cjih=d(j,h)-d(j,m)23九月202423+OiPOj++Orandom+OiOj+P+Orandom用圖1表示如下：23九月202424+Oi

POj++Orandom+Oi

Oj++POrandom23九月202425例：加入空間中有五個點{A,B,C,D,E}如圖所示，各點之間的距離關系如下表，根據(jù)所給的數(shù)據(jù)進行分類。ABCDEABCDEA01223B10243C22015D24103E3353023九月202426解：第一步：建立階段：加入從5個對象中隨機抽取的2個中心點為{A,B}，則樣本被劃分為{A,C,D}與{B,E};第二步交換階段：假定中心點A,B分別被非中心點{C,D,E}替換，計算代價TCAC,TCAD,TCAE,TCBC,TCBD,TCBE;23九月202427計算TCAC如下：當A被C替換后，看A是否發(fā)生變化：A不再是一個中心點，C稱為新的中心點，屬于第一種情況。因為A離B比A離C近，A被分配到B中心點代表的簇：

CAAC=d(A,B)-d(A,A)=1當A被C替換后，看B是否發(fā)生變化：屬于第三種情況。當A被C替換以后，B不受影響：

CBAC=023九月202428計算TCAC如下(續(xù))當A被C替換后，看C是否發(fā)生變化：C原先屬于A中心點所在的簇，當A被C替換以后，C是新中心點符合圖1中的第二種情況：

CCAC=d(C,C)-d(C,A)=-2當A被C替換后，看D是否發(fā)生變化：D原先屬于A中心點所在的簇，當A被C替換以后，離D最近的中心點是C，符合圖1的第二種情況：

CDAC=d(D,C)-d(D,A)=-123九月202429計算TCAC如下(續(xù))當A被C替換后，看E是否發(fā)生變化：E原先屬于B中心點所在的簇，離E最近的中心點是B，符合圖1的第三種情況：

CEAC=0因此TCAC=-223九月202430算法的性能分析：K-中心點算法消除了k-平均算法對于孤立點的敏感性；當存在“噪聲”與孤立點數(shù)據(jù)時，k-中心點方法比k-平均方法更健壯，這是因為中心點不像平均值那么容易被極端數(shù)據(jù)影響，但是，k-中心點方法的執(zhí)行代價比k-平均方法高；算法必須指定聚類的數(shù)目k，k的取值對聚類質量有重大影響；K-中心點算法對于小的數(shù)據(jù)非常有效，但對于大數(shù)據(jù)集效率不高。23九月202431KNN的例子姓名 性別 身高(米) 類別 Kristina 女 1.6 矮 Jim 男 2 高 Maggie 女 1.9 中等 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.95 中等 Kim 女1.9 中等 Amy 女1.8 中等 Wynette 女1.75 中等 23九月202432KNN的例子“高度”用于計算距離，K=5，對<Pat，女，1.6>分類。

對T前K=5個記錄，N={<Kristina，女，1.6>、<Jim，男，2>、<Maggie，女，1.9>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對第6個記錄d=<Bob，男，1.85>，得到N={<Kristina，女，1.6>、<Bob，男，1.85>、<Maggie，女，1.9>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對第7個記錄d=<Kathy，女，1.6>，得到N={<Kristina，女，1.6>、<Bob，男，1.85>、<Kathy，女，1.6>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對第8個記錄d=<Dave，男，1.7>，得到N={<Kristina，女，1.6>、<Dave，男，1.7>、<Kathy，女，1.6>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對第9和10個記錄，沒變化。對第11個記錄d=<Debbie，女，1.8>，得到N={<Kristina，女，1.6>、<Dave，男，1.7>、<Kathy，女，1.6>、<Debbie，女，1.8>和<Stephanie，女，1.7>}。對第12到14個記錄，沒變化。對第15個記錄d=<Wynette，女，1.75>，得到N={<Kristina，女，1.6>、<Dave，男，1.7>、<Kathy，女，1.6>、<Wynette，女，1.75>和<Stephanie，女，1.7>}。最后的輸出元組是<Kristina，女，1.6>、<Kathy，女，1.6>、<Stephanie，女，1.7>、<Dave，男，1.7>和<Wynette，女，1.75>。在這五項中，四個屬于矮個、一個屬于中等。最終KNN方法認為Pat為矮個。<Wynette，女，1.75>。23九月202433第三章分類方法

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

貝葉斯分類規(guī)則歸納與分類有關的問題23九月202434決策樹表示與例子決策樹（DecisionTree）的每個內部結點表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉結點代表類或類分布。樹的最頂層結點是根結點。

buys_computer的決策樹示意23九月202435決策樹的各部分是:

根:

學習的事例集.

枝:

分類的判定條件.

葉:

分好的各個類.23九月202436決策樹分類的特點決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內部結點進行屬性值的比較并根據(jù)不同的屬性值判斷從該結點向下的分枝，在決策樹的葉結點得到結論。所以從決策樹的根到葉結點的一條路徑就對應著一條合取規(guī)則，整棵決策樹就對應著一組析取表達式規(guī)則?；跊Q策樹的分類算法的一個最大的優(yōu)點就是它在學習過程中不需要使用者了解很多背景知識（這同時也是它的最大的缺點），只要訓練例子能夠用屬性-結論式表示出來，就能使用該算法來學習。決策樹分類模型的建立通常分為兩個步驟：決策樹生成開始，數(shù)據(jù)都在根節(jié)點遞歸的進行數(shù)據(jù)分片決策樹修剪。去掉一些可能是噪音或者異常的數(shù)據(jù)23九月202437決策樹生成算法描述算法4-3Generate_decision_tree(samples,attribute_list)/*決策樹生成算法*/輸入：訓練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹。（1）創(chuàng)建結點N；（2）

IF

samples

都在同一個類C

THEN

返回N

作為葉結點，以類C標記；（3）

IFattribute_list為空

THEN

返回N作為葉結點，標記為samples中最普通的類；//多數(shù)表決（4）選擇attribute_list中具有最高信息增益的屬性test_attribute；（5）標記結點N為test_attribute；（6）

FOReachtest_attribute中的已知值ai由結點N長出一個條件為test_attribute=ai的分枝；（7）設si是samples中test_attribute=ai的樣本的集合；//一個劃分（8）IF

si為空

THEN

加上一個樹葉，標記為samples中最普通的類；（9）ELSE

加上一個由Generate_decision_tree(si，attribute_list-test_attribute)返回的結點；23九月202438決策樹生成算法描述構造好的決策樹的關鍵在于如何選擇好的屬性進行樹的拓展。研究結果表明，一般情況下或具有較大概率地說，樹越小則樹的預測能力越強。由于構造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略來進行。屬性選擇依賴于各種對例子子集的不純度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距離度量（DistanceMeasure）、J-measure、G統(tǒng)計、χ2統(tǒng)計、證據(jù)權重（WeightofEvidence）、最小描述長度（MLP）、正交法（OrtogonalityMeasure）、相關度（Relevance）和Relief等。23九月202439決策樹修剪算法基本的決策樹構造算法沒有考慮噪聲，因此生成的決策樹完全與訓練例子擬合。在有噪聲情況下，將導致過分擬合（Overfitting），即對訓練數(shù)據(jù)的完全擬合反而使對現(xiàn)實數(shù)據(jù)的分類預測性能下降?，F(xiàn)實世界的數(shù)據(jù)一般不可能是完美的，可能缺值（MissingValues）；數(shù)據(jù)不完整；含有噪聲甚至是錯誤的。剪枝是一種克服噪聲的基本技術，同時它也能使樹得到簡化而變得更容易理解。有兩種基本的剪枝策略：預先剪枝（Pre-Pruning）：在生成樹的同時決定是繼續(xù)對不純的訓練子集進行劃分還是停機。后剪枝（Post-Pruning）：是一種擬合+化簡（fitting-and-simplifying）的兩階段方法。首先生成與訓練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時要用到一個測試數(shù)據(jù)集合（TuningSet或AdjustingSet），如果存在某個葉子剪去后能使得在測試集上的準確度或其他測度不降低（不變得更壞），則剪去該葉子；否則停機。理論上講，后剪枝好于預先剪枝，但計算復雜度大。剪枝過程中一般要涉及一些統(tǒng)計參數(shù)或閾值（如停機閾值）。要防止過分剪枝（Over-Pruning）帶來的副作用。23九月202440ID3算法ID3是Quinlan提出的一個著名決策樹生成方法：決策樹中每一個非葉結點對應著一個非類別屬性，樹枝代表這個屬性的值。一個葉結點代表從樹根到葉結點之間的路徑對應的記錄所屬的類別屬性值。每一個非葉結點都將與屬性中具有最大信息量的非類別屬性相關聯(lián)。采用信息增益來選擇能夠最好地將樣本分類的屬性。為了聚焦重點，將對ID3算法采用如下方式講解：偽代碼詳細描述見課本；給出信息增益對應的計算公式；通過一個例子來說明它的主要過程。23九月202441信息增益的計算設S是s個數(shù)據(jù)樣本的集合，定義m個不同類Ci（i=1，2，…，m），設si是Ci類中的樣本數(shù)。對給定的樣本S所期望的信息值由下式給出：其中pi是任意樣本屬于Ci的概率：si

/s。設屬性A具有個不同值{a1,a2,…,av}，可以用屬性A將樣本S劃分為{S1,S2,…,Sv}，設sij是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出：有A進行分枝將獲得的信息增益可以由下面的公式得到：23九月202442例：表1為一個商場顧客數(shù)據(jù)庫。例：表1為一個商場顧客數(shù)據(jù)庫樣本集合的類別屬性為：”buy_computer”23九月20244323九月202444ID3算法1.概念提取算法CLS

1)

初始化參數(shù)C={E},E包括所有的例子,為根.

2)

IF

C中的任一元素e同屬于同一個決策類則創(chuàng)建一個葉子

節(jié)點YES終止.

ELSE

依啟發(fā)式標準,選擇特Fi={V1,V2,V3,．．．Vn}并創(chuàng)建

判定節(jié)點

劃分C為互不相交的N個集合C1,C2,C3,．．．,Cn；

3)

對任一個Ci遞歸.23九月202445ID3算法1)

隨機選擇C的一個子集W

(窗口).

2)

調用CLS生成W的分類樹DT(強調的啟發(fā)式標準在后).

3)

順序掃描C搜集DT的意外(即由DT無法確定的例子).

4)

組合W與已發(fā)現(xiàn)的意外,形成新的W.

5)

重復2)到4),直到無例外為止.23九月202446啟發(fā)式標準:只跟本身與其子樹有關,采取信息理論用熵來量度.

熵是選擇事件時選擇自由度的量度,其計算方法為

P

=

freq(Cj,S)/|S|;

INFO(S)=

-

SUM(

P*LOG(P)

)

;

SUM()函數(shù)是求j從1到n和.

Gain(X)=Info(X)-Infox(X);

Infox(X)=SUM(

(|Ti|/|T|)*Info(X);

為保證生成的決策樹最小,ID3算法在生成子樹時,選取使生成的子樹的熵(即Gain(S))最小的的特征來生成子樹.23九月202447ID3算法對數(shù)據(jù)的要求1.

所有屬性必須為離散量.

2.

所有的訓練例的所有屬性必須有一個明確的值.

3.

相同的因素必須得到相同的結論且訓練例必須唯一.23九月202448ID3算法例子樣本數(shù)據(jù) warm_blooded feathers fur swims lays_eggs

1 1 1 0 0 1

2 0 0 0 1 1 3 1 1 0 0 1 4 1 1 0 0 1 5 1 0 0 1 0

6 1 0 1 0 0 假設目標分類屬性是lays_eggs，計算Gain(lays_eggs)：

warm_blooded=1，warm_blooded=0，類似的，Gain(feathers)=0.459；Gain(fur)=0.316；Gain(swims)=0.044。由于feathers在屬性中具有最高的信息增益，所以它首先被選作測試屬性。并以此創(chuàng)建一個結點，數(shù)據(jù)集被劃分成兩個子集。23九月202449ID3算法例子（續(xù)）根據(jù)feathers的取值，數(shù)據(jù)集被劃分成兩個子集對于feathers=1的所有元組，其目標分類屬性=lays_eggs均為1。所以，得到一個葉子結點。對于feathers=0的右子樹，計算其他屬性信息增益：Gain(warm_blooded)=0.918Gain(fur)=0.318Gain(swims)=0.318根據(jù)warm_blooded的取值，左右子樹均可得到葉子結點，結束。23九月202450ID3算法的性能分析ID3算法的假設空間包含所有的決策樹，它是關于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間。所以ID3算法避免了搜索不完整假設空間的一個主要風險：假設空間可能不包含目標函數(shù)。ID3算法在搜索的每一步都使用當前的所有訓練樣例，大大降低了對個別訓練樣例錯誤的敏感性。因此，通過修改終止準則，可以容易地擴展到處理含有噪聲的訓練數(shù)據(jù)。ID3算法在搜索過程中不進行回溯。所以，它易受無回溯的爬山搜索中的常見風險影響：收斂到局部最優(yōu)而不是全局最優(yōu)。ID3算法只能處理離散值的屬性。信息增益度量存在一個內在偏置，它偏袒具有較多值的屬性。例如，如果有一個屬性為日期，那么將有大量取值，這個屬性可能會有非常高的信息增益。假如它被選作樹的根結點的決策屬性則可能形成一顆非常寬的樹，這棵樹可以理想地分類訓練數(shù)據(jù)，但是對于測試數(shù)據(jù)的分類性能可能會相當差。ID3算法增長樹的每一個分支的深度，直到恰好能對訓練樣例完美地分類。當數(shù)據(jù)中有噪聲或訓練樣例的數(shù)量太少時，產生的樹會過渡擬合訓練樣例。23九月202451C4.5算法對ID3的主要改進C4.5算法是從ID3算法演變而來，除了擁有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：用信息增益比例的概念；合并具有連續(xù)屬性的值；可以處理具有缺少屬性值的訓練樣本；通過使用不同的修剪技術以避免樹的過度擬合；K交叉驗證；規(guī)則的產生方式等。23九月202452信息增益比例的概念信息增益比例是在信息增益概念基礎上發(fā)展起來的，一個屬性的信息增益比例用下面的公式給出：其中假如我們以屬性A的值為基準對樣本進行分割的化，Splitl(A)就是前面熵的概念。

23九月202453C4.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進行離散化。23九月202454C4.5的其他處理

C4.5處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對屬性和每一個值賦予一個概率，取得這些概率，取得這些概率依賴于該屬性已知的值。規(guī)則的產生：一旦樹被建立，就可以把樹轉換成if-then規(guī)則。規(guī)則存儲于一個二維數(shù)組中，每一行代表樹中的一個規(guī)則，即從根到葉之間的一個路徑。表中的每列存放著樹中的結點。23九月202455C4.5算法例子樣本數(shù)據(jù)Outlook Temperature Humidity Wind PlayTennis Sunny Hot 85 false No

Sunny Hot 90 true No Overcast Hot 78 false Yes

Rain Mild 96 false Yes Rain Cool 80 false Yes

Rain Cool 70 true No Overcast Cool 65 true Yes

Sunny Mild 95 false No

Sunny Cool 70 false Yes

Rain Mild 80 false Yes Sunny Mild 70 true Yes

Overcast Mild 90 true Yes Overcast Hot 75 false Yes

Rain Mild 80 true No（1）首先對Humidity進行屬性離散化，針對上面的訓練集合，通過檢測每個劃分而確定最好的劃分在75處，則這個屬性的范圍就變?yōu)閧（<=75，>75）}。（2）計算目標屬性PlayTennis分類的期望信息：

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

（4）選取最大的GainRatio，根據(jù)Outlook的取值，將三分枝。（5）再擴展各分枝節(jié)點，得到最終的決策樹（見課本圖4-7）。23九月202456例2銀行在處理一批客戶的信貸活動中，確定是否對具備貸款條件的客戶發(fā)放貸款，存在決策分析問題。在客戶信息表中去一些不必要的屬性，保留收入、客戶年齡、信譽度、貸款期限和準予貸款5個屬性，樣本數(shù)據(jù)集如下表：23九月20245723九月20245823九月20245923九月20246023九月202461第三章分類方法

內容提要分類的基本概念與步驟基于距離的分類算法決策樹分類方法貝葉斯分類

規(guī)則歸納與分類有關的問題23九月202462貝葉斯分類是統(tǒng)計學的分類方法，其分析方法的特點是使用概率來表示所有形式的不確定性，學習或推理都用概率規(guī)則來實現(xiàn)；樸素貝葉斯分類：假定一個屬性值對給定類的影響獨立于其他屬性的值；貝葉斯網(wǎng)絡：是用來表示變量間連接概率的圖形模式,它提供了一種自然的表示因果信息的方法,用來發(fā)現(xiàn)數(shù)據(jù)間的潛在關系。23九月202463對分類方法進行比較的有關研究結果表明：簡單貝葉斯分類器（稱為基本貝葉斯分類器）在分類性能上與決策樹和神經(jīng)網(wǎng)絡都是可比的。在處理大規(guī)模數(shù)據(jù)庫時，貝葉斯分類器已表現(xiàn)出較高的分類準確性和運算性能?；矩惾~斯分類器假設一個指定類別中各屬性的取值是相互獨立的。這一假設也被稱為：類別條件獨立，它可以幫助有效減少在構造貝葉斯分類器時所需要進行的計算量。23九月202464貝葉斯分類定義4-2設X是類標號未知的數(shù)據(jù)樣本。設H為某種假定，如數(shù)據(jù)樣本X屬于某特定的類C。對于分類問題，我們希望確定P(H|X)，即給定觀測數(shù)據(jù)樣本X，假定H成立的概率。貝葉斯定理給出了如下計算P(H|X)的簡單有效的方法:P(H)是先驗概率，或稱H的先驗概率。P(X|H)代表假設H成立的情況下，觀察到X的概率。P(H|X)是后驗概率，或稱條件X下H的后驗概率。例如，假定數(shù)據(jù)樣本域由水果組成，用它們的顏色和形狀來描述。假定X表示紅色和圓的，H表示假定X是蘋果，則P(H|X)反映當我們看到X是紅色并是圓的時，我們對X是蘋果的確信程度。貝葉斯分類器對兩種數(shù)據(jù)具有較好的分類效果：一種是完全獨立的數(shù)據(jù)，另一種是函數(shù)依賴的數(shù)據(jù)。23九月202465樸素貝葉斯分類樸素貝葉斯分類的工作過程如下：(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。這樣，最大化P(Ci|X)。其P(Ci|X)最大的類Ci稱為最大后驗假定。根據(jù)貝葉斯定理23九月202466樸素貝葉斯分類(續(xù))(3)

由于P(X)對于所有類為常數(shù)，只需要P(X|Ci)*P(Ci)最大即可。如果Ci類的先驗概率未知，則通常假定這些類是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此問題就轉換為對P(X|Ci)的最大化（P(X|Ci)常被稱為給定Ci時數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設Ci稱為最大似然假設）。否則，需要最大化P(X|Ci)*P(Ci)。注意，類的先驗概率可以用P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數(shù)，而s是訓練樣本總數(shù)。(4)

給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci)的開銷可能非常大。為降低計算P(X|Ci)的開銷，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性值相互條件獨立，即在屬性間，不存在依賴關系。這樣

23九月202467樸素貝葉斯分類(續(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ù)，而分別為平均值和標準差。

(5)

對未知樣本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)最大的類。

23九月20246823九月202469樸素貝葉斯分類舉例數(shù)據(jù)樣本用屬性age，income，student和credit_rating描述。類標號屬性buys_computer具有兩個不同值（即{yes，no}）。設C1對應于類buys_computer=”yes”，而C2對應于類buys_computer=”no”。我們希望分類的未知樣本為:X=（age=”<=30”，income=”medium”，student=”yes”，credit_rating=”fair”）。23九月202470樸素貝葉斯分類舉例(1)我們需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。(2)為計算P(X|Ci)，i=1，2，我們計算下面的條件概率：

P(age<=30|buys_computer=”yes”)=2/9=0.222，

P(age<=30”|buys_computer=”no”)=3/5=0.600， P(income=”medium”|buys_computer=”yes”)=4/9=0.444， P(income=”medium”|buys_computer=”no”)=2/5=0.400， P(student=”yes”|buys_computer=”yes”)=6/9=0.677， P(student=”yes”|buys_computer=”no”)=1/5=0.200， P(credit_rating=”fair”|buys_computer=”yes”)=6/9=0.667， P(credit_rating=”fair”|buys_computer=”no”)=2/5=0.400。

(3)假設條件獨立性，使用以上概率，我們得到：

P(X|buys_computer=”yes”)=0.222*0.444*0.667*0.667=0.044，P(X|buys_computer=”no”)=0.600*0.400*0.200*0.400=0.019，P(X|buys_computer=”yes”)*P(buys_computer=”yes”)=0.044*0.643=0.028P(X|buys_computer=”no”)*P(buys_computer=”no”)=0.019*0.357=0.007。因此，對于樣本X，樸素貝葉斯分類預測buys_computer=”yes”。23九月202471第三章分類方法

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

與分類有關的問題23九月202472規(guī)則歸納常見的采用規(guī)則表示的分類器構造方法有:利用規(guī)則歸納技術直接生成規(guī)則利用決策樹方法先生成決策樹，然后再把決策樹轉換為規(guī)則；使用粗糙集方法生成規(guī)則；使用遺傳算法中的分類器技術生成規(guī)則等。

本節(jié)將只討論規(guī)則歸納方法。我們這里討論的規(guī)則歸納算法，可以直接學習規(guī)則集合，這一點與決策樹方法、遺傳算法有兩點關鍵的不同。它們可學習包含變量的一階規(guī)則集合：這一點很重要，因為一階子句的表達能力比命題規(guī)則要強得多。這里討論的算法使用序列覆蓋算法：一次學習一個規(guī)則，以遞增的方式形成最終的規(guī)則集合。23九月202473規(guī)則歸納(續(xù))規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加策略。減法策略：以具體例子為出發(fā)點，對例子進行推廣或泛化，推廣即減除條件（屬性值）或減除合取項（為了方便，我們不考慮增加析取項的推廣），使推廣后的例子或規(guī)則不覆蓋任何反例。加法策略：起始假設規(guī)則的條件部分為空（永真規(guī)則），如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項，直到該規(guī)則不再覆蓋反例。先加后減策略：由于屬性間存在相關性，因此可能某個條件的加入會導致前面加入的條件沒什么作用，因此需要減除前面的條件。先減后加策略：道理同先加后減，也是為了處理屬性間的相關性。典型的規(guī)則歸納算法有AQ、CN2和FOIL等。

23九月202474AQ算法

AQ算法利用覆蓋所有正例，排斥所有反例的思想來尋找規(guī)則。比較典型的有Michalski的AQ11方法，洪家榮改進的AQ15方法以及洪家榮的AE5方法。AQR是一個基于最基本AQ算法的歸納算法。其實，在很多的算法中，都采用了基本AQ算法，象AQ11和GEM。但和其它方法比較而言，AQR更加簡單一些，如在AQ11中使用一種復雜的包括置信度的規(guī)則推導方法。下面我們首先對AQR算法進行概念描述，然后介紹算法描述和相關例子，最后分析其性能。23九月202475AQR算法有關定義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ī)則，則其分類為樣本集中最頻繁的分類。23九月202476

AQR算法描述算法4-5AQR輸入：正例樣本POS；反例樣本NEG。輸出：覆蓋COVER。（1）COVER=Φ；//初始化COVER為空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；/選取一個種子SEED，例如沒有被COVER覆蓋的一個正樣例（4）CallprocedureSTAR（SEED，NEG）；//產生一個能覆蓋種子而同時排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；/*從星中選取一個最好的復合*/（6）AddBESTasanextradisjucttoCOVER/*把最好的復合與COVER合取，形成新的COVER*/（7）END（8）RETURNCOVER.在算法AQR中調用了過程STAR，來排除所有的反例，產生覆蓋種子的星。23九月202477

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ī)則*/23九月202478AQR算法舉例假設現(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}。（４）調用STAR（SEED，NEG）去產生一個覆蓋SEED但不包含NEG的STAR集合；初始化STAR為空，即STAR={}?？盏腸omplex覆蓋所有樣例，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-wheeler23九月202479AQR算法舉例（5）BEST={size=huge

type=bicycle}，COVER={size=huge

type=bicycle}。

（6）顯然COVER不能覆蓋所有的正例，從正例中選取另一個SEED={size=huge，type=motorcycle}。（7）調用STAR（SEED，NEG）去產生一個覆蓋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)覆蓋到全部的正例，則算法結束。輸出規(guī)則為gaint2-wheeler

size=huge。假設現(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-wheeler23九月202480CN2算法描述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）并將其結果放入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需要通過調用函數(shù)Find_Best_Complex，它的描述寫成下面算法4-8。23九月202481CN2算法描述(續(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-definedcriteriawhentestedonE/*如果Ci在統(tǒng)計上有意義，并且對訓練集E測試后符合用戶定義的條件且優(yōu)于BEST_CPX*/（9） THENreplacethecurrentvalueofBEST_CPXbyCi；/*將BEST_CPX替換為Ci*/（10）REPEATremoveworstComplexesfromNEWSTAR（11）UNTILsizeofNEWSTARis<=user-definedmaximummaxstar；/*逐步移去在NEWSTAR中最壞的complex直到NEWSTAR的大小等于或小于用戶 定義的最大數(shù)目maxstar*/（12） LetSTARbeNEWSTAR；/*令STAR=NEWSTAR*/（13）END（14）RETURNBEST_CPX。/*返回BEST_CPX*/

23九月202482FOIL算法FOIL學習系統(tǒng)已經(jīng)被廣泛地應用在邏輯規(guī)約領域。FOIL是用來對無約束的一階Horn子句進行學習。一個概念的定義是由一系列的子句組成，而其中每一個子句描述了一種證明一個樣本是這個概念的實例的唯一方法。每個子句由一些文字的析取組成。FOIL由一系列的外部定義的斷言開始，其中之一被確定為當前學習的概念，而其他作為背景文字。FOIL從這些外部定義的斷言中獲取一系列包括文字的子句。FOIL算法由一個空子句開始查找，其不斷的向當前的子句中追加文字直到?jīng)]有負樣例被子句所覆蓋。之后，F(xiàn)OIL重新開始一個子句的查找，直到所有的正樣例均被已經(jīng)生成的子句所覆蓋。FOIL計算每一個外部定義斷言的信息熵（InformationGain）和合法的