基于幾何光滑度的案例聚類方法

摘要:聚類分析技術(shù)是近年迅速發(fā)展的一種數(shù)據(jù)處理技術(shù)，它在諸如經(jīng)濟(jì)學(xué)、生物學(xué)、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等許多領(lǐng)域具有廣泛的應(yīng)用。首先闡述聚類分析的基本概念，接下來(lái)介紹了當(dāng)前典型的幾種聚類方法，然后提出了基于幾何光滑度的光滑拼接聚類算法，最后提及了聚類算法的未來(lái)發(fā)展。

關(guān)鍵詞:聚類分析;相似度;共享最近鄰;k-平均算法;數(shù)據(jù)挖掘

中圖分類號(hào):F224.0 文獻(xiàn)標(biāo)志碼:A 文章編號(hào):1673-291X(2010)05-0238-03

引言

隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)庫(kù)應(yīng)用的范圍、規(guī)模和深度也在不斷的擴(kuò)大，這樣就導(dǎo)致積累了大量的數(shù)據(jù)，而人們所關(guān)心的往往是這些數(shù)據(jù)背后所隱藏的信息。目前，商業(yè)界普遍使用的條形碼和科學(xué)研究領(lǐng)域利用先進(jìn)的數(shù)據(jù)測(cè)量?jī)x器所測(cè)出的數(shù)據(jù)，這些數(shù)據(jù)都是海量的。面對(duì)這樣龐大的數(shù)據(jù)庫(kù)，人們迫切的需要一種有效的技術(shù)從這些龐大的數(shù)據(jù)中智能、自動(dòng)地提取出來(lái)有價(jià)值的知識(shí)或是信息，這就是所謂的數(shù)據(jù)挖掘技術(shù)。而聚類分析正是數(shù)據(jù)挖掘所采用的關(guān)鍵技術(shù)之一，它被用于發(fā)現(xiàn)隱藏在大量數(shù)據(jù)中的分組和令人感興趣的數(shù)據(jù)模式。迄今為止，人們提出了許多聚類算法，所有這些算法都試圖解決大規(guī)模數(shù)據(jù)的聚類問(wèn)題。

一、聚類的基本概念

1.聚類的定義

所謂聚類[1]，就是將一個(gè)數(shù)據(jù)集合分成若干個(gè)稱為簇或是類別的子集，每個(gè)簇中的數(shù)據(jù)都是具有很高的相似度，而簇之間具有較低的相似度。

簇的定義[2]:由于不同的應(yīng)用所分析的具體數(shù)據(jù)具有不同的特征，因此聚類的目標(biāo)簇具有不同的的形式和定義。簡(jiǎn)單的來(lái)講，簇就是聚類分析結(jié)果中由相似的數(shù)據(jù)對(duì)象所組成的一個(gè)個(gè)的分組就成為簇，同一簇中的點(diǎn)具有很高的相似性，不同簇中的點(diǎn)具有很高的相異性。

2.聚類的一般步驟

聚類分析一般的主要步驟如下:

(1)特征選擇。首先必須適當(dāng)?shù)倪x擇特征，盡可能多的包含任務(wù)所關(guān)心的信息。在選擇特征中，信息的多余減少和最小化是主要的目的。

(2)相似性度量。用于定量度量?jī)蓚€(gè)特征向量之間的相似度。一個(gè)簡(jiǎn)單的度量如歐氏距離經(jīng)常被用來(lái)反應(yīng)兩個(gè)特征向量之間的非相似度。

(3)聚類算法。已經(jīng)選擇了合適的相似性度量，這步涉及到選擇特定的聚類算法，用于揭示數(shù)據(jù)集中隱藏的數(shù)據(jù)結(jié)構(gòu)。

(4)結(jié)果驗(yàn)證。一旦用聚類算法得到了結(jié)果，就需要驗(yàn)證其正確性。

(5)結(jié)果的判定。在許多情況下，應(yīng)用領(lǐng)域的專家必須用其他實(shí)驗(yàn)數(shù)據(jù)和分析判定聚類結(jié)果，最后得出可被人理解的正確的結(jié)論。

3.聚類的典型要求

