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

1、大數(shù)據(jù)分析和內(nèi)存計(jì)算第4講 數(shù)據(jù)挖掘技術(shù)概述提綱數(shù)據(jù)挖掘概覽數(shù)據(jù)預(yù)處理分類（Classification）聚類（Cluster）關(guān)聯(lián)規(guī)則（Association Rule）回歸（Regression）數(shù)據(jù)挖掘概覽What?數(shù)據(jù)挖掘的定義Why?數(shù)據(jù)挖掘的動(dòng)機(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í) 數(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趨勢(shì)趨勢(shì)n事實(shí)事實(shí)n關(guān)系關(guān)系n模型模型n關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則n序列序列n目標(biāo)市場(chǎng)目標(biāo)市場(chǎng)n資金分配資金分配n貿(mào)易選擇貿(mào)易選擇n在哪兒做廣告在哪兒做廣告n銷售

6、的地理位置銷售的地理位置n金融金融n經(jīng)濟(jì)經(jīng)濟(jì)n政府政府n人口統(tǒng)計(jì)人口統(tǒng)計(jì)n生命周期生命周期數(shù)據(jù)挖掘的意義數(shù)據(jù)挖掘應(yīng)用l 銀行 美國(guó)銀行家協(xié)會(huì)(ABA)預(yù)測(cè)數(shù)據(jù)倉(cāng)庫和數(shù)據(jù)挖掘技術(shù)在美國(guó)商業(yè)銀行的應(yīng)用增長(zhǎng)率是14.9。 分析客戶使用分銷渠道的情況和分銷渠道的容量 ；建立利潤(rùn)評(píng)測(cè)模型；客戶關(guān)系優(yōu)化；風(fēng)險(xiǎn)控制等l 電子商務(wù) 網(wǎng)上商品推薦；個(gè)性化網(wǎng)頁；自適應(yīng)網(wǎng)站l 生物制藥、基因研究 DNA序列查詢和匹配；識(shí)別基因序列的共發(fā)生性 l 電信 欺詐甄別；客戶流失l 保險(xiǎn)、零售數(shù)據(jù)挖掘應(yīng)用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 傾向性分析 客戶保留 客戶生命周期管理 目標(biāo)市場(chǎng) 價(jià)格彈性分析 客戶細(xì)分 市場(chǎng)細(xì)分 傾向性分析 客戶保留 目標(biāo)市場(chǎng) 欺詐檢測(cè)關(guān)聯(lián)分析關(guān)聯(lián)分析 Association Association 市場(chǎng)組合分析

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

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

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

11、它的效果非常差。人工填寫空缺值：工作量大，可行性低使用一個(gè)全局變量填充空缺值：比如使用unknown或-使用屬性的平均值填充空缺值使用與給定元組屬同一類的所有樣本的平均值使用最可能的值填充空缺值：使用像使用最可能的值填充空缺值：使用像Bayesian公公式或判定樹這樣的基于推斷的方法式或判定樹這樣的基于推斷的方法噪聲數(shù)據(jù) 噪聲：一個(gè)測(cè)量變量中的隨機(jī)錯(cuò)誤或偏差 引起不正確屬性值的原因 數(shù)據(jù)收集工具的問題 數(shù)據(jù)輸入錯(cuò)誤 數(shù)據(jù)傳輸錯(cuò)誤 技術(shù)限制 命名規(guī)則的不一致 其它需要數(shù)據(jù)清理的數(shù)據(jù)問題 重復(fù)記錄 不完整的數(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人機(jī)融合人機(jī)融合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每個(gè)簇中的數(shù)據(jù)用其中心值代替忽略孤立點(diǎn)先通過聚類等方法找出孤立點(diǎn)。這些孤立點(diǎn)可能包含有用的信息。人工再審查這些孤立點(diǎn)Regression通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢(shì)，這樣可以用一個(gè)變量預(yù)測(cè)另一個(gè)變量。 線性回歸 多線性回歸 非線性回歸XY2211XXY33221XXXYxyy = x + 1X1Y1Y1數(shù)據(jù)集成實(shí)體識(shí)別元數(shù)據(jù)可幫助避免錯(cuò)誤知識(shí)圖譜屬性冗余相關(guān)分析數(shù)據(jù)重復(fù)（元組冗余）數(shù)據(jù)值沖突的檢測(cè)與處理表示、

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

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

18、的概率分布盡可能地接近使用所有屬性得到的原分布。通過窮舉搜索找出有屬性的最佳子集是不現(xiàn)實(shí)的。通常采用壓縮搜索空間的啟發(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 ）和對(duì)數(shù)線性模型非參數(shù)方

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

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

21、估模型（分類法）的預(yù)測(cè)準(zhǔn)確率。p將已知的類標(biāo)號(hào)與該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較p準(zhǔn)確率等于測(cè)試集的樣本中被模型正確分類的百分比p測(cè)試集應(yīng)該與訓(xùn)練集的內(nèi)容相互獨(dú)立，否則會(huì)出現(xiàn)過分適應(yīng)的情況如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對(duì)類標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類。（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?分類方法評(píng)價(jià)預(yù)測(cè)的準(zhǔn)確率l

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

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

25、方法的直觀解釋（a）類定義）類定義（b）待分類樣例）待分類樣例（c）分類結(jié)果）分類結(jié)果距離計(jì)算方法閔可夫斯基距離:當(dāng)p=2時(shí)，為歐幾里得距離當(dāng)p=1時(shí)，為曼哈頓距離當(dāng)p-時(shí)，為切比雪夫距離向量?jī)?nèi)積：夾角余弦：Jaccard：還有信息熵、相關(guān)系數(shù)等其他的度量方法(|xi-yi|pi1n)1/pInner(x,y) x,y xiyiicosqx1x2y1y2x12y12x22y22J(A,B)|AB|AB|基于距離的分類方法的一般性描述 算法算法 基于距離的分類算法基于距離的分類算法 輸入：每個(gè)類的中心輸入：每個(gè)類的中心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. 算法通過對(duì)每個(gè)元組和各個(gè)類的中心來比較，從而可算法通過對(duì)每個(gè)元組和各個(gè)類的中心來比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。以找出他的最近的類中心，得到確定的類別標(biāo)記。K近鄰算法（KNN） K K Nearest neighbor(KNN)Nearest neighbor(KNN)通過計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)

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

