專題數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型

1、第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,2,,4.1 廣義知識 4.2 關(guān)聯(lián)知識4.3 分類知識4.4 預(yù)測型知識4.5 偏差型知識,3,4.1 廣義知識,從數(shù)據(jù)分析角度出發(fā)，數(shù)據(jù)挖掘可以分為兩種類型：描述型數(shù)據(jù)挖掘——以簡潔概述的方式表達(dá)數(shù)據(jù)中的存在一些有意義的性質(zhì)預(yù)測型數(shù)據(jù)挖掘——通過對所提供數(shù)據(jù)集應(yīng)用特定方法分析所獲得的一個或一組數(shù)據(jù)模型，并將該模型用于預(yù)測未來新數(shù)據(jù)的有關(guān)性質(zhì)。,4,4.1 廣義知識,數(shù)據(jù)庫通常包含了大量細(xì)

2、節(jié)性數(shù)據(jù)，然而用戶卻常常想要得到能以簡潔描述性方式所提供的概要性總結(jié)(summarized)。這樣的數(shù)據(jù)摘要能夠提供一類數(shù)據(jù)的整體情況描述；或與其它類別數(shù)據(jù)相比較的有關(guān)情況的整體描述。此外用戶通常希望能輕松靈活地獲得從不同角度和分析細(xì)度對數(shù)據(jù)所進(jìn)行的描述。描述型數(shù)據(jù)挖掘又稱為概念描述，它是數(shù)據(jù)挖掘中的一個重要組成部分。下面就將主要介紹如何有效地進(jìn)行定性歸納以獲得概念描述的有關(guān)內(nèi)容。,5,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.1.1 廣

3、義知識的概念定義 廣義知識是指類別特征的概括性描述知識，也稱為概念描述。它反映同類事物共同性質(zhì)，是對數(shù)據(jù)的概括、精煉和抽象。廣義知識是對大量數(shù)據(jù)的歸納、概括，提煉出帶有普遍性的、概括性的描述統(tǒng)計知識。,6,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,數(shù)據(jù)庫中數(shù)據(jù)及對象在基本概念層次包含了許多細(xì)節(jié)性的數(shù)據(jù)信息。在商場銷售數(shù)據(jù)庫的商品信息數(shù)據(jù)中，就包含了許多諸如：商品編號、商品名稱、商品品牌等低層次信息，對這類大量的數(shù)據(jù)進(jìn)行更高層次

4、抽象以提供一個概要性描述是十分重要的。例如：對春節(jié)所銷售商品情況進(jìn)行概要描述，對于市場和銷售主管來講顯然是十分重要的。最簡單的描述型數(shù)據(jù)（廣義知識）挖掘就是定性歸納。定性歸納常常也稱為概念描述。這里概念描述涉及一組（同一類別）的對象，諸如：商店?？偷?。概念描述生成對數(shù)據(jù)的定性描述和對比定性描述。定性概念描述提供了一個有關(guān)數(shù)據(jù)整體的簡潔清晰描述（概念內(nèi)涵）對比定性概念描述提供了基于多組（不同類別）數(shù)據(jù)的對比概念描述（概念外延）

5、,7,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,給定存儲在數(shù)據(jù)庫中的大量數(shù)據(jù)，能夠用簡潔清晰的高層次抽象泛化名稱來描述相應(yīng)的定性概念是非常重要的，這樣用戶就可以利用基于多層次數(shù)據(jù)抽象的功能對數(shù)據(jù)中所存在的一般性規(guī)律進(jìn)行探索。例如在商場數(shù)據(jù)庫中，銷售主管不用對每個顧客的購買記錄進(jìn)行檢查，而只需要對更高抽象層次的數(shù)據(jù)進(jìn)行研究即可。如：對按地理位置進(jìn)行劃分的顧客購買總額、每組顧客的購買頻率以及顧客收入情況進(jìn)行更高層次的研究分析。這種多維多層次的數(shù)據(jù)

6、泛化分析與數(shù)據(jù)倉庫中的多維數(shù)據(jù)分析，,8,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.1.2 廣義知識的發(fā)現(xiàn)方法要順利完成概要描述任務(wù)，就需要一個十分重要的數(shù)據(jù)挖掘功能：數(shù)據(jù)泛化。數(shù)據(jù)泛化是一個從相對低層概念到更高層概念且對數(shù)據(jù)庫中與任務(wù)相關(guān)的大量數(shù)據(jù)進(jìn)行抽象概述的一個分析過程。對大量數(shù)據(jù)進(jìn)行有效靈活的概述方法主要有兩種1.數(shù)據(jù)立方體2.面向?qū)傩缘囊?guī)約,9,1.數(shù)據(jù)立方體,數(shù)據(jù)立方的維是通過一系列能夠形成層次的屬性或網(wǎng)格，例如：日期（

7、date）可以包含屬性天、周、月、季和年，這些屬性構(gòu)成了維的網(wǎng)格。利用數(shù)據(jù)立方方法（又稱為OLAP方法）進(jìn)行數(shù)據(jù)泛化，就是在數(shù)據(jù)立方中存放著預(yù)先對部分或所有維（屬性）的聚合計算結(jié)果。通常數(shù)據(jù)立方中的數(shù)據(jù)需要經(jīng)過費(fèi)時復(fù)雜的運(yùn)算操作（如：sum、count、average），不同的抽象層次均需要進(jìn)行這類運(yùn)算，將這些運(yùn)算與操作結(jié)果存放在這些數(shù)據(jù)立方中，最終所獲得的這些數(shù)據(jù)立方可用于決策支持、知識發(fā)現(xiàn)，或其它許多應(yīng)用。,10,1.數(shù)據(jù)立方

