數(shù)據(jù)挖掘應(yīng)用- 浙江大學計算機科學與技術(shù)學院

浙江大學研究生《人工智能引論》課件

廠第12講數(shù)據(jù)挖掘應(yīng)用

a]^r12ApplicationsofDataMining

徐從富(CongfuXu),PhD,Asso.Professor

浙江大學人工智能研究所

2005年5月17日第一稿

2006年10月30日第二次修改

目錄

一.關(guān)聯(lián)規(guī)則挖掘

二.聚類分析

三.分類與預(yù)測

四.Web挖掘

五.流數(shù)據(jù)挖掘

六.隱私保護數(shù)據(jù)挖掘

一.關(guān)聯(lián)規(guī)則挖掘

1.關(guān)聯(lián)規(guī)則挖掘簡介

2,關(guān)聯(lián)規(guī)則基本模型

3,關(guān)聯(lián)規(guī)則價值衡量與發(fā)展

1.關(guān)聯(lián)規(guī)則簡介

■關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依

存性和關(guān)聯(lián)性。如果兩個或者多個事物之間存在

一定的關(guān)聯(lián)關(guān)系，那么，其中一個事物就能夠通

過其他事物預(yù)測到。

■典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)

(MarketBasket)進行分析。通過發(fā)現(xiàn)顧客放入

貨籃中的不同商品之間的關(guān)系來分析顧客的購買

習慣。

什么是關(guān)聯(lián)規(guī)則挖掘

■關(guān)聯(lián)規(guī)則挖掘

□首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD會議上提出

□在事務(wù)、關(guān)系數(shù)據(jù)庫中的項集和對象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因

果結(jié)構(gòu)

□頻繁模式:數(shù)據(jù)庫中頻繁出現(xiàn)的項集

■目的：發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律

□超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？—啤酒和尿布

□在買了一臺PC之后下一步會購買？

□哪種DNA對這種藥物敏感？

□我們?nèi)绾巫詣訉eb文檔進行分類？

頻繁模式挖掘的重要性

■許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)

□關(guān)聯(lián)、相關(guān)性、因果性

□序列模式、空間模式、時間模式、多維

□關(guān)聯(lián)分類、聚類分析

■更加廣泛的用處

□購物籃分析、交叉銷售、直銷

點擊流分析、DNA序列分析等等

2.關(guān)聯(lián)規(guī)則基本模型

①關(guān)聯(lián)規(guī)則基本模型

②Apriori算法

①關(guān)聯(lián)規(guī)則基本模型

■IBM公司Almaden研究中心的R.Agrawal首先

提出關(guān)聯(lián)規(guī)則模型，并給出求解算法AIS。

隨后又出現(xiàn)了SETM和Apriori等算法。其中,

Apriori是關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法。

□給定一組事務(wù)

產(chǎn)生所有的關(guān)聯(lián)規(guī)則

□滿足最小支持度和最小可信度

關(guān)聯(lián)規(guī)則基本模型（續(xù)）

■設(shè)/=宿32,…，，m｝為所有項目的集合，。為事務(wù)數(shù)

據(jù)庫，事務(wù)T是一個項目子集（T』）。每一個事

務(wù)具有唯一的事務(wù)標識770。設(shè)J是一個由項目構(gòu)

成的集合，稱為項集。事務(wù)T包含項集4當且僅

當4=7。如果項集^中包含左個項目，則稱其為左項

集。項集4在事務(wù)數(shù)據(jù)庫。中出現(xiàn)的次數(shù)占。中總

事務(wù)的百分比叫做項集的支持度。如果項集的支

持度超過用戶給定的最小支持度閾值，就稱該項

集是頻繁項集（或大項集）。

關(guān)聯(lián)規(guī)則基本模型(續(xù))

■關(guān)聯(lián)規(guī)則是形如通丫的邏輯蘊含式，其中

Y0,且XnlMZS。如果事務(wù)數(shù)據(jù)庫。中有s%的事

務(wù)包含xuy,則稱關(guān)聯(lián)規(guī)則gy的支持度為s%,

實際上，支持度是一個概率值。若項集x的支持度

記為support(X),規(guī)則的信任度為sappo"(X<JY)/

