基于數據約減的聚類有效性分析*

于 曉， 李 晨， 王亞茹

(天津大學 電氣與自動化工程學院，天津 300072)

基于數據約減的聚類有效性分析*

于 曉， 李 晨， 王亞茹

(天津大學 電氣與自動化工程學院，天津 300072)

聚類分析中利用有效性指標判斷數據集的正確類數極易受到噪聲數據、類之間分離性以及聚類算法的影響，所確定類數的正確性難以得到保證。為克服這個問題，以文獻[1]中的數據約減方法為基礎，對原數據集和約減后的數據集利用有效性指標進行正確類數判別。實驗表明：該方法能增大類之間的分離性，有效判斷數據集的最優類數。

數據約減； 方向角； 聚類分析； 最優類數

0 引 言

目前隨著數據挖掘和人工智能技術的不斷進步，各行的數據量不斷涌現，如文本數據、基因數據、圖像數據等，由于聚類方法的無監督性，使得聚類分析在處理海量信息中得到了廣泛的應用[1]。近年來，隨著聚類理論的不斷發展，聚類分析在眾多領域也獲得了令人滿意的效果。但是，作為數據挖掘的重要工具，聚類在發展中還存在許多問題，如聚類中相似性的度量、數據的預處理、聚類有效性等[2]。其中，聚類有效性問題中如何確定數據集的最佳類數一直以來都是聚類分析問題中的一大難題，也是眾多學者研究的熱點問題。因為現有的聚類算法絕大多數都要預先給出數據集的類數，才能對數據集進行有效的聚類分析。為此，眾多聚類有效性指標被提出，以此確定數據集的最佳類數。但是由于數據結構的多樣性和復雜性，研究表明[3]，沒有哪一種聚類有效性指標可以在任何的情況下對任何的數據集都能取得良好的效果。

本文將基于張開角測度的數據約減方法應用于聚類分析中最佳類數的判別問題。通過優化原有的約簡方法，對數據集進行數據約減，去掉數據集中的噪聲數據，然后對約減前后的數據應用聚類方法和有效性指標進行最佳類數判別。實驗證明，與原數據集相比，約減后的數據集能夠得到較好的最優類數。

1 相關的工作

本節介紹了一個基于張開角的數據約簡方法以及兩個常用的聚類有效性指標，DBI指標[4]和Gap統計指標[5]，具體說明如下。

1.1 張開角測度的數據約減方法

設X={x1,x2,...,xi}是d維空間中包含n個數據向量的集合,xi={xi1,xi2,…,xid}是數據集中任意的第i個數據向量，設順時針排列的距離xi最近的2d個數據向量為xi={xi1,xi2,…,xid}，則從xi出發與這些向量相連構成的(2d-1)個向量的張開角依次表示為(xi,xi1),(xi1,xi2),…,(xi(2d-1),xi2d)，則xi的平均張開角定義為

(1)

式中 Angle()為一對從xi出發的一對連接向量之間的夾角;|xsxi|為向量xs與xi之間的連接線的距離。

該方法根據數據集分布的一般特征，能夠區分數據集中核心對象和邊界對象分布的本質區別，實現以核心目標為中心的數據約減。然而，該方法中計算方向角的向量數為2d是經驗確定的，并沒有經過優化。本文將對此進行優化設計。

1.2 聚類有效性指標

作為數據挖掘領域的重要分支，聚類是一個無監督的學習過程，然而如何確定最佳類數一直以來都是一項困難的工作[6,7]。解決這類問題的一個有效方法就是構造聚類有效性指標，目前研究者已經提出了許多聚類有效性指標，如DBI指標、Gap指標、PC方法等[8]。目前在工程中廣泛認可并最為常用的為DBI指標和Gap指標。

1)Davies-Bouldin指標

Davies-Bouldinindex(DBI)首先計算類內距離Si為

(2)

式中 xj為第i類中第j個數據點；Ai為第i類的類中心；Ni為第i類中的數據點總數；一般取q=2; 類間距離Mij定義為

(3)

式中 aik為第i類中心點的第k個屬性值，Mij為第i類與第j類中心的距離，一般情況,取p=2;DBI指標定義為

(4)

從Rij中選出最大值Ri=max(Rij)，即第i類與其他類的相似度中最大的相似度的值，取平均得到

(5)

DBI指數越小，表明其對應的聚類效果則越好。在過去的20年中，DBI指標已經在工程中有記錄的應用次數超過2 000次。

2)Gap統計指標

設xi表示數據集中的數據點，i=1,2,…,n,則xi可以表示為xi={xi1,xi2,…,xid}，d為數據集的維數，令dii＇表示數據點i與i＇之間的距離。

設C1，C2，…,Ck表示數據集被分成K個類，Cr表示數據點屬于第r類，Nr=|Cr|為第r類中數據點的總數。第r類中任意兩點之間的距離之和定義為

(6)

總的類內距離用符號Wk表示，Wk的計算表達式子為

(7)

則Gapn(k)指標定義為

(8)

2 本文提出的方法

使用聚類有效性指標確定類數的正確性嚴重受到以下因素影響：數據集中存在的大量噪聲數據、類與類之間的不可分性以及聚類算法的不穩定性等等[9]，本文的研究表明,通過數據約簡能夠有效地降低上述因素的影響。

2.1 基本動機

圖1顯示了人工數據集Set1和Set2在二維坐標下的分布情況。通過基于張開角的數據約簡方法進行約簡。 圖2、圖3分別顯示了約減30 %和90 %數據點后的結果，其中星號為保留下來的數據點，黑點的為約減掉的數據點。從約減結果可以看出，約減后的數據點逐漸趨向中心，數據集中類別分離性更加明顯。

