TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM
KHOA CÔNG NGHỆ THÔNG TIN
THUYẾT MINH ĐỀ TÀI NCKH CẤP TRƯỜNG ĐỀ TÀI
NGHIÊN CỨU VỀ THUẬT TOÁN PHÂN LỚP SỬ DỤNG QUÁ TRÌNH HỌC MÁY BÁN GIÁM SÁT, ỨNG DỤNG TRONG VIỆC PHÂN LỚP TRANG WEB
Chủ nhiệm đề tài: ThS. Lê Hoàng Dương
Thành viên tham gia: ThS. Ngô Quốc Vinh
Hải Phòng, tháng 4/2016
MỤC LỤC
MỞ ĐẦU ............................................................................................................... 1
1. Tính cấp thiết của vấn đề nghiên cứu ............................................................ 1
2. Tổng quan về tình hình nghiên cứu thuộc lĩnh vực đề tài ............................. 1
3. Mục tiêu, đối tượng, phạm vi nghiên cứu ...................................................... 2
4. Phương pháp nghiên cứu, kết cấu của công trình nghiên cứu ....................... 3
5. Kết quả đạt được của đề tài ............................................................................ 3
CHƯƠNG 1 TỔNG QUAN VỀ VIỆC PHÂN LỚP SỬ DỤNG PHƯƠNG
PHÁP HỌC BÁN GIÁM SÁT ............................................................................. 4
1.1. Tổng quan về phân lớp dữ liệu. .................................................................. 4
1.1.1. Tổng quan về bài toán phân lớp dữ liệu ............................................... 4
1.1.2. Tổng quan về quá trình phân lớp dữ liệu .............................................. 5
1.2. Tổng quan về phân lớp dữ liệu văn bản ...................................................... 6
1.2.1. Thực trạng của vấn đề. .......................................................................... 6
1.2.2. Sử dụng mô hình vector biểu diễn văn bản .......................................... 7
1.2.3. Tổng quan về phương pháp phân lớp văn bản .................................... 11
1.2.4. Ứng dụng của việc phân lớp dữ liệu văn bản ..................................... 12
1.2.5. Quá trình phân lớp dữ liệu văn bản: ................................................... 12
1.2.6. Đánh giá máy phân lớp dữ liệu văn bản ............................................. 14
1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp. .............................. 15
1.3. Các thuật toán học máy ứng dụng trong phân lớp .................................... 15
1.3.1. Phương pháp học có giám sát ............................................................. 15
1.3.2. Thuật toán phân lớp dữ liệu theo phương pháp học bán giám sát ...... 18
i
CHƯƠNG 2 BÀI TOÁN PHÂN LỚP ÁP DỤNG SVM VÀ PHƯƠNG PHÁP
HỌC BÁN GIÁM SÁT SVM ............................................................................. 21
2.1. Máy hỗ trợ vector – Support Vector Machine .......................................... 21
2.1.1. Giới thiệu về thuật toán SVM ............................................................. 22
2.1.2. Huấn luyện SVM ................................................................................ 23
2.1.3. Ưu điểm của SVM trong phân lớp văn bản ........................................ 24
2.2. Bán giám sát SVM và phân lớp trang Web .............................................. 26
2.2.1. Giới thiệu về bán giám sát SVM......................................................... 26
2.2.2. Phân lớp trang Web sử dụng bán giám sát SVM ................................ 27
CHƯƠNG 3 KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ ................................ 30
3.1. Giới thiệu về phần mềm SVMlin ............................................................. 30
3.2. Sử dụng phần mềm và kết quả đánh giá ................................................... 31
KẾT LUẬN ......................................................................................................... 34
TÀI LIỆU THAM KHẢO ................................................................................... 35
ii
DANH SÁCH HÌNH ẢNH
Tên hình
Số hình 1.1 1.2 Trang 5 8
1.3 13
1.4 18
Mô hình tổng quan về bài toán phân lớp Ví dụ về việc biểu diễn văn bản bởi vector đặc trưng Sơ đồ biểu diễn quá trình phân lớp dữ liệu văn bản Mặt siêu phẳng h phân các điểm thành 2 lớp + và - với khoảng cách biên lớn nhất. Các điểm gần mặt siêu phẳng h nhất là các vector hỗ trợ Thuật toán Self training Thuật toán Co training 1.5 1.6 19 20
iii
DANH SÁCH THUẬT NGỮ, CHỮ VIẾT TẮT
Chữ viết tắt
SVM: Support Vector Machine VC: Vapnik-Chervonenkis S3VM: Semi Supervised Support Vector Machine Trang 1 21 26
iv
MỞ ĐẦU
1. Tính cấp thiết của vấn đề nghiên cứu
Với xu hướng phát triển hiện tại, khối lượng dữ liệu trong cuộc sống
ngày càng lớn dẫn đến việc vai trò của phân lớp dữ liệu cũng ngày càng quan
trọng hơn, đây có thể được đánh giá là một trong các vấn đề bức thiết trong
ngành xử lý dữ liệu văn bản. Một trong các yêu cầu thiết yếu cần được đưa ra
là cải thiện hiệu suất của thuật toán thực hiện việc phân lớp, gia tăng giá trị
độ đo hồi tưởng, cũng như tính chính xác của phương pháp. Tuy nhiên trong
thực tế, nguồn dữ liệu được thiết lập nhãn trước không phải lúc nào cũng
được đáp ứng dẫn đến việc phải xây dựng các phương pháp phân lớp sử dụng
tập dữ liệu chưa gán nhãn. Để có thể thỏa mãn được cả hai yêu cầu trình bày
phía trên phương pháp phân lớp bán giám sát tỏ ra tương đối hiệu quả. Các
phương pháp phân lớp này tận dụng được các nguồn dữ liệu chưa được đánh
nhãn rất phong phú và đồng thời cũng tận dụng được hiệu quả một số lượng
nhỏ các dữ liệu đã được thiết lập nhãn sẵn.
Một trong các phương pháp được sử dụng và đánh giá tương đối tốt
trong thời gian qua để sử dụng trong các công việc nhận dạng hay phân loại
là phương pháp SVM - bộ phân loại máy hỗ trợ vector (Support Vector
Machine). Các nghiên cứu đã được công bố đã chứng minh về hiệu suất phân
loại văn bản khá tốt của phương pháp SVM.
2. Tổng quan về tình hình nghiên cứu thuộc lĩnh vực đề tài
Trong lĩnh vực khai phá dữ liệu, các phương pháp phân lớp văn bản đã
dựa trên những phương pháp quyết định như quyết định Bayes, cây quyết
định, K-người láng giềng gần nhất, …. Những phương pháp này đã cho kết
quả chấp nhận được và được sử dụng nhiều trong thực tế. Trong những năm
gần đây, phương pháp phân lớp sử dụng quá trình học máy bán giám sát
đang được quan tâm và sử dụng nhiều trong lĩnh vực nhận dạng, phân lớp.
Nhận thấy được tính mới trong vấn đề này nên tác giả lựa chọn đề tài
“Nghiên cứu về thuật toán phân lớp sử dụng quá trình học máy bán giám sát,
Trang 1
ứng dụng trong việc phân lớp trang Web” để sử dụng cho việc nghiên cứu
của mình.
3. Mục tiêu, đối tượng, phạm vi nghiên cứu
Những năm gần đây, thế giới chứng kiến sự phát triển bùng nổ của khoa
học nói chung và lĩnh vực công nghệ thông tin nói riêng. Chính điều này đã
làm gia tăng các hình thức trao đổi thông tin thông qua hệ thống Internet một
cách chóng mặt, có thể kể đến như thư viện điện tử, báo điện tử… Vì lý do
này mà lượng dữ liệu văn bản trên Internet cũng ngày càng tăng theo một
cách đáng kể, kèm theo đó là tốc độ của thông tin thay đổi cũng rất nhanh
chóng. Với lượng dữ liệu thông tin càng càng lớn, một trong những yêu cầu
bức thiết được lập ra là làm cách nào có thể tổ chức và khai thác được các
thông tin một cách hiệu quả. Để giải quyết được các yêu cầu trên thì bài toán
phân lớp là một trong những giải pháp thích hợp nhất. Tuy nhiên trong thực
tế, lượng thông tin lại quá lớn để có thể phân lớp một cách thủ công và các
thực hiện phân lớp bằng các phương pháp đơn giản thủ công là điều không
khả thi. Một chương trình máy tính thực hiện phân lớp các dữ liệu văn bản
một cách tự động chính là chìa khóa để giải quyết vấn đề này.
Trong thực tế, các khó khăn mà chúng ta thường phải đối mặt khi xử lý
các bài toán phân lớp tự động là làm thế nào để có thể tạo ra được một bộ
phân lớp có độ tin cậy cao khi số lượng dữ liệu được gán nhãn sẵn không có
sẵn. Các bộ dữ liệu được thiết lập nhãn sẵn này thường không có nhiều vì để
có được chúng đòi hỏi phải tốn nhiều công sức cũng như thời gian để xây
dựng thiết lập nhãn. Điều này dẫn đến việc phải có một phương pháp học
không đòi hỏi nhiều dữ liệu thiết lập nhãn sẵn và đồng thời tận dụng được
hiệu quả các nguồn dữ liệu chưa thiết lập nhãn có rất nhiều trong thực tế,
phương pháp học được lựa chọn để nghiên cứu ở đây là phương pháp học
bán giám sát. Thực chất phương pháp học bán giám sát có thể được xem là
cách học sử dụng dữ liệu chứa trong cả bộ dữ liệu chưa được thiết lập nhãn
Trang 2
và bộ dữ liệu đã được thiết lập nhãn. Vì ưu điểm tiện lợi của phương pháp
này nên nó được áp dụng khá rộng rãi.
Vì lý do trên, nghiên cứu tập trung vào việc trình bày về bài toán phân
lớp dữ liệu sử dụng phương pháp học bán giám sát và việc áp dụng phương
pháp học bán giám sát sử dụng máy hỗ trợ vector vào việc phân lớp dữ liệu
trên các trang Web. Mục tiêu chính của đề tài bao gồm:
+ Nghiên cứu thuật toán phân lớp sử dụng quá trình học máy bán giám sát.
+ Ứng dụng thuật toán trong việc phân lớp trang Web.
4. Phương pháp nghiên cứu, kết cấu của công trình nghiên cứu
Nghiên cứu định tính: Thực hiện tham khảo các bài báo khoa học liên
quan đến các thuật toán học máy và học máy bán giám sát cũng như tham
khảo các công trình đã công bố về lĩnh vực này.
Nghiên cứu định lượng: Cài đặt thuật toán, ứng dụng trong việc phân
lớp trang Web. Đánh giá kết quả đạt được đồng thời hiệu chỉnh thuật toán và
hệ thống để đạt được kết quả tốt nhất.
Nghiên cứu được trình bày trong 3 chương. Cấu trúc cụ thể như sau:
Chương 1: Tổng quan về việc phân lớp sử dụng phương pháp học bán
giám sát
Chương 2: Bài toán phân lớp áp dụng SVM và phương pháp học bán
giám sát SVM
Chương 3: Kết quả thử nghiệm và đánh giá.
5. Kết quả đạt được của đề tài
Kết quả đạt được của đề tài: là báo cáo về kết quả nghiên cứu thuật
toán phân lớp sử dụng quá trình học máy bán giám sát, và kết quả của việc
ứng dụng thuật toán trong việc phân lớp trang Web.
Trang 3
Đối tượng phục vụ: kết quả của nghiên cứu sẽ là tài liệu phục vụ cho
việc tham khảo và nghiên cứu của các đối tượng trong lĩnh vực Khai phá dữ
liệu.
CHƯƠNG 1
TỔNG QUAN VỀ VIỆC PHÂN LỚP SỬ DỤNG PHƯƠNG PHÁP
HỌC BÁN GIÁM SÁT
1.1. Tổng quan về phân lớp dữ liệu.
1.1.1. Tổng quan về bài toán phân lớp dữ liệu
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 cụ thể
vào một hoặc nhiều lớp dữ liệu đã xác định trước thông qua một mô hình phân
lớp được xây dựng từ trước dựa trên một tập đối tượng dữ liệu thiết lập nhãn sẵn
từ trước hay chúng ta vẫn thường gọi là tập huấn luyện. Quá trình phân lớp dữ
liệu còn có thể được gọi với một tên khác là quá trình thiết lập nhãn cho các đối
tượng dữ liệu.
Nhiệm vụ chính của việc phân lớp dữ liệu là tạo ra mô hình phân lớp để khi
có một đối tượng dữ liệu mới được đưa ra thì mô hình phân lớp dữ liệu sẽ xếp
đối tượng dữ liệu đó vào lớp nào hay có thể coi là thiết lập nhãn cho đối tượng
dữ liệu này.
Trong thực tế phân lớp dữ liệu có rất nhiều bài các bài toán khác nhau như
bài toán phân lớp nhị phân, bài toán phân lớp đa trị,….
Bài toán phân lớp nhị phân còn được hiểu là phân lớp đối tượng dữ liệu vào
một trong hai lớp cho trước khác nhau thông qua việc xem xét đối tượng dữ liệu
đó có hay không có các đặc tính phân loại được đặt ra theo quy ước của mô hình
phân lớp.
Bài toán phân lớp đa trị là bài toán phân lớp mà trong đó mỗi đối tượng dữ
liệu trong tập dữ liệu được gán nhãn cũng như các đối tượng dữ liệu chưa được
gán nhãn sau khi được phân lớp có thể được xếp vào hai lớp trở lên.
Trang 4
Tiếp theo đây, nghiên cứu sẽ trình bày tổng quan về quá trình phân lớp dữ
liệu và phương pháp phân lớp dữ liệu.
1.1.2. Tổng quan về quá trình phân lớp dữ liệu
Hình 1.1 Mô hình tổng quan về bài toán phân lớp
Như hình trên thể hiện quá trình phân lớp dữ liệu được thực hiện qua hai
bước chính:
Bước 1: Thiết lập mô hình phân lớp:
Mô hình phân lớp được tạo nên dựa trên việc phân tích các đối tượng dữ
liệu trong tập huấn luyện. Các lớp được gán nhãn của tập dữ liệu được gán nhãn
này được xác định thủ công từ trước, vì vậy phương pháp học này còn có thể
được gọi với tên khác là phương pháp học có giám sát (supervised learning). Tại
bước này, độ chính xác của mô hình cần được tính đến. Nếu độ chính xác của
mô hình là chấp nhận được mô hình phân lớp sẽ được dùng để xác định nhãn
cho các đối tượng chưa được gán nhãn. Trong quá trình đánh giá mô hình phân
lớp, độ đo sẽ được sử dụng để đánh giá độ chất lượng của các tập phân lớp.
Trong thực tế có nhiều phương pháp phân lớp dữ liệu để giải quyết các bài
toán phân lớp tùy thuộc vào cách tạo ra mô hình phân lớp. Có thể kể đến một số
phương pháp như Bayes, cây quyết định, SVM, K láng giềng gần nhất, .... Các
Trang 5
phương pháp phân lớp phân biệt nhau thông qua bộ| phân lớp. Bộ phân lớp còn
được gọi với tên gọi khác là thuật toán phân lớp.
Bước 2: Tiến hành phân lớp sử dụng mô hình phân lớp tạo ở bước 1.
Thuật toán phân lớp có thể coi là ánh xạ từ miền dữ liệu sẵn có sang một
miền giá trị cụ thể của nhãn lớp, dựa trên thuộc tính của các đối tượng dữ liệu.
1.2. Tổng quan về phân lớp dữ liệu văn bản
1.2.1. Thực trạng của vấn đề.
Các phương thức giao dịch sử dụng giấy tờ trong thời đại hiện nay thì
phương thức số dần đang thay thế các phương thức giao dịch truyền thống. Cụ
thể việc số hoá các giấy tờ có thể hiểu như việc chuyển các dữ liệu dạng giấy tờ
sang các định dạng số được lưu trữ trên máy tính hoặc truyền tải thông qua môi
trường internet. Lượng dữ liệu văn bản được lưu trữ trực tuyến hiện nay đang
gia tăng một cách chóng mặt do có nhiều ưu điểm như tiện dụng, gọn nhẹ và sự
lưu trữ ổn định lâu dài, dễ dàng hiệu chỉnh cũng như truyền gửi. Song song với
sự gia tăng số lượng văn bản thì nhu cầu khai thác tìm kiếm các dữ liệu văn bản
cũng đang trở thành một nhu cầu thiết yếu trong thời điểm hiện tại. Trong cuộc
sống hàng ngày, việc phân lớp các văn bản đa phần được thực hiện thủ công. Và
dễ thấy được cách thức phân loại này tốn kém về mặt thời gian cũng như công
sức của con người vì các văn bản rất lớn, để thực hiện phân lớp các văn bản theo
cách thức này về lâu dài là một vấn đề không khả thi. Từ đó chúng ta có thể
nhận thấy việc phân lớp văn bản tự động là một vấn đề bức thiết cần phải được
giải quyết.
Câu hỏi được đặt ra ở đây là phân lớp văn bản là gì? Phân lớp văn bản có
thể được hiểu là việc phân lớp dữ liệu áp dụng đối với các dữ liệu văn bản, hay
phân một văn bản vào một hay nhiều lớp văn bản thông qua một mô hình phân
lớp được xây dựng dựa trên một tập hợp các văn bản thiết lập nhãn từ trước.
Trang 6
Phân lớp dữ liệu văn bản hiện nay đang là một trong các lĩnh vực được
quan tâm hàng đầu và hiện đã và đang được đầu tư nghiên cứu tương đối nhiều
trong những năm gần đây trên khắp thế giới.
1.2.2. Sử dụng mô hình vector biểu diễn văn bản
Một trong những cách phổ biến được sử dụng để biểu diễn dữ liệu văn bản
là phương pháp biểu diễn bằng mô hình vector, mỗi văn bản sẽ được biểu diễn
thông qua một vector trọng số. Cụ thể phương pháp này sẽ coi mỗi một đối
tượng dữ liệu văn bản Di được biểu diễn dưới dạng 𝐷𝑖 = ( →, 𝑖), trong đó chỉ số i 𝑑𝑖
dùng để nhận diện văn bản này và → là vector đặc trưng biểu diễn cho văn bản 𝑑𝑖
Di . Cụ thể trong vector này: →=(wi1,wi2,…,win), với n là số luợng đặc trưng được 𝑑𝑖
trích chọn của văn bản, wij là trọng số của đặc trưng thứ j của văn bản Di,
j∈{1,2,...,n}.
Đối với việc chuyển đổi văn bản sang biểu diễn dưới dạng vector đặc trưng,
thì vấn đề cần quan tâm là việc lựa chọn đặc trưng nào và bao nhiêu đặc trưng,
phương thức chọn ra sao?
Các đặc trưng trong vector biểu diễn văn bản
Số chiều của không gian vector đặc trưng biểu diễn văn bản thường
lớn và phụ thuộc vào lượng thông tin trong các văn bản.
Các đặc trưng trong vector biểu diễn của văn bản thường độc lập nhau.
Các đặc trưng rời rạc: vector đặc trưng di có thể có nhiều trọng số đặc
trưng bằng 0 do có nhiều đặc trưng không xuất hiện trong văn bản di,
tuy vậy nếu đơn thuần chỉ dùng cách tiếp cận sử dụng bộ giá trị 0, 1 thì
kết quả phân lớp sẽ bị hạn chế là do có thể có các đặc trưng không có
trong văn bản đang xét nhưng trong văn bản đang xét lại có nội dung
có ý nghĩa tương đồng với đặc trưng bị bỏ qua này, do điều này chúng
ta có thể lựa chọn cách tiếp cận khác là không sử dụng bộ số 0, 1 mà
sử dụng giá trị các giá trị thực để phần nào giảm bớt sự rời rạc trong
vector đặc trưng biểu diễn văn bản.
Trang 7
Đa số các văn bản có thể được phân loại một cách tuyến tính bằng
cách sử dụng các hàm tuyến tính.
Theo đó, số chiều của vector là số lượng các từ xuất hiện trong ít nhất
một mẫu dữ liệu đã được thiết lập nhãn. Trước khi thiết lập các trọng
số đặc trưng cho các từ khoá phân loại cần thực hiện loại trừ những từ
dừng. Từ dừng ở đây được hiểu là các từ thường xuất hiện nhưng
không đem lại lợi ích trong việc phân lớp dữ liệu văn bản chẳng hạn
như “như vậy”, “tuy”, “là”, “và”, “thì”, “and”, “but”, “the”, “or”, ….
thường chúng ta có thể nhận biết các từ dừng có thể kể đến như các
trạng từ hoặc liên từ hay giới từ.
Chúng ta có thể xem xét ví dụ sau về việc biểu diễn văn bản dưới dạng vector
đặc trưng:
Hình 1.2 Ví dụ về việc biểu diễn văn bản bởi vector đặc trưng
Biểu diễn dữ liệu văn bản dạng trang Web
Về mặt bản chất các trang web thực chất là các siêu văn bản. Ngoài các
thành phần dữ liệu văn bản và các thành phần dữ liệu media, trong các trang
Web còn chứa các thành phần đặc trưng như các Hyperlink, các tag định dạng
Trang 8
HTML và các meta-data. Kết quả của phần lớn nghiên cứu chỉ ra công việc phân
lớp Web được cung cấp thông tin chủ yếu nhở các thành phần băn bản trong
trang web và được gia tăng hiệu suất nhờ vào những thành phần không phải văn
bản.
Ở thời điểm hiện tại để biểu diễn một trang Web người ta có thể sử dụng
nhiều cách khác nhau, tùy theo mục đích chúng ta có thể lựa chọn các cách thức
biểu diễn riêng. Các bộ máy tìm kiếm của các hãng lớn như Google hay Yahoo...
đều sử dụng hệ thống từ khóa móc nối thay vì lựa chọn cách biểu diễn sử dụng
vector.
Các hệ thống văn bản cũ trước đây thường thực hiện các công việc tìm
kiếm, biểu diễn, phân lớp... theo các phương pháp dựa trên việc xem trang Web
như một văn bản thông thường và biểu diễn văn bản đó bằng vector. Siêu liên
kết được sử dụng kết nối các trang Web thể hiện được các mối liên hệ giữa nội
dung giữa các trang, Từ đó chúng ta có thể nâng cao hiệu suất của các công việc
như phân lớp và tìm kiếm giúp khai thác được các ưu điểm của hyperlink trong
các văn bản. Một số nghiên cứu gần đây đã chi ra cách nâng cao hiệu quả thông
qua phương pháp bổ sung thêm các từ khoá bằng cách mở rộng thêm các từ
khoá mới trong các văn bản lân cận với siêu liên kết.
Trong nghiên cứu này sẽ tập trung vào cách biểu diễn trang Web bằng cách
sử dụng mô hình vector. Sử dụng các thông tin liên kết với mục đích cải thiện độ
chính xác của công việc tìm kiếm và các công việc phân lớp các trang Web bằng
cách bổ sung các thông tin về các trang Web láng giềng vào vector đặc trưng
biểu diễn cho trang đang được xét.
Hiện nay tồn tại bốn cách chính để biểu diễn trang Web dưới dạng vector
như sau:
Cách thứ nhất
Lưu trữ các từ khóa cùng tần số xuất hiện từ khóa đó trong trang Web được
xét. Cách lưu trữ này bỏ qua tất các thông tin khác như vị trí của từ khoá trong
Trang 9
trang đang xét cũng như thứ tự của các từ trong trang cùng các thông tin khác
như hyperlink.
Cách biểu diễn này được cho là phương pháp hiệu quả nhất cho các trường
hợp tài liệu đã liên kết độc lập với các nhãn của các lớp nhưng với một số
trường hợp đặc biệt khác thì phương pháp lại không tận dụng được tính cân đối
của tài liệu siêu liên kết.
Cách thứ hai
Móc nối trang được xét tới các trang láng giềng để tạo ra một super
document thông qua thông tin liên kết của trang đó. Vector đặc trưng của văn
bản gồm thông tin về các từ xuất hiện trong trang trong các trang láng giềng của
nó đi kèm với tần số có mặt của các từ đó. Phương pháp này cũng giống như
phương pháp trên bỏ qua các thông tin liên quan đén vị trí xuất hiện và thứ tự
xuất hiện của các từ khóa.
Điểm yếu của phương pháp này là gây phân tán nội dung của trang web
đang quan tâm. Tuy vậy với trường hợp biểu diễn cho một tập các trang web
tương đồng về nội dung chủ đề thì đây lại là phương pháp tương đối tốt. Tuy
nhiên việc các trang web liên kết cùng chủ điểm hiện nay chưa thật sự phổ biến
nên phương pháp này ít được lựa chọn.
Cách thứ ba
Phương pháp biểu diễn trang web dùng một vector có cấu trúc gồm lớn hơn
2 thành phần. Mỗi thành phần trong vector biểu diễn một tập các trang lân cận
với trang được xét. Số chiều của vector cố định nhưng mỗi thành phần của
vector đó chỉ biểu diễn cho các từ khóa xuất hiện trong một tập.
Phương pháp này khắc phục được tình trạng các từ khóa của trang láng
giềng làm loãng nội dung của trang web đang được xét. Nếu thông tin mở rộng
trang láng giềng thực sự hữu ích cho công việc phân lớp thì mô hình học vẫn có
thể truy cập đến toàn bộ nội dung trong trang láng giềng đó để học.
Cách thứ tư
Trang 10
Phương pháp biểu diễn trang web thông qua vector có cấu trúc. Cụ thể các
bước thực hiện xây dựng vector gồm các bước như sau:
Bước 1: Gán d là bậc cao nhất của các trang trong tập được xét.
Bước 2: Thiết lập vector với cấu trúc gồm d + 1 các phần:
- Phần 1 biểu diễn chính cho trang Web đang xét.
- Phần 2 đến phần thứ d+1 biểu diễn các trang láng giềng của trang được
biểu diễn ở phần 1, mỗi trang láng giềng được biểu diễn ở 1 phần riêng rẽ.
Từ đó thông qua các cách biểu diễn trang web bằng vector như đã trình bày
ở phía trên ta có thể thấy rằng đa phần các phương pháp biểu diễn trang web
bằng mô hình vector sẽ kết hợp các thông tin về web đó với các trang láng giềng
để có được hiệu suất phân lớp tốt hơn so với hiệu suất của phương pháp biểu
diễn trang web bằng mô hình vector lưu thông tin về từ khóa và số lần xuất hiện
của nó chỉ trong trang web đang xét.
1.2.3. Tổng quan về phương pháp phân lớp văn bản
Hiện nay, có rất nhiều các phương pháp dùng để phân lớp văn bản như
phương pháp Bayes, sử dụng cây quyết định, k láng giềng gần nhất hay SVM.
Thuật toán học máy thường được sử dụng để xây dựng mô hình phân lớp
văn bản một cách tự động. Ngoài ra chúng ta còn có thể kể đến các phương
pháp đặc biệt hơn dùng để phân lớp trong một số lĩnh vực. Ví dụ khi mô hình
phân loại thấy xuất hiện một cụm từ trong văn bản thì hệ thống sẽ phân văn bản
đó vào một lớp nào đó. Trong trường hợp các văn bản có số đặc trưng hơn
không nhiều như vậy thì chúng ta đưa ra các phương pháp phân lớp dựa vào nội
dung trong văn bản độ phù hợp của văn bản đó với các văn bản trong tập huấn
luyện. Trong mô hình học máy được áp dụng, văn bản trong tập huấn luyện đã
được gán nhãn trước và mô hình phân loại cần phải tìm cách để trích chọn ra các
đặc trưng của các văn bản thuộc mỗi lớp.
Trang 11
1.2.4. Ứng dụng của việc phân lớp dữ liệu văn bản
Phân lớp dữ liệu văn bản có vai trò vô cùng quan trọng với công việc tìm
kiếm dữ liệu văn bản. Thông qua phân lớp văn bản chúng ta có thể xác định ra
được chủ để phân lớp dữ liệu muốn tìm kiếm.
Ngoài ra chúng ta có thể kể đến một ứng dụng nữa của việc phân lớp dữ
liệu văn bản là việc ứng dụng để lọc văn bản hoặc một phần văn bản chứa những
thông tin cần tìm mà không làm mất hay ảnh hưởng tới tính phức tạp ngôn ngữ
tự nhiên.
Phân lớp dữ liệu văn bản còn có rất nhiều ứng dụng đa dạng khác trong
thực tế, điển hình chúng ta có thể kể đến những ứng dụng trích chọn thông tin
trên mạng Internet. Có rất nhiều trang có nội dung không lành mạnh hay phản
động hoặc đăng những nội dung sau sự thật nhằm tăng lượng người xem, những
nội dung này có khả năng lẫn lộn vào kết quả trả về của các bộ máy tìm kiếm
thông tin trên mạng hoặc có thể gây phiền toái cho những người dùng internet
bằng các email rác. Từ đó chúng ta ngày càng thấy rõ sự cần thiết của việc ứng
dụng việc phân lớp văn bản vào việc xây dựng các mô hình lọc thông tin trên
mạng internet.
Từ đó có thể thấy rằng phân lớp văn bản đã và đang là một trong các công
cụ không thể thiếu trong thời đại hiện nay, vì vậy phân lớp dữ liệu văn bản đang
là một trong các vấn đề được quan tâm phát triển được hàng đầu với mục đích
tạo ra những công cụ hữu ích cho thế giới nói chung và lĩnh vực công nghệ
thông tin nói riêng.
1.2.5. Quá trình phân lớp dữ liệu văn bản:
Phân lớp dữ liệu văn bản có thể chia làm 4 bước cơ bản sau:
Trang 12
Sơ đồ dưới đây thể hiện bộ khung cho việc phân lớp dữ liệu văn bản,
trong đó có thể kể đến ba công đoạn chính:
Công đoạn 1: Biểu diễn đối tượng văn bản dưới dạng có cấu trúc, xây
dựng tập dữ liệu được gán nhãn.
Công đoạn 2: Dùng các kỹ thuật học máy để tiến hành huấn luyện trên các
mẫu vừa được biểu diễn ở công đoạn 1. Thực chất công đoạn 1 tạo ra các
vector đầu vào cho công đoạn 2.
Công đoạn 3: Mở rộng các dữ liệu thêm vào được cung cấp bởi người
dùng để cải thiện hiệu suất.
Trang 13
Hình 1.3 Sơ đồ biểu diễn quá trình phân lớp dữ liệu văn bản
1.2.6. Đánh giá máy phân lớp dữ liệu văn bản
Trong thực tế không có một phương pháp phân lớp dữ liệu văn bản nào là
tuyệt đối trong mọi hoàn cảnh. Bất cứ một phương pháp phân loại nào cũng đều
tồn tại độ sai số. Do đó chỉ ra độ đo để có thể đánh giá chính xác được hiệu suất
của mô hình phân lớp sẽ giúp xác định được phương pháp nào là tốt hay không
tốt. Có thể đưa ra một số công thức chung để đánh giá hiệu suất của các mô hình.
Độ hồi tưởng và độ chính xác, độ và độ đo F1 được sử dụng khá phổ biến
trong việc đánh giá độ chính xác của các mô hình phân lớp.
Để dễ hiểu hơn, chúng ta có công thức:
Trang 14
1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp.
Phân lớp dữ liệu văn bản hiện đang có vai trò rất quan trọng trong sự phát
triển của toàn thế giới, tùy vào độ phức tạp của từng loại văn bản khả năng thực
thi của các mô hình phân lớp sẽ khác nhau. Có 3 yếu tố thiết yếu ảnh hưởng đến
kết quả của việc phân lớp có thể kể đến:
Tập dữ liệu được thiết lập nhãn trước phải đủ lớn để huấn luyện cho mô
hình phân lớp. Có được một tập dữ liệu chuẩn và đủ lớn sẽ giúp cho việc học
của mô hình được tốt hơn và đem lại kết quả phân lớp sau này chính xác hơn.
Phương pháp tách từ khóa trong văn bản ảnh hưởng tới quá trình biểu diễn
văn bản bằng vector vì các phương pháp tách đơn giản thường sẽ gặp vấn đề với
những ngôn ngữ khác nhau, do đó việc xây dựng phương pháp tách từ khóa là
một yếu tố thiết yếu.
Phân lớp dữ liệu văn bản phải sử dụng thuật toán hợp lý về thời gian xử lý
gồm: thời gian để huấn luyện và thời gian thực hiện phân lớp, thêm nữa thuật
toán sẽ không phân lớp lại toàn bộ tập văn bản khi thêm vào đối tượng dữ liệu
văn bản mới mà chỉ thực hiện phân lớp cho đối tượng văn bản mới, ngoài ra
thuật toán cần có khả năng giảm nhiễu khi phân lớp dữ liệu văn bản.
1.3. Các thuật toán học máy ứng dụng trong phân lớp
1.3.1. Phương pháp học có giám sát
1.3.1.a. Tổng quan về bài toán học có giám sát
Trang 15
Mục tiêu của bài toán là để huấn luyện tạo nên một hàm ánh xạ từ tập X
tới tập Y. Cụ thể nếu tập huấn luyện gồm các cặp (xi , yi ), với yi ∈Y là nhãn
phân loại của mẫu xi∈X. Một thủ tục chuẩn là các cặp (xi, yi) được thử theo
giả thiết độc lập trên khắp miền giá trị X × Y.
1.3.1.b. Giới thiệu về phương pháp học có giám sát
• Bước 1: Xác định thể loại của tập dữ liệu huấn luyện.
• Bước 2: Tiến hành Thu thập tập dữ liệu huấn luyện.
• Bước 3: Thiết lập cấu trúc biểu diễn các đặc trưng đầu vào.
• Bước 4: Thiết lập cấu trúc của hàm chức năng cần huấn luyện và
Giải quyết bài toán học có giám sát cần có nhiều bước khác nhau:
• Bước 4: Hoàn thiện việc học.
phương pháp học tương ứng.
1.3.1.c. Phương pháp học có giám sát sử dụng thuật toán k láng
giềng gần nhất.
Như đã trình bày phía trên, có rất nhiều thuật toán học có giám sát trong
Trang 16
thực tế, trong nghiên cứu này tôi sẽ giới thiệu một phương pháp học sử dụng
thuật toán k láng giếng gần nhất, một phương pháp học có giám sát điển hình.
Phương pháp này được đánh giá là một trong những phương pháp hàng đầu
được áp dụng từ những ngày đầu trong nghiên cứu phân loại dữ liệu văn bản.
Phương pháp này sử dụng ý tưởng là khi cần phân loại một đối tượng
văn bản, thuật toán sẽ tính khoảng cách (Euclide, Manhattan, Cosine, …) của
tất cả đối tượng văn bản trong tập dữ liệu văn bản đã thiết lập nhãn đến đối
tượng văn bản này để xác định k văn bản có khoảng cách gần nhất, được gọi
là k láng giềng gần nhất, sau đó đánh trọng số cho các chủ để bằng các
khoảng cách này. Trọng số một chủ đề chính là tổng khoảng cách ở trên của
các văn bản trong k văn bản gần nhất cùng chủ đề, chủ đề nào không xuất
hiện trong k văn bản thì trọng số được thiết lập là 0. Các chủ đề tiếp đó sẽ
được sắp xếp lại theo chiều giảm dần của trọng số. Các chủ đề trọng số cao
sẽ được coi là nhãn của đối tượng dữ liệu văn bản cần phân loại.
chủ đề cj đối với văn bản x được tính giá trị trọng số như sau :
Trong đó:
Giá trị y (di, c) thuộc vào miền {0,1}, với:
y = 0: văn bản di không được gán nhãn chủ đề cj
y = 1: văn bản di được gán nhãn chủ đề cj
sim (x, d): độ tương đồng giữa văn bản x và văn bản d. Có thể dùng
công thức cosine để tính khoảng cách giữa 2 vector biểu diễn văn bản:
Trang 17
bj là ngưỡng phân loại của nhãn cj giá trị này có được sau quá trình huấn
luyện.
1.3.1.d. Phương pháp học có giám sát sử dụng Support vector
machine (SVM)
Máy hỗ trợ vector là phương pháp phân lớp đặc biệt hiệu quả trong giải
quyết nhận dạng mẫu chỉ có hai lớp sử dụng nguyên lý Giảm tiểu tối đa rủi ro
cấu trúc.
Thuật toán có ý tưởng chính là với một tập huấn luyện được biểu diễn
trong không gian vector và mỗi đối tượng tài liệu được xem là 1 điểm, mục
tiêu phương pháp là tìm ra một mặt siêu phẳng h chia các điểm trong không
gian này thành hai lớp + và -. Khoảng cách từ điểm gần nhất tới mặt phẳng
càng lớn thì việc phân loại càng chính xác.
Hình 1.4 Mặt siêu phẳng h phân các điểm thành 2 lớp + và - với
khoảng cách biên lớn nhất. Các điểm gần mặt siêu phẳng h nhất là
các vector hỗ trợ
1.3.2. Thuật toán phân lớp dữ liệu theo phương pháp học bán giám sát
1.3.2.a. Khái niệm
Phương pháp học bán giám sát là một phương phương pháp học trong
ngành học máy sử dụng đồng thời dữ liệu đã thiết lập nhãn và cả dữ liệu chưa
xác định nhãn. Trong thực tế để có được dữ liệu xác định nhãn đòi hỏi nhiều
thời gian và công sức nhưng ngược lại dữ liệu chưa gán nhãn lại có tương đối
Trang 18
sẵn trong thế giới hiện tại. Từ đây, ta có thể thấy được phương pháp học bán
giám sát có thể giúp thực hiện các công việc với quy mô lớn.
Phương pháp học bán giám sát bao gồm dữ liệu huấn luyện và dữ liệu
chưa xác định nhãn. Phương pháp này có thể được dùng trong các công việc
phân lớp hay phân nhóm. Phương pháp học bán giám sát có mục tiêu nhằm
vào việc huấn luyện mô hình phân lớp tốt hơn phương pháp học có giám sát
cùng trên tập dữ liệu xác định nhãn và chưa được xác định nhãn.
1.3.2.b. Tổng quan về một số phương pháp học bán giám sát
Hiện nay học bán giám sát có rất nhiều phương pháp được sử dụng cũng
như được nghiên cứu và phát triển. Có thể kể đến một số phương pháp phổ
biến như: Naïve Bayes, self-training hay co-training và transductive support
vector machine,... Về cơ bản không thể xác định được chính xác phương
pháp hiệu quả nhất trong các phương pháp này.
Tiếp theo, chúng ta sẽ tìm hiểu tổng quan một số thuật toán học bán
giám sát thường gặp.
Self-training
Self-training sử dụng một tập phân lớp ban đầu được cùng với một
lượng nhỏ dữ liệu đã xác định nhãn. Tập phân lớp sẽ được dùng để thiết lập
nhãn cho dữ liệu chưa xác định nhãn. Có thể thấy rằng hầu hết các đối tượng
dữ liệu chưa phân loại có độ tin cậy cao, cũng như các nhãn dự đoán trước
của chúng. Các dữ liệu này sau khi phân lớp sẽ được thêm vào tập huấn
luyện. Mô hình phân lớp sẽ được huấn luyện lại. Chú ý rằng việc tự học ở
đấy chính là việc mô hình phân lớp học trên chính các dữ liệu mà nó đã phân
loại.
Thuật toán học Self-training có thể được dùng trong việc xử lý các bài
toán của một số ngôn ngữ tự nhiên. Ngoài ra thuật toán này còn có thể được
dùng trong phân tách và dịch máy.
Trang 19
Hình 1.5 Thuật toán học self training
Co-training
Thuật toán học Co training là thuật toán được dựa trên giả thiết rằng các
đặc trưng có thể được tách ra thành hai tập đặc trưng. Mỗi một tập đặc trưng
lại có khả năng huấn luyện một mô hình phân lớp tốt.
Hình 1.6 Thuật toán học Co training
Trang 20
CHƯƠNG 2
BÀI TOÁN PHÂN LỚP ÁP DỤNG SVM VÀ PHƯƠNG PHÁP HỌC
BÁN GIÁM SÁT SVM
Trong các nghiên cứu thời gian gần đây, phương pháp phân lớp dùng tập
phân lớp vector hỗ trợ đang được nghiên cứu và áp dụng tương đối mạnh mẽ
trong lĩnh vực phân lớp và nhận dạng. SVM là phương pháp được ra đời từ lý
thuyết học thống kê do Vapnik và Chervonenkis nghiên cứu và phát triển. Đây
là phương pháp có nhiều tiềm năng phát triển về trong thực tiễn cũng như trong
các nghiên cứu lý thuyết. Từ kết quả của những nghiên cứu gần đây cho thấy
rằng SVM là phương pháp có khả năng phân lớp khá tốt không chỉ đối với bài
toán phân lớp dữ liệu văn bản mà còn trong nhiều ứng dụng như nhận dạng văn
bản viết tay, phát hiện mặt người khung hình… Khả năng phân lớp của phương
pháp SVM được đánh giá là khá cao so với các phương pháp khác.
2.1. Máy hỗ trợ vector – Support Vector Machine
SVM sử dụng thuật toán học với mục tiêu tìm ra một mặt siêu phẳng làm
nhỏ nhất có thể độ phân lớp sai cho một đối tượng dữ liệu mới. Độ phân lớp sai
của một mặt siêu phẳng được đặc trưng bởi khoảng cách từ điểm gần nhất tới
siêu phẳng đấy.
Đặc trưng thiết yếu thể hiện khả năng của mô hình phân lớp chính là khả
năng phân lớp những dữ liệu mới sau quá trình huấn luyện. Phương pháp huấn
luyện sẽ được đánh giá là tốt nếu hiệu suất tổng quát hoá của mô hình phân lớp
cao và ngược lại phương pháp huấn luyện sẽ được đánh giá là chưa tốt nếu hiệu
suất tổng quát hóa của mô hình là thấp. Hiệu suất tổng quát hoá ở đây phụ thuộc
vào hai yếu tố là năng lực của máy học và sai số huấn luyện. Trong các tham số
này thì sai số huấn luyện được hiểu là tỷ lệ sai lỗi của quá trình phân lớp trên tập
dữ liệu huấn luyện. Còn yếu tố thứ hai năng lực của máy học được xác định
bằng kích thước VC (Vapnik-Chervonenkis). Đây được coi là một khái niệm
quan trọng đối với một mô hình phân lớp. Kích thước VC được tính bởi số điểm
cực đại mô hình phân lớp có thể tách trong không gian đối tượng cần phân loại.
Trang 21
2.1.1. Giới thiệu về thuật toán SVM
m
i∈ R }
Xét ví dụ về bài toán phân tập dữ liệu mẫu thành 2 lớp:
{( x i, yi) i = 1, 2,…, N, x
Trong đó đối tượng dữ liệu mẫu ở đây chính là các vector đối tượng được
phân lớp và lớp chúng ta sẽ chia thành lớp các mẫu dương và lớp các mẫu âm
như trong hình 1.4:
Lớp các mẫu dương là lớp các mẫu xi thuộc vào lĩnh vực được quan tâm
và được thiết lập nhãn yi = 1.
Lớp các mẫu âm là các mẫu xi không thuộc vào lĩnh vực được quan tâm
và được thiết lập nhãn yi = - 1.
Phương pháp về bản chất chính là một bài toán tối ưu, mục tiêu của bài
toán này là tìm ra một không gian H và mặt siêu phẳng quyết định h trên H sao
với sai số phân lớp là cực tiểu.
Mô hình phân lớp SVM ở đây thực chất chính là mặt siêu phẳng phân tách
các mẫu dương và âm với độ chênh lệch là lớn nhất, độ chênh lệch ở đây được
xác định bằng khoảng cách nhỏ nhất giữa các mẫu dương và các mẫu âm với
mặt siêu phẳng.
Phương trình của mặt siêu phẳng có thể xác định như sau:
C + w1 x1 + w2 x2 + … + wn xn = 0
Hoặc chúng ta có thể sử dụng công thức tương đương sau để biểu diễn cho
C + ∑wi xi = 0 (2.2)
phương trình của mặt siêu phẳng
với i=1,…,n
Trang 22
w = w1 + w2 + …+ wn là bộ hệ số siêu phẳng hay là vector trọng số của mặt
siêu phẳng, C là độ dịch, Thay đổi w và C có thể làm thay đổi hướng và khoảng
cách từ gốc toạ độ đến mặt siêu phẳng.
Tập phân lớp SVM được định nghĩa như sau:
(2.3) f(x) = sign(C + ∑wi xi)
sign(z) = +1 nếu z ≥0,
sign(z) = -1 nếu z < 0.
Khi f(x) = 1 thì xác định x thuộc về lĩnh vực được quan tâm, và ngược lại,
nếu f(x) = -1 thì x không thuộc vào lĩnh vực cần quan tâm.
Mô hình học SVM có thể được coi là một mô hình học với các siêu phẳng
phụ thuộc vào tham số vector trọng số w của mặt siêu phẳng và tham số độ dịch
C. Mục tiêu của mô hình học SVM là xác định được w và C để có thể cực đại
hoá khoảng cách tối thiểu giữa các điểm dương và điểm âm với mặt siêu phẳng.
Về cơ bản việc xây dựng mô hình cần phải giải phương trình sau:
để có thể tìm ra được vector trọng số
w và sai số của mỗi điểm trong tập
huấn luyện để có được phương trình tổng quát của mặt siêu phẳng:
f(x1, x2,…, xn) = C +∑ wi xi
Với i = 1,…, n. Trong đó n là tổng số các đối tượng dữ liệu dùng để huấn
luyện.
2.1.2. Huấn luyện SVM
Để huấn luyện máy hỗ trợ vector thực chất chúng ta sẽ tiến hành giải bài
toán quy hoạch toàn phương Support Vector Machine. Để giải bài toán này
chúng ta có thể dùng các phương pháp số. Cụ thể các phương pháp này cần một
Trang 23
ma trận kích thước bằng bình phương của số lượng mẫu dùng trong việc training.
Điều này trong thực tế đôi khi không khả thi vì kích thước của tập dữ liệu dùng
để training thường rất lớn (thậm chí có thể đến hàng chục nghìn mẫu huấn
luyện). Nhằm giải quyết vấn đề nêu trên người ta đã phát triển nhiều thuật toán
khác nhau dựa trên việc phân rã tập training thành những nhóm dữ liệu. Lúc này
bài toán quy hoạch toàn phương sẽ được giải với kích thước nhỏ hơn. Sau đó,
những thuật toán này sẽ kiểm tra các điều kiện Karush KuhnTucker để tìm ra
được phương án tối ưu nhất.
Một vài phương pháp huấn luyện dựa vào tính chất: Nếu trong tập training
của bài toán quy hoạch toàn phương Support Vector Machine con (bài toán nhỏ)
có ít nhất một mẫu vi phạm vào điều kiện Karush KuhnTucker, thì bài toán này
sau khi được giải, hàm mục tiêu sẽ tăng. Một loạt các bài toán quy hoạch toàn
phương Support Vector Machine con với ít một mẫu nào đó vi phạm các điều
kiện Karush KuhnTucker được đảm bảo sẽ sự hội tụ đến phương án tối ưu.
2.1.3. Ưu điểm của SVM trong phân lớp văn bản
Chúng ta có thể thấy từ các thuật toán phân lớp hai lớp như SVM đến các
thuật toán phân lớp đa lớp đều có đặc điểm chung là yêu cầu văn bản phải được
biểu diễn dưới dạng vector đặc trưng, tuy nhiên các thuật toán khác đều phải sử
dụng các uớc lượng tham số và ngưỡng tối ưu trong khi đó thuật toán SVM có
thể tự tìm ra các tham số tối ưu này. Trong các phương pháp thì SVM là phương
pháp sử dụng không gian vector đặc trưng lớn nhất (hơn 10.000 chiều) trong khi
đó các phương pháp khác có số chiều bé hơn nhiều (như Naïve Bayes là 2000,
k-Nearest Neighbors là 2415…).
Trang 24
Trong công trình của mình năm 1999, Joachims đã so sánh SVM với Naïve
Bayesian, k-Nearest Neighbour, Rocchio, và C4.5 và đến năm 2003, Joachims
đã chứng minh rằng SVM làm việc rất tốt cùng với các đặc tính được đề cập
trước đây của văn bản. Các kết quả cho thấy rằng SVM đưa ra độ chính xác
phân lớp tốt nhất khi so sánh với các phương pháp khác.
Theo Xiaojin Zhu thì trong các công trình nghiên cứu của nhiều tác giả
(chẳng hạn như Kiritchenko và Matwin vào năm 2001, Hwanjo Yu và Han vào
năm 2003, Lewis vào năm 2004) đã chỉ ra rằng thuật toán SVM đem lại kết quả
tốt nhất phân lớp văn bản.
Kiritchenko và Matwin đã nghiên cứu và so sánh phương pháp SVM với
kỹ thuật Naïve Bayesian, sau đó đã chứng minh được rằng SVM là phương pháp
tốt nhất cho phân lớp thưđiện tử cũng như phân lớp văn bản.
Hwanjo Yu và Han cho thấy rằng SVM hoàn toàn được tiến hành tốt nhất
so với các phương pháp phân lớp văn bản khác. Tất cả các tài liệu nghiên cứu
hiện nay cho thấy rằng SVM đưa ra kết quả chính xác nhất trong khía cạnh phân
lớp văn bản.
Lewis đã nghiên cứu phân lớp văn bản và đã khám phá ra rằng kết quả của
SVM là tốt nhất. Lewis đã đưa ra tập hợp nhỏ các tài liệu của phân lớp văn bản.
Tác giả đã cố gắng cải tiến phương pháp RCV1 cho phân lớp văn bản và sử
dụng phương pháp mới được ứng dụng cho một số kỹ thuật phân lớp văn bản
khác nhau. SVM đã đưa ra kết quả tốt nhất khi đặt dựa vào k-người láng giềng
gần nhất và kỹ thuật tập phân lớp RocchioStyle Prototype.
Những phân tích của các tác giả trên đây cho thấy SVM có nhiều điểm phù
hợp cho việc ứng dụng phân lớp văn bản. Và trên thực tế, các thí nghiệm phân
lớp văn bản tiếng Anh chỉ ra rằng SVM đạt độ chính xác phân lớp cao và tỏ ra
xuất sắc hơn so với các phương pháp phân lớp văn bản khác.
Vấn đề căn bản của học bán giám sát là chúng ta có thể tận dụng dữ liệu
chưa gán nhãn để cải tiến hiệu quả của độ chính xác trong khi phân lớp, điều này
Trang 25
được đưa ra để so sánh với một tập phân lớp được thiết kề mà không tính đến dữ
liệu chưa gán nhãn.
Trong phần sau của chương này, nghiên cứu sẽ giới thiệu một phương thức
cải tiến của SVM là bán giám sát SVM (semi-supervised support vector machine – S3VM). Bán giám sát SVM được đưa ra nhằm nâng SVM lên một mức cao
hơn, trong khi SVM là một thuật toán học có giám sát, sử dụng dữ liệu đã gán
nhãn thì bán giám sát SVM sử dụng cả dữ liệu gán nhãn (tập huấn luyện –
training set) kết hợp với dữ liệu chưa gán nhãn (working set).
2.2. Bán giám sát SVM và phân lớp trang Web
2.2.1. Giới thiệu về bán giám sát SVM
Chúng ta sẽ giới thiệu phương thức cải tiến của SVM là Bán giám sát
SVM (Semi Supervised Support Vector Machine - S3VM). Cho một tập huấn
luyện (training set) của dữliệu gán nhãn và có sự tham gia của một tập các dữ
liệu chưa gán nhãn (working set), S3VM xây dựng một máy hỗ trợ vector sử
dụng cả training set và working set. Bài toán truyền dẫn sẽ dựđoán giá trị của
một hàm phân lớp tới các điểm đã cho trong working set.
Trong khi SVM là một thuật toán có giám sát sử dụng dữ liệu đã gán nhãn,
thì S3VM được xây dựng sử dụng hỗn hợp dữ liệu gán nhãn (training set) và dữ
liệu chưa gán nhãn (working set). Mục đích là để gán các lớp nhãn tới working
set một cách tốt nhất, sau đó sử dụng hỗn hợp dữ liệu huấn luyện đã gán nhãn và
dữ liệu working set sau khi đã gán nhãn để phân lớp những dữ liệu mới. Nếu
working set rỗng thì phương pháp này trở thành phương pháp chuẩn SVM để
phân lớp. Nếu training set rỗng, sau đó phương pháp này sẽ trở thành hình thể
học không giám sát. Học bán giám sát xảy ra khi cả training set và working set
không rỗng.
Để hiểu một cách rõ ràng cụ thể về S3VM, thì chúng ta cần hiểu về SVM
đã được trình bày ở trên. Với thời gian và điều kiện không cho phép, trong khoá
Trang 26
luận này em chỉ có thể tìm hiểu về thuật toán S3VM là bài toán phân lớp nhị
phân.
Cho trước một tập huấn luyện gồm những dữ liệu đã gán nhãn cùng với tập
dữ liệu chưa gán nhãn working set bao gồm n dữ liệu. Mục đích là gán nhãn cho
những dữ liệu chưa gán nhãn này.
Với hai lớp đã cho trước gồm lớp dương (lớp +1) và lớp âm (lớp –1). Mỗi
dữ liệu được xem như một điểm trong không gian vector. Mỗi điểm i thuộc tập
dữ liệu huấn luyện có một sai số là ηivà mỗi điểm j thuộc working set sẽ có hai
sai sốξj (sai số phân lớp với giả sử rằng j thuộc lớp +1) và zi (sai số phân lớp với
giả sử rằng j thuộc lớp –1).
S
au khi đã tìm được ξi và zj, chúng ta sẽ có được sai số nhỏ nhất của mỗi điểm j,
Nếu ξi < zj thì điểm j thuộc lớp dương, ngược lại nếu ξi> zj thì điểm j thuộc
lớp âm. Quá trình này diễn ra trên tất cả các điểm thuộc working set, sau khi quá
trình này đã hoàn thành, tất cả các điểm chưa gán nhãn sẽđược gán nhãn.
Tập dữ liệu chưa gán nhãn working set sau khi đã gán nhãn sẽđược đưa vào
tập dữ liệu huấn luyện, tiếp theo đó sẽ sử dung thuật toán SVM để học tạo ra
SVM mới, SVM này chính là S3VM có một siêu phẳng mới. Sau đó áp dụng
siêu phẳng này để phân lớp các mẫu dữ liệu mới được đưa vào.
2.2.2. Phân lớp trang Web sử dụng bán giám sát SVM
2.2.2.a. Giới thiệu bài toán phân lớp trang Web (Web
Classification)
Trang 27
Phân lớp trang Web là một trường hợp đặc biệt của phân lớp văn bản
bởi sự hiện diện của các siêu liên kết trong trang Web, cấu trúc trang Web
chặt chẽ, đầy đủ hơn, dẫn đến các tính năng hỗn hợp như là plain texts, các
thẻ hypertext, hyperlinks….
Internet với hơn 10 tỷ trang Web là một tập huấn luyện rất phong phú về
mọi chủđề trong cuộc sống, hơn nữa với số lượng chủđề trên các Website là
không nhiều thì việc sử dụng Internet như cơ sở huấn luyện rất phù hợp.
Trong các trang Web, tuy độ chính xác không phải là tuyệt đối, nhưng ta có
thể thấy mỗi chủđề gồm có nhiều từ chuyên môn với tần suất xuất hiện rất
cao, việc tận dụng tần số phụ thuộc của các từ này vào chủđề có thểđem lại
kết quả khả quan cho phân lớp.
2.2.2.b. Áp dụng S3VM vào phân lớp trang Web
Có thể thấy trang Web là siêu văn bản (hypertext) rất phổ dụng hiện nay.
Nội dung của các trang Web thường được mô tả ngắn gọn, súc tích, có các
siêu liên kết chỉđến các Web có nội dung liên quan và cho phép các trang
khác liên kết đến nó.
Nhưđã nói trên, vì được xem như là các văn bản thông thường nên trong
quá trình phân lớp trang Web việc biểu diễn văn bản sử dụng mô hình không
gian vector. Việc biểu diễn và xử lý tài liệu Web cũng giống như biểu diễn và
xử lý văn bản bằng mô hình này. Tuy nhiên trong phân lớp Web thì việc khai
thác thế mạnh của siêu liên kết trong văn bản là một vấn đềđáng quan tâm.
Với việc sử dụng các siêu liên kết giữa các trang Web từđó có thể lấy được
các thông tin về mối liên hệ giữa nội dung các trang, và dựa vào đó để nâng
cao hiệu quả phân lớp và tìm kiếm.
Để áp dụng vào phân lớp trang Web, thuật toán S3VM xem mỗi trang
Web là một vector f(d1, d2,…, dn)được biểu diễn giống như văn bản. Áp dụng
công thức (2.5) trong phương trình của siêu phẳng:
Trang 28
f(x1, x2,…, xn) = C +∑ wi xi
Thay thế mỗi văn bản tương ứng với mỗi trang Web vào phương trình siêu
phẳng này:
f(d1, d2,…,dn) = C +∑ wi di (2.6)
Với i=1,…,n.
Nếu f(d) ≥ 0 thì trang Web thuộc lớp +1.
Ngược lại nếu f(d) < 0 trang Web thuộc lớp –1.
Có thể thấy rằng quá trình áp dụng thuật toán S3VM vào bài toán phân lớp
trang Web chính là việc thay thế vector trọng số biểu diễn trang Web đó vào
phương trình siêu phẳng của S3VM, từđó tìm ra được nhãn lớp của các trang
Web chưa gán nhãn.
Như vậy, thực chất của quá trình phân lớp bán giám sát áp dụng đối với dữ
liệu là các trang Web là tập dữ liệu huấn luyện là các trang Web còn tập working
set (dữ liệu chưa gán nhãn) là những trang Web được các trang Web đã có nhãn
trong tập huấn luyện trỏ tới.
Trang 29
CHƯƠNG 3
KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ
Trong nghiên cứu này, tác giả sử dụng phần mềm nguồn mở để tiến hành
thực nghiệm phân lớp bán giám sát các tài liệu Web. Trong nội dung của
chương sẽ giới thiệu giới thiệu về phần mềm nguồn mở SVMlin do Vikas
Sindhwani công bố, trình bày quá trình khai thác phần mềm nhằm thực hiện bài
toán phân lớp và đánh giá.
3.1. Giới thiệu về phần mềm SVMlin
SVMlin là gói phần mềm dành cho SVMs tuyến tính, nó thoả mãn bài toán
phân lớp một số lớn các mẫu dữ liệu và các đặc trưng. Là chương trình phần
mềm được viết trên ngôn ngữ C++.
Ngoài tập dữ liệu đã được gán nhãn, SVMlin còn có thể tận dụng tập dữ
liệu chưa được gán nhãn trong quá trình học. Tập dữ liệu chưa được gán nhãn
này thực sử hữu ích trong việc nâng cao độ chính xác của quá trình phân lớp khi
mà số lượng dữ liệu được gán nhãn từ trước là rất ít.
Hiện tại SVMlin đã thực hiện cài đặt các thuật toán sau:
Thuật toán học có giám sát (chỉ sử dụng các dữ liệu đã gán nhãn)
Thuật toán phân lớp bình phương tối thiểu đã được chuẩn hóa tuyến
tính (Linear Regularized Least Squares Classification).
Thuật toán học bán giám sát (có thể sử dụng các dữ liệu chưa gán nhãn)
Thuật toán học tuyến tính SVM truyền dẫn sử dụng nhiều lần chuyển
đổi (Multi-switch linear Transductive L2-SVMs)
Theo Vikas Sindhwani, khi dùng SVMlin phân loại văn bản (tập dữ liệu
RCV1v2/LYRL2004) với 804414 dữ liệu gán nhãn và 47326 đặc trưng, SVMlin
mất ít hơn hai phút để huấn luyện SVM tuyến tính trong một máy Intel với tốc
độ xử lý 3GHz và 2GB RAM. Nếu chỉ cho 1000 nhãn, nó có thể sử dụng hàng
trăm ngàn dữ liệu chưa gán nhãn để huấn luyện một SVM tuyến tính bán giám
Trang 30
sát trong vòng khoảng 20 phút. Dữ liệu chưa gán nhãn rất hữu ích trong việc cải
thiện quá trình phân lớp khi số lượng nhãn lớp không quá lớn.
Download SVMlin: phiên bản mới nhất của SVMlin được tải tại trang Web:
http://www.cs.uchicago.edu/people/vikass
Cài đặt:
- Thực hiện giải nén file cài đặt bằng các lệnh sau:
unzip svmlin.zip
tar –xvzf svmlin.tar.gz
- Kết quả giải nén sẽ tạo ra thư mục svmlin-v1.0 gồm các File: Makefile,
ssl.h, ssl.cpp và svmlin.cpp.
- Gõ lệnh:
make
Sẽ tạo ra file thực thi
svmlin
Quá trình thực thi này được sử dụng để huấn luyện, kiểm tra và đánh giá quá
trình thực hiện.
3.2. Sử dụng phần mềm và kết quả đánh giá
Các file dữ liệu
Định dạng dữ liệu đầu vào cho SVMlin tương tự như định dạng của bộ
công cụ SVM-Light/LIBSVM (điểm khác biệt duy nhất là không có cột đầu tiên
mô tả nhãn của các dữ liệu)
Mỗi một dòng mô tả một mẫu dữ liệu và là danh sách các cặp gồm chỉ số
đặc trưng : giá trị đặc trưng cho các đặc trưng có giá trị khác không, được
phân cách nhau bởi một ký tự trống. Mỗi hàng được kết thúc bằng một ký tự ‘\n’.
dụ với ma trận dữ liệu với 4 dữ liệu và 5 đặc trưng như sau:
Trang 31
0 3 0 0 1
4 1 0 0 0
6 5 9 2 0
6 0 0 5 3.
Được mô tả trong file đầu vào là:
2:3 5:1
1:4 2:1
2:5 3:9 4:2
1:6 4:5 5:3
Nhãn của các dữ liệu huấn luyện được chứa trong một file riêng biệt, gọi là
file mô tả nhãn dữ liệu. Mỗi dòng của file chứa nhãn cho dữ liệu ở dòng tương
ứng trong file mô tả dữ liệu ở trên. Nhãn của dữ liệu có thể nhận các giá trị sau:
+1 (dữ liệu gán nhãn thuộc lớp dương)
-1 (dữ liệu gán nhãn thuộc lớp âm)
0 (các dữ liệu chưa được gán nhãn)
Quá trình huấn luyện
Gõ lệnh:
svmlin [options] training_examples training_labels
Trong đó:
- training_examples.weights là File chứa dữ liệu huấn luyện
- training_examples.outputs. File chứa kết quả mô hình phân lớp
Kiểm tra (testing)
Gõ lệnh: svmlin -f training_examples.weights
test_examples_filename
Trong đó:
Trang 32
training_examples.weights: File chứa kết quả mô hình phân lớp
test_examples_filename: File chứa dữ liệu kiểm tra
Đánh giá
Nếu nhãn của dữ liệu kiểm thử đã được biết trước, chúng ta sử dụng lệnh
sau để tính ma trận thực thi của quá trình phân lớp:
svmlin -f weights_filename test_examples_filename test_labels_filename
Dữ liệu dùng cho quá trình huấn luyện
Dữ liệu huấn luyện được sử dụng bao gồm 1460 tài liệu (trongđó chỉ có 50
tài liệu được gán nhãn) được lấy từ bộ dữ liệu chuẩn 20-newsgroups.
Kết quả phân lớp
Với dữ liệu huấn luyện trên đây, SVMlin đạt độ chính xác là 92.8% khi lựa
chọn chức năng multi-switch TSVM và đạt độ chính xác là 95.5% khi lựa chọn
chức năng semi-supervised SVM. Điều này khẳng định tính hiệu quả của học
bán giám sát SVM.
Trang 33
KẾT LUẬN
Kết quả của nghiên cứu đã chỉ ra được một số vấn đề về bài toán phân lớp như: phương pháp phân lớp dữ liệu, phân lớp văn bản, sự áp dụng của thuật toán học máy vào bài toán phân lớp, trong đó tập trung trình bày về phương pháp học bán giám sát – phương pháp hiệu quả và được sử dụng phổ biến. Về phân lớp dữ liệu, nghiên cứu đã đưa ra bài toán tổng quan và trình bày về phương pháp phân lớp dữ liệu tổng quát từ đó có thể giúp người đọc hiểu về bài toán phân lớp. Nghiên cứ cũng đã trình bày cơ bản về bài toán phân lớp văn bản, cách một văn bản trong bài toán phân lớp được biểu diễn, qua đó nêu lên các phương pháp phân lớp văn bản cơ bản hiện nay.
Nghiên cứu đồng thời cũng đã tìm hiểu về việc sử dụng các thuật toán học
máy trong bài toán phân lớp văn bản như: thuật toán phân lớp sử dụng quá trình
học có giám sát và học bán giám sát. Kết quả của việc tìm hiểu đã nêu lên một
số phương pháp học bán giám sát điển hình, trên cơ sở đó sẽ đi sâu tìm hiểu
thuật toán học bán giám sát SVM.
Nghiên cứu cũng đã giới thiệu một công cụ có tên là SVMlin, cách sử dụng
phần mềm và kết quả chạy phần mềm do V. Sindhwani tiến hành trong năm
2007.
Hướng nghiên cứu trong thời gian tới
Như đã trình bày ở trên, trong nghiên cứu chưa thể tìm hiểu sâu, đặc biệt là tiến
hành thực hiện phần mềm SVMlin đã khảo sát. Vì thế trong thời gian tới tôi sẽ
tìm hiểu kỹ hơn về phần mềm để có thể chủ động nắm vững việc thực hiện phần
mềm, đặc biệt là các thuật toán học bán giám sát nền tảng lý thuyết của phần
mềm.
Trang 34
TÀI LIỆU THAM KHẢO
1. Balaij Krishnapuuram, David Williams, Ya Xue,k Alex Hartemink, Lawrence Carin, Masrio A.T.Figueiredo (2005). On Semi-Supervised Classification. NIPS: 721-728, 2005.
2. Panu Erastox (2001). Support Vector Machines: Background and Practice. Academic Dissertation for the Degree of Licentiate of Philosophy. University of Helsinki, 2001.
3. T. Joachims (2003). Transductive learning via spectral graph partitioning. Proceeding of The Twentieth International Conference on Machine Learning (ICML2003): 290-297.
Trang 35
