有效距離在聚類算法中的應(yīng)用*

光俊葉，劉明霞,2，張道強(qiáng)+

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106

2.泰山學(xué)院 信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021

有效距離在聚類算法中的應(yīng)用*

光俊葉1，劉明霞1,2，張道強(qiáng)1+

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106

2.泰山學(xué)院 信息科學(xué)技術(shù)學(xué)院，山東 泰安 271021

聚類；距離度量；度量學(xué)習(xí)；有效距離

1 引言

在如今的大數(shù)據(jù)時(shí)代，人們需要利用成熟的數(shù)據(jù)挖掘技術(shù)處理海量的數(shù)據(jù)，希望從中找到有價(jià)值的信息或模型[1]。聚類分析是數(shù)據(jù)挖掘中不可或缺的常用技術(shù)[2]，在許多領(lǐng)域（例如，醫(yī)學(xué)方面的疾病診斷[3-4]和電力系統(tǒng)方面的安全保障[5]等）有非常重要的利用價(jià)值。

聚類分析的研究歷史比較長遠(yuǎn)，存在很多種類型的聚類算法。其中，K-means是經(jīng)典的基于劃分的聚類算法，但是該算法對(duì)初始聚類中心的選擇非常敏感，易收斂到局部最優(yōu)解，而且聚類簇K的數(shù)目還難以確定，不合適的K值往往會(huì)得到比較差的聚類結(jié)果[6]。于是研究人員不斷提出改進(jìn)算法，希望可以彌補(bǔ)算法存在的不足。例如，Huang提出了K-modes-Huang算法，將傳統(tǒng)K-means拓展到可以處理包含多種不同數(shù)據(jù)類型的大數(shù)據(jù)集的方法[7]。Gupta等人提出的基于文檔的K-means算法可以自動(dòng)進(jìn)行K選擇以及聚類簇的細(xì)化[8]?？紤]到K-means算法利用均值計(jì)算中心點(diǎn)時(shí)噪聲點(diǎn)造成的不利影響，K-medoids算法選擇有代表性的真實(shí)存在的樣本點(diǎn)作為聚類簇的中心。K-means和K-medoids算法都要求一個(gè)樣本屬于且只屬于一個(gè)聚類簇。1969年，Ruspini提出了FCM（fuzzy C-means）聚類算法，指出一個(gè)樣本也可能屬于多個(gè)聚類簇，只是隸屬度不同而已[9]。2002年，Zhang等人引入核方法，不僅將FCM的適用范圍從球形分布拓展到包括非球形的任意分布，而且可以自動(dòng)評(píng)估聚類簇的數(shù)目[10]。2006年，李潔等人提出基于特征加權(quán)的模糊聚類算法（new feature weighted fuzzy clustering algorithm，NFWFCA），可以有選擇性地區(qū)別對(duì)待不同的特征，更加有利于聚類[11]。2007年，Cai等人提出了FGFCM（fast generalized fuzzy C-means）算法，該方法融合了局部空間信息和灰度信息，可以更快更好地進(jìn)行圖像分割[12]。聚類算法在不斷地更新改進(jìn)，雖然在這些算法中距離度量方法都大同小異，但它確實(shí)是至關(guān)重要的一個(gè)步驟。

距離度量可以計(jì)算樣本之間的距離或者相似性，它的優(yōu)劣性在很大程度上影響甚至決定著聚類效果。常用的度量方法是歐氏距離。雖然歐氏距離是簡單并且方便計(jì)算的，但是只考慮了數(shù)據(jù)之間的直接地理距離，忽略了其余有價(jià)值的信息（如拓?fù)鋷缀侮P(guān)系等）。很多學(xué)者嘗試用其他距離進(jìn)行聚類分析。例如，Groenen等人提出的模糊聚類模型中使用明氏距離代替歐氏距離[13]。Xiang等人提出在已知must-link和cannot-link等約束信息的情況下學(xué)習(xí)樣本之間的馬氏距離然后進(jìn)行聚類分析，這種度量方法在圖形分割和臉部識(shí)別等應(yīng)用中都取得了比較好的實(shí)驗(yàn)結(jié)果[14]。Rammal等人對(duì)紅外線光譜聚類進(jìn)行了研究，通過實(shí)驗(yàn)驗(yàn)證了使用L1或曼哈頓距離的實(shí)驗(yàn)結(jié)果優(yōu)于歐氏距離以及切氏距離[15]。新型度量方法的提出可以說是層出不窮。Brockmann等人在探討影響傳染病傳播情況的因素時(shí)，提出了一種不是傳統(tǒng)意義上距離的有效距離度量方法。該距離基于兩地之間由于航空運(yùn)輸導(dǎo)致的人口流動(dòng)比率，發(fā)現(xiàn)各地與病菌發(fā)源地之間的有效距離與病菌到達(dá)相應(yīng)地點(diǎn)的時(shí)間成固定比例，并且利用該有效距離度量方法模擬H1N1和SARS病毒傳播情況與真實(shí)情況十分吻合[16]。綜上所述，不同的距離度量方法有不同的優(yōu)勢，可以從不同的角度描述樣本之間的距離，可能得到不同的聚類結(jié)果。

