第3章聚類分析

商務(wù)數(shù)據(jù)挖掘與應(yīng)用案例分析第3章聚類分析

3.1概述>>

3.2相似性度量>>

3.3k-means算法及其改進(jìn)>>3.4一趟聚類算法>>3.5層次聚類算法>>3.6神經(jīng)網(wǎng)絡(luò)方法>>3.7聚類算法評(píng)價(jià)>>3.8綜合例子>>開篇案例——百思買的客戶分群百思買(BestBuy)作為美國(guó)最大的家電及IT零售連鎖商，其客戶細(xì)分戰(zhàn)略(CustomerCentricity)是其經(jīng)營(yíng)及商店定位的重要組成部分。百思買將其中心客戶分為5種類型，巴利(Barry)，巴茨(Buzz)，雷(Ray)，店門(StoreFront)，吉兒(Jill)。巴利是對(duì)技術(shù)很精通的顧客，吉兒是忙于接送小孩參加各種市區(qū)文體活動(dòng)的住在郊區(qū)的媽媽，巴茨是熱衷于新玩意兒的潮族，雷是對(duì)價(jià)格敏感的工薪族，店門則擁有一家小企業(yè)。除5種核心客戶之外，還有單身年輕女士凱莉(Carrie)和空巢一族海倫及查理(Helen，Charlie)等，也是百思買感興趣的客戶類型。百思買結(jié)合銷售數(shù)據(jù)(含會(huì)員卡)以及人口分布數(shù)據(jù)，來確認(rèn)每個(gè)商店是否需要側(cè)重于某個(gè)客戶群。在其300個(gè)店中，就有40個(gè)專門定位于巴利型客戶，并進(jìn)行了重新布局，在這類店中可以看到單獨(dú)的家庭影院店中店，資深銷售，以及便攜設(shè)備專家；吉兒型店的特色導(dǎo)購(gòu)員可以幫主婦選擇合適的數(shù)碼產(chǎn)品；而巴茨店則有大量的電子游戲商品。同一個(gè)店可以側(cè)重于多個(gè)客戶類型，比如吉兒型和巴利型就經(jīng)常被作為同一個(gè)店的定位。每個(gè)店的定位確定之后，相應(yīng)的布局，存貨，人員等，即可相應(yīng)進(jìn)行調(diào)整優(yōu)化。(資料來源：)利用顧客的消費(fèi)行為和人口特征對(duì)客戶分群是市場(chǎng)營(yíng)銷中的重要手段。如何對(duì)客戶進(jìn)行有效分群是聚類分析的重要研究?jī)?nèi)容。3.1概述(1)類間相似度最小化(距離最大化)類內(nèi)相似度最大化(距離最小化)簡(jiǎn)單地描述，聚類(Clustering)是將數(shù)據(jù)集劃分為若干相似對(duì)象組成的多個(gè)組(group)或簇(cluster)的過程，使得同一組中對(duì)象間的相似度最大化，不同組中對(duì)象間的相似度最小化。或者說一個(gè)簇(cluster)就是由彼此相似的一組對(duì)象所構(gòu)成的集合，不同簇中的對(duì)象通常不相似或相似度很低。3.1概述(2)從機(jī)器學(xué)習(xí)的角度看，聚類是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法，即事先對(duì)數(shù)據(jù)集的分布沒有任何的了解，它是將物理或抽象對(duì)象的集合組成為由類似的對(duì)象組成的多個(gè)類的過程。聚類方法的目的是尋找數(shù)據(jù)中：潛在的自然分組結(jié)構(gòu)和感興趣的關(guān)系。聚類分析中“簇”的特征：聚類所說的簇不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分；聚的數(shù)目和結(jié)構(gòu)都沒有事先假定。3.1概述(3)聚類分析的應(yīng)用聚類分析正在蓬勃發(fā)展，廣泛應(yīng)用于一些探索性領(lǐng)域,如統(tǒng)計(jì)學(xué)與模式分析，金融分析，市場(chǎng)營(yíng)銷，決策支持，信息檢索，WEB挖掘，網(wǎng)絡(luò)安全，圖象處理，地質(zhì)勘探、城市規(guī)劃，土地使用、空間數(shù)據(jù)分析，生物學(xué)，天文學(xué)，心理學(xué)，考古學(xué)等。3.1概述(4)典型聚類方法簡(jiǎn)介劃分方法：基于質(zhì)心(K-means)、中心的劃分方法層次的方法(hierarchicalmethods)：BIRCH、ROCK、CURE基于密度的方法：

DBSCAN、

