BỘ GIAO THÔNG VẬN TẢI BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM
----------------------------

KS. CAO CHIẾN THẮNG

XÂY DỰNG HỆ HỖ TRỢ CHO HỌC SINH
DỰ TUYỂN VÀO CÁC TRƯỜNG THPT
TRÊN ĐỊA BÀN NỘI THÀNH HẢI PHÒNG

LUẬN VĂN THẠC SĨ KỸ THUẬT

HẢI PHÒNG - 2016
BỘ GIAO THÔNG VÂN TẢI BỘ GIÁO DỤC VÀ ĐÀO TẠO


TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM
----------------------------

KS.

CAO CHIẾN THẮNG

XÂY DỰNG HỆ HỖ TRỢ CHO HỌC SINH
DỰ TUYỂN VÀO CÁC TRƯỜNG THPT
TRÊN ĐỊA BÀN NỘI THÀNH HẢI PHÒNG

LUẬN VĂN THẠC SĨ KỸ THUẬT;

MÃ SỐ: 60480201

CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

Người hướng dẫn khoa học: TS. Nguyễn Trọng Đức

HẢI PHÒNG - 2016

2


LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung luận văn,
những điều đã được trình bày hoặc là của riêng cá nhân tôi hoặc là được tổng hợp
từ nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo được dùng đều có xuất
xứ rõ ràng, được trích dẫn hợp pháp.
Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỉ luật theo quy
định cho lời cam đoan của mình.

Hải Phòng, 03/2016

Cao Chiến Thắng

3


LỜI CÁM ƠN

Được sự phân công của Khoa công nghệ thông tin trường Đại học Hàng Hải,
và sự đồng ý của thầy giáo hướng dẫn TS. Nguyễn Trọng Đức tôi đã thực hiện đề

tài “Xây dựng hệ hỗ trợ cho học sinh dự tuyển các trường THPT trên địa bàn nội
thành Hải Phòng”.
Để hoàn thành luận văn này, tôi xin chân thành cảm ơn các thầy cô giáo đã
tận tình hướng dẫn, giảng dạy trong suốt quá trình học tập, nghiên cứu ở trường
Đại học Hàng Hải Việt Nam.
Tôi xin chân thành cám ơn thầy giáo hướng dẫn TS. Nguyễn Trọng Đức người đã chỉ bảo tận tình, chu đáo, cung cấp tài liệu và phương pháp luận nghiên
cứu khoa học để tôi hoàn thành bản luận văn này.
Mặc dù đã có nhiều cố gắng để thực hiện luận văn một cách hoàn chỉnh nhất.
Xong luận văn được hoàn thành trong thời gian hạn hẹp, những hạn chế về kiến
thức và kinh nghiệm nên không thể tránh khỏi những thiếu sót nhất định mà bản
thân chưa thấy được. Tôi rất mong được sự góp ý của quý Thầy, Cô giáo để luận
văn của tôi được hoàn chỉnh hơn.
Tôi xin chân thành cám ơn!
Hải Phòng, 03/2016

Cao Chiến Thắng

4


MỤC LỤC
Trang

DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÝ HIỆU
Chữ viết tắt
Giải thích
CSDL

Cơ sở dữ liệu


HTQĐ

Hỗ trợ quyết định

KPDL

Khai phá dữ liệu

HS

Học sinh

THPT

Trung học phổ thông

THCS

Trung học cơ sở

DSS

Decision Support Systems

5


DANH MỤC CÁC HÌNH MINH HỌA
Số hình


Tên hình

Trang

Hình 1.1

Các bước của quá trình khai phá dữ liệu

12

Hình 1.2

Cây quyết định

17

Hình 2.1

Giao diện khởi đầu của WEKA 3.6.9

31

Hình 2.2

Kết quả thi tuyển sinh vào lớp 10 năm học 2013-2014

32

Hình 2.3


Dữ liệu sau khi đã loại bỏ các thuộc tính không cần
thiết

33

Hình 2.4

Một số thuộc tính có dữ liệu kiểu liên tục

34

Hình 2.5

Các thuộc tính sau khi đã được rời rạc

36

Hình 2.6

Hình ảnh cây quyết định

39

Hình 2.7

Cây quyết định theo tổng điểm thi

40

Hình 2.8


Cây quyết đinh theo tổng điểm thi và nhóm điểm

42

Hình 3.1

Thứ tự các bước giải quyết bài toán

44

Hình 3.2

Dữ liệu thô ban đầu

45

Hình 3.3

Các mẫu luật được lưu trong CSDL

46

Hình 3.4

Các luật được tạo bởi phần mềm Weka

47

Hình 3.5


Giao diện chính chương trình

48

Hình 3.6

Màn hình nhập liệu và kết quả tư vấn

49

Hình 3.7

Đánh giá kết quả

50

Hình 3.8

Thống kê theo điểm thi

51

Hình 3.9

Thống kê theo trường THCS

