Phân cụm dữ liệu mờ theo tiếp cận đại số gia tử : Luận văn thạc sĩ - Chuyên ngành: Khoa học máy tính

BỘ CÔNG THƯƠNG

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH

PHẠM XUÂN THẢO

PHÂN CỤM DỮ LIỆU MỜ

THEO TIẾP CẬN ĐẠI SỐ GIA TỬ

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã chuyên ngành: 60480101

LUẬN VĂN THẠC SĨ

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2019

Công trình được hoàn thành tại Trường Đại học Công nghiệp TP. Hồ Chí Minh.

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

Người phản biện 1: TS. Đàm Quang Hồng Hải

Người phản biện 2: TS. Lê Ngọc Sơn

Luận văn thạc sĩ được bảo vệ tại Hội đồng chấm bảo vệ Luận văn thạc sĩ Trường Đại học

Công nghiệp thành phố Hồ Chí Minh ngày 12 tháng 4 năm 2019

Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:

1. PGS.TS. Phạm Thế Bảo Chủ tịch Hội đồng

2. TS. Lê Nhật Duy Thư ký

3. TS. Đàm Quang Hồng Hải Phản biện 1

4. TS. Lê Ngọc Sơn Phản biện 2

5. TS. Phạm Văn Chung Uỷ viên

CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA CNTT

NHIỆM VỤ LUẬN VĂN THẠC SĨ

Họ tên học viên: Phạm Xuân Thảo MSHV:16083181

Ngày, tháng, năm sinh: 20/04/1974 Nơi sinh: Vĩnh Phúc

Chuyên ngành: Khoa học Máy tính Mã chuyên ngành: 60480101

I. TÊN ĐỀ TÀI:

Phân cụm dữ liệu mờ theo tiếp cận đại số gia tử

NHIỆM VỤ VÀ NỘI DUNG:

Tìm hiểu về tập mờ và một số thuật toánphân cụm dữ liệu mờ. Nghiên cứu tìm hiểu về đại

số gia tử, phân cụm dữ liệu mờ theo tiếp cận đại số gia tử.

II. NGÀY GIAO NHIỆM VỤ: Theo quyết định giao đề tài số 1486/QĐ-ĐHCN ngày

25/06/2018

III. NGÀY HOÀN THÀNH NHIỆM VỤ: 25/12/2018

IV. NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Đoàn Văn Thắng

Tp. Hồ Chí Minh, ngày … tháng … năm 2019

NGƯỜI HƯỚNG DẪN

TS. Đoàn Văn Thắng

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO

TRƯỞNG KHOA CNTT

BỘ CÔNG THƯƠNG

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP

THÀNH PHỐ HỒ CHÍ MINH

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập - Tự do - Hạnh phúc

i

LỜI CẢM ƠN

Để hoàn thành luận văn này, em xin bày tỏ lòng biết ơn chânthành và sâu sắc đến

Tiến sĩ Đoàn Văn Thắng, người đã tận tình và trực tiếp hướng dẫn em trong suốt

quá trình triển khai và nghiên cứu đề tài, tạo điều kiện để em hoàn thành luận văn.

Em cũng xin chân thành cảm ơn tới toàn thể quý thầy cô giáo trong khoa Công nghệ

Thông tin, Trường Đại học Công nghiệp TP.HCM đã cung cấp thêm nhiều kiến

thức quý giá thông qua các môn học, các chuyên đề cũng như truyền đạt tận tình

trong suốt quá trình em học tập tại khoa để em có thể hoàn thành tốt hơn luận văn

của mình.

Cuối cùng xin chân thành cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn đồng

hành cổ vũ, động viên và giúp đỡ trong suốt quá trình học tập và thực hiện luận văn.

Xin chân thành cảm ơn!

ii

TÓM TẮT LUẬN VĂN THẠC SĨ

Phân cụm mờ đã được nhiều tác giả quan tâm nghiên cứu theo nhiều cách tiếp cận

khác nhau và đã có nhiều kết quả công bố trong khai phá dữ liệu. Tuy nhiên, đối với

việc khai phá dữ liệu mờ với nhiều kiểu dữ liệu khác nhau để tìm ra các đối tượng

thuộc một cụm nào đó là vấn đề khó và phức tạp. Trong luận văn này, với nhiều ưu

điểm của đại số gia tử về ngữ nghĩa ngôn ngữ được lượng hóa bằng các ánh xạ định

lượng của ĐSGT, ngữ nghĩa của ngôn ngữ có thể được biểu thị bằng một lân cận

các khoảng được xác định bởi độ đo tính mờ của các giá trị ngôn ngữ của một thuộc

tính với vai trò là biến ngôn ngữ, chúng tôi trình bày một phương pháp mới để phân

các đối tượng thuộc về một cụm sử dụng đại số gia tử trở nên đơn giản và trực quan

hơn.

iii

ABSTRACT

Fuzzy clusters have been studied by many authors in various approaches and there

have been many results published in data mining. However, for fuzzy data mining

