數(shù)據(jù)挖掘第8章-分類：基本概念

數(shù)據(jù)挖掘與商務智能范勤勤物流研究中心第八章分類1基本概念2決策樹歸納3貝葉斯分類方法4基于規(guī)則的分類5模型評估與選擇6提高分類準確率的技術基本概念分類VS.預測分類預測類標號（離散值）根據(jù)訓練數(shù)據(jù)集和類標號屬性，構建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)典型應用信譽證實（分類為低，中，高風險）醫(yī)療診斷（腫瘤是良性還是惡性）性能預測目標市場預測建立連續(xù)函數(shù)值模型，比如預測空缺值4一個兩步過程第一步，建立一個分類模型，描述預定數(shù)據(jù)類或概念集假定每個元組屬于一個預定義的類，由一個類標號屬性確定基本概念訓練數(shù)據(jù)集：由為建立模型而被分析的數(shù)據(jù)元組形成訓練樣本：訓練數(shù)據(jù)集中的單個樣本（元組）學習模型可以由分類規(guī)則、判定樹或數(shù)學公式的形式提供第二步，使用模型，對將來的或未知的對象進行分類評估模型的預測準確率測試集：要獨立于訓練樣本集，避免“過分擬合”的情況對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較準確率：被模型正確分類的測試樣本的百分比如果準確率可以接受，那么使用該模型來分類標簽為未知的樣本56第一步——建立模型訓練數(shù)據(jù)集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規(guī)則7第二步——用模型進行分類分類規(guī)則測試集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?有指導的學習VS.無指導的學習有指導的學習（用于分類）模型的學習在被告知每個訓練樣本屬于哪個類的“指導”下進行新數(shù)據(jù)使用訓練數(shù)據(jù)集中得到的規(guī)則進行分類無指導的學習（用于聚類）每個訓練樣本的類編號是未知的，要學習的類集合或數(shù)量也可能是事先未知的通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類8決策樹歸納用決策樹歸納分類什么是決策樹？類似于流程圖的樹結構每個內(nèi)部節(jié)點（非樹葉節(jié)點）表示在一個屬性上的測試每個分枝代表該測試的一個輸出每個樹葉節(jié)點存放一個類標號10age?nostudent?credit_rating?noyesfairexcellentyouthseniornoyesyesyesMiddleaged決策樹：Buys_computer用決策樹歸納分類使用決策樹分類給定一個類標號未知的元組X，在決策樹上測試元組的屬性值，跟蹤一條由根到葉節(jié)點的路徑，葉節(jié)點存放該元組的類預測。決策樹容易轉(zhuǎn)換為分類規(guī)則決策樹的生成由兩個階段組成決策樹構建：自頂向下遞歸地分治方式使用屬性選擇度量來選擇將元組最好的劃分為不同的類的屬性遞歸的通過選定的屬性（必須是離散值）來劃分樣本樹剪枝決策樹建立時，許多分枝反映的是訓練數(shù)據(jù)中的噪聲或離群點，樹剪枝試圖識別并剪去這種分枝，以提高對未知數(shù)據(jù)分類的準確性11決策樹歸納策略輸入數(shù)據(jù)分區(qū)D，訓練元組和他們對應類標號的集合attribute_list,候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發(fā)式過程算法步驟1.樹以代表訓練樣本的單個節(jié)點（N）開始2.如果樣本都在同一個類，則該節(jié)點成為樹葉，并用該類標記3.否則，算法調(diào)用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準則”，指出“分裂點”或“分裂子集”4.對測試屬性每個已知的值，創(chuàng)建一個分支，并以此劃分元組5.算法使用同樣的過程，遞歸的形成每個劃分上的元組決策樹。一旦一個屬性出現(xiàn)在一個節(jié)點上，就不在該節(jié)點的任何子節(jié)點上出現(xiàn)6.遞歸劃分步驟停止的條件劃分D（在N節(jié)點提供）的所有元組屬于同一類沒有剩余屬性可以用來進一步劃分元組——使用多數(shù)表決沒有剩余的樣本給定分支沒有元組，則以D中多數(shù)類創(chuàng)建一個樹葉12屬性選擇度量屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓練元組最好的進行劃分的方法理想情況，每個劃分都是“純”的，即落在一個給定分區(qū)的所有元組都屬于相同的類屬性選擇度量又稱為分裂規(guī)則常用的屬性選擇度量信息增益增益率基尼指數(shù)（Gini指數(shù)）13信息增益選擇具有最高信息增益的屬性作為結點N的分裂屬性pi是D中任意元組屬于類Ci的非零概率，并用|Ci,D|/|D|估計對D中的元組分類所需要的期望信息（熵）由下式給出：14信息增益用屬性A將D劃分為v個分區(qū)或子集后，為了得到準確的分類，我們還需要多少信息？這個量由下式度量：例8.115ageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno16例8.1代表“age<=30”占14個樣本中的5個有2個"yes"和3個"no"ClassP:buys_computer=“yes”ClassN:buys_computer=“no”相應的，計算對D中元組分類所需要的期望信息：若元組根據(jù)age劃分，則：這種劃分的信息增益：計算連續(xù)值屬性的信息增益假設A是連續(xù)值的，而不是離散值分裂D1是滿足A≤split-point的元組集合,而D2是滿足A>split-point的元組集合必須確定A的“最佳”分裂點將A的值按遞增序排序典型的，每對相鄰值的中點被看作可能的分裂點A的值ai和ai+1之間的中點是(ai+ai+1)/2A具有最小期望信息需求的點選做A的分裂點17增益率信息增益度量傾向于選擇具有大量值的屬性18ID3的后繼C4.5使用一種稱為增益率的信息增益擴充，試圖克服這種偏倚，它用“分裂信息”值將信息增益規(guī)范化，分裂信息定義如下：分裂信息增益率選擇具有最大增益率的屬性作為分裂屬性—GainRatio(income)=0.029/1.557=0.019例8.2incomehigh4medium6low4基尼指數(shù)如果A的二元劃分將D劃分成D1和D2，則給定該劃分，D的基尼指數(shù)為：最大化不純度降低（或等價地，具有最小基尼指數(shù)）的屬性選為分裂屬性。（需要枚舉所有可能的分裂情況）19基尼指數(shù)度量數(shù)據(jù)分區(qū)或訓練元組集D的不純度，定義為：其中pj是D中元組屬于Ci類的概率不純度降低為:屬性選擇度量對比信息增益偏向于多值屬性基尼指數(shù)偏向于多值屬性當類的數(shù)量很大時會有困難傾向于導致相等大小的分區(qū)和純度增益率傾向于不平衡的劃分，其中一個分區(qū)比其他分區(qū)小得多20三種度量通常會得到好的結果，但這些度量并非無偏的過度擬合與樹剪枝產(chǎn)生的決策樹會出現(xiàn)過分適應數(shù)據(jù)的問題由于數(shù)據(jù)中的噪聲和離群點，許多分枝反映的是訓練數(shù)據(jù)的異常對未知樣本判斷不準確防止過分擬合的兩種方法先剪枝通過提前停止樹的構造，如果劃分一個結點元組導致低于預定義臨界值的劃分，則給定子集的進一步劃分將停止。選擇一個合適的臨界值往往很困難后剪枝由“完全生長”的樹剪去子集——算法產(chǎn)生一個漸進的剪枝樹集合使用一個獨立的測試集來評估每顆樹的準確率，就能得到具有最小期望錯誤率的決策樹21可伸縮性與決策樹歸納RainForest(雨林)能適應可用的內(nèi)存量，并用于任意決策樹歸納算法結點N上屬性A的AVC-集給出N上元組A的每個值的類標號計數(shù)在每個結點，對每個屬性維護一個AVC-集（其中AVC表示“屬性-值，類標號”），描述該結點的訓練元組結點N上所有AVC-集的集合是N的AVC-組群2223雨林:訓練集和它的AVC-集AVC-setonincomeAVC-setonAgeAVC-setonStudentAVC-setoncredit_ratingAgeBuy_Computeryesno<=302331..4040>4032incomeBuy_Computeryesnohigh22medium42low31studentBuy_Computeryesnoyes61no34CreditratingBuy_Computeryesnofair62excellent33貝葉斯分類方法貝葉斯定理設X是數(shù)據(jù)元組（“證據(jù)”）：類標號未知P(H|X)是后驗概率，或在條件X下，H的后驗概率例如，X是一位35歲的顧客，其收入為4萬美元。令H為某種假設，如顧客將購買計算機令H為某種假設，如數(shù)據(jù)元組X屬于某個特定類C25P(H)(priorprobability)是先驗概率，或H的先驗概率例如,X將購買電腦,無論年齡和收入等等P(X)是X的先驗概率，可觀察到樣本數(shù)據(jù)用上面的例子，它是顧客集合中年齡為35歲且收入為四萬美元的概率貝葉斯定理為樸素貝葉斯分類（Na?veBayesian）設D是訓練元組和它們相關聯(lián)的類標號的集合。通常，每個元組用一個n維屬性向量X=(x1,x2,…,xn)表示，描述由n個屬性對元組的n個測量給定元組X，分類法將預測X屬于具有最高后驗概率的類（在條件X下）假設有m個類C1,C2,…,Cm26根據(jù)貝葉斯定理由于P(X)對所有類為常數(shù)，所以需將下式最大化類條件獨立使用樸素貝葉斯分類預測類標號類C1:buys_computer=‘yes’C2:buys_computer=‘no’希望分類的元組X=(age<=30,Income=medium,Student=yes，Credit_rating=Fair)27ageincomestudentcredit_ratingbuys_computer<=30highnofairno<=30highnoexcellentno31…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes<=30mediumnofairno<=30lowyesfairyes>40mediumyesfairyes<=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes>40mediumnoexcellentno使用樸素貝葉斯分類預測類標號P(Ci)P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357為計算P(X|Ci)，計算下面的條件概率P(age=“<=30”|buys_computer=“yes”)=2/9=0.222P(age=“<=30”|buys_computer=“no”)=3/5=0.600P(income=“medium”|buys_computer=“yes”)=4/9=0.444P(income=“medium”|buys_computer=“no”)=2/5=0.400P(student=“yes”|buys_computer=“yes)=6/9=0.667P(student=“yes”|buys_computer=“no”)=1/5=0.200P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.40028ageincomebuys_computer<=30highno<=30highno31…40highyes>40mediumyes>40lowyes>40lowno31…40lowyes<=30mediumno<=30lowyes>40mediumyes<=30mediumyes31…40mediumyes31…40highyes>40mediumnostudentcredit_ratingbuys_computernofairnonoexcellentnonofairyesnofairyesyesfairyesyesexcellentnoyesexcellentyesnofairnoyesfairyesyesfairyesyesexcellentyesnoexcellentyesyesfairyesnoexcellentno使用樸素貝葉斯分類預測類標號X=(age<=30,income=medium,student=yes,credit_rating=fair)P(X|Ci)*P(Ci)P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007P(X|Ci)P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.667=0.044P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019因此，對于元組X，樸素貝葉斯分類預測元組X的類為“buys_computer=yes”29使用拉普拉斯校準避免計算零概率值例8.5假設在某訓練數(shù)據(jù)庫D上,類buys-computer=yes包含1000個元組，0個元組income=low,990個元組income=medium,10個元組income=high用拉普拉斯進行校準對每個收入-值對增加一個元組Prob(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003這些“校準的”概率估計與對應的“未校準的”估計很接近，但是避免了零概率值30基于規(guī)則的分類使用IF-THEN規(guī)則分類一個IF-THEN規(guī)則是一個如下形式的表達式R:IFage=youthANDstudent=yesTHENbuys_computer=yes規(guī)則前件/規(guī)則的結論將R的覆蓋率和準確率定義為ncovers

：為規(guī)則R覆蓋的元組數(shù)ncorrect：R正確分類的元組數(shù)coverage(R)=ncovers/|D|/*D:trainingdataset*/accuracy(R)=ncorrect/ncovers32使用IF-THEN規(guī)則分類如果多個規(guī)則被觸發(fā)，則需要一種解決沖突的策略來決定激活哪一個規(guī)則，并對X指派它的類預測規(guī)模序:方案把最高優(yōu)先權賦予具有“最苛刻”要求的被觸發(fā)的規(guī)則，其中苛刻性用規(guī)則前件的規(guī)模度量，激活具有最多屬性測試的被觸發(fā)的規(guī)則?；陬惖男?類按“重要性”遞減排序，如按普遍性的降序排序基于規(guī)則的序:根據(jù)規(guī)則質(zhì)量的度量，或領域?qū)＜业慕ㄗh，把規(guī)則組織成一個優(yōu)先權列表33由決策樹提取規(guī)則規(guī)則比大的決策樹更容易理解對每條從根到樹葉結點的路徑創(chuàng)建一個規(guī)則規(guī)則是互斥的和窮舉的例8.7由決策樹提取分類規(guī)則IFage=youngANDstudent=noTHENbuys_computer=noIFage=youngANDstudent=yesTHENbuys_computer=yesIFage=mid-age THENbuys_computer=yesIFage=oldANDcredit_rating=excellentTHENbuys_computer=noIFage=oldANDcredit_rating=fairTHENbuys_computer=yes34age?student?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno模型評估與選擇模型評估與選擇評價指標:我們?nèi)绾螠y量精度?其他指標要考慮嗎?評估一個分類準確率的方法保持方法,隨機二次抽樣交叉驗證自助法分類器的準確率最好在檢驗集上估計模型選擇統(tǒng)計顯著性檢驗基于成本效益和ROC曲線36評估分類器性能的度量37正組元（P）：感興趣的主要類的元組。負組元（N）：其他元組。真正例（TruePositive，TP）：是指被分類器正確分類的正元組。真負例（TrueNegative，TN）：是指被分類器正確分類的負元組。假正例（FalsePositive，F(xiàn)P）：是被錯誤地標記為正元組的負元組。假負例（False

