关联分析

多年前，新的互联网销售开始在网上卖书，随着时间的推移，积累了一些关于客户购买书籍的信息。使用关联分析，可以识别一些客户有相似兴趣的书，使用用户购买信息，建立相应的推荐系统。

关联分析是发现数据集中对象或者属性间的相关性，这些相关性可以用关联规则来表达。这个方法一直成功的应用于大的事物数据库，比如购物车和线上客户的购买。关联分析是数据挖掘核心算法之一。

对于线上卖书的实例，原始数据作为建模的基础识别数据。比如，一个用户购买了两本特定的的书，也很有可能购买相关的另外一本特定的书。原始数据可能表明所有用户购买前两本书的的概率是0.5%，但是70%的人会购买第三本。作为一个企业，我们将利用观察到的这个信息，对购买前两种书的客户投入第三种书的广告。

关联分析输入数据的一般类型由事物型数据构成，如在超市购物车中的商品信息、单机购买的书和光盘、病人收到的药物治疗和测试数据等。

这一篇简单介绍了关联分析的内容，以及在Rattle和R中的实现。

1.知识概要

关联规则的表达即是表明事物间的相关性，假设每项事物由一系列的项目组成（可以表示为{A，B，C，D，E，F}），目的是确定一起出现在多个购物车中的项目集合（可能项目{A，C，F}一起出现在多个购物车当中）这里我们称之为项集。比如我们确认规则A，F=>C，意思是当A和F在事物中出现的时候（购物车中出现A和F），那么C通常也会出现。

 

关联分析输出的模型可以由一系列的关联规则表示，关联规则的一般格式表示为：  A -->C

A和C都是集合当中的一项，通常我们将项目看作特定的书籍，比如特定的杂货店项目。例子可能是：

牛奶 ---> 面包

啤酒&坚果 --->马铃薯薯片

史莱克1 --->史莱克2&史莱克3

项目的内容可以概括为特定的属性/值的组合。关联分析的内容可以应用于许多不同的数据集。使用weather数据集，关联规则的表达如下：

WindDir3pm=NNW  --->  RainToday = No.

2.启发式搜索

关联分析算法的基础是生成频繁项集。等频出现的项目的集合组成一个频繁项集来生成关联规则。

确定数据中的频繁项集的计算代价是昂贵的，即使是适度的数据集。Apriori算法前提要求对象的频繁项集的所有子集都是等频的，就是说，假如{牛奶，面包，奶酪}是一个频繁项集，那么它的子集{牛奶，面包}，{牛奶，奶酪}，{面包，奶酪}，{牛奶}，{面包}和{奶酪}要是频繁的。使用频繁的个体使得算法的搜索空间大大降低，第一步就消除了罕见的项目个体。之后我们合并剩余的单项到频繁项集。

足够频繁项是算法的一个的参数用来控制发现的规则的数目，称之为支持度，来具体规定项目在数据集中必须出现的频次。比如，用户可以选择频繁项在所有事物中出现的概率至少5%。

第二阶段算法考虑每个频繁项集生成关联规则的所有可能的组合，因此，对于包含三个项目的频繁项集{牛奶，面包，奶酪}，可能的关联规则如下：

面包 & 牛奶  -->  奶酪

牛奶  --> 面包&奶酪

奶酪&牛奶  --->面包    等等。

我们保留的实际的关联规则满足一项称为置信度的标准，置信度的计算是即包含A又包含C在事物中所占的比例，置信度为关联规则指定一个最小的概率。比如，用户可以选择生成的规则至少90%以上的时间是有效的（也就是说，当A出现在购物车中，C也至少出现在相同的购物车中的时间是90%以上）。

apriori算法是一个广度优先搜索算法，当搜索完所有的k项可能的项目后再考虑搜索包含k+1项。对于每一个k，所有的候选项都需要经过测试来确定它们是否有足够的支持度。

总的来说，我们主要分两阶段来做。第一阶段，我们生成一个大小为k的频繁项集，然后将它们合并生成大小为k+1的候选频繁项集。第二阶段，我们建立候选的关联规则。

3.具体措施

关联分析两个主要的计算是支持度和置信度。最小支持度是项目（items）I在所有事物中所占的比例，也可以理解为项目同时出现在事物中的频率。我们定义支持度如下：

Support（A-->C）= P（AUC）

最小置信度被表示为所有事物在数据集所占的比例，它是个条件概率：

Confidence(A-->C)=P(C|A)=P(AUC)/P(A)

也可以用支持度表示：

Confidence(A-->C)=support(A-->C)/support(A)

在rattle和R中使用的关联规则分析是lift，计算如下：

Lift（A-->C）= confidence(A-->C)/support(C)

4.案例分析

使用rattle建立模型

如果没有安装rattle，通过以下命令安装：

>insatll.packages("rattle") >library(rattle) >rattle()

　我们接下来使用rattle自带的一个DVD Moves包：dvdtrans.csv.加载方法是首先Source选项选择Spreadsheet，在Data工具栏点击执行按钮，点开Filename右边的文件夹标识，将会出现一个选择文件的窗口，然后点击选取dvdtrans.csv文件，如下图1所示：

选在打开，然后点击执行按钮。

我们看到这个数据集只有两个属性ID和Item。我们将Item的属性改为Target（XXXX）。

Rattle建立关联规则模型通过Associate工具栏。如果勾选了Baskets选项，rattle将会使用Ident和Target属性来进行分析，执行一个超市购物车分析。如果不勾选，rattle将会使用输入数据进行规则分析。我们这里选用的数据集要勾选Baskets。

点击选择Associate工具栏下，勾选Baskets，点击执行按钮，运行结果如下图所示：

以下依次介绍文本视区内容：

Summary of the Apriori Associate Rules（关联规则总结）

Number of Rules:规则的总数

再下面分别是support,confidence,lift三种方法关于29条规则的测量信息。

再下面是构建apriori模型过程，参数规范（Parameter Specification）列出了一些初始化参数。

控制算法运行的一组参数（Algorithmic control），再下面是算法运行的具体细节。

Freq Plot按钮将会绘制Item对象的频率分布：

show rules按钮将会再文本视区打印所有的规则：

旁边的plot可以生成规则视图：

由图中图形大小代表支持度，图形颜色深浅代表lift。几种电影的关联程度一目了然。

 

 原创文章，转载请注明出处。（阿蛮的杜鹃：）