BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------NGÔ VĂN LINH

PHÂN LOẠI VĂN BẢN SỬ DỤNG MÔ HÌNH XÁC SUẤT
TRÊN ĐA TẠP VĂN BẢN

Chun ngành : Cơng Nghệ Thơng Tin

LUẬN VĂN THẠC SĨ KHOA HỌC
CHUN NGÀNH: CƠNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC :
PGS.TS. Nguyễn Thị Kim Anh

Hà Nội – Năm 2013


Ngô Văn Linh

Phân loại văn bản

Năm 2013

LỜI CAM ĐOAN
Tôi - Ngô Văn Linh - xin cam kết Luận văn tốt nghiệp là cơng trình nghiên cứu
của bản thân tơi dưới sự hướng dẫn của PGS.TS. Nguyễn Thị Kim Anh, Viện
CNTT-TT, trường Đại học Bách khoa Hà Nội.
Các kết quả nêu trong Luận văn tốt nghiệp là trung thực, không sao chép
tồn văn của bất kỳ cơng trình nào khác

Hà Nội, ngày 2 tháng 8 năm 2013
Học viên thực hiện luận văn

Ngô Văn Linh

1


Ngô Văn Linh

Phân loại văn bản

Năm 2013

Lời cảm ơn
Đầu tiên, em xin được gửi lời cảm ơn chân thành đến các thầy giáo, cô giáo
thuộc trường đại học Bách Khoa Hà Nội. Đặc biệt là các thầy giáo, cô giáo
thuộc Viện Cơng nghệ Thơng tin và Truyền Thơng. Chính các thầy cô giáo đã
trang bị cho em những kiến thức quý báu trong thời gian em học tập và nghiên
cứu tại trường. Đồng thời em cũng xin được gửi lời cảm ơn đặc biệt đến PGS.TS
Nguyễn Kim Anh. Cô là người đã chỉ dẫn tận tình, cho em những kinh nghiệm
q báu để em có thể hồn thành luận văn tốt nghiệp này. Cô luôn động viên,
giúp đỡ em trong những thời điểm khó khăn bế tắc nhất.
Em xin gửi làm cảm ơn chân thành tới các thầy cô thuộc bộ môn Hệ thống
thông tin đã hướng dẫn, chia sẽ kinh nghiệm, thảo luận giúp cho luận văn được
hoàn thành.
Em cũng xin gửi lời cảm ơn tới các bạn Nguyễn Thế Tâm, Nguyễn Khắc Tới,
Lê Hồng Kỳ và các bạn KSTN CNTT K55, K57 đã giúp đỡ, đọc và góp ý em
trong q trình hồn thành nội dung luận văn.
Em xin gửi lời cảm ơn tới gia đình và bạn bè. Lời động viên tinh thần từ gia

đình và bạn bè ln là động lực để em tiến lên phía trước.

2


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

Tóm tắt nội dung
Phân loại các tài liệu là một trong những kĩ thuật thiết yếu đối
với vấn đề thu thập và khai phá thông tin văn bản. Trong thế giới
thực, dữ liệu chưa được gán nhãn là thực sự sẵn có nhưng việc gán
nhãn cho chúng thường là cơng việc địi hỏi mất thời gian, tốn kém.
Luận văn đề xuất hai phương pháp phân loại văn bản mới dựa trên
phương pháp học bán giám sát với mơ hình trộn của phân phối vMF
và phân phối Watson trên cấu trúc hình học các văn bản, được gọi là
LapSSvMFs và LapSSWatsons, đây là những thuật tốn xét đến cấu
trúc hình học của khơng gian tài liệu để khai thác cả dữ liệu có nhãn
và dữ liệu khơng có nhãn cho bài tốn phân loại. Đóng góp chính của
luận văn là:
1. Luận văn đề xuất phương pháp học bán giám sát với mơ hình trộn
của phân phối vMF (SSvMFs) và phân phối Watson (SSWatsons)
để khai thác cả dữ liệu có nhãn và dữ liệu khơng nhãn cho bài
toán phân loại. Luận văn đã phát triển thuật toán suy diễn biến
phân cho xác suất hậu nghiệm của các biến ẩn.
2. Luận văn đề xuất 2 phương pháp chuẩn tắc học SSvMFs và
SSWatsons với cấu trúc hình học văn bản có mã hóa thơng tin

về cấu trúc hình học trong phương pháp suy diễn Bayesian.
Thử nghiệm chỉ ra rằng các phương pháp đề xuất thu được kết quả
tốt hơn các phương pháp khác trong phân loại dữ liệu đơn và đa nhãn.

3


Ngô Văn Linh

Phân loại văn bản

Năm 2013

Abstract
Document classifications is essential to information retrieval and
text mining. In real life, unlabeled data is readily available whereas
labeled ones are often laborious, expensive and slow to obtain. This
thesis proposes two novel document classification algorithms approach
based on semi-supervised vMF mixture model and Watson mixture
model on document manifold, called Laplacian regularized Semi-Supervised vMF Mixture Model (LapSSvMFs) and Watson Mixture Model
(LapSSWatsons), which explicitly considers the manifold structure of
document space to exploit efficiently both labeled and unlabeled data
for classification. Main contributions in this thesis are as follows:
1. Thesis proposes Semi-Supervised vMF Mixture Model and Watson Mixture Model to exploit both labeled and unlabeled data
for document classification. Thesis has developed a mean-field
variational inference algorithm for the posterior distribution of
the latent variables.
2. Thesis proposes two new regularization frameworks to learn SSvMFs and SSWatsons with document manifold structure for encoding manifold information into variational Bayesian method.
The experimental results show that proposed methods outperform the
state-of-the-art methods applying to labeled and multilabeled text

