免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2778 | 回复: 0

多层概图文档聚类方法中精化算法的研究 [复制链接]

论坛徽章:
0
发表于 2011-03-19 14:18 |显示全部楼层
转自 http://www.chinakdd.com/portal.php?mod=view&aid=124638

多层概图文档聚类方法中精化算法的研究

1、引言
聚类分析是数据挖掘的重要手段之一,在文本挖掘中也占据重要地位。在各种聚类方法中,图论法是一种较为灵活有效的方法。其前提是把需要聚类的数据表示成无 向图G=(V,E)的形式,V是图的顶点集,E是图的边集。所有数据点构成顶点集,如果两个顶点符合一定的邻域规则,那么它们之间有边。
基于图的聚类操作,一般是应用图分割算法,把图分割为互不连通的分支,再把分支中的顶点集映射到数据集合,得到最后的聚类结果。在图的分割和映射过程中, 要能对边和点的权重进行处理,并研究根据一定的目标函数,求取最优分割的算法。本文研究了高维特征空间下的文本聚类方法,提出了一种基于多层粗图模型的聚 类算法,对反概化操作中的精化算法进行了深入探讨。
2、相关工作
文献[1]提出了一种基于超图(hypergraph)模型、对高维空间数据进行聚类的方法,并应用于Web文档聚类。其中的HEMTIS是一种应用于 VLSI设计的多层超图二分算法。超图的最优二分计算是一个NP问题,但由于该问题在许多应用领域的重要性,学者们已经提出很多启发式算法用于近似解决二 分图的问题。
超图二分模型一般有三种。第一种为单阶段型,其一般的过程是,从一个初始分割(随机获得)开始,通过应用精化算法进行迭代,顶点在炉分割的两部分之间动态 移动,使分割质量不断提高。第二种是两阶段型,包括:①把原始图聚集为一个较小型的图,并应用FM算法进行二分;②把该聚集超图的二分映射回原始超图,获 得原始超图的二分。该类型的分割质量主要取决于第一阶段超图聚集操作。第三种是三阶段型,包括:①概化过程;②初始分割过程;③反概化和精化过程。在概化 过程中,从原始图通过概化操作,产生一系列逐步缩小的概图;在初始分割过程,应用超图分割算法对最小的概图进行分割;在反概化和精化过程,最小概图的二分 反向逐层映射回较细的概图,并在每一层应用KL或FM算法进行精化操作,不断提高超图的分割质量。
无论是何种超图分割模型,均需要应用精化算法在不同阶段进行局部点的移动,以改善分割质量。在这些分割模型中,应用到的精化算法一般有三种,分别为 Kernighan-Lin算法、KL的扩展Schweikert-Kernighan算法和计算速度较快的Fiduccia-Mattheyses算 法。但是,应用这些算法产生的分割质量有时仍难令人满意,尤其是对于顶点较多的大型超图。究其原因主要有:1、对移动点的选择仅仅依赖于局部信息,没有考 虑全局信息;2、当顶点的“增益”相等时,无法给出正确选择移动点的方法;3、当含有多个顶点的超边跨越分割时,这些顶点的“增益”计算无法准确进行。
METIS是一种多层图分割算法,对概化操作进行了改进,但不能直接应用于超图分割;hMETIS则在此基础做了进一步改进,使其能应用于超图分割。文献[]在图的二分基础上进行了扩展,能同时把图划分为二、四或八个分割,称为k-way算法。
本文针对web文档聚类的数据高维、稀疏的特点,提出一种基于多层概图模型的文档聚类算法,首先创建文档的向量空间,运用向量内积定义数据点的相似性;然 后建立图模型反映数据点之间的联系程度,对此原始图进行不断的概化操作,形成一系列逐层缩小的概图序列,对最小的概图运用分割算法划分为k个分支;最后把 此分割再逐层映射回较细图,根据需要运用改进的FM精化算法对分割进行局部调整,不断改善分割质量,最终原始图的分割映射到文档数据集,就是我们需要的聚 类结果。本文主要介绍了多层概图聚类算法中的精化算法。
3、基于多层概图模型的文档聚类算法
3.1、文档向量空间模型
Web文档经过预处理[]后,产生一系列原始数据,如特征词j在文档i中出现的次数fji ,包含特征词j的文档数dj 等。利用这些计数,在Rd空间建立n个文档向量 x1,x2,……,xn,文档向量xi的第j分量为
xji=tji×gj×si (1≤j≤d,1≤i≤n) (1)
其中,tji 是依赖于fji的特征词权重分量;gj是依赖于dj的全局权重分量;si是xi的范化分量。也就是说,tji 反映特征词在一篇文档中的相对重要性,而gj反映词在整个文档集中的全局重要性。该文档向量的权重模型,加强了不同文档向量的识别,从而加强了信息获取效 力。
对于特征词权重分量、全局权重分量和范化分量的取值方法有多种,我们采用较为通用的TF和IDF模型取值,即tji= fji, gj=1(TF模型)或gj=log(n/dj)(IDF模型),范化分量的取值采用L2范式,即
sj= (2)
一般来说,范化的目的是只获得文档向量模型的方,这保证了拥有相同主题(即使用了相似的特征词)的文档不会因为文档长度的不同而使其相似度减小。
3.2、向量相似度计算
根据(1)、(2)式,文档向量x1,x2,……,xn可以看作Rd空间单位球表面上的n个点。对多数权重模型来说,向量的各个分量均是非负的,因此文档向量在Rd空间处于非负方向,即 。对于向量模型,内积是一种自然的相似性度量准则。
给定 空间任意两个单位向量x和y,两者之间的角度可以表示为0≤θ(x,y)≤π/2,那么

