HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Đỗ Văn Minh ỨNG DỤNG PHÂN CỤM DỮ LIỆU TRONG PHÂN TÍCH,
ĐÁNH GIÁ KẾT QUẢ ĐIỂM CỦA HỌC SINH Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013 Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG


Ngành giáo dục nói chung và các trường học nói riêng có lượng dữ
liệu lưu trữ khá lớn nhưng việc phân tích, đánh giá để đưa ra các chiến lược
phát triển phù hợp, cung cấp chất lượng giáo dục tốt hơn và hỗ trợ các hoạt
động quản lí hiện nay chưa thực sự được quan tâm đúng mức và khai thác
có hiệu quả.
Với những lý do như vậy tôi chọn đề tài “Ứng dụng phân cụm dữ
liệu trong phân tích, đánh giá kết quả điểm của học sinh” làm đề tài luận
văn tốt nghiệp.
Bố cục luận văn gồm 3 chương:
Chương 1: Tìm hiểu tổng quan về khai phá dữ liệu và kỹ thuật
phân cụm dữ liệu trong KPDL.
Chương 2: Tìm hiểu một số thuật toán điển hình trong phân cụm
dữ liệu.
Chương 3: Ứng dụng thuật toán k-means để thử nghiệm phân cụm
trên dữ liệu điểm của học sinh.

2

CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ
PHÂN CỤM DỮ LIỆU
1.1 Khai phá dữ liệu
1.1.1. Giới thiệu về Khai phá dữ liệu
Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những
năm cuối thập kỷ 80 của thế kỉ XX. Khai phá dữ liệu là một lĩnh vực được
nghiên cứu nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn
từ các CSDL lớn, kho dữ liệu…
Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những
hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT
trên thế giới. Trong những năm gần đây, rất nhiều các phương pháp và
thuật toán mới về KPDL liên tục được công bố. Điều này chứng tỏ những

cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không
tương đồng.
Phân cụm dữ liệu là một kỹ thuật trong KPDL nhằm tìm kiếm,
phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập
dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.
4

Phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí
cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc
điểm, có tác dụng trong việc phát hiện ra các cụm.
1.2.2 Một số khái niệm cần thiết khi tiếp cận phân cụm dữ
liệu
1.2.2.1 Các kiểu dữ liệu và thuộc tính trong phép phân cụm
1.2.2.2 Đo độ tương đồng

1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
- Có khả năng mở rộng
- Thích nghi với các kiểu dữ liệu khác nhau
- Khám phá ra các cụm với hình thù bất kỳ
- Tối thiểu lượng tri thức cần cho xác định các tham số vào
- Khả năng thích nghi với dữ liệu nhiễu cao
- Ít nhạy cảm với các tham số đầu vào
- Thích nghi với dữ liệu đa chiều
- Dễ hiểu, dễ cài đặt và khả thi
1.2.4 Các hướng tiếp cận trong phân cụm dữ liệu
1.2.4.1 Phương pháp phân hoạch (Partitioning Methods) chia một
tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm
được thiết lập. Số các cụm được thiết lập là các đặc trưng được lựa chọn
trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu trong không
gian Euclid.

6

CHƯƠNG II. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU
ĐIỂN HÌNH
2.1 Các thuật toán phân cụm phân hoạch
2.1.1 Thuật toán K-means
Đầu vào: Một CSDL gồm n đối tượng và số các cụm k.
Đầu ra: Các cụm C
i
(i=1, ,k) sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu.
Bước 1: Khởi tạo
Chọn k đối tượng m
j
(j=1 k) là trọng tâm ban đầu của k cụm từ tập dữ liệu

Bước 2: Tính toán khoảng cách
Đối với mỗi đối tượng X
i
(i=1, ,n) , tính toán khoảng cách từ nó tới mỗi
trọng tâm m
j
với j=1, ,k; sau đó tìm trọng tâm gần nhất đối với mỗi đối
tượng.
Bước 3: Cập nhật lại trọng tâm
Đối với mỗi j=1, ,k; cập nhật trọng tâm cụm m
j
bằng cách xác định trung
bình
cộng của các véc-tơ đối tượng dữ liệu.
Bước 4: Điều kiện dừng

