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

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

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

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

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

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

6、估無標(biāo)號樣本類 ，或評估給定樣本可能具有的屬性值或值區(qū)間u與分類區(qū)別：與分類區(qū)別：二者是兩類主要的預(yù)測問題。 分類是預(yù)測離散或標(biāo)號值； 預(yù)測是預(yù)測連續(xù)或有序值；觀點：用預(yù)測法預(yù)測類標(biāo)號為分類；用預(yù)測法預(yù)測連續(xù)值（一般用回歸法）為預(yù)測。18示例示例背景：背景： 假定已建立AllElectronics公司的郵寄清單數(shù)據(jù)庫。郵寄清單用于分發(fā)介紹新產(chǎn)品和降價信息材料。數(shù)據(jù)庫描述顧客的屬性，包括姓名、年齡、收入、職業(yè)和信譽度，并按照顧客是否在該公司購買計算機進行分類。19示例示例分類模型：分類模型： 假定新的顧客添加到數(shù)據(jù)庫中，由于向每位顧客分發(fā)促銷材料費用很高，因此，可以根據(jù)數(shù)據(jù)庫中已有顧客信息構(gòu)建分

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

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

9、常見的距離分類算法？1. 1. 基于距離分類的基本思想？基于距離分類的基本思想？2022年3月30日星期三25基于距離的分類算法的思路基于距離的分類算法的思路q 定義：給定一個數(shù)據(jù)庫 D=t1，t2，tn和一組類C=C1，Cm。假定每個元組包括一些數(shù)值型的屬性值：ti=ti1，ti2，tik，每個類也包含數(shù)值性屬性值：Cj=Cj1，Cj2，Cjk，則分類問題是要分配每個分類問題是要分配每個ti到滿足如下條件的類到滿足如下條件的類Cj： sim(ti，Cj)=sim(ti，Ci) ，CiC，CiCj，其中sim(ti，Cj)被稱為相似性。2022年3月30日星期三26基于距離的分類算法的思路基于

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

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

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

13、往用距離來表征： 距離越近，相似性越大；距離越近，相似性越大； 距離越遠，相似性越小。距離越遠，相似性越小。q距離的計算方法有多種，最常用的是通過計算樣本到每個類中心的距離來完成。2022年3月30日星期三31 基于距離的分類算法的一般性描述基于距離的分類算法的一般性描述q算法計算每個元組到各個類中心的距離類中心的距離，從而可以找出離它的最近的類中心，得到確定的類別標(biāo)記。算法 基于距離的分類算法輸入：每個類的中心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);請用基于距離的算法基于距離的算法給以下樣本分類：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 幾種常見的距離分類算法？幾種常見的距離分類算法？36幾種常見的距離分類算法幾種常見的距離分類算法 u （1）k-近鄰算法近鄰算法；u （2）K-means算法（聚類）；算法（聚類）；u （3）K-mediods算法（聚類）。算法（聚類）。2022年3月30日星期三37（1）K-近鄰分類算法近鄰分類算法qK-近鄰分類算法（K Nearest Neighb

16、ors，簡稱KNN）通過計算每個訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個訓(xùn)練數(shù)據(jù)，K個數(shù)據(jù)中哪個類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個類別。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個樣本；v 將目標(biāo)劃分到找出的K個樣本中出現(xiàn)最頻繁的類。2、K的直觀形式：的直觀形式：v 以目標(biāo)樣本為中心；v 劃出一個剛好包含K個樣本的圓；v 當(dāng)K增大時，圓半徑增大。KNN的直觀解釋的直觀解釋3、直觀的例子、直觀的例子v手寫識別手寫識別 記錄手寫體特征； 計算手寫體與標(biāo)準(zhǔn)漢字的相似度； 根據(jù)相似度（距離），找出K個備選集； 選擇一個正確漢字v人種識

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

