基于隐喻词扩展的短文本聚类算法

王 烨, 左万利, 王 英

(吉林大学 计算机科学与技术学院, 符号计算与知识工程教育部重点实验室, 长春 130012)

互联网的飞速发展使得网络上信息量剧增, 人们浏览网页留下的信息不断增加, 各种即时短消息大量涌现, 如人们在搜索引擎中输入的搜索内容, 在即时聊天系统中写入的大部分句子及各种新闻标题等. 人们希望能从这些短文本中获取有用的资源, 并对海量的文本进行管理.

在实际应用中, 若判断一则短消息的具体类别, 需要发现其与归属类的某些内在联系以判断其类别属性. 根据这些内在联系去完成各种任务, 例如: 通过聚类用户在搜索引擎中输入的搜索内容, 向用户提供最相关的信息； 通过将新闻标题进行聚类, 向用户推荐类似新闻; 减少冗余信息的沉积等. 文本聚类就是把语料集分成几个类簇, 使其中相似的文本组织成一个类簇, 并使类簇内短文本的相似度尽可能较大, 而类簇间短文本的相似度尽可能较小. 文本聚类作为一种无监督的机器学习方法, 不需要训练过程, 具备良好的自动化处理能力和一定的灵活性, 在文本挖掘等领域应用广泛. 文本聚类算法主要分为划分法、 层次法、 基于密度的方法、 基于网格的方法和基于模型的方法[1-4]. 但短文本的信息缺失使普通的文本聚类方法很难应用于此, 短文本的词汇量少, 表达形式多样, 易导致原应属于同一类的两则短文本之间几乎没有相同词汇, 进而导致短文本聚类结果不准确.

目前, 对短文本聚类分析的研究主要分为两方面: 1) 尝试改进各种传统的聚类方法; 2) 致力于处理短文本本身, 对较稀疏的特征进行扩展. 文献[5-6]针对短文本特征稀疏的问题, 对短文本进行文本扩充, 从而增加了短文本信息量. Hu等[7]提出了一种基于三层结构式的处理短文本特征词稀疏的方法, 将特征分为内部特征和外部特征, 将其融合形成特征短文本； Ni等[8]提出了一种基于查找核心词的短文本聚类方法； 杨俊丽[9]提出了一种基于外在知识的短文本聚类方法； 袁满等[10]提出了一种基于频繁词集的特征扩展方法； 韩冬雷等[11]提出了一种基于维基百科的短文本语义扩张方法. 与英文短文本聚类研究相比, 对中文短文本聚类的研究相对较少. 本文对短文本扩张进行进一步研究, 利用维基百科将短文本中的隐喻词进行扩展, 以在一定程度上弥补短文本信息量较少的缺陷, 提升短文本聚类效果.

1 短文本聚类算法

1.1 维基百科

本文使用维基百科对短文本进行扩展. 维基百科是由多种语言分类构成的知识库, 内容丰富, 其主题页面之间的链接关系可解释词语之间的相关关系, 为计算词语相关度提供了研究基础.

图1 维基百科的链入链出关系Fig.1 Relationship of Wikipedia chain

图1为维基百科的链入链出关系, 其中γ列为同义词关系, 即重定向到同一页面的词语,α列为γ列的入链接集合,β列为γ列的出链接集合, 本文基于维基百科的链接关系对词语相关性进行计算. 使用维基百科数据库的page,pagelinks,redirect,category,categorylinks,revision和text表, 其中: page表用于保存主题页面的相关信息, 是维基百科系统的核心表； pagelinks表用于保存主题页与主题页之间的链接关系, 表示的链接关系为链入关系与链出关系； redirect表用于保存页面中的重定向信息, 重定向信息是指一个词语是否有其他主题与其一致, 例如“五星红旗”重定向为“中华人民共和国国旗”, 即主题页面“五星红旗”的内容与主题页面“中华人民共和国国旗”的内容一致； category表用于保存已存在的分类； categorylinks表用于保存主题页面所属的类别链接； revision表用于保存修改后页面的信息, 每次修改形成一个新的版本； text表用于保存主题页面的正文内容.

维基百科数据库的各表间关系如下：

1) page.page_latest→revision.rev_id;

2) revision.rev_page→page.page_id;

3) revision.rev_text_id→text.old_id;

