PAM

如今數據挖掘的理論越來越廣泛的應用在商業、製造業、金融業、醫藥業、電信業等等許多領域。數據挖掘的目標之一是進行聚類分析。聚類就是把一組個體按照相似性歸成若干類別，它的目的是使得屬於同一類別的個體之間的差別儘可能的小，而不同種類別上的個體間的差別儘可能的大。PAM聚類演演算法是眾多聚類演演算法的之一。PAM演演算法的優勢在於：PAM演演算法比K-平均演演算法更健壯，對“雜訊”和孤立點數據不敏感；它能夠處理不同類型的數據點；它對小的數據集非常有效。

PAM聚類演演算法的基本思想為：

選用簇中位置最中心的對象，試圖對n個對象給出k個劃分；代表對象也被稱為是中心點，其他對象則被稱為非代表對象；最初隨機選擇k個對象作為中心點，該演演算法反覆地用非代表對象來代替代表對象，試圖找出更好的中心點，以改進聚類的質量；在每次迭代中，所有可能的對象對被分析，每個對中的一個對象是中心點，而另一個是非代表對象。對可能的各種組合，估算聚類結果的質量；一個對象Oi可以被使最大平方-誤差值減少的對象代替；在一次迭代中產生的最佳對象集合成為下次迭代的中心點。

輸入：簇的數目k和包含n個對象的資料庫

輸出：k個簇，使得所有對象與其距離最近中心點的相異度總和最小

（1）任意選擇k個對象作為初始的簇中心點（2） Repeat

（3）指派每個剩餘對象給離他最近的中心點所表示的簇

（4） Repeat

（5）選擇一個未被選擇的中心點Oi

（6） Repeat

（7）選擇一個未被選擇過的非中心點對象Oh

（8）計算用Oh代替Oi的總代價並記錄在S中

（9） Until 所有非中心點都被選擇過

（10） Until 所有的中心點都被選擇過

（11） If 在S中的所有非中心點代替所有中心點后的計算出總代價有小於0的存在，then找出S中的用非中心點替代中心點後代價最小的一個，並用該非中心點替代對應的中心點，形成一個新的k個中心點的集合；

（12） Until 沒有再發生簇的重新分配，即所有的S都大於0.

(1) 消除了k-平均演演算法對於孤立點的敏感性。

(2) K-中心點方法比k-平均演演算法的代價要高

(3) 必須指定k

(4) PAM對小的數據集非常有效，對大數據集效率不高。特別是n和k都很大的時候。