首页 > 人工智能 > 对 Web 数据的高性能聚类

对 Web 数据的高性能聚类

 

由于工作中需要对大量数据进行聚类,因此阅读了论文“Efficient Clustering of web-derived data sets”。该论文中的方法,从时间复杂度上来说,要优于k-means。

Web数据的特点是数据量大、高维、特征稀疏,类别和特征都符合Zipfian分布。对这类数据的聚类,可以采用streaming clustering算法。算法框架如下:

1. 将所有数据随机打乱,并顺序访问;
2. 对下一条还未被聚类的item:
    2.1 将该item与已有的所有cluster中心对比;
    2.2 如果与最近聚类中心的距离小于mindist,则将该item分配给最近的cluster,
        并更新该cluster的中心;
    2.3 否则,创建一个只包含该item的新cluster。

该算法的时间复杂度为O(nCf),空间复杂度为O(Cf)。Cf是cluster的数量,n是参与聚类的item数量。因此该算法是scalable的。但问题是容易分散,大的cluster容易分为很多小的cluster。

为了解决聚类分散的问题,可以采用如下方式的聚类定义:每一个item对应一个点,如果两item之间的相似度大于一个阈值,则这两点之间连上一边条,那么在这些item及连接它们的边组成的图中,每一个连通的部分都对应一个cluster。

Naive的算法需要对所有的item两两比较,时间复杂度是平方级别的。关键的优化在于,对一个item来说,不需要与其他所有item比较,只需要比较足够多的其他item,得到kpos个相似item就可以得到相同的连通图集合。优化后的寻找连通图的算法如下:

1. 将所有item随机打乱,并给每个item赋一个序号;
2. 对所有item,从i=0开始:
    2.1 取第i个item,Ii,
    2.2 令j=1,
    2.3 重复以下步骤直到找到kpos个相似的item:
        2.3.1 比较Ii与Ii+j
        2.3.2 j加1

该算法的平均时间复杂度为O(n|C|kpos/(1-pfn)),其中|C|为聚类的数量,pfn是两item属于同一个聚类,但其相似度小于阈值的概率。

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

留下评论

你的email不会被公开。