Phân lớp bán giám sát và ứng dụng thuật toán SVM vào phân lớp trang web

MỤC LỤC

MỞ ĐẦU 9

Chương 1 TỔNG QUAN VỀ PHÂN LỚP BÁN GIÁM SÁT 11

1.1. Phân lớp dữ liệu 11

1.1.1. Bài toán phân lớp dữ liệu 11

1.1.2. Quá trình phân lớp dữ liệu 12

1.2. Phân lớp văn bản 13

1.2.1. Đặt vấn đề 13

1.2.2. Mô hình vector biểu diễn văn bản 14

1.2.3. Phương pháp phân lớp văn bản 19

1.2.4. Ứng dụng của phân lớp văn bản 19

1.2.5. Các bước trong quá trình phân lớp văn bản 20

1.2.6. Đánh giá mô hình phân lớp 22

1.2.7. Các yếu tố quan trọng tác động đến phân lớp văn bản 23

1.3. Một số thuật toán học máy phân lớp 23

1.3.1. Học có giám sát 23

1.3.1.1. Bài toán học có giám sát 23

1.3.1.2. Giới thiệu học có giám sát 24

1.3.1.3. Thuật toán học có giám sát k-nearest neighbor (kNN) 25

1.3.1.4. Thuật toán học có giám sát Support vector machine (SVM) 26

1.3.2. Thuật toán phân lớp sử dụng quá trình học bán giám sát 27

1.3.2.1. Khái niệm 27

1.3.2.2. Lịch sử phát triển sơ lược của học bán giám sát 28


1.3.2.3. Một số phương pháp học bán giám sát điển hình 29

Chương 2 SỬ DỤNG SVM VÀ BÁN GIÁM SÁT SVM
VÀO BÀI TOÁN PHÂN LỚP 32

2.1. SVM – Support Vector Machine 32

2.1.1. Thuật toán SVM 33

2.1.2. Huấn luyện SVM 35

2.1.3. Các ưu thế của SVM trong phân lớp văn bản 35

2.2. Bán giám sát SVM và phân lớp trang Web 37

2.2.1. Giới thiệu về bán giám sát SVM 37

2.2.2. Phân lớp trang Web sử dụng bán giám sát SVM 38

2.2.2.1. Giới thiệu bài toán phân lớp trang Web (Web Classification) 38

2.2.2.3. Áp dụng S3VM vào phân lớp trang Web 39

Chương 3 THỬ NGHIỆM HỌC BÁN GIÁM SÁT PHÂN LỚP TRANG
WEB 41

3.1. Giới thiệu phần mềm SVMlin 41

3.2. Download SVMlin 42

3.3. Cài đặt 42

3.4. Cách sử dụng phần mềm 42

KẾT LUẬN 45

Những công việc đã làm được của khoá luận 45

Hướng nghiên cứu trong thời gian tới 45

TÀI LIỆU THAM KHẢO 46

I. Tiếng Việt 46

II. Tiếng Anh 46



DANH SÁCH BẢNG VÀ TỪ VIẾT TẮT
Ký hiệu viết tắt Cụm từ
kNN k Nearest Neighbor
SVM Support Vector Machine
S3VM Semi Supervised Support Vector Machine











































DANH MỤC HÌNH ẢNH

Hình 1. Bài toán phân lớp.
Hình 2. Văn bản được biểu diễn là vector đặc trưng.
Hình 3. Sơ đồ khung quá trình phân lớp văn bản.
Hình 4. Siêu phẳng h phân chia dữ liệu huấn luyện thành 2 lớp + và - với khoảng
cách biên lớn nhất. Các điểm gần h nhất là các vector hỗ trợ (Support
Vector - được khoanh tròn).
Hình 5. Phương pháp học bán giám sát Self-training.
Hình 6. Phương pháp học bán giám sát Co-training.






























