基于云聚类挖掘的物流信息智能分析方法研究_聚类论文

基于云聚类挖掘的物流信息智能分析方法研究，本文主要内容关键词为：物流论文,智能论文,方法论文,信息论文,云聚类论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。

      1 相关研究回顾

      作为国民经济先导性、战略性、技术性的产业，物流业近年来插上了快速腾飞的翅膀，智能物流信息平台的建设如火如荼。在物流智能化进程中，国内外学者也对此展开了深入研究，有力地推动了物流业的实践发展。在此类研究成果中，有部分学者将聚类挖掘作为实现物流信息智能分析的手段与工具，并提出了相应的物流信息智能分析理论、模型与方法。

      例如，国外学者Min H.等针对产品回收的逆向物流网络选址问题，提出了一种非线性混合整数规划模型和遗传算法，实现多梯队逆向物流的网络选址优化[1]。Lee J.E.等为了实现逆向物流网络选址与优化，提出了一种遗传算法（GA）和基于优先级编码方法的三阶段逆向物流信息分析模型，以节省逆向物流的运输成本和拆卸成本[2]。Charles V.T.等通过应用结合沃德最小方差法和K-Means算法的两阶段聚类方法，对供应链伙伴进行细分，优化第三方物流服务提供商的服务，从而可以满足客户的特定偏好[3]。Mahmoudabadi A.等在对收集到的数据进行规范化处理后，提出了基于遗传算法的聚类分析方法应用于交通运输系统中超限检测站动态称重站的绩效优化方案[4]。Kargari M.等利用K-Means算法，以商店位置信息、货物订单信息、运输车辆信息、道路交通信息等为基础，对汽车零部件配送信息进行聚类挖掘，对汽车运输系统的路径进行优化，结果表明，能够显著降低汽车零部件配送和运输成本（高达32%）[5]。

