葛亮，郎江濤，唐黃，唐允恒

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

面向高維數(shù)據(jù)的PCA-Hubness聚類(lèi)方法

葛亮，郎江濤，唐黃，唐允恒

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

hub聚類(lèi)算法可以解決傳統(tǒng)聚類(lèi)算法無(wú)法處理高維數(shù)據(jù)的問(wèn)題。然而，由于它未考慮數(shù)據(jù)中的冗余和噪聲特征，從而降低聚類(lèi)性能。因此，提出PCA-Hubness聚類(lèi)方法用于提高高維數(shù)據(jù)的聚類(lèi)性能。PCA-Hubness聚類(lèi)方法利用逆近鄰數(shù)的偏度和本征維度的相互關(guān)系，以偏度的變化率為降維依據(jù)，保證在對(duì)高維數(shù)據(jù)降維時(shí)不會(huì)損失過(guò)多的有價(jià)值信息，有利于提高聚類(lèi)效果。此算法在UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，相比hub聚類(lèi)算法，輪廓系數(shù)平均提高15%。

Hub聚類(lèi)；高維數(shù)據(jù)；偏度；本征維度；PCA

0 引言

通常在無(wú)監(jiān)督學(xué)習(xí)過(guò)程中，聚類(lèi)是將元素分成不同的組別或者更多的子集，使得分配到相同簇中的元素彼此之間比其他的數(shù)據(jù)點(diǎn)更為相似，也就是說(shuō)，聚類(lèi)算法的目的是要增加類(lèi)內(nèi)的相似性并減小類(lèi)間的相似性。多年來(lái)，已提出多種聚類(lèi)算法，可以大致分為以下五類(lèi)：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[1]。以上這五類(lèi)傳統(tǒng)聚類(lèi)算法并不適用于高維數(shù)據(jù)聚類(lèi)。雖然hub聚類(lèi)算法可以對(duì)高維數(shù)據(jù)聚類(lèi)，然而當(dāng)存在冗余和噪聲數(shù)據(jù)時(shí)，聚類(lèi)效果表現(xiàn)不佳。傳統(tǒng)聚類(lèi)算法不適用于高維數(shù)據(jù)聚類(lèi)主要是由以下兩個(gè)因素引起的：數(shù)據(jù)的稀疏性和距離的集中。前者是指當(dāng)維數(shù)提高時(shí)，數(shù)據(jù)空間的體積提升過(guò)快，因而有用數(shù)據(jù)變得十分稀疏[2]。后者是指高維數(shù)據(jù)空間表示出現(xiàn)了某種程度上的反直覺(jué)特性。隨著維度增加，數(shù)據(jù)間的距離趨于相同，這可能會(huì)導(dǎo)致基于距離的算法性能變差。這便是機(jī)器學(xué)習(xí)中令人頭疼的維數(shù)災(zāi)難問(wèn)題。然而，由于本征維數(shù)的存在，許多高維空間中的數(shù)據(jù)可降低為低維空間數(shù)據(jù)，而不必?fù)p失重要信息。在高維數(shù)據(jù)中，某些點(diǎn)易頻繁地出現(xiàn)在其他點(diǎn)的k近鄰列表中，這種現(xiàn)象稱(chēng)為hubness現(xiàn)象，那些受“歡迎”的點(diǎn)稱(chēng)之為hubs[6]。高維數(shù)據(jù)中存在著的冗余和噪聲特征維度對(duì)聚類(lèi)造成了嚴(yán)重的影響，然而無(wú)目標(biāo)的降維又會(huì)損失重要的有價(jià)值信息。本文利用逆近鄰數(shù)的偏度和本征維度的相互關(guān)系，以偏度的變化率為降維依據(jù)，保證了在對(duì)高維數(shù)據(jù)降維時(shí)不會(huì)損失過(guò)多的有價(jià)值信息，有利于提高聚類(lèi)效果，實(shí)驗(yàn)結(jié)果表明此方法是可行的。

1 相關(guān)工作

