..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM

---------------------------

LÂM QUỐC CƯỜNG

KHAI THÁC ĐIỂM HỌC TẬP ĐỂ
DỰ ĐOÁN KẾT QUẢ THI TRUNG HỌC
PHỔ THÔNG QUỐC GIA CHO
HỌC SINH TRUNG HỌC

LUẬN VĂN THẠC SĨ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã số ngành: 60480201

TP. HỒ CHÍ MINH, tháng 7 năm 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM

---------------------------

LÂM QUỐC CƯỜNG

KHAI THÁC ĐIỂM HỌC TẬP ĐỂ
DỰ ĐOÁN KẾT QUẢ THI TRUNG HỌC
PHỔ THÔNG QUỐC GIA CHO

HỌC SINH TRUNG HỌC
LUẬN VĂN THẠC SĨ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã số ngành: 60480201
CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS. TS. VÕ ĐÌNH BẢY
TP. HỒ CHÍ MINH, tháng 7 năm 2016


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ TP. HCM

Cán bộ hướng dẫn khoa học: PGS. TS. VÕ ĐÌNH BẢY

Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Cơng nghệ TP. Hồ Chí
Minh ngày 10 tháng 9 năm 2016.
Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm:
TT

Họ và tên

Chức danh Hội đồng

1

PGS. TS. Quản Thành Thơ

Chủ tịch

2


TS. Lư Nhật Vinh

Phản biện 1

3

TS. Nguyễn Thị Thúy Loan

Phản biện 2

4

TS. Lê Văn Quốc Anh

5

TS. Phạm Thị Thiết

Ủy viên
Ủy viên, Thư ký

Xác nhận của Chủ tịch Hội đồng đánh giá Luận sau khi Luận văn đã được
sửa chữa (nếu có).
Chủ tịch Hội đồng đánh giá LV

PGS. TS. Quản Thành Thơ


TRƯỜNG ĐH CƠNG NGHỆ TP. HCM
PHỊNG QLKH – ĐTSĐH


CỘNG HỊA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
TP. HCM, ngày 30 tháng 7 năm 2016

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên:

Lâm Quốc Cường

Giới tính: Nam

Ngày, tháng, năm sinh:

27/7/1978

Nơi sinh: Sóc Trăng

Chun ngành:

Cơng nghệ thông tin

MSHV: 1441860033

I- Tên đề tài:
Khai thác điểm học tập để dự đốn kết quả thi trung học phổ thơng quốc gia cho học
sinh trung học.
II- Nhiệm vụ và nội dung:
- Nghiên cứu luật phân lớp, dự đoán.
- Nghiên cứu các phương pháp để phân lớp và dự đoán kết quả thi trung học phổ thông

quốc gia.
- Sử dụng các thuật toán của cây quyết định để phân lớp và dự đốn kết quả thi trung
học phổ thơng quốc gia và tìm ra thuật tốn có độ chính xác cao nhất.
III- Ngày giao nhiệm vụ:

23/01/2016

IV- Ngày hoàn thành nhiệm vụ: 30/7/2016
V- Cán bộ hướng dẫn: PGS. TS. VÕ ĐÌNH BẢY
CÁN BỘ HƯỚNG DẪN

PGS. TS. VÕ ĐÌNH BẢY

KHOA QUẢN LÝ CHUYÊN NGÀNH


i

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi. Các số liệu, kết
quả nêu trong Luận văn là trung thực và chưa từng được ai cơng bố trong bất kỳ
cơng trình nào khác.
Tơi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này
đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn
gốc.
Học viên thực hiện Luận văn

Lâm Quốc Cường



ii

LỜI CÁM ƠN
Trước tiên tơi xin bày tỏ lịng biết ơn sâu sắc tới thầy PGS. TS. Võ Đình Bảy,
thầy đã tận tình giúp đỡ, hướng dẫn, động viên và tạo mọi điều kiện giúp tơi tiếp cận và
hồn thành luận văn này theo đúng yêu cầu.
Tôi cũng xin bày tỏ lịng biết ơn tới Q thầy, cơ Khoa Cơng nghệ thơng tin và
cán bộ phịng Quản lý khoa học - Đào tạo sau đại học trường Đại học Công nghệ
Thành phố Hồ Chí Minh đã tạo mọi điều kiện thuận lợi và hướng dẫn tận tình về các
thủ tục, văn bản liên quan đến luận văn.
Tôi xin chân thành cảm ơn đến Quý thầy, cô trong Hội đồng đánh giá Luận văn
Thạc sĩ đã đóng góp ý kiến quý báo, chân tình để tơi hồn thiện luận văn này.
Cuối cùng, tơi xin cảm ơn gia đình, q đồng nghiệp, quý lãnh đạo cơ quan đã tạo
điều kiện tốt nhất và động viên tôi trong suốt thời gian thực hiện luận văn này.
Lâm Quốc Cường


iii

TÓM TẮT
Ngày nay, giáo dục và đào tạo là quốc sách hàng đầu đã được Đảng, Nhà
nước và toàn dân ta xác định, giáo dục luôn luôn được ưu tiên trong kế hoạch phát
triển kinh tế, xã hội của đất nước. Trong năm 2015, Bộ Giáo dục và Đào tạo đã thực
hiện đổi mới kiểm tra, đánh giá, cụ thể là trong kỳ thi trung học phổ thơng quốc gia
đó là kỳ thi hai trong một, nghĩa là học sinh có thể lấy kết quả thi trung học phổ
thơng quốc gia để xét công nhận tốt nghiệp trung học phổ thông và làm căn cứ để
xét tuyển sinh đại học, cao đẳng.
Đề tài “Khai thác điểm học tập để dự đốn kết quả thi trung học phổ thơng
quốc gia của học sinh trung học” nhằm hỗ trợ học sinh lớp 12 trong việc dự đoán
kết quả trong kỳ thi trung học phổ thông quốc gia. Hiện nay, phân lớp và dự đốn là

