NGUYÊN THỊ HÒA

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

NGUYÊN THỊ HÒA

KHOA HỌC MÁY TÍNH

2012 – 2013 Hà Nội, 2014

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỌC MÁY VÀ
ỨNG DỤNG

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

2014 – 2016

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

HÀ NỘI

HÀ NỘI - 2016


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

NGUYÊN THỊ HÒA

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỌC MÁY VÀ

Em xin gửi lời cảm ơn chân thành cảm ơn tất cả các thầy cô giáo của Học
viện Công nghệ Bƣu chính Viễn thông đã giảng dạy và dìu dắt em trong trong suốt
quá trình học tập tại trƣờng từ khi còn học đại học cho đến sau đại học.
Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè và những ngƣời đã
luôn ở bên cổ vũ tinh thần, tạo điều kiện thuận lợi cho em để em có thể học tập tốt
và hoàn thiện luận văn.
Em xin chân thành cảm ơn!


vii

MỤC LỤC
LỜI CAM ĐOAN ...............................................................................................................................i
LỜI CẢM ƠN ................................................................................................................................... ii
MỤC LỤC ...................................................................................................................................... vii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................................................. vii
DANH SÁCH BẢNG .................................................................................................................... viii
DANH SÁCH HÌNH VẼ ............................................................................................................... viii
LỜI MỞ ĐẦU .................................................................................................................................... 1
Chƣơng 1 - TỔNG QUAN VỀ HỌC MÁY ....................................................................................... 3
1.1
Một số khái niệm về học máy ............................................................................................ 3
1.2

Phân loại các thuật toán học máy ....................................................................................... 4

1.2.1

Học có giám sát .......................................................................................................... 4



2.1.1
2.1.1.1

Định nghĩa ............................................................................................................ 11

2.1.1.2

Chiến lƣợc cơ bản xây dựng cây quyết định ........................................................ 12

2.1.1.3

Thuận lợi và hạn chế của mô hình cây quyết định ............................................... 15

2.1.2

Thuật toán ID3 ......................................................................................................... 16

2.1.2.1

Thuật toán ............................................................................................................ 17

2.1.2.2

Độ đo tính thuần nhất ........................................................................................... 18

a.

Entropy đo tính thuần nhất của tập huấn luyện ........................................................ 19


2.2.3

Phƣơng pháp SVM phân loại nhị phân .................................................................... 24

2.2.3.1

SVM tuyến tính .................................................................................................... 25


viii

a.

SVM tuyến tính với tập dữ liệu phân tách đƣợc ...................................................... 28

2.2.3.2

SVM phi tuyến tính .............................................................................................. 36

2.2.3.3

Thuật toán tối thiểu tuần tự SMO......................................................................... 40

Thuật toán mạng nơ ron nhân tạo..................................................................................... 40

2.3
2.3.1

Giới thiệu ................................................................................................................. 40


Kết chƣơng ....................................................................................................................... 50

Chƣơng 3:
3.1

ỨNG DỤNG GIẢI QUYẾT BÀI TOÁN PHÂN LOẠI .......................................... 51

Bài toán phân loại ............................................................................................................ 51

3.1.1

Giới thiệu ................................................................................................................. 51

3.1.2

Mô tả bài toán phân loại ........................................................................................... 51

3.1.3

Phƣơng pháp phân loại ............................................................................................. 51

3.1.4

Đánh giá mô hình ..................................................................................................... 53

3.2
Bài toán phân loại bệnh dựa trên dấu hiệu khám bệnh lâm sàng và các chỉ số xét nghiệm
hóa nghiệm ................................................................................................................................... 55
3.2.1


Thực hiện thực nghiệm ............................................................................................ 65

3.3.4

Kết quả thực nghiệm ................................................................................................ 67

3.3.5

Phân tích và đánh giá kết quả ................................................................................... 69

3.4

Kết chƣơng ....................................................................................................................... 70

KẾT LUẬN ...................................................................................................................................... 71
IV. DANH MỤC CÁC TÀI LIỆU THAM KHẢO.......................................................................... 72
PHỤ LỤC......................................................................................................................................... 76


vii

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

Từ viết tắt

Nghĩa tiếng anh

Nghĩa tiếng việt

SVM


Linear Least Square Fit

Tuyến tính bình phƣơng nhỏ nhất

EM

expectation-maximization

Cực đại kỳ vọng

XN

HAC

Xét nghiệm

