第七章 分類與預(yù)測(cè)課件

《數(shù)據(jù)挖掘》第七章分類與預(yù)測(cè)引言—要挖掘知識(shí)的類型概念描述：特征化和比較；關(guān)聯(lián)規(guī)則；

分類/預(yù)測(cè)；聚類分析；其他的數(shù)據(jù)挖掘任務(wù)。2第七章分類與預(yù)測(cè)引言根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥類的信息，我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物A，動(dòng)物B進(jìn)行分類？動(dòng)物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動(dòng)物豬大04否是爬行動(dòng)物牛大04否是爬行動(dòng)物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類動(dòng)物A大02是無？動(dòng)物B中22否是？分類是數(shù)據(jù)挖掘中重要的任務(wù)分類的目的是學(xué)會(huì)一個(gè)分類器（分類函數(shù)或模型），該分類器能把待分類的數(shù)據(jù)映射到給定的類別中。分類可用于預(yù)測(cè)。從歷史數(shù)據(jù)紀(jì)錄中自動(dòng)推導(dǎo)出對(duì)給定數(shù)據(jù)的推廣描述，從而能對(duì)未來數(shù)據(jù)進(jìn)行類預(yù)測(cè)。4第七章分類與預(yù)測(cè)分類方法的類型從使用的主要技術(shù)上看，可以把分類方法歸結(jié)為以下幾種類型：基于距離的分類方法決策樹分類方法貝葉斯分類方法。本章主要圍繞這幾種分類方法展開。5第七章分類與預(yù)測(cè)

第6章分類與預(yù)測(cè)第七章分類與預(yù)測(cè)6.1分類與預(yù)測(cè)的基本知識(shí)6.2基于距離的分類算法6.3決策樹分類方法6.4貝葉斯分類方法6.5規(guī)則歸納方法*

第6章第七章分類與預(yù)測(cè)6.1分類和預(yù)測(cè)的基本知識(shí)什么是分類？預(yù)測(cè)？分類和預(yù)測(cè)的基本問題第七章分類與預(yù)測(cè)1.分類？預(yù)測(cè)？第七章分類與預(yù)測(cè)基本概念分類和預(yù)測(cè)是兩種數(shù)據(jù)分析的形式，可用于提取描述重要數(shù)據(jù)類的模型或預(yù)測(cè)未來的數(shù)據(jù)趨勢(shì)：分類（classification）：用于預(yù)測(cè)數(shù)據(jù)對(duì)象的分類標(biāo)號(hào)（或離散值），如，通過構(gòu)造分類模型對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估（安全或危險(xiǎn)）；預(yù)測(cè)（predication）：用于預(yù)測(cè)數(shù)據(jù)對(duì)象的連續(xù)取值，如，建立預(yù)測(cè)模型利用顧客收入與職業(yè)（參數(shù)）預(yù)測(cè)其可能用于購(gòu)買計(jì)算機(jī)設(shè)備的支出大小。10第七章分類與預(yù)測(cè)數(shù)據(jù)分類過程數(shù)據(jù)分類是一個(gè)兩步的過程：1）建立分類模型：機(jī)器學(xué)習(xí)過程，通過某種分類算法對(duì)訓(xùn)練集進(jìn)行訓(xùn)練，得到分類模型；“有指導(dǎo)的學(xué)習(xí)”、“有監(jiān)督的學(xué)習(xí)”假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)稱為類標(biāo)號(hào)屬性的屬性確定；訓(xùn)練數(shù)據(jù)集：為建立分類模型而被分析的數(shù)據(jù)元組。11第七章分類與預(yù)測(cè)分類過程的第一步：學(xué)習(xí)建模12第七章分類與預(yù)測(cè)數(shù)據(jù)分類過程數(shù)據(jù)分類是一個(gè)兩步的過程：2）使用模型進(jìn)行分類：測(cè)試數(shù)據(jù)集：用于評(píng)估模型的預(yù)測(cè)準(zhǔn)確率。模型在測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本所占的百分比。如認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它來對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。13第七章分類與預(yù)測(cè)分類過程的第二步：分類測(cè)試14第七章分類與預(yù)測(cè)分類過程示意圖15第七章分類與預(yù)測(cè)有指導(dǎo)的學(xué)習(xí)VS.無指導(dǎo)的學(xué)習(xí)有指導(dǎo)的學(xué)習(xí)（用于分類）訓(xùn)練樣本的類標(biāo)號(hào)已知；新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類無指導(dǎo)的學(xué)習(xí)（用于聚類）訓(xùn)練樣本的類標(biāo)號(hào)未知；通過一系列的度量、觀察，試圖確立數(shù)據(jù)中的類或聚類的存在第七章分類與預(yù)測(cè)數(shù)據(jù)預(yù)測(cè)預(yù)測(cè)：構(gòu)造和使用模型評(píng)估無標(biāo)號(hào)樣本類，或評(píng)估給定樣本可能具有的屬性值或值區(qū)間與分類區(qū)別：二者是兩類主要的預(yù)測(cè)問題。

分類是預(yù)測(cè)離散或標(biāo)號(hào)值；預(yù)測(cè)是預(yù)測(cè)連續(xù)或有序值；觀點(diǎn)：用預(yù)測(cè)法預(yù)測(cè)類標(biāo)號(hào)為分類；用預(yù)測(cè)法預(yù)測(cè)連續(xù)值（一般用回歸法）為預(yù)測(cè)。17第七章分類與預(yù)測(cè)示例背景：假定已建立AllElectronics公司的郵寄清單數(shù)據(jù)庫。郵寄清單用于分發(fā)介紹新產(chǎn)品和降價(jià)信息材料。數(shù)據(jù)庫描述顧客的屬性，包括姓名、年齡、收入、職業(yè)和信譽(yù)度，并按照顧客是否在該公司購(gòu)買計(jì)算機(jī)進(jìn)行分類。18第七章分類與預(yù)測(cè)示例分類模型：

