Mining Projected Clusters in High-Dimensional Spaces
Mining Projected Clusters in High-Dimensional Spaces
复制标题
DOI：
10.1109/tkde.2008.162
复制
发表时间：
2009-04
影响因子：
8.9
通讯作者：
M. Bouguessa;Shengrui Wang
中科院分区：
文献类型：
--
作者：
M. Bouguessa;Shengrui Wang
由于点的固有稀疏性，聚类高维数据一直是一个主要的挑战。大多数现有的聚类算法变得非常低效，如果所需的相似性度量计算在全维空间中的数据点之间。为了解决这个问题，已经提出了一些投影聚类算法。然而，当簇隐藏在维数很低的子空间中时，它们中的大多数遇到困难。这些挑战促使我们努力提出一个强大的分区距离为基础的投影聚类算法。该算法由三个阶段组成。第一阶段通过检测密集和稀疏区域及其在每个属性中的位置来执行属性相关性分析。从第一阶段的结果开始，第二阶段的目标是消除离群值，而第三阶段的目标是发现不同子空间中的聚类。聚类过程基于k-means算法，距离的计算仅限于对象值密集的属性子集。我们的算法能够检测嵌入在高维空间中的低维投影簇，并避免了在全维空间中的距离计算。我们的建议的适用性已被证明通过使用合成和真实的数据集的实证研究。
Clustering high-dimensional data has been a major challenge due to the inherent sparsity of the points. Most existing clustering algorithms become substantially inefficient if the required similarity measure is computed between data points in the full-dimensional space. To address this problem, a number of projected clustering algorithms have been proposed. However, most of them encounter difficulties when clusters hide in subspaces with very low dimensionality. These challenges motivate our effort to propose a robust partitional distance-based projected clustering algorithm. The algorithm consists of three phases. The first phase performs attribute relevance analysis by detecting dense and sparse regions and their location in each attribute. Starting from the results of the first phase, the goal of the second phase is to eliminate outliers, while the third phase aims to discover clusters in different subspaces. The clustering process is based on the k-means algorithm, with the computation of distance restricted to subsets of attributes where object values are dense. Our algorithm is capable of detecting projected clusters of low dimensionality embedded in a high-dimensional space and avoids the computation of the distance in the full-dimensional space. The suitability of our proposal has been demonstrated through an empirical study using synthetic and real datasets.