HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

NGUYỄN XUÂN HẢI

KHAI PHÁ DỮ LIỆU
VÀ ỨNG DỤNG TRONG DỰ BÁO TIẾN TRÌNH HỌC TẬP
CỦA SINH VIÊN ĐẠI HỌC THỦY LỢI

LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

HÀ NỘI - 2016


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

NGUYỄN XUÂN HẢI

KHAI PHÁ DỮ LIỆU
VÀ ỨNG DỤNG TRONG DỰ BÁO TIẾN TRÌNH HỌC TẬP
CỦA SINH VIÊN ĐẠI HỌC THỦY LỢI
CHUYÊN NGÀNH : KHOA HỌC MÁY TÍNH
MÃ SỐ:

0

60.48.01.01

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

biệt trong thời gian tôi theo học khóa thạc sỹ; Các Quý thầy cô tại Học viện Công
nghệ Bưu chính Viễn thông đã truyền đạt cho tôi những kiến thức bổ ích trong suốt
hai năm học vừa qua; Ban Giám hiệu, các Phòng chức năng và đặc biệt là Phòng
Đào tạo ĐH&SĐH – Trường Đại học Thủy lợi đã tạo điều kiện tối đa cho tôi được
học tập, nghiên cứu trong suốt thời gian qua.
Trong quá trình nghiên cứu của mình, mặc dù được sự hướng dẫn rất nhiệt
tình, nghiêm túc của TS. Nguyễn Đình Hóa và các thầy cô giáo trong Học viện
Công nghệ Bưu Chính Viễn thông, Đại học Thủy lợi cùng với sự nỗ lực của cá nhân
nhưng cũng không thể tránh được những thiếu sót. Tác giả chân thành mong nhận
được những ý kiến đóng góp từ quý Thầy, Cô và các bạn bè đồng nghiệp.
Trân trọng cám ơn.
Tác giả
Nguyễn Xuân Hải


iii

MỤC LỤC
LỜI CAM ĐOAN ................................................................................................................... i
LỜI CÁM ƠN………………………………………………………………………………………………ii
MỤC LỤC….…………………………………………………………………………………………….…iii
DANH MỤC TỪ VIẾT TẮT ................................................................................................ v
DANH MỤC CÁC BẢNG BIỂU ......................................................................................... vi
DANH MỤC CÁC HÌNH VẼ ............................................................................................. vii
MỞ ĐẦU……………………………..………………………………………………………………………1
Tính cấp thiết của đề tài..................................................................................................... 1
Tổng quan về vấn đề nghiên cứu ....................................................................................... 2
Mục đích, đối tượng, phạm vi và phương pháp nghiên cứu .............................................. 2
Cấu trúc luận văn ............................................................................................................... 3
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU TRONG BÀI TOÁN DỰ BÁO ... 4

Cấu trúc của cây quyết định ........................................................................... 17
Xây dựng cây quyết định ................................................................................ 18
Biến đổi cây quyết định thành luật ................................................................. 22
Một số thuật toán xây dựng cây quyết định.................................................... 22


iv

2.2. K Láng giềng gần nhất ............................................................................................. 41
2.2.1. Tổng quan về K láng giềng gần nhất ................................................................ 41
2.2.2. Thuật toán K láng giềng gần nhất ..................................................................... 41
2.3. Kết luận chương 2 .................................................................................................... 52
CHƯƠNG 3. DỰ BÁO TIẾN TRÌNH HỌC TẬP CỦA SINH VIÊN ĐẠI HỌC THỦY
LỢI………………………………………………………………………………………………………..…53
3.1 Giới thiệu bài toán ................................................................................................. 53
3.2

Phân tích và xây dựng mô hình bài toán................................................................ 53
Phân tích bài toán ........................................................................................... 53
Mô hình bài toán ............................................................................................. 54

3.3

Thực nghiệm .......................................................................................................... 59
Phương pháp đánh giá tập dữ liệu .................................................................. 59
Các độ đo được dùng để dự báo ..................................................................... 59
Mô hình dự báo tiến trình học tập của sinh viên ............................................ 60

3.4


Công nghệ thông tin

2

CSDL

Cơ sở dữ liệu

3

ĐATN

Đồ án tốt nghiệp

4

ĐHTL

Đại học Thủy lợi

5

