基于改进哈希算法的快速KNN文本分类方法
摘要
网络的日益普及和人们对技术的日益依赖,使得数据越来越多的以电子的形式存储在计算机中。在当今高节奏社会,无论是在大型的企业数据中,还是在网络上,如何迅速有效的找到所需要的数据已经成为一个重要的话题。对此,国内外的专家提出了各种各样的技术,如数据库技术、关键词匹配技术和文本分类技术等。对文本进行分类能够有效的降低搜索感兴趣内容的时间,并且提高结果的准确率,在一定的程度上提高了用户的体验度。
常用的分类技术如贝叶斯分类技术、支持向量机分类法、决策树等需要大量的时间来训练分类器,如果更新训练用的语料库的话,需要重新训练文本分类器。传统中的KNN分类器的一大优点在于其能够在语料增加的情况下,不用重新训练分类器,同时分类准确率也比较高,因此一直很是受欢迎。但是,KNN算法也有其瓶颈：需要计算待分类文本与所有训练文本之间的相似度,这会浪费大量的时间。
本文提出了一种改进的KNN文本分类方法,根据具有最小方差的若干个特征建立相应的文本列表,搜索近邻文本时,先确定待分类文本的近邻文本在这些特征上的大致取值范围,从而依据哈希算法直接剔除掉绝大多数的文本,对于剩下的文本计算与待分类文本的相似度并找出最近邻的若干个,如果不满足K的要求,可以适当的扩展特征的取值范围直到满足为止。这种做法会极大的提高文本检索的速度。同时根据训练文本的类别与待分类文本的距离溢出率,对该类别中的文本与待分类文本之间的相似度进行适当的权重调整,从而提高分类的准确率。在筛选特征的时候,改进了传统的tf-idf算法,并且根据特征的词性、在句子中的成分、文章标题、摘要、所在段落的位置、所在句子的位置以及句子中的提示词对特征进行适当的权重调整。实验结果说明了这些做法能够非常有效的提高文本分类的准确性。
The growing popularity of the network and people become increasingly dependent on technology to make the data more and more in electronic form stored in the computer. In today's high-speed society, in large enterprise data or the network, how to quickly and efficiently find the needed data has become an important topic.So the domestic and foreign experts have proposed a variety of techniques, such as database technology, keyword matching and text classification technique.Text classification can effectively reduce the time of searching interesting content, and effectively improve the accuracy of search results and the user experience degrees to a certain extent.
The commonly used text classification techniques such as the bayesian classification technique, support vector machine classification,decision tree require a lot of time to train the classifiers, if the training texts are updated,they need re-train text classifiers. One of the big advantages of traditional KNN classifier is that if the training texts are increased, it doesn't have to re-train the classifier.The classification accuracy rate is relatively high, so it has been very popular. However, the KNN algorithm also has its bottleneck:it need computing the similarity with all the text in all the training text set and it will waste a lot of time.
This paper proposes an improved algorithm:establish some text list based on some of the features,compare features with feature of the text needed to be classified, and based on the results hash to the text subset that are most probably needed, and this algorithm will greatly improve the speed of text retrieval. Based on the overflow rate which is the quotient of the distance to the class and the text needed to classify, adjust the similarity between the texts of the class and the text needed to classify,and it obviously improves the accuracy of classification. Based on the improve the traditional tf-idf for algorithm,we select features of texts, and according to part-of-speech, sentence composition, the title of the article and summary, the location of the passage, the position of the sentence and the sentence prompt words,we adjust feature properly.The experimental result indicates that the practice can very effectively improve the accuracy of text classification.
常用的分类技术如贝叶斯分类技术、支持向量机分类法、决策树等需要大量的时间来训练分类器,如果更新训练用的语料库的话,需要重新训练文本分类器。传统中的KNN分类器的一大优点在于其能够在语料增加的情况下,不用重新训练分类器,同时分类准确率也比较高,因此一直很是受欢迎。但是,KNN算法也有其瓶颈：需要计算待分类文本与所有训练文本之间的相似度,这会浪费大量的时间。
本文提出了一种改进的KNN文本分类方法,根据具有最小方差的若干个特征建立相应的文本列表,搜索近邻文本时,先确定待分类文本的近邻文本在这些特征上的大致取值范围,从而依据哈希算法直接剔除掉绝大多数的文本,对于剩下的文本计算与待分类文本的相似度并找出最近邻的若干个,如果不满足K的要求,可以适当的扩展特征的取值范围直到满足为止。这种做法会极大的提高文本检索的速度。同时根据训练文本的类别与待分类文本的距离溢出率,对该类别中的文本与待分类文本之间的相似度进行适当的权重调整,从而提高分类的准确率。在筛选特征的时候,改进了传统的tf-idf算法,并且根据特征的词性、在句子中的成分、文章标题、摘要、所在段落的位置、所在句子的位置以及句子中的提示词对特征进行适当的权重调整。实验结果说明了这些做法能够非常有效的提高文本分类的准确性。
The growing popularity of the network and people become increasingly dependent on technology to make the data more and more in electronic form stored in the computer. In today's high-speed society, in large enterprise data or the network, how to quickly and efficiently find the needed data has become an important topic.So the domestic and foreign experts have proposed a variety of techniques, such as database technology, keyword matching and text classification technique.Text classification can effectively reduce the time of searching interesting content, and effectively improve the accuracy of search results and the user experience degrees to a certain extent.
The commonly used text classification techniques such as the bayesian classification technique, support vector machine classification,decision tree require a lot of time to train the classifiers, if the training texts are updated,they need re-train text classifiers. One of the big advantages of traditional KNN classifier is that if the training texts are increased, it doesn't have to re-train the classifier.The classification accuracy rate is relatively high, so it has been very popular. However, the KNN algorithm also has its bottleneck:it need computing the similarity with all the text in all the training text set and it will waste a lot of time.
This paper proposes an improved algorithm:establish some text list based on some of the features,compare features with feature of the text needed to be classified, and based on the results hash to the text subset that are most probably needed, and this algorithm will greatly improve the speed of text retrieval. Based on the overflow rate which is the quotient of the distance to the class and the text needed to classify, adjust the similarity between the texts of the class and the text needed to classify,and it obviously improves the accuracy of classification. Based on the improve the traditional tf-idf for algorithm,we select features of texts, and according to part-of-speech, sentence composition, the title of the article and summary, the location of the passage, the position of the sentence and the sentence prompt words,we adjust feature properly.The experimental result indicates that the practice can very effectively improve the accuracy of text classification.
引文
[1]M. E. Maron, J. L. Kuhn. On Relevance, Probabilistic Indexing and Information Retrieval[J]. J. ACM,1960,7(3):216-244.
[2]F. Rosenblatt. Principles of Neurodinamics:Perceptrion and Theory of Brain Mechanisms. Spartan Books[D],1962.
[3]G. Salton, A. Wong, C. S. Yang. A Vector Space Model for Automated Indexing Communications of the ACM[J],1975,18(1):613-620.
[4]T. Mitchell. Machine Learning[D]. Nuew York:McGraw-Hill,1997.
[5]李金钊.基于流形学习的中文web文本分类算法研究[D].河北工业大学,2010.
[6]赵秦怡等.一种可伸缩的空间决策树分类挖掘算法[J].计算机工程,2005(3)：6-11.
[7]牛罡等.半监督文本分类综述[D].计算机科学与探索,2011.
[8]宋睿.基于SVM的Web文档分类方法和应用研究[D].中国科学技术大学,2006
[9]曹文梁.一种新的网页自动分类预处理方法[J].科技广场,2008(7)：18-21.
[10]刘柏嵩.基于Web的通用本体学习研究[D].浙江大学,2007.
[11]潘湑等.采用改进重采样和BRF方法的定义抽取研究[J].中文信息学报,2011(5)：32-35.
[12]柯丽.基于频繁共现熵的跨语言网页自动分类研究[D].江西师范大学,2011.
[13]李萍.基于改进词语权重的文本分类方法研究[D].东北师范大学,2010.
[14]胡晓辉.基于团结构的文本分类技术研究[D].江西师范大学,2008.
[15]杨志豪.面向生物医学领域的文本挖掘技术研究[D].大连理工大学,2008.
[16]何峰等.改进的KNN文本分类算法综述[D].福建电脑,2005.
[17]孟晓倩.基于PCA与多视图学习的中文文本分类研究[D].河北大学,2010.
[18]梁吉业等.半监督学习研究进展[J].山西大学学报：自然科学版,2009(2)：18-22.
[19]王博.文本分类中特征选择技术的研究[D].国防科学技术大学,2009.
[20]连浩等.改进的基于布尔模型的网页查重算法[J].计算机应用研究, 2007(7)：46-48.
[21]金艳伟.基于马尔可夫随机场的蒙古文信息检索模型研究[D].内蒙古大学,2011.
[22]霍仁崇等.基于Web的法律咨询系统的设计与实现[J].计算机光盘软件与应用,2011(4)：15-17.
[23]熊佳树.基于NUTCH的中文新闻事件自动分类系统研究[D].武汉理工大学,2011.
[24]岳涛汉语自动分词技术的最新发展及其在信息检索中的应用[J].情报杂志,2005(4)：16-18.
[25]黄聃.基于语义提取与分类的Web服务匹配方法[D].东南大学,2010.
[26]化柏林.知识抽取中的停用词处理技术[J].现代图书情报技术,2007(8)：15-18.
[27]刘海峰等.一种基于类别信息的改进文本特征选择[J].计算机应用与软件,2010(6)：41-43.
[28]刘丽珍等.文本分类中的特征选取[J].计算机工程,2004(4)：36-38.
[29]杨震.个性化信息获取方法的研究[D].大连理工大学,2004.
[30]沙朝锋.基于信息论的数据挖掘算法[D].复旦大学,2008.
[31]张凤.多值关联规则挖掘算法的研究[D].西安科技大学,2010.
[32]邓彩凤.中文文本分类中互信息特征选择方法研究[D].西南大学,2011.
[33]李晨.网络搜索引擎与专家检索系统框架和模型研究[D].北京邮电大学,2009.
[34]宋文贺.基于文本相似度的论文查重方法研究[D].南开大学,2009.
[35]曾一平.中文文本情感分类的研究[D].北京交通大学,2011.
[36]周城.面向中文Web评论的情感分析技术研究[D].国防科学技术大学,2011.
[37]代向敏.中国教育不平等现状的实证分析[D].东北财经大学,2007.
[38]王金花.一种利用本体关联度改进的TF-IDF特征词提取方法[D].河北大学,2011.
[39]胡文静.文本分类技术进展[D].知识经济,2011(10)：47-50.
[40]贺爱香.决策树在应用型本科高校就业管理中的应用研究[D].安徽大学, 2011.
[41]刘林.基于词语权重改进的朴素贝叶斯分类算法的研究与应用[D].中山大学,2009.
[42]高艳影.中文问答系统中的问题分类研究[D].合肥工业大学,2011.
[43]吴巧敏.基于支持向量机的文本分类算法研究[D].湖南大学,2007.
[44]杨显飞.基于边界向量预选的支持向量机算法研究[D].哈尔滨工程大学,2008.
[45]李旻.基于综合特征空间的Blog网页识别方法研究[D].河南大学,2009.
[46]鲁婷.K-近邻中文文本分类方法的研究[D].合肥工业大学,2010
[47]江慧娜.中文搜索引擎的关键技术研究[D].北京化工大学,2007.
[48]刘伟.基于限定领域的问句相似度[D].天津师范大学,2008.
[49]周舫.汉语句子相似度计算方法及其应用的研究[D].河南大学,2005.
[50]柳燕妮.副词的分类与释义分析——《现代汉语词典》副词的对比研究[D].西北师范大学,2007.
[51]匡鹏飞.时间词语前后分句共现状态之研究[D].华中师范大学,2006.
[52]陈海波.基于自动分词的企业文档搜索引擎设计与实现[D].西北工业大学,2007.
[2]F. Rosenblatt. Principles of Neurodinamics:Perceptrion and Theory of Brain Mechanisms. Spartan Books[D],1962.
[3]G. Salton, A. Wong, C. S. Yang. A Vector Space Model for Automated Indexing Communications of the ACM[J],1975,18(1):613-620.
[4]T. Mitchell. Machine Learning[D]. Nuew York:McGraw-Hill,1997.
[5]李金钊.基于流形学习的中文web文本分类算法研究[D].河北工业大学,2010.
[6]赵秦怡等.一种可伸缩的空间决策树分类挖掘算法[J].计算机工程,2005(3)：6-11.
[7]牛罡等.半监督文本分类综述[D].计算机科学与探索,2011.
[8]宋睿.基于SVM的Web文档分类方法和应用研究[D].中国科学技术大学,2006
[9]曹文梁.一种新的网页自动分类预处理方法[J].科技广场,2008(7)：18-21.
[10]刘柏嵩.基于Web的通用本体学习研究[D].浙江大学,2007.
[11]潘湑等.采用改进重采样和BRF方法的定义抽取研究[J].中文信息学报,2011(5)：32-35.
[12]柯丽.基于频繁共现熵的跨语言网页自动分类研究[D].江西师范大学,2011.
[13]李萍.基于改进词语权重的文本分类方法研究[D].东北师范大学,2010.
[14]胡晓辉.基于团结构的文本分类技术研究[D].江西师范大学,2008.
[15]杨志豪.面向生物医学领域的文本挖掘技术研究[D].大连理工大学,2008.
[16]何峰等.改进的KNN文本分类算法综述[D].福建电脑,2005.
[17]孟晓倩.基于PCA与多视图学习的中文文本分类研究[D].河北大学,2010.
[18]梁吉业等.半监督学习研究进展[J].山西大学学报：自然科学版,2009(2)：18-22.
[19]王博.文本分类中特征选择技术的研究[D].国防科学技术大学,2009.
[20]连浩等.改进的基于布尔模型的网页查重算法[J].计算机应用研究, 2007(7)：46-48.
[21]金艳伟.基于马尔可夫随机场的蒙古文信息检索模型研究[D].内蒙古大学,2011.
[22]霍仁崇等.基于Web的法律咨询系统的设计与实现[J].计算机光盘软件与应用,2011(4)：15-17.
[23]熊佳树.基于NUTCH的中文新闻事件自动分类系统研究[D].武汉理工大学,2011.
[24]岳涛汉语自动分词技术的最新发展及其在信息检索中的应用[J].情报杂志,2005(4)：16-18.
[25]黄聃.基于语义提取与分类的Web服务匹配方法[D].东南大学,2010.
[26]化柏林.知识抽取中的停用词处理技术[J].现代图书情报技术,2007(8)：15-18.
[27]刘海峰等.一种基于类别信息的改进文本特征选择[J].计算机应用与软件,2010(6)：41-43.
[28]刘丽珍等.文本分类中的特征选取[J].计算机工程,2004(4)：36-38.
[29]杨震.个性化信息获取方法的研究[D].大连理工大学,2004.
[30]沙朝锋.基于信息论的数据挖掘算法[D].复旦大学,2008.
[31]张凤.多值关联规则挖掘算法的研究[D].西安科技大学,2010.
[32]邓彩凤.中文文本分类中互信息特征选择方法研究[D].西南大学,2011.
[33]李晨.网络搜索引擎与专家检索系统框架和模型研究[D].北京邮电大学,2009.
[34]宋文贺.基于文本相似度的论文查重方法研究[D].南开大学,2009.
[35]曾一平.中文文本情感分类的研究[D].北京交通大学,2011.
[36]周城.面向中文Web评论的情感分析技术研究[D].国防科学技术大学,2011.
[37]代向敏.中国教育不平等现状的实证分析[D].东北财经大学,2007.
[38]王金花.一种利用本体关联度改进的TF-IDF特征词提取方法[D].河北大学,2011.
[39]胡文静.文本分类技术进展[D].知识经济,2011(10)：47-50.
[40]贺爱香.决策树在应用型本科高校就业管理中的应用研究[D].安徽大学, 2011.
[41]刘林.基于词语权重改进的朴素贝叶斯分类算法的研究与应用[D].中山大学,2009.
[42]高艳影.中文问答系统中的问题分类研究[D].合肥工业大学,2011.
[43]吴巧敏.基于支持向量机的文本分类算法研究[D].湖南大学,2007.
[44]杨显飞.基于边界向量预选的支持向量机算法研究[D].哈尔滨工程大学,2008.
[45]李旻.基于综合特征空间的Blog网页识别方法研究[D].河南大学,2009.
[46]鲁婷.K-近邻中文文本分类方法的研究[D].合肥工业大学,2010
[47]江慧娜.中文搜索引擎的关键技术研究[D].北京化工大学,2007.
[48]刘伟.基于限定领域的问句相似度[D].天津师范大学,2008.
[49]周舫.汉语句子相似度计算方法及其应用的研究[D].河南大学,2005.
[50]柳燕妮.副词的分类与释义分析——《现代汉语词典》副词的对比研究[D].西北师范大学,2007.
[51]匡鹏飞.时间词语前后分句共现状态之研究[D].华中师范大学,2006.
[52]陈海波.基于自动分词的企业文档搜索引擎设计与实现[D].西北工业大学,2007.