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

1、數(shù)據(jù)挖掘數(shù)據(jù)挖掘2u概念描述：特征化和比較；u 關(guān)聯(lián)規(guī)則；u 分類分類/預(yù)測(cè)；預(yù)測(cè)；u 聚類分析；u其他的數(shù)據(jù)挖掘任務(wù)。引引 言言根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥(niǎo)類的信息，根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥(niǎo)類的信息，我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物A，動(dòng)物，動(dòng)物B進(jìn)行分類？進(jìn)行分類？動(dòng)物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動(dòng)物豬大04否是爬行動(dòng)物牛大04否是爬行動(dòng)物麻雀小22是是鳥(niǎo)類天鵝中22是是鳥(niǎo)類大雁中22是是鳥(niǎo)類動(dòng)物A大02是無(wú)？動(dòng)物B中22否是？2022年3月30日星期三4分類是數(shù)據(jù)挖掘中重要的任務(wù)分類是

2、數(shù)據(jù)挖掘中重要的任務(wù) v分類的目的是學(xué)會(huì)一個(gè)分類器（分類函數(shù)或模型），該分類器能把待分類的數(shù)據(jù)映射到給定的類別中。v分類可用于預(yù)測(cè)。從歷史數(shù)據(jù)紀(jì)錄中自動(dòng)推導(dǎo)出對(duì)給定數(shù)據(jù)的推廣描述，從而能對(duì)未來(lái)數(shù)據(jù)進(jìn)行類預(yù)測(cè)。iiniiiyxxxxf),.,(3212022年3月30日星期三5分類方法的類型分類方法的類型v 從使用的主要技術(shù)上看，可以把分類方法歸結(jié)為以下幾種類型：基于距離的分類方法基于距離的分類方法決策樹(shù)分類方法決策樹(shù)分類方法貝葉斯分類方法貝葉斯分類方法。v 本章主要圍繞這幾種分類方法展開(kāi)。6 6.1 .1 分類與預(yù)測(cè)的基本知識(shí)分類與預(yù)測(cè)的基本知識(shí)6 6.2 .2 基于距離的分類算法基于距離的分

3、類算法6.3 6.3 決策樹(shù)分類方法決策樹(shù)分類方法6.4 6.4 貝葉斯分類方法貝葉斯分類方法6.5 6.5 規(guī)則歸納方法規(guī)則歸納方法* *6.1 6.1 分類和預(yù)測(cè)的基本知識(shí)分類和預(yù)測(cè)的基本知識(shí)l什么是分類？預(yù)測(cè)？什么是分類？預(yù)測(cè)？l分類和預(yù)測(cè)的基本問(wèn)題分類和預(yù)測(cè)的基本問(wèn)題1. 1. 分類？預(yù)測(cè)？分類？預(yù)測(cè)？10基本概念基本概念 u 分類和預(yù)測(cè)是兩種數(shù)據(jù)分析的形式，可用于提取描述重要數(shù)據(jù)類的模型或預(yù)測(cè)未來(lái)的數(shù)據(jù)趨勢(shì)：分類（分類（classification）：用于預(yù)測(cè)數(shù)據(jù)對(duì)象的分類標(biāo)號(hào)分類標(biāo)號(hào)（或離散離散值），如，通過(guò)構(gòu)造分類模型對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估（安全或危險(xiǎn)）；預(yù)測(cè)（預(yù)測(cè)（predic

4、ation）：用于預(yù)測(cè)數(shù)據(jù)對(duì)象的連續(xù)取值連續(xù)取值，如，建立預(yù)測(cè)模型利用顧客收入與職業(yè)（參數(shù)）預(yù)測(cè)其可能用于購(gòu)買計(jì)算機(jī)設(shè)備的支出大小。11數(shù)據(jù)分類過(guò)程數(shù)據(jù)分類過(guò)程數(shù)據(jù)分類是一個(gè)兩步的過(guò)程：1 1）建立分類模型）建立分類模型：機(jī)器學(xué)習(xí)過(guò)程，通過(guò)某種分類算法對(duì)訓(xùn)練集進(jìn)行訓(xùn)練，得到分類模型；“有指導(dǎo)的學(xué)習(xí)有指導(dǎo)的學(xué)習(xí)”、“有監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)” 假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)稱為類標(biāo)號(hào)屬性類標(biāo)號(hào)屬性的屬性確定； 訓(xùn)練數(shù)據(jù)集：為建立分類模型而被分析的數(shù)據(jù)元組。12分類過(guò)程的第一步：學(xué)習(xí)建模分類過(guò)程的第一步：學(xué)習(xí)建模13數(shù)據(jù)分類過(guò)程數(shù)據(jù)分類過(guò)程數(shù)據(jù)分類是一個(gè)兩步的過(guò)程：2 2）使用模型進(jìn)行分類

5、）使用模型進(jìn)行分類： 測(cè)試數(shù)據(jù)集：用于評(píng)估模型的預(yù)測(cè)準(zhǔn)確率。模型在測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本所占的百分比。 如認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它來(lái)對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。14分類過(guò)程的第二步：分類測(cè)試分類過(guò)程的第二步：分類測(cè)試15分類過(guò)程示意圖分類過(guò)程示意圖有指導(dǎo)的有指導(dǎo)的學(xué)習(xí)學(xué)習(xí) VS. 無(wú)指導(dǎo)的學(xué)習(xí)無(wú)指導(dǎo)的學(xué)習(xí)u有指導(dǎo)有指導(dǎo)的學(xué)習(xí)（用于分類）訓(xùn)練樣本的類標(biāo)號(hào)已知；新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類u無(wú)指導(dǎo)無(wú)指導(dǎo)的學(xué)習(xí)（用于聚類）訓(xùn)練樣本的類標(biāo)號(hào)未知；通過(guò)一系列的度量、觀察，試圖確立數(shù)據(jù)中的類或聚類的存在17數(shù)據(jù)預(yù)測(cè)數(shù)據(jù)預(yù)測(cè)u預(yù)測(cè)：預(yù)測(cè)：構(gòu)造和使用模型評(píng)

