Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng kỹ thuật đa mục tiêu vào phân cụm dữ liệu

ĐẠ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

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 trong 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

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

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

4.1. Giới thiệu ........................................................................................................................... 56 4.2. Chƣơng trình và dữ liệu thử nghiệm .............................................................................. 56 4.2.1. Chƣơng trình .................................................................................................. 56 4.2.2. Dữ liệu thử nghiệm ......................................................................................... 56 4.3. Kết quả thí nghiệm ........................................................................................................... 57

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................................. 64

TÀI LIỆU THAM KHẢO ........................................................................................................... 65

DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT

Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh

Thuật toán BIRCH BIRCH

Balanced Interative Reducing and Clustering using Hierarchies

Thuật toán CLARA CLARA Clustering LARge Applications

Cơ sở dữ liệu CSDL DataBase

Thuật toán CURE CURE Clustering Using Representatives

Thuật toán DBSCAN

DBSCAN Density-Based Spatial Clustering of Applications with Noise

Thuật toán DENCLUE DENCLUE DENsity – based CLUstEring

KDD Knowledge Discovery in Databases

Khai phá tri thức trong cơ sở dữ liệu

Khai phá dữ liệu KPDL Data Mining

Khai phá tri thức KPTT Knowledge Discovery

Thuật toán AMOSA AMOSA

Archived multiobjective simulated annealing

Phân cụm dữ liệu PCDL Data Clustering

Giải thuật SA SA Simulated Annealing

Giải thuật GA GA Genetic Algorithms

DANH MỤC CÁC HÌNH VẼ

Hình 1.1 Mô phỏng vấn đề PCDL 10

Hình 1.2 Quá trình phân cụm tập điểm thành 3 cụm theo k-means 13

Hình 1.3 Trường hợp của hàm chi phí cho phân cụm k-medoid 14

Hình 1.4 Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids 16

Hình 1.5 Phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu 17

Hình 1.6 Một cây cấu trúc CF 19

Hình 1.7 Phương pháp Chameleon 21

Hình 1.8 Phân cụm dựa trên phương pháp mật độ [4] 24

Hình 1.9 Ba tầng liên tiếp nhau của cấu trúc STING 25

Hình 1.10 CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc 26

Hình 2.1 Minh họa cho bánh xe sổ số với quần thể có 5 cá thể 33

Hình 2.2 Sơ đồ cấu trúc thuật toán di truyền 35

Hình 2.3 40

Số lượng của sự thống trị của hai giải pháp A và B là diện tích của hình chữ nhật được tô đậm.

Hình 2.4 41

Trường hợp khác nhau khi new-pt bị thống trị bởi curent-pt. a) new-pt không bị thống trị bởi các giải pháp trong kho Archive ngoại trừ curent- pt. b) Một số giải pháp trong kho Archive thống trị new-pt.

Hình 2.5a New-pt được thống trị bởi k điểm thuộc Archive 42

Hình 2.5b New-pt không thống trị những điểm khác thuộc Archive 42

Hình 2.5c New-pt thống trị k điểm thuộc Archive 43

Hình 2.6a New-pt thống trị current-pt nhưng k điểm thuộc Archive lại thống trị 43

new-pt

Hình 2.6b New-pt không thống trị những điểm thuộc Archive nhưng lại thống trị 44

7 current-pt nếu nó thuộc Archive.

Hình 2.6c New-pt thống trị k điểm thuộc Archive 44

Hình 3.1 Ví dụ về khoảng cách đối xứng điểm 50

Hình 3.2 Các bước chính của thuật toán VAMOSA 52

Hình 3.3 53

Các bước chính của quá trình phân điểm dữ liệu đến k nhóm dữ liệu dựa vào khoảng cách đối xứng điểm

Hình 4.1 Giao diện khi chạy chương trình 56

Hình 4.2 Mảng lưu trữ của tập dữ liệu Over_3 57

Hình 4.3 Kết quả phân cụm của phương án 1 là 3 cụm. 58

Hình 4.4 Kết quả phân cụm của phương án 2 là 4 cụm. 58

Hình 4.5 Kết quả phân cụm của phương án 3 là 5 cụm. 59

Hình 4.6 Kết quả phân cụm của phương án 4 là 6 cụm. 59

Hình 4.7 Kết quả phân cụm của phương án 5 là 7 cụm 60

Hình 4.8 Mảng lưu trữ của tập dữ liệu Iris 60

Hình 4.9 Kết quả phân cụm của phương án 1 là 3 cụm. 61

Hình 4.10 Kết quả phân cụm của phương án 2 là 4 cụm. 61

Hình 4.11 Kết quả phân cụm của phương án 3 là 5 cụm. 62

Hình 4.12 Kết quả phân cụm của phương án 4 là 6 cụm. 62

8 LỜI MỞ ĐẦU

Phân cụm dữ liệu là bài toán thuộc vào lĩnh vực học máy không giám sát và đang được ứng dụng rộng rãi để khai thác thông tin từ dữ liệu. Nó có nhiệm vụ tổ chức một tập các đối tượng dữ liệu thành các cụm sao cho những đối tượng trong cùng một cụm thì “tương tự” nhau trong khi các đối tượng trong các cụm khác nhau thì “kém tương tự” nhau.

Trong cuộc sống, một cá nhân, hay một tổ chức thường bị đặt vào tình huống phải lựa chọn phương án tối ưu để giải quyết một vấn đề nào đó. Khi ấy chúng ta phải tiến hành thu thập, phân tích và chọn lựa thông tin nhằm tìm ra một giải pháp tốt nhất để hành động. Các phương án đề xuất ấy có thể giải quyết một hay nhiều vấn đề cùng một lúc tùy thuộc vào tình huống và yêu cầu đặt ra của chúng ta. Trong toán học có rất nhiều lý thuyết cơ sở làm nền tảng giúp tìm ra một phương án tối ưu để giải quyết vấn đề như: lý thuyết thống kê, lý thuyết quyết định, lý thuyết tối ưu, vận trù học,…Do tính ưu việt và hiệu quả, tối ưu hóa nhiều mục tiêu là một trong những lý thuyết toán học ngày càng được ứng dụng rộng rãi trên nhiều lĩnh vực như: kỹ thuật công nghệ, hàng không, thiết kế, tài chính,…

Tối ưu hóa nhiều mục tiêu có nghĩa là tìm phương án tốt nhất theo một nghĩa nhất định nào đó để đạt được (cực đại hay cực tiểu) nhiều mục tiêu cùng một lúc và một phương án như vậy thì ta gọi là phương án lý tưởng. Trong một bài toán tối ưu nhiều mục tiêu thường thì các mục tiêu xung đột với nhau nên việc cố gắng làm “tăng” giá trị cực đại hay cực tiểu một mục tiêu có thể sẽ làm “giảm” gía trị cực đại hay cực tiểu của các mục tiêu khác nên việc tồn tại phương án lý tưởng là rất hiếm. Vì vậy cách tốt nhất là tìm một phương án nhằm thỏa mãn tất cả các yêu cầu các mục tiêu trong một mức độ chấp nhận được và phương án như thế gọi là phương án thỏa hiệp của các hàm mục tiêu.

Có rất nhiều định nghĩa khác nhau đề cập đến phương án/nghiệm tối ưu như: Pareto, Borwein, Benson, Geoffrion, Kuhn – Tucker,… Các định nghĩa này thường có sự tương quan với nhau và chúng được biểu hiện cụ thể thông qua các định lý, mệnh đề và tính chất. Như chúng ta đã biết một trong những cơ sở để định nghĩa về nghiệm tối ưu là quan hệ thứ tự trong không gian nhất là quan hệ hai ngôi.

Ngoài phần kết luận, cấu trúc nội dung của luận văn bao gồm 4 chƣơng:

Chương 1: Phân cụm dữ liệu

Chương 1 tập trung trình bày tổng quan về PCDL, đây là một hướng tiếp cận trong Data Mining. Trong đó đi sâu phân tích chi tiết các vấn đề cơ bản: khái niệm PCDL và ý nghĩa của nó trong thực tiễn; trình bày một số phương pháp PCDL và giải thuật điển hình của mỗi phương pháp phân cụm.

9 Chương 2: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

Để làm rõ hơn kỹ thuật PCDL đa mục tiêu, chương 2 trình bày một số khái niệm cơ bản và sự khác biệt cơ bản của phân cụm dữ liệu một mục tiêu và phân cụm dữ liệu đa mục tiêu. Và trình bày một số kỹ thuật tối ưu hóa cụm đặc biệt tìm hiểu về kỹ thuật tối ưu hóa cụm theo kỹ thuật SA - Thuật toán tối ưu hóa AMOSA theo khoảng cách đối xứng mới.

Chương 3:Thuật toán VAMOSA - Thuật toán phân cụm dựa trên tính đối xứng

Trong chương 3 tìm hiểu rõ kỹ thuật phân cụm đa mục tiêu dựa trên thuật toán VAMOSA được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm [3.4.3]: Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14]. Chỉ số Sym - chỉ số dựa trên khoảng cách đối xứng [15, 11]. Hai chỉ số này được tối ưu hóa đồng thời để xác định chính xác số phân cụm trong bộ dữ liệu. Do vậy, kỹ thuật này có thể phát hiện được số cụm thích hợp và phân vùng phù hợp từ các bộ dữ liệu.

Chương 4: Kết quả thử nghiệm

Chương 4, tiến hành cài đặt thuật toán và thử nghiệm trên ba bộ dữ liệu trong đó có bộ dữ liệu thực tế và rút ra được kết quả nhất định. Thuật toán đưa ra kết quả số cụm phù hợp với bộ dữ liệu đưa vào.

Cuối cùng là kết luận, hướng phát triển, tài liệu tham khảo và phụ lục. Phần kết luận trình bày tóm tắt kết quả thu được và đề xuất hướng nghiên cứu tiếp theo.

CHƢƠNG I. PHÂN CỤM DỮ LIỆU

1.1. Phân cụm dữ liệu

Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức được ứng dụng rộng rãi và đa dạng trong các ngành khoa học như sinh học, y học, tâm lý học, ngành marketting, thị giác máy tính và điều khiển học. PCDL (Data clustering) là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" (Dissimilar) với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tượng theo hình dạng tự nhiên. Các thuật toán phân cụm hướng tới việc tìm kiếm cấu trúc trong dữ liệu. Nói cách khác, phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unsupervised learning or automatic classfication) trong lĩnh vực nhận dạng mẫu (Patterm Recognition) nói riêng và trong trí tuệ nhân tạo nói chung. Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó [3, 10].

Dựa vào khám phá cấu trúc dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tượng trong cùng một cụm thì tương tự nhau so với các đối tượng khác cụm. Trong các bài toán này, ta không có thông tin về dữ liệu có nhãn mà chỉ đơn thuần dựa vào tính tương đồng của các đối tượng dữ liệu để phân lớp nên gọi tiếp cận này thuộc loại hướng dữ liệu (data driven).

Ví dụ minh họa về phân cụm dữ liệu như hình 1.1 sau:

Hình 1.1: Mô phỏng vấn đề PCDL

Có nhiều thuật toán phân cụm dựa trên các cách tiếp cận khác nhau về liên quan của đối tượng (tính tương đồng), J. Han và M. Kamber [10] phân làm 4 loại chính:

 Phương pháp phân hoạch (Partition Based Data Clustering).

 Phương pháp phân cấp (Hierarchical Data Clustering).

 Phương pháp dựa trên mật độ (Density Based Data Clustering).

 Phương pháp dựa trên lưới (Grid Based Data Clustering).

Mỗi một phương pháp phân cụm dữ liệu đều có ưu, nhược điểm riêng, 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ụm dữ liệu. Một thuật toán phân cụm phù hợp cho một ứng dụng phải thỏa mãn cả hai tiêu chuẩn về chất lượng và tốc độ yêu cầu.

Trước khi giới thiệu các phương pháp phân cụm, ta xem xét vấn đề chuẩn hóa dữ

liệu, một số khái niệm như chiều và phần tử nhiễu.

1.2. Các phƣơng pháp và các thuật toán phân cụm dữ liệu [2]

Phân cụm dữ liệu biểu diễn mỗi quan hệ giữa các đối tượng trong ma trân tương đồng. Nếu các đối tượng được đặc tả như là các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như là khoảng cách Euclidean. Ma trận mẫu và ma trận tương đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân cụm được xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể được phân theo một trong bốn phương pháp sau đây:

 Phương pháp dựa vào phân vùng.

 Phương pháp phân cấp.

 Phương pháp dựa trên mật độ.

 Phương pháp dựa trên lưới.

1.2.1. Các phƣơng pháp phân vùng

Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân . Phương cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [3]. Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới.

Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm. Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng

khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm.

Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng.

1.2.1.1. Phương pháp k-means

Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng giữa các cụm lại có sự khác biệt khá rõ [3]. Sự giống nhau trong cụm được đánh giá theo giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm của trọng lực” của cụm.

Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn. Đối với mỗi đối tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng cách giữa đối tượng và trung bình của đoạn. Nó sau đó sẽ tính trung bình mới cho mỗi đoạn. Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau được sử dụng:

Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra, là trung bình của

cụm (cả x và là đa chiều). Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức

có thể. Thủ tục k trung bình được tổng kết ở hình 1.2:

Thuật toán k means:

Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng

Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm

Thủ tục

1. Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm

2. Lặp

13 2.1. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so với các cụm khác

2.2. Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng giá trị trung bình tọa độ các đối tượng trong cụm.

3. Cho đến khi giá trị hàm mục tiêu không thay đổi

Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường <

(a) (b) (c)

Hình 1.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means

1.2.1.2. Phương pháp k-medoids

Thuật toán k-means với đối tượng khác biệt (đối tượng có sự khác biệt so với phần lớn các đối tượng trong tập) bởi vì một đối tượng với giá trị rất lớn có thể thay đổi sự phân phối dữ liệu.

