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

PH M MINH NGH

NH N DI
I D A TRÊN HÀNH VI
DI CHUY N KHÔNG TH I GIAN

Chuyên ngành: Khoa H c Máy Tính
Mã s : 60.48.01

LU N

TP. H


c hoàn thành t i:
Cán b

i H c Bách Khoa

-HCM

ng d n khoa h c: PGS.TS. Cao Hoàng Tr ........................

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

Cán b ch m nh n xét 2: ........................................................................

Lu

cb ov t

ngày ..24.. tháng . .07

2013. .

Thành ph n H
1. TS. Ph m Tr

iH

m:
............................................................

2. TS. Lê Thanh Vân............................................................
3. TS. Nguy n Tu n Nam.....................................................
4. TS. Võ Th Ng c Châu.....................................................
5. PGS.TS Cao Hoàng Tr ...................................................
Xác nh n c a Ch t ch H i
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


I H C QU C GIA TP.HCM

I H C BÁCH KHOA

C NG HÒA XÃ H I CH
c l p -T do -H nh phúc

T NAM

NHI M V LU

H và tên h c viên: PH M MINH NGH ........................... MSHV: 11070462.................
11/04/1985 .......................................

TP. HCM .............

Chuyên ngành: KHOA H C MÁY TÍNH .......................... Mã s : 604801 ......................

TÀI: NH N DI
I D A TRÊN HÀNH VI DI CHUY N
KHÔNG TH I GIAN
...................................................................................................
..................................................................................................................................................
NHI M V VÀ N I DUNG: ................................................................................................
..................................................................................................................................................
..................................................................................................................................................
..................................................................................................................................................
II. NGÀY GIAO NHI M V : 21/01/2013

..

III. NGÀY HOÀN THÀNH NHI M V : 21/06/2013.

IV. CÁN B

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

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

NG D N: PGS.TS. CAO HOÀNG TR
TP

CÁN B

NG D N

CH NHI M B

13
O


L IC
Tôi xin g i l i c

tôi, nh

i luôn ng h và t o m

u

ki n t t nh t cho vi c h c t p, nghiên c u c a tơi.

Xin chân thành c
th y

n tình ch d n tơi t

Xin chân thành bi
ih
Máy tính.

th y, PGS.TS. Cao Hoàng Tr . Trong su t m
c hoàn thành lu

t n tình gi ng d y và
c a t t c quý th y cô t i
c bi t là các th y cô trong khoa Khoa h c và K thu t


TĨM T T
D u v t v trí c

is d

n tho

ng ch a các thông tin v m t th i

gian và khơng gian c a q trình di chuy n. Nh
c dùng làm tham s cho bài toán nh n di n.
m c tiêu c i ti n
mơ hình Markov dùng

n tho
ng.

c
tài nh m

nh n di n b ng cách thêm y u t th i gian vào
mô ph ng quá trình di chuy n c a m
i s d ng
ng là xây d ng m t mơ hình khơng th i gian
c

cao, có th mơ ph

các tính ch t c a m t quá trình di chuy n xét v

m t không gian và th i gian c a hành vi di chuy n.
Vi c th c nghi
c ti
m
i có th
c
nh n di n thơng qua hành vi di chuy n c a h . K t qu th c nghi m cho th y m t
c nh n di n cao.

SUMMARY
processes. As a result, these traces are among the most sensitive data that could be
exploited to uniquely identify an individual. In this paper, we propose a spatiotemporal mobility model that extends a purely spatial Markov mobility model to
effectively tackle the identification problem. The idea is to incorporate temporal
perspectives of mobility traces into that probabilistic spatial mobility model to make

it more specific for an individual with respect to both of the space and time.
Then we conduct experiments to evaluate the degree to which individuals can be
uniquely identified using our spatio-temporal mobility model. The results show that
the proposed model outperforms the purely spatial one on the benchmark MIT
Reality Mining project dataset.


L
oan r ng, ngo i tr các k t qu tham kh o t các cơng tr
i dung trình bày trong lu
n n i dung nào c a lu

th c hi
m t

cn

l y b ng c p

ng khác.
TP.

3
Ph m Minh Ngh


i

N I DUNG


N I DUNG ................................................................................................................. i
DANH M C HÌNH .................................................................................................. iii
DANH M C B NG ................................................................................................. iv
M
1.1.