with many different data types to find objects of a certain cluster is difficult and

complex. In this dissertation, with many advantages of hedge algebras on linguistic

semantics quantified by quantitative mappings of HA, the semantics of the language

can be denoted by a neighbor of defined intervals by measuring the fuzziness of

linguistic values of an attribute as a linguistic variable, we present a new way of

dividing objects belonging to a cluster more simpler and intuitive by use hedge

algebra.

iv

LỜI CAM ĐOAN

Tôi xin cam đoan nội dung của luận văn là kết quả nghiên cứu của chính bản thân

dưới sự hướng dẫn của các cán bộ hướng dẫn khoa học. Công trình nghiên cứu của

nhiều tác giả được đưa vào luận văn (nếu có) đã được sự đồng ý của các đồng tác

giả. Việc tham khảo các nguồn tài liệu (nếu có) đã được thực hiện trích dẫn và ghi

nguồn tài liệu tham khảo theo quy định.

Học viên

Phạm Xuân Thảo

v

MỤC LỤC

MỤC LỤC .............................................................................................................. v

DANH MỤC HÌNH ẢNH ..................................................................................... vii

DANH MỤC BẢNG BIỂU ..................................................................................viii

DANH MỤC TỪ VIẾT TẮT ................................................................................. ix

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

1. Đặt vấn đề ....................................................................................................... 1

2. Mục tiêu nghiên cứu ....................................................................................... 4

3. Đối tượng và phạm vi nghiên cứu ................................................................... 4

4. Cách tiếp cận và phương pháp nghiên cứu ...................................................... 4

5. Ý nghĩa thực tiễn của đề tài ............................................................................. 5

CHƯƠNG 1 TẬP MỜ VÀ ĐẠI SỐ GIA TỬ ........................................................ 7

1.1 Tập mờ............................................................................................................ 7

1.1.1 Tập mờ, thông tin không chắc chắn và dữ liệu mờ .................................... 7

1.1.2 Một số khái niệm đặc trưng và phép toán trên tập mờ ............................... 9

1.1.3 Tổng quát hóa ba phép toán cơ bản trên tập mờ ...................................... 14

1.1.4 Biến ngôn ngữ ........................................................................................ 16

1.2 Đại số gia tử .................................................................................................. 18

1.2.1 Một số khái niệm .................................................................................... 18

1.2.2 Các tính chất của độ đo tính mờ trong ĐSGT .......................................... 21

1.3 Đại số gia tử tuyến tính đầy đủ. ..................................................................... 22

1.3.1 Một số khái niệm .................................................................................... 22

1.3.1.1 Khoảng mờ của khái niệm mờ ................................................................... 22

1.3.1.2 Khoảng mờ mức k ..................................................................................... 23

1.3.2 Các tính chất tôpô ................................................................................... 24

1.3.3 Ngữ nghĩa dữ liệu dựa trên lân cận tôpô của ĐSGT ................................ 25

CHƯƠNG 2 PHÂN CỤM MỜ............................................................................ 27

2.1 Tổng quan về phân cụm mờ .......................................................................... 27

vi

2.2 Các thuật toán trong phân cụm mờ ................................................................ 30

2.2.1 Thuật toán FCM (Fuzzy C-means) .......................................................... 30

2.2.1.1 Hàm mục tiêu ............................................................................................ 30

2.2.1.2 Thuật toán FCM ......................................................................................... 33

2.2.2 Thuận toán ɛFCM (ɛ- Insensitive Fuzzy C-Means) ................................. 37

2.2.2.1 Hàm mục tiêu ............................................................................................ 37

2.2.2.2 Thuật toán ɛFCM ....................................................................................... 39

2.2.3 Thuật toán FCM cải tiến ......................................................................... 39

2.2.3.1 Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu làm ứng viên cho việc

chọn các trung tâm của các cụm ............................................................................ 40

2.2.3.2 Thuật toán 2: Thuật toán lược bớt các ứng viên ......................................... 42

2.2.3.3 Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu hàm mục tiêu ..... 42

2.2.3.4 Thuật toán 4: Gán các trung tâm có liên kết “gần gũi” vào một cụm .......... 43

2.2.3.5 Tổng kết thuật toán FCM – Cải tiến ........................................................... 47

CHƯƠNG 3 PHÂN CỤM THEO ĐSGT VÀ ỨNG DỤNG ................................ 49

3.1 Thuật toán phân cụm mờ theo ĐSGT ............................................................ 49

3.2 Cài đặt thực nghiệm và ứng dụng .................................................................. 54

KẾT LUẬN VÀ KIẾN NGHỊ ............................................................................... 60

1. Kết luận ........................................................................................................ 60

2. Kiến nghị ...................................................................................................... 60

DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA HỌC VIÊN ........................... 61

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

PHỤ LỤC.............................................................................................................. 64

1. Kết quả cài đặt thực nghiệm .......................................................................... 64

2. Bài báo .......................................................................................................... 72

LÝ LỊCH TRÍCH NGANG CỦA HỌC VIÊN ....................................................... 78