不同相似度度量方式的隨機(jī)數(shù)據(jù)聚類分析

李 中，張鐵峰

(華北電力大學(xué) 電氣與電子工程學(xué)院，河北 保定 071003)

0 引言

聚類是按照某個(gè)特定標(biāo)準(zhǔn) (一般為距離準(zhǔn)則)把一個(gè)數(shù)據(jù)集分割成不同的類或簇，使得類內(nèi)相似性盡可能的大，同時(shí)類間的差異性也盡可能的大。聚類過程通常包括數(shù)據(jù) (或樣本、或模式)準(zhǔn)備、特征選擇與特征提取、相似度 (接近度)計(jì)算、聚類 (或分組)和有效性評估等步驟[1]。聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要研究內(nèi)容之一。

根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應(yīng)用這些規(guī)則的方法，有多種聚類算法。聚類算法的聚類結(jié)果有一定的不可預(yù)見性，在實(shí)際應(yīng)用中應(yīng)根據(jù)數(shù)據(jù)類型選擇合適的聚類算法和恰當(dāng)?shù)南嗨菩远攘糠绞剑匀〉米罴训木垲愋Ч鸞2，3]。

本文先就相似度有關(guān)概念及其主要度量方法等方面進(jìn)行了介紹，概述了考慮數(shù)據(jù)向量間差值特征的形狀相似距離 (Shape similarity distance，SSD)的有關(guān)工作，接著分別以經(jīng)典的曼哈頓距離(Manhattan distance，or City block distance，or L1)和歐幾里得距離 (Euclidean distance，or L2)以及形狀相似距離作為相似度度量方式，基于標(biāo)準(zhǔn)模糊C均值聚類 (fuzzy c-means，F(xiàn)CM)算法，在多個(gè)表示矩形對象的二維隨機(jī)數(shù)據(jù)集上進(jìn)行聚類，統(tǒng)計(jì)分析所得聚類結(jié)果，最后給出了相應(yīng)的結(jié)論。

1 相似度及其度量

相似度的研究起始于心理學(xué)，是人類判斷決策和解決問題的重要工具[4]。在聚類分析、模式識別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等計(jì)算機(jī)應(yīng)用領(lǐng)域中，如何確定對象的相似度是一個(gè)非常重要的基礎(chǔ)問題[5，6]。非正式地，兩個(gè)對象之間的相似度是這兩個(gè)對象相似程度的數(shù)值度量，兩者越相似，它們的相似度就越高，相似度是非負(fù)的，并常常在0(不相似)和1(完全相似)之間取值。

面向不同具體問題，相似度評估具有不同表現(xiàn)形式。常用相似系數(shù) (Similarity Coefficient)度量包含二元屬性的對象之間的相似性;用余弦相似度 (Cosine Similarity)分析文檔的相似性;社會(huì)學(xué)中普遍采用統(tǒng)計(jì)方法分析變量間關(guān)系密切程度，最常用的是線性相關(guān)系數(shù) (Linear Correlation Coefficient)，也被稱為皮爾森相關(guān)系數(shù)等。大多情況下，通過計(jì)算對象間距離的方法評估相似度:距離越小，相似度越大。用于相似度評估的距離有多種，通常滿足對稱性和非負(fù)性，但三角不等式或類似的性質(zhì)有時(shí)并不成立，其中最著名應(yīng)用也最廣泛的是歐幾里得距離和曼哈頓距離，其他較常用的還有如考慮屬性相關(guān)的馬哈拉諾比斯距離 (Mahalanobis distance)。此外，還有不少學(xué)者對上述距離加權(quán)處理，以適于不同情況下的相似度度量需求[7，8]。

2 形狀相似距離

