dataminingch4數(shù)據(jù)挖掘算法-分類方法

第4章數(shù)據(jù)挖掘算法——分類

分類分類的概念基于距離的分類方法BayesianClassificationClassificationbyBackPropagationSupportVectorMachinesAssociativeClassification:ClassificationbyassociationruleanalysisLazyLearners(orLearningfromyourNeighbors)OtherClassificationMethodsPredictionAccuracySummary

分類的基本概念分類是指將數(shù)據(jù)映射到預(yù)先定義好的群組或類。在分析測試數(shù)據(jù)之前，類別就已經(jīng)被確定了，所以分類統(tǒng)稱被稱作有指導(dǎo)的學(xué)習(xí)。分類算法要求基于數(shù)據(jù)屬性來定義類別。分類算法通常通過觀察已知所屬類別的數(shù)據(jù)的特征來描述類別。分類的基本概念分類具有廣泛的應(yīng)用，例如醫(yī)療診斷、信用卡系統(tǒng)的信用分級(jí)、圖像模式識(shí)別等。為了識(shí)別乘客是否是潛在的恐怖分子或罪犯，機(jī)場安全攝像站需要對(duì)乘客的臉部進(jìn)行掃描并辨識(shí)臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀），然后將得到的模式與數(shù)據(jù)庫中的已知恐怖分子或罪犯的模式進(jìn)行逐個(gè)比較，看看是否與其中的某一模式相匹配。分類步驟1．建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類集或概念集數(shù)據(jù)元組也稱作樣本、實(shí)例或?qū)ο?。為建立模型而被分析的?shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集中的單個(gè)元組稱作訓(xùn)練樣本，假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)稱作類標(biāo)號(hào)（classlabel）的屬性確定。由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)，因此也稱作有指導(dǎo)的學(xué)習(xí)。通過分析訓(xùn)練數(shù)據(jù)集來構(gòu)造分類模型，可用分類規(guī)則、決策樹或數(shù)學(xué)公式等形式提供。分類步驟2.使用模型進(jìn)行分類首先評(píng)估模型（分類法）的預(yù)測準(zhǔn)確率。將已知的類標(biāo)號(hào)與該樣本的學(xué)習(xí)模型類預(yù)測比較準(zhǔn)確率等于測試集的樣本中被模型正確分類的百分比測試集應(yīng)該與訓(xùn)練集的內(nèi)容相互獨(dú)立，否則會(huì)出現(xiàn)過分適應(yīng)的情況如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。(1)模型的構(gòu)建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no(2)利用模型分類ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?

有監(jiān)督（指導(dǎo)）vs.無監(jiān)督（無指導(dǎo)）的學(xué)習(xí)有指導(dǎo)的學(xué)習(xí)(分類)指導(dǎo):訓(xùn)練數(shù)據(jù)是已經(jīng)被標(biāo)注好類標(biāo)號(hào)的數(shù)據(jù)，用來進(jìn)行有指導(dǎo)的分類。新數(shù)據(jù)是基于訓(xùn)練集進(jìn)行分類的。無指導(dǎo)的學(xué)習(xí)(聚類)訓(xùn)練數(shù)據(jù)的類標(biāo)號(hào)不可知是觀察式學(xué)習(xí)基于距離的方法基于決策樹的方法基于神經(jīng)網(wǎng)絡(luò)的方法基于規(guī)則的方法常用分類方法預(yù)測的準(zhǔn)確率這涉及模型正確地預(yù)測新的或先前未見過的數(shù)據(jù)的類標(biāo)號(hào)的能力速度構(gòu)造模型的速度利用模型進(jìn)行分類的速度強(qiáng)壯性給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力可伸縮性當(dāng)給定大量數(shù)據(jù)時(shí)，有效地構(gòu)造模型的能力可解釋性涉及學(xué)習(xí)模型提供的理解和洞察的層次評(píng)價(jià)分類方法