OPTICS基于圖的方法：Chameleon、SNN基于網(wǎng)格的方法(grid-basedmethods)：

STING、WaveCluster、CLIQUE基于模型的方法(model-basedmethods)：EM、

COBWEB、神經(jīng)網(wǎng)絡(luò)其他聚類方法：譜聚類算法(spectralclustering)、蟻群聚類算法等3.2相似性度量3.2.1數(shù)據(jù)及數(shù)據(jù)類型3.2.2屬性之間的相似性度量3.2.3對(duì)象之間的相似性度量83.2.1數(shù)據(jù)及數(shù)據(jù)類型(1)相關(guān)概念(1)數(shù)據(jù)狹義：數(shù)字廣義：數(shù)據(jù)對(duì)象及其屬性的集合，其表現(xiàn)形式可以是數(shù)字、符號(hào)、文字、圖像抑或是計(jì)算機(jī)代碼等等。(2)屬性也稱為特征、維或字段，是指一個(gè)對(duì)象的某方面性質(zhì)或特性。一個(gè)對(duì)象通過若干屬性來刻畫。3.2.1數(shù)據(jù)及數(shù)據(jù)類型(2)不同的屬性類型屬性類型描述例子操作分類的(定性的)標(biāo)稱其屬性值只提供足夠的信息以區(qū)分對(duì)象。這種屬性值沒有實(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ū)間其屬性值之間的差是有意義的。日歷日期、攝氏溫度均值、標(biāo)準(zhǔn)差、皮爾遜相關(guān)比率其屬性值之間的差和比率都是有意義的。長(zhǎng)度、時(shí)間和速度幾何平均、調(diào)和平均、百分比變差10屬性包含電信客戶信息的樣本數(shù)據(jù)集客戶編號(hào)客戶類別行業(yè)大類通話級(jí)別通話總費(fèi)用…N22011002518大客戶采礦業(yè)和一般制造業(yè)市話16352…業(yè)客戶批發(fā)和零售業(yè)市話＋國(guó)內(nèi)長(zhǎng)途(含國(guó)內(nèi)IP)27891…N22004895555商業(yè)客戶批發(fā)和零售業(yè)市話＋國(guó)際長(zhǎng)途(含國(guó)際IP)63124…3221026196大客戶科學(xué)教育和文化衛(wèi)生市話＋國(guó)際長(zhǎng)途(含國(guó)際IP)53057…客戶房地產(chǎn)和建筑業(yè)市話＋國(guó)際長(zhǎng)途(含國(guó)際IP)80827…︰︰︰︰︰…對(duì)象3.2.1數(shù)據(jù)及數(shù)據(jù)類型(3)例子：包含電信客戶信息的樣本數(shù)據(jù)集113.2.1數(shù)據(jù)及數(shù)據(jù)類型(4)數(shù)據(jù)集可以看作具有相同屬性的數(shù)據(jù)對(duì)象的集合。在數(shù)據(jù)挖掘領(lǐng)域，關(guān)于數(shù)據(jù)集有三個(gè)方面的問題需要考慮：維度、稀疏性和分辨率。(1)維度(Dimensionality)指數(shù)據(jù)集中的對(duì)象具有的屬性個(gè)數(shù)總和。維歸約(2)稀疏性(Sparsity)指在某些數(shù)據(jù)集中，有意義的數(shù)據(jù)非常少，對(duì)象在大部分屬性上的取值為0；非零項(xiàng)不到1%。文本數(shù)據(jù)集(3)分辨率(Resolution)不同分辨率下數(shù)據(jù)的性質(zhì)不同123.2.2屬性之間的相似性度量簡(jiǎn)單屬性間的相似度和相異度兩個(gè)屬性相似程度的數(shù)值度量，兩個(gè)屬性越相似，它們的相似度就越高。相異度與相似度相反。不同類型的屬性使用的相似性度量是不同的。133.2.3對(duì)象之間的相似性度量(1)對(duì)象之間的相似性度量，即多個(gè)屬性整體的相似性度量方法。對(duì)象之間的相似度計(jì)算涉及描述對(duì)象的屬性類型，需要將不同屬性上的相似度整合成一個(gè)總的相似度來表示。相似性度量方法包括：距離度量和相似系數(shù)。 假定使用m個(gè)屬性來描述數(shù)據(jù)記錄，將每條記錄看成m維空間中的一個(gè)點(diǎn)，距離越小、相似系數(shù)越大的記錄之間的相似程度越大。這里分三種情況來描述：(1)所有屬性是數(shù)值型的；(2)所有屬性都是二值屬性的；(3)同時(shí)包含有分類屬性和數(shù)值屬性的混合屬性。(1)數(shù)值屬性相似性度量1)距離度量(a)閔可夫斯基(Minkowski)距離x=1,城市塊(曼哈頓)距離x=2,歐幾里得距離x=∞,切比雪夫(Chebyshev)距離3.2.3對(duì)象之間的相似性度量(2)15Minkowski距離計(jì)算例子DistanceMatrix3.2.3對(duì)象之間的相似性度量(3)163.2.3對(duì)象之間的相似性度量(4)Canberra距離是由Lance和Williams最早提出的，定義如下：Canberra距離或Lance距離可以看成一種相對(duì)曼哈頓距離，它克服了Minkowski距離受量綱影響的缺點(diǎn)Canberra距離對(duì)缺省值是穩(wěn)健的，當(dāng)兩個(gè)坐標(biāo)都接近0時(shí)，Canberra距離對(duì)微小的變化很敏感。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)化后的夾角余弦，取值范圍在區(qū)間[-1，1]內(nèi)。它表示兩個(gè)向量的線性相關(guān)程度。3.2.3對(duì)象之間的相似性度量(5)(c)廣義Jaccard系數(shù)廣義Jaccard系數(shù)又稱為Tanimoto系數(shù)，用EJ表示，取值范圍在區(qū)間[0，1]內(nèi)。廣泛用于信息檢索和生物學(xué)分類中，在二元屬性情況下簡(jiǎn)化為Jaccard系數(shù)。3.2.3對(duì)象之間的相似性度量(6)(2)二值屬性的相似性度量一個(gè)二值屬性變量(binaryvariable)只有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

