殷 硕，王卫亚，柳有权

(长安大学 信息工程学院，陕西 西安 710064)

0 引 言

文本聚类是将大规模文本按照某种表示模型划分为多个簇，使得同一个簇中的文本之间相似度尽可能大，不同簇中的文本之间相似度尽可能小[1]。文本聚类中最重要的两个步骤是：特征选取和利用特征进行相似度判断[2]。常见的文本聚类有基于向量空间模型的文本聚类和基于潜在语义索引的文本聚类[3]等。其中以向量空间模型[4](vector space model，VSM)作为文本表示模型，并使用TF-IDF(term frequency-inverse document frequency)作为模型中元素的权重的文本聚类方法应用最为广泛，比如文献[5]提出了一种基于K-Means和VSM的聚类算法，利用VSM模型计算文本相似度，从而实现文本聚类算法。但是使用VSM作为文本表示模型会产生两个问题：一是表示文本的向量维度过高，导致算法复杂度过高；二是VSM模型缺乏词语的语义信息。VSM向量维度过高的问题通常采用降维策略，对文本进行特征抽取[6-8]或者挖掘频繁项集作为特征信息[9-10]的方法降低数据的维度。

文中将《知网》[11]作为语义词典引入到文本聚类中，提出一种既能降低向量维度，又能弥补VSM所缺少的语义信息的聚类方法。该方法首先改进词语语义相似度算法，其次在词语语义相似度的基础上对文本进行语义特征抽取，降低文本表示模型的维度，以及完成对簇的语义特征抽取，最后通过计算抽取的特征集合之间的相似度，完成文本聚类。

1 词语语义相似度算法改进

1.1 义原相似度算法

《知网》将义原分为了几个大类，类与类之间不存在交集。通过义原之间的上下位关系，为每一个类构建出一棵义原层次树，不同义原层次树之间不存在可达路径。在知网中义原层次树部分示意图见图1。

图1 义原层次树示意图

朱新华[12]提出了综合义原层次树的深度以及密度因素计算义原相似度的公式，在一定程度上提高了词语语义相似度的准确性，具体公式为：

(1)

其中，p1和p2为两个义原，α为可调节参数，N为可达路径长度，level(i)为可达路径上的边在义原层次树中的层次，LCN为两个义原在层次树中的最小公共父节点，f(·)为当前节点的密度信息，其值为所有的兄弟节点的个数(含自身)除以义原层次树的总节点个数，weight(·)函数为每一条边的权重，定义为：

(2)

其中，depth为义原层次树的高度，θ为调节参数，与树高depth成反比，经过实验验证取θ=4，i为当前所在的层次。

1.2 义项相似度计算

义项是使用知识表示语言进行描述的，通过对《知网》知识描述语言进行分析，刘群[13]按照描述形式的不同将描述义项的义原分为4个集合：

通过计算相同类型集合的相似度，再对其进行加权求和得到两个义项之间的相似度。具体公式为：

(3)

其中，S1和S2为两个义项，simj(S1,S2)为第j类集合的相似度，βi为对集合相似度的加权，且满足β1+β2+β3+β4=1，β1>β2>β3>β4。

1.3 词语相似度计算

假设现有两个词语W1和W2，词语W1有n个义项，即s11,s12,…,s1n；词语W2有m个义项，即s21,s22,…,s2m，在计算词语之间的相似度时，首先需要进行消歧，具体消歧算法后面进行讨论。在经过消歧之后，得到两个词语唯一的义项S1和S2，W1和W2之间的相似度就是S1和S2之间的相似度。

2 基于语义特征抽取的文本聚类算法研究

2.1 词语语义相似度改进

虽然文献[12]在计算词语相似度时使用了义原层次树的密度信息，但是却没有考虑到可达路径上所有节点的密度对相似度的影响。所有子节点是对父节点所表达的概念的进一步细分，比如“植物”的子节点有“水果”、“花草”、“树”等，所以密度越大代表细分的程度越大。可达路径上的所有节点都比正在计算相似度的节点在树中的层次高，即在可达路径上的所有节点都是这两个节点中某一个的父节点，父节点的密度越大，在一定程度上也影响着子节点的分类细致程度。所以，文中将结合可达路径上的所以节点的密度，并对其进行加权再求和，得义原相似度计算时的密度部分：

(4)

(5)

通过上述处理，得到新的义原相似度计算函数：

(6)

其中，c1和c2是平衡深度和密度对相似度影响的权重因子，经过实验，文中取c1=0.7，c2=0.3。

2.2 文本预处理