因此,内积 常被称为”余弦相似度(cosine similarity)”。由于余弦相似度容易解释,对稀疏向量来说计算简单,因此在文本挖掘和信息抽取领域得到了广泛应用。
3.3、多层概图模型
在定义了文档向量的相似度以后,将n个文档向量映射为n个图的顶点,建立图模型H=(V,E),其中,V={v1,v2,…,vn}是图的顶点集合,E={e1,e2,…,em}是图的边集合。
图中,顶点的权重等于其连接的边数,边的权重等于所连接点的相似度,即余弦相似度。我们把原始数据集对应的图G0称为基图。从基图,G1=G0出发,经过 不断的概化操作,得到一系列概化程度逐步提高、点和边的规模逐步缩小的多层概图Gi(i=1…l)。我们称Gi是相对于Gi-1的概图,Gi-1是相对于 Gi的细图,Gl是最小概图。概化过程中,边和点的权重依据一定的规则得以在层间保留,并在反概化过程中又逐步映射回原始数据集,对最小概图应用k- way分割算法,形成图的划分,通过反向映射和周期性局部调整,在原始数据集中形成的划分就是聚类结果。
4、精化算法
由于随着图的顶点数增多,可能存在的分割数将呈指数增长,因此建立逐层概图模型、缩小分割对象的规模的主要目的是减小图分割的复杂度。但是,由于概化算法 的不足,概图的优化分割并不直接对应于较细图的优化分割,因此必须在从概图向细图映射的过程中应用精化算法,对细图的分割进行精化,以提高分割质量;然后 再向下一层细图映射,直到映射回基图。为此,我们总结Kernighan-Lin算法和Fiduccia-Mattheyses算法,对图的二分精化算法 进行推广,提出一种快而有效的精化算法。
4.1精化算法概述
我们的算法在FM算法的基础上,有以下几点改进:①可以优化任意数目的分割,而不局限于二分;②FM算法仅能处理顶点有权重的图,我们的算法能同时处理带 有顶点权重和边权重的图;③能进行任意整数个集合间的割集的消耗度量;④算法中采用一种随机机制以增强算法鲁棒性;⑤当只有少数点需要移动时,利用重用计 算(reuse computation)大幅减少运行时间。
与顶点在不同集合之间移动相联系的“增益(gain)”概念是KL之后精化算法的基本出发点。“增益”是指由于顶点在不同集合之间交换引起的割集权重的净减少。即,如果顶点i从集合l移动到集合K,相应的增益可以表示为:

