第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201711007 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180423.1540.016.html 基于支持向量的最近邻文本分类方法 古丽娜孜·艾力木江23，乎西旦·居马洪，孙铁利2，梁义 (1.伊犁师范学院电子与信息工程学院，新疆伊宁835000,2.东北师范大学计算机科学与技术学院，吉林长 春130117：3.东北师范大学地理科学学院，吉林长春130024) 摘要：文本分类为一个文档自动分配一组预定义的类别或主题。文本分类中，文档的表示对学习机的学习性 能有很大的影响。以实现哈萨克语文本分类为目的，根据哈萨克语语法规则设计实现哈萨克语文本的词干提 取，完成哈萨克语文本的预处理。提出基于最近支持向量机的样本距离公式，避免k参数的选定，以SVM与 KNN分类算法的特殊组合算法(SV-NN)实现了哈萨克语文本的分类。结合自己构建的哈萨克语文本语料库 的语料进行文本分类仿真实验，数值实验展示了提出算法的有效性并证实了理论结果。 关键词：词干提取；预处理：支持向量机：文本分类：分类精度 中图分类号：TP309文献标志码：A文章编号：1673-4785(2018)05-0799-09 中文引用格式：古丽娜孜·艾力木江，乎西旦·居马洪，孙铁利，等.基于支持向量的最近邻文本分类方法.智能系统学报， 2018,13(5):799-807. 英文引用格式：GULNAZ Alimjan,HURXIDA Jumahun,SUN Tieli,etal.The nearest neighbor text classification method based on support vector[J.CAAI transactions on intelligent systems,2018,13(5):799-807. The nearest neighbor text classification method based on support vector GULNAZ Alimjan2,HURXIDA Jumahun',SUN Tieli,LIANG Yi' (1.Department of Electronics and Information Engineering,Yili Normal University,Yining 835000,China;2.School of Information Science and Technology,Northeast Normal University,Changchun 130117,China;3.Department of Geographical Science,North- east Normal University,Changchun 130024,China) Abstract:Text categorization automatically assigns a set of predefined categories or topics to a document.In text classi- fication,the representation of the document has a great influence on the learning performance of the learning machine. The aim is to achieve Kazakh text classification,according to Kazakh grammar rules,the stemming of Kazakh texts is designed to complete the preprocessing of Kazakh text.A sample distance formula based on the latest support vector machine(SVM)is proposed to avoid the selection of k-parameters.The Kazakh texts are classified by special combina- tion of SVM and KNN classification algorithms (SV-NN).Combining the corpus of Kazakh text corpora constructed by himself,text categorization simulation experiments were conducted.Numerical experiments showed the effectiveness of the proposed algorithm and confirmed the theoretical results. Keywords:stemming;preprocessing;support vector machines,text categorization,classification accuracy 文本分类(text classification,.TC)是对一个文本数据组织与处理的关键技术。数字化数据有不 档自动分配一组预定义的类别或应用主题的过 同的形式，它可以是文字、图像、空间形式等，其 程"。随着数字图书馆的快速增长，TC已成为文 中最常见和应用最多的是文本数据，阅读的新 收稿日期：2017-11-02.网络出版日期：2018-04-24. 闻、社交媒体上的帖子和信息主要以文本形式出 基金项目：伊犁师范学院一般项目(2016WXYB0004):国家自然 科学基金项目(61663045)：新疆高校科研计划重点 现。文本自动分类在网站分类2-)、自动索引 研究项目(XEDU2014I043):伊犁师范学院重点项 目(2016YSZD04). 电子邮件过滤6、垃圾邮件过滤？1、本体匹配 通信作者：古丽娜孜艾力木江.E-mail:alay328@163.com. 超文本分类2和情感分析1等许多信息检索
DOI: 10.11992/tis.201711007 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180423.1540.016.html 基于支持向量的最近邻文本分类方法 古丽娜孜·艾力木江1,2,3，乎西旦·居马洪1 ，孙铁利2 ，梁义1 （1. 伊犁师范学院 电子与信息工程学院，新疆 伊宁 835000; 2. 东北师范大学 计算机科学与技术学院，吉林 长 春 130117; 3. 东北师范大学 地理科学学院，吉林 长春 130024） 摘 要：文本分类为一个文档自动分配一组预定义的类别或主题。文本分类中，文档的表示对学习机的学习性 能有很大的影响。以实现哈萨克语文本分类为目的，根据哈萨克语语法规则设计实现哈萨克语文本的词干提 取，完成哈萨克语文本的预处理。提出基于最近支持向量机的样本距离公式，避免 k 参数的选定，以 SVM 与 KNN 分类算法的特殊组合算法（SV-NN）实现了哈萨克语文本的分类。结合自己构建的哈萨克语文本语料库 的语料进行文本分类仿真实验，数值实验展示了提出算法的有效性并证实了理论结果。 关键词：词干提取；预处理；支持向量机；文本分类；分类精度 中图分类号：TP309 文献标志码：A 文章编号：1673−4785(2018)05−0799−09 中文引用格式：古丽娜孜·艾力木江, 乎西旦·居马洪, 孙铁利, 等. 基于支持向量的最近邻文本分类方法[J]. 智能系统学报, 2018, 13(5): 799–807. 英文引用格式：GULNAZ Alimjan, HURXIDA Jumahun, SUN Tieli, et al. The nearest neighbor text classification method based on support vector[J]. CAAI transactions on intelligent systems, 2018, 13(5): 799–807. The nearest neighbor text classification method based on support vector GULNAZ Alimjan1,2,3 ，HURXIDA Jumahun1 ，SUN Tieli2 ，LIANG Yi1 (1. Department of Electronics and Information Engineering, Yili Normal University, Yining 835000, China; 2. School of Information Science and Technology, Northeast Normal University, Changchun 130117, China; 3. Department of Geographical Science, Northeast Normal University, Changchun 130024, China) Abstract: Text categorization automatically assigns a set of predefined categories or topics to a document. In text classification, the representation of the document has a great influence on the learning performance of the learning machine. The aim is to achieve Kazakh text classification, according to Kazakh grammar rules, the stemming of Kazakh texts is designed to complete the preprocessing of Kazakh text. A sample distance formula based on the latest support vector machine (SVM) is proposed to avoid the selection of k-parameters. The Kazakh texts are classified by special combination of SVM and KNN classification algorithms (SV-NN) . Combining the corpus of Kazakh text corpora constructed by himself, text categorization simulation experiments were conducted. Numerical experiments showed the effectiveness of the proposed algorithm and confirmed the theoretical results. Keywords: stemming; preprocessing; support vector machines; text categorization; classification accuracy 文本分类 (text classification，TC) 是对一个文 档自动分配一组预定义的类别或应用主题的过 程 [1]。随着数字图书馆的快速增长，TC 已成为文 本数据组织与处理的关键技术。数字化数据有不 同的形式，它可以是文字、图像、空间形式等，其 中最常见和应用最多的是文本数据，阅读的新 闻、社交媒体上的帖子和信息主要以文本形式出 现。文本自动分类在网站分类[2-3] 、自动索引[4-5] 、 电子邮件过滤[6] 、垃圾邮件过滤[7-9] 、本体匹配[10] 、 超文本分类[11-12]和情感分析[13-14]等许多信息检索 收稿日期：2017−11−02. 网络出版日期：2018−04−24. 基金项目：伊犁师范学院一般项目 (2016WXYB0004)；国家自然 科学基金项目 (61663045)；新疆高校科研计划重点 研究项目 (XJEDU2014I043)；伊犁师范学院重点项 目 (2016YSZD04). 通信作者：古丽娜孜·艾力木江. E-mail：alay328@163.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·800· 智能系统学报 第13卷 应用中起到了重要的作用。数字化时代，在线文 1文本特征提取 本文档及其类别的数量越来越巨大，而TC是从 数据海洋当中挖掘出具有参考价值数据的应用程 1.1文本预处理 序s。文本挖掘工作是政府工作、科学研究、办 文本预处理在整个文本分类工作中扮演着最 公业务等许多应用领域里书面文本的分析过程。 重要的角色，其处理程度直接影响到文本分类精 朴素贝叶斯、k近邻、支持向量机、决策树、最大 度。因为它是从文档中抽取关键词集合的过程， 嫡和神经网络等基于统计与监督的模式分类算法 而关键词的单独抽取因语言语法规则的不同而不 在文本分类研究中已被广泛应用。提高文本分类 同，所以这层工作属于技术含量较高的基础性工 效率的算法研究对web数据的开发应用具有重要 作，需要设计人员熟练掌握语言语法规则和计算 意义。 机编程能力。目前存在一个现实问题，即包括作 合理的词干有助于提高文本分类的性能和效 者在内的很多编程人员因研究工作的需要一般从 率1，特别是对于哈萨克语这样的构词和词性 事于中英文文字资料上的研究，所以对母语（哈 变化较复杂语言的文本分类而言，词干的准确提 萨克语)语法规则的细节不精通，对从小开始在 取极其重要。从同一个词干可以派生出许多单 汉语授课学校上学的编程人员情况则更严重，所 词，因此通过词干提取还可以对语料库规模进行 以要实现词干解析需要向语言学专家或相关人员 降维。文本文档数量的巨大化和包含特征的多样 全面请教，这也是影响哈萨克语文本分类工作进 化，给文本挖掘工作带来一定的困难。目前，众 展的一个客观问题。 多文本分类研究都是基于英文或中文，基于少数 哈萨克语文字由24个辅音字母和9个元音 民族语言的文本分类研究相对较少叨：但是国外 字母的共有33个字母组成。因为哈萨克语语法 对于阿拉伯语的文本分类工作比中国少数民族语 形式是在单词原形前后附加一定附加成分来完成 言文本分类工作成熟-刘，投入研究的人员也较多。 的，所以哈萨克语言属于黏着语，即跟英文类似 哈萨克语言属于阿尔泰语系突厥语族的克普 一个哈萨克语单词对应多种链接形式，因此对其 恰克语支，中国境内通用的哈萨克文借用了阿拉 一定要进行词干提取。 伯语和部分波斯文字母，而哈萨克斯坦等国家用 本文前期系列研究工作基本完成了哈萨克语 的哈萨克文是斯拉夫文字。哈萨克文本跟中文不 文本词干提取以及词性标注工作，已完成哈萨克 同的一点是哈萨克文文本单词以空格分开的，这 语文本词干表的构建。该词干表收录了如图1所 点类似于英文，都需要文本词干提取过程。由于 示的由新疆人民出版社出版的《哈萨克语详解词 哈萨克语与英语语法体系不一样，英文词干提取 典》中的60000多个哈萨克语文本词干和如图2 规则还不能直接用到哈萨克语文本分类问题上， 所示的438个哈萨克语文本词干附加成分。 要研究适合哈萨克语语法体系的词干提取规则之 word pos 后才能实现哈萨克语文本的分类工作。哈萨克语 025 具有丰富的形态和复杂的拼字法，因此哈萨克语 29 adj 文本分类系统的实现是有难度的。为了实现文本 3 n 分类任务需要一定规模的语料库，语料库里语料 4 59 的质量直接影响文本分类的精度。到目前为止在 6业 va 哈萨克语中还没有一个公认的哈萨克文语料库， 当然，也有不少人认为新疆人民日报（哈文版）上 图1 哈萨克语词干 Fig.1 Kazakh text stem 的文本可以当作文本分类语料库。本文为了保证 文本分类语料库的规范化和文本分类工作的标准 index type suffix btype 化，经过认真挑选中文标准语料库里的部分语料 215ad d ge 文档并对其进行翻译和新疆人民日报上的部分文 201ad 月 gc 档来自行搭建了本研究的语料库。本文在对前期 228ad u gc 研究里词干提取程序词干解析规则222进行优化 227ad gc 改善的基础上实现本研究的文本预处理，提出新 226ad gc 的样本测度指标与距离公式，并结合SVM与 图2哈萨克语附加成分 KNN分类算法实现了哈萨克语文本分类。 Fig.2 Additional components in Kazakh text
应用中起到了重要的作用。数字化时代，在线文 本文档及其类别的数量越来越巨大，而 TC 是从 数据海洋当中挖掘出具有参考价值数据的应用程 序 [15-16]。文本挖掘工作是政府工作、科学研究、办 公业务等许多应用领域里书面文本的分析过程。 朴素贝叶斯、k 近邻、支持向量机、决策树、最大 熵和神经网络等基于统计与监督的模式分类算法 在文本分类研究中已被广泛应用。提高文本分类 效率的算法研究对 web 数据的开发应用具有重要 意义。 合理的词干有助于提高文本分类的性能和效 率 [17-18] ，特别是对于哈萨克语这样的构词和词性 变化较复杂语言的文本分类而言，词干的准确提 取极其重要。从同一个词干可以派生出许多单 词，因此通过词干提取还可以对语料库规模进行 降维。文本文档数量的巨大化和包含特征的多样 化，给文本挖掘工作带来一定的困难。目前，众 多文本分类研究都是基于英文或中文，基于少数 民族语言的文本分类研究相对较少[19] ；但是国外 对于阿拉伯语的文本分类工作比中国少数民族语 言文本分类工作成熟[20–21] ，投入研究的人员也较多。 哈萨克语言属于阿尔泰语系突厥语族的克普 恰克语支，中国境内通用的哈萨克文借用了阿拉 伯语和部分波斯文字母，而哈萨克斯坦等国家用 的哈萨克文是斯拉夫文字。哈萨克文本跟中文不 同的一点是哈萨克文文本单词以空格分开的，这 点类似于英文，都需要文本词干提取过程。由于 哈萨克语与英语语法体系不一样，英文词干提取 规则还不能直接用到哈萨克语文本分类问题上， 要研究适合哈萨克语语法体系的词干提取规则之 后才能实现哈萨克语文本的分类工作。哈萨克语 具有丰富的形态和复杂的拼字法，因此哈萨克语 文本分类系统的实现是有难度的。为了实现文本 分类任务需要一定规模的语料库，语料库里语料 的质量直接影响文本分类的精度。到目前为止在 哈萨克语中还没有一个公认的哈萨克文语料库， 当然，也有不少人认为新疆人民日报 (哈文版) 上 的文本可以当作文本分类语料库。本文为了保证 文本分类语料库的规范化和文本分类工作的标准 化，经过认真挑选中文标准语料库里的部分语料 文档并对其进行翻译和新疆人民日报上的部分文 档来自行搭建了本研究的语料库。本文在对前期 研究里词干提取程序词干解析规则[22-24]进行优化 改善的基础上实现本研究的文本预处理，提出新 的样本测度指标与距离公式，并结合 SVM 与 KNN 分类算法实现了哈萨克语文本分类。 1 文本特征提取 1.1 文本预处理 文本预处理在整个文本分类工作中扮演着最 重要的角色，其处理程度直接影响到文本分类精 度。因为它是从文档中抽取关键词集合的过程， 而关键词的单独抽取因语言语法规则的不同而不 同，所以这层工作属于技术含量较高的基础性工 作，需要设计人员熟练掌握语言语法规则和计算 机编程能力。目前存在一个现实问题，即包括作 者在内的很多编程人员因研究工作的需要一般从 事于中英文文字资料上的研究，所以对母语 (哈 萨克语) 语法规则的细节不精通，对从小开始在 汉语授课学校上学的编程人员情况则更严重，所 以要实现词干解析需要向语言学专家或相关人员 全面请教，这也是影响哈萨克语文本分类工作进 展的一个客观问题。 哈萨克语文字由 24 个辅音字母和 9 个元音 字母的共有 33 个字母组成。因为哈萨克语语法 形式是在单词原形前后附加一定附加成分来完成 的，所以哈萨克语言属于黏着语，即跟英文类似 一个哈萨克语单词对应多种链接形式，因此对其 一定要进行词干提取。 本文前期系列研究工作基本完成了哈萨克语 文本词干提取以及词性标注工作，已完成哈萨克 语文本词干表的构建。该词干表收录了如图 1 所 示的由新疆人民出版社出版的《哈萨克语详解词 典》中的 60 000 多个哈萨克语文本词干和如图 2 所示的 438 个哈萨克语文本词干附加成分。 图 1 哈萨克语词干 Fig. 1 Kazakh text stem 图 2 哈萨克语附加成分 Fig. 2 Additional components in Kazakh text ·800· 智 能 系 统 学 报 第 13 卷
第5期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·801· 本文在前期准备研究工作的基础上，给出 (如体育类文档中)每一个单词（如“排球”）的总出 3种词性的有限状态自动机，并采用词法分析和 现次数。图5所示的是词的权重计算结果，即统 双向全切分相结合的改进方法实现哈萨克语文本 计某词在判别文档类别所属关系中的隶属度，当 词干的提取与单词构形附加成分的细切分。以改 然隶属度越高说明该词在文档分类时的贡献越 进的逐字母二分词典查询机制对词干表进行搜 大。最后把文档由如图6所示的形式向量化表 索，提高词干提取的效率。以概率统计的方法对 示，生成分类问题的文档向量，即“X号特征词： 歧义词和未记载词进行切分。在此研究基础上， 该特征词的特征向量”形式向量化表示。 设计实现了哈萨克语文本的词法自动分析程序， 完成哈萨克语文本的读取预处理。处理结果如 图3所示，上半窗体上显示的是待切分的文档原 体 记 文，下半窗体上显示是词干切分后的结果。 85一 93U 11 工收的一记事本 12.11 E 5▣图 45? 23 s55 11 8 L 3 3 11 3 1 1 L5eu4d山1000-11 2 d4←-护-uj5-心w。 355 1 1 B I5 2 3 1 j 1 d1641h1114日.号+14144出月 -11一华”-y-0% 图4词频统计结果 Fig.4 Term frequency statistical result 5小1000 5=护-urJ5 归一一3步-如山异 a..心4一地2，心 0.0131578947368421y 开主可子 0.013157B947368421L 0.0131578947368421 5 0.024390243902439-1L- 图3哈萨克语文本词干切分结果示例 0.0131578947368421 003658536585365855:9- Fig.3 Example segmentation results of the Kazakh text 0.0131578947368421:5 0.0365853658536585,为 0.0131578947368421 stem 0.024390243902439LlL 0.02631578947368425 0 0.02439024390243914 0.0131578947368421 D.024390243902439 0.0 1.2特征处理 0.0263157894736842.=2 .0 0.0394736842105263 特征是文本分类时判别类别的尺度。模式识 0.02631578917368422 0.013157B947368421 0.0072463768115942过L 别的不同分类问题有不同的特征选择方法，而在 0.0263157894736842 0.0072463768115942- 文本分类问题中常用到的方法有互信息(MⅫ、X 0.0072463768115942-44 统计量(CH)、信息增益(IG)、文档频率(DF)、卡 图5词权重计算结果 方统计等21。这些方法各具优点和不足之处。 Fig.5 Term weight computed result M、IG和CHI倾向于低频词的处理，而DF则倾 固回图 向于高频词的处理。目前，也有许多优化改进方 文件巴国特试教看四的 14:0.01220391874313445:0.04881567497253766:0.04031567497253767:01 法26-2，其中文本频率比值法(document frequency 0057563342198956851:0.012203918743134452:0.012203918743134453:0. 9194499:0.903089986991944100:0.602059991327962101:0.9030899869919 ratio,DFR)以简单、快捷等优点克服了以上几种 03089986991944146:0.90308998699194H147:0.301029995663981148:0.301 44192:0.903089986991944193:0.,903089986991944194:0.602059991327962 方法存在的问题，综合考虑了类内外文本频率， 089986991944239:0.903089986991944240:0.903089986991944241:0.90308 285:0.903089986991944286:0.903089986991944287:0.90308998699194428 其计算公式为 986991944332:0.903089986991944333:0.90308998699194H334:0.90308998 DFR(,C)=(W-mz)xDF 8:0.903089986991944379:0.903089986991944380:0.903089986991944381: (1) 14:0.01220391874313445:0.0481567497253766:0.04期1567497253767：0.4 nix DF: 2687504.53254662983912E-0551:0.012203918743134452:0.0122039187 89558928395:0.0071109447794641396:0.0067081690121619197:0.007110 式中，对于词t,N是训练文本数，n,是C,类别 77946413138:0.00711094477946413139:0.00711094477946413140:0.00 中的文本数，DF,是C,类别中包含词1的文本数， 而D显然是除了C类以外的别的类别中包含词 图6文本向量文件 Fig.6 Text vector files t的文本数。 通过词频统计、词权重计算和文档向量化表 2SVM与KNN方法 示等一系列的预处理工作之后才能运用分类算 法，所以对文本分类工作而言这些都是非常重要 2.1SVM方法 的阶段性基础工作。图4所示的是每类文档里 支持向量机(support vector machine,SVM)是
本文在前期准备研究工作的基础上，给出 3 种词性的有限状态自动机，并采用词法分析和 双向全切分相结合的改进方法实现哈萨克语文本 词干的提取与单词构形附加成分的细切分。以改 进的逐字母二分词典查询机制对词干表进行搜 索，提高词干提取的效率。以概率统计的方法对 歧义词和未记载词进行切分。在此研究基础上， 设计实现了哈萨克语文本的词法自动分析程序， 完成哈萨克语文本的读取预处理。处理结果如 图 3 所示，上半窗体上显示的是待切分的文档原 文，下半窗体上显示是词干切分后的结果。 图 3 哈萨克语文本词干切分结果示例 Fig. 3 Example segmentation results of the Kazakh text stem 1.2 特征处理 特征是文本分类时判别类别的尺度。模式识 别的不同分类问题有不同的特征选择方法，而在 文本分类问题中常用到的方法有互信息 (MI)、X 2 统计量 (CHI)、信息增益 (IG)、文档频率 (DF)、卡 方统计等[ 2 5 ]。这些方法各具优点和不足之处。 MI、IG 和 CHI 倾向于低频词的处理，而 DF 则倾 向于高频词的处理。目前，也有许多优化改进方 法 [26-28] ，其中文本频率比值法 (document frequency ratio，DFR) 以简单、快捷等优点克服了以上几种 方法存在的问题，综合考虑了类内外文本频率， 其计算公式为 DFR(t,Ci) = (N −ni)×DFi ni ×DF′ i (1) DFi ′ 式中，对于词 t，N 是训练文本数，ni 是 Ci 类别 中的文本数，DFi 是 Ci 类别中包含词 t 的文本数， 而 显然是除了 Ci 类以外的别的类别中包含词 t 的文本数。 通过词频统计、词权重计算和文档向量化表 示等一系列的预处理工作之后才能运用分类算 法，所以对文本分类工作而言这些都是非常重要 的阶段性基础工作。图 4 所示的是每类文档里 (如体育类文档中) 每一个单词 (如“排球”) 的总出 现次数。图 5 所示的是词的权重计算结果，即统 计某词在判别文档类别所属关系中的隶属度，当 然隶属度越高说明该词在文档分类时的贡献越 大。最后把文档由如图 6 所示的形式向量化表 示，生成分类问题的文档向量，即“X 号特征词： 该特征词的特征向量”形式向量化表示。 图 4 词频统计结果 Fig. 4 Term frequency statistical result 图 5 词权重计算结果 Fig. 5 Term weight computed result 图 6 文本向量文件 Fig. 6 Text vector files 2 SVM 与 KNN 方法 2.1 SVM 方法 支持向量机 (support vector machine，SVM) 是 第 5 期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·801·
·802· 智能系统学报 第13卷 在1995年由Cortes和Vapnik首次提出来的一种 分界面的法向量w只受支持向量的影响，不受非 模式识别分类技术2。SVM是在统计学习理论 支持向量训练点的影响。 (statistical learning theory,SLT)原理的基础上发展 2)非线性可分 起来的机器学习算法。SVM方法的重点在于在 SVM通过运用合适的非线性映射，如 高维特征空间中能构造函数集VC维尽可能小的 P:x→(x)把分类问题原训练样本点转变（映 最优分类面，使得不同类别样本在这分类面上分 射)到新的地方（新特征空间），使得原样本在这新 类上界最小化，从而保证分类算法的最优推广能 特征空间（目标高维空间）中能够线性可分，然后 力。图7所示的是SVM方法的分类原理示意 在这新的映射空间中利用线性可分问题求解原理 图。SVM在有限训练样本情况下，在学习机复杂 求出最终的最优分类面。 度和学习机泛化能力之间找到一个平衡点，从而 为此，需要在式(3)中增加一个松弛变量：和 保证学习机的推广能力0。 惩罚因子C,从而式(3)变为 最优超平面 wx+b=0 min(,)= f+e2s,uyl+-l+6>0 00 (5) 2 分类间隔= 式中：≥0；i=1,2,,n;C为控制样本对错分的 分离超平面 调整因子，通常称为惩罚因子。C越大，惩罚越重。 0● 虽然原理看起来简单，然而在分类问题的训 练样本不充足或不能保证训练样本质量的情形下 支持向量 ●类别1 确定非线性映射是很困难的，那么如何确定非线 :分类错误 O类别2 性映射呢？SVM通过运用核函数概念解决这个 图7SVM分类原理示意图 问题，核函数是SVM的其他分类算法无法替代 Fig.7 SVM classification schematic diagram 的独特功能。 根据样本分布情况与样本集维数，SVM算法 SVM通过引入一个核函数K(x,x),将原低维 的判别函数原理大致可分为线性可分与非线性可 的分类问题空间映射到高维的新问题空间中，使 分两种形式。 核函数代替ω()内积运算，这个高维空间就称 1)线性可分 为Hilbert空间。引入核函数以后的最优分类函数为 带有以式(2)所示训练样本集的SVM线性可 f (x)=sign ay.K(xx+b (6) 分分类问题的数学模型可通过式(3)来表示： S={(xy),i=1,2,…,ri,xeR,ye+1,-1}(2) 2.2KNN方法 KNN(K nearest neighbor)分类法是基于实例 minp(w）=lwl,s.ty.[ox+-1≥0，i=1,2…n 的学习算法，它需要所有的训练样本都参与分 (3) 假如，对n维空间中的分类界面为wx+b=0, 类。在分类阶段，利用欧氏距离公式，将每个测 试样本与和它邻近的k个训练样本进行比较，然 使得与此分类界面最近的两类样本之间的距离 后将测试样本归属到票数最多的那一类里。 之最大，即为最小，则该分类界面就称为最优 lll KNN算法是根据测试样本最近的k个样本点的 分类界面；ω为权重向量（是x)的法向量），b为函 类别信息来对该测试样本类型进行判别，所以 数阈值。从而最终可得到所求的最优分类函数为 k值的选取非常重要。k值若太小，测试样本特征 f(x)=sign (4) 不能充分体现；k值若太大，与测试样本并不相似 的个别样本也可能被包含进来，这样反而对分类 式中对应a,0时的样本点就是支持向量。因为 不利。KNN算法在分类决策上只凭k个最邻近 最优化问题解a,的每一个分量都与一个训练点 样本类别确定待分样本的所属类。目前，对于 相对应，显然所求得的划分超平面仅仅与对应 k值的选取还没有一个全局最优的筛选方法，这 a,0时的那些训练点(c,x)相关，而跟a=O时的那 也是KNN方法的弊端，具体操作时，根据先验知 些训练点没有任何关系。相应于a0时的训练 识先给出一个初始值，然后需要根据仿真分类实 点(：x)里的输入点x就是支持向量，通常它们是 验结果重新调整，调整k值的操作有时一直到分 全体样本中的很少一部分。得出结论，最终分类 类结果满足用户需求为止。该方法原理可由式
在 1995 年由 Cortes 和 Vapnik 首次提出来的一种 模式识别分类技术[29]。SVM 是在统计学习理论 (statistical learning theory，SLT) 原理的基础上发展 起来的机器学习算法。SVM 方法的重点在于在 高维特征空间中能构造函数集 VC 维尽可能小的 最优分类面，使得不同类别样本在这分类面上分 类上界最小化，从而保证分类算法的最优推广能 力。图 7 所示的是 SVM 方法的分类原理示意 图。SVM 在有限训练样本情况下，在学习机复杂 度和学习机泛化能力之间找到一个平衡点，从而 保证学习机的推广能力[30]。 H1 H X1 H2 X2 最优超平面 w·x + b = 0 分类间隔 = 2 w 类别 1 分类错误 类别 2 支持向量 分离超平面 图 7 SVM 分类原理示意图 Fig. 7 SVM classification schematic diagram 根据样本分布情况与样本集维数，SVM 算法 的判别函数原理大致可分为线性可分与非线性可 分两种形式。 1) 线性可分 带有以式 (2) 所示训练样本集的 SVM 线性可 分分类问题的数学模型可通过式 (3) 来表示： S = {(xi , yi),i = 1,2,··· ,r}, xi ∈ R n , yi ∈ {+1,−1} (2) minφ(ω) = 1 2 ∥ω∥ 2 ,s.t.yi[ωxi +b]−1 ⩾ 0, i = 1,2,··· ,n (3) ω· x+b = 0 2 ∥ω∥ ∥ω∥ ω 假如，对 n 维空间中的分类界面为 ， 使得与此分类界面最近的两类样本之间的距离 最大，即 为最小，则该分类界面就称为最优 分类界面； 为权重向量 (是 f(x) 的法向量)，b 为函 数阈值。从而最终可得到所求的最优分类函数为 f (x) = sign ∑n i=1 aiyi(xi · x)+b (4) 式中对应 ai≠0 时的样本点就是支持向量。因为 最优化问题解 ai 的每一个分量都与一个训练点 相对应，显然所求得的划分超平面仅仅与对应 ai≠0 时的那些训练点 (xi ·x) 相关，而跟 ai=0 时的那 些训练点没有任何关系。相应于 ai≠0 时的训练 点 (xi ·x) 里的输入点 xi 就是支持向量，通常它们是 全体样本中的很少一部分。得出结论，最终分类 分界面的法向量 ω 只受支持向量的影响，不受非 支持向量训练点的影响。 2) 非线性可分 φ : xi → φ(xi) S V M 通过运用合适的非线性映射，如 把分类问题原训练样本点转变 (映 射) 到新的地方 (新特征空间)，使得原样本在这新 特征空间 (目标高维空间) 中能够线性可分，然后 在这新的映射空间中利用线性可分问题求解原理 求出最终的最优分类面。 为此，需要在式 (3) 中增加一个松弛变量 ξi 和 惩罚因子 C，从而式 (3) 变为 minφ(ω, ξ) = 1 2 ∥ω∥ 2 +C ∑n i=1 ξi , s.t.yi[ωxi +b]−1+ξi ⩾ 0 (5) 式中：ξi ≥ 0；i = 1, 2, ···, n；C 为控制样本对错分的 调整因子，通常称为惩罚因子。C 越大，惩罚越重。 虽然原理看起来简单，然而在分类问题的训 练样本不充足或不能保证训练样本质量的情形下 确定非线性映射是很困难的，那么如何确定非线 性映射呢？SVM 通过运用核函数概念解决这个 问题，核函数是 SVM 的其他分类算法无法替代 的独特功能。 ω·φ(x) SVM 通过引入一个核函数 K(xi ·x)，将原低维 的分类问题空间映射到高维的新问题空间中，使 核函数代替 内积运算，这个高维空间就称 为 Hilbert 空间。引入核函数以后的最优分类函数为 f (x) = sign ∑n i=1 aiyiK(xi · x)+b (6) 2.2 KNN 方法 KNN(K nearest neighbor) 分类法是基于实例 的学习算法，它需要所有的训练样本都参与分 类 [31]。在分类阶段，利用欧氏距离公式，将每个测 试样本与和它邻近的 k 个训练样本进行比较，然 后将测试样本归属到票数最多的那一类里[ 3 2 ]。 KNN 算法是根据测试样本最近的 k 个样本点的 类别信息来对该测试样本类型进行判别，所以 k 值的选取非常重要。k 值若太小，测试样本特征 不能充分体现；k 值若太大，与测试样本并不相似 的个别样本也可能被包含进来，这样反而对分类 不利。KNN 算法在分类决策上只凭 k 个最邻近 样本类别确定待分样本的所属类。目前，对于 k 值的选取还没有一个全局最优的筛选方法，这 也是 KNN 方法的弊端，具体操作时，根据先验知 识先给出一个初始值，然后需要根据仿真分类实 验结果重新调整，调整 k 值的操作有时一直到分 类结果满足用户需求为止。该方法原理可由式 ·802· 智 能 系 统 学 报 第 13 卷
第5期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·803· (7表示： 距离值点离得最近就把它归为该类别中。分类决 y(d)=argmax∑yc,c) (7) 策依据是各类别SVs平均距离值后对其与测试点 EKNN 之间距离的数值分析，所以简称该算法为支持向 式(7)表明将测试样本d,划入到k个邻近类 量与最近邻方法((the support vector of nearest neigh- 别中成员最多的那个类别里。 bor,SV-NN). 在使用KNN算法时，还可由其他策略生成测 3.1SV-NN算法描述及流程图 试样本的归属类，如式（⑧）也是被广泛使用的公式： 假设共有n个类别，每个类别含有m个支持 y(d)=argmaxSim(d.y() (8) 向量。 EKNN 训练集：T1={x,x2,…,xo 当x∈c,时，y(x,c)=1；当x度c,时，y(x,c)=0; 测试集：T2={x1,x2,…,xlo Sim(d,x)是测试样本d,和它最近邻x之间的余弦 SV-NN分类算法： 相似度。余弦相似度测量是由一个向量空间中两 Start: 个向量之间角余弦值来定义的。式(8)说明测试 integer i,jkl; 样本d,被归到k个最近邻类里相似性最大那个类 i=1;=1;k=1;i=1,2…,mj=1,2…,m 别里。 SVM:T→sV;∥通过使用SVM定义每个类别 一般情况下，不同类别训练样本的分布是不 的支持向量。 均匀的，同样不同类别的样本数量也可能不一 while(k<l) 样。所以，在分类任务中，KNN中k参数的一个固 {输入x: 定值可能会导致不同类别之间的偏差。例如，对 利用式(9)计算x与sV之间的距离(D: 于式(T),一个较大的k值使得方法运行结果过拟 利用式(10)计算x.与sV之间的平均距离 合，反过来一个较小的k值使得方法模型性能不 (averD); 稳定。实际上，k的值通常由交叉验证技术来获 利用式(11)计算x与sV1之间最小平均距离 取。然而，像在线分类等情况，就不能用交叉验证 (min(averD:)); 技术，只能给出经验值，因此k值的选定很重要。 将x划入到基于min(averDa)的最近类别； KNN虽是简单有效的分类方法，但不能忽略 =k+1 以下两方面的问题：1)由于KNN需要保留分类 过程中的所有相似性计算实例，从而随着训练集 规模的增多，其计算量也会增加，在处理较大规 End 模数据集分类时方法的时间复杂度会达到不可接 SV-NN分类方法的工作流程如图8所示。 受的程度例，这是KNN方法的主要缺点；2)KNN方 3.2SV-NN算法实现 法分类的准确性可能受到训练数据集中特性的无 1)将所有训练点映射到向量空间，并通过传 关性和噪声数据的影响，若考虑这些因素其分类 统SVM确定每一个类别的支持向量。 效果也许更好。 SV1sV2·· SVIm SV21 SV22 3基于SV-NN的哈萨克语文本分类 SV2m i=1,2,…,j=1,2,…,m 算法 SV SV2· (9) 本文提出一种组合分类方法，把SVM算法当 式中：支持向量sV,是从输人文档中提取的（共有 作KNN算法的训练阶段，这样可以避免k参数的 n个类，每个类别含有m个支持向量)。确定每一 选择。组合分类方法结合了SVM算法的训练和 类的支持向量之后，其余的训练点可以消除。 KNN算法的学习阶段。首先运用SVM算法对所 2)使用欧氏距离公式(9)计算测试样本x与 有训练样本进行一次训练获得每一类别的少量的 由1)生成的每一类支持向量sv之间的距离。 支持向量(support vectors,SVs),在测试阶段使用 最近邻分类器进行测试并分类测试样本，即计算 -2-2月 (10) 出新测试样本与每个类别SVs平均距离值后对其 进行对比分析，该测试样本与哪一类别SVs平均 式中：i=1,2,…,mj=1,2,…,m:k=1,2,…,1
(7) 表示： y (di) = argmax k ∑ xj∈KNN y ( xj , ck ) (7) 式 (7) 表明将测试样本 di 划入到 k 个邻近类 别中成员最多的那个类别里。 在使用 KNN 算法时，还可由其他策略生成测 试样本的归属类，如式 (8) 也是被广泛使用的公式： y (di) = argmax k ∑ xj∈KNN Sim( di , xj ) y ( xj , ck ) (8) y ( xj , ci ) = 1 < y ( xj , ci ) = 0 Sim( di , xj ) 当 x j∈c i时 ， ； 当 x j c i 时 ， ； 是测试样本 di 和它最近邻 xj 之间的余弦 相似度。余弦相似度测量是由一个向量空间中两 个向量之间角余弦值来定义的。式 (8) 说明测试 样本 di 被归到 k 个最近邻类里相似性最大那个类 别里。 一般情况下，不同类别训练样本的分布是不 均匀的，同样不同类别的样本数量也可能不一 样。所以，在分类任务中，KNN 中 k 参数的一个固 定值可能会导致不同类别之间的偏差。例如，对 于式 (7)，一个较大的 k 值使得方法运行结果过拟 合，反过来一个较小的 k 值使得方法模型性能不 稳定。实际上，k 的值通常由交叉验证技术来获 取。然而，像在线分类等情况，就不能用交叉验证 技术，只能给出经验值，因此 k 值的选定很重要。 KNN 虽是简单有效的分类方法，但不能忽略 以下两方面的问题：1) 由于 KNN 需要保留分类 过程中的所有相似性计算实例，从而随着训练集 规模的增多，其计算量也会增加，在处理较大规 模数据集分类时方法的时间复杂度会达到不可接 受的程度[33] ，这是 KNN 方法的主要缺点；2) KNN 方 法分类的准确性可能受到训练数据集中特性的无 关性和噪声数据的影响，若考虑这些因素其分类 效果也许更好。 3 基于 SV-NN 的哈萨克语文本分类 算法 本文提出一种组合分类方法，把 SVM 算法当 作 KNN 算法的训练阶段，这样可以避免 k 参数的 选择。组合分类方法结合了 SVM 算法的训练和 KNN 算法的学习阶段。首先运用 SVM 算法对所 有训练样本进行一次训练获得每一类别的少量的 支持向量 (support vectors，SVs)，在测试阶段使用 最近邻分类器进行测试并分类测试样本，即计算 出新测试样本与每个类别 SVs 平均距离值后对其 进行对比分析，该测试样本与哪一类别 SVs 平均 距离值点离得最近就把它归为该类别中。分类决 策依据是各类别 SVs 平均距离值后对其与测试点 之间距离的数值分析，所以简称该算法为支持向 量与最近邻方法 (the support vector of nearest neighbor，SV-NN)。 3.1 SV-NN 算法描述及流程图 假设共有 n 个类别，每个类别含有 m 个支持 向量。 训练集： T1 = {x1, x2,··· , xt}。 测试集： T2 = {x1, x2,··· , xl}。 SV-NN 分类算法： Start: { integer i, j,k,l； i=1; j=1; k=1；// i = 1,2,··· ,n; j = 1,2,··· ,m; SVM: T1→svij；//通过使用 SVM 定义每个类别 的支持向量。 while(k<l) { 输入 xk； 利用式 (9) 计算 xk 与 svij 之间的距离 (Dk )； 利用式 (10) 计算 xk 与 svij 之间的平均距离 (averDk )； min k (averDk) 利用式 (11) 计算 xk 与 svij 之间最小平均距离 ( )； min k 将 x (averDk) k 划入到基于 的最近类别； k=k+1; } } End SV-NN 分类方法的工作流程如图 8 所示。 3.2 SV-NN 算法实现 1) 将所有训练点映射到向量空间，并通过传 统 SVM 确定每一个类别的支持向量。 sv11 sv12 ··· sv1m sv21 sv22 ··· sv2m . . . . . . . . . svn1 svn2 ··· svnm , i = 1,2,··· ,n; j = 1,2,··· ,m (9) 式中：支持向量 svij 是从输入文档中提取的 (共有 n 个类，每个类别含有 m 个支持向量)。确定每一 类的支持向量之后，其余的训练点可以消除。 2) 使用欧氏距离公式 (9) 计算测试样本 xk 与 由 1) 生成的每一类支持向量 svij 之间的距离。 Dk j = ∑l k=1 vuut ∑n i=1 xk − ∑m j=1 svi j 2 (10) 式中： i = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,l。 第 5 期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·803·
·804· 智能系统学报 第13卷 测试 数据 测试集 基于欧氏距离函数的混合分类决策 模块 贝叶斯向量化模块 转换测试 计算测试点和每一类sw 转换训练 数据 之间的距离 数据 中 分类结果 计算测试点与每一类sv,之间 的平均距离 训练集 训练 将测试点归为具有最小平均距 数据 SVM训练算法 离值的类 图8SV-NN分类方法工作原理 Fig.8 SV-NN classification approach working principle diagram 3)使用式(10)计算测试样本x与每一类支 库还不能称得上“标准”词语，但对现阶段哈萨克 持向量sv之间的平均距离： 语文本分类任务的完成具有实际应用价值。 本文把语料集规模扩大到由计算机、经济、 教育、法律、医学、政治、交通、体育等8类共1 averD= -，j=1,2,…,mk=1,2…,l (11) 1 400个哈萨克语文档组成的小型语料集，如表1 4)计算最短平均距离minD,并将测试样本 所示。数据集被分为两个部分。880个文档 划入到最短平均距离对应的那一类中。 (63%)用于训练，520个文档用于测试(37%)。 min D min (averD )k=1,2.....l (12) 表1数据集 即输入点被确认为与sV之间最短平均距离值对 Table 1 Data set 应的正确类。 类别 文档总数 训练文档数 测试文档数 重复步骤2)~4)，直到所有的测试样本分类完 计算机 175 110 65 为止。 经济 175 110 65 教育 175 110 65 4实验结果与评价 法律 175 110 65 通常，语料库里语料的质量与数量直接影响 医学 175 110 65 政治 175 110 65 文本分类算法的分类性能。中、英文等其他语言 交通 175 110 65 文本分类研究都有标准的语料库，而哈萨克语文 体育 175 110 65 本分类工作却还没有一个公认的标准语料库。本 总计 1400 880 520 文考虑到文本分类工作的规范性和语料的标准 性，由中文标准语料部分文档的翻译和挑选新疆 本文文本分类实验评价指标采用了召回率、 日报（哈文版）上的部分文档来搭建了本研究的 精度和F这3种评价方法。精度评价是指比较 语料库。在前期研究里，同样是通过翻译收集语 实际文本数据与分类结果，以确定文本分类过程 料集的，只是其规模小了点，本文的语料工作算 的准确程度，是文本分类结果是否可信的一种度 是对前期研究语料集的补充和优化完善。前期研 量。高精度意味着一个算法返回更相关的结果， 究语料集语料文档只有5类文档，本文扩充到 高召回率代表着一个算法返回最相关的结果，所 8类文档。通过跟语言学专家们的多次沟通，选 以文本分类工作期望获得较高的精度和召回率。 择具有代表性的文档，同时对词干提取程序解析 本文在前期研究中搭建的哈萨克文语料集的 规则也作了适当的调整。虽然本文所构建的语料 补充完善以及对其词干提取程序提取规则细节的
转换测试 转换训练 数据 数据 测试 数据 训练 数据 训练集 贝叶斯向量化模块 SVM 训练算法 基于欧氏距离函数的混合分类决策 模块 计算测试点和每一类 svs 之间的距离 计算测试点与每一类 svs 之间 的平均距离 将测试点归为具有最小平均距 离值的类 分类结果 测试集 图 8 SV-NN 分类方法工作原理 Fig. 8 SV-NN classification approach working principle diagram 3) 使用式 (10) 计算测试样本 xk 与每一类支 持向量 svij 之间的平均距离： averDk = ∑m j=1 Dk j m , j = 1,2,··· ,m; k = 1,2,··· ,l (11) 4）计算最短平均距离 minD，并将测试样本 xk 划入到最短平均距离对应的那一类中。 minD = min k (averDk), k = 1,2,··· ,l (12) 即输入点被确认为与 svij 之间最短平均距离值对 应的正确类。 重复步骤 2)~4)，直到所有的测试样本分类完 为止。 4 实验结果与评价 通常，语料库里语料的质量与数量直接影响 文本分类算法的分类性能。中、英文等其他语言 文本分类研究都有标准的语料库，而哈萨克语文 本分类工作却还没有一个公认的标准语料库。本 文考虑到文本分类工作的规范性和语料的标准 性，由中文标准语料部分文档的翻译和挑选新疆 日报 (哈文版) 上的部分文档来搭建了本研究的 语料库。在前期研究里，同样是通过翻译收集语 料集的，只是其规模小了点，本文的语料工作算 是对前期研究语料集的补充和优化完善。前期研 究语料集语料文档只有 5 类文档，本文扩充到 8 类文档。通过跟语言学专家们的多次沟通，选 择具有代表性的文档，同时对词干提取程序解析 规则也作了适当的调整。虽然本文所构建的语料 库还不能称得上“标准”词语，但对现阶段哈萨克 语文本分类任务的完成具有实际应用价值。 本文把语料集规模扩大到由计算机、经济、 教育、法律、医学、政治、交通、体育等 8 类共 1 400 个哈萨克语文档组成的小型语料集，如表 1 所示。数据集被分为两个部分。 8 8 0 个 文 档 (63%) 用于训练，520 个文档用于测试 (37%)。 表 1 数据集 Table 1 Data set 类别 文档总数 训练文档数 测试文档数 计算机 175 110 65 经济 175 110 65 教育 175 110 65 法律 175 110 65 医学 175 110 65 政治 175 110 65 交通 175 110 65 体育 175 110 65 总计 1 400 880 520 本文文本分类实验评价指标采用了召回率、 精度和 F1 这 3 种评价方法。精度评价是指比较 实际文本数据与分类结果，以确定文本分类过程 的准确程度，是文本分类结果是否可信的一种度 量。高精度意味着一个算法返回更相关的结果， 高召回率代表着一个算法返回最相关的结果，所 以文本分类工作期望获得较高的精度和召回率。 本文在前期研究中搭建的哈萨克文语料集的 补充完善以及对其词干提取程序提取规则细节的 ·804· 智 能 系 统 学 报 第 13 卷
第5期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·805· 优化改善基础上实现了本研究哈萨克语文本的预 能获得较好分类精度的优点，另外，本算法没有 处理。分类任务的实现运用了SVM、KNN与本 去定义KNN算法的k参数，也没有跟所有类所有 文提出的SV-NN算法，并对3种算法分类精度进 训练样本进行距离运算。所以，本研究提出的算 行了较全面的对比分析。通过对表2和图9上的 法无论从算法复杂度的分析还是算法收敛速度的 仿真实验数字的对比分析，发现SVM算法优于 分析都是有效的。当然，总体精度还是没有像 KNN算法，而SV-NN算法优于SVM算法。SV-NN 中、英文等其他语言文本分类精度那么理想，因 方法F,指标除了教育类和法律类以外在其他类 为涉及很多方面的因素，如研究语料库语料文档 上的F,指标都高于都SVM、KNN对应指标。SVM、 数量、每一类文档本身的质量、词干表里已录用 KNN和SV-NN平均分类精度分别为0.754、 的词干数量和质量、词干提取程序解析规则的细 0.731和0.778，这说明本文提出算法对所有类别 节等，但目前所获得的分类精度比前期系列研究 文档词的召回率和区分度较稳定。本研究提出的 成果理想，本算法的文本分类性能有了很大的提 算法模型继承了SVM算法在有限样本情况下也 升也较好地提高了召回率。 表2SVM、KNN、SVNN的分类精度对比 Table 2 SVM KNN and SV-NN comparison of classification accuracy SVM KNN SV-NN 类别名 精度 召回率 F 精度 召回率 F 精度 召回率 F 计算机 0.665 0.651 0.658 0.636 0.649 0.642 0.696 0.647 0.671 经济 0.781 0.862 0.819 0.768 0.858 0.811 0.710 0.870 0.830 教育 0.715 0.691 0.703 0.698 0.675 0.686 0.615 0.651 0.632 法律 0.889 0.891 0.895 0.860 0.865 0.862 0.879 0.881 0.878 医学 0.812 0.881 0.845 0.799 0.892 0.843 0.877 0.881 0.879 政治 0.563 0.598 0.580 0.513 0.589 0.548 0.673 0.698 0.685 交通 0.791 0.721 0.754 0.769 0.711 0.739 0.891 0.851 0.870 体育 0.811 0.785 0.796 0.801 0.726 0.762 0.791 0.711 0.749 平均 0.754 0.759 0.756 0.731 0.746 0.738 0.778 0.774 0.775 1.0 1.0 0.8 0.8 0.6 0.6 0.4 ◆SVM精度 04 ◆一KNN精度 0.2 ■一SVM召回率 0.2 一KNN召回率 KNN F, 0 0 教育 计算机 (a)SVM分类精度 (b)KNN分类精度 1.0 1.0 0.8 0.8 0.6 0.6 04 ◆-SVNN精度 0.4 ◆F,SVM ■SV-NN召回率 0.2 F KNN SV-NNF 0.2 F.SV-NN 0 香我 0 (c)SV-NN分类精度 (d)3个方法F,指标的对比 图9分类精度的对比分析（每一类别均含175篇文档） Fig.9 Comparative analysis of classification accuracy (each category contains 175 documents)
优化改善基础上实现了本研究哈萨克语文本的预 处理。分类任务的实现运用了 SVM、KNN 与本 文提出的 SV-NN 算法，并对 3 种算法分类精度进 行了较全面的对比分析。通过对表 2 和图 9 上的 仿真实验数字的对比分析，发现 SVM 算法优于 KNN 算法，而 SV-NN 算法优于 SVM 算法。SV-NN 方法 F1 指标除了教育类和法律类以外在其他类 上的 F1 指标都高于都 SVM、KNN 对应指标。SVM、 KNN 和 SV-NN 平均分类精度分别 为 0.754、 0.731 和 0.778，这说明本文提出算法对所有类别 文档词的召回率和区分度较稳定。本研究提出的 算法模型继承了 SVM 算法在有限样本情况下也 能获得较好分类精度的优点，另外，本算法没有 去定义 KNN 算法的 k 参数，也没有跟所有类所有 训练样本进行距离运算。所以，本研究提出的算 法无论从算法复杂度的分析还是算法收敛速度的 分析都是有效的。当然，总体精度还是没有像 中、英文等其他语言文本分类精度那么理想，因 为涉及很多方面的因素，如研究语料库语料文档 数量、每一类文档本身的质量、词干表里已录用 的词干数量和质量、词干提取程序解析规则的细 节等，但目前所获得的分类精度比前期系列研究 成果理想，本算法的文本分类性能有了很大的提 升也较好地提高了召回率。 表 2 SVM、KNN、SV-NN 的分类精度对比 Table 2 SVM KNN and SV–NN comparison of classification accuracy 类别名 SVM KNN SV-NN 精度 召回率 F1 精度 召回率 F1 精度 召回率 F1 计算机 0.665 0.651 0.658 0.636 0.649 0.642 0.696 0.647 0.671 经济 0.781 0.862 0.819 0.768 0.858 0.811 0.710 0.870 0.830 教育 0.715 0.691 0.703 0.698 0.675 0.686 0.615 0.651 0.632 法律 0.889 0.891 0.895 0.860 0.865 0.862 0.879 0.881 0.878 医学 0.812 0.881 0.845 0.799 0.892 0.843 0.877 0.881 0.879 政治 0.563 0.598 0.580 0.513 0.589 0.548 0.673 0.698 0.685 交通 0.791 0.721 0.754 0.769 0.711 0.739 0.891 0.851 0.870 体育 0.811 0.785 0.796 0.801 0.726 0.762 0.791 0.711 0.749 平均 0.754 0.759 0.756 0.731 0.746 0.738 0.778 0.774 0.775 0 0.2 0.4 0.6 0.8 1.0 精度、召回率与 F1 SVM F1 SVM 精度 SVM 召回率 (a) SVM 分类精度 KNN 精度 KNN 召回率 KNN F1 0 0.2 0.4 0.6 0.8 1.0 精度、召回率与 F1 (b) KNN 分类精度 0 0.2 0.4 0.6 0.8 1.0 精度、召回率与 F1 SV-NN F1 SV-NN 精度 SV-NN 召回率 (c) SV-NN 分类精度 F1 SVM F1 KNN F1 SV-NN 0 0.2 0.4 0.6 0.8 1.0 F1 (d) 3 个方法 F1 指标的对比 计算机 经济 教育 法律 医学 政治 交通 体育 平均 计算机 经济 教育 法律 医学 政治 交通 体育 平均 计算机 经济 教育 法律 医学 政治 交通 体育 平均 计算机 经济 教育 法律 医学 政治 交通 体育 平均 图 9 分类精度的对比分析（每一类别均含 175 篇文档） Fig. 9 Comparative analysis of classification accuracy (each category contains 175 documents) 第 5 期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·805·
·806· 智能系统学报 第13卷 5结束语 spam detection[J].Applied soft computing,2011,11(4): 3827-3845. 本文在前期系列研究中所搭建的哈萨克文语 [10]MAO Ming,PENG Yefei,SORING M.Ontology map- 料集和词干提取程序的优化完善基础上实现了哈 ping:As a binary classification problem[J].Concurrency 萨克语文本的预处理。分类任务的实现上运用了 and computation:practice and experience,2011,23(9): 模式识别的3种分类算法，并对3种分类算法分 1010-1025. 类精度进行了较全面的对比分析。通过仿真实验 [11]YANG Yiming,SLATTERY S,GHANI R.A study of 客观数字的对比分析，说明本文提出算法的优越 approaches to hypertext categorization[J].Journal of intel- 性。本文算法对所有类别文档词的召回率和区分 ligent information systems,2002,18(2/3):219-241. 度较稳定。本文算法在继承SVM算法的分类优 [12]REN Fuji,LI Chao.Hybrid Chinese text classification ap- 越性基础上，还有效避免了KNN算法设置k参数 proach using general knowledge from Baidu Baike[J]. IEEJ transactions on electrical and electronic engineering, 的麻烦和跟所有训练样本进行距离计算而带来的 2016,11(4):488-498 巨大时间复杂度，进而保证了分类算法的收敛速度。 [13]DUWAIRI R,EL-ORFALI M.A study of the effects of 本研究仍有许多待优化完善的问题，本文接 preprocessing strategies on sentiment analysis for Arabic 下来的研究工作中将系统地研究并解决影响文本 text[J].Journal of information science,2014,40(4): 分类精度的阶段性问题，获得满意的分类精度。 501-513. 参考文献 [14]张冬梅.文本情感分类及观点摘要关键问题研究D]济 南：山东大学，2012 [1]SEBASTIANI F.Machine learning in automated text cat- ZHANG Dongmei.Research on key problems in text sen- egorization[J].ACM computing surveys,2002,34(1): timent classification and opinion summarization[D] 1-47 Ji'nan:Shandong University,2012 [2]AHMADI A,FOTOUHI M,KHALEGHI M.Intelligent [15]杨杰明.文本分类中文本表示模型和特征选择算法研 classification of web pages using contextual and visual fea- 究D1.长春：吉林大学，2013. tures[J].Applied soft computing,2011,11(2):1638-1647. YANG Jieming.The research of text representation and [3]MARTINEZ-CAMARA E,MARTIN-VALDIVIA M T, feature selection in text categorization[D].Changchun: URENA-LOPEZ L A,et al.Polarity classification for Jilin University,2013. Spanish tweets using the COST corpus[J].Journal of in- [16]张晓娜.CNNIC发布第37次中国互联网络发展状况统 formation science,2015,41(3):263-272 计报告N]民主与法制时报，2016-01-23(001) [4]PERCANNELLA G.SORRENTINO D,VENTO M.Auto- [17]SYIAM MM.FAYED Z T.HABIB M B.An intelligent matic indexing of news videos through text classification system for Arabic text categorization[J].International techniques[M]//SINGH S,SINGH M,APTE C,et al.Pat- journal of cooperative information systems,2006,6(1): tern Recognition and Image Analysis.Berlin:Springer, 1-19 2005:512-521. [18]DUWAIRI R.AL-REFAI M.KHASAWNEH N.Stem- [5]HU Rong,NAMEE B M,DELANY S J.Active learning ming versus light stemming as feature selection tech- for text classification with reusability[J].Expert systems niques for Arabic text categorization[C]//Proceedings of with applications,2016,45:438-449 the 4th International Conference on Innovations in In- [6]SAKURAI S,SUYAMA A.An e-mail analysis method formation Technology.Dubai,2007:446-450. based on text mining techniques[J].Applied soft comput- [19)]贺慧，王俊义.主动支持向量机的研究及其在蒙文文本 ing,2005,6(1:62-71. 分类中的应用).内蒙古大学学报：自然科学版，2006， [7]AL-KABI M,WAHSHEH H,ALSMADI I,et al.Content- 37(5)560-563 based analysis to detect Arabic web spam[J].Journal of in- HE Hui,WANG Junyi.Study of active learning support formation science,2012,38(3):284-296. vector machine and its application on mongolian text clas- [8]ZITAR R A,MOHAMMAD A H.Spam detection using sification].Acta scientiarum naturalium universitatis genetic assisted artificial immune system[J].International neimongol,2006.37(5):560-563. journal of pattern recognition and artificial intelligence, [20]ADELEKE A O.SAMSUDIN N A,MUSTAPHA A,et 2011,25(8):1275-1295. al.Comparative analysis of text classification algorithms [9]MOHAMMAD A H,ZITAR R A.Application of genetic for automated labelling of quranic verses[J].International optimized artificial immune system and neural networks in journal on advanced science engineering information
5 结束语 本文在前期系列研究中所搭建的哈萨克文语 料集和词干提取程序的优化完善基础上实现了哈 萨克语文本的预处理。分类任务的实现上运用了 模式识别的 3 种分类算法，并对 3 种分类算法分 类精度进行了较全面的对比分析。通过仿真实验 客观数字的对比分析，说明本文提出算法的优越 性。本文算法对所有类别文档词的召回率和区分 度较稳定。本文算法在继承 SVM 算法的分类优 越性基础上，还有效避免了 KNN 算法设置 k 参数 的麻烦和跟所有训练样本进行距离计算而带来的 巨大时间复杂度，进而保证了分类算法的收敛速度。 本研究仍有许多待优化完善的问题，本文接 下来的研究工作中将系统地研究并解决影响文本 分类精度的阶段性问题，获得满意的分类精度。 参考文献： SEBASTIANI F. Machine learning in automated text categorization[J]. ACM computing surveys, 2002, 34(1): 1–47. [1] AHMADI A, FOTOUHI M, KHALEGHI M. Intelligent classification of web pages using contextual and visual features[J]. Applied soft computing, 2011, 11(2): 1638–1647. [2] MARTÍNEZ-CÁMARA E, MARTÍN-VALDIVIA M T, UREÑA-LÓPEZ L A, et al. Polarity classification for Spanish tweets using the COST corpus[J]. Journal of information science, 2015, 41(3): 263–272. [3] PERCANNELLA G, SORRENTINO D, VENTO M. Automatic indexing of news videos through text classification techniques[M]//SINGH S, SINGH M, APTE C, et al. Pattern Recognition and Image Analysis. Berlin: Springer, 2005: 512–521. [4] HU Rong, NAMEE B M, DELANY S J. Active learning for text classification with reusability[J]. Expert systems with applications, 2016, 45: 438–449. [5] SAKURAI S, SUYAMA A. An e-mail analysis method based on text mining techniques[J]. Applied soft computing, 2005, 6(1): 62–71. [6] AL-KABI M, WAHSHEH H, ALSMADI I, et al. Contentbased analysis to detect Arabic web spam[J]. Journal of information science, 2012, 38(3): 284–296. [7] ZITAR R A, MOHAMMAD A H. Spam detection using genetic assisted artificial immune system[J]. International journal of pattern recognition and artificial intelligence, 2011, 25(8): 1275–1295. [8] MOHAMMAD A H, ZITAR R A. Application of genetic optimized artificial immune system and neural networks in [9] spam detection[J]. Applied soft computing, 2011, 11(4): 3827–3845. MAO Ming, PENG Yefei, SORING M. Ontology mapping: As a binary classification problem[J]. Concurrency and computation: practice and experience, 2011, 23(9): 1010–1025. [10] YANG Yiming, SLATTERY S, GHANI R. A study of approaches to hypertext categorization[J]. Journal of intelligent information systems, 2002, 18(2/3): 219–241. [11] REN Fuji, LI Chao. Hybrid Chinese text classification approach using general knowledge from Baidu Baike[J]. IEEJ transactions on electrical and electronic engineering, 2016, 11(4): 488–498. [12] DUWAIRI R, EL-ORFALI M. A study of the effects of preprocessing strategies on sentiment analysis for Arabic text[J]. Journal of information science, 2014, 40(4): 501–513. [13] 张冬梅. 文本情感分类及观点摘要关键问题研究[D]. 济 南: 山东大学, 2012. ZHANG Dongmei. Research on key problems in text sentiment classification and opinion summarization[D]. Ji’nan: Shandong University, 2012. [14] 杨杰明. 文本分类中文本表示模型和特征选择算法研 究[D]. 长春: 吉林大学, 2013. YANG Jieming. The research of text representation and feature selection in text categorization[D]. Changchun: Jilin University, 2013. [15] 张晓娜. CNNIC 发布第 37 次中国互联网络发展状况统 计报告[N]. 民主与法制时报, 2016-01-23(001). [16] SYIAM M M, FAYED Z T, HABIB M B. An intelligent system for Arabic text categorization[J]. International journal of cooperative information systems, 2006, 6(1): 1–19. [17] DUWAIRI R, AL-REFAI M, KHASAWNEH N. Stemming versus light stemming as feature selection techniques for Arabic text categorization[C]//Proceedings of the 4th International Conference on Innovations in Information Technology. Dubai, 2007: 446–450. [18] 贺慧, 王俊义. 主动支持向量机的研究及其在蒙文文本 分类中的应用[J]. 内蒙古大学学报: 自然科学版, 2006, 37(5): 560–563. HE Hui, WANG Junyi. Study of active learning support vector machine and its application on mongolian text classification[J]. Acta scientiarum naturalium universitatis neimongol, 2006, 37(5): 560–563. [19] ADELEKE A O, SAMSUDIN N A, MUSTAPHA A, et al. Comparative analysis of text classification algorithms for automated labelling of quranic verses[J]. International journal on advanced science engineering information [20] ·806· 智 能 系 统 学 报 第 13 卷
第5期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·807· technology,2017,7(4:1419-1427. of rule quality for feature selection in text categorization [21]MOHAMMAD A H,ALWADA N T,AL-MOMANI O. [M/International Symposium on Advances in Intelligent. Arabic text categorization using support vector machine, Berlin:Springer,,2003:589-598. naive bayes and neural network[J].GSTF journal on com- [29]CORTES C,VAPNIK V.Support-vector networks[J]. puting,2016,5(1):1-8. Machine learning,1995,20(3):273-297. [22]古丽娜孜艾力木江，孙铁利，伊力亚尔加尔木哈，等 [30]WANG Xuesong,HUANG Fei,CHENG Yuhu.Compu- 一种基于主动学习支持向量机哈萨克文文本分类方法 tational performance optimization of support vector ma- [).智能系统学报，2011,6(3：261-267. chine based on support vectors[J].Neurocomputing,2016, GU Linazi Ai Limujiang,SUN Tieli,Yi Liyaer Jia Er- 211:66-71. muhamaiti,et al.An approach to the text categorization of [31]COVER T,HART P.Nearest neighbor pattern classifica- the Kazakh language based on an active learning support tion[J].IEEE transactions on information theory,1967, vector machine[J].CAAI transactions on intelligent sys- 13(121-27. tems,2011,6(3):261-267 [32]FRANKLIN J.The elements of statistical learning:data [23]古丽娜孜艾力木江，孙铁利，乎西旦居马洪，等.一种 mining,inference and prediction[J].The mathematical in- 基于改进KNN的哈萨克语文本分类[J].东北师大学 telligencer,2005,27(2):83-85. 报：自然科学版，2014,46(2)：63-68. GU Linazi Ai Limujiang,SUNTieli,HU Xidan Ju Ma- [33]MENG Qingmin,CIESZEWSKI C J,MADDEN M,et al. K nearest neighbor method for forest inventory using re- hong,et al.Textcategorization of kazakh text based on mote sensing data[J].GIScience remote sensing,2007, improved KNN[J].Journal of northeast normal university: natural science edition,2014,46(2):63-68. 442:149-165 [24]古丽娜孜·艾力木江，孙铁利，乎西旦·居马洪，等.一种 作者简介： 基于SVM修正KNN算法的哈萨克语文本分类U.西 古丽娜孜·艾力木江，女，1972年 北师范大学学报：自然科学版，2014,50(3：48-53. 生，副教授，博士，主要研究方向为机 GU Linazi Ai Limujiang,SUN Tieli,HU Xidan Ju Ma- 器学习、模式识别、智能信息分类与图 hong,et al.An approach to the text categorization of the 像处理。参与国家级、省部级科研项 目3项，承担院级重点项目4项。发 Kazakh language based on SVM-modified KNN al- 表学术论文20余篇。 gorithm[J].Journal of northwest normal university:natur- al science,2014,50(3:48-53. [25]旺建华.中文文本分类技术研究D].长春：吉林大学， 乎西旦·居马洪，女，1966年生，教 2007. 授，主要研究方向为智能信息处理、人 WANG Jianhua.Research on classification of Chinese 脸识别。承担国家级、省部级科研项 目4项。发表学术论文20余篇.出版 documents[D].Changchun:Jilin University,2007 教材1部。 [26]JOACHIMS T.Text categorization with support vector machines:Learning with many relevant features[M// NEDELLEC C.ROUVEIROL C.Machine Learning: ECML-98.Berlin:Springer,1998:137-142. 孙铁利，男，1956年生，教授，博 士生导师，主要研究方向为智能用户 [27]WANG Ziqiang,SUN Xia,ZHANG Dexian,et al.An op- 接口、智能信息挖掘。承担国家级、省 timal SVM-based text classification algorithm [C]//Pro- 部级科研项目12项。发表学术论文 ceedings of 2006 International Conference on Machine 150余篇，出版专著及教材10部。 Learning and Cybernetics.Dalian,China,2006:13-16. [28]MONTANES E.FERANDEZ J,DIAZ I,et al.Measures
technology, 2017, 7(4): 1419–1427. MOHAMMAD A H, ALWADA N T, AL-MOMANI O. Arabic text categorization using support vector machine, naïve bayes and neural network[J]. GSTF journal on computing, 2016, 5(1): 1–8. [21] 古丽娜孜·艾力木江, 孙铁利, 伊力亚尔·加尔木哈, 等. 一种基于主动学习支持向量机哈萨克文文本分类方法 [J]. 智能系统学报, 2011, 6(3): 261–267. GU Linazi Ai Limujiang, SUN Tieli, Yi Liyaer Jia Ermuhamaiti, et al. An approach to the text categorization of the Kazakh language based on an active learning support vector machine[J]. CAAI transactions on intelligent systems, 2011, 6(3): 261–267. [22] 古丽娜孜·艾力木江, 孙铁利, 乎西旦·居马洪, 等. 一种 基于改进 KNN 的哈萨克语文本分类[J]. 东北师大学 报: 自然科学版, 2014, 46(2): 63–68. GU Linazi Ai Limujiang, SUNTieli, HU Xidan Ju Mahong, et al. Textcategorization of kazakh text based on improved KNN[J]. Journal of northeast normal university: natural science edition, 2014, 46(2): 63–68. [23] 古丽娜孜·艾力木江, 孙铁利, 乎西旦·居马洪, 等. 一种 基于 SVM-修正 KNN 算法的哈萨克语文本分类[J]. 西 北师范大学学报: 自然科学版, 2014, 50(3): 48–53. GU Linazi Ai Limujiang, SUN Tieli, HU Xidan Ju Mahong, et al. An approach to the text categorization of the Kazakh language based on SVM-modified KNN algorithm[J]. Journal of northwest normal university: natural science, 2014, 50(3): 48–53. [24] 旺建华. 中文文本分类技术研究[D]. 长春: 吉林大学, 2007. WANG Jianhua. Research on classification of Chinese documents[D]. Changchun: Jilin University, 2007. [25] JOACHIMS T. Text categorization with support vector machines: Learning with many relevant features[M]// NÉDELLEC C, ROUVEIROL C. Machine Learning: ECML-98. Berlin: Springer, 1998: 137–142. [26] WANG Ziqiang, SUN Xia, ZHANG Dexian, et al. An optimal SVM-based text classification algorithm[C]//Proceedings of 2006 International Conference on Machine Learning and Cybernetics. Dalian, China, 2006: 13–16. [27] [28] MONTAÑÉS E, FERÁNDEZ J, DÍAZ I, et al. Measures of rule quality for feature selection in text categorization [M]//International Symposium on Advances in Intelligent. Berlin: Springer,, 2003: 589–598. CORTES C, VAPNIK V. Support-vector networks[J]. Machine learning, 1995, 20(3): 273–297. [29] WANG Xuesong, HUANG Fei, CHENG Yuhu. Computational performance optimization of support vector machine based on support vectors[J]. Neurocomputing, 2016, 211: 66–71. [30] COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE transactions on information theory, 1967, 13(1): 21–27. [31] FRANKLIN J. The elements of statistical learning: data mining, inference and prediction[J]. The mathematical intelligencer, 2005, 27(2): 83–85. [32] MENG Qingmin, CIESZEWSKI C J, MADDEN M, et al. K nearest neighbor method for forest inventory using remote sensing data[J]. GIScience & remote sensing, 2007, 44(2): 149–165. [33] 作者简介： 古丽娜孜·艾力木江，女，1972 年 生，副教授，博士,主要研究方向为机 器学习、模式识别、智能信息分类与图 像处理。参与国家级、省部级科研项 目 3 项，承担院级重点项目 4 项。发 表学术论文 20 余篇。 乎西旦·居马洪，女，1966 年生，教 授，主要研究方向为智能信息处理、人 脸识别。承担国家级、省部级科研项 目 4 项。发表学术论文 20 余篇，出版 教材 1 部。 孙铁利，男，1956 年生，教授，博 士生导师，主要研究方向为智能用户 接口、智能信息挖掘。承担国家级、省 部级科研项目 12 项。发表学术论文 150 余篇，出版专著及教材 10 部。 第 5 期 古丽娜孜·艾力木江，等：基于支持向量的最近邻文本分类方法 ·807·
