一种基于黑洞算法的模糊C均值文本聚类方法

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

柳玉辉¹, 王伟超¹, 孟磊²
1. 东北大学计算机科学与工程学院, 辽宁沈阳 110169;
2. 东网科技有限公司, 辽宁沈阳 110169
收稿日期：2016-03-14
基金项目：国家高技术研究发展计划项目(2015AA016005)。
作者简介：柳玉辉(1966-)，男，山东烟台人，东北大学副教授。

摘要：FCM算法应用于文本聚类时, 由于初始聚类中心点选择的随机性，以及容易陷入局部最优的问题，导致文本聚类效果较差.为了提高FCM算法的聚类精度, 提出了采用黑洞算法寻找FCM最优初始聚类中心的方法.黑洞算法是一种启发式优化方法, 在FCM初始聚类中心寻优的过程中, 始终保持黑洞为全局最优解, 最终发现FCM的最优初始聚类中心.实验结果表明, 基于黑洞算法的FCM文本聚类方法可以解决FCM算法对初始中心点敏感和容易陷入局部最优的问题, 聚类精度明显提高.
关键词：模糊C均值黑洞算法文本聚类参数搜索初始聚类中心
Document Clustering of Fuzzy C-Means Based on Black Hole Algorithm
LIU Yu-hui¹, WANG Wei-chao¹, MENG Lei²
1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2. Neunn Technology Co., Ltd, Shenyang 110169, China
Corresponding author: LIU Yu-hui, E-mail: liuyh@neusoft.com
Abstract: When fuzzy c-means (FCM) algorithm is applied to document clustering, the result is not ideal because of its initial cluster center points' random selection and falling into the local optimal solution easily. Aiming at improving the FCM's clustering accuracy, a method is proposed which uses the black hole algorithm (BHA), a heuristic algorithm, to find FCM's optimal initial clustering centers. During searching for the FCM's best initial clustering centers, the black hole is considered as the optimal option, and the FCM's best initial clustering centers can be found. The experiment's results show that the document clustering of FCM based on black hole algorithm can solve the problem that FCM is sensitive to initial centers and easy to fall into the local optimal solution, and finally, the clustering accuracy is improved significantly.
Key Words: fuzzy c-meansblack hole algorithmdocument clusteringparameter searchinginitial clustering center
文本聚类是用于自动话题提取、信息检索、信息推荐等领域的基本方法.聚类的最终目标是将数据集的内部结构信息划分成为簇结构, 使得同一个簇内部的数据集有较高的相似度, 同时不同簇之间的数据集有较低的相似度.
模糊C均值(FCM)算法是划分聚类算法之一, 在处理大数据集时具有较好的效果, 但是需要提前确定簇数和随机初始化聚类中心, 使聚类结果容易陷入局部最优解.
FCM算法初始值的随机选取容易使该算法陷入局部最优，针对这一问题, 国内外学者给出很多解决方案.文献[1]给出了FCM算法2000年至2014年的研究状况.除此之外, Mekhmoukh等^[2]提出采用粒子群算法寻找FCM最优初始聚类中心的方法, 但是粒子群算法容易过早收敛, 以至于陷入局部最优解^[3].Wang等^[4]采用自适应粒子群算法解决FCM算法对中心点选择敏感的问题, 一定程度上改进了粒子群算法, 但算法性能仍有提高的空间.Ding等^[5]提出一种将遗传算法与基于核函数的FCM融合的方法进行聚类, 但是遗传算法在种群进化的过程中, 多样性容易丢失, 存在收敛过早的现象^[6].Naik等^[7]提出用TLBO算法来优化FCM算法的聚类中心, 但该算法解决高维复杂问题时, 收敛速度慢且容易陷入局部最优^[8].
黑洞算法^[9]是根据自然界的黑洞现象生成的一种启发式优化方法, 现阶段已被用于配电网潮流计算^[10]、图像处理^[11]、参数寻优^[12]等领域, 具有寻优精度高、容易达到全局最优等优点.Hatamlou等^[9]将黑洞算法与k-Means, PSO, GSA, BB-BC聚类算法做对比, 证明了黑洞算法应用于数值型数据中具有良好的聚类效果.本文将黑洞(BH)算法与FCM算法相结合, 并引入到文本聚类领域中, 提出了一种BH-FCM聚类方法.
1 基于LDA的文本特征提取1.1 LDA模型LDA模型^[13]是一种常用的文本生成模型, 它的图模型如图 1所示.
图 1(Fig. 1)

