Tối ưu hóa dữ liệu giáo dục trong luận văn thạc sĩ khoa học máy tính

Khám phá luận văn thạc sĩ khoa học máy tính về gom cụm dữ liệu giáo dục gia tăng, ứng dụng và tiềm năng trong nghiên cứu hiện đại.

• Tác giả: Tạ Minh Tuấn
• Người hướng dẫn: TS. Võ Thị Ngọc Châu
• Trường học: Đại học Bách Khoa - ĐHQG TP. Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Gom Cụm Dữ Liệu Giáo Dục Gia Tăng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu đề tài

Trong bối cảnh hiện nay, với sự phát triển nhanh chóng của công nghệ thông tin, việc thu thập và xử lý dữ liệu giáo dục ngày càng trở nên quan trọng. Tối ưu hóa dữ liệu giáo dục không chỉ giúp nâng cao chất lượng giảng dạy mà còn hỗ trợ cho việc ra quyết định trong quản lý giáo dục. Luận văn thạc sĩ này tập trung vào việc nghiên cứu và áp dụng các thuật toán gom cụm như K-Means và DBSCAN nhằm mục đích phân tích dữ liệu giáo dục gia tăng. Việc lựa chọn thuật toán phù hợp sẽ là yếu tố quyết định đến hiệu quả của quá trình phân tích dữ liệu. Theo đó, việc gom cụm dữ liệu giúp giáo viên hiểu rõ hơn về đặc điểm của các nhóm sinh viên, từ đó đưa ra những phương pháp giảng dạy phù hợp.

1.1 Lý do nghiên cứu

Sự gia tăng nhanh chóng của dữ liệu giáo dục đã tạo ra nhu cầu cấp thiết trong việc khai thác và phân tích thông tin từ những dữ liệu này. Phân tích dữ liệu giáo dục không chỉ giúp cải thiện chất lượng giảng dạy mà còn hỗ trợ các nhà quản lý trong việc đưa ra quyết định. Từ đó, việc tối ưu hóa dữ liệu giáo dục thông qua các thuật toán gom cụm sẽ giúp phát hiện ra những xu hướng và đặc điểm nổi bật trong quá trình học tập của sinh viên.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản về gom cụm dữ liệu trong lĩnh vực khai phá dữ liệu. Gom cụm là một phương pháp quan trọng trong khai phá dữ liệu giáo dục, giúp nhóm các đối tượng tương tự lại với nhau. Các thuật toán như K-Means và DBSCAN được phân tích chi tiết, chỉ ra ưu và nhược điểm của từng phương pháp. Đặc biệt, K-Means thường được ưa chuộng do tính đơn giản và hiệu quả, tuy nhiên, nó gặp khó khăn trong việc phát hiện các điểm dữ liệu khác biệt. Ngược lại, DBSCAN có khả năng phát hiện các cụm không hình tròn và có thể xử lý tốt với dữ liệu có nhiễu.

2.1 Gom cụm trong khai phá dữ liệu

Gom cụm dữ liệu là quá trình nhóm các đối tượng tương tự lại với nhau trong cùng một cụm. Để đánh giá chất lượng của các cụm, các tiêu chí như độ tương tự và khoảng cách giữa các đối tượng được sử dụng. Phân tích dữ liệu thông qua việc gom cụm sẽ giúp giáo viên hiểu rõ hơn về các nhóm sinh viên, từ đó đưa ra các phương pháp hỗ trợ học tập hiệu quả hơn.

III. Giải pháp gom cụm dữ liệu gia tăng

Giải pháp gom cụm dữ liệu gia tăng sử dụng hai thuật toán chính là K-Means gia tăng và DBSCAN gia tăng. Các thuật toán này được áp dụng để xử lý dữ liệu giáo dục có sự gia tăng theo thời gian. Kết quả thực nghiệm cho thấy việc sử dụng K-Means gia tăng cho phép xử lý dữ liệu mới một cách hiệu quả, trong khi DBSCAN gia tăng giúp phát hiện các cụm không đồng nhất. Việc so sánh các kết quả thu được từ hai phương pháp này sẽ giúp xác định phương pháp nào phù hợp hơn với dữ liệu giáo dục gia tăng.

