一种基于LDA的潜在语义区划分及Web文档聚类算法

刘振鹿,王大玲,2,冯 时,张一飞,2,方东昊

(1.东北大学信息科学与工程学院,辽宁沈阳110819;2.医学影像计算教育部重点实验室(东北大学),辽宁沈阳110819)

1 引言

向量空间模型[1](VSM)将文档视为n个索引项(t1,t2,…,tn)构成的向量,为每个索引项ti赋予权值wi(1≤i≤n),采用向量d=(w1,w2,…,wn)表示文档d。传统的表示方法将ti视为出现在文档中的一些术语,采用术语的绝对词频或相对词频(如TFIDF)为wi赋值,这样的权值忽略了术语之间的相互关系,而且以这样的模型表达的文档通常具有很高的维数,从而使文档聚类过程因“维灾”而导致相似性度量失去意义[2]。基于此,在文本聚类研究中,一些学者探索将索引项ti由可见的术语转换成潜在的语义,因而将wi由术语的权值转换为语义的权值,弥补了以词为特征的缺陷,而且很大程度上降低聚类的维数,节省聚类的时间。目前研究工作中表达文档潜在语义的方法主要包括 LSA[3]、PLSA[4]和 LDA[5-7]。文献[6]、[7]等研究在比较、分析LSA、PLSA、LDA的基础上证明了LDA在采用潜在语义表达文档方面具有更大的优势。

基于上述研究,本文根据LDA模型的特点,深入分析文档的潜在语义空间,获得能够表现文本特征的最佳语义区间,将其应用于Web游离文档的检测和Web文档聚类,采用文档类别与语义互作用机制对聚类结果进行修正,以获得更好的聚类结果。

本文其余部分组织结构如下：第2节基于LDA模型进行文档语义分布的分析,第3节基于语义分布的分析结果进行游离文档的检测,第4节基于语义分析结果进行Web文档聚类以及基于文档类别与语义互作用机制的聚类结果修正,第5节通过实验证明本文算法的优势,最后第6节是结论及进一步的工作。

2 基于LDA的文档语义空间分析

2.1 LDA模型

LDA模型是由Blei等提出的三级层次结构的贝叶斯模型[5]。在应用于文档分析时,表现为文档d、潜在语义z、术语t之间的关系。文档集合D 由M个文档单元构成,D={d1,d2,…,dM},di(i=1,2,…,M)由N个术语序列构成,即di={t1,t2,…,tN},在潜在语义zn条件下生成术语tn(n=1,2,…,N)的概率为 P(tn|zn,β)。基于此,概率模型表示为：

对文档建模,实际上就是估计α和β两个参数。文献[5]采用variational inference方法简化了模型,选择一个变分分布Q函数逼近P,即P(H|D)≈Q(H),Q选择为：

其中γ和φ为Q的参数。文献[5]假设θ和z相互独立 ,并丢掉 t,求最优解满足 Q(θ,z|γ,φ)和P(θ,z|t,α,β)之间的 KL 散度最小 ,计算出 γ和 φ迭代公式：

据此进行EM迭代,E步计算每篇文档的参数γ和φ,M步最大化Variational Inference中的下界,求出此时的α和β,直到α和β收敛。

2.2 语义空间分析

为表示语义空间分析过程,这里采用中国科学院计算所谭松波等收集并建立的中文文本分类语料库 TanCorpV1.0[8]中的3类(电脑网络,汽车快讯,医药)858个文档,初始语义数量IS设置为100,采用 LDA迭代结果α向量中αk(1≤k≤100),按值的升序排列后的结果如图1所示(横坐标SN表示语义编号)。

图1 语义空间α分布图实例

直观地看,如果将α分布曲线拟合成直线,根据直线的斜率,α曲线可近似分为A、B、C共3个区域。A区域中,α较小,表明在文档集中包含此区域中SN对应语义的文档较少;C区域中,α较大,则文档集包含此区域中SN对应语义的文档较多;B区域本身对应的语义最多,而文档集中包含该区域中SN对应语义的文档较A区域大较C区域小。基于此,将A、B、C区分别定义为低频语义区、中频语义区和高频语义区。