support(X)o這是一個條件概率尸(丫[X)。也就是：

support(Ji=^>y)=P(XuY)

confidence尸(K|X)

規(guī)則度量：支持度與可信度

查找所有的規(guī)則x&z

具有最小支持度和可信度

□支持度，S,一次交易中包含

｛X、Y、Z｝的可能性

口可信度，。，包含｛X、Y｝的交

易中也包含Z的條件概率

交易ID購買的商品設(shè)最小支持度為50%,最小可

2000A,B,C信度為50%,則可得到

1000A,CZnC(50%,66.6%)

4000A,D

A(50%,100%)

5000B,E,F

關(guān)聯(lián)規(guī)則基本模型（續(xù)）

■關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用

戶給定閾值的規(guī)則。

■發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個步驟：

□找出所有頻繁項集。

□由頻繁項集生成滿足最小信任度閾值的規(guī)則。

(％。01％00r個。

I(％e.99C%OB3_個r

:%ocH、OD~ulluc%ocuModdns~u-lu37

LJO

JL1LCO寸

Q<

Q<oN(

Q-

oC<oX

thguobsmetIdi-noitcasnarT

Transaction-idItemsboughtMin.support50%

10A,B,CMin.confidence50%

20A,CFrequentpatternSupport

30A,D

{A}75%

40B,E,F

>{B}50%

{C}50%

ForruleZ=>C:{A,C}50%

support=support({/\}o{C})=50%

confidence=support({/A}o{C})/support({/\})=

66.6%

②Apriori算法的步驟

■Apriori算法命名源于算法使用了頻繁項集性質(zhì)的先

驗(Prior)知識。

■Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個步驟：

□通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持

度不低于用戶設(shè)定的閾值的項集；

□利用頻繁項集構(gòu)造出滿足用戶最小信任度的規(guī)則。

■挖掘或識別出所有頻繁項集是該算法的核心，占整

個計算量的大部分。

頻繁項集

■為了避免計算所有項集的支持度（實際上頻

繁項集只占很少一部分），Apriori算法引入

潛在頻繁項集的概念。若潛在頻繁k項集的

集合記為CQ頻繁k項集的集合記為4,m

個項目構(gòu)成的k項集的集合為c%則三者之

間滿足關(guān)系47金=。上構(gòu)成潛在頻繁項集

所遵循的原則是“頻繁項集的子集必為頻繁

項集”。

關(guān)聯(lián)規(guī)則的性質(zhì):

■性質(zhì)6.1頻繁項集的子集必為頻繁項集。

■性質(zhì)6.2非頻繁項集的超集一定是非頻繁的。

■Apriori算法運用性質(zhì)6.1,通過已知的頻繁項集構(gòu)成

長度更大的項集，并修其稱為潛在頻繁項集。潛在

頻繁左項集的集合金是指由有可能成為頻繁左項集的

項集組成的集合。以后只需計算潛在頻繁項集的支

持度，而不必計算所有不同項集的支持度，因此在

一定程度上減少了計算量。

Apriori算法

(1)1二{頻繁1項集};

(2)for(k=2；4_iW0;k++)dobegin

(3)Ck=apriori_gen(Lk_1);〃新的潛在頻繁項集

(4)foralltransactionsteDdobegin

(5)Q=subset(Ck,f)；〃t中包含的潛在頻繁項集

(6)forallcandidatesceCtdo

(7)c.count++;

(8)end;

(9)Lk={cGCk|c.count>minsup}

(10)end;

(11)Answer=U4

實例

Itmtsup

DatabaseTDB1111ODIsup

{A}2J

{A}2

Items{B}3

{B}3

10A,C,D{C}3

1stscan{C}3

20B,C,E{D}1

{E}3

30A,B,C,E{E}3

40B,E

SU。

1

L?{A,B}2ndscan

{A,C}2{A,B}

{A,C}2

1{A,C}

{B,C}2{A.E}

{B,C}2{A,E}

{B,E}3

{B,E}3{B,C}

{C,E}2

{C,E}2{B,E}

{GE}

3rdscansu

{B,C,E){B,C,E)

VisualizationofAssociationRules:PaneGraph

備DBMinerEnterprise-[#8-Associator]

岫FileMiningAssociatorViewWindowOptionsHelp一依IX|

IH牌Im|闋A|G|?I

畫5|由|直5|7|J

VisualizationofAssociationRules:RuleGraph

ADBMinerEnterprise-[#1-Associ&tor]I-佰

岫FH?MiningAssociatoryiewWindowOptionsHelp

屈牌Inil%|s|q|?|

直lol田I回Al7畫

ActivatedNeutralDisabled

Support

^

2,3

王

ForHelp,pressF1NUM

提高Apriori算法的方法

■Hash-baseditemsetcounting（散歹1I項集計數(shù)）

■Transactionreduction（事務(wù)壓縮）

■Partitioning（劃分）

■Sampling（采樣）

關(guān)聯(lián)規(guī)則挖掘算法

■Agrawal等人提出的AIS,Apriori和AprioriTid

■Cumulate和Stratify,Houstsma等人提出的SETM

■Park等人提出的DHP

■Savasere等人的PARTITION

■Han等人提出的不生成候選集直接生成頻繁模式

FPGrowth

■其中最有效和有影響的算法為Apriori,DHP和

PARTITION,FPGrowtho

■用Frequent?Patteintree(FP-tree)結(jié)構(gòu)壓縮

數(shù)據(jù)庫，

口高度濃縮，同時對頻繁集的挖掘又完備的

□避免代價較高的數(shù)據(jù)庫掃描

■開發(fā)一種高效的基于FP-tree的頻繁集挖掘

算法

口采用分而治之的方法學：分解數(shù)據(jù)挖掘任務(wù)為

小任務(wù)

避免生成關(guān)聯(lián)規(guī)則：只使用部分數(shù)據(jù)庫！

用交易數(shù)據(jù)庫建立FP?tree

TIDItemsbought(ordered)介equentitems

100{f,a,c,d,g9i,m9p}優(yōu)c,a,m,p}

200{a,b,c,f,I,m,o}%?’am}最小支持度=0.5

300{仇/九j,。}

400{b,c,A,s,p}{c,b,p}

500{a,f,c,e,I,p,m,n}優(yōu)c,a,m,p}

步驟：

1.掃描數(shù)據(jù)庫一次，得到頻繁

1■項集

2.把項按支持度遞減排序

3.再一次掃描數(shù)據(jù)庫，建立FP-

tree

FP-tree結(jié)構(gòu)的好處

■完備：

不會打破交易中的任何模式

□包含了頻繁模式挖掘所需的全部信息

■緊密

□去除不相關(guān)信息一不包含非頻繁項

口支持度降序排列：支持度高的項在FP-tree中共享

的機會也高

□決不會比原數(shù)據(jù)庫大（如果不計算樹節(jié)點的額外

開銷）

□例子：對于Connect-4數(shù)據(jù)庫，壓縮率超過100

用FP?tree挖掘頻繁集

■基本思想（分而治之）

□用FP-tree地歸增長頻繁集

■方法

口對每個項，生成它的條件模式庫，然后是它的

條件FP-tree

□對每個新生成的條件FP-tree,重復(fù)這個步驟

□直到結(jié)果FP-tree為空，或只含維一的一個路徑

（此路徑的每個子路徑對應(yīng)的項集都是頻繁集）

挖掘FP?tree的主要步驟

1）為FP-tree中的每個節(jié)點生成條件模式庫

2）用條件模式庫構(gòu)造對應(yīng)的條件FP-tree

3）遞歸構(gòu)造條件FP-trees同時增長其包含

的頻繁集

■如果條件FP-tree只包含一個路徑，則直接生

成所包含的頻繁集。

步驟1:從FP-tree到條件模式庫

■從FP-tree的頭表開始

■按照每個頻繁項的連接遍歷FP-tree

■列出能夠到達此項的所有前綴路徑，得到條件

模式庫

頭表{)條件模式庫

itemcond.patternbase

Itemfrequencyhead

f4--cf：3

c4—afc:3

a3

b3—bfca:l,f:l,c:l

m3mfca:2,fcab:l

P3\

pfcam:2,cb:l

p:2^m:l

FP?tree支持條件模式庫構(gòu)造的屬性

■節(jié)點褪接

□任何包含a,.，的可能頻繁集，都可以從FP-tree頭

表中的沿著a,的節(jié)點鏈接得到

■前綴路徑

口要計算路徑戶中包含節(jié)點a,?的頻繁集，只要考

察到達a,?的路徑前綴即可，且其支持度等于節(jié)

點a,的支持度.

步驟2:建立條件FP-tree

■對每個模式庫

□計算庫中每個項的支持度

□用模式庫中的頻繁項建立FP-tree

()tn-條件模式庫:

頭表fca:2ffcab:l

Item血夕〃e1①head

,一亍C：1

4Allfrequentpatterns

(}concerningm

c4

a3m,

/?3今

b3a:3fm,cm,am,

m3fem,fam,cam,

m:2、b:lc:3

P3fcam

m:la:3

m-conditionalFP-tree

通過建立條件模式庫得到頻繁集

項條件模式庫條件FP-tree

P{(fcam:2),(cb:1)}{(c：3)}|p

m{(fca:2),(fcab:1)}{(f:3,c:3,a:3)}|m

b{(fca:1),(f:1),(c:1)}Empty

a{(fc：3)}{(f：3,c:3))|a

c{(f：3)}{(f：3)}|c

fEmptyEmpty

第3步：遞歸挖掘條件FP?tree

{}

I

儲

(}i

I'Im〃的條件模式庫：(fc:3)c:3

f：3

Iam-條年FP-tree

c:3{}

II

a:3f：3

條鄉(xiāng)FP-tree''cm〃的條件模式:(f:3)

cm-條殍FP-tree

()

I

儲

''cam〃條件模式庫：(f:3)

ca/o-條件FP-tree

3.關(guān)聯(lián)規(guī)則價值衡量與發(fā)展

①關(guān)聯(lián)規(guī)則價值衡量

②關(guān)聯(lián)規(guī)則最新進展

①規(guī)則價值衡量

■對關(guān)聯(lián)規(guī)則的評價與價值衡量涉及兩個層

面：

口系統(tǒng)客觀的層面

用戶主觀的層面

系統(tǒng)客觀層

■使用“支持度和信任度”框架可能會產(chǎn)生

一些不正確的規(guī)則。只憑支持度和信任度

閾值未必總能找出符合實際的規(guī)則。

用戶主觀層

■只有用戶才能決定規(guī)則的有效性、可行性。所以,

應(yīng)該將用戶的需求和系統(tǒng)更加緊密地結(jié)合起來。

■可以采用基于約束(Consraint-based)的數(shù)據(jù)挖

掘方法。具體約束的內(nèi)容有：數(shù)據(jù)約束、限定數(shù)

據(jù)挖掘的維和層次、規(guī)則約束。

■如果把某些約束條件與算法緊密結(jié)合，既能提高

數(shù)據(jù)挖掘效率，又能明確數(shù)據(jù)挖掘的目標。

②關(guān)聯(lián)規(guī)則新進展

■在基于一維布爾型關(guān)聯(lián)規(guī)則的算法研究中先后出

現(xiàn)了AIS、SETM等數(shù)據(jù)挖掘算法。

■R.Agrawal等人提出的Apriori是經(jīng)典算法。隨后的

關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法大多數(shù)建立在Apriori算法基礎(chǔ)

上，或進行改造，或衍生變種。比如AprioriTid和

AprioriHybrid算法。

■Lin等人提出解決規(guī)則挖掘算法中的數(shù)據(jù)傾斜問題,

從而使算法具有較好的均衡性。Park等人提出把

哈希表結(jié)構(gòu)用于關(guān)聯(lián)規(guī)則挖掘。

關(guān)聯(lián)規(guī)則新進展（續(xù)）

■數(shù)據(jù)挖掘工作是在海量數(shù)據(jù)庫上進行的，數(shù)據(jù)庫的

規(guī)模對規(guī)則的挖掘時間有很大影響。

■Agrawal首先提出事務(wù)縮減技術(shù)，Han和Park等人也

分別在減小數(shù)據(jù)規(guī)模上做了一些工作。

■抽樣的方法是由Toivonen提出的。

■Brin等人采用動態(tài)項集計數(shù)方法求解頻繁項集。

■Aggarwal提出用圖論和格的理論求解頻繁項集的方

法。Prutax算法就是用格遍歷的辦法求解頻繁項集。

關(guān)聯(lián)規(guī)則新進展（續(xù)）

■關(guān)聯(lián)規(guī)則模型有很多擴展，如順序模型挖掘，在順

序時間段上進行挖掘等。

■還有挖掘空間關(guān)聯(lián)規(guī)則，挖掘周期性關(guān)聯(lián)規(guī)則，挖

掘負關(guān)聯(lián)規(guī)則，挖掘交易內(nèi)部關(guān)聯(lián)規(guī)則等。

■Guralnik提出順序時間段問題的形式描述語言，以

便描述用戶感興趣的時間段，并且構(gòu)建了有效的數(shù)

據(jù)結(jié)病SP樹（順序模式樹）和白底高上的數(shù)據(jù)挖掘

算法。

■最大模式挖掘是Bayardo等人提出來的。

關(guān)聯(lián)規(guī)則新進展(續(xù))

■隨后人們開始探討頻率接近項集。Pei給出了一種有

效的數(shù)據(jù)挖掘算法。

■B.Ozden等人的周期性關(guān)聯(lián)規(guī)則是針對具有時間屬

性的事務(wù)數(shù)據(jù)庫，發(fā)現(xiàn)在規(guī)律性的時間間隔中滿足

最小支特度和信任度的規(guī)則。

■貝爾實驗室的S.Ramaswamy等人進一步發(fā)展了周期

性關(guān)聯(lián)規(guī)則，提出挖掘符合日歷的關(guān)聯(lián)規(guī)則、

(CalendricAssociationRules)算法，用以進行市場

貨籃分析。

■Fang等人給出冰山查詢數(shù)據(jù)挖掘算法。

關(guān)聯(lián)規(guī)則新進展（續(xù)）

■T.Hannu等人把負邊界引入規(guī)則發(fā)現(xiàn)算法中，每次挖

掘不僅保存頻繁項集，而且同時保存負邊界，達到

下次挖掘時減少掃描次數(shù)的目的。

■Srikant等人通過研究關(guān)聯(lián)規(guī)則的上下文，提出規(guī)則

興趣度尺度用以剔除冗余規(guī)則。

■Zakia還用項集聚類技術(shù)求解最大的近似潛在頻繁項

集，然后用格遷移思想生成每個聚類中的頻繁項集。

■CAR,也叫分類關(guān)聯(lián)規(guī)則，是Lin等人提出的一種新

的分類方法，是分類技術(shù)與關(guān)聯(lián)規(guī)則思想相結(jié)合的

產(chǎn)物，并給出解*方案箱算法。

關(guān)聯(lián)規(guī)則新進展（續(xù)）

■Cheung等人提出關(guān)聯(lián)規(guī)則的增量算法。

■Thomas等人把負邊界的概念引入其中）進一

步發(fā)展了增量算法。如，基于Apriori框架的

并行和分布式數(shù)據(jù)挖掘算法。

■Oates等人將MSDD算法改造為分布式算法。

還有其他的并行算法，如利用垂直數(shù)據(jù)庫探

求項集聚類等。

二.聚類分析

I.聚類分析簡介

II.聚類分析中的數(shù)據(jù)類型

III.劃分方法

IV.層次方法

I.聚類(Clustering)分析簡介

■聚類(Clustering)是對物理的或抽象的對

象集合分組的過程。

■聚類生成的組稱為簇(Cluster),簇是數(shù)據(jù)

對象的集合。簇內(nèi)部的任意兩個對象之間

具有較高的相似度，而屬于不同簇的兩個

對象間具有較高的相異度。相異度可以根

據(jù)描述對象的屬性值計算，對象間的距離

是最常采用的度量指標。

聚類分析簡介（續(xù)）

■聚類分析是數(shù)據(jù)分析中的一種重要技術(shù)，

它的應(yīng)用極為廣泛。許多領(lǐng)域中都會涉及

聚類分析方法的應(yīng)用與研究工作，如數(shù)據(jù)

挖掘、統(tǒng)計學、機器學習、模式識別、生

物學、空間數(shù)據(jù)庫技術(shù)、電子商務(wù)等。

聚類分析簡介（續(xù)）

■從統(tǒng)計學的觀點看，聚類分析是通過數(shù)據(jù)

建模簡化數(shù)據(jù)的一種方法。傳統(tǒng)的統(tǒng)計聚

類分析方法包括系統(tǒng)聚類法、分解法、加

入法、動態(tài)聚類法、有序樣品聚類、有重

疊聚類和模糊聚類等。采用k-均值、k-中心

點等算法的聚類分析工具已被加入到許多

著名的統(tǒng)計分析軟件包中，如SPSS、SAS

等。

聚類分析簡介（續(xù)）

■從機器學習的角度講，簇相當于隱藏模式。

聚類是搜索簇的無監(jiān)督學習過程。與分類

不同，無監(jiān)督學習不依賴預(yù)先定義的類或

帶類標記的訓練實例，需要由聚類學習算

法自動確定標記，而分類學習的實例或數(shù)

據(jù)對象有類別標記。聚類是觀察式學習，

而不是示例式的學習。

聚類分析簡介（續(xù)）

■從實際應(yīng)用的角度看，聚類分析是數(shù)據(jù)挖掘的主

要任務(wù)之一。

■就數(shù)據(jù)挖掘功能而言，聚類能夠作為一個獨立的

工具獲得數(shù)據(jù)的分布狀況，觀察每一簇數(shù)據(jù)的特

征，集中對特定的聚簇集合作進一步地分析。

■聚類分析還可以作為其他數(shù)據(jù)挖掘任務(wù)（如分類、

關(guān)聯(lián)規(guī)則）的預(yù)處理步驟。

■數(shù)據(jù)挖掘領(lǐng)域主要研究面向大型數(shù)據(jù)庫、數(shù)據(jù)倉

庫的高效實用的聚類分才斤算法。

聚類的常規(guī)應(yīng)用

■模式識別

■空間數(shù)據(jù)分析

□在GIS中，通過聚類發(fā)現(xiàn)特征空間來建立主題索

引；

□在空間數(shù)據(jù)挖掘中，檢測并解釋空間中的簇；

■圖象處理

■經(jīng)濟學（尤其是市場研究方面）

■WWW

□文檔分類

口分析WEB日志數(shù)據(jù)來發(fā)現(xiàn)相似的訪問模式

應(yīng)用聚類分析的例子

■市場銷售：幫助市場人員發(fā)現(xiàn)客戶中的不同群體,

然后用這些知識來開展一個目標明確的市場計劃;

■土地使用：在一個陸地觀察數(shù)據(jù)庫中標識那些土地

使用相似的地區(qū)；

■保險:對購買了汽車保險的客戶,標識那些有較高

平均賠償成本的客戶；

■城市規(guī)劃：根據(jù)類型、價格、地理位置等來劃分不

同類型的住宅；

■地震研究：根據(jù)地質(zhì)斷層的特點把已觀察到的地震

中心分成不同的類；

什么是一個好的聚類方法？

■一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果一

簇，這些簇要具備以下兩個特點：

高的簇內(nèi)相似性

□低的簇間相似性

■聚類結(jié)果的好壞取決于該聚類方法采用的相似性

評估方法以及該方法的具體實現(xiàn)；

■聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還

是所有的隱含模式；

II.聚類分析中的數(shù)據(jù)類型

■聚類分析主要針對的數(shù)據(jù)類型包括區(qū)間標

度變量、二元變量、標稱變量、序數(shù)型變

量，以及由這些變量類型構(gòu)成的復(fù)合類型。

■一些基于內(nèi)存的聚類算法通常采用數(shù)據(jù)矩

陣和相異度矩陣兩種典型的數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)矩陣(DataMatrix)

■設(shè)有"個對象，可用p個變量(屬性)描述每個對

象，則"xp矩陣

'll"12,,,p

1“22???p

稱為數(shù)據(jù)矩陣。數(shù)據(jù)矩陣是對象-變量結(jié)構(gòu)的數(shù)據(jù)

表達方式。

相異度矩陣(DissimilarityMatrix)

■按“個對象兩兩間的相異度構(gòu)建〃階矩陣(因為相異度矩陣

是對稱的，只需寫出上三角或下三角即可)：

9

或2,1)0

或3,1)6/(3,2)0

