基于相似度的词聚类算法

《基于相似度的词聚类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2005年第22卷第8期微电子学与计算机93基于相似度的词聚类算法袁里驰钟义信(北京邮电大学信息工程学院,北京100876)摘要:基于类的统计语言模型是解决统计模型数据稀疏问题的重要方法。传统的统计方法基于贪婪原则,常以语料的似然函数或困惑度(perplexity)作为评价标准。传统的聚类方法的主要缺点是聚类速度慢,初值对结果影响大,易陷入局部最优。本文提出了词相似度定义、词集合相似度定义,一种自下而上的分层聚类算法。这种方法不但能改善聚类效果,而且可根据不同的模型选择不同的相似度定义,从而提高聚类的使用效果。关键词:词相似度,词聚类,统计语言模型中图法分类号:TP391.1文献

2、标识码:A文章编号:1000-7180(2005)08-WordClusteringBasedonSimilarityYUANLi-chi,ZHONGYi-xin(CollegeofInformationEngineering,UniversityofPostsandTelecommunication,Beijing100876)Abstract:Cluster-basedstatisticlanguagemodelisanimportantmethodtosolvetheproblemofsparsedata.Conven-tionalstatisticalclustering

3、methodsusuallybaseongreedyprinciple.ThecommonMetricforevaluatingaclusteringal-gorithmisthelikelihoodfunctionorperplexityofthecorpus.Conventionalclusteringalgorithmsoftenconvergetoalocaloptimum,soglobaloptimumisnotguaranteed,andinitialchoicescaninfluencefinalresult.Theauthorstrytosolveabovepro

4、blemsinthispaper.Thispaperpresentsanoveldefinitionofwordsimilarity.Basedonwordsimilarity,thispapergivesthedefinitionofwordsetsimilarity,andproposesabottom-uphierarchicalclusteringalgorithmbasedonsimilarity.Thismethodnotonlyimprovesclusteringeffect,butalsocanchoicedifferentsimilaritydefinition

5、fordifferentcluster-basedmodel,suchaspredictiveclustering,conditionalclustering,andcombinedclustering,thusimprovedtheeffectofusingclusters.Experimentsshowthatwordclusteringalgorithmbasedonsimilarityisbetterthanconventionalgreedyclusteringmethodinspeedandperformance.Keywords:Wordsimilarity,Wor

6、dclustering,Statisticallanguagemodel1引言法的主要缺点是聚类速度慢,初值对结果影响大,在统计语言模型中,词的聚类是解决数据稀疏易陷入局部最优。我们提出的分层聚类算法基于词问题的主要方法之一。由于类的数量远远小于汉语的相似度,词集合的相似度,自下而上,能得到全局中词的数量,因此基于类的n元模型大大缓解了基最优的结果。实验证明聚类效果明显好于传统的聚于词的模型所遇到的数据稀疏问题。更进一步,因类算法。为类的数量少,使得我们统计n大于3的高阶模型成为可能。聚类算法有很多种,但可归结为两种基2常规的贪婪聚类方法本类型:层次聚类与非层次聚类。非层次聚类只

7、是2.1N-gram模型简单的包括了每类的数量,类与类之间的关系不确语言模型最重要的任务是在已知前面一些词定。层次聚类的每一个节点是其父节点的一个子的情况下,预测下一个词。n元模型是通常方法,能类,叶节点对应的是类别中每个单独的对象,常用在已知前面n-1个词的情况下,确定下一个词发生算法有:自下向上与自上向下(凝聚与分裂)。的概率:传统的统计聚类方法通常基于贪婪原则,以语P(wi)=P(wi

8、wi-n+1⋯wi-1)(1)料的似然函数或困惑度作为判别函数。这种传统方实际使用的n元