近年來(lái)在涉及聲音和圖像數(shù)據(jù)的若干應(yīng)用領(lǐng)域中觀察到hubness現(xiàn)象（Aucouturier and Pachet，2007；Doddington et al.，1998；Hicklin et al.，2005），此外，Jebara等人簡(jiǎn)要地描述了在半監(jiān)督學(xué)習(xí)的鄰域圖構(gòu)造過(guò)程中出現(xiàn)的hubness現(xiàn)象（Tony Jebara et al 2009）[3]，Amina M等人通過(guò)將hub引入到K-Means算法中從而形成了hub聚類(lèi)分析算法（Amina M et al 2015）[4]。盡管在數(shù)據(jù)聚類(lèi)中hubness這一現(xiàn)象并沒(méi)有給予過(guò)多的關(guān)注，然而k近鄰列表卻廣泛使用在諸多聚類(lèi)中。k近鄰列表通過(guò)觀察k個(gè)最近鄰所確定的空間體積來(lái)計(jì)算密度估計(jì)。基于密度的聚類(lèi)算法的主要目標(biāo)是尋找被低密度區(qū)域分離的高密度區(qū)域[5]。在高維空間中，這常常難以估計(jì)，因?yàn)閿?shù)據(jù)非常稀疏。Hub聚類(lèi)算法可以處理高維數(shù)據(jù)，然而并未對(duì)高維數(shù)據(jù)中的冗余和噪聲數(shù)據(jù)給予關(guān)注，從而導(dǎo)致聚類(lèi)性能不佳。

1.1 Hubness現(xiàn)象

令D?Rd，d∈{1，2，…}表示一組數(shù)據(jù)集，其中x1，x2，…，xn為數(shù)據(jù)集D中的元素。令dist表示在Rd空間中的一個(gè)距離函數(shù)pi，k，其中i，k∈{1，2，…，n}，定義如下：

1.2 Hub聚類(lèi)算法

具有高h(yuǎn)ubness分?jǐn)?shù)的點(diǎn)更易接近簇中心[6]。將hubness視為一種局部中心度量方式，則可以將它應(yīng)用到聚類(lèi)中。Hub聚類(lèi)算法主要有以下4種：deterministic，probabilistic，hybrid和kernel。這4種方法均為KMeans算法的擴(kuò)展。在deterministic方法中，首先確定簇的數(shù)量，然后使用K-Means算法進(jìn)行聚類(lèi)，在每次聚類(lèi)的過(guò)程中將當(dāng)前簇中具有高h(yuǎn)ubness分?jǐn)?shù)的點(diǎn)作為簇中心，例如，K-hub聚類(lèi)算法[9]。Probabilistic方法使用模擬退火算法以一定概率θ（=min（1，t/NProb））選擇高h(yuǎn)ubness分?jǐn)?shù)的點(diǎn)作為當(dāng)前簇的中心，例如，HPC聚類(lèi)算法[9]和GHPC聚類(lèi)算法[9]。Deterministic和probabilistic方法只依賴于距離矩陣而不必關(guān)心數(shù)據(jù)的表現(xiàn)形式。為了盡可能地獲取數(shù)據(jù)的中心位置則需要使用hybrid方法。在hybrid方法中，使用數(shù)據(jù)點(diǎn)的hubness分?jǐn)?shù)來(lái)指導(dǎo)搜索，但最終會(huì)形成基于質(zhì)心的簇結(jié)構(gòu)，例如，HPKM聚類(lèi)算法[9]和GHPKM聚類(lèi)算法[9]。Kernel方法在前三者基礎(chǔ)上可以對(duì)非超球面簇集進(jìn)行處理，例如，Ker-KM聚類(lèi)算法[4]和Ker-GHPKM聚類(lèi)算法[4]。Hub聚類(lèi)算法用于高維數(shù)據(jù)，由此可見(jiàn)隨著維度的增加聚類(lèi)時(shí)間和迭代次數(shù)也隨之增加。雖然hub聚類(lèi)算法可以處理高維數(shù)據(jù)，然而高維數(shù)據(jù)中存在的冗余和噪聲特征卻并未得到解決，這不利于聚類(lèi)分析。