分類分類的概念基于距離的分類方法BayesianClassificationClassificationbyBackPropagationSupportVectorMachinesAssociativeClassification:ClassificationbyassociationruleanalysisLazyLearners(orLearningfromyourNeighbors)OtherClassificationMethodsPredictionAccuracySummary基于距離的分類算法與一個(gè)類中的成員和另一個(gè)類中的成員之間的相似性相比，被映射到同一個(gè)類中的成員彼此之間被認(rèn)為是更加相似的。相似性（距離）度量可以用來識(shí)別數(shù)據(jù)庫中不同成員之間的“相似程度”。定義給定一個(gè)數(shù)據(jù)庫D={t1，t2，…，tn}和一組類C={C1，…，Cm}。假定每個(gè)元組包括一些數(shù)值型的屬性值：ti={ti1，ti2，…，tik}，每個(gè)類也包含數(shù)值性屬性值：Cj={Cj1，Cj2，…，Cjk}，則分類問題是要分配每個(gè)ti到滿足如下條件的類Cj：sim(ti，Cj)>=sim(ti，Cl)，Cl∈C，Cl≠Cj，其中sim(ti，Cj)被稱為相似性。在實(shí)際的計(jì)算中往往用距離來表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。距離的計(jì)算方法有多種，最常用的是通過計(jì)算每個(gè)類的中心來完成?；诰嚯x的分類算法基于距離的分類算法的一般性描述算法通過對(duì)每個(gè)元組和各個(gè)類的中心來比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。算法基于距離的分類算法輸入：每個(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.

基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結(jié)果K最近鄰居算法（KNN）Nearestneighbor(KNN)通過計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。訓(xùn)練樣本用n維數(shù)值屬性描述。每個(gè)樣本代表n維空間的一個(gè)點(diǎn)。所有的訓(xùn)練樣本都放在n維模式空間中。給定一個(gè)樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的k個(gè)訓(xùn)練樣本。K最近鄰居算法（KNN）要求的信息訓(xùn)練集距離計(jì)算值要獲取的最鄰近的鄰居的數(shù)目k一個(gè)未知的記錄進(jìn)行分類計(jì)算與其它訓(xùn)練記錄之間的距離識(shí)別出k個(gè)最近的鄰居使用最近鄰居的類標(biāo)號(hào)來標(biāo)識(shí)未知元組的類（bytakingmajorityvote）K最近鄰居算法（KNN）計(jì)算兩個(gè)點(diǎn)之間的距離如：Euclideandistance從最近鄰居列表中決定分類的結(jié)果選出k個(gè)最近的鄰居中的多數(shù)票的類標(biāo)號(hào)可以根據(jù)距離為每一個(gè)投票增加權(quán)重Weightfactor,w=1/d2算法K-近鄰分類算法輸入：訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。輸出：輸出類別c。（1）N=；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪baosb5w；（5）ELSE（6） IFu∈Nsuchthatsim(t，u)<sim(t，d)THENBEGIN（7） N=N-{u}；（8） N=N∪ukde4gb；（9） END（10）END（11）c=classtowhichthemostu∈N.K最近鄰居算法（KNN）實(shí)例姓名性別身高(米) 類別 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 中等“高度”用于計(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>、<Bob，男，1.85

>、<Kathy，女，1.6>、<Dave，男，1.7>和<Stephanie，女，1.7>}。對(duì)第9和10個(gè)記錄，沒變化。對(duì)第11個(gè)記錄d=<Debbie，女，1.8>，得到N={<Kristina，女，1.6>、<Debbie，女，1.8>、<Kathy，女，1.6>

、<Dave，男，1.7>和<Stephanie，女，1.7>}。對(duì)第12到14個(gè)記錄，沒變化。對(duì)第15個(gè)記錄d=<Wynette，女，1.75>，得到N={<Kristina，女，1.6>、<Wynette，女，1.75>、<Kathy，女，1.6>、<Dave，男，1.7>和<Stephanie，女，1.7>}。最后的輸出元組是<Kristina，女，1.6>、<Kathy，女，1.6>、<Stephanie，女，1.7>、<Dave，男，1.7>和<Wynette，女，1.75>。其中，四個(gè)屬于矮個(gè)、一個(gè)屬于中等。最終KNN方法認(rèn)為Pat為矮個(gè)。K最近鄰居算法（KNN）K值的選取如果k過于小，那么將會(huì)對(duì)數(shù)據(jù)中存在的噪聲過于敏感如果k過大，鄰居中可能包含其他類的點(diǎn)一個(gè)經(jīng)驗(yàn)的取值法則為k≤，q為訓(xùn)練元組的數(shù)目。商業(yè)算法通常以10作為默認(rèn)值。

分類分類的概念基于距離的分類方法基于決策樹的分類方法ClassificationbyBackPropagationSupportVectorMachinesAssociativeClassification:ClassificationbyassociationruleanalysisLazyLearners(orLearningfromyourNeighbors)OtherClassificationMethodsPredictionAccuracySummary基于決策樹的分類方法決策樹（decisiontree）決策樹是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。類似于流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸出，而每個(gè)樹葉節(jié)點(diǎn)代表類或類分布。樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。例如，在貸款申請(qǐng)中，要對(duì)申請(qǐng)的風(fēng)險(xiǎn)大小做出判斷。收入>40000高負(fù)債工作時(shí)間>5年是否是否“年收入大于￥40000”并且“高負(fù)債”的用戶被認(rèn)為是“高風(fēng)險(xiǎn)”；“年收入小于￥40000”但“工作時(shí)間大于5年”的申請(qǐng)，是“低風(fēng)險(xiǎn)”；NYYNNY

puter的決策樹示意Age?

Credit_rating?

student?

yes

no

yesyes

no

<=30?

>40

30~40yes

no

fairexcellent

決策樹（decisiontree）1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進(jìn)的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizableinductionofdecisiontrees)是比較有代表性的兩個(gè)算法?；跊Q策樹的分類方法

決策樹分類的特點(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í)過程中不需要使用者了解很多背景知識(shí)（這同時(shí)也是它的最大的缺點(diǎn)），只要訓(xùn)練例子能夠用屬性-結(jié)論式表示出來，就能使用該算法來學(xué)習(xí)。使用決策樹進(jìn)行分類分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個(gè)過程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過程。第2步：利用生成完畢的決策樹對(duì)輸入數(shù)據(jù)進(jìn)行分類。對(duì)輸入的記錄，從根結(jié)點(diǎn)依次測試記錄的屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類。

決策樹分類的步驟

問題的關(guān)鍵是建立一棵決策樹，即決策樹分類模型的建立。這個(gè)過程通常分為兩個(gè)階段：建樹（TreeBuilding）：決策樹建樹算法見下，可以看得出，這是一個(gè)遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。

