Chương 1: Tổng quan về khai phá dữ liệu (KPDL) 1. Khái niệm KPDL (Data Mining) là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng trong CDSL nhất định. Trong đó tri thức được ngầm hiểu là các thông tin mang tính chất quy luật và hữu ích đối với người sử dụng. KPDL là bước quan trọng nhất trong quá trình Khai phá tri thức (KDD – Knowledge Discovery in Database) - gồm 5 bước như sau [006]: + Thu thập dữ liệu (Data colection): là bước thu thập, trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (Databases, Data marts, Data warehouses, Data repositories) ban đầu theo một số tiêu chí nhất định.
+ Tiền xử lý dữ liệu (Data preprocessing): là bước làm sạch dữ liệu (xử lý với 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 hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, …), rời rạc hoá dữ liệu (rời rạc hoá dựa vào histograms, entropy, 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. + Biến đổi dữ liệu (Data Transformation): đây là bước chuẩn hoá 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 các kỹ thuật khai phá ở bước sau. + KPDL (Data mining): đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của máy học) nhằm để khai phá dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu.
Đây được xem là bước quan trọng nhất và tốn nhiều thời gian nhất của toàn quá trình KDD. + Đánh giá và biểu diễn tri thức (Knowledge presentation and evaluation): chuyển hoặc biểu diễn những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên về một 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 những tiêu chí nhất định. Trích chọn Tiền xử lý Biến đổi DL Dữ liệu thô DL DL Tri thức Đánh giá và Khai phá DL Biểu diễn TT Hình 1.1: Các bước trong quá trình KDD.
Một số phương pháp khai phá dữ liệu sinh luật kết hợp TIEU LUAN MOI download : skknchat@gmail. Các hướng tiếp cận chính trong KPDL Các hướng tiếp cận trong KPDL có thể được phân chia theo chức năng hay lớp các bài toán khác nhau, dưới đây là một số hướng tiếp cận chính: + Phân lớp và Dự đoán (Classification and Prediction): 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 trong hồ sơ bệnh án. 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), ….
Phân lớp và dự đoán còn được gọi là học có giám sát (Supervised learning). + Khai phá luật kết hợp (Association rules mining): khai phá các tri thức dạng luật kết hợp. Ví dụ: “60% nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm đậu phộng”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, 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): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian.
Phương pháp 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 vì nó có tính dự báo cao. + Phân cụm (Clustering/Segmentation): xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không giám sát (Unsupervised learning). + Mô tả khái niệm (Concept description and summarization): 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. Một số phương pháp KPDL phổ biến 1. Phương pháp suy diễn và quy nạp + Phương pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong CSDL dựa trên các quan hệ trong dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ.
Mẫu chiết suất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. + Phương pháp quy nạp: Các thông tin được suy ra từ CSDL bằng cách nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết trước. Cây quyết định và luật + Cây quyết định: Cây quyết định là một phương pháp mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút trong của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá miêu tả các lớp khác nhau.
Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của các thuộc tính của đối tượng tới lá. Một số phương pháp khai phá dữ liệu sinh luật kết hợp TIEU LUAN MOI download : skknchat@gmail.com 11 + Tạo luật: Các luật được tạo ra nhằm suy diễn cho một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng nếu P thì Q, trong đó P là mệnh đề đúng với một phần dữ liệu trong CSDL và Q là mệnh đề dự đoán. Ví dụ: Ta có mẫu phát hiện được bằng phương pháp tạo luật “Nếu mỗi năm cứ tăng vốn lưu động thêm 20% và vốn cố định tăng 10% thì lợi nhuận trước thuế tăng 25%”.
Cây quyết định là phương pháp dùng trong các bài toán phân loại dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Cây quyết định và luật có ưu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là miêu tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về độ chính xác của mô hình. Phát hiện các luật kết hợp Các luật kết hợp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu của hình thành tri thức.
Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Một đầu ra của giải thuật khai phá dữ liệu là tập các luật kết hợp tìm được. Cho một lược đồ R = {A1, A2, …, Ap} với các thuộc tính có miền giá trị {0, 1} và một quan hệ r trên R. Cho W R, đặt s(W, r) là tần số xuất hiện của W trong r được tính bằng tỉ lệ của các hàng trong r có giá trị 1 tại mỗi cột.
Ta định nghĩa một luật kết hợp trên quan hệ r: X => B với X R và B R\X với độ hỗ trợ (tần số xuất hiện) và độ tin cậy: - Độ hỗ trợ = s(X{B}, r). Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X => B sao cho tần số xuất hiện của luật không nhỏ hơn ngưỡng min cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng min cho trước. Những ngưỡng này thường do người dùng hoặc các chuyên gia trong lĩnh vực xác định. Giải thuật tìm các luật kết hợp được bắt đầu bằng việc tìm tất cả các tập mục thường xuyên xuất hiện (FIS - Frequent ItemSet), đây là các tập mục mà tần số xuất hiện lớn hơn min.
Sau đó các luật kết hợp sẽ được khai phá từ các tập mục phổ biến này dựa trên min. Chúng ta sẽ đi sâu nghiên cứu về Luật kết hợp trong Chương 2 và Chương 3. Phân nhóm và phân đoạn Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm.
Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá các thuộc tính của các thành phần như là hàm của các tham số của các thành phần. Kỹ thuật này được gọi là kỹ thuật phân hoạch tối ưu. Một số phương pháp khai phá dữ liệu sinh luật kết hợp TIEU LUAN MOI download : skknchat@gmail.com 12 Một trong những ứng dụng của kỹ thuật phân nhóm theo độ giống nhau là cơ sở dữ liệu khách hàng để phân nhóm khách hàng theo các tham số và các nhóm thuế tối ưu có được khi thiết lập biểu thuế bảo hiểm. Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu chứa dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu.
Khi các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan trọng. Mạng Neural Mạng neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng neural có thể đưa ra các kết luận từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được.
Một trong những ưu điểm phải kể đến của mạng neural là khả năng tạo ra các mô hình dự đoán do có độ chính xác cao, có thể áp dụng được cho nhiều các bài toán khác nhau đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo,…. Mẫu chiết xuất bằng mạng neural được thể hiện ở các nút đầu của mạng. Mạng neural có thể sử dụng các hàm số bất kỳ chứ không chỉ đơn giản là sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng neural là không cần gia công dữ liệu nhiều trước khi bắt đầu quá trình học như các kỹ thuật khác.
Tuy nhiên để có thể sử dụng mạng neural có hiệu quả cần xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng (kiến trúc) là gì ? - Mạng cần bao nhiêu tầng và bao nhiêu nút ?