关联规则,从啤酒与尿片到Apriori

2015-06-30 R

啤酒到尿片的故事激励着一代又一代的年轻人走向数据挖掘的道路(偷笑ing).不知道的自动补故事:

“在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：”跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在“尿布与啤酒”背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒[1]"

从海量的数据中挖掘出有相关关系的商品是数据挖掘关注的领域之一.它的名字叫做 关联规则(Association Rule) 也是 购物篮分析(Market Basket Analysis) 中比较关键的一环.它的目的是:

通过顾客购买的数据,挖掘出相关性较高的商品组合.

接下来,我会详细分析下关联准则的一般含义和一些简要的代码实现

关联规则

首先先给出一些定义:

假设我们购物篮的数据是这样的,

Itemsets

{1,2,3,4}

{1,2,4}

{1,2}

{2,3,4}

{2,3}

{3,4}

{2,4}

itemset(商品组合):
- {1,2,3,4}代表购买了1,2,3,4四种商品

繁项集: 出现频率较高的集合

Item	Support Freq
{1}	3
{2}	6
{3}	4
{4}	5

支持频数(support freq)
- 可以看到出现的商品为1,2,3,4四种商品
- 每种商品在购物篮中出现的频数就是支持频数

Item	Support
{1}	3/6
{2}	6/6
{3}	4/6
{4}	5/6

Item	Support
{1,2}	3/6
{1,3}	1/6
{1,4}	2/6
{2,3}	3/6
{2,4}	4/6
{3,4}	3/6

支持度(support)
- (s(A))代表商品A的支持度,(s(A,B))代表A,B的支持度
- 可以理解为商品/商品组合出现的频率
- 一般会选择支持度大于某个阈值的规则作为输出规则

置信度(confidence)
- (c(A,B) = s(A,B)/S(A))
- 体现了在A商品出现的情
- (c(A,B) = 1, c(B,A) = 0.5)意味着所有买了A商品的顾客也买了B
- 而买了B商品的顾客只有半买了A商品

简单的关联准则筛选,寻找的是支持度与置信度都大于某个阈值的准则,支持度较高说明这个准则对更多的人适用,置信度较高能找到更高的先后关系:(c(A,B) = 1, c(B,A) = 0.5)会让我选择为买了A商品的客户推荐B而不是相反.

[support \geq minsup] [confidence \geq minconf]

总的看来,关联规则也就仅此而已了,看起来结构不难,就是寻找出现频数较高的商品组合,作为输出.实际上,关联规则难在计算的过程上:假如有100个商品,长度为2的准则有4950,长度为3的准则有1.61710^{5}…

一个较好的计算方式是Apriori

Apriori

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛的应用到商业、网络安全等各个领域。

伪代码:

图展示的实现过程:

代码实现

在R中,可以使用arules来对购物篮数据进行Apriori的分析,不过我这里想自己写一遍购物篮准则的实现,简单的约束支持度的关联规则实现.

arules包中的实现用的是稀疏矩阵来代替列表型的数据,这里我们直接用list来进行分析.

1输入实例数据

a="牛奶,鸡蛋,面包,薯片
鸡蛋,爆米花,薯片,啤酒
鸡蛋,面包,薯片
牛奶,鸡蛋,面包,爆米花,薯片,啤酒
牛奶,面包,啤酒
鸡蛋,面包,啤酒
牛奶,面包,薯片
牛奶,鸡蛋,面包,黄油,薯片
牛奶,鸡蛋,黄油,薯片
"
input_list = strsplit(a,"\n")[[1]]
input_list = sapply(input_list,function(x) strsplit(x,","))
names(input_list) = 1:9

input_list