決策樹分類的步驟決策樹歸納算法基本算法(貪心算法)樹以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始（根）（所有的數(shù)據(jù)都在根結(jié)點(diǎn)）如果樣本都在同一類。則該結(jié)點(diǎn)成為樹葉，并用該類標(biāo)記；決策樹歸納算法基本算法(貪心算法)否則，選擇能夠最好的將樣本分類的屬性，該屬性成為該結(jié)點(diǎn)的“測試”或“判定”屬性；對(duì)于測試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分枝，并據(jù)此劃分樣本；算法使用同樣的過程，遞歸的形成每個(gè)劃分上的樣本決策樹；決策樹歸納算法可以清楚地看到，決策樹是一種自頂向下增長樹的貪婪算法，在每個(gè)節(jié)點(diǎn)選取能最好分類樣本的屬性，繼續(xù)這個(gè)過程直到這棵樹能完美地分類訓(xùn)練集，或所有的屬性均已被用過。算法的重點(diǎn)是屬性的選取。決策樹歸納算法算法遞歸執(zhí)行的終止條件（停止分支的條件）對(duì)于給定的節(jié)點(diǎn)，所有的例子都屬于同一個(gè)類雖然對(duì)于某一個(gè)節(jié)點(diǎn)當(dāng)前的例子不屬于同一個(gè)類，但是已經(jīng)沒有屬性可用來選擇繼續(xù)進(jìn)行分支處理。此時(shí)采用majorityvoting投票的方式?jīng)Q定分類結(jié)果沒有用于分支的例子（樣本滿足屬性的取值）,以Samples中的多數(shù)創(chuàng)建一個(gè)樹葉，作為分類的結(jié)果

決策樹生成算法描述DTree(examples,attributes)

If所有樣本屬于同一分類，返回標(biāo)號(hào)為該分類的葉結(jié)點(diǎn)

Elseif屬性值為空，返回標(biāo)號(hào)為最普遍分類的葉結(jié)點(diǎn)

Else選取一個(gè)屬性，A，作為根結(jié)點(diǎn)

ForA的每一個(gè)可能的值vi

令examplesi為具有A=vi的樣本子集

從根結(jié)點(diǎn)出發(fā)增加分支（A=vi)

如果examplesi為空則創(chuàng)建標(biāo)號(hào)為最普遍分類的葉結(jié)點(diǎn)

否則遞歸創(chuàng)建子樹——調(diào)用

DTree(examplesi,attributes-{A})ID3算法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)。采用信息增益來選擇能夠最好地將樣本分類的屬性。決策樹深入分裂屬性選擇決策樹的簡化分裂屬性選擇選擇屬性的方法選擇具有最大信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測試屬性該屬性使得對(duì)結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性。用信息增益這種信息論的理論方法，使得對(duì)一個(gè)對(duì)象分類所需要的期望測試數(shù)目達(dá)到最小，并確保找到一棵簡單的樹。分裂屬性選擇怎樣計(jì)算信息增益（informationgain）通過描述屬性可以減少類標(biāo)屬性的不確定性。如：由番茄、茄子、黃瓜三種蔬菜，現(xiàn)在對(duì)蔬菜分類。在不給任何描述時(shí)，該蔬菜可能是番茄、茄子、黃瓜三種之一，不確定性大。給出該蔬菜是“長形”形狀描述時(shí)，該蔬菜可能是茄子、黃瓜兩種之一，不確定性減少。在給出該蔬菜是“紫的”顏色描述時(shí)，只可能是茄子了，不確定性為零。怎樣計(jì)算信息增益（informationgain）雖然通過描述屬性可以減少類標(biāo)屬性的不確定性，但是不同描述屬性減少類標(biāo)屬性不確性的程度不同，即不同描述屬性對(duì)減少類標(biāo)屬性不確定性的貢獻(xiàn)不同。這種不確定性可以用信息論中的熵來描述。分裂屬性選擇分裂屬性選擇怎樣計(jì)算信息增益（informationgain）如：假設(shè)有番茄、茄子、黃瓜三種蔬菜，對(duì)某蔬菜分類，形狀描述與顏色描述的貢獻(xiàn)是不同的。在給出蔬菜的顏色描述時(shí)，如果顏色是紅的，則該蔬菜是番茄；如果顏色是紫的，則該蔬菜是茄子；如果顏色是綠的，則該蔬菜是黃瓜，不確定性減少為0。而在給出該蔬菜形狀時(shí)，如果形狀是圓的，則該蔬菜是番茄；如果形狀是長的，則該蔬菜可能是茄子，也可能是黃瓜，不確定性還是存在。怎樣計(jì)算信息增益（informationgain）信息增益被定義為原始分割的熵與劃分以后各分割的熵累加得到的總熵之間的差。信息增益是指劃分前后進(jìn)行正確預(yù)測所需的信息量之差。選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測試屬性。分裂屬性選擇

設(shè)S是有s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci（i=1,2,…,m），si是類Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類所需要的期望信息為：

其中pi是任意樣本屬于Ci的概率，可用si/s來估計(jì)信息增益的計(jì)算其中為第j個(gè)子集的權(quán)，等于子集（A值為aj）中的樣本數(shù)除以S中的樣本數(shù)。

設(shè)屬性A具有v個(gè)不同值{a1,a2,…,av}，則可用屬性A將S劃分為v個(gè)子集{S1,S2,…,Sv}，Sj中包含的樣本在屬性A上具有值aj。如果選擇A作為測試屬性，則這些子集對(duì)應(yīng)于由包含集合S的結(jié)點(diǎn)生長出來的分枝。設(shè)sij是子集Sj中類Ci的樣本數(shù)，則按照A劃分成子集的熵為：