MỞ ĐẦU
Trong những năm gần đây, sự phát triển vượt bậc của công nghệ thông tin đã làm
tăng số lượng giao dịch thông tin trên mạng Internet một cách đáng kể đặc biệt là thư
viện điện tử, tin tức điện tử… Do đó mà số lượng văn bản xuất hiện trên mạng Internet
cũng tăng với một tốc độ chóng mặt, và tốc độ thay đổi thông tin là cự
c kỳ nhanh chóng.
Với số lượng thông tin đồ sộ như vậy, một yêu cầu lớn đặt ra là làm sao tổ chức và tìm
kiếm thông tin, dữ liệu có hiệu quả nhất. Bài toán phân lớp là một trong những giải pháp
hợp lý cho yêu cầu trên. Nhưng một thực tế là khối lượng thông tin quá lớn, việc phân
lớp dữ liệu thủ công là điều không thể. Hướng giải quyết là một chương trình máy tính tự
động phân l
ớp các thông tin dữ liệu trên.
Tuy nhiên, khi xử lý các bài toán phân lớp tự động thì gặp phải một số khó khăn là
để xây dựng được bộ phân lớp có độ tin cậy cao đòi hỏi phải có một lượng lớn các mẫu
dữ liệu huấn luyện tức là các văn bản đã được gán nhãn lớp tương ứng. Các dữ liệu huấn
luyện này thường rất hiếm và đắt vì đòi hỏi thời gian và công s
ức của con người. Do vậy
cần phải có một phương pháp học không cần nhiều dữ liệu gán nhãn và có khả năng tận
dụng được các nguồn dữ liệu chưa gán nhãn rất phong phú như hiện nay, phương pháp
học đó là học bán giám sát. Học bán giám sát chính là cách học sử dụng thông tin chứa
trong cả dữ liệu chưa gán nhãn và tập huấn luyện, phương pháp học này được sử dụng rất
phổ bi
ến vì tính tiện lợi của nó.
Vì vậy, khoá luận tập trung vào nghiên cứu bài toán phân lớp sử dụng quá trình học
bán giám sát, và việc áp dụng thuật toán bán giám sát máy hỗ trợ vector (Support Vector
Machine – SVM) vào phân lớp trang Web.
Nội dung của khoá luận được trình bày bao gồm 3 chương. Tổ chức cấu trúc như
sau:






• Chương 1 Tổng quan về phân lớp bán giám sát. Phần đầu trình bày khái
quát về bài toán phân lớp dữ liệu, phân lớp văn bản, một số nét sơ bộ về học có giám sát.
Phần cuối của chương giới thiệu các nội dung cơ bản về phương pháp học bán giám sát,
trong đó đã giới thiệu một số thuật toán học bán giám sát điển hình.
• Chương 2 Sử dụng SVM và bán giám sát SVM vào bài toán phân l
ớp.
Khóa luận trình bày những bước hoạt động cơ bản nhất của thuật toán SVM, sau đó
nghiên cứu thuật toán học bán giám sát SVM, một cải tiến của SVM được trình bày trong
[11]. Khoá luận trình bày một số áp dụng học bán giám sát vào bài toán phân lớp trang
Web trong phần cuối cùng của chương.
• Chương 3 Hệ thống thử nghiệm phân loại trang Web và đánh giá.
Trình bày kết quả nghiên cứu của V. Sindhwani về phần mềm nguồn mở SVMlin [14, 15,
18] mà do chính tác giả đề xuất và công bố. Các nghiên cứu này cho thấy phần mềm
SVMlin phân lớp bán giám sát văn bản cho độ chính xác cao.




























