Tài liệu Hỗ trợ hệ chuyên gia cho khai phá luật kết hợp

  • Số trang: 71 |
  • Loại file: PDF |
  • Lượt xem: 115 |
  • Lượt tải: 0
nguyetha

Đã đăng 8489 tài liệu

Mô tả:

1 LỜI CẢM ƠN Trƣớc hết, tôi xin chân thành cảm ơn tới các thầy cô giáo Trƣờng Đại học Sƣ phạm Hà Nội 2 đã tận tâm giảng dạy, cung cấp cho tôi kiến thức, phƣơng pháp nghiên cứu trong khóa học cũng nhƣ trong quá trình thực hiện luận văn. Đặc biệt tôi xin đƣợc bày tỏ lòng biết ơn sâu sắc đến thầy giáo hƣớng dẫn PGS.TS Lê Huy Thập, ngƣời đã tận tình hƣớng dẫn, giúp đỡ và động viên để tôi thực hiện luận văn này. Xin cảm ơn gia đình, bạn bè và đồng nghiệp đã tạo điều kiện giúp đỡ tôi trong thời gian tôi thực hiện luận văn. Mặc dù tôi đã cố gắng nghiên cứu, tìm hiểu đề tài nhƣng vẫn không thể tránh khỏi những sai sót nhất định, rất mong nhận đƣợc sự đóng góp và chia sẻ của quý thầy cô và bạn bè. Tôi xin chân thành cảm ơn. Hà Nội, tháng 12 năm 2013 TÁC GIẢ LUẬN VĂN Hoàng Văn Lê \ 2 LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung bản luận văn theo đúng nội dung đề cƣơng. Nội dung luận văn là sự hƣớng dẫn tận tình của PGS. TS Lê Huy Thập và bản thân tôi tự sƣu tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu. Nội dung luận văn này chƣa đƣợc công bố hay xuất bản dƣới bất kỳ hình thức nào cũng nhƣ không đƣợc sao chép từ tài liệu đã có sẵn và đảm bảo tính chính xác và thực tiễn. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã đƣợc cảm ơn. Hà Nội, tháng 12 năm 2013 TÁC GIẢ LUẬN VĂN Hoàng Văn Lê 3 MỤC LỤC LỜI CẢM ƠN ........................................................................................................................ 1 LỜI CAM ĐOAN .................................................................................................................. 2 MỤC LỤC ............................................................................................................................. 3 DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ................................................... 5 DANH MỤC CÁC HÌNH VẼ ............................................................................................... 6 DANH MỤC CÁC BẢNG .................................................................................................... 7 PHẦN MỞ ĐẦU ................................................................................................................... 8 CHƢƠNG 1 TỔNG QUAN ................................................................................................ 10 1.1 KHAI PHÁ DỮ LIỆU ............................................................................................. 10 1.1.1 Định nghĩa khai phá dữ liệu ............................................................................... 10 1.1.2 Các ứng dụng của khai phá dữ liệu .................................................................... 10 1.1.3 Các bƣớc của quá trình khai phá dữ liệu ........................................................... 11 1.1.4 Nhiệm vụ chính trong khai phá dữ liệu ............................................................. 13 1.1.5 Các phƣơng pháp khai phá dữ liệu .................................................................... 15 1.1.6 Lợi thế cuả khai phá dữ liêu so với phƣơng pháp khác ..................................... 18 1.1.7 Lựa chọn phƣơng pháp ...................................................................................... 21 1.2 HỆ CHUYÊN GIA .................................................................................................. 22 1.2.1 Khái niệm Hệ chuyên gia................................................................................... 22 1.2.2 Kiến trúc tổng quát của các hệ chuyên gia ........................................................ 23 1.2.3 Các kĩ thuật thể hiện tri thức .............................................................................. 27 1.3 KẾT LUẬN CHƢƠNG ........................................................................................... 29 CHƢƠNG 2 HỖ TRỢ HỆ CHUYÊN GIA TRONG KHAI LUẬT KẾT HỢP .................. 30 2.1 PHƢƠNG PHÁP TÌM LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU ............ 30 2.1.1 Vài nét về khai phá luật kết hợp ........................................................................ 30 2.1.2 Luật kết hợp ....................................................................................................... 30 4 2.1.3 Thuật toán Apriorid ........................................................................................... 33 2.1.4 Thuật toán AprioriTID ...................................................................................... 39 2.1.5 Thuật toán AprioriHybrid .................................................................................. 43 2.1.6 Thuật toán K-Nearest Neighbors ....................................................................... 44 2.1.7 Thuật toán K-Means .......................................................................................... 45 2.2 CÁC PHƢƠNG PHÁP SUY LUẬT KHÔNG CHẮC CHẮN TRONG HCG…………48 2.2.1 Tổng quan về lý thuyết chắc chắn ..................................................................... 48 2.2.2 Cơ sở của lý thuyết chắc chắn ........................................................................... 49 2.2.3 Nhân tố chắc chắn dƣới khía cạnh xác suất ....................................................... 53 2.2.4 Lan truyền chắc chắn ......................................................................................... 53 2.2.5 Phƣơng pháp suy luận không chắc chắn trong Hệ chuyên gia .......................... 57 2.3 THỂ HIỆN ĐỘ CHẮC CHẮN CF TRONG SỰ KIỆN VÀ TRONG KHAI PHÁ LUẬT KẾT HỢP ....................................................................................................... 61 2.3.1 Tập luật sau khai phá luật kết hợp ..................................................................... 61 2.3.2 Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp .................... 61 2.4 KẾT LUẬT CHƢƠNG ............................................................................................ 62 CHƢƠNG 3 ỨNG DỤNG HỖ TRỢ HCG TRONG KPDL TẠI SIÊU THỊ BÁN SÁCH . 64 3.1 LẬP TRÌNH ỨNG DỤNG TẠI SIÊU THỊ BÁN SÁCH ........................................ 64 3.1.1 Giới thiệu bài toán ............................................................................................. 64 3.1.2 Tóm tắt và phân tích và thiết kế hệ thống .......................................................... 64 3.2 CÁC GIAO DIỆN VÀ KẾT QUẢ CỦA CHƢƠNG TRÌNH ................................. 66 KẾT LUẬN.......................................................................................................................... 70 TÀI LIỆU THAM KHẢO ................................................................................................... 71 5 DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ý nghĩa Ký hiệu, chữ viết tắt Candidate itemset Một itemset trong tập Ck đƣợc sử dụng để sinh ra các large itemset Ck Tập các candidate k-itemset ở giai đoạn thứ k Confidence Độ tin cậy của luật kết hợp CSDL Cơ sở dữ liệu HCG Hệ chuyên gia DM Data mining- Khai phá dữ liệu Frequent/large itemset Một intemset có độ hỗ trợ (support)>= ngƣỡng độ hỗ trợ tối thiểu CF Certainty factor ID Indentifier Item Một phần tử của Itemset Itemset Tập của các item k-itemset Một itemset có độ dài k Lk Tập các large itemset ở giai đoạn thứ k TID Transaction Indentifier Transaction Giao dịch Classification Phân loại Candidate Dự tuyển 6 DANH MỤC CÁC HÌNH VẼ Ý nghĩa Hình Trang Hình 1.1 Quy trình phát hiện tri thức 12 Hình 1.2 Hoạt động của hệ chuyên gia 23 Hình 1.3 Những thành phần cơ bản của một hệ chuyên gia 24 Hình 1.4 Quan hệ giữa máy suy diễn và cơ sở tri thức 25 Hình 1.5 Kiến trúc hệ chuyên gia theo J.Emine 26 Hình 1.6 Kiến trúc hệ chuyên gia theo C. Ernest 26 Hình 2.1 Query Point phân lớp 47 Hình 2.2 Thiết kế xác định danh giới các cụm ban đầu 48 Hình 2.3 Tính toán trọng tâm các cụm mới 48 Hình 2.4 Phạm vi của giá trị CF 53 Hình 3.1 Mô hình quan hệ thực thể 68 Hình 3.2 Sơ đồ giữ liệu quan hệ 69 Hình 3.3 Các giao dịch chính 70 Hình 3.4 Các giao dịch trong cơ sở dữ liệu 70 Hình 3.5 Thể hiện độ hỗ trợ tối thiểu và độ tin cậy tối thiểu 71 Hình 3.6 Thể hiện độ hỗ trợ tối thiểu và độ tin cậy tối thiểu khác 72 Hình 3.7 Thể hiện độ chắc chắn của luật 72 Hình 3.8 Kết quả chƣơng trình 73 7 DANH MỤC CÁC BẢNG Ý nghĩa Bảng Trang Bảng 2.1 Các mặt hàng và nhãn 38 Bảng 2.2 Các giao dịch 38 Bảng 2.3 Ứng viên C1 39 Bảng 2.4 Ứng viên L1 39 Bảng 2.5 Ứng viên C2 39 Bảng 2.6 Ứng viên C2 39 Bảng 2.7 Ứng viên C2 39 Bảng 2.8 Ứng viên L2 39 Bảng 2.9 Ứng viên C3 40 Bảng 2.10 Miêu tả giá trí CF 55 8 PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Để tìm ra các luật kết hợp trong khai phá dữ liệu, cơ bản dựa vào độ hỗ trợ Sup (Suport) và độ tin cậy Conf (Confidence), nhƣng những tham số này phải đƣợc xác định qua kinh nghiệm hay qua phƣơng pháp chuyên gia. Dù bằng cách nào thì độ khả tín của các luật cũng ở mức độ tham khảo nào đó. Để tăng độ tin cậy vào các luật đã tìm đƣợc chúng ta có thể dùng phƣơng pháp hỗ trợ thêm của hệ chuyên gia. Từng chuyên đề trên thì thế giới và Việt Nam đã có sự quan tâm nghiên cứu, nhƣng sự kết hợp gữa hai chuyên đề theo cách nêu ra trên thì chƣa. Chúng ta sẽ dùng phƣơng pháp bổ sung nhân tố chắc chắn CF cho cả các sự kiện, luật,… để tăng độ khả tín cho các luật kết hợp đã nhận đƣợc bằng phƣơng pháp khai phá luật kết hợp. 2. Mục đích nghiên cứu (Các kết quả cần đạt đƣợc) Dùng suy luận không chắc chắn để hỗ trợ khai phá luật kết hợp Lập trình thể hiện luật kết hợp có hỗ trợ phƣơng pháp suy luận không chắc chắn tại siêu thị bán sách 3. Nhiệm vụ nghiên cứu Nghiên cứu khai phá dữ liệu có hỗ trợ của hệ chuyên gia. 4. Đối tƣợng và phạm vi nghiên cứu Khai phá dữ liệu Hệ chuyên gia 5. Giả thuyết khoa học Dùng hệ chuyên gia, Trí tuệ nhân tạo,… để hỗ trợ khi nâng cao và mở rộng đề tài. 6. Phƣơng pháp nghiên cứu Phƣơng pháp tìm luật kết hợp trong khai phá dữ liệu Các phƣơng pháp suy luận không chắc chắn trong hệ chuyên gia. Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp 9 Nội dung luận văn gồm 3 chƣơng Chƣơng 1. Tổng quan 1.1 Khai phá dữ liệu 1.2 Hệ chuyên gia 1.3 Kết luận chƣơng Chƣơng 2. Hỗ trợ hệ chuyên gia trong khai phá luật kết hợp 2.1 Phƣơng pháp tìm luật kết hợp trong khai phá dữ liệu 2.2 Các phƣơng pháp suy luận không chắc chắn trong hệ chuyên gia. 2.3 Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp 2.4 Kết luận Chƣơng 3. Ứng dụng hỗ trợ hệ chuyên gia trong khai phá luật kết hợp tại siêu thị bán sách 3.1. Lập trình ứng dụng tại siêu thị bán sách 3.2. Các giao diện và kết quả của chƣơng trình ứng dụng 10 CHƢƠNG 1 TỔNG QUAN 1.1 KHAI PHÁ DỮ LIỆU 1.1.1 Định nghĩa khai phá dữ liệu Khai phá dữ liệu đƣợc dùng để mô tả quá trình phát hiện ra tri thức trong cơ sở dữ liệu. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất, ... Khai phá dữ liệu làm giảm chi phí về thời gian so với phƣơng pháp truyền thống trƣớc kia (ví dụ nhƣ phƣơng pháp thống kê). Sau đây là các định nghĩa mang tính mô tả của nhiều tác giả về khai phá dữ liệu: Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp đƣợc dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chƣa biết bên trong dữ liệu”. Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong cơ sở dữ liệu lớn”. Định nghĩa của Fayyad: “Khai phá dữ liệu là một quá trình không tầm thƣờng nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu đƣợc”. 1.1.2 Các ứng dụng của khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song ... Đặc biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phƣơng pháp thống kê để mô hình hóa dữ liệu và phát hiện các mẫu. Khai phá dữ liệu có nhiều ứng dụng trong thực tế, ví dụ nhƣ: Bảo hiểm, tài chính và thị trƣờng chứng khoán: phân tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận, ... Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định. 11 Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh đƣợc lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng bệnh, chuẩn đoán và phƣơng pháp điều trị. Sản xuất và chế biến: các quy trình, phƣơng pháp chế biến và xử lý sự cố. Text mining và Web mining: phân lớp văn bản và các trang Web, tóm tắt văn bản. Lĩnh vực khoa học: quan sát thiên văn, dữ liệu sinh vật học, dữ liệu gene, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di truyền, ... Mạng viễn thông: phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự cố, chất lƣợng dịch vụ, ... 1.1.3 Các bƣớc của quá trình khai phá dữ liệu Quy trình phát hiện tri thức thƣờng tuân theo các bƣớc sau: Bƣớc thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức hữu ích và cho phép chọn các phƣơng pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bƣớc thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn đƣợc gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bƣớc này thƣờng chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Do dữ liệu đƣợc lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể gây ra các nhầm lẫn. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và rời rạc hoá. 12 Hình 1.1. Quy trình phát hiện tri thức Bƣớc thứ ba: Khai phá dữ liệu, rút ra các tri thức.Là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dƣới các dữ liệu. Giai đoạn này rất quan trọng, bao gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, dùng phƣơng pháp khai phá nào? Thông thƣờng, các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đƣa ra tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa trên dữ liệu hiện có. Tùy theo bài toán xác định đƣợc mà ta lựa chọn các phƣơng pháp khai phá dữ liệu cho phù hợp. Bƣớc thứ tƣ: Là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bƣớc trên có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực hiện. Bƣớc thứ năm: Sử dụng các tri thức phát hiện đƣợc. Là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bƣớc trên có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực hiện. Các kết quả của quá trình phát hiện tri thức có thể đƣợc đƣa và ứng dụng trong các lĩnh vực khác nhau. Do các kết quả có thể là các dự đoán hoặc các mô tả nên chúng có thể đƣợc đƣa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này. Tóm lại: Khai phá dữ liệu là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 13 1.1.4 Nhiệm vụ chính trong khai phá dữ liệu Quá trình khai phá dữ liệu là quá trình phát hiện ra mẫu thông tin. Trong đó, giải thuật khai phá tìm kiếm các mẫu đáng quan tâm theo dạng xác định nhƣ các luật, phân lớp, hồi quy, cây quyết định, ... Nhiệm vụ chính trong khai phá dữ liệu bao gồm: phân lớp, hồi qui, phân nhóm, tổng hợp, mô hình hoá sự phụ thuộc và phát hiện sự biến đổi và độ lệch. 1.1.4.1 Phân lớp (phân loại – classification) Là việc xác định một ánh xạ để ánh xạ các mẫu dữ liệu thỏa mãn ràng buộc nào đó vào cùng một lớp, do đó dữ liệu sẽ đƣợc phân thành các lớp có thể giao nhau hoặc không. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Nhƣ thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức đƣợc phát hiện biểu diễn dƣới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thoả mãn điều kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết luận”. Ví dụ 1.1: Một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên. 1.1.4.2 Hồi qui (regression) Là việc dùng một hàm dự báo để từ các mẫu dữ liệu đã có hàm dự báo sẽ cho một giá trị thực. Nhiệm vụ của hồi qui 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 phải 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 hoá cũng đƣợc sử dụng, ví dụ nhƣ cây quyết định. Ứng dụng của hồi quy là rất nhiều: dự báo thời tiết, ƣớc lƣợng xác suất ngƣời bệnh có thể chết bằng cách kiểm tra các triệu chứng; dự báo nhu cầu của ngƣời dùng đối với một sản phẩm. 14 1.1.4.3 Phân nhóm (clustering) Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này lại vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm nhƣ phát hiện tập các khách hàng có phản ứng giống nhau trong cơ sở dữ liệu tiếp thị; xác định các quang phổ từ các phƣơng pháp đo tia hồng ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa biến/ các trƣờng trong cơ sở dữ liệu. 1.1.4.4 Tổng hợp (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 tổng hợp 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”. Lƣu ý rằng luật dạng này có các khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó. 1.1.4.5 Mô hình hoá 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 1: 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. Mức 2: 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 đề là đú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. 15 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 đó. 1.1.4.6 Phát hiện sự biến đổi và độ lệch (change and deviation dectection) Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau của giữa dữ liệu trong hai tập con dữ liệu, ở đây tính 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 đƣợc phát hiện. Vì những nhiệm vụ này yêu cầu số lƣợng và các dạng thông tin rất khác nhau nên chúng thƣờng ảnh hƣởng đến việc thiết kế và chọn phƣơng pháp khai phá dữ liệu khác nhau. Ví dụ nhƣ phƣơng pháp cây quyết định (sẽ đƣợc trình bày mục 1.1.5.3) tạo ra đƣợc một mô tả phân biệt đƣợc các mẫu giữa các lớp nhƣng không có tính chất và đặc điểm của lớp. 1.1.5 Các phƣơng pháp khai phá dữ liệu 1.1.5.1 Phƣơng pháp suy diễn / quy nạp Phƣơng pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong cơ sở dữ liệu. Ví dụ nhƣ toán tử liên kết áp dụng cho bảng quan hệ, bảng đầu chứa thông tin về các nhân viên và phòng ban, bảng thứ hai chứa các thông tin về các phòng ban và các trƣởng phòng. Nhƣ vậy sẽ suy ra đƣợc mối quan hệ giữa các nhân viên và các trƣởng phòng. Phƣơng pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất đƣợc bằng cách sử dụng phƣơng pháp này thƣờng là các luật suy diễn. Phƣơng pháp quy nạp: Phƣơng pháp quy nạp suy ra các thông tin đƣợc sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trƣớc. Các thông tin mà phƣơng pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tƣợng trong cơ sở dữ 16 liệu. Phƣơng pháp này liên quan đến việc tìm kiếm các mẫu trong cơ sở dữ liệu. Trong khai phá dữ liệu, quy nạp đƣợc sử dụng trong cây quyết định và tạo luật. 1.1.5.2 Phƣơng pháp K-láng giềng gần Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là rất có ích đối với việc phân tích dữ liệu. Việc dùng các miêu tả này, nội dung của vùng lân cận đƣợc xác định, trong đó các bản ghi gần nhau trong không gian đƣợc xem xét thuộc về lân cận (hàng xóm–láng giềng) của nhau. Khái niệm này đƣợc dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần, trong đó K là số láng giềng đƣợc sử dụng. Phƣơng pháp này rất hiệu quả nhƣng lại đơn giản. Ý tƣởng thuật toán học K-láng giềng gần là “thực hiện nhƣ các láng giềng gần của bạn trong đời sống hàng ngày”. Ví dụ 1.2: Để dự đoán hoạt động của cá thể xác định, K-láng giềng tốt nhất của cá thể đƣợc xem xét, và trung bình các hoạt động của các láng giềng gần đƣa ra đƣợc dự đoán về hoạt động của cá thể đó [4, 6]. Kỹ thuật K-láng giềng gần là một phƣơng pháp tìm kiếm đơn giản. Tuy nhiên, nó có một số mặt hạn chế giới là hạn phạm vi ứng dụng của nó. Đó là thuật toán này có độ phức tạp tính toán là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu. Vấn đề chính liên quan đến thuộc tính của bản ghi. Một bản ghi gồm nhiều thuộc tính độc lập, nó bằng một điểm trong không gian tìm kiếm có số chiều lớn. Trong các không gian có số chiều lớn, giữa hai điểm bất kỳ hầu nhƣ có cùng khoảng cách. Vì thế mà kỹ thuật K-láng giềng không cho ta thêm một thông tin có ích nào, khi hầu hết các cặp điểm đều là các láng giềng. Cuối cùng, phƣơng pháp Kláng giềng không đƣa ra lý thuyết để hiểu cấu trúc dữ liệu. Hạn chế đó có thể đƣợc khắc phục bằng kỹ thuật cây quyết định. 1.1.5.3 Phƣơng pháp sử dụng cây quyết định và luật Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của quá trình xây dựng mô hình sẽ cho ra một cây quyết định. Cây này đƣợc sử dụng trong quá trình phân lớp các đối tƣợng dữ liệu chƣa biết hoặc đánh giá độ chính xác của mô hình. Tƣơng ứng với hai giai đoạn trong quá trình phân lớp là quá trình xây dựng và sử dụng cây quyết định. 17 Quá trình xây dựng cây quyết định bắt đầu từ một nút đơn biểu diễn tất cả các mẫu dữ liệu. Sau đó, các mẫu sẽ đƣợc phân chia một cách đệ quy dựa vào việc lựa chọn các thuộc tính. Nếu các mẫu có cùng một lớp thì nút sẽ trở thành lá, ngƣợc lại ta sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm cơ sở để phân chia các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa chọn, ta tạo ra các nhánh tƣơng ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình trên cho tới khi tạo ra đƣợc cây quyết định, tất cả các nút triển khai thành lá và đƣợc gán nhãn. Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau đƣợc thỏa mãn: - Tất cả các mẫu thuộc cùng một nút. - Không còn một thuộc tính nào để lựa chọn. - Nhánh không chứa mẫu nào. Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng nhiều bộ nhớ. Lƣợng bộ nhớ sử dụng tỷ lệ thuận với kích thƣớc của mẫu dữ liệu huấn luyện. Một chƣơng trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài song lại có nhƣợc điểm về tốc độ thực thi. Do vậy, vấn đề tỉa bớt cây quyết định trở nên quan trọng. Các nút lá không ổn định trong cây quyết định sẽ đƣợc tỉa bớt. Kỹ thuật tỉa trƣớc là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa. 1.1.5.4 Phƣơng pháp phát hiện luật kết hợp Phƣơng pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm đƣợc. Ta có thể lấy một ví dụ đơn giản về luật kết hợp nhƣ sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A => B. Cho một lƣợc đồ R = {A1, …, Ap} các thuộc tính với miền giá trị {0,1}, và một quan hệ r trên R. Một luật kết hợp trên r đƣợc mô tả dƣới dạng X=>B với X R và B R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật nhƣ sau: Nếu một bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc tính B cũng là 1 trong cùng bản ghi đó. Ví dụ nhƣ ta có tập cơ sở dữ liệu về các mặt hàng bán trong siêu thị, các dòng tƣơng ứng với các ngày bán hàng, các cột tƣơng 18 ứng với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mì) xác định rằng bánh mì đã bán ngày hôm đó cũng kéo theo sự xuất hiện giá trị 1 tại ô (20/10, bơ). Cho W R, đặt s(W, r) là tần số xuất hiện của W trong r đƣợc tính bằng tỷ lệ của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật X=>B trong r đƣợc định nghĩa là s(X cậy của luật là s(X {B}, r) còn gọi là độ hỗ trợ của luật, độ tin {B}, r)/s(X, r). Ở đây X có thể gồm nhiều thuộc tính, B là giá trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn trƣớc khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm có kích thƣớc tăng theo hàm mũ của số lƣợng các thuộc tính ở đầu vào. Do vậy cần phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm các luật kết hợp. Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X=>B sao cho tần số của luật không nhỏ hơn ngƣỡng σ cho trƣớc và độ tin cậy của luật không nhỏ hơn ngƣỡng θ cho trƣớc. Từ một cơ sở dữ liệu ta có thể tìm đƣợc hàng nghìn và thậm chí hàng trăm nghìn các luật kết hợp. Ta gọi một tập con X R là thƣờng xuyên trong r nếu thỏa mãn điều kiện s(X,r) ≥ σ. Nếu biết tất cả các tập thƣờng xuyên trong r thì việc tìm kiếm các luật rất dễ dàng. Vì vậy, giải thuật tìm kiếm các luật kết hợp trƣớc tiên đi tìm tất cả các tập thƣờng xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách ghép dần các tập thuộc tính dựa trên mức độ thƣờng xuyên. Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất thích hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giải thuật tìm kiếm các luật kết hợp tạo ra số luật ít nhất phải bằng với số các tập phổ biến và nếu nhƣ một tập phổ biến có kích thƣớc K thì phải có ít nhất là 2K tập phổ biến. Thông tin về các tập phổ biến đƣợc sử dụng để ƣớc lƣợng độ tin cậy của các tập luật kết hợp. 1.1.6 Lợi thế cuả khai phá dữ liêu so với phƣơng pháp khác 1.1.6.1 Học máy (Machine Learning) Mặc dù ngƣời ta đã cố gắng cải tiến các phƣơng pháp học máy để có thể phù hợp với mục đích khai phá dữ liệu nhƣng sự khác biệt giữa cách thiết kế, các đặc 19 điểm của cơ sở dữ liệu đã làm cho phƣơng pháp học máy trở nên không phù hợp với mục đích này, mặc dù cho đến nay, phần lớn các phƣơng pháp khai phá dữ liệu vẫn đựa trên nền tảng cơ sở của phƣơng pháp học máy. Những phân tích sau đây sẽ cho thấy điều đó. Trong quản trị cơ sở dữ liệu, một cơ sở dữ liệu là một tập hợp đƣợc tích hợp một cách logic của dữ liệu đƣợc lƣu trong một hay nhiều tệp và đƣợc tổ chức để lƣu trữ có hiệu quả, sửa đổi và lấy thông tin liên quan đƣợc dễ dàng. Ví dụ nhƣ trong cơ sở dữ liệu quan hệ, dữ liệu đƣợc tổ chức thành các tệp hoặc các bảng có các bản ghi có độ dài cố định. Mỗi bản ghi là một danh sách có thứ tự các giá trị, mỗi giá trị đƣợc đặt vào một trƣờng. Thông tin về tên trƣờng và giá trị của trƣờng đƣợc đặt trong một tệp riêng gọi là thƣ viện dữ liệu (data dictionary). Một hệ thống quản trị cơ sở dữ liệu sẽ quản lý các thủ tục (procedures) để lấy, lƣu trữ, và xử lý dữ liệu trong các cơ sở dữ liệu đó. Trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập đến một tập các mẫu (instance hay example) đƣợc lƣu trong một tệp. Các mẫu thƣờng là các vector đặc điểm có độ dài cố định. Thông tin về các tên đặc điểm, dãy giá trị của chúng đôi khi cũng đƣợc lƣu lại nhƣ trong từ điển dữ liệu. Một giải thuật học còn sử dụng tập dữ liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị kết quả của việc học (ví dụ nhƣ một khái niệm). Với so sánh cơ sở dữ liệu thông thƣờng và cơ sở dữ liệu trong học máy nhƣ trên, có thể thấy là học máy có khả năng đƣợc áp dụng cho cơ sở dữ liệu, bởi vì không phải học trên tập các mẫu mà học trên tệp các bản ghi của cơ sở dữ liệu. Tuy nhiên, phát hiện tri thức trong cơ sở dữ liệu làm tăng thêm các vấn đề vốn đã là điển hình trong học máy và đã quá khả năng của học máy. Trong thực tế, cơ sở dữ liệu thƣờng động, không đầy đủ, bị nhiễu, và lớn hơn nhiều so với tập các dữ liệu học máy điển hình. Các yếu tố này làm cho hầu hết các giải thuật học máy trở nên không hiệu quả trong hầu hết các trƣờng hợp. Vì vậy trong khai phá dữ liệu, cần tập trung rất nhiều công sức vào việc vƣợt qua những khó khăn, phức tạp này trong cơ sở dữ liệu. 20 1.1.6.2 Phƣơng pháp hệ chuyên gia Các hệ chuyên gia cố gắng nắm bắt các tri thức thích hợp với bài toán nào đó. Các kỹ thuật thu thập giúp cho việp háp đó là một cách suy diễn các chuyên gia con ngƣời. Mỗi phƣơng pháp đó là một cách suy diễn các luật từ các ví dụ và giải pháp đối với bài toán chuyên gia đƣa ra. Phƣơng pháp này khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên gia thƣờng ở mức chất lƣợng cao hơn rất nhiều so với các dữ liệu trong cơ sở dữ liệu, và chúng thƣờng chỉ bao đƣợc các trƣờng hợp quan trọng. Hơn nữa, các chuyên gia sẽ xác nhận tính giá trị và hữu dụng của các mẫu phát hiện đƣợc. Cũng nhƣ với các công cụ quản trị cơ sở dữ liệu, ở các phƣơng pháp này đòi hỏi có sự tham gia của con ngƣời trong việc phát hiện tri thức. 1.1.6.3 Phát kiến khoa học Khai phá dữ liệu rất khác với phát kiến khoa học ở chỗ khai phá trong cơ sở dữ liệu ít có chủ tâm và có điều kiện hơn. Các dữ liệu khoa học có từ thực nghiệm nhằm loại bỏ một số tác động của các tham số để nhấn mạnh độ biến thiên của một hay một số tham số đích. Tuy nhiên, các cơ sở dữ liệu thƣơng mại điển hình lại ghi một số lƣợng thừa thông tin về các dự án của họ để đạt đƣợc một số mục đích về mặt tổ chức. Độ dƣ thừa này (hay có thể gọi là sự lẫn lộn – confusion) có thể nhìn thấy và cũng có thể ẩn chứa trong các mối quan hệ dữ liệu. Hơn nữa, các nhà khoa học có thể tạo lại các thí nghiệm và có thể tìm ra rằng các thiết kế ban đầu không thích hợp. Trong khi đó, các nhà quản lý cơ sở dữ liệu hầu nhƣ không thể xa xỉ đi thiết kế lại các trƣờng dữ liệu và thu thập lại dữ liệu. 1.1.6.4 Phƣơng pháp thống kê Một câu hỏi hiển nhiên là khai phá dữ liệu khác gì so với phƣơng pháp thống kê.. Từ nhiều năm nay, con ngƣời đã sử dụng phƣơng pháp thống kê một cách rất hiệu quả để đạt đƣợc mục đích của mình. Mặc dù các phƣơng pháp thống kê cung cấp một nền tảng lý thuyết vững chắc cho các bài toàn phân tích dữ liệu nhƣng chỉ có tiếp cận thống kê thuần túy thôi chƣa đủ. Thứ nhất, các phƣơng pháp thống kê chuẩn không phù hợp đối với các
- Xem thêm -