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

1、決策支持系統(tǒng)的核心決策支持系統(tǒng)的核心數(shù)據挖掘方法與技術數(shù)據挖掘方法與技術0 決策支持系統(tǒng)（決策支持系統(tǒng)（dss）數(shù)據數(shù)據模型模型推理推理知識知識決策決策人機人機交互交互1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘（數(shù)據挖掘（dm）的產生背景的產生背景n隨著數(shù)據庫技術的迅速發(fā)展以及數(shù)據庫隨著數(shù)據庫技術的迅速發(fā)展以及數(shù)據庫管理系統(tǒng)的廣泛應用，管理系統(tǒng)的廣泛應用，企業(yè)和組織企業(yè)和組織積累積累的數(shù)據越來越多的數(shù)據越來越多1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘（數(shù)據挖掘（dm）的產生背景的產生背景n數(shù)據庫系統(tǒng)可以高效地實現(xiàn)數(shù)據的錄入、數(shù)據庫系統(tǒng)可以高效地實現(xiàn)數(shù)據的錄入、查詢、統(tǒng)計等功能

2、，但無法發(fā)現(xiàn)數(shù)據中查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據中存在的關系和規(guī)則，無法根據現(xiàn)有的數(shù)存在的關系和規(guī)則，無法根據現(xiàn)有的數(shù)據預測未來的發(fā)展趨勢，據預測未來的發(fā)展趨勢， 從而出現(xiàn)從而出現(xiàn)“數(shù)數(shù)據爆炸但知識貧乏據爆炸但知識貧乏”的現(xiàn)象的現(xiàn)象1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘（數(shù)據挖掘（dm）的產生背景的產生背景n大量數(shù)據背后隱藏著許多重要的信息，大量數(shù)據背后隱藏著許多重要的信息，企業(yè)和組織的管理決策者企業(yè)和組織的管理決策者希望能夠對其希望能夠對其進行更高層次的分析。進行更高層次的分析。1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘（數(shù)據挖掘（dm）的產生背景的產生背景ngartn

3、er group的一次高級技術調查結果的一次高級技術調查結果將數(shù)據挖掘和人工智能列為將數(shù)據挖掘和人工智能列為“將對未來三將對未來三到五年內工業(yè)產生深遠影響的五大關鍵技到五年內工業(yè)產生深遠影響的五大關鍵技術術”之首；之首；n世界世界500強企業(yè)中強企業(yè)中80%都涉足數(shù)據挖掘的都涉足數(shù)據挖掘的前瞻性研究。前瞻性研究。1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的概念的概念 數(shù)據挖掘又稱為數(shù)據庫中的知識發(fā)現(xiàn)數(shù)據挖掘又稱為數(shù)據庫中的知識發(fā)現(xiàn)（knowledge discovery from database, kdd），它是一個從大量的、不完全的、有噪），它是一個從大量的、不完全的、有噪

4、聲的、模糊的、隨機的實際應用數(shù)據中抽取挖聲的、模糊的、隨機的實際應用數(shù)據中抽取挖掘出隱含其中的、事先未知的、有價值的模式掘出隱含其中的、事先未知的、有價值的模式或規(guī)律等知識的復雜過程，該過程如下圖所示。或規(guī)律等知識的復雜過程，該過程如下圖所示。1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念數(shù)據清洗與集成數(shù)據清洗與集成任務相關數(shù)據集任務相關數(shù)據集選擇與轉換選擇與轉換數(shù)據挖掘數(shù)據挖掘評估與表示評估與表示數(shù)據倉庫數(shù)據倉庫數(shù)據庫數(shù)據庫知識知識1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的概念的概念n數(shù)據挖掘涉及多學科技術的集成：數(shù)據挖掘涉及多學科技術的集成：數(shù)據數(shù)據庫庫技術，統(tǒng)計學，機器學習，

5、高性能計技術，統(tǒng)計學，機器學習，高性能計算，模式識別，神經網絡，數(shù)據可視化，算，模式識別，神經網絡，數(shù)據可視化，信息檢索，圖象與信號處理和空間數(shù)據信息檢索，圖象與信號處理和空間數(shù)據分析。分析。1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的概念的概念n數(shù)據挖掘功能用于指定數(shù)據挖掘任務中數(shù)據挖掘功能用于指定數(shù)據挖掘任務中要找的模式類型。數(shù)據挖掘任務一般分要找的模式類型。數(shù)據挖掘任務一般分兩類：兩類：n描述式數(shù)據挖掘：刻描述式數(shù)據挖掘：刻畫畫數(shù)據庫或數(shù)據倉庫中數(shù)據庫或數(shù)據倉庫中數(shù)據的一般特性。數(shù)據的一般特性。n預測式數(shù)據挖掘：在當前數(shù)據上進行推斷，預測式數(shù)據挖掘：在當前數(shù)據上進行推斷，

