ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG HẢI YẾN
HỌC BÁN GIÁM SÁT SVM-kNN
VÀ ỨNG DỤNG THỬ NGHIỆM PHÂN LỚP VĂN BẢN
GIAO THÔNG VẬN TẢI
LUẬN VĂN THẠC SĨ
Hà Nội - 2012
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG HẢI YẾN
HỌC BÁN GIÁM SÁT SVM-kNN
VÀ ỨNG DỤNG THỬ NGHIỆM PHÂN LỚP VĂN BẢN
GIAO THÔNG VẬN TẢI
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
CÁN BỘ HƯỚNG DẪN: PGS. TS. HÀ QUANG THỤY
Hà Nội - 2012
MỤC LỤC
DANH SÁCH CÁC HÌNH ................................................................................. 3
DANH SÁCH CÁC BẢNG ............................................................................... 4
DANH SÁCH CÁC TỪ VIẾT TẮT ................................................................... 5
MỞ ĐẦU ........................................................................................................... 6
Chương 1: Phương pháp phân lớp SVM và kNN................................................ 7
1.1. Phương pháp SVM .............................................................................. 7
1.1.1. Tách tuyến tính .......................................................................... 7
1.1.2. Tách phi tuyến ......................................................................... 11
1.1.3. Phân lớp đa lớp với SVM ........................................................ 14
1.2. Phương pháp kNN ........................................................................... 159
1.3. So sánh SVM với kNN ...................................................................... 18
Chương 2: Phương pháp SVM-kNN phân lớp văn bản ..................................... 20
2.1. Giới thiệu .......................................................................................... 20
2.2. Học bán giám sát SVM-kNN ............................................................ 22
2.2.1. Ý tưởng ................................................................................... 22
2.2.2. Thuật toán SVM-kNN ............................................................. 22
2.3. Áp dụng SVM phân lớp văn bản tiếng Việt ....................................... 24
2.3.1. Phát biểu bài toán .................................................................... 24
2.3.2 Tiền xử lý dữ liệu ..................................................................... 26
2.3.3 Trích chọn đặc trưng................................................................. 27
2.3.4. Phương pháp biểu diễn văn bản ............................................... 29
2.3.5. Đánh giá bộ phân lớp. .............................................................. 31
2.3.5.1. các độ đo .............................................................................. 32
Chương 3: Thực nghiệm phân lớp văn bản tiếng việt với thuật toán phân lớp bán
giám sát SVM-kNN .......................................................................................... 33
3.1. Môi trường và các công cụ sử dụng thực nghiệm .............................. 33
3.2. Xây dựng tập dữ liệu ......................................................................... 34
3.2.1. Phương pháp thu thập dữ liệu .................................................. 34
3.2.2. Tiền xử lý dữ liệu .................................................................... 36
3.2.3. Chọn từ đặc trưng và biểu diễn TF x DF.................................. 37
3.2.4. Thực nghiệm phân lớp bán giám sát SVM-kNN ...................... 37
KẾT LUẬN ...................................................................................................... 40
TÀI LIỆU THAM KHẢO ................................................................................ 41
3
DANH SÁCH CÁC HÌNH
Hình 1: Minh họa dữ liệu có thể phân tách một cách tuyến tính ......................... 8
Hình 2: Lề của một siêu phẳng ........................................................................... 8
Hình 3: Siêu phẳng có lề lớn .............................................................................. 9
Hình 4: Minh họa vector hỗ trợ ........................................................................ 10
Hình 5: Trường hợp dữ liệu không thể phân tách bằng một siêu phẳng ............ 12
Hình 6: Hàm ánh xạ từ dữ liệu phi tuyến sang dữ liệu tuyến tính ..................... 12
Hình 7: Các bước trong mô hình học máy có giám sát ..................................... 15
Hình 8: Minh họa vector hỗ trợ và vector biên. ................................................ 22
Hình 9: Mô hình đề xuất bởi Kunlun Li và cộng sự [7] .................................... 23
Hình 10: Các pha chính trong quá trình phân lớp văn bản ................................ 25
Hình 11: Mô hình hóa quá trình tiền xử lý dữ liệu. ........................................... 26
Hình 12: Các nội dung sẽ tách ra từ web .......................................................... 35
Hình 13: độ chính xác của bộ phân lớp trong 10 lần huấn luyện. ...................... 39
4
DANH SÁCH CÁC BẢNG
Bảng 1: Một số từ nhiễu cần được loại bỏ ........................................................ 27
Bảng 2: Cấu hình hệ thống thử nghiệm ............................................................ 33
Bảng 3: Công cụ phần mềm sử dụng ................................................................ 33
Bảng 4: các từ khóa xác định tiều đề và nội dung bài ....................................... 36
Bảng 5: Một số từ dừng loại bỏ trong quá trình xử lý ....................................... 36
Bảng 6: kết quả sau khi thu thập dữ liệu ........................................................... 37
Bảng 7: văn bản thuộc văn bản giao thông và không thuộc .............................. 37
Bảng 8:độ chính xác 10 lần huấn luyện với k = 5, n = 20 ................................. 39
5
DANH SÁCH CÁC TỪ VIẾT TẮT
SVM
Support Vector Machine
kNN
K Nearest Neighbors
MMH
Maximum marginal hyperplane
kNN-SVM
k Nearest Neighbors- Support Vector Machine
GTVT
Giao thông vận tải
TFIDF
Term Frequency Inverse Document Frequency
TF
Term frequency
DF
Document Frequency
URL
Uniform Resource Locator
DAGSVM
Direted Acyclic Graph Support Vector Machine
6
MỞ ĐẦU
Khối lượng khổng lồ các văn bản tiếng Việt trên mạng Internet đặt ra một
thách thức nhằm phân lớp tự động hoặc bán tự động các văn bản này nhằm cung
cấp những thông tin tập trung và có giá trị cho một ngành nghề cụ thể nào đó.
Trong các phương pháp phân lớp văn bản phổ biến thì phương pháp SVM
(Support Vertor Machine) được sử dụng với độ tin cậy cao. Tuy nhiên SVM
không tối ưu hóa thời gian tính toán sai số lớn trong việc ước lượng khoảng giữa
hai vector. Tức là khi các vector có số chiều lớn thì tốc độ của SVM bị hạn chế.
Trong luận văn này, tôi nghiên cứu phương pháp lai giữa k-láng giềng gần
(kNN) với SVM nhằm thực hiện phân đa lớp văn bản, lý do chính là nhằm tăng
khả năng tính toán trong cả quá trình huấn luyện và thực hiện phân lớp, kết quả
là phương pháp này đạt kết quả khá hơn trong thực tế thử nghiệm của luận văn.
Nội dung luận văn gồm 3 chương:
Chương 1: Giới thiệu khái quát phương pháp phân lớp SVM và kNN.
Chương 2: Giới thiệu giải pháp chi tiết các thuật toán lai SVM-kNN theo
hai phương pháp [5] và [7], quan điểm và các viễn cảnh cho các thuật toán lai
SVM-kNN tương ứng. Giới thiệu mô hình của thuật toán.
Chương 3: Dựa vào mô hình ở chương 2, tiến hành thực nghiệm việc
phân lớp văn bản tiếng Việt theo hai nhóm: nhóm văn bản liên quan tới ngành
Giao thông vận tải và nhóm không liên quan. Để làm rõ mô hình cũng như 3 pha
chính trong mô hình, các thực nghiệm trên các nội dung văn bản lấy tự động từ
internet được tiến hành. Luận văn tập trung đánh giá kết quả thực nghiệm từ 2
pha: tạo tập huấn luyện cho SVM-kNN và phân lớp SVM-kNN
7
Chương 1: Phương pháp phân lớp SVM và kNN
1.1. Phương pháp SVM
Phương pháp máy vector hỗ trợ (Support Vector Machine – SVM) là
phương pháp phân lớp dựa trên lý thuyết học thống kê được Corters và Vapnik
giới thiệu vào năm 1995 để giải quyết vấn đề nhận dạng mẫu hai lớp. Nó có khả
năng xử lý các tập dữ liệu cả khả tách tuyến tính lẫn không khả tách tuyến tính.
Bản chất của thuật toán này là nó xây dựng một siêu phẳng để phân chia tập dữ
liệu khả tách tuyến tích thành 2 nửa. Trong trường hợp nếu tập dữ liệu là không
khả tách tuyến tính thì nó sẽ sử dụng một hàm nhân (kernel function) để chuyển
đổi tập dữ liệu ban đầu sang một không gian mới có số chiều lớn hơn để xử lý.
Đây là phương pháp tiếp cận phân tách vector rất hiệu quả. Các thử nghiệm cho
thấy, phương pháp SVM có khả năng phân lớp khá tốt đối với bài toán phân lớp
văn bản cũng như trong nhiều ứng dụng khác (như nhận dạng chữ viết tay, nhận
dạng khuôn mặt…).
1.1.1. Tách tuyến tính
Thuật toán SVM cơ sở là trường hợp tập dữ liệu huấn luyện chỉ có 2 lớp
và nó phân bố ở dạng vector và ta có thể phân tách chúng một cách tuyến tính
bằng một siêu phẳng. Gọi D là tập dữ liệu huấn luyện: (X1, y1), (X2, y2), … , (X|D|,
y|D|), trong đó Xi là các phần tử dữ liệu và yi là nhãn tương ứng của nó. Giá trị
của yi có thể nhận là một trong 2 giá trị {-1, +1}. Để có thể hiển thị được dữ liệu
ta lấy trường hợp dữ liệu được biểu diễn bằng 2 thuộc tính A1 và A2, và các phần
tử dữ liệu của tập D được minh họa bằng hình 1. Từ hình vẽ cho chúng ta thấy
dữ liệu có thể phân tách thành 2 nửa bằng một đường thẳng. Tuy nhiên số lượng
các đường thẳng có thể dùng để phân tách tập dữ liệu trên thành 2 nửa là vô hạn
(hình 1 minh họa một số đường thằng vẽ bằng đường đứt nét có thể dùng để
phân tách dữ liệu thành 2 lớp riêng biệt). Trong trường hợp dữ liệu được biểu
diễn bằng 3 thuộc tính (3 chiều) thì đường thẳng sẽ được thay thế bằng mặt
phẳng (plane), và trường hợp tổng quát (n chiều) thì chúng ta dùng siêu phẳng
(hyperplane) có số chiều n-1 để tách tập dữ liệu khả tách tuyến tính. Như vậy,
tập dữ liệu hai lớp n-chiều được gọi là khả tách tuyến tính nếu tồn tại một siêu
phẳng tuyến tính (n-1 chiều) tách không gian n chiều thành hai phần, phần này
chứa dữ liệu chỉ thuộc một lớp và phần kia chứa dữ liệu chỉ thuộc lớp còn lại.
Vậy vấn đề chủ yếu trong SVM là phải làm sao tìm ra siêu phẳng tốt nhất,
thuật toán SVM sẽ cố gắng tìm siêu phẳng có lề lớn nhất (maximum marginal
8
hyperplane - MMH). Khái niệm lề có thể được minh họa trên Hình 2, lề của siêu
phẳng h là tổng khoảng cách từ h đến 2 siêu phẳng là tiếp tuyến với 2 miền dữ
liệu (ở hai bên siêu phẳng) và song song với siêu phẳng h. Hay nói một cách
khác, lề của siêu phẳng h là tổng khoảng cách của 2 phần tử dữ liệu (ở 2 mặt của
siêu phẳng) trong tập dữ liệu huấn luyện gần với h nhất. Hình 3 minh họa một
siêu phẳng khác có lề lớn hơn so với lề của siêu phẳng trong hình 2. Lý do của
việc tìm siêu phẳng có lề lớn nhất là ta hy vọng nó sẽ nó có thể phân lớp tốt
nhất, nó cho chúng ta tỉ lệ lỗi phân lớp thấp nhất. Một siêu phẳng phân lớp có
thể biểu diễn bằng công thức:
W X + b = 0
(1.1)
Hình 1: Minh họa dữ liệu có thể phân tách một cách tuyến tính
Hình 2: Lề của một siêu phẳng
9
Hình 3: Siêu phẳng có lề lớn
trong đó W là vector trọng số W={w1, w2, …, wn}; và n là số lượng các
thuộc tính mô tả tập dữ liệu D; b là một số thực được gọi là độ lệch. Trong
trường hợp đơn giản nhất, ta xét số lượng thuộc tính là 2 ký hiệu là A1 và A2.
Khi đó phần tử dữ liệu X được biểu diễn bằng X=(x1, x2) với x1, x2 là giá trị
tương ứng của thuộc tính A1 và A2. Nếu ta coi b cũng là một trọng số thì công
thức (1.1) sẽ được có dạng:
w0 + w1x1 + w2x2 = 0
(1.2)
Khi đó các điểm nằm phía trên siêu phẳng sẽ thỏa mãn điều kiện:
w0 + w1x1 + w2x2 > 0
(1.3)
Các điểm nằm phía dưới siêu phẳng sẽ thỏa mãn điều kiện:
w0 + w1x1 + w2x2 < 0
(1.4)
Hai siêu phẳng tiếp tuyến với dữ liệu và song song với siêu phẳng phân
lớp h có thể được biểu diễn bằng công thức:
H1 : w0 + w1x1 + w2x2 +1, với yi = +1
(1.5)
H2 : w0 + w1x1 + w2x2 - 1, với yi = -1
(1.6)
Do đó, nói một cách chính xác hơn thì các điểm ở trên siêu phẳng H1 sẽ
được phân vào lớp +1 và các điểm ở dưới siêu phẳng H2 sẽ được phân vào lớp 1. Bằng cách nhân cả 2 vế của 2 bất đẳng thức (1.5) và (1.6) với yi ta được bất
đẳng thức chung:
yi (w0 + w1x1 + w2x2) 1, với i
(1.7)
10
Để xác định 2 siêu phẳng H1 và H2 ta chỉ cần dựa vào các phần tử dữ liệu
huấn luyện nằm trên 2 siêu phẳng (các phần tử dữ liệu thỏa mãn yi (w0 + w1x1 +
w2x2) = 1).
Những phẩn tử dữ liệu này được gọi là các vector hỗ trợ (support vector).
Chúng cũng chính là các phần tử dữ liệu nằm gần siêu phẳng phân chia h nhất.
Hình 4 minh họa các vector hỗ trợ (chúng là các hình được bôi đen). Trong
trường hợp tổng quát thì các vector hỗ trợ chính là các phần tử khó phân lớp
nhất nhưng lại cung cấp nhiều thông tin nhất cho việc phân lớp (giúp ta xác định
các siêu phẳng tiếp tuyến). Từ công thức (1.7) ở trên chúng ta có thể suy ra công
thức tính độ lớn của lề. Khoảng cách từ một điểm bất kỳ từ siêu phẳng H1 đến
siêu phẳng phân lớp h là
1
, trong đó W là chuẩn Euclidean của W:
W
W W W w12 w22 ... wn2
(1.8)
Tương tự khoảng cách từ một điểm bất kỳ từ siêu phẳng H2 đến siêu
phẳng phân lớp h cũng là
1
2
, và độ lớn của lề sẽ là
. Việc tìm ra siêu phẳng
W
W
có lề lớn nhất người ta dựa vào việc giải công thức (1.7), việc này có thể giải
quyết bằng bài toán tối ưu toàn phương lồi (convex quadratic optimization). Chi
tiết cách giải bài toán này sẽ không được trình bày trong khuôn khổ cuốn giáo
trình này.
Hình 4: Minh họa vector hỗ trợ
Với SVM, sau khi tìm được siêu phẳng có lề lớn nhất MMH, siêu phẳng
này có thể được viết lại dựa trên công thức Lagrangian như sau:
11
l
f X T yi i X i X T b0
(1.9)
i 1
trong đó yi là nhãn của các vector hỗ trợ Xi; XT là một phần tử dữ liệu kiểm tra;
i và b0 là các số thực, chúng là các tham số được xác định thông qua quá trình
tối ưu; và l là số lượng các vector hỗ trợ.
Cho một phần tử dữ liệu mới XT nếu sign(f(XT)) =+1 thì phần tử XT nằm
trên siêu phẳng MMH, SVM sẽ dự đoán nhãn của XT là +1, ngược lại nó sẽ dự
đoán XT thuộc lớp -1.
1.1.2. Tách phi tuyến
Trong các bài toán phân lớp thực tế có thể gặp nhiều miền dữ liệu không
thể phân tách một cách tuyến tính như trong hình 5. Với ví dụ minh họa này, ta
thấy không thể tồn tại một siêu phẳng nào có thể phân tách tập dữ liệu (được ký
hiệu bằng các hình tròn rỗng và hình tròn được tô đen) thành 2 nửa. Tuy nhiên
SVM có thể mở rộng để phân lớp được các dữ liệu không thể phân tách tuyến
tính (linearly inseparable data hay non-linearly separable data) hay gọi đơn giản
là dữ liệu không tuyến tính (nonlinear data) hay dữ liệu phi tuyến. SVM mở
rộng này có khả năng tìm được ranh rới (boundary) phân lớp, hay siêu diện
không tuyến tính (nonlinear hypersurface) (hay siêu diện phi tuyến) từ không
gian dữ liệu đầu vào.
SVM được mở rộng để xử lý dữ liệu phi tuyến theo 2 bước chính như sau:
1. Bước đầu tiên chúng ta chuyển không gian dữ liệu đầu vào thành một
không gian dữ liệu có số chiều lớn hơn bằng một ánh xạ không tuyến tính (ánh
xạ phi tuyến). Có rất nhiều ánh xạ phi tuyến có thể được sử dụng trong bước này
(sẽ được trình bày ở dưới).
2. Khi dữ liệu đã được chuyển sang không gian có số chiều lớn hơn, bước
tiếp theo ta tìm siêu phẳng tuyến tính để phân lớp dữ liệu trên không gian mới.
Để hiểu hơn về phương pháp xử lý của SVM ta có thể xem minh họa
trong hình 6, trong đó hình 6 a) mô tả không của gian dữ liệu đầu vào (nó được
biểu diễn bằng không gian 2 chiều), rõ ràng với phân bố dữ liệu như thế này thì
ta không thể dùng một siêu phẳng để phân tách 2 lớp ra thành 2 phần độc lập
nhau. Sau khi sử dụng hàm ánh xạ, không gian dữ liệu đầu vào sẽ được chuyển
sang không gian mới có số chiều cao hơn (3 chiều), đặc biệt trong không gian dữ
liệu mới này ta có thể sử dụng một siêu phẳng để phân tách dữ liệu thành 2 lớp.
12
Hình 5: Trường hợp dữ liệu không thể phân tách bằng một siêu phẳng
a) Không gian ban đầu (2 chiều)
b) Không gian mới (3 chiều)
Hình 6: Hàm ánh xạ từ dữ liệu phi tuyến sang dữ liệu tuyến tính
Ví dụ trong một miền dữ liệu 3 chiều, một phần tử dữ liệu sẽ được biểu
diễn bằng vector X=(x1, x2, x3), sau khi sử dụng một hàm ánh xạ sang không
gian mới có 6 chiều, phần tử X sẽ biến thành Z, sao cho Z=ô(X)=(x1, x2, x3,
x1*x1, x1*x2, x1*x3). Giả sử sau khi biến đổi, dữ liệu trong không gian mới sẽ có
thể phân lớp tuyến tính, và ta có thể dùng một siêu phẳng để phân tách dữ liệu
thành 2 nửa, khi đó siêu phẳng h sẽ được biểu diễn bằng công thức
h(Z)=W*Z+b, trong đó W là vector trọng số và Z là vector biểu diễn dữ liệu
trong không gian mới và b là một số thực giống như công thức biểu diễn siêu
phẳng 1. Khi diễn giải công thức này ra ta có công thức biểu diễn siêu phẳng là:
h(Z) = w1x1 + w2x2 + w3x3 + w4x1x1 + w5x1x2 + w6x1x3 + b
= w1z1 + w2z2 + w3z3 + w4z4 + w5z5 + w6z6 + b
13
Khi mở rộng thêm sức mạnh của SVM, lại có thêm vấn đề cần giải quyết.
Cụ thể là độ phức tạp thuật toán sẽ tăng lên bởi vì ta phải sử dụng thêm hàm ánh
xạ. Rất may là tồn tại giải pháp cho vấn đề này, chú ý công thức (1.8), ta phải
thực hiện phép nhân tích vô hướng XiXT (trong đó Xi và XT đều là các vector
trong không gian dữ liệu ban đầu) hay viết XiXj cho đơn giản:
X i X j xik x jk , trong đó xik là các giá trị biểu diễn phần tử dữ liệu Xi và xjk
k
là các giá trị biểu diễn phần tử dữ liệu Xj.
Khi chuyển sang không gian mới, tích vô hướng trên sẽ được tính toán
bằng (Xi)(Xj) trong đó là hàm ánh xạ. Tuy nhiên, một mẹo toán học rất
hay ở đây là, thay vì tính tích vô hướng trên dữ liệu ở không gian dữ liệu mới, ta
sử dụng thì ta có thể sử dụng một hàm nhân (kernel function) K cho kết quả
tương tự như sau:
K X i , X j ( X i )X j
(1.10)
Bằng cách sử dụng hàm tương đương này, thì ở bất kỳ đâu xuất hiện
(Xi)(Xj) thì ta thay thế bằng hàm K(Xi,Xj). Do đó, việc tính toán về bản chất
sẽ được thực hiện trên không gian dữ liệu ban đầu – không gian có khả năng có
số chiều nhỏ hơn nhiều. Sau khi sử dụng hàm nhân thay thế, ta có thể sử dụng
thuật toán tìm kiếm siêu phẳng phân lớp mà cũng không cần quan tâm đến ánh
xạ biến đổi cụ thể là gì. Các đặc điểm của hàm nhân có thể sử dụng để thay thế
hàm nhân tích vô hướng đã được nghiên cứu. Dưới đây xin trình bày một số
hàm nhân phổ biến, nó thường được cài đặt trong các gói phần mềm cài đặt
thuật toán SVM (chẳng hạn như thư viện libSVM [4], hay thư viện Weka[8]):
1. Hàm nhân đa thức cấp h:
K X i , X j X i X j 1
h
(1.11)
2. Hàm nhân Gaussian radial cơ bản:
K X i , X j e
xi x j
2
/ 2 2
(1.12)
3. Hàm nhân đa sigmoid
K X i , X j tan(X i X j )
(1.13)
14
Một số hàm nhân khác ta có thể tham khảo và thử nghiệm từ bộ phần
mềm cài đặt thuật toán SVM có tên là Accord.NET1.
Vấn đề thứ 2 là liệu có tồn tại một hàm nhân nào có thể biến các tập dữ
liệu phi tuyến bất kỳ sang không gian dữ liệu tuyến tính. Câu trả lời có lẽ là
không, tùy vào từng loại dữ liệu mà sẽ có một hoặc một số hàm nhân phù hợp.
Trong nhiều trường hợp ta phải chọn thử nhiều hàm nhân khác nhau để chọn ra
hàm nhân phù hợp với tập dữ liệu đang xử lý nhất.
1.1.3. Phân lớp đa lớp với SVM
Như ta đã nói ở trên thuật toán SVM chỉ hoạt động với dữ liệu có 2 lớp,
trong thực tế số lượng lớp của dữ liệu có thể rất lớn. Tuy nhiên cũng đã có giải
pháp để mở rộng SVM cho bài toán phân lớp có nhiều lớp.
Bài toán phân đa lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần
cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong
những phương pháp cải tiến đó là sử dụng thuật toán 1-against-all [10]. ý tưởng
cơ bản là chuyển bài toán phân lớp nhiều lớp thành nhiều bài toán phân lớp nhị
phân như sau:
• Giả sử tập dữ liệu mẫu (x1,y1),..., (xm,ym) với xi là một vector n chiều và
yi Y là nhãn lớp được gán cho vector xi (có m nhãn lớp khác nhau)
• Biến đổi tập Y ban đầu thành m tập có hai lớp con Zi={yi,{Y - yi}}
• Áp dụng SVM phân lớp nhị phân cơ bản với m tập Zi để xây dựng siêu
phẳng cho phân lớp này. Như vậy ta sẽ có m bộ phân lớp nhị phân.
Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân
lớp đa lớp mở rộng với SVM.
Nhược điểm chính của phương pháp này, đôi khi được gọi là winnertake-all, chính là đặc điểm heuristic của nó. Những máy phân lớp nhị phân được
sử dụng huấn luyện trên các lớp khác nhau, và như vậy là không rõ ràng khi so
sánh các đầu ra giá trị thực của chúng cho dù có chuyển đổi giá trị thực thành
xác suất lớp.
1
http://accord-net.origo.ethz.ch/
15
1.2. Phương pháp kNN
Tư tưởng chung của các thuật toán học máy có giám sát là thuật toán sẽ
phân tích dữ liệu huấn luyện để tìm ra mô hình biểu diễn dữ liệu, sau đó ta có
thể dùng một tập dữ liệu khác để kiểm thử độ chính xác của thuật toán như minh
họa trên hình 7. Như mô tả ở trên hình, tập dữ liệu huấn luyện sẽ được sử dụng
để tạo ra mô hình (trong quá trình huấn luyện thuật toán). Yêu cầu trong thực tế
là việc phân lớp vẫn phải làm việc mà không hề tồn tại giai đoạn học để tạo ra
mô hình, mà nó chỉ đơn thuần là sử dụng tập dữ liệu huấn luyện phục vụ cho
giai đoạn dự đoán nhãn của dữ liệu sau này. Những thuật toán này được liệt kê
vào lớp thuật toán lười học (lazy learner). Đặc điểm của lớp thuật toán này là nó
không tốn thời gian để học, tuy nhiên giai đoạn phân lớp của nó lại bị “trả giá”.
Thông thường các thuật toán lười học sẽ cần phải tính toán nhiều trong quá trình
phân lớp. Có thể đây là nhược điểm lớn nhất của lớp thuật toán lười học, vì khi
tập dữ liệu huấn luyện là rất lớn thì chi phí khi phân lớp sẽ càng cao.
Hình 7: Các bước trong mô hình học máy có giám sát
Tuy nhiên một trong những ưu điểm của việc “lười học” là nó buộc phải
xử lý thêm một số bước nhỏ với dữ liệu. Cụ thể là với các thuật toán cần phải
huấn luyện thì khi dữ liệu huấn luyện thay đổi, thì ta phải huấn luyện lại thuật
toán để tạo ra mô hình mới tương ứng với dữ liệu mới. Tuy nhiên với thuật toán
lười học thì cho dù dữ liệu huấn luyện có thay đổi thì cũng không phải mất công
huấn luyện.
Một trong những thuật toán thuộc lớp thuật toán lười học là thuật toán k
người láng giềng gần nhất (k nearest neighbors) viết tắt là kNN và thuật toán
case-based reasoning. Trong luận văn này tôi sẽ trình bày chi tiết thuật toán
kNN.
16
Khi đưa một phần tử dữ liệu mới, thuật toán sẽ tìm k phần tử dữ liệu láng
giềng gần nó nhất (k nearest neighbors), sau đó dựa trên nhãn (lớp) của các láng
giềng này mà nó sẽ quyết định nhãn (lớp) của phần tử dữ liệu mới là thuộc lớp
nào. Trường hợp đơn giản nhất là ta chỉ tìm một phần tử gần phần tử mới nhất,
nhãn của phần tử mới sẽ được gán là nhãn của phần tử tìm được. Đề tìm các
phần tử láng giềng gần nhất ta cần định nghĩa độ đo nào đó, một trong các độ đo
điển hình là độ đo khoảng cách Euclide. Giả sử có 2 phần tử dữ liệu X1=(x11, x12,
…, x1n) và X2=(x21, x22, …, x2n), độ đo khoảng cách Euclide được tính bằng
công thức:
dist X 1 , X 2
n
x
i 1
1i
x 2i
2
(1.14)
Từ công thức (1.14), ta nhận thấy nếu các thuộc tính khác nhau có miền
giá trị khác nhau thì có thể độ chính xác của độ đo sẽ không chính xác. Ví dụ
thuộc tính thu nhập có miền giá trị lớn hơn nhiều so với thuộc tính tuổi, hay
thuộc tính số lượng con. Khi đó chỉ cần một độ chênh lệch nhỏ của thuộc tính
thu nhập cũng làm thay đổi giả trị của độ đo khoảng cách. Để làm cho các thuộc
tính có “ảnh hưởng” ngang nhau đến độ đo khoảng cách, ta có thể chuẩn hóa dữ
liệu các thuộc tính sử dụng công thức sau để chuyển giá trị v của một thuộc tính
A sang giá trị v’ có miền giá trị nằm trong khoảng [0, 1]:
v'
v min A
max A min A
(1.15)
trong đó minA và maxA là giá trị nhỏ nhất và lớn nhất của thuộc tính A.
Trường hợp thuộc tính biểu diễn dữ liệu không phải là dữ liệu liên tục mà
là dữ liệu rời rạc (chẳng hạn thuộc tính màu nó có miền giá trị là một danh sách
các loại màu). Khi đó ta có thể giải quyết như sau: giả sử x1i và x2i là giá trị rời
rạc (biểu diễn thuộc tính A) của 2 phần tử dữ liệu X1 và X2, thì:
0 khi x1i x2i
x1i x2i
1 khi x1i x2i
(1.16)
Rõ ràng với công thức này thì ta có thể áp dụng công thức (1.14) với dữ
liệu rời rạc. Trong nhiều trường hợp ta cũng có thể sử dụng độ đo tương tự (thay
vì độ đo khoảng cách) để tìm ra các phần tử láng giềng gần nhất.
17
Bây giờ ta sẽ nghiên cứu là xác định giá trị k như thế nào để ta có thể thu
được kết quả phân lớp tốt nhất. Với trường hợp đơn giản nhất thì k=1 (khi đó
thuật toán kNN sẽ được ký hiệu là 1-NN). Khi xác định được phần tử dữ liệu
gần phần tử dữ liệu cần phần lớp nhất thì bài toán xác định nhãn lại rất đơn giản
vì nó chính là nhãn của phần tử gần nhất vừa tìm được. Tuy nhiên có một vấn đề
khi ta chỉ dựa vào 1 phần tử láng giềng đề quyết định nhãn của phần tử dữ liệu
cần phân lớp: đó là trường hợp phần tử láng giềng gần nó nhất lại là phần tử
nhiễu (noise), khi đó nhãn thu được sẽ không chính xác. Đề giải quyết vấn đề
này thì ta có thể dùng các phương pháp để lọc các dữ liệu nhiễu, thậm chí là các
thuộc tính nhiễu đi.
Trên thực tế thuật toán mở rộng của thuật toán 1-NN được sử dụng rộng
hơn, đó là tăng giá trị của k lên để tạo khả năng ra quyết định dựa trên nhiều
phần tử dữ liệu. Thông thường các giá trị của k được chọn sẽ là các giá trị lẻ (để
tránh trường hợp các láng giềng của phần tử dữ liệu cần phân lớp lại thuộc 2 lớp
khác nhau, và số lượng các láng giềng trong mỗi lớp lại bằng nhau). Với k=3 và
có 3 phần tử dữ liệu láng giềng gần nhất có nhãn là {A, B, A}, khi đó ta có thể
kết luận là phần tử dữ liệu cần phần lớp là thuộc lớp A. Với k=5, các phần tử
láng giềng có nhãn là {A, B, A, B, B}, thì ta có thể kết luận là phần tử dữ liệu
mới thuộc lớp B. Tuy nhiên việc phân lớp dựa vào việc đếm số nhãn như thế này
sẽ có vấn đề. Cụ thể với trường hợp k=5, và giả sử độ tương tự tương ứng của 5
láng giềng này là {0.98, 0.67, 0.56, 0.34, 0.23}. Ta có thể nhận thấy các phần tử
láng giềng 4 và 5 có độ tương tự rất thấp, do đó nếu ta dựa vào các phần tử dữ
liệu này để kết luận nhãn của phần tử dữ liệu mới thuộc lớp A sẽ không tin cậy.
Do đó người ta đề xuất là sử dụng trọng số cho nhãn của các phần tử láng
giềng, chúng ta có thuật toán mới có tên là: k người láng giềng gần nhất có đánh
trọng số khoảng cách (distance-weighted kNN). Cụ thể nhãn của k láng giềng sẽ
được gán trọng số, lớp có tổng trọng số lớn nhất sẽ được dùng để gán cho phần
tử cần phân lớp. Trọng số đơn giản chính là độ tương tự giữa phần từ dữ liệu cần
phân lớp X với phần tử láng giềng Xi là sim(X, Xi). Với ví dụ k=5 ở trên thì tổng
trọng số của các láng giềng thuộc lớp A là 0.98+0.56=1.54, và tổng trọng số các
nhãn thuộc lớp B là 0.67 + 0.34 + 0.23 = 1.24, kết quả này cho ta quyết định là
phần tử cần phân lớp thuộc lớp A. Một số công thức tính trọng số khác là: 1/(1sim(X, Xi)) hay 1/(1-sim(X, Xi))2. Các công thức này đều có đặc điểm chung là
giá trị của chúng sẽ tăng lên khi độ tương tự giữa chúng tăng lên. Tuy có rất
18
nhiều đề xuất cải tiến so với thuật toán 1-NN tuy nhiên trong nhiều trường hợp
thì 1-NN vẫn tỏ ra là có chất lượng tốt hơn cả.
Một nhược điểm của thuật toán kNN là rất chậm khi kích thước của tập
dữ liệu huấn luyện D tăng lên. Ta phải sử dụng |D| phép so sánh để tìm ra các
láng giềng gần nhất, hay độ phức tạp của nó là O(n). Có rất nhiều đề xuất để làm
giảm độ phức tạp của thuật toán, một số phương pháp được liệt kê ở dưới:
• Sắp xếp tập dữ liệu D đầu vào và tổ chức nó dưới dạng 1 cây tìm kiếm,
khi đó độ phức tạp của nó giảm xuống còn O(log(n)).
• Sử dụng các phương pháp song song hóa.
• Lấy mẫu tập dữ liệu D để tạo một tập dữ liệu D có kích thước nhỏ hơn.
• Sử dụng 1 phần độ đo khoảng cách (partial distance), việc tính toán
khoảng cách chỉ dựa trên một tập con các thuộc tính, nếu giá trị thu được lớn
hơn 1 ngưỡng nào đó thì ta sẽ không tính toán tiếp phần tử dữ liệu hiện tại nữa
(vì nó có khoảng cách quá xa), và phần tử dữ liệu tiếp theo sẽ được xử lý.
• Phương pháp hiệu chỉnh (editing): chúng ta loại bỏ các phần tử dữ liệu
(đã được chứng minh) là vô nghĩa trong quá trình phân lớp. Phương pháp này
còn có các tên khác là tỉa (pruning) hay cô đọng hóa (condensing) vì chúng làm
giảm số lượng phần tử dữ liệu trong tập huấn luyện.
1.3. So sánh SVM với kNN
Trong ngành nghiên cứu máy học thì SVM và kNN là hai thuật toán rất
phổ biến và có được sự quan tâm nhiều nhất trong quá trình phát triển ngành.
Tuy nhiên câu hỏi đặt ra là hai thuật toán này có đặc điểm gì giống và khác
nhau? Ưu điểm từng phương pháp là gì và có thể áp dụng trong những bài toán
cụ thể như thế nào.
Trong luận văn này, tôi sẽ kết hợp những phân tích trong bài viết [9] từ đó
so sánh chi tiết hai thuật toán SVM và kNN:
Sự giống nhau:
Hai thuật toán phân lớp trên đều có điểm chung là yêu cầu dữ liệu phân
lớp phải được biểu diễn dưới dạng vector đặc trưng.
- Xem thêm -