韩 楠,乔少杰,黄 萍,彭 京,周 凯

(1.成都信息工程大学 a.管理学院; b.软件工程学院，成都 610225；2.四川省公安厅，成都 610014)

网络舆情分析需要对网络社会中群体所表达的情绪、态度、信念等信息进行实时准确的分析和挖掘，以掌握社情民意，应对网络突发的公共事件等[1]。随着互联网的飞速发展，跨语言(多语言)互联网文本信息在我国非常普遍，如藏族同胞经常采用藏文和中文混合使用的方式在网络上发表自己的观点。然而，目前的舆情分析系统主要针对单一语言进行挖掘和预测，跨语言的网络舆情分析的研究成果在国内外鲜有报道，国内目前没有同类技术和相关应用软件出现。因此，研发跨语言的网络舆情分析系统对于分析处理当前快速增长的大规模网络信息具有重要的科学价值及应用意义，也是迫切需要投入人力和物力开发的。

跨语言舆情分析系统旨在满足客户检测网络舆情动态并获得敏感信息的需求，主要功能包括：提取半结构化和无结构化网页、博客、论坛等文本中的主题信息，存储到数据库中；实现跨语言文本信息的预处理，包括分词、提取特征词、建立存储结构等；对提取的半结构化信息进行聚类或分类处理；分析海量的数据中发现主题、检测热点、追踪专题等。

分词是网络舆情分析系统的关键环节，在数据存储和数据分析中起着承前启后的作用。近年来，分词方法的研究备受学者关注，出现了多种具有应用前景的分词方法，其中基于字典的分词方法[2]应用十分广泛，尤其适用于多语言环境下的文本挖掘研究。基于字典的分词具有3个要素：分词字典、文本扫描顺序和匹配原则。这3个要素互相组合生成了许多种分词方法，包括正向最大匹配法、逆向最大匹配法、双向扫描法、逐词遍历法、最佳匹配法等。综合上述方法的优缺点及通用性，本文采用的是正向最大匹配法对爬取的半结构和无结构的文本进行分词，然后进行文本聚类。

文本聚类分析是网络舆情分析的关键步骤，旨在将散乱的抽象对象的集合划分为多个分组，生成的每个分组由相似的对象组成。本文研究的目的在于设计一种高效、准确、支持多语言环境的网络舆情文本聚类模型，为下一步的舆情分析做准备。

为了实现大规模半结构和无结构文本数据的聚类分析，各种聚类算法被广泛提出。随着大数据时代的来临，聚类算法不但要考虑结果的准确性，更重要的是算法如何更加高效地适应实时更新的网络环境。简单传统的聚类算法，如k-means[3]、k-mediods聚类算法，在局部环境的聚类中表现出较好的聚类效果，但运用于复杂和大规模文本数据中效率低下[4]。基于群体智能的聚类算法以其自身的自适、启发等特点，具有分布式处理大数据的优势[5]。

群体智能(swarm intelligence,SI)[6]作为一个新兴的研究领域，最早来自于对自然界中昆虫群居生活的观察和模拟。群居性生物就个体而言并不具有较高的智能，而是通过种群个体之间相互协作，共同完成复杂的工作，群体智能算法成功地解决了组合优化、计算机、机器人、电力系统等众多领域问题。目前，常见的群体智能算法有遗传算法(genetic algorithm,GA)[7]、蚁群算法(ant colony optimization,ACO)[8]、细菌觅食算法(bacterial foraging algorithm,BFA)[9]、人工鱼群算法(artificial fish swarm algorithm,AFSA)[10]、粒子群算法(particle swarm optimization,PSO)[11]、人工蜂群算法(artificial bee colony,ABC)[12]等。

本文借鉴蚁群算法的工作原理，生成智能体并将其随机放置于二维文本空间中，根据信息素的存量指定移动朝向进而实现文本聚类。此外，提出了多种优化策略，改进群体智能算法运行的网格环境和智能体(本文称为agent)。所提的新型群体智能算法具备启发式和自适性的特点，可以实现大规模跨语言文本聚类。

1 基本概念

本节首先给出模型中使用的重要定义，并给出基于群体智能文本聚类的概念。

定义1文本向量。文本被表示成一个多维向量，向量的每一维对应文本中的一个特征词，向量每一维的取值对应特征词在文本中的权重值，即该特征词在文本中的重要程度。一个文本d可以转换成一个多维文本向量，如式(1)所示。

d=〈(t1,w1),(t2,w2),…,(ti,wi),…,(tn,wn)〉

(1)