对于低频语义区,包含对应语义的文档较少,因此,低频语义区的语义对于表达文档特征的贡献较少。从文档聚类的意义上,中、高频语义区的语义对于表达不同类别文档特征的贡献更大。

为求得3个区域的分割点,本文首先给出两个定义。

定义1(凸点)：绘制 α曲线的辅助曲线α=f(SN),该曲线在两点(α1,SN1)与(α2,SN2)之间表现为一凸弧,则对于连接(α1,SN1)与(α2,S N2)的直线 α=aS N+b,∃(α1*,SN1*)使(α1*,SN1*)∈α曲线且(α1*,SN1*)与α=aS N+b距离最大,则称(α1*,SN1*)为凸点(Convex vertex),如图 2(a)。

图2 凸点与凹点

定义2(凹点)：绘制 α曲线的辅助曲线α=f(SN),该曲线在两点(α3,SN3)与(α4,SN4)之间表现为一凹弧,则对于连接(α3,SN3)与(α4,SN4)的直线 α=aSN+b,∃(α2*,SN2*)使(α2*,SN2*)∈ α曲线且(α2*,SN2*)与 α=aSN+b距离最大,则称(α2*,SN2*)为凹点(Concave vertex),如图 2(b)。

根据定义可见,这里的辅助曲线α=f(SN)仅仅是为了获得(α1,SN1)与(α2,SN2)以及(α3,SN3)与(α4,SN4),即凸弧和凹弧的两个端点,当各自端点确定后,凸点和凹点求解过程与α=f(SN)无关,而且凸点和凹点一般也不一定等于凸弧和凹弧的驻点。

分析α分布图,低频语义和中频语义区的分界近似为凸点,而中频语义和高频语义的分界则近似为凹点,因此若将α分布图拟合成曲线,在凸点和凹点之间必存在一个“拐点”,使α分布图的起点与该拐点构成定义1中的(α1,SN1)与(α2,SN2),而该拐点与α分布图的终点构成定义2中的(α3,SN3)与(α4,SN4)。

为获得α=f(S N),将α分布图拟合成曲线α=f(SN)=a3SN3+a2SN2+a1SN+a0,求拐点 ,然后分别在α分布图起点—拐点、拐点—终点中求出凸点和凹点。对图1中α分布图所求的拐点、凸点和凹点如图3所示。基于此,求α分布图中低频、中频、高频语义区的算法 Algorithm α-Analysis包括：1)求拟合曲线及拐点;2)求凸点和凹点;3)划分A 、B、C 区 。

划分低、中、高频语义区对于文档集特征提取和聚类具有重要作用。此外,语义数量IS的设置对于α分布曲线分布及其中低、中、高频语义区的变化也是有影响的,即IS不同时,α分布图亦不同。图4为 IS 分别为 10、20、40、60、80、100 时,α分布曲线分布。

3 基于LDA语义区间分析的游离点检测

图3 图1中α分布的凸点与凹点

图4 不同IS值的α分布

由2.2节分析可知,分布在低频语义区的语义被较少的文档包含。对于文档集D,假设其中的文档分属 C1、C2、…、Cn个类,若选择足够的 IS,则其 α分布图能够划分出低频、中频、高频语义区。直觉上,如果一个文档d不属于C1～Cn的任何一类,则其包含的语义应该处于低频语义区。因此,本文应用这一启发式规则进行游离文档的检测。

为此,这里给出游离文档的定义和性质。

定义3(游离文档与非游离文档)：设文档集D中的文档分属于C1、C2、…、Cn个类,若文档 d不属于C1～Cn的任何一类,则将d定义为游离文档,否则将其定义为非游离文档。

基于前面的分析,游离文档与非游离文档具有如下性质：

性质1：基于 LDA模型表示并采用EM算法迭代后,非游离文档的潜在语义在α分布图中能够分布在低、中、高频语义区或中、高频语义区;

性质2：基于 LDA模型表示并采用EM算法迭代后,游离文档的潜在语义在α分布图中仅分布在低频语义区。

为说明上述性质,本文在上面的电脑网络、汽车快讯、医药三方面858个文档的文档集D中加入一个体育类的文档d,根据定义3,d为游离文档。

前述公式(3)给出了α与γ的关系,本文通过对γ矩阵的展示来分析游离文档。过程如下：

