《商務(wù)數(shù)據(jù)挖掘與應(yīng)用案例分析課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《商務(wù)數(shù)據(jù)挖掘與應(yīng)用案例分析課件（63頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,/62,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),

2、第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,二級(jí),三級(jí),四級(jí),五級(jí),,,*,第,3,章,聚類(lèi)分析,,3.1,概述,>>,,3.2,相似性度量,>>,,,3.3 k-

3、means,算法及其改進(jìn),>>,3.4,一趟聚類(lèi)算法,>>,,3.5,層次聚類(lèi)算法,>>,,3.6,神經(jīng)網(wǎng)絡(luò)方法,>>,,3.7,聚類(lèi)算法評(píng)價(jià),>>,,3.8,綜合例子,>>,,第3章 聚類(lèi)分析 3.1 概述>>,開(kāi)篇案例,——,百思買(mǎi)的客戶(hù)分群,百思買(mǎi)(,BestBuy,)作為美國(guó)最大的家電及,IT,零售連鎖商，其客戶(hù)細(xì)分戰(zhàn)略(,Customer Centricity,)是其經(jīng)營(yíng)及商店定位的重要組成部分。百思買(mǎi)將其中心客戶(hù)分為,5,種類(lèi)型，巴利(,Barry,)，巴茨(,Buzz,)，雷(,Ray,)，店門(mén)(,StoreFront,)，吉兒(,Jill,)。巴利是對(duì)技術(shù)很精通的顧客，吉兒是

4、忙于接送小孩參加各種市區(qū)文體活動(dòng)的住在郊區(qū)的媽媽?zhuān)痛氖菬嶂杂谛峦嬉鈨旱某弊澹资菍?duì)價(jià)格敏感的工薪族，店門(mén)則擁有一家小企業(yè)。除,5,種核心客戶(hù)之外，還有單身年輕女士凱莉(,Carrie,)和空巢一族海倫及查理(,Helen,，,Charlie,)等，也是百思買(mǎi)感興趣的客戶(hù)類(lèi)型。,百思買(mǎi)結(jié)合銷(xiāo)售數(shù)據(jù)(含會(huì)員卡)以及人口分布數(shù)據(jù)，來(lái)確認(rèn)每個(gè)商店是否需要側(cè)重于某個(gè)客戶(hù)群。在其,300,個(gè)店中，就有,40,個(gè)專(zhuān)門(mén)定位于巴利型客戶(hù)，并進(jìn)行了重新布局，在這類(lèi)店中可以看到單獨(dú)的家庭影院店中店，資深銷(xiāo)售，以及便攜設(shè)備專(zhuān)家；吉兒型店的特色導(dǎo)購(gòu)員可以幫主婦選擇合適的數(shù)碼產(chǎn)品；而巴茨店則有大量的電子游戲商品。同一個(gè)

5、店可以側(cè)重于多個(gè)客戶(hù)類(lèi)型，比如吉兒型和巴利型就經(jīng)常被作為同一個(gè)店的定位。每個(gè)店的定位確定之后，相應(yīng)的布局，存貨，人員等，即可相應(yīng)進(jìn)行調(diào)整優(yōu)化。,(資料來(lái)源：, (1),,,,,,,,,,,,,,,,,,,,,,,,,類(lèi)間相似度最小化,(,距離最大化,),,,,類(lèi)內(nèi)相似度最大化,(,距離最小化,),簡(jiǎn)單地描述，,聚類(lèi),(Clustering),是將數(shù)據(jù)集劃分為若干相似對(duì)象組成的多個(gè)組,(group),或簇,(cluster),的過(guò)程，使得同一組中對(duì)象間的相似度最大化，不同組中對(duì)象間的相似度最小化。或者說(shuō)一個(gè)簇,(cluster),就是由彼此相似的一組對(duì)象所構(gòu)成的集合，不同簇中的對(duì)象通常不相似或相

6、似度很低。,3.1 概述 (1)類(lèi)間相似度最小化(距離最大化)類(lèi)內(nèi)相似度,3.1,概述 (2),從機(jī)器學(xué)習(xí)的角度看，聚類(lèi)是一種,無(wú)監(jiān)督的機(jī)器學(xué)習(xí),方法，即事先對(duì)數(shù)據(jù)集的分布沒(méi)有任何的了解，它是將物理或抽象對(duì)象的集合組成為由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的過(guò)程。聚類(lèi)方法的目的是尋找數(shù)據(jù)中：潛在的自然分組結(jié)構(gòu)和感興趣的關(guān)系。,,聚類(lèi)分析中“簇”的特征：,聚類(lèi)所說(shuō)的簇不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來(lái)劃分；,聚的數(shù)目和結(jié)構(gòu)都沒(méi)有事先假定。,3.1 概述 (2)從機(jī)器學(xué)習(xí)的角度看，聚類(lèi)是一種無(wú)監(jiān)督的機(jī),3.1,概述 (,3,),聚類(lèi)分析的應(yīng)用,聚類(lèi)分析正在蓬勃發(fā)展，廣泛應(yīng)用于一些探索性領(lǐng)域,,,如統(tǒng)

7、計(jì)學(xué)與模式分析，金融分析，市場(chǎng)營(yíng)銷(xiāo)，決策支持，信息檢索，,WEB,挖掘，網(wǎng)絡(luò)安全，圖象處理，地質(zhì)勘探、城市規(guī)劃，土地使用、空間數(shù)據(jù)分析，生物學(xué)，天文學(xué)，心理學(xué)，考古學(xué)等。,3.1 概述 (3)聚類(lèi)分析的應(yīng)用,3.1,概述 (,4,),典型聚類(lèi)方法簡(jiǎn)介,劃分方法,：基于質(zhì)心,(K-means),、中心的劃分方法,層次的方法,(hierarchical methods),：,BIRCH,、,ROCK,、,CURE,基于密度的方法,：,,DBSCAN,、,,OPTICS,基于圖的方法,：,Chameleon,、,SNN,基于網(wǎng)格的方法,(grid-based methods),：,,STING,、,

8、WaveCluster,、,CLIQUE,基于模型的方法,(model-based methods),：,EM,、,,COBWEB,、神經(jīng)網(wǎng)絡(luò),其他聚類(lèi)方法,：譜聚類(lèi)算法,(spectral clustering),、蟻群聚類(lèi)算法等,3.1 概述 (4)典型聚類(lèi)方法簡(jiǎn)介,3.2,相似性度量,3.2.1,數(shù)據(jù)及數(shù)據(jù)類(lèi)型,3.2.2,屬性之間的相似性度量,3.2.3,對(duì)象之間的相似性度量,3.2 相似性度量3.2.1 數(shù)據(jù)及數(shù)據(jù)類(lèi)型,7,3.2.1,數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (1),相關(guān)概念,(1),數(shù)據(jù),狹義：,數(shù)字,廣義：,數(shù)據(jù)對(duì)象及其屬性的集合，其表現(xiàn)形式可以是數(shù)字、符號(hào)、文字、圖像抑或是計(jì)算機(jī)代碼等

9、等。,,(2),屬性,也稱(chēng)為特征、維或字段，是指一個(gè)對(duì)象的某方面性質(zhì)或特性。一個(gè)對(duì)象通過(guò)若干屬性來(lái)刻畫(huà)。,73.2.1 數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (1)相關(guān)概念,3.2.1,數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (2),不同的屬性類(lèi)型,屬性類(lèi)型,描述,例子,操作,,,分類(lèi)的,(,定性的,),,標(biāo)稱(chēng),其屬性值只提供足夠的信息以區(qū)分對(duì)象。這種屬性值沒(méi)有實(shí)際意義,顏色、性別、產(chǎn)品編號(hào),眾數(shù)、熵、,列聯(lián)相關(guān)。,,序數(shù),其屬性值提供足夠的信息以區(qū)分對(duì)象的序。,成績(jī)等級(jí),(,優(yōu)、良、中、及格、不及格,),、年級(jí),(,一年級(jí)、二年級(jí)、三年級(jí)、四年級(jí),),中值、百分位、秩相關(guān)、符號(hào)檢驗(yàn)。,,數(shù)值的,(,定量的,),,區(qū)間,其屬性值之間的差是

10、有意義的。,日歷日期、攝氏溫度,均值、標(biāo)準(zhǔn)差、皮爾遜相關(guān),,比率,其屬性值之間的差和比率都是有意義的。,長(zhǎng)度、時(shí)間和速度,幾何平均、調(diào)和平均、百分比變差,3.2.1 數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (2)不同的屬性類(lèi)型屬性類(lèi)型描述,9,,屬性,包含電信客戶(hù)信息的樣本數(shù)據(jù)集,客戶(hù)編號(hào),客戶(hù)類(lèi)別,行業(yè)大類(lèi),通話級(jí)別,通話總費(fèi)用,…,N22011002518,大客戶(hù),采礦業(yè)和一般制造業(yè),市話,16352,…,C14004839358,商業(yè)客戶(hù),批發(fā)和零售業(yè),市話＋國(guó)內(nèi)長(zhǎng)途,(,含國(guó)內(nèi),IP),27891,…,N22004895555,商業(yè)客戶(hù),批發(fā)和零售業(yè),市話＋國(guó)際長(zhǎng)途,(,含國(guó)際,IP),63124,…,322

11、1026196,大客戶(hù),科學(xué)教育和文化衛(wèi)生,市話＋國(guó)際長(zhǎng)途,(,含國(guó)際,IP),53057,…,D14004737444,大客戶(hù),房地產(chǎn)和建筑業(yè),市話＋國(guó)際長(zhǎng)途,(,含國(guó)際,IP),80827,…,︰,︰,︰,︰,︰,…,,對(duì)象,3.2.1,數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (3),例子：包含電信客戶(hù)信息的樣本數(shù)據(jù)集,9屬性包含電信客戶(hù)信息的樣本數(shù)據(jù)集客戶(hù)編號(hào)客戶(hù)類(lèi)別行業(yè)大類(lèi)通,10,3.2.1,數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (4),數(shù)據(jù)集可以看作具有相同屬性的數(shù)據(jù)對(duì)象的集合。在數(shù)據(jù)挖掘領(lǐng)域，關(guān)于數(shù)據(jù)集有三個(gè)方面的問(wèn)題需要考慮：維度、稀疏性和分辨率。,(1),維度,(Dimensionality),指數(shù)據(jù)集中的對(duì)象具有的屬性

12、個(gè)數(shù)總和。,維歸約,(2),稀疏性,(Sparsity),指在某些數(shù)據(jù)集中，有意義的數(shù)據(jù)非常少，對(duì)象在大部分屬性上的取值為,0,；非零項(xiàng)不到,1%,。,文本數(shù)據(jù)集,(3),分辨率,(Resolution),不同分辨率下數(shù)據(jù)的性質(zhì)不同,103.2.1 數(shù)據(jù)及數(shù)據(jù)類(lèi)型 (4)數(shù)據(jù)集可以看作具有相同,11,3.2.2,屬性之間的相似性度量,簡(jiǎn)單屬性間的相似度和相異度,兩個(gè)屬性相似程度的數(shù)值度量，兩個(gè)屬性越相似，它們的相似度就越高。相異度與相似度相反。,不同類(lèi)型的屬性使用的相似性度量是不同的。,113.2.2 屬性之間的相似性度量 簡(jiǎn)單屬性間的相似度和相,12,3.2.3,對(duì)象之間的相似性度量 (1)

13、,對(duì)象之間的相似性度量，即多個(gè)屬性整體的相似性度量方法,。對(duì)象之間的相似度計(jì)算涉及描述對(duì)象的屬性類(lèi)型，需要將不同屬性上的相似度整合成一個(gè)總的相似度來(lái)表示。,相似性度量方法,包括：距離度量和相似系數(shù)。,假定使用,m,個(gè)屬性來(lái)描述數(shù)據(jù)記錄，將每條記錄看成,m,維空間中的一個(gè)點(diǎn)，距離越小、相似系數(shù)越大的記錄之間的相似程度越大。這里分三種情況來(lái)描述：,(1),所有屬性是,數(shù)值型,的；,(2),所有屬性都是,二值屬性,的；,(3),同時(shí)包含有分類(lèi)屬性和數(shù)值屬性的,混合屬性,。,,123.2.3 對(duì)象之間的相似性度量 (1)對(duì)象之間的相似性,(1),數(shù)值屬性相似性度量,1,)距離度量,(,a,) 閔可夫斯

