type
status
password
date
slug
summary
category
URL
tags
icon
K-Medoids 算法
基本原理
k-means算法对于异常值十分敏感，因为具有极大值的对象可能会产生严重扭曲的数据分布。因此我们根据K-means算法提出K-Medoids算法，K-Medoids算法不选用平均值，转而采用 簇中位置最中心的对象，即中心点（medoids） 作为参照点，算法步骤和 K-means 类似。
k-mediods每次选取的质心，必须是样本点，于是K-Medoids的重点，就在于中心点的选取。
选取簇中心点的准则函数是 :当前簇中所有其他点到该中心点的距离之和最小
K-Medoids 算法步骤
- 任意选取 k 个点作为 medoids
- 按照与medoids最近的原则，将剩余点分配到当前最佳的medoids代表的类中
- 在每一类中，计算每个成员点对应的准则函数，选取准则函数最小时对应的点作为新的 medoids
其中准则函数为，一类中，某个成员点和其他成员点的距离之和
- 重复2-3的过程，直到所有的 medoids 点不再发生变化，或已达到设定的最大迭代次数
优缺点
- 优点：当存在噪音和孤立点时, K-medoids 比 K-means 更健壮。
- 缺点：计算复杂度高，计算质心的步骤时间复杂度是，运行速度较慢
衍生算法
PAM，Partitioning Around Medoids
算法流程：
- 首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心。
- 然后，随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量
- 如果总的损失减少，则交换中心对象和非中心对象；
- 如果总的损失增加，则不进行交换
聚类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函数不再有改进为止。
通常，如果能够迭代所有情况，那么最终得到的划分一定是最优的划分，即聚类结果最好，这通常适用于聚类比较小的点的集合。但是如果待聚类的点的集合比较大，则需要通过限制迭代次数来终止迭代计算，从而得到一个能够满足实际精度需要的聚类结果。
CLARA，Clustering LARge Applications
简单来说，当面对一个大样本量时，CLARA每次随机选取样本量中的一小部分进行PAM聚类，然后将剩余样本按照最小中心距离进行归类。在各次重复抽样聚类的结果中，选取误差最小，即中心点代换代价最小的结果作为最终结果。