3.1 Gom cụm dữ liệu gia tăng với thuật toán K Means gia tăng

Thuật toán K-Means gia tăng cho phép cập nhật các cụm khi có dữ liệu mới mà không cần phải thực hiện lại toàn bộ quá trình gom cụm từ đầu. Điều này giúp tiết kiệm thời gian và tài nguyên. Kết quả thực nghiệm cho thấy K-Means gia tăng có thể duy trì chất lượng cụm tốt khi dữ liệu gia tăng, tuy nhiên vẫn cần xem xét đến độ chính xác của các cụm được hình thành.

3.2 Gom cụm dữ liệu gia tăng với thuật toán DBSCAN gia tăng

DBSCAN gia tăng cho phép phát hiện các cụm mới trong dữ liệu gia tăng mà không cần phải tái cấu trúc toàn bộ dữ liệu. Phương pháp này rất hiệu quả trong việc phát hiện các điểm ngoại lai và các cụm có hình dạng phức tạp. Kết quả thực nghiệm cho thấy DBSCAN gia tăng có thể cải thiện đáng kể khả năng phát hiện các cụm trong dữ liệu giáo dục gia tăng, từ đó cung cấp thông tin hữu ích cho giáo viên trong việc điều chỉnh phương pháp giảng dạy.

IV. Kết quả thực nghiệm

Kết quả thực nghiệm từ việc áp dụng hai thuật toán K-Means và DBSCAN cho thấy sự khác biệt rõ rệt trong khả năng gom cụm và phát hiện các điểm ngoại lai. Các số liệu đánh giá như độ đo Dunn và Silhouette được sử dụng để so sánh chất lượng các cụm. Kết quả cho thấy K-Means thường cho các cụm đồng nhất hơn, trong khi DBSCAN phát hiện được nhiều cụm không đồng nhất hơn, điều này rất quan trọng trong việc phân tích dữ liệu giáo dục.

4.1 Kết quả thực nghiệm sử dụng thuật toán K Means

Kết quả từ thuật toán K-Means cho thấy khả năng gom cụm tốt với các thông số k khác nhau. Tuy nhiên, một số cụm vẫn có thể bị ảnh hưởng bởi các điểm ngoại lai. Việc điều chỉnh tham số k là rất quan trọng để đạt được kết quả tối ưu trong việc phân tích dữ liệu giáo dục.

4.2 Kết quả thực nghiệm sử dụng thuật toán DBSCAN

DBSCAN cho thấy sự vượt trội trong việc phát hiện các cụm không đồng nhất và các điểm ngoại lai. Kết quả thực nghiệm cho thấy DBSCAN có thể điều chỉnh tốt với các tham số eps và minPts để đạt được chất lượng cụm tốt hơn. Việc này cho thấy DBSCAN là một lựa chọn khả thi cho việc phân tích dữ liệu giáo dục gia tăng.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu đề tài 1.1 Lý do nghiên cứu Ngày nay, với sự phát triển vượt bậc của công nghệ thông tin và truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin ngày càng nâng cao. Với lượng dữ liệu tăng nhanh và khổng lồ như vậy, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai phá hiệu quả các cơ sở dữ liệu (CSDL) lớn, một lĩnh vực khoa học mới ra đời: Khám phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD). Khai phá dữ liệu (Data Mining) là một công đoạn chính trong quá trình KDD.

Trong những năm gần đây, khai phá dữ liệu được ứng dụng trong rất nhiều lĩnh vực như: thương mại điện tử, viễn thông, thể thao, y tế, thiên văn học, đầu tư… Đặc biệt là đối với giáo dục, khai phá dữ liệu trong lĩnh vực này được gọi là Khai phá Dữ liệu Giáo dục (Educational Data Mining –EDM). EDM là quá trình chuyển đổi dữ liệu thô của hệ thống giáo dục thành các thông tin hữu ích, được dùng cho việc ra quyết định cũng như trả lời các câu hỏi nghiên cứu trong lĩnh vực giáo dục [4]. Một trong những bài toán được đề cập nhiều trong khai phá dữ liệu giáo dục là bài toán gom cụm dữ liệu [13]. Hiện nay, việc học theo hệ thống tín chỉ trở nên phổ biến trong các trường cao đẳng, đại học ở nước ta.

