自然邻在文本分类中的应用

朱庆生，张浪，张程

（重庆大学计算机学院，重庆 400044）

自然邻在文本分类中的应用

朱庆生，张浪，张程

（重庆大学计算机学院，重庆 400044）

在文本分类中，传统的KNN算法面临K值不确定，数据集分布不平衡等缺点的影响。基于此提出自然邻的思想，并将其应用到文本分类中，很好地克服KNN文本分类的缺点。首先，自然邻算法能够根据数据集自动获取文本向量的自然邻居，不需要人为干预，解决K值不确定问题。其次，对于不同的数据点其邻居数可能不一样，它会根据数据集的分布自动获取其对应的自然邻居，很好地克服数据集分布不平衡问题。并且，根据训练集的自然邻居设计一种权重分配算法，使得好邻居的权值较大，坏邻居的权值较小，进一步提高分类算法的精确度。

文本分类；自然邻居；KNN；权重分配

0 引言

近年来，随着互联网的飞快发展，网络信息量呈爆炸性的增长，增长速度比人类历史任何时期都要快的多，以互联网为载体的海量数据蕴含着大量的信息价值，因此有效地发现分析挖掘这些信息中的价值是很有必要的，可以给我们带来更大的生产力，给我们的生活带来更多的便利。传统的信息处理方法已经不能完全胜任各式各样的任务需要，一种新的数据处理方法应运而生，数据挖掘技术[1]弥补了传统数据处理方法的不足，能够发现海量数据背后蕴藏的有效信息，并且对于复杂的数据结构，对于那些传统数据处理方法很难下手的数据类型拥有更强的灵活性。更为重要的是在处理的方法上，不再拘泥于传统数据的增删改查，或是数据仓库的处理，其方法的广泛性和灵活性非传统方法所能比拟。

自动文本分类[2]属于数据挖掘技术中一个重要领域，在互联网出现之前，人们已经对文本分类进行了一定的研究工作，这些研究往往针对特定的领域，然而，随着互联网兴起，随着对大量不同类型的文本进行分类的需求，传统的分类方法不再适用。我们需要更加自动化的分类方法，文档自动分类技术的研究势在必行。国外对文本自动分类的研究最早可追溯到上世纪50年代末，由H.P.LUhn提出的一种基于词频统计的文本分类思想开创了文本自动分类的新天地。1960年，Maron发表了第一篇关于文本自动分类算法的论文，之后K.Spark、G.Salton等学者相继提出了很多关于文本自动分类的实用方法。由于对文本自动分类的研究较早，且技术相对比较成熟，所以在文本自动分类的实际应用上，国外也开始的比较早，而且应用广泛。其中邮件分类、电子会议取得了广泛的应用。知名度比较高的有麻省理工学院为白宫开发的邮件分类系统，卡内基集团为路透社开发的Construe系统[4]。

国内文本自动分类的起步较晚，1981年，候汉清教授对计算机在文本自动分类中的应用作了探讨和论述[6]。在分类算法的研究方面，中科院计算所的李晓黎、史忠植等人将概念推理网应用到文本分类中[5]，使得准确率和召回率得到比较明显的提高。中国科技大学的范焱等人提出了一种超文本协调分类器[3]，它适当考虑了HTML文本中的结构化信息，并将其和KNN、贝叶斯、和文档相似性研究结合起来，使得正确率接近80%。复旦大学和富士通研究中心的黄萱箐、吴力德对独立语种的文本分类进行了研究[8]，用词汇和类别的互信息量为评价函数，使得召回率达到88.87%。上海交通大学的刁倩、王永成等人考虑了词的权重和信息[11]，使得分类算法的准确率到达97%。

对于文本分类，相对比较成熟的分类算法有KNN分类算法、贝叶斯分类算法、支持向量机分类算法、决策树分类算法、神经网络等分类算法[7]。这些都是比较成熟的传统分本自动分类算法，很多学者基于上述方法对其改进能够得到整体效率或者对于部分数据集效率一定程度提高的混合型算法。

文本针对传统的KNN算法所面临的不足点，创造性提出了自然邻的思想，并将其应用到文本分类中，解决了KNN文本分类算法中K值无法确定问题，并提高了分类准确度。

1 文本分类定义与过程

文本分类属于分类问题，是一种有监督的学习。它的任务是：根据已定义类标签的训练集将未定义类标签的测试集中的每个文本分类到一个或者多个类标签中。这里有三点需要注意，第一，用于分类的类标签是已经定义好的，并且，训练集都有属于的类标签，这样才能从训练文本中学习到规则，为测试文本分类。第二，测试文本集中的文本可以被分配到一个或者多个标签中，而不是仅仅只能分配到一个标签中。第三，文本分类的类标签并不一定是主题信息，也就是说类标签可以是文章性质，例如积极消极，写作风格等。

文本分类一般过程可分为以下几个步骤。文本预处理，特征提取，特征权重计算，训练，分类预测[10]。如图1给出了文本分类的一般流程图。

2 基于KNN文本分类

2.1 KNN文本分类步骤