假定新的顧客添加到數(shù)據(jù)庫中，由于向每位顧客分發(fā)促銷材料費(fèi)用很高，因此，可以根據(jù)數(shù)據(jù)庫中已有顧客信息構(gòu)建分類模型，用以預(yù)測(cè)需向哪些顧客分發(fā)材料。預(yù)測(cè)模型：

假定想預(yù)測(cè)在一個(gè)財(cái)政年度，一個(gè)顧客將在AllElectronics進(jìn)行的主要的購(gòu)買的數(shù)量，則可以構(gòu)建一個(gè)預(yù)測(cè)模型。19第七章分類與預(yù)測(cè)2.分類和預(yù)測(cè)的基本問題？第七章分類與預(yù)測(cè)問題(1)：數(shù)據(jù)準(zhǔn)備1）準(zhǔn)備分類和預(yù)測(cè)的數(shù)據(jù)：數(shù)據(jù)的預(yù)處理數(shù)據(jù)清理：噪聲（平滑技術(shù)）；空缺值（統(tǒng)計(jì)手段）相關(guān)性分析（特征選擇）：刪除不相關(guān)和冗余屬性，如銀行貸款申請(qǐng)時(shí)填寫的星期數(shù)，可能與貸款是否申請(qǐng)成功無關(guān)；數(shù)據(jù)變換：數(shù)據(jù)離散化（數(shù)據(jù)概化）：如屬性“收入”的數(shù)值就可以被離散化為若干區(qū)間，如低、中等和高；數(shù)據(jù)規(guī)范化：將給定屬性的值按比例縮放至較小的區(qū)間，如[0,1]。21第七章分類與預(yù)測(cè)問題(2)：評(píng)估分類模型2）評(píng)估方法：對(duì)用于分類或預(yù)測(cè)的方法或模型進(jìn)行評(píng)估預(yù)測(cè)的準(zhǔn)確率：模型正確預(yù)測(cè)未知對(duì)象類別或數(shù)值的能力；速度：1）建立模型的時(shí)間；2）使用模型的時(shí)間強(qiáng)壯性（魯棒性）：處理噪聲和空缺值的能力；可伸縮（擴(kuò)展）性：處理大型數(shù)據(jù)及構(gòu)造模型的能力；可理解性：模型的可理解能力；規(guī)則的優(yōu)越性：1）判定樹的大??；2）分類規(guī)則的簡(jiǎn)潔性。22第七章分類與預(yù)測(cè)6.2基于距離的分類算法基本思想？

幾種常見的距離分類算法？第七章分類與預(yù)測(cè)1.基于距離分類的基本思想？第七章分類與預(yù)測(cè)基于距離的分類算法的思路定義：給定一個(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，Ci)，

Ci∈C，Ci≠Cj，其中sim(ti，Cj)被稱為相似性。25第七章分類與預(yù)測(cè)基于距離的分類算法的思路在實(shí)際的計(jì)算中往往用距離來表征：距離越近，相似性越大；距離越遠(yuǎn)，相似性越小。如何度量距離？歐幾里得距離；曼哈坦距離；明考斯基距離；加權(quán)的明考斯基距離。26第七章分類與預(yù)測(cè)（一）歐幾里得距離歐式距離由對(duì)應(yīng)元素間差值平方和的平方根所表示，即：

如何度量距離？第七章分類與預(yù)測(cè)（二）曼哈頓距離對(duì)應(yīng)元素間差值絕對(duì)值的和表示，即：

歐幾里得距離與曼哈頓距離的共同點(diǎn)：

(1)即距離是一個(gè)非負(fù)的數(shù)值

(2)自身的距離為0

(3)即距離函數(shù)具有對(duì)稱性

(4)即距離函數(shù)滿足三角不等式如何度量距離？第七章分類與預(yù)測(cè)(三)明可夫斯基距離

是歐幾里得距離和曼哈頓距離的概化其中p是一個(gè)正整數(shù)：當(dāng)p=1時(shí)，表示曼哈頓距離；當(dāng)p=2時(shí)，表示歐幾里得距離。(四)加權(quán)的明可夫斯基距離

如果對(duì)每一個(gè)變量根據(jù)其重要性賦予一個(gè)權(quán)重，就得到加權(quán)的明考斯基距離。如何度量距離？第七章分類與預(yù)測(cè)基于距離的分類算法的思路在實(shí)際的計(jì)算中往往用距離來表征：距離越近，相似性越大；距離越遠(yuǎn)，相似性越小。距離的計(jì)算方法有多種，最常用的是通過計(jì)算樣本到每個(gè)類中心的距離來完成。30第七章分類與預(yù)測(cè)基于距離的分類算法的一般性描述算法計(jì)算每個(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.31第七章分類與預(yù)測(cè)基于距離的分類方法的直觀解釋（a）類定義（b）待分類樣例（c）分類結(jié)果32第七章分類與預(yù)測(cè)距離分類例題例：C1=(3,3,4,2),C2=(8,5,-1,-7),C3=(-5,-7,6,10);請(qǐng)用基于距離的算法給以下樣本分類：A(5,5,0,0);B(5,5,-5,-5);C(-5,-5,5,5)3334距離分類例題歐幾里得距離：d(A,C1)=[(3-5)^2+(3-5)^2+(4-0)^2+(2-0)^2)]1/2=5.3;d(A,C2)=[(8-5)^2+(5-5)^2+(-5-0)^2+(-5-0)^2)]1/2=7.7;d(A,C3)=[(-5-5)^2+(-7-5)^2+(5-0)^2+(5-0)^2)]1/2=17.1顯然應(yīng)該將A劃入C1類。2幾種常見的距離分類算法？第七章分類與預(yù)測(cè)幾種常見的距離分類算法

