基本概念、決策樹與模型評價(ppt 92頁).ppt

數(shù)據(jù)挖掘分類 基本概念 決策樹與模型評價 第4章分類 基本概念 決策樹與模型評價 分類的是利用一個分類函數(shù) 分類模型 分類器 該模型能把數(shù)據(jù)庫中的數(shù)據(jù)影射到給定類別中的一個 分類 訓(xùn)練集 數(shù)據(jù)庫中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集 訓(xùn)練集中的單個元組稱為訓(xùn)練樣本 每個訓(xùn)練樣本有一個類別標(biāo)記 一個具體樣本的形式可為 v1 v2 vn c 其中vi表示屬性值 c表示類別 測試集 用于評估分類模型的準(zhǔn)確率 數(shù)據(jù)分類 一個兩步過程 1 第一步 建立一個模型 描述預(yù)定數(shù)據(jù)類集和概念集假定每個元組屬于一個預(yù)定義的類 由一個類標(biāo)號屬性確定學(xué)習(xí)模型可以用分類規(guī)則 決策樹或數(shù)學(xué)公式的形式提供 數(shù)據(jù)分類 一個兩步過程 2 第二步 使用模型 對將來的或未知的對象進(jìn)行分類首先評估模型的預(yù)測準(zhǔn)確率對每個測試樣本 將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比較模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比測試集要獨(dú)立于訓(xùn)練樣本集 否則會出現(xiàn) 過分適應(yīng)數(shù)據(jù) 的情況如果準(zhǔn)確性能被接受 則分類規(guī)則就可用來對新數(shù)據(jù)進(jìn)行分類 有監(jiān)督的學(xué)習(xí)VS 無監(jiān)督的學(xué)習(xí) 有監(jiān)督的學(xué)習(xí) 用于分類 模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的 監(jiān)督 下進(jìn)行新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類無監(jiān)督的學(xué)習(xí) 用于聚類 每個訓(xùn)練樣本的類編號是未知的 要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的通過一系列的度量 觀察來建立數(shù)據(jù)中的類編號或進(jìn)行聚類 分類模型的構(gòu)造方法 1 機(jī)器學(xué)習(xí)方法 決策樹法規(guī)則歸納2 統(tǒng)計(jì)方法 知識表示是判別函數(shù)和原型事例貝葉斯法非參數(shù)法 近鄰學(xué)習(xí)或基于事例的學(xué)習(xí) 3 神經(jīng)網(wǎng)絡(luò)方法 BP算法 模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型4 粗糙集 roughset 知識表示是產(chǎn)生式規(guī)則 一個決策樹的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 訓(xùn)練數(shù)據(jù) 模型 決策樹 決策樹的另一個例子 categorical categorical continuous class MarSt Refund TaxInc YES NO NO Yes No Married Single Divorced 80K 80K 用決策樹歸納分類 什么是決策樹 類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試每個分枝代表一個測試輸出每個樹葉節(jié)點(diǎn)代表類或類分布決策樹的生成由兩個階段組成決策樹構(gòu)建開始時 所有的訓(xùn)練樣本都在根節(jié)點(diǎn)遞歸的通過選定的屬性 來劃分樣本 必須是離散值 樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn) 樹剪枝試圖檢測和剪去這種分枝決策樹的使用 對未知樣本進(jìn)行分類通過將樣本的屬性值與決策樹相比較 為了對未知數(shù)據(jù)對象進(jìn)行分類識別 可以根據(jù)決策樹的結(jié)構(gòu)對數(shù)據(jù)集中的屬性進(jìn)行測試 從決策樹的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就形成了相應(yīng)對象的類別測試 決策樹可以很容易轉(zhuǎn)換為分類規(guī)則 決策樹分類任務(wù) DecisionTree 一個決策樹的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 訓(xùn)練數(shù)據(jù) 模型 決策樹 應(yīng)用決策樹進(jìn)行分類 測試數(shù)據(jù) Startfromtherootoftree 應(yīng)用決策樹進(jìn)行分類 測試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 測試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 測試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 測試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 測試數(shù)據(jù) AssignCheatto No 決策樹分類 DecisionTree 決策樹 有許多決策樹算法 Hunt算法信息增益 Informationgain ID3 增益比率 Gainration C4 5 基尼指數(shù) Giniindex SLIQ SPRINT Hunt算法 設(shè)Dt是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集算法步驟 如果Dt中所有記錄都屬于同一個類yt 則t是葉結(jié)點(diǎn) 用yt標(biāo)記如果Dt中包含屬于多個類的記錄 則選擇一個屬性測試條件 將記錄劃分成較小的子集 對于測試條件的每個輸出 創(chuàng)建一個子結(jié)點(diǎn) 并根據(jù)測試結(jié)果將Dt中的記錄分布到子結(jié)點(diǎn)中 然后 對于每個子結(jié)點(diǎn) 遞歸地調(diào)用該算法 Dt Hunt算法 Don tCheat 決策樹 Hunt算法采用貪心策略構(gòu)建決策樹 在選擇劃分?jǐn)?shù)據(jù)的屬性時 采取一系列局部最優(yōu)決策來構(gòu)造決策樹 決策樹歸納的設(shè)計(jì)問題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測試條件 怎樣評估每種測試條件 如何停止分裂過程 決策樹 Hunt算法采用貪心策略構(gòu)建決策樹 在選擇劃分?jǐn)?shù)據(jù)的屬性時 采取一系列局部最優(yōu)決策來構(gòu)造決策樹 決策樹歸納的設(shè)計(jì)問題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測試條件 怎樣評估每種測試條件 如何停止分裂過程 怎樣為不同類型的屬性指定測試條件 依賴于屬性的類型標(biāo)稱序數(shù)連續(xù)依賴于劃分的路數(shù)2路劃分多路劃分 基于標(biāo)稱屬性的分裂 多路劃分 劃分?jǐn)?shù) 輸出數(shù) 取決于該屬性不同屬性值的個數(shù) 二元劃分 劃分?jǐn)?shù)為2 這種劃分要考慮創(chuàng)建k個屬性值的二元劃分的所有2k 1 1種方法 OR 多路劃分 劃分?jǐn)?shù) 輸出數(shù) 取決于該屬性不同屬性值的個數(shù) 二元劃分 劃分?jǐn)?shù)為2 需要保持序數(shù)屬性值的有序性 基于序數(shù)屬性的劃分 OR 基于連續(xù)屬性的劃分 多路劃分 vi A vi 1 i 1 k 二元劃分 A v or A v 考慮所有的劃分點(diǎn) 選擇一個最佳劃分點(diǎn)v 基于連續(xù)屬性的劃分 決策樹 決策樹歸納的設(shè)計(jì)問題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測試條件 怎樣評估每種測試條件 如何停止分裂過程 怎樣選擇最佳劃分 在劃分前 10個記錄class0 10個記錄class1 怎樣選擇最佳劃分 選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度 不純性的程度越低 類分布就越傾斜結(jié)點(diǎn)不純性的度量 不純性大 不純性小 怎樣找到最佳劃分 B Yes No NodeN3 NodeN4 A Yes No NodeN1 NodeN2 劃分前 Gain M0 M12vsM0 M34 結(jié)點(diǎn)不純性的測量 GiniEntropyclassificationerror 不純性的測量 GINI 給定結(jié)點(diǎn)t的Gini值計(jì)算 p j t 是在結(jié)點(diǎn)t中 類j發(fā)生的概率 當(dāng)類分布均衡時 Gini值達(dá)到最大值 1 1 nc 相反當(dāng)只有一個類時 Gini值達(dá)到最小值0 計(jì)算GINI的例子 P C1 0 6 0P C2 6 6 1Gini 1 P C1 2 P C2 2 1 0 1 0 P C1 1 6P C2 5 6Gini 1 1 6 2 5 6 2 0 278 P C1 2 6P C2 4 6Gini 1 2 6 2 4 6 2 0 444 基于GINI的劃分 當(dāng)一個結(jié)點(diǎn)p分割成k個部分 孩子 劃分的質(zhì)量可由下面公式計(jì)算ni 孩子結(jié)點(diǎn)i的記錄數(shù) n 父結(jié)點(diǎn)p的記錄數(shù) 二元屬性 計(jì)算GINI 對于二元屬性 結(jié)點(diǎn)被劃分成兩個部分得到的GINI值越小 這種劃分越可行 B Yes No NodeN1 NodeN2 Gini N1 1 5 6 2 2 6 2 0 194Gini N2 1 1 6 2 4 6 2 0 528 Ginisplit 7 12 0 194 5 12 0 528 0 333 標(biāo)稱屬性 計(jì)算Gini 多路劃分二元劃分一般多路劃分的Gini值比二元劃分小 這一結(jié)果并不奇怪 因?yàn)槎獎澐謱?shí)際上合并了多路劃分的某些輸出 自然降低了子集的純度 Multi waysplit Two waysplit findbestpartitionofvalues 連續(xù)屬性 計(jì)算Gini 使用二元劃分劃分點(diǎn)v選擇N個記錄中所有屬性值作為劃分點(diǎn)對每個劃分進(jìn)行類計(jì)數(shù) A vandA v計(jì)算每個候選點(diǎn)v的Gini指標(biāo) 并從中選擇具有最小值的候選劃分點(diǎn)時間復(fù)雜度為 n2 連續(xù)屬性 計(jì)算Gini 降低計(jì)算復(fù)雜性的方法 將記錄進(jìn)行排序從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點(diǎn)計(jì)算每個候選點(diǎn)的Gini值時間復(fù)雜度為nlogn 定義 給定一個概率空間事件 的自信息定義為因 自信息反映了事件發(fā)生所需要的信息量 值越大說明需要越多的信息才能確定事件的發(fā)生 其隨機(jī)性也越大 而當(dāng)發(fā)生時所攜帶的信息量也越大 反過來 值越小 需要較少信息量就能確定的發(fā)生 即事件隨機(jī)性較小 當(dāng)其發(fā)生時所攜信息量就少 是對不確定性大小的一種刻畫 熵 定義 熵 定義 1 定義 在概率空間上定義的隨機(jī)變量I X 的數(shù)學(xué)期望 稱為隨機(jī)變量X的平均自信息 又稱X的信息熵或熵記為H x 非負(fù)性 H大于等于0連續(xù)性 H對任意q連續(xù)極值性 當(dāng)q都等于1 K時H達(dá)到最大值logK 熵 定義 基于InformationGain的劃分 給定結(jié)點(diǎn)t的Entropy值計(jì)算 p j t 是在結(jié)點(diǎn)t中 類j發(fā)生的概率 當(dāng)類分布均衡時 Entropy值達(dá)到最大值 lognc 相反當(dāng)只有一個類時 Gini值達(dá)到最小值0Entropy與GINI相似 計(jì)算Entropy的例子 P C1 0 6 0P C2 6 6 1Entropy 0log0 1log1 0 0 0 P C1 1 6P C2 5 6Entropy 1 6 log2 1 6 5 6 log2 1 6 0 65 P C1 2 6P C2 4 6Entropy 2 6 log2 2 6 4 6 log2 4 6 0 92 基于InformationGain的劃分 InformationGain ni 孩子結(jié)點(diǎn)i的記錄數(shù) n 結(jié)點(diǎn)p的記錄數(shù) 在ID3andC4 5中使用 基于InformationGain的劃分 增益率 GainRatio 熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性 如 利用雇員id產(chǎn)生更純的劃分 但它卻毫無用處每個劃分相關(guān)聯(lián)的記錄數(shù)太少 將不能做出可靠的預(yù)測解決該問題的策略有兩種 限制測試條件只能是二元劃分使用增益率 K越大SplitInfo越大增益率越小 基于ClassificationError的劃分 給定結(jié)點(diǎn)t的ClassificationError值計(jì)算 當(dāng)類分布均衡時 error值達(dá)到最大值 1 1 nc 相反當(dāng)只有一個類時 error值達(dá)到最小值0 例子 P C1 0 6 0P C2 6 6 1Error 1 max 0 1 1 1 0 P C1 1 6P C2 5 6Error 1 max 1 6 5 6 1 5 6 1 6 P C1 2 6P C2 4 6Error 1 max 2 6 4 6 1 4 6 1 3 不純性度量之間的比較 二元分類問題 決策樹 Hunt算法采用貪心策略構(gòu)建決策樹 在選擇劃分?jǐn)?shù)據(jù)的屬性時 采取一系列局部最優(yōu)決策來構(gòu)造決策樹 決策樹歸納的設(shè)計(jì)問題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測試條件 怎樣評估每種測試條件 如何停止分裂過程 停止分裂過程 當(dāng)所有的記錄屬于同一類時 停止分裂當(dāng)所有的記錄都有相同的屬性時 停止分裂提前終止樹的生長 三種著名的決策樹 Cart 基本的決策樹算法Id3 利用增益比不純性 樹采用二叉樹 停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時 停止分裂 或當(dāng)所有的記錄都有相同的屬性時 停止分裂C4 5 id3的改進(jìn)版本 也是最流行的分類數(shù)算法 采用多重分支和剪枝技術(shù) 決策樹 特點(diǎn) 決策樹是一種構(gòu)建分類模型的非參數(shù)方法不需要昂貴的的計(jì)算代價決策樹相對容易解釋決策樹是學(xué)習(xí)離散值函數(shù)的典型代表決策數(shù)對于噪聲的干擾具有相當(dāng)好的魯棒性冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響數(shù)據(jù)碎片問題 隨著數(shù)的生長 可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少 對于葉結(jié)點(diǎn)代表的類 不能做出具有統(tǒng)計(jì)意義的判決子樹可能在決策樹中重復(fù)多次 使決策樹過于復(fù)雜 子樹重復(fù)問題 Samesubtreeappearsinmultiplebranches 決策邊界 斜決策樹 模型過分?jǐn)M合和擬合不足 分類模型的誤差大致分為兩種 訓(xùn)練誤差 是在訓(xùn)練記錄上誤分類樣本比例泛化誤差 是模型在未知記錄上的期望誤差一個好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù) 而且對未知樣本也要能準(zhǔn)確分類 換句話說 一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差 當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型 其泛化誤差可能比具有較高訓(xùn)練誤差的模型高 這種情況成為模型過分?jǐn)M合 模型過分?jǐn)M合和擬合不足 當(dāng)決策樹很小時 訓(xùn)練和檢驗(yàn)誤差都很大 這種情況稱為模型擬合不足 出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu) 隨著決策樹中結(jié)點(diǎn)數(shù)的增加 模型的訓(xùn)練誤差和檢驗(yàn)誤差都會隨之下降 當(dāng)樹的規(guī)模變得太大時 即使訓(xùn)練誤差還在繼續(xù)降低 但是檢驗(yàn)誤差開始增大 導(dǎo)致模型過分?jǐn)M合 模型模型過分?jǐn)M合和擬合不足 過分?jǐn)M合 導(dǎo)致過分?jǐn)M合的原因 導(dǎo)致過分?jǐn)M合的原因 噪聲導(dǎo)致的過分?jǐn)M合例子 哺乳動物的分類問題十個訓(xùn)練記錄中有兩個被錯誤標(biāo)記 蝙蝠和鯨如果完全擬合訓(xùn)練數(shù)據(jù) 決策樹1的訓(xùn)練誤差為0 但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá)30 人和海豚 針鼴誤分為非哺乳動物相反 一個更簡單的決策樹2 具有較低的檢驗(yàn)誤差 10 盡管它的訓(xùn)練誤差較高 為20 決策樹1過分?jǐn)M合了訓(xùn)練數(shù)據(jù) 因?yàn)閷傩詼y試條件4條腿具有欺騙性 它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄 導(dǎo)致了對檢驗(yàn)集中記錄的誤分類 噪聲導(dǎo)致的過分?jǐn)M合 例子 噪聲導(dǎo)致決策邊界的改變 缺乏代表性樣本導(dǎo)致的過分?jǐn)M合 根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過分?jǐn)M合的影響 由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本 在沒有多少訓(xùn)練記錄的情況下 學(xué)習(xí)算法仍然細(xì)化模型就會產(chǎn)生過分?jǐn)M合 例子 五個訓(xùn)練記錄 所有的記錄都是正確標(biāo)記的 對應(yīng)的決策樹盡管訓(xùn)練誤差為0 但檢驗(yàn)誤差高達(dá)30 人 大象和海豚被誤分類 因?yàn)闆Q策樹把恒溫但不冬眠的動物分為非哺乳動物 決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€訓(xùn)練記錄 鷹 具有這些特征 這個例子清楚的表明 當(dāng)決策樹的葉結(jié)點(diǎn)沒有足夠的代表性樣本時 很可能做出錯誤的預(yù)測 過分?jǐn)M合與多重比較 模型的過分?jǐn)M合可能出現(xiàn)在使用多重比較過程的算法中多重比較的例子 考慮未來十個交易日股市是升還是降一個人十次猜測至少正確預(yù)測八次的概率是 0 0547假設(shè)從50個股票分析家中選擇一個投資顧問 策略是選擇在未來的十個交易日做出最多正確預(yù)測的分析家 該策略的缺點(diǎn)是 即使所有的分析家都用隨機(jī)猜測做出預(yù)測 至少有一個分析家做出八次正確預(yù)測的概率是 1 1 0 0547 50 0 9399 這一結(jié)果相當(dāng)高 多重比較過程與模型過分?jǐn)M合有什么關(guān)系 在決策樹增長過程中 可以進(jìn)行多種測試 以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù) 在這種情況下 算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹 當(dāng)候選屬性多 訓(xùn)練記錄數(shù)少時 這種影響就變得更加明顯 泛化誤差估計(jì) 過分?jǐn)M合的主要原因一直是個爭辯的話題 但大家還是普遍同意模型的復(fù)雜度對模型的過分?jǐn)M合有影響 如何確定正確的模型復(fù)雜度 理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度 估計(jì)泛化誤差的方法使用再代入估計(jì) 用訓(xùn)練誤差提供對泛化誤差的樂觀估計(jì)結(jié)合模型復(fù)雜度估計(jì)統(tǒng)計(jì)上界使用確定集 結(jié)合模型復(fù)雜度 奧卡姆剃刀 Occam sRazor 給定兩個具有相同泛化誤差的模型 較簡單的模型比復(fù)雜的模型更可取因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合 因此 分類模型評估應(yīng)把模型復(fù)雜度考慮進(jìn)去方法 悲觀誤差估計(jì) 最小描述長度原則 MDL 悲觀誤差評估 悲觀誤差估計(jì)公式 Q ti 為每個結(jié)點(diǎn)ti的罰分 e T 為訓(xùn)練樣本集的錯分樣本數(shù) Nt為訓(xùn)練樣本總數(shù) k為葉結(jié)點(diǎn)數(shù) 例子1 如果罰分等于0 5 訓(xùn)練樣本集中樣本數(shù)為24個 我們構(gòu)建了7個葉結(jié)點(diǎn)的決策樹 訓(xùn)練樣本集的錯分樣本數(shù)為4根據(jù)公式我們得e T 4 7 0 5 24 0 3125例子2 如果罰分等于0 5 訓(xùn)練樣本集中樣本數(shù)為24個 我們構(gòu)建了4個葉結(jié)點(diǎn)的決策樹 訓(xùn)練樣本集的錯分樣本數(shù)為6根據(jù)公式我們得e T 6 4 0 5 24 0 3333當(dāng)罰分等于1時 例1 2為0 458 0 4170 5的罰分項(xiàng)表示只要至少能夠改進(jìn)一個訓(xùn)練記錄的分類 結(jié)點(diǎn)就應(yīng)當(dāng)擴(kuò)充 因?yàn)閿U(kuò)展一個結(jié)點(diǎn)等價于總誤差增加0 5 代價比犯一個訓(xùn)練錯誤小 最小描述長度 MDL Cost Model Data Cost Data Model Cost Model Cost是傳輸總代價 最小化cost值 Cost Data Model 是誤分類記錄編碼的開銷 Cost Model 是模型編碼的開銷 使用確認(rèn)集 該方法中 不是用訓(xùn)練集估計(jì)泛化誤差 而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集 一個子集用于訓(xùn)練 而另一個稱為確認(rèn)集 用于估計(jì)泛化誤差 該方法為評估模型在未知樣本上的性能提供了較好辦法 處理決策樹中的過分?jǐn)M合 先剪枝 EarlyStoppingRule 樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長為了做到這一點(diǎn) 需要采用更具限制性的結(jié)束條件 當(dāng)結(jié)點(diǎn)的記錄