算法简介

如今数据挖掘的理论越来越广泛的应用在商业、制造业、金融业、医药业、电信业等等许多领域。数据挖掘的目标之一是进行聚类分析。聚类就是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽可能的小，而不同种类别上的个体间的差别尽可能的大。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.