聚类分析

数据的分类—聚类分析•在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具来发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上做进一步的分析。聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。其中，最广泛使用的聚类算法k-means算法属于划分法。聚类算法给定一个有N个元组或者纪录的数据集，划分法将构造K个分组，每一个分组就代表一个聚类，KN。而且这K个分组满足下列条件：（1）每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组（某些模糊聚类算法中该条件可以放宽）；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。划分法k-means算法，也被称为k-均值或k-平均。该算法首先随机地选择k个对象作为初始的k个簇的质心；然后对剩余的每个对象，根据其与各个质心的距离，将它赋给最近的簇，然后重新计算每个簇的质心；这个过程不断重复，直到准则函数收敛。通常采用的准则函数为平方误差和准则函数，即SSE(sumofthesquarederror)，其定义如下:SSE是数据库中所有对象的平方误差总和，p为数据对象，mi是簇Ci的平均值。这个准则函数使生成的结果尽可能的紧凑和独立。k-means算法饮料数据（drink.txt）•16种饮料的热量、咖啡因、钠及价格四种变量•如何根据以上数据对16种饮料进行分类呢？•对数据进行分类就需要知道距离？你知道那些距离？如何度量距离远近？•如果想要对100个学生进行分类，而仅知道他们的数学成绩，则只好按照数学成绩分类；这些成绩在直线上形成100个点。这样就可以把接近的点放到一类。•如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上的100个点，也可以按照距离远近来分类。•三维或者更高维的情况也是类似；只不过三维以上的图形无法直观地画出来而已。•在饮料数据中，每种饮料都有四个变量值。这就是四维空间点的问题了。两个距离概念•按照远近程度来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。•点间距离有很多定义方式。最简单的是歐氏距离。•当然还有一些和距离相反但起同样作用的概念，比如相似性等，两点越相似度越大，就相当于距离越短。两个距离概念•由一个点组成的类是最基本的类；如果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一类包含不止一个点，那么就要确定类间距离，•类间距离是基于点间距离定义的：比如两类之间最近点之间的距离可以作为这两类之间的距离，也可以用两类中最远点之间的距离或各类的中心之间的距离来作为类间距离。•在计算时，各种点间距离和类间距离的选择是通过统计软件的选项实现的。不同的选择的结果会不同，但一般不会差太多。向量x=(x1,…,xp)与y=(y1,…,yp)之间的距离或相似系数:2()iiixy欧氏距离:Euclidean平方欧氏距离:SquaredEuclidean2()iiixy夹角余弦(相似系数1):cosine22(1)cosiiixyxyiiiixyCxyPearsoncorrelation(相似系数2):Chebychev:Maxi|xi-yi|Block(绝对距离):Si|xi-yi|Minkowski:1()qqiiixy当变量的测量值相差悬殊时,要先进行标准化.如R为极差,s为标准差,则标准化的数据为每个观测值减去均值后再除以R或s.当观测值大于0时,有人采用Lance和Williams的距离||1iiiiixypxy22()()(2)()()iiixyxyiiiixxyyCrxxyy类Gp与类Gq之间的距离Dpq(d(xi,xj)表示点xi∈Gp和xj∈Gq之间的距离)min(,)pqijDdxx最短距离法:最长距离法:重心法:离差平方和:(Wald)类平均法:(中间距离,可变平均法,可变法等可参考各书).在用欧氏距离时,有统一的递推公式12121212()'(),()'(),()'()ipjqkpqipipjqjqxGxGkipqxGGDxxxxDxxxxDxxxxDDDDmax(,)pqijDdxxmin(,)pqpqDdxx121(,)ipjqpqijxGxGDdxxnn最短距离（NearestNeighbor)x21•x12•x22•x11•13d最长距离（FurthestNeighbor）•••x11•x21••••12d••••••991dd组间平均连接（Between-groupLinkage)组内平均连接法（Within-groupLinkage)1234566ddddddx21•x12•x22•x11•重心法（Centroidclustering):均值点的距离••11,xy22,xy离差平方和法连接2，41，56，522(23)(43)222(65.5)(55.5)0.522(13)(53)8红绿（2，4，6，5）8.75离差平方和增加8.75－2.5＝6.25黄绿（6，5，1，5）14.75离差平方和增加14.75－8.5＝6.25黄红（2，4，1，5）10－10＝0故按该方法的连接和黄红首先连接。•有了上面的点间距离和类间距离的概念，就可以介绍聚类的方法了。这里介绍两个简单的方法。系统聚类法•系统聚类法（hierarchicalclusteringmethod)是聚类分析中用的最多的一种。•基本思想：开始将n个样本各自作为一类，并规定样本之间的距离与类之间的距离，然后将距离最近的两类合并成一个新类，并计算新类与其他类之间的距离，重复进行两个最近类的合并，每次减少一类，直至所有的样本合并为一类。•当然我们可以选择以上距离的任意一种进行聚类。动态聚类法（K均值聚类）•前面说过，聚类可以走着瞧，不一定事先确定有多少类；但是这里的k-均值聚类（k-meanscluster，也叫快速聚类，quickcluster）却要求你先说好要分多少类。看起来有些主观，是吧！•假定你说分3类，这个方法还进一步要求你事先确定3个点为“聚类种子”(SPSS软件自动为你选种子)；也就是说，把这3个点作为三类中每一类的基石。•然后，根据和这三个点的距离远近，把所有点分成三类。再把这三类的中心(均值)作为新的基石或种子(原来“种子”就没用了)，再重新按照距离分类。•如此叠代下去，直到达到停止叠代的要求（比如，各类最后变化不大了，或者叠代次数太多了）。显然，前面的聚类种子的选择并不必太认真，它们很可能最后还会分到同一类中呢。下面用饮料例的数据来做k-均值聚类。•例1续•动态聚类的函数为kmeans()idx=kmeans(X,k,Name,Value)聚类要注意的问题•聚类结果主要受所选择的变量影响。如果去掉一些变量，或者增加一些变量，结果会很不同。•相比之下，聚类方法的选择则不那么重要了。因此，聚类之前一定要目标明确。•另外就分成多少类来说，也要有道理。只要你高兴，从分层聚类的计算机结果可以得到任何可能数量的类。•但是，聚类的目的是要使各类之间的距离尽可能地远，而类中点的距离尽可能的近，并且分类结果还要有令人信服的解释。这一点就不是数学可以解决的了。2020/6/625主成分分析2020/6/626一、什么是主成分分析及基本思想1、什么是主成分分析主成分概念首先由Karlparson在1901年引进，不过当时只对非随机变量来讨论的。1933年Hotelling将这个概念推广到随机向量：在实际问题中，研究多指标(变量)问题是经常遇到的，然而在多数情况下，不同指标之间是有一定相关性。由于指标较多再加上指标之间有一定的相关性，势必增加了分析问题的复杂性。主成分分析就是设法将原来指标重新组合成一组新的互相无关的几个综合指标来代替原来指标，同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息。这种将多个2020/6/627指标化为少数互相无关的综合指标的统计方法叫做主成分分析或称主分量分析。也是数学上处理降准的一种方法，例如，某人要做一件上衣要测量很多尺寸，如身长、袖长、胸围、腰围、肩宽、肩厚等十几项指标，但某服装厂要生产一批新型服装绝不可能把尺寸的型号分得过多？而是从多种指标中综合成几个少数的综合指标，做为分类的型号，利用主成分分析将十几项指标综合成3项指标，一项是反映长度的指标，一项是反映胖瘦的指标，一项是反映特体的指标。在商业经济中用主成分分析可将复杂的一些数据综合成几个商业指数形式，如物价指数、生活费用指数，商业活动指数等等。主成分分析除了可以单独用来处理上面所讨论的这一类问题外，还可以与其它方法结合起来使用，例如与回归分析结合起来就是主成分回归，它可以克服回归问题中由于自变量之间的高度相关而产生的分析困难。2020/6/6282基本思想主成分分析就是设法将原来众多具有一定相关性的指标(比如p个指标)，重新组合成一组新的相互无关的综合指标来代替原来指标。通常数学上的处理就是将原来p个指标作线性组合，作为新的综合指标，但是这种线性组合，如果不加限制，则可以有很多，我们应该如何去选取呢?如果将选取的第一个线性组合即第一个综合指标记F1，自然希望F1尽可能多的反映原来指标的信息，这里的“信息”用什么来表达?最经典的方法就是用F1的方差来表达，即Var(F1)越大，表示F1包含的信息越多。因此在所有的线性组合中所选取的F1应该是方差最大的，故称F1为第一主成分。如果第一主成分不足以代表原来p个指标的信息，再考虑选取F2即选第二个线性组合，为了有效地反映原来信息，F1已有的信息就不需要再出现在F2中，用数学2020/6/629语言表达就是要求Cov(F1，F2)＝0，称F2为第二主成分，依此类推可以造出第三，四，…，第p个主成分。不难想像这些主成分之间不仅不相关，而且它们的方差依次递减。因此在实际工作中，就挑选前几个最大主成分，虽然这样做会损失一部分信息，但是由于它使我们抓住了主要矛盾，并从原始数据中进一步提取了某些新的信息，因而在某些实际问题的研究中得益比损失大，这种既减少了变量的数目又抓住了主要矛盾的做法有利于问题的分析和处理。2、主成分分析的数学模型及几何解释（1）、数学模型设有n个样品，每个样品观测p项指标(变量),X1,X2，…，Xp，得到原始数据资料阵：2020/6/630其中用数据矩阵X的p个向量(即p个指标向量)X1，…，Xp作线性组合(即综合指标向量)为：2020/6/631简写成(注意：Xi是n维向量，所以Fi也是n维向量)上述方程组要求：2020/6/632的一切线性组合中方差最大的。如何求满足上述要求的方程组的系数aij呢?下一节将会看到每个方程式中的系数向量不是别的而恰好是X的协差阵所对应的特征向量；也就是说，数学上可以证明使Var(F1)达到最大，这个最大值是在的第一个特征值所对应特征向量处达到。依此类推使Var(Fp)达到最大值是在的的特征值2020/6/633第p个特征值所对应特征向量处达到。这里要说明两点：一个是数学模型中为什么作线性组合?基于两种原因：①数学上容易处理；②在实践中效果很好。另一个要说明的是每次主成分的选取使Var(Fi)最大，如果不加限制就可使Var(Fi)则就无意义了，而常用的限制是要求（2）主成分的几何意义从代数学观点看主成分就是p个变量X1…，Xp的一些特殊的线性组合，而在几何上这些线性组合正是把X1，…，Xp构成的坐标系旋转产生的新坐标系，新坐标轴使之通过样品变差最大的方向(或说具有最大的样品方差)。下面以最简单的二元正态变量来说明主成分的几何意义。•2x1