商務(wù)數(shù)據(jù)挖掘與應(yīng)用案例分析課件

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

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

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

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

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

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

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

7、計學(xué)與模式分析，金融分析，市場營銷，決策支持，信息檢索，,WEB,挖掘，網(wǎng)絡(luò)安全，圖象處理，地質(zhì)勘探、城市規(guī)劃，土地使用、空間數(shù)據(jù)分析，生物學(xué)，天文學(xué)，心理學(xué)，考古學(xué)等。,3.1 概述 (3)聚類分析的應(yīng)用,3.1,概述 (,4,),典型聚類方法簡介,劃分方法,：基于質(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ò),其他聚類方法,：譜聚類算法,(spectral clustering),、蟻群聚類算法等,3.1 概述 (4)典型聚類方法簡介,3.2,相似性度量,3.2.1,數(shù)據(jù)及數(shù)據(jù)類型,3.2.2,屬性之間的相似性度量,3.2.3,對象之間的相似性度量,3.2 相似性度量3.2.1 數(shù)據(jù)及數(shù)據(jù)類型,7,3.2.1,數(shù)據(jù)及數(shù)據(jù)類型 (1),相關(guān)概念,(1),數(shù)據(jù),狹義：,數(shù)字,廣義：,數(shù)據(jù)對象及其屬性的集合，其表現(xiàn)形式可以是數(shù)字、符號、文字、圖像抑或是計算機代碼等

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

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

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

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

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

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

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

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

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

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

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

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

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

22、方式有：,① 采用負(fù)指數(shù)函數(shù)將距離轉(zhuǎn)換為相似性度量,s,，即：,,②,采用距離的倒數(shù)作為相似性度量，即：,分母上加,1,是為了避免分母為,0,時出現(xiàn)錯誤。,,③,若距離在,0,～,1,之間，可采用與,1,的差作為相似系數(shù)，即：,,,3.2.3,對象之間的相似性度量 (,11,),,,,,,,,,,(4)由距離度量轉(zhuǎn)換而來的相似性度量3.2.3 對象之間的相,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,提出的，迄今為止，很多聚類任務(wù)都選擇該經(jīng)典算法。其核心思想是找出,K,個簇中心,,，使得每一個數(shù)據(jù)點,,到其最近的簇中心,,的平方距離和被最小化。,k-means,聚類算法的形式化描述如下：,(1),從數(shù)據(jù)集,D,中任意選擇,k,個對象作為初始簇中心；,(2) repeat,(3) for,數(shù)據(jù)集,D,中每個對象,P do,(4),計算對象,P,到,k,個簇中心的距離,(5),將對象,P,指派到與其最近,(,距離最短,),的簇；,(6) end for,(7),計算每個簇中對象的均值，做為新的簇的中心；,(8) until k,個簇的簇中心不再發(fā)

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

25、法不能正確識別，原因在于它們所采用的簇的表示及簇間相似性度量不能反映這些自然簇的特征；,(,5,)只能用于處理數(shù)值屬性的數(shù)據(jù)集，不能處理包含分類屬性的數(shù)據(jù)集。,3.3,.1,K-means,算法(,2,),,,圖,3-1,基于質(zhì)心的劃分方法不能識別的數(shù)據(jù)示例,k-means描述容易、實現(xiàn)簡單、快速，但存在如下不足：3.,例,3-1,對表,3-4,中二維數(shù)據(jù)，使用,k-means,算法將其劃分為,2,個簇，假設(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,聚類過程示例數(shù)據(jù)集,解：圖,3-2,顯示了對于給定的數(shù)據(jù)集,k-means,聚類算法的執(zhí)行過程。,,圖,3-2 k-means,算法聚類過程示例,例3-1 對表3-4中二維數(shù)據(jù)，使用k-means算法將其,(,1,)根據(jù)題目，假設(shè)劃分的兩個簇分別為,C,1,和,C,2,，初始中心分別為(,4,，,5,)和(,5,，,5,)，下面計算,10,個樣本到這,2,個簇中心的距離，并將,10,個樣本指派到與其最近的簇：,(,2,)第一輪迭代結(jié)果如下：,屬于簇,C,1,的樣本有：,{P7,，,

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

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

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

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

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

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

33、),(3)對象p與簇C間的距離 定義為p與,(4),簇,C,1,與,C,2,間的距離 定義為兩個簇的摘要間的距離：,,這里 為 與 在屬性 上的距離，對于分類屬性 其值定義為 中每個對象與 中每個對象的差異的平均值：,,,對于數(shù)值屬性 其值定義為,,在定義,3-3,的,(2),中，當(dāng),x=1,時，相當(dāng)于曼哈頓,(Manhattan),距離，當(dāng),x=2,時，相當(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,及兩個簇,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)聚類算法中的距離定義，就可

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

37、ary,算法將其劃分為,2,個簇，并選擇記錄,3,和,5,分別為每個簇的初始對象。,$_,年收入為年收入列規(guī)范化后的結(jié)果。,,表,3-5,某銀行拖欠貸款數(shù)據(jù),3.3,.2,K-means,算法的改進(jìn)(8),序號,是否有房,婚姻狀況,年收入,$_,年收入,拖欠貸款,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 對于表3-5所示的數(shù)據(jù)集，請使用k-summary,3.3,一趟聚類算法,現(xiàn)有聚類算法的普遍存在以下不足：,對于大規(guī)模數(shù)據(jù)集，聚類時效性和準(zhǔn)確性難以滿足要求；,難以直接處理混合屬性的數(shù)據(jù)；,聚類結(jié)果依賴于參數(shù)，而參數(shù)的選擇主要靠經(jīng)驗或試探，沒有簡單、通用的方法。,3.3 一趟聚類算法 現(xiàn)有聚類算法的普遍存在以下不足：,一趟聚類算法采用摘要信息,CSI,表示一個簇,，及定義,3-3,來度量距離，其將數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、單元，獲勝神經(jīng)元不但加強自身，且加強周圍鄰近神經(jīng)元，同時抑制距離較遠(yuǎn)的神經(jīng)元。,SOM,可以在不知道輸入數(shù)據(jù)任何信息結(jié)構(gòu)的情況下，學(xué)習(xí)到輸入數(shù)據(jù)的統(tǒng)計特征。,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)有以下特點：,,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ò)包含兩層，即一個輸入層和一個輸出層或競爭層。,(,2,)輸入層的神經(jīng)元個數(shù)由輸入數(shù)據(jù)的屬性個數(shù)決定，一個屬性對應(yīng)一個輸入神經(jīng)元，而輸出

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

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

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

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

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

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

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

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

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

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