本文提出了一種充分考慮樣本全局性結(jié)構(gòu)信息的距離度量方法——有效距離度量（effective distance metric），其基本思想是首先通過稀疏重構(gòu)的方法構(gòu)造樣本之間的連接網(wǎng)絡(luò)，然后借鑒Dirk等人提出的基于比率的距離度量方法計(jì)算樣本之間的有效距離。進(jìn)一步地，本文將有效距離應(yīng)用到K-means、K-medoids和FCM經(jīng)典聚類算法中，并且在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，基于有效距離度量的聚類方法有更高的聚類精確度，能夠得到比傳統(tǒng)聚類算法更好的聚類結(jié)果。

本文內(nèi)容安排如下：第2章簡單介紹了與本文相關(guān)的工作；第3章詳細(xì)討論了本文提出的新的基于有效距離的聚類方法；第4章通過多個(gè)實(shí)驗(yàn)驗(yàn)證了本文算法的性能；最后對(duì)本文的工作進(jìn)行總結(jié)和展望。

2 相關(guān)工作

2.1 聚類分析算法

已有的研究中，按照各類標(biāo)準(zhǔn)人們提出了多種聚類算法[6]。其中，K-means、K-medoids、FCM是3種常用的聚類算法。

2.1.1 K-means算法

目前，K-means聚類算法在很多領(lǐng)域中已經(jīng)成為進(jìn)行數(shù)據(jù)分析的主要工具[1]。該聚類算法以對(duì)數(shù)據(jù)集進(jìn)行硬劃分使得聚類的類內(nèi)誤差平方和最小為基本依據(jù)。給定數(shù)據(jù)樣本X=[x1,x2,…,xn]T∈Rn×d,需要聚成c個(gè)簇，用vk(k=1,2,…,c)表示每個(gè)聚類簇的聚類中心，uki=uXk(xi)表示第i個(gè)樣本xi對(duì)第K個(gè)子集XK的隸屬程度，且uki∈{0,1}。設(shè)劃分矩陣U是一個(gè)c×n的矩陣，可以用U=[uki]c×n表示。定義K-means聚類算法的目標(biāo)函數(shù)為：

該算法的目標(biāo)是尋找最優(yōu)對(duì)(U,V)，使得目標(biāo)函數(shù)J1(U,V)取得最小值。

2.1.2 K-medoids算法

K-medoids聚類算法是在K-means聚類算法的基礎(chǔ)上改進(jìn)的。K-means算法利用均值計(jì)算中心點(diǎn)時(shí)容易受到噪聲點(diǎn)或者離群點(diǎn)的影響，K-medoids算法具有較強(qiáng)的魯棒性，它選擇有代表性的真實(shí)存在的樣本點(diǎn)，也就是到當(dāng)前聚類簇中所有其他數(shù)據(jù)樣本的距離之和最小的樣本點(diǎn)，作為聚類簇的中心。

2.1.3 FCM算法

K-means和K-medoids兩種聚類算法是基于“非此即彼”的思想，屬于硬劃分的方法。但是實(shí)際應(yīng)用中，許多問題本身具有一定的模糊不可分性，使用模糊聚類方法處理更加合理。FCM是基于K-means推廣形式的具有代表性的一種模糊聚類算法[17]。1974年，Dunn首次提出了利用模糊C進(jìn)行劃分，引入聚類分析的模糊化情形[18]，其提出的算法的核心思想是根據(jù)模糊劃分求得劃分矩陣U，并用隸屬度的平方值對(duì)每個(gè)數(shù)據(jù)樣本與每個(gè)聚類中心點(diǎn)之間的距離進(jìn)行加權(quán)，從而得到一個(gè)新的目標(biāo)函數(shù)：

