Tài liệu Khai phá dữ liệu và thuật toán khai phá luật kết hợp

ĐẠI HỌC QUỐC G IA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN THỊ LIÊN KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP C huyên ngành: Mã số: 1.01.01 Công nghệ thông tin LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: PGS. TS. Đoàn Văn Ban Hà Nội 2004 2 MỤC LỤC Trang bìa phụ............................................................................................................................................. 1 Lời cảm ơn ................................................................................. Error! Bookmark not defined. Mục lục ................................................................................................................................................................2 Danh mục các thuật ngữ ...........................................................................................................................4 Danh mục các bảng ......................................................................................................................................5 Danh mục các hình vẽ .................................................................................................................................6 Mở đầu .................................................................................................................................................................7 Chương 1 Tổng quan về khai phá dữ liệu ..............................................................................9 1.1. Truyền thống tổ chức và khai thác cơ sở dữ liệu .......................................................9 1.2. Các chiến lược xử lý và phân phát thông tin ............................................................. 10 1.3. Kho dữ liệu – Data Warehouse ......................................................................................... 13 1.4. quá trình phát hiện tri thức .................................................................................................. 16 1.4.1. Phát hiện tri thức........................................................................................................... 16 1.4.2. Các giai đoạn của quá trình phát hiện tri thức ............................................... 16 1.5. Khai phá dữ liệu ....................................................................................................................... 20 1.5.1. Kiến trúc của hệ thống khai phá dữ liệu ........................................................... 20 1.5.2. Quá trình khai phá dữ liệu ....................................................................................... 22 1.5.3. Nhiệm vụ khai phá dữ liệu ...................................................................................... 24 1.5.4. Các thành phần của thuật toán khai phá dữ liệu ........................................... 27 1.5.5. Một số phương pháp khai phá dữ liệu ............................................................... 28 1.6. Những ứng dụng của khai phá dữ liệu .......................................................................... 34 1.7. Một số thách thức trong ứng dụng và nghiên cứu kỹ thuật khai .. phá dữ liệu 35 3 1.7.1. Các vấn đề về cơ sở dữ liệu .................................................................................... 35 1.7.2. Một số vấn đề khác ...................................................................................................... 38 Chương 2 Khai phá luật kết hợp .............................................................................................. 40 2.1. Các khái niệm cơ sở ............................................................................................................... 40 2.2. Mô tả dữ liệu .............................................................................................................................. 44 2.3. Mô tả bài toán............................................................................................................................ 46 2.4. Độ phức tạp của thuật toán khai phá luật kết hợp ................................................... 48 2.5. Thuật toán Apriori................................................................................................................... 52 2.5.1. Khai phá tập mục thường xuyên [16] ................................................................ 52 2.5.2. Phát hiện luật kết hợp [16] ...................................................................................... 59 2.5.3. Cấu trúc dữ liệu cho thuật toán [9] ...................................................................... 61 2.6. Thuật toán FP_growth........................................................................................................... 62 2.6.1. Cây mẫu thường xuyên ............................................................................................. 64 2.6.2. Khai phá tập mục thường xuyên........................................................................... 69 2.7. Thuật toán Charm .................................................................................................................... 73 2.7.1. Tập mục thường xuyên đóng.................................................................................. 74 2.7.2. Sinh luật ............................................................................................................................ 79 2.7.3. Chi tiết thuật toán Charm ......................................................................................... 81 2.8. Tổng hợp một số thuật toán................................................................................................ 89 Chương 3 Cài đặt và thử nghiệ m ............................................................................................. 97 3.1. Cấu trúc tệp dữ liệu ................................................................................................................ 97 3.2. Xây dựng chương trình ......................................................................................................... 98 3.3. Kết quả thử nghiệm ............................................................................................................. 102 3.4. Nội dung một số lớp ............................................................................................................ 105 Kết luận ........................................................................................................................................................ 122 Tài liệu tham khảo ................................................................................................................................. 123 4 DANH MỤC CÁC THUẬT NGỮ Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt Association Kết hợp Bipartite Lưỡng phân Classification Phân lớp Closed Itemset Tập mục đóng Closed frequent Itemsets Tập mục thường xuyên đóng Closure operator Toán tử đóng Confidence Độ tin cậy Data mining Khai phá dữ liệu Data mining engine Mô tơ khai phá dữ liệu Data Warehouse Kho dữ liệu Frequent Thường xuyên Frequent pattern tree Cây mẫu thường xuyên Itemset Tập mục Knowledge Tri thức Rule Luật Support Độ hỗ trợ Transaction Giao tác 5 DANH MỤC CÁC BẢNG 2.1 Cơ sở dữ iệu D. ....................................................................................................................................... 44 2.2 Độ hỗ trợ của các tập mục. ........................................................................................................... 45 2.3 Các giao tác cơ sở dữ liệu. .............................................................................................................. 57 2.4 Các giao tác cơ sở dữ liệu. .............................................................................................................. 66 3.1 Thời gian thực hiện và số tập mục tìm đợc của 2 thuật toán Apriori và Charm. ..................................................................................................................................................................... 102 6 DANH MỤC CÁC HÌNH VẼ 1.1 Luồng dữ liệu trong một tổ chức. ...................................................................................................... 16 1.2 Các giai đoạn của quá trình phát hiện tri thức. ......................................................................... 18 1.3 Kiến trúc hệ thống khai phá dữ liệu. ................................................................................................ 22 1.4 Quá trình khai phá dữ liệu. ..................................................................................................................... 23 1.5 Kết quả phân lớp theo lân cận gần nhất. ....................................................................................... 25 1.6 Mẫu kết quả với nhiệm vụ phân cụm .............................................................................................. 26 1.7 Mẫu kết quả của phương pháp cây quyết định. ........................................................................ 30 1.8 Sơ đồ quá trình khai phá dữ liệu bằng mạng neuron ............................................................ 33 2.1 Các dạng biểu diễn khác nhau của cơ sở dữ liệu. ................................................................... 46 2.2 a) Cơ sở dữ liệu sách, b) Các tập mục thường xuyên và luật kết hợp .................... 49 2.3 Clique lưỡng phân cực đại ...................................................................................................................... 50 2.4 Độ phức tạp của việc khai phá. ........................................................................................................... 50 2.5 Diễn biến của thuật toán Apriori........................................................................................................ 57 2.6 Một cây mẫu thường xuyên. .................................................................................................................. 64 2.7 Quá trình xây dựng FP_tree................................................................................................................... 66 2.8 Cây FP_tree của cơ sở dữ liệu trong bảng 2.1. ......................................................................... 67 2.9 Các FP_Tree phụ thuộc. ........................................................................................................................ 69 2.10 a) Kết nối Galois, b) Round – Trip ................................................................................................ 74 2.11 Dàn và các tập mục thường xuyên. ................................................................................................ 75 2.12 Dàn khái niệm thường xuyên ........................................................................................................... 76 2.13 Dàn đầy đủ các tập mục của cơ sở dữ liệu hình 2.2 a. ...................................................... 80 2.14 Các tính chất cơ bản của các tập mục và tập định danh. ................................................. 81 2.15 a) CHARM theo thứ tự từ điển, b) CHARM theo chiều tăng của độ hỗ trợ .... 83 3.1 Màn hình sau khi khởi động chương trình. ................................................................................ 98 3.2 Trang Tìm tập mục thường xuyên. ................................................................................................... 99 3.3 Trang Tìm luật kết hợp. ............................................................................................................................ 99 3.4 Kết quả khai phá tập mục thường xuyên của thuật toán Apriori. .............................. 100 3.5 Kết quả khai phá tập mục thường xuyên của thuật toán Charm. ............................... 101 3.6 Kết quả khai phá luật. ............................................................................................................................. 102 3.7 Biểu đồ thời gian thực hiện của 2 thuật toán Aproiri và Charm. ............................. 103 7 MỞ ĐẦU Sự phát triển mạnh mẽ của công nghệ phần cứng đã tạo nên các máy tính có bộ xử lý tốc độ cao, bộ nhớ dung lượng lớn và với sự phát triển không ngừng của các hệ thống viễn thông đã tạo điều kiện cho nhiều hệ thống thông tin phục vụ việc tự động hóa mọi hoạt động nghiệp vụ, sản xuất và kinh doanh được triển khai với tốc độ tăng trưởng vượt bậc. Với sự phát triển như thế tạo nên những dòng dữ liệu khổng lồ, tạo thành hiện tượng “bùng nổ” thông tin. Nhiều hệ quản trị cơ sở dữ liệu mạnh với công cụ phong phú đã giúp con người khai thác có hiệu quả nguồn tài nguyên dữ liệu lớn nói trên. Cùng với tính năng khai thác có tính chất tác nghiệp, việc khai thác các 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 lớn trong nhiều lĩnh vực. Với lượng thông tin ngày càng phát triển nhanh như vậy thì việc rút ra những “tri thức” có ích để hỗ trợ cho việc ra quyết định là một điều cần thiết. Từ nhu cầu đó, trong những năm gần đây đã phát triển mạnh mẽ một lĩnh vực nghiên về tổ chức các kho dữ liệu, các hệ trợ giúp quyết định, các phương pháp phát hiện tri thức và khai phá dữ liệu. Trong đó, khai phá dữ liệu và phát hiện tri thức đã trở thành một lĩnh vực nghiên cứu sôi động, thu hút sự quan tâm của rất nhiều người trên nhiều lĩnh vực như: hệ cơ sở dữ liệu, thống kê, nhận dạng, học máy, trí tuệ nhân tạo, ... Quá trình phát hiện tri thức gồm nhiều giai đoạn trong đó giai đoạn khai phá dữ liệu là chủ yếu nhất. Giai đoạn khai phá dữ liệu được thực hiện sau các khâu tinh lọc và tiền xử lý dữ liệu nhằm tìm ra các mẫu được xem là đáng quan tâm, mới được coi là tri thức và tri thức có ích khi nó đạt được mục đích nào đó của hệ thống hoặc của người dùng. Các kỹ thuật khai phá dữ liệu được chia làm ba mảng cơ bản: phân lớp/phâncụm, luật kết hợp, khai phá chuỗi. 8 Một trong các nội dung cơ bản trong khai phá dữ liệu là phát hiện luật kết hợp, được đề xuất lần đầu bởi Rakesh Agrawal, Tomasz Imielinski, Anin Sawami [15] vào năm 1993. Những nghiên cứu này nhằm tìm ra các tập mục thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật có ảnh hưởng của một tập mục đến sự xuất hiện của một (hoặc một tập) mục. Phương pháp nghiên cứu chính của luận văn là tổng hợp các kết quả dựa trên các báo cáo khoa học trong một số hội nghị quốc tế và các bài báo chuyên ngành hoặc phổ biến trên Internet. Luận văn trình bày một số vấn đề về phát hiện tri thức và một số thuật toán khai phá luật kết hợp cũng như những kiến thức liên quan đến vấn đề này. Nội dung luận văn gồm: mở đầu, ba chương và phần kết luận. Chương 1 Tổng quan về khai phá dữ liệu: giới thiệu tổng quan về tổ chức, phân phát thông tin, các giai đoạn của quá trình phát hiện tri thức, các phương pháp, kỹ thuật khai phá dữ liệu. Chương 2 Khai phá luật kết hợp. Chương này trình bày chi tiết về các kiến thức liên quan đến khai phá luật kết hợp, một số thuật toán tiêu biểu về khai phá luật kết hợp cũng như đánh giá độ phức tạp của các thuật toán này. Chương 3 Cài đặt và thử nghiệm. Trình bày kết quả xây dựng chương trình thử nghiệm khai phá luật kết hợp trên một số cơ sở dữ liệu. Những kết quả trong luận văn là bước đầu tìm hiểu và tổng hợp các kết quả đã có về khai phá dữ liệu nói chung và khai phá luật kết hợp nói riêng. Phần cài đặt và thử nghiệm mô tả lại các thuật toán đã có, chưa có điều kiện để ứng dụng vào thực tế. Những kết quả này là cơ sở để tác giả tiếp tục nghiên cứu sâu hơn sau này. 9 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Có rất nhiều cách quan niệm về khai phá dữ liệu (Data mining) ý chung có thể hiểu là quá trình tìm kiếm, khám phá, xem xét dữ liệu dưới nhiều mức độ nhằm tìm ra mối liên hệ giữa các thành phần dữ liệu và phát hiện ra những xu hướng, hình mẫu và những kinh nghiệm quá khứ tiềm ẩn trong kho dữ liệu vì vậy rất phù hợp với mục đích phân tích dữ liệu hỗ trợ cho công việc điều hành và ra quyết định [1]. Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm được những mẫu thông tin chưa biết và tiềm ẩn từ kho dữ liệu lớn, phức hợp. Để thực hiện khai phá hiệu quả thì phải biểu diễn dữ liệu dưới dạng trực quan (Data Visualization). Khi phân tích dữ liệu người ta không những muốn dữ liệu là những con số mà còn muốn thấy hình ảnh của dữ liệu để phát hiện ra những thông tin mới, những xu hướng phát triển của đối tượng mà dữ liệu mô tả. 1.1. TRUYỀN THỐNG TỔ CHỨC VÀ KHAI THÁC CƠ SỞ DỮ LIỆU Việc dùng các phương tiện tin học để tổ chức và khai thác cơ sở dữ liệu (CSDL) đã được phát triển từ những năm 60. Từ đó cho đến nay, rất nhiều cơ sở dữ liệu đã được tổ chức, phát triển và khai thác ở mọi quy mô và ở khắp các lĩnh vực hoạt động của con người và xã hội. Theo như đánh giá cho thấy, lượng thông tin trên thế giới cứ sau 20 tháng lại tăng gấp đôi. Kích thước và số lượng cơ sở dữ liệu thậm chí còn tăng nhanh hơn. Với sự phát triển mạnh mẽ của công nghệ phần cứng máy đã tạo ra các máy tính có bộ xử lý tốc độ cao, các bộ nhớ có dung lượng lớn và cùng với hệ thống mạng viễn thông người ta đã xây dựng các hệ thống thông tin nhằm tự động hóa mọi hoạt động kinh doanh của mình. Điều này tạo ra một dòng dữ liệu tăng lên không ngừng 10 vì ngay từ các giao dịch đơn giản nhất như một cuộc gọi điện thoại, sử dụng thẻ tín dụng,… đều được ghi vào máy tính. Số này đã trở nên khổng lồ bao gồm các cơ sở dữ liệu cực lớn cỡ gigabytes và thậm chí terabytes lưu trữ các dữ liệu kinh doanh như thông tin khách hàng, dữ liệu lịch sử các giao dịch, dữ liệu bán hàng, các tài khoản, các khoản vay, sử dụng vốn, … Nhiều hệ quản trị cơ sở dữ liệu mạnh với các công cụ phong phú và thuận tiện đã giúp cho con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình cơ sở dữ liệu quan hệ và ngôn ngữ truy vấn chuẩn (SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác cơ sở dữ liệu đó. Cho đến nay, không một tổ chức kinh tế nào là không sử dụng hệ quản trị cơ sở dữ liệu và các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các cơ sở dữ liệu phục vụ cho hoạt động nghiệp vụ của mình. 1.2. CÁC CHIẾN LƯỢC XỬ LÝ VÀ PHÂN PHÁT THÔNG TIN Chúng ta đang sống trong thời đại của nền kinh tế trí thức. Mọi hoạt động của chúng ta muốn đạt hiệu quả cao, giành được thắng lợi trong thế cạnh tranh gay gắt thì nhất thiết phải có những phương pháp để có được những thông tin, tri thức cần thiết một cách nhanh và chính xác. Việc áp dụng công nghệ thông tin vào thực tiễn sản xuất nghiệp vụ đã mang lại những hiệu quả và lợi ích to lớn. Công nghệ ngày càng được phát triển, hoàn thiện hơn để đáp ứng những yêu cầu ngày càng cao của thực tế nghiên cứu, quản lý sản xuất và nghiệp vụ. Sự mở rộng qui mô áp dụng từ những ứng dụng đơn lẻ đến các hệ thống thông tin cỡ lớn đã dẫn đến những thành công vượt bậc trong nghiệp vụ. Các hệ thống thông tin từ chỗ chỉ giải quyết những xử lý công việc hàng ngày nay đã tiến tới đáp ứng được những yêu cầu thông tin ở mức độ cao hơn. Các nhà quản lý điều hành không những biết được công việc đang diễn ra như thế nào mà còn biết cái gì sẽ xảy ra sau 11 đó, có nghĩa là thông tin mang tính phân tích và hệ thống thông tin có khả năng hỗ trợ quyết định. Tuy nhiên việc xây dựng một hệ thống như thế gặp phải một số hạn chế về mặt kỹ thuật, đặc biệt là khi kích thước cũng như độ phức tạp của môi trường thông tin tăng nhanh. Những hệ thống thông tin xây dựng theo phương pháp truyền thống không làm hài lòng người sử dụng và các nhà quản lý hệ thống thông tin. Những mục tiêu nêu trên không dễ gì đạt được bởi vì dữ liệu ngày một nhiều, lưu trữ phân tán ở nhiều dạng không tương thích với nhau, thậm chí còn ở những dạng phi cấu trúc. Nhiều hệ cơ sở dữ liệu đã được xây dựng không tương thích với nhau và không tương thích với những hệ thông tin mới được xây dựng. Nhiều khách hàng không thoả mãn với những hệ thống thông tin hiện thời. Internet đã mở ra nhiều khả năng và triển vọng cho các doanh nghiệp, cung cấp cho chúng ta lượng thông tin phong phú, rất cần thiết cho các hoạt động của chúng ta. WWW cung cấp nhiều thông tin về mọi lĩnh vực của xã hội loài người, từ các công trình nghiên cứu, kết quả học tập, thông tin quảng cáo, du lịch, các loại trò chơi giải trí, thương mại điện tử, v.v... Rất nhiều hoạt động của chúng ta có thể thực hiện được thông qua Internet. Tuy nhiên, một vấn đề đặt ra là làm thế nào để tổ chức, khai thác được những khối lượng dữ liệu khổng lồ và đa dạng đó được? Về phía người sử dụng, các khó khăn gặp phải thường là 1. “Không thể tìm thấy dữ liệu cần thiết”  Dữ liệu rải rác ở rất nhiều hệ thống với các giao diện và công cụ khác nhau, khiến tốn nhiều thời gian chuyển từ hệ thống này sang hệ thống khác. 12  Có thể có nhiều nguồn thông tin đáp ứng được đòi hỏi, nhưng chúng lại có những khác biệt và rất khó phát hiện thông tin nào là đúng. 2. “Không thể lấy ra được dữ liệu cần thiết”  Thường xuyên phải có chuyên gia trợ giúp, dẫn đến công việc dồn lại.  Có những loại thông tin không thể lấy ra được nếu không mở rộng khả năng làm việc của hệ thống có sẵn. 3. “Không thể hiểu dữ liệu tìm thấy”  Mô tả dữ liệu nghèo nàn và thường xa rời với các thuật ngữ nghiệp vụ quen thuộc. 4. “Không thể sử dụng được dữ liệu tìm thấy”  Kết quả thường không đáp ứng về bản chất dữ liệu và thời gian tìm kiếm.  Dữ liệu phải chuyển đổi bằng tay vào môi trường làm việc của người sử dụng. Những vấn đề về hệ thống thông tin: 1. “Phát triển các chương trình khác nhau là không đơn giản”  Một chức năng được thể hiện ở rất nhiều chương trình, nhưng việc tổ chức và sử dụng lại nó là rất khó khăn do hạn chế về kỹ thuật.  Chuyển đổi dữ liệu từ các khuôn dạng tác nghiệp khác nhau để phù hợp với người sử dụng là rất khó khăn. 2. “Duy trì những chương trình này gặp rất nhiều vấn đề”  Một thay đổi ở một ứng dụng sẽ ảnh hưởng đến tất cả các ứng dụng khác có quan hệ.  Thông thường sự phụ thuộc lẫn nhau giữa các chương trình không rõ ràng hoặc là không xác định được.  Do sự phức tạp của công việc chuyển đổi cũng như toàn bộ quá trình bảo trì dẫn đến mã nguồn của các chương trình trở nên hết sức phức tạp. 13 3. “Khối lượng dữ liệu lưu trữ tăng rất nhanh”  Không kiểm soát được khả năng chồng chéo dữ liệu trong các môi trường thông tin dẫn đến khối lượng dữ liệu tăng nhanh. 4. “Quản trị dữ liệu phức tạp”  Thiếu những định nghĩa chuẩn, thống nhất về dữ liệu dẫn đến việc mất khả năng kiểm soát môi trường thông tin.  Một thành phần dữ liệu tồn tại ở nhiều nguồn khác nhau. Giải pháp cho tất cả các vấn đề nêu trên chính là việc xây dựng một kho chứa dữ liệu (Data Warehouse). 1.3. KHO DỮ LIỆU – DATA W AREHOUSE Theo John Ladley kỹ nghệ kho dữ liệu (Data Warehouse Technology) là tập các phương pháp, kỹ thuật và các công cụ có thể kết hợp, hỗ trợ nhau để cung cấp thông tin cho người sử dụng trên cơ sở tích hợp từ nhiều nguồn dữ liệu, nhiều môi trường khác nhau. Định nghĩa [4] kho dữ liệu (Data Warehouse - DW) là tuyển tập các cơ sở dữ liệu tích hợp, hướng chủ đề, được thiết kế để hỗ trợ cho chức năng trợ giúp quyết định, mà mỗi đơn vị dữ liệu đều liên quan tới một khoảng thời gian cụ thể. Kho dữ liệu thường rất lớn tới hàng trăm GB hay thậm chí hàng Terabyte. Kho dữ liệu được xây dựng để tiện lợi cho việc truy cập theo nhiều nguồn, nhiều kiểu dữ liệu khác nhau sao cho có thể kết hợp được cả những ứng dụng của các công nghệ hiện đại và kế thừa được từ những hệ thống đã có sẵn từ trước. Dữ liệu phát sinh từ các hoạt động hàng ngày và được thu thập xử lí để phục vụ công việc nghiệp vụ cụ thể của một tổ chức thường được gọi là dữ liệu tác nghiệp (operational data) và hoạt động thu thập xử lí 14 loại dữ liệu này được gọi là xử lí giao dịch trực tuyến (Online Transaction Processing - OLPT). Kho dữ liệu trái lại phục vụ cho việc phân tích với kết quả mang tính thông tin cao. Các hệ thống thông tin thu thập xử lí dữ liệu loại này còn gọi là hệ xử lí phân tích trực tuyến (OnLine Analytical Processing OLAP). Một kho dữ liệu có thể được coi là hệ thống thông tin với những thuộc tính sau: - Là một tập dữ liệu được thiết kế có nhiệm vụ phân tích, sử dụng các dữ liệu từ các ứng dụng khác nhau. - Hỗ trợ cho một số người dùng có liên quan với các thông tin liên quan. - Là dữ liệu chỉ đọc. - Nội dung của nó được cập nhật thường xuyên theo cách thêm thông tin. - Chứa các dữ liệu lịch sử và hiện tại cung cấp các thông tin để phát hiện các xu hướng của các hoạt động nghiệp vụ. - Chứa các bảng dữ liệu có kích thước lớn, phức hợp. - Những câu hỏi thường trả về một tập kết quả liên quan đến toàn bộ bảng và các liên kết nhiều bảng. Cấu trúc kho dữ liệu được xây dựng dựa trên hệ quản trị cơ sở dữ liệu quan hệ, có chức năng giống như kho lưu trữ thông tin trung tâm. Trong đó, dữ liệu tác nghiệp và phần xử lý được tách riêng khỏi quá trình xử lý kho dữ liệu. Kho lưu trữ trung tâm được bao quanh bởi các thành phần được thiết kế để làm cho kho dữ liệu có thể hoạt động, quản lý và truy nhập được từ người dùng đầu cuối cũng như từ các nguồn dữ liệu. 15 Dòng dữ liệu trong một tổ chức (cơ quan, xí nghiệp, công ty, v.v.) có thể mô tả khái quát như sau [4]: Kho dữ liệu tác nghiệp. Kho dữ liệu Ngân hàng dữ liệu (Dữ liệu hiện tại) (dữ liệu lịch sử ) Quầy dữ liệu (Data Mart) Kho dữ liệu cá nhân ( dữ liệu tóm tắt, dữ liệu lịch sử) Siêu DL (MetaData) Hình 1.1 Luồng dữ liệu trong một tổ chức. Dữ liệu cá nhân (Personal Data) không thuộc phạm vi quản lý của hệ quản trị kho dữ liệu. Nó chứa các thông tin được trích xuất ra từ các hệ thống dữ liệu tác nghiệp, kho dữ liệu và từ những kho dữ liệu cục bộ của những chủ đề liên quan bằng các phép gộp, tổng hợp hay xử lý bằng một cách nào đó. Để lấy được những thông tin có ích từ các kho dữ liệu khổng lồ, người ta sử dụng công nghệ khai phá dữ liệu. 16 1.4. QUÁ TRÌNH PHÁT HIỆN TRI THỨC Phát hiện tri thức trong các cơ sở dữ liệu là quá trình nhận biết những mẫu hoặc mô hình trong dữ liệu có các tính năng: hợp thức, mới, có ích và dễ hiểu. Mục đích của phát hiện tri thức là phát hiện những tri thức có ích tiềm ẩn trong tập cơ sở dữ liệu lớn mà trước đó chưa được phát hiện. Thực hiện quá trình đó gọi là quá trình phát hiện tri thức trong cơ sở dữ liệu [1]. 1.4.1. Phát hiện tri thức Như Jonh Naisbell đã nói “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Dữ liệu thường cho bởi các giá trị mô tả các sự kiện, hiện tượng cụ thể còn tri thức là gì? Có thể có những định nghĩa rõ ràng để phân biệt các khái niệm dữ liệu, thông tin, tri thức hay không? Khó mà định nghĩa chính xác nhưng phân biệt chúng trong những ngữ cảnh nhất định là rất cần thiết, và có thể làm được. Thông tin là một khái niệm rất rộng, khó có thể đưa ra một định nghĩa chính xác cho khái niệm này. Cũng không định nghĩa cho khái niệm tri thức cho dù chỉ hạn chế trong phạm vi những những tri thức được chiết suất từ các cơ sở dữ liệu. Tuy nhiên, có thể hiểu đơn giản tri thức là một biểu thức trong một ngôn ngữ nào đó diễn tả một (hoặc nhiều) mối quan hệ giữa các thuộc tính trong các dữ liệu đó. Các ngôn ngữ thường được sử dụng để biểu diễn tri thức là các khung, cây và đồ thị, các luật, các công thức trong ngôn ngữ logic mệnh đề hoặc tân từ cấp một, các hệ thống phương trình... Ví dụ như các luật mô tả các thuộc tính của dữ liệu, các mẫu thường xuyên xảy ra, các nhóm đối tượng trong cơ sở dữ liệu, v.v... 1.4.2. Các giai đoạn của quá trình phát hiện tri thức Phát hiện tri thức là một quá trình truy xuất tri thức từ cơ sở dữ liệu. Tri thức mà ta nói ở đây thường được sử dụng để giải quyết một loạt nhiệm vụ 17 trong những lĩnh vực nhất định. Do đó việc phát hiện tri thức không phải là phát hiện mọi tri thức bất kỳ mà phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là sự tương tác của con người với công cụ tin học qua các giai đoạn sau: Giai đoạn 1: xác định và định nghĩa vấn đề: tìm hiểu lĩnh vực ứng dụng và nhiệm vụ đặt ra, xác định các tri thức đã có và mục tiêu của người dùng. Tạo lập tập dữ liệu đích bằng cách chọn từ cơ sở dữ liệu một tập giá trị biến và các mẫu được quan tâm, trên đó ta thực hiện quá trình phát hiện tri thức. Giai đoạn 2: thu thập và tiền xử lý dữ liệu : bao gồm làm sạch dữ liệu, thu gọn và rút bớt số chiều của dữ liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức. Giai đoạn 3: khai phá dữ liệu, bao gồm: chọn nhiệm vụ khai phá dữ liệu dựa vào mục tiêu của quá trình phát hiện tri thức: xếp loại, phân nhóm hay hồi quy... 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 để tìm các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng (cây quyết định, luật dẫn xuất, biểu thức hồi quy, ...). Giai đoạn 4: giải thích các mẫu và đánh giá kết quả đã được khai phá ở giai đoạn 3. 18 Giai đoạn 5: sử dụng các tri thức đã được phát hiện. 1 Xác định và định nghĩa vấn đề 2 Thu thập và tiền xử lý dữ liệu Khai phá dữ liệu 3 4 Giải thích kết quả và đánh giá 5 Sử dụng tri thức được phát hiện Hình 1.2 Các giai đoạn của quá trình phát hiện tri thức. Lý luận và thực tiễn thực hiện các quá trình phát hiện tri thức mà ta xét ở đây là sự tiếp thu, sử dụng và phát triển nhiều thành tựu và công cụ của các lĩnh vực đã phát triển trước đó như: lý thuyết nhận dạng, hệ chuyên gia, trí tuệ nhân tạo, .... Nhưng đặc điểm cơ bản của lý luận về phát hiện tri thức là phát hiện tri thức trực tiếp từ dữ liệu, do đặc điểm đó mà nó có những điểm mới, phân biệt với các ngành đã có từ trước. Ví dụ như hệ chuyên gia thì cơ sở tri thức được hình thành từ kinh nghiệm và kiến thức của các chuyên gia là chủ yếu, với nhiều bài toán nhận dạng thì tập các dạng mẫu thường là cho trước,... Còn đối với lý thuyết phát hiện tri thức; các dạng mẫu, các giả thuyết được phát hiện từ việc khai phá các kho dữ liệu. Nếu phát hiện tri thức là toàn bộ quá trình truy xuất tri thức từ cơ sở dữ liệu thì khai phá dữ liệu là giai đoạn chủ yếu của quá trình đó [1]. Như trên đã 19 trình bày, trong quá trình phát hiện tri thức, khâu khai phá dữ liệu được thực hiện sau các khâu tinh lọc và tiền xử lý dữ liệu, tức là việc khai phá để tìm ra các mẫu có ý nghĩa được tiến hành trên tập dữ liệu có hy vọng là sẽ phù hợp với từng nhiệm vụ khai phá chứ không phải khai phá hết dữ liệu với một thời gian đủ dài để lấy được một mẫu không thực sự có ích như khái niệm thống kê trước đây. Vì vậy, khai phá dữ liệu 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 đó. Ví dụ ta có mô hình là một luật kết hợp thì mẫu là các yếu tố tham gia cùng với độ hỗ trợ, độ tin cậy trong các luật tương ứng. Mặc dù các mẫu có thể được trích lọc từ bất kỳ cơ sở dữ liệu nào, nhưng chỉ có những mẫu được xem là đáng quan tâm xét theo một phương diện nào đó mới được coi là tri thức. Các mẫu là đáng quan tâm nếu chúng mới, có lợi, đáng được xem xét. Ta có thể coi khai phá dữ liệu giống như một quá trình phát hiện các mẫu mới phục vụ cho việc phân tích và phát hiện tri thức. Khai phá dữ liệu đượ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 khai phá dữ liệu phải phát hiện được những người có thu nhập thấp và nợ nhiều là những người có mức rủi ro cao, ngoài ra kỹ thuật khai phá dữ liệu cũng 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ụ 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, khai phá dữ liệu sử dụng các thông tin trong quá khứ. Khai phá dữ liệu được xây dựng dựa trên việc sử dụng các thuật toán mới, được định hướng theo nhu 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 hiện đang được nghiên cứu và sử dụng bao gồm: cây quyết định, mạng nơ ron, phương pháp láng giềng gần nhất, các luật suy diễn, ... 20 Khai phá dữ liệu không thuộc 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. Có thể xem khai phá dữ liệu ngày nay đang ở trạng thái giống như việc quản trị dữ liệu vào những năm 60, khi mà các ứng dụng quản trị dữ liệu đều không tuân theo một nguyên tắc chung nào cho đến khi mô hình dữ liệu quan hệ ra đời cùng với sức mạnh của ngôn ngữ truy vấn đã thúc đẩy việc phát triển các ứng dụng quản trị dữ liệu mạnh mẽ. Tuy vậy, hiện nay trên thế giới đã có rất nhiều ngành công nghiệp sử dụng kỹ thuật khai phá dữ liệu để phục vụ cho hoạt động nghiệp vụ của mình và bước đầu thành công như ngành tài chính, y học, hóa học, bảo hiểm, sản xuất, giao thông... Các kết quả đạt được cho thấy mặc dù kỹ thuật khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm, nhưng với những tri thức mà con người chưa cung cấp được thì khai phá dữ liệu có một tiềm năng to lớn trong việc tạo ra những thuận lợi đáng kể trong các hoạt động nghiệp vụ, sản xuất và kinh doanh. 1.5. KHAI PHÁ DỮ LIỆU Khai phá dữ liệu là một bước trong quá trình phát hiện tri thức. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. 1.5.1. Kiến trúc của hệ thống khai phá dữ liệu Khai phá dữ liệu là một bước trong quá trình phát hiện tri thức từ số lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu, kho dữ liệu hoặc các nơi lưu trữ khác. Bước này có thể tương tác lẫn nhau giữa người sử dụng hoặc cơ sở