6、以進行預測。以進行預測。1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n概念描述（概念描述（concept description）：利用）：利用數(shù)據屬性中更廣義的（屬性）內容對其進行數(shù)據屬性中更廣義的（屬性）內容對其進行歸納和總結歸納和總結1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n關聯(lián)分析（關聯(lián)分析（association analysis）：從）：從給定的數(shù)據集中發(fā)現(xiàn)頻繁出現(xiàn)的項集模式知給定的數(shù)據集中發(fā)現(xiàn)頻繁出現(xiàn)的項集模式知識識1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n分類（分類（classificatio

7、n）：找出一組能夠描）：找出一組能夠描述數(shù)據集合典型特征的函數(shù)，以便能夠識別述數(shù)據集合典型特征的函數(shù)，以便能夠識別未知數(shù)據的歸屬或類別，即將未知事例映射未知數(shù)據的歸屬或類別，即將未知事例映射到某個離散類別到某個離散類別1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n聚類分析（聚類分析（clustering analysis）：根據）：根據“各聚集（各聚集（cluster）之內數(shù)據對象的相似）之內數(shù)據對象的相似度最大化和各聚集之間數(shù)據對象相似度最小度最大化和各聚集之間數(shù)據對象相似度最小化化”這一原則將數(shù)據對象劃分為若干組這一原則將數(shù)據對象劃分為若干組1 數(shù)據挖掘的基本概念

8、數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n孤立點分析（孤立點分析（outlier analysis）：尋找不）：尋找不符合大多數(shù)數(shù)據對象所構成的規(guī)律（模型）符合大多數(shù)數(shù)據對象所構成的規(guī)律（模型）的數(shù)據對象的數(shù)據對象 1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念n數(shù)據挖掘數(shù)據挖掘的功能的功能n演化分析（演化分析（evolution analysis）：對隨）：對隨時間變化的數(shù)據對象的變化規(guī)律和趨勢進行時間變化的數(shù)據對象的變化規(guī)律和趨勢進行建模描述建模描述1 數(shù)據挖掘的基本概念數(shù)據挖掘的基本概念工具特點工具特點分析重點分析重點分析目的分析目的數(shù)據大小數(shù)據大小控制方式控制方式發(fā)展狀況發(fā)展狀況傳統(tǒng)

9、數(shù)據分析工具傳統(tǒng)數(shù)據分析工具回顧型、驗證型回顧型、驗證型已經發(fā)生了什么已經發(fā)生了什么從最近的銷售文件中列出最大客戶從最近的銷售文件中列出最大客戶數(shù)據量和數(shù)據維度均是少量的數(shù)據量和數(shù)據維度均是少量的企業(yè)管理人員、系統(tǒng)分析員、企業(yè)管理人員、系統(tǒng)分析員、管理顧問啟動與控制管理顧問啟動與控制成熟成熟數(shù)據挖掘工具數(shù)據挖掘工具發(fā)現(xiàn)型、預測型發(fā)現(xiàn)型、預測型解釋發(fā)生的原因、解釋發(fā)生的原因、預測未來的情況預測未來的情況鎖定未來的可能客戶，以減少鎖定未來的可能客戶，以減少未來的銷售成本未來的銷售成本數(shù)據量和數(shù)據維度均是龐大的數(shù)據量和數(shù)據維度均是龐大的數(shù)據與系統(tǒng)啟動，數(shù)據與系統(tǒng)啟動，少量的控制人員少量的控制人員發(fā)展

10、中發(fā)展中數(shù)據挖掘工具與傳統(tǒng)數(shù)據分析工具的比較數(shù)據挖掘工具與傳統(tǒng)數(shù)據分析工具的比較2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則n關聯(lián)規(guī)則的基本概念關聯(lián)規(guī)則的基本概念n關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據中項集之間有關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據中項集之間有趣的關聯(lián)或相關聯(lián)系。趣的關聯(lián)或相關聯(lián)系。n從大量商業(yè)事務記錄中發(fā)現(xiàn)有趣的關聯(lián)關從大量商業(yè)事務記錄中發(fā)現(xiàn)有趣的關聯(lián)關系，可以幫助許多商務決策的制定，如分系，可以幫助許多商務決策的制定，如分類設計、交叉購物和促銷分析等。類設計、交叉購物和促銷分析等。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則n購物籃分析購物籃分析n購物籃分析是關聯(lián)規(guī)則挖掘的最初形式購物籃分析是關聯(lián)

