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

大數(shù)據(jù)分析和內(nèi)存計(jì)算第4講數(shù)據(jù)挖掘技術(shù)概述李國(guó)良清華大學(xué)計(jì)算機(jī)系第一頁(yè)，共一百四十六頁(yè)。提綱數(shù)據(jù)挖掘概覽數(shù)據(jù)預(yù)處理分類(lèi)（Classification）聚類(lèi)（Cluster）關(guān)聯(lián)規(guī)則（Association

Rule）回歸（Regression）第二頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘概覽What?數(shù)據(jù)挖掘的定義Why?數(shù)據(jù)挖掘的動(dòng)機(jī)How?哪些數(shù)據(jù)可以用來(lái)挖掘？數(shù)據(jù)挖掘的主要內(nèi)容第三頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘定義什么是數(shù)據(jù)挖掘（Data

Mining）？Extractionofinteresting(non-trivial,implicit,previouslyunknownandpotentiallyuseful)patternsorknowledgefromhugeamountofdata其他稱(chēng)謂：Knowledge

discovery(mining)

in

database(KDD),

data/pattern

analysis,

business

intelligence,

decision-support

system,

knowledge

extraction,

data

archeology,

data

dredging

and

information

harvesting

etc.第四頁(yè)，共一百四十六頁(yè)。模式有效性度量SimplicityE.g.,(association)rulelength,(decision)treesizeCertaintyE.g.,confidence,P(A|B)=#(AandB)/#(B),classificationreliabilityoraccuracy,rulestrength,etc.UtilityPotentialusefulness,e.g.,support(association),noisethreshold(description)NoveltyNotpreviouslyknown,surprising(usedtoremoveredundantrules)第五頁(yè)，共一百四十六頁(yè)。為何需要數(shù)據(jù)挖掘？數(shù)據(jù)量大缺乏理論知識(shí)數(shù)據(jù)挖掘可以幫助產(chǎn)生新的假說(shuō)或者使數(shù)據(jù)變得有意義第六頁(yè)，共一百四十六頁(yè)。為何需要數(shù)據(jù)挖掘？Wearedrowningindata,butstarvinginknowledgeDataexplosion:Automateddatacollectiontoolsandmaturedatabasetechnologyleadtotremendousamountsofdataaccumulatedand/ortobeanalyzedindatabases,datawarehouses,andotherinformationrepositories.

苦惱:淹沒(méi)在數(shù)據(jù)中;不能制定合適的決策!數(shù)據(jù)知識(shí)決策模式趨勢(shì)事實(shí)關(guān)系模型關(guān)聯(lián)規(guī)則序列目標(biāo)市場(chǎng)資金分配貿(mào)易選擇在哪兒做廣告銷(xiāo)售的地理位置金融經(jīng)濟(jì)政府人口統(tǒng)計(jì)生命周期第七頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘的意義數(shù)據(jù)挖掘輔助社會(huì)管理促進(jìn)民生改善支持商業(yè)決策推動(dòng)科技進(jìn)步股票趨勢(shì)分析智能交通第八頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘應(yīng)用銀行美國(guó)銀行家協(xié)會(huì)(ABA)預(yù)測(cè)數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘技術(shù)在美國(guó)商業(yè)銀行的應(yīng)用增長(zhǎng)率是14.9％。

分析客戶使用分銷(xiāo)渠道的情況和分銷(xiāo)渠道的容量

；建立利潤(rùn)評(píng)測(cè)模型；客戶關(guān)系優(yōu)化；風(fēng)險(xiǎn)控制等電子商務(wù)網(wǎng)上商品推薦；個(gè)性化網(wǎng)頁(yè)；自適應(yīng)網(wǎng)站…生物制藥、基因研究DNA序列查詢和匹配；識(shí)別基因序列的共發(fā)生性…電信欺詐甄別；客戶流失…保險(xiǎn)、零售第九頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘應(yīng)用Debt<10%ofIncomeDebt=0%GoodCreditRisksBadCreditRisksGoodCreditRisksYesYesYesNONONOIncome>$40KQQQQII123456factor1factor2factorn神經(jīng)網(wǎng)絡(luò)NeuralNetworks聚類(lèi)分析ClusteringOpenAccn’tAddNewProductDecreaseUsage???Time序列分析SequenceAnalysis決策樹(shù)DecisionTrees

傾向性分析

客戶保留

客戶生命周期管理

目標(biāo)市場(chǎng)

價(jià)格彈性分析

客戶細(xì)分

市場(chǎng)細(xì)分

傾向性分析

客戶保留

目標(biāo)市場(chǎng)

欺詐檢測(cè)關(guān)聯(lián)分析Association

市場(chǎng)組合分析

套裝產(chǎn)品分析

目錄設(shè)計(jì)

交叉銷(xiāo)售第十頁(yè)，共一百四十六頁(yè)。數(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ù)模式）分類(lèi)、聚類(lèi)、關(guān)聯(lián)分析、回歸預(yù)測(cè)、文本挖掘質(zhì)量評(píng)估（識(shí)別提供知識(shí)的真正有趣模式）知識(shí)表示（可視化和知識(shí)表示技術(shù)）第十一頁(yè)，共一百四十六頁(yè)。數(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

update?可信度:how

trustable

the

data

are

correct?可解釋性:how

easily

the

data

can

be

understood?第十二頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)挖掘預(yù)處理的主要任務(wù)數(shù)據(jù)清理填寫(xiě)空缺的值，平滑噪聲數(shù)據(jù)，識(shí)別、刪除孤立點(diǎn)，解決不一致性數(shù)據(jù)集成集成多個(gè)數(shù)據(jù)庫(kù)、數(shù)據(jù)立方體或文件數(shù)據(jù)變換規(guī)范化和聚集數(shù)據(jù)歸約得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果數(shù)據(jù)離散化數(shù)據(jù)歸約的一部分，通過(guò)概念分層和數(shù)據(jù)的離散化來(lái)規(guī)約數(shù)據(jù)，對(duì)數(shù)字型數(shù)據(jù)特別重要第十三頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)清洗臟數(shù)據(jù)：例如設(shè)備錯(cuò)誤，人或者機(jī)器錯(cuò)誤，傳輸錯(cuò)誤等不完整性：屬性值缺失或者只有聚集數(shù)據(jù)例如：phone=“”;噪音：包含噪聲、錯(cuò)誤或者異常值例如：salary=-10不一致性:例如：age=42，birthday=03-07-2010假值：例如：使用某一值填補(bǔ)缺失屬性第十四頁(yè)，共一百四十六頁(yè)。缺失值（Incomplete/Missing

