Danh sách hình vẽ
Hình 1: Phân loại hệ thống quản lý danh tiếng 4
Hình 2 : Hai mô hình hệ thống 5
Hình 3 : Hệ thống quản lý danh tiếng tích hợp trong các trang web bán hàng
6
Hình 4 : Sử dụng hệ thống quản lý danh tiếng cho công ty BKAV 6
Hình 5 : Bốn tập dữ liệu được phân lớp theo phương pháp Pairwise
Classification 14
Hình 6 : Ví dụ số lớp trên Swotti 21
Hình 7 : Mô hình thực nghiệm bài toán 23
Danh sách bảng biểu
Bảng 1 : Dữ liệu để phân lớp đa nhãn 11
Bảng 2 : Phân lớp đa nhãn sử dụng PT2 11
Bảng 3 : Phân lớp đa nhãn sử dụng PT1 12
Bảng 4 : Phân lớp sử dụng PT3 12
Bảng 5 : Bốn tập dữ liệu được tổ chức phân lớp theo PT4 13
Bảng 6 : Bảng ký hiệu 26
Bảng 7 : Cấu hình phần cứng sử dụng trong thực nghiệm 28
Bảng 8 : Một số phần mềm sử dụng 28
Bảng 9 : Tập dữ liệu thực nghiệm 29
Bảng 10 : Tập dữ liệu huấn luyện 29
Bảng 11 : Kết quả đánh giá bộ phân lớp đa lớp sử dụng phương pháp
Entropy 30
Danh sách các từ viết tắt
ORM Online reputation management
BR Binary relevance learning
MLC Multilabel classification
LR Label ranking
MLR Multilabel ranking
SVM Support vector machine
Mở đầu

nhãn,bài toán phân lớp đa nhãn và bài toán xếp hạng nhãn trong hệ thống
quản lý danh tiếng.
Chương 2: Khóa luận trình bày về các giải pháp phân lớp đa nhãn,
xếp hạng đa nhãn. Ngoài ra khóa luận còn trình bày áp dụng phương pháp
xếp hạng đa nhãn bằng so sánh theo cặp vào bài toán quản lý danh tiếng.
Chương 3: Khóa luận đề xuất mô hình xếp hạng đa nhãn và giải pháp
phát hiện quan điểm trong bài toán quản lý danh tiếng. Đồng thời khóa luận
cũng trình bày chi tiết các pha cũng như các bước trong mô hình
Chương 4: Khóa luận trình bày thực nghiệm cho việc áp dụng
phương pháp xếp hạng đa nhãn đã được đề xuất. Từ đó, khóa luận sử dụng
để đánh giá danh tiếng cho 1000 khách sạn ở Việt Nam.
Phần kết luận : Tóm lược kết quả đạt được của khóa luận và định
hướng phát triển tương lai.
Chương 1. Tổng quan về bài toán xếp hạng nhãn trong quản lý danh
tiếng
• Hệ thống quản lý danh tiếng
Theo Liu,Ling [3], 2011 hệ thống quản lý danh tiếng là hệ thống làm
nhiệm vụ thu thập ý kiến của người dùng về sản phẩm và các sự kiện, thông
tin về uy tín của sản phẩm,… Sau đó tổng hợp thông tin này và công bố với
mọi người. Mọi người dùng khác có thể sử dụng thông tin mà hệ thống quản
lý danh tiếng mang lại như một tài liệu tham khảo để đưa ra quyết định. Với
sự phát triển ngày càng lớn của Internet thì hệ thống quản lý danh tiếng ngày
càng đóng một vai trò quan trọng.
Đối với doanh nghiệp thì danh tiếng càng có tầm quan trọng lớn hơn.
Việc quản lý danh tiếng là quá trình theo dõi thương hiệu và phản ứng khi có
những phản hồi tiêu cực về công ty đang quản lý. Từ đó, công ty có thể
tránh đươc những thảm họa tiềm ẩn như: ai đó nêu tên công ty trong một bài
viết có tính chất xuyên tạc. Ngoài khả năng phòng vệ, việc làm này còn giúp
công ty có thể tham gia vào những cuộc thảo luận xoay quanh các vấn đề
của doanh nghiệp, từ đó giúp quảng bá hình ảnh công ty ra bên ngoài hiều