图 1 LDA图模型Fig.1 Graphical model of LDA

图 1中, w_in表示第i个文档的第n个词语; θ_i表示了第i篇文章的主题分布; φ_k表示第k个主题的词分布; z_in表示第i个文档的第n个词的主题; α，β分别是文档主题分布与主题词分布先验分布的超参数.LDA模型的生成过程如下:
① 对所有设定的主题k∈[1, K], 随机初始化φ_k~Dir(β);
② 对所有存在的文档i∈[1, M], 随机初始化θ_i~Dir(α)和N_i~Poiss(ξ);
③ 对步骤② 中的每篇文档, 选择其所有的词项n∈[1, N_i], 采样z_in~Mult(θ_i)，w_in~Mult(φ_zin).
1.2 文本特征提取吉布斯采样之后, 可以得到矩阵Θ, Θ=(θ₁, θ₂, …, θ_i, …, θ_M)^T, M是数据集中文本总数, θ_i为K维的向量, K是预先设置的主题数目.
文本聚类中, 不同的文本特征提取方法对文本数据挖掘的精度有较大的影响.由LDA得到的模型Θ不仅是每个文本在各个主题上的概率, 也可以看成是每个文本在隐主题空间维度上的特征值, 当处理的文本数据较长时, 可以有效降低提取出的特征的维度.因此, 本文采用由LDA得到的文本主题矩阵Θ作为文本特征提取的最终结果.
2 FCM算法与黑洞算法2.1 FCM聚类算法FCM算法是基于模糊划分的聚类算法, 即对于适应度函数F, 求使得F值收敛的模糊划分矩阵Y以及聚类中心V.F, Y, V的求解公式如下:

(1)

(2)

(3)

(4)

式中:C为簇数; N为文本总数; p_j表示第j个文本向量; y_ij表示文本向量p_j隶属于第i类簇的程度; V=(v₁, v₂, …, v_i, …, v_C), v_i表示第i个聚类中心; α为加权指数.
FCM聚类算法的执行过程如下:
① 初始化聚类簇数C以及簇中心V;
② 根据式(3), 计算新的模糊划分矩阵Y;
③ 根据式(4), 更新聚类中心V;
④ 如果某次迭代与上次迭代的F值的差值小于阈值, 则结束循环, 否则执行步骤②.
2.2 黑洞算法黑洞算法通过适应度值的计算和星体与黑洞间的吸引吸收机制, 在迭代的过程中不断地选择出具有最佳适应度值的星体作为黑洞, 直到最终确定黑洞的位置与适应度值.黑洞与星体间的吸引机制如式(5) 所示.

(5)

式中:l_i(t)表示第i个星体在第t次搜索时的位置; l_BH代表黑洞的位置; rand是0到1之间的随机数.
在算法运行过程中, 各个星体同时向黑洞靠拢.黑洞与星体间的吸收机制通过吸收半径r的计算实现：

(6)

式中: f_BH, f_i分别代表黑洞的适应度值与第i个星体的适应度值; N为星体的总数量.
黑洞算法的执行过程如下:
① 在搜索空间中随机对几个星体初始化.
② 计算各个星体的适应度值, 并从中选择具有最好适应度值的星体作为黑洞.
③ 按照式(5) 移动各个星体.
④ 计算全部星体的适应度值, 如果某星体的适应度值优于黑洞的适应度值, 则让该星体成为新的黑洞.
⑤ 根据式(6) 计算半径, 如果存在某个星体与黑洞的距离小于该半径, 则删掉该星体, 并随机产生一个新的星体.
⑥ 如果算法达到了最大迭代次数或已经收敛, 结束执行过程, 否则执行步骤③.
3 BH-FCM文本聚类算法3.1 聚类流程首先对需要聚类的文本进行中文分词与去停用词处理, 消除高频无用词对特征提取的影响.其次, 使用LDA模型对该文本进行主题建模, 提取出文本的主题特征.然后, 对于不同的文本进行主题相似度的计算并执行BH-FCM聚类算法, 得到最终的文本聚类结果.
BH-FCM算法将黑洞算法与FCM算法相结合, 该算法的设计如图 2所示.
图 2(Fig. 2)

图 2 BH-FCM聚类算法Fig.2 BH-FCM clustering algorithm

