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