ĐẠ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
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

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

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

2
, y
2
), … , (X
|D|
,
y
|D|
), trong đó X
i
là các phần tử dữ liệu và y
i
là nhãn tương ứng của nó. Giá trị
của y
i
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 A
1
và A
2
, 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

trong đó W là vector trọng số W={w
1
, w
2
, …, w
n
}; 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à A
1
và A
2
.
Khi đó phần tử dữ liệu X được biểu diễn bằng X=(x
1
, x
2
) với x
1
, x
2
là giá trị
tương ứng của thuộc tính A
1
và A
2
. 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:
w
0

x
2
< 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:
H
1
: w
0
+ w
1
x
1
+ w
2
x
2
 +1, với y
i
= +1 (1.5)
H
2
: w
0
+ w
1
x
1
+ w
2
Để xác định 2 siêu phẳng H
1
và H
2
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 y
i
(w
0
+ w
1
x
1
+
w
2
x
2
) = 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 H
1
đến

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
i
T
iii
T
bXXyXf
1
0

(1.9)
trong đó y
i
là nhãn của các vector hỗ trợ X
i
; X
T
là một phần tử dữ liệu kiểm tra;


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=(x
1
, x
2
, x

1 +
w
2
x
2 +
w
3
x
3 +
w
4
x
1
x
1 +
w
5
x
1
x
2 +
w
6
x
1
x
3 +
b
= w
1

thực hiện phép nhân tích vô hướng X
i
X
T
(trong đó X
i
và X
T
đều là các vector
trong không gian dữ liệu ban đầu) hay viết X
i
X
j
cho đơn giản:


k
jkikji
xxXX
, trong đó x
ik
là các giá trị biểu diễn phần tử dữ liệu X
i
và x
jk

là các giá trị biểu diễn phần tử dữ liệu X
j
.
Khi chuyển sang không gian mới, tích vô hướng trên sẽ được tính toán


   
h
jiji
XXXXK 1, 
(1.11)
2. Hàm nhân Gaussian radial cơ bản:

 
2
2
2/
,

ji
xx
ji
eXXK


(1.12)
3. Hàm nhân đa sigmoid

 
)tan(,


jiji
XXXXK
(1.13)

) với x
i
là một vector n chiều và
y
i
Y là nhãn lớp được gán cho vector x
i
(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 Z
i
={y
i
,{Y - y
i
}}
• Áp dụng SVM phân lớp nhị phân cơ bản với m tập Z
i
để 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à winner-
take-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


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 X
1
=(x
11
, x
12
,
…, x
1n
) và X
2
=(x
21
, x
22
, …, x
2n
), độ đo khoảng cách Euclide được tính bằng
công thức:
   

(1.15)
trong đó min
A
và max
A
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ử x
1i
và x
2i
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 X
1
và X
2
, thì:






ii
ii
ii
xxkhi
xxkhi
xx

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 X
i
là sim(X, X
i
). 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/(1-
sim(X, X
i
)) hay 1/(1-sim(X, X
i
))
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
19
Sự khác biệt:
Khác biệt về tư tưởng đó là trong khi SVM được thiết kế với tư tưởng là
dùng cho “học bán giám sát” còn kNN được thiết kế theo tư tưởng “lười học”
nhằm tăng thêm tính tự động trong quá trình học máy.
Thuật toán kNN phải sử dụng các ước lượng tham số và ngưỡng tối ưu
khi phân lớp văn bản, trong khi thuật toán SVM có thể tự xác định các tham số
tối ưu này trong quá trình thực hiện thuật toán.
Xét về mặt thời gian, kNN có thời gian phân lớp dữ liệu nhanh hơn so với
SVM vì đơn giản là SVM cần phải thực hiện thêm giai đoạn huấn luyện.
Xét về mặt chất lượng phân lớp thì ngược lại SVM được cho là có hiệu
suất phân lớp cao hơn, tỉ lệ lỗi thấp hơn so với phân lớp kNN, nhất là trong phân
lớp văn bản.
Trong bài báo này [9], tác giả không quan tâm đến không có khả năng dự
đoán nhưng nó vẫn còn giá trị nhất định. Với SVM có thể dự đoán 72% dữ liệu
ẩn, ngược lại với kNN chỉ có thể dự đoán khoảng 8% dữ liệu dạng ẩn.
20
Chương 2: Phương pháp SVM-kNN phân lớp văn bản
Chúng ta xem xét vector đặc trưng trong công việc phân lớp có kích thước
giống nhau. Tiếp cận theo cách này khá linh hoạt, và cho phép phân lớp văn bản
dựa trên các thuộc tính đặc biệt của văn bản, trong một khuôn khổ đồng nhất.
Trong khi phân lớp k-láng giềng gần nhất là tự nhiên trong quá trình cài đặt,
nhưng nó bị các vấn đề về sai số cao quá, trong trường hợp hạn chế số lượng
mẫu. Ngoài ra, người ta có thể sử dụng phương pháp SVM, tuy nhiên SVM


phân lớp. Để cải tiến biên ta dùng thuật toán kNN. Một số câu hỏi đặt ra, có rất
nhiều thuật toán sao không dùng mà lại dùng kNN? Bởi vì trong quá trình quyết
định thì thuật toán kNN chỉ liên quan đến số lượng nhỏ các hàng xóm gần nó
nhất, do đó việc áp dụng phương pháp này có thể tránh được sự mất cân bằng
giữa các mẫu.
Mặt khác, kNN chủ yếu phụ thuộc vào số lượng giới hạn các hàng xóm
gần nhất không phải xung quanh một biên quyết định, vì vậy nó phù hợp với
việc phân lớp trong trường hợp tập hợp các mẫu có biên giao nhau hay chồng
chéo nhau giữa các mẫu.
Từ những ưu và nhược điểm của hai thuật toán SVM và kNN, Hao Zhang
và cộng sự [5] đã đề xuất một phương pháp kết hợp hai thuật toán trên. Sự kết
hợp này là công trình điển hình sớm nhất về phương pháp SVM-kNN. Ý tưởng
cơ bản của phương pháp này là tìm các hàng xóm gần với mẫu truy vấn và huấn
luyện một máy vector hỗ trợ cục bộ. Máy vector hỗ trợ cục bộ này duy trì hàm
khoảng cách trên tập các hàng xóm. Hao Zhang và cộng sự đã chứng minh được
rằng phương pháp này có thể áp dụng với tập dữ liệu lớn và đa lớp với kết quả
tốt hơn so với trường hợp khi chỉ áp dụng SVM hay kNN.
Sau đó, Kunlun Li và cộng sự [7] đã đề xuất một phương pháp phân lớp
SVM-kNN dựa trên học bán giám sát nhằm cải tiến thuật toán SVM bằng cách
tận dụng những ưu điểm của thuật toán kNN đã nêu ở trên. Phương pháp này
kết hợp thuật toán SVM và kNN, trong đó có sử dụng thông tin từ dữ liệu chưa
gán nhãn – nhưng thông tin này có thể giúp khôi phục các biên quyết định đúng
cho việc phân lớp. Trong thuật toán SVM, các vector hỗ trợ quyết định các biên
quyết định một cách trực tiếp, trong khi các vector biên có thể là những ứng viên
tốt cho vị trí vector hỗ trợ (hình 8). Do vậy, phương pháp này sử dụng các vector
biên để khắc phục các biên quyết định trong mỗi lần lặp. Thuật toán kNN được
dùng để gán nhãn các vector biên. Những vector biên cuối cùng được trộn với
các ví dụ huấn luyện khởi tạo để cải tiến độ chính xác của phân lớp. Phương
pháp này hiệu quả hơn so với phương pháp của Hao Zhang và cộng sự [5]. Do

Như vậy có được những vector biên đã được gán nhãn bởi bộ phận SVM yếu.
23
Bước thứ hai: Tiếp tục sử dụng tập các ví dụ huấn luyện ban đầu làm tập
huấn luyện để tạo ra bộ phân lớp dựa trên thuật toán kNN. Những vector biên
được lấy ra từ bước đầu tiên được coi như là tập kiểm tra cho bộ phân lớp được
tạo ra bởi thuật toán kNN. Các nhãn mới do kNN tạo ra sẽ được gán lại cho các
vector biên đó.
Cuối cùng: Những vector biên và nhãn mới này được đặt vào tập huấn
luyện ban đầu để làm giàu số lượng các ví dụ huấn luyện và sau đó tiếp tục huấn
luyện sử dụng SVM. Vòng lặp này kết thúc khi số lượng các ví dụ huấn luyện là
k lần toàn bộ tập dữ liệu.

Hình 9: Mô hình đề xuất bởi Kunlun Li và cộng sự [7]
Giả sử tập dữ liệu ban đầu là X gồm n ví dụ, trong đó có l ví dụ đã được
gán nhãn (l<<n) và u = n-m ví dụ chưa được gán nhãn (l < u). Gọi L  X là tập
ví dụ đã gán nhãn (||L|| = 1), U  X là tập ví dụ chưa gán nhãn (||U||=u). Giả sử
xét bài toán phân lớp hai lớp (A và B) và tập L chứa các ví dụ thuộc A và B.

Thuật toán SVM – KNN
Bước 1: Dùng tập dữ liệu có nhãn L làm ví dụ huấn luyện để xây dựng
một phân lớp yếu SVM
1

Bước 2: Sử dụng SVM
1
để dự đoán lớp của tất cả dữ liệu trong U, sau đó
chọn ra 2s (1≤s≤5) ví dụ làm các vector biên.