当前位置:首页 > 论文帮手>>文章详情

基于Hadoop的物流历史数据聚类挖掘研究

来源:论文帮手 作者: 发布日期:2017-12-09 11:41:01

  

基于Hadoop的物流历史数据聚类挖掘研究
 
 
摘  要
随着电商、物联网、云计算等一系列新型技术的发展与应用,如今的物流行业的数据增长已不再是线性的、缓慢的,它所呈现的是海量的、复杂的、实时与爆炸性的。显然,传统的单机存储和串行的数据挖掘技术已无法满足当前物流行业的大数据处理需求。Hadoop依然成为了当下社会发展的新趋势,它是一个开源的分布式平台,适用于大数据集的分布式计算。近年来,这一技术在数据挖掘领域逐渐发挥出其独特的优势。而K-means聚类算法就是一种有效的大数据挖掘算法,该算法实现简单且易于使用,但其在质心点及K值的选取上仍然存在很大的盲目性和不可预见性,经常导致聚类结果出现局部最优解,且在距离计算过程中存在着复杂的冗余计算,收敛速度慢,聚类精度低,缺乏并行性和可扩展性,大大降低了算法的运行效率。
针对传统K-means算法不足, 本课题结合了“距离三角不等式原理”和“最小最大原则”的优点,在Hadoop云计算平台上提出了一种基于双MapReduce分布式编程模型改进的Canopy-Kmeans算法,并通过社发物流公司的真实历史数据验证了本文算法的正确性。具体的研究工作如下:
首先,本文详细阐述了Hadoop生态系统,对其基本组件、构造模块以及工作机制进行了深入的剖析和研究;分析了大数据挖掘过程中标准流程;对传统k-means算法的设计思路和过程进行深入的研究,重点探讨了已有研究成果的优缺点。
其次,为了优化K值的选中问题,在Hadoop平台上基于最小最大原则对传统的Canopy算法进行了改进,成功地解决了传统Canopy算法中人为设置K值以及区域半径T1、T2的盲目性,为K-means聚类结果的准确性提供了可靠的理论依据。
再次,为了解决传统K-means算法在迭代过程中的大量冗余计算,本文基于三角不等式原理的优点,在k-means算法迭代计算之前,增加了距离筛选判定,减少大量的冗余计算;另外,为了进一步提高该算法运行效率,引入了加权聚类准则函数,并增加了算法的收敛性判定,提高了聚类的质量和收敛速度,降低了数据对象误分率。
最后,设计并实现了基于双MapReduce编程模型改进的Canopy-Kmeans算法。为了进一步验证本文算法设计的可行性,搭建了Hadoop集群环境,采用社发物流公司真实的历史数据,以寻找社发物流公司的关键客户群体为例进行了大量的实验。实验结果表明,设计的并行算法在聚类结果的准确性、加速比、扩展性等方面都有显著的提高。成功地解决了K值及Canopy中心点选中存在的问题,避免了迭代过程中冗余的距离计算,提高了原算法的收敛速度,并且数据规模越大、节点越多,改进的效果就越显著。
 
关键词:Hadoop;Canopy-Kmeans;数据挖掘;双MapReduce 
 
Research on Self-consciousness of Agents
 
Discipline: Software Engineering
Student Signature: 
Supervisor Signature: 
 
Abstract
With the development and application of a series of new technologies, such as electricity supplier, Internet of things, cloud computing, etc., the data growth of logistics industry is no longer linear and slow, and it presents a massive, complex, real-time and explosive. Clearly, the traditional stand-alone storage and serial data mining technology have been unable to meet the large data processing needs of current logistics industry. Hadoop has become a new trend of social development and it is an open source distributed platform for large data sets of distributed computing. In recent years, this technology has gradually played its unique advantages in the field of data mining. However, The K-means clustering algorithm is an effective algorithm for large data mining, the algorithm is simple and easy to implement but it still has great Blindness and predictability in the selection of K value and its centroid point. Moreover, it is easy to make the clustering results fall into the local optimum and there are a lot of redundant computations in the distance calculation. In addition, it also makes the convergence rate and the clustering accuracy slow, and the parallelism and expansibility be lack, which greatly reducing the operating efficiency of the algorithm.
According to the insufficiency of K-means algorithm and combined the advantages of “Distance Triangle Inequality Principle” and “Min-Max Principle”, this paper proposes an improved Canopy-Kmeans algorithm based on double MapReduce distributed programming model on Hadoop cloud computing platform. And it verifies the correctness of the algorithm by the real historical data of Shefa Logistics Company. The specific research is as follows:
Firstly, this paper elaborates the Hadoop ecosystem in detail, and analyzes and studies its basic components, construction modules and working mechanism. And it also analyzes the standard flow in the large data mining process. The traditional idea and process of k-means algorithm are deeply researched, and the advantages and disadvantages of the existing research results are discussed emphatically.
Secondly, in order to optimize the selection of K value, the traditional Canopy algorithm is improved on the Hadoop platform based on the min-max principle, which successfully solves the blindness of artificial located K value in the traditional Canopy algorithm and the area radius T1 and T2, and provides a reliable theoretical basis for K-means clustering results.
Thirdly, in order to solve the traditional redundant computation of K-means algorithm in the iterative process, based on the advantage of triangular inequality theory, this paper increases the distance selection decision and reduces the redundancy computation before the k-means algorithm is iterated. What is more, in order to make further improvement of the efficiency of the algorithm, a weighted clustering criterion function is introduced to increase the convergence judgment and improve the quality and convergence rate of clustering and reduce the misclassification rate of data objects.
Finally, an improved Canopy-Kmeans algorithm based on dual MapReduce programming model is designed and implemented. In order to validate the feasibility of this algorithm, a Hadoop cluster environment is set up, and a lot of experiments are carried out to find the key customer groups of Shefa Logistics Company by using the real historical data. The experimental results show that the designed parallel algorithm has significantly improved in the clustering results of accuracy, speedup, scalability and other aspects. It can solve the problems of K value and Canopy center point selection successfully, and avoid the redundant distance calculation in iterative process, and improve the convergence speed of the original algorithm. And the larger the data scale and the more nodes, the more remarkable effect of the improvement.
 
Key Words: Hadoop;Canopy-Kmeans;Data Mining;Double MapReduce 
目  录
1绪  论 1
1.1 问题的提出及研究意义 2
1.2 国内外研究现状 3
1.2.1 国内研究现状 3
1.2.2国外研究现状 3
1.3 本文的主要内容及结构安排 4
1.3.1 本文的主要内容 4
1.3.2 本文的结构安排 5
2相关理论研究 7
2.1 大数据概述 7
2.1.1大数据的特征 8
2.2 Hadoop生态系统 10
2.2.1 HDFS分布式文件系统 11
2.2.2 MapReduce 框架及计算模型 11
2.2.3 YARN架构 13
2.2.4 Hbase数据库 15
2.2.5 Zookeeper分布式协作服务 15
2.2.6 Sqoop 15
2.2.7 Pig 15
2.2.8 Flume工具 15
2.3 数据挖掘综述 16
2.3.1 数据挖掘方法 16
2.3.2 数据挖掘步骤 18
2.4 K-means算法理论研究 20
2.5 本章小结 22
3 基于双MapReduce改进的Canopy-Kmeans算法 23
3.1 传统的K-means算法 23
3.2原始的 Canopy-Kmeans算法 23
3.3改进的 Canopy-Kmeans算法 24
3.3.1 Canopy算法的改进 24
3.3.2 K-means算法的改进 25
3.3.3聚类函数收敛性的改进 26
3.4双MapReduce设计的Canopy-Kmeans算法 28
3.4.1基于MapReduce设计的Canopy算法 29
3.4.2基于MapReduce的K-means算法并行化设计 31
3.5算法复杂度分析 35
3.6本章小结 35
4 实验及实验分析 36
4.1 hadoop集群配置与部署 36
4.1.1网络配置 38
4.1.2安装jdk 38
4.1.3建立ssh互信 39
4.1.4 配置Hadoop 39
4.2实验数据及结果 43
4.2.1数据准备 43
4.2.2执行Canopy-Kmeans算法模型 44
4.2.3结果分析 45
4.3算法在Hadoop集群上的性能分析 46
4.3.1算法的准确性分析 46
4.3.2算法的加速比分析 48
4.3.3算法的扩展性分析 49
4.4本章小结 50
5结  论 51
参考文献 52
攻读硕士学位期间发表的论文 56
致  谢 57
学位论文知识产权声明 58
学位论文独创性声明 59
 
 
 
1绪  论
随着 “一带一路”区域经济合作战略的提出,我国交通运输线路已突破12.3万公里,跃居世界通车里程第一位,且还在持续的投入和完善中,运输成本的降低,为我国物流行业蓬勃发展和壮大带了可观的前景。另一方面,“大数据”时代已经到来,在过去的十几年中,信息技术的发展无论是在科技发展领域,还是在人们的生活方式和生活习惯上,都产生了深刻的变革和影响。尤其是随着大数据、物联网等新型技术的兴起,现在全球的数据量已呈现出爆炸式增长的趋势,将来合理地利用企业的“大数据”资源一定会给各行各业的组织、管理、营销带来便利。目前,大数据已经广泛地被越来越多的现代化企业推广应用,并为这些行业的健康持续发展提供了切实的保障和后盾。例如在金融服务行业、零销商行业、京东、淘宝、医疗服务行业、零售制造业等现代化部门。当然,物流行业也并不例外,因为其本身就是一个产生大量数据的行业。随着物联网、云计算、移动计算、无线射频技术RFID、GPS全球定位系统等技术的逐渐完善,这些新兴技术也逐渐被应用在物流行业中,极大地促进了物流企业乃至整个行业的发展和壮大。然而,现代化物流行业也存在着很多的弊端和不足之处,其集中表现在以下四个方面:
(1)我国物流成本居高不下,社会资源浪费严重,行业内分散、凌乱、缺乏统一的管理,中间环节多,信息化程度低,信息不透明严重,车货匹配效率差,部分中、小物流企业为了抢占货源,肆意压低运价,恶意竞争,导致物流市场混乱,整体利润下滑,整个行业竞争激烈,许多中、小型物流企业面临倒闭的风险;
(2)物流企业客户关系管理的理念还未得到足够的重视。现在有很多中、小型物流企业都是由以前的货运公司转型而来,但其往往只是一个名称的更改,走的还是传统的管理模式,忽略了客户关系管理的重要性。然而,随着我国“一带一路”全球化战略的提出,国外越来越多的实力较强的物流公司开始进入到我国物流运输市场领域。为我国物流企业的发展既带来了机遇,又带来了挑战。
(3)物流企业的信息技术手段落后,满足不了当前现有行业营销活动的需求。目前,虽然一些高科技信息技术也在源源不断地应用于物流企业中,但对于大多数企业来说,还是仅仅局限于对一些单个系统的开发,如物流信息管理系统、车辆调度系统等。企业的营销人员在面对纷杂的数据资料时,大多还仅停留在对信息的检索和查询上,且营销的方法也大多为传统的营销模式,以手工或半手工机械作业为主,没有充分利用其现有的数据来挖掘数据背后隐含的营销信息为物流企业的营销决策提供帮助;
(4)未能有效的细分客户群体进行有针对性的物流营销活动。由于物流行业本身属于一种新兴的服务型行业,所以其必然拥有大量的客户资源。因此,物流企业只有将自己有限的资源集中在对企业贡献最大的关键客户群体身上才是企业发展的重中之重,而在这些客户中存在着数量众多的微小型客户,物流企业如何区别客户的价值,从而采取不同的营销策略对客户进行分类就显得尤为重要。如何提高企业对信息和数据的掌控能力,提高企业对数据的使用率,将会是各个物流企业面临的难题。
综上可知,未来物流行业的发展,必将是数据的时代,谁能在数据面前获得先机,谁就能提前抢占市场,为客户提供更好的服务。在这方面国外的物流公司做的比较好,比如,物流巨头Panalpina公司为树立自己“以客户为中心”的服务理念[1],从2000年九月份开始进行机构、业务重组,形成了欧洲、亚洲、北美洲和非洲等经济发展中心,各经济发展中心的营销模式、组织机构均采取“最大程度满足客户”的需求而设立,服务周全统一,使所有客户都青睐于“Panalpina风格”的客户关系管理。英国物流公司Excel通过对货物空运中大量客户数据的收集、分析,制定出了提升空运领域便捷的物流供应链实施方案,依据物流在供应链体系中的重要度,减低物流成本,优化库存,提高了经营者在市场应变能力[2]。其对客户信息的精细化管理,经过互为供需关系服务流程,形成一个完整的物流服务供需过程,为英国的航空物流运输提供了完整的IT基础服务,并确立了自己在物流行业的优势地位。德国的物流巨头Schenker公司的客户分析已经成为其商业模式的核心,它建立了一个客户洞察团队,专门进行管理和挖掘客户数据。其发现通用汽车、福特/马自达、宝马均在该工业区设有零配件组装厂,及时调整了产业结构,将其主要用于汽车零配件的物流服务建在泰国东南部的最大工业区之间,为客户提供购销管理、组装成套、包装和其它增值服务。这一方案的及时调整,巩固了其在国际物流市场上的地位。
近来,随着我国“十三五”经济发展战略的提出,我国的物流行业又一次得到迅猛的发展,许多知名企业也纷纷加入到物流行业中来,它们的到来既发展壮大了物流企业的规模,也进一步加剧了企业之间的竞争力。另一方面随着现代网络技术的发展使得物流业的数据量也在与日俱增,企业竞争市场的焦点已经逐渐从产品性能、服务质量、品牌规格的竞争转向客户的竞争。客户就是财富、客户就是资产、客户就是价值,客户就是企业发展的动力和源泉。与客户保持一种长期的、稳定的合作关系,是企业提高市场占有率,获得最大利润额的关键。所以如何使物流企业适应当前大数据的发展,为企业尽可能地掌握客户资源,分析客户个性化需求,提供满意的客户服务,保住客户群体,将是我国物流行业迫切急需解决的一个难题。
1.1 问题的提出及研究意义
本课题研究的目的与意义在于物流企业属于服务型行业,物流企业的客户流动性比较大,且客户满意的标准不同,其更需要以客户为中心。未来在物流行业内争夺客户资源必将成为物流企业之间的主要方式。以客户为中心就成为了企业必须考虑的市场行为,也直接体现在客户的价值上。如何有效的减少客户的流失及保留有价值的客户,这将是企业最关注的问题。而针对所有客户进行全方位营销将耗费大量的人力物力,这仅仅是理论可行,其所产生的效益并不明显。尤其是中、小型物流企业在未来的激烈竞争中,如何利用为数不多的手中资源赢得尽可能多的利润,这将是企业今后发展的关键所在。在当今社会,谁充分利用了客户信息,谁能从企业大量的客户数据资源中挖掘出有意义额外知识,发现客户新的价值,并用与企业经营管理决策,谁就可以赢得市场,获得利润。但大量的客户数据资源往往会使企业陷入“信息爆炸,知识匮乏”的信息孤岛之中,除了增加数据中心的存储设备外,对数据资源的利用仍然停留在粗糙的增、删、改、查上,利用率低,很难发挥数据本身应有的商业价值和作用。
未来,针对物流历史数据的挖掘必将成为物流行业最受关注的话题之一。本文基于此提出的研究课题,将大数据挖掘技术有效的应用于物流企业中,从大量的数据中抽取有用的商业信息,对不同类型客户带给企业的利润进行深入的信息挖掘,发现物流企业中有价值的潜在客户并针对其关键客户群体进行研究分析,及时为企业经营决策提供支撑信息,实现客户价值最大化,这在当今的物流行业中必将具有非常大的研究意义与实用价值。
1.2 国内外研究现状
物流客户关系管理从1999年开始起步,经历了近几年的理念宣导、概念普及,现在处于调整期。根据赛迪顾问的调查结果,2000年的物流客户关系管理软件中国市场的销售额是0.6亿元,2001为0.9亿,增长50%,2004年达到3.06亿元,2008就表现出高速增长的劲头,销售额达到30亿元。到2015年底,只有12%的被调查企业还没有听说过客户关系管理。斯隆管理学院的海皮尔(Hippel)教授认为在产品创新过程中,对客户知识的有效管理至关重要,客户在企业发展中扮演着重要的角色。而对于大多数物流企业来说,大数据数据挖掘技都术可以有效帮助企业发现未来公司的业务发展方向,及早发现已有的事实,预测未来的结果,从而帮助企业达到增加利润、降低成本,进而可使企业在激烈的竞争中立于不败之地。因此,在国内外,物流界领先的企业也根据实际需求环境相应地提出了许多杰出的数据挖掘方案和解决策略。
1.2.1 国内研究现状  
我国对物流企业历史数据的研究目前还处于起步阶段,大多数的研究都还集中在企业客户管理基本策略、管理战略、客户保持战略等理论研究层面上。例如侯发欣等人提出的在物流企业中的客户关系管理学,重点阐述了物流企业客户关系管理学中的几项最关键技术,例如物流行业通用调度技术、物流行业大数据挖掘技术、物流成本效益具体分析技术等 [3];包玉梅等人提出了将客户关系管理学方面的内容与服务性的物流特色相结合的营销策略[4]。赵刚通过重点分析物流企业的客户行为,提出要加强物流客户群体知识管理与组织等核心技术[5]。
  1.2.2国外研究现状
