Thạc Sĩ Các kỹ thuật phân cụm trong khai phá dữ liệu sử dụng tính toán tiến hóa

LỜI CẢM ƠN

Luận văn được thực hiện dưới sự hướng dẫn của PGS.TS. Bùi Thu Lâm – Học
viện Kỹ thuật Quân sự. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng
dẫn và có ý kiến chỉ dẫn quý báu trong quá trình em làm luận văn. Em xin chân
thành cảm ơn các Thầy giáo trong bộ môn Công nghệ phần mềm. Em cũng xin
cảm ơn các thầy cô giáo trong Khoa, cán bộ thuộc phòng Khoa học và Đào tạo
sau Đại học, Trường Đại học Công nghệ đã tạo điều kiện trong quá trình học tập
và nghiên cứu tại Trường.
Cuối cùng xin bày tỏ lòng cảm ơn tới những người thân trong gia đình, bạn bè
đã động viên và giúp đỡ để tôi hoàn thành bản luận văn này.

Hà Nội, Tháng 10 năm 2014
Học viên thực hiện
Phan Minh Hải 4

LỜI CAM ĐOAN . 2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 6
DANH MỤC CÁC BẢNG . 7
DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ 8
CHƯƠNG 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC, KHAI PHÁ DỮ LIỆU
VÀ GIẢI THUẬT DI TRUYỀN 10
1.1. Tổng quan về khám phá tri thức và khai phá dữ liệu . 10
1.1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu . 10
1.1.2. Quá trình khám phá tri thức . 10
1.1.3. Các phương pháp khai phá dữ liệu . 12
1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL . 12
1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL. 13
1.1.6. Các yêu cầu của phân cụm 13
1.1.7. Phân cụm với giải thuật Kmean . 15
1.2. Tổng quan về giải thuật tiến hóa 16
1.2.1. Giải thuật di truyền . 16
1.2.1.1. Lịch sử phát triển . 18
1.2.1.2. Các bước áp dụng giải thuật di truyền 19
1.2.1.2.1. Mã hóa dữ liệu 19
1.2.1.2.2. Khởi tạo quần thể 19
1.2.1.2.3. Xác định hàm thích nghi . 19
1.2.1.2.4. Quá trình lai ghép 20
1.2.1.2.5. Quá trình đột biến . 21
1.2.1.2.6. Quá trình chọn lọc . 21
1.2.1.3. Các tham số của giải thuật di truyền . 21
1.2.1.4. Sơ đồ quá trình tính toán của giải thuật di truyền . 22
1.2.2. Giải thuật tiến hóa vi phân 25
1.2.2.1. Nguyên lý hoạt động 25
1.2.2.2. Sơ đồ giải thuật tiến hóa vi phân 25
1.3. Kết luận . 28
CHƯƠNG 2 GIẢI THUẬT PHÂN CỤM DỰA TRÊN LAI GHÉP GIẢI THUẬT
TIẾN HÓA VÀ KMEANS 29
2.1. Giải thuật phân cụm trong tính toán tiến hóa . 29
2.1.1.Giải thuật tổng quát cho phân cụm sử dụng giải thuật di truyền . 29
2.1.2. Biểu diễn cá thể 30
2.1.3. Tính toán độ thích nghi . 30
2.1.4. Phép chọn (Selection) . 31
2.1.5. Crossover (lai ghép) . 32
2.1.6. Mutation (Đột biến) 33
2.1.7. Kmeans sử dụng giải thuật di truyền . 34
2.1.8. Minh họa phân cụm Kmeans sử dụng giải thuật di truyền . 35
2.1.9. Phân cụm Kmeans sử dụng giải thuật tiến hóa vi phân 37 5
2.2. So sánh giữa giải thuật Kmeans và Kmeans sử dụng giải thuật di truyền . 38
2.3. Kết luận . 38
CHƯƠNG 3 CÀI ĐẶT VÀ THỬ NGHIỆM . 40
3.1. Chuẩn bị dữ liệu 40
3.2. Kết quả và phân tích . 41
3.2.1. Thí nghiệm giải thuật Kmeans, Genetic Kmean và DE Kmean 41
3.2.1.1. Thí nghiệm giải thuật Kmeans . 41
3.2.1.2. Thí nghiệm giải thuật Genetic Kmean 42
3.2.1.3. Thí nghiệm giải thuật DE Kmean . 43
3.2.1.4. Thí nghiệm giải thuật Kmean, Genetic Kmean, DE Kmean với Northwin 44
3.2.2. Phân tích kết quả 45
3.3. Đánh giá kết quả thử nghiệm chung 46
KẾT LUẬN 48
TÀI LIỆU THAM KHẢO . 50
6
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT


CDL Cụm dữ liệu
CNTT Công nghệ thông tin
CSDL Cơ sở dữ liệu
DE Giải thuật tiến hóa vi phân Differential Evolution
DL Dữ liệu
GA Giải thuật di truyền Genetic Algorithm
KPDL Khai phá dữ liệu
KPTT Khai phá thông tin
PCDL Phân cụm dữ liệu
NST Nhiễm sắc thể


7
DANH MỤC CÁC BẢNG


Bảng 2.1: Bộ dữ liệu số nguyên gồm 6 phần tử 35
Bảng 2.2: Khởi tạo các NST và tính độ thích nghi 35
Bảng 2.3: Các NST mới thu được bằng cách sử dụng chọn lọc, lai ghép, đột
biến, 36
Bảng 2.4: Các NST đầu vào và độ thích nghi cho đến thế hệ thứ 2 . 36
Bảng 2.5: Các NST đầu vào và độ thích nghi cho đến thế hệ thứ 3 . 36
Bảng 3.1: Bộ dữ liệu tự sinh có 2 trường dữ liệu 40
Bảng 3.2: Bộ dữ liệu Customers của Northwind . 40
Bảng 3.3: Kết quả thử nghiệm với giải thuật Kmeans . 41
Bảng 3.4: Kết quả thử nghiệm với giải thuật Genetic Kmean . 42
Bảng 3.5: Kết quả thử nghiệm với giải thuật DE Kmean 43
Bảng 3.6: Kết quả thử nghiệm các giải thuật với số cụm bằng 7 . 44