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

TRẦN VĂN HẢI

ỨNG DỤNG THUẬT TOÁN HỌC MÁY SVM
TRONG TƯ VẤN HƯỚNG NGHIỆP CHO
HỌC SINH TRUNG HỌC PHỔ THÔNG

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

HÀ NỘI – 2017


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

TRẦN VĂN HẢI

ỨNG DỤNG THUẬT TOÁN HỌC MÁY SVM
TRONG TƯ VẤN HƯỚNG NGHIỆP CHO
HỌC SINH TRUNG HỌC PHỔ THÔNG

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ:

60.48.01.01

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

Tôi xin cân thành cảm ơn!


iii

MỤC LỤC
LỜI CAM ĐOAN ................................................................................................................... i
LỜI CẢM ƠN ........................................................................................................................ ii
MỤC LỤC ............................................................................................................................iii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ........................................................ v
DANH MỤC CÁC BẢNG ................................................................................................... vi
DANH MỤC HÌNH VẼ, BIỂU ĐỒ .................................................................................... vii
LỜI MỞ ĐẦU ........................................................................................................................ 1
CHƯƠNG 1: TỔNG QUAN VỀ HỌC MÁY VÀ BÀI TOÁN TƯ VẤN HƯỚNG
NGHIỆP CHO HỌC SINH THPT......................................................................................... 3
1.1. Tổng quan về học máy ................................................................................................ 3
1.1.1. Giới thiệu về học máy .......................................................................................... 3
1.1.2. Ứng dụng của học máy ......................................................................................... 4
1.1.3. Phân loại các phương pháp học máy .................................................................... 6
1.2. Tổng quan về phương pháp Support Vector Machine ................................................ 8
1.2.1. Giới thiệu về Support Vector Machine................................................................. 8
1.2.2. SVM tuyến tính và SVM phi tuyến .................................................................... 11
1.2.3. SVM trong phân lớp đa lớp ................................................................................ 23
1.3. Bài toán tư vấn hướng nghiệp cho học sinh trung học phổ thông............................. 26
1.3.1. Giới thiệu về tư vấn hướng nghiệp ..................................................................... 26
1.3.2. Cơ sở lý thuyết tư vấn hướng nghiệp ................................................................. 28
1.3.3. Các kỹ năng và liệu pháp tư vấn hướng nghiệp ................................................. 31
1.3.4. Mô tả bài toán tư vấn hướng nghiệp cho học sinh THPT .................................. 32
1.4. Kết luận chương ........................................................................................................ 33
CHƯƠNG 2: XÂY DỰNG MÔ HÌNH TƯ VẤN HƯỚNG NGHIỆP CHO HỌC SINH


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Viết tắt

Tiếng Anh

Tiếng Việt

SVM

Support Vector Machine

Máy véc-tơ hỗ trợ

SMO

Sequential Minimal Optimization

Tối thiểu tuần tự

DT

Decision Tree

Cây quyết định

kNN

k-Nearest Neighbor


Trung học phổ thông

TVHN

Tư vấn hướng nghiệp


vi

DANH MỤC CÁC BẢNG
Bảng 2.1. Số lượng mẫu các nhóm ngành nghề .................................................................. 39
Bảng 3.1. Số lượng mẫu các nhóm ngành nghề tập dữ liệu 1 (1800 mẫu) .......................... 45
Bảng 3.2. Số lượng mẫu các nhóm ngành nghề tập dữ liệu 2 (3603 mẫu) .......................... 46
Bảng 3.3. Tệp tin dữ liệu huấn luyện và kiểm chứng .......................................................... 46
Bảng 3.4. Kết quả đánh giá theo chiến lược OAO với tập dữ liệu 1 ................................... 48
Bảng 3.5. Kết quả phân lớp theo chiến lược OAO với tập dữ liệu 1 ................................... 48
Bảng 3.6. Kết quả đánh giá theo chiến lược OAR với tập dữ liệu 1 ................................... 49
Bảng 3.7. Kết quả phân lớp theo chiến lược OAR với tập dữ liệu 1 ................................... 49
Bảng 3.8. So sánh giữa hai chiến lược OAO và OAR với tập dữ liệu 1.............................. 49
Bảng 3.9. Kết quả đánh giá theo chiến lược OAO với tập dữ liệu 2 ................................... 51
Bảng 3.10. Kết quả phân lớp theo chiến lược OAO với tập dữ liệu 2 ................................. 51
Bảng 3.11. Kết quả đánh giá theo chiến lược OAR với tập dữ liệu 2 ................................. 52
Bảng 3.12. Kết quả phân lớp theo chiến lược OAR với tập dữ liệu 2 ................................. 52
Bảng 3.13. So sánh giữa hai chiến lược OAO và OAR với tập dữ liệu 2............................ 52