Chương 1 TỔNG QUAN VỀ PHÂN LỚP
BÁN GIÁM SÁT
1.1. Phân lớp dữ liệu
1.1.1. Bài toán phân lớp dữ liệu
Là quá trình phân lớp một đối tượng dữ liệu vào một hay nhiều lớp cho trước nhờ
một mô hình phân lớp mà mô hình này được xây dựng dựa trên một tập hợp các đối
tượng dữ liệu đã được gán nhãn từ trước gọi là tập dữ liệu học (tập huấn luyện) [1-3].
Quá trình phân lớp còn được gọi là quá trình gán nhãn cho các đối tượng dữ liệu.
Như vậy, nhiệm vụ của bài toán phân lớp d
ữ liệu là cần xây dựng mô hình (bộ)
phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc
lớp nào.
Có nhiều bài toán phân lớp dữ liệu, như phân lớp nhị phân, phân lớp đa lớp, phân
lớp đa trị,….
Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vào một trong hai
lớp khác nhau dựa vào việc dữ liệu đó có hay không mộ
t số đặc tính theo quy định của bộ
phân lớp.
Phân lớp đa lớp là quá trình phân lớp với số lượng lớp lớn hơn hai. Như vậy, tập
hợp dữ liệu trong miền xem xét được phân chia thành nhiều lớp chứ không đơn thuần chỉ
là hai lớp như trong bài toán phân lớp nhị phân. Về bản chất, bài toán phân lớp nhị phân
là trường hợp riêng của bài toán phân lớp đa lớp.
Trong phân lớp đa tr
ị, mỗi đối tượng dữ liệu trong tập huấn luyện cũng như các
đối tượng mới sau khi được phân lớp có thể thuộc vào từ hai lớp trở lên. Ví dụ như trang
web về việc bùng phát bệnh cúm gia cầm, thủy cầm tại một số tính phía Bắc vừa thuộc về
lĩnh vực y tế liên quan đến lây bệnh sang người nhưng cũng thuộc về lĩnh vực kinh tế liên
quan
đến ngành chăn nuôi… Trong những trường hợp như vậy, việc sắp xếp một tài liệu
vào nhiều hơn một lớp là phù hợp với yêu cầu thực tế.
Sau đây chúng ta sẽ tìm hiểu khái quát về quá trình phân lớp dữ liệu và sơ bộ về
phương pháp phân lớp dữ liệu.

1.1.2. Quá trình phân lớp dữ liệu