d(n,2)...…0,

■其中d(/,/)表示對象/與的相異度，它是一個非負的數(shù)值。

當對象/和/越相似或“接近”時，d(/J)值越接近0;而對象

/和/越不相同或相距“越遠”時，d(/J)值越大。顯然，d(i,

j)=d(/,/),d(/,/)=0o相異度矩陣是后缸對象結(jié)構(gòu)的一種數(shù)

據(jù)表達方式。

評價聚類質(zhì)量

■差異度/相似度矩陣：相似度通常用距離函數(shù)來表

示；

■有一個單獨的質(zhì)量評估函數(shù)來評判一個簇的好壞；

■對不同類型的變量，距離函數(shù)的定義通常是不同的;

■根據(jù)實際的應(yīng)用和數(shù)據(jù)的語義，在計算距離的時候,

不同的變量有不同的權(quán)值相聯(lián)系；

■很難定義“足夠相似了”或者“足夠好了”

只能憑主觀確定;

聚類分析中的數(shù)據(jù)類型

■區(qū)間標度變量；

■二元變量；

■標稱型，序數(shù)型變量；

■混合類型變量；

對象間距離的計算

■設(shè)兩個p維向量毛=(%1,X/2,…，.p)丁和勺二(31,32,…，

為p)丁分別表示兩個對左，有多祎形式的距離度量

