數(shù)據(jù)挖掘技術(shù)概述

1、大數(shù)據(jù)分析和內(nèi)存計算第4講 數(shù)據(jù)挖掘技術(shù)概述提綱數(shù)據(jù)挖掘概覽數(shù)據(jù)預處理分類（Classification）聚類（Cluster）關(guān)聯(lián)規(guī)則（Association Rule）回歸（Regression）數(shù)據(jù)挖掘概覽What?數(shù)據(jù)挖掘的定義Why?數(shù)據(jù)挖掘的動機How?哪些數(shù)據(jù)可以用來挖掘？數(shù)據(jù)挖掘的主要內(nèi)容數(shù)據(jù)挖掘定義什么是數(shù)據(jù)挖掘（Data Mining）？- Extraction of interesting (non-trivial, implicit, previously unknown and potentially useful) patterns or knowledge fro

2、m huge amount of data - 其他稱謂：Knowledge discovery(mining) in database(KDD), data/pattern analysis, business intelligence, decision-support system, knowledge extraction, data archeology, data dredging and information harvesting etc.DatapreprocessingDataminingpostprocessingknowledgeraw dataFeature sele

3、ctionDimension reductionNormalizationData subsettingFiltering patternsVisuaralizationPattern interpretationData Mining Process模式有效性度量SimplicityE.g., (association) rule length, (decision) tree size CertaintyE.g., confidence, P(A|B) = #(A and B)/ #(B), classification reliability or accuracy, rule stre

4、ngth, etc. UtilityPotential usefulness, e.g., support (association), noise threshold (description) NoveltyNot previously known, surprising (used to remove redundant rules) 為何需要數(shù)據(jù)挖掘？ 數(shù)據(jù)量大 缺乏理論知識 數(shù)據(jù)挖掘可以幫助產(chǎn)生新的假說或者使數(shù)據(jù)變得有意義為何需要數(shù)據(jù)挖掘？ We are drowning in data, but starving in knowledge Data explosion: Autom

5、ated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases, data warehouses, and other information repositories. 苦惱: 淹沒在數(shù)據(jù)中 ; 不能制定合適的決策! n模式模式n趨勢趨勢n事實事實n關(guān)系關(guān)系n模型模型n關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則n序列序列n目標市場目標市場n資金分配資金分配n貿(mào)易選擇貿(mào)易選擇n在哪兒做廣告在哪兒做廣告n銷售

6、的地理位置銷售的地理位置n金融金融n經(jīng)濟經(jīng)濟n政府政府n人口統(tǒng)計人口統(tǒng)計n生命周期生命周期數(shù)據(jù)挖掘的意義數(shù)據(jù)挖掘應用l 銀行 美國銀行家協(xié)會(ABA)預測數(shù)據(jù)倉庫和數(shù)據(jù)挖掘技術(shù)在美國商業(yè)銀行的應用增長率是14.9。 分析客戶使用分銷渠道的情況和分銷渠道的容量 ；建立利潤評測模型；客戶關(guān)系優(yōu)化；風險控制等l 電子商務 網(wǎng)上商品推薦；個性化網(wǎng)頁；自適應網(wǎng)站l 生物制藥、基因研究 DNA序列查詢和匹配；識別基因序列的共發(fā)生性 l 電信 欺詐甄別；客戶流失l 保險、零售數(shù)據(jù)挖掘應用Debt$40KQ QQ QQ QQ QI II I1 12 23 34 45 56 6factor 1factor 2f

7、actor n神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò) Neural Networks Neural Networks聚類分析聚類分析 Clustering ClusteringOpenAccntAdd NewProductDecreaseUsage?Time序列分析序列分析 Sequence Analysis Sequence Analysis決策樹決策樹 Decision Trees Decision Trees 傾向性分析 客戶保留 客戶生命周期管理 目標市場 價格彈性分析 客戶細分 市場細分 傾向性分析 客戶保留 目標市場 欺詐檢測關(guān)聯(lián)分析關(guān)聯(lián)分析 Association Association 市場組合分析

8、 套裝產(chǎn)品分析 目錄設(shè)計 交叉銷售數(shù)據(jù)挖掘步驟數(shù)據(jù)預處理數(shù)據(jù)清理（消除噪音或不一致數(shù)據(jù)，補缺）數(shù)據(jù)集成（多種數(shù)據(jù)源可以組合在一起）數(shù)據(jù)變換（規(guī)范化）數(shù)據(jù)規(guī)約（數(shù)據(jù)簡化）數(shù)據(jù)挖掘算法（使用智能方法提取數(shù)據(jù)模式）分類、聚類、關(guān)聯(lián)分析、回歸預測、文本挖掘質(zhì)量評估（識別提供知識的真正有趣模式）知識表示（可視化和知識表示技術(shù)）數(shù)據(jù)質(zhì)量：為何需要數(shù)據(jù)預處理？數(shù)據(jù)質(zhì)量衡量：準確度:correct or wrong, accurate or not完整度:not recorded unavailable一致性:some modified but some not, dangling時效性:timely upd

