李德新

摘要：該文分析了聚類分析算法的基本思想、原理、數(shù)學(xué)模型及實(shí)現(xiàn)過(guò)程，詳細(xì)地分析了幾種經(jīng)典的聚類分析算法的優(yōu)缺點(diǎn)，最后介紹了常用的聚類分析算法的有效性分析方法。

關(guān)鍵詞：聚類分析算法;模型;有效性;評(píng)價(jià)

中圖分類號(hào)：TP391? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）30-0026-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1聚類分析的概念

在數(shù)據(jù)挖掘領(lǐng)域中，常常會(huì)遇到這樣的一些的問(wèn)題，從未加工的數(shù)據(jù)里面對(duì)有用的信息進(jìn)行轉(zhuǎn)換。轉(zhuǎn)換過(guò)程中可以利用的技術(shù)有很多，而其中的分類是最為常用的一種轉(zhuǎn)換技術(shù)。分類問(wèn)題需要一個(gè)參考問(wèn)題的樣本數(shù)據(jù)，并且這些樣本數(shù)據(jù)的屬性值都是已知的。分類得到的一個(gè)非常有價(jià)值的分類規(guī)則，并可以利用這些規(guī)則進(jìn)行未知類別的對(duì)象進(jìn)行分類，是先驗(yàn)學(xué)習(xí)的經(jīng)典案例。與分類相似的聚類[1]是將一個(gè)大數(shù)據(jù)集劃分為許多子集的過(guò)程。在這個(gè)問(wèn)題中，與分類所遇到的已知信息相比要少得多。在聚類過(guò)程中，待聚類的數(shù)據(jù)有關(guān)信息是不知道的，只能利用某種標(biāo)準(zhǔn)將數(shù)據(jù)進(jìn)行劃分到各個(gè)簇中。由此看來(lái)，聚類是一種發(fā)現(xiàn)數(shù)據(jù)對(duì)象內(nèi)在聯(lián)系的無(wú)監(jiān)督的學(xué)習(xí)算法，它主要是建立在集合知識(shí)之上的一種方法。聚類分析[2]是知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘的重要方法之一。聚類的過(guò)程是對(duì)知識(shí)的發(fā)現(xiàn)的過(guò)程，因此由聚類得出的結(jié)果可以反映數(shù)據(jù)分布的本質(zhì)特征。

2數(shù)據(jù)對(duì)象的相似性測(cè)量工具

聚類，顧名思義就是要將待處理的數(shù)據(jù)對(duì)象進(jìn)行劃分成類。聚類質(zhì)量的標(biāo)準(zhǔn)取決于相同類中的數(shù)據(jù)對(duì)象的相似性或者不相同類的數(shù)據(jù)對(duì)象的相異性。由此可見(jiàn)，對(duì)兩個(gè)數(shù)據(jù)對(duì)象之間的相似性度量對(duì)聚類具有重要意義。目前常用的相似性度量工具有距離和相似性系數(shù)兩種。

2.1距離

用于聚類分析相似性測(cè)量的最常用的方法是距離。通常我們自然會(huì)想到用點(diǎn)與點(diǎn)之間的距離來(lái)測(cè)量數(shù)據(jù)對(duì)象的相似程度。因?yàn)榫嚯x具有一些眾所周知的性質(zhì)，假設(shè)用[d（x，y）]來(lái)表示兩個(gè)點(diǎn)x、y之間的距離，則它具有如下性質(zhì)成立：

（1）非負(fù)性。對(duì)于所有的x和y，[d（x，y）]≥0，僅當(dāng)x = y時(shí)，[d（x，y）]=0.

（2）對(duì)稱性。對(duì)于所有的x和y，[d（x，y）]=[d（y，x）].

（3）三角不等式。對(duì)于所有的x，y和z，[d（x，z）]≤[d（x，y）]+[d（y，z）]。

數(shù)據(jù)對(duì)象之間的相似性通?？捎脷W幾里得距離及其變種來(lái)進(jìn)行測(cè)量，對(duì)于兩個(gè)數(shù)據(jù)對(duì)象x和y的距離的計(jì)算可采用以下3種常用的方法。

（1）歐幾里得距離（Euclidean distance）

[d（x，y）]=[k=1n（xk-yk）2]

在上式中，n表示數(shù)據(jù)對(duì)象的維數(shù)，其中的xk和yk分別用來(lái)表示x、y的第k個(gè)屬性值。