其中：ti表示向量空间中的特征词；wi表示在文档d中ti对应的权重。将所有的文本文档转化为文本向量，所有的文本向量构成一个特征向量空间。

定义2基于群体智能的文本聚类。假设具有n维向量文本数据集的m个对象{t1,t2,…,tm}以及L个智能体，基于群体智能文本聚类的基本思想是：L个智能体根据簇内相似度高、簇间相似度低的原则，将这m个对象划分到k个簇中，使得评价函数值最小。

利用智能体对文本进行聚类，生成智能体并将其随机放置于二维文本空间中，根据信息素的存量指定移动朝向，若当前网格的信息素存量相同，则随机指定移动朝向。这里给出文本拾起和放下的概念[5]。

定义3文本拾起概率。智能体利用式(2)计算拾起所在区域文本对象的概率

(2)

其中：kp表示智能体拾起文本对象的概率值；f(ti)表示文本对象ti与邻近文本相似度的平均值。

定义4文本放下概率。智能体利用式(2)计算放下所在区域文本对象的概率：

(3)

其中:kd表示智能体放下样本对象的概率;f(ti)表示文本对象ti与邻近文本相似度的平均值。

定义5文本相似度。文本相似度定义为

(4)

其中：s2代表局部环境范围；d(ti,tj)表示文本对象ti和tj之间的距离；α因子用来控制环境相似度的取值范围，决定了相邻对象之间的辨识度。α取值过小会导致簇过于紧凑且空间中出现多个小簇。

为了实现跨语言文本聚类，需要将分词后文本进行特征词提取生成多维文本向量，然后计算所有文本向量之间的相似度生成文本相似度矩阵，计算文本向量相似度利用夹角余弦公式。本文将式(4)修改为

(5)

将1-d(ti,tj)/α修改成为sim(ti,tj)/α。标准的群体智能聚类算法是根据对象之间的距离算出相似度，修改后的公式适应于文本聚类过程中文本相似度的计算。通过式(5)可以发现，文本向量ti与相邻的文本向量tj之间的相似度越高，说明ti的局部相似度越高。

2 基于群体智能的文本聚类算法

基于群体智能的跨语言网络舆情文本聚类模型的工作原理如图1所示：① 参数初始化，主要包括文本空间网格大小、信息素、拾起和放下文本的概率值kp和kd等参数的设置。② 计算智能体所在网格内文本对象相对于其他文本对象的相似度，将其作为文本拾起的概率，当智能体拾起文本的概率大于随机概率阈值，则拾起该文本。如果智能体本身拾有文本，计算当前文本与其所在网格相邻的8个不同区域，即：上、下、左、右、左上、左下、右上、右下中文本的相似性，作为文本对象放下的概率值；如果其值大于随机概率值，智能体便选择放下这一文本。大量的智能体在网格中向不同区域移动，重复上述步骤最终使得评估函数代价最小，完成文本向量聚类的任务。

图1 基于群体智能的文本聚类算法工作原理

算法1基于群体智能的跨语言文本聚类算法

输入：多语言文本特征向量集合T

输出：文本类簇集合C={c1,c2,…,cp}

1.initialTex(); //将文本向量随机分布到网格中

2.initialAgent(); //智能体及网格环境初始化

3.fori=1 toNdo //迭代N次

4. forj←agentNum do //遍历每个智能体

5.r=agent.getLocation(); //r获取智能体所在位置

6. fortk∈T

7. if(ajis unloaded &&ris occupied bytk)

//智能体aj无负载且r处有文本对象tk

8. computef(tk)andppick(tk);

//计算群体相似度f(tk)和拾起概率ppick(tk)

9. if(ppick(tk)>pr) //pr表示随机概率值

10.ajpicks uptk; //智能体拾起文本对象

11. else if(ajhastkandris empty)

//智能体负载对象tk且r处为空

12. computef(tk)andpdrop(tk);

//计算群体相似度和放下概率pdrop(tk)

13. if(pdrop(tk)>pr)//pr表示随机概率值

14.ajdrops offtk; //放下文本对象

15. end if

16. end for

17.aj.randomMove(); //智能体选择随机移动

18. end for

19.end for

20.outputC={c1,c2,…,cp}; //输出聚类结果

算法复杂性分析:通过分析可以得到算法的时间复杂度为O(A×N×M)，其中：A表示智能体的数量；N表示算法的迭代次数；M表示文本的数量。

3 优化策略

标准的基于群体智能的文本聚类算法主要存在如下几个方面的不足：

