Đăng ký Đăng nhập
Trang chủ Học bán giám sát SVM-KNN và ứng dụng thử nghiệm phân lớp văn bản giao thông vận ...

Tài liệu Học bán giám sát SVM-KNN và ứng dụng thử nghiệm phân lớp văn bản giao thông vận tải

.PDF
44
518
89

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG HẢI YẾN HỌC BÁN GIÁM SÁT SVM-kNN VÀ ỨNG DỤNG THỬ NGHIỆM PHÂN LỚP VĂN BẢN GIAO THÔNG VẬN TẢI LUẬN VĂN THẠC SĨ Hà Nội - 2012 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG HẢI YẾN HỌC BÁN GIÁM SÁT SVM-kNN VÀ ỨNG DỤNG THỬ NGHIỆM PHÂN LỚP VĂN BẢN GIAO THÔNG VẬN TẢI 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Ĩ CÁN BỘ HƯỚNG DẪN: PGS. TS. HÀ QUANG THỤY Hà Nội - 2012 MỤC LỤC DANH SÁCH CÁC HÌNH ................................................................................. 3 DANH SÁCH CÁC BẢNG ............................................................................... 4 DANH SÁCH CÁC TỪ VIẾT TẮT ................................................................... 5 MỞ ĐẦU ........................................................................................................... 6 Chương 1: Phương pháp phân lớp SVM và kNN................................................ 7 1.1. Phương pháp SVM .............................................................................. 7 1.1.1. Tách tuyến tính .......................................................................... 7 1.1.2. Tách phi tuyến ......................................................................... 11 1.1.3. Phân lớp đa lớp với SVM ........................................................ 14 1.2. Phương pháp kNN ........................................................................... 159 1.3. So sánh SVM với kNN ...................................................................... 18 Chương 2: Phương pháp SVM-kNN phân lớp văn bản ..................................... 20 2.1. Giới thiệu .......................................................................................... 20 2.2. Học bán giám sát SVM-kNN ............................................................ 22 2.2.1. Ý tưởng ................................................................................... 22 2.2.2. Thuật toán SVM-kNN ............................................................. 22 2.3. Áp dụng SVM phân lớp văn bản tiếng Việt ....................................... 24 2.3.1. Phát biểu bài toán .................................................................... 24 2.3.2 Tiền xử lý dữ liệu ..................................................................... 26 2.3.3 Trích chọn đặc trưng................................................................. 27 2.3.4. Phương pháp biểu diễn văn bản ............................................... 29 2.3.5. Đánh giá bộ phân lớp. .............................................................. 31 2.3.5.1. các độ đo .............................................................................. 32 Chương 3: Thực nghiệm phân lớp văn bản tiếng việt với thuật toán phân lớp bán giám sát SVM-kNN .......................................................................................... 33 3.1. Môi trường và các công cụ sử dụng thực nghiệm .............................. 33 3.2. Xây dựng tập dữ liệu ......................................................................... 34 3.2.1. Phương pháp thu thập dữ liệu .................................................. 34 3.2.2. Tiền xử lý dữ liệu .................................................................... 36 3.2.3. Chọn từ đặc trưng và biểu diễn TF x DF.................................. 37 3.2.4. Thực nghiệm phân lớp bán giám sát SVM-kNN ...................... 37 KẾT LUẬN ...................................................................................................... 40 TÀI LIỆU THAM KHẢO ................................................................................ 41 3 DANH SÁCH CÁC HÌNH Hình 1: Minh họa dữ liệu có thể phân tách một cách tuyến tính ......................... 8 Hình 2: Lề của một siêu phẳng ........................................................................... 8 Hình 3: Siêu phẳng có lề lớn .............................................................................. 9 Hình 4: Minh họa vector hỗ trợ ........................................................................ 10 Hình 5: Trường hợp dữ liệu không thể phân tách bằng một siêu phẳng ............ 12 Hình 6: Hàm ánh xạ từ dữ liệu phi tuyến sang dữ liệu tuyến tính ..................... 12 Hình 7: Các bước trong mô hình học máy có giám sát ..................................... 15 Hình 8: Minh họa vector hỗ trợ và vector biên. ................................................ 22 Hình 9: Mô hình đề xuất bởi Kunlun Li và cộng sự [7] .................................... 23 Hình 10: Các pha chính trong quá trình phân lớp văn bản ................................ 25 Hình 11: Mô hình hóa quá trình tiền xử lý dữ liệu. ........................................... 26 Hình 12: Các nội dung sẽ tách ra từ web .......................................................... 35 Hình 13: độ chính xác của bộ phân lớp trong 10 lần huấn luyện. ...................... 39 4 DANH SÁCH CÁC BẢNG Bảng 1: Một số từ nhiễu cần được loại bỏ ........................................................ 27 Bảng 2: Cấu hình hệ thống thử nghiệm ............................................................ 33 Bảng 3: Công cụ phần mềm sử dụng ................................................................ 33 Bảng 4: các từ khóa xác định tiều đề và nội dung bài ....................................... 36 Bảng 5: Một số từ dừng loại bỏ trong quá trình xử lý ....................................... 36 Bảng 6: kết quả sau khi thu thập dữ liệu ........................................................... 37 Bảng 7: văn bản thuộc văn bản giao thông và không thuộc .............................. 37 Bảng 8:độ chính xác 10 lần huấn luyện với k = 5, n = 20 ................................. 39 5 DANH SÁCH CÁC TỪ VIẾT TẮT SVM Support Vector Machine kNN K Nearest Neighbors MMH Maximum marginal hyperplane kNN-SVM k Nearest Neighbors- Support Vector Machine GTVT Giao thông vận tải TFIDF Term Frequency Inverse Document Frequency TF Term frequency DF Document Frequency URL Uniform Resource Locator DAGSVM Direted Acyclic Graph Support Vector Machine 6 MỞ ĐẦU Khối lượng khổng lồ các văn bản tiếng Việt trên mạng Internet đặt ra một thách thức nhằm phân lớp tự động hoặc bán tự động các văn bản này nhằm cung cấp những thông tin tập trung và có giá trị cho một ngành nghề cụ thể nào đó. Trong các phương pháp phân lớp văn bản phổ biến thì phương pháp SVM (Support Vertor Machine) được sử dụng với độ tin cậy cao. Tuy nhiên SVM không tối ưu hóa thời gian tính toán sai số lớn trong việc ước lượng khoảng giữa hai vector. Tức là khi các vector có số chiều lớn thì tốc độ của SVM bị hạn chế. Trong luận văn này, tôi nghiên cứu phương pháp lai giữa k-láng giềng gần (kNN) với SVM nhằm thực hiện phân đa lớp văn bản, lý do chính là nhằm tăng khả năng tính toán trong cả quá trình huấn luyện và thực hiện phân lớp, kết quả là phương pháp này đạt kết quả khá hơn trong thực tế thử nghiệm của luận văn. Nội dung luận văn gồm 3 chương: Chương 1: Giới thiệu khái quát phương pháp phân lớp SVM và kNN. Chương 2: Giới thiệu giải pháp chi tiết các thuật toán lai SVM-kNN theo hai phương pháp [5] và [7], quan điểm và các viễn cảnh cho các thuật toán lai SVM-kNN tương ứng. Giới thiệu mô hình của thuật toán. Chương 3: Dựa vào mô hình ở chương 2, tiến hành thực nghiệm việc phân lớp văn bản tiếng Việt theo hai nhóm: nhóm văn bản liên quan tới ngành Giao thông vận tải và nhóm không liên quan. Để làm rõ mô hình cũng như 3 pha chính trong mô hình, các thực nghiệm trên các nội dung văn bản lấy tự động từ internet được tiến hành. Luận văn tập trung đánh giá kết quả thực nghiệm từ 2 pha: tạo tập huấn luyện cho SVM-kNN và phân lớp SVM-kNN 7 Chương 1: Phương pháp phân lớp SVM và kNN 1.1. Phương pháp SVM Phương pháp máy vector hỗ trợ (Support Vector Machine – SVM) là phương pháp phân lớp dựa trên lý thuyết học thống kê được Corters và Vapnik giới thiệu vào năm 1995 để giải quyết vấn đề nhận dạng mẫu hai lớp. Nó có khả năng xử lý các tập dữ liệu cả khả tách tuyến tính lẫn không khả tách tuyến tính. Bản chất của thuật toán này là nó xây dựng một siêu phẳng để phân chia tập dữ liệu khả tách tuyến tích thành 2 nửa. Trong trường hợp nếu tập dữ liệu là không khả tách tuyến tính thì nó sẽ sử dụng một hàm nhân (kernel function) để chuyển đổi tập dữ liệu ban đầu sang một không gian mới có số chiều lớn hơn để xử lý. Đây là phương pháp tiếp cận phân tách vector rất hiệu quả. Các thử nghiệm cho thấy, phương pháp SVM có khả năng phân lớp khá tốt đối với bài toán phân lớp văn bản cũng như trong nhiều ứng dụng khác (như nhận dạng chữ viết tay, nhận dạng khuôn mặt…). 1.1.1. Tách tuyến tính Thuật toán SVM cơ sở là trường hợp tập dữ liệu huấn luyện chỉ có 2 lớp và nó phân bố ở dạng vector và ta có thể phân tách chúng một cách tuyến tính bằng một siêu phẳng. Gọi D là tập dữ liệu huấn luyện: (X1, y1), (X2, y2), … , (X|D|, y|D|), trong đó Xi là các phần tử dữ liệu và yi là nhãn tương ứng của nó. Giá trị của yi có thể nhận là một trong 2 giá trị {-1, +1}. Để có thể hiển thị được dữ liệu ta lấy trường hợp dữ liệu được biểu diễn bằng 2 thuộc tính A1 và A2, và các phần tử dữ liệu của tập D được minh họa bằng hình 1. Từ hình vẽ cho chúng ta thấy dữ liệu có thể phân tách thành 2 nửa bằng một đường thẳng. Tuy nhiên số lượng các đường thẳng có thể dùng để phân tách tập dữ liệu trên thành 2 nửa là vô hạn (hình 1 minh họa một số đường thằng vẽ bằng đường đứt nét có thể dùng để phân tách dữ liệu thành 2 lớp riêng biệt). Trong trường hợp dữ liệu được biểu diễn bằng 3 thuộc tính (3 chiều) thì đường thẳng sẽ được thay thế bằng mặt phẳng (plane), và trường hợp tổng quát (n chiều) thì chúng ta dùng siêu phẳng (hyperplane) có số chiều n-1 để tách tập dữ liệu khả tách tuyến tính. Như vậy, tập dữ liệu hai lớp n-chiều được gọi là khả tách tuyến tính nếu tồn tại một siêu phẳng tuyến tính (n-1 chiều) tách không gian n chiều thành hai phần, phần này chứa dữ liệu chỉ thuộc một lớp và phần kia chứa dữ liệu chỉ thuộc lớp còn lại. Vậy vấn đề chủ yếu trong SVM là phải làm sao tìm ra siêu phẳng tốt nhất, thuật toán SVM sẽ cố gắng tìm siêu phẳng có lề lớn nhất (maximum marginal 8 hyperplane - MMH). Khái niệm lề có thể được minh họa trên Hình 2, lề của siêu phẳng h là tổng khoảng cách từ h đến 2 siêu phẳng là tiếp tuyến với 2 miền dữ liệu (ở hai bên siêu phẳng) và song song với siêu phẳng h. Hay nói một cách khác, lề của siêu phẳng h là tổng khoảng cách của 2 phần tử dữ liệu (ở 2 mặt của siêu phẳng) trong tập dữ liệu huấn luyện gần với h nhất. Hình 3 minh họa một siêu phẳng khác có lề lớn hơn so với lề của siêu phẳng trong hình 2. Lý do của việc tìm siêu phẳng có lề lớn nhất là ta hy vọng nó sẽ nó có thể phân lớp tốt nhất, nó cho chúng ta tỉ lệ lỗi phân lớp thấp nhất. Một siêu phẳng phân lớp có thể biểu diễn bằng công thức: W X + b = 0 (1.1) Hình 1: Minh họa dữ liệu có thể phân tách một cách tuyến tính Hình 2: Lề của một siêu phẳng 9 Hình 3: Siêu phẳng có lề lớn trong đó W là vector trọng số W={w1, w2, …, wn}; và n là số lượng các thuộc tính mô tả tập dữ liệu D; b là một số thực được gọi là độ lệch. Trong trường hợp đơn giản nhất, ta xét số lượng thuộc tính là 2 ký hiệu là A1 và A2. Khi đó phần tử dữ liệu X được biểu diễn bằng X=(x1, x2) với x1, x2 là giá trị tương ứng của thuộc tính A1 và A2. Nếu ta coi b cũng là một trọng số thì công thức (1.1) sẽ được có dạng: w0 + w1x1 + w2x2 = 0 (1.2) Khi đó các điểm nằm phía trên siêu phẳng sẽ thỏa mãn điều kiện: w0 + w1x1 + w2x2 > 0 (1.3) Các điểm nằm phía dưới siêu phẳng sẽ thỏa mãn điều kiện: w0 + w1x1 + w2x2 < 0 (1.4) Hai siêu phẳng tiếp tuyến với dữ liệu và song song với siêu phẳng phân lớp h có thể được biểu diễn bằng công thức: H1 : w0 + w1x1 + w2x2  +1, với yi = +1 (1.5) H2 : w0 + w1x1 + w2x2  - 1, với yi = -1 (1.6) Do đó, nói một cách chính xác hơn thì các điểm ở trên siêu phẳng H1 sẽ được phân vào lớp +1 và các điểm ở dưới siêu phẳng H2 sẽ được phân vào lớp 1. Bằng cách nhân cả 2 vế của 2 bất đẳng thức (1.5) và (1.6) với yi ta được bất đẳng thức chung: yi (w0 + w1x1 + w2x2)  1, với i (1.7) 10 Để xác định 2 siêu phẳng H1 và H2 ta chỉ cần dựa vào các phần tử dữ liệu huấn luyện nằm trên 2 siêu phẳng (các phần tử dữ liệu thỏa mãn yi (w0 + w1x1 + w2x2) = 1). Những phẩn tử dữ liệu này được gọi là các vector hỗ trợ (support vector). Chúng cũng chính là các phần tử dữ liệu nằm gần siêu phẳng phân chia h nhất. Hình 4 minh họa các vector hỗ trợ (chúng là các hình được bôi đen). Trong trường hợp tổng quát thì các vector hỗ trợ chính là các phần tử khó phân lớp nhất nhưng lại cung cấp nhiều thông tin nhất cho việc phân lớp (giúp ta xác định các siêu phẳng tiếp tuyến). Từ công thức (1.7) ở trên chúng ta có thể suy ra công thức tính độ lớn của lề. Khoảng cách từ một điểm bất kỳ từ siêu phẳng H1 đến siêu phẳng phân lớp h là 1 , trong đó W là chuẩn Euclidean của W: W W  W  W  w12  w22  ...  wn2 (1.8) Tương tự khoảng cách từ một điểm bất kỳ từ siêu phẳng H2 đến siêu phẳng phân lớp h cũng là 1 2 , và độ lớn của lề sẽ là . Việc tìm ra siêu phẳng W W có lề lớn nhất người ta dựa vào việc giải công thức (1.7), việc này có thể giải quyết bằng bài toán tối ưu toàn phương lồi (convex quadratic optimization). Chi tiết cách giải bài toán này sẽ không được trình bày trong khuôn khổ cuốn giáo trình này. Hình 4: Minh họa vector hỗ trợ Với SVM, sau khi tìm được siêu phẳng có lề lớn nhất MMH, siêu phẳng này có thể được viết lại dựa trên công thức Lagrangian như sau: 11   l f X T   yi i X i X T  b0 (1.9) i 1 trong đó yi là nhãn của các vector hỗ trợ Xi; XT là một phần tử dữ liệu kiểm tra; i và b0 là các số thực, chúng là các tham số được xác định thông qua quá trình tối ưu; và l là số lượng các vector hỗ trợ. Cho một phần tử dữ liệu mới XT nếu sign(f(XT)) =+1 thì phần tử XT nằm trên siêu phẳng MMH, SVM sẽ dự đoán nhãn của XT là +1, ngược lại nó sẽ dự đoán XT thuộc lớp -1. 1.1.2. Tách phi tuyến Trong các bài toán phân lớp thực tế có thể gặp nhiều miền dữ liệu không thể phân tách một cách tuyến tính như trong hình 5. Với ví dụ minh họa này, ta thấy không thể tồn tại một siêu phẳng nào có thể phân tách tập dữ liệu (được ký hiệu bằng các hình tròn rỗng và hình tròn được tô đen) thành 2 nửa. Tuy nhiên SVM có thể mở rộng để phân lớp được các dữ liệu không thể phân tách tuyến tính (linearly inseparable data hay non-linearly separable data) hay gọi đơn giản là dữ liệu không tuyến tính (nonlinear data) hay dữ liệu phi tuyến. SVM mở rộng này có khả năng tìm được ranh rới (boundary) phân lớp, hay siêu diện không tuyến tính (nonlinear hypersurface) (hay siêu diện phi tuyến) từ không gian dữ liệu đầu vào. SVM được mở rộng để xử lý dữ liệu phi tuyến theo 2 bước chính như sau: 1. Bước đầu tiên chúng ta chuyển không gian dữ liệu đầu vào thành một không gian dữ liệu có số chiều lớn hơn bằng một ánh xạ không tuyến tính (ánh xạ phi tuyến). Có rất nhiều ánh xạ phi tuyến có thể được sử dụng trong bước này (sẽ được trình bày ở dưới). 2. Khi dữ liệu đã được chuyển sang không gian có số chiều lớn hơn, bước tiếp theo ta tìm siêu phẳng tuyến tính để phân lớp dữ liệu trên không gian mới. Để hiểu hơn về phương pháp xử lý của SVM ta có thể xem minh họa trong hình 6, trong đó hình 6 a) mô tả không của gian dữ liệu đầu vào (nó được biểu diễn bằng không gian 2 chiều), rõ ràng với phân bố dữ liệu như thế này thì ta không thể dùng một siêu phẳng để phân tách 2 lớp ra thành 2 phần độc lập nhau. Sau khi sử dụng hàm ánh xạ, không gian dữ liệu đầu vào sẽ được chuyển sang không gian mới có số chiều cao hơn (3 chiều), đặc biệt trong không gian dữ liệu mới này ta có thể sử dụng một siêu phẳng để phân tách dữ liệu thành 2 lớp. 12 Hình 5: Trường hợp dữ liệu không thể phân tách bằng một siêu phẳng a) Không gian ban đầu (2 chiều) b) Không gian mới (3 chiều) Hình 6: Hàm ánh xạ từ dữ liệu phi tuyến sang dữ liệu tuyến tính Ví dụ trong một miền dữ liệu 3 chiều, một phần tử dữ liệu sẽ được biểu diễn bằng vector X=(x1, x2, x3), sau khi sử dụng một hàm ánh xạ sang không gian mới có 6 chiều, phần tử X sẽ biến thành Z, sao cho Z=ô(X)=(x1, x2, x3, x1*x1, x1*x2, x1*x3). Giả sử sau khi biến đổi, dữ liệu trong không gian mới sẽ có thể phân lớp tuyến tính, và ta có thể dùng một siêu phẳng để phân tách dữ liệu thành 2 nửa, khi đó siêu phẳng h sẽ được biểu diễn bằng công thức h(Z)=W*Z+b, trong đó W là vector trọng số và Z là vector biểu diễn dữ liệu trong không gian mới và b là một số thực giống như công thức biểu diễn siêu phẳng 1. Khi diễn giải công thức này ra ta có công thức biểu diễn siêu phẳng là: h(Z) = w1x1 + w2x2 + w3x3 + w4x1x1 + w5x1x2 + w6x1x3 + b = w1z1 + w2z2 + w3z3 + w4z4 + w5z5 + w6z6 + b 13 Khi mở rộng thêm sức mạnh của SVM, lại có thêm vấn đề cần giải quyết. Cụ thể là độ phức tạp thuật toán sẽ tăng lên bởi vì ta phải sử dụng thêm hàm ánh xạ. Rất may là tồn tại giải pháp cho vấn đề này, chú ý công thức (1.8), ta phải thực hiện phép nhân tích vô hướng XiXT (trong đó Xi và XT đều là các vector trong không gian dữ liệu ban đầu) hay viết XiXj cho đơn giản: X i  X j   xik  x jk , trong đó xik là các giá trị biểu diễn phần tử dữ liệu Xi và xjk k là các giá trị biểu diễn phần tử dữ liệu Xj. Khi chuyển sang không gian mới, tích vô hướng trên sẽ được tính toán bằng (Xi)(Xj) trong đó  là hàm ánh xạ. Tuy nhiên, một mẹo toán học rất hay ở đây là, thay vì tính tích vô hướng trên dữ liệu ở không gian dữ liệu mới, ta sử dụng thì ta có thể sử dụng một hàm nhân (kernel function) K cho kết quả tương tự như sau: K X i , X j   ( X i )X j  (1.10) Bằng cách sử dụng hàm tương đương này, thì ở bất kỳ đâu xuất hiện (Xi)(Xj) thì ta thay thế bằng hàm K(Xi,Xj). Do đó, việc tính toán về bản chất sẽ được thực hiện trên không gian dữ liệu ban đầu – không gian có khả năng có số chiều nhỏ hơn nhiều. Sau khi sử dụng hàm nhân thay thế, ta có thể sử dụng thuật toán tìm kiếm siêu phẳng phân lớp mà cũng không cần quan tâm đến ánh xạ biến đổi cụ thể là gì. Các đặc điểm của hàm nhân có thể sử dụng để thay thế hàm nhân tích vô hướng đã được nghiên cứu. Dưới đây xin trình bày một số hàm nhân phổ biến, nó thường được cài đặt trong các gói phần mềm cài đặt thuật toán SVM (chẳng hạn như thư viện libSVM [4], hay thư viện Weka[8]): 1. Hàm nhân đa thức cấp h: K X i , X j   X i  X j  1 h (1.11) 2. Hàm nhân Gaussian radial cơ bản: K X i , X j   e xi  x j 2 / 2 2 (1.12) 3. Hàm nhân đa sigmoid K X i , X j   tan(X i  X j   ) (1.13) 14 Một số hàm nhân khác ta có thể tham khảo và thử nghiệm từ bộ phần mềm cài đặt thuật toán SVM có tên là Accord.NET1. Vấn đề thứ 2 là liệu có tồn tại một hàm nhân nào có thể biến các tập dữ liệu phi tuyến bất kỳ sang không gian dữ liệu tuyến tính. Câu trả lời có lẽ là không, tùy vào từng loại dữ liệu mà sẽ có một hoặc một số hàm nhân phù hợp. Trong nhiều trường hợp ta phải chọn thử nhiều hàm nhân khác nhau để chọn ra hàm nhân phù hợp với tập dữ liệu đang xử lý nhất. 1.1.3. Phân lớp đa lớp với SVM Như ta đã nói ở trên thuật toán SVM chỉ hoạt động với dữ liệu có 2 lớp, trong thực tế số lượng lớp của dữ liệu có thể rất lớn. Tuy nhiên cũng đã có giải pháp để mở rộng SVM cho bài toán phân lớp có nhiều lớp. Bài toán phân đa lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong những phương pháp cải tiến đó là sử dụng thuật toán 1-against-all [10]. ý tưởng cơ bản là chuyển bài toán phân lớp nhiều lớp thành nhiều bài toán phân lớp nhị phân như sau: • Giả sử tập dữ liệu mẫu (x1,y1),..., (xm,ym) với xi là một vector n chiều và yi Y là nhãn lớp được gán cho vector xi (có m nhãn lớp khác nhau) • Biến đổi tập Y ban đầu thành m tập có hai lớp con Zi={yi,{Y - yi}} • Áp dụng SVM phân lớp nhị phân cơ bản với m tập Zi để xây dựng siêu phẳng cho phân lớp này. Như vậy ta sẽ có m bộ phân lớp nhị phân. Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM. Nhược điểm chính của phương pháp này, đôi khi được gọi là winnertake-all, chính là đặc điểm heuristic của nó. Những máy phân lớp nhị phân được sử dụng huấn luyện trên các lớp khác nhau, và như vậy là không rõ ràng khi so sánh các đầu ra giá trị thực của chúng cho dù có chuyển đổi giá trị thực thành xác suất lớp. 1 http://accord-net.origo.ethz.ch/ 15 1.2. Phương pháp kNN Tư tưởng chung của các thuật toán học máy có giám sát là thuật toán sẽ phân tích dữ liệu huấn luyện để tìm ra mô hình biểu diễn dữ liệu, sau đó ta có thể dùng một tập dữ liệu khác để kiểm thử độ chính xác của thuật toán như minh họa trên hình 7. Như mô tả ở trên hình, tập dữ liệu huấn luyện sẽ được sử dụng để tạo ra mô hình (trong quá trình huấn luyện thuật toán). Yêu cầu trong thực tế là việc phân lớp vẫn phải làm việc mà không hề tồn tại giai đoạn học để tạo ra mô hình, mà nó chỉ đơn thuần là sử dụng tập dữ liệu huấn luyện phục vụ cho giai đoạn dự đoán nhãn của dữ liệu sau này. Những thuật toán này được liệt kê vào lớp thuật toán lười học (lazy learner). Đặc điểm của lớp thuật toán này là nó không tốn thời gian để học, tuy nhiên giai đoạn phân lớp của nó lại bị “trả giá”. Thông thường các thuật toán lười học sẽ cần phải tính toán nhiều trong quá trình phân lớp. Có thể đây là nhược điểm lớn nhất của lớp thuật toán lười học, vì khi tập dữ liệu huấn luyện là rất lớn thì chi phí khi phân lớp sẽ càng cao. Hình 7: Các bước trong mô hình học máy có giám sát Tuy nhiên một trong những ưu điểm của việc “lười học” là nó buộc phải xử lý thêm một số bước nhỏ với dữ liệu. Cụ thể là với các thuật toán cần phải huấn luyện thì khi dữ liệu huấn luyện thay đổi, thì ta phải huấn luyện lại thuật toán để tạo ra mô hình mới tương ứng với dữ liệu mới. Tuy nhiên với thuật toán lười học thì cho dù dữ liệu huấn luyện có thay đổi thì cũng không phải mất công huấn luyện. Một trong những thuật toán thuộc lớp thuật toán lười học là thuật toán k người láng giềng gần nhất (k nearest neighbors) viết tắt là kNN và thuật toán case-based reasoning. Trong luận văn này tôi sẽ trình bày chi tiết thuật toán kNN. 16 Khi đưa một phần tử dữ liệu mới, thuật toán sẽ tìm k phần tử dữ liệu láng giềng gần nó nhất (k nearest neighbors), sau đó dựa trên nhãn (lớp) của các láng giềng này mà nó sẽ quyết định nhãn (lớp) của phần tử dữ liệu mới là thuộc lớp nào. Trường hợp đơn giản nhất là ta chỉ tìm một phần tử gần phần tử mới nhất, nhãn của phần tử mới sẽ được gán là nhãn của phần tử tìm được. Đề tìm các phần tử láng giềng gần nhất ta cần định nghĩa độ đo nào đó, một trong các độ đo điển hình là độ đo khoảng cách Euclide. Giả sử có 2 phần tử dữ liệu X1=(x11, x12, …, x1n) và X2=(x21, x22, …, x2n), độ đo khoảng cách Euclide được tính bằng công thức: dist  X 1 , X 2   n  x i 1 1i  x 2i  2 (1.14) Từ công thức (1.14), ta nhận thấy nếu các thuộc tính khác nhau có miền giá trị khác nhau thì có thể độ chính xác của độ đo sẽ không chính xác. Ví dụ thuộc tính thu nhập có miền giá trị lớn hơn nhiều so với thuộc tính tuổi, hay thuộc tính số lượng con. Khi đó chỉ cần một độ chênh lệch nhỏ của thuộc tính thu nhập cũng làm thay đổi giả trị của độ đo khoảng cách. Để làm cho các thuộc tính có “ảnh hưởng” ngang nhau đến độ đo khoảng cách, ta có thể chuẩn hóa dữ liệu các thuộc tính sử dụng công thức sau để chuyển giá trị v của một thuộc tính A sang giá trị v’ có miền giá trị nằm trong khoảng [0, 1]: v'  v  min A max A  min A (1.15) trong đó minA và maxA là giá trị nhỏ nhất và lớn nhất của thuộc tính A. Trường hợp thuộc tính biểu diễn dữ liệu không phải là dữ liệu liên tục mà là dữ liệu rời rạc (chẳng hạn thuộc tính màu nó có miền giá trị là một danh sách các loại màu). Khi đó ta có thể giải quyết như sau: giả sử x1i và x2i là giá trị rời rạc (biểu diễn thuộc tính A) của 2 phần tử dữ liệu X1 và X2, thì: 0 khi x1i  x2i x1i  x2i   1 khi x1i  x2i (1.16) Rõ ràng với công thức này thì ta có thể áp dụng công thức (1.14) với dữ liệu rời rạc. Trong nhiều trường hợp ta cũng có thể sử dụng độ đo tương tự (thay vì độ đo khoảng cách) để tìm ra các phần tử láng giềng gần nhất. 17 Bây giờ ta sẽ nghiên cứu là xác định giá trị k như thế nào để ta có thể thu được kết quả phân lớp tốt nhất. Với trường hợp đơn giản nhất thì k=1 (khi đó thuật toán kNN sẽ được ký hiệu là 1-NN). Khi xác định được phần tử dữ liệu gần phần tử dữ liệu cần phần lớp nhất thì bài toán xác định nhãn lại rất đơn giản vì nó chính là nhãn của phần tử gần nhất vừa tìm được. Tuy nhiên có một vấn đề khi ta chỉ dựa vào 1 phần tử láng giềng đề quyết định nhãn của phần tử dữ liệu cần phân lớp: đó là trường hợp phần tử láng giềng gần nó nhất lại là phần tử nhiễu (noise), khi đó nhãn thu được sẽ không chính xác. Đề giải quyết vấn đề này thì ta có thể dùng các phương pháp để lọc các dữ liệu nhiễu, thậm chí là các thuộc tính nhiễu đi. Trên thực tế thuật toán mở rộng của thuật toán 1-NN được sử dụng rộng hơn, đó là tăng giá trị của k lên để tạo khả năng ra quyết định dựa trên nhiều phần tử dữ liệu. Thông thường các giá trị của k được chọn sẽ là các giá trị lẻ (để tránh trường hợp các láng giềng của phần tử dữ liệu cần phân lớp lại thuộc 2 lớp khác nhau, và số lượng các láng giềng trong mỗi lớp lại bằng nhau). Với k=3 và có 3 phần tử dữ liệu láng giềng gần nhất có nhãn là {A, B, A}, khi đó ta có thể kết luận là phần tử dữ liệu cần phần lớp là thuộc lớp A. Với k=5, các phần tử láng giềng có nhãn là {A, B, A, B, B}, thì ta có thể kết luận là phần tử dữ liệu mới thuộc lớp B. Tuy nhiên việc phân lớp dựa vào việc đếm số nhãn như thế này sẽ có vấn đề. Cụ thể với trường hợp k=5, và giả sử độ tương tự tương ứng của 5 láng giềng này là {0.98, 0.67, 0.56, 0.34, 0.23}. Ta có thể nhận thấy các phần tử láng giềng 4 và 5 có độ tương tự rất thấp, do đó nếu ta dựa vào các phần tử dữ liệu này để kết luận nhãn của phần tử dữ liệu mới thuộc lớp A sẽ không tin cậy. Do đó người ta đề xuất là sử dụng trọng số cho nhãn của các phần tử láng giềng, chúng ta có thuật toán mới có tên là: k người láng giềng gần nhất có đánh trọng số khoảng cách (distance-weighted kNN). Cụ thể nhãn của k láng giềng sẽ được gán trọng số, lớp có tổng trọng số lớn nhất sẽ được dùng để gán cho phần tử cần phân lớp. Trọng số đơn giản chính là độ tương tự giữa phần từ dữ liệu cần phân lớp X với phần tử láng giềng Xi là sim(X, Xi). Với ví dụ k=5 ở trên thì tổng trọng số của các láng giềng thuộc lớp A là 0.98+0.56=1.54, và tổng trọng số các nhãn thuộc lớp B là 0.67 + 0.34 + 0.23 = 1.24, kết quả này cho ta quyết định là phần tử cần phân lớp thuộc lớp A. Một số công thức tính trọng số khác là: 1/(1sim(X, Xi)) hay 1/(1-sim(X, Xi))2. Các công thức này đều có đặc điểm chung là giá trị của chúng sẽ tăng lên khi độ tương tự giữa chúng tăng lên. Tuy có rất 18 nhiều đề xuất cải tiến so với thuật toán 1-NN tuy nhiên trong nhiều trường hợp thì 1-NN vẫn tỏ ra là có chất lượng tốt hơn cả. Một nhược điểm của thuật toán kNN là rất chậm khi kích thước của tập dữ liệu huấn luyện D tăng lên. Ta phải sử dụng |D| phép so sánh để tìm ra các láng giềng gần nhất, hay độ phức tạp của nó là O(n). Có rất nhiều đề xuất để làm giảm độ phức tạp của thuật toán, một số phương pháp được liệt kê ở dưới: • Sắp xếp tập dữ liệu D đầu vào và tổ chức nó dưới dạng 1 cây tìm kiếm, khi đó độ phức tạp của nó giảm xuống còn O(log(n)). • Sử dụng các phương pháp song song hóa. • Lấy mẫu tập dữ liệu D để tạo một tập dữ liệu D có kích thước nhỏ hơn. • Sử dụng 1 phần độ đo khoảng cách (partial distance), việc tính toán khoảng cách chỉ dựa trên một tập con các thuộc tính, nếu giá trị thu được lớn hơn 1 ngưỡng nào đó thì ta sẽ không tính toán tiếp phần tử dữ liệu hiện tại nữa (vì nó có khoảng cách quá xa), và phần tử dữ liệu tiếp theo sẽ được xử lý. • Phương pháp hiệu chỉnh (editing): chúng ta loại bỏ các phần tử dữ liệu (đã được chứng minh) là vô nghĩa trong quá trình phân lớp. Phương pháp này còn có các tên khác là tỉa (pruning) hay cô đọng hóa (condensing) vì chúng làm giảm số lượng phần tử dữ liệu trong tập huấn luyện. 1.3. So sánh SVM với kNN Trong ngành nghiên cứu máy học thì SVM và kNN là hai thuật toán rất phổ biến và có được sự quan tâm nhiều nhất trong quá trình phát triển ngành. Tuy nhiên câu hỏi đặt ra là hai thuật toán này có đặc điểm gì giống và khác nhau? Ưu điểm từng phương pháp là gì và có thể áp dụng trong những bài toán cụ thể như thế nào. Trong luận văn này, tôi sẽ kết hợp những phân tích trong bài viết [9] từ đó so sánh chi tiết hai thuật toán SVM và kNN: Sự giống nhau: Hai thuật toán phân lớp trên đều có điểm chung là yêu cầu dữ liệu phân lớp phải được biểu diễn dưới dạng vector đặc trưng.
- Xem thêm -

Tài liệu liên quan