11、規(guī)則挖掘的最初形式n假定作為某商店經理，你想更加了解你的顧假定作為某商店經理，你想更加了解你的顧客的購物習慣。例如：客的購物習慣。例如：“什么商品組或集合什么商品組或集合顧客多半會在一次購物時同時購買？顧客多半會在一次購物時同時購買？”。為為解答這個問題，可以在商店顧客事務零售數(shù)解答這個問題，可以在商店顧客事務零售數(shù)據上運行購物籃分析。據上運行購物籃分析。n分析的結果可用于市場規(guī)劃、廣告策劃和分分析的結果可用于市場規(guī)劃、廣告策劃和分類設計。類設計。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則n購物籃分析購物籃分析n若設商店中所有銷售商品為一個集合，則每若設商店中所有銷售商品為一個集合，則每個商

12、品均為一個布爾變量，表示該商品是否個商品均為一個布爾變量，表示該商品是否被被（一個一個）顧客購買。因此每個購物籃就可顧客購買。因此每個購物籃就可以用一個布爾向量表示。以用一個布爾向量表示。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則n購物籃分析購物籃分析n分析相應布爾向量，得到反映商品頻繁關聯(lián)分析相應布爾向量，得到反映商品頻繁關聯(lián)或同時購買的購買模式，并可用關聯(lián)規(guī)則的或同時購買的購買模式，并可用關聯(lián)規(guī)則的形式表示模式。例如，購買計算機也趨向于形式表示模式。例如，購買計算機也趨向于同時購買財務管理軟件可用以下關聯(lián)規(guī)則表同時購買財務管理軟件可用以下關聯(lián)規(guī)則表示：示：2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)

13、規(guī)則關聯(lián)規(guī)則n購物籃分析購物籃分析n關聯(lián)規(guī)則的支持度關聯(lián)規(guī)則的支持度（support）2% 表示分表示分析中的全部事務的析中的全部事務的2% 同時購買計算機和同時購買計算機和財務管理軟件。財務管理軟件。n關聯(lián)規(guī)則的置信度關聯(lián)規(guī)則的置信度（confidence）60%表表示：購買計算機的顧客示：購買計算機的顧客60% 也購買財務管也購買財務管理軟件。理軟件。%60%,2_confidencesupportsoftwaremanagementfinancialcomputer2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法napriori算法是根據有關頻繁項集性質的先算法是根據

14、有關頻繁項集性質的先驗知識而命名。該算法使用一種逐層搜索的驗知識而命名。該算法使用一種逐層搜索的迭代方法，利用迭代方法，利用k-項集探索項集探索(k+1)-項集。項集。n具體做法：首先找出頻繁具體做法：首先找出頻繁1-項集的集合，記項集的集合，記為為l1 ；再用；再用l1找頻繁找頻繁2-項集的集合項集的集合l2；再用；再用l2找找l3 如此下去，直到不能找到頻繁如此下去，直到不能找到頻繁k-項項集為止。找每個集為止。找每個lk需要一次數(shù)據庫掃描。需要一次數(shù)據庫掃描。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法napriori算法的有效性算法的有效性，在于它利用了一個在于

15、它利用了一個非常重要的原理非常重要的原理，即即apriori性質性質：如果一：如果一個項集是頻繁的，則這個項集的任意一個非個項集是頻繁的，則這個項集的任意一個非空子集都是頻繁的。空子集都是頻繁的。napriori性質性質基于如下觀察：如果項集基于如下觀察：如果項集i不滿不滿足最小支持度閾值足最小支持度閾值min_sup，則，則i 不是頻繁不是頻繁的。如果增加項的。如果增加項a到到i，則結果項集不可能，則結果項集不可能比比i更頻繁出現(xiàn)。因此，也不是頻繁的。更頻繁出現(xiàn)。因此，也不是頻繁的。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n該性質屬于一種特殊的分類，也稱作反單調該

