今天看了一下关联规则分析中的Apriori算法,先了解下基本概念:
关联规则分析用于发现隐藏在大型数据集中的有意义的联系。在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。
•关联规则挖掘形式化定义:
•原始数据描述
设I ={i1, i2,…,im}是所有项(item)的集合,若干项的集合,称为项集(Item Sets)。
记T为交易(transaction,事务) t的集合,其中,交易t是项的集合,并且t⊆I。
设A、C分别是一个I中项的集合,如果A⊆T且C⊆T,且A∩C=Φ那么称交易T包含A ∪ C。
•目标数据描述
所有形如A⇒C蕴涵式的称为关联规则,这里A⊂I, C⊂I,并且A∩C=Φ。
•为了描述关联规则的有用性和确定性
•Ø关联规则的支持度
–如果交易集T中s次交易包含A∪C,则称规则A=>C在事务集T上的支持度为s。
–Support(A=>C)=P(A∪C)
•Ø关联规则的置信度
–如果交易数据库D中,包含A的交易中有c(%)的交易同时也包含C,称规则的置信度为c。(条件概率)
–Confidence(A=>C)=P(C|A) =support({A} ∪{C})/support({A})
•支持度, s,一次交易中包含{A、C}的可能性
•置信度, c,包含{A}的交易中也包含{C}的条件概率
•量化后的目标
–查找所有满足最小支持度和可信度的规则A=>C
•频繁项集
–如果项集满足最小支持度,则称之为频繁项集
•例如A={尿布,啤酒} ,支持度=3
•如果 最小支持度= 3,则A是频繁项集
•如果频繁项集中包含K个项,则称为频繁K-项集,A为2-项集
•关联规则的挖掘步骤
–发现频繁项集
–由频繁项集生成满足最小支持度和最小置信度的关联规则
Apriori性质
–一个频繁项集中的任一非空子集也应是频繁项集。
–如果一项交易包含{牛奶,面包,汽水},那么它一定包含{牛奶,面包}
–{牛奶,面包,汽水}是频繁的=>{牛奶,面包}一定也是频繁的
–即:任何非频繁项集的超集一定也是非频繁的
非频繁项集的超集可以不用进行测试 ,许多项之间的组合可以去掉(不满足频繁条件)
算法核心:逐层搜索的迭代方法,寻找最大频繁集 。
下面是Apriori算法Java的简单实现:
public class AprioriBuilder { /** 最小支持度*/ private int minSupport = 2; /** 最小置信度*/ private double minConfidence = 0.6; /** 数据集*/ private Data data = null; /** 候选集集合*/ private List<List<ItemSet>> candidates = null; /** 频繁集集合*/ private List<List<ItemSet>> frequencies = null; /** 关联规则集合*/ private Set<AssociationRule> associationRules = null; public void initialize() { data = DataLoader.load("d:\\apriori.txt"); candidates = new ArrayList<List<ItemSet>>(); frequencies = new ArrayList<List<ItemSet>>(); associationRules = new HashSet<AssociationRule>(); } /** 生成频繁一项集*/ private void frequency_1_itemset_gen() { List<ItemSet> frequency = new ArrayList<ItemSet>(); List<ItemSet> candidate = new ArrayList<ItemSet>(); Map<String, Integer> map = new HashMap<String, Integer>(); for (Instance instance : data.getInstances()) { Set<String> valueSet = new TreeSet<String>(); for (String value : instance.getValues()) { Integer mValue = map.get(value); map.put(value, null == mValue ? 1 : mValue + 1); valueSet.add(value); } } ShowUtils.print(map); for (Map.Entry<String, Integer> entry : map.entrySet()) { candidate.add(new ItemSet(entry.getKey(), entry.getValue())); if (entry.getValue() >= minSupport) { frequency.add(new ItemSet(entry.getKey(), entry.getValue())); } } candidates.add(candidate); frequencies.add(frequency); } /** 生成频繁K项集*/ private void frequency_k_itemset_gen(int k) { Iterator<ItemSet> f1Iter = frequencies.get(k - 2).iterator(); Iterator<ItemSet> f2Iter = frequencies.get(0).iterator(); List<ItemSet> candidate = new ArrayList<ItemSet>(); while (f1Iter.hasNext()) { ItemSet item1 = f1Iter.next(); while (f2Iter.hasNext()) { ItemSet item2 = f2Iter.next(); ItemSet temp = new ItemSet(); temp.getItems().addAll(item1.getItems()); if (!temp.getItems().containsAll(item2.getItems())) { temp.getItems().addAll(item2.getItems()); boolean isContain = false; for (ItemSet itemSet : candidate) { if (itemSet.getItems().containsAll(temp.getItems())) { isContain = true; } } if (!isContain) { candidate.add(temp); } } } f2Iter = frequencies.get(0).iterator(); } candidates.add(candidate); List<ItemSet> frequency = new ArrayList<ItemSet>(); for (ItemSet itemSet : candidate) { int support = calculateSupport(itemSet.getItemsArray()); if (support >= minSupport) { frequency.add(itemSet); } } frequencies.add(frequency); } /** 计算项集支持度*/ private int calculateSupport(String... items) { if (null == items || items.length == 0) return 0; int support = 0; for (Instance instance : data.getInstances()) { int temp = 0; for (String value : instance.getValues()) { for (String item : items) { if (item.equals(value)) { temp++; } } } if (temp == items.length) { support++; } } return support; } /** 计算关联规则置信度*/ private void calculateConfidence(AssociationRule associationRule) { String[] arLeft = associationRule.getLeft().getItemsArray(); String[] arRight = associationRule.getRight().getItemsArray(); int leftLength = arLeft.length; int rightLength = arRight.length; String[] left = new String[leftLength + rightLength]; String[] right = new String[rightLength]; System.arraycopy(arLeft, 0, left, 0, leftLength); System.arraycopy(arRight, 0, left, leftLength, rightLength); System.arraycopy(arRight, 0, right, 0, rightLength); double leftSup = calculateSupport(left); double rightSup = calculateSupport(right); System.out.print(AssociationRuleHelper.convert(left) + ": " + leftSup + " "); System.out.println(AssociationRuleHelper.convert(right) + ": " + rightSup + " "); if (rightSup != 0) { double confidence = leftSup / rightSup; associationRule.setConfidence(confidence); if (confidence >= minConfidence && !AssociationRuleHelper.isContain( associationRules, associationRule)) { associationRules.add(associationRule); } } for (AssociationRule child : associationRule.getChildren()) { calculateConfidence(child); } } /** 获取最新频繁项集*/ private List<ItemSet> getLastFrequency() { int index = frequencies.size() - 1; List<ItemSet> frequency = frequencies.get(index); while (0 == frequency.size()) { frequency = frequencies.get((index--)); } return frequency; } /** 生成关联规则并且计算置信度*/ private void association_rule_gen(List<ItemSet> frequency) { for (ItemSet itemSet : frequency) { AssociationRule ar = new AssociationRule(itemSet, null); child_association_rule_gen(ar); calculateConfidence(ar); AssociationRuleHelper.print(ar, 0); } } /** 生成子关联规则*/ private void child_association_rule_gen(AssociationRule associationRule) { ItemSet left = associationRule.getLeft(); TreeSet<String> items = left.getItems(); int length = items.size(); if (length == 1) return; List<String> temp = new ArrayList<String>(items); for (int i = 0; i < length; i++) { AssociationRule child = new AssociationRule(); associationRule.getChildren().add(child); child.getRight().addAll(associationRule.getRight().getItems()); child.getRight().add(temp.get(i)); for (int j = 0; j < length; j++) { if (j != i) { child.getLeft().add(temp.get(j)); } } child_association_rule_gen(child); } } public void build() { initialize(); frequency_1_itemset_gen(); print(candidates, true); print(frequencies, false); for (int k = 2; frequencies.get(k - 2).size() > 0; k++) { frequency_k_itemset_gen(k); print(candidates, true); print(frequencies, false); } List<ItemSet> lastFrequency = getLastFrequency(); print(lastFrequency); association_rule_gen(lastFrequency); System.out.println("associationRules size: " + associationRules.size()); for (AssociationRule associationRule : associationRules) { AssociationRuleHelper.print(associationRule); } } public void print(List<List<ItemSet>> itemSetss, boolean isCandidate) { System.out.println((isCandidate ? "Candidate" : "Frequency") + " Item Set"); System.out.println(itemSetss.size()); for (List<ItemSet> itemSets : itemSetss) { print(itemSets); } } public void print(List<ItemSet> itemSets) { System.out.println("----------"); for (ItemSet itemSet : itemSets) { System.out.println(itemSet.getItems()); } System.out.println("----------"); } public static void main(String[] args) { AprioriBuilder ab = new AprioriBuilder(); ab.build(); } }
相关推荐
人工智能-机器学习-关联规则分析-Apriori算法实例-挖掘电影导演的关联规则
【转】数据挖掘-关联分析频繁模式挖掘Apriori、FP-Growth及Eclat算法的JAVA及C 实现.doc
MADlib-基于SQL的数据挖掘解决方案-关联规则之Apriori算法.docx
数据挖掘中关联规则挖掘的Apriori算法源代码,很不错,值得看一下
10.1 关联规则基本概念 ...10.6 多层关联规则挖掘 10.7 多维关联规则挖掘 10.8 约束性关联规则挖掘 10.9 数量关联规则挖掘 10.10 负关联规则挖掘算法 10.11 加权关联规则挖掘算法 10.12 应用实例分析 10.13 小结
Apriori关联规则在中医证型中的应用,有对应数据及说明文档,可以运行
该算法是数据挖掘中关联规则的经典算法。代码风格清晰,运行速度快!
Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘Apriori关联规则挖掘
关联规则挖掘算法apriori算法的实现
1.基本概念 2.主要算法(重点) Apriori算法 及各种改进效率的方法 FP树算法 3.各种关联规则挖掘的扩展 多层关联规则 多维关联规则 4.强关联并不一定有趣 5.关联挖掘演示
对经典的数据挖掘算法 Apriori 算法和 FP-growth 进行简单实现
数据挖掘关联规则Apriori算法的一种新改进,白东玲,郭庆平,关联规则算法的研究在数据挖掘算法的研究中占有相当重要的地位。关联规则算法的核心是Apriori 算法,但随着对关联规则研究的深入,�
关联分析(Association Analysis) 关联分析是一种在大规模数据集中寻找有趣关系的任务。 这些关系有两种: 频繁项集(frequent item sets):经常出现在一起物品组合 关联规则(association rules):暗示物品之间很强关系
数据挖掘|关联分析与Apriori算法详解
数据挖掘经典的关联规则挖掘Apriori算法及其分桶策略的优化算法
主要关于关联规则里面经典算法的最初论文,对Apriori算法想深研究,可以看下。
云计算-基于云计算的关联规则Apriori算法的研究与实现.pdf
数据挖掘中关联规则Apriori算法.pdf
用java实现了关联规则中的Apriori算法
电子科技大学数据挖掘课程 第二次实验 关联规则挖掘 实验报告及代码实现 包括频繁项集获取过程 关联规则获取过程 自认为理解&写得还是很透彻的哈哈哈 没看懂可以来找我~