Tìm kiếm thông minh với ứng dụng của tập mờ trực cảm

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

i

ĐẠ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 TUẤN CƢỜNG

TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG

CỦA TẬP MỜ TRỰC CẢM

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

Thái Nguyên, tháng 10 năm 2013

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

i

ĐẠ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 TUẤN CƢỜNG

TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG

CỦA TẬP MỜ TRỰC CẢM

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

Giáo viên hƣớng dẫn khoa học: TS. NGUYỄN TÂN ÂN

Thái Nguyên, tháng 10 năm 2013

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

i

LỜI CAM ĐOAN

Tôi xin cam đoan toàn bộ nội dung trong luận văn này do tôi tự nghiên cứu,

đọc, dịch tài liệu, tổng hợp và thực hiện. Trong luận văn tôi có sử dụng một số tài

liệu tham khảo như đã trình bày trong phần tài liệu tham khảo.

Ngƣời viết luận văn

Nguyễn Tuấn Cƣờng

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

ii

LỜI CẢM ƠN

Đầu tiên tôi xin gửi lời cảm ơn chân thành đến thầy TS Nguyễn Tân Ân – Đại

học Sư phạm Hà Nội đã tận tình hướng dẫn, chỉ bảo cho tôi trong suốt quá trình làm

luận văn.

Tôi cũng xin gửi lời cảm ơn đến các thầy cô trường Đại học Công nghệ thông

tin và Truyền thông – Đại học Thái Nguyên, các thầy cô Viện Công nghệ thông tin

đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá trình học của mình.

Tôi cũng xin gửi lời cảm ơn tới các đồng nghiệp trong đơn vị công tác, gia

đình và bạn bè những người đã động viên tạo mọi điều kiện giúp đỡ tôi trong suốt

hai năm học.

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

iii

MỤC LỤC

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

LỜI CẢM ƠN ............................................................................................................ ii

MỤC LỤC................................................................................................................. iii

DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT............................................... iv

DANH MỤC CÁC HÌNH...........................................................................................v

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

Chƣơng 1: NHỮNG KIẾN THỨC CƠ SỞ TẬP MỜ, TẬP MỜ TRỰC CẢM,

VẤN ĐỀ TÌM KIẾM ................................................................................................4

1.1. Tập mờ..............................................................................................................4

1.1.1. Định nghĩa tập mờ, số mờ [1]........................................................................4

1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác ....................9

1.2. Tập mờ trực cảm.............................................................................................18

1.2.1. Định nghĩa ...................................................................................................18

1.2.2. Các phép toán trên số mờ trực cảm hình thang, hình tam giác ...................20

1.3. Bài toán tìm kiếm lời giải và những kỹ thuật tìm kiếm .................................26

1.4. Kết luận chương 1 ..........................................................................................37

Chƣơng 2: TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG CỦA TẬP MỜ

TRỰC CẢM.............................................................................................................38

2.1. Tìm kiếm thông minh .....................................................................................38

2.2. Thuật toán tìm kiếm thông minh với ứng dụng tập mờ trực cảm ..................53

2.3. Kết luận chương 2 ..........................................................................................58

Chƣơng 3: VÍ DỤ ÁP DỤNG.................................................................................59

3.1. Một số bài toán tìm kiếm................................................................................59

3.2. Lời giải ...........................................................................................................61

3.3. Kết luận chương 3 ..........................................................................................82

KẾT LUẬN..............................................................................................................83

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

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

iv

DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT

Vague sets (VS) Tập mờ trực cảm

Vague Number (VN) Số mờ trực cảm

Vague Relation (VR) Quan hệ mờ trực cảm

Vague Tolerance Relation (VTR) Quan hệ gần đúng

Vague Proximity Relation (VPR) Quan hệ lân cận

Depth First Search (DFS) Tìm kiếm theo chiều sâu

Breadth First Search (BFS) Tìm kiếm theo chiều rộng

Domain (Dom) Miền

Not less than (nlt) Không nhỏ hơn

Sup Cận trên

Inf Cận dưới

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

v

DANH MỤC CÁC HÌNH

Hình 1.1: Biểu diễn tập mờ cho số "integer nhỏ" .......................................................4

Hình 1.2: Biểu diễn tập mờ cho các tập người thấp, trung bình và cao......................5

Hình 1.3: Tập mờ lồi...................................................................................................6

Hình 1.4: Đồ thị hàm thành viên nhóm hàm đơn điệu................................................7

Hình 1.5: Đồ thị hàm thành viên nhóm hàm hình chuông..........................................7

Hình 1.6: Hàm thành viên của phần bù mờ ................................................................9

Hình 1.7: Hàm thành viên của hợp hai tập mờ có cùng cơ sở ....................................9

Hình 1.8a: Phép hợp hai tập mờ không cùng cơ sở: Hàm thành viên của 2 tập

mờ A, B .................................................................................................10

