面向高维数据的PCA-Hubness聚类方法

葛亮，郎江涛，唐黄，唐允恒

（重庆大学计算机学院，重庆 400044）

面向高维数据的PCA-Hubness聚类方法

葛亮，郎江涛，唐黄，唐允恒

（重庆大学计算机学院，重庆 400044）

hub聚类算法可以解决传统聚类算法无法处理高维数据的问题。然而，由于它未考虑数据中的冗余和噪声特征，从而降低聚类性能。因此，提出PCA-Hubness聚类方法用于提高高维数据的聚类性能。PCA-Hubness聚类方法利用逆近邻数的偏度和本征维度的相互关系，以偏度的变化率为降维依据，保证在对高维数据降维时不会损失过多的有价值信息，有利于提高聚类效果。此算法在UCI数据集上进行实验，相比hub聚类算法，轮廓系数平均提高15%。

Hub聚类；高维数据；偏度；本征维度；PCA

0 引言

通常在无监督学习过程中，聚类是将元素分成不同的组别或者更多的子集，使得分配到相同簇中的元素彼此之间比其他的数据点更为相似，也就是说，聚类算法的目的是要增加类内的相似性并减小类间的相似性。多年来，已提出多种聚类算法，可以大致分为以下五类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法[1]。以上这五类传统聚类算法并不适用于高维数据聚类。虽然hub聚类算法可以对高维数据聚类，然而当存在冗余和噪声数据时，聚类效果表现不佳。传统聚类算法不适用于高维数据聚类主要是由以下两个因素引起的：数据的稀疏性和距离的集中。前者是指当维数提高时，数据空间的体积提升过快，因而有用数据变得十分稀疏[2]。后者是指高维数据空间表示出现了某种程度上的反直觉特性。随着维度增加，数据间的距离趋于相同，这可能会导致基于距离的算法性能变差。这便是机器学习中令人头疼的维数灾难问题。然而，由于本征维数的存在，许多高维空间中的数据可降低为低维空间数据，而不必损失重要信息。在高维数据中，某些点易频繁地出现在其他点的k近邻列表中，这种现象称为hubness现象，那些受“欢迎”的点称之为hubs[6]。高维数据中存在着的冗余和噪声特征维度对聚类造成了严重的影响，然而无目标的降维又会损失重要的有价值信息。本文利用逆近邻数的偏度和本征维度的相互关系，以偏度的变化率为降维依据，保证了在对高维数据降维时不会损失过多的有价值信息，有利于提高聚类效果，实验结果表明此方法是可行的。

1 相关工作

近年来在涉及声音和图像数据的若干应用领域中观察到hubness现象（Aucouturier and Pachet，2007；Doddington et al.，1998；Hicklin et al.，2005），此外，Jebara等人简要地描述了在半监督学习的邻域图构造过程中出现的hubness现象（Tony Jebara et al 2009）[3]，Amina M等人通过将hub引入到K-Means算法中从而形成了hub聚类分析算法（Amina M et al 2015）[4]。尽管在数据聚类中hubness这一现象并没有给予过多的关注，然而k近邻列表却广泛使用在诸多聚类中。k近邻列表通过观察k个最近邻所确定的空间体积来计算密度估计。基于密度的聚类算法的主要目标是寻找被低密度区域分离的高密度区域[5]。在高维空间中，这常常难以估计，因为数据非常稀疏。Hub聚类算法可以处理高维数据，然而并未对高维数据中的冗余和噪声数据给予关注，从而导致聚类性能不佳。

1.1 Hubness现象

令D⊂Rd，d∈{1，2，…}表示一组数据集，其中x1，x2，…，xn为数据集D中的元素。令dist表示在Rd空间中的一个距离函数pi，k，其中i，k∈{1，2，…，n}，定义如下：

1.2 Hub聚类算法

具有高hubness分数的点更易接近簇中心[6]。将hubness视为一种局部中心度量方式，则可以将它应用到聚类中。Hub聚类算法主要有以下4种：deterministic，probabilistic，hybrid和kernel。这4种方法均为KMeans算法的扩展。在deterministic方法中，首先确定簇的数量，然后使用K-Means算法进行聚类，在每次聚类的过程中将当前簇中具有高hubness分数的点作为簇中心，例如，K-hub聚类算法[9]。Probabilistic方法使用模拟退火算法以一定概率θ（=min（1，t/NProb））选择高hubness分数的点作为当前簇的中心，例如，HPC聚类算法[9]和GHPC聚类算法[9]。Deterministic和probabilistic方法只依赖于距离矩阵而不必关心数据的表现形式。为了尽可能地获取数据的中心位置则需要使用hybrid方法。在hybrid方法中，使用数据点的hubness分数来指导搜索，但最终会形成基于质心的簇结构，例如，HPKM聚类算法[9]和GHPKM聚类算法[9]。Kernel方法在前三者基础上可以对非超球面簇集进行处理，例如，Ker-KM聚类算法[4]和Ker-GHPKM聚类算法[4]。Hub聚类算法用于高维数据，由此可见随着维度的增加聚类时间和迭代次数也随之增加。虽然hub聚类算法可以处理高维数据，然而高维数据中存在的冗余和噪声特征却并未得到解决，这不利于聚类分析。

2 PCA-Hubness聚类算法

2.1 算法框架

PCA-Hubness聚类算法的整体流程图如下所示：

图1 PCA-Hubness算法流程图

首先，对数据集进行预处理，将数据的每一维进行归一化；其次，构建KNN邻域矩阵，计算每个点的逆近邻数。然后，用PCA进行降维，在降维的过程中通过偏度的变化率来控制降维的程度，以防损失过多重要的有价值信息。最后，在获取降维数据后利用hub聚类算法进行聚类分析。

2.2 基于偏度的降维方法

关于数据降维的方法有多种，本文采用的是主成分分析法。主成分分析（Principal Components Analysis，PCA）常用于降低数据集的维数，同时保留数据集中方差贡献最大的特征，即保留低阶主成分，除去高阶主成分[7]。主成分分析通过对数据集的协方差矩阵进行特征分解，从而获得数据集的主成分（特征向量）与权重（特征值）。若没有假设信息信号模型，那么主成分分析在降维时无法保证不损失信息，其中信息的衡量指标是香农熵。然而，香农熵却无法作为数据有效降维时的衡量标准，因此本文采用了Nk的偏度这一指标。下文中将会探讨在使用降维技术PCA的情况下Nk的偏度和本征维数的相互作用。此研究的主要目的在于探讨降维是否能够缓解Nk的偏度这一问题。“因为观察到的Nk的偏度与与本征维数强烈相关，本征维数对Nk到数据集的均值或到最接近簇的均值有着积极影响，这意味着在较高（本征）维度中，hubs变得越来越接近数据集或最接近簇的中心”[6]。

实验过程中采用的距离度量方法是闵可夫斯基距离（Minkowski distance），它是衡量数值点之间距离的一种非常常见的方法，假设数值点P和Q坐标如下：

那么，闵可夫斯基距离定义为：

该距离最常用的p值是2和1，前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。

为了探究在使用降维技术的情况下Nk的偏度和本征维数的相互作用，本文使用了来自加州大学尔湾分校（UCI）机器学习库[10]的数据集进行观测Nk（k=10）的分布。在表1中包含了以下信息：数据集的样本数（n，第2列）；数据样本的特征维数（d，第3列）；数据样本的类别数（cls，第4列）。

表1 真实数据集

图2描述了针对若干个真实数据集（musk，sonar，mfeat-fou等）通过降维方法获得的维数占原有数据集维数的百分比与之间的相互关系。数据之间距离的度量方法为Minkowski距离，其中p的取值分别为：2（Euclidean distance）。从左往右观察，对于大部分数据集而言利用PCA降维算法，保持相对恒定直到降维后留下特征的百分比较小时才会陡然下降。因此，当达到数据集的本征维数时若继续减小维数则会导致有价值的信息丢失。针对PCA方法对数据进行降维时，若降维后本征维数未发生明显变化，那么降维并不会对hubness这一现象有显著影响。

图2 特征维度与偏度的关系

3 实验结果

实验数据来源于加州大学尔湾分校（UCI）机器学习库。表2中第5列为真实数据集的偏度值，其中10代表k近邻数。从表中数据可以看出，对于大多数数据集的的分布发生了倾斜。虽然k的值是固定的，但是使用其它的k值也可得到类似的结果。采用轮廓系数（Silhouette Index）作为聚类结果的评测指标[7]，其计算公式如下所示：

其中，ai表示i向量到同一簇内其他点不相似程度的平均值，bi表示i向量到其他簇的平均不相似程度的最小值。可见轮廓系数的值总是介于[-1，1]，越趋近于1代表内聚度和分离度都相对较优。将所有点的轮廓系数求平均，就是该聚类结果总的轮廓系数。本文方法与KMEANS[9]、GHPKM[9]、Ker-KM[4]和Ker-KM[4]方法进行了比较，其中PH-KM为本文的聚类方法。实验结果如表2所示，下表中加粗的数据表示当前数据集的最优值。

表2 轮廓系数

对于每一个数据集而言，取KMEANS、GHPKM、Ker-KM以及Ker-GHPKM聚类算法中轮廓系数的最大值作为经典聚类算法的最优值，然后同本文的PHKM聚类算法进行比较。实验结果表明，相比之前的聚类算法，本文提出的PH-KM聚类算法在轮廓系数上平均提高了15%。从实验结果可以看出，在数据集缺乏hubness特性的情况下，GHPKM、Ker-GHPKM等hub聚类算法表现不佳，其性能接近于KMEANS算法；然而在数据集呈现出较高的hubness特性时，GHPKM、Ker-GHPKM等hub聚类算法的表现要优于KMEANS算法。同时，本文提出的PH-KM聚类算法无论数据集是否呈现出较高的hubness特性，均可以取得不错的聚类效果，相比之前的聚类算法适用范围更广，聚类性能更佳。

4 结语

在高维数据空间中，传统的聚类算法已变得不再适用。虽然hub聚类算法可以处理上述问题，但是它却忽略了高维数据中的冗余和噪声数据，从而导致聚类效果不佳。本文以Nk的偏度与本征维数强烈正相关为理论基础，通过构建数据集的KNN邻域矩阵，以偏度的变化率作为降维依据，最后再对降维后的数据集进行聚类。实验结果表明，无论数据集是否含有较高的hubness特性，本文提出的PH-KM聚类算法均可以取得不错的聚类效果，相比之前的聚类算法，轮廓系数平均提高了15%。

[1]Jiawei Han．数据挖掘概念与技术[C].机械工业出版社，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，Fayyad 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-），男，重庆人，博士，副教授，研究方向为数据挖掘、图像处理

郎江涛（1990-），男，山西人，硕士，研究方向为计算机应用技术

唐黄（1991-），男，重庆人，硕士，本科，研究方向为计算机应用技术

唐允恒（1992-），男，重庆人，硕士，本科，研究方向为计算机应用技术

2017-03-09

2017-04-06