Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân cụm dựa trên tập thô và giải thuật di truyền

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƢỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> HOÀNG HUYỀN TRANG<br /> <br /> PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN<br /> TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN<br /> <br /> LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> Hà Nội - 2016<br /> <br /> 1<br /> ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƢỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> HOÀNG HUYỀN TRANG<br /> <br /> PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN<br /> TẬP THÔ VÀ GIẢI THUẬT DI TRUYỀN<br /> <br /> Ngành: Hệ thống thông tin<br /> Chuyên ngành: Hệ thống thông tin<br /> Mã số: 60480104<br /> <br /> LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> NGƢỜI HƢỚNG DẪN KHOA HỌC:<br /> PGS.TS. HOÀNG XUÂN HUẤN<br /> <br /> Hà Nội - 2016<br /> <br /> 2<br /> LỜI CẢM ƠN<br /> Tôi xin gửi lời biết ơn sâu sắc đến ngƣời thầy PGS,TS Hoàng Xuân Huấn,<br /> những thầy cô trƣờng Đại học Công nghệ đã dành rất nhiều thời gian và tâm<br /> huyết giảng dạy, hƣớng dẫn khoa học; giúp tôi nâng cao, mở rộng kiến thức,<br /> phát triển năng lực nghiên cứu khoa học, vận dụng thiết thực vào lĩnh vực hệ<br /> thống thông tin, hoàn thành tốt luận văn tốt nghiệp này;<br /> Trân trọng cảm ơn tới lãnh đạo đơn vị, đồng nghiệp nơi tôi công tác đã tạo<br /> điều kiện thuận lợi cho tôi hoàn thành khóa đào tạo;<br /> Xin biết ơn, yêu quý gia đình, ngƣời thân đã luôn đồng hành vƣợt khó trong<br /> cuộc sống, công tác và học tập.<br /> Tôi xin chân thành cảm ơn!<br /> Học viên<br /> Hoàng Huyền Trang<br /> <br /> 3<br /> LỜI CAM ĐOAN<br /> Tôi xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của cá<br /> nhân tôi, thực hiện dƣới sự hƣớng dẫn của PGS, TS Hoàng Xuân Huấn. Toàn bộ<br /> nội dung của luận văn, những điều đƣợc trình bày là của cá nhân hoặc đƣợc tổng<br /> hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng<br /> và đƣợc trích dẫn đúng quy định.<br /> Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan của mình.<br /> Hà Nội, tháng 11 năm 2016<br /> Học viên<br /> <br /> Hoàng Huyền Trang<br /> <br /> 4<br /> MỤC LỤC<br /> LỜI CẢM ƠN ....................................................................................................... 2<br /> LỜI CAM ĐOAN.................................................................................................. 3<br /> MỤC LỤC ............................................................................................................. 4<br /> DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... 6<br /> DANH MỤC CÁC HÌNH VẼ............................................................................... 7<br /> DANH MỤC CÁC BẢNG BIỂU ......................................................................... 8<br /> MỞ ĐẦU ............................................................................................................... 9<br /> CHƢƠNG I. PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN ... 10<br /> 1.1. Giới thiệu về phân cụm dữ liệu ................................................................. 10<br /> 1.1.1. Khái niệm và mục đích của phân cụm dữ liệu.................................... 10<br /> 1.1.2. Phƣơng pháp phân cụm dữ liệu .......................................................... 11<br /> 1.1.3. Phân cụm với giải thuật K-Means ...................................................... 12<br /> 1.2. Lý thuyết tập thô ....................................................................................... 14<br /> 1.2.1. Hệ thông tin và quyết định .................................................................. 14<br /> 1.2.2. Quan hệ bất khả phân biệt................................................................... 16<br /> 1.2.3. Xấp xỉ tập hợp ..................................................................................... 17<br /> 1.2.4. Thuộc tính thiết yếu và không thiết yếu ............................................. 18<br /> 1.3. Giải thuật di truyền ................................................................................... 19<br /> 1.3.1. Thông tin ............................................................................................. 19<br /> 1.3.2. Các thành phần cơ bản trong giải thuật di truyền ............................... 19<br /> 1.3.3. Quy trình thuật toán di truyền ............................................................. 23<br /> 1.3.4. Các thông số cơ bản của giải thuật di truyền ...................................... 25<br /> CHƢƠNG II. PHÂN CỤM DỮ LIỆU DỰA TRÊN TẬP THÔ VÀ GIẢI<br /> THUẬT DI TRUYỀN ......................................................................................... 26<br /> 2.1. Giới thiệu................................................................................................... 26<br /> 2.2. Phƣơng pháp phân cụm tập thô................................................................. 26<br /> 2.3. Phƣơng pháp phân cụm dựa trên giải thuật di truyền ............................... 31<br /> 2.4. Phƣơng pháp phân cụm dựa trên tập thô và giải thuật di truyền .............. 33<br /> CHƢƠNG III. CÀI ĐẶT VÀ PHÂN TÍCH THÍ NGHIỆM .............................. 35<br /> <br />