6、估無(wú)標(biāo)號(hào)樣本類 ，或評(píng)估給定樣本可能具有的屬性值或值區(qū)間u與分類區(qū)別：與分類區(qū)別：二者是兩類主要的預(yù)測(cè)問(wèn)題。 分類是預(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è)。18示例示例背景：背景： 假定已建立AllElectronics公司的郵寄清單數(shù)據(jù)庫(kù)。郵寄清單用于分發(fā)介紹新產(chǎn)品和降價(jià)信息材料。數(shù)據(jù)庫(kù)描述顧客的屬性，包括姓名、年齡、收入、職業(yè)和信譽(yù)度，并按照顧客是否在該公司購(gòu)買計(jì)算機(jī)進(jìn)行分類。19示例示例分類模型：分類模型： 假定新的顧客添加到數(shù)據(jù)庫(kù)中，由于向每位顧客分發(fā)促銷材料費(fèi)用很高，因此，可以根據(jù)數(shù)據(jù)庫(kù)中已有顧客信息構(gòu)建分

7、類模型，用以預(yù)測(cè)需向哪些顧客分發(fā)材料。預(yù)測(cè)模型：預(yù)測(cè)模型： 假定想預(yù)測(cè)在一個(gè)財(cái)政年度，一個(gè)顧客將在AllElectronics進(jìn)行的主要的購(gòu)買的數(shù)量，則可以構(gòu)建一個(gè)預(yù)測(cè)模型。2. 2. 分類和預(yù)測(cè)的基本問(wèn)題？分類和預(yù)測(cè)的基本問(wèn)題？21問(wèn)題問(wèn)題(1)(1)：數(shù)據(jù)準(zhǔn)備：數(shù)據(jù)準(zhǔn)備 1）準(zhǔn)備分類和預(yù)測(cè)的數(shù)據(jù)）準(zhǔn)備分類和預(yù)測(cè)的數(shù)據(jù)：數(shù)據(jù)的預(yù)處理v 數(shù)據(jù)清理數(shù)據(jù)清理：噪聲（平滑技術(shù)）；空缺值（統(tǒng)計(jì)手段）v 相關(guān)性分析相關(guān)性分析（特征選擇）：刪除不相關(guān)和冗余屬性，如銀行貸款申請(qǐng)時(shí)填寫(xiě)的星期數(shù)，可能與貸款是否申請(qǐng)成功無(wú)關(guān)；v 數(shù)據(jù)變換數(shù)據(jù)變換： 數(shù)據(jù)離散化（數(shù)據(jù)概化）：如屬性“收入”的數(shù)值就可以被離散化為若干

8、區(qū)間，如低、中等和高； 數(shù)據(jù)規(guī)范化：將給定屬性的值按比例縮放至較小的區(qū)間，如0,1。22問(wèn)題問(wèn)題(2)(2)：評(píng)估分類模型：評(píng)估分類模型 2）評(píng)估方法：）評(píng)估方法：對(duì)用于分類或預(yù)測(cè)的方法或模型進(jìn)行評(píng)估v 預(yù)測(cè)的準(zhǔn)確率：模型正確預(yù)測(cè)未知對(duì)象類別或數(shù)值的能力；v 速度：1）建立模型的時(shí)間；2）使用模型的時(shí)間v 強(qiáng)壯性（魯棒性）：處理噪聲和空缺值的能力；v 可伸縮（擴(kuò)展）性：處理大型數(shù)據(jù)及構(gòu)造模型的能力；v 可理解性：模型的可理解能力；v 規(guī)則的優(yōu)越性：1）判定樹(shù)的大小；2）分類規(guī)則的簡(jiǎn)潔性。6.2 6.2 基于距離的分類算法基于距離的分類算法l 基本思想？基本思想？l 幾種常見(jiàn)的距離分類算法？幾種

9、常見(jiàn)的距離分類算法？1. 1. 基于距離分類的基本思想？基于距離分類的基本思想？2022年3月30日星期三25基于距離的分類算法的思路基于距離的分類算法的思路q 定義：給定一個(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è)分類問(wèn)題是要分配每個(gè)ti到滿足如下條件的類到滿足如下條件的類Cj： sim(ti，Cj)=sim(ti，Ci) ，CiC，CiCj，其中sim(ti，Cj)被稱為相似性。2022年3月30日星期三26基于距離的分類算法的思路基于

