大數(shù)據(jù)技術(shù)及應(yīng)用

BigDataTechnologyandApplication第6章大數(shù)據(jù)分析挖掘—聚類(lèi)

相似度計(jì)算010203主要內(nèi)容聚類(lèi)分析的步驟

聚類(lèi)分析概述

聚類(lèi)算法04

聚類(lèi)結(jié)果評(píng)估05分類(lèi)與聚類(lèi)在日常生活中，人們不是孤立地看待每件事物，而是會(huì)根據(jù)觀(guān)察到的事物屬性對(duì)其進(jìn)行分類(lèi)。在研究分類(lèi)問(wèn)題時(shí)，會(huì)面臨兩種情況：一種是預(yù)先已經(jīng)劃分好類(lèi)別，要求根據(jù)研究對(duì)象的特征，確定它們所屬的目標(biāo)類(lèi)；另一種是預(yù)先未定義類(lèi)別，需要根據(jù)研究對(duì)象彼此間的相似程度，對(duì)它們進(jìn)行分類(lèi)。前一種稱(chēng)為分類(lèi)（classification）問(wèn)題，后一種是本章將重點(diǎn)闡述的聚類(lèi)（clustering）問(wèn)題。聚類(lèi)分析概述1聚類(lèi)分析是將物理或抽象對(duì)象的集合分成由相似對(duì)象組成的多個(gè)組（group）或簇（cluster）的過(guò)程。簇具有“內(nèi)部同質(zhì)性、外部可分性”的特征。常見(jiàn)簇的類(lèi)型常見(jiàn)簇的類(lèi)型明顯分離的簇（well-separatedclusters）每個(gè)點(diǎn)到同簇中任意點(diǎn)的距離比到不同簇中所有點(diǎn)的距離更近?；谥行牡拇兀╟enter-basedclusters）每個(gè)點(diǎn)到所在簇中心的距離比到任何其他簇中心的距離更近，簇的中心通常被稱(chēng)為質(zhì)心?；卩徑拇兀╟ontiguity-basedclusters）每個(gè)點(diǎn)到同簇中至少一個(gè)點(diǎn)的距離比到不同簇中任意點(diǎn)的距離更近。常見(jiàn)簇的類(lèi)型基于密度的簇（density-basedclusters）簇被視作由低密度區(qū)域分開(kāi)的高密度區(qū)域。概念簇（conceptualclusters）簇中的所有點(diǎn)具有某種共同的性質(zhì)。概念簇可以涵蓋前面幾種簇的定義。簇的概念的模糊性，會(huì)導(dǎo)致同一數(shù)據(jù)集因?yàn)檠芯磕康摹?shù)據(jù)輸入方式、所選特征的不同，而最終形成不同的分簇結(jié)果。聚類(lèi)分析的步驟201020304數(shù)據(jù)預(yù)處理相似性度量聚類(lèi)(分組)聚類(lèi)結(jié)果評(píng)估通過(guò)特征選擇和特征提取，確定聚類(lèi)算法所使用的特征的數(shù)量、類(lèi)型和取值范圍的過(guò)程。雖然聚類(lèi)算法總是試圖為數(shù)據(jù)集找到最佳的分簇方式，卻無(wú)法保證聚類(lèi)結(jié)果與數(shù)據(jù)集的真實(shí)結(jié)構(gòu)相一致。評(píng)估方法：外部準(zhǔn)則、內(nèi)部準(zhǔn)則、相對(duì)準(zhǔn)則相似性代表對(duì)象間的近似或相關(guān)程度，可作為聚類(lèi)的依據(jù)，決定個(gè)體在不同簇之間的歸屬。度量方法：距離，相似系數(shù)，……建立目標(biāo)函數(shù)，將聚類(lèi)問(wèn)題轉(zhuǎn)化為對(duì)數(shù)據(jù)對(duì)象進(jìn)行分割的優(yōu)化問(wèn)題，進(jìn)而采用合適的解法求出聚類(lèi)結(jié)果。相似度計(jì)算3聚類(lèi)分析的相似性度量分為兩個(gè)方面：數(shù)據(jù)對(duì)象（個(gè)體）之間的相似關(guān)系和類(lèi)（群體）之間的相似關(guān)系。數(shù)據(jù)對(duì)象之間相似程度的描述把每個(gè)對(duì)象看作是多維空間中的一個(gè)點(diǎn)，通過(guò)距離大小反映對(duì)象之間的親疏程度計(jì)算對(duì)象之間的相關(guān)系數(shù)（稱(chēng)為相似系數(shù)）類(lèi)之間相似程度的描述通過(guò)對(duì)兩類(lèi)之間每個(gè)對(duì)象相似度的匯總來(lái)反映類(lèi)之間的親疏程度通過(guò)兩個(gè)類(lèi)的概括統(tǒng)計(jì)量之間的相似性描述類(lèi)之間的親疏程度對(duì)象之間的相似度數(shù)據(jù)對(duì)象是通過(guò)一組刻畫(huà)其基本特征的屬性表達(dá)的。屬性也稱(chēng)為特征、變量、特性或字段，它們是計(jì)算對(duì)象之間相似度的依據(jù)。對(duì)象屬性有連續(xù)型、離散型、混合型等，因此相似度的計(jì)算方法也不盡相同。對(duì)象之間的相似度連續(xù)屬性

對(duì)于連續(xù)屬性，距離和相似系數(shù)都是度量對(duì)象之間相似程度的常用手段。距離反映對(duì)象之間的相異性，相似系數(shù)反映對(duì)象之間的相似性。

假設(shè)數(shù)據(jù)集包含m個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象用d個(gè)屬性描述，第i個(gè)對(duì)象記為

。對(duì)象之間的相似度(1)距離兩個(gè)對(duì)象

和之間的距離通過(guò)距離函數(shù)

計(jì)算，和越相似，的值越小。距離函數(shù)必須滿(mǎn)足以下條件：對(duì)稱(chēng)性：

非負(fù)性：自反性：三角不等式：

對(duì)象之間的相似度歐氏距離全稱(chēng)是歐幾里得距離，定義源于歐氏空間中兩點(diǎn)間的距離公式，是一種最常用也最易于理解的距離度量方法。歐氏距離的計(jì)算是基于各維度屬性的絕對(duì)數(shù)值，只有當(dāng)各個(gè)維度的數(shù)據(jù)值對(duì)歐氏距離的貢獻(xiàn)同等的時(shí)候，才能獲得良好的表達(dá)效果。對(duì)象之間的相似度曼哈頓距離也稱(chēng)為城市街區(qū)距離或出租車(chē)距離，來(lái)源于從一個(gè)十字路口到另一個(gè)十字路口沿公路穿越曼哈頓街區(qū)的實(shí)際駕駛距離。對(duì)象之間的相似度切比雪夫距離也稱(chēng)為棋盤(pán)距離（chessboarddistance），起源于國(guó)際象棋中國(guó)王的走法，表示國(guó)王從當(dāng)前位置走到某一格所需要的最少步數(shù)。對(duì)象之間的相似度閔氏距離全稱(chēng)為閔可夫斯基距離，實(shí)際上是一組距離的定義?？勺儏?shù)

r可以取任意正整數(shù)。當(dāng)

r=1時(shí)，為曼哈頓距離；當(dāng)r=2時(shí)，為歐氏距離；當(dāng)

r

∞時(shí)，為切比雪夫距離。對(duì)象之間的相似度蘭氏距離也稱(chēng)為堪培拉距離（Canberradistance），可以看作是曼哈頓距離的加權(quán)版本。對(duì)象之間的相似度馬氏距離表示數(shù)據(jù)的協(xié)方差距離。當(dāng)協(xié)方差矩陣

Σ

為單位陣時(shí)，馬氏距離就簡(jiǎn)化為歐氏距離。對(duì)象之間的相似度(2)相似系數(shù)

包括兩種相似的表示方法：余弦相似度和狹義相關(guān)系數(shù)。后者針對(duì)不同類(lèi)型的屬性，又有不同形式的定義，最常用的是皮爾遜相關(guān)系數(shù)。對(duì)象之間的相似度余弦相似度

如果將數(shù)據(jù)對(duì)象

和看作d維空間的向量，余弦相似度就是這兩個(gè)向量之間夾角的余弦值。

余弦相似度的取值范圍為[-1，1]，當(dāng)兩個(gè)向量的方向重合時(shí)，余弦相似度取最大值1；當(dāng)兩個(gè)向量的方向完全相反時(shí)，余弦相似度取最小值-1。對(duì)象之間的相似度

在歐氏距離中，衡量相似度的標(biāo)準(zhǔn)是點(diǎn)之間的絕對(duì)距離。在余弦相似度中，衡量相似度的標(biāo)準(zhǔn)是向量之間夾角的大小。余弦相似度更加注重兩個(gè)向量在方向上的差異，而與向量的長(zhǎng)度無(wú)關(guān)，因此它的優(yōu)點(diǎn)是不受坐標(biāo)軸旋轉(zhuǎn)、放大和縮小的影響。對(duì)象之間的相似度皮爾遜相關(guān)系數(shù)用于衡量數(shù)據(jù)對(duì)象間的線(xiàn)性關(guān)系。其中：對(duì)象之間的相似度

皮爾遜相關(guān)系數(shù)等于兩個(gè)變量的協(xié)方差除以它們各自標(biāo)準(zhǔn)差的乘積，取值介于-1和1之間。

表示和正相關(guān)，表示和負(fù)相關(guān)，表示和不相關(guān)。

根據(jù)皮爾遜相關(guān)系數(shù)，還可以定義皮爾遜距離：對(duì)象之間的相似度二值離散屬性

二值離散屬性只有兩個(gè)值，通常取0和1。二值屬性需要采用特定的方法計(jì)算相似度，其中一類(lèi)常用的方法是匹配距離（matchingdistance）。

假設(shè)兩個(gè)數(shù)據(jù)對(duì)象

和的每個(gè)屬性都是二值離散型的，而且0和1兩個(gè)取值的權(quán)重相同，這樣可以得到一個(gè)2

2的列聯(lián)表（contingencytable）。對(duì)象之間的相似度a：在和中取值均為1的二值屬性的個(gè)數(shù)b：在中取0在中取1的二值屬性的個(gè)數(shù)c：在中取1在

中取0的二值屬性的個(gè)數(shù)d：在和中取值均為0的二值屬性的個(gè)數(shù)對(duì)象之間的相似度

基于a、b、c、d這四個(gè)數(shù)值，定義和間的距離：歐氏距離：蘭氏距離：對(duì)象之間的相似度

信息論中的漢明距離（Hammingdistance）也可用于度量二值屬性的相似性。漢明距離是將一個(gè)數(shù)據(jù)對(duì)象變換為另一個(gè)數(shù)據(jù)對(duì)象所需要的最小替換次數(shù)。[例1]與的漢明距離等于3。

