Đề tài 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 Data Mining Kỹ thuật phát hiện tri thức và khai 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 Processing Phân tích trực tuyến ROLAP Relational OLAP Phân tích quân hệ trực tuyến Record record Bản ghi Supp suppport Độ hỗ trợ 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