決策支持系統(tǒng)的核心數(shù)據(jù)挖

決策支持系統(tǒng)的核心數(shù)據(jù)挖第一頁，共七十九頁，編輯于2023年，星期日0決策支持系統(tǒng)（DSS）數(shù)據(jù)模型推理知識決策人機交互第二頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘（DM）的產(chǎn)生背景隨著數(shù)據(jù)庫技術的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應用，企業(yè)和組織積累的數(shù)據(jù)越來越多第三頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘（DM）的產(chǎn)生背景數(shù)據(jù)庫系統(tǒng)可以高效地實現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預測未來的發(fā)展趨勢，從而出現(xiàn)“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象第四頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘（DM）的產(chǎn)生背景大量數(shù)據(jù)背后隱藏著許多重要的信息，企業(yè)和組織的管理決策者希望能夠?qū)ζ溥M行更高層次的分析。第五頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘（DM）的產(chǎn)生背景GartnerGroup的一次高級技術調(diào)查結(jié)果將數(shù)據(jù)挖掘和人工智能列為“將對未來三到五年內(nèi)工業(yè)產(chǎn)生深遠影響的五大關鍵技術”之首；世界500強企業(yè)中80%都涉足數(shù)據(jù)挖掘的前瞻性研究。第六頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的概念數(shù)據(jù)挖掘又稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KnowledgeDiscoveryfromDatabase,KDD），它是一個從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數(shù)據(jù)中抽取挖掘出隱含其中的、事先未知的、有價值的模式或規(guī)律等知識的復雜過程，該過程如下圖所示。第七頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)清洗與集成任務相關數(shù)據(jù)集選擇與轉(zhuǎn)換數(shù)據(jù)挖掘評估與表示數(shù)據(jù)倉庫數(shù)據(jù)庫知識第八頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的概念數(shù)據(jù)挖掘涉及多學科技術的集成：數(shù)據(jù)庫技術，統(tǒng)計學，機器學習，高性能計算，模式識別，神經(jīng)網(wǎng)絡，數(shù)據(jù)可視化，信息檢索，圖象與信號處理和空間數(shù)據(jù)分析。第九頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的概念數(shù)據(jù)挖掘功能用于指定數(shù)據(jù)挖掘任務中要找的模式類型。數(shù)據(jù)挖掘任務一般分兩類：描述式數(shù)據(jù)挖掘：刻畫數(shù)據(jù)庫或數(shù)據(jù)倉庫中數(shù)據(jù)的一般特性。預測式數(shù)據(jù)挖掘：在當前數(shù)據(jù)上進行推斷，以進行預測。第十頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能概念描述（Conceptdescription）：利用數(shù)據(jù)屬性中更廣義的（屬性）內(nèi)容對其進行歸納和總結(jié)第十一頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能關聯(lián)分析（AssociationAnalysis）：從給定的數(shù)據(jù)集中發(fā)現(xiàn)頻繁出現(xiàn)的項集模式知識第十二頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能分類（Classification）：找出一組能夠描述數(shù)據(jù)集合典型特征的函數(shù)，以便能夠識別未知數(shù)據(jù)的歸屬或類別，即將未知事例映射到某個離散類別第十三頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能聚類分析（ClusteringAnalysis）：根據(jù)“各聚集（cluster）之內(nèi)數(shù)據(jù)對象的相似度最大化和各聚集之間數(shù)據(jù)對象相似度最小化”這一原則將數(shù)據(jù)對象劃分為若干組第十四頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能孤立點分析（OutlierAnalysis）：尋找不符合大多數(shù)數(shù)據(jù)對象所構(gòu)成的規(guī)律（模型）的數(shù)據(jù)對象第十五頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念數(shù)據(jù)挖掘的功能演化分析（EvolutionAnalysis）：對隨時間變化的數(shù)據(jù)對象的變化規(guī)律和趨勢進行建模描述第十六頁，共七十九頁，編輯于2023年，星期日1數(shù)據(jù)挖掘的基本概念工具特點分析重點分析目的數(shù)據(jù)大小控制方式發(fā)展狀況傳統(tǒng)數(shù)據(jù)分析工具回顧型、驗證型已經(jīng)發(fā)生了什么從最近的銷售文件中列出最大客戶數(shù)據(jù)量和數(shù)據(jù)維度均是少量的企業(yè)管理人員、系統(tǒng)分析員、管理顧問啟動與控制成熟數(shù)據(jù)挖掘工具發(fā)現(xiàn)型、預測型解釋發(fā)生的原因、預測未來的情況鎖定未來的可能客戶，以減少未來的銷售成本數(shù)據(jù)量和數(shù)據(jù)維度均是龐大的數(shù)據(jù)與系統(tǒng)啟動，少量的控制人員發(fā)展中數(shù)據(jù)挖掘工具與傳統(tǒng)數(shù)據(jù)分析工具的比較第十七頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則關聯(lián)規(guī)則的基本概念關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關聯(lián)或相關聯(lián)系。從大量商業(yè)事務記錄中發(fā)現(xiàn)有趣的關聯(lián)關系，可以幫助許多商務決策的制定，如分類設計、交叉購物和促銷分析等。第十八頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則購物籃分析購物籃分析是關聯(lián)規(guī)則挖掘的最初形式假定作為某商店經(jīng)理，你想更加了解你的顧客的購物習慣。例如：“什么商品組或集合顧客多半會在一次購物時同時購買？”。為解答這個問題，可以在商店顧客事務零售數(shù)據(jù)上運行購物籃分析。分析的結(jié)果可用于市場規(guī)劃、廣告策劃和分類設計。第十九頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則購物籃分析若設商店中所有銷售商品為一個集合，則每個商品均為一個布爾變量，表示該商品是否被（一個）顧客購買。因此每個購物籃就可以用一個布爾向量表示。第二十頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則購物籃分析分析相應布爾向量，得到反映商品頻繁關聯(lián)或同時購買的購買模式，并可用關聯(lián)規(guī)則的形式表示模式。例如，購買計算機也趨向于同時購買財務管理軟件可用以下關聯(lián)規(guī)則表示：第二十一頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則購物籃分析關聯(lián)規(guī)則的支持度（support）2%表示分析中的全部事務的2%同時購買計算機和財務管理軟件。關聯(lián)規(guī)則的置信度（confidence）60%表示：購買計算機的顧客60%也購買財務管理軟件。第二十二頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法Apriori算法是根據(jù)有關頻繁項集性質(zhì)的先驗知識而命名。該算法使用一種逐層搜索的迭代方法，利用k-項集探索(k+1)-項集。具體做法：首先找出頻繁1-項集的集合，記為L1；再用L1找頻繁2-項集的集合L2；再用L2找L3…如此下去，直到不能找到頻繁k-項集為止。找每個Lk需要一次數(shù)據(jù)庫掃描。第二十三頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法Apriori算法的有效性，在于它利用了一個非常重要的原理，即Apriori性質(zhì)：如果一個項集是頻繁的，則這個項集的任意一個非空子集都是頻繁的。Apriori性質(zhì)基于如下觀察：如果項集I不滿足最小支持度閾值min_sup，則I不是頻繁的。如果增加項A到I，則結(jié)果項集不可能比I更頻繁出現(xiàn)。因此，也不是頻繁的。第二十四頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法該性質(zhì)屬于一種特殊的分類，也稱作反單調(diào)性。意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。反單調(diào)性能迅速減值，提高搜索頻繁項集的處理效率。第二十五頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法整個過程由連接和剪枝兩步組成，即連接步：為找Lk，可通過Lk-1與自己連接，產(chǎn)生一個候選k-項集的集合，該候選項集的集合記作Ck

