基于云计算架构的西藏生态数据聚类分析算法研究

巴桑次仁

（西藏自治区科技信息研究所，西藏 拉萨 850001）

随着互联网时代的发展，人们接触的数据量越来越多，对空间信息的需求也呈上升趋势。然而空间数据的类型是多样化的，如何将这些庞大的数据量进行聚类分析，得到满足实际应用的需求数据是人们现在最关注的问题[1]。而对空间数据分析获取有效信息，关键一步是对空间数据进行聚类分析，得到其中隐含的有效信息。海量信息处理方面，对聚类算法的要求越来越高，速率和计算的复杂度仅仅只是其中的两个方面，当然也是最主要的两个方面，因此传统单机的聚类算法在处理海量信息时，这两个方面已经达不到要求了。如果仍然要在传统的分布式系统上实现算法的并行，这无疑会增加系统开发者的工作量。因为这种做法不仅仅要考虑到算法本身、软硬件平台的特性，更不能忽略实际应用当中的需求。

基于Hadoop平台对空间聚类算法进行优化，能够有效的降低时间复杂度和提高空间聚类分析的精准度，还可以提取空间数据库中的一些隐式知识，空间关系或者是一些其他有意义的模式[2]。因此空间聚类算法在城市规划、土地利用数据、遥感等领域的空间数据分析中都起到了巨大作用。所以基于Hadoop框架下的空间聚类算法研究就变的十分重要。一般情况下会用一些参数来描述地理空间实体的分布规律，这些参数通常有：分布密度、离散度、分布的中心和轴线等，而地理空间实体的分布规律往往可以用来揭示空间实体的群体定位特征。空间聚类分析就是现在比较常见的，用来揭示空间实体的群体定位特征的方法之一。比如基于划分的聚类算法，通过该算法得到的空间聚类，在一定程度上可以间接反映空间实体的分布中心和分布轴，这是因为基于划分的聚类需要选取出聚类的中心，并使用了不同的距离度量方法。又例如，基于密度的聚类分析方法，该算法在一定程度上能把空间群体的分布密度以及离散度反映出来，这是因为基于密度的聚类分析方法在判断空间实体是否同属于一个聚类时，是根据空间实体间的分布密度来度量的[3]。

聚类分析主要是依据空间对象的特征，然后把描述这些个体的数据集分为相互之间有区别的组（这些组也可称之为类）。使得组内的相似性尽可能的大，而组间的相似性尽可能的小。一个空间对象就是特征空间中的一个点，在聚类算法中局势用特征来表示空间对象。空间数据库中的聚类其实就是对目标图形进行聚类，如今，空间目标有多种类型，如：点状、线状、面状，并且在大多数时候数据量非常庞大并且聚类形状也十分复杂，这无疑使空间数据挖掘对聚类有了更高的要求：①算法所需的参数能够自动或者由用户确定；②能够处理任意形状的聚类；③在处理大型空间数据库时的效率能够较高；④能够对任意形状的对象进行聚类，如点状、线状、面状。

数据挖掘当中，聚类按照相似性以及距离度量在空间数据集中标识稠密分布的地区或聚类，然后从当中发现数据集的典型模式以及整个空间的分布规律，然而这不仅仅是知识发现任务的一个重要组成部分了，同时它也是数据挖掘系统中发现关联知识、分类知识、广义知识等共性知识的先决条件[4]。

1 研究内容

文章选取K-means算法，基于Hadoop框架的并行化架构对空间数据的聚类算法开展研究。研究中选取特定研究区的植被评价遥感影像数据。通过编写程序获取大量随机采样数据，每条数据是包括经纬度、植被评价值的二元组数据。将这些数据作为聚类算法研究的原始数据，经过去除异常点和数据归一化等预处理手段，获取实验数据集。基于K-means聚类算法的原理设计空间数据聚类算法，取得的实验结果与研究区的实际数字高程模型（DEM）进行对比分析，检验算法计算的植被评价值分类与高程数据的变化是否存在对应关系，最终对算法的有效性做出评估。

