x: ờơ ỉ d ạ i h ọ c ọ u ó c g ia h à n ộ i
TRƯỜNG ĐAI HOC CÔNG NGHÊ
« * •
NGUYỀN HOÀI NAM
MỘT SỐ KỸ THUẬT VECTOR TỤA (SVM) TRONG
KHAI PHÁ Dữ LIÊU VÀ ỨNG DƯNG VÀO NHẢN DANG
• • 0 ề
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ĩ
NGƯỜI HƯỚNG DẢN KHOA HỌC : PGS.TSKH. Bùi Công Cường
■JAi HỌC QUỐC GIA HÀ NÔI
; rung tâm thOng tin thư viện
1 Vr LOẬ . . A S A L _
Hà Nội - 2008
3
LỜI CAM ĐOAN 1
LỜI CẢM ƠN 2
CÁC TỪ VIẾT TẮT, THUẬT NGỮ 6
CÁC HÌNH V Ẽ 6
CHƯƠNG 1 : MỘT SỐ KIẾN THÚC CHUẨN BỊ
10
1.1 Bài toán tối ưu 10
1.1.1 Bài toán qui hoạch tuyến tính 10
/. ỉ. ỉ. ỉ Dạng chính tắc
1Ị
Ị. ỉ. ỉ.2 Dạng chaân tắc / /
1.1.2 Qui hoạch tuyến tính đổi ngẫu 12
2.3.1 Cấu trúc của một hệ thống khai phá dừ liệu 32
2.3. ỉ. ì X ử lý dữ liệu 32
2.3.2 Các bài toán chính trong khai phá dữ liệu 33
2.3.2.1 Phân lớp và phán cụm 33
23.2.2 Tim ra các luật 34
2.3.3 Một số phương pháp tính dùng trong khai phá dừ liệu 35
2.4 Sự giống và khác nhau giữa khai phá dữ liệu và máy học 35
CHU ONG 3 36
HÀM HẠT NHÂN 36
3.1 Tích vô hướng các đặc trưng 36
3.1.1 Đặc trưng đơn 36
3.1.2 Hàm hạt n h â n 37
3.1.3 Hàm hạt nhân đa thức 37
3.2 Biểu diễn sự đồng dạng trong không gian tuyến tính 39
3.2.1 Các hạt nhân xác định dương 39
3.2.2 Tái lập ánh xạ hạt nhân 40
3.2.3 Tái lập không gian hạt nhân Hilbert 42
3.2.4 Ánh xạ hạt nhân Mercer 43
3.3 Các hạt nhân thưòng đưọc sử dụng 45
4
CHƯƠNG 4 46
PHƯƠNG PHÁP VECTOR TỰA (SVM) 46
4.1 Phân chia bằng siêu phắng
.
46
4.2 Vai trò cùa lề trong siêu phẳng 47
4.3 Siêu phẳng tối ưu - Phân lóp tuyến tính
6.2 Xây dựng hệ thống nhận dạng 74
KÉT LUẬN 76
TÀI LIỆU THAM KH ẢO 77
5
(ORL Cambridge Olivetti Research Lab
PCA Principal Components Analysis
1RBF Radial Basic Function
SVM Support Vector Machines
v c Vapnik Chervonenkis
CÁC HÌNH VẼ
Hình 1.1 Phân lớp trong đơn giản 17
Hình 1.2 : Hai hàm huấn luyện cho kết quả khác nhau trên dữ liệu kiểm tra
18
Hình : 1.3 v c của các đường thẳng có hướng
20
trong không gian 2 chiều (R2) là 3 20
Hình 1.4 Ý nghĩa hình học của PC A 27
Hình 2.1 : Sơ đồ của Bloom 29
Hình 2.2 : Thuật toán học có thày : Cây quyết định, Mạng nơron, Vector tựa 31
Hình 2.3 : Thuật toán học không có thày : Phân cụm 31
Hình 3.1 Ví dụ về phân lớp nhị phân khi ánh xạ sang không gian đặc trưng 38
Hình 3.2 Minh hoạ mối liên hệ giữa ánh xạ đặc trưng với hạt nhân
40
Hình 4.1 Một siêu phẳng phân lớp các đối tượng thành hai lớp 46
Hình 4.2 Siêu phẳng dạng chính tắc 47
Hình 4.3 Vỉ dụ phân lớp trong không gian 2 chiều 48
Hình 4.4 : Ví dụ : Bằng cách ánh xạ không gian dữ liệu phi tuyến đầu vào
nằm một chỗ mà nó luôn được luân chuyển, bổ sung, cập nhật bởi người sử
dụng.
Với khối lượng thông tin lớn đến như vậy, liệu con người chúng ta có cảm
thấy quá tái, ngập chìm trong biên thông tin, không thế chọn lựa được những
thông tin quan trọng, gần với nhu cầu sử dụng của minh nhất. Điều đó có nghĩa
là chúng ta có quá nhiều thông tin, nhưng điều chúng ta thực sự cần đó là tri
thức,là kiến thức có được qua sự tổng hợp, phân tích, thống kê từ các kho thông
tin đó. Đe tìm ra được tri thức trong một kho thông tin khổng lồ thì chúng ta cần
phải có các phương pháp khái phá các lượng thông tin đó. Cùng chính vì lý do
đó mà trong thời gian gần đây, nghành khai phá dừ liệu được rất nhiều người
quan tâm và nghiên cứu.
Trong luận vãn tốt nghiệp cao học tại trường Đại học công nghệ - Đại học
quốc gia Hà Nội, tôi thực hiện đề tài “Một sổ kỹ thuật vector tựa (SVM) trong
khai phá dữ liệu và ứng dụng vào nhận dạng”
• Lý do chọn đề tài
Trong khai phá dừ liệu và học máy, yếu tố quyết định đến độ chính
xác trong các dự đoán là khả năng phân lớp tốt. Kỹ thuật vector tựa được
đánh giá là có khả năng phân lớp rất tốt, đặc biệt là các bài toán phân lớp
phi tuyến. Hiện nay đã có nhiều ứng dụng được xây dựng dựa trên kỹ
thuật vector tựa và cho kết quả rất khả quan.
• Mục đích, đổi tượng, phạm vi nghiên cứu
MỞ ĐẦU
8
Nghiên cứu phần cơ sở, lý thuvết chung của kv thuật vector tựa,
nghiên cứu một sổ kỹ thuật vector tựa cụ thể. Nghiên cửu các phương
pháp sử dụng kv thuật vector tựa trong nhận dạng mẫu, đặc biệt là nhận
dạng khuôn mặt. Đưa ra các giải pháp nhàm tăng cường tốc độ tính toán,
độ chính xác cho phương pháp vector tựa.
• Ý nghĩa khoa học và thực tiễn
Đây là một trong các phương pháp phân lớp hiện đại, có thể áp
Bài toán tối ưu là bài toán tìm nghiệm tối ưu (cho một hàm mục tiêu nào
đó) trono, số các phương án (nghiệm) chấp nhận thuộc miền V cho trước.
1.1.1 Bài toán qui hoạch tuyến tính
Qui hoạch tuyến tính là một trong những lớp bài toán tối ưu quan trọng
nhất vả được ứng dụng rồng rãi trong thực tiền. Qui hoạch tuyến tính là bài toán
tìm cực tiểu (hay cực đại) của một hàm tuyến tính f(x) trên một khúc lồi D c
Rn được xác định bơi một hệ phương trình hay bất phương trình tuyến tính cho
trước.
Bài toán này có dạng : Tìm các vector x= (x/, x2, sao cho
Z
n
CịXị —> m in
7=1
thoá mân các ràng buộc
Z
Clij X) < bị ,i = 1, ,171,
7 = 1
/ . u ij
*—‘j=1
X x >
'7 = 1
X—1«
(1.1)
> b ị, i = m l + 1, , 771! + m 2, (1.2)
y dụ Xj — bị ,i = i — m í + m 2 4-1, (1.3)
£—Jj =1
Xị > 0,7 = l, ,n,Xj < 0,j - 71! + 1, ,ní + n2 < n (1.4)
trong đó a;j,bj,Cj là các hằng số cho trước.
Trong bài toán trên, f được gọi là hàm mục tiêu, mỗi hệ thức (1.1) - (1.4)
được gọi là các ràng buộc. Mồi ràng buộc (1.1) - (1.3) gọi là một ràng buộc
V Xj > 0 , j = 1,2,
Ràng buộc chính dạng đẳng thức và mọi biến đều không âm
1.1.1.2 Dạng chuẩn tắc
Z
n
CjXj -> m in,
i=1
I ^ CLijXj > bị, i = 1,2, , m,
l Xj > 0 , j = 1,2,
Ràng buộc chính dạng bất đẳng thức > (đổi với bài toán min hoặc < đối
với bài toán max), và mọi biến đều không âm.
Đe viết bài toán gọn hơn, ta dùng các ký hiệu vector và ma trận sau:
11
an
a12
aĩn
' aij '
A =
a21 0-22 ••• a2n
, Aj=
Ũ2j
•
•
.aml
^m2 Q-mn.
.amj.
12
■ V
'<v
'*l'
hay max { f(x)=<c,x> : Ax < b, X > 0 }
1.1.2 Qui hoạch tuyến tính đối ngẫu.
Đổi ngẫu là một phương pháp mà ứng với mỗi bài toán qui hoạch tuyến
tính đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán quy hoạch
tuyến tính khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta
có thể thu được thông tin về lời giải của bài toán kia. Vì thế, đôi khi đế có được
lời giải của một bài toán tỏ ra khó khăn, thì việc chuvến sang bài toán đối ngẫu
giúp ta có được lời giải thuận tiện hơn nhiều. Hơn thế, khi phân tích đồng thời
cả hai bài toán gổc và bài toán đổi ngẫu ta có thể rút ra được các kết luận sâu
sắc cả về mặt toán học lẫn ý nghĩa thực tiễn.
Cho một qui hoạch tuyến tính, kỷ hiệu (P), dưới dạng chuẩn :
(P) f(x)=CiX|+c2X
2
+ . + cnxn —» min
với các ràng buộc
I aMxi + ai2x2+ + ainxn> bj , i=l,2, ,m
I Xj > 0 , j=l,2, ,n,
13
trong đó ay, bị, Cj là các hệ số cho trước; x=(xl,x2, ,xn) G Rn là vector
biến cần tìm.
Ta gọi đổi ngầu của (P) là qui hoạch tuyển tính, bài toán đối ngầu Q có
dạng :
g(y)=b,yi+b2y2+ + bnyn max
với các ràng buộc
a ,yj + aj2y2 + + ainyn<Cj , i=l,2, ,n
I Ỵj> 0 ,j=l,2, ,m,
■ S
ở đây y=(yi.y
2
v»yn) e Rn là vector biến cần tìm. Ta có nhận xét :
luyện ta cỏ thế tồng quát quá cho các dừ liệu chưa gắn nhãn, tức là ta dự
đoán X E X thuộc về lớp nào {+1,-1}
Với sự chuyển đổi dừ huấn luyện vào đê dự đoán đầu ra trong { + 1,-1} đã
làm cho bài toán trở nên đơn giản hơn nhiều. Do vậy chúng ta cần có các
phép biến đồi dừ liệu của tập dừ liệu huấn luyện
Xét phép biến đổi
k : X X X -» E
(.x ,x ') *->/c(x,x')
với hai mẫu X v à x ’ qua phép biển đổi ta có sổ thực thể hiện sự liên quan
của X và x \ với k là đổi xứng (k(x,x’)=k(x’,x) với mọi x,x’G M) thì k
được gọi là một hạt nhân.
1.2.2 Không gian hữu hạn chiều
Xét li, V 0. Tích trực tiếp của IL v ằ V :
XLxV= {(u,v)\u 6 ĩl,v £ V]
Trong trường hợp V. — V — IRn, ta xét tích vô hướng của hai vector
X = (xvx2
xn) Vày = (yv y2,-,yn) là :
1.2 Biểu diễn dữ liêu
= f [ * ,
i= 1
< x ,y> = > [Xị.yi
15
về mặt hình học, tích vô hướng của hai vector chính là cosine của góc tạo
thành của hai vector đó. Dựa vào đó ta có thể tính được chuẩn của vector* theo
công thức sau :
||x|| = v < x.x >
1.2.3 Không gian đặc trưng
Việc chuyển được không gian đặc trưng lên một không gian ơclit
giúp ta có được hình dung về mặt hình học cũng như có thể tính được
Gọi b là lề, ta có
6 = i( |c _ |2 - |c+|2), (1.9)
Do |Ịx|| = v< x .x > ncn khi b triệt ticu tức là khoảng cách trung bình
của hai lớp đến gốc toạ độ là bàng nhau. Từ (1.8) ta có một siêu phẳng, gồm các
điểm thoả mãn các điều kiện của một đẳng thức tuyển tính. Trừ (1.6) và (1.7)
cho ( 1.8) ta có hàm quyết định :
Trước tiên, ta tính trung binh mẫu của hai lớp
Và lề b thành :
17
Hình ỉ. I Phân lớp trong đơn gián
Khi b=0 ta có trường hợp đặc biệt, bài toán trở thành bài toán phân lớp
theo phương pháp thống kê. Khi đó, k sê trở thành hàm xác suất khi một biến
không thav đổi
/
X
k (x ,x ')d x = 1 v ớ i m ọ i x 'e X (1.12)
Khi đó (1.11) là dạng phân lớp Bayes với hai lớp và phân bố xác suất
được tính theo công thức sau :
p+
(x) := —
y
k(x,xi) và P - 0 0 := —
V
k(x,xi) (1.13)
ĨĨĨ+ í—i ĨĨI- L-Ấ
{Ì|yi=+1} {i|y«=-i}
Khi đó, với một sổ mẫu X, thì nhãn được xác định bằng giá trị lớn hơn
trong hai giá trị p , (x) và p.(x)
ĐẠI H Ọ C Q U O C G I A H A N Ộ I
tru n g Tâm JHÔNG TIN THU VIỆN
Một giai thuật học chọn luật với độ rủi ro thực nghiệm trên tập huấn luyện
là thấp nhất, nói cách khác, chọn luật / được định nghĩa như sau :
Remp (/) = inf Rcmp(/)
Phương pháp này thườníĩ là phương pháp cực tiểu rủi ro thực nghiệm
( E:RM). Nói cách khác, mục tiêu cua giải thuật học là tìm ra luật có khả năng
tổng quát hóa tốt nhất, hay tìm luật thỏa mân
R (D = inf R.(/*)
Mối liên hệ giữa R(f) và R(/*) là kết quả chính của ]ý thuyết học thống kê
ER(/) < fi(/-)+c* J ï p
c là hàng sổ toàn cục, V(F) là đặc trưng số lượng của tập luật F , còn được gọi là
chiều Vapnik-Chervonenkis (hay chiều VC), và N là số các ví dụ trong tập huấn
luyện
Nếu
• Số lượng quan sát N trong tập huấn luyện phải đủ lớn
• Số chiều v c của tập luật tiềm năng phải đủ nhò
Thì độ rủi ro của một luật được chọn f không khác nhiều so với độ rủi ro tốt nhất
có thể /?(/*)
Ta thấy chiều v c càng nhỏ, khả năng tổng quát hóa của luật được lựa
chọn theo phương thức ERM càng nhỏ. Nói cách khác, một giải thuật học sẽ tìm
một luật tổng quát hóa tốt nếu nó có thể chọn các luật từ một tập F với sổ chiều
vc nhỏ.
1.2.4.1 Không gian v c
Xét các hàm f (x): R-»{+t,-l}, có 21 cách để gán nhãn cho / điểm. Nếu
với mồi một cách gán nhãn ta đều có thể tìm thấy một thành phần của tập hợp
ự(x)} mà nhận dạng chính xác cách gán nhãn này. Khi đó tập hợp của / điểm
được nói là bị phá vỡ bởi tập hợp các hàm ịf(x)}. Chiều v c của [f(x)} là số lớn
20
nhât của các điêm dừ liệu mà có thê bị phá vờ bời nó. Chiêu vc của các siêu
phẳng tronạ không gian Rn là thường là n+1.
Hình : 1.3 vc của các đường thẳng cỏ hưởng
1.3.2 Phtrong sai
Phương sai (variance) cũng ià một công cụ đế đo độ phân tán của dữ liệu
trong tập mẫu :
2 _ E?=i(*i - X ):
* - 1 -n
(L16)
( n - 1)
•»
t
Hay ta có thê viêt dưới dạng :
Z ?=1 (Xi-X)(X i-X )
va r(x ) = —
_
(1.17)
( n - 1)
Tuy nhiên, cả độ lệch chuẩn và phương sai chỉ làm việc trên không gian
một chiều thế nên trong không gian nhiều chiều ta chỉ tìm được sự phân bố dữ
liệu trên từng chiều riêng biệt. Điều chúng ta đang mong muốn là tìm mối quan
hệ giữa các chiều dừ liệu với giá trị trung bình mẫu. Do đó chúng ta sử dụng
hàm hiệp phương sai (covariance) để so sánh giữa hai chiều dữ liệu trong không
gian nhiều chiều. Ví dụ, trong không gian ba chiều (x,y,x), bằng cách sử dụng
hàm hiệp phương sai chúng ta có thể xem xét sự phân bố dữ liệu trong các chiều
(x,y),(x,z) và (y,z), giá trị của hàm hiệp phương sai giữa (x,x), (y,y) và (z,z)
cũng chính là giá trị hiệp phương sai tương úm trên x,y và z. Hàm hiệp phương
sai được tính theo công thức sau :
22
(1.18)
ỉ(Cj}. Ớ đây, ma trận T được chuyển từ cơ sở {ej} sang cơ sở mới {iij} nên ma
trận chuyển đối từ cơ sở {ej} sang {Uj} cũng là c. Nếu T chéo hoá tức ỉà tồn tại
ma trận c khả nghịch (tức c tạo được một cơ sở trong Rn) sao cho :
Tc = C~1TC (1.21)
có dạng chéo
Neu ta có c là một ma trận có các cột là các vector cơ sở đà được chuấn
hoá của không gian Rn thì CT = c -1, từ (1.35) ta suy ra :
Tc = CtTC (1.22)
Do đó ta có thể tìm được ma trận c để chéo hoá một ma trận T bàng cách
tìm ra các vector riêng của ma trận T, lúc đó các cột của vector c là vector riêng
của T.
1.3.4 Phương pháp phân tích thành phần chính
Khi giải bài toán nhận dạng các mẫu ta phải làm việc với các không gian
dừ liệu nhiều chiều. Nhằm cải thiện khả năng chạy của thuật toán, chúng ta sẽ
ánh xạ không gian dừ liệu nhiều chiều sang một không gian khác ít chiều hơn :
'aĩ'
\b 1]
X =
0-2
* \
giám só chiêu y —
^2
•
•
,aN.
Ỉ>K.
{K « N)
Một ưu điểm của phương pháp PCA là để giảm số chiều của dữ liệu trong
khi vẫn giữa được nhiều nhất có thể các thông tin về phân bổ dữ liệu của không
gian dừ liệu cũ.
Gọi X là vector trong không gian N chiều,
X
là một vector trong không
gian K chiều thỉ trung bình bình phương lỗi (MSE) là ||x — XII khi thực hiện
giảm số chiều từ vector X sang vector óc. Do đó, ta phải thực hiện phép chuyển
đổi sao cho lồi là nhỏ nhất. Các vector riêng được gọi là vector “tốt” nhất tương
ứng với giá trị riêng lớn nhất và được gọi ỉà thành phần chính - “principal
components”.
Các bước trong phương pháp giảm số chiều dữ liệu trong không gian dừ
liệu nhiều chiều :
Giả sử XJ,X
2
, ,XM là các vector có kích thước Nx 1
1) Tìm giá trị trung bình
= ẳf>
£ = 1
2) với mỗi dừ liệu, trừ giá trị trang bình :
<Ị>i = Xị ~ X
3) Ta có ma trận A = [<$!, <ỉ>2 — ^m] kích thước N*M, sau đó tính
25
M
— 's ' i> 0 '
m Z j " n
n=l
AA1
đỏ là ma trận hiệp phương sai của các mẫu dữ liệu, thể hiện sự phân bố dữ
liệu
4) Tính các giá trị riêng của ma trân hiệp phương sai c
À1 > Ả2 > ••• > Ả
N
hướng của vector riêng
■ Vector gốc X có thể được xây dựng lại bằng cách sử dụng các thành phần
chính của nó :
K
Ể=1
+ X
Do đó cơ sở trong không gian (có sổ chiều ít hơn) nếu dựa trên các thành
phần chính thì sẽ làm tối thiếu lỗi xây dựng lại.
L7 i e w
*11
Ta có thể tính được
N
i=K +1
Để tìm được K, ta nên chọn một ngưỡng sao cho
S T 7 > N gưỡng
(ví dụ ngưỡng bằn 0,9 hay 0,95)
Copyright: Tài liệu đại học ©