精华内容
下载资源
问答
  • 关联规则挖掘Association Rule Mining是数据挖掘中研究较早而且至今仍活跃的研究方法之一 最早是由Agrawal等人提出的1993最初提出的动机是针对购物篮分析Basket Analysis问题提出的其目的是为了发现交易数据库...
  • 一个事务数据库中的关联规则挖掘可以描述如下 设I= {i1, i2, , im} 是一个项目集合 事务数据 库D= {t1, t2, , tn} 是由一系列具有惟一标识的TID事务组成 每一个事务ti (i=1, 2, , n)都对应I上的一个子集 定义3.1 设...
  • 10.1 关联规则基本概念 10.2 关联规则算法原理 10.3 分层搜索经典算法-Apriori算法 10.4 并行挖掘算法 10.5 增量更新挖掘算法 10.6 多层关联规则挖掘 10.7 多维关联规则挖掘 10.8 约束性关联规则挖掘 10.9 数量关联...
  • 我计划整理数据挖掘基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。  关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇...

    我计划整理数据挖掘的基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。

     关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。

     啤酒与尿布的故事已经成为了关联规则挖掘的经典案例,还有人专门出了一本书《啤酒与尿布》,虽然说这个故事是哈弗商学院杜撰出来的,但确实能很好的解释关联规则挖掘的原理。我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念:

    TID Items
    T1 {牛奶,面包}
    T2 {面包,尿布,啤酒,鸡蛋}
    T3 {牛奶,尿布,啤酒,可乐}
    T4 {面包,牛奶,尿布,啤酒}
    T5 {面包,牛奶,尿布,可乐}

       表中的每一行代表一次购买清单(注意你购买十盒牛奶也只计一次,即只记录某个商品的出现与否)。数据记录的所有项的集合称为总项集,上表中的总项集S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}。

     一、关联规则、自信度、自持度的定义

      关联规则就是有关联的规则,形式是这样定义的:两个不相交的非空集合X、Y,如果有X-->Y,就说X-->Y是一条关联规则。举个例子,在上面的表中,我们发现购买啤酒就一定会购买尿布,{啤酒}-->{尿布}就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述,

       支持度的定义:support(X-->Y) = |X并Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%。

      自信度的定义:confidence(X-->Y) = |X并Y|/|X| = 集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数 。例如:confidence({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/啤酒出现的次数=3/3=100%;confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数/尿布出现的次数 = 3/4 = 75%。

      这里定义的支持度和自信度都是相对的支持度和自信度,不是绝对支持度,绝对支持度abs_support = 数据记录数N*support。

      支持度和自信度越高,说明规则越强,关联规则挖掘就是挖掘出满足一定强度的规则。

    二、关联规则挖掘的定义与步骤

      关联规则挖掘的定义:给定一个交易数据集T,找出其中所有支持度support >= min_support、自信度confidence >= min_confidence的关联规则。

      有一个简单而粗鲁的方法可以找出所需要的规则,那就是穷举项集的所有组合,并测试每个组合是否满足条件,一个元素个数为n的项集的组合个数为2^n-1(除去空集),所需要的时间复杂度明显为O(2^N),对于普通的超市,其商品的项集数也在1万以上,用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。

      仔细想一下,我们会发现对于{啤酒-->尿布},{尿布-->啤酒}这两个规则的支持度实际上只需要计算{尿布,啤酒}的支持度,即它们交集的支持度。于是我们把关联规则挖掘分两步进行:

      1)生成频繁项集

      这一阶段找出所有满足最小支持度的项集,找出的这些项集称为频繁项集。

      2)生成规则

      在上一步产生的频繁项集的基础上生成满足最小自信度的规则,产生的规则称为强规则。

      关联规则挖掘所花费的时间主要是在生成频繁项集上,因为找出的频繁项集往往不会很多,利用频繁项集生成规则也就不会花太多的时间,而生成频繁项集需要测试很多的备选项集,如果不加优化,所需的时间是O(2^N)。

    三、Apriori定律

      为了减少频繁项集的生成时间,我们应该尽早的消除一些完全不可能是频繁项集的集合,Apriori的两条定律就是干这事的。

      Apriori定律1):如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。

      Apriori定律2):如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合{A}不是频繁项集,即A出现的次数小于min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。

      利用这两条定律,我们抛掉很多的候选项集,Apriori算法就是利用这两个定理来实现快速挖掘频繁项集的。

    四、Apriori算法

      Apriori是由a priori合并而来的,它的意思是后面的是在前面的基础上推出来的,即先验推导,怎么个先验法,其实就是二级频繁项集是在一级频繁项集的基础上产生的,三级频繁项集是在二级频繁项集的基础上产生的,以此类推。

      Apriori算法属于候选消除算法,是一个生成候选集、消除不满足条件的候选集、并不断循环直到不再产生候选集的过程。

      

      上面的图演示了Apriori算法的过程,注意看由二级频繁项集生成三级候选项集时,没有{牛奶,面包,啤酒},那是因为{面包,啤酒}不是二级频繁项集,这里利用了Apriori定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。

      算法的思想知道了,这里也就不上伪代码了,我认为理解了算法的思想后,子集去构思实现才能理解更深刻,这里贴一下我的关键代码:

    复制代码
     1 public static void main(String[] args) {
     2         // TODO Auto-generated method stub
     3         record = getRecord();// 获取原始数据记录
     4         List<List<String>> cItemset = findFirstCandidate();// 获取第一次的备选集
     5         List<List<String>> lItemset = getSupportedItemset(cItemset);// 获取备选集cItemset满足支持的集合
     6 
     7         while (endTag != true) {// 只要能继续挖掘
     8             List<List<String>> ckItemset = getNextCandidate(lItemset);// 获取第下一次的备选集
     9             List<List<String>> lkItemset = getSupportedItemset(ckItemset);// 获取备选集cItemset满足支持的集合
    10             getConfidencedItemset(lkItemset, lItemset, dkCountMap, dCountMap);// 获取备选集cItemset满足置信度的集合
    11             if (confItemset.size() != 0)// 满足置信度的集合不为空
    12                 printConfItemset(confItemset);// 打印满足置信度的集合
    13             confItemset.clear();// 清空置信度的集合
    14             cItemset = ckItemset;// 保存数据,为下次循环迭代准备
    15             lItemset = lkItemset;
    16             dCountMap.clear();
    17             dCountMap.putAll(dkCountMap);
    18         }
    复制代码

      如果想看完整的代码,可以查看我的github,数据集的格式跟本文所述的略有不通,但不影响对算法的理解。

      下一篇将介绍效率更高的算法--FP-Grow算法。

    参考文献:

      [1].Pang-Ning Tan,Michael Steinbach. Introduction to Data Mining.

      [2].HanJiaWei. Data Mining: concept and  techniques.

    原文地址:点击打开链接

    展开全文
  • 数据挖掘系列(1)关联规则挖掘基本概念与Aprior算法 我计划整理数据挖掘基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。  关联规则挖掘在电商、...

    转自:http://www.cnblogs.com/fengfenggirl/p/associate_apriori.html


    数据挖掘系列 (1) 关联规则挖掘基本概念与 Aprior 算法


    我计划整理数据挖掘的基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。

    关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和 Aprori 算法。

    啤酒与尿布的故事已经成为了关联规则挖掘的经典案例,还有人专门出了一本书《啤酒与尿布》,虽然说这个故事是哈弗商学院杜撰出来的,但确实能很好的解释关联规则挖掘的原理。我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念:

    TIDItems
    T1{牛奶,面包}
    T2{面包,尿布,啤酒,鸡蛋}
    T3{牛奶,尿布,啤酒,可乐}
    T4{面包,牛奶,尿布,啤酒}
    T5{面包,牛奶,尿布,可乐}

       表中的每一行代表一次购买清单(注意你购买十盒牛奶也只计一次,即只记录某个商品的出现与否)。数据记录的所有项的集合称为总项集,上表中的总项集 S = {牛奶,面包,尿布,啤酒,鸡蛋,可乐}。

     一、关联规则、自信度、自持度的定义

      关联规则就是有关联的规则,形式是这样定义的:两个不相交的非空集合 X、Y,如果有 X-->Y,就说 X-->Y 是一条关联规则。举个例子,在上面的表中,我们发现购买啤酒就一定会购买尿布,{啤酒}-->{尿布} 就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述,

       支持度的定义:support(X-->Y) = |X 交 Y| / N=集合 X 与集合 Y 中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3 / 5 = 60%。

      自信度的定义:confidence(X-->Y) = |X 交 Y| / |X| = 集合 X 与集合 Y 中的项在一条记录中同时出现的次数/集合 X 出现的个数 。例如:confidence({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数 / 啤酒出现的次数 = 3 / 3 = 100%; confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数 / 尿布出现的次数 = 3 / 4 = 75%。

      这里定义的支持度和自信度都是相对的支持度和自信度,不是绝对支持度,绝对支持度abs_support = 数据记录数 N * support。

      支持度和自信度越高,说明规则越强,关联规则挖掘就是挖掘出满足一定强度的规则。

    二、关联规则挖掘的定义与步骤

      关联规则挖掘的定义:给定一个交易数据集 T,找出其中所有支持度 support >= min_support、自信度 confidence >= min_confidence的关联规则。

      有一个简单而粗鲁的方法可以找出所需要的规则,那就是穷举项集的所有组合,并测试每个组合是否满足条件,一个元素个数为 n 的项集的组合个数为 2^n-1(除去空集),所需要的时间复杂度明显为 O(2^N),对于普通的超市,其商品的项集数也在 1 万以上,用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。

      仔细想一下,我们会发现对于 {啤酒-->尿布},{尿布-->啤酒} 这两个规则的支持度实际上只需要计算 {尿布,啤酒} 的支持度,即它们交集的支持度。于是我们把关联规则挖掘分两步进行:

      1)生成频繁项集

      这一阶段找出所有满足最小支持度的项集,找出的这些项集称为频繁项集。

      2)生成规则

      在上一步产生的频繁项集的基础上生成满足最小自信度的规则,产生的规则称为强规则。

      关联规则挖掘所花费的时间主要是在生成频繁项集上,因为找出的频繁项集往往不会很多,利用频繁项集生成规则也就不会花太多的时间,而生成频繁项集需要测试很多的备选项集,如果不加优化,所需的时间是 O(2^N)。

    三、Apriori 定律

      为了减少频繁项集的生成时间,我们应该尽早的消除一些完全不可能是频繁项集的集合,Apriori 的两条定律就是干这事的。

      Apriori 定律 1):如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合 {A,B} 是频繁项集,即 A、B 同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集 {A},{B} 出现次数必定大于等于 min_support,即它的子集都是频繁项集。

      Apriori 定律 2):如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合 {A} 不是频繁项集,即 A 出现的次数小于 min_support,则它的任何超集如{A,B} 出现的次数必定小于 min_support,因此其超集必定也不是频繁项集。

      利用这两条定律,我们抛掉很多的候选项集,Apriori 算法就是利用这两个定理来实现快速挖掘频繁项集的。

    四、Apriori 算法

      Apriori 是由 a priori 合并而来的,它的意思是后面的是在前面的基础上推出来的,即先验推导,怎么个先验法,其实就是二级频繁项集是在一级频繁项集的基础上产生的,三级频繁项集是在二级频繁项集的基础上产生的,以此类推。

      Apriori 算法属于候选消除算法,是一个生成候选集、消除不满足条件的候选集、并不断循环直到不再产生候选集的过程。

      

      上面的图演示了 Apriori 算法的过程,注意看由二级频繁项集生成三级候选项集时,没有 {牛奶,面包,啤酒},那是因为 {面包,啤酒} 不是二级频繁项集,这里利用了 Apriori 定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布} 是最大频繁子集。

      算法的思想知道了,这里也就不上伪代码了,我认为理解了算法的思想后,子集去构思实现才能理解更深刻,这里贴一下我的关键代码:

    复制代码
     1 public static void main(String[] args) {
     2         // TODO Auto-generated method stub
     3         record = getRecord();// 获取原始数据记录
     4         List<List<String>> cItemset = findFirstCandidate();// 获取第一次的备选集
     5         List<List<String>> lItemset = getSupportedItemset(cItemset);// 获取备选集 cItemset 满足支持的集合
     6 
     7         while (endTag != true) {// 只要能继续挖掘
     8             List<List<String>> ckItemset = getNextCandidate(lItemset);// 获取第下一次的备选集
     9             List<List<String>> lkItemset = getSupportedItemset(ckItemset);// 获取备选集 cItemset 满足支持的集合
    10             getConfidencedItemset(lkItemset, lItemset, dkCountMap, dCountMap);// 获取备选集 cItemset 满足置信度的集合
    11             if (confItemset.size() != 0)// 满足置信度的集合不为空
    12                 printConfItemset(confItemset);// 打印满足置信度的集合
    13             confItemset.clear();// 清空置信度的集合
    14             cItemset = ckItemset;// 保存数据,为下次循环迭代准备
    15             lItemset = lkItemset;
    16             dCountMap.clear();
    17             dCountMap.putAll(dkCountMap);
    18         }
    复制代码

      如果想看完整的代码,可以查看我的 github,数据集的格式跟本文所述的略有不通,但不影响对算法的理解。

      下一篇将介绍效率更高的算法 -- FP-Grow 算法。

    参考文献:

      [1]. Pang-Ning Tan,Michael Steinbach. Introduction to Data Mining.

      [2]. HanJiaWei. Data Mining: concept and  techniques.

      感谢关注,欢迎回帖交流。

      转载请注明出处:www.cnblogs.com/fengfenggirl

    展开全文
  • 数据挖掘原理与SPSS_Clementine应用宝典.ppt 数据挖掘 机器学习原理与SPSS Clementine应用宝典 第1章 数据挖掘概述.ppt 数据挖掘 机器学习原理与SPSS Clementine应用宝典 第2章 数据挖掘可挖掘的知识类型.ppt 数据...
  • 出处: fengfenggirl(@...我计划整理数据挖掘基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。 关联规则挖掘在电商、零售、大气物理、生物医学

    出处: fengfenggirl(@也爱数据挖掘)

    网址:http://www.cnblogs.com/fengfenggirl/p/associate_apriori.html


    我计划整理数据挖掘的基本概念和算法,包括关联规则挖掘、分类、聚类的常用算法,敬请期待。今天讲的是关联规则挖掘的最基本的知识。


    关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。


    啤酒与尿布的故事已经成为了关联规则挖掘的经典案例,还有人专门出了一本书《啤酒与尿布》,虽然说这个故事是哈弗商学院杜撰出来的,但确实能很好的解释关联规则挖掘的原理。我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念:


    TID Items

    T1 {牛奶,面包}

    T2 {面包,尿布,啤酒,鸡蛋}

    T3 {牛奶,尿布,啤酒,可乐}

    T4 {面包,牛奶,尿布,啤酒}

    T5 {面包,牛奶,尿布,可乐}


    表中的每一行代表一次购买清单(注意你购买十盒牛奶也只计一次,即只记录某个商品的出现与否)。数据记录的所有项的集合称为总项集,上表中的总项集S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}。


    一、关联规则、自信度、自持度的定义


    关联规则就是有关联的规则,形式是这样定义的:两个不相交的非空集合X、Y,如果有X–>Y,就说X–>Y是一条关联规则。举个例子,在上面的表中,我们发现购买啤酒就一定会购买尿布,{啤酒}–>{尿布}就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述,


    支持度的定义:support(X–>Y) = |X交Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}–>{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%。


    自信度的定义:confidence(X–>Y) = |X交Y|/|X| = 集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数 。例如:confidence({啤酒}–>{尿布}) = 啤酒和尿布同时出现的次数/啤酒出现的次数=3/3=100%;confidence({尿布}–>{啤酒}) = 啤酒和尿布同时出现的次数/尿布出现的次数 = 3/4 = 75%。


    这里定义的支持度和自信度都是相对的支持度和自信度,不是绝对支持度,绝对支持度abs_support = 数据记录数N*support。


    支持度和自信度越高,说明规则越强,关联规则挖掘就是挖掘出满足一定强度的规则。


    二、关联规则挖掘的定义与步骤


    关联规则挖掘的定义:给定一个交易数据集T,找出其中所有支持度support >= min_support、自信度confidence >= min_confidence的关联规则。


    有一个简单而粗鲁的方法可以找出所需要的规则,那就是穷举项集的所有组合,并测试每个组合是否满足条件,一个元素个数为n的项集的组合个数为2^n-1(除去空集),所需要的时间复杂度明显为O(2^N),对于普通的超市,其商品的项集数也在1万以上,用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。


    仔细想一下,我们会发现对于{啤酒–>尿布},{尿布–>啤酒}这两个规则的支持度实际上只需要计算{尿布,啤酒}的支持度,即它们交集的支持度。于是我们把关联规则挖掘分两步进行:


    1)生成频繁项集


    这一阶段找出所有满足最小支持度的项集,找出的这些项集称为频繁项集。


    2)生成规则


    在上一步产生的频繁项集的基础上生成满足最小自信度的规则,产生的规则称为强规则。


    关联规则挖掘所花费的时间主要是在生成频繁项集上,因为找出的频繁项集往往不会很多,利用频繁项集生成规则也就不会花太多的时间,而生成频繁项集需要测试很多的备选项集,如果不加优化,所需的时间是O(2^N)。


    三、Apriori定律


    为了减少频繁项集的生成时间,我们应该尽早的消除一些完全不可能是频繁项集的集合,Apriori的两条定律就是干这事的。


    Apriori定律1):如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。


    Apriori定律2):如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合{A}不是频繁项集,即A出现的次数小于min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。


    利用这两条定律,我们抛掉很多的候选项集,Apriori算法就是利用这两个定理来实现快速挖掘频繁项集的。


    四、Apriori算法


    Apriori是由a priori合并而来的,它的意思是后面的是在前面的基础上推出来的,即先验推导,怎么个先验法,其实就是二级频繁项集是在一级频繁项集的基础上产生的,三级频繁项集是在二级频繁项集的基础上产生的,以此类推。


    Apriori算法属于候选消除算法,是一个生成候选集、消除不满足条件的候选集、并不断循环直到不再产生候选集的过程。



    上面的图演示了Apriori算法的过程,注意看由二级频繁项集生成三级候选项集时,没有{牛奶,面包,啤酒},那是因为{面包,啤酒}不是二级频繁项集,这里利用了Apriori定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。


    算法的思想知道了,这里也就不上伪代码了,我认为理解了算法的思想后,子集去构思实现才能理解更深刻,这里贴一下我的关键代码:


    public static void main(String[] args) {


    // TODO Auto-generated method stub

    record = getRecord();

    // 获取原始数据记录

    List<List<String>> cItemset = findFirstCandidate();

    // 获取第一次的备选集

    List<List<String>> lItemset = getSupportedItemset(cItemset);

    // 获取备选集cItemset满足支持的集合


    while (endTag != true) {

    // 只要能继续挖掘

    List<List<String>> ckItemset = getNextCandidate(lItemset);

    // 获取第下一次的备选集

    List<List<String>> lkItemset = getSupportedItemset(ckItemset);

    // 获取备选集cItemset满足支持的集合

    getConfidencedItemset(lkItemset, lItemset, dkCountMap, dCountMap);

    // 获取备选集cItemset满足置信度的集合

    if (confItemset.size() != 0)

    // 满足置信度的集合不为空

    printConfItemset(confItemset);

    // 打印满足置信度的集合

    confItemset.clear();

    // 清空置信度的集合

    cItemset = ckItemset;

    // 保存数据,为下次循环迭代准备

    lItemset = lkItemset;

    dCountMap.clear();

    dCountMap.putAll(dkCountMap);

    }


    如果想看完整的代码,可以查看我的github,数据集的格式跟本文所述的略有不通,但不影响对算法的理解。


    展开全文
  • 今天看了一下关联规则分析中的Apriori算法,先了解下基本概念: 关联规则分析用于发现隐藏在大型数据集中的有意义的联系。在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、...
    今天看了一下关联规则分析中的Apriori算法,先了解下基本概念:
    关联规则分析用于发现隐藏在大型数据集中的有意义的联系。在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。
    关联规则挖掘形式化定义:
    原始数据描述

      I ={i1, i2,…, im}是所有项(item)的集合,若干项的集合,称为项集(Item Sets)

      T为交易(transaction,事务) t的集合,其中,交易t是项的集合,并且t⊆I 

      A C分别是一个I中项的集合,如果A⊆TC⊆T ,且A∩C=Φ那么称交易T包含A ∪ C

    目标数据描述

      所有形如A⇒C 蕴涵式的称为关联规则,这里A⊂I, C⊂I,并且A∩C=Φ

    为了描述关联规则的有用性和确定性
    •Ø关联规则的支持度
    如果交易集Ts次交易包含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-项集,A2-项集
    关联规则的挖掘步骤
    发现频繁项集
    由频繁项集生成满足最小支持度和最小置信度的关联规则
     
    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();
    	}
    }

    代码托管:https://github.com/fighting-one-piece/repository-datamining.git

     

     


    展开全文
  • 数据挖掘关联规则挖掘的应用研究 ,吴海玲,王志坚,本文首先介绍关联规则基本原理,并简单概括其挖掘任务,然后说明关联规则的经典挖掘算法Apriori算法,通过一个实例分析进一步明��
  • 数据挖掘进阶之关联规则挖掘FP-Growth算法 绪 近期在写论文方面涉及到了数据挖掘,需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用...
  • 关联规则算法的PPT
  • 一、概述本篇博文主要阐述数据挖掘相关的关联规则挖掘的算法(Apriori算法)。主要介绍关联规则基本概念、Apriori算法原理和Apriori算法实例,文章末尾处附加Apriori算法源程序。二、关联规则挖掘的基本概念关联...
  • 关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。...我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘基本概念: TID Items
  • 关联规则挖掘 基本概念 Apriori算法 Apriori裁剪原理: 对于任意项集,如果它不是频繁集,则它的任何超集不用产生/测试! 算法流程: 关于连接操作: 一个例子: Apriori算法存在问题: 多次扫描数据库 产生...
  • 这篇文章主要介绍三个知识点,也是我《数据挖掘与分析》课程讲课的内容。 1.关联规则挖掘概念及实现过程;...关联规则数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系。
  • 数据挖掘基本原理,概念,算法,包括关联规则,分类,聚类,预测,WEB分析等
  • 数据挖掘 机器学习原理与SPSS Clementine应用宝典 第10章 关联规则.rar
  • 关联规则挖掘(Association rule mining)是数据挖掘中最活跃的研究方法之一,可以用来发现不同事物之间的联系,最早是为了发现超市交易数据库中不同的商品之间的关系。 例如一个超市的经理想要更多的了解顾客的购物...
  • 数据挖掘中的关联规则挖掘

    千次阅读 2016-04-21 11:36:32
    数据挖掘中的关联规则挖掘
  • 浅谈数据挖掘中的关联规则挖掘

    千次阅读 2017-09-07 10:11:00
    数据挖掘是指以某种方式分析数据源,从中发现一些潜在的有用的信息,所以数据挖掘又称作知识发现,而关联规则挖掘则是数据挖掘中的一个很重要的课题,顾名思义,它是从数据背后发现事物之间可能存在的关联或者联系。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,836
精华内容 5,134
关键字:

关联规则数据挖掘的基本原理