Nhận dạng motif và bất thường trên dữ liệu chuỗi thời gian dựa vào kỹ thuật băm
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.27 MB, 87 trang )
I H C QU C GIA TP. HCM
I H C BÁCH KHOA
----------------------------------------
PH M THANH XUÂN
NH N D NG MOTIF VÀ B
NG
TRÊN D LI U CHU I TH I GIAN
D A VÀO K THU
CHUYÊN NGÀNH: Khoa h c máy tính
MÃ S : 60.48.01
LU
TP. H CHÍ MINH, tháng 07
I H C QU C GIA TP. HCM
I H C BÁCH KHOA
----------------------------------------
PH M THANH XUÂN
NH N D NG MOTIF VÀ B
NG
TRÊN D LI U CHU I TH I GIAN
D A VÀO K THU T
CHUYÊN NGÀNH: Khoa h c máy tính
MÃ S : 60.48.01
LU
TP. H CHÍ MINH, tháng 07
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.
Cán b ch m nh n xét 1 : TS.
n Anh ........................
y ..............................................
Cán b ch m nh n xét 2 : TS. Võ Th Ng c Châu.....................................
Lu
ngày 22 tháng 07
cb ov t
2013.
ih
Thành ph n H
1. TS. Ph m Tr
m:
................................
2. TS. Lê Thanh Vân ................................
3.
y ..................................
4. TS. Võ Th Ng c Châu.........................
5.
n Anh ..................
Xác nh n c a Ch t ch H
ngành sau khi lu
CH T CH H
NG
ng Khoa qu n lý chuyên
c s a ch a (n u có).
T
NG KHOA
I H C QU C GIA TP. HCM
C NG HOÀ XÃ H I CH NGHIÃ VI T NAM
I H C BÁCH KHOA
c L p - T Do - H nh Phúc
---oOo---
-------------------------
Tp. HCM, ngày 22 tháng
2013.
NHI M V LU
i tính: Nam / N
Thanh Xuân
21/06/1983
Chuyên
Long An.................
m
Khoá: 2011
1-
VÀO
2motif
khai phá
.
H
321/01/2013
421/06/2013
5-
......
qua.
PGS.TS.
ng, ngo i tr các k t qu tham kh o t
ghi rõ trong lu
c trình bày trong lu
n n i dung nào c a lu
c n
ng này ho
ng khác.
Ngày 22/07/2013
Ph m Thanh Xuân
iii
c hi n
l y m t b ng c p
L IC
ôi xin chân thành
tâm
.
.
T
t
Tôi xin g i l
.
nt tc m
iv
i.
Motif trong d li u chu i th i gian là nh ng chu i con (Subsequense
xu t
hi n l
p l i nhi u l n trong t p d li u. B
ng trong d li u chu i th i gian
là m t chu i con ch xu t hi n duy nh t m t l n và khác bi t nh t v i t t c các chu i
con còn l i trong t p d li
các gi i thu t khai phá b
c c a d li u chu i th
ng r t l n và
i thu t khai phá motif
ng.
Trong lu
xu t m t gi i thu t m i, gi i thu t FMG (Feature
Match Grouping) có th v a phát hi n motif v a phát hi n b
chu i th
c r t l n. T d li u thô (raw data
ng trên t p d li u
u sau khi th c
hi
c chu n hóa (normalization) s ti p t c th c hi n thu gi m s chi u
(dimensionality reduction) và r i r c hóa (discretization) v d ng chu i ký t . S d ng
c as
t (sliding window
c w (w
t qua
t t c các ký t trong chu i d li u. Các chu i con sinh ra t c a s
(word), m i t
feature). M t b
ch
ch a trong cùng m
p (match) v i nhau s
c
c l n nh t, khóa
bucket
ng c
m
các th hi n motif t
t g i là các t
hash table)
là ng viên motif
ng ng viên b
ng viên motif
ch a duy nh t
ng. Th c hi n tìm
t
max (Rmax do
a trên hàm tính kho ng cách Euclid. M t ng viên b t
ng v n có th là m t th hi n motif v
ng Rmax, n u m t ng viên b
ng
là m t th hi n motif thì ng v
c lo i kh i danh sách nh ng ng viên b t
ng. B y gi , các ng viên b
ti n_lùi (forward_backward
ng còn l i s
nh n di n ng viên b
FMG
c lo i tr d n b ng gi i thu t
ng th t s .
phá motif
là
FMG
Random Projection
motif
v
ABSTRACT
Motif in time series data is the similar subsequences which appear repeatedly many
times in the data set. Anomaly in time series data is that a subsequence appears only
once and is most different from the rest of subsequence in the data set. Usually, the
size of the time series data is very large and growing more and more. This is the
challenge that makes it difficult for the motif discovery algorithms as well as the
anomaly discovery algorithms.
In this thesis, we propose a new algorithm, FMG (Feature Match Grouping)
algorithm which can find motif as well anomaly on the very large time series data.
From the initial raw data, after executing normalization step, we will perform
dimensionality reduction and discretization. Using the sliding window of size w (w
defined by the user), it slides through all the symbols in the string. The subsequence
generated by the sliding window are called the word, each word is considered as a
feature. A hash table is used to contain these features, two match features will be
stored together in the same bucket. Finding bucket with the largest size, the
corresponding key of this bucket will be the motif candidate. For the buckets
containing only a single feature, these features are anomaly candidates. We can find
motif instances from the motif candidate and basing on the dissimilarity maximum
threshold Rmax (Rmax defined by user based on Euclid distance function). An anomaly
candidate still can be any motif instance with the threshold Rmax, if an anomaly
candidate is also an motif instance, it will be eliminated from the anomaly candidate
list. Then, the remaining candidates will be excluded by forward_backward algorithm
to identify the real anomaly subsequence.
FMG algorithm solves the motif discovery and anomaly discovery problem in
linear time with the size of the data set, using memory space is a constant. The
experimental results show that the FMG algorithm is much better than the Random
Projection algorithm in motif discovery and much better than HOTSAX algorithm in
anomaly discovery.
vi
M CL C
................................................................................................................................. v
TÓM T T LU
ABSTRACT ................................................................................................................................................ vi
I THI
TÀI .........................................................................................................1
1.1
D li u chu i th i gian........................................................................................................... 1
1.2
Truy xu t thông tin trên d li u chu i th i gian ................................................................. 1
1.3
Khai phá motif và b
1.4
ng trên d li u chu i th i gian ............................................... 2
ng ti p c n c a lu
1.5
Ý ng
a lu
1.6
C u trúc c a lu
................................................................................................. 3
............................................................................................................. 4
............................................................................................................ 4
NG THU T NH NG CƠNG TRÌNH LIÊN QUAN ...................................................5
2.1
M t s khái ni
n........................................................................................................ 5
2.2
................................................................................. 8
2.2.1
........................................................................................................... 8
2.2.2
........................................................................ 9
2.3
u di n d li u chu i th i gian ......................................................... 10
2.3.1
m s chi u .......................................................................... 11
2.3.2
i r c hóa d li u ................................................................................ 15
2.4
Gi i thu t khai phá motif chính xác ................................................................................... 16
2.5
Gi i thu t khai phá motif x p x ......................................................................................... 17
2.6
Gi i thu t khai phá b
2.7
Gi i thu t k t h p khai phá motif và khai phá b
2.8
K t lu n ................................................................................................................................. 24
ng .......................................................................................... 19
I QUY T V
3.1
Thu gi m s chi u v
3.2
R i r c hóa d li u v
ng .............................................. 23
..................................................................... 25
......................................................................... 25
SAX ........................................................................ 26
3.3
MINDIST ................................................................................................... 28
3.4
Gi i thu t FMG .................................................................................................................... 30
3.5
Gi i thu t RFMG ................................................................................................................. 38
3.6
3.7
c hi n c a các gi i thu
K t lu n ................................................................................................................................. 41
N TH C VÀ TH
4.1
c ........................................... 39
NGHI M .................................................................................. 42
Mơ hình hi n th c các gi i thu t ........................................................................................ 43
vii
4.1.1
Gi i thu t chi u ng u nhiên RP .................................................................................. 43
4.1.2
Gi i thu t nh n d ng b
4.1.3
Gi i thu t v a khai phá motif v a khai phá b
4.1.4
Gi i thu t khai phá motif RFMG ............................................................................... 46
4.2
Th c nghi m các gi i thu
ng HOTSAX ............................................................. 44
ng FMG ................................ 45
n th c ........................................................................... 47
4.2.1
D li
m ................................................................... 49
4.2.2
D li
m ................................................................... 52
4.2.3
D li
m ..................................................................... 54
4.2.4
D li u doanh nghi
4.2.5
D li
m .................................................................................... 59
4.2.6
D li
m ............................................................... 62
4.2.7
D li u ch
4.3
m ................................................................ 57
m ............................................................. 63
So sánh các gi i thu t d a trên k t qu th c nghi m ....................................................... 66
T LU N ..................................................................................................................... 69
5.1
T ng k t ................................................................................................................................ 69
5.2
Nh
5.3
a lu
ng phát tri n c a lu
............................................................................................. 69
........................................................................................... 70
TÀI LI U THAM KH O...................................................................................................................... 71
PH L C A: B
I CHI U THU T NG
ANH-VI T .............................................................. A
PH L C B: LÝ L CH TRÍCH NGANG ............................................................................................... B
viii
HÌNH
Hình 1.1: D li u chu i th i gian bi u di n giá c phi u [1]................................................................... 1
Hình 1.2: (a) M t minh h a motif . (b) M t minh h a b
ng. [2] .................................................... 2
Hình 2.1: Chu i con C và M sinh ra t c a s
t và M kh
c v i C [5] ..................................... 6
Hình 2.2: Chu i con C kh p t
ng v i chu i con ngay chính v trí c a nó d ch sang trái hay sang
ph i m
m giá tr [5]..................................................................................................................... 7
Hình 2.3: Kho ng cách hai motif < 2R (A) ; Kho ng cách hai motif > 2R (B) [6] ................................. 7
a hai chu i con [9] ................................................................................ 9
a hai chu i con [9].......................................................... 10
Hình 2.6: Phép bi
i DFT [19] ......................................................................................................... 11
Hình 2.7: Phép bi
i DWT [19] ........................................................................................................ 12
Hình 2.8: Phép bi
i PAA [19] ......................................................................................................... 13
Hình 2.9: Phép bi
i APCA [19] ...................................................................................................... 14
Hình 2.10: Phép bi
i PLA [19] ....................................................................................................... 15
Hình 2.11: Phép bi
i r i r c hóa SAX [19] ..................................................................................... 16
Hình 2.12: Gi i thu t Brute-Force tìm 1-Motif trên d li u chu i th i gian [6] .................................... 17
Hình 2.13: Ma tr n ch a t t c các chu i con t c a s
t [5]....................................................... 18
Hình 2.14: Chi u trên c t 1 và 2, c p nh t ma tr n vuông | |× | | [5].................................................. 18
Hình 2.15: Chi u trên c t 3 và 4, c p nh t ma tr n vng | |× | | [5].................................................. 19
Hình 2.16: Gi i thu t Brute-Force nh n d ng chu i con b
ng [21] ............................................. 20
Hình 2.17: Gi i thu t HOTSAX nh n d ng chu i con b
ng [21]................................................. 21
Hình 2.18: Hai c u trúc d li u h tr gi i thu t HOTSAX [21] ........................................................... 22
Hình 2.19: Hai t p d li u chu i th
u [2]................................ 23
Hình 2.20: Hai t p d li u chu i th i gian sau khi kh p t ng c m hai[2]............................................. 24
m chu i d li u có chi u dài n = 128 v w = 8 [19]..................... 25
Hình 3.2: M u d li
c v có tính ch t tuy n tính cho th y d li u tuân theo phân b Gauss [19] 26
Hình 3.3: B ng th
tra nh
m ng t theo phân b Gauss v i s vùng phân b t 3
n 10 [19] ............................................................................................................................................. 27
Hình 3.4: R i r c hóa v chu i ký t cho m t chu i có chi u dài n = 128, ........................................... 27
w = 8, a = 3 [19]..................................................................................................................................... 27
Hình 3.5: Kho ng cách Euclid gi a hai chu i nguyên th y (A), hai chu
m s chi u (B)
và hai chu
i r c hóa (C) [19] ................................................................................................. 29
ng cách gi a hai ký t b ng cách tra b ng [19] ................................ 29
ch t ch
i c a hàm kho ng cách MINDIST v i h s a và w
ng [19] ......... 30
Hình 3.8: Gi i thu t Build_FM_HashTable xây d ng b
chu i d li
i r c hóa ......... 32
Hình 3.9: Minh h
ng viên motif và ng
viên b
ng t
i T = aacbaccacbc, c a s
t w = 3 ......................................... 33
Hình 3.10: Gi i thu t Get_Motif_Candidate ch n ng viên motif t b
................................... 34
Hình 3.11: Gi i thu t Find_Motif tìm t t c nh ng th hi n motif t motif
ng kho ng
cách t
max ...................................................................................................................................... 35
Hình 3.12: Gi i thu t Forward_Backward nh n d
ng nh t ................................. 37
Hình 4.1: Mơ hình hi n th c c a gi i thu t RP...................................................................................... 43
Hình 4.2: Mơ hình hi n th c gi i thu t HOTSAX ................................................................................. 44
ix
Hình 4.3: Mơ hình hi n th c gi i thu t FMG ........................................................................................ 45
Hình 4.4: Mơ hình hi n th c gi i thu t RFMG ...................................................................................... 46
Hình 4.5: Các thành ph n giao di
i dùng.................................................................................... 47
B ng 1: Ch
a các thành ph n giao di n c
..................................................... 48
B ng 2: Thông s
u vào cho các t p d li u dùng trong th c nghi m ............................................... 49
Hình 4.6: K t qu c a gi i thu t RP trên d li
m ................................................... 49
Hình 4.7: K t qu c a gi i thu t RFMG trên d li
m ............................................. 50
Hình 4.8: K t qu c a gi i thu t FMG tìm motif trên d li
m ................................ 50
Hình 4.9: K t qu c a gi i thu t FMG tìm b
ng trên d li
m ....................... 51
Hình 4.10: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m ..... 51
Hình 4.11: K t qu c a gi i thu t RP trên d li
m ................................................. 52
Hình 4.12: K t qu c a gi i thu t RFMG trên d li
m ........................................... 52
Hình 4.13: K t qu c a gi i thu t FMG tìm motif trên d li
m .............................. 53
Hình 4.14: K t qu c a gi i thu t FMG tìm b
ng trên d li
m ..................... 53
Hình 4.15: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m ..... 54
Hình 4.16: K t qu c a gi i thu t RP trên d li
m.................................................... 54
Hình 4.17: K t qu c a gi i thu t RFMG trên d li
m ............................................. 55
Hình 4.18: K t qu c a gi i thu t FMG tìm motif trên d li
m ................................ 55
Hình 4.19: K t qu c a gi i thu t FMG tìm b
ng trên d li
m ....................... 56
Hình 4.20: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m........ 56
Hình 4.21: K t qu c a gi i thu t RP trên d li
m .................................................. 57
Hình 4.22: K t qu c a gi i thu t RFMG trên d li
m............................................ 57
Hình 4.23: K t qu c a gi i thu t FMG tìm motif trên d li
m ............................... 58
Hình 4.24: K t qu c a gi i thu t FMG tìm b
ng trên d li
m ...................... 58
Hình 4.25: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m ...... 59
Hình 4.26: K t qu c a gi i thu t RP trên d li
m ........................................... 59
Hình 4.27: K t qu c a gi i thu t RFMG trên d li
m ..................................... 60
Hình 4.28: K t qu c a gi i thu t FMG tìm motif trên d li
m ........................ 60
Hình 4.29: K t qu c a gi i thu t FMG tìm b t
ng trên d li
m ............... 61
Hình 4.30: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m 61
Hình 4.31: K t qu c a gi i thu t RP trên d li
m ............................................. 62
Hình 4.32: K t qu c a gi i thu t RFMG trên d li
m ....................................... 62
Hình 4.33: K t qu c a gi i thu t FMG tìm motif trên d li
m .......................... 63
Hình 4.34: K t qu c a gi i thu t RP trên d li
m .............................................. 63
Hình 4.35: K t qu c a gi i thu t RFMG trên d li
m ........................................ 64
Hình 4.36: K t qu c a gi i thu t FMG tìm motif trên d li u STOCK 12
m ........................... 64
Hình 4.37: K t qu c a gi i thu t FMG tìm b
ng trên d li
m .................. 65
Hình 4.38: K t qu c a gi i thu t HOTSAX khai phá b
ng trên d li
m .. 65
B ng 3: T ng k t k t qu khai phá motif c a các gi i thu t................................................................... 66
B ng 4: T ng k t các k t qu khai phá b
ng c a các gi i thu t ................................................... 67
Hình 4.39: So sánh th i gian th c thi khai phá motif c a các gi i thu t ................................................ 68
Hình 4.40: So sánh th i gian th c thi khai phá b
ng c a các gi i thu t ....................................... 68
x
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
I THI
1.1 D li u chu i th i gian
D li u chu i th i gian là d li
c
ng d li u có th có hai hay nhi u chi
TÀI
c m t cách tu n t theo th i gian.
i
i có m t chi u là chi u th i
gian. D li u chu i th i gian xu t hi n r t nhi
(Hình 1.1), y t , âm nh
.v.v.
c
: tài chính
Hình 1.1: D li u chu i th i gian bi u di n giá c phi u [1]
D li u chu i th
c liên t c trong th i gian dài nên có kích
cr tl
Các gi i thu t khai phá d li u chu i th i gian ph i
i m t v i chi phí r t l n v th i gian th c thi
nh .
vi c nghiên c
u qu
khai phá d li u chu i th i gian ngày
càng quan tr ng và thu hút r t nhi u s quan tâm.
1.2 Truy xu t thông tin trên d li u chu i th i gian
Truy xu t thông tin trên d li u chu i th i gian là vi
th a mãn nhu c u c
nh và rút trích thơng tin
i dùng. Gi i thu t truy xu t thông tin s tìm trên t p d li u
nh ng m u thơng tin thích h
i dùng. Có hai
c truy xu t thông
tin là: truy xu t theo m u và truy xu t theo n i dung.
Truy xu t theo m u (pattern-base retrieval
c m t m u (pattern) mô t
thơng tin c n tìm, gi i thu t s tìm trong t p d li u nh ng m u thông tin th
u
ki n trùng kh p v i m u mơ t
c có th
c mơ t
i d ng
ngơn ng c p cao ho c có th chuy
i v d ng mơ t tốn h
máy tính có th
Trang 1
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
hi u. M t ví d truy xu t theo m
u ngơn ng truy v n có c u trúc
(Structured Query Language hay SQL). M t s ng d ng d ng truy xu t này là nh ng
ng d ng trong nh n d ng gi ng nói, h th ng truy xu t âm thanh, nh n d ng hình nh.
Truy xu t theo n i dung (content-base retrieval): là truy xu t t t c các m u thông
bi
c trong t p d li u th a mãn m t mô t v t lý, hay m t tiêu chí so
sánh, ho c là m t m
a nh ng m u thông tin trong t p d li u.
M t ví d cho truy xu t theo d
giá c phi
im
i dùng mu n theo dõi nh ng cơng ty có
.
t gi i thu t chúng ta d a vào ba t
:
Tính
: k t qu tr v khơng có l i tìm sai (d li u khơng nên có trong
k t qu tr v mà l i có trong k t qu tr v ).
: k t qu tr v khơng có l i tìm sót (d li u nên có trong k t qu
tr v
i khơng có trong k t qu tr v ).
Tính h u hi u: th
ng và không gian b nh c a gi i thu t ph i
ch p nh
c.
Tuy nhiên
cao
i qua l
i b gi
c tính h u hi u
c l i.
1.3 Khai phá motif và b
ng trên d li u chu i th i gian
Khai phá motif là tìm nh ng chu
nhau xu t hi n l
li u chu i th i gian (Hình 1.2a). Khai phá b
p l i trong d
ng (anomaly) là tìm m t chu i con
khác bi t nh t v i t t c các chu i con khác trong d li u chu i th i gian (Hình 1.2b).
Hình 1.2: (a) M t minh h a motif . (b) M t minh h a b
Trang 2
ng. [2]
NH N D NG MOTIF VÀ B
Trong khai phá b
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
ng k t qu tr v
i ph i là k t qu chính xác trong khi
khai phá motif k t qu tr v có th là m t k t qu x p x . H
gi i thu t khai phá motif là:
ng ti p c n chính c a
Khai phá motif chính xác (exact motif): là làm vi c tr c ti p trên d li u thơ d a
vào gi i thu t brute-force
t
có th c i ti n gi i thu t b ng cách áp
d ng m t s heuristic nh
c cho gi i thu t. Các gi i thu t
ng
ti p c n này có
phù h p v i d li
cao tuy nhiên tính h u hi u khơng cao,
c nh .
Khai phá motif x p x (approximate motif): d li u chu i th i gian s
c x lý
c khi th c hi n vi
gi m s chi u, r i r c hóa. Trong q
trình khai phá có th áp d ng m t s tính ch t d a trên xác su t, tính ng u
ng ti p c
tính h u hi u c a gi i thu t trong khi tính
tính chính xác v n có th ch p nh
c l n.
1.4
D
c, phù h p v i d li u có kích
ng ti p c n c a lu
ng v a khai phá motif v a khai phá b
các c ng s
xu
[2]. C
ng c a tác gi Yi Lin cùng
xu t m t gi i thu t m i, gi i thu t
FMG v a khai phá motif x p x v a nh n di n chính xác
ng b
ng d a trên
h qu c a quá trình khai phá motif . Gi i thu t FMG thích ng t t v i d li u có kích
c l n.
ng c a gi i thu t FMG là:
T
d
li u thô (raw data
u sau khi th c hi
c chu n hóa
(normalization) s ti p t c th c hi n thu gi m s chi u (dimensionality reduction) và
r i r c hóa (discretization) v d ng chu i các ký t . S d ng c a s
t (sliding
window
c w (w
i dùn
t qua t t c các ký t trong
chu i d li u. Các chu i con sinh ra t c a s
t g i là các t (word), m i t
c
feature). M t b
hash table
ch a các
p (match) v i nhau s
c ch a trong cùng m t
butket
là ng viên motif
nh
c l n nh
ch a duy nh t m
ng ng viên b
Trang 3
ng.
ng c a thùng
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
Th c hi n tìm các th hi n motif t
Rmax (Rmax
viên b
ng viên motif
a trên hàm tính kho ng cách Euclid. M t ng
ng v n có th là m t th hi n motif v
ng Rmax, n u m t ng viên
b
ng là m t th hi n motif thì
viên b
ng. B y gi , các ng viên b
gi i thu t ti n_lùi (forward_backward
1.5
c a lu n
Gi thu t FMG
nay.
t
c lo i kh i danh sách nh ng ng
ng còn l i s
c lo i tr d n b ng
nh n di n ng viên b
xu t giúp gi i quy
ng v a khai phá motif v a khai phá b
cv
ng là m t
ng th t s .
bùng n d li u hi n
ng m i giúp ti t
ki m chi phí c a các gi i thu t khai phá motif và khai phá b
ng riêng l . T k t
qu th c nghi m cho th y gi i thu t FMG tìm th y motif chính xác
i thu t chi u
ng u nhiên v i th i gian th
p nhi u l n. Trong khai phá b
ng
gi i thu t FMG nh n di
ng b
ng v i th
p
nhi u l n so v i gi i thu t HOTSAX.
1.6 C u trúc c a lu
Ph n ti p theo c a lu
có b c
nh c l i m t s khái ni m n n t ng v khai phá motif và b
ng
trên d li u chu i th i gian, t ng thu t l i nh
u di n d li u,
i r c hóa d li
d li u chu i th i gian. Ph n cu
khai phá motif và khai phá b
c a lu
C
lu
ng tiêu bi u
III: chi ti t hóa tu n t
c th c hi
m s chi
hàm tính kho ng cách Euclid trên d li
thông d ng trên
t ng thu t m t s cơng trình
ng ti p c n
ng ti p c n c a c a
i r c hóa SAX,
i r c hóa, gi i thi u gi i thu t
FMG v a khai phá motif v a khai phá b
c p.
IV: hi n th c và th nghi m gi i thu t FMG và m t s gi i thu t khác
so sánh. K t qu khai phá motif
(RP) và k t qu khai phá b
c so sánh v i g i thu t chi u ng u nhiên
c so sánh v i gi i thu t nh n d ng b t
ng HOTSAX.
nh ng k t lu n sau khi th c hi n lu
.
Trang 4
ng phát tri n c a lu n
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
NG THU T NH NG CƠNG TRÌNH
LIÊN QUAN
C
nh c l i m t s khái ni
khai phá b
b
ng, s
ng
c s d ng trong khai phá motif và
gi i thi u m t s cơng trình tiêu bi u v khai phá motif và
n lu
.
2.1 M t s khái ni
n
D li u chu i th i gian là m t t h p tu n t c a nh ng m u d li u
c
cm t
cách liên t c theo th i gian. M t m u d li u chu i th i gian có th là m t giá tr
(là m t con s th c), thì ta g i là chu i th i gian m t kênh (single-chanel time series)
ho c có th là m
ng con s th c), thì
c g i là chu i
th i gian nhi u kênh (multi-chanel time series) [4]. D li u chu i th i gian m t kênh ta
có th th y trong d li u ch ng khoán, d li
, d li
ng .v.v. D
li u nhi u kênh ta th th y trong d li u motion capture ghi nh n nhi u góc
khác
nhau c a m
ng. Trong lu
ch làm vi c trên d li u m t
kênh. Và gi s r ng t t c nh ng m u giá tr
c liên t c t i các th i kho ng
b ng nhau.
D li u chu i th i gian (Time series): M t d li u chu i th i gian T =
t1
n
là m t t p h p có th t c a n m u giá tr th
c t i nh ng th i
kho ng liên t c b ng nhau [7].
Chu i con (Subsequense): Cho m t d li u chu i th i gian T có chi u
dài là n, m t chu i con C trong T có chi u dài m là m t m u c a nh ng giá tr liên t c
trích t T, C = tp
p+ m-1
v i
m + 1 [6].
d li u chu i th i gian (Time series database): là m t t p khơng
có th t c a nhi u d li u chu i th i gian. Ký hi u D = {T1,
Vì t t c nh ng chu
ng nên b t k gi i thu
trong d li u chu i th
u có kh
Tk} [7].
ng viên motif ho c ng viên b t
i rút trích t t c nh ng chu i con có th có
u này có th
c b ng cách s d ng m t c a s
t (Sliding Window).
Trang 5
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
C as
t (Sliding Window): Cho m t d li u chu i th i gian T có
chi u dài n, m t c a s
cw
t qua t
m giá tr trên chu i T, k t qu
chu
cw
ng w << n) s
c m t danh sách n-w+ 1 các
c rút trích t chu i T [5].
M t chu
c sinh ra t c a s
tc
c ki
v i
m t chu i con khác trong t t c nh ng chu i con còn l i hay khơng d a vào m t hàm
tính kho ng c
c g i là kh p (match).
Kh p (Match): Cho m t s th c R
và m t d li u chu i th i gian T ch a m t chu i con C b
con M b
u t i v trí q, n u hàm tính kho ng cách t C
thì ta nói là chu i con M kh
u t i v trí p và m t chu i
n M ký hi u
c v i chu i con C [5] (Hình 2.1).
Hình 2.1: Chu i con C và M sinh ra t c a s
t và M kh
c v i C [5]
kh p c a hai chu i con thì r t rõ ràng và tr c quan, tuy nhiên chúng
khái ni m kh p t
ng (Trivial match). Hi n nhiên ta th y
m t chu i con s kh p t
best match) v i m t chu i con khác mà g
nó, là chu i con mà c a s
t v bên trái hay bên ph i c a chính nó
ch m
nh
m giá tr
trong
ng h p kh p t
Kh p t
motif và b
ng c n ph i lo i b
ng này.
ng (Trivial match): Cho m t d li u chu i th i gian T và
m t chu i con C b
u t i v trí p và m t chu i con M kh
cv iCb
ut iv
trí q. Chúng ta nói chu i con M là kh p t
ng v i chu i con C n u p = q ho c
không t n t i m t chu i
nào b
u t i v trí sao cho
và
ho c
[5] (Hình 2.2).
Trang 6
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
Kh p t m
ng
Hình 2.2: Chu i con C kh p t
ng v i chu i con ngay chính v trí c a nó
d ch sang trái hay sang ph i m
m giá tr [5]
K-Motifs: Cho m t d li u chu i th i gian T có chi u dài n, và m t s
th c R, motif quan tr ng nh t trong T
c g i là 1-Motif) là chu i con C1
trong T có s
ng chu i con kh p khơng t
tr ng b c K (cịn g i là K-Motif) là chu i con Ck
kh p khơng t
v im i
ng v i nó cao nh t. Motif quan
T có s
ng chu i con
ng v i nó cao th K và ph i th
u ki n D(Ck , Ci) > 2R,
K [6] (Hình 2.3B).
n nh n m nh r ng các chu i con trong t p các motif ph i tách
bi
u này r t quan tr ng vì n
motif mà có nh ng chu i con chung
c xem là m t motif (Hình 2.3A).
Hình 2.3: Kho ng cách hai motif < 2R (A) ; Kho ng cách hai motif > 2R (B) [6]
Trang 7
NH N D NG MOTIF VÀ B
B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
ng(Anomaly): Cho m t d li u chu i th i gian T có chi u dài n,
m t chu i con C trong T là b
ng n u kho ng cách t C n chu i con láng gi ng
g n nh t c a nó là l n nh t. Nói cách khác chu i con C là chu i con khác bi t nh t
trong T [21].
2.2
Trong các v
n d li u chu i th i gian, vi c tính m
gi
hai chu
t quan tr ng. Khi so sánh hai chu
nhau hay khơng ta ph i dùng m
tính m
là hàm kho ng cách. N
v i
gi chúng g i
ng cách gi a hai chu i con b ng không, ta nói hai
chu i con là gi ng h t nhau. N
xa) thì m
khác bi t c a hai chu
lu
c p nh
ng cách gi a hai chu i con càng l n (càng
i con có chi u dài
b ng nhau.
Cho các chu i con x, y và z, D g i là hàm kho ng cách gi a hai chu i con thì D
ph i th a các tính ch t sau:
1 Tính khơng âm
x, y
i x ng
2
D(x, y) = D(y, x)
3 Tính b
x, y
ng th c tam giác
x, y, z
2.2.1
Minkowski
H u h t các cơng trình nghiên c u trên d
li u chu i th i gian d
tính kho ng cách (hay m c
) gi a hai chu i con (Hình 2.4).
Hàm tính kho ng cách Minkowski
D(X, Y) =
=1(
c sau:
)
(2.1)
Khi p = 1 ta có kho ng cách Manhattan.
Khi p = 2 ta có kho ng cách Euclid.
Khi
ta có kho ng cách Max.
Trang 8
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
Hình 2.4:
Minkowski gi a hai chu i con [9]
m:
D tính toán.
S d
c cho nhi u bài toán khác nh
r t thích h p khi ta s d ng các phép bi
i, gom c
c bi t là
i và r i r c hóa d li u DFT,
m:
Nh y c m v i d li u nhi u.
Không hi u qu khi d li
ch ng
n khác nhau, ví d
i r t gi
ng m
hình d ng r t gi ng nhau.
c a A và B r t khác nhau m c dù
Khơng thích h p v i d li
c a A và B t
i r t gi
c a B là 30-
ng
hai chu i giá
m c 100 cịn
ng khác nhau, giá ch ng khốn
ng c a A là 20-80 còn
c a A và B r t khác nhau m c dù hình d ng r t
gi ng nhau.
2.2.2
Dynamic Time Warping (DTW)
V
Minkowski so sánh t ng c
m là không th trong
ng h p hai
chu i này s r t gi ng nhau n
c thu h p m t kho
tr c th i gian thì k t qu c
Minkowski s là r t l n (hai chu i r t khác
kh c ph
m này c a
Minkowski b ng cách t m t
Trang 9
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
m trong chu i này có th ánh x t i nhi
m trong chu i kia và nh ng ánh x
này là khơng th ng hàng (Hình 2.5).
(Dynamic Time Warping
Hình 2.5:
này g i là
xu
xo n th
ng
Dynamic Time Warping gi a hai chu i con [9]
m:
Cho k t qu
i
Minkovski.
Cho phép nh n d ng nh ng m u có hình d ng gi
u dài
khác nhau.
m:
ph c t p tính tốn cao, ch y lâu g p nhi u l n so v i
Minkovski. V i m t chu i có chi u dài n
p
2
ph c t p tính tốn là O(n ).
2.3
u di n d li u chu i th i gian
c c a d li u chu i th
ng r t l n cho nên chi phí truy xu t, tính tốn
trên d li u thơ là r t cao.
gi
c d li u
pháp thu gi m s chi u (dimensionality reduction) giúp nâng cao hi u su t truy xu t và
i r c hóa (discretization) d li
i d ng chu i bit hay
chu i ký t nh m khai thác các k thu t nén d li
thu t khai phá d li u
n (text mining
n chu n hóa d li u (normalization)
c khi b
nhau ho
u bi u di n nh m tránh nh ng v
ng khác nhau.
Trang 10
d li
n khác
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
2.3.1 Cá
m s chi u
Thu gi m s chi u là ta bi u di n d li u chu i th i gian n chi u X = (x1,x2
n) thành
nh
n k chi u Y = (y1,y2
n và k là h s c a
k ), Y g
n. T
n Y ta hồn tồn có th ph c h i l i d li u X
u.
y thay vì truy xu t, tính toán trên d li u g c n chi u thì ta ch c n truy xu t,
tính tốn trên d li u k chi u (k << n). Tuy nhiên n u k quá nh so v i n thì d li u
ph c h i s
li
a.
c l i.
i Fourier (Discrete Fourier Transform - DFT)
ng s
ngh xu
[10]. Trong
ng d li
c bi u di n b
n là
ng cosin (Hình 2.6).
Xf =
1
1
=0
Hình 2.6: Phép bi
2 ( )
(2.2)
i DFT [19]
m:
Có kh
li u và ch u nhi u t t.
Cho phép so sánh gián ti p hai chu i X,Y thông qua kho ng cách c a hai
chu i Xf , Yf
c bi
f,
Yf
t h ng s .
m:
i v i phép bi
i Fourier nhanh (Fast Fourier Transform ph c t p khá cao O(nlogn).
Khó gi i quy
ng bi u di n có chi u dài khác nhau.
Trang 11
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
b. P
ng s
xu
DWT bi u di n d li u chu i th
1
g H (t )
- DWT)
[11]
ng Haar (Hình 2.7).
0 t 1/ 2
1
1/ 2 t 1
0
(2.3)
otherwise
ng h p khác
Hình 2.7: Phép bi
i DWT [19]
m:
ph c t p c a DWT là O(n).
Có kh
nhi u cao, thích h p v i lo i d li
i vì
i liên t c.
m:
Chi u dài c a chu i d li u g c và chu i d li u sau khi bi
con s
i ph i là m t
a c a 2.
c.
ng pháp g p t
n x p x (Piecewise Aggregate Approximation PAA)
pt
n x p x (PAA) do E. Keogh và c ng s
xu
2000 [12]
n t x p x k m giá tr li n k nhau thành cùng
m t giá tr trung bình c ng c a k
c th c hi n t trái sang
ph i và k t qu cu
cm
ng d ng b c thang (Hình 2.8).
Trang 12
NH N D NG MOTIF VÀ B
NG TRÊN D LI U CHU I TH I GIAN D A VÀO K THU
Hình 2.8: Phép bi
i PAA [19]
m:
Th i gian tính tốn r t nhanh.
H tr nhi
ng cách.
H tr truy v n v i chi u dài khác nhau.
m:
Xây d ng l i chu
u là r
n nh
ng sinh l i.
c bi
m c c tr ) trong t
nx p
x vì tính giá tr trung bình.
d.
px t
n thích nghi (Adaptive Piecewise Constant
Approximation - APCA)
px t
n thích nghi do E. Keogh và các c ng s
xu
2001 [13]
p x hóa d li
u thành nh ng
n th ng n
nhau (b ng k
n th ng x p x là b ng
c khơng b ng
n th
nhau (Hình 2.9). T i nh ng th
n th ng x p x
Th
m giá tr d li
n d li u dài
m mà giá tr d li
c ng
long segment).
Trang 13
n d li u ng n
n th ng x p x
ng nhi u thì các
short segment),
c dài
