SVM – giới thiệu tổng quan và ví dụ

Overview – Tổng quan

Máy học khá phức tạp với nhiều bài viết về chúng, nhưng hầu hết là khó hiểu. Tôi muốn viết cho dễ hiểu và minh hoạ cách dùng LibSVM và ứng dụng của nó.

Nó là thư viện miễn phí. Về căn bản, nó cho phép bạn lấy vài mẫu dữ liệu đã có, huấn luyện để tạo 1 mô hình nhận dạng, và rồi sử dụng mô hình này để dự đoán.

The Data – Dữ liệu

Trong bài này, tôi sẽ thực hiện việc phát hiện SPAM. Nếu chúng ta có thể dựa vào những email được đánh dấu là SPAM/Not SPAM, chúng ta có thể dự đoán chính xác 1 email nào đó là SPAM hay ko? Dữ liệu ví dụ được tạo ra để minh hoạ cho thuật toán.

Đây là những email mẫu dùng để huấn luyện. Những email đầu tiên là SPAM, còn lại là không phải SPAM

SPAM

“Buy Viagra cheap”

“Cheap drugs, with no prescriptions”

“Buy drugs by mail”

“Viagra, Cialis, ED, others”

“Buy prescriptions drugs like viagra, cialis, and others.”

Not SPAM

“Hi James you are great”

“James, here is a picture of my dog”

“Adding James to the email list”

“Send me a picture of your dog”

“James we are going to give you a raise”

Dữ liệu có 10 emails. Tiếp theo là tiền xử lý để dữ liệu có định dạng mà LibSVM hiểu được, từ đó để huấn luyện mô hình.

Để định dạng dữ liệu, chúng ta cần biết libSVM học thế nào. Trong máy học nó thường được gọi là feature (bộ đặc tính). Trong trường hợp phân lớp tài liệu (phát hiện spam email) chúng ta xem mỗi từ như một đặc tính. Chắc chắn từ “Viagra” có trong hầu hết email spam, nhưng không tìm thấy trong email thường, nên thuật toán sẽ học từ những đặc điểm này để phân tích 1 email có phải spam không.

Mỗi đặc tính (từ vựng) mà SVM học phải có 1 giá trị. Trong trường hợp này chỉ là phân lớp nhị phân. Nếu từ vựng có trong email thì nó là true (1) và nếu không có thì nó là false (0)

Để đại diện cho mỗi email, chúng tôi tạo ra 1 vectơ giá trị true/false cho mỗi từ (lấy trong 10 email). Đầu tiên, chúng tôi lấy toàn bộ các từ

buy, viagra, cheap, drugs, with, no, prescription, by, mail, cialis, ed, others, like, and, hi, james, you, are, great, here, is, a, picture, of, my, dog, adding, to, the, email, list, send, me, your, we, going, give, you, raise

Bước tiếp theo là tạo vectơ cho mỗi email, hiển thị từ có trong email. Lấy email đầu tiên:

“Buy Viagra cheap”

Và định dạng của nó như thế này:

buy=1, viagra=1, cheap=1, drugs=0, with=0, no=0, prescription=0, by=0, mail=0, cialis=0, ed=0, others=0, like=0, and=0, hi=0, james=0, you=0, are=0, great=0, here=0, is=0, a=0, picture=0, of=0, my=0, dog=0, adding=0, to=0, the=0, email=0, list=0, send=0, me=0, your=0, we=0, going=0, give=0, you=0, raise=0

Bây giờ bạn thấy có quá nhiều số 0 và chúng ta chỉ cần quan tâm những từ có mặt:

buy=1, viagra=1, cheap=1

Bước tiếp theo là đơn giản hoá dữ liệu là đánh chỉ số cho mỗi từ, thay vì phải ghi ra. Để làm điều đó chúng tôi đánh số nguyên theo thứ tự mỗi từ:

1 = buy
2 = viagra
3 = cheap
4 = drugs
5 = with
6 = no
7 = prescription
8 = by
9 = mail
10 = cialis
11 = ed
12 = others
13 = like
14 = and
15 = hi
16 = james
17 = you
18 = are
19 = great
20 = here
21 = is
22 = a
23 = picture
24 = of
25 = my
26 = dog
27 = adding
28 = to
29 = the
30 = email
31 = list
32 = send
33 = me
34 = your
35 = we
36 = going
37 = give
38 = you
39 = raise

Nên email đó sẽ trở thành

1=1 2=1 3=1

Huấn luyện để tạo mô hình

Để huấn luyện, chúng ta cần cho thuật toán biết lớp của email đó. Trong trường hợp này có 2 lớp là SPAM NOTSPAM. Vì thuật toán chỉ chấp nhận 1 từ nên chúng tôi sửa “Not Spam” thành “NSpam”. Cuối cùng là thay dấu bằng bằng dấu hai chấm.

spam 1:1 2:1 3:1

Và để tạo toàn bộ tập huấn luyện đúng định dạng, chúng tôi cho mỗi email là 1 dòng trong file input. Ví dụ email thứ 2 là:

“Cheap drugs, with no prescriptions”

Nó sẽ trở thành:

spam 3:1 4:1 5:1 6:1 7:1

Chúng tôi tập hợp vào một file mà mỗi dòng là một email:

spam 1:1 2:1 3:1
spam 3:1 4:1 5:1 6:1 7:1
spam 1:1 4:1 8:1 9:1
spam 1:1 10:1 11:1 12:1
spam 1:1 7:1 4:1 13:1 2:1 10:1 14:1 12:1
NSpam 15:1 16:1 17:1 18:1 19:1
NSpam 16:1 20:1 21:1 22:1 23:1 24:1 25:1 26:1
NSpam 27:1 16:1 28:1 29:1 30:1 31:1
NSpam 32:1 33:1 22:1 23:1 24:1 34:1 26:1
NSpam 16:1 35:1 18:1 36:1 28:1 37:1 38:1 22:1 39:1

Chúng ta cần thay thế tên mỗi lớp bằng số (1 = SPAM và 0 = NSpam) và chúng ta phải đảm bảo dữ liệu sắp xếp theo thứ tự giảm dần. Nên dữ liệu input cuối cùng sẽ giống thế này:

1 1:1 2:1 3:1
1 3:1 4:1 5:1 6:1 7:1
1 1:1 4:1 8:1 9:1
1 1:1 10:1 11:1 12:1
1 1:1 2:1 4:1 7:1 10:1 12:1 13:1 14:1
0 15:1 16:1 17:1 18:1 19:1
0 16:1 20:1 21:1 22:1 23:1 24:1 25:1 26:1
0 16:1 27:1 28:1 29:1 30:1 31:1
0 22:1 23:1 24:1 26:1 32:1 33:1 34:1
0 16:1 18:1 22:1 28:1 35:1 36:1 37:1 38:1 39:1

Bây giờ chúng ta đã có file input, save lại và đặt tên là “Spam.train”. Để tạo mô hình dự đoán dùng lênh sau ở command line (trên Windows)

C:\Program Files\LibSVM\windows>svm-train.exe spam.train

Output khi train:

*
optimization finished, #iter = 5
nu = 1.000000
obj = -7.583904, rho = 0.229345
nSV = 10, nBSV = 10
Total nSV = 10

Sau khi chạy xong, sẽ có file “Spam.train.model” để phân lớp email.

Test kết quả

Để test, chúng ta dùng email này:

James, can you pick up the dog?

Để chuyển về đúng định dạng chúng ta một lần nữa phải chuyển mỗi từ sang dạng vectơ:

james=16
can=???
you=17
pick=???
up=???
the=29
dog=26

Những từ có dấu ??? nghĩa là không có từ đó, nên chúng ta bỏ qua. Định dạng mới của email là:

0 16:1 17:1 26:1 29:1

Do chúng ta biết email này không phải Spam nên chúng ta bắt đầu bằng 0, rồi save lại với tên “sample.1.txt” và dùng lệnh sau để test:

c:\Program Files\LibSVM\windows>svm-predict.exe sample.1.txt spam.train.model sample.1.predicted.txt