Làm thế nào thay đổi thuật toán để làm giảm bớt sự nhạy cảm như vậy? Thay cho việc lấy giá trị trung bình của các đối tượng trong một phân cụm như điểm tham chiếu, chúng ta có thể lấy những đối tượng thực để biểu diễn phân cụm, sử dụng một đối tượng biểu diễn một phân cụm. Mỗi đối tượng đang tồn tại được phân cụm với đối tượng biểu diễn mà giống nó nhất. Phương pháp phân cụm được thực hiện dựa trên nguyên lý tối thiểu tổng của sự khác biệt giữa mỗi đối tượng và điểm tham chiếu của nó. Đó là, một chuẩn lỗi-tuyệt đối (absolute-error criterion) được dùng như sau:

trong không gian biểu diễn một đối tượng đưa ra trong phân cụm Trong đó E là tổng lỗi tuyệt đối của mọi đối tượng trong tập dữ liệu; p là điểm ; và oj là đối tượng

biểu diễn của . Nói chung, trạng thái lặp đến tận khi mỗi đối tượng biểu diễn thực sự là

medoid, hoặc đối tượng nằm ở trung tâm

Xem xét trạng thái phân cụm k-medoid. Các đối tượng biểu diễn khởi tạo (hoặc hạt giống) được chọn ngẫu nhiên.Việc thay thế các đối tượng biểu diễn bởi đối tượng không biểu diễn còn lại sẽ được thực hiện nếu chất lượng của kết quả phân cụm được cải tiến. Chất lượng này được đánh giá bằng cách sử dụng một hàm chi phí để đo lường sự khác nhau trung bình giữa một đối tượng và đối tượng biểu diễn trong phân cụm của nó. Để xác định một đối tượng không biểu diễn orandom là sự thay thế tốt của đối tượng biểu diễn oj hiện tại cần kiểm tra 4 trường hợp sau đối với mỗi đối tượng không biểu diễn p. Xem mô tả trong hình 1.3

- Trường hợp 1: p hiện tại thuộc đối tượng biểu diễn oj. Nếu oj bị thay bằng orandom j thì gán p thuộc

và p gần với một trong những đối tượng biểu diễn khác oi, với i oi.

- Trường hợp 2: p hiện tại thuộc đối tượng biểu diễn oj. Nếu oj bị thay bằng orandom

và p gần nhất với orandom thì gán p thuộc orandom.

- Trường hơp 3: Nếu p hiện tại thuộc đối tượng biểu diễn oi (i

j). Nếu oj bị thay bằng orandom như một đối tượng biểu diễn và p gần nhất với oi, thì để nguyên không thay đổi.

j). Nếu oj được thay bằng