在聚類(lèi)分析中，還定義了一系列的相似系數(shù)來(lái)衡量二值屬性的相似度。對(duì)象之間的相似度對(duì)象之間的相似度

如果數(shù)據(jù)對(duì)象的屬性都是對(duì)稱(chēng)的二值離散屬性，則可以采用簡(jiǎn)單匹配系數(shù)或者RogersandTanimoto系數(shù)計(jì)算對(duì)象之間的相似度。所謂對(duì)稱(chēng)，是指屬性值取0或1所表示的內(nèi)容同樣重要。Jaccard系數(shù)和SneathandSokal系數(shù)適用于計(jì)算非對(duì)稱(chēng)二值屬性的相似度。對(duì)象之間的相似度多值離散屬性

多值離散屬性是二值離散屬性的推廣，是狀態(tài)數(shù)量大于2的離散屬性。度量多值屬性相似度最常用的方法是簡(jiǎn)單匹配法。對(duì)于給定的兩個(gè)

d

維數(shù)據(jù)對(duì)象和，如果每一維屬性都是多值離散型的，則相似度為：其中m是匹配數(shù)，即

和中取值相同的屬性個(gè)數(shù)。對(duì)象之間的相似度

另一種計(jì)算

和之間相似度的方法是先將多值離散屬性轉(zhuǎn)換成多個(gè)二值離散屬性，然后利用二值離散屬性的相似系數(shù)計(jì)算公式算出結(jié)果。

在對(duì)多值離散屬性進(jìn)行轉(zhuǎn)換時(shí)，需要為每種狀態(tài)創(chuàng)建一個(gè)相應(yīng)的二值屬性，當(dāng)給定對(duì)象具有某個(gè)狀態(tài)時(shí)，代表該狀態(tài)的二值屬性就置為1，否則置為0。

對(duì)象之間的相似度混合類(lèi)型屬性

實(shí)際中的數(shù)據(jù)集通常含有多種類(lèi)型的屬性，對(duì)于這種數(shù)據(jù)，有幾種不同的方式來(lái)計(jì)算對(duì)象之間的距離。方式一：把連續(xù)屬性通過(guò)二分法進(jìn)行離散化，然后利用二值離散屬性的距離函數(shù)計(jì)算對(duì)象之間的距離。方式二：將離散屬性轉(zhuǎn)化為連續(xù)屬性，然后將對(duì)象的所有屬性規(guī)范化到相同的區(qū)間上，最后利用連續(xù)屬性的距離函數(shù)進(jìn)行求解。對(duì)象之間的相似度方式三：根據(jù)每種屬性的類(lèi)型，分別選擇合適的距離函數(shù)，然后將所有屬性計(jì)算出的距離值進(jìn)行加權(quán)組合，得到最終結(jié)果。[例2]方式三的一種實(shí)現(xiàn)方案。第1步：將連續(xù)屬性通過(guò)規(guī)范化處理轉(zhuǎn)換到相同的值域區(qū)間[0.0，1.0]上；第2步：將多值離散屬性轉(zhuǎn)換成多個(gè)二值離散屬性；第3步：定義d

維數(shù)據(jù)對(duì)象和之間的距離為：對(duì)象之間的相似度其中表示和在第k個(gè)屬性上的距離，它的計(jì)算方法如下：i.若屬性k為二值離散型，當(dāng)時(shí)，；否則，

；ii.若屬性k為連續(xù)型，則其中

h是屬性k

的所有非空缺對(duì)象。對(duì)象之間的相似度其中表示屬性k對(duì)和之間距離的貢獻(xiàn)，它的計(jì)算方法如下：i.如果或缺失，則

；ii.如果，且屬性k是不對(duì)稱(chēng)的二值離散屬性，則；iii.除了上述

i和

ii之外的其他情況下，

。類(lèi)之間的相似度將類(lèi)之間的相似程度轉(zhuǎn)化為個(gè)體之間的相似程度

假設(shè)有

和兩個(gè)類(lèi)，x

和y

分別是這兩個(gè)類(lèi)中的對(duì)象，

和之間的相似度可通過(guò)距離函數(shù)進(jìn)行度量。最遠(yuǎn)距離也稱(chēng)為全連接法（completelinkage），它將兩個(gè)類(lèi)之間的距離定義為這兩個(gè)類(lèi)兩兩對(duì)象之間的最遠(yuǎn)距離，即：類(lèi)之間的相似度最近距離也稱(chēng)為單連接法（singlelinkage），它將兩個(gè)類(lèi)之間的距離定義為這兩個(gè)類(lèi)兩兩對(duì)象之間的最近距離，即：平均距離也稱(chēng)為平均連接法（averagelinkage），它將兩個(gè)類(lèi)之間的距離定義為這兩個(gè)類(lèi)兩兩對(duì)象之間的平均距離，即：代表類(lèi)的基數(shù)類(lèi)之間的相似度在上述距離函數(shù)中，對(duì)象x

和

y之間的距離

可以利用之前介紹過(guò)的各種距離公式計(jì)算得到，其中最常用的是歐氏距離。類(lèi)之間的相似度利用類(lèi)的某種統(tǒng)計(jì)平均量計(jì)算類(lèi)的相似程度重心距離

重心是類(lèi)中所有對(duì)象在各個(gè)屬性上的均值。重心距離法的定義如下：其中和分別表示

和的重心，類(lèi)之間的相似度

對(duì)于由離散屬性構(gòu)成的數(shù)據(jù)對(duì)象，重心

對(duì)應(yīng)的點(diǎn)可能會(huì)落在取值空間之外，在這種情況下，用均值中心或者中值中心來(lái)代表類(lèi)將更加合適。

一個(gè)類(lèi)的均值中心

是與類(lèi)內(nèi)其他對(duì)象的距離和最小的對(duì)象，即滿(mǎn)足：

類(lèi)的中值中心

定義為：其中表示數(shù)據(jù)集T

的中位數(shù)。類(lèi)之間的相似度離差平方和

離差平方和法的思想來(lái)自于方差分析，也稱(chēng)為Ward法。

和可以取和的重心、均值中心或者中值中心。相似性度量方法的選擇

相似性度量方法顯著影響著聚類(lèi)分析的效果。一般說(shuō)來(lái)，同一個(gè)數(shù)據(jù)集如果采用不同的相似性度量方法，就會(huì)得到不同的聚類(lèi)結(jié)果。究其原因，主要是因?yàn)椴煌亩攘糠椒ù砹瞬煌饬x上的相似性。

在實(shí)際應(yīng)用中，需要根據(jù)屬性類(lèi)型、數(shù)據(jù)性質(zhì)、聚類(lèi)算法等因素來(lái)選擇合適的度量方法。相似性度量方法的選擇屬性類(lèi)型不同類(lèi)型的屬性有各自的相似性度量方法，而具體到每種屬性類(lèi)型，又存在多種距離函數(shù)或相似系數(shù)的定義。因此，在研究具體問(wèn)題時(shí)，應(yīng)當(dāng)明確屬性及其取值在實(shí)際應(yīng)用中的意義，并據(jù)此選擇合適的度量方法。數(shù)據(jù)性質(zhì)一方面，數(shù)據(jù)維度的差異會(huì)影響度量方法的有效性。另一方面，在某些情況下，為了簡(jiǎn)化計(jì)算過(guò)程或者改善聚類(lèi)效果，需要對(duì)數(shù)據(jù)屬性的類(lèi)型進(jìn)行適當(dāng)變換。相似性度量方法的選擇聚類(lèi)算法相似性度量方法的選擇受到聚類(lèi)算法的影響，例如對(duì)于二維數(shù)據(jù)集，馬氏距離在k-means算法中的效果最優(yōu)，但是在k-medoids算法中卻不是。

此外，選擇相似性度量方法時(shí)，還應(yīng)當(dāng)考慮計(jì)算量大小、研究目標(biāo)等因素。聚類(lèi)算法4

根據(jù)聚類(lèi)原理的不同，現(xiàn)有聚類(lèi)算法主要分為以下幾類(lèi)：基于劃分的方法、基于層次的方法、基于密度的方法、基于模型的方法、基于網(wǎng)格的方法、基于圖論的方法、基于模糊聚類(lèi)的方法、基于分形理論的方法等，不少聚類(lèi)算法是這些方法的綜合。聚類(lèi)算法基于劃分的方法

聚類(lèi)分析中最簡(jiǎn)單、最基本的一類(lèi)算法。它的基本思想是：對(duì)一個(gè)具有

n個(gè)對(duì)象的數(shù)據(jù)集D，給定要生成的簇的個(gè)數(shù)

，算法從某個(gè)初始的劃分方式出發(fā)，通過(guò)反復(fù)迭代不斷調(diào)整

k

個(gè)簇的成員，直到每個(gè)簇的成員穩(wěn)定為止。

大多數(shù)基于劃分的聚類(lèi)算法通過(guò)距離衡量對(duì)象間的相似度。k-means算法k-means算法的工作流程k-means算法

在k-means算法中，每一輪迭代完成后，都需要判斷聚類(lèi)結(jié)果是否收斂。為此，通常會(huì)定義一個(gè)準(zhǔn)則函數(shù)（也稱(chēng)為目標(biāo)函數(shù)），其中最常用的是誤差平方和函數(shù)（SumoftheSquaredError，SSE），它的定義如下：其中x是集合D中的數(shù)據(jù)對(duì)象，代表第i個(gè)簇，是的中心，，是中數(shù)據(jù)對(duì)象的個(gè)數(shù)。k-means算法[例3]假設(shè)二維數(shù)據(jù)集合中有

a~j

共10個(gè)數(shù)據(jù)對(duì)象，如表所示，要求劃分的簇的數(shù)量為

k=2。k-means算法初始化：選擇點(diǎn)

c和

f為初始的聚類(lèi)中心，即，第一次迭代步驟一：對(duì)每個(gè)數(shù)據(jù)點(diǎn)，分別計(jì)算它們與聚類(lèi)中心

c1和c2的距離，并劃分給距離最近的簇。例如對(duì)于點(diǎn)a，有：由于，故將a

劃分到簇C1。其他點(diǎn)也按照同樣的方法處理，最終得到下表中的結(jié)果。k-means算法第一次迭代后的結(jié)果k-means算法步驟二：對(duì)劃分出的新簇，更新聚類(lèi)中心。步驟三：計(jì)算每個(gè)簇的誤差平方和，得到：總的誤差平方和為：由于聚類(lèi)中心發(fā)生了變化，所以需要回到步驟一，開(kāi)始第二次迭代。k-means算法第二次迭代步驟一：對(duì)每個(gè)數(shù)據(jù)點(diǎn)，分別計(jì)算它們與更新后的聚類(lèi)中心

