ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
---------- ----------
CHẾ THỊ HẰNG
ỨNG DỤNG KỸ THUẬT ĐA MỤC TIÊU VÀO PHÂN CỤM
DỮ LIỆU
LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
---------- ----------
CHẾ THỊ HẰNG
ỨNG DỤNG KỸ THUẬT ĐA MỤC TIÊU VÀO PHÂN CỤM
DỮ LIỆU
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN
Hà Nội - 2014
1
LỜI CẢM ƠN
Để hoàn thành đư ợc luận văn thạc sỹ này, trước hết tôi xin gửi lời cảm ơn sâu sắc
nhất đến PGS.TS Hoàng Xuân Huấn. Thầy đã cung cấp cho tôi những kiến thức, những
tài liệu, những phương pháp khi nghiên cứu một vấn đề mang tính khoa học. Thầy thường
xuyên đưa ra và giúp tôi có những ý tưởng khi làm luận văn. Tôi xin chân thành cảm ơn
thầy về sự hỗ trợ chân thành và nhiệt tình trong suốt thời gian qua.
Tôi xin chân thành cảm ơn các thầy, cô giáo tr ong Bộ môn Công nghệ phần mềm,
Khoa Công nghệ thông tin - Phòng Đào tạo sau đại học - Nghiên cứu Khoa học, Trường
Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất để tôi hoàn
thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn
khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và
các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt thời gian tôi học tập và rèn
luyện tại trường Đại học Công nghệ - Đại học Quốc gia Hà Nội.
Hà Nội, ngày 20 tháng 05 năm 2014
Học viên
Chế Thị Hằng
2
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu,
nghiên cứu và trình b ày theo cách hiểu của bản thân dưới sự hướng dẫn trực tiếp của
PGS.TS Hoàng Xuân Huấn. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có
liên quan và đã ghi rõ nguồn gốc tham khảo tài liệu đó. Mọi sao chép không hợp lệ, vi
phạm quy chế đào tạo tôi xin chịu hoàn toàn trách nhiệm.
Hà Nội, ngày 20 tháng 05 năm 2014
Học viên
Chế Thị Hằng
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, TỪ VIẾT TẮT ............................................................................ 5
DANH MỤC CÁC HÌNH VẼ ....................................................................................................... 6
MỞ ĐẦU ......................................................................................................................................... 8
CHƢƠNG I. PHÂN CỤM DỮ LIỆU ......................................................................................... 10
1.1. Phân cụm dữ liệu .............................................................................................................. 10
1.2. Các phƣơng pháp và các thuật toán phân cụm dữ liệu [2] ........................................... 11
1.2.1. Các phƣơng pháp phân vùng ........................................................................ 11
1.2.2. Các phƣơng pháp phân cấp........................................................................... 17
1.2.3. Phƣơng pháp phân cụm dựa trên mật độ .................................................... 22
1.2.4. Các phƣơng pháp phân cụm dựa trên lƣới ................................................. 24
CHƢƠNG II. PHÂN CỤM DỮ LIỆU ĐA MỤC TIÊU VÀ MỘT SỐ KỸ THUẬT TỐI ƢU
HÓA CỤM ................................................................................................................................... 28
2.1. Phân cụm dữ liệu đơn mục tiêu và phân cụm dữ liệu đa mục tiêu [1] ........................ 28
2.2.Một số giải thuật tối ƣu hóa cụm...................................................................................... 30
2.2.1. Giải thuật di truyền (Genetic Algorithm) .................................................... 30
2.2.2. Kỹ thuật mô phỏng luyện kim dựa trên thuật toán tối ƣu nhiều mục tiêu
(SA) VAMOSA .................................................................................................................. 37
CHƢƠNG III. THUẬT TOÁN VAMOSA – THUẬT TOÁN PHÂN CỤM DỰA TRÊN
TÍNH ĐỐI XỨNG ....................................................................................................................... 48
3.1. Giới thiệu ........................................................................................................................... 48
3.2. Thuật toán tối ƣu đa mục tiêu dựa vào SA: AMOSA ................................................... 49
3.3. Khoảng cách đối xứng ...................................................................................................... 49
3.4. Phƣơng pháp đề xuất để phân cụm đa mục tiêu ........................................................... 50
3.4.1. Trình bày chuỗi và khởi tạo kho lƣu trữ ..................................................... 50
3.4.2. Phân cụm các điểm dữ liệu ............................................................................ 52
3.4.3. Tính toán các hàm mục tiêu phù hợp ........................................................... 53
3.4.4. Một số phƣơng pháp nhiễu các phƣơng án ................................................. 55
3.4.5. Điều kiện dừng cùa thuật toán ...................................................................... 55
3.4.6. Lựa chọn giải pháp ......................................................................................... 55
CHƢƠNG IV. KẾT QUẢ THỬ NGHIỆM ............................................................................... 56
