异端审判器！一个泛用型文本聚类模型的实现（2）

上回，我们提出了一种只要输入一堆字符串，就能根据字符串的构造挑拣出“少数派”，以识别异常参数的构想。我们将它称作“异端审判”。

前文中我们已经定义好了一些必要概念，并写出了函数实现。我们的程序递进地量化了字符之间的差异、字符串之间的差异，最终得到了字符串集合之间的差异。有了这项指标，我们就能完成分拣工作。

在生活中，我们常有几排人一起合影的经历。有时是前排蹲下后排站立，有时是矮个子站在前排高个子位居后排。不妨假想一下，如果你就是那位摄影师，正指挥大家列队，你习惯于怎样安排队形呢？

通常情况下，你会直接要求站成大致均匀的两排，再逐个调整细节，直到整个队形看上去令人满意。

这为我们识别“异端”提供了灵感。

想象一位“主教”威立于尖塔的阳台，望着城楼下的人群，现在他要做的就是将人分成两类，一类大致可信，一类有些可疑，再逐个把后者中的信众移进前者，“异端”自然被剩下。

这篇文章中，我们就是要实现这样一件事。

从一刀切开始分类

我们先将每个输入都视作单独的一类，以启动整个流程。整个全集记作 C 。

# 初始化
# 输入一个列表，如['a','b','c']
# 输出一个把每个元素都封装为列表的列表，如[['a'],['b'],['c']]
def init(sample_list):
    C = []
    for x in sample_list:
        C.append([x])
    return C

基于此前定义的字符串集间距离（在文章中简称为类间距离），选择最接近的两类，合并它们。

这步操作听上去很简单，实际上确实也很简单，但我们会遇到一些麻烦：我们一直使用列表来简单表示集合这个数学概念，它们性质并不相同。集合的三个主要特性中，列表不满足无序性与互异性，因此需要一些额外的处理。

例如，找到最接近的两类，无论如何我们也需要计算出 n^2 个距离，这就不是一件轻松的事。我们将最小距离记作 d ——

def find_min(C):
    # 逻辑告诉我们无论怎样做都必须计算两两之间的全部距离，这里用一个二维列表来记录
    # 数学告诉我们 a->b 与 b->a 的距离是一样的，其实开销可以减小一半
    # 作者告诉大家由于我很懒，就不做这个优化了……
    scale = len(C)
    d = [[0 for i in range(scale)] for i in range(scale)]
    min_d = internal_classes(C[0], C[1])
    where_min_d = [0, 1]
    for i in range(scale):
        for j in range(scale):
            d[i][j] = internal_classes(C[i], C[j])
            if i != j and d[i][j] < min_d:
                min_d = d[i][j]
                where_min_d = [i, j]
    return where_min_d

找到了最小的 d 以后，就该合并它们了。在进行并运算时，我们就会遇到列表与集合的性质差异、逻辑与运算的表示差异等问题，我们重新定义运算函数来弥补这些偏差。

如果这部分让你有点眩晕，不要为此担心。你可以将它们都视作 dirty hack，记住我们只是在做一件简单的事情：将刚才已经找到的类间距离最小的两个集合，合并成一个。

# C:=C-Ci-Cj+CiUCj
# 输入全集列表C及其选出的两个子列表Ci、Cj，如C=[['a'],['b'],['c']]，Ci=['a'], Cj=['b']
# 需要注意的是，逻辑上，集合Ci与集合Cj是集合C的【元素】，而交并差都是【集合】之间的运算
# 输出合并Ci与Cj之后的全集列表，如[[['a'],['b']],['c']]
def merge(C, i, j):
    # 在数学上，集合[[1],[2]]与集合[[1,2]]的并集有三个元素，因为[1],[2],[1,2]都是完全不同的元素。但在这里的逻辑上，需要结果为[[1,2]]，所以另外定义了特殊的“交集”运算
    # 交集与差集的运算是针对集合的（如[[1]]）而非元素（如[1])，所以需要手动装进列表再传参。（其实已经特殊处理的交集运算无必要这样做，但为了逻辑一致遵守了统一的写法）
    C_u = special_union([C[i]], [C[j]])
    C_d = difference(difference(C, [C[i]]), [C[j]])
    C_n = C_d
    C_n.append(C_u)
    return C_n