(1)对γ矩阵预处理：γ矩阵行为文档代号(docID),列为语义代号(SN),每个语义均对应有α向量中的一个αk,通过对α向量的升序排列来对γ矩阵相应的列进行交换;

(2)应用 2.2节 Algorithm α-Analysis算法检测低、中、高频语义区,然后逐行扫描文档,判断其分布在各语义区的值选出游离文档。

以IS=60为例,游离文档(docID=19)与一些非游离文档(docID=6、18、20)的对比如图5所示。19号文档包含的语义只出现在低频语义区,不包含中、高频语义区的语义,而其他非游离文档,包含了中、高频语义区的语义。

为了进一步验证游离点检测算法的有效性,本文在原有文档集电脑网络、汽车快讯、医药三方面858个文档的基础之上加入了3个不同类别的游离文档：300号文档为体育类,301号文档为城建类,302号文档为电影类,303号为非游离文档(汽车快讯)。这些文档的对比如图6所示。从图中可见303号非游离文档和300,301,302号游离文档明显的差别,从而也证明了本文的游离点检测算法对于多游离点文档集同样适用。

图56号、18～20号文档在γ矩阵中一行的值

图6300～303号文档在γ矩阵中一行的值

因此,通过对语义区的划分以及对文档在不同语义区分布的分析,可以检测游离文档。而游离文档的检测,对于文档聚类具有预处理的作用,特别是对于如K-Means这类基于划分的聚类方法(即要求预先给定聚类数目),可以提高聚类的准确性。

4 基于文档类别与语义的互作用机制的聚类

基于LDA模型表达文本,提取中、高频语义区的语义作为文本特征,根据这些特征进行初始文本聚类。然后通过统计每个语义在各类文档中的比例获得语义的类,通过统计每篇文档在各类的比例修正文档所属的类,以此“文档类别与语义互作用”机制修正聚类结果。

4.1 基于K-Means的文本初始聚类

根据公式(3)对γ矩阵进行分析,部分中、高频语义区γ矩阵的值如表1所示。

表1 中、高频语义区 γ矩阵局部图

可见,γ矩阵中的值相差很多,由于不能满足欧式距离“贡献等同”的要求,直接聚类质量较差。本文在聚类时采用如下方法进行处理：(1)不作任何处理;(2)行归一化处理(对同一行的元素进行极大-极小归一化处理);(3)0、1归一化处理(即如果值大于等于1则赋值为1,否则赋值为0);(4)大于1者归1处理(即如果值大于1则赋值为1,否则保留原值)。在此基础上,以处理后的γ矩阵值为文档特征,应用K-Means算法进行文档聚类。

4.2 基于“类别与语义互作用”机制的聚类结果修正

若4.1节中对γ矩阵的预处理采用方法(3)或者(4),则γ矩阵每一行中1的数目即一篇文档所包含的语义数目,每一列中1的数目即包含该列对应语义的文档数目。基于此,本文通过对错误聚类的文本进一步纠正,从而得到更好的聚类结果。具体地,在初始聚类的基础上,采用“类别与语义互作用”机制做进一步的调整：一方面,通过对γ矩阵各列中1数目的统计,获得各语义在各类文档中所占比例,就某一列而言,所占比例最大的文档类别即为该语义的类别;另一方面,通过对γ矩阵各行中1数目的统计,获得各“类”语义在该文档中所占的比例,最大者为该文档的类别。重复这一过程,直到稳定。其算法MutualAction of Semantic-Cluster如下：

算法中,2～5行是根据初始聚类结果对语义“分类”,此过程结束后,各语义便有了对应的“类”;6～9行是根据语义分类结果对文档聚类结果进行修正,由于这种修正可能会影响语义“分类”结果,所以上述2～9行一般还需重复执行,直到稳定。图7给出了一个γ矩阵的初始聚类和调整过程及结果。

图7 文档类别与语义互作用实例

5 实验

本文分别在2个数据集上实验,数据集同样采用中国科学院计算所谭松波等的中文文本分类语料库-TanCorpV1.0,数据集1选择电脑网络、汽车快讯、医药3个类别共858个文档;数据集2选择电脑病毒、电脑软件、电脑网络3个类别共1200个文档。前者3类文档语义差别较大,后者3类文档语义相似,均为电脑类别。采用Matlab软件工具[9]实现相关算法。

