Apriori算法及java实现
Apriori算法详解及java代码实现
1 Apriori介绍
Apriori算法使用频繁项集的先验知识,使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。首先,通过扫描事务(交易)记录,找出所有的频繁1项集,该集合记做L1,然后利用L1找频繁2项集的集合L2,L2找L3,如此下去,直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则,即产生用户感兴趣的关联规则。
其中,Apriori算法具有这样一条性质:任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值,当有元素A添加到I中时,结果项集(A∩I)不可能比I出现次数更多。因此A∩I也不是频繁的。
2 连接步和剪枝步
在上述的关联规则挖掘过程的两个步骤中,第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1) 连接步
为找出Lk(所有的频繁k项集的集合),通过将Lk-1(所有的频繁k-1项集的集合)与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序,即对于(k-1)项集li,li[1]<li[2]<……….<li[k-1]。将Lk-1与自身连接,如果(l1[1]=l2[1])&&( l1[2]=l2[2])&&……..&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1]),那认为l1和l2是可连接。连接l1和l2 产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。
2) 剪枝步
CK是LK的超集,也就是说,CK的成员可能是也可能不是频繁的。通过扫描所有的事务(交易),确定CK中每个候选的计数,判断是否小于最小支持度计数,如果不是,则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质:任一频繁项集的所有非空子集也必须是频繁的,反之,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。
(Tip:为什么要压缩CK呢?因为实际情况下事务记录往往是保存在外存储上,比如数据库或者其他格式的文件上,在每次计算候选计数时都需要将候选与所有事务进行比对,众所周知,访问外存的效率往往都比较低,因此Apriori加入了所谓的剪枝步,事先对候选集进行过滤,以减少访问外存的次数。)
3 Apriori算法实例
Apriori算法详解及java代码实现
3. Apriori伪代码
Apriori算法详解及java代码实现
Ck=apriori_gen(Lk-1); // 产生候选,并剪枝
For each 事务t in D{ // 扫描D进行候选计数
Ct =subset(Ck,t); // 得到t的子集
For each 候选c 属于 Ct
c.count++;
}
Lk={c属于Ck | c.count>=min_sup}
}
Return L=所有的频繁集;
Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)
For each项集l1属于Lk-1
For each项集 l2属于Lk-1
If((l1[1]=l2[1])&&( l1[2]=l2[2])&&……..
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
c=l1连接l2 //连接步:产生候选
if has_infrequent_subset(c,Lk-1) then
delete c; //剪枝步:删除非频繁候选
else add c to Ck;
}
Return Ck;
Procedure has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets) For each(k-1)-subset s of c
If s不属于Lk-1 then
Return true;
Return false;
4. 由频繁项集产生关联规则
Confidence(A->B)=P(B|A)=support_count(AB)/support_count(A)
关联规则产生步骤如下:
1) 对于每个频繁项集l,产生其所有非空真子集;
2) 对于每个非空真子集s,如果support_count(l)/support_count(s)>=min_conf,则输
出 s->(l-s),其中,min_conf是最小置信度阈值。
Apriori算法详解及java代码实现
例如,在上述例子中,针对频繁集{I1,I2,I5}。可以产生哪些关联规则?该频繁集的非空真子集有{I1,I2},{I1,I5},{I2,I5},{I1 },{I2}和{I5},对应置信度如下:
I1&&I2->I5 confidence=2/4=50%
I1&&I5->I2 confidence=2/2=100%
I2&&I5->I1 confidence=2/2=100%
I1 ->I2&&I5 confidence=2/6=33%
I2 ->I1&&I5 confidence=2/7=29%
I5 ->I1&&I2 confidence=2/2=100%
如果min_conf=70%,则强规则有I1&&I5->I2,I2&&I5->I1,I5 ->I1&&I2。 5. Apriori Java代码
package com.apriori;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Apriori {
private final static int SUPPORT = 2; // 支持度阈值
private final static double CONFIDENCE = 0.7; // 置信度阈值
private final static String ITEM_SPLIT=";"; // 项之间的分隔符
private final static String CON="->"; // 项之间的分隔符
private final static List<String> transList=new ArrayList<String>(); //所有交易
static{//初始化交易记录
transList.add("1;2;5;");
transList.add("2;4;");
transList.add("2;3;");
transList.add("1;2;4;");
transList.add("1;3;");
transList.add("2;3;");
Apriori算法详解及java代码实现
transList.add("1;3;");
transList.add("1;2;3;5;");
transList.add("1;2;3;");
}
public Map<String,Integer> getFC(){
Map<String,Integer> frequentCollectionMap=new HashMap<String,Integer>();//所有的频繁集
frequentCollectionMap.putAll(getItem1FC());
Map<String,Integer> itemkFcMap=new HashMap<String,Integer>();
itemkFcMap.putAll(getItem1FC());
while(itemkFcMap!=null&&itemkFcMap.size()!=0){
Map<String,Integer> candidateCollection=getCandidateCollection(itemkFcMap);
Set<String> ccKeySet=candidateCollection.keySet();
//对候选集项进行累加计数
for(String trans:transList){
for(String candidate:ccKeySet){
boolean flag=true;// 用来判断交易中是否出现该候选项,如果出现,计数加1
String[] candidateItems=candidate.split(ITEM_SPLIT);
for(String candidateItem:candidateItems){
if(trans.indexOf(candidateItem+ITEM_SPLIT)==-1){
flag=false;
break;
}
}
if(flag){
Integer count …… 此处隐藏:3407字,全部文档内容请下载后查看。喜欢就下载吧 ……
相关推荐:
- [实用文档]李践-有效提升销售的12大黄金法则8-大
- [实用文档]党支部换届工作方案
- [实用文档]2013年下期电子商务专业部宣传工作计划
- [实用文档]方庄一矿通风、钻探绩效工资考核管理办
- [实用文档]项目一 认识企业物流认识企业物流
- [实用文档]MBI_Display_产品蓝图规画
- [实用文档]北京市建筑业劳务作业人员普法维权培训
- [实用文档]锅炉燃烧调整与运行优化
- [实用文档]4支付结算业务的核算
- [实用文档]米什金_货币金融学_第9版各章学习指导
- [实用文档]水泥混凝土路面硬化工程施工组织设计
- [实用文档]钢筋工程安全技术交底书
- [实用文档]关于公布华中师范大学本科毕业论文
- [实用文档]太原市园林绿化施工合同范本 2
- [实用文档]周日辅导 初中英语分类复习单项选择题(
- [实用文档]第四章 文化经纪人的管理形式 第二节
- [实用文档]学宪法讲宪法竞赛题库
- [实用文档]《数值计算方法》期末考试模拟试题二
- [实用文档]爱词霸学英语:每日一句( 十月)
- [实用文档]2014年国家公务员面试:无领导小组讨论
- 新课程主要理念和教学案例分析汇编(24
- 英国人的快乐源于幸福的家庭生活
- 七年级上册第一次月考模拟数学试卷
- 真丝及仿真丝的种类有哪些?
- 【最新】华师大版八年级数学下册第十六
- 高中英语3500个必背单词
- 我可以接受失败,但我不能接受放弃!
- 最近更新沪科版八年级物理上册期末试卷
- 绿化工作先进乡镇事迹材料
- 鲁教版九年级上册思想品德教学计划
- 英语音标的分类
- 地下室底板无梁楼盖与普通梁板结构形式
- 美容师黄金销售话术
- 雅思写作满分作文备考方法
- 血清甲状腺激素测定与高频彩色多普勒超
- 1度浅析装修对室内空气品质的影响
- 2017-2022年中国汞矿行业深度分析与投
- 计算机二级VB公共基础知识
- (何勇)秸秆禁烧_重在寻找出路
- 内外墙抹灰工程分包施工合同1




