Phương pháp khai phá dữ liệu dạng đóng và ứng dụng
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 (356.65 KB, 27 trang )
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG
NGUYỄN HỒNG HẢI
PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU DẠNG ĐÓNG
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH
Thái Nguyên - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG
NGUYỄN HỒNG HẢI
PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU DẠNG ĐÓNG
VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH
HƯỚNG DẪN KHOA HỌC
PGS.TS. NGÔ QUỐC TẠO
Thái Nguyên - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
LỜI CAM ĐOAN
Tôi xin cam đoan Luận văn “ Phƣơng pháp khai phá dữ liệu dạng đóng
và ứng dụng” là công trình nghiên cứu của riêng tôi dƣới sƣ̣ hƣớng dẫn của
PGS.TS. Ngô Quốc Tạo. Toàn bộ phần mềm do chính tôi lập trình và kiểm
thƣ̉. Tôi xin chị u trách nhiệm về lời cam đoan của mì nh .
Các số liệu và thông tin sử dụng trong luận văn này là trung thực.
Tác giả
Nguyễn Hồng Hải
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
MỤC LỤC
MỤC LỤC ...................................................................................................... i
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT .................................... iv
DANH MỤC CÁC BẢNG ............................................................................. v
DANH MỤC HÌNH VẼ ................................................................................ vi
MỞ ĐẦU ....................................................................................................... 1
Chƣơng 1: TÌM HIỂU PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU .................... 3
1.2. Khai phá dữ liệu là gì ........................................................................... 3
1.2. Ứng dụng của việc khai phá dữ liệu ..................................................... 3
1.3. Qui trình khai phá tri thức .................................................................... 4
1.3.1. Qui trình khai phá tri thức ............................................................. 4
1.3.2. Kiến trúc hệ thống khai phá dữ liệu ............................................... 5
1.4. Các nhiệm vụ chính của khai phá tri thức ............................................ 5
1.4.1. Dự đoán (predictive) ..................................................................... 5
1.4.2. Mô tả (discriptive) ......................................................................... 6
1.5. Ý tƣởng kĩ thuật khai phá tri thức ........................................................ 7
1.6. Các thách thức của khai phá tri thức .................................................... 7
1.7. Qui trình chuẩn bị dữ liệu .................................................................... 7
1.7.1. Tại sao cần chuẩn bị dữ liệu .......................................................... 7
1.7.2. Làm sạch dữ liệu ........................................................................... 8
1.7.3. Chọn lọc dữ liệu ............................................................................ 9
1.7.4. Rút gọn dữ liệu .............................................................................. 9
1.7.5. Mã hóa dữ liệu ............................................................................ 11
1.8. Tập phổ biến ...................................................................................... 11
1.8.1. Giới thiệu tập phổ biến ................................................................ 11
1.8.2. Các khái niệm cơ bản .................................................................. 12
1.8.2.1. Cho cơ sở dữ liệu giao dịch .................................................. 12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
1.8.2.2. Độ phổ biến và tập phổ biến ................................................. 13
1.8.2.3. Tính chất của tập phổ biến .................................................... 14
1.8.2.4. Tập phổ biến tối đại .............................................................. 14
1.8.2.5. Tập phổ biến đóng ............................................................... 14
1.8.2.6. Luật kết hợp .......................................................................... 15
1.8.2.7. Mô tả bài toán luật kết hợp .................................................. 15
1.9. Phân lớp dữ liệu ................................................................................. 16
1.9.1. Định nghĩa thông qua ví dụ ......................................................... 16
1.9.2. Quy trình phân lớp ...................................................................... 16
1.10. Phân cụm dữ liệu ............................................................................. 17
1.10.1. Phân cụm là gì? ......................................................................... 17
1.10.2. Phân biệt phân lớp và phân cụm ................................................ 17
1.10.3. Ứng dụng phân cụm .................................................................. 18
1.10.4. Ví dụ ......................................................................................... 19
Chƣơng 2: KHAI PHÁ TẬP PHỔ BIẾN ĐÓNG TRONG KHÔNG GIAN 2
CHIỀU VÀ KHAI PHÁ KHỐI ĐÓNG TRONG KHÔNG GIAN 3 CHIỀU 20
2.1. Tổng quan khai phá tập phổ biến đóng FCP trong không gian 2 chiều20
2.2. Mở đầu khai phá tập phổ biến đóng FCP trong không gian 2 chiều.... 20
2.3. Tiến hành khai phá tập phổ biến đóng FCP ........................................ 22
2.3.1. Sơ lƣợc về quá trình khai phá tập phổ biến đóng ......................... 22
2.3.2. Thuật toán C-Miner .................................................................... 23
2.3.2.1. Thuật toán phân cụm (thuật toán increamental k-mean) ........ 23
2.3.2.2 Quá trình chia không gian khai phá........................................ 25
2.3.2.3. Khai phá không gian con để tìm ra tập phổ biến đóng FCPs . 29
2.4. Tổng quan khai phá khối phổ biến đóng FCC trong không gian 3 chiều
................................................................................................................. 32
2.5. Mở đầu khai phá khối phổ biến đóng FCC trong không gian 3 chiều . 33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
2.6. Khai phá các lát cắt đại diện .............................................................. 36
2.6.1. Tạo ra các dàn đại diện ................................................................ 38
2.6.2. Tạo ra các tập phổ biến đóng FCP ............................................... 39
2.6.3. 3D FCC generation by post-pruning (Chiến lƣợc lƣợc bỏ các khối
đƣợc sinh ra không thỏa mãn) ............................................................... 39
2.6.4. Tính đúng đắn ............................................................................. 41
Chƣơng 3: CÀI ĐẶT THUẬT TOÁN VÀ ỨNG DỤNG ............................. 43
3.1. Cài đặt thuật toán trong không gian 2 chiều ....................................... 43
3.2. Cài đặt ứng dụng trong không gian 2 chiều ........................................ 46
3.2.1. Cơ sở dữ liệu ............................................................................... 47
3.2.2. Các bƣớc thực hiện ...................................................................... 47
3.3. Cài đặt thuật toán trong không gian 3 chiều ....................................... 50
3.4. Cài đặt ứng dụng trong không gian 3 chiều ........................................ 55
3.4.1. Cơ sở dữ liệu ............................................................................... 55
3.4.2. Các bƣớc thực hiện ...................................................................... 55
KẾT LUẬN .................................................................................................. 59
TÀI LIỆU THAM KHẢO ............................................................................ 61
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
Các từ viết tắt
Nghĩa tiếng anh
Nghĩa tiếng việt
EnumerateSubset
Liệt kê các tập con
Slice
Mặt cắt
Dàn tƣơng đƣơng với 1 tập
Slices
các mặt cắt kết hợp với
nhau.
CP
Closed pattern
Tập đóng
Không gian con đặc (trong
CS
Compact subspace
bài toán đang xét: là không
gian con mà tất cả các ô có
giá trị là “1”.
FCC
Frequent closed cube
Khổi phổ biến đóng
FCP
Frequent closed pattern
Tập phổ biến đóng
Là ngƣỡng giá trị Pattern
length mà các pattern phải
Minlen
thỏa mãn
Là ngƣỡng giá trị support
mà các pattern phải thỏa
Minsup
mãn
RS
Representative slices
Dàn đại diện
RSM
Representative slice Mining
Khai phá lát cắt đại diện
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
v
DANH MỤC CÁC BẢNG
Bảng 2.1 Bảng cơ sở dữ liệu ......................................................................... 21
Bảng 2.2 Ma trận rút gọn O‟......................................................................... 26
Bảng 2.3 Lát cắt ........................................................................................... 27
Bảng 2.4 Kết quả các không gian rút gọn và không gian con........................ 27
(minsup=3, minlen=2) .................................................................................. 27
Bảng 2.5 FCP (minsup=3, minle=2) ............................................................. 32
Bảng 2.6 Ma trận O trong không gian 3 chiều .............................................. 34
Bảng 2.7 Khai thác FCC (minH=minR=minC=2) ........................................ 38
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
vi
DANH MỤC HÌNH VẼ
Hình 1.1 Các bƣớc khai phá tri thức ............................................................... 4
Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu ................................................. 5
Hình 1.3 Minh họa phân cụm dữ liệu ........................................................... 18
Hình 1.4 Phân cụm các điểm trong không gian ............................................ 19
Hình 1.5 Phân cụm các ngôi nhà dựa vào khoảng cách địa lý ....................... 19
Hình 2.1 Khung khai phá.............................................................................. 22
Hình 2.2 Cây phân chia sử dụng lát cắt. ....................................................... 28
Hình 2.3 Sai sót và dƣ thừa .......................................................................... 29
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
MỞ ĐẦU
Ngày nay, cuộc cách mạng của kỹ thuật số cho phép số hóa thông tin dễ
dàng và chi phí lƣu trữ thấp.Với sự phát triển của phần mềm, phần cứng và
trang bị nhanh hệ thống máy tính trong kinh doanh. Số lƣợng dữ liệu khổng lồ
đƣợc tập trung và lƣu trữ trong cơ sở dữ liệu trên các thiết bị điện tử nhƣ: đĩa
cứng, băng từ, đĩa quang, CD-ROM,… Tốc độ tăng dữ liệu quá lớn. Từ đó
dẫn đến kết quả là sự pha trộn của kỹ thuật thống kê vào các công cụ quản trị
dữ liệu không thể phân tích đầy đủ dữ liệu rộng lớn đƣợc nữa.
Dữ liệu sau khi phục vụ cho một mục đích nào đó đƣợc lƣu lại trong kho
dữ liệu và theo ngày tháng khối lƣợng dữ liệu đƣợc lƣu trữ ngày càng lớn.
Trong khối lƣợng dữ liệu to lớn này có rất nhiều thông tin có ích mang tính
tổng quát, thông tin có tính quy luật vẫn còn đang tiềm ẩn mà chúng ta chƣa
biết. Từ khối lƣợng dữ liệu rất lớn cần có những công cụ tự động rút các
thông tin và kiến thức có ích. Một hƣớng tiếp cận có khả năng giúp các công
ty khai thác các thông tin có nhiều ý nghĩa từ các tập dữ liệu lớn đó là khai
phá dữ liệu (Data Mining).
Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với khoa học cũng nhƣ các hoạt động thực tế, trong đó khai phá
dữ liệu là một trong những lĩnh vực mang lại hiệu quả thiết thực cho con
ngƣời. Khai phá dữ liệu đã giúp ngƣời sử dụng thu đƣợc những tri thức hữu
ích từ những cớ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Luận văn đề
cập đến các khái niệm và vấn đề cơ bản trong Khai phá tri thức và Khai phá
dữ liệu, ngoài ra luận văn còn đề cập đến phƣơng pháp khai phá dữ liệu dạng
đóng đƣợc áp dụng trong nhiều lĩnh vực thực tiễn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
data error !!! can't not
read....