c1和c2的距離，并劃分給距離最近的簇。最終得到下表中的結(jié)果。k-means算法步驟二：對(duì)于每一個(gè)簇，更新聚類(lèi)中心。由于所有數(shù)據(jù)點(diǎn)都沒(méi)有改變簇成員關(guān)系，因此聚類(lèi)中心保持不變，仍然是

和。步驟三：計(jì)算誤差平方和。由于簇的劃分方式保持不變，所以SSE的值與第一次迭代相同。第二次迭代與第一次迭代的聚類(lèi)結(jié)果相同，表明算法已收斂，處理過(guò)程結(jié)束。k-means算法優(yōu)點(diǎn)：簡(jiǎn)單、快速，時(shí)間復(fù)雜度和空間復(fù)雜度都相對(duì)較低。缺點(diǎn)：算法要求用戶(hù)事先給出分簇的數(shù)目k，如果用戶(hù)沒(méi)有關(guān)于數(shù)據(jù)集的先驗(yàn)信息，k值的估計(jì)將非常困難。解決方法：可以設(shè)置不同的k值，多次執(zhí)行k-means算法，通過(guò)對(duì)比最終的聚類(lèi)效果，選出最優(yōu)的

k

值。算法對(duì)初始聚類(lèi)中心的選取較為敏感，不同的初始值會(huì)造成不同的聚類(lèi)結(jié)果。k-means算法在前面的例子中，如果初始化階段選擇點(diǎn)和為聚類(lèi)中心，得到的聚類(lèi)結(jié)果是：簇C1：簇C2：聚類(lèi)中心：，誤差平方和：解決方法：多次運(yùn)行k-means算法，每次隨機(jī)選擇一組不同的初始聚類(lèi)中心，最終所得到的SSE最小的一組就是最優(yōu)方案。k-means算法算法只有在簇的均值被定義的情況下才能使用，而無(wú)法直接處理離散型數(shù)據(jù)。解決方法：重新定義k-means算法的距離函數(shù)和計(jì)算聚類(lèi)中心的方法。算法采用歐氏距離度量數(shù)據(jù)對(duì)象之間的相似性，以誤差平方和最小化為優(yōu)化目標(biāo)，導(dǎo)致該算法對(duì)球狀簇有較好的聚類(lèi)效果，卻不適合非球狀的簇。對(duì)于離群點(diǎn)數(shù)據(jù)敏感。k-medoids算法

也稱(chēng)為k-中心點(diǎn)算法，是在k-means算法的基礎(chǔ)上，利用簇的中心點(diǎn)代替均值點(diǎn)作為聚類(lèi)中心，然后根據(jù)各數(shù)據(jù)對(duì)象與這些聚類(lèi)中心之間的距離之和最小化的原則，進(jìn)行簇的劃分。PAM（PartitioningAroundMedoids）算法是最早提出的k-medoids算法之一。k-medoids算法PAM算法的處理過(guò)程：建立階段：隨意選擇

k

個(gè)代表對(duì)象作為

k個(gè)簇中心，依次衡量其他數(shù)據(jù)點(diǎn)與各簇中心之間的距離，并將數(shù)據(jù)點(diǎn)分配到最近的一個(gè)簇中。交換階段：反復(fù)地用非代表對(duì)象（普通數(shù)據(jù)點(diǎn)）替代代表對(duì)象，目的是試圖找出更好的簇中心，以改進(jìn)聚類(lèi)的質(zhì)量。在每次迭代中，當(dāng)前某個(gè)代表對(duì)象被一個(gè)非代表對(duì)象替換后，數(shù)據(jù)集中所有其他的數(shù)據(jù)對(duì)象需要重新進(jìn)行歸類(lèi)，并計(jì)算交換前后各數(shù)據(jù)點(diǎn)與所在簇的中心點(diǎn)之間的距離差，以此作為該點(diǎn)因簇的代表對(duì)象變化而產(chǎn)生的代價(jià)。k-medoids算法

交換的總代價(jià)是所有對(duì)象的代價(jià)之和。如果總代價(jià)為負(fù)值，則表明交換后的類(lèi)內(nèi)聚合度更好，原來(lái)的代表對(duì)象將被替代；如果總代價(jià)為正值，則表明原來(lái)的代表對(duì)象更好，不應(yīng)被取代。

為了確定任意一個(gè)非代表對(duì)象

是否可以替換當(dāng)前的某個(gè)代表對(duì)象

，需要對(duì)數(shù)據(jù)集中的所有非代表對(duì)象

x進(jìn)行檢查，以確定

x

是否要重新歸類(lèi)。根據(jù)

x

位置的不同，分為4種情況。k-medoids算法交換后數(shù)據(jù)對(duì)象重新歸類(lèi)的四種情況：k-medoids算法情況(a)：x當(dāng)前屬于以

cj

為中心點(diǎn)的簇，如果用crandom替換

cj作為新的代表對(duì)象，x將更接近其他簇的中心點(diǎn)

ci，那么就將x

歸類(lèi)到以ci

為中心點(diǎn)的簇中。情況(b)：x當(dāng)前屬于以

cj

為中心點(diǎn)的簇，如果用crandom

替換

cj作為新的代表對(duì)象，x將更接近c(diǎn)random

，那么就將x

歸類(lèi)到以crandom為中心點(diǎn)的簇中。情況(c)：x當(dāng)前屬于以

ci為中心點(diǎn)的簇，如果用crandom

替換

cj作為新的代表對(duì)象，x仍然最接近

ci，那么x

的歸類(lèi)將保持不變。情況(d)：x當(dāng)前屬于以

ci

為中心點(diǎn)的簇，如果用crandom

替換

cj作為新的代表對(duì)象，x將更接近c(diǎn)random，那么就將x

歸類(lèi)到以crandom為中心點(diǎn)的簇中。k-medoids算法CLARA（ClusteringLARgeApplication）算法是PAM的擴(kuò)展，它利用抽樣的方法，能夠有效處理大規(guī)模數(shù)據(jù)所帶來(lái)的計(jì)算開(kāi)銷(xiāo)和RAM存儲(chǔ)問(wèn)題。CLARA算法不是從整個(gè)數(shù)據(jù)集中發(fā)現(xiàn)代表對(duì)象，而是取其中一小部分?jǐn)?shù)據(jù)作為代表（稱(chēng)作樣本），然后利用PAM算法從這個(gè)樣本中選出中心點(diǎn)。CLARA算法的有效性依賴(lài)于樣本的大小、分布及抽樣質(zhì)量。如果樣本包含的數(shù)據(jù)點(diǎn)過(guò)少，可能會(huì)沒(méi)有把全部的最佳聚類(lèi)中心都選中，這樣就不能找到最好的聚類(lèi)結(jié)果。k-medoids算法CLARANS（ClusteringLargeApplicationsbaseduponRANdomizedSearch）是另外一種k-medoids算法，它對(duì)CLARA的聚類(lèi)質(zhì)量和可擴(kuò)展性進(jìn)行了改進(jìn)，不像CLARA那樣在每輪迭代中都選取一個(gè)固定樣本，而是采用動(dòng)態(tài)抽樣的方法，在搜索的每一步都以某種隨機(jī)方式進(jìn)行抽樣。聚類(lèi)算法基于層次的方法

基于層次的聚類(lèi)算法，是通過(guò)將數(shù)據(jù)組織為若干組（簇）并最終形成一個(gè)樹(shù)狀結(jié)構(gòu)的聚類(lèi)方法。根據(jù)聚類(lèi)層次形成方向的不同，又分為自底向上的凝聚聚類(lèi)（AgglomerativeClustering）和自頂向下的分裂聚類(lèi)（DivisiveClustering）。

層次聚類(lèi)的結(jié)果通常用樹(shù)狀圖（dendrogram）表示，圖中最頂部的根節(jié)點(diǎn)表示整個(gè)數(shù)據(jù)集，中間節(jié)點(diǎn)代表由若干個(gè)對(duì)象構(gòu)成的子簇，最底部的葉子節(jié)點(diǎn)代表數(shù)據(jù)集中的對(duì)象。聚類(lèi)算法層次聚類(lèi)的樹(shù)狀圖最左邊的坐標(biāo)軸用于標(biāo)注節(jié)點(diǎn)的高度，實(shí)現(xiàn)節(jié)點(diǎn)在層次結(jié)構(gòu)中的定位。通常，所有葉子節(jié)點(diǎn)的高度均為0，根節(jié)點(diǎn)的高度最高。在不同高度對(duì)樹(shù)狀圖進(jìn)行分割，可能會(huì)得到不同的分簇?cái)?shù)目。凝聚聚類(lèi)

大多數(shù)層次聚類(lèi)算法都屬于凝聚聚類(lèi)，這些算法的區(qū)別主要體現(xiàn)在采用不同的方式定義簇之間的距離。度量簇之間距離的常用方法有：最遠(yuǎn)距離、最近距離、平均距離等。凝聚聚類(lèi)

凝聚聚類(lèi)的典型代表是AGNES（AGglomerativeNESting）算法，它的處理步驟是：①

將數(shù)據(jù)集中的每個(gè)對(duì)象作為一個(gè)簇；②

每次找到距離最近的兩個(gè)簇進(jìn)行合并；③

合并過(guò)程反復(fù)進(jìn)行，直至不能再合并或者達(dá)到結(jié)束條件為止。凝聚聚類(lèi)AGNES算法的偽代碼凝聚聚類(lèi)[例4]試用AGENES算法求出例3中數(shù)據(jù)集的層次聚類(lèi)樹(shù)狀圖。初始化階段：每個(gè)對(duì)象單獨(dú)構(gòu)成一個(gè)簇，共形成10個(gè)簇計(jì)算得到的距離矩陣D

如表所示。凝聚聚類(lèi)第一次迭代：將兩個(gè)距離最近的簇合并為一個(gè)簇。從表中可以看到，C1與C3、C2與C3、C3與C4、C3與C5、C4與C6、C5與C6、C5與C7的距離最近，均為1。假設(shè)合并C1與C3，這樣就產(chǎn)生一個(gè)新簇。

計(jì)算C13與其他簇之間的距離：

若使用最近距離，則簇C13與C2的距離為

若使用最遠(yuǎn)距離，則簇C13與C2的距離為

若使用平均距離，則簇C13與C2的距離為凝聚聚類(lèi)采用最近距離得到更新后的距離矩陣凝聚聚類(lèi)第二次迭代：合并C4與C6，得到一個(gè)新簇。繼續(xù)簇的合并過(guò)程，直到所有對(duì)象合并到一個(gè)簇中。最終生成的樹(shù)狀圖為：分裂聚類(lèi)