8、體,對多維數(shù)據(jù)立方的數(shù)據(jù)泛化和數(shù)據(jù)細(xì)化工作，可以通過roll up或drill down操作實現(xiàn)上卷(roll-up)：匯總數(shù)據(jù)消減數(shù)據(jù)立方中的維數(shù)（維規(guī)約），或?qū)傩灾捣夯癁楦邔哟蔚母拍睿ǜ拍罘謱酉蛏吓噬┫裸@(drill-down)：上卷的逆操作由不太詳細(xì)的數(shù)據(jù)到更詳細(xì)的數(shù)據(jù)，可以通過沿維的概念分層向下或引入新的維來實現(xiàn),,12,1.數(shù)據(jù)立方體,數(shù)據(jù)立方方法提供了一種有效的數(shù)據(jù)泛化方法，且構(gòu)成了描述型數(shù)據(jù)挖掘中一個重要功能

9、。數(shù)據(jù)立方體方法局限性：數(shù)據(jù)類型限制多數(shù)商用數(shù)據(jù)立方的實現(xiàn)都是將維的類型限制在數(shù)值類型方面，而且將處理限制在簡單數(shù)值聚合方面。由于許多應(yīng)用涉及到更加復(fù)雜數(shù)據(jù)類型的分析，此時數(shù)據(jù)立方體的方法應(yīng)用有限。缺乏一定的標(biāo)準(zhǔn)數(shù)據(jù)立方方法并不能解決概念描述所能解決的一些重要問題，諸如：在描述中應(yīng)該使用哪些維？在泛化過程應(yīng)該進(jìn)行到哪個抽象層次上。這些問題均要由用戶負(fù)責(zé)提供答案的。,13,2.面向?qū)傩缘臍w約（Attribure-Oriente

10、d Induction, 簡稱AOI）,數(shù)據(jù)立方方法是基于數(shù)據(jù)倉庫、預(yù)先計算的具體實施方法。該方法在進(jìn)行OLAP或數(shù)據(jù)挖掘查詢處理之前，就已進(jìn)行了離線聚合計算。而AOI方法是一種在線數(shù)據(jù)分析技術(shù)方法。1989年首次提出基本思想：首先利用關(guān)系數(shù)據(jù)庫查詢來收集與任務(wù)相關(guān)的數(shù)據(jù)，并通過對任務(wù)相關(guān)數(shù)據(jù)集中各屬性不同值個數(shù)的檢查完成數(shù)據(jù)泛化操作。數(shù)據(jù)泛化操作是通過屬性消減或?qū)傩苑夯ㄓ址Q為概念層次提升）操作來完成的。通過合并（泛化后）相

11、同行并累計它們相應(yīng)的個數(shù)。這就自然減少了泛化后的數(shù)據(jù)集大小。所獲（泛化后）結(jié)果以圖表和規(guī)則等多種不同形式提供給用戶。,14,示例：研究生概念描述,從一個大學(xué)數(shù)據(jù)庫的學(xué)生數(shù)據(jù)中挖掘出研究生的概念描述。所涉及的屬性包括：姓名、性別、專業(yè)、出生地、出生日期、居住地、電話和GPA,15,,AOI方法的第一步就是首先利用數(shù)據(jù)庫查詢語言從大學(xué)數(shù)據(jù)庫中將（與本挖掘任務(wù)相關(guān)的）學(xué)生數(shù)據(jù)抽取出來；然后指定一組與挖掘任務(wù)相關(guān)的屬性集（這對于用戶而言可能比較

12、困難）。例如：假設(shè)根據(jù)屬性城市City、省Province和國家Country定義出生地（BirthPlace）維，在這些屬性中，用戶或許只考慮了城市屬性。為了對出生地進(jìn)行泛化處理，就必須將出生地泛化所涉及的其它屬性也包含進(jìn)來。換句話說，系統(tǒng)應(yīng)能自動包含省和國家作為相關(guān)屬性，以便在歸納過程中可以從城市泛化到更高概念層次。而在另一方面，用戶或許會提供過多的屬性，這時就需要利用前面數(shù)據(jù)預(yù)處理所介紹的數(shù)據(jù)清理和維歸約方法從描述型數(shù)據(jù)挖掘中

13、過濾掉無關(guān)或弱相關(guān)的屬性。,16,,AOI的基本操作是數(shù)據(jù)泛化，其所涉及的操作主要有兩種：屬性消除它基于以下規(guī)則進(jìn)行：若一個屬性（在初始數(shù)據(jù)集中）有許多不同數(shù)值，且（a）該屬性無法進(jìn)行泛化操作（如：沒有定義相應(yīng)的概念層次樹），或（b）它更高層次概念是用其它屬性描述的，這時該屬性就可以從數(shù)據(jù)集中消去.屬性泛化它是基于以下規(guī)則進(jìn)行：若一個屬性（在初始數(shù)據(jù)集中）有許多不同數(shù)值，且該屬性存在一組泛化操作，則可以選擇一個泛化操作對該屬性進(jìn)

14、行處理。,17,,屬性消減和屬性泛化兩條規(guī)則都表明：若一個屬性有許多不同值，則應(yīng)對其應(yīng)用泛化操作。但這也提出一個問題，“究竟一個屬性應(yīng)有多少不同值才能認(rèn)為是許多呢？”。根據(jù)所涉及屬性或具體應(yīng)用情況，一個用戶或許選擇一些屬性仍保留在低層次抽象水平而對其它一些屬性進(jìn)行更高層次的泛化處理。對泛化抽象層次的控制也是相當(dāng)主觀的，這一控制也稱為屬性泛化控制。若屬性被泛化“過高”，就將會導(dǎo)致過分泛化以致所獲（結(jié)果）規(guī)則變得失去意義。另一方面，若屬