51

Hình 3.10


Thống kê theo trường THPT

52

6


DANH MỤC CÁC BẢNG
Số bảng

Tên bảng

Trang

Bảng 1.1

Điểm cộng ứng với kết quả học tập và rèn luyện
các năm lớp 6,7,8,9

8

Bảng 1.2

Thống kê điểm chuẩn của các trường THPT công
lập thuộc các quận nội thành Hải Phòng các năm
2011-2015

11


Bảng 2.1

Kết quả phân lớp bằng cây quyết định

45

Bảng 3.1

Các thuộc tính chương trình tuyển sinh

48

Bảng 3.2

Mô tả các trường lưu trữ mẫu luật trong CSDL

50

7


MỞ ĐẦU
"We are drowning in Data but starved for knowledge."
(Chúng ta đang chết chìm trong dữ liệu nhưng lại chết đói về tri thức)
John Naisbitt
Chúng ta đều biết công nghệ thông tin nói chung và tin học hóa các lĩnh vực
kinh tế, xã hội nói riêng đã đem lại những thành công đáng kể, đóng góp vào sự
phát triển của toàn nhân loại. Đồng thời với việc tin học hóa, việc lưu trữ thông tin
của các lĩnh vực kể trên đã phát triển một cách nhanh chóng.
Tuy nhiên, việc lưu trữ một cách ồ ạt với rất nhiều thông tin, trong đó có

nhiều thông tin có thể bị trùng lặp đó cũng gây ra những khó khăn, đó là từ nguồn
dữ liệu mênh mông bao la, làm thế nào để khai thác thành những tri thức có ích, có
giá trị.
Chính vì vậy một lĩnh vực mới ra đời, nó sử dụng các kỹ thuật để dữ liệu mà
ta đã lưu trữ được sẽ được chuyển đổi thành tri thức có ích. Đó chính là lĩnh vực
khai phá dữ liệu.
Mô tả quá trình phát hiện ra tri thức trong CSDL chính là nhiệm vụ của khai
phá dữ liệu. Các tri thức tiềm ẩn từ dữ liệu sẽ kết xuất ra từ quá trình này giúp cho
việc dự báo trong kinh doanh, các lĩnh vực sản xuất... So với phương pháp truyền
thống trước kia, khai phá dữ liệu giúp giảm chi phí về thời gian.
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều lĩnh vực, nhiều
ngành như thống kê, cơ sở dữ liệu, trí tuệ nhân tạo nâng cao, thuật toán, tính toán
song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia... Đặc biệt phát
hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, dùng các
phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật...
Lĩnh vực giáo dục cũng được các chuyên gia khai phá dữ liệu đặc biệt quan
tâm. Mọi người đều biết giáo dục là nhân tố quyết định sự phát triển của một quốc

8


gia về nhiều mặt. Một đất nước có phát triển bền vững hay không phụ thuộc vào
việc định hướng, hoạch định chính sách cho thế hệ trẻ.
Học và thi là hai mặt của một quá trình trong giáo dục. Học là quá trình tích
lũy, trau dồi kiến thức. Thi là để đánh giá quá trình học của người học.
Trong cuộc đời, mỗi người đều trải qua nhiều kỳ thi. Đặc biệt là học sinh,
sinh viên thì việc thi càng xảy ra thường xuyên: Thi giữa kỳ, thi cuối năm, thi lên
lớp, thi hết cấp,…
Kỳ thi nào cũng quan trọng, nhưng đã có thi thì có đỗ và có trượt. Không ai
muốn mình trượt thi dù đó là kỳ thi nào. Vậy nên kỳ thi tuyển vào lớp 10 đối với

học sinh phổ thông là cực kỳ quan trọng. Nó quan trọng ở chỗ mỗi năm số lượng
thí sinh được tuyển vào trường THPT công lập ở thành phố Hải Phòng chiếm
khoảng 70%, trong số nhiều trường THPT thì có số ít trường thuộc tốp trên, một số
trường thuộc tốp giữa và một số thuộc tốp cuối. Nếu các em thi được vào một
trường THPT thuộc tốp trên thì sau ba năm, việc thi đỗ một trường đại học của các
em là không mấy khó khăn. Vì vậy lựa chọn để đăng ký thi vào một trường THPT
phù hợp với khả năng của bản thân là một vấn đề rất quan trọng không chỉ với học
sinh mà ngay cả với các bậc phụ huynh.
Thành phố Hải Phòng có 7 quận và 8 huyện. Trong đó 7 quận nội thành với
13 trường THPT công lập, có một số trường THPT nằm trong tốp 100 các trường
THPT trên cả nước. Kết quả này được đánh giá bằng tỷ lệ học sinh đỗ vào đại học,
cao đẳng hàng năm của mỗi trường.
Trong thực tế có nhiều học sinh có học lực trung bình nhưng lựa chọn
trường phù hợp nên đã thi đỗ vào trường công lập, trong khi có những học sinh có
học lực khá nhưng chọn trường quá cao hoặc quá thấp thì đạt những kết quả không
mong muốn.
Việc tư vấn cho học sinh đăng ký dự thi vào một trường THPT phù hợp với
trình độ của các em chưa được các trường quan tâm. Chủ yếu các em được các

