如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卷)
