人工鱼群优化的维吾尔文文本特征选择方法

吴冰冰，哈力旦·阿布都热依木，阿丽亚·艾尔肯，何　燕

(新疆大学 电气工程学院，新疆 乌鲁木齐 830047)



人工鱼群优化的维吾尔文文本特征选择方法

吴冰冰，哈力旦·阿布都热依木，阿丽亚·艾尔肯，何燕

(新疆大学 电气工程学院，新疆 乌鲁木齐 830047)

特征选择是文本分类中的关键步骤，对分类结果产生直接的影响。本文分析了人工鱼群算法的觅食行为、群聚行为和追尾行为等基本原理。结合维吾尔文文本特征提取原理，提出了一种改进的人工鱼群算法，并将其运用到维吾尔文文本特征提取当中。为了加快鱼群的收敛速度，引入了主动改变视野的策略，同时，为了避免算法陷入局部最优，还在算法中加入了变异策略。将特征选择后的样本集输入到不同的分类器中进行仿真实验。实验结果表明：改进的人工鱼群算法能够使分类的准确率达到94.5%。

维吾尔文；文本分类；特征选择；人工鱼群算法

0　引言

文本分类技术是信息检索领域研究的重点，也是数据挖掘的一个主要分支[1]。研究维吾尔文文本分类技术有利于中国少数民族文化在互联网上的健康传播。在文本分类过程中，特征选择的好坏会对分类器的分类效果产生直接的影响，因此，特征选择一直是文本分类研究的重点。近年来，随着智能技术的迅猛发展，遗传算法、蚁群算法和粒子群算法都已经应用到文本分类中，并取得了较好的成果。文献[2-3]分别把遗传算法和粒子群算法应用到文本特征选择中，不仅降低了特征维数，而且提高了文本的分类性能。文献[4]用信息增益直接估计每个类的特征权重，进而筛选出对文本分类区分度大的特征项。文献[5]采用改进的人工鱼群算法实现了数据聚类。文献[6]采用人工鱼群算法实现了对文本分类器的优化，该算法较经典支持向量机算法和基于蚁群算法的直推式支持向量机算法具有更高的分类性能。文献[7]采用人工鱼群算法选择出最优的特征子集，提高了支持向量机算法的分类精度。

利用群体智能优化算法进行特征选择存在已久，其中，遗传算法和粒子群算法等经典算法均已有成功的应用。但是在不同的应用场合中，都存在各自不同的缺点。遗传算法以生物进化为原型，具有收敛性好和鲁棒性高等优点，但是处理文本分类这种高维度的计算问题，容易陷入“早熟”。粒子群算法虽然具有搜索速度快、效率高和算法简单等优点，但是具有后期全局收敛差的缺点。文献[8]首次提出了一种基于动物自治的优化方法，即鱼群算法。该算法通过构造人工鱼群来模仿鱼群的觅食行为、群聚行为和追尾行为，从而实现优化的目的。本文利用人工鱼群算法具有全局收敛性的优点，通过改进人工鱼群移动的3种行为来改善鱼群收敛速度慢和时间复杂度高的问题。改进的人工鱼群算法在文本特征选择中不仅具有良好的全局收敛性能，还具有较快的收敛速度。

1　人工鱼群算法在维吾尔文文本特征选择中的应用

采用人工鱼群算法对维吾尔文文本进行特征提取的模型如图1所示。从图1可以看出：该算法是以类别为单位，对样本集中的每一个类别采用人工鱼群算法，计算出每个类别各自的特征子集。

1.1文本预处理

图1　维吾尔文文本特征提取模型

文本预处理的主要目的是生成n个特征池，具体步骤为：

(Ⅰ)维吾尔文组词计算。为了使维吾尔文组词算法具有更高的组全率(组合正确的词/应该被组合的词)和更低的误组率(组合错误的词/组词总数)，本文引入了调解因子α、β，改进的维吾尔文组词算法[10]如下：

(1)

其中：Mi_Pf(a,b)为本文改进的组词方法；MI(a,b)为维吾尔文单词a和b的互信息值；P(a,b)为词串ab出现的概率；P(a)和P(b)分别为单词a和b出现的概率；Pf(a,b)为维吾尔文单词a和b的频繁模式匹配值；SWIN(a)·count为单词a在搜索窗口的匹配值；SWIN(a+b)·count为词组ab在搜索窗口的匹配值。该组词算法能有效地提高组全率并降低误组率，部分组词实例如图2所示。

图2　维吾尔文组词实例

(Ⅱ)特征池的生成。首先，对经过组词后的文本进行停用词和低频词过滤；再对维吾尔文单词进行去重处理；最后，按类别生成相对应的特征池。

