數(shù)據(jù)挖掘概念與技術(shù)CHAPTER6-分類基本概念課件

1Chapter6.分類:基本概念分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummary2有監(jiān)督vs.無監(jiān)督學(xué)習(xí)有監(jiān)督學(xué)習(xí)(分類)監(jiān)督：訓(xùn)練數(shù)據(jù)（觀察，測量等）都帶有標(biāo)簽,指示觀察的類別根據(jù)訓(xùn)練集分類新數(shù)據(jù)無監(jiān)督學(xué)習(xí)

(聚類)訓(xùn)練集的類別（標(biāo)簽）未知給定一個(gè)觀察，測量等的集合，目標(biāo)是建立數(shù)據(jù)中存在的數(shù)據(jù)的類或簇3分類預(yù)測分類的類標(biāo)簽(離散or名義)基于訓(xùn)練數(shù)據(jù)和類標(biāo)簽

構(gòu)造一個(gè)模型，并分類新數(shù)據(jù)數(shù)值預(yù)測

建連續(xù)值函數(shù)/模型,預(yù)測未知/缺失值典型應(yīng)用信用卡/貸款審批:醫(yī)療診斷:腫瘤是癌或良性？欺詐檢測:交易欺詐?網(wǎng)頁分類：這是哪一類？預(yù)測問題：

分類vs.數(shù)值預(yù)測5Process(1):模型構(gòu)建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)6Process(2):UsingtheModelinPredictionClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?Issues:EvaluatingClassificationMethodsAccuracyclassifieraccuracy:predictingclasslabelpredictoraccuracy:guessingvalueofpredictedattributesSpeedtimetoconstructthemodel(trainingtime)timetousethemodel(classification/predictiontime)Robustness:handlingnoiseandmissingvaluesScalability:efficiencyindisk-residentdatabasesInterpretabilityunderstandingandinsightprovidedbythemodelOthermeasures,e.g.,goodnessofrules,suchasdecisiontreesizeorcompactnessofclassificationrules9決策樹歸納:例子age?overcaststudent?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno訓(xùn)練集:購買計(jì)算機(jī)結(jié)果:10決策樹歸納的算法基本算法(貪心算法)樹構(gòu)建：自頂向下遞歸地分治方式開始，所有的訓(xùn)練樣本位于根節(jié)點(diǎn)屬性是分類屬性(若是連續(xù)值,事先離散化)基于選擇的屬性，樣本被遞歸地分割基于啟發(fā)式/統(tǒng)計(jì)測來選擇測試屬性(例如信息增益)終止劃分的條件一個(gè)給定節(jié)點(diǎn)的所有樣本屬于一個(gè)類別沒有屬性剩下，用于進(jìn)一步劃分–運(yùn)用多數(shù)投票來標(biāo)記此節(jié)點(diǎn)沒有樣本剩下13選擇具有最高信息增益的屬性令pi

為D中的任一元組屬于類Ci概率,估計(jì)為|Ci,D|/|D|分類D中元組需要的期望信息(entropy)

:

(利用A分裂D為v個(gè)部分后)分類D需要的信息為:以屬性A分枝得到的信息增益屬性選擇度量:信息增益(ID3/C4.5)14ClassP:買電腦=“yes”ClassN:買電腦=“no”屬性選擇:信息增益15計(jì)算信息增益-連續(xù)值屬性令A(yù)為連續(xù)屬性必須為A確定一個(gè)最佳分裂點(diǎn)

bestsplitpoint上升序排序A典型地,每對相鄰值的中點(diǎn)是一個(gè)可能的分裂點(diǎn)(ai+ai+1)/2isthemidpointbetweenthevaluesofaiandai+1具有最小期望信息需求的點(diǎn)選為A的分裂點(diǎn)Split:D1為D中元組滿足A≤split-point,D2是元組滿足A>split-point17GiniIndex指標(biāo)(CART)數(shù)據(jù)D包含n

類別的樣本,gini指標(biāo),gini(D)定義為

pj

類別

j在D中的頻率數(shù)據(jù)集D

基于屬性A分裂為子集

D1

和

D2,gini

指標(biāo)定義為不純度減少:具有最小ginisplit(D)的屬性(or不純度減少最大的)用于分裂節(jié)點(diǎn)(需要枚舉所有可能的分裂情況)18計(jì)算GiniIndex指標(biāo)D有9個(gè)元組買電腦=“yes”/5個(gè)買電腦=“no”設(shè)屬性income分裂D為包含10個(gè)元組的D1:{low,medium}/4個(gè)元組的D2Gini{low,high}=0.458;Gini{medium,high}=0.450.因此{(lán)low,medium}/{high}分裂，由于其有最小的Giniindex假設(shè)所有屬性都是連續(xù)值，需要其他技術(shù),e.g.,聚類,來獲得可能的分裂點(diǎn)19比較屬性選擇度量通常三種度量獲得較好的結(jié)果信息增益Informationgain:偏向于多值屬性增益率Gainratio:傾向于不平衡的分裂，其中一個(gè)子集比其他小得多Giniindex:偏向于多值屬性當(dāng)類數(shù)目較大時(shí)，計(jì)算困難傾向于導(dǎo)致大小相等的分區(qū)和純度21過擬合與數(shù)剪枝過擬合Overfitting:一棵歸納的樹