9、ate?可信度:how trustable the data are correct?可解釋性:how easily the data can be understood?數(shù)據(jù)挖掘預處理的主要任務數(shù)據(jù)清理 填寫空缺的值，平滑噪聲數(shù)據(jù)，識別、刪除孤立點，解決不一致性數(shù)據(jù)集成 集成多個數(shù)據(jù)庫、數(shù)據(jù)立方體或文件數(shù)據(jù)變換 規(guī)范化和聚集數(shù)據(jù)歸約 得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果數(shù)據(jù)離散化 數(shù)據(jù)歸約的一部分，通過概念分層和數(shù)據(jù)的離散化來規(guī)約數(shù)據(jù)，對數(shù)字型數(shù)據(jù)特別重要數(shù)據(jù)清洗臟數(shù)據(jù)：例如設(shè)備錯誤，人或者機器錯誤，傳輸錯誤等不完整性：屬性值缺失或者只有聚集數(shù)據(jù)p例如：phone=“”

10、;噪音：包含噪聲、錯誤或者異常值p例如：salary=-10不一致性:p例如：age=42，birthday=03-07-2010假值：p例如：使用某一值填補缺失屬性缺失值（Incomplete/Missing Data)數(shù)據(jù)并不總是完整的例如：數(shù)據(jù)庫表中，很多條記錄的對應字段沒有相應值，比如銷售表中的顧客收入引起空缺值的原因設(shè)備異常與其他已有數(shù)據(jù)不一致而被刪除因為誤解而沒有被輸入的數(shù)據(jù)在輸入時，有些數(shù)據(jù)因為得不到重視而沒有被輸入對數(shù)據(jù)的改變沒有進行日志記載空缺值要經(jīng)過推斷而補上如何補充缺失值忽略元組：當類標號缺少時通常這么做（假定挖掘任務設(shè)計分類或描述），當每個屬性缺少值的百分比變化很大時，

11、它的效果非常差。人工填寫空缺值：工作量大，可行性低使用一個全局變量填充空缺值：比如使用unknown或-使用屬性的平均值填充空缺值使用與給定元組屬同一類的所有樣本的平均值使用最可能的值填充空缺值：使用像使用最可能的值填充空缺值：使用像Bayesian公公式或判定樹這樣的基于推斷的方法式或判定樹這樣的基于推斷的方法噪聲數(shù)據(jù) 噪聲：一個測量變量中的隨機錯誤或偏差 引起不正確屬性值的原因 數(shù)據(jù)收集工具的問題 數(shù)據(jù)輸入錯誤 數(shù)據(jù)傳輸錯誤 技術(shù)限制 命名規(guī)則的不一致 其它需要數(shù)據(jù)清理的數(shù)據(jù)問題 重復記錄 不完整的數(shù)據(jù) 不一致的數(shù)據(jù)如何處理噪聲數(shù)據(jù)分箱分箱:first sort data and part

12、ition into (equi-depth) binsthen one can smooth by bin means, smooth by bin median, smooth by bin boundaries, etc.聚類聚類detect and remove outliers人機融合人機融合detect suspicious values and check by human (e.g., deal with possible outliers)回歸回歸smooth by fitting the data into regression functions分箱(Binning)等寬

13、Equal-width (distance) partitioning:Divides the range into N intervals of equal size: uniform gridif A and B are the lowest and highest values of the attribute, the width of intervals will be: W = (B A)/N.The most straightforward, but outliers may dominate presentationSkewed data is not handled well

14、.等深Equal-depth (frequency) partitioning:Divides the range into N intervals, each containing approximately same number of samplesGood data scalingManaging categorical attributes can be tricky.數(shù)據(jù)平滑的分箱方法 price的排序后數(shù)據(jù)（單位：美元）：4，8，15，21，21，24，25，28，34 劃分為（等深的）箱： 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值平滑： 箱

