精华内容
下载资源
问答
  • 一个事务数据库中的关联规则挖掘可以描述如下 设I= {i1, i2, , im} 是一个项目集合 事务数据 库D= {t1, t2, , tn} 是由一系列具有惟一标识TID事务组成 每一个事务ti (i=1, 2, , n)都对应I上一个子集 定义3.1 设...
  • 关联规则算法

    万次阅读 2014-02-17 11:31:25
    关联规则是形如X→Y蕴涵式,其中, X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。 目录 1简介 ▪ 故事 ▪ 定义 ▪ 例子 2挖掘过程 ...

    关联规则

    关联规则是形如X→Y的蕴涵式,其中, X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS)


    故事 
    在描述有关关联规则的一些细节之前,先来看一个有趣的故事: "尿布与啤酒"的故事。
    在一家超市里,有一个有趣的现象:尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话,而是发生在美国沃尔玛连锁店超市的真实案例,并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统,为了能够准确了解顾客在其门店的购买习惯,沃尔玛对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上,沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是:"跟尿布一起购买最多的商品竟是啤酒!经过大量实际调查和分析,揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自己买一些啤酒。产生这一现象的原因是:美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。
    按常规思维,尿布与啤酒风马牛不相及,若不是借助数据挖掘技术对海量交易数据进行挖掘和分析,沃尔玛是不可能发现数据内在这一有价值的规律的。

    定义

    根据韩家炜等观点,关联规则定义为:
    假设I是项的集合。给定一个交易数据库D,其中每个事务(Transaction)t是I的非空子集,即,每一个交易都与一个唯一的标识符TID(Transaction ID)对应。关联规则在D中的支持度(support)是D中事务同时包含X、Y的百分比,即概率置信度(confidence)是D中事物已经包含X的情况下,包含Y的百分比,即条件概率。如果满足最小支持度阈值和最小置信度阈值。这些阈值是根据挖掘需要人为设定。

    例子

    基本概念表1:关联规则的简单例子
    TID
    网球拍
    网 球
    运动鞋
    羽毛球
    1
    1
    1
    1
    0
    2
    1
    1
    0
    0
    3
    1
    0
    0
    0
    4
    1
    0
    1
    0
    5
    0
    1
    1
    1
    6
    1
    1
    0
    0
    用一个简单的例子说明。表1是顾客购买记录的数据库D,包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则(频繁二项集):网球拍与网球,事务1,2,3,4,6包含网球拍,事务1,2,6同时包含网球拍和网球,X^Y=3, D=6,支持度(X^Y)/D=0.5;X=5, 置信度(X^Y)/X=0.6。若给定最小支持度α = 0.5,最小置信度β = 0.6,认为购买网球拍和购买网球之间存在关联。

    2挖掘过程编辑

    两个阶段

    关联规则挖掘过程主要包含两个阶段:第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Itemsets),第二阶段再由这些高频项目组中产生关联规则(Association Rules)。
    关联规则挖掘的第一阶段必须从原始资料集合中,找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言,必须达到某一水平。一项目组出现的频率称为支持度(Support),以一个包含A与B两个项目的2-itemset为例,我们可以经由公式(1)求得包含{A,B}项目组的支持度,若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时,则{A,B}称为高频项目组。一个满足最小支持度的k-itemset,则称为高频k-项目组(Frequent k-itemset),一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1,直到无法再找到更长的高频项目组为止。
    关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则,是利用前一步骤的高频k-项目组来产生规则,在最小信赖度(Minimum Confidence)的条件门槛下,若一规则所求得的信赖度满足最小信赖度,称此规则为关联规则。例如:经由高频k-项目组{A,B}所产生的规则AB,其信赖度可经由公式(2)求得,若信赖度大于等于最小信赖度,则称AB为关联规则。

    案例分析

    就沃尔马案例而言,使用关联规则挖掘技术,对交易资料库中的纪录进行资料挖掘,首先必须要设定最小支持度与最小信赖度两个门槛值,在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布,啤酒」,满足下列条件,将可接受「尿布,啤酒」的关联规则。用公式可以描述Support(尿布,啤酒)>=5%且Confidence(尿布,啤酒)>=70%。其中,Support(尿布,啤酒)>=5%于此应用范例中的意义为:在所有的交易纪录资料中,至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布,啤酒)>=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中,至少有70%的交易会同时购买啤酒。因此,今后若有某消费者出现购买尿布的行为,超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据「尿布,啤酒」关联规则,因为就该超市过去的交易纪录而言,支持了“大部份购买尿布的交易,会同时购买啤酒”的消费行为。
    从上面的介绍还可以看出,关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据,则在关联规则挖掘之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值),数据的离散化是数据挖掘前的重要环节,离散化的过程是否合理将直接影响关联规则的挖掘结果。

    分类编辑

    按照不同情况,关联规则可以进行分类如下:
    1.基于规则中处理的变量的类别:
    关联规则处理的变量可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书” ,是布尔型关联规则;性别=“女”=>avg(收入)=2300,涉及的收入是数值类型,所以是一个数值型关联规则。
    2.基于规则中数据的抽象层次:
    基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。
    3.基于规则中涉及到的数据的维数:
    关联规则中的数据,可以分为单维的和多维的。在单维的关联规则中,我们只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换成另一句话,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户的购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。

    4相关算法编辑

    Apriori算法

    Apriori算法:使用候选项集找频繁项集
    Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。
    算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递推的方法。
    可能产生大量的候选集,以及可能需要重复扫描数据库,是Apriori算法的两大缺点。

    基于划分的算法

    基于划分的算法
    Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的,可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后,处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈;而另一方面,每个独立的处理器生成频集的时间也是一个瓶颈。

    FP-树频集算法

    FP-树频集算法
    针对Apriori算法的固有缺陷,J. Han等提出了不产生候选挖掘频繁项集的方法:FP-树频集算法。采用分而治之的策略,在经过第一遍扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息,随后再将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关,然后再对这些条件库分别进行挖掘。当原始数据量很大的时候,也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明,FP-growth对不同长度的规则都有很好的适应性,同时在效率上较之Apriori算法有巨大的提高。

    5应用编辑

    应用

    关联规则挖掘技术已经被广泛应用在西方金融行业企业中,它可以成功预测银行客户需求。一旦获得了这些信息,银行就可以改善自身营销。银行天天都在开发新的沟通客户的方法。各银行在自己的ATM机上就捆绑了顾客可能感兴趣的本行产品信息,供使用本行ATM机的用户了解。如果数据库中显示,某个高信用限额的客户更换了地址,这个客户很有可能新近购买了一栋更大的住宅,因此会有可能需要更高信用限额,更高端的新信用卡,或者需要一个住房改善贷款,这些产品都可以通过信用卡账单邮寄给客户。当客户打电话咨询的时候,数据库可以有力地帮助电话销售代表。销售代表的电脑屏幕上可以显示出客户的特点,同时也可以显示出顾客会对什么产品感兴趣。
    同时,一些知名的电子商务站点也从强大的关联规则挖掘中的受益。这些电子购物网站使用关联规则中规则进行挖掘,然后设置用户有意要一起购买的捆绑包。也有一些购物网站使用它们设置相应的交叉销售,也就是购买某种商品的顾客会看到相关的另外一种商品的广告。
    但是在我国,“数据海量,信息缺乏”是商业银行在数据大集中之后普遍所面对的尴尬。金融业实施的大多数数据库只能实现数据的录入、查询、统计等较低层次的功能,却无法发现数据中存在的各种有用的信息,譬如对这些数据进行分析,发现其数据模式及特征,然后可能发现某个客户、消费群体或组织的金融和商业兴趣,并可观察金融市场的变化趋势。可以说,关联规则挖掘的技术在我国的研究与应用并不是很广泛深入。

    研究

    由于许多应用问题往往比超市购买问题更复杂,大量研究从不同的角度对关联规则做了扩展,将更多的因素集成到关联规则挖掘方法之中,以此丰富关联规则的应用领域,拓宽支持管理决策的范围。如考虑属性之间的类别层次关系,时态关系,多表挖掘等。围绕关联规则的研究主要集中于两个方面,即扩展经典关联规则能够解决问题的范围,改善经典关联规则挖掘算法效率和规则兴趣性。[1]

    展开全文
  • 上次介绍了分类算法K近邻,其属于预测分类的一种,那么这次我们就学习一下数据挖掘算法中的关联算法Apriori,其最原始的...一、重要的定义事务型数据:关联分析的数据一般是事务型数据,事务型数据的特点是数据集中...

    6bd67ff61a15d3485a3ad30147716a17.png

    上次介绍了分类算法K近邻,其属于预测分类的一种,那么这次我们就学习一下数据挖掘算法中的关联算法Apriori,其最原始的应用就是挖掘交易数据中商品之间的关联,最经典的就是“尿布和啤酒”的案例,当然在当今这个互联网技术发达的时代,关联算法已经得到了很大的发展,在各行各领域上都有了各自的拓展和取得成效,下面就直奔主题。

    一、重要的定义

    事务型数据:关联分析的数据一般是事务型数据,事务型数据的特点是数据集中每一行记录对应一个事务(交易数据的明细),每个事务中的元素称为项,项集就是包含1个或者多个项的集合,若包含K个项,则称为K项集。

    支持度:一个项集的支持度是指该项集在事务型数据中出现的频率。例如一组包含了100个项集的事务型数据,其中项集{A,B}在事务型数据中共有出现了30次,则项集{A,B}的支持度为0.3,可以定义项集X的支持度函数如下,其中,N指事务型数据的总记录数,count(x)指项集X在事务型数据中出现的次数:

    37c08962e4f50885cab7bea035c1ac44.png

    置信度:支持度很低的项集规则一般情况下判断为偶然出现,支持度通常用来过滤掉那些无意义的项集规则。一个项集的置信度是指是用于度量该项集的预测准确度,简单来讲就是假设有一个二项集,已知其第一项为项A,而这个项集第二项为项B的概率为P,则P就是这个二项集的置信度 ,置信度函数可以表示为:

    e47016a9ba34e705f1d372a44b731996.png

    提升度:若频繁项集规则的支持度和置信度都比较高,我们称这些规则为强规则。要想知道这些强规则是否有效,要根据提升度的计算结果判断。提升度表示含有X的条件下,同时含有Y的概率,与Y总体发生的概率之比。简单理解的话,假设Lift(X→Y)的值为a,则表示顾客在已经购买了商品X的前提条件下,会再去购买商品Y的可能性是一般顾客购买商品Y可能性的a倍。提升度函数可表示为:

    6f54b5428a4c8ef0e1b8b431b4438c65.png

    二、Apriori算法原理与性质

    Apriori算法的核心是利用频繁项集性质的先验性质,即一个频繁项集的所有子集必须也是频繁的,也就是n-1项集用于探索n项集,从而减少关联规则的搜寻空间。Apriori算法需要在事先给定支持度阈值,作为判断频繁项集的标准。首先对事务型数据集进行扫描,产生第一个候选数据项集,且该候选数据集为1项集集合。根据事先给定的支持度,筛选出符合阈值要求的集合作为1项频繁项集,记作S_1。然后再次从原始数据集中搜索包含S_1的2项集集合作为下一个候选数据项集,记作S_2。采用相同的方法,直到生成频繁n项集S_n,且已n+1项集不能达到支持度和置信度的限制条件。至此,已完成了提取原始数据中的频繁项集的工作。针对这些频繁项集,使用给定的置信度进行筛选复合阈值条件的项集规则,便完成了关联规则的提取。

    在Apriori关联算法中,频繁项集都具有“频繁项集的所有子集也都是频繁项集”的性质。所以如果一个候选k项集的k-1项子集不在k-1项的频繁项集中,则能判断该候选不是频繁的,并从该候选项集中删除,获得压缩后的k项集,再删除不满足最小支持度的项,从而获得频繁k项集。Apriori算法利用这个性质,从而减少寻找数据集中频繁项集的时间。

    三、Apriori算法步骤

    (1):扫描原始事务型数据,并将提取候选1项集,根据给定的最小支持度s,提取项集频数不小于支持度s的项集,形成频繁1项集。
    (2):扫描原始事务型数据并提取候选2项集的集合,且对集合中各个2项集进行判断,将不包含频繁1项集的2项集排除,形成新的集合作为候选集。根据支持度s筛选出频繁2项集。
    (3):重复第二步的思路,得到频繁3项集、频繁4项集......频繁n项集,且n+1项集都不满足支持度阈值条件。
    (4):给定置信度,判断各频繁项集规则是否为有效的规则,计算该规则的提升度,判断是强规则是否有效。

    下面是Apriori算法过程示意图:

    52b15cff104a27c9797350b0290b8cdd.png

    四、算法优点与局限

    Apriori算法巧妙地利用了候选集合和频繁集之间的关系,利用其先验性质,从而得到全部频繁项集。在这个迭代的过程中,经过对候选集的不断剪枝,最终就会达到减少候选集规模的效果,体现出算法的效率。Apriori算法非常适合处理大规模的事务型数据,并且从数据中提取的关联规则也很容易理解。

    但是也需要注意三个问题,第一个问题就是当低阶的频繁项集有多个时,算法可能会产生大量的候选项集。第二个问题就是算法需要重复地扫描数据库,对于这个问题的解决,已经提出了许多Apriori算法的变形。最后的问题是无法对稀有信息进行分析,就是当数据集中某些项所占的比例很少,由于支持度阈值的限制,会被视为关联规则之外,这样往往会错过几类规则的分析。但是若为处理这个问题把支持度阈值调低,那么算法的效率就会下降。

    五、基于R实现关联规则挖掘

    1、前期准备

    在R语言中实现关联规则的挖掘我们会使用到arules拓展包,也有一套比较固定的过程步骤:

    2b86f0a6c525ff45c7b38642a61c3d7f.png

    首先实arules包,其apriori函数封装Apriori算法,然后arulesViz则是实现对关联规则的可视化 。

    library(arules)
    library(arulesViz)

    接着是轮到我们需要挖掘的事务型数据集登场了,之前做论文时收集过双十一的交易数据,不过数据量不大,所以我们还是以R语言中自带的Groceries数据集,记录了某个杂货店一个月的真实交易记录。此处我们需要引入稀疏矩阵的概念,稀疏矩阵的每列表示一种商品,取值为0或者1,1表示交易记录中包含该列对应的商品,而矩阵的每行表示一个交易记录。在R中,我们可以直接使用read.transactions()创建稀疏矩阵。

    #将工作目录中的交易数据集转换为稀疏矩阵的形式
    groceries <- read.transactions("groceries.csv", sep = ",")
    #使用summary()查看groceries的具体信息
    summary(groceries)

    6b4d910cfc6ae0918ad3681d0f42238c.png

    上面的截图包含了整个交易数据集中购买次数比较多的商品,比如whole milk被购买了2513次,其次还有描述交易记录的规模,比如在一次交易中只买了一样商品的记录就要2159条。当然要想更直观地看到交易数据集中商品的交易频数,可以使用itemFrequencyPlot(),使用参数TopN指定需要获取商品的数量,下面对指定交易频数前十的商品进行可视化:

    51b5dc1512bca260ce80aa2b8e8546c3.png

    2、模型建立

    在建立模型之前,我们需要设定支持度和置信度的值,这往往是个大难题,因为没有具体的方法帮助我们,假如支持度和置信度设置过低,就会导致得到的规则大部分因太过普通而没有太大价值。反之,若两者的阈值设置得过低,则会导致模型所产生的规则数量会非常多,更有可能算法需要运行长时间才可得到结果。我一般的理解就是支持度可以根据数据集的实际情况以及周期来帮助估计出其初始阈值,然后根据得到的规则再调整。下面就实现对Groceries的关联规则挖掘:

    # 设置支持度0.006,置信度0.25,规则的最小项集为2
    groceryrules <- apriori(groceries, parameter = list(support =0.006, confidence = 0.25, minlen = 2))
    #查看规则规模
    summary(groceryrules)

    9ea38eda61e6e0249c2df527bdd3d495.png

    可以看到我们得到符合支持度置信度阈值的规则一共有463条,其中2项集规则150条,3项集规则297条,4项集规则16条。

    3、认识规则模式

    在分析结论规则之前,需要先认识规则结果的分类模式,一般关联规则会被分作三类。首先是可行的关联规则,可行的规则既是明确的,又要是有用的,但这种类型的规则一般不太容易被发现,需要更多的理解和参数的调整。其次是平凡规则,平凡规则是指那些在现实生活中过于明显的规则,虽然它们是很明确,但是由于太过普通常见,缺乏有用的商业价值。最后是令人费解的规则,如果商品之间的规则过于奇怪,以至于可能需要更多的信息来理解规则的含义,称这些规则是令人费解的规则,而通常这些规则可能只是数据中的一种随机模式。R语言Apriori算法得到的关联规则是由lhs(规则前项)和rhs(规则后项)组成,lhs表示触发规则需要满足的条件,而rhs表示满足条件后的预期结果。我们可以使用下面的方法查看前5条关联规则:

    #查看前五条关联规则
    inspect(groceryrules[1:5])

    037a66d016027e2e744a63570e2e05b9.png

    4、探索关键规则

    我们可以看到符合支持度和置信度阈值的关联规则共有463条,当然其中起到关键价值的规则应该只是占有很少的一部分,所以我们需要通过特别的方法快速地从这四百多条规则中搜索出比较突出的规则或者我们指定的商品规则,下面就介绍一些常用的方法:

    1、按支持度排序的部分规则

    支持度作为我们关联规则算法的第一个门槛,其阈值的设置就是帮助我们排除一些具有偶然性的规则。我们将规则按照支持度降序排列,就能得到关联度由大带小的规则,并且通过观察排在前列的规则,从中抽取较为有用的规则。

    #按照支持度降序排列规则
    inspect(sort(groceryrules,by='con'))

    2d4177cd18df12137a30734689ca6980.png
    高支持度的前10条规则

    2、按置信度排序的部分规则

    支持度只是我们筛选关联规则的第一个判断条件,接着是置信度,置信度可以印证我们得到的高支持度的关联规则用于多少的可信度。我们同样地将关联规则以置信度降序排序.

    inspect(sort(groceryrules,by='sup'))

    f19f3c4704ddf34fc9caf78d83432a71.png
    高置信度的前10条规则

    3、按提升度排序的部分规则

    除了上面支持度和置信度之外,我们往往很少用到的提升度也可以用于对关联规则的排序。通常在挖掘过程中,提升度大于1的规则才是有意义的,而低于1的会被划分为无效的关联规则 ,所以通过提升度降序排列规则,也是另外一个挖掘的维度。

    inspect(sort(groceryrules,by='lift'))

    f6bbbcb88651078803da42bc4b02408c.png
    高提升度的前10条规则

    4、选择包含目标商品的规则

    有些时候我们需要分析特定的商品与之关联的规则,我们可以通过筛选出包含指定商品的规则,并从这些规则中提取支持度、置信度、提升度指标值都比较大的规则进行分析,比如我们抽取whole milk的关联规则。

    A1 = subset(groceryrules, items %in% c('whole milk'))
    inspect(A1)

    b018ba3d81fafd0230a34df838b98989.png
    包含whole milk的前10条规则

    在我们从多角度提取出关联规则之后,我们就可以对关联规则的内容进行实际意义的分析,通过模拟生活场景等方法去理解规则出现的原因,这点就是我们挖掘关联规则的关键所在。

    5、规则可视化

    来到这里,我们最后的任务就是对关联规则实现可视化。R语言中对关联规则的可视化使用的拓展包为arulesViz包。关联规则的可视化包括graph图、grouped图和paracoord图共三种类型。使用的函数是plot(),参数method决定作图类型。

    #加载arulesViz
    library(arulesViz)
    # 使用包含whole milk的前5条规则,分别用三种方法进行可视化
    plot(A1[1:5],method = 'graph',control=list(main='关联规则-graph'))
    plot(A1[1:5],method = 'grouped',control=list(main='关联规则-grouped'))
    plot(A1[130:140],method = 'paracoord',control=list(main='关联规则-paracoord'))

    9cce4a835afa6a9789d33c97d4beeb32.png
    graph图

    在graph图中,商品之间通过有向箭头组成一条规则,圆圈的大小用于度量支持度,面积越大表示该规则的支持度越大;圆圈的颜色表示支持度,颜色越深代表规则的支持度越大。

    0717cfabb56e78e01c62b8c35d62e20d.png
    group图

    而grouped图展现的效果与graph图有着异曲同工的地方,图中的横坐标为规则前项lhs,纵轴是结果项rhs,圆圈的大小表示规则支持度的大小,圆圈颜色深浅代表规则提升度的高低。

    8710a6faf8462c1cacb0d46cee409ac7.png
    paracoord图

    而paracoord图表示上没有前两种图那么直观,paracoord图通过由左至右的带箭头折线表示关联股则的lhs和rhs,用折线的粗细表示规则支持度的大小,灰度深浅表示提升度的高低。

    至此,我们已经将R语言中实现Apriori算法的过程步骤和原理都过了一遍,而Apriori算法作为最基础的关联规则挖掘算法,我们学习起来其实并没有太大的难度。其他的关联算法,比如Eclat算法、FP-Tree算法的学习难度是比Apriori算法高的,如果大家有兴趣的话,也可自行到网上学习,或者之后我会补上这些算法的原理及实现。

    展开全文
  • 为了提高个性化推荐效率和推荐质量,平衡冷门与热门数据推荐权重,对关联规则的Apriori算法频繁项集挖掘问题进行了重新评估和分析,定义了新测评指标推荐非空率以及k前项频繁项集关联规则的概念,设计了基于 k 前...
  • Apriori关联规则算法的目的就是找出所有的频繁项集,所以需要定义一个评估标准找出频繁项集,即最小支持度。 首先从原始数据集中找出出现的所有项,对应数据集确定候选1项集,根据候选一项集每项在原始项集中的出现...
    1. 算法原理

    Apriori关联规则算法的目的就是找出所有的频繁项集,所以需要定义一个评估标准找出频繁项集,即最小支持度。 首先从原始数据集中找出出现的所有项,对应数据集确定候选1项集,根据候选一项集每项在原始项集中的出现次数计算每一项的sup值。比较sup值 / 原始数据集数 的值与最小支持度,小于则舍去,计算出频繁一项集,然后对频繁一项集两项之间求补集,并按照一项集中求sup的方法求取候选二项集及频繁二项集。之后递归求取频繁n项集,当频繁项集项数只有一项时递归结束。得到最后的频繁项集。

    2. 代码实现
    import java.util.ArrayList;
    
    /**
     * @Description 项集item
     * @Author Clxk
     * @Date 2019/4/15 10:57
     * @Version 1.0
     */
    public class Data {
    
        private ArrayList<String> data = new ArrayList<>();
    
        private int cnt;
    
        public ArrayList<String> getData() {
            return data;
        }
    
        public void setData(ArrayList<String> data) {
            this.data = data;
        }
    
        public int getCnt() {
            return cnt;
        }
    
        public void setCnt(int cnt) {
            this.cnt = cnt;
        }
    
        @Override
        public boolean equals(Object obj) {
            Data rhs = (Data) obj;
            boolean eq = this.cnt == rhs.cnt;
    
            if(this.cnt == rhs.cnt) {
                for(int i = 0; i < data.size(); i++) {
                    if(!data.get(i).equals(rhs.data.get(i))) {
                        eq = false;
                        break;
                    }
                }
            }
            return eq;
        }
    }
    
    
    import java.util.*;
    
    /**
     * @Description Apriori
     * @Author Clxk
     * @Date 2019/4/15 10:43
     * @Version 1.0
     */
    public class Main {
    
        /**
         * 初始数据集最大值
         */
        private static final int MAXN = 1000;
        /**
         * 数据集长度、最小支持度
         */
        private static int datacnt = 0;
        private static double minsupport = 0;
        /**
         * 初始数据集
         */
        private static ArrayList<String> []data = new ArrayList[500];
        /**
         * 项集结构
         */
        private static ArrayList<Data> items = new ArrayList<>();
    
    
        public static void main(String[] args) {
    
            /**
             * 原始数据集读取
             */
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入数据集的大小: ");
            datacnt = scanner.nextInt();
            System.out.println("请输入最小支持度: ");
            minsupport = scanner.nextDouble();
            System.out.println("请输入原始数据集: ");
            String str;
            scanner.nextLine();
            for (int i = 0; i < datacnt; i++) {
                data[i] = new ArrayList<>();
                str = scanner.nextLine();
                String[] split = str.split("\\s");
                for (int j = 0; j < split.length; j++) {
                    data[i].add(split[j]);
                }
            }
    
            /**
             * 数据集处理
             */
            solve(data);
    
    
        }
    
        /**
         * 数据集处理
         * @param data
         */
        public static void solve(ArrayList<String>[] data) {
    
            getFrequent(data, 1);
        }
    
        /**
         * 获取到频繁1项集
         * @param data
         */
        public static void getFrequentOne(ArrayList<String>[] data) {
    
            /**
             * 获取不重复集合
             */
            for(ArrayList<String> list : data) {
                if(list == null) break;
                for(String s: list) {
                    Data dt = new Data();
                    List<String> ls = new ArrayList<>();
                    ls.add(s);
                    dt.setData((ArrayList<String>) ls);
                    int is_have = 0;
                    for(int i = 0; i < items.size(); i++) {
                        Data d = items.get(i);
                        if(d.getData().equals(ls)) {
                            is_have = 1;
                            break;
                        }
                    }
                    if(is_have == 0) {
                        items.add(dt);
                    }
                }
            }
        }
    
        /**
         * 输出候选n项集
         * @param n
         */
        public static void getCandidate(int n) {
    
            System.out.println("候选" + n + "项集为: ");
            outList();
        }
    
        /**
         * 输出频繁n项集
         * @param n
         */
        public static void getItems(int n) {
            for(int i = 0; i < items.size(); i++) {
                if((double)items.get(i).getCnt() / datacnt < minsupport) {
                    items.remove(i);
                    i--;
                }
            }
            System.out.println("频繁"+ n +"项集为: ");
            outList();
        }
    
        /**
         * 获取频繁n项集
         * @param data
         * @param n
         */
        public static void getFrequent(ArrayList<String>[] data, int n) {
    
            if(n == 1) {
                getFrequentOne(data);
            } else {
                ArrayList<Data> array = new ArrayList<>();
                for(int i = 0; i < items.size(); i++) {
                    Set<String> set = new HashSet<>();
                    ArrayList<String> data1 = items.get(i).getData();
                    for(int j = i+1; j < items.size(); j++) {
                        set.clear();
                        ArrayList<String> data2 = items.get(j).getData();
                        for(int u = 0; u < Math.max(data1.size(), data2.size()); u++) {
                            if(data1.size() > u) set.add(data1.get(u));
                            if(data2.size() > u) set.add(data2.get(u));
                        }
                        if(set == null || set.size() !=  n) continue;
                        put2Items(array,set);
                    }
                }
                items = (ArrayList<Data>) array.clone();
            }
    
            /**
             * 获取sup值
             */
            addSup(n);
    
            /**
             * 输出候选n项集
             */
            getCandidate(n);
            /**
             * 输出频繁n项集
             */
            getItems(n);
    
            if(items.size() > 1) {
                getFrequent(data, n+1);
            }
    
        }
    
        /**
         * 获取Sup值
         * @param n
         */
        public static void addSup(int n) {
            for(int i = 0; i < items.size(); i++) {
                ArrayList<String> list = items.get(i).getData();
                int cnt = 0;
                for(int j = 0; j < datacnt; j++) {
                    int have = 1;
                    ArrayList<String> cur = data[j];
                    for(int u = 0; u < list.size(); u++) {
                        if(!cur.contains(list.get(u))) {
                            have = 0;
                            break;
                        }
                    }
                    if(have == 1) cnt++;
                }
                Data d = new Data();
                d.setData(list);
                d.setCnt(cnt);
                items.set(i, d);
            }
        }
    
        /**
         * 整理候选频繁项集,同项相加
         * @param array,set
         */
        public static void put2Items(ArrayList<Data> array, Set<String> set) {
            Data data = new Data();
            for(String s:set) {
                data.getData().add(s);
            }
            int is_have = 0;
            for(int i = 0; i < array.size(); i++) {
                if(array.get(i) == null) break;
                if(array.get(i).equals(data)) {
                    is_have = 1;
                    array.set(i, data);
                    break;
                }
            }
            if(is_have == 0) {
                array.add(data);
            }
        }
    
    
        /**
         * 输出项集
         */
        public static void outList() {
    
            for(Data data : items) {
                System.out.println(Arrays.toString(data.getData().toArray()) + "   " + data.getCnt());
            }
    
        }
    }
    
    
    展开全文
  • Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索迭代方法找出数据库中项集关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉那些没必要中间结果)组成。该算法中项集概念...


    Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉那些没必要的中间结果)组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数,称为项集的频率。如果某项集满足最小支持度,则称它为频繁项集

    • 频繁项集:找出频繁一起出现的物品集的集合
    • 支持度:一个项集的支持度被定义为数据集中包含该项集的记录所占的比例;
      支持度 = (包含物品A的记录数量) / (总的记录数量
      在这里插入图片描述
    • 置信度体现了一个数据出现后,另一个数据出现的概率,或者说数据的条件概率。
      在这里插入图片描述
      图片来源https://www.cnblogs.com/pinard/p/6293298.html

    关联规则基本思想

    1. 找出所有频繁项集:找出支持度大于最小支持度的项集,即频繁项集
    2. 由频繁项集产生关联规则:这些规则必须满足最小支持度和最小可信度
    3. 算法核心思想
      频繁项集的非空子集一定也是频繁的

    算法基本过程

    • 算法命名源于算法使用了频繁项集性质的先验知识
    • 算法的基本过程:
      1. 生成候选集:找出候选集,即有可能成为频繁集的项集
      2. 生成频繁项集:生成通过数据库扫描筛选出满足条件的候选集形成又一层频繁集
        (频繁项集的子集也一定是频繁项集)例如:如果{A,B}是频繁集,则{A}{B}也一定是频繁集
      3. 生成关联规则:用得到的频繁集生成强关联规则。
    • Apriori算法中候选集生成步骤:
      1. 自连接Lk-1
        在这里插入图片描述
      2. 修剪
        . 在这里插入图片描述

    算法总结

    Aprior算法是一个很经典的频繁项集的挖掘算法,很多算法都是基于Aprior算法而产生的,包括FP-Tree,GSP, CBA等。这些算法利用了Aprior算法的思想,但是对算法做了改进,数据挖掘效率更好一些,因此现在一般很少直接用Aprior算法来挖掘数据了,但是理解Aprior算法是理解其它Aprior类算法的前提,同时算法本身也不复杂,因此值得好好研究一番。

    展开全文
  • 关联规则算法(Apriori/Fp-growth)在Python上实现

    万次阅读 多人点赞 2018-06-27 10:36:49
    可从数据库中关联分析出形如“由于某些事件发生而引起另外一些事件发生”之类的规则。如“67%顾客在购买啤酒同时也会购买尿布”,因此通过合理啤酒和尿布货架摆放或捆绑销售可提高超市服务质量和效益...
  • 面包 [支持度:3%,置信...关联规则是有趣的,如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。我们先来认识几个相关的定义:定义1: 支持度(support)支持度s是事务数据库D中包含A U ...
  • 关联规则 Apriori算法

    2020-05-14 23:16:44
    非常简单的关联规则的基础算法,Apriori算法的python实现 判断可连接性的规则: 先判断两个频繁k?1k?1项集是否是可连接的,可连接的定义是这样:对于两个频繁k?1k?1项集l1,l2l1,l2,先将项集中的项排序(比如字典...
  • 关联规则之Apriori算法

    2020-06-08 21:33:09
    我们可以定义一个关联规则: 其中,X,Y分别表示两个互斥事件,Y称为前因,X称为后果,上述的关联规则表示Y会导致X。但是我们又怎么评判这两个事件之间关系强弱呢?我们能够通过频繁项集评估标准来进一步分析...
  • 一种新动态关联规则及其挖掘算法研究,沈斌,姚敏,在分析原有动态关联规则不足基础上,本文提出了一种新动态关联规则,该定义支持度向量 、置信度向量 与经典定义相吻合,�
  • 关联规则--Apriori算法部分讨论关联模式概念都强调同时出现关系,而忽略数据中序列信息(时间/空间):时间序列:顾客购买产品X,很可能在一段时间内购买产品Y;空间序列:在某个点发现了现象A,很可能在下一个点...
  • 关联规则的强度用支持度(support)和自信度(confidence)来描述,关联规则是否可用,使用提升度(Lift)来描述。 挖掘定义 给定一个数据集,找出其中所有支持度support>=min_support,自信度confidence>=min_...
  • 定义何谓频繁模式挖掘呢?所谓频繁模式指是在样本数据集中频繁出现模式。举个例子,比如在超市交易系统中,记载了很多次交易,每一次交易信息包括用户购买商品清单。如果超市主管是个有心人话,他会发现...
  • 定义一:设I={i1,i2,…,im},是m个不同项目集合,每个ik称为一个项目。项目集合I称为项集。其元素个数称为项集长度,长度为k项集称为k-项集。引例中每个商品就是一个项目,项集为I={bread, beer, cake,...
  • 质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并...
  • 关联规则apriori算法的python实现

    万次阅读 2015-06-16 16:09:14
    学了两天python,想实践下,正好最近在学习数据挖掘,先用python实现下 注:由于后面加了注释,由于编码问题,可能即使是注释,有环境也不支持汉字编码,...定义全局变量k,即支持度计数k,此k也可以在运行程序之前
  • 关联规则挖掘目标是发现数据项集之间关联关系或相关关系。 2.关联规则的基本概念 定义1:项与项集 项:数据库中不可分割最小单位信息,用i表示,如商品中尿布、啤酒等。 项集:项集合,用下式表示 I...
  • 关联规则FpGrowth算法 Java实现

    千次阅读 2017-09-05 12:58:27
    关联规则算法有Apriori和FpGrowth,与Apriori相比,FpGrowth扫描数据库次数更少,效率大大提高,FpGrowth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成...
  • #寻找关联规则的函数 def find_rule(d, support, confidence, ms = u'--'): result = pd.DataFrame(index=['support', 'confidence']) #定义输出结果 support_series = 1.0*d.sum()/len(d) #支持度序列 ...
  • 数据记录所有项集合称为总项集,上表中总项集:S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}关联规则就是有关联规则,形式是这样定义的:两个不相交非空集合X、Y,如果有X->Y,就说X-->Y是一条关联规...
  • 在数据挖掘的知识模式中,关联规则模式是比较重要的一种...一、关联规则的定义和属性   考察一些涉及许多物品的事务:事务1 中出现了物品甲,事务2 中出现了物品乙,事务3 中则同时出现了物品甲和乙。那么,物品甲和
  • 关联规则就是形如A->B的表达式,A和B是整个项集中互不相交的两个子项。...支持度、置信度、提升度的定义: 支持度(A->B)=|AB|/|S| 置信度(A->B)=|AB|/|A| 提升度(A->B)=置信度(A->B)/P(B) ...
  • 数据挖掘算法基础-关联规则

    千次阅读 2015-11-11 10:40:17
    常被用于交易数据、关系数据分析,发现数据集中隐藏频繁模式,这些频繁模式可以用关联规则的形式表示,有效的关联规则对商家商品进出货摆放都有很大指导意义。 设 是项集合,数据集D是事务集合,每项...
  • 关联规则采掘是数据采掘...小,将关联规则分为正关联规则、 无效关联规则、 负关联规则,提出了新衡量标准采掘关联规则的算法, 并用 Visual FoxPr o 进行了试验。实验表明,新方法能明显减少无效关联规则的数目。</p>
  • 关联规则挖掘目标是发现数据项集之间关联关系或相关关系,是数据挖掘中一个重要课题。 关联规则挖掘一个典型例子是购物篮分析,关联规则挖掘有助于发现交易数据库中不同商品项之间关系,找出顾客购买...
  • 一个事务数据库中的关联规则挖掘可以描述如下:设 I = { i1,2,i3...,im}是一个项目集合 ,事务数据库D ={t1,t2,...tn}是由一系列具有唯一标识TID事务组成。每一个事务ti(i =1,2,...,n)都对应I上一个子集。 2. ...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 271
精华内容 108
关键字:

关联规则算法的定义