經(jīng)典的歐幾里得距離和曼哈頓距離根據(jù)向量差值之間的絕對值計(jì)算得出，沒有考慮向量各維差值的具體情況 (如各維差值的符號)。那么，向量差值的不同情況對向量間的相似度評估是否存在影響、以及會(huì)產(chǎn)生什么樣的影響，是一個(gè)值得研究的問題。文獻(xiàn)[9，10]對此問題進(jìn)行了部分研究，結(jié)果表明當(dāng)向量各維值取自對象的某些特征尺寸時(shí) (如Iris數(shù)據(jù)，分別取自3種不同鳶尾屬植物花朵樣本萼片和花瓣的長度及寬度)，向量差值的一些特征能夠表達(dá)對象形狀差異大小，并基于向量差值特征，對歐幾里得距離進(jìn)行修正，提出形狀相似距離用于相似度的度量。形

式中:L2為xj與xk之間的歐幾里得距離;L1為xj與xk之間的曼哈頓距離，ASD是xj與xk之間的差值和絕對值 (absolute sum of the differences)，其定義為

文獻(xiàn)[9]分析了向量差值與對象形狀相似之間的近似關(guān)系，定義了形狀相似距離，并應(yīng)用該距離在Iris數(shù)據(jù)集上進(jìn)行有監(jiān)督的K-means聚類，結(jié)果表明形狀相似距離在該測試集的相似度評估精度優(yōu)于經(jīng)典的曼哈頓距離和歐幾里得距離。文獻(xiàn)[10]提出了基于形狀相似距離的 K-means算法 (SSD-K-means)，并在3個(gè)UCI(University of California at Irvine)知名數(shù)據(jù)集上進(jìn)行聚類，結(jié)果表明涉及有關(guān)形狀或位置信息的聚類分析中，SSD-K-means算法相比基于經(jīng)典的歐幾里得距離和曼哈頓距離的K-means算法，具有更高的準(zhǔn)確度。

3 仿真實(shí)驗(yàn)

本文用二維向量的兩個(gè)屬性值分別表示矩形對象的寬和高，基于不同相似度度量方法對二維數(shù)組進(jìn)行聚類，根據(jù)矩形對象的聚類結(jié)果分析、對比不同相似度度量方法的性能。實(shí)驗(yàn)方法是隨機(jī)產(chǎn)生的二維數(shù)組 (表示多個(gè)矩形對象)作為測試數(shù)據(jù)，用標(biāo)準(zhǔn)FCM聚類算法，分別采用曼哈頓距離、歐幾里得距離形狀相似距離作為相似度度量方法，對各組測試數(shù)據(jù)進(jìn)行聚類，記錄各種相似度度量方式下的聚類結(jié)果，對聚類結(jié)果進(jìn)行分類后，采用統(tǒng)計(jì)的方法，分析、對比3種相似度度量方式的性能。本文實(shí)驗(yàn)的計(jì)算機(jī)環(huán)境為:處理器為AMD Athlon 2.61GHz，內(nèi)存2GB，硬盤120 G，操作系統(tǒng)為 WindowsXP，編程語言為MATLAB 7.01。

3.1 聚類過程

首先，隨機(jī)產(chǎn)生20組隨機(jī)測試數(shù)據(jù)，每組測試數(shù)據(jù)包含了的300個(gè)取值范圍為0－1的隨機(jī)二維數(shù)組。隨后，分別依據(jù)曼哈頓距離、歐幾里得距離和形狀相似距離，作為FCM聚類的相似度度量依據(jù) (即d2ij)，對每個(gè)測試數(shù)據(jù)集進(jìn)行兩次FCM聚類，分類數(shù) (c)分別取2和3。FCM聚類的初始參數(shù)設(shè)置為:ε=0.000 1，μij初始值隨機(jī)產(chǎn)生，m=2。

3.2 聚類結(jié)果

每組測試數(shù)據(jù)分別3種不同距離標(biāo)準(zhǔn)，進(jìn)行兩次聚類，可得到6個(gè)聚類結(jié)果，20組測試數(shù)據(jù)合計(jì)得到120個(gè)。圖1和圖2分別顯示了同一組測試數(shù)據(jù)聚類分類數(shù)為2和3的聚類結(jié)果。

圖1 一組測試數(shù)據(jù)基于不同相似度度量方式的FCM(c=2)聚類結(jié)果Fig.1 One test dataset FCM(c=2)clustering results based on different similarity measures