15、1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱邊界平滑： 箱1：4，4，15 箱2：21，21，24 箱3：25，25，34聚類：Cluster Analysis每個簇中的數(shù)據(jù)用其中心值代替忽略孤立點先通過聚類等方法找出孤立點。這些孤立點可能包含有用的信息。人工再審查這些孤立點Regression通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢，這樣可以用一個變量預測另一個變量。 線性回歸 多線性回歸 非線性回歸XY2211XXY33221XXXYxyy = x + 1X1Y1Y1數(shù)據(jù)集成實體識別元數(shù)據(jù)可幫助避免錯誤知識圖譜屬性冗余相關(guān)分析數(shù)據(jù)重復（元組冗余）數(shù)據(jù)值沖突的檢測與處理表示、

16、比例或編碼不同 數(shù)據(jù)變換（規(guī)范化）平滑：去掉數(shù)據(jù)中的噪聲。技術(shù)包括分箱、回歸、聚類。聚集：對數(shù)據(jù)進行匯總或聚集。數(shù)據(jù)泛化（概化）：使用概念分層，用高層概念替換低層或“原始”數(shù)據(jù)。規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間。最小-最大、Z-Score、按小數(shù)定標規(guī)范化。數(shù)據(jù)變換平滑，聚集數(shù)據(jù)概化，規(guī)范化屬性構(gòu)造(特征構(gòu)造)有限區(qū)間的歸一化：無限區(qū)間的歸一化：模糊隸屬度：minmaxminvv-vev-11數(shù)據(jù)規(guī)約海量數(shù)據(jù) 代表性數(shù)據(jù)對海量數(shù)據(jù)進行復雜的數(shù)據(jù)分析和挖掘?qū)⑿枰荛L時間，使得這種分析不現(xiàn)實或不可行。數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近保持原數(shù)據(jù)的完整

17、性。對歸約后的數(shù)據(jù)集挖掘?qū)⒏行?，并產(chǎn)生相同（或幾乎相同）的結(jié)果。數(shù)據(jù)規(guī)約數(shù)據(jù)歸約策略：（1）數(shù)據(jù)立方體聚集：對數(shù)據(jù)立方體做聚集操作（2）屬性子集選擇：檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬性和維。（3）維度歸約：刪除不重要的屬性（4）數(shù)值歸約：用規(guī)模較小的數(shù)據(jù)表示、替換或估計原始數(shù)據(jù)（5）離散化和概念分層產(chǎn)生屬性的原始數(shù)值用區(qū)間值或較高層的概念替換數(shù)據(jù)立方體據(jù)立方體存儲多維聚集信息，提供對預計算的匯總數(shù)據(jù)進行快速訪問。如：立方體內(nèi)存儲季度銷售額，若對年銷售額感興趣，可對數(shù)據(jù)執(zhí)行聚集操作，例如sum()等。屬性子集選擇通過刪除不相關(guān)或冗余的屬性（或維）減小數(shù)據(jù)集。其目標是找出最小屬性集，使得數(shù)據(jù)類

18、的概率分布盡可能地接近使用所有屬性得到的原分布。通過窮舉搜索找出有屬性的最佳子集是不現(xiàn)實的。通常采用壓縮搜索空間的啟發(fā)式算法。如貪心算法：從局部最優(yōu)到全局最優(yōu)。逐步向前選擇逐步向后刪除向前選擇和向后刪除的結(jié)合決策樹歸納維度規(guī)約維度歸約使用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。分為無損和有損兩種。主要方法：串壓縮：無損，但只允許有限的數(shù)據(jù)操作。小波變換（DWT）：有損，適合高維數(shù)據(jù)。主成分分析（PCA）：有損，能更好地處理稀疏數(shù)據(jù)。數(shù)值規(guī)約通過選擇替代的、“較小的”數(shù)據(jù)表示形式來減少數(shù)據(jù)量?？梢苑譃閰?shù)方法和非參數(shù)方法。參數(shù)方法：回歸（regression ）和對數(shù)線性模型非參數(shù)方

19、法：直方圖、聚類、抽樣離散化離散化的用途：（1）適應某些僅接受離散值的算法；（2）減小數(shù)據(jù)的尺度。離散化的方法包括幾下幾種。（1）等距分割；（2）聚類分割；（3）直方圖分割；（4）基于熵的分割； （5）基于自然屬性的分割。抽樣用數(shù)據(jù)的小得多的隨機樣本（子集）不是大型數(shù)據(jù)集。抽樣方法s個樣本無放回簡單隨機抽樣s個樣本有放回簡單隨機抽樣聚類抽樣分層抽樣分類分類分類是指將數(shù)據(jù)映射到預先定義好的群組或類。在分析測試數(shù)據(jù)之前，類別就已經(jīng)被確定了，所以分類統(tǒng)稱被稱作有指導的學習。分類算法要求基于數(shù)據(jù)屬性來定義類別。分類算法通常通過觀察已知所屬類別的數(shù)據(jù)的特征來描述類別。分類應用分類具有廣泛的應用，例如醫(yī)療