GD&ĐT

Giáo dục và Đào tạo

6

KNN


Tổng số tín chỉ tích lũy đến kỳ

13

TCTLK

Tổng số tín chỉ tích lũy kỳ

K Nearest Neighbors
(K láng giềng gần nhất)
Knowlegde Discovery in Databases
(Quy trình khám phá tri thức trong cơ sở dữ liệu)
K-fold cross validation
(Đánh giá chéo dựa trên k phần)


vi

DANH MỤC CÁC BẢNG BIỂU
Bảng 2.1. Tập mẫu huấn luyện chơi đá bóng (1)................................................................. 24
Bảng 2.2. Tập mẫu huấn luyện chơi đá bóng (2)................................................................. 30
Bảng 2.3. Tập mẫu huấn luyện chơi đá bóng (3)................................................................. 32
Bảng 2.4. Tỷ lệ Gain cho thuộc tính Độ ẩm ở lần tạo cây thứ nhất .................................... 34
Bảng 2.5. Tỷ lệ Gain cho thuộc tính Độ ẩm ở lần tạo cây thứ hai ...................................... 37
Bảng 2.6. Chuẩn hóa Min – Max, Z-Score thuộc tính tuổi .................................................. 44
Bảng 2.7. Chuẩn hóa Min - Max thuộc tính tuổi và tỷ lệ Na/K ........................................... 47
Bảng 2.8. Ước tính huyết áp cho bệnh nhân 17 tuổi với tỷ lệ Na/K=12.5 .......................... 50
Bảng 3.1. Danh sách các thuộc tính đầu vào của bài toán ................................................. 56
Bảng 3.2. Danh sách các thông tin đầu ra của bài toán ..................................................... 57
Bảng 3.3. Các độ đo dùng để dự báo................................................................................... 59

Hình 3.1. Mô hình bài toán .................................................................................................. 55
Hình 3.2. Thông tin về tiến trình học tập của sinh viên ....................................................... 55
Hình 3.3. Quá trình phân lớp............................................................................................... 58
Hình 3.4. Tỷ lệ dự báo chính xác theo Cây quyết định (ID3) .............................................. 62
Hình 3.5. Tỷ lệ dự báo chính xác theo Cây quyết định (C4.5)............................................. 63
Hình 3.6. Tỷ lệ dự báo chính xác theo K láng giềng gần nhất ............................................ 64
Hình 3.7. Đánh giá độ chính xác của 3 phương pháp khi dự báo kết quả học vụ ............... 65
Hình 3.8. Đánh giá độ chính xác của 3 phương pháp khi dự báo tiến độ học tập .............. 65


1

MỞ ĐẦU
Tính cấp thiết của đề tài
Mục tiêu chung của các em sinh viên cũng như của các bậc phụ huynh khi
bước chân vào Trường Đại học chính là tấm bằng Đại học. Tuy nhiên, với mô hình
đào tạo theo tín chỉ hiện nay tại hầu hết các trường Đại học nói chung và Đại học
Thủy lợi nói riêng thì việc tìm hiểu, thích nghi với quy chế đào tạo mới là một điều
không hề dễ dàng (trong quá trình học 12 năm phổ thông thì người học được đào
tạo theo niên chế). Trong thực tế, rất nhiều sinh viên vẫn giữ thói quen cũ từ thời
phổ thông (thang điểm, phương thức học tập…) trong quá trình học đại học, từ đó
phát sinh ra những trường hợp đáng tiếc mà do thiếu hiểu biết, các em đã bỏ lỡ mất
cơ hội của mình. Ví dụ như tại Đại học Thủy lợi, có trường hợp sinh viên học đạt
hầu hết các môn (Điểm D tức là từ 4-5.4 điểm theo thang 10 là đạt [1]) nhưng lại
không đủ điều kiện làm Đồ án tốt nghiệp (điều kiện làm Đồ án tốt nghiệp là không
nợ môn và điểm trung bình chung các môn là 2.0 theo thang điểm 4 [3]), từ đó dẫn
đến việc em bị chậm tiến độ học tập…
Để các em sinh viên và phụ huynh phần nào có cái nhìn rõ ràng hơn về tương
lai việc học tập tại Trường Đại học mà không cần phải hiểu sâu về quy chế đào tạo
theo tín chỉ: Đó là khả năng hoàn thành chương trình học như thế nào? Có đảm bảo

