基于數(shù)據(jù)約減的聚類有效性分析*

于 曉， 李 晨， 王亞茹

(天津大學(xué) 電氣與自動(dòng)化工程學(xué)院，天津 300072)

基于數(shù)據(jù)約減的聚類有效性分析*

于 曉， 李 晨， 王亞茹

(天津大學(xué) 電氣與自動(dòng)化工程學(xué)院，天津 300072)

聚類分析中利用有效性指標(biāo)判斷數(shù)據(jù)集的正確類數(shù)極易受到噪聲數(shù)據(jù)、類之間分離性以及聚類算法的影響，所確定類數(shù)的正確性難以得到保證。為克服這個(gè)問(wèn)題，以文獻(xiàn)[1]中的數(shù)據(jù)約減方法為基礎(chǔ)，對(duì)原數(shù)據(jù)集和約減后的數(shù)據(jù)集利用有效性指標(biāo)進(jìn)行正確類數(shù)判別。實(shí)驗(yàn)表明：該方法能增大類之間的分離性，有效判斷數(shù)據(jù)集的最優(yōu)類數(shù)。

數(shù)據(jù)約減； 方向角； 聚類分析； 最優(yōu)類數(shù)

0 引 言

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

本文將基于張開(kāi)角測(cè)度的數(shù)據(jù)約減方法應(yīng)用于聚類分析中最佳類數(shù)的判別問(wèn)題。通過(guò)優(yōu)化原有的約簡(jiǎn)方法，對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)約減，去掉數(shù)據(jù)集中的噪聲數(shù)據(jù)，然后對(duì)約減前后的數(shù)據(jù)應(yīng)用聚類方法和有效性指標(biāo)進(jìn)行最佳類數(shù)判別。實(shí)驗(yàn)證明，與原數(shù)據(jù)集相比，約減后的數(shù)據(jù)集能夠得到較好的最優(yōu)類數(shù)。

1 相關(guān)的工作

本節(jié)介紹了一個(gè)基于張開(kāi)角的數(shù)據(jù)約簡(jiǎn)方法以及兩個(gè)常用的聚類有效性指標(biāo)，DBI指標(biāo)[4]和Gap統(tǒng)計(jì)指標(biāo)[5]，具體說(shuō)明如下。

1.1 張開(kāi)角測(cè)度的數(shù)據(jù)約減方法

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

(1)

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

該方法根據(jù)數(shù)據(jù)集分布的一般特征，能夠區(qū)分?jǐn)?shù)據(jù)集中核心對(duì)象和邊界對(duì)象分布的本質(zhì)區(qū)別，實(shí)現(xiàn)以核心目標(biāo)為中心的數(shù)據(jù)約減。然而，該方法中計(jì)算方向角的向量數(shù)為2d是經(jīng)驗(yàn)確定的，并沒(méi)有經(jīng)過(guò)優(yōu)化。本文將對(duì)此進(jìn)行優(yōu)化設(shè)計(jì)。

1.2 聚類有效性指標(biāo)

作為數(shù)據(jù)挖掘領(lǐng)域的重要分支，聚類是一個(gè)無(wú)監(jiān)督的學(xué)習(xí)過(guò)程，然而如何確定最佳類數(shù)一直以來(lái)都是一項(xiàng)困難的工作[6,7]。解決這類問(wèn)題的一個(gè)有效方法就是構(gòu)造聚類有效性指標(biāo)，目前研究者已經(jīng)提出了許多聚類有效性指標(biāo)，如DBI指標(biāo)、Gap指標(biāo)、PC方法等[8]。目前在工程中廣泛認(rèn)可并最為常用的為DBI指標(biāo)和Gap指標(biāo)。

1)Davies-Bouldin指標(biāo)

Davies-Bouldinindex(DBI)首先計(jì)算類內(nèi)距離Si為

(2)

式中 xj為第i類中第j個(gè)數(shù)據(jù)點(diǎn)；Ai為第i類的類中心；Ni為第i類中的數(shù)據(jù)點(diǎn)總數(shù)；一般取q=2; 類間距離Mij定義為