国外的物流企业发展的较早与国内,所以其对物流行业的认知和研究也是最好的,
就目前来说,其对物流历史数据中的客户群体的研究大致上可以分为以下三种类型:
(1)从物流的上下游货物供应链入手,重点研究分析客户服务与上下游供应链之间的联系,以及它们的相互交叉组合的内在关系。从事这方面最关键一点就要是抓住各个供应链之间的敏捷性,供应链的敏捷性是能否迅速快捷地满足客户需求的基础,例如Perry等人就服装设计和鞋类产业与澳大利亚纺织业的供应链情况展开了研究,并建立了上下游供应链的相关的信息流处理模型,其指出了各个节点之间的供应链资源信息的共享会对整个供应链敏捷性起到非常重要的作用[6]。
(2)从物流企业的发展角度入手,着重研究了企业客户的心理特征。如Subhash等人提出的关于监控客户接受服务满意程度的模型。Stowed等人基于企业客户忠诚度三角模型,重点剖析了构建企业客户忠诚度的思路和模型,且还提出了利用企业用户忠诚度三角模型框架来强化企业客户的忠实度[7]。
(3)从物流企业客户关系管理学入手,重点探讨客户关系管理技术方案及解决措施。其技术方案的主要由数据存储系统、呼叫中心系统、数据仓库系统等构成,Panos等人利用具有丰富经验的数据仓库管理员来进行目标度量,以此来获得可靠的管理信息,为企业的决策提供切实的保障,其通过进一步的研究还分析出了产品质量内在复杂影响因素之间的关系,从而达到了精准投放生产要素来满足不同企业客户的各种需求[8]。
随着大数据时代的来临,现有的数据挖掘技术还不足以代替有经验的数据分析人员或管理人员单独存在,是一个人家交互、多次反复的过程,它得到的只是数学模型,无法直接形成企业的商业价值,而且这种模型还必须经过市场的不断检验。数据挖掘只是提供了一个比较好的工具,但不是万能的,不能单纯依靠这种技术解决所有的问题,虽然它能够在一定程度上发现一些潜在的物流客户,但是其却不能保证这些潜在的客户成为物流企业的忠实客户。例如关于啤酒尿布组合在一起销售的案例,这不仅仅是一个单纯靠一点点数据挖掘技术就能解决的问题,是将二者分开放,还是放在一起组合销售,这还需要对消费者的心理层面进行充分的研究才能做出最终的决定。齐克芒德曾指出,“优秀的企业管理者必须对企业的信息结构和心理营销理念进行系统的研究和了解,方能形成全面完整、持续可靠的客户管理观念”。因此,物流企业也必须要构建适合自己客户关系模型,只有充分将客户资源管理与数据挖掘技术相结合,才能从大量的数据中获得有利于企业发展、提高自身竞争力的信息,才能及早发现新的客户资源,保住有价值的客户群体,让已有的客户群体尽可能地创造出更多的利润。
1.3 本文的主要内容及结构安排
1.3.1 本文的主要内容
本课题根据物流行业历史数据的特点及中、小物流企业实际业务的需要,将着重对能产生价值的关键客户群体进行研究,并运用科学的方法量化分析客户的数据,以期建立全方位、多角度的关键客户群体聚类评价模型,为企业管理者在激烈的行业竞争中提供更加科学、合理的决策信息。针对以上目标,本课题在hadoop平台上设计并实现一个基于双MapReduce 编程模型改进的Canopy-Kmeans聚类挖掘算法来寻找关键客户群体评价模型。本文重点对以下四个方面进行了研究:
(1)对大数据相关技术进行了详细的的研究。学习了hadoop2.x的生态系统中的核心组件,重点研究了分布式HDFS文件系统的存储架构和MapReduce的主要编程思想以及hadoop作业的工作机制等。
(2)数据挖掘的研究。主要学习了数据处理架构中的数据挖掘技术,并对其标准挖掘流程进行阐述,深入研究了物流企业中的历史数据特点,利用已有的数据挖掘技术对原始数据进行了预处理和筛选,为本文K-means聚类挖掘算法提供数据支持。
(3)研究了传统Canopy算法和K-means算法的优缺点。为了优化K值的选中问题,利用最小最大原则对Canopy算法进行了改进,为了解决迭代过程中的冗余计算问题,利用三角不等式原理对K-means算法了改进,并增加了收敛性判断,提高了聚类的收敛速度。
(4)研究了Canopy-kmeans算法和MapReduce处理框架相结合的算法。将并行计算框架MapReduce和数据挖掘分析技术进行结合,运用大数据处理模型,结合hadoop分布式存储和计算的相关技术,针对业务的实际需求,设计并实现一个基于双MapReduce 编程模型改进的Canopy-Kmeans聚类挖掘算法来寻找关键客户群体评价模型。最后,通过多次实验分析,验证了本文算法的有效性和稳定性。
1.3.2 本文的结构安排
本文研究的课题是基于hadoop的物流历史数据的聚类挖掘研究,主要从以下五个章节进行探讨,各章节的主要内容安排如下:
第一章,绪论。首先分析了课题的研究背景、提出的意义以及国内外的研究发展现状,对当前物流行业的实际需求进行重点的分析和研究,提出了基于hadoop平台进行大数据分析的必要性。然后列举了一些数据的分析方案和系统,讨论了当前课题研究的现状,最后阐述了论文研究的重点和各章节的主要内容。
第二章,相关理论与技术。通过收集资料和大量的文献阅读,对hadoop技术、数据挖掘技术、K-means算法和数据处理模型等与本课题相关的知识进行分析和研究。
第三章,基于双MapReduce改进的Canopy-Kmeans算法。对于传统的K-means算法存在的不足和缺陷,针对实际的业务需求,本文对传统的k-means算法进行了三个方面的改进和优化,并基于双mapreduce模型设计和实现了改进的Canopy-kmeans算法,并分别针对该算法的总体架构设计和详细设计进行了说明。给出了系统各个功能模块的详细设计,包括算法的执行流程和伪代码设计过程等。
第四章,实验及实验分析。搭建hadoop实验集群,安装并配置文件和服务,利用数据挖掘的标准流程对社发物流公司的真实历史数据进行预处理和筛选。通过大量的实验,验证了本文算法的正确性和优越性,寻找到了关键客户群体,达到了预期的目标。
第五章,总结。概括总结了全文的主要工作,分析了本课题研究的不足之处和需要待完善的地方,并进一步指出了需要研究和解决的问题。
2相关理论研究
随着大数据时代的来临,数据挖掘技术日益成熟,本章首先对大数据基本理论进行了阐述,之后介绍了大数据分布式平台Haoop,分析了Hadoop生态系统的核心组件和工作机制,然后重点介绍了数据挖掘基本原理和相关的知识。最后深入研究了K-means聚类挖掘算法的发展与现状,对比分析了它们的优缺点。
2.1 大数据概述
随着大数据概念的提出,世界各国已将其视为一次新的产业革命,美国的泰晤士报及《Nature》等期刊也相继出版专刊专门用于探讨大数据给企业和国家政府带来的挑战和机遇。有专家称:“数据已经成为业务职能部门的重要生产因素,其已渗透到社会的各行各业中,与人们的生活息息相关。人们对于大数据的分析研究,必将带来新一代的经济发展浪潮”。,美联社发表文章称大数据是“未来世界各国发展的新石油”,一个国家存储和处理数据的能力必将成为一个国家综合国力的重要标志,未来对数据的控制和利用必将成为企业之间和国家之间彼此争夺的新焦点。 
大数据的快速发展浪潮已然来临。迄今为止,到底什么才是真正的大数据呢,目前还没有公认的说法。从宏观哲学的思维来讲,大数据是连接人类社会、物理世界以及信息空间的纽带,这是由于物理世界主要借助于物联、网互联网等信息技术在信息空间产生多元的大数据反射,而人类社会则借助图形、图像界面等方式在信息空间中产生一个属于自身的大数据反映。从工业化角度来讲,大数据还是第三次产业化浪潮的强劲助推力。根据IDC预测报告,全球到2020年底第三次信息产业化的市场营销份额将达到5.3万亿美金,而从2016年到2020年,IT行业90%的营业额增长都将由第三代信息产业推动。
与此同时,大数据也带来了很多前所未有的商机。例如,腾讯的易迅网电商平台会辨析每个登陆客户的身份,分析其曾经购买的商品,判断客户的喜好,并据此分析推荐客户登陆页面的广告位内容,提高客户的点击率。而每个成功的点击,都会给腾讯带来广告收入,腾讯2014年在广告方面的收入有90亿美元。由此可见,大数据分析在提升客户广告点击率方面的商业价值。大数据带来的商机不仅体现在广告领域。在金融行业,通过收集客户的数据并进行分析,能够对客户的“征信”程度进行评估。这种评估不仅可以降低贷款风险,而且可以用于交友等多方面,由此而产生的商业前途也比较广阔。在教育领域也可以实现一直所倡导的“因材施教”。基于学生的日常行为数据,可以分析学生的心理特点,了解学生的喜好,判断学生喜欢的学习模式,从而适配合适的教育方案。例如:通过分析大学生“小王”的上网数据,可以看出其关心“大数据学习”内容;通过分析其在朋友圈的交流内容,可以判断其性格特点(比较开朗、活泼)等;通过选课记录,可以判断其喜欢的讲师及类型(通过易懂型还是学术研究型等)。由此可以探索适合不同性格特点,选择不同教程的教育模式。例如让其选择网络上最流行的大数据培训教程和教学材料。甚至在“小王”的大学教育阶段,都可以基于大数据分析进行远程教育,制定上课计划,网上寻找教材,网上完成课程学分、论文编写等工作。这就撬开了庞大的网络“个性化教育”的金矿。与以往不同的是“因材施教”,是基于学生学习特点、独家制定个性化的教育培训方案。国内互联网公司已经率先行动开始改变自身的商业模式,通过自身与外部数据聚合,实现大数据“变现”模式。互联网主要企业大数据“变现”对比下表2.1所示。
 