（1）k-近鄰算法；

（2）K-means算法（聚類）；

（3）K-mediods算法（聚類）。36第七章分類與預(yù)測(cè)（1）K-近鄰分類算法K-近鄰分類算法（KNearestNeighbors，簡(jiǎn)稱KNN）通過計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。37第七章分類與預(yù)測(cè)（1）K-近鄰分類算法算法4-2K-近鄰分類算法輸入：訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。輸出：輸出類別c。（1）N=

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

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

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

38第七章分類與預(yù)測(cè)KNN的直觀解釋1、定義的直觀形式：找出與目標(biāo)最接近的K個(gè)樣本；將目標(biāo)劃分到找出的K個(gè)樣本中出現(xiàn)最頻繁的類。2、K的直觀形式：以目標(biāo)樣本為中心；劃出一個(gè)剛好包含K個(gè)樣本的圓；當(dāng)K增大時(shí)，圓半徑增大。第七章分類與預(yù)測(cè)KNN的直觀解釋3、直觀的例子手寫識(shí)別記錄手寫體特征；計(jì)算手寫體與標(biāo)準(zhǔn)漢字的相似度；根據(jù)相似度（距離），找出K個(gè)備選集；選擇一個(gè)正確漢字人種識(shí)別歐洲人的鼻子、亞洲人的眼睛非洲人的膚色、亞洲人的頭發(fā)第七章分類與預(yù)測(cè)形象的例子KNN的分類思想如果它走路像鴨子,叫聲也像鴨子,那么它可能就是只鴨子TrainingRecordsTestRecordComputeDistanceChoosekofthe“nearest”records第七章分類與預(yù)測(cè)KNN的特點(diǎn)1、非參數(shù)統(tǒng)計(jì)方法不需引入?yún)?shù)回歸分析是參數(shù)統(tǒng)計(jì)方法2、k的選擇K=1時(shí)，將待分類樣本劃入與其最接近的樣本的類；K=|X|時(shí)，僅根據(jù)訓(xùn)練樣本進(jìn)行頻率統(tǒng)計(jì)，將待分類樣本劃入最多的類；K需要合理選擇，太小容易受干擾、太大增加計(jì)算復(fù)雜性3、算法的復(fù)雜度維數(shù)災(zāi)難：當(dāng)維數(shù)增加時(shí)，算法的復(fù)雜度會(huì)急劇增加一般采用降維處理第七章分類與預(yù)測(cè)6.3決策樹分類算法

決策樹的基本概念？決策樹生成算法？剪枝方法？提取分類規(guī)則？第七章分類與預(yù)測(cè)1.決策樹的基本概念？第七章分類與預(yù)測(cè)決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學(xué)習(xí)算法學(xué)習(xí)模型模型應(yīng)用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓(xùn)練集（類標(biāo)號(hào)已知）檢驗(yàn)集（類標(biāo)號(hào)未知）歸納推論第七章分類與預(yù)測(cè)基本概念

決策樹（decisiontree）：決策樹是一種典型的分類方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策樹對(duì)新數(shù)據(jù)進(jìn)行分析。本質(zhì)上決策樹是通過一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過程。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買46第七章分類與預(yù)測(cè)決策樹的基本組成

決策樹的基本組成決策樹是類似流程圖的倒立的樹型結(jié)構(gòu)。最頂層節(jié)點(diǎn)為根節(jié)點(diǎn)，是整個(gè)決策樹的開始；樹的每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，其每個(gè)分支代表一個(gè)測(cè)試輸出；樹的每個(gè)葉節(jié)點(diǎn)代表一個(gè)類別。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買47第七章分類與預(yù)測(cè)基本概念決策樹的生成包括兩個(gè)過程：（1）樹的建立首先所有訓(xùn)練樣本都在根節(jié)點(diǎn)；依據(jù)所選的屬性循環(huán)地劃分樣本。（2）樹剪枝（treepruning）：在決策樹構(gòu)造時(shí)，許多分支可能反映的是訓(xùn)練數(shù)據(jù)中的噪聲或孤立點(diǎn)。樹剪枝就是識(shí)別并消除這類分支，以提高在未知數(shù)據(jù)上分類的準(zhǔn)確性。48第七章分類與預(yù)測(cè)49第七章分類與預(yù)測(cè)2.決策樹的生成算法？第七章分類與預(yù)測(cè)決策樹的生成算法基本的決策樹生成算法是一個(gè)貪心算法，采用自上而下、分而治之的遞歸方式來構(gòu)造。決策樹上的各個(gè)分支是在對(duì)數(shù)據(jù)不斷分組的過程中逐漸生長(zhǎng)出來的。首先，選擇一個(gè)屬性作為根節(jié)點(diǎn)，然后把該屬性的每一個(gè)可能的值作為子節(jié)點(diǎn)，這樣就把整個(gè)訓(xùn)練集分成了幾個(gè)子集，根節(jié)點(diǎn)屬性的每個(gè)取值都對(duì)應(yīng)著一個(gè)子集，然后遞歸應(yīng)用到每個(gè)子樹上進(jìn)行進(jìn)一步劃分，直到對(duì)所有數(shù)據(jù)的繼續(xù)分組不再有意義時(shí)，決策樹的生長(zhǎng)過程宣告結(jié)束，此時(shí)便生成了一棵完整的決策樹。其中，測(cè)試屬性的選擇是構(gòu)建決策樹的關(guān)鍵環(huán)節(jié)，不同的決策樹算法在此使用的技術(shù)都不盡相同。51第七章分類與預(yù)測(cè)決策樹的生成算法注意：在決策樹算法中，所有屬性均為符號(hào)值，即離散值，因此若有取連續(xù)值的屬性，必須首先進(jìn)行離散化。52第七章分類與預(yù)測(cè)決策樹的生成算法常見的有如下幾種決策樹生成算法：

