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