vii

DANH MỤC HÌNH VẼ, BIỂU ĐỒ
Hình 1.1. Mô tả phương pháp SVM ...................................................................................... 9

ngành nghề chủ yếu là theo cảm tính, theo xu thế hoặc do tác động từ gia đình, cha
mẹ, bạn bè, … không xác định được khả năng, năng lực bản thân có phù hợp với
ngành nghề hay không từ đó dẫn tới việc học tập và làm việc không hiệu quả, gây
lãng phí lớn cho bản thân, gia đình và xã hội.
Tư vấn hướng nghiệp là một vấn đề cần phải được quan tâm, nhất là ở cấp bậc
phổ thông. Khi được định hướng đúng đắn về nghề nghiệp, mỗi người sẽ yên tâm với
nghề mình lựa chọn, có thái độ tích cực, chủ động học tập, rèn luyện để có thể hoạt
động tốt lĩnh vực nghề nghiệp trong tương lai. Đối với học sinh ở bậc phổ thông, tư
vấn hướng nghiệp sẽ giúp các em định hướng ngành nghề một cách có cơ sở, có nhận
thức đúng đắn về nghề nghiệp, phát huy được tối đa khả năng của bản thân, khơi dậy
niềm đam mê của các em đối với công việc mình lựa chọn từ đó góp phần ổn định
cuộc sống của bản thân trong tương lai đồng thời đáp ứng được nhu cầu xã hội, tránh
lãng phí trong đào tạo và sử dụng hợp lý nguồn nhân lực, góp phần vào việc phát
triển kinh tế – xã hội của đất nước.
Trong việc chọn nghề, để có thể lựa chọn được một ngành nghề phù hợp ta
phải dựa vào khả năng, năng lực bản thân cũng như sở thích và tính cách của từng
người. Do đó, đối với công tác tư vấn hướng nghiệp cho học sinh trung học phổ thông,
cần phải có một phương pháp phân loại để phân nhóm các em học sinh dựa trên các
yếu tố này, từ đó mới có thể đưa ra sự tư vấn, định hướng nghề nghiệp một cách chính


2

xác cho các em. Nói cách khác, để có thể giải quyết được vấn đề về công tác tư vấn
hướng nghiệp cho học sinh trung học phổ thông ta cần phải giải quyết được bài toán
phân loại học sinh. Đây là bài toán nhằm mục đích phân lớp các em học sinh vào các
nhóm ngành nghề khác nhau dựa trên các đặc trưng về khả năng, năng lực, sở thích
cũng như tính cách của từng em.
Ngày nay, đối với các bài toán phân loại, việc sử dụng các mô hình tính toán
dựa trên các phương pháp học máy ngày càng được áp dụng một cách rộng rãi và đạt

