Đề tài Nghiên cứu thuật toán máy SVM

 TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT
 KHOA CÔNG NGHỆ THÔNG TIN
 Môn: KHAI PHÁ DỮ LIỆU
ĐỀ TÀI: Phương pháp Support Vector Machines
 Danh sách sinh viên :
 - Trần Thị Thơm 14110192
 - Huỳnh Nhật Thành 14110178
 - Nguyễn Quang Nhật 14110137
 TP.HCM, ngày 26 tháng 04 năm 2017 1. Nội dung chung
 ➢ Tên đề tài: 
 Phương pháp Support Vector Machines
 ➢ Giảng viên hướng dẫn:
 Quách Đình Hoàng
 ➢ Sinh viên thực hiện:
 - Trần Thị Thơm
 - Huỳnh Nhật Thành
 - Nguyễn Quang Nhật
 ➢ Thông tin liên lạc của sinh viên
 Stt Tên MSSV Email
 1 Trần Thị Thơm 14110192 14110192@student.hcmute.edu.vn
 2 Huỳnh Nhật Thành 14110178 14110178@student.hcmute.edu.vn
 3 Nguyễn Quang Nhật 14110137 14110137@student.hcmute.edu.vn
 ➢ Chương trình, ứng dụng sử dụng:
 - Chương trình sử dụng: R studio
 - Ứng dụng: 
2. Phân công thực hiện
 Phân công Thực hiện Tiến độ
 Cả nhóm Tìm kiếm, tổng hợp tài liệu 100%
 Lên nội dung cần làm cho đề tài, thời 
 gian thực hiện.
 Trình bày slide
 Sửa lỗi
 Nguyễn Quang Nhật Tìm hiểu, xây dựng nội dung cơ bản 80%
 Huỳnh Nhật Thành Triển khai nội dung chi tiết từng phần 90%
 Trần Thị Thơm Tổng hợp, viết bài báo cáo. 90% MỞ ĐẦU
 Trong thời đại công nghệ thông tin hiện nay, sự phát triển của công nghệ kéo 
theo sự gia tăng rất lớn của lưu lượng thông tin lưu trữ và trao đổi. Do đó, yêu cầu 
về tổ chức lưu trữ và truy cập thông tin sao cho hiệu quả được đặt lên hàng đầu. 
Hướng giải quyết được đưa ra là tổ chức, tìm kiếm và phân loại thông tin một cách 
hiệu quả. Bản thân con người trong đời sống cũng tiếp nhận thế giới xung quanh 
thông qua sự phân loại và tổ chức ghi nhớ tri thức một cách hiệu quả. Phân loại 
thông qua các lớp và mô tả các lớp giúp cho tri thức được định dạng và lưu trữ 
trong đó.
 Có nhiều phương pháp phân loại đã được nghiên cứu và được áp dụng. Hiện 
nay, phương pháp phân loại Support Vector Machines là một trong những phương 
pháp mạnh và hiệu quả để giải quyết các bài toán lớp phi tuyến được Vapnik và 
Chervonenkis giới thiệu vào năm 1995. Vì vậy, nhóm em chọn đề tài “Nghiên cứu 
thuật toán máy SVM”.
 Lý do chọn đề tài
 Vấn đề phân lớp và dự đoán là khâu rất quan trọng trong học máy và khai 
phá dữ liệu, phát triển tri thức. Kỹ thuật Support Vector Machines (SVM) được 
đánh giá là công cụ mạnh và tinh vi nhất hiện nay cho những bài toán phân lớp phi 
tuyến. Nhiều ứng dụng đã và đang được xây dựng dựa trên kỹ thuật SVM rất hiệu 
quả.
 Nội dung cơ bản bao gồm