14、基,(Minkowski ),距離,,,,x=1,,城市塊(曼哈頓)距離,x=2,,歐幾里得距離,x=,∞,,,切比雪夫,(Chebyshev),距離,3.2.3,對(duì)象之間的相似性度量 (2),,,,(1) 數(shù)值屬性相似性度量3.2.3 對(duì)象之間的相似性度量,14,Minkowski,距離計(jì)算例子,Distance Matrix,3.2.3,對(duì)象之間的相似性度量 (3),14Minkowski 距離計(jì)算例子Distance Mat,15,,,,,,,3.2.3,對(duì)象之間的相似性度量 (4),Canberra,距離是由,Lance,和,Williams,最早提出的，定義如下：,,Canberra

15、,距離或,Lance,距離可以看成一種相對(duì)曼哈頓距離，它克服了,Minkowski,距離受量綱影響的缺點(diǎn),Canberra,距離對(duì)缺省值是穩(wěn)健的，當(dāng)兩個(gè)坐標(biāo)都接近,0,時(shí)，,Canberra,距離對(duì)微小的變化很敏感。,,,,153.2.3 對(duì)象之間的相似性度量 (4)Canberra,2),相似系數(shù),(,a,) 余弦相似度,,余弦相似度忽略各向量的絕對(duì)長(zhǎng)度，著重從形狀方面考慮它們之間的關(guān)系。取值范圍在區(qū)間,[-1,，,1],內(nèi)。當(dāng)兩個(gè)向量方向相近時(shí)，夾角余弦值較大，反之則較小。特別地，當(dāng)兩個(gè)向量平行時(shí)，夾角余弦值為,1,，而正交時(shí)余弦值為,0,。,,(b),相關(guān)系數(shù),相關(guān)系數(shù)是向量標(biāo)準(zhǔn)化后的夾

16、角余弦，取值范圍在區(qū)間,[-1,，,1],內(nèi)。它表示兩個(gè)向量的線性相關(guān)程度。,,,3.2.3,對(duì)象之間的相似性度量 (,5,),,,,,,2) 相似系數(shù)3.2.3 對(duì)象之間的相似性度量 (5),(c),廣義,Jaccard,系數(shù),廣義,Jaccard,系數(shù)又稱(chēng)為,Tanimoto,系數(shù)，用,EJ,表示，取值范圍在區(qū)間,[0,，,1],內(nèi)。廣泛用于信息檢索和生物學(xué)分類(lèi)中，在二元屬性情況下簡(jiǎn)化為,Jaccard,系數(shù)。,,,3.2.3,對(duì)象之間的相似性度量 (,6,),,,,,,,(c)廣義Jaccard系數(shù)3.2.3 對(duì)象之間的相似性度量,(,2,)二值屬性的相似性度量,一個(gè)二值屬性變量(,bi

17、nary variable,)只有,0,或,1,兩種狀態(tài)，表示屬性的存在與否。一種差異計(jì)算方法就是根據(jù)二值數(shù)據(jù)計(jì)算。,假設(shè)二值屬性對(duì)象,p,和,q,的取值情況如表,3-3,所示，其中,n11,表示對(duì)象,p,和,q,中均取,1,的二值屬性個(gè)數(shù)，,n10,表示對(duì)象,p,取,1,而對(duì)象,q,取,0,的二值屬性個(gè)數(shù)，,n01,表示對(duì)象,p,取,0,而對(duì)象,q,取,1,的二值屬性個(gè)數(shù)，,n00,表示對(duì)象,p,和,q,均取,0,的二值屬性個(gè)數(shù)。,3.2.3,對(duì)象之間的相似性度量 (,7,),,,,,,表,3-3,,二值屬性對(duì)象,p,和,q,的取值情況,對(duì)象,p,對(duì)象,q,,1,0,合計(jì),1,n,11,n,

