目    录

1 课题背景与研究意义 2

2 国内外发展及相关技术分析 3

2.1 地理位置分析研究现状 3

2.2 聚类分析研究现状 3

2.1.1 划分聚类算法  3

2.1.2 层次聚类算法 4

2.1.3 密度聚类算法 4

2.1.3 网格聚类算法 4

2.2 遗传算法发展现状 5

2.3 Hadoop 平台国内外发展现状 6

3 研究内容与手段 9

3.1 遗传算法优化DBSCAN 9

3.1.1 DBSCAN 算法的基本思想 9

3.1.2 遗传算法思想 10

3.1.3 优化方法 11

3.2 改进后的DBSCAN 算法 MapReduce 化 12

3.3 HDFS 架构 13

3.3.1 Hadoop 中 HDFS 和 MapReduce 架构 13

3.3.2设计目标 15

4 课题难点与拟采用的解决方案 16

4.1 课题难点 16

4.2 拟采用的解决方案 16

5 实验条件 17

6 计划进度安排 17

参考文献 17

1 课题背景与研究意义

随着以互联网为核心的科技技术的发展与普及，信息技术已经渗透到社会生活中的各个层面。人们使用网络为生活提供便利，网络也从各个角度改变着人们的生活、工作、甚至思维。在移动互联时代的不断深入发展，包括智能手机等在内的移动终端设备获得流行已经是重要的趋势，截止2018年6月，我国网民手机上网规模已达7.88亿，网民通过手机接入互联网的比例高达98.3%[1]。同时，手机用户的分布非常广泛，它的每个时刻的位置信息很客观准确，因此，手机的位置信息有着很大的利用价值。近年来，由于地理位置的获取和无线通信技术的发展，已经使基于位置的网络服务成为可能[2]。在这样的服务中，用户可以容易地共享他们在真实物理世界的位置，以及在这个位置中想要表达的事情。

面对这些海量的手机定位信息，如果仅靠人工手动分析，不仅会消耗大量人力物力，且工作效率低，对时效性要求高的数据处理完之后就已经失去意义，对于海量数据单机根本无法处理[3]。采用本文技术对环境举报者定位的信息进行分析，得到精确的分析结果，也是研究热点。

地理位置信息研究意义在于以下几点：对于国家政府管理部门，一方面，积极推动政府管理力度，有助于塑造政府形象，营造良好的公共管理环境；另一方面，如果对这些举报信息处理不当，会为政府管理带来负面影响，政府与民众之间容易引发矛盾，不利于维护公共秩序；对于企业，通过分析网民举报定位的信息可以得知自己企业所在地区的环境变化，对自己的企业进行相关排查并协助环境管理相关部门制定预防性管理事件发生；对于广大网民，举报地理位置分析可以使广大用户更清楚的了解自己身边的环境问题，追踪自己关注的地区的环境问题。

本文主要的研究问题是基于12369环保举报中举报人所在位置信息通过采集、处理，通过对大数据的精确性和快速性的问题做了充分的研究，对现有的算法或者方法的缺点进行了改进，将采用 Hadoop 平台减少应用程序延迟，有效的提高数据处理速度，取代了传统的聚类分析，提高了效率和精准度。

2 国内外发展及相关技术分析

2.1 地理位置分析研究现状

随着移动通信技术的发展，手机成为人们生活必不可少的工具。位置是人日常生活最为重要的信息之一。手机定位信息客观反映了用户的现实行为，因此位置信息可支持多种应用场景。随着互联网的发展，基于地理位置的社交网络（Location-Based Social Network，LBSN）的覆盖范围越来越广，如微信定位、发现附近好友服务等[4]。LBSN 创造了一种基于用户地理位置的线上交互方式。它通过地理位置信息将虚拟世界和现实世界连接起来。

