什么是ROCK？

ROCK代表使用链接的鲁棒聚类。这是一种层次聚类算法，它分析链接的概念（两个对象之间共同邻居的数量）来处理具有类别属性的数据。它表明，在对类别信息进行聚类时，这种距离数据无法产生高质量的聚类。

此外，大多数聚类算法在聚类时只创建点之间的相似性，即在每一步中，将组合成单个聚类的点。“局部”方法容易出现错误。例如，两个不同的聚类可以有一些接近的点或异常值；因此，依赖点之间的相似性来做出聚类决策可能会导致将这两个聚类组合在一起。

ROCK通过处理单个点对的邻域来采用更全局的聚类方法。如果两个相似的点也具有相同的邻域，则这两个点很可能属于相同的聚类，因此可以组合在一起。

如果sim(p_i, p_j) ≥ θ，则存在两点p_i和p_j是邻居，其中sim是相似性函数，θ是用户指定的阈值。可以选择sim作为距离度量，甚至是非度量，只要将其标准化，使其值介于0和1之间，较高的值表示点越相似。

p_i和p_j之间的连接数表示为p_i和p_j之间共同邻居的数量。如果两点之间的链接数很高，则它们更可能属于相同的聚类。通过处理个体点群之间关系中的相邻数据点，ROCK比仅针对点相似性的标准聚类方法更强大。

包含类别属性的数据实例是市场篮子信息。此类数据包括一个事务数据库，其中每个事务是一组项目。事务被视为具有布尔属性的数据，每个属性对应于一个项目，例如面包或奶酪。

在事务数据中，如果事务包含该项目，则对应于该项目的属性为真；否则为假。可以用相同的方式管理几个具有类别属性的数据集。ROCK中两点或事务T_i和T_j之间的邻居和链接的概念用Jaccard系数表示为

$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$

ROCK首先利用相似性阈值和共享邻居的方法，从给定的数据相似性矩阵生成稀疏图。它可以在稀疏图上实现凝聚层次聚类。可以使用一种优度量来计算聚类。可以使用随机抽样来扩展到大型数据集。

ROCK的最坏情况时间复杂度为O(n² + nm_mm_a + n²log_n)，其中m_m和m_a分别表示最大和平均邻居数，n是对象的个数。

吉尼

更新于：2022年2月16日

4K+ 次查看

开启您的职业生涯

完成课程获得认证

开始