9


thầy cô ở trường THCS định hướng và tư vấn giúp bằng kinh nghiệm, điều này làm
nhiều bậc phụ huynh không thực sự yên tâm.
Bản thân tác giả làm trong ngành giáo dục, nhiều năm tham gia công tác
tuyển sinh vào lớp 10, đồng thời cũng từng là một phụ huynh có con đã thi vào lớp
10 nên rất chia sẻ với những lo lắng của các phụ huynh.
Từ nguồn dữ liệu tuyển sinh được lưu trữ từ nhiều năm của phòng Giáo dục
Trung học - Sở Giáo dục Đào tạo Hải Phòng, từ các kiến thức đã được học từ môn
khai phá dữ liệu, tác giả mong muốn xây dựng một chương trình hỗ trợ học sinh

cũng như phụ huynh học sinh có thể căn cứ để đăng ký nguyện vọng vào một
trường THPT mà khả năng đỗ cao nhất.
Đó là lý do tôi chọn đề tài: “Xây dựng hệ hỗ trợ cho học sinh dự tuyển các
trường THPT trên địa bàn nội thành Hải Phòng”.

BỐ CỤC CỦA LUẬN VĂN
Ngoài các phần mở đầu, mục lục, danh mục hình, kết luận, tài liệu tham
khảo. Luận văn được chia làm 3 chương:
Chương I: TỔNG QUAN
Chương này trình bày các vấn đề tổng quan về công tác tuyển sinh vào lớp
10 và đặc thù của tuyển sinh vào lớp 10 tại thành phố Hải Phòng. Những khái niệm
cơ bản về khai phá dữ liệu và việc áp dụng phương pháp cây quyết định vào bài
toán hỗ trợ học sinh đăng kí dự thi vào lớp 10.
Chương 2: HỆ HỖ TRỢ RA QUYẾT ĐỊNH ĐĂNG KÝ DỰ THI VÀO LỚP 10
Những khái niệm cơ bản về một hệ hỗ trợ ra quyết định. Trình bày nội dung
thuật toán C4.5 sẽ được dùng để áp dụng vào tạo cây quyết định cho bài toán hỗ
trợ tuyển sinh, giới thiệu các chức năng của phần mềm Weka, và các bước thực
hiện bài toán “Xây dựng hệ hỗ trợ cho học sinh dự tuyển các trường THPT trên
địa bàn nội thành Hải Phòng”
10


Chương 3: CÀI ĐẶT - THỬ NGHIỆM
Trong chương này tác giả trình bày các nội dung: Mô hình chung bài toán,
các bước thực hiện từ dữ liệu thô ban đầu đến xây dựng chương trình hỗ trợ tư vấn
tuyển sinh và kết quả thử nghiệm của chương trình.

11



Chương 1: TỔNG QUAN
1.1. Tổng quan về bài toán tuyển sinh trung học phổ thông
1.1.1. Đối tượng và phương thức tuyển sinh
Đối tượng tuyển sinh là người có độ tuổi theo quy định và đã tốt nghiệp
trung học cơ sở chương trình giáo dục phổ thông hoặc chương trình giáo dục
thường xuyên.
Một trong ba phương thức sau được áp dụng để tuyển sinh trung học phổ
thông:
Xét tuyển: dựa trên kết quả học tập rèn luyện, của 4 năm học ở trung học
cơ sở của đối tượng tuyển sinh, nếu lưu ban lớp nào thì lấy kết quả năm học lại của
lớp đó;
Thi tuyển;
Kết hợp thi tuyển với xét tuyển.
1.1.2. Hồ sơ tuyển sinh
Hồ sơ tuyển sinh gồm:
1. Bản sao giấy khai sinh có công chứng.
2. Bằng tốt nghiệp trung học cơ sở hoặc bản sao bằng tốt nghiệp trung học
cơ sở có công chứng hoặc giấy chứng nhận tốt nghiệp trung học cơ sở tạm thời.
3. Học bạ cấp trung học cơ sở (bản chính).
4. Giấy xác nhận chế độ khuyến khích, ưu tiên do cơ quan có thẩm quyền
cấp (nếu có).
5. Giấy xác nhận do ủy ban nhân dân phường, xã, thị trấn cấp (đối với
người học đã tốt nghiệp trung học cơ sở từ những năm học trước) không trong thời
gian đang vi phạm pháp luật hoặc thi hành án phạt tù; cải tạo không giam giữ.

12


1.1.3. Tuyển thẳng, chế độ ưu tiên, khuyến khích
1.1.3.1. Các đối tượng sau đây được tuyển thẳng vào trung học phổ thông

