PROCLUS算法

PROCLUS是由Aggarwal等人在1999年提出的一种子空间聚类算法。原文是《Fast Algorithms for Projected Clustering》，在ACM数据库可以进行下载。

算法总体介绍

PROCLUS是基于投影的子空间聚类算法，搜索策略为自顶向下。算法基于中心点思想，适合球形簇数据集，采用曼哈顿距离度量对象的相似性。

算法一共分为以下三个阶段：

输入：数据集合 $D$ ，簇个数 $K$ ，常数 $A$ ，常数 $B$
输出：中心点集 $MC$

从数据集中随机选择 $A*K$ （ $A$ 是常数）个数据构成初始中心点超集 $MC'$ ；
使用贪心算法从 $MC'$ 中选择大小为 $B*K$ （ $B$ 为常数，且 $B<A$ ）的中心点集 $MC$ ；
2.1 初始化 $MC$ 为空集
2.2 从 $MC'$ 中随机选择一个样本 $m$ 加入 $MC$ （同时将 $m$ 从 $MC’$ 中移除）
2.3 计算 $MC'$ 中每个点与 $MC$ 中离该点最近的点的距离 $dis$ ，选择 $dis$ 最大的点 $n$ ，将 $n$ 加入 $MC$ 中（同时将 $n$ 从 $MC’$ 中移除）
2.4 重复2.3直到 $MC$ 中样本点数为 $B*K$

输入：数据集 $D$ (大小为 $N$ )，中心点集 $MC$ ，簇平均维度 $L$ ，簇个数 $K$
输出：最终的中心点集 $M$ ， $MC$ 中每个中心点对应的维度

从 $MC$ 中选择一个样本 $i$
计算 $MC$ 中其他样本点与m的最小距离 $i_{mindist}$ （曼哈顿距离）
计算数据集中i局部近邻点集合 $i_{neighbor}$ （数据集 $D$ 中离 $i$ 的曼哈顿距离小于 $i_{mindist}$ 的样本点即为i的局部近邻点）
计算 $i_{neighbor}$ 与 $i$ 在每个特征维度的平均距离 $X_{ij}$ （i表示中心点， $j$ 表示对应维度），计算所有维度维度均值 $Y_i$
计算Xij的标准差 $σ_i=\sqrt {\frac{\sum_{j=1}^{d} {(X_{ij}-Y_i)}^2}{d-1}}$
对于每个特征维度计算 $Z_{ij}=\frac{X_{ij}-Y_i}{σ_i}$ ,对 $Z_{ij}$ 进行排序，选取 $Z_{ij}$ 最小的 $K*L$ (最小有两维特征)个特征对应的维度,作为候选中心点 $m$ 的子空间
重复1~6，为 $MC$ 中所有中心点找到对应子空间
从 $MC$ 中选择 $K$ 个中心点，通过计算数据集中其他样本点与中心点在中心点对应的子空间的曼哈顿截断距离（Manhattan segmental distance），进行样本点的分配，使用MC中其他中心点替换掉 $M_{bad}$ （在聚类过长中分配到的数据点个数小于 $\frac{N}{K}*C$ ，C是一个常数，一般设为0.1）中心点

曼哈顿截断距离：
$d_D(x_1,x_2)=\frac{\sum_{i\in{D}}|X_{1,i}-X_{2,i}|}{|D|}$ ( $D$ 表示中心点对应的子空间)

输入：最优的中心点集M，迭代阶段最后得到的簇分配结果 $\lbrace C_i,C_2....C_k\rbrace$
输出：聚类结果

[1]Aggarwal C C , Wolf J L , Yu P S , et al. Fast Algorithms for Projected Clustering[J]. Sigmod, 1999, 28(2):61-72.

更多精彩内容