For i=1 to numlocal do
Begin
Khởi tạo ngẫu nhiên k đối tượng medois
j = 1;
while j < maxneighbor do
Begin
Chọn ngẫu nhiên một láng giềng R của S.
Tính toán độ phi tương tự về khoảng cách giữa 2 láng giềng S và R.
Nếu R có chi phí thấp hơn thì hoán đối R cho S và j=1
ngược lại j++;
End;
8

Kiểm tra khoảng cách của phân hoạch S có nhỏ hơn khoảng cách nhỏ nhất
không, nếu nhỏ hơn thì lấy giá trị này để cập nhật lại khoảng cách nhỏ nhất
và phân hoạch S là phân hoạch tốt nhất tại thời điểm hiện tại.
End.

2.2 Các thuật toán phân cụm phân cấp
2.2.1 Thuật toán BIRCH
Bước 1: Duyệt tất cả các đối tượng trong CSDL và xây dựng một cây CF
khởi tạo. Một đối tượng được chèn vào nút lá gần nhất tạo thành cụm con.
Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi một
đối tượng thích hợp được chèn vào nút lá, tất cả các nút trỏ tới gốc của cây
được cập nhật với các thông tin cần thiết.
Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành xây
dựng một cây CF nhỏ hơn bằng cách điều khiển bởi tham số T (vì tăng T
sẽ làm hoà nhập một số các cụm con thành một cụm, điều này làm cho cây
CF nhỏ hơn). Bước này không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu
nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn.

2.3.1 Thuật toán DBSCAN
Input: Tập dữ liệu D chứa n đối tượng, ε là tham số bán kính và MinPts
ngưỡng mật độ láng giềng.
Output: Tập các cụm dựa trên mật độ.
(1) đánh dấu tất cả các đối tượng là chưa thăm;
(2) lặp
(3) lựa chọn ngẫu nhiên một đối tượng chưa thăm p;
10

(4) đánh dấu đã thăm p;
(5) nếu các ε láng giềng của p có ít nhất MinPts đối tượng
(6) tạo mới một cụm C và thêm p vào C;
(7) cho N là tập các đối tượng trong ε láng giềng của p;
(8) lặp: với mỗi điểm p’ trong N
(9) nếu p’chưa thăm
(10) đánh dấu p’ đã thăm;
(11) nếu ε láng giềng của p’ có ít nhất MinPts điểm,
thêm những điểm này đến N;
(12) nếu p’không phải là thành viên của bất kỳ cụm nào, thêm p’ vào C;
(13) kết thúc lặp
(14) đưa ra C;
(15) ngược lại đánh dấu p như là nhiễu;
(16) cho đến khi thăm hết các đối tượng;

2.3.2 Thuật toán DENCLUDE
DENCLUDE là phương pháp dựa trên một tập các hàm phân phối
mật độ và được xây dựng trên các ý tưởng như sau :
- Sự ảnh hưởng của mỗi điểm dữ liệu có thể biểu diễn dưới dạng
mô hình qua hàm toán học, được gọi là hàm ảnh hưởng (influence fuction),
dùng để mô tả tác động của điểm dữ liệu với các đối tượng láng giềng của

tượng dữ liệu trong số các đối tượng láng giềng cho trước).
Bước 2: Xác định không gian con chứa các cụm được sử dụng nguyên lý
Apriori.
12

Bước 3: Hợp các hình hộp này tạo thành các cụm dữ liệu.
Bước 4: Xác định các cụm: Trước hết nó tìm các ô đặc đơn chiều, tiếp
đến chúng tìm các hình chữ nhật 2 chiều, rồi 3 chiều,…, cho đến khi
hình hộp chữ nhật đặc k chiều được tìm thấy.