可以采用。

閔可夫斯基(Minkowski)距離：

□曼哈坦(Manhattan)距離：

□歐幾里得(Euclidean)距離：

□切比雪夫(Chebyshev)笈巨離：

□馬哈拉諾比斯(Mahalanobis)距離：

III.劃分方法簡介

■對于一個給定的〃個對象或元組的數(shù)據(jù)庫，采用目

標函數(shù)最小化的策略，通過迭代把數(shù)據(jù)分成k個劃

分塊，每個劃分塊為一個簇，這就是劃分方法。

■劃分方法滿足兩個條件：

(1)每個分組至少包含一個對象；

(2)每個對象必屬于且僅屬于某一個分組。

■常見的劃分方法有k-均值方法和k-中心點方法。

其他方法大都是這兩種方法的變形。

k-均值算法

■k-均值聚類算法的核心思想是通過迭代把數(shù)據(jù)對

象劃分到不同的簇中，以求目標函數(shù)最小化，從

而使生成的簇盡可能地緊湊和獨立。

□首先，隨機選取k個對象作為初始的k個簇的質(zhì)心；

□然后，將其余對象根據(jù)其與各個簇質(zhì)心的距離分配到

最近的簇；再求新形成的簇的質(zhì)心。

這個迭代重定位過程不斷重復(fù)，直到目標函數(shù)最小化