一種好的健壯的聚類方法應(yīng)當(dāng)具有可伸縮性、具有處理不同類型屬性的能力、能夠發(fā)現(xiàn)任意形狀的簇、先驗(yàn)知識(shí)最小化、具有處理噪聲數(shù)據(jù)的能力、對(duì)輸入數(shù)據(jù)的順序不敏感、具有處理高維數(shù)據(jù)的能力、基于約束的聚類、具有可解釋性和可用性。

二、典型的聚類方法

1.基于劃分的方法

給定一個(gè)包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，以及要生成簇的數(shù)目k，一個(gè)基于劃分的聚類算法將數(shù)據(jù)對(duì)象組織為k個(gè)劃分(k

k-平均算法(k-means)首先隨機(jī)選取k個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象代表一個(gè)簇的平均值或中心點(diǎn)。其余的對(duì)象按照它們與這些平均值之間的距離，被賦予與之最相近的簇。然后，算法對(duì)每個(gè)新簇重新計(jì)算其平均值。這個(gè)過(guò)程一直迭代直到一個(gè)準(zhǔn)則函數(shù)收斂為止。典型的準(zhǔn)則函數(shù)是方差準(zhǔn)則函數(shù)，定義為:E=xeCx=m

其中x代表數(shù)據(jù)空間中給定的對(duì)象，mi是簇Ci的平均值(x和mi可以是任意維的向量)。該準(zhǔn)則函數(shù)試圖使結(jié)果簇內(nèi)部盡可能地緊湊并相互分離。

k-中心算法(k-medoids)不采用簇中對(duì)象的平均值，而是采用簇中心點(diǎn)(medoid)作為參照點(diǎn)。對(duì)象劃分的原則仍與k-平均算法一樣是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和。該算法首先為每個(gè)類隨機(jī)選擇一個(gè)代表對(duì)象，剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配到最近的一個(gè)類中， 然后反復(fù)地用非代表對(duì)象替代代表對(duì)象， 以改進(jìn)聚類的質(zhì)量。

2.基于層次的方法

層次聚類法(hierarchicalcl ustering methods)是一種廣泛應(yīng)用的一種經(jīng)典方法[4]。這種方法的基本思想是:先將n個(gè)樣本各自看成一類(簇)，然后規(guī)定樣本之間的距離和類與類之間的距離。最初每個(gè)樣本自成一類，類與類之間的距離即為樣本之間的距離。然后選擇距離最小的一對(duì)合并為新類，接著計(jì)算新類與其他類之間的距離，再合并間距最小的兩個(gè)類，依次迭代，直到所有的樣本都?xì)w于一類。具體分為兩種:凝聚的(agglomerative)層次聚類和分裂的(divisive)層次聚類。

凝聚的層次聚類是采用自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者某個(gè)終止條件被滿足。絕大多數(shù)層次聚類方法屬于這一類，只是區(qū)別在簇間的相似度定義上。

分裂的層次聚類采用與凝聚的層次聚類相反的策略，首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一個(gè)簇，或達(dá)到某個(gè)終止條件。例如，達(dá)到了預(yù)期的簇的數(shù)量，或者兩個(gè)最近的簇之間的距離超過(guò)了某個(gè)閥值。

3.基于密度的方法

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)是一種典型的基于密度的聚類算法。[5]該算法的基本思想是:一個(gè)類能夠被其中的任意一個(gè)核心對(duì)象所確定，為了發(fā)現(xiàn)一個(gè)類，DBSCAN先從數(shù)據(jù)集D中找到任意一對(duì)象P，并查找數(shù)據(jù)集D中以Eps (半徑)和MinPts (最小密度閥值)為參數(shù)的從對(duì)象P密度可達(dá)的所有對(duì)象。如果P是核心對(duì)象，也就是說(shuō)半徑為Eps的P的鄰域中包含的對(duì)象數(shù)不少于MinPts個(gè)，則根據(jù)算法可以找到一個(gè)關(guān)于參數(shù)Eps和MinPts的類，如果P是一個(gè)邊界點(diǎn)，即半徑為Eps的P的鄰域包含的對(duì)象數(shù)目小于MinPts個(gè)，則沒(méi)有對(duì)象從P密度可達(dá)，P被暫時(shí)標(biāo)注為噪聲點(diǎn)，然后DBSCAN 處理數(shù)據(jù)集D中的下一個(gè)對(duì)象，該算法的時(shí)間復(fù)雜度為O (NlogN) (N是數(shù)據(jù)集中的數(shù)據(jù)對(duì)象數(shù)目)。