dữ liệu điểm các môn học sẽ thi đại học từ 03 năm học phổ thông.
Tuy nhiên, hiện vẫn chưa có nghiên cứu cụ thể nào có thể giải quyết bài toán
thực tế mà đề tài luận văn nhắc đến ở trên. Do đó, tác giả tiến hành thực hiện đề tài
luận văn nghiên cứu về vấn đề khai phá dữ liệu và ứng dụng vào giải quyết bài toán
thực tế là dự đoán tiến trình học tập của sinh viên Đại học Thủy lợi

Mục đích, đối tượng, phạm vi và phương pháp nghiên cứu
Luận văn tiến hành nghiên cứu, tìm hiểu các vấn đề cơ bản về khai phá dữ
liệu, các công cụ học máy. Từ đó ứng dụng vào việc xây dựng mô hình dự báo tiến
trình học tập của sinh viên Đại học Thủy lợi. Qua luận văn này, tác giả mong muốn
có những nghiên cứu lý thuyết về khai phá dữ liệu, các công cụ học máy và các
thuật toán dự báo (Cây quyết định, K láng giềng gần nhất); thực nghiệm, phân tích
được kết quả dự báo tiến trình học tập của sinh viên.
Thông qua phương pháp nghiên cứu lý thuyết và phương pháp nghiên cứu
thực nghiệm, tác giả đã tiếp cận nghiên cứu các văn bản pháp quy và các hướng dẫn


3

thực hiện quy chế đào tạo theo tín chỉ; dữ liệu về chương trình đào tạo tạo, điểm,
kết quả học vụ của sinh viên Đại học Thủy lợi hay các công nghệ liên quan đến khai
phá dữ liệu để tổng hợp thu thập thông tin. Từ đó phân tích được các yêu cầu của
công việc, vận dụng các kết quả lý thuyết vào bộ dữ liệu cụ thể của Trường Đại học
Thủy lợi để đánh giá và phân tích kết quả

Cấu trúc luận văn
Nội dung của luận văn được trình bày trong ba phần chính như sau:
1. Phần mở đầu
2. Phần nội dung: bao gồm ba chương
Chương 1: Tổng quan về Khai phá dữ liệu trong bài toán dự báo

được dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ
và các mẫu chưa biết bên trong dữ liệu”
Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định,
trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong cơ sở dữ
liệu lớn”.
Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm
thường nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu
được”.
Như vậy có thể nói rằng: Khai phá dữ liệu (data mining) là quá trình khám
phá 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 đã
có. Ví dụ: từ các dữ liệu đã có về độ ẩm, nhiệt độ,… người ta có thể đưa ra dự đoán
được được thời tiết của một ngày; hay từ các dữ liệu về huyết áp, tỷ lệ mỡ trong
máu… người ta có thể dự đoán khả năng bị bệnh của một bệnh nhân.

Hình 1.1. Quá trình khám phá, phát hiện tri thức từ dữ liệu [4]


5

Quy trình khám phá tri thức trong cơ sở dữ liệu (KDD) thường tuân theo các
bước như hình 1.1 trên đây:
Bước 1- Gom dữ liệu: là tập hợp dữ liệu từ các nguồn khác nhau. Dữ liệu
được gom lại từ một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các
nguồn ứng dụng Web.
Bước 2 - Trích lọc dữ liệu: dữ liệu được lựa chọn hoặc phân chia theo một số
tiêu chuẩn nào đó phục vụ mục đích khai thác. Ví dụ trong bộ dữ liệu của sinh viên
thì chỉ lọc ra những dữ liệu như: điểm trung bình tích lũy từng học kỳ, điểm trung
bình tích lũy toàn khóa tính đến thời điểm xét, số tín chỉ tích lũy từng học kỳ, số tín
chỉ tích lũy toàn khóa tính đến thời điểm xét, kết quả xử lý học vụ từng kỳ.
Bước 3 - Làm sạch, tiền xử lý dữ liệu: đây là một bước rất quan trọng trong

