一种改进的基于潜在语义索引的文本聚类算法

侯泽民，巨 筱

(郑州科技学院信息工程学院，河南 郑州 450064)

0 引言

自20世纪90年代以来，计算机网络技术的高速发展，导致信息量迅速增加。人们可以轻易地从Internet、新闻媒体、数字图书馆等数字载体上面获得数目庞大的文本文档。人们可以轻易收集数量庞大的信息，却无法进行精确定位，找到自己真正所需的信息，出现了“数据爆炸但知识贫乏”的怪现象。因此，人们迫切需要一种手段能够高效、快速地获取自己真正所需信息。文本聚类是文本挖掘的研究内容之一，通过文本聚类，可以从海量数据当中挖掘和提取有用信息，提高信息检索的速度和效率。王礼礼[1]曾提出一种基于潜在语义索引的文本聚类算法，其算法在文本聚类阶段使用的是k-means算法。本文提出的基于潜在语义索引的文本聚类算法，在文本聚类阶段使用的是SOM算法，只是在聚类之初，引用了改进的k-means算法的初值，二者有本质区别。SOM算法和k-means算法是目前文本聚类研究中比较常用的2种算法。罗克刚[2]曾对这2种算法从性能上做了一个比较，表明SOM算法的聚类效果要优于k-means算法的聚类效果。实验结果验证了本文算法的优越性。

1 相关技术

1.1潜在语义索引

在传统的文本聚类研究中，文本的表示主要采用向量空间模型[3](Vector Space Model，VSM)。使用计算公式将文本之间相似度表示出来。文本之间相似度量方式为余弦距离。但由于VSM只是词语表面上的匹配，对多义词和同义词非常敏感。例如“电脑”和“计算机”这2个词在很多情况下是同一个意思，但在向量模型中却不能匹配。基于此，本文给出的改进算法中，引入了潜在语义索引理论。

潜在语义索引[4-5](Latent Semantic Index，LSI)或潜在语义分析(Latent Semantic Analysis，LSA)，是1988年S.T.Dumais等人提出的一种新的信息检索代数模型，它运用统计计算方法对文档集中的大量文本进行分析，从而挖掘出文本中词与词之间隐藏的语义结构关系，并用这种潜在的语义结构关系，表示词与文本之间的关系，从而消除词语之间的相关性，降低文本空间维数，节省文本聚类的时间，并取得更好的聚类效果。

奇异值分解[6](Singular Value Decomposition，SVD)是潜在语义索引LSI的一个重要应用算法，是线性代数中一种重要的矩阵分解，可以用它进行多维矩阵的空间降维。

定理1 设A为m×n的矩阵，则存在m阶矩阵U和n阶矩阵V，使得:

其中，S=diag(σ1，σ2，…，σr)，σi＞0。

矩阵A是初始的特征矩阵，在文本挖掘中，A就是t(term)行d(document)列的矩阵，每列是一篇文章，每行是一个单词，每个单元格的值为当前单词在当前文章里的出现次数。U是一个t行r列的矩阵，V是一个r行d列的矩阵，S是一个r行r列的对角矩阵。这里r的大小是A的秩。那么U和V中分别是A的奇异向量，而S是A的奇异值。AAT的正交单位特征向量组成U，特征值组成STS，ATA的正交单位特征向量组成V，特征值组成SST。

本文给出的改进算法中，在聚类预处理阶段，应用潜在语义索引理论和奇异值分解算法来表示文本特征向量，以体现特征词的语义关系并实现特征向量的降维。

1.2 自组织映射网络

芬兰赫尔辛基大学教授Teuvo Kohonen于1982年提出了自组织映射(Self-Organizing Maps，SOM)网络[7-8]。SOM网络是一种无指导学习训练的神经网络，自组织过程其实就是无指导学习过程。自组织映射网络SOM由输入层和输出层(竞争层)组成。输入层通过权值向量将文本信息汇集到输出层各个神经元，输入层的神经元个数与样本维数相同。输出层即竞争层，其神经元节点数可按多种方式进行排列，例如有一维线阵、二维平面阵、三维栅格阵等。

SOM网络的工作原理为:竞争、合作、自适应[9]。

1)竞争。

竞争过程就是选择获胜神经元过程。设m为输入层向量空间维数，输入层空间向量模式记为:

SOM网络中输出层神经元向量空间与输入层向量空间维数相同。所以将输出层神经元节点j向量记为:

其中k为SOM网络输出层神经元节点总数。计算输入向量X与输出层神经元节点之间的距离，距离最小的输出层神经元即为获胜神经元。

2)合作。

合作过程就是根据竞争过程获得的获胜神经元，计算获胜神经元节点的拓扑邻域。

设hj，i为获胜神经元节点i为中心的拓扑邻域，dj，i为获胜神经元节点i与兴奋神经元节点j之间的侧向距离。则 hj，i和 dj，i之 间的关系为:

