Đề xuất giải pháp sử dụng lưới thích nghi để nâng cao độ chính xác trong bài toán phân nhóm sinh viên - Phạm Thị Bích Vân

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 119 ĐỀ XUẤT GIẢI PHÁP SỬ DỤNG LƯỚI THÍCH NGHI ĐỂ NÂNG CAO ĐỘ CHÍNH XÁC TRONG BÀI TOÁN PHÂN NHÓM SINH VIÊN Phạm Thị Bích Vân*, Đỗ Thị Mai Hường Tóm tắt: Trong những năm gần đây khai phá dữ liệu giáo dục trở thành hướng phát triển mới thu hút được đông đảo sự quan tâm của các nhà khoa học trên thế giới. Mục đích của khai phá dữ liệu giáo dục là nhằm trích rút các tri thức từ tập dữ liệu giáo dục, các tri thức này có thể giúp ích để nâng cao chất lượng giáo dục đào tạo. Trong bài báo này chúng tôi đề xuất một giải pháp sử dụng lưới thích nghi trong bài toán phân nhóm sinh viên theo kết quả học tập dựa trên tập cơ sở dữ liệu điểm học tập của sinh viên. Độ chính xác phân nhóm của giải pháp đề xuất được so sánh với các thuật toán khác. Quá trình thực nghiệm được tiến hành trên tập dữ liệu điểm sinh viên Khoa Công nghệ Thông tin, Học viện Kỹ thuật quân sự. Từ khóa: Dự báo, Khai phá dữ liệu giáo dục, Phân nhóm, Lưới thích nghi. 1. MỞ ĐẦU Khai phá dữ liệu giáo dục là một hướng mới của khai phá dữ liệu. Các phương pháp khai phá dữ liệu giáo dục đã và đang được áp dụng trong các nghiên cứu trên thế giới như luật kết hợp, phân lớp, phân nhóm, mạng nơron, thuật toán genCác ứng dụng chủ yếu tập trung vào dự báo điểm thi, dự báo khả năng thành công của sinh viên trong những năm học đầu, phân nhóm sinh viên, gợi ý khóa học phù hợp với sinh viên. Cụ thể như: Al- Radaideh và cộng sự [1] áp dụng các mô hình phân lớp như cây quyết định, ID3, C4.5 và Bayes để dự báo điểm thi kết thúc học phần C++ của sinh viên đại học Yarmouk, Jordan. Ayesha, Mustafa, Sattar và Khan [2] miêu tả việc dùng thuật toán phân nhóm K-means để dự báo các hành vi học tập của sinh viên. Romeo và cộng sự [3] thực hiện sánh về độ chính xác phân nhóm giữa các kỹ thuật và phương pháp khai phá dữ liệu khác nhau trên tập dữ liệu lấy từ hệ thống Moodle Nhận thấy, một đặc điểm chung cũng như vấn đề gặp phải đối với các nghiên cứu này đó là việc chọn lựa các thuộc tính phân tích và thu thập dữ liệu để trích rút ra các thuộc tính là tương đối khó khăn và mất nhiều thời gian; bên cạnh đó tỷ lệ chính xác thu được là chưa được cao (phần lớn đạt dưới 70 %) [3]. Lưới thích nghi [6,7,8] là một kỹ thuật được sử dụng trong phân nhóm không gian dữ liệu lớn nhiều chiều, dữ liệu phức tạp. Đối với dữ liệu giáo dục là tập dữ liệu tương đối phức tạp, và việc xử lý tập dữ liệu có ảnh hưởng lớn đối với chất lượng phân nhóm. Vì thế, đối với bài toán phân nhóm sinh viên dựa trên dữ liệu giáo dục, chúng tôi đề xuất giải pháp sử dụng kỹ thuật lưới thích nghi trong quá trình xử lý dữ liệu để nâng cao chất lượng phân nhóm. Bài báo được cấu trúc như sau: mục 2 trình bày về cơ sở lý thuyết, mục 3 đề xuất mô hình phân nhóm sinh viên và đề xuất thuật toán phân khoảng dữ liệu điểm sinh viên theo lưới thích nghi, mục 4 thực nghiệm so sánh giải pháp đề xuất với 2 thuật toán điển hình là K-means và CLIQUE, mục 5 là kết luận về các kết quả đạt được. 2. CƠ SỞ LÝ THUYẾT Phân nhóm (clustering) là gom các đối tượng dữ liệu thành các nhóm có sự giống nhau dựa trên các thuộc tính của chúng. Một tập hợp đối tượng được gom lại thành một nhóm (cụm) nếu giữa bản thân chúng có sự giống nhau và khác biệt so với các đối tượng thuộc các nhóm khác. Một số thuật toán phân nhóm phổ biến như: thuật toán K-means[4] thực hiện phân nhóm theo phân vùng với ưu điểm là đơn giản trong quá trình thực hiện nhưng nhạy cảm với nhiễu; thuật toán CLIQUE[5] tiếp cận dựa trên lưới và mật độ: ưu điểm của thuật toán này là có thể làm việc với các tập dữ liệu lớn, nhiều chiều và giảm được ảnh hưởng của Công nghệ thông tin & Khoa học máy tính P.T.B.Vân, Đ.T.M.Hường, “Đề xuất giải pháp sử dụng lưới phân nhóm sinh viên.” 120 nhiễu do không phải tiến hành điền các dự liệu khuyết thiếu như K-means. Tuy nhiên CLIQUE có nhược điểm là chất lượng nhóm phụ thuộc nhiều vào kích thước khoảng lưới của mỗi chiều, và kích thước này do người dùng lựa chọn; thuật toán MAFIA[6] là cải tiến thuật toán CLIQUE bằng cách sử dụng lưới thích nghi với kích thước của mỗi chiều được chia khoảng theo thích nghi, do vậy các khoảng lưới hình thành là thích nghi theo dữ liệu; pMAFIA[7] là phiên bản song song của thuật toán MAFIA để tăng tốc độ xử lý. Trong mô hình đề xuất ở bài báo này chúng tôi sử dụng thuật toán pMAFIA-TID[9] là cải tiến của thuật toán pMAFIA nhằm để tăng tốc độ thực hiện. Lý do lựa chọn pMAFIA- TID là do tập cơ sở dữ liệu sinh viên là tập cơ sở dữ liệu nhiều chiều (800 bản ghi, 27 chiều) do vậy thời gian hình thành các nhóm là rất lớn, từ đó rất cần phải tăng tốc độ thực thi. Bên cạnh đó không gian dữ liệu đầu vào là không đầy đủ và phân bố dữ liệu là không xác định trước do vậy cần sử dụng thuật toán dựa lưới thích nghi để nâng cao độ chính xác. 3. PHÂN NHÓM SINH VIÊN THEO KẾT QUẢ HỌC TẬP SỬ DỤNG LƯỚI THÍCH NGHI 3.1. Đề xuât mô hình Với mục đích phân nhóm sinh viên thành các nhóm theo khả năng tốt nghiệp, chúng tôi đề xuất mô hình phân nhóm sinh viên sử dụng lưới thích nghi dựa trên kết quả điểm thi các học phần. Mục đích nhằm phân thành các nhóm có khả năng tốt nghiệp đúng hạn, các nhóm có khả năng tốt nghiệp chậm, các nhóm có khả năng tốt nghiệp giỏi, khá và trung bình. Từ các nhóm này sẽ cho phép dự đoán sớm cho sinh viên có khả năng tốt nghiệp đúng hạn hay không và loại tốt nghiệp của sinh viên này là gì? Hình1. Mô hình phân nhóm sinh viên. Các bước thực hiện phân nhóm sinh viên như sau: Bước 1.Thu thập dữ liệu và tiền xử lý dữ liệu. Bước 2.Áp dụng kỹ thuật lưới thích nghi và thuật toán pMAFIA-TID để phân nhóm trên tập dữ liệu đã xử lý, gán nhãn các nhóm. Bước 3. Xây dựng module dự đoán theo mã sinh viên. 3.2. Đề xuất thuật toán phân khoảng dữ liệu điểm theo lưới thích nghi Muốn thu được nhóm chính xác nhất thì cần coi mỗi điểm là một khoảng lưới. Tuy nhiên, khi đó nếu ta để thông số ngưỡng mật độ lớn thì số nhóm tạo thành là ít và số chiều của nhóm tạo thành là rất nhỏ, do vậy thông tin và tri thức thu được không đủ để đưa ra dự đoán cho các trường hợp. Ngược lại, nếu ta để thông số ngưỡng mật độ là nhỏ thì quá trình khai phá sẽ mất rất nhiều thời gian, và yêu cầu lượng bộ nhớ rất lớn. Do vậy, ở đây chúng tôi đề xuất thuật toán dựa trên kỹ thuật lưới thích nghi và dựa trên phân tích dữ liệu để đưa ra các khoảng lưới thích nghi cho mỗi chiều (mỗi học phần). Dữ liệu chọn để phân tích thực nghiệm ở đây là dữ liệu điểm của sinh viên Khoa Công nghệ Thông tin, Học viện Kỹ thuật quân sự gồm 800 bản ghi. Dự đoán TN đúng hạn CSDL giáo dục gồm N bản ghi (800 bản ghi sinh viên) Tập các nhóm C1,,Cn (mang nhãn đúng hạn hoặc không đúng hạn) Tập các nhóm C’1,,C’m (mang nhãn Giỏi, Khá, hoặc Trung bình) Lưới thích nghi, pMAFIA-TID Dự đoán phân loại TN Thông tin Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 121 a. Cấu trúc máy tính b. Ngôn ngữ C Hình 2. Lược đồ histogram điểm hai học phần. Xét hình 3a là lược đồ phân bố dữ liệu điểm môn Cấu trúc máy tính của sinh viên. Nhận thấy số sinh viên đạt điểm 5 và số sinh viên đạt điểm 6 có sự chênh lệch mật độ không nhiều, về mặt nào đó, sự chênh lệch trình độ giữa điểm 5 và điểm 6 trong môn Cấu trúc máy tính là không lớn, do vậy ta có thể gộp khoảng 5 và khoảng 6 với nhau để thành khoảng [5,6] với mật độ gần tương đương. Mặc dù khoảng điểm 7 có mật độ cũng gần tương đương với khoảng điểm 6, tuy nhiên nếu ta gộp khoảng 7 với khoảng [5,6] đã có thành khoảng [5,7] khi đó điểm 5 và điểm 7 là có sự chênh lệch về năng lực lớn, do vậy chỉ nên gộp tối đa là hai khoảng. Tương tự ta có thể gộp khoảng 7 và khoảng 8 thành khoảng [7,8]. Trong lưới thích nghi có hai thông số cần lưu ý đó là thông số α(thông số quyết định đến mức độ đậm đặc của khối) và thông số β là thông số quyết định khả năng gộp hai khoảng liền kề nhau. Nhận thấy số sinh viên đạt được điểm 10 là rất nhỏ( xét trên tất cả các học phần), do vậy điểm 10 thường khó có thể hình thành khoảng mật độ cao, ngay cả khi nếu cho phép gộp khoảng, với thông số β chung thì khoảng 10 cũng hiếm khi có thể gộp với khoảng 9. Do vậy điểm 10 khó có thể tham gia vào quá trình hình thành nhóm, tuy nhiên các điểm 10 thường liên quan nhiều đến các sinh viên tốt nghiệp giỏi, do vậy để điểm 10 có thể tham gia vào nhóm thì ta sẽ để các mức β là khác nhau. Tuy nhiên, không phải trường hợp nào ta cũng gộp như vậy, xét lược đồ phân bố dữ liệu của môn Ngôn ngữ C hình 3b. Nhận thấy khoảng 5 có mật độ là 280 chênh lệch rất lớn so với khoảng 6 có mật độ là 144, do vậy ta không nên gộp hai khoảng lại với nhau. Thay vào đó khoảng 6 có thể gộp với khoảng 7 thành khoảng [6,7]. Như vậy quá trình tiền xử lý để đưa ra các khoảng cho các chiều dữ liệu được thực hiện như sau: Đối với các điểm từ 0 đến 4, ta sẽ gộp thành một khoảng giá trị [0,4]. Đối với các điểm từ 5 đến 10, ta gộp các giá trị điểm theo kỹ thuật lưới thích nghi để được các khoảng lưới thích nghi sao cho kích thước mỗi khoảng tối đa là 2. Ví dụ với môn Cấu trúc máy tính và môn Ngôn ngữ C, sau khi thực hiện theo phương pháp trên (β=20% cho trường hợp thông thường, và β=70% khi gộp mức điểm xuất sắc) ta thu được các khoảng mới như sau: Công nghệ thông tin & Khoa học máy tính P.T.B.Vân, Đ.T.M.Hường, “Đề xuất giải pháp sử dụng lưới phân nhóm sinh viên.” 122 a. Cấu trúc máy tính b. Ngôn ngữ C Hình 3. Các khoảng lưới thích nghi của hai học phần.  Thuật toán: 4. THỰC NGHIỆM Đánh giá độ chính xác phân nhóm và so sánh với một số thuật toán phân nhóm khác. Tập dữ liệu thực nghiệm: Tập dữ liệu gồm 800 bản ghi, mỗi bản ghi gồm 27 thuộc tính (27 học phần) thu thập từ dữ liệu điểm sinh viên Khoa Công nghệ Thông tin, Học viện Kỹ thuật Quân sự. Cài đặt, thử nghiệm giải pháp đề xuất và hai thuật toán CLIQUE, thuật toán K-means để phân nhóm sinh viên theo hai trường hợp dự đoán loại tốt nghiệp và dự đoán tốt nghiệp đúng hạn. Đối với CLIQUE chúng tôi thực hiện với độ rộng khoảng lưới cố định là 1, đối Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 123 với K-means chúng tôi thực hiện phân thành 10 nhóm. Kết quả thu được bảng so sánh về độ chính xác so với phân nhóm dựa trên lưới thích nghi như sau: Bảng 1. So sánh độ chính xác dự đoán giữa các thuật toán. Phương pháp Dự đoán loại TN (%) Dự đoán TN đúng hạn(%) pMAFIA-TID - Lưới thích nghi 83 73 CLIQUE- Lưới cố định 77 63 K-means 74 65 Bởi vì quá trình phân nhóm có thể được thực hiện ở các thời điểm khác nhau trong khóa học, do vậy không gian dữ liệu là không đầy đủ (điểm khuyết thiếu nhiều). Bên cạnh đó dữ liệu phân bố không đều (số sinh viên tốt nghiệp khá chiếm số lượng vượt trội so với số sinh viên giỏi) do vậy việc dùng mô hình đề xuất cho kết quả tốt hơn hẳn so với hai phương pháp còn lại Bảng 2. Chi tiết độ chính xác dự báo loại tốt nghiệp. Phương pháp Loại tốt nghiệp Tỷ lệ chính xác trung bình Giỏi Khá TB pMAFIA-TID - Lưới thích nghi 100 57 90 83 CLIQUE - Lưới cố định 0 28 95 77 K-Means 100 42 84 74 Bảng 2 đưa ra so sánh chi tiết tỷ lệ dự báo chính xác đối với từng loại tốt nghiệp giữa ba thuật toán. Trong ba loại tốt nghiệp Giỏi, Khá và Trung bình thì số lượng sinh viên trung bình chiếm tỷ lệ nhiều nhất, do vậy các nhóm Trung bình thường đậm đặc nên phần trăm dự báo chính xác của các thuật toán đều cao. Tuy nhiên đối với loại Khá, số lượng sinh viên ít và phân bố dữ liệu điểm của cùng học phần của các sinh viên thuộc nhóm này khác nhau nhiều dẫn đến tỷ lệ dự báo chính xác thấp. Bảng 3. Chi tiết độ chính xác dự báo khả năng tốt nghiệp. Phương pháp Không đúng hạn Đúng hạn Tỷ lệ chính xác trung bình pMAFIA-TID – Lưới thích nghi 60 85 73 CLIQUE – Lưới cố định 92 38 63 K-means 57 71 65 Lưới cố định cho kết quả thấp trong dự báo tốt nghiệp đúng hạn, trong khi K-means dự báo kém hơn đối với các trường hợp không tốt nghiệp đúng hạn. 5. KẾT LUẬN Trong bài này chúng tôi đã trình bày tóm lược một số kết quả nghiên cứu của khai phá dữ liệu trong lĩnh vực giáo dục đào tạo và tổng quan về các phương pháp phân nhóm dữ liệu. Đề xuất giải pháp phân nhóm sinh viên sử dụng lưới thích nghi để nâng cao độ chính xác trong bài toán phân nhóm sinh viên. Hiệu quả của việc đề xuất này đã được chứng minh khi so sánh chất lượng nhóm với hai thuật toán CLIQUE và K-means. TÀI LIỆU THAM KHẢO [1]. Q. A. AI-Radaideh, E. W. AI-Shawakfa, and M. I. AI-Najjar, “Mining student data using decision trees”, ACIT'2006. [2]. S. Ayesha, T. Mustafa, A. R. Sattar, M. I. Khan, “Data mining model for higher education system”, Europen Journal of Scientific Research, 2010. [3]. C. Romero, S. Ventura, P. Espejo, C. Hervas. Data mining algorithms to classify students. Educational Data Mining Conference (EDM 2008). Công nghệ thông tin & Khoa học máy tính P.T.B.Vân, Đ.T.M.Hường, “Đề xuất giải pháp sử dụng lưới phân nhóm sinh viên.” 124 [4]. Jianwei Li, Ying Liu, Wei-Keng Lia, Alok Choudhary, “Parallel Data mining Algorithms for Association Rules and Clustering”. [5]. R. Agrawal, J. Gehrke, D. Gunopulos, P. Raghavan, “Automatic subspace clustering of high dimensional data for data mining applications”, In Proceedings of the ACM SIGMOD international conference , pages 94-105, ACM Press, 1998. [6]. S.Goil, H. Nagesh, A. Choudhary, “MAFIA: Efficient and scalable subspace clustering for very large data sets”. Technical Report CPDC-TR-9906-010, 1999. [7]. H.S. Nagesh,A.Choudhary, “A scalable parallel subspace clustering algorithm for massive data sets”, International Conference on Parallel Processing, 2000. [8]. K. Leung, C.Leckie, “Unsupervised A normaly Detection in Network Intrusion Detection using Cluster”, 28th Australasian Computer Science Conference, 2005. [9]. Nguyễn Mạnh Hùng, Phạm T Bích Vân, Đỗ Thị Mai Hường, “Một số cải tiến thuật toán phân nhóm song song dữ liệu lớn, nhiều chiều dựa trên lưới thích nghi pMAFIA”, Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, 2010. ABSTRACT PROPOSING A SOLUTION USING ADAPTIVE GRIDS TECHNIQUE IN CLUSTERING STUDENTS TO IMPROVE THE ACCURACY Nowadays, the educational data mining has become a new emerging technique of data mining which has attracted more scientists in the world. In this paper, we propose the model which uses clustering to classify students based on their grades. The purpose is to predict the students’ performing in graduation, and the prediction is useful for both educators and students in indentify the weak students to help them score better results. In the model, we use adaptive grids technique in the processing of data to improve cluster’s quality. Finally, we produce the compare of prediction accuracy between proposed model with other models like CLIQUE and K-means. Keywords: Prediction, Educational data mining, Clustering, Adaptive grids. Nhận bài ngày 02 tháng 4 năm 2014 Hoàn thiện ngày 14 tháng 5 năm 2015 Chấp nhận đăng ngày 12 tháng 6 năm 2015 Địa chỉ: Học viện Kỹ thuật quân sự; *Email: manhhungk12@mta.edu.vn.