10合計(jì)1n11n10n11+n100n01n00N01+n00合計(jì)n11+n01n10+n00

二值屬性相似性存在對(duì)稱的和不對(duì)稱兩種情況。如果二值屬性的兩個(gè)狀態(tài)值所表示的內(nèi)容同等重要，則是對(duì)稱的，否則為不對(duì)稱。如，給定變量smoker，它描述一個(gè)病人是否吸煙的情況，用0或1進(jìn)行編碼來表示一個(gè)病人吸煙狀態(tài)是同等重要的，因此smoker是對(duì)稱變量?；趯?duì)稱二值變量所計(jì)算的相似度稱為不變相似性(即變量編碼的改變不會(huì)影響計(jì)算結(jié)果)。對(duì)于不變相似性，常用簡(jiǎn)單匹配相關(guān)系數(shù)來描述對(duì)象p和q之間的差異程度，其定義為：對(duì)于不對(duì)稱的二值變量，如果取值1比0重要，那么這樣的二值變量就只有一種狀態(tài)。例如，屬性disease的檢測(cè)結(jié)果是陽(yáng)性或陰性，這兩個(gè)結(jié)果的重要性是不一樣的，通常將少見而重要的情況用1表示(如HIV陽(yáng)性)，將不重要情況用0表示。這種情況下對(duì)象p和q之間的差異程度評(píng)價(jià)通常采用Jaccard系數(shù)，其定義為：3.2.3對(duì)象之間的相似性度量(8)(3)混合屬性相似性度量在實(shí)際應(yīng)用中，數(shù)據(jù)對(duì)象往往包含多種類型的屬性，因此使用混合類型的屬性描述。這需要將不同類型的屬性差異度組合成一個(gè)整體，把所有屬性間的差異轉(zhuǎn)換到區(qū)間[0，

1]中。假設(shè)數(shù)據(jù)集包含m個(gè)不同類型的屬性，對(duì)象p和q之間的差異度推廣Minkowski距離，定義為:3.2.3對(duì)象之間的相似性度量(9)對(duì)象p和q在屬性f上的相異度

根據(jù)其屬性類型不同進(jìn)行相應(yīng)計(jì)算：(a)若屬性f

為二元屬性或標(biāo)稱屬性，則：如果

，那么

，否則

。(b)若屬性f

為序數(shù)型屬性，計(jì)算對(duì)象p和對(duì)象q在屬性f上的秩(或等級(jí))

和

，

。(c)若屬性f

為區(qū)間標(biāo)度屬性，則

，

、

分別表示屬性f

的最大值和最小值。(d)若屬性f

