--------------------

TRÊN CÁC TRANG FACEBOOK FANPAGE

Chuyên ngành :
60.48.01

11

2013


-HCM

...........................................................................

...........................................................................

HCM ngày 25 tháng 12

Tr
2013

ng

i h c Bách Khoa, HQG Tp.

Thành ph n H i ng nh giá lu n v n th c s g m:
(Ghi
c a H i ng ch m b o v lu n v n th c
s)

1. ..............................................................
2. ..............................................................
3. ..............................................................
4. ..............................................................
5. ..............................................................
Xác nh n c a Ch t ch H i ng
chuyên ngành sau khi lu n v n ã

h giá LV và
c s a ch a (n u có).
KHOA

ii

lý


NAM

-

-

KHOA

..................... MSHV: 11070441 .................
04/06/1979 ...............................

KHÁNH HÒA .........


.......................

: 60.48.01 ...................

Chuyên ngành:
I.

FANPAGE ......................................................................................................................
II.

P
...........................................................................

.............................................................................................................................................
III.

: 21/01/2013 ................................................................

IV.

: 22/11/2013..................................................

V.

:

........................................

.............................................................................................................................................


Tp. HCM, ng

iii

20....


iv


m

v


ABSTRACT
In recent years, social network has changed completely the connection
method among netizens and become an essential part of the daily lives of
billions of people around the world. The continuous growth of social network
has made the process of finding useful information become difficult, and it also
motivates the research of data mining on social network environment more
powerful. One of the research directions in this field is data mining on social
networks to advise users with useful, quick and accurate data.
Within the scope of this thesis, we researched on classic methods in data
mining, assessment methods, user classification in the social network. After
that, we proposed a method of combining between fanpage content
for advising people to suitable fanpages.

vi



.

vii


.................................................................................................................... iv
..................................................................................................... v
ABSTRACT ....................................................................................................................... vi
............................................................................................................. vii
....................................................................................................................... viii
......................................................................................................... x
........................................................................................................... xi
............................................................................................... 12
1.1
.................................................................................................... 12
1.2
.............................................................................. 13
1.3
.................................................................................................... 14
................................................................................. 16
2.1
.............................................................. 16
2.2
................................................................................. 17
2.2.1
................................................................................... 17
2.2.2

....................................................................................... 18


2.3
2.3.1

................................................................................... 19
............................................................................................. 19

2.3.2

-means ............................................................................................ 19

2.4
2.5
3.1
3.1.1

.............................. 25
....................................................................................... 25
........................................................... 27
........................................................................................... 27
Vector space model ............................................................................................ 27

3.1.2

..................................................................... 28

3.1.3

..................................................................................... 28


3.2
3.2.1

............................................................................................ 29
........................................ 30

3.2.2

..................................................................................... 31

3.3
3.4

............................................................................................. 32
Social Lens ............................................................................................................. 33

4.1
4.2
4.3
4.3.1

....................................................................................................... 35
...................................................................................................... 35
............................................................................. 36
.................................................................................. 37
................................................................................................ 37

4.3.2

.................................................................................................. 40

viii


4.4
4.4.1

...................................................................................... 40
.............................................................. 40

4.4.2

..................................................................... 41

4.5
4.5.1

...................................................................................................... 42
.............................................................. 42

4.5.2

.............................................. 42

4.6
4.7
5.1
5.1.1

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

.................................................... 44
.................................................................................................... 44
............................................................. 44

a.

............................................................................ 44

b.

...................................................................................................... 51

c.

............................................................................................... 54

5.1.2 Ph

............................................................................. 54

a.

........................................................................... 55

b.

............................................................................................... 55
:

1.


...................................................................... 56
........................................................................................ 56
........................................................................... 58
................................................................................................. 59
7:
................................................................................................ 65
.................................................................................................................. 65
..................................................................................................... 66
................................................................................................ 68
........................................................................................................................ 69
...................................................................................................... 69

2.

................................................................... 72

3.

................................ 75

4.

.............................................................................. 76

6.1
6.2
6.3
7.1
7.2


ix


D
.......................................................................................... 39
-strength ........................................................................................... 39

x


D
-means ..................................................................................... 20
.............................................................................. 29
................................................................... 34
................................ 34
..................................................................... 40
.................................................. 41
......... 42
....................................................................................... 44
.................................. 45
............................................................ 45
.............................. 46
..................................................................... 47
..................................................... 47
........................................................................ 48
............................................................ 48
............................................................. 49
.............................................................................. 49
............................................................ 50

