２００７，４３（２２）
１引言
１．１相关概念
语义（Ｓｅｍａｎｔｉｃ）是一个语言学上的概念，它是语言文字能够对应于实体概念的体现，简单地说，有意义的语言文字信息就形成了语义。例如，讲到“计算机”，脑中就会出现计算机的一般形象，因此这个词，就含有了一定的语义。而不认识汉字的外国人看到这个词，则无法建立任何关于计算机实体的神经反射，对于他们来说，汉字的“计算机”不存在语义，而仅仅是一个符号。类似地，如果时光倒流几百年，中国的古人看到（繁体的）“计算机”三个字，也许他们知道“计算”和“机”这两个词，并且分别可以对应到实体语义，但是合起来却是他们所不能理解的一个概念，这同样是一种语义的缺失。但是与外国人不同的是，他们可以通过汉语的构词法简单地推测这个词的意思——
—用于计算的机器，尽管由于时代变迁计算机已不仅仅是计算功能，他们起码可以了解到部分的暗含的语义，或称之为潜在语义（ＬａｔｅｎｔＳｅｍａｎｔｉｃ）。他们之所以能得到潜在语义，是因为他们头脑中已经有了关于“计算”和“机”的语义，是基于已有知识和词法逻辑的简单推理（即语言学中形式语义学的研究内容，在计算机语言设计理论中也得到广泛应用）。信息检索中的潜在语义还有另外一层意思，即对于广大数目的数据对象，由于数据的内在特性，可能出现二元或者多元数据之间的关联并非随
机分布，而呈现一定的倾向性（比如某些词语共同出现的频率比较高，像本例中的“计算”和“机”，当然在现代分词方式中“计算机”会被切为一个词）。
语义网［１］是近年来发展起来的一种信息集成、发布、检索技术，它与传统的流行的ＨＴＭＬ网页最大的不同，就在于它是面向语义的（ＳｅｍａｎｔｉｃＯｒｉｅｎｔｅｄ），而传统的页面是面向表示的（ＰｒｅｓｅｎｔａｔｉｏｎＯｒｉｅｎｔｅｄ）。对于计算机来说，看到传统页面，它能够知道哪里是标题，哪里是链接，但是它无从知道标题说的是什么意思，链接的目的是什么，而语义网就可以让计算机“读
基于潜在语义的网络社区发现
班磊，方启明，武永卫，杨广文
ＢＡＮＬｅｉ，ＦＡＮＧＱｉ－ｍｉｎｇ，ＷＵＹｏｎｇ－ｗｅｉ，ＹＡＮＧＧｕａｎｇ－ｗｅｎ
清华大学计算机系清华信息科学与技术国家实验室（筹），北京１０００８４
ＴｓｉｎｇｈｕａＮａｔｉｏｎａｌＬａｂｏｒａｔｏｒｙｆｏｒＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００
８４，Ｃｈｉｎａ
Ｅ－ｍａｉｌ：ｂａｎｌｅｉ００＠ｍａｉｌｓ．ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ
ＢＡＮＬｅｉ，ＦＡＮＧＱｉ－ｍｉｎｇ，ＷＵＹｏｎｇ－ｗｅｉ，ｅｔａｌ．Ｗｅｂｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎｗｉｔｈｌａｔｅｎｔｓｅｍａｎｔｉｃｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（２２）：１１５－１１９．
Ａｂｓｔｒａｃｔ：ＷｅｅｘｐｌｏｒｅｔｈｅｌａｔｅｎｔｓｅｍａｎｔｉｃｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｂｌｏｇｐａｇｅｓｗｉｔｈｌｉｎｋｓｂｙａｍｅｔｈｏｄｓｉｍｉｌａｒｔｏＬＳＩｔｏｄｅｔｅｃｔｗｅｂｃｏｍｍｕｎｉｔｉｅｓ．Ｔｈｅｒｅｓｕｌｔｏｆｏｕｒｅｘｐｅｒｉｍｅｎｔｃｏｎｆｉｒｍｓｏｕｒｏｒｉｇｉｎａｌｉｄｅａｓｔｈａｔｗｅｂｌｉｎｋｓｃｏｎｔａｉｎｓｏｍｅｌａｔｅｎｔｓｅｍａｎｔｉｃｉｎｆｏｒｍａｔｉｏｎ．Ｎｏ－ｔｉｃｅｔｈａｔｓｅｍａｎｔｉｃｗｅｂｈａｓｎｏｄｉｆｆｅｒｅｎｃｅｗｉｔｈｃｕｒｒｅｎｔＨＴＭＬｗｅｂｏｎｌｉｎｋｓｅｘｃｅｐｔｆｏｒｓｏｍｅｓｅｍａｎｔｉｃｔａｇｓ，ｗｅｂｅｌｉｅｖｅｔｈｉｓｍｅｔｈｏｄｃａｎａｌｓｏｂｅａｐｐｌｉｅｄｔｏｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎａｎｄｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌｏｎｓｅｍａｎｔｉｃｗｅｂ，ｗｈｉｃｈｉｓｔｈｅｉｎｉｔｉａｌｇｏａｌｏｆｏｕｒｗｏｒｋ．Ａｎ－ｏｔｈｅｒｃｏｎｔｒｉｂｕｔｉｏ
ｎｏｆｔｈｉｓｐａｐｅｒｉｓｔｈａｔｗｅｄｏｓｏｍｅｏｐｔｉｍｉｚａｔｉｏｎｓｏｎＧＭＣｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｂｙｐｏｗｅｒｉｔｅｒａｔｉｏｎ，ｗｈｉｃｈｍａｋｅｓｉｔｍｕｃｈｆａｓｔｅｒｗｈｅｎｄｅａｌｉｎｇｗｉｔｈｈｕｇｅｄａｔａｓｏｕｒｃｅ．
Ｋｅｙｗｏｒｄｓ：ｓｅｍａｎｔｉｃｓｅａｒｃｈ；ｗｅｂｃｏｍｍｕｎｉｔｙ；ｌａｔｅｎｔｓｅｍａｎｔｉｃ；ＧＭＣｃｌｕｓｔｅｒｉｎｇ；ｐｏｗｅｒｉｔｅｒａｔｉｏｎ
摘要：采用类似于ＬＳＩ的方法，对于ｂｌｏｇ网页的链接进行了一次关于潜在语义的探索，借以发现网络社区。从实验的结果来看，基本验证了最初的想法，网页链接在一定程度上包含潜在语义的信息。注意到语义网与现今的ＨＴＭＬ网页在链接问题上思想基本一致（只是多了语义的标记），因此该方法同样适用于语义网内的社区发现与信息检索，这也是进行研究初衷。另一个贡献是通过幂迭代对ＧＭＣ聚类作了算法上的优化，使得在海量数据上的处理速度大大加快。
关键词：语义检索；网络社区；潜在语义；ＧＭＣ聚类；幂迭代
文章编号：１００２－８３３１（２００７）２２－０１１５－０５文献标识码：Ａ中图分类号：ＴＰ３１１
基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄ
ａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．９０４１２００６，Ｎｏ．９０４１２０１１，Ｎｏ．６０５７３１１０，Ｎｏ．９０６１２０１６，Ｎｏ．６０６７３１５２）；国家高技术研究发展计划（８６３）（ｔｈｅＮａｔｉｏｎａｌＨｉｇｈ－ＴｅｃｈＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔＰｌａｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００６ＡＡ０１Ａ１０１，Ｎｏ．２００６ＡＡ０１Ａ１０８，Ｎｏ．２００６ＡＡ０１Ａ１１１）；国家重点基础研究发展规划（９７３）（ｔｈｅＮａｔｉｏｎａｌＧｒａｎｄＦｕｎｄａｍｅｎｔａｌＲｅｓｅａｒｃｈ９７３ＰｒｏｇｒａｍｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００４ＣＢ３１８０００，Ｎｏ．２００３ＣＢ３１７００７）。
作者简介：班磊（１９８２－），男，硕士研究生，主要研究方向：信息检索。
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１１５
２００７，４３（２２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
懂”只有人才能理解的东西。为了实现这一目的，Ｂｅｒｎｅｒｓ－Ｌｅｅ提出了基于ＸＭＬ和描述逻辑的语义网七层体系结构［１］。语义网的初衷虽然很好，但是由于技术上的壁垒，以及重新改造现
有互联网规则的难度，推行起来相当困难，至今也只是在学术界比较流行。关于语义网的分歧和争议也时有出现，最近一次的著名的论战发生在美国人工智能协会（ＡＡＡＩ）上，论战双方是语义网的倡导者、被称为互联网之父的Ｂｅｒｎｅｒｓ－Ｌｅｅ和Ｇｏｏｇｌｅ搜索实验室主任ＰｅｔｅｒＮｏｒｖｉｇ，关于争论的详细内容参见文献［２］。
网络社区（ＷｅｂＣｏｍｍｕｎｉｔｙ）是指具有相同兴趣、爱好或者关注相同话题的一组用户所建立起来的一组网页／站点，这些页面通过链接或者引文的方式相互引用，以期浏览者能够对其所关注的话题有一个更深入的或者全面的了解，这是一个语义上的概念。发现网络社区对于信息检索来说具有很多的好处，最基本的一点，不同的网络社区讨论不同的话题，展示不同的内容，那么对于用户来讲，如果能将搜索结果以社区的方式呈现出来，辅之以适当的语义的描述，则就有助于用户迅速定位到他所感兴趣的内容，缩短了用户二次过滤的时间，这在查询词具有多义性的时候尤其的明显。比如同样是一个查询词“苹果”，一部分人可能关注的是作为水果的一种的苹果，另一部分人则可能关注的是作为ＩＴ公司的苹果。如果搜索结果能够自动地将这两类搜索结果聚合，那么用户就可以简单地做一次判断，剔除他不需要的那一部分，大大缩短了检索的时间。网络社区发现的另外一种功能，是可以辅助制作网页目录（ＷｅｂＤｉ－ｒｅｃｔｏｒｙ）。所谓网页目录，是指将具有相同属性、关注相同内容的网站集合起来，分门别类，放在网上供人查询浏览，与网络社区异曲同工。
１．２本文内容与结构
无论是现在的ＨＴＭＬ网页，还是正处于发展中的语义网，网络链接关系都是其中必不可少的一个组成元素，也是网络社区形成的一个重要机制。在上一小节中，已经说过，网络社区对信息检索加强语义相关性具有很重要的作用，而利用潜在语义是发现网络社区的一个重要途径，在这方面比较著名的工作是潜在语义索引算法（ＬａｔｅｎｔＳｅｍａｎｔｉｃＩｎｄｅｘｉｎｇ，ＬＳＩ）［３］。它利用文档不同关键词之间的相关性（共同出现的频率）来揭示文档间的潜在语义相关性，取得了很好的效果。回顾上一节关于潜在语义的定义，对于广大数目的数据对象，由于数据的内在特性，可能出现二元或者多元数据之间的关联并非随机分布，而呈现一定的倾向性的现象，都可以称为潜在语义。那么猜想不仅仅是文档内容，链接关系也应该会表现出一定的语义相关性，因为一篇文档总是会倾向于链接跟它内容（语义）相同或相似的文档，而不会莫名其妙地链接一篇毫无瓜葛的文章。正是基于这样的考虑，类比ＬＳＩ，试图通过链接关系来发现潜在语义进而发现网络社区。
注意到潜在语义表现出来的前提条件是大的数据规模，数据规模小的话不仅难以发现潜在语义相关性，而且及时发现了也不具有统计意义，没有说服力。应用是针对语义网的，但是由于语义网本身的一系列问题（前文中略有提及），并没有成规模的语义网的应用，这给实验带来了一定的问题。考虑到现有的ＨＴＭＬ网页数量庞大，而且在链接问题上与语义网并无二致，因此决定采用现有的ＨＴＭＬ网页作为数据源进行实验。在网页类型的选择上，考虑了两个因素：一个是流行度、互动性要好，即既要有数量庞大的数据源，又要有充分的链接关系；二是要结构化良好，具有一定程度的接近语义
的结构化特征，这样才能近似地模拟语义网（起码要能非常明确地分清楚非内容性链接（比如广告等）和内容性链接，前一部分的链接要被剔除，参见下文实验部分）。综合来看，最近几年兴起的ｂｌｏｇ页面最能满足这种要求，一方面用户数量非常大，而且还在飞速增加；另一方面用户活跃度非常高，由于ｂｌｏｇ具有非常方便的ｔｒａｃｋ－ｂａｃｋ功能，因此易于形成网络社区；还有就是ｂｌｏｇ的结构化程度非常高（所有的ｂｌｏｇ页面基本上都大同小异），相对其他类型的页面，它更接近于语义网的表示形式。
本文的剩余部分按照如下方式组织：第２章是模型以及算法介绍；第３章是针对海量数据的算法优化；第４章是实验过程及结果；最后是全文总结。
２模型和算法介绍
２．１模型和基本假设
基本的模型依赖于如下的一条假设：
页面中所有的链接都是语义相关的。
当然这个假设在一般情况下，无论对于现在的ＨＴＭＬ页面还是语义网，都是不成立的，因为出于盈利性或宣传性目的，绝大部分的公开页面都会有语义无关链接。因此第一步要做的，就是剔除每个页
面中语义无关的链接。对于语义网，可以根据页面的语义标记很轻松地进行过滤。而对于ｂｌｏｇ页面，由于其良好的页面结构，基本上也可以正确过滤掉绝大部分的语义无关链接。经过这样的处理以后，余下来的链接基本可以看作满足假设。
假设现在有Ｎ个文档，定义方阵Ｃ
Ｎ×Ｎ
＝（ｃ
ｉｊ
），满足以下条件：
如果ｉ＝ｊ，ｃ
ｉｊ
＝０；
如果ｉ≠ｊ并且ｉ与ｊ之间没有链接，ｃ
ｉｊ
＝０；
如果ｉ≠ｊ并且ｉ与ｊ有单向链接，ｃ
ｉｊ
＝１；
如果ｉ≠ｊ并且ｉ与ｊ有双向链接，ｃ
ｉｊ
＝２。
其中单向链接是指只有ｉ指向ｊ，没有ｊ指向ｉ；或者只有ｊ指向ｉ，没有ｉ指向ｊ。同理双向链接是指既有ｉ指向ｊ，又有ｊ指向ｉ。
可以看到这里忽略了链接的方向性，从而使得Ｃ
Ｎ×Ｎ
是对称矩阵，另一方面也忽略了链接的重复性，即对于从一个文档指向另一个文档的链接即使存在多个，也仅仅计算一次，这也符合写作ｂｌｏｇ时的用意：如果指向另一个文档的链接出现了多个，基本上是为了方便读者跳转，而不是为了语义上的强调。
这样下来就得到了类似ＬＳＩ中文档－关键词矩阵的一个文档链接（对称）矩阵，由于链接关系（相对于巨大的数据规模）的稀疏性，该矩阵实际上是一个很多元素为零的大规模稀疏矩阵，它的每一行或每一列都代表了一个文档与其他文档的链接关系，将其称为链接关系向量（ＬｉｎｋＲｅｌａｔｉｏｎＶｅｃｔｏｒ），同时也可以看作在Ｎ维空间中代表该文档的一个点。因此问题就转化为如何针对这些链接关系向量（点）进行聚类，以发现潜在语义，得到ｂｌｏｇ社区。
２．２算法描述
前面已经讲过，由于发现潜在语义本身的要求，实验数据量是非常大的（大约为１亿个ｂｌｏｇ页面，参见下文实验部分），这对算法的复杂度提出了非常苛刻的要求；另一方面，聚类的大小以及数目应该是不固定的，这对应于互联网上的社区有大有小、数目庞杂这一实际情况。因此，在考察算法时主要有３个
１１６
２００７，４３（２２）
标准：
（１）聚类效果：好的聚类效果是最基本的标准；
（２）算法复杂度：在不影响聚类效果的前提下，复杂度要尽
可能低；
（３）聚类限制：不能对聚类的数目和大小有明显的限制。
考查常用的聚类方法，主要可以分成两类。一类是关于数
据点的聚类，常见的算法有ＢＩＲＣＨ［４］、ＣＵＲＥ［５］、ＤＢＳＣＡＮ［６］、Ｋ－
ｍｅａｎｓ［７］等等，这些算法有些简单易行（比如Ｋ－ｍｅａｎｓ），有些复
杂度较低（比如ＢＩＲＣＨ），但是它们基本上都不满足第３个标
准：ＢＩＲＣＨ算法需提供正确的聚类个数和簇直径限制，对不可
视的高维数据不可行；ＣＵＲＥ和Ｋ－ｍｅａｎｓ需要预先确定聚类的
数目。ＤＢＳＣＡＮ虽然满足标准３，但是对聚类参数非常敏感，且
参数很难确定，需要根据ｋ－ｄｉｓｔ图来进行试探，这个对于海量
数据来说显然是不适用的。另一类的算法是关于图的聚类，但
由于问题的特殊性，可以将整个链接关系看成一张图，目的是
寻连接得最紧密的子图，因此也特意考察了图聚类的算法。
常用的图聚类算法有ＭＣＬ（ＭａｒｋｏｖＣｌｕｓｔｅｒｉｎｇ）［８］、ＩＣＣ（Ｉｔｅｒａｔｉｖｅ
ＣｏｎｄｕｃｔａｎｃｅＣｕｔｔｉｎｇ）［９］、ＧＭＣ（ＧｅｏｍｅｔｒｉｃＭＳＴＣｌｕｓｔｅｒｉｎｇ，这里
ＭＳＴ代表最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ）［１０］等。首先ＩＣＣ
可以被排除，因为ＩＣＣ需要设定类的大小阈值，然后根据最小
割算法对图进行二分直到所有的类（子图）大小小于阈值。ＭＣＬ
是一种聚类结果良好的随机游走算法（根据文献［１１］的实验，它
的聚类结果比ＩＣＣ和ＧＭＣ都要好），而且也满足标准３，但是
它对实验来说有一个致命的缺点，就是运算复杂度太高，因为
随机游走在若干步以后可以到达大部分节点，使得整个概率矩
阵迅速变得稠密，而这对于大规模矩阵是十分不利的。然后剩
下的就只有ＧＭＣ算法，ＧＭＣ算法同ＭＣＬ一样，也是算法复杂
度比较高，因为它需要计算邻接矩阵的若干个极端的特征对，
对于单个极端特征对有幂迭代等等算法，但是要计算很多个的
话一般的方法是通过分解矩阵把所有的特征对都计算出来，这
就大大增加了计算的复杂度，实际上在文献［１０，１１］中他们也是
这么做的。那么除此之外就没有比较好的复杂度比较低的解决
办法了吗？鉴于应用的特殊性，幸运的是对于ＧＭＣ来说有的，
这也是本文的主要贡献之一，关于这一部分的内容，将在第３
章来讲。下面首先来介绍一下ＧＭＣ算法。
ＧＭＣ算法是从谱方法（ＳｐｅｃｔｒａｌＭｅｔｈｏｄｓ）演化而来的。谱
方法是一类方法的统称，这类方法的基本步骤如下：
（１）根据图的权重生成邻接矩阵；
（２）计算邻接矩阵的ｋ个最大特征值对应的特征向量；
（３）通过这ｋ个特征向量来完成聚类。
所有的谱方法第（１）步几乎都是一模一样的。而对于ＧＭＣ
算法来说，在第（２）步中ｋ通常取２或者３。最重要的是第（３）
步，它直接关系到最后生成的聚类结果的好坏。ＧＭＣ的第（３）
步详细过程如下：
（１）根据ｋ个特征向量生成加权和ｖ；
（２）重新定义权重ｗ
ｉｊ＝ｖ
ｉ
－ｖ
ｊ
；
（３）根据新的权重生成最小生成树；
（４）根据给定的阈值，砍掉最小生成树中权重小于该阈值的边；
（５）最小生成树中的连通分支即最后的聚类结果。
其中在第（４）步中的阈值一般根据最小生成树的权重情况自动生成而不是人为给定一个具体的固定的数值。综合起来重新整理一下，ＧＭＣ的标准步骤是：
（１）计算规范化（ｎｏｒｍａｌｉｚｅｄ）的邻接矩阵（所谓归范化，即是将每行的元素除以该行的元素和使得矩阵每行元素和恒为１）；
（２）计算除１之外的ｋ个最大特征值对应的特征向量（一般ｋ＝２或３）（显然，在规一化之后，邻接矩阵恒具有特征值１和特征向量（１，１，…，１）Ｔ，因此予以排除）；
（３）根据特征向量计算新权重；
（４）根据新权重生成最小生成树；
（５）计算最小生成树的平均权重和最大权重；
（６）根据平均权重和最大权重计算用于剪裁的阈值；
（７）根据阈值剪裁最小生成树的边；
（８）得到最小生成树的连通分支即是聚类的结果。
综观ＧＭＣ算法，除第（２）步计算特征值以外，其它步骤均具有较低的计算复杂度，并且没有限制到生成的类的大小和个数，唯一需要给出的阈值也是由最小生成树自身确定，不需要特别指定。因此，如果能够解决第（２）步的计算复杂度问题，那么整个问题便可以迎刃而解。
３算法优化
大家知道计算单个极端特征值和其对应的特征向量有幂迭代、反幂迭代等比较高效的算法。根据上一章对算法的描述，问题在于要计算好几个的极端特征对。因此，寻一种可行的方法，可以连续地将极端特征对通过幂迭代逐一计算出来，得益于实对称矩阵良好的代数性质和本问题的特殊性，下面一一展开来说。
３．１幂迭代算法（ＰｏｗｅｒＩｔｅｒａｔｉｏｎＭｅｔｈｏｄ）
幂迭代算法是用于求大型稀疏矩阵的主特征值（绝对值最大的特征值称为主特征值）的迭代方法，其特点是公式简单，易于实现。鉴于大部分数值分析教材中都会讲述此方法，在此就不再赘述，仅列出它的性质：
定理１设Ａ∈Ｒｎ×ｎ有完全特征向量系，若!
１
，!
２
，…，!
ｎ
为Ａ的ｎ个特征值且满足
!
１
≥!２≥…≥!ｎ
对任取初始向量ｘ（０）∈Ｒｎ，对乘幂公式
ｘ（ｋ＋１）＝Ａｘ（ｋ）
确定的迭代序列｛ｘ（ｋ）｝，有下述结论：
（１）当!
１
＞!
２
时，对ｉ＝１，２，…，ｎ
ｌｉｍ
ｋ→∞
ｘ
ｉ
（ｋ＋１）
ｘ
ｉ
（ｋ）
＝!
１
收敛速度取决于ｒ＝
!
２
!
１
＜１的程度，ｒ＜＜１收敛快，ｒ≈１收
敛慢，且ｘ（ｋ）（当ｋ充分大时）为相应于!
１
的特征向量的近似值。
（２）当!
１
＝!
２
＞!
３
时
①若!
１
＝!
２
，则主特征值!
１
及相应特征向量的求法同（１）；
②若!
１
＝－!
２
，对ｉ＝１，２，…，ｎ
ｌｉｍ
ｋ→∞
ｘ
ｉ
（ｋ＋１）
ｘ
ｉ
（ｋ）
＝!２
１
收敛速度取决于ｒ＝
!
３
!
１
＜１的程度。向量ｘ（ｋ＋１）＋!
２
ｘ（ｋ），
班磊，方启明，武永卫，等：基于潜在语义的网络社区发现１１７
２００７，４３（２２）
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
ｘ
（ｋ＋１）
－!１ｘ（ｋ）
分别为主特征值!１，!２相应的特征向量的近似值。
③若!１＝!!２，则连续迭代两次，计算出ｘ（ｋ＋１），ｘ（ｋ＋２）
然后对ｊ＝
１，
２，…，ｎ解方程ｘｊ
（ｋ＋２）
＋ｐｘｊ
（ｋ＋１）
＋ｑｘｊ（ｋ）
＝０
求出ｐ、ｑ后，由公式
!１＝－ｐ２
＋ｉ
ｑ－
ｐ２
"#
２
$!２
＝－ｐ２－ｉｑ－ｐ
２%&２
$
解出主特征值!１，!２。此时收敛速度取决于ｒ＝!
３!１
＜１的
程度。向量ｘ
（ｋ＋１）
－!２ｘ（ｋ），ｘ
（ｋ＋１）
－!１ｘ（ｋ）
分别为相应于!１，
!２的特征向量的近似值。
从幂迭代的计算过程中可以看到，幂迭代不会改变原矩阵的稀疏性，因此对于应用来说会大大地加速计算过程，这也是采用此算法的主要原因。
３．２实对称矩阵的幂迭代特性
由３．１节的介绍可以看到，幂迭代的使用还是有其局限性
的，它只适用于主特征值的情况，而在应用中，需要求出两到三个除１以外的最大特征值对应的特征向量。这样就有一个难题：如何利用求出主特征值以外的其它特征值对应的特征向量？这个问题对于一般的矩阵来说很困难，几乎没有很好的办法。但是对于实对称矩阵来说，它却拥有天然的良好的特性，可以利用幂迭代顺次解决。
仍然采用３．１节的符号，不过在此假设Ａ∈Ｒｎ×ｎ
是对称矩
阵，有以下定理保证了Ａ具有完全特征向量系：
定理２实对称矩阵的特征值都是实数。
定理３若Ａ是ｎ阶实对称矩阵，
!１，!２，…，!ｎ是Ａ的ｎ个特征值，那么一定存在正交阵Ｔ，使得Ｔ－１
ＡＴ＝ＴＴ
ＡＴ＝ｄｉａｇ（!１，!２，…，!ｎ）
。这些定理的证明一般的代数书上都有，因此不再赘述。这样，实对称矩阵是一定满足定理３的前提条件的。依然假设!１≥!２≥…≥!ｎ，对应的特征值分别为ｖ１，ｖ２，…，ｖｎ，那么显然就有
Ａ＝（ｖ１，ｖ２，…，ｖｎ）・ｄｉａｇ（!１，!２，…，!ｎ）・（ｖ１，ｖ２，…，ｖｎ）Ｔ
＝
!１ｖ１ｖＴ
１＋!２ｖ２ｖＴ
２＋…＋!ｎｖｎｖＴ
ｎ
（１）
假如现在已经用幂迭代法求出了主特征对!１和ｖ１，那么对于第二大的特征对，可以稍作变换，由式（１）
Ａ－!１ｖ１ｖＴ
１＝!２ｖ２ｖＴ
２＋…＋!ｎｖｎｖＴ
ｎ＋０ｖ１ｖＴ
１＝
（ｖ２，ｖ３，…，ｖｎ，ｖ１）・ｄｉａｇ（!２，!３，…，!ｎ，!１）・（ｖ２，ｖ３，…，ｖｎ，ｖ０）
Ｔ
（２）
由此可以看到，Ａ－!１ｖ１ｖＴ
１仍然是对称矩阵，并且以!２为主特征值，因此当第一对特征对解出之后，可以继续使用幂迭代算法，对原矩阵稍作变换，来计算!２及其对应的特征向量ｖ２；以此类推，后续的各个特征值和特征向量也可以一一解出（直到生于特征值全部为０，即矩阵变为０矩阵）。
３．３ＧＭＣ的数值解法
之所以花费这么多篇幅介绍幂迭代及实对称矩阵的幂迭
代，是因为可以通过适当的变换，将原ＧＭＣ问题转化为对称矩
阵的特征对问题，从而使问题迎刃而解，现在来看如何进行这种转换。
由３．２节的基本模型可以看到，由于忽略了链接的方向性，生成的邻接矩阵Ｃ本身就是一个对称矩阵，但是由于ＧＭＣ的第１步要进行规范化，导致规范化后的邻接矩阵（不妨记为Ａ）对称性消失，从而给应用幂迭代算法造成困难。现在还原这一过程，假设Ｃ的各行元素和组成的对角阵为Ｄ，那么就有
Ａ＝Ｄ－１
Ｃ
（３）
假设!和ｖ是Ａ的一对特征对，由上式，有
Ａｖ＝!ｖ)Ｄ－１
Ｃｖ＝!ｖ)Ｄ１／２
Ｄ－１
Ｃｖ＝Ｄ１／２
!ｖ)Ｄ１／２
Ｃｖ＝!Ｄ１／２
ｖ)
Ｄ１／２
ＣＤ－１／２
・Ｄ１／２
ｖ＝!Ｄ１／２
ｖ
（４）
注意到Ｄ为正定的对角阵，因此Ｄ可以像单个正整数一
样进行指数运算。根据式（４）的结果，可以发现，Ａ的特征对（!，ｖ）对应于Ｄ１／２
ＣＤ
－１／２
的一个特征对（!，
Ｄ１／２
ｖ）。由于式（４）的推理步步都是可逆的，因此Ａ的特征对就和Ｄ１／２
ＣＤ
－１／２
的特征对建
立起一一对应的关系，这样可以先求Ｄ１／２
ＣＤ－１／２
的特征对，
再转而求Ａ的特征对，中间只需要经过一个简单的变换。
接下来再来看Ｄ１／２
ＣＤ
－１／２
这个矩阵，由于Ｃ是对称阵，Ｄ是
对角阵（当然也就对称），因此Ｄ１／２
ＣＤ－１／２
也是对称阵，这样它的
特征对通过幂迭代便不难求出；另外，Ｃ是稀疏矩阵，Ｄ１／２
ＣＤ
－１／２
相当于在Ｃ两边各乘以一个对角阵，Ｃ的每个元素只会放大或者缩小一定的倍数，丝毫不影响其稀疏性，这是这个变换的另一个优点，保持了原矩阵的稀疏性。
此外还要注意的一点是ＧＭＣ中要求的是两到三个除１以外的最大特征值，而幂迭代求出的是绝对值最大的特征值，这其中只要做一个简单的变换就可以满足要求。由于Ａ是规范化的，由矩阵的圆盘定理易知其谱半径为１，即所有的特征值都落在［－１，１］区间内，只需要再简单地对Ａ做一个ｓｈｉｆｔ，让Ａ变作Ａ＋Ｉ，就可以保证所有的特征值都是正的，这时候再作幂迭代就可以了。
４实验结果
４．１实验数据与预处理网络上xml是什么意思
本文的实验数据来自于百度公司的ｏｆｆｌｉｎｅｗｅｂｄａｔａｂａｓｅ（在此表示感谢），其中存储了大概有一亿个ｂｌｏｇ页面，各个页面的链接已经事先解析出来存在了数据库里，因此预处理的工作主要包含了三个部分：一是如前文中所述剔除语义无关的链接，包括站内链接和广告链接等；二是去除冗余页面，对于不同时间戳标记的同一页面，只取最新的页面作为实验数据；从前文的描述中也可以看到，应用ＧＭＣ的前提条件是图必须是连
通的，否则规范化的时候会出问题，因此预处理的另一个重要
步骤就是提取图的连通分支分别应用ＧＭＣ算法。
４．２实验结果
时间性能：对于这大约１亿个ｂｌｏｇ页面，在单台ＵＮＩＸ服务器上（志强双核２．８，２Ｇ内存）全部连通分支跑完大概用了１５０ｍｉｎ，时间性能还是相当的良好的，在可以接受的范围内。由于数据处理起来的复杂度以及运行时间的问题，并没有试图
１１８
２００７，４３（２２）
（上接１１４页）
样位数为１６位的ＰＣＭ格式。图２－图５分别给出了谱相减法、ＭＭＳＥ－ＬＳＡ和基于快速噪声估计的ＭＭＳＥ语音增强算法各自的增强时域图，实验中帧长取２５６点，帧移１２８点，加窗处理中采用汉宁窗。图６给出了几种语音增强算法在白噪声和Ｆ１６战斗机噪声环境下改进的分段信噪比。
图６中横轴表示带噪语音的分段信噪比（－１０ｄＢ，－５ｄＢ，０ｄＢ，５ｄＢ），纵轴表示改进的分段信噪比。＊表示谱相减法，＋表示ＭＭＳＥ－ＬＳＡ法，∧表示基于快速噪声估计的ＭＭＳＥ增强算法。
４小结
基于快速噪声估计的ＭＭＳＥ语音增强算法较之谱相减法和基于语音短时对数谱的最小均方误差（ＭＭＳＥ－ＬＳＡ）算法在语音听觉的质量与自然度上都有较明显的改进，能更好地抑制背景噪声和残留的“音乐噪声”。噪声估计算法简单，计算量小，适合应用于真实的噪声环境中。（收稿日期：２００７年３月）
参考文献：
［１］ＳｕｎｄａｒｒａｊａｎＲａｎｇａｃｈａｒｉ，ＬｏｉｚｏｕＰＣ．Ａｎｏｉｓｅ－ｅｓｔｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｈｉｇｈｌｙｎｏｎ－ｓｔａｔｉｏｎａｒｙｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］．ＳｐｅｅｃｈＣｏｍｍｕｎｉｃａｔｉｏｎ，２００６，４８：２２０－２３１．
［２］ＣｏｈｅｎＩ．Ｎｏｉｓｅｅｓｔｉｍａｔｉｏｎｂｙｍｉｎｉｍａｃｏｎｔｒｏｌｌｅｄｒｅｃｕｒｓｉｖｅａｖｅｒａｇｅｉｎｇｆｏｒｒｏｂｕｓｔｓｐｅｅｃｈｅｎｈａｎｃｅｍｅｎｔ［Ｊ］．ＩＥＥＥＳｉｇｎａｌＰｒｏｃｅｓｓ，２００２，９（１）：１２－１５．
［３］ＹａｒｉｖＥｐｈｒａｉｍ，ＭａｌａｈＤ．Ｓｐｅｅｃｈｅｎｈａｎｃｅｍｅｎｔｕｓｉｎｇａｍｉｎｉｍｕｍｍｅａｎ－ｓｑｕａｒｅｅｒｒｏｒｓｈｏｒｔ－ｔｉｍｅｓｐｅｃｔｒａｌａｍｐｌｉｔｕｄｅｅｓｔｉｍａｔｏｒ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＡｃｏｕｓｔｉｃｓ，ＳｐｅｅｃｈａｎｄＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，１９８４，ＡＳＳＰ－３２（６）．
［４］姜琳峰，石鸿凌，孙洪．基于最优平滑和统计最小的语音增强［Ｊ］．武汉大学学报：理学版，２００４，５０（１）：１１３－１１７．
与其它的聚类算法作对比。
聚类效果：最终形成了大约３０万个ｃｌｕｓｔｅｒ，按其ｓｉｚｅ基本分布如图１所示。从图中可以看出，大小在１００－１０００的ｃｌｕｓｔｅｒ占据了绝大部分，而在１００以下的也有相当多，１０００以上的ｃｌｕｓｔｅｒ很少。从内容来看，大部分处于同一ｃｌｕｓｔｅｒ的ｂｌｏｇ是内容相关的，这在ｃｌｕｓｔｅｒ的ｓｉｚｅ比较大时表现得尤其明显，这正好验证了最初的想法，链接关系也可以反映出一定的潜在语义性。ｃｌｕｓｔｅｒ的ｓｉｚｅ比较小时，表现出来的语义相关性不是很明显，猜想可能是由于链接关系比较弱的原因。由于语义相关性还缺乏一个明确的评判标准和成熟的评判方法，再者形成的ｃｌｕｓｔｅｒ比较多，无法一一甄别形成量化的数据，因此在这里只能泛泛而谈。但是整体的趋势是毋庸置疑的，链接关系越强，体现出来的潜在语义相关性也就越明显。
５结论及进一步的工作
本文采用类似于ＬＳＩ的方法，对于ｂｌｏｇ网页的链接进行了一次关于潜在语义的探索，借以发现网络社区，提高信息检索的语义相关性。从实验的结果来看，基本验证了最初的想法，网页链接在一定程度上包含潜在语义的信息。注意到语义网与现今的ＨＴＭＬ网页在链接问题上思想基本一致（只是多了语义的标记），因此相信该方法同样适用于语义网内的社区发现与信息检索，这也是进行本文工作的初衷。本文的另一个贡献是对ＧＭＣ聚类作了算法上的优化，使得在海量数据上的聚类速度大大加快。
从最后的链接结果来看，相对于如此巨大的数据量，最后形成的聚类的大小普遍偏小，这是一个主要的问题。以后可以考虑与ＬＳＩ结合起来，从两方面着手，增加聚类的大小，提高聚类的效果。（收稿日期：２００７年５月）
参考文献：
［１］Ｂｅｒｎｅｒｓ－ＬｅｅＴ．ＳｅｍａｎｔｉｃＷｅｂＸＭＬ２０００［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／２０００／Ｔａｌｋｓ／１２０６－ｘｍｌ２ｋ－ｔｂｌ／ｓｌｉｄｅ１０－０．ｈｔｍｌ．
［２］ＡＡＡＩ：ＧｏｏｇｌｅａｎｄｔｈｅＳｅｍａｎｔｉｃ，Ｓａｔａｎｉｃ，ＲｏｍａｎｔｉｃＷｅｂ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｎｏｄａｌｐｏｉｎｔ．ｏｒｇ／２００６／０７／１９／ａａａｉ＿ｇｏｏｇｌｅ＿ａｎｄ＿ｔｈｅ＿ｓｅｍａｎｔｉｃ＿ｓａｔａｎｉｃ＿ｒｏｍａｎｔｉｃ＿ｗｅｂ．
［３］ＫｌｅｉｎｂｅｒｇＪＭ．Ａｕｔｈｏｒｉｔａｔｉｖｅｓｏｕｒｃｅｓｉｎａｈｙｐｅｒｌｉｎｋｅｄｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＪｏｕｒｎａｌｏｆｔｈｅＡＣＭ，１９９９，４６（５）：６０４－６３２．
［４］ＺｈａｎｇＴ，ＲａｍａｋｒｉｓｈｎａｎＲ，ＬｉｖｎｙＭ．ＢＩＲＣＨ：ａｎｅｆｆｉｃｉｅｎｔｄａｔａｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｆｏｒｖｅｒｙｌａｒｇｅｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１９９６ＡＣＭＳＩＧＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＭａｎａｇｅｍｅｎｔｏｆＤａｔａ，Ｍｏｎｔｒｅａｌ，Ｑｕｅｂｅｃ，Ｃａｎａｄａ，１９９９：１０３－１１４．
［５］ＧｕｈａＳ，ＲａｓｔｏｇｉＲ，ＳｈｉｍＫ．ＣＵＲＥ：ａｎｅｆｆｉｃｉｅｎｔｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｌａｒｇｅｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１９９８ＡＣＭＳＩＧＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＭａｎａｇｅｍｅｎｔｏｆＤａｔａ，Ｓｅａｔｔｌｅ，Ｗａｓｈｉｎｇｔｏｎ，ＵｎｉｔｅｄＳｔａｔｅｓ，１９９８：７３－８４．
［６］ＥｓｔｅｒＭ，ＫｒｉｅｇｅｌＨＰ，ＳａｎｄｅｒＪ，ｅｔａｌ．Ａｄｅｎｓｉｔｙ－ｂａｓｅｄａｌｇｏｒｉｔｈｍｆｏｒｄｉｓｃｏｖｅｒｉｎｇｃｌｕｓｔｅｒｓｉｎｌａｒｇｅｓｐａｔｉａｌｄａｔａｂａｓｅｗｉｔｈｎｏｉｓｅ［Ｃ］／／Ｉｎｔ’ｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅｓａｎｄＤａｔａＭｉｎｉｎｇ（ＫＤＤ－９６），Ｐｏｒｔｌａｎｄ，Ｏｒｅｇｏｎ，Ａｕｇｕｓｔ１９９６．
［７］ＭａｃＱｕｅｅｎＪ．Ｓｏｍｅｍｅｔｈｏｄｓｆｏｒｃｌａｓｓｉｃａｔｉｏｎａｎｄａｎａｌｙｓｉｓｏｆｍｕｌｔｉｖａｒｉａｔｅｏｂｓｅｒｖａｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃ５ｔｈＢｅｒｋｅｌｅｙＳｙｍｐＭａｔｈＳｔａｔｉｓｔＰｒｏｂ，１９６７．
［８］ｖａｎＤｏｎｇｅｎＳＭ．Ｇｒａｐｈｃｌｕｓｔｅｒｉｎｇｂｙｆｌｏｗｓｉｍｕｌａｔｉｏｎ［Ｄ］．ＵｎｉｖｅｒｓｉｔｙｏｆＵｔｒｅｃｈｔ，２０００．
［９］ＫａｎｎａｎＲ，ＶａｍｐａｌａＳ，ＶｅｔｔａＡ．Ｏｎｃｌｕｓｔｅｒｉｎｇ－ｇｏｏｄ，ｂａｄａｎｄｓｐｅｃｔｒａｌ［Ｃ］／／ＦｏｕｎｄａｔｉｏｎｓｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ２０００，２０００：３６７－３７８．［１０］ＧａｅｒｔｌｅｒＭ．Ｃｌｕｓｔｅｒｉｎｇｗｉｔｈｓｐｅｃｔｒａｌｍｅｔｈｏｄｓ［Ｄ］．Ｕｎｉｖｅｒｓｉｔ!ａｔＫｏｎ－ｓｔａｎｚ，２００２．
［１１］ＢｒａｎｄｅｓＵ，ＧａｅｒｔｌｅｒＭ，ＷａｇｎｅｒＤ．Ｅｘｐｅｒｉｍｅｎｔｓｏｎｇｒａｐｈｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓ［Ｃ］／／ＬＮＣＳ２００３：Ｐｒｏｃ１１ｔｈＥｕｒｏｐＳｙｍｐＡｌｇｏｒｉｔｈｍｓ（ＥＳＡ’０３），Ｓｐｒｉｎｇｅｒ，２００３．
班磊，方启明，武永卫，等：
基于潜在语义的网络社区发现１１９

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。