空间聚类分析.doc

《空间聚类分析.doc》由会员分享，可在线阅读，更多相关《空间聚类分析.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除1 空间聚类的内涵理解1.1 定义空间聚类作为聚类分析的一个研究方向，是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度，而不同类中的对象间差异较大3。作为一种无监督的学习方法，空间聚类不需要任何先验知识。这是聚类的基本思想，因此空间聚类也是要满足这个基本思想。1.2 对空间数据聚类的要求256 可伸缩性；许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。 发现任意形状的聚

2、类；许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。（虽然聚类分析属于非监督学习方法，但在某些情况下一些基本的客观规律也会或多或少指示聚类分析的结果） 用于决定输入参数的领域知识最小化；许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。 对噪声数据不敏感；绝大多数现实中的数据库都包含了孤立点，缺失，或者错

3、误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。 对于输入记录的顺序不敏感；一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。 处理高维数据；一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数据可能分布非常稀疏，而且高度偏斜。2 空间聚类的主要算法空间聚类的主要方法有五大类：划分聚类算法、层次聚类

4、算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。23图2-1空间聚类算法分类2.1 划分聚类算法主要包括：K-means、K-medoids、PAM、CLARA、K-模、K-原型、EM和CLARANS等。基本思想：给定一个包含n个对象或数据的集合，将数据集划分为k个子集，其中每个子集均代表一个聚类(kn)，划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分中的对象来改变划分内容。典型的算法说明：K-means算法是首先从n个数据对象随机地选择k个对象，每个对象初始地代表了一个簇中心，对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇

5、的平均值。这个过程不断重复，直到准则函数收敛（说明：一般都采用均方差作为标准测度函数）。特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开，这个特点正是聚类的最根本的实质要求4。但是K-means也有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。而在这一点上，K-medoids做出了相应的改进，K-medoids不采用聚类中对象的平均值作为参照点，而选用聚类中位置最中心的对象，即中心点，仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。2.2 层次聚类算法层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的，层次聚类方法又可分为自顶向下的分裂算法和自底向

6、上的凝聚算法两种。分裂聚类算法，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达了某个终结条件，这里的终结条件可以是簇的数目，或者是进行合并的阈值。而凝聚聚类算法正好相反，首先将每个对象作为一个簇，然后将相互邻近的合并为一个大簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。CURE(clustering using representatives)算法采取随机取样和划分相结合的方法：一个随机样本首先被划分，每个划分被局部聚类，最后把每个划分中产生的聚类结果用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题，在处理孤立点时也更加健壮。CHA

7、MELEON(hierarchical clustering using dynamic modeling)算法的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类，其次使用凝聚的层次聚类算法反复地合并子类来找到真正的结果类。CHAMELEON 算法是在CURE 等算法的基础上改进而来，能够有效的解决CURE等算法的问题。2.3 基于密度的方法绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的类。因此，出现了基于密度的聚类方法，其主要思想是：只要邻近区域的密度(对象或数据点的数目) 超过某个阈值，就继续聚类，这样的方法可以过滤“噪声”数据，发现任意形状的类。从而克

8、服基于距离的方法只能发现类圆形聚类的缺点。代表性算法有：DBSCAN 算法、OPTICS 算法、DENCLUE算法等。DBSCAN(density based spatial clustering of applications with noise)算法可以有效地发现具有任意形状的类，并正确地处理噪声数据。除此之外，该算法还具有实现简单、聚类效果较好等优点。该算法对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目，即DBSCAN算法将聚类定义为基于密度可达性最大的密度相连对象的集合。另外不进行任何的预处理而直接对整个数据集进行聚类操作。OPTICS 算法是一种基

9、于类排序方法。该算法并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。这个顺序代表了数据的基于密度的聚类结构。DENCLUE 算法是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法： (1) 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在领域内的影响，被称为影响函数； (2) 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和； (3) 聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。2.4 基于网格法主要思想是将空间区域划分若干个具有层次结构的矩形单元，不同层次的单元对应于不同的分辨率网格，把数据集中

10、的所有数据都映射到不同的单元网格中，算法所有的处理都是以单个单元网格为对象，其处理速度要远比以元组为处理对象的效率要高的多。代表性算法有：STING算法、CLIQUE 算法、WAVE-CLUSTER 算法等。STING(statistical information grid) 算法首先将空间区域划分为若干矩形单元，这些单元形成一个层次结构，每个高层单元被划分为多个低一层的单元。单元中预先计算并存储属性的统计信息，高层单元的统计信息可以通过底层单元计算获得。这种算法的优点是效率很高，而且层次结构有利于并行处理和增量更新；其缺点是聚类的边界全部是垂直或是水平的，与实际情况可能有比较大的差别，影响

