第四章 分類方法

第四章分類方法

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

基于距離的分類算法決策樹分類方法貝葉斯分類規(guī)則歸納與分類有關(guān)的問(wèn)題2023/2/41DataMining:ConceptsandTechniques分類是數(shù)據(jù)挖掘中重要的任務(wù)分類的目的是學(xué)會(huì)一個(gè)分類器（分類函數(shù)或模型），該分類器能把待分類的數(shù)據(jù)映射到給定的類別中。分類可用于預(yù)測(cè)。從利用歷史數(shù)據(jù)紀(jì)錄中自動(dòng)推導(dǎo)出對(duì)給定數(shù)據(jù)的推廣描述，從而能對(duì)未來(lái)數(shù)據(jù)進(jìn)行類預(yù)測(cè)。分類和統(tǒng)計(jì)學(xué)中的回歸是既相互聯(lián)系，有有一定區(qū)別的概念。分類輸出的是離散的類別值，而回歸輸出的是連續(xù)數(shù)值。分類具有廣泛的應(yīng)用，例如醫(yī)療診斷、信用卡系統(tǒng)的信用分級(jí)、圖像模式識(shí)別等。2023/2/42DataMining:ConceptsandTechniques分類是數(shù)據(jù)挖掘中重要的任務(wù)分類器的構(gòu)造依據(jù)的方法很廣泛：統(tǒng)計(jì)方法：包括貝葉斯法和非參數(shù)法等。機(jī)器學(xué)習(xí)方法：包括決策樹法和規(guī)則歸納法。神經(jīng)網(wǎng)絡(luò)方法。其他，如粗糙集等（在前面緒論中也介紹了相關(guān)的情況）。2023/2/43DataMining:ConceptsandTechniques分類方法的類型從使用的主要技術(shù)可以把分類方法歸結(jié)為四種類型：基于距離的分類方法決策樹分類方法貝葉斯分類方法規(guī)則歸納方法。本章將擇選一些有代表性的方法和算法來(lái)介紹這四類分類方法。2023/2/44DataMining:ConceptsandTechniques分類問(wèn)題的描述定義4-1給定一個(gè)數(shù)據(jù)庫(kù)

D={t1，t2，…，tn}和一組類C={C1，…，Cm}，分類問(wèn)題是去確定一個(gè)映射

f:DC，使得每個(gè)元組ti被分配到一個(gè)類中。一個(gè)類Cj

包含映射到該類中的所有元組，即Cj={ti|f(ti)=Cj，1≤i≤n，而且tiD}。解決分類問(wèn)題的關(guān)鍵是構(gòu)造一個(gè)合適的分類器：從數(shù)據(jù)庫(kù)到一組類別集的映射。一般地，這些類是被預(yù)先定義的、非交疊的。構(gòu)造分類器，需要有一個(gè)訓(xùn)練樣本數(shù)據(jù)集作為輸入。分類的目的是分析輸入數(shù)據(jù)，通過(guò)訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來(lái)的特性，為每一個(gè)類找到一種準(zhǔn)確的描述或者模型。數(shù)據(jù)分類(DataClassification)分為兩個(gè)步驟:建模和使用。2023/2/45DataMining:ConceptsandTechniques分類問(wèn)題的描述2023/2/46DataMining:ConceptsandTechniques數(shù)據(jù)分類的兩個(gè)步驟1．建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類集或概念集數(shù)據(jù)元組也稱作樣本、實(shí)例或?qū)ο?。為建立模型而被分析的?shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集中的單個(gè)元組稱作訓(xùn)練樣本，由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)，因此也稱作有指導(dǎo)的學(xué)習(xí)。通過(guò)分析訓(xùn)練數(shù)據(jù)集來(lái)構(gòu)造分類模型，可用分類規(guī)則、決策樹或數(shù)學(xué)公式等形式提供。2023/2/47DataMining:ConceptsandTechniques數(shù)據(jù)分類的兩個(gè)步驟2．使用模型進(jìn)行分類首先評(píng)估模型（分類法）的預(yù)測(cè)準(zhǔn)確率。如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。2023/2/48DataMining:ConceptsandTechniques數(shù)據(jù)分類的兩個(gè)步驟圖5.1數(shù)據(jù)分類過(guò)程：a)學(xué)習(xí)：用分類算法分析訓(xùn)練數(shù)據(jù)。這里，類標(biāo)號(hào)屬性是loan_decision，學(xué)習(xí)的模型或分類器以分類規(guī)則形式提供。2023/2/49DataMining:ConceptsandTechniques數(shù)據(jù)分類的兩個(gè)步驟圖5.1數(shù)據(jù)分類過(guò)程：b)分類：檢驗(yàn)數(shù)據(jù)用于評(píng)估分類規(guī)則的準(zhǔn)確率。如果準(zhǔn)確率是可以接受的，則規(guī)則用于新的數(shù)據(jù)元組分類2023/2/410DataMining:ConceptsandTechniques第三章分類方法

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

決策樹分類方法貝葉斯分類規(guī)則歸納與分類有關(guān)的問(wèn)題2023/2/411DataMining:ConceptsandTechniques基于距離的分類算法的思路定義4-2給定一個(gè)數(shù)據(jù)庫(kù)D={t1，t2，…，tn}和一組類C={C1，…，Cm}。假定每個(gè)元組包括一些數(shù)值型的屬性值：ti={ti1，ti2，…，tik}，每個(gè)類也包含數(shù)值性屬性值：Cj={Cj1，Cj2，…，Cjk}，則分類問(wèn)題是要分配每個(gè)ti到滿足如下條件的類Cj：sim(ti，Cj)≥sim(ti，Cp)，Cp∈C，Cp≠Cj，其中sim(ti，Cj)被稱為相似性。在實(shí)際的計(jì)算中往往用距離來(lái)表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。為了計(jì)算相似性，應(yīng)首先得到表示每個(gè)類的向量。最常用的是通過(guò)計(jì)算每個(gè)類的中心來(lái)完成。2023/2/412DataMining:ConceptsandTechniques基于距離的分類算法的一般性描述算法4-1通過(guò)對(duì)每個(gè)元組和各個(gè)類的中心來(lái)比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。算法4-1基于距離的分類算法輸入：每個(gè)類的中心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/2/413DataMining:ConceptsandTechniques基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結(jié)果2023/2/414DataMining:ConceptsandTechniquesK-近鄰分類算法K-近鄰分類算法（KNearestNeighbors，簡(jiǎn)稱KNN）通過(guò)計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。2023/2/415DataMining:ConceptsandTechniquesK-近鄰分類算法算法4-2K-近鄰分類算法輸入：訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。輸出：輸出類別c。（1）N=；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN

N=N∪xtx7hlh；（4）ELSEIFu∈Nsuchthatsim(t,u)<sim(t,d)THEN

BEGIN（5） N=N-{u}；N=N∪l9v9jvp；（6） END（7）END（8）c=classtowhichthemostu∈N.2023/2/416DataMining:ConceptsandTechniquesKNN的例子姓名 性別身高(米) 類別 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 中等訓(xùn)練數(shù)據(jù)集2023/2/417DataMining:ConceptsandTechniquesKNN的例子“高度”用于計(jì)算距離，K=5，對(duì)<Pat，女，1.6>分類。

對(duì)T前K=5個(gè)記錄，N={<Kristina，女，1.6>、<Jim，男，2>、<Maggie，女，1.9>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對(duì)第6個(gè)記錄d=<Bob，男，1.85>，得到N={<Kristina，女，1.6>、<Bob，男，1.85>、<Maggie，女，1.9>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對(duì)第7個(gè)記錄d=<Kathy，女，1.6>，得到N={<Kristina，女，1.6>、<Bob，男，1.85>、<Kathy，女，1.6>、<Martha，女，1.88>和<Stephanie，女，1.7>}。對(duì)第8個(gè)記錄d=<Dave，男，1.7>，得到N={<Kristina，女，1.6>、<Dave，男，1.7>、<Kathy，女，1.6>、<Martha，女，1.88>和<Stephanie，女，1.7>}。2023/2/418DataMining:ConceptsandTechniquesKNN的例子對(duì)第9和10個(gè)記錄，沒(méi)變化。對(duì)第11個(gè)記錄d=<Debbie，女，1.8>，得到N={<Kristina，女，1.6>、<Dave，男，1.7>、<Kathy，女，1.6>、<Debbie，女，1.8>和<Stephanie，女，1.7>}。對(duì)第12到14個(gè)記錄，沒(méi)變化。對(duì)第15個(gè)記錄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>。在這五項(xiàng)中，四個(gè)屬于矮個(gè)、一個(gè)屬于中等。最終KNN方法認(rèn)為Pat為矮個(gè)。<Wynette，女，1.75>。2023/2/419DataMining:ConceptsandTechniques第三章分類方法

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

貝葉斯分類規(guī)則歸納與分類有關(guān)的問(wèn)題2023/2/420DataMining:ConceptsandTechniques決策樹表示與例子決策樹（DecisionTree）的每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表一個(gè)測(cè)試輸出，而每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。樹的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。buys_computer的決策樹示意

2023/2/421DataMining:ConceptsandTechniques決策樹表示與例子2023/2/422DataMining:ConceptsandTechniques決策樹分類的特點(diǎn)決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分枝，在決策樹的葉結(jié)點(diǎn)得到結(jié)論。從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整棵決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則?；跊Q策樹的分類算法的一個(gè)最大的優(yōu)點(diǎn)就是它在學(xué)習(xí)過(guò)程中不需要使用者了解很多背景知識(shí)（同時(shí)也是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性-結(jié)論式表示出來(lái)，就能使用該算法來(lái)學(xué)習(xí)。2023/2/423DataMining:ConceptsandTechniques決策樹分類算法步驟：（1）決策樹修剪決策樹生成算法的輸人是一組帶有類別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉樹或多叉樹。樹的葉子結(jié)點(diǎn)都是類別標(biāo)記。二叉樹：二叉樹的內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))一般表示為一個(gè)邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai是屬性，vi是該屬性的某個(gè)屬性值。多叉樹：樹的邊是邏輯判斷的分支結(jié)果。多叉樹的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)造。2023/2/424DataMining:ConceptsandTechniques決策樹分類算法步驟：（1）決策樹生成構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)造。思路：以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始建樹(對(duì)應(yīng)算法5.4步驟(1))。如果樣本都在同一個(gè)類，則該結(jié)點(diǎn)成為樹葉，并用該類標(biāo)記(步驟(2))。否則，使用信息增益度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性(步驟4)。該屬性成為該結(jié)點(diǎn)的“測(cè)試”或“判定”屬性(步驟5)。在這類算法中，所有的屬性都是取離散值的。連續(xù)值的屬性必須離散化。對(duì)測(cè)試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本(步驟(6)～(7))。同樣的過(guò)程，遞歸地形成每個(gè)劃分上的樣本決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)結(jié)點(diǎn)上，就不必考慮該結(jié)點(diǎn)的任何后代(步驟(9))。2023/2/425DataMining:ConceptsandTechniques決策樹分類算法步驟：（1）決策樹生成遞歸劃分步驟，當(dāng)下列條件之一成立時(shí)停止：給定結(jié)點(diǎn)的所有樣本屬于同一類(步驟(2))。沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本(步驟(3))。在此情況下，采用多數(shù)表決(步驟(3))。這涉及將給定的結(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在的類別標(biāo)記它。換一種方式，可以存放結(jié)點(diǎn)樣本的類分布。分支test_attribute=ai沒(méi)有樣本。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個(gè)樹葉(步驟(8))。2023/2/426DataMining:ConceptsandTechniques決策樹生成算法描述算法4-3Generate_decision_tree(samples,attribute_list)/*決策樹生成算法*/輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹。（1）創(chuàng)建結(jié)點(diǎn)N；（2）

IF

samples

都在同一個(gè)類C

THEN

返回N

作為葉結(jié)點(diǎn)，以類C標(biāo)記；（3）

IF

attribute_list為空

THEN

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

FOReachtest_attribute中的已知值ai，由結(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為

test_attribute=ai的分枝；（7）設(shè)si是samples中test_attribute

=ai的樣本的集合；//一個(gè)劃分（8）IF

si

為空

THEN

加上一個(gè)樹葉，標(biāo)記為samples中最普通的類；（9）ELSE

加上一個(gè)由Generate_decision_tree(si,attribute_list-

test_attribute)返回的結(jié)點(diǎn)；2023/2/427DataMining:ConceptsandTechniques決策樹生成算法描述構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的屬性進(jìn)行樹的拓展。研究結(jié)果表明，一般情況下或具有較大概率地說(shuō)，樹越小則樹的預(yù)測(cè)能力越強(qiáng)。由于構(gòu)造最小的樹是NP-難問(wèn)題，只能采取用啟發(fā)式策略來(lái)進(jìn)行。屬性選擇依賴于各種對(duì)例子子集的不純度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距離度量（DistanceMeasure）、J-measure、G統(tǒng)計(jì)、χ2統(tǒng)計(jì)、證據(jù)權(quán)重（WeightofEvidence）、最小描述長(zhǎng)度（MLP）、正交法（OrtogonalityMeasure）、相關(guān)度（Relevance）和Relief等。2023/2/428DataMining:ConceptsandTechniques決策樹修剪算法基本的決策樹構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹完全與訓(xùn)練例子擬合。在有噪聲情況下，將導(dǎo)致過(guò)分?jǐn)M合(Overfitting)，即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而使對(duì)現(xiàn)實(shí)數(shù)據(jù)的分類預(yù)測(cè)性能下降?，F(xiàn)實(shí)世界的數(shù)據(jù)一般不可能是完美的，可能缺值(MissingValues)；數(shù)據(jù)不完整；含有噪聲甚至是錯(cuò)誤的。2023/2/429DataMining:ConceptsandTechniques決策樹修剪算法剪枝是一種克服噪聲的基本技術(shù)，也能使樹得到簡(jiǎn)化而變得更容易理解。有兩種基本的剪枝策略：預(yù)先剪枝(Pre-Pruning)：在生成樹的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。后剪枝(Post-Pruning)：是一種擬合+化簡(jiǎn)(fitting-and-simplifying)的兩階段方法。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合(TuningSet或AdjustingSet)，如果存在某個(gè)葉子剪去后能使得在測(cè)試集上的準(zhǔn)確度或其他測(cè)度不降低(不變得更壞)，則剪去該葉子；否則停機(jī)。理論上講，后剪枝好于預(yù)先剪枝，但計(jì)算復(fù)雜度大。剪枝過(guò)程中，確定統(tǒng)計(jì)參數(shù)或閾值(如停機(jī)閾值)成為一個(gè)難點(diǎn)。要防止過(guò)分剪枝(Over-Pruning)帶來(lái)的副作用。2023/2/430DataMining:ConceptsandTechniquesID3算法ID3是Quinlan提出的一個(gè)著名決策樹生成方法：決策樹中每一個(gè)非葉結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)非類別屬性，樹枝代表這個(gè)屬性的值。一個(gè)葉結(jié)點(diǎn)代表從樹根到葉結(jié)點(diǎn)之間的路徑對(duì)應(yīng)的記錄所屬的類別屬性值。每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。采用信息增益來(lái)選擇能夠最好地將樣本分類的屬性。為了聚焦重點(diǎn)，將對(duì)ID3算法采用如下方式講解：偽代碼詳細(xì)描述見(jiàn)課本；給出信息增益對(duì)應(yīng)的計(jì)算公式；通過(guò)一個(gè)例子來(lái)說(shuō)明它的主要過(guò)程。2023/2/431DataMining:ConceptsandTechniques信息增益的計(jì)算設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，定義m個(gè)不同類Ci(i=1,2,…,m)，設(shè)si是Ci類中的樣本數(shù)。對(duì)給定的樣本S所期望的信息值由下式給出：其中pi是任意樣本屬于Ci的概率：si/s。設(shè)屬性A具有個(gè)不同值{a1,a2,…,av}，可以用屬性A將樣本S劃分為{S1,S2,…,Sv}，設(shè)sij是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出：由A進(jìn)行分枝將獲得的信息增益可以由下面的公式得到：2023/2/432DataMining:ConceptsandTechniquesID3算法例子樣本數(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假設(shè)目標(biāo)分類屬性是lays_eggs，計(jì)算Gain(lays_eggs)：

warm_blooded=1，warm_blooded=0，類似的，Gain(feathers)=0.459；Gain(fur)=0.316；Gain(swims)=0.044。由于feathers在屬性中具有最高的信息增益，所以它首先被選作測(cè)試屬性。并以此創(chuàng)建一個(gè)結(jié)點(diǎn)，數(shù)據(jù)集被劃分成兩個(gè)子集。2023/2/433DataMining:ConceptsandTechniquesID3算法例子（續(xù)）根據(jù)feathers的取值，數(shù)據(jù)集被劃分成兩個(gè)子集對(duì)于feathers=1的所有元組，其目標(biāo)分類屬性=lays_eggs均為1。所以，得到一個(gè)葉子結(jié)點(diǎn)。對(duì)于feathers=0的右子樹，計(jì)算其他屬性信息增益：Gain(warm_blooded)=0.918Gain(fur)=0.318Gain(swims)=0.318根據(jù)warm_blooded的取值，左右子樹均可得到葉子結(jié)點(diǎn)，結(jié)束。2023/2/434DataMining:ConceptsandTechniquesID3算法例子（續(xù)）2023/2/435DataMining:ConceptsandTechniquesID3算法的性能分析ID3算法可以描述成從一個(gè)假設(shè)空間中搜索一個(gè)擬合訓(xùn)練樣例的假設(shè)。被ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3算法以一種從簡(jiǎn)單到復(fù)雜的爬山算法遍歷這個(gè)假設(shè)空間，從空的樹開始，然后逐步考慮更加復(fù)雜的假設(shè)，目的是搜索到一個(gè)正確分類訓(xùn)練數(shù)據(jù)的決策樹。引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間。所以ID3算法避免了搜索不完整假設(shè)空間的一個(gè)主要風(fēng)險(xiǎn)：假設(shè)空間可能不包含目標(biāo)函數(shù)。2023/2/436DataMining:ConceptsandTechniquesID3算法的性能分析當(dāng)遍歷決策樹空間時(shí)，ID3僅維護(hù)單一的當(dāng)前假設(shè)，失去了表示所有一致假設(shè)所帶來(lái)的優(yōu)勢(shì)。ID3算法在搜索過(guò)程中不進(jìn)行回溯，每當(dāng)在樹的某一層次選擇了一個(gè)屬性進(jìn)行測(cè)試，它不會(huì)再回溯重新考慮這個(gè)選擇。所以，它易受無(wú)回溯的爬山搜索中的常見(jiàn)風(fēng)險(xiǎn)影響：收斂到局部最優(yōu)的答案，而不是全局最優(yōu)的。對(duì)于ID3算法，一個(gè)局部最優(yōu)的答案對(duì)應(yīng)著它在一條搜索路徑上搜索時(shí)選擇的決策樹。然而，這個(gè)局部最優(yōu)的答案可能不如沿著另一條分支搜索到的更令人滿意。ID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例，以統(tǒng)計(jì)為基礎(chǔ)決定怎樣精化當(dāng)前的假設(shè),大大降低了對(duì)個(gè)別訓(xùn)練樣例錯(cuò)誤的敏感性。因此，通過(guò)修改終止準(zhǔn)則，可以容易地?cái)U(kuò)展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。2023/2/437DataMining:ConceptsandTechniquesID3算法的性能分析ID3算法只能處理離散值的屬性。首先，學(xué)習(xí)到的決策樹要預(yù)測(cè)的目標(biāo)屬性必須是離散的。其次，樹的決策結(jié)點(diǎn)的屬性也必須是離散的。信息增益度量存在一個(gè)內(nèi)在偏置，它偏袒具有較多值的屬性。例如，如果有一個(gè)屬性為日期，那么將有大量取值，這個(gè)屬性可能會(huì)有非常高的信息增益。假如它被選作樹的根結(jié)點(diǎn)的決策屬性則可能形成一顆非常寬的樹，這棵樹可以理想地分類訓(xùn)練數(shù)據(jù)，但是對(duì)于測(cè)試數(shù)據(jù)的分類性能可能會(huì)相當(dāng)差。ID3算法增長(zhǎng)樹的每一個(gè)分支的深度，直到恰好能對(duì)訓(xùn)練樣例完美地分類。當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少時(shí)，產(chǎn)生的樹會(huì)過(guò)渡擬合訓(xùn)練樣例。2023/2/438DataMining:ConceptsandTechniques避免決策樹學(xué)習(xí)中的過(guò)度擬合方法