10、距離的分類算法的思路q在實(shí)際的計(jì)算中往往用距離來(lái)表征： 距離越近，相似性越大；距離越近，相似性越大； 距離越遠(yuǎn)，相似性越小。距離越遠(yuǎn)，相似性越小。q如何度量距離？ 歐幾里得距離；歐幾里得距離； 曼哈坦距離；曼哈坦距離； 明考斯基距離；明考斯基距離； 加權(quán)的明考斯基距離。加權(quán)的明考斯基距離。（一）歐幾里得距離（一）歐幾里得距離歐式距離由對(duì)應(yīng)元素間差值平方和的平方根所表示，即：歐式距離由對(duì)應(yīng)元素間差值平方和的平方根所表示，即：)()()(),(),(),(2222112121bnanbababnbbbanaaaxxxxxxbadxxxxxxxxnba維向量，兩個(gè)和設(shè)有如何度量距離？如何度量距離？（

11、二）曼哈頓距離（二）曼哈頓距離對(duì)應(yīng)元素間差值絕對(duì)值的和表示，即：對(duì)應(yīng)元素間差值絕對(duì)值的和表示，即：bnanbabaxxxxxxbad2211),(歐幾里得距離與曼哈頓距離的共同點(diǎn)：歐幾里得距離與曼哈頓距離的共同點(diǎn)：(1)(1)即距離是一個(gè)非負(fù)的數(shù)值即距離是一個(gè)非負(fù)的數(shù)值 (2)(2)自身的距離為自身的距離為0 (3)(3)即距離函數(shù)具有對(duì)稱性即距離函數(shù)具有對(duì)稱性 (4)(4)即距離函數(shù)滿足三角不等式即距離函數(shù)滿足三角不等式 0),(bad0),(, 0),(bbdaad),(),(abdbad),(),(),(kbdkadbad如何度量距離？如何度量距離？( (三三) )明可夫斯基距離明可夫斯

12、基距離是歐幾里得距離和曼哈頓距離的概化是歐幾里得距離和曼哈頓距離的概化ppbnanpbapbaxxxxxxbad/12211),(其中p是一個(gè)正整數(shù)：當(dāng)p=1時(shí)，表示曼哈頓距離；當(dāng)p=2時(shí)，表示歐幾里得距離。 ( (四四) )加權(quán)的明可夫斯基距離加權(quán)的明可夫斯基距離如果對(duì)每一個(gè)變量根據(jù)其重要性賦予一個(gè)權(quán)重，就得到加權(quán)的明考斯基如果對(duì)每一個(gè)變量根據(jù)其重要性賦予一個(gè)權(quán)重，就得到加權(quán)的明考斯基距離。距離。ppbnannpbapbaxxwxxwxxwbad/ 1222111),(如何度量距離？如何度量距離？2022年3月30日星期三30基于距離的分類算法的思路基于距離的分類算法的思路q在實(shí)際的計(jì)算中往

13、往用距離來(lái)表征： 距離越近，相似性越大；距離越近，相似性越大； 距離越遠(yuǎn)，相似性越小。距離越遠(yuǎn)，相似性越小。q距離的計(jì)算方法有多種，最常用的是通過(guò)計(jì)算樣本到每個(gè)類中心的距離來(lái)完成。2022年3月30日星期三31 基于距離的分類算法的一般性描述基于距離的分類算法的一般性描述q算法計(jì)算每個(gè)元組到各個(gè)類中心的距離類中心的距離，從而可以找出離它的最近的類中心，得到確定的類別標(biāo)記。算法 基于距離的分類算法輸入：每個(gè)類的中心C1，Cm；待分類的元組t。 輸出：輸出類別c。 （1）dist=；/距離初始化（2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN（

14、4）c i； （5）distdist(ci，t)； （6） END.2022年3月30日星期三32基于距離的分類方法的直觀解釋基于距離的分類方法的直觀解釋（a）類定義）類定義（b）待分類樣例）待分類樣例（c）分類結(jié)果）分類結(jié)果33距離分類例題距離分類例題 例：例：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)34距離分類例題距離分類例題 歐幾里得距離：歐幾里得距離：d(A,C1)=(3-5)2+(3-5)2+(4-0)2+(

15、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 2 幾種常見(jiàn)的距離分類算法？幾種常見(jiàn)的距離分類算法？36幾種常見(jiàn)的距離分類算法幾種常見(jiàn)的距離分類算法 u （1）k-近鄰算法近鄰算法；u （2）K-means算法（聚類）；算法（聚類）；u （3）K-mediods算法（聚類）。算法（聚類）。2022年3月30日星期三37（1）K-近鄰分類算法近鄰分類算法qK-近鄰分類算法（K Nearest Neighb

16、ors，簡(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è)類別。2022年3月30日星期三38（1）K-近鄰分類算法近鄰分類算法算法算法 4-2 K-近鄰分類算法近鄰分類算法輸入：輸入： 訓(xùn)練數(shù)據(jù)訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目；近鄰數(shù)目K；待分類的元組；待分類的元組t。 輸出：輸出： 輸出類別輸出類別c。 （1）N= ；（2）FOR each d T DO BEGIN（3） IF |N|K THEN（4） N=Nd； （5） ELSE（6） IF u N such that sim(t，u)sim(t，d)

17、 THEN BEGIN （7） N=N-u；（8） N=Nd；（9） END（10）END（11）c=class to which the most uN. KNN的直觀解釋的直觀解釋1、定義的直觀形式：、定義的直觀形式：v 找出與目標(biāo)最接近的K個(gè)樣本；v 將目標(biāo)劃分到找出的K個(gè)樣本中出現(xiàn)最頻繁的類。2、K的直觀形式：的直觀形式：v 以目標(biāo)樣本為中心；v 劃出一個(gè)剛好包含K個(gè)樣本的圓；v 當(dāng)K增大時(shí)，圓半徑增大。KNN的直觀解釋的直觀解釋3、直觀的例子、直觀的例子v手寫(xiě)識(shí)別手寫(xiě)識(shí)別 記錄手寫(xiě)體特征； 計(jì)算手寫(xiě)體與標(biāo)準(zhǔn)漢字的相似度； 根據(jù)相似度（距離），找出K個(gè)備選集； 選擇一個(gè)正確漢字v人種識(shí)

18、別人種識(shí)別 歐洲人的鼻子、亞洲人的眼睛 非洲人的膚色、亞洲人的頭發(fā)KNN的分類思想的分類思想如果它走路像鴨子如果它走路像鴨子, 叫聲也像鴨子叫聲也像鴨子, 那么那么它它可能就是只鴨子可能就是只鴨子Training RecordsTest RecordCompute DistanceChoose k of the “nearest” recordsKNN的特點(diǎn)的特點(diǎn)1、非參數(shù)統(tǒng)計(jì)方法v 不需引入?yún)?shù)v 回歸分析是參數(shù)統(tǒng)計(jì)方法2、k的選擇v K=1時(shí)，將待分類樣本劃入與其最接近的樣本的類；v K=|X|時(shí)，僅根據(jù)訓(xùn)練樣本進(jìn)行頻率統(tǒng)計(jì)，將待分類樣本劃入最多的類；v K需要合理選擇，太小容易受干擾、太

