Khai phá luật kết hợp mờ và ứng dụng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TT

---------***---------

Hoàng Thị Phượng

Khai phá luật kết hợp mờ

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 – ĐHTN http://www.lrc-tnu.edu.vn

Đại học Thái Nguyên

Trường đại học CNTT & TT

---------***---------

Hoàng Thị Phượng

Khai phá luật kết hợp mờ

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

Người hướng dẫn khoa học: PGS TS Đoàn Văn Ban

.

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

i

LỜI CAM ĐOAN

Tôi xin cam đoan, đây 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 Đoàn Văn Ban. Tất cả các nguồn tài liệu tham khảo đƣợc dùng

đều có xuất xứ rõ ràng, đƣợc trích dẫn hợp pháp.

Tôi xin chịu trách nhiệm và chịu mọi hình thức kỉ luật theo quy định cho lời

cam đoan của mình.

Thái Nguyên, 9/2011

Hoàng Thị Phƣợng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ii

MỤC LỤC

Trang phụ bìa

LỜI CẢM ƠN

LỜI CAM ĐOAN ....................................................................................................... i

MỤC LỤC.................................................................................................................. ii

CÁC KÝ HIỆU VIẾT TẮT ...................................................................................... iv

DANH MỤC CÁC BẢNG..........................................................................................v

DANH MỤC CÁC HÌNH VẼ................................................................................... vi

MỞ ĐẦU.....................................................................................................................1

CHƢƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU............................................4

1.1. Khai phá dữ liệu và phát hiện tri thức .............................................................4

1.1.1. Khai phá dữ liệu .......................................................................................4

1.1.2. Các bƣớc chính trong quá trình phát hiện tri thức....................................4

1.1.3. Khái niệm khai phá dữ liệu ......................................................................7

1.1.4. Kiến trúc của hệ thống khai thác dữ liệu.................................................8

1.2. Ứng dụng của khai phá dữ liệu......................................................................10

1.2.1. Ƣu thế của khai phá dữ liệu....................................................................10

1.2.2. Ứng dụng của khai phá dữ liệu...............................................................10

1.3. Hƣớng tiếp cận và các kỹ thuật khai phá dữ liệu...........................................11

1.3.1. Một số hƣớng tiếp cận chính của khai phá dữ liệu.................................11

1.3.2. Các phƣơng pháp khai phá dữ liệu (data mining) ..................................11

1.4. Khai phá luật kết hợp trong cơ sở dữ liệu......................................................12

1.4.1. Luật kết hợp............................................................................................12

1.4.2. Một số hƣớng tiếp cận trong khai phá luật kết hợp................................13

1.5. Phát biểu bài toán khai phá luật kết hợp........................................................15

1.5.1. Các khái niệm cơ bản .............................................................................15

1.5.2. Phát biểu bài toán luật kết hợp ...............................................................18

1.6. Thuật toán Apriori khai phá luật kết hợp.......................................................19

1.7. Luật kết hợp có thuộc tính số.........................................................................22

1.7.1 Luật kết hợp có thuộc tính số và thuộc tính các hạng mục .....................22

1.7.2. Các phƣơng pháp rời rạc hóa..................................................................23

1.8. Kết luận chƣơng 1..........................................................................................25

CHƢƠNG II KHAI PHÁ LUẬT KẾT HỢP MỜ....................................................27

2.1. Khái niệm về tập mờ (Fuzzy set)...................................................................27

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iii

2.1.1. Sơ lƣợc về tập mờ...................................................................................27

2.1.2. Định nghĩa tập mờ .................................................................................27

2.1.3. Định nghĩa hàm thuộc ...........................................................................28

2.1.4. Các phép toán cơ bản trên tập mờ ..........................................................29

2.2. Khái niệm tập mờ trong lĩnh vực khai phá dữ liệu........................................31

2.3. Áp dụng tập mờ để rời rạc hóa và các ƣu điểm.............................................31

2.4. Luật kết hợp mờ.............................................................................................34

2.5. Thuật toán khai phá luật kết hợp mờ có thuộc tính số đƣợc đánh trọng số

(David L. Olson)...................................................................................................36

2.5.1. Giới thiệu thuật toán ...............................................................................36

2.5.2. Chi tiết thuật toán ...................................................................................36

2.6. Thuật toán khai phá luật kết hợp mờ có thuộc tính số (F- APACS)..............39

2.6.1. Giới thiệu thuật toán ...............................................................................39

2.6.2 Những khái niệm .....................................................................................42

2.6.3. Thuật toán F-APACS .............................................................................46

2.6.4. Xác định luật có ích................................................................................48

2.6.5. Đo độ tin cậy của luật kết hợp................................................................49

2.7. Kết luận chƣơng II .........................................................................................51

CHƢƠNG III. CÀI ĐẶT THUẬT TOÁN F -APACS TRÊN CƠ SỞ DỮ LIỆU

CƢỚC ĐIỆN THOẠI ...............................................................................................51

3.1. Đặt vấn đề ......................................................................................................51

3.1.1. Phát hiện gian lận (fraud detection)........................................................52

3.1.2. Các ứng dụng quản lý và chăm sóc khách hàng.....................................52

3.1.3. Các ứng dụng phát hiện và cô lập lỗi trên hệ thống mạng viễn thông

(Network fault isolation) ..................................................................................54

3.2. Các dữ liệu chính trong viễn thông ...............................................................54

3.3. Cài đặt thuật toán trên cơ sở dữ liệu cƣớc điện thoại ....................................55

3.4. Kết quả cài đặt thuật toán ..............................................................................58

3.5. Kết luận chƣơng III........................................................................................65

KẾT LUẬN...............................................................................................................66

TÀI LIỆU THAM KHẢO.........................................................................................67

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iv

CÁC KÝ HIỆU VIẾT TẮT

Tên viết tắt Tên đầy đủ

CSDL Cơ sở dữ liệu

DL Dữ liệu

DM Data Mining (Khai phá dữ liệu)

KDD Knowledge discovery in database (Phát hiện tri thức

trong cơ sở dữ liệu)

KPDL Khai phá dữ liệu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

v

DANH MỤC CÁC BẢNG

Bảng 1.1. Ví dụ về một CSDL dạng giao dịch 15

Bảng 1.2. CSDL giao dịch với độ hỗ trợ 16

Bảng 1.3. Tính độ hỗ trợ và độ tin cậy 17

Bảng 1.4. Các tập phổ biến 18

Bảng 1.5. Luật kết hợp sinh từ tập phổ biến ADE 19

Bảng 1.6. Cơ sở dữ liệu chi tiết của 8 cuộc gọi điện thoại 22

Bảng 1.7. Rời rạc hóa thuộc tính số rời rạc hữu hạn hoặc thuộc tính hạng mục 24

Bảng 1.8. Rời rạc hóa thuộc tính thời gian đàm thoại (TGĐT) 24

Bảng 2.1. Cơ sở dữ liệu của 10 cuộc gọi 35