18、10,n,11,+n,10,0,n,01,n,00,N,01,+n,00,合計(jì),n,11,+n,01,n,10,+n,00,,(2)二值屬性的相似性度量3.2.3 對(duì)象之間的相似性度量,二值屬性相似性存在對(duì)稱(chēng)的和不對(duì)稱(chēng)兩種情況,。如果二值屬性的兩個(gè)狀態(tài)值所表示的內(nèi)容同等重要，則是對(duì)稱(chēng)的，否則為不對(duì)稱(chēng)。如，給定變量,smoker,，它描述一個(gè)病人是否吸煙的情況，用,0,或,1,進(jìn)行編碼來(lái)表示一個(gè)病人吸煙狀態(tài)是同等重要的，因此,smoker,是對(duì)稱(chēng)變量。,基于,對(duì)稱(chēng)二值變量,所計(jì)算的相似度稱(chēng)為,不變相似性,(即變量編碼的改變不會(huì)影響計(jì)算結(jié)果)。對(duì)于不變相似性，常用簡(jiǎn)單匹配相關(guān)系數(shù)來(lái)描述對(duì)象,p,和

19、,q,之間的差異程度，其定義為：,,對(duì)于不對(duì)稱(chēng)的二值變量，如果取值,1,比,0,重要，那么這樣的二值變量就只有一種狀態(tài)。,例如，屬性,disease,的檢測(cè)結(jié)果是陽(yáng)性或陰性，這兩個(gè)結(jié)果的重要性是不一樣的，通常將少見(jiàn)而重要的情況用,1,表示 (如,HIV,陽(yáng)性)，將不重要情況用,0,表示。這種情況下對(duì)象,p,和,q,之間的差異程度評(píng)價(jià)通常采用,Jaccard,系數(shù)，其定義為：,,,3.2.3,對(duì)象之間的相似性度量 (,8,),,,,,,,,二值屬性相似性存在對(duì)稱(chēng)的和不對(duì)稱(chēng)兩種情況。如果二值屬性的兩個(gè),(,3),混合屬性相似性度量,在實(shí)際應(yīng)用中，數(shù)據(jù)對(duì)象往往包含多種類(lèi)型的屬性，因此使用混合類(lèi)型的屬

20、性描述。這需要將不同類(lèi)型的屬性差異度組合成一個(gè)整體，把所有屬性間的差異轉(zhuǎn)換到區(qū)間,[0,，,,1],中。,假設(shè)數(shù)據(jù)集包含,m,個(gè)不同類(lèi)型的屬性，對(duì)象,p,和,q,之間的差異度推廣,Minkowski,距離，定義為,:,3.2.3,對(duì)象之間的相似性度量 (,9,),,,,,,,(3)混合屬性相似性度量3.2.3 對(duì)象之間的相似性度量 (,對(duì)象,p,和,q,在屬性,f,上的相異度,,根據(jù)其屬性類(lèi)型不同進(jìn)行相應(yīng)計(jì)算：,(,a,)若屬性,f,,為二元屬性或標(biāo)稱(chēng)屬性，則：如果,,，那么,,，否則,,。,(,b,)若屬性,f,,為序數(shù)型屬性，計(jì)算對(duì)象,p,和對(duì)象,q,在屬性,f,上的秩(或等級(jí)),,和,,

21、，,,。,(,c,)若屬性,f,,為區(qū)間標(biāo)度屬性，則,,，,,、,,分別表示屬性,f,,的最大值和最小值。,(,d,)若屬性,f,,為比率數(shù)值屬性，則通過(guò)變換轉(zhuǎn)換為區(qū)間標(biāo)度屬性來(lái)處理。,這樣，當(dāng)描述對(duì)象的屬性是不同類(lèi)型時(shí)，對(duì)象之間的相異度也能夠計(jì)算，且取值在,[0,，,1],區(qū)間。,3.2.3,對(duì)象之間的相似性度量 (,10,),,,,,,,,,,,,,,,,對(duì)象p和q在屬性f上的相異度 根據(jù)其屬性類(lèi)型不同進(jìn)行相應(yīng)計(jì)算,(,4),由距離度量轉(zhuǎn)換而來(lái)的相似性度量,可以通過(guò)一個(gè)單調(diào)遞減函數(shù)，將距離轉(zhuǎn)換成相似性度量，相似性度量的取值一般在區(qū)間,[0,，,1],之間，值越大，說(shuō)明兩個(gè)對(duì)象越相似。常用的

22、方式有：,① 采用負(fù)指數(shù)函數(shù)將距離轉(zhuǎn)換為相似性度量,s,，即：,,②,采用距離的倒數(shù)作為相似性度量，即：,分母上加,1,是為了避免分母為,0,時(shí)出現(xiàn)錯(cuò)誤。,,③,若距離在,0,～,1,之間，可采用與,1,的差作為相似系數(shù)，即：,,,3.2.3,對(duì)象之間的相似性度量 (,11,),,,,,,,,,,(4)由距離度量轉(zhuǎn)換而來(lái)的相似性度量3.2.3 對(duì)象之間的相,3.3 k-means,算法及其改進(jìn),3.3.1 k-means,算法,3.3.2 k-means,算法的改進(jìn),3.3 k-means算法及其改進(jìn)3.3.1 k-means,3.3,.1,K-means,算法(1),K-means,算法是,

23、1967,年由,MacQueen,提出的，迄今為止，很多聚類(lèi)任務(wù)都選擇該經(jīng)典算法。其核心思想是找出,K,個(gè)簇中心,,，使得每一個(gè)數(shù)據(jù)點(diǎn),,到其最近的簇中心,,的平方距離和被最小化。,k-means,聚類(lèi)算法的形式化描述如下：,(1),從數(shù)據(jù)集,D,中任意選擇,k,個(gè)對(duì)象作為初始簇中心；,(2) repeat,(3) for,數(shù)據(jù)集,D,中每個(gè)對(duì)象,P do,(4),計(jì)算對(duì)象,P,到,k,個(gè)簇中心的距離,(5),將對(duì)象,P,指派到與其最近,(,距離最短,),的簇；,(6) end for,(7),計(jì)算每個(gè)簇中對(duì)象的均值，做為新的簇的中心；,(8) until k,個(gè)簇的簇中心不再發(fā)

24、生變化,k-means,算法中用如,,來(lái)表示一個(gè)簇。,,3.3.1 K-means 算法(1) K-means 算,k-means,描述容易、實(shí)現(xiàn)簡(jiǎn)單、快速，但存在如下不足：,(,1,)簇個(gè)數(shù),k,需要預(yù)先指定，但實(shí)際上難以確定；,(,2,)算法對(duì)初始值的選取依賴(lài)性極大以及算法常陷入局部最優(yōu)解；,(,3,)由于簇的質(zhì)心(即均值)作為簇中心進(jìn)行新一輪聚類(lèi)計(jì)算，孤立點(diǎn)和噪聲點(diǎn)會(huì)導(dǎo)致簇質(zhì)心偏離真正的數(shù)據(jù)密集區(qū)，所以,k-means,對(duì)噪聲點(diǎn)和孤立點(diǎn)很敏感；,(,4,)不能用于發(fā)現(xiàn)非凸形狀的簇，或具有各種不同大小或密度的簇。例如圖,3-1,所示的兩個(gè)簇，用,k-means,劃分方

25、法不能正確識(shí)別，原因在于它們所采用的簇的表示及簇間相似性度量不能反映這些自然簇的特征；,(,5,)只能用于處理數(shù)值屬性的數(shù)據(jù)集，不能處理包含分類(lèi)屬性的數(shù)據(jù)集。,3.3,.1,K-means,算法(,2,),,,圖,3-1,基于質(zhì)心的劃分方法不能識(shí)別的數(shù)據(jù)示例,k-means描述容易、實(shí)現(xiàn)簡(jiǎn)單、快速，但存在如下不足：3.,例,3-1,對(duì)表,3-4,中二維數(shù)據(jù)，使用,k-means,算法將其劃分為,2,個(gè)簇，假設(shè)初始簇中心選為,P7(4,，,5),，,P10(5,，,5),。,3.3,.1,K-means,算法(,3,),,,,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,x,3,

26、3,7,4,3,8,4,4,7,5,y,4,6,3,7,8,5,5,1,4,5,表,3-4,,k-means,聚類(lèi)過(guò)程示例數(shù)據(jù)集,解：圖,3-2,顯示了對(duì)于給定的數(shù)據(jù)集,k-means,聚類(lèi)算法的執(zhí)行過(guò)程。,,圖,3-2 k-means,算法聚類(lèi)過(guò)程示例,例3-1 對(duì)表3-4中二維數(shù)據(jù)，使用k-means算法將其,(,1,)根據(jù)題目，假設(shè)劃分的兩個(gè)簇分別為,C,1,和,C,2,，初始中心分別為(,4,，,5,)和(,5,，,5,)，下面計(jì)算,10,個(gè)樣本到這,2,個(gè)簇中心的距離，并將,10,個(gè)樣本指派到與其最近的簇：,(,2,)第一輪迭代結(jié)果如下：,屬于簇,C,1,的樣本有：,{P7,，,

27、P1,，,P2,，,P4,，,P5,，,P8},屬于簇,C,2,的樣本有：,{P10,，,P3,，,P6,，,P9},重新計(jì)算新的簇中心，,得到：,C,1,的中心為(,3.5,，,5.167,)，,C,2,的中心為(,6.75,，,4.25,),(,3,)繼續(xù)計(jì)算,10,個(gè)樣本到兩個(gè)新的簇中心的距離，重新分配到新的簇中，第二輪迭代結(jié)果如下：,屬于簇,C1,的樣本有：,{ P1,，,P2,，,P4,，,P5,，,P7,，,P10},屬于簇,C2,的樣本有：,{ P3,，,P6,，,P8,，,P9},重新計(jì)算新的簇中心，得到：,C1,的中心為(,3.67,，,5.83,)，,C2,的中心為(,6.

28、5,，,3.25,),(,4,)繼續(xù)計(jì)算,10,個(gè)樣本到兩個(gè)新的簇中心的距離，重新分配到新的簇中，發(fā)現(xiàn)簇中心不再發(fā)生變化，算法終止。,3.3,.1,K-means,算法(,4,),,,(1)根據(jù)題目，假設(shè)劃分的兩個(gè)簇分別為C1和C2，初始中心分,,,3.3,.2,K-means,算法的改進(jìn)(1),k-means,算法中距離的計(jì)算基于數(shù)值型數(shù)據(jù),，沒(méi)有說(shuō)明對(duì)于分類(lèi)型數(shù)據(jù)如何處理。此外，它對(duì)于噪聲和離群點(diǎn)數(shù)據(jù)敏感。介紹,k-means,聚類(lèi)算法的一些改進(jìn)策略，它們?cè)诔跏即貢r(shí)對(duì)象的選擇、相似度的計(jì)算方法或簇中心的計(jì)算方法等不同。,,下面介紹三種,k-means,算法的改進(jìn)方法：,(,1,)將分類(lèi)型數(shù)

