基于改进KNN的文本分类方法，本文主要内容关键词为：文本论文,方法论文,KNN论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 传统KNN方法分析
随着文本信息量的快速增长，文本分类已成为信息检索、知识挖掘和管理等领域的关键技术。文本分类的精确程度取决于特征提取的科学性和分类算法的科学性。现有的文本分类方法主要有支持向量机(SVM)、K近邻(KNN)、决策树、线性最小二乘法估计(LLSP)和贝叶斯分类算法(Bayes)[1]等，相关研究证明，KNN算法是VSM（向量空间模型）下最好的分类算法之一[1]。KNN方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别中非常有效，对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰等诸多优点。其基本原理为：计算未知类别文本向量与样本集中每个文本向量的夹角余弦值，以此判断文本相似度，在样本集中找出K个最相似的文本向量，分类结果为K个相似样本中相似样本最多的一类。
但在文本分类中，KNN方法的缺陷也突出地暴露出来，主要有：首先KNN算法是懒散的分类算法，对于分类所需的计算都推迟到分类时才进行，在其分类器中存储有大量的样本向量，在未知类别样本需要分类时，再计算所有存储样本和未知类别样本的距离，对于高维文本向量或样本集规模较大的情况其时间和空间复杂度较高（时间代价为o(n*m)，n为VSM空间特征维数，m为样本集大小）；其次KNN方法是建立在VSM模型上的，其样本距离的测度使用欧式距离，各维权值相同，也就是认定各维对于分类的贡献是相同的，显然这是不符合实际情况的，同等的权重使得特征向量之间距离或者夹角余弦的计算不够准确，进而影响分类精度；最后，对于文本的高维向量，对于分类起主要作用的维数远远低于文本本身的维数，相当多维对于文本分类意义不大甚至是噪声数据。
对于上述缺点，文献[2]提出运用BP前向神经网络来计算各维权值。此方法虽然利用了神经网络的分类和泛化能力，但存在以下缺点：(1)BP神经网络学习算法容易陷入局部最小点，且在高维文本及其高数据量的情况下，学习算法计算开销很大，学习速度缓慢，另外，只适合于较为平稳的环境下，因其新知识记忆会使老知识的记忆丧失；(2)在其测算属性权值的方法中，需要逐个删除输入节点，每次删除均可能需要重新训练BP神经网络，对于高维或者大量的样本，计算量过大。
本文针对以上KNN方法的不足，提出一种改进KNN方法，以提高其分类精度和速度。
2 基于CHI方法的特征提取和模式聚合
由上文可见，为了提高KNN方法的分类精度、降低分类的时间和空间复杂度，必须进行特征提取和模式聚合，以保留和聚合对分类有贡献的特征，去除对分类贡献不大的特征以及噪声数据，从而降低文本特征空间维数。常见的特征提取和模式聚合算法有互信息、期望交叉熵、信息增益、文本证据权、几率比、词频法以及CHI方法[3]。相关文献证实GHI概率统计通常比其它特征词提取算法为优[4]。
2.1 基于CHI概率统计的特征提取与模式聚合
2.2 模式聚合和特征选择步骤
本文将原始特征空间中每个词条称为一个初等模式。模式聚合就是将那些对分类贡献相近的初等模式聚合为一个新模式，所得的这些模式将代替原有初等模式用于分类操作，一个模式将代表一个或多个初等模式；特征选择就是选取对分类贡献较大的特征，抛弃对分类贡献较小或是噪声的特征。经过特征选择和模式聚合后用于分类操作的特征数量将大大减少。
基于CHI概率统计理论，模式聚合的具体步骤如下：
(1)特征提取。应用特征提取理论选取M个特征词条，这M个特征词条满足条件：其CHI值＞阈值，则由此所得词条矩阵具有M个初等模式。根据有关研究[5]，删除出现次数低于某个阈值的特征词条不会提高错误率。
(2)设有S个类别，则每个初等模式都可达到
3 改进的KNN方法分析
经过CHI进行特征选择和模式聚合以后，KNN方法可以建立在新的特征空间中，针对VSM模型各维平等权重的缺陷，本文提出基于神经网络和CHI的改进KNN方法，具体步骤如下：
(1)建立原始特征空间，选择原始特征（初等模式）。
(2)运用上述CHI方法进行初步特征选择和模式聚合。
(3)按下述方法建立在新的特征空间中各个文本的向量表达：设新的特征空间为m维，原始特征空间为n维，每个文本首先构成原始n维向量，应用THDF公式[7]计算特征词的特征值，然后对于新特征空间的每一维的特征值由原始特征空间对应维的特征值相加得到。
(4)以SOM对文本集进行训练。
(5)对于维数权重计算，采用以下办法：对各个类别的特征向量（SOM神经网络输出层神经元的内星权值向量）的各个分量各自求其方差，设n为样本维数，函数var()为方差计算函数，
表示所有的类别特征向量的第j维构成的n维向量，则各维的权重系数为：
(6)如果文本类别数过多，可以采用快速的筛选策略选择K个最相似样本，比如使用淘汰赛算法[8]，就可以使选择的时间代价从
下降到o(klog(num))。
为减少文本过高维数对SOM时间复杂度的影响，也为了避免噪声或者无关属性对SOM计算结果精确度的影响，本文首先运用CHI概率统计方法进行初步特征提取和模式聚合。特征权重计算原理：如果某一维在各个类别中取值基本相同，那么此维对于文本分类的贡献率就相对较低，而如果在各个类别中取值有较大差距，那么很明显其就具有较强的文本分类能力；而方差正好是反应变量分布均匀状态的主要指标。此方法优点如下：一次性完成各维属性权值计算，克服原有方法逐个测算属性灵敏度和重新训练神经网络的高昂时间代价，同时避免BP网络的诸多缺点，适合于文本此类维数高达成千上万维的情况，也可在其中进一步选择若干关于分类的重要属性，以降低KNN方法的计算量；对类别特征向量进行权重计算也避免了直接对样本集进行权重计算容易受样本集数量及其空间分布影响的缺陷。
4 实验分析
实验文本取自互联网新闻文本，包含来自财经、军事、文化、科技等12个类别的3514篇文章。首先对文本进行预处理，主要步骤包括：文本分词（文本分词结果得到11115个特征词），高低频滤词，过滤主题无关词，计算词频，向量单位化等。经过以上预处理，本文选择分词结果中5218个词作为原始特征空间的基，从而建立原始词条—文本向量矩阵，其中行代表词条在每篇文档中的权重，列代表文本在原始特征空间中的文档向量。计算词条－文本向量矩阵中各个元素权值的公式如下。
其中
为词条—文档矩阵中第i个词条在第j篇文档中的权值，N为文本库中文本数量，
为第i个词条在第i篇文档中的出现频率，
为词条i在整个文本库中的出现频率，有文献[7]证明此计算公式相对于其它常见公式可以对文本检索等操作取得最好的结果。以此为基础进行本文提出的改进KNN方法和经典KNN之间的对比实验。
经过计算，得到所有特征词在各个类别下的
值矩阵(5218x12)，经过程序测算和图形分析，其最大值为1395.58，但是80%的值小于0.4541，90%的值小于4.8309，为了滤噪和将各初等模式对分类贡献的分布曲线标准化，根据实际情况选择公式5中λ=90%。
首先对低于预设阈值的特征词进行过滤，即特征提取，根据实验可以认为阈值的选择如果设定在合理的范围内，对于最后降维空间维数影响较小，即降维空间维数对于此阈值不敏感，变化范围在3%左右。这个测算结果表明对于本文文本集而言对分类作出较大贡献的特征大约就在376到570个之间。具体测算结果如表1所示。
表1 降维空间维数与CHI过滤阈值关系表
存储样本和分类运算所需空间在文本数确定的情况下，与特征空间维数成正比，因此与原始特征空间维数对比关系也就是两种方法的空间代价对比。本文采用1.035作为预设阈值进行特征词初步过滤，在此基础上，表2测算特征词对分类贡献的统计指标。
表2 特征词对分类贡献统计表
从表2可看到，正如本文所述，在本文文本集中约有40%的特征词只对某一个分类有贡献，即只在一个分类中出现；只对1个和2个分类有贡献的特征词占特征词总数的7成，正因为如此，通过合并分类贡献分布相同的特征词，模式聚合方法才可大大降低特征空间维数。
表3 两种方法分类准确度对比
本文将样本集中3514篇文章分为2部分，其中每类抽取200篇，共2400篇作为KNN方法的存储样本集，其余1114篇作为测试集。表3中数字为在KNN方法中k的不同取值下，分类正确数目与测试集文本数量的比值。从上面的结果可以看出，改进算法使测试准确率有显著提高。但无论经典KNN方法还是本文的改进KNN方法，其分类准确率均没有达到70%。考虑其原因主要由于样本集基本取自网络新闻，部分类别之间界限比较模糊，存在内容交叉或者类似的情况；另外文本集的分类也基本依据网络原有的新闻类别划分，其类别设定存在一定的不合理，故影响分类的准确度。但相对而言，本文提出的改进算法其分类准确率仍明显高于经典的KNN方法和权值相同的改进KNN方法。
表4中数值为进行1114篇文章分类所需要的总时间，比值＝（改进KNN方法所需分类时间）／（经典KNN方法所需分类时间）。从表4可以看出，本文的改进KNN方法极大地降低了KNN方法进行分类所需的时间代价，其所需时间只相当于经典KNN方法的22%左右。模式聚合计算时间并不是每次分类都需要进行，对于某确定样本集，只需要计算一次，所以单列出来，并不和分类时间合并计算。
表4 两种方法分类时间代价对比 单位：秒
从表3和表4可以看出，无论对于经典还是本文的改进KNN方法，在本文文本集环境下，分类准确程度和时间代价与k的取值并不敏感，并不随k的增大而增大，也就证明在合适的算法下，选择k个最接近的文本向量比只选择1个最接近的文本向量多花费的时间并不显著。
5 结论
通过对上述实验结果的分析可以得出以下结论：本文提出的改进KNN算法可以在降低时间和空间复杂度的基础上，提高KNN算法的分类准确度，从而为文本处理环境下的实时分类提供良好的实现算法。基于CHI的模式聚合方法运用目前还有待进一步的研究，比如阈值的选择，曲线相似度判断的快速算法或者简化算法等都有待于未来的研究工作。
标签：kNN论文; 文本分类论文; 空间向量论文; 特征选择论文; 文本分析论文; 样本空间论文; 时间计算论文; 自然语言处理论文; 算法论文;