classifications.

4


Ngô Văn Linh

Phân loại văn bản

Năm 2013

Mục lục
1. GIỚI THIỆU

10

1.1. Phân loại dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Mơ hình bài tốn phân loại . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1. Biểu diễn mẫu . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2. Phân loại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.3. Đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3. Tổ chức luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2. PHÂN LOẠI ĐƠN NHÃN

18

2.1. Bài toán phân loại đơn nhãn . . . . . . . . . . . . . . . . . . . . . . 18
2.2. Phân phối von Mises Fisher (vMF) . . . . . . . . . . . . . . . . . . 21
2.3. Mơ hình phân loại bán giám sát dựa trên mơ hình trộn các phân
phối vMF (SSvMFs) . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4. Mơ hình phân loại bán giám sát dựa trên mơ hình trộn các phân
phối vMFs trên đa tạp văn bản (LapSSvMFs) . . . . . . . . . . . . 27
2.5. Thử nghiệm và đánh giá . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1. Tập dữ liệu thí nghiệm (Datasets) . . . . . . . . . . . . . . 31
2.5.2. Độ đo đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.3. Các thuật toán sử dụng để so sánh (baselines) . . . . . . . 32
2.5.4. Kết quả thí nghiệm . . . . . . . . . . . . . . . . . . . . . . . 34
3. PHÂN LOẠI ĐA NHÃN

35

3.1. Bài toán phân loại đa nhãn . . . . . . . . . . . . . . . . . . . . . . 35
3.2. Phân phối Watson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3. Mơ hình phân loại bán giám sát cho dữ liệu đa nhãn sử dụng mơ
hình trộn các phân phối Watson (SSWatsons) . . . . . . . . . . . . 38

5


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

3.4. Mơ hình phân loại bán giám sát cho dữ liệu đa nhãn sử dụng mơ
hình trộn các phân phối Watson trên đa tạp văn bản (LapSSWatsons) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5. Thử nghiệm và đánh giá . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5.1. Tập dữ liệu thí nghiệm . . . . . . . . . . . . . . . . . . . . . 45
3.5.2. Độ đo đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.5.3. Các thuật toán so sánh . . . . . . . . . . . . . . . . . . . . . 48
3.5.4. Kết quả thí nghiệm . . . . . . . . . . . . . . . . . . . . . . . 49
4. KẾT LUẬN

50

A. Ước lượng tham số với SSvMFs

55

B. Ước lượng tham số với SSWatsons

62

6


Ngô Văn Linh

Phân loại văn bản

Năm 2013

Danh sách các từ viết tắt và thuật ngữ
TF-IDF

Term Frequency-Inverse Document Frequency

DF


Document Frequency

TC

Term Contribution

IG

Information Gain

LDA

Latent Dirichlet Allocation

PLSI

Probabilistic Latent Semantic Indexing

FSTM

Fully Sparse Topic Model

VB

Variational Bayesian

vMF

von Mises Fisher Distribution


LP

Label Propagation

SVM

Support Vector Machine

Labeled LDA

Labeled Latent Dirichlet Allocation

SSvMFs

Semi-Supervised Mixture Model of vMF Distributions

SSWatson

Semi-Supervised Mixture Model of Watson Distributions

LapSSvMFs

SSvMFs on Document Manifold

LapSSWatsons SSWatsons on Document Manifold

7


Ngơ Văn Linh


Phân loại văn bản

Năm 2013

Danh sách hình vẽ
1.

Các bước của bài toán phân loại . . . . . . . . . . . . . . . . . . . 12

2.

Mơ hình đồ thị cho SSvMFs . . . . . . . . . . . . . . . . . . . . . . 23

3.

Kết quả thử nghiệm trên các tập dữ liệu classic, NG17-19, la1
and k1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.

Mơ hình đồ thị cho SSWatsons . . . . . . . . . . . . . . . . . . . . 39

5.

Kết quả phân loại đa nhãn với các phương pháp LapSSWatsons,
SSWatsons, LapSSvMFs, SSvMFs và LP trên 4 datasets: Recreation, Education, Health and Arts. . . . . . . . . . . . . . . . . . . 47

6.


Hiệu năng phân loại đa nhãn khi thay đổi số lượng chủ đề . . . . 49

8


Ngô Văn Linh

Phân loại văn bản

Năm 2013

Danh sách bảng
1.

Sơ lược về các tập dữ liệu (với mỗi tập dữ liệu: nd là tổng số lượng
văn bản, nw là tổng số lượng từ, k tổng số lớp, nc là trung bình
số lượng tài liệu trên một lớp, và độ cân bằng) . . . . . . . . . . . 32

2.

Thống kê các tập dữ liệu yahoo: m, d, và N định nghĩa là số
lượng nhãn, số lượng chiều (từ điển), tổng số lượng tài liệu trong
tập dữ liệu sau khi tiền xử lý và “MaxNPI”/“MinNPI” định nghĩa
là số lượng maximum/minimum các văn bản thuộc các nhãn lớp
(positive instances for each label) . . . . . . . . . . . . . . . . . . . 45

3.

Bảng tổng hợp hiệu năng của LapSSWatsons, Labeled-LDA và
SVM sử dụng độ đo Micro-F1 và Macro-F1 trong 8 datasets . . . 46