để tìm ra dữ liệu có ích phục vụ cho nhu cầu cần thiết để đưa ra các quyết định
thông minh hỗ trợ người dùng trong công việc thuộc các lĩnh vực như y tế, giáo
dục, kinh doanh, .... Đề tài sử dụng phương pháp cây quyết định (Decision Tree) đó
là phương pháp đơn giản, dễ sử dụng và có độ tin cậy khá cao và phù hợp với nội
dung của đề tài để thực hiện việc dự đoán kết quả của học sinh trong kỳ thi trung
học phổ thông quốc gia, cụ thể là đề tài thử nghiệm trên ba thuật toán là C5.0,
CART và Random Forest.
Bên cạnh việc nghiên cứu cơ sở lý thuyết về phương pháp cây quyết định, đề
tài sử dụng ngôn ngữ R, đây là ngơn ngữ lập trình cấp cao, hỗ trợ rất mạnh mẽ cho
việc phân tích dữ liệu, tính tốn xác suất thống kê, giải thuật học tự động, … để xây
dựng ứng dụng hỗ trợ học sinh dự đoán kết quả trong các kỳ thi trung học phổ
thông quốc gia hàng năm do Bộ Giáo dục và Đào tạo tổ chức.


iv

ABSTRACT
Today, education and training is a top national policy was the Party, State and
people identification, education has always been a priority in the economic
development plan, the country's society. In 2015, the Ministry of Education and
Training has implemented innovative inspection and evaluation, particularly in the high
school exams that country is in a second exam, which means students can get results
exam national high school recognized at graduation for high school and as a basis for
college admission and college.
The theme “Mining to predict academic test results National High School High
School Student” in support of 12th graders in predicting the results of examinations
National High School. Currently, classification and prediction is to find useful data in
service needs to make smart decisions to support users in their work in fields such as
health, education, economic business, .... the theme uses a decision tree method
(decision tree) methods that are simple, easy to use and high reliability, and consistent

with the content of the subject to perform the project guess the outcome of the exam
students in the national high school, namely the three subjects tested on the C5.0
algorithm, CART and Random Forest.
Besides the study of the theoretical basis of the decision tree method, subjects
using the R language, this is a high-level programming language, very strong support
for data analysis, probability calculation system Statistics, automatic learning
algorithm, ... to build applications that support students predict the outcome of the high
school exams annually by the national Ministry of Education and Training held.


v

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CÁM ƠN ............................................................................................................. ii
TÓM TẮT.................................................................................................................. iii
ABSTRACT .............................................................................................................. iv
MỤC LỤC ...................................................................................................................v
DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... vii
DANH MỤC CÁC BẢNG........................................................................................ ix
DANH MỤC CÁC BIỂU ĐỒ, ĐỒ THỊ, SƠ ĐỒ, HÌNH ẢNH ..................................x
CHƯƠNG 1: MỞ ĐẦU ..............................................................................................1
1.1. Đặt vấn đề .........................................................................................................1
1.2. Lý do chọn đề tài ..............................................................................................1
1.3. Mục tiêu, nội dung và phương pháp nghiên cứu ..............................................2
1.3.1. Mục tiêu .....................................................................................................2
1.3.2. Nội dung ....................................................................................................3
1.3.3. Phương pháp ..............................................................................................3
1.4. Bố cục Luận văn ...............................................................................................3
CHƯƠNG 2: TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT ............................................4

2.1. Giới thiệu kỳ thi THPT quốc gia ......................................................................4
2.2. Khai thác dữ liệu ..............................................................................................5
2.2.1. Khai thác luật phân lớp, dự đoán ...............................................................5
2.2.2. Các vấn đề liên quan đến phân lớp dữ liệu ................................................7
2.2.3. Đánh giá độ chính xác của phân lớp ..........................................................7
2.2.4. Ví dụ về phân lớp và dự đoán ..................................................................12
2.3. Phương pháp phân lớp dựa trên cây quyết định .............................................17
2.3.1. Giới thiệu .................................................................................................17
2.3.2. Một số lưu ý khi sử dụng cây quyết định ................................................19
2.3.3. Đánh giá hiệu quả phương pháp cây quyết định .....................................20
2.3.4. Xây dựng cây quyết định .........................................................................21


vi

2.4. Thuật toán C5.0 ..............................................................................................22
2.5. Thuật toán CART ...........................................................................................27
2.6. Thuật toán RF .................................................................................................30
2.7. Tổng quan vấn đề nghiên cứu ........................................................................32
2.7.1. Giới thiệu tổng quan ................................................................................32
2.7.2. Tình hình nghiên cứu trên thế giới ..........................................................33
2.7.3. Tình hình nghiên cứu trong nước ............................................................35
CHƯƠNG 3: XÂY DỰNG MƠ HÌNH ....................................................................36
3.1. Xây dựng mơ hình hệ thống ...........................................................................36
3.1.1. Dữ liệu vào...............................................................................................36
3.1.2. Thuật toán cây quyết định........................................................................40
3.1.3. Kết quả ra .................................................................................................43
3.2. Xây dựng các thuật toán .................................................................................44
CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ .....................................................45
4.1. Môi trường thực nghiệm.................................................................................45

