Jan 26, 2015 1
Bài giảng môn: Data Mining
Bài giảng môn: Data Mining
CÁC THUẬT TOÁN KHAI
CÁC THUẬT TOÁN KHAI
THÁC LUẬT KẾT HỢP
THÁC LUẬT KẾT HỢP
Jan 26, 2015 2
Giới thiệu
Giới thiệu
Bài toán khai thác luật kết hợp được đưa ra vào
Bài toán khai thác luật kết hợp được đưa ra vào
năm 1993 bởi Agrawal được phát biểu như sau:
năm 1993 bởi Agrawal được phát biểu như sau:
Cho trước tập n danh mục mặt hàng
Cho trước tập n danh mục mặt hàng
I
I
= {
= {
i
i
1,
1,
i
i
2, …,
2, …,
i
i
n} và tập các giao dịch của các mặt hàng D trong

,
p
p
)
)
(
(
X
X⊂
⊂Y
Y
), trong đó
), trong đó
q
q
=
=
Sup
Sup
(
(
Y
Y
) được gọi là độ phổ

Jan 26, 2015 4
Tìm Tập Phổ Biến
Tìm Tập Phổ Biến
Jan 26, 2015 5
Các phương pháp tìm tập phổ biến
Các phương pháp tìm tập phổ biến
1.
1.
Phương pháp sinh ứng viên: Apriori do Agrawal đề xuất.
Phương pháp sinh ứng viên: Apriori do Agrawal đề xuất.
2.
2.
Phương pháp không sinh ứng viên:
Phương pháp không sinh ứng viên:
a) Zaki: dựa vào cây IT-tree và phần giao của các Tidset để
a) Zaki: dựa vào cây IT-tree và phần giao của các Tidset để
tính độ phổ biến.
tính độ phổ biến.
b) J. Han: dựa vào cây FP-tree để khai thác tập phổ biến.
b) J. Han: dựa vào cây FP-tree để khai thác tập phổ biến.
c) Ngoài ra, còn có một số phương pháp được đưa ra như:
c) Ngoài ra, còn có một số phương pháp được đưa ra như:
Lcm, DCI, …
Lcm, DCI, …
Jan 26, 2015
Jan 26, 2015
6
6
Các thuật toán tìm tập phổ biến
Các thuật toán tìm tập phổ biến

⊆I
I. Độ
. Độ
phổ biến của
phổ biến của
X
X
trong D, kí hiệu
trong D, kí hiệu
σ
σ
(
(
X
X
), được định
), được định
nghĩa là số giao dịch mà
nghĩa là số giao dịch mà
X
X
xuất hiện trong D.
xuất hiện trong D.
2. Định nghĩa tập phổ biến

minSup
là giá trị do người dùng chỉ định).
là giá trị do người dùng chỉ định).
Jan 26, 2015 8
Phương pháp IT-tree (tt)
Phương pháp IT-tree (tt)
3. Kết nối Galois
3. Kết nối GaloisCho quan hệ hai ngôi
Cho quan hệ hai ngôi
δ
δ⊆
⊆I
I×
×T
T