基于KNN的文本分类算法基本思想是：对于文本测试集中的每个文本向量，通过某种距离度量在训练文本向量中找出与其最近的K个邻居，并根据这K个邻居的类别信息将测试文本归类到相应的类别中，具体算法步骤见如下算法1：

算法1 KNN文本分类算法

输入：训练文本向量D，测试文本向量T，K

输出：带有预测类别的测试文本集

算法步骤：

Step1：对每个测试文本向量，计算距离训练文本向量最近的K的邻居

Step2：计算每个测试文本向量属于每个类别的余弦相似度总和

Step3：将改测试样本归类到余弦相似度总和最大的类别中

Step4：遍历所有的测试文本向量，完成并输出分类结果

图1 文本分类流程图

2.2 KNN文本分类缺点

基于KNN的文本分类算法简单、鲁棒性好且易于实现，并且具有不错的分类精度[9]。但是也和其他的算法一样有其自身的缺点，主要缺点如下：

（1）K值不易确定

KNN分类时K值的设定不确定，需要尝试不同的K值来找到最佳的K值，并且文本分类所使用的数据集不一样时，又得重新寻找最佳的K值，这是比较麻烦的事情，如果K值设定过大，那么它的K个邻居中可能包含很多和测试样本类别不同的邻居，这样必定会影响分类结果。如果K值设定太小，它的邻居数很小，很容易收到误差点的影响。

（2）分类精度受数据集分类影响很大

导致这样的主要原因是对于所有的测试文本向量，它所找的邻居数都是K，也就是说无论是稀疏的点还是稠密的点，它所比较的邻居数都是一样的，这显然有些不合理。

（3）计算复杂度大

KNN文本分类需要计算每个测试文本向量与训练向量的距离，当训练文本向量很大时，其计算复杂度会很大。

3 基于自然邻的文本分类

3.1 自然邻概念

基于传统的K近邻思想，本文提出了一种无尺度的近邻度量方法即自然邻方法。所谓自然邻，顾名思义，即根据数据集自身的分布情况自适应的得到每个样本点的邻居。那么，如何获取呢？其具体步骤为：以KNN为基础，K值从1递增，每次统计互为邻居的数目是否达到自然稳定状态，如果达到自然稳定状态，认为那些互为邻居的点便为各自的自然邻居。具体算法如下。

算法1自然邻居算法

输入：数据集X

输出：自然邻居特征值λ自然邻居邻域图边集NaN_Edge

其中，λ表示自然邻居特征值；NaN_Edge表示自然邻居边集；NaN_Num（xi）表示xi的自然邻居数目；knnr（xi）表示xi的r近邻；KNNr（xi）表示xi的r邻域；

3.2 基于自然邻的权重分配

下面文本根据上面提出的自然邻算法，对文本训练集中的数据进行训练，得到训练集中的每个文本向量的权重信息，使得有价值的文本向量具有较高的权重，而那些存在误差的文本向量具有较低的权重信息，这样对于后面测试文本的分类起到指导作用。

定义一：对于∀dj∈NaN_Edge（di），如果di与dj的类标记相同，则dj就是di好的自然邻居，好的自然邻居的个数为G_NaN（di）。

定义二：对于∀dj∈NaN_Edge（di），如果di与dj的类标记不相同，则dj就是di坏的自然邻居，坏的自然邻居的个数为B_NaN（di）。

定义三：dj的加权修正因子如下：

基于上述定义，基于自然邻的权重分类算法如下：

算法2基于自然邻的训练集加权算法

输入：训练文本向量D

输出：训练文本集的权重矩阵W

算法步骤：

Step1：∀di∈D，使用自然邻居算法得到NaN_Edge（di）

Step2：∀di∈D，遍历它的自然邻居，并根据上述定义计算出它的好的自然邻居数G_NaN（di）和坏的自然邻居数B_NaN（di）

Step3：根据上述定义三计算出di的权值w（di）

Step4：遍历完所有的训练集，完成计算，输出W

3.3 基于自然邻的文本分类

下面本文提出了基于自然邻的文本分类算法，对于每个文本测试集中的向量，根据上述算法1找到它的自然邻居，并结合算法2中训练文本向量的权重信息，计算出每个文本测试向量与每个类别的加权相似度之和，将其归类到相似度之和最大的类别中，具体算法步骤如下算法3所示。

算法3基于自然邻的文本分类算法

输入：训练文本向量D，测试文本向量T，训练文本向量集的权值矩阵W

输出：带有预测类别的测试集

算法步骤：

Step1：对每个测试文本向量，将其与训练文本向量D合并为数据集Z

Step2：根据前面的自然邻居算法，计算得到测试文本向量Ti的的自然邻居NaN_Edge（Ti）和自然邻居特征值λ和自然邻居个数NaN_Num（Ti）

Step3：如果上述NaN_Num（Ti）=0，我们重新定义NaN_Num（Ti）=λ

Step4：计算Ti到其所有自然邻居的余弦相似度

Step5：将上述得到的余弦相似度乘以对应的训练样本的权值矩阵W得到Ti与每个自然邻居的加权相似度

Step6：统计Ti与每个类别的加权相似度之和，并将其分类到权值相似度最大的类别中

