一种基于主题的Web文本聚类算法

袁晓峰

(盐城师范学院信息科学与技术学院,江苏盐城 224002)

0 引 言

随着计算机网络的高速发展,人们越来越依赖于网络,而网络上信息剧烈的膨胀又会让人们觉得在网络上寻找自己想要的信息越发变得困难了.为了帮助人们更快地找到想要的信息,文本聚类技术得到广泛的研究[1-3].虽然目前有许多文本聚类方法,但是还很少有主题聚类的方法,而主题聚类的结果更能让用户一目了然.主题聚类的思想是根据文本的主题来划分类别,将具有相同主题的文本归为一类.我们认为,Web文本的标题有助于主题的归纳,甚至有些文本的标题就是主题,例如我们搜索的关键字序列为“世界重新认识中国”,搜索引擎返回的结果中包含标题为“汶川地震让世界重新认识中国”的文本,这个标题就直接能反应文本的主题;而有些就不能反应文本的主题,对此,还必须进一步从正文中抽取出文本的主题.基于此,本文提出一种基于主题的Web文本聚类算法(HTBC),同时,在实验中我们还将 HTBC与经典的文本聚类算法(KMeans、AHC、STC)做了比较,实验结果表明,HTBC在聚类的准确率、召回率方面比传统的算法要好.

1 文本聚类算法概述

目前,文本聚类算法大致上可以分为层次聚类(Hierarchical Clustering)和非层次聚类 (Partitional Clustering)[1,2].层次聚类算法的代表是会聚层次聚类方法(AHC),它首先假设所有文本自成一类,然后将最相似的两类合并,并继续这一过程,直到将所有文本合并为一类,因而可以形成一棵聚类树.AHC的优点是能够清晰地显示整个聚类过程以及中间聚类方法.非层次聚类方法的代表是K-均值聚类方法(K-Means).K-Means是一种典型的基于划分的方法,其基本原理是首先选择k个文本作为初始的聚类点,然后根据簇中对象的平均值,将每个文本重新赋予最类似的簇,并更新簇的平均值,然后重复这一过程,直到簇的划分不再发生变化.

上述两种方法最主要的缺点是需要事先确定一个停止条件.比如,AHC要求事先确定所要聚成的类别数,而K-均值聚类则需要设定K值.而上述条件往往在实际应用中很难事先确定.此外,它们都不能很好地描述和解释聚类的结果.再者,这些方法限定每个文本只能属于一个类,而没有考虑一个文本可能属于多个主题的情况.

后缀树聚类算法[3](STC)较好地克服了上述缺点.STC利用一种名为后缀树的数据结构来发现文本所共同含有的短语信息并进而利用这些信息来构建基本类.为了避免出现大量重复的或非常相似的类别,STC合并那些高度重叠的基本类.但STC不是一种基于主题的聚类方法,因为它无法保证一个类别中包含共同短语信息的文本都是关于同一主题的.

2 HTBC算法

HTBC算法首先根据文本的标题和正文提取文本的主题词向量,然后通过训练文本集成生词聚类,并将每个主题词向量归类到其应属的词类,再将同属于一个词类的主题词向量对应的文本归并到用对应词类的名字代表的类,从而达到聚类的目的.HTBC算法的步骤包括预处理、建立主题向量、生成词聚类和主题聚类等环节.

2.1 预处理

由于文本中有些词语对文本主题的概括帮助甚微,甚至没有帮助且会干扰主题的提取,所以必须要对文本集进行预处理.有一些词在文本中出现频率极高,可将其称为停用词,如“的”“我”“你”“地”等,停用词对主题概括没有任何帮助.此外,还有一些出现频率极低的词同样对主题概括没有帮助,所以在预处理时应考虑将其剔除.

另外,在预处理时应将正文部分做中文分词的同时进行词性标注,去除停用词、副词、形容词、功能词和虚词等对主题基本没帮助或者帮助甚微的词,仅保留动词、名词.同样,对文本的标题,也应按上述方法进行处理.

2.2 计算各特征项的权重

文本聚类之前需要将文本表示为计算机能够处理的形式.目前,向量空间模型(VSM)是使用较多且效果较好的表示方法之一[4],其计算特征权值w的一种方法是TFIDF[5],词条ti在文本d中的TFIDF值由下式定义:

其中,TFi是词条ti在文本d中出现的频数,N表示全部训练文本的总数,DFi表示包含词条ti的文本频数.

通常,标题中出现的词肯定是比正文中出现的词对主题的概括更为重要.据统计,标题中出现的词的重要性是正文中出现的相同词的5倍[6].

在计算文本正文中每个词的频率时,考虑是否有与标题中相同的词,如果有则按下式计算,

在此基础上,挑选每篇文本中 TFIDF值高于阈值v的词作为一个主题用向量加以保存,用以聚类.

2.3 聚 类

在进行聚类时,可考虑利用计算词序列之间的相关度来排除干扰词,同时进行合并.

词的相关度通常采用互信息(MI)来计算[7],因为这种方法在处理中文文本时具有较好的性能[8].

如果用A表示包含词条t且属于类别c的文本频数,B为包含t但是不属于c的文本频数,C表示属于c但是不包含t的文本频数,N表示语料中文本总数,t和c的互信息可由下式计算:

通过在训练文本集中计算各主题词向量中特征项的相关度,然后用一个最能反映主题的词作为种子词,并将其作为最终类的代表.

2.4 HTBC算法的具体步骤

HTBC算法的具体步骤如下:

(1)特征项选取.对待聚类文本集中的文本进行预处理,得到词集,W={W1,W2,…,Wm},Wi= {wi1,wi2,…,wim}.其中,i表示所在文本序号.对 W中的词进行词频统计,并选取频度大于阈值f的词构成特征项集,T={T1,T2,…,Tm},Tij={twil1, twi2,…,twij,…,twim}.

(2)生成训练词序列.将训练文本集进行预处理,得到词序列,U={w1,w2,…,wn}.

(3)词聚类.先将U中每个词wi作为一个类.对U中每个词wi(i=1,2,…,n),按(3)式依次计算它与U中每个词wj(j=1,2,…,n)的互信息 MI(wi, wj),若MI(wi,wj)≥r(r为给定的聚类阈值),则将词wj归于wi所属的类,否则继续计算wi与U中下一个词的互信息,直到U中所有词都计算完毕,得到词类序列.其中,每个词类由一个词表示,每个词类记为 uwi(uwi1,uwi2,…,uwik),uwi为U中的第i个词表示的词类.

(4)文本聚类.从 T取出未处理的特征项Ti,在词类中查找,如果任意 Tij都属于同一个词类wi,则标注 Ti属于wi.否则将少数不属于wi的干扰词剔除,并标注Ti属于wi.重复该过程,直到所有的Ti都处理过.最后将同属一个词类的特征项对应的文本划分到以词类名表示的簇.

3 实 验

在实验中,我们用“世界重新认识中国”作为搜索语句,随机下载的100篇相关文本作为测试语料,文本平均长度约为325字,利用HTBC算法中步骤(1)、(2)得到特征项集T.再将特征项集中每个词在新华网站的新华搜索中进行搜索,并随机选取500篇网页文本下载作为训练语料库,有312个词频大于6的词.根据初步实验及分析取聚类阈值 r=0. 005,共产生27个词类,每个词类至少包含2个元素.

在实验中,我们使用准确率(precision)和召回率(recall)对算法进行评价.准确率、召回率的定义如下:

其中,n(i,r)是聚类 r中包含类别i中的文本的个数,nr是聚类形成的类别个数,ni是预定义类别的个数.

我们将待聚类文本集分别用 K-means、AHC、STC、HTBC算法进行聚类,并计算聚类的准确率、召回率,得到如图1、图2所示结果.

图1 4种算法准确率比较

图2 4种算法召回率比较

从图1、图2的比较结果可看出,HTBC算法的精确度较其余3种经典聚类算法要高许多,但召回率却低于K-Means和AHC算法.这主要是因为语言的复杂性,即同义词可能拥有相去甚远的表达方式.但是,79.7%的召回率对互联网上文本聚类方法来说应该是可以接受的.

4 结 语

在本文中,我们提出一种基于主题的Web文本聚类算法:即通过提取Web文本中的高频词,并结合文章的标题,计算这些词在文本中出现的频率,取频率最高的几个组成主题向量,然后通过在训练文本集中计算每个主题向量中词与词之间的相关度,剔除相关度低的干扰词,再计算不同主题向量中各个词之间的相关度,并将相关度高的聚为一类.实验表明,本文提出的文本聚类算法具有较高的精确度和召回率,特别是精确度,较其他几种经典的聚类算法要高.

[1]刘泉凤,陆 蓓,王小华.文本挖掘中聚类算法的比较研究[J].计算机时代,2005,6(1):7-8.

[2]Yanjun Li.Text Document Clustering Based on Frequent Word Meaning Sequences[J].Data and Knowledge Engineering,2008, 64(1):381-404.

[3]ZAMIR O E.Clustering Web Documents:A Phrase-Based Method for Grouping Search Engine Results[D].Washington DC:Unioversity of Washinton,1999.

[4]陈 涛,谢阳群.文本分类中的特征降维方法综述[J].情报学报,2005,24(6):690-695.

[5]Xu D X.Energy,Entropy and Information Poterntial for Neural Coputation[D].Florida:Universtiy of Florida,1999.

[6]韩客松,王永成,沈 洲,等.三个层面的中文文本主题自动提取研究[J].中文信息学报,2005,15(4):45-49.

[7]Yang Z R,Zwolinski Z.Mutual Information Theory for Adaptive Mixture Models[J].IEEE Transactions on Pattern Analaysis and Machine Intelligence,2001,23(4):26-32.

[8]代六玲,黄河燕,陈肇雄.中文文本分类中特征抽取方法的比较研究[J].中文信息学报,2004,18(1):26-32.