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

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

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

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

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

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

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

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

0 引言

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

1 相關(guān)工作

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

1.1 Hubness現(xiàn)象

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

1.2 Hub聚類算法

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

2 PCA-Hubness聚類算法

2.1 算法框架

PCA-Hubness聚類算法的整體流程圖如下所示：

圖1 PCA-Hubness算法流程圖

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

2.2 基于偏度的降維方法

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

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

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

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

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

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

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

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

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

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

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

表2 輪廓系數(shù)

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

4 結(jié)語

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

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

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

2017-03-09

2017-04-06