Chương 1: Trình bày tổng quan về khám phá tri thức và khai phá dữ liệu: các khái niệm liên quan, các giai đoạn trong quá trình khám phá tri thức, các kỹ thuật tiếp cận chính trong khai phá dữ liệu, … Chương 2: Giới thiệu về phân cụm dữ liệu, trong đó đi sâu phân tích chi tiết các vấn đề cơ bản trong PCDL và ý nghĩa của PCDL. Đồng thời, trình bày tóm tắt về các đặc trưng của các phương pháp PCDL như: phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,… và nêu các kỹ thuật đánh giá kết quả PCDL. Chương 3: Trình bày các phân tích, đánh giá đối với các thuật toán PCDL điển hình và chỉ ra ưu, nhược điểm của chúng. Chương 4: Trình bày về kỹ thuật phân cụm mờ trong PCDL, cụ thể là trình bày hai thuật toán FCM (Fuzzy C-means) và FCM.
Nêu lên một số kết quả thực nghiệm cho các thuật toán phân cụm mờ. Phụ lục: Cài đặt chương trình thử nghiệm cho thuật toán k-means. TIEU LUAN MOI download : skknchat@gmail.com - 11 - CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.
Quá trình khám phá tri thức trong cơ sở dữ liệu Cuộc cách mạng của khoa học kỹ thuật đã cho phép số hóa thông tin dễ dàng, nhanh chóng với chi phí lưu trữ thấp. Đồng thời, cùng với sự phát triển, trang bị hiện đại của hệ thống phần mềm, phần cứng máy tính, một số lượng dữ liệu khổng lồ đã được tích lũy, lưu trữ. Mục đích của việc thu thập và lưu trữ các kho dữ liệu khổng lồ như vậy không ngoài mục tiêu khai phá dữ liệu nhằm phát hiện các tri thức mới có ích cho hoạt động của con người. Chính vì vậy, kỹ thuật thống kê và các công cụ quản trị dữ liệu cũ không thể đáp ứng được nhu cầu phân tích đầy đủ dữ liệu rộng lớn được nữa và một khuynh hướng mới đã được ra đời, phát triển, đó là lĩnh vực khám phá tri thức và khai phá dữ liệu.
Theo Fayyad, Piatetsky-Shapiro, Smyth, việc nghiên cứu phát triển lĩnh vực khám phá tri thức trong CSDL (Knowledge Discovery in Databases: KDD) nhằm giải quyết tình trạng “ngập tràn thông tin mà vẫn thiếu thốn tri thức”. [22] Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực đã, đang và sẽ được quan tâm triển khai nghiên cứu, phát triển một cách nhanh chóng và rộng rãi. Đã có rất nhiều các thuật ngữ khác nhau mà được coi là cùng mang nghĩa của KDD như knowledge extraction (chiết lọc tri thức), information discovery (phát hiện thông tin), information harvesting (thu hoạch thông tin), data archaeology (khai quật dữ liệu) và data pattern processing (xử lý mẫu dữ liệu). Năm 1989, Fayyad, Smyth và Piatestsky-Shapiro đã định nghĩa một cách đầy đủ về khái niệm Khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database - KDD) như sau: [12]-[22] Khám phá tri thức trong cơ sở dữ liệu (đôi khi còn được gọi là khai phá dữ liệu) là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu.
Quá trình khám phá tri thức trong CSDL được chia thành các bước như trong hình 1.1 dưới đây: TIEU LUAN MOI download : skknchat@gmail.com - 12 - Đánh giá và biểu diễn tri thức Khai phá Biến đổi dữ liệu dữ liệu Tri thức Tiền xử lý dữ liệu Mẫu Trích chọn dữ Dữ liệu liệu chuyển dạng Dữ liệu đã tiền xử lý Dữ liệu đích Dữ liệu Hình 1. Quá trình khám phá tri thức trong CSDL - Trích lọc dữ liệu (Data Selection) Là bước trích chọn những tập dữ liệu cần được khai thác từ các tập dữ liệu lớn (databases, datawarehouses) ban đầu theo một số tiêu chí nhất định. - Tiền xử lý dữ liệu (Data preprocessing) Giai đoạn này hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Tiền xử lý dữ liệu là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…), rút gọn dữ liệu (sử dụng các phương pháp nén dữ liệu, histograms, entropy,…), rời rạc hóa dữ liệu (dựa vào histograms, dựa vào phân khoảng,…).
Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Có thể nói, đây là một bước rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. - Biến đổi dữ liệu (Data transformation) Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho mục đích khai thác ở bước sau. - Khai phá dữ liệu (Data mining) Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật phân tích (phần lớn là các kỹ thuật của học máy) nhằm khai thác, trích chọn được các mẫu thông tin, các mối liên hệ đặc biệt trong dữ liệu.
TIEU LUAN MOI download : skknchat@gmail.com - 13 - - Đánh giá và biểu diễn tri thức (Knowledge representation & evaluation) Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai thác ở bước trên theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,… Đồng thời, bước này cũng đánh giá những tri thức khám phá được theo các tiêu chí nhất định. Trong quá trình phát hiện tri thức trong các CSDL đưọc mô tả ở trên, chúng ta nhận thấy có sự tham gia của các kho dữ liệu. Inmon [12] "kho dữ liệu là tập hợp các dữ liệu định hướng theo chủ đề, được tích hợp từ, có tính phiên bản theo thời gian và kiên định được dùng để hỗ trợ việc tạo quyết định cho người quản trị". Tính liên ngành của khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời vào cuối những năm 1980.
Nó được xem là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh. KPDL nhận được sự quan tâm đặc biệt của các nhà nghiên cứu trong nhiều lĩnh vực học máy, thu nhận mẫu, CSDL, thống kê, trí tuệ nhân tạo, thu nhận tri thức đối với hệ chuyên gia (Hình 1. Hệ thống KDD lôi cuốn các phương pháp, thuật toán và kỹ thuật từ các lĩnh vực rời rạc nhau này. Mục tiêu thống nhất là trích lọc tri thức từ dữ liệu trong ngữ cảnh các CSDL lớn.
Tính đa/liên ngành của khai phá dữ liệu Đối với các lĩnh vực học máy và thu nhận mẫu, sự đan xen với KDD trải theo các nghiên cứu về lý thuyết và thuật toán đối với các hệ thống trích lọc mẫu và mô hình dữ liệu (chủ yếu đối với các phương pháp khai phá dữ liệu). Trọng tâm của KDD đối với việc mở rộng các lý thuyết và thuật toán này hướng tới bài toán tìm ra TIEU LUAN MOI download : skknchat@gmail.com - 14 - các mẫu đặc biệt (những mẫu mà trong một số ngữ cảnh còn được gọi là tri thức hữu dụng hoặc hấp dẫn) trong các tập hợp dữ liệu lớn của thế giới thực. Phát hiện máy với mục tiêu là phát hiện các luật kinh nghiệm từ quan sát và thử nghiệm và mô hình nhân quả phát hiện các kết luận của mô hình nhân quả từ dữ liệu là những lĩnh vực nghiên cứu có mối liên hệ với nhau. Một lĩnh vực nghiên cứu và triển khai có liên quan (trong nhiều trường hợp được coi là một bộ phận của lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL) là lĩnh vực kho dữ liệu (data warehouse) chỉ dẫn tới các khuynh hướng hệ thống thông tin quản lý (MIS: Managment Information Systems) phổ biến hiện tại đối với việc thu thập và làm sạch dữ liệu giao dịch và tạo cho chúng sự biến động khi tìm kiếm trực tuyến.
Một tiệm cận phổ biến đối với việc phân tích kho dữ liệu gọi là OLAP (On-Line Analytical Processing), qua một tập các nguyên lý được Codd đề xuất vào năm 1993 [19]. Các bài toán khai phá dữ liệu điển hình Bước khai phá dữ liệu trong quá trình KDD thường áp dụng một phương pháp khai phá dữ liệu cụ thể, liên quan đến các khái niệm mẫu và mô hình. Mẫu là một biểu thức trong một ngôn ngữ mô tả L được chọn. Mô hình được coi là một biểu thức tổng quát trong ngôn ngữ mô tả L nói trên mà tính tổng quát được thể hiện thông qua các tham số (được gọi là tham số mô hình), trong trường hợp đó, mẫu là một thể hiện của mô hình.
Nhiệm vụ của bài toán khai phá dữ liệu là từ dữ liệu (tập các sự kiện) quan sát đã có thì hoặc cần phải xác định mô hình phù hợp với dữ liệu quan sát, hoặc cần tìm ra các mẫu từ dữ liệu đó. Ở mức cao - tổng quát, hai mục tiêu chủ yếu của khai phá dữ liệu là dự đoán và mô tả. Dự đoán dùng một số biến hoặc trường trong CSDL để dự đoán hoặc về giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến. Mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu.
Dự đoán và mô tả có tầm quan trọng khác nhau đối với các thuật toán khai phá dữ liệu riêng. Ở mức chi tiết - cụ thể, dự đoán và mô tả được thể hiện thông qua các bài toán cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy, mô hình phụ thuộc, phát hiện biến đổi và độ lệch và một số bài toán cụ thể khác. Mô tả khái niệm Bài toán mô tả khái niệm là tìm các đặc trưng và tính chất của các khái niệm. Điển hình nhất là các bài toán như tổng quát hóa, tóm tắt, các đặc trưng dữ liệu ràng buộc,…Bài toán tóm tắt là một bài toán điển hình, áp dụng các phương pháp tìm TIEU LUAN MOI download : skknchat@gmail.com - 15 - một mô tả cô đọng đối với một tập con dữ liệu.
Một ví dụ điển hình về tóm tắt là kỳ vọng và độ lệch chuẩn. Kỹ thuật tóm tắt thường được áp dụng trong phân tích dữ liệu tham dò có tương quan và tự động hóa sinh thông báo. Quan hệ kết hợp Phát hiện mối quan hệ kết hợp là một bài toán quan trọng trong khai phá dữ liệu, trong đó khai phá luật kết hợp là một đại diện điển hình. Phân lớp Phân lớp (Classification) thực hiện việc xây dựng các mô hình (hàm) dự báo nhằm mô tả hoặc phát hiện các lớp hoặc khái niệm cho các dự báo tiếp theo.