2.2.1 文本内容分词

对于一篇文本，并不是所有的词语都是有实际意义的。中文包含许多停用词、虚词等，所以需要对文本进行分词、去停用词、去虚词等操作。文中使用NLPIR-ICTCLAS[14]分词系统进行分词，首先对NLPIR-ICTCLAS提供的二次开发接口进行编程对文本进行分词，再利用停用词表、虚词表对分词结果进行过滤，得到分词过后的词集。

2.2.2 基于语义相似度的词语消歧算法

中文包含多义词，多义词在《知网》中具有多个义项，所以需要对多义词进行消歧，确定词语唯一的义项。笔者认为，多义词在一个句子中的义项应该是唯一的，在多义词的所有义项中，需要确定的义项与其他已经确定了义项的词语之间的相似度是最大的。具体的消歧算法如下：

(1)获得多义词W的所有义项(s1,s2,…,sm)，以及句子中已经确定了义项的词语集合(W1,W2,…,Wn)；

(2)令W的所有义项的初始权重都为0；

(3)依次计算Wi的义项和(s1,s2,…,sm)之间的相似度，如果Wi和sj之间的相似度最大，则对sj的权重加1，其中1≤i≤n，1≤j≤m；

(4)比较(s1,s2,…,sm)的权重，选择权重最大的义项为W的唯一义项。

通过上述算法，确定多义词在一个句子中的唯一义项。但是在一篇正文中，多义词可能会出现在多个句子中，而且所有句子中的义项不一定相同。针对这种情况，文中采取如下做法：

(1)计算每个义项在正文中所出现的次数；

(2)选取出现次数最多的义项作为多义词在正文中的唯一义项。

2.3 文本语义特征抽取

如果直接使用2.2中得到的文本词集作为文本表示模型会出现两个问题：一是由于模型维度过高而导致算法复杂度过高，二是词集中含有大量与文本主题无关的词语，会降低聚类的精准度。所以需要对预处理后的文本词集进行语义特征抽取，在获得文本主题相关的特征项的同时，也可以降低模型维度。

2.3.1 语义特征压缩

文本的主题是通过一系列主题词进行描述的，而主题词之间则具有较大相似度，通过词语之间的语义相似度，可以获取到文本的主题词集合d，具体算法为：

(3)在S中，将相似度Sij≥μ的词Wi和Wj所在的集合合并，其中μ表示语义相似度阈值，相似度大于μ的两个词语归为同一集合；

(4)最后选取元素最多的一个集合作为文本主题词集合d。

2.3.2 文本特征抽取

在获取到文本的主题词集合d之后，需要根据主题词的权重抽取出文本的特征集。由于进行了语义压缩，笔者认为语义因素比词语的频数因素更加重要，所以对TF-IDF进行调整之后提出如下公式计算主题词的权重：

(7)

其中，Ni为包含词Wi的文本个数，N为文本总数。

在计算出所有主题词的权重之后，选取权重降序排序的前15个词作为文本的特征词集，主题词的权重仅仅作为特征选择的依据，并不参与文本相似度计算。通过特征词集建立文本表示模型Di={Wi1,Wi2,…,Win}，其中Di为文本集中的第i个文本，Wik为Di的第k个特征项。由于特征词都是经过语义压缩以及主题词权重排序抽取得到的，所以文中所有特征词具有相同的语义权重。

2.4 文本语义相似度计算

假设有两个文本表示模型Di={Wi1,Wi2,…,Win}和Dj={Wj1,Wj1,…,Wjm}，且m≥n，语义相似度算法为：

(1)采用完备二部图的构造方法，将两个模型的特征集的元素作为二部图中的两个顶点集合，建立连接，Di和Dj所构成的二部图如图2所示。

(a)计算Di部每个顶点和Dj部每个顶点的相似度，把它作为两个顶点的边的权值，所有边的权值集合记为S；

(b)从S中选取权值最大的边{Wip,Wjq}加入集合L，并从顶点集合中删除顶点Wip和Wjq以及从S中删除所有与之相关的边；

(c)重复(b)，直到Dj部中的顶点为空。

图2 两个文本模型构成的二部图

(2)由集合L中的边的权值得出文本表示模型的相似度计算方法：

0.1*(m-n))

(8)

其中，0.1*(m-n)是当m>n的情况出现时，Wi中元素与空对应，赋予一较小常数。

2.5 簇的语义特征抽取

(1)将C中所有文本的特征抽取出来，组成向量D'={(W1,F1),(W2,F2),…,(Wn,Fn)}，其中Fi为所有文本中Wi出现的频数；