2 算法设计与实现

2.1 MMKMEANS算法思想

MMKEANS算法是基于最大最小距离原理，是相对于传统的K-means算法所提出的一种改进的K-means算法。它的主要思想是先选取出初始聚心，然后在进行K-means聚类。那么对于初始聚心的选取分为以下几个步骤[5]：

2.1.1 选第一个聚类中心。从原数据集合D当中随机、任意的选择一个对象。

2.1.2 选取第二个聚类中心。算出该聚类中心与剩下的各个对象之间的距离，然后将这些距离进行比较，其中距离该聚类中心最远的那一个对象就是笔者要找的第二个聚类中心。

2.1.3 选取第三个聚类中心。与第二步不同的地方是接着要计算现有的两个聚类中心与剩余的对象之间的距离，并找出距离min（d1，d2）-也就是距离这两个聚类中心最小的那一个距离，之后找出基于这种距离当中最大的对象[6]。若该对象满足：max（min（di1,di2））＞t｜c2-c1｜。公式说明：d1表示的是对象与聚类中心C1的距离,d2表示的是对象与聚类中心C2的距离；t则表示的是在这个聚类算法中的检验参数，则把该对象当作第三个聚类中心。

按照这种方法依次迭代，直到无法找到满足条件：

2.2 MMKMEANS算法的并行设计

文章将在Hadoop平台实现MMKEANS算法的MapReduce化。以前面章节中对MapReduce编程框架大致的介绍为基础，这里笔者可以用两个阶段来表示MMKMEANS算法的并行化实现，在算法中的第一个阶段又分了两个MapReduce过程来实现对初始聚类中心的选择。这两个阶段的实现则需经过三个Ma⁃pReduce的过程[7]，结构框架如图 1 所示：

图1 MapReduce框架图

2.2.1 第一个过程。即MapReduce1里的map过程需要进行独立并行抽样，为了减少数据抽样带来的偏差，需要对数据进行多次抽样。因此第一步要把原数据集合进行划分，分成多个小片段，然后将这些数据片段复制到集群当中的每一个节点上，每一个节点都要独立的并行执行相关的子任务。当前MapRe⁃duce中reduce的任务数是由抽取出的样本数据所决定的。例如将样本数据任意分为m份，那么reduce的任务数则为m。当前任务中的数据并行的执行MMKEANS聚类是reduce要负责的事情，在每一个re⁃duce任务当中会有若干个待选的聚类中心产生，而每一个reduce的输出数据就是这些聚类中心。除此在之外，通过每一个reduce任务计算得到的各个聚类之间的平均距离：也是需要输出的，因为在下个过程中会用到一个半径r，在计算对象密度的时侯这个半径需要被用到。

2.2.2 第二个过程MapReduce。简单的来说就是要将第一个过程中reduce所输出的键值对进行处理，将其转变为不一样的输出类型。从全局来看，上一个过程中所输出的聚类中心有可能是相邻的，这是由于在上个reduce处理数据的过程中都是局部、独立并行执行的。然后这个reduce过程就负责将上一个reduce过程输出的若干个聚心进行汇总，邻近的聚类中心被归为一个聚类中，然后在这里只需设置一个reduce任务，用于计算新的聚类中心并输出。算法第二个阶段K-means聚类过程[8]：

①K-means聚类过程将用欧式距离来进行相似度度量，这个由一个MapReduce过程来是现实。这个过程的初始聚类中心为第一阶段中MapReduce2过程所输出的聚类中心。其中将原数据集合中的所有对象分到与其距离最近的那一个聚类当中，这一任务由map过程负责。

②该算法结束的标志是聚类的中心不再有变化。针对各个聚类计算出新的聚类中心然后将其输出，而下一次的迭代输入为则为这些新的聚类中心，这一操作是由reduce过程负责的，直到算法结束为止。

2.3 MMKEANS算法的并行实现