預(yù)先剪枝，及早停止樹增長(zhǎng)，在ID3算法完美分類訓(xùn)練數(shù)據(jù)之前就停止樹增長(zhǎng)。后剪枝，即允許樹過(guò)度擬合數(shù)據(jù)，然后對(duì)這個(gè)樹進(jìn)行后修剪。第一種方法看起來(lái)更直接，但是對(duì)過(guò)度擬合的樹進(jìn)行后修剪的在實(shí)踐中更成功。因?yàn)樵诘谝环N方法中精確地估計(jì)何時(shí)停止樹增長(zhǎng)很困難。2023/2/439DataMining:ConceptsandTechniquesC4.5算法對(duì)ID3的主要改進(jìn)C4.5算法是從ID3算法演變而來(lái)，除了擁有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能：用信息增益比例的概念；合并具有連續(xù)屬性的值；可以處理具有缺少屬性值的訓(xùn)練樣本；通過(guò)使用不同修剪技術(shù)以避免樹的過(guò)度擬合；K交叉驗(yàn)證；規(guī)則的產(chǎn)生方式等。2023/2/440DataMining:ConceptsandTechniques信息增益比例的概念信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來(lái)的，一個(gè)屬性的信息增益比例用下面的公式給出：其中假如我們以屬性A的值為基準(zhǔn)對(duì)樣本進(jìn)行分割，Splitl(A)就是前面熵的概念。2023/2/441DataMining:ConceptsandTechniquesC4.5處理連續(xù)值的屬性對(duì)于連續(xù)屬性值，C4.5其處理過(guò)程如下：根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序；用不同的閾值將數(shù)據(jù)集動(dòng)態(tài)的進(jìn)行劃分；當(dāng)輸出改變時(shí)確定一個(gè)閾值；取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值；取兩個(gè)劃分，所有樣本都在這兩個(gè)劃分中；得到所有可能的閾值、增益及增益比；每一個(gè)屬性會(huì)變?yōu)槿蓚€(gè)取值，即小于閾值或大于等于閾值。2023/2/442DataMining:ConceptsandTechniquesC4.5處理連續(xù)值的屬性針對(duì)屬性有連續(xù)數(shù)值的情況，則在訓(xùn)練集中可以按升序方式排列。如果屬性A共有n種取值，則對(duì)每個(gè)取值vj(j=1,2,…,n)，將所有的記錄進(jìn)行劃分：一部分小于vj；另一部分則大于或等于vj。針對(duì)每個(gè)vj計(jì)算劃分對(duì)應(yīng)的增益比率，選擇增益最大的劃分來(lái)對(duì)屬性A進(jìn)行離散化。2023/2/443DataMining:ConceptsandTechniquesC4.5處理未知屬性值C4.5處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對(duì)屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率依賴于該屬性已知的值。2023/2/444DataMining:ConceptsandTechniquesC4.5的規(guī)則的產(chǎn)生規(guī)則的產(chǎn)生：一旦樹被建立，就可以把樹轉(zhuǎn)換成if-then規(guī)則。規(guī)則存儲(chǔ)于一個(gè)二維數(shù)組中，每一行代表樹中的一個(gè)規(guī)則，即從根到葉之間的一個(gè)路徑。表中的每列存放著樹中的結(jié)點(diǎn)。