20、診斷、信用卡系統(tǒng)的信用分級、圖像模式識別等。為了識別乘客是否是潛在的恐怖分子或罪犯，機場安全攝像站需要對乘客的臉部進行掃描并辨識臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀），然后將得到的模式與數(shù)據(jù)庫中的已知恐怖分子或罪犯的模式進行逐個比較，看看是否與其中的某一模式相匹配。分類步驟1建立一個模型，描述預定的數(shù)據(jù)類集或概念集數(shù)據(jù)元組也稱作樣本、實例或?qū)ο?。為建立模型而被分析的?shù)據(jù)元組形成訓練數(shù)據(jù)集。訓練數(shù)據(jù)集中的單個元組稱作訓練樣本，假定每個元組屬于一個預定義的類，由一個稱作類標號。通過分析訓練數(shù)據(jù)集來構(gòu)造分類模型，可用分類規(guī)則、決策樹或數(shù)學公式等形式提供。2. 使用模型進行分類首先評

21、估模型（分類法）的預測準確率。p將已知的類標號與該樣本的學習模型類預測比較p準確率等于測試集的樣本中被模型正確分類的百分比p測試集應該與訓練集的內(nèi)容相互獨立，否則會出現(xiàn)過分適應的情況如果認為模型的準確率可以接受，就可以用它對類標號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。（1）模型的構(gòu)建TrainingDataClassificationAlgorithmsIF rank = professorOR years 6THEN tenured = yes Classifier(Model)NAME RANKYEARSTENUREDMikeAssistant Prof3noMaryAssistant Prof7

22、yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no（2）利用模型分類ClassifierTestingDataN A M ER A N KY E A R S TE N U R E DTomA ssistant P rof2noM erlisaA ssociate P rof7noG eorge P rofessor5yesJoseph A ssistant P rof7yesUnseen Data(Jeff, Professor, 4)Tenured?分類方法評價預測的準確率l

23、這涉及模型正確地預測新的或先前未見過的數(shù)據(jù)的類標號的能力速度l構(gòu)造模型的速度l利用模型進行分類的速度強壯性l給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預測的能力可伸縮性l當給定大量數(shù)據(jù)時，有效地構(gòu)造模型的能力可解釋性 l涉及學習模型提供的理解和洞察的層次分類器性能評價方式 準確率和召回率 - 混淆矩陣等 給定一個類Cj和一個數(shù)據(jù)庫元組ti，ti可能被分類器判定為屬于Cj或不屬于Cj，其實ti本身可能屬于Cj或不屬于Cj，這樣就會產(chǎn)生如下一些情況：真正: 判定ti在Cj中，實際上的確在其中。假正: 判定ti在Cj中，實際上不在其中。真負: 判定ti不在Cj中，實際上不在其中。假負: 判定ti不在C

24、j中，實際上的確在其中。準確率:P=A/(A+B)召回率:R=A/(A+C)評估分類方法的準確性保持方法給定數(shù)據(jù)隨機劃分為兩個集合：訓練集(2/3)和測試集(1/3)訓練集導出分類法，測試集對其準確性進行評估k-折交叉驗證初始數(shù)據(jù)被劃分為k個不相交的，大小大致相同的子集S1,S2Sk進行k次訓練和測試，第i次時，以Si做測試集，其他做訓練集準確率為k次迭代正確分類數(shù)除以初始數(shù)據(jù)集樣本總數(shù)分類方法基于距離的分類方法與一個類中的成員和另一個類中的成員之間的相似性相比，被映射到同一個類中的成員彼此之間被認為是更加相似的。相似性（距離）度量可以用來識別數(shù)據(jù)庫中不同成員之間的“相似程度”。基于距離的分類

25、方法的直觀解釋（a）類定義）類定義（b）待分類樣例）待分類樣例（c）分類結(jié)果）分類結(jié)果距離計算方法閔可夫斯基距離:當p=2時，為歐幾里得距離當p=1時，為曼哈頓距離當p-時，為切比雪夫距離向量內(nèi)積：夾角余弦：Jaccard：還有信息熵、相關(guān)系數(shù)等其他的度量方法(|xi-yi|pi1n)1/pInner(x,y) x,y xiyiicosqx1x2y1y2x12y12x22y22J(A,B)|AB|AB|基于距離的分類方法的一般性描述 算法算法 基于距離的分類算法基于距離的分類算法 輸入：每個類的中心輸入：每個類的中心C1，Cm；待分類的元組；待分類的元組t。 輸出：輸出類別輸出：輸出類別c。

