基于Synonyms、k-means的短文本聚类算法

回玥婷 夏懿嘉 陈紫荷 佟鑫

摘要：当今社会，网络搜索成为人们获取资讯的主流。短文本因特征信息不足且高维稀疏等特点，导致传统文本聚类算法应用于短文本聚类时效率低下。为此，我们采用为关键词以及k-means和synonyms相结合的方法，提高主题归类精确度。实验证明，我们提出的s-k（Synonyms-k-means）主题聚类算法不仅有效归类主题，而且能挖掘出词语的潜在含义。

关键词：文本聚类;短文本;k-means;synonyms

中图分类号：TP301        文献标识码：A        文章编号：1009-3044（2019）01-0005-02

1 引言

网络社交平台的广泛应用，使得人们越发偏向通过阅读屏幕上的文本内容获得自己想要了解的信息，网络搜索成为人们获取资讯的主流，以提高用户的使用舒适度为目的，国内外的研究人员针对主题检索和文本聚类方法在不断地进行完善。如何提高文本聚类的准确度是研究人员需要继续改进的问题。互联网的信息呈现多元化，文本内容冗杂不一，并且微博等短文本具有文本短小的特征，针对中文新生词语词义以及主题的歧义之特点，传统的文本检索方法不足满足当前用户的需求。因此，得出一种更加快速、高效的短文本聚类方法显得极为迫切。

通过更有效分析词义和句意是提高文本聚类准确度的关键点。最初由中国餐厅模型为我们了解文本聚类建立了形象的立体概念，但此模型欠缺之处主要在于文本内容和表达方式存在语义词义的差异，因此容易出现主题分类偏差的现象。文献【1】总结得出文本聚类目前存在的，高维稀疏、近义词和多义词技术难点，这三个文本数据所特有的问题使得文本聚类具有相当高的时间复杂度，而且极大干扰了聚类算法的准确性。文献【2】提出微博主题检索模型，利用文本聚类和LDA潜在主题发现相结合的检索模型，以缩小检索空间，使其适用于中文微博短文本的处理和分析，实现了微博信息的有效检索。然而，从挖掘的类簇中看，潜在主题仍旧较为单一。

针对传统文本聚类方法存在的词义分析不确切的不足，我们在目前已有的基础上，采用k-means和synonyms相结合的算法，该算法具有更大的词汇量，更便于针对中文词语进行语意辨析，通过计算强化了词语之间的近似度，有效地进行近义词的辨析，提高了文本类簇主题的精确度，实现了对短文本主题进行更加快速准确的检索，以最大程度满足用户需求。

2 算法内容

2.1文本预处理

分词处理：使用结巴分词。结巴分词基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 （DAG）;采用了动态规划查找最大概率路径， 找出基于词频的最大切分组合;对于未登录词，采用了基于汉字成词能力的 HMM 模型，采用Viterbi 算法;主要能够做到分词，添加自定义词典，基于TF-IDF算法及TextRank算法的关键词提取，词性标注，并行分词，Tokenize：返回词语在原文的起止位置，ChineseAnalyzer for Whoosh 搜索引擎，命令行分词。

分词过后，将得到的分词遍历一下载入的停用词表，去掉停用词。停用词主要包括英文字符、数字、数学字符、标点符号及使用频率特高的单汉字等。将停用词扔掉减少了索引量，增加了检索效率，提高检索的效果。

2.2 TF-IDF关键词提取

TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。TFIDF的主要思想是：如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。①

3 改进k-means算法

K-MEANS算法是输入聚类个数k，以及包含 n个数据对象的数据库，输出满足方差最小标准k个聚类的一种算法。k-means 算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。

基本步骤：

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心;

（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

（3） 重新計算每个（有变化）聚类的均值（中心对象）;

（4） 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止;如果条件不满足则回到步骤（2）。

聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。②

Synonyms是一个开源的中文近义词工具包。可以用于自然语言理解的很多任务：文本对齐，推荐算法，相似度计算，语义偏移，关键字提取，概念提取，自动摘要，搜索引擎等。目前很缺乏质量好的中文近义词库，于是便考虑使用 word2vec 训练一个高质量的同义词库将“非标准表述”映射到“标准表述”，这就是 Synonyms 的起源。在经典的信息检索系统中，相似度的计算是基于匹配的，而且是 Query 经过分词后与文档库的严格的匹配，这种就缺少了利用词汇之间的“关系”。而 word2vec 使用大量数据，利用上下文信息进行训练，将词汇映射到低维空间，产生了这种“关系”，这种“关系”是基于距离的，有了这种“关系”，就可以进一步利用词汇之间的距离进行检索。所以，在算法层面上，检索更是基于了“距离”而非“匹配”，基于“语义”而非“形式”。②

对比Synonyms较之于以上两者具有更大的词汇量，更便于针对中文词语进行语意辨析。下面选择一些在同义词词林、知网和Synonyms都存在的几个词，给出其近似度的对比：

k-means算法里，需要首先随机地选择k个对象代表簇的初始均值或中心;由此看出弊端，直接选取文档中k个词为主簇，并不能准确地概括出文本的中心主题，加大了聚簇工作量。由于k-means算法在初始化簇的种子对象时的随机性，被选到的K个对象中可能包括词义远离文本主题的词。不同的初始中心的选择对聚类结果有较大的影响。改进k-means，以关键词中的k个对象经过Synonyms相近词聚类处理后作为预判簇的初始中心，解决了上述缺陷，保证了文本中心主题的准确。

同时运用k-means算法和Synonyms工具包就可以得到文本的几个簇，解决了文本主题的单一性。语料库中每篇文档可以统计出多个主题，根据主题不同，多篇文档有多种聚类组合方式。

4 总结与展望

s-k（Synonyms-k-means）主题聚类算法解决了文本主题单一的问题，改善了k-means存在的随机性大的问题，改善了仅用关键词聚类的不精确，利用关键词间的语义联系提高了聚类的准确度。但算法用到的tf-idf算法更适用于长文本，所以在关键词提取方面还有提升空间。

注释：

① 来源于百度百科.

② 来源于自然语言处理之近义词包 Synonyms——胡小夕.

参考文献：

[1] 吴启明，易云飞. 文本聚类综述[J].. 河池学院学报，2008（2）.

[2] 唐晓波，房小可. 基于文本聚类与 LDA 相融合的微博主题检索模型研究[J].. 情报理论与实践，2013（8）.

[3] 田久乐，赵蔚. 基于同义词词林的词语相似度计算方法[J].. 吉林大学学报（信息科学版），2010（6）.

[4] 李国佳. 基于知网的中文词语相似度计算[J]. 智能计算机与应用，2015（3）.

[5] 张丹. 基于主题模型的话题聚类算法的研究. 北京邮电大學硕士论文，2017.

[6] 吴敏.网络短文本主题聚类研究. 华中科技大学，2015.

[7] 张宜浩，金澎，孙锐. 基于改进 k-means 算法的中文词义归纳[J]. 计算机应用.2012，32（5）.

[8] 张亚男. 基于混合聚类算法的微博热点话题发现的研究[J]. 杭州电子科技大学学报， 2018（1）.

[9] https：//github.com/huyingxi/Synonyms/.