- Trường hợp 4: hiện tại p thuộc đối tượng biểu diễn oi (i orandom và p gần orandom nhất, p được gán thuộc orandom.

Hình 1.3: Trường hợp của hàm chi phí cho phân cụm k-medoid

Hàm chi phí tính được tính dựa trên sự khác nhau trong giá trị lỗi-tuyệt đối nếu một đối tượng biểu diễn hiện tại được thay bằng một đối tượng không biểu diễn. Giả sử

ban đầu cụm được biểu diễn bởi oj có tổng giá trị lỗi tuyệt đối là E 1, sau đó cụm được biểu diễn lại bởi giá trị orandom có tổng giá trị lỗi tuyệt đối là E2. Khi đó tổng chi phí chuyển đổi là |E 1 - E 2|. Nếu tổng chi phí là âm, thì oj được thay thế hoặc đổi chỗ với orandom .

Nếu tổng chi phí dương, đối tượng biểu diễn hiện tại oj được chấp nhận, và không

có thay đổi trong việc lặp.

Thuật toán PAM (Partitioning Around Medoid) được chỉ ra bên dưới. Thuật toán thực hiện phân n đối tượng làm k cụm, độ phức tạp là O(k(n-k)2). Đối với các giá trị lớn của n và k, sự tính toán như vậy rất tốn chi phí.

Thuật toán k-medoid PAM, một trạng thái k-modoid cho cụm dựa trên medoid hoặc các đối tượng trung tâm

Đầu vào: Số phân cụm k, tập dữ liệu D chứa n đối tượng.

Đầu ra: Một tập k phân cụm.

Thủ tục

1. Chọn ngẫu nhiên k (oj (j = 1...k)) đối tượng trong D như các đối tượng biểu diễn khởi tạo hoặc điểm hạt giống

2. Lặp lại

2.1. Gán mỗi đối tượng còn lại cho phân cụm với đối tượng biểu diễn gần nhất

2.2. Lựa chọn ngẫu nhiên một đối tượng không biểu diễn, orandom.

2.3. Tính tổng chi phí, S = Ej-Erandom, của việc hoán chuyển đối tượng biểu diễn, oj với orandom.

2.4. Nếu S<0 thì hoán đổi oj và oramdon để hình thành tập mới k đối tượng biểu diễn.

3. Khi không có sự thay đổi thì kết thúc.

Phương thức k-medoid đáng tin cậy hơn k-trung bình bởi vì một medoid bị tác

động bởi các nhân tố bên ngoài hoặc các giá trị rất lớn ít hơn k trung bình.

Hình 1.4 : Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids

1.2.1.3. Phương pháp phân cụm trong cơ sở dữ liệu lớn CLARANS

Phương pháp k-medoid chỉ thích hợp với việc sử dụng cho tập dữ liệu nhỏ. Trong cơ sở dữ liệu lớn, người ta sử dụng một phương pháp dựa trên mẫu, gọi là CLARA (Clustering Large Application).

Ý tưởng của phương pháp này là thay cho việc dùng toàn bộ tập dữ liệu trong sự phân cụm, một phần nhỏ của dữ liệu được chọn như đại diện cho tập dữ liệu. Các medoid được chọn từ tập dữ liệu này sử dụng PAM. Nếu mẫu được chọn theo cách ngẫu nhiên, nó gần như đại diện cho tập dữ liệu gốc. Các đối tượng biểu diễn được chọn sẽ giống như trong toàn bộ cơ sở dữ liệu. CLARA dùng nhiều mẫu trong tập dữ liệu, sử dụng PAM trên mỗi mẫu và trả lại phân cụm tốt nhất của nó. CLARA có thể làm việc với tập dữ liệu lớn hơn PAM. Độ phức tạp của mỗi vòng lặp là O(ks2 +k(n-k)), trong dó s là kích thước mẫu, k là số phân cụm, và n là tổng số đối tượng.

Độ chính xác của thuật toán CLARA phụ thuộc vào kích thước mẫu. Chú ý rằng PAM tìm kiếm k điểm trung tâm trong tập dữ liệu đưa ra, trong khi đó CLARA tìm kiếm k điểm trung tâm trong tập mẫu được lựa chọn. CLARA không thể tìm được sự phân cụm chính xác nhất nếu không tìm được tập mẫu đại diện chính xác. Ví dụ, Oi là điểm trung tâm tốt nhất của một trong k cụm nhưng lại không được lựa chọn trong mẫu, CLARA sẽ không bao giờ tìm được cách phân cụm một cách chính xác.

Để cải tiến chất lượng của CLARA, một thuật toán phân cụm khác là CLARANS (Clustering Large Applications based upon RANdomized Search) được phát triển và giới thiệu bởi (Ng và Han 1994). CLARANS cũng sử dụng thuật toán k-medoids áp dụng PAM kết hợp với kỹ thuật lấy mẫu. Tuy nhiên, không giống như CLARA, CLARANS không giới hạn các mẫu trong mỗi lần lặp. Trong khi CLARA cố định các mẫu tại tất cả các bước trong quá trình phân cụm, CLARANS lấy ra các mẫu ngẫu nhiên trong từng bước.

1.2.2. Các phƣơng pháp phân cấp

Phương pháp phân cấp là sự phân chia các đối tượng dữ liệu đưa ra theo các cấp. Phương pháp phân cấp có thể được thực hiện theo các cách tích tụ hoặc phân rã. Hướng tích tụ, còn gọi là hướng từ dưới lên (bottom up) bắt đầu với mỗi đối tượng tạo thành một nhóm riêng rẽ. Nó hòa nhập các đối tượng hoặc nhóm bên cạnh (gần nhau) thành một, tới tận khi mọi nhóm được hòa nhập thành một (mức cao nhất của sự phân cấp), hoặc đến tận khi bắt gặp điều kiện kết thúc. Hướng phân rã, còn gọi là từ trên xuống (top down), bắt đầu với mọi đối tượng trong cùng cụm. Trong mỗi vòng lặp, một đoạn được phân chia thành những đoạn nhỏ hơn, tới tận khi mỗi đối tượng tương ứng một đoạn, hoặc tận khi gặp điều kiện kết thúc.

Phương pháp phân cấp có nhược điểm là một khi một bước (hòa nhập hoặc phân chia) được thực hiện, nó có thể không bao giờ thay đổi. Sự cứng nhắc này là chìa khóa đối với sự thành công của nó bởi vì nó dẫn đến chi phí tính toán nhỏ mà không lo lắng về một số sự tổ hợp của các lựa chọn khác nhau, đồng thời cũng là vấn đề chính bởi vì nó không thể sửa các quyết định sai.

1.2.2.1. Phân cụm phân cấp dạng tích lũy và phân chia

Phân cụm phân cấp dạng tích lũy: chiến lược từ dưới lên này bắt đầu bằng việc đặt mỗi đối tượng trong phân cụm của riêng nó và hòa nhập các phân cụm nhỏ thành những phân cụm lớn hơn đến tận khi mọi đối tượng trong một phân cụm đơn hoặc đến khi điều kiện kết thúc được thỏa mãn. Hầu hết các phương thức phân cụm phân cấp thuộc loại này.

Phân cụm phân cấp phân chia: chiến lược này hướng từ trên xuống ngược với chiến lược phân cụm tích lũy dần. Nó phân chia cụm thành những cụm nhỏ hơn đến khi mỗi đối tượng tạo thành một cụm hoặc bắt gặp điều kiện kết thúc.

Hình 1.5: phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu

18 Trong cả hai loại phân cụm phân cấp này, người dùng có thể xác định số cụm mong muốn và điêu kiện kết thúc. Bốn độ đo khoảng cách sử dụng rộng rãi giữa các cụm được chỉ ra bên dưới, trong đó |p-p’| là khoảng cách giữa hai đối tượng hoặc điểm p và p’, và mi là trung bình của cụm Ci và ni là số đối tượng trong Ci.

Khi thuật toán sử dụng khoảng cách nhỏ nhất dmin(Ci,Cj) để đo khoảng cách giữa các phân cụm, nó được gọi là k-nearest neighbor. Khi thuật toán sử dụng khoảng cách xa nhất dmax(Ci,Cj), thuật toán được gọi là thuật toán phân cụm farthest-neighbor.

1.2.2.2. Phương pháp BIRCH

BIRCH (Balanced iterative Reducing and Clustering Using Hierarchies) được thiết kế dành cho việc phân cụm lượng lớn dữ liệu số bằng cách tích hợp phân cụm phân cấp (ở trạng thái khởi đầu phân cụm vi mô) và các phương pháp phân cụm khác như phân cụm lặp (ở trạng thái sau phân cụm vĩ mô). Nó vượt qua hai sự khó khăn của phương thức phân cụm tích lũy: (1) tính mở rộng và (2) khả năng không thể quay lại bước trước.

BIRCH đưa ra hai khái niệm: đặc tính phân cụm và cây đặc tính phân cụm (CF tree), được sử dụng để tổng kết các sự thể hiện phân cụm. Những cấu trúc này giúp phương thức phân cụm đạt được tốc độ tốt và khả năng mở rộng trong cơ sở dữ liệu lớn, hơn nữa làm tăng tính hiệu quả của phân cụm tăng dần và tính linh động của đối tượng đầu vào.

Hãy xem xét sâu hơn các cấu trúc nhắc đến ở trên. Xem xét n đối tượng dữ liệu hoặc điểm có d chiều trong một cụm, chúng ta có thể xác định trung tâm x0, bán kính R, và đường kính D của cụm như sau:

19 Trong đó R là khoảng cách trung bình từ các đối tượng thành viên tới trung tâm, và D là khoảng cách trung bình giữa các cặp trong cụm. Cả R và D phản ánh tính gần gũi của cụm xung quanh trung tâm. Một đặc tính phân cụm (CF) là một vector 3 chiều tổng hợp thông tin về các cụm của đối tượng. Xem xét n đối tượng hoặc điểm có d chiều trong một phân cụm, {xi}, thì CF của cụm được định nghĩa là:

Trong đó n là số lượng điểm của phân cụm, LS là tổng tuyến tính của n điểm

(nghĩa là, LS= ), và SS là tổng bình phương của các điểm (nghĩa là, )

Hình 1.6: Một cây cấu trúc CF

BIRCH áp dụng một kĩ thuật nhiều pha: Thực hiện quét một lần tập dữ liệu tạo ra một phân cụm tốt ban đầu, và các lần quét sau đó được dùng để cải tiến chất lượng. Hai pha chính là:

 Pha 1: BIRCH quét cơ sở dữ liệu để xây dựng một cây CF bộ nhớ ban đầu, có thể được xem như là một sự nén đa cấp của dữ liệu để cố gắng bảo vệ cấu trúc phân cụm có sẵn của dữ liệu

 Pha 2: BIRCH áp dụng một thuật toán phân cụm để phân cụm các node lá của cây CF, cố gắng loại bỏ các phân cụm thừa và nhóm các phân cụm thành một phân cụm lớn hơn.

CF có 2 tham số: tham số nhánh (branching factor) B và ngưỡng T. B quy định số con lớn nhất mà một nút không phải nút lá có thể có, và T xác định đường kính lớn nhất của một phân cụm con.

Ở bước 1, khi một đối tượng được thêm vào một cụm, nếu đường kính của cụm này lớn hơn giá trị ngưỡng thì các cụm sẽ bị phân chia lại. Sau quá trình phân chia cụm lại ta được một tập các cụm mới. Ở bước 2, có thể áp dụng một thuật toán phân cụm bất kì nào để thực hiện việc phân tách hoặc hợp nhất các cụm lại.

Thuật toán BIRCH có độ phức tạp tính toán là O (n), trong đó n là số lượng đối

tượng được phân cụm.

1.2.2.3. Phương pháp ROCK

20 ROCK (Robust clustering using links) là một thuật toán phân cụm phân cấp quan tâm đến khái niệm links (số lượng hàng xóm chung của hai đối tượng) cho dữ liệu với các thuộc tính phân loại. Các thuật toán phân cụm truyền thống cho dữ liệu phân cụm với thuộc tính Boolean và phân loại sử dụng các hàm khoảng cách .Tuy nhiên, thí nghiệm chỉ ra rằng các độ đo khoảng cách như vậy không thể dẫn đến các phân cụm chất lượng cao khi phân cụm dữ liệu phân loại. Hơn nữa, hầu hết các thuật toán phân cụm chỉ đánh giá sự giống nhau giữa các điểm khi phân cụm. Đó là, ở mỗi bước, các điểm giống nhau nhất được hòa nhập vào trong một cụm duy nhất, hướng “cục bộ” này có thể dẫn tới lỗi. Ví dụ, hai phân cụm tách biệt có thể có ít điểm hoặc các thành phần bên ngoài gần nhau, và do đó, dựa trên sự giống nhau giữa các điểm để tạo các quyết định phân cụm có thể dẫn đến việc hai phân cụm bị hòa nhập. ROCK quan tâm đến hướng toàn cục hơn để phân cụm bằng việc xem xét quan hệ láng riềng của các cặp điểm riêng rẽ. Nếu hai điểm giống nhau có cùng quan hệ hàng xóm, chúng có thể thuộc cùng cụm do đó có thể được hòa nhập.

Hai điểm, pi và pj, là hàng xóm nếu sim (pi, pj)

, trong đó sim là một hàm thể là một ngưỡng do người dùng xác định. Chúng ta có thể chọn hiện sự giống nhau và sim là một độ đo dạng khoảng cách hoặc thậm chí không phải độ do dạng khoảng cách mà được chuẩn hóa để những giá trị của nó nằm trong khoảng 0 và 1, với những giá trị lớn hơn chỉ ra rằng những điểm này là giống nhau hơn. Số lượng links giữa pi và pj được xác định như số lượng hàng xóm giữa pi và pj. Nếu số lượng links giữa hai điểm lớn, có khả năng cao là hai điểm đó cùng thuộc cụm. Bằng việc xem xét các điểm dữ liệu có quan hệ hàng xóm giữa cặp điểm riêng rẽ, ROCK đáng tin cậy hơn các phương pháp phân cụm chuẩn chỉ tập trung vào sự giống nhau của các điểm.

1.2.2.4. Phương pháp Chameleon.

Chameleon là một thuật toán phân cụm phân cấp sử dụng mô hình động để xác định sự giống nhau giữa các cặp cụm [2]. Nó dựa trên việc xem xét điểm yếu hai thuật toán phân cụm phân cấp là ROCK và CURE. ROCK liên quan đến lược đồ nhấn mạnh sự tương tác cụm trong khi bỏ qua thông tin liên quan sự giống nhau cụm. CURE xem xét sự giống nhau cụm và bỏ qua tính tương tác cụm. Trong Chameleon, sự giống nhau cụm được đánh giá dựa trên việc các đối tượng trong cụm kết nối với nhau thế nào và quan hệ gần gũi của các cụm. Do đó, hai cụm được hòa nhập nếu quan hệ tương tác giữa chúng cao và chúng gần nhau. Do đó, Chameleon không dựa trên mô hình tĩnh và phụ thuộc người dùng và có thể điều chỉnh tự động đối với các đặc tính bên trong của các cụm được hòa nhập. Tiến trình hòa nhập làm tăng khả năng khám phá của các phân cụm tự nhiên và áp dụng các kiểu của dữ liệu cũng như một hàm thể hiện sự giống nhau có thể được xác định.

21 Hướng chính của Chameleon được đưa ra hình 1.7. Chameleon sử dụng hướng đồ thị k-nearest neighbor để xây dựng một đồ thị thưa, trong đó mỗi đỉnh của đồ thị biểu diễn một đối tượng dữ liệu, và tồn tại một cạnh giữa hai đỉnh (hai đối tượng) nếu một đối tượng thuộc tập k đối tượng giống nhất của đối tượng còn lại. Cạnh này được đánh trọng số để phản ánh sự giống nhau giữa các đối tượng. Chameleon sử dụng một thuật toán cụm đồ thị để cụm đồ thị k nearest neighbor thành một số lượng lớn của các phân cụm nhỏ. Nó sau đó sử dụng thuật toán phân cụm phân cấp dạng tích lũy để hòa nhập các phân cụm con dựa trên sự giống nhau của chúng. Để xác định các cặp phân cụm con giống nhau nhất, nó tính đến cả sự tương tác kết nối cũng như tính gần gũi của các cụm.

Hình 1.7: Phương pháp Chameleon

Thuật toán cụm đồ thị cụm đồ thị k-nearest neighbor để tối thiểu hóa sự giảm bớt cạnh. Đó là, một phân cụm C được phân cụm thành hai phân cụm nhỏ Ci và Cj ,để tối thiểu hóa trọng số các cạnh mà C được phân chia thành Ci và Cj. Sự giảm bớt cạnh được chỉ ra bằng EC(Ci,Cj) và lượng giá tính kết nối tương tác giữa các phân cụm Ci và Cj.

Chameleon xác định tính giống nhau giữa hai cụm Ci và Cj dựa vào hai tham số

tính kết nối tương tác quan hệ RI(Ci , Cj) và tính gần gũi RC(Ci, Cj).

Trong đó là giá trị trung bình trọng số của các cạnh nối các đỉnh trong Ci

(hoặc ) là giá trị trung bình của các cạnh cụm Ci

và các đỉnh trong Cj, và (hoặc Cj).

22 1.2.3. Phƣơng pháp phân cụm dựa trên mật độ

Hầu hết các phương pháp phân cụm các đối tượng dựa trên khoảng các giữa các đối tượng. Những phương pháp như vậy có thể chỉ tìm thấy các cụm dạng hình cầu và gặp khó khăn khi tìm kiếm các cụm có hình dạng bất kì. Các phương pháp cụm được phát triển dựa trên khái niệm mật độ. Ý tưởng chung là tiếp tục làm gia tăng cụm đưa ra dựa vào mật độ (số lượng đối tượng hoặc các điểm dữ liệu) trong “khoảng” vượt ra ngoài ngưỡng, nghĩa là, đối với mỗi điểm dữ liệu trong một cụm được đưa ra, hàng xóm (neighbourhood) trong một bán kính đưa ra phải chứa ít nhất một số tối thiểu các điểm. Phương pháp như vậy có thể được sử dụng để lọc ra các nhiễu, và khám phá các cụm có hình dạng bất kì.

1.2.3.1. Phương pháp DBSCAN

Phương pháp DBSCAN (Density-Based Spatial Clustering of Application witch Noise) là một thuật toán phân cụm dựa trên mật độ. Thuật toán xây dựng các vùng với mật độ lớn thích hợp vào trong các phân cụm và khám phá các phân cụm có hình dạng khác nhau trong cơ sở dữ liệu không gian với các nhiễu. Nó định nghĩa một phân cụm như một tập tối đa của các điểm phụ thuộc mật độ.

Ý tưởng chính của phân cụm dựa trên mật độ là đối với mỗi đối tượng thuộc nhóm -hàng xóm của đối tượng (-neighborhood) có được gọi là

vùng lân cận trong bán kính chứa ít nhất MinPts đối tượng.

 Nếu -hàng xóm của một đối tượng chứa ít nhất một số tối thiểu MinPts các

đối tượng, thì đối tượng đó gọi là đối tượng trung tâm (core object).

 Xem xét một tập các đối tượng D, chúng ta nói rằng một đối tượng p thuộc -hàng xóm

trong phạm vi mật độ trực tiếp của đối tượng q nếu p nằm trong của đối tượng q và q là đối tượng trung tâm.

 Một đối tượng p nằm trong phạm vi mật độ của đối tượng q đối với

và MinPts trong một tập các đối tượng D, nếu có một chuỗi các đối tượng p1,…, pn trong đó p1=q và pn=p và pi+1 nằm trong phạm vi mật độ trực tiếp của pi đối với và MinPts, với 1 i n, pi D.

 Một đối tượng p nằm trong phạm vi mật độ liên kết của đối tượng q đối với

và MinPts trong một tập các đối tượng D, nếu có một đối tượng o D mà cả p và q đều nằm trong phạm vi mật độ của o với và MinPts.

 Các điểm m, p, o là đối tượng trung tâm bởi vi mỗi đối tượng trong phạm vi

đều có ít nhất ba đối tượng khác. q nằm trong phạm vi trực tiếp của m, m nằm trong phạm vi trực tiếp của p và ngược lại q nằm trong phạm vi gián tiếp của p,

23 tuy nhiên p không nằm trong phạm vi của q vì q không phải là đối tượng trung tâm. o, r và s đều có liên kết mật độ.

Một phân cụm dựa trên mật độ là một tập các đối tượng có liên kết mật độ được làm tối đa hóa đối với phạm vi liên kết mật độ. Những đối tượng không thuộc cụm nào xem như là nhiễu.

DBSCAN sẽ tìm trong các cụm bằng cách kiểm tra

-hàng xóm cho mỗi điểm -hàng xóm của một điểm p chứa nhiều hơn MinPts điểm, một trong cơ sở dữ liệu. Nếu cụm mới với p là đối tượng trung tâm được tạo. DBSCAN tập hợp các đối tượng trong phạm vi mật độ trực tiếp cho những đối tượng trung tâm, có thể thực hiện việc hòa nhập một số ít cụm trong phạm vi mật độ. Tiến trình kết thúc khi không có điểm mới nào có thể thêm vào bất kì cụm nào.

1.2.3.2. Phương pháp DENCLUE (Density Based Clustering)

DENCLUE là một phương pháp phân cụm dựa trên một tập các hàm phương pháp mật độ. Phương pháp được xây dựng trên những ý tưởng sau: (1) sự tác động của mỗi điểm dữ liệu có thể được mô hình hóa hình thức sử dụng một hàm toán học, gọi là hàm tác động (ingluence function), mô tả tác động của một điểm dữ liệu nằm trong quan hệ hàng xóm của nó; (2) toàn thể mật độ của không gian dữ liệu có thể được mô hình hóa như tổng của hàm tác động cho tất cả các điểm dữ liệu; và (3) các phân cụm có thể được xác định bằng cách xác định các density attractor, trong đó các density attractor là các cực đại cục bộ của toàn bộ hàm mật độ.

chiều. Hàm tác động của điểm dữ liệu y trên x là một hàm, Giả sử x và y là các đối tượng hoặc điểm trong Fd, một không gian đầu vào d , được định nghĩa

như sau:

Hàm này phản ánh tác động của y lên x. Theo nguyên tắc, hàm tác động có thể là một hàm ngẫu nhiên mà có thể được xác định bởi khoảng cách giữa hai điểm trong một quan hệ hàng xóm. Hàm khoảng cách d(x,y), nên là tương phản và đối xứng, như là hàm khoảng cách Euclid. Nó được sử dụng để tính toán một hàm dạng:

hoặc dùng để tính hàm tác động Gaussian

, hàm mật độ ở x là: 24 Hàm mật độ ở một đối tượng hoặc một điểm x Fd được định nghĩa như một tổng của các hàm tác động của mọi điểm dữ liệu. Đó là, tổng tác động lên x của tất cả mọi điểm dữ liệu. Xem xét n đối tượng điểm, D={x1… xn}

Ví dụ, hàm mật độ có kết quả từ hàm tác động Gaussian là:

Từ hàm mật độ, chúng ta có thể xác định gradient của hàm và density attractor, cực trị địa phương của toàn bộ hàm mật độ. Một điểm x được nói là bị thu hút mật độ đối với một density attractor x* nếu có một tập các điểm x0, x1… xk mà x0=x, xk=x* và gradient của xi-1 nằm trong hướng của xi trong đó 0

Hình 1.8: Phân cụm dựa trên phương pháp mật độ [4]

1.2.4. Các phƣơng pháp phân cụm dựa trên lƣới

Các phương pháp phân cụm dựa vào mật độ như DBSCAN, OPTICS phải đổi có thể sẽ thất bại trong không gian dữ liệu với số chiều cao và phải thiết lập các tham số và MinPts. Để nâng cao hiệu quả của phân cụm, tiếp cận phân cụm dựa trên lưới sử dụng cấu trúc dữ liệu dạng lưới. Tiếp cận này phân chia không gian dữ liệu vào một số lượng hữu hạn các ô tạo nên dạng hình lưới. Tiện lợi chính của tiếp cận này là thời gian xử lý nhanh và nó không phụ thuộc vào số lượng các đối tượng dữ liệu, chỉ phụ thuộc vào số lượng các ô ở mỗi chiều trong không gian lượng hóa.

Một số thuật toán cơ bản của tiếp cận dựa trên lưới là thuật toán STING, thuật toán này tìm kiếm theo thống kê các thông tin nằm trong các ô. Thuật toán WaveCluster phân cụm dữ liệu sử dụng phương pháp biến đối sóng và thuật toán CLIQUE trình bày cách tiếp cận dựa vào mật độ và dựa vào lưới để phân cụm dữ liệu nằm trong không gian với số chiều lớn. Xem chi tiết ở [5]

1.2.4.1. Thuật toán STRING: A STatistical INformation Grid approach

STING là một cấu trúc dữ liệu đa mức dựa trên lưới, trong không gian dữ liệu được chia thành các ô hình chữ nhật. Có các ô tương ứng với các mức khác nhau để giải quyết bài toán, cách phân chia ô như vậy tạo ra một cấu trúc phân cấp: mỗi ô ở mức cao được phân chia thành một số ô ở mức thấp hơn tiếp theo. Thông tin thống kê liên quan tới thuộc tính của mỗi ô như mean, maximum, minimum được tính toán trước và lưu trữ. Những thông tin thông kê này sẽ trợ giúp cho quá trình truy vấn như sau:

Hình 1.9: Ba tầng liên tiếp nhau của cấu trúc STING

Trong hình 1.9 trình bày 3 tầng liên tiếp nhau của cấu trúc STING, mỗi ô ở tầng trên được phân chia thành bốn ô ở tầng tiếp theo. Các tham số thống kê ở mức cao có thể được dễ dàng tính toán bởi các tham số từ các ô ở mức thấp hơn. Các tham số này bao gồm: số lượng đối tượng trong ô: count, giá trị trung bình: mean, độ lệch chuẩn: s, giá trị nhỏ nhất của thuộc tính của các đối tượng trong ô: min, giá trị lớn nhất của thuộc tính của các đối tượng trong ô: max và kiểu phân bố trong các ô. Dữ liệu được đưa vào trong cấu trúc lưới bắt đầu từ mức thấp nhất. Các tham số count, m, s, min, max ở mức này được tính toán trực tiếp từ dữ liệu. Giá trị của phân bố có thể được đặt bởi người sử dụng. Kiểu phân bố ở ô mức cao được tính toán dựa trên các kiểu phân bố ở các ô tương ứng ở mức thấp kề nó theo một ngưỡng cho trước. Nếu các phân bố ở mức thấp giống nhau và bị lỗi khi kiểm tra bởi ngưỡng, kiểu phân bố ở ô mức cao sẽ là không xác định (được đặt là none).

Để thực hiện phân cụm trên cấu trúc lưới, người sử dụng cung cấp mật độ ở các ô như là tham số đầu vào. Sử dụng tham số này, áp dụng tiếp cận Top-down, phương pháp dựa trên lưới tìm các vùng có mật độ chấp nhận được bằng việc thực hiện các thao tác sau:

Một tần với cấu trúc phân cấp được xác định để thực hiện tiến trình trả lời truy vấn. Tầng này bao gồm một số lượng nhỏ các ô. Với mỗi ô trong tầng, tính khoảng chắc

chắn mà các ô trong đó sẽ trở thành một cụm. Các ô không chắc chắn sẽ bị loại bỏ. Các ô thỏa mãn truy vấn được tinh chỉnh lại bằng cách lặp lại thủ tục tại mức tiếp theo của cấu trúc. Tiến trình này được lặp lại cho đến khi mức cuối cùng được tìm thấy. Tại đó, nếu truy vấn xác định được kết quả, các vùng chứa các ô thích hợp thỏa mãn truy vấn được trả về. Trường hợp khác, dữ liệu rơi vào các ô thiưch hợp được khôi phục lại, và tiến trình tiếp theo được thực hiện cho đến khi chúng gặp các yêu cầu của truy vấn.

1.2.4.2. Thuật toán CLIQUE

Thuật toán CLIQUE tích hợp cả hai phương pháp phân cụm dựa trên mật độ và trên lưới. CLIQUE tìm kiếm các cụm trong không gian con của dữ liệu. Nó được sử dụng rộng rãi để phân cụm dữ liệu đa chiều phân bố thưa thớt và khó nhận ra các cụm trong không gian nhiều chiều này.

Trong thuật toán CLIQUE, không gian dữ liệu được chia thành các khối chữ nhật không chồng nhau lên bằng phân đoạn dọc theo mỗi chiều. Một khối là dày đặc nếu nó nó có số lượng các điểm dữ liệu bao gồm nó vượt quá thông số vào của mô hình. Một cụm được định nghĩa là một tập lớn nhất của các khối dày đặc liên kết với nhau.

CLIQUE thực hiện phân cụm dữ liệu nhiều chiều bằng di chuyển từ không gian ít chiều tới không gian nhiều chiều hơn. Khi tìm các khối có mật độ dày đặc tại vùng k- chiều, CLIQUE sử dụng thông tin phân cụm đạt được từ vùng (k-1)-chiều để làm giảm quá trình tìm kiếm không cần thiết. Điều này được thực hiện bằng cách quan sát thông tin tiên nghiệm được sử dụng trong khám phá luật kết hợp (Argawal & Srikant, 1994). Việc sự dụng thông tin biết trước này nhằm làm giảm quá trình tìm kiếm trong không gian tìm kiếm. Áp dụng tính chất này vào thuật toán QLIQUE có thể phát biểu như sau:

Nếu một khối k-chiều là dày đặc thì đó là các ánh xạ của chúng trong không gian (k-1)-chiều. Điều đó có nghĩa: một khối được xem là mật độ dày đặc trong k-chiều, nếu chúng ta kiểm tra các khối ánh xạ của nó trong không gian (k-1) chiều hình thành các khối và tìm xem nếu có bất kỳ một khối nào thưa thì chúng ta biết rằng khối trong không gian k-chiều sẽ không dày đặc.

27 Hình 1.10: CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc

Thuật toán CLIQUE được minh họa trong hình 1.10. Thông thường, kết quả vùng t m kiếm là nhỏ hơn so với vùng ban đầu. Các khối dày đặc đại diện để xác định các cụm. Điều kiện tìm ra các cụm, thuật toán CLIQUE mô tả thông tin tối thiểu về các cụm như sau: Với mỗi cụm, nó xác định vùng lớn nhất phủ các khối liên kết dày đặc. Sau đó nó xác định một phủ tối thiểu cho mỗi cụm.

CLIQUE tự động tìm các không gian con của không gian có số chiều cao nhất thỏa mãn các cụm mật độ cao tồn tại trong các các không gian con. Nó sẽ không nhạy cảm với thứ tự của các điểm dữ liệu và phân bố dữ liệu. Thuật toán phân chia tuyến tính với cỡ của dữ liệu vào và có thang chia tốt theo số chiều khi số lượng dữ liệu tăng. Tuy nhiên, tính chính xác của các cụm kết quả có thể giảm tại tính đơn giản hóa của phương pháp.

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

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]

