4.3　PAM算法的研究

4.3.1　PAM算法概述

PAM(Partitioning Around Medoid,围绕中心点的划分)是聚类分析算法中划分法的一种，是最早提出的K-中心点算法之一。

如今数据挖掘的理论被越来越广泛地应用在商业、制造业、金融业、医药业、电信业等领域。数据挖掘的目标之一是进行聚类分析。聚类就是把一组个体按照相似性归成若干类别，它的目的是使属于同一类别的个体之间的差别尽可能小，而不同类别上的个体间的差别尽可能大。PAM算法是众多聚类算法之一。PAM算法的优势在于：PAM算法比K-均值算法更健壮，对“噪声”和孤立点数据不敏感；它能够处理不同类型的数据点；它对小的数据集非常有效。

4.3.2　PAM算法的主要流程

输入：簇的数目k和包含n个对象的数据库。

输出：k个簇，使所有对象与其最近中心点的相异度总和最小。

(1)任意选择k个对象作为初始的簇中心点；

(2)重复；

(3)指派每个剩余对象给离它最近的中心点所表示的簇；

(4)重复；

(5)选择一个未被选择的中心点Oi；

(6)重复；

(7)选择一个未被选择的非中心点对象Oh；

(8)计算用Oh代替Oi的总代价并记录在S中；

(9)直到所有非中心点都被选择过；

(10)直到所有中心点都被选择过；

(11)如果在S中的所有非中心点代替所有中心点后计算出的总代价小于0，则找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；

(12)直到没有簇的重新分配为止，即所有的S都大于0。

PAM算法需用簇中位置最靠近中心的对象作为代表对象，然后反复地用非代表对象来代替代表对象，试图找出更好的中心点，在反复迭代的过程中，所有可能的“对象对”被分析，每个对象对中的一个对象是中心点，另一个对象是非代表对象。一个对象代表可以被最大平方-误差的值减少的对象代替。

一个非代表对象Oh是否是当前一个代表对象Oi的一个好的替代，对于每个非中心点对象Oj，有以下4种情况需要考虑。

(1)Oj当前隶属于Oi，如果Oi被Oh替换，且Oj离另一个中心点Om最近，i≠m，那么Oj被分配给Om，则替换代价为Cjih=d(j,m)-d(j,i)，如图4-3所示。

(2)Oj当前隶属于Oi，如果Oi被Oh替换，且Oj离Oh最近，那么Oj被分配给Oh，则替换代价为Cjih=d(j,h)-d(j,i)，如图4-4所示。

(3)Oj当前隶属于Om，m≠i，如果Oi被Oh替换，且Oj仍然离Om最近，那么Oj被分配给Om，则替换代价为Cjih=0，如图4-5所示。

(4) Oj当前隶属于Om，m≠i，如果Oi被Oh替换，且Oj离Oh最近，那么Oj被分配给Oh，则替换代价为Cjih=d(j,h)-d(j,m)，如图4-6所示。

每当重新分配发生时，平方-误差的值所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点对象代替，那么代价函数计算平方-误差的值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。如果总代价是负的，那么实际的平方-误差的值将会减小，Oi可以被Oh替代。如果总代价是正的，则当前的中心点Oi被认为是可接受的，在本次迭代中没有变化。

4.3.3　PAM算法的MATLAB实现

PAM算法的仿真结果如图4-7所示。