Hierarchical Agglomerative Kỹ thuật phân cụm theo thứ bậc
Clustering

SOM

Self-Organizing Map

Giải thuật bản đồ tự tổ chức


viii

DANH SÁCH BẢNG

Hình 2.15 Cấu trúc mạng nơ ron ..............................................................................42
Hình 2.16 Cấu trúc mạng nơ ron nhiều lớp ..............................................................42
Hình 2.17 Tiến trình học ...........................................................................................45
Hình 2.18 Mô hình tính toán một nơ-ron .................................................................46
Hình 3.1 Giai đoạn xây dựng mô hình .....................................................................52
Hình 3.2 Giai đoạn phân loại ....................................................................................52
Hình 3.3 Đánh giá độ chính xác của mô hình phần lớp với phƣơng pháp Holdout 53
Hình 3.4 Mô hình bài toán phân loại mặt bệnh ........................................................56
Hình 3.5 Các bƣớc phân loại mặt bệnh dựa trên triệu chứng lâm sàng và cận lâm
sàng ...........................................................................................................................57
Hình 3.6 Giao diện khởi động của WEKA ...............................................................63
Hình 3.7 Thực hiện phân loại với J48 Classifier và SMO Classifier .......................66


ix
Hình 3.8 So sánh độ nhạy và thời gian thực hiện giữa thuật toán SMO và cây quyết
định J48 .....................................................................................................................68


1

LỜI MỞ ĐẦU
Trong những năm gần đây, sự phát triển vƣợt bậc của công nghệ thông tin
đã làm số lƣợng thông tin đƣợc trao đổi trên mạng Internet tăng một cách đáng kể.
Do đó, số lƣợng thông tin đƣợc lƣu trữ trong các kho dữ liệu cũng tăng với một tốc
độ chóng mặt, và tốc độ thay đổi thông tin là cực kỳ nhanh chóng. Theo thống kê
của Broder et al (2003) thì cứ sau 9 tháng hoặc 12 tháng lƣợng thông tin đó lại tăng
gấp đôi. Cùng với đó là sự phổ cập máy tính và mạng internet, thói quen tìm kiếm
thông tin qua mạng, đặc biệt là qua các trang web tìm kiếm nổi tiếng ngày càng phổ
biến. Thông qua internet chúng ta có nhiều cơ hội để tiếp xúc với nguồn thông tin


Chƣơng 1 - TỔNG QUAN VỀ HỌC MÁY
Chương này trình bày một số kiến thức tổng quan về học máy: những khái
niệm cơ bản trong học máy, mô hình học máy, phân loại các phương pháp học máy,
ứng dụng của học máy trong thực tế.

1.1

Một số khái niệm về học máy
Học máy là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc nghiên cứu

và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải
quyết những vấn đề cụ thể[36].
Rất khó để định nghĩa một cách chính xác về học máy. “Học - learn” có ý
nghĩa khác nhau trong từng lĩnh vực: tâm lý học, giáo dục, trí tuệ nhân tạo,…
Một định nghĩa rộng nhất: “học máy là một cụm từ dùng để chỉ khả năng
một chƣơng trình máy tính để tăng tính thực thi dựa trên những kinh nghiêm đã trải
qua” hoặc “học máy là để chỉ khả năng một chƣơng trình có thể phát sinh ra một
cấu trúc dữ liệu mới khác với các cấu trúc dữ liệu cũ”. Lợi điểm của các phƣơng
pháp học máy là nó phát sinh ra các luật tƣờng minh, có thể đƣợc sửa đổi, hoặc
đƣợc huấn luyện trong một giới hạn nhất định. Các phƣơng pháp học máy hoạt
động trên các dữ liệu có đặc tả thông tin. Các thông tin đƣợc trình bày theo một cấu
trúc gồm 4 mức đƣợc gọi là tri thức kim tự tháp dƣới đây [32].

Hình 1.0.1 Mô hình kim tự tháp: Từ dữ liệu đến tri thức


4
Học máy là sự tự động của quy trình học và việc học thì tƣơng đƣơng với
việc xây dựng những luật dựa trên việc quan sát trạng thái trên cơ sở dữ liệu và

cho từng lớp (đặc tính của mẫu dữ liệu). Ngƣời ta có thể sử dụng các luật phân loại


