Tài liệu Phân cụm dữ liệu trừ mờ và ứng dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG TRẦN THỊ YẾN PHÂN CỤM DỮ LIỆU TRỪ MỜ VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS LÊ BÁ DŨNG Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS.TS Lê Bá Dũng, ngƣời đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình làm luận văn. Em cũng xin đƣợc bày tỏ lòng biết ơn tới các thầy đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể lớp nói chung và cá nhân em nói riêng. Tôi xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ, động viên và giúp đỡ để tôi có thể hoàn thành tốt luận văn. Tôi cũng xin gửi lời cảm ơn tới Ban giám hiệu trƣờng Đại học Khoa học, Ban chủ nhiệm Khoa Toán-Tin đã tạo điều kiện thuận lợi cho tôi tham gia khóa học và hoàn thành luận văn. Một lần nữa, xin chân thành cảm ơn. Thái Nguyên, tháng 09 năm 2012 Học viên Trần Thị Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan luận văn là kết quả của sự tìm hiểu, nghiên cứu các tài liệu một cách nghiêm túc dƣới sự hƣớng dẫn của PGS. TS Lê Bá Dũng. Nội dung luận văn đƣợc phát triển từ ý tƣởng, sự sáng tạo của bản thân và kết quả có đƣợc hoàn toàn trung thực. Học viên Trần Thị Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC LỜI CẢM ƠN ............................................................................................................. i LỜI CAM ĐOAN ..................................................................................................... iii MỤC LỤC ................................................................................................................. iv DANH MỤC CÁC TỪ VIẾT TẮT .......................................................................... vi DANH MỤC CÁC BẢNG BIỂU, HÌNH ẢNH ...................................................... vii MỞ ĐẦU .....................................................................................................................1 Chƣơng 1. ....................................................................................................................2 TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU................................................................2 1.1. Khái niệm và mục tiêu của phân cụm dữ liệu ............................................................. 2 1.2. Các ứng dụng của phân cụm dữ liệu ........................................................................... 4 1.3. Các yêu cầu của phân cụm dữ liệu.............................................................................. 4 1.4. Các kỹ thuật tiếp cận và một số thuật toán cơ bản trong phân cụm dữ liệu ............... 6 1.4.1. Các phương pháp phân cụm phân hoạch - Partitioning Methods....................... 6 1.4.2. Phương pháp phân cụm phân cấp - Hierarchical Methods ................................ 9 1.4.3. Phương pháp phân cụm dựa trên mật độ - Density-Based Methods ................. 12 1.4.4. Phương pháp phân cụm dựa trên lưới - Grid-Based Methods ......................... 14 1.4.5. Phương pháp phân cụm dựa trên mô hình - Model-Based Clustering Methods15 1.4.6 Phương pháp phân cụm có dữ liệu ràng buộc .................................................... 17 Chƣơng 2. ..................................................................................................................19 PHƢƠNG PHÁP PHÂN CỤM TRỪ MỜ ................................................................19 2.1. Phân cụm mờ và thuật toán phân cụm mờ ................................................................ 19 2.1.1. Tổng quan về phân cụm mờ ............................................................................... 19 2.1.2. Thuật toán phân cụm C-Means mờ (FCM)........................................................ 21 2.2. Thuật toán phân cụm trừ (SC - Subtractive Clustering) ........................................... 25 2.3. Thuật toán phân cụm trừ mờ (FSC – Fuzzy Subtractive Clustering) ....................... 28 Chƣơng 3 ...................................................................................................................31 ỨNG DỤNG PHƢƠNG PHÁP PHÂN CỤM TRỪ MỜ .........................................31 3.1. Ứng dụng thuật toán SC cho xây dựng hệ luật ......................................................... 31 3.1.1 Trích xuất luật với tính toán xấp xỉ hàm ............................................................. 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3.1.2 Hệ thống suy diễn mờ (FIS) cho bài toán nút giao thông vùng ngoại ô ............. 33 3.2 Ứng dụng thuật toán FSC vào phân đoạn ảnh ........................................................... 37 3.2.1 Phân đoạn ảnh .................................................................................................... 37 3.2.2. Phân đoạn ảnh sử dụng thuật toán phân cụm trừ mờ FSC ............................... 39 3.2.3 Thử nghiệm với thuật toán phân cụm trừ ........................................................... 40 3.2.4 Thử nghiệm với thuật toán phân cụm trừ mờ ..................................................... 42 3.2.5 Thử nghiệm thuật toán phân SC và FSC trên cùng một ảnh .............................. 43 PHỤ LỤC ..................................................................................................................46 KẾT LUẬN ...............................................................................................................49 DANH MỤC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ....................................50 TÀI LIỆU THAM KHẢO .........................................................................................51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn DANH MỤC CÁC TỪ VIẾT TẮT CURE Clustering Using Representatives DBSCAN Density based Spatial Clutering of Application with Noise DENCLUE Clustering Based on Density Distribution Functions EM Expectation Maximization FCM Fuzzy C-Means FSC Fuzzy Subtractive Clustering OPTICS Ordering Points to Identify the Clustering Structure SC Subtractive Clustering Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn DANH MỤC CÁC BẢNG BIỂU, HÌNH ẢNH Hình 2.1: Hai nhóm dữ liệu của phân cụm trừ mờ Hình 3.1: Biểu đồ dữ liệu vào và dữ liệu ra Hình 3.2: Kết quả sau khi phân cụm Hình 3.3: Hàm thành viên tƣơng ứng với biến vào số ô tô sở hữu Hình 3.4: Hàm thành viên tƣơng ứng với biến vào số lƣợng việc làm Hình 3.5: Hàm thành viên tƣơng ứng với biến vào thu nhập trung bình Hình 3.6: Ảnh ban đầu của thuật toán phân cụm trừ Hình 3.7: Ảnh kết quả của thuật toán phân cụm trừ Hình 3.8: Ảnh ban đầu của thuật toán phân cụm trừ mờ Hình 3.9: Ảnh kết quả của thuật toán phân cụm trừ mờ Hình 3.10: Ảnh đầu vào cho cả 2 thuật toán Hình 3.11: Ảnh kết quả của thuật toán SC với 122 cụm Hình 3.12: Ảnh kết quả của thuật toán FSC với 18 cụm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỞ ĐẦU Ngày nay, khai phá dữ liệu (Datamining) đã trở thành một trong những xu hƣớng nghiên cứu phổ biến trong lĩnh vực học máy và công nghệ tri thức. Nhiều thành tựu nghiên cứu của Datamining đã đƣợc áp dụng trong thực tế. Datamining có nhiều hƣớng quan trọng và một trong các hƣớng đó là phân cụm dữ liệu (Data Clustering). Phân cụm dữ liệu 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. Phân cụm dữ liệu là một phƣơng pháp học không giám sát. Hiện nay, các phƣơng pháp phân cụm đã và đang đƣợc phát triển và áp dụng nhiều trong các lĩnh vực khác nhau, bao gồm: nhận dạng, phân tích dữ liệu, nghiên cứu thị trƣờng, xử lý ảnh,… Các thuật toán phân cụm cũng rất đa dạng nhƣ Kmeans, Pam, C-means, C-means mờ, thuật toán phân cụm trừ,… Để tăng tính ổn định và chính xác của kết quả phân cụm, ngày càng có các tiếp cận mới. Một trong những cách tiếp cận đang đƣợc nghiên cứu đó là ứng dụng lý thuyết mờ vào bài toán phân cụm dữ liệu. Luận văn này trình bày phân cụm dữ liệu, một cách tiếp cận mới về phân cụm dữ liệu là thuật toán phân cụm trừ mờ và ứng dụng vào bài toán cụ thể. Luận văn bao gồm các nội dung chính sau: Chương 1: Tổng quan về phân cụm dữ liệu Chương 2: Phƣơng pháp phân cụm trừ mờ Chương 3: Ứng dụng phƣơng pháp phân cụm trừ mờ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chƣơng 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.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à một kỹ thuật trong khai phá dữ liệu, là quá trình phân chia một tập dữ liệu ban đầu thành các cụm sao cho các phần tử trong một cụm “tƣơng tự” với nhau và các phần tử trong các cụm khác nhau sẽ “phi tƣơng tự” 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 theo phƣơng pháp phân cụm. Trong học máy, phân cụm dữ liệu đƣợc xem là vấn đề học không có giám sát, vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chƣa biết trƣớc các thông tin về cụm hay các thông tin về tập huấn luyện. Trong nhiều trƣờng hợp, nếu phân lớp đƣợc xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, phân cụm dữ liệu sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu. 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 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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 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 cơ sở dữ liệu, 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. Tóm lại, phân cụm dữ liệu cần phải giải quyết các vần đề cơ bản nhƣ sau: - Biểu diễn dữ liệu, - Xây dựng hàm tính độ tƣợng tự, - Xây dựng các tiêu chuẩn phân cụm, - Xây dựng mô hình cho cấu trúc cụm dữ liệu, - Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo, - Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. Theo các nghiên cứu cho thấy thì hiện nay chƣa có một phƣơng pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. 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 dữ liệu, 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 khai phá dữ liệu. Mục tiêu của phân cụm là xác định đƣợc bản chất của các cụm dữ liệu trong tập dữ liệu chƣa có nhãn, theo đó cho phép đi sâu vào phân tích và nghiên cứu cho từng cụm dữ liệu này nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. Tuy nhiên, không có tiêu chí nào đƣợc xem là tốt Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nhất để đánh giá hiệu quả của phân cụm, điều này phụ thuộc vào mục đích của phân cụm, và đòi hỏi ngƣời sử dụng phải cung cấp tiêu chí này. 1.2. Các ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu đƣợc ứng dụng trong nhiều lĩnh vực nhƣ: - Thương mại: Phân cụm dữ liệu có thể giúp các thƣơng nhân tìm ra các nhóm khách hàng quan trọng có đặc trƣng tƣơng đồng nhau và đặc tả họ từ các mẫu mua bán trong cơ sở dữ liệu khách hàng. - Sinh học: Phân cụm dữ liệu đƣợc sử dụng để xác định các loại sinh vật, phân loại các gen với chức năng tƣơng đồng và thu đƣợc các cấu trúc trong các mẫu. - 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. - 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. - Khai phá web: 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 khai phá tri thức từ dữ liệu web,… 1.3. Các yêu cầu của phân cụm dữ liệu Việc xây dựng và lựa chọn một thuật toán phân cụm là bƣớc then chốt cho việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ƣu tiên giữa chất lƣợng của các cụm hay tốc độ thực hiện thuật toán,... Hầu hết các nghiên cứu và phát triển thuật toán phân cụm dữ liệu đều nhằm thỏa mãn các yêu cầu cơ bản sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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 cơ sở dữ liệu lớn có thể chứa tới hàng triệu đối tƣợng. Việc phân cụm trên một tập dữ liệu lớn có thể làm ảnh hƣởng tới kết quả. Vậy các thuật toán phân cụm dữ liệu có khả năng mở rộng cao là cần thiết. Khả năng thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau nhƣ dữ liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục,... và thích nghi với kiểu dữ liệu hỗn hợp. Khám phá các cụm với hình dạng bất kỳ: Do hầu hết các cơ sở dữ liệu có chứa nhiều cụm dữ liệu với các hình thù khác nhau nhƣ: hình lõm, hình cầu, hình que,... Vì vậy, để khám phá đƣợc các cụm có tính tự nhiên thì các thuật toán phân cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ. Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Do các giá trị đầu vào thƣờng ảnh hƣởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các cơ sở dữ liệu lớn. Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu, khi đƣa vào xử lý cho thuật toán phân cụm dữ liệu với các thứ tự vào của các đối tƣợng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hƣởng lớn đến kết quả phân cụm. Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm trong khai phá dữ liệu đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác. Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất lƣợng phân cụm thấp do nhạy cảm với nhiễu. Ít nhạy cảm với thứ tự của các tham số đầu vào: Nghĩa là giá trị của các tham số đầu vào khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm. Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau. Dễ hiểu dễ cài đặt và khả thi: 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt đƣợc mục tiêu rất quan trọng có thể gây ảnh hƣởng tới sự lựa chọn các phƣơng pháp phân cụm. Với những yêu cầu đáng chú ý này, ta tìm hiểu về phân cụm diễn ra nhƣ sau: Thứ nhất, tìm hiể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, đƣa ra một cách phân loại chúng trong các phƣơng pháp phân cụm. Sau đó, 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, các phƣơng pháp phân cấp, các phƣơng pháp dựa trên mật độ, các phƣơng pháp dựa trên lƣới và các phƣơng pháp dựa trên mô hình. 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. 1.4. Các kỹ thuật tiếp cận và một số thuật toán cơ bản trong phân cụm dữ liệu Có nhiều thuật toán phân cụm, nhƣng để đƣa ra một sự phân loại rõ nét của các phƣơng pháp phân cụm là khó khăn bởi vì các loại này có thể chồng chéo lên nhau, do đó một phƣơng pháp có thể có những đặc tính của một số thuật toán khác nhau. Các phƣơng pháp phân cụm chính có thể đƣợc phân loại nhƣ sau: 1.4.1. Các phương pháp phân cụm phân hoạch - Partitioning Methods Với một tập dữ liệu gồm n phần tử và k (k  n) là số cụm đƣợc tạo thành. Một thuật toán phân hoạch tổ chức các phần tử dữ liệu vào k phân vùng, mỗi phân vùng thể hiện một cụm dữ liệu và thỏa mãn: mỗi cụm phải chứa ít nhất một phần tử dữ liệu và mỗi phần tử dữ liệu chỉ thuộc vào một cụm. Để đƣa ra đƣợc k phân mảnh, một phƣơng pháp phân mảnh tạo ra một phân mảnh khởi tạo, sau đó sử dụng kỹ thuật lặp để cải thiện phân mảnh bằng cách di chuyển các phần tử dữ liệu từ cụm này sang cụm khác. Tiêu chuẩn tổng quát của quá trình phân mảnh tốt là các phần tử thuộc cùng một cụm thì “gần gũi” hoặc có liên quan đến nhau, các phần tử khác cụm thì “xa nhau” hoặc rất khác nhau. Có nhiều tiêu chuẩn khác nhau để đánh giá chất lƣợng của các phân mảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Để đạt đƣợc tối ƣu toàn cục trong phân cụm dựa trên phân hoạch yêu cầu phải liệt kê đầy đủ tất cả các phân mảnh có thể có. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong các phƣơng pháp heuristic phổ biến, nhƣ thuật toán K-means mỗi cụm đƣợc đại diện bởi giá trị trung bình của các phần tử trong cụm, thuật toán K-medoids mỗi cụm đƣợc đại diện bởi một phần tử nằm gần tâm cụm. Các phƣơng pháp phân cụm heuristic hiệu quả với các cụm hình cầu với tập dữ liệu vừa và nhỏ. Để tìm ra các cụm có hình dạng phức tạp và tập dữ liệu lớn thì các phƣơng pháp này cần đƣợc mở rộng. Các phƣơng pháp phân cụm dựa trên phân hoạch đƣợc biết tới nhƣ K-means, K-medoids, PAM, CLARA, CLARANS,... Trong đó, K-means và K-medoids đƣợc dùng phổ biến hơn cả. Thuật toán K-means sử dụng khoảng cách giữa các phần tử dữ liệu tới các tâm cụm để phân cụm. Trong thuật toán này, chúng ta phải chọn một giá trị k là số cụm mong muốn, và chọn ngẫu nhiên k phần tử dữ liệu làm k tâm cụm ban đầu. Sau đó tính khoảng cách từ các phần tử dữ liệu đến k tâm cụm. Kết nạp các phần tử dữ liệu vào cụm có tâm cụm gần nhất. Xác định tâm cụm mới cho các cụm, với tâm cụm mới là giá trị trung bình của các phần tử trong cụm. Quá trình này lặp lại cho đến khi các cụm không thay đổi. Thuật toán này thích hợp với các cụm dữ liệu có dạng hình cầu. Nhƣợc điểm của nó là phải xác định trƣớc số lƣợng cụm, khó xử lý đƣợc nhiễu và phần tử ngoại lai. Thuật toán K-medoids có thể khắc phục đƣợc nhiễu hoặc phần tử ngoại lai bằng cách chọn phần tử gần tâm cụm nhất làm đại diện cho cụm, gọi là phần tử medoid. Với k là số lƣợng cụm mong muốn, chọn k phần tử bất kỳ làm các medoid ban đầu. Gán mỗi phần tử còn lại vào cụm có medoid gần nhất. Thay thế các medoid hiện tại bằng các medoid mới sao cho chất lƣợng phân cụm đƣợc cải thiện. Chất lƣợng phân cụm đƣợc đánh giá bởi hàm tính độ phi tƣơng tự giữa một phần tử vào medoid của cụm chứa nó. Quá trình này lặp lại cho đến khi hội tụ. Thuật toán K-medoids hiệu quả hơn K-means khi xử lý nhiễu hoặc phần tử ngoại lai, nhƣng độ phức tạp tính toán lại lớn hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn * Thuật toán K-means: Thuật toán phân cụm K-means do MacQueen đề xuất năm 1967, là thuật toán phân cụm trong đó các cụm đƣợc định nghĩa bởi trọng tâm của các phần tử. Phƣơng pháp này dựa trê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à có tâm cụm gần nhất, và tính toán tại tâm của mỗi cụm trên cơ sở các đối tƣợng thuộc cụm. Quá trình lặp này dừng khi các tâm hội tụ. Trong thuật toán K-means, chọn một giá trị k là số cụm cần xác định và sau đó chọn ngẫu nhiên k đối tƣợng làm tâm cụm khởi tạo. Tính toán khoảng cách giữa đối tƣợng dữ liệu và mỗi tâm cụm để tìm kiếm phần tử nào là tƣơng tự (khoảng cách gần nhất) và thêm vào cụm đó. Tính lại tâm cụm cho mỗi cụm (giá trị trung bình của các đối tƣợng dữ liệu trong cụm) và lặp lại quá trình cho đến khi mỗi các đối tƣợng dữ liệu là một bộ phận của cụm nào đó và không đổi. 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 ban đầu chứa n đối tƣợng trong không gian d chiều Xi ={Xi1, Xi2 ,…, k Xin }, i = 1, n , sao cho hàm tiêu chuẩn: E   i 1 xCi D 2 ( x  mi ) đạ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. Trọng tâm của một cụm là một vectơ, trong đó giá trị của mỗi phần tử của nó là trung bình cộng của các thành phần tƣơng ứng của các đối tƣợng vectơ dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật toán là các trọng tâm của cụm dữ liệu. Độ đo khoảng cách D giữa các đối tƣợng dữ liệu thƣờng đƣợc sử dụng là khoảng cách Euclide vì đây là mô hình khoảng cách mà dễ lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể đƣợc xác định cụ thể hơn tùy vào ứng dụng hoặc quan điểm của ngƣời dùng. Thuật toán K-means đƣợc trình bày nhƣ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Input: Tập dữ liệu S và số cụm mong muốn k. Output: Tập các cụm Ci (1 ≤ i ≤ k) và hàm tiêu chẩn E đạt giá trị tối thiểu. Các bước thực hiện: Bƣớc 1: Khởi tạo Chọn k trọng tâm {mj} (1 ≤ j ≤ k) 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ƣớc 2: Tính toán khoảng cách Đối với một đ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 tƣợng 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. Bƣớc 4: Điều kiện dừng Lặp các bƣớc 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi. 1.4.2. Phương pháp phân cụm phân cấp - Hierarchical Methods Một phƣơng pháp phân cụm phân cấp hoạt động bằng cách nhóm các đối tƣợng dữ liệu vào một cây của các cụm. Phƣơng pháp phân cụm phân cấp có thể đƣợc phân loại là hợp nhất hoặc chia tách, tùy thuộc vào việc phân ly có thứ bậc đƣợc hình thành dựa trên kiểu bottom-up (hòa trộn) hay top-down (phân chia). Hiệu quả của một phƣơng pháp phân cụm phân cấp thuần túy bỏ qua sự không có khả năng để điều chỉnh một lần một quyết định hợp nhất hoặc chia tách đã đƣợc thực hiện. Nghĩa là, nếu một quyết định hợp nhất hoặc chia tách cụ thể đã đƣợc thực hiện, sau đó đẫn tới một lựa chọn kém thì phƣơng pháp này không thể quay trở lại và chỉnh sửa nó. Các nghiên cứu gần đây đã nhấn mạnh sự tích hợp của sự hợp nhất phân cấp với các phƣơng pháp lặp di dời. Có hai loại phƣơng pháp phân cụm phân cấp: Phân cụm phân cấp hợp nhất: Đây là chiến lƣợc từ dƣới lên bắt đầu bằng cách đặt mỗi đối tƣợng trong một cụm riêng của mình, sau đó sát nhập các cụm nguyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tử thành các cụm lớn hơn và lớn hơn, cho đến khi tất cả các đối tƣợng trong một cụm duy nhất hoặc cho đến khi các điều kiện kết thúc phân cụm đƣợc thỏa mãn. Hầu hết các phƣơng pháp phân cụm phân cấp thuộc loại này. Chúng chỉ khác nhau trong định nghĩa về sự tƣơng tự của các phần tử trong cụm. Phân cụm phân cấp chia tách: Đây là chiến lƣợc từ trên xuống, đảo ngƣợc của phân cụm phân cấp hợp nhất bằng cách bắt đầu với tất cả các đối tƣợng trong một cụm. Sau đó chia nhỏ cụm thành từng phần nhỏ hơn và nhỏ hơn, cho đến khi mỗi đối tƣợng hình thành một cụm riêng của mình hoặc cho đến khi các điều kiện thúc đƣợc thỏa mãn, chẳng hạn nhƣ một số mong muốn về các cụm đạt đƣợc, hoặc đƣờng kính của mỗi cụm trong một ngƣỡng nhất định. Một số thuật toán phân cụm phân cấp: Thuật toán CURE (Clustering Using REpresentatives) là thuật toán sử dụng chiến lƣợc bottom-up, Thuật toán BIRCH, Thuật toán AGNES, Thuật toán DIANA, Thuật toán ROCK, Thuật toán CHAMELEON. * Thuật toán CURE: Thuật toán CURE (Clustering Using REpresentatives) là thuật toán sử dụng chiến lƣợc Bottom up của kỹ thuật phân cụm phân cấp. 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 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 bởi trƣớc hết 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 hoà 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 hình cầu. Việc co lại các cụm có tác dụng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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 các 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 cơ sở dữ liệu lớn mà không làm giảm chất lƣợng phân cụm. Để xử lý đƣợc các cơ sở dữ liệu lớ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 trên mỗi phân hoạch là từng phần đã đƣợc phân cụm, quá trình này lặp lại cho đến khi ta thu đƣợc phân hoạch đủ tốt. 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. CURE là thuật toán tin cậy trong việc khám phá ra các cụm với hình dạng 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ệ của các phần tử đại diện. Thuật toán CURE đƣợc thực hiện qua các bƣớc cơ bản nhƣ 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 phân cụm dữ liệu cho các nhóm cho đến khi đƣợ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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - Đánh dấu dữ liệu với các nhãn tƣơng ứng. 1.4.3. Phương pháp phân cụm dựa trên mật độ - Density-Based Methods Để khám phá ra các cụm với hình dạng tùy ý, phƣơng pháp phân cụm dựa trên mật độ đã đƣợc phát triển. Những cụm đặc trƣng này nhƣ các vùng dày đặc của các đối tƣợng trong không gian dữ liệu đƣợc phân cách bởi các vùng mật độ thấp (đại diện cho nhiễu). Các thuật toán phân cụm dựa trên mật độ: - DBSCAN (Density based Spatial Clutering of Application with Noise) thực hiện chia các cụm sao cho mật độ của các đối tƣợng dữ liệu trong từng cụm lớn hơn một ngƣỡng đặt ra. - OPTICS (Ordering Points to Identify the Clustering Structure) mở rộng thuật toán DBSCAN, đƣa ra một trật tự cụm thu đƣợc từ một vùng rộng các thiết lập tham số. - DENCLUE (Clustering Based on Density Distribution Functions) là phƣơng pháp phân cụm dựa trên một tập hợp các hàm phân bố mật độ. * Thuật toán DBSCAN: DBSCAN (Density based Spatial Clutering of Application with Noise) phân cụm dựa trên sự quan sát thực tế thấy rằng, mật độ của những điểm trong cùng một cụm thì lớn hơn rất nhiều so với mật độ của những điểm không thuộc cụm đó. Từ quan sát đó, DBSCAN thực hiện chia các cụm sao cho mật độ của các đối tƣợng dữ liệu trong từng cụm lớn hơn một ngƣỡng đặt ra. Thuật toán DBSCAN yêu cầu hai tham số là Eps và minpts từ ngƣời dùng. Tham số Eps xác định tập các đối tƣợng lân cận của một đối tƣợng dữ liệu. Minpts là tham số ngƣỡng mật độ của các đối tƣợng dữ liệu. Một số khái niệm sử dụng trong DBSCAN: - Lân cận với ngƣỡng Eps của một điểm: Lân cận với ngƣỡng Eps của một điểm p ký hiệu NEps(p) đƣợc xác định nhƣ sau: NEps (p) = {q  D | dis(p, q)  Eps} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - Một điểm dữ liệu p đƣợc gọi là điểm nhân (core - point) nếu miền lân cận của p với bán kính Eps có ít nhất là minpts điểm. - q đƣợc gọi là đến đƣợc theo mật độ trực tiếp (directly density reachble) nếu p là điểm nhân và q  Neighbor(p, Eps). - q đƣợc gọi là đến đƣợc theo mật độ (density reachble) từ p nếu có một dãy p = p0, p1,…, pn = q với pi là đến đƣợc theo mật độ trực tiếp từ pi+1. - Một điểm p gọi là nối mật độ với q nếu có một điểm 0 mà cả p và q đều là đến đƣợc theo mật độ từ 0. - Một tập con C khác rỗng của D đƣợc gọi là một cụm theo Eps và minpts nếu thoả mãn hai điều kiện: p, q  D, nếu p  C và q có thể đến đƣợc từ p theo Eps và Minpts thì q  C. p, q  C, p liên thông theo mật độ với q theo Eps và Minpts. - Dữ liệu nhiễu (noise): Một điểm dữ liệu nếu không phụ thuộc vào cụm nào thì gọi là nhiễu: nhiễu = {p | i = 1…k, p  ci}. Để tìm ra các cụm, DBSCAN lần lƣợt duyệt lại mọi đối tƣợng thuộc cơ sở dữ liệu và mở rộng đến tất cả những điểm có cùng mật độ có thể đi đến đƣợc từ p với hai tham số Eps và minpts. Nếu đối tƣợng dữ liệu p là đối tƣợng dữ liệu nhân thì tập các điểm đến đƣợc mật độ từ p sẽ tạo ra một cụm. Trong trƣờng hợp ngƣợc lại, duyệt đến đối tƣợng dữ liệu kế tiếp trong cơ sở dữ liệu cho đến khi tất cả các đối tƣợng dữ liệu đã đƣợc duyệt qua. Eps và Minpts đƣợc xác định trƣớc bởi ngƣời dùng. Minpts thƣờng đƣợc đặt bằng 2n với n là số đối tƣợng trong không gian dữ liệu. Eps đƣợc xác định bởi ngƣời sử dụng trong từng ứng dụng cụ thể. Việc lựa chọn giá trị Eps có thể đƣợc hỗ trợ bởi đồ thị 2n – dist (đồ thị biểu diễn hàm ánh xạ mỗi một điểm p đến khoảng cách của điểm lân cận thứ 2n của điểm p) DBSCAN đƣợc thiết kế để xử lý với dữ liệu có nhiễu và hiệu quả trong việc loại trừ ngoại lai. Mặc dù DBSCAN có thể tìm ra đƣợc cụm với hình thù bất kỳ nhƣng DBSCAN không thể xác định đƣợc cụm với hình dạng lồng nhau. Một điểm yếu của DBSCAN là DBSCAN yêu cầu hai tham biến từ ngƣời sử dụng là Eps và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn