CHƯƠNG 1. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1. KHÁM PHÁ TRI THỨC Trong những năm gần đây, sự phát triển mạnh mẽ của ngành CNTT đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng một cách nhanh chóng. Bên cạnh đó, việc tin học hoá nhiều lĩnh vực của cuộc sống đã tạo ra cho chúng ta một kho dữ liệu khổng lồ.
Từ đó, Khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang là một vấn đề thời sự của nền CNTT thế giới hiện nay. Nó được ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu được nhiều thành quả to lớn. Khám phá tri thức trong CSDL là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu được mẫu hoặc mô hình trong dữ liệu. Quá trình khám phá tri thức có thể bao gồm một số bước như hình 1.
[7][10] Problem Identification and Definition Obtaining and Preprocessing Data Data Mining Extracting Knowledge Results Interpretation and Evaluation Using Discovered Knowledge Hình 1. Quá trình Khám phá tri thức Ø Tìm hiểu lĩnh vực ứng dụng và định nghĩa vấn đề: Là bước quan trọng để rút ra những tri thức hữu ích và chọn phương pháp KPDL phù hợp với mục đích ứng dụng và bản chất dữ liệu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Ø Thu thập và tiền xử lý dữ liệu: Bao gồm lựa chọn dữ liệu nguồn, loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị thiếu, biến đổi và rút gọn dữ liệu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. Bước này thường tốn thời gian trong quá trình KPTT.
Ø Khai phá dữ liệu: Trích chọn các mẫu ẩn hoặc mô hình trong dữ liệu. Một mô hình có thể xem như là một biểu diễn tổng thể của cấu trúc nhằm tóm lược các thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả dữ liệu phát sinh. Ngược lại, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trường hợp. Ø Biểu diễn và đánh giá tri thức: Đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế.
Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện được từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, quy trình KPTT được lặp đi lặp lại có điều chỉnh theo các tri thức phát hiện được. Để đánh giá được các luật áp dụng trong quy trình KPTT, dữ liệu thường được chia thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này với một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ước lượng các luật thi hành. Ø Ứng dụng tri thức được khám phá: Củng cố các tri thức đã khám phá, kết hợp các tri thức thành một hệ thống máy tính.
Giải quyết các xung đột tiềm năng trong tri thức khai thác được. Đưa kết quả vào thực tiễn là mục đích cuối cùng của KPTT. Hiện nay, có nhiều quan niệm về cách phân chia các giai đoạn của quá trình KPTT. Nhưng hầu hết các quan niệm đều cho rằng KPDL là một giai đoạn quan trọng nhất của qúa trình KPTT.
Bản chất của quá trình KPTT là rút LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 ra được tri thức phù hợp từ CSDL. Một cách phân chia khác về các giai đoạn của quá trình KPTT như hình 1. Cách phân chia khác của quá trình KPTT. KHAI PHÁ DỮ LIỆU Hiện nay, có một số nhà khoa học cho rằng hai thuật ngữ KPTT (Khám phá tri thức) và KPDL (Khai phá dữ liệu) là tương đương và có thể thay thế cho nhau.
Họ lý giải rằng, mục đích của quá trình khám phá tri thức là thông tin và tri thức có ích, nhưng mà đối tượng mà chúng ta phải xử lý nhiều trong suốt qúa trình đó lại chính là dữ liệu. Mặt khác, khi chia các bước của quá trình KPTT thì KPDL chỉ là một bước trong quá trình KPTT. Như vậy, khi xét ở mức không thật chi tiết thì hai thuật ngữ này là tương đương, còn khi xét ở mức chi tiết thì KPDL chỉ là một bước trong quá trình KPTT. Khai phá dữ liệu (Data mining) được định nghĩa là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong các CSDL, kho dữ liệu…Đây là một bước tốn nhiều thời gian nhất trong quá trình KPTT và bước này thường hay đề cập đến các vấn đề về kỹ thuật (thuật toán) được áp dụng [7][10].
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học khác như: Hệ CSDL, thống kê, học máy, trực quan hoá…Tuỳ vào cách tiếp cận được sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác như mạng nơ ron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức…So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt. So với phương pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó, phương pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không quá lớn. Phương pháp hệ chuyên gia, các ví dụ của chuyên gia thường phải đòi hỏi chất lượng cao hơn nhiều so với dữ liệu trong CSDL.
Phương pháp thống kê là một trong những nền tảng lý thuyết của khai phá dữ liệu nhưng khai phá dữ liệu đã khác phục được một số tồn tại của phương pháp thống kê như: - Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều kiểu CSDL. - Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức sẵn có của lĩnh vực. - Kết quả phân tích của thống kê rất nhiều và khó có thể làm rõ được. - Phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu.
Với những ưu điểm đó, khai phá dữ liệu đang được áp dụng vào nhiều lĩnh vực như tài chính, ngân hàng, bảo hiểm, y tế, an ninh, internet…Các công ty phần mềm lớn trên thế giới cũng đã rất quan tâm chú trọng việc nghiên cứu và phát triển các kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đi tiên phong phát triển khai phá dữ liệu với các ứng dụng như Intelligence Miner,…[5][7] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 Các kỹ thuật khai phá dữ liệu Các kỹ thuật khai phá dữ liệu thường chia thành hai nhóm chính [3]: o Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các kỹ thuật loại này gồm có: Phân cụm (Clustering), tóm tắt (Summerization), trực quan hoá (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation anlyst), phân tích luật kết hợp (Association rules),… o Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện tại. Các kỹ thuật loại này gồm có: Phân lớp (Classification), hồi quy (Regression),… Trong khuôn khổ có hạn của luận văn này, tôi tập trung trình bày về một trong những phương pháp thông dụng nhất thuộc kỹ thuật khai phá dữ liệu mô tả là “Phân cụm dữ liệu”. Các kỹ thuật khai phá dữ liệu LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
PHÂN CỤM DỮ LIỆU 1. Học có giám sát và học không có giám sát Học có giám sát (supervised learning) là một kĩ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào (gọi là phân loại).
Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm cho một đối tượng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa là các cặp đầu vào và đầu ra tương ứng). Để đạt được điều này, chương trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán được những tình huống chưa gặp phải theo một cách "hợp lí". Học không có giám sát (unsupervised learning) là một phương pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tương ứng cho mỗi đầu vào là không biết trước.
Trong học không có giám sát, một tập dữ liệu đầu vào được thu thập. Học không có giám sát thường đối xử với các đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đó [4]. Khái niệm về phân cụm Phân cụm dữ liệu (PCDL) là kỹ thuật sử dụng quan sát đối tượng để nhóm các đối tượng thành các cụm hoặc chia một tập dữ liệu ban đầu thành các cụm sao cho: Các đối tượng trong cùng một cụm là giống nhau hoặc gần giống nhau được xác định bằng độ tương tự.
Hay nói một cách khác, các đối tượng trong cùng một cụm là tương tự với nhau. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 Các đối tượng thuộc các cụm khác nhau sẽ không tương tự (phi tương tự) với nhau. Vậy có thể hiểu một cách đơn giản là “Phân cụm là qúa trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm là tương tự với nhau”. Quy trình này được thể hiện như hình 1.
Quy trình phân cụm Phân cụm tối ưu thuộc lớp bài toán NP-Hard, số cách để phân chia n đối tượng thành k cụm được tính theo công thức: Số các cụm được xác định tuỳ thuộc vào phương pháp phân cụm. Các thuật toán phân cụm tìm các nhóm chứa đối tượng tương tự nhau. Hai hay nhiều đối tượng được xếp vào cùng một cụm nếu chúng có chung một định nghĩa về khái niêm hoặc chúng xấp xỉ với các khái niệm được mô tả trước.