16、性質屬于一種特殊的分類，也稱作反單調性。意指如果一個集合不能通過測試，則它性。意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試的所有超集也都不能通過相同的測試。n反單調性能迅速減值，提高搜索頻繁項集的反單調性能迅速減值，提高搜索頻繁項集的處理效率。處理效率。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n整個過程由連接和剪枝兩步組成，整個過程由連接和剪枝兩步組成，即即n連接步：為找連接步：為找lk，可通過，可通過lk-1與自己連接，與自己連接，產生一個候選產生一個候選k-項集的集合，該候選項集的項集的集合，該候選項集的集合記作集合記作ck 。剪枝步確定頻

17、繁項集連接步產生候選項集2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n設設l1和和l2是是lk-1中的項集，記號中的項集，記號li j表示表示li的第的第j項。為方便計，假定事務或項集中的項按項。為方便計，假定事務或項集中的項按字典次序排序。字典次序排序。n執(zhí)行連接執(zhí)行連接 ， 其中其中l(wèi)k-1的元素是可的元素是可連接的，如果它們連接的，如果它們前前(k-2)個項相同個項相同。lk-1lk-12 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n即即lk-1的元素的元素l1和和l2是可連接的，如果是可連接的，如果（ l11 = l21 l12 = l22

18、 l1k-2 = l2k-2 l1k-1 l2k-1 ）。條件）。條件（l1k-1 l2 k-1）可確保不產生重復的）可確保不產生重復的項集。項集。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n剪枝步剪枝步nck是是lk的超集，即它的成員不一定都是頻繁的超集，即它的成員不一定都是頻繁項集，但所有的頻繁項集，但所有的頻繁k-項集都包含在項集都包含在ck中中n掃描數(shù)據庫，確定掃描數(shù)據庫，確定ck中每個候選項集的計數(shù)，中每個候選項集的計數(shù)，從而確定從而確定lk 。然而，。然而， ck可能很大，這樣所涉可能很大，這樣所涉及的計算量就很大。及的計算量就很大。2 數(shù)據挖掘功能數(shù)據挖

19、掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n剪枝步剪枝步n為了壓縮為了壓縮 ck ，可利用，可利用apriori性質：任何非性質：任何非頻繁的頻繁的(k-1)-項集都不可能是頻繁項集都不可能是頻繁k-項集的子項集的子集。因此，若一個候選集。因此，若一個候選k-項集的項集的(k-1)-項子集項子集不在不在 lk-1中，則該候選也不可能是頻繁的，中，則該候選也不可能是頻繁的，從而可以從從而可以從 ck 中刪除中刪除。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則【例】一個apriori的具體例子，該例基于右圖某商店的事務db。db中有9個事務，apriori假定事務中的項按字典次序存放。tid項

20、id的列表t100i1，i2，i5t200i2，i4t300i2，i3t400i1，i2，i4t500i1，i3t600i2，i3t700i1，i3t800i1，i2，i3，i5t900i1，i2，i32 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（1）在算法的第一次迭代，每個項都是在算法的第一次迭代，每個項都是候選候選1-1-項項集集的集合的集合c1的成員。算法簡單地掃描所有的事的成員。算法簡單地掃描所有的事務，對每個項的出現(xiàn)次數(shù)計數(shù)。務，對每個項的出現(xiàn)次數(shù)計數(shù)。掃描d d,對每個候選計數(shù)項集支持度計數(shù)i16i27i36i42i52c12 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（2 2）設最

21、小支持計數(shù)為）設最小支持計數(shù)為2 2，可以確定頻繁，可以確定頻繁1-1-項項集的集合集的集合lk-1。它由具有最小支持度的候選。它由具有最小支持度的候選1-1-項項集組成。集組成。項集支持度計數(shù)i16i27i36i42i52比較候選支持度計數(shù)與最小支持度計數(shù)l12 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（3 3）為發(fā)現(xiàn)頻繁）為發(fā)現(xiàn)頻繁2-2-項集的集項集的集合合l2，算法使用，算法使用 產生產生候選候選2-2-項集集合項集集合c2。l1l1項集i1，i2i1，i3i1，i4i1，i5i2，i3i2，i4i2，i5i3，i4i3，i5i4，i5c2由l1產生候選c22 數(shù)據挖掘功能數(shù)據挖掘功能