描述了层次聚类与路径处理（Hierarchical Cluster and Route Procedure）模型在协调大规模灾后物资配送和疏散的车辆运输路径的应用，多层聚类与路径处理模型是一个多层次聚类算法，运行在一个并行计算平台上，可以实现物流路径的最优解[6]。Santos L.F.等针对人道物流配送的优化问题，提出了一种可靠的聚类方法来分析灾害数据和运输物质数据、运输线路数据，以辅助人道主义行动的物流优化决策[7]。

      例如，国内学者施宏伟和王发年提出了解决物流服务节点选择问题的自适应蚁群聚类算法，以物流系统总成本最低为聚类准则，构建了物流服务节点布局优化模型[8]。罗冬梅抽象出基于聚类算法的交叉环物流服务模型，对物流的服务模式、交叉环物流调度服务器等进行了设计[9]。李峰等采用K-harmonic Means聚类分析方法和重心法对企业的产品配送中心位置进行重新选择，以进一步优化配送中心的位置及各配送中心所负责的区域[10]。李姗姗针对物流服务供应链订单分配问题的NP-hard特性，设计了相应的遗传算法，能够在可接受的时间内获得质量较高的满意解，实现大规模订单分配的优化[11]。李国俊和张娜以2012年新疆14个地州市数据为样本，运用基于中心点混合三角白化权函数对新疆各地州市从物流发展方面进行灰色聚类分析，对新疆各地州市从物流发展水平进行区域划分[12]。

      诚然，上述学者的研究成果，对于推动聚类挖掘在物流信息分析中的应用，起到了很好的启发与引领效果。但是，目前的物流数据日益呈现出信息量大、数据类型复杂、数据异构性、地理分布广、高度动态性、时效性等特点，而上述学者所提出的相关模型、方法，多局限于一个企业内部，多针对静态物流数据，处理的数据量还偏小，且开发成本较高，挖掘效率不高，无法满足海量数据挖掘对计算能力的需求。事实上，如果对物流数据进行聚类挖掘分析，要求能做到实时动态挖掘、分布式挖掘、数据质量控制、模式符合决策个性化需求。不过，借助于云计算技术和动态数据挖掘技术，这些需求能很好地满足，也能很好地弥补传统物流数据聚类挖掘的不足。

      2 云聚类挖掘技术

      2.1 云聚类挖掘的概念

      随着通信技术和网络技术的发展，数据正以成百上千TB的速度增长，数据日益呈现出大数据化。传统的数据挖掘技术已很难适应海量数据的增长，对于实时数据或数据流的挖掘无能为力，对于个性化多样化的数据挖掘需求已难以满足。云计算由于其海量的存储能力和强大的计算与数据处理能力，成为解决海量数据挖掘的有效方式[13]。在此背景下，数据挖掘已发展到第五代：基于云计算的并行数据挖掘与服务[14]。

      云计算与数据挖掘技术相结合，形成了云挖掘技术。所谓云挖掘，是指由云计算技术支撑的并行数据挖掘，即基于云计算平台的并行数据挖掘，以实现海量数据的高性能、高可靠性的存储、分析、处理及挖掘。

      聚类挖掘是数据挖掘中最常用的方法之一，以“物以类聚”的形式，将物理或抽象对象的集合组成若干个相似类群或簇的过程，是一种对数据进行分类的多元统计方法。簇是数据对象的集合，聚类挖掘通过对数据进行划分，对目标数据在没有训练的情况下分为若干组，把相似的对象通过静态分类的方法归类到一个簇中，同一簇中的数据具有相似的一些属性，不同簇中的成员尽可能相异，目的是通过总结发现新的规律与特点，帮助挖掘出新的有价值信息与知识[15]。聚类是一种无监督的算法，主要基于当前所处理的数据，对数据的具体类别和数据结构事先并不清楚，需要通过多次迭代来构建模型，最终达到聚类结果。

      将聚类挖掘算法与云计算技术相结合，运行在云计算平台之上，通过MapReduce的并行化，实现云计算技术支撑的并行数据聚类挖掘，可以对海量数据进行高性能、高可靠性的存储、分析、处理及挖掘，这就是云聚类挖掘方法。

      2.2 云聚类挖掘的实现原理

      云聚类挖掘的实现，其关键是实现聚类挖掘算法的MapReduce并行化，其实现框架如图1所示。

      

      该实现框架以实现聚类算法的MapReduce并行化为核心，整个框架的构成主体为：一个Master、若干个Mapper、一个Reducer。从图1可以看出，基于云聚类挖掘的物流信息智能分析的MapReduce并行化可以分为三个阶段：初始聚类阶段、Map/分组聚类阶段和Reduce/聚类结果阶段。在初始聚类阶段，由Master对输入的数据进行初始化，根据用户需求与实践，按照数据的性质，生成若干个初始聚类中心。在Map/分组聚类阶段，由每一个Mapper根据相应的聚类算法与模式，计算数据对象与初始聚类中心之间的相似度，对数据集进行聚类，将属于同一聚类中心的数据对象归并在一起，形成相应的数据簇。在Reduce/聚类结果阶段，由Reducer对上一阶段生成的n个数据簇进行汇总，然后生成一个新的聚类中心。该新的聚类中心包含着聚类挖掘的结果，可以由平台以可视化的形式向用户提供，以帮助用户进行决策参考。

      适合于云聚类挖掘的算法主要是k均值聚类算法、层次聚类算法、CURE算法等，对于不同的算法，其实现过程都一样，同样包括三个阶段[16]。但对于不同的聚类算法，在MapReduce并行化过程中，需要具体实现不同的Map函数和Reduce函数。

      3 基于云聚类挖掘的物流信息智能分析模式

      基于云聚类挖掘的物流信息智能分析，就是在Hadoop平台的集群环境下，物流信息智能分析平台根据用户的需求，从各节点集群和云计算数据中心收集和处理相应的物流数据，调用相应的聚类挖掘算法，并实现该聚类挖掘算法的MapReduce并行化，挖掘隐含在物流数据流中的有价值信息，用于完成各种数据聚类挖掘任务，对挖掘结果进行知识描述，将物流信息分析结果展现给用户终端。

      基于云聚类挖掘的物流信息智能分析模式及其过程是：物流信息预处理；选择聚类挖掘算法；实现聚类分析的MapReduce并行化。

      （1）物流信息预处理。云聚类挖掘处理的物流信息，一般都是海量数据，会达到TB级，甚至是PB级；同时，这些物流信息类型多样，动态数据、冗余数据、噪声数据、稀疏数据、高维数据或不完全数据层出不穷，因此，需要进行物流信息的预处理，这是实现物流信息智能分析的前提。具体来看，预处理过程分为两个阶段：先是将广域分布的海量物流信息按概念分层进行组织，同时以并行的方法实现数据的加载；然后利用数据稀疏化技术和数据降维技术，对获得的物流信息进行过滤、转换、清洗、整合，避免数据丢失。通过对物流信息预处理，实现对获得数据的规范性、完整性、无二义性和无重复性，从而提高物流信息智能分析的效率。

      （2）选择聚类挖掘算法。选择适合的聚类挖掘算法，是实现基于云聚类挖掘的物流信息智能分析的基础。数据挖掘聚类算法经过若干年的发展，现已形成了众多的算法，如K-means算法、CLARA算法、K-medoids算法、EM算法、CLARANS算法、CURE算法、ROCK算法、BIRCH算法、OPTICS算法、Wave-Cluster算法、SOM算法、COBWEB算法等。但这些算法的使用场景有差异，不同的数据对象、数据类型、挖掘目标，选用不同的算法，其效率与质量将会有所不同。另外，这些聚类挖掘算法并不是都能适用于云计算MapReduce等新型计算模型，因此，根据用户多样化和个性化需求，需要综合考虑算法的MapReduce并行化的可行性，选择合适的聚类挖掘算法。

      （3）实现聚类分析的MapReduce并行化。聚类分析的MapReduce并行化是实现物流信息智能分析的核心与关键。MapReduce编程模型能在大量普通配置的计算机上实现并行处理，主要用于大规模海量数据集的计算任务[17]。具体实现上，需要结合物流信息用户的信息需求，结合云计算分布式计算和存储的特点，进行聚类挖掘算法的改进，通过对获得的物流信息进行存储管理、数据清理、算法调用、数据挖掘、结果评估、结果输出等作业，达到物流信息智能分析的结果，并以服务方式提供给用户。

      4 基于云聚类挖掘的物流信息智能分析算法

      基于云聚类挖掘的物流信息智能分析的核心与关键就是实现聚类挖掘算法的MapReduce并行化。本文以K-Means算法为例，实现K-Means算法的MapReduce并行化，探讨以该算法为基础的物流信息智能分析的实现过程。

      4.1 K-Means算法简介

      K-Means（K-均值）算法是划分法中一种非常经典的聚类算法，由MacQueen J.B.在1967年提出，支持在没有先验知识的情况下，实现对多个变量的分类处理，用于发现无类标号数据中的簇和簇中心，具有计算复杂度不高、实现简单、执行速度快等优点，适用于连续性较好的聚类效应[18]。

      K-Means算法的工作原理是：对于一个给定的包含n个数据对象的数据集，通过采取一种迭代的过程，以距离作为相似性的评价指标，以K为参数，将数据集随机分成K个子集，每个子集均代表一个初始聚类，然后计算各个样本与子集之间的距离，使每类中的数据点到聚类中心的距离最小，平均距离即为新的聚类中心；如果经过两次计算，得到的聚类中心相同，则实现了数据的聚类；如果不相同，则重复计算，直到达到相同的聚类中心点；每个聚类的所有数据对象都具有较高的相似度，不同聚类之间的数据对象相似度较小。聚类相似度是根据各聚类中对象的平均值来进行计算。将数据集划分为K个子集，需要满足以下条件：每个子集都至少要包括一个数据对象；模糊划分中，一些数据对象可以归于多个子集；一般划分中，每个数据对象只能归于一个子集。

      K-Means算法的工作流程是[19]：

      首先，以K为参数，从数据集中随机选取K个对数据对象，成为初始聚类中心；

      第二，根据各个聚类对象的均值，计算其余的各个其他样本对象到聚类中心的相似度（欧氏距离），并以最短距离为依据，分别将它们分配到最邻近聚类；

      第三，根据最小距离重新计算每个簇的新均值，将新均值规定为新的聚类中心；

      第四，循环过程，比较前后两次计算所得的聚类中心，直到聚类不再变化或满足某些停止条件为止，停止迭代过程，得到K个聚类。

      在K-Means算法的串行实现中，其时间复杂度是O（nkt），n为数据对象的数量，k为聚类个数，t为迭代次数，计算时间将会以n*k*t乘积的形式迅速增长。

      4.2 K-Means算法的MapReduce并行化的基本思路

      实现K-Means算法的MapReduce并行化，其基本思路是：

      首先，在物流信息智能分析平台上选择一台服务器作为主服务器（Master），剩下的都属于节点服务器（Worker）；

      第二，主服务器（Master）对输入的数据块进行分簇，共划分为K个初始聚类中心，存储在HDFS分布式文件系统中，作为全局聚类中心分发给各工作节点；

      第三，工作节点（Worker）从HDFS分布式文件系统中下载已初始聚类的数据对象和未聚类的数据对象，按行分片，且分片间无相关性；

      第四，每个工作节点启动对应的Map函数，计算数据对象到初始聚类中心的距离，选择距离最小的聚类中心点，形成新的数据对象集合及所对应的聚类中心；

      第五，对于属于同一聚类中心的数据对象，由主服务器（Master）将Map函数计算结果提交给Combine函数，然后对数据对象进行归并，生成簇数据的局部结果；

      第六，由主服务器（Master）将Combine函数的同一簇的局部结果提交给Reduce函数，同一聚类中心数据对象求和，得到所有簇的新的聚类中心，最终生成聚类挖掘结果。

      上述思路如图2所示。

      

      K-Means算法的MapReduce并行化的关键是设计（key，value）（键，值）对。

      4.3 Map函数的设计

      Map函数的主要任务是HDFS分布式文件系统中，将文件的每行作为一个样本，逐行读取数据样本，形成（key，value）键值对，然后计算每个样本到各聚类中心点的距离，将距离最小作为选择的原则，选择距离最小的聚类中心，将样本数据归属于该聚类中心，同时标记为新的聚类类别，产生一组新的（key，value）键值对，作为数据输出。Map函数的输入数据为初始聚类中心或上一轮迭代计算得到的聚类中心和待聚类的数据样本，（key，value）键值对用〈行号，记录行〉来表示，其中，行号是当前样本对于相对于输入数据文件起始点的偏移量，记录行是当前样本的各维坐标值。Map函数的输出中间结果表达形式为＜key′，value′＞对，用〈聚类类别ID，记录属性向量〉来表示，其中聚类类别ID表示的是距离最近的聚簇ID，记录属性向量表示的是与该聚类中心最为相似的数据对象的各维坐标值。

      Map函数的伪代码如图3所示。

      

      4.4 Combine函数的设计

      Combine函数是实现本地的Reduce操作，对本地Map函数执行完后产生的中间结果进行预处理，减轻数据在物流信息智能分析平台上的传输时间，降低带宽的占用，从而最大限度地利用计算资源。Combine函数实现了对Map函数输出键值对的重新洗牌，使得整个并行化显得更为高效。

      Map函数执行完任务后，系统启动Combine函数，在本地完成同一个聚类的点的求和，得到局部聚类结果的累加和，再传给集群中Reduce函数进行规约操作，减少Reduce操作的通信量和计算量。Combine函数的输入为Map函数输出键值对，用〈聚类类别ID，记录属性向量〉来表示键值对＜key，value＞，其中聚类类别ID表示的是距离最近的聚簇ID，记录属性向量表示的是与该聚类中心最为相似的数据对象的各维坐标值。Combine函数的输出为键值对＜key′，value′＞，key′为聚类类别ID，value′为全部样本对象与局部聚类的各维累加和，得到同一簇的局部聚类结果。

      Combine函数的伪代码如图4所示。

      

      4.5 Reduce函数的设计

      Reduce函数的主要任务是对Combine函数产生局部聚类结果进行汇总，并据此计算出新的聚类中心，生成全局聚类结果，并将其用于下一轮Map-Reduce函数，实现迭代运算。Reduce函数输入数据为Combine函数的输出结果，其形式同样为＜key，value＞键值对，其中，key代表为聚类类别ID，value代表各个Combine函数的局部聚类结果。Reduce函数输出结果为键值对＜key′，value′＞，key′为聚类类别ID，value′为均值向量，代表新的聚类中心。

      Reduce函数的具体实现流程为：首先，根据输入数据统计总样本对象的个数，并对每个样本各维坐标值进行解析；然后，计算各样本各维坐标值的总和，除以总样本对象的个数，得到新的聚类中心。该新的聚类中心是下一轮迭代运算的聚类中心。

      相应的Reduce函数伪代码如图5所示。

      Reduce任务执行完之后，根据输出结果计算新的聚类中心，同时将其更新到HDFS分布式文件系统中，并向所有节点分发。然后经过两轮计算MapReduce Job的误差平方和准则函数，判断结果是否收敛，如果差值小于设定的值，则结果收敛，可以得到最终的聚类结果；如果差值大于设定的值，则需要启动新一轮迭代MapReduce运算过程，将新的聚类中心作为Map函数的输入数据，直到最终趋于收敛为止[20]。

      4.6 算法复杂度分析

      相对于传统的串行K-Means算法，经过MapReduce并行化后，输入的物流数据并分割成若干个数据包，K-Means算法的执行由不同的节点来并行完成。假设有x个节点参与到K-Means算法的执行，总样本都是被分摊到x个节点中，则K-Means算法的时间复杂度是O（nkt）/x，n为数据对象的数量，k为聚类个数，t为迭代次数。可以看出，K-Means算法的时间复杂度，随着集群中节点数目的增加，将得到大大简化，运行效率大大提升。

      

      5 基于云聚类挖掘的物流信息智能分析方法的优势

      云聚类挖掘实现了云计算与聚类挖掘的完美结合，用户向云端提出数据聚类挖掘任务，云端则能调动相应的服务资源来满足用户需求，聚类挖掘与云计算相得益彰，相辅相成。将云聚类挖掘应用到物流信息分析之中，实现物流信息的智能分析，其优势主要表现为：

      （1）提高信息分析能力。云聚类挖掘充分发挥了云计算的优势，能够提供分布式并行环境，把各节点的能力有效地发挥出来，提高了大规模数据处理速度和能力，实现海量物流信息高效实时的聚类挖掘与分析，从而快速、及时、高效地获得物流信息分析结果。

      （2）缩减用户分析成本。对于中小企业来说，并不需要花费巨额资金购买相应的设备和软件，只需按需购买相应的服务，就可以获得高效的物流信息挖掘结果，其所节省的成本非常可观。对于大企业来说，海量数据处理的能力与效率得到提升的同时，其数据处理成本同样将大大地降低，减轻大企业对大型高性能计算机的依赖。

      （3）提供简便操作平台。对于用户来说，操作简单，使用方便，对数据分类、数据分配、数据加载到节点、工作任务调度、知识库建设、算法完善、计算分配等，都无需考虑，仅需通过网络登录到系统，菜单式按键操作，选择合适的算法来处理数据，就可以获得挖掘结果。

      （4）拓展用户群体范围。无论是大型企业，还是中小微企业，也不管是否具备数据挖掘能力和知识技能，都可以通过注册、付费的方式来利用云聚类挖掘，大大拓展了物流信息智能分析体系的用户群体基础。

      6 结语

      基于云聚类挖掘的物流信息智能分析方法，充分利用大规模的计算资源，实现海量物流信息的实时存储，利用计算机集群拆分分布式系统中的并行任务，并由不同的计算机处理拆分后的任务，大大提高数据处理的效率，能够实现物流信息分析结果的价值转换，将为物流战略决策、资源统筹、运营管理、路线优化、市场营销、销售管理、客户管理、配送选址、车辆调配等方面提供有力支撑，从而帮助企业优化管理，提高行业竞争力。

标签：聚类论文;  k-means论文;  mapreduce论文;  大数据论文;  层次聚类方法论文;  模糊聚类分析论文;  智能算法论文;  智能物流论文;  云计算论文;  并行处理论文;  用户研究论文;  用户分析论文;  数据挖掘论文;  数据分析论文;  k-means算法论文;  算法论文;