我们将最接近的两类合并成一类了，而目标是“一刀切”，即把整个全集划分为大致均匀的两类。所以我们不断查找最接近的两类，将其合并，直到有某个集合的总量超过全集的一半。

# 查找规模最大的一个子列表
# 输入全集C，如[[['a'],['b']],['c']]
# 输出规模最大即集合内元素最多的列表的下标，如 0
def find_largest(C):
    s = [0] * len(C)
    max_s = len(C[0])
    where_max_s = 0
    for x in range(len(C)):
        s[x] = len(C[x])
        if s[x] > max_s:
            max_s = s[x]
            where_max_s = x
    return where_max_s

每个步骤都已经定义就绪，整个操作流程是这样的：

def layerClassification(sample_list):
    C = ini(sample_list)
    while True:
        where_min_d = find_min(C)
        i, j = where_min_d
        C = merge(C, i, j)
        where_max_s = find_largest(C)
        if count_elem(C[where_max_s]) > 0.5 * len(C):
            break
    CM = C[where_max_s]
    CN = difference(C, [CM])
    return flatten(CM), flatten(CN)

这段代码中提到了两个辅助函数，其中 count_elem() 用于递归遍历每个集合中实际包含的字符串个数（而非子元素个数），分类的最终结果可能出现复杂的多维列表，而我们只需要两个简单的一维列表用于表示两个集合，定义 flatten() 来展开嵌套。

你！到那边去！

经过了刚才的分类，现在我们有了两个集合。其中的一个包含了原本聚类性比较明显的元素，他们可能长相非常近似，剩下一半只是单纯被剩下了而已，风马牛齐聚一堂，看上去乱糟糟的。

接下来就是“微调”时间啦，我们要从那个泥沙俱下的集合中，把“信众”逐个移动到前面那个相对齐整的集合里，从而将“异端”孤立。

这件事的关键是何时停止：移到哪一步时，那个混乱的集合恰好只剩“异端”，而又没有“异端”错误地赦免呢？

好在我们的主教无需落子无悔，移错了就倒回去嘛。他甚至可以命人把所有结果都罗列出来，由他来判断哪一个方案是最好的。

那我们不妨先不考虑决策的事情，提供全部方案就好。

我们将分类方案记作 S ，一个分类方案由两个集合构成，即{C1, C2}，同样地，我们使用列表来表示。为了在不断移动的过程中，存储每一时刻的 C1 与 C2，而不作为引用跟随变化，我们需要使用深拷贝。

def note_solution(S, C1, C2, N):
    _C1 = copy.deepcopy(C1)
    _C2 = copy.deepcopy(C2)
    S.append([_C1, _C2])
    N = N + 1
    return S

基于此前定义的类间距离，我们能够选到 C2 中最接近 C1 的样本：

def select_min(C1, C2):
    min_x = C2[0]
    min_d = classesDistance(C1, min_x)
    for x in C2:
        temp = classesDistance(C1, x)
        if temp < min_d:
            min_d = temp
            min_x = x
    return min_x

把这个样本从 C2 中放进 C1：

def update(min_x, C1, C2):
    C1.append(min_x)
    C2.remove(min_x)
    return [C1, C2]

我们不断搬运元素，直到那个没有聚类性的 C2 被搬空。记录下这个过程中所有分类方案。除了全部分类方案 S 以外，我们同时维护另一个列表，记录被移动的元素，以便于撤回。由于这个列表里所有元素都是我们每一步选出的到 C1 距离最小元素，不妨就将这个列表称作 M ，整个过程如下：

def iterateClassification(C):
    N = 0
    S = []
    M = []
    C1 = C[0]
    C2 = C[1]
    while True:
        note_solution(S, C1, C2, N)
        min_x = select_min(C1, C2)
        M.append(min_x)
        update(min_x, C1, C2)
        if len(C2) == 0:
            break
    del(S[0])
    return S, M

到这里为止，我们反复运用上篇文章中定义的类间距离，做了一次粗选，又列出了所有微调生成的方案。最佳方案必然就是其中之一，留给我们大主教的，只剩一个优化问题。

让我们下回再见～