信息增益的計(jì)算由A劃分的信息增益為：

Gain(A)=I(s1,s2,…,sm)-E(A)

對(duì)于給定的子集Sj，它的信息I(s1j,s2j,…,smj)可用下式計(jì)算是Sj中的樣本屬于類Ci的概率信息增益的計(jì)算ID3–信息量大小的度量決策樹算法Gain（S，A）是屬性A在集合S上的信息增益Gain（S，A）=Entropy（S）-Entropy（S，A）Gain（S，A）越大，說明選擇測試屬性對(duì)分類提供的信息越多計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第1步計(jì)算決策屬性的熵決策屬性“買計(jì)算機(jī)？”。該屬性分兩類：買/不買S1(買)=641S2（不買）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2步計(jì)算條件屬性的熵條件屬性共有4個(gè)。分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2-1步計(jì)算年齡的熵年齡共分三個(gè)組：青年、中年、老年青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2-2步計(jì)算年齡的熵年齡共分三個(gè)組：青年、中年、老年中年買與不買比例為256/0S1(買)=256S2（不買）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2-3步計(jì)算年齡的熵年齡共分三個(gè)組：青年、中年、老年老年買與不買比例為125/127S1(買)=125S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第2-4步計(jì)算年齡的熵年齡共分三個(gè)組：青年、中年、老年所占比例青年組384/1025=0.375中年組256/1024=0.25老年組384/1024=0.375計(jì)算年齡的平均信息期望E（年齡）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年齡信息增益）

=0.9537-0.6877=0.2660（1）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第3步計(jì)算收入的熵收入共分三個(gè)組：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第4步計(jì)算學(xué)生的熵學(xué)生共分二個(gè)組：學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811=0.1726（3）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第5步計(jì)算信譽(yù)的熵信譽(yù)分二個(gè)組：良好，優(yōu)秀E（信譽(yù)）=0.9048信譽(yù)信息增益=0.9537-0.9048=0.0453（4）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買第6步計(jì)算選擇節(jié)點(diǎn)年齡信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年齡信息增益=0.9537-0.7811=0.1726（3）信譽(yù)信息增益=0.9537-0.9048=0.0453（4）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡青年中年老年買/不買買買/不買葉子決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入作為節(jié)點(diǎn)分高、中、低平均信息期望（加權(quán)總和）：

E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183

–0.4592=0.4591I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667注意決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買年齡青年中年老年學(xué)生買信譽(yù)葉子否是優(yōu)良買不買買/不買買葉子葉子葉子決策樹算法

決策樹歸納算法計(jì)算每個(gè)屬性的信息增益，并從中挑選出信息增益最大的屬性作為給定集合S的測試屬性并由此產(chǎn)生相應(yīng)的分支結(jié)點(diǎn)。所產(chǎn)生的結(jié)點(diǎn)被標(biāo)記為相應(yīng)的屬性，并根據(jù)這一屬性的不同取值分別產(chǎn)生相應(yīng)的（決策樹）分支，每個(gè)分支代表一個(gè)被劃分的樣本子集。信息增益的計(jì)算實(shí)例1：一個(gè)商場顧客數(shù)據(jù)庫（訓(xùn)練樣本集合）樣本集合的類別屬性為：“puter”，該屬性有兩個(gè)不同取值，即{yes,no}，因此就有兩個(gè)不同的類別(m=2)。設(shè)C1對(duì)應(yīng)類別yes，C2對(duì)應(yīng)類別no。類別C1包含9個(gè)樣本，類別C2包含5個(gè)樣本。為了計(jì)算每個(gè)屬性的信息增益，首先利用公式計(jì)算出所有（對(duì)一個(gè)給定樣本進(jìn)行分類所需要）的信息，具體計(jì)算過程如下：實(shí)例1：接著需要計(jì)算每個(gè)屬性的（信息）熵。假設(shè)先從屬性“age”開始，根據(jù)屬性“age”每個(gè)取值在

