精华内容
下载资源
问答
  • 关联规则—Apriori算法—FPTree

    万次阅读 多人点赞 2018-07-19 13:58:56
    1 关联规则 2 频繁项集(Frequent Itemset) 3 关联规则Association Rule 4 关联规则评估指标 5 关联规则挖掘方法: 6 关联规则 Apriori ...▶ 关联规则应用方向: ▶ 基于support,confidence和lift 筛选规则 ...

    一、关联规则

    1.1 概念
    啤酒与尿布的故事

    关联规律挖掘:从交易数据中发现:买了X 还会买Y 的规则
    关联规律挖掘‘购物篮分析’Market Basket Analysis(MBA)
    关联规律->应用于推荐系统

    基本概念:

    通过数据的关联性进行分析挖掘,适合用于大数据样本中。
    项集:包含0个或多个项的集合。包含k个项就是一个k项集

    事务:表示事件

    (比如每次去商场购买东西是一次事务,而实际购买到的东西就是项集)

    关联规则的三个计算:

    支持度 support
    置信度 confidence
    提升度 lift

    支持度(support):

    全部事务中,项集中{X,Y}同时出现的概率:
    support(X=>Y)=σ(XUY)Nsupport(X=>Y)=\frac{\sigma(X U Y)}{N}
    该指标作为建立强关联规则的第一个门槛,通过最小阈值(minsup)的设定,来剔除那些 “出镜率” 较低的无意义的规则.

    而相应地保留下出现较为频繁的项集所隐含的规则。即筛选出满足:
    support(Z)>=minSupsupport(Z) >= minSup
    项集Z,被称为频繁项集(Frequent Itemset)。

    置信度(confidence):

    在关联规则的先决条件 X 发生的条件下,关联结果Y发生的概率,
    即含有X的项集条件下,同时含有Y的可能性:
    confidence(X=>Y)=σ(XUY)σ(X)confidence(X=>Y) = \frac{\sigma(X U Y)}{\sigma(X)}

    在这里,也要对置信度设置 最小阈值(mincon) 来进一步筛选满足需要的强关联规则。因此,继产生频繁项集后,需从中进而选取满足:
    confidence(X=>Y)minconconfidence(X=>Y) \geq mincon

    提升度(lift):

    表示在含有 X 的条件下同时含有 Y 的可能性与无条件下含有Y的可能性之比。
    即在Y的自身出现的可能性P(Y)的基础上,X的出现对于Y的“出镜率” P(Y/X)的提升程度:
    lift(X=>Y)=P(YX)P(Y)==confidence(X=>Y)P(Y)lift(X=>Y) = \frac{P(Y|X)}{P(Y) } == \frac{confidence (X=>Y)}{P(Y)}
    该指标与confidence同样用来衡量规则的可靠性,可以看作置信度的一种互补指标。

    lift >1 X-y 正相关
    lift <1 X-y 负相关
    lift =1 X-y 无相关

    Support较大的规则lift值会倾向于比较小
    往往lift值特别大的规则,support会非常小

    1.2 示例
    TID 面包 牛奶 尿布 啤酒 鸡蛋 可乐
    1 1 1 0 0 0 0
    2 1 0 1 1 1 0
    3 0 1 1 1 0 1
    4 1 1 1 1 0 0
    5 1 1 1 0 0 1

    考虑规则{牛奶,尿布}->{啤酒}。
    由于项集{牛奶,尿布,啤酒}支持度计数2。事务总数5(购买5次)
    所以支持度:2/5=0.4

    由于项集{牛奶,尿布,啤酒}支持度计数2。项集{牛奶,尿布}支持度计数为3 所以该置信度:2/3=0.67
    这里写图片描述

    二、关联规则挖掘推论(Apriori 算法)

    这里写图片描述
    这里写图片描述

    2.1 关联规则挖掘方法:
    分两步走:

    频繁项集(Frequent Itemset)的生成:生成所有supoort>= minsup的项集合

    关联规则的生成:对每一个频繁项集(XY)进行二元划分,生成confidence最高的一系列规则(X->Y)

    Apriori 算法思想:(购买A、B、C频繁则分别购买AB、BC、AC、ABC肯定频繁)

    频繁项集的子集也是频繁项集

    优点:使用先验性质,大大提高了频繁项集产生的效率;算法简单易理解,容易实施

    缺点:候选频繁K项集数量巨大;需要对整个数据库进行扫描,非常耗时;数据集存放内存中,大数据处理有困难
    这里写图片描述

    关联规则应用方向:

    交叉销售:向买A的用户推荐B

    捆绑销售:把A和B打包销售

    基于support,confidence和lift 筛选规则

    这里写图片描述

    2.3 FP-growth

    每次由(k-1)项集L(K-1)产生K项集L(K)时,自连接产生采用枚举的方式,而且产生的项集每次都得去扫描一下数据库

    如何提高Apriori算法的效率,有比较多的方法:基于散列,抽样等方式,比较出名的改进算法有FPGrowth算法。

    经典的关联规则挖掘算法包括Apriori算法和FP-growth算法。

    apriori算法多次扫描交易数据库,每次利用候选频繁集产生频繁集;

    FP-growth则利用树形结构,无需产生候选频繁集而是直接得到频繁集,大大减少扫描交易数据库的次数,从而提高了算法的效率。
    但是apriori的算法扩展性较好,可以用于并行计算等领域。

    使用Apriori算法进行关联分析。FP-growth算法来高效发现频繁项集。
    sklearn 没有关联规则算法,寻求GitHub
    https://github.com/asaini/Apriori
    Python Implementation of Apriori Algorithm

    三、FP-growth原理

    3.1 生成项头表

    原始数据中共有10个事务。
    首先根据原始数据并对1项集计数,我们发现F,O,I,L,J,P,M, N都只出现一次,支持度为1,低于2的阈值(此处假设我们设定一个阈值为2)。
    去除后将剩下的A, C, E, G, B, D, F按照出现次数(即支持度)的大小降序排列,组成了项头表。 (一般使用降序排序)
    这里写图片描述

    3.2 生成FP tree以及节点链表

    原始数据得到初步的整理后,开始生成FP tree以及节点链表。
    首先把根节点设为null,也就是说根节点不包含任何项。这样做的好处是,任何一个事务都可以被视为是从一个空项开始的。
    这里写图片描述
    这里写图片描述

    3.3 挖掘过程

    首先挖掘频率低的项,然后逐次挖掘频率高的项。

    首先挖掘频率最低的项F,因为其子树恰好较为简单,所以可以很容易地得到其条件模式基。
    条件模式基(conditional pattern base):条件模式基是以所查找项为结尾的路径集合。每一条路径其实都是一条前缀路径。
    简而言之,一条前缀路径是介于所查找元素项与树根节点之间的所有内容。
    对于一颗conditional FP-tree(条件FP树),可以进行递归的挖掘(合并分支等)。
    这里写图片描述
    F挖掘完了,我们开始挖掘项D。
    D比F复杂一些,因为其节点链表含有两个叶子节点。因此首先得到一颗conditional FP-tree 。
    我们接着将所有的祖先节点计数设置为叶子节点的计数,即变成{A:2, C:2, E:1, G:1, D:1, D:1}。此时E和G由于在条件模式基里面的计数低于阈值2,被我们删除,最终得到条件模式基为{A:2, C:2}。(如右上图)
    这里写图片描述

    展开全文
  • 海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之association rules关联规则频繁项集挖掘 {Frequent Itemsets: Often called "association

    http://blog.csdn.net/pipisorry/article/details/48894977

    海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之association rules关联规则与频繁项集挖掘

    {Frequent Itemsets: Often called "association rules," learn a number of techniques for finding items that appear unusually often together.  The classical story of "beer and diapers" (people who buy diapers in a supermarket are unusually likely to buy beer) is an example of this data-mining technique.}

    题外话: lz真的不建议看这个视频,当你看了这个视频后,你会发现,原本一个简单的问题可以通过很优雅的方式简单地解释清楚的时候,主讲人总是偏离方向,以一种相当繁琐隐晦的形式讲到另一个地方去,而让人一下子就可以明白的解释总是讲不出来,让人看不懂(说真的,那个比较老的主讲人讲解的是相当水),并且制作的ppt中的语句完全不是最好的,总是缺点什么,总要加一点注释在下面才能更好明白那是什么意思。所以关于频繁项集挖掘以及关联规则,lz建议看看《数据挖掘概念与技术》这本书中第六章 挖掘频繁模式、关联和相关性:基本概念与方法的内容,讲的相当清晰易懂)

    Frequent Itemsets频繁项集

    与相似性分析的区别:相似性分析,研究的对象是集合之间的相似性关系。而频繁项集分析,研究的集合间重复性高的元素子集。

    Market-Basket 模型及其应用

    Note: 一个item可以看成是买的一个东西,其集合就是项集。一个basket就是买的东西的集合,也是一个项集,但一般看作是多个项集的集合。

    频繁项集的应用:真实超市购物篮的分析,文档或网页的关联程序分析,文档的抄袭分析,生物标志物(疾病与某人生物生理信息的关系)

    应用一:人们会同时买什么


    Note:

    1. Run a sale on diapers; raise price of beer.是一种营销策略,但是反过来却不是。这就要分析频繁项集的原因。

    2. 当然这种营销策略只对实体店有效。超市购物篮的分析,主要是针对实体销售商,而不是在线零售商,这是因为实体销售可以找点频繁项集合后,可以采取对一种频繁项商品促销,而抬高相关的频繁项其他商品的价格来获利,因为客户一般不会去另外一家店购买其他的商品。而这种策略在在线销售时,会忽略“长尾”客户的需求。对于实体销售,商品的数量和空间资源有限,所以只能针对一些畅销商品进行关注和指定策略。而对于在线销售,没有资源限制,而且客户切换商户很方便,所以实体店销售的策略不合适在线销售,在线销售更应该关注相似客户群的分析,虽然他们的购买的产品不是最畅销、频繁的,但对客户群的偏好分析,可以很容易做到对每个客户进行定制化广告推荐,所以,相似性分析对在线销售更为重要。

    应用二:抄袭plagiarism检测


    Note: the basket corresponding to a sentence contains all the documents in which that sentence appears.
    应用三:词关联


    关联规则Association Rules、支持度与置信度

    Support支持度

     

    支持度: 包含频繁项集F的集合的数目。项集的支持度就是项集应该在所有basket中出现的数目。>=项集的支持度的项集都是频繁项集。

    Confidence置信度

      

    置信度:confidence(A=>B) = P(B|A) = support(A U B)/support(A) = support_count(A U B)/support_count(A),就是itemA存在时itemB也存在的条件概率,也是频繁项A与某项B的并集的支持度 与 频繁项集A的支持度的比值。


    寻找关联规则和频繁项集

    关联规则挖掘两个步骤

    1. 寻找所有频繁项集(满足最小支持度的项集)

    2. 由频繁项集产生关联规则(满足最小支持度和最小可信度的项集)

    Note: 确定频繁项集,{i}只需要support,而{i,j}则需要support*confidence.

    Note:

    1. 这种寻找关联规则的方法步骤是:先找到支持度>=cs的,然后去掉其中一个item j,找到支持度>=s的,这样去掉j后的项集{i}->j的置信度>=c,{i}->j就是一个关联规则。

    2. 这种解释完全没有《数据挖掘概念与技术》中的解释清晰明了。

    频繁项集的计算模型


    算法瓶颈


    寻找频繁二项集的算法

    Naive Algorithm朴素算法

    关联规则的整体性能有第一步决定,给定n项,可能有2的n次方个候选项。当然这个算法不是很有效,后面会用Apriori算法代替。

    频繁项对{i, j}在内存中的存放方式

    {用什么数据结构来存储频繁二项集数对更有效}

     

    Triangular Matrix三角阵方法

    {采用一个数组来存储这个三角阵中的元素,它可以节省二维数组一半的空间}


    Note: translate from an items name in the data to its integer.A hash table whose key is the original name of the item in the data will do just fine.


    Note: 因为pairs存放在一个一维数组中。则频繁对(i, j)存放的位置就是上面这个公式。

    Tabular三元组方法

    {当频繁项对的数目小于C(n, 2)的数目的1/3时,三元组的方式相对于三角阵比较有优势}

    Note: 链表实现需要指针指向下一个,这样就是16p而不是12p了。

    两种方法的比较和取舍

    如果有大于1/3的候选二项集是频繁二项集,那么使用Triangular结构存储比较好。if more than one-third of possible pairs are present in at least one basket,you prefer the triangular matrix.

    设频繁一项集数目为N,频繁二项集的数目为M,候选二项集自然就是N^2/2。则使用Triangular矩阵存储频繁二项集的空间为4*N^2/2, 使用Tabular结构存储频繁二项集的空间为12*M。当大于1/3的候选二项集是频繁二项集,也就是1/3 * N^2/2 < M,这时4*N^2/2 < 12*M,使用Triangular矩阵存储频繁二项集的空间较小。

    皮皮blog



    A-priori算法

    {通过限制候选产生来发现频繁项集。Aprior有点类似广度优先的算法。}

    频繁项集的先验性质:单调性和反单调性

    Note: 寻找频繁二项集是扫描两次,频繁k项集当然是k次。if you want to go pass pairs to larger item sets,then you need k passes, define frequent items that's of size up to K.

    A-priori算法步骤

    频繁二项集的挖掘

      

    If there's still too many counts to maintain in main memory,we need to try something else,a different algorithm,splitting the task among different processors, or even buying more memory.

    A-Priori算法中使用Triangular Matrix

      

    Note:

    1. 也就是第一次扫描后,选出频繁一项集并重新编号,组成Triangular Matrix。在Triangular Matrix中再选出频繁二项集重新编号,并组成Triangular Matrix,再进行下一次Apriori算法的计算。

    2. There are better ways to organize the table that save space,if the fraction of items that are frequent is small.For example, we could use a hash table in which we stored only the frequent items with the key being the old number and the associated value being the new number.(也就是Tabular?)

    频繁K项集挖掘

     

    数据挖掘概念与技术中对Apriori算法的图解


    数据挖掘概念与技术中对Apriori算法的描述

    是不是简单清晰得多!

    Apriori算法内存需求分析

    每次计算一个频繁k{k = 1-K}项集,都要扫描一次basket(transaction交易)

    Apriori算法的内存的使用情况,左边为第一步时的内存情况,右图为第二步时内存的使用情况

    pipi

    在第一步(对所有item扫描计数,并选出频繁一项集)里,我们只需要两个表,一个用来保存项的名字到一个整数的映射,用这些整数值代表项,一个数组来计数这些整数。

    皮皮blog



    Reviews复习

    Triangular Matrix和Tabular的选择


    Note: S是N和M的函数。

    从上面分析可知:如果有大于1/3的候选二项集是频繁二项集(也就是1/3 * N^2/2 < M <=> N^2 < 6M),那么使用Triangular结构存储比较好。并且使用Triangular矩阵存储频繁二项集的空间为4*N^2/2, 使用Tabular结构存储频繁二项集的空间为12*M。

    N = 10,000, M=50,000,000,则N^2 = 10^8 < 6M=3*10^8,故使用Triangular矩阵来存储频繁二项集,空间为S = 4*N^2/2=2*10^8。(的确比12*M = 6*10^8小)

    N = 100,000, M=40,000,000,则N^2 = 10^10 > 6M=2.4*10^8,故使用Tabular来存储频繁二项集,空间为S =12*M=4.8*10^8。(的确比4*N^2/2= 2*10^10小)

    N = 100,000, M=100,000,000,则N^2 = 10^10 > 6M=6*10^8,故使用Tabular矩阵来存储频繁二项集,空间为S =12*M=12*10^8。(的确比4*N^2/2= 2*10^10小)

    N = 30,000, M=100,000,000,则N^2 = 9*10^8 > 6M=6*10^8,故使用Tabular矩阵来存储频繁二项集,空间为S =12*M=18*10^8。(的确比4*N^2/2= 12*10^8小)

    from:http://blog.csdn.net/pipisorry/article/details/48894977


    展开全文
  • 大数据机器学习 基础篇 关联分析

    千次阅读 2018-04-22 23:21:37
    这种关联规则在人的认知里反射类似。如在小时候不小心被针扎到,会有痛感,这样针刺和痛感就在大脑里有了这种关联。这就是人在认识事物的过程中在认知中所建立的关联规则,即通过客观事件互动发现事物之间存在的...

    关联规则是人类在认识客观事物中形成的一种认知模式。这种关联规则在人的认知里与反射类似。如在小时候不小心被针扎到,会有痛感,这样针刺和痛感就在大脑里有了这种关联。这就是人在认识事物的过程中在认知中所建立的关联规则,即通过与客观事件互动发现事物之间存在的依赖或因果关系

    注:本文中用到的Python及其模块安装教程参见


    关联分析

    这里的关联分析就是尝试在数据中发现依赖或者因果关系的方法。这其中有一个非常经典的案例,就是“啤酒和尿布”案例。


    案例分析

    据说事情发生在20世纪80年代的美国沃尔玛,销售经理经过研究零售记录发现啤酒和尿布会同时出现在很多购物记录里,令人百思不得其解。经过观察发现,在这个地区会有很多年轻的父亲会时常光顾超市,在超市里为孩子购买尿布的同时也会为自己买上一些啤酒。从此,超市经理借题发挥,又专门把啤酒和尿布的销售货架放在一起,进而让啤酒和尿布的销量进一步提高。

    这种研究方式在零售行业得到了比较广泛的应用,这种分析也称作“购物篮分析”。下面简单介绍一下这个分析过程是怎么实现的。

    一个超市每天有很多的购物记录,为例示例方便,假设只有5个购物记录,购物记录如下:

    • 记录1:(啤酒,香烟,白菜,鸡蛋,酸奶,卫生纸)
    • 记录2:(红酒,香烟,巧克力,酸奶)
    • 记录3:(牙刷,奶糖,食盐,鸡肉,卫生纸)
    • 记录4:(啤酒,酒杯,香烟,瓜子,花生,薯片)
    • 记录5:(酸奶,巧克力,味精)

    我们先建立一个超市中所有商品和超市购物记录的关系型数据库。

    #关联分析(association analysis)
    drop database if exists association_analysis;
    create database association_analysis;
    use association_analysis;
    create table item
    	(ID char(5),
    	 name varchar(20),
    	 primary key (ID, name)
    	);
    
    create table buy_list
    	(serial char(4) not null,
    	 item_ID char(5) not null,
    	 constraint buy_list_fk foreign key (item_ID) references item (ID)
    	);
    
    insert into item values ('00001', 'Beer');
    insert into item values ('00002', 'Cigarette');
    insert into item values ('00003', 'Cabbage');
    insert into item values ('00004', 'Egg');
    insert into item values ('00005', 'Yogurt');
    insert into item values ('00006', 'Toilet paper');
    insert into item values ('00007', 'Wine');
    insert into item values ('00008', 'Chocolate');
    insert into item values ('00009', 'Toothbrush');
    insert into item values ('00010', 'Toffee');
    insert into item values ('00011', 'Saft');
    insert into item values ('00012', 'Chicken');
    insert into item values ('00013', 'Glass');
    insert into item values ('00014', 'Sunflower seeds');
    insert into item values ('00015', 'Peanut');
    insert into item values ('00016', 'Chips');
    insert into item values ('00017', 'Aginomoto');
    
    insert into buy_list values ('0001', '00001');
    insert into buy_list values ('0001', '00002');
    insert into buy_list values ('0001', '00003');
    insert into buy_list values ('0001', '00004');
    insert into buy_list values ('0001', '00005');
    insert into buy_list values ('0001', '00006');
    insert into buy_list values ('0002', '00007');
    insert into buy_list values ('0002', '00002');
    insert into buy_list values ('0002', '00008');
    insert into buy_list values ('0002', '00005');
    insert into buy_list values ('0003', '00009');
    insert into buy_list values ('0003', '00010');
    insert into buy_list values ('0003', '00011');
    insert into buy_list values ('0003', '00012');
    insert into buy_list values ('0003', '00006');
    insert into buy_list values ('0004', '00001');
    insert into buy_list values ('0004', '00013');
    insert into buy_list values ('0004', '00002');
    insert into buy_list values ('0004', '00014');
    insert into buy_list values ('0004', '00015');
    insert into buy_list values ('0004', '00016');
    insert into buy_list values ('0005', '00005');
    insert into buy_list values ('0005', '00008');
    insert into buy_list values ('0005', '00017');
    

    由以下SQL语句可以创建一个购物记录表的视图。

    create view buy_list_view (serial, item_name) as select serial, item.name 
    from buy_list left join item on (buy_list.item_ID = item.ID);
    
    select * from buy_list_view;
    

    -表1:购物记录表Buy-list

    流水号(serial) 单品类别(item_name)
    0001 Beer
    0001 Cigarette
    0001 Cabbage
    0001 Egg
    0001 Yogurt
    0001 Toilet paper
    0002 Wine
    0002 Cigarette
    0002 Chocolate
    0002 Yogurt
    0003 Toothbrush
    0003 Toffee
    0003 Saft
    0003 Chicken
    0003 Toilet paper
    0004 Beer
    0004 Glass
    0004 Cigarette
    0004 Sunflower seeds
    0004 Peanut
    0004 Chips
    0005 Yogurt
    0005 Chocolate
    0005 Aginomoto

    在分析数据之前,先引出几个概念:

    • 频繁模式:在每个购物记录中出现的各种单品其实体现的是一种组合的性质。而这些单品的组合在记录中是无序的,这种无序的组合叫做“模式”。这些模式里,有的出现频率很低,有的出现频率很高,一般认为频率较高的通常更有指导意义,这种高频率的模式就被称作“频繁模式”。
    • 支持度:衡量频繁模式的有用性,为某一种模式在所有模式中出现的记录。例如,在上例中,购买(啤酒,香烟)模式的支持度为40%,也就说明,在所有的购物记录中,有40%的购物记录都包含这两种模式。
    • 置信度:衡量频繁模式的“确定性”,置信度是有“方向性”的,为某种模式中不同维度之间的一种关系。例如,在上例中,购买啤酒的记录里有100%的记录都购买了香烟,那么就说购买啤酒后购买香烟的置信度为100%;反向来看,购买香烟的记录里有67%的记录都购买了啤酒,那么就说购买香烟后购买啤酒的置信度为67%。

    示例计算(啤酒,香烟)模式的支持度:

    #(啤酒,香烟)模式的购物记录数量
    select @someSerial := count(*) from(
    	select *, count(*) from (
    		select serial from (
    			buy_list left join item on (buy_list.item_ID = item.ID)
    		)
    		where item.name = 'Beer' 
    		union all 
    		select serial from (
    			buy_list left join item on (buy_list.item_ID = item.ID)
    		)
    		where item.name = 'Cigarette'
    	) as tmp1
    	group by tmp1.serial having count(*) = 2
    ) as tmp2;
    #所有的购物记录的数量
    select @totalSerial := count(*) from (
    	select serial from buy_list group by serial
    ) as tmp;
    
    set @support = @someSerial / @totalSerial;
    select @support;
    

    示例计算“啤酒=>香烟”的置信度和“香烟=>啤酒”的置信度:

    select @beerSerial := count(*) from buy_list_view where item_name = 'Beer';
    
    select @cigaretteSerial := count(*) from buy_list_view where item_name = 
    'Cigarette';
    
    set @confidenceBeerToCigarette = @someSerial / @beerSerial;
    set @confidenceCigaretteToBeer = @someSerial / @cigaretteSerial;
    select @confidenceBeerToCigarette;
    select @confidenceCigaretteToBeer;
    

    为了表达简便,也常记录如下:

    • 啤酒=>香烟[support=40%,confidence=100%]
    • 香烟=>啤酒[support=40%,confidence=67%]

    我们认为,设置门限“最小支持度”和“最小置信度”之后,支持度和置信度同时高于这两个门限的模式就可以认为是频繁模式

    如果支持度高置信度低,说明这两种情况确实同时出现,但是“转化率”可能比较低。而如果支持度比较低,但是转化率比较高,说明这种模式在所有的模式里很平常,不能算作“频繁模式”。所以基于这样的原因,通常还是会选择支持度和置信度都高于阈值的模式作为频繁模式。


    Apriori算法

    Apriori算法用于求出所有的频繁模式,求解过程有以下几个步骤。

    **步骤1:**先设置一个最小支持度作为阈值门限值进行扫描,因为对同时过滤最小支持度和最小置信度这两个操作来说,最小支持度的查找更为简单一些。假设设置的最小支持度为40%。

    在数据库中建立一个单品支持度的表。

    #Apriori算法求频繁模式
    import pymysql
    import numpy as np
    
    # 打开数据库连接
    db = pymysql.connect( "localhost", "user", "password", 
    "association_analysis" )
    
    # 使用cursor()方法获取操作游标 
    cursor = db.cursor()
    
    # 获取商品条目
    sql = "select name from item"
    cursor.execute(sql)
    items = cursor.fetchall()
    
    # 求所有商品的支持度
    supports = []
    
    for i in range( len(items) ):
     sql = "select count(*) from buy_list_view where item_name = '"+items[i][0]
     +"'"
     cursor.execute(sql)
     supports.append( cursor.fetchone() )
    
    supports = np.array(supports)
    supports.shape = len(items)
    
    sql = "select count(*) from ( select serial from buy_list group by serial ) 
    as tmp"
    cursor.execute(sql)
    total = cursor.fetchone()
    
    supports = supports / total
    
    # 创建单品支持度表
    sql = "drop table if exists supports"
    cursor.execute(sql)
    sql = "create table supports ( item_name varchar(20), support float(2) )"
    cursor.execute(sql)
    
    for i in range( len(items) ):
     sql = "insert into supports values ('"+items[i][0]+"', "+str(supports[i])
     +")"
     try:
      # 执行sql语句
      cursor.execute(sql)
      # 提交到数据库执行
      db.commit()
     except:
      # 如果发生错误则回滚
      db.rollback()
    db.close()
    
    select * from supports;
    
    • 表2:单品支持度表
    单品类别(item_name) 单品支持度(support)
    Beer 0.4
    Cigarette 0.6
    Cabbage 0.2
    Egg 0.2
    Yogurt 0.6
    Toilet paper 0.4
    Wine 0.2
    Chocolate 0.4
    Toothbrush 0.2
    Toffee 0.2
    Saft 0.2
    Chicken 0.2
    Glass 0.2
    Sunflower seeds 0.2
    Peanut 0.2
    Chips 0.2
    Aginomoto 0.2

    **步骤2:**扫描所有满足最小支持度的单品。如果一个模式满足最小支持度40%,那么这个模式中的所有单品都必须满足最小支持度40%,这是一个必要条件。

    select * from supports where support>0.4;
    
    • 表3:支持度大于等于40%的单品
    单品类别(item_name) 单品支持度(support)
    Beer 0.4
    Cigarette 0.6
    Yogurt 0.6
    Toilet paper 0.4
    Chocolate 0.4

    **步骤3:**查找满足条件的2项模式。即支持度满足条件的集合作笛卡尔积。上面的示例给出了计算(啤酒,香烟)模式的支持度。

    • 表3:满足条件的2项模式

    |2项模式|支持度(support)||2项模式|支持度(support)|
    |------|-------||------|-------|
    |Beer,Cigarette|40%||Cigarette,Toilet paper|20%|
    |Beer,Yogurt|20%||Cigarette,Chocolate|20%|
    |Beer,Toilet paper|20%||Yogurt,Toilet paper|20%|
    |Beer,Chocolate|0%||Yogurt,Chocolate|40%|
    |Cigarette,Yogurt|40%||Toilet paper,Chocolate|0%|

    • 表4:满足最小支持度的2项模式
    2项模式 支持度(support)
    Beer,Cigarette 40%
    Yogurt,Chocolate 40%
    Cigarette,Yogurt 40%

    **步骤4:**查找满足条件的3项模式。注意,2项模式满足最小支持度是3项模式满足最小支持度的必要条件,所以只需从满足最小支持度的2项模式中查找即可。

    • 表5:候选的3项模式
    3项模式 支持度(support)
    Beer,Cigarette,Yogurt 20%
    Beer,Cigarette,Chocolate 0
    Cigarette,Yogurt,Chocolate 0

    观察发现,到目前为止,所有的3项模式都不满足最小支持度,那么算法到这里就结束了,因为不可能再找到满足条件的3项,4项以及以后任何多种符合条件的频繁模式了。

    示例代码:求出所有候选模式的支持度和置信度并建表。

    #Apriori算法求频繁模式
    import pymysql
    import numpy as np
    
    # 打开数据库连接
    db = pymysql.connect( "localhost", "user", "password", 
    "association_analysis" )
    
    # 使用cursor()方法获取操作游标 
    cursor = db.cursor()
    
    # # # # # # # # # # # # # # # # # # #
    # 求出所有的2项模式(有顺序)
    sql = 'select * from supports where support>0.4'
    cursor.execute(sql)
    frequentItems = cursor.fetchall()
    frequentPatterns = []
    for i in range(len(frequentItems)):
     for j in range(len(frequentItems)):
      if i==j:
       continue
      frequentPatterns.append( [frequentItems[i][0], frequentItems[j][0]] )
    
    patternCounts=[]
    
    # 求2项模式支持度
    for i in range(len(frequentPatterns)):
     sql="select count(*) from( 
    		 select *, count(*) from ( 
    			 select serial from ( 
    				 buy_list left join item on (buy_list.item_ID = item.ID) ) 
    					 where item.name = '" + frequentPatterns[i][0] + "' 
    			union all 
    			select serial from ( 
    				buy_list left join item on (buy_list.item_ID = item.ID) ) 
    					where item.name = '"+frequentPatterns[i][1] + "'
    		) as tmp1 
    	group by tmp1.serial having count(*) = 2 
    ) as tmp2"
     cursor.execute(sql)
     patternCounts.append(cursor.fetchall())
    
    patternCounts = np.array(patternCounts)
    patternCounts.shape = len(frequentPatterns)
    
    # 所有的购物记录的数量
    sql = "select count(*) from ( select serial from buy_list group by serial ) 
    as tmp"
    cursor.execute(sql)
    total = cursor.fetchone()
    
    patternSupports = patternCounts / total
    
    # 求2项模式置信度
    patternConfidences = []
    for i in range(len(frequentPatterns)):
     sql = "select count(*) from buy_list_view where item_name = '" + 
     frequentPatterns[i][0] + "'"
     cursor.execute(sql)
     itemCounts = cursor.fetchone()[0]
     patternConfidences.append(patternCounts[i] / itemCounts)
    
    # 创建2项模式支持度和置信度表
    sql = "drop table if exists association"
    cursor.execute(sql)
    sql = "create table association ( pattern varchar(50), support float(2), 
    confidence float(2) )"
    cursor.execute(sql)
    
    for i in range(len(frequentPatterns)):
     sql = "insert into association values ('" + frequentPatterns[i][0] + "=>" + 
     frequentPatterns[i][1] + "', "+str(patternSupports[i]) + ", " + 
     str(patternConfidences[i]) + ")"
     try:
      # 执行sql语句
      cursor.execute(sql)
      # 提交到数据库执行
      db.commit()
     except:
      # 如果发生错误则回滚
      db.rollback()
    
    db.close()
    

    建立的关联分析表如下。

    • 表6:关联分析表
    2项模式(pattern) 支持度(support) 置信度(confidence)
    Beer=>Cigarette 0.4 1
    Beer=>Yogurt 0.2 0.5
    Beer=>Toilet paper 0.2 0.5
    Beer=>Chocolate 0 0
    Cigarette=>Beer 0.4 0.666667
    Cigarette=>Yogurt 0.4 0.666667
    Cigarette=>Toilet paper 0.2 0.333333
    Cigarette=>Chocolate 0.2 0.333333
    Yogurt=>Beer 0.2 0.333333
    Yogurt=>Cigarette 0.4 0.666667
    Yogurt=>Toilet paper 0.2 0.333333
    Yogurt=>Chocolate 0.4 0.666667
    Toilet paper=>Beer 0.2 0.5
    Toilet paper=>Cigarette 0.2 0.5
    Toilet paper=>Yogurt 0.2 0.5
    Toilet paper=>Chocolate 0 0
    Chocolate=>Beer 0 0
    Chocolate=>Cigarette 0.2 0.5
    Chocolate=>Yogurt 0.4 1
    Chocolate=>Toilet paper 0 0

    求出所有的频繁模式。

    select pattern from association where support>=0.4 and confidence>=0.4;
    
    • 表7:频繁模式表
    频繁模式(pattern)
    Beer=>Cigarette
    Cigarette=>Beer
    Cigarette=>Yogurt
    Yogurt=>Cigarette
    Yogurt=>Chocolate
    Chocolate=>Yogurt

    由上表可得,频繁模式有(香烟,啤酒),(香烟,酸奶),(酸奶,巧克力)。


    关联分析和相关性分析

    在使用Apriori算法计算出有较高支持度和较高置信度的频繁模式之后,要对这些频繁模式进行一些甄别和分析。但是,是不是所有的频繁模式都是潜在有用的。

    下面引出有关相关规则的分析。之前提过关联规则的一种记述方式,Item1=>Item2 [支持度,置信度],现在给这种记述方式增加一个维度为:Item1=>Item2 [支持度,置信度,关联度]

    提升度(Lift)是一种简单的关联度度量:

    Lift(AB)=P(BA)P(B)\LARGE Lift(A,B)=\frac{P(B|A)}{P(B)}

    上式与朴素贝叶斯公式类似,等号左边是A和B的相关性定义,右边分子是发生A的情况下发生B的概率,分母是发生B的概率。

    • 当相关性是1时,P(B|A)与P(B)相等,也就是说在全样本空间内,B发生的概率和在发生A的情况下发生B的概率是一样的,那么A和B就是毫无关系
    • 当相关性大于1时,P(B|A)大于P(B),也就是说在全样本空间内,发生A的情况下发生B的概率要比单独统计B发生的概率要大,那么B和A就是正相关的。也就是A的发生促进了B的发生
    • 当相关性小于1时,P(B|A)小于P(B),也就是说在全样本空间内,发生A的情况下发生B的概率要比单独统计B发生的概率要小,那么B和A就是负相关的。也就是A的发生抑制了B的发生

    示例代码:求出所有候选模式的关联度并建表。

    import pymysql
    
    # 打开数据库连接
    db = pymysql.connect( "localhost", "user", "password", 
    "association_analysis" )
    
    # 使用cursor()方法获取操作游标 
    cursor = db.cursor()
    
    # # # # # # # # # # # # # # # # # #
    # 求关联度
    sql = "select * from supports"
    cursor.execute(sql)
    supports = cursor.fetchall()
    sql = "select pattern, support from association"
    cursor.execute(sql)
    patterns = cursor.fetchall()
    patternsTmp = []
    for i in range(len(patterns)):
     tmp = patterns[i][0].split("=>")
     tmp.append(patterns[i][1])
     patternsTmp.append(tmp)
    
    def searchSupport(targetItem, supports):
     for support in supports:
      if support[0]==targetItem:
       return support[1]
    
    lift = []
    for pattern in patterns:
     tmp = pattern[2]
     tmp = tmp / searchSupport(pattern[0], supports)
     tmp = tmp / searchSupport(pattern[1], supports)
     lift.append(tmp)
    
    # 为association表添加列lift
    sql = "alter table association add lift float(2)"
    cursor.execute(sql)
    for i in range(len(lift)):
     if lift[i] == 0:
      continue
     sql = "update association set lift = " + str(lift[i]) + " where pattern = 
     '" + patterns[i][0] + "'"
     try:
      # 执行sql语句
      cursor.execute(sql)
      # 提交到数据库执行
      db.commit()
     except:
      # 如果发生错误则回滚
      db.rollback()
    
    db.close()
    

    最终关联分析表如下。

    • 表8:关联分析表
    2项模式(pattern) 支持度(support) 置信度(confidence) 关联度(lift)
    Beer=>Cigarette 0.4 1 1.66667
    Beer=>Yogurt 0.2 0.5 0.833333
    Beer=>Toilet paper 0.2 0.5 1.25
    Beer=>Chocolate 0 0 NULL
    Cigarette=>Beer 0.4 0.666667 1.66667
    Cigarette=>Yogurt 0.4 0.666667 1.11111
    Cigarette=>Toilet paper 0.2 0.333333 0.833333
    Cigarette=>Chocolate 0.2 0.333333 0.833333
    Yogurt=>Beer 0.2 0.333333 0.833333
    Yogurt=>Cigarette 0.4 0.666667 1.11111
    Yogurt=>Toilet paper 0.2 0.333333 0.833333
    Yogurt=>Chocolate 0.4 0.666667 1.66667
    Toilet paper=>Beer 0.2 0.5 1.25
    Toilet paper=>Cigarette 0.2 0.5 0.833333
    Toilet paper=>Yogurt 0.2 0.5 0.833333
    Toilet paper=>Chocolate 0 0 NULL
    Chocolate=>Beer 0 0 NULL
    Chocolate=>Cigarette 0.2 0.5 0.833333
    Chocolate=>Yogurt 0.4 1 1.66667
    Chocolate=>Toilet paper 0 0 NULL

    对于负相关模式,一般来说,如果X和Y都是频繁的,但是很少或者不一起出现,那么就说X和Y是负相关的,X和Y组成的模式就是负相关模式。如果X和Y组成的模式支持度远远小于X的支持度与Y的支持度的乘积,那么就说X和Y是强负相关的。


    想了解更多关于大数据和机器学习:大数据与机器学习专栏

    展开全文
  • uml的关联关系中聚合组合的区别

    千次阅读 2016-04-26 20:39:11
    什么是关联关系?...一种特殊的关联关系,指明一个聚集(整体)组成部分之间的关系。 什么是组合关系? 语义更强的聚合关系,组成部分整体之间具有相同的生命周期。   相同:   聚合关系组合关

    什么是关联关系?

    在UML中,关联关系是描述了类的结构之间的关系。具有方向、名字、角色和多重性等信息。

    一般的关联关系语义较弱。也有两种语义较强,分别是聚合与组合。

     

     

     

    什么是聚合关系?

    一种特殊的关联关系,指明一个聚集(整体)与组成部分之间的关系。

    什么是组合关系?

    语义更强的聚合关系,组成部分与整体之间具有相同的生命周期。

     

    相同:

     

    聚合关系与组合关系都是属于关联关系,他们都是描述了整体与部分之间的关系。

     

    异同:

     

    聚合关系与组合关系相比,组合关系要求类的组成部分与整体之间具有相同生命周期。也就是说,类的组成部分不能脱离整体而存在,而聚合关系可以。

     

    举个车子与轮子的关系。车子是整体,而轮子是组成部分,即使没有车子,轮子还是可以脱离车子单独存在,并可以为其他车辆使用。这种车子-轮子的关联关系就是聚合的体现

     

    举个人和心脏的关系。人是整体,而心脏是组成部分。心脏与人具有相同的生命周期,人死了,心脏也就停了。人活着,心脏就跳动。如果心脏离开了人体便不能单独存在(当然现代的医学技术手段能保存心脏活性的,这里只是举个例子说明)

     

    所以简单的来说。聚合关系和组合关系同样都是描述整体与部分的关系,不同的是,组合关系是一种整体与部分具有相同生命周期的聚合关系。

     

     

    展开全文
  • <!-- 建立一对一关系 --> <one-to-one name="idCard" />
  • 方向导数梯度——学习笔记

    万次阅读 多人点赞 2018-04-27 00:43:34
    方向导数和梯度在高等数学偏导数那一部分提到,两者相互关联,可能会弄混,简单来说方向导数是一个值而梯度是一个向量。了解梯度的概念可以在以后的机器学习或者深度学习模型优化用到梯度下降时更容易理解,接下来让...
  • 灰色关联分析

    千次阅读 2018-09-05 13:56:55
    灰色关联分析:对于两个系统之间的因素,其随时间或不同对象而变化的关联性大小的量度,称为关联度。在系统发展过程中,若两个因素变化的趋势具有一致性,即同步变化程度较高,即可谓二者关联程度较高;反之,则较低...
  • SPSS Modeler——超市商品购买关联分析

    万次阅读 多人点赞 2018-10-31 11:21:09
    这种联系反映一个事物其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。 超市在运营中保存了交易明细帐数据,考虑根据顾客购买商品...
  • 关联规则挖掘

    千次阅读 2014-10-17 22:44:21
    关联规则是数据挖掘技术的一个活跃的研究方向之一,其反映出项目集之间有意义的关联关系。关联规则可以广泛地应用于各个领域,既可以检验行业内长期形成的知识模式,也能够发现隐藏的新规律。有效地发现、理解和运用...
  • 关联规则

    千次阅读 2018-04-18 09:40:56
    1.概念1.1 引论关联规则(AssociationRules)是无监督的机器学习方法,用于知识发现,而预测。关联规则的学习器(learner)无需事先对训练数据进行打标签,因为无监督学习没有训练这个步骤。缺点是很难对关联规则...
  • 在领域模型中,类类之间最普遍的关系就是关联关系。在 UML 中,关联是有方向的。以 Customer 和 Order 为例:一个用户能发出多个订单, 而一个订单只能属于一个客户。从 Order 到 Customer 的关联是多对一关联; 而...
  • 开始学习UML类图中的类类之间的关系中的时候,其中依赖,...多重性关联关系 多重性关联关系又称为重数性关联关系,表示一个类的对象另一个类的对象连接的个数。在UML中多重关系可以直接在关联直线上增加一个数
  • 关联矩阵

    千次阅读 2020-01-31 19:16:08
     有一个n个结点m条边的有向图,请输出他的关联矩阵。 输入格式  第一行两个整数n、m,表示图中结点和边的数目。n<=100,m<=1000。  接下来m行,每行两个整数a、b,表示图中有(a,b)边。  注意图中可能含有重...
  • 关联与依赖、聚合组合

    千次阅读 热门讨论 2014-02-25 19:34:19
    聚合组合   组合 聚合 定义 几个独立部分组成的整体 分散的聚到一起 标识 实心菱形加实线箭头表示 空心菱形加实线箭头表示 整体和部分的关系强弱程度 强 弱 生存期的关系...
  • 激光雷达摄像头数据融合(2)——关键点关联与追踪 上一篇文章我们简要的介绍了一下两个传感器的优劣势,以及他们为什么可以优势互补为我们的应用助力,带来可靠性高的结果。 在这篇文章中,我将介绍数据融合前的...
  • 【UML】关联和依赖

    万次阅读 多人点赞 2018-09-27 09:03:17
    前言 UML四大关系中,包括:泛化,实现,关联,依赖。 泛化就是我们在面向对象中提到的继承,而实现则更多的体现在类和接口之间的关系。 关联和依赖相对于上边两个关系,则表现的不是很容易...关联是类类,类...
  • 关联规则概述

    千次阅读 2006-09-19 11:58:00
    关联规则是数据挖掘的重要方面。我概述如下:概论数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性,就称为关联关联可分为简单关联、时序关联、因果关联关联分析的...
  • MFC控件关联变量

    千次阅读 2016-12-22 10:24:20
    ①值变量:控件关联的数据变量,可以为任何MFC基本数据类型,在控件和变量之间有两种数据的传递方式:控件传递给变量(表征为向控件输入数值改变关联的变量的值),和变量传递给控件(表征为刷新后控件中的...
  • STL关联容器概述

    千次阅读 多人点赞 2011-07-09 16:00:11
    1. 概念 STL容器大的方向分为两类,序列式容器和关联式容器,这两者通过数据在容器内的排列来区分,关联容器是通过键(key)存储和读取元素的,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。标准的STL序列...
  • 关联分析的基本概念

    千次阅读 2018-01-04 13:39:53
    关联分析也是人的一种认知模式,这种关联规则和人的反射类似,就是在认识事物的过程中在认知中建立的关联规则。关联分析是数据挖掘里很重要的部分。1. 频繁模式例如一个超市每天有很多的购物记录,而且消费者的购买...
  • 基本映射是对一个实体进行映射,关联映射就是处理多个实体之间的关系,将关联关系映射到数据库中,所谓的关联关系在对象模型中有一个或多个引用。
  • 数据挖掘之关联分析

    千次阅读 2015-10-04 16:33:13
    数据挖掘之关联分析 1、基本概念 (1)通常认为项在事物中出现比不出现更重要,因此项是非对称二元变量。 (2)关联规则是形如X->Y的蕴涵表达式,其中X和Y是不相交的项集,即X交Y=空。 (3)由关联规则...
  • 关联规则1:关联规则的应用场景

    千次阅读 2020-08-03 11:33:30
    关联规则,作为十大机器学习算法之一,应用非常广泛。最经典的例子当然是“啤酒”和“尿布” 的故事。 这个故事的背景是什么呢?
  • 关联分析(一):频繁项集及规则产生

    万次阅读 多人点赞 2018-09-28 15:46:10
    关联分析用于发现隐藏在大型数据集中有意义的联系,属于模式挖掘分析方法,其为人熟知的经典应用当属沃尔玛超市里“啤酒尿布”的关系挖掘了。关联分析的应用领域非常多,当数据集类型比较复杂时,进行关联分析采用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 195,036
精华内容 78,014
关键字:

关联方向与非关联方向