Step7：重复上述步骤（1）到步骤（6），直到所有的测试样本都处理完

4 实验结果与分析

本文所使用的数据集为Newsgroups数据集，选择其中的10个类别，每个类别选择400个文本文件，总共4000个文件，其中3600作为训练集，400作为测试集。其原始文件如下：

表1 数据集

经数据预处理过后，对其进行特征提取，本文使用的是词频，为了不影响后面的分类精度，本文测试了不同词频下的文本特征数以及KNN文本分类算法的准确率，如下表2所示。

表2 不同特征KNN分类准确率

上述表中，词频项表示提取特征时使用的最小词频数，特征数表示大于等于此词频的总特征数，K值表示使用KNN算法时K的取值。

从上述表中我们的看到，随着词频的增加，特征数的减少，分类准确率整体先稳定后减少，随着K值的增大，分类准确率先增大，后趋于稳定，K值取40到60之间时，获取最高的准确率。当词频取5时，既充分减少了特征数，也能保留文本的绝大部分信息。所以，本文进行特征选择时，词频选择大于等于5，此时的特征数为11976，在使用KNN算法与自然邻做比较时，选择的K值为40到60。

根据上述的分析进行对比实验，使用十折交叉验证，对比KNN与自然邻的分类准确率和F1，其具体结果如下表3和表4所示。

表3 准确率对比

表4 F1值对比

根据上述表3和表4的对比结果，自然邻算法无论在分类准确率和F1值都比传统KNN算法的高，在准确率对比试验中，只有第二个类别（Comp.graphics）KNN算法比自然邻算法高，其他类别中都是自然邻算法的准确率较高，在F1值对比试验中，只有第二第三个类别中KNN算法比自然邻算法高，其他类别都是自然邻算法的F1值高。因此，实验很好地验证了自然邻算法在分类精度上的准确性。

5 结语

在KNN文本分类中，K值的确定是一个难题，而且KNN算法对数据集比较敏感，基于此本文提出了自然邻居的思想，很好地解决了上述两个难题，并且提高了分类准确率。然而对于KNN算法时间复杂度比较高的难题仍然存在，仍有待解决。

[1]汪明.数据挖掘综述[J].河北软件职业技术学院学报，2012，14（1）:45-48.

[2]J.Han，M.Kanber.数据挖掘-概念与技术.范明，孟小峰等译.北京：机械工业出版社，2001.

[3]湛燕.K近邻、K均值及其在文本分类中的应用.硕士学位论文.河北大学，2003.

[4]王继成，潘金贵，张福炎.Web文本挖掘技术研究.计算机研究与发展，2000，37（5）:513-520.

[5]王本年，高阳，陈世福等.Web智能研究现状与发展趋势.计算机研究与发展，2005，42（5）:721-727.

[6]侯汉清.分类法的发展趋势简论.北京:中国人民大学出版社，1981.

[7]张治平.Web信息精确获取技术研究.硕士学位论文,国防科学技术大学，2004.

[8]独立于语种的文本分类方法.2000 International Conference Multilingual Information Processing，2000:37-43.

[9]张海燕.基于分词的中文文本自动分类研究与实现.硕士学位论文.湖南大学，2002.

[10]刁倩，王永成，张惠惠等.VSM中词权重的信息嫡算法.情报学报，2000，19（4）:354-358.

[11]Y.Yang,J.Wilbur.Using Corpus Statistics to Remove Redundant Words in Text Categorization.Information Science,1996.

Application of Natural Neighbor in Text Classification

ZHU Qing-sheng，ZHANG Lang，ZHANG Cheng

（College of Computer Science，Chongqing University，Chongqing 400044）

In text classification,traditional KNN algorithm is affected by the uncertainty of K value and the unbalanced distribution of data sets.Proposes the idea of natural neighbor and applies it to text classification,which can overcome the disadvantages of KNN text classification. Firstly,the natural neighbor algorithm can automatically obtain the natural neighbor of the text vector according to the data set,and it is not necessary for human intervention.So it can solve the problem of uncertainty of K value.Secondly,for different data points,the number of neighbors may not be the same,it will automatically obtain their corresponding natural neighbors based on the distribution of the data set which can solve the problem of unbalanced distribution of data sets.In addition,according to the natural neighbor of the training set,designs a weight assignment algorithm,which makes the weight of the good neighbors larger and the weight of the bad neighbors smaller which improves the accuracy of the classification algorithm.

Text Classification;Natural Neighbor;KNN;Weight Assignment

1007-1423（2017）11-0042-05

10.3969/j.issn.1007-1423.2017.11.008

朱庆生（1957-），男，安徽当涂人，教授，博士，研究方向为面向服务的软件工程、离群检测、数据挖掘

2017-03-21

2017-04-10

重庆市研究生科研创新项目（No.CYS15029）、重庆市基础科学与前沿研究计划项目（No.cstc2013jcyjA40049）

张浪（1990-），男，江苏淮安人，硕士研究生，研究方向为机器学习、数据挖掘

张程（1977-），男，重庆人，副教授，博士，研究方向为移动智能、无线自组网络