trong tương lai thay vì chỉ thực hiện theo đúng các quy tắc đã được lập trình sẵn.
Chẳng hạn, máy tính có thể học cách dự đoán dựa trên các ví dụ, hay học cách tạo ra
các hành vi phù hợp dựa trên quan sát trong quá khứ [4].
Ví dụ như chương trình có thể dựa vào dữ liệu trong quá khứ để phân loại thư
điện tử xem có phải thư rác (spam) hay không và tự động xếp thư vào thư mục tương
ứng. Thư rác ở đây được hiểu là các thư điện tử có chứa các nội dung quảng cáo hay
các loại hàng miễn phí cho dùng thử được chuẩn bị từ trước và gửi đồng loạt tới nhiều
địa chỉ. Khái niệm “rác” đến từ ý nghĩa là những thư này thường bị loại bỏ hơn là
được sự lưu tâm của người nhận.
Tương tự quá trình học thông thường, một hệ thống học máy cần có khả năng
ghi nhớ, thích nghi và đặc biệt là tổng quát hóa. Tổng quát hóa là khả năng của hệ
thống học máy ra quyết định chính xác trong các trường hợp mới, chưa gặp dựa trên
kinh nghiệm học được từ dữ liệu hoặc các quan sát trước đó.
Một tiến trình học máy gồm 2 giai đoạn:
- Giai đoạn học (giai đoạn huấn luyện): hệ thống phân tích dữ liệu và tìm ra
mối quan hệ (có thể là tuyến tính hoặc phi tuyến) giữa các đối tượng dữ liệu huấn
luyện. Kết quả của việc học có thể là nhóm các đối tượng vào trong các lớp, tạo ra
các luật, dự đoán lớp cho các đối tượng mới.
- Giai đoạn thử nghiệm (giai đoạn dự đoán): mối quan hệ (các luật, các lớp,
…) được tạo ra trong giai đoạn học phải được kiểm nghiệm lại bằng một số hàm tính
toán thực thi trên một phần của tập dữ liệu huấn luyện hoặc trên một tập dữ liệu lớn
hơn.


4

Một số khái niệm được sử dụng trong học máy [4]:
- Mẫu hay ví dụ dùng để chỉ đối tượng cần phân loại. Mẫu thường được mô tả
bằng một tập các thuộc tính còn được gọi là đặc trưng hay biến. Chẳng hạn như trong
bài toán phân loại thư rác, mỗi thư được gọi là một mẫu hay ví dụ, còn thuộc tính là

Dịch tự động
Dịch tự động thực hiện dịch một ngôn ngữ này (gọi là ngôn ngữ nguồn) sang
một hoặc nhiều ngôn ngữ khác (gọi là ngôn ngữ đích) một cách tự động, không có sự
can thiệp của con người trong quá trình dịch. Dữ liệu huấn luyện là các văn bản song
ngữ, hệ thống dịch tự động học cách dịch từ ngôn ngữ này sang ngôn ngữ khác.
Phân loại văn bản tự động
Đầu vào sẽ cho trước một tập huấn luyện bao gồm các văn bản. Mỗi văn bản
có thể thuộc vào một trong các loại văn bản khác nhau. Sau khi huấn luyện xong,
thuật toán phân loại sẽ được nhận văn bản mới và cần xác định nhãn phân loại cho
văn bản này. Ví dụ, với các văn bản là nội dung thư điện tử, thuật toán có thể phân
loại thư thành “thư rác” và “thư bình thường”.
Phát hiện và nhận dạng mặt người
Phát hiện vùng có chứa mặt người trong ảnh, xác định đó là mặt của người nào
trong số những người đã có ảnh trước đó, tức là phân chia ảnh thành những loại tương
ứng với những người khác nhau. Ứng dụng này hiện nay được sử dụng rộng rãi trong
các thiết bị quay phim, chụp ảnh, …
Chuẩn đoán y khoa
Trong lĩnh vực y học, để chuẩn đoán các loại bệnh, người ta thường dựa vào
các triệu chứng của người bệnh. Ứng dụng sẽ học cách dự đoán người bệnh có mắc
hay không mắc một số bệnh nào đó dựa trên các triệu chứng quan sát được.
Các hệ tư vấn, khuyến nghị
Đưa ra các gợi ý về các loại hàng hóa, tin tức, video, … mà người dùng nhiều
khả năng sẽ quan tâm đến. Ví dụ như các khuyến nghị trên Youtube hay trên các trang
mua bán trực tuyến.