為比率數(shù)值屬性，則通過變換轉(zhuǎn)換為區(qū)間標(biāo)度屬性來處理。這樣，當(dāng)描述對(duì)象的屬性是不同類型時(shí)，對(duì)象之間的相異度也能夠計(jì)算，且取值在[0，1]區(qū)間。3.2.3對(duì)象之間的相似性度量(10)(4)由距離度量轉(zhuǎn)換而來的相似性度量可以通過一個(gè)單調(diào)遞減函數(shù)，將距離轉(zhuǎn)換成相似性度量，相似性度量的取值一般在區(qū)間[0，1]之間，值越大，說明兩個(gè)對(duì)象越相似。常用的方式有：①采用負(fù)指數(shù)函數(shù)將距離轉(zhuǎn)換為相似性度量s，即：②采用距離的倒數(shù)作為相似性度量，即：分母上加1是為了避免分母為0時(shí)出現(xiàn)錯(cuò)誤。③若距離在0～1之間，可采用與1的差作為相似系數(shù)，即：

3.2.3對(duì)象之間的相似性度量(11)3.3k-means算法及其改進(jìn)3.3.1k-means算法3.3.2k-means算法的改進(jìn)3.3.1K-means算法(1)K-means算法是1967年由MacQueen提出的，迄今為止，很多聚類任務(wù)都選擇該經(jīng)典算法。其核心思想是找出K個(gè)簇中心

，使得每一個(gè)數(shù)據(jù)點(diǎn)

到其最近的簇中心

的平方距離和被最小化。k-means聚類算法的形式化描述如下：(1)從數(shù)據(jù)集D中任意選擇k個(gè)對(duì)象作為初始簇中心；(2)repeat(3)for數(shù)據(jù)集D中每個(gè)對(duì)象Pdo(4)計(jì)算對(duì)象P到k個(gè)簇中心的距離(5)將對(duì)象P指派到與其最近(距離最短)的簇；(6)endfor(7)計(jì)算每個(gè)簇中對(duì)象的均值，做為新的簇的中心；(8)untilk個(gè)簇的簇中心不再發(fā)生變化k-means算法中用如<n，Mean>來表示一個(gè)簇。k-means描述容易、實(shí)現(xiàn)簡(jiǎn)單、快速，但存在如下不足：(1)簇個(gè)數(shù)k需要預(yù)先指定，但實(shí)際上難以確定；(2)算法對(duì)初始值的選取依賴性極大以及算法常陷入局部最優(yōu)解；(3)由于簇的質(zhì)心(即均值)作為簇中心進(jìn)行新一輪聚類計(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劃分方法不能正確識(shí)別，原因在于它們所采用的簇的表示及簇間相似性度量不能反映這些自然簇的特征；(5)只能用于處理數(shù)值屬性的數(shù)據(jù)集，不能處理包含分類屬性的數(shù)據(jù)集。3.3.1K-means算法(2)圖3-1基于質(zhì)心的劃分方法不能識(shí)別的數(shù)據(jù)示例例3-1對(duì)表3-4中二維數(shù)據(jù)，使用k-means算法將其劃分為2個(gè)簇，假設(shè)初始簇中心選為P7(4，5)，P10(5，5)。3.3.1K-means算法(3)

P1P2P3P4P5P6P7P8P9P10x3374384475y4637855145表3-4

k-means聚類過程示例數(shù)據(jù)集解：圖3-2顯示了對(duì)于給定的數(shù)據(jù)集k-means聚類算法的執(zhí)行過程。圖3-2k-means算法聚類過程示例(1)根據(jù)題目，假設(shè)劃分的兩個(gè)簇分別為C1和C2，初始中心分別為(4，5)和(5，5)，下面計(jì)算10個(gè)樣本到這2個(gè)簇中心的距離，并將10個(gè)樣本指派到與其最近的簇：(2)第一輪迭代結(jié)果如下：屬于簇C1的樣本有：{P7，P1，P2，P4，P5，P8}屬于簇C2的樣本有：{P10，P3，P6，P9}重新計(jì)算新的簇中心，得到：C1的中心為(3.5，5.167)，C2的中心為(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.5，3.25)(4)繼續(xù)計(jì)算10個(gè)樣本到兩個(gè)新的簇中心的距離，重新分配到新的簇中，發(fā)現(xiàn)簇中心不再發(fā)生變化，算法終止。3.3.1K-means算法(4)3.3.2K-means算法的改進(jìn)(1)k-means算法中距離的計(jì)算基于數(shù)值型數(shù)據(jù)，沒有說明對(duì)于分類型數(shù)據(jù)如何處理。此外，它對(duì)于噪聲和離群點(diǎn)數(shù)據(jù)敏感。介紹k-means聚類算法的一些改進(jìn)策略，它們?cè)诔跏即貢r(shí)對(duì)象的選擇、相似度的計(jì)算方法或簇中心的計(jì)算方法等不同。下面介紹三種k-means算法的改進(jìn)方法：(1)將分類型數(shù)據(jù)轉(zhuǎn)化為數(shù)值型數(shù)據(jù)，再利用k-means算法進(jìn)行聚類分析。(2)適用于純分類屬性數(shù)據(jù)集的k-modes算法和適用于混合屬性數(shù)據(jù)集的k-prototypes算法。k-modes算法采用mode(取值頻率最大的屬性值，即眾數(shù))來表示分類屬性，在聚類過程中使用簡(jiǎn)單匹配來度量分類屬性的不相似性(dissimilarity)。將k-modes算法和k-means結(jié)合到一起形成了k-prototypes算法，用來處理具有混合屬性的數(shù)據(jù)集。(3)適用于混合屬性數(shù)據(jù)集的K-Summary算法，它使用簇的摘要信息表示簇的質(zhì)心。數(shù)據(jù)往往具有混合屬性的特點(diǎn)，這里介紹一種簡(jiǎn)單的聚類表示方法，并對(duì)閔可夫斯基(Minkowski)距離進(jìn)行推廣以使聚類算法可以有效處理包含分類屬性的數(shù)據(jù)。假設(shè)數(shù)據(jù)集D有m個(gè)屬性，其中有