。剪枝步確定頻繁項集連接步產(chǎn)生候選項集第二十六頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法設l1和l2是Lk-1中的項集，記號li[j]表示li的第j項。為方便計，假定事務或項集中的項按字典次序排序。執(zhí)行連接，其中Lk-1的元素是可連接的，如果它們前(k-2)個項相同。Lk-1Lk-1第二十七頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法即Lk-1的元素l1和l2是可連接的，如果（l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-2]=l2[k-2]∧l1[k-1]<l2[k-1]）。條件（l1[k-1]<l2[k-1]）可確保不產(chǎn)生重復的項集。第二十八頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法剪枝步Ck是Lk的超集，即它的成員不一定都是頻繁項集，但所有的頻繁k-項集都包含在Ck中掃描數(shù)據(jù)庫，確定Ck中每個候選項集的計數(shù)，從而確定Lk。然而，Ck可能很大，這樣所涉及的計算量就很大。第二十九頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法剪枝步為了壓縮Ck

，可利用Apriori性質(zhì)：任何非頻繁的(k-1)-項集都不可能是頻繁k-項集的子集。因此，若一個候選k-項集的(k-1)-項子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck

中刪除。第三十頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則【例】一個Apriori的具體例子，該例基于右圖某商店的事務DB。DB中有9個事務，Apriori假定事務中的項按字典次序存放。TID項ID的列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3第三十一頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（1）在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法簡單地掃描所有的事務，對每個項的出現(xiàn)次數(shù)計數(shù)。掃描D,對每個候選計數(shù)項集支持度計數(shù){I1}6{I2}7{I3}6{I4}2{I5}2C1第三十二頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（2）設最小支持計數(shù)為2，可以確定頻繁1-項集的集合Lk-1。它由具有最小支持度的候選1-項集組成。項集支持度計數(shù){I1}6{I2}7{I3}6{I4}2{I5}2比較候選支持度計數(shù)與最小支持度計數(shù)L1第三十三頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（3）為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用產(chǎn)生候選2-項集集合C2。L1L1項集{I1，I2}{I1，I3}{I1，I4}{I1，I5}{I2，I3}{I2，I4}{I2，I5}{I3，I4}{I3，I5}{I4，I5}C2由L1產(chǎn)生候選C2第三十四頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（4）掃描D中事務，計算C2中每個候選項集的支持計數(shù)。項集支持度計數(shù){I1，I2}4{I1，I3}4{I1，I4}1{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2{I3，I4}0{I3，I5}1{I4，I5}0掃描D,對每個候選計數(shù)C2第三十五頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（5）確定頻繁2-項集的集合L2，它由具有最小支持度的C2中的候選2-項集組成。項集支持度計數(shù){I1，I2}4{I1，I3}4{I1，I5}2{I2，I3}4{I2，I4}2{I2，I5}2比較候選支持度計數(shù)與最小支持度計數(shù)L2第三十六頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（6）候選3-項集的集合C3的產(chǎn)生如下：

①連接：

C3=

=

{{I1,I2}，{I1,I3}，{I1,I5}，{I2,I3}，{I2,I4}，{I2,I5}}{{I1,I2}，{I1,I3}，{I1,I5}，{I2,I3}，{I2,I4}，I2,I5}}=