................................................................. 50
................................................................... 51
.......................................................................................... 59
.......................................................................................... 60
.......................................................................................... 61
.......................................................................................... 62
.......................................................................................... 63

xi


1 : T ng quan

1.1 Lý do ch

tài

Trong nh

ng xã h

i m i hoàn toàn cách

ng liên k t v i nhau và tr thành m t ph n trong cu c s ng hàng
ngày c a hàng t
Hi n nay, th

i trên th gi i.
gi


ng m ng xã h i khác nhau, v i

MySpace và Facebook n i ti ng nh t trong th

ng B c M và Tây Âu;

Orkut và Hi5 t i Nam M ; Friendster t
D

o qu c Thái Bình

ng xã h i khác g

theo vùng mi n

i Anh Qu c, CyWorld t i Hàn Qu c, Mixi t i Nh t B n và t i Vi t
Nam xu t hi n r t nhi u các m ng xã h
c ngo t m i cho h th ng
m ng xã h i tr c tuy n v i nhi
g

t tr i. Facebook nhanh chóng

t b c, s

m ng xã h

thành

u th gi i hi


n cu i tháng 11/2011, s

ng

m 55.1% t ng s thành viên các
m ng xã h i (ngu n ).
S phát tri n không ng ng c a m ng xã h
d li

y các nghiên c u khai thác

ng này ngày càng m nh m .
ng bao g m s k t h p c a các d

li

ng nh t. Khai phá d li

ng g i là khai

phá d li u web ngoài vi c c n khai thác n

n, các nghiên c u còn

khai thác các m i quan h gi a chúng và cách th
chúng. Khai phá d li
c nghiên c

i s d ng


n m nh m bao g m r t nhi u
nhân t o, truy xu t thông tin, th ng kê và tiên
truy xu t thông tin d a trên n i dung, truy xu t thơng

tin s d ng, tính h ng trang web d

ng

c nh trong khai phá web. Khai phá web v n còn là
12


1 : T ng quan
m

ng m và liên t

c phát tri n. Tuy v y, ta có th hi u khai

c trích ra các thành ph
có ích cùng các thơng tin ti

các tài nguyên ho c các ho

ng liên

quan t i world-wide-web.
v c: khai phá n i dung web, khai phá c u trúc web và khai phá s d ng web.
c thù riêng, m ng xã h i mang

n cho vi c khai phá d li u nhi
n mv

i và thách th c m i. Ngoài yêu c u

v lý thuy t khai phá d li u, phân c m tài li u, phân tích các
li u truy n th ng, khai phá d li u

trên m ng xã h i còn yêu c u x lý tài li

c vi t m t cách khơng chính