為止。

k-均值算法

■輸入期望得到的簇的數(shù)目上4個對象的數(shù)據(jù)庫。

■輸出使得平方誤差準則函數(shù)最小化的4個簇。

■方法

□選擇左個對象作為初始的簇的質(zhì)心；

□repeat

計算對象與各個簇的質(zhì)心的距離，嚼對象劃分到距離

其最近的簇；

□重新計算每個新簇的均值；

unti1簇的質(zhì)心不再變化。

K-均值算法

10

9

8

7o

6?>

5。???

4?

AssignUpdate

3the

2each

1objectscluster

0means

012345678910tomost

similar

treassign

■centerreassign

K=2

ArbitrarilychooseK

objectasinitial

clustercenterUpdate

the

cluster

means

IV.層次聚類

■層次聚類按數(shù)據(jù)分層建立簇，形成一棵以

簇為節(jié)點的樹，稱為聚類圖。

■按自底向上層次分解）則稱為凝聚的層次

聚類。

■按自頂向下層次分解,就稱為分裂的層次

聚類。

凝聚的和分裂的層次聚類

■凝聚的層次聚類采用自底向上的策略，開

始時把每個對象作為一個單獨的簇，然后

逐次對各個簇進行適當合并，直到滿足某

個終止條件。

■分裂的層次聚類采用自頂向下的策略，與

