k-medoids算法在大数据集上的效率如何？

像PAM这样的经典k-medoids划分算法在小型数据集上效率很高，但在大数据集上却难以扩展。对于较大的数据集，可以使用一种基于采样的方法，称为CLARA（Clustering Large Applications）。

CLARA背后的方法如下：如果样本以相当随机的方式选择，它必须紧密地定义原始数据集。选择的代表性对象（medoids）将类似于从整个数据集选择的那些对象。CLARA从数据集中抽取多个样本，对每个样本应用PAM，并将其最佳聚类作为输出返回。

CLARA的性能基于样本大小。观察到PAM在一个给定数据集之间搜索最佳k个medoids，而CLARA搜索所选数据集样本之间的最佳k个medoids。提出了一种称为CLARANS（Clustering Large Applications depends upon RANdomized Search）的k-medoids类型算法。它可以将采样方法与PAM连接起来。虽然CLARA在搜索的每个阶段都有一个固定的样本，但CLARANS在搜索的每个阶段都会以一定的随机性抽取样本。

聚类过程可以看作是对图的搜索，其中每个节点都是一个可能的解（一组k个medoids）。如果它们的集合只相差一个对象，则两个节点是相邻的（特别是，由图中的弧连接）。每个节点都可以分配一个成本，该成本由每个对象与其簇的medoid之间的总差异表示。

在每一步中，PAM确定其在搜索最小成本解时最新节点的所有邻居。然后，最新节点将被具有最大成本下降的邻居替换。因为CLARA操作的是整个数据集的样本，所以它确定的邻居较少，并将搜索限制在比初始图更小的子图。

实验表明，CLARANS比PAM和CLARA都更有效率。它可以使用轮廓系数（定义对象真正应用于聚类的程度的对象属性）来发现最“自然”的聚类数量。CLARANS还允许发现异常值。

CLARANS的计算复杂度为O(n2)，其中n是对象的个数。此外，其聚类质量基于所使用的采样方法。通过关注探索空间数据结构（包括R*-树）的方法，可以进一步提高CLARANS处理驻留在磁盘上的数据对象的能力。

更新于：2021年11月24日

447 次浏览

启动您的职业生涯

通过完成课程获得认证

开始
广告