U .................................................................................................1
nh bài tốn ...........................................................................................1

1.2. M c tiêu và ph m vi.......................................................................................2
CÁC CƠNG TRÌNH LIÊN QUAN.........................................................4
2.1.

n ...........................................4

2.1.1.

mơ hình b ng q trình ng u nhiên ...................................4

2.1.2.

t k t h p c a các v trí ...................................7

2.2.

n di n ...........................................................................8

2.2.1.

n di n b ng mơ hình Markov ......................................8


2.2.2.

n di n b

i v trí ................11

LÝ THUY T ............................................................................14
3.1. Quá trình ng u nhiên ....................................................................................14
3.2. Quá trình Markov .........................................................................................15
3.3. Mơ hình Markov n......................................................................................16
3.3.1. Xây d ng mơ hình .................................................................................16
3.3.2. Các bài tốn trên mơ hình Markov n. ..................................................17
XU T ................................................................19
4.1. T ng quan ....................................................................................................19
4.2. M r ng mơ hình Markov ............................................................................20
4.2.1. Xây d ng mơ hình .................................................................................20
4.2.2. Thêm y u t th i gian vào mô hình.......................................................23


ii

4.3.

n di n b ng mơ hình Markov n ......................................27

4.3.1. Xây d ng mơ hình .................................................................................27
4.3.2. Nh n di n b ng mơ hình Markov n .....................................................29
4.3.3. Thêm y u t th i gian vào mơ hình.......................................................32
TH C NGHI M ...................................................................................33

5.1. T p d li u ...................................................................................................33
5.2. Th c nghi m và phân tích k t qu ...............................................................35
5.2.1. Th c nghi m v i các th i kho ng ng v i bu i trong ngày .................36
5.2.2. Th c nghi m v i các th i kho ng b t kì ...............................................38
5.2.3. H n ch c

n di n ..............................................41

K T LU N ...........................................................................................46
6.1.

......................................................................................................46

6.2.

ng phát tri n ..........................................................................................46

THAM KH O ..........................................................................................................48


iii

DANH M C HÌNH

Hình 2.1. Bi u di n mơ hình Random Walk trên h tr c t

hai chi u................5

Hình 2.2. Q trình chuy n tr ng thái trong mơ hình Markov. .................................6
Hình 2.3. Chu i v trí c a quá trình di chuy n xét trên m t tr c th i gian .............12

Hình 3.1. Minh h a mơ hình Markov n .................................................................17
Hình 4.1.

ng di chuy n c a m t

n tho

ng trong

m ng GSM ...............................................................................................20
Hình 4.2.

th bi u di n m i liên h gi a các v trí trong q trình di chuy n ....23

Hình 4.3: Xác su

u ra

m t v trí trong q trình di chuy n .......28

Hình 4.4. Mơ hình Markov n bi u di n quá trình di chuy n c a m

ng ...29

Hình 4.5.

c nh n di n d a trên mơ hình Markov n ..................................30

Hình 5.1.


n di n d a trên quá trình di chuy n .............................35

Hình 5.2. Minh h a s ch ng l n ph m vi ph sóng c a các tr m thu/phát sóng ...40
Hình 5.3. M t ví d v gom nhóm các ơ m ng .......................................................41


iv

DANH M C B NG

B ng 2.1. Các ki u m

t c a m t quá trình di chuy n .......................8

B ng 5.1. D li u d ng chu i v trí c a m

ng trong t p d li u Reality

Mining ......................................................................................................34
B ng 5.2. K t qu th c nghi m v i các th i kho ng ng v i bu i trong ngày .......37
B ng 5.3. K t qu th c nghi m v i các th i kho ng b t kì .....................................39
B ng 5.4. Các m

n su

ng ...............................................42

B ng 5.5. M t ph n k t qu th c nghi m c

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


B ng 5.6. M t ph n k t qu th c nghi m c

.........45


1

M

1.1.

U

nh bài toán

n tho

t b truy

m t ph n thi t y u c a cu c s
nên ph bi
nm tm

ang tr nên

i. Vi c s d ng các thi t b
ng này
có th ph
c nh ng hành vi, m i liên


k t xã h i, hay nh
is d
li
ct
n truy n thông này tr thành m t ngu n thông tin giá tr cho vi c
nghiên c

i [6].