4.2. Giới thiệu cơ sở dữ liệu thực nghiệm .............................................................45
4.3. Áp dụng các thuật toán phân lớp dựa trên phương pháp cây quyết định .......45
4.3.1. Xây dựng phần chung ..............................................................................45
4.3.2. Thuật toán C5.0 .......................................................................................50
4.3.3. Thuật toán CART ....................................................................................54
4.3.4. Thuật toán RF ..........................................................................................56
4.4. Đánh giá và so sánh ........................................................................................57
4.4.1. Đánh giá hiệu suất của các giải thuật.......................................................57
4.4.2. So sánh các thuật toán..............................................................................58
CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ..........................................60
5.1. Kết luận ..........................................................................................................60
5.2. Ưu điểm và hạn chế ........................................................................................60
5.3. Hướng phát triển .............................................................................................60
TÀI LIỆU THAM KHẢO .........................................................................................62


vii

DANH MỤC CÁC TỪ VIẾT TẮT
Tiếng Việt

Từ viết tắt

STT

Viết rõ

1

THPT


Trung học phổ thơng

2

Gioi

Giỏi

3

Kha

Khá

4

Tbinh

Trung bình

5

Yeu

Yếu

6

Kem


Kém

7

DoGioi

Đỗ loại giỏi

8

DoKha

Đỗ loại khá

9

DoKTB

Đỗ loại trung bình khá

10

DoTB

Đỗ loại trung bình

11

Hong


Hỏng

12

TOAN10

Điểm trung bình mơn Tốn lớp 10

13

VL10

Điểm trung bình mơn Vật lí lớp 10

14

HH10

Điểm trung bình mơn Hóa học lớp 10

15

SH10

Điểm trung bình mơn Sinh học lớp 10

16

NV10


Điểm trung bình mơn Ngữ văn lớp 10

17

LS10

Điểm trung bình mơn Lịch sử lớp 10

18

DL10

Điểm trung bình mơn Địa lí lớp 10

19

NN10

Điểm trung bình mơn Ngoại ngữ lớp 10

20

TB10

Điểm trung bình cả năm lớp 10

21

TOAN11


Điểm trung bình mơn Tốn lớp 11

22

VL11

Điểm trung bình mơn Vật lí lớp 11

23

HH11

Điểm trung bình mơn Hóa học lớp 11

24

SH11

Điểm trung bình mơn Sinh học lớp 11


viii

Từ viết tắt

STT

Viết rõ


25

NV11

Điểm trung bình mơn Ngữ văn lớp 11

26

LS11

Điểm trung bình mơn Lịch sử lớp 11

27

DL11

Điểm trung bình mơn Địa lí lớp 11

28

NN11

Điểm trung bình mơn Ngoại ngữ lớp 11

29

TB11

Điểm trung bình cả năm lớp 11


30

TOAN12

Điểm trung bình mơn Tốn lớp 12

31

VL12

Điểm trung bình mơn Vật lí lớp 12

32

HH12

Điểm trung bình mơn Hóa học lớp 12

33

SH12

Điểm trung bình mơn Sinh học lớp 12

34

NV12

Điểm trung bình mơn Ngữ văn lớp 12


35

LS12

Điểm trung bình mơn Lịch sử lớp 12

36

DL12

Điểm trung bình mơn Địa lí lớp 12

37

NN12

Điểm trung bình mơn Ngoại ngữ lớp 12

38

TB12

Điểm trung bình cả năm lớp 12

39

KETQUA

Kết quả thi THPT quốc gia


Tiếng Anh

Từ viết tắt

STT

Viết rõ

1

CART

Classification And Regression Tree

2

NBC

Naive Bayes Classification

3

ANN

Artificial Neural Network

4

CBA


Classification Based on Associations

5

SVM

Support Vector Machines

6

ILA

Inductive Learning Algorithm

7

RF

Random Forest

8

DT

Decision Tree

9

KNN


K nearest neighbors


ix

DANH MỤC CÁC BẢNG
Bảng 2.1. Tập cơ sở dữ liệu ....................................................................................12
Bảng 2.2. Tập dữ liệu huấn luyện ..........................................................................13
Bảng 2.3. Tập dữ liệu kiểm tra ...............................................................................14
Bảng 2.4. Mẫu cụ thể .............................................................................................14
Bảng 2.5. Kết quả cho mẫu cụ thể .........................................................................14
Bảng 2.6. Tập cơ sở dữ liệu ...................................................................................15
Bảng 2.7. Tập dữ liệu kiểm tra fold_1 ...................................................................15
Bảng 2.8. Tập dữ liệu huấn luyện ..........................................................................15
Bảng 2.9. Tập dữ liệu kiểm tra fold_2 ...................................................................16
Bảng 2.10. Tập dữ liệu huấn luyện ........................................................................16
Bảng 2.11. Tập dữ liệu kiểm tra fold_10 ...............................................................16
Bảng 2.12. Tập dữ liệu huấn luyện ........................................................................16
Bảng 2.13. Mẫu cụ thể ...........................................................................................17
Bảng 2.14. Kết quả cho mẫu cụ thể .......................................................................17
Bảng 3.1. Kết quả của các thuật toán ......................................................................43
Bảng 4.1. Độ chính xác các thuật tốn ...................................................................58