15、性泛化沒有到達(dá)“足夠高的層次”，那么“亞泛化”也可能同樣會變得失去意義。因此在基于屬性歸納時掌握泛化平衡是非常重要的。,18,,有許多控制泛化過程的方法，以下就是兩種常用的方法屬性泛化閾值控制該技術(shù)就是對所有屬性統(tǒng)一設(shè)置一個泛化閾值，或每個屬性分別設(shè)置一個閾值；若一個屬性不同取值個數(shù)大于屬性泛化閾值，就需要對相應(yīng)屬性作進(jìn)一步的屬性消減或?qū)傩苑夯僮鳌?shù)據(jù)挖掘系統(tǒng)通常都有一個缺省屬性閾值（一般從2到8）泛化關(guān)系閾值控制若一個泛化關(guān)

16、系中內(nèi)容不相同的行數(shù)（元組數(shù)）大于泛化關(guān)系閾值，這就需要進(jìn)一步進(jìn)行相關(guān)屬性的泛化工作。否則就不需要作更進(jìn)一步的泛化。通常數(shù)據(jù)挖掘系統(tǒng)都預(yù)置這一閾值（一般為10到30）這兩個技術(shù)可以串行使用，即首先應(yīng)用屬性閾值控制來泛化每個屬性；然后再應(yīng)用泛化關(guān)系閾值控制來進(jìn)一步減少泛化關(guān)系的（規(guī)模）大小。,19,對原數(shù)據(jù)集進(jìn)行泛化的處理過程,20,,21,,初始數(shù)據(jù)集,結(jié)果數(shù)據(jù)集,22,面向?qū)傩詺w約的結(jié)果表示,AOI方法的挖掘結(jié)果可以有多種輸出表示形

17、式。,23,組合表表示,在二維組合表中，每一行代表屬性的一個值；每一列代表其它屬性的一個值。在一個n維組合表中，列可能代表多個屬性的值并分欄顯示各屬性累計值,24,用圖（棒圖、餅圖和曲線）表示,25,轉(zhuǎn)換為邏輯規(guī)則形式,通常每個泛化后的數(shù)據(jù)行代表（概念描述）規(guī)則中的一個析取項。由于一個大型數(shù)據(jù)庫中的數(shù)據(jù)通常具有多種不同的分布；因此一個泛化后的數(shù)據(jù)行不可能覆蓋或表達(dá)所有（100％）初始數(shù)據(jù)集中的數(shù)據(jù)行。因此定量信息，諸如滿足規(guī)則條件左邊（

18、自然也滿足規(guī)則右邊）數(shù)據(jù)行數(shù)目與初始數(shù)據(jù)集中總行數(shù)之比，可作為所獲概念描述規(guī)則的一個度量客觀價值的重要參量，帶有這種參量的概念描述規(guī)則就稱為定量描述規(guī)則。,26,,27,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.2 關(guān)聯(lián)知識4.2.1 關(guān)聯(lián)知識的概念關(guān)聯(lián)知識反映一個事件和其他事件之間依賴或相互關(guān)聯(lián)的知識，如果兩項或多項屬性之間存在關(guān)聯(lián)，那么其中一項的屬性值就可以依據(jù)其他屬性值進(jìn)行預(yù)測。 關(guān)聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)

19、據(jù)項之間相互聯(lián)系的有關(guān)知識。隨著收集和存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，人們對從這些數(shù)據(jù)中挖掘相應(yīng)的關(guān)聯(lián)知識越來越有興趣。例如：從大量的商業(yè)交易記錄中發(fā)現(xiàn)有價值的關(guān)聯(lián)知識就可幫助進(jìn)行商品目錄的設(shè)計、交叉營銷或幫助進(jìn)行其它有關(guān)的商業(yè)決策。挖掘關(guān)聯(lián)知識的一個典型應(yīng)用實例就是市場購物分析“什么商品組或集合顧客多半會在一次購物時同時購買”,28,,給定: 事務(wù)數(shù)據(jù)庫， 每個事務(wù)是一系列商品（一個消費(fèi)者一次購買的物品）找到: 所有 的規(guī)則

20、，這些規(guī)則能夠表明這些列商品和另一系列商品相關(guān)。E.g., 購買汽車配件的人中有98%會購買汽車服務(wù)應(yīng)用* ? Maintenance Agreement (那些商品能夠加強(qiáng)日常消費(fèi)？)家用電器 ? * (那些商品應(yīng)該保持高庫存？),29,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.2.2 關(guān)聯(lián)知識的發(fā)現(xiàn)方法購物模式的關(guān)聯(lián)規(guī)則:支持度與可信度關(guān)聯(lián)規(guī)則的支持度（support）和信任度（confidence）是兩個度量有關(guān)

21、規(guī)則趣味性的方法。支持度描述了一個被挖掘出的關(guān)聯(lián)規(guī)則的有用性，信任度描述了一個被挖掘出的關(guān)聯(lián)規(guī)則的確定性。規(guī)則（computer->financial_management_software）的支持度為2%，就表示所分析的交易記錄數(shù)據(jù)中有2%交易記錄同時包含電腦和金融管理軟件（即在一起被購買）。規(guī)則（computer->financial_management_software）的60信任度則表示有60%的顧客在購買電腦