Quá trình phân lớp dữ liệu thường gồm hai bước: xây dựng mô hình (tạo bộ phân
lớp) và sử dụng mô hình đó để phân lớp dữ liệu.
• Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các đối tượng dữ
liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này còn được gọi là tập dữ liệu
huấn luyện (
training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định
bởi con người trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học
có giám sát (supervised learning). Trong bước này, chúng ta còn phải tính độ chính xác
của mô hình, mà cần phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính
xác là chấp nhận được (tức là cao), mô hình sẽ được sử dụng để xác định nhãn lớp cho
các d
ữ liệu khác mới trong tương lai. Trong việc test mô hình, sử dụng các độ đo để đánh
Hình 1. Bài toán phân lớp

giá chất lượng của tập phân lớp, đó là độ hồi tưởng, độ chính xác, độ đo F
1
Nội dung
chi tiết về các độ đo này được trình bày trong mục (1.2.6).
Tồn tại nhiều phương pháp phân lớp dữ liệu để giải quyết bài toán phân lớp tùy
thuộc vào cách thức xây dựng mô hình phân lớp như phương pháp Bayes, phương pháp
cây quyết định, phương pháp k-người láng giềng gần nhất, phương pháp máy hỗ trợ
vector Các phương pháp phân lớp khác nhau chủ yếu về mô hình phân lớp. Mô hình
phân lớp còn được gọi là thuật toán phân lớp.
•
Bước 2: sử dụng mô hình đã được xây dựng ở bước 1 để phân lớp dữ liệu mới.
Như vậy, thuật toán phân lớp là một ánh xạ từ miền dữ liệu đã có sang một miền
giá trị cụ thể của thuộc tính lớp, dựa vào giá trị các thuộc tính của dữ liệu.
1.2. Phân lớp văn bản
1.2.1. Đặt vấn đề
Ngày nay phương thức sử dụng giấy tờ trong giao dịch đã dần được số hoá chuyển
sang các dạng văn bản lưu trữ trên máy tính hoặc truyền tải trên mạng. Bởi nhiều tính
năng ưu việt của tài liệu số như cách lưu trữ gọn nhẹ, thời gian lưu trữ lâu dài, tiện dụng
trong trao đổi đặc biệt là qua Internet, dễ dàng sửa đổi… nên càng ngày, số lượng văn
b
ản số tăng lên một cách nhanh chóng đặc biệt là trên World Wide Web. Cùng với sự gia
tăng về số lượng văn bản, nhu cầu tìm kiếm văn bản cũng tăng theo. Trong đời thường,
phân lớp các văn bản được tiến hành một cách thủ công, nghĩa là chúng ta thực hiện công
việc đọc từng văn bản một, xem xét và sau đó là gán nó vào một lớp cụ thể nào đó. Cách
này sẽ tốn rất nhiều th
ời gian và công sức của con người vì các văn bản là vô vàn, để gán
mỗi văn bản vào một lớp đã cho là một vấn đề không thể và do đó không khả thi. Với số
lượng văn bản đồ sộ thì việc phân lớp văn bản tự động là một nhu cầu bức thiết.
Vậy phân lớp văn bản là gì? Phân lớp văn bản (Text Categorization) là việc phân
lớp áp dụng đố
i với dữ liệu văn bản, tức là phân lớp một văn bản vào một hay nhiều lớp
văn bản nhờ một mô hình phân lớp; mô hình này được xây dựng dựa trên một tập hợp các
văn bản đã được gán nhãn từ trước.
Phân lớp văn bản là một lĩnh vực được chú ý nhất và đã được nghiên cứu trong
những năm gần đây.

1.2.2. Mô hình vector biểu diễn văn bản
Như đã trình bày ở phần trên, bước đầu tiên trong qui trình phân lớp văn bản là
thao tác chuyển văn bản đang được mô tả dưới dạng chuỗi các từ thành một mô hình
khác, sao cho phù hợp với các thuật toán phân lớp.
Thông thường nguời ta thường biểu diễn văn bản bằng mô hình vector, mỗi văn
bản được biểu diễn bằng một vector trọng số. Ý tưởng của mô hình này là xem mỗi một
văn bả
n D
i
được biểu diễn theo dạng
(
)
i,
d
D
i
i
=
, trong đó i là chỉ số dùng để nhận
diện văn bản này và
d
i
là vector đặc trưng của văn bản D
i
này, trong đó :
), ,,(
www
d
in2i1i
i
=
, và n là số luợng đặc trưng của vector văn bản,
w
ij
là trọng số
của đặc trưng thứ j ,
{}
n1,2, ,j∈
.
Trong quá trình chuyển thể văn bản sang thành dạng vector, vấn đề mà chúng ta
cần quan tâm là việc lựa chọn đặc trưng và số chiều cho không gian vector, chọn bao
nhiêu từ, là các từ nào, phương pháp chọn ra sao?
Việc lựa chọn phương pháp biểu diễn văn bản để áp dụng vào bài toán phân lớp
tuỳ thuộc vào độ thích hợp, phù hợp, độ đo đánh giá mô hình phân lớp của phương pháp
đó sử dụng so với bài toán mà chúng ta đang xem xét giả
i quyết. Ví dụ nếu văn bản là
một trang Web thì sẽ có phương pháp để lựa chọn đặc trưng khác so với các loại văn bản
khác.

Các đặc trưng của văn bản khi biểu diễn dưới dạng vector

- Số nhiều không gian đặc trưng thường lớn. Các văn bản càng dài, lượng thông tin
trong nó đề cập đến nhiều vấn đề thì không gian đặc trưng càng lớn.
- Các đặc trưng độc lập nhau, sự kết hợp các đặc trưng này thường không có ý nghĩa
trong phân lớp.
- Các đặc trưng rời rạc: vector đặc trưng d
i
có thể có nhiều thành phần mang giá trị
0 do có nhiều đặc trưng không xuất hiện trong văn bản d
i
(nếu chúng ta tiếp cận
theo cách sử dụng giá trị nhị phân 1, 0 để biểu diễn cho việc có xuất hiện hay
không một đặc trưng nào đó trong văn bản đang được biểu diễn thành vector), tuy
nhiên nếu đơn thuần cách tiếp cận sử dụng giá trị nhị phân 0, 1 này thì kết quả

Xem chi tiết: Phân lớp bán giám sát và ứng dụng thuật toán SVM vào phân lớp trang web