异端审判器！一个泛用型文本聚类模型的实现（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”、“>”‘>

” 呢？

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

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

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

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

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

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

主教的自我修养：看脸

北京与成都之间相距再远，也可以用欧式距离轻松度量。但 “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() 。

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