1.2改进的人工鱼群算法

为了简化人工鱼群算法，提高程序的执行效率，本文舍去了算法中对特征项进行编码的部分，改进了人工鱼的结构。设T=[t1,t2,…,tn]为改进后的人工鱼，其中，ti为特征池中的某一个特征项，人工鱼的n个变量不能重复，并且各个变量是按升序排列的。visual为人工鱼的感知距离，其取值为[0,1]，如果两条人工鱼之间相同的变量个数大于visual×n，则这两条鱼是相互可见的。Fit=f(X)为目标函数，记录当前人工鱼所在位置的食物浓度。tryNum为在觅食行为中人工鱼尝试的次数。

1.2.1初始人工鱼群的产生

初始人工鱼群的产生方法有两种[12-13]：一种是人为给定的初始种群；另一种是随机产生的初始种群。本文初始人工鱼群个体的产生方法主要是随机产生。初始鱼群产生的步骤为：

(Ⅰ)对特征池中的所有特征从0开始进行编号。

(Ⅱ)假设每条人工鱼由n个特征构成，特征池中有N个特征项。随机生成n个[0，N-1] 的不重复整数。

(Ⅲ)对这n个整数按升序排列。

(Ⅳ)判定新生成的整数序列是否已经存在，如果存在，则重新执行步骤Ⅱ和步骤Ⅲ；反之，则成功生成新的人工鱼。

1.2.2觅食行为的改进

visual⟸visual+0.1，visual<1。

(2)

如果找到新的状态更好，则继续增大visual的值，直到尝试的次数等于tryNum，则停止觅食行为。

1.2.3群聚行为的改进

(3)

1.2.4追尾行为的改进

1.2.5适应度函数的设计

本文的人工鱼群算法是以类别为单位，通过人工鱼的适应度值来衡量与该类别的相似度，即人工鱼的适应度值越高，则说明该人工鱼的状态越能代表该类的特征子集。因此，适应度函数的设计应考虑以下两点：

(Ⅰ)从总体上来看，采用平均相似度来衡量人工鱼的状态与类别的近似程度，其计算式为：

(4)

其中：sim(Xi,dj)为人工鱼Xi与该类别下的第j篇文本的余弦相似度；N为该类别下的文本总数。

(Ⅱ)从特征项个体来看，如果没有考虑到所选特征间的相关性，将会带来较大的冗余。为了弥补平均相似度算法的缺点，采用带惩罚的互信息特征选择算法来计算特征项之间的相关性，其计算式为：

(5)

其中：I(C;wj)为人工鱼Xi状态的j特征与类别C的互信息值；S为预先选择好有代表性的少数特征子集；I(s;wj)为人工鱼Xi状态的j特征与S集合里的元素s的互信息值；λ为惩罚因数，当λ∈[0.5,1.0]时，算法效果较好；n为人工鱼Xi的维度。

结合式(4)和式(5)，设计出人工鱼群算法的适应度函数，其计算式为:

Fit(Xi)=Sim(Xi)+J(Xi)，

(6)

其中：Sim(Xi)为人工鱼的状态与类别的平均相似度；J(Xi)为人工鱼Xi的内部特征相关性。

1.2.6变异策略的设计

1.2.7人工鱼群算法的设计

改进的人工鱼群算法的执行步骤如下：

(Ⅰ)初始化人工鱼群。利用特征池i，随机生成N条不重复的人工鱼。同时在公告板上记录适应度值最高的人工鱼。

图3　改进的人工鱼群算法执行流程

(Ⅱ)鱼群移动策略。对鱼群中的每条鱼都执行觅食行为，观察移动后的人工鱼是否有进步，即人工鱼适应度值变大。如果有进步，则依次执行追尾行为和群聚行为；反之，则先执行变异策略，然后依次执行追尾行为和群聚行为。再观察人工鱼是否有进步，如果有进步，则更新公告板；反之，再执行一次觅食行为，然后再更新公告板。

(Ⅲ)鱼群结束条件。当鱼群移动的次数达到了设定值，则人工鱼群算法结束，并输出最优的人工鱼。利用最优的人工鱼状态计算出所选择的维吾尔文特征项。

改进的人工鱼群算法具体执行流程如图3所示。

2　实验结果与分析

本文实验中所使用的维吾尔文文本数据集均为本实验室人工收集，数据主要来源于Ulinix网、天山网和新疆政府网等主要维吾尔文门户网站。文献[14]指出文本的分类性能受训练集的特征数、文本数和类别数3项数量指标交互影响，在特征数一定的情况下，各个类别所包含的文本数越多，分类性能越好，训练集的类别数越多，分类性能越差。实验所需样本集的描述信息见表1。