1981年，Bezdek對(duì)此方法進(jìn)行了完善，并將其推廣到更為普遍的表示形式[19]，即將式（2）中的目標(biāo)函數(shù)J2進(jìn)行進(jìn)一步的推廣，定義了模糊C-均值聚類算法的目標(biāo)函數(shù)為：

其中，m∈[1,∞)稱作模糊加權(quán)指數(shù)（或平滑參數(shù)），數(shù)據(jù)樣本的隸屬度取值為[0,1]區(qū)間內(nèi)的任何一個(gè)實(shí)數(shù)。FCM聚類算法的基本依據(jù)是“類內(nèi)加權(quán)誤差平方和最小化”準(zhǔn)則。

2.2 距離度量

2.2.1 傳統(tǒng)的距離度量方法

常用的距離度量有歐氏距離、絕對(duì)值距離、切氏距離、明氏距離、馬氏距離和歸一化距離等。這里簡單介紹歐氏距離的具體度量方法。

設(shè)a=(a1,a2,…,ad)，b=(b1,b2,…,bd)為兩個(gè)樣本，則它們之間的歐氏距離定義為：

歐氏距離是使用最為廣泛、最簡單的距離度量，而且歐氏距離具有平移和旋轉(zhuǎn)不變性。

2.2.2 有效距離

近幾年，全球氣候的反常變化導(dǎo)致了很多傳染性病毒的肆意傳播，比如2003年的SARS病毒和2009年的H1N1病毒。2013年，Brockmann等人在探討影響傳染病傳播情況的因素時(shí)，提出了一種不是傳統(tǒng)意義上距離的有效距離度量方法。該距離基于兩地之間由于航空運(yùn)輸導(dǎo)致的人口流動(dòng)比率，發(fā)現(xiàn)各地與病菌發(fā)源地之間的有效距離與病菌到達(dá)相應(yīng)地點(diǎn)的時(shí)間成固定比例。而且利用該有效距離度量方法模擬H1N1和SARS病毒傳播情況與真實(shí)情況十分吻合[16]。以真實(shí)病菌傳播情況為例，該有效距離度量方法還可以成功地挖掘出傳染病菌的傳播源，并且預(yù)測傳染病菌未來的傳播狀態(tài)。而簡單的歐氏距離度量在這些案例中沒有辦法達(dá)到滿意的效果。這些事實(shí)說明，現(xiàn)實(shí)世界中兩個(gè)事物之間的距離實(shí)際上不僅僅取決于幾何坐標(biāo)中的歐氏距離或者地理距離。度量兩個(gè)事物之間的距離時(shí)，除了考慮這兩個(gè)事物之間的關(guān)系之外，還要考慮與這兩個(gè)事物相關(guān)的其余事物對(duì)它們的影響，也就是要考慮數(shù)據(jù)的全局結(jié)構(gòu)信息。

因此，本文提出了通過概率形式反映樣本之間全局性結(jié)構(gòu)信息的有效距離度量方法。具體的有效距離示意圖如圖1所示。假設(shè)有4個(gè)數(shù)據(jù)樣本點(diǎn)A、B、C、D。圖1（a）是4個(gè)樣本點(diǎn)之間的有向關(guān)系圖，圖中各邊所占的權(quán)重值相等。圖1（b）中，通過計(jì)算概率值P(n|m)表示有向圖中樣本點(diǎn)之間各邊所占的權(quán)重，而且圖中邊的寬度越寬，表示其權(quán)重越大。概率值P(n|m)表示從m點(diǎn)出發(fā)到達(dá)n點(diǎn)的直接路徑數(shù)與所有從m點(diǎn)出發(fā)的直接路徑數(shù)的比值。例如，概率值P(B|A)=1/4，表示從A點(diǎn)到B點(diǎn)的概率是1 4，其中4表示從A點(diǎn)出發(fā)的路徑總共有4條，1表示其中有1條路徑可以直接到達(dá)B點(diǎn)。另外，從圖1（b）中容易看出，從B點(diǎn)出發(fā)到達(dá)D點(diǎn)的概率（如P(D|B)=1）明顯大于從C點(diǎn)出發(fā)到達(dá)D點(diǎn)的概率（如P(D|C)=1/5）。根據(jù)Brockmann等人提出的有效距離思想[16]，概率值P(n|m)越小表示從m點(diǎn)到n點(diǎn)的有效距離就越大，反之亦然。跟常見的歐氏距離或者地理距離相比，有效距離因?yàn)榭紤]了數(shù)據(jù)樣本間的全局性結(jié)構(gòu)信息，所以更能體現(xiàn)出數(shù)據(jù)樣本之間隱藏的模式結(jié)構(gòu)信息。因此，用有效距離度量方法代替歐氏距離，能更全面地展示樣本之間的關(guān)聯(lián)信息，而完全不受樣本分布、地理距離等因素的影響。