yes類別和no類別中的分布，就可以計(jì)算出每個(gè)分布所對(duì)應(yīng)的信息。實(shí)例1：然后利用公式計(jì)算出若根據(jù)屬性“age”對(duì)樣本集合進(jìn)行劃分，所獲得對(duì)一個(gè)數(shù)據(jù)對(duì)象進(jìn)行分類而需要的信息熵為：由此獲得利用屬性“age”對(duì)樣本集合進(jìn)行劃分所獲得的信息增益為：實(shí)例1：類似可得Gain(e)=0.029，Gain(student)=0.151，Gain(credit_rating)=0.048。顯然選擇屬性“age”所獲得的信息增益最大，因此被作為測試屬性用于產(chǎn)生當(dāng)前分支結(jié)點(diǎn)。這個(gè)新產(chǎn)生的結(jié)點(diǎn)被標(biāo)記為“age”；同時(shí)根據(jù)屬性“age”的三個(gè)不同取值，產(chǎn)生三個(gè)不同的分支，當(dāng)前的樣本集合被劃分為三個(gè)子集，如圖所示。最終產(chǎn)生的決策樹?實(shí)例1：編號(hào)年齡學(xué)生信譽(yù)等級(jí)類別標(biāo)號(hào)1<=30是良好會(huì)購買2<=30是一般會(huì)購買3>40否一般會(huì)購買4>40否良好不會(huì)購買5>40否一般會(huì)購買631~40是一般會(huì)購買7<=30否良好不會(huì)購買8>40是一般會(huì)購買9<=30否良好不會(huì)購買10>40否良好不會(huì)購買11<=30否一般不會(huì)購買1231~40是一般會(huì)購買1331~40否一般會(huì)購買1431~40是良好會(huì)購買實(shí)例1：“年齡”在各個(gè)屬性中具有最大的信息增益，所以選擇“年齡”屬性作為第一個(gè)測試屬性，創(chuàng)建一個(gè)節(jié)點(diǎn)，用“年齡”標(biāo)記。計(jì)算剩余各個(gè)屬性的相應(yīng)的信息增益，選擇信息增益最大的屬性作為測試屬性，這時(shí)信息增益最大的是“學(xué)生”屬性，創(chuàng)建一個(gè)節(jié)點(diǎn)，用“學(xué)生”標(biāo)記。實(shí)例1：決策樹中分類規(guī)則獲取決策樹所表示的分類知識(shí)可以被抽取出來并可用IF-THEN分類規(guī)則形式加以表示。從決策樹的根結(jié)點(diǎn)到任一個(gè)葉結(jié)點(diǎn)所形成的一條路徑就構(gòu)成了一條分類規(guī)則。沿著決策樹的一條路徑所形成的屬性-值偶對(duì)就構(gòu)成了分類規(guī)則條件部分（IF部分）中的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)所標(biāo)記的類別就構(gòu)成了規(guī)則的結(jié)論內(nèi)容（THEN部分）。

IF-THEN分類規(guī)則表達(dá)方式易于被人理解，且當(dāng)決策樹較大時(shí)，IF-THEN規(guī)則表示形式的優(yōu)勢就更加突出。ExampleIFage=“<=30”ANDstudent=“no”THENputer=“no”IFage=“<=30”ANDstudent=“yes”THENputer=“yes”IFage=“31…40” THENputer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENputer=“no”IFage=“<=30”ANDcredit_rating=“fair”THENputer=“yes”樣本數(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

目標(biāo)分類屬性是lays_eggs，計(jì)算I(lays_eggs)：由于feathers在屬性中具有最高的信息增益，所以它首先被選作測試屬性。并以此創(chuàng)建一個(gè)結(jié)點(diǎn)，數(shù)據(jù)集被劃分成兩個(gè)子集。實(shí)例2warm_blooded=1warm_blooded=0類似的，Gain(feathers)=0.459；Gain(fur)=0.316；

Gain(swims)=0.044。根據(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é)束。ID3決策樹建立算法1決定分類屬性；2對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn)N3如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個(gè)類，N就是樹葉，在樹葉上標(biāo)出所屬的類4如果數(shù)據(jù)表中沒有其他屬性可以考慮，則N也是樹葉，按照少數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別5否則，根據(jù)平均信息期望值E或GAIN值選出一個(gè)最佳屬性作為節(jié)點(diǎn)N的測試屬性6節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值：從N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹。決策樹算法ID3算法的性能分析ID3算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間。所以ID3算法避免了搜索不完整假設(shè)空間的一個(gè)主要風(fēng)險(xiǎn)：假設(shè)空間可能不包含目標(biāo)函數(shù)。ID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例，大大降低了對(duì)個(gè)別訓(xùn)練樣例錯(cuò)誤的敏感性。因此，通過修改終止準(zhǔn)則，可以容易地?cái)U(kuò)展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。ID3算法在搜索過程中不進(jìn)行回溯。所以，它易受無回溯的爬山搜索中的常見風(fēng)險(xiǎn)影響：收斂到局部最優(yōu)而不是全局最優(yōu)。決策樹的數(shù)據(jù)準(zhǔn)備姓名年齡收入學(xué)生信譽(yù)電話地址郵編買計(jì)算機(jī)張三234000是良

2714Ave.M77388買李四342800否優(yōu)

5606HollyCr78766買王二701900否優(yōu)

2000BellBlvd.70244不買趙五18900是良

100MainStreet70244買劉蘭342500否優(yōu)

606HollyCt78566買楊俊278900否優(yōu)

233RiceBlvd.70388不買張毅389500否優(yōu)

399SugarRd.78244買。。。。。。。。原始表決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買。。。整理后的數(shù)據(jù)表決策樹的數(shù)據(jù)準(zhǔn)備Datacleaning

刪除/減少noise，補(bǔ)填missingvaluesDatatransformation

數(shù)據(jù)標(biāo)準(zhǔn)化（datanormalization） 數(shù)據(jù)歸納（generalizedatatohigher-levelconceptsusingconcepthierarchies） 例如：年齡歸納為老、中、青三類 控制每個(gè)屬性的可能值不超過七種（最好不超過五種）Relevanceanalysis

對(duì)于與問題無關(guān)的屬性：刪 對(duì)于屬性的可能值大于七種又不能歸納的屬性：刪決策樹算法決策樹的數(shù)據(jù)準(zhǔn)備決策樹算法處理連續(xù)屬性值