2 PCA-Hubness聚類(lèi)算法

2.1 算法框架

PCA-Hubness聚類(lèi)算法的整體流程圖如下所示：

圖1 PCA-Hubness算法流程圖

首先，對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將數(shù)據(jù)的每一維進(jìn)行歸一化；其次，構(gòu)建KNN鄰域矩陣，計(jì)算每個(gè)點(diǎn)的逆近鄰數(shù)。然后，用PCA進(jìn)行降維，在降維的過(guò)程中通過(guò)偏度的變化率來(lái)控制降維的程度，以防損失過(guò)多重要的有價(jià)值信息。最后，在獲取降維數(shù)據(jù)后利用hub聚類(lèi)算法進(jìn)行聚類(lèi)分析。

2.2 基于偏度的降維方法

關(guān)于數(shù)據(jù)降維的方法有多種，本文采用的是主成分分析法。主成分分析（Principal Components Analysis，PCA）常用于降低數(shù)據(jù)集的維數(shù)，同時(shí)保留數(shù)據(jù)集中方差貢獻(xiàn)最大的特征，即保留低階主成分，除去高階主成分[7]。主成分分析通過(guò)對(duì)數(shù)據(jù)集的協(xié)方差矩陣進(jìn)行特征分解，從而獲得數(shù)據(jù)集的主成分（特征向量）與權(quán)重（特征值）。若沒(méi)有假設(shè)信息信號(hào)模型，那么主成分分析在降維時(shí)無(wú)法保證不損失信息，其中信息的衡量指標(biāo)是香農(nóng)熵。然而，香農(nóng)熵卻無(wú)法作為數(shù)據(jù)有效降維時(shí)的衡量標(biāo)準(zhǔn)，因此本文采用了Nk的偏度這一指標(biāo)。下文中將會(huì)探討在使用降維技術(shù)PCA的情況下Nk的偏度和本征維數(shù)的相互作用。此研究的主要目的在于探討降維是否能夠緩解Nk的偏度這一問(wèn)題。“因?yàn)橛^察到的Nk的偏度與與本征維數(shù)強(qiáng)烈相關(guān)，本征維數(shù)對(duì)Nk到數(shù)據(jù)集的均值或到最接近簇的均值有著積極影響，這意味著在較高（本征）維度中，hubs變得越來(lái)越接近數(shù)據(jù)集或最接近簇的中心”[6]。

實(shí)驗(yàn)過(guò)程中采用的距離度量方法是閔可夫斯基距離（Minkowski distance），它是衡量數(shù)值點(diǎn)之間距離的一種非常常見(jiàn)的方法，假設(shè)數(shù)值點(diǎn)P和Q坐標(biāo)如下：

那么，閔可夫斯基距離定義為：

該距離最常用的p值是2和1，前者是歐幾里得距離（Euclidean distance），后者是曼哈頓距離（Manhattan distance）。

為了探究在使用降維技術(shù)的情況下Nk的偏度和本征維數(shù)的相互作用，本文使用了來(lái)自加州大學(xué)爾灣分校（UCI）機(jī)器學(xué)習(xí)庫(kù)[10]的數(shù)據(jù)集進(jìn)行觀測(cè)Nk（k=10）的分布。在表1中包含了以下信息：數(shù)據(jù)集的樣本數(shù)（n，第2列）；數(shù)據(jù)樣本的特征維數(shù)（d，第3列）；數(shù)據(jù)樣本的類(lèi)別數(shù)（cls，第4列）。

表1 真實(shí)數(shù)據(jù)集

