算法设计原理

4．2　算法设计原理

如前所述，在采用统计方法的自动分类领域，有关权值计算方法基本稳定了，当然在此基础上也有一些改进方法被研究出来，如曹慧提出的AMTW算法等^［10］。在此对各特征权重计算方法作分析：

①TF－IDF方法：该方法将文档集作为整体来考虑，但忽略了特征项在类间和类内的分布情况。可以设想，如果某一特征项在某个类别大量出现，而在其他类别出现较少，则其分类能力应该很强。但TF－IDF算法对此的体现不强烈。另外，对集中分布于某一类别但类内分布相对均匀的特征项的权重应该比分布不均匀的要高（即类内出现特征项的文献数量很少时，可能该特征项是特例，不具代表性），TF－IDF无法排除这种特例情况。同时该方法也对低频高权的特征项同样没有很有效的处理办法。

②MI（互信息）：互信息方法其含义是针对每个特征词，可以以其在每个类别中的出现占它在整个文本集中的出现的比率作为它对每个类别分类依据的贡献。该衡量方法是基于各个类别中的文本量大致相等的假设的，即这种方法忽略了类别中文本量的多少对词条在每个类别中出现的比率的影响。可以设想有一种极端情况，类别c_i有超过100个的样本，而类别c_j只有1～2个少量样本。这时，即使某个词t与类别c _i的相关程度很小，由于计算得出的其和c_i的互信息很大而被选中作为特征项。相反，即使t与类别c _j的相关程度很大，但由于计算得出的其和c_j的互信息很小而可能被丢弃不作为特征项。这是该方法的缺陷所在。

③CHI（x ²）：原算法未考虑特征项出现与否对分类的贡献可能存在正贡献和负贡献的情况。

④IG（信息增益）：信息增益方法由于考虑了单词未出现的情况，认为“单词不出现”对判断文本分类有贡献，但相关研究表明，这反而对分类造成了较大的干扰。尤其是在类分布和特征项权值分布高度不平衡的情况下，出现较多的负类和较多的不出现特征词，从而导致最终分类精度的下降。

因此如何避免上述方法的不足（对部分低频词的倚重），发挥它们的优势，需要一种矫正方法。因各类算法的复杂度均比较高，单纯通过加大训练语料不可取。另外，以上方法虽然计算公式不同，但有一个共同的特点，即基本都是以词在类内、类间的频率或概率为基础的。

基于以上分析，笔者设想，在基本词频统计完成的基础上，依次按上述方法计算其权值，在设定阈值范围内确定各自的特征项集，最后取其交集，并计算综合权值，可以称其为“投票法”。

具体思路描述如下：

在训练集中选取某类，特征选择方法i的权值计算结果为（已按权值大小排好序，括号中的第2项为序号）：

S_i：T _i¹（x _i¹，y _i¹），T _i²（x _i²，y _i²），T _i³（x _i³，y _i³），…，T _ij（x _ij，y _ij）　　（i＝1，2，3，…；j为集合元素总数）

如此，共有4个这样的集合，依次为S₁，S₂，S₃，S₄。在取定的特征项数量内进行交运算：

某个特征词T _w的最后权值为：

其中T _w为最终权值，y _i为该特征词在各个集合中的序号。之后再重新排序并确定为最终该类的表达向量矩阵。

特征选择及权值算法：

输入：抽词结果库

输出：投票法权值计算的特征向量库

步骤如下：

Step1：抽词结果库的类内词频统计

Step2：抽词结果库的类间词频统计

Step3：基于四种权值计算方法的各权值计算

A）TF－IDF，生成w＿value/w＿value2列集合（分别存储特征权值及排序后的序号，下同）

B）MI，生成m＿value/m＿value2列集合

C）CHI（x₂），生成c＿value/c＿value2列集合

D）IG，生成i＿value/i＿value2列集合

Step4：计算序号均值，生成value/vaule2列集合

Step5：根据设定阈值，生成最终向量分类矩阵知识库

示例如下：

取训练集中“法律”类为例，其中的前14条特征项分别采用以上4种方法进行权值计算，结果如表4－1。

最终的权值采用合集方式确定，计算方法见公式4－8。

为了观察不同特征项选择及权值计算方法对分类效果的影响，验证笔者所设计方法的改进效果，笔者对此进行了验证实验。

本次实验测试数据采用ChinaInfoBank^［11］数据集，分类器采用最小距离分类器，即单一向量夹角余弦公式，测试环境同前。在其他条件不变的情况下，分别采用综合权值方式及各自单独权值方式进行自动分类实验，然后进行统计对比。