可能過分?jǐn)M合訓(xùn)練數(shù)據(jù)分枝太多,某些反映訓(xùn)練數(shù)據(jù)中的異常，噪音/孤立點(diǎn)對未參與訓(xùn)練的樣本的低精度預(yù)測兩種處理方法先剪枝:提前終止樹構(gòu)造如果對一個(gè)節(jié)點(diǎn)的分裂會產(chǎn)生低于給定的閾值的度量，劃分停止選擇一個(gè)合適的閾值很難后剪枝:從完全生長的樹中剪去樹枝—得到一個(gè)逐步修剪樹例如，最小化代價(jià)復(fù)雜度（樹節(jié)點(diǎn)個(gè)數(shù)和錯(cuò)誤率的函數(shù)）使用不同于訓(xùn)練集的數(shù)據(jù)來確定哪一個(gè)是“bestprunedtree”22決策樹歸納的增強(qiáng)允許連續(xù)值屬性動態(tài)地定義新的離散值屬性，其把連續(xù)值屬性分成離散的區(qū)間處理缺失屬性值分配屬性的最常見值為每一個(gè)可能的值分配概率屬性構(gòu)造基于現(xiàn)有的稀少出現(xiàn)的屬性創(chuàng)建新的屬性，這減少了分散，重復(fù)和復(fù)制23大型數(shù)據(jù)庫中分類分類—被統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)研究人員廣泛地研究一個(gè)經(jīng)典問題可伸縮性:以合理的速度分類由帶有數(shù)百個(gè)屬性的百萬個(gè)樣本組成的數(shù)據(jù)集為什么決策樹歸納受歡迎？相對快的訓(xùn)練速度(與其他分類方法相比)轉(zhuǎn)換為簡單、易于理解的分類規(guī)則可用SQL查詢來訪問數(shù)據(jù)庫與其它方法可比的分類精度RainForest(VLDB’98—Gehrke,Ramakrishnan&Ganti)BuildsanAVC-list(attribute,value,classlabel)25Rainforest:訓(xùn)練集和AVC集studentBuy_Computeryesnoyes61no34AgeBuy_Computeryesno<=302331..4040>4032CreditratingBuy_Computeryesnofair62excellent33AVC-setonincomeAVC-setonAgeAVC-setonStudentTrainingExamplesincomeBuy_Computeryesnohigh22medium42low31AVC-setoncredit_rating26BOAT(BootstrappedOptimisticAlgorithmforTreeConstruction)使用一個(gè)叫做

bootstrapping

自助法的統(tǒng)計(jì)技術(shù)多個(gè)更小的樣本集（子集）,每一個(gè)可放入內(nèi)存每個(gè)子集產(chǎn)生一個(gè)樹,導(dǎo)致多個(gè)樹

考察這些樹并用他們構(gòu)造一個(gè)新樹T’事實(shí)證明，T’

非常接近于使用全部數(shù)據(jù)集構(gòu)造的樹Adv:只要求掃描DB兩遍,并且是一個(gè)增量算法.29Chapter6.分類:貝葉斯分類分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummary30貝葉斯理論令X為數(shù)據(jù)樣本:類標(biāo)簽未知令H為一個(gè)假設(shè)在：X屬于類別C分類就是確定P(H|X)(后驗(yàn)概率),給定觀察數(shù)據(jù)X，假設(shè)H成立的概率P(H)(先驗(yàn)概率)——最初的概率例,不管年齡和收入等條件X將會購買計(jì)算機(jī)P(X):樣本數(shù)據(jù)x被觀察到的概率P(X|H)(可能性),假設(shè)H成立，那么觀測到樣本X的概率E.g.,已知X購買計(jì)算機(jī)，X為31..40且中等收入的概率31貝葉斯理論BayesianTheorem給定訓(xùn)練數(shù)據(jù)

X,假設(shè)H的后驗(yàn)概率