2023/2/445DataMining:ConceptsandTechniquesC4.5算法例子樣本數(shù)據(jù)Outlook TemperatureHumidity Wind PlayTennis

Sunny Hot 85 false No

Sunny Hot 90 true No OvercastHot 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 No2023/2/446DataMining:ConceptsandTechniquesC4.5算法例子（1）首先對(duì)Humidity進(jìn)行屬性離散化，針對(duì)上面的訓(xùn)練集合，通過(guò)檢測(cè)每個(gè)劃分而確定最好的劃分在75處，則這個(gè)屬性的范圍就變?yōu)閧（<=75，>75）}。（2）計(jì)算目標(biāo)屬性PlayTennis分類的期望信息：

（3）計(jì)算每個(gè)屬性的GainRatio：

（4）選取最大的GainRatio，根據(jù)Outlook的取值，將三分枝，同時(shí)，數(shù)據(jù)集被劃分成三個(gè)子集，如圖4-6所示。2023/2/447DataMining:ConceptsandTechniquesC4.5算法例子2023/2/448DataMining:ConceptsandTechniquesC4.5算法例子（5）各個(gè)子樹生成過(guò)程第一個(gè)子樹生成過(guò)程:GainRatio(Humidity)=1；GainRatio(Temperature)=0.244GainRatio(Wind)=0.0206。選擇Humidity生成分支，得到兩個(gè)葉子結(jié)點(diǎn)。第二個(gè)子樹生成過(guò)程:第二個(gè)子樹所有的樣本屬于同一類（PlayTennis=Yes），所以直接得到葉子結(jié)點(diǎn)。第三個(gè)子樹生成過(guò)程：GainRatio(Humidity)=0.446GainRatio(Temperature)=0.0206GainRatio(Wind)=1，選擇Wind生成分支，得到兩個(gè)葉子結(jié)點(diǎn)。2023/2/449DataMining:ConceptsandTechniquesC4.5算法例子2023/2/450DataMining:ConceptsandTechniques第三章分類方法

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

