Bài 2: Luật kết hợp
1
KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
– Tìm tần số mẫu, mối kết hợp, sự tương quan, hay các cấu trúc
•• KhaiKhai phpháá luluậậtt kkếếtt hhợợpp::
•• TTíính hi
nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác. nh hiểểu đưu đượợc:c: dễ hiểu
– Phân tích dữ liệu giỏ hàng, cross-marketing, thiết kế catalog, loss-
leader analysis, gom cụm, phân lớp, ...
2
•• TTíính snh sửử ddụụng đư •• TTíính hi ng đượợc: c: Cung cấp thông tin thiết thực nh hiệệu quu quảả: : Đã có những thuật toán khai thác hiệu quả •• CCáácc ứứngng ddụụngng::
KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
– khăn ⇒ bia [0.5%, 60%] – mua:khăn ⇒ mua:bia [0.5%, 60%]
– “Nếu mua khăn thì mua bia trong 60% trường hợp. Khăn và bia
được mua chung trong 0.5% dòng dữ liệu."
•• ĐĐịịnhnh ddạạngng ththểể hihiệệnn đđặặcc trưng trưng chocho ccáácc luluậậtt kkếếtt hhợợpp::
– mua(x, “khăn") ⇒ mua(x, “bia") [0.5%, 60%] – khoa(x, "CS") ^ học(x, "DB") ⇒ điểm(x, "A") [1%, 75%]
3
•• CCáácc bibiểểuu didiễễnn khkháácc::
KhaiKhai phpháá ddữữ liliệệuu
1
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
khăn ⇒ bia [0.5%, 60%]
1 2 3 4 “NẾU mua khăn THÌ mua bia trong 60% trường hợp trên 0.5% dòng dữ liệu"
11 TiTiềềnn đđềề, vế trái, thân 22 MMệệnhnh đđềề kkếếtt ququảả, vế phải, đầu 33 Support
4
44 Confidence Support, tần số (“trong bao nhiêu phần trăm dữ liệu thì những điều ở vế trái và vế phải cùng xảy ra") Confidence, độ mạnh (“nếu vế trái xảy ra thì có bao nhiêu khả năng vế phải xảy ra")
KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
•• ĐĐộộ ủủngng hhộộ:: ¨ ¨ ¨ ¨ ¨ ¨ support(A A ⇒⇒ B [ s, c ] support( biểu thị tần số luật có trong các giao tác. ¨ BB) = support ({A,B}) ) = support ({A,B}) B [ s, c ]) = ) = p(p(AA¨
biểu thị số phần trăm giao tác có chứa luôn •• ĐĐộộ tin c tin cậậyy::
5
¨ ¨ ¨ ¨ ¨ ¨ B trong số những giao tác có chứa A. confidence(A A ⇒⇒ B [ s, c ] confidence( B [ s, c ]) = ) = p(B|A) ¨ B) / p( ) = B) / p(AA) = p(B|A) = = p(Ap(A¨ support({A,B}) / support({A}) support({A,B}) / support({A})
KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
s s s s s s s :: – Cao i thiểểu u s •• ĐĐộộ ủủng hng hộộ ttốối thi ⇒ ít tập phần tử (itemset) phổ biến ⇒ ít luật hợp lệ rất thường xuất hiện – Thấp ⇒ nhiều luật hợp lệ hiếm xuất hiện
g g g g g g g :: •• ĐĐộộ tin c tin cậậy ty tốối thi i thiểểu u g
– Cao ⇒ ít luật nhưng tất cả “gần như đúng" – Thấp ⇒ nhiều luật, phần lớn rất “không chắc chắn"
6
s g s s s g g g s s g g s = 2 -10 %, g g = 70 - 90 % •• GiGiáá trtrịị tiêutiêu bibiểểuu:: s
KhaiKhai phpháá ddữữ liliệệuu
2
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
•• GiaoGiao ttáácc::
Dạng kết
phần tử đơn lẻ và tập phần tử – Dạng quan hệ
7
ngưỡng cho support : s Support của tập I: số lượng giao tác có chứa I •• Support Min Support s •• Min Support •• TTậậpp phphầầnn ttửử phphổổ bibiếếnn:: có độ ủng hộ (support) ‡
KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt kkếếtt hhợợpp: : CơCơ ssởở
100 200 400 500
A,B,C A,C A,D B,E,F
Tập phổ biến {A} {B} and {C} {D}, {E} and {F} {A,C} Các cặp khác
Độ tin cậy 3 or 75% 2 or 50% 1 or 25% 2 or 50% max 25%
•• ChoCho: : (1) CSDL các giao tác, (2) mỗi giao tác là một danh sách mặt hàng được mua (trong một lượt mua của khách hàng) ID của giao tác Hàng mua
8
•• TTììmm: : ttấấtt ccảả luật có support >= minsupport • If min. support 50% and min. confidence 50%, then A A ⇒⇒ CC [50%, 66.6%], C C ⇒⇒ AA [50%, 100%]
KhaiKhai phpháá ddữữ liliệệuu
TTạạoo luluậậtt kkếếtt hhợợpp
•• QuQuáá trtrììnhnh haihai bubuớớcc đđểể khaikhai ththáácc luluậậtt kkếếtt hhợợpp::
BƯBƯỚỚC 1C 1: : TTììmm ccáácc ttậậpp phphổổ bibiếếnn: : ccáácc ttậậpp ccáácc phphầầnn ttửử ccóó đđộộ support support ttốốii thithiểểuu.. – Mẹo Apriori: Tập con của tập phổ biến cũng là một tập phổ biến: • ví dụ, nếu {AB} là một tập phổ biến thì cả {A} và {B} đều là
những tập phổ biến
– Lặp việc tìm tập phổ biến với kích thước từ 1 đến k (tập có kích
thước k)
BƯBƯỚỚC 2C 2: : DDùùngng ccáácc ttậậpp phphổổ bibiếếnn đđểể ttạạoo ccáácc luluậậtt kkếếtt hhợợpp..
9
KhaiKhai phpháá ddữữ liliệệuu
3
CCáácc ttậậpp phphổổ bibiếếnn vvớớii mmẹẹoo Apriori Apriori
Ck được tạo bằng cách kết Lk-1 với chính nó Những tập kích thước (k-1) không phổ biến
•• BưBướớcc kkếếtt hhợợpp: •• BưBướớcc rrúútt ggọọnn:
không thể là tập con của tập phổ biến kích thước k
•• MãMã gigiảả:
Ck: Tập ứng viên có kích thước k; Lk : Tập phổ biến có kích
thước k
; k++) do begin
L1 = {các phần tử phổ biến}; for (k = 1; Lk !=˘
Ck+1 = {các ứng viên được tạo từ Lk }; for each giao tác t trong database do
tăng số đếm của tất cả các ứng viên trong Ck+1 mà được chứa trong t
return ¨
Lk+1 = {các ứng viên trong Ck+1 có độ ủng hộ tối tiểu} end k Lk;
10
KhaiKhai phpháá ddữữ liliệệuu
TTạạoo ứứngng viênviên Apriori Apriori
•• Nguyên Nguyên ttắắcc Apriori Apriori:: Những tập con của tập phổ biến cũng phải phổ biến , ace, bcdbcd}} •• LL33=={{abcabc, , abdabd, , acdacd, ace, •• TTựự kkếếtt: : LL33*L*L33
11
– abcd từ abc và abd – acde từ acd và ace •• RRúútt ggọọnn:: – acde bị loại vì ade không có trong L3 •• CC44={={abcdabcd}}
KhaiKhai phpháá ddữữ liliệệuu
VVíí ddụụ vvềề Apriori
(1/6) Apriori (1/6)
Database D Database D LL11 CC11
Tập {1} {2} {3} {5}
Độ ủng hộ 2 3 3 3
ID giao tác Phần tử 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
Tập Độ ủng hộ {1} {2} {3} {4} {5}
2 3 3 1 3
12
DuyDuyệệtt DD
KhaiKhai phpháá ddữữ liliệệuu
4
VVíí ddụụ vvềề Apriori
(2/6) Apriori (2/6)
CC22 CC22 LL22
Tập Độ ủng hộ {1 3} {2 3} {2 5} {3 5}
2 2 3 2
Tập Độ ủng hộ {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
1 2 1 2 3 2
Tập {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
13
DuyDuyệệtt DD
KhaiKhai phpháá ddữữ liliệệuu
VVíí ddụụ vvềề Apriori
(3/6) Apriori (3/6)
Tập Độ ủng hộ
CC33 LL33
{2 3 5}
2
Tập {2 3 5}
14
DuyDuyệệtt DD
KhaiKhai phpháá ddữữ liliệệuu
VVíí ddụụ vvềề Apriori
(4/6) Apriori (4/6)
12345 12345 Không giangian Không ttììmm kikiếếmm ccủủaa CSDL D CSDL D 1234 1234 1235 1235 1245 1245 1345 2345 1345 2345
123 124 125 134 135 145 234 235 245 345345 123 124 125 134 135 145 234 235 245
12 13 14 15 23 24 25 34 35 455 12 13 14 15 23 24 25 34 35 4
15
11 22 33 44 55
KhaiKhai phpháá ddữữ liliệệuu
5
VVíí ddụụ vvềề Apriori
(5/6) Apriori (5/6)
12345 12345 ÁÁpp ddụụngng mmẹẹoo Apriori Apriori trêntrên CCấấpp 11 1234 1234 1235 1235 1245 1245 1345 1345 2345 2345
123 124124 123 125 134134 125 135 145145 135 234234 245 345 235 245 345 235
12 13 1414 12 13 15 23 2424 15 23 25 3434 25 35 4545 35
16
11 22 33 44 55
KhaiKhai phpháá ddữữ liliệệuu
VVíí ddụụ vvềề Apriori
(6/6) Apriori (6/6)
12345 12345 ÁÁpp ddụụngng mmẹẹoo Apriori Apriori trêntrên CCấấpp 22 1234 1234 1235 1235 1245 1245 1345 2345 1345 2345
123 124 125 134 135 145 234 235 123 124 125 134 135 145 234 245 345 235 245 345
1212 13 1414 13 1515 23 2424 23 25 34 34 25 35 4545 35
17
11 22 33 44 55
KhaiKhai phpháá ddữữ liliệệuu
ThuThuậậtt totoáánn Apriori
Apriori đãđã đđủủ nhanh nhanh??
– Dùng các tập phổ biến kích thước (k – 1) để tạo các tập phổ biến
kích thước k ứng viên
– Duyệt database và đối sánh mẫu để đếm số lần xuất hiện của các
tập ứng viên trong các giao tác
Apriori:: •• PhPhầầnn ccốốtt lõilõi ccủủaa thuthuậậtt totoáánn Apriori
•• TTììnhnh trtrạạngng nghnghẽẽnn ccổổ chai chai ccủủaa thuthuậậtt totoáánn Apriori Apriori: : viviệệcc
• 104 tập phổ biến kích thước 1sẽ tạo ra 107 tập ứng viên kích
thước 2
• Để phát hiện một mẫu phổ biến kích thước 100, ví dụ {a1, a2,
…, a100}, cần tạo 2100 » 1030 ứng viên.
– Duyệt database nhiều lần:
• Cần duyệt (n +1 ) lần, n là chiều dài của mẫu dài nhất
18
ttạạoo ứứngng viênviên – Các tập ứng viên đồ sộ:
KhaiKhai phpháá ddữữ liliệệuu
6
ThuThuậậtt totoáánn Apriori
Apriori đãđã đđủủ nhanh nhanh??
– Đối với tiếp cận Apriori căn bản thì số lượng thuộc tính trên dòng
thường khó hơn nhiều so với số lượng dòng giao tác.
– Ví dụ:
• 50 thuộc tính mỗi cái có 1-3 giá trị, 100.000 dòng (không quá tệ) • 50 thuộc tính mỗi cái có 10-100 giá trị, 100.000 dòng (hơi tệ) • 10.000 thuộc tính mỗi cái có 5-10 giá trị, 100 rows (quá tệ...)
– Lưu ý:
• Một thuộc tính có thể có một vài giá trị khác nhau • Các thuật toán luật kết hợp có đặc trưng là xem một cặp thuộc tính-
giá trị là một thuộc tính (2 thuộc tính mỗi cái có 5 giá trị => "10 thuộc tính")
•• ThThựựcc ttếế::
19
•• CCóó mmấấyy ccááchch đđểể khkhắắcc phphụụcc vvấấnn đđềề......
KhaiKhai phpháá ddữữ liliệệuu
CCảảii thithiệệnn hihiệệuu ququảả ccủủaa TT TT Apriori Apriori
– Một tập kích thước k có hashing bucket count tương ứng nhỏ hơn
giới hạn thì không thể phổ biến.
•• ĐĐếếmm ttậậpp ddựựaa vvààoo kkỹỹ thuthuậậtt bămbăm:
– Một giao tác không chứa tập phổ biến kích thước k nào thì không
cần xét đến ở các lần duyệt tiếp tiếp theo.
•• Thu Thu nhnhỏỏ giaogiao ttáácc:
– Tập nào có khả năng phổ biến trong DB thì sẽ phổ biến trong ít
nhất một phần chia của DB.
•• ChiaChia nhnhỏỏ:
– Khai thác trên tập con của dữ liệu được cho, ngưỡng của độ ủng
hộ thấp hơn + một phương thức để xác định tính đầy đủ
20
•• LLấấyy mmẫẫuu:
KhaiKhai phpháá ddữữ liliệệuu
RRúútt ccáácc luluậậtt kkếếtt hhợợpp ttừừ ccáácc ttậậpp
•• MãMã gigiảả::
for mỗi tập phổ biến l
tạo tất cả các tập con khác rỗng s of l
for mỗi tập con khác rỗng s of l
cho ra luật "s ⇒⇒ (l-s)" nếu support(l)/support(s) ‡ min_conf", trong đó min_conf là ngưỡng độ tin cậy tối
thiểu
l = {abcabc}, subsets s = {a, b, c,
}, subsets s = {a, b, c, abab, ac,
, ac, bcbc))
•• VVíí ddụụ: : ttậậpp phphổổ bibiếếnn l = { – a ⇒⇒ b, a ⇒⇒ c, b ⇒⇒ c – a ⇒⇒ bc, b ⇒⇒ ac, c ⇒⇒ ab – ab ⇒⇒ c, ac ⇒⇒ b, bc ⇒⇒ a
21
KhaiKhai phpháá ddữữ liliệệuu
7
TTạạoo luluậậtt kkếếtt hhợợpp
– Việt tạo các tập phổ biến thì chậm (đặc biệt là các tập kích thước 2) – Việc tạo các luật kết hợp từ các tập phổ biến thì nhanh
•• GhiGhi nhnhớớ 1:1:
– Khi tạo các tập phổ biết, ngưỡng độ ủng hộ được sử dụng – Khi tạo luật kết hợp, ngưỡng độ tin cậy được sử dụng
•• GhiGhi nhnhớớ 2:2:
•• ThThựựcc ttếế, , viviệệcc ttạạoo ccáácc ttậậpp phphổổ bibiếếnn vvàà ttạạoo ccáácc luluậậtt kkếếtt
bộ nhớ chính 512 MB & Red Hat Linux release 5.0 (kernel 2.0.30)
22
hhợợpp ththậậtt ssửử chichiếếmm ththờờii giangian baobao lâulâu?? – Xét một ví dụ nhỏ trong thực tế… – Các thử nghiệm được thực hiện với Citum 4/275 Alpha server có
KhaiKhai phpháá ddữữ liliệệuu
ChChọọnn nhnhữữngng luluậậtt ttốốtt nhnhấấtt??
•• TTậậpp kkếếtt ququảả thưthườờngng rrấấtt llớớnn, , ccầầnn chchọọnn rara nhnhữữngng luluậậtt ttốốtt
(cid:1) support; và (cid:2) confidence
nhnhấấtt ddựựaa trêntrên:: – Các độ đo khách quan: Hai các đo phổ biến:
(cid:1) nó bất ngờ (gây ngạc nhiên cho user); và/hoặc (cid:2) có thể hoạt động (user có thể dùng nó để làm gì đó)
– Các độ đo chủ quan (Silberschatz & Tuzhilin, KDD95) Một luật (mẫu) là tốt nếu
23
trong ccáácc ququáá trtrììnhnh khkháámm phpháá tri •• NhNhữữngng kkếếtt ququảả nnààyy ssẽẽ đưđượợcc ddùùngng trong (KDD) tri ththứứcc (KDD) KhaiKhai phpháá ddữữ liliệệuu
LuLuậậtt Boolean
Boolean vvàà luluậậtt đđịịnhnh lưlượợngng
•• LuLuậậtt kkếếtt hhợợpp Boolean so Boolean so vvớớii đđịịnhnh lưlượợngng ((ttùùyy vvààoo loloạạii gigiáá
trtrịị đưđượợcc ddùùngng)) –– Boolean:
DMBook ⇒⇒ muamua==DBMiner
SQLServer, , muamua==DMBook
Boolean: Luật liên quan đến mối kết hợp giữa sự có xuất hiện và không xuất hiện của các phần tử (ví dụ “có mua A" hoặc “không có mua A") mua==SQLServer DBMiner [2%,60%] [2%,60%] mua(x, "SQLServer") ^ mua(x, "DMBook") fi mua(x, "DBMiner") [0.2%, 60%]
–– ĐĐịịnhnh lưlượợngng:: Luật liên quan đến mối kết hợp giữa các phần tử hay
=42..48K ⇒⇒ muamua=PC [1%, 75%] =PC [1%, 75%]
=30..39, thuthu nhnhậậpp=42..48K
thuộc tính định lượng tuổi=30..39, tuổi(x, "30..39") ^ thu nhập(x, "42..48K") fi mua(x, "PC") [1%, 75%]
24
KhaiKhai phpháá ddữữ liliệệuu
8
CCáácc luluậậtt đđịịnhnh lưlượợngng
c thuộộc tc tíính nh đđịịnh lưnh lượợng:ng: ví dụ: tuổi, thu nhập, chiều cao, •• CCáác thu cân nặng
30,5 20,3 25,8 27,0
75,4 80,0 70,3 65,2
CID 1 2 3 4
•• CCáácc thuthuộộcc ttíínhnh phânphân loloạạii:: ví dụ: màu sắc của xe chieu cao can nang thu nhap 168 175 174 170
25
VVấấnn đđềề:: có quá nhiều giá trị khác nhau cho các thuộc tính định lượng GiGiảảii phpháápp:: chuyển các thuộc tính định lượng sang các thuộc tính phân loại (chuyển qua không gian rời rạc)
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt mmộộtt chichiềềuu vvàà nhinhiềềuu chichiềềuu
•• CCáácc mmốốii kkếếtt hhợợpp mmộộtt chichiềềuu vvàà nhinhiềềuu chichiềềuu
–– MMộộtt chichiềềuu:: Các thuộc tính hoặc thuộc tính trong luật chỉ qui về
khoai tâytây chiên
một đại lượng (ví dụ, qui về “mua") chiên ⇒⇒ bbáánhnh mmìì [0.4%, 52%] BiaBia, , khoai [0.4%, 52%] mua(x, “Bia") ^ mua(x, “Khoai tây chiên") fi mua(x, “Bánh mì") [0.4%, 52%]
–– NhiNhiềềuu chichiềềuu:: Các thuộc tính hoặc thuộc tính trong luật qui vềhai hay nhiều đại lượng (ví dụ: “mua", “thời gian giao dịch", “loại khách hàng") Trong ví dụ sau là: quốc gia, tuổi, thu nhập
26
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt nhinhiềềuu chichiềềuu
quoc gia Ý Pháp Pháp Ý Ý Pháp
tuoi 50 40 30 50 45 35
thu nhap thap cao cao trung bình cao cao
CID 1 2 3 4 5 6
CCÁÁC LUC LUẬẬTT:: quốc gia = Pháp thu nhập = cao tuổi = 50
27
⇒ thu nhập = cao [50%, 100%] ⇒ quốc gia = Pháp [50%, 75%] ⇒ quốc gia = Ý [33%, 100%]
KhaiKhai phpháá ddữữ liliệệuu
9
CCáácc luluậậtt mmộộtt ccấấpp vvàà nhinhiềềuu ccấấpp
•• CCáácc mmốốii kkếếtt hhợợpp mmộộtt ccấấpp vvàà nhinhiềềuu ccấấpp
–– MMộộtt ccấấpp:: Mối kết hợp giữa các phần tử hay thuộc tính của cùng một cấp khái niệm (ví dụ cùng một cấp của hệ thống phân cấp) chiên ⇒⇒ BBáánhnh mmìì [0.4%, 52%] [0.4%, 52%] BiaBia, , Khoai
Khoai tâytây chiên
–– NhiNhiềềuu ccấấpp:: Mối kết hợp giữa các phần tử hay thuộc tính của
chiên:Estrella:Barbeque ⇒⇒ BBáánhnh mmìì
Khoai tâytây chiên:Estrella:Barbeque
:Karjala, , Khoai
nhiều cấp khái niệm khác nhau (ví dụ nhiều cấp của hệ thống phân cấp) Bia:Karjala [0.1%, 74%] [0.1%, 74%]
28
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp
•• KhKhóó ttììmm nhnhữữngng mmẫẫuu ttốốtt ởở ccấấpp ququáá ggầầnn ggốốcc –– at at too too
primitive level primitive level – độ ủng hộ cao = quá ít luật – độ ủng hộ thấp = quá nhiều luật, không tốt nhất •• TiTiếếpp ccậậnn: : suysuy luluậậnn ởở ccấấpp khkhááii niniệệmm phphùù hhợợpp •• MMộộtt ddạạngng phphổổ bibiếếnn ccủủaa tri
tri ththứứcc nnềềnn llàà mmộộtt thuthuộộcc ttíínhnh hay chi titiếếtt hhóóaa ddựựaa vvààoo câycây
ccóó ththểể đưđượợcc ttổổngng ququáátt hhóóaa hay chi khkhááii niniệệmm
•• CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp:: nhnhữữngng luluậậtt phphốốii hhợợpp ccáácc
mmốốii kkếếtt hhợợpp vvớớii câycây ccáácc khkhááii niniệệmm
29
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp
Thực phẩm
bánh mì
sữa
•• CCáácc phphầầnn ttửử thưthườờngng ttạạoo ththàànhnh ccáácc câycây phânphân ccấấpp •• CCáácc phphầầnn ttửử ởở ccấấpp ththấấpp hơnhơn đưđượợcc chocho llàà ccóó đđộộ ủủngng hhộộ ththấấpp hơnhơn
2%
trắng
lúa mì
sữa không béo
Fraser
Sunset
•• CCáácc luluậậtt vvềề ccáácc ttậậpp ởở ccáácc ccấấpp ththííchch hhợợpp ssẽẽ khkháá hhữữuu ííchch
•• CơCơ ssởở ddữữ liliệệuu giaogiao ttáácc ccóó
ththểể đưđượợcc mãmã hhóóaa ddựựaa trêntrên ccáácc chichiềềuu vvàà ccáácc ccấấpp
30
KhaiKhai phpháá ddữữ liliệệuu
10
CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp
Thực phẩm
1
2
bánh mì
sữa
ID giao tác Mat hang T1 T2 T3 T4 T5
1
{111, 121, 211, 221} {111, 211, 222, 323} {112, 122, 221, 411} {111, 121} {111, 122, 211, 221, 413}
2 2%
2 trắng
1 lúa mì
sữa không béo 1
2
Fraser
Sunset
121= sữa - 2% - Fraser
31
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp
•• TiTiếếpp ccậậnn trêntrên--xuxuốốngng, , titiếếnn theo
theo chichiềềuu sâusâu::
– Trước tiên tìm những luật mạnh ở cấp cao:
sữa fi
bánh mì [20%, 60%] – Sau đó tìm những luật “yếu hơn” ở cấp thấp hơn của chúng:
sữa 2% fi
bánh mì lúa mì [6%, 50%]
•• KhaiKhai ththáácc thay
thay đđổổii trêntrên ccáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp::
– Các luật kết hợp trên nhiều cấp khác nhau:
sữa fi
bánh mì lúa mì
– Các luật kết hợp với nhiều cây khái niệm:
sữa fi
bánh mì Wonder
32
KhaiKhai phpháá ddữữ liliệệuu
CCáácc luluậậtt kkếếtt hhợợpp nhinhiềềuu ccấấpp
•• TTổổngng ququáátt hhóóa/chuyên
a/chuyên bibiệệtt hhóóaa gigiáá trtrịị ccủủaa ccáácc thuthuộộcc
support của các luật tăng (có
ttíínhnh…… –– ......ttừừ chuyên
sang ttổổngng ququáátt:: support
support của các luật giảm (có
chuyên bibiệệtt sang thêm những luật mới hợp lệ) sang chuyên
–– ......ttừừ ttổổngng ququáátt sang
chuyên bibiệệtt:: support những luật trở thành không hợp lệ, độ ủng hộ của chúng giảm xuống nhỏ hơn ngưỡng qui định)
•• BBậậcc ququáá ththấấpp => => ququáá nhinhiềềuu luluậậtt vvàà ququáá thôthô sơsơ
Pepsi light 0.5l bottle ⇒ Taffel Barbeque Chips 200gr
hay không hay
•• BBậậcc ququáá caocao => => ccáácc luluậậtt không
Food ⇒ Clothes
33
KhaiKhai phpháá ddữữ liliệệuu
11
LLọọcc luluậậtt ththừừaa
•• CCóó nhnhữữngng luluậậtt ccóó ththểể llàà dưdư ththừừaa do do đãđã ccóó ccáácc mmốốii quanquan
hhệệ ““ttổổ tiêntiên”” gigiữữaa ccáácc phphầầnn ttửử
[độ ủng hộ = 8%, độ tin cậy = 70%]
•• VVíí ddụụ ((ssữữaa ccóó 4 4 llớớpp con): con): – sữa ⇒ bánh mì lúa mì – sữa 2% ⇒ bánh mì lúa mì [độ ủng hộ = 2%, độ tin cậy =
72%]
•• Ta Ta nnóóii luluậậtt ththứứ nhnhấấtt llàà ttổổ tiêntiên ccủủaa luluậậtt ththứứ haihai
•• MMộộtt luluậậtt llàà dưdư ththừừaa nnếếuu đđộộ ủủngng hhộộ ccủủaa nnóó ggầầnn vvớớii gigiáá
trtrịị ““mongmong đđợợii””, , ddựựaa trêntrên ttổổ tiêntiên ccủủaa luluậậtt – Luật thứa hai ở trên có thể là dư thừa
34
KhaiKhai phpháá ddữữ liliệệuu
KhaiKhai ththáácc ddựựaa trêntrên rrààngng bubuộộcc
•• KhaiKhai ththáácc ccảả gigagiga--byte
byte ddữữ liliệệuu theo
tương theo ccááchch thămthăm dòdò, , ccóó tương
ttáácc? ? – Điều này có khả thi không? - Bằng cách sử dụng tốt các ràng buộc!
trong khaikhai ththáácc ddữữ liliệệuu??
•• CCáácc loloạạii rrààngng bubuộộcc nnààoo ccóó ththểể ddùùngng trong tri ththứứcc: phân lớp, kết hợp, ….
–– RRààngng bubuộộcc ddạạngng tri –– RRààngng bubuộộcc ddữữ liliệệuu: những câu truy vấn dạng SQL
• Tìm những cặp sản phẩm được bán chung tại VanCouver tháng 12/98
–– NhNhữữngng rrààngng bubuộộcc vvềề kkííchch thưthướớc/cc/cấấpp bbậậcc:
• Có liên quan về vùng, giá, nhãn hiệu, loại khách hàng
–– NhNhữữngng rrààngng bubuộộcc vvềề ssựự hhấấpp ddẫẫnn:
• Những luật mạnh (min_support ‡ 3%, min_confidence ‡
60%)
–– NhNhữữngng rrààngng bubuộộcc luluậậtt (xem slide sau)
35
KhaiKhai phpháá ddữữ liliệệuu
RRààngng bubuộộcc luluậậtt
•• CCóó haihai loloạạii rrààngng bubuộộcc luluậậtt::
–– RRààngng bubuộộcc ddạạngng luluậậtt: : khaikhai ththáácc theo
theo siêusiêu luluậậtt (meta (meta--
rule) rule)
• Metarule: P(X, Y) ^ Q(X, W) fi lấy(X, "database systems") • Luật đối sánh: tuổi(X, "30..39") ^ thu nhập(X, "41K..60K") fi
lấy(X, "database systems").
–– RRààngng bubuộộcc trêntrên nnộộii dung
dung luluậậtt: : ttạạoo câucâu truy
truy vvấấnn ddựựaa
(Ng, et al., SIGMOD’’98)98)
trêntrên rrààngng bubuộộcc (Ng, et al., SIGMOD
• sum(LHS) < 100 ^ min(LHS) > 20 ^ count(LHS) > 3 ^ sum(RHS) >
1000
36
KhaiKhai phpháá ddữữ liliệệuu
12
RRààngng bubuộộcc luluậậtt
•• RRààngng bubuộộcc 11--bibiếến n vvàà rrààngng bubuộộcc 22--bibiếến (n (Lakshmanan Lakshmanan, ,
99): et al. SIGMOD’’99): et al. SIGMOD
– 1-biến: Ràng buộc chỉ hạn chế trên một bên (L/R) của
luật, ví dụ;
• sum(LHS) < 100 ^ min(LHS) > 20 ^ count(LHS) > 3 ^
sum(RHS) > 1000
– 2-biến: Ràng buộc hạn chế trên cả hai bên (L và R)
của luật.
• sum(LHS) < min(RHS) ^ max(RHS) < 5* sum(LHS)
37
KhaiKhai phpháá ddữữ liliệệuu
TTóómm ttắắtt
•• KhaiKhai ththáácc luluậậtt kkếếtt hhợợpp::
– Gần như là phần quan trọng nhất trong KDD – Khái niệm khá đơn giản nhưng ý tưởng của nó cung cấp cơ sở cho
những mở rộng và những phương pháp khác – Nhiều bài báo đã được công bố về đề tài này
•• ĐãĐã ccóó nhinhiềềuu kkếếtt ququảả hhấấpp ddẫẫnn
•• HưHướớngng nghiên
nghiên ccứứuu lýlý ththúú::
– Phân tích mối kết hợp trong các dạng dữ liệu khác: dữ liệu không
gian, dữ liệu đa phương tiện, dữ liệu thời gian thực, …
38
