LUẬN VĂN:PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:78

Thêm vào BST

Báo xấu

215
lượt xem 100
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của luận văn gồm 3 chương và phần phụ lục:Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC. Chương này đề cập đến các giai đoạn của quy trình phát hiện tri thức, các vấn đề chính của khai phá dữ liệu, các phương pháp, các nhiệm vụ trong khai phá dữ liệu.Chương 2: CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN:PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO

1 TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệp Đề tài: PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO
2 MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... 5 DANH MỤC CÁC HÌNH VẼ ............................................................................ 6 LỜI MỞ ĐẦU .................................................................................................... 7 Chương 1 .......................................................................................................... 9 TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC............ 9 1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu ...................................... 9 1.2. Các bước trong quá trình phát hiện tri thức[7] ........................................ 10 1.3. Kiến trúc hệ thống khai phá dữ liệu ........................................................ 12 1.4.1. Cơ sở dữ liệu quan hệ ...................................................................... 12 1.4.2. Kho dữ liệu ...................................................................................... 12 1.4.3. Cơ sở dữ liệu không gian ................................................................. 13 1.4.4. Cơ sở dữ liệu văn bản ...................................................................... 13 1.4.5. Dữ liệu Web..................................................................................... 13
3 1.5. Các phương pháp khai phá dữ liệu ......................................................... 13 1.5.1. Các thành phần của giải thuật khai phá dữ liệu ................................ 14 1.5.2. Phương pháp suy diễn / quy nạp ...................................................... 16 1.5.3. Phương pháp ứng dụng K-láng giềng ............................................... 16 1.5.4. Phương pháp sử dụng cây quyết định và luật[14] ............................. 17 1.5.5. Phương pháp phát hiện luật kết hợp ................................................. 18 1.6. Các nhiệm vụ trong khai phá dữ liệu ...................................................... 19 1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa..................................... 20 1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu ............................................... 20 1.6.3. Phát hiện sự sai lệch ......................................................................... 21 1.6.4. Phát hiện luật kết hợp....................................................................... 21 1.6.5. Mô hình hoá sự phụ thuộc ................................................................ 21 1.6.6. Mô hình hoá nhân quả...................................................................... 22 1.6.7. Phân cụm, nhóm .............................................................................. 22 1.6.8. Phân lớp ........................................................................................... 23 1.6.9. Hồi quy ............................................................................................ 23 1.6.10. Tổng hợp ....................................................................................... 23 1.7. Các thách thức và giải pháp cơ bản ........................................................ 24 1.7.1. Thách thức ....................................................................................... 24 1.7.2. Một số giải pháp .............................................................................. 25 1.8. Kết luận.................................................................................................. 25 Chương 2 ........................................................................................................ 26 CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP ..................................................................... 26 2.1. Lý thuyết về luật và luật kết hợp ............................................................ 26 2.1.1. Luật thừa .......................................................................................... 26 2.1.2. Luật kết hợp ..................................................................................... 27 2.1.3. Một số tính chất của luật kết hợp[6] ................................................. 30 2.1.4. Phát biểu bài toán khai phá luật kết hợp[8] ...................................... 31 2.1.5. Một số hướng tiếp cận trong khai phá luật kết hợp ........................... 32 2.2. Các đặc trưng của luật kết hợp ............................................................... 34 2.2.1. Không gian tìm kiếm của luật .......................................................... 34
4 2.2.2. Độ hỗ trợ của luật ............................................................................ 36 2.3.Một số giải thuật cơ bản khai phá các tập phổ biến ................................. 36 2.3.1.Kỹ thuật BFS .................................................................................... 37 2.3.2.Kỹ thuật DFS .................................................................................... 44 2.5. Thuật toán AIS ....................................................................................... 44 2.5.1. Bài toán đặt ra .................................................................................. 44 2.5.2. Thuật toán AIS................................................................................. 45 2.6. Thuật toán SETM ................................................................................... 47 2.6.1. Bài toán đặt ra .................................................................................. 47 2.6.2. Thuật toán SETM ............................................................................ 47 2.7. Thuật toán CHARM[9] .......................................................................... 50 2.7.1. Tư tưởng thuật toán CHARM .......................................................... 50 2.7.1.1. Cơ sở lý thuyết .......................................................................... 50 2.7.2.2. Bài toán đặt ra............................................................................ 52 2.7.2. Thuật toán CHARM ......................................................................... 53 2.8. Kết luận.................................................................................................. 56 Chương 3 ........................................................................................................ 57 ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO .............. 57 3.1. Bài toán .................................................................................................. 57 3.2. Đặc tả dữ liệu ......................................................................................... 58 3.3. Chương trình thử nghiệm minh họa ........................................................ 63 3.4. Kết luận .............................................................................................. 66 KẾT LUẬN ...................................................................................................... 67 PHỤ LỤC ........................................................................................................ 68 TÀI LIỆU THAM KHẢO ................................................................................ 77
5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt ADO Activate X Data Object BFS Breadth First Search Tìm kiếm theo bề rộng Ck Ck Tập các K – itemset ứng cử Conf confidence Độ tin cậy CSDL Database Cơ sở dữ liệu DFS Depth First Search Tìm kiếm theo độ sâu DW Data Warehouse Kho dữ liệu Item item Khoản mục Itemset itemset Tập các khoản mục K- itemset K- itemset Tập gồm K mục KDD Knowledge Discovery and Kỹ thuật phát hiện tri thức và khai Data Mining phá dữ liệu Lk Lk Tập các K - itemset phổ biến Minconf Minimum Confidence Độ tin cậy tối thiểu Minsup Minimum Support Độ hỗ trợ tối thiểu MOLAP Multidimensional OLAP Phân tích đa chiều trực tuyến OLAP On Line Analytical Phân tích trực tuyến Processing ROLAP Relational OLAP Phân tích quân hệ trực tuyến Record record Bản ghi Supp suppport Độ hỗ t r ợ TID Transaction Indentification Định danh giao tác SQL Structured Query Language Ngôn ngữ vấn đáp chuẩn SQO Sematics Query Optimization TC Tính chất
6 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Các bước trong quá trình phát hiện tri thức .................................................... 11 Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu ................................................................ 12 Hình 1.3: Ví dụ mô hình khai phá dữ liệu ....................................................................... 15 Hình 1.4: Ví dụ cây quyết định......................................................................................... 17 Hình 1.5: Ví dụ về luật kết hợp ........................................................................................ 19 Hình 1.6: Ví dụ Form nhập liệu ........................................................................................ 24 Bảng 2.1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D............................................... 28 Bảng 2.2 : Các tập phổ biến trong cơ sở dữ liệu ở bảng 1 với độ hỗ trợ tối thiểu 50% 28 Hình 2.3: Dàn cho tập I = {1,2,3,4} ................................................................................. 34 Hình 2.4: Cây cho tập I = {1, 2, 3, 4} .............................................................................. 35 Hình 2.5: Hệ thống hóa các giải thuật .............................................................................. 37 Bảng 2.6: Ví dụ thuật toán Apriori ................................................................................... 42 Bảng 2.7. Ví dụ thuật toán AIS ........................................................................................ 46 Bảng 2.8: Ví dụ thuật toán SETM .................................................................................... 50 Bảng 2.9: Tập các giao dịch trong ví dụ thuật toán CHARM ........................................ 53 Bảng 2.10: Tập mục phổ biến trong ví dụ minh hoạ thuật toán CHARM ..................... 54 Hình 2.11: Thuật toán CHARM sắp xếp theo thứ tự từ điển .......................................... 54 Hình 2.12: Sắp xếp theo độ hỗ trợ tăng dần .................................................................... 55 Hình 3.1: Trường Đại học Dân lập Hải phòng ................................................................ 57 Bảng 3.2: Ví dụ CSDL điểm của sinh viên...................................................................... 59 Bảng 3.3: Dữ liệu đã chuyển đổi từ dạng số sang dạng logic......................................... 60 Bảng 3.4: Bảng ký hiệu tên các môn học......................................................................... 63 Hình 3.5: Sơ đồ quan hệ CSDL điểm sinh viên .............................................................. 63 Hình 3.6: Giao diện chương trình chính .......................................................................... 63 Hình 3.7: Phần kết nối CSDL ........................................................................................... 64 Hinh 3.8: Form cập nhật điểm sinh viên .......................................................................... 64 Hình 3.9: Form cập nhật thêm sinh viên .......................................................................... 64 Hình 3.10: Phần dữ liệu đã được mã hoá ......................................................................... 65 Hình 3.11: Phần tạo luật kết hợp dùng thuật toán Apriori .............................................. 65 Hình 3.12: Phần mô phỏng thuật toán với dữ liệu nhập vào từ bàn phím ..................... 66
7 LỜI MỞ ĐẦU Ngày nay công nghệ thông tin luôn luôn phát triển và không ngừng đổi mới, cùng với sự phát triển đó là các hệ thống thông tin phục vụ việc tự động hoá trong các lĩnh vực của con người cũng được triển khai vượt bậc. Điều đó đã tạo ra những dòng dữ liệu khổng lồ. Nhiều hệ quản trị CSDL mạnh cũng đã ra đời giúp chúng ta khai thác hiệu quả nguồn tài nguyên đã thu thập được. Với lượng dữ liệu, thông tin thu thập được ngày càng nhiều như vậy đòi hỏi chúng ta phải trích rút ra những thông tin tiềm ẩn nhằ m đưa ra các quyết định đúng đắn trong công việc. Xuất phát từ thực tiễn đó, vào những nă m cuối của thế kỷ 20 khai phá dữ liệu ra đời. Đây là một lĩnh vực nghiên cứu khá mới mẻ của ngành khoa học máy tính và khai phá tri thức (KDD). Nó đã thu hút sự quan tâm của rất nhiều người ở các lĩnh vực khác nhau như : các hệ CSDL, thống kê, nhận dạng, máy học, trí tuệ nhân tạo... Khai phá dữ liệu sử dụng các công cụ phân tích dữ liệu như: truy vấn, báo cáo, dịch vụ phân tích trực tuyến (OLAP, ROLAP, MOLAP) để tìm ra các mẫu có giá trị trong kho dữ liệu. Khai phá dữ liệu đã và đang được ứng dụng thành công vào các ngành thương mại, tài chính, kinh doanh, sinh học, y học, giáo dục, viễn thông... Khai phá luật kết hợp từ CSDL lớn được khởi xướng từ năm 1993, nó đã và đang được nghiên cứu, phát triển mạnh vì khả năng tìm được các luật có ích, từ đó có những dự báo giúp chúng ta có kế hoạch các hướng phát triển cho tương lai. Việc khai phá luật kết hợp ứng dụng vào trong công tác đào tạo còn chưa được nghiên cứu và ứng dụng tối đa. Để từng bước nâng cao khả năng ứng dụng khai phá luật kết hợp vào giải quyết những công việc trong công tác đào tạo đạt hiệu quả cao, bằng những kinh nghiệm thực tế và qua kiến thức thu thập được trong những năm theo học tại khoa Công nghệ Thông tin trường đại học Quốc Gia Hà Nội, nghiên cứu giảng dạy tại trường đại học Dân Lập Hải Phòng, chính vì vậy tác giả chọn đề tài “KHAI PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO”. Nội dung chính của đề tài là đi sâu vào tìm hiểu một số thuật toán khai phá luật kết hợp và áp dụng thuật toán kinh điển Apriori ứng dụng trong công tác đào tạo của trường đại học Dân lập Hải Phòng. Kết quả nghiên cứu sẽ cung cấp các thông tin hỗ trợ cho sinh viên lựa chọn môn học, ngành học, hướng nghiên cứu, đồng thời hỗ trợ cán bộ làm công tác tư vấn đào tạo, cán bộ phòng đào tạo được thuận lợi hơn trong công tác đào tạo. Nội dung của luận văn gồm 3 chương và phần phụ lục:
8 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC. Chương này đề cập đến các giai đoạn của quy trình phát hiện tri thức, các vấn đề chính của khai phá dữ liệu, các phương pháp, các nhiệm vụ trong khai phá dữ liệu. Chương 2: CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP. Chương này trình bày một số vấn đề chính của khai phá luật kết hợp: lý thuyết luật kết hợp, bài toán khai phá và phát hiện luật kết hợp, các phương pháp phát hiện luật kết hợp, một số thuật toán điển hình giải quyết vấn đề, phân tích độ phức tạp của bài toán. Chương 3: ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO. Nội dung của chương là áp dụng kỹ thuật khai phá luật kết hợp vào trong đào tạo của trường Đại học Dân lập Hải phòng. Ứng dụng này nhằ m đưa ra dự báo hỗ trợ cho công tác đào tạo của trường. Phần phụ lục đưa ra một số modul của chương trình ứng dụng. Cuối cùng là kết luận lại những kết quả đạt được của đề tài và hướng phát triển trong tương lai.
9 Chương 1 TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu Việc dùng các phương tiện tin học để tổ chức và khai thác các CSDL đã được phát triển từ những năm 60, nhiều CSDL đã được tổ chức, phát triển và khai thác ở mọi qui mô và khắp các lĩnh vực hoạt động của xã hội. Với sự phát triển mạnh mẽ của máy tính và các mạng viễn thông, người ta đã xây dựng được nhiều hệ CSDL lớn tập trung hoặc phân tán, nhiều hệ quản trị CSDL mạnh với các công cụ phong phú và thuận tiện giúp con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu trong các hoạt động kinh tế xã hội. Tuy nhiên từ đầu thập niên 90, con người mới thực sự bước vào giai đoạn bùng nổ thông tin. Nhờ áp dụng các công nghệ và kỹ thuật mới, rất nhiều các thiết bị tiên tiến ra đời có khả năng hỗ trợ đắc lực cho việc thu thập, lưu trữ và khai thác dữ liệu. Các thiết bị lưu trữ với tốc độ cao, dung lượng lớn như đĩa từ, CD/DVD-ROM, thiết bị điều khiển từ xa, vệ tinh nhân tạo… đã giúp con người hàng ngày thu thập được hàng chục, hàng trăm gigabytes dữ liệu. Sự phát triển nhanh chóng của một lượng lớn dữ liệu được thu thập và lưu trữ trong các CSDL lớn đã vượt ra ngoài khả năng của con người có thể hiểu được chúng nếu không có những công cụ hỗ trợ tốt. Kết quả là, dữ liệu thu thập được trong một lượng lớn CSDL đã trở thành những đống dữ liệu mà ít khi được xem xét đến. Do vậy, việc đưa ra những quyết định thường không dựa vào những thông tin hoặc dữ liệu thu thập được mà chỉ dựa vào nhận thức, suy đoán của người đưa ra quyết định. Đơn giản là vì họ không có những công cụ giúp cho việc lấy ra những tri thức từ lượng lớn dữ liệu. Tình huống này đã đặt chúng ta trong hoàn cảnh nhiều dữ liệu nhưng thiếu thông tin, thiếu tri thức. Với một khối lượng lớn dữ liệu như vậy rõ ràng là các phương pháp thủ công truyền thống áp dụng để phân tích dữ liệu như chia bảng không còn là phù hợp nữa. Và có một kỹ thuật mới ra đời đó là kỹ thuật khai phá tri thức trong cơ sở dữ kiệu (Knowledge Discovery in Database) gọi tắt là KDD. Thuật ngữ KDD được đưa ra vào năm 1989 với ý nghĩa là thực hiện các xử lý để tìm ra các tri thức trong CSDL và mục đích nhấn mạnh đến các ứng dụng ở mức cao hơn của khai phá dữ liệu (data mining). Khai phá dữ liệu thường được dùng trong các lĩnh vực thống kê, đánh giá dữ liệu và các hệ thống quản lý dữ liệu.
10 Chúng ta có thể phân biệt một cách tương đối giữa phát hiện tri thức trong CSDL và khai phá dữ liệu. KDD để chỉ một quá trình tổng thể bao gồm nhiều bước nhằ m phát hiện ra các tri thức hữu ích trong dữ liệu còn khai phá dữ liệu chỉ tập trung vào việc ứng dụng các thuật toán nhằ m phát hiện các mẫu từ dữ liệu mà không có thêm các bước của quá trình KDD như bước kết hợp với tri thức đã có hoặc bước đánh giá kết quả thu được. Các bước thê m vào này rất cần thiết để thấy rõ được rằng những thông tin thu được từ dữ liệu là thực sự hữu ích. Đối với quá trình khai phá dữ liệu, nhiều khi các mẫu thu được nhờ thực hiện một ứng dụng nào đó không có giá trị hoặc không phục vụ cho mục đích nào. Như vậy, một quá trình phát hiện tri thức từ dữ liệu được đặc trưng bằng các bước lặp chính là lặp lại các ứng dụng theo một thuật toán khai phá dữ liệu cụ thể và hiểu các mẫu thu được từ thuật toán này Định nghĩa: “KDD là một quá trình không tầm thường của việc xác định các mẫu mới, có giá trị, có hiệu quả sử dụng và cơ bản hiểu được trong cơ sở dữ liệu”.[7] Còn các nhà thống kê thì xem Khai phá dữ liệu như là một qui trình phân tích được thiết kế để thăm dò một lượng cực lớn các dữ liệu nhằ m phát hiện ra các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm đưọc bằng cách áp dụng các mẫu đã phát hiện được cho các tập con mới của dữ liệu. Qui trình này bao gồm ba giai đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức/kiểm chứng. 1.2. Các bước trong quá trình phát hiện tri thức[7] Phát hiện tri thức bao gồm nhiều giai đoạn được lặp đi lặp lại nhiều lần mà không cần phân biệt từng bước trong quá trình thực hiện. 1. Giai đoạn 1: Hình thành, xác định và định nghĩa bài toán. Là việc 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 cùng với bản chất của dữ liệu. 2. Giai đoạn 2: Thu thập và tiền xử lý ( xử lý thô). Bước này còn được gọi là tiền xử lý dữ liệu nhằ m loại bỏ nhiễu (dữ liệu dư thừa), làm sạch dữ liệu, xử lý và khắc phục vấn đề thiếu hoặc thừa 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 (bước quan trọng) trong toàn bộ quy trình phát hiện tri thức.
11 3. Giai đoạn 3: Biến đổi dữ liệu, chọn lựa một số phương pháp. Phân loại (Classification), hồi quy (Regression), phân nhóm (Clustering), quy nạp, tổng hợp kết quả (Summarization). Giải thích kết quả và đánh giá mẫu Tri thức và cách sử dụng Khai phá dữ liệu Biến đổi dữ liệu Thu thập và tiền xử lý Hình thành, xác định và Mẫu và định nghĩa vấn đề mô hình Dữ liệu đã được Dữ liệu đã biến đổi được tiền xử lý Mục tiêu dữ Internet,... liệu Kho dữ liệu Hình 1.1: Các bước trong quá trình phát hiện tri thức 4. Giai đoạn 4: Khai phá dữ liệu, hay nói cách khác là trích chọn, chiết xuất ra các mẫu hay các mô hình tiềm ẩn dưới các dữ liệu có ý nghĩa, hiểu được. 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 khai phá dữ liệu, dùng phương pháp khai phá nào là thích hợp?. 5. Giai đoạn 5: Giải thích kết quả và đánh giá các mẫu hay mô hình. Các mẫu và mô hình này là kết quả của giai đoạn 3 trong quy trình. Đây là công đoạn không thể thiếu trong quá trình khai phá tri thức. 6. Giai đoạn 6: Hiểu và sử dụng 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 trên tất cả các lần thực hiện. Tóm lại: Quá trình phát hiện tri thức từ trong kho dữ liệu (KDD – Knowledge Discovery Database) là quá trình chiế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.
12 1.3. Kiến trúc hệ thống khai phá dữ liệu Kiến trúc của hệ thống khai phá dữ liệu có thể chia thành các thành phần chính như trong hình. 1- Kho dữ liệu: là một tập các cơ sở dữ liệu, các công cụ làm sạch dữ liệu và tích hợp dữ liệu có thể thực hiện trên chúng. 2- Cơ sở tri thức: là yếu tố tri thức được dùng để đánh giá các mẫu kết quả khai phá được. Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu 3- Kỹ thuật khai phá: là các công cụ để thực hiện các nhiệm vụ: mô tả, kết hợp, phân lớp, phân nhóm dữ liệu. 4- Công cụ đánh giá mẫu: gồm một số modul sử dụng các độ đo và tương tác với các modul khai phá dữ liệu để tập trung vào các thuộc tính cần quan tâm. 5- Biểu diễn dạng đồ hoạ: modul này giao tiếp giữa người dùng và hệ thống khai phá dữ liệu. 1.4. Các loại dữ liệu sử dụng 1.4.1. Cơ sở dữ liệu quan hệ Các CSDL quan hệ là một trong những kho chứa phổ biến nhiều thông tin nhất và là dạng dữ liệu chủ yếu để nghiên cứu khai phá dữ liệu. 1.4.2. Kho dữ liệu
13 Kho dữ liệu (Data Warehouse) chứa thông tin thu thập từ nhiều nguồn, được lưu trữ trong một lược đồ hợp nhất. Kho dữ liệu được tổ chức theo các chủ đề và cung cấp tính lịch sử, tổng hợp cao với cấu trúc vật lý là CSDL quan hệ hoặc khối dữ liệu nhiều chiều. Kho dữ liệu là môi trường tốt nhất cho khai phá dữ liệu hoạt động hiệu quả. 1.4.3. Cơ sở dữ liệu không gian CSDL không gian chứa các thông tin có quan hệ về mặt không gian như CSDL địa lý, CSDL ảnh vệ tinh và y học…Dữ liệu được biểu diễn theo dạng mã vạch, chứa bản đồ bit n- chiều hoặc bản đồ các điểm pixel. Bản đồ có thể được biểu diễn thành dạng vectơ trong đó đường phố, cầu, toà nhà, hồ…Khai phá dữ liệu có thể phát hiện mẫu bằng cách mô tả đặc trưng của ngôi nhà gần một vị trí nào đó như hồ chẳng hạn. Nói chung, các khối dữ liệu không gian có thể tổ chức thành cáu trúc đa chiều và phân cấp. 1.4.4. Cơ sở dữ liệu văn bản CSDL văn bản chứa các mô tả từ như các câu, đoạn. Có nhiều CSDL văn bản có tính phi cấu trúc như các trang Web hoặc nửa cấu trúc như các message mail, trang XML…Để phát hiện các đặc tả chung của các lớp đối tượng, từ khoá, nội dung liên quan, đối tượng văn bản…các phương pháp khai phá dữ liệu cần tích hợp với các kỹ thuật lấy thông tin và xây dựng từ điển, từ điển đồng nghĩa… 1.4.5. Dữ liệu Web Dữ liệu Word Wide Web cung cấp các dịch vụ thông tin trực tuyến toàn cầu là cơ hội phong phú với nhiều thách thức mới cho khai phá dữ liệu. Khai phá dữ liệu Web với các mục đích như:  Khai phá nội dung Web để phát hiện ra các tri thức từ nội dung các trang Web  Khai phá cấu trúc Web: phát hiện mô hình nền tảng cấu trúc liên kết.  Khai phá sử dụng Web: phát hiện thông tin từ các phiên làm việc truy nhập của người dùng. Khi nắ m bắt được các mẫu tra cứu trang có thể sắp xếp lại các liên kết và đưa các quảng cáo vào những trang mà người dùng thường quan tâm 1.5. Các phương pháp khai phá dữ liệu Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mực đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong
14 đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác định. Có thể kể ra đây một vài phương pháp như: sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị trung bình, phát hiện luật kết hợp, … Các phương pháp trên có thể được phỏng theo và được tích hợp vào các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách thức về mặt hiệu quả và quy mô. 1.5.1. Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm. Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu tả các mẫu có thể khai thác được. Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có mô hình chính xác cho dữ liệu. Tuy nhiên, nếu mô hình quá lớn thì khả năng dự đoán của học máy sẽ bị hạn chế. Như thế sẽ làm cho việc tìm kiếm phức tạp hơn cũng như hiểu được mô hình là không đơn giản hoặc sẽ không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Ví dụ: mô tả cây quyết định sử dụng phân chia các nút theo một trường dữ liệu, chia không gian đầu vào thành các siêu phẳng song song với trục các thuộc tính. Phương pháp cây quyết định như vậy không thể khai phá được dữ liệu dạng công thức “X = Y” dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy, việc quan trọng là người phân tích dữ liệu là cần phải hiểu đầy đủ các giả thiết miêu tả. Một điều cũng khá quan trọng là người thiết kế giải thuật cũng phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm giả m đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở lên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với tham số được xác định dựa trên dữ liệu (trong một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập các dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS, … một số giải thuật học máy (ví dụ như cây quyết định và các quyết định học có thầy khác),
15 mạng neuron, suy diễn hướng tình huống (case based reasoning), các kỹ thuật phân lớp. Hình 1.3: Ví dụ mô hình khai phá dữ liệu Kiểm định mô hình (model evaluation): Là việc đánh giá, ước lượng các mô hình chi tiết, chuẩn trong quá trình xử lý và phát hiện tri thức với sự ước lượng có dự báo chính xác hay không và có thoả mãn cơ sở logic hay không? Ước lượng phải được đánh giá chéo (cross validation) với việc mô tả đặc điểm bao gồm dự báo chính xác, tính mới lạ, tính hữu ích, tính hiểu được phù hợp với các mô hình. Hai phương pháp logic và thống kê chuẩn có thể sử dụng trong mô hình kiểm định. Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: tìm kiế m tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. Việc tìm kiếm không cần thiết đối với một số bài toán khá đơn giản: các đánh giá tham số tối ưu có thể đạt được bằng các cách đơn giản hơn. Đối với các mô hình chung thì không có các cách này, khi đó giải thuật “tham lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phương pháp giả m gradient trong giải thuật lan truyền ngược (backpropagation) cho các mạng neuron. Tìm kiếm mô hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: mô tả mô hình bị thay đổi tạo nên một họ các mô hình. Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản (closed form) không dễ đạt được.
16 1.5.2. Phương pháp suy diễn / quy nạp Một CSDL là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và 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 CSDL. 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ừ CSDL. 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 CSDL. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. 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.5.3. Phương pháp ứng dụng K-láng giềng 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 đã làm”. Ví dụ: Để 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ể đó. 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 hạn là 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ế
17 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 K-lá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.5.4. Phương pháp sử dụng cây quyết định và luật[14] 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. 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. Hình 1.4: Ví dụ cây quyết định 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.
18  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.5.5. 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 CSDL. 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 CSDL về các điểm của sinh viên, các dòng tương ứng với các các sinh viên, các cột tương ứng với các điểm các môn học thì giá trị 1 tại ô (Trần Thu Hà, lập trình C đạt 8) xác định rằng sinh viên đó cũng đạt (Trần Thu Hà, hệ điều hành đạt 7). 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  {B}, r) còn gọi là độ hỗ trợ của luật, độ tin cậy của luật là s(X  {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 CSDL 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.
19 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ổ K biến có kích thước K thì phải có ít nhất là 2 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. Hình 1.5: Ví dụ về luật kết hợp 1.6. Các nhiệm vụ trong khai phá dữ liệu Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong CSDL (KDD) theo yêu cầu nhằ m đáp ứng những đòi hỏi trong nhiều lĩnh vực khác nhau, việc phát hiện tri thức cũng trở lên đa dạng hơn. Do đó, nhiệm vụ của phát hiện tri thức trong CSDL cũng trở lên phong phú và có thể phát hiện rất nhiều kiểu tri thức khác nhau. Một trong các bước đầu tiên trong quá trình phát hiện tri thức trong CSDL là quyết định xem loại kiến thức nào mà thuật toán phát hiện tri thức trong CSDL cần phải kết xuất từ dữ liệu. Do đó, việc phân loại và so sánh các kiểu nhiệm vụ phát hiện tri thức trong CSDL là vấn đề đáng quan tâm nhằ m tạo ra một hệ thống phát hiện tri thức trong CSDL hữu ích. Ta sẽ xem xét một số kiểu nhiệm vụ phát hiện tri thức sau:
20 1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa Các luật tối ưu truy vấn CSDL thông thường thực hiện một phép biến đổi cú pháp, hay sắp xếp lại thứ tự của các phép toán quan hệ trong một truy vấn và sản sinh ra một truy vấn hiệu quả hơn. Các phép biến đổi này thường dựa trên lý thuyết đại số quan hệ. Các luật được biến đổi trả lại cùng một câu trả lời như câu truy vấn ban đầu ở bất kỳ trạng thái nào của CSDL. Ngược lại, luật tối ưu truy vấn ngữ nghĩa biến đổi các câu truy vấn ban đầu thành một truy vấn mới bằng cách thêm vào hoặc xoá đi các mối liên kết bằng việc sử dụng các tri thức CSDL ngữ nghĩa bao gồm các ràng buộc về tính toàn vẹn và sự phụ thuộc hàm để sản sinh ra các câu truy vấn hiệu quả hơn. Như vậy câu truy vấn đã biến đổi cũng trả lại cùng câu trả lời giống như câu truy vấn ban đầu trong bất kỳ trạng thái nào của CSDL thoả mãn kiến thức về ngữ nghĩa được sử dụng trong phép biến đổi. Các hệ thống phát hiện luật SQO có thể được chia thành ba lớp: Các hệ thống hướng truy vấn (hệ thống báo cáo) trong đó thuật toán phát hiện tri thức trong CSDL nhằ m phục vụ các truy vấn CSDL thực của người dùng; 1. Các hệ thống hướng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán phát hiện tri thức trong CSDL chủ yếu phục vụ sự phân bổ dữ liệu trong trạng thái hiện thời của CSDL; 2. Các hệ thống lại kết hợp các đặc tính của cả hệ thống hướng truy vấn và hướng dữ liệu. Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện tri thức khác, là việc chọn các thuộc tính để tổng hợp một SQO cần phải tính đến chi phí liên quan như dùng phương pháp truy cập nào và sơ đồ chỉ số trong hệ quản trị CSDL. Việc này là cần thiết để tiết kiệm thời gian xử lý truy vấn. Một thuật toán phát hiện tri thức trong CSDL loại này đòi hỏi phải xem xét tối ưu chi phí. 1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này thường được thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn. Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu này. Sự phụ thuộc CSDL được sử dụng trong thiết kế và duy trì một CSDL. Phương pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu nhiệm vụ của khai phá dữ liệu.