5
hình thành trong quá trình học và phân loại để có thể sử dụng dự báo các lớp dữ liệu
sau này.
Thuật toán học có giám sát gồm tập dữ liệu huấn luyện M cặp:
S = {(xi, cj) i=1,…,M; j=1,…,C}
Các cặp huấn luyện này đƣợc gọi là mẫu, với
xi là vector n-chiều còn gọi là vector đặc trƣng,
ci là lớp thứ j đã biết trƣớc.
Thuật toán học máy giám sát tìm kiếm không gian của những giả thuyết có
thể, gọi là H. Đối với một hay nhiều giả thuyết, mà ƣớc lƣợng tốt nhất hàm không
đƣợc biết chính xác f : x  c.
Đối với công việc phân loại có thể xem giả thuyết nhƣ một tiêu chí phân loại.
Thuật toán học máy tìm ra những giả thuyết bằng cách khám phá ra những đặc
trƣng chung của những ví dụ mẫu thể hiện cho mỗi lớp. Kết quả nhận đƣợc thƣờng
ở dạng luật (Nếu ... thì). Khi áp dụng cho những mẫu dữ liệu mới, cần dựa trên
những giả thuyết đã có để dự báo những phân loại tƣơng ứng của chúng. Nếu nhƣ
không gian giả thuyết lớn, thì cần một tập dữ liệu huấn luyện đủ lớn nhằm tìm kiếm
một hàm xấp xỉ tốt nhất f.
Tùy thuộc vào mức độ của thuật toán học giám sát, ngƣời ta có những mô
hình học giám sát nhƣ sau:
-

Học vẹt: hệ thống luôn luôn đƣợc “dạy” những luật đúng, rồi có học hội tụ.

-

Học bằng phép loại suy: hệ thống đƣợc dạy phản hồi đúng cho một công việc

Trong trƣờng hợp chỉ có ít, hay gần nhƣ không có tri thức về dữ liệu đầu
vào, khi đó một hệ thống học không giám sát sẽ khám phá ra những phân loại của
dữ liệu, bằng cách tìm ra những thuộc tính, đặc trƣng chung của những mẫu hình
thành nên tập dữ liệu. Một thuật toán học máy giám sát luôn có thể biến đổi thành
một thuật toán học máy không giám sát.
Đối với một bài toán mà những mẫu dữ liệu đƣợc mô tả bởi n đặc trƣng,
ngƣời ta có thể chạy thuật toán học giám sát n-lần, mỗi lần với một đặc trƣng khác
nhau đóng vai trò thuộc tính lớp, mà chúng ta đang tiên đoán. Kết quả sẽ là n tiêu
chí phân loại (n bộ phân loại), với hy vọng là ít nhất một trong n bộ phân loại đó là
đúng.
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ân cụm phục vụ khai thác hiệu quả nguồn dữ liệu chƣa gán
nhãn nhiều và rất đa dạng. Việc lựa chọn sử dụng thuật toán nào tuỳ thuộc vào dữ
liệu và mục đích của từng bài toán. Trong đó các thuật toán thƣờng đƣợc sử dụng
nhƣ: k-means, HAC, SOM ...

1.2.3 Học nửa giám sát


7

Học nửa giám sát là các thuật toán học tích hợp từ học giám sát và học
không giám sát. Học bán giám sát sử dụng cả dữ liệu đã gán nhãn và chƣa gán nhãn
để huấn luyện - điển hình là một lƣợng nhỏ dữ liệu có gán nhãn cùng với lƣợng lớn
dữ liệu chƣa gán nhãn.
Nội dung chính của học bán giám sát là hệ thống sử dụng một tập huấn luyện
gồm 2 phần: các ví dụ huấn luyện có nhãn, thƣờng với số lƣợng ít, và các ví dụ học
không có nhãn, thƣờng với số lƣợng nhiều. Các dữ liệu gán nhãn thƣờng hiếm, đắt
và rất mất thời gian, đòi hỏi sự nỗ lực của con ngƣời, trong khi đó dữ liệu chƣa gán
nhãn thì vô vàn nhƣng để sử dụng vào mục đích cụ thể của chúng ta thì rất khó, vì

