聚類分析中的相似度研究

鄧冠男

(東北電力大學(xué)理學(xué)院，吉林吉林132012)

聚類，也稱作無監(jiān)督分類，是數(shù)據(jù)挖掘的重要組成部分，目前已經(jīng)在很多領(lǐng)域取得了成功的應(yīng)用。聚類分析的目的是通過將有限的數(shù)據(jù)集分成多個具有同質(zhì)的“簇”(即不同的類)，來發(fā)現(xiàn)隱藏的、潛在于數(shù)據(jù)中的有用信息。其目標(biāo)是要求同一類內(nèi)的數(shù)據(jù)盡可能相近，而不同的類之間的數(shù)據(jù)盡可能相異。為了達(dá)到這一目標(biāo)，必須考慮如何度量數(shù)據(jù)之間、數(shù)據(jù)與類之間或者類與類之間相似性這一基本而重要的問題。為了度量數(shù)據(jù)的相似性，人們提出相似度的概念，并提出許多相似度的計算公式［1－3］。

盡管很多時候沒有明確說明，但是事實(shí)上，無論何種聚類算法，都是建立在事先假定某種相似性度量方式基礎(chǔ)上的，比如K－均值算法假定數(shù)據(jù)之間、數(shù)據(jù)與類之間都使用歐式距離構(gòu)造的相似度;基于圖的聚類算法假定數(shù)據(jù)之間使用歐式距離構(gòu)造的相似度，但是數(shù)據(jù)與類之間的相似度定義為數(shù)據(jù)該類所有元素相似度的最小值;EM算法利用某種概率密度函數(shù)來度量數(shù)據(jù)與類之間的相似度等等。

在實(shí)際的聚類問題中，存在很多與相似度有關(guān)的問題。比如，當(dāng)數(shù)據(jù)的屬性具有不同權(quán)重時，如何計算相似度。如果沒有任何關(guān)于屬性重要性的先驗信息，毫無疑問我們會認(rèn)為所有屬性都應(yīng)當(dāng)平等對待，但是如果必須區(qū)別對待的話，我們必須考慮如何對屬性進(jìn)行加權(quán)。然而，從眾多相似度的計算公式中，我們并不能看出或者明確給出權(quán)重如何分配給各個屬性的。再如，如果數(shù)據(jù)混合有不同類型的數(shù)據(jù)(如布爾型、文本型、數(shù)值型等等)，如何計算其相似度，目前能夠解決這一問題的相似度還是非常少的［4，5］。

本文針對聚類分析中的相似度進(jìn)行研究。首先，通過分析相似度的構(gòu)成的過程，將相似度的構(gòu)造分解為比較、綜合及轉(zhuǎn)換的過程，進(jìn)而提出一般相似度的概念。之后，利用一般相似度分析常見相似度對權(quán)重的分配方式，同時提出幾種多類型混合數(shù)據(jù)相似度計算的策略。

1 相似度

在一些文獻(xiàn)中可以找到不同的相似度的公理化定義方式［6，7］，這里我們給出其中一種簡單的定義方式。

定義1設(shè)X=X1×X2×…×Xn為n維有限論域，對于?x，y∈X，如果映射s:X×X→［0，1］滿足下列條件時:

(1)非負(fù)性0≤s(x，y)≤1;

(2)對稱性s(x，y)=s(y，x);

(3)s(x，x)=1。

則稱s(x，y)稱為x與y之間的相似度。

但是，需要注意的是，目前某些文獻(xiàn)中給出的相似度的計算公式并不完全滿足上述定義。針對不同的數(shù)據(jù)類型，目前有許多相似度的計算公式，下面列出常見的一些:

(1)數(shù)值型數(shù)據(jù)的相似度

數(shù)值型數(shù)據(jù)的相似度通常利用數(shù)據(jù)間的距離來構(gòu)造，可以利用公式

將距離轉(zhuǎn)化為相似度，其中max_d表示數(shù)據(jù)集中數(shù)據(jù)之間的最大的距離。

常用的距離公式有:

其中，∨表示取大運(yùn)算，對應(yīng)的∧表示取小運(yùn)算。

(2)二元數(shù)據(jù)的相似度

二元數(shù)據(jù)是由二元變量構(gòu)成。二元變量只能有兩種取值狀態(tài):0或1，其中0表示該特征為空，1表示該特征存在。設(shè)x=(x1，x2，…，xn)、y=(y1，y2m…，yn)為二元數(shù)據(jù)，常用0－0匹配表示xi=0且yi=0，同理可用0－1、1－0及1－1匹配表示xi及yi相應(yīng)的取值。常見的計算其相似度的方法列舉如下，其中fij表示集合{(xk，yk)xk=i且yk=j，k=1，2，…，n}的基數(shù)，i，j∈{0，1}。

(3)其他相似度

2 一般相似度

上文列出了一些相似度的計算公式，顯然，由這些公式，我們是無法看出這些相似度之間有什么差別，也看不出這些相似度對于權(quán)重是如何分配的，那么，在實(shí)際運(yùn)用中究竟選擇哪種相似度進(jìn)行計算呢。

