數(shù)據(jù)挖掘?qū)д摰?章分類：基本概念、決策樹與模型評估.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)確率是正確被模型分類的測試樣本的百分比 測試集要獨立于訓(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)計方法：知識表示是判別函數(shù)和原型事例 貝葉斯法 非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí)) 3.神經(jīng)網(wǎng)絡(luò)方法： BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型 4.粗糙集(rough set)知識表示是產(chǎn)生式規(guī)則,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,訓(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é)點表示在一個屬性上的測試 每個分枝代表一個測試輸出 每個樹葉節(jié)點代表類或類分布 決策樹的生成由兩個階段組成 決策樹構(gòu)建 開始時，所有的訓(xùn)練樣本都在根節(jié)點 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） 樹剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝 決策樹的使用：對未知樣本進(jìn)行分類 通過將樣本的屬性值與決策樹相比較,為了對未知數(shù)據(jù)對象進(jìn)行分類識別，可以根據(jù)決策樹的結(jié)構(gòu)對數(shù)據(jù)集中的屬性進(jìn)行測試，從決策樹的根節(jié)點到葉節(jié)點的一條路徑就形成了相應(yīng)對象的類別測試。決策樹可以很容易轉(zhuǎn)換為分類規(guī)則,決策樹分類任務(wù),Decision Tree,一個決策樹的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型: 決策樹,應(yīng)用決策樹進(jìn)行分類,測試數(shù)據(jù),Start from the root of tree.,應(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ù),Assign Cheat to “No”,決策樹分類,Decision Tree,決策樹,有許多決策樹算法: Hunt算法 信息增益Information gain （ID3） 增益比率Gain ration（C4.5） 基尼指數(shù)Gini index (SLIQ，SPRINT),Hunt 算法,設(shè) Dt 是與結(jié)點 t相關(guān)聯(lián)的訓(xùn)練記錄集 算法步驟: 如果Dt 中所有記錄都屬于同一個類 yt, 則t是葉結(jié)點，用yt標(biāo)記 如果 Dt 中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子結(jié)點，并根據(jù)測試結(jié)果將Dt中的記錄分布到子結(jié)點中。然后，對于每個子結(jié)點，遞歸地調(diào)用該算法,Dt,?,Hunt算法,Dont Cheat,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分?jǐn)?shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測試條件? 怎樣評估每種測試條件? 如何停止分裂過程,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分?jǐn)?shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(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ù)屬性的劃分,多路劃分:viAvi+1（i=1,k) 二元劃分: (A v) or (A v) 考慮所有的劃分點，選擇一個最佳劃分點v,基于連續(xù)屬性的劃分,決策樹,決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測試條件? 怎樣評估每種測試條件? 如何停止分裂過程,怎樣選擇最佳劃分？,在劃分前: 10 個記錄 class 0, 10 個記錄 class 1,怎樣選擇最佳劃分？,選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點不純性的程度。不純性的程度越低，類分布就越傾斜 結(jié)點不純性的度量:,不純性大,不純性小,怎樣找到最佳劃分？,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,劃分前:,Gain = M0 M12 vs M0 M34,結(jié)點不純性的測量,Gini Entropy classification error,不純性的測量: GINI,給定結(jié)點t的Gini值計算 : (p( j | t) 是在結(jié)點t中，類j發(fā)生的概率). 當(dāng)類分布均衡時，Gini值達(dá)到最大值 (1 - 1/nc) 相反當(dāng)只有一個類時，Gini值達(dá)到最小值0,計算 GINI的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0,P(C1) = 1/6 P(C2) = 5/6 Gini = 1 (1/6)2 (5/6)2 = 0.278,P(C1) = 2/6 P(C2) = 4/6 Gini = 1 (2/6)2 (4/6)2 = 0.444,基于 GINI的劃分,當(dāng)一個結(jié)點 p 分割成 k 個部分 (孩子), 劃分的質(zhì)量可由下面公式計算 ni = 孩子結(jié)點 i的記錄數(shù), n = 父結(jié)點 p的記錄數(shù).,二元屬性: 計算 GINI,對于二元屬性，結(jié)點被劃分成兩個部分 得到的GINI值越小，這種劃分越可行.,B?,Yes,No,Node N1,Node N2,Gini(N1) = 1 (5/6)2 (2/6)2 = 0.194 Gini(N2) = 1 (1/6)2 (4/6)2 = 0.528,Gini split = 7/12 * 0.194 + 5/12 * 0.528 = 0.333,標(biāo)稱屬性:計算Gini,多路劃分 二元劃分 一般多路劃分的Gini值比二元劃分小，這一結(jié)果并不奇怪，因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了子集的純度,Multi-way split,Two-way split (find best partition of values),連續(xù)屬性: 計算 Gini,使用二元劃分 劃分點v選擇 N個記錄中所有屬性值作為劃分點 對每個劃分進(jìn)行類計數(shù), A v and A v 計算每個候選點v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點 時間復(fù)雜度為(n2),連續(xù)屬性: 計算 Gini.,降低計算復(fù)雜性的方法, 將記錄進(jì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都等于1K時 H達(dá)到最大值logK,熵-定義,基于 Information Gain的劃分,給定結(jié)點t的 Entropy值計算 : (p( j | t) 是在結(jié)點t中，類j發(fā)生的概率). 當(dāng)類分布均衡時， Entropy值達(dá)到最大值 (log nc) 相反當(dāng)只有一個類時，Gini值達(dá)到最小值0 Entropy 與 GINI相似,計算 Entropy的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = 0 log 0 1 log 1 = 0 0 = 0,P(C1) = 1/6 P(C2) = 5/6 Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65,P(C1) = 2/6 P(C2) = 4/6 Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92,基于 Information Gain的劃分.,Information Gain: ni = 孩子結(jié)點 i的記錄數(shù), n = 結(jié)點 p的記錄數(shù). 在 ID3 and C4.5中使用,基于 Information Gain的劃分.,增益率（Gain Ratio）: 熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無用處 每個劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測 解決該問題的策略有兩種： 限制測試條件只能是二元劃分 使用增益率。K越大Split Info越大增益率越小,基于 Classification Error的劃分,給定結(jié)點t的 Classification Error值計算 : 當(dāng)類分布均衡時， error值達(dá)到最大值 (1 - 1/nc) 相反當(dāng)只有一個類時， error值達(dá)到最小值0,例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Error = 1 max (0, 1) = 1 1 = 0,P(C1) = 1/6 P(C2) = 5/6 Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6,P(C1) = 2/6 P(C2) = 4/6 Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3,不純性度量之間的比較,二元分類問題:,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分?jǐn)?shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測試條件? 怎樣評估每種測試條件? 如何停止分裂過程,停止分裂過程,當(dāng)所有的記錄屬于同一類時，停止分裂 當(dāng)所有的記錄都有相同的屬性時，停止分裂 提前終止樹的生長,三種著名的決策樹,Cart：基本的決策樹算法 Id3：利用增益比不純性，樹采用二叉樹，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時，停止分裂，或當(dāng)所有的記錄都有相同的屬性時，停止分裂 C4.5：id3的改進(jìn)版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。,決策樹,特點: 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 不需要昂貴的的計算代價 決策樹相對容易解釋 決策樹是學(xué)習(xí)離散值函數(shù)的典型代表 決策數(shù)對于噪聲的干擾具有相當(dāng)好的魯棒性 冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響 數(shù)據(jù)碎片問題。隨著數(shù)的生長，可能導(dǎo)致葉結(jié)點記錄數(shù)太少，對于葉結(jié)點代表的類，不能做出具有統(tǒng)計意義的判決 子樹可能在決策樹中重復(fù)多次。使決策樹過于復(fù)雜,子樹重復(fù)問題,Same subtree appears in multiple branches,決策邊界,斜決策樹,模型過分?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)練和檢驗誤差都很大，這種情況稱為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實結(jié)構(gòu)。 隨著決策樹中結(jié)點數(shù)的增加，模型的訓(xùn)練誤差和檢驗誤差都會隨之下降。 當(dāng)樹的規(guī)模變得太大時，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗誤差開始增大，導(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，但它在檢驗數(shù)據(jù)上的誤差達(dá)30%.人和海豚，針鼴誤分為非哺乳動物 相反，一個更簡單的決策樹2，具有較低的檢驗誤差（10%），盡管它的訓(xùn)練誤差較高，為20% 決策樹1過分?jǐn)M合了訓(xùn)練數(shù)據(jù)。因為屬性測試條件4條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對檢驗集中記錄的誤分類,噪聲導(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，但檢驗誤差高達(dá)30% 人、大象和海豚被誤分類，因為決策樹把恒溫但不冬眠的動物分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓(xùn)練記錄（鷹）具有這些特征。 這個例子清楚的表明，當(dāng)決策樹的葉結(jié)點沒有足夠的代表性樣本時，很可能做出錯誤的預(yù)測。,過分?jǐn)M合與多重比較,模型的過分?jǐn)M合可能出現(xiàn)在使用多重比較過程的算法中 多重比較的例子：考慮未來十個交易日股市是升還是降 一個人十次猜測至少正確預(yù)測八次的概率是：0.0547 假設(shè)從50個股票分析家中選擇一個投資顧問，策略是選擇在未來的十個交易日做出最多正確預(yù)測的分析家。 該策略的缺點是，即使所有的分析家都用隨機(jī)猜測做出預(yù)測，至少有一個分析家做出八次正確預(yù)測的概率是：1-（1-0.0547）50=0.9399，這一結(jié)果相當(dāng)高。,多重比較過程與模型過分?jǐn)M合有什么關(guān)系？ 在決策樹增長過程中，可以進(jìn)行多種測試，以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。 在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。 當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時，這種影響就變得更加明顯。,泛化誤差估計,過分?jǐn)M合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分?jǐn)M合有影響。 如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。 估計泛化誤差的方法 使用再代入估計。用訓(xùn)練誤差提供對泛化誤差的樂觀估計 結(jié)合模型復(fù)雜度 估計統(tǒng)計上界 使用確定集,結(jié)合模型復(fù)雜度,奧卡姆剃刀 （Occams Razor ）：給定兩個具有相同泛化誤差的模型，較簡單的模型比復(fù)雜的模型更可取 因為復(fù)雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評估應(yīng)把模型復(fù)雜度考慮進(jìn)去 方法：悲觀誤差估計、最小描述長度原則（MDL）,悲觀誤差評估,悲觀誤差估計公式： Q(ti)為每個結(jié)點ti的罰分，e(T)為訓(xùn)練樣本集的錯分樣本數(shù)，Nt為訓(xùn)練樣本總數(shù)，k為葉結(jié)點數(shù)。,例子1：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個，我們構(gòu)建了7個葉結(jié)點的決策樹，訓(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é)點的決策樹，訓(xùn)練樣本集的錯分樣本數(shù)為6 根據(jù)公式我們得e(T)=(6+4*0.5)/24=0.3333 當(dāng)罰分等于1時，例1，2為0.458，0.417 0.5的罰分項表示只要至少能夠改進(jìn)一個訓(xùn)練記錄的分類，結(jié)點就應(yīng)當(dāng)擴(kuò)充，因為擴(kuò)展一個結(jié)點等價于總誤差增加0.5，代價比犯一個訓(xùn)練錯誤小,最小描述長度 (MDL),Cost(Model,Data) = Cost(Data|Model) + Cost(Model) Cost 是傳輸總代價. 最小化cost值. Cost(Data|Model) 是誤分類記錄編碼的開銷. Cost(Model) 是模型編碼的開銷 .,使用確認(rèn)集,該方法中，不是用訓(xùn)練集估計泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱為確認(rèn)集，用于估計泛化誤差。 該方法為評估模型在未知樣本上的性能提供了較好辦法。,處理決策樹中的過分?jǐn)M合,先剪枝 (Early Stopping Rule) 樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長 為了做到這一點，需要采用更具限制性的結(jié)束條件: 當(dāng)