19、大增加計(jì)算復(fù)雜性3、算法的復(fù)雜度v 維數(shù)災(zāi)難：當(dāng)維數(shù)增加時(shí)，算法的復(fù)雜度會(huì)急劇增加v 一般采用降維處理6.3 6.3 決策樹(shù)分類算法決策樹(shù)分類算法l 決策樹(shù)的基本概念？決策樹(shù)的基本概念？l 決策樹(shù)生成算法？決策樹(shù)生成算法？l 剪枝方法？剪枝方法？l 提取分類規(guī)則？提取分類規(guī)則？1. 1. 決策樹(shù)的基本概念？決策樹(shù)的基本概念？決策樹(shù)基本概念決策樹(shù)基本概念解決分類問(wèn)題的一般方法解決分類問(wèn)題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學(xué)習(xí)算法學(xué)習(xí)算法學(xué)習(xí)模型學(xué)習(xí)模型模型模型應(yīng)用模型應(yīng)用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N41

20、5M？訓(xùn)練集（類標(biāo)號(hào)已知）訓(xùn)練集（類標(biāo)號(hào)已知）檢驗(yàn)集（類標(biāo)號(hào)未知）檢驗(yàn)集（類標(biāo)號(hào)未知）歸納歸納推論推論46基本概念基本概念 u 決策樹(shù)（decision tree）： 決策樹(shù)是一種典型的分類方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹(shù)，然后使用決策樹(shù)對(duì)新數(shù)據(jù)進(jìn)行分析。 本質(zhì)上決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買47決策樹(shù)的基本組成決策樹(shù)的基本組成u 決策樹(shù)的基本組成決策樹(shù)是類似流程圖的倒立的樹(shù)型結(jié)構(gòu)。最頂層節(jié)點(diǎn)為根節(jié)點(diǎn)根節(jié)點(diǎn)，是整個(gè)決策樹(shù)的開(kāi)始；樹(shù)的每個(gè)內(nèi)部節(jié)點(diǎn)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，其每個(gè)分支代表一個(gè)測(cè)試輸出；樹(shù)的

21、每個(gè)葉節(jié)點(diǎn)葉節(jié)點(diǎn)代表一個(gè)類別。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買48基本概念基本概念 u決策樹(shù)的生成包括兩個(gè)過(guò)程：（1）樹(shù)的建立首先所有訓(xùn)練樣本都在根節(jié)點(diǎn)；依據(jù)所選的屬性循環(huán)地劃分樣本。（2） 樹(shù)剪枝（tree pruning）：在決策樹(shù)構(gòu)造時(shí)，許多分支可能反映的是訓(xùn)練數(shù)據(jù)中的噪聲或孤立點(diǎn)。樹(shù)剪枝就是識(shí)別并消除這類分支，以提高在未知數(shù)據(jù)上分類的準(zhǔn)確性。492. 2. 決策樹(shù)的生成算法？決策樹(shù)的生成算法？51決策樹(shù)的生成算法決策樹(shù)的生成算法u基本的決策樹(shù)生成算法是一個(gè)貪心算法，采用自上而下、分而自上而下、分而治之治之的遞歸方式來(lái)構(gòu)造。u決策樹(shù)上的各個(gè)分支是在對(duì)數(shù)據(jù)不斷分組的過(guò)程中逐漸

22、生長(zhǎng)出來(lái)的。 首先，選擇一個(gè)屬性作為根節(jié)點(diǎn)，然后把該屬性的每一個(gè)可能的值作為子節(jié)點(diǎn)，這樣就把整個(gè)訓(xùn)練集分成了幾個(gè)子集，根節(jié)點(diǎn)屬性的每個(gè)取值都對(duì)應(yīng)著一個(gè)子集，然后遞歸應(yīng)用到每個(gè)子樹(shù)上進(jìn)行進(jìn)一步劃分，直到對(duì)所有數(shù)據(jù)的繼續(xù)分組不再有意義時(shí)，決策樹(shù)的生長(zhǎng)過(guò)程宣告結(jié)束，此時(shí)便生成了一棵完整的決策樹(shù)。其中，測(cè)試屬性的選擇測(cè)試屬性的選擇是構(gòu)建決策樹(shù)的關(guān)鍵環(huán)節(jié)，不同的決策樹(shù)算法在此使用的技術(shù)都不盡相同。52決策樹(shù)的生成算法決策樹(shù)的生成算法注意：注意：u在決策樹(shù)算法中，所有屬性均為符號(hào)值，即離散值，因此若有取連續(xù)值的屬性，必須首先進(jìn)行離散化離散化。53決策樹(shù)的生成算法決策樹(shù)的生成算法常見(jiàn)的有如下幾種決策樹(shù)生成算