2.3.1 第一阶段MapReduce1过程。mapper类maxMin⁃Mapper实现：该类的功能是数据抽样，要对数据进行抽样，自然离不开map过程的参与，mapper类就是用来实现map过程的。各个map子任务的抽样计算均是独立并行的，第一步需要知道样本数，也就是在计算时map子任务所需要读取的样本数量；第二步各个节点上存储着输入的数据，以＜key,value＞对的形式存在的文件，map函数则顺序的读取数据（key为对象的ID,value则是对象的空间向量模型）。在执行当中，随机数生成器是一个重要步骤。第一步需要对所选取的对象进行计数。在概率为1的前提下，读取出前n个对象；然后从第n+1个对象起，要随机的替换掉之前读取出的n个对象之中的一个，用在n/i’概率下读取出的第n+1个对象之后的对象（i=n+1,n+2...）。其中根据概率论的原理可以知道，其实每一个对象被选取的几率是相等的为N/n’。map任务的对象数为N’。第二步则是需要把读取出的n个对象当作中间数据输出，仍然是以＜key,value＞对的形式。value仍然是对象ID和对象的空间向量模型。key是一个随机数，取值在[1,m]之间由随机数生成器生成的，m可以从配置文件中获得，代表的是执行reduce任务的数量[9]。

最终的目的是进行聚类处理，根据key把样本数据分到不同的reduce上，这些样本数据是在map过程中生成的，然后进行聚类处理。(docID，docVec)是doc⁃Vector类的数据结构。

reducer类maxMinReducer的实现：该类进行re⁃duce处理。Reduce过程把map过程当中输出的key以及与key有所关联的所有对象的迭代器当作输入数据，主要目的是为了选出若干个待选的聚类中心，这些待选的聚类中心则是从map过程中的样本数据通过聚类得到的。可以分为以下几个步骤进行聚类中心的选取[10]：

①选第一个聚类中心。从原数据集合D当中随机、任意的选择一个对象[11]。

②选取第二个聚类中心。算出该聚类中心与剩下的各个对象之间的距离，然后将这些距离进行比较，其中距离该聚类中心最远的那一个对象就是要找的第二个聚类中心。

③选取第三个聚类中心。与第二步不同的地方是接着要计算现有的两个聚类中心与剩余的对象之间的距离，并找出距离min(d1,d2)-也就是距离这两个聚类中心最小的那一个距离,之后找出基于这种距离当中最大的对象[12]。若该对象满足：max（min（d1，d2））＞t｜c2-c1｜。

公式说明：d1表示的是对象与聚类中心C1的距离,d2表示的是对象与聚类中心C2的距离；t则表示的是在这个聚类算法中的检验参数，则把该对象当作第三个聚类中心。

④按照这种方法依次迭代，直到无法找到满足条件[13]的对象结束。

要保存聚类中心之间的距离，采用的是键值对的形式，键值对分为两种类型：value为聚类中心的空间向量模型，key为对象ID；value为聚类间的平均距离，key=-1。为了达到使计算更便捷的目的，对象与各个聚类中心最小的距离用minDist表示的类去继承docVector。

2.3.2 第二个阶段MapReduce过程。mapper类kmeans⁃Mapper的实现：这个类主要是对map过程的实现，输入的数据为原数据集合，然后其初始的聚类中心为上一个过程的输出结果或者是上次迭代所产生的聚类中心[14]，valuer仍然是对象的空间向量模型，key是对象的ID。map过程主要是将对象划分到与其距离最近的那一个聚类当中，输出结果键值对中的key代表的是聚类的ID标识，valu则是clusterTool对象。为了使计算更加便捷，因此设置了两个类，一个是cluster，另一个是clusterTool。K-means算法迭代产生的聚类中心的信息存储在clusterList中，setup函数则是用来获取这些信息的，初始聚类中心的信息可以通过第一次迭代得到，这个初始聚类中心的信息是由上一过程中产生[10]。