Các đối tượng sau đây được tuyển thẳng vào trung học phổ thông:
Học sinh trường phổ thông dân tộc nội trú;
Học sinh là người dân tộc thiểu số;
Học sinh khuyết tật;
Học sinh đạt giải từ cấp quốc gia trở lên về văn hóa; thể dục thể thao; văn
nghệ; hoặc cuộc thi khoa học kĩ thuật dành cho học sinh trung học.
1.1.3.2. Đối tượng được cộng điểm ưu tiên.
Từng loại đối tượng được hưởng chế độ ưu tiên được Sở giáo dục và đào tạo
quy định điểm cộng thêm như sau:
a) Nhóm đối tượng 1:
Là con của liệt sĩ;
Là con của thương binh mất sức lao động 81% trở lên;
Là con của bệnh binh mất sức lao động 81% trở lên;
Là con của người được cấp “Giấy chứng nhận người hưởng chính sách như
thương binh mà người được cấp Giấy chứng nhận người hưởng chính sách như
thương binh bị suy giảm khả năng lao động 81% trở lên”.
b) Nhóm đối tượng 2:
Là con của Anh hùng lao động, con của Anh hùng lực lượng vũ trang, con
của Bà mẹ Việt Nam anh hùng;
Là con của thương binh mất sức lao động dưới 81%;
Là con của bệnh binh mất sức lao động dưới 81%;

13


Là con của người được cấp “Giấy chứng nhận người hưởng chính sách như
thương binh mà người được cấp Giấy chứng nhận người hưởng chính sách như
thương binh bị suy giảm khả năng lao động dưới 81%”.
c) Nhóm đối tượng 3:
Người có cha hoặc mẹ là người dân tộc ít người;

Người dân tộc ít người;
Người học đang học tập, sinh sống ở các vùng có điều kiện kinh tế - xã hội
đặc biệt khó khăn.
1.1.3.3. Đối tượng được cộng điểm khuyến khích.
Đối tượng và điểm cộng thêm cho từng loại đối tượng được hưởng chế độ
khuyến khích được Sở giáo dục và đào tạo quy định chi tiết.
1.2. Công tác tuyển sinh vào lớp 10 của thành phố Hải Phòng.
1.2.1. Đặc điểm
Mỗi năm thành phố Hải Phòng có khoảng 18.000 học sinh dự thi vào lớp 10.
Tổng số chỉ tiêu dành cho các trường công lập chiếm khoảng 70%, còn lại khoảng
30% dành cho khối trường dân lập và các trung tâm giáo dục thường xuyên. Như
vậy mỗi năm có khoảng 13.000 học sinh đỗ vào các trường công lập .
Thành phố Hải Phòng hiện có 40 trường THPT hệ công lập. (39 trường
THPT và 01 Trường THPT chuyên Trần Phú). Trong số 39 trường THPT này 2
trường THPT Cát Bà, Cát Hải thực hiện xét tuyển kết quả học tập, rèn luyện của 4
năm học ở bậc THCS của học sinh, 37 trường THPT thực hiện phương thức vừa
thi tuyển, vừa xét tuyển. Riêng trường THPT chuyên Trần Phú thi tuyển riêng.
Bài toán Xây dựng hệ hỗ trợ cho học sinh dự tuyển vào các trường THPT
trên địa bàn nội thành Hải Phòng tập trung vào đối tượng vừa thi tuyển vừa xét
tuyển, vì vậy các thông tin không liên quan sẽ không được trình bày trong luận
văn.

14


1.2.2. Thi tuyển và xét tuyển
Như đã trình bày ở trên, thành phố Hải Phòng có 37 trường THPT thuộc
công lập vừa tổ chức thi tuyển, vừa kết hợp xét tuyển: Kết quả điểm thi 2 môn
Toán, Ngữ Văn trong kì thi vào lớp 10 THPT công lập (không môn nào bị điểm 1
trở xuống) và xét kết quả học tập, rèn luyện của 4 năm học THCS và các điểm ưu

tiên, khuyến khích (nếu có).
1.2.2.1. Xét tuyển
Mỗi học sinh sẽ có 4 tiêu chuẩn xét tuyển: Điểm học tập và rèn luyện, điểm
thi nghề, điểm ưu tiên, điểm khuyến khích
Bảng 1.1: Điểm cộng ứng với kết quả học tập và rèn luyện các năm lớp 6,7,8,9
1)

Kết quả học tập và rèn luyện

Điểm cộng

Học sinh có: Hạnh kiểm tốt, học lực giỏi

5.0 điểm

Học sinh có: Hạnh kiểm khá, học lực giỏi hoặc hạnh kiểm tốt,
học lực khá

4.5 điểm

Học sinh có: Hạnh kiểm khá, học lực khá

4.0 điểm

Học sinh có: Hạnh kiểm Tb, học lực giỏi hoặc hạnh kiểm tốt,
học lực Tb