国内外学者对地理位置的相关研究，包括通过数学模型检测用户行为轨迹中的重要地理位置，从而总结用户的行为规律；从地理位置角度分析用户之间的相似度，建立多层次的相似度模型；通过地理位置数据的分析，研究用户的行为和偏好，并对未来的行为进行预测；基于 LBSN 的数据，建立用户相似度计算模型，发现用户可能的好友和可能偏好的地理位置，从而进行好友推荐和位置推荐；使用 Louvain 算法进行社区划分，提高好友预测和链接预测的准确率；基于用户通过手机软件进行签到的数据，建立主题挖掘模型，对签到的主题信息进行充分挖掘；从垂直距离、平行距离、角度距离三个方面计算用户运动轨迹的相似度。在该领域，从早期的与基于内容的推荐方法的结合，到后来与社交网络平台的结合，再到后来结合复杂的情景信息进行信息推荐，广泛地应用于各个领域，并且将复杂的情景信息进行综合考虑是当前的热点和未来的发展趋势[5]。

2.2 聚类分析研究现状

聚类算法按照基本的划分可分为以下六类：划分聚类，层次聚类，密度聚类，网格聚类，模型聚类，图聚类等[6]。在实际聚类分析应用中，不同的场景合适的聚类算法需求各不相同，主要根据数据的类型及结构，分析数据的目标要求等来选取其相应的算法。

2.1.1 划分聚类算法 

划分方法是将分类的数据对象集合分成若干个数据区域，每个数据区域对应于一种聚簇。满足划分方法的聚簇必须符合下面的几个条件：每个类簇不能为空值，也就是说最少也要包括一个数据对象，且每个数据对象的所属簇类别是独占式的，它只能属于一个簇中[7]。首先，需要将数据集划分为几堆，然后挑选每个分类的中心点作为初始点，最后利用启发式的自定义算法进行最终的数据迭代分析与计算。直到符合最终的算法终止条件，完成最终数据划分。说到迭代计算，就是先根据初始中心点计算出初始的划分类，由于不满足终止条件，必须重新计算中心点然后重复前一次计算，就这样通过数据集点在聚类间的移动最终得到划分结果[8]。划分算法一般都会有一个准则，这个准则就是：同一个聚簇放入的是很相似的数据集的点，差别较大的数据要放在不同的聚簇中。判断划分质量的方法也有一定的依据准则，比如误差平方和以及加权平均平方距离和等。像  K-means 算法，K-Medoid 算法都属于划分聚类算法[9]。

2.1.2 层次聚类算法  

层次聚类算法需要一个树型的结构来存储数据集的对象，并按照树型的方式组织数据的生成以及重构。对于层次聚类的操作和平衡树的操作很类似，平衡树的操作主要是插入和平衡调整，层次聚类需要凝聚操作，将近似的数据集点凝聚到一起，第二个就是当满足某一条件的时候就会将数据聚簇裂变，相当于树的节点调整[10]。也需要经过多次调整最终将数据集分别分到符合要求的簇内。这个过程会多次执行直到所有数据对象集合都在同一个类别里或符合指定的条件。

2.1.3 密度聚类算法

密度聚类算法是以一个核心点在密度可达范围内的数据都属于一个聚类，密度可达是一个点在聚类中全部点的邻域内。当相邻范围内的数据点密度值大于给定阈值时，则将此点放到另一个聚簇中，而且必须保证每个聚类中至少含有一定数目的数据点。这种聚类方法也可以过滤噪声点及发现任意形状的聚簇，这也是密度聚类算法的一大特色[11]。基于密度的聚类是根据样本的密度分布来进行聚类。通常情况下，密度聚类从样本密度的角度出来，来考查样本之间的可连接性，并基于可连接样本不断扩展聚类簇，以获得最终的聚类结果。典型的算法包含 DBSCAN 算法和 DESCAN 算法[12]。

2.1.3 网格聚类算法

聚类算法在数据规模逐渐增加的情况下处理数据受到了很大的限制，由于分布式计算框架的出现，因此也为分析处理大数据的计算带来了非常好的解决方案。聚类分析的算法运用在 Map Reduce 上的分析研究也逐渐增加，有些文献在此基础上就提出分析和挖掘增量式大规模数据的处理方法，并实现了一种网格化聚类算法来解决这个已知的问题[13]。

