Chương 1: Tổng quan về khai phá dữ liệu và khai phá tập mục thường xuyên. Chương 2: Khai phá tập mục lợi ích cao sử dụng cấu trúc cây tiền tố. Chương 3: Chương trình thực nghiệm và ứng dụng. Số hóa bởi Trung tâm Học liệu http://www.vn/ 3 CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN 1.
Khái niệm về khai phá tri thức và khai phá dữ liệu KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không tường minh (ẩn), chưa được biết đến và có tiềm năng mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức.
Quá trình phát hiện tri thức gồm các bước [3], [6]: Bƣớc 1: Trích chọn dữ liệu (data selection): Là bước 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 ware houses). Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): 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,…v.v), rút gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời rạc hóa dữ liệu (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. Bƣớc 3: 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 các kỹ thuật khai thác ở bước sau.
Bƣớc 4: 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 khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Bƣớc 5: Đá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 biểu diễ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,…v. Đồ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. Số hóa bởi Trung tâm Học liệu http://www.vn/ 4 Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất.
Các tri thức nhận được cũng có thể được lưu và sử dụng lại.1: Quá trình phát hiện tri thức Việc KPDL có thể được tiến hành trên một lượng lớn dữ liệu có trong CSDL, các kho dữ liệu hoặc trong các loại lưu trữ thông tin khác. Các mẫu đáng quan tâm có thể được đưa đến người dùng hoặc được lưu trữ trong một cơ sở tri thức. Kiến trúc của hệ thống khai phá dữ liệu Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần phần như hình 1. - CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases, Data ware house,…): Đây là một hay một tập CSDL, các kho dữ liệu, các trang tính hay các dạng lưu trữ thông tin khác.
Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thực hiện trên những dữ liệu này. (Graphical user interface) Giao diện đồ họa cho người dùng (Pattern evaluation) Đánh giá mẫu Cơ sở tri thức (Data mining engine) Máy khai phá dữ liệu (Knowledge-base) (Database or Ware house Server) Máy chủ CSDL hay kho dữ liệu Làm sạch; tích hợp dữ liệu; lọc Các lưu trữ Cơ sở dữ liệu Kho dữ liệu Số hóa bởi Trung tâm Học liệu http://www.vn/ thông tin khác 5 Hình 1.2: Kiến trúc của một hệ thống khai phá dữ liệu - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or Warehouse Server): Máy chủ này có trách nhiệm lấy những dữ liệu tích hợp dựa trên các yêu cầu khai phá của người dùng. - Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để hướng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc như: đặc trưng hóa, kết hợp, phân lớp, phân cụm, phân tích sự tiến hóa.
- Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tương tác với các modun KPDL để duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể modun đánh giá mẫu được tích hợp vào modun khai phá, tùy theo cách cài đặt của phương pháp khai phá được dùng. - Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận này còn cho phép người dùng giao tiếp với hệ thống KPDL.
Ngoài ra, bộ phận này còn cho phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu (hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau. Quá trình khai phá dữ liệu Các giải thuật khai phá dữ liệu thường được miêu tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được.
Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình khai phá dữ liệu được thể hiện bởi mô hình sau [2]: Thống kê tóm tắt Xác định Xác định dữ Thu thập và Giải thuật nhiệm vụ liệu liên quan tiền xử lý DL Mẫu khai phá DL Dữ liệu trực tiếp Số hóa bởi Trung tâm Học liệu http://www.3: Quá trình KPDL + Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết. + Xác định các dữ liệu liên quan dùng để xây dựng giải pháp. + Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được.
Ở đây có thể gặp một số vấn đề: dữ liệu phải được sao ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi v. + Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu: nhằm tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó. Một số kỹ thuật khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện được nhằm vào mục đích này.
Dự đoán liên quan đến việc sử dụng các biến hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp dữ liệu [6] Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000. Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai.
Quá trình phân lớp dữ liệu được thực hiện qua hai bước. Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm. Số hóa bởi Trung tâm Học liệu http://www.vn/ 7 Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định.
Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán. Một ví dụ tiêu biểu về cây quyết định: Tuổi >35 TID 30-35 Sinh viên Yes Giáo sư Yes No Yes No Hình 1.4: Cây quyết định Trong hình 1.4 là một cây quyết định cho lớp mua laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là Yes hay No.
Sau khi mô hình này được xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực. Phân nhóm dữ liệu [6] Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu. Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá trình nhóm những đối tượng vào trong những lớp tương đương, đến những đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong những nhóm khác.
Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những chức năng giống nhau. Thông thường những sự giống về định lượng như khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia trong lĩnh vực của mình.
Nợ nhóm 1 nhóm 2 + + + + + + + + + + + + + + + + + + + + Số hóa bởi Trung tâm Học liệu + + + +http://www.vn/ nhóm 3 Thu nhập 8 Hình 1.
