TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
VIỆN CÔNG NGHỆ THÔNG TIN

TRẦN THỊ THÙY LINH

TÌM HIỂU VỀ KHAI PHÁ DỮ LIỆU
BẰNG CÂY QUYẾT ĐỊNH VÀ ỨNG
DỤNG HƯỚNG NGHIỆP
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Sư phạm Tin học
Người hướng dẫn khoa học

ThS. Đỗ Thị Lan Anh

HÀ NỘI, 2019


LỜI CẢM ƠN
Em xin chân thành cảm ơn cô giáo ThS. Đỗ Thị Lan Anh, giảng viên
Viện Công nghệ thông tin, trường Đại học Sư phạm Hà Nội 2, người đã trực
tiếp hướng dẫn em trong suốt thời gian qua để em có thể hoàn thành khóa
luận này.
Em xin gửi lời cảm ơn tới các thầy, cô giáo trong Viện Công nghệ
thông tin, các bạn lớp K41 – Sư Phạm tin học đã tạo điều kiện, động viên
khích lệ em trong suốt quá trình học tập và nghiên cứu.
Do thời gian nghiên cứu còn hạn chế nên những vấn đề mà em trình bày
trong khóa luận sẽ không tránh khỏi những thiếu xót. Em kính mong nhận
được những ý kiến đóng góp từ thầy cô và các bạn để bài khóa luận của em
được hoàn thiện hơn.
Em xin trân thành cảm ơn!
Hà Nội, ngày tháng 5 năm 2019

Hình 3.6: Lưu trữ thông tin ......................................................................... 41


DANH MỤC CÁC BẢNG
Bảng 2.1. Tập dữ liệu huấn luyện quyết định đi Picnic............................... 11
Bảng 2.2. Thống kê mối quan hệ mức độ thực phẩm cần cung cấp và độ
tuổi................................................................................................................... 29
Bảng 2.3. Minh họa tìm ngưỡng ................................................................... 33


MỤC LỤC
LỜI CẢM ƠN
LỜI CAM ĐOAN
MỞ ĐẦU .......................................................................................................... 1
1. Lý do chọn đề tài ......................................................................................... 1
2. Mục đích và nhiệm vụ nghiên cứu............................................................. 1
3. Phương pháp nghiên cứu............................................................................ 1
4. Nội dung chính của đề tài ........................................................................... 2
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU............................. 3
1.1. Khái niệm .................................................................................................. 3
1.2. Các bước khai phá dữ liệu....................................................................... 3
1.2.1. Tìm hiểu bài toán ................................................................................... 3
1.2.2. Thu thập và xử lý dữ liệu....................................................................... 3
1.2.3. Khai phá dữ liệu và lựa chọn giải thuật phù hợp ................................ 3
1.2.4. Phân tích đánh giá ................................................................................. 3
1.2.5. Sử dụng kết quả...................................................................................... 3
1.3. Một số kỹ thuật khai phá dữ liệu............................................................ 4
1.3.1. Phân lớp dữ liệu ..................................................................................... 4
1.3.2. Phân cụm dữ liệu ................................................................................... 5
1.3.3. Sử dụng luật kết hợp............................................................................. 6

cho đến công nghệ và đặc biệt lĩnh vực công nghệ thông tin có những bước phát
triển chóng mặt. Cùng với sự phát triển thì lượng dữ liệu thu thập được ngày
càng nhiều, lượng thông tin được lưu trữ trên các thiết bị ngày càng tăng lên.
Để tìm ra những thông tin hữu ích trong lượng dữ liệu khổng lồ ngày càng khó.
Chính vì vậy mà hiện nay đã phát triển một kỹ thuật mới nhằm tìm ra những
thông tin hữu ích đó chính là khai phá dữ liệu.
Nghề nghiệp là một vấn đề quan trọng đối với mỗi con người, có rất nhiều
các bạn đang rất băn khoăn về việc lựa chọn nghề nghiệp cho bản thân mình,
đặc biệt đối với những học sinh lớp 12. Do vậy việc hướng nghiệp cho học sinh
trung học phổ thông là hết sức cần thiết.
Trước những thực tế đó, tôi chọn đề tài: “Tìm hiểu về khai phá dữ liệu
bằng cây quyết định và ứng dụng hướng nghiệp” cho khóa luận tốt nghiệp
của mình.
2. Mục đích và nhiệm vụ nghiên cứu
- Mục đích: Từ việc nghiên cứu phương pháp khai phá dữ liệu bằng cây
quyết định để xây dựng mô hình phân tích kết quả học tập và đưa ra tư vấn nghề
nghiệp cho học sinh.
- Nhiệm vụ nghiên cứu:
+ Tìm hiểu các kỹ thuật về khai phá dữ liệu, các thuật toán được áp dụng
cho từng kỹ thuật.
+ Áp dụng thuật toán cơ bản trong cây quyết định để phân tích kết quả
học tập của học sinh.
3. Phương pháp nghiên cứu
- Phương pháp nghiên cứu lí thuyết:
Tìm hiểu và lựa chọn phương pháp khai phá dữ liệu cho phù hợp.
- Phương pháp nghiên cứu thu thập thông tin, phân tích số liệu:
1


