Phân tích dữ liệu lớn - Quy tắc liên kết
Gọi I = i 1 , i 2 , ..., i n là tập hợp n thuộc tính nhị phân được gọi là mục. Gọi D = t 1 , t 2 , ..., t m là tập các giao dịch được gọi là cơ sở dữ liệu. Mỗi giao dịch trong D có một ID giao dịch duy nhất và chứa một tập hợp con của các mục trong I. Quy tắc được định nghĩa là hàm ý của dạng X ⇒ Y trong đó X, Y ⊆ I và X ∩ Y = ∅.
Tập hợp các mục (đối với các tập mục ngắn) X và Y được gọi là tiền đề (bên trái hoặc LHS) và là hệ quả (bên phải hoặc RHS) của quy tắc.
Để minh họa các khái niệm, chúng tôi sử dụng một ví dụ nhỏ từ miền siêu thị. Tập hợp các mục là I = {sữa, bánh mì, bơ, bia} và một cơ sở dữ liệu nhỏ chứa các mục được hiển thị trong bảng sau.
| ID giao dịch | Mặt hàng |
|---|---|
| 1 | bánh mì sữa |
| 2 | bơ bánh mì |
| 3 | bia |
| 4 | sữa, bánh mì, bơ |
| 5 | bơ bánh mì |
Một quy tắc ví dụ cho siêu thị có thể là {sữa, bánh mì} ⇒ {bơ} có nghĩa là nếu mua sữa và bánh mì, khách hàng cũng mua bơ. Để chọn các quy tắc thú vị từ tập hợp tất cả các quy tắc có thể có, có thể sử dụng các ràng buộc về các thước đo ý nghĩa và mức độ quan tâm khác nhau. Các hạn chế được biết đến nhiều nhất là ngưỡng tối thiểu về sự hỗ trợ và độ tin cậy.
Hỗ trợ supp (X) của tập hợp mục X được định nghĩa là tỷ lệ các giao dịch trong tập dữ liệu chứa tập hợp mục. Trong cơ sở dữ liệu ví dụ ở Bảng 1, bộ mục {milk, bread} có mức hỗ trợ là 2/5 = 0,4 vì nó xảy ra trong 40% tất cả các giao dịch (2 trong số 5 giao dịch). Việc tìm kiếm các tập hợp mục thường xuyên có thể được coi là đơn giản hóa vấn đề học tập không giám sát.
Độ tin cậy của một quy tắc được xác định conf (X ⇒ Y) = supp (X ∪ Y) / supp (X). Ví dụ: quy tắc {sữa, bánh mì} ⇒ {butter} có độ tin cậy là 0,2 / 0,4 = 0,5 trong cơ sở dữ liệu trong Bảng 1, có nghĩa là đối với 50% các giao dịch có chứa sữa và bánh mì, quy tắc là đúng. Độ tin cậy có thể được hiểu là ước tính xác suất P (Y | X), xác suất tìm thấy RHS của quy tắc trong các giao dịch với điều kiện các giao dịch này cũng chứa LHS.
Trong tập lệnh nằm ở bda/part3/apriori.R mã để triển khai apriori algorithm có thể được tìm thấy.
# 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"))Để tạo các quy tắc bằng thuật toán apriori, chúng ta cần tạo một ma trận giao dịch. Đoạn mã sau đây cho thấy cách thực hiện việc này trong 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}