M

n tho

u có th

l i d u v t v trí (mobility

traces) c a mình,
là m t trong nh ng lo i thơng tin giá tr và nh y c m nh t có
th thu th
c t m t thi t b d
ng [4]. M t ví d v vi
id uv tc a
n tho i
ng là: khi m t ng i di chuy n trong ph m vi ph sóng
c a m ng GSM, v trí c

i này


trí c a thi t b

ng

i này mang theo) có th
nh thơng qua v trí c a các tr m thu/phát
ng. M t m
ng GSM (Global System for Mobile
Communications) v
n là m t m ng t bào (cellular network) bao ph m t khu
v
a lý nh
nh, khu v
c chia thành các vùng nh
i là các ô
m ng (cell), m i ô m ng
c qu n lý b ng m t tr m thu/phát sóng (base station)
ng. Tùy vào m
ng mà m i ơ m ng có th
ng kính t vài ch c
meter

n vài kilometer

ng c
v trí c a

i dùng di chuy n vào m t ô m ng, thi t b di

nh n bi

i dùng
ct

thu/phát sóng mà thi t b
nghiên c u các chu i v trí

ng c

c tr m thu/phát sóng g n nó nh
y, các
n tho
ng s có d ng m t chu i các tr m
c theo th t th i gian. Vi c
mang l i nhi u ng d
:d
ng

ch giao thông, thi t k và t
ng, v.v
i v trí này
cịn th hi n nh
c tính c a m t q trình di chuy n, giúp nh n di
c i
ng di chuy n

ng.

V b n ch t, quá trình chuy n c a m
ho


i là duy nh

i

y, v i gi s r ng thói quen di chuy n c a m
i khơng
i
i
theo th i gian, quan sát và phân tích d u v t v trí c a

m t q trình di chuy n s giúp nh n di

c

ng di chuy n

ng. C


2

th

ta có th so sánh m t chu i v trí

chu i v trí c a nh ng
ai d a trên s

ct m t


ng

c

ng
ng

tv i
a bi t này là

ng gi a các chu i v trí.

M t h ng ti p c n cho bài toán nh n di n là: xây d ng m t mơ hình tốn h c
có th mơ ph ng
c q trình di chuy
am
i, và t
sánh các mơ hình này v
tìm ra m c
ng gi a chúng. Hai mơ hình di chuy n càng gi ng nhau cho th y chúng
càng có xác su

c sinh ra t cùng m

ng [5].

M t s mơ hình tốn h

mơ ph ng q trình di chuy n c a


i, ví d
Tuy nhiên, trong th c t , các mơ hình này
ng khơng th b o
c m i tính ch t c a m t quá trình di chuy n trong th c t , do quá trình di
chuy n c a m
gian, th i gian

i ph c t p, ch a nhi u y u t
không
o hay v n t c. Ví d v m t s tính ch t có th quan sát
c

khi phân tích m t chu i v trí c
ng
i m t v trí, kho ng th

n tho
iv

ng: th
m i
i gian di chuy n t

m t v trí sang v trí k ti
ùm
i dùng có m t q trình di chuy n
i c khơng ph
t t c nh ng tính ch t trên s
làm gi m tính
duy nh t c a mơ hình, làm

n kh
n
di n d a trên mơ hình.
y, vi c xây d ng
cm
c a
m i
ng di chuy n là m c tiêu quan tr ng trong vi c gi i bài toán nh n di n.

1.2. M c tiêu và ph m vi
M c tiêu c

tài là gi i bài toán nh n di n m

i d a trên hành vi di chuy n

c a h . C th :

mơ hình di chuy n Markov
is d

n tho
các y u t v

chuy n trong th c t .

k t h p y u t th i gian vào q trình xây d ng
mơ ph ng quá trình di chuy n c a m t
ng, giúp mơ hình có kh
mơ ph

c
i gian c a m t quá trình di


3

mơ ph ng q trình di chuy n m i, s
d ng mơ hình Markov n (Hidden Markov Model), và
n
di n d a trên mơ hình này.
tài ti

xu t

khác bi t v hi u qu c
nhau. T
ng t r ng m

n di

cho th y s

i v i các mơ hình khác

nh n di n cao.
xu
trên t p d li u c a d án Reality Mining [6]
n tho
ng trong m ng GSM.
i d li u này.