表2.1互联网企业大数据应用对比
企业名称 大数据资源 大数据战略 大数据“实现模式”
百度 互联网入口数据:即时需求数据;公共网页数据; 强大的搜索引擎功能,加上高性能云计算服务支撑研发人员开发各种软件和App; 百度广告联盟;百度指数;百度定制报告;
阿里巴巴 整个互联网价值最高的电商流量数据;交易数据;信用数据;社交数据(微博和陌陌); “数据分享平台”的战略,为客户提供多元化或个性化服务,通过这些不同类型的服务平台,来完成自身对于大数据的手机以及完善,实现“跨界”合作创新的目的; 淘宝广告交易平台淘宝广告联盟;小微企业金融服务;数据交易集市;
腾讯 腾讯拥有大量基于客户明确ID的行为数据;社交数据; “强化大社交网络”平台揭开了由 “大数据”转向推广营销的大序幕,实现了尽早争夺市场的目的; 智能推荐;后端数据整合统一向前台开放;游戏广告;
大数据时代,工业设备、汽车、电表、水表、街头摄像头等每天都能产生海量数据,同样可以产生很高的应用价值,催生丰富的商业应用模式。所以互联网大数据时代,很多传统的商业模式都将受到新的洗礼,大数据提供的商机,让一切变得“皆有可能”,企业数据犹如一座“金矿”,蕴含着大量的宝藏。
2.1.1大数据的特征
随着对大数据研究的深入,越来越多的业界人士认为大数据普遍存在以下四个共同的特征:
(1)数据量大,即Volume。大数据通常指100 TB(1TB=1024 GB)规模以上的数据量,数据量大是大数据的基本属性。现在全球的数据量已然从过去的TB级别标准跳跃到PB级别标准。据IDC公司预测,科技的迅猛发展,全世界的数据存储量平均每两年就要翻一番,预计到达2020年底,全球数据存储容量将超越35 ZB,大部分的数据都会以半结构化或非结构化的形式涌现出来,具体数据增速规模如下图2.1所示。这就对大容量存储提出了更加严峻的挑战。二十多年前,由于受到当时硬件条件、信息技术和营销成本等的限制,使得大多数的企业数据都无法得到妥善存储和记录,即便是能够保存下来的信息,也仅仅是一些简单的模拟信号,当模拟信号向数字信号转化的时候,也常常由于各种误差造成大量的数据遗漏和丢失。然而,大数据的出现,就使得原本无法保存的大容量数据得以完善的存储。
 
 
 
 
 
 
 
 
 
 
 
图2.1 数据增速规模
(2)数据类型繁多,即Variety。传统的数据存储类型比较单一,通常仅仅局限于一些图形图像、数字文本、网络日志等少数的几种存储类型,形式上基本以结构化数据存储为主。而到了大数据时代则迅速扩展到语音、视频、地理位置信息等,甚至还扩展到结构化数据、非结构化数据和半结构化数据中去,其数据种类复杂多样,不计期数,目前形式上企业大数据基本上以非结构化数据和半结构化数据为主。与此同时,全世界的非结构化数据增速也是相当明显的,其增速指标高达63%,而结构化数据则仅仅占有剩余的30%以下。
(3)数据处理速度快,即Velocity。数据规模大规模的增加,必然对随之而来的数据处理速度要求越来越高。根据相关部门不完整统计,目前,互联网上平均每秒钟就能产生20万条搜索引擎信息和30万条网络广告需要处理分析;交通摄像头监控录像视频每天能产生10TB数据量;而全球最大的企业数据处理量年平均增速为213%。所以庞大的数据量必然导致现有的数据处理速度要满足实时性。例如当你开车自驾游时会查看智能导航仪来查询安全节约的路线,网络购物时会查看一下其他客户对这家商店的整体评价及商家信誉度,见到自己喜欢的食物会拍照发微博等诸如此类的信息互动交流活动,这些都不可或缺的产生一些网络数据。如何快速处理这些随之而来的数据信息,降低网络延迟时间,实时地呈现给客户,就显得尤为重要了。
(4)数据价值密度低,即Value。其主要指当数据量越大时,大数据能够被真正被利用的价值就越低,就像沙里淘金,很难发现有价值的信息。而所有数据的价值又不尽相同,只要合理灵活的利用数据并对其进行正确地分析研究,提取出有价值的信息,将信息整合为有用的知识,发现相关规律,最终都会产生高价值的信息。例如,电信行业的客户通话详单数据的价值,就比账单数据价值更高些,在实际应用中,使用频度也更高些。分析每个客户的交往圈,判断客户的信用度等应用,都应用到客户通话详细数据。这种客户通话详单数据是指客户每打一个电话,电信运营商就要形成一个通话记录,作为后续收费的明细凭证。客户账单数据,是基于客户通话详单数据,根据客户预定的资费产品,统计客户漫游等信息,最后形成每月向客户收取费用的依据。所以,如果没有应用价值,大数据就会成为“大垃圾”。
2.2 Hadoop生态系统
Hadoop是大数据平台处理数据的关键技术,其具有安全可靠、高效低廉的优点。它雏形起源于2002年的Apache公司的Nutch项目。后来在google公司与Nutch创始人Doug Cutting共同努力研究下,提出了针对大数据的Hadoop处理模型。Hadoop平台的核心组成部分是由HDFS文件系统与MapReduce 框架构成。HDFS在 上实现了 系统, 在 上实现了 和任务管理。 系统为MapReduce任务处理提供了可靠的文件操作和存储支持,而MapReduce则在 的基础上实现了作业任务的 等工作,并不断收集执行结果,二者相辅相成,共同来完成集群分发的任务。
目前,比较流行的是Hadoop 2.x系列的版本,其是1.x发行版本的延续,包含有当前最稳定的Hadoop发行版本,其整个生态系统如下图2.2所示。
 
 
 
 
 
 
 
 
 
 
 
 
 
图2.2 hadoop生态系统
2.2.1 HDFS分布式文件系统
 是一个在底层硬件上运行的具有高度容错性的分布式文件系统,它是Hadoop生态系统中数据管理与存储的基础,其通过流式数据访问解决了文件一致性访问的难题, 提高了并行环境下数据访问的吞吐量,适用于大规模数据集的开发。HDFS文件系统主要是采用主从 结构模式进行工作的,具体如下图2.3所示,其主要由一个 节点和若干个 节点组成。整个系统架构把 作为主节点,用于统一管理整个文件系统资源和客户端对文件的打开、创建、关闭等访问工作;并采用 作为从节点,用于统一管理系统中存储的数据集。从文件系统内部运行机制来看,所有的大容量文件都被分成若干个小规模的数据块,这些小规模的数据块被统一存放在一组 从节点上。所有的 节点都在 节点的统一调度下协调工作, 主节点永远不用来处理用户数据。为了整个系统稳定性,HDFS还增加了一个备用的Secondary   节点,用于辅助主节点工作。
 
 
 
 
 
 
 
 
 
 
 
图2.3 HDFS分布式文件系统
 
2.2.2 MapReduce 框架及计算模型
 框架同样也是采用主从结构模型进行工作的,其主要由一个独立运行在 上的 和运行在Hadoop集群 上的 共同组成,JobTracker负责将作业map阶段的任务和reduce阶段的任务分发给集群中空闲的TaskTracker。集群中的 负责调度一个用户作业的所有任务,并把这些作业任务分发到不同的 上,然后监视各个从节点上作业任务的执行情况,并反复调度执行从节点上失败的作业任务,而每一个 仅负责由 分派的任务。每当客户端提交一个作业任务时, 接受到任务和作业配置信息后,立即会将作业配置信息分发给 ,同时一边调度任务协调工作,一边监视 任务的执行情况。集群中的任何一个节点都能运行 ,而TaskTracker只能运行在 上负责执行作业任务。如果 出了问题, 会主动把任务调度给其它空闲的 重新执行。其工作流程主要包括以下几个组成部分,具体如下图2.4所示。
 
 
 
 
 
 
 
 
 
 
 
 
 
图2.4 MapReduce工作机制
 
MapReduce本身是一种计算模型,用以进行大数据量的快速计算。其计算原理主要是采用“分而治之”的思想。整个计算步骤分为两个阶段:Map阶段和Reduce阶段。其中Map阶段主要是有一个map函数来完成对大数据集上每一个单独元素进行特定的操作,以键值对的形式生成中间结果供Reduce阶段使用。而Reduce阶段主要是有一个Reduce函数来对Map阶段产生的中间结果进行归约,其把中间结果中具有 的 进行合并归约,以期产生最终结果。显然,MapReduce计算模型的划分很适合在分布式集群环境下进行并行化数据处理,它把大规模的数据集分为若干个小规模的数据块,这些数据块被分配到集群中任一个空闲的节点进行处理并输出一个中间结果。
MapRedcue工作原理:当启动作业任务时,map函数从分配到的数据块中一行行读取原始数据的键值对<k1,v1>,并将读入的数据暂时存入缓存区,接下来按着map函数的约定对读入的键值对进行排序,最后输出处理后的中间结果键值对<k2,v2>。与此同时,集群中其余的所有节点都执行同样的操作。在执行reduce函数之前,集群首先对中间结果进行了一次数据合并(Combine),即将中间结果具有相同key的键值对中的value进行合并。Combine阶段的合并过程类似与Reduce阶段合并过程,然而不同的是Combine阶段是map任务中的一部分,其紧接着map函数之后执行。Combine阶段能有效的减少中间结果键值对的个数,可大大地减轻网络通信的负担。Combine阶段完成以后,所产生的中间结果会以文件的形式存储到本地磁盘上,并通知主控 其所存储中间结果的文件位置,接下来, 再告知 任务应该到哪一个 上去取 结果,并将集群中所有的map任务产生的中间结果 划分成为n份,每份对应一个reduce任务分别负责不同的key区间。每个reduce任务向集群中所有的map任务节点抽取 的key区间内的 结果,并执行 函数进行合并,最后形成一个最终结果<k3,v3>。集群中若启动n个reduce任务,则最终就会产生n个结果,一般情况下这n个最终结果并不需要再一次合并为一个结果。因此,多数情况下可以直接将这多个键值对<k3,v3>输出到HDFS文件中。具体的数据处理的流程如下图2.5所示。
 
 
 
 
 
 
 
 
 
 
图2.5 MapReduce数据处理流程
2.2.3 YARN架构
 是Hadoop中的资源管理框架,其总体上仍然采用( )主从架构模型。它将每一个JobTracker划分为两个独立的进程:用一个负责管理全局的资源管理器 作为Master,其余负责管理任务的应用管理器NodeManager作为Slave, 整体负责对各个 上的 进行统一调度和管理。当客户端提交一个作业任务时,同时需要提供一个ApplicationMaster用以 这个任务,它一边向ResourceManager申请完成任务所需要的资源,一边要求NodeManger启动任务。
 架构主要由以下几个组件构成: (1)ResourceManager(RM)主要用来接收客户端任务请求、接收和监控NodeManager(NM)的资源汇报情况、负责全局资源的分配与调度以及启动和监控ApplicationMaster(AM)应用程序。其主要包括两个部件:一个是用于进行资源分配的调度器(Scheduler),另外一个是应用程序管理器( )。(2) 主要是用来负责单个Application(Job)的task管理和调度,向RM进行资源的申请,将得到的任务进一步分配给内部的任务,并向NM发出launch Container指令,接收NM的task处理状态信息。(3)NodeManager(NM)是运行在集群各个节点上的资源和任务管理器。它主要负责完成两个任务:一边,它要定时地向RM发送一个心跳信号,汇报本节点上各个Container容器的运行情况以及本节点上各个资源的使用状态;另一边,它要 来自AM的 等各种请求命令。(4)Container是各个节点封装多维度资源的容器,比如各个节点的内存、磁盘、CPU等资源。当 申请系统资源时,RM通过Container容器向AM返回资源。每个任务执行之前,YARN架构都会根据应用程序的动态需求为其生成一个Container容器,且每个任务只能使用与之对应的Container容器中所描述的资源。