圖1 原數據集Set1和Set2

圖2 30 %的數據點約簡

圖3 90 %的數據點約簡

因此，將數據集中非關鍵的數據去除，使數據集中類別的分離性更加明顯，容易得到更加準確的類數判斷[10]。

2.2 確定計算方向角的最優方式

上述基于張開角測度的數據約減方法根據數據集中各個數據點張開角的不同對數據集進行約減。為了得到最優的約減效果，確定以下優化目標：使數據集中所有點計算出的測度最大化。該優化目標基于兩點：首先，數據點之間的測度值差別越大，約簡結果越穩定[11]；其次，方向角測度較大的點對應各個類的核心點而較小的點對應邊界點；因此，數據點之間測度值差別的最大化將增大這兩類點之間的差別，從而隨著約簡過程的進行，邊界點以及噪聲點逐漸被去除，類之間的可分性越來越強。據此定義以下目標函數

(9)

3 實 驗

實驗中,使用UCI中具有不同結構和特征的15個數據集,這些數據集的特征說明如表1所示，且這些數據集的正確類數是已知的。

表1 15個UCI中真實數據集

實驗中,首先使用張開角的數據約減方法對數據集進行不同比例的約減，對約減前后的數據集運用k-means進行聚類，然后對聚類結果分別應用DBI、Gap兩個指標進行最優類數的判別，實驗結果如表2、表3以及圖4、圖5所示。從實驗結果中可以得出以下結論：

1)從表2、表3可得，與約減前的最優類數相比較，約減后的最優類數更加準確或更加接近數據集的真實類數，說明約減后數據集中類別之間的分離性更加凸顯，因此，該方法對于聚類中最佳類數的判別具有一定的有效性。然而對類數未能正確判斷的數據集，實際上，數據集中類的形狀是任意的，無法用k-means聚類，因而無法得到正確的類數判別。

表2 DBI指標聚類數

表3 Gap指標聚類數

圖4 Glass數據集約減前后DBI指標

圖5 Iris數據集約減前后Gap指標

2)利用有效性指標得到的結果并非與真實類數完全一致，從結果可以看出，DBI指標類數判別的準確性要高于Gap指標的準確性。 因為不同的指標適用的條件不同，聚類有效性評價一直是聚類分析中一個重要的研究方向，目前還沒有一種有效性指標可以完全適用于所有聚類算法。

3)如圖4、圖5中Glass，Iris數據集指標曲線圖所示，約減后數據集的指標曲線圖中最優點位置更加突出，其他數據集與之類似。

4 結 論

通過對數據結構的分析，文中將基于張開角測度的數據約減方法優化后針對一般數據集能夠進行有效約減，并將該方法應用于聚類分析中最佳類數的判別問題。通過對具有不同數據結構和密度的數據集進行測試，可以發現約減后得到的最優類數與數據集的真實類數更加接近，這表明約減后數據集中類別的分離性更加明顯，因此，該方法對聚類分析中最佳類數的判別具有一定的有效性和有用性。

該方法還有一定的不足之處，因為得到比較好的最優類數是以時間為代價的，約減的過程是一個逐層循環的過程，每次循環都要計算每個點周圍的鄰域點，因此，進一步提高該算法的效率有待進一步研究。

[1] 李 晨,王亞茹,岳士弘.基于張開角測度的數據約簡[J].傳感器與微系統,2016,35(4):25-28.

[2] 周世兵.聚類分析中的最佳聚類確定方法研究及應用[D].無錫：江南大學,2011.

[3] Sergios T,Konstantinos K.模式識別[M].4版.北京:電子工業出版社,2010.

[4] Arbelaitz O,Gurrutxaga I,Muguerza J,et al.An extensive comparative study of cluster validity indices[J].Pattern Recognition,2013,46(1):243-256.

[5] Guerra L,Bobles V,Bielza C,et al.A comparison of clustering quality indices using outliers and noise[J].Intelligent Data Analysis,2012,16(4):703-715.

[6] 白素琴,吳小俊.基于模糊聚類算法的有效性指標[J].江南大學學報,2007,6(6):878-882.

[7] 楊 燕,靳 蕃,KAME Lmohamed.聚類有效性評價綜述[J].計算機應用研究,2008,25(6):1630-1632.

[8] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[9] 周開樂,楊善林,丁 帥,等.聚類有效性研究綜述[J].系統工程理論與實踐,2014,34(9):2417-2431.

[10] Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[11] 曹付元,武鵬鵬.一種基于稀疏度和距離的初始類中心選擇算法[J].山西大學學報:自然科學版,2015,38(1):73-78．

Cluster validity analysis based on data reduction*

YU Xiao， LI Chen， WANG Ya-ru

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Estimating the correct number of clusters by cluster validity index in cluster analysis is highly susceptible to noise data,separation among clusters and clustering algorithm,so the correctness of the estimated number of clusters is difficult to be guaranteed.In order to overcome this problem,validity index is used to estimated number of clusters in original dataset and reduced dataset based on the data reducing method proposed in reference[1],the result demonstrate the method can enhance separation among clusters and effectively determine the optimal number of clusters.

data reduction; direction angle; cluster analysis; the optimal number of clusters

10.13873/J.1000—9787(2017)03—0055—03

2016—04—26

國家自然科學基金資助項目(61573251)

TP 391.4

A

1000—9787(2017)03—0055—03

于 曉(1991-)，女，碩士研究生，主要研究方向為模式識別。