Phân Cụm Đa Mục Tiêu Mờ Cho Dữ Liệu Định Danh

1

LỜI CẢM ƠN

Để có thể hoàn thiện được luận văn thạc sỹ của mình, trước tiên em xin được gửi

lời cảm ơn sâu sắc đến thày PGS.TS Hoàng Xuân Huấn. Thày đã tận tình định hướng,

dìu dắt, chỉ bảo cho em trong những bước đầu nghiên cứu khoa học. Trong quá trình ấy

thày luôn quan tâm, lo lắng, động viên, những điều đáng quý ấy em xin được ghi nhớ

mãi trong lòng.

Em cũng xin được gửi lời chân thành cảm ơn đến các thày cô giáo trong bộ môn

Hệ thống thông tin, bộ môn Khoa học máy tính – Khoa Công nghệ thông tin – Trường

Đại học Công nghệ – Đại học Quốc gia Hà Nội và các thày cô đã tận tình dạy dỗ, nỗ

lực, tâm huyết dạy từng môn học giúp em có được kiến thức về cuộc sống, về chuyên

môn và hoàn thành khóa học tại trường.

Đồng thời em cũng xin được gửi lời cảm ơn đến các bạn học, người thân trong

gia đình, đồng nghiệp đã giúp đỡ, động viên, tạo điều kiện cho em trong suốt khóa học

tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội.

Hà Nội, tháng 11 năm 2016

Học viên

Nguyễn Thị Thanh Tâm

2

LỜI CAM ĐOAN

Em xin cam đoan những nội dung kiến thức mà em trình bày trong quyển luận

văn này là do em tự tìm hiểu, nghiên cứu, trình bày dưới sự hướng dẫn trực tiếp của thày

PGS. TS Hoàng Xuân Huấn. Tất cả những phần nội dung mà em có tham khảo đã được

trích dẫn đầy đủ, ghi rõ nguồn gốc ở phần Tài liệu tham khảo.

Em xin chịu trách nhiệm với lời cam đoan của mình, nếu có mọi phát hiện về sao

chép không hợp lệ, vi phạm quy chế đào tạo em xin được hoàn toàn chịu trách nhiệm.

Hà Nội, tháng 11 năm 2016

Học viên

Nguyễn Thị Thanh Tâm

3

MỤC LỤC

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

LỜI CAM ĐOAN ................................................................................................. 2

MỤC LỤC............................................................................................................. 3

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT................................................. 5

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

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

LỜI NÓI ĐẦU ...................................................................................................... 7

CHƯƠNG 1. NỀN TẢNG LÝ THUYẾT............................................................. 9

1.1. Phân cụm dữ liệu là gì?.............................................................................. 9

1.2. Các khái niệm cần thiết khi tiếp cận phân cụm dữ liệu ........................... 10

1.2.1. Cấu trúc dữ liệu................................................................................. 10

1.2.2. Các kiểu dữ liệu ................................................................................ 11

1.2.3. Độ đo tương tự và phi tương tự ........................................................ 12

1.3. Phân cụm dữ liệu mờ ............................................................................... 15

1.3.1. Tổng quan về tập mờ......................................................................... 15

1.3.2. Phân cụm rõ và phân cụm mờ........................................................... 17

1.4. Tối ưu đa mục tiêu [1].............................................................................. 21

1.4.1. Bài toán tối ưu tổng quát................................................................... 21

1.4.2. Tối ưu đơn mục tiêu.......................................................................... 21

1.4.3. Tối ưu đa mục tiêu ............................................................................ 22

1.4.4. Chọn phương án trong bài toán đơn mục tiêu và bài toán đa mục tiêu

..................................................................................................................... 23

1.5. Giải thuật di truyền sử dụng để tối ưu hóa đa mục tiêu........................... 24

1.5.1. Giới thiệu........................................................................................... 24

1.5.2. Các quy luật cơ bản........................................................................... 25

CHƯƠNG 2. PHÂN CỤM ĐA MỤC TIÊU MỜ CHO DỮ LIỆU ĐỊNH DANH

............................................................................................................................. 28

2.1. Giới thiệu.................................................................................................. 28

2.2. Thuật toán phân cụm mờ cho dữ liệu định danh [4]................................ 29

2.3. Tối ưu hóa đa mục tiêu và các giải thuật tối ưu hóa đa mục tiêu ............ 31

2.3.1. Tối ưu hóa đa mục tiêu ..................................................................... 31

2.3.2. Việc sử dụng giải thuật di truyền giải quyết bài toán tối ưu đa mục

tiêu............................................................................................................... 32

4

2.4. Phân cụm đa mục tiêu mờ cho dữ liệu định danh sử dụng giải thuật di

truyền............................................................................................................... 33

2.4.1. Thuật toán NSGA-II.......................................................................... 33

2.4.2. Biểu diễn nhiễm sắc thể .................................................................... 35

2.4.3. Khởi tạo quần thể .............................................................................. 35

2.4.4. Tính toán giá trị của các hàm mục tiêu............................................. 35

2.4.5. Thủ tục sắp xếp không vượt trội và tính toán khoảng cách mật độ.. 37

2.4.6. Chọn lọc, lai ghép và đột biến .......................................................... 38

2.4.7. Chọn một phương án từ các tập không vượt trội.............................. 39

CHƯƠNG 3. THỬ NGHIỆM............................................................................. 42

3.1. Giới thiệu.................................................................................................. 42

3.2. Chương trình ............................................................................................ 42

3.3. Dữ liệu thử nghiệm .................................................................................. 42

3.3.1. Cơ sở dữ liệu Soybean ...................................................................... 43

3.3.2. Cơ sở dữ liệu SPECT heart............................................................... 44

3.3.3. Cơ sở dữ liệu Hayes – Roth .............................................................. 44

3.4. Phương pháp biểu diễn dữ liệu ................................................................ 45

3.5. Độ đo hiệu suất ........................................................................................ 45

3.6. Thủ tục thực nghiệm ................................................................................ 45

3.7. Các thông số đầu vào ............................................................................... 46

3.8. Kết quả thử nghiệm.................................................................................. 46

KẾT LUẬN......................................................................................................... 52

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

5

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

Từ hoặc cụm từ Từ viết tắt Từ Tiếng Anh

Cơ sở dữ liệu CSDL DataBase

Thuật toán HAC HAC Hierarchical agglomerative clustering

Thuật toán BIRCH BIRCH Balanced Interative Reducing and Clustering

using Hierarchies

Thuật toán PAM PAM Partition Around Mediods

Thuật toán STING STING A STatistical Information Grid approach

Giải thuật di truyền GA Genetic Algorithms

Nhiễm sắc thể NST Chromosomes

Thuật toán C-Mean

mờ

FCM Fuzzy C-Means

Thuật toán NSGA-II NSGA-II Non-dominated Sorting Genetic Algorithm-II