第八章 數(shù)據(jù)開采課件

一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘二、決策樹方法（分類方法）三、聚類方法四、關(guān)聯(lián)分析方法第八章數(shù)據(jù)挖掘本章內(nèi)容

第八章數(shù)據(jù)開采(1)80年在美國召開了第一屆國際機器學習研討會；(2)89年8月于美國底特律市召開的第一屆KDD國際學術(shù)會議；(3)95年在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學術(shù)會議；(4)我國于87年召開了第一屆全國機器學習研討會。第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.1知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的興起第八章數(shù)據(jù)開采

知識發(fā)現(xiàn)（KDD）被認為是從數(shù)據(jù)中發(fā)現(xiàn)有用知識的整個過程。數(shù)據(jù)挖掘（DM）被認為是KDD過程中的一個特定步驟，它用專門算法從數(shù)據(jù)中抽取模式（patterns）。

KDD過程定義（Fayyad，Piatetsky-Shapiror，andSmyth1996）：

從大量數(shù)據(jù)中提取出可信的、新穎的、有用的并能被人理解的模式的高級處理過程?！澳Ｊ健笨梢钥闯墒侵R的雛形，經(jīng)過驗證、完善后形成知識。第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.2知識發(fā)現(xiàn)和數(shù)據(jù)挖掘概念第八章數(shù)據(jù)開采KDD過程數(shù)據(jù)源數(shù)據(jù)數(shù)據(jù)集成目標數(shù)據(jù)預(yù)處理后數(shù)據(jù)轉(zhuǎn)換數(shù)據(jù)模式知識數(shù)據(jù)選擇預(yù)處理數(shù)據(jù)挖掘數(shù)據(jù)轉(zhuǎn)換結(jié)果表達和解釋數(shù)據(jù)準備數(shù)據(jù)挖掘結(jié)果表達和解釋第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.2知識發(fā)現(xiàn)和數(shù)據(jù)挖掘概念第八章數(shù)據(jù)開采若兩個或多個數(shù)據(jù)項的取值之間重復出現(xiàn)且概率很高時，它就存在某種關(guān)聯(lián)，可以建立起這些數(shù)據(jù)項的關(guān)聯(lián)規(guī)則。一個相關(guān)規(guī)則的形式為：A1∧A2…∧Ai→B1∧B2…∧Bj。如果B1,B2,Bj出現(xiàn)，那么A1,A2,Ai一定出現(xiàn)，這表明A1,A2,Ai與B1,B2,Bj有某種關(guān)聯(lián)第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.3數(shù)據(jù)挖掘任務(wù)關(guān)聯(lián)分析數(shù)據(jù)挖掘任務(wù)主要有：關(guān)聯(lián)分析、聚類、概念描述

、偏差檢測、預(yù)測。第八章數(shù)據(jù)開采

數(shù)據(jù)庫中的數(shù)據(jù)可以劃分為一系列有意義的子集，即類。在同一類別中，個體之間的距離較小，而不同類別上的個體之間的距離偏大。第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.3數(shù)據(jù)挖掘任務(wù)聚類分析第八章數(shù)據(jù)開采對數(shù)據(jù)庫中一類對象的內(nèi)涵進行描述，以概括這個類的有關(guān)特征。概念描述是對數(shù)據(jù)庫的整體信息有全面概括，從數(shù)據(jù)庫中歸納抽象的信息。類的內(nèi)涵描述有兩種：（1）特征描述：對類中對象的共同特點進行描述（2）辨別性描述：對兩個或多個類之間的區(qū)別描述產(chǎn)生辨別性描述的方法有：(1)決策樹方法：ID3，IBLE等(2)神經(jīng)網(wǎng)絡(luò)方法(3)遺傳算法第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.3數(shù)據(jù)挖掘任務(wù)

概念描述第八章數(shù)據(jù)開采數(shù)據(jù)庫中的數(shù)據(jù)存在很多異常情況，從數(shù)據(jù)分析中發(fā)現(xiàn)這些異常情況也是很重要的，以引起人們對它更多的注意。偏差檢測的數(shù)據(jù)模式有極值點、斷點、拐點、零點和邊界等不同的偏差對象。第八章數(shù)據(jù)挖掘一、