決策樹算法比較適合處理離散數(shù)值的屬性。實(shí)際應(yīng)用中屬性是連續(xù)的或者離散的情況都比較常見。在應(yīng)用連續(xù)屬性值時(shí)，在一個(gè)樹結(jié)點(diǎn)可以將屬性Ai的值劃分為幾個(gè)區(qū)間。然后信息增益的計(jì)算就可以采用和離散值處理一樣的方法。原則上可以將Ai的屬性劃分為任意數(shù)目的空間。C4.5中采用的是二元分割（BinarySplit）。需要找出一個(gè)合適的分割閾值。參考C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem200814:1–37決策樹算法ID3算法小結(jié)ID3算法是一種經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變?yōu)樽钚〉膶傩?，以?gòu)造一顆熵值下降最快的決策樹，到葉子節(jié)點(diǎn)處的熵值為0。此時(shí)，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的實(shí)例集中的實(shí)例屬于同一類。決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）

通過ID3算法來實(shí)現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的特征，以幫助電信公司有針對(duì)性地改善客戶關(guān)系，避免客戶流失利用決策樹方法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)處理、決策樹挖掘操作，模式評(píng)估和應(yīng)用。電信運(yùn)營商的客戶流失有三方面的含義：一是指客戶從一個(gè)電信運(yùn)營商轉(zhuǎn)網(wǎng)到其他電信運(yùn)營商，這是流失分析的重點(diǎn)。二是指客戶月平均消費(fèi)量降低，從高價(jià)值客戶成為低價(jià)值客戶。三、指客戶自然流失和被動(dòng)流失。在客戶流失分析中有兩個(gè)核心變量：財(cái)務(wù)原因／非財(cái)務(wù)原因、主動(dòng)流失／被動(dòng)流失。客戶流失可以相應(yīng)分為四種類型：其中非財(cái)務(wù)原因主動(dòng)流失的客戶往往是高價(jià)值的客戶。他們會(huì)正常支付服務(wù)費(fèi)用，并容易對(duì)市場活動(dòng)有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（2）數(shù)據(jù)預(yù)處理數(shù)據(jù)挖掘的處理對(duì)象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲(chǔ)在數(shù)據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲(chǔ)在其CRM中），是長期積累的結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般包括數(shù)據(jù)的選擇(選擇相關(guān)的數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分，對(duì)于挖掘算法的效率乃至正確性都有關(guān)鍵性的影響。該公司經(jīng)過多年的電腦化管理，已有大量的客戶個(gè)人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號(hào)碼、用戶標(biāo)識(shí)、用戶身份證號(hào)碼(轉(zhuǎn)化為年齡)、在網(wǎng)時(shí)間（竣工時(shí)間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)）等等，數(shù)據(jù)準(zhǔn)備時(shí)必須除掉表中一些不必要的屬性，一般可采用面向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（3）屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標(biāo)識(shí)、身份證號(hào)碼等，它們的取值太多且無法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表1。

表1客戶信息表年齡學(xué)歷職業(yè)繳費(fèi)方式在網(wǎng)時(shí)長費(fèi)用變化率客戶流失58大學(xué)公務(wù)員托收1310%NO47高中工人營業(yè)廳繳費(fèi)942%NO26研究生公務(wù)員充值卡263%YES28大學(xué)公務(wù)員營業(yè)廳繳費(fèi)52.91%NO32初中工人營業(yè)廳繳費(fèi)32.3%NO42高中無業(yè)人員充值卡2100%YES68初中無業(yè)人員營業(yè)廳繳費(fèi)92.3%NO決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（4）屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進(jìn)行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(xué)(?？?、本科及以上)；職業(yè)類別：按工作性質(zhì)來分共分3類：Z1一Z3；繳費(fèi)方式：托收：T1,營業(yè)廳繳費(fèi)：T2,充值卡：T3。連續(xù)型屬性概化為區(qū)間值：表中年齡、費(fèi)用變化率和在網(wǎng)時(shí)間為連續(xù)型數(shù)據(jù)，由于建立決策樹時(shí)，用離散型數(shù)據(jù)進(jìn)行處理速度最快，因此對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，根據(jù)專家經(jīng)驗(yàn)和實(shí)際計(jì)算信息增益，在“在網(wǎng)時(shí)長”屬性中，通過檢測每個(gè)劃分，得到在閾值為5年時(shí)信息增益最大，從而確定最好的劃分是在5年處，則這個(gè)屬性的范圍就變?yōu)椋?lt;=5,>5：H1,H2｝。而在“年齡”屬性中，信息增益有兩個(gè)鋒值，分別在40和50處，因而該屬性的范圍變?yōu)閧<=40,>40-<=50,>50}即變?yōu)閧青年，中年，老年：N1,N2,N3}；費(fèi)用變化率：指（（當(dāng)月話費(fèi)－近3個(gè)月的平均話費(fèi)）/近3個(gè)月的平均話費(fèi)）×％>0，F(xiàn)1:<＝30%，F(xiàn)2：30%-99%,F3:＝100%變?yōu)椋鸉1,F2,F3｝。

表2轉(zhuǎn)化后的客戶信息表年齡學(xué)歷職業(yè)繳費(fèi)方式開戶時(shí)間費(fèi)用變化率客戶流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（5）YESNO年齡職業(yè)YES繳費(fèi)方式Y(jié)ESYESNOYSESNONO在網(wǎng)時(shí)長NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2費(fèi)用變化率決策樹算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（6）