3.5 điểm

Học sinh có: Hạnh kiểm khá, học lực Tb hoặc hạnh kiểm Tb,

học lực khá

3.0 điểm

Các trường hợp còn lại

2.5

2)

điểm

Điểm thi nghề:

Giỏi

1.5 điểm

Khá

1.0

3)

điểm

Điểm ưu tiên:

Là con của liệt sĩ;
Là con của thương binh mất sức lao động 81% trở lên;

Là con của bệnh binh mất sức lao động 81% trở lên;
Là con của người được cấp “Giấy chứng nhận người được
hưởng chính sách như thương binh mà người được cấp Giấy
chứng nhận người hưởng chính sách giống như thương binh bị
suy giảm khả năng lao động 81% trở lên”

3.0 điểm

Là con của Anh hùng lao động, con của Anh hùng lực lượng vũ
trang, con của Bà mẹ Việt Nam anh hùng;

2.0 điểm

15


Là con của thương binh mất sức lao động dưới 81%;
Là con của bệnh binh mất sức lao động dưới 81%;
Là con của người được cấp “Giấy chứng nhận người được
hưởng chính sách như thương binh mà người được cấp Giấy
chứng nhận người hưởng chính sách giống như thương binh bị
suy giảm khả năng lao động dưới 81%”.
4)

Điểm khuyến khích:

Đạt giải Nhất QG môn văn hóa

4.0 điểm


Đạt giải Nhì QG môn văn hóa

3.5 điểm

Đạt giải Ba QG môn văn hóa

3.0 điểm

Đạt giải Nhất TP môn văn hóa

2.0 điểm

Đạt giải Nhì TP môn văn hóa

1.5 điểm

Đạt giải ba TP môn văn hóa

1.0

điểm

1.2.2.2. Thi tuyển:
Thi viết 2 môn Ngữ Văn và Toán.
Thời gian làm bài 120 phút/môn thi
Điểm của bài thi: Điểm của bài thi được cho theo thang điểm từ 0 đến 10,
điểm lẻ đến 0,25
Điểm xét tuyển được tính theo công thức: (1.1)
Điểm xét tuyển = 2*(Điểm Văn + Điểm Toán)+ Điểm HT_RL+Điểm ƯT+Điểm KK


Thí sính trúng tuyển phải không có bài thi nào nhỏ hơn 1.

Bài toán xây dựng hệ hỗ trợ tuyển sinh cho học sinh dự tuyển vào các
trường THPT trên địa bàn nội thành Hải Phòng chỉ quan tâm đến đối tượng vừa thi
tuyển vừa xét tuyển nên các học sinh thi vào trường THPT chuyên Trần Phú và
học sinh đăng ký vào các trường ở ngoại thành không nằm trong phạm vi tư vấn.

16


Bảng 1.2: Thống kê điểm chuẩn của các trường THPT công lập thuộc các quận nội thành Hải Phòng các năm 2011-2015
STT

Các trường Nội thành

Quận

2011-2012

2012-2013

2013-2014

2014-2015

Điểm TB

1 THPT Ngô Quyền

Lê Chân


50.5

50.5

50.5

52.5

51

2 THPT Thái Phiên

Ngô Quyền

50.5

50

49.5

51.5

50.375

3 THPT Lê Quý Đôn

Hải An

47.5


50

46

49.5

48.25

4 THPT Trần Nguyên Hãn

Lê Chân

49

48

49

51

49.25

5 THPT Hồng Bàng

Hồng Bàng

45

46.5


45

48.5

46.25

6 THPT Lê Hồng Phong

Hồng Bàng

47.5

45

46.5

48

46.75

7 THPT Lê Chân

Lê Chân

38

43.5

41


44.5

41.75

8 THPT Hải An

Hải An

45

43.5

46

45.5

45

9 THPT Kiến An

Kiến An

44.5

43.5

47.5

47


45.625

10 THPT Đồng Hòa

Kiến An

31.5

38.5

38.5

39.5

37

Dương Kinh

36.5

41

41

40

39.625

11 THPT Mạc Đĩnh Chi

12 THPT Đồ Sơn

Đồ Sơn

20

30.5

30.5

34

28.75

13 THPT Phan Đăng Lưu

Kiến An

23.5

26.5

32.5

36

29.6

17



1.3. Khai phá dữ liệu
1.3.1. Định nghĩa khai phá dữ liệu
Khai phá dữ liệu (datamining) được định nghĩa như là một quá trình chắt lọc
hay khai phá tri thức từ một lượng lớn dữ liệu. Một ví dụ hay được sử dụng là là
việc khai thác vàng từ đá và cát, Dataming được ví như công việc "Đãi cát tìm
vàng" trong một tập hợp lớn các dữ liệu cho trước. Thuật ngữ Dataming ám chỉ
việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có
nhiều thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ Datamining như
Knowledge Mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức),
data/patern analysis (phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu),
datadredging (nạo vét dữ liệu),...
Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để
tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập
hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong
tập dữ liệu đó.
Quy trình phát hiện tri thức thường tuân theo các bước sau:

Hình 1.1: Các bước của quá trình khai phá dữ liệu

18


Bước một: Đây là quá trình tìm hiểu các lĩnh vực của bài toán, từ đó hình
thành bài toán và định nghĩa bài toán, việc quan trọng ở bước này là xác định được
các nhiệm vụ, yêu cầu của bài toán. Ở bước này sẽ quyết định việc rút ra được
những tri thức gì từ dữ liệu. Tại bước này cũng quyết định lựa chọn phương pháp
khai phá dữ liệu sao cho phù hợp với mục đích cũng như nội dung của dữ liệu.
Bước hai: Từ việc xác định được các nhiệm vụ của bài toán từ bước 1,
chuyển qua bước thu thập dữ liệu. Dữ liệu có thể được lấy từ nhiều nguồn khác

nhau, có thể có những thông tin bị trùng lặp, hay những nội dung bị khuyết, thiếu.
Khi đó việc cần làm trong bước này là đồng bộ các kiểu dữ liệu, rút gọn các những
thuộc tính thừa hoặc không cần thiết và bổ sung nhưng thông tin bị khuyết thiếu.
Nhiệm vụ của bước này là bộ dữ liệu phải được nhất quán, đầy đủ nhưng cũng đòi
hỏi phải được rút gọn nhất. Thông thường bước này tốn rất nhiều thời gian và công
sức trong toàn bộ quá trình khai phá tri thức.
Bước ba: Sau khi có bộ dữ liệu từ bước hai, chuyển qua bước ba là bước rút
ra tri thức. Nhiệm vụ của bước này là rút ra các mẫu và các mô hình ẩn dưới các dữ
liệu. Có thể coi đây là bước quan trọng nhất trong việc khai phá dữ liệu. Nó bao
gồm các công đoạn như chức năng, nhiệm vụ cũng như mục đích của khai phá dữ
liệu. Sử dụng phương pháp nào để khai phá dữ liệu cho phù hợp. Thông thường
một bài toán khai phá dữ liệu có dạng mô tả - đưa ra những tính chất chung nhất
của dữ liệu hoặc dự báo – phát hiện và suy diễn dựa trên các dữ liệu đã có. Khi đó
việc lựa chọn phương pháp phù hợp sẽ quyết định đến sự thành công của việc khai
phá dữ liệu.
Bước bốn: Các tri thức đã nhận được từ bước ba sẽ được làm rõ hơn đối với
mỗi dạng mô tả cũng như dự đoán. Quá trình làm rõ này có thể trải qua các bước
lặp đi lặp lại, khi đó kết quả mà ta thu nhận được là trung bình cộng trong tất cả
các lần thực hiện.
Bước năm: Những tri thức đã được tìm thấy ở bước bốn sẽ được sử dụng, tại
bước này chính là ứng dụng những kết quả mà khai phá tri thức đem lại. Đồng thời
19


cũng giúp ta hiểu rõ hơn, sâu hơn về tri thức mà ta đã tìm được để tiếp tục làm sáng
tỏ các mô tả cũng như các dự đoán.
Kết quả của quá trình phát hiện tri thức được ứng dụng trong các lĩnh vực
khác nhau. Các kết quả có thể là các dự đoán hoặc các mô tả nên chúng có thể
được đưa vào các hệ thống nhằm hỗ trợ ra quyết định nhằm tự động hoá quá trình.
1.3.2. Các chức năng chính của khai phá dữ liệu.

Data Mining được chia nhỏ thành một số hướng chính như sau:
• Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt
khái niệm. Ví dụ: tóm tắt văn bản.
• Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá
đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số
họ sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực
kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v.
• Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào
một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời
tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như
cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Người
ta còn gọi phân lớp là học có giám sát (học có thầy).
• Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng cũng như
tên của cụm chưa được biết trước. Người ta còn gọi phân cụm là học không giám
sát (học không thầy).
• Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá luật
kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng
dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo
cao.
1.3.3. Các phương pháp khai phá dữ liệu
Khai phá dữ liệu bao gồm các thành phần cơ bản sau: Biểu diễn mô hình,
kiểm định mô hình và phương pháp tìm kiếm. Cụ thể:
20


Biểu diễn mô hình: Việc miêu tả các mẫu có thể khai thác được biểu diễn
theo một ngôn ngữ nào đó được gọi là biểu diễn mô hình. Nếu mô hình càng rõ
ràng thì học máy sẽ tạo ra các mẫu càng chính xác cho dữ liệu. Nếu mô hình quá
lớn sẽ làm giảm khả năng dự đoán của học máy. Việc miêu tả mô hình càng lớn
dẫn tới việc học máy bị quá làm giảm khả năng dự đoán các dữ liệu chưa biết.

