Luận văn Hệ thống nhận diện khuôn mặt qua camera

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

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

NGUYỄN QUANG HUY

HỆ THỐNG NHẬN DIỆN KHUÔN MẶT QUA CAMERA

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

(Theo định hướng ứng dụng)

HÀ NỘI - 2020

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

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

NGUYỄN QUANG HUY

HỆ THỐNG NHẬN DIỆN KHUÔN MẶT QUA CAMERA

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

MÃ SỐ: 8.48.01.01

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

(Theo định hướng ứng dụng)

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN ĐÌNH HÓA

HÀ NỘI - 2020

i

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này là công trình nghiên cứu của cá nhân tôi, được

thực hiện trên cơ sở nghiên cứu lý thuyết, thực tế dưới sự hướng dẫn của TS. Nguyễn

Đình Hóa.

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.

Hà Nội, ngày 16 tháng 11 năm 2020

Học Viên Thực Hiện

Nguyễn Quang Huy

ii

LỜI CẢM ƠN

Em xin chân thành cảm ơn TS. Nguyễn Đình Hóa đã tận tình chỉ dạy và hướng

dẫn cho em trong việc lựa chọn đề tài, thực hiện đề tài và viết báo cáo luận văn, giúp

em hoàn thành tốt luận văn này.

Em xin cám ơn các thầy cô giáo trường Học viện Công nghệ Bưu chính Viễn

thông đã tận tình dạy dỗ và chỉ bảo em trong suốt 2 năm học.

Cuối cùng em xin cám ơn gia đình, bạn bè, đồng nghiệp, những người đã luôn

bên cạnh động viên em những lúc khó khăn và giúp đỡ em trong suốt thời gian học

tập và làm luận văn, tạo mọi điều kiện tốt nhất cho em để có thể hoàn thành tốt luận

văn của mình.

Mặc dù đã cố gắng hoàn thành nghiên cứu trong phạm vi và khả năng cho

phép nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. Em kính mong nhận được

sự góp ý, thông cảm của thầy cô và các bạn. Em xin chân thành cảm ơn!

Hà Nội, ngày 12 tháng 11 năm 2020

Sinh viên

NGUYỄN QUANG HUY

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.................................................................................... vi

DANH M Ụ C CÁC B Ả NG....................................................................................... vii

DANH M Ụ C CÁC HÌN H ....................................................................................... viii

M Ở ĐẦ U.....................................................................................................................1

CHƯƠNG 1. TỔ NG QUAN V Ề NH Ậ N DI Ệ N KHUÔN M Ặ T................................3

1.1 T ổ ng quan v ề nh ậ n di ệ n khuôn m ặ t cùng v ớ i các ứ ng d ụ ng th ự c t ế c ủ a các k ỹ

thu ậ t nh ậ n d ạ ng khuôn m ặ t......................................................................................3

1.1.1 T ổ ng quan....................................................................................................3

1.1.2 Ki ế n trúc t ổ ng quát h ệ th ố ng nh ậ n di ệ n ......................................................3

1.1.3 Ứ ng d ụ n g .....................................................................................................3

1.2 M ộ t s ố phương pháp trong nh ậ n di ệ n khuôn m ặt thường đượ c áp d ụ ng trong

th ự c t ế và nghiên c ứ u...............................................................................................4

1.2.1 Phân tích thành ph ầ n chính (PCA).............................................................4

1.2.2 Phân tích s ự khác bi ệ t tuy ế n tính(LDA) ....................................................6

1.2.3 Cây quy ết đị nh (Decision Tree) .................................................................8

1.2.4 M ạng nơ -ron nhân t ạ o ..............................................................................15

1.2.5 M ạng nơ -ron tích ch ậ p .............................................................................21

1.3 Phương pháp xác đị nh v ị trí khuôn m ặ t v ớ i m ạ ng tích ch ậ p MTCNN ...........27

1.3.1 Gi ớ i thi ệ u..................................................................................................27

1.3.2 C ấ u trúc m ạ ng P-Ne t ................................................................................27

1.3.3 C ấ u trúc m ạ ng R-Net ...............................................................................28