4.基于網(wǎng)格的方法

基于網(wǎng)格的(grid-based)聚類方法采用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)。它將空間量化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)格上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是處理速度快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，僅依賴于量化空間中每一維上的單元數(shù)目。基于網(wǎng)格的代表性算法有STING和CLIQUE等。

5.基于模型的方法

基于模型的聚類方法試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)據(jù)模型之間的適應(yīng)性。[6]這類方法經(jīng)常是基于這樣的假設(shè)，即數(shù)據(jù)是根據(jù)潛在的概率分布生成的。基于模型的方法主要包括統(tǒng)計(jì)學(xué)類方法和神經(jīng)網(wǎng)絡(luò)類方法。

三、基于幾何光滑度的案例聚類方法

由于上述算法都存在一些局限性，一般只能發(fā)現(xiàn)凸型的類或是球型的類，而對(duì)于凹形或是任意形狀的類或是具有高度稀疏特性的類就無(wú)能為力，因此，本文提出基于SNN相似度的類似于幾何中自由曲線曲面拼接光滑度計(jì)算(即連接點(diǎn)處若干階左右導(dǎo)數(shù)一致)的聚類算法，即基于幾何光滑度的光滑拼接聚類算法，算法本身可由光滑度參數(shù)來(lái)調(diào)節(jié)。

1.SNN相似度

數(shù)據(jù)對(duì)象之間相似的程度取決于它們共享最近鄰的數(shù)量。任一數(shù)據(jù)對(duì)象的k個(gè)最近鄰組成 一個(gè)最近鄰列表，兩個(gè)對(duì)象之間的共享最近鄰為它們最近鄰列表的交集。特殊地，當(dāng)兩個(gè)對(duì)象的k最近鄰列表完全一致時(shí)，它們的相似程度最大。SNN相似度就是它們共享的近鄰個(gè)數(shù)。計(jì)算SNN相似度可利用下述算法。

2.相關(guān)定義

如前所述，SNN相似度就是它們共享的最近鄰個(gè)數(shù)。通過(guò)算法1我們能夠計(jì)算出所有樣本間的SNN相似度并組成相似度圖。隨后我們可以應(yīng)用到基于SNN的聚類算法中，但是一般的基于SNN的聚類算法如JP聚類[7]和基于SNN密度聚類[8]都存在一個(gè)共同的缺點(diǎn):一個(gè)樣本集是分裂成兩個(gè)類還是保持不變，可能依賴于一條鏈，這使它們顯得有些脆弱。例如，如果有3個(gè)樣本x1，x2，x3，x1和x2有一個(gè)很高的SNN相似度，x2和x3也有一個(gè)很高的SNN相似度，但x1和x3的SNN相似度卻為0，這時(shí)應(yīng)用JP聚類算法或基于SNN密度聚類算法，x1，x2，x3一般會(huì)歸到一類中去。這顯然不是很好的聚類。因?yàn)橹庇^上看，如果這3個(gè)樣本是一類，那么x1和x3也應(yīng)該有一個(gè)較高的SNN相似度，而不至于很快降為0。這類似于幾何中計(jì)算參數(shù)曲線拼接問(wèn)題，如果兩條參數(shù)曲線在拼接點(diǎn)滿足越高階的導(dǎo)數(shù)連續(xù)性，拼接后的曲線就被認(rèn)為越光滑，在直觀上也覺(jué)得它更象一條曲線了。因此，我們根據(jù)幾何中的這種現(xiàn)象提出基于SNN相似度的n階光滑度的定義。在此基礎(chǔ)上再提出光滑拼接聚類算法。

定義1:如果有一條長(zhǎng)鏈，由2n+1個(gè)樣本點(diǎn)x-n，…，x-1，x0，x1，…，xn組成。假設(shè)鏈可表示為:x-n?圮x-n+1?圮…?圮x-1?圮x0?圮x1?圮…?圮xn-1?圮xn，其中，每個(gè)樣本點(diǎn)和其后的樣本點(diǎn)之間的SNN相似度是這兩個(gè)樣本點(diǎn)組成的單鏈強(qiáng)度(大于0)。我們把這個(gè)長(zhǎng)鏈看作是一個(gè)短鏈x-n?圮x-n+1?圮…?圮x-1?圮x0與另一個(gè)短鏈x0?圮x1?圮…?圮xn-1?圮xn在x0處的拼接。如果x-1與x1的SNN相似度不為0，則稱原長(zhǎng)鏈在x0處是1階光滑的;否則稱為0階光滑的;如果x-2，x-1，x1，x2的兩兩SNN相似度都不為0，則稱原長(zhǎng)鏈在x0處是2階光滑的;一直下去，如果有x-n，…，x-1，x1，…，xn兩兩之間SNN相似度都不為0，則稱原長(zhǎng)鏈在x0處是n階光滑的。