9


Ngô Văn Linh

Phân loại văn bản

Năm 2013

1. GIỚI THIỆU
1.1. Phân loại dữ liệu
Một số khái niệm cơ bản
• Mẫu (pattern): xn là một dữ liệu thuộc tập có N dữ liệu được sử dụng cho

thuật toán phân loại. Mẫu thường được biểu diễn dưới dạng một vector
d chiều xn = (xn,1 , xn,2 , .., xn,d ). Cách biểu diễn này được gọi là biểu diễn

vector dựa trên các mô hình lựa chọn đặc trưng và xác định trọng số. Cụ
thể hơn trong bài tốn phân loại văn bản thì mẫu ở đây chính là các văn
bản.
• Mỗi thành phần xn,i được gọi là một đặc trưng (feature) hay thuộc tính

(attribute) của xn .
• d là số chiều của khơng gian biểu diễn mẫu.
• Tập mẫu có nhãn (labeled data) XN = {x1 , x2 , . . . , xN }, (với N là kích thước

tập mẫu) là tập dữ liệu có thơng tin về nhãn.
• Tập mẫu có không nhãn (unlabeled data) XM = {x1 , x2 , . . . , xM }, (với M


là kích thước tập mẫu) là tập dữ liệu khơng có nhãn.
• Tập nhãn (label set) L = {l1 , l2 , . . . , lK } hoặc đơn giản hơn là L = {1, 2, ..., K}:

là các nhãn sẽ được gán cho các mẫu để xác định các lớp mà mẫu thuộc
vào, với K là số nhãn.

Học có giám sát (supervised-learning) và bài tốn phân loại
(classification)
Bài tốn học có giám sát được phát biểu như sau: Cho tập dữ liệu (dataset) bao
gồm: tập các mẫu được gắn kèm với một nhãn lớp/giá trị đầu ra mong muốn

10


Ngô Văn Linh

Phân loại văn bản

Năm 2013

(labeled data) và tập các mẫu khơng có thơng tin về nhãn lớp/giá trị đầu ra
mong muốn (unlabeled data). Mục đích của bài tốn học có giám sát là học
được bộ gán nhãn (vd: một phân lớp, một hàm mục tiêu ) phù hợp tập dữ liệu
có nhãn (labeled data) và gán nhãn cho dữ liệu chưa có nhãn (unlabeled data).
Trong bài tốn học có giám sát, nhãn lớp ở đây có thể là giá trị liên tục
(continous-value) hoặc giá trị rời rạc (discrete-value). Bài tốn học một hàm
mục tiêu có giá trị liên tục được gọi là bài toán hồi quy (regression), bài toán
học hàm mục tiêu rời rạc được gọi là bài toán phân loại (classification). Luận
văn tập trung vào bài toán học hàm phân loại.


Học không giám sát (unsupervised-learning) và bài tốn phân
cụm (clustering)
Bài tốn học khơng giám sát là bài tốn tìm trong tập dữ liệu (khơng có thơng
tin nhãn) những đặc điểm như: nhóm, cấu trúc, mối quan hệ giữa các dữ liệu.
Trong đó, bài tốn phân cụm là một bài tốn phổ biến của học khơng giám sát.
u cầu được đặt ra là tìm cách phân cụm tập dữ liệu mà mỗi dữ liệu thuộc
trong nhóm (cụm) thường giống nhau (có quan hệ với nhau) và khác với dữ liệu
thuộc nhóm khác.

Học bán giám sát (semi-supervised learning)
Khi tập dữ liệu có nhãn ít và khó thu thập, mà học có giám sát chỉ học ra bộ
phân loại trên tập có nhãn, tập dữ liệu có nhãn khơng đủ đặc trưng cho mỗi
nhãn, nên kết quả phân loại thường khơng thu được kết quả cao. Khi đó, phương
pháp học bán giám sát là phương pháp khai thác cả dữ liệu có nhãn và dữ liệu
khơng nhãn thường được sử dụng thay thế, thu được kết quả tốt trên tập dữ
liệu có nhãn ít.

11


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

Hình 1: Các bước của bài tốn phân loại

1.2. Mơ hình bài tốn phân loại
Bài tốn phân loại dữ liệu thường có các bước như sau:

1. Biểu diễn mẫu (pattern representation), có thể bao gồm cả lựa chọn đặc
trưng (feature selection).
2. Phân loại
3. Đánh giá kết quả đầu ra.
Hình 1 mơ tả mơ các bước của bài toán phân loại dữ liệu.
1.2.1. Biểu diễn mẫu
Biểu diễn mẫu: là biểu diễn tập các mẫu theo tập các đặc trưng quan trọng của
mẫu để phục vụ cho mục đích tăng hiệu quả tính tốn và độ chính xác. Lựa
chọn đặc trưng (feature selection) là q trình tìm tập đặc trưng biểu diễn tốt
nhất từ tập đặc trưng ban đầu để biểu diễn mẫu cho quá trình phân loại. Sau

12


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

đó trên mỗi mẫu, các đặc trưng được tính các trọng số tương ứng dựa trên các
mơ hình. Ví dụ với văn bản có 2 cách xác định trọng số thường gặp là dựa trên
túi từ (dựa trên tần suất xuất hiện của từ) hoặc tf-idf.
Phương pháp lựa chọn đặc trưng không giám sát
Tần suất tài liệu
Tần suất tài liệu DF [13] của một từ t được đo bằng tỉ số giữa số tài liệu chứa
từ t đó trên tổng số tài liệu trong cơ sở dữ liệu.
DF (t) càng lớn thì đặc trưng t có chất lượng càng tốt. Đây là phương pháp