如果給定兩個數(shù)據(jù)x=(x1，x2，…，xn)及y=(y1，y2，…，yn)，顯然數(shù)據(jù)由各個分量所共同描述而成，因此其相似度也是由各分量來決定的。自然而然，可以得到這樣的想法，如果比較xk與yk(k=1，2，…，n)之間的接近或者分離程度，然后將所得結(jié)果綜合起來就可以形成對x與y之間整體相似度的描述。這就是本文一般相似度的基本出發(fā)點(diǎn)，并且下文分析也可以看出，常見的一些相似度實(shí)際上也是這樣計算得來，而且由此我們可以看出權(quán)重的分配方式及相關(guān)問題的解決方案。

定義2設(shè)X=X1×X2×…×Xn是n維有限論域，x=(x1，x2，…，xn)，y=(y1，y2，…，yn)是兩個n維數(shù)據(jù)對象，那么x與y之間的一般相似度可由下式計算得到:

其中，

(1)φi:Xi×Xi→Y稱作單屬性相似或相離度，是度量第i個屬性元素之間接近或分離程度的函數(shù);

(2)Mn:Yn→Y稱作綜合函數(shù)［8］，滿足如下條件:

(3)f:Y→［0，1］稱作轉(zhuǎn)換函數(shù)。

定義2中，Y表示計算單屬性元素之間接近或者分離程度函數(shù)的值域，通常如果計算的是接近程度Y=［0，1］，如果計算的是分離程度Y=R。從定義2可以看出，一般相似度將相似度的計算過程分解成三個步驟:比較、綜合及轉(zhuǎn)換。比較，度量單個屬性之間的相似或相離程度;綜合，將每一屬性之間的度量結(jié)果綜合，形成對整體的度量結(jié)果;轉(zhuǎn)換，將上一步的計算結(jié)果映射到［0，1］。這樣構(gòu)成的相似度給出了大多數(shù)相似度的一般表示形式，具體的轉(zhuǎn)化形式在下一節(jié)給出。為了方便起見，稱φi、Mn及f為一般相似度的構(gòu)成函數(shù)，其中綜合函數(shù)在文獻(xiàn)［8］中已經(jīng)詳細(xì)討論過，這里不再贅述，常用的綜合函數(shù)有:

特別的，如果φi為單屬性相似度，且Mn為可加標(biāo)準(zhǔn)綜合函數(shù)［8］，則可以將一般相似度形式簡化為:

為了方便起見，稱其為一般正規(guī)相似度。

設(shè)μn={MnMn是n階可加標(biāo)準(zhǔn)綜合函數(shù)}，si為單屬性相似度，按照綜合函數(shù)的性質(zhì)，很容易得到如下這些結(jié)論:

定理1設(shè)M2∈μ2，令Mn(x)=M2(M2(…(M2(x1，x2)，x3)…)，xn)，那么s(x，y)=Mn(s1(x1，y1)，s2(x2，y2)，…，sn(xn，yn))為一般正規(guī)相似度。

定理2設(shè)Mm∈μm，Mnk∈μnk且，令

則s(x，y)=Mn(s1(x1，y1)，s2(x2，y2)，…，sn(xn，yn))為一般正規(guī)相似度。

定理3設(shè)Mm∈μm，M(k)n∈μn且1≤k≤m，令

則s(x，y)=Mn(s1(x1，y1)，s2(x2，y2)，…，sn(xn，yn))為一般正規(guī)相似度。

定理1－定理3可以很容易由可加標(biāo)準(zhǔn)綜合函數(shù)的性質(zhì)直接得到，需要注意的是，這三個定理給出了三種不同的方式來獲取同樣的兩個數(shù)據(jù)相似度的方法，雖然，這里看起來比較復(fù)雜，但是對于多類型混合數(shù)據(jù)卻是非常有用的。

3 相似度相關(guān)問題分析

3.1 常見相似度的權(quán)重分配

設(shè)x=(x1，x2，…，xn)和y=(y1，y2，…，yn)為兩個數(shù)據(jù)對象，這一節(jié)我們分析常見相似度是如何分配權(quán)重的。如果沒有特別說明，本節(jié)中我們?nèi)【C合函數(shù)

我們以歐式距離構(gòu)成的相似度為例進(jìn)行分析，設(shè)Ri為第i個屬性差異量數(shù)，Li為第i個屬性的集中量數(shù)，則有

對于其他一些相似度我們進(jìn)行了類似分析，具體如表1、表2及表3所示。

表1 基于距離的相似度的構(gòu)成函數(shù)

觀察基于距離的相似度的構(gòu)成函數(shù)，從中可以發(fā)現(xiàn)這樣一個事實(shí):如果數(shù)據(jù)沒有經(jīng)過標(biāo)準(zhǔn)化處理，基于距離的相似度并不是平均分配權(quán)重的，對于差異量數(shù)較大的屬性賦予了較大的權(quán)重，這也反映了數(shù)據(jù)標(biāo)準(zhǔn)化處理的必要及重要性。

表2 二元數(shù)據(jù)相似度的函數(shù)構(gòu)成