4) 通过page.page_id可得到redirect.rd_title, 从而可得到重定向到此页面的所有rd_from.

由上述表可得到表间丰富的链接关系及主题页面所属类别, 通过这些关系可得到主题与主题之间的相互关系, 从而得到词语的同义词、 近义词等有关联的词语, 为后续的短文本扩展提供基础.

1.2 短文本关键词选择

在对短文本进行分词以去停用词后, 需要对文本中的字词进行度量, 判断其在文本中的重要程度, 即选择关键词.

TF-IDF作为一种用于文本挖掘的常用加权技术, 其作用是可用于评估一个字词对于一个语料集中一个文本的重要程度. 如果一个字词在文本中的出现次数越多, 则其重要程度就会成正比增加； 反之, 如果其在数据集中的出现次数越多, 则其重要程度就会成反比下降. TF-IDF的主要思想是： 在语料集中选出若干关键词, 通过关键词对文本进行区分. 作为关键词的条件是其在一个文本中出现的频率较高, 同时在语料集中其他文本中出现的频率较低, 则该词语即具有较好的类别区分能力, 适用于分类.

TF是对词数的归一化表示, 用于防止其偏向较长的文本. 因为长文本中重复的词汇可能会较多, 若只计算词语总数, 则可能导致偏差. 逆向文件频率(IDF)是度量一个词语在数据集中普遍重要性的指标. 计算某个词语wi逆向文件频率, 可由总文件数|D|除以包含该词语wi文件的数目|{j:wi∈dj}|, 再将得到的商取对数, 即得到理想文件频率IDF：

TF-IDF实际上是TF(wi,dj)×IDF(wi), 则

如果某个词语在一个文本内拥有较高词频, 同时在整个语料集中拥有较低频率, 则经过计算后即可得较高的权重, 可作为候选关键词. 因此, TF-IDF可过滤掉一些在数据集中经常出现的词语, 同时保留重要的词语, 能区分出产生良好效果的词语.

1.3 算法设计

1.3.1 相关度计算 在维基百科中的大量链入链出关系可侧面反映两个主题的相关度, Milne[12]提出了一种基于两个页面的入链接关系计算这两个词语的相关度方法, 以及一种基于概念间相互链接关系计算两个词语相关度的方法, 这两种方法都是目前普遍采用的计算词语相关度的方法.

本文采用基于入链接关系的方法[13]计算词语相关度：

作为重定向的某一页面, 其链入页面很可能并不包含其同义词的链入页面, 故|a→b|中的页面a与页面b也需要包含其同义词的页面.

1.3.2 短文本扩充 短文本的词汇量较少, 同时文本中重复词语出现次数较少, 文本中的信息量较少, 在应用传统文本聚类方法的情况下并不能得到较好的聚类结果. 考虑到文本中存在大量的隐喻现象, 因而需将文本中的隐喻词进行扩展. 首先基于维基百科得到其真正表示的含义, 然后对其真正含义的同义词进行扩展, 目的是增加文本的信息量, 从而提高文本聚类效果.

一般短文本中的隐喻词会在维基百科中形成“歧义页”主题页面, 该主题页面中列出了该词语包含的几种含义. 例如, 网络中的“恐龙”一词, 原意指出现于中生代的曾支配全球陆地生态系统超过1亿6千万年之久的多样化优势陆栖脊椎动物, 但在现代中文网络中, “恐龙”一词多指对丑女的称呼, 在维基百科中对应的页面为“恐龙(俗语)”, 由于此类解释多为维基百科中消歧义页面的内容, 所以在这里需要用到对隐喻词进行扩展的页面为维基百科中的消歧义页面.

首先, 将文本dj表示为一个词汇列表, 对于词汇列表中的每个词语wi进行遍历, 查询其是否在维基百科中存在歧义页面. 如果存在歧义页面, 则将除隐喻词wp外的其他词语表示为一个词汇列表lj, 对于词语列表lj中的每个词语wlj,i, 使用上述计算词语相关度的方法计算相关度, 并选取歧义页面中与其相关度最大的一项作为该隐喻词wp的真正解释ep.