lựa chọn đặc trưng đơn giản nhất và có độ phức tạp tính tốn thấp, tuyến tính

với kích thước cơ sở dữ liệu. Tuy nhiên phương pháp này có điểm yếu là có xu
hướng giữ lại những từ xuất hiện nhiều trong các văn bản. Trong đó những từ
như stopword và những từ dùng để liên kết câu là những từ không mang thông
tin mà xuất hiện gần như trong hầu hết các tài liệu. Do đó phương pháp này
chỉ hiệu quả khi ta loại bỏ hết stopword và sử dụng một ngưỡng tần số để loại
bỏ những từ xuất hiện quá nhiều trong các văn bản.
Mức độ đóng góp của từ
Mức độ đóng góp của từ T C [13] được tính dựa trên trọng số của từ trong tài
liệu. Phương pháp DF giả sử rằng mỗi từ có vai trị như nhau trong cùng một
tài liệu, và DF có xu hướng giữ lại các từ có tần suất cao nhưng có phân phối
đều giữa các lớp. T C đề xuất để giải quyết vấn đề này.
Kết quả của phân cụm phụ thuộc nhiều vào độ đo tương tự giữa các tài liệu.
T C đo mức độ quan trọng của từ dựa vào độ đóng góp của nó trong độ tương

tự giữa hai tài liệu. Đóng góp của từ vào độ tương tự của các tài liệu trong cơ
sở dữ liệu được tính như sau:
w(t, di ) ∗ w(t, dj )

T C(t) =
i,j,i#j

T C(t) càng lớn thì đặc trưng càng tốt.

13

(1)


Ngô Văn Linh


Phân loại văn bản

Năm 2013

Dựa trên xác suất các từ thuộc chủ đề
Ý tưởng của mơ hình hóa chủ đề là tạo ra một mơ hình sinh xác suất (probabilistic generative model) như PLSI [10], LDA [5], FSTM [20] cho các tài liệu
trong tập dữ liệu. Các giả định của các phương pháp mơ hình hóa chủ đề như
sau:
Tập N tài liệu giả định có một xác suất thuộc vào K chủ đề, do đó một tài
liệu có thể có một xác suất thuộc nhiều chủ đề. Điều đó cho biết một tài liệu
có thể chứa trong nó nhiều chủ đề khác nhau. Một chủ đề về cơ bản được coi là
một cụm hoặc một tập các từ có liên quan nhau và giá trị P (Tj |di ) là xác suất
để tài liệu di thuộc vào chủ đề j . Trong phương pháp thông thường, hàm thuộc
của một tài liệu vào một cụm là 0 (không thuộc) hoặc 1(thuộc). Phương pháp
xác suất cho ta một cái nhìn thực tế hơn, đó là một tài liệu có thể thuộc nhiều
cụm ứng với một xác suất biểu thị độ thuộc của nó. Giá trị của P (Tj |di ) được
ước lượng sử dụng phương pháp mơ hình hóa chủ đề.
Mỗi chủ đề có một vector xác suất, xác định xác suất của các từ biểu diễn
chủ đề đó. Đối với một tài liệu thuộc chủ đề Tj xác suất từ tl thuộc vào chủ đề
đó là P (tl |Tj ). Giá trị P (tl |Tj ) là một tham số cần ước lượng trong phương pháp
mơ hình hóa chủ đề và dựa trên tham số này từ sẽ được lựa chọn.
Các mơ hình PLSI, LDA, FSTM chỉ ra các phương pháp khác nhau để học
các xác suất này.
Phương pháp lựa chọn đặc trưng có giám sát
Sự có mặt của thông tin nhãn là rất quan trọng, các phương pháp lựa chọn
đặc trưng có giám sát khai thác thơng tin về nhãn sẽ hiệu quả hơn nhiều các
phương pháp không giám sát. Ở đây luận văn giới thiệu 2 phương pháp lựa chọn
đặc trưng có giám sát đó là chỉ số Gini và phương pháp dựa trên mơ hình sinh.
Gini
Chỉ số Gini [19] đo mức độ phân bố không đồng nhất của một đặc trưng đối

với các lớp. Gọi ni (t) là số tài liệu trong lớp li chứa từ t. Gọi pi (t) là tỉ lệ số tài

14


Ngô Văn Linh

Phân loại văn bản

Năm 2013

liệu chứa từ t trong lớp li trên tổng số tài liệu chứa từ t trong tồn bộ tập dữ
liệu. Ta có
pi (t) =

ni (t)
j nj (t)

(2)

(pi (t))2

(3)

Hệ số Gini của từ t được tính như sau:
G(t) =
i

Khoảng giá trị của hệ số Gini là (0,1] và nếu từ t chỉ xuất hiện trong một lớp
li nào đó thì giá trị hệ số Gini của nó bằng 1. Hệ số gini càng nhỏ khi nó phân


