06聚类分析方法与操作

技术资料6：聚类分析方法与操作聚类是一种应用非常广泛的数据分析方法，它是统计学的一个分支，目前在诸多领域，包括数据挖掘、图像处理、市场研究等，都能凸显出其重要性。聚类是将一个对象的集合分成不同的类，从而描述数据。通过这种方式，人们能够将密集的和稀疏的区域区分开来，从而发现全局的分布模式，以及数据属性之间有趣的相互关系。很久以前人们就对聚类方法有所研究。传统的聚类方法主要是基于距离的聚类，例如欧氏距离、切比雪夫距离、马氏距离[1]等。在今天，聚类分析也是数据挖掘和知识发现领域中的重要课题。迄今为止，人们已经提出了许多数据聚类的算法，试图解决各种领域的聚类问题。从目前来看，对数据挖掘中聚类方法的研究大都集中于计算机科学领域，更多注重聚类算法的研究，或者对现有聚类方法进行算法上的改进，而很少真正从统计学角度出发对数据挖掘中的聚类问题进行深入分析。若尝试从统计学视角出发，以统计理论为基础，以统计方法与算法相结合为基本思路，将一些现有的优秀统计方法，如因子分析、对应分析等引入数据挖掘领域，则能够使其应用于海量数据的聚类分析。（一）聚类分析的基本概念聚类是指将一群物理的或抽象的对象，根据它们之间的相似程度，分为若干组，并使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的。一个聚类就是由彼此相似的一组对象所构成的集合。在很多应用中，我们可以把同一个类的数据对象当做一个整体来处理。聚类的严格数学描述如下：假设被研究的样本集为E，类C定义为E的一个非空子集，即：EC，且C聚类就是满足以下两个条件的类1C，2C，…，kC的集合：(1)1C2C…ECk(2)jiCC=(对任意ji)由第一个条件可知，样本集E中的每个样本必定属于某一个类；由第二个条件可知，样本集E中的每个样本最多只属于一个类。（二）几种主要的聚类方法如今各种各样的聚类方法层出不穷，我们在选用聚类方法时也会依据不同的标准，例如数据的类型、数据的大小等等。目前主要的聚类方法有：划分的方法、层次的方法、基于密度的方法、基于网格的方法等。（1）划分的方法划分的方法是指将一个给定n个数据对象的数据集合，构建数据的k个划分，每个划分表示一个聚类，这k个分组必须满足：每个组至少包含一个对象；每个对象必须属于且只属于一个组。给定要构建的划分的数目k，划分方法首先创建一个初始划分，然后采用一种迭代的重定位技术，通过对象在划分间的移动来改进划分[3]。好的划分的一般准则是：同一分组中的距离越近越好，而不同分组中的距离越远越好，即使得下列的准则函数最小：kjCxjjmxE1上式中jm是类jC的均值，x是数据空间中的数据对象。属于该类的聚类方法有k-均值(k-means)算法、k-中心点(k-medoids)算法、PAM、CLARA、CLARANS等。（2）层次方法将给定的数据对象集合进行层次的分解，这就是层次聚类法。我们可根据层次分解的形成方式不同，把层次方法分为凝聚的和分裂的。凝聚的方法首先把每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件；分裂的方法首先把所有的对象置于一个聚类中，在每步迭代里，一个簇被分裂成更小的簇，直到最后每个对象在单独的一个簇中，或者达到一个终止条件[4]。层次方法的缺陷在于，执行合并或分裂的操作不能被撤销。这个严格规定是有用的，由于不用担心组合数目的不同选择，故计算代价会较小。不过，该技术的一个主要问题是它不能改正错误的决定。我们可以通过两种方法来改进层次聚类的结果：一是在每层划分中，仔细分析对象之间的“联接”；二是把层次凝聚和迭代的重定位方法综合起来，先用自底向上的层次算法，再用迭代的重定位来改进结果。层次方法包括BIRCH、CURE、ROCK、Chameleon算法等。（3）密度方法绝大多数划分方法是基于对象之间的距离进行聚类的。这样的方法只能发现球状的簇，却在发现任意形状的簇上遇到了困难。随之提出了基于密度的聚类方法，它的主要思想是：只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就继续聚类。主要的基于密度的方法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。（4）网格方法基于网格的方法首先将数据空间量化为有限数目的单元，形成了一个网格结构，全部的聚类操作都在这个网格结构上进行。这种方法的主要优点在于它的处理速度很快，且处理时间与数据对象的数目相独立，只取决于量化空间中每一维的单元数目。有代表性的网格方法是STING算法，除此之外，CLIQUE算法和Wavecluster算法既是基于网格的，又是基于密度的。（三）聚类方法的进一步分析和总结以上我们将现有的主要聚类方法大致分为划分的方法、层次的方法、基于密度的方法、基于网格的方法四大类。下面我们将从聚类标准、类的标识这两个角度对众多聚类方法进行更为全面和深入的分析与对比，以加深对聚类方法的认识。（1）聚类标准聚类分析的最主要的任务是建立数据对象之间以及类与类之间相似性的度量标准。最常用的相似性标准包括：以距离为标准、以密度为标准和以链接为标准。1）以距离为标准距离是一种最为简单、直观的聚类标准。常见的数据对象之间距离的度量指标包括欧式距离、切比雪夫距离距离等。以距离为标准的聚类方法只能建立在欧式空间上。类间距离的度量广泛使用如下四种方法：代表点距离：(,)(,)repijijDCCdmm平均距离：）（jiCxCxjijiavgnnxxdCCDjjii,),(),(最小距离：min(,)min(,)|,ijijiijjDCCdxxxCxC最大距离：jjiijijiCxCxxxdCCD,|),(max),(max上式中，用),(jiCCD表示类间距离，用),(jixxd表示数据点之间距离，im和jm分别是类iC和jC的代表点(或称“重心”)。单一代表点的聚类方法(如k-means法和k-medoids法)通常使用代表点距离来度量类间距离。平均距离、最小距离、最大距离的计算时间复杂度均为)(21nnO，因此，直接使用这三种方式来度量类间距离时算法效率一般较低，唯一的例外是BIRCH方法，该方法借助聚类特征树来提高算法速度[5]。用距离作为聚类标准比较直观且易于计算，但是对异常点通常比较敏感。所以，它们经常会通过引入某项技术来克服异常点的影响。例如，k-medoids利用中心点而不利用均值作为类的代表点，从而降低了异常点的影响；CURE通过调节“收缩因子”，对多个代表点进行收缩处理来减少对孤立点的敏感度[6]；BIRCH通过控制子类的直径来控制孤立点的影响。2）以密度为标准以密度为标准的聚类方法也只能建立在欧式空间上。相对于以距离为标准，以密度为聚类标准的最大优点就是可以发现任意形状的类，并且能够有效地消除噪声。以密度为标准的聚类方法中，数据点之间相似程度的判断标准是它们是否属于同一个连续的密集区域，同属于一个连续密集区域的数据点被归为一类。根据密度计算方式的不同，以密度为聚类标准的方法又可以进一步划分为三类：基于网格的方法、最近邻方法和基于密度函数的方法。基于网格的方法通过网格内数据对象的数量来计算类的密度。通过这种方法得到的密度仅仅是真实密度的近似，从而会降低聚类的精确度。STING、Wavecluster和CLIQUE方法属于这一类。最近邻方法把一定半径内最近邻的数据对象的个数是否超过临界值作为判断密度是否足够高的标准。DBSCAN和OPTICS都属于这一类。基于密度函数的方法利用密度函数的大小来表示类的密度，并且通过寻找密度函数的局部最大值精确地确定类。这类方法包括DENCLUE等。3）以链接为标准以链接为标准的聚类方法的目标是把具有更多链接的数据点聚为一类，即其相似性度量采用的是链接的数目[7]。这类方法一般都把模型建立在一个稀疏图上，然后依据图中的信息进行聚类。此类方法的代表是ROCK和Chameleon。以链接为标准的聚类方法可以建立在任意空间之上。除此之外，由于在高维空间中距离和密度的度量常常失效，此时，以链接为标准的方法就是一个较优的选择。（2）类的标识聚类分析的目的是要把原始数据划分成不同的类，每一类代表了相似的数据点的集合，因此，任何聚类方法都需要用某种方式对不同的类别作出标识。我们把聚类方法中对类别进行标识的方式分为如下三类：1）以代表性的数据点进行标识大多数以距离为标准的聚类方法都使用代表性的数据点对类别进行标识。这些代表性的点既可以是原始数据中存在的点，也可以是原始数据中不存在的点，如类的均值。最简单的方法是利用单一代表点来标识类别。原始数据库中每一个数据点被划分到离它最近的单一代表点。例如，k-means方法利用类均值作为代表点；k-medoids方法利用原始数据库中距离类中心最近的点作为代表点；另外，BIRCH、CLARA、CLARANS等方法也是利用单一代表点对类别进行标识。单一代表点方法的最大缺陷是只能识别凸状或球状的类。多代表点方法(如CURE、ROCK、Chameleon等)的出现在一定程度上克服了这一困难。这种方法首先选择距离类中心最近的点作为代表点，然后选出离类中心较远且彼此相距也较远的点作为代表点。多个代表点可以描绘出类的形状特征，从而使得聚类方法能够识别任意形状的类。2）以密集区域进行标识DBSCAN、OPTICS等基于密度的聚类方法利用相互分隔的密集区域来标识类或者子类。每个密集区域中都包含一个核心对象。核心对象是指一定半径内最近邻的个数超过指定临界值的数据点[8]。一个核心对象可以扩张出一个子类，因此聚类的过程就等价于核心对象的搜索过程。由于核心对象的搜索将耗费大量计算资源，所以这类聚类方法常借助特殊的索引结构来加快搜索速度。3）以网格单元进行标识基于网格的聚类方法利用网格单元的特征来描述类别特征。如果说密集区域是数据点的凝聚，网格单元则是数据空间的划分。一个网格单元就近似地代表了落入其中的数据点，因此，网格单元在局部范围内近似地反映了数据点的分布状况。由于网格是独立于数据的，且网格单元的数量远远少于数据对象的数量，所以，网格单元特征的汇总远比密集区域的搜索效率高，因此这类方法往往运算速度很快。但由于网格单元毕竟只是数据对象的近似代表，因此其精确度常常不能令人满意。7聚类分析的SPSS操作方法城镇居民消费水平通常用下表中的八项指标来描述。八项指标间存在一定的线性相关。为研究城镇居民的消费结构，需将相关性强的指标归并到一起，这实际上就是对指标聚类。实验数据表2001年30个省。市，自治区城镇居民月平均消费数据x1人均粮食支出(元／人)x5人均衣着商品支出(元／人)x2人均副食支出(元／人)x6人均日用品支出(元／人)x3人均烟、酒、茶支出(元／人)x7人均燃料支出(元／人)x4人均其他副食支出(元／人)x8人均非商品支出(元／人)x1x2x3x4x5x6x7x8北京7.7848.448.0020.5122.1215.731.1516.61天津10.8544.687.3214.5117.1312.081.2611.57河北9.0928.127.409.6217.2611.122.4912.65山西8.3523.537.518.6217.4210.001.0411.21内蒙古9.2523.756.619.1917.7710.481.7210.51辽宁7.9039.778.4912.9419.2711.052.0413.29吉林8.1930.504.729.7816.287.602.5210.32黑龙江7.7329.205.429.4319.298.492.5210.00上海8.2864.348.0022.2220.0615.520.7222.89江苏7.2145.797.6610.3616.5612.862.2511.69浙江7.6850.3711.3513.3019.2514.592.7514.87安徽8.1437.759.618.4913.159.761.2811.28福建10.6052.4