CLS;ID3;C4.5;CART。53第七章分類與預(yù)測(cè)（1）CLS（ConceptLearningSystem）算法

CLS算法是早期的決策樹學(xué)習(xí)算法。它是許多決策樹學(xué)習(xí)算法的基礎(chǔ)。

CLS基本思想

從一棵空決策樹開始，選擇某一屬性（分類屬性）作為測(cè)試屬性。該測(cè)試屬性對(duì)應(yīng)決策樹中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng)于決策樹的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對(duì)該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。第七章分類與預(yù)測(cè)人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血CLS算法第七章分類與預(yù)測(cè)人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血CLS算法-決策樹的構(gòu)建眼睛顏色[1,6][2,4,8][3,5,7]黑色藍(lán)色灰色不屬于同一類，非葉結(jié)點(diǎn)第七章分類與預(yù)測(cè)眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色蘭色灰色CLS算法黃種人[1]混血[6]白種人[2]白種人[4]混血[8]白種人[3]白種人[5]混血[7]黑色金色金色紅色黑色金色紅色黑色第七章分類與預(yù)測(cè)CLS算法1）

生成一顆空決策樹和一張訓(xùn)練樣本屬性集;2）

若訓(xùn)練樣本集T中所有的樣本都屬于同一類，則生成結(jié)點(diǎn)T，并終止學(xué)習(xí)算法；否則3）

根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測(cè)試屬性，

生成測(cè)試結(jié)點(diǎn)A4）

若A的取值為v1,v2,…,vm，

則根據(jù)A的取值的不同，將T劃分成m個(gè)子集T1,T2,…,Tm;5）

從訓(xùn)練樣本屬性表中刪除屬性A;6）

轉(zhuǎn)步驟2,對(duì)每個(gè)子集遞歸調(diào)用CLS。第七章分類與預(yù)測(cè)CLS算法存在的問題在步驟3中，根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測(cè)試屬性，沒有規(guī)定選擇測(cè)試屬性的標(biāo)準(zhǔn)和依據(jù)。實(shí)踐表明，測(cè)試屬性集的組成以及測(cè)試屬性的先后對(duì)決策樹的學(xué)習(xí)具有舉足輕重的影響。舉例：下表為調(diào)查學(xué)生膳食結(jié)構(gòu)和缺鈣情況的關(guān)系，其中1表示包含食物，0表示不包含。第七章分類與預(yù)測(cè)學(xué)生雞肉豬肉牛肉羊肉魚肉雞蛋青菜番茄牛奶健康情況1011010101不缺鈣2000011111不缺鈣3111110100缺鈣4110011001不缺鈣5100111000缺鈣6111001010缺鈣7010001111不缺鈣8010001111缺鈣9010001111不缺鈣10101111011不缺鈣學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表CLS算法存在的問題第七章分類與預(yù)測(cè)采用不同的測(cè)試屬性及其先后順序?qū)?huì)生成不同的決策樹雞肉豬肉豬肉牛肉牛肉牛肉不缺鈣（2）缺鈣（3，6）不缺鈣（4）不缺鈣（10）缺鈣（5）不缺鈣（1）魚肉缺鈣（5）不缺鈣（7，9）是否是否否否否否否是是是是是CLS算法存在的問題第七章分類與預(yù)測(cè)牛奶不缺鈣（1，2，4，7，9，10）缺鈣（3，5，6，8）在上例中，顯然生成的兩種決策樹的復(fù)雜性和分類意義相差很大.由此可見，選擇測(cè)試屬性是決策樹學(xué)習(xí)算法中需要研究的重要課題。CLS算法存在的問題第七章分類與預(yù)測(cè)（2）ID3算法ID3算法主要針對(duì)屬性選擇問題，是決策樹學(xué)習(xí)方法中最具影響和最為典型的算法。ID3使用信息增益度選擇測(cè)試屬性。選擇當(dāng)前所有分割屬性中，信息增益最大的屬性作為測(cè)試屬性，該屬性最能消除不確定性。第七章分類與預(yù)測(cè)64第七章分類與預(yù)測(cè)（2）ID3算法類比：生活工作中的決策（做/不做？）我們總是傾向于選擇最具有決定性意義的輔助條件進(jìn)行判定。如：打不打室外羽毛球？是否刮風(fēng)是最具有決定意義的因素。如何度量信息量的大?。康谄哒路诸惻c預(yù)測(cè)ID3–信息量大小的度量Shannon在1948年提出的信息論理論中，指出事件ai的信息量I(

ai)可如下度量：其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個(gè)互不相容的事件a1,a2,a3,….,an，則其平均的信息量可如下度量：第七章分類與預(yù)測(cè)上式中，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。通常取2，并規(guī)定當(dāng)p(ai)=0時(shí)，=0ID3–信息量大小的度量第七章分類與預(yù)測(cè)ID3-屬性選擇方法設(shè)S為包含s個(gè)數(shù)據(jù)樣本的集合，假定類別屬性C具有m個(gè)不同值Ci(i=1,2,…,m)。設(shè)si是類Ci中的樣本個(gè)數(shù)，則，對(duì)一個(gè)給定數(shù)據(jù)對(duì)象進(jìn)行分類所需要的期望信息可由下式給出：其中，pi是任意樣本屬于類Ci的概率，按照si/S進(jìn)行計(jì)算。Log函數(shù)是以2為底的函數(shù)。（6.1）H(x)=68第七章分類與預(yù)測(cè)（6.2）ID3-屬性選擇方法H(x/y)=69第七章分類與預(yù)測(cè)（6.4）（6.3）ID3-屬性選擇方法I=H(X)-H(X/Y)70第七章分類與預(yù)測(cè)ID3-屬性選擇方法71第七章分類與預(yù)測(cè)Gain(S,A)是屬性A在集合S上的信息增益Gain(S,A)=Entropy(S)