6

1.1.3. Phân loại các phương pháp học máy
1.1.3.1. Học có giám sát [4]

gồm các ví dụ tương tự nhau. Hình thức học như vậy được gọi là phân cụm
(clustering). Ví dụ, dựa vào tuổi của mọi người ta học được khái niệm “già” và “trẻ”,
và có thể xếp mọi người vào một trong hai cụm tương ứng.
Ngoài ra, học không giám sát có thể được dùng kết hợp với suy diễn Bayes để
đưa ra xác suất có điều kiện cho bất kỳ biến ngẫu nhiên nào khi biết trước các biến
khác. Ví dụ, qua phân tích dữ liệu mua hàng ở siêu thị, ta có thể dự đoán rằng người
đã mua bánh mỳ thì có nhiều khả năng cũng sẽ mua bơ.
Có rất nhiều thuật toán học không giám sát được ra đời và phát triển nhằm giải
quyết bài toán phâm cụm phục vụ khai thác hiệu quả nguồn dữ liệu chưa gán nhãn.
Việc lựa chọn thuật toán nào tùy thuộc vào dữ liệu và mục đích của từng bài toán.
Một số thuật toán thường được sử dụng như: k-means, Hierarchical Agglomerative
Clustering (HAC), Self-organizing Map (SOM), …

1.1.3.3. Học bán giám sát
Học bán giám sát (semi-supervised learning) là dạng kết hợp giữa học có giám
sát và học không giám sát. Trong đó, nó kết hợp các ví dụ có gán nhãn và không gán
nhãn để sinh ra một hàm hoặc một bộ phân loại thích hợp.
Thuật toán học bán giám sát sử dụng một tập huấn luyện (training set) gồm 2
phần: các ví dụ huấn luyện có nhãn thường có số lượng ít và các ví dụ huấn luyện
không có nhãn thường có số lượng nhiều.
Một thuật toán học bán giám sát được sử dụng sẽ học các ví dụ có nhãn, sau
đó tiến hành gán nhãn cho một số (có lựa chọn) các ví dụ không có nhãn một cách
hợp lý và có đánh giá chất lượng độ chính xác. Tiếp theo, chọn các ví dụ vừa được
gán nhãn có độ tin cậy cao (vượt trên một ngưỡng cho trước) đưa vào kết hợp với tập
dữ liệu có nhãn, tạo thành một tập dữ liệu huấn luyện mới.


8

1.2. Tổng quan về phương pháp Support Vector Machine

SVM sẽ ánh xạ không gian ban đầu của các ví dụ sang một không gian khác thường
là có số chiều cao hơn, sau đó tìm siêu phẳng tốt nhất trong không gian này.
Có thể tìm được nhiều siêu phẳng để phân chia tập dữ liệu huấn luyện ban đầu.
Mục đích của phương pháp SVM là tìm được siêu phẳng sao cho khoảng cách từ siêu
phẳng này tới những ví dụ có nhãn khác nhau là lớn nhất.

Hình 1.1. Mô tả phương pháp SVM
Trong hình vẽ trên, đường tô đậm là siêu phẳng tốt nhất và các điểm được
khoanh tròn là những điểm gần siêu phẳng nhất, chúng được gọi là các véc-tơ hỗ trợ
(support vector). Các đường nét đứt mà các véc-tơ hỗ trợ nằm trên đó được gọi là lề
(margin).
Các véc-tơ hỗ trợ sẽ quyết định hàm phân tách dữ liệu. Từ đây, có thể thấy
phương pháp SVM không hoàn toàn phụ thuộc vào các ví dụ huấn luyện ban đầu mà
chỉ phụ thuộc vào các véc-tơ hỗ trợ. Cho dù các điểm khác bị xóa thì thuật toán vẫn
cho kết quả tương tự. Đây chính là điểm nổi bật của phương pháp SVM so với các
phương pháp khác.


10