## $1
## [1] "牛奶" "鸡蛋" "面包" "薯片"
##
## $2
## [1] "鸡蛋"   "爆米花" "薯片"   "啤酒"
##
## $3
## [1] "鸡蛋" "面包" "薯片"
##
## $4
## [1] "牛奶"   "鸡蛋"   "面包"   "爆米花" "薯片"   "啤酒"
##
## $5
## [1] "牛奶" "面包" "啤酒"
##
## $6
## [1] "鸡蛋" "面包" "啤酒"
##
## $7
## [1] "牛奶" "面包" "薯片"
##
## $8
## [1] "牛奶" "鸡蛋" "面包" "黄油" "薯片"
##
## $9
## [1] "牛奶" "鸡蛋" "黄油" "薯片"

2判断函数

建立一个判断函数,目的是检测某条准则是不是在一个交易记录中

## 一个用于判断候选是否存在于某账单的函数
%arule_in% = function(list_c,list_itemset){
  ans = sapply(list_c,function(x) x %in% list_itemset)
  all(ans)
}

## test for %arule_in%
input_list[[1]]

## [1] "牛奶" "鸡蛋" "面包" "薯片"

"牛奶" %arule_in% input_list[[1]]

## [1] TRUE

list("牛奶","鸡蛋") %arule_in% input_list[[1]]

## [1] TRUE

list("牛奶","爆米花") %arule_in% input_list[[1]]

## [1] FALSE

3准则生成函数

这个函数的目的是从长度为k的准则(每条准则k商品)生成一个长度为k+1的准则

## 一个用于生成更高长度准则的函数
create_rules = function(shorter.rules){
    item_vec = do.call(c,shorter.rules)
    unique_item = unique(item_vec)
    a = list()
    for(i in 1:length(shorter.rules)){
      for ( j in 1:length(unique_item)){
      if(unique_item[j] %in% shorter.rules[[i]]){
        a[[length(unique_item)(i-1) + j]] = NA
      }else{
        a[[length(unique_item)(i-1) + j]] =
          sort(c(shorter.rules[[i]],unique_item[j]))
      }
      }}
      a = unique(a)
      a[[1]] = NULL
      a
}

## Test create_rules function
shorter_rules = unique(do.call(c,input_list))
shorter_rules = as.list(shorter_rules)
create_rules(shorter_rules)[1:5]

## [[1]]
## [1] "鸡蛋" "牛奶"
##
## [[2]]
## [1] "面包" "牛奶"
##
## [[3]]
## [1] "牛奶" "薯片"
##
## [[4]]
## [1] "爆米花" "牛奶"
##
## [[5]]
## [1] "牛奶" "啤酒"

create_rules(create_rules(shorter_rules))[1:5]

## [[1]]
## [1] "鸡蛋" "面包" "牛奶"
##
## [[2]]
## [1] "鸡蛋" "牛奶" "薯片"
##
## [[3]]
## [1] "爆米花" "鸡蛋"   "牛奶"
##
## [[4]]
## [1] "鸡蛋" "牛奶" "啤酒"
##
## [[5]]
## [1] "黄油" "鸡蛋" "牛奶"

4主程序

其实这个主程序还是写的比较繁的…有一大段比较重复可以并在一个循环中来着的…

## 主程序
getApriori = function(input_list,# 输入数据,list
                      support,# 支持度
                      rule_min = 2,# 最短准则长度
                      rule_max = 2# 最长准则长度
                      ){
  if(rule_max<rule_min)
    stop("rule_max shloud bigger than rule_min!")

  rule_output = list(0)
  support_output = list(0)
  n = length(input_list)

  rule_cache = as.list(unique(do.call(c,input_list)))
  support_cache = unique(do.call(c,input_list))
  for ( i in 1:length(rule_cache)){
    support_freq = sapply( input_list ,
            function(x) rule_cache[[i]] %arule_in% x )
    support_cache[i] = sum(support_freq)/n

  }
  judge = which(support_cache>support)



  rule_output[[1]] = rule_cache[judge]
  support_output[[1]] = support_cache[judge]


  for(k in 2:rule_max){

    rule_cache = create_rules(rule_output[[k-1]])
    support_cache = 0
    for ( i in 1:length(rule_cache)){
      support_freq = sapply( input_list ,
                             function(x) rule_cache[[i]] %arule_in% x )
      support_cache[i] = sum(support_freq)/n

    }
    judge = which(support_cache>support)



    rule_output[[k]] = rule_cache[judge]
    support_output[[k]] = support_cache[judge]

  }


  output = list()
  for(i in 1:(rule_max-rule_min+1)){
    rules = sapply(rule_output[[rule_min+i-1]],
                   function(x) paste(x,collapse = ","))
    if (length(rules) ==0){
      print(paste("No association found in length of",
                  i+rule_min-1))
      break
    }
    output[[i]] = data.frame(rules = rules,
                             support = support_output[[rule_min+i-1]]
                             )
  }
  output
}