知識發(fā)現(xiàn)與數(shù)據(jù)挖掘1.3數(shù)據(jù)挖掘任務(wù)偏差檢測

預(yù)測是利用歷史數(shù)據(jù)找出變化規(guī)律，建立模型，并用此模型來預(yù)測未來數(shù)據(jù)的種類，特征等。預(yù)測第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.1基本概念決策樹方法著眼于從一組無次序、無規(guī)則的示例中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點（非葉結(jié)點）進行屬性值的比較，并根據(jù)不同的屬性值決定從此結(jié)點向下的分支，直到葉結(jié)點才得到結(jié)論。葉結(jié)點的條件：結(jié)點內(nèi)所有示例屬于同類。內(nèi)部結(jié)點用作分支判斷的屬性稱為測試屬性。

——怎么選擇測試屬性？二、

決策樹方法（分類分析）分類規(guī)則：從樹根到葉結(jié)點的一條路徑對應(yīng)著一條合取規(guī)則。第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.2CLS（ConceptLearningSystem）方法二、

決策樹方法（分類分析）工作過程：首先找出最有判別力的因素，把數(shù)據(jù)分成兩個子集，每個子集又選擇最有判別力的因素進行劃分，一直進行到所有子集僅包含同一類型的數(shù)據(jù)為止，最后得到一棵決策樹，可以用來對新的樣例進行分類。

沒有明確選擇測試屬性的標準Quinlan在1979年引進了信息論中的互信息，作為特征判別能力的度量?！狪D3方法第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.3信息論原理源信息宿信息信道干預(yù)源信息是客觀系統(tǒng)本身固有的信息。宿信息是接受系統(tǒng)所呈現(xiàn)的信息。信息熵（先驗熵）、條件熵（后驗熵）、互信息互信息=信息熵-條件熵三者關(guān)系：二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采條件熵：H（U/V）=-∑P(vj)∑P(ui/vj)logP(ui/vj)第八章數(shù)據(jù)挖掘2.3信息論原理源U宿V信道P(V/U)u1,u2,…,urv1,v2,…,vq信道模型:計算：信息熵：H（U）=-∑P（ui）logP（ui）irrijqP(U)=(P(u1),P(u2),…,P(ur))給定：P(V/U)=P(v1/u1)P(v2/u1)…P(vq/u1)P(v1/u2)P(v2/u2)…P(vq/u2)P(v1/ur)P(v2/ur)…P(vq/ur)傳輸概率二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.4ID3算法主算法：訓練集PE，NE取子集建窗口窗口PE’，NE’生成決策樹測試PE，NE存在錯判的PE’’，NE’’？擴展窗口PE’=PE’+PE’’NE’=NE’+NE’’YN結(jié)束二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.4ID3算法建樹算法：（1）對當前集合，計算各特征的互信息；（2）選擇互信息最大的特征AK；（3）根據(jù)特征AK的取值把當前集合分為若干個子集；（4）對既含正例又含反例的子集，遞歸調(diào)用建樹算法；（5）對只含正例或反例的子集，對應(yīng)分支標上P或N，返回調(diào)用處。二、

決策樹方法（分類分析）優(yōu)缺點：第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.4ID3算法示例：二、

決策樹方法（分類分析）1晴熱高無風N2晴熱高有風N3多云熱高無風P4雨適中高無風P5雨冷正常無風P6雨冷正常有風N7多云冷正常有風P8晴適中高無風N9晴冷正常無風P10雨適中正常無風P11晴適中正常有風P12多云適中高有風P13多云熱正常無風P14雨適中高有風N天氣氣溫濕度風P（u1）=9/14u1代表正例Pu2代表反例P（u2）=5/14A1=天氣取值

v1=晴，v2=多云，v3=雨第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.4ID3算法示例：NPNP天氣濕度風高正常有風無風多云P晴

雨二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.5ID3應(yīng)用示例