(2)类似于文本特征抽取算法，计算D'中所有词语的两两相似度，找到相似度大于阈值μ的最大集合d'；

(3)选取d'中频数降序排序的前30个词作为簇的特征集。

与2.2类似，这里的频数仅仅作为簇的特征抽取的依据，并不参与簇的相似度计算，簇中的特征项具有相同的语义权重。获取到簇的特征集之后，将簇的表示模型定义为C={W1,W2,…,Wn}，与文本表示模型形式相同，所以簇之间的相似度计算类似于文本相似度计算，以下不再描述。

2.6 文本聚类算法设计

假设现有文本数量为N，需要将这N篇文本进行聚类，使之被分在不同的集合中，不同的集合代表不同的簇。首先利用文中提出的文本语义特征抽取算法抽取每个文本的特征集，初始情况下，将这N个文本视为N个集合，即N个簇，每个簇的特征集为对应文本的特征集。计算所有簇两两之间的相似度sim(Ci,Cj)，如果相似度大于阈值，则将两个簇进行合并，并重新抽取新簇的特征。如果两次迭代之后簇的个数不变，则终止该算法。具体描述为：

(1)抽取每个文本的特征集；

(2)将N个文本初始化为N个簇，每个簇的特征集为对应的文本的特征集；

(3)计算簇之间的两两相似度，如果两个簇的相似度大于阈值α，则将两个簇合并；

(4)根据簇的语义特征抽取算法更新所有簇的特征集；

(5)重复步骤(3)和步骤(4)，直到两次迭代之后簇的个数不变。

3 实验与分析

3.1 实验数据获取

使用爬虫程序在新浪新闻网站中爬取财经、旅游、教育、文化、军事5个类别各400篇网页，共2 000篇作为实验数据。

3.2 聚类实验

为了检验所提出的聚类算法的优劣性，使用准确率(Precision,P)、召回率(Recall,R)和F1度量值作为评价指标，具体公式如下：

(9)

(10)

(11)

其中，a、b、c所表示的含义如表1所示。

表1 评价指标参数

实验之前，首先需要确定文本特征抽取和簇特征抽取过程中所使用的阈值μ，以及聚类算法中不同簇之间的相似度阈值α。文中参考刘怀亮[15]所使用的词语相似度阈值，令μ=0.8。然后需要确定阈值α的最佳值，图3显示了不同阈值α下对聚类结果的影响。

图3 不同阈值对聚类的影响

当0.6≤α≤0.7时，F1度量值随着α的增大而增大，表明聚类效果越来越好。主要原因是当阈值α变大时，不同簇之间的区分度也越来越大，所以聚类效果也在逐步提升。当0.7≤α≤0.85时，F1度量值随着α的减小而减小，表明聚类效果反而降低了。主要原因是当阈值α变得过大时，原本应当合并为一个新簇的两个簇的相似度却达不到阈值α，所以聚类效果逐步降低。

在设定簇相似度阈值α=0.7之后，添加文献[5]基于K-Means和VSM的聚类算法作为对比，表2为两种算法中每个类别文本的所有特征维度比较。

表2 特征集维度比较

由表2可以得出，文中提出的文本表示模型相较于传统的VSM文本表示模型在维度方面有着极大的优势，主要因为文中使用语义对特征词进行了抽取，每一个文本的特征词数量都不会超过15，而VSM则将所有词语所组成的向量作为文本表示模型，使向量维度极大。

表3为两种算法的准确率、召回率和F1度量值的对比。

表3 实验结果对比

由表3可以得出，文中提出的算法相较于文献[5]的算法在准确率、召回率和F1度量值上都有所提高，其原因主要有两点：一是加入了语义信息，弥补了VSM文本模型中语义缺失的问题，使词语相似度更符合人类主观判断的结果，二是通过语义对文本特征进行了抽取，使特征项都是主题相关的，减少了主题无关词语对文本相似度的影响，从而得到了更加准确的文本相似度。

4 结束语

文中提出一种基于语义特征抽取的文本聚类算法，使用词语的语义信息和词语权重对文本的特征项进行了抽取，不仅可以降低文本表示模型的维度，同时所抽取的特征都是主题相关的，彼此之间有着很大的关联。通过计算文本表示模型之间的相似度使同一类的文本聚集到同一个簇中，并更新簇的特征，使簇的特征值可以更好地体现簇中文本主题。通过实验分析，提出的聚类算法不仅能大幅降低文本表示模型的维度，而且聚类效果提升也比较明显。