19、大增加計算復(fù)雜性3、算法的復(fù)雜度v 維數(shù)災(zāi)難：當(dāng)維數(shù)增加時，算法的復(fù)雜度會急劇增加v 一般采用降維處理6.3 6.3 決策樹分類算法決策樹分類算法l 決策樹的基本概念？決策樹的基本概念？l 決策樹生成算法？決策樹生成算法？l 剪枝方法？剪枝方法？l 提取分類規(guī)則？提取分類規(guī)則？1. 1. 決策樹的基本概念？決策樹的基本概念？決策樹基本概念決策樹基本概念解決分類問題的一般方法解決分類問題的一般方法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)號已知）訓(xùn)練集（類標(biāo)號已知）檢驗集（類標(biāo)號未知）檢驗集（類標(biāo)號未知）歸納歸納推論推論46基本概念基本概念 u 決策樹（decision tree）： 決策樹是一種典型的分類方法，首先對數(shù)據(jù)進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策樹對新數(shù)據(jù)進行分析。 本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。年齡？學(xué)生？信譽？買青中老否是優(yōu)良不買買買不買47決策樹的基本組成決策樹的基本組成u 決策樹的基本組成決策樹是類似流程圖的倒立的樹型結(jié)構(gòu)。最頂層節(jié)點為根節(jié)點根節(jié)點，是整個決策樹的開始；樹的每個內(nèi)部節(jié)點內(nèi)部節(jié)點表示在一個屬性上的測試，其每個分支代表一個測試輸出；樹的

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

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

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

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

25、 白種人白種人5混血混血7黑色黑色金色金色金色金色紅色紅色黑色黑色金色金色紅色紅色黑色黑色CLS算法算法1） 生成一顆空決策樹和一張訓(xùn)練樣本屬性集;2） 若訓(xùn)練樣本集T 中所有的樣本都屬于同一類，則生成結(jié)點T ，并終止學(xué)習(xí)算法；否則3） 根據(jù)某種策略某種策略從訓(xùn)練樣本屬性表中選擇屬性A 作為測試屬性， 生成測試結(jié)點A 4） 若A的取值為v1,v2,vm， 則根據(jù)A 的取值的不同，將T 劃分成 m個子集T1,T2,Tm;5） 從訓(xùn)練樣本屬性表中刪除屬性A;6） 轉(zhuǎn)步驟2, 對每個子集遞歸調(diào)用CLS。CLS算法存在的問題算法存在的問題q 在步驟3中，根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測試

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

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

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

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

30、假定類別屬性C具有m個不同值Ci (i=1,2,m)。設(shè)si是類Ci中的樣本個數(shù)，則，對一個給定數(shù)據(jù)對象進行分類所需要的期望信息可由下式給出：其中，pi是任意樣本屬于類Ci的概率，按照si /S進行計算。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)越大，說明選擇測試

31、屬性對分類提供的信息越多.ID3 屬性選擇方法屬性選擇方法計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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 怎么建立決策樹？怎么建立決策樹？v 誰是根節(jié)點？誰是根節(jié)點？v 誰是下一層子節(jié)點？誰是下一層子節(jié)點？為什么是它？為什么是它？計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步計算決策屬性的熵步計算決策屬性的熵決策屬性決策屬性“買計算機？買計算機？”該屬性分兩類：買/不買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算法示例算法示例初始不初始不確定性確定性計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步計算條件屬性的熵步計算條件屬性的熵條件屬性條件屬性共有4個： 分別是年齡、收入、學(xué)生、信譽。 分別計算不同屬性的信息增益。ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步步 計算年齡的熵計算年齡的熵年齡年齡共分三個組： 青年、中年、老年1）青年：）青年：買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步步 計算年齡的熵計算年齡的熵年齡共分三個組： 青年、中年、老年2）中年：）中年：買與不買比例為256/0S1(買)=256 S2（不買）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步計算年齡的熵步計算年齡的熵年齡共分三個組： 青年、中年、老年3）老年：）老年：買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步步 計算年齡的熵計算年齡的熵年齡共分三個組： 青年、中年、老年所占比例：青年組 384/1025=0.375中年組 256/1024=0.25老年組 384/1024=0.375計算年齡的平均信息期望年齡的平均信息期望E（年齡）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877G（年齡信息增益） =0.9537-0.6877 =0.2660 （1）ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機

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步步 計算計算收入收入的熵的熵收入共分三個組： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 （2）ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步步 計算計算學(xué)生學(xué)生的熵的熵學(xué)生共分二個組： 學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811 =0.1726 （3）ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步步 計算計算信譽信譽的熵的熵信譽分二個組： 良好，優(yōu)秀E（信譽）= 0.9048信譽信息增

40、益=0.9537-0.9048 =0.0453 （4）ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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步計算選擇節(jié)點步計算選擇節(jié)點 年齡年齡信息增益=0.9537-0.6877 =0.2660 （1）收入信息增益=0.9537-0.9361 =0.0176 （2）年齡信息增益=0.9537-0.7811 =0.1726 （3）信譽信息增益=0.9537-0