（2）閔可夫斯基距離（Minkowski distance）

[d（x，y）]=[k=1nxk-ykr1r]

這是最廣泛的閔可夫斯基的距離形式。其中，r是參數(shù)。

（3）Mahalanobis距離

Mahalanobis距離也是用得比較多的一種用于測(cè)量?jī)蓚€(gè)數(shù)據(jù)對(duì)象之間的相似性的距離。通常可以用下面的公式計(jì)算：

[mahalanobis（x，y）=（x-y）T-1（x-y）]

其中[Σ]為樣本協(xié)方差陣。該距離是為了克服其他兩種距離定義容易受到量綱和多重相關(guān)性的影響的缺點(diǎn)而提出來(lái)的一種新穎的距離測(cè)量方法。該距離的不足之處在于計(jì)算量大，對(duì)大規(guī)模的數(shù)據(jù)量性能較差。

2.2相似性系數(shù)度量方法

相似性系數(shù)可定義為兩個(gè)二元屬性數(shù)據(jù)對(duì)象的相似性程度，它的值可以在[0，1]之間取值，當(dāng)值為0時(shí)，表明兩個(gè)數(shù)據(jù)對(duì)象不相似，當(dāng)值為1時(shí)，可以得出兩個(gè)數(shù)據(jù)對(duì)象非常相似的結(jié)論。有大量的理由可以表明在特定情形下，一種系數(shù)為何要比另一種好。

假設(shè)存在兩個(gè)含有n個(gè)二元屬性數(shù)據(jù)對(duì)象x，y。那么通常對(duì)數(shù)據(jù)對(duì)象x和y進(jìn)行的比較就有如下四種情況：

（1）f00表示為當(dāng)x取0、y取0時(shí)的屬性數(shù)目;

（2）f01表示為x當(dāng)取0、y取1時(shí)的屬性數(shù)目;

（3）f10表示為x當(dāng)取1、y取0時(shí)的屬性數(shù)目;

（4）f11表示為x當(dāng)取1、y取1時(shí)的屬性數(shù)目。

SMC系數(shù)（Simple Matching Coefficient）SMC系數(shù)是目前應(yīng)用得最為廣泛的相似性系數(shù)之一。用SMC來(lái)表示，那么SMC就可以利用下面的計(jì)算公式來(lái)計(jì)算。

SMC = [值匹配的屬性個(gè)數(shù)屬性個(gè)數(shù)] =[][f11+f00f01+f10+f11+f00]

該系數(shù)對(duì)存在和不存在進(jìn)行同等計(jì)數(shù)。

Jaccard系數(shù)（Jaccard Coefficient）

當(dāng)數(shù)據(jù)對(duì)象包含非對(duì)稱的二元屬性時(shí)，利用SMC來(lái)進(jìn)行判定時(shí)會(huì)出現(xiàn)無(wú)法區(qū)分的現(xiàn)象，為了克服SMC的缺點(diǎn)提出了Jaccard 系數(shù)，該系數(shù)可用符號(hào)J表示，計(jì)算公式為：

J = [匹配的個(gè)數(shù)不涉及0-0匹配的屬性個(gè)數(shù)] =[][f11f01+f10+f11]

Tanimoto系數(shù)

用于對(duì)文檔數(shù)據(jù)的相似性度量的Tanimoto系數(shù)可用EJ表示，計(jì)算公式如下：

EJ（x，y） = [x?yx2+y2-x?y]

皮爾森相關(guān)（Pearsons correlation）系數(shù)

皮爾森相關(guān)系數(shù)是對(duì)兩個(gè)具有二元變量或連接變量的數(shù)據(jù)相關(guān)性進(jìn)行測(cè)定的系數(shù)，可以用如下公式進(jìn)行計(jì)算：

corr（x，y） =[covariance（x，y）standard_deviation（x）×standard_deviation（y）]=[sxysxsy]

3典型的聚類算法的有效性分析準(zhǔn)則

為了驗(yàn)證算法的有效性，經(jīng)常采用對(duì)聚類分析算法有效性評(píng)價(jià)方法有外部準(zhǔn)則、內(nèi)部準(zhǔn)則以及相對(duì)準(zhǔn)則，而這些評(píng)價(jià)準(zhǔn)則都是依靠統(tǒng)計(jì)假設(shè)檢驗(yàn)來(lái)實(shí)現(xiàn)的。

