.
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐỖ THỊ NƯƠNG

CÁC PHƯƠNG PHÁP XÁC ĐỊNH MỐI QUAN HỆ ĐA NHÃN
VÀ ỨNG DỤNG TRONG PHÂN LỚP ĐA NHÃN TIẾNG VIỆT

LUẬN VĂN THẠC SỸ

HÀ NỘI - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐỖ THỊ NƯƠNG

CÁC PHƯƠNG PHÁP XÁC ĐỊNH MỐI QUAN HỆ ĐA NHÃN
VÀ ỨNG DỤNG TRONG PHÂN LỚP ĐA NHÃN TIẾNG VIỆT

Ngành: Công Nghệ Thông Tin
Chuyên ngành: Hệ Thống Thông Tin
Mã số: 60480104

LUẬN VĂN THẠC SỸ

CÁN BỘ HƯỚNG DẪN: TS. Nguyễn Cẩm Tú

HÀ NỘI - 2015

một các rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Trong luận văn, không
có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài
liệu tham khảo.
Hà Nội, ngày 07 tháng 07 năm 2015
Tác giả

Đỗ Thị Nương

ii


MỤC LỤC
MỞ ĐẦU

...................................................................................................................... 1

Chương 1.
các nhãn

Giới thiệu chung bài toán phân lớp đa nhãn và mối quan hệ giữa
...................................................................................................................... 3

1.1

Đa nhãn – phân lớp đa nhãn...............................................................................3

1.1.1

Đa nhãn – phân lớp đa nhãn ........................................................................3


2.2.1

Giới thiệu về công cụ word2vec ............................................................... 10

2.2.2

Một số kỹ thuật sử dụng trong Word2Vec ................................................11

2.2.3

Sử dụng word2vec để đo độ gần nhau giữa các từ....................................13

2.3

Các phương pháp phân lớp đa nhãn sử dụng độ gần nhau giữa các nhãn .......14

2.3.1

Binary Relevance (BR) .............................................................................14

2.3.2

Classifier Chain (CC) ................................................................................15

2.3.3

Calibrated Label Ranking (CLR) .............................................................. 18

2.3.4


Pha 1. Huấn luyện mô hình ..............................................................................30

3.3.1

Quá trình tiền xử lý văn bản [3] ................................................................ 30
iii


3.3.2

Biểu diễn văn bản trong mô hình vector [3] .............................................30

3.3.3

Học máy đa nhãn ....................................................................................... 32

3.3.4

Học máy đa nhãn và tích hợp độ gần nhau giữa các nhãn ........................ 32

3.4

Pha 2. Phân lớp sử dụng mô hình ....................................................................33

3.5

Kết luận chương 3 ............................................................................................ 34

Chương 4.


4.4

Thực nghiệm ....................................................................................................40

4.5

Kết quả thực nghiệm ........................................................................................ 41

Kết luận

.................................................................................................................... 43

Tài liệu tham khảo ............................................................................................................ 44

iv


DANH SÁCH HÌNH VẼ
Hình 1.1: Ví dụ dữ liệu đa nhãn ...................................................................................... 3
Hình 1.2: Học đơn nhãn ..................................................................................................4
Hình 1.3: Học đa nhãn đơn thể hiện ................................................................................4
Hình 1.4: Mô hình phân lớp ............................................................................................ 6
Hình 2.1: Mô hình CBOW ............................................................................................ 11
Hình 2.2: Mô hình Skip-gram liên tục...........................................................................12
Hình 2.3: Ví dụ về xác định độ gần nhau giữa các từ sử dụng Word2Vec ................... 13
Hình 2.4: Mã giả của phương pháp Binary Relevance .................................................15
Hình 2.5: Mã giả của phương pháp CC .........................................................................17
Hình 2.6: Mã giả của phương pháp CLR ......................................................................20
Hình 2.7: Mã giả của phương pháp CML .....................................................................23
Hình 3.1: Mô hình phân lớp đa nhãn văn bản tiếng việt ...............................................29


Multi – Label k-Nearest Neighbors