Tối ưu hoá là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng đến hầu hết các lĩnh vực. Trong thực tế, việc tìm ra giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng. Phương án tối ưu là những phương án tốt nhất, tiết kiệm chi phí, tài nguyên, sức lực mà lại cho hiệu quả cao. Có thể phát biểu mô hình (bài toán) tối ưu tổng quát như sau:

F(X) => Max (Min) với X D đƣợc gọi là miền ràng buộc.

F ở đây có thể là một hàm vô hướng hay hàm véc tơ, tuyến tính hay phi tuyến. Trong trường hợp F là hàm vô hướng thì ta có mô hình quy hoạch (tối ưu) đơn mục tiêu, còn nếu F là véc tơ thì có mô hình quy hoạch (tối ưu) đa mục tiêu. X có thể là một biến đơn lẻ hay một tập hợp nhiều biến tạo thành một vectơ hay thậm chí là một hàm của nhiều biến khác. Biến có thể nhận các giá trị liên tục hay rời rạc. D là miền ràng buộc của X, thường được biểu diễn bởi các đẳng thức, bất đẳng thức và được gọi là miền phương án khả thi hay phương án chấp nhận được.

2.1.1. Phân cụm dữ liệu đơn mục tiêu

Dạng chính tắc của bài toán tối ưu toàn cục một mục tiêu được biểu diễn như sau:

Trong các bài toán thực tế có thể bổ xung các ràng buộc dạng:

Hàm mục tiêu f(x) và các hàm ràng buộc gj(x) với j=1,2, …,m có thể là tuyến tính hay phi tuyến. Véctơ X có thể bao gồm các thành phần rời rạc hay liên tục hoặc là sự kết hợp giữa các thành phần rời rạc và các thành phần liên tục. Các dạng khác của bài toán tối ưu một mục tiêu đều có thể đưa về dạng chính tắc theo những quy tắc nhất định.

Nếu ký hiệu D là miền các phương án (miền ràng buộc) cho bởi các ràng buộc (i), (ii) hoặc (iii) thì bài toán trên đây có thể viết gọn hơn như sau: f(x) →Max (Min) với x

D. Lúc này, x* D được gọi là phương án tối ưu toàn cục nếu ∀x D ta luôn có:

f(x*) ≤ f(x). Trong trường hợp f(x*) ≤ f(x) chỉ đúng với ∀x D trong một lân cận của

x* thì x* được gọi là phương án tối ưu địa phương.

2.1.2. Bài toán phân cụm dữ liệu đa mục tiêu

Bài toán tối ưu đa mục tiêu tổng quát có thể xem xét dưới dạng sau :

Cực đại hóa các hàm lợi ích :

(2.1)

Với x  X  Rn (2.2)

). Lời giải của

Nói chung không có lời giải đồng thời đạt cực đại của cả k hàm fi ( nó được tìm theo nghĩa tối ưu pareto như sau.

Định nghĩa. Điểm x*  X gọi là tối ưu pareto của bài toán đa mục tiêu (1.1) trên tập X nếu không tồn tại điểm y  X sao cho có ít nhất i  k mà

và

2.1.2.1. Xử ly bài toán đa mục tiêu

Bài toán tối ưu đa mục tiêu được nhiều người quan tâm nghiên cứu và có nhiều phương pháp để tìm tập lời giải pareto. Trong thực hành, việc lựa chọn lời giải thường theo hướng “hỗ trợ quyết định” có thể xử l nó nhờ đưa về các bài toán một mục tiêu.

2.1.2.1.1. Đưa các mục tiêu thứ yếu vào điều kiện ràng buộc

Theo phương pháp này, ta chọn hàm mục tiêu fj mà ta cho là quan trọng nhất và xét bài toán:

(2.3)

Với điều kiện

(2.4)

Trong đó các ci thay đổi theo muốn của người ra quyết định.

2.1.2.1.2. Chọn trọng số ưu tiên

Ta chọn các trọng số sao cho

Độ lớn của i phụ thuộc vào mức độ quan trọng của hàm mục tiêu fi. Với các

đã có ta giải bài toán

(2.5)

Người ta quyết định tùy theo sự thay đổi khi chọn các trọng số i để lựa chọn lời giải.

2.1.3. Chọn phƣơng án trong phân cụm đơn mục tiêu và phân cụm đa mục tiêu

Trong phân cụm đơn mục tiêu thì các phương án so sánh được với nhau. Nếu 2 phương án x và y có hai giá trị hàm mục tiêu f(y) ≤ f(x) thì chấp nhận phương án x. Còn

trong phân cụm đa mục tiêu Một nghiệm x∗ của bài toán (P1) được gọi là nghiệm lý

tưởng nếu: fi(x*) ≤ fi(x) Với ∀x  X, i={1,...,k}. Nói một cách khác một nghiệm lý

tưởng là một nghiệm mà nó phải thỏa mãn tất cả các hàm mục tiêu cần tối ưu ứng với miền chấp nhận được là X. Thực tế thì những nghiệm như vậy rất ít khi tồn tại. Nên ta đưa ra một số khái niệm khác về tối ưu có vẻ “mềm dẻo” hơn đó là nghiệm tối ưu Pareto.

- Một điểm x*  X được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm x

≠ x∗ X sao cho x trội hơn x∗.Nghĩa là f(x) < f(x*).

được gọi là trội hơn nghiệm y = ký hiệu

- Một nghiệm là: x ≤ y, nếu:

- được gọi là nghiệm không trội hơn nghiệm

2.2. Một số giải thuật tối ƣu hóa cụm

2.2.1. Giải thuật di truyền (Genetic Algorithm)

2.2.1.1. Giới thiệu

Thuật giải di truyền cung cấp một cách tiếp cận cho việc học dựa vào mô phỏng sự tiến hóa. Các giả thuyết thường được mô tả bằng các chuỗi bit, việc hiểu các chuỗi bit này tùy thuộc vào ứng dụng, ý tưởng các giả thuyết cũng có thể được mô tả bằng các biểu thức kí hiệu hoặc ngay cả các chương trình máy tính. Tìm kiếm giả thuyết thích hợp bắt

đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học. Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi được cho, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp. Thuật giải di truyền đã được ứng dụng một cách thành công cho những tác vụ học khác nhau và cho các vấn đề tối ưu hóa khác. Ví dụ, chúng đã được dùng để học tập luật điều khiển robot và để tối ưu hóa các thông số học và tôpô cho mạng nơron nhân tạo.

2.2.1.2. Các quy luật cơ bản

2.2.1.2.1. Qúa trình lai ghép

Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau:

Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1. Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12. Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa.

Ví dụ: có hai nhiễm sắc thể bố và mẹ

Chromosome1 11011 | 00100 | 110110

Chromosome 2 10101 | 11000 | 011110

Thực hiện lai ghép ở các đoạn như sau sẽ tạo ra hai con:

Offspring 1 10101 | 00100 | 011110

Offspring 2 11011 | 11000 | 110110

Có thể thấy rằng, hai cá thể bố mẹ với các đặc tính tốt chưa chắc đã cho hai con có đặc tính tốt hơn nó. Tuy nhiên, khả năng tạo ra các cá thể con tốt là rất cao. Nếu hai cá thể con không phải là một lời giải tốt, nó có thể sẽ bị đào thải ở thế hệ tiếp theo.

2.2.1.2.2. Quá trình đột biến

Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. Phép

đột biến là sự thay đổi một vài gen của một nhiễm sắc thể. Toán tử biến dị làm tăng nhanh quá trình hội tụ, nhưng cũng có thể sự tăng đột ngột không có tác dụng hoặc làm hội tụ sớm dẫn đến một lời giải kém tối ưu.

Trong GA cổ điển, mỗi cá thể biểu diễn bởi một chuỗi nhị phân. Phép đột biến tại

một chỗ nào đó là việc đảo bít tương ứng tại vị trí đó.

Ví dụ:

Offspring 11011 00100 110110

Mutated Offspring 11010 00100 100110

2.2.1.2.3. Quá trình chọn lọc

Các cá thể được chọn lọc theo độ thích nghi của chúng để tham gia vào quá trình tiến hóa tiếp theo. Cá thể có độ thích nghi cao hơn sẽ có cơ hội sống sót nhiều hơn và có nhiều con trong trong thế hệ tiếp theo.

Phép chọn lọc các cá thể trong môi quần thể được thựchiện bởi bánh xe sổ số.

Quá trình chọn lọc:Chúng ta quay bánh xe sổ số với n lần ( n là số nghiệm của bài toán). Mỗi lần bánh xe dừng lại, một cá thể tương ứng sẽ bị rơi xuống rãnh và nó được chọn. Cá thể đó được chọn có cơ hội sóng sót và di truyền lại cho thế hệ sau. Với cách thực hiện này, có thể một số cá thể tốt sẽ được chọn nhiều lần, và các cá thể xấu sẽ bị loại bỏ dần.

Mỗi quần thể P(t-1) gồm n nhiễm sắc thể P(t-1) = {v1,v2,…vn}. Có thể xây dựng

bánh xe sổ số như sau:

 Để đánh giá độ thích nghi của quần thể, gọi là tổng độ thích nghi của quần thể

 Tính xác xuất chọn lọc của mỗi cá thể vi:

 Tính xác suất tích lũy qi cho mỗi cá thể vi:

 Thực hiện quá trình chọn lọc bằng các thực hiện chọn quần thể Q(t) từ quần thể

p(t-1) dựa vào bánh xe sổ số:

- Với mỗi số tự nhiên k = 1,2…n. Ta sinh một số thực ngẫu nhiên rk

trong đoạn [0,1]

- Nếu rk< q1 thì chọn cá thể v1, ngược lại, chọn cá thể vi sao cho qi-1 

rk qi , 2  i n

Cá thể 1 có xác suất chọn lọc là 31%, có nghĩa là khi bánh xe sổ số quay, nó có khả

Điểm chọn

Cá thể có xắc suất chọn nhiều nhất

Cá thể có xắc suất chọn ít nhất

năng được chọn là 0.31. Tương tự như vậy với các cá thể 2,3,4,5.

Hình 2.1: Minh họa cho bánh xe sổ số với quần thể có 5 cá thể

2.2.1.2.4. Quá trình tái tạo

Quá trình tái tạo chính là để giữ lại các cá thể tốt hơn và loại bỏ các cá thể xấu hơn

trong quần thể, trong khi vẫn giữ được số lượng của quần thể.

Quá trình tái tạo hay chính là tái sản sinh dùng để:

 Nhận ra các đặc cá thể tốt trong quần thể

 Tạo ra các bản sao của các cá thể tốt nhất

 Loại trừ các cá thể xấu từ quần thể trong khi các cá thể tốt đựoc sao chép

vẫn có được duy trì trong quần thể

Công việc này có thể thực hiện được như sau:

Cho trước xác suất lai và phân cụm và xác suất biến dị pm

34  Với mỗi cá thể vi thuộc Q(t), i = 1,..,n; gán cho nó một giá trị được sinh ngẫu

nhiên tương ứng là u  [0,1]. Nếu u < pc thì vi đuợc đưa vào tập lai.

 Trong tập lai được chia thành các cặp và tiến hành lai ghép để tạo thành thế hệ

sau cho chúng.

 Sau khi lai ghép, với mỗi gen của một cá thể cũng được gán cho một giá trị sinh

ngẫu nhiên u  [0,1], nếu u < Project Manager thì gen đó được đột biến.

 Quá trình trên sẽ tạo ra một quần thể mới P(t) sau đó tiến hành đánh giá để

chọn các cá thể thích nghi nhất.

2.2.1.3. Thủ tục GA

GA cổ điển do Holand đề xuất với mục đích giải quyết bài toán tối ưu sau:

f(x) {x  D  Rn} -> max (min). Trong đó D là hình hộp trong không gian số thực n- chiều Rn, f(x) > 0 với x  D.

Mỗi x trong D được mã hóa bằng một chuỗi nhị phân (x1,x2,….xm) với m là độ dài của chuỗi. Một chuỗi là biểu diễn của nhiễm sắc thể, và mỗi xi là một gen. Để đánh giá khả năng thích nghi của mỗi cá thể, ta xây dựng hàm

Eval(x1,x2,…xm) = f(x), với x là một vectơ tương ứng với (x1,x2,….xm)

Thủ tục GA được xây dựng qua các bước sau:

Bước 1. Thế hệ T = 0; Khởi tạo ngẫu nhiên quần thể ban đầu P(0) gồm n cá thể

Bước 2: Đánh giá độ thích nghi của quần thể

Bước 3: Lặp quá trình tiến hóa cho thế hệ T = T+1

Bước 4: Chọn các cá thể tốt để sinh sản cho thế hệ ( bởi bánh xe sổ số)

Bước 5: Tái tạo quần thể với các cá thể đã chọn bằng các toán tử di truyền

Bước 6: Đánh giá quần thể vừa được tái tạo

Bước 7: Kết thúc khi điều kiện được thỏa mãn;

t = t+1; Chọn Q(t) từ P(t-1) {bằng bánh xe sổ số} Tái tạo P(t) từ Q(t) {bằng các toán tử di truyền} Đánh giá P(t)

t = 0; Khởi tạo P(t); Đánh giá (P(t)); While ( not E) do Begin End;

Procedure GA Begin End;

Trong đó: P(t) là quần thể thế hệ thứ t;

E là điều kiện dừng thuật toán - được xây dựng bởi người dùng cho từng ứng dụng.

Thuật toán di truyền có thể mô tả vắn tắt qua hình sau :

36 Hình 2.2: Sơ đồ cấu trúc thuật toán di truyền

2.2.1.4. Biểu diễn dữ liệu trong GA bằng vector số thực

GA cổ điển biểu diễn một lời giải tiềm năng (một nhiễm sắc thể) bằng một chuỗi mã hóa nhị phân. Nó sử dụng rất hiệu quả trong thuật ngữ của tính toán. Tuy nhiên, đối với bài toán lớn, thì độ dài của các nhiễm sắc thể biểu diễn theo GA cổ điển sẽ rất lớn và việc áp dụng nó là một vấn đề. Do đó sự cân bằng giữa hiệu quả tính toán và tính ứng dụng là nhiệm vụ cần thiết được đưa ra. Hiện nay một số phương pháp để mã hóa thông tin các nhiễm sắc thể được sử dụng là: cây mã hóa, chuỗi số thực,…

Trong phương pháp biểu diễn bằng số thực, ta sử dụng các vector thực trong miền giá trị xác đinh ( thuộc tập D) làm nhiễm sắc thể và xây dựng các toán tử di truyền thích hợp với phương pháp biểu diễn này mà vẫn giữ được đặc thù đã có của GA.

Các toán tử lai:

 Lai đơn giản: thực hiện tráo đổi hai nhóm gen tương tự như GAc cổ điển:

x = (x1,x2, …..,xn) và y = (y1,y2,… ..yn)

Chọn điểm lai k  [1, n-1] (cho trước hoặc ngẫu nhiên), sẽ sinh ra hai cs thể

mới:

o1 = (x1,x2, …..,xk, yk+1,…..yn) ; và o2 = (y1,y2,…..yk, xk+1, …xn)

 Phép lai số học đơn: lai hai vec tor

x = (x1,x2, …..,xn) và y = (y1,y2,…..yn) với điểm chọn tại k, ta được

x' = (x1,x2, …..,xk',…..xn) ; và y' = (y1,y2,…..yk', …yn)