個(gè)分類屬性和

個(gè)數(shù)值屬性，

，設(shè)分類屬性位于數(shù)值屬性之前，用

表示第i個(gè)屬性取值的集合。定義3-1給定簇C，

，a在C中關(guān)于Di

的頻度定義為C在

Di上的投影中包含a的次數(shù)：

定義3-2給定簇C，C的摘要信息CSI(ClusterSummaryInformation)定義為：

，其中

為C的大小,由分類屬性中不同取值的頻度信息和數(shù)值型屬性的質(zhì)心兩部分構(gòu)成，即：3.3.2K-means算法的改進(jìn)(2)定義3-3給定D的簇C、和,對(duì)象與，x>0。

(1)對(duì)象p，q在屬性i上的差異程度(或距離)定義為：對(duì)于分類屬性或二值屬性，

;對(duì)于連續(xù)數(shù)值屬性或順序?qū)傩?，?2)兩個(gè)對(duì)象p，q間的差異程度(或距離)定義為：

;

3.3.2K-means算法的改進(jìn)(3)(3)對(duì)象p與簇C間的距離定義為p與簇C的摘要之間的距離：這里為p與C在屬性上的距離，對(duì)于分類屬性其值定義為p與C中每個(gè)對(duì)象在屬性上的距離的算術(shù)平均值，即；對(duì)于數(shù)值屬性其值定義為

3.3.2K-means算法的改進(jìn)(4)(4)簇C1與C2間的距離定義為兩個(gè)簇的摘要間的距離：這里為與在屬性上的距離，對(duì)于分類屬性其值定義為中每個(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.2K-means算法的改進(jìn)(5)3.3.2K-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)=(1-25/30)+(1-20/30)+(19-18)=1.5

d(p，C2)=(1-3/15)+(1-0/15)+(24-18)=7.8d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15d(C1,C2)=1-(25*3+5*12)/(30*15)+1-6*1/(30*15)+(24-19)=1003/150≈6.693.3.2K-means算法的改進(jìn)(7)用定義3-3取代相關(guān)聚類算法中的距離定義，就可使原來僅適用于數(shù)值或分類屬性的聚類算法不受數(shù)據(jù)類型的限制而可用于任何數(shù)據(jù)類型。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ù)收斂，如誤差和變化很小或相鄰兩次迭代沒有對(duì)象從一個(gè)簇移動(dòng)到另一個(gè)簇。例3-3對(duì)于表3-5所示的數(shù)據(jù)集，請(qǐng)使用k-summary算法將其劃分為2個(gè)簇，并選擇記錄3和5分別為每個(gè)簇的初始對(duì)象。$_年收入為年收入列規(guī)范化后的結(jié)果。