1.3.4 C ấ u trúc m ạ ng O-Net ...............................................................................30

iv

1.3.5 Đánh giá ...................................................................................................31

1.4 K ế t lu ậ n............................................................................................................31

CHƯƠNG 2. HỆ TH Ố NG NH Ậ N DI Ệ N KHUÔN M Ặ T D Ự A TRÊN M ẠNG NƠ

RON TÍCH CH Ậ P ....................................................................................................32

2.1 Sơ đồ thi ế t k ế h ệ th ố ng nh ậ n di ệ n khuôn m ặ t .................................................32

2.2 M ạ ng Inception-ResNet s ử d ụ ng cho vi ệ c trích ch ọn đặc trưng khuôn mặ t ...33

2.2.1 Gi ớ i thi ệ u..................................................................................................33

2.2.2 M ạ ng GoogleNe t ......................................................................................34

2.2.3 M ạ ng ResNet............................................................................................36

2.2.4 M ạ ng Inception-ResNet ...........................................................................40

2.3 R ừ ng ng ẫ u nhiê n ..............................................................................................47

2.3.1 Gi ớ i thi ệ u..................................................................................................47

2.3.2 Ki ế n trú c ...................................................................................................47

2.3.3 Quá trình bootstrapping............................................................................48

2.3.4 Quá trình attribute sampling.....................................................................48

2.3.5 K ế t qu ả d ự đoán .......................................................................................49

2.3.6 Tham s ố c ủ a Random Forest....................................................................49

2.3.7 S ử d ụng random forest để phân lo ại, đị nh danh cho khuôn m ặ t..............49

2.4 K ế t lu ậ n............................................................................................................50

CHƯƠNG 3. THỬ NGHI ỆM VÀ ĐÁNH GIÁ .......................................................51

3.1 B ộ d ữ li ệu đầ u vào ...........................................................................................51

3.2 Quá trình hu ấ n luy ệ n .......................................................................................51

3.3 Th ử nghi ệ m ch ạ y h ệ th ố ng nh ậ n di ệ n khuôn m ặ t nh ậ n di ệ n khách hàng VIP c ủ a

khách s ạ n................................................................................................................53

3.4 Đánh gi á ...........................................................................................................55

3.5 K ế t lu ậ n............................................................................................................58

v

K Ế T LU Ậ N ...............................................................................................................59

DANH M Ụ C CÁC TÀI LI Ệ U THAM KH Ả O.........................................................60

vi

DANH MỤC TỪ VIẾT TẮT

Tên viết tắt

DT

Tiếng Anh

Tiếng Việt

Cây quyết định

Thuật toán ID3

Decision Tree

ID3

RF

Iterative Dichotomiser 3

Random Forest

Rừng ngẫu nhiên

MLP

Multi layer perceptron

Mạng nơ-ron truyền thẳng nhiều

lớp

CNN

PCA

LDA

MLP

Convolutional Neural Network Mạng nơ-ron tích chập

Principal Components Analysis Phân tích thành phần chính

Linear Discriminant Analysis

Multilayer perceptron

Phân tích sự khác biệt tuyến tính

Mạng nơron truyền thẳng nhiều

lớp

ANN

Artificial Neural network

Mạng nơron nhân tạo

vii

DANH MỤC CÁC BẢNG

B ả ng 1.1. Các hàm kích ho ạ t ....................................................................................16

B ả ng 2.1. B ảng đánh giá độ chính xác gi ữ a các mô hìn h .........................................56

viii

DANH MỤC CÁC HÌNH

Hình 1.1. Ki ế n trúc t ổ ng quát v ề h ệ th ố ng nh ậ n di ệ n .................................................3

Hình 1.2. Thành ph ầ n cây quy ết đị nh .........................................................................9

Hình 1.3. Đồ th ị hàm entropy....................................................................................10

Hình 1.4. C ấ u t ạ o c ủ a Perceptron s ............................................................................15

Hình 1.5. C ấ u trúc c ủa nơ -ron nhân t ạ o ....................................................................16