phối càng đều trong các lớp, và những từ phân phối đều như vậy sẽ khơng có ý
nghĩa khi phân tích dữ liệu.
Các phương pháp giảm chiều dựa trên mơ hình sinh
Trong [21] đưa ra phương pháp giảm chiều giống như PLSI, LDA, FSTM
nhưng sử dụng thêm thông tin nhãn và cho kết quả là đáng kể. Tư tưởng của
[21] là khai thác thông tin chủ đề nổi bật từ tập dữ liệu có nhãn để làm mạnh
chủ đề đó lên trong q trình học với tồn bộ dữ liệu. Đồng thời, [21] khai thác
thơng tin về hình học liên hệ giữa các điểm dữ liệu, từ đó kết quả thu được tốt
hơn các phương pháp gốc.
1.2.2. Phân loại
Phân loại: là q trình gán nhãn dữ liệu chưa có nhãn. Q trình phân loại có
thể được tiến hành theo nhiều cách và có thể chia thành các dạng: gán đơn nhãn
và gán đa nhãn.
Một số lượng lớn các thuật toán phân loại cho văn bản được đưa ra, nhưng có
thể xếp vào trong 2 mục chính: phân loại phân tách (discriminative approaches)
và dựa trên mơ hình sinh (generative approaches) [23]. Khơng có phương pháp
nào là làm việc tốt với mọi tập dữ liệu, điều đó có nghĩa là hiệu năng của thuật
toán phụ thuộc vào tập dữ liệu. Tuy nhiên, phương pháp tiếp cận dựa trên mô

15


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

hình sinh thường đưa ra những hiểu biết chi tiết hơn. Ví dụ mơ hình sinh có thể

đưa ra được xác suất mỗi tài liệu thuộc vào các nhãn, hoặc có thể mơ tả được
đặc trưng của từng nhãn. Dưới đây là một số thuật toán phân loại thường được
sử dụng cho phân loại văn bản.
Trong phân loại văn bản, thuật toán phân loại có giám sát SVM [22] là một
trong những thuật tốn tốt nhất cho văn bản. Thuật toán SVM phù hợp với
những mơ hình dữ liệu có số chiều cao và có nhiễu. Ban đầu thuật tốn SVM
chỉ sử dụng cho phân loại đơn nhãn, sau đó được cải tiến sử dụng cho phân loại
đa nhãn [17].
Thuật toán lan truyền nhãn [12] là một thuật toán bán giám sát, tư tưởng của
thuật toán lan truyền nhãn là giả thiết rằng dữ liệu có nhãn và dữ liệu khơng
nhãn được liên kết trên một đồ thị (một cấu trúc hình học), trong đó mỗi cạnh
biểu diễn như là độ tương đồng giữa các dữ liệu. Với giả thiết các điểm dữ liệu
có trọng số của cạnh càng lớn (hay càng tương đồng) thì xác suất gán nhãn
cho chúng càng giống nhau. Khi đó thơng tin nhãn từ các điểm có nhãn sẽ lan
truyền theo cạnh sang điểm chưa có nhãn. Sau nhiều lần lặp thì nhãn sẽ lan
truyền đến tất cả các điểm, đồng thời xác suất gán nhãn sẽ hội tụ.
Khi sử dụng các thuật tốn phân loại, có thể thuật tốn đó u cầu phải khởi
tạo các tham số truyền vào, ví dụ như số lượng chủ đề, số lượng cụm,... Tham
số này tùy người dùng thay đổi. Tuy nhiên, để chọn được bộ tham số tốt, người
ta thường điều chỉnh tham số sao cho tối ưu trên tập kiểm thử (validation set).
1.2.3. Đánh giá
Đánh giá kết quả đầu ra: Kết quả đầu ra của một thuật toán phân loại thường
được đánh giá bằng độ đo chính xác (accuracy).

1.3. Tổ chức luận văn
Luận văn được tổ chức thành 4 phần:

16



Ngơ Văn Linh

Phân loại văn bản

• Phần 1: Giới thiệu
• Phần 2: Phân loại đơn nhãn
• Phần 3: Phân loại đa nhãn
• Phần 4: Kết luận

17

Năm 2013


Ngô Văn Linh

Phân loại văn bản

Năm 2013

2. PHÂN LOẠI ĐƠN NHÃN
2.1. Bài toán phân loại đơn nhãn
Với sự phát triển nhanh chóng của Internet, tài liệu dạng văn bản (news document) trở nên phong phú và xuất hiện ở khắp nơi. Phân loại văn bản tự động là
chức năng quan trọng trong khai phá dữ liệu văn bản và đang được quan tâm
nhiều hơn trong ngày nay.
Thực tế, bài toán phân loại văn bản và trong rất nhiều bài toán ứng dụng của
học máy, khai phá dữ liệu khác, dữ liệu chưa được gán nhãn (unlabeled data)
nhiều và sẵn có. Trong khi, việc gán nhãn thường nhọc nhằn, tốn kém và nhàm
chán. Điều đó là bởi vì gán nhãn dữ liệu thường yêu cầu sự cố gắng và độ chính
xác cao của chuyên gia. Trong hoàn cảnh này, phương pháp học bán giám sát