2.2 遗传算法发展现状

遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生。他们受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法[14]。1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念[15]。1975年，De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989年，Goldberg出版了《Genetic Algorithm in Search，Optimization and Machine Learning》一书，系统地总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理及其应用[16]。1991年，David出版了《Handbook of Genetic Algorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming，简称GP)的概念。在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Gusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell(鲍威尔)的增音机设计所用的时间要少(功能评估)。Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案[17]。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。

从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。

近些年来，国内外很多学者在遗传算法的编码表示、适应度函数、遗传算子、参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研究和改进。还有很多学者将遗传算法和其他只能算法结合，进一步提高局部搜索能力。在遗传算法的应用上也有很多改进[18]。由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点，使得遗传算法广泛地应用于计算机科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领域[19]。针对遗传算法的一些问题，还有一些问题需要进一步的探究，将大大促进遗传算法理论和应用的发展，遗传算法必将在智能计算领域中展现出更加光明的前景。

2.3 Hadoop 平台国内外发展现状

Hadoop 是 Apache 软件基金会旗下的一个开源分布式计算平台。以 Hadoop 分布式文件系统(HDFS，Hadoop Distributed File system)和 Map Reduce(Google Map Reduce 的开源实现)为核心的 Hadoop 为用户提供了系统底层细节透明的分布式基础架构。HDFS 的高容错性、高伸缩性等优点允许用户将 Hadoop 部署在低廉的硬件上，形成分布式系统；Map Reduce 分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并行应用程序[20]。所以用户可以利用 Hadoop 轻松地组织计算机资源，从而搭建自己的分布式计算平台，并且可以充分利用集群的计算和存储能力，完成海量数据的处理。

Google 公司早期时候为了快速捕获由用户使用搜索引擎所产生的大量网页数据并进行及时处理，优化引擎搜索速度，设计发明了 GFS 文件系统和 MapReduce 并行计算框架。结合 Google 的相关技术，开源项目 Nutch 的创始人 Cutting Doug 设计了基于 Java语言的 Hadoop 平台系统的初级版本，其中包括两大模块[21]。一个是 HDFS 分布式文件系统，专门用来存储和管理数据记录；另一个是 MapReduce 并行计算框架，主要任务是对输入的数据样本进行统计计算。后来，随着 Hadoop 版本不断地优化升级，它已经发展成为一个以 HDFS 和 Map Reduce 为核心的、包含 Zookeeper 分布式协调服务框架、Hive 分布式数据仓库、 HBase 分布式数据库等多个组件构成的大数据处理体系。如图3-1 展示了 Hadoop 基本生态系统。

图2-1 Hadoop 基本生态系统

Hadoop 有集群完全分布式、单机伪分布式和单机方式三种不同的部署方式。单机方式是在一台 PC 机上安装运行 Hadoop 平台，该 PC 机是 Linux 系统或 Windows 均可，单机方式多被程序员用来进行程序的编写调试。单机伪分布式是运行在一台安装虚拟Linux 系统的 PC 机上，该 PC 机是 Linux 系统或 Windows 均可，分别由不同的 Java 进程模拟伪分布运行环境中的各个节点[22]。集群完全分布式是在集群环境下安装运行Hadoop程序，集群中的每个节点可以 Linux 系统或 Windows 下虚拟机实现操作。

现代社会的信息量增长速度极快，这些信息里又积累着大量的数据，其中包括个人数据和工业数据。预计到2020年，每年产生的数字信息将会有超过 1/3 的内容驻留在云平台中或借助云平台处理[23]。同时需要对这些数据进行分析和处理，以获取更多有价值的信息。为了高效地存储和管理这些数据，这时可以选用 Hadoop 系统进行数据分析，它在处理这类问题时，采用了分布式存储方式，提高了读写速度，并扩大了存储容量。采用Map Reduce来整合分布式文件系统上的数据，可保证分析和处理数据的高效[24]。与此同时，Hadoop 还采用存储冗余数据的方式保证了数据的安全性。