với xk' = a.xk +(1-a).yk và yk' = a.yk + (1-a).xk với a [0,1] là một số cho trước

hoặc được chọn ngẫu nhiên.

 Lai số học toàn cục

Lai hai vector x = (x1,x2, …..,xn) và y = (y1,y2,…..yn)

sử dụng: x' = a.x +(1-a).y và y' = a.y + (1-a).x với a [0,1] là một số cho

trước hoặc được chọn ngẫu nhiên.

Các toán tử biến dị:

- Biến dị đều:

Gen xkbiến dị thành xk' thì xk' là một số ngẫu nhiên phân bố đều trên miền xác

định chấp nhận được [ak, bk] của nó.

- Biến dị không đều:

Gen xkbiến dị thành xk' thì xk' thì xk' = xk+(t,xk) với (t,xk) là một số ngẫu

nhiên phân bố không đều trên đoạn [ak-xk, bk - xk]

2.2.1.5. Ứng dụng của GA trong các thuật toán phân cụm

Trong các thuật toán phân cụm dữ liệu, GAs thường đươc sử dụng để tìm đặc trưng

của các cụm theo chiến lược Heuictic với mục đích tăng nhanh độ hội tụ của thuật toán

Sử dụng phương pháp biểu diễn gen bằng số thực với một nhiễm sắc thể là một

dãy các chữ số đặc trưng của một tâm cụm.

Thuật toán áp dụng cho họ các thuật toán phân cụm phân hoạch được áp dụng như

Bước 1: Khởi tạo một quần thể ban đầu là một tập nhiễm sắc thể tương ứng với k

đặc trưng của cụm ban đầu.

Bước 2: Lặp

Bước 3: Phân các đối tượng dữ liệu vào k cụm tương ứng theo thuật toán

Bước 4: Thay vì tính lại tâm cụm, ta sử dụng các toán tử trong GA để tìm các đặc

trưng mới cho các cụm.

C1: Sử dụng toán tử lai để tạo ra các cụm đặc trưng mới từ k cum đặc trưng ban đầu, bằng việc chọn lọc các cặp nhiễm sắc thể để lai bằng bánh xe sổ số. Chọn ngẫu nhiên m cặp gen trong nhiễm sắc thể để tiến hành lai tạo, kết quả tạo ra hai nhiễm sắc thể con mới

C2: Sử dụng toán tử đột biến để đột biến một số các gen được chọn ngẫu nhiên trong nhiễm sắc thể đặc trưng cho một tâm cụm đang xét. Việc giả sử một gen an được đột biến sẽ tạo ra một giá trị tương ứng là an' bằng cách chọn một giá trị ngẫu nhiên trong tập các khả năng lựa chọn của an được xác định bởi dữ liệu của bài toán.

Kết quả phép đột biến cũng tạo ra một nhiễm sắc thể mới. Sau khi tìm được các thế hệ mới của k cụm, ta sử dụng một hàm đánh giá để quyết định chọn ra k đại diện mới trong bước phân hoạch tiếp theo.

Bước5: Quá trình sẽ kết thúc khi thỏa mãn điều kiện dừng

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

Các phương pháp nêu trên đã kết hợp chặt chẽ giữa bộ giải pháp PO với khái niệm

Pareto thống trị [6]. Trong Pareto thống trị các tiêu chí lựa chọn giữa current-pt và new-pt

đã được xây dựng dựa trên sự khác biệt của các giải pháp mà nó thống trị [7], [8]. Thuật

toán AMOSA được đề xuất kết hợp một khái niệm mới về số lượng của các phương pháp

thống trị để lựa chọn hay loại bỏ một phương pháp mới, ở đây các phương pháp PO được

lưu trữ trong một kho lưu trữ. Các khái niệm về lưu trữ hoặc một tập hợp các giải pháp

PO cũng được sử dụng trước đây để lưu trữ các giải pháp không bị thống trị. Tuy nhiên

điều cải tiến ở thuật toán AMOSA so với các thuật toán khác là để chấp nhận một giải

pháp mới AMOSA dựa vào một xác suất hay độ tin cậy của phương pháp hiện tại và các

giải pháp trong kho lưu trữ và việc phân cụm xuất hiện như một sự lựa chọn tự nhiên nếu

số lượng trong kho lưu trữ vượt quá một giới hạn nào đó, việc làm này làm giảm sự mất

mát của việc phân cụm.

AMOSA sử dụng một mảng lưu trữ, nơi sẽ lưu trữ các giải pháp không bị thống trị. Kích thước của mảng lưu trữ này không bị ràng buộc để làm giảm sự mất mát của việc phân tập. Trong cách tiếp cận bài toán, chúng ta đã giữ kích thước của mảng lưu trữ bằng một kích thước có giới hạn mà vẫn đảm bảo các giải pháp Pareto thực hiện được.

Như đã nêu trên, AMOSA dựa trên nguyên tắc của SA [9]. Ở nhiệt độ T, một trạng

thái mới s được lựa chọn với xác suất:

Trong đó: q là trạng thái hiện tại và E(q,T) và E(s,T) là giá trị năng lượng tương ứng với q và s, phương trình này tự động đảm bảo rằng giá trị xác suất nằm trong khoảng từ 0 đến 1.

Hai giới hạn được đề xuất:

- Giới hạn cứng (hard limit) ký hiệu là HL - Giới hạn mềm (soft limit) ký hiệu là SL

Trong quá trình xử lý, các giải pháp không bị thống trị sẽ được lưu trữ trong mảng lưu trữ và chúng được tạo ra cho đến khi kích thước của mảng lưu trữ tăng lên giới hạn mềm SL. Nếu sau đó không có giải pháp không bị thống trị nào được tạo ra nữa thì kích thước của mảng lưu trữ sẽ được giảm dần về giới hạn HL thông qua quá trình phân cụm (chú ý: SL > HL).

Các thông số

Và như vậy ta có được các tham số cần thiết lập mức ưu tiên trong thuật toán như

- HL: Kích thước tối đa của mảng lưu trữ, kích thước này được đặt bằng số

lượng tối đa các giải pháp không bị thống trị do người sử dụng đưa vào.

- SL: Kích thước tối đa mà mảng lưu trữ được làm đầy trước quá trình phân

cụm.

- Tmax: Độ đo tối đa (khởi tạo). - Tmin: Độ đo tối thiểu (kết thúc). - iter: Số lượng các vòng lặp với mỗi độ đo. - α: Tỉ lệ làm nguội trong SA

2.2.2.1. Khởi tạo kho lưu trữ

Thuật toán bắt đầu bằng việc khởi tạo một số lượng các giải pháp, số này là γ * SL (với γ > 1). Mỗi giải pháp này sẽ được tinh lọc bằng việc sử dụng một kỹ thuật leo đồi đơn giản. Việc chấp nhận một giải pháp mới chỉ khi nó thống trị một giải pháp trước đó. Việc này lặp đi lặp lại dựa vào số lượng các vòng lặp. Sau đó các giải pháp không bị thống trị sẽ được chứa trong mảng lưu trữ và đạt tới kích thước HL. Trong trường hợp số các giải pháp lưu trữ vượt quá kích thước HL, thì việc phân cụm sẽ được áp dụng tiếp để giảm kích thước của mảng lưu trữ về HL. Và như vậy thì mảng lưu trữ sẽ chứa tối đa là HL giải pháp.

2.2.2.2. Phân cụm các điểm dữ liệu

Việc phân cụm các giải pháp trong mảng lưu trữ để đảm bảo sự phân tập của các giải pháp không bị thống trị. Trên thực tế, kích thước của mảng lưu trữ được phép tăng tới SL (>HL), sau khi các giải pháp được phân cụm thành các nhóm giải pháp nằm trong các cụm HL.

Việc cho phép kích thước mảng lưu trữ đạt tới SL không những làm giảm những việc thực hiện phân cụm mà còn cho phép trải rộng các cụm hơn và phân tập tốt hơn. Sau khi đạt được các cụm HL, các thành phần trong mỗi cụm sẽ có kích thước trung bình tới các thành phần khác đạt giá trị nhỏ nhất.