Vì thế, việc gom cụm dữ liệu giáo dục sẽ cung cấp cho giáo viên bản chất của nhóm sinh viên, từ đó có những yêu cầu, hướng dẫn, hỗ trợ thích hợp cho từng nhóm sinh viên. Bên cạnh đó, dữ liệu về quá trình học tập của các sinh viên ngày càng gia tăng theo thời gian. Việc tiến hành gom cụm trên tập dữ liệu gia tăng này cũng là 1 vấn đề cấp thiết. Nó thể hiện quá trình thay đổi trong học tập của sinh viên.

Từ đây, giáo viên có những điều chỉnh trong quá trình dạy học phù hợp hơn với sinh viên. Chính vì vậy, việc gom cụm dữ liệu giáo dục và gom cụm dữ liệu giáo dục gia tăng rồi đánh giá chất lượng cụm nhằm tìm ra các cụm có chất lượng tốt phục vụ cho quá trình dạy và học là cần thiết đối với hệ thống giáo dục theo tín chỉ.2 Mục đích nghiên cứu Hiện nay, có rất nhiều giải thuật gom cụm dữ liệu và việc lựa chọn giải thuật nào thích hợp cho việc gom cụm dữ liệu và gom cụm dữ liệu gia tăng trong giáo dục cũng là 1 vấn đề cần quan tâm. Chính vì vậy, đề tài chúng tôi hướng tới việc lựa chọn giải thuật thích hợp cho dữ liệu giáo dục bằng cách so sánh, đánh giá chất lượng gom cụm sau khi thực hiện 1 gom cụm dữ liệu và gom cụm dữ liệu gia tăng bằng 2 giải thuật khác nhau là K- Means và DBSCAN. Lí do chúng tôi chọn K-Means là bởi vì thuật toán này đơn giản, và có rất nhiều công trình gom cụm dữ liệu đã sử dụng giải thuật này hoặc cải tiến của nó.

Tuy nhiên, nhược điểm của giải thuật K-Means là không phát hiện ra các phần tử khác biệt so với số đông các phần tử còn lại. Để khắc phục nhược điểm này, chúng tôi sẽ sử dụng giải thuật DBSCAN nhằm phát hiện các phần tử khác biệt đó. Điều này rất quan trọng, đặc biệt là trong lĩnh vực giáo dục. Việc phát hiện ra các sinh viên có trình độ khác biệt so với phần đông các sinh viên còn lại giúp giảng viên quan tâm hơn tới các sinh viên này, nhằm đưa ra phương pháp giảng dạy thích hợp, hỗ trợ các em tốt hơn trong quá trình học tập.3 Phạm vi nghiên cứu Trong phạm vi đề tài không xem xét tới các vấn đề liên quan đến tiền xử lý dữ liệu như thêm điểm còn thiếu,….

Bên cạnh đó, việc xác định tham số k cho thuật toán K-Means, tham số minpoint và eps cho thuật toán DBSCAN một scách tự động cũng không được xem xét tới.4 Quy trình nghiên cứu Quy trình gom cụm dữ liệu giáo dục sẽ được tiến hành theo quy trình gom cụm dữ liệu trong hình 1. Đối với bài toán gom cụm dữ liệu giáo dục gia tăng thì input và output của bài toán được xác định như sau: o Input: là tập dữ liệu gốc đã được tiến hành gom cụm và tập dữ liệu gia tăng chứa các thuộc tính về điểm của sinh viên. o Output: là các cụm sinh viên có chất lượng cao. Bước 1: tiến hành gom cụm dữ liệu gia tăng với thuật toán DBSCAN gia tăng.