Hình 1.6. C ấ u t ạ o c ủ a m ạ ng truy ề n th ẳ ng.................................................................19

Hình 1.7. C ấ u t ạ o c ủ a m ạ ng MLP.............................................................................19

Hình 1.8. Ki ế n trúc m ạ ng CNN ................................................................................22

Hình 1.9. Ví d ụ v ề l ớ p g ộ p c ực đạ i ...........................................................................23

Hình 1.10. Đồ th ị hàm f(θ) củ a thu ậ t toán Gradient Descent ...................................24

Hình 1.11. M ố i liên h ệ gi ữ a t ốc độ hu ấ n luy ệ n và hàm 퐽(휃) trong thu ậ t toán

Momentum ................................................................................................................24

Hình 1.12. Ki ế n trúc m ạ ng P-Net..............................................................................28

Hình 1.13. Ki ế n trúc m ạ ng R-Ne t .............................................................................29

Hình 1.14. Ki ế n trúc m ạ ng O-Ne t .............................................................................30

Hình 2.1. Sơ đồ ho ạt độ ng c ủ a h ệ th ố ng nh ậ n di ệ n khuôn m ặ t ................................32

Hình 2.2. Hình 2.1 Kh ố i Inception............................................................................34

Hình 2.3. Ki ế n trúc m ạ ng GoogletNet ......................................................................35

Hình 2.4. Ki ế n trúc m ạng nơ -ro n ..............................................................................37

Hình 2.5. Ki ế n trúc kh ố i ph ần dư ..............................................................................38

Hình 2.6. Ki ế n trúc m ạ ng Resne t ..............................................................................39

Hình 2.7. Ki ế n trúc m ạ ng Inception-ResNet.............................................................41

Hình 2.8. Kh ố i STEM ...............................................................................................42

Hình 2.9. Kh ố i Inception-A ......................................................................................43

Hình 2.10. Kh ố i Inception-B.....................................................................................44

Hình 2.11. Kh ố i Inception-C.....................................................................................45

Hình 2.12. Kh ố i Reduction A ...................................................................................46

Hình 2.13. Kh ố i Reduction B....................................................................................46

1

MỞ ĐẦU

Công nghệ thông tin ngày càng phát triển và đã là một thành phần không thể

thiếu trong hầu hết mọi lĩnh vực trên thế giới. Những người máy thông minh được

con người tạo ra đã có khả năng phân tích và xử lý được các công việc của con người

một cách tự động và đem lại lợi ích kinh tế rất lớn. Trong thời gian gần đây, một trong

những bài toán được nghiên cứu, ứng dụng nhiều nhất vào trong cuộc sống đó là bài

toán nhận diện. Tuy mới xuất hiện chưa lâu nhưng nó đã rất được quan tâm vì tính

ứng dụng thực tế của bài toán như nhận dạng chữ viết, nhận dạng giọng nói, nhận

dạng hình dáng, nhận diện khuôn mặt. Trong đó, bài toán nhận diện khuôn mặt là một

chủ đề đang được khá nhiều nhà đầu tư, doanh nghiệp quan tâm đến. Dù đã được

nghiên cứu từ rất lâu nhưng bài toán nhận diện khuôn mặt vẫn đang gặp phải nhiều

thách thức và vẫn chưa có phương pháp cụ thể nào có thể giải quyết hết các vấn đề

trong bài toán này.

Bài toán nhận diện khuôn mặt là một trong những chủ đề đang được quan tâm

nhiều nhất. Ứng dụng từ bài toán này được áp dụng trong rất nhiều lĩnh vực khác

nhau. Các ứng dụng liên quan đến nhận diện khuôn mặt có thể kể như: tra cứu thông

tin tội phạm, phát hiện tội phạm tại các nơi công cộng, tìm người lạc, điểm danh học

sinh ...

Từ những phân tích và khảo sát ở trên, em nhận thấy hệ thống nhận diện khuôn

mặt rất có ý nghĩa trong thực tiễn cuộc sống và em xin chọn đề tài nghiên cứu “Hệ