YARN架构的工作原理如下图2.6所示:Client首先要向YARN管理器提交一个处理任务;然后, 在接受到任务后会主动地为该任务分配一个Container容器,并及时与 进行通信,要求它在这个Container容器中启动该任务的  ;一旦 启动后,它会通过RPC协议以轮询的方式向ResourceManager申领系统资源,然后不断监控它们的运行情况,直到应用程序运行完毕为止。如果任务完成失败, 就会重新启动该请求任务,重新为其申请可用的系统资源。
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
图2.6 YARN架构 
2.2.4 Hbase数据库
HBase是一个分布式的、面向列的动态模式数据库,具有良好的伸缩性和可靠的性能,通常用来存储非结构化数据。它与一般的关系型数据库不同,其存储数据的模式是基于列元素存储的而不是基于行的,同一个列的数据元素会被存储在一个块中,当需要读某些数据列时,只需把存储的相关数据列块读入内存即可,而不必进行整行读入,可节省大量的IO的访问。HBase数据库还为大规模数据提供了的随机访问和实时读写的功能,保存在其中的数据集可以使用 来进行处理,它完美的将并行计算和大数据存储结合在一起。当然,Hbase也存在着一定的局限,它只能做很简单的Key-value查询,适合有高速插入,同时又有大量读写的操作场景。
2.2.5 Zookeeper分布式协作服务
ZooKeeper是一个精简的文件系统,主要用来为分布式应用程序提供一个分布式的协调服务,起源于2006年11月份Google上发表的一篇Chubby论文。它提供了一系列简单的原子操作和一组额外的抽象接口,为分布式应用实现更高层次的服务提供了保障,轻松地解决了分布式环境下的复杂的数据管理问题:各节点状态的同步,集群资源的统一管理,统一的群组命名,协调的节点间配置、防止竞争资源的死锁问题等。
2.2.6 Sqoop
Sqoop起源于2009年的一个Apache项目开发的一个独立工具,它是SQL-to-Hadoop的简写,主要用于Hadoop和传统关系型数据库之间大批量数据传输,能够快速的分割每一个数据集并为之创建Hadoop应用程序来处理每个区块。它可以将一个传统关系型数据库(例如:Oracle,MySQL,Postgres等)中的数据导进到Hadoop的HDFS中,也可以将HDFS的数据导进到关系型数据库中,充分利用了Mapreduce程序的容错性和并行化,为使用者的快速开发提供了便利。
2.2.7 Pig
Pig是一种基于MapReduce的探索大规模数据集的脚本语言,其内包含了一系列的数据变换操作和数据流语言,在Pig内部,这些变换操作被转换成一系列的MapReduce作业在Hadoop上执行,经常用于进行大数据的离线分析。
2.2.8 Flume工具
Flume是由Cloudera提供的一个分布式的,高可用的,高容错的海量日志采集、定制、扩展、传输和聚合的系统。Flume为了收集数据允许在日志系统中定制各类数据发送方;同时,Flume还可以对数据进行简单的过滤、格式转换等处理,并能将处理后的结果写入到各种数据接受方。为了保证集群中各节点配置数据信息的统一性, 引入了 ,用于保存配置好的数据,从而保证配置数据的高可靠性和一致性,此外,若配置的信息发生改变时, 就会通知 Master进行配置信息更新。 之间使用 协议进行通信并同步数据。 
2.3 数据挖掘综述
数据挖掘是进年来商业应用领域中一项崭新的数据处理技术,其主要特点是对商业数据库中累积的大量繁杂数据进行抽取、转化、分析、整合、归纳和模式化处理,进而从中提取具有商业价值的关键知识,为企业的全面决策提供辅助支撑。简单来讲,数据挖掘就是对已有数据中本身存在而又尚未被发现的潜在信息进行发掘,从中抽取有用的信息或知识,比如某一个行业的未来发展趋势、产品之间潜在的相互关联性及数据之间模式等。
现在,数据挖掘已广泛应用于人工智能、数据库领域、机器学习、模式识别、可视化技术、统计学等多个相互交叉的领域。而在竞争激烈的商业界,许多的企业逐渐开始意识        到,合理地对公司业务数据进行挖掘和探索,不仅能带来商业机遇还能更好地帮助企业规避风险,扩大生产和投资。但是,数据挖掘技术常常也不是万能的,其毕竟也仅仅只是一个工具,并不能对所有的“预言”进行查证和确认,对已预测的事情,也不能保证其一定具有实际的商业价值和应用。所以有时候也有可能因为数据量的不足及某些方面的缺陷而产生误判或者虚假的信息,给企业带来一定的投资风险。所以现代企业在总结前人挖掘失败教训经验,经常会全面搜集大批量的数据,这些数据不仅仅是业务内的数据,也涵盖了整个产业链的交易数据,例如市场销售、客户资源、供货商配货等,甚至会涉及到行业内重要竞争对手的商业信息,然后再借助数据挖掘技术,这样企业就可以完全有能力从大规模数据洪流中,寻找到“金矿”,收集和挖掘出真正有价值的“营养品”,为企业未来的持续发展注入活力,进而也可为企业形成独特的竞争优势— 。它是确立企业“精细化营销、精细化管理”的基础。可以帮助企业梳理企业发展的理念,掌握市场发展动向。例如,市场经济和计划经济相比,具有很大的盲目性,生产者在生产产品时,不知道市场到底是什么样子,只能先生产,再销售,如果销售良好,就扩大生产,如果销售不好,就降低产量。这种盲目性造成大量生产资料浪费,是市场经济的最大弊端,但市场经济能够充分激活生产者的积极性。而计划经济则是另一个极端,所有的生产都是事先确定好的,但生产计划制定者并不知道产品实际销售情况如何,导致生产方式滞后,生产者积极性不高。在数据驱动的时代,可以适当做到“按需生产”的理想状态。通过数据分析,能了解客户的真实需求,再结合市场容量分析,然后合理安排生产,避免浪费,也可以促进生产者的生产积极性,这将解决传统的两种经济模式中由于信息封闭导致的生产资料浪费或者计划跟不上变化的等问题。
2.3.1 数据挖掘方法
一般而言,常用的数据挖掘分析方法,主要包括以下几个方面的统计和计量方法:
 (1) 分类。它是数据挖掘中的一个重要分支。分类是把任意数据集的总体数据按照同组相似性和组间差异性自动分成几个类别,无须事先的人工干预,也无须事先知道总体中存在的一些潜在类别信息。其主要是用来寻找大数据集中某一类数据对象的共同特征,将其按着一定的分类规则细分为不同类别,以达到群分的目的。它可以应用到社会的各行各业中去,例如公司的客户群体分类、客户群体消费行为及喜好分析、客户贡献度分析、客户的忠诚度分析以及客户的未来购买需求分析等,进而可以大大提高企业的精准营销。基本的分类步骤有:(a)建模;选取训练样本集,每个训练样本都有一个类标签与之对应,根据训练集中的数据表现出来的特性,为每一个类找到一种准确地学习模型,学习模型主要使用分类规则、决策树、等式、不等式和规则等形式提供。(b)使用模型进行分类:首先评估模型的预测准确度,主要方法是选择一组独立于训练集的随机样本在给定的模型上进行测试,被正确分类的测试样本的百分比就是准确度(使用交叉验证法来评估模型是比较合理的);如果准确度可以被接受,就可以用它来对未知的数据进行具体分类了。当然,良好的分类效果,必然离不开一个好的分类器,分类器通常也被称为分类函数或分类模型。它能把大规模数据集中的每一个数据项映射到特定类别的群体中。经常用于深层次的数据分析、为大规模数据集提取重要的分类模型以及根据数据的走向预测未来有可能发展的趋势。分类器的基本 包括:(a) 统计分析法:分为非参数法和贝叶斯法。贝叶斯法是一种通过计算假设下概率的方法来获取未知参数的先验信息和样本信息,然后再根据贝叶斯公式,得出后验信息,最后再反过来通过后验信息的结果去推断未知参数的方法。而非参数法主要是基于现有样例的学习或者模仿学习的经验来得出统计结果。 (b) 机器学习法:分为规则推导和决策树。规则推导主要根据规则产生式或者决策表来推导要产生的结果。而决策树则根据每个事件或决策采取自上而下的方式推导尽可能存在的结果。(c)神经网络方法:主要包括 网络模型,多层网络 算法,自组织 理论,自适应 理论等。
(2) 回归与预测。回归与预测挖掘技术的核心思想就是从复杂多变的数据集中,分析得到一个回归函数,该函数可以用于描述待处理数据样本的分布规律。而且这个函数可以是线性的,也可以是非线性的,通过该函数来描述和预估未来可能出现的数据或事件,其研究的领域主要包括数据序列的 特征预测、数据间的相互关联性等。经常被有效地应用到商业营销的各个方面,比如寻找客户资源、保持企业客户防止流失、有 性的促销活动以及产品 周期预测、销售趋势分析等。因此,回归与预测法是当前最行之有效的市场预测手段之一,其常用的方法包括:时间 分析、类 网络和 分析等。 
(3) 关联规则分析。关联规则分析主要是用于发现复杂数据集中各个数据项之间相互存在的一种规律和模式,也即是说根据某一个 中出现的一些事项可推断出必然会有另外一些隐藏的事项也会随之在同一 中发生。例如,在企业客户关系管理系统中,可以通过对企业数据库中大量的客户资源信息进行有价值的关联挖掘,找出最具影响力的市场营销因素,进而可以为企业的商品定位、商品定价、客户群体的营销、新客户的寻找、老客户的保持以及企业的市场风险评估与预测等重大决策提供真实的参考依据。有时,也可从数据库中关联分析出形如“由于某些事务的发生而引起另外一些事务的发生”之类的规则。如“67%的顾客在购买啤酒的同时也会购买尿布”,因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益。又如“‘C语言’课程优秀的同学,在学习‘数据结构’时为优秀的可能性达88%”,那么就可以通过强化“C语言”的学习来提高教学效果。
(4) 特征提取与选择。特征提取和特征选择都是从原始特征中找出最有效(同类样本的不变性、不同样本的鉴别性、对噪声的鲁棒性)的特征并将原始特征转换为一组具有明显物理意义(Gabor、几何特征[角点、不变量]、纹理[LBP HOG])或者具有统计意义的特征。然后从特征集合中挑选一组最具统计意义的特征,达到降维的目的。它们的主要作用是减少数据存储和输入数据带宽,并且其在低维度上分类效果往往会比较好。它能发现更有意义的潜在的变量,帮助对数据产生更深入的了解。
(5) 偏差和变化分析。偏差主要包括事务中很大一类不易发现的反常事件,比如模式中的特例,聚类中经常遇见的反常数据,实际观察结果对理想中期望的偏差等。其目的就是要寻找事务中的差异性,即寻找正常情况下观察结果与实际参照量之间的误差。这一点功能对于企业危机管理及其风险预警具有极其重要的意义,相比较可预测的正常情况,企业管理者更加青睐那些对异常规则信息的及时发现与识别。
(6) Web挖掘。随着互联网日新月异的发展,使得Web在全球快速得到普及,其上所囊括的信息量也是丰富多样,从而将数据挖掘应用到Web上也逐渐成为一种新的趋势。它利用数据挖掘技术从Web海量信息的资源和行为中挖掘出比较感兴趣的、有用的模式和潜在资源信息,这其中会涉及到Web信息技术、大数据分析、人类行为学、计算机信息学等多个相互交叉的科学领域。通常,利用Web 的海量信息量进行挖掘与分析,可以获取企业竞争对手信息、探索用户浏览日志规律、发现潜在市场、识别竞争对手、保护企业敏感信息等。目前,根据对数据类别的不同,可以大致将Web挖掘任务分细分为三种类型:对Web页面的结构挖掘、对Web页面的内容挖掘和对Web页面的使用挖掘。
2.3.2 数据挖掘步骤
数据挖掘的步骤业界至今尚未有统一的定论,其经常随着挖掘领域不同的特性和技术方案而随之变化,比如数据规模的大小、数据的完整性、行业类对挖掘知识的认知程度以及挖掘人员对同一个问题理解的差异性都会对具体挖掘步骤产生影响,甚至会出现截然不同的挖掘方案和步骤。此外,由于其自身过分依赖领域知识,即便是同一领域,往往也会因为分析流程的规划步骤和技术方案的设计模式不同而有所影响,甚至产生差异性。因此,针对业界的需求,数据挖掘流程的标准化及统一化就显得尤为重要了。后来,随着业内迫切的需求,在2000年由欧洲的几家数据挖掘公司通过切实的参与和研究提出了一个为数据挖掘建模的标准模型—CRISP-DM 1.0。该模型通过完整的规划、设计以及与行业内多家有经验的软件公司探讨,最终确立了数据挖掘过程中必不可少的步骤并加以统一化和标准化。它着重分析了数据挖掘中要必须有一个完整过程而非仅仅针对一些数据分析及建模,同时其也区别于其它各种具体的数据挖掘系统和算法。由此可以看出,CRISP-DM1.0模型着重从方法学的角度入手来强调挖掘过程中方法和步骤的重要性。如此一来,该模型就不仅仅可以轻松地跨行业使用,也可以结合领域的专业知识及实际操作流程来充分发挥其真正的挖掘功能和作用。一个完整的数据挖掘步骤主要包括如下几个方面:
(1) 业务理解。本阶段也是数据挖掘的最开始阶段,主要需要从具体的业务角度出发去宏观地了解项目要达到的目标。在该阶段,要准确把握业务中的关键因素,确定好业务对象,并能在分析过程中逐渐将具体的业务内容及知识转化为数据挖掘中所能接受和识别的定义。虽然业务理解阶段并不能做什么具体的挖掘工作,但其是必不可少的,因为清晰地了解业务是数据挖掘的第一步,其具有一定的预见性和探索性。否则,盲目性的挖掘只会带来失败。
(2) 数据理解。本阶段需要对原始的业务数据进行充分的收集和了解,熟悉数据的含义及代表的意义,检查数据的合法性,去除异常的数据及不完整的数据,寻找数据内部存在的潜在关系,根据数据内部隐含的信息去探索一些新的挖掘思路。
(3) 数据准备。本阶段主要是根据业务的具体需求从已理解的原始数据中选取符合要求的数据集。数据集的选取和构造过程不是一次性就能解决的,必须通过反复的收集和确认,甚至有些特殊过程要执行很次。整个数据构造过程采用随机选取的原则,没有任何的顺序。其中主要包括三个方面的工作:(a) 数据的选择:由项目的实际目标出发,选择所有与需求有关的业务数据,这些数据不仅仅局限于数据库里面的数据,可以来自不同的渠道。(b)数据的预处理:对于收集来的“粗糙”数据进行去干扰处理,提高数据的质量,消除冗余的和不必要的数据,确定数据挖掘需要的数据类型,为进一步的研究提供数据支持。(c)数据的转换:将上一步得到的数据真正地转化成为一个可以分析处理的数据挖掘模型。
(4) 数据建模。本阶段主要利用各种方法和模型技术对已经处理好的数据进行反复实验和研究,建立一个最佳的数据挖掘模型,不断调整模型参数值,反复验证模型的准确性,优化模型性能及操作,直到建立一个最符合要求的挖掘模型为止。通常情况下,有些模型可能只对同一个问题具有较好的效果,在一些特殊的需求仍然很难达到真正的满足,因此,有时候为了更加完善挖掘模型的性能,需要经常回退到数据准备阶段重新组织数据进行实验。理论上,在数据建模阶段除了挖掘算法不合适需要重新选择外,其余的一切操作流程都应该能自动完成。
(5) 模型评估。相比较前一阶段来说,本阶段的主要任务是从宏观的角度上对已建立好的高性能挖掘模型进行全方位的验收和评估。其主要工作包括:验证模型的可行性,检查挖掘步骤是否有纰漏,随机抽取实验数据进行实验,评估实验结果是否符合业务的标准,测试是否还有没有被考虑到的重大业务问题等。在模型评估完成后,意味着由该模型产生的挖掘结果已经具备可以投入使用的状态。
(6) 模型部署。这个阶段主要将已构建好的复杂模型经过层层封装后重新可视化地展示给客户。通常会有一些图形图像界面或者简单通俗的挖掘报告供业务员参考,客户满意后再进行实际应用环境的部署。
CRISP-DM 1.0 模型的生命周期一共包含以上六个阶段。但它们的执行顺序又不是完全固定不变的,可以根据实际情况的需要前后颠倒这些执行过程。因此,一个良好的数据挖掘结果是需要综合考量许多内在或外在的因素,单单的靠某一个挖掘技术是不行的,要因地制宜。
2.4 K-means算法理论研究
随着电商、物联网、云计算等一系列新型技术的发展与应用,如今的数据增长已不再是线性的、缓慢的,它所呈现的是海量的、复杂的、实时与爆炸性的。显然,再使用传统的单机存储和串行的数据挖掘技术已无法满足当前的应用需求。而Google提出的一种用于大规模数据集并行处理的软件架构MapReduce编程模型,在处理TB级别以上的数据业务时有着明显的优势。在由Apache基金会开发的Hadoop平台上,能够轻松搭建这样一个具有海量存储能力的分布式文件系统HDFS和并行化计算的MapReduce框架。近年来,把Hadoop大数据处理技术广泛应用于数据挖掘领域已经逐渐成为一种新趋势。而聚类分析算法正是这一类数据挖掘算法的核心之一,它的重要思想就是数据归类,正所谓的“物以类聚,人以群分”。其优秀的分类技术使得同组数据更紧密,而不同组数据更加疏远。目前,业界研究人员提出的聚类算法主要被划分为以下几大类:基于 的聚类算法,基于 的聚类算法,基于 的聚类算法,基于 的聚类算法,基于 的聚类算法等。
 算法就是一种常用的基于划分的聚类挖掘算法,该算法的思路简单、收敛速度快,且设计方便使用范围广,但是传统的 算法也有自身的缺陷:要求用户事先指定K值来确定分组数量,由于K值的选取具有一定的盲目性和随机性,使得聚类的结果经常会陷入局部最优,而不能达到全局最优;聚类质心是随机的指派的,缺乏科学性和指导性,经常导致得到的聚类质量较差,甚至出现错误的聚类结果,往往对K-means算法的精确度具有严重影响;当数据量非常大时,聚类迭代次数繁琐,程序运行时间消耗大,对高维数据集的处理十分棘手且易产生内存溢出的现象;算法并行处理能力差,传统的设计思路缺乏可伸缩性且不利于扩展;传统的聚类准则函数通常用来处理一些簇密度比较均匀的样本集,对于样本之间数据量差异较大的样本分布处理效果较差,对于不规则的数据集和簇密度分布不太均匀的数据集无法有效的处理,还会经常引起大的类簇被拆分。