圖2 一組測試數(shù)據(jù)集基于不同相似度度量方式的FCM(c=3)聚類結(jié)果Fig.2 One test dataset FCM(c=3)clustering results based on different similarity measures

4 結(jié)果分析

為便于分析，我們根據(jù)同類數(shù)據(jù)分布的區(qū)域?qū)Ω鞔尉垲惤Y(jié)果進(jìn)行分類。當(dāng)把測試數(shù)據(jù)劃分為兩類 (即c=2)時(shí)，觀察兩類二維數(shù)據(jù)向量在二維空間中的分布，依據(jù)同類點(diǎn)分布區(qū)域的特征，本文將所有20個(gè)測試數(shù)據(jù)集的聚類結(jié)果分為4類，分別定義為類型A，B，C和D，各類型分布示意圖見圖3。如圖1中基于3種相似度度量方式的聚類結(jié)果由左至右依次分類屬于類型A，B和C。

類型A，兩類測試數(shù)據(jù)大體分布在上、下兩個(gè)部分，分別標(biāo)記為Cluster 1和Cluster 2。粗略地，Cluster 1中的點(diǎn)的縱坐標(biāo)值大于0.5，Cluster 2中的點(diǎn)的縱坐標(biāo)值小于0.5。近似地可理解為:二維數(shù)組表示的矩形按照其大高度的大小進(jìn)行分類。

類型 B，測試數(shù)據(jù)大體分為左 (Cluster 1)和右 (Cluster 2)兩個(gè)部分，Cluster 1中點(diǎn)的橫坐標(biāo)值小于0.5，而Cluster 2中點(diǎn)的縱坐標(biāo)值大于0.5。近似地，矩形按照其寬度的大小進(jìn)行分類。

圖3 測試數(shù)據(jù)集FCM(c=2)聚類結(jié)果的4種類型Fig.3 Four types of test dataset FCM(c=2)clustering

類型C，兩類測試數(shù)據(jù)大體分布在左上和右下兩個(gè)近似的直角三角形中。其中，Cluster 1中的點(diǎn)pj(x，y)和Cluster 2中的點(diǎn)pk(x，y)的坐標(biāo)近似滿足以下約束:

由此可見，Cluster 1中的測試數(shù)據(jù)表示的矩形高度大于其寬度，即形狀是窄長的矩形，Cluster 2中的矩形高度小于其寬度，即形狀是扁寬的矩形。

類型D，二維數(shù)組大體分布在右上、左下兩個(gè)近似直角三角形中，顯然兩類數(shù)據(jù)包含了形狀各異的矩形。

進(jìn)一步分析上述4類聚類結(jié)果，發(fā)現(xiàn)在類型A，B和D中，同一類中包含了高度大于、等于和小于寬度的形狀不同的矩形，而類型C中，兩類結(jié)果分別表示了窄長的矩形和扁寬的矩形，可認(rèn)為這一聚類結(jié)果是依據(jù)矩形的形狀進(jìn)行了分類。

同樣方法，當(dāng)把測試數(shù)據(jù)劃分為3類 (即c=3)時(shí)，依據(jù)同類點(diǎn)大體構(gòu)成的形狀，歸納所有20個(gè)測試數(shù)據(jù)集聚類結(jié)果，能夠分成5類，分別定義為類型A，B，C，D和E，其分布示意圖見圖4。

圖4 隨機(jī)數(shù)據(jù)FCM(c=3)聚類結(jié)果的五種類型Fig.4 Five types of random data FCM(c=3)clustering

分析圖4易知，類型 A，B，C和 D均包含了的形狀不同的矩形，而類型E中，Cluster 1中的點(diǎn)的橫坐標(biāo)值小于其縱坐標(biāo)，對應(yīng)了形狀窄長的矩形，Cluster 2中的點(diǎn)的縱坐標(biāo)值近似等于橫坐標(biāo)，對應(yīng)了長和高近似相等的矩形，即正方形，Cluster 3中的點(diǎn)的橫坐標(biāo)值大于縱坐標(biāo)，對應(yīng)了形狀是扁寬的矩形?？梢婎愋虴的聚類結(jié)果是考慮了矩形的形狀相似因素進(jìn)行的分類。

