精华内容
下载资源
问答
  • 关联规则算法的介绍,希望对大家有帮助,其中详细介绍了关联规则的定义和使用,并且列举了多个实例来进行说明和讲解
  • 关联规则算法

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

    关联规则

    关联规则是形如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]

    展开全文
  • apriori和关联规则算法

    千次阅读 2016-02-21 10:32:48
    从大规模数据集中寻找物品间的隐含关系被称为关联规则分析(association analysis)或关联规则学习(association rule learning)。举个例子说就是发现用户购买了一件商品(如帽子)后,会购买另一件商品(如围巾)...
    问题的背景: 
    
        超市的会员卡记录了大量的用户购买数据,通过分析这些数据可以帮助商店分析用户的购买行为。从大规模数据集中寻找物品间的隐含关系被称为关联规则分析(association analysis)或关联规则学习(association rule learning)。举个例子说就是发现用户购买了一件商品(如帽子)后,会购买另一件商品(如围巾)的概率。关联规则分析需要从大规模的商品数据中,发现和统计各种商品的组合(频繁项集发现)是一个非常费时费力的事情,这个也是关联规则分析的主要问题。为了解决这个问题提出了apriori算法,也叫先验算法。
        1993年,R.Agrawal等人首次提出了挖掘顾客交易数据中项目集间的关联规则问题,其核心是基于两阶段频繁集思想的递推算法。该关联规则在分类上属于单维、单层及布尔关联规则,典型的算法是Aprior算法。
      Aprior算法将发现关联规则的过程分为两个步骤:第一步通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;第二步利用频繁项集构造出满足用户最小信任度的规则。其中,挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。

    问题定义:
        关联规则分析是为了在大规模数据集中寻找有趣关系的任务。这些关系分为两种,频繁项集和关联规则。
        频繁项集(frequent item sets)是经常出现在一块的物品的集合,关联规则(association rules)暗示两种物品之间可能存在很强的关系。
        apriori算法就是为了发现频繁项集。频繁项集发现后再进行关联规则分析,需要用到条件概型。

        需要思考的问题:
            1、频繁项集,频繁如何定义,也就是说怎样才算频繁?
            2、应该如何去定义商品间的购买关系,也就是凭什么说他们存在某个关系?
            3、如何去过滤掉一些不需要的商品关系,筛选出想要的商品关系?
            第一个问题会在讲apriori算法原理的时候解决。
            第二个问题需要用到条件概型

            ,其中P(AB)是A商品和B商品同时出现的概率,P(B)是B商品出现的概率,P(A|B)是在B商品出现的情况下出现A商品的概率。在关联规则分析中,我们将P(AB)称为A和B同时出现的的 支持度,P(B)称为B出现的支持度。P(A|B)指定是购买B再购买A的 可信度
            

        apriori原理:
            如下图对于{0,1,2,3}的组合如下共有15种,即2的N次方减1种,其中N为商品种数。因此计算所有组合的次数时间复杂度是很大的。

            如何降低复杂度呢?
            研究人员发现了一种所谓的Apriori原理,如果某个项集是频繁的,那么它的所有子集也是频繁的。逆否命题是,如果某个项集不是频繁的,那么包含这个项集的项集也不是频繁的。这个原理可作为减枝的依据,例如{0}不是频繁的,那么包含0的所有项集都不是频繁的,包含0的项集出现次数就不用统计了。
            第一个问题的解决方法:
            频繁项集的频繁是自定义的,根据实验场景定义一个次数,低于这个次数的项集就可以减枝减掉。

    算法图例说明     

              为了便于计算, 下面的支持度用项集出现次数来代替。

    假设有一个数据库D,其中有4个事务记录,分别表示为:

    TIDItems
    T1I1,I3,I4
    T2I2,I3,I5
    T3I1,I2,I3,I5
    T4I2,I5

    这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程:

    TIDItems
    T1I1,I3,I4
    T2I2,I3,I5
    T3I1,I2,I3,I5
    T4I2,I5

    扫描D,对每个候选项进行支持度计数得到表C1:

    项集支持度计数
    {I1}2
    {I2}3
    {I3}3
    {I4}1
    {I5}3

    比较候选项支持度计数与最小支持度minSupport,产生1维最大项目集L1:

    项集支持度计数
    {I1}2
    {I2}3
    {I3}3
    {I5}3

    由L1产生候选项集C2:

    项集
    {I1,I2}
    {I1,I3}
    {I1,I5}
    {I2,I3}
    {I2,I5}
    {I3,I5}

    扫描D,对每个候选项集进行支持度计数:

    项集支持度计数
    {I1,I2}1
    {I1,I3}2
    {I1,I5}1
    {I2,I3}2
    {I2,I5}3
    {I3,I5}2

    比较候选项支持度计数与最小支持度minSupport,产生2维最大项目集L2:

    项集支持度计数
    {I1,I3}2
    {I2,I3}2
    {I2,I5}3
    {I3,I5}2

    由L2产生候选项集C3:

    项集
    {I2,I3,I5}

    扫描D,对每个候选项集进行支持度计数:

    项集支持度计数
    {I2,I3,I5}2

    比较候选项支持度计数与最小支持度minSupport,产生3维最大项目集L3:

    项集支持度计数
    {I2,I3,I5}2

    算法终止。



    从频繁项中挖掘关联规则:


    关联规则挖掘也可以进行减枝,例如012->3,可信度可用如下公式计算为,


    对于以012->3为根节点的所有节点,例如03->12,可信度可用如下公式计算为

    观察发现分子是一样的,分母由于子节点是父节点的子集,所以对应的概率更大,上面的例子P(12) >= P(012)。

    所以可以得出如果某条规则不满足最小可信度,那么该规则的所有子集也不会满足最小可信度要求。


    在ipython和python3.4环境下进行的实验,代码如下:

    例子数据

    def loadDataSet():
        return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    def loadDataSet2():
        return [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]


    """
    创建集合大小为1的项集
    """
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
                    
        C1.sort()
        return map(frozenset, C1)#use frozen set so we
                                #can use it as a key in a dict  
    """
    计算指定项集的支持度
    D是数据集合,Ck是要求支持度的项集,minSupport是最小支持度
    """
    def scanD(D, Ck, minSupport):
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):
                    if not ssCnt.get(can): ssCnt[can]=1
                    else: ssCnt[can] += 1
        numItems = float(len(D))
        retList = []
        supportData = {}
        for key in ssCnt:
            support = ssCnt[key]/numItems
            if support >= minSupport:
                retList.insert(0,key)
            supportData[key] = support
        return retList, supportData
    """
    生成集合大小比原来的大一的项集
    """
    def aprioriGen(Lk, k): #creates Ck
        retList = []
        lenLk = len(Lk)
        # 如果Lk只有一项,则retList为[]
        for i in range(lenLk):
            for j in range(i+1, lenLk):
                # 为了每次添加的都是单个项构成的集合,所以Lk中项的大小是k-1,那么前k-2项相同,才能使合并后只比原来多一项。
                L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
                L1.sort(); L2.sort()
                if L1==L2: #if first k-2 elements are equal
                    retList.append(Lk[i] | Lk[j]) #set union
        return retList
    """
    求出数据集合中,支持度大于最小支持度的所有项集
    """
    def apriori(dataSet, minSupport = 0.5):
        C1 = createC1(dataSet)
        # 转化为list类型重要
        C1 = list(C1)
        D = map(set, dataSet)
        # 转化为list类型重要
        D = list(D)
    #     print(D)
    #     print(C1)
        L1, supportData = scanD(D, C1, minSupport)
    #     print(L1)
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0):
            Ck = aprioriGen(L[k-2], k)
            Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk
            supportData.update(supK)
            L.append(Lk)
            k += 1
        return L, supportData
    """
    计算 freqSet-conseq -> conseq 的可信度, conseq是H中的元素
    """
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):
        prunedH = [] #create new list to return
        for conseq in H:
            conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence
            if conf >= minConf: 
                print(freqSet-conseq,'-->',conseq,'conf:',conf)
                brl.append((freqSet-conseq, conseq, conf))
                prunedH.append(conseq)
        return prunedH
    """
    # 1个元素的集合 -> (len(freqSet) - 1) 元素的集合
    # 2个元素的集合 -> (len(freqSet) - 2) 元素的集合
    # ...
    """
    def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
        print("H:", H)
        m = len(H[0])
        if (len(freqSet) > (m + 1)): #try further merging
            Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates
    #         print("Hmp1:",Hmp1)
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
    #         print("Hmp1:",Hmp1)
            if (len(Hmp1) > 1):    #need at least two sets to merge
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    """
    两个元素的集合求关联规则
    三个元素的集合求关联规则
    ...
    """
    def generateRules(L, supportData, minConf=0.7):  #supportData is a dict coming from scanD
        bigRuleList = []
        for i in range(1, len(L)):#only get the sets with two or more items
            print(L[i])
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                print(H1)
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList  



    进行apriori算法项集为1的测试,如果可行再应用到递推中

    # 加载数据
    dataSet=loadDataSet()
    dataSet

    # 获取集合大小为1的所有项集
    C1=createC1(dataSet)
    # print(len(C1))
    # TypeError: object of type 'map' has no len()
    C1 = list(C1)
    C1

    # 将数据类型转换为集合
    D=map(set, dataSet)
    # print(len(D))
    D = list(D)
    D

    # 求集合大小为1的项集的支持度,返回留下支持度大于最小支持度的项集和它们的支持度
    L1, suppData0 = scanD(D, C1, 0.5)
    print(L1)
    print(suppData0)

    测试priori算法
    L1, suppData0 = apriori(dataSet)
    print(L1)
    print()
    print(suppData0)

    L1, suppData0 = apriori(dataSet, minSupport=0.7)
    print(L1)
    print()
    print(suppData0)

    测试关联规则

    L, suppData = apriori(dataSet, minSupport=0.5)
    print(L)
    print()
    print(suppData)

    rules = generateRules(L, suppData, minConf=0.7)

    rules = generateRules(L, suppData, minConf=0.5)
    rules

    缺点:
    每次增加频繁项集的大小,Apriori算法都会重新扫描整个数据集合。


    当数据集很大时,这会显著降低频繁项集的发现速度。



    参考自:
    《机器学习实战》






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

    千次阅读 2018-01-27 18:12:55
    它的模式属于描述型模式,发现关联规则算法属于无监督学习的方法。其实是一种事物相关性的探究。 百度百科: 通过对比支持度,进行剪枝,将支持度高的分支留下,继续探寻关联,直到再没有高于最小支持度为止。...

    关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。它的模式属于描述型模式,发现关联规则的算法属于无监督学习的方法。其实是一种事物相关性的探究。

    百度百科:

    这里写图片描述

    通过对比支持度,进行剪枝,将支持度高的分支留下,继续探寻关联,直到再没有高于最小支持度为止。
    应用场景比较广泛,购物篮数据,医疗诊断,科学数据分析。
    首先数据方面,要把数据转换为0,1 的形式,1代表有,0代表无,每一项集的中元素相乘结果为1,则证明有该项集有结果,在通过求和后求占比,即是该项集支持度。

    再通过置信度检验是否为强规则。

    实现代码:

    def find_rule(data, support, confidence):
        result = pd.DataFrame(index=['support', 'confidence'])  # 定义输出结果
    
        support_series = round(1.0 * data.sum() / len(data), 6)  # 支持度序列
        column = list(support_series[support_series > support].index)  # 初步根据支持度筛选
        k = 0
        while len(column) > 1:
            k += 1
            print("正在搜索{}元项集".format(k))
            column = connect_string(column)
            # 通过相乘得1 确认项集结果
            sf = lambda i: data[i].prod(axis=1, numeric_only=True)  # 新一批支持度的计算函数
            # 用map函数分布式求解,加快运算速度
            data_new = pd.DataFrame(list(map(sf, column)), index=['-'.join(i) for i in column]).T
            # 计算占比(支持度)
            support_series_new = round(data_new[['-'.join(i) for i in column]].sum() / len(data),6)
            # 通过支持度剪枝
            column = list(support_series_new[support_series_new > support].index)
            support_series = support_series.append(support_series_new)
            column_new = []
    
            for i in column:
                i = i.split('-')
                for j in range(len(i)):
                    column_new.append(i[:j] + i[j + 1:] + i[j:j+1])
            # 先行定义置信度序列,节约计算时间
            cofidence_series = pd.Series(index=['-'.join(i) for i in column_new])
    
            for i in column_new:  # 计算置信度序列
                cofidence_series['-'.join(i)] = support_series['-'.join(sorted(i))] / support_series['-'.join(i[:len(i) - 1])]
    
            for i in cofidence_series[cofidence_series > confidence].index:  # 置信度筛选
                result[i] = 0.0
                result[i]['confidence'] = cofidence_series[i]
                result[i]['support'] = support_series['-'.join(sorted(i.split('-')))]
        return result.T
    
    def trans_index(x):
        rename = []
        for item in x.split('-'):
            rename.append(origin_columns[int(item)])
        return "-".join(rename)
    
    if __name__ == '__main__':
        inputfile = 'data/Income.csv'
        outputfile = 'tmp/income.csv'
        data = pd.read_csv(inputfile)
        del data['Unnamed: 0']
        # 保存原列标
        origin_columns = list(data.columns)
        # 替换列标
        data.columns = np.arange(0, len(origin_columns)).astype(str)
        # 设置最小支持度
        support = 0.3
        # 设置最小置信度
        confidence = 0.5 
        result = find_rule(data, support, confidence).reset_index()
        # 将关系名称换回原来的
        result['index'] = result['index'].apply(trans_index)
        result = result.set_index('index')
        print("*"*20, "结果", "*"*20)
        print(result)
        result.to_csv(outputfile)

    结果也可以写成键值对的形式存入redis 数据库,方便搜索调用。

    展开全文
  • 一句话 关联分析(关联规则学习): 从大规模数据集中寻找物品间的隐含关系被称作 关联...在关联规则Aprioir算法中,有两个很重要的概念,分别是频繁项集(frequent item sets),关联规则(associational rules)...

    一句话

    关联分析(关联规则学习): 从大规模数据集中寻找物品间的隐含关系被称作 关联分析(associati analysis) 或者 关联规则学习(association rule learning)

    一张图

    这里写图片描述

    解释一下这张图:
    在关联规则Aprioir算法中,有两个很重要的概念,分别是频繁项集(frequent item sets),关联规则(associational rules),它们是用来描述隐含关系的形式。

    频繁项集(frequent item sets): 经常出现在一块的物品的集合。
    关联规则(associational rules): 暗示两种物品之间可能存在很强的关系。

    那么 频繁 的定义是什么呢?怎么样才算频繁呢? 度量它们的方法有很多种,这里我们来简单的介绍下支持度和可信度。

    支持度: 数据集中包含该项集的记录所占的比例。例如上图中,{豆奶} 的支持度为 4/5。{豆奶, 尿布} 的支持度为 3/5。
    可信度: 针对一条诸如 {尿布} -> {葡萄酒} 这样具体的关联规则来定义的。这条规则的 可信度 被定义为 支持度({尿布, 葡萄酒})/支持度({尿布}),从图中可以看出 支持度({尿布, 葡萄酒}) = 3/5,支持度({尿布}) = 4/5,所以 {尿布} -> {葡萄酒} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。

    举个栗子呗

    还是上面的那个尿布和葡萄酒的栗子,让我们仔细的看一下它的关联规则的发现过程(Aprioir)

    过程1:寻找k项频繁集

    这里写图片描述
    我们规定最小支持度为0.3
    L1为1项频繁集,可以从图中看出它的计算过程为:

    P()= P ( 豆 奶 ) = 豆 奶 出 现 的 次 数 订 单 总 数 量

    L2为2项频繁集,从L1中选择候选者(去除了小于最小支持度的数据),计算过程为:
    P()= P ( 豆 奶 , 莴 苣 ) = 豆 奶 , 莴 苣 共 同 出 现 的 次 数 订 单 总 数 量

    同理可以推出L3

    过程2:发现关联规则

    这里写图片描述
    这里举一个例子说明,买了尿布的人也会继续买葡萄酒的规则,支持度为0.6(前面已经算出),那么它的置信度计算过程为:

    P(尿>)=尿尿=P(|尿) P ( 尿 布 − − > 葡 萄 酒 ) = 尿 布 , 葡 萄 酒 同 时 出 现 的 概 率 尿 布 出 现 的 概 率 = P ( 葡 萄 酒 | 尿 布 )

    以上就是Aprioir关联规则算法的整体思路啦!!!

    展开全文
  • 关联规则常用算法

    千次阅读 2020-07-03 15:53:41
    关联规则常用算法   关联规则(Association Rules)是海量数据挖掘(Mining Massive Datasets,MMDs)非常经典的任务,其主要目标是试图从一系列事务集中挖掘出频繁项以及对应的关联规则关联规则来自于一个...
  • 数据挖掘笔记(5)-关联规则算法Apriori

    千次阅读 2019-01-22 11:12:10
    2、关联规则算法Apriori Apriori是最常用也是最经典的挖掘频繁项集的算法,其核心思想是通过连接产生候选项及其支持度,然后通过剪枝生成频繁项集。 (1)项集 项集是项的集合,包含k个项的就是k项集,如{牛奶,面...
  • 算法工程可以在下载:(只是单机版的实现,并没有MapReduce的代码)使用FP关联规则算法计算置信度基于下面的思路:1. 首先使用原始的FP树关联规则挖掘出所有的频繁项集及其支持度;这里需要注意,这里是输出所有的...
  • 文章目录关联规则基本思想算法基本过程算法总结 Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉...
  • 提到关联规则算法,一般会想到Apriori或者FP,一般很少有想到HotSpot的,这个算法不知道是应用少还是我查资料的手段太low了,在网上只找到很少的内容,这篇...比较好用的算法类软件,如weka,其里面已经包
  • R语言学习之关联规则算法

    千次阅读 2016-08-08 18:06:16
    R语言学习之关联规则算法  卡卡 2014-03-05 10:42:03 library(arules) #加载arules程序包 data(Groceries) #调用数据文件 frequentsets=eclat(Groceries,parameter=list(support=0.05,maxlen=10)) #求...
  • 前篇《HotSpot关联规则算法(1)-- 挖掘离散型数据》分析了离散型数据的HotSpot关联规则,本篇分析离散型和连续型数据的HotSpot关联规则挖掘。1. 首先看下数据格式(txt文档):@attribute outlook {sunny, overcast...
  • 关联规则挖掘算法

    千次阅读 2018-08-31 20:06:08
    关联规则挖掘是一种基于规则的机器学习算法,该算法可以在大数据库中发现感兴趣的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现,而非预测,所以是属于无监督的...
  • Hadoop实现关联规则算法--二项集挖掘

    千次阅读 2012-11-08 10:20:15
    近期看mahout的关联规则源码,颇为头痛,本来打算写一个系列分析关联规则的源码的,但是后面看到有点乱了,可能是稍微有点复杂吧,所以就打算先实现最简单的二项集关联规则算法的思想还是参考上次的图片: 这里...
  • 关联规则算法-Aprior

    万次阅读 2017-04-17 09:41:52
    数据挖掘是一个比较庞大的领域,它包括数据预处理(清洗去噪)、数据仓库、分类聚类、关联分析等。关联分析可以算是数据挖掘最贴近我们生活的一部分了,打开卓越亚马逊,当挑选一本《Android4高级编程》时,它会...
  • 关联规则算法   数据挖掘是指以某种方式分析数据源,从中发现一些潜在的有用的信息,其中关联规则挖掘是数据挖掘中的一个重要课题,它是从数据背后发现事物之间可能存在的关联或者联系。比如经调查发现30%的顾客会...
  • 关联规则Apriori算法

    千次阅读 2020-10-20 09:13:30
    参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联...关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成,分别是 频繁项集(frequ.
  • 关联规则算法之FP growth算法

    千次阅读 2014-02-19 19:25:01
    FP Growth算法利用了巧妙的数据结构,大大降低了Aproir挖掘算法的代价,他不需要不断得生成候选项目队列和不断得扫描整个数据库进行比对。为了达到这样的效果,它采用了一种简洁的数据结构,叫做frequent-pattern ...
  • 关联规则(Association Rules) 两个不相交的非空集合X、Y,如果有X->Y,就说X->Y是一条关联规则关联规则的强度用支持度(support)和自信度(confidence)来描述,关联规则是否可用,使用提升度(Lift)来描述。 挖掘...
  • 关联规则算法(Apriori/Fp-growth)在Python上的实现

    万次阅读 多人点赞 2018-06-27 10:36:49
    可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。如“67%的顾客在购买啤酒的同时也会购买尿布”,因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益...
  • 针对模糊关联规则挖掘时隶属函数的确定困难以及区间划分边界过硬等问题,提出了模糊...在这些权值的基础上定义了模糊关系支持度和置信度,阐述了算法的详细步骤,最后给出了算法在服务信任领域挖掘关联规则的应用过程。
  • 为了提高个性化推荐效率和推荐质量,平衡冷门与热门数据推荐权重,对关联规则的Apriori算法频繁项集挖掘问题进行了重新评估和分析,定义了新的测评指标推荐非空率以及k前项频繁项集关联规则的概念,设计了基于 k 前...
  • Mahout关联规则算法源码分析(2)

    千次阅读 2013-02-07 15:44:46
    接着看同名函数,其定义如下: private Map,FrequentPatternMaxHeap> generateTopKFrequentPatterns( Iterator[],Long>> transactions, long[] attributeFrequency, long minSupport, int k, int ...
  • 关联规则算法(The Apriori algorithm)

    千次阅读 2019-07-27 15:30:15
    关联规则的目的在于在一个数据集中找出项之间的关系,也称之为购物篮分析 (market basket analysis)。例如,购买鞋的顾客,有10%的可能也会买袜子,60%的买面包的顾客,也会买牛奶。这其中最有名的例子就是"尿布和...
  • 最近在工作中遇到一个问题:需要求几千个商品类目之间的相关性,自然而然相当了关联规则算法。 由于商品类目只有几千个,所以起初并没有考虑性能问题,所以就自己实现了一个mapreduce版的Priori算法,结果用到实际...
  • 关联规则Apriori算法实例

    千次阅读 2019-10-18 11:02:55
    Apriori算法关联规则计算结果Apriori算法 关联规则 以下数据使用关联规则计算 import pandas as pd #import Apriori from apriori import * inputfile ='../menu_orders.xls' outputfile = 'tmp/apriori_rules.xls...
  • 关联规则算法Apriori的学习与实现

    千次阅读 2014-04-24 20:14:21
    关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系,根据所挖掘的关联关系,可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶 ⇒...
  • 关联规则DHP算法详解

    千次阅读 2016-09-29 17:05:38
    参考文献: [1]Park, J. S., Chen, M. S., & Yu, P. S. (1995). An effective hash-based algorithm for mining association rules.... Sigmod Record, 24(2), 175-... 关联规则dhp算法的研究与分析. 佛山科学技术学院学

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 98,670
精华内容 39,468
关键字:

关联规则算法的定义