(3)

式中 aik為第i類中心點(diǎn)的第k個(gè)屬性值，Mij為第i類與第j類中心的距離，一般情況,取p=2;DBI指標(biāo)定義為

(4)

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

(5)

DBI指數(shù)越小，表明其對(duì)應(yīng)的聚類效果則越好。在過(guò)去的20年中，DBI指標(biāo)已經(jīng)在工程中有記錄的應(yīng)用次數(shù)超過(guò)2 000次。

2)Gap統(tǒng)計(jì)指標(biāo)

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

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

(6)

總的類內(nèi)距離用符號(hào)Wk表示，Wk的計(jì)算表達(dá)式子為

(7)

則Gapn(k)指標(biāo)定義為

(8)

2 本文提出的方法

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

2.1 基本動(dòng)機(jī)

圖1顯示了人工數(shù)據(jù)集Set1和Set2在二維坐標(biāo)下的分布情況。通過(guò)基于張開(kāi)角的數(shù)據(jù)約簡(jiǎn)方法進(jìn)行約簡(jiǎn)。 圖2、圖3分別顯示了約減30 %和90 %數(shù)據(jù)點(diǎn)后的結(jié)果，其中星號(hào)為保留下來(lái)的數(shù)據(jù)點(diǎn)，黑點(diǎn)的為約減掉的數(shù)據(jù)點(diǎn)。從約減結(jié)果可以看出，約減后的數(shù)據(jù)點(diǎn)逐漸趨向中心，數(shù)據(jù)集中類別分離性更加明顯。

圖1 原數(shù)據(jù)集Set1和Set2

圖2 30 %的數(shù)據(jù)點(diǎn)約簡(jiǎn)

圖3 90 %的數(shù)據(jù)點(diǎn)約簡(jiǎn)

因此，將數(shù)據(jù)集中非關(guān)鍵的數(shù)據(jù)去除，使數(shù)據(jù)集中類別的分離性更加明顯，容易得到更加準(zhǔn)確的類數(shù)判斷[10]。

2.2 確定計(jì)算方向角的最優(yōu)方式

上述基于張開(kāi)角測(cè)度的數(shù)據(jù)約減方法根據(jù)數(shù)據(jù)集中各個(gè)數(shù)據(jù)點(diǎn)張開(kāi)角的不同對(duì)數(shù)據(jù)集進(jìn)行約減。為了得到最優(yōu)的約減效果，確定以下優(yōu)化目標(biāo)：使數(shù)據(jù)集中所有點(diǎn)計(jì)算出的測(cè)度最大化。該優(yōu)化目標(biāo)基于兩點(diǎn)：首先，數(shù)據(jù)點(diǎn)之間的測(cè)度值差別越大，約簡(jiǎn)結(jié)果越穩(wěn)定[11]；其次，方向角測(cè)度較大的點(diǎn)對(duì)應(yīng)各個(gè)類的核心點(diǎn)而較小的點(diǎn)對(duì)應(yīng)邊界點(diǎn)；因此，數(shù)據(jù)點(diǎn)之間測(cè)度值差別的最大化將增大這兩類點(diǎn)之間的差別，從而隨著約簡(jiǎn)過(guò)程的進(jìn)行，邊界點(diǎn)以及噪聲點(diǎn)逐漸被去除，類之間的可分性越來(lái)越強(qiáng)。據(jù)此定義以下目標(biāo)函數(shù)

(9)

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

實(shí)驗(yàn)中,使用UCI中具有不同結(jié)構(gòu)和特征的15個(gè)數(shù)據(jù)集,這些數(shù)據(jù)集的特征說(shuō)明如表1所示，且這些數(shù)據(jù)集的正確類數(shù)是已知的。

表1 15個(gè)UCI中真實(shí)數(shù)據(jù)集