Chương 1: Giới thiệu Support Vector Machines
Chương 2: Tại sao chọn Support Vector Machines
Chương 3: Đặt vấn đề
Chương 4: Bài toán phân 2 lớp với SVM
Chương 5: So sánh và cải tiến SVM 
Phần kết luận
Phần Demo
Phần tài liệu tham khảo CHƯƠNG 1: GIỚI THIỆU VỀ SUPPORT VECTOR MACHINE
1. Giới thiệu
 Bài toán phân lớp (Classification) và dự đoán (Prediction) là hai bài 
 toán cơ bản và có rất nhiều ứng dụng trong tất cả các lĩnh vực như: học máy, 
 nhận dạng, trí tuệ nhân tạo , . v. v. Trong đề tài này, chúng em sẽ đi sâu 
 nghiên cứu phương pháp Support Vector Machines (SVM), một phương 
 pháp rất hiệu quả hiện nay.
 Phương pháp SVM được coi là công cụ mạnh cho những bài toán 
 phân lớp phi tuyến tính được các tác giải Vapnik và Chervonenkis phát triển 
 mạnh mẽ năm 1995. Phương pháp này thực hiện phân lớp dựa trên nguyên 
 lý Cực tiểu hóa rủi ro có Cấu trúc SRM (Structural Risk Minimization), được 
 xem là một trong các phương pháp phân lớp giám sát không tham số tinh vi 
 nhất cho đến nay. Các hàm công cụ đa dạng của SVM cho phép tạo không 
 gian chuyển đổi để xây dựng mặt phẳng phân lớp.
2. Lịch sử
 Thuật toán Support Vector Machines (SVM) ban đầu tìm ra bởi 
 Vladimir N.Vapnik và dạng chuẩn hiện nay sử dụng lề mềm được tìm ra bởi 
 Vapnik và Corinna Cortes năm 1995.
3. Đị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à chính xác.
 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à một 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. 4. Ứng dụng
 - Nhận dạng: tiếng nói, ảnh, chữ viết tay (hơn mạng nơron)
 - Phân loại văn bản, khai mỏ dữ liệu văn bản
 - Phân tích dữ liệu theo thời gian
 - Phân tích dữ liệu gien, nhận dạng bệnh, công nghệ bào chế thuốc
 - Phân tích dữ liệu marketing
 CHƯƠNG 2: TẠI SAO CHỌN SUPPORT VECTOR MACHINES
 Sử dụng thuật toán Support vector machines có nhiều lơi ích:
 ✓ SVM rất hiệu quae để 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 gien, 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 rờ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.
 CHƯƠNG 3: ĐẶT VẤN ĐỀ
 1. Ý tưởng
 Cho trước một tập huấn luyện, được biểu diễn trong không gian 
 vector, trong đó mỗi tài liệu là một điểm, phương pháp này tìm ra một 
 siêu phẳng f quyết định tốt nhất có thể chia các điểm trên không gian này 
 thành hai lớp riêng biệt tương ứng là lớp “+” và lớp “-”. Chất lượng của 
 siêu phẳng này được quyết định bởi khoảng cách (gọi là biên) của điểm 
 dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khi đó, khoảng cách 
 biên càng lớn thì mặt phẳng quyết định càng tốt, đồng thời việc phân loại 
 càng chính xác.
 Ý tưởng của nó là ánh xạ (tuyến tính hoặc phi tuyến) dữ liệu vào 
 không gian các vector đặc trưng (space of feature vectors) mà ở đó một 
 siêu phẳng tối ưu được tìm ra để tách dữ liệu thuộc hai lớp khác nhau.
 Mục đích của phương pháp SVM là tìm được khoảng cách biên lớn 
 nhất. Đường tô đậm là siêu phẳng tốt nhất và các điểm được bao bởi hình 
 chữ nhật là những điểm gần siêu phẳng nhất, chúng được gọi là các 
 vector hỗ trợ (support vector). Các đường nét đứt mà các support vector 
 nằm trên đó được gọi là lề (margin).