BH-FCM算法首先使用黑洞算法进行全局最优初始中心点的寻找.在黑洞算法收敛后, 利用得到的全局最优解作为FCM算法的初始聚类中心, 借以优化FCM聚类算法, 解决FCM聚类算法对初始中心点的选择敏感以及容易陷入局部最优解的问题.
3.2 文本相似度计算在LDA模型中, 因为所有文本在各个隐主题上的分布都是由同一分布中采样得到^[13], 所以本文使用KL散度的对称平滑变形Jensen-Shannon距离来衡量两个文本向量的相似度.Jensen-Shannon距离越小, 说明两文本越相似.对于向量v和e来说, 它们的KL散度定义如式(7) 所示.

(7)

Jensen-Shannon距离的定义如式(8) 所示.

(8)

式中:

.
3.3 黑洞算法的编码结构黑洞算法用于FCM初始聚类中心点寻优时, 关键是如何表示每一个星体及确定适应度函数.由于黑洞算法中每一个星体都是聚类结果的候选解, 所以每一个星体(候选解)的表示如图 3所示.
图 3(Fig. 3)

图 3 星体的表示Fig.3 Representation of a star

图 3中:算法初始化时, Z_ij为星体随机赋值的第i个聚类中心的第j维值, 算法执行结束之后, Z_ij表示最优初始聚类中心中第i个中心的第j维值; C值为簇的数目; k值为文本特征提取向量的维度.
黑洞算法的适应度函数计算如下：

(9)

式中:X=(x₁, x₂, …, x_i, …, x_T), x_i为第i个文本向量; Z=(z₁, z₂, …, z_j, …, z_C), z_j为第j个聚类中心; T为文本向量的总数; C为聚类的簇数.若第i个文本向量属于第j个簇, 则w_ij为1, 否则为0.
4 实验与分析4.1 文本数据选择为了测试该算法的稳定性与有效性, 本文采用复旦大学语料作为聚类测试样本, 随机选择150篇艺术类文本、210篇历史类文本、240篇电脑类文本作为数据集Data1, 150篇运动类文本、210篇政治类文本、240篇经济类文本、260篇农业类文本、240篇环境类文本作为数据集Data2, 100篇艺术类文本、140篇历史类文本、160篇电脑类文本、240篇环境类文本、160篇农业类文本、100篇经济类文本、100篇政治类文本作为数据集Data3.数据集的具体描述如表 1所示.本文采用ICTCLAS^[14]中文分词系统, 在对文本分词处理后去停用词, 使用LDA模型进行文本特征提取, LDA的超参数α通常取0.05, β为0.01.使用内部簇距离之和作为适应度函数值.
表 1(Table 1)

表 1 文本数据集Table 1 Document data sets

数据集	文档数量	隐主题数量	簇的数量
Data1	600(150, 210, 240)	200	3
Data2	1 100(150, 210, 240, 260, 240)	350	5
Data3	1 000(100, 140, 160, 240, 160, 100, 100)	300	7

表 1 文本数据集 Table 1 Document data sets

4.2 文本聚类对比在PSO-FCM聚类算法中, 设置粒子数为50, 设置初始惯性权重w为0.72, 加速系数c₁与c₂设置为1.49.在GA-FCM算法中, 设置个体数为50, 采用单点交叉、交换突变的方法, 交叉概率设置为0.4.BH-FCM聚类算法中, 设置星体个数为50.FCM算法、PSO-FCM算法、GA-FCM算法、BH-FCM算法的文本聚类平均准确率对比如图 4所示.
图 4(Fig. 4)

图 4 各算法的聚类效果对比Fig.4 Comparison of all algorithms for clustering effect

由图 4可知, 在三类数据集上, BH-FCM算法的聚类准确率最高, PSO-FCM算法次之, GA-FCM算法再次之, FCM算法准确率最低.
遗传算法、离子群算法、黑洞算法在Data1上寻找聚类中心点的过程中, 适应度值的变化趋势如图 5所示.
图 5(Fig. 5)

图 5 三种算法聚类过程对比Fig.5 Comparison of three algorithms for clustering process

由图 5可知, 在聚类过程中, 黑洞算法比遗传算法与粒子群算法的收敛速度最快, 且能收敛到一个最优的适应度值, 从而发现最优的初始聚类中心.
综上所述, BH-FCM算法较FCM算法、PSO-FCM算法、GA-FCM算法有更优的效果, 证明了该方法的有效性.
5 结语本文提出一种基于黑洞算法的模糊C均值文本聚类方法BH-FCM.通过对黑洞算法在启发式搜索与聚类算法的研究, 提出使用黑洞算法搜寻FCM算法的最优初始聚类中心, 解决FCM算法容易陷入局部最优的问题.结合LDA模型提取出的文本特征值, 将BH-FCM算法应用于文本聚类领域中, 通过仿真实验, 将该算法与FCM算法、PSO-FCM算法、GA-FCM算法对比.实验结果表明, 黑洞算法能发现最佳的聚类中心, 基于黑洞算法的FCM文本聚类方法具有最高的聚类准确率, 证明了文本提出的方法是有效的.在未来的研究中, 可以对黑洞算法进行改进, 或者采用其他性能更好的启发式算法与FCM算法结合, 提升FCM算法的精确度.
参考文献

[1]	Nayak J, Naik B, Behera H S. Computational intelligence in data mining—volume 2[M]. New Delhi: Springer India, 2015: 133-149.
[2]	Mekhmoukh A, Mokrani K. Improved fuzzy c-means based particle swarm optimization (PSO) initialization and outlier rejection with level set methods for MR brain image segmentation[J].Computer Methods & Programs in Biomedicine, 2015, 122(2): 266–281.
[3]	Kanwar N, Gupta N, Niazi K R, et al. Simultaneous allocation of distributed energy resource using improved particle swarm optimization[J].Applied Energy, 2017, 185: 1684–1693.DOI:10.1016/j.apenergy.2016.01.093
[4]	Wang D, Li Y, Hu Y, et al. Integrated dynamic evaluation of depletion-drive performance in naturally fractured-vuggy carbonate reservoirs using DPSO-FCM clustering[J].Fuel, 2016, 181: 996–1010.DOI:10.1016/j.fuel.2016.05.009
[5]	Ding Y, Fu X. Kernel-based fuzzy c-means clustering algorithm based on genetic algorithm[J].Neurocomputing, 2016, 188: 233–238.DOI:10.1016/j.neucom.2015.01.106
[6]	Yang H J, Hu X. Wavelet neural network with improved genetic algorithm for traffic flow time series prediction[J].Optik—International Journal for Light and Electron Optics, 2016, 127(19): 8103–8110.DOI:10.1016/j.ijleo.2016.06.017
[7]	Naik A, Satapathy S C, Parvathi K. Improvement of initial cluster center of c-means using teaching learning based optimization[J].Procedia Technology, 2012, 6(4): 428–435.
[8]	岳振芳, 高岳林. 一种改进的教与学优化算法[J].兰州理工大学学报, 2015, 41(6): 99–103. ( Yue Zhen-fang, Gao Yue-lin. An improved algorithm for teaching-learning-based optimization[J].Journal of Lanzhou University of Technology, 2015, 41(6): 99–103.)
[9]	Hatamlou A. Black hole:a new heuristic optimization approach for data clustering[J].Information Sciences, 2013, 222(3): 175–184.
[10]	Bouchekara H. Optimal power flow using black-hole-based optimization approach[J].Applied Soft Computing, 2014, 24: 879–888.DOI:10.1016/j.asoc.2014.08.056
[11]	Yaghoobi S, Hemayat S, Mojallali H.Image gray-level enhancement using black hole algorithm[C]// Pattern Recognition and Image Analysis.Piscataway:IEEE, 2015:1-5.
[12]	王通, 高宪文, 蒋子健. 基于黑洞算法的LSSVM的参数优化[J].东北大学学报(自然科学版), 2014, 35(2): 170–174. ( Wang Tong, Gao Xian-wen, Jiang Zi-jian. Parameters optimizing of LSSVM based on black hole algorithm[J].Journal of Northeastern University(Natural Science), 2014, 35(2): 170–174.)
[13]	Blei D M, Ng A Y, Jordan M I. Latent Dirichlet allocation[J].Journal of Machine Learning Research, 2003, 3: 993–1022.
[14]	Zhang H P, Yu H K, Xiong D Y, et al.HHMM-based Chinese lexical analyzer ICTCLAS[C]// SIGHAN Workshop on Chinese Language Processing.Stroudsburg:Association for Computational Linguistics, 2003:758-759.