11、聚类的质量。CLIQUE(clustering in quest)算法综合了基于密度和基于网格的聚类方法。其主要思想是将多维数据空间划分为多个矩形单元，通过计算每一个单元中数据点中全部数据点的比例的方法确定聚类。其优点是能够有效处理高维度的数据集，缺点是聚类的精度有可能会降低。WaveCluster(clustering using wavelet transformation)算法是一种采用小波变换的聚类方法。其首先使用多维数据网格结构汇总区域空间数据，用多维向量空间表示多维空间中的数据对象，然后使用小波变换方法对特征空间进行处理，发现特征空间中的稠密区域。最终通过多次小波变换，获得多分辨率

12、的聚类。2.5 基于模型法给每一个聚类假定一个模型，然后去寻找能够很好地满足这个模型的数据集。常用的模型主要有两种：一种是统计学的方法，代表性算法是COBWEB算法；另一种是神经网络的方法，代表性的算法是竞争学习算法。COBWEB 算法是一种增量概念聚类算法。这种算法不同于传统的聚类方法，它的聚类过程分为两步：首先进行聚类，然后给出特征描述。因此，分类质量不再是单个对象的函数，而且也加入了对聚类结果的特征性描述。竞争学习算法属于神经网络聚类。它采用若干个单元的层次结构，以一种“胜者全取”的方式对系统当前所处理的对象进行竞争。3 空间聚类分析的实现空间聚类分析可以分为基于点和基于面两种方法。基于

13、点的方法需要时间准确的地理位置，基于面的的方法是运用其区域内的平均值1。到底用哪种方法，关键取决于数据，“基于点的方法并不总是优于基于面的方法。”（Oden etal.，1996）当前ArcGIS软件中的空间统计分析功能还很有限，只能实现基于面的空间的空间聚类分析，其他软件如CrimeStat(Levine，2002)也有类似的功能。在这里将讲解SaTScan实现基于点的空间聚类分析和ArcGIS实现基于面的空间聚类分析，而本文的应用实例将采用SaTScan分析中国南部地区台语地名的聚集性。图3-1 空间聚类分析分类3.1 SaTScan中空间聚类的实现3.1.1 基于点的全局聚类检验全局聚类

14、检验用于分析研究对象在整个区域内是否具有空间集聚性。将所有观察个体去分为事件和非事件两类。以Whittemore et al.提出的全局聚类检验指标为例，先计算事件之间的平均距离，再计算所有个体之间的平均距离。如果前置比后者低，则表明时间在空间上存在集聚。当研究区的中心地区具有丰富的调查样本资料时，这个方法比较有效，但如果病例分散在外围地区，则此方法效果不佳1。3.1.2 基于点的局部聚类检验对于大多数研究而言，确定空间集聚的具体位置或局部集聚也是十分重要的。研究区即使在全局聚类检验中没有统计想助兴，也有可能存在着局部集聚的现象。这里主要说明SaTScan软件使用的空间扫描统计法使用圆作为扫描

15、窗口，搜索这个研究区，扫描窗口半径大小的选取，以圆内样本数占总样本数的比例来确定，从0%到50%逐步上升。针对每个圈，比较窗口内和窗口外的出现的几率，存照窗口内统计上明显高的圈定义为空间集聚。空间扫描统计法使用泊松分布或伯努利分布来判断统计显著性。如果是二项分布数据（即事件与非事件数据）选用伯努利模型，它要求所有样本的地理坐标，事件记为1，非事件记为0。例如，在伯努利模型中窗口z的似然函数计算如下：其中，N为研究区中的样本总数，n为窗口中的事件数， M为研究区中的非事件数，m为窗口中的非事件数，p=n/m为事件在窗口中的概率，q=(N-n)(M-m)为事件在窗口外的概率。对每个窗口，求似然函数

16、的最大值，最可能的集聚圈就是窗口内最不可能为随机分布的圈。这种方法找到了最可能的集聚圈后，还可能找到与之不重叠的次一级集聚圈。3.2 ArcGIS中空间聚类的实现3.2.1 空间权重的定义首先说明定义空间权重的不同方法，这对基于面的空间聚集分析确定各个观察对象之间的空间关系十分重要。基于距离来定义空间权重，方法有：1）以距离倒数为权重（1/d）。2）以距离平方的倒数为权重（1/d2）。3） 以距离阈值定义权重（如在阈值方位内定义为1，在阈值范围外定义为0）。4）定义权重为距离的一个连续函数：ij=exp(-dij2/h2)其中，dij是地区i和地区j之间的距离，h是距离阈值范围（Fotheri

17、ngham et al.，2000：111），阈值范围的选取决定于距离影响程度，一个高度h值表示地区之间的相互影响距离远，影响范围大。上述基于距离的空间权重，在ArcGIS软件中都有相应的定义工具，具体是在“Cpnceptualization of Spatial Relationships”（定义空间关系）的时候选定的7。ArcGIS中可选的前三项为“Inverse Distance”、“Inverse Distance Squared”、“Fixed Distance Band”分别对应着上述的“距离倒数”、“距离平方倒数”和“距离阈值”这三种空间权重定义方法。第四项为“Zone of I

