基于ROCK算法的分类数据聚类分析系统

资 源 简 介

该项目完整实现了ROCK (RObust Clustering using linKs) 算法的核心逻辑，旨在解决分类数据（Categorical Data）和布尔数据的聚类问题。主要功能涵盖了算法的全过程：首先，根据输入的数据集和设定的相似度阈值（theta），计算数据点之间的Jaccard系数以确定邻居关系；其次，构建链接矩阵（Link Matrix），通过计算两个数据点共同邻居的数量来衡量其紧密程度，这是ROCK算法区别于传统基于距离算法的核心特征；再次，实现层次凝聚聚类策略，定义并计算簇合并的优度量度（Goodness Measure），该量度综合考虑了簇内链接与簇间链接的比例；最后，执行迭代合并过程，每次选择优度最高的两个簇进行合并，并高效更新剩余相关簇的链接数和优度值，直到达到预期的聚类中心数量。该算法特别在处理高维稀疏数据及具有噪声的数据集时表现出优异的鲁棒性。

详 情 说 明

ROCK聚类算法MATLAB实现

这是一个基于MATLAB开发的ROCK (RObust Clustering using linKs) 聚类算法完整实现项目。该算法专门针对分类数据（Categorical Data）和布尔型数据设计，通过引入“链接（Link）”的概念来衡量数据点之间的紧密程度，从而克服了传统基于距离的聚类算法在处理非度量数据时的局限性。

项目介绍

本项目在一个单一的脚本文件中完整复现了ROCK算法的核心逻辑。不同于K-Means等基于质心的算法，ROCK属于层次凝聚聚类算法。它利用数据点共同邻居的数量（Links）作为相似性的度量基础，通过最大化“优度量度（Goodness Measure）”来迭代合并簇。该实现包含了从数据生成、关联矩阵构建、链接计算、迭代聚类到最终结果可视化的全过程。

功能特性

• 全流程自动化：包含合成数据集生成、算法核心计算及结果展示，无需外部数据源即可运行演示。
• 鲁棒的相似性度量：使用Jaccard系数计算二值/布尔数据的相似度，适合处理稀疏的高维数据。
• 基于链接的邻域分析：通过计算共同邻居数（Link Matrix）来反映数据结构的全局连通性，有效处理噪声。
• 层次凝聚策略：实现了基于优度量度（Goodness Measure）的动态簇合并过程，自动更新簇间的链接关系。
• 高效矩阵运算：利用MATLAB的向量化操作和稀疏矩阵（Sparse Matrix）优化了大规模矩阵乘法，加速链接矩阵的构建。
• 降维可视化：集成了MDS（多维缩放）算法，将高维布尔数据的聚类结果投影到二维平面进行直观展示。

系统要求

• MATLAB R2016a 或更高版本
• Statistics and Machine Learning Toolbox（用于 cmdscale, pca, gscatter 等函数）

使用方法

1. 确保MATLAB环境已安装所需的工具箱。
2. 直接运行主程序脚本。
3. 程序将输出聚类过程的日志，包括相似度计算进度、邻居阈值设定、每次合并的优度值以及最终的簇统计信息。
4. 运行结束后，会弹出一个图形窗口，对比显示“真实标签”与“ROCK聚类结果”。

实现细节与算法逻辑

本项目代码通过以下几个关键步骤实现了ROCK算法：

1. 数据合成与参数配置

程序首先生成一个模拟的布尔型数据集（150样本 × 30特征），数据包含3个潜在的簇。每个簇在特定的特征子集上具有较高的激活概率，同时加入了随机噪声以测试算法的鲁棒性。

• 目标簇数：预设为3。
• 相似度阈值 (theta)：预设为0.55，用于判定两个点是否互为邻居。

2. 相似度与邻居矩阵构建

• 利用Jaccard系数公式计算所有样本对之间的相似度。
• 邻居定义：若两个样本的相似度大于或等于阈值 theta，则在邻接矩阵中标记为1（互为邻居）。
• 自我包含：为了后续链接计算的正确性，代码显式地将每个样本视为自己的邻居（对角线置1）。

3. 链接矩阵 (Link Matrix) 计算

• 核心逻辑：链接数定义为两个数据点共同邻居的数量。
• 实现方式：通过邻接矩阵与自身的矩阵乘法（Adjacency × Adjacency）直接得到链接矩阵。为了提高内存效率和计算速度，此处使用了稀疏矩阵转换。

4. 优度量度 (Goodness Measure) 初始化

• 初始化阶段，每个数据点被视为一个独立的簇。
• 计算用于优度公式的指数系数，该系数依赖于阈值 theta。
• 初始化优度矩阵，仅计算存在链接关系的簇对之间的优度值，并将结果存储在上三角矩阵中以节省资源。

5. 层次迭代合并

程序进入主循环，持续合并簇直到达到目标簇数：

1. 寻找最佳合并对：在优度矩阵中检索具有最大优度值的两个簇（u, v）。
2. 异常处理：若最大优度值无效（如无连接），则提前终止循环。
3. 合并更新：将簇v并入簇u，更新簇内的样本索引列表和样本总数。
4. 动态更新链接与优度：

* 计算新合并的簇与所有剩余活跃簇之间的总链接数（原簇u的链接 + 原簇v的链接）。 * 基于更新后的链接数，重新计算相关簇对的优度值。 * 将已合并的簇v标记为非活跃状态，并将相关的旧优度值置为负无穷。

6. 结果可视化

代码实现了将高维Jaccard距离投影到二维空间的功能：

• 距离矩阵：由 1 - Jaccard相似度 得到。
• 降维策略：优先尝试使用 MDS (多维缩放) 进行投影。如果因距离矩阵非欧氏导致MDS失败，代码包含 try-catch 块自动回退到 PCA (主成分分析) 进行近似投影。
• 绘图：在同一窗口中绘制两幅子图，分别展示原始数据的真实分类和算法计算出的聚类结果，并通过颜色区分不同的簇。

关键算法函数说明

Jaccard 相似度计算

该模块接收逻辑矩阵作为输入，通过矩阵乘法高效计算交集（Intersection），通过行求和计算并集（Union），最终得出两两之间的Jaccard系数矩阵。逻辑中包含对除零异常（全零行）的处理。

Goodness 优度计算

实现了ROCK算法特有的优度估算公式。该度量标准化了簇之间的链接数，通过引入期望链接数的概念（由簇的大小和幂系数决定），来防止算法偏向于合并大簇或过度分散。公式分母部分严格遵循计算逻辑，并包含防止分母非正的边界检查。