I H C QU C GIA TP. HCM
I H C BÁCH KHOA
-------------------

TR N MINH HÙNG

RÚT TRÍCH, PHÂN LO I VÀ T NG H P THÔNG TIN
T

CÁC PH N H I TRÊN M NG XÃ H I

Chuyên ngành : KHOA H C MÁY TÍNH
Mã s : 60 48 01

LU

TP. H CHÍ MI


C HOÀN THÀNH T I
I H C BÁCH KHOA -

Cán b

- HCM

ng d n khoa h c: PGS. TS. Qu

Cán b ch m nh n xét 1: TS. Nguy

ng

Cán b ch m nh n xét 2: TS. Lê Thanh Vân

Lu
ngày 23 tháng 07

cb ov t

i h c Bách

2013

Thành ph n H

m:

1. Ch t ch: TS. Ph m Tr
2.

Ng c Châu

3. Ph n bi n 1: TS. Nguy

ng

4. Ph n bi n 2: TS. Lê Thanh Vân
5. y viên: TS. Tr
Xác nh n c a Ch t ch H
ngành sau khi lu
CH T CH H


ng Khoa qu n lý chuyên
c s a ch a (n u có).

NG

NG KHOA

ii


T NAM
-

-

MSHV: 10070481
23/02/1987
Chuyên ngành: Kho

: 60 48 01

I.

II.
áp
-domain

III. NGÀY GIAO NHI


: 02/07/2012

IV.
V. CÁN

: 30/11/2012
:

13

iii


Tôi xin chân thành c
cô gi ng d

ih cc bi t c

d n, truy
th

ng d n, ch d

t n tình c a các th y

i h c Bách khoa thành ph H Chí Minh.
y PGS. TS.

,


i

ng

t nh ng ki n th c và kinh nghi

ki n

hoàn thành lu

Và xin c m

n bè và nh

ng và truy n

thêm ngh l c cho tơi trong q trình h c t p, nghiên c u c a b n thân.
M

g ng r t nhi u trong vi c th c hi n lu

h n, nên không th tránh kh i nh ng thi u sót,
cs

i th i gian có
nh, r t mong nh n

n c a quý Th y Cô và các b n.

H c viên

Tr n Minh Hùng

x


V i s phát tri n c a m ng xã h i, ngày càng nhi
ki n

i tham gia và chia s các ý

a h v nh ng s n ph m và d ch v mà h

d ng. Các ph n

h i này cung c p nhi u thông tin h u ích, giúp

các quy t

nh mua s m và các công ty c i thi n s n ph m c a h .
Vi c rút trích các thơng tin h u ích t
v

ng ph n h i quá l n không ph i là m t

i r t nhi u th i gian và công s

nhi

ng nghiên c


Nhi u b phân l

này,

t trong s
c phát tri

c c. Tuy nhiên, c
u này

gi i quy t v

phân lo i m t ph n h i là tích c c hay tiêu

c th hi n khác nhau trong các mi n d li u khác nhau;
chính xác c a vi c phân lo i. Các b phân l p m

chính xác khi áp d ng v i nh ng mi n d li u khác v i mi n hu n luy n.
M c tiêu c a lu

là xây d ng m t b phân l p có th ho

ng t t trên

các mi n d li u khác nhau.
ASTRACT
With the growth of social networks, more and more people take part and share their
comments and reviews about products and services they used. These comments
provide useful information, helping consumers make shopping decisions and
companies improve their products.

But the amount of these comments is so big that extracting useful information from
them is not easy, require a lot of time and effort. As a result, many research
directions have been proposed, one of them is Sentiment Analysis.
Many classifiers have been developed to classify a comment as either positive or
negative. However, sentiment is expressed differently in different domains, which
affect the accuracy of sentiment classification. Trained classifiers lose accuracy
when used on domains different from the training domain.
The aim of this thesis is to develop a classifier which can perform well on different
domains.
xi


ng trình nghiên c u c a tơi. Các s li u, k t qu nêu
trong lu n án là trung th c, khách quan

c công b trong b t k m t

cơng trình nào khác.
.

H c viên
Tr n Minh Hùng

xii


NHI M V LU
L IC

.................................................................... iii


........................................................................................................ x

TÓM T T ............................................................................................................. xi
L

................................................................................................ xii

M C L C ...........................................................................................................xiii
I THI U ....................................................................................... 1
1.1.

Lý do ch

tài: ..................................................................................... 1

1.2.

