ng khai phá dữ liệu
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (401.93 KB, 18 trang )
1
1
Sinh viên thực hiện: Nguyễn Khắc Giáo
Lớp: ĐH KHMT1 – K1
Giáo viên hướng dẫn: PGS.TS Vũ Đức Thi
Tháng 6/2010
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
TÌM HIỂU VỀ LUẬT KẾT HỢP TRONG
KHAI PHÁ DỮ LIỆU
2
2
Nhiệm vụ của đề tài
•
Nghiên cứu vào một hướng phát triển còn mới, đầy triển
vọng : “Khai phá dữ liệu”.
•
Đi sâu vào phương pháp khai phá dữ liệu luật kết hợp
(rút quy luật, tri thức từ trong kho dữ liệu)
•
Cài đặt thành công thuật toán Apriori – thuật toán cơ
bản của phương pháp khai phá dữ liệu luật kết hợp
3
3
Chương 1: Tổng quan về khai phá dữ liệu
Định nghĩa khai phá dữ liệu: dùng để mô tả quá trình phát
hiện tri thức trong cơ sở dữ liệu.
Ứng dụng của khai phá dữ liệu: khai phá dữ liệu có nhiều
ứng dụng trong thực tế như: bảo hiểm, tài chính cổ phiếu;
thống kê, phân tích dữ liệu, hỗ trợ ra quyết định; y tế; sản xuất
chế biến; thiên văn; viễn thông
Ưu điểm của khai phá dữ liệu so với các phương pháp
khác: các phương pháp như khác (Học máy, Hệ chuyên gia,
thống kê, … ) đều gặp phải khó khăn khi CSDL vô cùng lớn.
Bài toán trên CSDL lớn khai phá dữ liệu giải quyết tốt hơn
nhiều.
4
4
Quy trình phát hiện tri thức
Bước 1: Hình thành, xác định,
định nghĩa bài toán
Bước 2: Thu thập, tiền xử lý
dữ liệu
Bước 3: Khai phá dữ liệu, rút
ra tri thức
Bước 4: Phân tích và kiểm
định kết quả.
Hình : Quy trình phát hiện tri thức
Bước 5: Sử dụng tri thức phát
hiện được
5
5
Các phương pháp khai phá dữ liệu
•
Phương pháp suy diễn/quy nạp
•
Phương pháp ứng dụng K – láng giềng
•
Phương pháp sử dụng cây quyết định và luật
•
Phương pháp phát hiện luật kết hợp
•
Và một số phương pháp khác
Trong đó phương pháp phát hiện luật kết hợp là một trong những
phương pháp quan trọng.
6
6
Chương 2: Luật kết hợp trong khai phá dữ liệu
Định nghĩa 2.1. Ký hiệu I = {I1, I2, …, Im} là tập m khoản mục
(item), một giao dịch (transaction) T được định nghĩa như một
con (subset) của các koản mục trong I (T⊆I)
Định nghĩa 2.2. Cho tập mục X ⊆ I. Ta gọi độ hỗ trợ (Support)
của X trong CSDL giao tác D, ký hiệu sup(X), là tỷ lệ phần trăm
các giao tác chứa X trên tổng các giao tác trong D.
Công thức:
7
7
Chương 2: Luật kết hợp trong khai phá dữ liệu
Định nghĩa 2.3. Cho tập mục X ⊆I và ngưỡng hỗ trợ tối thiểu
minsup (minimum support – được xác định trước bởi người sử
dụng). X được gọi là tập mục phổ biến (tập mục thường xuyên)
với độ hỗ trợ tối thiểu minsup nếu sup(X)≥minsup. Ngược lại X
gọi là tập mục không thường xuyên.
Định nghĩa 2.4. Một luật kết hợp có dạng R: X=>Y, trong X, Y
là tập các mục, X, Y ⊂ I và X∩Y=Ø. X được gọi là tiên đề và Y
được gọi là hệ quả của luật.
Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy
8
8
Chương 2: Luật kết hợp trong khai phá dữ liệu
Định nghĩa 2.5. Độ tin cậy (confidence) của một luật X => Y
được định nghĩa là khả năng giao dịch T hỗ trợ X thì cũng hỗ trợ
Y. Ký hiệu conf(X => Y )
Công thức:
Độ hỗ trợ (Support) của một luật X => Y được tính bằng độ hỗ
trợ cho tập X= X ∪Y
Sup(X=> Y) = sup(X ∪Y)
9
9
Một số tính chất của tập mục phổ biến
Tính chất 1: Độ hỗ trợ (support) cho tất cả các tập con (subset):
Cho A,B là các tập mục, nếu A⊆B thì sup(A)≥sup(B).
Tính chất 2: Mọi tập cha của tập mục không phổ biến đều là tập
không phổ biến.
Tính chất 3: Mọi tập con của tập mục phổ biến đều là tập mục
phổ biến.
10
10
Chương 3: Một số thuật toán phát hiện luật kết hợp
1. Thuật toán AIS
2. Thuật toán SETM
3. Thuật toán APRIORI
4. Thuật toán CHARM
5. Thuật toán phân hoạch
6. Thuật toán FP-growth
7.
Trong đó thuật toán Apriori là một thuật toán cơ bản quan trọng
để phát triển nhiều thuật toán khai phá dữ liệu sau này.
11
11
Thuật toán Apriori
Apriori là một giải thuật được Rakesh Agrawal, Tomasz
Imielinski, Arun Swami đề xuất lần đầu vào năm 1993. Thuật toán
tìm giao dịch t có độ hỗ trợ và độ tin cậy thỏa mãn lớn hơn một
ngưỡng giá trị nào đó.
Ý tưởng của thuật toán như sau: Sinh ra các tập mục ứng viên
từ các tập mục thường xuyên ở bước trước, sử dụng kỹ thuật
tỉa để bỏ bớt đi tập mục ứng viên không thỏa mãn ngưỡng hỗ
trợ tối thiểu cho trước. Cơ sở của kỹ thuật này là tính chất
Apriori: Bất kỳ tập con nào của tập mục thường xuyên cũng là
tập mục thường xuyên.
12
12
Thuật toán Apriori
Bước kết nối (tìm Ck): tập các k-tập mục ứng viên Ck được sinh ra
bởi việc kết nối Lk-1 với chính nó. Hai tập mục l1 và l2 của Lk-1
được kết nối nếu chúng có (k-2) mục dữ liệu đầu bằng nhau và
mục dữ liệu thứ (k-1) của l1 nhỏ hơn của l2:
(L1(1)==L2(1)&&L1(2)==L2(2)&&…&&L1(k-2)==L2(k-
2)&&L1(k-1)==L2(k-1)
Bước tỉa: Tính độ hỗ trợ của các tập mục ứng viên trong Ck, loại
bỏ tập ứng viên không thường xuyên.
Thuật toán duyệt CSDL nhiều lần. Mỗi lần duyệt, thuật toán thực
hiện hai bước: bước kết nối và bước tỉa. Trong lần lặp k, thuật toán
thực hiện:
Gọi: * Lk: là các k-tập mục thường xuyên
* Ck: là các k-tập mục ứng viên
13
13
Ví dụ cho thuật toán Apriori
Cho CSDL dưới đây, minsup =50%, minconf = 60%.Tìm luật kết hợp.
TID Tập các mục trong giao dịch
1 Bánh mì, Bơ, Trứng
2 Bơ, Sữa, Trứng
3 Bơ
4 Bánh mì, Bơ
14
14
Ví dụ cho thuật toán Apriori (tiếp)
1-tập mục Độ hỗ trợ
Bánh mì 50%
Bơ 100%
Sữa 25%
Trứng 50%
C1
1-tập mục Độ hỗ trợ
Bánh mì 50%
Bơ 100%
Trứng 50%
L1
Loại bỏ 1-
tập mục
có sup
<50%
15
15
Ví dụ cho thuật toán Apriori (tiếp)
2-tập mục Độ hỗ trợ
Bánh mì, Bơ 50%
Bánh mì, Trứng 0%
Bơ, Trứng 50%
C2
Kết nối L1 & L1 được C2
Loại bỏ 2-
tập mục
có sup
<50%
2-tập mục Độ hỗ trợ
Bánh mì, Bơ 50%
Bơ, Trứng 50%
L2
16
16
Ví dụ cho thuật toán Apriori (tiếp)
Kết nối L2 & L2 được C3 = ∅. Thuật toán dừng. Ta được tập
mục thường xuyên thỏa mãn minsup = 50% là:
X={{Bánh mì}, {Bơ}, {Trứng}, {Bánh mì, Bơ}, {Bơ,
Trứng}}
17
17
Ví dụ cho thuật toán Apriori (tiếp)
Với minconf = 60% ta có bảng luật sau:
TT Luật Độ hỗ trợ Thỏa mãn
1
Bánh mì ⇒ Bơ
50%/50% = 100% Có
2
Bơ ⇒ Bánh mì
50%/100% = 50% Không
3
Trứng ⇒Bơ
50%/100% = 50% Không
4
Bơ ⇒ Trứng
50%/50% =100% Có
18
18
Xin chân thành cảm ơn các quý thày cô
và các bạn đã chú ý theo dõi.