22、的同時還會購買金融管理軟件。通常如果一個關(guān)聯(lián)規(guī)則滿足最小支持度閾值（min_support）和最小信任度閾值（min_confidence），那么就認(rèn)為該關(guān)聯(lián)規(guī)則是有意義的；而用戶或?qū)＜铱梢栽O(shè)置最小支持度閾值和最小信任度閾值。,30,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.2.2 關(guān)聯(lián)知識的發(fā)現(xiàn)方法基本概念：一個數(shù)據(jù)項的集合就稱為項集(Itemset)一個包含k個數(shù)據(jù)項（屬性）的項集就稱為k?項集。{computer, finan

23、cial_management_software}就是一個2-項集。一個項集的出現(xiàn)頻度就是整個交易數(shù)據(jù)集中包含該項集的交易記錄數(shù)，這也稱為是該項集的支持度（support count）。若一個項集的出現(xiàn)頻度大于最小支持度閾值乘以交易記錄集D中記錄數(shù)，那么就稱該項集滿足最小支持度閾值滿足最小支持度閾值所對應(yīng)的交易記錄數(shù)就稱為最小支持頻度（minimum support count）。滿足最小支持閾值的項集就稱為頻繁項集（frequ

24、ent itemset）。所有頻繁k?項集的集合就記為Lk。,31,Apriori算法,一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁集的算法，使用候選項集找頻繁項集?；舅枷耄喊l(fā)現(xiàn)所有的頻繁項集，根據(jù)定義，這些項集的頻度至少應(yīng)等于（預(yù)先設(shè)置的）最小支持頻度；根據(jù)所獲得的頻繁項集，產(chǎn)生相應(yīng)的強(qiáng)關(guān)聯(lián)規(guī)則。根據(jù)定義這些規(guī)則必須滿足最小信任度閾值。,32,,關(guān)聯(lián)規(guī)則的分類1.基于規(guī)則中處理的變量的類別分類布爾型：性別＝男 -> 職業(yè)

25、=“網(wǎng)絡(luò)工程師”數(shù)值型：2.基于規(guī)則中數(shù)據(jù)的抽象層次分類 3.基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)分類 單維的多維的,33,Apriori算法,Apriori算法是挖掘產(chǎn)生布爾關(guān)聯(lián)規(guī)則所需頻繁項集的基本算法，它也是一個很有影響的關(guān)聯(lián)規(guī)則挖掘算法。Apriori算法利用了一個層次順序搜索的循環(huán)方法來完成頻繁項集的挖掘工作。這一循環(huán)方法就是利用k-項集來產(chǎn)生(k+1)?項集。具體做法就是：首先，通過掃描數(shù)據(jù)集，產(chǎn)生一個大的

26、候選數(shù)據(jù)項集,并計算每個候選數(shù)據(jù)項發(fā)生的次數(shù)，然后基于預(yù)先給定的最小支持度生成頻繁1-項集的集合，該集合記作L1；然后基于L1和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生頻繁2-項集L2；用同樣的方法，直到生成頻繁n-項集Ln，其中已不再可能生成滿足最小支持度的（N+1）－項集。最后，從大數(shù)據(jù)項集中導(dǎo)出規(guī)則。每挖掘一層，就需要掃描整個數(shù)據(jù)庫一遍。,34,,為提高按層次搜索并產(chǎn)生相應(yīng)頻繁項集的處理效率。 Apriori算法利用了一個重要性質(zhì)，又稱為A

27、priori性質(zhì)來幫助有效縮小頻繁項集的搜索空間。,35,Apriori算法中的關(guān)鍵步驟,36,Apriori算法中的關(guān)鍵步驟,37,實例1,假定最小事務(wù)支持計數(shù)為2（即min_sup=2/9=22%）,38,,,39,,40,,,41,算法描述,42,,43,,5.2.3 從頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則,44,,,45,實例2,46,關(guān)聯(lián)規(guī)則的應(yīng)用,前件和后件規(guī)則中的信任度和支持度,47,關(guān)聯(lián)規(guī)則的表述(Table Form ),48,用圖形

28、可視化的表述關(guān)聯(lián)規(guī)則,49,用圖形可視化的表述關(guān)聯(lián)規(guī)則,50,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.2.3 關(guān)聯(lián)規(guī)則應(yīng)用實例例如某超級市場的銷售系統(tǒng)，記錄了5個顧客的購物清單,51,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,采用著名的Apriori算法多次掃描數(shù)據(jù)庫，得出支持度大于（等于）40%的數(shù)據(jù),52,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,對支持度大于（等于）40%同時購買兩種商品的數(shù)據(jù)進(jìn)行統(tǒng)計,53,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,支持度大于（

29、等于）40%同時購買三種商品的數(shù)據(jù)進(jìn)行統(tǒng)計,54,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,得出下列規(guī)則：（1）買了摩托車的顧客同時買手套或頭盔的支持度是40% ，置信度是66.6%；（2）買了手套的顧客同時買摩托車或頭盔的支持度是40%，置信度是66.6%；（3）買了頭盔的顧客同時買手套或摩托車的支持度是40%，置信度是50%。按照第（1）條關(guān)系，將摩托車降價以促銷手套或頭盔，就可能賠本；而按照第（3）條關(guān)系，將頭盔降價以促銷摩托車，