CC

Classifier Chain

CLR

Calibrated Label Ranking

CML

Collective Multi Label Classifier

RLOSS

Rank-Loss

HLOSS

Hamming-Loss

AP

Average Precision

MAP

Mean Average Precision


Không gian nhãn với q nhãn có thể {y1, y2, …, yq}

𝑥

Feature vector

Vector đặc trưng d chiều của thể hiện x (x1, x2, …, xd)T (x ∈ 𝒳)

𝑌

Tagged label set

Tập nhãn liên quan tới x (𝑌 ⊆ 𝒴)

𝑌̅

Complementary set

Tập bù của Y trong 𝒴

𝒟

Training set

Tập huấn luyện đa nhãn {(𝑥𝑖 , 𝑌𝑖 ) | 1 ≤ 𝑖 ≤ 𝑚}

𝑆

Test set

-

𝒟𝑗

Binary Training DataSet
for j-th Label

Tập huấn luyện nhị phân {(𝑥𝑖 , 𝜙(𝑌𝑖 , 𝑦𝑗 ))| 1 ≤ 𝑖 ≤ 𝑚} dẫn xuất từ tập 𝒟

𝜓(. , . , . )

-

𝜓(𝑌, 𝑦𝑗 , 𝑦𝑘 ) trả về +1 nếu 𝑦𝑗 ∈ 𝑌 và 𝑦𝑘 ∉ 𝑌 và -1 nếu 𝑦𝑗 ∉ 𝑌 và 𝑦𝑘 ∈ 𝑌

𝐷𝑗𝑘

Binary Training DataSet
for Label Pair (yj, yk)

Tập

Binary learning algorithm

Giải thuật học nhị phân

ℬ

𝜙(𝑌, 𝑦) trả về 1 nếu x 𝑦 ∈ 𝑌, -1 ngược lại.


và các nhãn có mối liên hệ với nhau, (2) dữ liệu có kích thước vô cùng lớn.
Xuất phát từ thực tế nêu trên, luận văn tập trung vào nghiên cứu một số phương
pháp phân lớp đa nhãn mà có xét đến mối quan hệ đa nhãn như: Classifier Chain (CC)
[8] [13], Calibrated Label Ranking – Xếp hạng theo nhãn hiệu chuẩn (CLR) [9],
Collective Multi-Label Classifier [6] và phương pháp cơ sở Binary Relevance [10].
Ngoài ra, luận văn cũng nghiên cứu về công cụ word2vec [16] xác định độ gần nhau
giữa các từ, nhãn và một số đề xuất cho việc tích hợp độ gần nhau giữa các từ, nhãn
này vào các phương pháp phân lớp đa nhãn đã nghiên cứu. Qua đó, luận văn áp dụng
các phương pháp, kỹ thuật đã nghiên cứu vào việc xây dựng mô hình phân lớp cho văn
bản tiếng Việt.
Đóng góp của luận văn gồm ba phần:
1) Nghiên cứu công cụ xác định độ gần nhau giữa các từ, nhãn.
2) Nghiên cứu một số thuật toán phân lớp đa nhãn và đưa ra đề xuất tích hợp độ
gần nhau giữa các từ, nhãn vào một số thuật toán phân lớp đã nghiên cứu.
3) Áp dụng các phương pháp học máy đa nhãn cho bài toán gán nhãn tiếng Việt,
thực nghiệm và đánh giá.
Nội dung của luận văn được chia thành các chương như sau:
Chương 1: Giới thiệu khái quát về đa nhãn và phân lớp đa nhãn văn bản. Ngoài ra,
luận văn còn trình bày thách thức của phân lớp đa nhãn. Từ đó, luận văn nêu ý nghĩa
của mối quan hệ giữa các nhãn trong bài toán phân lớp đa nhãn.
Chương 2: Trình bày về công cụ để xác định độ gần nhau giữa các từ, nhãn, các
phương pháp phân lớp đa nhãn mà luận văn sẽ áp dụng và đưa ra một số đề xuất cho
việc tích hợp độ gần nhau giữa các từ, nhãn vào các phương pháp phân lớp đa nhãn đã
1