1.2 Một số phương pháp khai phá dữ liệu
Phân lớp (Classification)
Phân lớp là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong
số các lớp đã được biết trước đó. Mục tiêu của phương pháp phân lớp dữ liệu là dự
đoán nhãn lớp cho các mẫu dữ liệu. Như thế quá trình phân lớp có thể sử dụng mối
quan hệ này để dự báo cho các mục (cá thể, mẫu) mới. Các kiến thức được phát
hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của
một mục thoả mãn điều kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết
luận”[6].
Quá trình phân lớp, hay phân loại dữ liệu thường gồm 2 bước: Xây dựng mô
hình và sử dụng mô hình để phân lớp dữ liệu. Ví dụ: Giả sử có một mục biểu diễn
thông tin về bệnh nhân và có các thuộc tính dự báo là: họ tên, tuổi, giới tính, tỷ lệ
Na/k, chỉ số huyết áp… và thuộc tính phân loại là có bị ung thư hay không.
Các bài toán phân lớp có thể được chia thành hai dạng cơ bản :
a. Phân lớp nhị phân/đa lớp: Phân lớp nhị phân là phân lớp mà giá trị của
thuộc tính cần dự đoán chỉ có 2 giá trị ví dụ Yes/No, còn phân lớp đa lớp là phân
lớp mà giá trị của thuộc tính cần dự đoán có hơn 2 giá trị. Ví dụ như phân loại kết
quả của sinh viên ở trường ĐHTL thì mỗi em có khả năng nhận các giá trị: Xuất
sắc, giỏi, khá, trung bình, yếu kém.


7

b. Phân lớp đơn nhãn/ đa nhãn: Phân lớp đơn nhãn là phân lớp mà mỗi mẫu
cần dự đoán sẽ được gán vào chính xác một lớp. Ví dụ như dự đoán 1 bệnh nhân có
mắc virut H5N1 hay không thì hệ thống chỉ có thể dự đoán là có hoặc không. Trong
trường hợp phân lớp đa nhãn, một mẫu mới có thể được gán vào nhiều hơn một lớp.
Ví dụ như hệ thống dự đoán xem máy tính bị nhiễm những loại virut nào.

Phân cụm (Clustering)

càng lớn. Trong thực tế, có rất nhiều các mô hình dự báo được ứng dụng trong rất
nhiều lĩnh vực thực tế, ví dụ như dự báo khí tượng thủy văn (sử dụng mô hình
GSM, HRM…), dự báo tỷ giá hay chứng khoán (sử dụng mô hình ARIMA), dự báo
về sử dụng điện năng (mô hình mạng nơron…).
Dự báo dữ liệu là một quá trình gồm hai bước, nó gần giống với quá trình
phân lớp. Tuy nhiên để dự đoán, chúng ta bỏ qua khái niệm nhãn phân lớp bởi vì
các giá trị được dự đoán là liên tục (được sắp xếp) hơn là các giá trị phân loại. Ví dụ
thay vì phân loại xem một khoản vay có là an toàn hay rủi ro thì chúng ta sẽ dự
đoán xem tổng số tiền cho vay của một khoản vay là bao nhiêu thì khoản vay đó là
an toàn. Do đó, ta có thể thấy rằng tất cả những đặc điểm của bài toán phân lớp hiện
hữu trực tiếp tại bài toán dự báo

Đặc điểm của bài toán dự báo
Quá trình dự báo thường gồm 2 bước:
Bước 1: Xây dựng mô hình
Trong bước này, một mô hình sẽ được xây dựng dựa trên việc phân tích các
mẫu dữ liệu sẵn có. Đây là quá trình học, trong đó một thuật toán phân lớp được
xây dựng bằng cách phân tích hoặc “học” từ tập dữ liệu huấn luyện được xây dựng
sẵn bao gồm nhiều bộ dữ liệu (xem ví dụ ở Hình 1.2).
Đầu vào của quá trình này 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 đó. Mỗi bộ giá trị
được gọi chung là một mẫu (sample). Trong tập dữ liệu này, mỗi mẫu dữ liệu X
biểu diễn bằng một vector n chiều, X = (x1, x2,…, xn), đây là các giá trị cụ thể của
một tập n thuộc tính của nguồn dữ liệu {A 1, A2, …, An}. Mỗi mẫu được giả sử
thuộc về một lớp định nghĩa trước, lớp ở đây là giá trị của một thuộc tính được chọn
làm thuộc tính gán nhãn lớp hay thuộc tính quyết định.
Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng ifthen (nếu-thì), công thức logic, hay các công cụ phân lớp như mạng nơron, cây
quyết định, SVM…