c xây d ng và ki m nghi m
c t quá trình di chuy n c a
t qu th c nghi m s
c


4

CÁC CƠNG TRÌNH LIÊN QUAN

Vi c nh n di n d a trên quá trình di chuy n g m hai
hình di chuy n và nh n d ng d a trên mơ hình [5]
nghiên c

c chính là: xây d ng mơ
ng

n vi c xây d ng mơ hình mơ ph ng quá trình di chuy n c a
g và nh n di n d a

i

trên mơ hình di chuy n này. Nh ng nghiên c
và mơ hình c i ti n

xu t trong C

2.1.


c
.

phân tích q trình di chuy n

2.1.1.

ng quá trình ng u nhiên

M
c quan tr ng trong bài toán nh n di n d a trên d u v t di chuy n là mơ
hình hóa q trình di chuy n này.
, d u v t v trí c a
q trình di chuy
gian. Nh

ng có d ng m t chu i tu n t các v trí theo th i
cs d
i v i d li u d ng

này g m: mơ hình Random Walk, mơ hình Random Waypoint, mơ hình Markov,
v.v [2].
Mơ hình Random Walk. Mơ hình Random Walk
c gi i thi
quá trình mà s chuy
ng c a nó mang tính ng u nhiên, g

mơ ph ng m t
khơng th


c. Trong mơ hình Random Walk, m t quá trình ng u nhiên s ti n tri n v i các
tham s là

ng ng u nhiên và v n t c ng u nhiên.

Có th hình dung m t mơ hình Random W
th
ng trong
h tr c t
vng góc Oxy
m b t kì trên h tr c là nh kh i
uc am t
th . S
cách gi a nh m i và
nh

nh

n m t nh m i trên h tr c t
sao cho kho ng
u n m trong kho ng [dmin, dmax]
,r in i

nh m i. Ti p t c n i nh m
u di
c hình
Random Walk v i v n t c ng u nhiên m i
c
th
ng ng u nhiên là góc t o b

t

uv i

,

a trong hình 2.1.

i này v i m t nh m i theo cách
nh hai chi u c a m t mơ hình
c ti n tri n là chi u dài c a m t
i các c nh
th v i h tr c


5

Hình 2.1. Bi u di n mơ hình Random Walk trên h tr c t

t

hai chi u

Mơ hình Random Walk v i các thông s phù h p v s ng u nhiên c a
ng và v n t c s giúp bi u di
c các quá trình
c trong
di chuy n c a ch t l ng, s
a ch t khí, s d ch chuy n


c a các phân t
Tuy nhiên, h u h t các quá trình chuy
quanh ta u khơng ph i là hồn tồn ng u nhiên, ví d
di chuy n c
T t c nh ng quá t

s

c hàng ngày xung
i th i ti t, s

n giao thơng trong thành ph , t giá ch ng khốn,
u ph n nào có th d
c. S ti n tri n c a các

quá trình này ph thu c các ràng bu c
u ki n bên ngoài
a trên
l ch s ti n tri n c a chính nó. S ti n tri n c a mơ hình Randon Walk là hồn tồn
ng u nhiên, khơng ph thu c vào m t tri th
Walk khơng
phù h p có th mơ ph
nó b chi ph i b i nh

u ki n ph c t p, ví d

t nào
c các q trình mà s ti n tri n c a
di chuy n c


i.

Mô hình Markov. Là m t mơ hình c i ti n giúp lo i b ph n nào y u t ng u nhiên
c a mơ hình Random Walk [2]. Trong mơ hình Markov, s ti n tri n c a quá trình
ng
c chi ph i b i tr ng thái hi n t i c a quá trình, hay th m chí b chi
ph i b i N tr
m t quá trình Markov s tránh
c nh ng s
t ng t v
ng và v n t c, giúp mơ hình tr nên
phù h
ng quá trình
c trong th c t . Ví d : trong th
ng ch ng khốn giá c phi u c a ngày hôm sau s ph thu c vào giá và xu


6

ng mua bán c

c; hay v trí c a m

ph

thu c vào v tr hi n t i c a h .
P(S2|S1)

S1


P(S1|S2)

P(S3|S1)

S2

P(S2|S3)

P(S3|S2)
P(S1|S3)

S3