thống nhận diện khuôn mặt qua camera”. Kết quả của luận văn hướng tới việc xây

một hệ thống nhận diện khuôn mặt có khả năng mở khả năng mở rộng cao, dễ dàng

tích hợp.

Nội dung luận văn được trình bày trong ba chương với các nội dung chính

như sau:

Chương 1. Tổng quan về nhận diện khuôn

Chương này sẽ trình bày một số nội dung nền tảng về bài toán nhận diện khuôn

mặt, các ứng dụng tương tác người máy liên quan đến nhận diện khuôn mặt, và một

số kỹ thuật hay được sử dụng trong bài toán nhận diện khuôn mặt. Nội dung của

2

chương bao gồm ba phần chính. Phần đầu tiên giới thiệu tổng quan về bài toán nhận

diện khuôn mặt cùng với các ứng dụng thực tế. Phần thứ hai giới thiệu một số phương

pháp trong nhận diện khuôn mặt thường được áp dụng trong thực tế và nghiên cứu.

Phần cuối cùng giới thiệu một số mạng tích chập thường được sử dụng trong bài toán

nhận diện khuôn mặt.

Chương 2. Hệ thống nhận diện khuôn mặt dựa trên mạng nơ ron tích chập

Các kỹ thuật cơ bản được sử dụng để xây dựng hệ thống nhận diện khuôn mặt

của luận văn được trình bày trong chương này. Nội dung của chương trình bày về các

phương pháp trích chọn đặc trưng phục vụ quá trình nhận diện khuôn mặt, phương

pháp định danh khuôn mặt và mô hình học máy được sử dụng để phân loại dữ liệu

nhận diện khuôn mặt. Chương này cũng bao gồm các thông tin về mô hình, kiến trúc

mạng nơ ron tích chập Inception-ResNet sử dụng cho việc trích chọn đặc trưng khuôn

mặt của luận văn.

Chương 3. Thử nghiệm và đánh giá

Chương này mô tả chi tiết về bộ dữ liệu được sử dụng, cùng các kịch bản

và kết quả các quá trình huấn luyện mô hình. Các kết quả thực nghiệm kèm theo

đánh giá mô hình sau khi huấn luyện cũng được trình bày trong chương này.

Nội dung của luận văn được kết thúc bằng phần Kết luận, trong đó trình bày

tóm lược các nội dung và kết quả đã đạt được trong luận văn, từ đó đề xuất các hướng

phát triển trong tương lại.

3

CHƯƠNG 1. TỔNG QUAN VỀ NHẬN DIỆN KHUÔN MẶT

1.1 Tổng quan về nhận diện khuôn mặt cùng với các ứng dụng thực tế

của các kỹ thuật nhận dạng khuôn mặt.

1.1.1 Tổng quan

Nhận diện khuôn mặt là một bài toán tổng hợp. Trong đó ta cần các mô đun

quan trọng như như xác định vị trí khuôn mặt, trích chọn đặc trưng rồi phân loại. Từ

đó ta có thể xác định danh tính người trong ảnh.

1.1.2 Kiến trúc tổng quát hệ thống nhận diện

Hình 1.1. Kiến trúc tổng quát về hệ thống nhận diện

Nhận ảnh là bộ phận thu nhận ảnh. Ảnh ở đây có thể nhận được qua camera

màu hoặc đen trắng. Tiền xử lý ảnh là bước tiền xử lý để nâng cao chất lượng ảnh

đầu vào. Vì ảnh thu nhận được có thể bị nhiễu hoặc độ tương phản thấp gây ảnh

hưởng đến việc trích chọn đặc trưng cũng như xác định vị trí khuôn mặt. Tiếp đến là

xác định vị trí khuôn mặt. Ở bước này hệ thống sẽ xác định vị trí khuôn mặt và các

điểm mắt, mũi, miệng. Trích chọn đặc trưng từ khuôn mặt sẽ thực hiện lấy khuôn mặt

trong ảnh gốc để thực hiện trích chọn đặc trưng. Phân loại là bước thực hiện phân

loại đặc trưng từ đó sẽ định danh được khuôn mặt đầu vào là ai. Kết luận là từ kết

