共计 3847 个字符，预计需要花费 10 分钟才能阅读完成。
上文链接：异端审判器！一个泛用型文本聚类模型的实现(1)
上回，我们提出了一种只要输入一堆字符串，就能根据字符串的构造挑拣出“少数派”，以识别异常参数的构想。我们将它称作“异端审判”。
前文中我们已经定义好了一些必要概念，并写出了函数实现。我们的程序递进地量化了字符之间的差异、字符串之间的差异，最终得到了字符串集合之间的差异。有了这项指标，我们就能完成分拣工作。
在生活中，我们常有几排人一起合影的经历。有时是前排蹲下后排站立，有时是矮个子站在前排高个子位居后排。不妨假想一下，如果你就是那位摄影师，正指挥大家列队，你习惯于怎样安排队形呢？
通常情况下，你会直接要求站成大致均匀的两排，再逐个调整细节，直到整个队形看上去令人满意。
这为我们识别“异端”提供了灵感。
想象一位“主教”威立于尖塔的阳台，望着城楼下的人群，现在他要做的就是将人分成两类，一类大致可信，一类有些可疑，再逐个把后者中的信众移进前者，“异端”自然被剩下。
这篇文章中，我们就是要实现这样一件事。
从一刀切开始分类
我们先将每个输入都视作单独的一类，以启动整个流程。整个全集记作 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 = classesDistanse(C[0], C[1])
where_min_d = [0, 1]
for i in range(scale):
for j in range(scale):
d[i][j] = classesDistanse(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 = init(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
到这里为止，我们反复运用上篇文章中定义的类间距离，做了一次粗选，又列出了所有微调生成的方案。最佳方案必然就是其中之一，留给我们大主教的，只剩一个优化问题。
让我们下回再见～
编者按：
本文未完待续，敬请期待后续推送。参考文献及整理后的示例代码将在完整文章末给出。
文 / YvesX 反正你也猜不出我是做什么的编 / 荧声
本文由创宇前端作者授权发布，版权属于作者，创宇前端出品。欢迎注明出处转载本文。文章链接：https://www.yvesx.com/archive…
想要订阅更多来自知道创宇开发一线的分享，请搜索关注我们的微信公众号：创宇前端（KnownsecFED）。欢迎留言讨论，我们会尽可能回复。
欢迎点赞、收藏、留言评论、转发分享和打赏支持我们。打赏将被完全转交给文章作者。
感谢您的阅读。