外部準(zhǔn)則的精髓在于把聚類分析所得到的聚類結(jié)果和事先定義好的數(shù)據(jù)集的分類結(jié)構(gòu)進(jìn)行對(duì)比研究，并最終得出算法有效性的評(píng)價(jià)方法。外部準(zhǔn)則方法可以采納的統(tǒng)計(jì)標(biāo)準(zhǔn)包括Jaccard系數(shù)、Rand統(tǒng)計(jì)、Mallows指數(shù)、Fowlkes和Hubert的[Γ]統(tǒng)計(jì)和F- measure等。

外部準(zhǔn)則在使用的時(shí)候，通常必須讓它滿足兩個(gè)重要的條件：（1）聚類算法得到的結(jié)果C與預(yù)先已知的X劃分的結(jié)果可以進(jìn)行比較;（2）要能夠?qū)κ孪纫呀?jīng)定義的劃分結(jié)果X與它的近鄰矩陣之間的相似程度進(jìn)行測(cè)定。

在上述外部準(zhǔn)則中所列舉的方法中，使用的最廣泛、優(yōu)勢(shì)最明顯的方法是F-measure，該方法的優(yōu)勢(shì)主要來(lái)源于對(duì)信息檢索領(lǐng)域中的查準(zhǔn)率（precision）及查全率（recall）的結(jié)合[2]，在對(duì)分類i的F-measure進(jìn)行計(jì)算時(shí)可用公式進(jìn)行計(jì)算：

F（i） = 2PR/（P+R）

通過(guò)計(jì)算就能夠得出各個(gè)聚類的F-measure值，按值的大小進(jìn)行排序，就能夠得出聚類質(zhì)量的高低。而公式中的P和R分別表示的是查準(zhǔn)率和查全率，可用下面的公式計(jì)算得出。

P = precision（i，j） = [Nij]/[Ni];

R = recall（i，j） = [Nij]/[Nj]，

在上面的兩個(gè)公式中，[Nij]表示聚類j中分類數(shù)i的多少;而[Nj]表示的是聚類j中所有數(shù)據(jù)對(duì)象的數(shù)量;[Ni]是分類i中所有對(duì)象的個(gè)數(shù)。于是與聚類結(jié)果[λ]相對(duì)應(yīng)的F-measure值可用下面的公式進(jìn)行計(jì)算：

[Fλ=ii×F（i）ii]

在式中，[i]的取值為分類i數(shù)據(jù)對(duì)象的總個(gè)數(shù)。

內(nèi)部準(zhǔn)則是將聚類結(jié)果簡(jiǎn)單的與數(shù)據(jù)集合本身所具有的一些特征進(jìn)行比較的評(píng)價(jià)方法。內(nèi)部準(zhǔn)則的方法也是對(duì)聚類算法評(píng)價(jià)的有效方法，較為常用的方法有統(tǒng)計(jì)指標(biāo)有[Γ]統(tǒng)計(jì)、同現(xiàn)相關(guān)系數(shù)（CPCC）等[3]。

（1）不受簇的形狀的限制

現(xiàn)實(shí)中的數(shù)據(jù)對(duì)象形成的簇，其形狀可以是任意形狀的。因此，一個(gè)好的聚類算法，應(yīng)該能夠發(fā)現(xiàn)任意形狀的簇。

（2）可伸縮性

在實(shí)際的數(shù)據(jù)處理時(shí)，面臨的數(shù)據(jù)對(duì)象的規(guī)模有大有小，可伸縮性指的是聚類算法既要具有處理大規(guī)模海量數(shù)據(jù)的能力又要能處理小規(guī)模數(shù)據(jù)的性能。因此，一個(gè)聚類算法需要具備良好的可伸縮性。

（3）同一時(shí)刻能夠處理不同類型屬性的能力

聚類算法需要具有處理不同類型的屬性的能力，例如數(shù)值屬性、組合類型屬性或類屬性。

參考文獻(xiàn)：

[1] 范明，孟小峰，譯.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2005.

[2] 胡建軍，唐常杰，李川，等.基于最近鄰優(yōu)先的高效聚類算法[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2004，36（6）：93-99.

[3] Han Jiawei， Kamber Micheline. Data Ming Concepts and Techniques[M].2nd edition.San Francisco，USA：Morgan Kaufmann Publisher，2020.

【通聯(lián)編輯：代影】