谱系聚类法

6.2系统聚类法系统聚类法又称为谱系聚类法,是聚类分析诸方法中用得最多的一种。基本思想是：开始将个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。().Q一、样品间的聚类型聚类(HierarchicalClusteringMethod)1、最短距离法(Nearestneighbor)pqijpqDMindxGxGij：，ppqqGnGn类(含个样本）与类(含个样本)的距离定义为：,.ijijdxx其中，表示样品之间的距离定义类与类之间的距离为两类最近样品间的距离，即xq1•xp2•xq2•xp1•pqdxq3•piqjGxGxijqppqdnnD2213、类平均距离(Between-groupslinkage)2、最长距离(Furthestneighbor)pqijpqDMaxdxGxGij：，xq1•xp3•xq2•xp1•pqdxq3•xp2•••••••92921dd(1)规定样品之间的距离，计算n个样品的距离矩阵(0)D，它是一个对称矩阵。(2)选择(0)D中的最小元素，设为pqD，•(3)计算新类rG与任一类kG之间距离的递推公式,,,minminmin,minmin,*rkpkqkrkijijijiGjGiGjGiGjGkpkqDdddDD最短距离法的聚类步骤,ppqqGxGx则将pG和qG合并成一个新类，记为rG，即rpqGGG.在(0)D中，pG和qG所在的行和列合并成一个新行新列，对应rG，该行、列上的新距离值由（*）式求得，其余行列上的距离值不变，这样就得到新的距离矩阵，记作(1)D.(4)对(1)D重复上述对(0)D的两步得(2)D，如此下去直至所有元素合并成一类为止。如果某一步()kD中最小的元素不止一个，则称此现象为结(tie)，对应这些最小元素的类可以任选一对合并或同时合并。例设抽取五个样品，每个样品只有一个变量，它们是1，2，3.5，7，9。用最短距离法对5个样品进行分类。)0(D1G2G3G4G5G1G2G3G4G5G0102.51.50653.50875.520△然后和被聚为新类，得：1G2G6G)1(D首先采用绝对距离计算距离矩阵：6G3G5G3G4G01.5053.5075.5206G4G5GqpijpqGGdMinDjixx，：定义距离：qplDDMinDqlplrl，，递推公式：△2、最长距离法(Furthestneighbor)pqijpqDMaxdxGxGij：，xq1•xp3•xq2•xp1•pqdxq3•xp2••最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。max,rkpkqkDDD最长距离法容易被异常值严重地扭曲，一个有效的方法是将这些异常值单独拿出来后再进行聚类。rpqGGG递推公式：)0(D1G2G3G4G5G1G2G3G4G5G0102.51.50653.50875.520首先采用绝对距离计算距离矩阵：△例设抽取五个样品，每个样品只有一个变量，它们是1，2，3.5，7，9。用最长距离法对5个样品进行分类。}{qpijpqGGdMaxDjiXX，：定义距离：max,rkpkqkDDD递推公式：rpqGGG然后被聚为新类，得：02.5063.5085.5203G5G6G4G5G6G3G4G1D（）3、类平均距离(Between-groupslinkage)221pqpqijiGpqjGDdnn,rpqGGG若新类rG与任一类kG之间距离平方递推公式为222pqrkpkqkpqpqnnDDDnnnn两类中各个元素两两之间的距离平方相加后取平均值..2G3G4G0106.252.250362512.250644930.25401G2G3G5G1G4G5GpiqjGxGxijqppqdnnD221首先采用绝对距离的平方得到距离矩阵：△然后被聚为新类，得：)1(D6G3G4G5G3G4G04.25030.2512.25056.2530.25406G5GqpkqqkpprknnDnDnD222递推公式：4、重心距离法(Centroidclustering)(,)xxpqpqDd,.xxpqpqGG是，的重心,rpqGGG若新类rG与任一类kG之间距离的递推公式为2222qkpqpqpqrkpkpqpqpqpqnnnnDDDDnnnnnnnn均值间的距离5、离差平方和距离(Ward'smethod)2()().xxxxpqpqTpqpqpqnnDnn,rpqGGG若新类rG与任一类kG之间距离的递推公式为2222qkpqpkqkkrkpkpqkpqkpqknnnnnDDDDnnnnnnnnn其他方法中间距离法2222412121pqkqkpkrDDDD递推公式：可变类平均法2222)1(pqqpqkqpkprkDnnDnDnDkpdkrdpqdkqdpGqGrG称为可变法22221()12krkpkqpqDDDD，中间距离法的更一般形式系统聚类法距离公式的统一表达式若样品间距离采用欧氏距离平方21(,)()piiidxyxy||222222kqkppqkqqkppkrdddddd1、最短距离法当β、γ四个参数取不同的值时，就形成了不同的聚类方法.pq、0pq111=、=，，2222、最长距离法0pq111=、=，，2223、类平均距离：0pqpqpqpqnnnnnn=、=，，0系统聚类分析实例对中国大陆31个省级区域第三产业综合发展水平进行类型划分及差异性程度分析---聚类指标选择(选取如下7项指标)①y1——人均GDP，它反映了经济社会发展的总体状况和一般水平；②y2——人均第三产业增加值，它反映了人均服务产品占有量或服务密度；③y3——第二产业增加值比重，它反映了工业化水平和产业结构现代化程度；④y4——第三产业增加值比重，它反映了第三产业的发展程度及其对国民经济的贡献；⑤y5——第三产业从业人员比重，它反映了第三产业对劳动力的吸纳能力；⑥y6——第三产业固定资产投资比重，它反映了第三产业的资金投入程度；⑦y7——城市化水平，它反映了农村人口转化为城市人口的程度及对服务的需求量。聚类计算(计算过程)①用标准差标准化方法对7项指标的原始数据进行处理。②采用欧氏距离测度31个省（市、区）之间的样本间距离。③选用类平均法计算类间的距离，并对样本进行归类。经过上述聚类计算步骤，得到的聚类结果见下图.样本Num+---------+---------+---------+---------+---------+安徽12河南16甘肃28四川23贵州24河北3山东15山西4湖北17重庆22陕西27宁夏30江西14湖南18广西20云南25江苏10浙江11广东19福建13辽宁6黑龙江8吉林7新疆31内蒙古5青海29海南21西藏26北京1上海9天津2图3.4.5中国31个省级区域第三产业发展水平组平均聚类谱系图聚类结果分析当类间距离取为4.0和2.5时，全国各省份被合并成以下几类：①上海、北京、天津3直辖市为一类，而上海和北京更接近；②西藏、海南为一特殊类；青海、内蒙古、新疆、吉林为一类，其中内蒙古、新疆、吉林合并为一亚类；③江苏、浙江、广东、福建、辽宁、黑龙江为一类，其中江苏、浙江、广东合并为一亚类；④重庆、陕西、宁夏、江西、湖南、广西为一类，其中重庆、陕西、宁夏和江西、湖南、广西各自为一亚类，云南为一孤立点；⑤河北、山东、山西、湖北为一类；⑥安徽、河南、甘肃、四川、贵州为一类。R型聚类,.CQ由相似矩阵出发聚类步骤与型聚类相同如最短距离法、最长距离法、重心法等聚类方法同例某公司下属30个企业，公司为了考核下属企业的经济效益，设计了8个指标。为了避免重复，需要对这8个指标进行筛选，建立一个恰当的经济效益指标体系。通过计算30个企业8个指标的相关系数距离，数据是1-r2。得如下表:试将它们聚类。x1x2x3x4x5x6x7x8x100.6000.430.4600.470.450.1200.570.450.230.2200.380.400.210.290.2200.310.790.650.700.800.6600.450.450.270.230.140.190.770x2x3x4x5x6x7x8结果如下例每个样品只测了两个指标,它们是{1.0,1.5}、{0.8,1.0}、{1.2,1.6}、{2.0,0}、{3.0,4.0}、{1.1,0.2},试用最短距离法对六个样品进行聚类（定义样品间的距离采用绝对距离）,写出聚类过程,写出聚为两类的聚类结果.x-c(1,0.8,1.2,2,3,1.1,1.5,1,1.6,0,4,0.2)dim(x)-c(6,2)#用向量构造6行2列的矩阵d0-dist(x,method=“minkowski”,diag=TRUE,upper=FALSE,p=1)#method是两个样品的距离,参数有“euclidean”,“maximum”,“manhattan”,“canberra”,“minkowski”等计算初始距离距阵(0)Dhcs-hclust(d0,method=“single”)hclust(d,method=“complete”,members=NULL)R中聚类函数,格式为：method是系统聚类的方法,其参数有“single”(最短距离法),“complete”(最长距离法),“median”(中间距离法),centroid”(重心法),“average”(类平均法),“ward”(离差平方和法),“mcquitty”(相似法).plot(hcs,hang=-1)#画树形图,hang=-1使样品标号水平对齐,位于同一行.二、数据的变换处理npnnppxxxxxxxxx212222111211X设原始观测数据矩阵为：中心化变换是一种坐标轴平移处理方法，它是先求出每个变量的样本平均值，再从原始数据中减去该变量的均值.jijijxxx*),,3,2,1;,,3,2,1(pjni1、中心化变换结果使每个变量均值为0，每列数据的平方和是该列变量样本方差的(n—1)倍，任何不同两列数据之交叉乘积是这两列变量样本协方差的(n—1)倍，中心化变换可方便地计算方差与协方差。2、极差规格化变换从数据矩阵的每一个变量中找出其最大值和最小值,这两者之差称为极差，然后从每个变量的每个原始数据中减去该变量中的最小值，再除以极差，即有：jniijijijRxxx,,2,1*)min(),,3,2,1;,,3,2,1(pjniniijijnijxxR,,2,1,,2,1)min()(max10*ijx变换后，数据矩阵中每个变量的最大数值为1，最小数值为0，其余数据取值均在0－1之间；并且变换后的数据都不再具有量纲，便于不同的变量之间的比较。3、标准化变换标准化变换也是对变量的数值和量纲进行类似于规格化变换的一种数据处理方法。首先对每个变量进行中心化变换，然后用该变量的标准差进行标准化。即有：jjijijSxxx*),,3,2,1;,,3,2,1(pjninijijjxxnS12)(11变换后，每个变量的平均值为0，方差为1，且也具有量纲，同样也便于不同变量之间的比较；数据阵中任何两列数据乘积之和是两个变量相关系数的（n－1）倍，方便计算相关矩阵。4．对数变换对数变换是将各个原始数据取对数，将原始数据的对数值作为变换后的新值。即：)log(*ijijxx三、确定