利用Hbase的coprocessor实现增量式Apriori算法

  • Apriori在数据挖掘中是经典的频繁项集挖掘算法,其主要思想就是如果某个项集不频繁,则任何包含此项集的项集一定不频繁。而今天要实现的增量式的Apriori算法,有点像分布式的Apriori,因为我们可以把已挖掘的事务集和新增的事务集看作两个互相独立的数据集,挖掘新增的事务集,获取所有新增频繁集,然后与已有的频繁集做并集,对于两边都同时频繁的项集肯定全局频繁,而只有一边频繁的项集则需要统计其在两边的频繁计数,这样完成后就能获得所有的全局频繁集,并不需要重新挖掘已有的事务集,效率必然提高。
  • 至于Hbase的Coprocessor,相信大家也很了解了吧,这是根据Google的BigTable中实现的Percolator的开源实现,目的是提供增量操作以及建立二级索引。Hbase提供两种类型的Coprocessor,Endpoint和Observer,Endpoint提供的类似于数据库的存储过程,需要事先部署一份程序到各个regionserver,然后由客户端调用,并汇总各个regionserver处理后返回的数据。Observer就像数据库中的触发器,只需部署到regionserver,其提供PreGet、PostGet、PrePut、PostPut、PreDelete、PostDelete等操作,所以当每个regionserver发生了以上的操作时,就会触发Observer。
  • 今天我们只用到了Endpoint型的Coprocessor,由各个regionserver统计其事务集中所有频繁项集,然后客户端汇总各个region的频繁项集,做个并集,对于计数已达到最低支持度要求的项集就认定为全局频繁,剩下的项集就继续统计其在所有region中的频繁计数,最终获得所有全局频繁项集。第二步,就是增量地插入事务集,用timestamp做好标记,然后按照一开始说的方法,再次得到所有全局频繁的项集。 有必要提一下的是,Hbase从0.98版本开始,Coprocessor的远程通信采用了protobuf标准,protobuf需要实现定义通信格式,下面就是该算法需要的proto
package apriori;
option java_package = "dave.apriori.protos";
option java_outer_classname = "AprioriProtos";
option java_generic_services = true;
option java_generate_equals_and_hash = true;
option optimize_for = SPEED;

message AprioriRequest {
  required int32 length = 1;
  required float support = 2;
}

message AprioriResponse {
  message FrequentSet {
    required bytes fset = 3;
    required int32 support = 4;
  }
  required int32 count = 5;
  repeated FrequentSet fsets = 6;
}

message SpecialRequest {
    repeated bytes fsets = 7;
}

message SpecialResponse {
    repeated int32 supportCount = 8;
}

message HelloRequest{
    required bytes hellostr = 9;
}

message HelloResponse{
    required bytes helloresp = 10;
}

service Apriori {
  rpc getFrequentSet(AprioriRequest)
    returns (AprioriResponse);
  rpc getSepecialSupport(SpecialRequest)
    returns (SpecialResponse);
  rpc sayHello(HelloRequest)
    returns (HelloResponse);
}

定义了三个service,一个是获得该region所有的频繁项集,另一个是获取某个项集在该region的计数,最后是测试用的sayHello。 定义好了之后,用protoc –java_out=. Apriori.proto命令就可以在当前目录下生成相应的java文件,再导入到项目中就可以编写服务器和客户端了。 部署过程和源代码已上传,有需要的朋友可在http://download.csdn.net/detail/xanxus46/8801857下载

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30840
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44830
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51620
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22440
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

12310
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18430
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

16220
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

35230
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13750

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励