聚类算大经典论文之 ROCK: A Robust Clustering Algorithm for Categorical Attributes*

聚类算大经典论文之ROCK (RObust Clustering using linKs)*

属于凝聚型的层次聚类算法，直接翻译为“鲁棒的链接型聚类”

Introduction

聚类算法的两大类， partitional clustering and hierarchical clustering

#分区聚类：

先分成K的块，然后优化一个criterion function for metric spaces：

分层方法是起初开始令每个点都当做一个类，然后逐渐迭代合并。

Motivation

聚类算法中一个关键问题是计算两个点之间的相似性。传统计算方法，比如Jaccard距离，对数值数据表现尚可，但是对类别信息如果还像往常一样计算几何距离，无论怎么哪种计算方法都存在问题。

传统相似度计算的缺陷举例说明
对数值类型数据表现尚可，但对类别型有缺陷。

传统聚类算法缺陷举例：

例1：

（a）{1，2，3，5}，
（b）{2，3，4，5}，
（c）{1，4}，
（d）{6}
四个事务可以被看作具有布尔项（0/1）属性的点，这些属性对应于项目1， 2， 3，4，5和6。四个点因此成为
（1，1，1，0，1，0），
（0，1，1，1，1，0），
（1，0，0，1，0，0），
（0，0，0，0，0，1）。
欧氏距离测得最小距离为点a点b间为√2，合并得到新质心（0.5，1，1，0.5，1，0）。下一步第点c点d点合并，它们没有共同项，却被分配到一个簇，这显示是不合理的。

例2：

Solution

本算法针对这一问题，提出了Link的方法，在计算两个点的相似度时，不仅考虑到了两个点本身，还引入了全局信息。因此取得了很好效果。

链接， Link

链接 ：如果两个点具有共同邻居，则它们之间有链接。
邻居/近邻：如果两个样本点的 相似度 达到了 阀值，这两个样本点就是邻居。
这里阈值是提前指定的。
而相似度的计算，我们一般有两种选择：Jaccard系数，余弦相似度。
Jaccard 系数定义为A与B交集的大小与A与B并集的大小的比值，值越大，相似度越高。

余弦相似度，是通过计算两个向量的夹角余弦值来评估他们的相似度。
值越接近1，就说明夹角角度越接近0°，也就是两个向量越相似，就叫做余弦相似

细节补充：
Link计算方式与复杂度：
可以直接使用邻接表的方式，其复杂度是O(n3)

ROCK 聚类步骤：

初始状态时，每一个样本都是一个簇。在合并两个簇的时候，我们遵循的原则是，簇之间的链接数量最小，而簇内的链接数量最大。
首先我们想到的是，简单加总每个簇内的 link，最大化下面的公式：

但是这样遇到的问题是，不能避免把所有样本分到同一个簇内，这种情况下link值肯定是最大的。
于是，我们有了下面的目标函数：

其中，
Ci，表示第 i 个簇，
k，簇的个数，
ni，Ci 中样本点的数量

现在，我们的目标是最大化
如何最大化呢？ 下面 ROCK 聚类提供了一种方法，比较计算两个簇的Goodness Measure，合并最大的两个簇。
Goodness Measure 的 计算公式如下：

1、输入聚类个数 k 值和相似度阈值 θ
2、计算点与点之间的相似度，生成相似度矩阵
3、计算邻居矩阵 A
4、计算链接矩阵 L = A x A
5、计算 Goodness Measure，将相似性最高的两个对象合并。
回到第3步进行迭代更新，
直到形成k个聚类，或这聚类的数量不在发生变换。

总结

优点：
（1）ROCK算法适用于类别型数据，比如，关键字、比尔值、和枚举值等；
（2）ROCK算法核心思想是利用链接作为相似性的度量，而不是仅仅依赖于距离
缺点：
（1）相似度阀值需要预先指定，阀值对聚类质量影响很大，在对数据集没有充分了解的前提下很难给出合理的阀值；
（2）在ROCK算法中，相似度函数仅被用于最初邻居的判断上，只考虑相似与否，而未考虑相似程度，是算法对相似度阈值过于敏感；
（3）ROCK算法还要求用户事先选定聚类簇数 k

`