按照上述分類方法，將所有測試數(shù)據(jù)的聚類結(jié)果進(jìn)行分類并做記錄。表1記錄了分類數(shù)為2時(shí)，3種相似度度量方式的聚類結(jié)果統(tǒng)計(jì)信息?；诼D距離和歐幾里得距離的聚類結(jié)果在4種類型中均有出現(xiàn)，基于形狀相似距離的聚類都?xì)w納在類型C中。

表1 不同相似度度量方式的FCM(c=2)聚類結(jié)果統(tǒng)計(jì)Table 1 The statistics results of FCM(c=2)using different similarity measures

表2記錄了分類數(shù)為3時(shí)，3種相似度度量方式的聚類結(jié)果統(tǒng)計(jì)信息。基于曼哈頓距離和歐幾里得距離的聚類結(jié)果在類型A，B，C和D中均有出現(xiàn)，但沒有出現(xiàn)類型E中，而基于形狀相似距離的聚類都?xì)w納在類型E中。

表2 不同相似度度量方式的FCM(c=3)聚類結(jié)果統(tǒng)計(jì)Table 2 The statistics results of FCM(c=3)using different similarity measures

表1和表2表明基于經(jīng)典距離與形狀相似距離的聚類結(jié)果有明顯的差異。無論聚類分類數(shù)是2或3，所有依據(jù)形狀相似距離為相似度度量方式的聚類結(jié)果都?xì)w為考慮矩形對象形狀相似因素的類型中。

5 結(jié)論

如何計(jì)算對象間的相似度，在聚類分析、模式識別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等計(jì)算機(jī)研究和應(yīng)用領(lǐng)域中是一個(gè)重要的研究課題。本文分別采用經(jīng)典的曼哈頓距離、歐幾里德距離和形狀相似距離作為相似性度量依據(jù)，在多個(gè)表示矩形對象的二維隨機(jī)數(shù)據(jù)集上進(jìn)行FCM聚類。聚類結(jié)果的分類統(tǒng)計(jì)分析表明，相比經(jīng)典距離，形狀相似距離能夠考慮矩形對象的形狀相似因素進(jìn)行相似度評估。

[1]Gelbard R，Goldman O，Spiegler I．Investigating diversity of clustering methods: An empirical comparison[J]．Data＆ Knowledge Engineering，2007，63(1):155－166．

[2]Sambasivam S，Theodosopoulos N．Advanced data clustering methods of mining Web documents[J]．Issues in Informing Science and Information Technology，2006，(3):563－579．

[3]孫吉貴，劉杰，趙連宇．聚類算法研究[J]．軟件學(xué)報(bào)，2008，19(1):48－61．

[4]Tversky A．Features of similarity[J]．Psychological Review，1977，84(4):327－352．

[5]Jain A K，Murty M N，F(xiàn)lynn P J．Data clustering:A review．ACM Computing Surveys[J]，1999，31(3):264－323．

[6]Jiawei H，Micheline K．Data mining:Concepts and techniques，2nd ed[M]．Morgan Kaufmann Publishers，2006．

[7]Wang D F，Yeung D S，Tsang E C C．Weighted mahalanobis distance kernels for support vector machines[J]．IEEE Trans．Neural Networks，2007，18(5):1453－1462．

[8]李潔，高新波，焦李成．基于特征加權(quán)的模糊聚類新算法[J]．電子學(xué)報(bào)，2006，34(1):89－92．

[9]Li Z，Yuan J S，Hong Y，Zhang K．K-mean algorithm with a distance based on the characteristic of differences[C]．WiCOM 2008，Dalian，China，2008，10．

[10]苑津莎，李中．基于形狀相似距離的K-means聚類算法[J]．華北電力大學(xué)學(xué)報(bào)，2009，36(6):98－103．