凝聚的層次聚類相反，開始時將所有對象

置于同一個簇中，然后逐次將簇分裂為更

小的簇，直到滿足某個終止條件。

凝聚的和分裂的層次聚類

凝聚的（AGENS）

層次聚類方法的優(yōu)缺點

■層次聚類方法的優(yōu)點在于可以在不同粒度水平上對數(shù)據(jù)進行

探測，而且容易實現(xiàn)相似度量或距離度量。

■單純的層次聚類算法終止條件含糊，而且執(zhí)行合并或分裂簇

的操作后不可修正，這很可能導致聚類結(jié)果質(zhì)量很低。由于

需要檢查和估算大量的對象或簇才能決定簇的合并或分裂，

所以這種方法的可擴展性較差。通常考慮把層次聚類方法與

其他方法（如迭代重定位方法）相結(jié)合來解決實際聚類問題。

■層次聚類和其他聚類方法的有效集成可以形成多階段聚類，

能夠改善聚類質(zhì)量。這類方法包括BIRCH、CURE、ROCK、

Chameleon等。

三.分類與預(yù)測

1.簡介

2.決策樹

1.簡介

①分類

②預(yù)測

①分類

■分類的目的是提出一個分類函數(shù)或分類模型（即分

類器），通過分類器將數(shù)據(jù)對象映射到某一個給定

的類別中。

■數(shù)據(jù)分類可以分為兩步進行。

第一步建立模型，用于描述給定的數(shù)據(jù)集合。通過分析

由屬不生描述的數(shù)據(jù)集合來建立反映數(shù)據(jù)集合特性的模型。

這一步也稱作有監(jiān)督的學習，導出模型是基于訓練數(shù)據(jù)

集的，訓練數(shù)據(jù)集是已知類標記的數(shù)據(jù)對象。

第二步使用模型對數(shù)據(jù)對象進行分類。首先應(yīng)該評估模

型的分類準確度，如果模型準確度可以接受，就可以用

它乘對未知類標記的對象進行分類。

訓練集與測試集