có một sự phân loại lỗi thì có thể tăng cƣờng thêm cho chính nó, thì co-training
giảm bớt đƣợc lỗi tăng cƣờng có thể xảy ra khi có một quá trình phân loại bị lỗi.
Cùng với quá trình phát triển và việc áp dụng phổ biến và sự tăng lên về chất lƣợng
của thuật toán SVM, SVM truyền dẫn nổi bật lên nhƣ một SVM chuẩn mở rộng cho
phƣơng pháp học bán giám sát. Gần đây các phƣơng pháp học bán giám sát dựa trên
đồ thị thu hút nhiều sự quan tâm của các nhà khoa học cũng nhƣ những ngƣời quan
tâm đến lĩnh vực khai phá dữ liệu. Các phƣơng pháp Graph-based bắt đầu với một
đồ thị mà các nút là các điểm dữ liệu gán nhãn và chƣa gán nhãn, và các điểm nối
phản ánh đƣợc sự giống nhau giữa các nút này. Có thể thấy học bán giám sát là một
quá trình hoàn thiện dần các thuật toán để áp dụng vào các vấn đề của đời sống con
ngƣời. Một số thuật toán học bán giám sát điển hình có thể xem là đƣợc áp dụng
nhiều nhất, đó là Naive Bayes, EM với các mô hình hỗn hợp sinh, self-training, cotraining, SVM truyền dẫn, và các phƣơng pháp dựa trên đồ thị.

1.3

Ứng dụng của học máy
Học máy có ứng dụng rộng khắp trong các ngành khoa học và sản xuất, đặc

biệt những ngành cần phân tích khối lƣợng dữ liệu khổng lồ. Dƣới đây là một số
ứng dụng phổ biến của học máy.

1.3.1 Ứng dụng trong phân tích dự báo[32]
 Các loại phƣơng pháp dự báo:
-

Dự báo điểm và dự báo khoảng.

-

Phƣơng pháp định tính và định lƣợng.


 Ứng Dụng Các Mô Hình Dự Báo Của Học máy.
-

Chƣơng Trình Ứng Dụng Hệ Thống Mạng Nơron Lan Truyền Ngƣợc (FNN).

-

Chƣơng Trình Ứng Dụng Hệ luật mờ (SAM).

-

Chƣơng Trình Ứng Dụng Mạng Nơ rôn dạng Lan Truyền Ngƣợc và thuật toán
di truyền vào phân tích dự báo.
Các chƣơng trình ứng dụng mô hình mạng nơ rôn mờ hồi quy, sử dụng file

dữ liệu huấn luyện, thử nghiệm và dự báo dạng văn bản.

1.3.2 Ứng dụng trong tìm kiếm
Mô hình tìm kiếm có thể gom lại gồm hai thành phần chính: một thành phần
chạy trực tuyến trên web dùng để tƣơng tác với ngƣời dùng, nhận và xử lý câu truy
vấn, một thành phần chạy không trực tuyến dùng để xử lý lƣu lịch sử truy cập trang
web, xử lý tập từ khóa trên trang, xử lý gán trọng số cho trang web, xử lý gom
nhóm phiên làm việc và huấn luyện mạng.
Để quá trình tìm kiếm của ngƣời dùng ít tốn thời gian và tài nguyên xử lý,
toàn bộ quá trình tính toán và tiền xử lý đƣợc thi hành trƣớc trên máy chủ, thành
phần trực tuyến chỉ tính toán lại một phần kết quả do phụ thuộc vào câu truy vấn


10

quyết định, SVM và mạng nơ-ron.


11

Chƣơng 2: NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỌC
MÁY
Chương này trình bày một số thuật toán học máy tiêu biểu, cụ thể là thuật
toán cây quyết định, vectơ hỗ trợ SVM và mạng nơron nhân tạo.

2.1 Cây quyết định
Cây quyết định là một trong phƣơng pháp học máy tiêu biểu có nhiều ứng
dụng trong phân loại và dự đoán. Mặc dù độ chính xác của phƣơng pháp này không
thật cao so với những phƣơng pháp đƣợc nghiên cứu gần đây, học cây quyết định
vẫn có nhiều ƣu điểm nhƣ đơn giản, dễ lập trình, và cho phép biểu diễn hàm phân
loại dƣới dạng dễ hiểu, dễ giải thích cho con ngƣời. Phƣơng pháp này thƣờng đƣợc
dùng nhƣ phƣơng pháp mở đầu để minh họa cho kỹ thuật học bộ phân loại từ dữ
liệu. Phƣơng pháp học cây quyết định đƣợc sử dụng cho việc học các hàm phân loại
từ dữ liệu huấn luyện, trong đó cây quyết định đƣợc sử dụng làm biểu diễn xấp xỉ
của hàm phân loại, tức là hàm có đầu ra là các giá trị rời rạc. Nhƣ đã nói ở trên,
phƣơng pháp học này thuộc loại học có giám sát.

