关联分析

定义

关联分析是指关联规则挖掘，它是数据挖掘中一个重要的、高度活跃的分支，目标是发现事务数据库中不同项（如顾客购买的商品项）之间的联系，这些联系构成的规则可以帮助用户找出某些行为特征（如顾客购买行为模式），以便进行企业决策。
事务数据库->关联分析法->关联规则

事务数据库

定义1 设I={i1，i2，…，im}是一个全局项的集合，其中ij（1≤j≤m）是项（item）的唯一标识，j表示项的序号。事务数据库（transactional databases）D={t1，t2，…，tn}是一个事务（transaction）的集合，每个事务ti（1≤i≤n）都对应I上的一个子集，其中ti是事务的唯一标识，i表示事务的序号。

定义2 由I中部分或全部项构成的一个集合称为项集（itemset），任何非空项集中均不含有重复项。
若I包含m个项，那么可以产生2的M次幂-1个非空项集。
例如，I={i1，i2，i3}，可以产生的非空项集为{i1}，{i2}，{i3}，{i1，i2}，{i1，i3}，{i2，i3}，{i1，i2，i3}，共有7个非空项集。

关联规则及其度量

1.关联规则
关联规则表示项之间的关系，它是形如X→Y的蕴涵表达式，即与X决定Y，其中X和Y是不相交的项集，即X∩Y=Ф，X称为规则的前件，Y称为规则的后件。

例如，“{面包，牛奶}→{鸡蛋}”关联规则表示的含义是购买谷类食品和牛奶的人也会购买水果，它的前件为“{面包，牛奶}”，后件为“{鸡蛋}”，有时也表示为“面包，牛奶→鸡蛋”或“面包 and 牛奶→鸡蛋”等形式。
通常关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量。

2.支持度（support）
给定一个全局项集I和事务数据库D，一个项集I1I在D上的支持度是包含I1的事务在D中所占的百分比

3. 置信度
给定一个全局项集I和事务数据库D，一个定义在I和D上的关联规则形如X→Y，其中X、Y∈I，且X∩Y=Ф，它的置信度（或可信度、信任度）是指包含X和Y的事务数与包含X的事务数之比，即：

给定D上的最小支持度（记为min_sup）和最小置信度（记为min_conf），分别称为最小支持度阈值和最小置信度阈值，同时满足最小支持度阈值和最小置信度阈值的关联规则称为强关联规则，也就是说，某关联规则的最小支持度≥min_sup、最小置信度≥min_conf，则它为强关联规则。

给定全局项集I和事务数据库D，对于I的非空项集I1，若其支持度大于或等于最小支持度阈值min_sup，则称I1为频繁项集（Frequent Itemsets）。
一般地，项集支持度是一个0～1的数值，由于在计算项集支持度时，所有分母是相同的，所以可以用分子即该项集出现的次数来代表支持度，称为支持度计数。

对于I的非空子集I1，若项集I1中包含有I中的k个项，称I1为k-项集。若k-项集I1是频繁项集，称为频繁k-项集。显然，一个项集是否频繁，需要通过事务数据库D来判断。

挖掘关联规则的基本过程

挖掘强关联规则两个基本步骤如下：
① 找频繁项集：通过用户给定最小支持度阈值min_sup，寻找所有频繁项集，即仅保留大于或等于最小支持度阈值的项集。
② 生成强关联规则：通过用户给定最小置信度阈值min_conf，在频繁项集中寻找关联规则，即删除不满足最小置信度阈值的规则。

示例

订单编号	购买商品
1	牛奶、面包、尿布
2	可乐、面包、尿布、啤酒
3	牛奶、尿布、啤酒、鸡蛋
4	面包、牛奶、尿布、啤酒
5	面包、牛奶、尿布、可乐

事务、项、项集、规则

名称	解释	备注
事务	每条交易为一个事务	图中有5个事务
项	交易的每个物品称之为一个项	如面包
项集	包含零个或多个项的集合称为一个项集	如【面包、牛奶】
规则	从项集中找出各项之间的关系	如关联规则[牛奶]–>[面包]
支持度	支持度是个百分比，指的是某个商品组合出现的次数与总次数之间的比例。支持度越高代表这个商品组合出现的频率越大。	5个订单中牛奶的支持度为80%，牛奶+面包出现了3个所以牛奶+面包的支持度为60%
置信度	购买了商品A，有多大概率购买商品B	置信度（牛奶->啤酒）=2/4=50%，置信度(啤酒->牛奶)=2/3=66.7%
提升度	商品A的出现对商品B的出现概率提升的程度，提升度（A->B）=置信度（A->B）/支持度(B)	1.提升度（A->B）>1代表有提升，=1代表没有提升没有下降、<1代表下降
频繁项集	支持度大于等于最小支持度（Min Support）阈值的项集	阈值设为50%的时候，{牛奶，面包}支持度为60%，所以是频繁项集