Аналитика больших данных - правила ассоциации

Пусть I = i 1 , i 2 , ..., i n будет набором из n двоичных атрибутов, называемых элементами. Пусть D = t 1 , t 2 , ..., t m - набор транзакций, называемый базой данных. Каждая транзакция в D имеет уникальный идентификатор транзакции и содержит подмножество элементов в I. Правило определяется как импликация формы X ⇒ Y, где X, Y ⊆ I и X ∩ Y = ∅.

Наборы элементов (для коротких наборов элементов) X и Y называются предшествующими (левая сторона или LHS) и последующими (правая сторона или правая сторона) правила.

Чтобы проиллюстрировать концепции, мы используем небольшой пример из области супермаркетов. Набор элементов - это I = {молоко, хлеб, масло, пиво}, а небольшая база данных, содержащая элементы, показана в следующей таблице.

номер транзакции Предметы
1 молоко, хлеб
2 хлеб, масло
3 пиво
4 молоко, хлеб, масло
5 хлеб, масло

Примером правила для супермаркета может быть {молоко, хлеб} ⇒ {масло}, означающее, что если покупаются молоко и хлеб, покупатели также покупают масло. Чтобы выбрать интересные правила из набора всех возможных правил, можно использовать ограничения на различные меры значимости и интереса. Наиболее известные ограничения - это минимальные пороговые значения поддержки и уверенности.

Поддержка supp (X) набора элементов X определяется как доля транзакций в наборе данных, которые содержат этот набор элементов. В примере базы данных в Таблице 1 набор элементов {молоко, хлеб} имеет поддержку 2/5 = 0,4, поскольку он встречается в 40% всех транзакций (2 из 5 транзакций). Нахождение частых наборов заданий можно рассматривать как упрощение проблемы обучения без учителя.

Достоверность правила определяется conf (X ⇒ Y) = supp (X ∪ Y) / supp (X). Например, правило {молоко, хлеб} ⇒ {масло} имеет достоверность 0,2 / 0,4 = 0,5 в базе данных в таблице 1, что означает, что для 50% транзакций, содержащих молоко и хлеб, правило верно. Доверие можно интерпретировать как оценку вероятности P (Y | X), вероятности нахождения правой части правила в транзакциях при условии, что эти транзакции также содержат левую часть правила.

В скрипте, расположенном в 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"))

Чтобы сгенерировать правила с использованием априорного алгоритма, нам нужно создать матрицу транзакций. В следующем коде показано, как это сделать в 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}