nghiên cứu. Tiếp theo, luận văn còn trình bày về phương pháp đánh giá các mô hình
phân lớp đa nhãn và đưa ra một số độ đo đánh giá chúng.
Chương 3: Luận văn trình bày về mô hình phân lớp đa nhãn trong văn bản. Luận
văn áp dụng phương pháp biểu diễn dữ liệu (TF) vào trích trọn đặc trưng để giảm số

Cho 𝒳 là không gian thể hiện, 𝒴 là tập của các nhãn lớp. Theo Zhi-Hua Zhou
và các đồng nghiệp, đơn nhãn đơn thể hiện (học giám sát truyền thống), để học một

3


hàm f: 𝒳 → Y từ một tập dữ liệu {(x1, y1), (x2, y2) … (xm, ym)}, với xi 𝜖 𝒳 là một thể
hiện và yi 𝜖 𝒴 là nhãn xác định của xi.
Tức là từ một tập dữ liệu ví dụ đã được xây dựng trước 𝒟 = {{(x1, y1), (x2, y2)
… (xm, ym)}, nhiệm vụ của bài toán học đơn nhãn đơn thể hiện là học một ánh xạ f sao
cho có thể gán nhãn từng thể hiện chưa được gãn nhãn trong tập thể hiện 𝒳 với một
nhãn trong 𝒴.
Một số giải thuật học đơn nhãn đơn thể hiện như Naïve Bayes, Cây quyết định
và máy vector hỗ trợ (Support Vector Machine – SVN) [4].
Nhãn

Thể hiện
Hình 1.2: Học đơn nhãn

Trong thực tế, dữ liệu đa nhãn gặp nhiều trong thực tế hơn là dữ liệu đơn nhãn.
Theo Zhi-Hua Zhou và các đồng nghiệp, học đa nhãn (đơn thể hiện) được định nghĩa
như sau:
Để học một hàm f: 𝒳 → 2y từ tập dữ liệu {(x1, y1), (x2, y2) … (xm, ym)}, với với
xi 𝜖 𝒳 là một thể hiện và Yi ⊆ 𝒴 là tập của các nhãn của xi.
Nhãn
…
Nhãn

Thể hiện


và phân lớp tương ứng của chúng. Bước này còn gọi là bước xây dựng huấn luyện
(training process) hay ước lượng mô hình phân lớp. Ở bước thứ hai, mô hình phân lớp
xây dựng ở bước đầu sẽ được sử dụng để phân lớp cho những văn bản (chưa được
phân loại) trong tương lai. Bước đầu tiên được xem như là việc học có giám sát mà
chúng ta có thể sử dụng rất nhiều các kĩ thuật học máy đã có như: Naïve Bayes, k láng
giếng gần nhất (kNN), cây quyết định (Decision Tree), máy vector hỗ trợ (SVN)…
Mục tiêu của bài toán phân lớp là nhằm xây dựng mô hình có khả năng gán
nhãn cho một văn bản bất kì với độ chính xác cao nhất có thể. Mô hình để học và sử
dụng bộ phân lớp là một quá trình 2 pha được minh họa như sau:

5


Hình 1.4: Mô hình phân lớp

Trong những năm gần đây, đã có rất nhiều nghiên cứu để tìm ra các thuật phân
lớp cho bài toán phân lớp đa nhãn. Về cơ bản, người ta phân loại các giải thuật phân
lớp đa nhãn thành hai loại [13] [7]:
Chuyển đổi bài toán: Ý tưởng của các giải thuật loại này là chuyển đổi bài
toán phân lớp đa nhãn thành nhiều bài toán phân lớp đơn nhãn để sử dụng các giải
thuật phân lớp đơn nhãn đã được xây dựng trước đó. Một số giải thuật phân lớp đa
nhãn thuộc loại này như Binary Relevance [10], Classifier Chain [8], Calibrated Label
Ranking [9], Randon k-labelsets [7].
Tương thích giải thuật: Ý tưởng của các giải thuật loại này là mở rộng các các
giải thuật, kỹ thuật học đã có để xử lý dữ liệu đa nhãn. Một số giải thuật phân lớp đa
nhãn thuộc loại này như Multi - label k-Nearest Neighbors [14] tương thích các kỹ
thuật học lười (lazy learning), Collective Multi-Label Classifier [6] tương thích các kỹ
thuật về lý thuyết thông tin cụ thể là maximum entropy.
6


khi đó số lượng tập con nhãn sẽ là trên một triệu nhãn (220).
Để giải quyết vấn đề này, cần thiết phải khai thác mối quan hệ giữa các nhãn
khác nhau để nâng cao việc học đa nhãn.

7


Ví dụ, xác suất để một bức ảnh được gán nhãn là “Châu phi” rất cao khi ta biết
nó có các nhãn là “sư tử” và “đồng cỏ”, hay một văn bản được gán nhãn “giải trí”
thường sẽ không được gán nhãn “chính trị”.
Các cách tiếp cận của các phương pháp phân lớp đa nhãn hiện tại có thể được
phân loại dựa trên mối quan hệ giữa các nhãn như sau:
 Kiểu quan hệ bậc nhất: Các nhãn được giả thiết là độc lập. Nói cách khác,
mối quan hệ đa nhãn không được tận dụng trong phân lớp đa nhãn.
 Kiểu quan hệ bậc hai: Các mối quan hệ theo cặp, ví như: mối quan hệ giữa
“nhãn phù hợp” và “nhãn không phù hợp” trong quá trình xếp hạng nhãn.
 Kiểu quan hệ bậc cao: Ví như quan hệ toàn bộ theo đó toàn bộ các nhãn
đều có ảnh hưởng tới việc phân lớp mỗi nhãn; hoặc quan hệ bộ phận trong
đó với một nhãn nhất định, tồn tại một nhóm con trong số toàn bộ các nhãn
có ảnh hưởng tới việc phân lớp nhãn được xét .

8


1.3 Kết luận chương 1
Trong chương này, luận văn giới thiệu khái quát về một số khái niệm, nội dung
của đa nhãn và phân lớp đa nhãn văn bản. Ngoài ra, luận văn cũng nêu ra thách thức
của bài toán đa nhãn văn bản và mục tiêu của luận văn để giải quyết thách thức về việc
tận dụng mối quan hệ các nhãn trong phân lớp đa nhãn.
Chương tiếp theo, luận văn sẽ giới thiệu về phương pháp xác định độ gần nhau

Ngoài việc học các vector biểu diễn của các từ, word2vec cũng cung cấp công
cụ cho biểu diễn của cụm từ bằng việc tiền xử lý tập dữ liệu huấn luyện để thành lập
các cụm từ và sau đó tập các cụm từ này được xem như các từ để học vector biểu diễn
cho các từ đó.
Bảng sau đây mô tả một số tệp nguồn chính trong word2vec, theo đó mỗi tệp sẽ
ứng với một chức năng mà word2vec hỗ trợ:
Bảng 2.1: Các tệp nguồn chính trong Word2Vec
STT
1.

Tên tệp
word2vec.c

2.

word2phase.c

3.

distance.c

Hỗ trợ
Học mô hình vector biểu diễn của tất cả các từ từ tập
dữ liệu đầu vào.
Tiền xử lý dữ liệu huấn luyện để xây dựng tập các
cụm từ cho tập dữ liệu đầu vào.
Tính độ gần nhau của từ do người dùng nhập vào
10



từ ở xa nhỏ đi để khắc phục vấn đề này.
Không giống với các kiến trúc mạng nơ-ron được sử dụng trước đó để học
vector từ, việc đào tạo mô hình Skip-gram không sử dụng đến các phép nhân ma trận
dày đặc. Điều này khiến cho việc đào tạo trở nên cực kỳ hiệu quả: một máy đơn đã
được tối ưu có thể đào tạo hơn 100 tỉ từ một ngày. Và các đại diện từ được tính toán ra
bằng cách sử dụng mạng nơ-ron, tức các vector đã học được thì mã hóa một cách rõ
ràng nhiều quy tắc ngôn ngữ và mô hình.
Một mở rộng đáng ngạc nhiên của phương pháp này đó là việc áp dụng các
phép cộng/trừ đại số cho các vector có thể thu được các kết quả bất ngờ về ngữ nghĩa.
Ví dụ: phép tính vec(“Russia”) + vec(“river”) ta sẽ thu được kết quả là vec(“Volga
River”) hay vec(“king”) - vec(“man”) + vec(“woman”) ta sẽ thu được kết quả là
vec(“queen”). Điều này cho thấy một gợi ý mơ hồ về việc hiểu biết ngôn ngữ có thể
thu được bằng cách sử dụng các phép toán cơ bản với các đại diện vector từ.

Hình 2.2: Mô hình Skip-gram liên tục
12


2.2.3 Sử dụng word2vec để đo độ gần nhau giữa các từ
Một trong các chức năng được hỗ trợ từ word2vec đó là tính toán độ gần nhau
giữa các từ được thể hiện bằng giá trị thực của khoảng cách giữa các từ; cụ thể là, từ
mô hình biểu diễn của các vector từ ta có thể có được độ gần nhau của hai từ bất kỳ
hay giữa các từ trong một tập con từ nào đó. Ví dụ sau đây mô tả về kết quả các từ gần
nhất với từ “index” khi sử dụng word2vec cho tập dữ liệu đầu vào là 2694 bài báo trên
trang “vnexpress.net” đã qua tiền xử lý [3] sử dụng độ đo cosine:

Hình 2.3: Ví dụ về xác định độ gần nhau giữa các từ sử dụng Word2Vec
Như vậy, sử dụng mô hình vector biểu diễn từ huấn luyện được từ công cụ,
Word2Vec có thể tính được khoảng cách (độ gần nhau) các từ bất kỳ cũng như các
nhãn với nhau. Kết quả này sẽ được luận văn sử dụng để tích hợp vào một số phương

Bảng 2.2: Tập dữ liệu ví dụ
Thể hiện

Tập nhãn

𝑥1

{𝑦2 , 𝑦3 }

𝑥2

{𝑦1 }

𝑥3

{𝑦1 , 𝑦2 , 𝑦3 }

𝑥4

{𝑦2 , 𝑦4 }

Khi đó ta sẽ xây dựng 4 tập dữ liệu huấn luyện cho 4 nhãn như sau:
𝐷1 = {(𝑥1 , −1), (𝑥2 , 1), (𝑥3 , 1), (𝑥4 , −1)}
𝐷2 = {(𝑥1 , 1), (𝑥2 , −1), (𝑥3 , −1), (𝑥4 , −1)}
14


𝐷3 = {(𝑥1 , 1), (𝑥2 , 1), (𝑥3 , 1), (𝑥4 , −1)}
𝐷4 = {(𝑥1 , −1), (𝑥2 , 1), (𝑥3 , −1), (𝑥4 , 1)}
Sau khi xây được q tập huấn luyện từ tập dữ liệu ví dụ ban đầu, Binary

chuỗi (chain) các bài toán phân lớp nhị phân, trong đó bộ phân lớp nhị phân sau sẽ sử
dụng những dự đoán của bộ phân lớp trước đó trong chuỗi [13] [8].
Cho q là tập nhãn { 𝑦1 , 𝑦2 , … , 𝑦𝑞 }, 𝜏 ∶ {1, … , 𝑞} → {1, … , 𝑞} là một hàm hoán vị
để xác định thứ tự của các nhãn ví dụ, 𝑦𝜏(1) ≻ 𝑦𝜏(2) ≻ ⋯ ≻ 𝑦𝜏(𝑞) . Xét nhãn thứ j là
𝜏(𝑗)

(1 ≤ 𝑗 ≤ 𝑞) trong danh sách nhãn đã được sắp thứ tự, tập dữ liệu huấn luyện của
15