Nghiên cứu một số phương pháp phân cụm mờ và ứng dụng

......................... Chƣơng 1 - TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KPDL .................. 1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu ................. 1.2. Quá trình khám phá tri thức ................................................................. 1.3. Quá trình khai phá dữ liệu .................................................................... 1.4. Các phƣơng pháp khai phá dữ liệu ....................................................... 1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL ........................................ 1.6. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL .............. 1.7. Các thách thức - khó khăn trong KPTT và KPDL................................ 1.8. Kết luận ................................................................................................ Chƣơng 2 - PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG PCDL . 2.1. Khái niệm và mục tiêu của phân cụm dữ liệu ...................................... 2.2. Các ứng dụng của phân cụm dữ liệu .................................................... 2.3. Các yêu cầu của phân cụm ................................................................... 2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu ................................. 2.4.1. Phƣơng pháp phân cụm phân hoạch .......................................... 2.4.2. Phƣơng pháp phân cụm phân cấp .............................................. 2.4.3. Phƣơng pháp phân cụm dựa trên mật độ ................................... 2.4.4. Phƣơng pháp phân cụm dựa trên lƣới ....................................... 2.4.5. Phƣơng pháp phân cụm dựa trên mô hình ................................. 2.4.6. Phƣơng pháp phân cụm có dữ liệu ràng buộc ........................... 2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu ................................ 2.5.1. Các thuật toán phân cụm phân hoạch ........................................ 2.5.2. Các thuật toán phân cụm phân cấp ............................................ 2.5.3. Các thuật toán phân cụm dựa trên mật độ ................................. 2.5.4. Các thuật toán phân cụm dựa trên lƣới ...................................... 4 5 6 6 7 8 9 10 11 12 12 13 13 15 16 18 19 19 20 21 22 22 24 24 26 29 32 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.5.5. Các thuật toán phân cụm dựa trên mô hình ............................... 2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc ......................... Chƣơng 3 - KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ ......................................... 3.1. Tổng quan về phân cụm mờ ................................................................. 3.2. Các thuật toán trong phân cụm mờ ...................................................... 3.2.1. Thuật toán FCM(Fuzzy C-means) ............................................. 3.2.1.1. Hàm mục tiêu ............................................................. 3.2.1.2. Thuật toán FCM ......................................................... 3.2.2. Thuật toán FCM(ε- Insensitive Fuzzy C-means) ..................... 3.2.2.1. Hàm mục tiêu ............................................................. 3.2.2.2. Thuật toán FCM ........................................................ 3.2.3. Thuật toán FCM Cải tiến ........................................................... 3.2.3.1. Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu làm ứng viên cho việc chọn các trung tâm của các cụm ....... 3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên ........ 3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu hàm mục tiêu .................................................................. 3.2.3.4. Thuật toán 4: Gán các trung tâm có liên kết “gần gũi” vào một cụm .................................................................. 3.2.3.5. Tổng kết thuật toán FCM-Cải tiến ............................. Chƣơng 4 - MÔ HÌNH MẠNG NƠRON ĐA KHỚP DÙNG CHO PCM ............ 4.1. Tổng quan về mạng Nơron ................................................................... 4.2. Cấu trúc mạng Nơron ........................................................................... 4.2.1. Hàm kích hoạt ........................................................................... 4.2.2. Liên kết mạng ............................................................................ 4.2.3. Bài toán huấn luyện mạng ......................................................... 4.3. Mạng HOPFIELD ................................................................................ 4.3.1. Huấn luyện mạng ....................................................................... 4.3.2. Sử dụng mạng ............................................................................. 35 36 37 37 38 39 39 42 46 46 48 49 49 51 51 52 56 58 58 61 61 61 61 62 62 63 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4.4. Mạng Nơron đa khớp dùng cho phân cụm ............................................ 4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm ........ 4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc ................. 4.5. Sự hội tụ của FBACN ........................................................................... 4.5.1. Chứng minh sự hội tụ của FBACN ............................................ 4.5.2. Sự hội tụ FBACN liên tục của Layer1 ....................................... 4.6. Giải thuật của FBACN và FBACN với việc học .................................. Chƣơng 5 - CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG ..................................... 5.1. Cài đặt thử nghiệm thuật toán FCM ...................................................... 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh ....................... KẾT LUẬN ............................................................................................................ TÀI LIỆU THAM KHẢO ...................................................................................... 63 65 68 72 72 74 75 79 79 82 86 87 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC TỪ VIẾT TẮT CNTT CSDL CEF DL FBACN FCM HMT KPDL KPTT LKM MH NDA NN PCM PCDL TLTK TT XLA Công nghệ thông tin Cơ sở dữ liệu Computational Energy Function Dữ liệu Fuzzy Bi-directional Associative Clustering Network (Mạng Nơron đa khớp phục vụ cho phân cụm mờ) Fuzzy C-Means Hàm mục tiêu Khai phá dữ liệu Khám phá tri thức Liên kết mạng Mô hình Nhận dạng ảnh Neural Network Phân cụm mờ Phân cụm dữ liệu Tài liệu tham khảo Thuật toán Xử lý ảnh 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC HÌNH MINH HOẠ Hình 1.1 Hình 1.2 Hình 2.1 Hình 2.2 Hình 2.3 Hình 2.4 Hình 2.5 Hình 2.6 Hình 2.7 Hình 2.8 Hình 2.9 Hình 3.1 Hình 3.2 Hình 3.3 Hình 3.4 Hình 4.1 Hình 4.2 Hình 4.3 Hình 4.4 Hình 4.5 Hình 5.1 Hình 5.2 Hình 5.3 Hình 5.4 Hình 5.5 Quá trình Khám phá tri thức ................................................... Quá trình Khai phá dữ liệu ...................................................... Mô tả tập dữ liệu vay nợ đƣợc phân thành 3 cụm .................1 Các chiến lƣợc phân cụm phân cấp .......................................2 Cấu trúc phân cấp ..................................................................2 Các cách mà các cụm có thể đƣa ra ....................................... Các thiết lập để xác định ranh giới các cụm ban đầu ............. Tính toán trọng tâm của các cụm mới .................................... Khái quát thuật toán CURE ................................................... Các cụm dữ liệu đƣợc khám phá bởi CURE .......................... Hình dạng các cụm đƣợc khám phá bởi TT DBSCAN .......... Mô phỏng về tập dữ liệu đơn chiều ....................................... Hàm thuộc với trọng tâm của cụm A trong k-means ............. Hàm thuộc với trọng tâm của cụm A trong FCM .................. Các cụm khám phá đƣợc bởi thuật toán FCM ....................... Mô hình mạng Nơron ............................................................. Mô hình học có giám sát ........................................................ Mô hình FBACN .................................................................... Mô hình Lớp Layer1 của FBACN ......................................... Mô hình Lớp Layer2 của FBACN ......................................... Giao diện của thuật toán FCM khi khởi động ........................ Giao diện của thuật toán FCM khi làm việc .......................... Giao diện của chƣơng trình khi khởi động ............................. Giao diện của chƣơng trình khi chọn ảnh để phân cụm .......... Giao diện của chƣơng trình khi thực hiện phân cụm ............. 7 9 14 20 21 23 24 25 27 27 30 44 44 45 46 60 62 64 65 69 80 81 83 84 85 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 1 TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu .................................... 1.2. Quá trình khám phá tri thức .................................................................................... 1.3. Quá trình khai phá dữ liệu ...................................................................................... 1.4. Các phƣơng pháp khai phá dữ liệu ......................................................................... 1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL ........................................................... 1.6. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL ................................ 1.7. Các thách thức - khó khăn trong KPTT và KPDL .................................................. 1.8. Kết luận ................................................................................................................... 6 7 8 9 10 11 12 12 1.1. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu. Thông thƣờng, chúng ta coi dữ liệu nhƣ là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tƣợng” với một ý nghĩa nào đó khi đƣợc gửi cho một chƣơng trình dƣới một dạng nhất định. Các bits thƣờng đƣợc sử dụng để đo thông tin, và xem nó nhƣ là dữ liệu đã đƣợc loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trƣng một cách cơ bản cho dữ liệu. Tri thức đƣợc xem nhƣ là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã đƣợc nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác, tri thức có thể đƣợc coi là dữ liệu ở mức độ cao của sự trừu tƣợng và tổng quát. Khám phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu đƣợc. 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức, gồm các thuật toán khai thác dữ liệu chuyên dùng dƣới một số qui định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong CSDL nhƣng ẩn trong khối lƣợng lớn dữ liệu. 1.2. Quá trình khám phá tri thức Hình 1.1: Quá trình KPTT Bao gồm các bƣớc sau: Làm sạch dữ liệu (Data Cleaning): Loại bỏ dữ liệu nhiễu và dữ liệu không nhất quán. Tích hợp dữ liệu (Data Intergation): Dữ liệu của nhiều nguồn có thể đƣợc tổ hợp lại. 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lựa chọn dữ liệu (Data Selection): Lựa chọn những dữ liệu phù hợp với nhiệm vụ phân tích trích rút từ cơ sở dữ liệu. Chuyển đổi dữ liệu (Data Transformation): Dữ liệu đƣợc chuyển đổi hay đƣợc hợp nhất về dạng thích hợp cho việc khai phá. Khai phá dữ liệu (Data Mining): Đây là một tiến trình cốt yếu trong đó các phƣơng pháp thông minh đƣợc áp dụng nhằm trích rút ra mẫu dữ liệu. Đánh giá mẫu (Pattern Evaluation): Dựa trên một độ đo nào đó xác định lợi ích thực sự, độ quan trọng của các mẫu biểu diễn tri thức. Biểu diễn tri thức (Knowledge Presentation): Ở giai đoạn này các kỹ thuật biểu diễn và hiển thị đƣợc sử dụng để đƣa tri thức lấy ra cho ngƣời dùng. 1.3. Quá trình khai phá dữ liệu KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là giai đoạn duy nhất tìm ra đƣợc thông tin mới, thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con ngƣời có thể hiểu đƣợc. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật đƣợc phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán đƣợc những giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến quan tâm. Quá trình KPDL bao gồm các bƣớc chính đƣợc thể hiện nhƣ Hình 1.2 sau: 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 1.2: Quá trình KPDL  Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.  Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.  Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu đƣợc. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vƣớng mắc nhƣ: dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v.v..  Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc PKDL để tìm đƣợc các mẫu có ý nghĩa, các mẫu này đƣợc biểu diễn dƣới dạng luật kết hợp, cây quyết định... tƣơng ứng với ý nghĩa của nó. 1.4. Các phƣơng pháp khai phá dữ liệu Với hai mục đích khai phá dƣ liệu là Mô tả và Dự đoán, ngƣời ta thƣờng sử dụng các phƣơng pháp sau cho khai phá dữ liệu:  Luật kết hợp (association rules)  Phân lớp (Classfication)  Hồi qui (Regression)  Trực quan hóa (Visualiztion) Thu thập và tiền xử lý DL Thống kê tóm tắt Thuật toán KPD L Mẫu Xác định nhiệm vụ DL trực tiếp Xác định DL liên quan 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  Phân cụm (Clustering)  Tổng hợp (Summarization)  Mô hình ràng buộc (Dependency modeling)  Biểu diễn mô hình (Model Evaluation)  Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)  Phƣơng pháp tìm kiếm (Search Method) Có nhiều phƣơng pháp khai phá dữ liệu đƣợc nghiên cứu ở trên, trong đó có ba phƣơng pháp đƣợc các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp, Phân lớp dữ liệu và Phân cụm dữ liệu. 1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL KPDL là một lĩnh vực mới phát triển nhƣng thu hút đƣợc khá nhiều nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng dụng thực tế điển hình của KPDL: - Phân tích dữ liệu và hỗ trợ ra quyết định - Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân cụm ảnh màu - Chuẩn đoán triệu chứng, phƣơng pháp trong điều trị y học - Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học - Phân tích tình hình tài chính, thị trƣờng, dự báo gía cổ phiếu trong tài chính, thị trƣờng và chứng khoán - Phân tích dữ liệu marketing, khách hàng. - Điều khiển và lập lịch trình - Bảo hiểm - Giáo dục..... 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.6. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng trong KPDL. Vấn đề khai phá dữ liệu có thể đƣợc phân chia theo lớp các hƣớng tiếp cận chính sau: - Phân lớp và dự đoán (classification &prediction): Là quá trình xếp một đối tƣợng vào một trong những lớp đã biết trƣớc (ví dụ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết...). Đối với hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định (decision tree), mạng nơron nhân tạo (neural network),...Hay lớp bài toán này còn đƣơc gọi là học có giám sát - Học có thày (supervised learning). - Phân cụm (clustering/segmentation): Sắp xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên, tức là số lƣợng và tên cụm chƣa đƣợc biết trƣớc. Các đối tƣợng đƣợc gom cụm sao cho mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là lớn nhất và mức độ tƣơng tự giữa các đối tƣợng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán này còn đƣợc gọi là học không giám sát - Học không thày (unsupervised learning). - Luật kết hợp (association rules): Là dạng luật biểu diễn tri thức ở dạng khá đơn giản (Ví dụ: 80% sinh viên đăng ký học CSDL thì có tới 60% trong số họ đăng ký học Phân tích thiết kế hệ thống thông tin). Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trƣờng chứng khoán,... - Phân tích chuỗi theo thời gian (sequential/temporal patterns): Cũng tƣơng tự nhƣ khai phá dữ liệu bằng luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán bởi chúng có tính dự báo cao. 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - Mô tả khái niệm (concept desccription & summarization): Lớp bài toán này thiên về mô tả, tổng hợp và tóm tắt khái niệm (Ví dụ: tóm tắt văn bản). 1.7. Các thách thức - khó khăn trong KPTT và KPDL KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn hơn. Sau đây là một số các thách thức và khó khăn cần đƣợc quan tâm: + Các cơ sở dữ liệu lớn, các tập dữ liệu cần sử lý có kích thƣớc cực lớn, Trong thực tế, kích thƣớc của các tập dữ liệu thƣờng ở mức tera-byte (hàng ngàn giga-byte). + Mức độ nhiễu cao hoặc dữ liệu bị thiếu + Số chiều lớn + Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp + Quan hệ giữa các trƣờng phức tạp 1.8. Kết luận KPDL là lĩnh vực đã và đang trở thành một trong những hƣớng nghiên cứu thu hút đƣợc sự quan tâm của nhiều chuyên gia về CNTT trên thế giới. Trong những năm gần đây, rất nhiều các phƣơng pháp và thuật toán mới liên tục đƣợc công bố. Điều này chứng tỏ những ƣu thế, lợi ích và khả năng ứng dụng thực tế to lớn của KPDL. Chƣơng này đã trình bày một số kiến thức tổng quan về KPTT, những khái niệm và kiến thức cơ bản nhất về KPDL. 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 2 PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG PHÂN CỤM DỮ LIỆU 2.1. Khái niệm và mục tiêu của phân cụm dữ liệu ........................................................ 2.2. Các ứng dụng của phân cụm dữ liệu ...................................................................... 2.3. Các yêu cầu của phân cụm ..................................................................................... 2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu ................................................... 2.4.1. Phƣơng pháp phân cụm phân hoạch ............................................................. 2.4.2. Phƣơng pháp phân cụm phân cấp ................................................................. 2.4.3. Phƣơng pháp phân cụm dựa trên mật độ ...................................................... 2.4.4. Phƣơng pháp phân cụm dựa trên lƣới ........................................................... 2.4.5. Phƣơng pháp phân cụm dựa trên mô hình .................................................... 2.4.6. Phƣơng pháp phân cụm có dữ liệu ràng buộc ............................................... 2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu ................................................. 2.5.1. Các thuật toán phân cụm phân hoạch ........................................................... 2.5.2. Các thuật toán phân cụm phân cấp ............................................................... 2.5.3. Các thuật toán phân cụm dựa trên mật độ .................................................... 2.5.4. Các thuật toán phân cụm dựa trên lƣới ......................................................... 2.5.5. Các thuật toán phân cụm dựa trên mô hình .................................................. 2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc ............................................. 13 15 16 18 19 19 20 21 22 22 24 24 26 29 32 35 36 2.1. Khái niệm và mục tiêu của phân cụm dữ liệu Phân cụm dữ liệu là quá trình nhóm một tập các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm sao cho các đối tƣợng thuộc cùng một cụm là tƣơng đồng còn các đối tƣợng thuộc các cụm khác nhau sẽ không tƣơng đồng. Phân cụm dữ liệu là một ví dụ của phƣơng pháp học không có thầy. Không giống nhƣ phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trƣớc các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ… Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ một bƣớc tiền xử lí cho các thuật toán khai phá dữ liệu khác nhƣ là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm. 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.1: Mô tả tập dữ liệu vay nợ đƣợc phân thành 3 cụm. Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con ngƣời. Ngay từ lúc bé, con ngƣời đã học cách làm thế nào để phân biệt giữa mèo và chó, giữa động vật và thực vật và liên tục đƣa vào sơ đồ phân loại trong tiềm thức của mình. Phân cụm đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng....Với tƣ cách là một chức năng khai phá dữ liệu, phân tích phân cụm có thể đƣợc sử dụng nhƣ một công cụ độc lập chuẩn để quan sát đặc trƣng của mỗi cụm thu đƣợc bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt của các cụm để giúp cho việc phân tích đạt kết quả. Một vấn đề thƣờng gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lí dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trƣớc khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở đây đƣợc hiểu là các đối tƣợng dữ liệu không chính xác, không tƣờng minh hoặc là các đối tƣợng dữ liệu khuyết thiếu thông tin về một số thuộc tính... Một trong các kỹ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tƣơng ứng. Ngoài ra, dò tìm phần tử ngoại lai cũng là một trong những hƣớng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định một nhóm nhỏ các đối tƣợng dữ liệu khác thƣờng so với các dữ liệu trong CSDL, tức là các đối tƣợng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hƣởng của chúng tới quá trình và kết quả của phân cụm. Mục tiêu của phân cụm là xác định đƣợc bản chất nhóm trong tập DL chƣa có nhãn. Nhƣng để có thể quyết định đƣợc cái vì tạo thành một cụm tốt. Nó có thể đƣợc chỉ ra rằng không có tiêu chuẩn tuyệt đối “tốt” mà có thể không phụ thuộc vào kq phân cụm. Vì vậy, nó đòi hỏi ngƣời sử dụng phải cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu cầu. Theo các nghiên cứu cho thấy thì hiện nay chƣa có một phƣơng pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc CDL. Hơn nữa, các phƣơng pháp phân cụm cần có cách thức biểu diễn cấu trúc của các CDL, với mỗi cách thức biểu diễn khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực KPDL. 2.2. Các ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu có thể đƣợc ứng dụng trong nhiều lĩnh vực nhƣ: Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trƣng tƣơng đồng và những đặc tả họ từ các bản ghi mua bán trong CSDL Sinh học: Phân loại các gen với các chức năng tƣơng đồng và thu đƣợc các cấu trúc trong mẫu 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Thư viện: Phân loại các cụm sách có nội dung và ý nghĩa tƣơng đồng nhau để cung cấp cho độc giả Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí bồi thƣờng cao, nhận dạng gian lận thƣơng mại Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí,... nhằm cung cấp thông tin cho quy hoạch đô thị Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm WWW: Có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trƣờng Web. Các lớp tài liệu này trợ giúp cho việc KPTT từ dữ liệu. 2.3. Các yêu cầu của phân cụm Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng dụng tiềm năng của chúng đƣợc đƣa ra ngay chính trong những yêu cầu đặc biệt của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong KPDL: Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những tập dữ liệu nhỏ chứa ít hơn 200 đối tƣợng, tuy nhiên, một CSDL lớn có thể chứa tới hàng triệu đối tƣợng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh hƣởng tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các thuật toán phân cụm có khả năng mở rộng cao đối với các CSDL lớn ? Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều thuật toán đƣợc thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác nhau, nhƣ kiểu nhị phân, kiểu tƣờng minh (định danh - 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên không thứ tự), và dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này. Khám phá các cụm với hình dạng bất kỳ: Nhiều thuật toán phân cụm xác định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng cách Manhattan. Các thuật toán dựa trên các phép đo nhƣ vậy hƣớng tới việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ tƣơng tự nhau. Tuy nhiên, một cụm có thể có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng. Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật toán phân cụm yêu cầu ngƣời dùng đƣa vào những tham số nhất định trong phân tích phân cụm (nhƣ số lƣợng các cụm mong muốn). Kết quả của phân cụm thƣờng khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để xác định, nhất là với các tập dữ liệu có lƣợng các đối tƣợng lớn. Điều này không những gây trở ngại cho ngƣời dùng mà còn làm cho khó có thể điều chỉnh đƣợc chất lƣợng của phân cụm. Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chƣa biết hoặc dữ liệu sai. Một số thuật toán phân cụm nhạy cảm với dữ liệu nhƣ vậy và có thể dẫn đến chất lƣợng phân cụm thấp. Ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân cụm nhạy cảm với thứ tự của dữ liệu vào, ví dụ nhƣ với cùng một tập dữ liệu, khi đƣợc đƣa ra với các thứ tự khác nhau thì với cùng một thuật toán có thể sinh ra các cụm rất khác nhau. Do đó, việc quan trọng là phát triển các thuật toán mà ít nhạy cảm với thứ tự vào của dữ liệu. Số chiều lớn: Một CSDL hoặc một kho dữ liệu có thể chứa một số chiều hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tốt cho dữ liệu với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Ngƣời ta đánh giá việc phân cụm là có chất lƣợng tốt nếu nó áp dụng đƣợc cho dữ liệu có từ 3 chiều trở lên. Nó là sự thách thức với các đối tƣợng dữ liệu cụm trong không gian với số chiều lớn, đặc biệt vì khi xét những không gian với số chiều lớn có thể rất thƣa và có độ nghiêng lớn. Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện phân cụm dƣới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm những nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc. Dễ hiểu và dễ sử dụng: Ngƣời sử dụng có thể chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần đƣợc giải thích ý nghĩa và ứng dụng rõ ràng. Với những yêu cầu đáng lƣu ý này, nghiên cứu của ta về phân tích phân cụm diễn ra nhƣ sau: Đầu tiên, ta nghiên cứu các kiểu dữ liệu khác và cách chúng có thể gây ảnh hƣởng tới các phƣơng pháp phân cụm. Thứ hai, ta đƣa ra một cách phân loại chung trong các phƣơng pháp phân cụm. Sau đó, ta nghiên cứu chi tiết mỗi phƣơng pháp phân cụm, bao gồm các phƣơng pháp phân hoạch, phân cấp, dựa trên mật độ,... Ta cũng khảo sát sự phân cụm trong không gian đa chiều và các biến thể của các phƣơng pháp khác. 2.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong t._.hực tế, nó đều hƣớng tới hai mục tiêu chung đó là chất lƣợng của các cụm khám phá đƣợc và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể phân loại theo các cách tiếp cận chính sau : 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4.1. Phương pháp phân cụm phân hoạch Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm đƣợc thiết lập. Số các cụm đƣợc thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho việc tìm các cụm hình cầu trong không gian Euclidean. Ngoài ra, phƣơng pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phƣơng pháp này không thể xử lí các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ƣu toàn cục cho vấn đề PCDL, do nó phải tìm kiếm tất cả các cách phân hoạch có thể đƣợc. Chính vì vậy, trên thực tế thƣờng đi tìm giải pháp tối ƣu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lƣợng của cụm cũng nhƣ để hƣớng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Nhƣ vậy, ý tƣởng chính của thuật toán phân cụm phân hoạch tối ƣu cục bộ là sử dụng chiến lƣợc ăn tham (Greedy) để tìm kiếm nghiệm. 2.4.2. Phương pháp phân cụm phân cấp Phƣơng pháp này xây dựng một phân cấp trên cơ sở các đối tƣợng dữ liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ quy. Có hai cách tiếp cận phổ biến của kỹ thuật này đó là: * Hòa nhập nhóm, thƣờng đƣợc gọi là tiếp cận Bottom-Up * Phân chia nhóm, thƣờng đƣợc gọi là tiếp cận Top-Down 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.2: Các chiến lƣợc phân cụm phân cấp Thực tế áp dụng, có nhiều trƣờng hợp kết hợp cả hai phƣơng pháp phân cụm phân hoạch và phân cụm phân cấp, nghĩa là kết quả thu đƣợc của phƣơng pháp phân cấp có thể cải tiến thông qua bƣớc phân cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phƣơng pháp PCDL cổ điển, hiện đã có rất nhiều thuật toán cải tiến dựa trên hai phƣơng pháp này đã đƣợc áp dụng phổ biến trong KPDL. 2.4.3. Phương pháp phân cụm dựa trên mật độ Kỹ thuật này nhóm các đối tƣợng dữ liệu dựa trên hàm mật độ xác định, mật độ là số các đối tƣợng lân cận của một đối tƣợng dữ liệu theo một nghĩa nào đó. Trong cách tiếp cận này, khi một dữ liệu đã xác định thì nó tiếp tục đƣợc phát triển thêm các đối tƣợng dữ liệu mới miễn là số các đối tƣợng lân cận này phải lớn hơn một ngƣỡng đã đƣợc xác định trƣớc. Phƣơng pháp phân cụm dựa trên mật độ của các đối tƣợng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật này có thể khắc phục đƣợc các phần tử ngoại lai hoặc giá trị nhiễu rất tốt, tuy nhiên việc xác định các tham số mật độ của thuật toán là rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến kết quả phân cụm. 21 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4.4. Phương pháp phân cụm dựa trên lưới Kỹ thuật phân cụm dựa trên lƣới thích hợp với dữ liệu nhiều chiều, dựa trên cấu trúc dữ liệu lƣới để phân cụm, phƣơng pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian. Mục tiêu của phƣơng pháp này là lƣợng hóa dữ liệu thành các ô tạo thành cấu trúc dữ liệu lƣới. Sau đó, các thao tác phân cụm chỉ cần làm việc với các đối tƣợng trong từng ô trên lƣới chứ không phải các đối tƣợng dữ liệu. Cách tiếp cận dựa trên lƣới này không di chuyển các đối tƣợng trong các ô mà xây dựng nhiều mức phân cấp của nhóm các đối tƣợng trong một ô. Phƣơng pháp này gần giống với phƣơng pháp phân cụm phân cấp nhƣng chúng không trộn các ô, đồng thời giải quyết khắc phục yêu cầu đối với dữ liệu nhiều chiều mà phƣơng pháp phân phân cụm dựa trên mật độ không giải quyết đƣợc. Ƣu điểm của phƣơng pháp phân cụm dựa trên lƣới là thời gian xử lí nhanh và độc lập với số đối tƣợng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số ô trong mỗi chiều của không gian lƣới. Hình 2.3: Cấu trúc phân cấp 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4.5. Phương pháp phân cụm dựa trên mô hình Phƣơng này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lƣợc phân cụm phân hoạch hoặc phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách chúng hiệu chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phƣơng pháp phân cụm dựa trên mô hình cố gắng khớp giữa các dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu đƣợc tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai cách tiếp cận chính: mô hình thống kê và mạng nơron. Phƣơng pháp này gần giống với phƣơng pháp phân cụm dựa trên mật độ, vì chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã đƣợc xác định trƣớc đó, nhƣng đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm. 2.4.6. Phương pháp phân cụm có dữ liệu ràng buộc Sự phát triển của PCDL không gian trên CSDL lớn đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho ngƣời dùng để xác định các ràng buộc trong thế giới thực cần phải đƣợc thỏa mãn trong quá trình phân cụm. Để PCDL không gian hiệu quả hơn, các nghiên cứu bổ sung cần đƣợc thực hiện để cung cấp cho ngƣời dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm. 23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.4: Các cách mà các cụm có thể đƣa ra Hiện nay, các phƣơng pháp phân cụm trên đã và đang đƣợc phát triển và áp dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu đƣợc phát triển trên cơ sở của các phƣơng pháp đó nhƣ: Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, nhánh nghiên cứu này sử dụng các độ đo tƣơng tự để phân hoạch các đối tƣợng, nhƣng chúng chỉ áp dụng cho các dữ liệu có thuộc tính số. Phân cụm khái niệm: Kỹ thuật này đƣợc phát triển áp dụng cho dữ liệu hạng mục, chúng phân cụm các đối tƣợng theo các khái niệm mà chúng xử lí. Phân cụm mờ: Sử đụng kỹ thuật mờ để PCDL. Các thuật toán thuộc loại này chỉ ra lƣợc đồ phân cụm thích hợp với tất cả các hoạt động đời sống hàng ngày, chúng chỉ xử lí các dữ liệu thực không chắc chắn. Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của các mạng nơron. Mạng Kohonen có tầng nơron vào và các tầng nơron ra. Mỗi 24 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nơron của tầng vào tƣơng ứng với mỗi thuộc tính của bản ghi, mỗi một nơron vào kết nối với tất cả các nơron của tầng ra. Mỗi liên kết đƣợc gắn liền với một trọng số nhằm xác định vị trí của nơron ra tƣơng ứng. 2.5. Một số thuật toán cơ bản trong phân cụm dữ liệu 2.5.1. Các thuật toán phân cụm phân hoạch Thuật toán k-means Thuật toán này dựa trên độ đo khoảng cách của các đối tƣợng dữ liệu trong cụm. Trong thực tế, nó đo khoảng cách tới giá trị trung bình của các đối tƣợng dữ liệu trong cụm. Nó đƣợc xem nhƣ là trung tâm của cụm. Nhƣ vậy, nó cần khởi tạo một tập trung tâm các trung tâm cụm ban đầu, và thông qua đó nó lặp lại các bƣớc gồm gán mỗi đối tƣợng tới cụm mà trung tâm gần, và tính toán tại tung tâm của mỗi cụm trên cơ sở gán mới cho các đối tƣợng. Quá trình lặp này dừng khi các trung tâm hội tụ. Hình 2.5: Các thiết lập để xác định ranh giới các cụm ban đầu Mục đích của thuật toán k-means là sinh k cụm dữ liệu {C1, C2,..., Ck} từ một tập dữ liệu chứa n đối tƣợng trong không gian d chiều Xi = {xi1, xi2,..., xid}, i = 1  n, sao cho hàm tiêu chuẩn: 25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên     k i Cx ii mxDE 1 2 )( đạt giá trị tối thiểu, trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tƣợng. Hình 2.6: Tính toán trọng tâm của các cụm mới Thuật toán k-means bao gồm các bƣớc cơ bản sau : Input: Số cụm k và các trọng tâm cụm  k jj m 1 . Output: Các cụm C[i] (1  i  k) và hàm tiêu chuẩn E đạt giá trị tối thiểu. Begin (a) Bƣớc 1 : Khởi tạo Chọn k trọng tâm  k jj m 1 ban đầu trong không gian Rd (d là số chiều của dữ liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm. (b) Bƣớc 2: Tính toán khoảng cách Đối với mỗi điểm Xi (1  i  n), tính toán khoảng cách của nó tới mỗi trọng tâm mj (1  j  k). Sau đó tìm trọng tâm gần nhất đối với mỗi điểm. (c) Bƣớc 3: Cập nhật lại trọng tâm Đối với mỗi 1  j  k, cập nhật trọng tâm cụm mj bằng cách xác định trung bình cộng các vectơ đối tƣợng dữ liệu. (d) Điều kiện dừng: 26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lặp lại các bƣớc 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi. End. Thuật toán k-means trên đƣợc chứng minh là hội tụ và có độ phức tạp tính toán là ))3(( flopTnkdO  . Trong đó, n là số đối tƣợng dữ liệu, k là số cụm dữ liệu, d là số chiều,  là số vòng lặp, flopT là thời gian để thực hiện một phép tính cơ sở nhƣ phép tính nhân, chia,... Nhƣ vậy, do k-means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn.Tuy nhiên, nhƣợc điểm của k-means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hơn nữa, chất lƣợng PCDL của thuật toán k-means phụ thuộc nhiều vào các tham số đầu vào nhƣ: số cụm k và k trọng tâm khởi tạo ban đầu. Trong trƣờng hợp các trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của k-means là rất thấp, nghĩa là các cụm dữ liệu đƣợc khám phá rất lệch so với các cụm trong thực tế. Trên thực tế chƣa có một giải pháp tối ƣu nào để chọn các tham số đầu vào, giải pháp thƣờng đƣợc sử dụng nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. Ngoài ra thuật toán K-means ra, phân cụm phân hoạch còn bao gồm một số các thuật toán khac nhƣ: Thuật toán PAM; Thuật toán CLARA; Thuật toán CLARANS. 2.5.2. Các thuật toán phân cụm phân cấp Thuật toán CURE Trong khi hầu hết các thuật toán thực hiện phân cụm với các cụm hình cầu và kích thƣớc tƣơng tự, nhƣ vậy là không hiệu quả khi xuất hiện các phần tử ngoại lai. Thuật toán CURE khắc phục đƣợc vấn đề này và tốt hơn với các 27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên phần tử ngoại lai. Thuật toán này định nghĩa một số cố định các điểm đại diện nằm rải rác trong toàn bộ không gian dữ liệu và đƣợc chọn để mô tả các cụm đƣợc hình thành. Các điểm này đƣợc tạo ra nhờ lựa chọn các đối tƣợng nằm rải rác cho cụm và sau đó “co lại” hoặc di chuyển chúng về trung tâm cụm bằng nhân tố co cụm. Quá trình này đƣợc lặp lại và nhƣ vậy trong quá trình này, có thể đo tỉ lệ gia tăng của cụm. Tại mỗi bƣớc của thuật toán, hai cụm có cặp các điểm đại diện gần nhau (mỗi điểm trong cặp thuộc về mỗi cụm khác nhau) đƣợc hòa nhập. Nhƣ vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE khám phá đƣợc các cụm có hình dạng không phải là hình cầu. Việc co lại các cụm có tác dụng làm giảm tác động của các phần tử ngoại lai. Nhƣ vậy, thuật toán này có khả năng xử lí tốt trong trƣờng hợp có các phần tử ngoại lai và làm cho nó hiệu quả với những hình dạng không phải là hình cầu và kích thƣớc độ rộng biến đổi. Hơn nữa, nó tỉ lệ tốt với CSDL lớn mà không làm giảm chất lƣợng phân cụm. Hình 2.8: Các cụm dữ liệu đƣợc khám phá bởi CURE Hình 2.7: Khái quát thuật toán CURE 28 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Để xử lí đƣợc các CSDL 1ớn, CURE sử dụng mẫu ngẫu nhiên và phân hoạch, một mẫu là đƣợc xác định ngẫu nhiên trƣớc khi đƣợc phân hoạch, và sau đó tiến hành phân cụm trên mỗi phân hoạch, nhƣ vậy mỗi phân hoạch là từng phần đã đƣợc phân cụm, các cụm thu đƣợc lại đƣợc phân cụm lần thứ hai để thu đƣợc các cụm con mong muốn, nhƣng mẫu ngẫu nhiên không nhất thiết đƣa ra một mô tả tốt cho toàn bộ tập dữ liệu. Thuật toán CURE đƣợc thực hiện qua các bƣớc cơ bản sau: Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thƣớc bằng nhau: Ý tƣởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thƣớc của mỗi phân hoạch là n’/p (n’ là kích thƣớc của mẫu). Phân cụm các điểm của mỗi nhóm: Thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm đƣợc phân thành n’/pq cụm (với q > 1). Loại bỏ các phần tử ngoại lai: Trƣớc hết, khi các cụm đƣợc hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trƣờng hợp các phần tử ngoại lai đƣợc lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ. Phân cụm các cụm không gian: các đối tƣợng đại diện cho các cụm di chuyển về hƣớng trung tâm cụm, nghĩa là chúng đƣợc thay thế bởi các đối tƣợng gần trung tâm hơn. Đánh dấu dữ liệu với các nhãn tƣơng ứng. Độ phức tạp tính toán của thuật toán CURE là O(n21og(n)). CURE tà thuật toán tin cậy trong việc khám phá ra các cụm với hình thù bất kỳ và có thể áp dụng tốt đối với dữ liệu có phần tử ngoại lai và trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số nhƣ số các đối tƣợng đại diện, tỉ lệ co của các phần tử đại điện. 29 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ngoài thuật toán CURE ra, phân cụm phân cấp còn bao gồm một số thuật toán khac nhƣ: Thuật toán BIRCH; Thuật toán AGNES; Thuật toán DIANA; Thuật toán ROCK; Thuật toán CHANMELEON. 2.5.3. Các thuật toán phân cụm dựa trên mật độ Thuật toán DBSCAN Thuật toán DBSCAN thích nghi với mật độ dầy để phân cụm và khám phá ra các cụm có hình dạng bất kỳ trong không gian CSDL có nhiễu. Trên thực tế DBSCAN tìm kiếm cho các cụm bằng cách kiểm tra các đối tƣợng mà có số đối tƣợng láng giềng nhỏ hơn một ngƣỡng tối thiểu, tức là có tối thiểu MinPts đối tƣợng và mỗi đối tƣợng trong cụm tồn tại một đối tƣợng khác trong cụm giống nhau với khoảng cách nhỏ một ngƣỡng Eps. Tìm tất cả các đối tƣợng mà các láng giềng của nó thuộc về lớp các đối tƣợng đã xác định ở trên, một cụm đƣợc xác định bằng một tập tất cả các đối tƣợng liên thông mật độ các láng giềng của nó. DBSCAN lặp lại tìm kiếm ngay khi các đối tƣợng liên lạc mật độ từ các đối tƣợng trung tâm, nó có thể bao gồm việc kết hợp một số cụm có mật độ liên lạc. Quá trình kết thúc khi không tìm đƣợc điểm mới nào có thể thêm vào bất cứ cụm nào. DBSCAN có thể tìm ra các cụm với hình thù bất kỳ, trong khi đó tại cùng một thời điểm ít bị ảnh hƣởng bởi thứ tự của các đối tƣợng dữ liệu nhập vào. Khi có một đối tƣợng đƣợc chèn vào chỉ tác động đến một láng giềng xác định. Mặt khác, DBSCAN sử dụng tham số Eps và MinPts trong thuật toán để kiểm soát mật độ của các cụm. DBSCAN bắt đầu với một điểm tuỳ ý và xây dựng mật độ láng giềng có thể đƣợc đối với Eps và MinPts. Vì vậy, DBSCAN yêu cầu ngƣời dùng xác định bán kính Eps của các láng giềng và số các láng giềng tối thiểu MinPts, các tham số này khó mà xác định đƣợc tối ƣu, thông thƣờng nó đƣợc xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm. 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Độ phức tạp của DBSCAN là O(n2), nhƣng nếu áp dụng chỉ số không gian để giúp xác định các láng giềng của một đối tƣợng dữ liệu thì độ phức của DBSCAN đã đƣợc cải tiến là O(nlogn). Thuật toán DBSCAN có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều, khoảng cách Euclide đƣợc sử dụng để đo sự tƣơng tự giữa các đối tƣợng nhƣng không hiệu quả đối với dữ liệu đa chiều. Hình 2.9: Hình dạng các cụm đƣợc khám phá bởi thuật toán DBSCAN Thuật toán: DBSCAN khởi tạo điểm p tùy ý và lấy tất cả các điểm liên lạc mật độ từ p tới Eps và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo ra một cụm theo Eps và MinPts, nếu p là một điểm biên, không có điểm nào liên lạc mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu. Nếu sử dụng giá trị toàn cục Eps và Minpts, DBSCAN có thể hoà nhập hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả sử khoảng cách giữa hai tập dữ liệu S1 và S2 đƣợc định nghĩa là: dist(S1, S2) = min{dist(p, q) {p  S1 và q  S2}. Thuật toán DBSCAN đƣợc mô tả chi tiết nhƣ sau: ......... Modul chƣơng trình chính .......... DBSCAN(SetOfPoints, Eps, MinOts) //SetOfPoints is UNCLASSIFIED Clusterid:= NextId(NOISE); FOR i FROM 1 TO SetOfPoints.size DO 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Point := SetOfPoints.get(i); IF PointClId = UNCLASSIFIED THEN IF ExpandCluster(SetOfPoints, Point, ClusterId, Eps, MinPts) THEN ClusterId.= nextId(ClusterId) END IF END IF END FOR END; //DBSCAN --------Thủ tục ExpandCluster-------- ExpandClusster(SetOfPoints, Points, C1Id, Eps, MinPts): Boolean; seeds:= SetOfPoints.regionQuery(Point, Eps) IF seeds.size < MinPts THEN //no core point SetOfPoints.changeclId(Point, NOISE), RETURN False; ELSE //all points in seeds are density-reachable from Point SetOfPoints.changeClId(seeds, C1Id); seeds.delete(Point); WHILE seeds Empty DO currentP:= seeds.first(); result:= SetOfPoints.regionQuery(CurrentP, Eps); IF result.size >= MinPts THEN FOR i FROM 1 to result.size DO resultpP:= result.get(i); IF resultp.C1Id IN {UNCLASSIFIED, NOISE} THEN IF resultp.ClId = UNCLASSIFIED THEN seeds.append(resultP); END IF; 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên SetOfPoints.changeC1Id(resultP, C1Id), END IF; //UNCLASSIFIED or NOISE END FOR; END IF; //result.size >= Minpts seeds.delete(currentP); END WHILE; //seeds Empty RETURN True; END IF; END; //ExpandCluster Trong đó SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm đƣợc khám phá từ bƣớc trƣớc, C1Id (ClusterId) là nhãn đánh dấu phần tử dữ liệu nhiễu có thể thay đổi nếu chúng có thể liên lạc mật độ từ một điểm khác trong CSDL, điều này chỉ xảy ra đối với các điểm biên của dữ liệu. Hàm SetOfPoints.get(i) trả về phần tử thứ i của SetOfPoints. Thủ tục SetOfPoints.regionQuery(Point, Eps) trả về một danh sách các điểm dữ liệu lân cận với điểm Point trong ngƣỡng Eps từ tập dữ liệu SetOfPoints. Trừ một số trƣờng hợp ngoại lệ, kết quả của DBSCAN là độc lập với thứ tự duyệt các đối tƣợng dữ liệu. Eps và MinPts là hai tham số toàn cục đƣợc xác định bằng thủ công hoặc theo kinh nghiệm. Tham số Eps đƣợc đƣa vào là nhỏ so với kích thƣớc của không gian dữ liệu, thì độ phức tạp tính toán trung bình của mỗi truy vấn là O(logn). Ngoài thuật toán DBSCAN ra, phân cụm dựa trên mật độ còn bao gồm 2 thuật toán khác nhƣ: Thuật toán OPTICS; Thuật toán DENCLUE. 2.5.4. Các thuật toán phân cụm dựa trên lƣới Thuật toán STING STING là kỹ thuật phân cụm đa phân giải dựa trên lƣới, trong đó vùng không gian dữ liệu đƣợc phân rã thành số hữu hạn các ô chữ nhật, điều này có 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nghĩa là các ô lƣới đƣợc hình thành từ các ô lƣới con để thực hiện phân cụm. Có nhiều mức của các ô chữ nhật tƣơng ứng với các mức khác nhau của phân giải trong cấu trúc lƣới, và các ô này hình thành cấu trúc phân cấp: mỗi ô ở mức cao đƣợc phân hoạch thành số các ô nhỏ ở mức thấp hơn tiếp theo trong cấu trúc phân cấp. Các điểm dữ liệu đƣợc nạp từ CSDL, giá trị của các tham số thống kê cho các thuộc tính của đối tƣợng dữ liệu trong mỗi ô lƣới đƣợc tính toán từ dữ liệu và lƣu trữ thông qua các tham số thống kê ở các ô mức thấp hơn. Các giá trị của các tham số thống kê gồm: số trung bình - mean, số tối đa - max, số tối thiểu - min, số đếm - count, độ lệch chuẩn - s, ... Các đối tƣợng dữ liệu lần lƣợt đƣợc chèn vào lƣới và các tham số thống kê ở trên đƣợc tính trực tiếp thông qua các đối tƣợng dữ liệu này. Các truy vấn không gian đƣợc thực hiện bằng cách xét các ô thích hợp tại mỗi mức của phân cấp. Một truy vấn không gian đƣợc xác định nhƣ là một thông tin khôi phục lại của dữ liệu không gian và các quan hệ của chúng. STING có khả năng mở rộng cao, nhƣng do sử dụng phƣơng pháp đa phân giải nên nó phụ thuộc chặt chẽ vào trọng tâm của mức thấp nhất. Đa phân giải là khả năng phân rã tập dữ liệu thành các mức chi tiết khác nhau. Khi hoà nhập các ô của cấu trúc lƣới để hình thành các cụm, nó không xem xét quan hệ không gian giữa các nút của mức con không đƣợc hoà nhập phù hợp (do chúng chỉ tƣơng ứng với các cha của nó) và hình dạng của các cụm dữ liệu khám phá đƣợc, tất cả ranh giới của các cụm có các biên ngang và dọc, theo biên của các ô và không có đƣờng biên chéo đƣợc phát hiện ra. Một trong những hạn chế trong khi sử dụng cách tiếp cận đa phân giải để thực hiện phân tích cụm chất lƣợng của phân cụm STING hoàn toàn phụ thuộc vào tính chất hộp ở mức thấp của cấu trúc lƣới. Nếu tính chất hộp là mịn, dẫn đến chi phí thời gian xử lý tăng, tính toán trở nên phức tạp và nếu 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên mức dƣới cùng là quá thô thì nó có thể làm giảm bớt chất lƣợng và độ chính xác của phân tích cụm. Cấu trúc dữ liệu lƣới thuận tiện cho quá trình xử lí song song và cập nhật liên tục, khi duyệt toàn bộ CSDL một lần để tính toán các đại lƣợng thống kê cho mỗi ô, nên nó rất hiệu quả và do đó độ phức tạp thời gian để tạo các cụm xấp xỉ O(n), trong đó n là tổng số các đối tƣợng. Sau khi xây dựng cấu trúc phân cấp, thời gian xử lý cho các truy vấn là O(g), trong đó g là tổng số ô lƣới ở mức thấp (g << n). Thuật toán STING gồm các bƣớc sau: Xác định tầng để bắt đầu: Với mỗi cái của tầng này, tính toán khoảng tin cậy (hoặc ƣớc lƣợng khoảng) của xác suất mà ô này liên quan tới truy vấn. Từ khoảng tin cậy của tính toán trên, gán nhãn cho là có liên quan hoặc không liên quan. Nếu lớp này là lớp dƣới cùng, chuyển sang Bƣớc 6; nếu khác thì chuyển sang Bƣớc 5. Duyệt xuống dƣới của cấu trúc cây phân cấp một mức. Chuyển sang Bƣớc 2 cho các ô mà hình thành các ô lên quan của lớp có mức cao hơn. Nếu đặc tả đƣợc câu truy vấn, chuyển sang Bƣớc 8; nếu không thì chuyển sang Bƣớc 7. Truy lục dữ liệu vào trong các ô liên quan và thực hiện xử lí. Trả lại kết quả phù hợp yêu cầu của truy vấn. Chuyển sang Bƣớc 9. Tìm thấy các miền có các ô liên quan. Trả lại miền mà phù hợp với yêu cầu của truy vấn . Chuyển sang Bƣớc 9. 9. Dừng. Ngoài thuật toán STING ra, phân cụm dựa trên lƣới còn có thêm một thuật toán khác là: Thuật toán CLIQUE. 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.5.5. Các thuật toán phân cụm dựa trên mô hình Thuật toán EM Thuật toán EM đƣợc xem nhƣ là thuật toán dựa trên mô hình hoặc là mở rộng của thuật toán k-means. Thật vậy, EM gán các đối tƣợng cho các cụm đã cho theo xác suất phân phối thành phần của đối tƣợng đó. Phân phối xác suất thƣờng đƣợc sử dụng là phân phối xác suất Gaussian với mục đích là khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là hàm logarit khả năng của đối tƣợng dữ liệu, đây là hàm tốt để mô hình xác suất cho các đối tƣợng dữ liệu. EM có thể khám phá ra nhiều hình dạng cụm khác nhau, tuy nhiên do thời gian lặp của thuật toán khá nhiều nhằm xác định các tham số tốt nên chi phí tính toán của thuật toán khá cao. Đã có một số cải tiến đƣợc đề xuất cho EM dựa trên các tính chất của dữ liệu: có thể nén, có thể sao lƣu trong bộ nhớ và có thể hủy bỏ. Trong các cải tiến này, các đối tƣợng bị hủy bỏ khi biết chắc chắn đƣợc nhãn phân cụm của nó, chúng đƣợc nén khi không bị loại bỏ và thuộc về một cụm quá lớn so với bộ nhớ và chúng sẽ đƣợc lƣu lại trong các trƣờng hợp còn lại. Thuật toán đƣợc chia thành hai bƣớc và quá trình đó đƣợc lặp lại cho đến khi vấn đề đƣợc giải quyết: E: hbha         2 1 , 2 1 2 1 M: )(6 , dcb ba ba     Các bƣớc thực hiện của thhuật toán EM Khởi tạo tham số: },...,,,,...,,{ )0()0(2 )0( 1 )0()0( 2 )0( 1 KKo ppp  Bước E: 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   k t j t jjk t i t iik tk tjtjk tkj PxP PxP xP PxP xP )(2)( )(2)( ),,|( ),,|( ),( ),(),|( ),|(    Bước M:    k tki kk tkit i xP xxP ),|( ),|( )1(    R xP p k tkit i   ),|( )1(  Lặp lại bước 2 và 3 cho đến khi đạt được kết quả Ngoài thuật toán EM ra, phân cụm dựa trên mô hình còn có thêm một thuật toán khác là: Thuật toán COBWEB. 2.5.6. Các thuật toán phân cụm có dữ liệu ràng buộc Thuật toán Phân cụm mờ: FCM, FCM và FCM-Cải tiến (Các thuật toán này sẽ đƣợc đề cập chi tiết ở chƣơng kế tiếp). Tóm lại, các kỹ thuật PCDL trình bày ở trên đã đƣợc sử dụng rộng rãi trong thực tế, thế nhƣng hầu hết chúng chỉ nhằm áp dụng cho tập dữ liệu với cùng một kiểu thuộc tính. Vì vậy, việc PCDL trên tập dữ liệu có kiểu hỗn hợp là một vấn đề đặt ra trong KPDL ở giai đoạn hiện nay. 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 3 KỸ THUẬT PHÂN CỤM DỮ LIỆU MỜ 3.1. Tổng quan về phân cụm mờ ................................................................................... 3.2. Các thuật toán trong phân cụm mờ ........................................................................ 3.2.1. Thuật toán FCM(Fuzzy C-means) ..................................................................... 3.2.1.1. Hàm mục tiêu .............................................................................................. 3.2.1.2. Thuật toán FCM .......................................................................................... 3.2.2. Thuật toán FCM(ε- Insensitive Fuzzy C-means) ............................................. 3.2.2.1. Hàm mục tiêu .............................................................................................. 3.2.2.2. Thuật toán FCM ........................................................................................ 3.2.3. Thuật toán FCM-Cải tiến ................................................................................... 3.2.3.1. Thuật toán 1: Thuật toán lựa chọn các điểm dữ liệu làm ứng viên cho việc chọn các trung tâm của các cụm ......................................................... 3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên ........................................ 3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu hàm mục tiêu .. 3.2.3.4. Thuật toán 4: Gán các trung tâm có liên kết “gần gũi” vào một cụm ....... 3.2.3.5. Tổng kết thuật toán FCM-Cải tiến .............................................................. 37 38 39 39 42 46 46 48 49 49 51 51 52 56 3.1. Tổng quan về phân cụm mờ Trong cuộc sống, chúng ta đã gặp rất nhiều ứng dụng của bài toán phân cụm. Chẳng hạn nhƣ trong ngành bƣu điện, hàng ngày bƣu điện phải phân loại thƣ theo mã nƣớc, trong mã nƣớc lại phân loại theo mã tỉnh/thành phố, sau đó khi thƣ về đến bƣu điện tỉnh thì bƣu điện tỉnh lại phải phân loại thƣ theo quận/huyện để gửi đi, đến bƣu điện quận/huyện lại phân loại thƣ theo xã/phƣờng để gửi thƣ. Đó chính là một ứng dụng của bài toán phân cụm rõ. Vậy bài toán phân cụm rõ là gì? Ta có thể định nghĩa bài toán phân cụm rõ nhƣ sau: Cho tập dữ liệu mẫu X, ta kiểm tra các điểm dữ liệu xem nó giống với đặc điểm của nhóm nào nhất thì ta gán điểm dữ liệu đó vào trong nhóm đó. Nhƣng trong thực tế không phải lúc nào bài toán phân cụm rõ cũng áp dụng đƣợc. Chẳng hạn, ta có phép phân loại sau: Những ngƣời đi xe máy xịn thì thuộc nhóm ngƣời giàu, những ngƣời đi xe máy thƣờng thuộc nhóm ngƣời bình dân. Vậy ngƣời 38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nghèo mà đi xe máy xịn thì chúng ta xếp ngƣời đó vào nhóm nào? Vì vậy, chúng ta cần đƣa vào khái niệm bài toán phân cụm mờ. Trong các phƣơng pháp phân cụm đã giới thiệu trong chƣơng trƣớc, mỗi phƣơng pháp phân cụm phân hoạch một tập dữ liệu ban đầu thành các cụm dữ liệu có tính tự nhiên và mỗi đối tƣợng dữ liệu chỉ thuộc về một cụm dữ liệu, phƣơng pháp này chỉ phù hợp với việc khám phá ra các cụm có mật độ cao và rời nhau, với đƣờng biên giữa các cụm đƣợc xác định tốt. Tuy nhiên, trong thực tế, đƣờng biên giữa các cụm có thể mờ, các cụm có thể chồng lên nhau, nghĩa là một số các đối tƣợng dữ liệu thuộc về nhiều các cụm khác nhau, do đó mô hình này không mô tả đƣợc dữ liệu thực. Vì vậy ngƣời ta đã áp dụng lý thuyết về tập mờ trong PCDL để giải quyết cho trƣờng hợp này. Cách thức kết hợp này đƣợc gọi là Phân cụm mờ. Phân cụm mờ là phƣơng pháp phân cụm dữ liệu mà cho phép mỗi điểm dữ liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Ruspini (1969) giới thiệu khái niệm phân hoạch mờ để mô tả cấu trúc cụm của tập dữ liệu và đề xuất một thuật toán để tính toán tối ƣu phân hoạch mờ. Dunn (1973) mở rộng phƣơng pháp phân cụm và đã phát triển thuật toán phân cụm mờ. Ý tƣởng của thuật toán là xây đựng một phƣơng pháp phân cụm mờ dựa trên tối thiểu hóa hàm mục tiêu. Bezdek (1981) cải tiến và tổng quát hóa hàm mục tiêu mờ bằng cách đƣa ra trọng số mũ để xây dựng thuật toán phân cụm mờ và đƣợc chứng minh độ hội tụ của các thuật toán là cực tiểu cục bộ. 3.2. Các thuật toán trong phân cụm mờ K-means là thuật toán PCDL rõ và C-means là thuật toán phân cụm mờ tƣơng ứng, hai thuật toán này cùng sử dụng chung một chiến lƣợc phân cụm dữ liệu. Thuật toán C-means mờ hay còn gọi tắt là thuật toán FCM (Fuzzy C-means) đã đƣợc áp dụng thành công trong giải quyết một số lớn 39 Số h._.iệu – Đại học Thái Nguyên 4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm Lớp Layer1 của FBACN có thể sử dụng mạng Hopfield hoặc mạng Nơron đa khớp tuỳ thuộc vào các ràng buộc của FC-partition (FC- fuzzy c). Nếu ràng buộc làm cho hàm mục tiêu có dạng bậc cao, hoặc dạng logarithm, hoặc dạng sin, v.v.. thì ta sử dụng mạng Nơron đa khớp thay vì dùng mạng Hopfield đơn giản. Hình 4.4: Mô hình Lớp Layer1 của FBACN Gọi  ji là trọng số kết nối hoạt động của Nơron j với Nơron vào i. Tất cả các đầu vào đến Nơron thứ j đƣợc kí hiệu là ij. Khi đó, tổng hợp các tín hiệu đầu vào đối với Nơron j là: 1     n j i ji j i net v i (1). Với vi là đầu ra của Nơron i, f là hàm đơn điệu tăng và liên tục. Ta có hàm kích hoạt 2 ( ) 1 1 exp( . ) j j f net r net     (2). ở đây, ngƣỡng r > 0 làm tăng tính thích nghi và khả năng tính toán của mạng Nơron. Giả sử g là chỉ số đệ quy và khi đó 66 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( 1) ( ) ( ) 1 ( ) ( . ) s g g g j j ji i j i v f net f v i     (3) Khi đó, ta có thể diễn tả mạng Nơron thông qua ma trận NET sau: NET = WV + I (4) với 1 2 s net net NET net               , 11 1 21 2 1 s s s ss W                        , 1 2 s v v V v               và 1 2 s i i I i               Để đánh giá tính ổn định của hệ thống trong hình 4.4, chúng ta dùng hàm tính toán năng lƣợng CEF(computational energy function-CEF). Ta có CEF(E) là: 1 . . . 2 T TE V W V I V   (5) Hay cụ thể hơn là: 1 1 12 1 . . s s ji i j j j j i j s E v v i v        (6) Trong công thức (6) thì E là dạng toàn phƣơng. Vì vậy, trong mạng Nơron động này ta có thể dùng hàm mục tiêu dạng toàn phƣơng để tối ƣu hóa các tham số. Tiếp theo, ta sẽ lý giải sự phù hợp giữa hàm mục tiêu của FC-partion và hàm tính toán năng lƣợng của FBACN. Ta có hàm mục tiêu của FC-partion là: , 1 1 ( ; ) 2 ( ) n c T T T m m k k i k i i i k k i z U v x x v x v v u          (7) Trong Layer1 của FBACN, các tham số tối ƣu là các trung tâm cụm vi. Các độ thuộc mới ui,k đƣợc thực hiện từ lớp 2 tới Layer1 sẽ kích hoạt hồi quy trong Layer1 để tối ƣu vi. Ngoài ra, ui,k tạm thời coi là các hằng số trong khi hồi quy trong Layer1. Từ định nghĩa của hàm mục tiêu, các véctơ trung tâm của các cụm p ipiii Rvvvv  ),..,,( 21 là véctơ p chiều. Vì vậy, ta phải khai triển 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (7) để khử biểu thức véctơ trƣớc khi nó đƣợc đem so sánh với hàm tính toán năng lƣợng thăng giá trị. Thăng giá trị đƣợc khai triển trong công thức (7) với lần khử đầu tiên là: 2 , , , , 1 1 1 ( ; ) 2 . ( ) pn c m m i l k l i l i k k i l z U v v x v u          (8) Quan sát (6) và (8) ta thấy sự khác nhau chính giữa hai công thức này là cách ký hiệu khác nhau. Trong mạng Nơron, thì các hoạt động ra của các Nơron đƣợc ký hiệu một cách duy nhất bằng một ký hiệu dƣới dòng. Chẳng hạn, hoạt động ra vi với si ...1 . Tuy nhiên, sau khi khai triển hàm mục tiêu của FC-pariton, có 2 từ viết dƣới dòng trong tham số vi,l, với 1..1, 1..l i c  . Để thống nhất trong cách thể hiện, ta ký hiệu lại nhƣ sau: , ( 1).i l i p lv v   (9) Khi đó, ta viết lại biểu thức (8) nhƣ sau: , ( 1) , 1 1 1 ( ; ) [ 2( ) . . pn c m m i k i p l k l k i l z U v u v x       2 , ( 1)( ) . ] m j k i p lu v   (10) Số Nơron s trong Layer1 ở (6) là c p . Ta có 1 2 c p i i I i                ,với ( 1) , , 1 2 . n m i p l i k k l k i u x     , 1.. 1..i c và l p  (11) và các phần tử của ma trận W đƣợc xác định bởi: / , 1 2 , 0, n m i p k kji u i j i j             , , 1..i j c n  (12) với ký hiệu | x | là cách lấy số nguyên cao hơn và gần nhất so với x. 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Quá trính tối ƣu của Layer1: Mục tiêu của mạng hồi quy là làm cho hàm mục tiêu xấp xỉ tới giá trị nhỏ nhất. Do W là ma trận đối xứng nên WT=W, ta lấy gradient của véctơ năng lƣợng trong (5) ta đƣợc: 1 ( ). . 2 T E W W V I W V I NET          (13) và ( ) . ( )T TE E V NET V       1 . s j j j net v     (14) Tiếp theo, chúng ta xây dựng hàm kích hoạt (liên tục hoặc rời rạc) f đƣợc sử dụng ở trong Layer1 của FBACN theo công thức sau: ( ) ( ) ( 1) ( ) ( ) , 0 ( ) , 0 g g j j jg g j g g j j j v if net v f net v if net            (15) với j là giá trị dƣơng nhỏ nhất để điều chỉnh vj. Ta thấy khi ( ) 0gjnet  thì ( 1) ( )g g j j j jv v v     >0, 1 . 0 s j j j E net v       . Trong kiểu kiến trúc này, thì sự cập nhật hệ số j với giá trị không hạn chế. Theo phƣơng pháp mà ta đã thiết kế thì cách lựa chọn giá trị của nó là phù hợp với tiến triển của Layer1. 4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc Lớp mạng Layer2 của FBACN có chức năng là tối ƣu hóa lớp các độ thuộc. Ta có thể coi các vi là các hằng số tạm thời trong khi lớp Layer2 hồi quy. Ta có tập 2 ,k i i kx v d  . Khi đó, công thức:   2 , 1 1 ( ; ) c n m m i k k i i k z U v u x v     đƣợc viết lại là , , 1 1 ( ) c n m i k i k i k u d    . Khi đó, bài toán tối ƣu trong lớp Layer2 của FBACN là: làm min , , 1 1 ( ) . c n m i k i k i k u d    với ràng buộc , 1 1, 1.. c i k i u k n     . 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Theo công thức Lagrange thì ta có thể phát biểu lại bài toán nhƣ sau: 2 , , , 1 1 1 ( ) 1 n c c m i k i k i k k i i u d u                  (16) với  là tham số Lagrange (thƣờng 10000 100000  ). Ta ký hiệu lại , ( 1).i k k c iu u   và , ( 1).i k k c id d   (17) Khi đó, ta có thể biểu diễn lại hàm mục tiêu là: 2 ( 1). ( 1). ( 1). 1 1 1 ( ) . ( 1) n c c m k c i k c i k c i k i i u d u                 (18) Trong công thức (18) thì số hạng có bậc cao nhất là ( 1).( ) m k c iu   (thông thường ta chọn m=2) với k=1, 2, ..,n và i = 1, 2, ..., c. Nhƣng mạng Hopfield chỉ phù hợp với bài toán tối ƣu bậc hai. Vì vậy, ta phát triển mạng Nơron đa khớp cho các bài toán tối ƣu chung. Tức mạng Nơron đa khớp có thể giải quyết đƣợc với bất kỳ hàm mục tiêu bậc cao có ràng buộc nào. Mô hình mạng Nơron đa khớp đơn giản đƣợc sử dụng cho Layer2 nhƣ sau: Hình 4.5: Mô hình Lớp Layer2 của FBACN Tính động của mạng Nơron đa khớp trong hình 4.5 là: 70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( 1) ( ) ( ) ( ) 1 ( ) ( ( . . ) ) S g g g g j j ji i ji i j i u f net f u z u i      , với j=1, 2, ..., s. (19) Ta có ma trận đầu vào mạng: . .NET WU ZU I   (20) Với 11 12 1 21 22 2 1 2 s s s s ss z z z z z z Z z z z                   và 1 2 S u u U u                                   1 1 2 1 1 )1( m nxc m m m u u u U  , m > 1 và U(1) = U (21) Ta ký hiệu chuyển vị của U(m-1) là: ( 1) T mU  . Khi đó, hàm tính toán năng lƣợng của mạng Nơron sẽ đƣợc tính bởi công thức: IUUZUU m E TTTm ... 2 1 -W.U. 1 )1(               (22) Với số lƣợng Nơron s trong lớp Layer2 là n c . Ta có thể tính toán các phần tử của ma trận W, Z và I nhƣ sau: 1 2 0 0 0 0 0 0 c n d d W m d                       tức là các phần tử của W đƣợc tính theo công thức sau: , 0 , md i j i ji i j          , , 1,2,..i j c n  (23) Z là ma trận cỡ ( ) ( )c n c n   và đƣợc xác định nhƣ sau: 2 ( 1). . 0 , , ji i i c j c c c if z                    với i,j = 1, 2, ..., c n . (24) Và ma trận I là ma trận một chiều cỡ c n và đƣợc xác định nhƣ sau: otherwise 71 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 2 2 I                 Do ma trận trọng số W là đối xứng (W được gọi là đối xứng nếu A. W.B = B.W.A), vì vậy hàm tính toán năng lƣợng ở (22) đƣợc biểu diễn là: IUUZUU m E TTT ... 2 1 W.U. 1 1)-(m              (25) U có thể điều chỉnh hai ma trận trọng số W và Z. Khi đó, ma trận NET của mạng Nơron đa khớp đƣợc xác định nhƣ sau: 1. .mNET WU ZU I     Gọi h là hàm số xác định bởi: 1)(  mjj uuh (26). Khi đó, h đƣợc gọi là hàm để tính 1m ju  Và tính động của lớp Layer2 đƣợc thể hiện ở công thức: ( 1) ( ) ( ) g g u f net j j   ( ) 1 ( ) 1 ( ( ( ) ) ) s g m g ji j ji j j i f u z u i      (27) Với net j là tổng đầu vào của Nơron thứ j và đƣợc tính bởi công thức: jiji m iji s i j iuzunet     )..( 1 1  (28) Theo công thức (25), ta có gradient năng lƣợng E : sjiuzu u E s i jiji m iji j ..1),)..(( 1 1       với s = n c (29) Từ (28) và (29) ta có , 1.. E net j s ju j      (30) Quá trình tối ƣu của Layer2 Khi hàm mục tiêu (18) đƣợc cân bằng với hàm tính toán năng lƣợng (25) và gradient tính toán năng lƣợng đƣợc liên kết với giá trị net vào, kết quả tối ƣu dần đạt đƣợc khi mạng tiến triển. Từ khái niệm năng lƣợng, hàm 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên rời rạc f là hàm kích hoạt của mạng Nơron đa khớp đƣợc xây dựng giống nhƣ của lớp thứ nhất: Vectơ năng lƣợng gradient đƣợc tính toán liên quan đến uj: j j net u    Hàm kích hoạt rời rạc đƣợc đƣa ra : ( ) ( ) ( 1) ( ) ( ) 0, ( ) , g g j j jg g j j g j j if net otherwise u u f net u            (31) Với vectơ năng lƣợng gradient luôn âm và công thức (31), đảm bảo mạng Layer2 sẽ tối ƣu trong quá trình tiến hoá. 4.5. Sự hội tụ của FBACN 4.5.1. Chứng minh sự hội tụ của FBACN Một yếu tố quan trọng cho mạng hồi quy đó là khả năng ổn định của mạng. Trƣớc khi đƣa ra tính ổn định của mạng FBACN, chúng ta sẽ bắt đầu với một vài định nghĩa về không gian Metric và định lý đƣa ra bởi Steck và sau đó là một định lý hội tụ phổ quát. Định nghĩa 1: Trong không gian Metric cho tập X và hàm d: X X R  thỏa mãn các điều kiện: 1) ( , ) 0, ,d x y x y X   2) ( , ) 0d x y x y   3) ( , ) ( , ), ,d x y d y x x y X   4) ( , ) ( , ) ( , )d x z d x y d y z , ,x y z X  Định nghĩa 2: Cho X là không gian Metric với khoảng cách d và : X X  . Điểm x đƣợc gọi là điểm cố định của  nếu ( )x x  . Định nghĩa 3: Ánh xạ  là co nếu tồn tại c*, với *0 1c  sao cho:   ),(.)(),( * yxdcyxd  , Xyx , (32) 73 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nếu  thỏa mãn (32) thì  chỉ có 1 điểm cố định. Thật vậy, giả sử có 2 điểm cố định x và y. Khi đó theo (32) ta có: *( , ) . ( , )d x y c d x y . Vì vậy, d(x,y)=0, nên x = y. Vậy ta có thể khái quát điều trên thông qua định lý sau: Định lý về ánh xạ co(ánh xạ thu gọn-AXC): Ánh xạ co của không gian Metric đầy đủ có duy nhất một điểm cố định. Định lý 1: Cho mạng Nơron nhân tạo hồi quy kết nối đầy đủ gồm các Nơron s với kích hoạt động     s i j g iji g j inetfnet 1 )()1( )(. (33), với f là một hàm có giới hạn, liên tục và có giá trị thực, hàm có đạo hàm có giới hạn và nếu thỏa mãn: s cf ji 1** max '  , sji ..1&  (34) thì mạng hội tụ đến một điểm cố định duy nhất đối với bất kỳ một giá trị khởi tạo nào của mạng. Bổ đề: với mỗi hàm f thỏa mãn điều kiện giả thuyết, thì với bất kỳ ,x y R ta có '( ) ( ) maxf x f y f x y   (35) Dựa vào các định nghĩa, định lý và bổ đề ở trên, một định lý hội tụ phổ biến cho mạng Nơron đa khớp nối đƣợc đƣa ra nhƣ sau: Định lý 2(đối với mạng Nơron đa khớp nối): Ứng với mỗi mạng Nơron đa khớp nối gồm s Nơron có hai trọng số ji và jiz với tính động kích hoạt sau: ( 1) ( ) 1 ( ) 1 ( ( )) ( ) S g g m g j ji j ji j j i net f net z f net i      (36) ở đây f là hàm có giới hạn, liên tục và có giá trị thực. Nếu f thỏa mãn điều kiện: 1 ' ** max 1 ( )m ji jif z c s    , (với i, j = 1, 2, ..., s) (37) thì mạng hội tụ đến một giá trị cố định duy nhất đối với với mọi giá trị khởi đầu của mạng. Chứng minh: Theo định lý về ánh xạ co, để chứng minh FBACN là hội tụ đến một điểm duy nhất thì chúng ta phải chỉ ra tồn tại một hằng số 74 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên c* (0,1) sao cho với mọi giá trị 1 2( , ,..., ) S Snetx netx netx netx  và 1 2( , ,..., ) S Snety nety nety nety  thì   ),(.)(),( * netynetxdcnetynetxd  (38) Ta định nghĩa hàm số:             s j s i jiji m ijis inetfznetfnetnetnetnet 1 1 1 21 ))(.))(((),...,,()(  (39) Với không gian s là đầy đủ với Metric đã lựa chọn, thì ta có: ( , ) 1 s d netx nety netx nety netx nety i ii      , , snetx nety (40) Ta có : ( ( ), ( )) ( ) ( )    d netx nety netx nety = 1 1 1 1 ( ( )) ( ( )) ( ) ( ) S S m m i i ji i i ji j i f netx f nety f netx f nety z           ' 1 ' ' max max 1 1 ( ) S S m i i ji i i ji j i f netx nety f netx nety z           (41) ** 1 1 S S i i i j netx nety c      = *. ( , )c d netx nety (42) với * ** ** 1 . S j c c s c    . Theo (37) thì ** (0,1)c  (43) Theo (42) và (43) thì ánh xạ là ánh xạ co. Do đó, theo điều kiện của (37) thì mạng Nơron đang xét là hội tụ về một điểm duy nhất. 4.5.2. Sự hội tụ FBACN liên tục của Layer1 Hàm kích hoạt của Layer1 đƣợc xây dựng nhƣ sau: 2 ( ) ( ) 1 exp( . ) j f net v j j jr net j j       (44) Với j và r j là các số thực dƣơng. Ta cần tìm giá trị max của đạo hàm cấp 1 của (44). Ta biết rằng đạo hàm cấp 1 của hàm f là cực đại tại x nếu đạo 75 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên hàm cấp 2 của hàm f tại x là bằng 0. Giả sử ''( ) 0f net j  thì ta có netj=0. Vì vậy, giá trị max của ' f là đạt cực đại địa phƣơng tại netj = 0 và giá trị đó là . ' '( )max 2 r j j f f net j    (45) Mặt khác 2 0n ji    nên ta có ' '0 2 . 2 . .max maxf n f n rji j j     (46) Ta có 1 1 . . . . n r r j j js s n j      (47) với s là số lƣợng Nơron có trong mạng và s c p  trong lớp Layer1. Vì thế ta chọn 1 . . r j n s j   , và vì vậy ta có thể tìm đƣợc một hằng số ** (0,1)c  sao cho 1' ** maxf cji s    (48) Điều này thỏa mãn điều kiện của định lý 1 nên ta có mạng là hội tụ đến một điểm. Kết luận: Quá trình tính toán và chứng minh, ta có đƣợc kết quả sau:  Với Layer1, mạng thoả mãn giả thuyết của định lý 1, nên mạng hội tụ  Với Layer2, mạng thoả mãn giả thuyết của định lý 2, nên mạng hội tụ 4.6. Giải thuật của FBACN và FBACN với việc học Giải thuật của FBACN đƣợc thực hiện qua các bƣớc sau: GIẢI THUẬT CỦA FBACN 1) Thiết lập các giá trị c, m, λ, ε và các hệ số iδv, iδu trong lớp Layer1 và Layer2 tƣơng ứng. 2) Đặt hệ số ổn định v và u cho Layer1 và Layer2 tƣơng ứng. 3) Khởi tạo ngẫu nhiên các trung tâm cụm ( 1). ,i p lv   i=1, 2, ..., c và l = 1, 2.., n trong Layer1 và lớp thành viên ,i k fcu M   với k=1, 2, 76 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ...,n và i = 1, 2, ...,c trong Layer2. 4) Cập nhật các hệ số iv v j   và iu u j   và giá trị mạng ban đầu (0) 0net j  với j =1, 2, ..., s (s=c.p trong Layer1 và s=n.c trong Layer2). 5) Thiết lập chỉ số hồi quy g =1 cho Layer1. 6) Trong Layer1, tính ma trận trọng số W theo công thức (12), ma trận tín hiệu vào bên ngoài I theo công thức (11), và giá trị mạng NET theo công thức (4). 7) For j = 1 to s do if ( ) ( 1). 0g gj jnet net   then : / 2 j j v v  ; 8) For j = 1 to s do if ( ) 0gjnet  then :j j j v v v  else :j j j v v v  9) if (( )&( )&...&( ) 1 2 v v v v v vs         then goto 10) else {g:= g+1; goto 6)}. 10) Đặt chỉ số hồi quy g=1 cho Layer2. 11) Trong Layer2, tính ma trận trọng số W theo công thức (23), ma trận trọng số Z theo công thức (24) và  TI  2,...,2,2 và ma trận IUZNET m   .W.U 1 . 12) For j = 1 to s do if ( ) ( 1) . 0 g g net net j j   then : / 2u u j j   ; 13) For j = 1 to s do if ( ) 0 g net j  then :u u uj j j   77 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên else u : u uj j j   14) if (( )&( )&...&( ) 1 2 u u u u u us         then goto 15) else {g:= g+1; goto 11)}. 15) if ( ) ( 1)g g U U   then Stop else goto 4 Đối với FBACN với việc học thì thuật toán tƣơng tự nhƣ của FBACN, nhƣng từ bƣớc 10 đến bƣớc thứ 14 thì đƣợc thay bằng 10’ đến 17’. Trƣớc hết ta định nghĩa một số tham số: p0 là hằng số tỉ lệ xác suất nằm trong [0,1], sử dụng để tính xác suất. EquiCycle là chu kỳ thăng bằng ấm(có nghĩa là khi vòng lặp đang xử lý cần giữ thăng bằng ấm tại nhiệt độ T). Tstart là nhiệt độ xung quanh, Tstop là nhiệt độ dừng(tức dừng việc học) và Tstep là tổng nhiệt độ thấp hơn trong mỗi vòng lặp. Giải thuật của FBACN với việc học đƣợc thực hiện nhƣ sau: GIẢI THUẬT CỦA FBACN VỚI VIỆC HỌC 1’ -> 9’ = 1 -> 9 của FBACN 10’) Đặt T = Tstart. 11’) Đặt chỉ số hồi quy g = 1 cho Layer2. 12’) Trong Layer2, tính giá trị của ma trận trọng số W theo công thức (23), ma trận trọng số Z theo công thức (24) và ma trận tín hiệu vào từ bên ngoài I và ma trận giá trị mạng NET. 13’) if g EquiCycle then { For j =1 to s do { Tính xác xuất ( ) 0 /1 . g j j j T p p e net u     ; 78 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  ( ) ( 0,1 )gja Rand }} esle { For j =1 to s do { ( ) ( ) 0; 1 g g p a j j  }}; 14’) for j = 1 to s do if ( ) ( 1) ( 1) ( 1) (( . ) 0)&( . 0)) g g g g net net a p j j j j      then : / 2u u j j   15’) for j =1 to s do { if ( ) ( )g g a p j j  then { if Rand([0,1]) 0.5 then :u u uj j j   else :u u uj j j   } else { if ( ) 0 g net j  then :u u uj j j   else :u u uj j j   }} 16’) if 1 2(( )&( )&...&( )su u u u u u        then goto 17’) else {g:= g+1; goto 12’)}. 17’) if T>Tstop then {T:=T-Tstep; goto 11’)} else goto 18’). 18’) if ( ) ( 1)g g U U   then Stop else goto 4) 79 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 5 CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG 5.1. Cài đặt thử nghiệm thuật toán FCM ........................................................................ 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh .......................................... 79 82 Chƣơng này trình bày kết quả xây dựng chƣơng trình thử nghiệm của thuật toán FCM và ứng dụng thuật toán FCM-Cải tiến vào quá trình nhận dạng ảnh. 5.1. Cài đặt thử nghiệm thuật toán FCM FCM là một thuật toán đƣợc áp dụng khá nhiều trong phân cụm dữ liệu vì hiệu năng và tính hiện thực của nó khá tốt. Thuật toán FCM đƣợc bắt đầu bằng cách chọn C cụm và chọn ngẫu nhiên c điểm làm trung tâm cụm hoặc chọn phân hoạch ngẫu nhiên C cụm và tính trọng tâm của từng cụm này. Nếu số lƣợng dữ liệu nhỏ hơn số cụm thì ta gán mỗi dữ liệu là một trọng tâm của cụm, mỗi trọng tâm sẽ có 1 số cụm. Nếu số lƣợng dữ liệu lớn hơn số cụm, với mỗi dữ liệu, ta tính toán độ tƣơng tự có trọng số giữa điểm đó và trọng tâm cụm và lấy khoảng cách tối thiểu. Dữ liệu này thuộc về cụm có khoảng cách tối thiểu tới dữ liệu đó. Khi chúng ta không chắc chắn về vị trí của trọng tâm, ta cần điều chỉnh vị trí trọng tâm dựa vào dữ liệu đã cập nhật hiện tại. Sau đó, ta gán tất cả dữ liệu tới trọng tâm mới này. Quá trình này đƣợc lặp lại cho tới khi không còn dữ liệu di chuyển sang cụm khác. Về mặt toán học, vòng lặp này có thể chứng minh là hội tụ cực tiểu cục bộ. Quá trình cài đặt của thuật toán đƣợc mô phỏng thông qua giao diện của chƣơng trình nhƣ Hình 5.1 và Hình 5.2 dƣới đây:  Ngôn ngữ sử dụng là Visual C++ 6.0  Tham số ban đầu: Số cụm = 3, tham số mũ m = 2  Dữ liệu đầu vào là các điểm màu khác nhau 80 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.1: Giao diện của chƣơng trình khi khởi động Khi ngƣời sử dụng nhập số cụm vào khung “Nhập số cụm”, kích chuột vào khung chƣơng trình để tạo ra các điểm của cụm, vị trí của các điểm đƣợc thể hiện ở khung “Toạ độ xy”. Chƣơng trình sẽ tự động tạo ra các cụm dữ liệu bằng cách tối giản tổng bình phƣơng các khoảng cách giữa dữ liệu và trọng tâm cụm tƣơng ứng khi ta kích chuột vào khung chƣơng trình để tạo ra mỗi điểm. Mỗi điểm và tọa độ của nó biểu thị cho một đối tƣợng với mô tả hai thuộc tính của đối tƣợng đó là màu sắc của điểm và số nhãn biểu thị cho cụm. 81 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Dƣới đây là hình ảnh thu đƣợc khi chạy chƣơng trình với số cụm nhập vào là 8 cụm.. Hình 5.2: Giao diện của chƣơng trình khi làm việc Chƣơng trình tự động phân thành 8 cụm thông qua số màu hiện trong từng cụm và tâm của mỗi cụm. 82 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh Bài toán nhận dạng chính là quá trình phân loại các đối tƣợng đƣợc biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp dựa theo các quy luật và các mẫu chuẩn. Nhận dạng có rất nhiều ứng dụng, đƣợc áp dụng vào rất nhiều lĩnh vực, chẳng hạn nhƣ nhận dạng vân tay, nhận dạng chữ viết, nhận dạng ảnh… Và phân cụm màu là một bƣớc rất quan trọng trong quá trình nhận dạng ảnh. Do số lƣợng điểm ảnh là rất lớn, thƣờng trên 80.000 điểm ảnh và số lƣợng màu của mẫu dữ liệu ảnh là phụ thuộc vào độ sắc nét của ảnh. Nếu ảnh có chất lƣợng càng tốt thì số lƣợng màu càng lớn, nhƣng dù ảnh có chất lƣợng nhƣ thế nào đi nữa thì số lƣợng màu vẫn lớn. Mặt khác, trong nhận dạng ảnh, chúng ta chỉ quan tâm tới một số yếu tố nhất định, chẳng hạn nhƣ mắt, lông mày, miệng và da,... nên số lƣợng màu mà ta quan tâm cũng không lớn lắm, vì vậy áp dụng thuật toán FCM-Cải tiến vào việc phân cụm màu trong nhận dạng ảnh là một ứng dụng rất cần thiết trong bài toán này. Quá trình ứng dụng của thuật toán FCM-Cải tiến đƣợc mô phỏng thông qua giao diện của chƣơng trình với Hình 5.3, Hình 5.4 và Hình 5.5 dƣới đây:  Ngôn ngữ sử dụng là Visual C++ 6.0  Tham số ban đầu: Khai báo mảng lƣu trữ số lƣợng màu của ảnh, mảng lƣu trữ số trung tâm của cụm, số lƣợng cụm, tham số mũ.  Dữ liệu đầu vào là một File ảnh màu(Bitmap)  Dữ liệu đầu ra là một ảnh màu đã đƣợc nhận dạng với số cụm màu đã đƣợc thuật toán FCM-Cải tiến thực hiện phân cụm. 83 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.3: Giao diện của chƣơng trình khi khởi động Khi chƣơng trình khởi động xong, ta chọn một ảnh nguồn để thực hiện bằng cách ấn vào nút “Mở File Ảnh” và chọn một ảnh cần thực hiện nhƣ Hình 5.4 dƣới đây: 84 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.4: Giao diện của chƣơng trình khi chọn ảnh để phân cụm Sau khi chọn xong, ta ấn vào nút “Thực hiện phân cụm”. Chƣơng trình sẽ thực hiện quá trình nhận dạng và phân cụm màu theo thuật toán FCM-Cải tiến và hiển thị kết quả ở khung “Ảnh Đích” nhƣ Hình 5.5 dƣới đây. 85 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.5: Giao diện của chƣơng trình khi thực hiện phân cụm 86 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên KẾT LUẬN Trong quá trình tìm hiểu và hoàn thành luận văn tốt nghiệp với đề tài “Nghiên cứu một số phương pháp phân cụm mờ và ứng dụng”, dù đã đạt đƣợc những kiến thức nhất định, nhƣng em nhận thấy phân cụm dữ liệu trong KPDL nói chung và phân cụm dữ liệu mờ nói riêng là một lĩnh vực nghiên cứu rộng lớn, nhiều triển vọng. Đề tài đã cố gắng tập trung tìm hiểu, nghiên cứu và trình bày đƣợc một số kỹ thuật và thuật toán phân cụm dữ liệu phổ biến, một số kỹ thuật phân cụm mờ và mô hình mạng nơron đa khớp dùng cho phân cụm mờ trong KPDL hiện nay, trình bày một số cải tiến của thuật toán phân cụm mờ(FCM-Cải tiến) dựa trên các phƣơng pháp đã có, cài đặt thử nghiệm thuật toán phân cụm mờ(FCM) với ứng dụng phân cụm các điểm màu và thực hiện cài đặt ứng dụng của thuật toán FCM-Cải tiến đối với việc phân cụm màu trong bài toán nhận dạng ảnh màu. Tuy nhiên, do những hạn chế về tài liệu và thời gian nên em mới chỉ tìm hiểu đƣợc một số kỹ thuật điển hình trong phân cụm và đặc biệt là phân cụm mờ, cài đặt và thử nghiệm một số thuật toán ứng dụng .... nhƣng còn một số kỹ thuật khác vẫn chƣa đƣợc tìm hiểu và khai thác, cài đặt thử nghiệm chƣa áp dụng đƣợc cho bài toán phân cụm tổng quát.... Trong thời gian tới em sẽ tiếp tục nghiện cứu thêm một số kỹ thuật phân cụm và đặc biệt là các thuật toán phân cụm mờ kết hợp song song ứng dụng vào một số bài toán thực tế ở Việt Nam hiện nay và hy vọng sẽ dần đƣa những kiến thức đã có từ đề tài này sớm trở thành thực tế, phục vụ cho cuộc sống con ngƣời chúng ta. Học viên thực hiện An Hồng Sơn 87 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt: 1. Phan Đình Diệu (1999), “Lô Gích trong Các Hệ Tri Thức”, NXB Đại học Quốc gia Hà Nội, Hà Nội. 2. Nguyễn Trọng Thuần, “Điều khiển Logic và ứng dụng”, Nhà xuất bản Khoa học và Kỹ thuật, 2004. 3. Bùi Công Cƣờng và Nguyễn Doãn Phƣớc, “Hệ mờ, mạng nơron và ứng dụng ”, NXB Khoa học và kỹ thuật, 2006. 4. Vũ Thanh Nguyên, “Ứng dụng logic mờ, mạng nơron mờ, hệ các luật mờ phân tích dự báo các mặt hàng chiến lược”, Hội thảo khoa học Hệ mờ, mạng nơron và ứng dụng, lần 1, Hà nội 8-9/11/2006. 5. Ngô Quốc Tạo, “Giáo trình Xử Lý Ảnh”, Lớp CHCLC-ĐH Công Nghệ-ĐHQG Hà Nội 2001-2002. 6. Ngô Quốc Tạo, “Bài giảng môn Data Mining”, Lớp CHK5-ĐH Thái Nguyên 2006-2008. 7. Ngô Quốc Tạo, “Bài giảng môn Xử Lý Ảnh”, Lớp CHK5-ĐH Thái Nguyên 2006-2008. Tài liệu Tiếng Anh: 8. Daniel T. Larose, “Discovering Knowledge in Data: An Introduction toData Mining”, ISBN 0-471-66657-2 CopyrightC 2005 John Wiley & Sons, Inc. 9. A. Arning, R. Agrawal, and P. Raghavan. Alinear method for deviation detection in larger databases, “In Proc. 1996 Int. Conf. Data Mining and Knowledge Discovery (KDD-96)”, Portland, Oregon, August 1996. 88 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10. P.S. Bradley, U. Fayyad, C. Reina, Scaling Clustering Algorithms to Large Databases, “In Proc of 4th International conference on Knowledge Discovery and Dala Mining (Kdd-98)”, New York. 1998. 11. D. Fisher, “Knowledge acquisition via incremental conceptual clustering, In Machine Learning”, 2 pp. 139-/72, 1987. 12. D. Gibson, J. Kleinberg, P. Raghavan, “Clustering Categorical Data: An Approach Based on Dynamical Systems”, VLDB Journal 8 (3-4) pp. 222-236, 2000. 13. J. Han, M. Kamber, “Data Mining Concepts and Techniques”, Morgan Kaufmann Publishers, 2001. 14. A.K. Jain, R.C. Dubes, “Algorithms for clustering data”, Ptentice Hall, Englewood Cliffs, NJ, 1988. 15. R.A. Jarvis, E.A. Patrick, “Clustering using a similarity measure based on shared near neighbors”, IEEE Transactions on Computers C22, pp. 1025-1034, 1973. 16. M. Manago, Y. Kodratoff, “Inđuction of Decision Trees from Complex Structuted Data, In Knowledge Discovery in Databases”, AAAI/Th MIT press, pp. 289-306, 1991. 17. J.C.Bezdek, “Pattern Recognition with fuzzy Objective Function Algorithms”, New York, Plenum, 1981. 18. W.Pedrycz, “Algorithms of fuzzy clustering with partial supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990. 19. M.P.Windham, “Cluster validity for fuzzy clustering algorithms”, “Fuzzy Sets and System”, vol. 3, pp. 177-183, 1981. 20. W.Pedrycz, “Algorithms of fuzzy clustering with partial supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990. 89 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21. G.Bueno, R.Gonzalez, J.Gonzalez, and M.Garcia-Rojo, “Fuzzy colour C-means clustering for pattern segmentation in histological images”, The 3rd European Medical and Biological Engineering Conference, 2005. 22. Chih-Hsiu Wei, Chin - Shyurng Fahn, “The multisynapse neural network and its application to fuzzy clustering”. 23. J.H.Wang and C.Y.Peng, “Optimal clustering using neural network”, in Proc. IEEE Int. Conf. Syst., Man, Cybern., vol.2, 1998, pp.1625-1630. 24. Y.Guo, X.Yin, and W.Gong, “ART2 neural network clustering for hierarchical simulation”, in Proc. SPIE Int. Soc.Opt.Eng., vol. 2.1998, pp.35-48. 25. M.F.Augusteijn and U.J.Steck, “Supervised adaptive clustering: A hybrid neural network clustering algorithm”, neural Comput.Applicat., vol.7,no. 1, pp.78-89, 1998. 26. E. C. Tsao, J. C. Bezdek, and N. R. Pal, “Fuzzy Kohonen clustering network”, Patterm recognition, vol.27, no.5, pp.757-764, 1994. 27. J. Lin, K. Cheng, and C.Mao, “A fuzzy Hopfield neural network for medical image segmentation”, IEEE Trans. Nuclear Sci., vol.43, 1996. 28. Hathaway R.J and Bezdek J.CNTT (2000), “Generalized fuzzy c-means clustering Strategies using LP Norm Distances”, IEEE Trans.Fuzzy Syst, No 5, pp.576-582. 29. J.E.Steck and S.N.Balakrishnan, “Use of Hopfield newral networks in optimal guidance”, IEEE Trans. Aerosp.Electron. Syst., vol.30, no.1, pp 287-293, Jan.1994. ._.