Part 1

如果给你一大堆用户输入，里面有大量的中文地名，像是“北京”、“成都”、“东莞”，不幸的是，其中也混有一些罗马地名，比如 “Singapore”、“New York”、“Tokyo”。你的任务是将它们分开，你会如何去做？

当然，有很多方法可以轻易做到。

如果是一堆 “good”、“fine”、“not bad”、“amazing”、"nice" 的简短反馈里混有 “Fallout 4 is the epitemy of everything wrong with modern gaming, it has a total of 2 compelling quests, its gameplay is worse then the rest, and to top it off they added microtransactions to it. it is the worst of the fallout series.” 这样的长篇抱怨呢？

你可能会想，这不更简单了嘛，检测字符串长度甚至标点符号数目就行呀。

如果是一堆 “12345678”、“5201314”、“password”里混有“password' and (select count(*) from data)>0 and 'a'='a”、“>"'><script>alert('XSS')</script>” 呢？

或许你已经不耐烦了：这点安全素养还是有的！检测关键字和特殊符号呀！

你已经不打算让我再“如果”下去了：没有什么是一段正则表达式搞不定的，如果有，那就该再学一次。

好，但是现在，我们需要的是，用同一个模型实现上述所有场景——当字符串有长有短，它要将长度异常的字符串分开。当有常规字符串和包含特殊符号的字符串，它能把特殊的那些拎出来。当字符串混有不同的语言，它能进行“净化”。甚至，还有各种不在意料之中的情形。

这段代码就像是在宗教战争中审判异端，无论是中出了一个叛徒还是干脆分裂成了两类，它总是能根据字符串的长相，把少数派给抓出来。

如果你恰好做过一些事，例如探索深度学习对网络安全的应用，相信你看着数据集，能很快想到这个“异端审判器”的实用价值。

让我们默契地眨眨眼。在后文里，我们会实现这样一个玩具。

主教的自我修养：看脸

北京与成都之间相距再远，也可以用欧式距离轻松度量。但 “Beijing” 与 “Chengdu” 之间的距离呢？

我们需要看脸，根据字符串“外貌”的特征，去定义和量化这样一种差异。

不难发现，字符串之间的距离至少应该包括如下组分：

• 字符串长度差异（如 cat 与miaomiaomiaomiaomiao）
• 字符集差异（如 123 与 abc）
• 字符序列差异（如 上海自来水 与 水来自海上）

长度差异

这有什么好说的……长度为5的字符串显然比长度为3的字符串多出一个2……

在此略过。

def strLengthDiffer(str1, str2):
    return abs(len(str1) - len(str2))

字符集差异

字符集的差异是为了刻画不同字符串在字符选择上的差异，我们应该对差异较大的字符串——特别是出现了不同类别的字符时——进行距离上的惩罚。

为了实现这个目标，首先要定义字符间的距离。这里，我们把相同字符间距离定义为 0, 同类字符（如a与b）间距离定义为 1，不同类字符间距离定义为 10。

字符分类可以为小写字母、大写字母、数字和其他，当然读者也可以根据自己的实际用途进行分类，把系统需要敏感识别的差异分为不同的两类。

有了字符间距离，我们定义字符 A(1) 与字符集 B 的距离为该 A(1) 到 B 中每一个字符的距离的最小值。

在上述基础上，我们进一步定义字符集 A 到字符集 B 间的距离为：A 中每一个字符到 B 的距离的算术和。

显然：

• 字符距离(a, b) = 字符距离(b, a)
• 字符到字符集距离(a, B) = 字符集到字符距离(B, a)
• 字符集间距离(A, B) = 字符集间距离(B, A)

由此，我们对字符集间距离完成了符合认知的定义。

def charSetDiffer(s1, s2):
    # 由于笔者使用的代码版本在这里有更复杂的逻辑，就不提供代码细节了
    # 已经讲得这么明确了，写写看吧
    return s

字符序列差异

对于开发者而言，用户输入是 alert("test") 还是 aeelrstt""()，显然有着完全不同的含义。后面这种意味不明的字符串根本不会让人多看一眼，而前者如果被用户执行成功，那么他后续多半会再搞些别的破坏，非常邪恶。

这个故事告诉我们，字符序列的差异不容忽视。

在这里，我们使用 N-Gram 语言模型，借助 N=2 时的 Gram 数目来度量两个序列的差异。

如果你并不知道我在说什么，那么具体而言是像这样的计算：

1. 假设我们有字符串 S1 与 S2。
2. 将字符串 S1 每两个连续字符作为一个元素，构成集合 G1，同理也有 G2。
3. 字符串 S1 与 S2 之间的序列差异就是 G1 与 G2 中不同元素的数目。显然，你可以通过他们的交集减去他们的并集取到该值。

def n_grams(a):
    z = (islice(a, i, None) for i in range(2))
    return list(zip(*z))

def groupDiffer(s1, s2):
    len1 = len(list(set(s1).intersection(set(s2))))
    len2 = len(list(set(s1).union(set(s2))))
    return abs((len2 - len1))

总算有了字符串间距离

到现在为止，我们对两个字符串间三个形式维度的差异都有了量化，接下来做的就是通过精妙绝伦的加权求和，算出那个令人拍案叫绝的字符串间距离。

在此，笔者使用的方法是——

def samplesDistance(str1, str2):
    a = strLengthDiffer(str1, str2)
    b = charSetDiffer(str1, str2)
    s1 = n_grams(str1)
    s2 = n_grams(str2)
    c = groupDiffer(s1, s2)
    d = a+b+c
    return d

是的！简单相加……

山不在高，有庙则有人送锦旗，算法不在复杂，有用就行。

你当然可以根据自己的需要，去调节系统对于其中三个维度的不同敏感度，但笔者认为字符集差异的值天然就比另外两种差异的值要大，已经符合我的需要，就不再调整啦。

你好像和他们不太一样

有了字符串间的距离，进一步，就有一个字符串到另一堆字符串的距离。我们定义如下：

字符串样本与字符串集合的距离 = 该字符串样本到字符串集合中每个字符串样本的距离的算术平均值

即：

def sampleClassDistance(sample, class1):
    list_0 = []
    length = len(class1)
    for item in class1:
        list_0.append(samplesDistance(sample, item))
    return sum(list_0)/length

你们是两类

由上一节的一个字符串到一堆字符串的距离出发，我们可以得到一堆字符串到另一堆字符串的距离。它的定义形式很相似：

字符串集合间的距离 = 该字符串集合中的每一样本到字符串集合的距离的算术平均值 = 该字符串集合中每一样本到另一字符串中每一样本的距离的算术平均值

即：

def classesDistance(class1, class2):
    list_0 = []
    class1 = flatten(class1)
    class2 = flatten(class2)
    m = len(class1)
    n = len(class2)
    for item1 in class1:
        for item2 in class2:
            list_0.append(sampleDistance(item1, item2))
    return sum(list_0)/(m*n)

类内无派，千奇百怪

同理，也可以定义“类内距离”作为一堆字符串内部的属性。它在实际意义上可能有些接近于方差。我们规定：

类内距离 = 该字符串集合到自己的距离

def innerClassesDistanse(class1):
    return classesDistance(class1, class1)

让我们停下来整理一下思路

到这里你可能已经晕了，定义这么多距离到底要干嘛？

我们说过，要把两类不确定的形式不同的字符串分开，关键是定义差异，也就是去量化“长得显然不同”到底有多不同。

于是我们发明了一些“距离”作为量化属性，两个字符串之间，有长度不同、构成的字符不同、字符序列不同，那么这两个字符串就有可量化的距离。

两个字符串有距离，那么一个字符串到另一类字符串、一类字符串到另一类字符串、同一类字符串内部也有距离。

当你混迹人群，最重要的事情是弄清谁是朋友、谁是敌人。而当你需要把人群分为两类，最重要的事情就是知道两类人有多不同，以及每类人内部有多一致。

放在分类字符串的情景，就是要能够量化类间距离与类内距离。

嘿，这不，我们已经有了 classesDistance() 与 innerClassesDistanse()。

就到这里，我们下次再会 :)

Part 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 = 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

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

让我们下回再见～