Hoàng Linh - Lê Mai
Hoàng Linh - Lê Mai
1
1
Khai phá dữ liệu
Khai phá dữ liệu
Các thuật toán khai phá dữ
Các thuật toán khai phá dữ
liệu và ứng dụng
liệu và ứng dụngGiáo viên hướng dẫn :
Giáo viên hướng dẫn : PGS.TSKH Nguyễn Xuân Huy
PGS.TSKH Nguyễn Xuân Huy
Sinh viên thực hiện:
Sinh viên thực hiện: Lê Thị Mai
Lê Thị MaiPhạm Thị Hoàng Linh
Phạm Thị Hoàng LinhKhai phá dữ liệu Hoàng Linh - Lê Mai 2

Khai phá dữ liệu,
rút ra kết luận
Phân tích và
kiểm định kết quả
Sử dụng các tri thức
phát hiện được.
Khai phá dữ liệu Hoàng Linh - Lê Mai 5
Quá trình phát hiện tri thức
Quá trình phát hiện tri thức
1. Hình thành, xác định và định nghĩa bài
toán.
2. Thu thập và tiền xử lý dữ liệu.
3. Khai phá dữ liệu, rút ra các tri thức.
4. Sử dụng các tri thức phát hiện được.
Khai phá dữ liệu Hoàng Linh - Lê Mai 6

Quá trình phát hiện tri thức

Khái niệm,phương pháp khai phá dữ liệu

Khái niệm về luật kết hợp

Quy trình khai phá luật kết hợp

Thuật toán Apriori
Khai phá dữ liệu Hoàng Linh - Lê Mai 7
Khái niệm khai phá dữ liệu
Khái niệm khai phá dữ liệu
Phát hiện ra các thông tin có giá trị
tiềm ẩn trong các tập dữ liệu lớn (các

Gọi D là cơ sở dữ liệu bao gồm n giao dịch
T
∈
D hỗ trợ (support) cho một tập X ⊆ I nếu nó chứa tất cả các
khoản mục của X, nghĩa là X ⊆ T
Ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ cho X.
Khai phá dữ liệu Hoàng Linh - Lê Mai 11
Ví dụ về luật kết hợp
Ví dụ về luật kết hợp
Cho CSDL:
1- có mua sản phẩm; 0- không mua sản phẩmKhoản mục
Khoản mục
Giao dịch
Giao dịchBánh
Bánh
mì
mì
Bơ
Bơ
Phomat
Phomat
Táo
Táo
Nho

1
1
1
1
1
0
0
T4
T4
1
1
0
0
1
1
1
1
1
1
Khai phá dữ liệu Hoàng Linh - Lê Mai 12
Ví dụ về luật kết hợp
Ví dụ về luật kết hợp
Tập các khoản mục:
I = {Bánh mì, Bơ, Phomat, Táo, Nho}
D là CSDL bao gồm 4 giao dịch
D = {T1, T2, T3, T4}
Cho tập X = {Bánh mì, Phomat}
Các giao dịch không hỗ trợ cho X: T1, T3.
Các giao dịch hỗ trợ cho X: T2,T4.
Khai phá dữ liệu Hoàng Linh - Lê Mai 13

1/4
1/4
Táo
Táo
4/4 = 1
4/4 = 1
Bơ, Phomat,Bánh mì
Bơ, Phomat,Bánh mì
0/4 = 0
0/4 = 0
Khai phá dữ liệu Hoàng Linh - Lê Mai 15
Định nghĩa luật kết hợp
Định nghĩa luật kết hợp

Luật kết hợp có dạng X
⇒
Y, X, Y
⊂
I là
các tập mục gọi là itemsets, X được gọi là
tiền đề, Y là mệnh đề kết quả.

Độ hỗ trợ của luật X
⇒
Y có công thức :
Support(X) =
Support(X) =
Số lượng giao dịch hỗ trợ (X)
Số lượng giao dịch hỗ trợ (X)
Tổng số giao dịch D

Ví dụ về luật kết hợp:
Cho bảng cơ sở dữ liệu D như sau :
Mã số giao
Mã số giao
dịch
dịch
Các mặt
Các mặt
hàng
hàng
10
10
A,B,C
A,B,C
20
20
A,C
A,C
30
30
A,D
A,D
40
40
B,E,F
B,E,F
Khoản mục
Khoản mục{A, C}
{A, C}50%
50%Khai phá dữ liệu Hoàng Linh - Lê Mai 18
Ví dụ về luật kết hợp
Ví dụ về luật kết hợp
Luật kết hợp: A ⇒ C
Support = support ({A} ∩ {C}) = 50%
Cofidence = support({A}∩{C}) / support ({A})
= 66,6%.
Cho min_support = 50%, min_conf = 50% :
A ⇒ C (support = 50%, confidence = 66.6%)
C ⇒ A (support = 50%, confidence = 100%).
Khai phá dữ liệu Hoàng Linh - Lê Mai 19

Quá trình phát hiện tri thức

Khái niệm,phương pháp khai phá dữ liệu

Khái niệm về luật kết hợp

Quy trình khai phá luật kết hợp


Giới hạn của Apriori

Ví dụ minh hoạ thuật toán Apriori
Khai phá dữ liệu Hoàng Linh - Lê Mai 23
Ý tưởng của thu
Ý tưởng của thu
ậ
ậ
t toán Apriori
t toán Apriori

Tạo ra các tập phổ biến (thường xuyên) có
1 item, rồi tiếp đến là 2 items, 3 items cho
đến khi chúng ta tạo ra tập phổ biến của
mọi kích thước.

Mỗi tập item được tạo ra phải được tính toán độ hỗ trợ và độ tin
cậy.

Tập k item được tạo ra từ tập k-1 items. Tạo danh sách các item
dự kiến của tập k items bằng cách hợp từng đôi một tập k-1
items có trong danh sách.
Khai phá dữ liệu Hoàng Linh - Lê Mai 24
Triển khai thuật toán
Triển khai thuật toán
Apriori
Apriori
Qua 2 bước:

Tạo tập item phổ biến: tạo tất cả các tập item