像 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(n 2 )，其中 n 是对象的数量。此外，其聚类质量基于所使用的采样方法。此外，通过专注于探索空间数据结构（包括 R* 树）的方法，可以提高 CLARANS 管理驻留在磁盘上的数据对象的能力。