26、（1）dist=；/距離初始化距離初始化（2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN（4）cCi； （5）distdist(Ci，t)； （6） END. 算法通過對每個元組和各個類的中心來比較，從而可算法通過對每個元組和各個類的中心來比較，從而可以找出他的最近的類中心，得到確定的類別標記。以找出他的最近的類中心，得到確定的類別標記。K近鄰算法（KNN） K K Nearest neighbor(KNN)Nearest neighbor(KNN)通過計算每個訓練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個訓練數(shù)據(jù)，K個數(shù)據(jù)中哪個

27、類別的訓練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個類別。訓練樣本用n維數(shù)值屬性描述。每個樣本代表n維空間的一個點。所有的訓練樣本都放在n維模式空間中。給定一個樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的k個訓練樣本。K近鄰算法（KNN） 要求的信息要求的信息訓練集訓練集距離計算值距離計算值要獲取的最鄰近的鄰居的數(shù)目要獲取的最鄰近的鄰居的數(shù)目k k 一個未知的記錄進行分類一個未知的記錄進行分類計算與其它訓練記錄之間的距離計算與其它訓練記錄之間的距離識別出識別出k k個最近的鄰居個最近的鄰居使用最近鄰居的類標號來標識未知元組的類（使用最近鄰居的類標號來標識未知元組的類（by taking b

28、y taking majority votemajority vote）K近鄰算法（KNN）算法算法 K-近鄰分類算法近鄰分類算法輸入：輸入： 訓練數(shù)據(jù)訓練數(shù)據(jù)T；近鄰數(shù)目；近鄰數(shù)目K；待分類的元組；待分類的元組t。 輸出：輸出： 輸出類別輸出類別c。 （1）N= ；（2）FOR each d T DO BEGIN（3） IF |N|K THEN（4） N=Nd； （5） ELSE（6） IF uN such that sim(t，u)40000高負債高負債工作時間工作時間5年年是是否否是是否否“年收入大于￥40000”并且“高負債”的用戶被認為是“高風險”；“年收入小于￥40000”但“工作

29、時間大于5年”的申請，是“低風險”；NYYNNY決策樹buys_computer的決策樹示意的決策樹示意 Age? Credit_rating? student? yes no yesyes no 40 3040yes no fairexcellent 決策樹l決策樹（決策樹（decision treedecision tree）l19861986年年 Quinlan Quinlan提出了著名的提出了著名的ID3ID3算法。算法。l在在ID3ID3算法的基礎(chǔ)上，算法的基礎(chǔ)上，19931993年年QuinlanQuinlan又提出了又提出了C4.5C4.5算法算法。l為了適應處理大規(guī)模數(shù)據(jù)集的需

30、要，后來又提出了若為了適應處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進的算法，其中干改進的算法，其中SLIQ (super-vised learning in quest)SLIQ (super-vised learning in quest)和和SPRINT (scalable parallelizableSPRINT (scalable parallelizable induction of decision induction of decision trees)trees)是比較有代表性的兩個算法。是比較有代表性的兩個算法。決策樹的步驟使用決策樹進行分類分為兩步：使用決策樹進行分類分為

31、兩步：第1步：利用訓練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進行機器學習的過程。第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進行分類。對輸入的記錄，從根結(jié)點依次測試記錄的屬性值，直到到達某個葉結(jié)點，從而找到該記錄所在的類。決策樹算法遞歸執(zhí)行的終止條件（停止分支的條件）算法遞歸執(zhí)行的終止條件（停止分支的條件）對于給定的節(jié)點，對于給定的節(jié)點，所有的例子都屬于同一個類所有的例子都屬于同一個類雖然對于某一個節(jié)點當前的例子不屬于同一個類，但雖然對于某一個節(jié)點當前的例子不屬于同一個類，但是已經(jīng)是已經(jīng)沒有屬性沒有屬性可用來選擇繼續(xù)進行分支處理可用來選擇繼續(xù)進行分支處理分裂屬