x

DANH MỤC CÁC BIỂU ĐỒ, ĐỒ THỊ, SƠ ĐỒ, HÌNH ẢNH
Hình 2.1. Mơ hình bài tốn phân lớp .......................................................................6
Hình 2.2. Mơ hình phân lớp .....................................................................................8
Hình 2.3. Mơ hình phân lớp theo phương pháp holdout ..........................................9

Hình 2.4. Mơ hình phân lớp theo phương pháp k-fold cross-validation ................10
Hình 2.5. Mơ hình sử dụng fold_1 làm tập kiểm tra ..............................................10
Hình 2.6. Mơ hình sử dụng fold_2 làm tập kiểm tra ..............................................11
Hình 2.7. Mơ hình sử dụng fold_3 làm tập kiểm tra ..............................................11
Hình 2.8. Mơ hình sử dụng fold_10 làm tập kiểm tra ............................................12
Hình 2.9. Cây quyết định mua máy tính hay khơng, dựa vào độ tuổi, sinh viên và tín
dụng ........................................................................................................................18
Hình 2.10. Giải thuật rừng ngẫu nhiên (RF-Random Forest) ................................31
Hình 3.1. Mơ hình hệ thống ...................................................................................36
Hình 3.2. Mơ hình dữ liệu vào ...............................................................................36
Hình 3.3. Bảng điểm học sinh lớp 10 của một trường THPT ................................37
Hình 3.4. Bảng điểm học sinh thi THPT quốc gia .................................................37
Hình 3.5. Tập tin cơ sở dữ liệu dạng excel ............................................................38
Hình 3.6. Tập tin cơ sở dữ liệu dạng csv ...............................................................39
Hình 3.7. Cơ sở dữ liệu đầu vào dạng csv .............................................................40
Hình 3.8. Cây quyết định .......................................................................................41
Hình 3.9. Lưu đồ của các thuật tốn ......................................................................42
Hình 4.1. Dữ liệu các thuộc tính lưu trong bảng HocSinh .....................................46
Hình 4.2. Tập dữ liệu huấn luyện (trainingData) ...................................................47
Hình 4.3. Tập dữ liệu kiểm tra (testingData) .........................................................48
Hình 4.4. Kích thước dữ liệu chia thành 10 fold ....................................................48
Hình 4.5. Fold01 của tập dữ liệu có kích thước 807 mẫu tin .................................49
Hình 4.6. Fold10 của tập dữ liệu có kích thước 807 mẫu tin .................................49
Hình 4.7. Kết quả thử nghiệm của tập dữ liệu huấn luyện .....................................50


xi

Hình 4.8. Luật được sinh ra của lớp DoGioi ...........................................................51
Hình 4.9. Luật được sinh ra của lớp DoKha ...........................................................51

Hình 4.10. Luật được sinh ra của lớp DoKTB .......................................................52
Hình 4.11. Luật được sinh ra của lớp DoTB ..........................................................52
Hình 4.12. Luật được sinh ra của lớp Hong ...........................................................52
Hình 4.13. Kết quả phân lớp của tập huấn luyện trong thuật tốn C5.0 .................53
Hình 4.14. Kết quả phân lớp của tập kiểm tra trong thuật tốn C5.0 ....................53
Hình 4.15. Độ quan trọng của các thuộc tính ảnh hưởng đến phân lớp và dự đốn
của thuật tốn C5.0 .................................................................................................54
Hình 4.16. Độ quan trong của tập dữ liệu huấn luyện trong thuật tốn CART ......54
Hình 4.17. Kết quả dự đốn của thuật tốn CART ................................................55
Hình 4.18. Độ quan trọng của các thuộc tính ảnh hưởng đến phân lớp và dự đốn
của thuật tốn CART ..............................................................................................56
Hình 4.19. Kết quả dự đốn của giải thuật RF .......................................................56
Hình 4.20. Độ quan trọng của các thuộc tính ảnh hưởng đến phân lớp và dự đốn
thuật tốn của RF ...................................................................................................57
Hình 4.21. Độ chính xác trung bình của các thuật tốn ..........................................58
Hình 4.22. Độ chính xác 10 fold của các thuật tốn ..............................................59


1

CHƯƠNG 1: MỞ ĐẦU
1.1. Đặt vấn đề
Giáo dục và đào tạo là quốc sách hàng đầu đã được Đảng, Nhà nước và toàn
dân ta xác định và đầu tư cho giáo dục là đầu tư cho sự phát triển, giáo dục luôn
luôn được ưu tiên trong kế hoạch phát triển kinh tế, xã hội của đất nước. Trong quá
trình đổi mới của đất nước thì giáo dục cần phải được đổi mới một cách căn bản và
toàn diện để từ đó tạo ra con người phát triển tồn diện như đã được nêu lên trong
Nghị quyết số 29-NQ/TW ngày 04/11/2013 của Ban Chấp hành Trung ương Đảng.
Kỳ thi THPT quốc gia mới được Bộ Giáo dục và Đào tạo triển khai thực hiện từ
năm 2015 và mục đích của kỳ thi lấy kết quả để xét công nhận tốt nghiệp THPT và