Hadoop中HDFS的高容错特性，以及它是基于Java语言开发的，这使得Hadoop可以部署在低廉的计算机集群中，同时不限于某个操作系统。Hadoop 中 HDFS 的数据管理能力，Map Reduce 处理任务时的高效率，以及它的开源特性，使其在同类的分布式系统中大放异彩，并在众多行业和科研领域中被广泛采用[25]。

3 研究内容与手段

近些年，虽然云计算相关的资料很多，关于云计算所做的研究也成为国内外的热点。本课题提出应用手机定位的地理信息进行分析，由于手机定位未开启时获取的信息会出现偏差，严重的甚至还会定位到国外或者山中海里等错误位置，此时使用传统的聚类算法处理数据，会严重影响分析结果的准确性。

本课题的研究重点就是将经典的DBSCAN聚类算法通过遗传算法进行改进，为实现地理位置信息的分析提出了一种新的尝试和分析方法。首先将获取的地理位置数据通过遗传算法改进DBSCAN算法中的两个参数 Eps 和MinPts 进行优化，其次利用云计算平台 Hadoop 框架对改进后的算法 Map Reduce 化，将算法分布到集群节点中，通过并行运算来缓解传统的单节点运算所造成的问题延迟问题。

3.1 遗传算法优化DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 是一种将数据对象密度作为相似性指标进行空间聚类的方法，又称为具有噪声的基于密度的聚类方法[26]。作为一种典型的空间聚类分析算法，对空间球状类型数据和非球状数据类型都有良好的支持，同时还能够过滤孤立噪声点。

3.1.1 DBSCAN 算法的基本思想

DBSCAN 算法是一种简单、有效的基于密度的聚类算法，该算法可以过滤密度较低的样本点，发现密度较高样本点区域，可以快速发现任意形状的类。基本思想是:对于一个类中的每个样本，在其给定半径的邻域中包含的样本数不能少于某个给定的值。

DBSCAN 算法涉及到几个重要概念：

Eps 邻域：对于任意点 p，以 p 为中心，Eps 为半径的区域构成 p 点的 Eps 邻域。

核心点：对于任意点，如果该点的 Eps 邻域内的点个数超过给定的阈值 MinPts，则该点为核心点。

边界点：空间中任意点，本身不是核心点，但是落在某个核心点的 Eps 邻域内，该点被称为边界点。边界点可能落在多个核心点的邻域内。

直接密度可达：对于样本集合 D，如果样本点 q在 p 的 Eps 邻域内，且 p 为核心点，那么样本点 q 从p 直接密度可达。

密度可达：对于样本集合 D，给定一串样本点p1，p2……pn，p = p1，q = pn，如果 pi 从 pi - 1 直接密度可达，则 q 从 p 密度可达。密度可达是直接密度可达的一个扩展，密度可达是可以传递的，但密度可达不对称。

密度相连：对于样本集合 D 中的任意一点 O，若存在点 P 到 O 密度可达，并且点 q 到 O 密度可达，那么 q 到 p 密度相连。密度相连是一个对称关系。

噪声点：既不是核心点也不是边界点的任何点。

DBSCAN 发现类的过程如下： step1，确定算法运行所需的两个参数：Eps 和 MinPts；step2，从样本集 D 中选取任意一个样本点 p，判断其 Eps 邻域内点的数目，如果点数大于或等于参数 MinPts，则 p 为核心点；step3，如果 p 为核心点，构建以 p 为中心的簇，依次将 p 的 Eps 邻域内的各点标记为与 p 相同的类标识。如果该邻域内的点 q 也为核心点，那么q 是 p 的密度可达点，将点 q 及其 Eps 邻域内的点也标记为 p 的类 p 的 E 标识；如果 q 不为核心点，则直接将其标记为 p 的类标识。如果 p 为边界点，则p 的 Eps 邻域包含点数小于参数 MinPts，没有点从 p密度可达，则 p 标记为噪声点。step4，从样本集 D中选择下一个样本点，重复进行 step2、step3，直到样本集 D 中没有未遍历的点，聚类过程结束。在数据空间中，存在一个边界点的邻域内可能包含多个核心点，这些核心点可能属于不同的簇。DBSCAN 算法没有对这样的边界点归属问题进行进一步甄别，而采取简单的“谁发现归谁所有的策略”。为了提高聚类精度，可以使用基于距离的方法处理边界点，将边界点划入离它距离最近的核心点所属类中。