表3-5某銀行拖欠貸款數(shù)據(jù)3.3.2K-means算法的改進(jìn)(8)序號(hào)是否有房婚姻狀況年收入$_年收入拖欠貸款1yessingle125K0.406no2nomarried100K0.25no3nosingle70K0.063no4yesmarried120K0.375no5nodivorced95K0.219yes6nomarried60K0no7yesdivorced220K1no8nosingle85K0.156yes9nomarried75K0.094no10nosingle90K0.188yes3.3一趟聚類算法現(xiàn)有聚類算法的普遍存在以下不足：對(duì)于大規(guī)模數(shù)據(jù)集，聚類時(shí)效性和準(zhǔn)確性難以滿足要求；難以直接處理混合屬性的數(shù)據(jù)；聚類結(jié)果依賴于參數(shù)，而參數(shù)的選擇主要靠經(jīng)驗(yàn)或試探，沒有簡(jiǎn)單、通用的方法。一趟聚類算法采用摘要信息CSI表示一個(gè)簇，及定義3-3來度量距離，其將數(shù)據(jù)集分割為半徑幾乎相同的超球體(簇)。具體過程如下：(1)初始時(shí)，簇集合為空，讀入一個(gè)新的對(duì)象；(2)以這個(gè)對(duì)象構(gòu)造一個(gè)新的簇；(3)若已到數(shù)據(jù)庫(kù)末尾，則轉(zhuǎn)(5)，否則讀入新對(duì)象，利用給定的距離定義，計(jì)算它與每個(gè)已有簇間的距離，并選擇最小的距離；若最小距離超過給定的半徑閾值r，轉(zhuǎn)(2)；(4)否則將該對(duì)象并入具有最小距離的簇中并更新該簇的各分類屬性值的統(tǒng)計(jì)頻度及數(shù)值屬性的均值，轉(zhuǎn)(3)；(5)結(jié)束。3.4.1

算法描述3.4.2