theo (Hoffman và cộng sự., 2009) [15], (Zheng và Jin, 2009) [16],
(Swamynathan và cộng sự., 2010) thì hệ thống chỉ được chia làm ba phần :
phần thu thập thông tin, phần xử lý thông tin và phần hiển thị kết quả người
dùng như hình 3(b).
Hình 2 : Hai mô hình hệ thống
So sánh hai cách tiếp cận trên thì mô hình thứ hai sử dụng thông tin
được thu thập từ nguồn có uy tín sẽ cho độ chính xác cao hơn. Không những
thế cách tiếp cận này còn tránh được sự gian lận của người dùng hay tổ
chức, vì cách tiếp cận này không sử dụng thông tin phản hồi như là nguồn
dữ liệu. Chính vì sự chính xác mà cách tiếp cận thứ hai mang lại nên chúng
tôi quyết định xây dựng mô hình thực nghiệm ở chương ba theo cách tiếp
cận thứ hai.
• Các ứng dụng của hệ thống quản lý danh tiếng trong thực tế
Hiện nay, ở Việt Nam có hai loại ứng dụng nổi bật của hệ thống quản
lý danh tiếng là :
• Tích hợp trong các trang web bán hàng : Việc đánh giá danh tiếng
trong các trang web bán hàng giúp người dùng có thể lựa chọn được
những sản phẩm phù hợp với túi tiền và yêu cầu của họ. Hiện nay, có
một số trang web ở Việt Nam đã tích hợp hệ thống quản lý danh tiếng
như : vatgia.com, chudu24.com,
Hình 3 : Hệ thống quản lý danh tiếng tích hợp trong các trang web bán hàng
• Là hệ thống theo dõi danh tiếng riêng biệt cho từng công ty, tổ chức :
Việc theo dõi và bảo vệ danh tiếng cho từng công ty đã được ứng
dụng trên thế giới từ lâu, xong hiện tại ở Việt Nam, hệ thống theo dõi
danh tiếng cho từng công ty vẫn còn là vấn đề mới. Theo tìm hiểu của
chúng tôi, hệ thống ORM là hệ thống thương mại về quản lý danh
tiếng đầu tiên ở Việt Nam.

Hình 4 : Sử dụng hệ thống quản lý danh tiếng cho công ty BKAV
• Bài toán xếp hạng nhãn trong hệ thống quản lý danh tiếng

lượng bộ phân lớp giảm đi đáng kể. Khắc phục nhược điểm trên của phương
pháp chuyển đổi nhị phân (BR), phương pháp xếp hạng nhãn do AAAA []
đề xuất đã giải quyết được sự ảnh hưởng lẫn nhau giữa các nhãn lớp và cho
kết quả phân lớp rất khả quan (điền kết quả ra)
• Bài toán xếp hạng nhãn để phân lớp dữ liệu đa nhãn
Bài toán xếp hạng nhãn là một bài toán đang rất được quan tâm hiện
nay như Brinker và cộng sự [3], 20, Tsoumakas và cộng sự [], 20. Tuy
nhiên, phương pháp xếp hạng nhãn theo cặp do Klaus Brinker và cộng sự [],
20 đề xuất là phương pháp đơn giản và hiệu quả trong việc xếp hạng dữ liệu
đa nhãn.
Ý tưởng của bài toán xếp hạng nhãn so sánh theo cặp là với mỗi cặp
nhãn (λi, λj) chúng tôi đưa ra một mô hình nhị phân M
ij
(x). Bằng mô hình
đó, chúng tôi có thể dự đoán nhãn λi được ưu tiên hơn nhãn λj hoặc ngược
lại với mỗi tài liệu đầu vào x. Từ tập các bộ phân lớp như trên, sẽ đưa ra
được kết quả của việc gán nhãn cho tài liệu dựa trên độ ưu tiên của nhãn.
Với những ưu điểm trên của phương pháp xếp hạng nhãn so sánh theo
cặp trong miền dữ liệu đa nhãn trong [Klaus Brinker], chúng tôi quyết định
sử dụng phương pháp này trong việc xây dựng bộ phân lớp dữ liệu đa nhãn
và ứng dụng để đánh giá danh tiếng cho 1000 khách sạn ở Việt Nam.
Tổng kết chương một
Trong chương một, chúng tôi đã giới thiệu về hệ thống quản lý danh
tiếng, phân loại hệ thống và nêu lên các ứng dụng phổ biến của hệ thống
quản lý danh tiếng. Ngoài ra, chúng tôi còn nêu lên được tầm quan trọng của
bài toán xếp hạng nhãn trong phân lớp dữ liệu đa nhãn.
Chương tiếp theo, chúng tôi sẽ đi sâu vào phân tích bài toán phân lớp
dữ liệu đa nhãn, giới thiệu các phương pháp chuyển đổi phổ biến và ưu điểm
của bài toán xếp hạng nhãn trong phân lớp dữ liệu đa nhãn.
Chương 2 : Phân lớp đa nhãn và xếp hạng nhãn