定義2:如果有一條長(zhǎng)鏈，由n+1個(gè)樣本點(diǎn)x0，x1，…，xn組成。假設(shè)鏈可表示為:x0?圮x1?圮…?圮xn-1?圮xn，其中，每個(gè)樣本點(diǎn)和其后的樣本點(diǎn)之間的SNN相似度是這兩個(gè)樣本點(diǎn)組成的單鏈強(qiáng)度(大于0)。我們把這個(gè)長(zhǎng)鏈看作是一個(gè)單鏈x0?圮x1與另一個(gè)短鏈x1?圮…?圮xn-1?圮xn在x1處的拼接。如果x0與x2的SNN相似度不為0，則稱原長(zhǎng)鏈在x1處是1階單側(cè)光滑的;否則稱為0階單側(cè)光滑的;如果x0，x2的SNN相似度也不為0，則稱原長(zhǎng)鏈在x1處是2階單側(cè)光滑的;一直下去，如果有x0 ， x1，…，xn兩兩之間SNN相似度都不為0，則稱原長(zhǎng)鏈在x1處是n階單側(cè)光滑的。

3.算法設(shè)計(jì)

通過(guò)算法1我們可以從數(shù)據(jù)集{xi1≤i≤m}中計(jì)算出任意兩個(gè)樣本間的SNN相似度，并組成一個(gè)m×m階的SNN相似度矩陣。從此矩陣中可以找出Cm2個(gè)單鏈，其中，每個(gè)單鏈的強(qiáng)度為兩個(gè)樣本點(diǎn)的SNN相似度。如果兩個(gè)短鏈中含有相同的樣本點(diǎn)，我們可以考慮把它們合并成一條鏈，并檢查這種拼接在拼接點(diǎn)是否滿足s階光滑(如果兩條都是單鏈，則s只能取1)，如果滿足，就合并;否則，它們就不拼接而維持原狀。由于拼接需要考慮光滑度，因此這種拼接聚類不僅僅依賴于單鏈的強(qiáng)度，s值如果過(guò)大，會(huì)導(dǎo)致一些單鏈無(wú)法拼接。這將會(huì)導(dǎo)致類別數(shù)目過(guò)多。假設(shè)已有一個(gè)連通圖，而一條單鏈要在連通圖的一個(gè)節(jié)點(diǎn)處拼接，從這個(gè)節(jié)點(diǎn)出發(fā)在連通圖中可以找到若干條短鏈，這個(gè)單鏈要與這些短鏈在拼接點(diǎn)滿足一個(gè)指定的光滑度。因?yàn)槠唇右写_定的先后順序，以保持實(shí)驗(yàn)結(jié)果的穩(wěn)定，所以我們預(yù)先將單鏈集中的單鏈按強(qiáng)度(即SNN值)由大到小排序。這樣先拼接的單鏈的強(qiáng)度大，但光滑度要求低;后參加拼接的單鏈的強(qiáng)度(同一類內(nèi)而言)越來(lái)越小，但光滑度要求越來(lái)越高。由此可知，這種拼接是強(qiáng)度和光滑度之間互補(bǔ)的。這顯然是合理的，因?yàn)槿绻粋€(gè)樣本點(diǎn)要加入一個(gè)類中，如果和類中的某個(gè)樣本沒(méi)有很大的SNN相似度，那么它至少應(yīng)該和這個(gè)類中的很多樣本有一個(gè)共享最近鄰(SNN值為1)。由于算法內(nèi)含強(qiáng)度和光滑度互補(bǔ)的運(yùn)行機(jī)制，因而算法本身不需要設(shè)置參數(shù)。在拼接過(guò)程中，滿足條件就進(jìn)行拼接，但在第k層節(jié)點(diǎn)拼接之間，我們可以刪除之前的第k-1層節(jié)點(diǎn)的單鏈，因?yàn)檫@些節(jié)點(diǎn)已經(jīng)屬于一類，無(wú)需參加拼接，這樣單鏈集容量就能迅速降低，加快算法。