41、.9048 =0.0453 （4）ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡年齡青年中年老年買/不買買買/不買葉子ID3算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入收入作為節(jié)點分高、中、低平均信息期望（加權(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算法示例算法示例計數(shù)年齡收入學(xué)生信譽歸類：買計算機？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ōu)優(yōu)良良買不買買/不買買葉子葉子葉子ID3算法示例算法示例ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1） 通過ID3算法來實現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的特征，以幫助電信公司有針對性地改善客戶關(guān)系，避免客戶流失. 利用

44、決策樹方法進行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)數(shù)據(jù)預(yù)處理、決策樹挖掘處理、決策樹挖掘操作，模式評估和應(yīng)用。 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1）v電信運營商的客戶流失有三方面的含義： 一是指客戶從一個電信運營商轉(zhuǎn)網(wǎng)到其他電信運營商，這是流失分析的重點； 二是指客戶月平均消費量降低，從高價值客戶成為低價值客戶。 三指客戶自然流失和被動流失。ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1）v 在客戶流失分析中有兩個核心變量：財務(wù)原因非財務(wù)原因、主動流失被動流失。v 客戶流失可以相應(yīng)分為四種類型.v 其中非財務(wù)原因主動流失非財務(wù)原因

45、主動流失的客戶往往是高價值的客戶。他們會正常支付服務(wù)費用，并容易對市場活動有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。 （1）數(shù)據(jù)預(yù)處理）數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲在數(shù)據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲在其CRM中），是長期積累的結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般包括數(shù)據(jù)的選擇(選擇相關(guān)的數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分，對于挖掘算法的效率乃至正確性都有關(guān)鍵性的影響。ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1）（1）數(shù)據(jù)預(yù)處理）數(shù)據(jù)預(yù)處理 該公司經(jīng)過多年的電腦化管理，已

46、有大量的客戶個人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號碼、用戶標(biāo)識、用戶身份證號碼(轉(zhuǎn)化為年齡)、在網(wǎng)時間（竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)）等等，數(shù)據(jù)準(zhǔn)備時必須除掉表中一些不必要的屬性，一般可采用面向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。 ID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1）1）屬性刪除：）屬性刪除： 將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標(biāo)識、身份證號碼等，它們的取值太多且無法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表

47、1。 表1 客戶信息表年齡學(xué)歷職業(yè)繳費方式在網(wǎng)時長費用變化率客戶流失58大學(xué)公務(wù)員托收1310%NO47高中工人營業(yè)廳繳費942%NO26研究生公務(wù)員充值卡263%YES28大學(xué)公務(wù)員營業(yè)廳繳費52.91%NO32初中工人營業(yè)廳繳費32.3%NO42高中無業(yè)人員充值卡2100%YES68初中無業(yè)人員營業(yè)廳繳費92.3%NOID3算法實際應(yīng)用算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（在電信行業(yè)應(yīng)用實例（1）2）屬性概化：）屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進行概化。 文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(xué)(?？?、本科及以上)； 職業(yè)類別：按工作性質(zhì)來

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

49、變?yōu)榍嗄辏心?，老年：N1,N2,N3； 費用變化率：指（當(dāng)月話費近3個月的平均話費）/近3個月的平均話費）0，F(xiàn)1:0,則在事件B 已經(jīng)發(fā)生的條件下，事件A發(fā)生的條件概率：u聯(lián)合概率：若對任意兩事件A、B都有P(A)0 ，P(B)0,則：P(AB)=P(A)P(BA)=P(B)P(AB)u邊際概率：若A1、A2構(gòu)成互斥和完整的兩個事件， A1和A2 中的一個出現(xiàn)是事件B發(fā)生的必要條件，則事件B的邊際概率公式為（全概率公式）：P(B)=P(B A1)P(A1)+P(B A2)P(A2)148貝葉斯定理貝葉斯定理u貝葉斯定理是關(guān)于隨機事件A和B的條件概率和邊緣概率的一則定理。u通常，事件A在事件

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

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