P(H|X滿足貝葉斯理論

通俗地說，這可以寫成 posteriori=likelihoodxprior/evidence預(yù)測X屬于類別C2當(dāng)且僅當(dāng)概率P(Ci|X)是所有P(Ck|X)forallthekclasses最大的實(shí)際困難:需要許多可能性的初步知識，計(jì)算成本顯著32Na?veBayesianClassifierD為訓(xùn)練數(shù)據(jù)集（包含類別標(biāo)簽）,并且每個(gè)元組表示為一個(gè)n-維的屬性向量X=(x1,x2,…,xn)假定有m

個(gè)類別C1,C2,…,Cm.分類就是推導(dǎo)最大的后驗(yàn)概率,i.e.,themaximalP(Ci|X)可以由貝葉斯理論計(jì)算由于對所有類P(X)是常量，只需要最大化33樸素貝葉斯分類器的推導(dǎo)一個(gè)簡單假定:屬性是條件獨(dú)立的(i.e.,屬性間沒有依賴關(guān)系):這樣極大地減少了計(jì)算代價(jià)：

只需要統(tǒng)計(jì)類的分布若Ak

是分類屬性P(xk|Ci)=Ci

類中Ak

取值為xk

的元組數(shù)/|Ci,D|(類Ci

的大小)若Ak

是連續(xù)值,P(xk|Ci)通常基于均值μ

標(biāo)準(zhǔn)差σ的高斯分布計(jì)算P(xk|Ci)=34樸素貝葉斯分類:訓(xùn)練數(shù)據(jù)集兩個(gè)類別:C1:buys_computer=‘yes’C2:buys_computer=‘no’數(shù)據(jù)樣本X=(age<=30,Income=medium,Student=yesCredit_rating=Fair)35Na?veBayesianClassifier:例子P(Ci):P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357ComputeP(X|Ci)foreachclassP(age=“<=30”|buys_computer=“yes”)=2/9=0.222P(age=“<=30”|buys_computer=“no”)=3/5=0.6P(income=“medium”|buys_computer=“yes”)=4/9=0.444P(income=“medium”|buys_computer=“no”)=2/5=0.4P(student=“yes”|buys_computer=“yes)=6/9=0.667P(student=“yes”|buys_computer=“no”)=1/5=0.2P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4X=(age<=30,income=medium,student=yes,credit_rating=fair)

P(X|Ci):P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.667=0.044P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028

P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007Therefore,Xbelongstoclass(“buys_computer=yes”)

36貝葉斯分類:Why?一個(gè)統(tǒng)計(jì)學(xué)分類器:執(zhí)行概率預(yù)測,i.e.,預(yù)測類成員的概率基礎(chǔ):

基于貝葉斯理論

Performance:

一個(gè)簡單的貝葉斯分類器,樸素貝葉斯分類器,可以與決策樹和經(jīng)過挑選的神經(jīng)網(wǎng)絡(luò)分類器相媲美增量:每次訓(xùn)練的樣本可以逐步增加/減少一個(gè)假設(shè)是正確的可能性——先驗(yàn)知識可與觀測數(shù)據(jù)相結(jié)合Standard:即使貝葉斯方法是難以計(jì)算的,最優(yōu)決策制定提供標(biāo)準(zhǔn)（其他方法可以衡量）37避免零概率問題樸素貝葉斯要求每個(gè)條件概率非零.然而,預(yù)測的概率可能為零

Ex.假定有1000元組,e=low(0),income=medium(990),andincome=high(10)UseLaplaciancorrection校準(zhǔn)

(orLaplacianestimator估計(jì)法)Adding1toeachcaseProb(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003校準(zhǔn)的“corrected”概率估計(jì)很接近未校準(zhǔn)的38Na?veBayesianClassifier:評論AdvantagesEasytoimplementGoodresultsobtainedinmostofthecasesDisadvantagesAssumption:類條件獨(dú)立性,損失精度實(shí)際中,變量間存在依賴E.g.,醫(yī)院：患者：簡介：年齡，家族病史等癥狀：發(fā)燒，咳嗽等疾?。悍伟悄虿〉?/p>

DependenciesamongthesecannotbemodeledbyNa?veBayesianClassifierHowtodealwiththesedependencies?BayesianBeliefNetworks39Chapter6.分類:基于規(guī)則的分類分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummary40使用IF-THEN規(guī)則分類使用

IF-THEN

規(guī)則表示知識R:IFage=youthANDstudent=yesTHENbuys_computer=yes規(guī)則前件/前提vs.規(guī)則結(jié)論評估規(guī)則:覆蓋率coverageand準(zhǔn)確率accuracy

ncovers=#規(guī)則R覆蓋的元組數(shù)%給定元組，規(guī)則的前提滿足—覆蓋元組ncorrect=#R正確分類的元組數(shù) coverage(R)=ncovers/|D|/%D:訓(xùn)練數(shù)據(jù)集 accuracy(R)=ncorrect/ncovers如果超過1條規(guī)則被觸發(fā),需要解決沖突規(guī)模序Sizeordering:最高優(yōu)先權(quán)賦予“最苛刻”的規(guī)則(即,最多屬性測試)基于類的序:每個(gè)類的錯(cuò)誤分類代價(jià)的下降序基于規(guī)則的序(決策表):根據(jù)一些規(guī)則的質(zhì)量度量或由專家建議，規(guī)則被組織成一個(gè)長的優(yōu)先級列表41age?student?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesnoExample:Ruleextractionfromourbuys_computerdecision-treeIFage=youngANDstudent=noTHENbuys_computer=noIFage=youngANDstudent=yesTHENbuys_computer=yesIFage=mid-age THENbuys_computer=yesIFage=oldANDcredit_rating=excellentTHENbuys_computer=noIFage=oldANDcredit_rating=fairTHENbuys_computer=yes從決策樹提取規(guī)則規(guī)則比一棵大的決策樹更容易理解從根到每個(gè)葉子的路徑產(chǎn)生一個(gè)規(guī)則沿路徑的每個(gè)屬性值對一起形成了一個(gè)聯(lián)合:葉節(jié)點(diǎn)形成規(guī)則后件

規(guī)則是互斥的和窮舉的沒有沖突規(guī)則，每個(gè)元組被覆蓋42順序覆蓋算法的規(guī)則歸納

順序覆蓋算法:直接從訓(xùn)練數(shù)據(jù)抽取規(guī)則典型的算法:FOIL,AQ,CN2,RIPPER規(guī)則被順序地學(xué)習(xí),類Ci的規(guī)則將盡量覆蓋Ci的元組，不或少覆蓋其他類的元組Steps:一次學(xué)習(xí)一個(gè)規(guī)則每學(xué)習(xí)一個(gè)規(guī)則，刪除此規(guī)則覆蓋的元組對剩下的元組重復(fù)該過程直到終止條件,e.g.,沒有訓(xùn)練樣本/返回的規(guī)則的質(zhì)量低于用戶給定的閾值與決策樹對照：

同時(shí)學(xué)習(xí)一組規(guī)則43順序覆蓋算法

while(enoughtargettuplesleft)

產(chǎn)生一個(gè)規(guī)則

刪除這個(gè)規(guī)則覆蓋的元組ExamplescoveredbyRule3ExamplescoveredbyRule2ExamplescoveredbyRule1Positiveexamples44RuleGenerationTogeneratearulewhile(true)

找到最好的謂詞p

if

規(guī)則質(zhì)量度量(p)>thresholdthenaddptocurrentrule

elsebreakPositiveexamplesNegativeexamplesA3=1A3=1&&A1=2A3=1&&A1=2&&A8=5如何學(xué)習(xí)一個(gè)規(guī)則?從可能的最一般的規(guī)則開始:condition=empty采用貪心的深度優(yōu)先策略添加新屬性（于規(guī)則中）選擇對“規(guī)則質(zhì)量”提高最大的那個(gè)屬性47規(guī)則質(zhì)量度量與剪枝規(guī)則質(zhì)量度量:同時(shí)考慮覆蓋率和準(zhǔn)確率Foil-gain(inFOIL&RIPPER):評價(jià)擴(kuò)展條件的info_gain偏向于具有高準(zhǔn)確率并覆蓋許多正元組的規(guī)則正用于學(xué)習(xí)規(guī)則的類的元組—正元組；其余為負(fù)元組

Pos(neg):規(guī)則覆蓋的正（負(fù)）元組數(shù)基于一個(gè)獨(dú)立的測試集進(jìn)行規(guī)則剪枝（即刪除一個(gè)屬性測試）Pos/negare#被R覆蓋的正/負(fù)元組.If規(guī)則R剪枝后FOIL_Prune

較高,那么剪枝R48Chapter6.分類:模型評價(jià)與選擇分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummary模型評價(jià)與選擇評價(jià)指標(biāo):怎樣度量準(zhǔn)確率?考慮其他指標(biāo)??使用測試集（帶標(biāo)簽）代替訓(xùn)練集評估準(zhǔn)確度估計(jì)分類器準(zhǔn)確率的方法:Holdoutmethod,randomsubsampling交叉驗(yàn)證Cross-validation自助法（解靴帶）BootstrapComparingclassifiers:置信區(qū)間Confidenceintervals代價(jià)效益分析和ROC曲線Cost-benefitanalysisandROCCurves49分類器評價(jià)指標(biāo):混淆矩陣Actualclass\Predictedclassbuy_computer=yesbuy_computer=noTotalbuy_computer=yes6954467000buy_computer=no41225883000Total7366263410000感興趣的類定為“正類”或“陽性類”，對應(yīng)的為“負(fù)/陰性類”正樣本/負(fù)樣本

給定m

個(gè)類,CMi,j

表示#類i的樣本被分類器分到類別j的個(gè)數(shù)可以提供額外的行/列提供“合計(jì)”和“識別率”混淆矩陣ConfusionMatrix:Actualclass\PredictedclassC1?C1C1TruePositives(TP)FalseNegatives(FN)?C1FalsePositives(FP)TrueNegatives(TN)例子:50分類器評價(jià)指標(biāo):準(zhǔn)確度,誤差率,靈敏性Sensitivity,特效性Specificity分類器準(zhǔn)確度,or識別率:測試元組被正確識別的比例Accuracy=(TP+TN)/All誤差率:

1–

accuracy,orErrorrate=(FP+FN)/AllClassImbalanceProblem類分布不平衡問題:Oneclassmayberare,e.g.fraud,orHIV-positiveSensitivity:TruePositiverecognitionrateSensitivity=TP/PSpecificity:TrueNegativerecognitionrateSpecificity=TN/NA\PC?CCTPFNP?CFPTNNP’N’All51分類器評價(jià)指標(biāo):

PrecisionandRecall,andF-measuresPrecision:正確–被分類器標(biāo)記為正類的樣本中實(shí)際上屬于“正類”的比例Recall:completeness完全–what%ofpositivetuplesdidtheclassifierlabelaspositive?Perfectscoreis1.0精度和召回率逆關(guān)系Fmeasure(F1

or

F-score):精度和召回的調(diào)和平均值,F?:精確度和召回率的加權(quán)量assigns?timesasmuchweighttorecallastoprecision52分類器評價(jià)指標(biāo):例子53Precision=90/230=39.13%Recall=90/300=30.00%真實(shí)類\預(yù)測類cancer=yescancer=noTotalRecognition(%)cancer=yes9021030030.00(sensitivitycancer=no1409560970098.56(specificity)Total23097701000096.40(accuracy)評測分類器的正確率:

Holdout&Cross-ValidationMethodsHoldoutmethod給定數(shù)據(jù)隨機(jī)分成兩個(gè)部分訓(xùn)練集(e.g.,2/3)用于模型構(gòu)造測試集(e.g.,1/3)用于正確率估計(jì)隨機(jī)抽樣:avariationofholdout重復(fù)holdoutk次,accuracy=所有正確率的平均值Cross-validation(k-fold,k=10最常用)隨機(jī)分割數(shù)據(jù)為k

互不相交的子集,每一個(gè)大小近似相等在i-th迭代中,使用Di為測試集其他的為訓(xùn)練集留一法:kfoldswherek=#oftuples,forsmallsizeddata*Stratifiedcross-validation*:每個(gè)部分分層使得每個(gè)子集中類分布近似于原始數(shù)據(jù)54評測分類器的正確率:BootstrapBootstrap對于小樣本數(shù)據(jù)，效果很好從給定樣本中又放回的均勻抽樣withreplacementi.e.,每次一個(gè)樣本被選中,把它加入訓(xùn)練集并且等可能得被再次選中多個(gè)自助法,最常用的是

.632boostrap含d

個(gè)樣本的數(shù)據(jù)集有放回抽樣d

次,產(chǎn)生d個(gè)樣本的訓(xùn)練集.沒有被抽到的樣本組成測試集.大約63.2%的樣本被抽中，剩余的36.8%形成測試集(因?yàn)?1–1/d)d≈e-1=0.368)重復(fù)抽樣過程k

次,總體準(zhǔn)確率為:55估計(jì)置信區(qū)間:分類器M1vs.M2假定有連個(gè)分類器M1andM2,那一個(gè)更好?用10-foldcross-validation獲得了這些平均誤差率僅僅是未來數(shù)據(jù)總體誤差的一種估計(jì)2個(gè)錯(cuò)誤率之間差別如果是否是偶然的？使用統(tǒng)計(jì)顯著性檢驗(yàn)

獲得估計(jì)誤差的confidencelimits置信界56估計(jì)置信區(qū)間:NullHypothesis執(zhí)行10-foldcross-validation假定樣本服從k–1個(gè)自由度的tdistribution(k=10)degreesoffreedomUset-test(orStudent’st-test)零假設(shè)NullHypothesis:M1&M2

相同（即沒有區(qū)別）如果可以拒絕nullhypothesis,那么可以斷定M1&M2

間的不同是統(tǒng)計(jì)上顯著的Chosemodelwithlowererrorrate57估計(jì)置信區(qū)間:t-test當(dāng)只有一個(gè)測試集時(shí):成對比較pairwisecomparison對于10倍交叉驗(yàn)證中的ithround,使用相同的樣本分割來計(jì)算err(M1)i

anderr(M2)i然后球平均over10t-testcomputest-statisticwithk-1

degreesoffreedom:如果有連個(gè)測試集:usenon-pairedt-test其中andwherewherek1&k2are#ofcross-validationsamplesusedforM1&M2,resp.58估計(jì)置信區(qū)間:Tablefort-distributionSymmetricSignificancelevel,e.g.,sig=0.05or5%meansM1&M2aresignificantlydifferentfor95%ofpopulationConfidencelimit,z=sig/259估計(jì)置信區(qū)間:StatisticalSignificanceM1&M2

是否顯著得不同?Computet.Selectsignificancelevel(e.g.sig=5%)Consulttablefort-distribution:Findtvaluecorrespondingtok-1degreesoffreedom(here,9)t-分布對稱:通常顯示分布的上百分點(diǎn)%→查找值confidencelimit

z=sig/2(here,0.025)If

t>zort<-z,那么t的值位于拒絕域:RejectnullhypothesisthatmeanerrorratesofM1&M2aresameConclude:statisticallysignificantdifferencebetweenM1&M2

Otherwise,concludethatanydifferenceischance60模型選擇:ROCCurvesROC(ReceiverOperatingCharacteristics)curves:圖形比較分類模型源于信號檢測理論truepositiverate和falsepositiverate間的折衷ROC曲線下的面積就是模型正確率的度量測試元組遞減序排列:最可能屬于正類的排在最頂端Theclosertothediagonalline(i.e.,theclosertheareaisto0.5),thelessaccurateisthemodel垂直坐標(biāo)表示thetruepositiverate水平坐標(biāo)表示thefalsepositiverate同時(shí)顯示對角線Amodelwithperfectaccuracywillhaveanareaof1.06162Chapter6.分類:集成方法分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummary集成方法:IncreasingtheAccuracy集成方法Ensemblemethods使用多個(gè)模型的組合來提高accuracy組合多個(gè)學(xué)習(xí)的模型,M1,M2,…,Mk,來獲得一個(gè)提高的模型M*Popularensemblemethods裝袋Bagging:多個(gè)分類器的結(jié)果進(jìn)行多數(shù)表決提升Boosting:多個(gè)分類器的結(jié)果權(quán)重投票集成Ensemble:combiningasetofheterogeneousclassifiers63裝袋Bagging訓(xùn)練給定包含d個(gè)元組的數(shù)據(jù)D,在第i次迭代，從D中有放回抽取d個(gè)樣本組成訓(xùn)練集Di(i.e.,bootstrap)，從Di

學(xué)習(xí)一個(gè)分類器Mi

分類:分類一個(gè)未知樣本X

每個(gè)分類器Mi

給出預(yù)測結(jié)果裝袋分類器M*計(jì)算投票，把得票最多的類分配給X預(yù)測:每個(gè)分類器預(yù)測的值的平均值正確性Accuracy常常優(yōu)于D上單個(gè)分類器的正確率對噪音數(shù)據(jù):不會很差，更健壯Provedimprovedaccuracyinprediction64提升Boosting類比:咨詢幾個(gè)醫(yī)生，在原來的診斷準(zhǔn)確性的基礎(chǔ)上分配權(quán)重，加權(quán)診斷的組合為結(jié)果Boosting如何工作?Weights分配給每個(gè)訓(xùn)練樣本迭代學(xué)習(xí)一系列分類器學(xué)習(xí)Mi

后,權(quán)重更新使得，后續(xù)得分類器Mi+1更關(guān)注于Mi錯(cuò)誤分類的訓(xùn)練樣本最后的分類器M*組合了每個(gè)獨(dú)立分類器的投票,其中每個(gè)分類器的權(quán)重勢其正確率的函數(shù)可以擴(kuò)充Boosting算法用于數(shù)值預(yù)測與bagging比較:Boosting傾向于得到更高的準(zhǔn)確率,但有過擬合錯(cuò)誤分類數(shù)據(jù)的風(fēng)險(xiǎn)6566Adaboost(FreundandSchapire,1997)數(shù)據(jù)集含dclass-labeled元組,(X1,y1),…,(Xd,yd)最初,每個(gè)元組的權(quán)重為1/d在k輪中產(chǎn)生kclassifiers.在第i輪,從D有放回抽取訓(xùn)練集Di

（大小相等每個(gè)元組被選中的概率基于其權(quán)重分類模型Mi

學(xué)習(xí)自Di使用Di為測試集計(jì)算誤差率如果一個(gè)元組被錯(cuò)分,權(quán)重增加,o.w.否則下降誤差率:err(Xj)為錯(cuò)誤分類元組Xj誤差，分類器Mi

誤差率是元組錯(cuò)誤分類的權(quán)重和:分類器Mi投票權(quán)重為隨機(jī)森林RandomForest(Breiman2001)RandomForest:每個(gè)分類器為decisiontree，在每個(gè)結(jié)點(diǎn)上使用隨機(jī)選出的屬性來分裂產(chǎn)生判定樹分類時(shí),每棵樹投票得票最多的類返回結(jié)果兩種構(gòu)造方法:Forest-RI(randominputselection):每個(gè)結(jié)點(diǎn)隨機(jī)選F個(gè)屬性為分裂的候選.用CART方法產(chǎn)生最大尺寸的樹Forest-RC(randomlinearcombinations):

以現(xiàn)有屬性的線性組合來產(chǎn)生新屬性(降低了單個(gè)分類器間的相關(guān)性)準(zhǔn)確率比得上Adaboost,對誤差和孤立點(diǎn)更穩(wěn)健每次分裂時(shí)對選出的候選屬性數(shù)目不敏感，fasterthanbaggingorboosting67分類類別不平衡數(shù)據(jù)集類別不平衡問題.傳統(tǒng)的方法假定平衡的類別分布和相等的錯(cuò)誤代價(jià):不適合二元分類中典型的方法處理不平衡數(shù)據(jù):過采樣Oversampling:對正類數(shù)據(jù)過/多采樣Under-sampling:隨機(jī)減少負(fù)類的樣本閾值-移動Threshold-moving:移動判定閾值t,使得少數(shù)類元組更容易識別,減少（昂貴的）假陰性錯(cuò)誤的機(jī)會集成技術(shù):Stilldifficultforclassimbalanceproblemonmulticlasstasks6869預(yù)測誤差的度量度量預(yù)測準(zhǔn)確率:度量預(yù)測值與真實(shí)值的距離損失函數(shù):度量yi

和預(yù)測值yi’間的誤差絕對誤差A(yù)bsoluteerror:|yi–yi’|平方誤差Squarederror:(yi–yi’)2

檢驗(yàn)誤差(泛化誤差generalizationerror):平均絕對誤差:均方誤差Meansquarederror:Relativeabsoluteerror:Relativesquarederror:均方誤差夸大了離群點(diǎn)Popularlyuse(square)rootmean-squareerror,similarly,rootrelativesquarederror70WhatIsPrediction?(Numerical)預(yù)測類似于分類構(gòu)建一個(gè)模型利用模型來估計(jì)給定輸入的連續(xù)或排序的值與分類的不同分類是預(yù)測類別標(biāo)簽預(yù)測是模型連續(xù)值函數(shù)Majormethodforprediction:regression模型一個(gè)或多個(gè)預(yù)測變量和相應(yīng)變量間的關(guān)系Regressionanalysis線性和多元回歸非線性回歸其他方法:generalizedlinearmodel,Poissonregression,log-linearmodels,regressiontrees71線性回歸

Linearregression:包含一個(gè)響應(yīng)變量y和一個(gè)預(yù)測變量xy=w0+w1xMethodofleastsquares:estimatesthebest-fittingstraightline多元線性回歸:包含多個(gè)預(yù)測變量Trainingdataisoftheform(X1,y1),(X2,y2),…,(X|D|,y|D|)對2-D數(shù)據(jù),有y=w0+w1x1+w2x2通常用統(tǒng)計(jì)軟件包求解SAS,S-Plus多個(gè)非線性函數(shù)可以表示成上面這種形式72某些非線性模型可以用多項(xiàng)式函數(shù)多項(xiàng)式回歸模型可以變換為線性回歸模型.例如y=w0+w1x+w2x2+w3x3借助新變量:x2=x2,x3=x3y=w0+w1x+w2x2+w3x3其他函數(shù),如冪函數(shù),也可以轉(zhuǎn)化為線性函數(shù)Somemodelsareintractablenonlinear(e.g.,指數(shù)相求和)可能通過更復(fù)雜的公式綜合計(jì)算，得到最小二乘估計(jì)非線性回歸

08二月2023DataMining:ConceptsandTechniques73Generalizedlinearmodel:FoundationonwhichlinearregressioncanbeappliedtomodelingcategoricalresponsevariablesVarianceofyisafunctionofthemeanvalueofy,notaconstantLogisticregression:modelstheprob.ofsomeeventoccurringasalinearfunctionofasetofpredictorvariablesPoissonregression:modelsthedatathatexhibitaPoissondistributionLog-linearmodels:(forcategoricaldata)Approximatediscretemultidimensionalprob.distributionsAlsousefulfordatacompressionandsmoothingRegressiontreesandmodeltreesTreestopredictcontinuousvaluesratherthanclasslabelsOtherRegression-BasedModels74RegressionTreesandModelTreesRegressiontree:proposedinCARTsystem(Breimanetal.1984)CART:ClassificationAndRegressionTreesEachleafstoresacontinuous-valuedpredictionItistheaveragevalueofthepredictedattributeforthetrainingtuplesthatreachtheleafModeltree:proposedbyQuinlan(1992)Eachleafholdsaregressionmodel—amultivariatelinearequationforthepredictedattributeAmoregeneralcasethanregressiontreeRegressionandmodeltreestendtobemoreaccuratethanlinearregressionwhenthedataarenotrepresentedwellbyasimplelinearmodel75Prediction:NumericalData76Prediction:CategoricalData77Chapter6.分類:基本概念分類:基本概念決策樹歸納貝葉斯分類基于規(guī)則的分類模型評價(jià)與選擇提高分類準(zhǔn)確率的技術(shù):集成方法EnsembleMethodsSummarySummary(I)Classificationisaformofdataanalysisthatextractsmodelsdescribingimportantdataclasses.Effectiveandscalablemethodshavebeendevelopedfordecisiontreeinduction,NaiveBayesianclassification,rule-basedclassification,andmanyotherclassificationmethods.Evaluationmetricsinclude:accuracy,sensitivity,specificity,precision,recall,Fmeasure,andF?

measure.Stratifiedk-foldcross-validationisrecommendedforaccuracyestimation.Baggingandboostingcanbeusedtoincreaseoverallaccuracybylearningandcombiningaseriesofindividualmodels.78Summary(II)SignificancetestsandROCcurvesareusefulformodelselection.Therehavebeennumerouscomparisonsofthedifferentclassificationmethods;thematterremainsaresearchtopicNosinglemethodhasbeenfoundtobesuperioroverallothersforalldatasetsIssuessuchasaccuracy,trainingtime,robustness,scalability,andinterpretabilitymustbeconsideredandcaninvolvetrade-offs,furthercomplicatingthequestforanoverallsuperiormethod79References(1)C.ApteandS.Weiss.Dataminingwithdecisiontreesanddecisionrules.FutureGenerationComputerSystems,13,1997C.M.Bishop,NeuralNetworksforPatternRecognition.OxfordUniversityPress,1995L.Breiman,J.Friedman,R.Olshen,andC.Stone.ClassificationandRegressionTrees.WadsworthInternationalGroup,1984C.J.C.Burges.ATutorialonSupportVectorMachinesforPatternRecognition.DataMiningandKnowledgeDiscovery,2(2):121-168,1998P.K.ChanandS.J.Stolfo.Learningarbiterandcombinertreesfrompartitioneddataforscalingmachinelearning.KDD'95H.Cheng,X.Yan,J.Han,andC.-W.Hsu,DiscriminativeFrequentPatternAnalysisforEffectiveClassification,ICDE'07H.Cheng,X.Yan,J.Han,andP.S.Yu,DirectDiscriminativePatternMiningforEffectiveClassification,ICDE'08W.Cohen.Fasteffectiveruleinduction.ICML'95G.Cong,K.-L.Tan,A.K.H.Tung,andX.Xu.Miningtop-kcoveringrulegroupsforgeneexpressiondata.SIGMOD'0580References(2)A.J.Dobson.AnIntroductiontoGeneralizedLinearModels.Chapman&Hall,1990.G.DongandJ.Li.Efficientminingofemergingpatterns:Discoveringtrendsanddifferences.KDD'99.R.O.Duda,P.E.Hart,andD.G.Stork.PatternClassification,2ed.JohnWiley,2001U.M.Fayyad.Branchingonattributevaluesindecisiontreegeneration.AAAI’94.Y.FreundandR.E.Schapire.Adecision-theoreticgeneralizationofon-linelearningandanapplicationtoboosting.J.ComputerandSystemSciences,1997.J.Gehrke,R.Ramakrishnan,andV.Ganti.Rainforest:Aframeworkforfastdecisiontreeconstructionoflargedatasets.VLDB’98.J.Gehrke,V.Gant,R.Ramakrishnan,andW.-Y.Loh,BOAT--OptimisticDecisionTreeConstruction.SIGMOD'99.T.Hastie,R.Tibshirani,andJ.Friedman.TheElementsofStatisticalLearning:DataMining,Inference,andPrediction.Springer-Verlag,2001.D.Heckerman,D.Geiger,andD.M.Chickering.LearningBayesiannetworks:Thecombinationofknowledgeandstatisticaldata.MachineLearning,1995.W.Li,J.Han,andJ.Pei,CMAR:AccurateandEfficientClassificationBasedonMultipleClass-AssociationRules,ICDM'01.81References(3)T.-S.Lim,W.-Y.Loh,andY.-S.Shih.Acomparisonofpredictionaccuracy,complexity,andtrainingtimeofthirty-threeoldandnewclassificationalgorithms.MachineLearning,2000.J.Magidson.TheChaidapproachtosegmentationmodeling:Chi-squaredautomaticinteractiondetection.InR.P.Bagozzi,editor,AdvancedMethodsofMarketingResearch,BlackwellBusiness,1994.M.Mehta,R.Agrawal,andJ.Rissanen.SLIQ:Afastscalableclassifierfordatamining.EDBT'96.T.M.Mitchell.MachineLe