–Entropy(S,A)Gain(S,A)越大，說明選擇測(cè)試屬性對(duì)分類提供的信息越多.ID3–屬性選擇方法第七章分類與預(yù)測(cè)計(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)買ID3算法示例怎么建立決策樹？誰是根節(jié)點(diǎn)？誰是下一層子節(jié)點(diǎn)？為什么是它？第七章分類與預(yù)測(cè)計(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.9537ID3算法示例初始不確定性第七章分類與預(yù)測(cè)計(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ì)算不同屬性的信息增益。ID3算法示例第七章分類與預(yù)測(cè)計(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è)組：

青年、中年、老年1）青年：買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183ID3算法示例第七章分類與預(yù)測(cè)計(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è)組：

青年、中年、老年2）中年：買與不買比例為256/0S1(買)=256S2（不買）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0ID3算法示例第七章分類與預(yù)測(cè)計(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è)組：

青年、中年、老年3）老年：買與不買比例為125/127S1(買)=125S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157ID3算法示例第七章分類與預(yù)測(cè)計(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）ID3算法示例第七章分類與預(yù)測(cè)計(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）ID3算法示例第七章分類與預(yù)測(cè)計(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）ID3算法示例第七章分類與預(yù)測(cè)計(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）ID3算法示例第七章分類與預(yù)測(cè)計(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）ID3算法示例第七章分類與預(yù)測(cè)計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡青年中年老年買/不買買買/不買葉子ID3算法示例第七章分類與預(yù)測(cè)計(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.9183ID3算法示例第七章分類與預(yù)測(cè)計(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.4591高：I(0,128)=0比例:128/384=0.3333中：I(64,128)=0.9183比例:192/384=0.5低：I(64,0)=0比例:64/384=0.1667注意ID3算法示例第七章分類與預(yù)測(cè)計(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)良買不買買/不買買葉子葉子葉子ID3算法示例第七章分類與預(yù)測(cè)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ù)測(cè)ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）電信運(yùn)營(yíng)商的客戶流失有三方面的含義：一是指客戶從一個(gè)電信運(yùn)營(yíng)商轉(zhuǎn)網(wǎng)到其他電信運(yùn)營(yíng)商，這是流失分析的重點(diǎn)；二是指客戶月平均消費(fèi)量降低，從高價(jià)值客戶成為低價(jià)值客戶。三指客戶自然流失和被動(dòng)流失。第七章分類與預(yù)測(cè)ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）在客戶流失分析中有兩個(gè)核心變量：財(cái)務(wù)原因／非財(cái)務(wù)原因、主動(dòng)流失／被動(dòng)流失。客戶流失可以相應(yīng)分為四種類型.其中非財(cái)務(wù)原因主動(dòng)流失的客戶往往是高價(jià)值的客戶。他們會(huì)正常支付服務(wù)費(fèi)用，并容易對(duì)市場(chǎng)活動(dòng)有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。第七章分類與預(yù)測(cè)（1）數(shù)據(jù)預(yù)處理

數(shù)據(jù)挖掘的處理對(duì)象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲(chǔ)在數(shù)據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲(chǔ)在其CRM中），是長(zhǎng)期積累的結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般包括數(shù)據(jù)的選擇(選擇相關(guān)的數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分，對(duì)于挖掘算法的效率乃至正確性都有關(guān)鍵性的影響。ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)（1）數(shù)據(jù)預(yù)處理

該公司經(jīng)過多年的電腦化管理，已有大量的客戶個(gè)人基本信息(文中簡(jiǎn)稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號(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í)例（1）第七章分類與預(yù)測(cè)1）屬性刪除：

將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標(biāo)識(shí)、身份證號(hào)碼等，它們的取值太多且無法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表1。

表1客戶信息表年齡學(xué)歷職業(yè)繳費(fèi)方式在網(wǎng)時(shí)長(zhǎng)費(fèi)用變化率客戶流失58大學(xué)公務(wù)員托收1310%NO47高中工人營(yíng)業(yè)廳繳費(fèi)942%NO26研究生公務(wù)員充值卡263%YES28大學(xué)公務(wù)員營(yíng)業(yè)廳繳費(fèi)52.91%NO32初中工人營(yíng)業(yè)廳繳費(fèi)32.3%NO42高中無業(yè)人員充值卡2100%YES68初中無業(yè)人員營(yíng)業(yè)廳繳費(fèi)92.3%NOID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)2）屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進(jìn)行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(xué)(?？啤⒈究萍耙陨?；職業(yè)類別：按工作性質(zhì)來分共分3類：Z1一Z3；繳費(fèi)方式：托收：T1,營(yíng)業(yè)廳繳費(fèi)：T2,充值卡：T3。ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)2）屬性概化：連續(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í)長(zhǎng)”屬性中，通過檢測(cè)每個(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｝。

ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)表2轉(zhuǎn)化后的客戶信息表年齡學(xué)歷職業(yè)繳費(fèi)方式開戶時(shí)間費(fèi)用變化率客戶流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NOID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)YESNO年齡職業(yè)YES繳費(fèi)方式Y(jié)ESYESNOYSESNONO在網(wǎng)時(shí)長(zhǎng)NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2費(fèi)用變化率

在圖中，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í)間較短的客戶容易流失；年齡較大的客戶，則工人容易流失。ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）第七章分類與預(yù)測(cè)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í)例屬于同一類。第七章分類與預(yù)測(cè)ID3算法小結(jié)優(yōu)點(diǎn)：算法簡(jiǎn)單；易于理解缺點(diǎn)：偏向分割屬性中取值多的一個(gè)；只能處理離散屬性；ID3不包括樹剪枝，易受噪聲和波動(dòng)影響；不易對(duì)變化的數(shù)據(jù)集進(jìn)行學(xué)習(xí)。第七章分類與預(yù)測(cè)（3）C4.5算法ID3缺點(diǎn)1：偏向分割屬性中取值多的一個(gè)原因：分割屬性取值越多，每個(gè)值對(duì)應(yīng)的子集規(guī)模越小。極限情況下，每個(gè)子集內(nèi)只有一個(gè)單元（行），則它的信息增益必然最高（對(duì)不確定的消除達(dá)到最大）。例如，用身份證號(hào)區(qū)別“是否相親成功”，顯然沒有任何意義，但是確實(shí)符合ID3算法。解決方法：引入增益比例第七章分類與預(yù)測(cè)“相親”101第七章分類與預(yù)測(cè)（3）C4.5算法第七章分類與預(yù)測(cè)多取值個(gè)數(shù)非常多的情況？第七章分類與預(yù)測(cè)對(duì)取值個(gè)數(shù)非常少的情況如何？104第七章分類與預(yù)測(cè)G(X,Y)105第七章分類與預(yù)測(cè)C4.5算法如，只有一個(gè)取值的情況排除取值個(gè)數(shù)很多的情況106第七章分類與預(yù)測(cè)107第七章分類與預(yù)測(cè)對(duì)取值按照由小到大的順序排序：108第七章分類與預(yù)測(cè)109第七章分類與預(yù)測(cè)110第七章分類與預(yù)測(cè)111第七章分類與預(yù)測(cè)112第七章分類與預(yù)測(cè)113第七章分類與預(yù)測(cè)114第七章分類與預(yù)測(cè)115第七章分類與預(yù)測(cè)116第七章分類與預(yù)測(cè)117第七章分類與預(yù)測(cè)118第七章分類與預(yù)測(cè)融合119第七章分類與預(yù)測(cè)（4）CART算法CART：ClassificationandRegressionTree分類回歸樹采用基于最小距離的基尼指數(shù)估計(jì)函數(shù)；生成二叉樹。第七章分類與預(yù)測(cè)121第七章分類與預(yù)測(cè)122第七章分類與預(yù)測(cè)123第七章分類與預(yù)測(cè)124第七章分類與預(yù)測(cè)125第七章分類與預(yù)測(cè)126第七章分類與預(yù)測(cè)127第七章分類與預(yù)測(cè)用測(cè)試集128第七章分類與預(yù)測(cè)2.決策樹剪枝？第七章分類與預(yù)測(cè)130第七章分類與預(yù)測(cè)131第七章分類與預(yù)測(cè)132第七章分類與預(yù)測(cè)133第七章分類與預(yù)測(cè)3.提取分類規(guī)則？第七章分類與預(yù)測(cè)由決策樹提取分類規(guī)則決策樹所表示的分類知識(shí)可以被抽取出來，并用IF-THEN的分類規(guī)則的形式表示。

從決策樹的根節(jié)點(diǎn)到任一個(gè)葉節(jié)點(diǎn)所形成的一條路徑構(gòu)成一條分類規(guī)則。

其中，沿著決策樹的一條路徑所形成的屬性-值對(duì)形成分類規(guī)則的前件（IF部分）的一個(gè)合取項(xiàng)；葉節(jié)點(diǎn)所標(biāo)記的類別構(gòu)成規(guī)則的后件（THEN部分）。IF-THEN分類規(guī)則表達(dá)方式易于被人理解，尤其是當(dāng)決策樹較大時(shí)，優(yōu)勢(shì)更加突出。135第七章分類與預(yù)測(cè)示例136第七章分類與預(yù)測(cè)示例137第七章分類與預(yù)測(cè)138第七章分類與預(yù)測(cè)6.4貝葉斯分類方法貝葉斯定理？樸素貝葉斯分類？貝葉斯信念網(wǎng)絡(luò)？第七章分類與預(yù)測(cè)1.貝葉斯定理？第七章分類與預(yù)測(cè)貝葉斯分類方法（Bayes）貝葉斯分類是統(tǒng)計(jì)學(xué)分類方法，可預(yù)測(cè)類別所屬的概率，如：一個(gè)數(shù)據(jù)對(duì)象屬于某個(gè)類別的概率。

貝葉斯分類的基礎(chǔ)是貝葉斯定理。

貝葉斯定理（Bayestheorem）：是概率論中的一個(gè)結(jié)果，跟隨機(jī)變量的條件概率以及邊緣（條件）概率分布有關(guān)。141第七章分類與預(yù)測(cè)在實(shí)際中，人們常會(huì)根據(jù)不確定性信息作出推理和決策，此時(shí)往往需要對(duì)各種結(jié)論出現(xiàn)的概率進(jìn)行估計(jì)，這類推理稱為概率推理。

貝葉斯推理的問題是條件概率推理問題。貝葉斯分類方法（Bayes）142第七章分類與預(yù)測(cè)概率論基本知識(shí)回顧概率論是研究隨機(jī)性或不確定性等現(xiàn)象的數(shù)學(xué)。更精確的說，是用來模擬實(shí)驗(yàn)在同一環(huán)境下會(huì)產(chǎn)生不同結(jié)果的情狀。隨機(jī)事件；事件間的關(guān)系；概率定義；條件概率。143第七章分類與預(yù)測(cè)（1）隨機(jī)事件隨機(jī)實(shí)驗(yàn)：隨機(jī)實(shí)驗(yàn)是一個(gè)可觀察結(jié)果的人工或自然的過程，其產(chǎn)生的結(jié)果可能不止一個(gè)，且不能事先確定會(huì)產(chǎn)生什么結(jié)果。樣本空間：樣本空間是一個(gè)隨機(jī)實(shí)驗(yàn)的全部可能出現(xiàn)的結(jié)果的集合，通常記作Ω，Ω中的點(diǎn)（即一個(gè)可能出現(xiàn)的實(shí)驗(yàn)結(jié)果）稱為樣本點(diǎn)，通常記作ω。隨機(jī)事件：隨機(jī)事件是一個(gè)隨機(jī)實(shí)驗(yàn)的一些可能結(jié)果的集合，是樣本空間的一個(gè)子集。常用大寫字母A,B,C,…表示。144第七章分類與預(yù)測(cè)（2）事件間的關(guān)系145第七章分類與預(yù)測(cè)（3）概率定義定義：設(shè)Ω為一個(gè)隨機(jī)實(shí)驗(yàn)的樣本空間，對(duì)Ω上的任意事件A，規(guī)定一個(gè)實(shí)數(shù)與之對(duì)應(yīng)，記為P(A)，滿足以下三條基本性質(zhì)，稱為事件A發(fā)生的概率：146第七章分類與預(yù)測(cè)（4）條件概率條件概率：設(shè)A、B是兩個(gè)隨機(jī)事件，且P(B)>0,則在事件B已經(jīng)發(fā)生的條件下，事件A發(fā)生的條件概率：聯(lián)合概率：若對(duì)任意兩事件A、B都有P(A)>0，P(B)>0,則：P(AB)=P(A)P(B\A)=P(B)P(A\B)邊際概率：若A1、A2構(gòu)成互斥和完整的兩個(gè)事件，A1和A2

中的一個(gè)出現(xiàn)是事件B發(fā)生的必要條件，則事件B的邊際概率公式為（全概率公式）：P(B)=P(B\A1)P(A1)+P(B\A2)P(A2)147第七章分類與預(yù)測(cè)貝葉斯定理貝葉斯定理是關(guān)于隨機(jī)事件A和B的條件概率和邊緣概率的一則定理。通常，事件A在事件B發(fā)生的條件下的概率，與事件B在事件A發(fā)生的條件下的概率是不一樣的，然而，這兩者是有確定的關(guān)系的，貝葉斯定理就是這種關(guān)系的陳述。148第七章分類與預(yù)測(cè)貝葉斯定理由前面三個(gè)概率公式可以得到貝葉斯公式：全概率：P(B)=P(B\A1)P(A1)+P(B\A2)P(A2)條件概率：聯(lián)合概率：P(AB)=P(A)P(B\A)=P(B)P(A\B)149第七章分類與預(yù)測(cè)貝葉斯定理兩個(gè)事件的貝葉斯公式：若A1、A2構(gòu)成互斥和完整的兩個(gè)事件，A1和A2

中的一個(gè)出現(xiàn)是事件B發(fā)生的必要條件，則兩個(gè)事件的貝葉斯公式：150第七章分類與預(yù)測(cè)貝葉斯定理n個(gè)事件的貝葉斯公式：假定存在一個(gè)互斥和完整的事件A1,A2,…,An，Ai中的某一個(gè)出現(xiàn)是事件B發(fā)生的必要條件，則n個(gè)事件的貝葉斯公式：151第七章分類與預(yù)測(cè)貝葉斯定理在貝葉斯定理中，每個(gè)名詞都有約定俗成的名稱：P(A)：事件A的先驗(yàn)概率或邊緣概率。“先驗(yàn)”指其不考慮任何B方面的因素。P(A\B)：事件A的后驗(yàn)概率，即已知B發(fā)生后A的條件概率。P(B\A)：事件B的后驗(yàn)概率，即已知A發(fā)生后B的條件概率。P(B)：是事件B的先驗(yàn)概率或邊緣概率。152第七章分類與預(yù)測(cè)示例1背景：辦公室新來了一個(gè)雇員小王，小王是好人還是壞人，大家都在猜測(cè)。按人們的主觀意識(shí)，一個(gè)人是好人還是壞人的概率均為0.5，壞人總是要做壞事，好人總是做好事，偶爾也會(huì)做一件壞事。一般好人做好事的概率是0.9，壞人做好事的概率是0.2.一天，小王做了一件好事，則小王是好人的概率有多大，小王究竟為好人還是壞人？第七章分類與預(yù)測(cè)示例1第七章分類與預(yù)測(cè)旅客搭乘飛機(jī)必須經(jīng)電子儀器檢查是否身上攜帶金屬物品。如果攜帶金屬，儀器會(huì)發(fā)出聲音的概率是97%，但身上無金屬物品儀器會(huì)發(fā)出聲音的概率是5%。

已知一般乘客身上帶有金屬物品的概率是30%，若某旅客經(jīng)過儀器檢查時(shí)發(fā)出聲音，請(qǐng)問他身上有金屬物品的概率是多少？

示例2155第七章分類與預(yù)測(cè)解：設(shè)C1=“有金屬物”，X=“儀器會(huì)發(fā)聲”，則156第七章分類與預(yù)測(cè)貝葉斯分類設(shè)X為一個(gè)類別未知的數(shù)據(jù)樣本，設(shè)H為某種假設(shè)，如：數(shù)據(jù)樣本X屬于某特定的類C。對(duì)于分類問題，我們希望確定P(H\X)，即給定觀測(cè)數(shù)據(jù)樣本X，假定H成立的概率。157第七章分類與預(yù)測(cè)貝葉斯分類

設(shè)x∈Ω是一個(gè)類別未知的數(shù)據(jù)樣本，cj為某個(gè)類別，若數(shù)據(jù)樣本x屬于一個(gè)特定的類別cj，那么分類問題就是決定P(cj|x)，即在獲得數(shù)據(jù)樣本x時(shí)，確定x的最佳分類。第七章分類與預(yù)測(cè)

先驗(yàn)概率P(cj)P(cj|x)=P(x|cj)P(cj)P(x)

后驗(yàn)概率P(x|cj)

后驗(yàn)概率P(cj|x)貝葉斯分類第七章分類與預(yù)測(cè)先驗(yàn)概率P(cj)P(cj)為類cj的先驗(yàn)概率(priorprobability)，它反映了我們所擁有的關(guān)于cj是正確分類的背景知識(shí)。通?？梢杂脴永袑儆赾j的樣例數(shù)|cj|比上總樣例數(shù)|D|來近似，即:第七章分類與預(yù)測(cè)

后驗(yàn)概率P(x|cj)指的是當(dāng)已知類別為cj的條件下，樣本x出現(xiàn)的概率。后驗(yàn)概率P(x|cj)若設(shè)x=<a1,a2…am>，且屬性值相互條件獨(dú)立，即在屬性間，不存在依賴關(guān)系，則P(x|cj)=P(a1,a2…am|

cj)第七章分類與預(yù)測(cè)后驗(yàn)概率P(cj|x)

即給定數(shù)據(jù)樣本x時(shí)cj成立的概率，而這正是我們所感興趣的。

P(cj|x

)被稱為C的后驗(yàn)概率（posteriorprobability），因?yàn)樗从沉嗽诘玫綌?shù)據(jù)樣本x后cj成立的置信度.第七章分類與預(yù)測(cè)貝葉斯分類計(jì)算Pmax(ci|x)=maxP(cj|x)j∈(1,|C|)則Pmax(ci|x)稱為最大后驗(yàn)概率，并將x分到ci類中.第七章分類與預(yù)測(cè)2.樸素貝葉斯分類？第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程（1）每個(gè)數(shù)據(jù)樣本X用一個(gè)n維特征向量：X={x1,x2,…,xn}表示，分別描述對(duì)n個(gè)屬性(A1,A2,…,An)的具體取值；（2）假定共有m個(gè)不同類別，C1,C2,…,Cm。給定一個(gè)類別未知的數(shù)據(jù)樣本X，分類法將在已知X情況下，將X賦于后驗(yàn)概率最大的那個(gè)類別。即，樸素貝葉斯分類將類別未知的樣本X歸屬到類別Ci，當(dāng)且僅當(dāng)：即，最大化P(Ci\X)。其中的類別Ci稱為最大后驗(yàn)假定。根據(jù)貝葉斯定理，有：第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程（3）由于P(X)對(duì)于所有的類別均是相同的，因此只需要計(jì)算P(X\Ci)P(Ci)取最大即可。如果各類別的先驗(yàn)概率未知，通常假定這些類是等概率的，即：P(C1)=P(C2)=…=P(Cm)。這樣變成只需要對(duì)P(X\Ci)求最大，否則就要P(X\Ci)P(Ci)取最大。否則，一般可以通過P(Ci)=si/s進(jìn)行估算，其中si為訓(xùn)練樣本集合中類別Ci的個(gè)數(shù)，s為整個(gè)訓(xùn)練樣本集合的大小。第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程（4）對(duì)于包含多個(gè)屬性的數(shù)據(jù)集，直接計(jì)算P(X\Ci)的運(yùn)算量是非常大的。為實(shí)現(xiàn)對(duì)P(X\Ci)的有效估算，樸素貝葉斯分類通常假設(shè)各屬性是相互獨(dú)立的，即在屬性間，不存在依賴關(guān)系，則對(duì)于給定的類別Ci，有：而P(x1\Ci),P(x2\Ci),…,P(xn\Ci)的值，可以由訓(xùn)練樣本集進(jìn)行估算。具體處理如下：第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程1）如果Ak是符號(hào)屬性，則P(xk\Ci)=sik/si，：其中sik為訓(xùn)練樣本中類別為Ci且屬性Ak取值vk的樣本數(shù)，si為訓(xùn)練樣本中類別為Ci的樣本數(shù)。第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程第七章分類與預(yù)測(cè)樸素貝葉斯分類的工作過程（5）為預(yù)測(cè)一個(gè)未知樣本X的類別，對(duì)每個(gè)類Ci，計(jì)算P(X\Ci)P(Ci)。則，樣本X被指派到類Ci，當(dāng)且僅當(dāng)：P(X\Ci)P(Ci)>P(X\Cj)P(Cj),第七章分類與預(yù)測(cè)樸素貝葉斯分類的效果研究表明，與決策樹和神經(jīng)網(wǎng)絡(luò)分類器相比，貝葉斯分類器在某些情況下具有更好的分類效果。但必須滿足某些假定條件，如要求各屬性間是相互獨(dú)立的。第七章分類與預(yù)測(cè)示例172第七章分類與預(yù)測(cè)示例背景：

給定與決策樹歸納相同的訓(xùn)練數(shù)據(jù)集，希望使用樸素貝葉斯分類預(yù)測(cè)未知樣本的類標(biāo)號(hào)?；拘畔ⅲ?）數(shù)據(jù)樣本用age,income,student,credit-rating描述。類標(biāo)號(hào)屬性buys_computer具有兩個(gè)不同取值{yes,no}。2）設(shè)C1對(duì)應(yīng)類“yes”，