其中P(j)是顶点j的当前所在集合,wij是顶点i和j之间边的权重,clk是连接集合l和k的边的对称集合间消耗度量,一般可取为1。
上式表明,如果一个顶点的增益是正的,那么移动该点会减少割集的总消耗或称为权重,无疑对优化分割是有利的。但是是否移动,必须考虑两个因素,一是分割的 规模约束,即考虑分割顶点集合的平衡性。如果要求最后的分割集合规模大致相当,在考察顶点移动时就要考虑相应的两个集合的规模因素;二是局部和全局的因 素,也许某个顶点的移动从当前来看是不利的,但从全局看也许由此引发的一系列顶点移动会使分割性能更为优化。
精化算法的基本结构如图1所示:
Until No better partition is discovered
Best Partition:=Current Partition
Compute all initial gains
Until Termination criteria reached
Select vertex to move
Perform move
Update gains of all neighbors of moved vertex
If Current Partition balanced and better than Best Partition Then
Best Partition:=Current Partition
End Until
Current Partition:=Best Partition
End Until
图1. 图分割精化算法
该算法包括含两个嵌套的循环。内循环完成一系列集合间点的移动,外循环持续探测改善分割的可能性。我们称外循环一次为一个轮次,每次内循环完成一个顶点的 移动,每个顶点在一轮次内只允许移动一次。点移动完成后,所有它的邻点的增益更新,然后进入下一个选择和移动的循环。为了突破局域限制,内循环中的最好分 割配置被记录下来,并进行更多点的移动和探索,直到满足终止条件跳出内循环;在进入下一轮次(外循环)时,数据按最优分割进行配置。
4.2精化算法的数据结构
FM算法使用一种相对复杂的数据结构,采用一种抽象的“桶”的概念存储所有可能移动的顶点增益。由于其针对二分图进行精化,假定顶点集合为A、B,所有从 A到B的可能移动点及其增益值存入一“桶”,从B到A的存入另一“桶”,并由大到小排序,具体可由双链列表实现。选择具有最高增益值的点,只需简单地寻找 最高的非空桶,然后把相应的点的序号从一个桶移到另一个桶,并更新所有相邻点的增益值。
我们的算法对FM作了扩展,使之能处理任意数目的集合。假定有s个集合,每次移动一个点,可能有s(s-1)个不同移动,我们为每个移动维持一个排序的桶 结构,则有s(s-1)个桶。共n个点,每个点可能移动到其它s-1个集合中,所以需要的存储空间是O(n(s-1))。也就是说,共有n(s-1)个候 选移动分布在s(s-1)个桶中,每个桶有中的候选移动由增益值自大到小排序。此种结构可以由经过排序的双链表实现,每个存储单元有两个指针,一个指针指 示其在桶中的位置,另一指针指示其所属的顶点,即每个增益值既可以按桶索引,也可按点索引。在进入最里层循环之前,计算所有的增益值并存储在相应的桶中, 计算复杂度为O((s-1)m)。进入内层循环之后,移动点的选择需要O(s(s-1)m)的时间,其余需要O(sm)的时间。
4.3循环的终止条件
循环的终止条件有两种,一种是从大集合到小集合的移动不再可能;另一种是无法改善分割质量而提前终止循环。实际上,第二种终止条件是有利的,虽然我们设计 了多层概图模型中的精化算法,但实际上希望尽量少地使用到,或即使用到,其做的改变也尽量小。对于第二种条件,我们比较遇到的最好分割和当前分割之间的质 量差异,如果这种差异越来越大,表明发现更好分割的可能性很小,内部循环随即终止。
4.4随机机制
当出现顶点的增益值相等时,如何处理将直接影响分割的结果。我们采用了随机选择的机制,初始增益值的计算是按随机顺序进行的,当增益值得到更新时,相应的 顶点及其增益值放在列表的最前端,然后其邻集的增益值逐步计算。另外,为了克服局域优化的问题,在外循环寻求更好的分割配置时失败时仍使算法继续循环三 次,以增加分割优化的可能性。
5、实验结果
为了评价多层概图文档聚类算法和传统聚类算法的性能,我们从网上收集了有关商业、娱乐、健康、政治、运动、技术、文学、农业等的文档874篇,进行文档预处理后,保留了1653个特征词。形成874×1653的数据表,表中第I行第j列表示文档I中出现的j特征词的次数。
运用本文算法,定义了数据对象之间的余弦相似度,并对相似度大于0.05的数据对象之间建立边,形成顶点数n=768(其余文档由于其与任何文档的相似度 均低于0.05,视为孤立点),边m=81253的基图。设k=8,我们应用多层概图算法对文档进行了聚类。由于类别之间文档数相差较大,我们对算法进行 了设置,对图进行分割时没有要求平衡性。作为对比,我们还应用autoclass对同一数据集进行聚类操作。分析聚类结果,多层概图方法的聚类结果,其8 个簇的文档数分别为c1=116,c2=108,c3=74,c4=85,c5=132,c6=94,c7=124,c8=35。其中,有关商业、娱乐、 健康、运动、农业、技术的文章聚集相关性较强,能较好的聚为一类,属于政治、文学的文档,大部分聚为相应的两个簇,有少部分被聚集到其它类中。以 autoclass方法进行文档的自动聚类,结果聚集为12个簇,具体分析时发现簇内文档有些混乱,许多相似性不大的、明显处于不同类的文档被划分到一 簇,总体聚类质量低于多层概图模型的质量。
6、结论与未来工作
文档聚类是高维聚类的重要应用领域。我们应用多层概图模型进行文档聚类,把文档对象作为图的顶点,以对象间的相似性建边,在对最小概图进行初始分割后,应用精化算法对划分进行逐层优化,取得了较好的效果。
本文应用的精化算法仍需要继续改进。精化操作,可以在多层概图算法的概化过程中应用,也可以设计在反概化过程中应用。作者将进一步深入精化算法的研究,进一步提高多层概图模型的性能。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP