CHƯƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 1.1 Giới thiệu tổng quan Trong thời đại hiện nay, với sự phát triển vượt vật của công nghệ thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Không có một lĩnh vực nào lại không cần đến sự hỗ trợ của công nghệ thông tin và sự thành công của các lĩnh vực đó phụ thuộc rất nhiều vào việc nắm bắt thông tin một cách nhạy bén, nhanh chóng và hữu ích. Với nhu cầu như thế nếu chỉ sử dụng thao tác thủ công truyền thống thì độ chính xác không cao và mất rất nhiều thời gian. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu (KPDL) và Máy Học (MH) có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa biết.
Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. Do vậy việc khai phá tri thức từ dữ liệu trong các tập tài liệu lớn chứa đựng thông tin phục vụ nhu cầu nắm bắt thông tin có vai trò hết sức to lớn. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay.1 Khái niệm khai phá dữ liệu Khai phá dữ liệu (data mining) Là quá trình tính toán để tìm ra các mẫu trong các bộ dữ liệu lớn liên quan đến các phương pháp tại giao điểm của máy học, thống kê và các hệ thống cơ sở dữ liệu. Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó.
Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowledge Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự sau: 1. Làm sạch dữ liệu (data cleaning & preprocessing)s: Loại bỏ nhiễu và các dữ liệu không cần thiết. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xử lý (data cleaning & preprocessing). Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức.
Quá trình này bao 4 gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không đầy đủ (incomplete data),. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý. Khai phá dữ liệu(data mining): Là một trong các bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu. Ước lượng mẫu (knowledge evaluation): Quá trình đánh giá các kết quả tìm được thông qua các độ đo nào đó.
Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng.2 Một số ứng dụng của khai phá dữ liệu Data Mining tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể liệt kết ra đây một số ứng dụng điển hình: • Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support) • Điều trị y học (medical treatment) • Khai phá văn bản và khai phá web (Text mining & Web mining) • Tin-sinh (Bioinformatics) • Tài chính và thị trường chứng khoán (finance & stock market) • Bảo hiểm (insurance) • Nhận dạng (pattern recognition) 1.3 Quá trình phát hiện tri thức và khai phá dữ liệu Một vấn đề rất quan trọng để dẫn đến thành công là việc biết sử dụng thông tin một cách có hiệu quả.1 : Quá trình phát hiện tri thức 5 Trước khi đi vào tìm hiểu các giai đoạn trong KDD em đưa ra một số ví dụ để phân biệt ba khái niệm: dữ liệu, thông tin và tri thức.2: Mối quan hệ giữa thông tin, dữ liệu và tri thức 1.4 Các bước của quá trình KPDL Các giải thuật KPDL thường được mô 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.3 : Quá trình KPDL 6 1.2 Một số kỹ thuật khai phá dữ liệu cơ bản 1.1 Khai phá dữ liệu dự đoán Nhiệm vụ của khai phá dữ liệu dự đoán là đưa ra các dự đoán dựa vào các suy diễn trên cơ sở dữ liệu hiện nay, bao gồm một số thuật toán nổi tiếng thuộc về nhóm học có giám sát như: phân lớp (Classification) và hồi quy (Regression). ● Phân lớp: k-Nearest Neighbors, mạng nơron nhân tạo, SVM, … ● Hồi quy: Linear Regression, Logistic Regression, … ❖ Phân lớp (Classification) Một bài toán được gọi là phân lớp nếu các nhãn của dữ liệu đầu vào được chia thành một số hữu hạn lớp (miền giá trị là rời rạc). Chẳng hạn như tính năng xác định xem một email có phải là spam hay không của Gmail; xác định xem hình ảnh của con vật là chó hay mèo. ❖ Hồi quy (Regression) Hồi quy là quá trình tìm mối quan hệ phụ thuộc của một biến (được gọi là biến phụ thuộc hay biến được giải thích, biến được dự báo, biến được hồi quy, biến phản ứng, biến nội sinh) vào một hoặc nhiều biến khác (được gọi là biến độc lập, biến giải thích, biến dự báo, biến hồi quy, biến tác nhân hay biến kiểm soát, biến ngoại sinh) nhằm mục đích ước lượng hoặc tiên đoán giá trị kỳ vọng của biến phụ thuộc khi biết trước giá trị của biến độc lập.4 : Thuật toán hồi quy 1.2 Khai phá dữ liệu mô tả Kỹ thuật này 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ó bao gồm các kỹ thuật: Phân cụm (clustering) và khai phá luật kết hợp (asociation rules).
7 ❖ Phân cụm Một bài toán phân cụm / phân nhóm toàn bộ dữ liệu X thành các nhóm/cụm nhỏ dựa trên sự liên quan giữa các dữ liệu trong mỗi nhóm. Chẳng hạn như phân nhóm khách hàng dựa vào độ tuổi, giới tính.5 : Thuật toán phân cụm Tất cả các phương pháp đều sử dụng các cấu trúc vốn có trong dữ liệu để tổ chức tốt nhất dữ liệu thành các nhóm có mức độ phổ biến tối đa dựa vào trọng tâm (centroid) và thứ bậc (hierarchal) như thể hiện ở Hình 1.5 ❖ Luật kết hợp Là bài toán mà khi em muốn khám phá ra một quy luật dựa trên nhiều dữ liệu cho trước. Ví dụ như những khách hàng mua mặt hàng này sẽ mua thêm mặt hàng kia; hoặc khán giả xem phim này sẽ có xu hướng thích xem phim kia, dựa vào đó em có thể xây dựng những hệ thống gợi ý khách hàng (Recommendation System) nhằm thúc đẩy nhu cầu mua sắm hoặc xem phim….6 : Thuật toán học quy tắc kết hợp 1.3 Tổng quan các phương pháp học máy cơ bản 1.1 Học có giám sát (supervised learning) Học có giám sát là thuật toán dự đoán nhãn (label)/đầu ra (output) của một dữ liệu mới dựa trên tập dữ liệu huấn luyện mà trong đó mỗi mẫu dữ liệu đều đã được gán nhãn.7 : Thuật toán học có giám sát Một cách toán học, học có giám sát là khi em có một tập hợp biến đầu vào $ X={x_1,x_2,…,x_N} $ và một tập hợp nhãn tương ứng $ Y={y_1,y_2,…,y_N} $, trong đó $ x_i$, $y_i $ là các vector. Các cặp dữ liệu biết trước $( x_i, y_i ) \in X \times Y $ được gọi là tập dữ liệu huấn luyện (training data).
Từ tập dữ liệu huấn luyện này, em cần tạo ra một hàm số ánh xạ mỗi phần tử từ tập X sang một phần tử (xấp xỉ) tương ứng của tập Y: 𝑦𝑖 ≈ 𝑓(𝑥𝑖 ), ∀𝑖 = 1,2, … , 𝑁 Mục đích là xấp xỉ hàm số $f$ thật tốt để khi có một dữ liệu x mới, em có thể tính được nhãn tương ứng của nó $y=f(x)$. Ví dụ: Trong nhận dạng chữ số viết tay, em có ảnh của hàng nghìn trường hợp ứng với mỗi chữ số được viết bởi nhiều người khác nhau. Em đưa các bức ảnh này vào một thuật toán học và chỉ cho nó biết “mỗi bức ảnh tương ứng với chữ số nào”. Sau khi thuật toán tạo ra một mô hình, tức là một hàm số nhận đầu vào là một bức ảnh và cho ra kết quả là một chữ số.
Khi nhận được một bức ảnh mới mà mô hình “chưa từng gặp qua” và nó sẽ dự đoán xem bức ảnh đó tương ứng với chữ số nào.8: Ảnh minh hoạ cho tập dữ liệu chữ số viết tay – MNIST Đối với những ai sử dụng mạng xã hội Facebook thì khá quen thuộc với tính năng phát hiện khuôn mặt trong một bức ảnh, bản chất của thuật toán dò tìm các khuôn mặt 9 này là một thuật toán học có giám sát với tập huấn luyện là vô số ảnh đã được gán nhãn là mặt người hay không phải mặt người.2 Học bán giám sát (Semi-supervised learning) Là bài toán mà khi tập dữ liệu đầu vào X là hỗn hợp các mẫu có nhãn và không có nhãn, trong đó số lượng có nhãn chỉ chiếm một phần nhỏ như minh hoạ. Phần lớn các bài toán thực tế của ML thuộc nhóm này vì việc thu thập dữ liệu có nhãn tốn rất nhiều thời gian và có chi phí cao. Rất nhiều loại dữ liệu thậm chí cần phải có chuyên gia mới gán nhãn được, chẳng hạn như ảnh y học hoặc các cặp câu song ngữ. Ngược lại, dữ liệu chưa có nhãn có thể được thu thập với chi phí thấp từ internet.3 Học không có giám sát (Unsupervised learning) Trái với Supervised learning, học không giám sát là thuật toán dự đoán nhãn của một dữ liệu mới dựa trên tập dữ liệu huấn luyện mà trong đó tất cả các mẫu dữ liệu đều chưa được gán nhãn hay nói cách khác là em không biết câu trả lời chính xác cho mỗi dữ liệu đầu vào như minh hoạ.