Chương 1 tập trung trình bày tổng quan về PCDL, đây là một hướng tiếp cận trong Data Mining. Trong đó đi sâu phân tích chi tiết các vấn đề cơ bản: khái niệm PCDL và ý nghĩa của nó trong thực tiễn; trình bày một số phương pháp PCDL và giải thuật điển hình của mỗi phương pháp phân cụm. Chương 2: Phân cụm dữ liệu mờ Để làm rõ hơn kỹ thuật PCDL mờ, chương 2 trình bày một số khái niệm cơ bản của lý thuyết tập mờ; phân tích kỹ thuật phân cụm rõ và phân cụm mờ, trình bày hai LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 thuật toán phân cụm mờ điển hình: C-means mờ (viết tắt là FCM) và mở rộng của nó là thuật toán Gustafson-Kessel (viết tắt là GK). Chương 3: Số cụm và chỉ số đánh giá Trong chương 3, luận văn đặc tả vấn đề ước lượng số cụm trong bài toán phân cụm.
Phân tích một số hàm chỉ số thông dụng để đánh giá chất lượng phân hoạch được tạo ra bởi các thuật toán phân cụm mờ, nhờ đó xác định số cụm tối ưu cho tập dữ liệu được xét. Chương 4: Một chỉ số đánh giá số cụm mới cho phân cụm mờ Chương 4, luận văn đề xuất một chỉ số đánh giá số cụm mới nhờ kết hợp độ nén và độ chồng nhau của các cụm. Tiến hành thực nghiệm trên nhiều bộ dữ liệu nhân tạo và bộ dữ liệu thực đã cho thấy ưu điểm nổi trội của chỉ số mới so với các chỉ số điển hình hiện có trong quá trình tìm kiếm số cụm tối ưu cho một tập dữ liệu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 CHƢƠNG I TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.
Phân cụm dữ liệu là gì Một trong những bài toán quan trọng trong lĩnh vực khai phá dữ liệu (data mining) là bài toán phân cụm. Ở một mức cơ bản, ta có thể định nghĩa phân cụm dữ liệu như sau: [13] Phân cụm dữ liệu (PCDL) 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 các phần tử trong cùng một cụm thì “tương tự” nhau và các phần tử trong các cụm khác nhau thì “kém tương tự” nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước hoặc có thể được tự động xác định theo phương pháp phân cụm.1: Mô phỏng vấn đề phân cụm dữ liệu. Trong học máy, PCDL được xem là vấn đề học không có giám sát (unsupervised learning), 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 mà chỉ đơn thuần dựa vào tính tương đồng của các đối tượng dữ liệu.
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ì PCDL là một bước trong phân lớp dữ liệu, nó 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. [2,6,13] Với một tập dữ liệu, quá trình phân cụm có thể cho ra nhiều kết quả khác nhau tùy thuộc vào tiêu chí cụ thể được sử dụng để phân cụm. Các bước cơ bản của quá trình phân cụm được thể hiện trong hình 1.2 và được tóm tắt như sau:[15,19] Lựa chọn đặc trưng (Feature selection): các đặc trưng phải được lựa chọn một cách hợp lý để có thể “mã hóa” nhiều thông tin nhất liên quan đến nhiệm vụ mà chúng ta quan tâm. Mục tiêu chính là giảm thiểu dư thừa thông tin giữa các đặc trưng.
Do đó, tiền xử lý dữ liệu là một nhiệm vụ quan trọng trước khi tiến hành các bước sau. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Lựa chọn thuật toán phân cụm (clustering algorithm selection): cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc của tập dữ liệu. Đánh giá kết quả phân cụm (validation of results): Khi đã có kết quả phân cụm thì ta phải kiểm tra tính đúng đắn của nó. Với cùng một tập dữ liệu, những cách tiếp cận khác nhau thường dẫn tới các kết quả phân cụm khác nhau và ngay cả cùng một thuật toán với các tham số đầu vào khác nhau cũng cho ra các kết quả khác nhau.
Vì vậy, các tiêu chuẩn và tiêu chí để đánh giá kết quả phân cụm là rất quan trọng. Nó cung cấp cho người dùng mức độ tin cậy của các kết quả mà thuật toán phân cụm thực hiện. Giải thích kết quả (interpretation of results): Mục tiêu cuối cùng của việc phân cụm là cung cấp cho người sử dụng những hiểu biết ý nghĩa từ dữ liệu gốc. Các chuyên gia phải giải thích những phân vùng dữ liệu thu được.
Trong nhiều trường hợp, các chuyên gia trong các lĩnh vực ứng dụng phải tích hợp các kết quả phân cụm với các bằng chứng thực nghiệm khác và phân tích để rút ra những kết luận đúng. Giải thích kết quả Đánh giá cụm Thuật toán phân cụm Tri thức Lựa chọn Các cụm đặc trưng cuối cùng Kết quả Dữ liệu cho phân cụm xử lý Dữ liệu thô Hình 1.2: Các bước của quá trình phân cụm dữ liệu. Thế nào là phân cụm tốt Phương pháp phân cụm nhóm các đối tượng có độ tương tự hay độ tương đồng cao vào trong một nhóm và các đối tượng khác nhóm nhau thì kém tương đồng nhau. Sự khác biệt hay tương tự giữa hai đối tượng thường được xác định qua một hàm khoảng cách.
Giá trị của hàm khoảng cách càng nhỏ nghĩa là sự giống nhau giữa hai đối tượng càng lớn và ngược lại. Một phương pháp phân cụm tốt sẽ sinh ra các cụm có chất lượng cao, trong đó: - Mức độ tương tự giữa các đối tượng trong cùng một cụm là cao; - Mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là thấp. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Cực đại hóa khoảng Cực tiểu hóa khoảng cách giữa các cụm cách bên trong cụm Hình 1.3: Tiêu chuẩn phân cụm. Chất lượng của kết quả phân cụm phụ thuộc vào cả độ đo tương tự được sử dụng và cách thức thực hiện.
Chất lượng của phương pháp phân cụm cũng được đánh giá bởi khả năng phát hiện các mẫu tiềm ẩn (hidden patterns). Các yêu cầu của phân cụm trong khai phá dữ liệu:[6,13] 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 PCDL đều nhằm thỏa mãn các yêu cầu cơ bản sau: - Có tính mở rộng ; - Thích nghi với các kiểu dữ liệu khác nhau; - Khám phá ra các cụm với hình dạng bất kỳ; - Tối thiểu lượng tri thức cần cho xác định các tham số vào; - Thích nghi với dữ liệu nhiễu; - Ít nhạy cảm với các tham số đầu vào; - Có khả năng phân cụm với dữ liều có số chiều cao; - Dễ hiểu, cài đặt và khả dụng. Các ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu là một trong những công cụ chính được ứng dụng trong nhiều lĩnh vực.
Một số ứng dụng của phân cụm [2,5,19] như: Xử lý dữ liệu lớn: việc khám phá tri thức trong các cơ sở dữ liệu thường phải xử lý khối lượng dữ liệu rất lớn, nhiều khi ngay cả các thuật toán với độ phức tạp tính toán là đa thức cũng không dùng được. Do đó, việc phân và xử lý theo các cụm là một giải pháp hữu hiệu. Tạo giả thuyết: phân tích cụm được sử dụng để suy ra một số giả thuyết liên quan đến dữ liệu. Ví dụ: dựa trên tuổi tác và thời điểm mua hàng, chúng ta có thể tìm thấy LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 trong một cơ sở dữ liệu bán lẻ có hai nhóm khách hàng quan trọng.
Sau đó, chúng ta có thể suy ra một số giả thuyết cho dữ liệu là: "những người trẻ tuổi đi mua sắm vào buổi tối", "người già đi mua sắm vào buổi sáng". Kiểm định giả thuyết: Trong trường hợp này, phân tích cụm được sử dụng cho việc xác minh tính hợp lệ của một giả thuyết cụ thể. Ví dụ, chúng ta xem xét giả thuyết như sau: "Những người trẻ tuổi đi mua sắm vào buổi tối". Một cách để xác minh điều này là áp dụng phân tích cụm cho một tập đại diện các cửa hàng.
Giả sử rằng mỗi cửa hàng được đặc trưng bởi các chi tiết của khách hàng (tuổi tác, công việc, …) và thời điểm giao dịch. Nếu sau khi áp dụng phân tích cụm, một cụm tương ứng với "những người trẻ mua sắm vào buổi tối" được tạo thành thì giả thuyết ban đầu đã được chứng minh là hợp lệ. Cụ thể, các kỹ thuật phân cụm dữ liệu đã được áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau: Thương mại: Trong thương mại, phân cụm dữ liệu có thể giúp các nhà tiếp thị khám phá ra các nhóm khách hàng quan trọng có cá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: Trong 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 Gen với chức năng tương đồng và thu được những hiểu biết bên trong những cấu trúc của quần thể.
Phân tích dữ liệu không gian: Do một lượng lớn dữ liệu không gian có thể thu được từ các hình ảnh vệ tinh, thiết bị y tế, hệ thống thông tin địa lý (GIS), cơ sở dữ liệu hình ảnh thăm dò,… làm cho người dùng tốn kém và khó khăn để kiểm tra các dữ liệu không gian một cách cụ thể. Phân cụm dữ liệu có thể giúp người dùng tự động phân tích và xử lý các dữ liệu không gian. Nó được sử dụng để nhận dạng, trích xuất các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong cơ sở dữ liệu không gian lớn. Khai phá Web (Web mining): phân cụm dữ liệu 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 hỗ trợ trong việc phát hiện ra thông tin. Trong tìm kiếm tương tự (similar search), nếu trước đó các trang web đã phân cụm, thì khi lọc các kết quả, ta chỉ tập trung vào các trang Web nằm trong cụm có liên quan nhiều đến câu truy vấn. Như vậy, chất lượng của kết quả tìm kiếm sẽ tốt hơn.