实验采用宏平均MacroP作为聚类质量的度量准则,计算方法如下。

5.1 对γ矩阵不同预处理方法的聚类实验

如前所述,在聚类之前,对γ矩阵的值采用了不同的预处理方法,这里将不作任何处理、行归一化方法、0-1归一化方法、大于1者归1方法进行对比,同时,将传统向量空间模型采用的“以术语为特征”(word as feature)的方法也进行对比。这里采用KMeans算法、每类随机选择初始中心点进行聚类,图8是进行100次上述实验的聚类结果的MacroP平均值。(图8中将上述4种方法分别表示为no smooth、unitary 、0-1 smooth、smooth to one)。

图8 不同预处理方法聚类的MacroP对比实验结果

结果表明,大于1者归1方法具有更好的聚类结果。由于聚类过程中文本的相似性度量采用欧式距离,而欧氏距离要求对象的各个分量贡献同等。如果某个语义对应的值过大,足以掩盖其他语义时,直接应用欧氏距离将导致对象间区分度较差。为体现各语义在文档中的作用,需进行平滑处理,而大于1者归1方法将对语义包含者进行平滑处理,在应用欧氏距离时表现出了更好的质量。基于同样原因,0、1归一化效果也比较好。

另一方面,从图8也可看出IS的选择对聚类结果的影响,前者IS在30附近、后者IS在50附近时聚类结果是最好的。

5.2 基于“类别与语义互作用”机制的聚类结果修正实验

在初始聚类基础上,应用MutualAction of Semantic-Cluster算法修正聚类结果,其结果与图8中smooth to one的初始聚类的结果对比如图9所示。

图9(a)中,当IS为50到110时,MacroP经纠正后有大幅提升(最高11%),图9(b)则无明显变化,说明基于“类别与语义互作用”机制对于类别差异不大的文档集的聚类修正效果不明显。

图9 修正前后的聚类结果对比

6 结语

本文在应用LDA模型表示文档的基础上,对潜在语义的分布进行了深入分析,通过对不同频度语义区的划分以及对文档在不同语义区分布的分析,得到表现文档的主要语义特征,并据此检测游离文档和进行文档聚类。

本文目前的工作尚显粗糙,一些问题尚需深入研究,因此今后进一步的工作包括：(1)低频、中频、高频语义区的精确划分算法;(2)各区语义内容、特别是高频语义区作用的深入剖析;(3)基于LDA的文档表示、聚类及其他相关算法的进一步优化。

[1]Salton G,Wong A,Yang C.A vector space model for automatic indexing[J]//Communications of the ACM,1975,18(11)：613-620.

[2]Hinneburg A,Aggarwal C,Keim D.What Is the Nearest Neighbor in High Dimensional Spaces[C]//Proceedingofthe 26th VLDB Conference,2000：506-515.

[3]Dumais S,Furnas G.,Landauer T,Scott D,et al.U-sing Latent Semantic Analysis to Improve Access to Textual Information[C]//Proceedings of Computer Human Interaction,1988：281-285.

[4]Hofmann T.Probabilistic Latent Semantic Indexing[C]//Proceedings of the 22th Annual International SIGIR Conference on Research and Development in Information Retrieval,1999：50-57.

[5]Blei D,Ng A,Jordan M.Latent Dirichlet allocation[J].Journal of Machine Learning Research,2003,3(5)：993-1022.

[6]Phan X,Nguyen L,Horiguchi S.Learning to classify short and sparse text&web with hidden topics from large-scale data collections[C]//Proceedings of 2008 WWW Conference,2008：91-100.

[7]Titov I,McDonald.Modeling online reviews with multi-grain topic models[C]//Proceedings of 2008 WWW Conference,2008：111-120.

[8]谭松波,王月粉.中文文本分类语料库.TanCorpV1.0。www.Searchforum.org.cn/tansongbo/corpus.htm

[9]薛定宇,陈阳泉.高等应用数学问题的MATLAB求解[M].第一版,北京清华大学学研大厦A座：清华大学出版社,2004.10.