K-中點

K-中點係一系列同 K-平均聚類法相似嘅聚類分析演算法。

中點周邊分區

中點周邊分區（Partitioning Around Medoids，PAM）係種同 K-平均聚類法好似嘅做法，最基本如下：

1. BUILD：首先，段演算法揀一點做中點（medoid），揀嘅原則係揀成本（cost；可以用同其他所有點之間嘅總距離）最低嗰點；
2. 重複：揀成本最低嗰點出嚟做中點，直至揀咗 $k$ 點出嚟為止；
3. 將每點唔屬中點嘅點，掕落離佢最近嗰粒中點度；
4. SWAP：如果能夠令成本下降，一路做
   • Foreach 中點 $m$，foreach 喺佢個聚類內嘅非中點 $o$：
     • 考慮將 $m$ 同 $o$ 掉換，計吓兩者掉換咗嘅話成本會點變；
     • 如果場掉換係目前最好（最能夠令成本跌）嘅，記住呢場掉換；
   • 如果做出最好嗰場 $m$ $o$ 掉換會令成本跌，就郁手做；否則段演算法就算行完（converged）。

PAM 唔少人用（下圖係 $k=3$ 嘅 gif 圖解），而且好多做統計相關工作嘅人都鍾意「PAM 冇乜隨機性」呢一樣嘢，不過 PAM 又畀人詬病話佢計得慢－PAM 要係噉計「呢點呢點同其他所有點之間嘅距離嘅總和」。

PAM 嘅 gif 圖解，$k=3$

睇埋

• 聚類分析
• K-平均聚類法