聚類分析模型算法研究及其有效性評價

李德新

摘要：該文分析了聚類分析算法的基本思想、原理、數學模型及實現過程，詳細地分析了幾種經典的聚類分析算法的優缺點，最后介紹了常用的聚類分析算法的有效性分析方法。

關鍵詞：聚類分析算法;模型;有效性;評價

中圖分類號：TP391? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）30-0026-02

開放科學（資源服務）標識碼（OSID）：

1聚類分析的概念

在數據挖掘領域中，常常會遇到這樣的一些的問題，從未加工的數據里面對有用的信息進行轉換。轉換過程中可以利用的技術有很多，而其中的分類是最為常用的一種轉換技術。分類問題需要一個參考問題的樣本數據，并且這些樣本數據的屬性值都是已知的。分類得到的一個非常有價值的分類規則，并可以利用這些規則進行未知類別的對象進行分類，是先驗學習的經典案例。與分類相似的聚類[1]是將一個大數據集劃分為許多子集的過程。在這個問題中，與分類所遇到的已知信息相比要少得多。在聚類過程中，待聚類的數據有關信息是不知道的，只能利用某種標準將數據進行劃分到各個簇中。由此看來，聚類是一種發現數據對象內在聯系的無監督的學習算法，它主要是建立在集合知識之上的一種方法。聚類分析[2]是知識發現和數據挖掘的重要方法之一。聚類的過程是對知識的發現的過程，因此由聚類得出的結果可以反映數據分布的本質特征。

2數據對象的相似性測量工具

聚類，顧名思義就是要將待處理的數據對象進行劃分成類。聚類質量的標準取決于相同類中的數據對象的相似性或者不相同類的數據對象的相異性。由此可見，對兩個數據對象之間的相似性度量對聚類具有重要意義。目前常用的相似性度量工具有距離和相似性系數兩種。

2.1距離

用于聚類分析相似性測量的最常用的方法是距離。通常我們自然會想到用點與點之間的距離來測量數據對象的相似程度。因為距離具有一些眾所周知的性質，假設用[d（x，y）]來表示兩個點x、y之間的距離，則它具有如下性質成立：

（1）非負性。對于所有的x和y，[d（x，y）]≥0，僅當x = y時，[d（x，y）]=0.

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

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

數據對象之間的相似性通常可用歐幾里得距離及其變種來進行測量，對于兩個數據對象x和y的距離的計算可采用以下3種常用的方法。

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

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

在上式中，n表示數據對象的維數，其中的xk和yk分別用來表示x、y的第k個屬性值。

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

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

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

（3）Mahalanobis距離

Mahalanobis距離也是用得比較多的一種用于測量兩個數據對象之間的相似性的距離。通常可以用下面的公式計算：

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

其中[Σ]為樣本協方差陣。該距離是為了克服其他兩種距離定義容易受到量綱和多重相關性的影響的缺點而提出來的一種新穎的距離測量方法。該距離的不足之處在于計算量大，對大規模的數據量性能較差。

2.2相似性系數度量方法

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

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

（1）f00表示為當x取0、y取0時的屬性數目;

（2）f01表示為x當取0、y取1時的屬性數目;

（3）f10表示為x當取1、y取0時的屬性數目;

（4）f11表示為x當取1、y取1時的屬性數目。

SMC系數（Simple Matching Coefficient）SMC系數是目前應用得最為廣泛的相似性系數之一。用SMC來表示，那么SMC就可以利用下面的計算公式來計算。

SMC = [值匹配的屬性個數屬性個數] =[][f11+f00f01+f10+f11+f00]

該系數對存在和不存在進行同等計數。

Jaccard系數（Jaccard Coefficient）

當數據對象包含非對稱的二元屬性時，利用SMC來進行判定時會出現無法區分的現象，為了克服SMC的缺點提出了Jaccard 系數，該系數可用符號J表示，計算公式為：

J = [匹配的個數不涉及0-0匹配的屬性個數] =[][f11f01+f10+f11]

Tanimoto系數

用于對文檔數據的相似性度量的Tanimoto系數可用EJ表示，計算公式如下：

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

皮爾森相關（Pearsons correlation）系數

皮爾森相關系數是對兩個具有二元變量或連接變量的數據相關性進行測定的系數，可以用如下公式進行計算：

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

3典型的聚類算法的有效性分析準則

為了驗證算法的有效性，經常采用對聚類分析算法有效性評價方法有外部準則、內部準則以及相對準則，而這些評價準則都是依靠統計假設檢驗來實現的。

外部準則的精髓在于把聚類分析所得到的聚類結果和事先定義好的數據集的分類結構進行對比研究，并最終得出算法有效性的評價方法。外部準則方法可以采納的統計標準包括Jaccard系數、Rand統計、Mallows指數、Fowlkes和Hubert的[Γ]統計和F- measure等。

外部準則在使用的時候，通常必須讓它滿足兩個重要的條件：（1）聚類算法得到的結果C與預先已知的X劃分的結果可以進行比較;（2）要能夠對事先已經定義的劃分結果X與它的近鄰矩陣之間的相似程度進行測定。

在上述外部準則中所列舉的方法中，使用的最廣泛、優勢最明顯的方法是F-measure，該方法的優勢主要來源于對信息檢索領域中的查準率（precision）及查全率（recall）的結合[2]，在對分類i的F-measure進行計算時可用公式進行計算：

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

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

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

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

在上面的兩個公式中，[Nij]表示聚類j中分類數i的多少;而[Nj]表示的是聚類j中所有數據對象的數量;[Ni]是分類i中所有對象的個數。于是與聚類結果[λ]相對應的F-measure值可用下面的公式進行計算：

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

在式中，[i]的取值為分類i數據對象的總個數。

內部準則是將聚類結果簡單的與數據集合本身所具有的一些特征進行比較的評價方法。內部準則的方法也是對聚類算法評價的有效方法，較為常用的方法有統計指標有[Γ]統計、同現相關系數（CPCC）等[3]。

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

現實中的數據對象形成的簇，其形狀可以是任意形狀的。因此，一個好的聚類算法，應該能夠發現任意形狀的簇。

（2）可伸縮性

在實際的數據處理時，面臨的數據對象的規模有大有小，可伸縮性指的是聚類算法既要具有處理大規模海量數據的能力又要能處理小規模數據的性能。因此，一個聚類算法需要具備良好的可伸縮性。

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

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

參考文獻：

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

[2] 胡建軍，唐常杰，李川，等.基于最近鄰優先的高效聚類算法[J].四川大學學報（工程科學版），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.

【通聯編輯：代影】