{{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}L2L2第三十七頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（6）候選3-項集的集合C3的產(chǎn)生如下：

②利用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的。存在候選項集，判斷其子集是否頻繁。

{I1,I2,I3}的2-項子集是{I1,I2}，{I1,I3}和{I2,I3}，它們都是L2的元素。因此保留{I1,I2,I3}在C3中。{I1,I2,I5}的2-項子集是{I1,I2}，{I1,I5}和{I2,I5},它們都是L2的元素。因此保留{I1,I2,I5}在C3中。第三十八頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（6）候選3-項集的集合C3的產(chǎn)生如下：

{I1,I3,I5}的2-項子集是{I1,I3}，{I1,I5}和{I3,I5}，{I3,I5}不是L2的元素，因而不是頻繁的，由C3中刪除{I1,I3,I5}。

{I2,I3,I4}的2-項子集是{I2,I3}，{I2,I4}和{I3,I4}，其中{I3,I4}不是L2的元素，因而不是頻繁的，由C3中刪除{I2,I3,I4}。第三十九頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（6）候選3-項集的集合C3的產(chǎn)生如下：

{I2,I3,I5}的2-項子集是{I2,I3}，{I2,I5}和{I3,I5}，其中{I3,I5}不是L2的元素，因而不是頻繁的，由C3中刪除{I2,I3,I5}。{I2,I4,I5}的2-項子集是{I2,I4}，{I2,I5}和{I4,I5}，其中{I4,I5}不是L2的元素，因而不是頻繁的，由C3中刪除{I2,I4,I5}。③這樣，剪枝后C3

=

{{I1,I2,I3}，{I1,I2,I5}}。第四十頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（7）掃描D中事務，以確定L3，它由具有最小支持度的C3中的候選3-項集組成。項集{I1，I2，I3}{I1，I2，I5}由L2產(chǎn)生候選C3C3掃描D,對每個候選計數(shù)項集支持度計數(shù){I1，I2，I3}2{I1，I2，I5}2C3第四十一頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則（8）算法使用產(chǎn)生候選4-項集的集合C4。盡管連接產(chǎn)生結(jié)果{{I1,I2,I3,I5}}，這個項集將被剪去，因為它的子集{I2,I3,I5}不是頻繁的。則C4

=，因此算法終止，找出了所有的頻繁項集。項集支持度計數(shù){I1，I2，I3}2{I1，I2，I5}2比較候選支持度計數(shù)與最小支持度計數(shù)L3L3L3ψ第四十二頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法基于上例結(jié)果，假定數(shù)據(jù)包含頻繁項集l={I1，I2，I5}?？梢杂蒷產(chǎn)生哪些關聯(lián)規(guī)則？l的非空子集有{I1，I2}、{I1，I5}、{I2，I5}、{I1}、{I2}和{I5}，則結(jié)果關聯(lián)規(guī)則如下（每個都列出置信度）。第四十三頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法%%%%%第四十四頁，共七十九頁，編輯于2023年，星期日2數(shù)據(jù)挖掘功能——關聯(lián)規(guī)則Apriori算法如果最小置信度閾值為70%，那么只有第2、3、6個規(guī)則可以作為最終的輸出，因為只有這些是產(chǎn)生的強規(guī)則。第四十五頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識基于判定樹的分類簡單貝葉斯分類第四十六頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識分類和預測是數(shù)據(jù)分析的兩種形式，可以用來提取描述重要數(shù)據(jù)類的模型或預測未來的數(shù)據(jù)趨勢分類：預測離散或分類屬性預測：預測連續(xù)或有序值第四十七頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識數(shù)據(jù)分類（1）學習：建立一個描述已知數(shù)據(jù)集類別或概念的模型。該模型是通過對DB中元組屬性的分析而構(gòu)造的。假定每個元組屬于一個預定義的類，由類標號屬性確定。為建立模型所使用的元組形成訓練數(shù)據(jù)集。其中的單個元組稱作訓練樣本，并隨機地從樣本群體中選取。由于提供了每個訓練樣本的類標號，該步也稱作有指導的學習第四十八頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識數(shù)據(jù)分類通常學習模型用分類規(guī)則、判定樹或數(shù)學公式的形式提供例如：給定一個顧客信用信息DB，通過學習獲得的分類規(guī)則，可用于識別顧客是否具有良好的信用等級或一般的信用等級第四十九頁，共七十九頁，編輯于2023年，星期日姓名年齡收入信用等級王明<=30低良張小麗<=30低優(yōu)許永新31-40高優(yōu)陳進>40中良方菲>40中良劉力音31-40高優(yōu)…………訓練數(shù)據(jù)分類算法分類規(guī)則if年齡=“31-40”

and

收入=“高”

then信用等級=“優(yōu)”（1）學習：用分類算法分析訓練數(shù)據(jù)類標號屬性是信用等級，學習模型以分類規(guī)則形式提供第五十頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識數(shù)據(jù)分類（2）分類：使用學習得到的模型進行分類。首先評估模型的預測準確率。有多種方法可以用來評估分類的準確率，保持（holdout）方法是一種利用類標號樣本測試集的簡單方法。這些樣本隨機選取，并獨立于訓練樣本。對于每個測試樣本，將已知的類標號與學習所獲模型的預測類別進行比較。模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比第五十一頁，共七十九頁，編輯于2023年，星期日姓名年齡收入信用等級蘇寺華>40高良汪洋<=30低良劉賓31-40高優(yōu)…………（2）分類：測試數(shù)據(jù)用于評估分類規(guī)則的準確率（若準確率可以接受，則規(guī)則可用于新的數(shù)據(jù)元組分類）測試數(shù)據(jù)分類規(guī)則新數(shù)據(jù)(劉賓，31-40，高)信用等級？優(yōu)第五十二頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測分類與預測的基本知識數(shù)據(jù)預測預測是構(gòu)造和使用模型評估無標號樣本類，或評估給定樣本可能具有的屬性值或值區(qū)間為了提高分類與預測過程的準確性、有效性和可伸縮性，可對數(shù)據(jù)進行預處理。一般使用：數(shù)據(jù)清理，相關性分析，數(shù)據(jù)變換（概念分層或規(guī)范化）第五十三頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類判定樹判定樹是一個類似流程圖的樹型結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節(jié)點代表類或類分布判定樹歸納是構(gòu)造判定樹的基本算法。在判定樹構(gòu)造時，許多分枝可能反映的是訓練數(shù)據(jù)中的噪聲或孤立點?？捎脴浼糁Ψ椒z測和剪去這類分枝，以提高在未知數(shù)據(jù)上分類的準確性第五十四頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（1）判定樹歸納：以自頂向下遞歸的分而治之方式構(gòu)造判定樹。算法的基本策略如下：判定樹以代表訓練樣本的單個節(jié)點開始若一個節(jié)點的樣本均為同一類別，則該節(jié)點成為樹葉，并用該類進行標記第五十五頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（1）判定樹歸納：否則，算法使用信息增益度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性，作為該節(jié)點的“測試”屬性。在此算法中，所有的屬性都是分類的，即取離散值。對連續(xù)值的屬性必須離散化對測試屬性的每個已知的值，創(chuàng)建一個分枝，并具此劃分樣本第五十六頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（1）判定樹歸納：算法使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。一個屬性一旦出現(xiàn)在某個節(jié)點上，就不再考慮該節(jié)點的任何后代遞歸劃分操作僅當下列條件之一成立時停止：a）給定節(jié)點的所有樣本屬于同一類b）沒有剩余屬性可用來進一步劃分樣本c）測試屬性的一個分枝沒有樣本第五十七頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（2）屬性選擇方法：在判定樹的每個節(jié)點上使用信息增益度量選擇測試屬性。選擇具有最高信息增益的屬性作為當前節(jié)點的測試屬性，可以使結(jié)果劃分中的樣本分類需要的信息量最小，并反映劃分的最小隨機性。這種信息論方法使得對一個對象分類所需的期望測試數(shù)目達到最小，并確保找到一棵簡單的樹。第五十八頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類信息增益度量設S是訓練樣本的集合，其中每個樣本的類標號已知假定有m個類，設S包含si個Ci類樣本，i=1,2,…,m任意一個樣本屬于類Ci的可能性為si/s，其中s是集合S中樣本的總數(shù)。第五十九頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類信息增益度量一個決策樹可用于對數(shù)據(jù)對象進行分類,因此決策樹可以看成是Ci的一個信息源,為產(chǎn)生相應信息需要的信息熵（entropy）為：第六十頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類信息增益度量若屬性A的取值為{a1,a2,…,an}，且該屬性用作決策樹的一個結(jié)點時，則可將S劃分為子集{S1,S2,…,Sn}。其中Sj包含屬性A取同一值aj的數(shù)據(jù)行。記sij為Sj包含類Ci的樣本個數(shù)。第六十一頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類信息增益度量根據(jù)屬性A的取值對當前數(shù)據(jù)集劃分所獲得的信息就稱為屬性A的熵。它的計算公式如下：第六十二頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類信息增益度量A上該劃分得到的信息增益定義為:：第六十三頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（2）屬性選擇方法：判定樹歸納算法計算每個屬性的信息增益，并挑選具有最高信息增益的屬性作為給定集合的測試屬性。創(chuàng)建一個節(jié)點，并以該屬性標記。對屬性的每個值創(chuàng)建分枝，并據(jù)此劃分樣本。第六十四頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類【例】下表給出一個商場顧客DB數(shù)據(jù)元組訓練集，類標號屬性buys_compute有兩個不同值，即{yes，no}，因此訓練集中有兩個不同的類（m=2）。設類C1對應于yes，而類C2對應no。類C1有9個樣本，類C2有5個樣本。我們用前面的一組公式計算每個屬性的信息增益。第六十五頁，共七十九頁，編輯于2023年，星期日RID年齡收入學生信用級購買電腦1<=30高No良No2<=30高No優(yōu)No331–40高No良Yes4>40中No良Yes5>40低Yes良Yes6>40低Yes優(yōu)No731–40低Yes優(yōu)Yes8<=30中No良No9<=30低Yes良Yes10>40中Yes良Yes11<=30中Yes優(yōu)Yes1231–40中No優(yōu)Yes1331–40高Yes良Yes14>40中No優(yōu)No第六十六頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類首先計算給定樣本分類所需的信息增益:接著計算每個屬性的熵,從屬性age開始:第六十七頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類若樣本按age劃分，對一個給定的樣本分類所需的期望信息為：這種劃分的信息增益是:第六十八頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類類似地，可計算：由于age在屬性中具有最高信息增益，它被選作測試屬性。創(chuàng)建一個節(jié)點，用age標記，并對每個屬性值引出一個分枝。樣本據(jù)此劃分，見下圖：第六十九頁，共七十九頁，編輯于2023年，星期日收入學生?信用級購買?高No良No高No優(yōu)No中No良No低Yes良Yes中Yes優(yōu)Yes收入學生?信用級購買?中No良Yes低Yes良Yes低Yes優(yōu)No中Yes良Yes中No優(yōu)No收入學生?信用級購買?高No良Yes低Yes優(yōu)Yes中No優(yōu)Yes高Yes良Yes年齡?<=30>3031-40第七十頁，共七十九頁，編輯于2023年，星期日年齡？學生？信用級？yesyesyesnono<=3031…40>40noyes良優(yōu)算法返回的最終判定樹如下：第七十一頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類判定樹歸納算法被廣泛應用到許多進行分類識別的應用領域，這類算法無需相關領域知識。歸納的學習與分類識別的操作處理速度較快，相應的分類準確率較高。第七十二頁，共七十九頁，編輯于2023年，星期日3數(shù)據(jù)挖掘功能——分類與預測基于判定樹的分類（3）樹剪枝：在判定樹構(gòu)造時，許多分枝可能反映的是訓練數(shù)據(jù)中的噪聲或孤立點。可用樹剪枝