28、y taking majority votemajority vote）K近鄰算法（KNN）算法算法 K-近鄰分類算法近鄰分類算法輸入：輸入： 訓(xùn)練數(shù)據(jù)訓(xùn)練數(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高負(fù)債高負(fù)債工作時(shí)間工作時(shí)間5年年是是否否是是否否“年收入大于￥40000”并且“高負(fù)債”的用戶被認(rèn)為是“高風(fēng)險(xiǎn)”；“年收入小于￥40000”但“工作

29、時(shí)間大于5年”的申請(qǐng)，是“低風(fēng)險(xiǎn)”；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為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需

30、要，后來又提出了若為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進(jìn)的算法，其中干改進(jìn)的算法，其中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)是比較有代表性的兩個(gè)算法。是比較有代表性的兩個(gè)算法。決策樹的步驟使用決策樹進(jìn)行分類分為兩步：使用決策樹進(jìn)行分類分為

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

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

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

34、是任意樣本屬于C Ci i的概率，可用的概率，可用s si i/s/s來估計(jì)來估計(jì)決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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)買決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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)買決策屬性“買計(jì)算機(jī)？”。該屬性分兩類：買/不買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步計(jì)算決策屬性的熵步計(jì)算決策屬性的熵決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算條件屬性的熵步計(jì)算條件屬性的熵條件屬性共有4個(gè)。分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算年齡的熵步計(jì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年青年買與不買

37、比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算年齡的熵步計(jì)算年齡的熵年齡共分三個(gè)

38、組： 青年、中年、老年中年買與不買比例為256/0S1(買)=256 S2（不買）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算年齡的熵步計(jì)算年齡的熵年齡

39、共分三個(gè)組： 青年、中年、老年老年買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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、步計(jì)算年齡的熵步計(jì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年所占比例青年組 384/1025=0.375中年組 256/1024=0.25老年組 384/1024=0.375計(jì)算年齡的平均信息期望E（年齡）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877G（年齡信息增益） =0.9537-0.6877 =0.2660 （1）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算收入的熵步計(jì)算收入的熵收入共分三個(gè)組： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 (2)決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算學(xué)生的熵步計(jì)算學(xué)生的熵學(xué)生共分二個(gè)組： 學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9

42、537-0.7811 =0.1726 （3）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算信譽(yù)的熵步計(jì)算信譽(yù)的熵信譽(yù)分二個(gè)組： 良好，優(yōu)秀E（信譽(yù)）= 0.9048信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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步計(jì)算選擇節(jié)點(diǎn)步計(jì)算選擇節(jié)點(diǎn) 年齡信息增益=0.9537-0.6877 =0.2660 （1）收入信息增益=0.9537-0.9361 =0.0176 （2）年齡信息增益=0.9537-0.7811 =0.1726 （3）信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)

44、買年齡年齡青年中年老年買/不買買買/不買葉子決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如

45、果選擇收入作為節(jié)點(diǎn)分高、中、低平均信息期望（加權(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 注意決策樹算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？歸類：買計(jì)算機(jī)？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)買年齡年齡青年中年老年學(xué)生買信譽(yù)葉子否否是是優(yōu)優(yōu)良良買不買買/不買買葉子葉子葉子決策樹分類規(guī)則提取 決策樹所表示的分類知識(shí)可以被抽取出來并可用IF-THEN 分類規(guī)則形式加以表示。 從決策樹的根結(jié)點(diǎn)到任一個(gè)葉結(jié)點(diǎn)所形成的一條路徑就構(gòu)成了一條分類規(guī)則。 沿著決策樹的一條路徑所形成的屬性-值對(duì)就構(gòu)成了分類規(guī)則條件部分（IF 部分）中的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)所標(biāo)記的類別就構(gòu)成了規(guī)則的結(jié)論內(nèi)容（THEN 部分）。 IF-THEN分類規(guī)則表達(dá)方式易于被人理解，且當(dāng)決策樹較

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

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

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

