（国网晋中供电公司 山西省晋中市 030600）
摘要：对于以ZB 为基本计算单位的大数据挖掘，提出了基于Hadoop的海量数据挖掘算法。通过使用高效的K-means算法与MapReduce分布式计算模型相结合，根据数据自身的相似度，将大数据进行分片、分组、聚类，得到预处理数据并写入Hadoop的HDFS中。利用Hadoop自身对海量数据的存储能力和并行计算能力，在MapReduce框架中融入经典的Apriori算法，可以降低运算时间，提高算法效率，得到所挖掘数据间的关联规则。
关键词：K-means；Aprior；Hadoop集群；大数据；关联规则算法
1.引言
对于如何“开采”大数据以挖掘其内部蕴藏的“富矿”，这一问题已经上过《纽约时报》、《华尔街日报》的专栏封面，进入美国白宫官网的新闻，现身在国内一些互联网主题的讲座沙龙中，甚至被嗅觉灵敏的国金证券、国泰君安、银河证券等写进了投资推荐报告[1]。本文使用MapReduce模型，将高效的K-means算法[7]与MapReduce并行化，根据数据自身的相似度，将大数据进行分片、分组、聚类，得到预处理数据并写入Hadoop的HDFS中。在底层封装任务分配、并行处理的过程中，通过将经典的Aprior数据挖掘算法融入MapReduce中，即将Apriori算法与MapReduce并行化，可以高效得到数据间的关联规则[8]。
2.问题描述
由已有的观看历史集合推出可能感兴趣的还未观看的资源集合的推断关系是该问题的重点。如用户已有的资源观看历史集合t1，可能感兴趣的资源集合t2，则关联规则表示为：t1=>t2。为了得到有效合理的关联规则，并根据关联规则挖掘技术基本理论得到如下两个规则判定指标：
挖掘数据关联规则的实质是为找到满足用户定义的最小支持度（min_sup）和最小置信度（min_con）的t1=>t2。
本文数据来自明尼苏达大学GroupLeIIs研究小组。数据主要包含1，000，209组评级信息、3952部电影信息和6040位观众对所观看过的电影的评分。数据的基本结构如下：
（3）电影基本信息
包括MovieID（电影序列号），Genes（电影题裁），Title（电影名称）等32个属性，有3952部影片，共有18种不同题裁的影片，为简化问题，仅考虑列出的3个属性。
（4）观众基本信息
包括UserID（观众序列号），Gender（性别），Age（年龄），Occupation（职业）等六个属性，共有6040位观众。在观众的选择上，随机选择人群进行数据取样。为简化问题，这里仅考虑列出的4个属性。
（5）观众对电影评分表
包括UserID（观众序列号），MovieID（电影序列号），Rating（评级标准），Timestamp（电影生产时间）四个属性。
3.海量数据挖掘模型
本文通过Hadoop云计算平台，提出信息粒挖掘模型、聚类分析模型与关联规则挖掘模型，主要是利用Hadoop自身的对海量数据的存储能力和并行计算能力且融入经典的Apriori算法，可降低运算时间、提高对海量数据的处理能力。
3.1信息粒挖掘模型
定义1 假定在数据集T中，F（i）表示数据集T中的第i个数据项是否存在，存在返回1，不存在返回0。
定义2 假定在数据集T中，每条记录中数据项个数为m，，每个数据项i对应的原子信息粒：
其中di为第i个数据项的二进制数表示，则可以定义一个可标识二进制数D（i）=d1d2…di…dm。
定义3 假设 x 与 y 表示两个信息记录，并用符号 D（x）和 D（y）分别表示相应信息的二进制表示（即信息粒的机器表示），则可以定义记录信息之间的“与”运算：
M（x∪y）= D（x）and D（y）
定义4 假定在数据集T中，每条记录中数据项个数为m，x 与 y 表示两个信息记录，并用符号 D（x）和 D（y）分别表示相应信息的二进制表示（即信息粒的机器表示），则可以定义两个记录之间的相似度DOFS（Degree of Similarity）为：
定义5 假定在数据集T中，每条记录中数据项个数为m，x 与 y 表示两个信息记录，并用符号 D（x）和 D（y）分别表示相应信息的二进制表示（即信息粒的机器表示），则可以定义两个记录之间的相似距离DIOS（Distance of similarity）为：
根据以上定义，可采用一组二进制数据，唯一表示某个数据集中的一条记录，且可得到这两条记录之间的相似度与相似距离。
3.2聚类分析模型（k-means算法与MapReduce并行化）
K-means 聚类算法的数据描述为：把n个向量xj（j=1，2，...，n）分成c个类Gj（j=1，2，...，n），并求每类的聚类中心，使得非相似性（或距离）指标的目标函数达到最小。当选择第i类Gi中向量xk与相应聚类中心ci间的度量为欧几里德距离时，目标函数可以定义为：
其中
是类Gi的目标函数。Ji值依赖于Gi的几何形状与和Ci的位置。显然，J的值越小，表明聚类效果越好。
这里，假定在数据集T中，每条记录中数据项个数为m，x 与 y 表示两个信息记录，我们可以设为：
，即为1/DOFS。
则目标函数为：
得到目标函数之后，将K-means聚类算法用于MapReduce并行化，对串行算法中每1次迭代启动对应的1次MapReduce计算过程，完成数据记录到聚类中心的距离计算以及新的聚类中心的计算。
结束语
大数据通常要面对十几 GB 乃至几十 GB 容量的巨型文件，而 32 位的进程也只有4GB 的虚拟地址空间，显然不能一次全部映射文件的映像。基于此情况，只能将大文件分割为若干个部分，本文采用基于Hadoop的海量数据挖掘算法，其目的是先通过使用高效的K-means算法与MapReduce分布式计算模型相结合进行聚类分析，然后在MapReduce框架中融入经典的Apriori算法，实验结果达到了预期的设计。
参考文献
[1] MICHAEL Armbrust，ARMANDO Fox. Above the Clouds：A Berkeley View of Cloud Computing[R]. California：Electrical Engineering and Computer Sciences，2009.
[2] Cheung W L，Ncentn V I，FU W C，et al． Efficient mining of association rules in distributed database[J]. IEEETrans on Knowledge and Data Engineering，1996，8（1）：911-922．
[3]Robert Bell，Yehuda Koren，and Chris Volinsky. Modeling relationships at multiple scales to improve accuracy of large recommender systems. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining，NY，USA，2007，95–104.
作者简介：张琛（1980-），女，本科，主要研究方向电力系统及其自动化。
王军（1987-），男，硕士研究生，主要研究方向为软件工程理论与技术、实时大数据处理挖掘。
论文作者:张琛1,王军1
论文发表刊物:《电力设备》2018年第9期
论文发表时间:2018/7/3
标签：数据论文; 算法论文; 数据项论文; 信息论文; 定义论文; 模型论文; 海量论文; 《电力设备》2018年第9期论文;