CLARANS是分割方法中基于随机搜索的大型应用聚类算法。在分割方法中最早提出的一些算法大多对小数据集合非常有效，但对大的数据集合没有良好的可伸缩性。

如PAM。CLARA能处理比PAM大的数据集合，其有效性取决于样本的大小，但当某个采样得到的中心点不属于最佳的中心点时．CLARA不能得到最佳聚类结果。CLARA NS是在CLA RA 算法的基础上提出来的．与CLA RA 不同．CLARA NS没有在任一给定的时间局限于任一样本．而是在搜索的每一步都带一定随机性的选取一个样本。CLARA NS的时间复杂度大约是O(n2)．n是对象的数目。此方法的优点是一方面改进了CLA RA 的聚类质量．另一方面拓展了数据处理量的伸缩范围，具有较好的聚类效果。但它的计算效率较低，且对数据输入顺序敏感，只能聚类凸状或球型边界。

CLARANS的步骤：

第 1 步输入参数numlocal 和maxneighbor。

第 2 步从 n 个目标中随机地选取k 个目标构成质心集合，并令它们作为current。

第 3 步令 j 等于1。

第 4 步从第 2 步中剩下的n–k 个目标集中随机选取一个目标，并用之替换质心集合中随机的某一个质心可得到一个新的质心集合，计算两个质心集合的代价差（这一点和PAM相似，只是变成了随机选取替换对象和被替换对象）。

第 5 步如果新的质心集合代价较小则将其赋给current，重置j=1，否则j+=1

第 6 步直到j大于等于maxneighbor，则current为此时的最小代价质心集合

第 7 步重复以上步骤numlocal次，取其中代价最小的质心集合为最终质心集合

第 8 步按照最终质心集合进行划分并输出

(以上步骤参考论文：“不确定性目标的 CLARANS 聚类算法”，计算机工程，2012年11期38卷)