DBSCAN 算法的思路是通过对样本集 D 中每个点 Eps 邻域来判断其是否为核心点，进而决定如何进行簇扩展。该算法中对每个样本点进行计算，计算每个点的时间复杂度为 O(n)，因此，算法的时间复杂度为 O(n2)。随着 n 的数量级增大，串行DBSCAN 算法的运行时间也增大，因此对于串行DBSCAN 算法不适合大数据量的环境。而采用并行化处理方式可以提高算法执效率。可以对样本集 D均分为 q 个子样本集，对每个 q 进行独立局部 DBSCAN 聚类，然后通过通信输出全局聚类结果。

3.1.2 遗传算法思想

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成[27]。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度(fitness)大小选择(selection)个体，并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation)，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding)，可以作为问题近似最优解。

遗传算法中交叉算子是最重要的算子，决定着遗传算法的全局收敛性。交叉算子设计最重要的标准是子代继承父代优良特征和子代的可行性。在深入分析job-shop调度问题的基础上，提出了一种基于工序编码的POX方法，将其与其他基于工序编码的交叉进行比较，证明了该交叉方法解决job-shop调度问题的有效性。同时，为解决传统遗传算法在求解job-shop调度问题的早熟收敛，同时还设计了一种改进的子代交替模式遗传算法，明显加快了遗传算法收敛的速度，此原理同样适用于其他组合优化问题。

3.1.3 优化方法

首先，该算法对原数据集进行采样得到采样集。在处理大容量数据集时，数据采样是一种常见的减少计算量的方法。它在所使用的算法具有较的时间复杂性时尤其有效。接着，我们的方法将在采样集上利用遗传算法对于 DBSCAN 算法的两个参数 Eps 和MinPts 进行优化。遗传算法是一种有效的最优搜索技术，在许多领域都得到了广泛的应用。它能在没有任何额外知识的情况下解决许多多维度非线性优化问题。我们的方法把 Eps 和MinPts 的所有可能值作为遗传算法的解空间，将 DBSCAN 算法聚类结果的闵科夫斯基评价作为遗传算法的适应度函数。

闵可夫斯基评价通过计算分类结果 U 和 V 的同表象矩阵CU 和CV 来评价分类效果。一般 U 和 V 中，有一个是由数据集类标签给出的标准分类结果。同表象矩阵是一个二元矩阵，如果数据点 i 和 j 在同一个簇中，则CU(i，j) = 1 ，反之CU(i，j) = 0 。闵可夫斯基评价的定义为：

                            (1)

该值在 [ 0，+∞) 范围内变化，取值越小说明实际聚类结果与标准结果差异越小。

考虑到 Eps 是实数而 MinPts 是自然数，我们对 Eps 采用实数编码，而对 MinPts 使用二进制编码。因此，二者的交叉算子和变异算子都会有不同。在这个步骤中，合适的 Eps 和MinPts 将能够被遗传算法找到。

最后，在采样集上得到的 Eps 和 MinPts 会根据采样率进行一定的处理，使之能够适用于原数据集。之后，DBSCAN 算法将采用新得到的参数对原数据集进行聚类，以期得到更好的聚类效果。

3.2 改进后的DBSCAN 算法 MapReduce 化

Map Reduce 是一种高效的分布式编程模型，也是一种用于处理和生成大规模数据集的实现方式，它将数据处理分为 Map 和 Reduce 两个阶段。