Hình 2.2. Quá trình chuy n tr ng thái trong mơ hình Markov. m i tr ng thái, mơ hình
s có m t phân b xác su t chuy n n nh ng tr ng thái ti p theo.

c s d ng trong [5]
i dùng

bi u di n quá trình di chuy n c a

n tho i trong m ng GSM. D li u

c t quá trình di chuy n

c
i dùng thi t b
ng trong m ng GSM có d ng chu i tu n t theo th i
gian v trí c a các tr m thu/phát sóng. Chu i v trí c a các tr m thu/phát sóng này
t chu i tr ng thái c a m t quá trình Markov, m i tr ng thái c a

quá trình này ng v i m t v trí; v trí c a m
i m t th
ng thái hi n t i c a quá trình, và s di chuy n c
m t v trí sang v trí k ti p li n k

m nh
nh
i dùng t

t s chuy n tr ng thái trong

chu i Makov.
B ng cách mơ hình hóa q trình di chuy
trên, ta có th

c nh ng y u t

t quá trình Markov
a quá trình Markov này, và

di chuy n c a
ng. C th , ta có th tính tốn
c phân b xác su t mà h chuy n t tr ng thái này sang m t tr ng thái khác
ng v i xác su
ng s di chuy n t v trí hi n t
n m t v trí k c n
xác su
c bi u di n b ng m t ma tr n chuy
i
(transition probability matrix).

c phân b xác su t c a
chu i Markov trên t ng tr ng thái. Phân b xác su
c bi u di n b ng m t
vector phân b (stationary distribution vector).


7

M

ng s có q trình di chuy

trình di chuy n c

ng này s giúp sinh ra các ma tr n chuy

vector phân b

i và

ng.

2.1.2.

t k t h p c a các v trí

M

mơ ph


a m t q trình di chuy n là khai thác m i

quan h gi
m
m i quan h này là: m t

ng mà m
ng U1

và L3,

ng U2

t
Nh ng m i quan h này

ví d

ng
v trí L1
trí L3 r i m

1]. Ví d v
n v trí L2
n v trí L2,

c xem xét trong t ng kho ng th i gian nh

nh,


i trong ngày hay ngày trong tu n.

Vi

c chính:
Xây d

ruction).

Khai phá lu t k t h

(pattern discovery).

c xây d
quan tr ng c a m t v
iv im t
l thu n v i kho ng th i gian
ng này t
trí trên chu i v trí
quan tr ng này.

ng
Các v

c xem xét hay lo i b
tránh nhi u) d a trên m c
i thu t kc áp d
gom nhóm các v trí

có liên quan v i nhau thành m t v trí duy nh t. K t qu cu i cùng c

này là chu
m nh ng v
và quan tr
iv im t

n
i

ng di chuy n.
i i thu t Apriori tu n t
các v

.

cs d

khai phá lu t k t h p gi a

ng di chuy n c a m

c bi u di n d ng t p nh ng m i k t h p (hay còn g i là ki u m u

i có th
pattern) này.

Ví d trình bày trong b ng sau là 5 ki u m u di chuy n ph bi n nh t c a m t
i trong trong kho ng th i gian là các ngày làm vi c trong tu n
i này có
t n su t di chuy n t
m Home n Media Lab (chu i <Home, Media Lab>)

cao nh t, xác su t xu t hi n c a chu i này trên
. Chu i ph bi n
th hai là <Media Lab, Home> và k

n là chu i <Commonweath, Media Lab>,


8

B ng 2.1. Các ki u m
có th
c xem

c

nh t c a m t quá trình di chuy n. Nh ng ki u m u này
am
i do m i
i s có các ki u m u và t n su t
khác nhau

#

M u

T n su t

1

<Home, Media Lab>


0.279

2

<Media Lab, Home>

0.265

3

<Commonweath, Media Lab>

0.133

4

<Home, Charles Hotel, Media Lab>

0.060

5

<Media Lab, Charles Hotel, Home>

0.053

Khai thác lu t k t h p trong nh ng kho ng th i gian khác nhau s cho k t qu
là các ki u m u khác nhau th hi
c thù di chuy n c a m

i trong nh ng
kho ng th i gian này. Ví d , cùng m
ng trên n u xét trong kho ng th i
gian ngày ngh (th b y và ch nh t) ta s

c t p các m