xét tuyển sinh đại học, cao đẳng.
Hiện nay, có rất có nhiều mơ hình phân lớp được đề xuất như cây quyết định,
phân lớp NBC, ILA, ANN, SVM, KNN. Vấn đề phân lớp dữ liệu và dự đoán đã
được quan tâm trong nhiều lĩnh vực như y tế, giáo dục, kinh tế, bảo hiểm, ngân
hàng…, chúng ta có thể dựa vào phân lớp dữ liệu để tạo ra mô hình phân lớp và dự
đốn để biết được khuynh hướng của dữ liệu trong tương lai. Trong y tế, dựa vào
các thơng số xét nghiệm có thể dự đốn được các bệnh và hỗ trợ đưa ra các quyết
định trong việc chẩn đốn; trong ngân hàng, dựa vào các thơng tin từ khách hàng
mà ngân hàng đưa ra quyết định cho hay không cho và cho với mức vay là bao
nhiêu để có khả năng thu hồi và tăng lợi nhuận; trong giáo dục, từ phân lớp dữ liệu
và dự đốn ta có thể dựa vào điểm học tập của học sinh để từ đó có thể dự đốn
được kết quả thi THPT quốc gia.
1.2. Lý do chọn đề tài
Học sinh trường THPT muốn bước vào ngưỡng cửa của các trường đại học,
cao đẳng thì các em có thể phải trải qua kỳ thi THPT quốc gia và kỳ thi này rất quan
trọng quyết định về tương lai sau này của các em. Năm 2015, Bộ Giáo dục và Ðào
tạo đã thực hiện đổi mới trong kiểm tra, đánh giá được thể hiện trong kỳ thi THPT
quốc gia [1], đây là kỳ thi hai trong một, trong kỳ thi này có những mơn bắt buộc và


2

các mơn tự chọn và học sinh phải có định hướng học như thế nào đối với các môn
bắt buộc và các em phải biết chọn các môn nào là thế mạnh của mình để chắt chắn
thi đạt trong kỳ thi này.
Trong kỳ thi THPT quốc gia tại tỉnh Sóc Trăng, để xét công nhận tốt nghiệp
THPT học sinh sẽ thi bốn mơn trong đó có hai mơn bắt buộc là Tốn, Ngữ văn và
hai mơn tự chọn trong các mơn Vật lí, Hóa học, Sinh học, Lịch sử, Địa lí, Tiếng
Anh. Vì thế từ những năm học lớp 10, 11 các em có thể định hướng các mơn thi để
đến năm lớp 12 các em có kế hoạch và lựa chọn các môn thi cho phù hợp với khả

năng của mình và đặc biệt là được xét cơng nhận tốt nghiệp THPT từ đó làm căn cứ
để xét vào các trường đại học, cao đẳng.
Từ những vấn đề đã nêu trên, tơi nhận thấy cần phải có một cơng cụ hỗ trợ để
học sinh có thể dự đốn kết quả trong kỳ thi THPT quốc gia để học sinh có thể điều
chỉnh khả năng học tập và có căn cứ khoa học hơn trong việc lựa chọn môn thi từ
điểm các môn học của lớp 10, lớp 11 và lớp 12. Vì vậy, tơi chọn đề tài “Khai thác
điểm học tập để dự đoán kết quả thi trung học phổ thông quốc gia của học sinh
trung học” sử dụng các thuật tốn của cây quyết định để tìm ra thuật tốn có độ
chính xác cao nhất cho đề tài.
1.3. Mục tiêu, nội dung và phương pháp nghiên cứu
1.3.1. Mục tiêu
Mục tiêu của đề tài là bước đầu nghiên cứu về khai thác dữ liệu, xây dựng ứng
dụng khai thác điểm học tập để dự đoán kết quả thi THPT quốc gia của học sinh
trung học và để làm được điều này, đề tài cần được thực hiện các nội dung sau:
- Thực hiện tìm hiểu, phân tích và tổng hợp kết quả học tập của học sinh từ lớp
10 đến lớp 12 để từ đó xác định được những môn thế mạnh cũng như những môn
hạn chế.
- Nghiên cứu phương pháp phân lớp dữ liệu cụ thể là phương pháp cây quyết
định (Decision Tree) để tìm ra thuật tốn có độ chính xác cao nhất. Sử dụng dữ liệu
kết quả học tập và kết quả thi THPT quốc gia năm 2015 để dự đoán kết quả thi
THPT quốc gia của học sinh cho những năm tiếp theo.


3

- Sử dụng ngôn ngữ R [16] để kiểm định độ chính xác của các thuật tốn theo
phương pháp cây quyết định.
1.3.2. Nội dung
- Sử dụng công cụ để kiểm định kết quả khi sử dụng phân lớp và dự đoán dữ
liệu dựa trên phương pháp cây quyết định, các thuật toán tiêu biểu được sử dụng là

C5.0, CART và RF.
- Sử dụng ngôn ngữ R để kiểm định các thuật tốn trên, để lựa chọn thuật tốn
có độ chính xác cao nhất.
1.3.3. Phương pháp
- Nghiên cứu tài liệu, các văn bản, thông tư, hướng dẫn của Bộ Giáo dục và
Đào tạo, của Sở Giáo dục và Đào tạo tỉnh Sóc Trăng có liên quan đến việc đánh giá
kết quả học tập, kỳ thi THPT quốc gia năm 2015 [1][2][3].
- Thu thập, tổng hợp dữ liệu.
- Làm sạch, phân tích và biến đổi dữ liệu theo đúng yêu cầu.
- Tiến hành kiểm thử và đánh giá hiệu suất của các thuật toán dựa trên dữ liệu
kết quả thi THPT quốc gia năm 2015.