在圖中，NO表示客戶不流失，YES表示客戶流失。從圖可以看出，客戶費(fèi)用變化率為100%的客戶肯定已經(jīng)流失；而費(fèi)用變化率低于30%的客戶；即每月資費(fèi)相對(duì)穩(wěn)定的客戶一般不會(huì)流失，費(fèi)用變化率在30%～99%的客戶有可能流失，其中年齡在40～50歲之間的客戶流失的可能性非常大，而年齡低于40歲的客戶，用充值卡繳費(fèi)的客戶和在網(wǎng)時(shí)間較短的客戶容易流失；年齡較大的客戶，則工人容易流失。C4.5算法對(duì)ID3的主要改進(jìn)C4.5算法是從ID3算法演變而來，除了擁有ID3算法的功能外，C4.5克服了ID3在應(yīng)用中的不足，主要體現(xiàn)在：用信息增益比例/信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向于選擇取值多的屬性的不足；能夠完成對(duì)連續(xù)屬性的離散化處理；可以處理具有缺少屬性值的訓(xùn)練樣本；在數(shù)構(gòu)造過程中或者構(gòu)造完成之后，進(jìn)行剪枝以避免樹的過度擬合；C4.5采用的知識(shí)表示形式為決策樹，并最終可以形成產(chǎn)生式規(guī)則。

信息增益比例的概念信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來的，一個(gè)屬性的信息增益比例用下面的公式給出：其中而分裂信息SplitInfo(S,A)代表了按照屬性A分裂樣本集S的廣度和均勻性。假如以屬性A的值為基準(zhǔn)對(duì)樣本進(jìn)行分割的化，SplitI(A)就是前面熵的概念。

如按照屬性A把S集（含30個(gè)用例）分成了10個(gè)用例和20個(gè)用例兩個(gè)集合則

SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3)簡單地說，針對(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)的增益比率，選擇增益率最大的劃分來對(duì)屬性A進(jìn)行離散化。C4.5處理連續(xù)值的屬性C4.5算法例子樣本數(shù)據(jù)OutlookTemperatureHumidityWindPlayTennis 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 No1）首先對(duì)Humidity進(jìn)行屬性離散化，針對(duì)上面的訓(xùn)練集合，通過檢測每個(gè)劃分而確定最好的劃分在75處，則這個(gè)屬性的范圍就變?yōu)閧（<=75，>75）}。2）計(jì)算目標(biāo)屬性PlayTennis分類的期望信息：

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

4）選取最大的GainRatio，根據(jù)Outlook的取值，得到三個(gè)分支。5）再擴(kuò)展各分枝節(jié)點(diǎn)，得到最終的決策樹。決策樹研究問題理想的決策樹有三種：

(1)葉子結(jié)點(diǎn)數(shù)最少；

(2)葉子結(jié)點(diǎn)深度最?。?/p>

(3)葉子結(jié)點(diǎn)數(shù)最少且葉子結(jié)點(diǎn)深度最小。

然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)的決策樹是NP難題。因此，決策樹優(yōu)化的目的就是要找到盡可能趨向于最優(yōu)的決策樹。關(guān)于過渡擬合

上述的決策樹算法增長樹的每一個(gè)分支的深度，直到恰好能對(duì)訓(xùn)練樣例比較完美地分類。實(shí)際應(yīng)用中，當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時(shí)，該策略可能會(huì)遇到困難。在以上情況發(fā)生時(shí)，這個(gè)簡單的算法產(chǎn)生的樹會(huì)過渡擬合訓(xùn)練樣例（過渡擬合：OverFitting）.決策樹研究問題關(guān)于過渡擬合

對(duì)于一個(gè)假設(shè)，當(dāng)存在其它的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布上（包含訓(xùn)練集合以外的實(shí)例）表現(xiàn)得卻更好時(shí)，則稱該假設(shè)過度擬合訓(xùn)練樣例。過度擬合：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)h∈H，如果存在其它的假設(shè)h1∈H,使得在訓(xùn)練樣例上h的錯(cuò)誤率比h1小，但在整個(gè)實(shí)例發(fā)布上h1的錯(cuò)誤率比h小，則稱假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)過度擬合產(chǎn)生的原因：噪聲，訓(xùn)練樣例太小等決策樹研究問題關(guān)于過渡擬合

對(duì)學(xué)習(xí)算法是否成功的真正測試是看它對(duì)于訓(xùn)練中未見到的數(shù)據(jù)的執(zhí)行性能。訓(xùn)練過程應(yīng)該包含訓(xùn)練樣本和驗(yàn)證樣本。驗(yàn)證樣本用于測試訓(xùn)練后的性能。如果驗(yàn)證結(jié)果差，則需要考慮采用不同的結(jié)構(gòu)重新進(jìn)行訓(xùn)練，例如使用更大的樣本集，或者改變從連續(xù)值到離散值得數(shù)據(jù)轉(zhuǎn)換等。通常應(yīng)該建立一個(gè)驗(yàn)證過程，在訓(xùn)練最終完成后用來檢測訓(xùn)練結(jié)果的泛化能力。決策樹研究問題關(guān)于過渡擬合分類模型的誤差一般可以將分類模型的誤差分為：

1、訓(xùn)練誤差（TrainingError）；

2、泛化誤差（GeneralizationError）決策樹研究問題關(guān)于過渡擬合分類模型的誤差