其中σ为邻域半径，σ是动态变化的，其变化规律如公式(3)所示:

其中，σ0为邻域半径初始值，τ1为常数，表示时间。将σ(n)代入公式(2)可得:

公式(4)中的hj，i(x)(n)称为邻域函数。根据邻域函数hj，i(x)(n)可以计算确定获胜神经元节点的拓扑邻域。

3)自适应。

自适应过程使兴奋神经元通过对自身突触权值的适当改变，以增加它们关于该输入模式的判别函数值。所作的改变使获胜神经元节点对以后相似输入模式的响应增强了。随着对样本数据的反复训练，邻域更新会使得突触权值趋于服从输入向量的分布。

2 改进的基于潜在语义索引的文本聚类算法

2.1 传统SOM算法的局限性

SOM算法是常用的、经典的无导师学习算法，可以将高维向量空间模型转化为二维向量空间表示;抗噪声能力强;能进行并行化处理;可视化效果好。但是SOM算法也存在一些局限性:

1)SOM算法需要提前确定聚类类别数目[10]，即输出层神经元节点的数目和结构层次。

2)SOM网络进行训练时，一些输出层神经元节点的连接权值与输入层模式相差较大，始终不能获胜，成为“死神经元[11-12]”。

3)SOM算法缺乏具体的目标函数[13-14]。

2.2 SOM算法的改进策略

从2.1节内容可以看出，传统SOM算法依然存在着一些局限性。2.1节中提到的局限性1)，在实际聚类过程中，大多数研究者们也只是根据自己丰富的经验和专业的知识来确定聚类类别数目，而且是多次尝试，直至得到正确的结果。这种方法有很大的盲目性和不确定性，若得出错误的聚类类别数目，最终的聚类效果也会很差。基于此，本文针对2.1节内容的局限性1)，给出相应的解决方案:即改进传统的kmeans聚类算法得出聚类初始值，作为聚类类别数目。将此准确聚类类别数目作为SOM网络模型输出层神经元节点数目。

2.3 获取SOM算法聚类类别数目的值

刘远超等[15]改进了传统 k-means算法，提出了一种基于最小最大原则的k-means聚类初始值选择算法，该算法能够确定k-means聚类的初始聚点及聚类类别数目。本文借鉴该改进算法，对传统k-means算法进行改进，得到聚类类别数目，然后应用于SOM算法，作为SOM网络模型输出层神经元节点数目。下面介绍k-means算法的改进策略及算法过程。

假设要将原始文档集聚类成k个模式类，那么首先要选取2个距离最远即余弦相似度最小的聚点x1，x2，而剩余聚点的确定则可通过迭代公式推出。设已经选取确定了m个聚点，则第m+1个聚点可通过公式(5)推出:

在公式(5)中，min、max表示聚点之间的最小最大距离，即用 min{d(xm+1，xr)，r=1，2，…，m}表示2个聚点的最小距离，记为mindist。通过文本聚类规则知道，类内文本之间距离小即相似度大，而类间文本之间距离大即相似度小。公式(5)是一个递推迭代公式，可用来选取下一个聚点。采用深度[16](depth)曲线来描述聚点与最小距离之间的变化。聚点的深度值为该聚点与左邻点的最小距离的差的绝对值和该聚点与右邻点的最小距离的差的绝对值的和，如公式(6)所示。

利用公式(6)，可以得出聚点与深度之间的变化曲线，如图1所示。

图1 聚点-深度变化曲线

从图1聚点与深度之间的变化曲线可以很容易看出，有一临界点深度值最大，临界点所对应的聚点即为真实聚类类别数目的值。

2.4 改进的基于潜在语义索引的文本聚类算法

本文针对传统SOM算法的局限性提出了2个改进策略，引入潜在语义索引LSI解决文本中同义词、多义词的敏感问题，使用改进的k-means初始值选择算法确定聚类类别数目，作为SOM模型输出层神经元节点数目。下面，将具体描述改进的基于潜在语义索引的文本聚类算法。

在文本预处理阶段，通过词根还原、分词、词性标注、听用词过滤、名实体识别、关键词抽取得到词-文档矩阵。然后使用潜在语义索引中的奇异值分解SVD对词-文档矩阵进行分解及降维。

在文本聚类阶段，对传统的SOM算法进行改进，算法流程如下:

1)根据2.3节给出的改进k-means初值选择算法可以得出聚类类别数目值，将此值作为SOM网络模型输出层神经元节点数目值，构建一个二维平面阵列结构的SOM网络模型。

2)初始化，时间步长为 n=0，1，2，…，输出节点权值向量初始值为Wj(0);向量各元素从区间(0，1)上随机取值;学习率初始值尽量取大些，最好接近1;邻域半径初始值也要取大些，尽可能多地包含临近神经元。

3)对于训练样本集中各个输入向量X，求竞争获胜神经元节点i(x):

其中k为SOM网络输出层神经元节点总数。