29、據(jù)轉(zhuǎn)化為數(shù)值型數(shù)據(jù)，再利用,k-means,算法進(jìn)行聚類(lèi)分析。,(,2,)適用于純分類(lèi)屬性數(shù)據(jù)集的,k-modes,算法和適用于混合屬性數(shù)據(jù)集的,k-prototypes,算法。,k-modes,算法采用,mode,(取值頻率最大的屬性值，即眾數(shù))來(lái)表示分類(lèi)屬性，在聚類(lèi)過(guò)程中使用簡(jiǎn)單匹配來(lái)度量分類(lèi)屬性的不相似性(,dissimilarity,)。將,k-modes,算法和,k-means,結(jié)合到一起形成了,k-prototypes,算法，用來(lái)處理具有混合屬性的數(shù)據(jù)集。,(,3,)適用于混合屬性數(shù)據(jù)集的,K-Summary,算法，它使用簇的摘要信息表示簇的質(zhì)心。,3.3.2 K-means 算法

30、的改進(jìn)(1) k-mean,數(shù)據(jù)往往具有混合屬性的特點(diǎn)，這里介紹一種簡(jiǎn)單的聚類(lèi)表示方法，并對(duì),閔可夫斯基(,Minkowski,)距離進(jìn)行推廣以使聚類(lèi)算法可以有效處理包含分類(lèi)屬性的數(shù)據(jù),。,假設(shè)數(shù)據(jù)集,D,有,m,個(gè)屬性，其中有,,個(gè)分類(lèi)屬性和,,個(gè)數(shù)值屬性，,,，設(shè)分類(lèi)屬性位于數(shù)值屬性之前，用,,表示第,i,個(gè)屬性取值的集合。,定義3,-1,給定簇,C,，,,，,a,在,C,中關(guān)于,D,i,,的頻度定義為,C,在,,D,i,上的投影中包含,a,的次數(shù)：,,定義3,-2,給定簇,C,，,C,的摘要信息,CSI,(Cluster Summary Information),定義為：,,，其中,,

31、為,C,的大小,,,由分類(lèi)屬性中不同取值的頻度信息和數(shù)值型屬性的質(zhì)心兩部分構(gòu)成，即：,,3.3,.2,K-means,算法的改進(jìn)(2),,,,數(shù)據(jù)往往具有混合屬性的特點(diǎn)，這里介紹一種簡(jiǎn)單的聚類(lèi)表示方法，,定義3,-3,給定,D,的簇,C,、 和,,,對(duì)象 與 ，,x>0,。,,(1),對(duì)象,p,，,q,在屬性,i,上的差異程度,(,或距離,),定義為：,對(duì)于分類(lèi)屬性或二值屬性，,,,;,,對(duì)于連續(xù)數(shù)值屬性或順序?qū)傩裕? ；,(2),

32、兩個(gè)對(duì)象,p,，,q,間的差異程度,(,或距離,),定義為：,,,;,,,3.3,.2,K-means,算法的改進(jìn)(3),定義3-3 給定D的簇C、 和 ,對(duì)象,(3),對(duì)象,p,與簇,C,間的距離 定義為,p,與簇,C,的摘要之間的距離：,,,這里 為,p,與,C,在屬性 上的距離，對(duì)于分類(lèi)屬性 其值定義為,p,與,C,中每個(gè)對(duì)象在屬性 上的距離的算術(shù)平均值，即,；,對(duì)于數(shù)值屬性 其值定義為,,,,,,,,,,,,,,,,,,,,,,,,,,,3.3,.2,K-means,算法的改進(jìn)(4

33、),(3)對(duì)象p與簇C間的距離 定義為p與,(4),簇,C,1,與,C,2,間的距離 定義為兩個(gè)簇的摘要間的距離：,,這里 為 與 在屬性 上的距離，對(duì)于分類(lèi)屬性 其值定義為 中每個(gè)對(duì)象與 中每個(gè)對(duì)象的差異的平均值：,,,對(duì)于數(shù)值屬性 其值定義為,,在定義,3-3,的,(2),中，當(dāng),x=1,時(shí)，相當(dāng)于曼哈頓,(Manhattan),距離，當(dāng),x=2,時(shí)，相當(dāng)于歐式,(Euclidean),距離。,3.3,.2,K-means,算法的改進(jìn)(5),

34、,,(4) 簇C1與C2間的距離,3.3,.2,K-means,算法的改進(jìn)(6),例,3-2,假設(shè)描述學(xué)生的信息包含屬性：性別，籍貫，年齡。有兩條記錄,p,，,q,及兩個(gè)簇,C1,，,C2,的信息如下，分別求出記錄和簇彼此之間的距離：,p={,男，廣州，,18},，,q={,女，深圳，,20},,C1={,男：,25,，女：,5,；廣州：,20,，深圳：,6,，韶關(guān)：,4,；,19},,C2={,男：,3,，女：,12,；汕頭：,12,，深圳：,1,，湛江：,2,；,24},按定義,4-3,，取,x=1,得到的各距離如下：,d(p,，,q)=1+1+(20-18)=4,,d(p,，,C1)=(

35、1-25/30)+(1-20/30)+(19-18)=1.5,,d(p,，,C2)=(1-3/15)+(1-0/15)+(24-18)=7.8,d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30,d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15,d(C1,C2)=1-(25*3+5*12)/(30*15)+1-6*1/(30*15)+(24-19)=1003/150≈6.69,3.3.2 K-means 算法的改進(jìn)(6) 例3-2 假,3.3,.2,K-means,算法的改進(jìn)(7),用定義,3-3,取代相關(guān)聚類(lèi)算法中的距離定義，就可