(semi-supervised learning) trở nên hiệu quả bằng cách sử dụng cả dữ liệu có
nhãn và dữ liệu không nhãn để xây dựng bộ phân loại tốt hơn.
Khi biểu diễn văn bản bằng mơ hình túi từ (bag-of-words model) hoặc mơ
hình tf-idf, tài liệu được biểu diễn dưới dạng vector có số chiều cao nhưng thưa.
Đó là lý do vì sao phân cụm dựa trên mơ hình trộn các phân phối vMF và phân
phối Watson (các phân phối trên dữ liệu có hướng) có hiệu năng tốt hơn các mơ
hình dựa trên các phân phối đa thức (multinomial distribution) và phân phối
Bernoulli ( Multivariate Bernoulli model) [2, 23, 3]. Lý do mà phân phối trên
dữ liệu có hướng cho kết quả tốt hơn là: thứ nhất, mơ hình sử dụng phân phối
vMF và phân phối Watson có thể đương đầu trực tiếp với bài tốn có dữ liệu
vector với số chiều cao và thưa. Thứ hai, phân phối vMF tương tự như sử dụng
độ đo tương đồng cosin mà phù hợp với dữ liệu văn bản số chiều cao, còn phân
phối chuẩn (Gaussian distribution)[24] dựa trên độ đo khoảng cách euclit.
Các phương pháp học máy dựa trên xác suất và thống kê đã được nghiên cứu
từ rất lâu. Tuy nhiên, trong khoảng thập niên gần đây các mô hình học thống kê
mới nhận được sự quan tâm mạnh mẽ của nhiều nhà khoa học và có những bước

18


Ngô Văn Linh

Phân loại văn bản

Năm 2013

tiến đáng kể. Trước đây, mơ hình trộn (mixture models) đã được nghiên cứu và
áp dụng cho phân tích chỉ trên dữ liệu khơng có nhãn (unsupervised-learning).
Gần đây, các mơ hình học cho bài tốn phân loại sử dụng cả dữ liệu có nhãn và
khơng nhãn (semi-supervised-learning) dựa trên mơ hình trộn đã có nhiều kết

quả. Mơ hình trộn với phân phối đa thức (multinomial mixtures) được chứng
minh tốt từ kết quả thử nghiệm của [16] so với phương pháp Naive Bayes. [16]
đã kết hợp phương pháp phân loại Naive Bayes và mơ hình trộn các phân phối
đa thức để khai thác cả thông tin của dữ liệu có nhãn và dữ liệu khơng nhãn.
Trong đó, văn bản được biểu diễn dưới dạng túi từ, xác suất sinh ra các từ dựa
trên phân phối đa thức. Tư tưởng của phương pháp dựa trên tập có nhãn để
tính xác suất sinh ra các nhãn và xác suất mỗi từ trong từ điển thuộc các nhãn,
sau đó sử dụng tập giá trị đó như giá trị khởi tạo cho mơ hình trộn để học cho
dữ liệu khơng có nhãn. Từ đó thơng tin về xác suất sinh ra từ và tỉ lệ nhãn được
điều chỉnh. Tuy nhiên, Cozmain [8] chỉ ra rằng trong phương pháp học bán giám
sát sử dụng mơ hình trộn (semi-supervised learning of mixture models) dữ liệu
khơng nhãn có thể làm cho khơng thích hợp với mơ hình trộn, dẫn đến khả năng
dữ liệu khơng có nhãn làm giảm độ chính xác của phân loại, trong khi tăng dữ
liệu có nhãn có thể cải thiện bộ phân loại. Xa hơn, việc chọn mô hình trộn với
các phân phối thích hợp có thể ảnh hưởng đến hiệu năng của thuật toán phân
loại. Trong các ứng dụng của thu thập và khai phá thông tin đã chỉ ra rằng khi
biểu diễn văn bản dưới dạng vector if-idf và sử dụng độ đo tương đồng cosin sẽ
đem lại hiệu quả cao trong các bài toán phân loại và phâm cụm [2].
Một phương pháp học máy bán giám sát khơng sử dụng mơ hình trộn cũng
thu được hiệu quả cao và đang được tham chiếu đến như một trong những
phương pháp tốt nhất trong phân loại, đó là phương pháp lan truyền nhãn
(Label Propagation method) [1]. Tuy nhiên, trong thuật tốn lan truyền nhãn
q trình xây dựng đồ thị sẽ phụ thuộc vào cách biểu diễn dữ liệu, vào khơng
gian thuộc tính. Do đó việc lựa chọn thuộc tính trở thành bài tốn quan trọng

19


Ngô Văn Linh


Phân loại văn bản

Năm 2013

trong phương pháp lan truyền nhãn. Hơn nữa, khi sử dụng thuật toán lan truyền
nhãn kích thước tập có nhãn cũng ảnh hưởng đến việc lựa chọn đặc trưng, khi
tập dữ liệu có nhãn nhỏ thì kết quả độ chính xác cũng khơng thực sự cao, nhưng
tăng đáng kể khi tăng kích thước tập có nhãn. Cuối cùng một vấn đề gặp phải
với thuật tốn lan truyền nhãn đó là khi có một dữ liệu mới xuất hiện, thuật
tốn muốn phân loại thì phải học lại từ đầu. Nguyên nhân là do thuật toán phải
xây dựng đồ thị và áp dụng lan truyền nhãn theo các cạnh.
Gần đây, trong các cách tiếp cận sử dụng mơ hình trộn, các tác giả giả
thiết thêm rằng các điểm dữ liệu phân bố trên một cấu trúc hình học đa tạp
(manifold). Khi đó các tác giả kết hợp dữ liệu được sinh ra từ các mơ hình trộn
và thêm những xác suất tiên nghiệm về dữ liệu (prior) dựa trên học những cấu
trúc hình học của dữ liệu. Đó có thể xem là cách các tác giả khai thác điểm mạnh
của phương pháp lan truyền nhãn vào mơ hình phân cụm. Tác giả Cai đã đưa
ra những phương pháp phân cụm mới gọi là LapPLSI (Laplacian Probabilistic
Latent Semantic Indexing) [6] và LTM ( Locally-consistent Topic Model) [6, 7]
khai thác những tính chất này. LapPLSI và LTM khác nhau chỉ ở chỗ cách xây
dựng cấu trúc hình học khác nhau, LapPLSI sử dụng độ đo cosin để xây dựng
đồ thị, còn LTM sử dụng độ đo KL (KL-divergence) để xây dựng đồ thị. Thí
nghiệm cho thấy LapPLSI và LTM thu được những kết quả tốt hơn các phương
pháp xác định chủ đề ẩn trước đây như PLSA [10] and LDA [5], đồng thời áp
dụng vào bài toán phân cụm cho kết quả cao. Tuy nhiên, hai mơ hình này xuất
phát từ mơ hình PLSI, nên có những nhược điểm giống như PLSI đó là số lượng
tham số của mơ hình q nhiều dẫn đến khả năng dễ bị overfitting [6]. Xa hơn,
những mơ hình này sử dụng phân phối đa thức để sinh dữ liệu, hay sử dụng mơ
hình túi từ để biểu diễn tài liệu mà khơng sử dụng mơ hình tf-idf.
Đến đây, luận văn đề xuất một phương pháp phân loại mới, được đặt tên

