Chương 1: GIỚI THIỆU VẤN ĐỀ Chương này sẽ trình bay tong quan về khai pha dữ liệu và việc áp dụng khai phá dữ liệu, cụ thể là khai phá luật kết hợp, vào lĩnh vực giáo dục, các ưu điểm và thách thức của khai phá luật kết hợp trên dữ liệu giáo dục. Cuôi cùng là trình bày mục tiêu và ý nghĩa của dé tài.1 Giới thiệu đề tài Trong những năm gan day, sự phát triển mạnh mẽ của công nghệ thông tin và việc ứng dụng công nghệ thông tin vào hau hết mọi lĩnh vực sản xuất, quản lý, kinh doanh,. đã tạo ra một lượng dt liệu không lỗ. Làm sao khai thác được những thông tin hữu ích từ kho dữ liệu ấy trở thành một vấn đề rất được quan tam.
Từ đó, khám pha tri thức trong các cơ sở dữ liệu (Knowledge Discovery in Databases — KDD) ra đời. Day là quá trình khám phá những thông tin mới hữu ích và có giá tri từ lượng dữ liệu lớn [1,21]. KDD nhìn chung bao gồm quá trình tiền xử ly (pre-processing), khai phá dữ liệu (data mining), hậu xử lý (post-processing) [2]. Trong đó, khai phá dữ liệu là cốt lõi của KDD, bao gồm các giải thuật suy luận (inferring algorithms) dé khám pha dữ liệu, phát triển các mô hình toán học và khám phá các mẫu có ý nghĩa, chính là các tri thức cần khai phá [1.
Khai phá dữ liệu được ứng dụng trong rất nhiều lĩnh vực như bán lẻ (retail sales), sinh tin hoc (bioinformatics), và chống khủng bố (counter-terrorism) [3]. phân tích DNA [4]. Và trong những năm gân day, khai phá dữ liệu đã được ứng dụng vào lĩnh vực giáo dục, hình thành nên một hướng nghiên cứu mới gọi là khai phá dữ liệu giáo dục (Educational Data Mining — EDM) [5]. Đề thúc day cho sự phát triển của lĩnh vực nghiên cứu này, Hội nghị Quốc tế về Khai phá dữ liệu giáo dục (International Conference on Educational Data Mining) được tô chức hằng năm, bắt đầu từ năm 2008, bởi TỔ công tác về Khai phá Dữ liệu Giáo dục Quốc tế (International Working Group on Educational Data Mining ).
Ngoài ra tổ công tác này còn thành lập Hội Khai phá Dữ liệu Giáo dục Quốc tế (International Educational Data Minng Society, có Web site tại http://educationaldatamining.org) vào tháng 7 năm 2011, và xuất bản các Tạp chí Khai phá Dữ liệu Giáo dục (Journal of Educational Data Mining - JEDM). Trong những năm gan đây, EDM duoc sử dung trong các hệ thong E- learning va Hé thong quan ly hoc tap (Learning Management System - LMS), Hệ thống trợ giáo thông minh (Intelligent Tutoring System — ITS) [6] và Tri tué nhan tao trong Giao duc (Artificial Intelligence in Education — ATED) [7] trên khắp thé giới để giải quyết các van dé cũng như hỗ trợ hệ thống giáo dục như [8]: e Du đoán điêm sô của sinh viên và kêt qua học tập e Duy trì và cải tiên các khóa học (nội dung, các hoạt động .) e Tạo ra các dé nghị giúp sinh viên nhận biết nội dung nào là phù hop nhât với họ. Đề khai phá được các mẫu/mô hình và các mối quan hệ mới hữu ích từ các dữ liệu giáo dục, nhiều kỹ thuật đã được áp dụng như phân lớp (classification), gom cum (clustering), luật kết hop (association rule), thông kê va trực quan hóa (statistics and visualization), khai thác mẫu tuần tự (sequential pattern mining) [3. Trong đó khai phá luật kết hop là một trong những kỹ thuật phố biến nhất được sử dụng trong khai pha dir liệu giáo dục [5,8,10,11,12,13,14].
Khai phá luật kết hợp được sử dung trong các hệ thong e-learning [12] dé: tự động hướng dẫn hoạt động của người học, tạo ra và giới thiệu tài liệu học tập một cách thông minh, xác định các thuộc tính đặc trưng cho sự chênh lệch hiệu suất hoc tập giữa các nhóm sinh viên khác nhau. phát hiện các mối quan hệ đáng quan tâm từ các thông tin sử dung của học sinh để cung cấp thông tin phản hồi cho tác giả, tìm kiếm những sai lầm của sinh viên thường hay xuất hiện cùng nhau, tối ưu hóa nội dung của công thông tin e-learning bang cách xác định các nội dung được quan tâm nhất bởi người sử dụng, trích xuất các mô hình hữu ích để giúp nhà giáo dục và quản trị web đánh giá và hiểu các hoạt động khóa học trực tuyến. Trong [11], khai phá luật kết hợp được sử dụng dé tìm mối liên hệ giữa các môn học mà sinh viên không đạt nhằm giúp 2 họ định hướng học tập trong tương lai. [15] kết hợp khai phá luật kết hợp với lập trình tiễn hóa (genetic programming) dé khám phá các mối quan hệ giữa kiến thức, thời gian và điểm số, giúp giáo viên thay đổi cau trúc và nội dung ban đâu của môn học.
Khai phá luật kết hợp được giới thiệu đầu tiên năm 1993 trong [19], được sử dụng dé khám phá các mối quan hệ giữa các tập phan tử (itemset) trong cơ sở dữ liệu. Một luật kết hợp có dang A => B [support, confidence], trong đó A, B là các itemset, support va confidence lần lượt là độ hỗ trợ và độ tin cdy cua luật. Vị dụ: computer > antivirus_software [support=2%;confidence=60%| Luật này có nghĩa là 2% các giao dịch cho thay máy tinh (computer) va phần mém diệt vi-rút (antivirus software) được mua cùng nhau và 60% khách hàng nêu mua may tính sẽ mua phân mêm diệt vi-rút. Thông tin này rõ ràng rất hữu ích đối với doanh nghiệp.
giúp họ có chiến lược kinh doanh hiệu quả hơn. Bài toán khai phá luật kết hợp trên cơ sở dữ liệu được chia thành hai bài toán nhỏ [20. Bài toán thứ nhất là tìm tập pho biến, là tập các phân tử có độ hỗ trợ thỏa mãn ngưỡng tối thiểu cho trước. Bài toán thứ hai là tìm các luật kết hợp từ những tập phô biến thỏa mãn độ tin cậy tối thiểu cho trước.
Bài toán thứ hai có thé được giải quyết dé dàng và hiệu quả trong khoảng thời gian hợp lý. Tuy nhiên bài toán thứ nhất lại tốn nhiều thời gian và chi phí tính toán khi áp dụng trên các cơ sở đữ liệu lớn. Tuy nhiên lượng dữ liệu ngày một lớn và được cập nhật hàng ngày. Việc cập nhật dữ liệu có thể khiến các tập phố biến thành không phố biến và ngược lại, và do đó sẽ phát sinh những luật kết hợp mới cũng như loại bỏ một số luật kết hợp được khai phá trước đó.
Để giải quyết vẫn đề dữ liệu gia tăng, các thuật toán truyền thống không còn phù hợp và một số thuật toán mới đã được dé xuất. Dau tiên là thuật toán FUP do Cheung ef al. Y tuong cua thuat toan la luu lai tất cả các độ hỗ trợ của các tập phố biến cũ và kêt hợp với độ hồ trợ của các tập phô biên mới đê giảm sô lượng tập ứng viên (candidate itemsets) cần kiểm tra lại. Tuy vậy, thuật toán FUP vẫn phải xử lý lại toàn bộ co sở dữ liệu gốc khi thêm mới dữ liệu.
Một số thuật toán khác như AFPIM [24], FELINE [25], CanTree [26] sử dụng các khái niệm mới dé khai pha dữ liệu gia tăng. Các thuật toán trên sử dụng các cau trúc dữ liệu như FP-Tree, CanTree để lưu tất cả các thông tin của các mẫu. Tuy nhiên các thuật toán này đều tốn nhiều chỉ phí cho việc xử lý lại toàn bộ cơ sở dữ liệu gốc. Năm 2001, Hong et al.[37] đã đề xuất khái niệm pre-large itemset dé giảm bớt số lần xử lý lại cơ sở dữ liệu gốc khi có giao dịch mới được thêm vào.
Thuật toán chỉ xử lý lại toàn bộ cơ sở đữ liệu sốc khi số lượng giao dịch mới thêm vào vượt quá một ngưỡng an toàn. Đến năm 2008 Hong et al.[38] đề xuất cầu trúc FUFP-tree (Fast Updated FP-tree) dựa trên cau trúc FP-tree để xử lý các giao dịch mới và giúp cho quá trình cập nhật lại cây dễ dàng hơn. Vào năm 2009, cũng chính Hong et al.[39] đã kết hợp khái niệm pre-large itemset vào cau trúc FUFP-tree để xây dựng thuật toán Pre-FUFP dé xử lý trường hợp thêm mới giao dịch hiệu quả hon, đặc biệt khi số lượng nhỏ giao dịch được thêm vào. Năm 2011, Lê Thiện Phương et al.[40] đã đề xuất thuật toán Pre-FUT, kết hợp khái niệm pre-large itemset của Hong với cấu trúc Trie để cải tiễn hiệu năng của thuật toán FUP.
Hau hết các thuật toán khai phá luật kết hợp thường sinh ra một lượng lớn các luật và không đảm bảo rằng các luật đó có hữu ích không. Mặc dù việc sử dụng độ hỗ trợ và độ tin cậy có thể giúp loại bỏ nhiều luật. Tuy nhiên ngay cả các luật có độ hỗ trợ và độ tin cậy cao vẫn có thé không thu vi (interesting — dễ hiểu đối với con người, mới và hữu ich [21]). Dé giải quyết van dé này có thé sử dụng các độ đo tương quan (vi du lift, cosine .) nhăm đánh giá mức độ liên quan giữa các thuộc tính tốt hơn.2 Mục tiêu và phạm vỉ nghiên cứu của đề tài Mục tiêu của đề tài là xây dựng một hướng tiếp cận cho bài toán khai phá luật kết hợp định lượng gia tăng với dữ liệu đầu vào là tập kết quả học tập của sinh viên trong hệ giáo dục tín chi và dau ra là tập các luật kết hợp định lượng.
Các luật kết hợp định lượng được khai phá dễ hiểu đối với một người dùng thông thường như giáo viên, sinh viên và bộ phận quản lý, bộ phận đào tạo của các trường, các cơ sở giáo dục. Do đó dé tài sẽ áp dụng qui trình Khám phá tri thức tong quát (gồm giai đoạn tiền xử lý, khai phá dữ liệu và hậu xử lý) vào bài toán khai phá luật kết hợp định lượng gia tăng trên cơ sở dữ liệu giáo dục. Trong đó tập trung chủ yếu vào giai đoạn khai phá dữ liệu và hậu xử lý kết quả khai phá được. Giải pháp sẽ được thử nghiệm và đánh giá trên tập dữ liệu điểm thi của các sinh viên khóa 2005-2008 của khoa Khoa học và Kỹ thuật Máy tính, Đại học Bách Khoa TpHCM từ học kỳ I năm học 2005-2006 đến học kỳ I năm học 2011- 2012.3 Ý nghĩa của đề tài 1.1 Ý nghĩa khoa học Một trong những khía cạnh mà dé tài quan tâm và xử lý là vấn đề dữ liệu liên tục được thêm vào qua từng học kỳ cũng như việc thay đối chương trình dao tao và các môn học ảnh hưởng đến nhau.
Nếu không quan tâm đến van dé này thì các luật khai phá được sẽ bị lỗi thời và không còn phù hợp với tình hình hiện tại.