quả phân loại sẽ đưa ra kết quả nhận diện.

1.1.3 Ứng dụng

Bài toán nhận diện khuôn mặt có rất nhiều ứng dụng trong cuộc sống. Trong

đó, một số ứng dụng tiêu biểu không thể không kể đến của bài toán này là hệ thống

phát hiện, truy vết tội phạm, hệ thống tìm trẻ lạc, hệ thống điểm danh, chấm công hay

ứng dụng nhận diện đối tác, khách hàng VIP. Các bài toán trên hiện đang được sử

dụng rất nhiều và thành một phần không thể thiếu trong cuộc sống của mỗi người.

4

1.2 Một số phương pháp trong nhận diện khuôn mặt thường được áp

dụng trong thực tế và nghiên cứu

1.2.1 Phân tích thành phần chính (PCA)

a. Giới thiệu

PCA (Principal Components Analysis) [1] là một thuật toán được sử dụng để

tạo ra một ảnh mới từ ảnh ban đầu. Ảnh mới này có kích thước nhỏ hơn nhiều so với

ảnh ban đầu nhưng vẫn mang những đặc trưng cơ bản nhất của ảnh cần nhận dạng.

Trong nghiên cứu [2], thuật toán PCA thường được sử dụng cho việc trích chọn đặc

trưng khuôn mặt. PCA không cần quan tâm đến việc tìm ra các đặc điểm cụ thể của

thực thể cần nhận dạng và mối quan hệ giữa các đặc điểm đó. Tất cả các chi tiết đó

đều được thể hiện ở ảnh mới được tạo ra từ PCA.

b. Thuật toán PCA

Không gian mới được tạo bởi PCA được cấu thành từ k vectơ đơn vị có chiều

là N. Mỗi vectơ được gọi là một Eigenface. Phép biến đổi :

A=

 W =

với K<<N

(1.1)

W=T.A

Với T là ma trận chuyển đổi, T có kích thước K x N. Gọi M là số ảnh đầu vào,

mỗi ảnh được chuyển thành vectơ N chiều. Từ (1.1) ta có tập hợp đầu vào

X={x₁, x₂,…,x_M} (x_i€ R^N)

(1.2)

Trung bình của các vectơ đầu vào :

X_tb=

(1.3)

Sai lệch so với tâm:

(1.4)

Φ_i= x_i- x_tb

Gọi A=[ Φ_1,Φ_2,…,Φ_M] ta có ma trận tương quan của A là :

5

(1.5)

C=

= A.A^T

Gọi các giá trị riêng của C là: λ_1,λ_{2, …,}λ_nsắp xếp theo thứ tự giảm dần, tương

ứng với N vectơ riêng u_1,u_{2, …,}u_N.Các vectơ riêng này trực giao từng đôi một, Mỗi

vectơ riêng u_iđược gọi là một eigenface. Tập hợp các vectơ ban đầu được biểu diễn

trong không gian tạo bởi n eugenface theo mô tả:

(1.6)

x-x_tb= w₁u₁+ w₂u₂+…+ w_Nu_N=

Chọn lấy K vectơ riêng u tương ứng với K giá trị riêng λ lớn nhất, ta có:

(1.7)

x-x_tb= w₁u₁+ w₂u₂+…+ w_Nu_N=

với K<<N

Vectơ các hệ số khai triển [w1, w2, …, wk] chính là biểu diễn mới của ảnh

được tạo ra trong không gian PCA. Ảnh mới vẫn giữ được các đặc điểm chính của

ảnh đầu vào. Vectơ [w₁, w₂, …, w_K] được tính theo công thức:

(1.8)

=

(x-x_tb) = U^T.(x-x_tb)

Vấn đề cần giải quyết ở đây là ma trận tương quan C=A.A^Tcó kích thước N².

Với N=180x200=36000, khối lượng tính toán sẽ rất lớn. Do đó, để tính được các

eigenface mà không cần tính cả ma trận C, người ta đưa ra phương pháp tính nhanh

