CLARANS算法

轉載http://www.idataskys.com/%E8%81%9A%E7%B1%BB%E5%88%86%E6%9E%90%E4%B9%8Bclarans%E7%AE%97%E6%B3%95/

CLARANS (A Clustering Algorithm based on Randomized Search，基于随機選擇的聚類算法) 将采樣技術（CLARA）和PAM結合起來。CLARA的主要思想是：不考慮整個資料集合，而是選擇實際資料的一小部分作為資料的代表。然後用PAM方法從樣本中選擇中心點。如果樣本是以非常随機的方式選取的，那麼它應當接近代表原來的資料集。從中選出代表對象（中心點）很可能和從整個資料集合中選出的代表對象相似。CLARA抽取資料集合的多個樣本，對每個樣本應用PAM算法，并傳回最好的聚類結果作為輸出。 

        CLARA的有效性主要取決于樣本的大小。如果任何一個最佳抽樣中心點不在最佳的K個中心之中，則CLARA将永遠不能找到資料集合的最佳聚類。同時這也是為了聚類效率做付出的代價。 

        CLARANS聚類則是将CLARA和PAM有效的結合起來，CLARANS在任何時候都不把自身局限于任何樣本，CLARANS在搜素的每一步都以某種随機性選取樣本。算法步驟如下（算法步驟摘自百度文庫）： 

1、輸入參數numlocal和maxneighbor。numlocal 表示抽樣的次數， maxneighbor 表示一個節點可以與任意特定鄰居進行比較的數目 令：i=1，i用來表示已經選樣的次數 mincost為最小代價，初始時設為大數。 

2、設定目前節點current為Gn中的任意一個節點。 

3、令j =1。（j用來表示已經與current進行比較的鄰居的個數） 

4、考慮目前點的一個随機的鄰居S，并計算兩個節點的代價差。

5、如果S的代價較低，則current:=S，轉到步驟3。 

6、否則，令j=j+1。如果j<=maxneighbor,則轉到步驟4。 

7、否則 ，當j>maxneighbor，目前節點為本次選樣最小代價節點. 如果其代價小于mincost,令mincost為目前節點的代價，bestnode為目前的節點。 

8、令 i= i+1，如果i〉numlocal,輸出bestnode，運算中止.否則，轉到步驟2。 對上面出現一些概念進行說明： 

    （1）代價值，主要描述一個對象被分到一個類别中的代價值，該代價值由每個對象與其簇中心點間的相異度（距離或者相似度）的總和來定義。代價差則是兩次随機領域的代價內插補點。 

    （2）更新鄰接點，CLARANS不會把搜尋限制在局部區域，如果發現一個更好的近鄰，CLARANS就移到該近鄰節點，處理過程從新開始；否則，目前的聚類則産生了一個局部最小。如果找到一個局部最小，CLARANS從随機選擇的新節點開始，搜尋新的局部最小。當搜尋的局部最小解達到使用者指定的數目時，最好的局部最小作為算法的輸出。從上面的算法步驟也可以看出這一思想。在第5步中更新節點current。