2.1.2基于潜在语义的网络社区发现算法
首先我们先做个假设：页面中所有的连接都是语义相关的。
当然这个假设在一般情况下．无论对于现在的HTML页面还是语义网，都是不成立的，因为出于盈利性或宣传性目的，绝大部分的公开页面都会有语义无关链接。因此第一步要做的，就是剔除每个页面中语义无关的链接。对于语义网，可以根据页面的语义标记很轻松地进行过滤。而对于blog页面，由于其良好的页面结构，基本上也可以正确过滤掉绝大部分的语义无关链接。经过这样的处理以后，余下来的链接基本可以看作满足假设。
假设现在有N个文档，定义方阵CN×N=（Cij），满足以下条件：如果i=j,cij=0；如果i≠j并且i与j有没有链接，cij=0；如果i≠j并且i与j有单向链接，cij=1；如果i≠j并且i与j有双向链接，cij=2；其中单向链接是指只有i指向j,没有j指向i；或者只有j指向i,没有i指向j。同理双向链接是指既有i指向j,又有j指向i。可以看到这里忽略了链接的方向性，从而使得CN×N是对称矩阵，另一方面也忽略了链接的重复性，即对于一个文档指向另一个文档的链接即使存在多个，也仅仅计算一次，这也符合写作blog时的用意；如果指向另一个文档的链接出现了多个，基本上市为了方便读者跳转，而不是为了语义上的强调。
这样下来就得到了类似LSI中文档-关键词矩阵的一个文档链接矩阵，由于链接关系稀疏性，该矩阵实际上市一个很多元素为零的大规模稀疏矩阵，它的每一行或每一列都代表了一个文档与其他文档的链接关系，将其称为链接关系向量(Link Relation Vector)，同时也可以看作在Ⅳ文空间中代表该文档的一个点。因此问题就转化为如何针对这些链接关系向量(点)进行聚类，以发现潜在语义，得到社区。
由于潜在语义自身的要求，数据量非常大，另一方面，大小及数目的不固定，因此，我们在观察算法时应该有3个标准⑴类聚效果：好的类聚效果是最基本的标准；⑵算法复杂度：在不影响聚类效果的前提下，复杂要尽可能低；⑶聚类限制：不能对象聚类的数目和大小有明显的限制。
常见的聚类方法分成两类。一类是关于数据点的类聚，算法有BIRCH(复杂度比较低)，K-means（简单易行），CURE，DBSCAN等，但是他们无法满足第3个标准。另一类算法是关于图的聚类，但由于问题的特殊性，可以将整个链接关系看成一张图，目的是寻找连接得最紧密的子图，因此也特意考察了图类聚的算法。常见的类聚算法有Markov Clustering（马尔可夫聚类，简称MCL）、Iterative Conductance Cutting(迭代电导切割，简称ICC)、Geometric MST Clustering(几何生成树聚类,简称CMC)等。首先ICC算法需要设定类得大小网址，然后根据最小割算法对图进行二分直到所有的类大小小于阈值。MCL算法是一种聚类结果良好的随机游走算法，而且满足标准3，但是它有一个非常致命的缺点，就是复杂度太高，所以对于大规模矩阵是非常不利的。而GMC算法和MCL算法一样，计算复杂度比较高，因为它需要计算邻接矩阵的若干个计算的特征对，对于单个极端特征对有幂迭代等算法，但是要计算很多个的话一般的方法就是通过分解矩阵把所有的特征对都计算出来，这就大大地增加了计算的复杂程度。本文来自辣,文'论#文^网，
毕业论文 www.751com.cn下面我们来介绍下GMC算法。
GMC算法是从谱方法演化而来的。谱方法是一类方法的统称，这类方法的基本步骤如下：⑴根据图的权重生成邻接矩阵；⑵计算邻接举证的k个最大特征值对应的特征向量；⑶通过这个k个特征向量来完成聚类。
所有的谱方法第一步几乎是一样的。而第2步在GMC算法中k的值一般取2或者3。第3步，关系到最后聚类的好坏。GMC的第3步详细可分为以下几步骤：⑴根据k个特征向量生成加权和v⑵重新定义权重wij=|vi-vj|;⑶根据新的权重生成最小生成树⑷根据给订的阈值，砍掉最小生成树中权重小于该阈值的边：⑸最小生成树中的连通分支局势最后的聚类结果。在第4步中的阈值基本上是根据最小生成树的权重情况自动生成的值而不是人们给定的一个具体固定数值。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页
GN算法的设计与源代码+网络社区发现算法分析与比较 第4页下载如图片无法显示或论文不完整，请联系qq752018766
