Tài liệu 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

TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHAN MINH HẢI 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 Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM Hà Nội, 2014 2 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ yêu cầu do giáo viên hướng dẫn đề ra để hình thành hướng nghiên cứu. Các số liệu có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong luận văn được thu thập được trong quá trình nghiên cứu là trung thực chưa từng được ai công bố trước đây. Hà Nội, tháng 10 năm 2014 Tác giả luận văn Phan Minh Hải 3 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 DL Dữ liệu GA Giải thuật di truyền 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ể Differential Evolution Genetic Algorithm 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 8 DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ Hình 1.1: Quá trình KPTT ............................................................................. 11 Hình 1.2: Ví dụ về mã hóa nhiễm sắc thể ...................................................... 19 Hình 1.3: Lai ghép hai cá thể ......................................................................... 20 Hình 1.4: Đột biến một nhiễm sắc thể ........................................................... 21 Hình 1.5: Sơ đồ quá trình tính toán của giải thuật di truyền ............................ 23 Hình 1.6: Sơ đồ giải thuật tiến hóa vi phân ..................................................... 26 Biểu đồ 3.1: Tổng hợp kết quả của các giải thuật với giá trị trung bình trong trường hợp 1 (hình a) và trường hợp 2 (hình b) .............................................. 45 9 MỞ ĐẦU Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học không giám sát (unsupervised learning). Các Kỹ thuật phân cụm được ứng dụng rất nhiều trong các lĩnh vực tài chính ngân hành để phân lọai các nhóm khách hàng khác nhau. Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các giải thuật khai phá dữ liệu khác như phân loại và mô tả đặc điểm, có tác dụng phát hiện ra các cụm. Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc của các CSDL. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các CSDL, với mỗi cách thức biểu diễn khác nhau sẽ có một giải thuật phân cụm thích nghi. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và thích nghi với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong KPDL. Một điểm khác nữa là các hàm mục tiêu của các giải thuật phân cụm như K-means thường tồn tại nhiều điểm tối ưu cục bộ. Do đó mà đề tài tập trung vào tìm hiểu “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”; một kỹ - giải thuật tiến hóa được thiết kế để khắc phục tính chất cục bộ của các giải thuật phân cụm. Luận văn gồm có 3 chương chính: 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 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 Chương 3: Cài đặt và thử nghiệm Kết luận định hướng phát triển kết quả nghiên cứu 10 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 1.1. Tổng quan về khám phá tri thức và khai phá dữ liệu 1.1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu. Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác, tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng quát[2]. Khám phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu được. Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các giải thuật khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu. 1.1.2. Quá trình khám phá tri thức Quá trình khám phá dữ liệu có thể chia thành các giai đoạn như sau, xem hình 1.1 [3]: Giai đoạn 1. Trích chọn dữ liệu: Đây là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định. Giai đoạn 2. Tiền xử lý dữ liệu: Đây là bước làm sạch dữ liệu (xử lý những dữ liệu không đầy đủ, nhiễu, không nhất quán, ...), rút gọn dữ liệu (sử dụng hàm 11 nhóm và tính tổng, các phương pháp nén dữ liệu, lấy mẫu, ...), rời rạc hóa dữ liệu. Flat files: Những tệp dữ liệu không có mối quan hệ về cấu trúc Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Giai đoạn 3. Biến đổi dữ liệu: Đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bước sau. Giai đoạn 4. Khai phá dữ liệu: Đây là bước áp dụng những kỹ thuật phân tích (như các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của quá trình KDD. Giai đoạn 5. Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên được biến đổi và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, ... Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Đánh giá và biểu diễn Khai phá dữ liệu Các mẫu Lựa chọn và biến đổi Kho dữ liệu Làm sạch và tích hợp Cơ sở dữ liệu Flat files Hình 1.1: Quá trình khám phá tri thức Tri thức 12 1.1.3. Các phương pháp khai phá dữ liệu Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường sử dụng các phương pháp sau cho khai phá dữ liệu [3]: o Luật kết hợp (association rules) o Phân lớp (Classfication) o Hồi qui (Regression) o Trực quan hóa (Visualiztion) o Phân cụm (Clustering) o Tổng hợp (Summarization) o Mô hình ràng buộc (Dependency modeling) o Biểu diễn mô hình (Model Evaluation) o Phân tích sự phát triển và độ lệch (Evolution and deviation analyst) o Phương pháp tìm kiếm (Search Method) Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp, Phân lớp dữ liệu và Phân cụm dữ liệu. 1.1.4. Các lĩnh vực ứng dụng thực tiễn của KPDL KPDL là một lĩnh vực mới phát triển nhưng thu hút được khá nhiều nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng dụng thực tế điển hình của KPDL[2]: - Phân tích dữ liệu và hỗ trợ ra quyết định - Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân cụm ảnh màu - Chuẩn đoán triệu chứng, phương pháp trong điều trị y học - Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học - Phân tích tình hình tài chính, thị trường, dự báo gía cổ phiếu trong tài chính, thị trường và chứng khoán - Phân tích dữ liệu marketing, khách hàng. - Điều khiển và lập lịch trình - Bảo hiểm - Giáo dục..... 13 1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL. Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận chính sau [3]: - Phân lớp và dự đoán (classification &prediction): Là quá trình xếp một đối tượng vào một trong những lớp đã biết trước (ví dụ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết...). Đối với hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định (decision tree), mạng nơron nhân tạo (neural network),... Hay lớp bài toán này còn đươc gọi là học có giám sát - Học có thày (supervised learning). - Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm dữ liệu tự nhiên, tức là số lượng và tên cụm chưa được biết trước. Các đối tượng được gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán này còn được gọi là học không giám sát - Học không thày (unsupervised learning). - Luật kết hợp (association rules): Là dạng luật biểu diễn tri thức ở dạng khá đơn giản (Ví dụ: 80% sinh viên đăng ký học CSDL thì có tới 60% trong số họ đăng ký học Phân tích thiết kế hệ thống thông tin). Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng khoán,... - Phân tích chuỗi theo thời gian (sequential/temporal patterns): Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi chúng có tính dự báo cao. - Mô tả khái niệm (concept desccription & summarization): Lớp bài toán này thiên về mô tả, tổng hợp và tóm tắt khái niệm (Ví dụ: tóm tắt văn bản). 1.1.6. Các yêu cầu của phân cụm Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong KPDL [3]: 14 Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những tập dữ liệu khoảng vài trăm đối tượng, tuy nhiên, một CSDL lớn có thể chứa tới hàng triệu đối tượng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh hưởng tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các giải thuật phân cụm có khả năng mở rộng cao đối với các CSDL lớn? Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều giải thuật được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác nhau, như kiểu nhị phân, kiểu tường minh (định danh - không thứ tự), và dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này. Khám phá các cụm với hình dạng bất kỳ: Nhiều giải thuật phân cụm xác định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng cách Manhattan. Các thuật toán dựa trên các phép đo như vậy hướng tới việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ tương tự nhau. Tuy nhiên, một cụm có thể có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng. Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật toán phân cụm yêu cầu người dùng đưa vào những tham số nhất định trong phân tích phân cụm (như số lượng các cụm mong muốn). Kết quả của phân cụm thường khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để xác định, nhất là với các tập dữ liệu có lượng các đối tượng lớn. Điều này không những gây trở ngại cho người dùng mà còn làm cho khó có thể điều chỉnh được chất lượng của phân cụm. Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số giải thuật phân cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng phân cụm thấp. Ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân cụm nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu, khi được đưa ra với các thứ tự khác nhau thì với cùng một giải thuật có thể sinh ra các cụm rất khác nhau. Do đó, việc quan trọng là phát triển các giải thuật mà ít nhạy cảm với thứ tự vào của dữ liệu. Số chiều lớn: Một CSDL hoặc một kho dữ liệu có thể chứa một số chiều hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt cho dữ liệu với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Người ta đánh giá việc phân 15 cụm là có chất lượng tốt nếu nó áp dụng được cho dữ liệu có từ 3 chiều trở lên. Nó là sự thách thức với các đối tượng dữ liệu cụm trong không gian với số chiều lớn, đặc biệt vì khi xét những không gian với số chiều lớn có thể rất thưa và có độ nghiêng lớn. Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện phân cụm dưới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm những nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc. Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải thích ý nghĩa và ứng dụng rõ ràng. 1.1.7. Phân cụm với giải thuật Kmean Cho tập dữ liệu D gồm n đối tượng trong không gian Euclidean. Phương pháp này sẽ phân hoạch các đối tượng trong D vào trong k cụm, C1, .., Ck, trong đó Ck ⊂ D và Ci ∩ Cj = ∅ (trong đó, 1 ≤ i, j ≤ k). Hàm mục tiêu được sử dụng để đánh giá độ các đối tượng trong một cụm tương tự nhau, các đối tượng thuộc các cụm khác nhau sẽ không tương tự. Sự khác nhau giữa một đối tượng p ∈ Ci và ci được thể hiện bằng phép đo khoảng cách Euclidean dist(p, ci) [3]. Đặc tính của cụm Ci được xác định bởi sự khác nhau trong cụm theo công thức sau: trong đó, ci là trọng tâm cụm của Ci, p là điểm thuộc Ci Giải thuật phân cụm Kmean: Input: k: số cụm D: tập dữ liệu chứa n đối tượng Output: một tập hợp k các cụm Thứ tự thực hiện giải thuật: (1) Khởi tạo k trọng tâm cụm từ tập D đối tượng (2) Lặp (3) Đăng ký hoặc đăng ký lại mỗi đối tượng vào cụm có độ tương tự lớn nhất, dựa trên giá trị trung bình của các đối tượng thuộc cụm; 16 (4) Cập nhập lại các giá trị trung bình của cụm bằng cách tính toán giá trị trung bình của các đối tượng trong mỗi cụm (5) Đến khi trọng tâm cụm không thay đổi 1.2. Tổng quan về giải thuật tiến hóa Thuật ngữ Chương trình tiến hóa (cấu trúc dữ liệu + giải thuật di truyền) là khái niệm dùng để chỉ các chương trình máy tính có sử dụng giải thuật tìm kiếm và tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. Ta gọi chung các giải thuật như thế là giải thuật tiến hóa. Dưới đây là một số giải thuật tiến hóa đã được công bố [1]. − Quy hoạch tiến hóa - EP, do D.B. Pogel đề xuất. Có thể diễn tả EP đơn giản như sau: Cho một lớp các phương pháp khả dĩ giải quyết được một (số) phần của vấn đề. Dựa vào quy luật tiến hóa, tìm một phương pháp liên hợp đủ khả năng giải quyết trọn vẹn vấn đề đó. − Chiến lược tiến hóa, do T. Baeck, F.H. Hofmeister và H.P. Schwefel đề xuất. Giải thuật này dựa trên một số chiến lược ban đầu, tiến hóa để tạo ra những chiến lược mới thích nghi với môi trường thực tế một cách tốt nhất. − Giải thuật di truyền (Genetic Algorithms), do D.E. Goldberg đề xuất, được L. Davis và Z. Michalevicz phát triển. − Giải thuật tiến hóa vi phân (Differential Evolution), do Rainer Storn và Kenneth Price phát triển dựa trên giải thuật di truyền. Và trong phần trình bày dưới đây sẽ mô tả giải thuật di truyền và giải thuật tiến hóa vi phân. 1.2.1. Giải thuật di truyền Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên và trao đổi chéo [12]. Ngày nay, giải thuật di truyền được dùng phổ biến trong một số ngành như tin sinh học, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác. Giải thuật di truyền được lấy cảm hứng từ thuyết tiến hóa của giới tự nhiên do nhà bác học Darwin xây dựng. Nguyên lý sinh học khởi nguồn của tư tưởng lập trình tiến hóa như sau: Trong tất cả cá thể sống đều chứa các tế bào. Mỗi mội tế bào đều chứa cùng tập hợp bộ nhiễm sắc thể giống nhau. Nhiễm sắc thể chứa các chuỗi DNA. Các chuỗi DNA được nhóm lại thành các khối (block) hay còn 17 gọi là gen, mỗi một gen này là một Protein. Hay có thể nói mỗi một gen này biểu diễn một đặc điểm của sinh vật, ví dụ như đặc điểm của màu mắt (nâu, đen, xanh, vàng), đặc điểm của màu tóc (đen, bạch kim, nâu, vàng), kiểu tóc (thẳng, xoăn…). Các Gen tương ứng là các Gen có cùng một đặc tính với giá trị khác nhau, hoặc giống nhau. Ví dụ Gen quy định màu tóc vàng ở cá thể A tương ứng với Gen quy định tóc đen ở cá thể B. Tập hợp toàn bộ các nguyên liệu di truyền học (tất cả các nhiễm sắc thể) được gọi là bộ di truyền. Kiểu Gen là tập hợp con các gen trong bộ các nguyên liệu di truyền. Kiểu gen này sẽ quy định đặc tính cơ thể (thể xác) và tinh thần của cá thể sống như màu mắt, mức độ thông minh. Sự sinh sản: Trong quá trình sinh sản sự tổ hợp (trao đổi chéo). Gen từ các cá thể cha mẹ sẽ được chuyển cho thế hệ sau. Quá trình tạo mới cá thể con cháu có thể là đột biến. Đột biến xảy ra khi các thành phần DNA có một chút thay đổi, nguyên nhân chính của quá trình đột biến thường là lỗi trong quá trình sao chép các Gen từ các cá thể cha-mẹ. Sự phù hợp của một cá thể (fitness) được đánh giá bằng sự thành công của cá thể đó trong môi trường sống. Giải thuật di truyền được ứng dụng để giải quyết các bài toán NP-Problem. NPhard: Non-deterministic polynomial time hard. Các bài toán dạng này bao gồm: - Configuration: Cấu hình - Data mining: Khai phá dữ liệu - Selection: Chọn lọc - Diagnosis: Phân tích - Process monitoring and control: Thực hiện điều phối và giám sát - Scheduling: Lập lịch - Planning: Lập kế hoạch - Rosters or schedules - Tutoring systems: Hệ thống giám sát - Decision support: Hỗ trợ quyết định - Phylogenetics “Giống như giải thuật tiến hóa nói chung, giải thuật di truyền hình thành dựa trên quan niệm cho rằng quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể xem như một tiên đề đúng không chứng minh được nhưng phù hợp với thực tế khách quan. Tính tối ưu trong tự nhiên thể hiện ở chỗ thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước nhờ hai quá trình cơ bản là sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn được sinh ra để bổ xung thay thế thế hệ cụ. Những cá thể nào phát triển thích nghi với môi 18 trường sẽ tồn tại và ngược lại, những cá thể nào không thích nghi với môi trường sẽ bị đào thải. Sự thay đổi của môi trường sẽ tác động đến quá trình tiến hóa và bản thân quá trình tiến hóa cũng có tác động và làm thay đổi môi trường. Cá thể mới sinh ra trong quá trình tiến hóa nhờ vào sự lai ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những đặc tính của cha-mẹ ở thế hệ trước (di truyền) hoặc mang những đặc tính mới hoàn toàn (đột biến). Di truyền và đột biến là hai cơ chế quan trọng như nhau trong quá trình tiến hóa mặc dù xác suất để xảy ra hiện tượng đột biến nhỏ nhiều so với hiện tượng di truyền” [1]. Mặc dù cơ chế là ngẫu nhiên nhưng giải thuật di truyền không phải là một giải thuật ngẫu nhiên. Giải thuật khai thác và tận dụng được một cách hiệu quả thông tin quá khứ để có được những kết quả mới đạt kết quả như mong muốn. Các cải tiến trong việc sử dụng giải thuật di truyền đã làm tăng thêm hiệu quả của việc sử dụng giải thuật trong các bài toán phức tạp. Điều này thể hiện ở việc giảm thời gian tính toán ngày càng hiệu quả mà ta sẽ tìm hiểu cụ thể hơn ở dưới đây. 1.2.1.1. Lịch sử phát triển Năm 1954, GP bắt đầu với giải thuật tiến hóa, nó được sử dụng lần đầu tiên bởi Nils Aall Barricelli trong việc mô phỏng quá trình tiến hóa. Vào những năm 1960 và nửa đầu những năm 1970 giải thuật tiến hóa (EA) được biết đến như là các phương pháp tối ưu hóa. I. Rechenberg và nhóm của ông ấy đã giải quyết được nhiều vấn đề phức tạp trong ngành công nghệ bằng chiến lược tiến hóa (Evolution strategies). Ông đã giới thiệu ý tưởng về lập trình tiến hóa trong tác phẩm "Evolution strategies" (Evolutions strategie in original). Sau đó các nhà nghiên cứu khác tiếp tục phát triển ý tưởng này của ông. Năm 1971 ông làm luận án tiến sỹ về evolution strategies và năm 1973 ông xuất bản thành sách. Trong những năm 1970 Jonh Holland có những ảnh hưởng rất lớn trong quá trình phát triển của giải thuật di truyền. Giải thuật di truyền (GA) được Holland phát minh và sau đó ông cùng các sinh viên và cộng sự của mình phát triển tiếp. Các kết quả này được giới thiệu trong cuốn sách "Adaption in Natural and Artificial Systems" xuất bản vào năm 1975 của ông. Vào năm 1992, John Koza đã sử dụng giải thuật di truyền để thực hiện một vài nhiệm vụ trong chương trình tiến hóa. Ông đã gọi phương pháp này là Lập trình tiến hóa ("Genetic Programming" (GP)) [17]. 19 1.2.1.2. Các bước áp dụng giải thuật di truyền 1.2.1.2.1. Mã hóa dữ liệu Hay còn gọi là biểu diễn di truyền cho lời giải của bài toán: Đây là bước đầu tiên và rất quan trọng đối với việc tìm ra lời giải của bài toán. Mỗi lời giải của bài toán được biểu diễn dưới dạng một chuỗi ký tự hữu hạn hay còn được gọi là một nhiễm sắc thể. Các ký tự có thể là số nhị phân, số thập phân, … tùy vào từng bài toán cụ thể. Trong quá trình này, việc mã hóa cái gì, mã hóa như thế nào, trật tự các thành phần trong nhiễm sắc thể ra sao,… luôn là những thách thức cho những người giải bài toán. Nhiễm sắc thể 1 1101100100110110 Nhiễm sắc thể 2 1101111000011110 Hình 1.2: Ví dụ về mã hóa nhiễm sắc thể 1.2.1.2.2. Khởi tạo quần thể Xây dựng tập hợp nghiệm ban đầu (tập hợp các cá thể) có thể ngẫu nhiên hoặc không ngẫu nhiên. Có nhiều cách để khởi tạo giá trị quần thể nghiệm ban đầu, tùy từng bài toán mà ta lựa chọn phương pháp phù hợp. Thông thường, hệ nghiệm ban đầu được chọn ngẫu nhiên trong không gian tìm kiếm. Tuy vậy, việc chọn này cũng cần phải xem xét về tương quan giữa độ thích nghi của các nhiễm sắc thể để tránh tình trạng nghiệm tìm ra là nghiệm tối ưu cục bộ hay còn gọi là cực trị địa phương. Còn vấn đề số lượng nghiệm của tập nghiệm hay qui mô của quần thể cũng cần được xem xét kỹ dựa vào độ phức tạp của bài toán, độ chính xác yêu cầu (cao hay thấp) và thời gian tính toán yêu cầu (nhanh hay chậm). 1.2.1.2.3. Xác định hàm thích nghi Hay hàm lượng giá cho mỗi nhiễm sắc thể hay chính là cho các phương án nghiệm trong tập nghiệm. Hàm này dùng để đánh giá độ thích nghi của các nhiễm sắc thể. Hàm thích nghi cần phải đánh giá được mức độ thích nghi cho tất cả các nghiệm khả thi và luôn được giả định là không âm để hiện độ thích nghi của các cá thể. Công thức biểu diễn hàm cần phải thể hiện được tất cả các đặc tính mong muốn của nhiễm sắc thể, thông qua đó có thể chọn lọc được các quần thể nghiệm tốt nhất cho bài toán. 20 1.2.1.2.4. Quá trình lai ghép Đây là quá trình nhiễm sắc thể mới được hình thành dựa trên nhiễm sắc thể chamẹ bằng cách lai ghép một hay nhiều đoạn nhiễm sắc thể cha mẹ với nhau. Lai ghép có xét tới các đặc tính trội và lặn trong tự nhiên. Các đặc tính này được quy định trước trong khi biểu diễn cấu trúc nhiễm sắc thể. Bằng việc xem xét tới các đặc tính trội-lặn, quá trình sản sinh ra các "quần thể chất lượng tốt" sẽ nhanh hơn và do đó thời gian tính toán cũng được rút ngắn. Phép lai ghép xảy ra với xác suất là p1 có thể được mô phỏng như sau: − Chọn hai (hay nhiều) cá thể bất kỳ trong quần thể. Quần thể ở đây bao gồm các nhiễm sắc thể (cha-mẹ) có độ dài bằng nhau. − Chọn điểm lai là một điểm có vị trí bất kỳ (như nhau) trên nhiễm sắc thể cha-mẹ và thực hiện hoán đổi các đoạn gen của nhiễm sắc thể cha-mẹ tại điểm lai này. − Đưa hai cá thể này vào quần thể để thực hiện vào các quá trình tiến hóa tiếp theo Nhiễm sắc thể cha-mẹ: 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 Điểm lai ghép 1 0 1 0 0 1 0 Hai nhiễm sắc thể con được sinh ra sau quá trình lai ghép: 0 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 Hình 1.3: Lai ghép giữa hai cá thể Trong quá trình tồn tại và phát triển, giải thuật di truyền đã được bổ sung rất nhiều các phương pháp lai ghép để nhằm thích ứng với nhiều kiểu bài toán và cũng là để tăng hiệu quả của giải thuật. Có thể kể một số phép lai cải tiến như sau: − Lai ghép từng phần: Việc giữ lại những đoạn mã đã "tối ưu" trong nhiễm sắc thể cũng là một cách để quá trình lai ghép trở nên hiệu quả hơn. − Lai ghép có trật tự − Lai ghép dựa trên vị trí − Lai ghép chu trình − Lai ghép thứ tự tuyến tính