空间聚类分析

2011土地信息技术11空间聚类的内涵理解1.1定义空间聚类作为聚类分析的一个研究方向，是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度，而不同类中的对象间差异较大[3]。作为一种无监督的学习方法，空间聚类不需要任何先验知识。这是聚类的基本思想，因此空间聚类也是要满足这个基本思想。1.2对空间数据聚类的要求[2][5][6]①可伸缩性；许多聚类算法在小于200个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。②发现任意形状的聚类；许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。（虽然聚类分析属于非监督学习方法，但在某些情况下一些基本的客观规律也会或多或少指示聚类分析的结果）③用于决定输入参数的领域知识最小化；许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。④对噪声数据不敏感；绝大多数现实中的数据库都包含了孤立点，缺失，或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。⑤对于输入记录的顺序不敏感；2011土地信息技术2一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。⑥处理高维数据；一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数据可能分布非常稀疏，而且高度偏斜。2空间聚类的主要算法空间聚类的主要方法有五大类：划分聚类算法、层次聚类算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。[2][3]空间聚类算法层次聚类算法基于密度的方法基于模型法划分聚类算法K-模基于网格法K-meansK-medoidsPAMCLARAK-原型凝聚法分裂法ChameLeonCUREDBSCANOPTICSDENCLUESTINGCLIQUEWAVE-CLUSTERCOBWEB统计学方法神经网络的方法竞争学习算法图2-1空间聚类算法分类2.1划分聚类算法主要包括：K-means、K-medoids、PAM、CLARA、K-模、K-原型、EM和CLARANS等。基本思想：给定一个包含n个对象或数据的集合，将数据集划分为k个子集，其中每个子集均代表一个聚类(k≤n)，划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分中的对象来改变划分内容。2011土地信息技术3典型的算法说明：K-means算法是首先从n个数据对象随机地选择k个对象，每个对象初始地代表了一个簇中心，对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛（说明：一般都采用均方差作为标准测度函数）。特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开，这个特点正是聚类的最根本的实质要求[4]。但是K-means也有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。而在这一点上，K-medoids做出了相应的改进，K-medoids不采用聚类中对象的平均值作为参照点，而选用聚类中位置最中心的对象，即中心点，仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。2.2层次聚类算法层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的，层次聚类方法又可分为自顶向下的分裂算法和自底向上的凝聚算法两种。分裂聚类算法，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达了某个终结条件，这里的终结条件可以是簇的数目，或者是进行合并的阈值。而凝聚聚类算法正好相反，首先将每个对象作为一个簇，然后将相互邻近的合并为一个大簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。CURE(clusteringusingrepresentatives)算法采取随机取样和划分相结合的方法：一个随机样本首先被划分，每个划分被局部聚类，最后把每个划分中产生的聚类结果用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题，在处理孤立点时也更加健壮。CHAMELEON(hierarchicalclusteringusingdynamicmodeling)算法的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类，其次使用凝聚的层次聚类算法反复地合并子类来找到真正的结果类。CHAMELEON算法是在CURE等算法的基础上改进而来，能够有效的解决CURE等算法的问题。2011土地信息技术42.3基于密度的方法绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的类。因此，出现了基于密度的聚类方法，其主要思想是：只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就继续聚类，这样的方法可以过滤“噪声”数据，发现任意形状的类。从而克服基于距离的方法只能发现类圆形聚类的缺点。代表性算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。DBSCAN(densitybasedspatialclusteringofapplicationswithnoise)算法可以有效地发现具有任意形状的类，并正确地处理噪声数据。除此之外，该算法还具有实现简单、聚类效果较好等优点。该算法对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目，即DBSCAN算法将聚类定义为基于密度可达性最大的密度相连对象的集合。另外不进行任何的预处理而直接对整个数据集进行聚类操作。OPTICS算法是一种基于类排序方法。该算法并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。这个顺序代表了数据的基于密度的聚类结构。DENCLUE算法是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法：(1)每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在领域内的影响，被称为影响函数；(2)数据空间的整体密度可以被模型化为所有数据点的影响函数的总和；(3)聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。2.4基于网格法主要思想是将空间区域划分若干个具有层次结构的矩形单元，不同层次的单元对应于不同的分辨率网格，把数据集中的所有数据都映射到不同的单元网格中，算法所有的处理都是以单个单元网格为对象，其处理速度要远比以元组为处理对象的效率要高的多。代表性算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法等。STING(statisticalinformationgrid)算法首先将空间区域划分为若干矩形单2011土地信息技术5元，这些单元形成一个层次结构，每个高层单元被划分为多个低一层的单元。单元中预先计算并存储属性的统计信息，高层单元的统计信息可以通过底层单元计算获得。这种算法的优点是效率很高，而且层次结构有利于并行处理和增量更新；其缺点是聚类的边界全部是垂直或是水平的，与实际情况可能有比较大的差别，影响聚类的质量。CLIQUE(clusteringinquest)算法综合了基于密度和基于网格的聚类方法。其主要思想是将多维数据空间划分为多个矩形单元，通过计算每一个单元中数据点中全部数据点的比例的方法确定聚类。其优点是能够有效处理高维度的数据集，缺点是聚类的精度有可能会降低。WaveCluster(clusteringusingwavelettransformation)算法是一种采用小波变换的聚类方法。其首先使用多维数据网格结构汇总区域空间数据，用多维向量空间表示多维空间中的数据对象，然后使用小波变换方法对特征空间进行处理，发现特征空间中的稠密区域。最终通过多次小波变换，获得多分辨率的聚类。2.5基于模型法给每一个聚类假定一个模型，然后去寻找能够很好地满足这个模型的数据集。常用的模型主要有两种：一种是统计学的方法，代表性算法是COBWEB算法；另一种是神经网络的方法，代表性的算法是竞争学习算法。COBWEB算法是一种增量概念聚类算法。这种算法不同于传统的聚类方法，它的聚类过程分为两步：首先进行聚类，然后给出特征描述。因此，分类质量不再是单个对象的函数，而且也加入了对聚类结果的特征性描述。竞争学习算法属于神经网络聚类。它采用若干个单元的层次结构，以一种“胜者全取”的方式对系统当前所处理的对象进行竞争。3空间聚类分析的实现空间聚类分析可以分为基于点和基于面两种方法。基于点的方法需要时间准确的地理位置，基于面的的方法是运用其区域内的平均值[1]。到底用哪种方法，关键取决于数据，“基于点的方法并不总是优于基于面的方法。”（Odenetal.，1996）2011土地信息技术6当前ArcGIS软件中的空间统计分析功能还很有限，只能实现基于面的空间的空间聚类分析，其他软件如CrimeStat(Levine，2002)也有类似的功能。在这里将讲解SaTScan实现基于点的空间聚类分析和ArcGIS实现基于面的空间聚类分析，而本文的应用实例将采用SaTScan分析中国南部地区台语地名的聚集性。空间聚类分析基于点的空间聚类分析基于面的空间聚类分析全局聚类检验局部聚类检验用于分析研究对象在整个区域内是否具有空间集聚性。将所有观察个体区分为事件和非事件两类。对于大多数研究而言，研究区即使在全局聚类检验中没有统计显著性。也有可能存在着局部集聚的现象。图3-1空间聚类分析分类3.1SaTScan中空间聚类的实现3.1.1基于点的全局聚类检验全局聚类检验用于分析研究对象在整个区域内是否具有空间集聚性。将所有观察个体去分为事件和非事件两类。以Whittemoreetal.提出的全局聚类检验指标为例，先计算事件之间的平均距离，再计算所有个体之间的平均距离。如果前置比后者低，则表明时间在空间上存在集聚。当研究区的中心地区具有丰富的调查样本资料时，这个方法比较有效，但如果病例分散在外围地区，则此方法效果不佳[1]。3.1.2基于点的局部聚类检验对于大多数研究而言，确定空间集聚的具体位置或局部集聚也是十分重要的。研究区即使在全局聚类检验中没有统计想助兴，也有可能存在着局部集聚的现象。这里主要说明SaTScan软件使用的空间扫描统计法使用圆作为扫描窗口，搜索这个研究区，扫描窗口半径大小的选取，以圆内样本数占总样本数的比例来确2011土地信息技术7定，从0%到50%逐步上升。针对每个圈，比较窗口内和窗口外的出现的几率，存照窗口内统计上明显高的圈定义为空间集聚。空间扫描统计法使用泊松分布或伯努利分布来判断统计显著性。如果是二项分布数据（即事件与非事件数据）选用伯努利模型，它要求所有样本的地理坐标，事件记为1，非事件记为0。例如，在伯努利模型中窗口z的似然函数计算如下：其中，N为研究区中的样本总数，n为窗口中的事件数，M为研究区中的非事件数，m为窗口中的非事件数，p=n/m为事件在窗口中的概率，q=(N-n)(M-m)为事件在窗口外的概率。对每个窗口，求似然函数的最大值，最可能的集聚圈就是窗口内最不可能为随机分布的圈。这种方法找到了最可能的集聚圈后，还可能找到与之不重叠的次一级集聚圈。3.2ArcGIS中空间聚类的实现3.2.1空间权重的定义首先说明定义空间权重的不同方法，这对基于面的空间聚集分析确定各个观察对象之间的空间关系十分重要。基于距离来定义空间权重，方法有：1）以距离倒数为权重（1/d）。2）以距离平方的倒数为权重（1/d2）。3）以距离阈值定义权重（如在阈