23、法：u CLS;u ID3;u C4.5;u CART。（1）CLS（Concept Learning System）算法）算法 CLS算法是早期的決策樹(shù)學(xué)習(xí)算法。它是許多決策樹(shù)學(xué)習(xí)算法的基礎(chǔ)。 CLS基本思想基本思想 從一棵空決策樹(shù)開(kāi)始，選擇某一屬性（分類屬性）作為測(cè)試屬性。該測(cè)試屬性對(duì)應(yīng)決策樹(shù)中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng)于決策樹(shù)的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對(duì)該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色

24、金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血CLS算法算法人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血CLS算法算法-決策樹(shù)的構(gòu)建決策樹(shù)的構(gòu)建眼睛顏色眼睛顏色1,62,4,83,5,7黑色黑色藍(lán)色藍(lán)色灰色灰色不屬于同一類，非葉結(jié)點(diǎn)不屬于同一類，非葉結(jié)點(diǎn)眼睛顏色眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色黑色蘭色蘭色灰色灰色CLS算法算法黃種人黃種人1 混血混血6白種人白種人2 白種人白種人4 混血混血8 白種人白種人3

25、 白種人白種人5混血混血7黑色黑色金色金色金色金色紅色紅色黑色黑色金色金色紅色紅色黑色黑色CLS算法算法1） 生成一顆空決策樹(shù)和一張訓(xùn)練樣本屬性集;2） 若訓(xùn)練樣本集T 中所有的樣本都屬于同一類，則生成結(jié)點(diǎn)T ，并終止學(xué)習(xí)算法；否則3） 根據(jù)某種策略某種策略從訓(xùn)練樣本屬性表中選擇屬性A 作為測(cè)試屬性， 生成測(cè)試結(jié)點(diǎn)A 4） 若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。CLS算法存在的問(wèn)題算法存在的問(wèn)題q 在步驟3中，根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測(cè)試

26、屬性，沒(méi)有規(guī)定選擇測(cè)試屬性的標(biāo)準(zhǔn)和依據(jù)。q 實(shí)踐表明，測(cè)試屬性集的組成以及測(cè)試屬性的先后對(duì)決策樹(shù)的學(xué)習(xí)具有舉足輕重的影響。舉例：舉例：下表為調(diào)查學(xué)生膳食結(jié)構(gòu)和缺鈣情況的關(guān)系，其中1表示包含食物，0表示不包含。學(xué)生雞肉豬肉牛肉羊肉魚(yú)肉雞蛋青菜番茄牛奶健康情況1011010101不缺鈣2000011111不缺鈣3111110100缺鈣4110011001不缺鈣5100111000缺鈣6111001010缺鈣7010001111不缺鈣8010001111缺鈣9010001111不缺鈣10101111011不缺鈣學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表CLS算法存在的問(wèn)題算法存在的問(wèn)題采用不同

27、的測(cè)試屬性及其先后順序?qū)?huì)生成不同的決策樹(shù)采用不同的測(cè)試屬性及其先后順序?qū)?huì)生成不同的決策樹(shù)雞肉雞肉豬肉豬肉豬肉豬肉牛肉牛肉牛肉牛肉牛肉牛肉不缺鈣（不缺鈣（2）缺鈣（缺鈣（3，6） 不缺鈣（不缺鈣（4） 不缺鈣（不缺鈣（10）缺鈣（缺鈣（5）不缺鈣（不缺鈣（1）魚(yú)肉魚(yú)肉缺鈣（缺鈣（5）不缺鈣（不缺鈣（7，9）是是否否是是否否否否否否否否否否否否是是是是是是是是是是CLS算法存在的問(wèn)題算法存在的問(wèn)題牛奶牛奶不缺鈣不缺鈣（1，2，4，7，9，10）缺鈣缺鈣（3，5，6，8）v 在上例中，顯然生成的兩種決策樹(shù)的復(fù)雜性和分類意義相差很大.v 由此可見(jiàn)，選擇測(cè)試屬性是決策樹(shù)學(xué)習(xí)算法中需要研究的重要課題。

28、CLS算法存在的問(wèn)題算法存在的問(wèn)題（2）ID3算法算法q ID3算法主要針對(duì)屬性選擇問(wèn)題，是決策樹(shù)學(xué)習(xí)方法中最具影響和最為典型的算法。q ID3使用信息增益度選擇測(cè)試屬性。使用信息增益度選擇測(cè)試屬性。q 選擇當(dāng)前所有分割屬性中，信息增益最大的屬性作為測(cè)試屬性，該屬性最能消除不確定性。64（2）ID3算法算法類比：生活工作中的決策（做/不做？）q 我們總是傾向于選擇最具有決定性意義的輔助條件進(jìn)行判定。q 如：打不打室外羽毛球？q 是否刮風(fēng)是最具有決定意義的因素。q 如何度量信息量度量信息量的大?。縄D3 信息量大小的度量信息量大小的度量 Shannon在1948年提出的信息論理論中，指出事件ai