■訓練集：數(shù)據(jù)庫中為建立模型而被分析的

數(shù)據(jù)元組形成訓練集。

■訓練集中的單個元組稱為訓練樣本,每個訓

練樣本有一個類別標記。一個具體樣本的

形式可為：（vl,v2,??.，vn;c）;其中

vi表示屬性值,c表示類別。

■測試集：用于評估分類模型的準確率。

分類的兩個階段

分類算法，

訓練數(shù)據(jù)，

a.模型訓練階段

姓名。年齡。收入e信用等級，

訓練集好<=30。低，中尸

<=30。除:高，

鏟31.VW.*40+'高，高a

去一>40，中中「

ef>40^中.：.中。

高~

31,.SA.A*40尹

b.使用模型

分類階段

評估準確率（測試集

對類標號未知的新標識a信用等級“

既>40*中Q

數(shù)據(jù)分類hP<=30^低」中丫

531W.V.*如2高J高，，

分類模型的構(gòu)造方法

機器學習方法：

決策樹法知識表示是決策樹

規(guī)則歸納知識表示是產(chǎn)生式規(guī)則

神經(jīng)網(wǎng)絡(luò)方法：

BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型

粗糙集(roughset)知識表示是產(chǎn)生式規(guī)則

②預(yù)測

■預(yù)測的目的是從歷史數(shù)據(jù)記錄中自動推導

出對給定數(shù)據(jù)的推廣描述，從而能夠?qū)κ?/p>

先未知的數(shù)據(jù)進行預(yù)測。

■分類和回歸是兩類主要的預(yù)測問題。分類

是預(yù)測離散的值,回歸是預(yù)測連續(xù)值。

■用預(yù)測法預(yù)測類標號為分類

■用預(yù)測法預(yù)測連續(xù)值為預(yù)測

評估分類和預(yù)測方法的五條標準

■預(yù)測的準確率

■計算速度

■魯棒性

■可伸縮性

■可解釋性

2.決策樹

①決策樹學習簡介

②決策樹實例

③決策樹學習的算法

①決策樹學習簡介

■決策樹(DecisionTree)學習是以樣本為基礎(chǔ)的歸

納學習方法。

■決策樹的表現(xiàn)形式是類似于流程圖的樹結(jié)構(gòu)，在決

策樹的內(nèi)部節(jié)點進行屬性值測試，并根據(jù)屬性值判

斷由該節(jié)點引出的分支，在決策樹的葉節(jié)點得到結(jié)

論。內(nèi)部節(jié)點是屬性或?qū)傩缘募?，葉節(jié)點代表樣

本所屬的類或類分布。

■經(jīng)由訓練樣本集產(chǎn)生一棵決策樹后，為了對未知樣

本集分類，需要在決策樹上測試未知樣本的屬性值。

測試路徑由根節(jié)點到某個葉節(jié)點，葉節(jié)點代表的類

就是該樣本所屬的類。

②決策樹實例

■關(guān)于尸/ayfeca/s的決策樹如圖所示:

③決策樹學習的算法

■決策樹學習的基本算法是貪心算法，采用自頂向下

的遞歸方￡而造決策樹。

■Hunt等人于1966年提出的概念學習系統(tǒng)CLS是最早

的決策樹算法，以后的許多決策樹算法都是對CLS

算法的改進或由CLS衍生而來。

■Quinlan于1979年提出了著名的ID3方法。以ID3為

藍本的C4.5是一個能處理連續(xù)屬性的算法。

■其他決策樹方法還有ID3的增量版本ID4和ID5等。

■強調(diào)在數(shù)據(jù)挖掘中有伸縮性的決策樹算法有SLIQ、

SPRINT、RainForest算法等。

四.Web挖掘

WWW

Knowledge

目錄

Web挖掘簡介

II.Web日志挖掘

WebMining簡介

1,產(chǎn)生原因

2.應(yīng)用

3.分類

4.過程

1.產(chǎn)生原因

■網(wǎng)絡(luò)信息搜集的需求與收集結(jié)果低效性的

矛盾迫切需要對網(wǎng)絡(luò)資源的整序與檢索。

■傳統(tǒng)數(shù)據(jù)挖掘和文本挖掘技術(shù)的不斷完善

和應(yīng)用。

2.應(yīng)用

■查詢相關(guān)信息

■從Web數(shù)據(jù)發(fā)現(xiàn)潛在的未知信息

■了解用戶的興趣愛好

■信息個性化

3.Web挖掘分類

①Web內(nèi)容挖掘

■Web內(nèi)容挖掘是從文檔內(nèi)容或其描述中抽

取知識的過程。

■Web內(nèi)容挖掘策略

□直接挖掘文檔的內(nèi)容

□在其它工具搜索的基礎(chǔ)上進行改進

Web內(nèi)容挖掘（續(xù)）

■提取文字、圖片或者其他組成網(wǎng)頁內(nèi)容成

分的信息，即通過有效的內(nèi)容挖掘能告訴

我們哪些頁面是德文或者法文的？哪些站

點賣我們喜歡的東西？哪些頁面介紹了我

們感興趣的知識？搜索引擎、智能代理和

一些推薦引擎都使用內(nèi)容挖掘來幫助客戶