Thu thập thống kê số liệu từ khảo sát sinh viên, phân tích các dữ liệu,

những kết quả không mong muốn trong khai phá dữ liệu.
1.2.3 Khai phá dữ liệu và lựa chọn giải thuật phù hợp
Sau khi dữ liệu được thu thập, xử lý sẽ bắt đầu lựa chọn phương pháp khai
phá phù hợp với dữ liệu có được.
1.2.4 Phân tích đánh giá
Dựa trên một số tiêu chí tiến hành kiểm tra và chọn lọc nguồn tri thức thu
được.
1.2.5 Sử dụng kết quả
Sau quá trình chắt lọc, tìm kiếm tri thức tìm ra được đem vảo sử dụng.
Các kết quả của quá trình phát hiện tri thức có thể được đưa và ứng dụng trong
các lĩnh vực khác nhau.


1.3 Một số kỹ thuật khai phá dữ liệu
1.3.1. Phân lớp dữ liệu
Mục đích của phân lớp là dự đoán các nhãn phân lớp cho các bộ dữ liệu
mới. Kỹ thuật phân lớp bao gồm hai bước: Xây dựng mô hình và sử dụng mô
hình.
- Xây dựng mô hình: Là mô tả một tập những lớp được định nghĩa trước
trong đó: Mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước
như là được xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ được sử
dụng trong việc sử dụng mô hình được gọi là tập huấn luyện. Mô hình được biểu
diễn là những luật phân lớp, cây quyết định và những công thức toán học.
- Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích phân lớp
dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến. Trước
khi sử dụng mô hình người ta thường phải đánh giá tính chính xát của mô hình
trong đó: Nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp
của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiêm tra mà phân loại
đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện. [2]
* Một số thuật toán về phân lớp dữ liệu:

+ P(X/H) là hậu xác suất của X xác định điều kiện trên H.
+ P(X) là tiền xác suất của X.
1.3.2 Phân cụm dữ liệu
Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các
cụm dữ liệu sao cho các đối tượng trong cùng một cụm là tương đồng. Trong
quá trình phân cụm dữ liệu thì vấn đề trở ngại lớn nhất đó là nhiễu. Nhiễu xuất
hiện trong quá trình thu thập thông tin chưa chính xác. Vì vậy phải khử nhiễu
trong quá trình phân cụm dữ liệu.
* Các vấn đề con cơ bản của phân cụm dữ liệu cần giải quyết đó là:
- Biểu diễn dữ liệu.
- Xây dựng hàm tính độ tương tự.
- Xây dựng các tiêu chuẩn phân cụm.
- Xây dựng mô hình cho cấu trúc cụm dữ liệu.
- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo.
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm.
* Một số kiểu dữ liệu trong phân cụm:
- Phân loại dựa trên kích thước miền:
Cách phân loại này phân biệt các đối tượng dữ liệu dựa trên lích thước
miền của đối tượng đó, hay là các giá trị khác nhau của vùng đó. Giả sử cơ sở dữ
liệu X và k đối tượng. Nếu a, b, c là 3 đối tượng của X thì chúng sẽ có dạng:
a = (a1, a2, a3, ..., ay), b = (b1, b2, b3,..., by), c = (c1, c2, c3,..., cy)
Với y là số chiều và ai, bi, ci với 1 ≤ i ≤ y là các thuộc tính tương ứng của
các đối tượng.
5


Các loại dữ liệu dựa trên kích thước miền:
+ Thuộc tính liên tục: Miền giá trị của các thuộc tính này là các miền liên
tục. Ví dụ như âm thanh, nhiệt độ.
+ Thuộc tính rời rạc: Miền giá trị của thuộc tính này là các miền các giá trị