29、的信息量I( ai )可如下度量：其中p(ai)表示事件ai發(fā)生的概率。 假設(shè)有n個(gè)互不相容的事件a1,a2,a3,.,an，則其平均的信息量可如下度量：niiiniinapapaIaaaI12121)(1log)()(),.,()(1log)()(2iiiapapaIniiiniinapapaIaaaI12121)(1log)()(),.,( 上式中，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。 通常取2，并規(guī)定當(dāng)p(ai)=0時(shí)， =0)(1log)()(2iiiapapaIID3 信息量大小的度量信息量大小的度量68ID3-屬性選擇方法屬性選擇方法 設(shè)S為包含s個(gè)數(shù)據(jù)樣本的集合，

30、假定類別屬性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)=69（6.2）ID3-屬性選擇方法屬性選擇方法H(x/y)=70（6.4）（6.3）ID3-屬性選擇方法屬性選擇方法I=H(X)-H(X/Y)71ID3-屬性選擇方法屬性選擇方法v Gain(S, A)是屬性A在集合S上的信息增益v Gain(S, A)= Entropy(S) Entropy(S, A)v Gain(S, A)越大，說(shuō)明選擇測(cè)試

31、屬性對(duì)分類提供的信息越多.ID3 屬性選擇方法屬性選擇方法計(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算法示例算法示例v 怎么建立決策樹(shù)？怎么建立決策樹(shù)？v 誰(shuí)是根節(jié)點(diǎn)？誰(shuí)是根節(jié)點(diǎn)？v 誰(shuí)是下一層子節(jié)點(diǎn)？誰(shuí)是下一層子節(jié)點(diǎn)？為什么是它？為什么是它？計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買6

32、4中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第1步計(jì)算決策屬性的熵步計(jì)算決策屬性的熵決策屬性決策屬性“買計(jì)算機(jī)？買計(jì)算機(jī)？”該屬性分兩類：買/不買S1(買)=641 S2（不買）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537ID3算法示例算法示例初始不初始不確定性確定性計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青

33、高否良不買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ì)算條件屬性的熵步計(jì)算條件屬性的熵條件屬性條件屬性共有4個(gè)： 分別是年齡、收入、學(xué)生、信譽(yù)。 分別計(jì)算不同屬性的信息增益。ID3算法示例算法示例計(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中高是

34、良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-1步步 計(jì)算年齡的熵計(jì)算年齡的熵年齡年齡共分三個(gè)組： 青年、中年、老年1）青年：）青年：買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買13

35、2老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-2步步 計(jì)算年齡的熵計(jì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年2）中年：）中年：買與不買比例為256/0S1(買)=256 S2（不買）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不

36、買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-3步計(jì)算年齡的熵步計(jì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年3）老年：）老年：買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64

37、老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-4步步 計(jì)算年齡的熵計(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算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)

38、？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ì)算計(jì)算收入收入的熵的熵收入共分三個(gè)組： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 （2）ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中

39、是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第4步步 計(jì)算計(jì)算學(xué)生學(xué)生的熵的熵學(xué)生共分二個(gè)組： 學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811 =0.1726 （3）ID3算法示例算法示例計(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ì)算計(jì)算信譽(yù)信譽(yù)的熵的熵信譽(yù)分二個(gè)組： 良好，優(yōu)秀E（信譽(yù)）= 0.9048信譽(yù)信息增

40、益=0.9537-0.9048 =0.0453 （4）ID3算法示例算法示例計(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)步計(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

41、.9048 =0.0453 （4）ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡年齡青年中年老年買/不買買買/不買葉子ID3算法示例算法示例計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買比例為128/256S1(買)=128 S2（不買）= 256S= S1 + S2 =384P1=128/384P2=256/384I(S1, S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P

42、2Log2P2) =0.9183ID3算法示例算法示例計(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

43、,0)=0比例: 64/384=0.1667 注意ID3算法示例算法示例計(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中高是良買年齡年齡青年中年老年學(xué)生買信譽(yù)葉子否否是是優(yōu)優(yōu)良良買不買買/不買買葉子葉子葉子ID3算法示例算法示例ID3算法實(shí)際應(yīng)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1） 通過(guò)ID3算法來(lái)實(shí)現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的特征，以幫助電信公司有針對(duì)性地改善客戶關(guān)系，避免客戶流失. 利用

44、決策樹(shù)方法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)數(shù)據(jù)預(yù)處理、決策樹(shù)挖掘處理、決策樹(shù)挖掘操作，模式評(píng)估和應(yīng)用。 ID3算法實(shí)際應(yīng)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）v電信運(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)流失。ID3算法實(shí)際應(yīng)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）v 在客戶流失分析中有兩個(gè)核心變量：財(cái)務(wù)原因非財(cái)務(wù)原因、主動(dòng)流失被動(dòng)流失。v 客戶流失可以相應(yīng)分為四種類型.v 其中非財(cái)務(wù)原因主動(dòng)流失非財(cái)務(wù)原因

45、主動(dòng)流失的客戶往往是高價(jià)值的客戶。他們會(huì)正常支付服務(wù)費(fèi)用，并容易對(duì)市場(chǎng)活動(dòng)有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。 （1）數(shù)據(jù)預(yù)處理）數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘的處理對(duì)象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲(chǔ)在數(shù)據(jù)庫(kù)系統(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)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）（1）數(shù)據(jù)預(yù)處理）數(shù)據(jù)預(yù)處理 該公司經(jīng)過(guò)多年的電腦化管理，已

46、有大量的客戶個(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)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）1）屬性刪除：）屬性刪除： 將有大量不同取值且無(wú)概化操作符的屬性或者可用其它屬性來(lái)代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標(biāo)識(shí)、身份證號(hào)碼等，它們的取值太多且無(wú)法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表

47、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高中無(wú)業(yè)人員充值卡2100%YES68初中無(wú)業(yè)人員營(yíng)業(yè)廳繳費(fèi)92.3%NOID3算法實(shí)際應(yīng)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）2）屬性概化：）屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進(jìn)行概化。 文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(xué)(?？啤⒈究萍耙陨?； 職業(yè)類別：按工作性質(zhì)來(lái)

48、分共分3類：Z1一Z3； 繳費(fèi)方式：托收：T1,營(yíng)業(yè)廳繳費(fèi)：T2,充值卡：T3。ID3算法實(shí)際應(yīng)用算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（在電信行業(yè)應(yīng)用實(shí)例（1）2）屬性概化：）屬性概化： 連續(xù)型屬性概化為區(qū)間值。表中年齡、費(fèi)用變化率和在網(wǎng)時(shí)間為連續(xù)型數(shù)據(jù)，由于建立決策樹(shù)時(shí)，用離散型數(shù)據(jù)進(jìn)行處理速度最快，因此對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化處理. 根據(jù)專家經(jīng)驗(yàn)和實(shí)際計(jì)算信息增益，在“在網(wǎng)時(shí)長(zhǎng)”屬性中，通過(guò)檢測(cè)每個(gè)劃分，得到在閾值為5年時(shí)信息增益最大，從而確定最好的劃分是在5年處，則這個(gè)屬性的范圍就變?yōu)?：H1,H2。 而在“年齡”屬性中，信息增益有兩個(gè)鋒值，分別在40和50處，因而該屬性的范圍變?yōu)?0-50即

49、變?yōu)榍嗄?，中年，老年：N1,N2,N3； 費(fèi)用變化率：指（當(dāng)月話費(fèi)近3個(gè)月的平均話費(fèi)）/近3個(gè)月的平均話費(fèi)）0，F(xiàn)1:0,則在事件B 已經(jīng)發(fā)生的條件下，事件A發(fā)生的條件概率：u聯(lián)合概率：若對(duì)任意兩事件A、B都有P(A)0 ，P(B)0,則：P(AB)=P(A)P(BA)=P(B)P(AB)u邊際概率：若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)148貝葉斯定理貝葉斯定理u貝葉斯定理是關(guān)于隨機(jī)事件A和B的條件概率和邊緣概率的一則定理。u通常，事件A在事件

