快速聚类法

基本思想是，样本容量较大时，选择一批凝聚点或给出一个初始的分类，让样品按某种原则向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。动态聚类法有许多种方法，本节中，只讨论一种比较流行的动态聚类法——k均值法。k均值法是由麦奎因(MacQueen,1967)提出并命名的一种算法。§6.3快速聚类法(动态聚类法)类的个数k可以事先指定，也可以在聚类过程中确定。选择初始凝聚点(或给出初始分类)的一种简单方法是采用随机抽选(或随机分割)样品的方法。选择凝聚点分类修改分类分类是否合理分类结束YesNo用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：（a）空间的群点1、随机选取两个点(1)1x和(1)2x作为聚点,图(b)(b)任取两个聚点2、对任何点kx,分别计算(1)1,kdxx和(1)2,kdxx.(c)第一次分类(d)求各类中心3、若(1)(1)12(,)(,)kkdxxdxx则将kx划为第一类，否则划给第二类。于是得图(c)的两个类.4．分别计算两个类的重心，则得(2)1x和(2)2x，以其为新的聚点，图(d),(b)(e)第二次分类5.对空间中的点进行重新分类，得到新分类,图(e).1.快速聚类法的步骤(1)选择聚点1)经验选择k个样品作为聚点;2)人为选择k个样品作为聚点;(i)先选2个,12(,)max{}iiijddxx3)最小最大原则(ii)再选第3个3ix,满足1212max{min((,),(,),,}jijiddjiixxxx3132min{(,),(,)}iiiiddxxxx(iii)一般设已选l个,则第1l个由以下式子确定+1min{(,),1~}lriidrlxxr1max{min[(,),1~],~}jildrljiixx直到k个.这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太少，一般选d1＝2d。对代表点内的密度一般要求大于T。T0为规定的一个正数。4)按密度大小选代表点：以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度,并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心,再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点,否则不能作为代表点。(2)此后过程(假设采用欧氏距离)1)设初始聚点集(0)(0)(0)(0)12{,,,}kLxxx初始分类(1~ik)(最近者)(0)(0)(0){|(,)(,),1~,}iijGddjkjixxxxx(0)(0)(0)(0)12{,,,}kGGGG5)用前k个样本点作为代表点2)计算新聚点(0)(1)1,1~iiiixGiiknxx.重新分类：(1)(1)(1){|(,)(,),1~,}iijGddjkjixxxxx得到新分类集(1)(1)(1)(1)12{,,,}kGGGG3)设在第m步已得()()()()12{,,,}mmmmkGGGG(m)m-1)(m)iiiGxx（是类的重心，不一定是样品。(m+1)m)(m+1)iiiGxx（是类的重心，也不一定是样品类重心点集(m+1)(1)(1)(1)12{,,,}mmmkLxxx当m增大，分类趋于稳定时，(m+1)(m)iixx与趋于相等。实际计算，当m步与m+1步分类结果完全相同时，聚类过程结束。2.用mL距离进行快速聚类mL距离即明氏距离(Minkowski)对1L,也称绝对距离(1)记11(,)ijikjkijkpdxxxxxx。11(,)pmmijikjkkdxxxx(1)对1L,记11(,)ijikjkijkpdxxxxxx。当维数1p，12,,,nxxx,有(证略)11||minmednjjjnjxccMx。当p维,12,,,nxxx,也有12(,,,)TpMMMM(称为中位向量)其中分量,1~iMip均为中位数.使得1||min,1~njkkjxMkp从而1111||minpnnjjkkjjkxMxM(2)对一般1mL,记(,)ijijmdxxxx当1p维12,,,nxxx,称1||minnmjjxcc为m中心当p维12,,,nxxx,称12(,,,)Tpcccc为m中心向量其中分量,1~jcjp均为jkx的m中心,满足1||min,1~nmjkkjxMkp从而111||minpnnmmjjkkmjjkxMxM结论:(1)中心向量=中位向量(有较强的稳健性)(2)中心向量=均值向量.对一维数据,宜用1L;此外用1mL.结果与m有关例6.3利用表6.1的13个国家可持续发展综合国力的数据进行分类(4类),(1)用1L;(2)用1.5L.解:初始聚点最终结果(部分)相关信息中位数向量类间距离•①选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。②选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。•③直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。•三、初始分类和调整④最佳初始分类。如图所示，随着初始分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。准则函数JK最佳初始分类A拐点03217654下降快下降慢例用动态聚类法对例6.2给出31个城市的气候标准值进行聚类分析(聚为四类).输入R命令:x-read.table(“data.exam6.2.txt”,header=TRUE)rownames(x)-x[,1]stdx-scale(x[,2:9],center=TRUE,scale=TRUE)kmeans(stdx,4,iter.max=10,algorithm=“MacQueen”)输出结果中,K-meansclusteringwith4clustersofsizes13,4,11,3各类中的样品个数.为各个类的类中心(均值).Clustermeans:V1V2V3V4V510.527790770.89853470.17424160.81833811.00466452-2.06438887-0.4013210-1.72533750.2025202-0.87127323-0.01367297-0.52496260.6372198-0.5971752-0.773750440.51555940-1.4336925-0.7910695-1.6265161-0.3547638V6V7V810.99601630.026398711.04652402-0.1821661-0.63374505-0.77728963-0.8137310-0.27912237-0.80666664-1.08950211.75404768-0.5407737各个样品的分类情况:Clusteringvector:北京重庆安庆福州兰州广州南宁贵阳31113111海口承德哈尔滨郑州武汉长沙内蒙古南京13431131南昌长春沈阳银川西宁西安济南上海14432331太原西昌天津拉萨乌鲁木齐昆明杭州3232321x-rbind(matrix(rnorm(100,sd=0.3),ncol=2),matrix(rnorm(100,mean=1,sd=0.3),ncol=2))colnames(x)-c(x,y);x(cl-kmeans(x,2))plot(x,col=cl$cluster)points(cl$centers,col=1:2,pch=8,cex=2)R中例子