k-medoids 算法在大型数据集上的效率如何?
像 PAM 这样的经典 k-medoids 划分算法对于小型数据集非常有效，但对于大型数据集的扩展性不佳。它可以处理更大的数据集，可以使用一种基于采样的方法，称为 CLARA(大型应用聚类)。
CLARA 背后的方法如下:如果样本的选择方式相当随机，则它必须紧密定义原始数据集。所选的代表性对象(medoids)将与从整个数据集中选择的对象相似。CLARA 从数据集中抽取多个样本，对每个样本应用 PAM，并返回其最佳聚类结果作为输出。
CLARA 的性能取决于样本量。据观察，PAM 在给定数据集之间搜索最佳的 k 个medoids，而 CLARA 在数据集的选定样本之间搜索最佳的 k 个medoids。一种名为 CLARANS(大型应用聚类依赖于随机搜索)的 k-medoids 类型算法被提出。它可以将采样方法与 PAM 连接起来。CLARA 在搜索的每个阶段都有固定的样本，而 CLARANS 则在搜索的每个阶段都随机地抽取样本。
聚类过程可以看作是对图的搜索，其中每个节点都是一个可能的解(一组 k 个 medoid)。如果两个节点的集合仅相差一个对象，则它们相邻(特别是图中由弧连接)。每个节点可以分配一个成本，该成本由每个对象与其聚类 medoid 之间的总差异度表示。
在每一步中，PAM 都会确定最新节点的所有邻居，以寻求最小成本解。然后，最新节点将被成本下降幅度最大的邻居替换。由于 CLARA 对整个数据集的样本进行操作，因此它确定的邻居更少，并将搜索限制在小于初始图的子图中。
实验表明，CLARANS 比 PAM 和 CLARA 更高效。它可以使用轮廓系数(silhouette coefficient)来发现最"自然"的聚类数量。轮廓系数是对象的一个属性，用于定义该对象在聚类中实际占比的程度。CLARANS 还可以发现异常值。
CLARANS 的计算复杂度为 O(n2)，其中 n 是对象的数量。此外，其聚类质量取决于所使用的采样方法。此外，通过专注于探索空间数据结构(包括 R* 树)的方法，可以提高 CLARANS 管理磁盘上数据对象的能力。