分裂聚類(lèi)的典型代表是DIANA（DIvisiveANAlysis）算法，它的處理步驟是：1)將數(shù)據(jù)集中的所有對(duì)象作為一個(gè)簇；2)根據(jù)某種準(zhǔn)則，每次將當(dāng)前最大的簇分裂成兩個(gè)子簇；3)分裂過(guò)程反復(fù)進(jìn)行，直至每個(gè)簇只包含一個(gè)對(duì)象或者達(dá)到結(jié)束條件為止。分裂聚類(lèi)

為了確定當(dāng)前的最大簇，DIANA算法定義了簇的直徑這一概念，它是簇中任意兩個(gè)數(shù)據(jù)對(duì)象之間距離的最大值。DIANA算法還定義平均相異度作為進(jìn)行簇分裂的依據(jù)，它的計(jì)算公式如下：表示對(duì)象x與簇C的平均相異度，|C|表示簇C中對(duì)象的個(gè)數(shù)，是對(duì)象x與y之間的距離。越大，在進(jìn)行簇的分裂時(shí)，應(yīng)當(dāng)優(yōu)先將x分離出去。分裂聚類(lèi)DIANA算法的偽代碼其他層次聚類(lèi)方法

凝聚聚類(lèi)和分裂聚類(lèi)方法經(jīng)常會(huì)遇到如何選擇合并或分裂點(diǎn)的問(wèn)題。如果在某一階段所做出的合并或分裂決策不恰當(dāng)，就可能導(dǎo)致聚類(lèi)質(zhì)量降低。

這類(lèi)方法在做出合并和分裂決策前需要檢測(cè)和估算大量的對(duì)象或簇，可擴(kuò)展性較差，幾乎不能在大數(shù)據(jù)集上使用。

為了改進(jìn)層次聚類(lèi)算法的聚類(lèi)質(zhì)量，新的研究從層次聚類(lèi)與其他聚類(lèi)技術(shù)結(jié)合入手，將層次聚類(lèi)和其他聚類(lèi)技術(shù)進(jìn)行集成，形成多階段的聚類(lèi)。其他層次聚類(lèi)方法(1)BIRCH算法BIRCH算法的全稱(chēng)是利用層次方法的平衡迭代歸約和聚類(lèi)（BalancedIterativeReducingandClusteringusingHierarchies），適用于大規(guī)模數(shù)據(jù)集。BIRCH首先利用層次聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行劃分，然后再利用其他聚類(lèi)方法進(jìn)行優(yōu)化，以改善聚類(lèi)質(zhì)量。BIRCH算法BIRCH算法引入聚類(lèi)特征（ClusteringFeature，CF）和聚類(lèi)特征樹(shù)（CF樹(shù)）的概念來(lái)描述簇的整體特征。聚類(lèi)特征是一個(gè)三元組，概括了子簇的統(tǒng)計(jì)信息。若一個(gè)子簇包含n

個(gè)d

維的數(shù)據(jù)對(duì)象，則這個(gè)子簇的CF定義為：其中BIRCH算法由CF可以計(jì)算簇的信息：

簇中心：

簇半徑：

簇直徑：

兩簇之間的距離：

BIRCH算法CF具有線(xiàn)性性質(zhì)，可以快速實(shí)現(xiàn)BIRCH算法中兩個(gè)簇的合并操作。

例如有兩個(gè)簇C1和C2，C1包含3個(gè)二維的數(shù)據(jù)對(duì)象(1,1)、(1,2)和(2,1)，C2包含2個(gè)對(duì)象(3,2)和(3,3)，則：如果合并C1、C2為一個(gè)新簇C12，則：BIRCH算法CF樹(shù)是一棵高度平衡樹(shù)，存儲(chǔ)著層次聚類(lèi)的聚類(lèi)特征，其中每個(gè)節(jié)點(diǎn)都包含一系列的CF。在葉子節(jié)點(diǎn)中，每個(gè)CF條目對(duì)應(yīng)一個(gè)由若干數(shù)據(jù)對(duì)象組成的子簇。根節(jié)點(diǎn)和非葉節(jié)點(diǎn)中的每個(gè)CF條目是相應(yīng)子節(jié)點(diǎn)中的所有CF條目之和。CF樹(shù)有3個(gè)重要的參數(shù)：分支因子B、閾值T和葉子節(jié)點(diǎn)包含的最大CF條目數(shù)L。B用于限定非葉節(jié)點(diǎn)擁有的最大子節(jié)點(diǎn)數(shù)，T指定了存放在葉子節(jié)點(diǎn)中的子簇的最大直徑。BIRCH算法CF樹(shù)的結(jié)構(gòu)BIRCH算法BIRCH算法的工作過(guò)程：階段一：掃描數(shù)據(jù)集，構(gòu)建一個(gè)存放于內(nèi)存的初始CF樹(shù)；階段二：采用某個(gè)聚類(lèi)算法對(duì)CF樹(shù)的葉子節(jié)點(diǎn)進(jìn)行聚類(lèi)。該階段可以選擇任意現(xiàn)有的聚類(lèi)算法，如k-means。在階段一，BIRCH每次掃描一個(gè)對(duì)象，并決定是否應(yīng)當(dāng)將給定的對(duì)象分配給已經(jīng)存在的某個(gè)簇或者構(gòu)造一個(gè)新簇。隨著對(duì)象不斷被插入，CF樹(shù)動(dòng)態(tài)地構(gòu)造起來(lái)。BIRCH算法CF樹(shù)構(gòu)建過(guò)程：確定根節(jié)點(diǎn)CF：對(duì)于每一個(gè)待插入的對(duì)象

x，BIRCH比較該對(duì)象與根節(jié)點(diǎn)中每個(gè)CF的位置關(guān)系，將其放入最接近的根節(jié)點(diǎn)CF中。確定非葉節(jié)點(diǎn)CF：將

x下傳到上述根節(jié)點(diǎn)CF所對(duì)應(yīng)的非葉節(jié)點(diǎn)，比較

x與非葉節(jié)點(diǎn)中各個(gè)CF的位置關(guān)系，并將它放入最接近的非葉節(jié)點(diǎn)CF中。如果CF樹(shù)中存在多級(jí)非葉節(jié)點(diǎn)，這一步將重復(fù)執(zhí)行多次。確定葉子節(jié)點(diǎn)CF：根據(jù)上一步所確定的最低一級(jí)非葉節(jié)點(diǎn)CF，將x下傳到這個(gè)CF所對(duì)應(yīng)的葉子節(jié)點(diǎn)中。比較

x的位置與葉子節(jié)點(diǎn)中每個(gè)CF的位置，初步將其分配給最接近的葉子節(jié)點(diǎn)CF。假設(shè)該CF所代表的簇的名稱(chēng)為

Ci。BIRCH算法修改葉子節(jié)點(diǎn)：檢驗(yàn)

Ci能否容納x并且不違反閾值

T的規(guī)定。如果符合閾值的要求，則確定將

x分配給Ci，并更新相應(yīng)的CF值；否則，為x

新建一個(gè)CF并插入葉子節(jié)點(diǎn)中。如果葉子節(jié)點(diǎn)沒(méi)有足夠的空間，則會(huì)被分裂為兩個(gè)葉子節(jié)點(diǎn)。分裂時(shí)，將距離最遠(yuǎn)的一對(duì)CF作為葉子節(jié)點(diǎn)的種子，其他CF按照最鄰近標(biāo)準(zhǔn)分配到這兩個(gè)葉子節(jié)點(diǎn)中。修改根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑：把x

插入到葉子節(jié)點(diǎn)后，必須更新根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑上所有節(jié)點(diǎn)中的CF信息。如果上一步中不存在葉子節(jié)點(diǎn)分裂，則只需要把

x

的值添加到葉子節(jié)點(diǎn)的父節(jié)點(diǎn)及祖先節(jié)點(diǎn)的CF三元組中；如果存在分裂，則需要在葉子節(jié)點(diǎn)的父節(jié)點(diǎn)中加入一個(gè)新的CF。這一過(guò)程將一直回溯到根節(jié)點(diǎn)。BIRCH算法[例5]利用BIRCH算法構(gòu)建以下數(shù)據(jù)集的CF樹(shù)。CF參數(shù)設(shè)置為：輸入第一個(gè)數(shù)據(jù)對(duì)象

。因?yàn)槌跏紩r(shí)CF為空，因而創(chuàng)建一個(gè)根節(jié)點(diǎn)，并將對(duì)象放入其中。BIRCH算法輸入第二個(gè)數(shù)據(jù)對(duì)象

。將x2

暫時(shí)分配給

CF1，得到更新后的值為

。計(jì)算此時(shí)簇1的直徑

D

為0.25，小于閾值

T，因此x2可以分配給CF1。BIRCH算法輸入第三個(gè)對(duì)象

。將x3

暫時(shí)分配給

CF1，得到更新后的值為

。計(jì)算此時(shí)簇1的直徑

D

為0.354，大于閾值

T，因此x3不可以分配給CF1，需要新建一個(gè)簇

CF2，將x3放入其中。BIRCH算法輸入第四個(gè)對(duì)象

。比較x4

與

CF1及CF2的位置關(guān)系，找到更靠近

x4

的那個(gè)簇。如果采用CF的均值進(jìn)行度量，則有：比較后發(fā)現(xiàn)x4

距離更近，所以暫時(shí)將

x4

放入CF1

中。更新后的值為

，簇1的直徑

D

變?yōu)?.286，大于閾值

T，需要?jiǎng)?chuàng)建一個(gè)新的簇

CF3

來(lái)容納x4。由于這時(shí)根節(jié)點(diǎn)中的CF數(shù)量將增加到3，超過(guò)了規(guī)定的最大值

B，因此必須分裂根節(jié)點(diǎn)。BIRCH算法加入第四個(gè)對(duì)象后的CF樹(shù)BIRCH算法輸入第五個(gè)對(duì)象

。首先比較x5

與

CFB1及CFB2的位置關(guān)系，因?yàn)?，，可?jiàn)x5

距離CFB1更近，所以暫時(shí)將

x5

放入葉子節(jié)點(diǎn)2的

CF3

中。更新后的值為

，簇3的直徑

D

變?yōu)?.35，大于閾值

T，需要?jiǎng)?chuàng)建一個(gè)新的簇

CF4

來(lái)容納x5。BIRCH算法輸入最后一個(gè)對(duì)象

。首先比較x6

與

CFB1及CFB2的位置關(guān)系，因?yàn)椋?，可?jiàn)x6

距離CFB2更近，所以暫時(shí)將

x6

放入CFB2，并下傳到葉子節(jié)點(diǎn)2。在葉子節(jié)點(diǎn)2，比較

x6與

CF3及CF4

