Big Data Analytics - Zasady asocjacji

Niech I = i 1 , i 2 , ..., i n będzie zbiorem n atrybutów binarnych zwanych przedmiotami. Niech D = t 1 , t 2 , ..., t m będzie zbiorem transakcji zwanych bazą danych. Każda transakcja w D ma unikalny identyfikator transakcji i zawiera podzbiór pozycji w I. Reguła jest zdefiniowana jako implikacja postaci X ⇒ Y, gdzie X, Y ⊆ I i X ∩ Y = ∅.

Zbiory elementów (dla krótkich zestawów elementów) X i Y nazywane są poprzednimi (lewostronnymi lub LHS) i następczymi (prawostronnymi lub prawostronnymi) reguły.

Aby zilustrować koncepcje, posłużymy się małym przykładem z domeny supermarketów. Zestaw elementów to I = {mleko, chleb, masło, piwo}, a mała baza danych zawierająca elementy jest pokazana w poniższej tabeli.

Identyfikator transakcji Przedmiotów
1 mleko, chleb
2 masło do chleba
3 piwo
4 mleko, chleb, masło
5 masło do chleba

Przykładową regułą dla supermarketu może być {mleko, chleb} ⇒ {masło}, co oznacza, że ​​jeśli kupuje się mleko i chleb, klienci kupują również masło. Aby wybrać interesujące reguły ze zbioru wszystkich możliwych reguł, można zastosować ograniczenia dotyczące różnych miar istotności i zainteresowania. Najbardziej znanymi ograniczeniami są minimalne progi wsparcia i zaufania.

Wsparcie (X) zestawu pozycji X jest zdefiniowane jako odsetek transakcji w zbiorze danych, który zawiera zestaw pozycji. W przykładowej bazie danych w tabeli 1 zestaw pozycji {mleko, chleb} ma wsparcie 2/5 = 0,4, ponieważ występuje w 40% wszystkich transakcji (2 z 5 transakcji). Znajdowanie częstych zestawów przedmiotów może być postrzegane jako uproszczenie problemu uczenia się bez nadzoru.

Pewność reguły jest określona conf (X ⇒ Y) = sup (X ∪ Y) / sup (X). Na przykład reguła {mleko, chleb} ⇒ {masło} ma w bazie danych w Tabeli 1 pewność 0,2 / 0,4 = 0,5, co oznacza, że ​​dla 50% transakcji zawierających mleko i chleb reguła jest prawidłowa. Zaufanie można interpretować jako oszacowanie prawdopodobieństwa P (Y | X), prawdopodobieństwa znalezienia RHS reguły w transakcjach pod warunkiem, że transakcje te zawierają również LHS.

W skrypcie znajdującym się w bda/part3/apriori.R kod do implementacji apriori algorithm może być znaleziony.

# 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"))

Aby wygenerować reguły za pomocą algorytmu apriori, musimy stworzyć macierz transakcji. Poniższy kod pokazuje, jak to zrobić w języku 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}