针对上述K-means算法的局限性,许多研究人员提出了不同的解决方案。在K值选取的问题上,赵庆、毛典辉等提出了Canopy改进策略,避免了K值选取的盲目性[9,10];雷小锋等利用多次随机采样的方式来确定K值,然后再完成聚类[11];武霞等针对质心的随机选择存在的缺陷提出了一种新的中心点选取算法M+Kmeans,进一步提高K值选取的精确性[12];刘远超等也在此基础上提出了一种更为先进的K-means文档聚类初始值选择算法[13]。
针对传统的K-means算法在迭代过程中产生的大量冗余计算问题,张顺龙等针此问题提出利用三角不等式原理的优点来解决距离迭代计算中的不足,减少了迭代次数,提高了算法的运行效率[14,15];Dean J和Ghemawat S等提出了一种基于Mapreduce简化的大数据处理集群,提高了数据检索的速度和精确性[16];ElkanC等提出了一种加速的K-means  聚类算法,来提高算法的距离迭代计算速度[17];AndrewWM等人将三角不等式原理应用到高维数据集的处理上,获得了很好的实验效果[18];何春霞等提出了基于三角不等式原理改进的K-means聚类算法,达到了很好的聚类效果[19];此外,虞倩倩等还对迭代计算过程中产生的内存泄漏问题做了进一步的优化工作[20]。
针对串行化设计的局限性,文献[21,22,23,24]实现了 K-means算法的分布式聚类,提高了聚类算法的运行效率和加速比;Saeed Shahrivari等基于MapReduce利用重组技术提出了一种新的聚类算法Mrk-kmeans,提高了原算法的运行效率和时间复杂度[25];文献[26,27,28,29]利用MapReduce编程模型在Hadoop平台上实现K-means算法的并行化;提高了算法的加速比,节省了大量的系统运行时间;谭跃生、孟海东等在云计算平台下对传统的K-means算法进行了研究分析,并验证了该算法在Hadoop平台上具有良好的性能,适合应用于大规模的数据集 [30,31];高榕、李晶等基于云环境提出了一种并行化的K-means算法,它采用集 存储方式进一步提高了算法的精度和运行效率,但其却只能在单机节点下运行,无法适用于大规模集群环境下的聚类挖掘 [32];另外,文献[33]利用 云计算技术和 技术的有机结合,对 K-means聚类算法进行了混合式的架构设计,进一步缩短了传统算法的运行时间 [33]。 
针对聚类准则函数的不足,孙秀娟等在确定最佳K值方面,提出了一种新的基于几何的聚类有效性函数,大幅度降低了噪声和孤立点数据对聚类结果的影响[34];张雪凤等提出了一种新的数据对象分配方式,使簇内的各点更加紧凑,不在簇内的点更加稀松,大大减少了数据点的误分率,提高了K-means算法的有效性[35];Banerjee和Ghosh等人提出了一种比例均衡的聚类算法研究,提高了类簇的聚类效果[36];叶于林等针对K-means算法对初始聚类中心点非常敏感,利用势函数法对聚类函数进行了改进,使聚类具有更好的稳定性和可控性[37];石云平等使用平均误差准则函数E作为聚类结果好坏的衡量标准之一,保证了聚类运行结果的有效性和可靠性[38]。
另外,国外一些学者,还提出了一些扩展性的研究分析。Hamerly和Pelleg等人提出了一种新的K值估计方法,用以提高算法的聚类精度 [39,40];Fayyad等人在传统算分研究的基础之上,提出了一种简单处理方案,用于规避簇初始化对整体运行结果影响 [41];Khan和Deelers等人为了想摆脱初始质心点对聚类结果的影响,在这方面做了许多有意义的突破和尝试[42,43];Pena等人还对前人所研究的诸多聚类初始化方法进行了详细的比较和实验 [44];由于仅仅通过改进聚类的初始质心点并不能保证一定会有最好的聚类结果,Likas等人提出了用另外的方式来解决聚类质量问题[45];此外,Bradley和Nittel等人提出了一种专门用于处理大数据集的可伸缩性K-means算法 [46,47];Ahmad和Dey充分研究了 算法在 和 数据集上的使用情况[48];Stoffel等研究了并行K/h-means在大数据集下的聚类[49],Low和Bichson等在云计算平台下研究了一个基于机器学习框架的数据挖掘算法,提高了“盲聚类”的效果[51],Kwerdprasop等研究了基于密度的加权k-means偏聚类的方法[52]。Mortazavi和Jalili等研究了面向大型数值微聚集算法[53,54]。
2.5 本章小结
本章开始以大数据理论为基础,首先对本文研究的分布式平台Hadoop生态系统进行了介绍,重点阐述了Hadoop的核心组件、主要构造模块和工作机制;然后对数据挖掘的理论进行了详细的阐述,并对大数据挖掘步骤进行了分析研究;最后对目前K-means算法的研究成果进行了仔细的分析和研究,并对比了各种技术的优缺点。
 
 
3 基于双MapReduce改进的Canopy-Kmeans算法
本章根据第二章中K-means算法相关综述,探讨了传统Canopy算法与K-means算法不足之处。引入 “最小最大原则”对Canopy算法进行了改进,解决了K值和初始中心点的选取问题;应用“距离三角不等式原理”对传统的K-means算法进行了改进,解决了冗余计算问题,并在此基础上引入了加权聚类准则函数,增加了算法的收敛性判定。然后,在 云计算平台上提出了一种基于   改进的Canopy-Kmeans算法,并在此基础上给出了算法总体设计方案以及各部分的算法设计流程。本章特殊说明:本章的理论研究部分已于2016年09月发表在 学报期刊上(双MapReduce改进的Canopy-Kmeans算法.刘宝龙,苏金)。
3.1 传统的K-means算法
传统K-means算法首先是从n个数据对象中任意选择k个对象作为初始聚类中心,对于剩余的其它对象,根据它们与各个簇(类)中心的相似度,分别将它们分配到相似度距离最近的那个中心点所在的簇内,然后再重新计算每个新聚类的中心,重复迭代这一过程直到准则函数收敛为止。具体算法描述如下所示: 
(1) 对于任意的数据集合 ,事先设定聚类数目为 ,并从 中随机选取任意的 个数据对象作为聚类的初始质心点 ,其中 。
(2) 对于每一个数据点 ,计算其到各个质心的欧式距离并将其分配到距离最小的那个类簇中。欧式距离计算公式如下:
                              (3.1)
(3) 对于新得到每一个簇 ,重新计算其中心点坐标 。
(4)循环迭代执行(2)、(3)步,直到聚类准则函数 
                          (3.2)
收敛为止。其中: 是所有数据对象的平方误差总和, 代表类簇的个数, 代表第 个簇, 代表簇 的中心点, 代表任意的数据对象。
3.2原始的 Canopy-Kmeans算法
原始的Canopy-Kmeans算法是在K-means算法的基础上提出的一种优化,其基本思想是首先通过Canopy算法进行聚类,以确定簇数以及初始簇心,接着通过K-means算法进行迭代运算,收敛出最后的聚类结果。具体描述如下:对于任意的数据V,预先设定Canopy算法的两个区域半径(即阈值),通过粗糙距离计算方法计算集合中各对象的相似性,按着各对象的相似性可把数据划分成若干可重叠的小集合(即Canopy),经过一系列的计算后,最终可使得所有的对象均落在Canopy覆盖的范围内;对落在同一区域内的对象,利用K-means算法重新迭代计算出新中心点,并根据对象与新中心点之间的距离重新划分对象所属区域;循环迭代执行“划分Canopy-计算中心点”的过程,直到k个中心点的位置不再发生变化,即聚类函数收敛为止。
由上述描述可知,K-means算法虽然在开始时使用Canopy算法进行了预处理,无需再人为设置初始的聚类中心点及聚类个数K,但Canopy在初始中心点的选取上容易受到区域半径的主观影响,具有较大的盲目性和随机性。而该算法对K-means算法本身并未作出任何的改进,聚类迭代次数依然繁琐,存在大量的冗余计算,且该聚类函数 并未明确指出当算法收敛到何种程度时,可结束整个算法的迭代过程,针对以上存在的问题,本文同时从以下三个方面对原始的Canopy-Kmeans算法进行了改进和优化。
3.3改进的 Canopy-Kmeans算法
3.3.1 Canopy算法的改进
传统的Canopy算法虽然在K-means算法运行之前完成了对数据的预处理功能,解决了K-means算法在开始时需要人为设置初始中心点及K值问题。但Canopy在K值及初始中心点的选取上却容易受到区域半径的主观设置的影响,仍然具有较大的随机性。其具体描述如下:
定义1(Canopy):给定任意数据集合 ,对于 ,若其满足如下公式 ,则称 为Canopy集合, 为Canopy中心点,  为Canopy集合半径。 
定义2(Canopy 中心点):给定数据集合 ,对于 ,若其满足如下公式 ,则称 为非Canopy候选中心点集合。
从以上的定义可知,传统Canopy算法的执行效率受Canopy区域半径 、 影响较大,当 过大时,会使同一点属于多个Canopy,增加了计算开销;当 过大时,会减少聚类的个数,使得聚类过程陷入局部最优。这样就导致了Canopy 算法在初始中心点的选取上具有较大的随意性。因此,为了解决 Canopy 区域半径 、 以及初始中心点的随机选取问题,本文采用了一种基于“最小最大原则”改进的Canopy 算法来提高聚类结果的准确性[9]。
为了避免在聚类过程陷入局部最优,应该使Canopy获得的中心点间距尽可能大。最小最大的基本原理[19]是首先随机选取一个种子点作为中心点A,然后计算集合C中剩余点到A点的距离,选取距离最大的点作为第二个种子点B,再计算C中剩余数据点到这两个种子点的距离,得出到这两个种子点的距离,得出到这两个中心距离最小的点 ,找到这些距离最小者中的最大值 ,迭代条件若满足公式3.3。
                    (3.3)
则该数据点为第三个种子点,其中 、 表示数据点到 、 点的距离。按照上述方法一直迭代下去,最终可以确定所有的中心点,这样 值也就一并得到了。
基于上述原理改进的Canopy中心点选取方法避免了区域半径 的设置( 为非Canopy中心点区域半径,当所有中心点确定后,该值就无需设置)[9]。另外, Canopy 中心点选择方法在具体应用中呈现如下规律:Canopy个数低于或者超过类别真实值时, 变化呈现较小幅度;当Canopy个数临近或达到类别真实值时,该距离呈现较大的突变[9,55]。因此,为了确定Canopy 中心点的最优个数以及区域半径 ,参照边界识别思想,引入了表示 变化幅度的深度指标 [9,19],其定义为:
          (3.4)
当 达到最优聚类时,深度值 取得最大值。由以上定义可知,此时Canopy中心点集合中前 个记录即为最优的聚类初始中心点,同时为了保证最终的聚类中心点均落在 Canopy范围内,可设区域半径 。则基于“最小最大原则”可进一步将Canopy算法改进为:
定义3(Canopy):给定任意数据集合 ,对于 ,若其满足如下公式 ,则称 为Canopy集合, 为Canopy中心点且 。 表示数据点 为所有最小距离中的最大者。 
定义4(Canopy中心点):给定数据集合 ,对于 ,若其满足如下公式 ,则称 为非Canopy候选中心点集合。 表示数据点 为所有最小距离中的最大者。
经过以上的改进可知,经过改进的Canopy算法,解决了人为设置区域半径 、 以及初始中心点和 值选取的盲目性,为聚类结果的准确性提供了可靠的理论依据。
3.3.2 K-means算法的改进
定义5:假设存在数据集 ,若 中存在这样一个划分,使得以下的式子成立 ,则称 为一个聚类。
定义6:假设 为所有已聚类中心的集合,当 ,使得 ,那么 为向量 的聚类中心。
公理1:任意一个三角型,两边之和大于第三边,两边之差小于第三边。由于欧式距离满足三角不等式特性,可以将它扩展到多维的欧几里得空间[32,54,55]。对于任意三个向量 、 、 ,其满足以下两个不等式:
                                  (3.5)
                                   (3.6)
根据以上定义及公理,我们可以得到以下应用:假设 是数据集当中任一个向量, 是向量 当前的类中心, 已知且 是剩余中心点中除 外任意的一个,如果 ,则有: ,化简可得:
                               (3.7)