để đạt kết quả tốt nhất.
Ví dụ ta có luật: Những người mua dầu ăn, muối, bột ngọt, nước mắm =>
Đây là những bà mẹ nội trợ. Hay những người mua muối sẽ mua bột ngọt, dầu
ăn, ta sẽ quan tâm đến nhu cầu mua hàng của đối tượng khách hàng này để đưa
ra luật hỗ trợ phù hợp.
* Một số thuật toán cơ bản trong khai phá dữ liệu
- Thuật toán APPIORI
- Thuật toán FB – Growwth
- Thuật toán AIS
- Thuật toán STEAM
1.3.4 Sử dụng cây quyết định
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 tương ứng với một biến. Đường nối giữa nó với nút con của nó thể hiện
giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục
tiêu. Đỉnh trên cùng gọi là gốc.
Cây quyết định đượ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ây quyết định nhằm hỗ trợ quá trình ra quyết định.

7


CHƯƠNG 2: CÁC PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU
BẰNG CÂY QUYẾT ĐỊNH
2.1 Kỹ thuật khai phá dữ liệu sử dụng cây quyết định
2.1.1 Các kiểu cây quyết định
Có hai kiểu cây quyết định:
- Cây hồi quy: Ước lượng các hàm có giá trị là số thực thay vì sử dụng
cho các nhiệm vụ phân loại.
- Cây phân loại: Nếu x có các nhiệm vụ phân loại như: Thời tiết (nắng hay
mưa), kết quả (thắng hay thua).

tập thuộc tính đó. Sau đó mới có thể chọn được thuộc tính phát triển và tương
ứng là một phân chia tốt nhất.
2.1.3 Xây dựng cây quyết định
Để xây dựng cây quyết định có thể thực hiện bằng thuật toán nhất đinh
nào đó, nhưng quá trình xây dựng cây gồm 3 giai đoạn:
- Giai đoạn 1: Tạo dựng cây
Giai đoạn này phát triển bắt đầu từ gốc, đến từng nhánh và phát triển quy
nạp theo cách thức chia để trị để đến khi đạt được cây quyết định với tất cả các
lá được gán nhãn lớp.
- Giai đoạn 2: Cắt tỉa cây
Đây là công việc để tối ưu hóa cây, khái quát hóa để tăng độ chính xác
của cây bằng cách loại bỏ sự phụ thuộc vào mức độ nhiễu.
- Giai đoạn 3: Đánh giá cây
Dùng để đánh giá độ chính xác của cây kết quả. Tiêu chí đánh giá là tổng
số mẫu được phân lớp chính xác trên tổng số mẫu đưa vào.
2.2. Các thuật toán sử dụng cây quyết định
2.2.1 Thuật toán CLS
Thuật toán CLS được Hoveland và Hint giới thiệu lần đầu tiên vào những
năm 50 của thế kỷ XX. Thuật toán này được thiết kế theo chiến lược chia để trị
từ trên xuống.
CLS là một thuật toán được phát minh ra sớm nhất so với các thuật toán
khác. Nó được đem ra áp dụng cho các cơ sở dữ liệu chứa ít thuộc tính, giá trị
các
9


thuộc tính được phân loại hay rời rạc. Cùng với một tập dữ liệu đầu vào, thuật
toán có thể cho các kết quả khác nhau. Do thuật toán này chưa có tiêu chí để lựa
chọn thuộc tính trong quá trình xây dựng. Thuật toán CLS khá đơn giản, dễ cài
đặt phù hợp giải quyết trong các nhiệm vụ đơn giản.

Đi Picnic

N1

Áo dài

Quần Jean

Bốt

Bus

Không

N2

Áo dài

Quần Jean

Bốt

Xe máy

Không

N3

Áo phông



Bus

Có

N6

Áo sơ mi

Quần ngố

Thể thao

Xe máy

Không

N7

Áo phông

Quần ngố

Thể thao

Xe máy

Có

N8


Bus

Có

N11

Áo dài

Quần vải

Thể thao

Xe máy

Có

N12

Áo dài

Quần vải

Bốt

Xe máy

Có

N13

Chọn thuộc tính Áo = {Áo sơ mi, Áo phông, Áo dài} ta có cây như sau:
Áo
[N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14]
Áo dài
[N1, N2, N8, N9, N11]