(1)  Map过程

Map过程处理输入的 < key，value> 对，产生一些临时中间结果，以 <key，value> 对方式输出；Reduce 过程合并临时< key，value> 对，集中具有相同 key 值的 value 部分，最后输出结果。所以要实现 DBSCAN 算法的并行化，需要对 Map 和 Reduce 过程进行设计。各节点将收到的子样本集归并为 <key，value> 对，作为 Map 函数的输入。点标识 pid 作为 key 值，向量(coretag，usedtag，cid，xi) 作为 value 值，其中 coretag 表示样本点是否是核心点，usedtag 表示样本点是否有过类标识，cid 表示类标识，xi 表示样本点各维坐标组成的字符串。输出结果为 <key1，value1 > ，key1 存放点标识 pid，value1 存放类标识cid。

(2)  Combine 过程

Combine 函数将 Map 函数的输出作为输入，将 pid 值相同的点归为一组，存储为中间键值对 <pid，list(cid)>，利用分区函数 hash mod R 将中间键值对分成 R 个不同的分区，最后输出 < key2，value2> 对，其中 key2 值为点标识 pid， value2 值为具有相同 pid 的样本序列。

(3) Reduce 过程

执行 Reduce 任务的处理机收到 Combine 过程分配给自己的那部分数据 < pid，list(cid)> 后，首先调用层次合并函数 Hierarchical Merge ( )，对包含一个或多个共享核心点的这些类合并为一类，并赋予统一的类标识。如果其公共点均为共享边界点，对比该公共点与其 Eps 邻域内核心点的距离，将其划入距离最近的核心点所在类中。直到所有点都具有唯一的类标识。

3.3 HDFS 架构

HDFS 分布式文件系统具有高容错性、高并发性、高可用性和可扩展性等特点。它实现数据的存储管理同样是在本地服务器上进行的，与单机模式下的数据存储不同， HDFS 利用本地的若干台计算机，借助本区域网络使各机器服务点通过通信建立连接，组织成一个能为高层大数据处理应用程序提供服务的完整分布式文件管理系统。大规模 GB 级到 TB 级别的数据，无论是从存储容量还是传输速度进行考虑，仅仅依靠集中式的物理服务器存储是不现实的[28]。大数据的存储需使用多个服务器节点，几十台、几百台甚至更多，必须使用分布式文件系统来对这些节点的数据存储进行统一管理。

3.3.1 Hadoop 中 HDFS 和 MapReduce 架构

HDFS 作为 Hadoop 平台中最常用的分布式文件系统不仅能存储 TB 级别的单个文件，还支持在一个文件系统中存储数千万量级的文件。Hadoop 中 HDFS 和 MapReduce 架构如图 3-1 所示。

图 3-1 Hadoop 中 HDFS 和 MapReduce 架构

目前，普遍应用的 Hadoop 有两个版本，Hadoop1 和 Hadoop2。在 Hadoop1中，一个 HDFS 文件系统中包含一个主控节点 NameNode和一组从节点 DataNode 。Hadoop2 中可以有一个或者多个新的 NameNode节点。 NameNode主要负责执行文件操作，并将数据块分配给 DataNode ，建立 DataNode 和数据块的对应关系，NameNode含有命名空间、数据块与文件名的映射表、数据块副本位置信息等。DataNode 用于存储文件的数据块，并处理数据读取请求和 NameNode发来的多个指令。

HDFS 作为一个分布式文件系统，虽然还是建立在一组分布式本地服务器节点之上的文件系统，但是不同于单机状态下的本地文件系统。它们的数据文件存储机制、读写过程都有很大不同。 HDFS 的文件访问过程分为以下几点：

(1) 用户的应用程序如果要访问 HDFS 文件系统。首先，应用程序要和文件系统的client 进行交互，请求访问文件。client 接收到信息之后，会将文件名提交给 NameNode。虽然客户端 client 不是 HDFS系统的组成部分，但常规部署的HDFS都会提供 client。