規(guī)則歸納與分類有關(guān)的問(wèn)題2023/2/451DataMining:ConceptsandTechniques貝葉斯分類定義4-3設(shè)X是類標(biāo)號(hào)未知的數(shù)據(jù)樣本。設(shè)H為某種假定，如數(shù)據(jù)樣本X屬于某特定的類C。對(duì)于分類問(wèn)題，希望確定P(H|X)，即給定觀測(cè)數(shù)據(jù)樣本X，假定H成立的概率。貝葉斯定理給出了如下計(jì)算P(H|X)的簡(jiǎn)單有效的方法:P(H)是先驗(yàn)概率，或稱H的先驗(yàn)概率。P(X|H)代表假設(shè)H成立的情況下，觀察到X的概率。P(H|X)是后驗(yàn)概率，或稱條件X下H的后驗(yàn)概率。2023/2/452DataMining:ConceptsandTechniques貝葉斯分類例如，假定數(shù)據(jù)樣本域由水果組成，用它們的顏色和形狀來(lái)描述。假定X表示紅色和圓的，H表示假定X是蘋果，則P(H|X)反映當(dāng)看到X是紅色并是圓的時(shí)，對(duì)X是蘋果的確信程度。P(H|X)隨著P(H)和P(X|H)的增長(zhǎng)而增長(zhǎng)。P(H|X)隨著P(X)的增長(zhǎng)而減小。貝葉斯分類器對(duì)兩種數(shù)據(jù)具有較好的分類效果：一種是完全獨(dú)立的數(shù)據(jù)，另一種是函數(shù)依賴的數(shù)據(jù)(分布函數(shù))。2023/2/453DataMining:ConceptsandTechniques樸素貝葉斯分類樸素貝葉斯分類的工作過(guò)程如下：(1)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X={x1，x2，……，xn}表示，分別描述對(duì)n個(gè)屬性A1，A2，……，An的n個(gè)度量。2023/2/454DataMining:ConceptsandTechniques樸素貝葉斯分類(2)假定有m個(gè)類C1，C2，…，Cm，給定一個(gè)未知類標(biāo)號(hào)的數(shù)據(jù)樣本X，分類器將預(yù)測(cè)X屬于具有最高后驗(yàn)概率（條件X下）的類。也就是說(shuō)，樸素貝葉斯分類將未知的樣本分配給類Ci（1≤i≤m）當(dāng)且僅當(dāng)P(Ci|X)>P(Cj|X)，對(duì)任意的j=1，2，…，m，j≠i。這樣，最大化P(Ci|X)。其P(Ci|X)最大的類Ci稱為最大后驗(yàn)假定。根據(jù)貝葉斯定理：2023/2/455DataMining:ConceptsandTechniques樸素貝葉斯分類(續(xù))

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

2023/2/456DataMining:ConceptsandTechniques樸素貝葉斯分類(續(xù))

(4)

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