1.2.1.2. Cơ sở lý thuyết
Cho tập huấn luyện T = {(x1,y1), (x2,y2), …, (xn,yn)} trong đó xi ϵ Rn là các
véc-tơ đặc trưng và yi ϵ {-1, +1} là nhãn phân loại tương ứng của các xi. Giả sử ta
chọn tập các đặc trưng là D = {d1, d2, …, dn} thì véc-tơ đặc trưng xi = {xi1, xi2, …,
xin} trong đó xij ϵ Rn. Đối với bài toán phân lớp nhị phân, nhãn yi sẽ có hai giá trị -1
hoặc +1.
Ta cần tìm một siêu phẳng có lề lớn nhất phân tách các điểm yi = -1 và yi =
+1. Mỗi siêu phẳng có thể được biểu diễn dưới dạng
𝑓 (𝑥) = 〈𝑤. 𝑥〉 + 𝑏 = 0


⃗⃗ . ⃗⃗⃗
𝑥𝑖 + 𝑏 < 0

(2.3)

Như vậy, yi biểu diễn sự phân lớp của ⃗⃗⃗
𝑥𝑖 vào hai lớp -1 và +1.
Bản chất của phương pháp SVM là tìm ra w và b sao cho siêu phẳng phân tách
dữ liệu huấn luyện 𝑓 (𝑥) = 〈𝑤. 𝑥〉 + 𝑏 có lề lớn nhất.


11

Hình 1.2. Siêu phẳng phân tách với véc-tơ pháp tuyến w

1.2.2. SVM tuyến tính và SVM phi tuyến
1.2.2.1. SVM tuyến tính [12][7]
1.2.2.1.1. SVM tuyến tính với tập dữ liệu phân tách được
Giả sử tập huấn luyện có thể phân tách tuyến tính được mà không có nhiễu (tất
cả các điểm được gán nhãn +1 thuộc về phía dương của siêu phẳng, tất cả các điểm
được gán nhãn -1 thuộc về phía âm của siêu phẳng).
Hai lề của siêu phẳng 𝑓(𝑥) = 〈𝑤. 𝑥〉 + 𝑏 = 0 sẽ là:
- Lề cộng: 〈𝑤. 𝑥〉 + 𝑏 = +1
- Lề trừ: 〈𝑤. 𝑥〉 + 𝑏 = −1
Khi đó, để tính độ rộng của lề, ta cần tính tổng khoảng cách từ 2 lề cộng và lề
trừ đến siêu phẳng 〈𝑤. 𝑥〉 + 𝑏 = 0.


12


𝑑+ =

|〈𝑤. 𝑥1 〉 + 𝑏 − 1| |−1|
1
=
=
‖𝑤‖
‖𝑤‖ ‖𝑤‖

(2.8)

Tương tự, ta có khoảng cách từ x2 đến lề trừ là:
𝑑− =

|〈𝑤. 𝑥2 〉 + 𝑏 + 1|
|1|
1
=
=
‖𝑤‖
‖𝑤‖ ‖𝑤‖

(2.9)

Từ (2.8) và (2.9) ta suy ra độ rộng lề:
𝑚 = 𝑑+ + 𝑑− =

1
1
2

Bài toán này rất khó giải, do đó ta cần chuyển mục tiêu từ ‖𝑤‖ sang ‖𝑤‖2 .
2

Lúc này, bài toán chuyển sang bài toán quy hoạch lồi (hàm mục tiêu lồi, ràng buộc
tuyến tính) và có nghiệm tối ưu tương đương với bài toán ban đầu. Vậy ta cần giải
bài toán:
1
min ‖𝑤‖2
𝑤,𝑏 2
Với ràng buộc 𝑦𝑖 (〈𝑤. 𝑥𝑖 〉 + 𝑏) ≥ 1, ∀𝑖 = 1, 2, … , 𝑛

(2.12)


14