Khi đó việc giải thích mô hình trở lên phức tạp hơn và việc tìm kiếm cũng trở
thành khó khăn hơn.
Ban đầu mô hình được xác định bằng cách kết hợp giữa các biến độc lập với
các biến đầu ra, mà biến đầu ra phụ thuộc vào đó. Tiếp theo đi tìm những tham số
mà bài toán cần tập trung giải quyết. Công việc tìm kiếm mô hình sẽ tạo ra được
mô hình phù hợp với tham số xác định dựa trên dữ liệu (đôi khi mô hình hoặc các
tham số có thể thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập các
dữ liệu được chia thành 2 tập dữ liệu: tập dữ liệu học và tập dữ liệu thử. Ban đầu
tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu.
Sau đó mô hình sẽ được đánh giá bằng cách sử dụng tập các dữ liệu thử vào mô
hình và thay đổi các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể một
số giải thuật học máy (ví dụ như cây quyết định), mạng Nơ_ron, suy diễn hướng
tình huống, các kỹ thuật phân lớp.
Kiểm định mô hình (model evaluation): Là việc đánh giá đồng thời ước
lượng các mô hình chi tiết và chuẩn trong quá trình xử lý và phát hiện tri thức với
sự ước lượng có dự báo chính xác hay không, có thoả mãn cơ sở logic hay không.
Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: Tìm
kiếm tham số và tìm kiếm mô hình. Với tìm kiếm tham số, giải thuật cần tìm kiếm
các tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình, với các dữ liệu quan
sát được và với một mô tả mô hình đã định. Tìm kiếm mô hình thực hiện giống
như một vòng lặp qua phương pháp tìm kiếm tham số: Mô tả mô hình thay đổi
cho ta một họ các mô hình. Đối với một mô tả mô hình, phương pháp tìm kiếm
tham số được áp dụng để đánh giá chất lượng mô hình.
21


Phương pháp suy diễn/quy nạp:
Mỗi cơ sở dữ liệu là một kho thông tin nhưng kho thông tin đó còn có thể
suy diễn ra những thông tin hữu ích hơn. Để thực hiện việc này có hai kỹ thuật
chính đó là suy diễn và quy nạp.

Phương pháp suy diễn: Đây là phương pháp rút ra thông tin là kết quả logic
của các thông tin trong nguồn cơ sở dữ liệu. Phương pháp suy diễn dựa trên các
sự kiện chính xác nhằm suy ra các tri thức mới từ các thông tin có sẵn. Mẫu chiết
xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. Ví dụ
như toán tử liên kết áp dụng cho bảng quan hệ, bảng đầu chứa thông tin về các
công nhân và phân xưởng, bảng thứ hai chứa các thông tin về các phân xưởng và
các đốc công. Như vậy sẽ suy ra được mối quan hệ giữa các công nhân và các đốc
công.
Phương pháp quy nạp: Phương pháp này cho phép suy ra các thông tin
được sinh ra từ CSDL. Các thông tin mà phương pháp này đem lại là lượng thông
tin hay tri thức cấp cao diễn tả về các đối tượng trong CSDL. Phương pháp này
liên quan đến việc tìm kiếm các mẫu trong CSDL. Khi đó nó sẽ tự tìm kiếm, tạo
mẫu đồng thời sinh ra tri thức, không phải bắt đầu với các tri thức đã biết trước.
Đối với khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật.
Phương pháp K-láng giềng gần: Một đối tượng được phân lớp dựa vào k
láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật
toán. Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các
đối tượng
Kỹ thuật K -láng giềng gần tuy là một phương pháp tìm kiếm đơn giản,
nhưng nó có một số mặt hạn chế giới là hạn phạm vi ứng dụng của nó, do là thuật
toán có độ phức tạp tính toán là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu. Với
phương pháp K -láng giềng không đưa ra lý thuyết để hiểu cấu trúc dữ liệu. Hạn
chế đó có thể được khắc phục bằng kỹ thuật cây quyết định.

22


Phương pháp sử dụng cây quyết định và luật: Cây quyết định thể hiện các
quyết định và tình huống xảy ra theo trình tự.
Kết quả của quá trình xây dựng mô hình với kỹ thuật phân lớp dựa trên cây

quyết định sẽ cho ra một cây quyết định cụ thể. Với cây quyết định này được dùng
để phân lớp các đối tượng dữ liệu chưa biết cũng như việc đánh giá độ chính xác
của mô hình. Nó tương ứng với hai giai đoạn của quá trình phân lớp là quá trình
xây dụng cây quyết định và quá trình sử dụng cây quyết định.
Một hạn chế chung cho các bài toán sử dụng cây quyết định là sử dụng
nhiều bộ nhớ. Kích thước của mẫu dữ liệu huấn luyện càng lớn thì bộ nhớ dùng
cho cây quyết định càng nhiều. Mặc dù một số chương trình sinh cây quyết định
có hỗ trợ bộ nhớ ngoài xong nó lại liên quan đến thời gian thực hiện. Do vậy, việc
tỉa bớt cây quyết định là rất quan trọng. Đặc biệt các nút lá không ổn định trong
cây quyết định sẽ cần được tỉa bớt. Kỹ thuật tỉa trước là việc dừng sinh cây thực
thi khi chia dữ liệu không có ý nghĩa.
Phương pháp phát hiện luật kết hợp: Phương pháp này giúp tìm ra các luật
kết hợp giữa các thành phần dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai
phá dữ liệu là tập luật kết hợp tìm được. Ví dụ đơn giản về luật kết hợp như sau: sự
kết hợp giữa hai thuộc tính A và B chính là sự xuất hiện của A trong bản ghi kéo
theo sự xuất hiện của B trong cùng bản ghi đó: A → B.
1.4. Cây quyết định
1.4.1. Khái niệm
Cây quyết định là mô hình kiểu dự báo, mỗi nút ứng với một biến, đường
nối giữa nó với nút con thể hiện giá trị cụ thể của biến, mỗi nút lá đại diện cho giá
trị dự đoán của biến mục tiêu. Kỹ thuật học máy dùng trong cây quyết định được
gọi là học bằng cây quyết đinh.

23


Hình 1.2: Cây quyết định
Khi tiến hành phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu
được đưa vào để kiểm tra trên cây quyết định. Đối với mỗi mẫu tương ứng sẽ có
một đường đi từ gốc đến lá. Khi đó lá sẽ biểu diễn giá trị dự đoán phân lớp của

mẫu đó.
1.4.2. Ưu điểm và nhược điểm của cây quyết định
Cây quyết định là một phương pháp phân lớp rất hiệu quả và có những ưu
điểm chính sau:
Khả năng sinh ra các quy tắc hiểu được: Cây quyết định có thể dễ dàng hiểu
được khi được giải thích ngắn, khả năng sinh ra các quy tắc có thể chuyển đổi
được sang các câu lệnh SQL.
Khả năng thực thi trong những lĩnh vực hướng quy tắc: Quy tắc quy nạp nói
chung và cây quyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh vực thực
sự là các quy tắc.
Dễ dàng tính toán trong khi phân lớp: Các thuật toán sử dụng để tạo ra cây
quyết định thường tạo ra những cây có số phân nhánh thấp và các kiểm tra là đơn
giản tại từng node. Những kiểm tra điển hình là: so sánh số lượng phần tử của một
tập hợp với các phép nối đơn giản. Quá trình sẽ được thực thi trên máy tính,

24


những kiểm tra này chuyển thành các hàm logic đồng thời những toán hạng được
thực thi nhanh và có độ phức tạp tính toán đơn giản.
Khả năng xử lý tất cả thuộc tính liên tục với thuộc tính rời rạc: Cây quyết
định có thể xử lý cả thuộc tính có kiểu liên tục cũng như thuộc tính dạng rời rạc.
Tuy rằng với thuộc tính liên tục cần nhiều tài nguyên tính toán hơn. Trong đó một
số kỹ thuật khác chỉ có thể thực hiện được trên một loại biến.
Thể hiện rõ ràng những thuộc tính tốt nhất: Thuật toán xây dựng cây quyết
định đưa ra thuộc tính mà phân chia tốt nhất tập dữ liệu đào tạo bắt đầu từ nút gốc
của cây, khi đó có thể thấy thuộc tính nào là quan trọng nhất cho việc dự đoán hay
phân lớp.
Nhược điểm:
Với những bài toán mục tiêu là dự đoán giá trị của thuộc tính liên tục, cây

quyết định không thích hợp. Ví dụ như mức thu nhập, đo huyết áp hay lãi xuất
ngân hàng,…
Với những bài toán có quá nhiều lớp tốn nhiều dung lượng bộ nhớ và có thể
xẩy ra lỗi.
1.4.3. Xây dựng cây quyết định
Quá trình xây dựng cây quyết định gồm hai giai đoạn: Tạo cây và tỉa cây
Giai đoạn một tạo cây quyết định: Giai đoạn này tất cả các dữ liệu huấn
luyện đều ở gốc, sau đó phân chia dữ liệu huấn luyện đến từng nhánh theo chách
đệ quy cho tới khi đạt được cây quyết định với tất cả các lá được gán nhãn lớp
riêng.
Giai đoạn thứ hai cắt, tỉa bớt các nhánh trên cây quyết định. Giai đoạn này
nhằm đơn giản hóa kèm theo khái quát hóa từ đó làm tăng độ chính xác của cây
quyết định bằng cách loại bỏ những nhánh có phần tử hỗn loạn hoặc những phần
từ không thuộc vào một lớp nào. Giai đoạn này nhiệm vụ chỉ truy cập dữ liệu trên
cây quyết định đã được phát triển trong giai đoạn trước. Quá trình này chỉ chiếm
25