Fig.1 Graphical explanation of effective distance圖1 有效距離示意圖

3 基于有效距離的聚類算法

3.1 基于稀疏表示的有效距離的計(jì)算

近年來，稀疏表示在機(jī)器學(xué)習(xí)、模式識(shí)別[20]和計(jì)算機(jī)視覺[21]等領(lǐng)域得到越來越廣泛的應(yīng)用。稀疏表示可以構(gòu)建高效的數(shù)據(jù)表示，作為從數(shù)據(jù)本身學(xué)習(xí)到的幾個(gè)典型（原子）模式的一個(gè)組合（通常為線性的），很多基于稀疏表示的方法取得了令人鼓舞的成果[22]。如前所述，有效距離度量方法能夠考慮數(shù)據(jù)樣本之間的全局性信息。值得注意的是，稀疏表示方法能夠有效表達(dá)數(shù)據(jù)的全局特性?；谙∈璞硎镜倪@一特性，本文提出了一種基于稀疏表示的有效距離計(jì)算方法。

假設(shè)需要處理2.1.1小節(jié)中描述的樣本集。構(gòu)建數(shù)據(jù)樣本之間有效距離的具體步驟如下：

（1）根據(jù)數(shù)據(jù)樣本之間在稀疏表示過程中所占的權(quán)重系數(shù)構(gòu)建有向圖。

式（5）中B=[x1,x2,…,xi-1,xi+1,…,xn]T表示樣本xi從X中移除。

根據(jù)式（5）計(jì)算求得權(quán)重系數(shù)矩陣W=[w1,w2,…,wn]T，Wij表示樣本xi在稀疏表示樣本xj的過程中所占的權(quán)重值。λ是稀疏表示過程中的正則化參數(shù)λ∈(0,1]，λ越大則矩陣越稀疏。

（2）求數(shù)據(jù)樣本間歸一化后的權(quán)重系數(shù)。

根據(jù)式（6）得到歸一化的權(quán)重系數(shù)矩陣P。Pij越大，說明xi在稀疏重建xj時(shí)，所占的權(quán)重越大，也就表示xi在xj的所有近鄰中位置更靠前，xi與xj之間的相似度越大，有效距離越小。

（3）計(jì)算樣本之間的有效距離。

根據(jù)式（7）得到有效距離矩陣ED。因?yàn)?≤Pij≤1，所以lnPij≤0，顯然EDij≥1。

3.2 基于有效距離的聚類算法

本文通過將有效距離應(yīng)用到K-means、K-medoids和FCM經(jīng)典聚類算法中，開發(fā)了3種基于有效距離的聚類算法，即EK-means、EK-medoids和EFCM聚類算法。

3.2.1 基于有效距離的K-means聚類算法

傳統(tǒng)的K-means聚類算法一般利用歐氏距離評(píng)估兩個(gè)數(shù)據(jù)樣本之間的相似性，考慮到有效距離的思想后，提出了基于有效距離的K-means——EK-means聚類算法。

EK-means聚類算法的目標(biāo)函數(shù)為：

其中，Dij為數(shù)據(jù)樣本xi距離聚類簇的中心vj的有效距離，并且

式（9）以及接下來的式（10）、（11）中m表示該聚類簇所包含的數(shù)據(jù)樣本的個(gè)數(shù)；rjq表示屬于該聚類簇的第q個(gè)數(shù)據(jù)樣本在原始數(shù)據(jù)樣本中的編號(hào)。

EK-means算法的具體流程如下。

算法1基于有效距離的K-means聚類算法

