基于类别覆盖集的改进蚁群算法研究

焦莉娟,宗春梅

(忻州师范学院 计算机系,山西 忻州 034000)

基于类别覆盖集的改进蚁群算法研究

焦莉娟,宗春梅

(忻州师范学院 计算机系,山西 忻州 034000)

结合蚁群算法在解决分类问题方面的优势,以及中文网页内容特征值的离散性特点,提出一种改进的基于蚁群算法的网页分类方法。该算法通过携带类别信息的种群蚂蚁的爬行,在迭代过程中寻找一条最佳路径与之匹配，实现了Web页面的分类。最佳路径通过计算测试文档与每一类别的覆盖集合,进而比较最优覆盖集合得到。其中类别权重计算中引入了文字链接比和标签权值，进一步提高了分类精度。实验证明，引入类别覆盖集的蚁群分类算法能够取得更好的分类效果。

蚁群算法；文本分类；类别覆盖集；词义相似度

0 引言

基于文本分类的网络页面分类是根据页面文本内容,由计算机依照某种分类算法,把文本自动映射到一个或多个预先定义好的类别。网页标记与页面链接是影响网络页面分类的主要元素,采用文本与网页特征有机结合的分类方法是网页分类的研究趋势[1]。目前常用的文本分类方法有支持向量机[2]、朴素Bayes[3]、KNN[4]等。

蚁群算法ACA(Ant Colony Algorithm)是20世纪90年代意大利学者M Dorigo,V Maniezzo,A Colorni等[5]通过模拟真实蚂蚁寻找路径的行为,而提出的一种成熟的模拟进化算法。蚁群算法最初主要用于求解TSP问题、分配问题、Job-shop调度问题等,目前已有学者将其应用于文本分类问题,并取得显著效果。本文利用蚁群算法在解决分类问题方面的优势,将其引入Web页面分类领域,并提出类别覆盖集概念。

1 蚁群算法

研究发现,蚂蚁在寻找食物时,会在走过的路上留下一种分泌物产生气味,用来进行信息交互,以此进行相互合作共同完成任务。后来的蚂蚁会选择气味最重的路径行进并释放同样的分泌物,如此循环往复。由于最短路径上的蚂蚁最先返回蚁穴,这样单位时间内的蚂蚁流量最大,气味挥发量最少,路上留下的气味最重,因而有越来越多的蚂蚁选这条路径,直到所有蚂蚁都趋向这条路径。

用蚁群算法解决经典问题与网页分类问题的关联可描述如下：

(1)一类蚂蚁可对应一个目标类别,该类别名称由分类机制决定。此时应使蚂蚁有针对性地携带某种类别信息。

(2)城市间的距离可对应为特征结点之间存在的类别关联程度,即相似度,其计算公式为[5]：

(1)

(3)信息素对应为结点词条的类别权重。

这样,只要通过带有类别信息的种群蚂蚁的爬行,便可找到每种类别的最佳路径,通过比较选择一条信息素浓度最高的最佳路径所对应的类别即为该文档所属类别。

2 构造分类器

2.1 分类算法

算法基本原理是,当蚂蚁类别与文档类别一致时聚合效果好,生成的聚类数量较少,因而信息素浓度高；相反其类别一致性越差,聚合结果越杂乱,信息素浓度越低。算法中引入类别覆盖集来描述聚类结果。首先使蚂蚁自身带有类别信息并遍历所有结点,将测试文档中的一个特征词条作为一个结点。当某一类蚂蚁k全部迭代完后,便生成一条类别路径Ik作为类别k的覆盖集合,即描述该类别的最优解。所有蚁群迭代结束后,可通过比较每一类对应各自类别覆盖集合上的信息素浓度b得出分类结果,信息素浓度最大者的路径Ik所描述的类别k即为该文档所属类别。

算法实现过程中需要解决如下问题：

(1)确定路径的下一节点。分别计算当前节点与剩余节点的相似度概率积：X=S·Pij,其中S为两点的余弦值,转移概率计算公式为：

(2)

(2)更新结点j的信息素τj。在蚂蚁已经走过的路径上信息量增加的同时,各边路径上的原有信息量还会随时间有一定的丢失。因此更新信息量的公式如下：

(3)

