Пусть 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) и последовательными (правая сторона или RHS) правила.
Чтобы проиллюстрировать концепции, мы используем небольшой пример из домена супермаркета. Набор элементов — это 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), вероятности нахождения RHS правила в транзакциях при условии, что эти транзакции также содержат LHS.
В скрипте, расположенном в bda / part3 / apriori.R, можно найти код для реализации алгоритма apriori .
# 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.