(2) 在主控节点 NameNode接收到文件名之后，根据本身存储的元数据信息，查找文件目录，找到文件对应的数据块，然后依据数据块在 DataNode 上的位置，得到文件的地址信息，反馈给 client，进而发送给用户。

(3) 当 HDFS客户端接收到这些 DataNode 地址之后，客户端与 DataNode 并行地建立连接后进行数据传输操作，并提交操作结果日志。

然而，数据块的存储位置信息通常是从 NameNode上存储的元数据目录处获得，再通过访问对应位置信息的数据节点以获取数据，而不是通过 NameNode来传送文件数据流。这样操作一方面不仅大大降低了 NameNode节点的承载压力，以免出现节点访问瓶颈；另一方面通过在不同的 DataNode 节点同时访问一个文件数据来提高数据读写速度。

3.3.2设计目标

根据 HDFS 在 Hadoop 平台上的使用，提出以下设计目标：

(1) 硬件错误处理：一般情况下都会出现硬件异常，HDFS 是有数以千计的单节点组成，其中每一个节点都有可能出现问题，所以错误的监控和迅速自动恢复是 HDFS 最关键的目标点。

(2) 流式访问：HDFS 与其他应用不同之处在于它是流式的访问文件系统，因为无需考虑与用户交互，所以一般是处理批量数据。所以实现数据的高吞吐量比数据的低延迟更关键。

(3) 大规模数据集：在 HDFS 上运行的程序一般都要处理大小在 G 字节甚至 T 字节，数据规模很大，所以 HDFS 要能够存储大文件，应该具有高的传输带宽，在集群中可以有数百个节点。

(4) 简单一致性：“一次写多次读”是 HDFS 访问文件时要满足的条件之一。即文件在创建、输入和关闭后就不能再改变数据了。这样就使得数据一致性变得简单，同时使得数据访问时的高吞吐率也成为可能。

(5) 移动计算高效性：一个程序的的计算，当所要处理的数据离算法越近的时候，计算就越高效，尤其是当数据为海量级别的时候。将计算的程序移动每个节点的数据的附近，比移动数据到算法要更高效。HDFS 就是这样的运行模式。

4 课题难点与拟采用的解决方案

4.1 课题难点

一个有效的采样意指采样集基本能够代表原数据集的所有信息；对于聚类算法而言，这要求对于原数据集和采样集的聚类结果基本相同。这就需要对于采样率和采样方法的适当选择。本实验选取12369环保举报中的经纬度作为分析数据，根据实际情况有可能出现部分地区密集部分地区分散的情况，若参数选取误差较大，会造成分析结果不准确。

4.2 拟采用的解决方案

为了确保聚类有效性，采样集应该能够有效地表达原数据集中的所有信息。如果采样集过小，则在采样集之上产生的聚类结果可能是无效的。采样集的最小容量可由切尔诺夫边界确定：

      (2)

其中 N 是原数据集的容量， 是数据集中最小的簇的容量。该方程意指，当采样集的容量是  时，原数据集中最小的簇中至少有 个数据点被选入采样集的概率不小于。

简单随机抽样是一种最简单的抽样方式，它使得每个数据具有相同的概率被选入采样集。当对于数据集没有预先知识或对其无法进行任何预先处理的时候，简单随进抽样是一个很常用的方法。在数据集是由几种不同类型的数据组成，且各类数据的数量差距很大的时候，分层抽样是一个有效的选择。由于在我们的实验中，对数据集的预先知识和预先处理都是很难得到的，故选择简单随机抽样。

5 实验条件

课题计划在Linux系统平台下，创建三台虚拟机搭建 Hadoop 平台，系统硬件平台为兼容型计算机，初步拟定计算机配置情况为core i5 CPU、MX250 2G独显、20G 内存、512G 固态硬盘。

6 计划进度安排

参考文献

[1] 洪菁. 大数据时代的思维特点研究[J]. 计算机科学, 2016(z2).