22、關聯(lián)規(guī)則關聯(lián)規(guī)則（4 4）掃描）掃描d d中事務，計中事務，計算算c2中每個候選項集的中每個候選項集的支持計數(shù)。支持計數(shù)。項集支持度計數(shù)i1，i24i1，i34i1，i41i1，i52i2，i34i2，i42i2，i52i3，i40i3，i51i4，i50掃描d,對每個候選計數(shù)c22 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（5 5）確定頻繁）確定頻繁2-2-項集的集項集的集合合l2，它由具有最小支持，它由具有最小支持度的度的c2中的候選中的候選2-2-項集組項集組成。成。項集支持度計數(shù)i1，i24i1，i34i1，i52i2，i34i2，i42i2，i52比較候選支持度計數(shù)與最小支持度計數(shù)l

23、22 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（6 6）候選）候選3-3-項集的集合項集的集合c3的產生如下：的產生如下： 連接：連接： 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,i5l2l22 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（6 6）候選）候選3-3-項集的集合項集的集合c3的產生如下：的產生如下： 利用利用apriori性質剪枝：頻繁項集的所有子集必性質剪枝：頻繁

24、項集的所有子集必須是頻繁的。存在候選項集，判斷其子集是否頻須是頻繁的。存在候選項集，判斷其子集是否頻繁。繁。 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中。中。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（6 6）候選）候選3-3-項集的集合項集的集合c3的產生如下：的產生如下： i1,i3,i5的的2-項子集項子集是是

25、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。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（6 6）候選）候選3-3-項集的集合項集的集合c3的產生如下：的產生如下： i2,i3,i5的的2-項子集項子集是是i2,i3，i2,i5和和i3,i5，其中其中i3,i5不是不是l2的元素，因而不是頻的元素，因

26、而不是頻繁的，由繁的，由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。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（7 7）掃描）掃描d d中事務，以確定中事務，以確定l3，它由具有最小支，它由具有最小支持度的持度的c3中的候選中的候選3-3-項集組成。項集組成。項集i1，i2，i3i1，i2，i5由l2產生候選c3c3掃描d,對每個候選計

27、數(shù)項集支持度計數(shù)i1，i2，i32i1，i2，i52c32 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則（8 8）算法使用算法使用 產生產生候選候選4-項集項集的集合的集合c4。盡管連接產生結果盡管連接產生結果 i1,i2,i3,i5，這個項這個項集將被剪去，因為它的子集集將被剪去，因為它的子集i2,i3,i5不是頻不是頻繁的。則繁的。則 c4 = ，因此算法終止，找出了所有，因此算法終止，找出了所有的頻繁項集。的頻繁項集。項集支持度計數(shù)i1，i2，i32i1，i2，i52比較候選支持度計數(shù)與最小支持度計數(shù)l3l3l32 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n基于上例結

28、果，假定數(shù)據包含頻繁項集基于上例結果，假定數(shù)據包含頻繁項集l=i1，i2，i5?？梢杂?。可以由l產生哪些關聯(lián)規(guī)產生哪些關聯(lián)規(guī)則？則？nl的非空子集有的非空子集有i1，i2、i1，i5、i2，i5、i1、i2和和i5，則結果關聯(lián)規(guī)則，則結果關聯(lián)規(guī)則如下（每個都列出置信度）。如下（每個都列出置信度）。2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法10022confidencei2,i1i52972confidencei5,i1i23362confidencei5,i2i110022confidencei1,i5i210022confidencei2,i5i15042confi

29、dencei5,i2i1 % % % % % %2 數(shù)據挖掘功能數(shù)據挖掘功能關聯(lián)規(guī)則關聯(lián)規(guī)則napriori算法算法n如果最小置信度閾值為如果最小置信度閾值為70%，那么只有，那么只有第第2、3、6個規(guī)則可以作為最終的輸出，個規(guī)則可以作為最終的輸出，因為只有這些是產生的強規(guī)則。因為只有這些是產生的強規(guī)則。3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n基于判定樹的分類基于判定樹的分類n簡單貝葉斯分類簡單貝葉斯分類3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n分類和預測是數(shù)據分析的兩種形式，可以用分類和預測

30、是數(shù)據分析的兩種形式，可以用來提取描述重要數(shù)據類的模型或預測未來的來提取描述重要數(shù)據類的模型或預測未來的數(shù)據趨勢數(shù)據趨勢n分類：預測離散或分類屬性分類：預測離散或分類屬性n預測：預測連續(xù)或有序值預測：預測連續(xù)或有序值3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n數(shù)據分類數(shù)據分類n（1）學習：建立一個描述已知數(shù)據集類別或概）學習：建立一個描述已知數(shù)據集類別或概念的模型。該模型是通過對念的模型。該模型是通過對db中元組屬性的分中元組屬性的分析而構造的。假定每個元組屬于一個預定義的析而構造的。假定每個元組屬于一個預定義的類，由類標號屬性確定。為建立模型所