dựa vào vectơ riêng và giá trị riêng của ma trận L=A^T.A có kích thước MxM với M

là số ảnh đầu vào. Gọi v_i, μ_ilần lượt là vectơ riêng và giá trị riêng của ma trận L:

A^T.A.v_i= μ_i. v_i

(1.9)

Nhân cả 2 vế với A, ta có :

A.A^T.A.v_i= μ_i. A.v_i

(1.10)

6

Ta thấy A.v_ichính là vectơ riêng của C=A.A^Tứng với giá trị riêng μ_i.Thuật

toán PCA thường được sử dụng để trích chọn vectơ đặc trưng. Không gian chứa vectơ

này có số chiều là N=w*h với mỗi bức ảnh có kích thước là w*h pixels. Các bước để

trích chọn đặc trưng là tạo một tập X gồm M ảnh (ảnh học), mỗi ảnh có kích thước

N, các ảnh được chuyển thành vectơ N chiều.

(1.11)

X = {x_1,x₂, …, x_M}

Từ đó ta sẽ tính trung bình của tập trên:

(1.12)

X_tb=

Bước tiếp theo là tính sai lệch của ảnh đầu vào với giá trị trung bình trên:

(1.13)

Φ_i= x_i- x_tb

Cuối cùng là tìm một tập M vectơ trực giao u biểu diễn phân bố mạnh nhất của

tập dữ liệu X. Tập các vectơ u được gọi là eigenface của tập dữ liệu học.Xây dựng

các ảnh mới v_itheo M vectơ u :

v_i= u_i^tΦ_i

Ω=[v_1,v_2,…,v_M]^T

(1.14)

Trong đó, v_i= u_i^tΦ_ilà vectơ đặc tính của ảnh thứ I trong không gian mới. Ω ở

đây là tập các eigenface, các thành phần cơ bản cho bức ảnh cần nhận dạng. Sau khi

trích chọn được các vectơ đặc tính, cần đối chiếu vectơ này với cơ sở dữ liệu, từ đó

đưa ra kết quả nhận dạng. Trong bài toán, kết quả nhận dạng sẽ là nhận biết được

hoặc chưa nhận biết được.

1.2.2 Phân tích sự khác biệt tuyến tính(LDA)

a. Giới thiệu

LDA được coi là một phương pháp giảm chiều dữ liệu (dimensionality

reduction), và cũng có thể được coi là một phương pháp phân lớp (classification), và

cũng có thể được áp dụng đồng thời cho cả hai, tức giảm chiều dữ liệu sao cho việc

7

phân lớp hiệu quả nhất. Trong nghiên cứu [3], [4] cũng chỉ rõ đây là một thuật toán

tốt được sử dụng cùng với các phương pháp khác như mạng nơ-ron nhân tạo hay PCA

trong bài toán nhận diện khuôn mặt.

b. Thuật toán LDA

Ý tưởng cơ bản của LDA là tìm một không gian mới với số chiều nhỏ hơn

không gian ban đầu sao cho hình chiếu của các điểm trong cùng 1 class lên không

gian mới này là gần nhau trong khi hình chiếu của các điểm của các lớp khác nhau là

khác nhau. Phương pháp LDA phân loại các lớp chưa biết thành các lớp đã biết, mà

ở đó các khuôn mặt tạo thành một lớp và sự khác biệt giữa các khuôn mặt trong một

lớp là rất nhỏ. Cả PCA chọn cách thống kê lấy mẫu, chọn lọc để nhận diện khuôn

mặt.

Thuật toán LDA dựa trên phân tích phân loại phi tuyến của Fisher là phương

pháp tính toán chuyển đổi tối đa hóa sự phân tán giữa các lớp trong khi giảm thiểu

phân tán trong lớp. Giải sử ta có các lớp C với 휇_푖là vectơ trung bình của các lớp i với

i = 1, 2,…C. 푀_푖là số lượng mẫu trong lớp i.

퐶

1

흁 = ∑ ꢀ 흁_푦

(1.15)

푐

푦=1

Gọi S_wlà ma trận tán xạ nội lớp (các phần tử trong lớp) và S_Blà ma trận tán