Đối với việc phân cụm, các thuật toán phân cụm dữ liệu đơn mục tiêu được áp dụng [9]. Ở đây khoảng cách giữa hai cụm tương ứng với với chiều dài ngắn nhất giữa chúng. Ngoại trừ việc ở đây sử dụng phương pháp tính bình quân khoảng cách ngắn nhất giữa các thành viên trong một cụm. Sau đó, HL cụm được chọn là các thành viên có khoảng cách trung bình ngắn nhất trong mỗi nhóm là các thành viên đại diện của các cụm được lưu trong mảng lưu trữ.

2.2.2.3. Độ thống trị

40 Như đã đề cập AMOSA sử dụng khái niệm về số lượng của sự thống trị trong tính toán xác suất của một giải pháp mới. Với hai giải pháp a và b số lượng thống trị được định nghĩa là:

Trong đó: M: Số các mục tiêu.

Ri: Mục tiêu thứ i.

Trong những tình huống, các giải pháp trong kho lưu trữ, giải pháp mới và giải pháp

được sử dụng trong AMOSA trong khi

hiện tại được sử dụng để tính toán nó. tính xác suất chấp nhận của một phương pháp mới.

Hình 2.3. Số lượng của sự thống trị của hai giải pháp A và B là diện tích của hình chữ nhật được tô đậm.

2.2.2.4. Tiến trình chính của AMOSA

Một trong những điểm được gọi là current-pt được lựa chọn ngẫu nhiên từ mảng lưu trữ và được coi là phương án khởi tạo tại độ đo Temp=Tmax, current-pt được nhiễu loạn để tạo ra một phương án new-pt. Trạng thái thống trị của new-pt được kiểm tra với độ tin cậy so với curent-pt và các giải pháp thuộc mảng lưu trữ (Archive).

Dựa trên trạng thái thống trị giữa current-pt và new-pt ta thấy có ba trường hợp khác

nhau xảy ra, chúng được liệt kê dưới đây:

Trƣờng hợp 1: Current-pt thống trị new-pt và k điểm (k>0) thuộc mảng

Archive.

Hình 2.4. Trường hợp khác nhau khi new-pt bị thống trị bởi curent-pt. a) new-pt

không bị thống trị bởi các giải pháp trong kho Archive ngoại trừ curent-pt. b) Một số giải pháp trong kho Archive thống trị new-pt.

Trường hợp này được hiện thị trong hình 2.4 khi k=0 và k>=1. trong trường hợp này

new-pt được chọn là current-pt với xác suất:

Với

) là giá trị trung bình của độ thống trị giữa new-pt bởi (k+1) điểm (current-pt và k điểm thuộc kho

cũng tăng lên và các điểm thống trị sẽ dần

Archive). Do đó khi k tăng lên thì dần cách xa new-pt hơn và góp phần vào giá trị của nó.

Trƣờng hợp 2: Current-pt và new-pt không thống trị lẫn nhau.

Dựa vào trạng thái thống trị của new-pt và các thành phần thuộc kho Archive có 3

tình huống có thể xảy ra:

- Tình huống 1: new-pt đƣợc thống trị bởi k điểm thuộc Archive. (k>=1)

(hình 2.5a).

Hình 2.5a. new-pt được thống trị bởi k điểm thuộc Archive

New-pt được chọn là current-pt với xác suất:

Với . Ở đây current-pt có thể hoặc

không nằm trên đường lưu trữ.

- Tình huống 2: new-pt không thống trị những điểm khác thuộc Archive.

(hình 2.5b)

Hình 2.5b. new-pt không thống trị những điểm khác thuộc Archive

Trường hợp này new-pt nằm trên cùng một đường Archive. Vì vậy new-pt được chọn là current-pt và được đưa vào Archive. Nếu Archive đầy thì nó được phân cụm để giảm kích thước xuống còn HL.

- Tình huống 3: new-pt thống trị k điểm thuộc Archive. (k>=1) (hình

2.5c)

Hình 2.5c. new-pt thống trị k điểm thuộc Archive

Trong trường hợp này new-pt được chọn làm current-pt và được đưa vào mảng Archive khi đó mọi điểm k bị thống trị sẽ bị loại bỏ khỏi Archive. Ở đây current-pt cũng có thể hoặc không nằm trên đường lưu trữ.

Trƣờng hợp 3: new-pt thống trị current-pt

Trường hợp này cũng dựa trên trạng thái thống trị của new-pt và các thành phần

thuộc mảng Archive. Và có 3 tình huống có thể xảy ra:

- Tình huống 1: new-pt thống trị current-pt nhƣng k điểm thuộc Archive

lại thống trị new-pt. (hình 2.6a)

Hình 2.6a. new-pt thống trị current-pt nhưng k điểm thuộc Archive lại thống trị

new-pt

Trường hợp này chỉ có thể xảy ra khi current-pt không thuộc Archive. Sự khác biệt

nhỏ nhất của lượng thống trị giữa new-pt và k điểm thuộc Archive là . Điểm

44 thuộc Archive tương ứng với sự khác biệt nhỏ nhất được chọn là current-pt với xác suất

là: . Mặt khác new-pt được chọn là current-pt.

- Tình huống 2:new-pt không thống trị những điểm thuộc Archive nhƣng

lại thống trị current-pt nếu nó thuộc Archive. (hình 2.6b)

Hình 2.6b. new-pt không thống trị những điểm thuộc Archive nhưng lại thống trị

current-pt nếu nó thuộc Archive.

Do vậy new-pt được chấp nhận như current-pt có thể được xem xét như là một giải pháp không bị thống trị mà phải được lưu trữ trong Archive. Do đó new-pt được thêm vào Archive. Nếu current-pt thuộc Archive suy ra nó sẽ bị loại bỏ. Mặt khác, nếu số lượng điểm thuộc Archive trở nên lớn hơn giá trị SL thì việc phân cụm sẽ được thực hiện để làm giảm kích thước của nó xuống còn HL. Ở đây current-pt có thể hoặc không nằm trên đường lưu trữ.

- Tình huống 3: new-pt thống trị k điểm thuộc Archive. (hình 2.6c)

Hình 2.6c. new-pt thống trị k điểm thuộc Archive.

45 Do vậy new-pt được chọn là current-pt và được đưa vào Archive, trong khi mọi điểm thống trị của Archive bị loại bỏ. Ở đây, current-pt có thể hoặc không nằm trên đường lưu trữ.

Thuật toán được biểu diễn như sau:

Đặt Tmax, Tmin, HL, SL, iter, α,temp=Tmax

Khởi tạo mảng lưu trữ Archive

Current-pt= random(Archive) /* chọn ngẫu nhiên 1 giải pháp trong mảng lưu trữ*/

While (temp>Tmin)

For (i=0;i

New-pt=perturb(current-pt)

/*Kiểm tra trạng thái thống trị của current-pt và new-pt*/

If (current-pt thống trị new-pt) /*Trường hợp 1*/

/*với k = tổng ∆domtrungbình =

số các điểm trong Archive mà thống trị new-pt, k ≥ 0*/

prob =

Đặt new-pt = current-pt với xác suất = prob

if(current-pt và new-pt cùng thống trị lẫn nhau) /* trường hợp 2 */

/*Kiểm tra trạng thái thống trị của new-pt và các điểm trong mảng lưu trữ

Archive*/

if(new-pt bị thống trị bởi k (k ≥1) điểm trong Archive) /* trường hợp 2a */

prob =

∆domtrungbình =

Đặt new-pt = current-pt với xác suất = prob

if(new-pt là đang không thống trị mọi điểm trong Archive) /* trường hợp 2b*/

Đặt new-pt = current-pt và đưa new-pt vào trong Archive

Nếu kích thước Archive-size > SL

Phân cụm Archive tới giới hạn HL cụm

if(new-pt thống trị k (k≥1) điểm trong Archive) /* trường hợp 2c */

Đặt new-pt = current-pt và đưa nó vào trong Archive

Loại bỏ tất cả k điểm bị thống trị ra khỏi mảng Archive

if(new-pt thống trị current-pt) /* trường hợp 3 *

Kiểm tra trạng thái thống trị của new-pt và các điểm trong mảng Archive

if(new-pt bị thống trị bởi k (k≥1) điểm trong Archive) /* trường hợp 3a */

∆dommin = tối thiểu của các sự khác biệt của các vùng thống trị giữa new-pt và k

điểm

prob =

Đặt điểm tương ứng trong Archive với = current-pt với xác suất = prob

else đặt new-pt = current-pt

if(new-pt là không thống trị với các điểm trong Archive /* trường hợp 3b */

đặt new-pt = current-pt và đưa nó vào trong Archive

if current-pt nằm trong Archive Loại bỏ nó ra khỏi Archive

else if kích thước Archive-size > SL

Phân cụm Archive tới giới hạn HL cụm

if (new-pt thống trị k điểm khác trong Archive) /* trường hợp 3c */

đặt new-pt = current-pt và đưa nó vào trong mảng Archive

Loại bỏ tất cả k điểm bị thống trị ra khỏi mảng Archive

End for

temp = α * temp

End while

if kích thước Archive-size > SL

Phân cụm Archive tới giới hạn HL cụm

Quá trình trên được lặp đi lặp lại iter lần với mỗi độ đo Temp. Độ đo Temp sẽ giảm một lượng là <1 cho đến khi đạt độ đo nhỏ sau mỗi lần với hệ số nhất Tmin. Sau đó quá trình sẽ dừng lại và mảng Archive sẽ chứa các giải pháp cuối cùng không bị thống trị.

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

Kỹ thuật phân cụm đa mục tiêu được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm [3.4.3]: Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14]. Chỉ số Sym - chỉ số dựa trên khoảng cách đối xứng [15, 11]. Hai chỉ số này được tối ưu hóa đồng thời để xác định chính xác số phân cụm trong bộ dữ liệu. Do vậy, kỹ thuật này có thể phát hiện được số cụm thích hợp và phân vùng phù hợp từ các bộ dữ liệu.

3.1. Giới thiệu

Phân cụm là tác vụ để tìm ra phân vùng tự nhiên trong bộ dữ liệu với những đơn vị dữ liệu trong cùng một cụm thì có nhiều điểm tương đồng hơn các đơn vị dữ liệu trong các nhóm khác. Ở đây, để xác định “độ chính xác” của các giải pháp phân cụm thuật toán ứng dụng các kỹ thuật tối ưu hóa mục tiêu [12]. Thay vì tối ưu hóa đơn mục tiêu thuật toán này tiến hành tối ưu hóa đồng thời nhiều mục tiêu (chỉ số phân cụm) và cho kết quả tốt hơn. Trong thuật toán này, phân vùng tự động một bộ dữ liệu được gọi là tối ưu hóa đa mục tiêu (MOO) [13]. Tối ưu hóa đơn mục tiêu tạo ra một giải pháp tốt nhất nhưng trong tối ưu hóa đa mục tiêu tạo ra một bộ giải pháp gồm các giải pháp tối ưu, không có giải pháp nào trong số các giải pháp đó được đánh giá hơn, hay trội hơn các giải pháp khác.

Để phân cụm từ bộ dữ liệu đầu tiên phải đánh giá được mức độ giống và khác nhau giữa các dữ liệu. Sau đó, mức độ đánh giá này sẽ được dùng để phân các dữ liệu này đến các cụm dữ liệu khác nhau. Nhìn chung nhiều phân cụm có tính chất đối xứng trục hoặc điểm dựa vào quan sát này khoảng cách dựa vào đối xứng điểm dps [16] được sử dụng để giảm bớt sự phức tạp trong việc tính toán khoảng cách.

Để xác định số lượng cụm từ bộ dữ liệu rất quan trọng. Việc tối ưu hóa các hàm giá trị sẽ tương đương với việc tìm được các giải pháp tốt nhất nên giải thuật di truyền (GA) dựa trên các thuật toán phân cụm ngẫu nhiên được sử dụng để tối ưu hóa các hàm giá trị để xác định số lượng các phân cụm đồng thời phân vùng từ bộ dữ liệu [chương 2]. Trong giải thuật di truyền, việc phân các dữ liệu đến các cụm khác nhau được thực hiện dựa theo khoảng cách Euclidean của thuật toán K-Mean do cách tiếp cận này chỉ tìm thấy siêu chỉ đồ cầu nhỏ, các phân cụm lồi và kích cỡ bằng nhau. Nếu các cụm có hình dạng khác nhau trong một bộ dữ liệu thì phương pháp này không thể tìm ra các phân cụm của nó. Kỹ thuật phân cụm di truyền dựa trên khoảng cách đối xứng điểm được đề xuất trong [11] thuật toán VGAPS để xác định số lượng phân cụm và phân vùng thích hợp từ các bộ dữ liệu có phân cụm đối xứng điểm nhưng nó tối ưu hóa đánh giá giá trị phân cụm đơn, nhưng chỉ số đối xứng lại hiếm khi áp dụng cho bộ dữ liệu khác nhau có tính chất khác

nhau. Do đó, việc tối ưu hóa đồng thời đánh giá các giá trị là rất quan trọng nó có thể thu được các đặc điểm dữ liệu khác nhau. Kỹ thuật tối ưu hóa đa mục tiêu được đề xuất dựa trên thuật toán mô phỏng luyện kim (SA) – Kỹ thuật AMOSA [17] (được trình bày ở mục [3.2] và chương 2) được sử dụng để xác định trung tâm phân cụm chính xác và phân vùng tương ứng từ bộ dữ liệu.

Kỹ thuật phân cụm đa mục tiêu, VAMOSA, được đề xuất sử dụng mã hóa dựa vào trung tâm cụm. Kỹ thuật được đề xuất sử dụng thuật toán mô phỏng luyện kim (SA) dựa trên cơ sở phương pháp tối ưu đa mục tiêu như một chiến lược tối ưu hóa cơ bản. Hai chỉ số đánh giá phân cụm được tối ưu hóa đồng thời, Chỉ số XB - chỉ số dựa trên khoảng cách Euclidean [14] và chỉ số đối xứng Sym - dựa vào khoảng cách đối xứng điểm [15, 11]. Các chỉ số đánh giá phân cụm khác cũng có thể được thay thế cho hai chỉ số này.

3.2. Thuật toán tối ƣu đa mục tiêu dựa vào SA: AMOSA

Như đã trình bày ở chương II, giải thuật AMOSA kết hợp các khái niệm của kho lưu trữ, nơi mà các giải pháp không bị ảnh hưởng nhiều được lưu trữ. Kho lưu trữ được giới hạn bởi hai kích cỡ giới hạn là: giới hạn cứng kí hiệu là HL và giới hạn mềm kí hiệu là SL. Giải thuật này bắt đầu khởi tạo một một số lượng các giải pháp, số này là γ * SL (với γ > 1). Các hàm mục tiêu được tính toán, mỗi lời giải được cập nhật lại bằng cách sử dụng thuật toán leo đồi và sự thống trị của các giải pháp. Sau đó, các lời giải không bị ảnh hưởng nhiều sẽ được lưu trong kho lưu trữ cho đến khi khối lượng của kho tăng lên giới hạn SL. Trong trường hợp số các giải pháp lưu trữ vượt quá kích thước HL, thì việc phân cụm sẽ được áp dụng tiếp để giảm kích thước của mảng lưu trữ về HL. Và như vậy thì mảng lưu trữ sẽ chứa tối đa là HL giải pháp.

3.3. Khoảng cách đối xứng

Một định nghĩa mới về khoảng cách là khoảng cách đối xứng điểm ) , kết