由公理1中的欧式空间的三角不等式特性可得:
                               (3.8)
因此,有(3.7)、(3.8)式联立可得到如下结论:
 ,即向量点 属于聚类中心点 。
由以上推导可知,对于传统的K-means算法,若能在每次距离迭代计算之前增加一次判定筛选,则可避免很多的冗余计算。若用 表示 到 上界约束,用 表示 到 下界约束,则基于三不等式角原理可将传统K-means算法距离迭代计算进一步优化为:
(1)如果 ,则说明数据点 离该中心点比离任何其它的中心点都近好多,因此可断定数据点 在迭代过程不会变更其类中心,也就没必要对数据点 进行任何的距离计算。
(2)如果 ,由以上推导可知,并不能确切的断定 一定成立。因此,无法确定 与 的大小关系,数据点 有可能变更其聚类中心。但同时我们也注意到,对于满足 的类中心点也不可能成为数据点 类中心,所以此时只需计算当 满足 时,只需要计算 和 即可。这样一来就可进一步减少冗余的距离计算。
通过以上的判定可知,基于三角不等式原理改进的K-means算法能够大幅度地减少迭代过程中不必要的距离计算,提高了原算法的运行速度。
3.3.3聚类函数收敛性的改进
由公式(3.2)可知,聚类准则函数 只适用于各类样本大体上为球形、簇密度均匀且样本数目之间悬殊不大的样本分布,对簇密度不均匀的大数据集及具有噪声和孤立点分布的数据集布比较敏感。为了解决传统K-means算法聚类准则函数 的不足,本文采用加权聚类准则函数[56]来表示一个数据集的离散程度,具体如公式(3.9)所示。 值越高,表示实验数据越离散,结果就越不精确,反之, 值越低,实验数据越精确。
                          (3.9)
为了使 能够取得最小值,由公式(3.9)可得到如下结论:对于任意的一个数据点 ,在算法迭代过程中,都应该选择一个使聚类准则函数 的值增加最小的簇 加入。这样,数据点在每一次迭代过程中,就会更容易防止孤立点对 值的影响。当不同大小和密度的簇相邻而间距又比较小时,处于稀疏的大簇边界上的数据被错分到与之相邻的高密度小簇中的可能性就会减少。
若进一步对聚类准则函数 分析可知,在理想状态下该函数值在迭代计算过程中是一个单调下降的曲线。具体如下图3.1所示:
 
 
 
 
 
 
 
图3.1加权的聚类准则函数曲线图
 
这是因为对于任意数据对象 ,其在聚类迭代计算的过程中,数据对象都会被分配到离自己最近的簇中。随着聚类质心的不断调整,数据对象都将会越来越向着有利于自己的簇进行靠近, 的值也将会慢慢趋近于一个固定的值,最终当 的值不再发生变化时,整个算法将达到最优聚类。然而传统的K-means算法在每次迭代计算过程中并未明确指出当算法收敛到何种程度时,可结束整个算法的迭代计算过程,也并未将准则函数的值作为算法是否结束的判定标志。因此,可以在K-means算法迭代过程中增加一个基于聚类准则函数的收敛性判定,来提高聚类的收敛速度和准确性。
综合本章3.3.1节中定义3、定义4中改进的K值选取策略、本章3.3.2节中增加的距离计算筛选判定思路以及本章3.3.3节基于聚类准则函数增加的收敛性判定,则可进一步将原始的Canopy-Kmeans算法改进为:
(1)给定数据集合 且 ,将由定义3、4得到的Canopy中心点集合 中的元素作为 个初始聚类质心点 ,并令 。
(2)对于Canopy集合中的任意数据对象 ,在迭代距离计算之前都应进行一次筛选判定:若满足 ,则将数据点 分配到中心点 所在的簇 中,即 ,不需进行任何迭代计算;若满足 且 时,需要对数据点 进行迭代计算,以确定其所属的簇:
                     (3.10)
这样,最终将会生成 个新的簇。
(3)令 ,对新得到的每一个簇 重新计算其聚类质心:
                                  (3.11)
其中 代表被分配到簇 中数据点的总个数。
(4)计算加权聚类准则函数的值:
                    (3.12)
(5)若加权聚类准则函数满足收敛判定条件: (其中 为一个很小的常数),则当前各簇内已没有数据对象被调整,加权聚类准则函数已收敛,可结束本算法,已达到最优聚类;否则 ,返回循环执行第(2)步,直到加权聚类准则函数收敛为止。
3.4双MapReduce设计的Canopy-Kmeans算法
针对以上的改进理论,本文在Hadoop平台上采用了双MapReduce编程技术,将整个算法分成两个MapReduce子任务来完成,并用第一个MapReduce子任务的输出结果作为下一个MapReduce子任务的输入。基于双MapReduce改进的Canopy-Kmeans并行算法流程如上图3.2所示。其具体做法如下:首先,第一个子任务是在MapReduce编程模型中利用“最小最大原则”对Canopy聚类算法进行“粗糙”聚类,通过计算数据的相似性来对全体数据集进行相似性划分,最终可得到各个分组及所需的中心点集合和k值,完成对K-means算法的预处理。这样下一步的初始中心点的选择就不至于因为随机选择而偏离实际中心点太远,同时也避免了初始K值设定的盲目性;然后,第二个MapReduce子任务是在各个分组内(Canopy子集内)采用基于距离三角不等式原理改进的K-means算法进行“精细”聚类,在每一次迭代计算过程中,通过对各个数据点分配到加权聚类准则函数最小的簇中,减少了不合理的分类,提高了聚类质量,进一步优化了传统的聚类算法;最后,通过Driver对象将以上两个MapReduce子任务作业按线性方式顺序链接并自动化地生成一个可执行序列交给Hadoop平台处理,并将最终得到的聚类结果存入HDFS中。
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
图3.2双MapReduce设计的Canopy-Kmeans算法
3.4.1基于MapReduce设计的Canopy算法
利用改进的Canopy算法来选取初始的聚类中心点及K值。在Map阶段,根据“最小最大”原则及边界意识进行分类迭代,并在迭代过程中生成数据子集Canopy集合,然后输出得到的数据子集Canopy中心点集合Pi;在Reduce阶段,合并各个集群节点所得到中间结果Pi,得到一个全局的中心点集合P,然后在重复Canopy聚类,直到数据集合P为空时结束聚类。其中Map阶段算法流程设计如下图3.3所示。
 
图3.3 Canopy算法在Map阶段流程图
Map阶段算法伪代码如下:
输入:本节点数据集合List;Canopy中心点空集合Pi;
输出:Canopy中心点集合Pi;
Map(List list,List Pi ){
1. 设置初始的数据集合List={n},其中n为数据集合中任意的一个数据元素;
2. While List不为空
3. If Pi==0
4. 从List集合随机选取一个点n作为Canopy集合的中心点,并保存该点至集合Pi中;
5. 把数据点n从List集合中删除;
6. Else if Pi!=0
7. For 遍历List集合
8. 对于List集合中的任意一点,计算该点到Canopy集合中各个中心点的最小距离sn,并存入集合S中;
9. 求出集合S中的最大值Max(sn);
10. 把Max(sn)所对应的n点存入集合Pi中;
11. End if
12. End for
13. End while
14. Output(Pi);
}
把各个任务节点上在Map阶段产生的中间结果作为Reduce阶段的输入,Reduce阶段算法流程设计如下图3.4所示。
 
图3.4 Canopy算法在Reduce阶段流程图
Reduce阶段算法伪代码:
输入:各个节点在Map阶段所产生的局部中心点集合{P1,P2,...Pn};
输出:聚类个数K;最终的Canopy中心点集合U;
Reduce(String K,ArrayList P){
1.求取数据集合{P1,P2,...Pn}的数据总量M=sum(P);
2.While i<M
3.对于List集合中的任意一点n,计算该点到Canopy集合中各个中心点的最小距离sn,并存入集合S中;
4.求出集合S中的最大值Max(sn);
5.把Max(sn)所对应的n点存入新的中心点集合P′中;
6.End while
7.计算新的Canopy中心点集合P′中的数据量k=sum(P′);
8.While j<k
9.计算新的Canopy中心点集合P′中Depth(i)最大值max(Depth(i));
10.T1=max(Depth(i));
11.把新的Canopy中心点集合P′前i个点赋值给集合U;
12.End while
13.K=count(P′);//输出聚类的K值
14.Output(U);}
3.4.2基于MapReduce的K-means算法并行化设计
根据以上的分析,可以利用第一次MapReduce子任务输出聚类结果作为本次K-means算法输入, K-means算法主要以下三部分组成:Map阶段,Combine阶段和Reduce阶段。其中Map阶段算法流程如下图3.5所示。
 
 
图3.5 K-means算法在Map阶段流程图
 
Map阶段的伪代码设计如下:
Public void map(<key,value>,<key′,value′>){
输入:输入有Canopy算法得到的K值及中心点U集合,数据集X={x1,x2,…,xn};
输出:输出新的<key′,value′>键值对集合;
1.将Canopy中心点集合U作为初始化中心点集合;
2.While(true)
3.计算出U中所有的中心点ui到剩余中心点uj距离d(ui,uj);
4.If( && )
5.计算数据点x到中心点的距离,并确定其所在的类簇;
6.Else If ( )
7.数据点x不需要迭代计算其到中心点的距离;
8.end while;
}
在Map阶段当数据规模比较大时,集群中各个节点会产生许多的中间结果,势必会造成内存溢出,额外增加程序运行维护的开销。本算法在不影响聚类结果的情况下,采用了Combine()函数在Reduce阶段之前先进行一次中间结果合并,它主要是将具有相同key的键值对中的value值合并在一起,这样做不仅可以减轻Reduce阶段再次合并数据的压力,也大大减少中间结果写入到磁盘的次数。Combine阶段具体算法流程如下图3.6所示。
 
图3.6 K-means算法在Combine阶段流程图
Combine阶段伪代码设计如下:
Public void Combine(<key,V>,<key′,value′>){ 
输入:来自Map阶段的输出键值对<key,Value>;
输出:合并后新的键值对<key′,value′>;
1.定义一个数组Data并将每个元素初始化为0;
2.Number1=0,统计具有相同聚类的记录数目;
3.While(Value.hasNext()){
4.从Value.hasNext()中读取各维坐标值;
5.各维坐标值累加并存储到数组Data相应的分量中;
6.number1++;}
7.key′=key;
8.定义一个字符串stringvalue1,包含Number1和Data数组各个分量的信息;
9.Stringvalue1=value′;
10.Ouput(<key′,value′>);
}
本阶段通过将各个Combine函数得到的局部聚类结果来计算出新的聚类中心,并将该聚类中心用作下一轮的迭代运算。在Reduce阶段对Combine阶段的得到的中间结果进行数据处理,并将处理结果作为新一轮迭代计算的 ,直到聚类算法满足收敛性判定条件为止。 阶段算法设计流程如下图3.7所示。
 
图3.7 K-means算法在Reduce阶段流程图
 
Reduce阶段伪代码设计如下:
Pubic void Reduce(<key,Value>,<key′,value′>){ 
1. 定义一个数组Data并将每个元素初始化为0;
2. Number2=0,统计具有相同聚类的记录数目;
3. While(V.hasNext()){
4. 从V.Next()中读取出每一个数据样本的各维坐标值和样本个数Number2;
5. 各维坐标值累加并存储到数组Data相应的分量中;
6. Number2+=Number2;}
7. key′=(数组各分量/Number2);
8. 定义一个字符串stringvalue2,存储key′中新的坐标值信息;
9. Stringvalue2=value′;
10.Output(<key′,value′>);}
3.5本章小结
本章对传统k-means算法的设计思路和过程进行深入的研究,重点探讨了已有研究成果的优缺点。首先,为了优化K值的选中问题,在Hadoop平台上基于最小最大原则对传统的Canopy算法进行了改进,成功地解决了传统Canopy算法中人为设置K值选取问题;其次,为了解决传统K-means算法在迭代过程中的大量冗余计算,本文基于三角不等式原理的优点,在k-means算法迭代计算之前,增加了距离筛选判定;另外,为了进一步提高算法精确性,引入了加权聚类准则函数,增加了收敛性判定;最后,设计并实现了基于双MapReduce编程模型改进的Canopy-Kmeans算法,并对该算法的时间复杂度进行了分析。
 
4 实验及实验分析
第三章介绍了本文提出的基于双MapReduce编程模型改进Canopy-Kmeans算法的基本步骤,为了检验本文提出算法的实际性能,本章利用分布式Hadoop平台分别实现了传统K-means算法、传统的Canopy-Kmeans算法以及本文改进的Canopy-Kmeans算法,以社发物流公司的真实历史数据为依据,进行了大量的实验,并对实验结果进行了分析对比。
4.1 hadoop集群配置与部署
Hadoop集群环境总共有5台PC机搭建而成,其中作为Master节点的配置为:CPU型号为Intel(R) Core(TM)i5-4200U 1.6GHz,内存8GB,硬盘1TB,其它4台计算机作为slaves节点的配置为:CPU型号为酷睿2E6600, 内存2GB,硬盘500GB,5台计算机的操作系统都为统一安装的Linux系统。各台计算机之间通过局域网连接,具体如下图4.1所示。
 
图4.1 hadoop集群环境搭建
 
本次安装规划总共使用了6个节点,每个节点使用的hadoop版本统一为hadoop-2.5.0。五个节点的hostname分别规划为:Hadoop-0,Hadoop-1、 Hadoop-2、Hadoop-3、Hadoop-4、Hadoop-5,其对应的ip地址分别可以设置为: 、 、 、 、 、 。六台计算机的安装方式为一主五从,另外,为了使集群具有良好的性能,分别将ResourceManage安装在hadoop-1机器上,将SecondaryNameNode安装在hadoop-2机器上,其余的各主机角色分工及网络拓扑结构分配如下表4.1至4.7所示。
 
表4.1 Client角色分工
主机名 Hadoop角色 角色任务分工
Client 开发测试 安装了jdk、 eclipse及 hadoop安装jar包。
 