Data)數(shù)據(jù)并不總是完整的例如：數(shù)據(jù)庫(kù)表中，很多條記錄的對(duì)應(yīng)字段沒(méi)有相應(yīng)值，比如銷(xiāo)售表中的顧客收入引起空缺值的原因設(shè)備異常與其他已有數(shù)據(jù)不一致而被刪除因?yàn)檎`解而沒(méi)有被輸入的數(shù)據(jù)在輸入時(shí)，有些數(shù)據(jù)因?yàn)榈貌坏街匾暥鴽](méi)有被輸入對(duì)數(shù)據(jù)的改變沒(méi)有進(jìn)行日志記載空缺值要經(jīng)過(guò)推斷而補(bǔ)上第十五頁(yè)，共一百四十六頁(yè)。如何補(bǔ)充缺失值忽略元組：當(dāng)類(lèi)標(biāo)號(hào)缺少時(shí)通常這么做（假定挖掘任務(wù)設(shè)計(jì)分類(lèi)或描述），當(dāng)每個(gè)屬性缺少值的百分比變化很大時(shí)，它的效果非常差。人工填寫(xiě)空缺值：工作量大，可行性低使用一個(gè)全局變量填充空缺值：比如使用unknown或-∞使用屬性的平均值填充空缺值使用與給定元組屬同一類(lèi)的所有樣本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定樹(shù)這樣的基于推斷的方法第十六頁(yè)，共一百四十六頁(yè)。噪聲數(shù)據(jù)噪聲：一個(gè)測(cè)量變量中的隨機(jī)錯(cuò)誤或偏差引起不正確屬性值的原因數(shù)據(jù)收集工具的問(wèn)題數(shù)據(jù)輸入錯(cuò)誤數(shù)據(jù)傳輸錯(cuò)誤技術(shù)限制命名規(guī)則的不一致其它需要數(shù)據(jù)清理的數(shù)據(jù)問(wèn)題重復(fù)記錄不完整的數(shù)據(jù)不一致的數(shù)據(jù)第十七頁(yè)，共一百四十六頁(yè)。如何處理噪聲數(shù)據(jù)分箱:firstsortdataandpartitioninto(equi-depth)binsthenonecansmoothbybinmeans,smoothbybinmedian,smoothbybinboundaries,etc.聚類(lèi)detectandremoveoutliers人機(jī)融合detectsuspiciousvaluesandcheckbyhuman(e.g.,dealwithpossibleoutliers)回歸smoothbyfittingthedataintoregressionfunctions第十八頁(yè)，共一百四十六頁(yè)。分箱(Binning)等寬Equal-width(distance)partitioning:DividestherangeintoNintervalsofequalsize:uniformgridifAandBarethelowestandhighestvaluesoftheattribute,thewidthofintervalswillbe:W=(B–A)/N.Themoststraightforward,butoutliersmaydominatepresentationSkeweddataisnothandledwell.等深Equal-depth(frequency)partitioning:DividestherangeintoNintervals,eachcontainingapproximatelysamenumberofsamplesGooddatascalingManagingcategoricalattributescanbetricky.第十九頁(yè)，共一百四十六頁(yè)。數(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用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱邊界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34第二十頁(yè)，共一百四十六頁(yè)。聚類(lèi)：Cluster

Analysis每個(gè)簇中的數(shù)據(jù)用其中心值代替忽略孤立點(diǎn)先通過(guò)聚類(lèi)等方法找出孤立點(diǎn)。這些孤立點(diǎn)可能包含有用的信息。人工再審查這些孤立點(diǎn)第二十一頁(yè)，共一百四十六頁(yè)。Regression通過(guò)構(gòu)造函數(shù)來(lái)符合數(shù)據(jù)變化的趨勢(shì)，這樣可以用一個(gè)變量預(yù)測(cè)另一個(gè)變量。線性回歸多線性回歸非線性回歸xyy=x+1X1Y1Y1’第二十二頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)集成實(shí)體識(shí)別元數(shù)據(jù)可幫助避免錯(cuò)誤知識(shí)圖譜屬性冗余相關(guān)分析數(shù)據(jù)重復(fù)（元組冗余）數(shù)據(jù)值沖突的檢測(cè)與處理表示、比例或編碼不同第二十三頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)變換（規(guī)范化）平滑：去掉數(shù)據(jù)中的噪聲。技術(shù)包括分箱、回歸、聚類(lèi)。聚集：對(duì)數(shù)據(jù)進(jìn)行匯總或聚集。數(shù)據(jù)泛化（概化）：使用概念分層，用高層概念替換低層或“原始”數(shù)據(jù)。規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特定區(qū)間。最小-最大、Z-Score、按小數(shù)定標(biāo)規(guī)范化。第二十四頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)變換平滑，聚集數(shù)據(jù)概化，規(guī)范化屬性構(gòu)造(特征構(gòu)造)有限區(qū)間的歸一化：無(wú)限區(qū)間的歸一化：模糊隸屬度：第二十五頁(yè)，共一百四十六頁(yè)。數(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ù)可以用來(lái)得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近保持原數(shù)據(jù)的完整性。對(duì)歸約后的數(shù)據(jù)集挖掘?qū)⒏行?，并產(chǎn)生相同（或幾乎相同）的結(jié)果。第二十六頁(yè)，共一百四十六頁(yè)。數(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ū)間值或較高層的概念替換第二十七頁(yè)，共一百四十六頁(yè)。數(shù)據(jù)立方體據(jù)立方體存儲(chǔ)多維聚集信息，提供對(duì)預(yù)計(jì)算的匯總數(shù)據(jù)進(jìn)行快速訪問(wèn)。如：立方體內(nèi)存儲(chǔ)季度銷(xiāo)售額，若對(duì)年銷(xiāo)售額感興趣，可對(duì)數(shù)據(jù)執(zhí)行聚集操作，例如sum()等。第二十八頁(yè)，共一百四十六頁(yè)。屬性子集選擇通過(guò)刪除不相關(guān)或冗余的屬性（或維）減小數(shù)據(jù)集。其目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類(lèi)的概率分布盡可能地接近使用所有屬性得到的原分布。通過(guò)窮舉搜索找出有屬性的最佳子集是不現(xiàn)實(shí)的。通常采用壓縮搜索空間的啟發(fā)式算法。如貪心算法：從局部最優(yōu)到全局最優(yōu)。逐步向前選擇逐步向后刪除向前選擇和向后刪除的結(jié)合決策樹(shù)歸納第二十九頁(yè)，共一百四十六頁(yè)。維度規(guī)約維度歸約使用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。分為無(wú)損和有損兩種。主要方法：串壓縮：無(wú)損，但只允許有限的數(shù)據(jù)操作。小波變換（DWT）：有損，適合高維數(shù)據(jù)。主成分分析（PCA）：有損，能更好地處理稀疏數(shù)據(jù)。第三十頁(yè)，共一百四十六頁(yè)。數(shù)值規(guī)約通過(guò)選擇替代的、“較小的”數(shù)據(jù)表示形式來(lái)減少數(shù)據(jù)量?？梢苑譃閰?shù)方法和非參數(shù)方法。參數(shù)方法：回歸（regression）和對(duì)數(shù)線性模型非參數(shù)方法：直方圖、聚類(lèi)、抽樣第三十一頁(yè)，共一百四十六頁(yè)。離散化離散化的用途：（1）適應(yīng)某些僅接受離散值的算法；（2）減小數(shù)據(jù)的尺度。離散化的方法包括幾下幾種。（1）等距分割；（2）聚類(lèi)分割；（3）直方圖分割；（4）基于熵的分割；（5）基于自然屬性的分割。第三十二頁(yè)，共一百四十六頁(yè)。抽樣用數(shù)據(jù)的小得多的隨機(jī)樣本（子集）不是大型數(shù)據(jù)集。抽樣方法s個(gè)樣本無(wú)放回簡(jiǎn)單隨機(jī)抽樣s個(gè)樣本有放回簡(jiǎn)單隨機(jī)抽樣聚類(lèi)抽樣分層抽樣第三十三頁(yè)，共一百四十六頁(yè)。分類(lèi)第三十四頁(yè)，共一百四十六頁(yè)。分類(lèi)分類(lèi)是指將數(shù)據(jù)映射到預(yù)先定義好的群組或類(lèi)。在分析測(cè)試數(shù)據(jù)之前，類(lèi)別就已經(jīng)被確定了，所以分類(lèi)統(tǒng)稱(chēng)被稱(chēng)作有指導(dǎo)的學(xué)習(xí)。分類(lèi)算法要求基于數(shù)據(jù)屬性來(lái)定義類(lèi)別。分類(lèi)算法通常通過(guò)觀察已知所屬類(lèi)別的數(shù)據(jù)的特征來(lái)描述類(lèi)別。第三十五頁(yè)，共一百四十六頁(yè)。分類(lèi)應(yīng)用分類(lèi)具有廣泛的應(yīng)用，例如醫(yī)療診斷、信用卡系統(tǒng)的信用分級(jí)、圖像模式識(shí)別等。為了識(shí)別乘客是否是潛在的恐怖分子或罪犯，機(jī)場(chǎng)安全攝像站需要對(duì)乘客的臉部進(jìn)行掃描并辨識(shí)臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀），然后將得到的模式與數(shù)據(jù)庫(kù)中的已知恐怖分子或罪犯的模式進(jìn)行逐個(gè)比較，看看是否與其中的某一模式相匹配。第三十六頁(yè)，共一百四十六頁(yè)。分類(lèi)步驟1．建立一個(gè)模型，描述預(yù)定的數(shù)據(jù)類(lèi)集或概念集數(shù)據(jù)元組也稱(chēng)作樣本、實(shí)例或?qū)ο?。為建立模型而被分析的?shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集中的單個(gè)元組稱(chēng)作訓(xùn)練樣本，假定每個(gè)元組屬于一個(gè)預(yù)定義的類(lèi)，由一個(gè)稱(chēng)作類(lèi)標(biāo)號(hào)。通過(guò)分析訓(xùn)練數(shù)據(jù)集來(lái)構(gòu)造分類(lèi)模型，可用分類(lèi)規(guī)則、決策樹(shù)或數(shù)學(xué)公式等形式提供。2.使用模型進(jìn)行分類(lèi)首先評(píng)估模型（分類(lèi)法）的預(yù)測(cè)準(zhǔn)確率。將已知的類(lèi)標(biāo)號(hào)與該樣本的學(xué)習(xí)模型類(lèi)預(yù)測(cè)比較準(zhǔn)確率等于測(cè)試集的樣本中被模型正確分類(lèi)的百分比測(cè)試集應(yīng)該與訓(xùn)練集的內(nèi)容相互獨(dú)立，否則會(huì)出現(xiàn)過(guò)分適應(yīng)的情況如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用它對(duì)類(lèi)標(biāo)號(hào)未知的數(shù)據(jù)元組或?qū)ο筮M(jìn)行分類(lèi)。第三十七頁(yè)，共一百四十六頁(yè)。（1）模型的構(gòu)建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’

Classifier(Model)NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no第三十八頁(yè)，共一百四十六頁(yè)。（2）利用模型分類(lèi)ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?第三十九頁(yè)，共一百四十六頁(yè)。分類(lèi)方法評(píng)價(jià)預(yù)測(cè)的準(zhǔn)確率這涉及模型正確地預(yù)測(cè)新的或先前未見(jiàn)過(guò)的數(shù)據(jù)的類(lèi)標(biāo)號(hào)的能力速度構(gòu)造模型的速度利用模型進(jìn)行分類(lèi)的速度強(qiáng)壯性給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，模型正確預(yù)測(cè)的能力可伸縮性當(dāng)給定大量數(shù)據(jù)時(shí)，有效地構(gòu)造模型的能力可解釋性

涉及學(xué)習(xí)模型提供的理解和洞察的層次第四十頁(yè)，共一百四十六頁(yè)。分類(lèi)器性能評(píng)價(jià)方式準(zhǔn)確率和召回率-混淆矩陣等給定一個(gè)類(lèi)Cj和一個(gè)數(shù)據(jù)庫(kù)元組ti，ti可能被分類(lèi)器判定為屬于Cj或不屬于Cj，其實(shí)ti本身可能屬于Cj或不屬于Cj，這樣就會(huì)產(chǎn)生如下一些情況：真正:判定ti在Cj中，實(shí)際上的確在其中。假正:判定ti在Cj中，實(shí)際上不在其中。真負(fù):判定ti不在Cj中，實(shí)際上不在其中。假負(fù):判定ti不在Cj中，實(shí)際上的確在其中。準(zhǔn)確率:P=A/(A+B)召回率:R=A/(A+C)第四十一頁(yè)，共一百四十六頁(yè)。評(píng)估分類(lèi)方法的準(zhǔn)確性保持方法給定數(shù)據(jù)隨機(jī)劃分為兩個(gè)集合：訓(xùn)練集(2/3)和測(cè)試集(1/3)訓(xùn)練集導(dǎo)出分類(lèi)法，測(cè)試集對(duì)其準(zhǔn)確性進(jìn)行評(píng)估k-折交叉驗(yàn)證初始數(shù)據(jù)被劃分為k個(gè)不相交的，大小大致相同的子集S1,S2…Sk進(jìn)行k次訓(xùn)練和測(cè)試，第i次時(shí)，以Si做測(cè)試集，其他做訓(xùn)練集準(zhǔn)確率為k次迭代正確分類(lèi)數(shù)除以初始數(shù)據(jù)集樣本總數(shù)第四十二頁(yè)，共一百四十六頁(yè)。分類(lèi)方法第四十三頁(yè)，共一百四十六頁(yè)。基于距離的分類(lèi)方法與一個(gè)類(lèi)中的成員和另一個(gè)類(lèi)中的成員之間的相似性相比，被映射到同一個(gè)類(lèi)中的成員彼此之間被認(rèn)為是更加相似的。相似性（距離）度量可以用來(lái)識(shí)別數(shù)據(jù)庫(kù)中不同成員之間的“相似程度”。第四十四頁(yè)，共一百四十六頁(yè)?；诰嚯x的分類(lèi)方法的直觀解釋?zhuān)╝）類(lèi)定義（b）待分類(lèi)樣例（c）分類(lèi)結(jié)果第四十五頁(yè)，共一百四十六頁(yè)。距離計(jì)算方法閔可夫斯基距離:當(dāng)p=2時(shí)，為歐幾里得距離當(dāng)p=1時(shí)，為曼哈頓距離當(dāng)p->∞時(shí)，為切比雪夫距離向量?jī)?nèi)積：夾角余弦：Jaccard：還有信息熵、相關(guān)系數(shù)等其他的度量方法第四十六頁(yè)，共一百四十六頁(yè)?；诰嚯x的分類(lèi)方法的一般性描述算法

基于距離的分類(lèi)算法輸入：每個(gè)類(lèi)的中心C1，…，Cm；待分類(lèi)的元組t。

輸出：輸出類(lèi)別c。

（1）dist=∞；//距離初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←Ci；（5） dist←dist(Ci，t)；（6） END.算法通過(guò)對(duì)每個(gè)元組和各個(gè)類(lèi)的中心來(lái)比較，從而可以找出他的最近的類(lèi)中心，得到確定的類(lèi)別標(biāo)記。第四十七頁(yè)，共一百四十六頁(yè)。K近鄰算法（KNN）K

Nearestneighbor(KNN)通過(guò)計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類(lèi)元組的距離，取和待分類(lèi)元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)類(lèi)別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類(lèi)元組就屬于哪個(gè)類(lèi)別。訓(xùn)練樣本用n維數(shù)值屬性描述。每個(gè)樣本代表n維空間的一個(gè)點(diǎn)。所有的訓(xùn)練樣本都放在n維模式空間中。給定一個(gè)樣本，k-最臨近分類(lèi)法搜索模式空間，找出最接近未知樣本的k個(gè)訓(xùn)練樣本。第四十八頁(yè)，共一百四十六頁(yè)。K近鄰算法（KNN）要求的信息訓(xùn)練集距離計(jì)算值要獲取的最鄰近的鄰居的數(shù)目k一個(gè)未知的記錄進(jìn)行分類(lèi)計(jì)算與其它訓(xùn)練記錄之間的距離識(shí)別出k個(gè)最近的鄰居使用最近鄰居的類(lèi)標(biāo)號(hào)來(lái)標(biāo)識(shí)未知元組的類(lèi)（bytakingmajorityvote）第四十九頁(yè)，共一百四十六頁(yè)。K近鄰算法（KNN）算法K-近鄰分類(lèi)算法輸入：

訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目K；待分類(lèi)的元組t。

輸出：

輸出類(lèi)別c。

（1）N=?；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）

N=N∪i8cikoa；

（5）ELSE（6）

IF

u∈Nsuchthatsim(t，u)<sim(t，d)THENBEGIN（7）

N=N-{u}；（8）

N=N∪y6uacs6；（9） END（10）END（11）c=classtowhichthemostu∈N.第五十頁(yè)，共一百四十六頁(yè)。K近鄰算法（KNN）K值的選取如果k過(guò)于小，那么將會(huì)對(duì)數(shù)據(jù)中存在的噪聲過(guò)于敏感如果k過(guò)大，鄰居中可能包含其他類(lèi)的點(diǎn)一個(gè)經(jīng)驗(yàn)的取值法則為k≤，q為訓(xùn)練元組的數(shù)目。商業(yè)算法通常以10作為默認(rèn)值。第五十一頁(yè)，共一百四十六頁(yè)。決策樹(shù)第五十二頁(yè)，共一百四十六頁(yè)。決策樹(shù)（Decision

Tree）決策樹(shù)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無(wú)次序、無(wú)規(guī)則的元組中推理出決策樹(shù)表示形式的分類(lèi)規(guī)則。類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，而每個(gè)樹(shù)葉節(jié)點(diǎn)代表類(lèi)或類(lèi)分布。樹(shù)的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。第五十三頁(yè)，共一百四十六頁(yè)。決策樹(shù)例如，在貸款申請(qǐng)中，要對(duì)申請(qǐng)的風(fēng)險(xiǎn)大小做出判斷。收入>40000高負(fù)債工作時(shí)間>5年是否是否“年收入大于￥40000”并且“高負(fù)債”的用戶被認(rèn)為是“高風(fēng)險(xiǎn)”；“年收入小于￥40000”但“工作時(shí)間大于5年”的申請(qǐng)，是“低風(fēng)險(xiǎn)”；NYYNNY第五十四頁(yè)，共一百四十六頁(yè)。決策樹(shù)buys_computer的決策樹(shù)示意

Age?

Credit_rating?

student?

yes

no

yesyes

no

<=30?

>40

30~40yes

no

fairexcellent

第五十五頁(yè)，共一百四十六頁(yè)。決策樹(shù)決策樹(shù)（decisiontree）1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來(lái)又提出了若干改進(jìn)的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizable

inductionofdecisiontrees)是比較有代表性的兩個(gè)算法。第五十六頁(yè)，共一百四十六頁(yè)。決策樹(shù)的步驟使用決策樹(shù)進(jìn)行分類(lèi)分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹(shù)，建立決策樹(shù)模型。這個(gè)過(guò)程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過(guò)程。第2步：利用生成完畢的決策樹(shù)對(duì)輸入數(shù)據(jù)進(jìn)行分類(lèi)。對(duì)輸入的記錄，從根結(jié)點(diǎn)依次測(cè)試記錄的屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類(lèi)。

第五十七頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法遞歸執(zhí)行的終止條件（停止分支的條件）對(duì)于給定的節(jié)點(diǎn)，所有的例子都屬于同一個(gè)類(lèi)雖然對(duì)于某一個(gè)節(jié)點(diǎn)當(dāng)前的例子不屬于同一個(gè)類(lèi)，但是已經(jīng)沒(méi)有屬性可用來(lái)選擇繼續(xù)進(jìn)行分支處理第五十八頁(yè)，共一百四十六頁(yè)。分裂屬性選擇選擇屬性的方法選擇具有最大信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性該屬性使得對(duì)結(jié)果劃分中的樣本分類(lèi)所需的信息量最小，并反映劃分的最小隨機(jī)性。用信息增益這種信息論的理論方法，使得對(duì)一個(gè)對(duì)象分類(lèi)所需要的期望測(cè)試數(shù)目達(dá)到最小，并確保找到一棵簡(jiǎn)單的樹(shù)。第五十九頁(yè)，共一百四十六頁(yè)。分裂屬性選擇怎樣計(jì)算信息增益（informationgain）信息增益被定義為原始分割的熵與劃分以后各分割的熵累加得到的總熵之間的差。信息增益是指劃分前后進(jìn)行正確預(yù)測(cè)所需的信息量之差。選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性。第六十頁(yè)，共一百四十六頁(yè)。信息增益的計(jì)算

設(shè)S是有s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類(lèi)標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類(lèi)Ci（i=1,2,…,m），si是類(lèi)Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類(lèi)所需要的期望信息為：

其中pi是任意樣本屬于Ci的概率，可用si/s來(lái)估計(jì)第六十一頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第六十二頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)決策屬性“買(mǎi)計(jì)算機(jī)？”。該屬性分兩類(lèi)：買(mǎi)/不買(mǎi)S1(買(mǎi))=641S2（不買(mǎi)）=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ì)算決策屬性的熵第六十三頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2步計(jì)算條件屬性的熵條件屬性共有4個(gè)。分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。第六十四頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-1步計(jì)算年齡的熵年齡共分三個(gè)組：

青年、中年、老年青年買(mǎi)與不買(mǎi)比例為128/256S1(買(mǎi))=128S2（不買(mǎi)）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第六十五頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-2步計(jì)算年齡的熵年齡共分三個(gè)組：

青年、中年、老年中年買(mǎi)與不買(mǎi)比例為256/0S1(買(mǎi))=256S2（不買(mǎi)）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0第六十六頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-3步計(jì)算年齡的熵年齡共分三個(gè)組：

青年、中年、老年老年買(mǎi)與不買(mǎi)比例為125/127S1(買(mǎi))=125S2（不買(mǎi)）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157第六十七頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-4步計(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）第六十八頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第3步計(jì)算收入的熵收入共分三個(gè)組：

高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)第六十九頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第4步計(jì)算學(xué)生的熵學(xué)生共分二個(gè)組：

學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811=0.1726（3）第七十頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第5步計(jì)算信譽(yù)的熵信譽(yù)分二個(gè)組：

良好，優(yōu)秀E（信譽(yù)）=0.9048信譽(yù)信息增益=0.9537-0.9048=0.0453（4）第七十一頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第6步計(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）第七十二頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)年齡青年中年老年買(mǎi)/不買(mǎi)買(mǎi)買(mǎi)/不買(mǎi)葉子第七十三頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)青年買(mǎi)與不買(mǎi)比例為128/256S1(買(mǎi))=128S2（不買(mǎi)）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第七十四頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)如果選擇收入作為節(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注意第七十五頁(yè)，共一百四十六頁(yè)。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)年齡青年中年老年學(xué)生買(mǎi)信譽(yù)葉子否是優(yōu)良買(mǎi)不買(mǎi)買(mǎi)/不買(mǎi)買(mǎi)葉子葉子葉子第七十六頁(yè)，共一百四十六頁(yè)。決策樹(shù)分類(lèi)規(guī)則提取決策樹(shù)所表示的分類(lèi)知識(shí)可以被抽取出來(lái)并可用IF-THEN分類(lèi)規(guī)則形式加以表示。從決策樹(shù)的根結(jié)點(diǎn)到任一個(gè)葉結(jié)點(diǎn)所形成的一條路徑就構(gòu)成了一條分類(lèi)規(guī)則。沿著決策樹(shù)的一條路徑所形成的屬性-值對(duì)就構(gòu)成了分類(lèi)規(guī)則條件部分（IF部分）中的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)所標(biāo)記的類(lèi)別就構(gòu)成了規(guī)則的結(jié)論內(nèi)容（THEN部分）。IF-THEN分類(lèi)規(guī)則表達(dá)方式易于被人理解，且當(dāng)決策樹(shù)較大時(shí)，IF-THEN規(guī)則表示形式的優(yōu)勢(shì)就更加突出。第七十七頁(yè)，共一百四十六頁(yè)。貝葉斯分類(lèi)第七十八頁(yè)，共一百四十六頁(yè)。貝葉斯分類(lèi)貝葉斯定理

貝葉斯定理給出了如下計(jì)算P(C|X)的簡(jiǎn)單有效的方法:

P(C):是先驗(yàn)概率，或稱(chēng)C的先驗(yàn)概率。

P(X):樣本數(shù)據(jù)被觀察的概率。

P(X|C)代表假設(shè)C成立的情況下，觀察到X的概率。

P(C|X)是后驗(yàn)概率，或稱(chēng)條件X下C的后驗(yàn)概率。

后驗(yàn)概率P(C|X)比先驗(yàn)概率P(C)基于更多的信息。

P(C)是獨(dú)立于X的。第七十九頁(yè)，共一百四十六頁(yè)。樸素貝葉斯分類(lèi)樸素貝葉斯分類(lèi)的工作過(guò)程如下：(1)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X={x1,x2…xn}表示，分別描述n個(gè)屬性A1，…，An樣本的n個(gè)度量。(2)假定有m個(gè)類(lèi)C1，C2，…，Cm，給定一個(gè)未知的數(shù)據(jù)樣本X（即沒(méi)有類(lèi)標(biāo)號(hào)），分類(lèi)器將預(yù)測(cè)X屬于具有最高后驗(yàn)概率（條件X下）的類(lèi)。樸素貝葉斯分類(lèi)將未知的樣本分配給類(lèi)Ci（1≤i≤m）當(dāng)且僅當(dāng)P(Ci|X)>P(Cj|X)，j≠i。即最大化P(Ci|X)P(Ci|X)最大的類(lèi)Ci稱(chēng)為最大后驗(yàn)假定。第八十頁(yè)，共一百四十六頁(yè)。樸素貝葉斯分類(lèi)(3)由于P(X)對(duì)于所有類(lèi)為常數(shù)，P(X|Ci)*P(Ci)最大即可。如果Ci類(lèi)的先驗(yàn)概率未知，則通常假定這些類(lèi)是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此問(wèn)題就轉(zhuǎn)換為對(duì)P(X|Ci)的最大化（P(X|Ci)常被稱(chēng)為給定Ci時(shí)數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設(shè)Ci稱(chēng)為最大似然假設(shè)）。否則，需要最大化P(X|Ci)*P(Ci)。類(lèi)的先驗(yàn)概率可以用P(Ci)=si/s計(jì)算，其中si是類(lèi)Ci中的訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。第八十一頁(yè)，共一百四十六頁(yè)。樸素貝葉斯分類(lèi)（4）給定具有許多屬性的數(shù)據(jù)集，計(jì)算P(X|Ci)的開(kāi)銷(xiāo)可能非常大。為降低計(jì)算P(X|Ci)的開(kāi)銷(xiāo)，可以做類(lèi)條件獨(dú)立的樸素假定。給定樣本的類(lèi)標(biāo)號(hào)，假定屬性值相互條件獨(dú)立，即在屬性間，不存在依賴(lài)關(guān)系。這樣概率P(x1|Ci)，P(x2|Ci)，……，P(xn|Ci)由訓(xùn)練樣本估值。第八十二頁(yè)，共一百四十六頁(yè)。如果Ak是離散屬性，則P(xk|Ci)=sik/si，其中sik是在屬性Ak上具有值xk的類(lèi)Ci的訓(xùn)練樣本數(shù)，si是Ci中的訓(xùn)練樣本數(shù)。

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

第八十五頁(yè)，共一百四十六頁(yè)。樸素貝葉斯分類(lèi)舉例(2)為計(jì)算P(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(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667，P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.400。

第八十六頁(yè)，共一百四十六頁(yè)。樸素貝葉斯分類(lèi)舉例(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”)=

0.044*0.643=0.028，P(X|buys_computer=“no”)*P(buys_computer=“no”)=

0.019*0.357=0.007。因此，對(duì)于樣本X，樸素貝葉斯分類(lèi)預(yù)測(cè)buys_computer=“yes”X=（age=“<=30”,income=“medium”,student=“yes”,credit_rating=“fair”）第八十七頁(yè)，共一百四十六頁(yè)。聚類(lèi)第八十八頁(yè)，共一百四十六頁(yè)。聚類(lèi)：Cluster聚類(lèi)就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類(lèi)別在同一個(gè)類(lèi)中，對(duì)象之間具有相似性；不同類(lèi)的對(duì)象之間是相異的。聚類(lèi)分析把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇；聚類(lèi)是一種無(wú)監(jiān)督分類(lèi)法:沒(méi)有預(yù)先指定的類(lèi)別；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布；

作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；第八十九頁(yè)，共一百四十六頁(yè)。聚類(lèi)圖示聚類(lèi)中沒(méi)有任何指導(dǎo)信息，完全按照數(shù)據(jù)的分布進(jìn)行類(lèi)別劃分第九十頁(yè)，共一百四十六頁(yè)。聚類(lèi)與分類(lèi)的區(qū)別有類(lèi)別標(biāo)記和無(wú)類(lèi)別標(biāo)記;有監(jiān)督與無(wú)監(jiān)督;（有訓(xùn)練語(yǔ)料與無(wú)訓(xùn)練語(yǔ)料）TrainAndClassification（分類(lèi)）;NoTrain（聚類(lèi)）;第九十一頁(yè)，共一百四十六頁(yè)。聚類(lèi)分析為達(dá)到全局最優(yōu)，基于劃分的聚類(lèi)會(huì)要求窮舉所有可能的劃分。聚類(lèi)技術(shù)將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為群或聚類(lèi)，使得在一個(gè)聚類(lèi)中的對(duì)象“類(lèi)似”，但與其它聚類(lèi)中的對(duì)象“不類(lèi)似”。絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的基于劃分的方法，這些基于劃分的聚類(lèi)方法對(duì)在中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用。（1）k-means算法，在該算法中，每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。（2）k-medoids算法，在該算法中，每個(gè)簇用接近聚類(lèi)中心的一個(gè)對(duì)象來(lái)表示。第九十二頁(yè)，共一百四十六頁(yè)。K-means初始參數(shù)-類(lèi)別數(shù)&初始類(lèi)別中心;聚類(lèi)有效性函數(shù)-最小誤差;優(yōu)點(diǎn)：

聚類(lèi)時(shí)間快;缺點(diǎn)：對(duì)初始參數(shù)敏感;容易陷入局部最優(yōu);

第九十三頁(yè)，共一百四十六頁(yè)。K-means步驟1設(shè)置初始類(lèi)別中心和類(lèi)別數(shù);2根據(jù)類(lèi)別中心對(duì)數(shù)據(jù)進(jìn)行類(lèi)別劃分;3重新計(jì)算當(dāng)前類(lèi)別劃分下每類(lèi)的中心;4在得到類(lèi)別中心下繼續(xù)進(jìn)行類(lèi)別劃分;5如果連續(xù)兩次的類(lèi)別劃分結(jié)果不變則停止算法;否則循環(huán)2～5;O（kndt）第九十四頁(yè)，共一百四十六頁(yè)。第九十五頁(yè)，共一百四十六頁(yè)。初始值敏感初始化4個(gè)類(lèi)別中心;左側(cè)的全體數(shù)據(jù)僅與第一個(gè)類(lèi)別中心相似;第九十六頁(yè)，共一百四十六頁(yè)。K-mediods步驟1任意選取K個(gè)對(duì)象作為medoids;2將余下的對(duì)象分到各個(gè)類(lèi)中去（根據(jù)與medoid最相近的原則）;3對(duì)于每個(gè)類(lèi)（Oi）中，順序選取一個(gè)Or，計(jì)算用Or代替Oi后的消耗—E（Or）。選擇E最小的那個(gè)Or來(lái)代替Oi。4重復(fù)2-3直到medoids不變;O（n2dt）第九十七頁(yè)，共一百四十六頁(yè)。聚類(lèi)方法性能評(píng)價(jià)一個(gè)好的聚類(lèi)方法要能產(chǎn)生高質(zhì)量的聚類(lèi)結(jié)果——簇，這些簇要具備以下兩個(gè)特點(diǎn)：高的簇內(nèi)相似性低的簇間相似性

聚類(lèi)結(jié)果的好壞取決于該聚類(lèi)方法采用的相似性評(píng)估方法以及該方法的具體實(shí)現(xiàn)；聚類(lèi)方法的好壞還取決于該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；第九十八頁(yè)，共一百四十六頁(yè)。聚類(lèi)方法性能評(píng)價(jià)可伸縮性能夠處理不同類(lèi)型的屬性能發(fā)現(xiàn)任意形狀的簇在決定輸入?yún)?shù)的時(shí)候，盡量不需要特定的領(lǐng)域知識(shí)；能夠處理噪聲和異常對(duì)輸入數(shù)據(jù)對(duì)象的順序不敏感能處理高維數(shù)據(jù)能產(chǎn)生一個(gè)好的、能滿足用戶指定約束的聚類(lèi)結(jié)果結(jié)果是可解釋的、可理解的和可用的第九十九頁(yè)，共一百四十六頁(yè)。聚類(lèi)評(píng)價(jià)準(zhǔn)備率：找到正確的結(jié)果數(shù)/找到結(jié)果數(shù)召回率：找到正確的結(jié)果數(shù)/正確結(jié)果數(shù)最小誤差:衡量不同類(lèi)別的數(shù)據(jù)與類(lèi)別中心的誤差和;最小方差:衡量同一類(lèi)別內(nèi)數(shù)據(jù)的平均誤差和;第一百頁(yè)，共一百四十六頁(yè)。常用的相似性度量方法余弦?jiàn)A角：Dice系數(shù)：Jaccard系數(shù)：第一百零一頁(yè)，共一百四十六頁(yè)。相似性度量方法EuclideanDistance交叉熵Cosine數(shù)據(jù)表示為向量，向量中某一維對(duì)應(yīng)數(shù)據(jù)某一特征或?qū)傩詢H計(jì)算了數(shù)據(jù)向量中屬于同一維度特征的權(quán)值差距;第一百零二頁(yè)，共一百四十六頁(yè)。聚類(lèi)分析（續(xù)）基于層次的方法：層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。

（Chameleon，CURE，BIRCH）

基于密度的方法：只要臨近區(qū)域的密度超過(guò)某個(gè)閾值，就繼續(xù)聚類(lèi)。避免僅生成球狀聚類(lèi)。（DBSCAN，OPTICS，DENCLUE）基于網(wǎng)格的方法：基于網(wǎng)格的方法把對(duì)象空間量化為有限數(shù)目的單元，所有的聚類(lèi)操作都在這個(gè)量化的空間上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快。（STING，CLIQUE，WaveCluster）基于模型的方法：為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配。（COBWEB，CLASSIT，AutoClass）

第一百零三頁(yè)，共一百四十六頁(yè)。DBSCAN基于密度的簇是密度相連的點(diǎn)的集合主要思想尋找被低密度區(qū)域分離的高密度區(qū)域只要臨近區(qū)域的密度（單位大小上對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過(guò)某個(gè)閾值，就繼續(xù)聚類(lèi)

第一百零四頁(yè)，共一百四十六頁(yè)。DBSCAN兩個(gè)參數(shù)：Eps:鄰域的最大半徑MinPts:一個(gè)核心對(duì)象以Eps為半徑的鄰域內(nèi)的最小頂點(diǎn)數(shù)MinPts=5Eps=1cmpq第一百零五頁(yè)，共一百四十六頁(yè)。DBSCAN密度=制定半徑(Eps)內(nèi)點(diǎn)的個(gè)數(shù)如果一個(gè)對(duì)象的Eps鄰域至少包含最小數(shù)目MinPts個(gè)對(duì)象，則稱(chēng)該對(duì)象為核心對(duì)象（Corepoint）如果一個(gè)對(duì)象是非核心對(duì)象,但它的鄰域中有核心對(duì)象，則稱(chēng)該對(duì)象為邊界點(diǎn)（Borderpoint

）除核心對(duì)象和邊界點(diǎn)之外的點(diǎn)是噪聲點(diǎn)（Noisepoint

）第一百零六頁(yè)，共一百四十六頁(yè)。DBSCAN第一百零七頁(yè)，共一百四十六頁(yè)。DBSCAN密度可達(dá)的（Density-reachable）對(duì)于對(duì)象p和核心對(duì)象q(關(guān)于E和MinPts),我們稱(chēng)p是從q(關(guān)于E和MinPts)直接密度可達(dá)，若對(duì)象p在對(duì)象q的E鄰域內(nèi)。如果存在一個(gè)對(duì)象鏈p1,…,pn,p1=q,pn=p

，pi+1是從pi關(guān)于Eps和MinPts

直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于Eps和MinPts

密度可達(dá)的。密度可達(dá)性是直接密度可達(dá)性的傳遞閉包，這種關(guān)系是非對(duì)稱(chēng)的。只有核心對(duì)象之間是相互可達(dá)的。pqp1第一百零八頁(yè)，共一百四十六頁(yè)。DBSCAN密度相連的（Density-connected）如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于Eps

和MinPts密度可達(dá)的，那么對(duì)象p和q是關(guān)于Eps

和MinPts密度相連的。密度相連性是一個(gè)對(duì)稱(chēng)的關(guān)系。pqo第一百零九頁(yè)，共一百四十六頁(yè)。DBSCANDBSCAN算法描述：輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，半徑ε，最少數(shù)目MinPts。輸出：所有生成的簇，達(dá)到密度要求。1.REPEAT2.從數(shù)據(jù)庫(kù)中抽取一個(gè)未處理過(guò)的點(diǎn)；3.IF抽出的點(diǎn)是核心點(diǎn)THEN找出所有從該點(diǎn)密度可達(dá)的對(duì)象，形成一個(gè)簇4.ELSE抽出的點(diǎn)是邊緣點(diǎn)(非核心對(duì)象)，跳出本次循環(huán)，尋找下一點(diǎn)；5.UNTIL所有點(diǎn)都被處理；第一百一十頁(yè)，共一百四十六頁(yè)?；诿芏确椒ǖ木垲?lèi)-DBSCAN

下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫(kù)（見(jiàn)下表），對(duì)它實(shí)施DBSCAN算法。根據(jù)所給的數(shù)據(jù)通過(guò)對(duì)其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入ε=1，MinPts=4）

序號(hào)屬性1屬性2121251312422532642752862913102311531224樣本事務(wù)數(shù)據(jù)庫(kù)第一百一十一頁(yè)，共一百四十六頁(yè)。DBSCAN聚類(lèi)過(guò)程第1步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)（小于4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第2步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第3步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第一百一十二頁(yè)，共一百四十六頁(yè)。DBSCAN聚類(lèi)過(guò)程第4步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)（直接可達(dá)4個(gè)，間接可達(dá)3個(gè)），聚出的新類(lèi){1，3，4，5，9，10，12}，選擇下一個(gè)點(diǎn)。第一百一十三頁(yè)，共一百四十六頁(yè)。DBSCAN聚類(lèi)過(guò)程第5步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)5，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第6步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第一百一十四頁(yè)，共一百四十六頁(yè)。DBSCAN聚類(lèi)過(guò)程第7步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)，聚出的新類(lèi){2，6，7，8，11}，選擇下一個(gè)點(diǎn)。第一百一十五頁(yè)，共一百四十六頁(yè)。DBSCAN聚類(lèi)過(guò)程第8步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)8，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。第9步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)9，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第10步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)10，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第11步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)11，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。第12步，選擇12點(diǎn)，已經(jīng)在簇1中，由于這已經(jīng)是最后一點(diǎn)所有點(diǎn)都以處理，程序終止。序號(hào)屬性1屬性2121251312422532642752862913102311531224第一百一十六頁(yè)，共一百四十六頁(yè)?；诿芏确椒ǖ木垲?lèi)-DBSCAN步驟選擇的點(diǎn)在ε中點(diǎn)的個(gè)數(shù)通過(guò)計(jì)算可達(dá)點(diǎn)而找到的新簇112無(wú)222無(wú)333無(wú)445簇C1：{1，3，4，5，9，10，12}553已在一個(gè)簇C1中663無(wú)775簇C2：{2，6，7，8，11}882已在一個(gè)簇C2中993已在一個(gè)簇C1中10104已在一個(gè)簇C1中，11112已在一個(gè)簇C2中12122已在一個(gè)簇C1中算法執(zhí)行過(guò)程：第一百一十七頁(yè)，共一百四十六頁(yè)。DBSCANOriginalPointsClusters特點(diǎn)：抗噪聲能處理任意形狀聚類(lèi)第一百一十八頁(yè)，共一百四十六頁(yè)。關(guān)聯(lián)規(guī)則第一百一十九頁(yè)，共一百四十六頁(yè)。關(guān)聯(lián)規(guī)則：Association

Rule關(guān)聯(lián)規(guī)則挖掘：在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。應(yīng)用：購(gòu)物籃分析、交叉銷(xiāo)售、產(chǎn)品目錄設(shè)計(jì)等。舉例：

規(guī)則形式:“Body

=>

Head[support,confidence]”buys(x,“diapers”)=>buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)=>grade(x,“A”)[1%,75%]第一百二十頁(yè)，共一百四十六頁(yè)。規(guī)則度量：支持度與可信度查找所有的規(guī)則

X&Y=>Z具有最小支持度和可信度支持度,

s,一次交易中包含{X、Y、Z}的可能性可信度,

c,

包含{X、Y}的交易中也包含Z的條件概率設(shè)最小支持度為50%,最小可信度為50%,則可得到A=>C(50%,66.6%)C=>A(50%,100%)買(mǎi)尿布的客戶二者都買(mǎi)的客戶買(mǎi)啤酒的客戶第一百二十一頁(yè)，共一百四十六頁(yè)。關(guān)聯(lián)規(guī)則挖掘問(wèn)題就是根據(jù)用戶指定的最小支持度和最小可信度來(lái)尋找強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘問(wèn)題可以劃分成兩個(gè)子問(wèn)題：1.發(fā)現(xiàn)頻繁項(xiàng)目集:通過(guò)用戶給定最小支持度，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。2.生成關(guān)聯(lián)規(guī)則:通過(guò)用戶給定最小可信度，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。第1個(gè)子問(wèn)題是近年來(lái)關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。關(guān)聯(lián)規(guī)則挖掘基本過(guò)程第一百二十二頁(yè)，共一百四十六頁(yè)。經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法Apriori算法是通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)來(lái)完成頻繁項(xiàng)目集發(fā)現(xiàn)的。首先產(chǎn)生1_頻繁項(xiàng)目集L1，然后產(chǎn)生2_頻繁項(xiàng)目集L2，直到不能再擴(kuò)展頻繁項(xiàng)目集的元素?cái)?shù)目為止。TIDItemset1001，3，42002，3，53001，2，3，54002，51994年，Agrawal等人提出了著名的Apriori算法。第一百二十三頁(yè)，共一百四十六頁(yè)。Apriori算法例子DatabaseDC1L1L2C2ScanDL3ScanDC3ScanDC4ScanDScanD?L4Minsupport=50%

C1：1-候選集L1：1-頻繁項(xiàng)目集C2：2-候選集L2：2-頻繁項(xiàng)目集C3：3-候選集L3：3-頻繁項(xiàng)目集C4：4-候選集L4：4-頻繁項(xiàng)目集L3是最大頻繁項(xiàng)目集第一百二十四頁(yè)，共一百四十六頁(yè)。

根據(jù)上面介紹的關(guān)聯(lián)規(guī)則挖掘的兩個(gè)步驟，在得到了所有頻繁項(xiàng)目集后，可以按照下面的步驟生成關(guān)聯(lián)規(guī)則：對(duì)于每一個(gè)頻繁項(xiàng)目集l，生成其所有的非空子集；對(duì)于l

的每一個(gè)非空子集x，計(jì)算Conference（x），如果Confidence（x）≥minconfidence，那么“x(l-x)”成立。關(guān)聯(lián)規(guī)則生成算法:從給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則該算法的核心是genrules遞歸過(guò)程，它實(shí)現(xiàn)一個(gè)頻繁項(xiàng)目集中所有強(qiáng)關(guān)聯(lián)規(guī)則的生成。Rule-generate（L，minconf）（1）FOReachfrequentitemsetlkinL（2）genrules（lk

，lk）;關(guān)聯(lián)規(guī)則的生成問(wèn)題第一百二十五頁(yè)，共一百四十六頁(yè)。Rule-generate算法例子Minconfidence=80%序號(hào)lkxm-1ConfidenceSupport規(guī)則（是否是強(qiáng)規(guī)則）1235267%50%235（否）2235367%50%325（否）3235567%50%523（否）423523100%50%235（是）52352567%