theo tâm

hợp với điểm [16] cũng chỉ ra đây. Khoảng cách đối xứng điểm được triển khai trong Tham khảo [16]. Trong nghiên cứu có thể giải quyết các hạn chế của khoảng cách Euclidean trước đối được tính như sau. Lấy một điểm là

xứng điểm của theo tâm là , ky hiện là . Với Knear điểm lân cận khoảng

cách đối xứng điểm được tính theo công thức:

Trong đó: là khoảng cách Euclidean giữa điểm và , và là độ

đối xứng của theo . Khái niệm khoảng cách đối xứng điểm được thể hiện trong hình

3.1. Trong hình này trình bày một điểm cụ thể. Tâm được ký hiệu là . Do đó, đối

xứng điểm của theo là .

Hình 3.1. Ví dụ về khoảng cách đối xứng điểm

Hai điểm gần nhất của

có khoảng cách Euclidean tương ứng là d1 , được tính như sau: và Ví dụ: và d2. Do đó, khoảng cách đối xứng điểm giữa

. Trong đó, là khoảng cách Euclidean giữa điểm và

tâm .

Chú ý: Knear trong Công thức (2) không được chọn bằng 1, vì nếu

có trong bảng giá trị thì , và do đó không ảnh hưởng đến khoảng cách Euclindean. Nói theo cách khác, các giá trị lớn của knear có thể không phù hợp do có thể ước tính thấp khoảng đối xứng của một điểm theo một tâm điểm nhóm cụ thể. Ở đây, knear được chọn bằng 2. Cần chú ý là giá trị phù hợp của knear phụ thuộc nhiều vào việc phân phối các tập dữ liệu. Giá trị cố định knear có thể cũng có hạn chế. Ví dụ, với một nhóm lớn (với quá nhiều điểm) hai điểm lân cận có thể không đủ vì có thể có một vài điểm lân cận có khoảng cách gần bằng không. Nói cách khác, nhóm điểm với quá nhiều điểm dễ phân tán hơn, và khoảng cách của hai điểm lân cận có thể quá lớn. Do đó, việc lựa chọn knear phù hợp rất quan trọng cần được xem xét. Và đây cũng là một hạn chế của đề tài, trong tương lai đề tài sẽ có hướng khắc phục việc tính giá trị phù hợp cho Knear.

3.4. Phƣơng pháp đề xuất để phân cụm đa mục tiêu

Một thuật toán phân cụm đa mục tiêu mới là VAMOSA được đề xuất dựa trên phương pháp tối ưu đa mục tiêu – AMOSA như một chiến lược tối ưu hóa. Các bước cơ bản trong VAMOSA được nối sau các bước cơ bản trong AMOSA được trình bày trong hình 3.2, quy trình phân nhóm từ tập dữ liệu dựa trên khoảng cách đối xứng điểm được mô tả trong hình 3.3.

3.4.1. Trình bày chuỗi và khởi tạo kho lƣu trữ