聚類閾值的選擇策略采用抽樣技術(shù)來計(jì)算閾值范圍，具體描述如下：(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一趟聚類算法聚類過程示例。對(duì)于表3-5的數(shù)據(jù)集，采用一趟聚類算法聚類。EX=43，DX=45，取r=EX，若規(guī)范化年收入屬性，則EX=1.32,DX=0.89,取r=EX。表中$_年收入為年收入規(guī)范化的結(jié)果。

3.5層次聚類算法3.5.1概述3.5.2BIRCH算法3.5.3兩步聚類算法3.5.1概述(1)層次聚類法是一種已得到廣泛使用的經(jīng)典方法，它是通過將數(shù)據(jù)組織為若干組并形成一個(gè)相應(yīng)的樹來進(jìn)行聚類。層次聚類方法可分為自頂向下和自下而上兩種層次聚類。自下而上聚合層次聚類方法(或凝聚層次聚類)。這種自下而上策略就是最初將每個(gè)對(duì)象(自身)作為一個(gè)簇，然后將這些簇進(jìn)行聚合以構(gòu)造越來越大的簇，直到所有對(duì)象均聚合為一個(gè)簇，或滿足一定終止條件為止。絕大多數(shù)層次聚類方法屬于這一類，只是簇間相似度的定義有所不同。自頂向下分解層次聚類方法(或分裂層次聚類)。這種策略的作法與自下而上策略的作法相反。它首先將所有對(duì)象看成一個(gè)簇的內(nèi)容，將其不斷分解以使其變成越來越小但個(gè)數(shù)越來越多的小簇，直到所有對(duì)象均獨(dú)自構(gòu)成一個(gè)簇，或滿足一定終止條件為止。圖3-3兩種不同層次聚類算法3.5.1概述(2)圖3-3描述了一種凝聚層次聚類算法AGENS(AGglomerativeNESting)和一種分裂層次聚類算法DIANA(DIvisiveANAlysis)對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合{a，b，c，d，e}的處理過程。其中從左往右的過程屬于凝聚層次聚類方法：3.5.2BIRCH算法(1)BIRCH算法是一種基于距離的層次聚類算法，其核心是聚類特征CF(ClusterFeature)和聚類特征樹(CF-Tree)，它們用于概括簇描述。這些結(jié)構(gòu)使得BIRCH方法對(duì)增量和動(dòng)態(tài)聚類非常有效。下面詳細(xì)討論聚類特征和聚類特征樹。(1)CF結(jié)構(gòu)聚類特征(CF)是一個(gè)包含聚類信息的三元組，其定義如下：給定一個(gè)簇中的N個(gè)d維的數(shù)據(jù)點(diǎn)：

，這個(gè)簇的聚類特征CF向量是一個(gè)三元組

，其中

N是簇中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，

是N個(gè)數(shù)據(jù)點(diǎn)的線性和(即

)，而

SS是

N個(gè)數(shù)據(jù)點(diǎn)的平方和(即

)。其中線性和反映了聚類的質(zhì)心，平方和反映了簇的直徑大小，它們的作用是計(jì)算平均值和方差。聚類特征具有可加性。例3-5假定在簇中有三個(gè)點(diǎn)(2，5)，(3，2)和(4，3)。的聚類特征是：

CF1=<3，(2+3+4，5+2+3)，(

，)>=<3，(9，10)，(29，28)>假定是與不相交的簇，CF2

=<3，(35，36)，(417，440)>。和合并形成一個(gè)新的簇，其聚類特征便是，即：

CF3=<3+3，(9+35，10+36)，(29+417，38+440)>=<6，(44，46)，(446，478)>3.5.2BIRCH算法(2)(2)CF-樹一個(gè)CF-樹是一個(gè)高度平衡的樹，它具有三個(gè)參數(shù)：非葉節(jié)點(diǎn)CF條目最大個(gè)數(shù)B、葉節(jié)點(diǎn)中CF條目的最大個(gè)數(shù)L和距離閾值T。這些參數(shù)影響結(jié)果樹的大小，其目標(biāo)是通過參數(shù)調(diào)整，將CF樹保存在內(nèi)存中。每個(gè)非葉節(jié)點(diǎn)最多容納B個(gè)形為

的CF條目，

是一個(gè)指向它的第

個(gè)子節(jié)點(diǎn)的指針，

是由這個(gè)

指向的子節(jié)點(diǎn)所代表的子聚類的

。一個(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樹的圖形如圖3-4。3.5.2BIRCH算法(3)3.5.2BIRCH算法(4)CF-樹構(gòu)造過程實(shí)際是一個(gè)數(shù)據(jù)點(diǎn)的插入過程，步驟如下：(a)從根節(jié)點(diǎn)開始遞歸往下，計(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樹。當(dāng)數(shù)據(jù)點(diǎn)無(wú)法插入時(shí)，這個(gè)時(shí)候需要提升閾值T并重建樹來吸收更多的葉節(jié)點(diǎn)條目，直到把所有數(shù)據(jù)點(diǎn)全部插入完畢。3.5.2BIRCH算法(5)(3)BIRCH算法描述BIRCH算法主要分為四個(gè)階段：第一個(gè)階段對(duì)整個(gè)數(shù)據(jù)集進(jìn)行掃描，根據(jù)給定的初始距離閾值T建立一棵初始聚類特征樹；第二階段通過提升閾值T重建CF樹，得到一棵壓縮的CF樹。第三、四階段利用全局聚類算法對(duì)已有的CF樹進(jìn)行聚類得到更好的聚類結(jié)果。3.5.2BIRCH算法(6)其中具體建樹階段算法步驟如下：(a)給定一個(gè)初始的距離閾值T并初始化一棵CF-樹t1。(b)掃描數(shù)據(jù)點(diǎn)并插入到CF-樹t1中。(c)判斷內(nèi)存是否溢出，如果沒有溢出轉(zhuǎn)(d)，如果溢出轉(zhuǎn)(e)。(d)此時(shí)已經(jīng)掃描完所有數(shù)據(jù)點(diǎn)，將存儲(chǔ)在磁盤中的潛在離群點(diǎn)重新吸收到CF-樹t1中，結(jié)束建樹。(e)提升閾值T的值并根據(jù)新的閾值通過CF-樹t1中各節(jié)點(diǎn)條目重建CF-樹t2：在重建過程中，如果t1的葉節(jié)點(diǎn)條目是潛在的離群點(diǎn)并且磁盤仍有空間，則將該離群點(diǎn)寫入磁盤，否則使用該條目重建樹t2。整個(gè)樹t2建好后，重新將t2賦給t1。(f)判斷此時(shí)存儲(chǔ)潛在離群點(diǎn)的磁盤是否已滿，如果沒有滿則轉(zhuǎn)(b)繼續(xù)掃描下一個(gè)數(shù)據(jù)點(diǎn)。如果此時(shí)磁盤滿了，則將存儲(chǔ)在磁盤中的潛在離群點(diǎn)重新吸收到CF-樹t1中，并轉(zhuǎn)轉(zhuǎn)(b)繼續(xù)掃描下一個(gè)數(shù)據(jù)點(diǎn)。3.5.3兩步聚類算法(1)兩步聚類(TwoStepClustering)算法是BIRCH算法的一種改進(jìn)。其基本步驟如下：第一步，預(yù)聚類，即先將樣本粗略劃分成L個(gè)簇。該步驟讀入一個(gè)樣本數(shù)據(jù)后，根據(jù)“親疏程度”或“相似性”決定該樣本應(yīng)派生出一個(gè)新簇，還是應(yīng)合并到已有的某個(gè)子簇中。這個(gè)過程反復(fù)進(jìn)行，最終形成L個(gè)簇。第二步，聚類。即在預(yù)聚類的基礎(chǔ)上，再根據(jù)“親疏程度”決定哪些子簇可以合并，最終形成M`個(gè)簇。3.5.3兩步聚類算法(3)3.5.3.1兩步聚類算法的特點(diǎn)兩步聚類的特點(diǎn)包括：既可以處理數(shù)值型變量，也可以處理分類型變量；能夠根據(jù)一定準(zhǔn)則確定簇?cái)?shù)目；通過兩步實(shí)現(xiàn)數(shù)據(jù)聚類。3.5.3.2兩步聚類的“親疏程度”度量?jī)刹骄垲惒捎镁嚯x度量樣本或簇間的“親疏程度”，并依據(jù)距離確定簇的劃分。兩步聚類同時(shí)考慮數(shù)值型和分類型變量的計(jì)算，如果變量均為數(shù)值型，則采用歐氏距離，否則，采用對(duì)數(shù)似然距離。3.5.3.3簇?cái)?shù)目的確定簇?cái)?shù)目的確定在第二步聚類中完成。采用兩個(gè)階段的策略，第一階段僅給出一個(gè)粗略估計(jì)，第二階段給出一個(gè)恰當(dāng)?shù)淖罱K簇?cái)?shù)目，且兩個(gè)階段的判定標(biāo)準(zhǔn)不同。3.6SOM算法(1)3.6.1SOM算法中網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)3.6.2SOM算法的聚類原理3.6SOM算法(2)SOM采用WTA(WinnerTakesAll)競(jìng)爭(zhēng)學(xué)習(xí)算法，其聚類過程通過若干單元對(duì)當(dāng)前單元的競(jìng)爭(zhēng)來完成，與當(dāng)前單元權(quán)值向量最接近的單元成為贏家或獲勝單元，獲勝神經(jīng)元不但加強(qiáng)自身，且加強(qiáng)周圍鄰近神經(jīng)元，同時(shí)抑制距離較遠(yuǎn)的神經(jīng)元。SOM可以在不知道輸入數(shù)據(jù)任何信息結(jié)構(gòu)的情況下，學(xué)習(xí)到輸入數(shù)據(jù)的統(tǒng)計(jì)特征。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.1SOM算法中網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)輸入單元Xi連接權(quán)值Wij輸出層權(quán)重向量Wj輸入層(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)元，而輸出層則是由輸出層神經(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)來說，在一定鄰域范圍內(nèi)會(huì)有一定數(shù)量的連接節(jié)點(diǎn)，這些連接有不同的權(quán)值，它控制和影響著輸出層神經(jīng)元之間的交互作用。3.6.2SOM算法的聚類原理(1)SOM算法中的拓?fù)浣Y(jié)構(gòu)很好地模擬了人腦神經(jīng)網(wǎng)絡(luò)的特點(diǎn)和工作機(jī)理。輸入層模擬不同的刺激信號(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)值更新鄰域和方式)過程兩部分組成，這兩部分相輔相成，它們共同作用完成自組織特征映射的學(xué)習(xí)過程。選擇最優(yōu)匹配神經(jīng)元實(shí)質(zhì)是選擇輸入模式對(duì)應(yīng)的中心神經(jīng)元，每執(zhí)行一次學(xué)習(xí)，SOM網(wǎng)絡(luò)中就會(huì)對(duì)外部輸入模式執(zhí)行一次自組織適應(yīng)過程；其結(jié)果是強(qiáng)化現(xiàn)行模式的映射形態(tài)，弱化以往模式的映射形態(tài)。在SOM模型中，每一個(gè)權(quán)值的有序序列(p為網(wǎng)絡(luò)中神經(jīng)元總數(shù))都可以看作是神經(jīng)網(wǎng)絡(luò)的一種內(nèi)部表示，它是有序輸入序列的相對(duì)應(yīng)映象。(1)獲勝神經(jīng)元對(duì)于輸入向量x，使用表示最優(yōu)匹配輸入向量x的神經(jīng)元，則可以通過下列條件決定：這個(gè)條件概括了神經(jīng)元競(jìng)爭(zhēng)的本質(zhì)，滿足這個(gè)條件的神經(jī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.2SOM算法的聚類原理(2)(3)權(quán)值更新與學(xué)習(xí)率參數(shù)對(duì)于獲勝神經(jīng)元i的拓?fù)溧徲蚶锏纳窠?jīng)元，按以下方式更新權(quán)值：這里為學(xué)習(xí)率參數(shù)，它隨時(shí)間的增加單調(diào)下降，一種選擇就是：這里是另一個(gè)時(shí)間常數(shù)。學(xué)習(xí)率參數(shù)也可以選擇線性下降函數(shù)。3.6.2SOM算法的聚類原理(3)3.