combiner类kmeansCombiner的实现：在本地中具有一样的key的中间数据可以利用算法结合combine过程将它们进行合并，这样可以使map过程中存储在各个节点的本地磁盘中的中间数据的网络通信开销得以减小，节点之间网络开销也得到有效的减少。这个类用于combine过程的实现，并且将本地节点同属与一个聚类对象clusterTool的信息进行归并[15]。本地节点在map过程输出的key和关联到这个key的相关的value迭代器是它的输入，在combine过程后所得到的键值对当中，value是clusterTool类的对象，而key表示的是聚类ID标识[11]。

reducer类kmeansReducer的实现：这个类用于reduce过程的实现。其中各个节点的key和与该key有所关联的value迭代器都是这个过程接收的数据。各个节点具有相同key的数据会被归类到一起，同时同属于一个对象的clusterTool类的信息也会被归并，最后决定是否要继续迭代则需要更新各个聚类中心以及聚类半径，以此来判断结果是否收敛，若收敛则停止迭代，反之；这些是由reduce过程负责的。最后value为新的聚类，聚类的ID标识用key表示。

在第二个阶段中进行多次的迭代，聚类过程的收敛速度同样可以是快速的，这是因为在初始聚类的时候，就会先经过一系列的处理。在聚类收敛之后并且我们已经获得了各个聚类的中心，还需要为最终得到的每一个聚类分配对象，这些对象就是原数据集中的各个对象，因此这就需要再执行一次MapReduce过程。其中第二个过程当中的map处理过程和在最后MapReduce的map过程中是一样的；相异之处在于最后各个聚类会涵盖所有的对象，但是reduce过程可以使用缺省的方式，而不需要在重新定义reduce函数；除此之外reduce过程也不必再次的更新各个聚类的中心。

3 实验分析

研究中选取特定研究区(西藏那曲地区)的植被评价遥感影像数据。通过编写程序获取大量随机采样数据（每次实验5000-1000条），如图2。

图2 研究区空间数据采样

通过随机采样点获取的部分实验数据如图3所示：

图3 原始空间数据片段

这些空间数据包括三条属性：精度、纬度、植被评价值，经过整理构成D（经纬度，评价值）的二元组数据[16]。通过编写程序对二元组数据集中的平均值为零，以及超出评价值范围的异常点进行清理，然后通过公式以及通过聚类算法，对所处不同经纬度的植被评价值进行分类，可以推测研究区域的地形变化，比如文章研究数据中聚类的信息体现了所处区域的坡面、坡度和坡向的总体分布情况。通过聚类分析以及对每个像元进行对比分析，发现植被评价值的聚类结果与坡度和坡向不存在明显的关联度，与DEM的高程数据存在明显的函数关系，如图4。

图4 聚类分析结果

4 结论

文章研究了空间数据聚类分析的一些算法，选择MMKEANS算法在Hadoop框架上进行实验，对实验结果进行了分析。由于空间数据具有类型多、数据量大并且复杂的特点，这无疑加大了从空间数据当中获得信息的难度，相较于传统的关系数据库，空间数据挖掘研究还有待完善，许多的方法和理论需要深入的研究，主要包括：对于多源空间数据的预处理。其中影像数据、数字线数据都是属于空间数据的，并且因多源空间数据本身就十分复杂，在加上对多源空间数据的收集及其不易，因此像一些噪声数据、空缺值以及不一致的空间数据或多或少的都会被收集到。这也就是为什么要对多源空间数据进行预处理的原因，这一过程是极其重要的；提高空间数据挖掘算法的效率以及对空间数据挖掘算法研究，其中空间数据挖掘的研究焦点之一就是空间同位算法；网络环境下对空间数据的挖掘、遥感图像数据库的数据挖掘、多分辨率以及多层次数据挖掘等，选择改进的K-means算法-MMKMEANS算法在Hadoop平台进行并行化实现研究。实验证明基于Hadoop平台的最大最小K-means算法优于传统的K-means算法，其时间复杂度以及处理数据的精度都提高了，对于挖掘实际应用中空间数据的有效信息更有利。