ch a các v trí Media Lab và Commonwealth.
K t lu n: nghiên c u [1] không nh m m c tiêu nh n di n hay so sánh các mơ
hình di chuy n v i nhau mà ch
khai thác nh ng y u t
c
t quá trình di chuy n. Tuy nhiên, có th th
c r ng: d li u v
chu i v trí c a m
phân bi
thu c

i có th
i nh

c mơ hình hóa
i khác.

m tm
cr

vào kho ng th i gian mà quá trình di chuy

giúp

c
c

xem xét.

2.2.
2.2.1.

n di n
n di n b ng mơ hình Markov

Trong bài tốn nh n di n, vi c mơ hình hóa q trình di chuy n c a m
i là
c quan tr ng vì
có th phân bi
c các q trình di chuy n khác nhau thì
c n ph i mô ph
di chuy n này.

và b

c a m i quá trình


9

mơ ph

c q trình di chuy n, v


nh n di n là: tính tốn m
xem chúng có thu c v cùng m
mơ hình di chuy n c a m

ti p theo c a bài tốn

ng gi a hai mơ hình di chuy n
nh
ng hay khơng. Hay nói cách khác, t m t
t, so sánh v i mơ hình c a nh
i

n d a trên nh ng

ng nh t t
u ki n sau:

ng c n tìm.

1) Quá trình di chuy n c a m

c

2) Nh

theo th i gian.

Quá trình di chuy n c a m

iv


cao.

n là duy nh t. Tuy nhiên, tính duy

nh t này có th
cb
m trong m t s
ng h p mà d li
m n và chính xác. Tuy nhiên, trong th c t , c
u ki
xác su
c ch ng minh trong [5] khi có t
n tho i d

ng có th

c
u có

c nh n di n d a trên mơ hình di chuy n

c ah .
Nghiên c u [5
ng gi a các mơ hình di chuy n Markov.
2.2.1.1.

m ng

n di n d a trên vi c tính tốn s


Residence Matching
ng Ux và Uk cùng di chuy n trong ph m vi m
m. Hay chính
v trí c a
ng này n m trong ph m vi m khu v
nh b i m ô
ng. Ch s
ng iden (identification index) gi a hai q trình di

chuy n c a Ux và Uk

c tính b ng công th c sau:
m

iden

Prx (Lj | Li ) Prx ( Li ) Prk ( Lj | Li ) Prk ( Li )

(1)

i, j

Lj | Li) (i, j
m) là xác su t m
ng di chuy n t i
v trí Lj sau khi r i v trí Li và Pr(Li) là xác su
ng t i v trí Li. t P x và x
l
t là ma tr n chuy

i và vector phân b sinh ra t quá trình Markov c a
Ux. Ta th y các xác su t Prx(Lj, Li) và
x(i

y, (1) có th

x(i)

c vi t l i

l

t ng v i các giá tr P x(i, j) và
:

m

iden

Px (i, j )
i, j

x

(i) Pk (i, j )

k

(i)



10

Xét m t t p d li u có n

ng.

t Ux v i l
t p d li u trên ta s
c
Uk. Giá tr idenk càng l n thì kh
m

ng) càng cao.

em so sánh mơ hình di chuy n c a m t

