一种聚类程序的纲要及其输出的使用

汉斯·瓦尔盖塞·马修斯（Hans Varghese Mathews）¶

程序的预期用途

这里所述程序的用途，是将在某个适当短暂的时期内编辑过某一维基百科页面的各位编辑者，聚类为不同群体或“派别”；各群体彼此之间以某种可识别的兴趣区分，而这种兴趣可以被视为与他们对该页面本身的兴趣并列或相伴。我们把后者称为“被研究的页面”；算法处理的是这些编辑者在同一时期也编辑过的其他维基百科页面的记录。按照目前的实现方式，该算法在一群确实具有不同兴趣的编辑者于相对短暂的时期内频繁编辑时，效果最佳；粗略估计，这个时期应为1至3个月——不过，兴趣种类也不能多到使他们无法结成派别。¶

输入

假设 E₁、E₂、……、Eᵢ、……、Eₙ 是被研究页面的编辑者，令 P₁、P₂、……、Pⱼ、……、Pₘ 为所考察时期内，某位编辑者 Eᵢ 编辑过的其他页面。算法的输入是一个二元矩阵 D：每位编辑者对应一行，每个页面对应一列；若 Eᵢ 编辑过 Pⱼ，则矩阵的第 ij 个元素 Dᵢⱼ 为1，否则为0。¶

降低噪声

对于 D 的任意一行 Rᵢ，假设 Cⱼ₁、Cⱼ₂、……、Cⱼₖ 是第 i 个元素为1的那些列；那么 Pⱼ₁、Pⱼ₂、……、Pⱼₖ 自然就是 Eᵢ 编辑过的其他页面。现在将 D 的每一列看作一个向量，并构造一个 k×k 对称矩阵 A：对集合 {1, 2, …, k} 中的每个指标 r 和指标 s，将第 rs 个元素 Aᵣₛ 与第 sr 个元素 Aₛᵣ 都设为 Cⱼᵣ 与 Cⱼₛ 之间夹角的余弦。设 λ 为 A 的最大特征值，它将大于或等于1；我们预期，对于大多数行，λ 会显著大于 A 中那些小于1的特征值的平均值。但如果并非如此，或者 k＝1，我们便把该行对应的编辑者认定为“单例”。假设 n 位编辑者中有 q 位被认定为单例。现在，每个页面 Pⱼ 的 nⱼ 位编辑者中都会有一定数量 qⱼ 的单例（也可能为零）；如果 qⱼ·n 显著大于 q·nⱼ，我们便将 Pⱼ 认定为“奇异页面”。单例编辑者对应的行，以及奇异页面对应的列，都被视为噪声，在继续下一步之前从数据 D 中移除。¶

生成编辑者的分组方案

我们所谓一个集合的“分组方案”，是指将它划分为若干非空子集；每个子集都是该方案中的一个群组。¶

假设移除噪声之后，还剩下 E₁、E₂、……、E_N这 N 位编辑者，以及 P₁、P₂、……、P_M这 M 个页面；他们的编辑记录汇集成一个 N×M 矩阵，仍称之为 D。可以用多种方式，从缩减后的数据矩阵 D 的第 r 行 Rᵣ 和第 s 行 Rₛ，取得编辑者 Eᵣ 与 Eₛ 之间的相似度量。每种方法都会产生一个 n×n 对称相似度矩阵 Σ，其第 rs 个元素 Σᵣₛ——当然也包括第 sr 个元素 Σₛᵣ——就是该方法所评估的 Eᵣ 与 Eₛ 之间的相似程度。^[1]¶

现在可以对 Σ 应用各种层次聚类方法，得到编辑者的分组方案。理想情况下，每种聚类方法应产生一个分组方案；但有些方法可能根本无法产生令人满意的分组，而且视相似度量而定，同一种方法也很可能产生不止一个方案。在我们的实验中，给定一种相似度量和层次聚类方法后，某次程序运行所建议的分解中，并不常见某一种毫无疑问优于所有其他分解的情形。^[2] 接下来，算法使用不同的相似度量和不同的聚类方法，生成大量彼此不同的分组方案，然后从中选出少数有用的方案。¶

用页面标记分组方案中的群组