在浩瀚的網(wǎng)絡(luò)空間中尋找所需的內(nèi)容。

②Web結(jié)構(gòu)挖掘

■Web結(jié)構(gòu)挖掘研究的是Web文檔的鏈接結(jié)

構(gòu)，揭示蘊含在這些文檔結(jié)構(gòu)中的有用模

式，處理的數(shù)據(jù)是Web結(jié)構(gòu)數(shù)據(jù)。是從

WWW的組織結(jié)構(gòu)和鏈接關(guān)系中推導知識。

由于文檔之間的互連，WWW能夠提供除文

檔內(nèi)容之外的有用信息。利用這些信息，

可以對頁面進行排序，發(fā)現(xiàn)重要的頁面。

Web結(jié)構(gòu)挖掘（續(xù)）

■提取網(wǎng)絡(luò)的拓撲信息—網(wǎng)頁之間的鏈接

信息，即通過有效的結(jié)構(gòu)挖掘能告訴我們

哪些頁面被其他頁面所鏈接？哪些頁面指

向了其他頁面？哪些頁面的集合構(gòu)成了一

個獨立的整體？

③Web日志挖掘

■Web日志挖掘的主要目標則是從Web的訪

問記錄中（Web服務(wù)器log日志）抽取感興

趣的模式。WWW中的每個服務(wù)器都保留了

訪問日志（Webaccesslog））記錄了用

戶訪問和交互的信息。分析這些數(shù)據(jù)可以

幫助理解用戶的行為，從而改進站點的結(jié)

構(gòu)，或為用戶提供個性化的服務(wù)。

Web日志挖掘（續(xù)）

■一般的訪問模式跟蹤

□通過分析日志數(shù)據(jù)來了解用戶的訪問模式和傾

向，以改進站點的組織結(jié)構(gòu)

■個性化的使用記錄跟蹤

傾向于分析單個用戶的偏好，其目的是根據(jù)不

同用戶的訪問模式，為每個用戶提供定制的站

占

八。

Web日志挖掘（續(xù)）

■提取關(guān)于客戶如何運用瀏覽器瀏覽和使用

這些鏈接的信息，即通過有效的日志挖掘

能告訴我們那些客戶訪問了哪些頁面？在

每一頁上待了多長時間？下一步單擊了什

么？在站點中是按照怎樣的訪問路線通向

檢查計數(shù)器，又是通過怎樣的路線直接退

出的？

Web結(jié)構(gòu)挖Web日志挖

內(nèi)容挖掘

Web掘掘

IR方法：無結(jié)構(gòu)

處理數(shù)據(jù)數(shù)據(jù)庫方法：半用戶訪問Web數(shù)

數(shù)據(jù)、半結(jié)構(gòu)數(shù)Web結(jié)構(gòu)數(shù)據(jù)

結(jié)構(gòu)化數(shù)據(jù)據(jù)

類型據(jù)

自由化文本、Serverlog,

HTML標記的超Web文檔內(nèi)及文

主要數(shù)據(jù)HTML標記的超Proxyserverlog,

文本檔間的超鏈

文本Clientlog

詞集、段落、概

表示方法念、IR的三種經(jīng)對象關(guān)系模型圖關(guān)系表、圖

典模型

統(tǒng)計、機器學習、機器學習、專有統(tǒng)計、機器學習、

處理方法數(shù)據(jù)庫技術(shù)

自然語言理解算法關(guān)聯(lián)規(guī)則

模式發(fā)現(xiàn)、數(shù)據(jù)頁面權(quán)重

分類、聚類、模向?qū)А⒍鄬訑?shù)據(jù)Web站點重建，

主要應(yīng)用分類聚類

式發(fā)現(xiàn)庫、站點創(chuàng)建與商業(yè)決策

維護模式發(fā)現(xiàn)

4.Web挖掘過程

■資源發(fā)現(xiàn)：在線或離線檢索Web的過程，例如用

爬蟲(crawler)或(spider)在線收集Web頁面

■信息選擇與預(yù)處理：對檢索到的Web資源的任何

變換都屬于此過程。

□詞干提取

□高低頻詞的過濾

□漢語詞的切分

■綜合過程：自動發(fā)現(xiàn)Web站點的共有模式

■分析過程：對挖掘到的模式進行驗證和可視化處

理

II.Web日志挖掘

1.Web日志挖掘數(shù)據(jù)類型

2.Web日志挖掘應(yīng)用

3.Web日志挖掘過程

?，

二o

I?>:o

E7f.r

“UTfH0

8EJ8:

0*?，-T.60

O二

Oe8ecf二

TTMaCsu1

?DTUtOT7X

m-、rTeO6I

w4、EteZ，dIL

-T0oOX

aIoo-T?H

:a6--0Ct?

*wss8、M3

gf?ne-二0:B?

uI-n0&mn

、z、61H

?，ul、I9Oere_

r，6rsm?lc-nn

r、br，Jl;ST

eeIpeVUII<

Ts，e/oZS、&QM

oIDTO-

、wryT、'-.

Te、nlTIIII

fSuTlBEBTS

iO&Irs1FnMO-2

uMx?8?oOaa::U

::u-DO.M?rJP

:3-M?oSC-2