1)算法1是基于网格空间的聚类算法，文本被随机放置于网格空间中，算法经若干次迭代后，文本向量在网格空间中的分布呈现出聚类结构，即相似的文本向量对象被聚到一起。但是网格空间中的聚类结构并不稳定，智能体在移动的过程中不断形成新的聚类结构，同时也在不停地破坏智能群体的分布。

2)在标准的群体智能本文聚类算法中引入信息素机制，借助信息素引导和控制智能体的移动，可以加快聚类收敛，极大地提高算法的收敛速度，但同时也带来了局部对象过多、智能体容易陷入局部最优等问题。智能体会被引导到信息素浓度较高的区域，由于智能体与环境的正反馈作用，局部的文本向量集中于该区域。

3)利用群体智能实现文本聚类的优越性表现在自组织、启发式和鲁棒性等方面，聚类结果需要从网格空间结构中迭代获取，网格中的聚类效果越明显，越容易获取较好的结果。

优化标准群体智能算法，需要改进算法运行的网格环境和智能体，保证群体智能算法具备启发式和自适应性的特点。本文提出如下优化策略：

策略1在算法运行过程中，逐渐弱化智能体拾取文本对象的能力，以达到网格中聚类结构趋于稳定的目的。具体做法是在迭代的过程中利用梯度下降法逐步降低kp值，使得智能体拾取概率ppick降低，当kp缩小到智能体不再具有拾取对象的能力时，网格中的聚类结构趋于稳定，kp值也无需进一步降低。

策略2添加信息素引导智能体的移动，信息素能够提高智能体与环境的交互能力[13]，基本思路为：在智能体搬运和搜索食物时，每个智能体会在所经过路径上留下一定量的信息素。智能体在选择下一步之前会感应周围环境中的信息素以指导下一步走向，同时信息素以一定速度挥发，最终的结果是环境中形成一条由高浓度信息素构成的路径，最终找到最优路径。智能体在网格环境中移动，会在网格环境中留下大小为σ的信息素，信息素会随着时间的流逝而挥发，挥发因子为η。算法每经过一次迭代，网格环境中的信息素都会按照挥发因子消失一部分。第k+1次迭代后，网格环境中某个位置的信息素由σk变为σk+1，计算方法如式(6)所示。

σk+1=(1-η)*σk

(6)

式中η的取值范围为[0,1]。

针对信息素挥发过快的问题，本文对式(6)进行改进，智能体在经过某一位置时，该位置的信息素σl变为σl+1，计算方法如式(7)所示。

σl+1=σl+(η+N/A)

(7)

式中：N表示算法执行的次数；A表示智能体数量。式(7)中增加了执行次数和智能体数量的比值，可以有效地避免信息素挥发过快的问题。

策略3智能体根据当前位置选择下一位置需要考虑两个因素：信息素感应浓度和方向权重因子。

智能体移动的步长均为1，因此智能体的下一步移动方向为(1,Δθ)，其向各个方位移动的概率是不同的，每个方位的权重值都是由智能体当前移动方向决定的，上一步的位置为(x*,y*)，经过移动方向(1,Δθ)，移动到了(x,y)，可以利用公式(8)计算得到智能体在(x,y)处的移动方向状态θ值。

(8)

网格环境中信息素响应浓度利用如下公式求取：

(9)

其中参数β表示对信息素刺激的敏感程度，用来决定响应函数W(σ)。β控制随机移动的程度，依据这个参数，智能体沿着信息素梯度方向移动。低于β值的信息素浓度并不会很大程度地影响智能体的移动概率，而高于β值的信息素浓度会使智能体更确定地沿着信息素浓度的梯度方向移动。1/γ描述了智能体对信息素的感知能力，即在高浓度情况下对信息素减少的感知能力。参数β和1/γ共同决定了信息素的痕迹。因此，信息素浓度的响应函数由σ、β和1/γ三个参数共同决定。

因此，感应信息素浓度和方向权重因子决定了智能体的下一步移动方向。智能体移动下一步选择临近网格信息素为σ的概率p可用式(10)计算。

(10)

通过上述分析可以发现：实现基于信息素的群体智能文本聚类算法，仅需要将算法1中第17行的智能体随机移动方法改为基于式(6)～(10)的感应信息素移动方法，进而实现对本文所提基于群体智能的文本聚类算法的优化。

4 实验及算法性能分析

4.1 实验数据集及参数设置

实验数据为利用笔者开发的跨语言网络爬取器从中文、英文及藏文门户网站抓取的半结构化和无结构化的文本，并保存到数据库中。对存入数据库的文本信息利用正向最大匹配法进行分词，去噪和提取关键字等操作后得到初始数据集。藏文数据如图2所示。