實(shí)驗(yàn)中,首先使用張開(kāi)角的數(shù)據(jù)約減方法對(duì)數(shù)據(jù)集進(jìn)行不同比例的約減，對(duì)約減前后的數(shù)據(jù)集運(yùn)用k-means進(jìn)行聚類，然后對(duì)聚類結(jié)果分別應(yīng)用DBI、Gap兩個(gè)指標(biāo)進(jìn)行最優(yōu)類數(shù)的判別，實(shí)驗(yàn)結(jié)果如表2、表3以及圖4、圖5所示。從實(shí)驗(yàn)結(jié)果中可以得出以下結(jié)論：

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

表2 DBI指標(biāo)聚類數(shù)

表3 Gap指標(biāo)聚類數(shù)

圖4 Glass數(shù)據(jù)集約減前后DBI指標(biāo)

圖5 Iris數(shù)據(jù)集約減前后Gap指標(biāo)

2)利用有效性指標(biāo)得到的結(jié)果并非與真實(shí)類數(shù)完全一致，從結(jié)果可以看出，DBI指標(biāo)類數(shù)判別的準(zhǔn)確性要高于Gap指標(biāo)的準(zhǔn)確性。 因?yàn)椴煌闹笜?biāo)適用的條件不同，聚類有效性評(píng)價(jià)一直是聚類分析中一個(gè)重要的研究方向，目前還沒(méi)有一種有效性指標(biāo)可以完全適用于所有聚類算法。

3)如圖4、圖5中Glass，Iris數(shù)據(jù)集指標(biāo)曲線圖所示，約減后數(shù)據(jù)集的指標(biāo)曲線圖中最優(yōu)點(diǎn)位置更加突出，其他數(shù)據(jù)集與之類似。

4 結(jié) 論

通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)的分析，文中將基于張開(kāi)角測(cè)度的數(shù)據(jù)約減方法優(yōu)化后針對(duì)一般數(shù)據(jù)集能夠進(jìn)行有效約減，并將該方法應(yīng)用于聚類分析中最佳類數(shù)的判別問(wèn)題。通過(guò)對(duì)具有不同數(shù)據(jù)結(jié)構(gòu)和密度的數(shù)據(jù)集進(jìn)行測(cè)試，可以發(fā)現(xiàn)約減后得到的最優(yōu)類數(shù)與數(shù)據(jù)集的真實(shí)類數(shù)更加接近，這表明約減后數(shù)據(jù)集中類別的分離性更加明顯，因此，該方法對(duì)聚類分析中最佳類數(shù)的判別具有一定的有效性和有用性。

該方法還有一定的不足之處，因?yàn)榈玫奖容^好的最優(yōu)類數(shù)是以時(shí)間為代價(jià)的，約減的過(guò)程是一個(gè)逐層循環(huán)的過(guò)程，每次循環(huán)都要計(jì)算每個(gè)點(diǎn)周圍的鄰域點(diǎn)，因此，進(jìn)一步提高該算法的效率有待進(jìn)一步研究。

[1] 李 晨,王亞茹,岳士弘.基于張開(kāi)角測(cè)度的數(shù)據(jù)約簡(jiǎn)[J].傳感器與微系統(tǒng),2016,35(4):25-28.

[2] 周世兵.聚類分析中的最佳聚類確定方法研究及應(yīng)用[D].無(wú)錫：江南大學(xué),2011.

[3] Sergios T,Konstantinos K.模式識(shí)別[M].4版.北京:電子工業(yè)出版社,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] 白素琴,吳小俊.基于模糊聚類算法的有效性指標(biāo)[J].江南大學(xué)學(xué)報(bào),2007,6(6):878-882.

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

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

[9] 周開(kāi)樂(lè),楊善林,丁 帥,等.聚類有效性研究綜述[J].系統(tǒng)工程理論與實(shí)踐,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].山西大學(xué)學(xué)報(bào):自然科學(xué)版,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61573251)

TP 391.4

A

1000—9787(2017)03—0055—03

于 曉(1991-)，女，碩士研究生，主要研究方向?yàn)槟Ｊ阶R(shí)別。