示例：用決策樹方法挖掘保險業(yè)務(wù)（醫(yī)療保險）數(shù)據(jù)中的投資風險規(guī)則設(shè)醫(yī)療保險數(shù)據(jù)庫由個人信息表、單位信息表、一定時間內(nèi)（月）索賠單據(jù)表等數(shù)據(jù)表組成，各表信息如下：保險號姓名性別出生日期單位編號年薪投保日期張女670121305423000970901劉男541123200115508970402李男43082520457086970623……個人信息表：二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.5ID3應(yīng)用示例

編號單位名稱類別投保日期3054XX房產(chǎn)公司企業(yè)9709012001XX公交公司企業(yè)9704022045XX工業(yè)大學事業(yè)970623…………單位信息表：月索賠單據(jù)表：單號營業(yè)員保險號索賠金額索賠日期000121王300970901000101劉158970902000340劉208970923二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.5ID3應(yīng)用示例

數(shù)據(jù)挖掘工作的幾個步驟：1）數(shù)據(jù)整理保險號年齡性別單位類別年薪索賠次數(shù)是否索賠63女企業(yè)230006Y33男企業(yè)155080N55男事業(yè)70863Y2）數(shù)據(jù)分析：索賠次數(shù)可以去掉。3）數(shù)據(jù)挖掘：

年齡分段；年薪分段。

ID3建樹4）挖掘結(jié)果解釋：二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.5ID3應(yīng)用示例

數(shù)據(jù)離散化（分段）

無指導離散化：等間隔離散、等頻度離散有指導離散化：基于信息熵的離散化等基于信息熵的離散化基本原理：給定一樣本集S，如果用邊界T將S劃分為S1和S2兩部分，則劃分后的熵為：H（S，T）=H（S1）+H（S2）|S1||S||S2||S|選取使H（S，T）取值最小的邊界T進行劃分。二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.6IBLE算法基本思想2.7IBLE算法為了克服ID3的缺點，而設(shè)計的。用信道容量代替互信息作為特征判別力的度量結(jié)點是一組特征，而不只一個特征決策規(guī)則樹規(guī)則2規(guī)則3規(guī)則1u1u1u1u2u2u2二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘2.7IBLE算法決策規(guī)則樹中非葉結(jié)點均為規(guī)則。規(guī)則形式為:

特征:A1，A2，...，.Am

權(quán)值:W1，W2，...，.Wm

標準值:V1，V2，...，.Vm

閾值:Sp，Sn該規(guī)則可形式描述為：（1）sum:=0；（2）對i:=1到m作：若Ai=Vi，則sum:=sum+wi；（3）若sum

sn，則該例為N類；（4）若sum

sp，則該例為P類；（5）若sn<sum<sp，則該例暫不能判，轉(zhuǎn)下一條規(guī)則判別。其中sum表示權(quán)和。二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘決策規(guī)則樹結(jié)點IBLE算法組成部分：預(yù)處理，建規(guī)則算法，建決策樹算法，類判定算法PENE建規(guī)則測試PEPPENPEMNEPNENNEM二、

決策樹方法（分類分析）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.1聚類將集合分組成為由類似的對象組成的多個類的過程被稱為聚類。主要的聚類方法：劃分方法、層次方法、基于密度方法、基于網(wǎng)格的方法、基于模型的方法。三、

聚類分析與分類的區(qū)別：不依賴預(yù)先定義的類和帶類標識的訓練實例。聚類屬于無指導學習，而分類是指導性的學習。第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.2劃分法算法思想：對N個對象的數(shù)據(jù)集，構(gòu)建數(shù)據(jù)的K個劃分，每個劃分表示一個聚簇，并且K<=N。即，它將數(shù)據(jù)劃分為K個組，同時滿足如下的要求：

每個組至少包含一個對象；每個對象必須屬于且只屬于一個組。三、

聚類分析目前較流行的兩個劃分方法是：K-平均算法：每個簇用該簇中所有對象的平均值來表示；K-中心算法：每個簇用最接近簇中心的那個對象來表示。第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.2劃分法三、

聚類分析K-平均算法：輸入：簇的數(shù)目K和包含N個對象的數(shù)據(jù)集輸出：K個簇，使平方誤差準則最小方法：任意選擇K個對象作為初始的簇中心；repeat