2023/2/457DataMining:ConceptsandTechniques樸素貝葉斯分類(續(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ù)，而分別為平均值和標(biāo)準(zhǔn)差。

2023/2/458DataMining:ConceptsandTechniques樸素貝葉斯分類(續(xù))

(5)

對(duì)未知樣本X分類，也就是對(duì)每個(gè)類Ci，計(jì)算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當(dāng)且僅當(dāng)P(Ci|X)>P(Cj|X)，對(duì)任意的j=1，2，…，m，j≠i。換言之，X被指派到其P(X|Ci)*P(Ci)最大的類。

2023/2/459DataMining:ConceptsandTechniques樸素貝葉斯分類舉例RIDAgeIncomeStudentCerdit_ratingBuy_computer1≤30HighNoFairNo2≤30HighNoExcellentNo331～40HighNoFairYes4>40MediumNoFairYes5>40LowYesFairYes6>40LowYesExcellentNo731～40LowYesExcellentYes8≤30MediumNOFairNo9≤30LowYesFairYes10>40MediumYesFairYes11≤30MediumYesExcellentYes1231～40MediumNoExcellentYes1331～40HighYesFairYes14>40MediumNoExcelleatNo2023/2/460DataMining:ConceptsandTechniques樸素貝葉斯分類舉例數(shù)據(jù)樣本用屬性age，income，student和credit_rating描述。類標(biāo)號(hào)屬性buys_computer具有兩個(gè)不同值（即{yes，no}）。設(shè)C1對(duì)應(yīng)于類buys_computer=“yes”，

C2對(duì)應(yīng)于類buys_computer=“no”。希望分類的未知樣本為:X=(age<=“30”,income=“medium”,student=“yes”,credit_rating=“fair”)。2023/2/461DataMining:ConceptsandTechniques樸素貝葉斯分類舉例

(1)最大化P(X|Ci)*P(Ci),i=1,2。每個(gè)類的先驗(yàn)概率P(Ci)根據(jù)訓(xùn)練樣本計(jì)算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。(2)為計(jì)算P(X|Ci)，i=1，2，下面計(jì)算條件概率：

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。2023/2/462DataMining:ConceptsandTechniques樸素貝葉斯分類舉例

(3)假設(shè)條件獨(dú)立性，使用以上概率，我們得到：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。因此，對(duì)于樣本X，樸素貝葉斯分類預(yù)測(cè)buys_computer=”yes”。2023/2/463DataMining:ConceptsandTechniques避免計(jì)算零概率值在上例中，估計(jì)P(age≤30|buys_computer=”yes”)使用的是比值行nc/n，其中n=9為所有buys_computer=”yes”的訓(xùn)練樣本數(shù)目，而nc=2是其中age≤30的數(shù)目。在多數(shù)情況下，觀察到的比例是對(duì)概率的一個(gè)良好估計(jì)，但當(dāng)nc很小時(shí)估計(jì)較差。設(shè)想P(age≤30|buys_computer=”yes”)的值為0.08，而樣本中只有9個(gè)樣本為buys_computer=”yes”，那么對(duì)于nc最有可能的值只有0。這產(chǎn)生了兩個(gè)難題：2023/2/464DataMining:ConceptsandTechniques避免計(jì)算零概率值兩個(gè)難題：nc/n產(chǎn)生了一個(gè)有偏的過(guò)低估計(jì)(Underestimate)概率。當(dāng)此概率估計(jì)為0時(shí)，如果將來(lái)的查詢包括age≤30，此概率項(xiàng)會(huì)在貝葉斯分類器中占有統(tǒng)治地位。原因在于，其他概率項(xiàng)乘以此0值后得到的最終結(jié)果為0。2023/2/465DataMining:ConceptsandTechniques避免計(jì)算零概率值為避免這些難題，可以采用一種估計(jì)概率的貝葉斯方法，即如下定義的m-估計(jì)：nc和n與前面定義相同，P是將要確定的概率的先驗(yàn)估計(jì)，而m是一個(gè)稱為等效樣本大小的常量，它起到對(duì)于觀察到的數(shù)據(jù)如何衡量P的作用。m被稱為等效樣本大小的原因：上式可被解釋為將n個(gè)實(shí)際的觀察擴(kuò)大，加大m個(gè)按P分布的虛擬樣本。在缺少其他信息時(shí)選擇P的一種典型的方法是假定均勻的先驗(yàn)概率，也就是，如果某屬性有k個(gè)可能值，那么設(shè)置P=1/k。2023/2/466DataMining:ConceptsandTechniques避免計(jì)算零概率值例如，為估計(jì)P(age≤30|buys_computer=”yes”)，注意到屬性age有三個(gè)可能值，因此均勻的先驗(yàn)概率為P=0.333。如果m為0，m估計(jì)等效于簡(jiǎn)單的比例nc/n。如果n和m都非0，那么觀測(cè)到的比例nc/n和先驗(yàn)概率P可按照權(quán)m合并。2023/2/467DataMining:ConceptsandTechniques第三章分類方法

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

與分類有關(guān)的問(wèn)題2023/2/468DataMining:ConceptsandTechniques規(guī)則歸納分類器采用規(guī)則形式表達(dá)易于理解。常見(jiàn)的采用規(guī)則表示的分類器構(gòu)造方法有:利用規(guī)則歸納技術(shù)直接生成規(guī)則利用決策樹方法先生成決策樹，然后再把決策樹轉(zhuǎn)換為規(guī)則；使用粗糙集方法生成規(guī)則；使用遺傳算法中的分類器技術(shù)生成規(guī)則等。

2023/2/469DataMining:ConceptsandTechniques規(guī)則歸納規(guī)則歸納算法，可以直接學(xué)習(xí)規(guī)則集合，這一點(diǎn)與決策樹方法、遺傳算法有兩點(diǎn)關(guān)鍵的不同。它們可學(xué)習(xí)包含變量的一階規(guī)則集合：這一點(diǎn)很重要，因?yàn)橐浑A子句的表達(dá)能力比命題規(guī)則要強(qiáng)得多。這里討論的算法使用序列覆蓋算法：一次學(xué)習(xí)一個(gè)規(guī)則，以遞增的方式形成最終的規(guī)則集合。注釋：一階規(guī)則也就是一階謂詞。在謂詞P(x1,x2,…,xn)中，如果xi(i=1,2,…,n)都是個(gè)體常量、變量或函數(shù)，成為一階謂詞。如果xi本身又是一個(gè)一階謂詞，則稱它為二階謂詞。2023/2/470DataMining:ConceptsandTechniques規(guī)則歸納(續(xù))規(guī)則歸納有四種策略：減法策略：以具體例子為出發(fā)點(diǎn)，對(duì)例子進(jìn)行推廣或泛化，推廣即減除條件（屬性值）或減除合取項(xiàng)(為了方便，不考慮增加析取項(xiàng)的推廣)，使推廣后的例子或規(guī)則不覆蓋任何反例。加法策略：起始假設(shè)規(guī)則的條件部分為空(永真規(guī)則)，如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項(xiàng)，直到該規(guī)則不再覆蓋反例。先加后減策略：由于屬性間存在相關(guān)性，因此可能某個(gè)條件的加入會(huì)導(dǎo)致前面加入的條件沒(méi)什么作用，因此需要減除前面的條件。先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。2023/2/471DataMining:ConceptsandTechniquesAQ算法典型的規(guī)則歸納算法：AQ、CN2、FOIL等。AQ算法利用覆蓋所有正例，排斥所有反例的思想來(lái)尋找規(guī)則。比較典型的有Michalski的AQ11方法，洪家榮改進(jìn)的AQ15方法以及洪家榮的AE5方法。AQ算法在歸納過(guò)程中使用的是“種子”和“星”的概念，種子即是-個(gè)正例，星是覆蓋種子而同時(shí)排除所有反例的概念描述或規(guī)則。AQ獲取星的方法是通過(guò)在星(初始時(shí)在種子中，種子是一種特殊的星)中增加析取或去掉合取項(xiàng)，使其包含新的正例，然后又在該星中增加合取項(xiàng)使其排除的反例上面的過(guò)程反復(fù)進(jìn)行(實(shí)際算法還存在很多技巧)，直到所有正例都被覆蓋。