4)更新获胜神经元节点及邻域内节点的权值向量:

5)更新学习率η(n):

其中η0为初始值，τ2为时间常数。

6)使用公式(4)更新邻域函数值。

7)当特征映射不再发生明显变化或达到最大网络训练次数时退出;否则令n=n+1，转入步骤3)。

3 实验结果及分析

3.1 聚类效果评价方法

本文采用F-measure方法[17]来评价聚类算法的效果。F-measure方法中precision为查准率，表示聚类的准确度，recall为查全率，表示聚类类别文本的覆盖程度。而F-measure方法是它们的调和平均数。

其中:

在求出某个类别的F(r，s)值之后，取各个F值中的最大值，记为Fmax，然后求出所有类别的平均F值，此F值即可表示最终的聚类效果。

其中，T表示测试数据集中所有聚类类别的集合，|t|为测试数据集类别t中的文本数量。F值越大说明聚类效果越好。

3.2 测试数据集

下面选择6个主题的新闻，每个新闻报道含50篇文本，共300篇文本，然后将这些新闻报道处理成纯文本格式。这6个主题共300篇文本即为本文的测试数据集。测试数据集的6个主题分别为:马航失联事件、乌克兰冲突事件、雾霾天气、钓鱼岛事件、食品安全、腾讯入股京东。详细情况如表1所示。

表1 测试数据集数据

3.3 实验结果及分析

下面利用测试数据集，来验证本文算法的优越性。

本文的测试数据集为D1至D6共6个类别300个文本。应用公式(10)来计算F-measure方法中的F值，比较传统k-means算法、SOM算法以及本文改进算法的F值和聚类时间，如表2所示。

表2 不同算法的F值及聚类时间比较

实验结果表明，本文算法得到的F值比传统kmeans算法和SOM算法得到的F值要高。根据F-measure评价方法，可以说明本文算法的聚类效果明显好于传统k-means算法和SOM算法，而且本文算法的聚类时间也更少。

4 结束语

本文首先引入潜在语义索引，消除词语之间的相关性，降低文本空间维数，节省文本聚类的时间，然后，改进k-means文本聚类算法，计算出聚类类别数目，作为SOM算法的聚类类别数目。根据以上策略，本文给出了一种改进的基于潜在语义索引的文本聚类算法。实验结果表明，本算法的聚类效果更好，聚类时间更少。

[1] 王礼礼.基于潜在语义索引的文本聚类算法研究[D].成都:西南交通大学，2008.

[2] 罗克刚.基于自组织映射的文本聚类研究[D].哈尔滨:哈尔滨工业大学，2007.

[3] 郭武斌，周宽久，张世荣.基于潜在语义索引的SVM文本分类模型[J].情报学报，2009，28(6):827-833.

[4] 廖一星.一种新的监督潜在语义模型[J].计算机工程与应用，2009，45(33):117-119.

[5] 常利伟.基于多系统融合的潜在语义分析技术研究[D].沈阳:沈阳航空航天大学，2013.

[6] 吴志媛.基于潜在语义索引的Web文本挖掘[D].无锡:江南大学，2013.

[7] 刘远超.基于动态自组织映射模型的文本聚类研究[D].哈尔滨:哈尔滨工业大学，2006.

[8] 刘旭政，张春荣，陈水生.基于模糊神经网络的拉索耐久性评价模型[J].华东交通大学学报，2010，27(2):8-12.

[9] 刘云峰.基于潜在语义分析的中文概念检索研究[D].武汉:华中科技大学，2005.

[10] Alahakoon D，Halgamuge S K，Srinivasan B.Dynamic self-organizing maps with controlled growth for knowledge discovery[J].IEEE Transactions on Neural Networks，2000，11(3):601-614.

[11] Jin Huidong，Shum Wing-Ho，Leung Kwong-Sak，et al.Expanding self-organizing map for data visualization and cluster analysis[J].Information Sciences，2004，163(1-3):157-173.

[12] 尹峻松，胡德文，陈爽，等.DSOM:一种基于NO时空动态扩散机理的新型自组织模型[J].中国科学(E辑:信息科学)，2004，34(10):1094-1109.

[13] Pal S K，Dasgupta B，Mitra P.Rough self-organizing map[J].Applied Intelligence，2004，21(3):289-299.

[14] Hussin M F，Kamel M.Document clustering using hierarchical SOMATR neural network[C]//Proceedings of the 2003 IEEE International Joint Conference on Neural Networks.2003，3:2238-2242.

[15] 刘远超，王晓龙，刘秉权.一种改进的k-means文档聚类初值选择算法[J].高技术通讯，2006，16(1):11-15.

[16] Hearst M A.TextTiling:Segmenting text into multi-paragraph subtopic passages[J].Computational Linguistics，1997，23(1):33-64.

[17] Ayad H，Kamel M.Topic discovery from text using aggregation of different clustering methods[C]//Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence.2002:161-175.