M c tiêu và gi i h n c

1.3.

tài: ............................................................... 2

tài: ................................................................................. 2
NG QUAN ...................................................................................... 3

2.1.

n theo c m xúc ................................ 3


2.2.

V

2.3.

Domain Adaptation .................................................................................. 7

2.4.

c chú ý g

ng ti p c n c

-domain classification ...................... 5

tài....................................................................... 11

LÝ THUY T ........................................................................ 13
3.1.

Support Vector Machine (SVM) ............................................................ 13

3.2.

Ti n x

n .................................................................................. 15


3.3.

Bi

n Vector Space Model .............................................. 16

3.4.

DeltaTFIDF............................................................................................. 18

3.5.

t qu phân lo i .................................................................... 19
T K VÀ HI N TH

4.1.
4.2.

.......................... 21

xu t: ............................................................................ 21
Thi t k và hi n th

...................................................... 23

C NGHI M .............................................................................. 27
5.1.

T p d li u: ............................................................................................. 27


5.2.

K t qu thí nghi m ................................................................................. 28

5.3.

Nh n xét: ................................................................................................. 29
T LU N ....................................................................................... 30

TÀI LI U THAM KH O ................................................................................... 31

xiii


1.1.

Lý do ch

tài:

Các ph n h i, bình lu n

c chia s b

i dùng trên các trang m ng xã h i là

m t ngu n d li u phong phú, cung c p nhi u thông tin h u ích v
c a các s n ph m, d ch v mà h
nh vào vi c quy


m

d ng. Các thông tin này góp ph n khơng

nh mua s m c

i tiêu dù

nhà s n su t

ng phát tri n, c i ti n các s n ph m.
Tuy nhiên, v i s phát tri n ngày càng m nh c a các m ng xã h i, s
ph n h

ng các

c chia s ngày càng nhi u, vi c rút trích ra các thơng tin h u ích là m t

v

n nhi u th i gian và công s c.
gi i quy t v

s

này, nhi u

ng nghiên c u m

Sentiment Classification (phân lo


b n theo c m xúc là m

ng h

c phân lo i d

t trong

n theo c m xúc). Phân lo

c bi t c a bài toán phân lo
ng c m xúc c a chúng.

n, các
ng phân lo i

ng là các câu bình lu n, ph n h i trên các m ng xã h i ho c
m t s n ph m, d ch v

c

phân lo i làm hai l p chính là tích c c và tiêu c c.
M t trong nh ng thách th c c n gi i quy t
c m xúc là v

c phân lo

Domain Dependence (ph thu c mi n). Các b phân l


xây d ng ch

c k t qu phân lo i t t trên mi n d li

áp d ng sang mi n d li u khác thì k t qu
Nguyên nhân là do có nh ng t ch xu t hi n
delicious
i hi
b phân l
tr ng s

n theo
c

c hu n luy n, khi

chính xác r t th p.
m t s mi n d li u nh

nh, ví d

th hi n c m xúc tích c
c s d ng trong các nh n xét v

ym t

c hu n luy n trên t p d li u là các nh n xét v sách s khơng có
ch cv t

delicious


dùng b phân l

phân

lo i các nh n xét v
Ngồi ra, x

ng tình c m c a m t s t có th

c s d ng. Ví d , t

unpredictable
1

i tùy theo ng c nh mà nó


c khi nói v kh

n hành n

nh c a m t chi c xe.
Hi n nay vi c xây d ng m t b phân l p có kh
nhi u mi n khác nhau là m t v

1.2.

c quan tâm gi i quy t.


M c tiêu và gi i h n c

M c tiêu c

i t t d li u thu c

tài:

tài là nghiên c u hi n th c m t b phân l p có th phân lo i hi u

qu các ph n h i thu c nhi u mi n d li u khác nhau, s d ng k thu t nh n d ng
các t khoá phân lo

c l p mi n (domain-independent keywords).

tài này ch t p trung x lý các ph n h i b ng ngôn ng ti
xu

ng d

c các y u t c a m ng xã h

chính

xác c a b phân l p.

1.3.

tài:


V im

ra và k t qu
Xây d

c, nh

tài mang l i là:

c b phân l p cho d li u thu c nhi u mi n d li

xác c a b phân l

i m t s cơng trình nghiên c u khác.

Tìm hi u và áp d ng k thu t nh n d ng các t khoá phân lo
(domain-independent keywords) d a trên tr ng s
thành công các t

Góp ph n ch

phát hi n