Accuracy = 100% (1/1) (classification)

Kết quả xuất ra cho chúng ta biết thuật toán này dự báo không phải SPAM, độ chính xác là 100%. Tương tự, bạn mở file “sample.1.predicted.txt” bạn sẽ thấy số 0 chỉ ra rằng nó dự báo dòng đầu tiên trong file input thuộc lớp 0 hay là Nspam.

Bây giờ chúng ta tạo vài email để test

Cheap viagra by mail!
James, you need viagra.

Email đầu tiên là SPAM, nhưng cái thứ 2 có 1 chút thú vị. Nếu đó là từ người lạ thì đó là SPAM, tuy nhiên nếu nó từ vợ bạn thì có thể là không 🙂

Chúng ta thêm vào file input đã có sẵn thì file input trở thành

0 16:1 17:1 26:1 29:1
1 2:1 3:1 8:1 9:1
0 2:1 16:1 17:1

Sau đó gõ lệnh:

c:\Program Files\LibSVM\windows>svm-predict.exe sample.1.txt spam.train.model sample.1.predicted.txt
Accuracy = 100% (3/3) (classification)

Như bạn thấy, thuật toán làm rất tốt. Nó nghĩ rằng email đầu tiên là NSPAM, thứ 2 là SPAM và thứ 3 là NSPAM. File output: 0, 1, 0

Đây chỉ là ví dụ, tôi mong bản hiểu cách dùng LIBSVM để phân lớp dữ liệu. Bằng cách tạo tập huấn luyện rồi tạo mô hình phân lớp, và test lại thì chúng tôi thấy rằng Support Vector Machines mạnh mẽ và dễ dùng trong Machine Learning.

Trang chủ LIBSVM: http://www.csie.ntu.edu.tw/~cjlin/libsvm/
Download LIBSVM

Nguồn: http://jamescpoole.com/2012/10/30/libsvm-tutorial-part-1-overview/

Các bạn có thể tham khảo thêm bài viết này
https://ongxuanhong.wordpress.com/2015/09/19/support-vector-machine-svm-hoi-gi-dap-nay/

9 thoughts on “SVM – giới thiệu tổng quan và ví dụ

  1. Chào Anh!
    Anh có thể cho em hỏi là vì sao khi tạo file test trong svm, nó hiểu được là văn bản đó thuộc class nào vậy anh?
    Cơ chế để test là như thế nào ạ.
    Cảm ơn anh nhiều.

    1. Cái này thì bạn phải đọc chuyên sâu hơn về giải thuật của svm rồi. Bạn có thể tìm đọc trên mạng, mình chỉ đăng những bài nói về ứng dụng của nó thôi

  2. Bạn ơi, mình muốn hỏi 1 chút
    Ở bước : “Bước tiếp theo là đơn giản hoá dữ liệu là đánh chỉ số cho mỗi từ, thay vì phải ghi ra. Để làm điều đó chúng tôi đánh số nguyên theo thứ tự mỗi từ” . Nếu ở bước này dữ liệu rất lớn bạn cũng vẫn đánh chỉ số à? có công cụ nào hỗ trợ chuyển từ file sang dạng vector không bạn?

    1. @hippo

      Nếu dữ liệu lớn thì mình cần phải viết tool để thực hiện, nếu dữ liệu có độ phức tạp không lớn thì có thể dùng notepad++ để làm cũng được. Notepad++ có chức năng replace từ khóa theo pattern

  3. Mình thắc mắc ở chỗ Ví dụ có 1 email cần kiểm tra có phải spam hay nospam, email đó khoảng 10 từ trong đó 9 từ không thuộc vào tập train chỉ có 1 từ thuộc vào tập spam >> email đó là spam, kết luận này có chính xác ko bác, hoặc có cách nào xử lý trong trường hợp này.

    1. Theo kết quả test thì chính xác, tuy nhiên cũng có sai số nhất định. Còn machine learning là dự đoán những gì chưa biết dựa vào những cái đã biết, cho nên email có những từ chưa từng xuất hiện vẫn phân loại được.

Leave a Reply