Big Data Analytics 简明教程

Big Data Analytics - Association Rules

令 I = i1, i2, …​, in 是称为项的 n 个二进制属性的集合。令 D = t1, t2, …​, tm 是称为数据库的事务集合。D 中的每笔交易具有唯一的交易 ID，并且包含 I 中项的子集。规则定义为形式为 X ⇒ Y 的蕴含，其中 X, Y ⊆ I 且 X ∩ Y = ∅。

项集（简称项集）X 和 Y 称为规则的前件（左侧或 LHS）和结果（右侧或 RHS）。

为了说明这些概念，我们使用超市领域的一个小示例。项集为 I = {牛奶、面包、黄油、啤酒}，下表中显示了一个包含该项的小数据库。

Transaction ID

Items

1

milk, bread

2

bread, butter

3

beer

4

milk, bread, butter

5

bread, butter

超市的一个示例规则可以是 {牛奶、面包} ⇒ {黄油}，这意味着如果购买牛奶和面包，顾客也会购买黄油。为了从所有可能的规则集中选择出有趣的规则，可以使用对各种重要性和兴趣度量要求约束。众所周知，对支持度和置信度的约束最低。

项集 X 的支持度 supp(X) 定义为包含该项集的数据集中事务的比例。在表 1 中的示例数据库中，项集 {牛奶、面包} 的支持度为 2/5 = 0.4，因为它出现在 40% 的所有交易中（5 笔交易中的 2 笔）。查找频繁项集可视为无监督学习问题的简化。

规则的置信度定义为 conf(X ⇒ Y ) = supp(X ∪ Y )/supp(X)。例如，规则 {牛奶、面包} ⇒ {黄油} 在表 1 中的数据库中的置信度为 0.2/0.4 = 0.5，这意味着在包含牛奶和面包的交易中，该规则在 50% 的交易中是正确的。置信度可解释为概率 P(Y|X) 的估计，即在这些事务也包含 LHS 的条件下，在事务中找到规则 RHS 的概率。

可以在 bda/part3/apriori.R 中找到用于实现 apriori algorithm 的代码。

# Load the library for doing association rules
# install.packages(’arules’)
library(arules)

# Data preprocessing
data("AdultUCI")
AdultUCI[1:2,]
AdultUCI[["fnlwgt"]] <- NULL
AdultUCI[["education-num"]] <- NULL

AdultUCI[[ "age"]] <- ordered(cut(AdultUCI[[ "age"]], c(15,25,45,65,100)),
   labels = c("Young", "Middle-aged", "Senior", "Old"))
AdultUCI[[ "hours-per-week"]] <- ordered(cut(AdultUCI[[ "hours-per-week"]],
   c(0,25,40,60,168)), labels = c("Part-time", "Full-time", "Over-time", "Workaholic"))
AdultUCI[[ "capital-gain"]] <- ordered(cut(AdultUCI[[ "capital-gain"]],
   c(-Inf,0,median(AdultUCI[[ "capital-gain"]][AdultUCI[[ "capitalgain"]]>0]),Inf)),
   labels = c("None", "Low", "High"))
AdultUCI[[ "capital-loss"]] <- ordered(cut(AdultUCI[[ "capital-loss"]],
   c(-Inf,0, median(AdultUCI[[ "capital-loss"]][AdultUCI[[ "capitalloss"]]>0]),Inf)),
   labels = c("none", "low", "high"))

为了使用 Apriori 算法生成规则，我们需要创建一个事务矩阵。以下代码展示了如何在 R 中执行此操作。

# Convert the data into a transactions format
Adult <- as(AdultUCI, "transactions")
Adult
# transactions in sparse format with
# 48842 transactions (rows) and
# 115 items (columns)

summary(Adult)
# Plot frequent item-sets
itemFrequencyPlot(Adult, support = 0.1, cex.names = 0.8)

# generate rules
min_support = 0.01
confidence = 0.6
rules <- apriori(Adult, parameter = list(support = min_support, confidence = confidence))

rules
inspect(rules[100:110, ])
# lhs                             rhs                      support     confidence  lift
# {occupation = Farming-fishing} => {sex = Male}        0.02856148  0.9362416   1.4005486
# {occupation = Farming-fishing} => {race = White}      0.02831579  0.9281879   1.0855456
# {occupation = Farming-fishing} => {native-country     0.02671881  0.8758389   0.9759474
                                       = United-States}