31、使用的類，由類標號屬性確定。為建立模型所使用的元組形成訓練數(shù)據集。其中的單個元組稱作訓元組形成訓練數(shù)據集。其中的單個元組稱作訓練樣本，并隨機地從樣本群體中選取。由于提練樣本，并隨機地從樣本群體中選取。由于提供了每個訓練樣本的類標號，該步也稱作有指供了每個訓練樣本的類標號，該步也稱作有指導的學習導的學習3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n數(shù)據分類數(shù)據分類n通常學習模型用通常學習模型用分類規(guī)則分類規(guī)則、判定樹判定樹或或數(shù)學公式數(shù)學公式的形式提供的形式提供n例如：給定一個顧客信用信息例如：給定一個顧客信用信息db，通過學習獲，通過學習獲得的分類

32、規(guī)則，可用于識別顧客是否具有良好得的分類規(guī)則，可用于識別顧客是否具有良好的信用等級或一般的信用等級的信用等級或一般的信用等級姓名年齡收入信用等級王明=30=30低良張小麗=304040中良方菲4040中良劉力音31-4031-40高優(yōu)訓練數(shù)據分類算法分類規(guī)則if 年齡=“31-40” and 收入=“高” then 信用等級=“優(yōu)”（1）學習：用分類算法分析訓練數(shù)據類標號屬性是信用等級，學習模型以分類規(guī)則形式提供3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n數(shù)據分類數(shù)據分類n（2）分類：使用學習得到的模型進行分類。首）分類：使用學習得到的模型進行分

33、類。首先評估模型的預測準確率。有多種方法可以用先評估模型的預測準確率。有多種方法可以用來評估分類的準確率，保持（來評估分類的準確率，保持（holdout）方法是）方法是一種利用類標號樣本測試集的簡單方法。這些一種利用類標號樣本測試集的簡單方法。這些樣本隨機選取，并獨立于訓練樣本。對于每個樣本隨機選取，并獨立于訓練樣本。對于每個測試樣本，將已知的類標號與學習所獲模型的測試樣本，將已知的類標號與學習所獲模型的預測類別進行比較。模型在給定測試集上的準預測類別進行比較。模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比確率是正確被模型分類的測試樣本的百分比姓名年齡收入信用等級蘇寺華4040高

34、良汪洋=30=30低良劉賓31-4031-40高優(yōu)（2）分類：測試數(shù)據用于評估分類規(guī)則的準確率（若準確率可以接受，則規(guī)則可用于新的數(shù)據元組分類）測試數(shù)據分類規(guī)則新數(shù)據(劉賓，31-40，高)信用等級？ 優(yōu)3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n分類與預測的分類與預測的基本知識基本知識n數(shù)據預測數(shù)據預測n預測是構造和使用模型評估無標號樣本類，或預測是構造和使用模型評估無標號樣本類，或評估給定樣本可能具有的屬性值或值區(qū)間評估給定樣本可能具有的屬性值或值區(qū)間n為了提高分類與預測過程的準確性、有效性和為了提高分類與預測過程的準確性、有效性和可伸縮性，可對數(shù)據進行預處理。一般使用：可伸縮性，可

35、對數(shù)據進行預處理。一般使用：數(shù)據清理，相關性分析，數(shù)據變換（概念分層數(shù)據清理，相關性分析，數(shù)據變換（概念分層或規(guī)范化）或規(guī)范化）3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n判定樹判定樹n判定樹是一個類似流程圖的判定樹是一個類似流程圖的樹型結構樹型結構，其中，其中每個每個內部節(jié)點內部節(jié)點表示在一個屬性上的測試，每表示在一個屬性上的測試，每個個分枝分枝代表一個測試輸出，而每個代表一個測試輸出，而每個樹葉節(jié)點樹葉節(jié)點代表類或類分布代表類或類分布n判定樹歸納判定樹歸納是構造判定樹的基本算法。在判是構造判定樹的基本算法。在判定樹構造時，許多分枝可能反映的是訓練數(shù)定

