第三节快速聚类法

第五章第三节一、快速聚类法的步骤二、用Lm距离进行快速聚类快速聚类法7/28/2023在谱系聚类法中，因为样品一旦被归到某个类后就不变了，所以要求分类方法比较准确。而样品容量较大时，谱系聚类法的计算量过大。因此，为了弥补谱系聚类法的不足，产生了快速聚类法，又称动态聚类法。快速聚类法先将样品粗糙地分一下类，然后再按照某种原则进行修正，直至分类比较合理为止。7/28/2023快速聚类法选择聚点最终分类合理初始分类分类是否合理修改分类不合理7/28/2023一、快速聚类法的步骤1选择聚点聚点（种子）是一批有代表性的样品，它的选择决定了初始分类，对最终分类有较大影响。在进行快速聚类法前，要根据研究问题的要求及了解程度先定下分类数k，这样就可以在每一类中选择一个有代表性的样品作为聚点（初始聚点）。7/28/2023选择聚点有下列方法：

(1)经验选择。如果对研究对象比较了解，根据以往的经验定下k个样品作为聚点。

(2)将n个样品人为地（或随机地）分成k类，以每类的重心作为聚点。

(3)最小最大原则。设要将n个样品分成k类，先选择所有样品中距离最远的两个样品为前两个聚点,即选择和使7/28/2023然后选择第3个聚点使其与前两个聚点的距离最小者等于所有其余的与的较小距离中最大的,用公式表示为然后按相同的原则选取依次下去，直至选定k个点若已选了l个聚点(l<k),则第l+1个聚点选取的原则为7/28/2023注：在SAS系统procfastclus过程中，分类数k是事先给定的。在给定k以后，procfastclus过程会按上述方法算出初始聚点的。2快速聚类法的计算步骤先假设聚类中采用的距离是欧式距离，即1）设k个初始聚点的集合是用下列原则实现初始分类。记7/28/2023则是每个样品以最靠近的初始聚点归类。这样，将样品分成不相交的k类。以上初始分类的原依照以上计算，得到一个初始分类2）从出发，计算新的聚点集合以的重重心作为新的聚点：7/28/2023其中是类中的样品数.这样得到新的聚点集合：从出发，将样品作新的分类。记得到分类这样，依次重复计算下去。7/28/20233）设在第m步得到分类在以上递推计算过程中，是类的重心.不一定是样品，又一般不是的重心.当m逐渐增大时，分类的重心，从而趋于稳定.此时，就会近似认为算法即可结束。实际计算时，从某一步m开始，分类与完全相同，计算即告结束。7/28/2023记理论上可以证明:当m增加时为单调减下有界序将逐步稳定，即上述快速聚类法具有收敛性.故存在，即会逐步趋于稳定。因此，分类结果也设给定若则递推计算过程结束。7/28/2023例1.1976年74个国家和地区的人口出生率x1和死亡率x2的数据见表6.25（国家与地区名从略）.表中列出的数据是每10万人的出生数与死亡数.试对这74个国家与地区按人口出生率与死亡率进行快速聚类分析。7/28/2023data

shengsi;inputx1x2;cards;……;proc

fastclusdata=shengsiout=a1maxc=3cluster=cdistancelist;proc

plot;plotx2*x1=c;run;假定分3类7/28/20237/28/20237/28/20237/28/20237/28/2023data

shengsi;inputx1x2;cards;……;proc

fastclusdata=shengsiout=a1maxc=4cluster=cdistancelist;proc

plot;plotx2*x1=c;run;分为4类7/28/20237/28/20237/28/20237/28/20237/28/2023二、用Lm距离进行快速聚类上面我们介绍的聚类方法都是用欧氏距离。下面我们介绍用Lm距离进行快速聚类的方法。则Lm距离为设当m=2时，即是欧氏距离，当m=1时，为绝对距离：7/28/2023我们先讨论L1的情况。对于一元数据要求一个数c，使得可知，使上式达到小的c是的中位数7/28/2023对于p元样品的第k个分量的数据集是设它的中位数是则称其为的中位向量，其中满足7/28/2023从而7/28/2023讨论Lm最优化准则。对于一元数据要求有一个数c，使得的m中心.对于p元样品称c为其中的第k个分量的数据集是设它的m中心是则7/28/2023的m中心向量，其中称为满足从而显然，2中心向量即均值向量，1中心向量即中位向量.7/28/2023在采用Lm距离进行快速聚类分析时，最终聚点应是每一类的m中心向量。在采用L1距离进行聚类分析时,最终聚点应是每一类的中位向量.用L1距离进行聚类分析时，有较强的稳健性，当有异常数据时，分类结果经常会更好些.采用不同的Lm距离，聚类分析的结果经常会是不同的.7/28/2023例2.利用绝对距离对例6.8的数据进行快速聚类。（1）分为3类；（2）分为4类。7/28/20237/28/20237/28/20237/28/20237/28/20237/28/20237/28/20237/28/2023例3.利用L