Newton毕设：Rock聚类算法详解及实现

本文档主要介绍了Rock聚类算法的实现，这是一种由Sudipno Guha等人在1999年提出的针对分类属性数据的高效聚类算法。Rock算法的核心在于利用公共近邻数（链接数）来衡量数据点之间的相关性，这与传统的基于距离的度量方式有所不同。算法主要包括两个主要部分：预处理计算公共点数量和Brock算法主体。 预处理阶段（compute_links(S)）的主要任务是计算每个数据点与其邻居之间的链接数。通过遍历数据集S，维护一个inlist数组记录每个点的邻节点集合，并初始化所有链接值为0。接着，对于每个点i，找出其邻节点集合N，然后计算N中任意两个节点之间的链接数，并累加到对应的链接表link中。 Brock算法主体（cluster(S,k)）则负责实际的聚类过程。首先调用预处理函数得到链接表link。接下来，创建两个队列：全局队列Q用于存储当前未分配的聚类中心，以及局部堆q，用于维护每个数据点的最接近聚类中心。在while循环中，直到队列大小大于k，算法执行以下操作： 1. 从全局队列中取出一个未分配的聚类中心u，并找到其在局部堆中的最大邻节点v。 2. 更新链接表，将u和v的链接数合并，并从局部堆中移除v。 3. 合并u和v，形成新的聚类中心w，更新链接表，并在局部堆中相应地调整元素。 4. 对于u和v的所有邻节点，更新它们与w的关系，并可能调整它们在局部堆中的位置。 5. 将新聚类中心w添加回全局队列，并清理已使用的局部堆。 值得注意的是，文中提到的"build_local_heap"、"build_global_heap"、"extract_max"、"insert"等函数分别对应堆数据结构的操作，例如构建堆、提取最大元素、插入和删除元素等，这些都是算法实现中的关键步骤。算法通过优先处理与当前聚类中心关系密切的数据点，逐步合并聚类，直至达到目标聚类数量k。 整个Rock算法的优势在于它能够利用全局信息来评估数据点之间的相关性，适用于属性数据的复杂聚类场景。如果在阅读或实现过程中遇到任何问题，可以参考作者提供的代码示例，并在讨论中交流优化和理解策略。