ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THANH TỊNH
NGHIÊN CỨU ỨNG DỤNG KỸ THUẬT BOOSTMETRIC
NHẰM TĂNG HIỆU QUẢ PHÂN LỚP DỮ LIỆU LỚN
LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THANH TỊNH
NGHIÊN CỨU ỨNG DỤNG KỸ THUẬT BOOSTMETRIC
NHẰM TĂNG HIỆU QUẢ PHÂN LỚP DỮ LIỆU LỚN
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã Số: 60480104
LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN HÀ NAM
HÀ NỘI - 2014
Lời cam đoan
Tôi xin cam đoan luận văn “Nghiên cứu ứng dụng kỹ thuật BoostMetric nhằm
tăng hiệu quả phân lớp dữ liệu lớn” là công trình nghiên cứu của riêng tôi. Các số liệu,
kết quả được trình bày trong luận văn là hoàn toàn trung thực. Tôi đã trích dẫn đầy đủ
các tài liệu tham khảo, công trình nghiên cứu liên quan. Ngoại trừ các tài liệu tham
khảo này, luận văn hoàn toàn là công việc của riêng tôi.
Luận văn được hoàn thành trong thời gian tôi là học viên tại Khoa Công nghệ
Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.
Hà Nội, ngày 30 tháng 10 năm 2014
Học viên
Nguyễn Thanh Tịnh
Lời cảm ơn
Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới PGS.TS.
Nguyễn Hà Nam đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt
nghiệp.
Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để
tôi học tập và nghiên cứu tại trường Đại học Công Nghệ.
Tôi xin gửi lời cảm ơn tới các bạn trong lớp cao học K18 đã ủng hộ, khuyến
khích tôi trong suốt quá trình học tập tại trường.
Tôi cũng thầm biết ơn tới công lao to lớn của gia đình - những người luôn luôn
động viên và nuôi dưỡng tôi trong cuộc đời. Cám ơn những người bạn đồng nghiệp
của tôi, luôn bên cạnh tôi để chia sẻ những kinh nghiệm trong học tập cũng như trong
cuộc sống.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 30 tháng 10 năm 2014
Học viên
Nguyễn Thanh Tịnh
Mục lục
Mở đầu................................................................................................................................
Chương 1. Giới thiệu về Khai phá dữ liệu..........................................................................
1.1. Tổng quan về Khai phá dữ liệu...........................................................................
1.2. Thuật toán k láng giềng gần nhất (kNN)...............................................................
1.3. Thuật toán Weighted k-Nearest-Neighbors (WkNN)............................................
1.4. Phương pháp Kernel kNN.....................................................................................
1.5. Khoảng cách Mahalanobis..................................................................................
1.6. Kỹ thuật Boosting...............................................................................................
1.7. Kỹ thuật BoostMetric..........................................................................................
Chương 2. Kết hợp giữa BoostMetric và WkNN..............................................................
2.1. Mô hình tổng quan..............................................................................................
2.2. Cách thức hoạt động của từng thành phần..........................................................
Chương 3. Thực nghiệm...................................................................................................
3.1. Môi trường và thiết kế thực nghiệm....................................................................
3.2. Dữ liệu sử dụng..................................................................................................
3.3. Phân tích kết quả thực nghiệm............................................................................
Kết luận............................................................................................................................
Tài liệu tham khảo............................................................................................................
Danh mục hình vẽ
Hình 1.1: Ví dụ về thuật toán kNN.....................................................................................
Hình 1.2: Ví dụ về thuật toán WkNN..................................................................................
Hình 1.3: Ví dụ về độ biến thiên theo các chiều khác nhau của dữ liệu............................
Hình 1.4: Dạng tổng quát của thuật toán Boosting...........................................................
Hình 1.5: Ví dụ về thuật toán Boosting.............................................................................
Hình 1.6: Tìm wj bằng tìm kiếm nhị phân...................................................................
Hình 1.7: Huấn luyện ma trận xác định không âm dựa theo thuật toán Boosting.............
Hình 2.1: Mô hình tổng quan kết hợp BoostMetric và WkNN..........................................
Hình 2.2: Mô hình chi tiết kết hợp BoostMetric và WkNN..............................................
Hình 2.3: Thuật toán sinh tập các bộ ba dùng để huấn luyện các ma trận cơ sở Zj...........
Hình 3.1: So sánh độ chính xác của bốn bộ phân lớp: BoostMetric+WkNN,
BoostMetric+kNN, Kernel WkNN và WkNN với các bộ dữ liệu sử dụng........................
Hình 3.2: So sánh chi tiết 10 lần chạy của bốn bộ phân lớp: BoostMetric+WkNN,
BoostMetric+kNN, Kernel WkNN và WkNN với các bộ dữ liệu sử dụng........................
Hình 3.3: So sánh độ chính xác của ba bộ phân lớp: BoostMetric+WkNN, Random
Forest và SVM với các bộ dữ liệu sử dụng.......................................................................
Hình 3.4: So sánh chi tiết 10 lần chạy của ba bộ phân lớp: BoostMetric+WkNN,
Random Forest và SVM với các bộ dữ liệu sử dụng.........................................................
Hình 3.5: So sánh hiệu quả của các hàm trọng số sử dụng với bộ phân lớp
BoostMetric+WkNN.........................................................................................................
Danh mục bảng biể
Bảng 1.1: Các hàm trọng số tiêu biểu.................................................................................
Bảng 1.2: Một số hàm nhân hay được dùng......................................................................
Bảng 3.1: Các bộ dữ liệu dùng trong thực nghiệm............................................................
Bảng 3.2: So sánh tỉ lệ lỗi (%) khi chạy thực nghiệm các bộ phân lớp:
BoostMetric+5NN, W5NN, Kernel W5NN và BoostMetric+W5NN...............................
Bảng 3.3: So sánh tỉ lệ lỗi (%) khi chạy thực nghiệm các bộ phân lớp:
BoostMetric+7NN, W7NN, Kernel W7NN và BoostMetric+W7NN...............................
Bảng 3.4: So sánh tỉ lệ lỗi (%) khi chạy thực nghiệm các bộ phân lớp:
BoostMetric+WkNN, Random Forest và SVM................................................................
Y
Danh mục viết tắt
STT
Thuật ngữ
Từ viết tắt
1
k-Nearest Neighbors
kNN
2
Weighted k-Nearest Neighbors
WkNN
3
Support Vector Machine
SVM
4
Số thứ tự
STT
9
10
Mở đầu
Ngày nay, cuộc cách mạng về khoa học và công nghệ đã có những bước phát
triển vượt bậc, đánh dấu những mốc son đáng tự hào trong nền văn minh của thế giới
đương đại. Cùng với sự phát triển này, một lượng dữ liệu ngày càng lớn và vô cùng
phong phú đã được tạo ra. Lượng dữ liệu rất lớn, nhưng thông tin chứa trong nó thì rất
ít, nên đòi hỏi phải có các kỹ thuật mới để khai thác thông tin, khai phá dữ liệu ra đời
nhằm đáp ứng các yêu cầu đó.
Phân lớp dữ liệu là một trong các hướng nghiên cứu của khai phá dữ liệu. Phân
lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị hay là nhãn của lớp
trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Thuật
toán k láng giềng gần nhất (kNN) là một trong những kỹ thuật cơ bản, đơn giản và trực
giác nhất trong lĩnh vực Phân tích thống kê. Bộ phân lớp dựa trên thuật toán kNN là
một bộ học lười (lazy learner), không cần thực hiện quá trình học cho mô hình. Nó cần
sử dụng tất cả các đối tượng dữ liệu trong tập tham chiếu để ra quyết định gán nhãn
lớp cho một quan sát mới. Mặc dù rất đơn giản, nhưng thuật toán kNN đã cho kết quả
tốt trong nhiều ứng dụng thực tế.
BoostMetric là phương pháp đo khoảng cách giữa các điểm dữ liệu dựa vào việc
huấn luyện ma trận tham số X của hàm khoảng cách Mahalanobis. Trong luận văn
này, chúng tôi đề xuất mô hình kết hợp sử dụng BoostMetric và Weighted kNN, một
cải tiến của thuật toán kNN, nhằm làm tăng hiệu quả phân lớp dữ liệu.
Nội dung của luận văn được chia thành các chương như sau:
Chương 1: Luận văn giới thiệu khái quát về Khai phá dữ liệu và một số kỹ thuật
Học máy cơ bản, bao gồm hai thuật toán BoostMetric và WkNN.
Chương 2: Luận văn đề xuất mô hình kết hợp hai thuật toán BoostMetric và
WkNN để làm tăng hiệu quả phân lớp dữ liệu.
Chương 3: Thực nghiệm, kết quả, và đánh giá. Tiến hành thực nghiệm theo mô
hình đã đề xuất trong chương 2.
Phần kết luận: Tóm lược kết quả đạt được của luận văn.
11
Chương 1. Giới thiệu về Khai phá dữ liệu
1.1. Tổng quan về Khai phá dữ liệu
Khai phá dữ liệu là quá trình khám phá các tri thức mới và các tri thức có ích ở
dạng tiềm năng trong nguồn dữ liệu đã có.
Một số phương pháp Khai phá dữ liệu tiêu biểu:
Phân lớp (Classification): Khai thác một hàm đã được huấn luyện trước để
phân loại một đối tượng dữ liệu vào một trong các lớp được định nghĩa
trước.
Hồi qui (Regression): Khai thác một hàm đã được huấn luyện trước để ánh
xạ một đối tượng dữ liệu thành một giá trị thực là kết quả dự báo.
Phân cụm (Clustering): Giải quyết vấn đề tìm kiếm, phát hiện số lượng
hữu hạn các cụm mô tả một tập hợp dữ liệu ban đầu không có nhãn. Đó là
quá trình tìm cách nhóm các đối tượng đã cho vào các cụm, sao cho các đối
tượng trong cùng một cụm tương tự (similar) nhau, và các đối tượng khác
cụm thì không tương tự (dissimilar) nhau.
Tổng hợp (Summarization): Quá trình bao gồm các phương pháp để tìm
một mô tả súc tích cho một tập (hoặc một tập con) dữ liệu.
Mô hình hóa ràng buộc (Dependency Modeling): Tìm một mô hình cục bộ
mô tả các ràng buộc quan trọng giữa các biến hoặc giữa các giá trị của một
đặc trưng trong một tập dữ liệu hoặc trong một phần của tập dữ liệu
Phát hiện biến đổi và độ lệch (Change and Deviation Detection): Khai
phá những biến đổi quan trọng nhất trong tập dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng quan trọng trong thực tế, lĩnh vực cũng rất
phong phú:
Trong lĩnh vực Bảo hiểm, Tài chính, và Thị trường chứng khoán: phân tích
tình hình tài chính của một công ty dựa trên báo cáo tài chính. Hay dự đoán
giá cổ phiếu dựa vào phân tích dữ liệu về Thị trường chứng khoán,…
Trong Thống kê, Phân tích dữ liệu và Hỗ trợ ra quyết định.
Trong Y học: chẩn đoán bệnh và gợi ý phác đồ điều trị dựa vào mối liên hệ
giữa các triệu chứng của bệnh nhân.
Quảng cáo, Thương mại điện tử, Phát triển ứng dụng hướng người dùng:
phân tích thói quen sử dụng/mua bán sản phẩm của người dùng để đưa ra
các gợi ý mua sắm hoặc cách sắp xếp, cách đầu tư các sản phẩm tối ưu. Dự
đoán hành vi người dùng nhằm nâng cao chất lượng dịch vụ.
…
12
Các phần tiếp theo tôi sẽ trình bày một số kỹ thuật Khai phá dữ liệu tôi đã tìm
hiểu để phục vụ cho đề tài nghiên cứu của mình.
1.2. Thuật toán k láng giềng gần nhất (kNN)
1.2.1. Phương pháp Láng giềng gần nhất (Nearest Neighbor)
Phương pháp Láng giềng gần nhất [5, 8] được đề xuất bởi Fix và Hodges năm
1951, là một trong những kỹ thuật cơ bản, đơn giản và trực giác nhất trong lĩnh vực
Phân tích thống kê. Nó được xây dựng từ nhu cầu thực hiện phân tích biệt số khi
không biết hoặc khó xác định các tham số tin cậy ước lượng các hàm mật độ xác suất.
Trong phương pháp này, một quan sát (observation) mới x sẽ được gán nhãn lớp của
đối tượng quan sát trong tập tham chiếu có nét tương đồng nhất với x. Độ tương tự
giữa các đối tượng dữ liệu được quyết định dựa vào một hàm đo khoảng cách.
Đặt: L = {(yi, xi), i = 1,…, nL }
là tập tham chiếu gồm các dữ liệu được quan sát, trong đó yi ¿ {1,…, c} biểu diễn
nhãn lớp và xi = (xi1,…, xip) là vectơ biểu diễn một đối tượng dữ liệu trong không gian
đặc trưng.
Việc xác định các láng giềng gần nhất dựa trên một hàm khoảng cách d(.,.). Theo đó,
với một quan sát mới (y, x) thì láng giềng gần nhất của nó (y(1), x(1)) trong tập tham
chiếu được xác định bởi:
d(x, x(1)) = mini ( d ( x , x i ) )
(1.1)
và nhãn lớp ^y = y(1) của láng giềng gần nhất được lựa chọn để gán cho y. Ở đây các
ký hiệu x(j) và y(j) biểu diễn láng giềng gần nhất thứ j của x và nhãn lớp tương ứng của
nó.
Hàm khoảng cách d(.,.) thường là hàm khoảng cách Euclidean:
p
d ( xi , x j )=
(∑ (
s=1
1
2 2
x is −x js )
)
(1.2)
hoặc hàm khoảng cách tuyệt đối:
p
d ( xi , x j )=∑ |x is −x js|
(1.3)
s=1
Phương pháp Láng giềng gần nhất được giải thích dựa vào sự phân bố ngẫu
nhiên của tập tham chiếu, được mô tả bởi Fahrmeir và các cộng sự vào năm 1996 [5].
Nhãn lớp y(1) của láng giềng gần nhất x(1) của đối tượng quan sát mới x là một biến
ngẫu nhiên. Xác suất để x được phân vào lớp y(1) là P(y(1)|x(1)). Với tập tham chiếu có
kích thước lớn, có thể coi x và x(1) gần như trùng khớp với nhau, dẫn đến P(y(1)|x(1)) ≈
P(y|x). Do đó x được phán đoán thuộc về lớp đúng y với xác suất xấp xỉ P(y|x).
13
1.2.2. Thuật toán kNN
Thuật toán k láng giếng gần nhất [5, 6, 8] là một mở rộng đầu tiên của phương
pháp trên, và thường được sử dụng rộng rãi trong thực tế. Ở đây không chỉ tham chiếu
đến một mà xét đến k láng giềng gần nhất trong tập tham chiếu của đối tượng cần phán
đoán x. Điều này giúp tránh trường hợp một đối tượng quan sát kỳ dị (nhiễu) trong tập
tham chiếu quyết định nhãn lớp. Tham số k do người dùng lựa chọn. Nhãn lớp được
gán cho x là lớp chiếm đại đa số trong tập k láng giềng vừa xác định.
Đặt kr là số quan sát thuộc về lớp r nằm trong tập k láng giềng gần nhất của x. Ta có:
c
∑ k r=k
(1.4)
r=1
Khi đó x sẽ được gán nhãn lớp l thỏa mãn:
k l =maxr ( k r )
(1.5)
Mức độ cục bộ của phương pháp này phụ thuộc vào tham số k. Với k = 1, ứng
với phương pháp Láng giềng gần nhất cơ bản, cho mức độ cục bộ tối đa. Với k = nL,
kéo theo một kết quả phán đoán duy nhất cho mọi đối tượng quan sát mới, nhãn lớp
xuất hiện nhiều nhất trong tập tham chiếu sẽ luôn được chọn.
Bộ phân lớp dựa trên thuật toán k láng giếng gần nhất là một bộ học lười (lazy
learner), không cần thực hiện quá trình học cho mô hình. Nó cần sử dụng tất cả các đối
tượng dữ liệu trong tập tham chiếu để ra quyết định gán nhãn lớp cho một quan sát
mới.
Một ví dụ về thuật toán kNN:
?
k=
5
14
Hình 1.1: Ví dụ về thuật toán kNN
Với k = 5, trong 5 láng giếng gần nhất của đối tượng cần phân lớp x có 3 đối tượng
quan sát thuộc lớp âm (-), và 2 đối tượng quan sát thuộc lớp dương (+). Như vậy x sẽ
được gán nhãn là lớp âm.
1.3. Thuật toán Weighted k-Nearest-Neighbors (WkNN)
Thuật toán WkNN [5] cải tiến thuật toán kNN theo ý tưởng: các láng giềng ở gần
đối tượng quan sát mới x phải có vai trò quan trọng hơn so với các láng giềng ở xa
trong việc quyết định nhãn lớp của x. Trong thuật toán kNN thì cả k láng giềng gần
nhất của x đều có vai trò ảnh hưởng như nhau, dù độ tương tự giữa từng thành viên
trong chúng so với x có thể khác xa nhau. Để phản ánh độ quan trọng khác nhau của
các láng giềng gần nhất của x, các giá trị khoảng cách từ chúng đến x cần được biến
đổi thành các trọng số. Theo đó, mỗi láng giềng của x sẽ được gán cho một giá trị
trọng số, giá trị này sẽ được dùng trực tiếp để quyết định nhãn lớp cho x.
1.3.1. Chiến lược đánh trọng số cho các láng giềng
Việc biến đổi từ giá trị khoảng cách sang giá trị trọng số được thực hiện thông
qua một hàm trọng số f(.). Hàm f(.) là hàm của biến khoảng cách d, nhận đầu vào là
giá trị khoảng cách d, đầu ra là giá trị trọng số w = f(d).
Hàm f(d) phải thỏa mãn các tính chất sau:
f(d) ≥ 0 ∀ d ∈ R .
f(d) đạt giá trị cực đại khi d = 0.
f(d) là hàm giảm nghiêm ngặt với d → ±∞. Tức f(d1) ≤ f(d2)
Một số hàm trọng số tiêu biểu được mô tả trong bảng 1.1 dưới đây:
∀ d1≥ d2
15
Bảng 1.1: Các hàm trọng số tiêu biểu
Tên hàm
Công thức tương ứng
2
15
( 1−d 2 ) (|d|≤ 1 )
16
Biweight
f (d )=
Cosine
π
π
f ( d ) = cos d (|d|≤ 1 )
4
2
Epanechnikov
3
2
f ( d ) = ( 1−d ) (|d|≤ 1 )
4
Gauss
1
−d 2
f (d )=
exp
2
√2 π
Inversion
f (d )=
Rectangular
f (d )=
Triangular
f ( d ) =1−|d|(|d|≤ 1 )
Triweight
f (d )=
( )
( )
1
|d|
1
2
3
35
( 1−d 2 ) (|d|≤ 1 )
32
Trong ngữ cảnh sử dụng các giá trị khoảng cách làm tham số đầu vào, đương
nhiên chỉ miền xác định dương của hàm f(.) được sử dụng. Việc lựa chọn dùng hàm
trọng số nào là tham số đầu vào thứ ba của thuật toán này.
Ta thấy hầu hết các hàm trọng số trong bảng 1.1 đều có tập xác định là [0, 1]. Và
để tránh trường hợp giá trị trọng số của một láng giềng nào đó bằng 0 (khi d = 1), tức
láng giềng đó hoàn toàn không có vai trò gì trong việc quyết định nhãn lớp của đối
tượng quan sát x, thì giá trị của d cần được chuẩn hóa để xác định trong khoảng [0, 1).
WkNN thực hiện điều này bằng cách sử dụng giá trị khoảng cách của láng giềng gần
nhất thứ (k+1) khi chuẩn hóa các khoảng cách của k láng giềng đã chọn.
Ta dùng công thức sau để chuẩn hóa khoảng cách của k láng giềng gần nhất:
D ( x , x (i )) =
trong đó:
d ( x , x(i) )
d ( x , x(i) )
d ( x , x (k+1 )) +ε
với i=1, … , k
là khoảng cách từ láng giềng thứ i đến x.
d ( x , x (k +1) ) là khoảng cách từ láng giềng thứ k+1 đến x.
(1.6)
16
ε
> 0 là một hằng số có giá trị rất nhỏ được dùng để đảm bảo
D ( x , x (i )) <1 . Nếu không dùng
thì trong trường hợp một trong số k láng giềng
gần nhất của x có khoảng cách đến x bằng với láng giềng gần nhất thứ (k+1) thì
khoảng cách sau khi chuẩn hóa của nó sẽ bằng 1. Dẫn đến trọng số của nó sẽ bằng 0
nếu dùng với một số hàm trọng số trong bảng 1.1 ở trên.
ε
Với cách chuẩn hóa như trên thì ta sẽ đảm bảo D ( x , x (i )) ϵ ¿
ta có thể sử dụng được bất kỳ hàm trọng số nào trong bảng 1.1.
∀ i . Và như vậy
1.3.2. Lược đồ hoạt động
Sau khi xác định các độ đo tương tự cho các quan sát trong tập tham chiếu, mỗi
đối tượng quan sát mới x sẽ được phân vào lớp r có tổng các trọng số lớn nhất:
maxr
Trong đó:
(
k
∑ ( f ( D ( x , x (i ) ) ) I ( y(i)=r ) )
i=1
)
(1.7)
{
I ( cond )= 1,∧cond =true
0,∧cond=false
Có thể coi hai thuật toán kNN và NN là các trường hợp đặc biệt của thuật toán
WkNN. Ta có kết quả của kNN nếu chọn sử dụng hàm trọng số Rectangular. Và có kết
quả của NN nếu chọn k = 1, với mọi lựa chọn của hàm trọng số.
Mục đích chính của phương pháp này là xây dựng được một kỹ thuật trong đó
đạt tới một cấp độ tương đối độc lập với việc lựa chọn giá trị tham số k, với kNN thì
việc chọn sai giá trị của k sẽ dẫn đến tỉ lệ phân lớp sai lớn. Số lượng các láng giềng
gần nhất hoàn toàn được ẩn đi với việc sử dụng các trọng số: nếu k có giá trị quá lớn,
nó sẽ tự động được điều chỉnh xuống một giá trị thấp hơn. Trong trường hợp này, một
số nhỏ các láng giềng có trọng số lớn sẽ lấn át các láng giềng khác.
Thuật toán WkNN được mô tả tổng quan ở dưới đây:
Bước 1: Đặt L = {(yi, xi), i = 1,…, nL } là tập tham chiếu chứa các đối tượng
quan sát xi với nhãn lớp tương ứng yi. Giả sử ta cần phán đoán nhãn lớp y của
một đối tượng quan sát mới x.
Bước 2: Tìm k+1 láng giềng gần nhất của x dựa vào một hàm khoảng cách d(x,
xi). Ở đây dùng hàm khoảng cách Minkowski:
d ( xi , x j )=
(
p
1
q q
∑|x is−x js|
s=1
)
(1.8)
Bước 3: Sử dụng công thức (1.6) để chuẩn hóa khoảng cách từ x đến k láng
giềng gần nhất của nó.
Bước 4: Sử dụng một trong số các hàm trọng số để biến đổi các khoảng cách
chuẩn D(i) thành các giá trị trọng số:
17
w(i)=f ( D(i) )
(1.9)
Bước 5: Chọn lớp có tổng các trọng số lớn nhất để gán nhãn cho x:
k
^y =max r
(∑ (
i=1
w(i) I ( y (i )=r ) )
)
(1.10)
Nhìn chung có thể coi các phương pháp WkNN và kNN là các phương pháp bầu
cử nhóm: một số bộ phân lớp tiềm năng (các láng giềng gần nhất) được kết hợp lại và
thực hiện một cuộc bầu cử đa số thắng, và kết quả này được dùng để thực hiện phán
đoán.
Hình 1.2 dưới đây minh họa một ví dụ về thuật toán WkNN với k = 5:
0.
33
0.
73
0.
34
0.
35
?
0.7
1
k=
5
Hình 1.2: Ví dụ về thuật toán WkNN
Trong hình 1.2 trên ta thấy các láng giềng gần nhất của đối tượng quan sát cần
phán đoán lớp x thuộc về hai lớp: lớp dương (+), và lớp âm (-). Giả sử sau khi tính
toán khoảng cách ta tìm được 5 láng giềng gần nhất của x như trên, trong đó có 3 đối
tượng thuộc về lớp âm và 2 đối tượng thuộc về lớp dương. Giả sử các trọng số của
từng láng giềng có giá trị tính được như trên hình vẽ.
Ta có:
Tổng trọng số của lớp dương là: 0.73 + 0.71 = 1.44
Tổng trọng số của lớp âm là: 0.33 + 0.34 + 0.35 = 1.02
Như vậy x sẽ được phán đoán thuộc về lớp dương vì lớp này có tổng trọng số lớn
nhất.
18
Qua ví dụ này ta thấy có sự khác biệt rõ ràng trong kết quả phán đoán của WkNN
và kNN. Nếu sử dụng bộ phân lớp kNN thì x sẽ được phán đoán thuộc về lớp âm vì
đây là lớp chiếm đại đa số trong 5 láng giềng gần nhất của x.
Từ mô hình hoạt động của bộ phân lớp WkNN ta nhận thấy bộ phân lớp này có
một vấn đề, đó là nó sử dụng một hàm khoảng cách duy nhất (cách tính luôn cố định
trước) cho mọi tập dữ liệu đầu vào – hàm khoảng cách Minkowski. Hàm khoảng cách
này có thể cho kết quả tốt (lựa chọn chính xác các láng giềng gần nhất) với một số bộ
dữ liệu nhất định nhưng không đảm bảo cho được kết quả tương tự với rất nhiều bộ dữ
liệu khác. Và quan trọng hơn, với việc dùng hàm khoảng cách Minkowski, bộ phân
lớp WkNN vẫn chưa vượt qua được vấn đề không gian phi tuyến, nơi các đối tượng dữ
liệu phân bố tương đối tự do và mức độ phân tán theo các chiều là khác xa nhau.
Mục tiêu luận văn của tôi là tìm một phương pháp đo khoảng cách khác có khả
năng thích ứng với mọi bộ dữ liệu đầu vào, và hoạt động tốt trên không gian phi tuyến.
Ở đây, khả năng thích ứng với mọi bộ dữ liệu đầu vào có nghĩa là kỹ thuật đó cho
phép huấn luyện hàm đo khoảng cách dựa vào tập huấn luyện. Phương pháp
BoostMetric được trình bày ở mục 1.7 đáp ứng đầy đủ các tiêu chí trên.
1.4. Phương pháp Kernel kNN
1.4.1. Tổng quan
Thuật toán kNN đã cho kết quả tốt trong nhiều bài toán thực tế. Tuy nhiên, với
các bài toán phi tuyến phức tạp, nơi dữ liệu phân bố tương đối tùy ý, nó thường cho
kết quả khá tồi. Từ thực trạng đó, năm 2002, nhóm tác giả Kai Yu, Liang Ji, và
Xuegong Zhang, tiếp cận theo hướng sử dụng hàm nhân (Kernel) để cải tiến độ chính
xác của thuật toán kNN trên không gian phi tuyến [7]. Về bản chất, Kernel kNN dùng
một hàm phi tuyến ánh xạ các mẫu dữ liệu trong không gian ban đầu sang một không
gian đặc trưng mới, rồi thực hiện thuật toán kNN trên không gian đặc trưng mới đó.
Điểm mấu chốt của phương pháp này là dựa vào việc sử dụng một hàm nhân để tính
phép nhân trong (inner product) của các vectơ là ảnh của các mẫu dữ liệu ban đầu qua
phép ánh xạ. Nếu chọn được một hàm nhân phù hợp thì hiệu quả của thuật toán kNN
có thể được cải thiện đáng kể.
Ta xét trường hợp ánh xạ một không gian n-chiều sang một không gian đặc trưng
m-chiều như sau:
x=( x 1 ,… , x n ) á n h x ạ đặ c tr ư ng ψ ( x )=( φ1 ( x ) , … φm ( x ) ) , x ∈ S1 ,ψ ( x ) ∈ S 2
→
trong đó S 1 là không gian n-chiều ban đầu và S 2 là không gian đặc trưng
mới có m-chiều. x là một vectơ tùy ý trong S 1 , ψ ( x ) là vectơ tương ứng trong
S 2 . ψ là một ánh xạ phi tuyến tùy ý từ không gian ban đầu sang không gian S 2
, và φi (i = 1…m) là các hàm ánh xạ đặc trưng.
19
Ta định nghĩa một hàm nhân K sao cho với mọi
x , y ∈ S1
ta có:
K ( x , y )= ⟨ ψ ( x ) , ψ ( y ) ⟩
(1.11)
trong đó ⟨ ψ ( x ) ,ψ ( y ) ⟩ biểu diễn phép nhân trong của
K ( x , y ) là một hàm của x và y.
ψ(x)
và
ψ( y) ,
Việc định nghĩa một hàm nhân như công thức (1.11) ở trên dẫn đến phép nhân
trong trong không gian đặc trưng mới có thể được tính mà không cần thực sự thực hiện
phép ánh xạ ψ . Ba hàm nhân được mô tả trong bảng 1.2 dưới đây thường được sử
dụng rộng rãi:
Bảng 1.2: Một số hàm nhân hay được dùng
Tên hàm
Công thức tương ứng
p
Polynomial
K ( x , y )=( 1+ ⟨ x , y ⟩ )
Radial Basis
−‖x − y‖
K ( x , y )=exp
σ2
Sigmoid
K ( x , y )=tanh ( α ⟨ x , y ⟩ + β )
Trong đó
(
p,σ ,α , β
2
)
là các tham số có thể điều chỉnh được.
1.4.2. Nguyên lý hoạt động
Trong thuật toán kNN truyền thống, một hàm đo khoảng cách chuẩn như khoảng
cách Euclidean thường được sử dụng. Bằng cách định nghĩa lại hàm đo, ta có thể sử
dụng phương pháp hàm nhân để áp dụng vào thuật toán kNN. Phương pháp sử dụng
hàm nhân dựa trên một thực tế là ta cần phải tính phép nhân trong giữa các vectơ là
ảnh của các mẫu dữ liệu ban đầu qua phép ánh xạ. Do phép nhân trong chỉ tính được
trong không gian Hilbert, nên ta chỉ quan tâm đến các hàm đo khoảng cách chuẩn
trong không gian Hilbert.
Khoảng cách chuẩn d ( x , y ) giữa 2 vectơ x và y là:
(1.12)
d ( x , y )=‖ x− y‖
Để sử dụng thuật toán kNN trong không gian đặc trưng mới, ta cần tính khoảng
cách chuẩn trong không gian đó. Sử dụng (1.11) và (1.12) ta có:
2
2
d ( ψ ( x ) ,ψ ( y ) )=‖ψ ( x )−ψ ( y )‖
¿ ⟨ ψ ( x ) ,ψ ( x ) ⟩−2 ⟨ ψ ( x ) , ψ ( y ) ⟩ + ⟨ ψ ( y ) , ψ ( y ) ⟩
¿ K ( x , x ) −2 K ( x , y ) + K ( y , y )
(1.13)
20
Như vậy khoảng cách chuẩn trong không gian đặc trưng mới có thể được tính
bằng cách sử dụng một hàm nhân và các vectơ dữ liệu trong không gian mẫu ban đầu
mà không cần xác định và thực hiện phép ánh xạ ψ . Sau khi xác định được hàm đo
khoảng cách ở công thức (1.13), ta có thể dễ dàng thực hiện thuật toán kNN trên không
gian đặc trưng mới.
1.5. Khoảng cách Mahalanobis
Khoảng cách Mahalanobis [9] giữa một đối tượng quan sát
x=( x 1 , x 2 ,… , x n )T
T
thuộc một nhóm các quan sát với trung bình của nhóm đó μ=( μ 1 , μ2 , … , μn ) là:
D M ( x )=√ ( x−μ ) S ( x −μ )
T
−1
(1.14)
trong đó S là ma trận hiệp phương sai của nhóm.
Nếu ma trận hiệp phương sai S là ma trận đơn vị, khoảng cách Mahalanobis trở
thành khoảng cách Euclidean. Dùng khoảng cách Mahalanobis ta có thể biết được một
điểm ở cách trung bình của nhóm bao nhiêu độ lệch chuẩn. Khoảng cách xa gần không
đơn giản như những gì mắt ta nhìn thấy. Ta xét ví dụ một phân bố dữ liệu như hình 1.3
dưới đây:
Hình 1.3: Ví dụ về độ biến thiên theo các chiều khác nhau của dữ liệu
Theo đó, dữ liệu được phân bố theo các hình e-líp đồng tâm tại gốc tọa độ (trung
bình của nhóm). Ta gọi các đường e-líp này lần lượt là các đường e-líp 10%, 20%,…,
90% tính từ gốc tọa độ. Mật độ dữ liệu ở các đường e-líp càng gần tâm thì càng lớn.
Ta xét 2 điểm có tọa độ lần lượt là A(0; 2) và B(4; 0). Nếu dùng khoảng cách
Euclidean, rõ ràng điểm A(0; 2) ở gần tâm hơn so với điểm B(4; 0). Nhưng như ta thấy
điểm A(0; 2) nằm trên đường e-líp 90% (ngoài cùng), còn điểm B(4; 0) nằm trên
đường e-líp 70%, nên B(4; 0) phải ở gần tâm hơn so với A(0; 2). Ở đây phương sai
- Xem thêm -