1.4. Bố cục Luận văn
Luận văn được chia thành 5 chương, cụ thể như sau:
Chương 1: Từ vấn đề cần giải quyết đưa ra lý do chọn đề tài và nêu mục tiêu,
nội dung và phương pháp nghiên cứu
Chương 2: Giới thiệu khai thác dữ liệu, luật phân lớp và dự đoán cụ thể là
phương pháp cây quyết định và các nghiên cứu liên quan
Chương 3: Nghiên cứu các thuật toán phân lớp dữ liệu bằng phương pháp
cây quyết định, kiểm định các thuật toán và đưa ra thuật tốn có độ chính xác cao
nhất
Chương 4: Thực nghiệm và đánh giá kết quả thu được từ việc sử dụng
phương pháp cây quyết định trên cơ sở dữ liệu cụ thể
Chương 5: Kết luận, nhận xét và hướng phát triển của đề tài


4

CHƯƠNG 2: TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT
2.1. Giới thiệu kỳ thi THPT quốc gia

Năm 2015, Bộ Giáo dục và Đào tạo đã đổi mới trong kỳ thi THPT quốc gia,
cụ thể là Bộ Giáo dục và Đào tạo đã có Thơng tư số 02/2015/TT-BGDĐT ngày
26/02/2015 Ban hành Quy chế thi THPT quốc gia [1] và Thông tư số 03/2015/TTBGDĐT ngày 26/02/2015 Ban hành Quy chế tuyển sinh đại học, cao đẳng hệ chính
quy [2], bên cạnh đó Cục Khảo thí và Kiểm định chất lượng giáo dục có công văn
số 1388/BGDĐT-KTKĐCLGD ngày 25/3/2016 về việc hướng dẫn thực hiện Quy
chế thi trong tổ chức thi THPT quốc gia và xét công nhận tốt nghiệp trung học phổ
thông [3]. Đối với tỉnh Sóc Trăng trong kỳ thi này học sinh phải thi hai môn bắt
buộc và được phép lựa chọn hai mơn cịn lại để xét cơng nhận tốt nghiệp THPT và
làm căn cứ tuyển sinh đại học, cao đẳng. Đối với các môn tự chọn phần lớn học sinh
chưa biết cách chọn có thể chọn theo bạn bè, theo sự tư vấn của thầy cô, theo sự
quyết định của cha mẹ vì thế khi tham gia kỳ thi thì kết quả sẽ khơng như mong
muốn và có thể ảnh hưởng đến việc xét vào các trường đại học, cao đẳng sau này.
Để giúp cho học sinh tự tin trong việc lựa chọn các môn thi, đề tài đã sử dụng kết
quả học tập các môn của từng năm học lớp 10, lớp 11 và lớp 12 để từ đó đưa ra dự
đốn kết quả thi THPT quốc gia của học sinh trung học.
Trong kỳ thi THPT quốc gia tổ chức thi tám mơn Tốn, Ngữ văn, Lịch sử,
Địa lí, Vật lí, Hóa học, Sinh học, Ngoại ngữ. Tỉnh Sóc Trăng, để xét cơng nhận tốt
nghiệp THPT thí sinh phải thi bốn môn gồm hai môn bắt buộc là Tốn và Ngữ văn
và hai mơn do thí sinh tự chọn trong các mơn cịn lại. Nếu thí sinh muốn xét công
nhận tốt nghiệp THPT và xét tuyển sinh đại học, cao đẳng thí sinh phải thi hai mơn
bắt buộc Tốn, Ngữ văn và thi ít nhất hai mơn tự chọn trong các mơn cịn lại và
đăng ký dự thi thêm các môn phù hợp với tổ hợp các môn thi để xét tuyển sinh do
trường đại học, cao đẳng quy định. Kỳ thi THPT quốc gia năm 2015 đáp ứng theo
Nghị quyết số 29-NQ/TW ngày 04/11/2013 của Ban Chấp hành Trung ương Đảng
về đổi mới căn bản toàn diện giáo dục và cụ thể là đổi mới trong thi cử.


5

2.2. Khai thác dữ liệu

