> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/ji-qi-xue-xi/ju-lei-suan-fa/based-on-partition/kmedoids-suan-fa.md).

# K-Medoids算法

## 引入

K-Means算法高效, 使用广泛, 但对样本中的异常值十分敏感, 异常点的存在会使聚类的结果发生严重的偏离.

**K-Medoids**算法则消除了这种不足之处. 利用**代表对象**(即用样本中的一个点, 代表多个点)这种形式. 在消除噪声和异常值显著的背后, 是**很高的算法复杂度**, 计算效率很低, 只能再中小数据集中使用.

## 算法原理

在K-means算法的迭代中, 每次计算新的中心点时, 使用该簇的所有点计算平均值, 以这个平均值作为新的中心. **K-Medoids**算法不选用平均值, 而是采用**簇中位置最中心的对象**, 即**中心点**(medoids)作为参照点.

K-Medoids的重点, 在于中心点的选取. 选取簇中心点的原则为: **当前簇中所有其他点到该中心点的距离之和最小, 需要遍历簇中所有点.** 其他的步骤与K-Means算法中的相同.

K-Medoids的使用**绝对差值和**(Sum of Absolute Differences, SAD)来的度量来衡量聚类结果的优劣, SAD的公式如下:

$$\text{SAD}=\sum\limits\_{m=1}^{k}\sum\limits\_{p\_i\in{C\_m}}\sqrt{\sum\limits\_{j=1}^{|C\_m|}(p\_{ij}-o\_{ij})^2}$$

## PAM

PAM, Partitioning Around Medoids. PAM算法是K-Medoids算法的衍生算法. 基本流程如下:

* 首先随机选择k个对象作为中心, 把每个对象分配给离它最近的中心
* 然后**随机地**选择一个非中心对象替换中心对象, 每次交换一个中心点和非中心点, 然后执行将非中心点指派到最近的中心点, 计算得到的SAD值越小, 则聚类质量越好
* 如果总的损失减少, 则交换中心对象和非中心对象; 如果总的损失增加, 则不进行交换
* 聚类的过程就是不断迭代, 进行中心对象和非中心对象的反复替换过程, 直到目标函数不再有改进为止

在交换中心点和非中心点时, 应当遍历当前所有的中心点和非中心点, 选取最优的交换组合, 但这样的效率很低, 使用随机的方法代替遍历.

这种算法通常适用于聚类比较小的点的集合, 因为如果能够迭代所有情况, 那么最终得到的划分一定是最优的划分, 得到最好的聚类效果. 但是如果待聚类的点的集合比较大, 则需要通过限制迭代次数来终止迭代计算, 从而得到一个能够满足实际精度需要的聚类结果.

## CLARA

CLARA, Clustering LARge Applications, 也是K-Medoids的一种衍生算法. 由于PAM在面对大样本时很慢, CLARA从数据集中抽取多个样本集, 对每个样本集使用PAM, 并以最好的聚类作为输出. 具体步骤如下:

* 设定从数据集中抽取子样本集的次数, 进行循环
  * 从整体数据集中抽取$$N$$个对象的样本子集, 调用PAM算法, 得到K个中心点
  * 将整个数据集中的所有样本点根据最近距离匹配到这K个样本点上
  * 计算SAD值, 如果当前的K个中心点对应的聚类结果计算得到的SAD值小于之前的模型, 则用现在的这K个中心点对应的模型作为最优模型
* 得到最优的聚类模型

## 参考资料

* [数据挖掘入门笔记——K-Medoids](https://zhuanlan.zhihu.com/p/55163617)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/ji-qi-xue-xi/ju-lei-suan-fa/based-on-partition/kmedoids-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.