30、就能盈利；利用第（2）條關(guān)系，將手套降價以促銷摩托車，有可能引不起顧客的興趣。,55,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.3 分類知識4.3.1 分類知識的概念 分類：把給定的數(shù)據(jù)劃分到一定的類別中。分類是預(yù)測分類標(biāo)號，即離散型。分類知識：反映同類事物共同性質(zhì)的特征型知識和不同事物之間的差異型特征知識。,56,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.3.2 分類知識的發(fā)現(xiàn)方法分類過程：首先，在已知訓(xùn)練數(shù)據(jù)集上，根據(jù)屬性特征，為每

31、一種類別找到一個合理的描述或模型，即分類規(guī)則；其次，根據(jù)規(guī)則對新數(shù)據(jù)進(jìn)行分類。,57,具體步驟（P83）,1 ：建立一個模型，描述給定的數(shù)據(jù)類集或概念集（簡稱訓(xùn)練集） 通過分析由屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型。每個元組屬于一個預(yù)定義的類，由類標(biāo)號屬性確定。用于建立模型的元組集稱為訓(xùn)練數(shù)據(jù)集，其中每個元組稱為訓(xùn)練樣本。由于給出了類標(biāo)號屬性，因此該步驟又稱為有指導(dǎo)的學(xué)習(xí)。如果訓(xùn)練樣本的類標(biāo)號是未知的，則稱為無指導(dǎo)的學(xué)習(xí)（聚類）。學(xué)習(xí)模型

32、可用分類規(guī)則、決策樹和數(shù)學(xué)公式的形式給出。通常分類學(xué)習(xí)所獲得的模型可以表示為分類規(guī)則形式、決策樹形式，或數(shù)學(xué)公式形式。,58,具體步驟,2.使用模型進(jìn)行分類首先對模型分類準(zhǔn)確率進(jìn)行估計如果一個學(xué)習(xí)所獲模型的準(zhǔn)確率經(jīng)測試被認(rèn)為是可以接受的，那么就可以使用這一模型對未來數(shù)據(jù)行或?qū)ο螅ㄆ漕悇e未知）進(jìn)行分類。,59,應(yīng)用,信譽(yù)證實醫(yī)療診斷性能測試市場營銷示例：現(xiàn)有一個顧客郵件地址數(shù)據(jù)庫，該數(shù)據(jù)庫內(nèi)容包含有關(guān)顧客情況的描述（例如年齡

33、、收入、職業(yè)和信用等級等）。利用分類數(shù)據(jù)挖掘技術(shù)可以將顧客被分類為是否會成為在本商場購買商品的顧客，這個郵件地址可以給潛在顧客發(fā)送用于促銷的新商品宣傳冊和將要開始的商品打折信息。,60,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,分類規(guī)則的挖掘常用方法：決策樹方法貝葉斯方法人工神經(jīng)網(wǎng)絡(luò)方法粗集方法遺傳算法,61,對各種分類方法比較標(biāo)準(zhǔn),預(yù)測準(zhǔn)確率——描述（學(xué)習(xí)所獲）模型能夠正確預(yù)測未知對象類別或（類別）數(shù)值的能力。速度——描述在構(gòu)造和

34、使用模型時的計算效率。魯棒性——描述在數(shù)據(jù)帶有噪聲和有數(shù)據(jù)遺失情況下，（學(xué)習(xí)所獲）模型仍能進(jìn)行正確預(yù)測的能力?？蓴U(kuò)展性——描述對處理大量數(shù)據(jù)并構(gòu)造相應(yīng)學(xué)習(xí)模型所需要的能力。易理解性——描述學(xué)習(xí)所獲模型表示的可理解程度,62,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.4 預(yù)測型知識4.4.1 預(yù)測型知識的概念預(yù)測（prediction）是構(gòu)造和使用模型評估無標(biāo)號樣本類，或評估給定的樣本可能具有的屬性或區(qū)間值預(yù)測型知識：根據(jù)時間

35、序列型數(shù)據(jù)，由歷史的和當(dāng)前的數(shù)據(jù)去推測未來的數(shù)據(jù)，也可以認(rèn)為是以時間為關(guān)鍵屬性的關(guān)聯(lián)知識。預(yù)測的目的是從歷史數(shù)據(jù)中自動推導(dǎo)出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進(jìn)行預(yù)測。在這種觀點(diǎn)下，分類和回歸是兩類主要預(yù)測問題。其中分類是預(yù)測離散或標(biāo)稱值，而回歸用于預(yù)測連續(xù)或有序值。一般認(rèn)為：用預(yù)測法預(yù)測類標(biāo)號為分類，用預(yù)測法預(yù)測連續(xù)值為預(yù)測。連續(xù)值的預(yù)測一般用回歸統(tǒng)計技術(shù)建模。回歸方法包括：線性回歸、多元回歸、非線性回歸和其他回歸方法等。,

36、63,第5章 數(shù)據(jù)挖掘中常用算法,5.3 決策樹算法用于分類和預(yù)測。決策樹學(xué)習(xí)是以樣本為基礎(chǔ)的歸納學(xué)習(xí)方法?；舅惴ㄊ秦澬乃惴?，采用自頂向下的遞歸方式構(gòu)造決策樹。決策樹（Decision Tree）又稱為判定樹，是運(yùn)用于分類的一種樹結(jié)構(gòu)。其中的每個內(nèi)部結(jié)點(diǎn)（internal node）代表對某個屬性的一次測試，每條邊代表一個測試結(jié)果，葉結(jié)點(diǎn)（leaf）代表某個類（class）或者類的分布（class distribution），最