Khai thác dữ liệu (Data mining) là một quá trình khai thác các tri thức mới
và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu lớn hiện có được lưu trữ
trong cơ sở dữ liệu hay kho dữ liệu. Khai thác dữ liệu là một bước của quá trình
khai thác tri thức (Knowledge Discovery Process). Trong khai thác tri thức gồm các
bước sau: Chọn dữ liệu (data selection): chọn dữ liệu cần thiết; Làm sạch dữ liệu
(data cleaning): loại bỏ dữ liệu khơng thích hợp và dữ liệu nhiễu; Làm giàu dữ liệu
(enrichment): bổ sung thêm các thông tin cho dữ liệu phong phú hơn; Chuyển đổi
dữ liệu hoặc mã hóa (data transformation or encoding ): chuyển đổi dữ liệu về dạng
phù hợp để thích hợp cho việc khai thác dữ liệu; Khai thác dữ liệu (data mining): sử
dụng các phương pháp thích hợp để kết xuất dữ liệu; Báo cáo và trình bày dữ liệu
khai thác: sử dụng các kỹ thuật để biểu diễn tri thức cho người sử dụng.
2.2.1. Khai thác luật phân lớp, dự đoán
Ngày nay phân lớp dữ liệu là hướng nghiên cứu chính của vấn đề khai thác
dữ liệu, từ nhu cầu thực tế đặt ra là dữ liệu ngày càng lớn và để tìm ra dữ liệu có ích
phục vụ cho nhu cầu cần thiết để đưa ra các quyết định thông minh. Phân lớp và dự
đốn là hai dạng của phân tích dữ liệu nhằm rút trích ra mơ hình dữ liệu quan trọng
và dự đoán xu hướng dữ liệu trong tương lai. Trong những năm qua, phân lớp dữ
liệu đang phát triển mạnh mẽ trong nhiều lĩnh vực khác nhau như máy học, hệ
chuyên gia, thống kê, ..., và được ứng dụng nhiều trong các lĩnh vực như giáo dục, y
tế, thương mại, kinh doanh, nghiên cứu thị trường, bảo hiểm, .... Ví dụ như mơ hình
dự báo thời tiết, muốn dự đốn thời tiết ngày mai là mưa hay nắng thì dựa vào nhiệt
độ, độ ẩm của ngày hôm nay và các ngày trước đó từ đó sẽ đưa ra kết quả dự đốn.
Khai thác luật phân lớp được tóm tắt bằng bài tốn là ta có cơ sở dữ liệu D
với các thuộc tính là (A1, A2, ..., An) trong đó A1 chứa các giá trị (ai1, ai2, ..., ain) và
thuộc tính phân lớp là C với k lớp là các lớp nhãn (c1, c2, ..., ck). Sử dụng tập dữ liệu
đã cho khi đó thuật tốn phân lớp sẽ tìm ra các luật của dữ liệu và hình thành nên bộ
phân lớp, trên cơ sở đó có thể dự đốn được lớp của các mẫu mới.


6

LỚP C1
DỮ
LIỆU
VÀO

THUẬT TỐN
PHÂN LỚP

LỚP C2
………

LỚP Ck

Hình 2.1. Mơ hình bài toán phân lớp
Phân lớp dữ liệu là tạo ra bộ phân lớp hay mơ hình phân lớp từ dữ liệu, q
trình phân lớp gồm có hai bước: [9]
- Bước huấn luyện: Dữ liệu huấn luyện được phân tích bởi thuật tốn phân
lớp (có thuộc tính nhãn lớp) để tạo ra bộ phân lớp. Đầu vào của bước huấn luyện là
một tập dữ liệu có cấu trúc được mơ tả bằng các thuộc tính và được tạo ra từ tập các
bộ giá trị của các thuộc tính. Đầu ra của bước này là các quy tắc phân lớp dưới dạng
phương pháp cây quyết định (Decision Tree), cụ thể là các phương pháp dựa trên
mơ hình cây như C5.0, CART và RF.
- Bước phân lớp: Dữ liệu kiểm tra được dùng để ước lượng độ chính xác của
bộ phân lớp. Độ chính xác mang tính chất dự đốn của mơ hình phân lớp, nếu độ
chính xác là chấp nhận được thì có thể dùng bộ phân lớp để phân lớp các mẫu dữ
liệu mới. Cần sử dụng tập dữ liệu kiểm tra độc lập với tập dữ liệu đào tạo. Nếu độ
chính xác của mơ hình là chấp nhận được thì mơ hình đó được sử dụng cho để phân
lớp dữ liệu trong tương lai.
Trong mơ hình phân lớp thì thuật tốn phân lớp là đóng vai trị quyết định tới
sự thành cơng hay thất bại của mơ hình. Vì vậy cần phải tìm ra được một thuật tốn

phân lớp hiệu quả, nhanh chóng, có độ chính xác cao và có khả năng mở rộng cho
các tập dữ liệu lớn [9]. Hiện nay có các kỹ thuật phân lớp như sau: phương pháp cây
quyết định, NBC, ANN, CBA, KNN, SVM, ILA, phân tích thống kê, thuật tốn di
truyền, phương pháp tập thơ, .... Đề tài sử dụng phương pháp cây quyết định với các
thuật toán là C5.0, CART và RF để xác định dộ chính xác khi dự đốn.


7

2.2.2. Các vấn đề liên quan đến phân lớp dữ liệu
Chuẩn bị dữ liệu: dữ liệu cần phải được chuẩn bị trước cho quá trình phân
lớp, việc xử lý dữ liệu là một cơng việc khơng thể thiếu và đóng vai trị quyết định
tới sự áp dụng được hay khơng được của các mơ hình phân lớp. Các cơng việc
chuẩn bị dữ liệu [9]:
- Thu thập dữ liệu: thực hiện thu thập các thông tin, dữ liệu cần thiết phục vụ
cho nhu cầu của đề tài.
- Làm sạch dữ liệu: thực hiện tìm và thay thế những giá trị thiếu trong dữ liệu
ban đầu. Giá trị thiếu có thể do lỗi chủ quan của người nhập liệu, trường hợp này ta
có thể thay bằng giá trị phổ biến nhất của tập thuộc tính đó.
- Chọn lọc dữ liệu: có nhiều thuộc tính khơng cần thiết hay khơng liên quan
đến vấn đề cần xử lí, ta có thể loại bỏ những thuộc tính này vì có thể những thuộc
tính đó làm ảnh hưởng đến q trình học của thuật tốn phân lớp.
- Biến đổi dữ liệu: có những dữ liệu của một số thuộc tính là dạng liên tục
nên có thể biến đổi sang dạng rời rạc, việc biến đổi này làm cô đọng dữ liệu nên các
thao tác vào, ra liên quan sẽ tối ưu hơn trong quá trình học. Ví dụ như điểm trung
bình của học sinh nếu có giá trị liên tục thì rất nhiều và ta có thể chuyển sang dạng
rời rạc gồm giỏi, khá, trung bình, yếu và kém.
So sánh các mơ hình phân lớp: mỗi ứng dụng cần lựa chọn một mơ hình phù
hợp dựa trên các tiêu chí như độ chính xác khi dự đốn, tốc độ thực hiện, khả năng
tạo ra mơ hình dự đoán đúng, khả năng thực hiện hiệu quả trên mơ hình đã học,

