基于有代表性的点的技术：K中心聚类法

• 算法步骤
  1. 随机选择k个点作为“中心点”
  2. 计算剩余的点到这个k中心点的距离，每个点被分配到最近的中心点组成聚簇
  3. 随机选择一个非中心点，用它代替某个现有的中心点，计算这个代换的总代价S
  4. 如果S<0，则用代替，形成新的k个中心点集合
  5. 重复2，直至中心点集合不发生变化

K中心法的实现：PAM

• PAM使用离差平方和来计算成本S（类似于ward距离的计算）
• R语言的cluster包实现了PAM
• K中心法的优点：对于“噪音较大和存在离群值的情况，K中心法更加健壮，不像Kmeans那样容易受到极端数据影响
• K中心法的缺点：执行代价更高

cluster包的pam()函数

> library(cluster)
> x=iris[,1:4]
> kc=pam(x,3)
> kc
Medoids:
      ID Sepal.Length Sepal.Width Petal.Length Petal.Width
[1,]   8          5.0         3.4          1.5         0.2
[2,]  79          6.0         2.9          4.5         1.5
[3,] 113          6.8         3.0          5.5         2.1
Clustering vector:
  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 [38] 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 [75] 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 2 3 3 3 3
[112] 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3 3 3 2 3
[149] 3 2
Objective function:
    build      swap 
0.6709391 0.6542077 

Available components:
 [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 
 [6] "clusinfo"   "silinfo"    "diss"       "call"       "data"