Bước 2: bên cạnh đó cũng sử dụng thuật toán K-Means gia tăng để tiến hành gom cụm dữ liệu gia tăng. Bước 3: ứng với quá trình gom cụm theo từng thuật toán, sẽ tiến hành đánh giá kết quả gom cụm dựa trên 2 độ đo là Dunn và Silhouette Bước 4: dựa trên 2 độ đo ở trên và các tiêu chí khác để so sánh chất lượng gom cụm dữ liệu gia tăng. 2 Chương 2: Cơ sở lý thuyết 2.1 Gom cụm trong khai phá dữ liệu Gom cụm dữ liệu là việc nhóm các đối tượng gần nhau vào trong cùng một cụm (cluster). Một cụm là một tập các đối tượng sao cho khoảng cách (độ tương tự) giữa các thành viên trong cùng một cụm là gần nhau (tương tự), còn với các đối tượng khác cụm thì xa nhau [7].

Sự tương tự / không tương tự giữa các đối tượng thường được biểu diễn qua độ đo khoảng cách d(x,y) và độ đo khoảng cách này được tính tùy thuộc vào kiểu dữ liệu của đối tượng [7].2 Các kiểu dữ liệu và độ đo tương tự Ứng với mỗi kiểu dữ liệu sẽ có 1 hàm khoảng cách d(x,y) để xác định khoảng cách giữa 2 đối tượng trong tập dữ liệu. Các độ đo này được xác định trong không gian metric. Một tập dữ liệu D là không gian metric nếu: ∀ (𝑥, 𝑦) ∈ 𝐷, xác định được số thực d(x,y) theo quy tắc nhất định và số thực d(x,y) được gọi là khoảng cách của (x,y). Quy tắc này phải thỏa mãn các tính chất sau:  𝑑 (𝑥, 𝑦) > 0 𝑛ế𝑢 𝑥 ≠ 𝑦  𝑑 (𝑥, 𝑦) = 0 𝑛ế𝑢 𝑥 = 𝑦  𝑑 (𝑥, 𝑦) = 𝑑 (𝑦, 𝑥)  𝑑 (𝑥, 𝑦) ≤ 𝑑 (𝑥, 𝑧) + 𝑑(𝑧, 𝑦) 2.1 Thuộc tính có kiểu trị-khoảng (interval-scaled) Nếu thuộc tính có kiểu trị-khoảng thì sau khi chuẩn hóa độ đo phi tương tự được tính theo các khoảng cách sau: 1 𝑛  Khoảng cách Minkowski 𝐷𝑖𝑗 =(∑𝑑𝑙=1|𝑥𝑖𝑙 − 𝑥𝑗𝑙 |𝑛 ) (1.1) 1 2  𝑑 Khoảng cách Euclidean 𝐷𝑖𝑗 =(∑𝑙=1|𝑥𝑖𝑙 − 𝑥𝑗𝑙 |2 ) (1.2)  Khoảng cách Manhattan 𝐷𝑖𝑗 =(∑𝑑𝑙=1|𝑥𝑖𝑙 − 𝑥𝑗𝑙 | ) (1.2 Thuộc tính có kiểu nhị phân (Binary) Nếu đối tượng có kiểu nhị phân thì độ tương tự được tính như sau: 3 Bảng 1: Công thức tính độ tương tự của thuộc tính có kiểu nhị phân.

Đối tượng j 1 0 sum 1 a b a+b Đối tượng i 0 c d c+d Sum a+c b+d P = a+b+c+d 𝑏+𝑐  Hệ số so trùng đơn giản (nếu đối xứng) 𝑑 (𝑖, 𝑗) = (1.4) 𝑎+𝑏+𝑐+𝑑 𝑏+𝑐  Hệ số so trùng Jaccard (nếu bất đối xứng) 𝑑 (𝑖, 𝑗) = (1.3 Thuộc tính có kiểu Categorical Bao gồm thuộc tính có kiểu định danh (Nominal scale) và thuộc tính có kiểu thứ tự (Ordinal scale) Đối với thuộc tính có kiểu định danh thì hàm khoảng cách được tính theo công 𝑝−𝑚 thức 𝑑 (𝑥, 𝑦) = (1.6) 𝑝 trong đó p là tổng số các thuộc tính và m là số thuộc tính đối sánh trùng nhau. Đối với thuộc tính có kiểu thứ tự thì độ đo phi tương tự giữa các đối tượng được thực hiện như sau. Giả sử I là thuộc tính thứ tự có Mi giá trị: Các trạng thái Mi được sắp thứ tự [1.Mi], thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri với ri ∈ {1,.,Mi} Mỗi thuộc tính thứ tự có các miền giá trị khác nhau, vì vậy chuyển chúng về miền giá trị [0,1] bằng cách thực hiện phép biến đổi theo công thức sau: (𝑖) (𝑖) 𝑟𝑖 −1 𝑍𝑖 = (1.4 Thuộc tính có kiểu khoảng-tỉ lệ (ratio-scaled) Nếu đối tượng có kiểu khoảng –tỉ lệ thì sử dụng biến đổi thuộc tính xi thành qi theo công thức sau: 𝑞𝑖 = log 𝑥𝑖 (1.5 Thuộc tính có kiểu hỗn hợp (mixed typed) Nếu đối tượng có kiểu nhị phân thì độ tương tự được tính như sau: (𝑓) (𝑓) ∑ 𝑝𝑓=1 𝛿𝑖𝑗 𝑑𝑖𝑗 𝑑 (𝑖, 𝑗) = (𝑓) (1.9) ∑ 𝑝𝑓=1 𝛿𝑖𝑗 (𝑓)  Nếu xif hoặc xjf bị thiếu (missing) thì 𝛿𝑖𝑗 = 0 (𝑓) (𝑓)  Nếu f có kiểu binary (nominal): 𝑑𝑖𝑗 = 0 𝑛ế𝑢 𝑥𝑖𝑓 = 𝑥𝑗𝑓 , ngược lại 𝑑𝑖𝑗 = 1  Nếu f có kiểu interval-scaled sử dụng độ đo Minkowski (1.2)  Nếu f có kiểu ordinal hoặc ratio-scaled 4 𝑟𝑖𝑓 −1  Tính ranks rif và 𝑍𝑖𝑓 = 𝑀𝑓 −1  Zif trở thành interval-scaled 2.3 Quy trình gom cụm dữ liệu Clustering Feature Selection Algorithm Design or Extraction or Selection Data Samples Clusters Clusters Results Interpretation Validation Knowledge Hình 1: Quy trình gom cụm dữ liệu [14] Thủ tục gom cụm có 4 bước cơ bản sau: o Khai thác hoặc lựa chọn thuộc tính (Feature Selection or Extraction): Mỗi đối tượng có nhiều thuộc tính, tuy nhiên không nhất thiết phải sử dụng tất cả các thuộc tính này. Ta có thể chọn ra các thuộc tính đặc trưng của đối tượng hoặc có thể sử dụng 1 số biến đổi để tạo ra các thuộc tính hữu ích cho quá trình gom cụm dữ liệu.

o Lựa chọn hoặc thiết kế thuật toán gom cụm (Clustering Algorithm Design or Selection): kết hợp với việc lựa chọn độ đo tương tự giữa các đối tượng. Việc lựa chọn độ đo này sẽ ảnh hưởng trực tiếp tới sự hình thành các cụm kết quả cũng như ảnh hưởng tới việc lựa chọn thuật toán. o Xác nhận cụm (Clusters Validation): Với 1 tập dữ liệu, mỗi thuật toán phân cụm luôn có thể tạo ra sự phân chia cụm, tuy nhiên với mỗi cách tiếp cận khác nhau sẽ dẫn đến kết quả là các cụm khác nhau. Ngay cả với cùng 1 thuật toán, việc xác định tham số hoặc các mẫu đầu vào cũng có thể ảnh hưởng tới kết quả cuối cùng.

Vì vậy, các tiêu chí cũng như các tiêu chuẩn đánh giá hiệu quả là rất quan trọng để cung cấp cho người dùng các kết quả đáng tin cậy. Những đánh giá này cần phải khách quan và không thiên vị thuật toán nào. o Giải thích kết quả (Results Interpretation): Mục tiêu cuối cùng của phân cụm là cung cấp cho người dùng những hiểu biết ý nghĩa từ dữ liệu gốc, để họ có thể giải quyết hiệu quả các vấn đề gặp phải.