3.2.2 基于有效距離的K-medoids聚類算法

傳統(tǒng)的K-medoids聚類算法一般利用歐氏距離評(píng)估數(shù)據(jù)樣本之間的相似性，考慮到有效距離的思想后，提出了基于有效距離的K-medoids——EK-medoids聚類算法。

EK-medoids算法的具體流程與K-means的流程大致相同。不同之處在于，第二步要利用得到的有效距離矩陣ED構(gòu)造相似性矩陣A∈Rn×n，矩陣中的元素定義如下：

另外需要注意的是簇中心樣本更新方法的不同。傳統(tǒng)的K-medoids聚類算法中，計(jì)算第i個(gè)聚類簇的新聚類中心的方法如下：

在EK-medoids算法中應(yīng)該用下面公式來計(jì)算：

這樣，第i個(gè)聚類簇的新聚類中心vi=xrij。其中j的取值范圍均為0≤j≤m。

3.2.3 基于有效距離的FCM聚類算法

FCM是一種柔性的模糊劃分。隸屬度uki的迭代更新方法為：

其中，uki(1 ≤k≤c,1≤i≤n)表示第i個(gè)樣本xi屬于第k個(gè)聚類簇的隸屬函數(shù)。dki表示數(shù)據(jù)樣本xi與第k個(gè)聚類簇的聚類中心之間的距離。

EFCM聚類算法的具體流程如下。

算法2基于有效距離的FCM聚類算法

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)中利用稀疏表示構(gòu)建數(shù)據(jù)樣本之間的有向圖，其中正則化參數(shù)λ∈[0.10,0.95]，每次取值間隔0.5。FCM中的模糊加權(quán)指數(shù)取通用值2。實(shí)驗(yàn)最終將聚類后的結(jié)果與傳統(tǒng)算法的結(jié)果進(jìn)行對(duì)比，把聚類的正確精度作為實(shí)驗(yàn)結(jié)果，同時(shí)要求正確率與聚類效果是正相關(guān)的。另外，考慮到程序每次運(yùn)行時(shí)聚類中心有不同的初始化，對(duì)每個(gè)算法重復(fù)運(yùn)行了50次，然后將50次的平均值作為最終的聚類結(jié)果。其中，有關(guān)有效距離實(shí)驗(yàn)的最終結(jié)果是取不同λ對(duì)應(yīng)的聚類精度中的最大值。

4.2 實(shí)驗(yàn)結(jié)果與分析

在10個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了基于傳統(tǒng)歐氏距離的聚類算法和基于有效距離的聚類算法的對(duì)比實(shí)驗(yàn)。

表1首先描述了實(shí)驗(yàn)中所涉及到的10個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集，包括每個(gè)數(shù)據(jù)集中數(shù)據(jù)樣本的維數(shù)、個(gè)數(shù)以及聚類簇?cái)?shù)目等情況。然后展示了EK-means聚類算法與K-means聚類算法、EK-medoids聚類算法與K-medoids聚類算法、EFCM聚類算法與FCM聚類算法分別在這些數(shù)據(jù)集上的聚類結(jié)果。從表1的聚類結(jié)果可以看出，在UCI標(biāo)準(zhǔn)數(shù)據(jù)集下，基于有效距離的聚類算法結(jié)果絕大部分都要優(yōu)于基于歐氏距離的聚類算法。

圖2是各種算法對(duì)比的箱形圖。該圖非常直觀地描述了K-means與EK-means、K-medoids與EK-medoids，F(xiàn)CM與EFCM聚類算法在10個(gè)UCI數(shù)據(jù)集上的聚類結(jié)果比較情況。圖2中一個(gè)箱形對(duì)應(yīng)的橫線從下到上依次為：下邊緣線、下四分位線、中位數(shù)線、上四分位線以及上邊緣線。從圖2可以明顯看出，所有的基于有效距離的算法的各條線都比傳統(tǒng)的聚類算法的對(duì)應(yīng)線要高，體現(xiàn)了新算法明顯優(yōu)于傳統(tǒng)算法。

Table 1 UCI datasets and comparision of algorithms表1 UCI數(shù)據(jù)集介紹以及算法結(jié)果比較

Fig.2 Clustering results圖2 聚類算法結(jié)果對(duì)比

5 總結(jié)與展望