50、k的類Ci的訓(xùn)練樣本數(shù)，si是Ci中的訓(xùn)練樣本數(shù)。 - 如果Ak是連續(xù)值屬性，常用的處理方法有兩種：一是對(duì)其離散化，然后按照離散值處理；另一種假定這一屬性服從某一分布，通常假定該屬性服從高斯分布。( 5 ) 對(duì) 未 知 樣 本X分 類 ， 也 就 是 對(duì) 每 個(gè) 類Ci， 計(jì) 算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當(dāng)且僅當(dāng)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”）思路思路:計(jì)算每一個(gè)類的計(jì)算每一個(gè)類的P(Ci|X)=P(X|Ci)P(Ci)/P(X) , Ci代表任意一個(gè)代表任意一個(gè)類，類，X代表需要判斷的代表需要判斷的查詢條件查詢條件樸素貝葉斯分類舉例設(shè) C1對(duì)應(yīng)于類buys_computer=“yes”， C2對(duì)應(yīng)于類buys_computer=“no”。(1) 需要最大化P(X|Ci)*P(Ci)，i=1，2。每個(gè)類的先驗(yàn)概率P(Ci)可以根據(jù)訓(xùn)練樣本計(jì)算：P(buys_computer=”yes”)=9/14=0.643，P(buys_computer=”no”)=5/14=0.357。 樸素貝葉斯分類舉例(2) 為計(jì)算P

52、(X|Ci)，i=1，2，計(jì)算下面的條件概率：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è)條件獨(dú)立性，使用以上概率，得到：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。因此，對(duì)于樣本因此，對(duì)于樣本X，樸素貝葉斯分類預(yù)測(cè)，樸素貝葉斯分類預(yù)測(cè)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購(gòu)買的商品2000A,B,C1000A,C4000A,D5000B,E,F買尿布的客買尿布的客戶戶二者都買二者都買的客戶的客戶買啤酒的客戶買啤酒的客戶關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的最小最小支持度和最小可信度來尋找強(qiáng)關(guān)聯(lián)規(guī)則。支持度和最小可信度來尋找強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)子問題：關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)子問題：1.1.發(fā)現(xiàn)頻繁項(xiàng)目集發(fā)現(xiàn)頻繁項(xiàng)目集: :通過用戶給定通過用戶給定最小支持度最小支持度，尋，尋找

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

57、的元素?cái)?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-頻繁項(xiàng)目集頻繁項(xiàng)目集C2：2-候選集候選集 L2：2-頻繁項(xiàng)目集頻繁項(xiàng)目集C3：3-候選集候選集 L3：3-頻繁項(xiàng)目集頻繁項(xiàng)目集C4：4-

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

59、給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則從給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則 該算法的核心是該算法的核心是genrules遞歸過程，它實(shí)現(xiàn)一個(gè)頻繁項(xiàng)目集遞歸過程，它實(shí)現(xiàn)一個(gè)頻繁項(xiàng)目集中所有強(qiáng)關(guān)聯(lián)規(guī)則的生成。中所有強(qiáng)關(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%序號(hào)序號(hào)lkxm-1ConfidenceSupport規(guī)則（是否是強(qiáng)規(guī)則）規(guī)則（是否是強(qiáng)規(guī)則）1235267

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