|
文 / 曾剑平 大数据分析所面对的数据量通常是巨大的，由此带来了高计算复杂度的问题。以往主要针对单机系统而设计的分析算法就难于在可接受的时间内完成任务，面向大数据分析处理的并行化分析算法就很有必要了。本文以通俗的语言和例子解释了大数据并行方法，描述了Kmeans并行化的原理。（关注微信公众号 IntBigData '互联网大数据处理技术与应用'获得更多互联网大数据技术介绍。） 一、数硬币
在投币乘车的年代里，公交公司每天会收到大量的硬币，假如公司要数一下某一天收到的硬币中一角、五角、一元三种硬币的个数。 问题本身很简单，三岁小孩都能区分这些硬币，但问题是硬币数量太大，一个工作人员来数要花多少时间? 假如每分钟能区分60个硬币，5万个硬币就需要数10几个小时。
显然，可以让多个工作人员一起数，有两种方法。一是，让所有工作人员围着这堆硬币数；另一种方法是把这堆硬币大概平均分一下，每个人自己去数。
前一种方法看起来很好，但是有的人在数数时，喜欢“1、2、3...”地发声来数，从而严重干扰其他人。所以第二种是不错的选择。每个人数完之后，报告给公司老板，老板把每个人一角、五角、一元三种硬币的个数分别加一下就可以得到结果。这样，如果5个人来数，那么两个多小时就可以完成任务了。这种数法就是并行化方法。
同样，大数据分析计算方法也采取类似的思路。在目前的计算平台中，并行化大都以Map Reduce为计算框架，每个人就相当于这个计算框架中的一台计算机，独立完成任务。当然这种计算框架为了能更具有普遍适应性，就对参与计算的所有计算机进行了适当组织。
还是以数硬币为例，尽管对硬币进行了大概的平均分配，但总是有人快有人慢，老板如果都要在现场等结果就不太合理了。因此，可以对这种人员结构做个调整，比如设置三个小组长A、B、C，分别负责汇总一角、五角、一元三种硬币个数，等收齐后再报告老板。
这样，员工数完之后，需要把结果报告给不同的组长，即一角的个数报告给A，五角的个数报告给B，一元的个数报告给C。任务分工也很清晰。
上述过程其实就是Map Reduce的计算原理，员工是Map节点，组长是Reduce节点，老板负责分配和记录最终结果，是总控。 二、Kmeans的并行化
Kmeans是数据聚类中经典方法之一，在上述Map Reduce框架中，其并行化方法如图所示。
步骤说明如下： 1. 对输入的数据集进行分割，老板按照一定原则分给各个计算节点（员工），并随机选择聚类的初始中心。 2. 每个计算节点负责分给自己的所有数据样本，对每个样本计算与每个聚类中心的距离，记录每个样本的最近中心，即（样本、最近中心）。 3. 每个计算节点完成后，按照中心与样本的对应关系，将样本数据传给相应的小组长。 4. 这样每个小组长负责一个类，在收到所有样本数据后，对这些数据计算新的中心。 5. 每个小组长将计算结果（类中心）报告给老板，老板根据Kmeans的收敛条件判断是否要进行第2-4步骤迭代，直到完成任务。 下图是传统实现方法和并行化方法在性能上的对比关系，可以看出，随着数据样本数量的增加，传统方法的时间消耗增加得很快。
当然由于Kmeans算法的特点，可以简单地将数据集进行分割，而在一些复杂的问题中，有时候要找到数据分割方法并不容易，需要先做一定的分解。在互联网大数据分析应用中，页面关系、用户关系、位置联系等等许多问题都可以抽象为矩阵运算，对于矩阵相乘这个大数据基础算法的并行化就很关键，具体计算方法就难于在这里展开了。在我编著的《互联网大数据处理技术与应用》一书中，一章描述了数据挖掘的经典算法及其并行化方法，分析了矩阵相乘并行化所需要考虑的关键因素，包括数据存储、矩阵数据在网络上的传输量、稀疏矩阵，稠密矩阵等许多问题。点击原文链接查看专著介绍。
|
|
|
