Luận văn Thạc sĩ Công nghệ thông tin: Phân cụm đa mục tiêu mờ cho dữ liệu định danh

1<br /> LỜI CẢM ƠN<br /> Để 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<br /> 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,<br /> 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<br /> 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ớ<br /> mãi trong lòng.<br /> 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<br /> 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<br /> Đạ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ỗ<br /> 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<br /> môn và hoàn thành khóa học tại trường.<br /> Đồ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<br /> 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<br /> tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội.<br /> Hà Nội, tháng 11 năm 2016<br /> Học viên<br /> Nguyễn Thị Thanh Tâm<br /> <br /> 2<br /> LỜI CAM ĐOAN<br /> Em xin cam đoan những nội dung kiến thức mà em trình bày trong quyển luận<br /> 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<br /> 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<br /> trích dẫn đầy đủ, ghi rõ nguồn gốc ở phần Tài liệu tham khảo.<br /> 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<br /> 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.<br /> Hà Nội, tháng 11 năm 2016<br /> Học viên<br /> <br /> Nguyễn Thị Thanh Tâm<br /> <br /> 3<br /> MỤC LỤC<br /> <br /> LỜI CẢM ƠN ....................................................................................................... 1<br /> LỜI CAM ĐOAN ................................................................................................. 2<br /> MỤC LỤC ............................................................................................................. 3<br /> DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ................................................. 5<br /> DANH MỤC CÁC BẢNG ................................................................................... 6<br /> DANH MỤC CÁC HÌNH VẼ .............................................................................. 6<br /> LỜI NÓI ĐẦU ...................................................................................................... 7<br /> CHƯƠNG 1. NỀN TẢNG LÝ THUYẾT............................................................. 9<br /> 1.1. Phân cụm dữ liệu là gì? .............................................................................. 9<br /> 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<br /> 1.2.1. Cấu trúc dữ liệu ................................................................................. 10<br /> 1.2.2. Các kiểu dữ liệu ................................................................................ 11<br /> 1.2.3. Độ đo tương tự và phi tương tự ........................................................ 12<br /> 1.3. Phân cụm dữ liệu mờ ............................................................................... 15<br /> 1.3.1. Tổng quan về tập mờ......................................................................... 15<br /> 1.3.2. Phân cụm rõ và phân cụm mờ ........................................................... 17<br /> 1.4. Tối ưu đa mục tiêu [1].............................................................................. 21<br /> 1.4.1. Bài toán tối ưu tổng quát ................................................................... 21<br /> 1.4.2. Tối ưu đơn mục tiêu .......................................................................... 21<br /> 1.4.3. Tối ưu đa mục tiêu ............................................................................ 22<br /> 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<br /> ..................................................................................................................... 23<br /> 1.5. Giải thuật di truyền sử dụng để tối ưu hóa đa mục tiêu ........................... 24<br /> 1.5.1. Giới thiệu........................................................................................... 24<br /> 1.5.2. Các quy luật cơ bản ........................................................................... 25<br /> CHƯƠNG 2. PHÂN CỤM ĐA MỤC TIÊU MỜ CHO DỮ LIỆU ĐỊNH DANH<br /> ............................................................................................................................. 28<br /> 2.1. Giới thiệu.................................................................................................. 28<br /> 2.2. Thuật toán phân cụm mờ cho dữ liệu định danh [4] ................................ 29<br /> 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<br /> 2.3.1. Tối ưu hóa đa mục tiêu ..................................................................... 31<br /> 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<br /> tiêu ............................................................................................................... 32<br /> <br /> 4<br /> <br /> 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<br /> truyền............................................................................................................... 33<br /> 2.4.1. Thuật toán NSGA-II.......................................................................... 33<br /> 2.4.2. Biểu diễn nhiễm sắc thể .................................................................... 35<br /> 2.4.3. Khởi tạo quần thể .............................................................................. 35<br /> 2.4.4. Tính toán giá trị của các hàm mục tiêu ............................................. 35<br /> 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<br /> 2.4.6. Chọn lọc, lai ghép và đột biến .......................................................... 38<br /> 2.4.7. Chọn một phương án từ các tập không vượt trội .............................. 39<br /> CHƯƠNG 3. THỬ NGHIỆM ............................................................................. 42<br /> 3.1. Giới thiệu.................................................................................................. 42<br /> 3.2. Chương trình ............................................................................................ 42<br /> 3.3. Dữ liệu thử nghiệm .................................................................................. 42<br /> 3.3.1. Cơ sở dữ liệu Soybean ...................................................................... 43<br /> 3.3.2. Cơ sở dữ liệu SPECT heart ............................................................... 44<br /> 3.3.3. Cơ sở dữ liệu Hayes – Roth .............................................................. 44<br /> 3.4. Phương pháp biểu diễn dữ liệu ................................................................ 45<br /> 3.5. Độ đo hiệu suất ........................................................................................ 45<br /> 3.6. Thủ tục thực nghiệm ................................................................................ 45<br /> 3.7. Các thông số đầu vào ............................................................................... 46<br /> 3.8. Kết quả thử nghiệm .................................................................................. 46<br /> KẾT LUẬN ......................................................................................................... 52<br /> TÀI LIỆU THAM KHẢO................................................................................... 53<br /> <br /> 5<br /> <br /> DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT<br /> <br /> Từ hoặc cụm từ<br /> Cơ sở dữ liệu<br /> Thuật toán HAC<br /> Thuật toán BIRCH<br /> <br /> Từ viết tắt<br /> CSDL<br /> HAC<br /> BIRCH<br /> <br /> Thuật toán PAM<br /> Thuật toán STING<br /> Giải thuật di truyền<br /> Nhiễm sắc thể<br /> Thuật toán C-Mean<br /> mờ<br /> Thuật toán NSGA-II<br /> <br /> PAM<br /> STING<br /> GA<br /> NST<br /> FCM<br /> <br /> Từ Tiếng Anh<br /> DataBase<br /> Hierarchical agglomerative clustering<br /> Balanced Interative Reducing and Clustering<br /> using Hierarchies<br /> Partition Around Mediods<br /> A STatistical Information Grid approach<br /> Genetic Algorithms<br /> Chromosomes<br /> Fuzzy C-Means<br /> <br /> NSGA-II<br /> <br /> Non-dominated Sorting Genetic Algorithm-II<br /> <br />