Áo phông
[N3, N7, N12, N13]

Áo sơ mi
[N4, N5, N6, N10, N14]

Hình 2.1: Cây quyết định được xây dựng theo thuật toán CLS
Với giá trị thuộc tính Áo = ”Áo dài “ các giá trị thuộc tính Đi Picnic của
{N3, N7, N12, N13} đều có giá trị là có, chúng thuộc cùng lớp “có”. Đây là nút
lá có nhãn là “có”.

11


Tiếp theo chọn thuộc tính Giầy = {bốt, thể thao} để mở rộng cho nhánh bên trái
của cây, chúng ta được cây như hình 2.2 như sau:
Áo
[N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14]
Áo dài

Áo phông
[N3, N7, N12, N13]

Giầy


[N1, N2, N8, N9, N11]
Bốt

Có

Giầy thể thao

Không

Áo sơ mi

Có

Phương tiện
[N4, N5, N6, N10, N14]
Xe máy Xe bus
Không

Có

Hình 2.3: Mở rộng nhánh bên phải cây quyết định
Hình 2.3 là kết quả thu được khi áp dụng thuật toán CLS cho tập dữ liệu
huấn luyện trong bảng 2.1 với thứ tự các thuộc tính áo, giầy, phương tiện. Nếu
áp dụng thuật toán CLS với thứ tự khác của thuộc tính ta sẽ thu được cây kết
quả có hình dạng khác.
2.2.2 Thuật toán ID3
Thuật toán ID3 được công bố bởi Quainlan vào cuối thập niên 70 của thế
kỷ XX. Sau đó, thuật toán ID3 được giới thiệu và trình bày trong mục Induction
on decision tree, machine learning năm 1986. ID3 là một thuật toán đơn giản

luyện khác.
Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân
loại đúng tất cả các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây quyết
định khác nhau tùy thuộc vào thứ tự các kiểm tra trên thuộc tính.
* Hàm xây dựng cây quyết định ID3 từ trên xuống
ID3 xây dựng cây quyết định theo cách từ trên xuống. Lưu ý rằng với bất
kỳ thuộc tính nào chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện


thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng có một
giá trị


chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của
cây và dùng trắc nghiệm này để phân vùng tập hợp các ví dụ. Thuật toán khi đó
xây dựng theo cách đệ quy một cây con cho từng phân vùng. Việc này tiếp tục
cho đến khi mọi thành viên của phân vùng đều nằm trong cùng một lớp, nút đó
trở thành nút lá của cây.
Vì thứ tự trắc nghiệm của các trắc nghiệm là rất quan trọng đối với xây
dựng một cây quyết định đơn giản. ID3 phụ thuộc rất nhiều vào tiêu chuẩn chọn
lựa trắc nghiệm để làm gốc của cây.
* Giải thuật xây dựng thuật toán ID3
Tên hàm: Genrate_decision_tree
Input: Tập dữ liệu học S có chứa các mẫu, tập thuộc tính A.
Output: Cây quyết định T
Hàm Genrate_decision_tree được mô tả dưới dạng giải mã:
Function Genrate_decision_tree (S, A)
Begin
If mọi mẫu trong tập S đều nằm trong một lớp then
Return một nút lá được gán nhãn bởi lớp đó

- Không còn thuộc tính nào => Nghĩa là dữ liệu bị nhiễu, khi đó giải thuật
phải sử dụng một luật nào đó để xử lý, chẳng hạn như luật đa số (lớp nào có
nhiều ví dụ hơn sẽ được dùng để gán nhãn cho nút lá trở về).
- Để hiểu hơn về thuật toán ID3, ta xét ví dụ được cho trong bảng 2.1 với
tập dữ liệu S. Tập S gồm 14 mẫu dữ liệu, thuộc tính Ngày là thuộc tính định
danh. Các thuộc tính ứng viên, thuộc tính đi Picnic là thuộc tính phân lớp. Ta có:
S gồm
14 mẫu [9+, 5-].
* Thuộc tính phân loại tốt nhất:
- Hàm Entropy:
Hàm entropy dùng để đo tính thuần nhất của một tập dữ liệu. Khái niệm
emtropy của một tập S được định nghĩa trong lý thuyết thông tin là số lượng
mong đợi các bit cần biết để mã hóa thông tin về lớp của một thành viên rút ra