本文提出了一種充分考慮樣本之間的全局結(jié)構(gòu)信息的有效距離度量方法。進(jìn)一步地，對(duì)提出的3種基于有效距離的聚類算法，包括EK-means、EK-medoids以及EFCM方法，在標(biāo)準(zhǔn)UCI Benchmark數(shù)據(jù)集上進(jìn)行了聚類實(shí)驗(yàn)，并通過實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的有效性。在未來的研究中，擬嘗試尋找更有意義的距離度量，希望可以更好地完善聚類算法，提高聚類算法的性能。

[1]Xu Rui,Wunsch D.Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks,2005,16(3):645-678.

[2]Shirkhorshidi A S,Aghabozorgi S,Wah T Y,et al.Big data clustering:a review[C]//LNCS 8583:Proceedings of the 14th International Conference on Computational Science and Its Applications,Guimar?es,Portugal,Jun 30-Jul 3, 2014.Berlin,Heidelberg:Springer,2014:707-720.

[3]Shi Jinlong,Luo Zhigang.Nonlinear dimensionality reduction of gene expression data for visualization and clustering analysis of cancer tissue samples[J].Computers in Biology and Medicine,2010,40(8):723-732.

[4]Sebiskveradze D,Vrabie V,Gobinet C,et al.Automation of an algorithm based on fuzzy clustering for analyzing tumoral heterogeneity in human skin carcinoma tissue sections[J]. Laboratory Investigation,2011,91(5):799-811.

[5]Kalyani S,Swarup K S.Particle swarm optimization basedK-means clustering approach for security assessment in power systems[J].Expert Systems with Applications,2011, 38(9):10839-10846.

[6]Sun Jigui,Liu Jie,Zhao Liayu.Clustering algorithms research[J].Journal of Software,2008,19(1):48-61.

[7]Huang Zhexue.Extensions to theK-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery,1998,2(3):283-304.

[8]Gupta H,Srivastava R.K-means based document clustering with automatic“K”selection and cluster refinement[J].International Journal of Computer Science and Mobile Applications,2014,2(5):7-13.

[9]Ruspini E H.A new approach to clustering[J].Information and Control,1969,15(1):22-32.

[10]Zhang Daoqiang,Chen Songcan.Fuzzy clustering using kernel method[C]//Proceedings of the 8th IEEE Interna-tional Conference on Control and Automation,Xiamen, China,Jun 19,2002.Piscataway,USA:IEEE,2002:123-127.

[11]Li Jie,Gao Xinbo,Jiao Licheng.A new feature weighted fuzzy clustering algorithm[C]//LNCS 3641:Proceedings of the 10th International Conference on Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing,Regina,Canada, Aug 31-Sep 3,2005.Berlin,Heidelberg:Springer,2005:412-420.

[12]Cai Weiling,Chen Songcan,Zhang Daoqiang.Fast and robust fuzzy C-means clustering algorithms incorporating local information for image segmentation[J].Pattern Recognition,2007,40(3):825-838.

[13]Groenen P J F,Jajuga K.Fuzzy clustering with squared Minkowski distances[J].Fuzzy Sets and Systems,2001,120 (2):227-237.

[14]Xiang Shiming,Nie Feiping,Zhang Changshui.Learning a Mahalanobis distance metric for data clustering and classification[J].Pattern Recognition,2008,41(12):3600-3612.

[15]Rammal A,Perrin E,Vrabie V,et al.Optimal preprocessing and FCM clustering of MIR,NIR and combined MIR-NIR spectra for classification of maize roots[C]//Proceedings of the 3rd International Conference on E-Technologies and Networks for Development,Apr 29-May 1,2014.Piscataway, USA:IEEE,2014:110-115.

[16]Brockmann D,Helbing D.The hidden geometry of complex,network-driven contagion phenomena[J].Science,2013, 342(6164):1337-1342.

[17]FahadA,Alshatri N,Tari Z,et al.Asurvey of clustering algorithms for big data:Taxonomy and empirical analysis[J]. IEEE Transactions on Emerging Topics in Computing,2014, 2(3):267-279.

[18]Dunn J C.Well-separated clusters and optimal fuzzy partitions[J].Journal of Cybernetics,1974,4(1):95-104.

[19]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].Secaucus,USA:Springer-Verlag New York,Inc,1981.

[20]Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2009,31(2):210-227.

