信息爆炸式增长，企业迫切需要对海量数据进行及时、准确地处理，以获取潜在的、有价值的信息，云计算集网格计算、分布计算、并行计算、效用计算、网络存储、虚拟化、负载均衡等技术于一体，具有海量的存储能力和可弹性变化的计算能力，成为解决该问题的有效方式，自Google提出GAE(Google App Engine)后，各种云计算产品纷纷出现：Apache的FIadoop，Amazon的AWS(Amazon Web Services)，微软的Windows Azure，IBM的Blue Cloud，SalesForce.com的SFDC等，遗憾的是以上公司并没有将研发的云计算架构大规模应用于数据挖掘领域，而市面上各种通用数据挖掘工具，如SAS的EntERPrise Miner，IBM的SPSS Modeler等，价格昂贵，对海量数据分析的效果欠佳。
基于云计算平台研发的数据挖掘产品，比较有名的包括：中国科学院计算所研发的PDMiner(Parallel Distributed Miner)，提供基于Hadoop的数据处理能力，但数据预处理能力有限，部分挖掘算法的并行策略还需改善；Apache软件基金会的开源Mahout，提供分类、聚类、频繁模式挖掘、回归、降维等算法，但缺少数据准备和展示过程，用户需要以编程方式调用算法；Source forge的开源Augustus，支持预测模型标记语言，可在Amazon的云计算平台上运行，虽提供了强大的建模能力和稳定的平台支撑，但对数据预处理工作关注太少：德国Fraunhofer在开源数据挖掘软件WEKA和开源云平台Hadoop之上实现了图形化的数据挖掘工具包，虽解决了WEKA单机运行的缺陷，但WEKA无法为用户提供完整的业务流程；Radoop以Hadoop，Hive，Mahout为基础，对RapidMiner进行了扩展，并以拖拽方式配置海量数据分析流程，但它尚处起步阶段，且依赖于底层Mahout提供的分析算法，只能完成部分常用的数据分析工作。
而学术界从2011年起，对于将MapReduce这一云计算框架应用于数据挖掘领域的研究和讨论逐年增多，例如，Robson使用MapReduce实现多维度大数据的聚类；Alina实现了快速聚类算法；Herodotos通过他们的“profing and what-if engine”提升了MapReduce的效率，种种现象表明，MapReduce适合于开发并行数据挖掘算法。
总之，目前的并行数据挖掘工具在功能、处理能力、用户体验等方面存在一些不足，更明显的是它们着眼点或者是科研，或者是简单应用，并没有以大规模企业应用为背景，适应大型企业商务智能应用需求。以电信行业为例，为了正确分析用户数据，获取有价值的知识，更好地提供服务，发现商机，制定营销、资费等策略，不少电信运营商自主开发基于云计算的新型数据分析工具。例如，国外AT&T推出了Synaptic，Verizon推出了CaaS；国内，中国移动提出“大云计划”，电信提出了“星云计划”，联通开发了“互联云”。
本文介绍一款基于Hadoop的并行数据分析系统PDM(Integrated Parallel Data Mining)，它以全球最大电信运营企业——中国移动的商务智能应用需求为背景，旨在针对海量数据提供高效、准确、便捷的数据分析服务。本系统具有强大的数据预处理能力，优化了传统算法的并行策略，既适合简单的数据分析，也支持复杂的业务逻辑。更重要的是，系统将数理统计功能、文本分析、图挖掘能力与传统数据挖掘工具相结合，丰富了数据处理的方法和能力，本系统还针对电信数据，开发了一系列典型应用，并在中国移动多个省公司试点运行。
本文结构如下：第1章系统整体架构，说明各层的功能和特色；第2章并行多元回归算法和并行多源最短路径算法的设计与实现；第3章基于本系统开发的典型应用；第4章系统性能测试结果；第5章总结全文，说明后续研究工作。
1 系统架构
如图1所示，本系统包含：提供云存储和计算环境的云平台层，提供数据分析核心能力的算法层，提供业务支撑的逻辑层和提供用户交互功能的界面层。
图1 系统架构
1.1 云平台层
提供计算和存储能力，主要由一系列第三方开源软件组成。
云存储框架：由分布式文件系统HDFS(Hadoop Distributed File System)、分布式数据库HBase(Hadoop Database)和分布式数据仓库工具Hive构成，实现数据分布式存取。
云计算框架：由Hadoop的MapReduce模型，提供并行计算、数据发送和错误控制等功能。MapReduce使用极为简单，以64MB为单位自动将文件划分成数个片段，并送入各计算节点，执行用户定义的Map（映射）过程，输出key/value的键值对；经过一次混洗和排序，把具有相同key值的键值对，传送到同一个Reduce（归纳）过程；最后根据用户定义的Reduce，完成处理，将结果保存在分布式集群上。
数据组织模块：加载不同格式的数据；根据内容快速查询数据；针对云计算系统常存在缺乏数据来源的问题，本系统提供数据交换功能，保证数据在本地机器、指定服务器、分布式文件系统、分布式数据库、传统数据库之间，快速、无缝地转换和传递，便于与现有软硬件设施相结合。
监控采集模块：对任务进度、计算资源、存储资源进行监控，并收集各节点产生的日志。
1.2 算法层
算法层包含大量并行数据分析算法，能高效准确地处理各种结构化、半结构化、非结构化数据。算法层所包含的功能如下。
数据分析模块。提供核心数据处理能力，包括4类并行算法集。
并行数据预处理算法集：实现抽取(Extract)、转置(Transform)、加载(Load)等数据预处理操作，为后续数据分析奠定基础，含37种算法，主要分为：对数据类型和取值进行约束、选择的“清洗类”，进行转换操作的“转换类”；进行计算操作的“计算类”；对数据进行分割、采样的“抽样类”；进行集合运算的“集合类”；进行更新或插人数值的“更新类”。
并行数据挖掘算法集：将传统的数据挖掘算法并行化，以满足海量数据的处理要求，含16种算法，主要分为：有监督的“分类”学习算法；无监督的“聚类”学习算法；从数据中发现平凡相集的“关联规则”算法。
并行数据统计算法集：针对数值型数据求解某些统计特征值，从不同角度反映数据的特性，含22种算法，主要分为：反映数据中心点位置的“集中趋势”；反映数据变异程度的“离散趋势”；描述数据分布形状和对称性的“分布趋势”；计算不同组数据相关程度的“相关性分析”；根据一定假设条件由样本推断总体的“假设检验”。
并行文本挖掘算法集：含11种算法，通过文本预处理、聚类、分类等一系列方法，实现在海量非结构化文本数据中提炼知识的目的。
并行社会网络分析算法集：社会学家以数学方法、图论等为基础，提出社会网络分析(SNA，Social Network Analysis)，对网络中各种关系进行精确的量化分析，建立“宏观和微观”之间的桥梁．本算法集含22种算法，分为：针对点、边、网络进行分析的“点特征”、“边特征”、“网络特征”算法；寻找网络中所有的派系，并根据重叠关系产生社团网络的“社区发现”算法；挖掘网络中社团在不同时间段上的演化关系的“社区演化”算法。
算法模型模块，采用W3C(World Wide Web Consortium)认定的PIVWIL(Predictive Model Markup Language)标准，描述和存储数据挖掘模型；采用OMG(Object Management Group)制定的CWM(Conunon Warehouse Meta model)标准定义元数据，以便其它数据仓库工具能够理解各自的元数据含义。
接口封装模块．以Java API，WebService，REST(Representational State Transfer)3种方式封装算法，以便算法的调用和二次开发。
1.3 逻辑层
逻辑层对存储资源、计算资源进行调控和管理，并以流程驱动的方式分析数据。本系统支持分支、选择等多种复杂结构；支持多条流程组合业务的方式；提供流程和业务两个层次的调度功能，为用户创建符合需要的数据处理步骤创造良好的平台支撑。
1.4 界面层
基于富客户端的web应用，为用户创建数据处理流程或业务提供良好的使用体验。
2 核心算法介绍
由于算法众多，且篇幅有限，本章选取了数据挖掘算法集中的并行多元线性回归算法，以及社会网络分析算法集中的并行多源最短路径算法进行介绍。
2.1 并行多元线性回归算法
用于确定因变量y和自变量X1，X2，…，Xp之间的关系。
首先，假设式(1)成立，其中ε～N(O，σ)，β1，β2，…，βp以及σ为参数，如果p>2，式(1)就是线性回归模型：
求解线性回归模型参数的最基本方法是最小二乘法。当式(2)达到最小时，用最小二乘法计算向量β。根据式(3)得到β的估计值β：
建立线性回归模型，先计算训练集中自变量和因变量的平均值，然后利用这些均值计算矩阵L中每个元素。假设矩阵中的元素是l(i，j)，则式(4)成立，其中X(i，j)是原始矩阵中元素，avg(X(i))是原始矩阵中第i列的平均值，N是向量的个数，k的取值范围是1到n。
以类似的方法计算向量B。假设l(i，y)是向量B的元素，可由式(5)求得：
根据式(6)，得到回归参数β向量，其中L-1可由Gauss-Jordan算法求得：
综上，算法的步骤如下：
Step1设置MapReduce任务，计算矩阵L和向量B的平均值；
Step2根据式(4)和(5)计算矩阵L和向量B的全部元素；
Step3根据式(6)计算向量p。
2.2 并行多源最短路径算法
最短路径问题是图论中的经典问题，而Dijkstra算法和Floyd-Warshall算法分别求解单源和多源最短路径。基于MapReduce的单源最短路径算法可由Dijkstra改进而成；但Floyd-Warshall以邻接矩阵作为输入，而MapReduce仅适合读入邻接链表，并行多源最短路径的求解无法基于Floyd-Warshall算法进行改进。一种解决方案是将并行单源最短路径解法迭代多次，但系统开销大，实用性低，本文提出了一种基于MapReduce的多源最短路径的算法。
建立消息传递模型，每个节点都有一张消息表，即mesTable，用于保存到达该节点的消息。消息的内容包括消息的源节点(发送该消息的源节点，srcld)，源节点到该节点的距离(distance)和消息的状态(state)。模型按如下方式进行消息传递：
Step1在各节点中的mesTable中添加第一条消息记录，消息的源节点是节点自身，到该节点的距离为0，并将消息状态置为active。
Step2将mesTable里的所有active状态消息的distance和节点的邻接边的权值相加，并将该消息发送给该邻接边所对应的邻接节点，最后将该消息状态置为inactive。
Step3 当一个节点收到新消息后，如果mesTable中未包含与新消息来自同一个源节点的消息，则将该消息放入本节点的mesTable中；反之，如果mesTable存在与新消息来自同一个源节点的旧消息，此时，若新消息记录中的distance小于旧消息中的distance，则用新消息更新旧消息，并置该消息状态为active。
Step4重复步骤2，3，直到所有节点中的消息记录状态均为inactive。
该模型易用MapReduce实现：在Map函数中，读入节点邻接表及mesTable，并向邻居节点发送消息；在Reduce函数中，接收新消息，根据Step3的内容更新节点的mesTable。
3 典型应用
本系统不仅提供通用的数据挖掘能力，还能针对不同数据集快速开发多种应用，例如用户行为分析、用户兴趣识别、客户流失预测、网络质量分析、用户的多重身份识别、家庭用户的社团发现等等。本节将介绍利用电信数据开发的“套餐推荐”和“营销关键点发现”两种典型应用。
3.1 套餐推荐
背景：电信用户的消费行为具有特定的模式。发现这些消费模式，能为人网新用户推荐适合的业务，并针对新的消费需求推出新业务。
原理：利用了“客户细分”和“客户分类”两种技术。客户细分，用于发现具有相似消费行为的客户，为发现消费群体的消费行为特征，及时制定符合消费行为的套餐业务提供可能，常采用无监督的聚类学习方法；客户分类，是建立一套数据模型，发现客户各属性与客户所选套餐之间的隐含关系，达到分类的目的。
实现：将39列、约300万条记录的原始通话数据，进行预处理，选出20列数据——主要包括用户、费用、语音（主叫、被叫、本地、漫游、长途等各种情况下的通话次数和总时长）及短信等信息；采用并行k均值算法实现客户细分，将客户划分为6类：高端客户、高端通话客户、高端增值业务客户、中端通话客户、终端增值业务客户和低端客户；利用所得客户类标号，以套餐编号作为分类属性，采用并行C45的决策树分类方法，建立客户分类模型；最后将模型用于预测新用户的潜在行为，为新人网用户的套餐推荐方案提供决策支持。
结果：在86个计算节点上，对29GB原始数据（含100万数据）进行分析，共耗时37分46秒。建模准确率达到89.03%。证明本系统对传统数据挖掘问题的处理，效果不俗。
3.2 营销关键点发现
本节将介绍采用并行社会网络算法开发的典型应用——“营销关键点发现”。
背景：营销关键点，是自身消费对其他客户消费有较大影响的点。通过探索营销关键点，可开拓新的营销渠道，针对关键点进行业务推广，提高营销效率。由于营销关键点对周围客户的消费行为影响较大，该客户离网会加大周围客户离网的概率，因此需要对关键客户进行消费跟踪，及时预测消费行为。
原理：Google提出了PageRank算法，用于衡量特定网页相对于其他网页的重要程度，将网页改为用户t将链接改为用户间的通信关系，可将PageRank应用于营销关键点的发现上。PageRank值越大意味着该用户影响力越大。PageRank的计算是一个迭代过程，需要获得邻居节点的信息，这是通过消息传递模型实现的。
实现：选择原始通话数据中的主叫号码、被叫号码、通话时长等属性进行建模，并去除通话时间、短信数量极小的用户记录，形成输入数据；利用并行社会网络分析算法集的PageRank方法，构建网络拓扑结构，找出通话网络中的PageRank值较高的点，作为营销关键点。
结果：在92个计算节点上，对含有340万个通话节点的数据进行分析，共耗时约1小时46分钟，输出结果按用户的影响力降序排列，证明本系统的图挖掘功能拓展了数据挖掘的应用范围，具有很好的效果。
4 系统性能
本文对PDM进行了测试，测试环境：各节点CPU为Intel (R) Xeon (R) CPU E5504 @ 2.00GHz、4核，内存为8GB，硬盘1TB；节点之间传输速度为31.5MB/s～33.8MB/s；测试数据大小为403 GB.测试的部分结果如下：
在10个节点上，系统响应100个用户同时登录平均时间是3.32s；
在10个节点上，对于典型的并行数据挖掘、统计算法需要2h左右(如图2)；
图2 数据挖掘、数据统计算法的性能测试结果
在5个节点上，对分组计算和缺值处理算法进行扩展性测试，图3显示，随数据规模的增大，算法耗时呈线性增长，具有良好的扩展性。
图3 分组计算和缺值处理算法的性能测试结果
社会网络分析中，如果数据量过大，串行算法消耗的资源和时间是难以接受的。表1显示，在30个节点上，将Map个数和Reduce个数都设置为60，本系统的数据替换、度数统计、均值、最大值、边点统计、单源最短路径、接近度(Closeness)等算法计算复杂度为线性；聚集系数和社团发现算法容易受输入数据的影响，如果输入的网络具有比较大的局部密集子图容易造成计算的不均衡，会使某个Reduce的计算量急剧增加导致整体的计算时间较长，但它们在稀疏的网络中的复杂度近似线性，而通话网是一般是稀疏网络，因此适用于分析通话数据。
表1 社会网络分析的性能测试结果
5 结论
本文从系统架构、核心算法介绍、典型应用、系统性能等多个角度，全面介绍了一款基于Hadoop的并行数据挖掘系统，本系统融合了数理统计、文本分析及图挖掘技术，扩大了传统数据挖掘的范围和效果；针对传统MapReduce的并行计算机制，优化了数据处理流程的性能；提供的数据组织功能，解决了HDFS数据来源问题，增加了类数据库处理能力；业务引擎，能自由组合各类分析算法，满足不同层次的要求，易于开发典型应用，因此，本系统性能优越、功能丰富、商用前景广泛，是一个前沿且注重实用的实践．下一步的工作有：继续添加数据分析算法，优化算法性能；对于一些不便于用MapReduce机制处理的算法类型，可以探索新的并行计算模型，例如考虑融入图数据存储和计算框架，提高图挖掘的效率。
转载请注明出处：拓步ERP资讯网http://www.toberp.com/
相关文章