36、使原來(lái)僅適用于數(shù)值或分類(lèi)屬性的聚類(lèi)算法不受數(shù)據(jù)類(lèi)型的限制而可用于任何數(shù)據(jù)類(lèi)型。,,k-summary,算法,就是采用定義,3-3,推廣了,k-means,算法，可以處理混合屬性數(shù)據(jù)集。由三個(gè)主要步驟完成,:,(,1,)初始化,:,選擇,k,個(gè)對(duì)象，創(chuàng)建,k,個(gè)簇的,CSI,；,(,2,)劃分對(duì)象到最接近的簇,;,(,3,)重新計(jì)算每個(gè)簇的,CSI;,(,4,)重復(fù)(,2,)和(,3,)直到選用的度量函數(shù)收斂，如誤差和變化很小或相鄰兩次迭代沒(méi)有對(duì)象從一個(gè)簇移動(dòng)到另一個(gè)簇。,3.3.2 K-means 算法的改進(jìn)(7) 用定義3-3,例,3-3,對(duì)于表,3-5,所示的數(shù)據(jù)集，請(qǐng)使用,k-summ

37、ary,算法將其劃分為,2,個(gè)簇，并選擇記錄,3,和,5,分別為每個(gè)簇的初始對(duì)象。,$_,年收入為年收入列規(guī)范化后的結(jié)果。,,表,3-5,某銀行拖欠貸款數(shù)據(jù),3.3,.2,K-means,算法的改進(jìn)(8),序號(hào),是否有房,婚姻狀況,年收入,$_,年收入,拖欠貸款,1,yes,single,125K,0.406,no,2,no,married,100K,0.25,no,3,no,single,70K,0.063,no,4,yes,married,120K,0.375,no,5,no,divorced,95K,0.219,yes,6,no,married,60K,0,no,7,yes,divorc

38、ed,220K,1,no,8,no,single,85K,0.156,yes,9,no,married,75K,0.094,no,10,no,single,90K,0.188,yes,例3-3 對(duì)于表3-5所示的數(shù)據(jù)集，請(qǐng)使用k-summary,3.3,一趟聚類(lèi)算法,現(xiàn)有聚類(lèi)算法的普遍存在以下不足：,對(duì)于大規(guī)模數(shù)據(jù)集，聚類(lèi)時(shí)效性和準(zhǔn)確性難以滿(mǎn)足要求；,難以直接處理混合屬性的數(shù)據(jù)；,聚類(lèi)結(jié)果依賴(lài)于參數(shù)，而參數(shù)的選擇主要靠經(jīng)驗(yàn)或試探，沒(méi)有簡(jiǎn)單、通用的方法。,3.3 一趟聚類(lèi)算法 現(xiàn)有聚類(lèi)算法的普遍存在以下不足：,一趟聚類(lèi)算法采用摘要信息,CSI,表示一個(gè)簇,，及定義,3-3,來(lái)度量距離，其將數(shù)

39、據(jù)集分割為半徑幾乎相同的超球體(簇)。具體過(guò)程如下：,,(,1,)初始時(shí)，簇集合為空，讀入一個(gè)新的對(duì)象；,(,2,)以這個(gè)對(duì)象構(gòu)造一個(gè)新的簇；,(,3,)若已到數(shù)據(jù)庫(kù)末尾，則轉(zhuǎn)(,5,)，否則讀入新對(duì)象，利用給定的距離定義，計(jì)算它與每個(gè)已有簇間的距離，并選擇最小的距離；若最小距離超過(guò)給定的半徑閾值,r,，轉(zhuǎn)(,2,)；,(,4,)否則將該對(duì)象并入具有最小距離的簇中并更新該簇的各分類(lèi)屬性值的統(tǒng)計(jì)頻度及數(shù)值屬性的均值，轉(zhuǎn)(,3,)；,(,5,)結(jié)束。,3.,4.1,,算法描述,一趟聚類(lèi)算法采用摘要信息CSI表示一個(gè)簇，及定義3-3來(lái)度量,3.,4.2,,聚類(lèi)閾值的選擇策略,,采用抽樣技術(shù)來(lái)計(jì)算閾值

40、范圍，具體描述如下：,(1),在數(shù)據(jù)集,D,中隨機(jī)選擇對(duì)對(duì)象；,(2),計(jì)算每對(duì)對(duì)象間的距離；,(3),計(jì)算,(2),中距離的平均值,EX,和標(biāo)準(zhǔn)差,DX,；,(4),取,r,在,EX+0.25DX,到,EX-2DX,之間,,例,3-4,一趟聚類(lèi)算法聚類(lèi)過(guò)程示例。,對(duì)于表,3-5,的數(shù)據(jù)集，采用一趟聚類(lèi)算法聚類(lèi)。,EX=43,，,DX=45,，取,r=EX,，若規(guī)范化年收入屬性，則,EX=1.32,DX=0.89,,取,r=EX,。表中,$_,年收入為年收入規(guī)范化的結(jié)果。,,3.4.2 聚類(lèi)閾值的選擇策略 采用抽樣技術(shù)來(lái)計(jì)算閾值范圍，,3.5,層次聚類(lèi)算法,3.5.1,概述,3.5.2 BIR

41、CH,算法,3.5.3,兩步聚類(lèi)算法,3.5 層次聚類(lèi)算法3.5.1 概述,3.,5.1 概述 (1),層次聚類(lèi)法,是一種已得到廣泛使用的經(jīng)典方法，它是通過(guò)將數(shù)據(jù)組織為若干組并形成一個(gè)相應(yīng)的樹(shù)來(lái)進(jìn)行聚類(lèi)。層次聚類(lèi)方法可分為自頂向下和自下而上兩種層次聚類(lèi)。,,自下而上聚合層次聚類(lèi)方法,(,或凝聚層次聚類(lèi),),。這種自下而上策略就是最初將每個(gè)對(duì)象,(,自身,),作為一個(gè)簇，然后將這些簇進(jìn)行聚合以構(gòu)造越來(lái)越大的簇，直到所有對(duì)象均聚合為一個(gè)簇，或滿(mǎn)足一定終止條件為止。絕大多數(shù)層次聚類(lèi)方法屬于這一類(lèi)，只是簇間相似度的定義有所不同。,自頂向下分解層次聚類(lèi)方法,(,或分裂層次聚類(lèi),),。這種策略的作法與自下

42、而上策略的作法相反。它首先將所有對(duì)象看成一個(gè)簇的內(nèi)容，將其不斷分解以使其變成越來(lái)越小但個(gè)數(shù)越來(lái)越多的小簇，直到所有對(duì)象均獨(dú)自構(gòu)成一個(gè)簇，或滿(mǎn)足一定終止條件為止。,3.5.1 概述 (1)層次聚類(lèi)法是一種已得到廣泛使用的經(jīng)典,圖,3-3,兩種不同層次聚類(lèi)算法,,3.,5.1 概述,(2),圖,3-3,描述了一種,凝聚層次聚類(lèi)算法,AGENS,(,AGglomerative NESting,)和一種,分裂層次聚類(lèi)算法,DIANA,(,DIvisive ANAlysis,)對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合,{a,，,b,，,c,，,d,，,e},的處理過(guò)程。,其中從左往右的過(guò)程屬于凝聚層次聚類(lèi)方法：,圖

43、3-3 兩種不同層次聚類(lèi)算法3.5.1 概述 (2)圖3-,3.5.2 BIRCH,算法 (1),BIRCH,算法,是一種,基于距離的層次聚類(lèi)算法,，其,核心是聚類(lèi)特征,CF,(,Cluster Feature,)和,聚類(lèi)特征樹(shù),(,CF-Tree,)，它們用于概括簇描述。這些結(jié)構(gòu)使得,BIRCH,方法對(duì)增量和動(dòng)態(tài)聚類(lèi)非常有效。下面詳細(xì)討論聚類(lèi)特征和聚類(lèi)特征樹(shù)。,,(,1,),CF,結(jié)構(gòu),聚類(lèi)特征(,CF,)是一個(gè)包含聚類(lèi)信息的三元組，其定義如下：,給定一個(gè)簇中的,N,個(gè),d,維的數(shù)據(jù)點(diǎn)：,,，這個(gè)簇的聚類(lèi)特征,CF,向量是一個(gè)三元組,,，其中,,N,是簇中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，,,是,N,個(gè)數(shù)據(jù)點(diǎn)的