52、：辦公室新來了一個雇員小王，小王是好人還是壞人，大家都在猜測。按人們的主觀意識，一個人是好人還是壞人的概率均為0.5，壞人總是要做壞事，好人總是做好事，偶爾也會做一件壞事。一般好人做好事的概率是0.9，壞人做好事的概率是0.2.一天，小王做了一件好事，則小王是好人的概率有多大，小王究竟為好人還是壞人？示例示例1 1155 旅客搭乘飛機必須經(jīng)電子儀器檢查是否身上攜帶金屬物品。如果攜帶金屬，儀器會發(fā)出聲音的概率是97%，但身上無金屬物品儀器會發(fā)出聲音的概率是5%。 已知一般乘客身上帶有金屬物品的概率是30%，若某旅客經(jīng)過儀器檢查時發(fā)出聲音，請問他身上有金屬物品的概率是多少？ 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=“儀器會發(fā)聲儀器會發(fā)聲”，則則157貝葉斯分類貝葉斯分類 設(shè)X為一個類別未知的數(shù)據(jù)樣本，設(shè)H為某種假設(shè)，如：數(shù)據(jù)樣本X屬于某特定的類C。 對于分類問題，我們希望確定P(HX)，即給定觀測數(shù)據(jù)樣本X，假定H成立的概率。 設(shè)x是一個類別未知的數(shù)據(jù)樣本，cj為某個類別，若數(shù)據(jù)樣本x屬于一個特定的類別cj，那么分類問題就是決定P(cj|x)，即在獲得數(shù)據(jù)樣

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

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

56、m。給定一個類別未知的數(shù)據(jù)樣本X，分類法將在已知X情況下，將X賦于后驗概率最大的那個類別。即，樸素貝葉斯分類將類別未知的樣本X歸屬到類別Ci，當(dāng)且僅當(dāng)：即，最大化P(CiX)。其中的類別Ci稱為最大后驗假定。根據(jù)貝葉斯定理，有：樸素貝葉斯分類的工作過程樸素貝葉斯分類的工作過程（3）由于P(X)對于所有的類別均是相同的，因此只需要計算P(X Ci)P(Ci)取最大即可。 如果各類別的先驗概率未知，通常假定這些類是等概率的，即：P(C1)=P(C2)=P(Cm)。這樣變成只需要對P(X Ci)求最大，否則就要P(X Ci)P(Ci)取最大。 否則，一般可以通過P(Ci)=si/s進行估算，其中si

57、為訓(xùn)練樣本集合中類別Ci的個數(shù)，s為整個訓(xùn)練樣本集合的大小。樸素貝葉斯分類的工作過程樸素貝葉斯分類的工作過程（4）對于包含多個屬性的數(shù)據(jù)集，直接計算P(X Ci) 的運算量是非常大的。為實現(xiàn)對P(X Ci)的有效估算，樸素貝葉斯分類通常假設(shè)各屬性是相互獨立的，即在屬性間，不存在依賴關(guān)系，則對于給定的類別Ci ，有：而P(x1 Ci), P(x2 Ci), P(xn Ci)的值，可以由訓(xùn)練樣本集進行估算。具體處理如下：樸素貝葉斯分類的工作過程樸素貝葉斯分類的工作過程1）如果Ak是符號屬性，則P(xkCi)=sik/si，：其中sik為訓(xùn)練樣本中類別為Ci且屬性Ak取值vk的樣本數(shù)，si為訓(xùn)練樣本

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

59、類器在某些情況下具有更好的分類效果。u但必須滿足某些假定條件，如要求各屬性間是相互獨立的。172示示例例示例示例背景：背景： 給定與決策樹歸納相同的訓(xùn)練數(shù)據(jù)集，希望使用樸素貝葉斯分類預(yù)測未知樣本的類標(biāo)號?；拘畔ⅲ夯拘畔ⅲ?）數(shù)據(jù)樣本用age, income, student, credit-rating描述。類標(biāo)號屬性buys_computer具有兩個不同取值yes, no。2）設(shè)C1對應(yīng)類“yes”，C2對應(yīng)類“no”。3）需分類的未知樣本為：X=(age=“=30”, income=“medium”, student=“yes”, credit-rating=“fair”)示例示例根據(jù)貝葉斯分類公式： 由于P(X)對于所有的類別均是相同的，因此只需要計算P(X Ci)P(Ci)取最大即可。 P(Ci）為先驗概率，可用如下公式計算： P(Ci)=si/s。 對于P(X Ci)，在假定各屬性是相互獨立的前提下，可按照如下公式計算：P(CP(Ci i) )的計算的計算P(Ci)為類別的先驗概率，i=1,2，具體計算如下：P(X Ci) 的的計算計算X=(age=“=30”, income=“medium”, student=“yes”, credit-rating=“fair”)結(jié)結(jié) 論論計算P(X Ci)P(Ci)，并