的位置關(guān)系。由于所以將x6

暫存于CF4，更新后的值為

，簇4的直徑

D

變?yōu)?.4，大于閾值

T，需要在葉子節(jié)點(diǎn)2中創(chuàng)建一個(gè)新的簇

CF5

，但是該操作會(huì)使葉子節(jié)點(diǎn)2中CF的數(shù)量超過(guò)最大值

L，因此必須對(duì)葉子節(jié)點(diǎn)2進(jìn)行分裂，創(chuàng)建一個(gè)新的葉子節(jié)點(diǎn)3。相應(yīng)地，根節(jié)點(diǎn)也必須進(jìn)行分裂。BIRCH算法最終生成的CF樹(shù)其他層次聚類(lèi)方法(2)CURE算法CURE（ClusteringUsingRepresentatives）算法是一種新穎的層次聚類(lèi)算法，不僅能夠處理大數(shù)據(jù)集，而且克服了大多數(shù)聚類(lèi)算法在處理非球形簇、非均勻大小的簇以及離群點(diǎn)等方面的不足。CURE算法最突出的特點(diǎn)是利用數(shù)據(jù)空間中固定數(shù)目的代表性點(diǎn)來(lái)表示一個(gè)簇，而不是僅用單個(gè)的質(zhì)心或數(shù)據(jù)對(duì)象來(lái)描述。CURE算法

在選擇代表點(diǎn)時(shí)，CURE首先盡可能選擇簇中分散的對(duì)象，然后通過(guò)應(yīng)用收縮因子

α

，使這些分散的點(diǎn)向簇的質(zhì)心方向收縮。為了獲得較好的聚類(lèi)效果，α

通常在0.2~0.7之間取值。

代表點(diǎn)的個(gè)數(shù)

c是算法的一個(gè)參數(shù)，當(dāng)

c的值取10或者更大時(shí)，聚類(lèi)效果較好。CURE算法CURE算法采用凝聚聚類(lèi)的思想，在最開(kāi)始的時(shí)候，每一個(gè)數(shù)據(jù)對(duì)象就是一個(gè)獨(dú)立的簇。在聚類(lèi)過(guò)程中，每次將距離最近的兩個(gè)簇進(jìn)行合并。兩個(gè)簇之間的距離被定義為二者代表點(diǎn)之間距離的最小值。在合并簇的過(guò)程中，需要計(jì)算新產(chǎn)生的簇的質(zhì)心和代表點(diǎn)，計(jì)算方法如下：質(zhì)心：代表點(diǎn)：

CURE算法CURE在最壞情況下的時(shí)間復(fù)雜度是

，不適于處理大型數(shù)據(jù)集，因此使用隨機(jī)抽樣和劃分的方法來(lái)加快聚類(lèi)過(guò)程。

與BIRCH算法相比，CURE在大數(shù)據(jù)集上具有更強(qiáng)的可擴(kuò)展性，聚類(lèi)質(zhì)量也更高，但是要求用戶(hù)輸入的參數(shù)較多。聚類(lèi)算法基于密度的方法

基于劃分的聚類(lèi)算法和基于層次的聚類(lèi)算法往往只能發(fā)現(xiàn)凸形的聚類(lèi)簇，而且多數(shù)容易受離群點(diǎn)的影響。為了更好地發(fā)現(xiàn)各種形狀的聚類(lèi)簇，人們提出了基于密度的聚類(lèi)算法。這類(lèi)算法的主要思想是尋找被低密度（噪聲）區(qū)域分離的高密度區(qū)域，而數(shù)據(jù)空間中的對(duì)象就位于這些高密度區(qū)域。DBSCAN算法

DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）是一種基于密度的空間聚類(lèi)算法，它的基本思想是每個(gè)簇的內(nèi)部點(diǎn)的密度比簇的外部點(diǎn)的密度要高得多，簇是密度相連的點(diǎn)的最大集合，聚類(lèi)是在數(shù)據(jù)空間中不斷尋找最大集合的過(guò)程。DBSCAN算法幾個(gè)基本概念ε-鄰域：對(duì)于給定的對(duì)象

p，以p為中心，以ε為半徑的區(qū)域稱(chēng)為對(duì)象

p的ε-鄰域。核心對(duì)象：對(duì)于給定的正整數(shù)

MinPts，如果對(duì)象p的ε-鄰域內(nèi)至少包含MinPts個(gè)對(duì)象，則稱(chēng)p為核心對(duì)象。邊界對(duì)象：如果對(duì)象

p位于某個(gè)核心對(duì)象的鄰域內(nèi)，但其本身又不滿(mǎn)足核心對(duì)象的條件，則稱(chēng)

p為邊界對(duì)象。既不是核心對(duì)象，也不是邊界對(duì)象的點(diǎn)被視為噪聲點(diǎn)。DBSCAN算法核心對(duì)象、邊界對(duì)象與噪聲點(diǎn)DBSCAN算法幾個(gè)基本概念直接密度可達(dá)：如果對(duì)象

p

在對(duì)象

q

的ε-鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則稱(chēng)對(duì)象

p

從q

出發(fā)是直接密度可達(dá)的。密度可達(dá)：給定一個(gè)數(shù)據(jù)對(duì)象集合

D，如果存在一個(gè)對(duì)象序列

，

，

，pn+1是從pn出發(fā)關(guān)于ε和MinPts直接密度可達(dá)的，則稱(chēng)對(duì)象

p

是從q

出發(fā)關(guān)于ε和MinPts密度可達(dá)的。DBSCAN算法密度相連：如果對(duì)象集合

D

中存在一個(gè)對(duì)象

o，使得對(duì)象

p

和q

都是從

o出發(fā)關(guān)于ε和MinPts密度可達(dá)的，則稱(chēng)對(duì)象

p和q是關(guān)于ε和MinPts密度相連的。DBSCAN算法算法流程：①

從數(shù)據(jù)對(duì)象集合中選擇一個(gè)未處理過(guò)的對(duì)象

p，判斷p

在(ε，MinPts)條件下是否為核心對(duì)象；②如果p

為核心對(duì)象，掃描對(duì)象集合，找出

p關(guān)于ε和MinPts密度可達(dá)的所有對(duì)象，形成一個(gè)簇；③

如果

p

是非核心對(duì)象，則訪(fǎng)問(wèn)數(shù)據(jù)集中的下一個(gè)對(duì)象；④

重復(fù)①-③步，直到數(shù)據(jù)集合中的所有對(duì)象都被處理。DBSCAN算法[例6]利用DBSCAN算法對(duì)下圖中的數(shù)據(jù)集進(jìn)行聚類(lèi)處理。設(shè)，MinPts=4，對(duì)象之間的距離采用歐氏距離進(jìn)行度量。DBSCAN算法第1步：在數(shù)據(jù)集中任意選擇一點(diǎn)，假定是

a，由于在以它為圓心，以

為半徑的圓內(nèi)包含2個(gè)點(diǎn)，小于MinPts，因此它不是核心對(duì)象，選擇下一個(gè)點(diǎn)。第2步：在數(shù)據(jù)集中選擇一點(diǎn)c，在以它為圓心，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心對(duì)象。在其ε-鄰域內(nèi)，點(diǎn)

a、b、d都不是核心對(duì)象，而點(diǎn)

e是核心對(duì)象，繼續(xù)在點(diǎn)

e的ε-鄰域內(nèi)尋找新的核心對(duì)象，最終得到一個(gè)新的簇

。

DBSCAN算法第3步：在數(shù)據(jù)集中選擇未處理過(guò)的一點(diǎn)

h，在以它為圓心，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心對(duì)象，選擇下一個(gè)點(diǎn)。第4步：在數(shù)據(jù)集中選擇未處理過(guò)的一點(diǎn)

i，在以它為圓心，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心對(duì)象，選擇下一個(gè)點(diǎn)。

第5步：在數(shù)據(jù)集中選擇未處理過(guò)的一點(diǎn)j，在以它為圓心，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心對(duì)象，選擇下一個(gè)點(diǎn)。第6步：在數(shù)據(jù)集中選擇點(diǎn)

l，在以它為圓心，以1為半徑的圓內(nèi)包含4個(gè)點(diǎn)，因此它是核心對(duì)象。在其ε-鄰域內(nèi)的點(diǎn)h、i、j都不是核心對(duì)象,因此得到一個(gè)新的簇

。DBSCAN算法DBSCAN算法的聚類(lèi)結(jié)果OPTICS算法

OPTICS（OrderingPointsToIdentifytheClusteringStructure）是一種基于簇排序的聚類(lèi)分析方法。它以DBSCAN算法為基礎(chǔ)，但是并不顯式地產(chǎn)生一個(gè)數(shù)據(jù)集的聚類(lèi)，而是基于密度建立起一種簇排序（clusterordering）。該序列蘊(yùn)涵了數(shù)據(jù)集的內(nèi)在聚類(lèi)結(jié)構(gòu)，其中包含的信息等同于從一系列參數(shù)設(shè)置所獲得的基于密度的聚類(lèi)。OPTICS算法

OPTICS算法對(duì)鄰域半徑參數(shù)

ε

賦予一系列不同的取值，以獲得一組密度聚類(lèi)結(jié)果，從而適應(yīng)不同的密度分布。在處理數(shù)據(jù)集時(shí)，OPTICS按照

ε

從小到大的順序來(lái)進(jìn)行，以便高密度的聚類(lèi)能夠先被執(zhí)行。核心距離：對(duì)于一個(gè)給定的MinPts，對(duì)象p

的核心距離是使得

p

成為核心對(duì)象的最小鄰域半徑，記作

?？蛇_(dá)距離：對(duì)象

p

和q

的可達(dá)距離是

p

的核心距離與

p、q

之間的歐氏距離中的較大者。OPTICS算法核心距離與可達(dá)距離的概念OPTICS算法OPTICS算法執(zhí)行時(shí)，需要對(duì)數(shù)據(jù)集中的對(duì)象進(jìn)行排序，同時(shí)計(jì)算并存儲(chǔ)每個(gè)對(duì)象的核心距離與可達(dá)距離，這些信息足以使用戶(hù)獲得鄰域半徑小于等于

ε

范圍內(nèi)的所有聚類(lèi)結(jié)果。聚類(lèi)算法基于網(wǎng)格的方法

這類(lèi)方法的基本思想是：將數(shù)據(jù)空間的每一維分別劃分成有限數(shù)目的單元，從而構(gòu)成一個(gè)可以進(jìn)行聚類(lèi)分析的網(wǎng)格結(jié)構(gòu)。當(dāng)網(wǎng)格足夠小時(shí)，同一網(wǎng)格單元內(nèi)的數(shù)據(jù)對(duì)象屬于同一個(gè)簇的可能性較大，它們將被視為一個(gè)對(duì)象進(jìn)行處理，即所有的聚類(lèi)操作都在網(wǎng)格單元上進(jìn)行，這樣算法的處理時(shí)間就與數(shù)據(jù)對(duì)象的數(shù)目無(wú)關(guān)，而只與網(wǎng)格單元的數(shù)量有關(guān)，因此處理速度很快。STING算法