xác phân lớp có thể dự đoán thói quen mua sắm của các khách hàng tương lai như
thế nào. Độ chính xác đánh giá này sẽ trợ giúp cho việc so sánh các phân lớp khác
nhau.
Có nhiều kỹ thuật để có thể đánh giá độ chính xác của các thuật toán phân
lớp. Trong đó Holdout và K-fold cross validation (đánh giá chéo dựa trên k phần) là
hai kỹ thuật phổ biến để đánh giá độ chính xác phân lớp dựa trên các phân chia lấy
mẫu ngẫu nhiên từ dữ liệu cho trước [8].

Hình 1.4. Đánh giá độ chính xác phân lớp với phương pháp holdout [8]

Trong phương pháp holdout, dữ liệu đã cho được phân chia ngẫu nhiên vào
trong hai tập độc lập: một tập huấn luyện và một tập kiểm định. Thông thường, hai
phần ba dữ liệu được chỉ định là tập huấn luyện và còn lại một phần ba được chỉ
định là tập kiểm định. Tập huấn luyện được dùng để phân lớp, độ chính xác của nó
được đánh giá với tập kiểm định (Hình 1.4). Việc đánh giá này là lạc quan bởi chỉ
một phần dữ liệu ban đầu được dùng để phân lớp. Lấy mẫu con ngẫu nhiên là một
sự thay đổi của phương pháp holdout trong đó phương pháp holdout được lặp lại k
lần. Độ chính xác phân lớp bằng giá trị trung bình của các độ chính xác có được từ
mỗi lần lặp.


11

Trong K-fold, dữ liệu ban đầu được phân chia ngẫu nhiên vào trong k tập con
riêng biệt ("các fold – phần dữ liệu") S1S2,...,Sk, chúng có kích thước xấp xỉ bằng
nhau. Huấn luyện và kiểm định được thực hiện k lần. Trong lần lặp thứ i, tập con Si
đóng vai trò như một tập kiểm định và các tập con còn lại được dùng chung để huấn
luyện phân lớp. Tức là phân lớp của lần lặp đầu tiên được huấn luyện trên các tập
con S2,S3,...,Sk và được kiểm định trên S1; phân lớp của lần lặp thứ 2 được huấn
luyện trên các tập con S1,S3,...,Sk và được kiểm định trên S2, v.v... Độ chính xác phân

lựa chọn các thuộc tính. Nếu các mẫu có cùng một lớp thì nút sẽ trở thành lá, ngược
lại sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm cơ sở để phân
chia các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa chọn, tạo ra các nhánh
tương ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình trên cho tới
khi tạo ra được cây quyết định, tất cả các nút triển khai thành lá và được gán nhãn.
Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau được thỏa mãn:
(1) Tất cả các mẫu thuộc cùng một nút; (2) Không còn một thuộc tính nào để lựa
chọn; (3) Nhánh không chứa mẫu nào.
Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng
nhiều bộ nhớ. Lượng bộ nhớ sử dụng tỷ lệ thuận với kích thước của mẫu dữ liệu
huấn luyện. Một chương trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài
song lại có nhược điểm về tốc độ thực thi. Do vậy, vấn đề tỉa bớt cây quyết định trở
nên quan trọng. Các nút lá không ổn định trong cây quyết định sẽ được tỉa bớt. Kỹ
thuật tỉa trước là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa.

Các phương pháp K-láng giềng gần nhất
Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều
là rất có ích đối với việc phân tích dữ liệu. Với việc dùng các miêu tả này, nội dung
của vùng lân cận được xác định, trong đó các bản ghi gần nhau trong không gian
được xem xét thuộc về lân cận (hàng xóm – láng giềng) của nhau. Khái niệm này


13

được dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần nhất, trong đó K là
số láng giềng được sử dụng. Phương pháp này rất hiệu quả nhưng lại đơn giản. Ý
tưởng thuật toán học K-láng giềng gần là “thực hiện như các láng giềng gần của bạn
đã làm”. Để dự đoán hoạt động của một mẫu xác định, K-láng giềng tốt nhất của
mẫu đó sẽ được xem xét, và trung bình các hoạt động của các láng giềng gần sẽ đưa
ra được dự đoán về hoạt động của mẫu đó.