51 Kỹ thuật AMOSA phát triển một tập tâm nhóm thể hiện sự phân chia các dữ liệu. Trong một chuỗi cụ thể ghi mã các tâm nhóm k trong không gian d chiều do đó chiều dài l của chúng được tính thành d*K. Ví dụ, trong không gian bốn chiều, chuỗi (2.3 1.4 7.6 12.9 2.1 3.4 0.01 12.2 0.06 2.3 6.7 15.3 3.2 11.72 9.5 3.4) ghi mã mốn tâm nhóm ( 2.3 1.4 7.6 12.9) , (2.1, 3.4, 0.01, 12.2), (0.06, 6.7, 15.3) và (3.2, 11.72, 9.5, 3.4). Mỗi tâm được của các coi là không thể phân chia. Mỗi chuỗi trong lưu trữ khởi tạo ghi mã tâm Ki nhóm, ví dụ Ki (rand () mod (Kmax - 1)+2. Ở đây, rand () là một chức năng chuyển thành số nguyên và Kmax là ước tính tạm thời của một số nhóm bên trên. Số nhóm sẽ dao động từ hai đến Kmax. Các tâm Ki ghi mã trong một chuỗi thường là các điểm chọn ngẫu nhiên từ tập dữ liệu.

Begin

Bƣớc 1: T = Tmax; Tmax = độ đo cực đại.

Bƣớc 2: Khởi tạo kho lưu trữ.

Bƣớc 3: Current_sol= giải pháp chọn ngẫu nhiên từ kho lưu trữ.

While T < Tmin ; Tmin=giá trị độ đo cực tiểu

Bƣớc 4: For i=1 to iter

Call clustering_PS() procedure for current_sol

/* tiến hành phân cụm cho giải pháp current_sol */

Compute objective function for current_sol

/* tính các hàm mục tiêu cho current_sol */

New_sol = mutate(current_sol)

Call clustering_PS() procedure for new_sol

Compute objective function for new_sol

Use the steps of AMOSA to decide who will be the next current_sol.

Whether to include new_sol in the archive.

/* sử dụng giải thuật AMOSA để quyết định xem chấp nhận giải

pháp mới hay giải pháp cũ.

T = α x T; α cooling rate.

End for.

End while.

Bƣớc 5: Select the best solution from the archive.

/* Chọn giải pháp trong kho lưu trữ*/

Bƣớc 6: Output best solution and stop.

End.

Hình 3.2. Các bước chính của thuật toán VAMOSA

3.4.2. Phân cụm các điểm dữ liệu

Cho một bộ dữ liệu gồm n điểm dữ liệu và số nhóm k cho trước, phân bố các j, J =1,2, …n, được phân bố tới một nhóm nhất định

điểm tới k nhóm khác nhau. Mỗi điểm theo cách sau:

Tìm tâm nhóm gần nhất với j theo ý nghĩa đối xứng. Nghĩa là chúng tôi tìm ra tâm

nhóm k có khoảng cách đối xứng ngắn nhất tới j:

) k= Argmini=1…K.dps( j,

Trong đó: biểu diễn tâm của nhóm thứ i và dps( j,

đối xứng điểm [16] giữa điểm cụ thể j với tâm nhóm ) là khoảng cách dựa trên )/ nếu tỷ số tương ứng dps( j,

) nhỏ hơn thông số đã quy định trước ɵ, chúng tôi gán điểm j tới nhóm thứ k de( j,

). Nhưng nếu ) là khoảng cách Ơ-clit giữa giữa điểm j và tâm nhóm (de( j,

))> ɵ, thì việc phân bố dựa trên tiêu chí khoảng cách Euclidean nhỏ (dps( j, )/ de( j,

j tới nhất như thường dùng trong [18] hoặc thuật toán công cụ K, tức là gán gán điểm ). Nguyên nhân thực hiện việc phân bố này nhóm thứ k tại đó k = Argmini=1…Kde( j, như sau: trong các giai đoạn trung gian của thusật toán, khi các tâm chưa khai triển đúng, giá trị dps cực tiểu cho mỗi điểm được mong đợi là khá lớn, vì điểm đó có thể không đối xứng với tâm nào cả. Trong các trường hợp đó, khoảng cách Euclidean để phân bố nhóm phù hợp hơn.

Sau khi việc phân bố điểm dữ liệu hoàn thành, các tâm nhóm được cập nhập lại

theo tư tưởng của thuật toán K-Mean.

Procedure: Clustering_PS()

+ Assignment of data point:

1. Let a particular string encode total K number of clusters. For all data point

/* là khoảng cách Euclidean giữa điểm và tâm nhóm

Gán giá trị điểm vào nhóm thứ */

3. Otherwise, the data point is assigned to the cluster where

+ Updation of centres: Compute the new centroids of the K clusters as follows:

/* Cập nhập lại tâm nhóm.*/

Hình 3.3. Các bước chính của quá trình phân điểm dữ liệu đến k nhóm dữ liệu dựa

vào khoảng cách đối xứng điểm

3.4.3. Tính toán các hàm mục tiêu phù hợp

Trong thuật toán này, hai hàm mục tiêu được tối ưu hóa đồng thời là chỉ số Xie- Beni (XB) [14] dựa vào khoảng cách Euclidean và chỉ số Sym dựa trên khoảng đối xứng điểm [11,15]. Chú ý, cũng có thể sử dụng nhiều chỉ số phù hợp khác. Hai chỉ số này được tối ưu hóa đồng thời bằng phương pháp tối ưu cụm AMOSA.

Chỉ số XB là một chỉ số dựa trên khoảng cách Euclidean. Nó là một tỷ lệ của độ nén nhóm giữa các nhóm (sử dụng khoảng cách Ơ-clít) theo sự phân tách giữa các cặp nhóm. Do đó, nó có thể phát hiện tốt các nhóm có hình dạng siêu cầu. Ở đây, sự phân nhóm được đo bằng cách sử dụng khoảng cách nhỏ nhất giữa hai trung tâm nhóm. Nhưng trong chỉ số Sym, sự tách nhóm được đo bằng cách sử dụng khoảng cách lớn nhất giữa tâm hai nhóm. Do đó hai chỉ số này kiểm tra các đặc điểm khác nhau của các nhóm. Hơn nữa, chỉ số XB là chỉ số hiệu lực nhóm rất thông dụng và nổi tiếng dựa trên khoảng cách Ơ-clit. Do đó, ở đây chúng ta đã tối ưu hóa cả chỉ số XB và chỉ số Sym đồng thời sử dụng MOO là AMOSA.

Để tính tóan các phương pháp này, ban đầu các trung tâm được mã hóa trong dãy được trích ra. Cho số K trung tâm nhóm được mã hóa trong một dãy riêng. Diễn tả chúng là

+ Chỉ số XB: được xác định là hàm của tỷ lệ giữa tổng biến thể σ với sự phân tách

tối thiểu sep của các nhóm.

{

Trong đó: σ và sep được viết là: σ(Z,X)= và sep(Z)= min }

trong đó là định chuẩn Ơ-Clít và de

và tâm nhóm là khoảng cách Ơ-clit giữa điểm thứ k và , ni diễn tả số điểm dữ liệu xuất hiện trong nhóm thứ i. Z

nhóm thứ i và X là bộ các tâm nhóm và bộ dữ liệu. chỉ số XB sau đó được viết như sau:

XB= =

Chú ‎ý: Khi sự phân chia chắc chắn và tốt thì tổng độ lệch σ sẽ có giá trị thấp trong khi đó sự phân tách cực tiểu (sep) giữa mỗi cặp trung tâm sẽ có giá trị cao. Do đó, mục tiêu là tối thiểu chỉ số XB để đạt được sự phân nhóm tốt.

Chỉ số XB => Min

+ Chỉ số Sym: xác định dựa trên khoảng cách đối xứng điểm [11,15]. Nó được xác

định như sau:

Sym (K) = ( )

Trong đó: K là tổng số nhóm cho trước. Ở đây = trong đó = và DK=

. DK là khoảng cách Ơ-clit lớn nhất giữa các trung tâm cặp nhóm.

là khoảng cách dối xứng điểm [3] giữa điểm thứ j và nhóm thứ i. Ở đây, các lân

cận k gần nhất của = 2 x sẽ chỉ được tìm kiếm giữa các các điểm trong nhóm i,

, điểm phản chiếu của đối với và nên thuộc về

tức là các lân cận k gần nhất của nhóm thứ i.

Chú ‎ý: Mục tiêu là tối đa hóa chỉ số Sym để đạt được số nhóm thực và đạt được sự phân nhóm tốt. Sym là tập hợp 3 yếu tố là 1/K, 1/ và DK. Yếu tố thứ nhất tăng khi K giảm để giảm giá trị của K. Yếu tố thứ hai nằm trong tổng thể khoảng cách đối xứng nhóm. Đối với nhóm có cấu trúc đối xứng tốt, giá trị Ei là nhỏ hơn. Điều này chỉ ra rằng sự hình thành thêm nhiều nhóm, đối xứng về hình dạng được khích lệ. Cuối cùng yếu tố thứ ba Dk đo sự phân tách cực đại của các cặp nhóm, tăng với giá trị của K. Khi ba yếu tố này bổ sung về bản chất, chúng được kỳ vọng là sẽ hoàn thiện và cân bằng với nhau để quyết định sự phân chia chính xác.

Chỉ số Sym => Max

Vậy cần tối ưu hóa đồng thời hai hàm mục tiêu dựa trên phương pháp tối ưu nhóm AMOSA:

55 Chỉ số XB => Min

Chỉ số Sym => Max

3.4.4. Một số phƣơng pháp nhiễu các phƣơng án

Khác với thuật toán K-mean, ở đây thuật toán VAMOSA không cần xác định số k cụm cho trước, nó khởi tạo một số k bất kỳ sau mỗi lần thực hiện thủ tục phân cụm PS() thì ta có thể thay đổi tập tâm cụm theo 1 trong 3 phương án sau:

(1) Mỗi trung tâm cụm mã hóa trong mỗi chuỗi được thay thế bằng một tọa độ gần

tâm.

(2) Một trung tâm cụm bất kỳ được bỏ bớt.

(3) Tổng số cụm được mã hóa trong chuỗi tăng lên 1. Một điểm được chọn bất kỳ của

bộ dữ liệu sẽ được mã hóa như trung tâm cụm mới.

3.4.5. Điều kiện dừng cùa thuật toán

Các bước của AMOSA dựa trên các bước của kỹ thuật phân cụm VAMOSA theo sau các bước của giải thuật SA. Dựa vào giải thuật SA, trong AMOSA độ đo ban đầu được đặt ngang bằng với Tmax, giá trị độ đo cực đại. Các bước của AMOSA được thực hiện iter lần đối với mỗi độ đo. Sau khi thực hiện xong iter lần độ đo giảm xuống α lần với T = α x T ( <1 ) cho đến khi đạt độ đo nhỏ nhất Tmin. Sau đó quá trình sẽ dừng lại.

3.4.6. Lựa chọn giải pháp

Các thuật toán tối ưu cụm sản sinh ra số lượng lớn các giải pháp không bị trội [13] ở trên biên Pareto tối ưu. Mỗi giải pháp cung cấp một cách đặt các dữ liệu cụm. Tất cả các giải pháp đều được đánh giá như nhau. Nhưng thi thoảng người sử dụng có thể chỉ muốn sử dụng một giải pháp đơn. Do đó giải pháp nửa giám sát được áp dụng để chọn lựa ra giải pháp phù hợp cho từng trường hợp cụ thể.

CHƢƠNG IV. KẾT QUẢ THỬ NGHIỆM

4.1. Giới thiệu

Những thí nghiệm này được thực hiện để thực nghiệm thuật toán VAMOSA và trích rút kết quả phân cụm từ mảng tối ưu thu được. Các hàm mục tiêu đánh giá chất lượng phân cụm là hai hàm đánh giá XB, SYM. Giá trị hàm mục tiêu thay đổi được xem xét khi điều chỉnh tham số cụm.

4.2. Chƣơng trình và dữ liệu thử nghiệm

4.2.1. Chƣơng trình

Chương trình cài đặt thuật toán VAMOSA phân cụm dữ liệu được viết bằng ngôn ngữ Matlab trong môi trường Matlab 2008 được chạy trên máy tính Intel core i5, 2.5 GHz, 4GB RAM.

Hình 4.1: Giao diện khi chạy chương trình

4.2.2. Dữ liệu thử nghiệm

Tiến hành thử nghiệm trên ba bộ dữ liệu, đánh giá hai chỉ số XB và SYM ở những phương án thu được trong mảng tối ưu. Hai bộ dữ liệu nhân tạo (over_3; over_4) trong đó over_3 có 250 điểm dữ liệu, mật độ khác nhau được phân cụm tối ưu là 3 cụm, over_4 có

250 điểm dữ liệu, mật độ khác nhau được phân cụm tối ưu là 3 cụm và một bộ dữ liệu thực tế (Iris) được lấy từ website: http://archive.ics.uci.edu/ml/datasets/Iris. Bộ dữ liệu thực tế (Iris): Tập hợp số liệu này gồm 150 điểm dữ liệu bốn chiều được sắp xếp thành 3 cụm. Mỗi cụm gồm 50 điểm. Tập hợp số liệu này thể hiện các loại con ngươi được đặc trưng bởi 4 giá trị đặc trưng. Có 3 loại là Setosa, Versicolor và Virginica. Hai loại (Versicolor và Virginica) có số lượng gối chồng lớn trong khi đó Setosa lại phân biệt một cách tuyến tính với hai loại trên.

4.3. Kết quả thí nghiệm

Các thông số về kỹ thuật phân cụm VAMOSA được trình bày trên như sau: Tmax=50, Tmin=0.1, α=0.8, SL=20 và HL=5. Kmax bằng trong đó n là kích thước của tập hợp số liệu. AMOSA dựa trên kỹ thuật phân cụm đa mục tiêu tự động tạo ra số lượng lớn các giải pháp không bị kiềm chế trên bề mặt tối ưu Pareto cuối cùng. Giải pháp tốt nhất được xác định bởi phương pháp nửa giám sát.

Các kết quả thu được:

Tập dữ liệu Over_3:

Hình 4.2. Mảng lưu trữ của tập dữ liệu Over_3

Trong hình 4.2 thể hiện kết quả như sau: Gồm có 5 phương án trong mảng tối ưu. Với mỗi phương án thể hiện số tâm cụm, tọa độ tâm cụm và hai chỉ số đánh giá SYM, XB cho mỗi phương án. Dựa vào phương pháp nửa giám sát có thể xác định được phương án nào tối ưu nhất tùy từng trường hợp cụ thể. Như trên thì dựa vào hai chỉ số đánh giá chúng ta có thể thấy phương án 1 là phương án tối ưu nhất. Các cụm được thể hiện như sau:

Hình 4.3. Kết quả phân cụm của phương án 1 là 3 cụm.

Hình 4.4. Kết quả phân cụm của phương án 2 là 4 cụm.

Hình 4.5. Kết quả phân cụm của phương án 3 là 5 cụm.

Hình 4.6. Kết quả phân cụm của phương án 4 là 6 cụm.

Hình 4.7. Kết quả phân cụm của phương án 5 là 7 cụm.

Tập dữ liệu Iris:

Hình 4.8. Mảng lưu trữ của tập dữ liệu Iris

Trong hình 4.8 thể hiện kết quả như sau: Gồm có 5 phương án trong mảng tối ưu. Với mỗi phương án thể hiện số tâm cụm, tọa độ tâm cụm và hai chỉ số đánh giá SYM, XB cho mỗi phương án. Như trên thì dựa vào hai chỉ số đánh giá chúng ta có thể thấy phương án 1 là phương án tối ưu nhất. Các cụm được thể hiện như sau:

Hình 4.9. Kết quả phân cụm của phương án 1 là 3 cụm.

Hình 4.10. Kết quả phân cụm của phương án 2 là 4 cụm.

Hình 4.11. Kết quả phân cụm của phương án 3 là 5 cụm.

Hình 4.12. Kết quả phân cụm của phương án 4 là 6 cụm.

Hình 4.13. Kết quả phân cụm của phương án 5 là 7 cụm.

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN

Sau thời gian nghiên cứu, được sự hướng dẫn tận tình của Thầy giáo PGS.TS.Hoàng Xuân Huấn, tôi đã trình bày luận văn “Ứng dụng kỹ thuật đa mục tiêu vào phân cụm dữ liệu”. Luận văn đã đạt được hai kết quả chính như sau:

1./ Nghiên cứu tài liệu để hệ thống lại các vấn đề sau:

- Khám phá tri thức và phân cụm dữ liệu.

- Một số phương pháp phân cụm chính.

- Nghiên cứu giải thuật tối ưu trong phân cụm dữ liệu.

- Phân cụm dữ liệu đa mục tiêu.

2./ Luận văn đã cài đặt thuật toán tối ưu đa mục tiêu VAMOSA.

Luận văn đã chạy thử nghiệm với 3 bộ dữ liệu với CSDL với nhiều thuộc tính và

nhiều bản ghi, trong đó có thử nghiệm với một bộ dữ liệu thực tế.

 Hƣớng nghiên cứu tiếp theo.

Trong thời gian tới, tôi sẽ cố gắng tìm hiểu nhiều hơn nữa về các phương pháp tối ưu cụm và phương pháp phân cụm dữ liệu, đặc biệt là phương pháp phân cụm dữ liệu đa mục tiêu và cố gắng mở rộng ứng dụng của thuật toán phân cụm đa mục tiêu vào nhiều bài toán thực tế.

Ngoài ra, việc tối ưu cụm trong phân cụm đa mục tiêu cho tập dữ liệu rất quan

trọng và nó cũng là một hướng nghiên cứu mà tôi quan tâm.

Do thời gian nghiên cứu có hạn cộng với năng lực bản thân còn hạn chế, luận văn chắc chắn sẽ không tránh khỏi một số sai sót nhất định. Tôi rất mong nhận được ý kiến đóng góp của các Thầy Cô, các bạn đồng nghiệp cùng các cá nhân quan tâm để nội dung luận văn được hoàn thành với chất lượng tốt hơn.

Cuối cùng, Em xin cảm ơn Thầy giáo PGS.TS. Hoàng Xuân Huấn đã tận tình giúp đỡ em hoàn thành nội dung nghiên cứu đề ra. Em xin cảm ơn các Thầy Cô tong Khoa Công Nghệ thông tin – Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giảng dạy cung cấp kiến thức cho em trong suốt khóa học.

TÀI LIỆU THAM KHẢO

Tiếng việt

PGS.TS Hoàng Xuân Huấn (2012), Giáo trình Nhận dạng mẫu, Trường Đại học công nghệ - Đại Học Quốc Gia Hà Nội.

Đỗ Thị Hòa (2011, Tóm tắt dữ liệu quan hệ sử dụng thuật toán di truyền nửa giám sát dựa trên kỹ thuật phân cụm, Trường Đại học công nghệ - Đại Học Quốc Gia Hà Nội, Luận văn thạc sỹ.

Tiếng anh

Anil K.Jain, Richard C.Dubes (1988), Algorithms for Clustering Data. 3.

Jiawei Han, Micheline Kamber and Anthony K. H. Tung, Spatial Clustering Methods In Data Mining: A Survey, Natural Science and Engineering Research Council of Canada.

Kuo-Lung Wu, Miin-Shen Yang, Alternative c-means clustering algorithms, Pattern Recognition 35 (2002) 2267–2278.

Sriparna Saha, Sanghamitra Bandyopadhyay, A symmetry based multiobjective clustering technique for automatic evolution of clusters, Pattern Recognition 43(3): 738-751 (2010)

in B. Suman, Study of self-stopping PDMOSA and performance measure multiobjective optimization, Computers and Chemical Engineering, vol. 29, no. 5, pp. 1131-1147, 15 April 2005.

K. Smith, R. Everson, and J. Fieldsend, Dominance measures for multi-objective simulated annealing, in Proceedings of the 2004 IEEE Congress on Evolutionary Computation (CEC'04), 2004, pp. 23-30.

Garcia Najera, Abel (2010) Multi-Objective evolutionary algorithms for vehicle routing problems. Ph.D. thesis, University of Birmingham.

10.

Jiawei Han and Micheline Kamber (2001), “Data Mining: Concepts and Techniques”, Hacours Science and Technology Company, USA.

11. S. Bandyopadhyay, S. Saha, A point symmetry based clustering technique for

66 automatic evolution of clusters, IEEE Transactions on Knowledge and Data

Engineering 20 (11) (2008) 1–17.

12. Handl, J. Knowles, An evolutionary approach to multiobjective clustering,

IEEE Transactions on Evolutionary Computation 11 (1) (2007) 56–76.

13. K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley,

England, 2001.

14. X.L. Xie, G. Beni, A validity measure for fuzzy clustering, IEEE Transactions on

Pattern Analysis and Machine Intelligence 13 (1991) 841–847.

15. S. Saha, S. Bandyopadhyay, Application of a new symmetry based cluster validity

index for satellite image segmentation, IEEE Geoscience and Remote Sensing

Letters 5 (2) (2008) 166–170.

16. S. Bandyopadhyay, S. Saha, GAPS: a clustering method using a new point

symmetry based distance measure, Pattern Recognition 40 (2007) 3430–3451.

17. S. Bandyopadhyay, S. Saha, U. Maulik, K. Deb, A simulated annealing

based multi-objective optimization algorithm: AMOSA, IEEE Transactions on

Evolutionary Computation 12 (3) (2008) 269–283.

18. S. Bandyopadhyay, U. Maulik, Genetic clustering for automatic evolution of

clusters and application to image classification, Pattern Recognition 2 (2002)

1197–1208.

Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng kỹ thuật đa mục tiêu vào phân cụm dữ liệu

Mục tiêu nghiên cứu của đề tài là phân cụm dữ liệu. 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. Thuật toán VAMOSA - Thuật toán phân cụm dựa trên tính đối xứng. Kết quả thử nghiệm.

ĐẠ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

ĐẠ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

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN

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

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

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

CHƢƠNG IV. KẾT QUẢ THỬ NGHIỆM ............................................................................... 56

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................................. 64

TÀI LIỆU THAM KHẢO ........................................................................................................... 65

DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT

Có thể bạn quan tâm

Bài giảng Phân tích và thiết kế hệ thống thông tin giáo dục

Bài giảng Công nghệ phần mềm: Bài 1 - Tổng quan về phần mềm và công nghệ phần mềm

Bài giảng Công nghệ phần mềm: Bài 2 - Đặc tả yêu cầu phần mềm

Bài giảng Công nghệ phần mềm: Bài 3 - Thiết kế phần mềm

Bài giảng Công nghệ phần mềm: Bài 4 - Đảm bảo chất lượng phần mềm

Bài giảng Công nghệ phần mềm: Bài 5 - Mô hình CMMI

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Đồ án tốt nghiệp: Xây dựng app nghe nhạc kết hợp các tiện ích AI

Áp dụng mạng Bayes xây dựng mô hình dự đoán xác suất có điều kiện phức hợp

Bài giảng Mạng định nghĩa bằng phần mềm và ảo hóa chức năng mạng (SDN và NFV)

Bài tập lớn: Tổng quan về mạng cảm biến không dây (WSN)

Bài giảng Tin học căn bản: Chương 1 - Kiến thức cơ bản về máy tính và hệ điều hành windows

Bài giảng Tin học căn bản: Chương 2 - Microsoft Word

Bài giảng Tin học căn bản: Chương 3 - Microsoft Excel

Bài giảng Tin học căn bản: Chương 4 - Microsoft PowerPoint

Bài giảng Tin học căn bản: Chương 5 - Internet và email

Đồ án chuyên ngành: Tìm hiểu hệ thống thông tin quang truyền trong không gian tự do và mô phỏng hệ thống đơn giản

Báo cáo đồ án: Quản lý nhà sách

Đồ án cơ sở: Xây dựng ứng dụng nghe sách audiobook trực tuyến

Báo cáo đồ án: Thiết kế mạng cho doanh nghiệp

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng