Chương 1 Giới thiệu đề tài 1. Lý do nghiên cứu Khai phá dữ liệu (hay còn gọi là khám phá tri thức hoặc dữ liệu) đã trở thành lĩnh vực ngày càng quan trọng vì nó giúp phân tích và tổng kết dữ liệu thành những thông tin hữu ích [4]. Các dữ liệu được thu thập từ nhiều nguồn khác nhau tạo thành cơ sở dữ liệu và sử dụng các kỹ thuật hay công cụ khai thác nó nhằm giải quyết một vấn đề nào đó. Khai phá dữ liệu được ứng dụng trong nhiều lĩnh vực như tài chính, kinh tế, sinh học, chống khủng bố.
một trong những lĩnh vực được quan tâm nhiều gần đây là lĩnh vực giáo dục hay còn được gọi là khai phá dữ liệu giáo dục (EDM – Educational Data Mining). Các nghiên cứu tập trung vào việc khám phá dữ liệu đến từ môi trường giáo dục được thu thập từ mỗi sinh viên hay trường đại học nào đó, bao gồm các đặc trưng về hành vi học của sinh viên, giảng dạy của giáo viên. nhằm giúp cải thiện chương trình đào tạo, giảng dạy tốt hơn, đánh giá hệ thống giảng dạy trực tuyến, hay giúp sinh viên xác định mục tiêu học và nhiều lợi ích khác[4]. Thông tin về quá trình học tập của sinh viên là dữ liệu có sự gia tăng theo thời gian.
Thông thường có thể sử dụng một số phương pháp gom cụm gia tăng như K- means gia tăng, DBScan gia tăng.hay cả những giải thuật truyền thống gom cụm lại. Nhưng trong trường hợp, tập dữ liệu gia tăng rất ít dữ liệu việc gom cụm lại dẫn đến tốn chi phí, hay tập gia tăng có thêm đặc trưng thì lại khó xây dựng mô hình khi 6 sử dụng các giải thuật trên. Vì thế Kỹ thuật học chuyển đổi được đề xuất thực hiện trong đề tài này nhằm khắc phục các trường hợp trên. Mục đích nghiên cứu Có rất nhiều nghiên cứu về kỹ thuật học chuyển đổi nhưng thường là với tập dữ liệu có nhãn, còn đối với tập dữ liệu không nhãn thì số công trình đang còn hạn chế, nên việc lựa chọn giải thuật là một vấn đề khó khăn.
Ở đây chúng tôi hướng tới 2 giải thuật với 2 cách tiếp cận khác nhau. Một là Self-taught Clustering được công bố năm 2008 [5] có thể sử dụng khi tập gia tăng có thêm số đặc trưng và ít dữ liệu. Hai là kỹ thuật học chuyển đổi khác được công bố 2013 [15] khi tập gia tăng có ít dữ liệu. Dựa vào 2 giải thuật được đề xuất chúng tôi mong muốn thu được sẽ có những cụm có chất lượng tốt (những cụm sinh viên có quá trình học chưa tốt), để thực hiện gán nhãn hay dự đoán kết quả học tập của sinh viên.
Dựa vào kết quả có thể giúp giáo viên kịp thời quan tâm, đưa ra những phương pháp giảng dạy thích hợp hỗ trợ các em trong quá trình học tập. Ý nghĩa đề tài Đề tài đóng góp về ý nghĩa thực tiễn cũng như học thuật. • Về mặt học thuật: đề tài khai thác được 2 phương pháp học chuyển đổi với dữ liệu gia tăng trong gom cụm. • Về mặt thực tiễn: đưa ra phương pháp xử lý gom cụm gia tăng không giám sát.
Đánh giá mô hình trên tập dữ liệu sinh viên. • Về mặt khoa học: đề xuất được phương pháp gom cụm cho tập dữ liệu có sự thay đổi theo thời gian. Mô tả bài toán Phát biểu bài toán: - Thông tin đầu vào và đầu ra của bài toán được xác định như sau: • Phần nhập: tập dữ liệu ban đầu, tập dữ liệu gia tăng. • Thực hiện: – Dựa vào thông tin có được từ tập dữ liệu là điểm số của sinh viên, tiến hành gom cụm những sinh viên có điểm số tương đồng với nhau.
– Khảo sát một số giải pháp gom cụm gia tăng. – Nhận xét và đánh giá kết quả. • Phần xuất: các cụm có chất lượng. Phạm vi đề tài: Phạm vi nghiên cứu của đề tài trước mắt tập trung vào việc đưa ra một quy trình thực hiện gom cụm gia tăng bằng phương pháp học chuyển đổi như thế nào với tập dữ liệu trong môi trường giáo dục.
Kiểm tra, đánh giá tính hiệu quả mô hình. Đề tài sẽ chưa xét đến vấn đề “từ chối việc học” (Negative transfer), 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,. Quy trình nghiên cứu Để thực hiện các mục tiêu đề ra, cần thực hiện từng bước những mục tiêu nhỏ như sau: • Xử lý tập dữ liệu thành 2 phần: tập ban đầu và tập gia tăng để phục vụ cho quá trình gom cụm. • Lựa chọn đặc trưng thu hẹp khoảng cách giữa tập hỗ trợ và tập đích để xây dựng mô hình gom cụm bằng phương pháp học chuyển đổi Sefl-taught clus- tering.
• Nghiên cứu công trình [15] để cải tiến phương pháp học chuyển đổi cho phù hợp với tập dữ liệu giáo dục và tiến hành xây dựng mô hình. • Xây dựng mô hình gom cụm bằng K-means gia tăng. • Kiểm tra, đánh giá các mô hình gom cụm gia tăng và báo cáo kết quả. 8 Chương 2 Cơ sở lý thuyết 2.
Gom cụm trong khai phá dữ liệu Gom cụm là quá trình phân chia một tập dữ liệu thành các tập con. Mỗi tập con là một cụm mà các đối tượng trong cụm có đặc điểm tương đồng với nhau và khác đặc điểm với đối tượng nằm trong cụm khác. Việc phân chia các cụm được thực hiện bởi các giải thuật, các phương pháp khác nhau sẽ sinh ra các cụm khác nhau trên cùng tập dữ liệu. Lợi ích của việc gom cụm giúp ta khám phá ra các cụm thông tin hữu ích mà khó thấy trong tập dữ liệu lớn trước đó [7].
Gom cụm được ứng dụng trong nhiều lĩnh vực như: hỗ trợ giai đoạn tiền xử lý dữ liệu, nhận dạng hình ảnh, bảo mật, sinh học, kinh doanh. Độ tương tự giữa các đối tượng được xác định qua độ đo khoảng cách [7]. Độ đo khoảng cách có nhiều công thức tính tùy thuộc vào kiểu dữ liệu của đối tượng. Các kiểu dữ liệu và độ đo tương tự Tùy thuộc vào kiểu dữ liệu có giá trị thuộc tính là số nguyên, số thực hay kiểu nhị phân.
mà chúng ta sử dụng độ đo khác nhau. Dưới đây là một số công thức tính khoảng cách (độ đo tương tự) giữa các đối tượng trong tập dữ liệu khi thực hiện gom cụm. * Thuộc tính có kiểu định khoảng (interval-scaled) 9 Khoảng cách q Minkowski d (i, j) = q |xi1 − x j1 |q + |xi2 − x j2 |q + .1) Khoảng cách q Euclidean d (i, j) = |xi1 − x j1 |2 + |xi2 − x j2 |2 + .2) Khoảng cách Manhattan d (i, j) = xi1 − x j1 + xi2 − x j2 +.3) * Thuộc tính có kiểu nhị phân (Binary) đối tượng j i 1 0 sum 1 a b a+b 0 c d c+d sum a+c b+d b+c Hệ số so trùng đơn giản (nếu đối xứng): d (i, j) = a+b+c+d (1.4) b+c Hệ số so trùng Jaccard (nếu bất đối xứng): d (i, j) = a+b+c (1.5) * Đối tượng có dạng là vector • Đối tượng i và j được biểu diễn tương ứng bởi vector x và y. • Độ tương tự (similarity) giữa i và j được tính bởi độ đo cosine: x.
Độ đo đánh giá kết quả gom cụm • Có 3 loại độ đo. – Độ đo đánh giá ngoại (external validation): đánh giá kết quả gom cụm dựa vào các cụm được chỉ định trước cho tập dữ liệu. Đây cũng là độ đo được sử dụng trong phần đánh giá kết quả gom cụm của các giải thuật. Cụ thể là độ đo Entropy: ∗ Phân vùng P: kết quả gom cụm trên n đối tượng.
10 ∗ Phân vùng C: các cụm thật sự của n đối tượng. ∗ ni j = Pi ∩C j Hình 2.1: Contingency table Dựa vào Contingency table công thức tính Entropy như sau: ni j ni j TotalEntropy = − ∑ nni. i j Giá trị Entropy càng nhỏ càng cho cụm có chất lượng càng tốt. – Độ đo đánh giá nội (internal validation): đánh giá kết quả gom cụm theo số lượng các vector của chính tập chính tập dữ liệu.
– Độ đo đánh giá tương đối (relative validation): đánh giá kết quả gom cụm bằng việc so sánh các kết quả gom cụm khác ứng với các bộ trị thông số khác nhau. • Tiêu chí cho việc đánh giá và chọn kết quả gom cụm tối ưu – Độ chặt chẽ (compactness): các đối tượng trong cụm nên gần nhau. – Độ phân tách (separation): các cụm nên xa nhau. Quy trình gom cụm Hình 2.2: Quy trình gom cụm dữ liệu [13] Thủ tục gom cụm có 4 bước cơ bản sau: • 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. • 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 hưởng tới việc lựa chọn thuật toán. • 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. • 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.
Để đảm bảo độ tin cậy của tri thức thì các chuyên gia trong nhiều lĩnh vực liên quan cần giải thích các phân vùng dữ liệu, phân tích sâu hơn, thậm chí là thí nghiệm. Các phương pháp gom cụm tiêu biểu • Phân hoạch (K-means,PAM.