2023/2/472DataMining:ConceptsandTechniquesAQ算法AQR是一個(gè)基于最基本AQ算法的歸納算法。其實(shí)，在很多的算法中，都采用了基本AQ算法，象AQ11和GEM。但和其它方法比較而言，AQR更加簡(jiǎn)單一些，如在AQ11中使用一種復(fù)雜的包括置信度的規(guī)則推導(dǎo)方法。AQR為每一個(gè)分類推導(dǎo)出一條規(guī)則，每一條規(guī)則形式如下：if<cover>thenpredict<class>。在一個(gè)屬性上的基本測(cè)試被稱為一個(gè)Selector。下面是一些Selector的例子：<Cloudy=yes>或<Temp>60>。2023/2/473DataMining:ConceptsandTechniquesAQR算法有關(guān)定義AQR允許測(cè)試做{=，≤，≥，≠}。Selectors的合取被稱為復(fù)合(Complex)，Complexes之間的析取被稱為覆蓋(Cover)。如果一個(gè)表達(dá)式對(duì)某個(gè)樣本為真，則我們稱其為對(duì)這個(gè)樣本的一個(gè)覆蓋。這樣，一個(gè)空Complex覆蓋所有的樣本，而一個(gè)空Cover不覆蓋任何樣本。在AQR中，一個(gè)新樣本被區(qū)分是看其屬于哪個(gè)推導(dǎo)出來(lái)的規(guī)則。如果該樣本只滿足一條規(guī)則，則這個(gè)樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預(yù)測(cè)的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。2023/2/474DataMining:ConceptsandTechniques

AQR算法描述算法4-5AQR輸入：正例樣本POS；反例樣本NEG。輸出：覆蓋COVER。（1）COVER=Φ；//初始化COVER為空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；/選取一個(gè)種子SEED，例如沒(méi)有被COVER覆蓋的一個(gè)正樣例（4）CallprocedureSTAR（SEED，NEG）；//產(chǎn)生一個(gè)能覆蓋種子而同時(shí)排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；/*從星中選取一個(gè)最好的復(fù)合*/（6）AddBESTtoCOVER/*把最好復(fù)合與COVER合取，形成新COVER*/（7）END（8）RETURNCOVER.在算法AQR中調(diào)用了過(guò)程STAR，來(lái)排除所有的反例，產(chǎn)生覆蓋種子的星。2023/2/475DataMining:ConceptsandTechniques

AQR算法描述(續(xù))算法4-6

STAR輸入：種子SEED；反例NEG。輸出：星STAR。（1）初始化STAR為空Complex（2）WHILEoneormoreComplexesinSTARcoverssomenegativeexamplesinNEGBEGIN/*如果STAR中的一個(gè)或多個(gè)Complex覆蓋NEG中的負(fù)樣例*/（3）SelectanegativeexampleEnegcoveredbyaComplexinSTAR；/*選取一個(gè)被STAR中的Complex覆蓋的負(fù)樣例*/（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/2/476DataMining:ConceptsandTechniquesAQR算法舉例假設(shè)現(xiàn)有一個(gè)訓(xùn)練集，其包含兩種屬性：Size(屬性值：micro，tiny，mid，big，huge，vast)type(屬性值：bicycle，motorcycle，car，prop，jet，glider)現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示：2023/2/477DataMining:ConceptsandTechniquesAQR算法舉例反例樣本sizetypeclassTinymotorcycleconventionaltransportationtinycarconventionaltransportationmidcarconventionaltransportationmicrojetfastplaneTinyjetfastplaneMidjetfastplane正例樣本sizetypeclassHugebicyclegiant2-wheelerHugemotorcyclegiant2-wheeler2023/2/478DataMining:ConceptsandTechniquesAQR算法舉例