32、性選擇選擇屬性的方法選擇屬性的方法選擇具有選擇具有最大信息增益最大信息增益的屬性作為當前節(jié)點的的屬性作為當前節(jié)點的測試屬性測試屬性該屬性使得對結(jié)果劃分中的樣本分類所需的該屬性使得對結(jié)果劃分中的樣本分類所需的信信息量最小息量最小，并反映劃分的最小隨機性。，并反映劃分的最小隨機性。用信息增益這種用信息增益這種信息論信息論的理論方法，使得對一的理論方法，使得對一個對象分類所需要的期望測試數(shù)目達到最小，個對象分類所需要的期望測試數(shù)目達到最小，并確保找到一棵簡單的樹。并確保找到一棵簡單的樹。分裂屬性選擇怎樣計算信息增益（怎樣計算信息增益（information gaininformation gain）

33、信息增益被定義為信息增益被定義為原始分割的熵原始分割的熵與劃分以后各與劃分以后各分割的熵分割的熵累加得到的總熵之間的差。累加得到的總熵之間的差。信息增益信息增益是指劃分前后進行正確預測所需的是指劃分前后進行正確預測所需的信信息量之差息量之差。選擇具有選擇具有最高信息增益最高信息增益的屬性作為當前節(jié)點的的屬性作為當前節(jié)點的測試屬性。測試屬性。信息增益的計算 設(shè)S是有s個訓練樣本數(shù)據(jù)的集合，類標號屬性具有m個不同值，定義m個不同類Ci（i=1,2,m），si是類Ci中的樣本數(shù)，則對一個給定的訓練樣本分類所需要的期望信息為： -miiimppsssI1221log,其中其中p pi i是任意樣本屬于

34、是任意樣本屬于C Ci i的概率，可用的概率，可用s si i/s/s來估計來估計決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買

35、32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買決策屬性“買計算機？”。該屬性分兩類：買/不買S1(買)=641 S2（不買）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537第第1步計算決策屬性的熵步計算決策屬性的熵決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中

36、否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2步計算條件屬性的熵步計算條件屬性的熵條件屬性共有4個。分別是年齡、收入、學生、信譽。分別計算不同屬性的信息增益。決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-1步計算年齡的熵步計算年齡的熵年齡共分三個組： 青年、中年、老年青年買與不買

37、比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-2步計算年齡的熵步計算年齡的熵年齡共分三個

38、組： 青年、中年、老年中年買與不買比例為256/0S1(買)=256 S2（不買）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-3步計算年齡的熵步計算年齡的熵年齡

39、共分三個組： 青年、中年、老年老年買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第2-4

40、步計算年齡的熵步計算年齡的熵年齡共分三個組： 青年、中年、老年所占比例青年組 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）決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32

41、中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第3步計算收入的熵步計算收入的熵收入共分三個組： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 (2)決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第4步計算學生的熵步計算學生的熵學生共分二個組： 學生、非學生E（學生）=0.7811年齡信息增益=0.9

42、537-0.7811 =0.1726 （3）決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第5步計算信譽的熵步計算信譽的熵信譽分二個組： 良好，優(yōu)秀E（信譽）= 0.9048信譽信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中

43、否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第第6步計算選擇節(jié)點步計算選擇節(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）決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)

44、買年齡年齡青年中年老年買/不買買買/不買葉子決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如