其中,ρ表示信息量τ随时间的推移而衰减的程度。分类问题中期望蚂蚁走过的路径能够对应一个文档类别的覆盖集合,因此本文取△τ=wjk,为类别k对于词条j的权重值。

(3)确定最优覆盖集合。每一个类别覆盖集合记录了此类别对应的一条最优路径的所有结点,通过引入信息素浓度来比较各路径与文本类别的关联程度,即单位距离内信息素最多的路径被认为是与文本类别关联性最强的一条路径,即最优覆盖集合。信息素浓度计算公式为：

(4)

算法描述：①按分类机制取m只类别蚂蚁a1,a2,……,am,将测试文档的特征词条随机散列；②初始化第k类的类别覆盖集为空集φ；③随机选择首结点；④计算当前词条与其余所有词条的相似度转移概率积X；⑤选择X值最大者作为下一词条,并与当前词条连通,更新信息素浓度；⑥重复④、⑤,直到Max(X)小于标准值,转下一步；⑦将通路聚合为一个新结点,该结点信息素为原通路中所有结点信息素之和；⑧重复③～⑦,直到不再产生新聚类为止；⑨重复②～⑧m次,得到m个类别覆盖集合；⑩求每一类别覆盖集的信息素浓度b,其最大值所对应的类别k=argMaxb(k)即为所求类别。

2.2 分类过程

训练过程中,若当前训练文档类别为k,则利用TFID方法计算类别k对于词条i的权重wik。计算时引入“权重因子”可得到一个精度更高的词条权重值。其中权重因子由网页中标签权重和文字链接比的乘积计算得到。训练结果得到一个权重类别词库。

测试过程引入基于类别覆盖集的分类算法将测试语料进行分类，分类过程如图1所示。

3 实验

实验选取了200篇文档,其中140篇作为训练语料,包括财经类40篇、体育类40篇、文化类30篇、军事类30篇、60篇作为测试语料。经过特征提取可得到6 217个特征项,训练过程就是计算这些特征项结点相对于每一类别的权重值w。测试过程中,依照上述算法,对每一篇测试文档进行迭代、计算,并采用国际上通用的准确率、召回率对分类效果进行评估。实验结果如表1所示。表1中参数A、B分别表示蚂蚁种群平均数量和标准值。

图1 分类过程模型

表1 分类结果比较

财经体育文化军事平均值P0．900．790．770．861000．58R0．880．830．800．800．84BPR0．890．810．790．83P0．920．930．960．91AB2000．70R0．900．910．950．920．93BPR0．910．920．960．91P0．920．930．810．915000．90R0．880．910．850．920．89BPR0．900．920．830．91

实验证明,对种群蚂蚁规模、确定是否停止本次迭代的标准值的大小、权重因子等参数的取值都会直接影响分类精度。图2给出了A、B值分别取200和0.70时,算法改进前后分类精度的对比。

图2 引入类别覆盖集前后分类精度对比

4 结语

本文主要研究了用蚁群算法进行文本分类,并提出一种切实可行的分类算法。实验证明,用基于类别覆盖集的改进蚁群算法进行文本分类具有强鲁棒性和优良的分布式计算机制等优势,是一个值得深入研究的课题。种群蚂蚁规模确定以及如何选择最佳相似度、标准值及词性因子等参数,以便达到最优的分类效果等,则是下一步需要解决的问题。

[1] 凤丽洲.文本分类关键技术及应用研究[D].长春：吉林大学,2015.

[2] WANG F,WANG Z,LI Z,et al.Concept-based short text classification and ranking[C].Proceeding of the 23rd ACM International Conference on Information and Knowledge Management.ACM,2014:1069-1078.

[3] 邸鹏,段利国.一种新型朴素贝叶斯文本分类算法[J].数据采集与处理,2014,29(1):11-15.

[4] 钟将,刘荣辉.一种改进的KNN文本分类[J].计算机工程与应用,2012,48(2):142-144.

[5] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.

(责任编辑：孙 娟)

焦莉娟(1978-),女,山西忻州人,硕士,忻州师范学院计算机系副教授,研究方向为自然语言处理、数字图像处理；宗春梅(1977-),女,山西忻州人,硕士,忻州师范学院计算机系讲师,研究方向为数据挖掘。

10.11907/rjdk.162540

TP312

A

1672-7800(2017)003-0054-02