37、上面的結(jié)點(diǎn)是根結(jié)點(diǎn)。決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。若要對一個實體分類，從樹根開始進(jìn)行測試，按特征的取值分枝向下進(jìn)入下層節(jié)點(diǎn)，對該節(jié)點(diǎn)進(jìn)行測試，過程一直進(jìn)行到葉節(jié)點(diǎn)，實體被判為屬于該葉節(jié)點(diǎn)所標(biāo)記的類別。決策樹方法有ID3、ID4和ID5等。,64,,這棵決策樹對銷售記錄進(jìn)行分類，指出一個電子產(chǎn)品消費(fèi)者是否會購買一臺計算機(jī)“buys_computer”。每個內(nèi)部結(jié)點(diǎn)（方形框）代表對某個屬性的一次檢測

38、。每個葉結(jié)點(diǎn)（橢圓框）代表一個類： buys_computers=yes 或者 buys_computers=no 在這個例子中，樣本向量為： （age, student, credit_rating; buys_computers） 被決策數(shù)據(jù)的格式為:（age, student, credit_rating） 輸入新的被決策的記錄，可以預(yù)測該記錄隸屬于哪個類。,65,第5章 數(shù)

39、據(jù)挖掘中常用算法,5.3.1 信息論的基本原理1.信息論原理信息論是為解決信息傳遞（通信）過程問題而建立的理論，也稱為統(tǒng)計通信理論。一個傳遞信息的系統(tǒng)是由信源、信宿、信道組成。信息論把通信過程看作是在隨機(jī)干擾的環(huán)境中傳遞信息的過程。在這個通信模型中，信息源和干擾（噪聲）都被理解為某種隨機(jī)過程或隨機(jī)序列。先驗不確定性——在進(jìn)行實際通信以前，信宿對于信源狀態(tài)具有不確定性。后驗不確定性——通信結(jié)束之后，信宿仍然具有一定程度的不確定性

40、?！昂篁灢淮_定性=先驗不確定性”——信宿根本沒有收到信息?！昂篁灢淮_定性=0”——信宿收到了全部信息。,66,第5章 數(shù)據(jù)挖掘中常用算法,2.互信息的計算（1）定義設(shè)S為訓(xùn)練集，訓(xùn)練集中每個訓(xùn)練樣本有n個特征（屬性），表示為（A1,A2… An），|S|表示例子總數(shù)；S中有U1、U2兩類，|Ui|表示Ui類例子總數(shù)；特征 Ak處有m個取值，分別為（V1,V2…Vm）。（2）概率出現(xiàn)概率： Ui類出現(xiàn)概率 P(Ui)= |

41、Ui| / |S|條件概率： Ui類中在特征Ak處，取值Vj的例子集合Vij的條件概率 P(Vj | Ui)= |Vij| / |Ui|子集概率：在特征Ak處，取值Vj的例子集合的概率為 P(Vj)= |Vj| / |S|子集條件概率：在特征Ak處取值Vj的例子，屬于Ui類的例子集合Uii的概率為 P(Ui|Vj)= |Uij| /|Vj|,67,第5章 數(shù)據(jù)挖掘中常用算法,（3）信息熵 信源數(shù)學(xué)模型[U,P]：消息（符號）及其

42、發(fā)生概率。自信息I(Ui)：在收到Ui之前，收信者對信源發(fā)出Ui的不確定性定義為信息符號Ui的自信息量I(Ui)。它反映消息發(fā)生后所含有的信息量或者消息發(fā)生前的不確定性（隨機(jī)性）。信息熵H(U)：信源輸出前的不確定性（平均）。（4）互信息 后驗熵H(U/Vj)條件熵H(H/V)平均互信息：I(U,V),68,第5章 數(shù)據(jù)挖掘中常用算法,5.3.2 ID3算法1.ID3基本思想在一實體世界中，每個實體用多個特征來描述。每個

43、特征限于在一個離散集中取互斥的值。每個實體在世界中屬于不同的類別，為簡單起見，假定有兩個類別，分別為P和N。在這兩個類別的歸納任務(wù)中，P類和N類的實體分別稱為概念的正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。例P108：氣候訓(xùn)練集,69,第5章 數(shù)據(jù)挖掘中常用算法,2.ID3算法ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（Induction of Decision Tree）。早期的ID算法只能就兩

44、類數(shù)據(jù)進(jìn)行挖掘（如正類和反類）；經(jīng)過改進(jìn)后，現(xiàn)在ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對具有相同屬性的數(shù)據(jù)，其對應(yīng)的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。,70,第5章 數(shù)據(jù)挖掘中常用算法,（1）算法的基本思想 step 1．任意選取一個屬性作為決策樹的根結(jié)點(diǎn)，然后就這個屬性所有的取值創(chuàng)建樹的分支；step 2．用這棵樹來對訓(xùn)練數(shù)據(jù)集進(jìn)行分類，如果一個葉結(jié)點(diǎn)的所有實例都屬于同一

45、類，則以該類為標(biāo)記標(biāo)識此葉結(jié)點(diǎn)；如果所有的葉結(jié)點(diǎn)都有類標(biāo)記，則算法終止；step 3．否則，選取一個從該結(jié)點(diǎn)到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識該結(jié)點(diǎn)，然后就這個屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step 2；這個算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)

46、式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高互信息——即最高信息增量（information gain）——的屬性，也就是說，生成最少分支決策樹的那個屬性。,71,第5章 數(shù)據(jù)挖掘中常用算法,（2）建樹算法 對當(dāng)前例子集合，計算各特征的互信息；選擇互信息最大的特征Ak；把在Ak處取值相同的例子歸于同一子集， Ak取幾個值就得幾個子集；對既含正例又含反例的子集，遞歸調(diào)用建樹算法；若子集僅含正例或反例，對應(yīng)分枝上標(biāo)P或N，返