50、B發(fā)生的條件下的概率，與事件B在事件A發(fā)生的條件下的概率是不一樣的，然而，這兩者是有確定的關(guān)系的，貝葉斯定理就是這種關(guān)系的陳述。149貝葉斯定理貝葉斯定理由前面三個(gè)概率公式可以得到貝葉斯公式：全概率：P(B)=P(B A1)P(A1)+P(B A2)P(A2)條件概率：條件概率：聯(lián)合概率：P(AB)=P(A)P(BA)=P(B)P(AB)150貝葉斯定理貝葉斯定理兩個(gè)事件的貝葉斯公式：u若A1、A2構(gòu)成互斥和完整的兩個(gè)事件， A1和A2 中的一個(gè)出現(xiàn)是事件B發(fā)生的必要條件，則兩個(gè)事件的貝葉斯公式：1111122AAAAAAAPPPPPPP（）（B/）（/B）=（）（B/）+（）（B/）151貝

51、葉斯定理貝葉斯定理n個(gè)事件的貝葉斯 公式：u假定存在一個(gè)互斥和完整的事件A1,A2,An， Ai中的某一個(gè)出現(xiàn)是事件B發(fā)生的必要條件，則n個(gè)事件的貝葉斯公式：)/()()/()()/()()/()()/(2211111nnABPAPABPAPABPAPABPAPBAP152貝葉斯定理貝葉斯定理在貝葉斯定理中，每個(gè)名詞都有約定俗成的名稱：uP(A)：事件A的先驗(yàn)概率或邊緣概率?！跋闰?yàn)”指其不考慮任何B方面的因素。uP(AB)：事件A的后驗(yàn)概率，即已知B發(fā)生后A的條件概率。uP(BA)：事件B的后驗(yàn)概率，即已知A發(fā)生后B的條件概率。uP(B)：是事件B的先驗(yàn)概率或邊緣概率。示例示例1 1背景：背景

52、：辦公室新來(lái)了一個(gè)雇員小王，小王是好人還是壞人，大家都在猜測(cè)。按人們的主觀意識(shí)，一個(gè)人是好人還是壞人的概率均為0.5，壞人總是要做壞事，好人總是做好事，偶爾也會(huì)做一件壞事。一般好人做好事的概率是0.9，壞人做好事的概率是0.2.一天，小王做了一件好事，則小王是好人的概率有多大，小王究竟為好人還是壞人？示例示例1 1155 旅客搭乘飛機(jī)必須經(jīng)電子儀器檢查是否身上攜帶金屬物品。如果攜帶金屬，儀器會(huì)發(fā)出聲音的概率是97%，但身上無(wú)金屬物品儀器會(huì)發(fā)出聲音的概率是5%。 已知一般乘客身上帶有金屬物品的概率是30%，若某旅客經(jīng)過(guò)儀器檢查時(shí)發(fā)出聲音，請(qǐng)問(wèn)他身上有金屬物品的概率是多少？ 2022-3-30示例