xạ tương hổ của các lớp thuộc C.

퐶

푀푖

S_w= ∑ ꢀ ∑ ꢀ (푦_푗− 휇_푖)(푦_푗− 휇_푖)^T

푖=1 푗=1

퐶

푇

(

)(

)

푆_퐵= ∑ ꢀ 휇_푖− 휇 휇_푖− 휇

(1.16)

(1.17)

푖=1

Phương pháp LDA sẽ tìm giá trị W để cực đại hóa hàm mục tiêu H_(W)

:

푊푆_퐵푊^푇

푊푆_푊푊^푇

H_(W)

=

8

LDA tính toán chuyển đổi tối đa hóa sự phân tán giữa các lớp trong khi giảm

thiểu phân tán trong lớp.

1.2.3 Cây quyết định (Decision Tree)

a. Giới thiệu

Việc quan sát, suy nghĩ và đưa ra các quyết định của con người thường được

bắt đầu từ các câu hỏi. Trong học máy cũng có mô hình đưa ra quyết định dựa vào

các câu hỏi như cây quyết định. Cây quyết định (Decision Tree) là một trong những

thuật toán phổ biến của học máy thuộc nhánh học có giám sát. Decision Tree ra đời

từ những năm 1975 từ một tác giả có tên Ross Quinlan. Thuật toán này là tiền đề để

ra đời những phương pháp dự báo theo dòng Tree-based method như là: Random

Forest, Bagging, AdaBoost, Gradient Boosting Machine. Mô hình cây quyết định

thuộc nhóm các bài toán học có giám sát (supervised learning). Mô hình này có thể

sử dụng vào cả hai loại bài toán phân loại (classification) và hồi quy (regression) theo

[5]. Hiện nay, mô hình cây quyết định vẫn còn được sử dụng rất nhiều trong các

nghiên cứu cũng như ứng dụng [6].

b. Thành phần

Một cây quyết định được bao gồm 4 thành phần như sau: root node, internal

node, leaf node, dept. Trong đó root node là nhánh chia đầu tiên của cây quyết định.

Internal node là các nhánh chia tiếp theo của cây quyết định. Leaf node là các nhánh

cuối cùng của một quyết định. Dept sẽ quy định tầng của cây

9

Hình 1.2. Thành phần cây quyết định

c. Hàm số entropy

Trên thực tế ta sẽ sẽ có một bảng dữ liệu với rất nhiều biến. Decision Tree sẽ

sử dụng một vài chỉ số để đưa ra việc xác định câu hỏi và thứ tự các biến nào chia dữ

liệu để tạo ra Decision Tree có khả năng phân loại tốt nhất. Các hệ số này là Gini và

Cross-Entropy.

Để tìm nghiệm cho các bài toán có nhiều thuộc tính và mỗi thuộc tính có nhiều

giá trị khác nhau thì ta sẽ sử dụng một phương pháp đơn giản thường được sử dụng

là tại mỗi bước, một thuộc tính tốt nhất sẽ được chọn ra dựa trên một tiêu chuẩn nào

đó. Với mỗi thuộc tính được chọn, ta chia dữ liệu vào các child node tương ứng với

các giá trị của thuộc tính đó rồi tiếp tục áp dụng phương pháp này cho mỗi child node.

Trong đó, hành động chọn ra thuộc tính tốt nhất ở mỗi bước như trên gọi là cách

chọn tham lam (greedy). Cách chọn tham lam này có thể không phải là tối ưu nhưng

nó đem lại kết quả cũng khá tốt cho bài toán này. Child node sẽ chứa những câu trả

lời tương ứng với dữ liệu sau mỗi câu hỏi. Câu hỏi ở đây được coi như là một thuộc

tính và câu trả lời sẽ là giá trị của thuộc tính đó. Để đánh giá chất lượng của một cách

phân chia, chúng ta cần đi tìm một phép đo. Và đó là hàm entropy.

Giả sử ta có một dãy các giá trị (x₁, x₂, … , x_n) . Công thức để tính xác suất sao

cho x nhận các giá trị này là