ng
t Uk (k
n) trong
c các ch s
ng idenk gi a Ux và t ng
Ux và Uk trùng nhau (hay Ux và Uk là cùng
y, Ux

Công th c (1)

c

nh là Uk có ch s idenk cao nh t.


i d a trên công th c

sau:

m

iden

Prx (Lj | Li ) Prx ( Li ) Prk ( Lj | Li ) Prk ( Li )
i, j

m

Prx (Lj

Li ) Prk ( Lj

Li )

i, j

y, có th hi u m c tiêu c

: tính tích xác su t hai

ng Ux và Uk cùng t ng c p v trí i và j trong t p m v trí chung. P
pháp này
c ki m nghi m trong [5] v i t l nh n di
vào kho ng ~30%.

2.2.1.2.

Cell Sequence Matching

M
xác su t mà ma tr n chuy
(hay

ch s
ng gi a
ng Ux và Uk là tính
i c a Ux có th
c sinh ra t chu i Markov c a Uk

c l i, tính xác su t ma tr n chuy n

i c a Uk có th

c sinh ra t chu i

Markov c a Ux).

t

M i s chuy
i tr ng thái trong chu i Markov c a Ux
c gán m t s tu n
y, n u chu i Markov c a Ux g m l tr ng thái thì s có l 1 s chuy n

i tr ng thái (

l 1). Xác su t m i chuy
i tr ng thái trong chu i
Markov c a Ux
c tham kh o trong ma tr n chuy
i c a Uk. Các xác su t này
c kí hi u là p .
y tích c a t t c các xác su t này th hi n m
liên
quan gi a ma tr n chuy
chính là ch s

i c a Uk

i v i chu i Markov c a Ux.

ng iden gi a Ux và Uk.
l 1

iden

p
1


11

nh ng chuy n

i tr ng thái


có xác su t p = 0

c lo i kh i chu i l
ng h p iden = 0.
d ng vector phân b mà ch s d ng ma tr n chuy
i và chu
r
i x ng, do xác su t ma tr n chuy

Chú ý
i c a Ux
c

sinh ra t chu i Markov c a Uk s khác v i xác su t ma tr n chuy
c sinh ra t chu i Markov c a Ux.

i c a Uk

Trong th c t , các xác su t p là m t s th c n m trong kho ng (0, 1]. D
tích c a chúng ti m c n v 0 và có th tr nên r t nh
c a máy tính

ng.

t ngồi ph m vi tính tốn

dùng m t cơng th

sau:


Trong cơng th c trên, iden s ln có giá tr
10 ln tr v m t giá tr
kho ng (0, 1]. Tuy nhiên, m
mơ hình v i nhau nh m tìm ra c p

c

b i m t bi u th c
v i bi n s

so sánh
ng có ch s iden l n nh t,

u vào trong
i các
giá tr c

th c a iden là không quan tr ng.
Qua th c nghi
di n

c ti n hành trong [5], p

i ~80%

c

so v i t l nh n di

u su t nh n

vào kho ng ~30%

.

2.2.2.

nh n di n b ng

M

n di
o di chuy n.

chu i g m các v trí
m ng. Vi c gom nhóm
m n) t

chu i v trí

c trình bày trong [4] d a trên vi c khai thác
t
n tho i
. M i v trí là m t nhóm các ơ
c th c hi n d a trên tham s là m t kho ng th i

.

Ví d , v i d li u di chuy



12

a

b

c

a

b

a

b

a

l1
d

c

a

b

a

b


c

a

l2

0

1

2

3

4

5

6

t=1
t=2

Hình 2.3. Chu i v trí c a q trình di chuy n xét trên m t tr c th i gian

Gi s v i t = 1, ta có chu i v trí c a U1 và U2
l1 = {a,b}

{c}


{a}

{b}

l2 = {d,c}

{a}

{b}

{a,b}

{a,b}

{a}

{c}

{a}

V i t = 2, ta có chu i v trí c a U1 và U2
l1 = {a,b,c}

{a,b}

l2 = {d,c,a}

{b,a,b}


Cho t p d li u D, v i m

{a,b,a}
{c,a}