(
(
T
T
)
)
như sau:
như sau:
a)
a)
t
t
:
:
P
P
(
(
I
I
)
)
→
→
P
P
(
(
T
T

→
→
P
P
(
(
T
T
),
),
i
i
(Y) = {x
(Y) = {x
∈
∈
I
I
|
|
∀
∀
y
y
∈
∈
Y, x
Y, x
δ
δ

gồm k phần tử đầu của
X
X
và quan hệ tương
và quan hệ tương
đương dựa vào tiền tố như sau:
đương dựa vào tiền tố như sau:
Mỗi nút trên IT-tree gồm 2 thành phần Itemset-
Mỗi nút trên IT-tree gồm 2 thành phần Itemset-
Tidset X
Tidset X
×
×
t
t
(X) được gọi là
(X) được gọi là
IT-pair
IT-pair
, thực chất là
, thực chất là
một lớp tiền tố. Các nút con của X thuộc về lớp
một lớp tiền tố. Các nút con của X thuộc về lớp
tương đương của X vì chúng chia sẻ chung tiền
tương đương của X vì chúng chia sẻ chung tiền
tố X (
tố X (
t
t
(X) là tập các giao dịch có chứa X)

i
])
Delete [P
i
]
Jan 26, 2015 11
Ví dụ minh họa
Ví dụ minh họaBảng 1: CSDL mẫu
Bảng 1: CSDL mẫu
⇒
⇒
định dạng dữ liệu dọc
định dạng dữ liệu dọc
⇒
⇒t
t
(
(

) = 1345
) = 1345
∩
∩
2456 = 45
2456 = 45
Mã danh mục
Mã danh mục
Các giao dịch
Các giao dịch
chứa danh mục
chứa danh mục
A
A
1, 3, 4, 5
1, 3, 4, 5
C
C
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
D
D
2, 4, 5, 6
2, 4, 5, 6
T
T
1, 3, 5, 6
1, 3, 5, 6
W
W

D
D
,
,
W
W
3
3
A
A
,
,
C
C
,
,
T
T
,
,
W
W
4
4
A
A
,
,
C
C

D
D
,
,
T
T
Jan 26, 2015 12
Cây IT-tree với minSup = 50%(3 item)
ADx45 AWx1345
Cx123456 Dx2456 Tx1356 Wx12345
CWx12345 DTx56 DWx245 TWx135
{}x123456
Ax1345
ACTx135 ACWx1345 ATWx135
ACx1345
ATx135
ACTWx135
CDTx56 CDWx245 CTWx135
CDx2456 CTx1356
A C
AC
1234561345
1345
∩
Jan 26, 2015 13
Nhận xét
Nhận xét

Thuật toán dựa vào phần giao giữa các Tidset để
Thuật toán dựa vào phần giao giữa các Tidset để


Toán tử đóng
Toán tử đóngCho
Cho
X
X⊆
⊆I.
I.c
c
it
it
:
:
P
P
(
(
I

(
X
X
)). Ánh xạ
)). Ánh xạ
c
c
it
it
được gọi
được gọi
là toán tử đóng.
là toán tử đóng.Ví dụ
Ví dụ
:
:
c
c
it
it
(
(
AW
AW
) =
) =
i

I
I
.
.
X
X
gọi là tập đóng
gọi là tập đóng
⇔
⇔c
c
it
it
(
(
X
X
) =
) =
X
X
.
.
Ví dụ
Ví dụ
: xét CSDL ở bảng 1 ta có
: xét CSDL ở bảng 1 ta có

ACW⇒
⇒AW
AWkhông phải là tập
không phải là tập
đóng
đóng
.
.
•
Do
Do
c
c
it
it
(
(
ACW
ACW
) =
) =

.
.
Jan 26, 2015 15
Các tính chất của IT-pair
Các tính chất của IT-pair
Định lý 1:
Định lý 1:
Cho X
Cho X
i
i
×
×
t(X
t(X
i
i
) và X
) và X
j
j
×
×
t(X
t(X
j
j
) là hai thành viên
) là hai thành viên
tùy ý của lớp tương được [P]. Ta có 4 tính chất

∪
X
X
j
j
)
)
2.
2.
Nếu t(X
Nếu t(X
i
i
)
)
⊂
⊂
t(X
t(X
j
j
) thì c(X
) thì c(X
i
i
)
)
≠
≠
c(X

)
⊃
⊃
t(X
t(X
j
j
) thì c(X
) thì c(X
i
i
)
)
≠
≠
c(X
c(X
j
j
)
) nhưng c(X
nhưng c(X
j
j
) = c(X
) = c(X
i

i
∪
∪
X
X
j
j
)
)
Jan 26, 2015 16
Nhận xét về IT-pair
Nhận xét về IT-pair
1.
1.
Tính chất 1 nói rằng, nếu phần giao của hai Tidset
Tính chất 1 nói rằng, nếu phần giao của hai Tidset
bằng nhau thì |t(X
bằng nhau thì |t(X
i
i
)|=|t(X
)|=|t(X
j
j
)|=|t(X
)|=|t(X
i
i
∪
∪

i
i
∪
∪
X
X
j
j
nên X
nên X
i
i
,X
,X
j
j
không là tập
không là tập
đóng.
đóng.
2. Theo tính chất 2, ta có c(X
2. Theo tính chất 2, ta có c(X
i
i
) = c(X
) = c(X
i
i
∪
∪

và
vàX
X
j
j
thuộc về 2 tập đóng khác nhau.
thuộc về 2 tập đóng khác nhau.
3. Tương tự tính chất 2.
3. Tương tự tính chất 2.
4. Theo tính chất 4, X
4. Theo tính chất 4, X
i
i
,
,X
X
j
j
và X
và X
i
i
∪
∪

return C
CHARM-EXTEND([P], C)
for each l
i
×t(l
i
) in [P] do
P
i
= P
i
∪ l
j
and [P
i
] = ∅
for each l
j
×t(l
j
) with j > i do
Y =t(l
i
) ∩t(l
j
)
CHARM-PROPERTY(X×Y,l
i
,l
j

i
= P
i
∪ l
j
elseif t(l
i
) ⊂ t(l
j
) then
P
i
= P
i
∪ l
j
elseif t(l
i
) ⊃ t(l
j
) then
Remove l
j
from [P]
Add X ×Y to [P
i
]
else
Add X ×Y to [P
i

FI
⇒
⇒
không gian bộ nhớ yêu cầu cho quá trình gọi đệ qui sẽ nhỏ
không gian bộ nhớ yêu cầu cho quá trình gọi đệ qui sẽ nhỏ
hơn.
hơn.
Jan 26, 2015 20

Mục tiêu xây dựng dàn: nhằm tăng tốc độ khai thác luật.
Mục tiêu xây dựng dàn: nhằm tăng tốc độ khai thác luật.
Xây dựng dàn (Building Lattice)
Xây dựng dàn (Building Lattice)
Jan 26, 2015 21
Định nghĩa: chặn trên, chặn dưới
Định nghĩa: chặn trên, chặn dưới
Gọi (
Gọi (
P,
P,
≤
≤
) là tập hợp thứ tự với quan hệ hai ngôi
) là tập hợp thứ tự với quan hệ hai ngôi
≤
≤
và
và
S
S

(
(
chặn dưới
chặn dưới
) của
) của
S
S
nếu
nếu
s
s≤
≤u
u
(
(
s
s≥
≥
S
.
.

Chặn dưới lớn nhất
Chặn dưới lớn nhất
gọi là
gọi là
meet
meet
của
của
S
S
, kí hiệu
, kí hiệu
∧
∧
S
S
.
.

Nếu S = {x,y} ta viết x
Nếu S = {x,y} ta viết x
∨
∨
y cho
y cho
join

Y
Y
1
1
)
)
∧
∧
(X
(X
2
2
×
×
Y
Y
2
2
) =
) =
c
c
it
it
(X
(X
1
1
∪
∪

Y
1
1
)
)
∨
∨
(X
(X
2
2
×
×
Y
Y
2
2
) =
) =
c
c
ti
ti
(X
(X
1
1
∩
∩
X

≤
) là một
) là một
dàn
dàn
nếu
nếu
∀
∀
x,y
x,y
∈
∈
L
L
, x
, x
∨
∨
y
y
và x
và x
∧
∧
y luôn luôn tồn tại.
y luôn luôn tồn tại.

L
L

.
.

Mọi
Mọi
dàn hữu hạn
dàn hữu hạn
đều là
đều là
dàn hoàn chỉnh
dàn hoàn chỉnh
(Davey và
(Davey và
Priestley, 1990).
Priestley, 1990).

Gọi
Gọi
P
P
là tập tất cả các tập con của
là tập tất cả các tập con của
S
S
. Một tập thứ
. Một tập thứ
tự (
tự (
P
P

P
(
(
I
I
)
)
,
,
⊆
⊆
), tập tất cả các
), tập tất cả các
itemset có thể và (
itemset có thể và (
P
P
(
(
T
T
)
)
,
,
⊆
⊆
), tập tất cả các Tidset có
), tập tất cả các Tidset có
thể cũng là

∪
∪
Y và Y
Y và Y
⊂
⊂
X
X
∪
∪
Y nên nút dàn {X
Y nên nút dàn {X
∪
∪
Y}
Y}
là nút dàn con(trực tiếp) của hai nút dàn {X}, {Y}.
là nút dàn con(trực tiếp) của hai nút dàn {X}, {Y}.

Thuật toán duyệt theo chiều sâu: do đó, có thể tồn
Thuật toán duyệt theo chiều sâu: do đó, có thể tồn
tại nút con của {X} ở các nhánh con bên trái nó. Ví
tại nút con của {X} ở các nhánh con bên trái nó. Ví
dụ: xét X = ATW ở mức 3, ta thấy trên cây có chứa
dụ: xét X = ATW ở mức 3, ta thấy trên cây có chứa
nút dàn {ACTW} ở mức 4 là con trực tiếp của {X}
nút dàn {ACTW} ở mức 4 là con trực tiếp của {X}
⇒
⇒


I
} với các nút con của
} với các nút con của
nút con
nút con
l
l
i
i
.
.
LATTICE_FI ( )
l
r
= ∅
[∅]={l
i
×t(l
i
):l
i
∈I ∧Sup(l
i
)≥ minSup}
for all l
i
∈ [∅] do
l
r
.AddChildren ({l

},{I})
{l
i
}.AddChildren ({I})
{l
j
}.AddChildren ({I})
ENUMERATE_LATTICE([P
i
])
UPDATE_LATTICE({l
i
}, {I})
for all {lc} ∈ {l
i
}.Children do
for all {lcc} ∈{lc}.Children do
if lcc ⊃ I then
{I}.AddChildren({lcc})
Thuật toán xây dựng dàn
Thuật toán xây dựng dàn