j
,c
i
) có nghĩa là tài liệu d
j
thuộc lớp
c
i
. Giá trị F(False) tức là tài liệu d
j
không thuộc lớp c
i
.
Hoặc, phân lớp văn bản là bài toán tìm một hàm trong đó D là tập
các văn bản và là tập các lớp cho trước, hàm được gọi là bộ phân lớp.
Tùy vào bài toán khác nhau, ta có các ràng buộc khác nhau. Nhìn
chung có thể phân biệt bài toán phân lớp theo hai cách sau :
• Phân lớp văn bản nhị phân / đa lớp : Bài toán phân lớp văn bản được
gọi là nhị phân nếu , gọi là đa lớp nếu .
• Phân lớp văn bản đơn nhãn / đa nhãn : Bài toán phân lớp văn bản
được gọi là đơn nhãn nếu mỗi tài liệu hay câu được gán vào chính xác
một lớp. Một bài toán phân lớp văn bản được gọi là đa nhãn nếu một
tài liệu hay câu có thể được gán nhiều hơn một nhãn.
• Bài toán phân lớp đa nhãn
Với mỗi thuật toán phân lớp sẽ có những chiến lược khác nhau cho
bài toán phân lớp đa nhãn. Ví dụ, thuật toán Naïve Bayes có thể gán một văn
bản hay câu không chỉ vào lớp có xác suất dự đoán cao nhất mà sẽ gán vào
tất cả các lớp có xác suất cao hơn một ngưỡng nào đó. Với các thuật toán
khác, giải pháp phổ biến là chuyển bài toán n lớp thành tập các bài toán nhị
phân. Trong phạm vi khóa luận này, khóa luận sẽ trình bày một số giải pháp

) Vị trí(λ
3
) Giá cả(λ
4
)
1 X X
2 X X
3 X
4 X X
Bảng 1 : Dữ liệu để phân lớp đa nhãn
Khi đó có hình 2 và hình 3 biểu diễn việc chuyển đổi từ phân lớp đa
nhãn về phân lớp đơn nhãn sử dụng hai phương pháp trên.
Ex. Phục vụ Ăn uống Vị trí Giá cả
1 X X
2 X
3 X
4 X
Bảng 2 : Phân lớp đa nhãn sử dụng PT2
Ex. Phục vụ Ăn uống Vị trí Giá cả
3 X
Bảng 3 : Phân lớp đa nhãn sử dụng PT1
Phương pháp tiếp theo (PT3) là phương pháp nhóm một tập nhãn vào
thành một nhãn. Hình 4 biểu diễn kết quả chuyển đổi từ dữ liệu ở hình một
áp dụng PT3. Tuy nhiên, phương pháp này có hạn chế là số lượng các lớp
học lớn. Theo [17], phương pháp này đã được sử dụng trong Boutell và cộng
sự (2004) và Diplaris, Tsoumakas, Mitkas, và Vlahavas (2005).
Ex. Phục vụ

Phục vụ ^ Giá cả Vị trí ^ Giá
cả