2. Cơ sở lý thuyết
 SVM thực chất là một bài toán tối ưu, mục tiêu của thuật toán này là 
 tìm được một không gian F và siêu phẳng quyết định f trên F sao cho sai 
 số phân loại là thấp nhất.
 푛
 Cho tập mẫu D = {(x1, y1), (x2,y2), , (xl, yl)} với xi ∈ 푅 , thuộc 
 vào hai lớp nhãn yi ∈ {-1,1} là tập nhãn lớp tương ứng của các xi (-1 
 biểu thị lớp I, 1 biểu thị lớp II).
 Ta có, phương trình siêu phẳng chứa vector 푖 trong không gian:
 푖. 푤+ b = 0
 +1, 푖. 푤 + b > 0
 Đặt f( 푖) = sign( 푖. 푤+ b) ={ 
 ―1, 푖. 푤 + b < 0
 Như vậy, f( 푖) biểu diễn sự phân lớp của 푖 vào hai lớp như nêu trên.
 Ta nói yi = +1 nếu thuộc lớp I và yi = -1 nếu 푖 thuộc lớp II. CHƯƠNG 4: BÀI TOÁN PHÂN 2 LỚP VỚI SVM
 Bài toán đặt ra là: Xác định hàm phân lớp lớp để phân lớp các mẫu 
 trong tương lai, nghĩa là với một mẫu dữ liệu mới xi thì cần phải xác định 
 xi được phân lớp +1 hay lớp -1.
 Ta xét 3 trường hợp, mỗi trường hợp sẽ có 1 bài toán tối ưu, giải được 
 bài toán tối ưu đó sẽ tìm được siêu phẳng cần tìm.
1. Trường hợp 1
 Tập D có thể phân chia tuyến tính được mà không có nhiễu (tất cả các điểm 
 được gán nhãn +1 thuộc về phía dương của siêu phẳng, tất cả các điểm được 
 gán nhãn -1 thuộc về phía âm của siêu phẳng)
 Hình 2. Tập dữ liệu được phân chia tuyến tính
 Ta sẽ tìm siêu phẳng tách với w ∈ 푅푛 là vector trọng số, b ∈ 푅푛 là hệ số tự 
 do, sao cho:
 +1, 푖. 푤 + b > 0
 Đặt f( 푖) = sign( 푖. 푤+ b) ={ ∀( 푖, 푖) ∈ D
 ―1, 푖. 푤 + b < 0
 Lúc này ta cần giải toán tối ưu:
 푖푛 (퐿(푤)) = 1 ||푤||2
 2
 { 
 푖( 푖.푤 + ) ≥ 1,푖 = 1, ,푙 2. Trường hợp 2
 Tập dữ liệu D có thể phân chia tuyến tính được nhưng có nhiễu. Trong 
 trường hợp này, hầu hết các điểm đều được phân chia đúng bởi siêu phẳng. 
 Tuy nhiên có 1 số điểm bị nhiễu, nghĩa là: điểm có nhãn dương nhưng lại 
 thuộc phía âm của siêu phẳng, điểm có nhãn âm nhưng lại thuộc phía dương 
 của siêu phẳng.
 Hình 3. Tập dữ liệu phân chia tuyến tính nhưng có nhiễu
 Trong trường hợp này, ta sử dụng 1 biến mềm 휀푖 ≥ 0 sao cho: yi.( 풙풊. 
 풘+ b) ≥ ― 휺풊, i=1, ,l
 Bài toán tối ưu trở thành : 
 푖푛 (퐿(푤,휀)) = 1 ||푤||2 + ∑푙 휀 
 2 푖=1 푖
 { 
 푖( 푖.푤 + ) ≥ 1 ― 휀푖,푖 = 1, ,푙; 휀푖 ≥ 0
 Trong đó C là tham số xác định trước, định nghĩa giá trị ràng buộc, C 
 càng lớn thì mức độ phạm vi đối với những lỗi thực nghiệm (là lỗi xảy ra lúc 
 huấn luyện, tính bằng thương số của số phần tử lỗi và tổng số phần tử huấn 
 luyện) càng cao.
3. Trường hợp 3 Ta dữ liệu D không thể phân chia tuyến tính được, ta sẽ ánh xạ các vector dữ 
 liệu x từ không gian n chiều vào một không gian m chiều (m > n), sao cho 
 trong không gian m chiều, D có thể phân chia tuyến tính được.
 Hình 4. Tập dữ liệu không phân chia tuyến tính.
 Gọi ∅ là ánh xạ phi tuyến từ không gian 푅푛 vào không giam 푅 
 ∅: 푅푛 → 푅 
 Bài toán tối ưu trở thành:
 푖푛 (퐿(푤,휀)) = 1 ||푤||2 + ∑푙 휀 
 { 2 푖=1 푖
 푖 ∅( 푖).푤 + ≥ 1 ― 휀푖,푖 = 1, ,푙; 휀푖 ≥ 0
4. Bài toán phân đa lớp của SVM
 Để phân đa lớp thì kỹ thuật SVM sẽ chia không gian dữ liệu thành 2 phần và 
 tiếp tục với không gian đã được phân chia. Khi đó hàm quyết định phân dữ 
 liệu vào lớp thứ I sẽ là:
 푖( ) = 푤푖 ( ) + 푖
 Những phần tử x là support vector nếu thỏa điều kiện:
 1, ∈ 푖
 푖( ) = ―1, ∉ 푖
 Giả sử bài toán phân loại k lớp (k ≥ 2), ta sẽ tiến hành k(k-1)/2 lần phân 
 lớp nhị phân sử dụng phương pháp SVM. Mỗi lớp sẽ tiến hành phân tách với k-1 lớp còn lại để xác định k-1 hàm phân tách (chiến lược “một-đối-
 một” (one-against-one). 
 Kỹ thuật phân đa lớp bằng phương pháp hiện vẫn đang được tiếp tục 
 nghiên cứu và phát triển.
 LƯU Ý: CÁC BƯỚC CHÍNH CỦA PHƯƠNG PHÁP SVM
 ➢ Tiền xử lý dữ liệu: Phương pháp SVM yêu cầu được diễn tả như 
 các vector của các số thực. Như vậy nếu đầu vào chưa phải là số 
 thực thì ta cần tìm cách chuyển chúng về dạng số SVM. Tránh các 
 số quá lớn, thường nên co giãn dữ liệu để chuyển đoạn [-1,1] hoặc 
 [0,1].
 ➢ Chọn hàm hạt nhân: cần chọn hàm hạt nhân phù hợp tương ứng 
 cho từng bài toán cụ thể để đạt được độ chính xác cao trong quá 
 trình học tập.
 ➢ Thực hiện việc kiểm tra chéo để xác định các tham số cho ứng 
 dụng.
 ➢ Sử dụng các tham số cho việc huấn luyện tập mẫu.
 ➢ Kiểm thử tập dữ liệu Test.
 CHƯƠNG 5: SO SÁNH VÀ MỘT SỐ CẢI TIỀN
 Một số phương pháp như neuron, fuzy logic, mạng fuzzy-neuron, , 
cũng được sử dụng thành công để giải quyết bài toán phân lớp. Ưu điểm của 
phương pháp này là không cần xác định mô hình đối của đối tượng.
SVM có 2 đặc trưng cơ bản:
- Nó luôn kết hợp với các dữ liệu có ý nghĩa về mặt vật lý, do vậy dễ dàng 
 giải thích được một cách tường minh,
- Cần một tập các mẫu huấn luyện rất nhỏ.
Phương pháp SVM hiện nay được xem là một công cụ mạnh và tinh vi nhất 
hiện any cho những bài toán phân lớp phi tuyến. Nó có một số biến thể như 
C-SVC, v-SVC. Cải tiến mới nhất hiện nay của phương pháp SVM đã được