44、線性和(即,,)，而,,SS,是,,N,個(gè)數(shù)據(jù)點(diǎn)的平方和(即,,)。其中線性和反映了聚類(lèi)的質(zhì)心，平方和反映了簇的直徑大小，它們的作用是計(jì)算平均值和方差。,聚類(lèi)特征具有可加性。,,,,,,,,,,3.5.2 BIRCH算法 (1)BIRCH算法是一種基于距,例,3-5,假定在簇 中有三個(gè)點(diǎn),(2,，,5),，,(3,，,2),和,(4,，,3),。 的聚類(lèi)特征是：,,CF,1,=<3,，,(2+3+4,，,5+2+3),，,(,,,，,)> = <3,，,(9,，,10),，,(29,，,28)>,假定 是與 不相交的簇，,CF,2,,= <3,，,(35,，,36)

45、,，,(417,，,440)>,。,和 合并形成一個(gè)新的簇 ，其聚類(lèi)特征便是 ，即：,,CF,3,=<3+3,，,(9+35,，,10+36),，,(29+417,，,38+440)> = <6,，,(44,，,46),，,(446,，,478)>,3.5.2 BIRCH,算法 (2),例3-5 假定在簇 中有三個(gè)點(diǎn)(2，5)，(3，2)和,(,2,),CF-,樹(shù),一個(gè),CF-,樹(shù)是一個(gè)高度平衡的樹(shù)，它具有三個(gè)參數(shù)：非葉節(jié)點(diǎn),CF,條目最大個(gè)數(shù),B,、葉節(jié)點(diǎn)中,CF,條目的最大個(gè)數(shù),L,和距離閾值,T,。,這些參數(shù)影響結(jié)果樹(shù)的大小，其目標(biāo)是通

46、過(guò)參數(shù)調(diào)整，將,CF,樹(shù)保存在內(nèi)存中。每個(gè)非葉節(jié)點(diǎn)最多容納,B,個(gè)形為,,的,CF,條目，,,是一個(gè)指向它的第,,個(gè)子節(jié)點(diǎn)的指針，,,是由這個(gè),,指向的子節(jié)點(diǎn)所代表的子聚類(lèi)的,,。一個(gè)葉節(jié)點(diǎn)最多容納,,個(gè),,條目，每個(gè)葉節(jié)點(diǎn)還有一個(gè)指向前面節(jié)點(diǎn)的指針,,和指向后面葉節(jié)點(diǎn)的指針,,，這樣所有葉節(jié)點(diǎn)形成一個(gè)鏈表可以方便掃描。當(dāng),B=6,，,L=5,時(shí)的一棵,CF,樹(shù)的圖形如圖,3-4,。,3.5.2 BIRCH,算法 (3),(2)CF-樹(shù)3.5.2 BIRCH算法 (3),3.5.2 BIRCH,算法 (4),CF-,樹(shù)構(gòu)造過(guò)程實(shí)際是一個(gè)數(shù)據(jù)點(diǎn)的插入過(guò)程，步驟如下：,(,a,)從根節(jié)點(diǎn)開(kāi)始遞歸往

47、下，計(jì)算當(dāng)前條目與要插入數(shù)據(jù)點(diǎn)之間的距離，尋找距離最小的那個(gè)路徑，直到找到與該數(shù)據(jù)點(diǎn)最接近的葉節(jié)點(diǎn)中的條目。,(,b,)比較計(jì)算出的距離是否小于閾值,T,，如果小于閾值,T,則當(dāng)前條目吸收該數(shù)據(jù)點(diǎn)；如果距離大于等于閾值,T,，則轉(zhuǎn),(c),。,(,c,)判斷當(dāng)前條目所在葉節(jié)點(diǎn)的條目個(gè)數(shù)是否小于,L,，如果是則直接將數(shù)據(jù)點(diǎn)插入為該數(shù)據(jù)點(diǎn)的新條目，否則需要分裂該葉節(jié)點(diǎn)。分裂的原則是尋找該葉節(jié)點(diǎn)中距離最遠(yuǎn)的兩個(gè)條目并以這兩個(gè)條目作為分裂后新的兩個(gè)葉節(jié)點(diǎn)的起始條目，其它剩下的條目根據(jù)距離最小原則分配到這兩個(gè)新的葉節(jié)點(diǎn)中，刪除原葉節(jié)點(diǎn)并更新整個(gè),CF,樹(shù)。,當(dāng)數(shù)據(jù)點(diǎn)無(wú)法插入時(shí)，這個(gè)時(shí)候需要提升閾值,T,

48、并重建樹(shù)來(lái)吸收更多的葉節(jié)點(diǎn)條目，直到把所有數(shù)據(jù)點(diǎn)全部插入完畢。,3.5.2 BIRCH算法 (4)CF-樹(shù)構(gòu)造過(guò)程實(shí)際是一個(gè),3.5.2 BIRCH,算法 (5),(,3,),BIRCH,算法描述,,BIRCH,算法主要分為四個(gè)階段：,第一個(gè)階段對(duì)整個(gè)數(shù)據(jù)集進(jìn)行掃描，根據(jù)給定的初始距離閾值,T,建立一棵初始聚類(lèi)特征樹(shù)；,第二階段通過(guò)提升閾值,T,重建,CF,樹(shù)，得到一棵壓縮的,CF,樹(shù)。,第三、四階段利用全局聚類(lèi)算法對(duì)已有的,CF,樹(shù)進(jìn)行聚類(lèi)得到更好的聚類(lèi)結(jié)果。,,3.5.2 BIRCH算法 (5)(3)BIRCH算法描述,3.5.2 BIRCH,算法 (,6,),其中具體建樹(shù)階段算法步驟如下

49、：,(,a,)給定一個(gè)初始的距離閾值,T,并初始化一棵,CF-,樹(shù),t1,。,(,b,)掃描數(shù)據(jù)點(diǎn)并插入到,CF-,樹(shù),t1,中。,(,c,)判斷內(nèi)存是否溢出，如果沒(méi)有溢出轉(zhuǎn)(,d,)，如果溢出轉(zhuǎn)(,e,)。,(,d,)此時(shí)已經(jīng)掃描完所有數(shù)據(jù)點(diǎn)，將存儲(chǔ)在磁盤(pán)中的潛在離群點(diǎn)重新吸收到,CF-,樹(shù),t1,中，結(jié)束建樹(shù)。,(,e,)提升閾值,T,的值并根據(jù)新的閾值通過(guò),CF-,樹(shù),t1,中各節(jié)點(diǎn)條目重建,CF-,樹(shù),t2,：在重建過(guò)程中，如果,t1,的葉節(jié)點(diǎn)條目是潛在的離群點(diǎn)并且磁盤(pán)仍有空間，則將該離群點(diǎn)寫(xiě)入磁盤(pán)，否則使用該條目重建樹(shù),t2,。整個(gè)樹(shù),t2,建好后，重新將,t2,賦給,t1,。,(,

50、f,)判斷此時(shí)存儲(chǔ)潛在離群點(diǎn)的磁盤(pán)是否已滿(mǎn)，如果沒(méi)有滿(mǎn)則轉(zhuǎn)(,b,)繼續(xù)掃描下一個(gè)數(shù)據(jù)點(diǎn)。如果此時(shí)磁盤(pán)滿(mǎn)了，則將存儲(chǔ)在磁盤(pán)中的潛在離群點(diǎn)重新吸收到,CF-,樹(shù),t1,中，并轉(zhuǎn)轉(zhuǎn)(,b,)繼續(xù)掃描下一個(gè)數(shù)據(jù)點(diǎn)。,,3.5.2 BIRCH算法 (6)其中具體建樹(shù)階段算法步驟如,3.5.3,兩步聚類(lèi)算法,(1),兩步聚類(lèi)(,Two Step Clustering,)算法是,BIRCH,算法的一種改進(jìn)。其基本步驟如下：,第一步，預(yù)聚類(lèi),，即先將樣本粗略劃分成,L,個(gè)簇。該步驟讀入一個(gè)樣本數(shù)據(jù)后，根據(jù)“親疏程度”或“相似性”決定該樣本應(yīng)派生出一個(gè)新簇，還是應(yīng)合并到已有的某個(gè)子簇中。這個(gè)過(guò)程反復(fù)進(jìn)行，最終