một kết quả phân lớp cuối cùng, vẫn phải kết hợp kết quả dự báo của tất cả
c(c-1)/2 bộ phân lớp nhị phân đó.
Phương pháp Pairwise Classification xây dựng c(c-1)/2 bộ phân lớp
nhị phân cho tập nhãn L = {λ
i
| i = 1 . . . c}. Một giả thuyết mạnh được sử
dụng trong phương pháp này là với mỗi dữ liệu học x
k
⊆ X, thì mọi nhãn
được gán cho x
k
thuộc tập P
k
⊆ L sẽ mạnh hơn so với tất cả các nhãn không
được gán thuộc tập N
k
= {L\P
k
} với một hàm ưu tiên về độ liên quan giữa
nhãn và dữ liệu. Nên việc phân lớp cho cặp là việc huấn luyện giữa lớp
nhãn và . Hình 5 biểu diễn sáu bộ phân lớp nhị phân đối với mỗi cặp nhãn.
Hình 5 : Bốn tập dữ liệu được phân lớp theo phương pháp Pairwise
Classification
• Áp dụng các thuật toán học máy để phân lớp đa nhãn
Adaboost.MH và Adaboost.MR Schapire và Singer, 2000 [19] là
phương pháp mở rộng của phương pháp AdaBoost Freund và Schapire, 1997
[18] để phân lớp đa nhãn. Cả hai phương pháp này đều sử dụng kỹ thuật
phân lớp kết hợp các luật “yếu” (weak rule) có độ chính xác dự đoán thấp để
cho ra một luật có độ chính xác dự đoán cao. Cốt lõi của hai thuật toán này
là thực hiện phép chuyển đổi (PT6) : Xét bài toán phân loại văn bản nhiều

vòng phân lớp nhị phân thứ hai lại sử dụng chính dữ liệu mở rộng để phân
lớp và lại tiếp tục làm giàu thêm tập đặc trưng. Ví dụ : cần phân lớp cho tài
liệu x, bộ phân lớp khi đó không chỉ sử dụng tập đặc trưng của tài liệu x mà
còn sử dụng thêm các đặc trưng kết hợp nhãn thu được trong quá trình học
mô hình. Từ cách tiếp cận này, có thể thu được đặc trưng phụ thuộc giữa các
nhãn để phục vụ quá trình phân lớp.
Cách cải tiến thứ hai là những cải tiến liên quan trực tiếp đến hiệu quả
của thuật toán phân lớp SVM trong phân lớp dữ liệu đa nhãn. Dữ liệu đa
nhãn thường là kiểu dữ liệu không có sự phân chia rõ ràng giữa các nhãn.
Chính vì thế, để cải tiến hiệu quả của thuật toán thì cần loại bỏ các dữ liệu
thuộc lớp tiêu cực nhưng lại rất gần với lớp tích cực. Phương pháp này được
thực hiện ở hai cấp là : cấp tài liệu và cấp lớp học. Đối với cấp tài liệu thuật
toán thực hiện qua hai bước :
• Đầu tiên, thực hiện huấn luyện từ tập dữ liệu học.
• Trong quá trình huấn luyện, loại bỏ các dữ liệu thuộc lớp âm mà thỏa
mãn một ngưỡng cho trước.
Đối với cấp lớp học, thuật toán thực hiện loại bỏ các trường hợp huấn luyện
tiêu cực của một lớp nếu nó tương tự như các lớp học tích cực, dựa trên một
ma trận “tương đồng”.
• Xếp hạng đa nhãn
• Bài toán xếp hạng nhãn
Xếp hạng nhãn là việc tìm một ánh xạ từ tập dữ liệu đầu vào đến việc
xếp hạng tập các nhãn trên một tập nhãn có sẵn. Xét tập X ⊆ R
m
là tập dữ
liệu đầu vào, tập nhãn cho trước L = {λ
i
| i = 1 . . . c} , và tập Y kết quả đầu
ra của việc xếp hạng trên tập nhãn L. Với T = {x
i

x
và tập nhãn tiêu cực N
x
, và tập nhãn P
x
sẽ được gán cho
dữ liệu đầu vào x.
Thời gian gần đây, bài toán xếp hạng nhãn đang được rất nhiều nghiên
cứu quan tâm vì tầm quan trọng và độ liên quan của nó đến những bài toán
khác là vô cùng lớn. Sau đây là một số bài toán liên quan đến vấn đề xếp
hạng đang được quan tâm :
• Phân lớp đa nhãn : Như đã được nhắc đến trong phần trên của
khóa luận thì bài toán xếp hạng đa nhãn với việc phân chia tập
nhãn thành hai tập tích cực và tiêu cực cũng được ngầm hiểu