53、示例2 215611111122()()()()()0.3 0.970.89260.3 0.970.7 0.05P X C P CP CXP C XP XP X C P CP X CP C2022-3-30解：解：設(shè)設(shè)C1=“有金屬物有金屬物”，X=“儀器會(huì)發(fā)聲儀器會(huì)發(fā)聲”，則則157貝葉斯分類貝葉斯分類 設(shè)X為一個(gè)類別未知的數(shù)據(jù)樣本，設(shè)H為某種假設(shè)，如：數(shù)據(jù)樣本X屬于某特定的類C。 對(duì)于分類問(wèn)題，我們希望確定P(HX)，即給定觀測(cè)數(shù)據(jù)樣本X，假定H成立的概率。 設(shè)x是一個(gè)類別未知的數(shù)據(jù)樣本，cj為某個(gè)類別，若數(shù)據(jù)樣本x屬于一個(gè)特定的類別cj，那么分類問(wèn)題就是決定P(cj|x)，即在獲得數(shù)據(jù)樣

54、本x時(shí)，確定x的最佳分類。u 先驗(yàn)概率先驗(yàn)概率P(P(cj) )P( cj|x) =P(x|cj)P(cj)P(x)u 后驗(yàn)概率后驗(yàn)概率P(P(x| |cj) )u 后驗(yàn)概率后驗(yàn)概率P(P(cj| |x) ) P(cj) 為類cj的先驗(yàn)概率(prior probability) ，它反映了我們所擁有的關(guān)于cj是正確分類的背景知識(shí)。 通?？梢杂脴永袑儆赾j的樣例數(shù)|cj|比上總樣例數(shù)|D|來(lái)近似，即:jj|c |P(c )= |D| 后驗(yàn)概率P(x|cj)指的是當(dāng)已知類別為cj的條件下，樣本x出現(xiàn)的概率。 若設(shè)x = ，且屬性值相互條件獨(dú)立，即在屬性間，不存在依賴關(guān)系，則P(x|cj)= P(

55、a1,a2am| cj) 即給定數(shù)據(jù)樣本x時(shí)cj成立的概率，而這正是我們所感興趣的。 P(cj|x )被稱為C的后驗(yàn)概率（posterior probability），因?yàn)樗从沉嗽诘玫綌?shù)據(jù)樣本x后cj成立的置信度.計(jì)算Pmax (ci|x) = max P(cj|x) j(1,|C|)則Pmax (ci|x)稱為最大后驗(yàn)概率，并將x分到ci類中.2. 2. 樸素貝葉斯分類？樸素貝葉斯分類？樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程（1）每個(gè)數(shù)據(jù)樣本X用一個(gè)n維特征向量：X=x1,x2,xn表示，分別描述對(duì)n個(gè)屬性(A1,A2,An)的具體取值；（2）假定共有m個(gè)不同類別，C1,C2,C

56、m。給定一個(gè)類別未知的數(shù)據(jù)樣本X，分類法將在已知X情況下，將X賦于后驗(yàn)概率最大的那個(gè)類別。即，樸素貝葉斯分類將類別未知的樣本X歸屬到類別Ci，當(dāng)且僅當(dāng)：即，最大化P(CiX)。其中的類別Ci稱為最大后驗(yàn)假定。根據(jù)貝葉斯定理，有：樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程（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)取最大。 否則，一般可以通過(guò)P(Ci)=si/s進(jìn)行估算，其中si

57、為訓(xùn)練樣本集合中類別Ci的個(gè)數(shù)，s為整個(gè)訓(xùn)練樣本集合的大小。樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程（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)行估算。具體處理如下：樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程1）如果Ak是符號(hào)屬性，則P(xkCi)=sik/si，：其中sik為訓(xùn)練樣本中類別為Ci且屬性Ak取值vk的樣本數(shù)，si為訓(xùn)練樣本

58、中類別為Ci的樣本數(shù)。樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程222()1()= (,)22(,)iiiiiiikkCkikCCCCikkCCkAxP xCg xeCAg xA（ ）如果是連續(xù)型屬性，則通常假定該屬性服從高斯分布。因而，其中，給定類的訓(xùn)練樣本屬性的值，是屬性的高斯密度函數(shù)。樸素貝葉斯分類的工作過(guò)程樸素貝葉斯分類的工作過(guò)程（5）為預(yù)測(cè)一個(gè)未知樣本X的類別，對(duì)每個(gè)類Ci，計(jì)算P(X Ci)P(Ci)。則，樣本X被指派到類Ci，當(dāng)且僅當(dāng)：P(XCi)P(Ci) P(XCj)P(Cj), 樸素貝葉斯分類的效果樸素貝葉斯分類的效果u研究表明，與決策樹(shù)和神經(jīng)網(wǎng)絡(luò)分類器相比，貝葉斯分

59、類器在某些情況下具有更好的分類效果。u但必須滿足某些假定條件，如要求各屬性間是相互獨(dú)立的。172示示例例示例示例背景：背景： 給定與決策樹(shù)歸納相同的訓(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”，C2對(duì)應(yīng)類“no”。3）需分類的未知樣本為：X=(age=“=30”, income=“medium”, student=“yes”, credit-rating=“fair”)示例示例根據(jù)貝葉斯分類公式： 由于P(X)對(duì)于所有的類別均是相同的，因此只需要計(jì)算P(X Ci)P(Ci)取最大即可。 P(Ci）為先驗(yàn)概率，可用如下公式計(jì)算： P(Ci)=si/s。 對(duì)于P(X Ci)，在假定各屬性是相互獨(dú)立的前提下，可按照如下公式計(jì)算：P(CP(Ci i) )的計(jì)算的計(jì)算P(Ci)為類別的先驗(yàn)概率，i=1,2，具體計(jì)算如下：P(X Ci) 的的計(jì)算計(jì)算X=(age=“=30”, income=“medium”, student=“yes”, credit-rating=“fair”)結(jié)結(jié) 論論計(jì)算P(X Ci)P(Ci)，并