根據(jù)對象與各簇中心的距離，將每個對象賦給最近的簇；更新簇的平均值，即計算每個簇的中心；3.Until平方誤差準則函數(shù)收斂第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.2劃分法三、

聚類分析K-平均算法：簇是否不再變化結(jié)束NY任意選定K個初始的簇中心將每個對象分配給最臨近的簇更新簇平均值缺陷：

不適合發(fā)現(xiàn)非凸面形狀的簇；不適合發(fā)現(xiàn)大小相差很大的簇；對噪聲和孤立點數(shù)據(jù)敏感。算法復雜度：O（nkt）第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.2劃分法三、

聚類分析K-中心算法：方法：任意選擇K個對象作為初始的簇中心；repeat將每個對象賦給最臨近的簇；隨機地選擇一個非中心點對象，并計算迭代后的總代價；如果總代價小于0，迭代成功，形成新的K個中心點集合；3.until不再發(fā)生變化優(yōu)點：對噪聲和孤立點不敏感缺陷：計算代價高第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.3層次法三、

聚類分析算法思想：首先將每個對象作為一簇，然后這些原子簇為越來越大的簇，直到所有的對象都在一個簇中。CURE(ClusteringUsingREpresentatives)CURE思想：用固定數(shù)目的代表點來表示一個簇。每個簇的代表點通過這種方式產(chǎn)生：首先選擇類中分散的點，然后根據(jù)一個特定的收縮因子向類中心“收縮”。在算法的每一步，有最近距離的代表點對（每個點來自一個不同的類）的兩個類被合并。第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.3層次法三、

聚類分析優(yōu)點：每個類有多于一個的代表點使得CURE可以適宜非球形的幾何形狀。類的收縮可以有助于控制孤立點的影響。因此，CURE對孤立點的處理更加健壯，而且能夠識別非球形和大小變化較大的類。

CURE(ClusteringUsingREpresentatives)劃分法聚類結(jié)果第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.3層次法三、

聚類分析代表點的產(chǎn)生與收縮：CURE第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.4基于密度的方法——DBSCAN三、

聚類分析算法思想：算法將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有“噪聲”的數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。它定義簇為密度相連的點的最大集合。有關(guān)定義：核心對象：如果一個對象的EPS鄰域至少包含了MinPts個對象，則稱該對象為核心對象。直接密度可達：給定一個對象集合D，如果p在q的EPS鄰域內(nèi)，而q是一個核心對象，則稱p從對象q出發(fā)是直接密度可達的。密度可達：如果存在一個對象鏈p1,p2,…,pn,p1=q,pn=p,對pi∈D，（1≤i≤n），pi+1是從pi關(guān)于EPS和MinPts直接密度可達的，則對象p是從對象q關(guān)于EPS和MinPts密度可達的。密度相連：如果對象集合D中存在一個對象o，使得對象p、q是從o關(guān)于EPS和MinPts密度可達的，那么對象p，q是關(guān)于EPS和MinPts密度相連的。

第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.4基于密度的方法——DBSCAN三、

聚類分析基于密度的簇：基于密度可達性的最大的密度相連對象的集合

DBSCAN的原理如下：檢查數(shù)據(jù)庫中每個點的EPS鄰域，如果一個點p的EPS鄰域包含多于MinPts個點，則創(chuàng)建一個以p為核心的新簇。然后，反復尋找從核心對象直接密度可達的對象，這個過程還涉及一些密度可達簇的合并。當沒有新的點可以被添加到任何簇時，該過程結(jié)束。第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘3.4基于密度的方法——DBSCAN三、

聚類分析參數(shù)設(shè)置接受用戶給定的EPS和MinPts的設(shè)置值查找核心對象根據(jù)EPS和MinPts的設(shè)置值，掃描數(shù)據(jù)庫，找出所有核心對象，建立初始簇群簇的擴展與合并根據(jù)直接密度可達性擴展和合并簇篩除噪聲把不屬于任何簇的對象標識為噪聲第八章數(shù)據(jù)開采第八章數(shù)據(jù)挖掘四、

關(guān)聯(lián)分析4.1基本概念設(shè)I={i1