Tài liệu Khai phá tập mục thường xuyên đóng trong cơ sở dữ liệu và ứng dụng

i LỜI CẢM ƠN Trước hết em xin gửi lời cảm ơn đến TS. Nguyễn Huy Đức, người thầy đã hướng dẫn em rất nhiều trong suốt quá trình tìm hiểu, nghiên cứu và hoàn thành luận văn tốt nghiệp từ lý thuyết đến ứng dụng. Sự hướng dẫn của thầy đã giúp em có thêm được những hiểu biết khai phá dữ liệu và ứng dụng của nó. Đồng thời em cũng xin chân thành cảm ơn các thầy cô trong trường cũng như các thầy cô ở Viện Khoa học và công nghệ Việt Nam đã tận tình giảng dạy, trang bị cho em những kiến thức cơ bản cần thiết để em có thể hoàn thành tốt luận văn. Em xin gửi lời cảm ơn đến gia đình, bạn bè đã tạo mọi điều kiện thuận lợi để em có thể xây dựng thành công luận văn này. Thái Nguyên, tháng 06 năm 2013 Học viên Lê Thị Tuyết Nhung ii LỜI CAM ĐOAN Tôi xin cam đoan đề tài “Khai phá tập mục thường xuyên đóng trong cơ sở dữ liệu và ứng dụng ” là công trình nghiên cứu của bản thân tôi. Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong luận văn. Tôi xin chịu trách nhiệm về luận văn của mình. iii MỤC LỤC Lời cảm ơn i Lời cam đoan MỤC LỤC DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC HÌNH VẼ MỞ ĐẦU Chương 1: Tổng quan về khai phá dữ liệu và khai phá tập mục thường ii iii v vi vii 1 xuyên 2 1.1 Khái niệm về khai phá tri thức và khai phá dữ liệu 2 1.2 Kiến trúc của hệ thống khai phá dữ liệu 4 1.3 Quá trình khai phá dữ liệu 5 1.4 Một số kỹ thuật khai phá dữ liệu 8 1.4.1 Phân lớp và dự đoán (Classification & Prediction) 8 1.4.2 Luật kết hợp (Association Rules) 11 1.4.3 Khai thác mẫu tuần tự (Sequential/ Temporal patterns) 11 1.4.4 Phân nhóm - đoạn (Clustering/ Segmentation) 11 1.4.5 Hồi quy (Regression) 12 1.4.6 Tổng hợp hóa (Summarization) 12 1.4.7 Mô hình hóa sự phụ thuộc (dependency modeling) 12 1.4.8 Phát hiện sự biến đổi và độ lệch (Change and deviation detection) 13 1.5 Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 13 1.6 Một số ứng dụng của khai phá dữ liệu 14 1.7 Khai phá luật kết hợp 14 1.7.1 Bài toán phát hiện luật kết hợp 14 1.7.2 Các khái niệm 15 1.7.3 Các cách tiếp cận khai phá tập mục thường xuyên 18 1.7.4 Một số thuật toán điển hình tìm tập mục thường xuyên 19 1.7.4.1 Thuật toán Apriori (Phương pháp sinh ứng viên) 19 1.7.4.2 Thuật toán FP-Growth 23 iv 1.8 Kết luận chương 1 Chương 2: Khai phá tập mục thường xuyên đóng trong cơ sở dữ liệu 31 32 2.1 Cơ sở toán học của tập mục thường xuyên đóng 32 2.1.1 Ánh xạ đóng 32 2.1.2 Tập đóng 32 2.1.3 Kết nối Galois 32 2.1.4 Bao đóng của tập mục dữ liệu 33 2.2 Khái niệm, tính chất tập mục thường xuyên đóng 34 2.3 Một số thuật toán điển hình khai phá tập mục thường xuyên đóng 35 2.3.1 Thuật toán CHARM (Phương pháp dựa trên cây IT-Tree) 35 2.3.1.1 Giới thiệu thuật toán CHARM 35 2.3.1.2. Cây tìm kiếm và lớp tương đương 35 2.3.1.3 Các tính chất cơ bản của cặp tập mục – tập định danh 36 2.3.1.4 Thiết kế thuật toán 37 2.3.2 Thuật toán Closet + 41 2.4 Kết luận chương 2 Chương 3: Chương trình thực nghiệm ứng dụng trong lĩnh vực y tế 45 46 3.1 Bài toán phát hiện luật kết hợp trong dữ liệu y tế 46 3.2 Xây dựng chương trình 50 3.3 Kết quả thực nghiệm 57 3.4 Nhận xét 58 KẾT LUẬN 59 TÀI LIỆU THAM KHẢO 60 PHỤ LỤC 62 v DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải Ck Tập các k tập mục ứng viên BFS Breadth First Search CSDL Cơ sở dữ liệu CHARM Closed Asociation RuleMning DB Cơ sở dữ liệu giao tác DFS Depth First Search FP -growth Frequent -Pattern Growth FP -tree Frequent pattern tree IT-tree Itemset-Tidset tree I Tập các mục dữ liệu k-itemset Tập mục gồm k mục KPDL Khai phá dữ liệu Minsup Ngưỡng hỗ trợ tối thiểu Lk Tập các k-tập mục thường xuyên Supp Độ hỗ trợ (support) TID Định danh của giao tác T Giao tác (transaction) DL Dữ liệu TX Thường xuyên TTHN Tình trạng hôn nhân vi DANH MỤC CÁC BẢNG Bảng 1.1 Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori Bảng 1.2: CSDL giao tác minh họa cho thuật toán FP-Growth Bảng 2.1: a) CSDL giao tác biểu diễn ngang b) CSDL giao tác biểu diễn dọc Bảng 3.1 : Dữ liệu bệnh hen suyễn Bảng 3.2: Lựa chọn thuộc tính Bảng 3.3: Thuộc tính “Tuổi” sau khi phân hoạch Bảng 3.4: Dữ liệu tìm kiếm sau khi thực hiện phân loại dữ liệu Bảng 3.5: Chuyển đổi dữ liệu Bảng 3.6: Dữ liệu cho khai phá vii DANH MỤC HÌNH VẼ Hình 1.1: Kiến trúc của một hệ thống khai phá dữ liệu Hình 1.2: Quá trình khám phá tri thức Hình 1.3: Quá trình khai phá dữ liệu Hình 1.4: Cây FP-tree được xây dựng dần khi thêm các giao tác t1 ÷ t6 Hình 1.5: Cây FP-tree của CSDL DB trong bảng 1.5 Hình 2.1: Kết nối Galois Hình 2.2: Cây IT-tree dùng Tidset với minSup =3 Hình 2.3: Cây IT-tree tìm tập mục thường xuyên đóng thỏa mãn ngưỡng minsup = 50% Hình 2.4: Áp dụng tính chất của tập thường xuyên đóng Hình 2.5: Minh họa xây dựng cây kết quả Hình 3.1: Mô hình khai phá cho dữ liệu y tế Hình 3.2: Giao diện chính chứa dữ liệu gốc Hình 3.3: Hiển thị dữ liệu chuyển đổi Hình 3.4: Giao diện thêm mới bản ghi 1 MỞ ĐẦU Khai phá dữ liệu (Data Mining), hiện nay đang được rất nhiều người chú ý. Nó thực sự đã đem lại những lợi ích đáng kể trong việc cung cấp những thông tin tiềm ẩn trong các cơ sở dữ liệu lớn, giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Những “tri thức” chiết xuất từ nguồn cơ sở dữ liệu đó phục vụ các yêu cầu trợ giúp quyết định ngày càng có ý nghĩa quan trọng và là nhu cầu to lớn trong mọi lĩnh vực hoạt động kinh doanh, quản lý. Tiến hành công việc như vậy chính là thực hiện quá trình phát triển tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát hiện những tri thức tiềm ẩn. Một trong các nội dung cơ bản trong khai phá dữ liệu là khai phá luật kết hợp. Khai phá luật kết hợp gồm hai bước: Bước thứ nhất, tìm tất cả các tập mục thường xuyên, đòi hỏi sự tính toán lớn. Bước thứ hai, dựa vào các tập mục thường xuyên tìm các luật kết hợp, đòi hỏi tính toán ít hơn, song gặp phải một vấn đề là có thể sinh ra quá nhiều luật, vượt khỏi sự kiểm soát của người khai phá hoặc người dùng, trong đó có nhiều luật không cần thiết. Để giải quyết vấn đề đó, trong bước thứ nhất, không cần thiết khai phá tất cả các tập mục thường xuyên mà chỉ cần khai phá các tập mục thường xuyên đóng. Khai phá luật kết hợp dựa trên tập mục thường xuyên đóng cho hiệu quả cao hơn, nó đảm bảo không tìm ra các tập mục thường xuyên không cần thiết, không sinh ra các luật dư thừa. Với ý nghĩa đó và mục đích tìm hiểu về bài toán tìm tập mục thường xuyên trong cơ sở dữ liệu lớn, em đã quyết định lựa chọn đề tài “Khai phá tập mục thường xuyên đóng trong cơ sở dữ liệu và ứng dụng”. Nội dung luận văn gồm 3 chương: 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 thường xuyên đóng trong cơ sở dữ liệu Chương 3: Chương trình thực nghiệm ứng dụng trong lĩnh vực y tế 2 CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN 1.1 Khái niệm về khai phá tri thức và khai phá dữ liệu "Khám phá tri thức là quá trình tìm ra những tri thức, đó là những mẫu tìm ẩn, trước đó chưa biết và là thông tin hữu ích đáng tin cậy". Còn khai phá dữ liệu (KPDL) là một bước quan trọng trong quá trình khám phá tri thức, sử dụng các thuật toán KPDL chuyên dùng với một số qui định về hiệu quả tính toán chấp nhận được để chiết xuất ra các mẫu hoặc các mô hình có ích trong dữ liệu. Nói một cách khác, mục đích của khám phá tri thức và KPDL chính là tìm ra các mẫu hoặc mô hình đang tồn tại trong các cơ sở dữ liệu (CSDL) nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu. Khám phá tri thức từ CSDL là một quá trình sử dụng các phương pháp và công cụ tin học, trong đó con người là trung tâm của quá trình. Do đó, con người cần phải có kiến thức cơ bản về lĩnh vực cần khám phá để có thể chọn được tập con dữ liệu tốt, từ đó phát hiện các mẫu phù hợp với mục tiêu đề ra. Đó chính là tri thức, được rút ra từ CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Tuy vậy, quá trình khám phá tri thức mang tính chất hướng nhiệm vụ vì không phải là mọi tri thức tìm được đều áp dụng vào thực tế được. Để có được những thông tin quý báu chúng ta phải tìm ra các mẫu có trong tập CSDL trước. Việc đánh giá các mẫu được tìm thấy cũng là một điều thú vị và tất yếu có tính chất quyết định đến sự sử dụng hay không sử dụng chúng. Đầu ra của một chương trình là khám phá những mẫu có ích được gọi là tri thức. Tri thức được khám phá có các đặc điểm chính: - Kiến thức cao cấp: Ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Quá trình để tìm ra kiến thức như vậy không phải từ những phương pháp thống kê cổ điển mà mà nó được được đúc kết từ các kinh nghiệm đã có, được thể hiện trong dữ liệu, những kết quả đó có thể lĩnh hội được. 3 - Độ chính xác: Dù cho những mẫu khai phá thật sự có trong CSDL hay không thì việc đo lường trị giá của chúng là bắt buộc phải có. Chúng ta sẽ chỉ sử dụng những mẫu nào có độ chính xác càng cao thì hiệu quả công việc đạt được càng lớn, những mẫu có độ chính xác chưa được xác định rõ ràng hoặc không cao thì không nên sử dụng chúng. - Tính hấp dẫn: Khám phá tri thức được coi là lý thú vì nó có thể vạch ra các xu hướng một cách hoàn thiện. Đó là những điều mới lạ hay những quy trình tìm năng, hữu ích ẩn chứa từ trong dữ liệu trước đó. - Tính hiệu quả: thời gian chạy của thuật toán khám phá tri thức trên CSDL lớn có thể dự tính và chấp nhận được. Dữ liệu là tập hợp những bộ thông tin chính xác và quá trình khám phá tri thức được xem là sự lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu chỉ để lại các đặc trưng cơ bản cho dữ liệu. Tri thức được tìm thấy là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ trong chúng. Các mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học. Nếu khám phá tri thức là toàn bộ quá trình chiết xuất tri thức từ các CSDL thì KPDL là giai đoạn chủ yếu của quá trình đó. KPDL là một quá trình phát hiện các mẫu mới, thường bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm kiếm các mẫu từ tập dữ liệu theo mô hình đó. Sử dụng các kỹ thuật và các khái niệm của các lĩnh vực đã được nghiên cứu từ trước như: học máy, nhận dạng, thống kê, hồi quy, xếp loại, phân nhóm, các mô hình đồ thị, các mạng Bayes, Hầu hết các CSDL đều chứa rất nhiều các mẫu mới và có ích, tuy nhiên mẫu có giá trị với mục tiêu đặt ra phải là những mẫu không tầm thường. Để các mẫu trở nên không tầm thường, hệ thống phải làm nhiều hơn là chỉ mò mẫm thống kê vì kết quả của việc tính toán trực tiếp qua công tác thống kê là đã có đối với người dùng. Một hệ thống tìm kiếm cần phải có khả năng quyết định cần thực hiện tính toán nào và kết quả là có đáng quan tâm để tạo nên tri thức trong ngữ cảnh hiện tại hay không. KPDL được sử dụng để tạo ra giả thuyết. Ví dụ như để xác định các yếu tố rủi ro khi cho vay tín dụng, kỹ thuật KPDL phải phát hiện được những người có thu 4 nhập thấp và nợ nhiều là những người sẽ có mức rủi ro cao. Ngoài ra kỹ thuật cũng có thể phát hiện ra những quy luật mà nhà phân tích có thể chưa tìm ra ví dụ như tỷ lệ giữa thu nhập trên nợ và tuổi cũng là các yếu tố xác định mức rủi ro. Để làm được điều này, KPDL sử dụng các thông tin trong quá khứ để học. Nó sẽ tìm kiếm các thông tin này trong các CSDL và sử dụng chúng để tìm ra các mẫu đáng quan tâm. Nếu xét về mặt ý tưởng và mục đích ứng dụng, KPDL là một nhu cầu tất yếu, một sự nhạy cảm đáp lại sự mong mỏi của giới kinh doanh thì về mặt kỹ thuật, đó thực sự là một khó khăn và là cả sự thách thức đối với những nhà khoa học. KPDL được xây dựng dựa trên việc sử dụng các giải thuật mới, được định hướng theo như cầu kinh doanh để có thể giải quyết tự động các bài toán kinh doanh bằng các kỹ thuật dễ dùng và có thể hiểu được. Các kỹ thuật đang được nghiên cứu và sử dụng hiện nay bao gồm cây quyết định (CART, CHAID, AID), mạng neuron, phương pháp láng giềng gần nhất, các luật suy diễn, KPDL không thuộc một ngành công nghiệp nào. Nó sử dụng các kỹ thuật thông minh để khai phá các tri thức tiềm ẩn trong dữ liệu. 1.2 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 như hình 1.1 [8]: Dữ liệu thực Mẫu ước lượng Công cụ khai thác Cơ sở tri thức DL Kho dữ liệu Cơ sở tri thức Kho dữ liệu Nơi chứa DL khác Hình 1.1: Kiến trúc của một hệ thống khai phá dữ liệu 5 - CSDL, kho dữ liệu hoặc nơi lưu trữ thông tin khác (Databases, Data warehouse,...): Đây là một hay một tập các 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. - 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 thí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 đượ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 môđun 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. - Môđun đánh giá mẫu (Pattern evaluation): Bộ phận này tương tác với các môđun 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ể môđun đánh giá mẫu được tích hợp vào môđun khai phá, tùy theo sự 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 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 khuôn dạng khác nhau. 1.3 Quá trình khai phá dữ liệu 6 Hình 1.2: Quá trình khám phá tri thức Quá trình khám phá tri thức từ CSDL là một quá trình có sử dụng nhiều phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người là trung tâm. Do đó, nó không phải là một hệ thống phân tích tự động mà là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và CSDL, tất nhiên là với sự hỗ trợ của các công cụ tin học. Người sử dụng hệ thống ở đây phải là người có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn được đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so với mục đích. Tri thức mà ta nói ở đây là các tri thức rút ra từ các CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Do đó, quá trình phát hiện tri thức cũng mang tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. (1) Gom dữ liệu (Gathering): Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một CSDL, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. (2) Trích lọc dữ liệu (Selection): Ở giai đoạn này lựa chọn những dữ liệu phù hợp với nhiệm vụ phân tích trích rút từ CSDL. (3) Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing, Pre-processing and Preparation) Giai đoạn thứ ba này là giai đoạn 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. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logic. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu, ví dụ: điểm = -1. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được "làm sạch" sẽ gây nên những kết quả sai lệch nghiêm trọng. (4) Chuyển đổi dữ liệu (Transformation): Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu được chuyển đổi hay được hợp nhất về dạng thích hợp cho việc khai phá. 7 (5) Khai phá dữ liệu (Data Mining): Đây là một tiến trình cốt yếu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng một cách phù hợp để trích xuất thông tin có ích hoặc cá mẫu điển hình trong dữ liệu. (6) Đánh giá kết quả mẫu (Evaluation of Result): Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu được chiết xuất, không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần thiết. Từ quá trình khám phá tri thức trên chúng ta thấy được sự khác biệt giữa khám phá tri thức và khai phá dữ liệu. Trong khi khám phá tri thức là nói đến quá trình tổng thể phát hiện tri thức hữu ích từ dữ liệu. Còn KPDL chỉ là một bước trong quá trình khám phá tri thức, các công việc chủ yếu là xác định được bài toán khai phá, tiến hành lựa chọn phương pháp KPDL phù hợp với dữ liệu có được và tách ra các tri thức cần thiết. Quá trình khai phá dữ liệu được thể hiện bởi mô hình sau: Thống kê Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý dữ liệu tóm tắt Giải thuật khai phá dữ liệu Mẫu DL trực tiếp Hình 1.3: Quá trình khai phá dữ liệu - 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 KPDL 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,...). - Chọn thuật toán KPDL thích hợp và thực hiện việc KPDL: 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 đó. 8 1.4 Một số kỹ thuật khai phá dữ liệu Các kỹ thuật KPDL được có thể chia làm 2 nhóm chính: - Kỹ thuật KPDL mô tả: 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ó. Nhóm kỹ thuật này gồm các phương pháp: phân nhóm (Clustering), tổng hợp hóa (Summerization), phát hiện sự biến đổi và độ lệch (Change and deviation detection), phân tích luật kết hợp (Association Rules), ... - Kỹ thuật KPDL dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Nhóm kỹ thuật này gồm các phương pháp: phân lớp (Classification), hồi quy (Regression), ... 1.4.1 Phân lớp và dự đoán (Classification & Prediction) Là đặt các mẫu vào các lớp được xác định trước. Nhiệm vụ chính là tìm các hàm ánh xạ các mẫu dữ liệu một cách chính xác vào trong các lớp.Ví dụ một ngân hàng muốn phân loại các khách hành của họ vào trong hai nhóm có nợ hay không nợ, từ đó giúp họ ra quyết định cho vay hay không cho vay. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu. - Bước 1: Một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát (supervised learning) khác với phân nhóm dữ liệu là học không có giám sát (unsupervised learning). - Bước 2: Sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng Nơron (Neural networks), Giải thuật di truyền (Genetic algorithms), Mạng Bayesian (Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets). 9 a) Cây quyết định (Decision Tree) Các kỹ thuật phân lớp sử dụng cây quyết định để phân tách các dữ liệu cho đến khi mỗi phần chứa đựng hầu hết các mẫu từ một lớp đặc trưng, kết quả của quá trình sẽ cho ra một cây quyết định. Điểm phân tách trong cây quyết định là một nút (không phải là nút lá) sẽ sử dụng một số điều kiện để quyết định dữ liệu sẽ được phân tách như thế nào. Các nút cuối cùng trong cây quyết định chứa đựng các bộ mẫu giống nhau. Lợi thế của cây quyết định là các thuật toán chạy khá nhanh, với kết quả khá tốt và có thể giải thích được rõ ràng. Tuy nhiên, bất lợi mà các thuật toán của cây quyết định có thể gặp phải đó là chúng có thể tìm ra các điểm tới hạn cục bộ, đưa ra các kết quả không đúng. b) K-láng giềng gần nhất (k-Nearest Neighbor) Thuật toán này tìm ra các láng giềng gần nhất của mẫu thử nghiệm và quy về các nhãn lớp của chúng dựa trên các nhãn đa số, điều đó có nghĩa là các mẫu được quy về cùng lớp khi chúng là lân cận của nhau. Kỹ thuật này cho rằng vị trí trong không gian đặc trưng hàm ý một quan hệ họ hàng gần gũi ở giữa các nhãn lớp. Lợi thế của các thuật toán K-Láng giềng gần nhất là dễ thực thi, và kết quả mà nó đem lại khả năng dễ dàng giải thích. Nhưng một điểm bất lợi là các thuật toán này đưa ra các mô hình rất lớn với một tập dữ liệu nhỏ. c) Mạng nơron (Neural networks) Mạng nơron là mạng được mô phỏng theo bộ não của con người. Đó là một cấu trúc dữ liệu của các hàm với một hoặc nhiều trọng số đầu vào, với kết quả đầu ra là một nhãn các lớp. Từng phần riêng biệt của dữ liệu được đưa vào mạng nơron và các hàm - các trọng số trong mạng nơron bị thay đổi (học - huấn luyện) tùy theo tỷ lệ lỗi của đầu ra. Phương pháp này thường đưa đến một khoảng thời gian huấn luyện dài ngay cả khi tập dữ liệu nhỏ. Lợi thế của mạng nơron là đưa đến các kết quả khá chính xác, nhưng bất lợi của nó là thường đòi hỏi thời gian huấn luyện dài và đưa ra các kết quả khó hiểu, cứng nhắc, bị bao bọc trong một hộp đen, khó giải thích tường minh. 10 d) Giải thuật di truyền (Genetic algorithms) Các giải thuật di truyền được sử dụng để đưa ra công thức giả thuyết về sự phụ thuộc giữa các biến. Đối với một giải thuật di truyền phải sử dụng các giải pháp như cạnh tranh, lựa chọn và kết hợp giữa các tập hợp cá thể. Lợi thế của Giải thuật di truyền là thường đưa đến các kết quả kiểm tra khá chính xác, nhưng bất lợi của nó là kết quả có được thông qua việc lập trình tiến hóa và các kết quả cũng thường cứng nhắc, khó hiểu. e) Mạng Bayesian (Bayesian networks) Trong mạng Bayesian sử dụng các đồ thị có hướng, không có chu trình để miêu tả sự phân lớp có thể được. Các đồ thị này cũng có thể được sử dụng để miêu tả các tri thức chuyên gia. Các nút miêu tả các biến thuộc tính và các trạng thái (sự kiện) và mỗi một cạnh miêu tả khả năng sự phụ thuộc giữa chúng. Kết hợp với mỗi nút là các lớp cục bộ có thể và các cung được vẽ từ nút nguyên nhân đến nút bị ảnh hưởng. KPDL trong mạng Bayesian bao gồm việc sử dụng đầu vào các tri thức chuyên gia và sau đó sử dụng một CSDL để cập nhật, lọc và cải tiến tri thức đó trong mạng. Các đồ thị mới có thể là kết quả từ các cải tiến này và nguyên nhân của các mối quan hệ giữa các nút kết quả có thể được giải thích một cách dễ dàng. Lợi thế của mạng Bayesian là thường đưa ra các kết quả dễ hiểu, nhưng bất lợi của nó là cần thu thập được các tri thức chuyên gia truyền thống. f) Tập mờ và tập thô (Rough and Fuzzy Sets) Lý thuyết về tập mờ và tập thô dựa trên một sơ sở toán học không chắc chắn. Đối với các mô hình tập thô, một giới hạn trên và giới hạn dưới sẽ được xác định. Một tập thô định nghĩa một lớp C là một xấp xỉ bởi hai tập. Tập cận dưới (lower) của C bao gồm tất cả các mẫu dữ liệu, mà dựa vào tri thức của các mẫu dữ liệu có thể quyết định một mẫu bất kỳ thuộc phân lớp C một cách rõ ràng. Tập cận trên của C bao gồm tất cả các mẫu với giá trị của thuộc tính được mô tả không thể thuộc vào phân lớp C. Mô hình tập mờ không dốc về cực đại cục bộ bằng các thuật toán cây quyết định, và cũng giống như mô hình tập thô, chúng dùng để đối phó với những điều không chắc chắn tốt hơn bất kỳ một thuật toán nào khác. 11 1.4.2 Luật kết hợp (Association Rules) Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật KPDL là tập luật kết hợp tìm được. Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ ra quyết định. Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu. 1.4.3 Khai thác mẫu tuần tự (Sequential/ Temporal patterns) Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo cao. 1.4.4 Phân nhóm - đoạn (Clustering/ Segmentation) Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này, nhưng cũng có thể vừa thuộc nhóm khác. Không giống như phân lớp dữ liệu, phân nhóm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân nhóm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này bạn sẽ không thể biết kết quả các nhóm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các nhóm thu được. Phân nhóm còn được gọi là học không có giám sát (unsupervised learning). Phân nhóm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại 12 trang Web,  Ngoài ra phân nhóm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán KPDL khác. 1.4.5 Hồi quy (Regression) Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn như hồi quy tuyến tính. Tuy nhiên phương pháp mô hình hóa cũng có thể được sử dụng như cây quyết định. 1.4.6 Tổng hợp hóa (Summarization) Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật mô tả khái niệm và tổng hợp hóa thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: "Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận". 1.4.7 Mô hình hóa sự phụ thuộc (dependency modeling) Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức. Mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị), trong đó, các biến phụ thuộc bộ phận vào các biến khác. Và mức định lượng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật "nếu thì" - nếu tiền đề đúng thì kết luận đúng. Về nguyên tắc, cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề thường là nhóm các giá trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa, hệ thống có thể phát hiện các luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do người dùng chỉ ra trong kết luận. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy Bayes. Đó là đồ thị có hướng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết phụ thuộc giữa các nút đó. 13 1.4.8 Phát hiện sự biến đổi và độ lệch (Change and deviation detection) Tập trung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu thời gian. Độ lệch theo nhóm là sự khác nhau của dữ liệu trong hai tập con dữ liệu, ở đây xét cả trường hợp tập con dữ liệu này thuộc tập con kia. Nghĩa xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so với toàn bộ đối tượng không? Theo cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường sẽ được phát hiện. 1.5 Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ liệu thành các loại khác nhau. Cơ sở dữ liệu quan hệ (relational databases): là những CSDL được tổ chức theo mô hình quan hệ. Hiện nay, các hệ quản trị CSDL đều hỗ trợ mô hình này như: MS Access, MS SQL Server, Oracle, IBM DB2,... Cơ sở dữ liệu đa chiều (multidimention structures, data warehouse, data mart): còn được gọi là nhà kho dữ liệu, trong đó dữ liệu được chọn từ nhiều nguồn khác nhau và chứa những đặc tính lịch sử thông qua thuộc tính thời gian tường minh hoặc ngầm định. Cơ sở dữ liệu giao tác (transaction databases): là loại dữ liệu được sử dụng nhiều trong siêu thị, thương mại, ngân hàng,... Cơ sở dữ liệu quan hệ - hướng đối tượng (object relational databases): mô hình CSDL này là lai giữa mô hình hướng đối tượng và mô hình CSDL quan hệ. Cơ sở dữ liệu không gian và thời gian (spatial, temporal, and time - series data): chứa những thông tin về không gian địa lý hoặc thông tin theo thời gian. Cơ sở dữ liệu đa phương tiện (Multimedia database): là loại dữ liệu có nhiều trên mạng, bao gồm các loại như âm thanh, hình ảnh, video, văn bản và nhiều kiểu dữ liệu định dạng khác.