là LapSSvMFs (Laplacian regularized Semi-Supervised vMF Mixture Model),
mà phương pháp khai thác cả dữ liệu có nhãn và dữ liệu khơng nhãn (semi-

20


Ngô Văn Linh

Phân loại văn bản

Năm 2013

supervised learning) sử dụng mơ hình trộn và cấu trúc hình học. Phương pháp
LapSSvMFs sẽ khắc phục cả nhược điểm của phương pháp học bán giám sát
dựa trên mơ hình trộn và phương pháp lan truyền nhãn. Chính vì thế, kết quả
thử nghiệm chỉ ra, khi so với phương pháp sử dụng mơ hình trộn thì thuật tốn
LapSSvMFs ổn định và kết quả tốt hơn. Đồng thời so với lan truyền nhãn trên
tập dữ liệu kích thước nhỏ thì kết quả của LapSSvMFs lớn hơn là đáng kể, mặt
khác với dữ liệu mới đến thuật tốn LapSSvMFs có thể phân loại được mà khơng
cần học lại từ đầu.

2.2. Phân phối von Mises Fisher (vMF)
Phân phối vMF phù hợp với việc biểu diễn dữ liệu có số chiều cao và thưa. Trong
thống kê có hướng (directional statistics), phân phối vMF là một phân phối trên
hình cầu (d − 1) chiều trong không gian Rd [2]. Một vector ngẫu nhiên d chiều
x ( x ∈ Rd và x = 1, tương đương x ∈ Sd−1 (hình cầu d − 1 chiều)) được nói là

sinh ra từ phân phối von Mises-Fisher (vMF) nếu nó có hàm mật độ phân phối
(probability density function): f (x|µ, κ) = Cd (κ) exp(κµT x), với µ = 1, κ ≥ 0 và
d ≥ 2. Hằng số chuẩn tắc Cd (κ) được đưa ra theo công thức:

d

Cd (κ) =

κ 2 −1
d

(4)

(2π) 2 I d −1 (κ)
2

trong đó Ir (·) là hàm Bessel (the modified Bessel function) [15]. Hàm mật độ
phân phối f (x|µ, κ) có tham số trung bình hướng (the mean direction) µ, và tham
số độ tập trung (the concentration parameter) κ. κ được gọi là độ tập trung vì
các mẫu dữ liệu được sinh ra gần với vector trung bình hướng µ phụ thuộc vào
κ. Nếu κ ∈ R thì mẫu các tập trung quanh trung bình hướng. Đặc biệt, khi
κ = 0, f (x|µ, κ) suy biến về phân phối đều (uniform density) trên cầu S d−1 , và

khi κ → ∞, f (x|µ, κ) tiến đến một điểm trung bình hướng trên cầu. Phân phối

21


Ngơ Văn Linh

Phân loại văn bản

Năm 2013


vMF của x có kỳ vọng (expectation) là E(x) = ρµ, với:

ρ = Ad (κ) =

(d−3)
1 2 κt
t e (1 − t2 ) 2 dt
−1
(d−3)
1 κt
e (1 − t2 ) 2 dt
−1

I d (κ)
=

2

I d −1 (κ)

(5)

2

2.3. Mơ hình phân loại bán giám sát dựa trên mơ hình trộn
các phân phối vMF (SSvMFs)
Trong phần này, luận văn đưa ra mơ hình SSvMFs với mục đích khai thác cả
dữ liệu có nhãn XN và dữ liệu khơng nhãn XM . SSvMFs là mơ hình đồ thị xác
suất mơ tả q trình sinh cả dữ liệu có nhãn và dữ liệu khơng nhãn dựa trên các
phân phối vMF. Trong đó văn bản được biểu diễn theo mơ hình tf-idf (d chiều)

