一種有效的面向高維數(shù)值型數(shù)據(jù)的聚類方法

李順勇，宋云勝，趙興旺

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

0 引言

聚類作為數(shù)據(jù)挖掘中的一項(xiàng)重要技術(shù)，人們利用對(duì)數(shù)據(jù)的分析從中發(fā)掘有用的信息。作為一種無監(jiān)督的學(xué)習(xí)方法，聚類從數(shù)學(xué)分析的角度提供了一種對(duì)數(shù)據(jù)進(jìn)行準(zhǔn)確、細(xì)致的分析工具。對(duì)一個(gè)給定的數(shù)據(jù)（對(duì)象、記錄）集，聚類或劃分的目的就是把這些對(duì)象歸到相應(yīng)的組或“簇”中，使得類內(nèi)（intra-class）數(shù)據(jù)或?qū)ο蟮南嗨菩宰顝?qiáng)，以緊致度描述；類間（inter-class）數(shù)據(jù)或?qū)ο蟮南嗨菩宰钊酰苑蛛x度描述。聚類質(zhì)量的高低通常取決于聚類方法所使用的相似性度量方法和實(shí)現(xiàn)方式，作為一種無監(jiān)督的學(xué)習(xí)方法（unsupervised learning），能夠從研究對(duì)象的特征數(shù)據(jù)中挖掘出有用的模式。因此，聚類是一種強(qiáng)有力的信息處理方法。它在數(shù)據(jù)挖掘、圖像分割、模式識(shí)別、空間遙感技術(shù)、特征提取、信號(hào)壓縮以及在中醫(yī)醫(yī)藥等諸多領(lǐng)域中有著廣泛的應(yīng)用，并取得了一些令人滿意的效果。

數(shù)據(jù)挖掘涉及的數(shù)據(jù)可能包括很多屬性，有時(shí)可達(dá)成百乃至上千、上萬。聚類方法在處理這樣的高維數(shù)據(jù)時(shí)往往會(huì)碰到較大的困難。聚類方法的選擇取決于數(shù)據(jù)的類型和聚類應(yīng)用的目的。常用的聚類方法有基于劃分的、基于層次的、基于密度的、基于網(wǎng)格的以及基于模型的等。而相似性常常是用來計(jì)算聚類的有效方法。本文提出了一種針對(duì)高維數(shù)值型數(shù)據(jù)進(jìn)行聚類的有效方法，利用相關(guān)數(shù)據(jù)進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了其理論和應(yīng)用的有效性。

UCI Machine Learning Repository中有許多高維數(shù)值型數(shù)據(jù)集，部分?jǐn)?shù)據(jù)集見表1。

表1 UCI中的部分?jǐn)?shù)值型數(shù)據(jù)集Table 1 Parts of the UCI numeric data set

我們以SPECTF Heart為例，該數(shù)據(jù)集有267個(gè)對(duì)象，44個(gè)屬性，分為兩類，其數(shù)據(jù)表示如圖1，其中橫坐標(biāo)為維數(shù)個(gè)數(shù)（Dimension（a）），縱坐標(biāo)為無量綱化的數(shù)值（Dimensionless Number），圖2類似。

Fig.1 Discrimination of SPECTF Heart data圖1 SPECTF Heart數(shù)據(jù)區(qū)分

從圖1中我們很難區(qū)分它們之間的相似度或類別歸屬。為了清楚地表示數(shù)據(jù)之間的區(qū)別，以Anseombe數(shù)據(jù)［1］為例。圖2中顯示Anseombe數(shù)據(jù)中的x1，x2，x3以及y的11個(gè)屬性值都比較接近，較難區(qū)分，那么哪個(gè)和y更接近（或可歸為一類）？

Fig.2 Discrimination of Anseombe data圖2 Anseombe數(shù)據(jù)區(qū)分

實(shí)際問題當(dāng)中，有許多這樣的數(shù)據(jù)需要區(qū)分或?qū)λ鼈冞M(jìn)行歸類。一個(gè)“好”的方法只有在實(shí)際應(yīng)用中才能體現(xiàn)其優(yōu)勢(shì)。

1 三類經(jīng)典的距離度量方法［2］

設(shè)，x＝（x1，x2，…，xn），y＝（y1，y2，…，yn）為兩個(gè)向量。

1.1 相關(guān)系數(shù)（Pearson correlation coefficient）

相關(guān)系數(shù)通常用來描述兩個(gè)向量的相關(guān)性。

｜ρ｜值越大，x，y相似性越好。