圖2描述了針對(duì)若干個(gè)真實(shí)數(shù)據(jù)集（musk，sonar，mfeat-fou等）通過(guò)降維方法獲得的維數(shù)占原有數(shù)據(jù)集維數(shù)的百分比與之間的相互關(guān)系。數(shù)據(jù)之間距離的度量方法為Minkowski距離，其中p的取值分別為：2（Euclidean distance）。從左往右觀察，對(duì)于大部分?jǐn)?shù)據(jù)集而言利用PCA降維算法，保持相對(duì)恒定直到降維后留下特征的百分比較小時(shí)才會(huì)陡然下降。因此，當(dāng)達(dá)到數(shù)據(jù)集的本征維數(shù)時(shí)若繼續(xù)減小維數(shù)則會(huì)導(dǎo)致有價(jià)值的信息丟失。針對(duì)PCA方法對(duì)數(shù)據(jù)進(jìn)行降維時(shí)，若降維后本征維數(shù)未發(fā)生明顯變化，那么降維并不會(huì)對(duì)hubness這一現(xiàn)象有顯著影響。

圖2 特征維度與偏度的關(guān)系

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于加州大學(xué)爾灣分校（UCI）機(jī)器學(xué)習(xí)庫(kù)。表2中第5列為真實(shí)數(shù)據(jù)集的偏度值，其中10代表k近鄰數(shù)。從表中數(shù)據(jù)可以看出，對(duì)于大多數(shù)數(shù)據(jù)集的的分布發(fā)生了傾斜。雖然k的值是固定的，但是使用其它的k值也可得到類(lèi)似的結(jié)果。采用輪廓系數(shù)（Silhouette Index）作為聚類(lèi)結(jié)果的評(píng)測(cè)指標(biāo)[7]，其計(jì)算公式如下所示：

其中，ai表示i向量到同一簇內(nèi)其他點(diǎn)不相似程度的平均值，bi表示i向量到其他簇的平均不相似程度的最小值?？梢?jiàn)輪廓系數(shù)的值總是介于[-1，1]，越趨近于1代表內(nèi)聚度和分離度都相對(duì)較優(yōu)。將所有點(diǎn)的輪廓系數(shù)求平均，就是該聚類(lèi)結(jié)果總的輪廓系數(shù)。本文方法與KMEANS[9]、GHPKM[9]、Ker-KM[4]和Ker-KM[4]方法進(jìn)行了比較，其中PH-KM為本文的聚類(lèi)方法。實(shí)驗(yàn)結(jié)果如表2所示，下表中加粗的數(shù)據(jù)表示當(dāng)前數(shù)據(jù)集的最優(yōu)值。

表2 輪廓系數(shù)

對(duì)于每一個(gè)數(shù)據(jù)集而言，取KMEANS、GHPKM、Ker-KM以及Ker-GHPKM聚類(lèi)算法中輪廓系數(shù)的最大值作為經(jīng)典聚類(lèi)算法的最優(yōu)值，然后同本文的PHKM聚類(lèi)算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，相比之前的聚類(lèi)算法，本文提出的PH-KM聚類(lèi)算法在輪廓系數(shù)上平均提高了15%。從實(shí)驗(yàn)結(jié)果可以看出，在數(shù)據(jù)集缺乏hubness特性的情況下，GHPKM、Ker-GHPKM等hub聚類(lèi)算法表現(xiàn)不佳，其性能接近于KMEANS算法；然而在數(shù)據(jù)集呈現(xiàn)出較高的hubness特性時(shí)，GHPKM、Ker-GHPKM等hub聚類(lèi)算法的表現(xiàn)要優(yōu)于KMEANS算法。同時(shí)，本文提出的PH-KM聚類(lèi)算法無(wú)論數(shù)據(jù)集是否呈現(xiàn)出較高的hubness特性，均可以取得不錯(cuò)的聚類(lèi)效果，相比之前的聚類(lèi)算法適用范圍更廣，聚類(lèi)性能更佳。

4 結(jié)語(yǔ)

在高維數(shù)據(jù)空間中，傳統(tǒng)的聚類(lèi)算法已變得不再適用。雖然hub聚類(lèi)算法可以處理上述問(wèn)題，但是它卻忽略了高維數(shù)據(jù)中的冗余和噪聲數(shù)據(jù)，從而導(dǎo)致聚類(lèi)效果不佳。本文以Nk的偏度與本征維數(shù)強(qiáng)烈正相關(guān)為理論基礎(chǔ)，通過(guò)構(gòu)建數(shù)據(jù)集的KNN鄰域矩陣，以偏度的變化率作為降維依據(jù)，最后再對(duì)降維后的數(shù)據(jù)集進(jìn)行聚類(lèi)。實(shí)驗(yàn)結(jié)果表明，無(wú)論數(shù)據(jù)集是否含有較高的hubness特性，本文提出的PH-KM聚類(lèi)算法均可以取得不錯(cuò)的聚類(lèi)效果，相比之前的聚類(lèi)算法，輪廓系數(shù)平均提高了15%。

