PAM（Partitioning Around Medoid,圍繞中心點的劃分）是聚類分析算法中劃分法的一個聚類方法，是最早提出的k-中心點算法之一。
基本介紹
- 中文名：PAM
- 外文名：Partitioning Around Medoid
- 全稱：圍繞中心點的劃分
- 套用：商業、製造業、金融業、醫藥業
算法簡介,算法思想,算法描述,算法性能,
算法簡介
如今數據挖掘的理論越來越廣泛的套用在商業、製造業、金融業、醫藥業、電信業等等許多領域。數據挖掘的目標之一是進行聚類分析。聚類就是把一組個體按照相似性歸成若干類別，它的目的是使得屬於同一類別的個體之間的差別儘可能的小，而不同種類別上的個體間的差別儘可能的大。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都很大的時候。