[2] 第 41 次中国互联网络发展状况统计报告[R], 中国互联网络信息中心(CNNIC), 2018-1.

[3] Wigan M R , Clarke R . Big Data[J]. 2013.

[4] 介晓伟. 基于地理位置的社交网络中的区域推荐[D]. 厦门大学, 2017.

[5] 李蕴怡. 基于地理位置数据挖掘的用户行为分析[J]. 通信技术, 2019(6).

[6] 张  伟. MapReduce 聚类方法的研究与应用[D]. 中国民航大学, 2018.

[7] Liu X , Yang Q , He L . A novel DBSCAN with entropy and probability for mixed data[J]. Cluster Computing, 2017, 20(3):1-11.

[8] 国  珉. 基于 Spark 平台的 DBSCAN 文本聚类研究[D]. 北京工业大学, 2018.

[9] Gan J , Tao Y . DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation.[J]. 2015.

[10] 王翠茹, 朵春红. 一种改进的基于密度的DBSCAN聚类算法[J]. 广西师范大学学报(自然科学版), 2007(04):112-115.

[11] 邓青, 杨宁. 云环境下并行 DBSCAN 聚类算法研究[J]. 山西电子技术, 2017:90.

[12] Shi C , Cai Y , Fu D , et al. A link clustering based overlapping community detection algorithm[J]. Data & Knowledge Engineering, 2013, 87(Complete):394-404.ju

[13] 伍育红. 聚类算法综述[J]. 计算机科学, 2015(S1):500-508+533.

[14] HANDL J, KNOWLES J, KELL D B. Computation cluster validation in post-genomic data analysis [J]. Bioinformatics, 2105, 21(15): 3201-3212.

[15] 冯智莉, 易国洪, 李普山. 并行化遗传算法研究综述[J]. 计算机应用与软件, 2018, 35(11):7-13+86.

[16] 曲志坚, 张先伟, 曹雁锋, 刘晓红. 基于自适应机制的遗传算法研究[J]. 计算机应用研究, 2015(11):3222-3225.

[17] 李岩, 袁弘宇, 于佳乔. 遗传算法在优化问题中的应用综述[J]. 山东工业技术, 2019(12):242-243.

[18] CELIK M, DADASER-CELIK F, DOKUZ A S. Anomaly Detection in Temperature Data Using DBSCAN Algorithm, 2011 International Symposium on Innovations in Intelligent Systems and Applications [C], Istanbul: Dogus

[19] 栗盼. 混合遗传算法综述[J]. 电子世界, 2015, No.475(13):75-76+80.

[20] 吕  涛. 基于 Hadoop 平台的并行决策树算法研究[D]. 西安科技大学, 2018.

[21] 王雅光. 基于 Hadoop 平台的 DBSCAN 算法应用研究[D]. 广东工业大学, 2013.

[22] 梅松. 基于Hadoop的分布式文件系统研究[J]. 数字化用户, 2017, 23(44).

[23] O’Driscoll A, Daugelaite J, Sleator R D. ‘Big data’, Hadoop and cloud computing in genomics[J]. 2013, 46(5):774-781.

[24] 李元亨, 邹学玉. Hadoop综述[J]. 电脑知识与技术, 2018(9).

[25] Ashish Thusoo, Joydeep Sen Sarma, Namit Jain,等. Hive – A Petabyte Scale Data Warehouse Using Hadoop[J].

[26] HUANG P, CHOU W, LIN W. Using SOM and DBSCAN-based models for landslide hazard and spatial correlations analysis: A case study in central Taiwan, 20th International Conference on Geoinformatics [C], Hong Kong

[27] 朱会霞, 李微微, 李彤煜. 区间自适应遗传算法优化无约束非线性规划问题[J]. 数学的实践与认识, 2019(4).

[28] M. Maghsoudloo, N. Khoshavi. Elastic HDFS: interconnected distributed architecture for availability–scalability enhancement of large-scale cloud storages[J]. The Journal of Supercomputing, 2019(1).