表2中，ω00表示xi=0且yi=0對應(yīng)屬性的權(quán)重，同理可理解ω01，ω10及ω11。表中所列二元數(shù)據(jù)相似度，其轉(zhuǎn)化函數(shù)均為f(t)=t，單屬性相似度均為的函數(shù)形式可知，0－1及1－0這兩種匹配形式，對相似度計算沒有任何影響。從表2中可以看出，一些相似度公式，如簡單匹配系數(shù)、Rogers-Tanimoto以及Sokal-Sneath-a對0－0匹配及1－1均給予考慮;而Jaccard系數(shù)、Russell-Rao以及Srensen僅考慮1－1匹配。另外，通過比較不同相似度的權(quán)重分配數(shù)值，很容易得到下面的結(jié)論。

定理4簡單匹配系數(shù)、Rogers-Tanimoto以及Sokal-Sneath-a的權(quán)重ω11(或ω00)之間有如下關(guān)系:

定理5Jaccard系數(shù)、Russell-Rao、Srensen以及Sokal-Sneath-e的權(quán)重之間有如下關(guān)系:

由于φi(xi，yi)=1－xi－yi，因此有

這說明本文所列的二元數(shù)據(jù)相似度可以看成由Manhattan距離(令p=1的Minkowski距離)構(gòu)成的相似度，可以看作是一種特殊的由距離構(gòu)成的相似度。

表3 其他相似度的函數(shù)構(gòu)成

由表3可知，余弦相似度及相關(guān)系數(shù)構(gòu)成的相似度對各個屬性的權(quán)重也不是平均分配，而是數(shù)據(jù)的函數(shù)?？梢钥闯?，數(shù)據(jù)取值越大，余弦相似度分配的權(quán)重越大，同樣數(shù)據(jù)距離均值越遠(yuǎn)，相關(guān)系數(shù)構(gòu)成的相似度分配的權(quán)重越大。

3.2 多類型混合數(shù)據(jù)的相似度

在很多應(yīng)用問題中，數(shù)據(jù)不僅是由一種類型的屬性構(gòu)造，這時各種相似度的計算公式就不能直接應(yīng)用。然而，除了Gower［4］及Ichino［5］給的計算混合數(shù)據(jù)相似度的方法外，很少有人對此進(jìn)行考慮。由本文的研究可知，問題的關(guān)鍵在于如何將不同類型屬性的相似度綜合起來，本文提出的一般相似度正好提供了這一問題的解決方案。具體在實(shí)施的時候可以有三種策略:

(1)直接按照一般正規(guī)相似度的定義方式進(jìn)行計算。也就是，先度量單個屬性之間的相似度，然后利用綜合函數(shù)得出整體相似度。但是，很多常見的相似度在計算單屬性相似度時會歸約到同一形式上，如由Minkowsi距離、平均距構(gòu)成的相似度以及很多二元數(shù)據(jù)的相似度都可以寫成s(x，y)=1－x－y。

(2)將數(shù)據(jù)按照類型劃分，利用相應(yīng)的相似度公式計算不同類型數(shù)據(jù)的相似度，之后利用綜合函數(shù)得出整體相似度，這種方法將同種類型的數(shù)據(jù)看成整體進(jìn)行考慮。

(3)將上兩種策略混合使用。

在實(shí)際應(yīng)用中，還會涉及到其他一些問題，比如權(quán)重分配問題、綜合函數(shù)選取問題、相似度選取問題等等，這還需要針對實(shí)際問題進(jìn)行考慮。

4 結(jié)論

針對聚類分析中的相似度問題，本文提出了一般相似度的概念，在此基礎(chǔ)上分析常見相似度的權(quán)重分配及多類型混合數(shù)據(jù)的相似度計算策略。需要注意的是，由一般相似度的概念可以很容易構(gòu)造多種相似度的計算公式，這也是本文提出的一般相似度非常具有前景意義之處，但是鑒于本文并未考慮實(shí)際問題的需求，因此沒有具體去做。

［1］S.Santini，R.Jain.Similarity Measures［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，1999，21(9):871－883.

［2］Y.S.Son，J.Baek.A modified correlation coefficient based similarity measure for clustering time-course gene expression data［J］.Pattern Recognition Letters，2008，29(3):232－242.

［3］L.Bodis，A.Ross，E.Pretsch.A novel spectra similarity measure［J］.Chemometrics and Intelligent Laboratory Systems，2007，85(1):1－8.

［4］J.Gower.A general coefficient of similarity and some of its properties［J］.Biometrics，1971，27(4):857－874.

［5］M.Ichino，H.Yaguchi.Generalized Minkowski metrics for mixed feature-type data analysis［J］.IEEE Transactions on System，Man and Cybernetics，1994，24(4):698－708.

［6］L.Kaufman，P.Rousseeuw.Finding Groups in Data-An Introduction to Cluster Analysis［M］.New York:John Wiley＆Sons，Inc，1990.

［7］Anderberg M.Cluster analysis for application［M］.New York:Academic Press，1973.

［8］H.X.Li.Multifactorial functions in fuzzy sets theory［J］.Fuzzy Sets and Systems，1990，35(1):69－84.