統(tǒng)計(jì)信息網(wǎng)格（STatisticalINformationGrid，STING）是一種基于網(wǎng)格的多分辨率聚類(lèi)技術(shù)，它將空間區(qū)域劃分為矩形單元，通常存在多級(jí)矩形單元分別對(duì)應(yīng)不同級(jí)別的分辨率，從而形成一個(gè)層次結(jié)構(gòu)。STING算法

每個(gè)網(wǎng)格單元的屬性由一系列統(tǒng)計(jì)參數(shù)加以描述，這些參數(shù)包括：n（計(jì)數(shù)）、m（均值）、s（標(biāo)準(zhǔn)差）、min（最小值）、max（最大值），以及該單元中屬性值遵循的分布類(lèi)型。

當(dāng)數(shù)據(jù)存入數(shù)據(jù)庫(kù)時(shí)，首先根據(jù)數(shù)據(jù)計(jì)算出最底層單元的參數(shù)n，m，s，min和max，而數(shù)據(jù)分布可以由用戶(hù)指定或者通過(guò)假設(shè)檢驗(yàn)來(lái)獲得。STING算法高層單元中的參數(shù)通過(guò)以下公式計(jì)算得到STING算法STING算法自頂向下地使用網(wǎng)格單元中的統(tǒng)計(jì)信息，來(lái)尋找滿(mǎn)足指定查詢(xún)條件的區(qū)域。首先，根據(jù)查詢(xún)需求在層次結(jié)構(gòu)中選定一層作為查詢(xún)過(guò)程的起始點(diǎn)，對(duì)于其中每個(gè)單元，利用統(tǒng)計(jì)參數(shù)計(jì)算該單元在某種預(yù)設(shè)的置信級(jí)別上與查詢(xún)條件相關(guān)的可能性。不相關(guān)單元在后續(xù)處理過(guò)程中將不再考慮。對(duì)于相關(guān)單元，需要繼續(xù)進(jìn)入下一層，對(duì)其劃分出的每個(gè)子單元進(jìn)行同樣的處理。這個(gè)處理過(guò)程不斷重復(fù)，直到完成最底層單元的檢查。

找出所有相關(guān)單元后，利用廣度優(yōu)先法發(fā)現(xiàn)滿(mǎn)足指定密度要求的區(qū)域（簇）。STING算法算法優(yōu)點(diǎn)：①

存儲(chǔ)在每個(gè)單元中的統(tǒng)計(jì)信息提供了網(wǎng)格單元中所有數(shù)據(jù)對(duì)象的匯總信息。由于這些信息不依賴(lài)于具體的查詢(xún)處理，所以基于網(wǎng)格的計(jì)算過(guò)程與查詢(xún)過(guò)程相互獨(dú)立。②

網(wǎng)格結(jié)構(gòu)有助于實(shí)現(xiàn)并行處理和增量更新。③

效率高。STING算法存在的問(wèn)題：聚類(lèi)質(zhì)量依賴(lài)于網(wǎng)格結(jié)構(gòu)最底層的粒度。如果粒度很細(xì)，處理的代價(jià)會(huì)顯著增加；反之，如果粒度太粗，將會(huì)降低聚類(lèi)分析的質(zhì)量。CLIQUE算法

CLIQUE（CLusteringInQUEst）算法是最早且最具代表性的子空間聚類(lèi)算法。子空間聚類(lèi)（Subspaceclustering）是解決大規(guī)模高維數(shù)據(jù)聚類(lèi)的一種有效方法，它的特點(diǎn)是只在相關(guān)屬性構(gòu)成的子空間上執(zhí)行聚類(lèi)任務(wù)，通過(guò)一定的搜索策略和評(píng)測(cè)標(biāo)準(zhǔn)從不同的子空間中篩選出需要聚類(lèi)的簇。CLIQUE算法

CLIQUE算法采用基于密度的方法，區(qū)分空間中密集的和稀疏的區(qū)域（即網(wǎng)格單元）。判斷一個(gè)網(wǎng)格單元是否密集的依據(jù)是，統(tǒng)計(jì)該單元中數(shù)據(jù)對(duì)象的數(shù)目，如果這個(gè)值超過(guò)了預(yù)先輸入的某個(gè)模型參數(shù)，則該單元是密集的。在CLIQUE中，簇定義為相連的密集單元的最大集合。

在搜索密集單元的過(guò)程中，CLIQUE采用一種自底向上的方法。首先掃描數(shù)據(jù)庫(kù)，找出所有一維子空間中的密集單元；然后通過(guò)某種候選單元產(chǎn)生算法，從已經(jīng)確定的k-1維密集單元中生成候選的k維密集單元，如此重復(fù)，直到不再產(chǎn)生新的候選集為止。CLIQUE算法CLIQUE算法這個(gè)例子更加直觀(guān)地表明：存在于整個(gè)數(shù)據(jù)空間或者高維子空間的簇，在低維子空間中也會(huì)作為簇出現(xiàn)。但是，在整個(gè)數(shù)據(jù)空間不能形成簇的點(diǎn)集，卻有可能在子空間中形成簇。因此，許多在子空間發(fā)現(xiàn)的簇可能只是較高維簇的“影子”（投影），在聚類(lèi)過(guò)程中需要篩除它們。CLIQUE算法算法執(zhí)行過(guò)程：第一階段：將n-維數(shù)據(jù)空間劃分為互不重疊的矩形單元，并識(shí)別出其中的密集單元。第二階段：運(yùn)用深度優(yōu)先算法從上一階段輸出的密集單元集合中識(shí)別出簇。第三階段：為每個(gè)簇生成最小化的描述。聚類(lèi)算法基于模型的方法這類(lèi)方法的基本思想是為每個(gè)簇假設(shè)一個(gè)分布模型，然后在數(shù)據(jù)集中尋找能夠符合這個(gè)模型的數(shù)據(jù)對(duì)象，試圖使給定數(shù)據(jù)與該數(shù)學(xué)模型達(dá)成最佳擬合。

基于模型的聚類(lèi)方法主要有三種：混合模型法、概念聚類(lèi)法和神經(jīng)網(wǎng)絡(luò)法。混合模型法

混合模型法是將整個(gè)數(shù)據(jù)集看作是有限（k）個(gè)概率分布的混合，其中每個(gè)單獨(dú)的概率分布被稱(chēng)為組件分布（componentdistribution），代表一個(gè)簇。在聚類(lèi)過(guò)程中，選擇合適的聚類(lèi)方法和分簇?cái)?shù)目的問(wèn)題被轉(zhuǎn)化為如何選擇統(tǒng)計(jì)模型的問(wèn)題，包括概率分布的數(shù)量、每個(gè)組件分布的類(lèi)型及其參數(shù)的取值。

高斯混合模型（GaussianMixtureModel，GMM）算法是這類(lèi)方法的典型代表。混合模型法GMM假設(shè)數(shù)據(jù)集是由多個(gè)符合高斯分布的組件分布混合而成，它的定義為：其中

、是第i個(gè)組件分布的均值向量和協(xié)方差矩陣，

為混合系數(shù)，代表第i個(gè)組件分布占總體分布的比例，

?；旌夏Ｐ头ㄔ贕MM算法中，模型參數(shù)

是未知的，首先需要進(jìn)行參數(shù)估計(jì)。參數(shù)估計(jì)常采用最大似然法，即尋找參數(shù)的最優(yōu)取值，使得數(shù)據(jù)集

D

在估計(jì)的概率密度函數(shù)上有最大的概率值。混合模型法期望最大化（ExpectationMaximization，EM）算法的步驟：期望步（E步）：在給定GMM參數(shù)的情況下，計(jì)算每個(gè)數(shù)據(jù)對(duì)象屬于各個(gè)簇的概率。對(duì)于第

j

個(gè)對(duì)象

xj，它屬于第

i個(gè)簇的概率為：最大化步（M步）：使用E步獲得的概率值重新計(jì)算GMM的參數(shù)?；旌夏Ｐ头‥M算法交替執(zhí)行E步和M步，直到達(dá)到指定的迭代次數(shù)，或者模型參數(shù)收斂為止?；旌夏Ｐ头℅MM算法與k-means算法相類(lèi)似，也需要用戶(hù)預(yù)先指定簇的數(shù)目k。k-means是一種“硬”聚類(lèi)算法，它明確地指出每個(gè)對(duì)象所屬的簇，而且每個(gè)對(duì)象屬于且僅屬于一個(gè)簇，簇之間有明確的界線(xiàn)，不存在交集；GMM則是一種“軟”聚類(lèi)算法，它沒(méi)有嚴(yán)格劃分簇的界限，也沒(méi)有直接指出對(duì)象所屬的簇，而是通過(guò)概率值來(lái)衡量對(duì)象隸屬于各個(gè)簇的程度。概念聚類(lèi)法

概念聚類(lèi)（conceptualclustering）與傳統(tǒng)聚類(lèi)方法的不同之處在于，后者的主要目標(biāo)是識(shí)別相似對(duì)象，而概念聚類(lèi)在此基礎(chǔ)上更進(jìn)一步，它要找出每一個(gè)類(lèi)的特征描述。

概念聚類(lèi)方法種類(lèi)繁多，有基于樹(shù)結(jié)構(gòu)的COBWEB、CLASSIT、COBBIT算法，基于圖的LC、RGC算法，基于進(jìn)化模型的EMO-CC、GAIL算法，基于網(wǎng)格的MCC、GALOIS算法，等等。概念聚類(lèi)法COBWEB是一個(gè)常用的簡(jiǎn)單增量式概念聚類(lèi)方法，采用分類(lèi)樹(shù)（classificationtree）的形式進(jìn)行層次聚類(lèi)。樹(shù)的每個(gè)節(jié)點(diǎn)代表一個(gè)概念（類(lèi)），其中包含這個(gè)概念的概率描述，該描述用于概括歸類(lèi)于這個(gè)節(jié)點(diǎn)的所有數(shù)據(jù)對(duì)象。

概念聚類(lèi)法COBWEB算法通過(guò)逐個(gè)插入對(duì)象的方法增量式地構(gòu)造分類(lèi)樹(shù)。當(dāng)要插入一個(gè)對(duì)象時(shí)，COBWEB從根節(jié)點(diǎn)開(kāi)始，沿著分類(lèi)樹(shù)中一條“最合適”的路徑自頂向下，尋找可以分類(lèi)該對(duì)象的最佳節(jié)點(diǎn)。這個(gè)判定是基于將對(duì)象臨時(shí)置于每個(gè)節(jié)點(diǎn)，并計(jì)算劃分結(jié)果的分類(lèi)效用（CategoryUtility，CU），根據(jù)最大的分類(lèi)效用做出相應(yīng)的動(dòng)作。

