来源 | AI实战派
作者 | AI实战派
当我们想要切入某个领域时，显然这个领域已经有大量前人的工作，包括大家常用的模型、数据集、评价指标等等，初出茅庐的你却不知道这些大家习以为常的背景知识，那么如何才能快速切入一个子领域呢？
本文展示了一个例子，以复现一篇论文为起点，快速切入向量空间模型领域。
想要切入向量空间模型领域，首先先选择一篇时间上足够近的论文并且文章中有介绍以前常用的方法，并将自己提出的新方法与常用方法进行比较。文章最好有一定的引用量防止作者故意挑偏门的模型做对比，满足这样条件的论文挑出几篇，收集并复现他们所提到的方法，收集多了就会发现，他们提来提去就是那几种模型，那几种指标。当你对被经常提及的模型和指标滚瓜烂熟时，你就算是入门了。
这里笔者选用的第一篇论文是学校老师发表的：Entropy-based Term Weighting Schemes for Text Categorization in VSM。
笔者通过复现论文新提出的tf_dc，tf_bdc，以及用于实验比较的tf·idf, tf·chi, tf·ig, tf·eccd, tf·rf and iqf·qf·icf，在使用和论文实验一样的语料库 Reuters-R8 和 同样的分类模型 ：KNN和SVM
在此将整个复现的流程记录和小结一下，从阅读论文到实现计算方法再到使用分类模型到评估结果，整个过程虽然遇到了不少问题，但最终能够逐个克服并最终完成复现。
复现基于python2.7，KNN使用sklearn包，SVM和原论文同样使用liblinear，鉴于只是大致复现，因此除了和原论文同样对KNN的邻居数目参数进行实验外，没有细致对knn和SVM做调参。
理论介绍
向量空间模型
在自然语言处理过程中，第一步都是将要处理的字、词或文本转换成向量，毕竟计算机不懂文字，它只会处理数字。把词转换成向量我们有one hot, word embedding。到了文档层级，既然文档是由词语组成的，那么可以试着用词语来表示文档。来看看一个用one hot表示文章的例子：
假设词汇表有 ['one', 'apple','a','day','an'], 此时只使用one hot，即只判断记录词是否出现，不记录词的频率
文章a = "one day". 那么 它的向量则是 [1,0,0,1,0]
文章b = "an apple"， 则代表b的向量是[0,1,0,0,1]
one hot表示法虽然简单，但也有很多缺点，比如只记录词出现与否，词的区分能力被认为是一样的等等，由此人们提出了很多计算方法，核心思想就是表示出一个词的辨别能力。
词语的辨别能力是指：这个词将一篇文档从其它文档中区分出来的能力（或者将一个类从其它类区分出来的能力）,比如说一篇文章出现 "算法" 这个词较多，那么它通常会是计算机等领域的文章，而不太可能会是体育、艺术类的文章。
就拿之前的例子而言，an和One这种词明显在很多地方都会出现，因此它们的辨别能力不强，而apple就比它们好一点，那么在特征权重计算中，它的权重就会比其它两个高一些。
由此，每个词语对应一个维度，每个词语有一定的权重（由训练语料训练出来，代表这个词区分各类文档或各个标签的能力），再结合词语在文本出现的次数，就能够构成一个多维向量，将文档成功投射到多维空间中，这就是向量空间模型。投射之后，计算文章之间的相似度就可以有很多方法了，比如直接计算空间当中的距离啊，cosine啊等等，那么我们就可以将文章归到和它相似度高的那类中，由此完成文档分类的过程。
旧方法
为什么需要提出新的权重计算方法呢？因为旧的不够好，不够好在哪里？论文给出了理由：
大多数监督学习的计算方法基于词在 PC（positive category） 和 NC（negative category） 中的出现次数，就会有以下问题：
- PC是单独一个类， 而 NC包含多个类，而把它们统一成一个数字，那么显然NC的数目要远远大于PC，在权重计算中也会占主导地位。
- NC包含多个类，仅归为一个数字后，词语在这些类中的分布信息就丢失了
- 计算权重得基于标签，但测试文档本身就不具备标签
对于非监督的计算方法，就拿tf-idf来说，其能力在于将一篇文档从其它文档区分出来，而不是将一个类从其它类区分出来。
文章列举了其它较为流行的权重计算方法，并依照上面提出的问题一一举出了例子。
tf·idf
作为最流行的权重计算方法，其计算方法分为两个部分
一个是tf(i,j)，即词i在文章j中出现的频率：
用词i出现的次数 / 这篇文章总长即可
另一个是 idf(i,j)，称为逆文档频率，和这个词出现的文档数相关：
用文档总数 / 出现了 i 的文档数目，而后再取log，一般为了防止分母为0会在分母上加一。
最终的 tf-idf就等于两者相乘。
tf·chi
基于统计的卡方检验和下面一些计算方法都基于以下这个表格：
A：类别k中出现了词j的文档数目
B：除类别k外的其它类出现了词j的文档总数，用词j出现的文档总数 - A 即可
C：负文档数目，即类别k中不包含词j的数目，用 类别k的文章总数-A
D：其它类别不包含词j的数目，用其它类文档总数 - B
卡方检验的原始公式和近似公式：
tf·ig
Information Gain 信息增益：增加了这个信息使得系统的熵降低了多少。
在特征权重计算中，以词语出现与否分别计算整个语料库的熵，以熵的差值作为词语的信息增益，即词的权重。
P(Ci)：表示类别Ci出现的概率，用Ci包含的文档数除以文档总数
P(t)：词语T出现的概率，用出现过T的文档数除以总文档数
P(Ci|t)：出现T的时候，类别Ci出现的概率，用出现了T并且属于类别Ci的文档数除以出现了T的文档数
P(～t)：词语T不出现的概率，用 1 - P(t) 即可
P(Ci|～t)表示未出现T的时候，类别Ci出现的概率，用未出现了T并且属于类别Ci的文档数除以未出现T的文档数
tf·eccd
论文Entropy based feature selection for text categorization同样提出了一种基于熵的权重计算方法
tf·rf
由于表格中B、D的数目显然很大，为了避免它们带来的影响，人们提出了relevance frequency（rf），只是用 a和c的比值来表明一个词的辨别能力。
iqf·qf·icf
这篇论文 Term weighting schemes for question categorization面对短文本（用户提出的问题）提出三种新的权重计算方式：iqf*qf*icf、qf*icf 和 vrf。
和rf相比，iqf*qf*icf额外考虑了一个词出现了类数目，然而正如论文提出的那样，只考虑了类的数目，却没有考虑到词在这些类内部的分布情况。
新的权重计算方法tf·dc
论文论证了用熵来表示词语辨别能力的可行性，由此提出了新的计算方法 dc：distribution concentration。
思想基于两点：
- 辨别能力和词语在所有类的集中程度有关，词语集中程度越高，则它只出现在很少几个类，那么它的辨别能力就越高
- 集中程度越高的词，具有的熵越小
H(t)即代表t的熵， f(t,ci)表明词语t在类别 ci出现的文档数目
由于
，在除了log(|C|)之后就能将熵化为[0,1]区间，这使得同一篇文章内的词有了可比性。
tf·bdc
考虑到现实中语料库类别包含的文档数目有差异，并非理想中所有类的文档数大致相等，那么为了平衡类之间的规模差异，论文在dc的基础上提出了bdc：balanced distribution concentration。
为了避免大类文档数目过多带来的偏差，论文将绝对频率换成了概率，由此平衡类之间的差异。
复现过程用特征权重进行文本分类的思路
文本分类的整个过程如下：
- 通过训练语料库计算得到词语权重，并通过将语料库文章投影成向量构成训练特征，标签则为类标签索引，以此训练KNN或SVM模型。此步主要得到三样东西：
- 词语权重表
- 词汇表：计算词语频率后删减频率过高和过低的词的产物，每个词汇表里面的词将作为一维，每篇文章为 1*n 的向量，n为词汇表大小。
- 模型参数
- 对于每篇测试文档：
- 根据词汇表删去无关词汇
- 查词语权重表，若使用tf则额外计算每个词语在文本中出现的频率。得到每个词语的词语权重，由此得到文档的向量表示
- 将文档向量作为特征输入分类模型中，得到预测结果
数据处理
语料库和论文中同样选用路透社的语料 Reuters-21578 R8，鉴于Reuters的语料是有名的难处理再加上复现的重点不在此，因此笔者直接使用处理好的语料：Reuters-21578 R8（http://ana.cachopo.org/datasets-for-single-label-text-categorization），TrainingSet（http://ana.cachopo.org/datasets-for-single-label-text-categorization/r8-train-all-terms.txt?attredirects=0），TestSet（http://ana.cachopo.org/datasets-for-single-label-text-categorization/r8-test-all-terms.txt?attredirects=0）.
获得语料之后，一个比较重要的地方在于制作特征向量和标签。
我的特征向量和标签制作方法是：
- 对于文档，首先将所有词转换成one hot，转换使用了sklearn.preprocessing中的Encoder，然而一件很重要的事情在于one hot的顺序，因为Encoder会按照词汇出现顺序设置one hot的顺序，因此我的做法是把文档的词连接在词汇表后面一起导入Encoder，而后再对生成的one hot进行截取，因为词汇表的顺序和大小是固定的，所以截取也很方便。需要注意的是要将词汇表设置为全局的，并且仅在训练集中构造词汇表，而测试集仅用词汇表进行筛选。
- 对于类别标签，同样在训练集中构造标签表，而后串接起来导入Encoder再截取，然后用argmax获得唯一的1所在的下标，由此将字符串转换成了单个数字。
维度压缩
在复现的过程中，首先遇到的第一个小问题就是维度过大，虽然只使用了几MB的语料库，但要是把每个词都作为一维的话，那就有将近两万维，刚开始直接运行的时候电脑就报出超出内存的错误了。
解决方法就是删去频率过高和过低的词：
- 统计训练语料中的词语频率得到词频表和词汇表
- 使用Counter得到各个频率的词汇数目并使用matplotlib.pyplot将词汇频率绘制成直方图，此外还将词汇表的长度作为额外参考
- 根据长度、频率分布挑选阈值，根据上下界删减词汇表
- 根据词汇表删去训练和测试语料的其它词，仅保留在词汇表中的词语。
通过这么个维度压缩，使得维度从两万维降低到五千多维，不仅加快了运行速度，减少了运行需要的空间，同时也减少了停用词和自造词的干扰。
删减前
删减后
KNN中的cos近似
下一个比较重要的小问题在于sklearn中的KNN提供的计算距离的函数并没有cos距离，而后在寻找解决方案时发现了这条stackoverflow上的回答：
https://stackoverflow.com/questions/34144632/using-cosine-distance-with-scikit-learn-kneighborsclassifier
回答分为两个方面：
- 指出为什么cosine相似度没有在sklearn包中：cosine相似度在两个向量完全一样时的输出结果是1，在它们完全相反时结果是-1，而这严格上并不能算作衡量指标，其它如欧几里得距离，向量相似度越高距离越小即越接近于0. （不过为什么通过1-cos近似），因此不能使用knn的加速结构来加快运算。
- 给出了解决方法：
- 可以自行实现cos相似度并作为函数参数传进去，代价就是不能使用knn中用于加速的结构，只能使用暴力计算。
- 第二个方案比较巧妙，通过深入到公式的转换把计算cosine相似度转换成用归一化之后的欧几里得即可。
看完之后笔者被那个公式转换惊叹到，而后果断地采用了这个方案，在计算出文档向量之后，额外做一次归一化，之后只需要正常传入knn，距离函数用默认的欧几里得距离即可。
论文细节
论文中的实验部分有这么一句话：
To represent test documents with category-specific schemes, e.g., tf·chi, tf·ig, tf·eccd, tf·rf and iqf·qf·icf, we adopt a popular method in previous studies hat assigning the maximum value among |C| estimated weights to each term in test documents.
鉴于笔者阅读时没有考虑到实现，所以当时始终不明白这句话的意思，但后来在实现话中提到的 tf-chi、tf-ig等方法时程序频繁报出词典key error，而后想起这句似乎关键但并不太明白什么意思的话，再结合实现时候的问题，终于明白了。
权重计算方法如 tf-idf 分为两个部分，一个是 tf ，由一个词在一篇文章内出现的频率得到，训练集和测试集均要计算，用python代码表示即是一个两层的词典
tf[document][word] = frequency[document][word] / doclength[document]
另一个是 idf ，由一个词在语料库中出现的文档数和文档总数计算得到，对于训练集是需要计算得到的，对于测试集则相当于权重词典，要用的时候直接查就行，而它的表现形式在tf-idf中是一个单层的词典，idf只计算每个词，和词在哪个类中没有关系。
tf_idf[document][word] = tf[document][word] * idf[word]
而对于如chi等词，它们词权重计算不仅和词相关，还和类别相关。意思就是每个词的权重在不同类是不一样的，用代码表示出来即是：
tf_chi[document][word] = tf[document][word] * chi[label][word]
那么就有一个比较重要的问题：要是测试集的词在测试文档属于的类中不存在怎么办？那句话就给出了答案：若是词在所属类中不存在权重，那么就在其它类里面选择这个词权重最大的那个作为权重，用代码表示就是：
if weights[labell].has_key(word): tf_chi[doc][word] *= weights[labell][word]else: tf_chi[doc][word] *= max([ weights[x][word] for x in weights if weights[x].has_key(word)])
由此，缺失的拼图找到了，笔者最终成功实现了这些权重计算方法。
衡量标准
根据论文原文，实验采用了两种衡量标准：MicroF1和MacroF1：
- MicroF1就是一般说的准确率：预测正确的数目 / 测试样本总数
- MacroF1 就是通常的F1的均值：
- 正确预测为C的数目 / 预测为C的总数：正确预测为C的数目 / 真实为C的数目：
- TP: true positive 属于C被分到C（预测正确）TN: true nagative 属于C被分到其它类（预测错误）FP: false positive 不属于C被正确分类（预测正确）FN: false nagative 不属于C被分到C（预测错误）
复现结果
下面是复现之后的结果：
笔者在未调参的SVM、KNN上，使用Reuters R8语料库的结果（KNN邻居数在1-35内选择结果最优的）：
论文给出的最终结果：
笔者复现的在Reuters R8中KNN邻居数和MicroF1的关系：
论文给出的关系图：
可以看到，虽然数据上略微有差距，但经过在模型上的优化之后应该能够接近或达到论文给出的结果，提出的新的权重计算方式tf_dc和tf_bdc在Reuters R8上的表现还是不错的，不说能够傲视所有权重计算方式，起码表现足够优异，有一席之地。
小结
通过这次复现，笔者较为深入地学习了向量空间模型VSM，还了解了各种权重计算方法，谈到权重计算也不再只有单一的tf_idf了。此外，这么一个完整的，从数据到特征（虽然语料库预处理不是我做的），再到导入模型进行训练，再到预测，最后进行评估，这么个流程走下来之后，笔者对于机器学习的理解也加深了。光是从调包上讲也知道怎么用KNN和SVM，怎么做数据可视化了。
源代码
原论文、笔者实现过程的完整代码（包括训练模型、测试、评估、所有权重计算方法）、笔者实验得到的数据（MicroF1和MacroF1，knn各个邻居数上的MicroF1，可直接调用评估函数查看结果）都可以在我的github上看到（复制到浏览器打开）：
https://github.com/zedom1/VSM
The End
,