图2 藏文数据表结构示例

图2为输入数据表，包括7个属性：id，title，content，url，words，num，date。其中:id表示文本编号;title是文本主题;content是文本内容;url是文本的爬取链接;words是经过分词和提取关键字后的关键字序列;num是对应关键字在文本中出现的频数。本文进行跨语言(如藏文和中英文)文本聚类时，主要利用了图2中title、content和words三个涉及文本内容的属性。

本文的实验环境为：奔腾双核2.0 GHz CPU，2 GB内存，开发语言为Java，使用Eclipse SDK1.6。

实验中分别使用k-means、标准群体智能文本聚类算法(swarm-intelligence-based text clustering model，简称SI-Cluster)和应用第3节介绍的优化策略的群体智能文本聚类算法SI*-Cluster算法对多语言文本数据集进行聚类。通过比较聚类算法的准确性和收敛速度，证明本文所提算法的性能优势。

SI-Cluster算法参数设置如表1所示。在如表1所示参数设置下，群体智能算法性能较好。实验中当文本数量增加时，仅需改变网格空间大小和智能体数量即可，无需进行其他人为设置。

表1 基于群体智能的文本聚类算法参数设置

4.2 聚类准确性对比

实验中对聚类的有效性利用查准率P、查全率R和F-measure值[14]进行评价，定义如下:

已知TP表示利用聚类算法正确聚类出的文本；FP为不在本簇被错误聚类出的文本；FN表示包含在本簇但未被聚类到这个簇中的文本；TN表示不在本簇且未被聚类到本簇的文本，于是：

P=TP/(TP+FP)

(11)

R=TP/(TP+FN)

(12)

F-measure = 2PR/(P+R)

(13)

实验选用1 200条数据作为基本测试数据集。这些数据集主要从新浪中英文网站中的3个栏目中爬取的，即体育(sports)、新闻(news)和视频(video)，并自动加上标签用于聚类准确性的判别。对比SI-Cluster和SI*-Cluster算法，聚类准确性结果如表2～4所示。

表2 k-means算法聚类准确性

表3 SI-Cluster算法聚类准确性

表4 SI*-Cluster算法聚类准确性

通过表2～4可以发现：应用优化策略的群体智能文本聚类算法SI*-Cluster的F-measure平均值相比于标准算法SI-Cluster提高13.6%，相比于k-means算法提高44.1%，证明了本文所提出应用优化策略的基于群体智能的文本聚类算法的准确率较传统算法有显著提升，主要原因在于：

1)传统k-means算法需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择不合适，可能无法得到有效的聚类结果。此外，k-means 算法中k是事先给定的，k值的选定非常难以确定。而本文提出的基于群体智能的文本聚类算法，一旦初始参数确定，算法可以自适应训练，通过一定的改进和优化，可以保证找到最优聚类结果。

2)改进的群体智能文本聚类算法SI*-Cluster明显优于标准的SI-Cluster算法，原因在于SI*-Cluster算法通过改进网格环境和智能体，保证了群体智能算法具有启发式和自适应性的特点。在算法运行过程中，逐渐弱化智能体拾取文本对象的能力，以达到网格中聚类结构趋于稳定的目的。此外，添加信息素引导智能体的移动，信息素能够提高智能体与环境的交互能力。

为了进一步验证本文所提算法可以处理多语言文本，如藏文，实验中对藏文文本数据集进行实验，验证k-means、SI-Cluster和SI*-Cluster算法的聚类准确性。实验文本数量分别选取150、300、450、600、750、800、950、1 100。由于采集的数据集分类不均衡，因此利用F-measure方法来评价聚类效果，结果如图3所示。

图3 藏文文本聚类准确性F-measure值对比

通过图3可以发现：对于藏文文本，本文提出的群体智能文本聚类算法明显优于k-means算法。从F-measure值的变化可以看出，3种算法在文本数量较少的情况下，聚类效果都比较好。随着文本数量增加到450，算法的F-measure值不断减小。然而当文本数量增加到一定的程度(当文本数量为600时)，SI-Cluster算法和SI*-Cluster算法的聚类准确性不断提升，说明基于群体智能的文本聚类算法不会受到文本数量的影响，具有比较高的稳定性和自适应性。

4.3 聚类运行收敛性及运行时间对比

本节比较SI-Cluster和SI*-Cluster的算法收敛性并对比收敛时的运行时间，进而说明本文所提出应用优化策略的群体智能文本聚类算法的性能优势。实验中选用4.2节中1 200条中英文半结构化文本数据，为了保证实验结果的客观性和可比性，每组实验对1 200条文本数据集训练10次取F-measure的平均值。实验参数设置如表1所示，SI*-Cluster算法应用第3节优化策略1将kp值设置为0.01～0.001变化，下降梯度设置为0.000 1，实验结果如图4所示。

