【Apriori算法Java实现版】聚类算法与关联分析 |
您所在的位置：网站首页 › 数据挖掘apriori算法Java代码 › 【Apriori算法Java实现版】聚类算法与关联分析 |
| 正文之前
当初毕设的时候准备用这个算法来着，不过后来为了给自己减少工作量（俗称偷懒），就没搞了，没想到这两天看一篇论文看到了这个，重新捡起来学一下。对于我这种算法底子不是很好的来说。。只能代码实现来感受下了。。 正文 基本概念关联分析是一种在大规模数据集中寻找有趣关系的非监督学习算法。这些关系可以有两种形式：频繁项集或者关联规则。频繁项集（frequent item sets)是经常出现在一块的物品的集合，关联规则(association rules)暗示两种物品之间可能存在很强的关系。 下图是一个乒乓球店的交易记录，〇表示顾客购买了商品。其中{底板,胶皮,浇水}就是一个频繁项集；从中可以找到底板->胶皮这样的关联规则： 然后是两个至关重要的参数的表示法： 支持度怎样有效定义频繁和关联？其中最重要的两个概念是支持度和置信度。 支持度(support)从字面上理解就是支持的程度，一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。上图中{底板}的支持度=(5/6) * 100%。 这个概念其实经常在现实生活中出现，翻译成支持率似乎更好理解，典型的例子就是投票，比如英国脱欧的支持率为51.89%。 用数学去解释就是，设W 中有s％的事务同时支持物品集A和B，s％称为{A，B}的支持度，即: support({A,B}) = num(A∪B) / W = P(A∩B)num(A∪B)表示含有物品集{A,B}的事务集的个数，不是数学中的并集。 置信度置信度(confidence)揭示了A出现时B是否一定出现，如果出现，则出现的概率是多大。如果A->B的置信度是100%，则说明A出现时B一定会出现（返回来不一定）。上图中底板共出现5次，其中4次同时购买了胶皮，底板->胶皮的置信度是80%。 用公式表示是，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度： Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)这是Apriori算法的关键数学模型。下面就是关键的Java实现，有时候我觉得看代码真的比算法更加直观些。。。不过，当我打开了算法流程图的大门。 Apriori算法过程发现频繁项集的过程如上图所示： 由数据集生成候选项集C1（1表示每个候选项仅有一个数据项）；再由C1通过支持度过滤，生成频繁项集L1（1表示每个频繁项仅有一个数据项）。 将L1的数据项两两拼接成C2。 从候选项集C2开始，通过支持度过滤生成L2。L2根据Apriori原理拼接成候选项集C3；C3通过支持度过滤生成L3……直到Lk中仅有一个或没有数据项为止。下面是一个超市的交易记录： Apriori算法发现频繁项集的过程如下： 或者这是我抄代码的博客的图，也挺好看的： 还有一段伪代码奉上： 算法：Apriori 输入：D - 事务数据库；min_sup - 最小支持度计数阈值 输出：L - D中的频繁项集 方法： L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集 For(k=2;Lk-1!=null;k++){ 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](a,b) (1,0,1)->(a,c) (1,0,0)->(a) (0,1,1)->(b,c) (0,1,0)->(b) (0,0,1)->(c) (0,0,0)->@(@表示空集) */ List result = new ArrayList(); String[] strings = sourceSet.split(GAP); for (int i = 1; i=0 && countB) = support({A,B}) / support({A}) = P(B|A) */ Double confidence = (1.0*frequentSetMap.get(key))/(1.0*frequentSetMap.get(keySubSetItem)); if (confidence > CONFIDENCE) { relationMap.put(keySubSetItem+CON+expect(key,keySubSetItem),confidence); } } } } return relationMap; } public static void main(String[] args){ ArrayList dataList = new ArrayList(); dataList.add("1;2;5;"); dataList.add("2;4;"); dataList.add("2;3;"); dataList.add("1;2;4;"); dataList.add("1;3;"); dataList.add("2;3;"); dataList.add("1;3;"); dataList.add("1;2;3;5;"); dataList.add("1;2;3;"); System.out.println("=数据集合=========="); for(String string:dataList){ System.out.println(string); } Apriori2 apriori2 = new Apriori2(); System.out.println("=频繁项集=========="); Map frequentSetMap = apriori2.apriori(dataList); Set keySet = frequentSetMap.keySet(); for(String key:keySet){ System.out.println(key+" : "+frequentSetMap.get(key)); } System.out.println("=关联规则=========="); Map relationRulesMap = apriori2.getRelationRules(frequentSetMap); Set rrKeySet = relationRulesMap.keySet(); for (String rrKey : rrKeySet){ System.out.println(rrKey + " : " + relationRulesMap.get(rrKey)); } } }上面这些代码基本是照抄下面这个博客里面的。我就改动了一下那个获取真子集的函数而已。其他的不好怎么改，还不如直接抄。不过自己过一遍手之后确实感觉理解深刻了很多。 频繁模式挖掘apriori算法介绍及Java实现 控制台输出如下： [zbzhang@node61 JavaCode]$ java Apriori2 =数据集合========== 1;2;5; 2;4; 2;3; 1;2;4; 1;3; 2;3; 1;3; 1;2;3;5; 1;2;3; =频繁项集========== 1;2; : 4 1;3; : 4 5; : 2 2;3; : 4 4; : 2 2;4; : 2 1;5; : 2 3; : 6 2; : 7 1; : 6 1;2;5; : 2 1;2;3; : 2 2;5; : 2 =关联规则========== 4;->2; : 1.0 5;->1;2; : 1.0 5;->1; : 1.0 1;5;->2; : 1.0 5;->2; : 1.0 2;5;->1; : 1.0 [zbzhang@node61 JavaCode]$ 正文之后下面是参考文献时间： 使用Apriori进行关联分析（一） 频繁模式挖掘apriori算法介绍及Java实现 Java compareTo() 方法 Map获取其键和值 Java进阶--深入理解ArrayList实现原理 ArrayList的用法整理 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |