提升文本聚类质量以避免偏差

### 提升文本聚类质量以避免偏差 #### 1. 软约束 k - 均值与归一化切割的结合 归一化切割算法是将聚类问题转化为图切割问题，目标是找到图的一个切割，使得归一化切割值最小。由于这是一个 NP 难题，需要对解的条件进行一定的松弛，以降低复杂度并使其在计算上可行。其最小化的结果是将数据点投影到 $R^k$ 空间，而不是直接得到聚类结果，还需要最后一步才能完成数据的最终聚类。Shi 和 Malik 提出在投影后的数据点上使用 k - 均值算法来完成这最后一步。 本文提出使用 Ares 等人提出的软约束 k - 均值算法代替批量 k - 均值算法，这样可以引入以绝对（Must 和 Cannot - Link）和非绝对（May 和 May - Not - Link）约束形式存在的领域知识。虽然这些约束是在初始文档上定义的，但初始文档与投影文档之间存在一一对应关系，因此可以将这些实例级约束应用到相应的投影文档上。 从软约束 k - 均值的角度来看，归一化切割起到了一种文档预处理的作用，将文档从所选的文档表示转换为基于归一化切割准则的 $R^k$ 表示。这种“预处理”有双重效果：不仅可以从使用归一化切割算法带来的聚类质量提升中受益，还可能增加成对约束的效果。因为与受约束文档接近的文档也会受到约束引起的目标变化的影响，相似的文档（通常具有相同的约束）会被聚集在一起，不相似的文档会被分开，从而避免了约束对不相关文档的不必要“干扰”。 在性能方面，这种组合方法的计算成本与归一化切割算法相同，因为软约束 k - 均值和批量 k - 均值的成本相同。整个算法中最昂贵的操作仍然是特征向量的计算，总成本取决于执行该计算的方法。如果使用标准算法，成本可以得到较好的控制。例如，使用 Lanczos 算法，时间复杂度为 $O(kN_{Lanczos}nnz(M))$，其中 $k$ 是所需的聚类数（即特征向量的数量），$N_{Lanczos}$ 是算法的迭代步数，$nnz(M)$ 是矩阵 $D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$ 的非零元素数量。 #### 2. 实验设计 ##### 2.1 实验方法 为了测试算法的实际性能，进行了避免偏差实验，采用了该领域论文的标准方法。使用的文本文档集合中的文档按照两种不同标准进行了分类。交替假设其中一种分类为已知分组，尝试避免该分组，并通过将聚类结果与已知分组（评估避免程度）和“未知”分组（衡量结果质量）进行比较来评估聚类过程的结果。 以 Ares 等人提出的原始软约束 k - 均值避免偏差方法为基线。复制了该论文中的实验条件，为已知分组中同一聚类的每对文档引入一个约束。对于基线和组合（NC + SCKM）方法，由于它们支持双向和单向约束，使用了双向约束。假设聚类数已知，将其设置为非避免分组的聚类数。由于聚类种子是从文档中随机选择的，且聚类结果很大程度上取决于初始种子的质量，因此需要多次重复聚类过程，并报告这些初始化的平均值。 需要初始设置的参数有：基线和基于归一化切割与软约束 k - 均值组合方法中的约束强度 $w$，以及基于约束归一化切割方法中负约束遵守的紧密度 $\beta_N$。实验发现，当光谱阶段文档投影的维度数大于所需聚类数时，聚类算法效果更好。通常，特征向量数量在 10 到 20 之间时性能最佳（所需聚类数在 2 到 5 之间）。经过初步测试，使用前 15 个特征向量来创建文档投影，这个值在所有集合中表现良好。 ##### 2.2 数据集 使用了两个数据集： - 数据集（i）：来自 WebKB 的大学数据集，收集了美国不同大学网站的网页，这些网页根据大学和主题（“课程”、“部门”、“教师”、“项目”、“员工”、“学生”和“其他”）进行了手动标记。实验数据集选取了康奈尔、德克萨斯、华盛顿和威斯康星大学中标记为“课程”、“教师”、“项目”、“员工”、“学生”的文档，共 1087 篇。 - 数据集（ii）：来自路透社 RCV - 1，这是一个包含约 810,000 篇新闻报道的大型文档集合。文档根据主题、地理区域和行业进行了手动标记。实验数据集选取了仅标记有一个主题和区域标签，且主题为“MCAT”或“GCAT”，区域为“英国”或“印度”的文档，共 1600 篇。 ##### 2.3 文档表示 与基线实验一样，使用互信息作为文档的原始表示（用于构建图 $G$），因为它比其他 tf · idf 方法表现更稳定。文档 $d$ 在包含 $m$ 个术语和 $d$ 篇文档的集合中的表示是一个向量： $mi(d) = [mi(d, t_1); mi(d, t_2)