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

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

19
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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