一种基于自动阈值鱼群算法的文本聚类方法

摘要

本发明公开了一种基于自动阈值鱼群算法的文本聚类方法，通过计算文本特征向量的相似度矩阵，采用相似度矩阵的每行元素获得每个文本的初始等价划分阈值，从而对文本进行初始等价划分，进而确定初始聚类数目和初始聚类中心；结合采用人工鱼群算法，根据全局最优和局部最优信息更新每条人工鱼的状态，以寻找全局最优聚类中心，对初始聚类结果再聚类。由于采用自动获取阈值的方法得到初始聚类数目和初始聚类中心，并通过人工鱼群算法寻找全局最优聚类中心，本发明克服了传统聚类方法对初值敏感、仅依靠局部数据特性等弊端，可提高文本聚类的准确度与智能性。

主权项

1.一种基于自动阈值鱼群算法的文本聚类方法，其特征在于包括以下步骤：（1）、对N个文本对象进行预处理，包括中文分词、去停用词、词频统计、特征项提取、文本向量化，得到文本对象的特征向量：$x_i=\underset{r=1}{\overset{R}{\Sigma }}{l}_{r,i}{a}_r;$（2）、根据N个文本对象的特征向量计算每个文本对象的初始等价划分阈值Th_i，确定初始聚类数目和初始聚类中心：2.1）、计算文本对象的相似度矩阵S：其中，sim(x_i,x_j),1≤i≤N,1≤j≤N表示文本对象x_i、x_j之间的相似度；2.2）、将相似度矩阵S的每行元素按相似度从大到小排序，得到排序后的相似度矩阵S′：其中，sim(x_i,x_j′),1≤j′≤N表示经排序后文本对象x_i与x_j′之间的相似度；初始等价划分阈值Th_i的计算公式为：${\mathrm{Th}}_i=\left\{\mathrm{sim}(x_i,x_{j\prime })\right|\underset{j\prime }{\mathrm{Max}}[\mathrm{sim}(x_i,x_{j\prime })-\mathrm{sim}(x_i,x_{j\prime +1})]\},j^{\prime }\in \{\mathrm{1,2}...,N-1\}$2.3）、根据相似度矩阵S和初始等价划分阈值Th_i计算每个文本的初始等价划分R_i：R_i={{P_i},{U-P_i}}其中，P_i={x_jsim(x_i,x_j)≥Th_i}，U={x₁,x₂,…,x_i,…,x_N}；2.4）、根据每个文本的初始等价划分R_i进行初始聚类，得到初始聚类结果CR：CR=R₁∩R₂∩…∩R_i∩…∩R_N={c₁,c₂,…,c_K}其中，c_k,1≤k≤K表示初始聚类结果中的一个类，K为初始聚类数目，将c_k中所有文本对象特征向量的平均值作为初始第k类的聚类中心x_ck，初始聚类中心x_ck的计算公式为：$x_{\mathrm{ck}}=\underset{r=1}{\overset{R}{\Sigma }}\overline{l_{r,k}}{a}_r$其中p表示c_k类中文本对象的个数，l_r,s表示c_k类中第s,1≤s≤p_k个文本对象特征向量中第r个特征项的权值，是c_k类中的所有文本对象特征向量中第r个特征项的权值之和；（3）、采用人工鱼群算法对步骤（2）得到的初始聚类结果进行再聚类：3.1）、设置人工鱼条数Total与各人工鱼的初始状态，第m条人工鱼的状态Q_m,m=1,2,…,Total为数据空间中的向量，其形式与文本对象的特征向量一致；设置最大重复尝试次数TryNumber、最大迭代次数IT、将K个初始聚类中心作为初始全局最优人工鱼状态Q_{best_af,k},1≤k≤K；3.2）、对人工鱼状态进行迭代更新：在第t,1≤t≤IT次迭代更新时，依次对每条人工鱼状态进行更新，第m条人工鱼的状态为计算其适应度值$Y_m^t=\frac{\mathrm{num}\left(Q_m^t\right)}{\pi *{\mathrm{Visual}}^2}$其中，表示迭代次数为t时第m条人工鱼的适应度值，表示迭代次数为t时第m条人工鱼视野范围内的文本对象个数；此时前m-1条人工鱼已完成状态更新，即当前时刻其状态为当前时刻全局最优人工鱼状态记为其中离人工鱼距离最近的全局最优人工鱼状态记为第m条人工鱼分别模拟执行以下三种行为：a.觅食行为：在第m条人工鱼视野范围内随机选择一个状态若则第m条人工鱼向和的向量方向前进一步：$Q_m^{t+1}=Q_m^t+\left(\frac{(Q_n^t-Q_m^t)+(Q_{\mathrm{near},m}^t-Q_m^t)}{\left|\right|(Q_n^t-Q_m^t)+(Q_{\mathrm{near},m}^t-Q_m^t)\left|\right|}\right)·\mathrm{Step}·\mathrm{Rand}\left(\right)$其中，Rand()是一个介于0和1之间的随机数；反之，则更新随机选择状态判断是否满足前进条件；如果重复尝试次数达到TryNumber次后仍不满足条件，则第m条人工鱼随机移动一步：$Q_m^{t+1}=Q_m^t+\mathrm{Visual}·\mathrm{Rand}\left(\right)$b.聚群行为在当前时刻的所有人工鱼状态中，计算第m条人工鱼视野范围内的人工鱼同伴数目同伴中心为及其视野范围内同伴的状态的平均值，同伴中心的适应度值为若则第m条人工鱼向和的向量方向前进一步：$Q_m^{t+1}=Q_m^t+\left(\frac{(Q_{c,m}^t-Q_m^t)+(Q_{\mathrm{near},m}^t-Q_m^t)}{\left|\right|(Q_{c,m}^t-Q_m^t)+(Q_{\mathrm{near},m}^t-Q_m^t)\left|\right|}\right)·\mathrm{Step}·\mathrm{Rand}\left(\right);$否则第m条人工鱼再重新执行一次觅食聚群行为；c.追尾行为：在当前时刻的所有人工鱼状态中，比较第m条人工鱼视野范围内各人工鱼同伴的适应度值，找到适应度最大值及其对应的同伴状态若则第m条人工鱼向和的向量方向前进一步：$Q_m^{t+1}=Q_m^t+\left(\frac{(Q_{\max ,m}^t-Q_m^t)+(Q_{\mathrm{mear},m}^t-Q_m^t)}{\left|\right|(Q_{\max ,m}^t-Q_m^t)+(Q_{\mathrm{mear},m}^t-Q_m^t)\left|\right|}\right)·\mathrm{Step}·\mathrm{Rand}\left(\right)$否则第m条人工鱼再重新执行一次觅食行为；第m条人工鱼在模拟执行三种行为后得到三个备选更新状态三个备选更新状态，比较三个备选更新状态的适应度值，如果其中最大的适应度值高于当前适应度值且只对应一个备选更新状态，则将第m条人工鱼更新为最大适应度值所对应的备选更新状态；如果其中最大适应度值高于当前适应度值且对应一个以上备选更新状态，则任意选择一个备选更新状态进行更新；如果其中最大的适应度值不高于当前适应度值则第m条人工鱼状态保持不变；本次更新中第m条人工鱼的最终更新结果记为如果此时人工鱼状态的适应度值高于距离最近的最优人工鱼的适应度值则用代替所对应的全局最优人工鱼否则全局最优人工鱼状态保持不变；当迭代次数达到最大迭代次数IT时，人工鱼状态迭代更新结束，得到最终全局最优人工鱼状态$Q_{\mathrm{best}\_\mathrm{af},k}^{\mathrm{IT}},1\le k\le K;$3.3）、根据人工鱼状态计算最终聚类中心：对于最终全局最优人工鱼，设定全局最优人工鱼聚类阈值，计算第一条最终全局最优人工鱼与其他最终全局最优人工鱼之间的距离，将距离小于聚类阈值的最终全局最优人工鱼与第一条最终全局最优人工鱼归于一类；在剩下的最终全局最优人工鱼中按顺序选择第一条，计算其与剩下的其它最终全局最优人工鱼的距离，将距离小于聚类阈值的最终全局最优人工鱼与该最终全局最优人工鱼归于一类；依此类推，直到将所有最终全局最优人工鱼归类；最终得到的人工鱼类的个数为最终聚类数目H，将每个人工鱼类中所有最终全局最优人工鱼成员状态的均值作为该类的最终聚类中心X_ch,1≤h≤H；3.4）、计算每个文本对象与H个最终聚类中心的距离，将文本对象归入与其距离最近的最终聚类中心所对应的类中，得到文本对象的最终聚类结果C_h,1≤h≤H。