và được chuẩn tắc thuộc hình cầu Sd−1 . Tư tưởng của mơ hình SSvMFs ban
đầu giống như mơ hình trộn các phân phối vMF trong các mơ hình học khơng
giám sát (unsupervised learning). Đó là dữ liệu được sinh ra thuộc vào K cụm
và mỗi cụm được đặc trưng bởi một phân phối vMF với các tham số khác nhau.
Tuy nhiên trong mơ hình học phân loại (một mơ hình có giám sát (supervised
learning)), thơng tin K cụm được biết trước, là số lượng nhãn trong tập nhãn,
cịn trong phân cụm thơng tin về số lượng cụm là tham số của mơ hình. Đặc
biệt trong bài toán phân loại, dữ liệu trong tập học (trainning set) đã có nhãn.
Cụ thể, mỗi văn bản có một nhãn. Vì vậy, dữ liệu có nhãn sẽ chỉ được sinh ra
từ một phân phối vMF đặc trưng cho nhãn đó, hay xác suất để dữ liệu có nhãn
thuộc các nhãn khác là bằng 0.
Đặt zm là biến ẩn chứa thông tin về nhãn mà được gán cho xm . Trong mơ
hình SSvMFs, zm của dữ liệu khơng nhãn được sinh ra theo phân phối đa thức
(multinomial distributions): zm ∼ M utl(π). Trái lại, zn của xn chính là nhãn của
nó. Phân phối có điều kiện sinh ra x khi biết nhãn z và các đặc trưng về trung
bình hướng µ = {µ1 , .., µK } và tham số độ tập trung κ = {κ1 , .., κK } của các nhãn
là p(x|z, µ, κ) = vM F (x|µz , κz ). Nghĩa là, khi biết dữ liệu có nhãn z thì phân phối

22


Ngơ Văn Linh

Phân loại văn bản

Năm 2013

Hình 2: Mơ hình đồ thị cho SSvMFs
vMF có các tham số (µz , κz ) được lựa chọn để sinh ra dữ liệu. Với trung bình
hướng µk , Mardia and El-Atoum [14] đã xác định được rằng phân phối vMF

liên hợp (conjugate prior) cho vector trung bình hướng. Vì thế, phân phối vMF
p(µk |µ0 , κ0 ) = vM F (µk |µ0 , κ0 ), với µ0 , κ0 là tham số, được lựa chọn để sinh µk .

Mơ hình sinh được minh họa đầy đủ (Hình 2):
1. Với mỗi nhãn k ∈ {1, . . . , K}
a) Sinh đặc trưng mỗi nhãn: µk |µ0 , κ0 ∼ vM F (µk |µ0 , κ0 )
2. Với mỗi văn bản có nhãn xn ∈ XN
a) Sinh dữ liệu: xn |zn , µ, κ ∼ vM F (xn |µzn , κzn )
3. Với mỗi văn bản chưa có nhãn xm ∈ XM
a) Sinh nhãn: zm ∼ M ult(π)
b) Sinh dữ liệu: xm |zm , µ, κ ∼ vM F (xm |µzm , κzm )
Tuy nhiên, để đi ước lượng tham số và suy diễn ra thơng tin biến ẩn là bài tốn
phức tạp. Hiện tại, các phương pháp xấp xỉ được xem là giải pháp hữu hiệu để
giải quyết các bài toán này như: phương pháp lấy mẫu (Gibbs sampling), phương
pháp suy diễn biến phân (variational inference). Phương pháp lấy mẫu là một
phương pháp cho kết quả độ chính xác cao, tuy nhiên vấn đề với phương pháp
lấy mẫu là số lần lặp lấy mẫu lớn và khó biết thời điểm hội tụ. Phương pháp suy

23


Ngô Văn Linh

Phân loại văn bản

Năm 2013

diễn biến phân là phương pháp được sử dụng rộng rãi hiện nay, phương pháp
đảm bảo nhanh hội tụ và kết quả tốt. Chính vì thế, luận văn lựa chọn phương
pháp suy diễn biến phân để giải quyết vấn đề tối ưu hàm log likehood.

Bài toán đưa ra yêu cầu là xác định nhãn cho mỗi tài liệu khơng có nhãn.
Phương pháp MLE (maxinmum log likehood estimation) là một phương pháp
hay được sử dụng trong các mơ hình học máy dựa trên xác suất thống kê. Tư
tưởng của phương pháp MLE là những tham số của mơ hình được ước lượng
sao cho ứng với các giá trị tham số đó thì xác suất sinh ra dữ liệu là lớn nhất.
Log likelihood của những dữ liệu được quan sát trong mơ hình là:
log p(XN , ZN , XM |π, κ1 , .., κK , µ0 , κ0 )

(6)

Theo MLE, phải ước lượng các tham số π, κ1 , .., κK , µ0 , κ0 để log likehood là lớn
nhất. Phân tích biểu thức tối ưu:
log p(XN , ZN , XM |π, κ, µ0 , κ0 )
= log

p(XN , ZN , XM , ZM , µ|π, κ, µ0 , κ0 )dµ
ZM

µ

= log
ZM

≥

µ

p(XN , ZN , XM , ZM , µ|π, κ, µ0 , κ0 )
q(ZM , µ)dµ
q(ZM , µ)


q(ZM , µ) log
ZM

µ

p(XN , ZN , XM , ZM , µ|π, κ, µ0 , κ0 )
dµ
q(ZM , µ)

= Eq(ZM ,µ) [log p(XN , ZN , XM , ZM , µ|π, κ, µ0 , κ0 )]
− Eq(ZM ,µ) [log q(ZM , µ)] = L

(7)

với ZN = {z1 , ..., zN } và ZM = {z1 , ..., zM }. Bài tốn xấp xỉ được đưa ra đó là thay
vì tối ưu trên hàm log likehood phức tạp, biểu thức cận dưới (lower bound) L
được thay thế.

24