n theo c m xúc cho k t qu

i tr ng s TFIDF.
c vi c k t h p thêm thông tin v

c m c a các t
c phân lo


c l p mi n

c l p mi n và ph thu c mi n. Cho th y vi c s

d ng tr ng s DeltaTFIDF trong phân lo
phân lo i t

chính

ng tình

n nâng cao hi u qu trong
n theo c m xúc.

2


ta s kh o sát m t s cơng trình nghiên c u có liên quan m t
thi

tài.

2.1.
Phân lo

n theo c m xúc là m

ng h


n nay, nhi u nghiên c
l p

c bi t c a bài toán phân lo i

c ti n hành nh m xây d ng các b phân

c này
D a trên các gi i thu t h c máy (machine learning):

V

b phân l

c xây d ng d a trên các gi i thu t h c máy

và t p d li u hu n luy n g m các

n

c gán nhãn s n.

chính xác c a

b phân l p ph thu c khá nhi
thu t h c máy

n. Các gi i

c s d ng là Support Vector Machine (SVM), Naive


Bayes, maximum entropy,

d a trên các gi i thu t h

chính xác khá cao v i bài toán phân lo
Pang et al. [10

t

n truy n th ng theo ch

o sát hi u qu c a

.

i bài toán phân lo i

n c m xúc. Các gi i thu t h c máy Naive Bayes, maximum entropy và
support vector machines (SVMs)

c áp d ng trên t p d li u là nh ng nh n xét

v phim nh. K t qu th c nghi m cho th y
phân lo

n theo ch

c th


truy n th ng. Nguyên nhân d

trong m t s nh n xét v phim nh

i nh n xét c

i
u này là do
t ng quát

cv
Ví d xét các câu nh n xét v m t b
This film should be brilliant. It sounds like a great plot, the actors are first grade,
and the supporting cast is good as well, and Stallone is attempting to deliver a good
performance. However, it can't hold up
b n có s d ng nhi u t

ng tích c
i là m t nh n xét tiêu c c.

3


V i nh ng

ng h

ng tình c m c a

ng tình c m c a h u h t các t trong


n

cv i

n

phân l

ra k t qu phân lo i chính xác.
D a trên

ng tình c m c a các t v ng

V

c phân lo

c th c hi n ch d

ng tình

c m c a các t v ng, ta không c n s d ng t p d li

hu n luy n.

Turney [14]

M t nh n xét


u vào s

ra m t gi i thu t tiêu bi
c phân lo i là tích c c hay tiêu c c qua m t gi i thu

a. T nh

ng m

u vào, áp d ng b gán nhãn t lo i (part-ofm t có ch a các t mang nhi

ng tình c m

, phó t .
b.

ng

ng tình c m c a các c m t
và

nh. Ch n hai t

i di n cho các t tích c c và tiêu c c, d a trên

liên k t ng

a các c m t v i hai t

ng


tình c m c a chúng. C m t có m i liên k t v i t

nhi

cl is
c.

c.

ng tình c m c a t t c các c m t , t

i câu

nh n xét là tích c c hay tiêu c c.
o sát trên t p d li u g m các câu nh n xét v s n ph m và phim nh.
v i k t qu c

ng c m xúc c a các nh n xét v

phim nh có th khơng ph thu
chính xác c a b phân l p ch

ng c m xúc c a các c m t trong câu,
t kho ng 66%.

chính xác c

áp d ng thêm các k


thu t x lý ngôn ng t
m

ph

nh, t

ng ho c gi m nh

phân l p SO-CAL (the Semantic Orientation CALculator)

c a Taboada et al. [13]. SO-

c kh o sát trên m t vài t p d li u khác

nhau và cho k t qu phân lo i khá t t,

nh, không ph thu c nhi u vào m t

mi n d li u c th nào.
4


Tóm l i, có hai lo
phân lo

xây d ng b phân l p

n theo c m xúc


c

t lo i d a trên các gi i thu t h c máy

t o ra các b phân l p s d ng các t p d li u hu n luy n. Lo i th hai không
c n s d ng các t p d li u hu n luy n, các b phân l

c t o ra d a trên tính

ng tình c m c a các t và các k thu t x lý ngôn ng t nhiên.

2.2.

V

c chú ý g

Nhi u nghiên c

-domain classification

c th c hi

Chaovalit

so sánh gi a hai lo

ng c hai lo

v phim nh. K t qu cho th

t

phân lo i các nh n xét
a trên gi i thu t h c máy cho k t qu

n có th i gian hu n luy n dài và yêu c u t p d li u hu n luy n

ph

l n.

H u h t các nghiên c

c th c hi n trên t p d li u là các nh n xét v phim nh

và các s n ph m thu t

n lo

dung dài và ch t p trung vào m t lo

ng có n i

ng, s n ph m c th . Tuy nhiên, trên

các trang m ng xã h i, các nh
nhi

i


c vi t ng n g n, không tuân theo m t chu n nào và có

th

c

ng thu c nhi u mi n d li u khác nhau. V y v i các nh n

xét lo

phân lo i nào s cho k t qu t

tr l i câu h i này, Paltoglou et al. [11]
pháp phân lo i v i t p d li u

kh o sát hi u qu c a hai
i tho i, ph n h i c

i dùng trên

các trang m ng xã h i. K t qu th c nghi m cho th
d a trên
là v

ng tình c m c a t v ng

ng h p này, các
t hi u qu

c bi t


n có n i dung ng n, ch g m m t ho

b phân l p d a trên gi i thu t h c máy cho k t qu v
Nguyên nhân d

chính xác r t th p.

n k t qu trên là do trong các mi n d li u khác nhau, c m xúc

c th hi n c a m t s t

,t

tích c c khi nói v th i gian s d ng c
gian th c thi c a m t c

long
mô t v th i

nh thì l i mang ý tiêu c c.

5


a, có nh ng t ch xu t hi n
delicious
i hi
l


m t s mi n d li u nh

nh, ví d

t

th hi n c m xúc tích c c khi
c s d ng trong các nh n xét v

y m t b phân

c hu n luy n trên t p d li u là các nh n xét v sách s khơng có tr ng s
ch cv t

delicious

dùng b phân l

phân lo i các

nh n xét v
Hình 2.1 trình bày các k t qu phân lo
các b phân l

c do Blitzer et al. [1] khi s d ng

c hu n luy n trên m t mi n d li

phân lo i cho các d li u


thu c mi n khác. D li u là các câu nh n xét v s n ph m thu c các mi n khác
appliances.
chính xác mà b phân l
cùng mi n hu n luy n, các c t baseline

c khi phân lo i các d li u
c khi dùng phân lo i

d li u thu c các mi n khác. Các c t SCL, SCL-

c khi áp

d ng bi n pháp domain adaptation (thích ng mi

nâng cao hi u qu phân lo i

d li u thu c các mi n khác.

Hình 2.1: K t qu s d ng domain adaptation gi a các mi n d li u, [1]

6


K t qu cho th y các b phân l

c xây d

c máy ch

cho k t qu phân lo i t t trên mi n d li


c hu n luy n (trên 80%), khi

áp d ng sang t p d li u thu c các mi n khác thì k t qu
r t th p (ch

chính xác

t 70.8% khi phân lo i d li u mi n electronics b ng b hu n luy n

thu c mi n books). Ngoài ra, cịn có s phân nhóm gi a các mi n d li u, d li u
thu c các mi n kitchen appliances và electronics khá gi ng nhau nên cùng thu c
m

t qu

cv i

ng h p K->E và E-

u

chính xác cao.
Tóm l i, các b phân l

c xây d

phân lo i t t trên mi n d li

c máy ch cho k t qu

c hu n luy n, khi áp d ng sang t p d li u

thu c các mi n khác thì k t qu
qu thì t p hu n luy

chính xác r t th p.

nâng cao hi u

i ph i ch a d li u t nhi u mi n khác nhau. Tuy

nhiên, vi c thu th p và g n nhãn các d li u c n thi t cho t p hu n luy n là m t
công vi c r t t n th i gian, cơng s c và chi phí. D

t

ng gi i quy t m i

cross-domain classification, xây d ng m t b phân l p có kh
i các t p d

li u thu c nhi u mi

adaptation là m t trong s

2.3.

ng ti p c n chính.

Domain Adaptation


Nhu c u c n thi t c a domain adaptation phát sinh trong nhi u bài toán phân lo i
th c t , khi có s khơng phù h p v phân b d li u gi a mi n ki m tra và mi n
hu n luy n. M c tiêu c a domain adaptation là xây d ng m t b phân l p v ng
ch c (robust) b ng cách làm gi m s khác bi t gi a các mi n d li u.

ta s

xem xét m t s cơng trình nghiên c u tiêu bi u v
phân lo

c

n theo c m xúc.

Blitzer et al. [1] áp d ng gi i thu t structural correspondence learning (SCL) v i các
c c th

:

a. T t p d li
c gán nhãn

c gán nhãn t mi n d li u g c và các d li
c hai mi n d li u g c và d li

tính m u ch t (pivot features) xu t hi

7


ng xuyên

n ra m t s
c hai mi n d li u.

c


b. D

c tính m u ch t này xây d ng m t projection matrix có kh
tn

c tính mi n d li

c tính (feature

space) c a mi n d li u g c.
c. S d

c tính này, b phân l p hu n luy

c k t qu t t

c có th

t

c hai mi n d li u.


K t qu phân lo i c a gi i thu t SCL ph thu c nhi u vào cách ch n các pivot
m m r ng c a gi i thu
c phân lo

c áp d ng vào

n theo c m xúc. Trong nghiên c u này, các pivot features

c ch n theo các cách sau:
D a trên t n s xu t hi n c a t (cách ch n theo gi i thu t SCL). Các t xu t
hi

ng xuyên

D a trên t n s

c hai mi n d li u s

xu t hi n c a t

c ch n làm pivot features.
ng thơng tin

(mutual

information) c a nó v i các nhãn g c. Các t xu t hi
hai mi n d li

ng xuyên


c

c là các ng c viên, t

cao nh t v i các nhãn g c s

c ch n làm pivot features (ký hi u cách

ch n này là SCL-MI).
, Pan et al. [8]

t gi i pháp t ng quát cho v

domain

adaptation s d ng gi i thu t spectral feature alignment (SFA), g
a. Ch n l c các t

c l p mi n (domain-indepenent) và các t ph thu c mi n

(domainlà t

c:

hai t p d li u g c và t p d li
ng tình c

mi n là t

.T


c l p mi n

trên nhi u mi n d li u, t ph thu c

ng tình c

i tùy theo ng c nh. Các t

cl p

mi n gi vai trò là các pivot features.
b. Xây d ng m

th

i m i quan h gi

nh d a vào m t s
c. D a vào các t

c xác

n s xu t hi n cùng nhau.

c l p mi n, s d ng gi i thu

liên k t các t ph

thu c mi n t hai mi n khác nhau thành các c m th ng nh t. Các c m này có

th

rút ng n s khác bi t gi a các t ph thu c mi n gi a hai

8


mi n d li

n nâng cao hi u qu vi c hu n luy n b phân

l p trên mi n d li
Vi c l a ch

c l p mi

c ti n hành theo m t s

D a trên t n s xu t hi n c a t trong c hai mi n d li u (SFAFQ).
D

gi a t v i nhãn c a mi n d li u g c (SFAMI).

D

gi a t v i mi n d li u (SFADI). T
cao là t ph thu c mi

C


c l i là t

ng

c l p mi n.

u ch s d ng d li u t m t mi n d li u g
xây d ng b phân l p phân lo i cho d li

c

c gán nhãn thu c

m t mi n khác.
V i

ng d li u t nhi u mi n khác nhau có th h tr l

b phân l
b t

t o nên m t

n, Bollegala et al. [2] s d ng k thu t feature expansion

n các t

t o

ng c m xúc:


T các t p d li

c gán nhãn ho c

li u g c và t p d li

c các mi n d

c gán nhãn thu c mi n d li

n các

lexicon elements là các unigrams và bigrams.
liên quan (relatedness) gi a các lexicon elements và nhóm các
lexicon elements có liên quan v
(thesaurus). B t

t o thành m t b

n này s ch a thông tin v

t

n

liên quan gi a các

lexicon elements trong các mi n d li u d a trên ng c nh mà nó xu t hi n.
B t


m r

c tính khi ti n hành

hu n luy n b phân l p s d ng gi i thu t h i quy logistic L1 regularization.
d ng t t c
t o ra b t

n d a vào s

c tính trong q trình t o b t
ng l n các t p d li

cao hi u qu phân lo i trên mi n d li
phân l
b phân l

K t qu thí nghi

c hu n luy n b i d li u thu c nhi u mi n cho k t qu t
c hu n luy n b i m i mi n d li u riêng l .

9

n và có th
nâng
yb
i



Li và Zong [4]
khác nhau

k t h p t p d li u t nhi u mi n

xây d ng b phân l

n: Feature-level fusion và Classifier-

level fusion.
Feature-level fusion: k t h
t

c tính t các mi n khác nhau thành m t

c tính th ng nh t

hu n luy n m t b phân l p.

Classifier-level fusion: v i m i mi n d li u xây d ng m t b phân riêng
bi t

Hình 2.2

t h p các b phân l p này

t o ra m t b phân l p

n.


ng ti p c n Feature-level fusion và Classifier-level fusion, [4]

Th c nghi m cho th y

ng ti p c n classifier-level fusion cho k t qu t

v i feature-level fusion và các b phân l
ng ti p c n Classifier-level fusion, ta có th d
d li u mà gán tr ng s

so

n riêng bi t c a m i mi n. V i
liên quan gi a các mi n

phân l p thu c các mi n có d li

v i d li u thu c mi n c n phân lo i.
Tóm l i, các nghiên c
v

cross-

cm

gi i quy t

ó là domain adaptation, d a trên vi c chuy n


i cách bi u di n d li u c a mi n d li u g c và mi n d li
gi m s khác bi t gi a các mi n d li

m làm
iv i

10


Vi c

c tính

ng c

li u g c và mi n d li

gi a mi n d

làm các pivot features.

D a trên m i quan h gi a các pivot features và
mi n d li u

c tính khác c a các

làm gi m s khác nhau v phân b d li u c a các mi n.

Hi u qu c a vi c phân l p ph thu c nhi u vào vi c l a các pivot features.
tính


c

c ch n ph i là các t khóa có vai trị quan tr ng trong vi c phân lo

b n,

a các mi n d li u, nên chúng ph i là các t
ng c m xúc

c l p mi n.

Trong nghiên c u c a Blitzer et al. [1] và Pan et al. [8], các pivot features

c

ch n có ph n ph thu c vào kinh nghi m (heuristically).
n d a trên t n s xu t hi
thích h p v i bài tốn phân lo
ph n l n là t khơng ma

ng xuyên c a t không

n theo c m xúc. Các t
ng c m xúc.

nd
li u g

gi a t v i nhãn c a mi n d

c các t

b

c ch n

ng c

m

c l p mi n.
n d

gi a t v i mi n d li u,

không ph i t t c các t
thu c mi

u có th

c m t cách rõ ràng là ph

c l p mi n.

2.4.
G

, cross-domain classification là v

n ib


b n theo c m xúc. Nhìn chung các nghiên c

c phân lo
c m t gi i pháp t ng quát,

t qu phân l p ph thu c khá nhi u vào vi c
nh các t

c l p mi n làm các pivot feature.

N i dung nghiên c u c

tài là tìm hi u và hi n th c m t b phân l p có th

phân lo i các ph n h i thu c nhi u mi n d li u khác nhau, s d ng k thu t nh n
d ng các t khoá phân lo

c l p mi n (domain-independent keywords) d a trên

ch s DeltaTFIDF.
11


Thu th p và gán nhãn các ph n h i v nh ng ch
li u khác nhau (gi s
nh t khóa
T

thu c nhi u mi n d

p d li u hu n luy n.

c l p mi n và t khóa ph thu c mi n t t p hu n luy n.

c l p mi n là t

ng tình c

mi n d li u. T khóa ph thu c mi n là t

t c các
ng tình c

i

theo ng c nh.
D a vào m i quan h gi a các t
(ví d

c l p mi n v i các t

a trên t n s xu t hi n cùng nhau)

ng tình c
Bi

n

nh các t mang xu
thu c t p hu n luy n.


n thành các feature vector,

ti n hành hu n luy n b

phân l p.
Áp d ng b phân l p h
m t ch

,m

ti n hành phân lo i cho các ph n h i v
ng m i (E)

12

c gán nhãn.


:
lý thuy t c a m t s k thu
quá trình th c hi

3.1.

c s d ng trong

tài.

Support Vector Machine (SVM)


SVM là b phân l p d a trên lý thuy t h c th ng kê, do Vladimir Vapnik
ng
li u là

n c a SVM là tìm ki m m t hyperland (siêu ph

.

phân chia d

m trong không gian nhi u chi u vào các l p phân ho ch khác nhau.

m m u ch

m b o sao cho margin (l ), kho ng cách t

n các

phân ho ch là l n nh t.
Ví d v i bài tốn phân lo i hai l p: c
m trong không gian, m
m
thu c vào m t l p v i ký hi
ng là
ho c .
phân l
m
trên, ta có th dùng nhi
ng th ng L1,

u có th phân lo i t t các m thành hai l p riêng bi t.

, [7] trang 112.

Hình

Tuy nhiên v
phân l
c s là cách phân l p t
Ví d
ng th ng w.x - b = 0,
m
thành hai l p phân ho ch riêng bi t v i kho ng cách t
ng th
mg n
nh t là l n nh t.

13


Hình 3.2

, [7] trang 113.

Gi i thu t tìm hyperland t
i Vladimir Vapnik
1963 là m t b phân l p tuy
Isabelle
Guyon và Vapnik
ngh m

t o ra các b phân l p phi tuy n
b ng cách s d
bi
i các d li
u vào (khơng kh tách
r i tuy n tính) sang m t khơng gian có s chi u l n
, mà
li u này
tr nên có th tách r i tuy n tính.
Có b n hàm kernel thơng d ng là: Linear kernel, Polynomial kernel, Radial basis
function (RBF) kernel và Sigmoid kernel
ngh s d ng cho h u h
ng h p b i vì:
Linear kernel khơng gi i quy
r i tuy n tính.
V i m t s thơng s nh

ng h p các d li u là không kh tách

nh, sigmoid và RBF x lý gi ng nhau.

Polynomial kernel có s siêu tham s (hyperparameters) nhi
c l a ch n mô hình (model selection)
Tuy nhiên, trong
ng h p s
m (feature) là r t l n, ta không c n
chuy
i d li u sang khơng gian có s chi u nhi
c dùng linear kernel
t t và ta ch c n tìm giá tr t

C nên th i gian x lý nhanh
.
Gi i thu t SVM là m t trong nh ng cách xây d ng b phân l p v
chính xác
c phân lo
n, c phân lo i theo ch d và phân lo i theo
c
u này
c ch ng minh qua m t s cơng trình c a Pang et al. [10],
Paltoglou và Thelwall [12], ...
14


áp d ng SVM vào bài toán phân lo
d ng các vector nhi u chi
i chi u c
t
chi u c a vector là r t l n, vi
và t n nhi u th i gian tính tốn các tr ng s .
Vì v

c bi u di
i
ng v i m t t
u

u qu s d ng SVM, ta c n tìm cách rút ng n s chi u c a không
u này có th th c hi n b ng cách áp d ng các bi n pháp ti n x lý
n.


3.2.

Ti n x

n

t hi u qu cao trong quá trình phân tích t ng , ta c n ti
lý

c ti n x

n nh m làm gi m s t

li u trong bi u di

cd

b n.
ng bao g m các

Xóa b t

c sau:

a (Stop-word removal):

V i ngơn ng t nhiên, ngồi ph n n
khơng mang nhi

ng có các t


m t phân lo i n i dung. Ví d trong ti ng Anh có

nhi u t ch

ph c v cho vi c bi u di n c u trúc ch không bi

dung c

a

the

m t s tr ng t và tính t

in

but

ng t ph bi n có d

c bi

stop-word s khơng

tn i

to

be


c xem t stop-word. Vi c lo i b các
n công vi c phân lo i

c bi t, trong bài toán phân lo

n.

m xúc, ta ch c n t p trung xét các t

ng tình c m. Theo Taboada et al. [13], các t này là tính t , tr ng t ,
danh t
tagging

ng t . Vì v y, ta có th d a vào vi
lo i b các t

u t lo i (Part-Of-Speech

ng c m xúc ra kh

n.

Rút g n d ng t (Stemming ho c Lemmatization):
a, các t ti ng Anh khi s d ng

nh ng hoàn c nh khác nhau thì có th

c vi t b ng nhi u


ng t
, thì hi n t i,

was

were

d ng b

c vi t khác nhau
Ví d

t ngu n t m t t g c là be

d ng g c c a nó s làm gi m s t c n phân tích mà v n khơng
dung

n.
15

are

thì
is

c thu g n các t v
nn i


X lý c m t ph

Ngoài ra, v

nh
c phân lo

n theo c m xúc, các c m t ph
ng,

Vì v y, vi
h p t ph

nh trong

n k t qu phân lo i c

nh các c m t ph

tv

c

n.

c quan tâm.

ra m
nh các c m t ph
nh và các t li n k v i nó, d a vào m t s m

nh là k t


<Verb> - <Negative Particle> - <Verb>:
<Verb> - <Negative Particle> - <Adverb> - <Adjective>: be not happy, be
not very impressed, be not as good
K t qu cho th

3.3.

chính xác c a b phân l

Bi

n

ng mơ hình trên.

Vector Space Model

có th xây d ng b phân l p s d ng SVM, các
x

c và bi u di n

n c n phân lo i ph

d ng toán h c mà máy tính có th hi

u qu

c


c.

bi u di n các tài li u là s d ng Vector Space Model

(Mơ hình khơng gian Vector). M i câu nh n xét s

c bi

i thành m t vector

s nhi u chi u

< label> là m t giá tr

ng v i l p phân lo i, ví d

ng

h p c a chúng ta < label> = 1 (positive) và < label> = -1 (negative)
< index> :< value> là m t c p giá tr
< index> là giá tr s th t
nh m

ch

ng cho m i t trong câu, v i
nt

< value> là giá tr nh m xác


quan tr ng c a t

i c a câu.

TFIDF (Term Frequency - Inverse Document Frequency):
ng, giá tr <value>
quan tr ng c a m t t t

iv

ng dùng là tr ng s TFIDF, th hi n s
n d trong m t t

tfidf (t , d , D) tf (t , d ) idf (t , D)
16

n D.
(1)

c


TF (Term Frequency):
G i f (t , d ) là s l n xu t hi n c a t t

n d, tf (t, d ) có th

c tính


b ng m t s
tf (t , d )

Raw frequency

tf (t , d )

Boolean frequency

f (t , d )

(2.1)

1, if f (t , d ) 0
0, otherwise

tf (t , d ) log( f (t , d ) 1)

Logarithmically scaled frequency

tf (t , d ) 0.5

Augmented frequency

(2.2)

(2.3)

0.5 f (t , d )
max f ( w, d ) : w d


(2.4)

B ng 3.1: M t s cơng th c tính TF
Theo Pang et al. [10], vi c s d ng Boolean frequency s cho k t qu phân lo i v i
t qu t t v
phân lo i ch
qu

c

i v i phân lo i câu bình lu n k t

cl

chính xác khơng cao.

IDF (Inverse Document Frequency):
V i D là t ng s

n, Dt

d

D:t

idf (t , D) log

Giá tr IDF c a m t t cho bi t t


d là s

D
Dt

n có ch a t t:

(3)

t hi

n

hay khơng.
M t t có giá tr IDF càng th
trong t p
N
t

càng xu t hi

ng xuyên

n.

c l i giá tr IDF c a t

l n thì t

n.


17

m xu t hi n trong


3.4.

DeltaTFIDF

Tr ng s TFIDF cho k t qu khá t t v i phân lo
tuy nhiên v i phân lo

n truy n th ng theo ch

b n theo c

nh các t

,
ng

tình c m, ta có th s d ng m t cách tính tr ng s khác t
DeltaTFIDF do Martineau và Finin [5]

ng chính là s d ng ch s idf

vào vi c phân lo i các câu bình lu n. T p d li u hu n luy n s

c chia làm hai:


t p tích c c P và t p tiêu c c N ; tính giá tr c c b idf (t , P ) và idf (t , N)

y

hi u c a hai giá tr này.
(t , d ) tf (t , d ) *(idf (t , P ) idf (t , N ))
P

tf (t , d ) * log

Pt
P
Pt

tf (t , d ) *log

V

log

N

(4)

Nt

Nt
N


u DeltaTFIDF c a m t t có giá tr l
thì t

hi

ít xu t hi

ng xuyên

tiêu c

ng

n thu c t p tích c c và xu t

n thu c t p tiêu c

này mang xu h

c l i, n u DeltaTFIDF c a m t t có giá tr nh
thì t

xu t hi

xu t hi n

ng xuyên

ng âm


n thu c t p tích c c và ít

n thu c t p tiêu c

Các giá tr

ng

ng tiêu c c.

ng âm trên s

u ch nh sao

cho thích h p v i t ng t p d li u c th .
M t t có t n s xu t hi n g n

c t p tích c c và t p tiêu c c s có giá

tr DeltaTFIDF g n b ng 0

này khơng mang xu

quan tr ng cho vi c phân lo
có giá tr tuy

ng c m xúc, khơng

n. Tóm l i, các t


ng c m xúc s

i c a DeltaTFIDF l n, bi u di n cho s quan tr ng c a chúng

trong quá trình phân lo i.
Tuy nhiên, v i công th

n Martineau và Finin

ng h p m t t ch xu t hi n
l i trong vi c tính tốn IDF.

t p tích c c ho c t p tiêu c c,

gi i quy t v

t s công th c m i
18

d

n

này, Paltoglou và Thelwall [12]