5测试

getApriori(input_list,# 输入数据,list
           support = 0.5,2,3)

## [1] "No association found in length of 3"

## [[1]]
##       rules   support
## 1 面包,牛奶 0.5555556
## 2 牛奶,薯片 0.5555556
## 3 鸡蛋,面包 0.5555556
## 4 鸡蛋,薯片 0.6666667
## 5 面包,薯片 0.5555556

getApriori(input_list,
           support = 0.3,2,3)

## [[1]]
##       rules   support
## 1 鸡蛋,牛奶 0.4444444
## 2 面包,牛奶 0.5555556
## 3 牛奶,薯片 0.5555556
## 4 鸡蛋,面包 0.5555556
## 5 鸡蛋,薯片 0.6666667
## 6 鸡蛋,啤酒 0.3333333
## 7 面包,薯片 0.5555556
## 8 面包,啤酒 0.3333333
##
## [[2]]
##            rules   support
## 1 鸡蛋,面包,牛奶 0.3333333
## 2 鸡蛋,牛奶,薯片 0.4444444
## 3 面包,牛奶,薯片 0.4444444
## 4 鸡蛋,面包,薯片 0.4444444

6经典的啤酒尿片

dataset = list(
    c(‘bread’, ‘milk’),
    c(‘bread’, ‘diaper’, ‘beer’, ‘eggs’),
    c(‘milk’, ‘diaper’, ‘beer’, ‘coke’),
    c(‘bread’, ‘milk’, ‘diaper’, ‘beer’),
    c(‘bread’, ‘milk’, ‘diaper’, ‘coke’)
)
getApriori(dataset,
           support = 0.3,2,3)

## [[1]]
##          rules support
## 1   bread,milk     0.6
## 2 bread,diaper     0.6
## 3   beer,bread     0.4
## 4  diaper,milk     0.6
## 5    beer,milk     0.4
## 6    coke,milk     0.4
## 7  beer,diaper     0.6
## 8  coke,diaper     0.4
##
## [[2]]
##               rules support
## 1 bread,diaper,milk     0.4
## 2 beer,bread,diaper     0.4
## 3  beer,diaper,milk     0.4
## 4  coke,diaper,milk     0.4

7win用户

win用户目测输出的utf-8码会出问题,恩,老实换英文来测试吧~

### For windows:
a = gsub("牛奶","milk",a)
a = gsub("鸡蛋","egg",a)
a = gsub("面包","bread",a)
a = gsub("薯片","chips",a)
a= gsub("啤酒","beer",a)
a= gsub("黄油","butter",a)
a= gsub("爆米花","popcorn",a)
a
input_list = strsplit(a,"\n")[[1]]
input_list = sapply(input_list,function(x) strsplit(x,","))
names(input_list) = 1:9

input_list


getApriori(input_list,# 输入数据,list
           support = 0.5,2,3)

getApriori(input_list,
           support = 0.3,2,3)

[1]
http://baike.baidu.com/link?url=HSFhQ6Ns8RJ_9KNWWovuhoDIeKa66i2x2gdfFbEyI5_7ejYkhw_-gGKWnKaKHhLPK6AKWQRMVRDG3WMm6VY1Cq

[2] wikihttps://en.wikipedia.org/wiki/Association_rule_learning
[3] 图片:http://blog.csdn.net/lizhengnanhua/article/details/9061887