mức độ hiểu và hiểu rõ kết quả sinh ra bởi mơ hình đã học.
2.2.3. Đánh giá độ chính xác của phân lớp
Hiện nay có rất nhiều phương pháp đánh giá độ chính xác của phân lớp, độ
chính xác của phân lớp giúp cho dự đốn kết quả của phân lớp dữ liệu trong tương
lai, ngoài ra độ chính xác cịn giúp so sánh các mơ hình phân lớp. Có hai phương
pháp được sử dụng phổ biến dựa trên phân hoạch ngẫu nhiên tập dữ liệu ban đầu đó
là holdout (splitting) và k-fold cross-validation. Mơ hình phân lớp dạng tổng quát.


8

Mẫu mới

Tập dữ liệu
kiểm tra

Phân
lớp
Tập
dữ liệu

Thuật toán
phân lớp
Tập dữ liệu
huấn luyện

Độ
chính
xác
Lớp


Hình 2.2. Mơ hình phân lớp
Trong mơ hình trên, ta thấy tập dữ liệu được chia làm hai phần là tập dữ liệu
kiểm tra và tập dữ liệu huấn luyện, trong tập dữ liệu huấn luyện ta dùng các thuật
toán phân lớp thực hiện phân lớp trên tập dữ liệu kiểm tra cho kết quả là độ chính
xác của mơ hình phân lớp. Cụ thể là khi có mẫu mới khi đưa vào phân lớp thì kết
quả là mẫu mới đó thuộc lớp nào.
Việc ước lượng độ chính xác của phân lớp là rất quan trọng cho phép dự
đoán độ chính xác của các kết quả phân lớp những dữ liệu tương lai. Độ chính xác
cịn giúp so sánh các mơ hình phân lớp khác nhau về tính hiệu quả và khả năng đáp
ứng của thuật tốn. Độ chính xác bộ phân lớp trên tập kiểm tra cho trước là phần
trăm của các mẫu trong tập kiểm tra được bộ phân lớp xếp đúng lớp, dựa vào công
thức sau:


9

- Phương pháp holdout, tập dữ liệu sẽ được chia thành hai phần ngẫu nhiên
gồm tập dữ liệu huấn luyện và tập dữ liệu kiểm tra. Phương pháp holdout chia 2/3
tập dữ liệu huấn luyện và 1/3 tập dữ liệu kiểm tra và thực hiện phân lớp để tính độ
chính xác của phân lớp. Độ chính xác của bộ phân lớp trên tập kiểm tra cho trước là
phần trăm của các mẫu trong tập kiểm tra được bộ phân lớp xếp đúng lớp.
Mơ hình phân lớp theo phương pháp holdout

2/3
TẬP HUẤN
LUYỆN
PHÂN
LỚP


TẬP
DỮ
LIỆU
1/3
TẬP KIỂM
TRA

ĐỘ
CHÍNH XÁC

Hình 2.3. Mơ hình phân lớp theo pương pháp holdout
- Phương pháp k-fold cross-validation, tập dữ liệu sẽ được phân chia ngẫu
nhiên thành k-fold có kích thước bằng nhau S1, S2, ..., Sk. Việc huấn luyện và kiểm
tra được thực hiện k lần, trong đó một fold được giữ lại làm tập dữ liệu kiểm tra và
k-1 fold còn lại làm tập dữ liệu huấn luyện. Lần lược mỗi k-fold được giữ lại làm
tập dữ liệu kiểm tra, tức là lần lặp thứ i, Si là tập dữ liệu kiểm tra (với i = 1...k) và
các tập dữ liệu còn lại hợp thành tập dữ liệu huấn luyện. Mơ hình phân lớp theo
phương pháp k-fold cross-validation với k = 10, tập dữ liệu được chia ngẫu nhiên từ
fold_1, fold_2, ..., fold_10 có kích thước gần bằng nhau.


10

TẬP
DỮ
LIỆU

k=1

fold_1


k=2

fold_2

k=3

fold_3

k=4

fold_4

k=5

fold_5

k=6

fold_6

k=7

fold_7

k=8

fold_8

k=9


fold_9

k = 10

fold_10

Hình 2.4. Mơ hình phân lớp theo phương pháp k-fold cross-validation
Bước 1: chia tập dữ liệu thành hai phần, lấy fold_1 làm dữ liệu kiểm tra, còn
9 fold còn lại làm dữ liệu huấn luyện.

TẬP
DỮ
LIỆU

k=1

fold_1

k=2

fold_2

k=3

fold_3

k=4

fold_4


k=5

fold_5

k=6

fold_6

k=7

fold_7

k=8

fold_8

k=9

fold_9

k = 10

fold_10

TẬP KIỂM TRA

TẬP
HUẤN
LUYỆN


Hình 2.5. Mơ hình sử dụng fold_1 làm tập kiểm tra