概念聚類(lèi)法

在確定對(duì)象最終插入位置時(shí)，COBWEB還會(huì)考慮為對(duì)象創(chuàng)建一個(gè)新的節(jié)點(diǎn)所獲得的分類(lèi)效用，并將其與基于現(xiàn)有節(jié)點(diǎn)的計(jì)算結(jié)果進(jìn)行比較。因此，COBWEB具有自動(dòng)調(diào)整分簇?cái)?shù)量的能力。

由于插入和新建操作對(duì)輸入對(duì)象的順序非常敏感，COBWEB又定義了合并與分裂操作來(lái)緩解這一問(wèn)題。在合并操作中，分類(lèi)效用值最高的兩個(gè)節(jié)點(diǎn)被合并為一個(gè)節(jié)點(diǎn)，從而使相似性高的對(duì)象盡量被合并到一個(gè)簇中；在分裂操作中，分類(lèi)效用值最大的節(jié)點(diǎn)將被刪除。概念聚類(lèi)法神經(jīng)網(wǎng)絡(luò)法

基于神經(jīng)網(wǎng)絡(luò)的聚類(lèi)方法種類(lèi)繁多，在這些算法中，每個(gè)簇被描述為一個(gè)范例（exemplar）。范例作為簇的原型，類(lèi)似于k-means中的質(zhì)心，不一定對(duì)應(yīng)一個(gè)特定的數(shù)據(jù)對(duì)象。在進(jìn)行聚類(lèi)時(shí)，算法通過(guò)某種距離度量方法，比較一個(gè)新的數(shù)據(jù)對(duì)象與各個(gè)范例的相似程度，并將其分配到最相似的簇中。神經(jīng)網(wǎng)絡(luò)法SCL算法SCL算法采用競(jìng)爭(zhēng)學(xué)習(xí)的思想，它的生理學(xué)基礎(chǔ)是神經(jīng)網(wǎng)絡(luò)的側(cè)抑制現(xiàn)象，即當(dāng)一個(gè)神經(jīng)細(xì)胞興奮后，會(huì)對(duì)其周?chē)纳窠?jīng)細(xì)胞產(chǎn)生抑制作用。這種側(cè)抑制使神經(jīng)細(xì)胞呈現(xiàn)出競(jìng)爭(zhēng)，開(kāi)始時(shí)可能多個(gè)細(xì)胞同時(shí)興奮，但一個(gè)興奮程度最強(qiáng)的神經(jīng)細(xì)胞對(duì)周?chē)窠?jīng)細(xì)胞的抑制作用也更強(qiáng)，結(jié)果使其周?chē)窠?jīng)細(xì)胞興奮度減弱，該神經(jīng)細(xì)胞成為這次競(jìng)爭(zhēng)中的“勝者”。神經(jīng)網(wǎng)絡(luò)法SCL采用層次型網(wǎng)絡(luò)結(jié)構(gòu)，由輸入層和輸出層組成。神經(jīng)網(wǎng)絡(luò)法

輸入層負(fù)責(zé)接收外界信息并將輸入模式向輸出層傳遞；輸出層也稱(chēng)為競(jìng)爭(zhēng)層，起分析比較的作用，負(fù)責(zé)從輸入模式中找出規(guī)律并進(jìn)行歸類(lèi)。輸入層與輸出層之間采用全連接方式。

輸出層各神經(jīng)元之間的連接用于模擬生物神經(jīng)網(wǎng)絡(luò)內(nèi)的側(cè)抑制現(xiàn)象，從而保證在一次計(jì)算中，只有一個(gè)輸出神經(jīng)元獲勝，獲勝的神經(jīng)元標(biāo)記為1，其余神經(jīng)元均標(biāo)記為0，這一規(guī)則稱(chēng)為“勝者為王”（Winner-Take-All）。神經(jīng)網(wǎng)絡(luò)法SOM算法SOM是一種基于競(jìng)爭(zhēng)學(xué)習(xí)的自組織映射網(wǎng)絡(luò)，一方面，它與SCL網(wǎng)絡(luò)相類(lèi)似，都是由輸入層和輸出層構(gòu)成，而且輸出神經(jīng)元之間具有競(jìng)爭(zhēng)性；另一方面，SOM還模擬了人腦的自組織特性。類(lèi)似于人腦中的不同區(qū)域有著不同的功能，不同的感官輸入會(huì)刺激不同位置的神經(jīng)元產(chǎn)生興奮，當(dāng)SOM神經(jīng)網(wǎng)絡(luò)接受外界輸入模式時(shí)，也會(huì)分為不同的對(duì)應(yīng)區(qū)域，各區(qū)域?qū)斎肽Ｊ骄哂胁煌捻憫?yīng)特征。神經(jīng)網(wǎng)絡(luò)法

在SOM網(wǎng)絡(luò)中，輸入層神經(jīng)元通過(guò)權(quán)值向量將外界信息匯集到競(jìng)爭(zhēng)層的各神經(jīng)元；競(jìng)爭(zhēng)層也是輸出層，神經(jīng)元的排列有多種形式，如一維線(xiàn)陣、二維網(wǎng)格陣和三維柵格陣等。神經(jīng)網(wǎng)絡(luò)法SOM網(wǎng)絡(luò)的學(xué)習(xí)算法稱(chēng)為Kohonen算法，它是在勝者為王算法的基礎(chǔ)上改進(jìn)而成的。二者的主要區(qū)別在于：在勝者為王算法中，只有競(jìng)爭(zhēng)獲勝的神經(jīng)元才能調(diào)整連接權(quán)值，而在SOM中，每個(gè)神經(jīng)元附近一定鄰域內(nèi)的神經(jīng)元也會(huì)得到更新，較遠(yuǎn)的神經(jīng)元?jiǎng)t不會(huì)更新。

聚類(lèi)結(jié)果評(píng)估5外部準(zhǔn)則法

屬于有監(jiān)督的度量方法，它假設(shè)數(shù)據(jù)集中各對(duì)象的真實(shí)類(lèi)別已知，通過(guò)比較聚類(lèi)結(jié)果與已知類(lèi)別的匹配程度來(lái)判斷聚類(lèi)質(zhì)量的優(yōu)劣。

外部評(píng)價(jià)指標(biāo)分為基于集合匹配度的指標(biāo)、基于信息熵的指標(biāo)和基于樣本對(duì)的指標(biāo)。(1)基于集合匹配度的指標(biāo)

這類(lèi)度量方法認(rèn)為待評(píng)測(cè)的聚類(lèi)集

C與真實(shí)的分類(lèi)集

L之間具有一一對(duì)應(yīng)的關(guān)系，并利用信息檢索中的精確率和召回率等概念來(lái)構(gòu)造不同的評(píng)價(jià)指標(biāo)。

對(duì)于給定的類(lèi)別

，簇的精確率和召回率分別定義為：

聚類(lèi)結(jié)果評(píng)估純度：逆純度：F測(cè)度：聚類(lèi)結(jié)果評(píng)估(2)基于信息熵的指標(biāo)

這類(lèi)度量方法利用信息論中信息熵和互信息的概念來(lái)評(píng)價(jià)聚類(lèi)質(zhì)量。聚類(lèi)熵：聚類(lèi)結(jié)果中所有簇的熵的平均值，它的計(jì)算公式如下：聚類(lèi)結(jié)果評(píng)估互信息MI（MutualInformation）：用于度量聚類(lèi)結(jié)果

C與數(shù)據(jù)真實(shí)分布

L

之間的相似程度，表示在已知對(duì)象真實(shí)類(lèi)別的條件下，可以多大程度地減少對(duì)象隨機(jī)選簇的不確定性。聚類(lèi)結(jié)果評(píng)估標(biāo)準(zhǔn)化互信息NMI（NormalizedMutualInformation）調(diào)整互信息AMI（AdjustedMutualInformation）其中E[MI]是互信息MI的數(shù)學(xué)期望，H(C)和H(L)分別代表C和L這兩種分布的熵。聚類(lèi)結(jié)果評(píng)估(3)基于樣本對(duì)的指標(biāo)

這類(lèi)度量方法先要根據(jù)樣本對(duì)在聚類(lèi)結(jié)果和真實(shí)分類(lèi)中的分布情況構(gòu)造列聯(lián)表，然后將列聯(lián)表中的四個(gè)參量以某種形式進(jìn)行組合，得到不同的評(píng)價(jià)標(biāo)準(zhǔn)。聚類(lèi)結(jié)果評(píng)估列聯(lián)表中參量的定義：f00：屬于不同類(lèi)別而且不同分簇的樣本對(duì)數(shù)量f01：屬于不同類(lèi)別但是相同分簇的樣本對(duì)數(shù)量f10：屬于相同類(lèi)別但是不同分簇的樣本對(duì)數(shù)量f11：屬于相同類(lèi)別而且相同分簇的樣本對(duì)數(shù)量其中，f00和f11反映聚類(lèi)結(jié)果與真實(shí)類(lèi)結(jié)構(gòu)的一致性，f01和f10反映其偏差。聚類(lèi)結(jié)果評(píng)估蘭德指數(shù)RI（RandIndex）：調(diào)整蘭德指數(shù)RI：Jaccard系數(shù)：FM指數(shù)：聚類(lèi)結(jié)果評(píng)估內(nèi)部準(zhǔn)則法

屬于非監(jiān)督的度量方法，沒(méi)有可參考的外部信息，只能依賴(lài)數(shù)據(jù)集自身的特征和量值對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)。在這種情況下，需要從聚類(lèi)的內(nèi)在需求出發(fā)，考察簇的緊密度、分離度以及簇表示的復(fù)雜度。

緊密度（Cohesion）反映簇內(nèi)成員的凝聚程度；分離度（Separation）表示簇與簇之間的相異程度，理想的聚類(lèi)效果應(yīng)該具有較高的簇內(nèi)緊密度和較大的簇間分離度。聚類(lèi)結(jié)果評(píng)估(1)輪廓系數(shù)：基本思想是將數(shù)據(jù)集中的任一對(duì)象與本簇中其他對(duì)象的相似性以及該對(duì)象與其他簇中對(duì)象的相似性進(jìn)行量化，并將量化后的兩種相似性以某種形式組合，以獲得聚類(lèi)優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)。數(shù)據(jù)對(duì)象xi

的輪廓系數(shù)：其中ai是xi與本簇中其他對(duì)象之間的平均距離，它反映了