th ng (pha tr n nhi u ngôn ng , vi t t t, vi t sai chính t

c bi u

di n b ng cách ph i h p nhi u ki u d li
clip, siêu liên k

nh nh

li u

ng m ng xã h
các c

, hình nh,

ra nhi u ng d ng m


p

ng chung s thích, qu

tìm hi u m

ng d li u m i, nhi u ti

ph c v c

n ng d ng

ng, chúng tôi ti n hành nghiên c

khai th c nghi m h th

hát tri n và tri n

n các trang facebook

fanpage phù h p d a trên nhu c u v n i dung và s

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

tài

ng truy c

tài


c thù c a m ng xã h i, vi c khai phá liên k t web và khai phá s
d

ng d ng không có quy n truy c p sâu vào
d li u c

c a mình

ng khơng thi t l p trang cá nhân

tr ng thái cơng khai hồn tồn (public).

Vì v y, m c tiêu c a nghiên c u này là
ng ti p c n cho vi c khai thác d li

lý thuy t và
ng m ng xã h i, t p

trung vào khai thác n i dung web và k t h p m t s thông tin liên k t web thu
thu th

c, cùng v

i dùng lên h th

13

cung c p



1 : T ng quan
k t qu tìm ki
v

i dùng. Qua

ng và th nghi m h th

n các trang facebook fanpage phù h p.
Trong ph

thu th

tài này, chúng tôi t p trung nghiên c u và x lý d li u
c trên ngôn ng ti ng anh (các ngôn ng khác s

c lo i b

trong quá trình x lý d li u).

1.3 C u trúc lu
V im

t ra là kh o sát, nghiên c u và tri n khai th c

nghi m h th

i dùng

h p d a trên nhu c u v n i dung và s

c chia thành 7

n các trang facebook fanpage phù
ng truy c p. N i dung lu

ic

.Q
tài.

.

Trong c

, chúng tôi
.
. Chúng tôi

14


1 : T ng quan

.

5.
6:
,

7:


g ng r t nhi
do kinh nghi

lu

u ki n nghiên c

t k t qu t t nh t. Tuy nhiên,
i gian ng n nên nh ng sai

u không th tránh kh i. Chúng tôi xin chân thành c
ti p thu t t c nh ng ý ki

a q th y cơ và b

c hồn thi

15

tr ng
lu


2 :

2.1

lýthuy t


c c a quá trình phát hi n tri th c
V

n, quá trình phát hi n tri th

T p h p d li

c quy v

c chính:

u tiên trong quá trình khai phá d li

c khai thác t các ngu n d li
ngu n ng d

d li u, kho d li u, các

.

n này d li
chu

c l a ch

phân chia theo m t s tiêu

cv m

c r t quan tr ng trong quá trình khai phá d li u. D li u thu

ng t n t i các ph n t khơng có tính logic, ch a các giá tr vơ
t o ra tri th c (ví d v n t

p là 320km/gi ).

c này s ti n hành x lý nh ng d ng d li u không ch t ch nói trên.
Nh ng d li u lo

.B iv

là m t quá trình r t quan tr ng vì d li u này n
gây nên nh ng sai l ch k t qu

cx

c thì s

c sau.

Chu
n chuy

i d li u, d li u

c t ch c l i và s

c chuy n

i v d ng phù h p, s n sàng cho vi c khai phá tri th c.


c quan tr ng, quy
d li u.

c này,

toán khác nhau s

nh s khác bi t gi a các h th ng khai phá
c thù c a ng d ng khai phá d li u, các thu t
ph c v cho vi c rút trích tri th c.

16


2 :

n này các m u d li
Không ph i t t c các m u d li

lýthuy t

c rút ra b i thu t toán khai phá d li u.
u

i u c u

khi nó cịn b sai l ch. Vì v y, c n ph i có các tiêu chu
ra các tri th c c n thi t. Ví d

n cung c p m


h u ích c a các m u tri th c
cách tr c quan hóa

rút trích

c

ánh giá s

tri th c s

c bi u di n m t

i s d ng.

2.2 Các k thu t khai phá d li u
2.2.1 Khai phá d li u d
Khai phá d li u là quá trình rút ra các lu t, các d
hi n th i. Nó d a vào các thơng tin có s n
giá tr khơng bi t hay các giá tr

a trên d li u
d li

d

m các k thu t phân lo i

(classification), h i quy (regression).

o

Phân lo i:
P

q trình gán

.
:

.
Mơ hình
.P

.

:

Phân lo i có th coi là m t hàm ánh x m t m c d li u vào m t trong các
l

c.
17


2 :
o

lýthuy t


H i quy:
N u phân lo

d

d

tr r i r c c a thu c tính l p thì h i

các giá tr liên t c. H i quy là m t hàm ánh x m t

m c d li u vào m t bi n d báo giá tr th c.

2.2.2 Khai phá d li u mô t
Các k thu t này có nhi m v mơ t v các tính ch t ho
chung c a d li u trong

c tính

d li u hi n có. Bao g m các k thu t phân c m,

phân tích lu t k t h p.
o

Phân c m:
Phân c m là quá trình phân lo
cho cá

ng vào các c m khác nhau sao


ng trong cùng m t c m thì

thu c khác c m s

ng

ng. Phân c m d li u là m t ví d c a

c khơng giám sát. Không gi
c m d li

i d li u, phân

i ph

c các m u d li u hu n luy n.

, k t qu các c
Phân c m d li

c bi

c.

c s d ng trong các ng d ng v phân tích th

ng,

khách hàng, nh n d ng m u, phân lo i
cịn có th


ng

cs d

cs

n

m d li u

c ti n x lý cho các thu t toán khai phá

d li u khác.
o

Lu t k t h p:
P

lu t k t h

các giá tr d li u trong
li u là t p lu t k t h

phát hi n và tìm ra các m i liên h gi a
d li u. K t qu

u ra c a gi i thu t khai phá d

c. Khai phá lu t k t h


c:

18

c th c hi n qua 2


2 :

2.3

lýthuy t

Các thu t toán x lý d li u

2.3.1 Ti n x

n

Ti n x
li

u tiên trong quá trình rút trích tri th c t d

b

t s c quan tr ng trong q trình rút trích

tri th c ti p theo. Ti n x


n giúp gi

quá trình x lý, phân nhóm và tìm ki

c d li

c

n.

-words
Stop-

-

-

-

các

2.3.2 Thu t tốn k-means
Phân c m là k thu t r t quan tr ng trong khai phá d li u, nó thu c l p
c khơng giám sát trong Machine Learning. Có nhi
k thu

nh

b n ch t ta có th hi u phân c m là

ng vào các c

trong cùng m t c

ng
ng khác c

t nhau.
19


2 :
M

lýthuy t

a phân c m là tìm ra b n ch t bên trong c a các c m d li u.

Các thu t toán phân c

u sinh ra các c m. Tuy nhiên khơng có tiêu chí nào

c xem là t t nh
ph thu c vào m

u qu c a thu t toán phân c

u này

c a vi c phân c m.

-Means

K-Means là thu t toán quan tr ng và ph bi n b c nh t trong k thu t phân
c

ng chính c a thu t tốn k-

i

m (k là s c

c và k là s nguyên
ng cách gi

nhóm là nh nh t.
Thu t tốn k-

c mơ t

sau:

Hình 1

-means

Ví d minh h a:

20

n tâm



2 :

c1

2

21

lýthuy t


2 :

d(C, c1) =

(4 1)2 (3 1)2

= 13

d(C, c2) =

(4 2)2 (3 1)2

=8

d(C, c1) > d(C, c2
d(D, c1) =


(5 1)2 (4 1)2

= 25

d(D, c2) =

(5 2)2 (4 1)2

= 18

d(D,c1) > d(D, c2)

1
2

(x,y) =

-1:

)

c2

d(A, c1 ) = 0 <

d(A, c2 ) = 9.89

d(B, c1 ) = 1 <

d(B, c2 ) = 5.56


d(C, c1 ) = 13

>

d(C, c2 ) = 0.22

d(D, c1 ) = 25

>

d(D, c2 ) = 3.56

-2:

22

lýthuy t


2 :
c1 = (3/2, 1) và c2 = (9/2, 7/2)

-3:
d(A, c1 ) = 0.25

<

d(A, c2 ) = 18.5


=>

d(B, c1 ) = 0.25

<

d(B, c2 ) = 12.5

=>

d(C, c1 ) = 10.25

<

d(C, c2 ) = 0.5

=>

d(D, c1 ) = 21.25

>

d(D, c2 ) = 0.5

=>

t toán:
m:
23


C

lýthuy t


2 :

lýthuy t

ph c t p: O(K.N.l) v i l: s l n l p.
Có kh

r ng, có th d dàng s

i v i nh ng d li u

m i.
B

m h i t sau m t s

c l p h u h n.

Ln có K c m d li u.
Ln có ít nh t m

m d li u trong m t c m d li u.

Các c m không phân c p và không b ch ng chéo d li u lên
nhau.

M i thành viên c a m t c m là g n v i chính c

t

c 1 c m nào khác.
m:
Khơng có kh

ác c m khơng l i ho c các c m có

hình d ng ph c t p.
nh các tr ng tâm c

u

o Ch n ng u nhiên các trung tâm c m lúc kh i t o.
h i t c a thu t toán ph thu c vào vi c kh i t o các

o

vector trung tâm c m.
ch

cs

qua nhi u l n th

ng c m t
cs


u, mà ph i
ng c m t

R t nh y c m v i nhi u và các ph n t ngo i lai trong d li u.
Không ph i lúc nào m
ch phù h p v

thu c v m t c m,

ng biên gi a các c m rõ.

ng K,l << N nên thu t toán k-means khá hi u qu
s d li u l n. V

iv

d li u là hàng tri u facebook fanpage, vi c áp d ng

thu t toán k-means s giúp làm gi m khơng gian bài tốn cho nh
lý ti p theo.

24

cx


2 :

lýthuy t


2.4 Nh ng thách th c c a vi c khai phá d li u trên m ng xã h i
o

c thay

o

o

o

o

p

2.5

ng ti p c n c

tài

Cùng v i s phát tri n c a các trang cá nhân trên m ng xã h i facebook,
các fanpage g

n r t nhanh và d n thay th các di

thu n túy. Bên c nh vi c cung c
i

i dùng nh ng thơng tin h u ích và


k t b n v i nh

i cùng s thích, s

tri n quá nhanh l
phù h p.

ng fanpage phát

i dùng trong vi c l a ch n fanpage

i dùng g

p trong m

g i ý b i facebook. Nh n th

cs

ng fanpage l

c

i dùng chúng tôi

nghiên c u xây d ng h th ng g i ý facebook fanpage theo tiêu chí c a
i dùng v

ng ti p c n m i bao g m thu th p, chu n hóa d li u, phân


c m d li u, k t h p thông tin th
th

m hi n t i. Nh

nh n ra ch

c a t ng fanpage t i

, h th ng có th g i ý

i dùng nh ng

fanpage phù h p nh t.

25