ROCK 聚类算法

ROCK 聚类算法

ROCK (RObust Clustering using linKs) 聚类算法 是一种鲁棒的用于分类属性的聚类算法。该算法属于凝聚型的层次聚类算法。之所以鲁棒是因为在确认两对象（样本点/簇）之间的关系时考虑了他们共同的邻居（相似样本点）的数量，在算法中被叫做链接（Link）的概念。而一些聚类算法只关注对象之间的相似度。

ROCK 算法中用到的四个关键概念

1.邻居（Neighbors）：如果两个样本点的相似度达到了阈值（θ），这两个样本点就是邻居。阈值（θ）有用户指定，相似度也是通过用户指定的相似度函数计算。常用的分类属性的相似度计算方法有：Jaccard 系数，余弦相似度。

2.链接（Links）：两个对象的共同邻居数量

3.目标函数（Criterion Function）：最大化下面目标函数以获得最优的聚类结果（最终簇之间的链接总数最小，而簇内的链接总数最大）。Ci：第i个簇，k:簇的个数，ni:Ci的大小（样本点的数量）。一般可使用f (θ) = (1-θ)/(1+θ). f(θ)一般具有以下性质：Ci中的每个样本点在Ci中有nif(θ)个邻居。

4. 相似性的度量（Goodness Measure）：使用该公式计算所有对象的两两相似度，将相似性最高的两个对象合并。通过该相似性度量不断的凝聚对象至k个簇，最终计算上面目标函数值必然是最大的。

link[Ci,Cj]=

大概算法思路：

输入：需要聚类的个数-k，和相似度阈值-θ

算法：

开始每个点都是单独的聚类，根据计算点与点间的相似度，生成相似度矩阵。

根据相似度矩阵和相似度阈值-θ，计算邻居矩阵-A。如果两点相似度>=θ,取值1（邻居），否则取值0.

计算链接矩阵-L=A x A

计算相似性的度量（Goodness Measure），将相似性最高的两个对象合并。回到第2步进行迭代直到形成k个聚类或聚类的数量不在发生变换。

输出：

簇和异常值（不一定存在）

伪代码：

:= compute links(S)

2. for each s 2 S do

3. q[s] := build local heap(link; s)

4. Q := build global heap(S; q)

5. while size(Q) > k do {

6. u := extract max(Q)

7. v := max(q[u])

8. delete(Q; v)

9. w := merge(u; v)

10. for each x 2 q[u] [ q[v] do {

11. link[x;w] := link[x; u] + link[x; v]

12. delete(q[x]; u); delete(q[x]; v)

13. insert(q[x];w; g(x;w)); insert(q[w]; x; g(x;w))

14. update(Q; x; q[x])

15. }

16. insert(Q;w; q[w])

17. deallocate(q[u]); deallocate(q[v])

18. }

end

1. Compute nbrlist[i] for every point i in S

2. Set link[i; j] to be zero for all i; j

3. for i := 1 to n do{

4. N := nbrlist[i]

5. for j := 1 to jNj 1 do

6. for l := j + 1 to jNj do

7. link[N[j];N[l]] := link[N[j];N[l]] + 1

8.}

end