47、回調(diào)用處。,72,實例計算,信息熵計算信息概率P(U1)、P(U2)信息熵H(U)條件熵計算假設(shè)A1=天氣，V1=晴，V2=多云，V3=雨P(guān)(V1)、 P(V2)、 P(V3)P(U1/V1),P(U2/V1),P(U1/V2),P(U2/V2),P(U1/V3),P(U2/V3)條件熵H(U/V)平均互信息計算I(U,V),73,第5章 數(shù)據(jù)挖掘中常用算法,5.3.3 樹剪枝 剪枝常常利用統(tǒng)計學(xué)方法，去掉最不可

48、靠、可能是噪音的一些枝條，同時它也能使樹得到簡化而變得更容易理解。 兩種剪枝策略：先剪枝（預(yù)剪枝）——限制決策樹的過度生長；后剪枝：待決策樹生成后再進(jìn)行剪枝。1.先剪枝事先限定最大生長高度，使決策樹不能過度生長。 采用x2檢驗、信息增益等度量，評估每次節(jié)點(diǎn)分裂對系統(tǒng)性能的增量，如果節(jié)點(diǎn)分裂的增量小于預(yù)先給定的閥值，則不對該節(jié)點(diǎn)進(jìn)行擴(kuò)展。,74,第5章 數(shù)據(jù)挖掘中常用算法,2.后剪枝允許決策樹過度生長，然后根據(jù)一定的規(guī)則，剪

49、去那些不具有一般代表性的節(jié)點(diǎn)和分枝。可以采用自上而下的順序或自下而上的順序進(jìn)行剪枝。 代價復(fù)雜性剪枝算法：對于樹中每個非樹葉節(jié)點(diǎn)計算該子樹被剪枝會出現(xiàn)的期望錯誤率，如果剪去該節(jié)點(diǎn)導(dǎo)致較高的期望錯誤率，則保留該子樹；否則剪去該子樹。 可以將先剪枝和后剪枝算法交叉使用。,75,第5章 數(shù)據(jù)挖掘中常用算法,5.3.4 由決策樹提取分類規(guī)則 獲得簡單規(guī)則從根到葉的每一條路徑都可以是一條規(guī)則。規(guī)則采用IF-THEN的形式表示。,76,補(bǔ)充

50、內(nèi)容：貝葉斯分類方法,貝葉斯分類是一個統(tǒng)計學(xué)分類方法。它們能夠預(yù)測一個要進(jìn)行分類判斷的數(shù)據(jù)對象屬于某個類別的概率。貝葉斯分類是基于貝葉斯定理（以下將會介紹）而構(gòu)造出來的?；矩惾~斯分類（Naïve Bayesian classify，又稱為樸素貝葉斯分類）假設(shè)一個指定類別中各屬性的取值是相互獨(dú)立的。這一假設(shè)也被稱為：類別條件獨(dú)立，它可以幫助有效減少在構(gòu)造貝葉斯分類時所需要進(jìn)行的計算量。 對分類方法進(jìn)行比較的有關(guān)研究

51、結(jié)果表明：基本貝葉斯分類在分類性能上與決策樹和神經(jīng)網(wǎng)絡(luò)相媲美。在處理大型數(shù)據(jù)庫時，貝葉斯分類法已表現(xiàn)出較高的分類準(zhǔn)確性和運(yùn)算性能。,77,背景知識：貝葉斯定理,設(shè)X為一個類別未知的數(shù)據(jù)樣本，設(shè)H為某個假設(shè)，比如數(shù)據(jù)樣本X屬于一個特定的類別C。對于分類問題，我們的目標(biāo)是確定P(H|X)——給定觀察數(shù)據(jù)樣本X，假設(shè)H成立的概率大小。P(H|X)是后驗概率（事后概率），即在條件X下的，H成立的概率。例如：假設(shè)數(shù)據(jù)樣本是水果，描述水果的屬性

52、有顏色和形狀。假定X表示紅色和圓狀，H表示假定X是蘋果的假設(shè)，因此P(H/X)就表示在已知水果X是紅色和圓狀時，樣品X為蘋果的概率大小。相反，P(H)為先驗概率（事前概率）在上述例子中， P(H)就表示對于任意給定的數(shù)據(jù)樣品為蘋果的概率，而無論它是看上去顏色和形狀如何。P(H|X)是建立更多信息基礎(chǔ)之上的；而P(H)則與X無關(guān)。類似的P(X|H)是在條件H下，X成立的后驗概率。即若已知H是蘋果，那X是紅色和圓狀的概率可表示

53、為P(X|H) 。P(X)是X的先驗概率，即由水果集合中取出一個樣品是紅的和園的的概率。貝葉斯定理描述了如何根據(jù)P(X)、P(H)和P(X|H)的概率值計算獲得的P(H|X)：其中，P(X)、P(H)和P(X|H)的概率值可以從（供學(xué)習(xí)使用的）訓(xùn)練數(shù)據(jù)集合中得到。,78,基本貝葉斯分類方法（步驟）,79,,,80,貝葉斯分類的效率如何？,從理論上講與其它分類方法相比，貝葉斯分類具有最小的錯誤率。但實踐上并非總是如此。這