ng Ui (i

trong t p này, tìm m t

chu i con c a chu i v trí li sao cho chu i con này là duy nh
trên,
v i t = 1, ta th y chu i con {a} {b} {a,b} khơng ph i là duy nh t, vì chu i con
này xu t hi n c hai chu i l1 và l2. Trong ph m vi t p d li u D ch g m hai i
ng U1 và U2, ví d các chu
c a l1 (ch xu t hi n trong l1) khi t = 1
là: {a,b}

{c} ho c {a,b}
a l2 là {d,c}

{c}

{a} ho c {a,b}

{a}

{b}, {d,c}

dài p c a chu i con có th


{a}

, các chu i

{a}

i (p = 2

mn tc a

d li u.
Nghiên c u [4
ch ra r ng các chu i con
l p l i nhi u l n trong nh ng kho ng th i gian khác nhau. D
có th
là c

nh danh duy nh
ng nào.

nh xem chu

y, vi c nh n di n m

th c hi n b ng cách dị tìm xem chu
c am t

ng
i con này


lx c
t Ui

a nó
t Ux

c

ng này có ch a chu i
có th

nh Ux = Ui.


13

Tuy nhiên trong m t s

ng h p mà d li

m n, vi c tìm m t chu
ng h p s

c b nhi u, ho c không

không cho k t qu chính xác ho c
c m t chu

y.



14

LÝ THUY T

lý thuy t tốn h c c
c trình bày
tài. N i dung bao g m lý thuy t v các hàm ng u nhiên, các
quá trình ng u nhiên,
mơ hình tốn h c và th ng kê dùng bi u di n
các quá trình này.

3.1. Quá trình ng u nhiên
Trong lý thuy t xác su t, quá trình ng u nhiên là m t t p h p các bi n ng u nhiên
t theo th i gian.
i n ng u nhiên là bi u di n c a m t
phép th ng u nhiên nào
i d ng m t s th c. Bi n ng u nhiên X là m t ánh
x t không gian các bi n c

p

vào R.
X:

R

Quá trình ng u nhiên
bi u di n s ti n hóa theo th i
gian c a m

ng hay m t h th ng. M t s ví d v quá trình ng u nhiên ti n
tri n theo th

giá ch ng khoán, ngo i t , s

a các lo i tín hi u

V m t tốn h c, m t q trình ng
cho m t khơng
gian xác su t ( , F, P) và m t t p h u h n S. M t quá trình ng u nhiên X trên
không gian tr ng thái S

c xem là m t t p h p
{ Xt: t

V i Xt là giá tr trong t p S và
còn g i là t p th i gian.
c a quá trình ng u nhiên X th

T}

c

y, Xt

t theo m t t p có th t T, hay
c xem là tr ng thái hay v trí

m t thu c T.


Q trình ng u nhiên r i r c. N u th i gian T thu c m t t p s nguyên có mi n
giá tr
nh (h u h n hay vơ h n), ví d T = N+ = [0; + ) thì quá trình quá trình
ng u nhiên là r i r c. Gi a m t kho
nh trong t p T s có m t s
ng xác
nh các giá tr t. Ví d , v i t p T = {1,2,3,4,5,6} ta có th d dàng nh n th y s
ng các giá tr t gi a 2 và 4 là 1 (ph n t 2), hay s

ng các giá tr gi a 1 và 5 là


15

3

y, s chuy
cr ir c

i tr ng thái c a quá trình ng u nhiên di n ra theo t ng

nh t.

Quá trình ng u nhiên liên t c. N u th i gian T thu c m t t p s th c

T = R+

= [0; + ) thì q trình ng
c g i là liên t c. Ví d , v i t p T = R+ , gi a
hai ph n t 1.0 và và 2.0 có th có vơ s các ph n t t, ví d : 1.1, 1.2, 1.3

v y, s chuy

i tr ng thái c a q trình ng u nhiên có th di n ra

b t c th i

m nào trong m t tr c th i gian xuyên su t c a q trình.
Các q trình ng
nhiên, ví d

c dùng mơ ph ng các quá trình x y ra trong t
a ch t l ng hay s d ch chuy n c a các phân t . K t

qu vi c nghiên c

c ng d ng trong vi c d

ng

ng th

3.2. Quá trình Markov
M
t t p h u h n các tr ng thái
S = {s1, s2, ... sn} và m t quá trình ng u nhiên b
u t m t tr ng thái b t kì trong
S. Quá trình l
t chuy n t tr ng thái này sang tr ng thái khác. Khi quá trình
m t tr ng thái si-1
n sang m t tr ng thái k ti p si, thì xác

su t chuy n tr ng thái này ch ph thu c vào tr ng thái hi n t i si-1
cl pv i
b t kì tr
c si-1, thì ta g i quá trình này là m t quá trình Markov b c
nh t. Kí hi u:
Pr(si | s0, s1, s2, s3
Tính ch
cịn

c

si-1) = Pr(si | si-1)

c g i là tính ch t M

y, q trình Markov

là m t q trình ng u nhiên có tính ch t Markov.

V i |S| = m tr ng thái trong t p S, phân b xác su t chuy n tr ng thái c a q
trình Markov có th
c bi u di n b ng m t ma tr n vuông P
c m x m,
g i là ma tr n chuy
i tr ng thái. M i ph n t P(i,j) bi u di n xác su
ki n Pr(sj | si) hay xác su t mà quá trình s chuy n sang tr ng thái sj

u

tr ng thái si.

T ng quát hóa, trong m t quá trình Markov b c n, xác su t x y ra c a tr ng
thái si ph thu

u ki n vào n tr