ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG
ĐẠI
HỌCGIA
CÔNG
NGHỆ
ĐẠI HỌC
QUỐC
HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THANH TỊNH
NGUYỄN THANH TỊNH
NGHIÊN
NGHIÊN CỨU
CỨU ỨNG
ỨNG DỤNG
DỤNG KỸ
KỸ THUẬT
THUẬT BOOSTMETRIC
BOOSTMETRIC
NHẰM
NHẰM TĂNG
TĂNG HIỆU
HIỆU QUẢ
QUẢ PHÂN
PHÂN LỚP
LỚP DỮ
DỮ LIỆU
LIỆU LỚN
LỚN
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
LUẬN
THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN
Mã VĂN
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
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
Danh mục hình vẽ
Danh mục bảng biểu
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
8
9
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.
10
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ụ.
…
11
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)) =
(1.1)
và nhãn lớp = 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:
(1.2)
hoặc hàm khoảng cách tuyệt đối:
(1.3)
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).
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
12
đế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ó:
(1.4)
Khi đó x sẽ được gán nhãn lớp l thỏa mãn:
(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
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.
13
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 .
• 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:
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
14
Biweight
Cosine
Epanechnikov
Gauss
Inversion
Rectangular
Triangular
Triweight
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:
(1.6)
trong đó: là khoảng cách từ láng giềng thứ i đến x.
là khoảng cách từ láng giềng thứ k+1 đến x.
> 0 là một hằng số có giá trị rất nhỏ được dùng để đảm bảo . 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 . Và như vậy ta có thể sử dụng
được bất kỳ hàm trọng số nào trong bảng 1.1.
15
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:
(1.7)
Trong đó:
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:
(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 thành các giá trị trọng số:
(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:
(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:
16
0.33
0.34
0.73
?
0.35
0.71
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.
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.
17
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:
trong đó là không gian n-chiều ban đầu và là không gian đặc trưng mới có mchiều. là một vectơ tùy ý trong , là vectơ tương ứng trong . là một ánh xạ phi tuyến
tùy ý từ không gian ban đầu sang không gian , và (i = 1…m) là các hàm ánh xạ đặc
trưng.
Ta định nghĩa một hàm nhân K sao cho với mọi ta có:
(1.11)
trong đó biểu diễn phép nhân trong của và , là một hàm của 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
18
Polynomial
Radial Basis
Sigmoid
Trong đó 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 giữa 2 vectơ x và y là:
(1.12)
Để 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ó:
(1.13)
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 thuộc một nhóm các
quan sát với trung bình của nhóm đó là:
(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
19
đ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
theo chiều Y nhỏ hơn so với phương sai theo chiều X. Dùng khoảng cách Mahalanobis
ta sẽ phản ánh được hiện tượng trên.
Khoảng cách Mahalanobis có những ưu điểm sau:
Tính đến phương sai theo các chiều khác nhau là khác nhau.
Tính đến hiệp phương sai giữa các biến.
1.6. Kỹ thuật Boosting
Để trả lời cho câu hỏi của Michael Kearns năm 1988: “Liệu có thể tạo ra một bộ
phân loại mạnh từ một tập các bộ phân loại yếu?”, Robert Schapire đã giới thiệu thuật
toán Boosting vào năm 1990. Boosting [3] là một thuật toán thuộc lớp các phương
pháp học tổ hợp (ensemble learning), nơi nhiều bộ học được huấn luyện để giải quyết
cùng một bài toán. Một thuật toán Boosting điển hình tạo một bộ học mạnh duy nhất
bằng cách từng bước thêm các bộ học cơ sở (yếu) vào bộ học mạnh cuối cùng. Các bộ
học cơ sở có vai trò quan trọng trong bộ học mạnh, chúng là các bộ học đơn giản, chỉ
cần có độ chính xác trên 50%. Một cách tổng quát, một thuật toán Boosting được xây
20
dựng trên một thủ tục huấn luyện cơ bản do người dùng định rõ và chạy lặp đi lặp lại
với dữ liệu được sửa đổi là đầu ra từ những vòng lặp trước.
Dạng tổng quát của thuật toán Boosting được mô tả trong hình 1.4 bên dưới. Đầu
vào của thuật toán là một tập các mẫu huấn luyện x và nhãn lớp y tương ứng của nó.
Kết quả cuối cùng là một bộ phân lớp mạnh có dạng:
(1.15)
trong đó là một bộ học cơ sở.
Input: Tập dữ liệu huấn luyện.
Begin
• Khởi tạo một tập trọng số trên các mẫu huấn luyện;
for j = 1,2,…, do
Thu được một bộ học yếu ;
Tính ;
Cập nhật ;
end;
End;
Output: Một tổ hợp tuyến tính của các bộ học yếu: .
Hình 1.4: Dạng tổng quát của thuật toán Boosting
Ví dụ trong hình 1.5 dưới đây minh họa việc xây dựng một bộ học mạnh từ các bộ
học yếu :
- Xem thêm -