luật không nhỏ hơn ngưỡng θ cho trước. Từ một cơ sở dữ liệu có thể tìm được hàng
nghìn và thậm chí hàng trăm nghìn các luật kết hợp.
Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất thích
hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giới hạn cơ bản của
phương pháp này là ở chỗ các quan hệ cần phải thưa theo nghĩa không có tập
thường xuyên nào chứa nhiều hơn 15 thuộc tính. Giải thuật tìm kiếm các luật kết
hợp tạo ra số luật ít nhất phải bằng với số các tập phổ biến và nếu như một tập phổ
K

biến có kích thước K thì phải có ít nhất là 2 tập phổ biến. Thông tin về các tập phổ
biến được sử dụng để ước lượng độ tin cậy của các tập luật kết hợp [8].

Các phương pháp Bayes «ngây thơ» và mạng tin cậy Bayes
Phân lớp Bayesian là phân lớp thống kê. Phân lớp Bayesian dựa trên định lý
Bayes. Một phân lớp đơn giản của Bayesian đó là Naive Bayesian, so với việc thực
thi của phân lớp cây quyết định và mạng nơron, phân lớp Bayesian đưa ra độ chính
xác cao và nhanh khi áp dụng vào các cơ sở dữ liệu lớn.
Các phân lớp Naive Bayesian giả định rằng hiệu quả của một giá trị thuộc
tính trên một lớp là độc lập so với giá trị của các thuộc tính khác. Giả định này được
gọi là độc lập có điều kiện lớp. Như vậy sẽ đơn giản hoá các tính toán rắc rối, vì thế
coi nó là "ngây thơ".
Các mạng belief (dựa trên) Bayesian là các mô hình đồ thị, nó không giống
như phân lớp Bayesian ngây thơ, cho phép biểu diễn sự phụ thuộc giữa các tập con
của các thuộc tính. Các mạng belief Bayesian cũng được dùng cho phân loại [8].

1.5 Kết luận chương 1
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 liên tục



KHAI PHÁ DỮ LIỆU VÀ CÁC CÔNG CỤ
HỌC MÁY

2.1 Cây quyết định
Tổng quan về cây quyết định
2.1.1.1 Giới thiệu chung
Cây quyết định (decision tree) là một phương pháp mạnh và thường được sử
dụng cho cả hai nhiệm vụ của khai phá dữ liệu là phân loại và dự báo. Mặt khác,
cây quyết định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng tri
thức với các luật If-Then.
Cây quyết định là cấu trúc biễu diễn dưới dạng cây. Trong đó, mỗi nút trong
(internal node) biễu diễn một thuộc tính, mỗi nhánh (branch) biễu diễn giá trị có thể
có của thuộc tính, mỗi lá (leaf node) biểu diễn các lớp quyết định và đỉnh trên cùng
của cây gọi là nút gốc (root). Cây quyết định có thể được dùng để phân lớp bằng
cách xuất phát từ gốc của cây và di chuyến theo các nhánh cho đến khi gặp nút lá.
Cũng trên cơ sở phân lớp này có thể chuyển đổi về các luật quyết định.
Cây quyết định thường được sử dụng để xây dựng một kế hoạch nhằm đạt
được mục tiêu mong muốn. Các cây quyết định được dùng để hỗ trợ quá trình ra
quyết định. Cây quyết định là một dạng đặc biệt của cấu trúc cây. Tạo cây quyết
định chính là quá trình phân tích cơ sở dữ liệu, phân lớp và đưa ra dự đoán. Cây
quyết định được tạo thành bằng cách lần lượt chia (đệ quy) một tập dữ liệu thành
các tập dữ liệu con, mỗi tập con được tạo thành chủ yếu từ các phần tử của cùng
một lớp. Việc lựa chọn thuộc tính để tạo nhánh của cây được thực hiện thông qua
Entropy và Gain.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai
phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện
cho các phân loại còn các nhánh của cây đại diện cho các kết hợp của các thuộc tính
dẫn tới phân loại đó. Một cây quyết định có thể được học bằng cách chia tập hợp
nguồn thành các tập con dựa theo việc kiểm tra giá trị thuộc tính. Quá trình này