51、形成,L,個(gè)簇。,第二步，聚類(lèi),。即在預(yù)聚類(lèi)的基礎(chǔ)上，再根據(jù)“親疏程度”決定哪些子簇可以合并，最終形成,M,`,個(gè)簇。,,,,3.5.3 兩步聚類(lèi)算法 (1)兩步聚類(lèi)(Two Step,3.5.3,兩步聚類(lèi)算法,(3),3.5.3.1,兩步聚類(lèi)算法的特點(diǎn),兩步聚類(lèi)的特點(diǎn)包括：既可以處理數(shù)值型變量，也可以處理分類(lèi)型變量；能夠根據(jù)一定準(zhǔn)則確定簇?cái)?shù)目；通過(guò)兩步實(shí)現(xiàn)數(shù)據(jù)聚類(lèi)。,,3.5.3.2,兩步聚類(lèi)的“親疏程度”度量,兩步聚類(lèi)采用距離度量樣本或簇間的“親疏程度”，并依據(jù)距離確定簇的劃分。兩步聚類(lèi)同時(shí)考慮數(shù)值型和分類(lèi)型變量的計(jì)算，如果變量均為數(shù)值型，則采用歐氏距離，否則，采用對(duì)數(shù)似然距離。,,3.5

52、.3.3,簇?cái)?shù)目的確定,簇?cái)?shù)目的確定在第二步聚類(lèi)中完成。采用兩個(gè)階段的策略，第一階段僅給出一個(gè)粗略估計(jì)，第二階段給出一個(gè)恰當(dāng)?shù)淖罱K簇?cái)?shù)目，且兩個(gè)階段的判定標(biāo)準(zhǔn)不同。,,,,3.5.3 兩步聚類(lèi)算法 (3)3.5.3.1 兩步聚類(lèi)算,3.6 SOM,算法 (,1,),3.6.1 SOM,算法中網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),3.6.2 SOM,算法的聚類(lèi)原理,3.6 SOM算法 (1)3.6.1 SOM算法中網(wǎng)絡(luò)的拓?fù)?3.6 SOM,算法 (2),SOM,采用,WTA(Winner Takes All),競(jìng)爭(zhēng)學(xué)習(xí)算法，其聚類(lèi)過(guò)程通過(guò)若干單元對(duì)當(dāng)前單元的競(jìng)爭(zhēng)來(lái)完成，與當(dāng)前單元權(quán)值向量最接近的單元成為贏家或獲勝

53、單元，獲勝神經(jīng)元不但加強(qiáng)自身，且加強(qiáng)周?chē)徑窠?jīng)元，同時(shí)抑制距離較遠(yuǎn)的神經(jīng)元。,SOM,可以在不知道輸入數(shù)據(jù)任何信息結(jié)構(gòu)的情況下，學(xué)習(xí)到輸入數(shù)據(jù)的統(tǒng)計(jì)特征。,3.6 SOM算法 (2) SOM采用WTA(Winner,SOM,中的網(wǎng)絡(luò)采用兩層、前饋式和全鏈接的拓?fù)浣Y(jié)構(gòu),，其網(wǎng)絡(luò)結(jié)構(gòu)如圖,3-5,所示。,該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有以下特點(diǎn)：,,3.,6.1 SOM算法中網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),,輸入單元,X,i,連接權(quán)值,W,ij,輸出層,權(quán)重向量,W,j,輸入層,(,1,)網(wǎng)絡(luò)包含兩層，即一個(gè)輸入層和一個(gè)輸出層或競(jìng)爭(zhēng)層。,(,2,)輸入層的神經(jīng)元個(gè)數(shù)由輸入數(shù)據(jù)的屬性個(gè)數(shù)決定，一個(gè)屬性對(duì)應(yīng)一個(gè)輸入神經(jīng)元，而輸出

54、層則是由輸出層神經(jīng)元按照一定的方式排列在二維平面上，輸出節(jié)點(diǎn)個(gè)數(shù)就是簇個(gè)數(shù)，輸出層的神經(jīng)元個(gè)數(shù)的選取直接影響,SOM,網(wǎng)絡(luò)的性能。,(,3,)網(wǎng)絡(luò)是全連接的，即輸入層中的每個(gè)輸入節(jié)點(diǎn)都與輸出節(jié)點(diǎn)完全相連，這些連接有不同的強(qiáng)度或權(quán)值。,(,4,)輸出節(jié)點(diǎn)呈二維結(jié)構(gòu)分布，且節(jié)點(diǎn)之間具有側(cè)向連接。所以對(duì)某個(gè)輸出節(jié)點(diǎn)來(lái)說(shuō)，在一定鄰域范圍內(nèi)會(huì)有一定數(shù)量的連接節(jié)點(diǎn)，這些連接有不同的權(quán)值，它控制和影響著輸出層神經(jīng)元之間的交互作用。,SOM中的網(wǎng)絡(luò)采用兩層、前饋式和全鏈接的拓?fù)浣Y(jié)構(gòu)，其網(wǎng)絡(luò)結(jié)構(gòu),3.6.2 SOM,算法的聚類(lèi)原理,(1),SOM,算法中的拓?fù)浣Y(jié)構(gòu)很好地模擬了人腦神經(jīng)網(wǎng)絡(luò)的特點(diǎn)和工作機(jī)理。輸入層

55、模擬不同的刺激信號(hào)，輸出層中的每個(gè)節(jié)點(diǎn)模擬為神經(jīng)細(xì)胞。,,SOM,學(xué)習(xí)算法由最優(yōu)匹配神經(jīng)元(競(jìng)爭(zhēng))的選擇和網(wǎng)絡(luò)中權(quán)值的自組織(確定權(quán)值更新鄰域和方式)過(guò)程兩部分組成，這兩部分相輔相成，它們共同作用完成自組織特征映射的學(xué)習(xí)過(guò)程。選擇最優(yōu)匹配神經(jīng)元實(shí)質(zhì)是選擇輸入模式對(duì)應(yīng)的中心神經(jīng)元，每執(zhí)行一次學(xué)習(xí)，,SOM,網(wǎng)絡(luò)中就會(huì)對(duì)外部輸入模式執(zhí)行一次自組織適應(yīng)過(guò)程；其結(jié)果是強(qiáng)化現(xiàn)行模式的映射形態(tài)，弱化以往模式的映射形態(tài)。,3.6.2 SOM算法的聚類(lèi)原理 (1)SOM算法中的拓?fù)浣Y(jié),在,SOM,模型中，每一個(gè)權(quán)值的有序序列,(p,為網(wǎng)絡(luò)中神經(jīng)元總數(shù),),都可以看作是神經(jīng)網(wǎng)絡(luò)的一種內(nèi)部表示，它是,有序輸入序列

56、 的相對(duì)應(yīng)映象。,,(1),獲勝神經(jīng)元,對(duì)于輸入向量,x,，使用 表示最優(yōu)匹配輸入向量,x,的神經(jīng)元，則可以通過(guò)下列條件決定 ：,這個(gè)條件概括了神經(jīng)元競(jìng)爭(zhēng)的本質(zhì)，滿(mǎn)足這個(gè)條件的神經(jīng)元稱(chēng)為最佳匹配或獲勝神經(jīng)元。,,(2),拓?fù)溧徲?獲勝神經(jīng)元決定興奮神經(jīng)元的拓?fù)溧徲蚩臻g位置，一個(gè)獲勝神經(jīng)元傾向于激活它緊接的鄰域內(nèi)神經(jīng)元而不是隔得遠(yuǎn)的神經(jīng)元，這導(dǎo)致對(duì)獲勝神經(jīng)元的拓?fù)溧徲虻膫?cè)向距離可以光滑地縮減。,,,,,,3.6.2 SOM,算法的聚類(lèi)原理,(2),在SOM模型中，每一個(gè)權(quán)值的有序序列,(3),權(quán)值更新與學(xué)習(xí)率參數(shù),

57、對(duì)于獲勝神經(jīng)元,i,的拓?fù)溧徲蚶锏纳窠?jīng)元，按以下方式更新權(quán)值：,,這里 為學(xué)習(xí)率參數(shù)，它隨時(shí)間的增加單調(diào)下降，一種選擇就是：,,,這里 是另一個(gè)時(shí)間常數(shù)。學(xué)習(xí)率參數(shù) 也可以選擇線性下降函,數(shù)。,,,,,3.6.2 SOM,算法的聚類(lèi)原理,(3),(3) 權(quán)值更新與學(xué)習(xí)率參數(shù)3.6.2 SOM算法的聚類(lèi)原理,3.7,聚類(lèi)算法評(píng)價(jià),(1),好的聚類(lèi)方法產(chǎn)生高質(zhì)量的簇，即簇內(nèi)的對(duì)象具有高的相似度和不同簇之間具有低的相似度。由于存在大量不同類(lèi)型的聚類(lèi)算法，而每種聚類(lèi)算法可能都定義了自己的簇類(lèi)型，每種情況都可能需要一種不同的評(píng)估度量。,傳統(tǒng)的用于評(píng)估簇的度量有兩類(lèi)：監(jiān)督的度量和非

58、監(jiān)督的度量。,,3.7.1,監(jiān)督度量,監(jiān)督度量，也稱(chēng)外部質(zhì)量評(píng)價(jià)準(zhǔn)則,，是基于一個(gè)已經(jīng)存在的人工分類(lèi)數(shù)據(jù)集(已知每個(gè)對(duì)象的類(lèi)別)進(jìn)行評(píng)價(jià)的，這樣可以將聚類(lèi)輸出結(jié)果直接與之進(jìn)行比較。外部質(zhì)量評(píng)價(jià)準(zhǔn)則與聚類(lèi)算法無(wú)關(guān)，理想的聚類(lèi)結(jié)果是具有相同類(lèi)別的數(shù)據(jù)被聚集到相同的簇中，具有不同類(lèi)別的數(shù)據(jù)聚集在不同的簇中。,,3.7 聚類(lèi)算法評(píng)價(jià) (1)好的聚類(lèi)方法產(chǎn)生高質(zhì)量的簇，即簇,3.7,聚類(lèi)算法評(píng)價(jià),(2),1,)聚類(lèi)熵,聚類(lèi)熵越小，聚類(lèi)效果越好。,類(lèi)似于信息熵，考慮簇中不同類(lèi)別數(shù)據(jù)的分布。對(duì)于簇,,Ci,，聚類(lèi)熵,,定義為：,,整體聚類(lèi)熵,定義為所有聚類(lèi)熵的加權(quán)平均值：,,,(,2,)聚類(lèi)精度,基本出發(fā)點(diǎn)

59、是使用簇中數(shù)目最多的類(lèi)別作為該簇的類(lèi)別標(biāo)記。對(duì)于簇,,Ci,，聚類(lèi)精度,,定義為：,,整體聚類(lèi)精度,,定義為所有聚類(lèi)精度的加權(quán)平均值：,,,,,,,,3.7 聚類(lèi)算法評(píng)價(jià) (2)1)聚類(lèi)熵,3.7,聚類(lèi)算法評(píng)價(jià),(1),3.7.2,非監(jiān)督度量,非監(jiān)督度量，也稱(chēng)內(nèi)部質(zhì)量評(píng)估準(zhǔn)則,，該類(lèi)方法不使用對(duì)象的類(lèi)別信息。非監(jiān)督簇評(píng)估度量與聚類(lèi)算法類(lèi)型有關(guān)，如凝聚度和分離度僅用于劃分的簇集合，而共性分離相關(guān)系數(shù)用于層次聚類(lèi)。這里介紹共性分離相關(guān)系數(shù)。,,共性分離相關(guān)系數(shù)(,CoPhenetic Correlation Coefficient,，簡(jiǎn)稱(chēng),CPCC,)用于層次聚類(lèi)的評(píng)估。兩個(gè)對(duì)象之間的共性分離距離

60、(,cophenetic distance,)是凝聚層次聚類(lèi)算法首次將對(duì)象放在同一個(gè)簇時(shí)的鄰近度。例如，在凝聚層次聚類(lèi)過(guò)程的某個(gè)時(shí)刻，兩個(gè)合并的簇之間的最小距離為,0.1,，則一個(gè)簇中的所有點(diǎn)關(guān)于另一個(gè)簇的各點(diǎn)的共性分離距離都是,0.1,。在共性分離距離矩陣中，項(xiàng)是每對(duì)對(duì)象之間的共性分離距離。共性分離相關(guān)系數(shù)是該矩陣與原來(lái)的相異度矩陣的項(xiàng)的相關(guān)度，是層次聚類(lèi)對(duì)數(shù)據(jù)擬合程度的標(biāo)準(zhǔn)度量。該度量常用于評(píng)估層次聚類(lèi)算法之間的質(zhì)量對(duì)比。,,3.7 聚類(lèi)算法評(píng)價(jià) (1)3.7.2 非監(jiān)督度量,3.8,綜合例子,本例的目的是通過(guò)對(duì)超市客戶(hù)個(gè)人信息的聚類(lèi)分析，發(fā)現(xiàn)客戶(hù)群的特征，以實(shí)現(xiàn)對(duì)目標(biāo)客戶(hù)的準(zhǔn)確理解和客

61、戶(hù)定位，便于后期針對(duì)不同特點(diǎn)的客戶(hù)采用不同的營(yíng)銷(xiāo)策略。,數(shù)據(jù)來(lái)源于美國(guó)一家大型連鎖會(huì)員制超市,Food Mart,，該超市擁有巨大的客戶(hù)數(shù)量，而且記錄了客戶(hù)的個(gè)人信息。使用客戶(hù)信息表,customer,進(jìn)行分析，,customer,共有,10281,條記錄，這些個(gè)人信息包括客戶(hù)編號(hào)、賬戶(hù)編號(hào)、姓名、地址、城市、郵政編號(hào)、電話、生日、婚姻狀態(tài)、年收入、性別、孩子數(shù)量、教育水平等,28,個(gè)屬性。,表,3-7,客戶(hù)細(xì)分屬性選擇,序 號(hào),屬 性,屬 性 描 述,數(shù) 據(jù) 類(lèi) 型,1,Marital_status,婚姻狀態(tài),二元變量,2,Yearly_income,年收入,標(biāo)稱(chēng)變量,3,Gen

62、der,性別,二元變量,4,Total_children,孩子數(shù)量,區(qū)間標(biāo)度變量,5,Num_child_at_home,在家的孩子數(shù)量,區(qū)間標(biāo)度變量,6,Education,教育水平,標(biāo)稱(chēng)變量,7,Member_card,會(huì)員卡類(lèi)型,標(biāo)稱(chēng)變量,8,Occupation,職業(yè),標(biāo)稱(chēng)變量,9,Houseowner,是否有房子,二元變量,10,Num_cars_owned,擁有的汽車(chē)數(shù)量,區(qū)間標(biāo)度變量,3.8 綜合例子本例的目的是通過(guò)對(duì)超市客戶(hù)個(gè)人信息的聚類(lèi)分析,3.9,本章小結(jié),聚類(lèi)分析,是最基本的數(shù)據(jù)分析工具，可用于發(fā)現(xiàn)復(fù)雜數(shù)據(jù)的結(jié)構(gòu)，對(duì)數(shù)據(jù)進(jìn)行探索性分析。一旦聚類(lèi)分析找到了不同的簇，就能用分

63、類(lèi)等其他工具來(lái)發(fā)現(xiàn)不同簇之間的規(guī)律和模式。在市場(chǎng)或客戶(hù)細(xì)分、高價(jià)值客戶(hù)的發(fā)現(xiàn)等方面具有廣泛用途。,聚類(lèi)算法依賴(lài)于屬性或?qū)ο笾g的相似性度量，因而本章首先介紹數(shù)據(jù)的相似性度量。在此基礎(chǔ)上，對(duì)聚類(lèi)分析的經(jīng)典方法，包括劃分方法,(K-MEANS,、一趟聚類(lèi)算法,),、層次方法,(BIRCH,、兩步聚類(lèi),),、神經(jīng)網(wǎng)絡(luò)聚類(lèi)方法的原理進(jìn)行了介紹，并通過(guò)實(shí)例對(duì)這些經(jīng)典算法的使用進(jìn)行說(shuō)明。,3.9 本章小結(jié)聚類(lèi)分析是最基本的數(shù)據(jù)分析工具，可用于發(fā)現(xiàn)復(fù),作業(yè)：,P61,：,3.1,3.4,3.5,3.6,作業(yè)：P61：3.1,3.4,3.5,3.6,此課件下載可自行編輯修改，此課件供參考！,部分內(nèi)容來(lái)源于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)與我聯(lián)系刪除！感謝你的觀看！,此課件下載可自行編輯修改，此課件供參考！,