图4 基于群体智能的本文聚类算法收敛性对比

表5 基于群体智能的文本聚类算法收敛次数及时间

通过图4和表5可以发现：

1)基于群体智能的文本聚类算法会在运行若干步之后达到收敛，即F-measure值达到一定的水平。SI-Cluster算法随着迭代次数的增加，F-measure值的变化波动较大，而SI*-Cluster算法的F-measure曲线相对平滑，而且稳定时的F-measure值明显高于SI-Cluster算法。主要原因在于SI*-Cluster算法应用了第3节优化策略3，智能体移动时根据当前位置选择下一位置结合了信息素感应浓度和方向权重因子，智能体稳定地沿着信息素梯度增加的方向移动，避免了陷入局部最优的问题，具有较高的稳定性。

2)SI*-Cluster算法的F-measure曲线能够平滑且较快地收敛并达到稳定值。原因在于SI*-Cluster算法应用第3节优化策略2，通过添加信息素并有效避免信息素挥发过快的问题，引导智能体快速地找到最优解，具有较快的收敛速度。

5 基于群体智能的文本聚类过程模拟

为了进一步观察应用本文提出3种优化策略前后的文本聚类效果，笔者开发了一个基于群体智能的跨语言文本聚类系统。系统模拟过程中采用第4.2节介绍的3个栏目的中英文文本共90条数据作为待聚类数据，每类含有30个文本向量(相同的颜色表示属于相同的类)，被随机放置在网格环境中。SI-Cluster和SI*-Cluster算法运行结果如图5～6所示。

图5(a)为初始化数据后的网格结构图，图中网格表示网格环境，不同颜色的正方形代表不同类的文本向量。图5(b)是SI-Cluster算法迭代300次之后的网格布局。图5(c)是SI-Cluster算法迭代600次之后的网格布局。可以看出，算法在迭代300次之后所有的文本向量已经被大致划分为11个类，有一定的聚集效果。再次迭代300次之后网格中又出现了一个全新的聚类结构。算法由于没有应用优化策略，所以经过900次迭代后的聚类效果并不好，没有达到收敛，很多不同颜色的文本被错分到一个类簇中。

图6(a)为初始化数据后的网格结构图，图6(b)是SI*-Cluster算法迭代300次之后的网格布局，图6(c)是SI*-Cluster算法迭代600次之后的网格布局，图6(d)是SI*-Cluster算法迭代900次之后的网格布局。可以看出，算法在迭代了300次之后所有的文本向量已经被大致分为11个类，相比于SI-Cluster算法，聚类效果具有显著的提升。迭代了600次之后聚类结构与迭代300次时的聚类结构布局相似且相对收敛，证明了本文所提的优化策略具有较好的稳定性。算法迭代900次之后类簇结构比较明显，网格中构建了9个簇，不同的类之间的重合区域比较少，只需要将聚类结构继续聚合，便可方便地得出最终的聚类结构，进一步说明应用本文提出的优化策略，算法聚类效果好，具有较高的收敛速度。

图6 SI*-Cluster算法不同迭代次数下聚类结果展示

6 结束语

随着Web2.0技术快速发展，Internet网上信息交流变得更加方便和快捷，不同语言和民族的个体可以通过论坛、微博、社交网站及时发表个人观点，研发跨语言的网络舆情文本挖掘技术对于分析和处理当前日益增长的大规模网络本文信息具有重要的科学价值及应用意义。本文充分考虑群体智能算法的启发性、自适应性和鲁棒性，提出了一种基于群体智能的跨语言文本聚类模型。为了克服传统群体智能算法的不足，所提算法应用了3种策略，即：应用梯度下降法弱化智能体拾取文本对象的能力避免陷入局部最优解，添加信息素引导智能体移动并有效避免信息素挥发过快的问题，智能体从当前位置选择下一位置考虑信息素感应浓度和方向权重因子。大量实验证明本文所提算法具有较高的聚类准确性和较快的收敛速度。

未来工作将从以下几个方面展开研究：① 将所提的文本聚类方法应用于大规模网络舆情文本挖掘，通过分析网络文本预测可能潜在的突发事件；② 借鉴蜂群等其他更加智能的群体算法，进一步提高文本聚类的准确性；③ 对算法进一步优化，提高群体智能寻找最优解的速度，及算法收敛速度。