18、ndifference”，指给定一个距离阈值，在阈值范围内由距离倒数定义空间权重，在范围之外定义为0。3.2.2 基于面的全局聚类检验Morans I指数是最早应用于全局聚类检验的方法。它检验整个研究区中临近地区间是相似、相异（空间正相关、负相关），还是相互独立的。Morans I指数计算公式：这里，N是研究区内地区总数，ij是空间权重， xi 和 xj分别是区域i和j的属性，是属性的平均值。Morans I指数数值处于-1到1之间，值接近1是表明具有相似的属性集聚在一起；值接近-1时表明具有相异的属性集聚在一起。如果Morans I指数接近于0则表示属性是随机分布的，或者不存在空间自相关性。

19、与Morans I指数相似，吉瑞C指数（Gearys C）也是全局聚类检验的一个指数，其公式为：吉瑞C指数值通常在0到2之间。虽然2不是一个严格的上界。其值为1时，表示属性的观察值在空间上是相互独立的，值在0到1之间表示空间正相关，值在1到2之间时表示空间负相关。因此，吉瑞C指数与Morans I指数刚好相反。在ArcGIS的空间统计工具包中，提供了Morans I指数和吉瑞C指数的计算功能：ArcToolboxSpatial Statistics ToolsAnalyzing Patterns选Spatial Autocorrelation(Morans I)计算Morans I，选High

20、-Low Clustering(Getis-Ord General G)计算吉瑞C。3.2.3 基于面的局部聚类检验Anselin提出了一个局部莫兰指数（Local Moran Index）用来检验局部地区是否存在相似或者相异的观察值聚集在一起。区域i的局部莫兰指数用来度量区域i和它领域之间的关联程度，定义为：正的Ii表示一个高值被高值所包围（高-高）或者是一个低值被低值所包围（低-低）；负的Ii表示一个低值被高值所包围或与之相反的情况。类似地，Gi指数（Getis and Ord，1992）用来检验局部地区是否存在显著地高值或低值。Gi定义如下：公式中的符号与Morans I指数相同，式中对

21、j的累加不包括区域i本身，即j不等于i；高的Gi代表高值的样本集中在一起，而低的Gi值表示低值的样本集中在一起。在ArcGIS的空间统计工具包中，计算局部莫兰指数和Gi指数：ArcToolboxSpatial Statistics ToolsMapping Clusters选Cluster and Outlier Analysis(Anselin Local Moran Index)计算局部莫兰指数，选Hot Spot Analysis(Getis-Ord Gi*)计算Gi指数。计算结果分别用“Cluster and Outlier Analysis with Rendering ”和“Hot

22、 Spot Analysis with Rendering”的工具来绘图显示。4 应用实例本案例是对于中国南部地区台语地名的空间分布进行区别是随机分布还是存在集聚性，实现过程是利用SaTScan软件（版本9.1）来完成1。1、用ArcGIS准备SaTScan软件的数据在SaTScan软件平台下，用伯努利模型执行基于点的空间聚类分析需要定义三个数据文件，即事件文件（包含区位ID和每个区位的事件数），非事件文件（包含区位ID和每个区位的非事件数）以及坐标文件（包含区位ID和对应的笛卡尔坐标或经纬度坐标）。这一步就是在ArcGIS中定义好相关属性，如必须给图层文件加入变量的坐标（Add XY Coo

23、rdinates）,并将属性表输出为dBase文件格式。如下图。图4-1 图层文件属性表 图中的TAI是事件属性，POINT_X、POINT_Y是加入的坐标属性，NONTAI是根据TAI计算出的非事件属性，这些属性是不可缺少的。2、用SaTScan软件执行空间聚类分析运行SaTScan软件，选择Creat New Session，系统弹出一个新的对话框，如图。图4-2 SaTScan软件创建新任务图4-3 空间聚类分析文件设置对话框在第一个标签Input下使用Import Wiard来定义事件文件（Case File）：选择上面输出的dBase文件作为输入文件，弹出对话框，如图所示。图4-4

24、Import Wiard对话框设置Case File按照上述的步骤定义好Case File、Control File以及Coordinates File。在第二个标签Analysis下进行选择操作，按照下图所示设置。图4-5 Analysis设置在第三个标签Output下，输入cluster作为结果输出文件，在dBase下点击所有的选项按钮。最后运行。3、分析结果的制图在ArcGIS下，基于关联码Location ID和cluster.gis.dbf中的LOC_ID将dBase文件cluster.gis.dbf连到图层文件上。结果如下图。图4-6 分析结果5 参考文献1 王法辉著.基于GIS的数量方法与应用M.姜世国，滕骏华译.北京：商务印书馆，2009.2 马程.空间聚类研究J. 计算机技术与发展.2009,19(4).3 席景科，谭海樵.空间聚类分析及评价方法J.计算机工程与设计.2009,30 (7).4 戴晓燕，过仲阳，李勤奋，吴健平.空间聚类的研究现状及其应用J. 上海地质.2003,4.5 聚类算法_百度百科. 6 柳彦平，王文杰，谈恒贵.数据挖掘空间聚类. 计算机工程与应用.2005,357 Desktop Help 10.【精品文档】第 11 页