Negative，F(xiàn)N）：是被錯誤地標記為負元組的正元組。評估分類器性能的度量：混淆矩陣混淆矩陣給定m個類，混淆矩陣前m行和m列中的表目CMi,j指出類i的元組被分類器標記為類j的個數(shù)混淆矩陣的例子38實際的類\預測的類yesnoyesTPFNnoFPTN類buy_computer=yesbuy_computer=no合計buy_computer=yes6954467000buy_computer=no41225883000合計7366263410000準確性、錯誤率、敏感度和特效性類不平衡問題其中感興趣的主類是稀少的，例如“欺詐”正類多，負類少靈敏性(召回率):正確識別的正元組的百分比,靈敏性=TP/P特效性:正確識別的負元組的百分比,特效性=TN/N準確率=靈敏性×P/(P+N)+特效性×N/(P+N)=(TP+TN)/(P+N)錯誤率)=(FP+FN)/(P+N)39A\Pyesno合計yesTPFNPnoFPTNN合計P’N’P+N精度、召回率、F度量精度:精確性的度量，即標記為正類元組實際為正類所占的百分比F度量(F1

或F分數(shù)):把精度和召回率集中到一個度量中F?:精度和召回率的加權度量它賦予召回率權重是賦予進度的β倍40例子41類cancer=yescancer=no合計識別率(%)cancer=yes90（TP）210（FN）300（P）30.00(sensitivitycancer=no140（FP）9560（TN）9700（N）98.56(specificity)合計23097701000096.40(accuracy)準確率（TP+TN）/(P+N)錯誤率（FP+FN）/(P+N)敏感度（召回率）TP/P特效性TN/N精度TP/(TP+FP)Precision=90/230=39.13%

Recall=90/300=30.00%保持方法,隨機二次抽樣保持方法給定的數(shù)據(jù)隨機的劃分為兩個獨立的集合訓練集，通常2/3的數(shù)據(jù)被分配到訓練集檢驗集，通常1/3的數(shù)據(jù)被分配到檢驗集隨機二次抽樣:保持方法的變形將保持方法重復k次，總準確率估計取每次迭代準確率的平均值交叉驗證(k-折交叉驗證)初始數(shù)據(jù)隨機地劃分成k個互不相關的子集，每個子集的大小大致相等在第i次迭代,分區(qū)Di用作檢驗集，其他區(qū)位訓練集留一:每次只給檢驗集“留出”一個樣本分層交叉驗證：折被分層，使的每個折中樣本的類分布與在初始數(shù)據(jù)中的大致相同42自助法自助法處理較小的數(shù)據(jù)集合比較有效從給定訓練元組中有放回的均勻抽樣在有放回的抽樣中，允許機器多次選擇同一個元組43有多種自助方法,最常用的一種是.632自助法假設給定的數(shù)據(jù)集包括d個元組。該數(shù)據(jù)集有放回地抽樣d次，產(chǎn)生d個樣本的自助樣本集或訓練集。結果是，在平均的情況下，63.2%的原數(shù)據(jù)元組將出現(xiàn)在自助樣本中，而其余36.8%的元組將形成檢驗使用統(tǒng)計顯著性檢驗選擇模型假設已經(jīng)由數(shù)據(jù)產(chǎn)生了兩個分類模型M1

和M2,如何確定哪一個更好？M1

和M2

的平均錯誤率雖不同，但差別可能不是統(tǒng)計顯著的進行10折交叉驗證，得到每一個平均錯誤率err(M1)和err(M2)i如果二者之間的差別只是偶然的，該如何處理？統(tǒng)計顯著性檢驗44使用統(tǒng)計顯著性檢驗選擇模型如果我們能拒絕原假設,則則可以斷言模型之間的差是統(tǒng)計顯著的在此情況下，我們可以選擇具有較低錯誤率的模型45進行10次10-折交叉驗證利用t-檢驗假設它們服從具有k-1個自由度的t分布，其中k=10.原假設:M1&M2

相同t-檢驗46如果使用單個檢驗集:逐對比較