AQR算法對(duì)giant2-wheeler類的規(guī)則進(jìn)行獲取過(guò)程步驟如下：（１）COVER={}。（２）空cover不覆蓋任何樣本，進(jìn)入循環(huán)。（３）一開始COVER并沒(méi)有覆蓋任何正例，假定從正例中選取的SEED為{size=huge，type=bicycle}。（４）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個(gè)覆蓋SEED但不包含NEG的STAR集合；2023/2/479DataMining:ConceptsandTechniquesAQR算法舉例(4-1)初始化STAR為空，即STAR={}。(4-2)空的complex覆蓋所有樣例，STAR覆蓋多個(gè)負(fù)樣例，進(jìn)入循。(4-2-1)選取一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例ENEG，假定被選取的是Eneg={size=tiny，type=motorcycle}。(4-2-2)使EXTENSION為所有覆蓋SEED但不覆蓋ENEG的選擇，則EXTENSION包括size=huge和type=bicycle，則又根據(jù)STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=hugetype

=bicycle}。(4-2-3)在這里定義maxstar為2，可不對(duì)STAR進(jìn)行精簡(jiǎn)。(4-2-4)接著選取另一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例ENEG，顯然已經(jīng)沒(méi)有這樣的負(fù)樣例，故STAR={size=hugetype

=bicycle}。(4-3)從STAR(SEED，NEG)返回。2023/2/480DataMining:ConceptsandTechniquesAQR算法舉例（5）BEST={size=hugetype=bicycle}，COVER={size=hugetype

=bicycle}。（6）顯然COVER不能覆蓋所有的正例，從正例中選取另一個(gè)SEED={size=huge,type=motorcycle}。（7）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個(gè)覆蓋SEED但不包含NEG的STAR集（7-1）初始化STAR為空，即STAR={}；（7-2）空的complex覆蓋所有樣例，所以STAR覆蓋負(fù)樣例，進(jìn)入循環(huán)；（7-2-1）假定被選取的是Eneg={size=tiny，type=motorcycle}；（7-2-2）使EXTENSION為所有覆蓋SEED但不覆蓋NEG的選擇，則EXTENSION包括size=huge，則又根據(jù)STAR={x∧y|x∈STAR，y∈EXTENSION}，因此，STAR={size=huge}；（7-2-3）接著選取另一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例Eneg，顯然已經(jīng)沒(méi)有樣的負(fù)樣例，因此，STAR={size=huge}。（7-3）從STAR（SEED，NEG）返回。（8）BEST={size=huge}，將BEST添加到COVER中，COVER={size=hugetype=bicyclesize=huge}={size=huge}。（9）這時(shí)，COVER已經(jīng)覆蓋到全部的正例，則算法結(jié)束。輸出規(guī)則為gaint2-wheelersize=huge。2023/2/481DataMining:ConceptsandTechniquesCN2算法描述在構(gòu)造專家系統(tǒng)的過(guò)程中，從樣本集中通過(guò)歸約方法獲取規(guī)則被證明是十分成功的，并且它很好地解決了知識(shí)獲取中的瓶頸。基于ID3和AQ算法的系統(tǒng)成功應(yīng)用。這些算法在假設(shè)領(lǐng)域中無(wú)噪音的情況下，能夠十分完美地從訓(xùn)練數(shù)據(jù)中找到相應(yīng)的概念描述。但是將這些算法應(yīng)用到現(xiàn)實(shí)世界時(shí)就需要對(duì)噪音數(shù)據(jù)進(jìn)行處理。ID3算法可以通過(guò)簡(jiǎn)單的修改來(lái)放寬這種限制。樹剪枝技術(shù)已經(jīng)被證明是避免過(guò)度擬合的有效手段。對(duì)AQ算法來(lái)說(shuō)，由于其對(duì)具體訓(xùn)練樣例的依賴，因此很難進(jìn)行修改2023/2/482DataMining:ConceptsandTechniquesCN2算法描述CNZ算法結(jié)合了ID3算法處理數(shù)據(jù)的效率和處理噪音數(shù)據(jù)的能力，以及AQ算法家族的靈活性。通過(guò)改進(jìn)去除了對(duì)特定數(shù)據(jù)的依賴，且通過(guò)統(tǒng)計(jì)學(xué)類比，它可以達(dá)到與使用樹剪枝方法的算法同樣的效果。CN2使用一種基于噪音估計(jì)的啟發(fā)式方法，使用這種方法可以不用對(duì)所有的訓(xùn)練樣本進(jìn)行正確的區(qū)分，但是規(guī)約出的規(guī)則在對(duì)新數(shù)據(jù)的處理上有很好的表現(xiàn)。2023/2/483DataMining:ConceptsandTechniquesCN2算法描述算法4-7CN2輸入：E/*E為訓(xùn)練樣本*/輸出：RULE_LIST/*返回一個(gè)覆蓋若干樣例的規(guī)則*/2023/2/484DataMining:ConceptsandTechniquesCN2算法描述（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；/*從訓(xùn)練樣本E中除去E’，即E=E-E’；*/（7）LetCbethemostcommonclassofexamplesinE’；/*令C為樣本子集E’中最頻繁的分類標(biāo)號(hào)；*/（8）Addtherule‘ifBEST_CPXthenclass=C’totheendofRULE_LIST；/*將規(guī)則‘ifBEST_CPXthenclass=C’添加到RULES_LIST中*/（9）END（10）UNTILBEST_CPXisnilorEisempty./*直到BEST_CPX為空或者訓(xùn)練樣本E為空*/（11）RETURNRULE_LIST2023/2/485DataMining:ConceptsandTechniquesCN2算法描述(續(xù))算法4-8

Find_Best_Complex輸入：E/*E為訓(xùn)練樣本*/輸出：BEST_CPX/*返回最佳的規(guī)則BEST_CPX*/（1）LetthesetSTARcontainonlytheemptyComplex；/*初始化集合STAR為空Complex；*/（2）LetBEST_CPXbenil；/*初始化BEST_CPX為空*/（3）LetSELECTORSbethesetofallpossibleSelectors；/*