这个是广研班的最后的大作业，具体是导师给了一堆垃圾邮件的标题，大约有1W条，然后我们的事是把这些短文本按照相似性进行聚类。或许对于有过文本聚类的同学来说不算难题，但对于我来说还真是一个很难的问题。题目是按小组来完成的，我所在小组有三人，都没接触过这类问题，我们大约是周五下午拿到的题目，周日晚即要交作业。所以最后能作出东西来，聚类效果也还不错的时候，我便又忍不住佩服我们小组的同学，包括我自己。。。。 这次作业有很多是小组另外两个同学完成的，感谢他们两位。
因为小组讨论后决定用python来完成作业，对于没有用python写过代码的我，只好用了半个晚上速成了一下python，然后第二天就提抢上马用pyhton写作业了。。可见python易用性还是很好的，感谢python，感谢Guido Rossum。
首先是文本的分词与过滤。因为导师不允许我们使用现有的中文分词器及带有频率信息的字典，所以我们只能自己写分词模块及过滤模块。分词我们用的是正向匹配，这这个模块是我们组另外一个同学完成的。完成的分词效果应该说虽不完善但可用。主要是时间的限制，我们只选择了相对简单的正向匹配，而没有使用更复杂的双向匹配，也受时间限制，没能找到更全更大的字典。 前向匹配的算法思想是，对于文本内容，从左到右扫描，如果连续的几个字在字典中存在且这个字跟后面的字不再构成字典里存在的词，则将这几个字”切“出来。这种算法简单好实现，但缺点也明显，他的准确度完全依赖于字典的完整度。而且字典越大，效率越低。 分词之后是对过滤，主要是过滤掉一些停词，心腹一些无意义的单字，比如垃圾邮件标题中常见的火星文及全角符号，这部分是我做的。这里要说明一下，用正向匹配分词后，不能被字典的匹配的会以单个字存在保留下来。本来过滤没什么好说的，就拿个停词表字符串匹配一下就完事，但在实践中我们发现，停词表远远不够，单字的漏网之鱼太多。后来我就想到用一个常用中文字表，再过滤一下：不在常用中文字表里的单字，全部过滤掉。这样下来，效果就很好了，我们得到了纯净的，基本是包含这个短文本关键信息的词语或单字。
接着是对取出的单词计算权重。这里我们用的tf-idf，这部分是我做的。其实对于用什么来提取短文本的特征向量，计算各单词的权重我们队伍讨论过多次，因为对于短文本来说，几乎每一个分词出来的单词都是唯一的，于是tf就几乎没有意义了。但最后我们也想不其他可行的算法，于是我便决定反正先写出来，用着试一下好了。后来用着对最后的结果也是只有一点细微的提升。 tf-idf的算法思想是，tf*idf，tf是词频，指单词在其所在文档中出现的频率。idf是逆向文档频率，idf基于这样一个假设，如果某个单词所在文档在所有文档中出现次数越小，则说明这个单词越特殊，越能代表其所在的文档。idf的算法是，总文档数目除以出现该单词的文档的数目，再将得到的商取对数。 从上面的描述，我们直观都可以感觉到，它对短文本聚类真没啥大用。。。 这部分代码着实简单，如下。因为当时讨论时有想过不用tf-idf只用idf，因此我的代码里将tf、idf、tf-idf三者分开实现，实际上的tf-idf是可以不用到下面的tf和idf函数的。
#!/usr/bin/env python2.7#coding=utf-8#Tfidf类import mathclass Tfidf: newWords = {}#单词频率字典 wordsNum = 0#总文档数目 #获取并统计所有单词 def getWords(self,allWords): for lineWords in allWords:for word in lineWords:if word in self.newWords:self.newWords[word] += 1 else:self.newWords[word] = 1self.wordsNum += 1 #计算tf def tf(self,line): tfDict = {} lineLen = float(len(line)) for word in self.tfDict: tfDict[word] = line.count(word)/lineLen return tfDict #计算idf def idf(self): idfDict = {} for word in self.newWords: idfDict[word] = math.log(float(self.wordsNum)/self.newWords[word]) return idfDict #计算tfidf def tfidf(self,line): tfidfDict = {}; lineLen = float(len(line)) for word in line: wordFrequency = float(self.newWords[word]) tfidfDict[word] = line.count(word)/lineLen * math.log(self.wordsNum/wordFrequency) return tfidfDict def __init__(self,allWords): self.getWords(allWords)
接着是对这些单词作simhash，这也算是这个作业或者说项目的核心了，这部分也是队伍里的另一个同学主要完成的，膜拜一下他。simhash其实也还简单，他的算法思想是，对文本中的提取出来的单词，先用普通hash（如md5）降维，得到一串固定长度的二进制值，对该值的每一位，加减该单词权重（0则减，1则加），又得到一串值，再将所有单词算出来的值按位相加，对结果取其符号，又得到一串二进制值，成为该文本的fingerprint。 从上面的算法就可以看到，simhash是一种LSH（局部敏感性哈希）哈希。 完成simhash之后是将文本的fingerprint比较海明距离，低于阈值则将之放进一同一个聚类的桶里。海明距离是指两fingerprint间不同的位的个数，海明距离越小则说明两个文本越相似。
在正式比较fingerprint之前，我想到用一个字典来存储，健为fingerprint，值为对应的文本，先对fingerprint做一次去重。因为对于完全相同或极度相似的文本来说，经过提取单词，过滤后，他们计算出来的fingerprint应该是一样的，因些先做一次去重可以降低后面参与比较海明距离的数量。对于我们这个项目，导师给的约1.2W条文本，去重后就只剩下大约6000条数据了。
比较海明距离是整个项目中最费时间的一步，如果是普通的两两比较，其时间复杂度可以去到O(n^2)。而导师对我们的要求是，要在5分钟内完成聚类。如果是前面没有去重，那么这样的复杂度是难以接受的。 后来队伍的同学想到的是将每一个fingerprint只与桶中已有的每一个文本做比较，这样子做虽然不能降低比较的时间复杂度的量级，但能降低比较的常数。于是我们的时间进一步降下来了。最后，我们的程序大概在I7的机器上跑1分半钟。满足了。
PS：为什么挂出最没用的tf-idf的代码，因为只有这一部分是全部是我做的，其他的都是小组三人的作品，不好随便挂。。。
