漫谈Clustering(2):k

这里我们用 N-gram 来代替 word 。这样，我们从一个文档中可以得到一个 N-gram 的频率分布，按照频率排序一下，只保留频率最高的前 k 个（比如，300）N-gram，我们把叫做一个“Profile”。正常情况下，某一种语言（至少是西方国家的那些类英语的语言）写成的文档，不论主题或长短，通常得出来的 Profile 都差不多，亦即按照出现的频率排序所得到的各个 N-gram 的序号不会变化太大。这是非常好的一个性质：通常我们只要各个语言选取一篇（比较正常的，也不需要很长）文档构建出一个 Profile ，在拿到一篇未知文档的时候，只要和各个 Profile 比较一下，差异最小的那个 Profile 所对应的语言就可以认定是这篇未知文档的语言了——准确率很高，更可贵的是，所需要的训练数据非常少而且容易获得，训练出来的模型也是非常小的。

不过，我们这里且撇开分类（Classification）的问题，回到聚类（Clustering）上，按照前面的说法，在 k-medoids 聚类中，只需要定义好两个东西之间的距离（或者 dissimilarity ）就可以了，对于两个 Profile ，它们之间的 dissimilarity 可以很自然地定义为对应的 N-gram 的序号之差的绝对值，在 Python 中用下面这样一个类来表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Profile(object):
 def __init__(self, path, N=3, psize=400):
 self.N = N
 self.psize = psize
 self.build_profile(path)
 
 sep = re.compile(r'\W+')
 def build_profile(self, path):
 grams = {}
 with open(path) as inf:
 for line in inf:
 for tok in self.sep.split(line):
 for n in range(self.N):
 self.feed_ngram(grams, tok, n+1)
 self.create_profile(grams.items())
 
 def create_profile(self, grams):
 # keep only the top most psize items
 grams.sort(key=itemgetter(1), reverse=True)
 grams = grams[:self.psize]
 
 self.profile = dict()
 for i in range(len(grams)):
 self.profile[grams[i][0]] = i
 
 def __getitem__(self, key):
 idx = self.profile.get(key)
 if idx is None:
 return len(self.profile)
 return idx
 
 def dissimilarity(self, o):
 dis = 0
 for tok in self.profile.keys():
 dis += abs(self[tok]-o[tok])
 for tok in o.profile.keys():
 dis += abs(self[tok]-o[tok])
 return dis
 
 def feed_ngram(self, grams, tok, n):
 if n != 0:
 tok = '_' + tok
 tok = tok + '_' * (n-1)
 for i in range(len(tok)-n+1):
 gram = tok[i:i+n]
 grams.setdefault(gram, 0)
 grams[gram] += 1

europarl 数据集共有 11 种语言的文档，每种语言包括大约 600 多个文档。我为这七千多个文档建立了 Profile 并构造出一个 7038×7038 的 dissimilarity matrix ，最后在这上面用 k-medoids 进行聚类。构造 dissimilarity matrix 的过程很慢，在我这里花了将近 10 个小时。相比之下，k-medoids 的过程在内存允许的情况下，采用向量化的方法来做实际上还是很快的，并且通常只要数次迭代就能收敛了。实际的 k-medoids 实现可以在 mltk 中找到，今后如果有时间的话，我会陆续地把一些相关的比较通用的代码放到那里面。

Hungarian algorithm 来求解。

我们这里有 11 种语言，全排列有 11! = 39916800 种情况， 对于每一种排列，我们需要遍历一次 label list ，并数出真正的 label （语言）与聚类得出的结果相同的文档的个数，再除以总的文档个数，得到 accuracy 。假设每次遍历并求出 accuracy 只需要 1 毫秒的时间的话，总共也需要 11 个小时才能得到结果。看上去好像也不是特别恐怖，不过相比起来，用 Hungarian algorithm 的话，我们可以几乎瞬间得到结果。由于文章的篇幅已经很长了，就不在这里介绍具体的算法了，感兴趣的同学可以参考 Wikipedia ，这里我直接使用了一个现有的 Python 实现。

虽然这个实验非常折腾，不过最后的结果其实就是一个数字：accuracy ——在我这里达到了 88.97% ，证明 k-medoids 聚类和 N-gram Profile 识别语言这两种方法都是挺不错的。最后，如果有感兴趣的同学，代码可以从这里下载。需要最新版的 scipy， munkres.py 和 mltk 以及 Python 2.6 。