加载中…
个人资料
bicloud
bicloud
  • 博客等级:
  • 博客积分:0
  • 博客访问:380,110
  • 关注人气:493
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

基于mapreduce的购物篮分析算法实现

(2011-08-01 13:31:28)
标签:

hadoop

购物篮分析

it

分类: 数据挖掘
1介绍
自从google在gfs的基础上实现分布式计算平台,amazon通过hadoop集群提供AWS服务,mapreduce方法被普遍应用于海量数据处理。为了处理大量数据,mapreduce方法导致需要重新设计和实现传统的数据分析算法。hadoop是建立在hdfs和mapreduce基础上的分布式计算平台。在企业计算中,hadoop得到大量的应用,主要是由于企业界现在拥有越来越多的数据,譬如日志数据或者交易数据。hadoop在处理商业智能中的大量数据非常有用,在最近几年的数据挖掘中也有很多应用。这里主要介绍将传统的购物篮分析算法在hadoop平台上实现,提高性能。
2相关工作
关联规则或者关联分析是数据挖掘算法中用来发现用户购物行为中商品关联性的法。Aster Data 开发了SQL mapreduce框架,提供sql方式处理数据库中的海量数据。该框架在SQL API的基础上实现了购物篮分析算法。
3hadoop中的mapreduce
3.1 mapreudce原理
 基于mapreduce的购物篮分析算法实现

3.2 海量数据存储
在本文中,输入输出文件通过hadfs实现,并不采用hbase数据库。然而,虽然hbase很有趣,在未来的算法开发中会考虑集成hbase。在使用关系型数据库管理系统处理大数据时存在一些缺点,譬如无法处理删除,插入速度慢以及产生随机错误。基于hdfs的hbase是一个分布式数据库,为列式数据表提供结构化存储。
3.3 mapreduce问题
(1)在处理大量数据应用中,这种编程方式是一种巨大的退步
(2)并不是全新的方法,譬如很多实现的算法是数十年前的,尤其是人工智能算法
(3)数据需要转化成key-value形式,失去了当前RDBMS的很多特性
(4)与很多已经存在的算法和工具不兼容

4购物篮分析算法
购物篮分析算法是数据挖掘中发现数据集中关联规则的重要算法之一。它的基本思想就是,寻找交易数据集中项目对之间的关联关系。
譬如数据集
Transaction 1: cracker, icecream, beer
Transaction 2: chicken, pizza, coke, bread
Transaction 3: baguette, soda, hering, cracker, beer
Transaction 4: bourbon, coke, turkey
Transaction 5: sardines, beer, chicken, coke
Transaction 6: apples, peppers, avocado, steak
Transaction 7: sardines, apples, peppers, avocado,
steak
......
通过关联分析可以找出下列关系,
Total number of Items: 322,322
Ten most frequent Items:
cracker, beer 6,836
artichok, avocado 5,624
avocado, baguette 5,337
bourbon, cracker 5,299
baguette, beer 5,003
corned, hering 4,664
beer, hering 4,566
......
hadoop版本MBA算法
Mapper
1: Reads each transaction of input file and generates
the data set of the items:
(<V1>, <V2>, …, <Vn>) where < Vn>: (vn1, vn2,.. vnm)
2: Sort all data set <Vn> and generates sorted data set
<Un>:
(<U1>, <U2>, …, <Un>) where < Un>: (un1, un2,.. unm)
3: Loop While < Un> has the next element;
note: each list Un is handled individually
3.1: Loop For each item from un1 to unm of < Un> with
NUM_OF_PAIRS
3.a: generate the data set <Yn>: (yn1, yn2,.. ynl);
ynl: (unx􀀀 uny) is the list of self-crossed pairs of
(un1, un2,.. unm) where unx uny
3.b: increment the occurrence of ynl;
note: (key, value) = (ynl, number of occurrences)
3.2: End Loop For
4. End Loop While
5. Data set is created as input of Reducer: (key,
<value>) = (ynl, <number of occurrences>)
Reducer
1: Read (ynl, <number of occurrences>) data from
multiple nodes
2. Add the values for ynl to have (ynl, total number of
occurrences)

5实验结果
Total number of keys in order 2: 212
Total number of items: 1,255,922,927
Items Paired (key) Frequency (value)
cracker, heineken 208,816,643
artichok, avocado 171,794,426
avocado, baguette 163,027,463
bourbon, cracker 161,866,763
baguette, heineken 152,824,775
corned_b, hering 142,469,636
heineken, hering 139,475,906
bourbon, heineken 126,310,383
baguette, cracker 125,699,308
artichok, heineken 125,180,072

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有