首页 > 人工智能 > 一种基于连接图的 Web 文档聚类方法

一种基于连接图的 Web 文档聚类方法

 

09年的文章“Efficient Clustering of Web-Derived Data Sets”提出了一种基于连接图的web文档聚类方法,该方法不仅在性能可与平衡数据集上的streaming clustering(流聚类算法)相媲美,而且在处理稀疏、非平衡数据集时也加高效。

1.Web数据特点

Web数据集有着以下一些特点:数据量大;特征高维且稀疏;数据类别和特征呈典型的Zipfian分布。所以,web数据的聚类对聚类方法有更高的要求,比如”all-against-all”的方式会产生巨大的运算量,以及由于特征向量稀疏导致的与零向量相似等问题。

2.Streaming Clustering算法

在实际的web文档聚类中,每个数据样本只与类集群的某种摘要(比如:质心),或者少数几个样本点进行距离计算。最常用的方法聚类方法是Streaming Clustering,该方法就是用比较样本与各个类集群质心距离(也可称为相似度)的方式进行聚类的,其计算复杂度为线性的,(在理想条件下)对内存的要求也是可接受的。

Streaming Clustering算法的基本步骤如下:

setp 1. 把所有样本打乱并随机排列;

setp 2. 对每个未分类样本,重复下列过程,直至所有样本都被聚类:

a.计算该样本与所有类别质心(可看做类别的中心,用一组向量表示)的距离;

b.在所有距离中,如果最小距离小于预先设定的阈值min_dist,则把该样本归入这个距离最近的类别,同时更新该类别的质心向量;否则,把该样本作为一个新的分类。

该算法的时间和空间复杂度是很显然的。当样本数为n,类别数为C时,时间复杂度为O(nC),空间复杂度为O(C)(只需存储C个类别的质心)。

通过上面的算法步骤,可以简单分析下为什么高维稀疏的web数据会降低Streaming Clustering算法的性能。这是因为在计算某个数据样本和某个类别的质心距离时,该数据样本很可能属于该类别,却因为数据稀疏,而使两者特征向量中的非零特征交集为空(导致计算得到的相似度很低或空间距离很大),从而导致该样本被错分(false negatives),treaming Clustering算法会认为该样本属于一个未知的分类,进而使用该样本建立一个新的类别。这就使得一些dominant类别被拆分为很多很小的碎片类别,容易得到次优解,且计算量因为碎片类别的产生而大大增加。

3.基于连接图的web数据聚类

连接图G表达了所有数据样本的聚类信息:图中相连的两个样本表示它们的相似度大于某个阈值;所有相连的样本(connected components)都属于一个类别。构建G的直观做法是all-against-all的比较所有数据样本,但在时间和空间上都是不可接受的。

基于这种方式进行聚类,可以对false negatives更加健壮,这是因为图G中的每个结点都期望与其最相近的几个结点相连,false negatives的影响可以通过随机移除G中的边(edges)进行抵消。对于一个合理的连接图G,随机的移除一些边应该不会对connected components的连通性影响太大,这是因为那些关键的边(以很大的概率)不可能被同时移除。而且connected components越大,这种随机移除对连通性的影响越小,因此,我们可以建立一个简化的连接图G_min:每个结点只有一条边,且connected components的连通性与G是相同的。步骤如下:

step 1.随机打乱数据集S(n)得到S_rand(n),并对S_rand(n)中的样本进行从1到n的编号;

step 2. 对所有的样本重新以下步骤(从i=0开始):

a.取得索引为i的样本一种基于连接图的 Web 文档聚类方法 - 第1张  | 新闻中心;

b.重复下列过程直到找到k_pos条边:

比较一种基于连接图的 Web 文档聚类方法 - 第2张  | 新闻中心一种基于连接图的 Web 文档聚类方法 - 第3张  | 新闻中心;

j++;

该算法评价计算量如下(其中,|C|是真实类别的个数,pfn是false negatives的概率,k_pos是期望得到的每个样本点边的条数):

一种基于连接图的 Web 文档聚类方法 - 第4张  | 新闻中心保存在内存中的最大样本数为(其中,p_min为最小类别中样本数所占的百分比):

一种基于连接图的 Web 文档聚类方法 - 第5张  | 新闻中心原文后续又通过实验及一系列的数据分析、对比,从工程角度验证了上述算法的有效性,以及相比Streaming Clustering的优势。

最后编辑:
作者:兴明
这个作者貌似有点懒,什么都没有留下。

留下评论

你的email不会被公开。