Luật kết hợp mờ và ứng dụng đối với một số bài toán dự báo

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

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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

BÙI VĂN THẮNG

LUẬT KẾT HỢP MỜ VÀ ỨNG DỤNG

ĐỐI VỚI MỘT SỐ BÀI TOÁN DỰ BÁO

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2014

i

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

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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

BÙI VĂN THẮNG

LUẬT KẾT HỢP MỜ VÀ ỨNG DỤNG

ĐỐI VỚI MỘT SỐ BÀI TOÁN DỰ BÁO

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: TS. VŨ VINH QUANG

THÁI NGUYÊN - 2014

ii

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

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

trực tiếp của TS. Vũ Vinh Quang.

Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệu tham

khảo theo đúng qui định.

Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu

hoàn toàn trách nhiệm.

Thái Nguyên, ngày27tháng8năm 2014

Tác giả

Bùi Văn Thắng

iii

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

MỤC LỤC

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

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

CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ....................................................................... iii

DANH MỤC BẢNG .....................................................................................................iv

DANH MỤC HÌNH VẼ.................................................................................................v

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

CHƢƠNG 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ KHAI PHÁ DỮ LIỆU............3

1.1. Khái niệm cơ bản về khai phá dữ liệu...............................................................3

1.1.1. Giới thiệu.....................................................................................................3

1.1.2. Khái niệm khai phá dữ liệu .........................................................................4

1.2. Một số hƣớng nghiên cứu trong khai phá dữ liệu ............................................5

1.2.1. Một số hướng nghiên cứu ...........................................................................5

1.2.2. Các dạng dữ liệu có thể khai phá ................................................................8

1.3. Nhiệm vụ chính của khai phá dữ liệu................................................................8

1.3.1. Phân lớp (Classification).............................................................................9

1.3.2. Hồi quy (Regression) ..................................................................................9

1.3.3. Khai phá luật kết hợp (Association rule) ....................................................9

1.3.4. Gom nhóm (Clustering) ..............................................................................9

1.3.5. Tổng hợp (Summarization).......................................................................10

1.3.6. Mô hình ràng buộc (Dependency modeling) ............................................10

1.3.7. Dò tìm biến đổi và độ lệch (Change and Deviation Dectection) ..............10

1.4. Bài toán khai phá luật kết hợp.........................................................................10

1.4.1. Bài toán .....................................................................................................10

1.4.2. Một số thuật toán cơ bản...........................................................................15

1.5. Logic mờ.............................................................................................................23

1.5.1. Định nghĩa tập mờ.....................................................................................23

1.5.2. Độ cao, miền xác định và miền tin cậy của tập mờ ..................................25

1.5.3. Các phép toán logic trên tập mờ................................................................26

1.5.4. Biến ngôn ngữ và giá trị của nó ................................................................27

1.6. Kết luận..............................................................................................................28

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

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

2.1. Rời rạc hóa thuộc tính dựa vào tập mờ ..........................................................30

2.1.1. Luật kết hợp với thuộc tính số...................................................................30

2.1.2. Các phương pháp rời rạc hóa ....................................................................30

2.2. Luật kết hợp mờ................................................................................................33

2.2.1. Rời rạc hóa thuộc tính mờ.........................................................................33

2.2.2. Luật kết hợp mờ ........................................................................................35

2.3. Thuật toán khai phá luật kết hợp mờ dựa trên thuật toán Apriori.............37

2.4. Khai phá luật kết hợp mờ dựa trên thuật toán Fp-Growth..........................40

2.4.1. Thuật toán xây dựng cây CUFP-Tree .......................................................40

2.4.2. Thuật toán tìm tập phổ biến FP-Growth dựa trên cậy CUFP-Tree...........41

2.5. Ví dụ thử nghiệm...............................................................................................42

2.5.1. Xây dựng cây CUFP-Tree.........................................................................42

2.5.2. Thuật toán tìm tập phổ biến ......................................................................45

2.6. Kết luận..............................................................................................................46

CHƢƠNG 3. ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG MÔ HÌNH DỰ

BÁO ..............................................................................................................................48

3.1. Mô hình một số bài toán dự báo ......................................................................48

3.1.1. Giới thiệu...................................................................................................48

3.1.2. Một mô hình dự báo là gì? ........................................................................49

3.1.3. Các kỹ thuật mô hình hóa dự báo phổ biến...............................................51

3.2. Xây dựng các luật kết hợp mờ trong mô hình dự báo...................................55

3.3. Một số kết quả thực nghiệm.............................................................................55

3.3.1. Môi trường thử nghiệm.............................................................................55

3.3.2. Kết quả thử nghiệm với CSDL gồm 20 giao dịch ....................................60

3.3.3. Kết quả thử nghiệm...................................................................................61

PHẦN KẾT LUẬN......................................................................................................62

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

iii

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

CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

CNTT Công nghệ thông tin

CSDL Cơ sở dữ liệu

KPDL Khai phá dữ liệu

KDD Knowledge Discovery in Databases

ItemSet Tập mục

Item Mục

iv

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

DANH MỤC BẢNG

Bảng 1.1: Cơ sở dữ liệu giao tác ...................................................................................11

Bảng 1.2: Kết quả thuật toán Apriori ............................................................................16

Bảng 1.3: Những biến đổi dữ liệu của FP-Growth........................................................19

Bảng 2.1: CSDL thống kế dân số của 10 gia đình [21].................................................31

Bảng 2.2: 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 ..........31

Bảng 2.3: Rời rạc hóa thuộc tính số“Tuổi" ...................................................................32

Bảng 2.4: Bảng các ký hiệu sử dụng trong thuật toán khai phá luật kết hợp mờ..........38

Bảng 2.5: Bảng các ký hiệu sử dụng trong thuật toán...................................................40

Bảng 2.6: Cơ sở dữ liệu mờ...........................................................................................42

Bảng 2.7: Kết quả sau khi thực hiện Bước 1.................................................................42

Bảng 2.8: Header_Table................................................................................................43

Bảng 2.9: CSDL mờ sau khi đã cập nhật ......................................................................43

Bảng 2.10: Tập phổ biến ...............................................................................................46

Bảng 3.1: Giao tác ví dụ trong CSDL FAM95..............................................................56

Bảng 3.2: CSDL giao tác Bảng 3.1 sau khi mờ hóa......................................................57