【文章內(nèi)容簡(jiǎn)介】 斯分類器 , 樸素貝葉斯分類器 , 可以與決策樹(shù)和經(jīng)過(guò)挑選的神經(jīng)網(wǎng)絡(luò)分類器相媲美 ? 增量 :每次訓(xùn)練的樣本可以逐步增加 /減少一個(gè)假設(shè)是正確的可能性 ——先驗(yàn)知識(shí)可與觀測(cè)數(shù)據(jù)相結(jié)合 ? Standard:即使貝葉斯方法是難以計(jì)算的 , 最優(yōu)決策制定提供標(biāo)準(zhǔn)（其他方法可以衡量） 37 避免零概率問(wèn)題 ? 樸素貝葉斯要求每個(gè)條件概率非零 . 然而 ,預(yù)測(cè)的概率可能為零 ? Ex. 假定有 1000 元組 , e=low (0), ine= medium (990), and ine = high (10) ? Use Laplacian correction校準(zhǔn) (or Laplacian estimator估計(jì)法 ) ? Adding 1 to each case Prob(ine = low) = 1/1003 Prob(ine = medium) = 991/1003 Prob(ine = high) = 11/1003 ? 校準(zhǔn)的 “ corrected” 概率估計(jì)很接近未校準(zhǔn)的 ???nkC ix kPC iXP1)|()|(38 Na239。ve Bayesian Classifier:評(píng)論 ? Advantages ? Easy to implement ? Good results obtained in most of the cases ? Disadvantages ? Assumption: 類條件獨(dú)立性 , 損失精度 ? 實(shí)際中 , 變量間存在依賴 ? .,醫(yī)院：患者：簡(jiǎn)介：年齡，家族病史等 癥狀：發(fā)燒，咳嗽等疾?。悍伟?，糖尿病等 ? Dependencies among these cannot be modeled by Na239。ve Bayesian Classifier ? How to deal with these dependencies? Bayesian Belief Networks 39 Chapter 6. 分類 :基于規(guī)則的分類 ? 分類 : 基本概念 ? 決策樹(shù)歸納 ? 貝葉斯分類 ? 基于規(guī)則的分類 ? 模型評(píng)價(jià)與選擇 ? 提高分類準(zhǔn)確率的技術(shù) :集成方法 Ensemble Methods ? Summary 40 使用 IFTHEN 規(guī)則分類 ? 使用 IFTHEN 規(guī)則表示知識(shí) R: IF age = youth AND student = yes THEN buys_puter = yes ? 規(guī)則前件 /前提 vs. 規(guī)則結(jié)論 ? 評(píng)估規(guī)則 : 覆蓋率 coverage and 準(zhǔn)確率 accuracy ? ncovers = 規(guī)則 R覆蓋 的元組數(shù) % 給定元組，規(guī)則的前提滿足 —覆蓋元組 ? ncorrect = R正確分類的元組數(shù) coverage(R) = ncovers /|D| /%D: 訓(xùn)練數(shù)據(jù)集 accuracy(R) = ncorrect / ncovers ? 如果超過(guò) 1條規(guī)則被觸發(fā) ,需要 解決沖突 ? 規(guī)模序 Size ordering: 最高優(yōu)先權(quán)賦予 “最苛刻”的規(guī)則 (即 , 最多屬性測(cè)試 ) ? 基于類的序 :每個(gè)類的錯(cuò)誤分類代價(jià)的下降序 ? 基于規(guī)則的序 (決策表 ):根據(jù)一些規(guī)則的質(zhì)量度量或由專家建議，規(guī)則被組織成一個(gè)長(zhǎng)的優(yōu)先級(jí)列表 41 age? student? credit rating? =30 40 no yes yes yes 31..40 fair excellent yes no ? Example: Rule extraction from our buys_puter decisiontree IF age = young AND student = no THEN buys_puter = no IF age = young AND student = yes THEN buys_puter = yes IF age = midage THEN buys_puter = yes IF age = old AND credit_rating = excellent THEN buys_puter = no IF age = old AND credit_rating = fair THEN buys_puter = yes 從決策樹(shù)提取規(guī)則 ? 規(guī)則比一棵大的決策樹(shù)更容易理解 ? 從根到每個(gè)葉子的路徑產(chǎn)生一個(gè)規(guī)則 ? 沿路徑的每個(gè)屬性值對(duì)一起形成了一個(gè)聯(lián)合 : 葉節(jié)點(diǎn)形成規(guī)則后件 ? 規(guī)則是 互斥的 和 窮舉的 ? 沒(méi)有沖突規(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ī)則覆蓋的元組 ? 對(duì)剩下的元組重復(fù)該過(guò)程直到終止條件 , ., 沒(méi)有訓(xùn)練樣本 /返回的規(guī)則的質(zhì)量低于用戶給定的閾值 ? 與決策樹(shù)對(duì)照： 同時(shí)學(xué)習(xí)一組規(guī)則 43 順序覆蓋算法 while (enough target tuples left) 產(chǎn)生一個(gè)規(guī)則 刪除這個(gè)規(guī)則覆蓋的元組 Examples covered by Rule 3 Examples covered by Rule 2 Examples covered by Rule 1 Positive examples 44 Rule Generation ? To generate a rule while(true) 找到最好的謂詞 p if 規(guī)則質(zhì)量度量 (p) threshold then add p to current rule else break Positive examples Negative examples A3=1 A3=1amp。amp。A1=2 A3=1amp。amp。A1=2 amp。amp。A8=5 如何學(xué)習(xí)一個(gè)規(guī)則 ? ? 從可能的最一般的規(guī)則開(kāi)始 : condition = empty ? 采用貪心的深度優(yōu)先策略添加新屬性（于規(guī)則中） ? 選擇對(duì)“規(guī)則質(zhì)量” 提高最大的那個(gè)屬性 47 規(guī)則質(zhì)量度量與剪枝 ? 規(guī)則質(zhì)量度量 : 同時(shí)考慮 覆蓋率和準(zhǔn)確率 ? Foilgain (in FOIL amp。 RIPPER): 評(píng)價(jià)擴(kuò)展條件的 info_gain ? 偏向于具有高準(zhǔn)確率并覆蓋許多正元組的規(guī)則 ? 正用于學(xué)習(xí)規(guī)則的類的元組 —正元組 ；其余為 負(fù)元組 ? Pos(neg):規(guī)則覆蓋的正（負(fù)）元組數(shù) ? 基于一個(gè)獨(dú)立的測(cè)試集進(jìn)行規(guī)則剪枝（即刪除一個(gè)屬性測(cè)試） Pos/neg are 被 R覆蓋的正 /負(fù)元組 . If 規(guī)則 R 剪枝后 FOIL_Prune 較高 , 那么剪枝 R )l og39。39。 39。(l og39。_ 22 ne gpos posne gpos posposG ai nF O IL ?????ne gposne gposRP r un eF O IL???)(_48 Chapter 6. 分類 :模型評(píng)價(jià)與選擇 ? 分類 : 基本概念 ? 決策樹(shù)歸納 ? 貝葉斯分類 ? 基于規(guī)則的分類 ? 模型評(píng)價(jià)與選擇 ? 提高分類準(zhǔn)確率的技術(shù) :集成方法 Ensemble Methods ? Summary 模型評(píng)價(jià)與選擇 ? 評(píng)價(jià)指標(biāo) : 怎樣度量準(zhǔn)確率 ?考慮其他指標(biāo) ?? ? 使用測(cè)試集（帶標(biāo)簽）代替訓(xùn)練集評(píng)估準(zhǔn)確度 ? 估計(jì)分類器準(zhǔn)確率的方法 : ? Holdout method, random subsampling ? 交叉驗(yàn)證 Crossvalidation ? 自助法（解靴帶） Bootstrap ? Comparing classifiers: ? 置信區(qū)間 Confidence intervals ? 代價(jià)效益分析和 ROC曲線 ? Costbenefit analysis and ROC Curves 49 分類器評(píng)價(jià)指標(biāo) : 混淆矩陣 Actual class\Predicted class buy_puter = yes buy_puter = no Total buy_puter = yes 6954 46 7000 buy_puter = no 412 2588 3000 Total 7366 2634 10000 ? 感興趣的類定為“ 正類 ” 或“ 陽(yáng)性類 ”，對(duì)應(yīng)的為“ 負(fù) /陰性類 ” ? 正樣本 /負(fù)樣本 ? 給定 m 個(gè)類 , CMi,j 表示 類 i的樣本被分類器分到類別 j 的個(gè)數(shù) ? 可以提供額外的行 /列提供“合計(jì)”和“識(shí)別率” 混淆矩陣 Confusion Matrix: Actual class\Predicted class C1 172。 C1 C1 True Positives (TP) False Negatives (FN) 172。 C1 False Positives (FP) True Negatives (TN) 例子 : 50 分類器評(píng)價(jià)指標(biāo) : 準(zhǔn)確度 , 誤差率 , 靈敏性Sensitivity, 特效性 Specificity ? 分類器準(zhǔn)確度 , or 識(shí)別率 : 測(cè)試元組被正確識(shí)別的比例 Accuracy = (TP + TN)/All ? 誤差率 : 1 – accuracy, or Error rate = (FP + FN)/All ? Class Imbalance Problem類分布不平衡問(wèn)題 : ? One class may be rare, . fraud, or HIVpositive ? Sensitivity: True Positive recognition rate ? Sensitivity = TP/P ? Specificity: True Negative recognition rate ? Specificity = TN/N A\P C 172。C C TP FN P 172。C FP TN N P’ N’ All 51 分類器評(píng)價(jià)指標(biāo) : Precision and Recall, and Fmeasures ? Precision: 正確 – 被分類器標(biāo)記為正類的樣本中實(shí)際上屬于“正類”的比例 ? Recall: pleteness完全 – what % of positive tuples did the classifier label as positive? ? Perfect score is ? 精度和召回率逆關(guān)系 ? F measure (F1 or Fscore):精度和召回的調(diào)和平均值 , ? F223。:精確度和召回率的加權(quán)量 ? assigns 223。 times as much weight to recall as to precision 52 分類器評(píng)價(jià)指標(biāo) : 例子 53 ? Precision = 90/230 = % Recall = 90/300 = % 真實(shí)類 \預(yù)測(cè)類 cancer = yes cancer = no Total Recognition(%) cancer = yes 90 210 300 (sensitivity cancer = no 140 9560 9700 (specificity) Total 230 9770 10000 (accuracy) 評(píng)測(cè)分類器的正確率 : Holdout amp。 CrossValidation Methods ? Holdout method ? 給定數(shù)據(jù)隨機(jī)分成兩個(gè)部分 ? 訓(xùn)練集 (., 2/3) 用于模型構(gòu)造 ? 測(cè)試集 (., 1/3) 用于正確率估計(jì) ? 隨機(jī)抽樣 : a variation of holdout ? 重復(fù) holdout k次 , accuracy = 所有正確率的平均值 ? Crossvalidation (kfold, k = 10 最常用 ) ? 隨機(jī)分割數(shù)據(jù)為 k 互不相交的子集 , 每一個(gè)大小近似相等 ? 在 ith 迭代中 , 使用 Di 為測(cè)試集其他的為訓(xùn)練集 ? 留一法 : k folds where k = of tuples, for small sized data ? *Stratified crossvalidation*:每個(gè)部分分層使得每個(gè)子集中類分布近似于原始數(shù)據(jù) 54 評(píng)測(cè)分類器的正確率 : Bootstrap ? Bootstrap ? 對(duì)于小