Đề 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

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