- 基于MATLAB的人工智能模式识别
- 周润景 武立群 蔺雨露编著
- 1180字
- 2021-06-10 14:48:42
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所示。
图4-3 第一种情况
图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所示。
图4-5 第三种情况
图4-6 第四种情况
每当重新分配发生时,平方-误差的值所产生的差别对代价函数有影响。因此,如果一个当前的中心点对象被非中心点对象代替,那么代价函数计算平方-误差的值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。如果总代价是负的,那么实际的平方-误差的值将会减小,Oi可以被Oh替代。如果总代价是正的,则当前的中心点Oi被认为是可接受的,在本次迭代中没有变化。
4.3.3 PAM算法的MATLAB实现
PAM算法的仿真结果如图4-7所示。
图4-7 PAM算法的仿真结果