具體的基于SNN相似度的光滑拼接聚類算法可以描述如下:

四、實(shí)驗(yàn)與分析

本次試驗(yàn)我們采用數(shù)值型數(shù)據(jù)進(jìn)行試驗(yàn)，這樣可以簡(jiǎn)化操作，便于進(jìn)行數(shù)據(jù)進(jìn)行處理，突出我們所采用的聚類算法的有效性。

1.數(shù)據(jù)集

實(shí)驗(yàn)所采用的數(shù)據(jù)集來(lái)源于國(guó)家從2004—2007年全國(guó)總共發(fā)生的洪澇災(zāi)害，總共由100條數(shù)據(jù)點(diǎn)組成。在這個(gè)數(shù)據(jù)集中，我們可以將取值密集但相同的變量去掉，并將一些非數(shù)值文字型的不影響實(shí)驗(yàn)結(jié)果的變量去掉，最終每個(gè)數(shù)據(jù)點(diǎn)都是一個(gè)24維的向量。

2.實(shí)驗(yàn)結(jié)果分析

對(duì)于算法1中我們將最近鄰參數(shù)k取值為常數(shù)6，算法2中光滑度參數(shù)s取定值為1。我們采用算法2進(jìn)行聚類分析，在結(jié)果中我們發(fā)現(xiàn)類別編號(hào)1、3、5、7四個(gè)類是算法所發(fā)現(xiàn)的類，這些類中數(shù)據(jù)點(diǎn)相對(duì)集中，其他還有少量數(shù)據(jù)點(diǎn)的類別均看作是噪聲。并且發(fā)現(xiàn)四級(jí)響應(yīng)級(jí)別數(shù)據(jù)點(diǎn)相對(duì)比較集中。并發(fā)現(xiàn)那些被看做是噪聲的數(shù)據(jù)點(diǎn)一般都是屬于個(gè)別年份離類別較遠(yuǎn)的數(shù)據(jù)點(diǎn)。

聚類分析是數(shù)據(jù)挖掘中的一種非常實(shí)用的技術(shù)，它能夠發(fā)現(xiàn)大量數(shù)據(jù)背后所隱藏的數(shù)據(jù)分布模式與關(guān)聯(lián)規(guī)則，以便提供給我們有價(jià)值的信息。目前聚類算法已經(jīng)應(yīng)用到許多領(lǐng)域，但是仍然存在諸多缺陷。今后，聚類算法將在可伸縮性、容錯(cuò)性、易用性、處理高維數(shù)據(jù)等方面加以提高和改進(jìn)，以便能夠更好地應(yīng)用于更多的領(lǐng)域，解決其他方法不能夠解決的問(wèn)題。

參考文獻(xiàn):

[1] Han JiaWei.Kamber數(shù)據(jù)挖掘概念與技術(shù)[M].北京: 機(jī)械工業(yè)出版社， 2001.

[2] 邵峰晶，于忠清. 數(shù)據(jù)挖掘——原理與算法[M].北京: 中國(guó)水利水電出版社， 2003.

[3] 王實(shí)，高文. 數(shù)據(jù)挖掘中的聚類算法[J].計(jì)算機(jī)科學(xué)，2007， (4): 42-45.

[4] 武森，高學(xué)東. 高維稀疏聚類知識(shí)發(fā)現(xiàn)[M]. 北京: 冶金工業(yè)出版社， 2003.

[5] 周水庚，周傲英，曹晶. 基于數(shù)據(jù)分區(qū)的DBSCAN算法[J]. 計(jì)算機(jī)研究與發(fā)展， 2000，(10): 1153-1159.

[6] Guha， S， R. Rastogi， and K Shim， Rock. A robust clustering algorithm for categorical attributes. Information Systems， 2000，25(5): 345-366.

[7] Abascal E， Garcia Lautre I， Mallor F. Data Mining in a Bicriteria Clustering Problem， 2006:705-716.

[8] MacQueen， J.， Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Symp. on Math. Statist. and Prob.， 1967，(1):281-297.