实验采用Java编程语言，eclipse开发平台。采用k最近邻 (k-nearestneighbor，KNN)分类算法分类器和控制变量法计算3个主要参数对文本分类的影响。实验结果表明：当鱼群的数量和迭代次数较小时，容易陷入局部最优解；但过大时，会提高程序的时间复杂度。鱼群迭代的次数呈抛物线状，当迭代次数为20时，对文本分类的效果最佳。因此，当人工鱼的维度为100、鱼群数量为80、人工鱼的视野取0.7、在觅食过程中每条人工鱼尝试的次数为15次、迭代次数取20时，人工鱼群算法提取出来的特征最好，能够使KNN分类器的分类准确率达到94.5%。

表1　样本集的描述信息

为了更好地分析改进算法对分类器性能的影响，本文采用准确率来进行描述，同时与当前主流的特征选择算法进行了实验对比，结果见表2。

表2　各特征选择算法的分类准确率比较 　 %

从表2可以看出：本文提出的改进的人工鱼群算法比其他几种特征选择算法具有更高的分类精度。主要原因为人工鱼群算法是以寻找出与本文类别最相似的特征子集为寻优目的，这样选取的特征子集能更好地代表该类别。同时，改进的人工鱼群算法能达到良好的全局收敛，其性能优于标准人工鱼群算法。改进的人工鱼群算法对KNN分类器的性能影响最大，其次是贝叶斯分类器，最后是质心分类器。

3　结束语

基于人工鱼群算法的特征选择方法可选出更能代表该类的特征集，能够显著地提高分类器的分类性能，仿真实验验证此方法具有有效性和可行性。虽然人工鱼群算法在理论上已经比较成熟，但是在数据挖掘和文本分类等领域的应用还有很大的研究空间。

[1]苏金树,张博峰.基于机器学习的文本分类技术研究进展[J].软件学报,2006,17(9):1848-1859.

[2]路永和,梁明辉.遗传算法在改进文本特征提取方法中的应用[J].现代图书情报技术,2014,245(4):48-57.

[3]路永和,曹利朝.基于粒子群优化的文本特征选择方法[J].现代图书情报技术,2011(7):76-81.

[4]MALIKH，FRADKIND，MOERCHENF．Singlepasstextclassificationbydirectfeatureweighting[J].Knowledgeandinformationsystems,2011,28(1):79-98.

[5]CHENGYM,JIANGMY,YUANDF.Novelclusteringalgorithmsbasedonimprovedartificialfishswarmalgorithm[C]//ProceedingsoftheSixthInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.2009:141-145.

[6]齐芳,冯昕,徐其江.基于人工鱼群优化的直推式支持向量机分类算法[J].计算机应用与软件,2013,30(3):294-296.

[7]LINKC,CHENSY,HUNGJC.Featureselectionforsupportvectormachinesbaseonmodifiedartificialfishswarmalgorithm[M]//UbiquitousComputingApplicationandWirelessSensor.Netherlands:Springer,2015:297-304.

[8]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.

[9]李敏强,哈力旦·阿布都热依木,闫轲.一种改进型局部二值模式的维吾尔文定位算法[J].河南科技大学学报(自然科学版),2015,36(3):43-47.

[10]吐尔地·托合提,艾克白尔·帕塔尔,艾斯卡尔·艾木都拉.语义词特征提取及其在维吾尔文文本分类中的应用[J].中文信息学报,2014,28(4):140-144.

[11]吐尔地·托合提,维尼拉·木沙江,艾斯卡尔·艾木都拉.基于频繁模式挖掘的维吾尔文智能组词方法[J].计算机应用,2012,32(10):2920-2922.

[12]吴昌友,王福林,马力.一种新的改进粒子群优化算法[J].控制工程,2010,17(5):359-362.

[13]吴昌友.一种新的改进人工鱼群优化算法[J].智能系统学报,2015,10(3):1-6.

[14]李湘东,曹环,黄莉.文本分类中训练集相关数量指标的影响研究[J].计算机应用研究,2014,33(11):3324-3327.

国家自然科学基金项目(61163026)

吴冰冰(1991-),男,四川达州人,硕士生;哈力旦·阿布都热依木(1959-),女,维吾尔族,新疆乌鲁木齐人,教授,硕士生导师,主要研究方向为图像处理和数据挖掘.

2015-11-11

1672-6871(2016)06-0046-05

10.15926/j.cnki.issn1672-6871.2016.06.010

TP391.1

A