Hình 1.8b: Phép hợp hai tập mờ không cùng cơ sở: Đưa 2 tập mờ về chung

một cơ sở MxN......................................................................................10

Hình 1.8c: Phép hợp hai tập mờ không cùng cơ sở: Hợp 2 tập mờ trên cơ sở MxN.......10

Hình 1.9: Phép giao hai tập mờ cùng cơ sở ..............................................................11

Hình 1.10: Phép giao hai tập mờ không cùng cơ sở .................................................12

Hình 1.11: Số mờ hình thang ....................................................................................17

Hình 1.13: Số mờ trực cảm hình thang .....................................................................21

Hình 1.14: Số mờ trực cảm tam giác ........................................................................21

Hình 1.15: Đồ thị không gian trạng thái ...................................................................28

Hình 1.16: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số....................30

Hình 1.17: Các trạng thái của cây trò chơi................................................................36

Hình 1.18: Cây tìm kiếm và sự bùng nổ tổ hợp ........................................................37

Hình 2.1: Hình ảnh của tìm kiếm chiều sâu. Nó chỉ lưu ý "mở rộng" trạng thái được

chọn mà không "mở rộng" các trạng thái khác (nút màu trắng).....................39

Hình 2.2: Hình ảnh của tìm kiếm chiều rộng. Tại một bước, mọi trạng thái đều

được mở rộng, không bỏ sót trạng thái nào.............................................41

Hình 2.3: Chi phí ước lượng h‟ = 6 và chi phí tối ưu thực sự h = 4+5 = 9 (đi

theo đường 1-3-7)....................................................................................43

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

vi

Hình 2.5: Đồ thị không gian trạng thái .....................................................................47

Hình 2.6: Cây tìm kiếm Beam...................................................................................48

Hình 2.7: Đồ thị không gian trạng thái .....................................................................50

Hình 2.8: Sơ đồ biểu thị đường đi.............................................................................51

Hình 2.9: Đồ thị không gian trạng thái .....................................................................55

Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số......................59

Hình 3.2: Giải bài toán Ta canh bằng phương pháp tìm kiếm theo chiều sâu..........59

Hình 3.3: Giải bài toán Ta canh bằng thuật giải Heuristics tìm đường đi có giá

nhỏ nhất với tri thức bổ sung...................................................................60

Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số......................61

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

1

MỞ ĐẦU

Xuất phát từ sự bùng nổ thông tin và mạng internet kết nối hầu hết các máy

tính của các tổ chức thành những kho dữ liệu khổng lồ. Tuy nhiên, dữ liệu được bố

trí sắp xếp và phân tán thành nhiều tập dữ liệu được lưu trữ trên các hệ thống máy

tính lớn nằm rải rác trên toàn thế giới. Với một kỹ thuật đơn giản thì việc tìm kiếm

thông tin là rất khó khăn và không chính xác mất nhiều thời gian tìm kiếm. Câu hỏi

đặt ra là làm thế nào để con người có thể vươn tới tầm cao tri thức làm chủ được

công nghệ, tìm kiếm thông tin nhanh và chính xác.

Cùng với việc phát minh ra các thuật toán tìm kiếm tối ưu các kỹ thuật mới

xuất hiện và có tốc độ phát triển rất nhanh đóng góp vai trò quan trọng trong việc

tìm kiếm dữ liệu, các thuật toán mới xuất hiện với thời gian tính toán đã phần nào

giải quyết được những vướng mắc nói trên.

Ngoài ra còn có sự hỗ trợ của nhiều phương pháp, liên quan đến nhiều lĩnh

vực, ngành khác như: lý thuyết thuật toán, thị giác máy tính (Visualization), Data

Warehouses, OLAP, tính toán song song, cấu trúc ôtômát mờ và các phép tính toán

kết quả cao…nhưng chủ yếu dựa trên nền tảng của xác suất thống kê, cơ sở dữ liệu,

lý thuyết mờ, lý thuyết ôtômát và học máy.

Đây là một quá trình mang tính định tính với mục đích xác định được

lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng thể. Trong thực

tế, các cơ sở dữ liệu được chuyên môn hoá và phân chia theo các lĩnh vực

khác nhau như sản xuất, kinh doanh, tài chính... Với mỗi tri thức phát hiện

được, có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa

đối với một lĩnh vực khác. Vì vậy việc xác định lĩnh vực và định nghĩa bài

toán giúp định hướng cho giai đoạn tiếp theo – thu thập và tiền xử lý dữ liệu.

Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại

không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy,

giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình

phát hiện tri thức từ cơ sở dữ liệu phục vụ cho việc tìm kiếm dữ liệu.

Quá trình tìm kiếm lời giải thực sự là một bài toán khó. Các phương pháp vét

cạn kinh điển như tìm kiếm sâu (DFS), tìm kiếm rộng (BFS),… đều không thể áp