假设 Γ 是我们的编辑者的一种分组方案，将他们划分为 G₀、G₁、……、G_K，其规模分别为 N₀、N₁、……、N_K，且 N₀＋N₁＋…＋N_K＝N。虽然我们已经移除了单例编辑者和奇异记录，某种相似度量配合某种聚类方法，仍可能产生含有成员过少之零散小簇的聚类结果。我们从这种聚类结果取得分组方案的做法是：将规模足够大的簇保留为群组——称它们为“同质群组”——而把很小的零散簇合并为群组 G₀。¶

对于页面 P，以及 {1, 2, …, K} 中的每个指标 k，假设群组 Gₖ 的 Nₖ 位成员中，有 Qₖ 位编辑过 P；设 Q(Γ)＝Q₁＋Q₂＋…＋Q_K，N(Γ)＝N₁＋N₂＋…＋N_K。如果 P 的编辑活动是随机的，我们可以预期，Gₖ 中大约有 Wₖ＝Q(Γ)·Nₖ／N(Γ) 位成员编辑过该页面。若通常的卡方检验，以观察值和期望值组成的配对集合 {(Q₁, W₁); (Q₂, W₂); …; (Qₖ, Wₖ)} 进行检验时，检测到出乎预期的编辑者组合，那么在 Qₖ·N(Γ) 显著大于 Q(Γ)·Nₖ 的所有情形中，我们就用页面 P 标记 Γ 中的 Gₖ。^[3]¶

利用群组标记来描述分组方案

对分组方案中按照上述方法以页面标记的一个同质群组而言，会有一个或多个页面最受其成员编辑。用编辑了最常被编辑页面的成员比例 φ，来度量该群组的聚焦程度。异质的 G₀ 以及所有未被标记的群组，其聚焦度设为0；整个分组方案的聚焦度，则是这些比例 φ 依各自群组的相对规模适当加权后的总和。¶

首先，令 G₁、G₂、……、G_q 为分组方案 Γ 内被标记的群组，P₁、P₂、……、P_r 为标记它们的页面。构造一个 q×r 矩阵 C：对于 {1, 2, …, q} 中的每个 t，以及 {1, 2, …, r} 中的每个 s，将第 ts 个元素 Cₜₛ 设为 Gₜ 中编辑过 Pₛ 的成员比例。然后构造一个 q×q 对称矩阵 S，将第 ij 个元素和第 ji 个元素都设为 C 的第 i 行与第 j 行所构成向量之间夹角的余弦。这个量应该可以相当合用地度量群组 Gᵢ 与 Gⱼ 之间兴趣的重叠程度。将 S 的最大正特征值除以全部正特征值的总和，应当得到区间 [0,1] 内的一个数 θ；它大致度量 Γ 中被标记群组的兴趣，整体而言有多大程度相互重叠或混合。反之，1－θ 可以被视为这些兴趣相互分离程度的度量。¶

将分组方案归束

作为这项操作的预备步骤，我们移除所有这样的分组方案：与总体比例相比，未被标记群组中的编辑者比例异常高。为了将分组方案本身归为互不相交的集合，我们必须以某种方式评估任意一对分组方案 Γ 和 Λ 之间的相似性或一致性。我们使用的度量，是互信息 I(Γ, Λ) 除以通常的各自熵度量之乘积的平方根 [H(Γ)·H(Λ)]<super>1/2</super>。^[4]¶

令 Γ₁、Γ₂、……、Γν 为我们拥有的全部分组方案；这些信息相似度将得到一个 ν×ν 对称矩阵。接着，通常的因子分析程序会给出彼此不同的分组方案束，其数量与因子数量一样多；然后，把分组方案视作“观察变量”，各自与识别方案中“潜在”束的“因子”具有不同相关性，我们利用经过适当旋转的载荷矩阵，选取构成一个束的分组方案。¶

选择有用的分组方案

我们以如下方式，从每个不同的方案束中最多选择三个分组方案。在每个束内部，将分组方案分成三个子集：一类的组成群组之间兴趣异常混合，另一类的兴趣异常分离——如果存在可如此看待的方案的话——第三类则包括剩下的方案，其中的兴趣既没有异常共享，也没有异常分离。我们预期，这种方式能够覆盖实际可能性的范围。然后，从每个子集中挑出聚焦度最高的分组方案。因此，如果有 J 个束，就会选出最多 3·J 个更可能有用的分组方案。^[5]¶