2.5 Các thuật toán phân cụm dựa trên mô hình
2.5.1 Thuật toán EM
1. Khởi tạo tham số
(0) (0) (0) (0) (0) (0)
0 1 2 1 2
{ , , , , , , , }
k k
p p p
   


2. Bước E
( ) 2 ( )
( ) 2 ( )
(x | , ) ( , )
( | , , )P
( | , )
( , ) ( | , , )P
t t
k j t j t


 



( 1)
( | , )
i k t
t
k
i
P x
p
R
 




4. Lặp lại bước 2, 3 cho đến khi đạt kết quả 13

2.5.2 Thuật toán COBWEB
1) Khởi tạo cây bắt đầu bằng một nút rỗng.
2) Sau khi thêm vào từng nút một và cập nhật lại cây cho phù hợp tại

w ( ) ( )( w
ji j I x i ji
t T t x

  
với
, ( )
( )
j I x
T t
là Gauss lân cận và
( )t

là tỷ lệ học.
Bước 5: Lặp lại
Lặp lại bước 2 cho đến khi giải thuật tối ưu hoặc đạt đến số lần lặp xác
định N cho trước.
14 2.6 Các thuật toán phân cụm có dữ liệu ràng buộc
2.6.1 Thuật toán K-Prototype
Input: Tập dữ liệu ban đầu X và số cụm k.
Output: k đối tượng mẫu sao cho hàm tiêu chuẩn đạt giá trị tối thiểu.
Bước 1: Khởi tạo k đối tượng mẫu ban đầu cho X, mỗi đối tượng mẫu
đóng vai trò là tâm đại diện của mỗi cụm.
Bước 2: Phân phối mỗi đối tượng trong X cho mỗi cụm sao cho chúng
gần nhất với đối tượng mẫu trong cụm, đồng thời cập nhật lại đối
tượng mẫu cho mỗi cụm.
Bước 3: Sau khi tất cả các đối tượng đã được phân phối hết cho các

hình được giải quyết tốt.
Sau đây là tổng hợp các đặc tính của các phương pháp và các thuật
toán PCDL nhằm làm căn cứ cho việc lựa chọn phương pháp khi phát triển
các ứng dụng khác. Tùy vào từng ứng dụng và căn cứ vào các đặc tính của
thuật toán ta có thể tìm được các thuật toán phù hợp để áp dụng cho bài toán
thực tế.
16

CHƯƠNG 3. ỨNG DỤNG THUẬT TOÁN PHÂN CỤM
K-MEANS TRONG PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢ
ĐIỂM CỦA HỌC SINH.
3.1 Đặt vấn đề
Cuối mỗi học kì, mỗi năm học dựa trên kết quả điểm trung bình
(ĐTB) của học sinh các thầy, cô giáo, các nhà quản lý giáo dục đều muốn
có được những thông tin tổng hợp về tình hình học tập của trường, của lớp.
Những cách thống kê thường thấy như:
- Tính ĐTB theo bộ môn của từng giáo viên, từng lớp, từng khối
hoặc toàn trường …
- Đếm số lượng ĐTB trong ngưỡng nào đó. Ví dụ, số học sinh đạt
ĐTB dưới 5.0, số học sinh đạt ĐTB trên 8.0 …
Những cách thống kê đó chưa thể đánh giá chính xác kết quả học
tập của học sinh và từ đó các nhà trường chưa có được các các biện pháp
giáo dục phù hợp nhất. Vì vậy, tôi có ý tưởng áp dụng kỹ thuật phân cụm
trong khai phá dữ liệu để phân tích, đánh giá dữ liệu điểm của học sinh.
3.2 Giải quyết vấn đề
3.2.1 Xác định bài toán
Dữ liệu vào (Input): Dữ liệu được thu thập từ ĐTB, điểm tổng kết
cuối học kì, cuối năm học của học sinh.
Dữ liệu ra (Output): Các cụm học sinh được phân nhóm theo kết
quả ĐTB của một hay một số bộ môn, hoặc phân cụm theo ĐTB học kỳ,
Hình 3.2 Giao diện nhập và xem dữ liệu
3.3 Kết quả thử nghiệm
Trên thực tế, kết quả học tập của học sinh được đánh giá dựa trên
học lực và hạnh kiểm. Trong luận văn này chỉ phân tích các dữ liệu về ĐTB
của học sinh (đánh giá về học lực). Có 5 mức xếp loại học lực của học sinh:
Giỏi, Khá, Trung bình, Yếu, Kém. Vì vậy, trong quá trình thử nghiệm tôi
chọn số cụm để phân tích từ 3 đến 5 cụm và có thể phân tích theo ĐTB cuối
mỗi học kì hoặc ĐTB cuối năm học.
19

3.3.1 Phân cụm theo ĐTB cả năm

Hình 3.3 Phân cụm dữ liệu theo điểm trung bình cả năm

Ví dụ, từ kết quả phân cụm với dữ liệu khối 12 năm 2012 có thể
đưa ra một vài đánh giá và nhận xét như sau:
- Kết quả học tập của học sinh khối 12 không có em nào học lực
yếu (100% học sinh đủ điều kiện dự thi tốt nghiệp). Số học sinh học có học
lực trung bình là 237 học sinh (chiếm tỷ lệ 38.85%), số học sinh có học lực
khá giỏi là 373 em (chiếm tỷ lệ 61.15%).
20

- Ban giám hiệu nhà trường cần rút kinh nghiệm với công tác chủ
nhiệm và việc dạy-học với một số lớp như 12A12 (có 25 em xếp loại trung
bình, 15 em khá giỏi), lớp 12A1 có sự phân cấp quá rõ ràng giữa 2 loại học
sinh khá giỏi và yếu kém, cần có biện pháp hay kế hoạch phụ đạo các học
sinh yếu kém.
- So sánh với kết quả phân cụm trên dữ liệu điểm của học kì 1 và


Số học sinh có học lực trung bình chiếm tỷ lệ tương đối cao
(khoảng 60%), từ đó cho thấy Nhà trường cần có các biện pháp thúc đẩy
việc dạy và học để đạt kết quả cao hơn nữa.
Phần mềm WEKA ngoài việc đưa ra trọng tâm các cụm, thống kê
số lượng và tỷ lệ phần tử trong từng cụm còn cung cấp công cụ đưa ra hình
ảnh trực quan của các cụm dữ liệu.
- Phân cụm dữ liệu điểm trên phần mềm SPSS:
- Số học sinh có học lực khá khoảng gần 600 em và tập trung ở
cụm 3, cụm 5 (khoảng 35%). Kết quả phân cụm trên SPSS cũng tương
đương với kết quả phân cụm trên WEKA.
+ Đánh giá kết quả thử nghiệm:
Các chương trình như WEKA, SPSS thường chỉ đưa ra trọng tâm
các cụm và thống kê số phần tử và tỷ lệ trong từng cụm. Kết quả đó chưa hỗ
trợ tốt cho việc phân tích và đánh giá kết quả học tập của học sinh. Với
chương trình ứng dụng tôi xây dựng phần nào đã hỗ trợ tốt hơn khi đưa ra
được thông tin các cụm, đồ thị tương ứng và danh sách học sinh tương ứng
trong từng cụm.
Kết luận chương
Việc phân cụm các học sinh chính là việc nhóm các học sinh có
khả năng học tốt hay học yếu ở cùng một số môn học vào một cụm. Nói
cách khác, phân cụm học sinh là quá trình nhóm các học sinh có sự tương
đồng về điểm số vào một cụm. Các học sinh ở các cụm khác nhau thì có đặc
tính điểm số khác nhau.
Từ những kết quả phân cụm, các nhà quản lí, các giáo viên có thể
đưa ra các chiến lược đào tạo để bồi dưỡng học sinh khá giỏi, phụ đạo học
sinh yếu kém và điều phối phân công giảng dạy hợp lí.
23

KẾT LUẬN