1.2 瑞利熵（Rênyi entropy）［3］

熵用來度量無序性，熵值越大越好，類的區(qū)分度也越好［4］，其中α＝2，σ＝3。

1.3 歐氏距離（Euclidean distance）

dE值越小，x，y相似度越大，dE＝0時(shí)，表明x，y二者完全一樣。

以上三種方法都是經(jīng)典的計(jì)算相似性的方法，各有優(yōu)劣，還有一些計(jì)算相似性的方法見文獻(xiàn)［5－9］。利用1.1、1.2、1.3對(duì)Anseombe中的數(shù)據(jù)計(jì)算x1，x2，x3和y的相似度，其結(jié)果如表2。

表2 經(jīng)典方法相似度比較Table 2 Similarity comparison of Classical method

表2顯示三種經(jīng)典方法對(duì)x1，x2，x3和y的整體相似度區(qū)別不大，有的幾乎難于區(qū)分，但圖2顯示x1，x2，x3和y還是有區(qū)別的。

為了有效地區(qū)別x1，x2，x3和y，本文提出了新的線性相似度（Linear Measure）。

2 新的線性相似性度（LM）

3 實(shí)驗(yàn)性分析對(duì)比

為了檢驗(yàn)文中提出方法的有效性，我們重新對(duì)表1中的數(shù)據(jù)進(jìn)行了相似度計(jì)算，結(jié)果見表4。

表3 LM-dnew方法Table 3 LM-dnew method

由表3我們明顯可以看出x3和y最相似，可以歸為一類（組），x2和y次之，x1和y最差。圖3為L(zhǎng)M-dnew和三種經(jīng)典方法的比較演示，圖3中顯示新的線性相似度對(duì)該類數(shù)據(jù)有較好的靈敏度。

在相似性計(jì)算和聚類問題上，我們所尋求的方法，一方面希望相似性越精確越好，另一方面，更希望方法越簡(jiǎn)單越好。

文中提出的方法既然能處理兩兩數(shù)據(jù)之間的相似性問題，那么它也就能處理一個(gè)數(shù)據(jù)和一個(gè)類之間的問題，同時(shí)也就能處理類和類之間的問題，這將會(huì)是我們以后研究的新方向。

Fig.3 Comparison of four methods圖3 四種方法比較演示

4 結(jié)論

本文提出了一種有效的面向高維數(shù)值型數(shù)據(jù)的聚類方法，通過實(shí)驗(yàn)比較，結(jié)果顯示該方法有較好的靈敏度，能對(duì)某些高維數(shù)值型數(shù)據(jù)起到較好的聚類效果，值得進(jìn)一步研究和推廣。

［1］ Suykens J A K.Nonlinear Modeling and Support Vector Machines［J］.IEEEInstrumentationandMeasurementTechnologyConference.Budapest，Hungary，2001：21-23.

［2］ 張宇，劉雨東，計(jì)釗.向量相似度測(cè)度方法［J］.聲學(xué)技術(shù)，2009，28（4）：532-536.

［3］ Renyi A.On Measures of Entropy and Information［C］.Proceeding of the 4th Berkeley Symposium on Mathematics of Statistics and Probability，1961：547-561.

［4］ Liang Ji-ye，Zhao Xing-wang，Li De-yu，etal.Determining the Number of Clusters Using Information Entropy for Mixed Data［J］.PatternRecognition，2012，45：2251-2265.

［5］ Jiang Qing-shan，Zhang Yan-ping，Chen Li-fei.An Initilization Method for Subspace Clustering Algorithm［J］.IJIntelligentSystemsandApplications，2011，3：54-61.

［6］ Christian Borgelt.Accelerating Fuzzy Clustering［J］.InformationSciences，2009，179：3985-3997.

［7］ Cheng Victor，Li Chun-hung，Kwokb James T，etal.Dissimilarity Learning for Nominal Data［J］.PatternRecognition，2004，37：1471-1477.

［8］ Rudi L.Cilibrasi and Paul M.B.Vitanyi.The Google Similarity Distance［J］.IEEETransactionsonKnowledgeandData Engineering，2007，19（3）：370-383.

［9］ Nikolaj Tatti.Distances Between Data Sets Based on Summary Statistics［J］.JournalofMachineLearningResearch，2007，8：131-154.

［10］ Cao Fu-yuan，Liang Ji-ye，Li De-yu，etal.A Dissimilarity Measure for the k-Modes Clustering Algorithm［J］.Knowledge-BasedSystems，2012，26：120-127.