使用输出

在一个分组方案内，用来标记某个群组的页面，应当指出把它与该方案其他群组区分开来的相伴兴趣。尽管技术上并非不可能，同一批页面标记同一方案中不同群组的可能性，却极小。可以使用把标记页面与群组配对的表格，单独考察每个被选中的分组方案：表中每个单元格将显示，哪个群组中有多大比例的成员编辑过哪个页面。也可以把所有选中的分组方案，与全部标记页面一起考察：表中每个标记页面占一行，每个分组方案占一列；特定方案与特定页面相交的单元格，此时将显示该方案中哪些群组被这个页面标记，以及每个被标记群组中有多大比例的成员编辑过该页面。¶

浏览这张将标记与分组方案汇集起来的表格——如前所述，后者数量应少到便于处理——一个对被研究页面的主题具有先验知识的人，应当能够从选定方案中挑出一两个，认为它们比其余方案更合理。而最终选定的一个或多个方案中，构成群组的页面标记之间的对照，应揭示其编辑者带给被研究页面的不同兴趣。如果最后找到的群组标记，分离程度明显高于混合程度，我们大可猜测：发挥作用的各种兴趣并不相互冲突。反之，如果这些标记的混合程度远高于分离程度，那么很可能有相互冲突的兴趣在起作用；但只有检查被研究页面上的实际编辑，才能判断这种可能性。¶

因此，我们的聚类程序所产生的输出，应该有助于考察维基百科页面可能具有的独特话语史。可以设想，维基百科页面常常会表现出某些话语特征，而这些特征特属于其持续增补和修订的过程。通过指出相互冲突或互补的兴趣，并指明可能在哪里发现它们发挥作用，我们的程序应能为调查提供方向，帮助汇集证据，使之成为撰写这种历史所需推断与解释的基础。例如，当某个页面的主题或内容容纳着彼此不相容的基础前提时，这样的历史应该尤其富于事件。^[6]¶

技术考虑与注意事项

现在应该很清楚：上述算法是一种服务于定性理解的定量程序——其输出当然不能替代定性理解。考虑到评估聚类对数据“拟合”得如何时伴随的不确定性，这似乎再恰当不过。为某个维基百科页面建构话语史，可能需要对不同的频繁编辑阶段多次运行算法，并在其间检查审慎挑选的该页面过往版本。不过，尽管人对记录的考察应当能够纠正机器的严重错误，列出程序设计中的某些概括性选择，以及可以改进的地方，仍不失为有益之举。¶

关于输入：最简便的做法，是考虑被研究页面的编辑者所做的所有旁支编辑，而不只考虑实质性编辑；原因很简单，似乎没有高效的机器流程能把后者与其余编辑区分开来。于是，降低噪声就势在必行；我们相信，这里使用的方式足以满足输出的预定用途，尽管单例的识别相当粗略。对于我们的二元数据，既然并无“自然”的相似度量，看来最好还是使用不同的相似度量与聚类程序，生成许多分组方案。用页面标记群组采用的是标准做法；我们也注明通常的警告：标准“期望值对观察值”统计量的分布，只是近似卡方分布。赋予编辑者分组方案的聚焦、混合和分离等属性，似乎是自然的；但度量它们的概括性数字，同样是以略显粗糙的方式取得的。关于如何将分组方案归束：对信息相似度矩阵进行因子分析，看来是决定“潜在”束数量的一种良好办法；而通常的方差最大化法（varimax），看来是把分组方案分配到各束时合适的旋转程序。不过，在衡量分组方案之间的相似性时，或许应当适当考虑群组的标记。聚焦度似乎是分组方案最有用的属性；而既然没有理由预期有用的方案必然是混合的，或者必然是分离的，那么最好的做法似乎是先把每个束划分为异常混合、异常分离以及两者皆非的子集，再从中选择聚焦的方案。^[7]¶

最后，我们指出：一个页面的编辑者中，相当大比例属于我们所谓“单例”，并非不可能。在这种情况下，就必须设法查明这些个体的主要兴趣——他们可能十分了解彼此，也可能并不了解——以考察其活动如何塑造了该页面已经形成的话语史。¶

译注

注释