表4.2 Hadoop-0角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-0
(192.168.60.100) Master NameNode
JobTracker
NodeManager
JobHistoryServer
/opt/hadoop
 
表4.3 Hadoop-1角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-1
(192.168.60.101) Slaves1 DataNode
TaskTracker
ResourceManager
/opt/hadoop
 
表4.4 Hadoop-2角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-2
(192.168.60.102) Slaves2 DataNode
TaskTracker
NodeManager
SecondaryNameNode
/opt/hadoop
 
表4.5 Hadoop-3角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-3
(192.168.60.103) Slave3 DataNode
TaskTracker
NodeManager
/opt/hadoop
 
表4.6 Hadoop-4角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-4
(192.168.60.104) Slave4 DataNode
TaskTracker
NodeManager
/opt/hadoop
 
表4.7 Hadoop-5角色分工
主机名 Hadoop角色 角色任务分工 安装目录
Hadoop-5
(192.168.60.105) Slave5 DataNode
TaskTracker
NodeManager
/opt/hadoop
 
4.1.1网络配置
首先关闭六台节点上的防火墙,配置各节点的IP地址,具体分为以下三步:
(1) 配置主机点的静态网络IP及剩余从节点的IP。
(2) 使用命令vi /etc/hosts修改主机名,并添加以下IP地址与主机名的映射。
 
 
 
 
 
 
 
 
(3) 按照此过程及相同数据(除了IP地址不同)分别对剩余五台从节点进行IP地址与主机名的映射配置。
4.1.2安装jdk
Hadoop是由Java语言程序编写的,自然其上面的MapReduce程序框架设计环境也就需要JDK,具体的JDK安装步骤如下所示:
(1)下载并安装jdk。
(2)在用户根目录下,建立bin文件夹。
mkdir /bin
(3)修改文件的使用权限。
 
(4)然后执行JDK安装文件。
 
 
 
 
(5)使配置文件profile重新生效。
 
(6)验证JDK安全文件是否已经成功安装到节点上,并重新配置生效。
 
(7)另外五台主机与以上配置相同。
4.1.3建立ssh互信
由于Hadoop集群一般机器规模比较大,每次启动集群需要耗费大量的机器连接登陆时间,所以为了节省Hadoop集群的启动时间,本集群也采用SSH(无密码登陆模式)进行各个主机进程的通信。具体的配置如下所示:
(1)设置主节点进程并配置ssh通信。
 
(2)将 文件拷贝到剩余的五个从节点上。
 
 
 
(3)检查配置的ssh通信是否成功。
4.1.4 配置Hadoop
(1)到hadoop官方网站上下载hadoop版本,并选择hadoop-2.5.0.tar.gz。
(2)将下载的压缩包放到bin目录下解压。
(3)进入解压后文件目录 下,然后执行如下操作重新配置 文件。
 
(4)重新修改配置文件 下的 hadoop.tmp.dir目录以及 所在的主机端口号:9000。
 
(5)重新配置 文件中的数据块复制参数 的值为3。
 接下来,设置mapred-site.xml文件下jobtracker主机端口参数值为 9001。
 
(6)增加 环境变量,并使用命令 重新为之生效。
 
(7)以上就完成了第一台主节点的配置,剩余的五台机器上也按着以上相同配置安装hadoop,当hadoop的集群中的各节点配置完成以后,可输入hadoop操作命令,验证各节点是否配置成功。
 
 
(8) 格式化HDFS,在hadoop-0的/home/brian/hadoop/hadoop/sbin中执行start-dfs.sh命令。
 
(9)在Hadoop-1上启动YARN,把namenode和resourcemanager分开是因为性能问题,因为他们都要占用大量资源,所以把他们分开了,他们分开了就要分别在不同的机器上启动。在hadoop-1的/home/brian/hadoop/hadoop/sbin中执行start-yarn.sh命令。
 
(10)通过命令 来 化 ,并通过命令 来启动Hadoop。 然后输入jps命令,查看启动的服务进程,如下所示,则说明相应的服务进程都启动成功了,运行本文程序可如下所示。
 
(11)所有的配置完成后,可查看本文程序的运行情况,具体如下所示。
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4.2实验数据及结果
4.2.1数据准备
根据商业理解的目标可知,本阶段是对无标识类型的客户进行有效分类。因此,可以利用Canopy-Kmeans聚类分析的方法对原始客户进行聚类分析。本文主要从社发物流管理信息系统中抽取2015年的客户资料和年度报表等原始数据资料。这些资料中包含客户的运单号、信用度、交易额、利润和运单数量等聚类分析所需的关键信息,然后进行以下数据处理:
(1)数据的抽取。对于物流企业来说,其客户细分的主要指标有客户的交易额、盈利能力(利润)交易的频度(运单数量)和信用度这四个方面。因此企业需要获得有关这些指标的数据。在大多数物流企业的客户资料和年度报表中都拥有满足这些指标的相关数据。以1年为单位从物流企业管理的数据库中抽取业务的客户资料和年度报表的相关数据作为聚类分析的原始数据;
(2)数据的筛选。由于物流企业的运单发生率很高,从而导致企业产生大量的微小客户,有些客户月平均的交易数量极低且利润率微薄,更有甚者仅为一次性交易的客户。此类客户数据的存在不仅对聚类分析确定物流企业的关键客户毫无用处而且会影响k-means聚类的计算效率。因此企业可以设定一定的阈值剔除微小型客户,筛选出符合阈值标准的客户数据;例如,将年交易次数在10次以下,年交易额在3000元以下,年利润在300元以下的数据信息剔除。
(3)数据的清洗。经过筛选处理后的数据,仍然不能够直接用于K-means数据挖掘。此时的数据记录还存在许多的不必要的属性(字段),这些属性并不参与k-means聚类的数据挖掘,对挖掘结果不产生影响。需要将不必要的属性(字段)予以屏蔽处理。如原始数据中还包含“吨位”、“件数”、“目的站点”、“源站点”、“中转站” 、“联系方式”、“负责人”、“客户地址”等属性。另外还需要对可能存在瑕疵点和异常值进行检查剔除处理。如物流信息中的回货单、退货单及数据记录值的缺省、数据的冗余记录,这些数据会影响聚类结果的正确性。
经过以上的数据准备,将原始数据整理成包含“运单号”、“年交易额”、“年利润”、“运单数量”和“客户信用”四个聚类指标的数据集,作为下一步“Canopy-kmeans算法建模”的数据。其抽取的所得到数据格式如下表4.8所示。
 
表4.8抽取的物流历史数据
客户编号 年交易额(元) 年利润(元) 运单数量(个) 信用度(%)
SH16174 300786 32010 320 100
SH10384 54621 9400 78 98
SH13120 112932 12336 185 87
SH15776 127682 46778 301 79
SH24578 33567 40083 54 100
SH63102 72389 28345 86 100
SH63275 145903 39921 192 94
SH83129 21008 2980 32 98
 
4.2.2执行Canopy-Kmeans算法模型
首先,将上一步利用孤立点挖掘算法得到的清洗数据上传到HDFS分布式文件系统中;其次,利用本文基于双MapReduce改进的Canopy-kmeans算法对新得到的数据进行聚类;最后,运用Hadoop集群强大的存储与计算能力,完成最终的客户细分,获得关键客户群体的聚类分组。具体执行流程如下图4.2所示:
 
图4.2 整体解决方案
4.2.3结果分析
通过运行本文设计的双Mapreduce程序可以对抽取的原始物流信息进行聚类,由聚类结果可知,所有客户被分为5类,具体如下图4.3所示。
 
图4.3 客户聚类结果
由于聚类数不多,这里可以通过直接比较法来确定关键客户群体。通过以上的运行结果可以看出聚类1中的客户群体在“年交易额”、“年利润”、 “运单量”和“信用度”这四个指标的均值比例均达到整个聚类分组中的最大比例。由此可知,本文改进的Canopy-Kmeans算法是可以满足物流企业确定关键客户需要的,聚类结果是合理可行的,聚类1中的37个客户群体即为本次物流企业所要找的关键客户群体,具体如下图4.4所示。
 
图4.4 聚类1客户详细列表
4.3算法在Hadoop集群上的性能分析
为了进一步验证本文改进的Canopy-Kmeans算法的在Hadoop平台上的有效性和整体性能,本文又采用了四个衡量指标,其分别为算法的准确性、收敛性、加速比以及扩展性,并以社发物流公司真实的历史数据为依据,进行了大量的实验,并把实验结果分别与传统的K-means算法和进行了分析比较,实验结果表明,改进的算法各方面都明显优于传统的K-means算法。
4.3.1算法的准确性分析
为了验证本文算法的正确性,从物流历史数据中分别选取了三组样本数据进行实验,分别为:数据集1:100M,2维;数据集2:300M,4维;数据集3:900M,8维。由表4.9可知:改进的 Canopy-Kmeans算法准确性和收敛性明显优于传统的K-means算法。这是因为在真正分类之前,本文首先采用Canopy算法对数据集进行了一次预处理,其基于“最小最大”原则对要进行分类的数据集先进行了一次“粗糙”聚类,确定K值及初始中心点,避免了随机选取的盲目性,提高了聚类的精度和收敛的速度;而后再使用经过三角不等式原理优化的K-means算法进行真正的聚类,应用三角不等式原理的优点对需要进行距离计算的数据点进行了预先筛选,避免了过多的冗余计算,节省了必要时间的开销。尤其是当数据规模与维数变得更加复杂时,计算数据点与聚类中心点之间的距离就会变得更加繁琐,能够减少一定量的不必要计算对提高算法的运行效率是很有必要的。此外,为了进一步减少在相似性分组时数据点被误分的概率,本文还在加权聚类准则函数的基础上,增加了算法的收敛性判定,明显降低了稀疏簇数据对象被错误地分配到相邻的小而密集簇的可能性。其既继承了传统K-means的优点,又改善了聚类效果,减少了迭代计算中过程中质心被调整的次数,缩短了原算法的收敛时间,大幅度地提高了聚类的精度。
 
表4.9两种算法在Hadoop平台上的结果对比
历史数据 Hadoop平台算法 K值 质心调整次数 聚类准则函数收敛值 收敛时间/s 准确率%
数据集1 传统K-means
Canopy-Kmeans 82
76 75
50 =  90.1
 = 63.1 2.3
1.6 65.1
74.8
数据集2 传统K-means
Canopy-Kmeans 120
154 93
78 =  68.7
 = 55.1 5.7
2.8 72.9
88.5
数据集3 传统K-means
Canopy-Kmeans 240
235 132
124 =  59.4
 = 53.6 13.2
6.3 87.9
93.7
 
为了能更好的反映K-means算法优化前与优化后聚类准则函数收敛的效果,针对表1中所取的三组历史数据数据集,若用 表示优化前的K-means算法的准则函数值,用 表示优化后Canopy-kmeans算法的加权准则函数值,取误差 ,则准则函数运行结果的变化趋势可分别描绘为如下图4.4至4.6所示(注:聚类准则函数值没有单位,由于质心调整次数数值较大,在图形绘制的过程中对横坐标采用了等比例缩放)。
 
图4.4  数据集1的准则函数变化趋势图
 
 
图4.5  数据集2的准则函数变化趋势图
 
 
图4.6  数据集3的准则函数变化趋势图
从图4.4到图4.6可以看出,两种算法在迭代过程中聚类准则函数都会随着聚类质心调整次数的增加而不断的减少直至最后收敛为止,且两条曲线靠的越紧凑,其所对应的聚类结果也就越准确。反之,间距越大,聚类效果也就越差。但改进的Canopy-Kmeans聚类准则函数值 明显优于传统K-means算法的聚类准则函数值 ,这是因为优化后的结果簇中各数据对象在每次的迭代过程中更加趋近于紧凑和独立,进一步验证了本文算法优越性。
4.3.2算法的加速比分析
为了测试本文算法的加速比,在物流历史数据中随机选取了3个样本数据,其样本数分别为: 100万条,300万条,900万条。令5个数据节点逐渐参与实验中,从图4.7可以看出,本文改进的Canopy-Kmeans算法加速比随着数据规模和节点的增加成线性增长,当数据规模越大时,这种线性增长就越明显。此外,有图4.7也可以看出,随着主机节点的增加,加速比的增长速度也慢慢趋于平缓,这是因为当样本数据量一定时,集群中主机节点的增加反而增大了各个主机节点之间拉取数据的通信时间开销,降低了算法的运行效率。
 
图4.7  算法加速比曲线图
4.3.3算法的扩展性分析
由下图4.8可以看出,随着TastTracker任务节点的递增,算法运行效率整体上是在逐渐下降的,且数据规模越大,扩展性曲线下降就越趋于平稳。
 
                                                                                                                                                                                                    
  图4.8 Hadoop平台上的扩展性曲线图
这是由于在Reduce阶段各主机节点之间需要合并和传输大量的中间结果,任务节点的增加将会导致系统额外开销增大。随着节点的增加,数据规模越小,系统的额外开销所占用总的时间比例就越大,自然扩展率曲线波动也就越大,反之扩展性曲线就会越平稳。进一步观察可知,当节点数目一定时,随着样本数据量的增加,大数据量的运行效率明显优于小数据量的运行效率,尤其在第3个任务节点上,集群处理900万条数据集的运行效率明显高于运行100万条的数据集。这是因为当数据量增加时,集群处理数据的有效时间占用总时间的开销比例将会远大于各节点之间的额外通信开销,这充分说明了本文所设计的算法具有良好的扩展性。数据规模越大,Hadoop集群越容易发挥它的并行计算能力。
4.4本章小结
本章首先介绍了实验的软硬件环境及数据采集,并根据第三章介绍了本文提出的基于双MapReduce编程模型改进Canopy-Kmeans算法的基本步骤,为了检验本文提出算法的实际性能,本章利用分布式Hadoop平台分别实现了传统K-means算法、本文改进的Canopy-Kmeans算法,为了进一步验证本文算法设计的可行性,采用社发物流公司真实的历史数据,以寻找社发物流公司的关键客户群体为例进行了大量的实验。实验结果表明,设计的并行算法在聚类结果的准确性、加速比、扩展性等方面都有显著的提高。成功地解决了K值及Canopy中心点选中存在的问题,避免了迭代过程中冗余的距离计算,提高了原算法的收敛速度,并且数据规模越大、节点越多,改进的效果就越显著。
 