Bài toán cực tiểu hóa có ràng buộc bất đẳng thức như sau:
Cực tiểu hóa f(x) với điều kiện g(x) ≤ 0. Điều kiện để x0 là một lời giải
𝜕
(𝑓 (𝑥) + 𝛼𝑔(𝑥))|
{𝜕𝑥
𝑥 = 𝑥0 = 0
𝑔 (𝑥 ) ≤ 0

(2.13)

Với α là hệ số nhân Lagrange.
Trong trường hợp có nhiều ràng buộc bất đẳng thức thì cần phải có hệ số nhân
Lagrange cho mỗi ràng buộc:
𝑛


Với αi ≥ 0 là các hệ số nhân Lagrange
Lời giải tối ưu cho (2.16) phải thỏa mãn các điều kiện nhất định gọi là các điều
kiện Karush-Kuhn-Tucker (KKT). Tập điều kiện KKT gồm:
𝜕L𝑃
=0
𝜕𝑤
𝜕L𝑃
=0
𝜕𝑏


15

𝑦𝑖 (〈𝑤. 𝑥𝑖 〉 + 𝑏) − 1 ≥ 0,
𝛼𝑖 ≥ 0,

∀𝑖 = 1, 2, … , 𝑛

∀𝑖 = 1, 2, … , 𝑛

𝛼𝑖 [𝑦𝑖 (〈𝑤. 𝑥𝑖 〉 + 𝑏) − 1] = 0,

∀𝑖 = 1, 2, … , 𝑛

Phương pháp Lagrange giải quyết bài toán tối ưu hàm lồi dẫn đến một biểu
thức đối ngẫu của bài toán tối ưu dễ giải quyết hơn so với biểu thức cần tối ưu ban
đầu.
Để tìm được biểu thức đối ngẫu từ biểu thức ban đầu, ta tính đạo hàm bộ phận
của biểu thức Lagrange với các biến ban đầu (w và b) và gán bằng 0, sau đó áp dụng

𝑖=1

Thay vào biểu thức Lagrange ban đầu, ta có biểu thức đối ngẫu Lagrange là:
𝑛

𝑛

𝑖=1

𝑖,𝑗=1

1
𝐿𝐷 = ∑ 𝛼𝑖 − ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 〈𝑥𝑖 𝑥𝑗 〉
2

(2.17)

Cả hai biểu thức LP và LD đều là biểu thức Lagrange dựa trên cùng một hàm
mục tiêu nhưng với các ràng buộc khác nhau. Lời giải tìm được bằng cách cực tiểu
hóa LP hoặc cực đại hóa LD.
Từ (2.17), ta có bài toán đối ngẫu Lagrange:


16

𝑛

𝑛

𝑖=1

trên một trong hai lề cộng hoặc trừ. Khi đó xi được gọi là véc-tơ hỗ trợ.
Trường hợp này, ta có thể tính được: 𝑏 = 𝑦𝑖 − 𝑤. 𝑥𝑖
Gọi SV là tập các véc-tơ hỗ trợ, NSV là số véc-tơ hỗ trợ, khi đó b được tính
bằng công thức:
𝑁𝑆𝑉

1
∑(𝑦𝑖 − 𝑤. 𝑥𝑖 )
𝑏=
𝑁𝑆𝑉

(2.19)

𝑖=1

Sử dụng các điều kiện KKT ta tính được w và b, từ đó suy ra công thức siêu
phẳng quyết định ranh giới phân lớp:
𝑓 (𝑥) = 〈𝑤. 𝑥〉 + 𝑏 = ∑ 𝛼𝑖 . 𝑦𝑖 〈𝑥𝑖 . 𝑥〉 + 𝑏 = 0

(2.20)

𝑥𝑖 𝑆𝑉

Đối với một ví dụ cần phân lớp chúng ta chỉ cần tính giá trị:
𝑠𝑖𝑔𝑛(〈𝑤. 𝑥〉 + 𝑏) = 𝑠𝑖𝑔𝑛( ∑ 𝛼𝑖 . 𝑦𝑖 〈𝑥𝑖 . 𝑥〉 + 𝑏)
𝑥𝑖 𝑆𝑉

(2.21)