54、是由于其所依據(jù)的類別獨(dú)立性假設(shè)的不確定性，以及缺乏某些概率數(shù)據(jù)造成的。但各種研究結(jié)果表明：與決策樹和神經(jīng)網(wǎng)絡(luò)分類器相比，貝葉斯分類器在某些情況下可以與之媲美，甚至具有更好的分類效果。貝葉斯分類的另一個用途就是它可為那些沒有利用貝葉斯定理的分類方法提供了理論依據(jù)。例如在某些特定假設(shè)情況下，許多神經(jīng)網(wǎng)絡(luò)和曲線擬合算法的輸出都同貝葉斯分類一樣，使得事后概率取最大。,81,,,假設(shè),82,,83,,已知求：數(shù)據(jù)樣品 X=

55、(outlook=sunny,Temp=mild,Humid=high,Wind=weak)PlayTennis?,84,貝葉斯信念網(wǎng)絡(luò),基本貝葉斯分類是基于各類別相互獨(dú)立這一假設(shè)來進(jìn)行分類計算的，也就是要求若給定一個數(shù)據(jù)樣本類別，其樣本屬性的取值應(yīng)是相互獨(dú)立的。這一假設(shè)簡化了分類計算復(fù)雜性。若這一假設(shè)成立，則與其它分類方法相比，基本貝葉斯分類是最準(zhǔn)確的；但實際上變量間的相互依賴情況是較為常見的。貝葉斯信念網(wǎng)絡(luò)就是用于描述這種相互

56、關(guān)聯(lián)的概率分布（聯(lián)合條件概率分布）。該網(wǎng)絡(luò)能夠描述各屬性子集之間有條件的相互獨(dú)立。它提供了一個圖形模型來描述其中的因果關(guān)系，而學(xué)習(xí)也正是基于這一模型進(jìn)行的。這一圖形模型就稱為貝葉斯網(wǎng)絡(luò)、貝葉斯信念網(wǎng)絡(luò)（或簡稱為信念網(wǎng)絡(luò)）。,85,信念網(wǎng)絡(luò)組成,1.有向無環(huán)圖其中的每一個結(jié)點(diǎn)代表一個隨機(jī)變量；每一條?。▋蓚€結(jié)點(diǎn)間連線）代表一個概率依賴。若一條弧從結(jié)點(diǎn)Y到結(jié)點(diǎn)Z，那么Y就是Z的一個父結(jié)點(diǎn)，Z就是Y的一個子結(jié)點(diǎn)。給定父結(jié)點(diǎn)，每個變量有條件

57、地獨(dú)立于圖中非子結(jié)點(diǎn)。變量既可取離散值，也可取連續(xù)值。它們既可對應(yīng)數(shù)據(jù)集中實際的變量，也可對應(yīng)數(shù)據(jù)集中的“隱含變量”，以構(gòu)成一個關(guān)系。,86,,下圖所示就是一個簡單的信念網(wǎng)絡(luò)。它表示一個人患肺癌與他家庭的肺癌史有關(guān)；也與該人是否吸煙有關(guān)。但是與肺氣腫無關(guān)。,87,信念網(wǎng)絡(luò)組成,2.包含所有變量的條件概率表（Conditional Probability Table, CPT）對于一個變量Z，CPT定義了一個條件分布P(Z|pare

58、nt(Z))；其中parent(Z)表示Z的父結(jié)點(diǎn)。下表是LungCancer的一個CPT表。它描述了對于其父結(jié)點(diǎn)每一種組合，LungCancer取沒個值的條件概率。,88,,信念網(wǎng)絡(luò)中的內(nèi)部結(jié)點(diǎn)可以被選為輸出結(jié)點(diǎn)，用以代表類別屬性。網(wǎng)絡(luò)中可以有多個輸出結(jié)點(diǎn)。學(xué)習(xí)推理算法可以用于網(wǎng)絡(luò)。其分類過程不是返回一個類別標(biāo)記，而是返回一個關(guān)于類別屬性的概率分布，即對每個類別的預(yù)測概率。,89,貝葉斯信念網(wǎng)絡(luò)的學(xué)習(xí),在一個貝葉斯信念網(wǎng)絡(luò)的學(xué)

59、習(xí)或訓(xùn)練過程中，其網(wǎng)絡(luò)結(jié)構(gòu)必須首先事先確定或從數(shù)據(jù)中推出。網(wǎng)絡(luò)所涉及變量必須是可觀察或隱含在訓(xùn)練數(shù)據(jù)集合中。若隱含在數(shù)據(jù)中，就稱為數(shù)據(jù)遺失或不完全。若網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)確定并且所涉及變量均為可觀察的，那么就可以進(jìn)行網(wǎng)絡(luò)學(xué)習(xí)了，這其中包括：計算CPT表的入口，與基本貝葉斯分類方法中的概率計算過程類似。,90,,91,,92,,93,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.5 偏差型知識4.5.1 偏差型知識的概念偏差型知識：對差異和極端特例

60、的描述，揭示事物偏離常規(guī)的異?，F(xiàn)象，如標(biāo)準(zhǔn)類外的特例，數(shù)據(jù)聚類外的離群值等。 偏差即異常，在數(shù)據(jù)挖掘中也有稱其為“孤立點(diǎn)”之說。孤立點(diǎn)探測和分析是數(shù)據(jù)挖掘中的一個很特殊的任務(wù)，被稱為孤立點(diǎn)挖掘。,94,第4章 數(shù)據(jù)挖掘發(fā)現(xiàn)知識的類型,4.5.2 偏差型知識的發(fā)現(xiàn)方法基本方法是，尋找觀測結(jié)果與參照值之間有意義的差別。最常用的偏差型知識的發(fā)現(xiàn)方法是異常探測。異?！炔粚儆诰垲?，也不屬于背景噪聲的點(diǎn)。它們的行為與正常行為有很大不同。