[21]Yang Jianchao,Wright J,Huang T S,et al.Image superresolution via sparse representation[J].IEEE Transactions on Image Processing,2010,19(11):2861-2873.

[22]Xie Yuan,Zhang Wensheng,Qu Yangyun,et al.Discriminative subspace learning with sparse representation viewbased model for robust visual tracking[J].Pattern Recognition,2014,47(3):1383-1394.

GUANG Junye was born in 1991.She is an M.S.candidate at Nanjing University of Aeronautics and Astronautics. Her research interests include machine learning,data mining and pattern recognition,etc.

光俊葉（1991—），女，南京航空航天大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，模式識(shí)別等。

LIU Mingxia was born in 1981.She received the Ph.D.degree from Nanjing University of Aeronautics and Astronautics in 2015.Her research interests include machine learning,data mining and medical image processing,etc.

劉明霞（1981—），女，2015年于南京航空航天大學(xué)獲得博士學(xué)位，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，醫(yī)學(xué)圖像處理等。

ZHANG Daoqiang was born in 1978.He is a professor and Ph.D.supervisor at Nanjing University of Aeronautics and Astronautics.His research interests include machine learning,pattern recognition,data mining and medical image processing,etc.

張道強(qiáng)（1978—），男，南京航空航天大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，模式識(shí)別，數(shù)據(jù)挖掘，醫(yī)學(xué)圖像處理等。

Application of Effective Distance in ClusteringAlgorithms*

GUANG Junye1,LIU Mingxia1,2,ZHANG Daoqiang1+
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
2.College of Information Science and Technology,Taishan University,Taian,Shandong 271021,China
+Corresponding author:E-mail:dqzhang@nuaa.edu.cn

Distance metric learning is a key step in clustering analysis,which is an important sub-domain of data mining. Euclidean distance metric is a quite commonly used local distance metric in clustering algorithms,which only focuses on the distance between two samples.This paper proposes a new global distance metric method,named as the effective distance metric.In the new method,the similarity between two samples is evaluated by using not only the distance between these two samples,but also distances between one specific sample and all the other related ones.Sparse reconstruction coefficients are employed to reflect such global relationship among samples.Then,this paper develops three effective distance-based clustering algorithms,including EK-means,EK-medoids and EFCM,by applying the effective distance to three classical clustering algorithms,i.e.,K-means,K-medoids and FCM(fuzzy C-means),respectively. The experimental results on UCI benchmark datasets demonstrate the efficacy of the proposed methods.

clustering;distance metric;metric learning;effective distance

10.3778/j.issn.1673-9418.1603046

A

：TP181

*The National Natural Science Foundation of China under Grant Nos.61422204,61473149(國家自然科學(xué)基金);the Open Foundation of Graduate Innovation Center in NUAAunder Grant No.kfjj20151605(南京航空航天大學(xué)研究生創(chuàng)新實(shí)驗(yàn)室開放基金).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-04-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160419.1143.006.html

GUANG Junye,LIU Mingxia,ZHANG Daoqiang.Application of effective distance in clustering algorithms. Journal of Frontiers of Computer Science and Technology,2017,11(3)：406-413.

摘 要：聚類分析是數(shù)據(jù)挖掘領(lǐng)域的重要組成部分之一，而度量學(xué)習(xí)是聚類分析中的關(guān)鍵性步驟。傳統(tǒng)聚類算法中通常使用歐氏距離進(jìn)行距離度量，但是歐氏距離只關(guān)注兩兩樣本之間的距離關(guān)系，并沒有顧及數(shù)據(jù)的全局性分布結(jié)構(gòu)?？紤]到數(shù)據(jù)的全局性結(jié)構(gòu)信息，提出了一種新的具有全局性的度量方法——有效距離度量（effective distance metric），其主要思想是通過稀疏重構(gòu)的方法計(jì)算數(shù)據(jù)樣本之間的有效距離。進(jìn)一步地，將有效距離應(yīng)用到K-means、K-medoids和FCM（fuzzy C-means）3種經(jīng)典聚類算法中開發(fā)了3種基于有效距離的聚類算法，即EK-means，EK-medoids和EFCM聚類算法。通過與傳統(tǒng)聚類算法在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果進(jìn)行比較，驗(yàn)證了基于有效距離的聚類算法能顯著提高聚類效果。