36、樹構造時，許多分枝可能反映的是訓練數(shù)據中的噪聲或孤立點?？捎脫械脑肼暬蚬铝Ⅻc?？捎脴浼糁浼糁Ψ椒z測方法檢測和剪去這類分枝，以提高在未知數(shù)據上分類和剪去這類分枝，以提高在未知數(shù)據上分類的準確性的準確性3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（1）判定樹歸納：以自頂向下遞歸的分）判定樹歸納：以自頂向下遞歸的分而治之方式構造判定樹。算法的基本策而治之方式構造判定樹。算法的基本策略如下：略如下：n判定樹以代表訓練樣本的單個節(jié)點開始判定樹以代表訓練樣本的單個節(jié)點開始n若一個節(jié)點的樣本均為同一類別，則該節(jié)點若一個節(jié)點的樣本均為同一類別，則該節(jié)點成為樹葉，并

37、用該類進行標記成為樹葉，并用該類進行標記3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（1）判定樹歸納：）判定樹歸納：n否則，算法使用信息增益度量作為啟發(fā)信息，否則，算法使用信息增益度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性，作為該選擇能夠最好地將樣本分類的屬性，作為該節(jié)點的節(jié)點的“測試測試”屬性。在此算法中，所有的屬性。在此算法中，所有的屬性都是分類的，即取離散值。對連續(xù)值的屬性都是分類的，即取離散值。對連續(xù)值的屬性必須離散化屬性必須離散化n對測試屬性的每個已知的值，創(chuàng)建一個分枝，對測試屬性的每個已知的值，創(chuàng)建一個分枝，并具此劃分樣本并具此劃分樣本

38、3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（1）判定樹歸納：）判定樹歸納：n算法使用同樣的過程，遞歸地形成每個劃分算法使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。一個屬性一旦出現(xiàn)在某個上的樣本判定樹。一個屬性一旦出現(xiàn)在某個節(jié)點上，就不再考慮該節(jié)點的任何后代節(jié)點上，就不再考慮該節(jié)點的任何后代n遞歸劃分操作僅當下列條件之一成立時停止：遞歸劃分操作僅當下列條件之一成立時停止：na）給定節(jié)點的所有樣本屬于同一類）給定節(jié)點的所有樣本屬于同一類nb）沒有剩余屬性可用來進一步劃分樣本）沒有剩余屬性可用來進一步劃分樣本nc）測試屬性的一個分枝沒有樣本）測試屬性的

39、一個分枝沒有樣本3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（2）屬性選擇方法：）屬性選擇方法：n在判定樹的每個節(jié)點上使用在判定樹的每個節(jié)點上使用信息增益度量信息增益度量選選擇測試屬性。選擇具有擇測試屬性。選擇具有最高信息增益最高信息增益的屬性的屬性作為當前節(jié)點的測試屬性，可以使結果劃分作為當前節(jié)點的測試屬性，可以使結果劃分中的樣本分類需要的信息量最小，并反映劃中的樣本分類需要的信息量最小，并反映劃分的最小隨機性。這種信息論方法使得對一分的最小隨機性。這種信息論方法使得對一個對象分類所需的期望測試數(shù)目達到最小，個對象分類所需的期望測試數(shù)目達到最小，并確保

40、找到一棵簡單的樹。并確保找到一棵簡單的樹。3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n信息增益度量信息增益度量n設設s是訓練樣本的集合，其中每個樣本的類標是訓練樣本的集合，其中每個樣本的類標號已知號已知n假定有假定有m個類，設個類，設s包含包含si個個ci類樣本，類樣本，i=1,2,mn任意一個樣本屬于類任意一個樣本屬于類ci的可能性為的可能性為si /s，其中，其中s是集合是集合s中樣本的總數(shù)。中樣本的總數(shù)。3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n信息增益度量信息增益度量n一個決策樹可用于對數(shù)據對象進行分類一

41、個決策樹可用于對數(shù)據對象進行分類,因此因此決策樹可以看成是決策樹可以看成是ci的一個信息源的一個信息源,為產生相為產生相應信息需要的信息熵（應信息需要的信息熵（entropy）為：）為：sssssssiimiim2121log,3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n信息增益度量信息增益度量n若屬性若屬性a的取值為的取值為a1, a2, an，且該屬性用，且該屬性用作決策樹的一個結點時，則可將作決策樹的一個結點時，則可將s劃分為子集劃分為子集s1, s2, sn。其中。其中sj包含屬性包含屬性a取同一值取同一值aj的數(shù)據行。記的數(shù)據行。記sij為為s

