Kết luận
Luận văn đã giới thiệu một sốkỹthuật đánh giá luật dựa trên lý thuyết tập
thô thông qua 3 độ đo: RIM, RAM, ERIM và đềxuất 2 độ đo mới WAERIM
và AIERIM đểgiải quyết hạn chếcủa độ đo ERIM.
Vì các rút gọn chứa các thuộc tính tiêu biểu nên những luật phát sinh từcác
rút gọn là những tri thức tiêu biểu cho toàn bộCSDL. Ứng với mỗi rút gọn ta
có một tập luật, một luật được xem là quan trọng nếu nó xuất hiện thường
xuyên trong các tập luật, độ đo RIM của một luật chính là tỉlệgiữa sốlượng
các tập luật chứa luật này so với tổng sốlượng các tập luật. Độ đo RIM dùng
để đánh giá mức độquan trọng của một luật và so sánh tầm quan trọng của nó
với các luật khác. Đây là một độ đo khách quan, đơn giản và tính toán khá dễ
dàng.
Độ đo RAM được đềxuất đểrút trích những luật quan trọng nhất từtập luật
dù độ đo này không có một giá trịtượng trưng cụthể. Bằng cách xem luật như
thuộc tính, độ đo này xây dựng lại bảng quyết định mới và tìm rút gọn của bảng
quyết định mới này, vì rút gọn chứa những thuộc tính tiêu biểu nên các rút gọn
của bảng quyết định mới chính là những luật tiêu biểu nhất cho toàn bộdữliệu.
Độ đo ERIM là độ đo chủquan vì giá trịcủa độ đo này được tính toán dựa
trên trọng sốcủa các thuộc tính được đánh giá bởi các chuyên gia. Từtập luật
RIM – tập luật thu được từ độ đo RIM – ta tính toán giá trịERIM cho từng
luật, những luật có giá trị độ đo RIM và ERIM cao được xem là quan trọng.
Tuy nhiên hạn chếcủa độ đo ERIM là phụthuộc vào sốlượng các thuộc tính
điều kiện trong luật, do đó luận văn đềxuất độ đo WAERIM nhưlà giải pháp
thay thếERIM.
Việc sửdụng trọng sốcủa các thuộc tính điều kiện trong quá trình đánh giá
luật giúp người dùng có thểchọn ra những luật thực sự đáng tin cậy vì các
trọng sốnày chính là ý kiến nhận định của các chuyên gia trong cùng lĩnh vực
(ERIM, WAERIM). Tuy nhiên đối với những ứng dụng không được các
chuyên gia đánh giá thì việc đánh giá tầm quan trọng của luật theo độ đo này
mang lại hiệu quảthấp, vì vậy song song với độ đo WAERIM luận văn đềxuất
độ đo AIERIM, độ đo này cũng cải tiến độ đo RIM dựa vào mức độquan trọng
của các thuộc tính điều kiện. Khác với ERIM và WAERIM, mức độquan trọng
các thuộc tính điều kiện ở độ đo AIERIM có được từchính nguồn dữliệu dùng
đểkhai phá.
Khảnăng đánh giá luật của các độ đo này được chứng minh bằng thử
nghiệm thực tếtrên 2 nguồn dữliệu Nursery và BankLoan. Cũng nhưcác độ đo
hữu ích, các độ đo dựa trên lý thuyết tập thô không phải là sựchọn lựa tốt nhất
cho tất cảcác ứng dụng, mỗi độ đo đều có những mặc hạn chếnhất định và
trong một sốtrường hợp nó không mang lại kết quảnhưmong đợi.
Hướng phát triển
- Mởrộng kỹthuật đánh giá luật bằng cách kết hợp các độ đo đã được đề
xuất, chẳng hạn kết hợp WAERIM với Confidence, AIERIM với
Support, hay sửdụng tập luật RIM đểxây dựng lại bảng quyết định mới
và tìm các luật quan trọng theo độ đo RAM
- Tiếp tục tìm hiểu các độ đo khác kết hợp giữa độ đo chủquan và khách
quan để đưa ra nhiều kỹthuật đánh giá luật hỗtrợviệc chọn lựa những
tri thức thực sựcó ích trong quá trình khai thác dữliệu.
79 trang |
Chia sẻ: tuandn | Lượt xem: 2665 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Một số kỹ thuật đánh giá luật dựa trên lý thuyết tập thô, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN THỊ LY SA
MỘT SỐ KỸ THUẬT ĐÁNH GIÁ LUẬT
DỰA TRÊN LÝ THUYẾT TẬP THÔ
LUẬN VĂN THẠC SĨ
NGÀNH KHOA HỌC MÁY TÍNH
Thành phố Hồ Chí Minh - 2010
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN THỊ LY SA
MỘT SỐ KỸ THUẬT ĐÁNH GIÁ LUẬT
DỰA TRÊN LÝ THUYẾT TẬP THÔ
Chuyên ngành: Khoa học máy tính
LUẬN VĂN THẠC SĨ
HƯỚNG DẪN KHOA HỌC
TS. VŨ THANH NGUYÊN
Thành phố Hồ Chí Minh - 2010
i
NHẬN XÉT CỦA CÁN BỘ HƯỚNG DẪN
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
TP Hồ Chí Minh, ngày …….tháng …… năm 2010
Cán bộ hướng dẫn
TS. Vũ Thanh Nguyên
ii
NHẬN XÉT CỦA CÁN BỘ PHẢN BIỆN
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
...............................................................................................................................
TP Hồ Chí Minh, ngày …….tháng …… năm 2010
Cán bộ phản biện
iii
MỤC LỤC
Trang
NHẬN XÉT CỦA CÁN BỘ HƯỚNG DẪN ................................................................ I
NHẬN XÉT CỦA CÁN BỘ PHẢN BIỆN .................................................................. II
MỤC LỤC ...................................................................................................................III
DANH MỤC CÁC BẢNG ......................................................................................... VI
DANH MỤC CÁC HÌNH..........................................................................................VII
DANH MỤC CÁC TỪ VIẾT TẮT ..........................................................................VIII
CHƯƠNG 1. GIỚI THIỆU.........................................................................................1
1.1. KHAI PHÁ DỮ LIỆU .........................................................................................1
1.2. LUẬT KẾT HỢP.................................................................................................2
1.3. LÝ THUYẾT TẬP THÔ .....................................................................................2
1.4. ĐÁNH GIÁ LUẬT..............................................................................................3
1.5. TÓM LẠI ............................................................................................................4
CHƯƠNG 2. KIẾN THỨC CƠ BẢN.........................................................................5
2.1. LÝ THUYẾT TẬP THÔ .....................................................................................5
2.1.1. Các khái niệm ..............................................................................................5
2.1.2. Thuật toán tìm các rút gọn .........................................................................12
2.1.3. Thuật toán tìm rút gọn tối ưu .....................................................................16
2.1.4. Tập thô và rời rạc hóa dữ liệu ....................................................................17
2.2. PHÁT SINH LUẬT KẾT HỢP .........................................................................23
2.2.1. Giới thiệu ...................................................................................................23
2.2.2. Khai thác tập phổ biến ...............................................................................23
2.2.3. Khai thác luật kết hợp từ tập phổ biến .......................................................28
2.2.4. Sử dụng luật kết hợp vào việc phân lớp.....................................................30
CHƯƠNG 3. CÁC PHƯƠNG PHÁP ĐÁNH GIÁ LUẬT DỰA TRÊN LÝ
THUYẾT TẬP THÔ..................................................................................................32
3.1. ĐỘ ĐO SỰ HỮU ÍCH CỦA LUẬT ..................................................................32
3.1.1. Độ hỗ trợ ...................................................................................................33
3.1.2. Độ tin cậy ..................................................................................................33
3.1.3. Độ đo Lift...................................................................................................34
iv
3.1.4. Độ đo Laplace ............................................................................................34
3.1.5. Độ chắc chắn .............................................................................................35
3.1.6. Độ đo Leverage..........................................................................................35
3.1.7. Độ đo Correlation ......................................................................................35
3.1.8. Độ đo Jaccard.............................................................................................36
3.1.9. Độ đo Cosine..............................................................................................36
3.1.10. Độ đo Odds Ratio.....................................................................................36
3.1.11. Rule Template..........................................................................................36
3.2. ĐỘ ĐO TẦM QUAN TRỌNG CỦA LUẬT .....................................................38
3.2.1. Các định nghĩa ...........................................................................................38
3.2.2. Một ví dụ về độ đo RIM ............................................................................39
3.2.3. Nhận xét về độ đo RIM..............................................................................40
3.3. ĐỘ ĐO XEM LUẬT NHƯ THUỘC TÍNH.......................................................41
3.3.1. Xây dựng bảng quyết định mới..................................................................41
3.3.2. Các định nghĩa ...........................................................................................43
3.3.3. Một ví dụ về độ đo RAM...........................................................................43
3.3.4. Nhận xét giữa hai độ đo RIM và độ đo RAM............................................44
3.4. ĐỘ ĐO TẦM QUAN TRỌNG CẢI TIẾN ........................................................45
3.4.1. Định nghĩa..................................................................................................45
3.4.2. Quá trình thực hiện ....................................................................................45
3.4.3. Một ví dụ về độ đo ERIM..........................................................................46
3.4.4. Nhận xét về độ đo ERIM ...........................................................................47
3.5. ĐỘ ĐO WAERIM.............................................................................................47
3.5.1. Định nghĩa..................................................................................................48
3.5.2. Quá trình thực hiện ....................................................................................48
3.6. ĐỘ ĐO AIERIM ...............................................................................................49
3.6.1. Định nghĩa..................................................................................................49
3.6.2. Một ví dụ về độ đo AIERIM......................................................................50
CHƯƠNG 4. XÂY DỰNG ỨNG DỤNG SO SÁNH KỸ THUẬT ĐÁNH GIÁ
LUẬT GIỮA CÁC ĐỘ ĐO.......................................................................................51
4.1. GIỚI THIỆU .....................................................................................................51
4.1.1. Nguồn dữ liệu “Nursery” ...........................................................................51
4.1.2. Nguồn dữ liệu “BankLoan” .......................................................................52
v
4.2. MÔ HÌNH XÂY DỰNG ỨNG DỤNG .............................................................54
4.3. KẾT QUẢ SO SÁNH GIỮA CÁC ĐỘ ĐO.......................................................55
4.3.1. Sử dụng nguồn “Nursery”..........................................................................55
4.3.2. Sử dụng nguồn “BankLoan”......................................................................56
4.3.3. Kết luận......................................................................................................57
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN................................................................65
TÀI LIỆU THAM KHẢO.........................................................................................67
vi
DANH MỤC CÁC BẢNG
Bảng 2.1. Một ví dụ về Hệ thông tin ................................................................................... 5
Bảng 2.2. Một ví dụ về Bảng quyết định ............................................................................. 6
Bảng 2.3. Ma trận khả phân xây dựng từ Bảng 2.2.......................................................... 11
Bảng 2.4. Một ví dụ về Bảng quyết định ........................................................................... 11
Bảng 2.5. Ma trận khả phân xây dựng từ Bảng 2.4.......................................................... 12
Bảng 2.6. Quá trình rời rạc hoá ....................................................................................... 18
Bảng 2.7. Bảng quyết định mới ∗T ................................................................................... 21
Bảng 2.8. Kết quả rời rạc hóa dữ liệu .............................................................................. 23
Bảng 2.9. Ví dụ về cơ sở dữ liệu dạng giao dịch .............................................................. 24
Bảng 2.10. Một ví dụ về tập phổ biến ............................................................................... 24
Bảng 2.11. Luật kết hợp thỏa minSupp=50%, minConf=80% ......................................... 29
Bảng 3.1. Ví dụ cho mẫu luật............................................................................................ 37
Bảng 3.2. Một số rút gọn từ nguồn Zoo............................................................................ 39
Bảng 3.3. Tập luật quan trọng theo độ đo RIM từ nguồn Zoo.......................................... 40
Bảng 3.4. Bảng quyết định ví dụ cho độ đo RAM ............................................................. 42
Bảng 3.5. Xây dựng bảng quyết định mới ......................................................................... 43
Bảng 3.6. Các luật kết hợp từ nguồn Lenses với minSupp=3% và minConf=70%.......... 44
Bảng 3.7. Tập luật quan trọng theo độ đo RAM từ nguồn Lenses.................................... 44
Bảng 3.8. Trọng số cho từng thuộc tính điều kiện của nguồn Car ................................... 46
Bảng 3.9. Tập luật với độ đo ERIM từ nguồn Car............................................................ 46
Bảng 3.10. Mức độ quan trọng của các tập thuộc tính trên nguồn Car ........................... 50
Bảng 3.11. Tập luật với độ đo AIERIM từ nguồn Car...................................................... 50
Bảng 4.1. Các thuộc tính của nguồn Nursery ................................................................... 51
Bảng 4.2. Các thuộc tính của dữ liệu BankLoan .............................................................. 52
Bảng 4.3. Trọng số các thuộc tính điều kiện của BankLoan ............................................ 53
Bảng 4.4. Kết quả 10 lần thử nghiệm với Nursery ........................................................... 60
Bảng 4.5. Kết quả 10 lần thử nghiệm với BankLoan (trường hơp 1) ............................... 62
Bảng 4.5. Kết quả 10 lần thử nghiệm với BankLoan (trường hơp 2) ............................... 64
vii
DANH MỤC CÁC HÌNH
Hình 1.1. Quá trình phát hiện tri thức ................................................................................ 1
Hình 2.1. Tập các điểm cắt trên thuộc tính a.................................................................... 19
Hình 2.2. Tập các điểm cắt cực tiểu ................................................................................. 22
Hình 2.3. Cây tìm kiếm IT-tree ......................................................................................... 26
Hình 2.4. Cây tìm kiếm tập phổ biến với minSupp=50% ................................................. 27
Hình 4.1. Mô hình xây dựng ứng dụng ............................................................................. 54
Hình 4.2. Biểu đồ so sánh giữa các độ đo từ nguồn Nursery ........................................... 55
Hình 4.3. Biểu đồ so sánh giữa các độ đo từ nguồn BankLoan (trường hợp 1)............... 56
Hình 4.4. Biểu đồ so sánh giữa các độ đo từ nguồn BankLoan (trường hợp 2)............... 57
viii
DANH MỤC CÁC TỪ VIẾT TẮT
AIERIM Attributes Importance Degree Based Enhanced Rule
Importance Measure
CBA Classification Based on Associations
CSDL Cơ Sở Dữ Liệu
ERIM Enhanced Rule Importance Measure
IT-pair Itemset-Tidset pair
IT-tree Itemset-Tidset tree
KDD Knowledge Discovery in Database
RIM Rule Importance Measure
RAM Rule-as-Attribute Measure
WAERIM Weight Average Based Enhanced Rule Importance
Measure
1
Chương 1. GIỚI THIỆU
1.1. KHAI PHÁ DỮ LIỆU
Phát hiện tri thức trong cơ sở dữ liệu (KDD-Knowledge Discovery in
Database) là quá trình tìm kiếm những thông tin ẩn có giá trị từ tập dữ liệu lớn,
là quá trình hoạt động tương tác giữa con người và cơ sở dữ liệu với sự hỗ trợ
của công cụ tin học để chọn ra những tri thức có ích phục vụ cho một mục đích
nhất định trong một lĩnh vực nhất định. Khai phá dữ liệu (Data Mining) là một
trong những hoạt động của quá trình phát hiện tri thức, là kỹ thuật chính giúp ta
lấy được các tri thức hữu ích, quan trọng.
Quá trình phát hiện tri thức có thể được biểu diễn bằng Hình 1.1:
Hình 1.1. Quá trình phát hiện tri thức
Hiện nay trên thế giới đã có nhiều ngành công nghiệp sử dụng kỹ thuật khai
phá dữ liệu để phục vụ cho các hoạt động kinh doanh của mình và bước đầu
thành công như ngành tài chính, y học, bảo hiểm, sản xuất… Mặc dù kỹ thuật
khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm nhưng với những tri
thức mà nó đem lại cũng đã chứng tỏ khai phá dữ liệu có một tiềm năng to lớn
trong việc tạo ra những lợi nhuận đáng kể trong nền kinh tế.
Các hướng tiếp cận khai phá dữ liệu phổ biến đang được nghiên cứu và sử
dụng hiện nay: mạng nơron, kỹ thuật phân cụm và phân đoạn, phương pháp
Xác định mục tiêu
Thu thập và tiền xử lý
dữ liệu
KHAI PHÁ DỮ LIỆU
(Triết xuất tri thức)
Phát biểu kết quả và
đánh giá
Sử dụng tri thức đã phát
hiện được
2
láng giềng gần nhất, giải thuật di truyền, phương pháp phát hiện luật kết hợp…
Trong đó, các hướng tiếp cận khai phá luật kết hợp: luật kết hợp nhị phân, luật
kết hợp mờ, luật kết hợp nhiều mức, luật kết hợp tiếp cận theo hướng tập thô,
luật kết hợp với các thuộc tính được đánh trọng số…
Luận văn này tập trung vào kỹ thuật phát hiện luật kết hợp theo hướng tiếp
cận tập thô trong quá trình khai phá dữ liệu, tiếp theo đó giới thiệu những kỹ
thuật đánh giá luật dựa trên cơ sở lý thuyết tập thô để rút trích những luật quan
trọng và có ích để tri thức phát hiện được thật sự có ý nghĩa cho ứng dụng.
1.2. LUẬT KẾT HỢP
Luật kết hợp là lĩnh vực quan trọng trong khai phá dữ liệu, là kỹ thuật khai
phá dữ liệu khá đơn giản nhưng thiết thực. Phát hiện luật kết hợp giúp ta tìm ra
được các mối liên quan của các thành phần trong dữ liệu. Chẳng hạn, từ việc
phân tích dữ liệu bán hàng của siêu thị, ta có thể phát hiện thói quen mua hàng
của khách hàng như: khi khách hàng mua bánh mì thì hầu như họ sẽ mua
sữa. Luật kết hợp có thể được sử dụng để tìm hiểu các thói quen này của khá