其次, 对该解释ep进行扩展. 查询其链入页面的主题页面集合, 对集合中的每个页面与该页面进行相关度计算, 由于短文本数据集选择的是新闻标题, 文本长度较小, 故选择相关度最大的3个页面作为扩展选项对短文本进行扩展. 例如, 新闻标题“苹果Apple Watch今年难在瑞士开售： 商标被抢注”, 经过分词以及去停用词后变为词汇列表[“苹果”,“Apple”,“Watch”,“今年”,“瑞士”,“开售”,“商标”,“抢注”], 经过遍历后发现“苹果”一词为隐喻词, 使用上述算法进行计算后, 得到其真正解释为“苹果公司”, 通过对“苹果公司”进行扩展后, 得到与其相关度最大的3项, 分别为“苹果电脑”、 “苹果计算机”和“Apple_Computer”, 将这3项作为扩展词语扩充入短文本中, 即具有增加短文本信息量的作用. 但像“小米”一词在中文维基百科中并没有歧义页面, 而该词语却是真实存在的拥有隐藏含义的词语. 经过探索发现, 在中文维基百科数据库中text表的old_text中存在“other”选项“小米科技”, 即隐喻词的发现仅通过歧义页面还不够, 还需对上述这类词语进行old_text的查询, 发现其其他用法.

1.3.3 短文本聚类 由于本文使用的语料集规模较小, 而k-means算法简单易行, 较适用于这种规模的数据集[14-15]. 但k-means算法易导致无法收敛到全局最小值, 因此本文采用二分k-means算法对短文本进行聚类.

k-means算法是通过用户给定类簇个数k, 通常随机选择k个初始点作为聚类中心, 将语料集中的每个数据点分配到离其最近质心所属的类簇中, 然后更新每个类簇的质心为该类簇所有点的平均值[16-17]. 二分k-means算法克服了k-means算法易收敛到全局最小值的问题, 该算法首先将所有数据点作为一个簇, 然后取这些数据点的平均值作为簇中心, 将其一分为二, 最后根据分开后的两个簇哪个可以降低总误差就对哪个簇进行划分, 直到达到规定类簇的个数.

算法1基于隐喻词扩展的短文本聚类算法.

forwiindj:

ifwi在维基百科中存在歧义页面：

查询wi的歧义词

else:

查询wi的old_text页面, 发现其其他用法

lj={wlj,i|wi∉wlj}

forwlj,iinlj:

计算词语相关度

选取相关度最大的wlj,i作为真正解释ep

for 链入 inep:

计算其与ep的相关度

选取相关度最大的3个页面作为扩展项对短文本进行扩充

将所有数据点视为一个簇

当类簇个数小于规定个数k时

对于每个类簇

计算SSE值

进行k=2的k-means聚类

计算聚类后的总误差

选择使总误差最小的类簇进行一分为二的划分.

2 实验结果与性能分析

本文采用F-measure方法[18]进行聚类结果评价.F-measure方法通过查准率与查全率得到综合评价的F值, 其中查准率是正确分配到一个类簇中短文本的概率, 反映每类中的内容是否集中； 查全率是同一类别的文本被分配到一个类簇中的概率, 反映同一类中的相似文本是否集中.

本文对教育、 音乐、 体育和科技4类共1 600条新浪新闻标题进行聚类分析. 通过对本文提出的基于隐喻词扩展的短文本聚类算法进行10次交叉实验后的聚类结果如图2所示. 与二分k-means聚类算法相比,k-means聚类算法对于聚类中心的选择具有较大随机性, 易导致聚类局限性. 对扩展前后的短文本进行10次交叉实验, 采用平均值作为聚类结果如图3所示.

图2 二分k-means聚类结果Fig.2 Clustering results of bisecting k-means

图3 k-means聚类结果Fig.3 Clustering results of k-means

由图2和图3可见, 二分k-means方法得到的结果相对较好, 扩展前后的F值平均提高了18%, 基于隐喻词扩展后的短文本在聚类结果上得到较大提高.

考虑到新闻标题中出现的大量人名或新鲜词汇在中文维基百科中可能查询不到相关内容, 因此若能考虑到这些因素, 并在本文基于隐喻词扩展的基础上再次进行扩展, 所得到的聚类结果可能更有效.

综上可见, 本文采用基于隐喻词扩展的方法对短文本进行聚类的效果得到了较大提升, 能对短文本文档进行有效归类.