45、果選擇收入作為節(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.4591I(0,128)=0 比例: 128/384=0.3333I(64,128)=0.9183 比例: 192/384=0.5I(64,0)=0比例: 64/384=0.1667 注意決策樹算法計數(shù)年齡收入學生信譽歸類：買計算機？歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是

46、優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買年齡年齡青年中年老年學生買信譽葉子否否是是優(yōu)優(yōu)良良買不買買/不買買葉子葉子葉子決策樹分類規(guī)則提取 決策樹所表示的分類知識可以被抽取出來并可用IF-THEN 分類規(guī)則形式加以表示。 從決策樹的根結(jié)點到任一個葉結(jié)點所形成的一條路徑就構(gòu)成了一條分類規(guī)則。 沿著決策樹的一條路徑所形成的屬性-值對就構(gòu)成了分類規(guī)則條件部分（IF 部分）中的一個合取項，葉結(jié)點所標記的類別就構(gòu)成了規(guī)則的結(jié)論內(nèi)容（THEN 部分）。 IF-THEN分類規(guī)則表達方式易于被人理解，且當決策樹較

47、大時， IF-THEN規(guī)則表示形式的優(yōu)勢就更加突出。貝葉斯分類貝葉斯分類貝葉斯定理 貝葉斯定理給出了如下計算P(C|X)的簡單有效的方法: P(C):是先驗概率，或稱C的先驗概率。 P(X): 樣本數(shù)據(jù)被觀察的概率。 P(X|C)代表假設(shè)C成立的情況下，觀察到X的概率。 P(C|X)是后驗概率，或稱條件X下C的后驗概率。 后驗概率P(C|X) 比先驗概率P(C)基于更多的信息。 P(C)是獨立于X的。P(C|X)P(X|C)P(C)P(X)樸素貝葉斯分類l樸素貝葉斯分類的工作過程如下：(1)每個數(shù)據(jù)樣本用一個n維特征向量X=x1,x2xn表示，分別描述n個屬性A1，An樣本的n個度量。(2)假

48、定有m個類C1，C2，Cm，給定一個未知的數(shù)據(jù)樣本X（即沒有類標號），分類器將預測X屬于具有最高后驗概率（條件X下）的類。樸素貝葉斯分類將未知的樣本分配給類Ci（1im）當且僅當P(Ci|X)P(Cj|X)，ji。即最大化P(Ci|X)P(Ci|X)最大的類Ci稱為最大后驗假定。樸素貝葉斯分類(3)由于P(X)對于所有類為常數(shù)，P(X|Ci)*P(Ci)最大即可。如果Ci類的先驗概率未知，則通常假定這些類是等概率的，即P(C1)=P(C2)=P(Cm)，因此問題就轉(zhuǎn)換為對P(X|Ci)的最大化（P(X|Ci)常被稱為給定Ci時數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設(shè)Ci稱為最大似然假設(shè)）。

49、否則，需要最大化P(X|Ci)*P(Ci)。類的先驗概率可以用P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數(shù)，而s是訓練樣本總數(shù)。)()()|()|(XPCPCXPXCPiii樸素貝葉斯分類（4）給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci)的開銷可能非常大。為降低計算P(X|Ci)的開銷，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性值相互條件獨立，即在屬性間，不存在依賴關(guān)系。這樣)|()|(1inkkiCxPCXP概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)由訓練樣本估值。- 如果Ak是離散屬性，則P(xk|Ci)=sik/si，其中sik是在屬性Ak上具有值x

50、k的類Ci的訓練樣本數(shù)，si是Ci中的訓練樣本數(shù)。 - 如果Ak是連續(xù)值屬性，常用的處理方法有兩種：一是對其離散化，然后按照離散值處理；另一種假定這一屬性服從某一分布，通常假定該屬性服從高斯分布。( 5 ) 對 未 知 樣 本X分 類 ， 也 就 是 對 每 個 類Ci， 計 算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當且僅當P(Ci|X) P(Cj|X)，1jm，ji。即X被指派到其P(X|Ci)*P(Ci)最大的類。樸素貝葉斯分類舉例希望分類的未知樣本為希望分類的未知樣本為:X=（age=“=30”，income=“medium”，student=“yes”，credit_rat

51、ing=“fair”）思路思路:計算每一個類的計算每一個類的P(Ci|X)=P(X|Ci)P(Ci)/P(X) , Ci代表任意一個代表任意一個類，類，X代表需要判斷的代表需要判斷的查詢條件查詢條件樸素貝葉斯分類舉例設(shè) C1對應于類buys_computer=“yes”， C2對應于類buys_computer=“no”。(1) 需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算：P(buys_computer=”yes”)=9/14=0.643，P(buys_computer=”no”)=5/14=0.357。 樸素貝葉斯分類舉例(2) 為計算P

52、(X|Ci)，i=1，2，計算下面的條件概率：P(age=30|buys_computer=“yes” )=2/9=0.222，P(age=30”|buys_computer=“no” )=3/5=0.600，P(income=“medium”|buys_computer=“yes” )=4/9=0.444，P(income=“medium”|buys_computer=“no” )=2/5=0.400，P(student=“yes”|buys_computer=“yes” )=6/9=0.677，P(student=“yes”|buys_computer=“no” )=1/5=0.200，P

53、(credit_rating=“fair”|buys_computer=“yes” )=6/9=0.667，P(credit_rating=“fair”|buys_computer=“no” )=2/5=0.400。 樸素貝葉斯分類舉例 (3) 假設(shè)條件獨立性，使用以上概率，得到：P(X|buys_computer=“yes” )=0.222*0.444*0.667*0.667=0.044，P(X|buys_computer=“no” )=0.600*0.400*0.200*0.400=0.019，P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=

54、 0.044*0.643=0.028，P(X|buys_computer=“no”)*P(buys_computer=“no”)= 0.019*0.357=0.007。因此，對于樣本因此，對于樣本X，樸素貝葉斯分類預測，樸素貝葉斯分類預測buys_computer=“yes”X=（age=“ Head support, confidence”buys(x, “diapers”) = buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) = grade(x, “A”) 1%, 75%查找所有的規(guī)則 X & Y = Z 具有最小支持

