第6卷第3期 智能系统学报 Vol.6 No.3 2011年6月 CAAI Transactions on Intelligent Systems Jun.2011 doi:10.3969/i.i8gn.1673-4785.2011.03.011 一种基于主动学习支持向量机 哈萨克文文本分类方法 古丽娜孜1,2，孙铁利2，伊力亚尔1，吴迪2 (1.伊犁师范学院电子与信息工程学院，新疆伊宁835000：2.东北师范大学计算机科学与信息技术学院，吉林长春130117) 摘要：将文本分类理论应用于哈萨克语中，给出基于支持向量机的哈萨克文文本分类系统的设计思想.从哈萨克 语言学的角度对哈萨克文分析，提出哈萨克文词干提取的方法.在对支持向量机的理论分析基础上，提出主动学习 算法对支持向量机进行训练，使用训练后的分类器对新的文本进行分类.实验结果表明，该方法在哈萨克文文本分 类中能获得可接受的分类性能 关键词：支持向量机；哈萨克文文本分类：主动学习 中图分类号：TP391.1文献标识码：A文章编号：16734785(2011)03026107 An approach to the text categorization of the Kazakh language based on an active learning support vector machine GU Linazi'2,SUN Tieli2,YI Liyaer',WU Di2 (1.School of Electronic and Information Engineering,Yili Normal University,Yining 835000,China;2.School of Computer Science and Information Technology,Northeast Normal University,Changchun 130117,China) Abstract:In applying the theory of text categorization to the study to the Kazakh language,an approach to text cat- egorization of Kazakh text based on a support vector machine system was introduced.In this paper,from the Ka- zakh linguistic angle,the method to extract word stems was analyzed.Based on analysis of the support vector ma- chine,the proposed active learning algorithm was adopted for training.The trained classifier was used to classify new text.The experimental results show that this approach to Kazakh text classification has an acceptable classifica- tion performance. Keywords:support vector machine;Kazakh text categorization;active learning 文本自动分类任务是对未知类别的文本文档进实现分类任务需要一定的语料库，但目前为止在哈 行自动处理，判别它们所属预定义类别集中的一个 萨克语言中还没有一个公认的哈萨克文语料库，为 或多个类别.迄今为止，文本分类在那些被广泛使用 此需考虑语料集的规范，笔者对公认的中文语料库 的语言中得到了较好的研究和应用2]，但在哈萨 中的部分文本进行翻译构建了本文分类器的语料 克语中没有得到很好的发展.这是因为哈萨克语的 库，同时选择最适合这种小样本分类任务的支持向 文本分类技术研究起步此较晚，而且哈萨克语单词 量机分类方法来实现分类 的自动切分处理有一定的难度.由于哈萨克语的语 1文本特征提取 法体系与其他语言语法体系之间存在很大的差别， 因此不能直接采用其他语言文本处理方面的研究成 实现文本分类任务大致需要经过以下几个步 果，需要研究出适合哈萨克文自己的文本分类体系. 骤：1)文本预处理，通过特征提取将文本转换成自 动处理的文本模型；2)根据问题性质和研究结果建 收稿日期：2010-1008. 基金项目：教育部科技发展中心网络时代的科技论文快速共享研究 立分类器模型，并以相应数据集来训练分类器；3) 项目(20090043110010)：吉林省科技规划资助项目 (20090503):吉林省教育厅“十一五”科研规划资助项目 测试新的文本样本.本文将就上述关键技术进行讨 (2009587). 论，并给出研究方法和实验结果。 通信作者：孙铁利.E-mail:8untl@nenu.edu.cm
262 智能系统学报 第6卷 1.1文本预处理 换最复杂的词类，是词切分中的难点.本文在上述各 文本预处理主要是从文本中提取关键词来表示 类前期准备工作的基础上，给出了这3种词性的有 文本的处理过程.在预处理过程中，要对文本进行分 限状态自动机，然后采用双向全切分和词法分析相 词处理，将连续的语句分隔为分散的有独立意义的 结合的改进方法实现哈萨克语词干提取和构形附加 词集，然后去除集合中的停用词，获得文本的关键词 成分的细切分.对于词干表搜索，首次采用了改进的 集合.文本预处理方法是影响文本分类准确度的关 逐字母二分词典查询机制来提高词干提取的效率， 键因素之一，对于不同语言，需要采用不同的预处理 对歧义词和未登陆词的切分采用概率统计的方法。 技术得到相关文本的词性信息.例如，中文需要进行 index type sulfix btype 分词，英文则需要进行词干提取 215adj Y ge 201ad igc 哈萨克文为拼音文字，属于阿尔泰语系突厥语 228ad gc 族的克普恰克语支，中国境内通用的哈萨克文借用 227 adj C 了阿拉伯语和部分波斯文字母.哈萨克文共有33个 226ad 字母，其中有24个辅音字母、9个元音字母，每个字 图2哈萨克语附加成分 母的位置有词首、词中、词末、独立4种变体，词与词 Fig.2 Additional components in Kazakh text 之间有空格分开，所以哈萨克文不需要分词处理.作 在以上研究基础上，设计实现了哈萨克语自动 为黏着语，哈萨克语的语法形式是通过在单词原形 词法分析中的附加成分的切分和词干提取程序，完 的后面或前面附加一定的附加成分来完成的.这就 成了哈萨克文文本的读取预处理.处理结果如图3 造成在哈萨克语文本中，一个哈萨克语词对应多个 所示，上半窗体显示内容是待切分的原文，下半窗体 字符串形式，因此一定要对其进行词干提取 显示内容是切分后的结果 哈萨克文预处理工作中，除了词干提取以外，还 要进行构形附加成分的切分.这是由于构形附加成 -i心4d沙护uL·为 分与词干互相黏连，构形附加成分之间也互相黏连， 而且构形附加成分往往可以表示一定意义，如果不 ·sLu 将这些黏连在一起的构形附加成分切分开，就不能 JL13s 罗-05店与中运片 l4克？+小 准确地表达整个单词的含义.因此，对于哈萨克语词 -1护心-”y-呢4为 干提取方法的研究和应用其构形语素的分析需要并 山54这 行处理.本文完成了哈萨克文词干提取以及词性标 注所需的哈萨克语词干表的构建.该词干表收录了 ·5,Ly且-+yr为 由新疆人民出版社出版的《哈萨克语详解词典》中 .i远，远：一114光，，h,玉，d心--儿 的6万多个哈萨克语词干，形式如图1所示.图2是 附加成分表的一部分，其收录了438个哈萨克语附 图3哈萨克文词干切分结果示例 加成分.整个附加成分可分为构形附加成分和构词 Fig.3 Example of segmentation results of the Ka- 附加成分两大类.其中，构形附加成分为4种，即复 zakh text stem 数附加成分、领属性人称附加成分、格附加成分和谓 1.2文本模型 语性人称.构词附加成分同样分为4种，包括动词、 文本属于一种非结构化的数据，无法被学习算 形容词、数词和副词附加成分.附加成分的详细分类 法直接用于训练或分类.通过简单而准确的方法，将 文本表示成机器可处理的形式，是进行文本分类的 有助于在附加成分切分阶段进行词法分析. id word pos 基础.向量空间模型(vector space model,VSM)是最 经典的文本形式化表示方法，它将文本表示为包含 特征项和特征项权重的向量.在VSM中，用d(doc ument)表示文本，特征项是指出现在文本d中且可 5. 6 代表该文本内容的基本语言单位，用t(tem)表示， 特征项权重是指词对文本的重要程度，用0 图1哈萨克语词干 (weight)表示.VSM将文本映射为一个特征向量 Fig.1 Kazakh text stem V(d)=（(t1,01),(t2,02),…,（t,0:）,…,(tn, 名词、动词和形容词是哈萨克语中数量最多、变 w)),其中(i=1,2,…,n)为一些互不相同的特征
第3期 古丽娜孜，等：一种基于主动学习支持向量机哈萨克文文本分类方法 ·263· 词，0：表示特征项t在文本中的权重，其计算公 SVM解决分类问题时根据数据集的来源特征 式3]为 将分类问题分为线性可分状态和线性不可分状态， f(t,d)log(n/n,+0.01) 针对训练样本集(1)，线性可分问题可以用式(2)所 0:= /∑[ft,d)log(n/n,+0.01)]2 示的SVM数学模型来解决. N S={(xy),i=1,2,…,rf, 式中：f(t,d)为特征项t在文本d中的词频；n为训 x:∈R",y:∈{+1，-1}； (1) 练文本总数；n,为训练文本集中包含特征项t的文 本数. min(w)=子Iw2, 1.3特征处理 s.t.y(wx:+b)-1≥0，i=1,2,…,1.(2) 对训练样本集进行预处理所得到的关键词的集 n维空间中分界面为wx+b=0,能使到该分界 合构成了初始特征项（词）集合，简称特征集，通常 该集合中特征项数目过多是制约分类的重要因素， 面最近的2类样本之间的距离品最大，也就是 即使是一个小规模的样本集，经过预处理也会得到 ‖w‖最小，该分类界面就称为最优分类界面.从而 一定数量的特征词，其中有些特征词对文本内容和 最终可得到所求的最优分类函数为 类别的贡献很小，及时消除这些特征词会有效地控 制向量空间的维数.因此，必须通过降维处理去除弱 fx)=8ign(∑ay:(x·x)+b): 关联词，抽取强关联词构成用于学习的特征集。 式中：对应a:不为0的样本就是支持向量.最优化 特征就是区分类别的尺度，不同的模式分类问 问题的解a:的每一个分量都与一个训练点相对应， 题有不同的特征选择方法，在文本分类中所用到的 显然以上算法所构造的划分超平面，仅仅依赖于那 方法有文档频率(DF)、信息增益(IG)、互信息 些相应于a:不为零的训练点(x:·x),而与相应于 (MI)、X统计量(CHⅢ)、卡方统计量、期望交叉嫡、 a;为零的那些训练点无关.相应于a;不为零的训练 文本证据权以及几率比等. 点(x:·x)中的输入x:为支持向量，显然，只有支持 上述评判函数是目前用的比较多的特征抽取评 向量对最终求得的划分超平面的法方向有影响， 估函数，它们各有各的优缺点，IG、MI、CHⅡ侧重于低 而它与非支持向量无关，这种方法就是支持向量机 频词，而DF侧重于高频词.目前，研究者分别对这 对于非线性问题，支持向量机通过选择适当的 些方法做了不同的优化改进，达到了各自的理想效 非线性变换，将输入空间中的训练样本集映射到某 果，其中文本频率比值法DFR(document frequency 个高维特征空间中，使得在目标高维空间中这些样 ratio)4以简单、快捷等优点克服了以上几种方法目 本集线性可分，然后再构造一个最优分界面来逼近 前所存在的缺点，综合考虑了类内外文本频率，其计 理想分类结果8.为此，需要在式(2)中增加一个松 算公式为 弛变量专：和惩罚因子C,从而式(2)变为： fD(6,C)=（W-:)xN(6,C) n×N'(t,C:) minwE)=w+C 式中：N为训练集中的总文本数；是C:类中的文 8.t.y:(wx:+b)-1+专：≥0， 本数；W(t,C:)表示类别C:中包含词t的文本数；而 5≥0，i=1,2,…,1. N'(t,C:)表示除去C:以外的其他类别中包含词t的 式中：C为某个指定的常数，控制对错分样本惩罚的 文本数， 程度，C值越大，惩罚越重。 2基于主动学习支持向量机的文本分类 SVM采用不同的核函数K(x,y),可以实现输 人空间中的不同类型的非线性分类问题转化为线性 2.1支持向量机 分类情况，进而产生不同的支持向量算法，引进核函 支持向量机(support vector machines,SVM)是 数以后的最优分类函数为 由Vapnik]提出的一种基于结构风险最小化原理 的机器学习方法[61.在最简单的情形中，线性SVM fx)=sigm(∑a:K(x·y)+b). 通过学习得到一个超平面，该超平面以最大分类间 2.2主动学习算法 隔将正样本集合与负样本集合分离开，此处的间隔 根据对训练样本处理方式的不同，可将学习方 (margin)是指超平面与距离它最近的正样本和负样 法分为主动学习和被动学习2类.主动学习在学习 本之间的距离。 过程中可以根据学习机推进的情况，选择最有利于
.264 智能系统学报 第6卷 分类器性能的样本来进一步训练分类器，这样它能 本进行分类，根据分类结果，删除其中表现差的一个 有效地减少评价样本数量；而被动学习只是随机地 类别，由剩下的类别形成新的队列； 选择训练样本，被动地接受这些样本的信息进行学 While(队列中所剩下的类别非单一类别) 习.引入主动学习目的主要是从减少评价样本所需 3 的代价，最大的优点是通过仔细、合理地选择训练样 取新队列的首个和最后一个类别对未知样本进行 本后，需要的实际训练样本数量将大大减少，评价样 分类，保留较优的结果类别，删除次优的结果类别； 本所需的代价也就随之减少. 针对哈萨克文文本的预处理的复杂性和SVM 队列中所剩下的最后一个类别就是得到的最优 方法只与支持向量有关这2个因素，对SVM算法进 类别 行了改进，用主动学习方法9o处理SVM分类器的 算法结束。 训练文本.为了更好地满足分类要求，文本分类模型 1.2,3.4 4 采用多分类模式山 非1 非4 主动学习从形式上是一个循环反复的过程，应 2,34 2.4 1.2.3 用SVM方法实现主动学习，采用何种算法有效地筛 选训练样本，以便快速进入训练阶段是研究的关键 非2 非4 非3 主动学习首先根据先验知识或者随机地从未带类别 3.4 标注的所有候选样本集中选择少量样本并标注它们 3 2.3 1.2 的类别，构造初始训练样本集，确保初始训练样本集 中至少包含有一个正例样本和一个负例样本.利用 初始训练样本集中这些带类别标注的样本训练一个 图44个单分类器用DAGSVM融合 分类器，在该分类器下，采用某种采样算法，从候选 Fig.4 Four single sorters fused with DAGSVM 样本集中选择最有利分类器性能的样本，标注类别 并加入到训练样本集中，重新训练分类器，再次选择 3 实验结果 最有利分类器性能的样本.重复以上过程，直到候选 通常分类器所选的训练文本集和测试文本集的 样本集为空或达到某种指标「2] 质量是最直接影响分类精度的因素之一，一般要选 文献[13]提出一种新的多类学习模型，即决策 择公认的、通用的语料集，而且数据集中所选类别应 有向无环图(directed acyclic graph,DAG).每条边都 是典型的、含有明显类别信息的文本类别，并且所选 有方向、且不存在任何回路的图称为有向无环图，图 文本应该是客观存在的各个类别中的实际文本.但 中惟一没有人度的节点则是DAG的根.在分类任务 是，对于哈萨克文文本分类器来说，目前还没有公认 中，可以引入此种数据结构构造SVM分类模型，即 的标准语料集，本文所构建的语料集尽管没有达到 有向无环图SVM(DAGSVM).对于DAGSVM,输入 上述标准，但作为初期研究哈萨克文文本分类处理 一个样本，从根节点开始判决，一直访问到叶子结点 尚有研究意义.通过人工翻译等方法，笔者收集了一 就是要得到的结果类别，这样对于N类的问题，要 部分哈萨克语文本的内容，并做了人工分类.实验的 进行N-1次判别.DAGSVM最大的优势在于能够 圳练集中共有5个类别，分别是交通、体育、医药、艺 准确定位结果类别，具有准确性较高的特点[4.如 术、政治，其中交通包含8篇文章、体育包含12篇文 图4是具有4个类别的DAG 章、医药包含10篇文章、艺术包含10篇文章、政治 有向无环图SVM算法的中心思想如下. 包含10篇文章. 输入：未知类别信息文本。 3.1词统计及文档的向量化表示 输出：最优的结果类别 图5为每类文档词频统计结果，即分别在交通 算法： 类、体育类、医药类、政治类、艺术类文档里词的总出 首先对未知文本采用主动学习SVM进行类别 现次数. 的分类； 图6为词权重计算结果，词前数字表示各个词 C排成队列，i=1,2,…,n;/将所有的类别 的权重，词的权重表明该词在判别文档类别所属过 按任意顺序排成队列 程中的重要程度 取首个和最后一个类别对应的分类器对未知样
第3期 古丽娜孜，等：一种基于主动学习支持向量机哈萨克文文本分类方法 ·265 5 也 2点 图5词频统计结果 Fig.5 Statistical results of term frequency .D131378917368171 R黑 0.018152日947309421 》.01315794730湖421c 0.0131529473421 00243902439z439y 03585155155. .013157B947309421 0.06658516585316585. 0.014925373134328 .013157H9473f84213 0213424319.249 0263157894736842.节 .223B0597014925C 947368421 0.24390249902439。 0024390241902393 1.013157097362 07247115425 0a7247H15042 0.01875L 0072463711s9425se 091875 .007246378"150425 0.0187316 0SG7g710H440278 月02I7013B434T28 0.01875 07171304372自. 0.00625-3 0.012359 0298550224f378 0.03754:3 D0289855072463768 0.025450 0144275231411 0.0065.5 0.0072463701159424J 0072437611642.LL 0.0t8753-小 图6词权重计算结果 Fig.6 Term weight computed results 图7为生成的文档向量.它是文档的特征向量 svmtrain.exe、根据已有SVM模型对数据集进行预 表示，冒号前的数字表示特征词的编号，冒号后的数 测的svmpredict..exe以及对训练数据与测试数据进 字表示生成的文档的特征向量， 行简单缩放的svmscale.exe.它们都可以直接在 DOS环境中使用，也便于研究者根据需要进行改进 h.01203914i3:.0557497257h:0.0431371972767:04 1744 (譬如设计符合自己特定问题需要的核函数等) H69019441470.010295063140.301 11920.93899461944130.030电98691944104：.69205991327062 通过执行svmtrain.exe实现对训练数据集的训 019441390.900305091944240.0.005 练，可获得如图8所示的SVM模型文件， 0.00991g41T:0.1g电33ta4430:0.50300gn99101: ,G19167313-14:001567475760,4615367497237674 svmn-lype 7940413130.00711m447794641313:0.0g75109447744413140-0.C0 nr-class 3 lotat-sv 50 图7文本向量文件 n-5yn1z101010 Fig.7 Text vector files 0.903080R0130:0.90:50g000140:0.8001099141:0.9030a909142 3.2分类器的模型表示 207:0.9030p附20周E0.00303999209:0.988999Z0:.903089992 分类器在整个文本分类系统中处于核心地位， 图8分类器模型文件 本文采用了台湾大学LibSVM的开源代码.LibSVM Fig.8 Classifier model file 在给出源代码的同时还提供了Windows操作系统下 根据训练获得的模型，可对数据集进行预测.经 的可执行文件，包括：进行支持向量机训练的 svmpredict分类后，在存放结果的文件中会出现一列