xi所屬簇的緊密程度；bi是xi與最近簇的對(duì)象之間的平均距離，它表示

xi與其他簇的分離程度。聚類(lèi)結(jié)果評(píng)估平均輪廓系數(shù)：數(shù)據(jù)集中所有對(duì)象輪廓系數(shù)的平均值，用于評(píng)價(jià)聚類(lèi)方案的有效性。聚類(lèi)結(jié)果評(píng)估(2)CH指標(biāo)：通過(guò)類(lèi)內(nèi)協(xié)方差矩陣描述緊密度，類(lèi)間協(xié)方差矩陣描述分離度。其中，n

為數(shù)據(jù)集中對(duì)象的個(gè)數(shù)，k

為簇的個(gè)數(shù)，trB(k)和trW(k)分別是類(lèi)間協(xié)方差矩陣B(k)和類(lèi)內(nèi)協(xié)方差矩陣W(k)的跡。聚類(lèi)結(jié)果評(píng)估式中|Ci|表示簇

Ci

中對(duì)象的數(shù)量，

是Ci中對(duì)象間的平均距離，

是數(shù)據(jù)集中所有對(duì)象間的平均距離，且有：聚類(lèi)結(jié)果評(píng)估(3)DH指標(biāo)：其中，表示簇Ci

內(nèi)的對(duì)象與其質(zhì)心間的平均距離，

表示簇Ci

與簇Cj

質(zhì)心間的距離，k是簇的數(shù)目。聚類(lèi)結(jié)果評(píng)估相對(duì)準(zhǔn)則法

相對(duì)準(zhǔn)則法用于比較不同聚類(lèi)的結(jié)果，通常是針對(duì)同一個(gè)聚類(lèi)算法的不同參數(shù)設(shè)置進(jìn)行算法測(cè)試（如不同的分簇個(gè)數(shù)），最終選擇最優(yōu)的參數(shù)設(shè)置和聚類(lèi)模式。相對(duì)準(zhǔn)則法在進(jìn)行聚類(lèi)比較時(shí)，直接使用外部準(zhǔn)則法或者內(nèi)部準(zhǔn)則法定義的評(píng)價(jià)指標(biāo)，因而它實(shí)際上并不是一種單獨(dú)的聚類(lèi)質(zhì)量度量方法，而是前兩類(lèi)度量方法的一種具體應(yīng)用。聚類(lèi)結(jié)果評(píng)估習(xí)題6.1比較聚類(lèi)分析與分類(lèi)分析的異同點(diǎn)。6.2簡(jiǎn)述衡量數(shù)據(jù)對(duì)象之間相似度的主要方法。6.3下表是我國(guó)部分省份2018年電話(huà)用戶(hù)情況統(tǒng)計(jì)數(shù)據(jù)，試通過(guò)k-means算法對(duì)其進(jìn)行分析。要求采用歐氏距離，分簇?cái)?shù)量取3。習(xí)題6.4試用DIANA算法對(duì)表6.3的數(shù)據(jù)集進(jìn)行聚類(lèi)，要求采用歐氏距離，終止條件取

k=2。6.5下表是我國(guó)部分省份2018年電話(huà)用戶(hù)情況統(tǒng)計(jì)數(shù)據(jù)，試通過(guò)k-means算法對(duì)其進(jìn)行分析。要求采用歐氏距離，分簇?cái)?shù)量取3。習(xí)題6.6設(shè)有一維數(shù)據(jù)集

，要求用BIRCH算法生成CF樹(shù)，CF參數(shù)設(shè)置為：T=0.2，B=2，L=2。6.7簡(jiǎn)述評(píng)價(jià)聚類(lèi)結(jié)果質(zhì)量的主要方法。6.8下表是某數(shù)據(jù)集的距離矩陣，若數(shù)據(jù)對(duì)象x1和x2被劃分到簇C1，x3和x4被劃分到簇C2，試計(jì)算每個(gè)對(duì)象的輪廓系數(shù)以及數(shù)據(jù)集的輪廓系數(shù)。習(xí)題6.9試采用DB指標(biāo)對(duì)圖6.10和圖6.11的聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)。第7章大數(shù)據(jù)分析挖掘—關(guān)聯(lián)規(guī)則

Apriori算法010203主要內(nèi)容關(guān)聯(lián)規(guī)則挖掘的一般過(guò)程

關(guān)聯(lián)規(guī)則的概念

FP-Growth算法04

關(guān)聯(lián)模式評(píng)估05大數(shù)據(jù)分析挖掘——關(guān)聯(lián)規(guī)則7.1基本概念設(shè)是項(xiàng)目的集合，其中的元素稱(chēng)為項(xiàng)目(item),一個(gè)集合被稱(chēng)為一個(gè)項(xiàng)集，包含k個(gè)項(xiàng)的集合稱(chēng)為k-項(xiàng)集。設(shè)是由數(shù)據(jù)庫(kù)中所有項(xiàng)目構(gòu)成的集合，事務(wù)數(shù)據(jù)庫(kù)是由一系列具有唯一標(biāo)識(shí)的事務(wù)組成，唯一標(biāo)識(shí)符記作TID（TransactionIdentifier），每一個(gè)事務(wù)包含的項(xiàng)集都是的子集。7.1關(guān)聯(lián)規(guī)則的基本概念關(guān)聯(lián)規(guī)則表示項(xiàng)集之間的關(guān)系或關(guān)聯(lián)，一般用形如的蘊(yùn)含式表達(dá)，其中。X稱(chēng)為規(guī)則的前提，Y稱(chēng)為規(guī)則的結(jié)果。支持度（support）：是事務(wù)集中同時(shí)包含X和Y的事務(wù)數(shù)與所有事務(wù)數(shù)之比，它反映了X和Y中所含的項(xiàng)在事務(wù)集中同時(shí)出現(xiàn)的概率。置信度（confidence）置信度是事務(wù)集中，同時(shí)包含X和Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)（不考慮是否包含Y）之比，反映了包含X的事務(wù)中出現(xiàn)Y的條件概率，記為confidence(X=>Y)，即：置信度高說(shuō)明X發(fā)生引起Y發(fā)生的可能性高，也就是說(shuō)，規(guī)則Y依賴(lài)X的可能性比較高。7.1關(guān)聯(lián)規(guī)則的基本概念7.2關(guān)聯(lián)規(guī)則挖掘的一般過(guò)程表7.1是該商店篩選出的10條購(gòu)物清單，每條清單包含3種商品。表7.1某商店購(gòu)物清單購(gòu)物車(chē)Item1Item2Item31香草華夫香蕉狗糧2香蕉面包酸奶3香蕉蘋(píng)果酸奶4香草華夫香蕉淡奶油5面包香草華夫酸奶6牛奶面包香蕉7香草華夫蘋(píng)果香蕉8酸奶蘋(píng)果香草華夫9香草華夫香蕉牛奶10香蕉面包花生醬首先，需要計(jì)算商店中所有單獨(dú)商品的支持度。在這10條清單里中共有9種商品，每種商品的支持度統(tǒng)計(jì)如表7.2所示：表7.2商品支持度統(tǒng)計(jì)表ItemSupport蘋(píng)果3香蕉8面包4狗糧1牛奶2花生醬1香草華夫6酸奶4淡奶油1只計(jì)算頻繁項(xiàng)集{香草華夫，香蕉}的關(guān)聯(lián)性分別計(jì)算兩條關(guān)聯(lián)規(guī)則的置信度：香草華夫=>香蕉香蕉=>香草華夫?qū)懗申P(guān)聯(lián)規(guī)則，可以得到規(guī)則“香草華夫=>香蕉”強(qiáng)于（支持度相同，置信度更高）規(guī)則“香蕉=>香草華夫”香草華夫=>香蕉[support=40%,confidence=67%]香蕉=>香草華夫[support=40%,confidence=50%]假設(shè)存在10000個(gè)超市訂單（10000個(gè)事務(wù)），其中購(gòu)買(mǎi)香草華夫（A事務(wù)）的6000個(gè)，購(gòu)買(mǎi)香蕉（B事務(wù)）的7500個(gè)，4000個(gè)同時(shí)包含兩者。那么通過(guò)上面支持度的計(jì)算方法可以計(jì)算出：香草華夫（A事務(wù)）和香蕉（B事務(wù)）的支持度為：香草華夫（A事務(wù)）對(duì)香蕉（B事務(wù)）的置信度為：4000/6000=0.67香蕉（B事務(wù)）對(duì)香草華夫（A事務(wù)）的置信度為：4000/7500=0.53在沒(méi)有任何條件下，香蕉的出現(xiàn)的比例是75%，而出現(xiàn)A事務(wù)，且同時(shí)出現(xiàn)B事務(wù)的比例是67%，也就是說(shuō)設(shè)置了A事務(wù)出現(xiàn)這個(gè)條件，B事務(wù)出現(xiàn)的比例反而降低了，這說(shuō)明A事務(wù)和B事務(wù)是排斥的。有些商品自身的表現(xiàn)好于作為關(guān)聯(lián)規(guī)則后的表現(xiàn)，即使規(guī)則符合某些最小支持閾值，也必須考慮商品在規(guī)則之外的表現(xiàn)。提升度（Lift）表示“包含X的事務(wù)中同時(shí)包含Y的事務(wù)的比例”與“包含Y的事務(wù)的比例”的比值。公式表達(dá)如7.5所示：提升度反映了關(guān)聯(lián)規(guī)則中X與Y的相關(guān)性，提升度>1且越高表明正相關(guān)性越高，提升度<1且越低表明負(fù)相關(guān)性越高，提升度=1表明沒(méi)有相關(guān)性。7.3Apriori算法尋找關(guān)聯(lián)規(guī)則的基礎(chǔ)是首先尋找頻繁項(xiàng)集。Apriori算法是一種先驗(yàn)概率算法，它的計(jì)算量主要集中在生成頻繁2-項(xiàng)集上。產(chǎn)生頻繁項(xiàng)集的過(guò)程：首先，通過(guò)掃描數(shù)據(jù)庫(kù)，積累每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿(mǎn)足最小支持度閾值的項(xiàng)，找出頻繁1項(xiàng)集的集合，該集合記為L(zhǎng)1

。然后，使用L1找出頻繁2項(xiàng)集的集合L2，使用L2找出L3，如此下去直到不能再找到頻繁k項(xiàng)集。7.3Apriori算法Apriori算法的先驗(yàn)性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也是頻繁的，任意非頻繁項(xiàng)集的所有超級(jí)也是非頻繁的。實(shí)例一：假設(shè)有一個(gè)數(shù)據(jù)庫(kù)D，其中有4個(gè)事務(wù)記錄，分別表示為：TIDT1T2T3T4ItemsI1,I3,I4I2