Xem mẫu
- Thuật toán máy hỗ trợ vector
(support vector machine-SVM)
Người hướng dẫn:CN.Vũ Tiến Thành
Sinhviên :Đinh thị Hương
Lớp : k52CA
- Nội dung chính
I.Phát biểu bài toán.
1.Trình bày tóm tắt về phân lớp dữ liệu
2.Tại sao lại sử dụng thuật toán SVM để phân lớp
dữ liệu?
II. Thuật toán máy hỗ trợ vector(SVM)
1. Định nghĩa
2. Mục đích
3. Mô hình giải thuật
4.Các câu hỏi
5.Giải quyết
6.Transductive support vector machine(TSVM)
III.Ứng dụng của SVM
- I.Phát biểu bài toán:
1.Trình bày tóm tắt về phân lớp dữ liệu
- Phân lớp dữ liệu là một kỹ thuật trong khai
phá dữ liệu được sử dụng rộng rãi nhất và được
nghiên cứu mở rộng hiện nay.
- Mục đích: Để dự đoán những nhãn phân lớp
cho các bộ dữ liệu hoặc mẫu mới.
- Đầu vào: Một tập các mẫu dữ liệu huấn
luyện,với một nhãn phân lớp cho mỗi mẫu dữ
liệu
- Đầu ra:Bộ phân lớp dựa trên tập huấn
luyện,hoặc những nhãn phân lớp
- - Kỹ thuật phân lớp dữ liệu được tiến
hành bao gồm 2 bước:
Bước 1:
Xây dựng mô hình từ tập huấn luyện
Bước 2:
Sử dụng mô hình – kiểm tra tính đúng đắn
của mô hình và dùng nó để phân lớp dữ liệu mới.
- Bước 1. Xây dựng mô hình
- Mỗi bộ/mẫu dữ liệu được phân vào một lóp
được xác định trước.
- Lớp của một bộ/mẫu dữ liệu được xác định bởi
thuộc tính gán nhãn lớp
- Tập các bộ/mẫu dữ liệu huấn luyện-tập huấn
luyện – được dùng để xây dựng mô hình.
- Mô hình được biểu diễn bởi các luật phân
lớp,các cây quyết định hoặc các công thức toán
học.
- Bước 2: Sử dụng mô hình
- Phân lớp cho những đối tượng mới hoặc chưa
được phân lớp
- Đánh giá độ chính xác của mô hình
+ Lớp biết trước của một mẫu/bộ dữ liệu đem
kiểm tra được so sánh với kết quả thu được từ
mô hình.
+ Tỉ lệ chính xác bằng phần trăm các mẫu/bộ
dữ liệu được phân lớp đúng bởi mô hình trong
số các lần kiểm tra.
- - Các thuật toán phân lớp dữ liệu phổ
biến:
+ Thuật toán cây quyết định
+ Thuật toán SVM
+ Thuật toán phân lớp Bayes
+ Thuật toán phân lớp K người láng giềng gần
nhất.
- 2.Tại sao lại sử dụng thuật toán SVM
trong phân lớp dữ liệu?
- SVM rất hiệu quả để giải quyết bài toán dữ liệu
có số chiều lớn(ảnh của dữ liệu biểu diễn
gene,protein, tế bào)
- SVM giải quyết vấn đề overfitting rất tốt (dữ liệu
có nhiễu và tách dời nhóm hoặc dữ liệu huấn
luyện quá ít)
- Là phương pháp phân lớp nhanh
- Có hiệu suất tổng hợp tốt và hiệu suất tính toán
cao.
- II.Thuật toán SVM
1.Định nghĩa:
- Là phương pháp dựa trên nền tảng của lý
thuyết thống kê nên có một nền tảng toán học
chặt chẽ để đảm bảo rằng kết quả tìm được
là tối ưu
- Là thuật toán học giám sát (supervied
learning)được sử dụng cho phân lớp dữ liệu.
- Là 1 phương pháp thử nghiệm,đưa ra 1 trong
những phương pháp mạnh và chính xác nhất
trong số các thuật toán nổi tiếng về phân lớp
dữ liệu
- - SVM là một phương pháp có tính tổng quát cao
nên có thể được áp dụng cho nhiều loại bài toán
nhận dạng và phân loại
-Ý tưởng chính của SVM: Là chuyển tập mẫu
từ không gian biểu diễn Rn của chúng sang một
không gian Rd có số chiều lớn hơn. Trong không
gian Rd, tìm một siêu phẳng tối ưu để phân
hoạch tập mẫu này dựa trên phân lớp của
chúng, cũng có nghĩa là tìm ra miền phân bố của
từng lớp trong không gian Rn để từ đó xác định
được phân lớp của 1 mẫu cần nhận dạng
- I.Thuật toán SVM
2. Mục đích
- Là tìm ra hàm phân lớp hiệu quả nhất để
phân biệt thành phần của các lớp trong việc
huấn luyện dữ liệu.
+ Ví dụ trong tập dữ liệu phân chia tuyến tính
, hàm phân loại tuyến tính tương ứng với 1 siêu
phẳng f(x) phân chia 2 tập hợp.khi hàm này đc
xác định thì bất kỳ 1 thể hiện mới sẽ được
Xn
phân lớp đơn giản bằng việc xét dấu của hàm f(
) nếu X n thuộc X n tập các giá dương thì
về
f( X n )>0 ngược lại thì thuộc tập các giá trị âm.
- I. Thuật toán SVM
3. Mô hình giải thuật
- Tính chất nổi trội của SVM là đồng thời cực tiểu
lỗi phân lớp và cực đại khoảng cách lề giữa các lớp
+ Giả sử có 1 số điểm dữ liệu thuộc một
trong hai lớp,và mục tiêu của ta là xác định xem dữ
liệu mới thêm vào sẽ thuộc lớp nào.Ta coi mỗi điểm
dữ liệu như một vector p chiều và chúng ta muốn
biết là liệu có tách được những điểm đó bằng một
siêu phẳng p-1 chiều hay không( được gọi là phân
loại tuyến tính)
- + Xem dữ liệu đầu vào như 2 tập vector n
chiều,một SVM sẽ xây dựng một siêu phẳng riêng
biệt trong không gian đó sao cho nó tối đa hóa biên
lề giữa hai tập dữ liệu.
+ Để tính lề,hai siêu phẳng song song được xây
dựng,mỗi cái nằm ở một phía của siêu phẳng phân
biệt và chúng được đẩy về phía hai tập dữ liệu.
+ Một cách trực quan,một phân biệt tốt sẽ thu
được bởi siêu phẳng có khoảng cách lớn nhất đến
các điểm lân cận của hai lớp,vì lề càng lớn thì sai
số tổng quát hóa của bộ phân lớp càng tốt hơn.
- H3 (green) doesn't separate the 2 classes. H1 (blue) does, with a
small margin and H2 (red) with the maximum margin.
- Trình bày với bộ phân lớp nhị phân
- Cho tâp dữ liêu hoc gồm n dữ liệu gắn nhãn
̣ ̣ ̣
D={(x1, y1), (x1, y1),..., (xn, yn)} với yi ∈ {-1,1} là
môt số nguyên xac đinh lớp cua xi. Môi xi là môt
̣ ́ ̣ ̉ ̃ ̣
văn ban được biêu diên dưới dạng môt vector
̉ ̉ ̃ ̣
thực d chiêu. Bộ phân lớp tuyên tinh (mô hình
̀ ́ ́
phân lớp) được xac đinh thông qua một siêu
́ ̣
phăng có dang:
̉ ̣
f(x) = w.x – b = 0
trong đó: w là vector pháp tuyến của siêu
phẳng và b đong vai trò là tham số mô hinh
́ ̀
- Bộ phân lớp nhị phân được xác
định thông qua dấu của f(x):
- - Để tìm được siêu phẳng phân cách có lề cực
đại,xây dựng các vector hỗ trợ và các siêu
phẳng song song với siêu phẳng phân cách
và gần vector hỗ trợ nhất,đó là các hàm :
w.x – b = 1
w.x – b = -1 2
- Khoảng cách giữa 2 siêu phẳng là w do đó
cần phải cực tiểu hóa w để đảm bảo với
mọi i ta có:
w.x – b > 1 cho lớp thứ nhất
w.x – b
- Hình 1. Biểu diễn siêu phẳng lề cực đại cho bộ
phân lớp SVM trên 2 lớp
- - Để đảm bảo là luôn tìm đc siêu phẳng phân cách
có lề cực đại,hàm xác định SVM sẽ làm cực đại
ur
u
hàm sau với vector w và hằng số b:
t uu ur
ru t
Lp = 1 − � i yi(w.xi − b) + � i
α α
2 i =1 i =1
Trong đó : + t là số lượng mẫu thử
+α i với i =1…t là các số nguyên dương
thỏa mãn đạo hàm Lp theo biến α i =0. α i được
gọi là nhân tử lagrange(điểm yên ngựa) và Lp
được gọi là hàm lagrange
ur
u
+ vector w và hằng số b xác định mặt
phẳng
nguon tai.lieu . vn