5结  论
随着大数据的兴起,数据挖掘技术越来越受到企业用户的青睐。现有的大数据聚类挖掘算法由于处于起步阶段,存在着各种各样的问题,还不能直接应用于企业数据中。如何将现有的大数据技术与企业复杂的历史数据结合起来进行分析和提供推荐服务,是目前众多研究者的共同追求。本文正是围绕这一问题进行深入展开研究的。
(1)通过阅读大量的数据资料和文献,本文在传统 算法研究的基础上,成功将 大数据平台与基于“ ”原则改进的 算法和基于 原理改进的 算法相结合,并在加权聚类函数的基础上增加了算法的收敛判定,最后设计并实现了一种基于双 编 改进的 算法。
(2)以社发物流企业的历史数据为实验对象,结合了其它行业数据评估分析的经验,通过对客户的交易量、盈利能力(利润)、交易的频率(订单数量)和信用度等数据和特点的分析,利用本文改进的Canopy-Kmeans 聚类算法构建了关键客户价值评价体系模型,并对社发物流公司的客户进行了分组,寻找到了关键客户群体。
(3)接下来对已建立的数学模型进行设计与实现,并部署在hadoop 集群上进行反复实验和优化。通过实验表明,改进的算法,在聚类准确率、加速比、扩展性等方面都具有很大程度上的提高,可以有效应用于海量的数据挖掘中。与传统的K-means算法相比,其在大数据的处理上具有明显的优势,并且集群节点越多,数据越复杂,其处理的效果就越明显。这些特性对当前各行各业急需要处理的海量数据来说,具有非常重要的研究意义和使用价值。
虽然,本文设计的算法虽然达到了预期目标, 但是由于时间限制以及本人研究水平有限,论文中还存在着许多不足之处:
(1)本文所改进的Canpy-kmeans算法对于非等轴状分布、具有噪声或孤立点的数据较为敏感,对聚类的质量影响较大,需要进一步的改善。
(2)本文算法对聚类结果呈现为条形状和非凸面形状的数据集分类效果较差,且Canopy中心点在在复杂高维数据空间上生成较为困难,对聚类精度影响较大,需要进一步提高生成Canopy中心点的效率。
参考文献
[1] 程学旗,靳小龙,王元卓等. 大数据系统和分析技术综述[J].软件学报, 2014, 09.
[2] 陈欣,胡梦文,陈娇.国际物流研究热点分析[J].物流工程与管理, 2014,11.
[3] 王慧.基于hadoop的并行挖掘算法的研究[J].计算机应用技术,北京:首都师范大学,2013.
[4] 段圣贤. 第三方物流的客户关系管理研究[J].物流科技,2006(6): 98-99.
[5] 赵刚. 第三方物流企业客户关系管理[J].物流科技,2015,01.
[6] Marcia P, Ainrik S, Peter R. Quick response supply chain alliances in the Australian testiles,clothing and footwear industry [J]. International Journal of  Production Economics ,1999,(1-2):119-132.
[7] Remko I,Van H.Role of third party logistic services in customization through postponement [J]. International Journal of Service Industry Management,2000,6(4):230-231.
[8] Boban T.Development of motor thid party liability[J].Social and Behavioral Sciences, 2012, 10(8):56-58.
[9] 毛典辉.基于MapReduce的Canopy-Kmeans改进算法[J].计算机工程与应用,2012.48 (27): 22-26.
[10] 赵庆.基于Hadoop平台下的Canopy-Kmeans高效算法[J].电子科技大学,2014, 27 (2): 29 -32.
[11] 雷小锋,谢昆青,夏征义.一种基于K-means局部最优性的高效聚类算法[J].软件学报, 2008,19(7): 1683-1972.
[12] 武霞,董增寿,孟晓燕.基于大数据平台Hadoop的聚类算法K值优化研究[J].太原科技大学学报,2015. 
[13] 张顺龙,库涛,周浩.针对多聚类中心大数据集的加速K-means聚类算法[J].计算机应用研究,2015,9.
[14]常晋义,何春霞.基于三角不等式原理的K-means加速算法[J].计算机工程与设计.2007,11,28(21).
[15] 虞倩倩,戴月明,李晶晶.基于MapReduce的ACO-Kmeans并行聚类算法[J].计算机工程与用, 2013, 49(6):117-120.
[16] Qian Yanjiang. Research and implementation on the technologies of mining of massive datasets [D].Chengdu: University of Electronic Science and Technology of China,2009: 27-55.
[17] 赵卫中,马慧芳.基于云计算平台的并行K-means聚类算法设计研究[J].计算机科学, 2011.
[18] 周丽娟,王慧,王文伯.面向海量数据的并行K-means算法[J].华中科技大学学报(自然科学报), 2012 (SI):150-152.
[19] Cui Xiaoli,Zhu Pingfei,YangXin,et,al.Optimized big data K-means clustering using MapReduce [J].The Journal of Supercomputing,2014,70(3):1249-1259.
[20] Saeed Shahrivari,Saeed Jalili.Single-pass and linear-time K-means clustering based on MapReduce,in:Information Systems,2016,pp.12-36.
[21] 贾瑞玉,管玉勇,李亚龙.基于MapReduce模型的并行遗传K-means聚类算法[J].计算机工程与设计,2014,2(2):31-35.
[22] 江小平,李成华,向文等.K-means聚类算法的MapReduce并行化实现[J].华中科技大学报,2011.
[23] Qiu Rongtai.Research on MapReduce application based on Hadoop[D]. Polytechnic University of Henan,2009:17-32(in China).
[24] 温程.并行聚类算法在MapReduce上的实现[D].杭州:浙江大学,2011.
[25] 唐振坤.基于Spark的机器学习平台设计与实现[D].厦门:厦门大学,2014.
[26] 孙秀娟,刘希玉.基于新聚类有效性函数的改进K-means算法[J].计算机应用,2008,(28) .
[27] 张雪凤,张桂珍,刘鹏.基于聚类准则函数的改进K-means算法[J].计算机工程和应用,2011,47(11). 
[28] Banerjee A,Ghosh J.On scaling up balanced clustering algorithms[C]//Proceedings og the 2nd SIAM ICDM,Arlington,VA,2002:333-349.
[29] 叶于林,夏秀渝等.对K-means及势函数聚类算法的研究与改进[J].计算机系统应用, 2015,24(4).
[30] Shi Yunping. Analysis of K-means algorithm using the average error criterion function E. Computer and information technology,2004.
[31] Liu Yuanchao, Wang Xiaolong, Liu Bingquan. An improved initial value selection algorithm for K-means document clustering[J].High Tech Communication,2006.
[32] Dean J, Ghemawat S. MapReduce:simplified data processing on large clusters[C]. Proc- eedings of the 6th International Conference on Operation Systems Design & Implementation (OSDI), Berkeley, CA,USA,2004:137-150.
[33] ElkanC. Using the Triangle Inequality to Accelerate K-means[C].Proceedings of the 20th International Conference on Machine Learning, Washington DC,2003.
[34] AndrewWM. The Anchors Hierarchy: Using the Triangle Inequality to Survive High Di -mensional Data[C].Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence,2000.
[35] 何春霞.三角不等式原理对聚类算法的改进[D].兰州:兰州大学,2006.
[36] 谭跃生,杨宝光.Hadoop云平台下的聚类算法研究[J].计算机工程与设计,2014,5(35).
[37] 孟海东,任敬佩.基于云计算平台的聚类算法[J].计算机工程与设计,2015,11(36).
[38] 高榕,李晶等.基于云环境K-means聚类的并行算法[J].武汉大学学报,2015,8.368-374.
[39] Hamerly,Elkan.big data: how do your data grow ? Nature 455(7209) (2008) 28-29.
[40] Pelleg,Moorede.Efficient algorithms for agglomerative hierarchlcal clustering methods, J. classif. (2014)7-24. 
[41] Bradley,Fayyad. Parallel k-means clustering based on MapReduce. In: Cloud Computering, Springer, Berlin, Germany, 2009, pp. 674-679.
[42] Khan, Ahmad.Parallel K-means clustering of remote sensing images based on Mapreduce. In : Web information systems and mining springer, Berlin. Germany, 2010, pp. 162-170.
[43] Deelers,Auwatanamongkol.data clustering: 50 years beyond K-means, pattern Recognit. Lett. 31(8) (2010) 651-666.
[44] Pena. High performance parallel k-means clustering for dist-resident datasets on multi-core cpus, J.Supercomput. (2014) 1-19.
[45] Likas ,M. Chowdhury, M.J. Franklin, S. Shenker,I. Stoica. Spark: clustering computing with working sets, in: Proceedings of the 2nd USENIX conference on Hot Topic in Cloud Computing. 2010, pp. 1-10.
[46] Bradley. Balazinska, M, D.Emst, Hadoop : efficient iterative data processing on large clusters. Proc. VLDB Endow. 3(1-2) (2010) 285-296.
[47] Nittel,R. Jaiswal, C. Monteleoni, Streaming k-means approximation , in: Advances in Neural Information Processing System, 2009, pp. 10-18.
[48] Ahmad,Dey J. Sanderm, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise. In: KDD96, vol.96,2009, pp. 226-231.
[49] K. stoffel, A. Belkoniene. Parallel k/h-means clustering for large data sets, in: Euro-par99 parallel proessing, springer,Toulouse, france, 2013.pp.1451-1454.
[50] Y,Low,D.Bichson,J. Gonzalez.C. Guestrin, A. Kyrola.J.M. Hellerstein, Distnboted graphl -ab: a framework of maching learning and data mining in the cloud, Proc.VLDB Endow,5(8)(2012) 716-727.
[51] K.Kwerdprasop,N.Kerdprasop,P.sattayatham.Weighted k-means for density-biased cluster -ing, in: Data Warehousing and knowledge Discovery, Springger, berlin, Germany,2005, pp. 488-497.
[52] R.Mortazavi,S. Jalili. Fate data-oriented microaggregation algorithm for large numerical datasets ,Knowl.-based Syst.(2014)1-25.
[53] J. Nickolis, I. Buck. M. Garland, K. Skadron.Scalable parallel programming with cuda, ACM Queue6(2)(2008)40-53.
[54]石云平.使用平均误差准则函数E的K-means算法分析[J].计算机与信息技术,2004,02.
 [55] 刘远超,王晓龙,刘秉权.一种改进得K-means文档聚类初始值选择算法[J].高技术通讯, 2006,6(2): 78-90.
 [56] 韩岩,李晓.加速大数据聚类K-means算法的改进[J].计算机工程与设计,2015,05.
[57] Hadoop生态系统介绍.中国.[2015-09-05]. https://www.douban.com/note/515645004.
[58] 段云峰.大数据和大分析[M].人民邮电出版社,2015,10.
[59] 孙昊.数据挖掘技术在物流企业关键客户组合业务中的应用研究[D].安徽:安徽工业大学, 2013.06.
[60] 刘宝龙,苏金.双MapReduce改进的Canopy-Kmeans算法[J]. 学报. 2016, 09.
 
 
攻读硕士学位期间发表的论文
[1] 刘宝龙,苏金.双MapReduce改进的Canopy-Kmeans算法[J]. 学报. 2016, 09.
[2] 刘宝龙,苏金.基于Hadoop平台的K-means聚类算法的优化与实现[J].计算机系统应用.2016,10.
 
致  谢
本论文能够顺利的完成,与刘宝龙教授的悉心指导和帮助是分不开的。无论是从论文的选题、中期的理论研究,还是到大论文的写作及软件设计的整个过程中刘老师都给予了我亲切的关怀和极大的鼓励,在此,我表示衷心的感谢。他认真务实的科研精神及严谨的治学态度将使我受益终身。在学习中刘老师总是尽心尽力地指导我的课题研究,他每提出的一个问题,指导的一个思路,都令我有一种豁然开朗的感觉,使我在整个课题的研究和写作过程中不致于迷失方向,少走了许多弯路,迅速提升了我的专业研究水平。能够顺利的完成毕业论文的撰写工作,除了自己认真刻苦的钻研外,这与刘老师的悉心栽培是分不开的;在生活中刘老师和蔼可亲,平易近人,为人谦和,每当我遇到困难的时候总是不遗余力去地支持我和帮助我,对于刘老师给予的关怀与帮助我将终生难忘。
时光荏苒,三年的研究生生活就快走近尾声,感谢 能够给予我这三年的学习与提高的机会。在三年的时光里,我经历了许多,也学到了很多,使我在不断成长的过程中积累了许多宝贵的知识财富。在这里,感谢所有的授业恩师,您们渊博的学识和专业素养不仅仅让我掌握了扎实的专业技能,还让我学到了许多为人处事的道理,开阔了我的视野。再次感谢您们孜孜不倦的教诲!
感谢师兄师姐们在学习生活中给予我的关怀与帮助,也感谢可爱的师弟师妹们,谢谢您们一直以来对我的支持和鼓励,谢谢您们陪我一起走过这段岁月,同时也感谢那些帮助过我、关心过我、鼓励过我的同学们。正是因为有了您们的支持、鼓励与帮助,才使我有了更加坚定的信念,来完成毕业论文的设计。在整个毕业论文的撰写工作中,我自身也有了长足的发展与进步,不仅使我学到了一些新的技术,也增强了我自身的知识储备和学术涵养。我为自己感到庆幸,谢谢您们三年以来的陪伴、照顾和激励。
同时,也感谢西安市未央区科技项目基金(项目编号:201609)对本课题的大力支持和资助!
最后,衷心的感谢为本论文评审而付出了辛勤汗水与心血的各位专家和教授!由于时间仓促以及个人的能力水平有限,本论文在撰写的过程中肯定存在许多不足之处,希望各位评审专家和教授能够给我多多指正与批评,谢谢!