訓(xùn)練誤差是在訓(xùn)練記錄上誤分類樣本比例；泛化誤差是模型在未知記錄上的期望誤差；一個(gè)好的模型不僅要能夠很好地?cái)M合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能夠準(zhǔn)確地分類。一個(gè)好的分類模型必須具有低的訓(xùn)練誤差和泛化誤差。因?yàn)橐粋€(gè)具有低訓(xùn)練誤差的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高。（訓(xùn)練誤差低，泛化誤差高，稱為過渡擬合）決策樹研究問題關(guān)于過渡擬合模型過渡擬合的潛在因素（1）噪聲導(dǎo)致的過渡擬合；

錯(cuò)誤的類別值/類標(biāo)簽，屬性值等（2）缺乏代表性樣本所導(dǎo)致的過渡擬合

根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過渡擬合的影響。由于訓(xùn)練樣本缺乏代表性的樣本，在沒有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會(huì)導(dǎo)致過渡擬合。決策樹研究問題關(guān)于過渡擬合模型過渡擬合的潛在因素名稱體溫胎生4條腿冬眠哺乳動(dòng)物蠑螈冷血NYYN虹鳉冷血YNNN鷹恒溫NNNN弱夜鷹恒溫NNYN鴨嘴獸恒溫YYYY哺乳動(dòng)物分類的訓(xùn)練樣例體溫恒溫冷血冬眠NYNN4條腿YNNY名稱體溫胎生4條腿冬眠哺乳動(dòng)物人恒溫YNNY大象恒溫YYNY鴿子恒溫NNNN哺乳動(dòng)物分類的訓(xùn)練樣例按照訓(xùn)練模型。人和大象都不是哺乳動(dòng)物。決策樹作出這樣的判斷是因?yàn)橹挥幸粋€(gè)訓(xùn)練樣例具有這些特點(diǎn)（鷹，恒溫，不冬眠）被劃分為非哺乳動(dòng)物。該例清楚表明，當(dāng)決策樹的葉節(jié)點(diǎn)沒有足夠的代表性時(shí)，可能會(huì)預(yù)測錯(cuò)誤。決策樹研究問題關(guān)于過渡擬合解決過度擬合的手段：

1及早停止樹增長；

2后修剪法。決策樹研究問題關(guān)于過渡擬合1及早停止樹增長

由于決策樹學(xué)習(xí)要從候選集合眾選擇滿足給定標(biāo)準(zhǔn)的最大化屬性，并且不回溯，也就是我們常說的爬山策略，其選擇往往會(huì)是局部最優(yōu)而不是全局最優(yōu)。樹結(jié)構(gòu)越復(fù)雜，則過渡擬合發(fā)生的可能性越大。因此，要選擇簡單的模型。

Occan法則（又稱Occan剃刀OccanRazor）:具有相同泛化誤差的兩個(gè)模型，較簡單的模型比復(fù)雜的模型更可取。決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）

在訓(xùn)練過程中允許對(duì)數(shù)據(jù)的過渡擬合，然后再對(duì)樹進(jìn)行修剪該方法稱為后剪枝法。決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN

一棵通過訓(xùn)練集合學(xué)好的決策樹決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN實(shí)例ABC類別錯(cuò)分類1YYY+2YYY+3YYY+4YYY+5YYY+6YYN-*7YYN-*8YYN-*9YNY+10YNY+11YNY+12YNY+13YNN+*14YNN+*15YNN-16YNN-17YNN-18NNN-19NYN-20NYY-對(duì)以上的決策樹通過右側(cè)的驗(yàn)證集合進(jìn)行測試，發(fā)現(xiàn)其有5個(gè)錯(cuò)分類。決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN{18，19，20}{1，2，3，45，6，7，8}{9，10，11，12}{13，14，15，16，17}錯(cuò)分類5個(gè)，6，7，8，13，14決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例第1步將決策樹規(guī)則化規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

AB負(fù)C正正負(fù)YYYNNN決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

規(guī)則分類正確的數(shù)目分類錯(cuò)誤的數(shù)目精度1535/82404/43323/54303/3第2步規(guī)則精度的計(jì)算決策樹研究問題規(guī)則2與規(guī)則4精度為100%，保留關(guān)于過渡擬合后修剪法（后剪枝法）例規(guī)則分類正確的數(shù)目分類錯(cuò)誤的數(shù)目精度1535/82404/43323/54303/3第3步對(duì)規(guī)則進(jìn)行修剪規(guī)則去掉A去掉B去掉C去掉AB去掉BC去掉AC選擇15/1011/17去掉B34/66/83/98/104/106/17去掉AB決策樹研究問題?關(guān)于過渡擬合后修剪法（后剪枝法）例第3步對(duì)規(guī)則進(jìn)行修剪-最終規(guī)則集合為規(guī)則去掉A去掉B去掉C去掉AB去掉BC去掉AC選擇15/1011/17去掉B34/66/83/98/104/106/17去掉AB規(guī)則1IFA=YANDB=Y

THEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

原始規(guī)則集合規(guī)則1IFA=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFC=NTHEN–規(guī)則4IFA=NTHEN-

最終規(guī)則集合決策樹研究問題關(guān)于過渡擬合后修剪法（后剪枝法）例第4步根據(jù)精度和泛化能力對(duì)對(duì)規(guī)則進(jìn)行排序IFA=NTHEN-{18，19，20}IFA=YANDB=NANDC=YTHEN+{9,10,11,12}IFC=NTHEN–{6,7,8,13,14,15,16,17}IFA=YT