[1]Jiawei Han．?dāng)?shù)據(jù)挖掘概念與技術(shù)[C].機(jī)械工業(yè)出版社，2012.

[2]Houle，M.E.，Kriegel，H.P.，Kr?ger，P.，Schubert，E.，Zimek.A.Scientific and Statistical Database Management[J]，Lecture Notes in Computer Science 6187:482.2010.

[3]Tony Jebara，Jun Wang，Shih-Fu Chang.Graph Construction and B-Matching for Semi-Supervised Learning[J].In Proceedings of the 26th International Conference on Machine Learning（ICML），pages 441-448，2009.

[4]Amina M，Syed Farook K.A Novel Approach for Clustering High-Dimensional Data using Kernel Hubness[J].International Confenrence on Advances in Computing and Communication，2015.

[5]Ester Martin，Kriegel Hans-Peter，Sander，J?rg，Xu，Xiaowei，Simoudis Evangelos，Han，Jiawei，F(xiàn)ayyad Usama M.，eds.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[J].Proceedings of the Second International Conference on Knowledge Discovery and Data Mining（KDD-96）.AAAI Press.pp.226-231.

[6]MilosˇRadovanovic，Alexandros Nanopoulos，Mirjana Ivanovic.Hubs in Space:Popular Nearest Neighbors in High-Dimensional Data [J].Journal of Machine Learning Research 11（2010）2487-2531，2010

[7]Abdi.H，Williams L.J.Principal Component Analysis[J].Wiley Interdisciplinary Reviews:Computational Statistics，2（4）:433-459，2010

[8]Peter J.Rousseeuw.Silhouettes:a Graphical Aid to the Interpretation and Validation of Cluster Analysis[J].Computational and Applied Mathematics，20:53-65，1987.

[9]Nenad Toma sev，Milo s Radovanovi c，Dunja Mladeni c，Mirjana Ivanovi c.The Role of Hubness in Clustering High-Dimensional Data [J].IEEE Transactions On Knowledge And Data Engineering,Vol.26，No.3.2014.

[10]Lichman，M.UCI Machine Learning Repository[http://archive.ics.uci.edu/ml].Irvine，CA:University of California，School of Information and Computer Science，2013

Clustering High-Dimensional Data Using PCA-Hubness

GE Liang，LANG Jiang-tao，TANG Huang，TANG Yun-heng

（School of Computer Science，Chongqing University，Chongqing 400044）

The hub-based clustering algorithm can solve high dimensional data problem that traditional clustering algorithm cannot handle.However，since it does not handle redundancy and noise features in high-dimensional data，the clustering performance is reduced.Therefore，PCA-Hubness clustering method is proposed to solve the clustering problem of high-dimensional data.The PCA-Hubness clustering method utilizes the relationship between skewness of anti-nearest-neighborhood’s number and intrinsic dimension.According to the rate of change of the skewness,it is guaranteed that the high dimensional data will not lose too much Information.And it is conducive to improving the clustering effect.This algorithm performs experiments on the UCI data set,and the Silhouette Index are increased by an average of 15%compared to hub-based clustering algorithm.

Skewness;Intrinsic Dimension;PCA;Hub Clustering;High-Dimensional Data

1007-1423（2017）11-0052-05

10.3969/j.issn.1007-1423.2017.11.010

葛亮（1980-），男，重慶人，博士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、圖像處理

郎江濤（1990-），男，山西人，碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)

唐黃（1991-），男，重慶人，碩士，本科，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)

唐允恒（1992-），男，重慶人，碩士，本科，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)

2017-03-09

2017-04-06