Chương 1 được bố cục gồm có 9 mục, mục kế tiếp sẽ đề cập đến những vấn đề cơ bản về phát hiện tri thức và khai phá dữ liệu. Mục 3 trong chương sẽ tóm tắt quá trình phát hiện tri thức và khai phá dữ liệu. Mục 4 trình bày các phương pháp khai phá dữ liệu. Mục 5 sẽ trình bày về các vấn đề cần nghiên cứu của phát hiện tri thức và khai phá dữ liệu.
Mục 6 là các lĩnh vực ứng dụng của phát hiện tri thức và khai phá dữ liệu. Mục 7 là kỹ thuật khai phá luật kết hợp. Mục 8 tóm tắt lý thuyết cây quyết định. Cuối cùng là tổng kết những vấn đề đã được tác giả thể hiện trong chương.2 Tổng quan về phát hiện tri thức và khai phá dữ liệu Cùng với sự phát triển của các ngành khoa học, các dữ liệu con người thu nhận, lưu trữ thông qua các hoạt động kinh tế - xã hội, các hoạt động nghiên cứu khoa học ngày một lớn, chúng được lưu trữ trên các hệ thống máy tính với dung lượng lên đến hàng terabyte, thậm chí đến hàng petabyte.
Tuy nhiên, việc hiểu và sử dụng hết được những dữ liệu đó đối với con người rất khó khăn. Trước thực tế như vậy, một hướng nghiên cứu mới về phát hiện tri thức và khai phá dữ liệu đã hình thành và phát triển nhanh chóng trong gần 20 năm qua. Tác giả sẽ trình bày lại một số khái niệm liên quan đến lĩnh vực Phát hiện tri thức và Khai phá dữ liệu (KDD - Knowledge Discovery and Data mining) được đề cập trong [1], [4], [9], [10], [11], [12], nhằm hệ thống hóa những kiến thức nền tảng về lĩnh vực này. Trong thực tế, Phát hiện tri thức và Khai phá dữ liệu còn có thể được sử dụng với cụm từ Khai phá dữ liệu và Phát hiện tri thức.
Dữ liệu (data) là số liệu về các hiện tượng, sự vật mà người ta thu thập được thông qua quan sát, khảo sát trực tiếp hoặc thông qua các thiết bị hỗ trợ, chúng có thể là các con số, các chuỗi ký tự, các biểu tượng hoặc các đối tượng có ý nghĩa nhất định. Dữ liệu có thể được đưa vào các chương trình máy tính theo một định dạng nào đó. Thông tin (information) là các dữ liệu đã qua một quá trình xử lý, chắt lọc và thường mang những ý nghĩa nhất định đối với những đối tượng tiếp nhận thông tin, người ta cũng có thể coi thông tin là những dữ liệu đã được 7 phiên dịch theo một phương pháp nào đó. Thông tin của quá trình xử lý này có thể lại trở thành dữ liệu cho một quá trình xử lý khác.
Tri thức (knowledge) là các thông tin được tích hợp bao gồm cả các cơ sở lập luận và những vấn đề liên quan, được nhận biết, khám phá, phản ánh trong trí óc và tinh thần. Tri thức còn được hiểu đó là dữ liệu đã được trừu tượng hoá và tổng quát hoá ở mức cao. Tri thức có đặc điểm là có thể được tái tạo, phát triển qua các quá trình học, suy luận và vận dụng, tri thức sẽ không mất đi trong quá trình sử dụng mà ngược lại nó càng gia tăng và phát triển lên một mức độ mới nếu càng được sử dụng nhiều. Phát hiện tri thức và khai phá dữ liệu là quá trình tự động trích rút các tri thức (knowledge) hoặc các mẫu (pattern), mô hình (model) có đặc điểm không tầm thường, ẩn, chưa biết trước, có khả năng sử dụng và hiểu được từ khối lượng lớn dữ liệu [4].
Phát hiện tri thức và khai phá dữ liệu là một lĩnh vực phát triển rất nhanh chóng, là lĩnh vực giao thoa giữa nhiều lĩnh vực liên quan như: công nghệ cơ sở dữ liệu, thống kê, học máy, thuật toán học và các lĩnh vực liên quan khác nhằm trích rút ra những tri thức hữu ích từ những tập dữ liệu rất lớn. Người ta cũng có thể sử dụng những tên khác cho khai phá dữ liệu và khám phá tri thức như: khám phá tri thức trong cơ sở dữ liệu (Knowledge discovery in databases - KDD), trích chọn tri thức (Knowledge extraction - KE), phân tích dữ liệu hay mẫu (Data/pattern analysis - DA/PA) hay kinh doanh thông minh hoặc tri thức doanh nghiệp (Business Intelligence - BI) [4]. Công nghệ Thống kê CSDL Học máy Khai phá dữ liệu Trực quan hoá và phát hiện tri thức Nhận diện mẫu Các lĩnh vực Thuật toán khác Hình 1.1 Mối quan hệ của KDD với các lĩnh vực khác [4] 8 Khai phá dữ liệu (Data mining) là một khâu trong quá trình khám phá tri thức mà trong đó ta có thể áp dụng những thuật toán khai phá dữ liệu với những giới hạn có thể chấp nhận được về độ phức tạp tính toán để tìm ra những mẫu hoặc mô hình trong dữ liệu [4]. Khai phá dữ liệu có hai chức năng chính là: mô tả dữ liệu và dự báo dữ liệu, trong đó mô tả dữ liệu tập trung vào tìm kiếm các đặc tính, đặc trưng của dữ liệu, còn dự báo dữ liệu tập trung vào việc phân tích, suy diễn dữ liệu quá khứ, hiện tại để dự báo giá trị dữ liệu tương lai.
Như vậy mục đích của phát hiện tri thức và khai phá dữ liệu là để tìm ra những mẫu và/hoặc những mô hình tồn tại trong cơ sở dữ liệu mà chúng có thể đang ẩn trong khối dữ liệu rất lớn.2 Mối quan hệ của KDD và kinh doanh thông minh [4] Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều lĩnh vực khác nhau [4]. Trong phân tích dữ liệu và hỗ trợ quyết định, phát hiện tri thức và khai phá dữ liệu được ứng dụng vào quản trị kinh doanh và phân tích thị trường (còn được coi là các lĩnh vực kinh doanh thông minh hay trí tuệ doanh nghiệp - Hình 1.2 ) như: định hướng thị trường, quản trị quan hệ khách hàng (Customer Relation Management - CRM), phân tích giỏ hàng, phân mảng thị trường và kinh doanh đa chiều; quản trị và phân tích rủi ro: dự báo, duy trì khách hàng, kiểm soát chất lượng, phân tích cạnh tranh.; phát hiện gian lận và dò tìm những mẫu không 9 bình thường, phân tích cá biệt (outlier). Trong các lĩnh vực khác, người ta áp dụng vào khai phá dữ liệu văn bản (bản tin, thư điện tử, tài liệu), khai phá dữ liệu Web, khai phá dữ liệu theo luồng và các dữ liệu sinh học. Theo [4], người ta thường sử dụng một số tiêu chí sau để phân loại mức độ hấp dẫn của kết quả: Tính căn cứ (Evidence) chỉ ra ý nghĩa của kết quả tìm kiếm được và thường đo bằng các tiêu chí thống kê.
Độ dư thừa (Redundancy) để chỉ sự tương tự của kết quả tìm được so với các kết quả tìm kiếm khác và các độ đo xác định mức độ tương tự của một kết quả với các kết quả khác. Tính hữu dụng (Usefulness) để chỉ mối quan hệ giữa kết quả tìm được và mục tiêu của người dùng. Tính mới (Novelty) để chỉ ra sự khác biệt của kết quả với những tri thức có trước của người sử dụng hay của hệ thống, người ta còn gọi đó là tính bất ngờ. Tính đơn giản (Simplicity) để chỉ độ phức tạp về cú pháp biểu diễn kết quả tìm kiếm và khả năng tổng quát hoá.
Ta cụ thể hoá một số các thuật ngữ như sau: • Dữ liệu (Data): là một tập hợp các thể hiện của các đối tượng hoặc tập hợp các giá trị của các biến (ví dụ là các bản ghi trong cơ sở dữ liệu). • Mẫu (Pattern): là mô tả một tập con của không gian kết quả hoặc không gian dữ liệu, các mẫu và mô hình thường được biểu diễn thông qua một hàm F(v1, v2, .,vn) trong đó vi là các tham số, các tham số này có giá trị là các tập con của dữ liệu. • Tiến trình (Process): thông thường trong tiến trình KDD là quá trình đa bước, bao gồm chuẩn bị và tiền xử lý dữ liệu, tìm kiếm hình mẫu, đánh giá tri thức và tinh chỉnh, được lặp đi lặp lại kèm theo sự sửa đổi nào đó, quá trình này có thể được thực hiện một cách tự động hoặc bán tự động. • Hợp lệ (Validity): Những mẫu hoặc mô hình được khám phá từ một tập dữ liệu huấn luyện phải đúng trên tập dữ liệu mới với một mức độ chắc chắn nào đó, mức độ chắc chắn này xác định khả năng đúng đắn của mẫu hoặc mô hình tìm được, thông thường người ta xác định một ngưỡng tối thiểu cho độ đo chắc chắn để lọc ra các kết quả phù hợp.
Tính mới có thể được đo đối với sự thay đổi trong dữ liệu (bằng việc so sánh các giá trị hiện tại với các giá trị trước hoặc các giá trị mong muốn) hoặc tri thức (kết quả tìm kiếm mới có quan hệ như thế nào đối với kết quả cũ). 10 • Hữu dụng tiềm năng (Potentially Useful): Các mẫu có thể có khả năng hữu dụng, nó thể hiện các kết quả tìm được có phù hợp với mục tiêu của người dùng không. Tính hữu dụng thường được đo bằng các hàm tiện ích là ánh xạ từ không gian kết quả đến không gian mục tiêu với một độ đo nào đó. • Khả năng có thể hiểu được (Understandability): Mục đích của KDD là tạo ra các mẫu mà con người có khả năng hiểu được để có thể nắm bắt tốt hơn về dữ liệu.
Điều này rất khó xác định một cách chính xác do vậy người ta sử dụng một thông số khác là độ đo tính đơn giản (Simplicity). Có nhiều độ đo tính đơn giản được sử dụng, từ việc đo về cú pháp (ví dụ là kích thước của mẫu) đến ngữ nghĩa (ví dụ như con người có dễ nhận thức được không trong một số tình huống). Một độ đo khác rất quan trọng được gọi là mức độ hấp dẫn (Interestingness) thường là độ đo tổng thể kết hợp các độ đo trên của các mẫu hoặc mô hình tìm được, tuỳ theo mục đích của người sử dụng mà mỗi độ đo riêng biệt được gán một trọng số nhất định khi kết hợp trong độ đo tổng thể.3 Quá trình phát hiện tri thức và khai phá dữ liệu Theo [1], quá trình phát hiện tri thức và khai phá dữ liệu được thực hiện thông qua nhiều bước và được lặp đi lặp lại. Dưới đây là tóm tắt lại những bước cơ bản trong quá trình này đã được mô tả chi tiết trong [1].
Bước 1: Tìm hiểu lĩnh vực áp dụng và xác định bài toán, còn được gọi là tìm hiểu tri thức lĩnh vực.