42、j包含類包含類ci的樣本個數(shù)。的樣本個數(shù)。3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n信息增益度量信息增益度量n根據屬性根據屬性a的取值對當前數(shù)據集劃分所獲得的的取值對當前數(shù)據集劃分所獲得的信息就稱為屬性信息就稱為屬性a的熵。它的計算公式如下：的熵。它的計算公式如下： 121 ,2 ,1( ),njjmjjjmjjssse ai ssss 3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n信息增益度量信息增益度量na上該劃分得到的信息增益定義為上該劃分得到的信息增益定義為:： 1,2,( ),( )mgain ai s

43、sse a 3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（2）屬性選擇方法：）屬性選擇方法：n判定樹歸納算法計算每個屬性的信息增益，判定樹歸納算法計算每個屬性的信息增益，并挑選具有最高信息增益的屬性作為給定集并挑選具有最高信息增益的屬性作為給定集合的測試屬性。創(chuàng)建一個節(jié)點，并以該屬性合的測試屬性。創(chuàng)建一個節(jié)點，并以該屬性標記。對屬性的每個值創(chuàng)建分枝，并據此劃標記。對屬性的每個值創(chuàng)建分枝，并據此劃分樣本。分樣本。3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n【例】下表給出一個商場顧客【例】下表給出一個商場顧客db數(shù)據元

44、組數(shù)據元組訓練集，類標號屬性訓練集，類標號屬性buys_compute有兩個有兩個不同值，即不同值，即yes，no ，因此訓練集中有兩，因此訓練集中有兩個不同的類（個不同的類（m= 2）。設類）。設類c1對應于對應于yes，而類而類c2對應對應no。類。類c1有有9個樣本，類個樣本，類c2有有5 個樣本。我們用前面的一組公式計算每個屬個樣本。我們用前面的一組公式計算每個屬性的信息增益。性的信息增益。ridrid年齡年齡收入收入學生學生信用級信用級購買電腦購買電腦1 1=30=30高高nono良良nono2 2=304040中中nono良良yesyes5 54040低低yesyes良良yesye

45、s6 64040低低yesyes優(yōu)優(yōu)nono7 731403140低低yesyes優(yōu)優(yōu)yesyes8 8=30=30中中nono良良nono9 9=304040中中yesyes良良yesyes1111=304040中中nono優(yōu)優(yōu)nono3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n首先計算給定樣本分類所需的信息增益首先計算給定樣本分類所需的信息增益:n接著計算每個屬性的熵接著計算每個屬性的熵,從屬性從屬性age開始開始:0.94145log145149log14959issi2221),(),(0.971ssi 3 s2s30age21112111, :

46、”“0ssi 0 s4s4031age22122212, :”“0.971ssi 2 s3s40age23132313, :”“3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n若樣本按若樣本按age劃分，對一個給定的樣本分類劃分，對一個給定的樣本分類所需的期望信息為：所需的期望信息為：n這種劃分的信息增益是這種劃分的信息增益是: ),(),(),()(0.694ssi145ssi144ssi145agee2313221221110.246ageessiagegain21)(),()(3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹

47、的分類n類似地，可計算：類似地，可計算：n由于由于age在屬性中具有最高信息增益，它被在屬性中具有最高信息增益，它被選作測試屬性。創(chuàng)建一個節(jié)點，用選作測試屬性。創(chuàng)建一個節(jié)點，用age標記，標記，并對每個屬性值引出一個分枝。樣本據此劃并對每個屬性值引出一個分枝。樣本據此劃分，見下圖：分，見下圖：029.0)(incomegain()0.151gain student 048.0)_(ratingcreditgain收入學生?信用級購買?高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

48、收入學生?信用級購買?高no良yes低yes優(yōu)yes中no優(yōu)yes高yes良yes年齡?=30303031-4031-40年齡？學生？信用級？yesyesyesnono=3040noyes良優(yōu)算法返回的最終判定樹如下：3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n判定樹歸納算法被廣泛應用到許多進行分類判定樹歸納算法被廣泛應用到許多進行分類識別的應用領域，這類算法無需相關領域知識別的應用領域，這類算法無需相關領域知識。歸納的學習與分類識別的操作處理速度識。歸納的學習與分類識別的操作處理速度較快，相應的分類準確率較高。較快，相應的分類準確率較高。 3 數(shù)據挖掘功能數(shù)據挖掘功能分類與預測分類與預測n基于判定樹的分類基于判定樹的分類n（3）樹剪枝：）樹剪枝：n在判定樹構造時，許多分枝可能反映的是訓在判定樹構造時，許多分枝可能反映的是訓練數(shù)據中的噪聲或孤立點?？捎脴浼糁Ψ椒ň殧?shù)據中