2.1.1 Tổng quan về cây quyết định
2.1.1.1 Định nghĩa
Cây quyết định là một cấu trúc ra quyết định có dạng cây. Cây quyết định
nhận đầu vào là một bộ giá trị thuộc tính mô tả một đối tƣợng hay một tình huống
và trả về một giá trị rời rạc. Mỗi bộ thuộc tính đầu vào đƣợc gọi là một mẫu hay
một ví dụ, đầu ra gọi là loại hay nhãn phân loại. Thuộc tính đầu vào còn đƣợc gọi là
đặc trƣng và có thể nhận giá trị rời rạc hoặc liên tục. Để cho đơn giản, trƣớc tiên ta
sẽ xem xét thuộc tính rời rạc, sau đó sẽ mở rộng cho trƣờng hợp thuộc tính nhận giá

Ngƣợc lại, dùng độ đo thuộc tính để chọn thuộc tính sẽ phân tách tốt nhất các
mẫu vào các lớp.

-

Một nhánh đƣợc tạo cho từng giá trị của thuộc tính đƣợc chọn và các mẫu đƣợc
phân hoạch theo.

-

Dùng đệ quy cùng một quá trình để tạo cây quyết định.


13

-

Tiến trình kết thúc chỉ khi bất kỳ điều kiện nào sau đây là đúng.
 Tất cả các mẫu cho một nút cho trƣớc đều thuộc về cùng một lớp.
 Không còn thuộc tính nào mà mẫu có thể dựa vào để phân hoạch xa
hơn.
 Không còn mẫu nào cho nhánh.

-

Tuy nhiên, nếu không chọn đƣợc thuộc tính phân loại hợp lý tại mỗi nút, ta sẽ
tạo ra cây rất phức tạp, ví dụ nhƣ cây dƣới đây:
Cho tập dữ liệu sau:
Bảng 2.1 Tập dữ liệu thời tiết


Âm u

Nóng

Cao

Yếu

Có

Mƣa

Ấm áp

Cao

Yếu

Có

Mƣa

Lạnh

Bình thƣờng

Yếu

Có


Nắng

Lạnh

Bình thƣờng

Yếu

Có

Mƣa

Ấm áp

Bình thƣờng

Yếu

Có

Nắng

Ấm áp

Bình thƣờng

Mạnh

Có



14

Từ dữ liệu trên ta xây dựng đƣợc cây quyết định nhƣ sau:
Quang cảnh

Nắng

Độ ẩm

U ám

Mƣa

U ám

Gió

Có
Bình thƣờng

Không

Có

Mạnh
Không

Yếu
Có

con,taxi}.Việc phân chia dữ liệu dựa vào phép kiểm tra giá trị của thuộc tính rời rạc
đƣợc chọn tại một ví dụ cụ thể có thuộc tập giá trị của thuộc tính đó hay không. Đây
là phép kiểm tra logic đơn giản, không tốn nhiều tài nguyên tính toán. Trong khi đó,
với thuộc tính liên tục (thuộc tính dạng số) thì tập giá trị là không xác định trƣớc.
Chính vì vậy, trong quá trình phát triển cây, cần sử dụng kiểm tra dạng nhị phân:
value(A) ≤ θ. Với θ là hằng số ngƣỡng đƣợc lần lƣợt xác định dựa trên từng giá trị
riêng biệt hay từng cặp giá trị liền nhau (theo thứ tự đã sắp xếp) của thuộc tính liên
tục đang xem xét trong tập dữ liệu đào tạo. Điều đó có nghĩa là nếu thuộc tính liên
tục A trong tập dữ liệu đào tạo có d giá trị phân biệt thì cần thực hiện d-1 lần kiểm
tra value(A) ≤ θi với i = 1..d-1 để tìm ra ngƣỡng θ tốt nhất tƣơng ứng với thuộc tính
đó. Việc xác định giá trị của θ và tiêu chuẩn tìm θ tốt nhất tùy vào chiến lƣợc của
từng thuật toán.

2.1.1.3 Thuận lợi và hạn chế của mô hình cây quyết định
Một số ƣu điểm của cây quyết định:
-

Cây quyết định tự giải thích và khi đƣợc gắn kết lại, chúng có thể dễ dàng tự
sinh ra. Nói cách khác, nếu cây quyết định mà có số lƣợng nút lá vừa phải thì