55、度和可信度支持度, s, 一次交易中包含X 、 Y 、 Z的可能性可信度, c, 包含X 、 Y的交易中也包含Z的條件概率交易ID購買的商品2000A,B,C1000A,C4000A,D5000B,E,F買尿布的客買尿布的客戶戶二者都買二者都買的客戶的客戶買啤酒的客戶買啤酒的客戶關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的最小最小支持度和最小可信度來尋找強關(guān)聯(lián)規(guī)則。支持度和最小可信度來尋找強關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：1.1.發(fā)現(xiàn)頻繁項目集發(fā)現(xiàn)頻繁項目集: :通過用戶給定通過用戶給定最小支持度最小支持度，尋，尋找

56、所有頻繁項目集或者最大頻繁項目集。找所有頻繁項目集或者最大頻繁項目集。2.2.生成關(guān)聯(lián)規(guī)則生成關(guān)聯(lián)規(guī)則: :通過用戶給定通過用戶給定最小可信度最小可信度，在頻，在頻繁項目集中，尋找關(guān)聯(lián)規(guī)則。繁項目集中，尋找關(guān)聯(lián)規(guī)則。第第1 1個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點。重點。Apriori算法是通過項目集元素數(shù)目不斷增長來完成頻繁項目算法是通過項目集元素數(shù)目不斷增長來完成頻繁項目集發(fā)現(xiàn)的。首先產(chǎn)生集發(fā)現(xiàn)的。首先產(chǎn)生1_頻繁項目集頻繁項目集L1，然后產(chǎn)生，然后產(chǎn)生2_頻繁項頻繁項目集目集L2，直到不能再擴展頻繁項目集的元素數(shù)目為止。，直到不能再擴展頻繁項目集

57、的元素數(shù)目為止。TIDItemset1001，3，42002，3，53001，2，3，54002，5 1994年，年，Agrawal 等人提出了著名的等人提出了著名的Apriori 算法。算法。Apriori算法例子算法例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4 C1：1-候選集候選集 L1：1-頻繁項目集頻繁項目集C2：2-候選集候選集 L2：2-頻繁項目集頻繁項目集C3：3-候選集候選集 L3：3-頻繁項目集頻繁項目集C4：4-

58、候選集候選集 L4：4-頻繁項目集頻繁項目集L3是最大頻繁項目集是最大頻繁項目集 根據(jù)上面介紹的關(guān)聯(lián)規(guī)則挖掘的兩個步驟，在得到了根據(jù)上面介紹的關(guān)聯(lián)規(guī)則挖掘的兩個步驟，在得到了所有頻繁項目集后，可以按照下面的步驟生成關(guān)聯(lián)規(guī)則：所有頻繁項目集后，可以按照下面的步驟生成關(guān)聯(lián)規(guī)則：對于每一個頻繁項目集對于每一個頻繁項目集 l ，生成其所有的非空子集；，生成其所有的非空子集；對于對于l 的每一個非空子集的每一個非空子集x，計算，計算Conference（x），如果），如果Confidence（x）minconfidence，那么，那么“ x(l-x) ”成立成立。 關(guān)聯(lián)規(guī)則生成算法關(guān)聯(lián)規(guī)則生成算法: 從

59、給定的頻繁項目集中生成強關(guān)聯(lián)規(guī)則從給定的頻繁項目集中生成強關(guān)聯(lián)規(guī)則 該算法的核心是該算法的核心是genrules遞歸過程，它實現(xiàn)一個頻繁項目集遞歸過程，它實現(xiàn)一個頻繁項目集中所有強關(guān)聯(lián)規(guī)則的生成。中所有強關(guān)聯(lián)規(guī)則的生成。Rule-generate（L，minconf）（1） FOR each frequent itemset lk in L（2） genrules（ lk ， lk）;關(guān)聯(lián)規(guī)則的生成問題關(guān)聯(lián)規(guī)則的生成問題Rule-generate算法例子Minconfidence=80%序號序號lkxm-1ConfidenceSupport規(guī)則（是否是強規(guī)則）規(guī)則（是否是強規(guī)則）1235267

60、%50%235（否）（否）2235367%50%325（否）（否）3235567%50%523（否）（否）423523100%50%235（是）（是）52352567%50%253（否）（否）623535100%50%352（是）（是）包含包含2,35的事務與包含的事務與包含2的的事務的比值事務的比值,即即2:3同時滿足支持同時滿足支持度和可信度度和可信度TIDItemset1001，3，42002，3，53001，2，3，54002，5算法問題算法問題Apriori作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。掘中具有里程碑的作用。Apriori算