決策樹培訓(xùn)教材(PPT 89頁).ppt

第6章決策樹 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 決策樹基本概念 關(guān)于分類問題 分類 Classification 任務(wù)就是通過學(xué)習(xí)獲得一個目標(biāo)函數(shù) TargetFunction f 將每個屬性集x映射到一個預(yù)先定義好的類標(biāo)號y 分類任務(wù)的輸入數(shù)據(jù)是紀(jì)錄的集合 每條記錄也稱為實例或者樣例 用元組 X y 表示 其中 X是屬性集合 y是一個特殊的屬性 指出樣例的類標(biāo)號 也稱為分類屬性或者目標(biāo)屬性 決策樹基本概念 關(guān)于分類問題 X y 分類與回歸 分類目標(biāo)屬性y是離散的 回歸目標(biāo)屬性y是連續(xù)的 決策樹基本概念 解決分類問題的一般方法 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法 分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型 該模型可以很好地擬合輸入數(shù)據(jù)中類標(biāo)號和屬性集之間的聯(lián)系 學(xué)習(xí)算法得到的模型不僅要很好擬合輸入數(shù)據(jù) 還要能夠正確地預(yù)測未知樣本的類標(biāo)號 因此 訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化能力模型 即建立能夠準(zhǔn)確地預(yù)測未知樣本類標(biāo)號的模型 分類方法的實例包括 決策樹分類法 基于規(guī)則的分類法 神經(jīng)網(wǎng)絡(luò) 支持向量級 樸素貝葉斯分類方法等 決策樹基本概念 解決分類問題的一般方法 通過以上對分類問題一般方法的描述 可以看出分類問題一般包括兩個步驟 1 模型構(gòu)建 歸納 通過對訓(xùn)練集合的歸納 建立分類模型 2 預(yù)測應(yīng)用 推論 根據(jù)建立的分類模型 對測試集合進(jìn)行測試 決策樹基本概念 解決分類問題的一般方法 學(xué)習(xí)算法 學(xué)習(xí)模型 模型 應(yīng)用模型 訓(xùn)練集 類標(biāo)號已知 檢驗集 類標(biāo)號未知 歸納 推論 決策樹基本概念 決策樹 決策樹是一種典型的分類方法 首先對數(shù)據(jù)進(jìn)行處理 利用歸納算法生成可讀的規(guī)則和決策樹 然后使用決策對新數(shù)據(jù)進(jìn)行分析 本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程 決策樹基本概念 決策樹的優(yōu)點1 推理過程容易理解 決策推理過程可以表示成IfThen形式 2 推理過程完全依賴于屬性變量的取值特點 3 可自動忽略目標(biāo)變量沒有貢獻(xiàn)的屬性變量 也為判斷屬性變量的重要性 減少變量的數(shù)目提供參考 決策樹基本概念 關(guān)于歸納學(xué)習(xí) 1 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法 歸納是從特殊到一般的過程 歸納推理從若干個事實中表征出的特征 特性和屬性中 通過比較 總結(jié) 概括而得出一個規(guī)律性的結(jié)論 歸納推理試圖從對象的一部分或整體的特定的觀察中獲得一個完備且正確的描述 即從特殊事實到普遍性規(guī)律的結(jié)論 歸納對于認(rèn)識的發(fā)展和完善具有重要的意義 人類知識的增長主要來源于歸納學(xué)習(xí) 決策樹基本概念 關(guān)于歸納學(xué)習(xí) 2 歸納學(xué)習(xí)的過程就是尋找一般化描述的過程 這種一般性描述能夠解釋給定的輸入數(shù)據(jù) 并可以用來預(yù)測新的數(shù)據(jù) 銳角三角形內(nèi)角和等于180度 鈍角三角形內(nèi)角和等于180度 三角形內(nèi)角和直角三角形內(nèi)角和等于180度 等于180度 已知三角形ABC A角等于76度 B角等于89度 則其C角等于15度 歸納學(xué)習(xí)由于依賴于檢驗數(shù)據(jù) 因此又稱為檢驗學(xué)習(xí) 歸納學(xué)習(xí)存在一個基本的假設(shè) 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù) 則它也能在未見樣本中很好地逼近目標(biāo)函數(shù) 該假定是歸納學(xué)習(xí)的有效性的前提條件 決策樹基本概念 關(guān)于歸納學(xué)習(xí) 3 決策樹基本概念 關(guān)于歸納學(xué)習(xí) 4 歸納過程就是在描述空間中進(jìn)行搜索的過程 歸納可分為自頂向下 自底向上和雙向搜索三種方式 自底向上法一次處理一個輸入對象 將描述逐步一般化 直到最終的一般化描述 自頂向下法對可能的一般性描述集進(jìn)行搜索 試圖找到一些滿足一定要求的最優(yōu)的描述 決策樹基本概念 從機器學(xué)習(xí)看分類及歸納推理等問題 1 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機器學(xué)習(xí)的中心問題 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理 每個例子都是一個對偶 序偶 x f x 對每個輸入的x 都有確定的輸出f x 學(xué)習(xí)過程將產(chǎn)生對目標(biāo)函數(shù)f的不同逼近 F的每一個逼近都叫做一個假設(shè) 假設(shè)需要以某種形式表示 例如 y ax b 通過調(diào)整假設(shè)的表示 學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形 在表示中通常需要修改參數(shù) 如a b 決策樹基本概念 從機器學(xué)習(xí)看分類及歸納推理等問題 2 從這些不同的變形中選擇最佳的假設(shè) 或者說權(quán)值集合 一般方法如定義為使訓(xùn)練值與假設(shè)值預(yù)測出的值之間的誤差平方和E最小為最佳 學(xué)習(xí)是在假設(shè)空間上的一個搜索 概念學(xué)習(xí)也可以看作是一個搜索問題的過程 它在預(yù)定義的假設(shè)空間中搜索假設(shè) 使其與訓(xùn)練樣例有最佳的擬合度 多數(shù)情況下 為了高效地搜索 可以利用假設(shè)空間中一種自然形成的結(jié)構(gòu) 即一般到特殊的偏序關(guān)系 決策樹基本概念 從機器學(xué)習(xí)看分類及歸納推理等問題 3 分類模型的性能根據(jù)模型正確和錯誤預(yù)測也可以根據(jù)的檢驗記錄計數(shù)進(jìn)行評估 這些計數(shù)存儲在混同矩陣 ConfusionMatrix 的表格中 二元分類問題混淆矩陣如下 實際的類 類1 f11 類0 f01 f10 f00 類1 類0 預(yù)測的類 準(zhǔn)確率 正確的預(yù)測數(shù) 預(yù)測總數(shù) f11 f00 f11 f01 f10 f00 差錯率 錯誤的預(yù)測數(shù) 預(yù)測總數(shù) f10 f01 f11 f01 f10 f00 歸納學(xué)習(xí)假設(shè)機器學(xué)習(xí)的任務(wù)是在整個實例集合X上確定與目標(biāo)概念c相同的假設(shè) 一般H表示所有可能假設(shè) H中每個假設(shè)h表示X上定義的布爾函數(shù) 由于對c僅有的信息只是它在訓(xùn)練樣例上的值 因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬合 若沒有更多的信息 只能假定對于未見實例最好的假設(shè)就是訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè) 定義歸納學(xué)習(xí)假設(shè) 任一假設(shè)如果在足夠大的訓(xùn)練樣例中很好地逼近目標(biāo)函數(shù) 則它也能在未見實例中很好地逼近目標(biāo)函數(shù) FunctionApproximation 決策樹基本概念 從機器學(xué)習(xí)看分類及歸納推理等問題 4 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 決策樹算法 與決策樹相關(guān)的重要算法 1 Hunt Marin和Stone于1966年研制的CLS學(xué)習(xí)系統(tǒng) 用于學(xué)習(xí)單個概念 2 1979年 J R Quinlan給出ID3算法 并在1983年和1986年對ID3進(jìn)行了總結(jié)和簡化 使其成為決策樹學(xué)習(xí)算法的典型 3 Schlimmer和Fisher于1986年對ID3進(jìn)行改造 在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū) 使決策樹可以遞增式生成 得到ID4算法 4 1988年 Utgoff在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法 進(jìn)一步提高了效率 1993年 Quinlan進(jìn)一步發(fā)展了ID3算法 改進(jìn)成C4 5算法 5 另一類決策樹算法為CART 與C4 5不同的是 CART的決策樹由二元邏輯問題生成 每個樹節(jié)點只有兩個分枝 分別包括學(xué)習(xí)實例的正例與反例 CLS ID3 C4 5 CART 決策樹算法 假定公司收集了左表數(shù)據(jù) 那么對于任意給定的客人 測試樣例 你能幫助公司將這位客人歸類嗎 即 你能預(yù)測這位客人是屬于 買 計算機的那一類 還是屬于 不買 計算機的那一類 又 你需要多少有關(guān)這位客人的信息才能回答這個問題 決策樹的用途 誰在買計算機 年齡 學(xué)生 信譽 青 中 老 否 是 優(yōu) 良 決策樹的用途 決策樹算法 誰在買計算機 年齡 學(xué)生 信譽 青 中 老 否 是 優(yōu) 良 決策樹的用途 決策樹算法 決策樹算法 決策樹的表示 決策樹的基本組成部分 決策結(jié)點 分支和葉子 年齡 學(xué)生 信譽 青 中 老 否 是 優(yōu) 良 決策樹中最上面的結(jié)點稱為根結(jié)點 是整個決策樹的開始 每個分支是一個新的決策結(jié)點 或者是樹的葉子 每個決策結(jié)點代表一個問題或者決策 通常對應(yīng)待分類對象的屬性 每個葉結(jié)點代表一種可能的分類結(jié)果 在沿著決策樹從上到下的遍歷過程中 在每個結(jié)點都有一個測試 對每個結(jié)點上問題的不同測試輸出導(dǎo)致不同的分枝 最后會達(dá)到一個葉子結(jié)點 這一過程就是利用決策樹進(jìn)行分類的過程 利用若干個變量來判斷屬性的類別 決策樹算法 CLS ConceptLearningSystem 算法 CLS算法是早期的決策樹學(xué)習(xí)算法 它是許多決策樹學(xué)習(xí)算法的基礎(chǔ) CLS基本思想從一棵空決策樹開始 選擇某一屬性 分類屬性 作為測試屬性 該測試屬性對應(yīng)決策樹中的決策結(jié)點 根據(jù)該屬性的值的不同 可將訓(xùn)練樣本分成相應(yīng)的子集 如果該子集為空 或該子集中的樣本屬于同一個類 則該子集為葉結(jié)點 否則該子集對應(yīng)于決策樹的內(nèi)部結(jié)點 即測試結(jié)點 需要選擇一個新的分類屬性對該子集進(jìn)行劃分 直到所有的子集都為空或者屬于同一類 決策樹算法 CLS算法 決策樹算法 CLS算法 決策樹的構(gòu)建 眼睛顏色 1 6 2 4 8 3 5 7 黑色 蘭色 灰色 不屬于同一類 非葉結(jié)點 眼睛顏色 頭發(fā)顏色 頭發(fā)顏色 頭發(fā)顏色 黑色 蘭色 灰色 決策樹算法 CLS算法 黃種人 1 混血 6 白種人 2 白種人 4 混血 8 白種人 3 白種人 5 混血 7 黑色 金色 金色 紅色 黑色 金色 紅色 黑色 決策樹算法 CLS算法 1生成一顆空決策樹和一張訓(xùn)練樣本屬性集 2若訓(xùn)練樣本集T中所有的樣本都屬于同一類 則生成結(jié)點T 并終止學(xué)習(xí)算法 否則3根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測試屬性 生成測試結(jié)點A4若A的取值為v1 v2 vm 則根據(jù)A的取值的不同 將T劃分成m個子集T1 T2 Tm 5從訓(xùn)練樣本屬性表中刪除屬性A 6轉(zhuǎn)步驟2 對每個子集遞歸調(diào)用CLS CLS算法問題 在步驟3中 根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性A作為測試屬性 沒有規(guī)定采用何種測試屬性 實踐表明 測試屬性集的組成以及測試屬性的先后對決策樹的學(xué)習(xí)具有舉足輕重的影響 舉例加以說明 下表為調(diào)查學(xué)生膳食結(jié)構(gòu)和缺鈣情況的關(guān)系 其中1表示包含食物 0表示不包含 決策樹算法 CLS算法問題 決策樹算法 學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表 CLS算法問題 決策樹算法 采用不同的測試屬性及其先后順序?qū)刹煌臎Q策樹 雞肉 豬肉 豬肉 牛肉 牛肉 牛肉 不缺鈣 2 缺鈣 3 6 不缺鈣 4 不缺鈣 10 缺鈣 5 不缺鈣 1 魚肉 缺鈣 5 不缺鈣 7 9 是 否 是 否 否 否 否 否 否 是 是 是 是 是 牛奶 不缺鈣 1 2 4 7 9 10 缺鈣 3 5 6 8 CLS算法問題 決策樹算法 在上例中 顯然生成的兩種決策樹的復(fù)雜性和分類意義相差很大由此可見 選擇測試屬性是決策樹學(xué)習(xí)算法中需要研究的重要課題 ID3 決策樹算法 ID3算法主要針對屬性選擇問題 是決策樹學(xué)習(xí)方法中最具影響和最為典型的算法 該方法使用信息增益度選擇測試屬性 當(dāng)獲取信息時 將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容 因此信息伴著不確定性 從直覺上講 小概率事件比大概率事件包含的信息量大 如果某件事情是 百年一見 則肯定比 習(xí)以為常 的事件包含的信息量大 如何度量信息量的大小 ID3 信息量大小的度量 決策樹算法 Shannon1948年提出的信息論理論 事件ai的信息量I ai 可如下度量 其中p ai 表示事件ai發(fā)生的概率 假設(shè)有n個互不相容的事件a1 a2 a3 an 它們中有且僅有一個發(fā)生 則其平均的信息量可如下度量 ID3 信息量大小的度量 決策樹算法 上式 對數(shù)底數(shù)可以為任何數(shù) 不同的取值對應(yīng)了熵的不同單位 通常取2 并規(guī)定當(dāng)p ai 0時 0 公式1 在決策樹分類中 假設(shè)S是訓(xùn)練樣本集合 S 是訓(xùn)練樣本數(shù) 樣本劃分為n個不同的類C1 C2 Cn 這些類的大小分別標(biāo)記為 C1 C2 Cn 則任意樣本S屬于類Ci的概率為 ID3 信息量大小的度量 決策樹算法 Entropy S A Sv S Entropy Sv 公式2 是屬性A的所有可能的值v Sv是屬性A有v值的S子集 Sv 是Sv中元素的個數(shù) S 是S中元素的個數(shù) ID3 信息量大小的度量 決策樹算法 Gain S A 是屬性A在集合S上的信息增益Gain S A Entropy S Entropy S A 公式3Gain S A 越大 說明選擇測試屬性對分類提供的信息越多 決策樹算法 第1步計算決策屬性的熵 決策屬性 買計算機 該屬性分兩類 買 不買S1 買 641S2 不買 383S S1 S2 1024P1 641 1024 0 6260P2 383 1024 0 3740I S1 S2 I 641 383 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9537 決策樹算法 第2步計算條件屬性的熵 條件屬性共有4個 分別是年齡 收入 學(xué)生 信譽 分別計算不同屬性的信息增益 決策樹算法 第2 1步計算年齡的熵 年齡共分三個組 青年 中年 老年青年買與不買比例為128 256S1 買 128S2 不買 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 決策樹算法 第2 2步計算年齡的熵 年齡共分三個組 青年 中年 老年中年買與不買比例為256 0S1 買 256S2 不買 0S S1 S2 256P1 256 256P2 0 256I S1 S2 I 256 0 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 決策樹算法 第2 3步計算年齡的熵 年齡共分三個組 青年 中年 老年老年買與不買比例為125 127S1 買 125S2 不買 127S S1 S2 252P1 125 252P2 127 252I S1 S2 I 125 127 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9157 決策樹算法 第2 4步計算年齡的熵 年齡共分三個組 青年 中年 老年所占比例青年組384 1025 0 375中年組256 1024 0 25老年組384 1024 0 375計算年齡的平均信息期望E 年齡 0 375 0 9183 0 25 0 0 375 0 9157 0 6877G 年齡信息增益 0 9537 0 6877 0 2660 1 決策樹算法 第3步計算收入的熵 收入共分三個組 高 中 低E 收入 0 9361收入信息增益 0 9537 0 9361 0 0176 2 決策樹算法 第4步計算學(xué)生的熵 學(xué)生共分二個組 學(xué)生 非學(xué)生E 學(xué)生 0 7811年齡信息增益 0 9537 0 7811 0 1726 3 決策樹算法 第5步計算信譽的熵 信譽分二個組 良好 優(yōu)秀E 信譽 0 9048信譽信息增益 0 9537 0 9048 0 0453 4 決策樹算法 第6步計算選擇節(jié)點 年齡信息增益 0 9537 0 6877 0 2660 1 收入信息增益 0 9537 0 9361 0 0176 2 年齡信息增益 0 9537 0 7811 0 1726 3 信譽信息增益 0 9537 0 9048 0 0453 4 決策樹算法 年齡 青年 中年 老年 買 不買 買 買 不買 葉子 決策樹算法 青年買與不買比例為128 256S1 買 128S2 不買 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 決策樹算法 如果選擇收入作為節(jié)點分高 中 低 平均信息期望 加權(quán)總和 E 收入 0 3333 0 0 5 0 9183 0 1667 0 0 4592Gain 收入 I 128 256 E 收入 0 9183 0 4592 0 4591 I 0 128 0比例 128 384 0 3333I 64 128 0 9183比例 192 384 0 5I 64 0 0比例 64 384 0 1667 注意 決策樹算法 年齡 青年 中年 老年 學(xué)生 買 信譽 葉子 否 是 優(yōu) 良 買 不買 買 不買 買 葉子 葉子 葉子 決策樹算法 ID3決策樹建立算法1決定分類屬性 2對目前的數(shù)據(jù)表 建立一個節(jié)點N3如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個類 N就是樹葉 在樹葉上標(biāo)出所屬的類4如果數(shù)據(jù)表中沒有其他屬性可以考慮 則N也是樹葉 按照少數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別5否則 根據(jù)平均信息期望值E或GAIN值選出一個最佳屬性作為節(jié)點N的測試屬性6節(jié)點屬性選定后 對于該屬性中的每個值 從N生成一個分支 并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點的數(shù)據(jù)表 在表中刪除節(jié)點屬性那一欄如果分支數(shù)據(jù)表非空 則運用以上算法從該節(jié)點建立子樹 決策樹算法 決策樹的數(shù)據(jù)準(zhǔn)備 原始表 決策樹算法 整理后的數(shù)據(jù)表 決策樹的數(shù)據(jù)準(zhǔn)備 Datacleaning刪除 減少noise 補填missingvaluesDatatransformation數(shù)據(jù)標(biāo)準(zhǔn)化 datanormalization 數(shù)據(jù)歸納 generalizedatatohigher levelconceptsusingconcepthierarchies 例如 年齡歸納為老 中 青三類控制每個屬性的可能值不超過七種 最好不超過五種 Relevanceanalysis對于與問題無關(guān)的屬性 刪對于屬性的可能值大于七種又不能歸納的屬性 刪 決策樹算法 決策樹的數(shù)據(jù)準(zhǔn)備 決策樹算法 處理連續(xù)屬性值 決策樹算法比較適合處理離散數(shù)值的屬性 實際應(yīng)用中屬性是連續(xù)的或者離散的情況都比較常見 在應(yīng)用連續(xù)屬性值時 在一個樹結(jié)點可以將屬性Ai的值劃分為幾個區(qū)間 然后信息增益的計算就可以采用和離散值處理一樣的方法 原則上可以將Ai的屬性劃分為任意數(shù)目的空間 C4 5中采用的是二元分割 BinarySplit 需要找出一個合適的分割閾值 參考C4 5算法Top10algorithmsindataminingKnowledgeInformationSystem200814 1 37 決策樹算法 ID3算法小結(jié) ID3算法是一種經(jīng)典的決策樹學(xué)習(xí)算法 由Quinlan于1979年提出 ID3算法的基本思想是 以信息熵為度量 用于決策樹節(jié)點的屬性選擇 每次優(yōu)先選取信息量最多的屬性 亦即能使熵值變?yōu)樽钚〉膶傩?以構(gòu)造一顆熵值下降最快的決策樹 到葉子節(jié)點處的熵值為0 此時 每個葉子節(jié)點對應(yīng)的實例集中的實例屬于同一類 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 1 通過ID3算法來實現(xiàn)客戶流失的預(yù)警分析 找出客戶流失的特征 以幫助電信公司有針對性地改善客戶關(guān)系 避免客戶流失利用決策樹方法進(jìn)行數(shù)據(jù)挖掘 一般有如下步驟 數(shù)據(jù)預(yù)處理 決策樹挖掘操作 模式評估和應(yīng)用 電信運營商的客戶流失有三方面的含義 一是指客戶從一個電信運營商轉(zhuǎn)網(wǎng)到其他電信運營商 這是流失分析的重點 二是指客戶月平均消費量降低 從高價值客戶成為低價值客戶 三 指客戶自然流失和被動流失 在客戶流失分析中有兩個核心變量 財務(wù)原因 非財務(wù)原因 主動流失 被動流失 客戶流失可以相應(yīng)分為四種類型 其中非財務(wù)原因主動流失的客戶往往是高價值的客戶 他們會正常支付服務(wù)費用 并容易對市場活動有所響應(yīng) 這種客戶是電信企業(yè)真正需要保住的客戶 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 2 數(shù)據(jù)預(yù)處理數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù) 這些數(shù)據(jù)一般存儲在數(shù)據(jù)庫系統(tǒng)中 該用戶相關(guān)數(shù)據(jù)存儲在其CRM中 是長期積累的結(jié)果 但往往不適合直接挖掘 需要做數(shù)據(jù)的預(yù)處理工作 一般包括數(shù)據(jù)的選擇 選擇相關(guān)的數(shù)據(jù) 凈化 消除冗余數(shù)據(jù) 轉(zhuǎn)換 歸約等 數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分 對于挖掘算法的效率乃至正確性都有關(guān)鍵性的影響 該公司經(jīng)過多年的電腦化管理 已有大量的客戶個人基本信息 文中簡稱為客戶信息表 在客戶信息表中 有很多屬性 如姓名用戶號碼 用戶標(biāo)識 用戶身份證號碼 轉(zhuǎn)化為年齡 在網(wǎng)時間 竣工時間 地址 職業(yè) 用戶類別 客戶流失 用戶狀態(tài) 等等 數(shù)據(jù)準(zhǔn)備時必須除掉表中一些不必要的屬性 一般可采用面向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 3 屬性刪除 將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除 比如客戶信息表中的用戶標(biāo)識 身份證號碼等 它們的取值太多且無法在該取值域內(nèi)找到概化操作符 應(yīng)將其刪除 得到表1 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 4 屬性概化 用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進(jìn)行概化 文化程度分為3類 W1初中以下 含初中 W2高中 含中專 W3大學(xué) 專科 本科及以上 職業(yè)類別 按工作性質(zhì)來分共分3類 Z1一Z3 繳費方式 托收 T1 營業(yè)廳繳費 T2 充值卡 T3 連續(xù)型屬性概化為區(qū)間值 表中年齡 費用變化率和在網(wǎng)時間為連續(xù)型數(shù)據(jù) 由于建立決策樹時 用離散型數(shù)據(jù)進(jìn)行處理速度最快 因此對連續(xù)型數(shù)據(jù)進(jìn)行離散化處理 根據(jù)專家經(jīng)驗和實際計算信息增益 在 在網(wǎng)時長 屬性中 通過檢測每個劃分 得到在閾值為5年時信息增益最大 從而確定最好的劃分是在5年處 則這個屬性的范圍就變?yōu)?5 H1 H2 而在 年齡 屬性中 信息增益有兩個鋒值 分別在40和50處 因而該屬性的范圍變?yōu)?40 50 即變?yōu)?青年 中年 老年 N1 N2 N3 費用變化率 指 當(dāng)月話費 近3個月的平均話費 近3個月的平均話費 0 F1 30 F2 30 99 F3 100 變?yōu)?F1 F2 F3 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 5 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例 6 在圖中 NO表示客戶不流失 YES表示客戶流失 從圖可以看出 客戶費用變化率為100 的客戶肯定已經(jīng)流失 而費用變化率低于30 的客戶 即每月資費相對穩(wěn)定的客戶一般不會流失 費用變化率在30 99 的客戶有可能流失 其中年齡在40 50歲之間的客戶流失的可能性非常大 而年齡低于40歲的客戶 用充值卡繳費的客戶和在網(wǎng)時間較短的客戶容易流失 年齡較大的客戶 則工人容易流失 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 決策樹研究問題 理想的決策樹有三種 1 葉子結(jié)點數(shù)最少 2 葉子結(jié)點深度最小 3 葉子結(jié)點數(shù)最少且葉子結(jié)點深度最小 然而 洪家榮等人已經(jīng)證明了要找到這種最優(yōu)的決策樹是NP難題 因此 決策樹優(yōu)化的目的就是要找到盡可能趨向于最優(yōu)的決策樹 關(guān)于過渡擬合 上述的決策樹算法增長樹的每一個分支的深度 直到恰好能對訓(xùn)練樣例比較完美地分類 實際應(yīng)用中 當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時 該策略可能會遇到困難 在以上情況發(fā)生時 這個簡單的算法產(chǎn)生的樹會過渡擬合訓(xùn)練樣例 過渡擬合 OverFitting 決策樹研究問題 關(guān)于過渡擬合 對于一個假設(shè) 當(dāng)存在其它的假設(shè)對訓(xùn)練樣例的擬合比它差 但事實上在實例的整個分布上 包含訓(xùn)練集合以外的實例 表現(xiàn)得卻更好時 則稱該假設(shè)過度擬合訓(xùn)練樣例 過度擬合 給定一個假設(shè)空間H 一個假設(shè)h H 如果存在其它的假設(shè)h1 H 使得在訓(xùn)練樣例上h的錯誤率比h1小 但在整個實例發(fā)布上h1的錯誤率比h小 則稱假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)過度擬合產(chǎn)生的原因 噪聲 訓(xùn)練樣例太小等 決策樹研究問題 關(guān)于過渡擬合 對學(xué)習(xí)算法是否成功的真正測試是看它對于訓(xùn)練中未見到的數(shù)據(jù)的執(zhí)行性能 訓(xùn)練過程應(yīng)該包含訓(xùn)練樣本和驗證樣本 驗證樣本用于測試訓(xùn)練后的性能 如果驗證結(jié)果差 則需要考慮采用不同的結(jié)構(gòu)重新進(jìn)行訓(xùn)練 例如使用更大的樣本集 或者改變從連續(xù)值到離散值得數(shù)據(jù)轉(zhuǎn)換等 通常應(yīng)該建立一個驗證過程 在訓(xùn)練最終完成后用來檢測訓(xùn)練結(jié)果的泛化能力 決策樹研究問題 關(guān)于過渡擬合 分類模型的誤差 一般可以將分類模型的誤差分為 1 訓(xùn)練誤差 TrainingError 2 泛化誤差 GeneralizationError 決策樹研究問題 關(guān)于過渡擬合 分類模型的誤差 訓(xùn)練誤差是在訓(xùn)練記錄上誤分類樣本比例 泛化誤差是模型在未知記錄上的期望誤差 一個好的模型不僅要能夠很好地擬合訓(xùn)練數(shù)據(jù) 而且對未知樣本也要能夠準(zhǔn)確地分類 一個好的分類模型必須具有低的訓(xùn)練誤差和泛化誤差 因為一個具有低訓(xùn)練誤差的模型 其泛化誤差可能比具有較高訓(xùn)練誤差的模型高 訓(xùn)練誤差低 泛化誤差高 稱為過渡擬合 決策樹研究問題 關(guān)于過渡擬合 模型過渡擬合的潛在因素 1 噪聲導(dǎo)致的過渡擬合 錯誤的類別值 類標(biāo)簽 屬性值等 2 缺乏代表性樣本所導(dǎo)致的過渡擬合根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過渡擬合的影響 由于訓(xùn)練樣本缺乏代表性的樣本 在沒有多少訓(xùn)練記錄的情況下 學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會導(dǎo)致過渡擬合 決策樹研究問題 關(guān)于過渡擬合 模型過渡擬合的潛在因素 哺乳動物分類的訓(xùn)練樣例 體溫 恒溫 冷血 冬眠 N Y N N 4條腿 Y N N Y 哺乳動物分類的訓(xùn)練樣例 按照訓(xùn)練模型 人和大象都不是哺乳動物 決策樹作出這樣的判斷是因為只有一個訓(xùn)練樣例具有這些特點 鷹 恒溫 不冬眠 被劃分為非哺乳動物 該例清楚表明 當(dāng)決策樹的葉節(jié)點沒有足夠的代表性時 可能會預(yù)測錯誤 決策樹研究問題 關(guān)于過渡擬合 解決過度擬合的手段 1及早停止樹增長 2后修剪法 決策樹研究問題 關(guān)于過渡擬合 1及早停止樹增長由于決策樹學(xué)習(xí)要從候選集合眾選擇滿足給定標(biāo)準(zhǔn)的最大化屬性 并且不回溯 也就是我們常說的爬山策略 其選擇往往會是局部最優(yōu)而不是全局最優(yōu) 樹結(jié)構(gòu)越復(fù)雜 則過渡擬合發(fā)生的可能性越大 因此 要選擇簡單的模型 Occan法則 又稱Occan剃刀OccanRazor 具有相同泛化誤差的兩個模型 較簡單的模型比復(fù)雜的模型更可取 決策樹研究問題 關(guān)于過渡擬合 后修剪法 后剪枝法 在訓(xùn)練過程中允許對數(shù)據(jù)的過渡擬合 然后再對樹進(jìn)行修剪該方法稱為后剪枝法 決策樹研究問題 關(guān)于過渡擬合 后修剪法 后剪枝法 例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N 一棵通過訓(xùn)練集合學(xué)好的決策樹 決策樹研究問題 關(guān)于過渡擬合 后修剪法 后剪枝法 例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N 對以上的決策樹通過右側(cè)的驗證集合進(jìn)行測試 發(fā)現(xiàn)其有5個錯分類 決策樹研究問題 關(guān)于過渡擬合 后修剪法 后剪枝法 例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N 18 19 20 1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 17 錯分類5個 6 7 8 13 14 決策樹研究問題 關(guān)于過渡擬合 后修剪法 后剪枝法 例 第1步將決策樹規(guī)則化 規(guī)則1IFA YANDB YTHEN 規(guī)則2IFA YANDB NANDC YTHEN 規(guī)則3IFA YANDB NANDC NTHEN 規(guī)則4IFA NTHEN A B 負(fù) C 正 正 負(fù) Y Y Y