Tài liệu Khai phá dữ liệu dùng luật kết hợp

§¹i §¹i häc häc quèc quèc gia gia Hµ Hµ néi néi Tr-êng ®¹i häc c«ng Tr-êng ®¹i häc c«ng nghÖ nghÖ Nguyễn Ngọc Long NGUYỄN NGỌC LONG KHAI PHÁ DỮ LIỆU DỮKẾT LIỆU SỬ KHAI DỤNGPHÁ LUẬT HỢP SỬ DỤNG LUẬT KẾT HỢP Ngành: Công Nghệ Thông Tin Mã số: 1.01.10 LUẬN VĂN VĂN THẠC THẠC SỸ SỸ LUẬN HÀ NỘI – 2005 HÀ NỘI – 2005 1 1.1.1.1.1 Hà nội 03/2004 §¹i häc quèc gia Hµ néi §¹i häc quèc gia Hµ néi Tr-êng ®¹i häc c«ng nghÖ Tr-êng ®¹i häc c«ng nghÖ Nguyễn Ngọc Long NGUYỄN NGỌC LONG KHAIPHÁ PHÁDỮ DỮLIỆU LIỆU KHAI SỬDỤNG DỤNGLUẬT LUẬTKẾT KẾTHỢP HỢP SỬ Ngành: Công Nghệ Thông Tin Mã số: 1.01.10 LUẬN VĂN THẠC SỸ LUẬN VĂN THẠC SỸ Người hướng dẫn khoa học: PGS. TS. Vũ Đức Thi HÀ NỘI – 2005 HÀ NỘI – 2005 2 1.1.1.1.2 Hà nội 03/2004 MỤC LỤC TÓM TẮT ......................................................................................................................... 2 MỞ ĐẦU .......................................................................................................................... 7 CHƢƠNG 1 TỔNG QUAN VỀ TỔ CHỨC - KHAI THÁC CSDL VÀ PHÁT HIỆN TRI THỨC ............................................................................................................................. 10 1.1 Nhu cầu, cách nhìn nhận và thực hiện trong các hệ CSDL truyền thống ............... 10 1.2 Các vấn đề hạn chế và mục tiêu cần có đƣợc ........................................................ 11 1.3 Tìm kiếm bƣớc phát triển mới trong tổ chức khai thác CSDL............................... 11 1.4 Quá trình phát hiện tri thức .................................................................................. 15 1.4.1 Phát hiện tri thức .............................................................................................. 15 1.4.2 Các giai đoạn của quá trình phát hiện tri thức ................................................... 15 CHƢƠNG 2 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ................................................... 18 2.1 Mục tiêu của khai phá dữ liệu. ............................................................................. 18 2.2 Các quá trình khai phá dữ liệu .............................................................................. 19 2.3 Các công việc chính của khai phá dữ liệu ............................................................. 20 2.4 Kiến trúc của hệ thống khai phá dữ liệu ............................................................... 22 2.5 Các thành phần của giải thuật khai phá dữ liệu ..................................................... 23 2.6 Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng .................................................... 24 2.7 Các ứng dụng của khai phá dữ liệu....................................................................... 25 2.8 Một số phƣơng pháp khai phá dữ liệu phổ biến .................................................... 26 2.8.1. Phƣơng pháp quy nạp (induction)..................................................................... 26 2.8.2. Cây quyết định và luật ..................................................................................... 26 2.8.3. Phát hiện các luật kết hợp................................................................................. 28 2.8.4. Phân nhóm và phân đoạn (Clasterring and Segmentation)................................ 29 2.8.5. Các phƣơng pháp dựa trên mẫu ........................................................................ 30 2.8.6. Mô hình phụ thuộc dựa trên đồ thị xác xuất ...................................................... 30 2.8.7. Mô hình học quan hệ........................................................................................ 30 2.8.8. Khai phá dữ liệu văn bản .................................................................................. 30 2.8.9. Mạng neuron .................................................................................................... 31 2.8.10. Giải thuật di truyền .......................................................................................... 32 2.9 Nhìn nhận và đánh giá chung. .............................................................................. 32 CHƢƠNG 3 KHAI PHÁ DỮ LIỆU SỬ DỤNG LUẬT KẾT HỢP .................................. 35 3.1. Luật kết hợp......................................................................................................... 35 3.1.1. Bài toán ........................................................................................................... 35 3.1.2. Các khái niệm cơ sở ......................................................................................... 37 3.1.3. Một số tính chất của tập mục phổ biến và luật kết hợp...................................... 40 3.1.4. Các loại luật kết hợp ........................................................................................ 43 3.2. Khai phá luật kết hợp đơn chiều, đơn mức, luật kết hợp Boolean ......................... 43 3.2.1. Thuật toán Apriori ........................................................................................... 43 3.2.2. Phát triển thuật toán Apriori ............................................................................. 51 3.2.3. Thuật toán sinh các luật kết hợp từ tập mục phổ biến. ..................................... 55 3.2.4. Khai phá tập mục phổ biến không sinh các ứng cử ........................................... 59 3.3. Khai phá luật kết hợp định lƣợng ......................................................................... 68 3.4. Khai phá luật kết hợp đa mức ............................................................................... 70 3.4.1. Luật kết hợp đa mức ........................................................................................ 70 3.4.2. Các cách tiếp cận khai phá luật kết hợp đa mức ................................................ 72 3.5. Khai phá luật kết hợp đóng .................................................................................. 76 3.5.1. Khắc phục hạn chế của thuật toán Apriori ........................................................ 76 Formatted: Font: 20 pt, Bold Formatted: Normal, Centered Formatted: Font: 12 pt, Bold 3.5.2. Tập mục phổ biến đóng .................................................................................... 76 3.5.3. Sinh luật........................................................................................................... 80 3.5.4. Thuật toán Charm ............................................................................................ 81 CHƢƠNG 4 THỬ NGHIỆM KHAI PHÁ LUẬT KẾT HỢP ........................................... 87 4.1. Mô tả dữ liệu ....................................................................................................... 87 4.2. Xây dựng chƣơng trình ........................................................................................ 90 4.3. Kết quả thu đƣợc................................................................................................ 100 KẾT LUẬN................................................................................................................... 101 TÀI LIỆU THAM KHẢO ............................................................................................. 103 TÓM TẮT ............................................................................................................... 2 LỜI MỞ ĐẦU ........................................................................................................ 7 CHƢƠNG 1 TỔNG QUAN VỀ TỔ CHỨC - KHAI THÁC CSDL VÀ PHÁT HIỆN TRI THỨC ............................................................................................................ 10 1.1 Nhu cầu, cách nhìn nhận và thực hiện trong các hệ CSLD truyền thống...... 10 1.2 Các vấn đề hạn chế và mục tiêu cần có đƣợc .............................................. 11 1.3 Tìm kiếm bƣớc phát triển mới trong tổ chức khai thác CSDL ..................... 11 1.4 Quá trình phát hiện tri thức ......................................................................... 15 1.4.1 Phát hiện tri thức ..................................................................................... 15 1.4.2 Các giai đoạn của quá trình phát hiện tri thức .......................................... 15 CHƢƠNG 2 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ........................................ 18 2.1 Mục tiêu của khai phá dữ liệu. .................................................................... 18 2.2 Các quá trình khai phá dữ liệu .................................................................... 19 2.3 Các công việc chính của khai phá dữ liệu ................................................... 20 2.4 Kiến trúc của hệ thống khai phá dữ liệu ...................................................... 22 2.5 Các thành phần của giải thuật khai phá dữ liệu ........................................... 23 2.6 Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng .......................................... 24 2.7 Các ứng dụng của khai phá dữ liệu ............................................................. 25 2.8 Một số phƣơng pháp khai phá dữ liệu phổ biến ........................................... 26 2.8.1. Phƣơng pháp quy nạp (induction)............................................................ 26 2.8.2. Cây quyết định và luật ............................................................................. 26 2.8.3. Phát hiện các luật kết hợp ........................................................................ 28 2.8.4. Phân nhóm và phân đoạn (Clasterring and Segmentation) ...................... 29 2.8.5. Các phƣơng pháp dựa trên mẫu ............................................................... 30 2.8.6. Mô hình phụ thuộc dựa trên đồ thị xác xuất ............................................. 30 2.8.7. Mô hình học quan hệ ............................................................................... 30 2.8.8. Khai phá dữ liệu văn bản ......................................................................... 30 2.8.9. Mạng neuron ........................................................................................... 31 2.8.10. Giải thuật di truyền ................................................................................. 32 2.9 Nhìn nhận và đánh giá chung. ..................................................................... 32 CHƢƠNG 3 KHAI PHÁ DỮ LIỆU SỬ DỤNG LUẬT KẾT HỢP ........................ 35 3.1. Luật kết hợp................................................................................................ 35 3.1.1. Bài toán ................................................................................................... 35 3.1.2. Các khái niệm cơ sở ................................................................................ 37 3.1.3. Một số tính chất của tập mục phổ biến và luật kết hợp ............................ 40 3.1.4. Các loại luật kết hợp................................................................................ 43 3.2. Khai phá luật kết hợp đơn chiều, đơn mức, luật kết hợp Boolean ................ 43 3.2.1. Thuật toán Apriori ................................................................................... 43 3.2.2. Phát triển thuật toán Apriori .................................................................... 51 3.2.3. Thuật toán sinh các luật kết hợp từ tập mục phổ biến. ............................ 55 3.2.4. Khai phá tập mục phổ biến không sinh các ứng cử .................................. 59 3.3. Khai phá luật kết hợp định lƣợng ................................................................ 68 3.4. Khai phá luật kết hợp đa mức ..................................................................... 70 3.4.1. Luật kết hợp đa mức................................................................................ 70 3.4.2. Các cách tiếp cận khai phá luật kết hợp đa mức ....................................... 72 3.5. Khai phá luật kết hợp đóng ......................................................................... 75 3.5.1. Khắc phục hạn chế của thuật toán Apriori ............................................... 75 3.5.2. Tập mục phổ biến đóng ........................................................................... 75 3.5.3. Sinh luật .................................................................................................. 75 3.5.4. Thuật toán Charm.................................................................................... 75 CHƢƠNG 4 THỬ NGHIỆM KHAI PHÁ LUẬT KẾT HỢP ................................. 75 4.1. Mô tả dữ liệu .............................................................................................. 75 4.2. Xây dựng chƣơng trình ............................................................................... 75 KẾT LUẬN CỦA LUẬN VĂN............................................................................. 75 TÀI LIỆU THAM KHẢO ..................................................................................... 75 BẢNG CÁC KÝ HIỆU VIẾT TẮT Tên viết tắt Tên đầy đủ CSDL Cơ sở dữ liệu DL Dữ liệu DM Data mining HTTT Hệ thống thông tin KDD Knowledge discovery in database OLAP On-Line Analytical Processing 7 BẢNG MỤC LỤC CÁC HÌNH VẼ Hình 1.1: Kiến trúc kho dữ liệu 13 Hình 1.2 Quá trình phát hiện tri thức 14 Hình 2.1 Mẫu kết quả với nhiệm vụ phân nhóm 19 Hình 2.2 Kiến trúc hệ thống khai phá dữ liệu 20 Hình 2.3 Quá trình khai phá dữ liệu 21 Hình 2.4 Mô tả cây quyết định cho khái niệm chơi tennis 25 Hình 3.1 Cơ sở dữ liệu D 36 Hình 3.2 Độ hỗ trợ của các mục Hình 3.3 Độ hỗ trợ của các tập mục 36 36 Hình 3.4 Độ tin cậy của các luật 36 Hình 3.5 Cơ sở dữ liệu D minh họa cho thuật toán Apriori 42 Hình 3.6: Quá trình thực hiện thuật toán Apriori với độ hỗ trợ là 2/9 (2 lần ) 43 Hình 3.7 Cây băm 48 Hình 3.8: Sơ đồ quá trình khai phá bằng phân 49 Hình 3.9: CSDL các tác vụ D minh họa cho thuật toán FP-Growth 55 Hình 3.10: Bảng các mục phổ biến đã đƣợc sắp theo thứ tự 56 Hình 3.11: FP-Tree đƣợc xây dựng dần khi thêm các tác vụ T100, T200, T300 56 Hình 3.12: FP-Tree đƣợc xây dựng dần khi thêm các tác vụ T400, T500 57 Hình 3.13: Cây FP-Tree của CSDL 57 Hình 3.14: Thực hiện thuật toán FP-Growth với cây có chứa đƣờng đơn 60 Hình 3.15 Dữ liệu điều tra dân số 62 Hình 3.16- Mô tả khái niệm phân cấp của các mục 65 Hình 3.17 – Khai phá nhiều mức với độ hỗ trợ nhƣ nhau 66 Hình 3.18 – Khai phá nhiều mức với độ hỗ trợ khác nhau 67 Hình 3.19 – Khai phá nhiều mức với giảm độ hỗ trợ, lọc bởi mục đơn 68 Hình 3.20 – Khai phá nhiều mức với giảm độ hỗ trợ, lọc bởi k-mục 68 Hình 3.21: CSDL bán sách minh họa cho tập mục phổ biến đóng 70 Hình 3.22 Các tập mục phổ biến 73 Hình 3.23 Dàn các tập con đầy đủ cho CSDL hình 3.21 76 Hình 3.24 Thuật toán Charm theo thứ tự từ điển 77 8 LỜI MỞ ĐẦU Sự bùng nổ thông tin là một yếu tố lớn cho sự phát triển xã hội. Cùng với sự phát triển vƣợt bậc này là yêu cầu đòi hỏi ngày càng cao trong việc xử lý và tìm kiếm thông tin sao cho nhanh và đạt đƣợc hiệu quả tối ƣu nhất. Cùng với sự phát triển đó, công nghệ phần cứng với bộ xử lý tốc độ cao, ổ cứng, các thiết bị băng từ dung lƣợng lớn song hành cùng với sự phát triển không ngừng của thiết bị viễn thông đã và đang hỗ trợ đắc lực cho công cuộc phát triển thông tin. Tâm điểm hiện nay là các hệ thống khai thác thông tin phục vụ việc tự động hóa trong các lĩnh vực kinh doanh cũng nhƣ quản lý trong điều hành ra quyết định. Hiện tƣợng ―bùng nổ thông tin‖ và sự ra đời hàng loạt các 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 ra đời đã giúp con ngƣời khai thác hiệu quả hơn nguồn tài nguyên dữ liệu phức tạp này. Từ sự phát triển với tốc độ kinh ngạc của các HTTT, việc khai phá dữ liệu phục vụ cho các yêu cầu trợ giúp quyết định cao hơn, chính xác và nhanh chóng hơn ngày càng nhiều, có ý nghĩa ngày càng quan trọng và là yếu tố quyết định trong mọi lĩnh vực hoạt động kinh doanh và quản lý. Những thông tin bổ ích, những ―tri thức‖ thông minh và hiệu quả rút ra từ những nguồn dữ liệu phức tạp và rộng lớn đã trở thành yếu tố sống còn trong các hoạt động thƣờng ngày của từng tổ chức kinh doanh, quản lý. ―Khai phá dữ liệu‖ trở thành trung tâm của hàng loạt các nghiên cứu và thảo luận cực kỳ sôi động nhằm tìm kiếm và khám phá ra đƣợc nhiều cách thức, phƣơng pháp hiệu quả với mong muốn tìm ra đƣợc càng ngày càng nhiều các tri thức mới, quan trọng và bổ ích. Điểm qua tình hình phát triển thông tin những năm gần đây, ta có một loạt các lĩnh vực nghiên cứu về tổ chức kho dữ liệu (data ware house, information ware house), các hệ hỗ trợ quyết định (DSS) , các phƣơng pháp phát hiện tri thức và các phƣơng pháp khai phá dữ liệu (data mining). Xét trên khía cạnh về nhu cầu ở mức trung bình hay trong phạm vi nhỏ hẹp, các kho dữ liệu có thể giúp khai thác thông tin bằng các công cụ truy vấn và báo cáo cũng nhƣ đƣợc dùng để hỗ trợ phân tích Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 10 trực tuyến, kiểm định các giả thuyết. Tuy nhiên điều ngƣời ta thấy thiếu ở đây là vấn đề tri thức (thông tin thông minh), điều đó có nghĩa là nếu dữ liệu trong các kho dữ liệu đƣợc phân tích một cách thông minh thì chúng sẽ là nguồn tài nguyên vô giá. Việc tự động phân tích tìm kiếm những thông tin tiềm ẩn có giá trị, chƣa đƣợc phát hiện, những xu hƣớng phát triển và những yếu tố tác động lên chúng từ những dữ liệu khổng lồ có sẵn là việc thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database-KDD). Là sự kết hợp của nhiều thành tựu nghiên cứu trong mọi lĩnh vực của đời sông xã hội nhƣ lý thuyết nhận dạng, hệ chuyên gia, trí tuệ nhân tạo, phát hiện tri thức trong các CSDL là quá trình tìm ra tri thức tiềm ẩn, không biết trƣớc và tiềm năng có lợi từ dữ liệu trong các CSDL lớn. Bằng cách thức này, KDD có đƣợc sự toàn diện và đầy đủ trong cách tìm kiếm và xử lý thông tin một cách tiên tiến và hiệu quả. Với nhiều giai đoạn và nhiều phƣơng pháp cụ thể, KDD đƣợc tiến hành theo thứ tự và có bổ xung hỗ trợ lẫn nhau. Vai trò của KDD đƣợc đƣa vào hai mảng sau đây: - Xác định, định nghĩa vấn đề, tìm hiểu lĩnh vực ứng dụng, nhiệm vụ … - Tinh lọc và tiền xử lý, nhằm tìm ra các mẫu, các xu hƣớng có ý nghĩa từ các tập dữ liệu. Chỉ có các mẫu, các xu hƣớng đƣợc xem là đáng quan tâm (xét theo một khía cạnh nào đó) mới đƣợc coi là tri thức và tri thức là có ích khi nó có thể giúp đạt đƣợc mục đích của hệ thống hoặc ngƣời dùng. Khai phá dữ liệu (Data mining - DM) đƣợc coi nhƣ là giai đoạn quan trọng nhất của KDD. Tiến trình KDD bao gồm các bƣớc sau đâyđƣợc : Formatted: Bullets and Numbering 1. Phân lớp/phân cụm dữ liệu 2. Các luật kết hợp 3. Khai phá chuỗi. 4. Đánh giá Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 11 5. Sử dụng các tri thức có đƣợc. Luận văn sẽ khái quát trình bày khái quát một số vấn đề về phát hiện tri thức, khai phá dữ liệu và tập trung trình bàylàm rõ vấn đề khai phá luật kết hợp để khai thác các CSDL lớn.:. Luận văn gồm 4 chƣơng: Chƣơng 1: Tổng quan về tổ chức và khai thác CSDL : Phân tích và nhìn nhận lại các cách thức tổ chức và lƣu trữ CSDL truyền thống. Từ đó có nhận xét và đánh giá về nhu cầu thông tin trong bƣớc phát triển mtới. Trong chƣơng này cũng trình bày các giai đoạn của quá trình phát hiện tri thức, xem xét tới một kiến trúc mới về lƣu trữ CSDL Data warehouse cùng với việc sử dụng nó cho khai phá dữ liệu - một giai đoạn chủ yếu.của quá trình phát hiện tri thức. Chƣơng 2 : Tổng quan về khai phá dữ liệu: tổng quan về mục tiêu, nhiệm vụ và các quá trình khai phá dữ liệu. Nêu khái quát các vấn đề chính của khai phá dữ liệu, các phƣơng pháp, kỹ thuật khai phá dữ liệu chính, phổ biến. Chƣơng 3: Khai phá dữ liệu sử dụng luật kết hợp: chƣơng này trình bày chi tiết các vấn đề chính yếu của khai phá luật kết hợp: bài toán xuất phát, mô hình hình thức, các thuật toán điển hình của luật kết hợp giải quyết vấn đề khai phá dữ liệu. Chƣơng 4: Thử nghiệm khai phá luật kết hợp. Xây dựng ứng dụng ―Tìm hiểu nhu cầu môn học‖. Khai phá dữ liệu sử dụng luật kết hợp CHƢƠNG 1 TỔNG QUAN VỀ TỔ CHỨC - KHAI THÁC CSDL VÀ PHÁT HIỆN TRI THỨC 1.1 Nhu cầu, cách nhìn nhận và thực hiện trong các hệ CSLD CSDL truyền thống Trong tình hình phát triển CNTT nhƣ vũ bão hiện nay, trong hầu hết các hoạt động của mình, con ngƣời đều có nhu cầu đƣợc ―máy tính‖ hóa và mong muốn mọi thông tin của mình về mọi lĩnh vực công việc, giải trí … đều đƣợc lƣu trữ và mong muốn dễ dàng tìm lại đƣợc khi có nhu cầu cần thiết. Trong các tổ chức cũng vậy, nhu cầu này còn cao hơn rất nhiều và trở thành xu hƣớng chính, chủ đạo trong việc tin học hóa hoạt động của mình. Hòa theo xu hƣớng này, là hàng loạt các hệ thống CSDL đã đƣợ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. Nhu cầu ấy ngày càng lớn và tăng trƣởng với một tốc độ lớn mà không có loại hình nào sánh kịp. Với sự giúp sức của ngành công nghệ điện tử và mạng truyền thông. Nhu cầu trao đổi thông tin của con ngƣời càng trở nên dễ dàng hơn rất nhiều và khiến nó trở nên một trào lƣu và là công cụ hữu ích để con ngƣời có thể chia sẻ thông tin với nhau. Với sự giúp sức của công nghệ, việc trao đổi này gần nhƣ càng ngày càng không có giới hạn. Khi lƣợng thông tin nhiều và trở nên lớn mạnh. Ngƣời ta hiểu đƣợc rằng ai nắm giữ đƣợc nhiều thông tin hơn ngƣời ấy sẽ trở thành thủ lĩnh. Chính điều ấy đã thúc đẩy việc tăng lên không ngừng của thông tin và việc các tổ chức dần đƣa các hoạt động kinh doanh, quyết định của mình dựa trên việc phân tích các thông tin đã trở thành phổ biến và quá quen thuộc. Nhiều hệ quản trị 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ả nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 13 và ngôn ngữ vấn đáp (SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác các CSDL đó. Cho đến nay, không một tổ chức kinh tế nào là không sử dụng các hệ thống quản trị CSDL và hệ thống báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các CSDL phục vụ cho hoạt động tác nghiệp của mình. 1.2 Các vấn đề hạn chế và mục tiêu cần có đƣợc Với các cách thực hiện nhƣ vậy, hệ thống thông tin có đƣợc trong các tổ chức hầu nhƣ chỉ mang tính chất lƣu trữ chứ chƣa có đƣợc cái mà ngƣời ta gọi là thông tin ―thông minh‖. Khi có nhu cầu về thông tin, hầu hết các hệ thống này chỉ hỗ trợ đƣợc các công việc tra cứu chứ không hề hỗ trợ đƣợc việc đánh giá, nhìn nhận một cách khoa học. Các vấn đề này lại chủ yếu mang tính chất chủ quan và do trình độ năng lực của chính những con ngƣời trong các tổ chức này. Trong khi vấn đề của tổ chức lại không thể phụ thuộc yếu tố con ngƣời. Điều này khiến các nhà tổ chức quản lý kinh doanh mong muốn có đƣợc các thông tin quan trọng và hữu ích một cách tự động từ trong các hệ thống thông tin CSDL lớn chứ không theo cách đánh giá chủ quan của một số cá nhân. Để có đƣợc điều này, cần có nhiều cách khám phá mới, cách nhìn nhận khác và tiến bộ hơn nhiều. 1.3 Tìm kiếm bƣớc phát triển mới trong tổ chức khai thác CSDL Sự phát triển kinh ngạc của công nghệ phần cứng máy tính trong 3 thập kỷ qua tạo cho máy tính có sức mạnh lớn. Điều đó cho phép tạo ra số lƣợng khổng lồ các CSDL và thông tin đƣợc cất giữ để quản lý kinh doanh, tìm thông tin, phân tích dữ liệu. Ngày nay dữ liệu có thể đƣợc lƣu trữ trong nhiều kiểu khác nhau. Một kiến trúc CSDL gần đây đã nổi bật lên đó là kho dữ liệu (data warehowse), nó lƣu dữ liệu từ nhiều nguồn khác nhau, tổ chức thống nhất để có thể tạo ra quyết định. Công nghệ kho dữ liệu bao gồm: làm sạch dữ liệu, tích hợp dữ liệu, phân tích trực tuyến (OLAP- Online analytical processingthuật ngữ tiếng Anh ),… đó là những kỹ thuật phân tích với chức năng nhƣ là tóm tắt, hợp nhất, tập hợp,… để có thể xem thông Khai phá dữ liệu sử dụng luật kết hợp Formatted: Default Paragraph Font, Font: Times New Roman, 13 pt, No underline, Font color: Auto Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 14 tin từ các góc độ khác nhau. Các công cụ OLAP hỗ trợ phân tích đa chiều và tạo ra quyết định, thêm vào đó là công cụ phân tích dữ liệu đòi hỏi phân tích sâu nhƣ phân lớp dữ liệu, phân nhóm, tìm các đặc tính của dữ liệu.u… Bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công trong kinh doanh không còn là năng suất của các hệ thông tin nữa mà là tính linh hoạt sẵn sàng đáp ứng lại yêu cầu trong thức tế, CSDL cần đem lại những tri thức hơn là chính những dữ liệu đó. Các quyết định cần phải chính xác, càng nhanh càng tốt trong hệ thống CSDL ngày càng lớn, mà các mô hình CSDL truyền thống và ngôn ngữ SQL cho thấy không đáp ứng đƣợc điều này. Để lấy đƣợc những thông tin mang tính tri thức trong khối dữ liệu khổng lồ này ngƣời ta đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập hợp các CSDL ổn định, có chất lƣợng đƣợc sử dụng riêng cho một vài mục đích nào đó. Các kỹ thuật đó đƣợc gọi là tạo kho dữ liệu (data warehousing) v và môi trƣờng các dữ liệu đó đƣợc gọi là các kho dữ liệu (data warehouse). Định nghĩa data warehouse : Có thể định nghĩa kho dữ liệu nhƣ sau: ―Một kho dữ liệu là một tập hợp dữ liệu tích hợp, hƣớng chủ đề có tính ổn định (?? ổn định rồi lại thay đổi là thế nào?), có thể thay đổi theo thời gian nhằm hỗ trợ cho việc tạo ra quyết định‖. Một kho dữ liệu bao gồm: - - Một hoặc nhiều công cụ để chiết truy xuấtkết xuất dữ liệu từ bất cứ dạng cấu trúc dữ liệu nào. - Cơ sở dữ liệu tích hợp hƣớng chủ đề, ổn định, đƣợc tổng hợp từ các dữ liệu bằng cách lập các bảng dữ liệu. Đặc tính - Là một cơ sở 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ốnhiều ngƣời dùng, có liên quan với các thông tin liên quan. - Là dữ liệu chỉ đọc. Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 - Luận văn thạc sỹ 15 - 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 xu hƣớng thông tin. - Chứa các bảng dữ liệu với các kích thƣớc lớn. - Một câu hỏi thƣờng trả về một tập kết quả liên quan đến toàn bộ các bảng và các liên kết nhiều bảng. Kiến trúc Cấu trúc kho dữ liệu đƣợc xây dựng dựa trên hệ quản trị CSDL quan hệ, có chức năng giống nhƣ một kho dữ liệu lƣu trữ thông tin trung tâm. Trong đó dữ liệu và phần xử lý tác nghiệp đƣợ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 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. Các dữ liệu nguồn Client - Làm sạch - Chuyển đổi - Tích hợp - Tải về… Kho dữ liệu Các công cụ truy vấn và phân tích Hình 1.1: Kiến trúc kho dữ liệu Nhƣ trên hình 1.1 đã trình bày, kho dữ liệu bao gồm 7 thành phần: - Dữ liệu nguồn (là các ứng dụng tác nghiệp hoặc các kho dữ liệu tácYes nghiệp và các công cụ chiết xuấttruy xuấtkết xuất, chuyển đổi, làm sạch dữ liệu). - Kho dữ liệu về dữ liệu (Metadata) - Các kỹ thuật xây kho - Kho dữ liệu thông minh hay dữ liệu theo chủ đề (hay trung tâm dữ liệu ?) Yes (Data marts) là nơi các dữ liệu đƣợc khoanh vùng theo chủ đề tới một giới Yes Khai phá dữ liệu sử dụng luật kết hợp ử Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 16 hạn nào đó và có thể thay đổi theo nhu cầu của từng bộ phận ngƣời dùng. Với các kho dữ liệu này, cũng có thể xây dựng một kho dữ liệu theo cách tiếp cận từng giai đoạn kế tiếp, nghĩa là với một tập hợp kho dữ liệu thông minh, ta tạo ra một kho dữ liệu ngƣợc lại, một kho dữ liệu có thể phân tích thành nhiều kho dữ liệu thông minh. - Các công cụ vấn đáp (query), báo cáo (reporting), phân tích trực tuyến và khai phá dữ liệu (Data mining). Đây chính là các cách khai thác kho dữ liệu để đem lại những ―tri thức‖ hơn là dữ liệu thô. - - Quản trị kho dữ liệu - Hệ thống phân phối thông tin Sử dụng trong Data warehouse Nhƣng chỉ có kho dữ liệu thôi chƣa đủ để có các tri thức. Các kho dữ liệu đƣợc sử dụng theo 3 cách chính: - Khai thác các thông tin bằng công cụ vấn đáp và báo cáo: Bằng cách sử dụng tầng ẩn giữa ngƣời dùng và CSDL, các dữ liệu thô đƣợc chuyển sang dữ liệu chất lƣợng cao và có tính ổn định, các dữ liệu đầu vào của các kỹ thuật này đƣợc đặt vào nguồn duy nhất. Việc hợp nhất này loại bỏ đƣợc rất nhiều lỗi sinh ra do việc phải thu thập và biểu diễn thông tin từ rất nhiều nguồn khác nhau cũng nhƣ giảm đƣợc sự chậm trễ do phải lấy các dữ liệu phân đoạn trong các cơ sở dữ liệu khác nhau, tránh cho ngƣời dùng SQL khỏi những câu lệnh SQL phức tạp. Tuy nhiên đây mới chỉ khai thác với kỹ thuật cao để đƣa ra các dữ liệu tinh và chính xác hơn chứ chƣa đƣa ra đƣợc dữ liệu ―tri thức‖. - Phân tích trực tuyến (Online analytical processingthuật ngữ tiếng Anh là gì ? - OLAP). Trong khi ngôn ngữ vấn đáp chuẩn SQL và các công cụ làm báo cáo truyền thống chỉ có thể miêu tả những gì có trong CSDL thì phân tích trực tuyến có khả năng phân tích dữ liệu, xác định xem giả thuyết đúng hay Khai phá dữ liệu sử dụng luật kết hợp Formatted: Default Paragraph Font, Font: Times New Roman, 13 pt, No underline, Font color: Auto Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 17 sai. Tuy nhiên phân tích trực tuyến lại không có khả năng đƣa ra đƣợc các giả thuyết (không hiểu, cần giải thích cụ thể hơn) vì tính trực tuyến của nó. - Công nghệ khai phá dữ liệu (Data mining). Một phƣơng pháp mới đƣợc đƣa ra với mục tiêu đáp ứng cả nhu cầu trong khoa học cũng nhƣ trong hoạt động thực tiễn trong việc tìm kiếm tri thức (sao không nói rõ thêm một chút nhỉ?). Việc đáp ứng đƣợc các yêu cầu khắt khe về tính thông minh, tính dự đoán và hỗ trợ việc kinh doanh cũng nhƣ ra quyết định một cách tự động là đặc điểm nổi bật nhất từ phƣơng pháp này. 1.4 Quá trình phát hiện tri thức 1.4.1 Phát hiện tri thức Sử dụng thông tin một cách hiệu quả - Là yếu tố thành công và mang tính sống còn trong mọi lĩnh vực kinh doanh hiện nay. Điều đó có nghĩa là từ dữ liệu có sẵn phải tìm ra những thông tin tiềm ẩn có giá trị mà trƣớc đó chƣa đƣợc phát hiện ra, tìm ra những xu hƣớng phát triển và những yếu tố tác động lên chúng. Thực hiện công việc đó chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in DataBase-KDD) mà trong đó kỹ thuật cho phép lấy ra các tri thức chính là kỹ thuật khai phá dữ liệu (data mining). Tri thức có thể hiểu là một biểu thức trong một ngôn ngữ nào đó diễn tả một hoặc một vài mối quan hệ giữa các thuộc tính trong dữ liệu. Các ngôn ngữ thƣờng đƣợc dùng để biểu diễn tri thức(trong việc phát hiện tri thức từ các CSDL) là các khung (frames), các cây đồ thị, các luật (rules), các công thức chính trong ngôn ngữ logic mệnh đề hoặc tân từ cấp một hay, các hệ thống phƣơng trình.h… Quá trình phát hiện tri thức mang tính hƣớng nhiệm vụ, 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 một nhiệm vụ nào đó. Vì vậy quá trình phát hiện tri thức là quá trình hoạt động tƣơng tác giữa ngƣời sử dụng hoặc chuyên gia phân tích với các công cụ tin học [3]. 1.4.2 Các giai đoạn của quá trình phát hiện tri thức Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 18 Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu trong CSDL lớn. Quá trình KDD là quá trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở bất cứ lúc nào. Quá trình đó có thể mô tả theo mô hình sau (Hình 2.2) 1 Xác định và định nghĩa vấn đề 2 Thu thập và tiền xử lý dữ liệu 3 Khai phá dữ liệu 4 Giải thích kết quả và đánh giá 5 Sử dụng tri thức phát hiện đƣợc Hình 1.2 Quá trình phát hiện tri thức 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 và lựa chọn CSDL. Giai đoạn 2: Thu thập và tiền xử lý: bao gồm làm sạch dữ liệu, rút gọn kích thƣớc và số chiều. Giai đoạn 3: Khai phá dữ liệu: bao gồm chọn nhiệm vụ khai phá, chọn các phƣơng pháp khai phá và thực hiện khai phá để rút ra các mẫu, các mô hình có ý nghĩa dƣới dạng biểu diễn tƣơng ứng (luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy…). Giai đoạn 4: Giải thích kết quả và đánh giá các mẫu các mô hình tìm thấy ở giai đoạn 3. Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 19 Luận văn thạc sỹ Giai đoạn 5: Sử dụng các tri thức đã được phát hiện: củng cố tinh chế các tri thức đã đƣợc phát hiện. Kết hợp các tri thức thành hệ thống. Giải quyết các xung đột tiềm năng trong tri thức khai thác đƣợc. Sau đó tri thức đƣợc chuẩn bị sẵn sàng cho ứng dụng. Nhƣ vậy KDD là một quá trình rút ra tri thức từ dữ liệu mà trong đó khai phá dữ liệu là giai đoạn chủ yếu. Lý luận và thực tiễn thực hiện các quá trình phát hiện tri thức là sự tiếp thu, sử dụng và phát triển nhiều thành tựu, 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... Lý thuyết phát hiện tri thức có đặc điểm mới là các tri thức, các dạng mẫu, các giả thuyết đều đƣợc phát hiện từ việc khai thác các kho dữ liệu. Nếu phát hiện tri thức là toàn bộ quá trình trừu truy xuấtkết xuất tri thức từ các CSDL thì khai phá dữ liệu là giai đoạn chủ yếu của quá trình đó. Trong quá trình phát hiện tri thức, khâu khai phá dữ liệu đƣợc thức hiện sau khâu tinh lọc và tiền xử lý tức là khai phá để tìm các mẫu hình có ý nghĩa đƣợc tiến hành trên một tập dữ liệu có chọn lọc chứ không phải là toàn bộ dữ liệu. Vì vậy, khai phá dữ liệu thƣờng bao gồm việc thử tìm một 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 đó. Thí 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ợ (support) và độ tin cậy (confidence) trong các luật tƣơng ứng. Các kết quả đạt đƣợc cho thấy các kỹ thuật khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm, với tri thức mà chuyên gia con ngƣời cũng 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 lợi nhuận đáng kể trong nền kinh tế. Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 20 CHƢƠNG 2 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 2.1 Mục tiêu của khai phá dữ liệu. Trong những thập kỷ gần đây, các thiết bị lƣu trữ thông tin với dung lƣợng lớn không ngừng tăng lên. Việc lƣu trữ dữ liệu lớn này ngày càng phát triển và bùng nổ với một tốc độ lớn. Với tình hình hiện tại, khối lƣợng thông tin trên toàn cầu đƣợc dự đoán sẽ tăng gấp đôi chỉ sau 2 năm và theo đà đó thì lƣợng lƣu trữ và kích cỡ của các CSDL cũng tăng lên một cách ồ ạt và nhanh chóng. Trong các lĩnh vực kinh doanh, tuy rằng đang có trong tay một lƣợng thông tin khổng lồ nhƣng các nhà quản lý vẫn thấy thiếu thông tin nhât là các thông tin cần thiết và hữu ích. Vậy thì phải làm thế nào ?. Khai thác thông tin tiềm ẩn mang tính dự đoán từ các CSDL lớn là mục tiêu chính của khai phá dữ liệu, sử dụng cách thức này đƣợc coi là một hƣớng tiếp cận mới giúp cho các đơn vị, tổ chức chú trọng vào những thông tin có nhiều ý nghĩa từ những tập dữ liệu lớn và hữu ích. Những công cụ khai phá dữ liệu có thể dự đoán các xu thểế tƣơng lai do đó cho phép các tổ chức doanh nghiệp đƣa ra đƣợc các quyết định kịp thời đƣợc định hƣớng bỏi bởi tri thức mà khi khai phá dữ liệu đem lại. Tính tự động trong phân tích dữ liệu khiến nó chiếm ƣu thế hơn hẳn so với các phân tích thông thƣờng dựa trên kinh nghiệm hay các sự kiện trong quá khứ của các hệ thống hỗ trợ ra quyết định trƣớc đây. Trên cơ sở đó cũng đồng thời trả lời đƣợc nhiều vấn đề trong kinh doanh mà trƣớc đây khó có thể thực thi vì cần rất nhiều thời gian và công sức để xử lý. Với định hƣớng và mục tiêu chính của khai phá dữ liệu là chiết xuấttruykết xuất tri thức từ dữ liệu. Do đó ta có thể coi mục đích chính của quá trình khai phá dữ liệu là mô tả (description) và dự đoán (prediction). Các mẫu mà khai phá dữ liệu phát hiện đƣợc nhằm vào mục đích này. Khai phá dữ liệu sử dụng luật kết hợp Nguyễn Ngọc Long, K9T3 Luận văn thạc sỹ 21 Dự đoán liên quan đến việc sử dụng các biến hoặc các trƣờng trong cơ sở dữ liệu để chiết xuấttruykết xuất ra các mẫu là các dự đoán những giá trị chƣa biết hoặc những giá trị trong 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. 2.2 Các 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ƣờng thì bƣớc đầu tiên là giải thuật nạp toàn bộ 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 đáp ứng đƣợc. Không chỉ bởi vì nó không thể nạp hết toàn bộ dữ liệu vào trong bộ nhớ mà còn có thể khó chiết xuấttruykế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 qua mô hình sau [3]: Thống kê tóm tắt Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý DL Giải thuật khai phá DL Mẫu Dữ liệu trực tiếp Hình 2.3 Quá trình khai phá dữ liệu Các dữ liệu nguồn - Xác định nhiệm vụ: Xác định chính xác cá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 và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền 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 Khai phá dữ liệu sử dụng luật kết hợp