Đại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA
--------------------

PHẠM ĐĂNG NINH

BIỂU DIỄN DỮ LIỆU CHUỖI THỜI GIAN
Ở MỨC BIT VÀ ỨNG DỤNG
Chuyên ngành : KHOA HỌC MÁY TÍNH

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 09 năm 2009


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Cán bộ hướng dẫn khoa học : PGS. TS. Dương Tuấn Anh ...............................

Cán bộ chấm nhận xét 1 : PGS. TS. Đỗ Phúc....................................................

Cán bộ chấm nhận xét 2 : TS. Quản Thành Thơ ...............................................

Luận văn thạc sĩ được bảo vệ tại:
HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng . . . . năm . . . . .


TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CƠNG NGHỆ THƠNG TIN

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

CỘNG HỒ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc
---oOo--Tp. HCM, ngày . . . . . tháng . . . . . năm . . . . . .

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: PHẠM ĐĂNG NINH. . . . . . . . . . . . . . . . . . … Phái: Nam………………..
Ngày, tháng, năm sinh: 17 / 12 / 1984 . . . . . . . . . . .

Nơi sinh: Bà Rịa Vũng Tàu. . . . . . .

Chuyên ngành: Khoa Học Máy Tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSHV: 00707177 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1- TÊN ĐỀ TÀI: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BIỂU DIỄN DỮ LIỆU CHUỖI THỜI GIAN Ở MỨC BIT VÀ ỨNG DỤNG. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..........................................................................
Nghiên cứu đề xuất một phương pháp biểu diễn dữ liệu chuỗi thời gian ở mức bit qua sự cải
tiến phương pháp xấp xỉ gộp ký hiệu góa SAX và xấp xỉ gộp ký hiệu hóa khả chỉ mục iSAX
(của nhóm Keogh) dựa trên một quá trình huấn luyện dữ liệu. . . . . . . . . . . . . . . . . . . . . . . . . .
..........................................................................
Nghiên cứu sử dụng hai cấu trúc chỉ mục phù hợp với kiểu biểu diễn ở mức bit là chỉ mục
VA-File và cấu trúc cây phân cấp (hierarchical tree) nhằm giải quyết bài toán so trung mẫu. .
..........................................................................
..........................................................................
..........................................................................
..........................................................................

.........................................
3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .
4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: PGS. TS. Dương Tuấn Anh. . . . . . . . . . . . . . . . . . .
.....................................................................
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

KHOA QL CHUYÊN NGÀNH
(Họ tên và chữ ký)


LỜI CAM ĐOAN
Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác như
đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do chính tơi
thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng
cấp ở trường này hoặc trường khác.
Ngày . . . . . tháng . . . . năm . . . . .

Phạm Đăng Ninh

i


LỜI CẢM ƠN

Tôi xin gởi lời cảm ơn chân thành và sâu sắc đến PGS. TS. Dương Tuấn Anh,
người Thầy đã tận tình hướng dẫn tơi trong suốt q trình học Cao học và tạo mọi
điều kiện để tơi có thể hồn thành luận văn này.
Tơi cũng xin cảm ơn gia đình, bạn bè đã động viên và tạo mọi điều kiện tốt nhất
để tơi có thể tiếp tục theo đuổi việc học tập và nghiên cứu. Tôi trân trọng dành tặng
thành quá của luận văn này cho Cha Mẹ. Nhờ công lao dưỡng dục của Người mà
chúng con mới có được thành quả như ngày hơm nay. Con xin hứa sẽ tiếp tục cố
gắng phấn đấu để vươn cao hơn nữa.

ii


TÓM TẮT LUẬN VĂN
Biểu diễn dữ liệu chuỗi thời gian ngày càng đóng vai trị quan trọng trong các
bài tốn khai phá dữ liệu chuỗi thời gian. Với sự phát triển nhanh chóng của chuỗi
dữ liệu thời gian cùng với các lĩnh vực ứng dụng của nó, địi hỏi phải đề ra những
phương pháp biểu diễn hợp lý nhằm giải quyết các bài toán liên quan một các hiệu
quả.
Đề tài này sẽ đề nghị một phương pháp biểu diễn dữ liệu ở mức bit mới thơng
qua q trình cải tiến phương pháp xấp xỉ gộp ký hiệu hóa SAX và xấp xỉ gộp ký
hiệu hóa khả chỉ mục iSAX dựa trên một q trình huấn luyện dữ liệu.
Chúng tơi sử dụng hai cấu trúc chỉ mục tương thích với kiểu biểu diễn bit là chỉ
mục file xấp xỉ hóa vector (vector approximation file) và kiến trúc cây phân cấp
(hierarchical tree) nhằm giải quyết bài toán so trùng mẫu. Trong quá trình tìm
kiếm, chúng tơi kết hợp giải thuật tìm kiếm xấp xỉ và giải thuật tìm kiếm chính xác
trên cả hai cấu trúc chỉ mục. Qua thực nghiệm cho thấy, phương pháp biểu diễn mới
hiệu quả hơn so với phương pháp cũ trong bài toán so trùng mẫu.

iii



ABSTRACT
The suitable choice of representation greatly affects the ease and efficiency of
time series data mining. With the increasing amount of time series data in many
applications, it is important to investigate a right representation for the areas that
have seen the majority of research interest in time series data mining.
This thesis introduces a new bit level representation of time series data based on
significant improvements over the current representations: Symbolic Aggregate
approXimation SAX and indexable Symbolic Aggregate approXimation iSAX via a
training phase.
To perform query by content, we build vector approximation file (VA-File) and
hierarchical tree as our indexing techniques. We have also provided examples of
algorithms that use a combination of approximate search and exact search to reduce
search space in both indexing structures. We find out our representation competitive
with existing approaches by experiments.

iv


MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
TÓM TẮT LUẬN VĂN ........................................................................................... iii
ABSTRACT .............................................................................................................. iv
MỤC LỤC...................................................................................................................v
DANH MỤC HÌNH ................................................................................................ viii
CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ .........................................................................1
1.1 Dữ liệu chuỗi thời gian…......................................................................................1
1.2 Biểu diễn chuỗi thời gian.. ....................................................................................2
1.3 Mục tiêu và giới hạn của đề tài .............................................................................5

1.4 Tóm lược những kết quả đạt được ........................................................................6
1.5 Cấu trúc của luận văn……....................................................................................8
CHƯƠNG 2: TỔNG THUẬT CÁC CƠNG TRÌNH LIÊN QUAN .........................10
2.1 Các cơng trình về độ đo tương tự........................................................................10
2.1.1 Độ đo Minkowski……...........................................................................11
2.1.2 Độ đo xoắn thời gian động (Dynamic Time Warping - DTW)..............13
2.1.3 Chuỗi con chung dài nhất (Longest Common Subsequence - LCS)......16
2.2 Các cơng trình về biểu diễn chuỗi thời gian .......................................................17
2.2.1 Các phương pháp thu giảm số chiều ......................................................17
2.2.2 Các phương pháp rời rạc dữ liệu ............................................................22
2.2.3 Các phương pháp biểu diễn dữ liệu ở mức bit .......................................26
2.3 Cấu trúc chỉ mục………… .................................................................................28
2.3.1 Cấu trúc chỉ mục R-Tree ........................................................................28
2.3.2 Mơ hình tổng qt bài tốn tìm kiếm tương tự ......................................29
2.3.3 Yêu cầu của phương pháp đánh chỉ mục ...............................................30
2.3.4 Framework GEMINI ..............................................................................30
CHƯƠNG 3: NHỮNG CƠ SỞ LÝ THUYẾT NỀN TẢNG ....................................33

v


3.1 Giải thuật gom cụm k-means (hay giải thuật Lloyd) ..........................................33
3.2 Cấu trúc chỉ mục file xấp xỉ hóa vectơ (VA-File) ..............................................36
3.2.1 Cấu trúc chỉ mục VA-File ......................................................................36
3.2.2 Chặn trên và chặn dưới của khoảng cách...............................................38
3.2.3 Giải thuật truy vấn n láng giềng gần nhất trên VA-File.........................40
3.3 Cấu trúc chỉ mục cây phân cấp trong biểu diễn iSAX ........................................43
3.3.1 Biểu diễn dữ liệu bằng phương pháp iSAX (indexable SAX) .................43
3.3.2 Cấu trúc chỉ mục cây phân cấp...............................................................48
3.3.3 Giải thuật truy vấn chuỗi láng giềng gần nhất (nearest neighbor) .........52

CHƯƠNG 4: HỆ THỐNG BIỂU DIỄN CHUỖI THỜI GIAN VÀ ỨNG DỤNG ..55
4.1 Đặt vấn đề………………. ..................................................................................55
4.2 Hướng giải quyết……….....................................................................................56
4.2.1 Biểu diễn dữ liệu chuỗi thời gian ...........................................................56
4.2.2 Độ đo tương tự .......................................................................................57
4.2.3 Cấu trúc chỉ mục ....................................................................................58
4.3 Kiến trúc hệ thống………...................................................................................59
4.4 Hoạt động của hệ thống…...................................................................................62
4.4.1 Môđun huấn luyện dữ liệu......................................................................62
4.4.2 Môđun biểu diễn dữ liệu ........................................................................68
4.4.3 Môđun so trùng mẫu ..............................................................................70
4.5 Kết luận…………………. ..................................................................................74
CHƯƠNG 5: THỰC NGHIỆM ................................................................................75
5.1 So sánh độ chặt của chặn dưới khoảng cách.......................................................75
5.1.1 Thực nghiệm trên tập dữ liệu Koski_ECG.............................................77
5.1.2 Thực nghiệm trên nhiều tập dữ liệu khác nhau......................................78
5.2 So sánh tỷ lệ thu giảm truy xuất..........................................................................78
5.3 So sánh số lần truy xuất đĩa trong quá trình tìm kiếm ........................................82
5.2.1 Thực nghiệm trên cấu trúc chỉ mục VA-File .........................................83
5.2.2 Thực nghiệm trên cấu trúc chỉ mục cây phân cấp..................................84

vi


5.3 Kết luận…………………. ..................................................................................85
Chương 6: KẾT LUẬN.............................................................................................86
6.1 Tổng kết…………………. .................................................................................86
6.2 Những đóng góp của đề tài .................................................................................87
6.3 Hướng phát triển………… .................................................................................87
DANH MỤC TÀI LIỆU THAM KHẢO..................................................................89

PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT .............................. i
PHỤ LỤC B: LÝ LNCH TRÍCH N GAN G................................................................ iv

vii


DANH MỤC HÌNH
Hình 1.1 Đường cong biểu diễn chuỗi thời gian.........................................................2
Hình 1.2 Cây tóm lược các cơng trình về biểu diễn chuỗi dữ liệu thời gian (nguồn
[17]).............................................................................................................................3
Hình 2.1 N hược điểm của độ đo Minkowski (nguồn [17]).......................................12
Hình 2.2 Sự khác nhau giữa hai độ đo Euclid và DTW (nguồn [17]) ......................13
Hình 2.3 Phương pháp tính khoảng cách DTW (nguồn [39])...................................15
Hình 2.4 Phương pháp chuỗi con chung dài nhất LCS (nguồn [33]) .......................16
Hình 2.5 Các phương pháp biểu diễn dữ liệu DFT, DWT, SVD (nguồn [17]) ........19
Hình 2.6 Các phương pháp biểu diễn dữ liệu APCA, PAA, PLA (nguồn [17]).......21
Hình 2.7 Phương pháp biểu diễn dữ liệu SAX (nguồn [17]) ....................................23
Hình 2.8 Xây dựng cây hậu tố từ S1={4, 5, 6, 7, 6, 6} và S2={4, 6, 7, 8} (nguồn
[33])...........................................................................................................................25
Hình 2.9 Một số từ mã được huấn luyện bởi GLA (nguồn [30])..............................26
Hình 2.10 Phương pháp xén và mã hóa dữ liệu ở mức bit (nguồn [37]) ..................27
Hình 2.11 Phương pháp biểu diễn dữ liệu iSAX (nguồn [40]) .................................28
Hình 2.12 Sự phân chia MBR và cấu trúc chỉ mục R-Tree (nguồn [12]).................29
Hình 2.13 Phương pháp đánh chỉ mục trong framework GEMIN I (nguồn [10]).....32
Hình 3.1 Các bước chạy giải thuật k-means với 3 cụm (nguồn [29]) .......................35
Hình 3.2 Phân bố các điểm trên hai chiều Ox và Oy (nguồn [42]) ...........................37
G G

Hình 3.3 Minh họa chặn trên và chặn dưới với công thức tính khoảng cách Lp (vq , vi )
(nguồn [42]) ..............................................................................................................39

Hình 3.4. Mã giả giải thuật VA-SSA (nguồn [42]) ....................................................41

viii


Hình 3.5 Mã giả giải thuật VA-NOA (nguồn [42])....................................................42
Hình 3.6 Phương pháp chuNn hóa trung bình zero (nguồn [17]) ..............................43
Hình 3.7 Q trình thu giảm số chiều 16 Ỉ 4 bằng PAA (nguồn [40]) ...................44
Hình 3.8 Bảng tra giá trị điểm ngắt theo hàm phân phối Gauss (nguồn [26])..........45
Hình 3.9 Rời rạc hóa dữ liệu dùng phương pháp iSAX (nguồn [40]) ......................45
Hình 3.10 Bảng tra khoảng cách cho 4 mức phân giải (nguồn [40])........................47
Hình 3.11 Cấu trúc chỉ mục cây phân cấp cho iSAX (nguồn [40]) ..........................48
Hình 3.12 Mã giả giải thuật chèn một chuỗi dữ liệu vào cấu trúc chỉ mục (nguồn
[40])...........................................................................................................................51
Hình 3.13 Mã giả giải thuật tìm kiếm chính xác (nguồn [40]) .................................54
Hình 4.1 Minh họa tỷ lễ lỗi khi tăng kích thước dữ liệu giữa 2 độ đo Euclid và
DTW trên 2 dataset (nguồn [40]) ..............................................................................58
Hình 4.2 Kiến trúc hệ thống......................................................................................61
Hình 4.3 Mơđun huấn luyện dữ liệu .........................................................................62
Hình 4.4 ChuNn hóa trung bình zero (nguồn [17])....................................................64
Hình 4.5 Biến đổi PAA .............................................................................................65
Hình 4.6 Mã giả giải thuật gom cụm k-means một chiều .........................................66
Hình 4.6 Một số tập các điểm ngắt thu được từ quá trình huấn luyện......................67
Hình 4.7. Biểu diễn aSAX ........................................................................................69
Hình 4.8 Mã giả giải thuật tìm kiếm xấp xỉ ..............................................................72
Hình 4.9 Mã giả giải thuật tìm kiếm chính xác.........................................................73
Hình 5.1 So sánh độ chặt của chặn dưới khoảng cách Euclid của các phương pháp
iaSAX, iSAX, aSAX, SAX, PAA trên tập dữ liệu Koski ECG................................78

ix



Hình 5.2 So sánh độ chặt của chặn dưới khoảng các Euclid của các phương pháp
iaSAX, iSAX, aSAX, SAX, PAA trên 12 tập dữ liệu với mức thu giảm chiều 32 : 1,
16 : 1 và 8 : 1.............................................................................................................79
Hình 5.3 So sánh tỉ lệ thu giảm truy xuất của các phương pháp iaSAX, iSAX,
aSAX, SAX trên 3 tập dữ liệu Koski ECG, Foetal ECG và Muscle Activation với

nhiều mức thu giảm chiều khác nhau .......................................................................81
Hình 5.4 So sánh tỉ lệ thu giảm truy xuất của các phương pháp iaSAX, iSAX,
aSAX, SAX trên 3 tập dữ liệu Koski ECG, Foetal ECG và Muscle Activation với

nhiều mức thu giảm chiều khác nhau........................................................................84
Hình 5.5 Minh họa số lần truy xuất đĩa trên tập dữ liệu RandomWalk và Koski
ECG trên cấu trúc chỉ mục VAFile ..........................................................................84
Hình 5.6 Minh họa chỉ số số lần truy xuất đĩa trên tập dữ liệu RandomWalk và
Koski ECG trên cấu trúc chỉ mục cây phân cấp ......................................................85

x


CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ
1.1 Dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian hay chuỗi thời gian thường xuất hiện trong nhiều ứng dụng
cụ thể cũng như các cơng trình nghiên cứu… Để dễ dàng tìm hiểu, chúng ta cần đưa
ra định nghĩa cụ thể về chuỗi thời gian.
Chuỗi thời gian (time series) là tập hợp các quan sát tuần tự theo thời gian. Dữ
liệu này có thể có hai hay nhiều chiều nhưng phải có một chiều là chiều thời gian.
Có rất nhiều dữ liệu có yếu tố thời gian như dữ liệu về giá chứng khoán, điện tâm
đồ, mực nước sông, số truy cập một trang web trong một giây… Thông thường,

chuỗi thời gian thường rất lớn. Do đó, việc khai phá chuỗi thời gian cần phải sử
dụng những cơng cụ máy tính nhằm tăng khả năng phân tích, tính tốn và xử lý.
Chính vì vậy, việc nghiên cứu và khai phá chuỗi thời gian đang được nghiên cứu
nhiều trong lĩnh vực khoa học máy tính và các lĩnh vực khác.
Trong phạm vi nghiên cứu của đề tài này, chuỗi thời gian được biểu diễn bằng
một chuỗi các số thực tương ứng X = x1 x2 ...xn , trong đó xi là giá trị đo ở thời điểm
thứ i. Một đường cong biểu diễn chuỗi thời gian được minh họa trong hình 1.1.
N hững khó khăn và thách thức khi nghiên cứu chuỗi thời gian [22]
o Dữ liệu quá lớn
Ví dụ: trong 1 giờ, dữ liệu điện tâm đồ (ECG) là 1 GigaByte.
o Phụ thuộc nhiều yếu tố chủ quan
Việc đánh giá mức độ tương tự giữa các dữ liệu phụ thuộc vào yếu tố chủ
quan của người dùng, của tập dữ liệu…
o Sự không đồng nhất của dữ liệu
Định dạng của các loại dữ liệu khác nhau, tần số lấy mẫu khác nhau.
N goài ra, dữ liệu có thể bị nhiễu, thiếu một vài giá trị, hoặc không sạch…

1


Hình 1.1 Đường cong biểu diễn chuỗi thời gian

1.2 Biểu diễn chuỗi thời gian
Trong hầu hết các bài toán về chuỗi thời gian, đặc biệt là bài toán cơ sở, tìm kiếm
tương tự (similarity search) và lập chỉ mục (indexing), việc biểu diễn dữ liệu
(representation of data) chính là nhân tố quan trọng nhất ảnh hưởng đến hiệu suất
cũng như kết quả của bài tốn. N gồi ra, nhiều bài tốn khác cũng sử dụng kết quả
bài tốn tìm kiếm tương tự để giải quyết vấn đề. Ví dụ: bài tốn gom cụm
(clustering), phân loại (classification), tìm quy luật của dữ liệu (rule discovery),
phát hiện điểm bất thường (novelty detection), tìm mẫu lặp (finding motif), dự báo

dữ liệu (prediction) trong tương lai… Do vậy, việc tìm ra những cách thức biểu
diễn chuỗi thời gian thích hợp đang là một thách thức lớn trong cộng đồng các nhà
khoa học nghiên cứu về chuỗi thời gian.

2


Biểu diễn chuỗi thời gian hợp lý giúp khắc phục được những yếu tố khó khăn
đặc thù của chuỗi thời gian như dữ liệu quá lớn (tốn chi phí I/O và CPU khi truy
xuất dữ liệu và tính tốn), sự khơng đồng nhất dữ liệu (kết quả tính tốn khơng
chính xác)… Trong phần lớn các cơng trình về biểu diễn chuỗi thời gian, các
phương pháp biểu diễn đều tập trung làm thu giảm số chiều (dimensionality
reduction) và bảo toàn độ đo tương tự (similarity measure) trên không gian biểu
diễn mới, nhằm thu giảm tối đa chi phí tính tốn cũng như tăng độ chính xác của kết
quả. Hình 1.2 tóm lược các cơng trình về biểu diễn chuỗi thời gian.

Time Series Representations

Model Based
Hidden
Markov
Models

Data Adaptive

Data Dictated

N on Data Adaptive

Grid


Statistical
Models
Sorted
Coefficients

Piecewise
Polynomial

Piecewise
Linear
Approximation

Interpolation

Regression

Singular
Symbolic
Value
Approximation

Adaptive
Piecewise
Constant
Approximation
Indexable
SAX

Natural

Language

Trees

Wavelets

Strings

Symbolic
Aggregate
Approximation
(SAX)

Orthonormal

N on
Lower
Bounding

Value
Based

Haar

Daubechies
dbn n > 1

Random
Mappings


Spectral

Bi-Orthonormal Discrete

Fourier
Transform

Coiflets

Clipped
Data

Piecewise
Aggregate
Approximation

Discrete Chebyshev
Cosine Polynomials
Transform

Symlets

Slope Based

Hình 1.2 Cây tóm lược các cơng trình về biểu diễn chuỗi dữ liệu thời gian
(nguồn [17])
o Biểu diễn dựa trên mơ hình (Model Based)
Chuỗi ban đầu và chuỗi truy vấn được biểu diễn dựa trên các đặc điểm đã
định nghĩa trước như sự tăng, giảm, khơng đổi… Sau đó, từ chuỗi dữ liệu
ban đầu này ta xây dựng mơ hình xác suất chuyển trạng thái như mơ hình


3


Markov ẩn (Hidden Markov Model HMM) [5][34], mơ hình ARMA
(Autogressive moving average model ARMA) [4]… dựa trên những đặc điểm
hữu hạn đã được định nghĩa trước. Sau đó, chúng ta rời rạc hóa chuỗi thời
gian thành chuỗi các đặc điểm và áp dụng giải thuật Markov để tính xác suất
cho các chuỗi đặc điểm. Qua đó đánh giá độ tương tự của các chuỗi thời
gian.
o Biểu diễn thích nghi dữ liệu (Data Adaptive)
Dữ liệu ở miền thời gian được rút trích đặc trưng (feature) thơng qua các
phép biến đổi. Ma trận chuyển đổi (transform matrix) được tính tốn dựa
trên tất cả các giá trị của chuỗi thời gian. Khi tập dữ liệu thay đổi, chúng ta
cần phải khởi động lại giải thuật. Do đó, phương pháp này thường được sử
dụng trong một số tập dữ liệu cụ thể, chuyên biệt. Một số phương pháp phổ
biến như phân rã giá trị riêng SVD [25], xấp xỉ tuyến tính từng đoạn PLA
[21][24], xấp xỉ hằng số từng đoạn thích nghi APCA [20], xấp xỉ gộp ký hiệu
hóa SAX [26].
o Biểu diễn khơng thích nghi dữ liệu (Non Data Adaptive)
Trong phép biểu diễn này, ma trận chuyển đổi (transform matrix) được xác
định trước và độc lập với tập dữ liệu. Phương pháp này sử dụng các phép
biến đổi tín hiệu trong xử lý tín hiệu số như biến đổi Fourier rời rạc DFT
[1][10], biến đổi Wavelet rời rạc DWT [6][7]. N goài ra, phương pháp xấp xỉ
gộp từng đoạn PAA [19][44] cũng được sử dụng rất phổ biến bởi tính bảo
tồn khoảng cách (khoảng cách Minkowski, khoảng cách Euclid, xoắn thời
gian động…).
o Biểu diễn điều khiển bởi dữ liệu (Data Dictated)
Trong tất cả cách cách biểu diễn trên, chúng ta cần phải gán những thông số
khởi động cho giải thuật như số lượng đặc trưng cần rút trích (DFT, DWT…)

hay số lượng các giá trị cần tính trung bình (PAA)... Tương ứng với mỗi loại
dữ liệu, mỗi phương pháp biểu diễn cần được khởi động bởi những thông số

4


khác nhau. Tuy nhiên, trong phương pháp biểu diễn này, tự bản thân dữ liệu
sẽ tạo ra thông số cần thiết cho việc biểu diễn. N ói cách khác, tự bản thân dữ
liệu quy ước các thơng số cho chính giải thuật. Phương pháp xén dữ liệu
(Clipped Data) [4][34] là một ví dụ. Phương pháp này được sử dụng kết hợp
với các mơ hình thống kê (mơ hình ARMA hay mơ hình Markov Nn HMM)
để tạo ra kết quả tốt hơn cho bài toán gom cụm [5].

1.3 Mục tiêu và giới hạn của đề tài
Mục tiêu chính của luận văn là biểu diễn chuỗi dữ liệu thời gian ở dạng bit nhằm
mục đích thu giảm số chiều nhưng vẫn bảo tồn độ đo tương tự. Khi đó, chuỗi dữ
liệu ban đầu là những số thực, thường được lưu trữ trong bộ nhớ với kích thước lớn
sẽ được biểu diễn thành các chuỗi bit với không gian lưu trữ nhỏ. N hờ vậy, việc tính
tốn, khai phá dữ liệu sẽ hiệu quả hơn và tốn ít chi phí hơn. Mặt khác, nhờ việc kết
hợp những cấu trúc chỉ mục dành cho các chuỗi bit như cấu trúc chỉ mục file xấp xỉ
hóa vectơ (Vector Approximation File – VA-File) [42] hay cấu trúc chỉ mục cây
phân cấp (hierarchical tree) [40], bài toán cơ sở tìm kiếm tương tự sẽ được giải
quyết một cách hiệu quả với mức chi phí I/O rất thấp trong quá trình truy vấn dữ
liệu.
Sau khi khảo sát các phương pháp biểu diễn dữ liệu chuỗi thời gian cùng với các
cấu trúc chỉ mục tương ứng với mỗi cách biểu diễn, chúng tơi đề xuất cách tiếp cận
bài tốn biểu diễn chuỗi dữ liệu thời gian ở mức bit theo hướng sau:
o Thu giảm số chiều bằng phương pháp xấp xỉ gộp từng đoạn PAA do E.
Keogh và cộng sự đề nghị [19].
o Huấn luyện dữ liệu nhằm tìm ra những điểm ngắt (breakpoints) thích hợp

nhất cho q trình rời rạc hóa dữ liệu. Thơng số đầu vào của giải thuật huấn
luyện sẽ là những điểm ngắt trong phương pháp xấp xỉ gộp ký hiệu hóa SAX
do J. Lin và cộng sự đề nghị [26] và các thông số thu giảm chiều trong
phương pháp PAA trước đó.

5


o Rời rạc hóa dữ liệu ở mức bit bằng phương pháp xấp xỉ gộp ký hiệu hóa khả
chỉ mục iSAX do J. Shieh và cộng sự đề nghị [40] với các điểm ngắt đã được
xác định trước trong quá trình huấn luyện.
o Xây dựng độ đo tương tự dựa trên các điểm ngắt nói trên.
o Sử dụng cấu trúc chỉ mục file xấp xỉ hóa vectơ VA-File và cây phân cấp
nhằm hạn chế hiện tượng vùng phủ lấp (overlapping region) trong các cấu
trúc chỉ mục không gian R-Tree hay R*-Tree… và thu giảm số lần truy xuất
đĩa (disk I/Os) trong quá trình tìm kiếm.
o Xây dựng và cải tiến cấu trúc chỉ mục VA-File cũng như giải thuật truy vấn
(query algorithm) trên cấu trúc chỉ mục VA-File cho tương thích với kiểu
biểu diễn mới này.
o Hiện thực và kiểm nghiệm bài tốn tìm kiếm tương tự dựa trên các tiêu chí:
độ chặt của chặn dưới độ đo tương tự (tightness of lower bound), tỉ lệ phần
trăm số lần truy xuất đĩa (percentage of disk I/Os) khi truy vấn dữ liệu trên
cấu trúc chỉ mục cây phân cấp và VA-File.
o Xây dựng một kiến trúc hệ thống tổng quát cho tất cả các bài toán liên quan
đến khai phá chuỗi dữ liệu thời gian.

1.4 Tóm lược những kết quả đạt được
Với những yêu cầu của đề tài, sau thời gian nghiên cứu và hiện thực, chúng tôi đã
xây dựng hệ thống tổng quát cho các bài toán liên quan đến dữ liệu chuỗi thời gian.
Trong giới hạn thời gian hiện thực, chúng tơi đã hiện thực 3 mơđun chính trong hệ

thống, bao gồm: môđun huấn luyện dữ liệu, môđun biểu diễn chuỗi dữ liệu thời gian
ở mức bit cùng với cấu trúc chỉ mục tương ứng, môđun so trùng mẫu nhằm giải
quyết bài tốn tìm kiếm tương tự một cách tối ưu.
Trong môđun thứ nhất, chúng tôi tiến hành huấn luyện dữ liệu nhằm tìm ra các
điểm ngắt (breakpoints) thích hợp nhất đối với từng loại dữ liệu. Tập điểm ngắt này

6


được sử dụng trong các môđun kế tiếp nhằm biểu diễn dữ liệu ở mức bit, đánh chỉ
mục và thực thi q trình tìm kiếm tương tự.
Trong mơđun thứ hai, chúng tôi cải tiến phương pháp xấp xỉ gộp ký hiệu hóa
hóa, (Symbolic Aggregate approXimation - SAX) [26] nhằm cải thiện độ chặt của
chặn dưới (tightness of lower bound) và hạn chế số lần truy xuất đĩa (disk I/Os)
trong quá trình tìm kiếm. Phương pháp này được đặt tên là phương pháp xấp xỉ gộp
ký hiệu hóa thích nghi (adaptive Symbolic Aggregate approXimation – aSAX) và
được mở rộng thành phương pháp xấp xỉ gộp ký hiệu hóa thích nghi khả chỉ mục
(indexable adaptive SAX - iaSAX) nhằm thích hợp với cấu trúc chỉ mục cây phân
cấp. Hai phương pháp biểu diễn nói trên aSAX và iaSAX cho kết quả hiệu quả hơn
hai phương pháp SAX và iSAX do nhóm của E. Keogh đề nghị [26][40] trong bài
tốn tìm kiếm tương tự. Chúng tôi đã sử dụng hai cấu trúc chỉ mục thích hợp nhất
đối với biểu diễn bit của dữ liệu chuỗi thời gian là: cấu trúc chỉ mục file xấp xỉ hóa
vectơ (VA-File) đối với biểu diễn aSAX và cấu trúc chỉ mục cây phân cấp
(hierarchical tree) đối với biểu diễn iaSAX. N gồi ra, chúng tơi đã cải tiến phương
pháp đánh chỉ mục VA-File tương thích với hai phương pháp biểu diễn aSAX và
iaSAX nhằm thu giảm chi phí truy xuất đĩa trong q trình truy vấn dữ liệu. Việc kết
hợp hai cấu trúc chỉ mục nói trên với hai phương pháp biểu diễn dữ liệu mới aSAX
và iaSAX đã nâng cao hiệu quả tìm kiếm cũng như thu giảm thời gian xây dựng cấu
trúc chỉ mục.
Môđun thứ ba sẽ thực thi quá trình so trùng chuỗi. Trong quá trình này, việc xác

định độ tương tự giữa các mẫu là quan trọng nhất. Cũng tương tự như các nghiên
cứu khác, chúng tôi sử dụng khoảng cách Euclid làm độ đo tương tự. Tuy nhiên,
ứng với mỗi loại cấu trúc chỉ mục nêu trên, chúng tôi sẽ đề ra những cách thức tính
tốn chặn dưới của độ đo (lower bound) và xây dựng một mơ hình truy vấn chung
cho cả hai loại chỉ mục nói trên.

7


N gồi ra, trong q trình hiện thực hệ thống, chúng tôi đã đề ra những hướng
mở rộng và ứng dụng của hai phương pháp biểu diễn nói trên trên nhiều phương
diện:
o Cải thiện độ chặt của chặn dưới khoảng cách.
o Tổng quát hóa cấu trúc chỉ mục trên chuỗi biểu diễn bit
o Tăng hiệu suất quá trình truy vấn
o Xây dựng ứng dụng so trùng mẫu đoạn nhạc nhằm hạn chế hiện tượng ăn cắp
bản quyền trong âm nhạc.
N hư vậy, hệ thống đã hiện thực mà chúng tôi sẽ trình bày chi tiết ở những
chương sau đã đáp ứng những yêu cầu và nhiệm vụ của đề tài.

1.5 Cấu trúc của luận văn
Tổ chức của phần còn lại của luận văn theo cấu trúc như sau:
Chương II là tổng quan về các cơng trình liên quan. N hững cơng trình này trình
bày những phương pháp biểu diễn dữ liệu chuỗi thời gian bằng cách thu giảm số
chiều, mã hóa và cải thiện hiệu suất tìm kiếm tương tự dựa trên những cấu trúc chỉ
mục thích hợp.
Chương III giới thiệu một số lý thuyết phức tạp mà chúng ta sẽ sử dụng trong
luận văn. Trước hết đó là giải thuật lượng tử hóa tối ưu (optimal quantization) được
đưa ra bởi Lloyd, S. P. năm 1982 [28] hay còn được gọi là giải thuật gom cụm kmeans (k-means clustering) [29]. Giải thuật này sẽ được dùng để huấn luyện dữ
liệu, nhằm tìm ra những điểm ngắt thích hợp nhất cho phương pháp aSAX và iaSAX

đối với mỗi kiểu dữ liệu. Sau đó là các lý thuyết về cấu trúc chỉ mục cùng với các
giải thuật truy vấn thích hợp với biểu diễn bit của dữ liệu: cấu trúc VA-File và cấu
trúc cây phân cấp.
Chương IV trình bày những vấn đề đặt ra khi biểu diễn dữ liệu ở mức bit cùng
với bài tốn tìm kiếm tương tự. Trong chương này, chúng tơi sẽ phân tích những

8


vấn đề chính mà hệ thống cần phải giải quyết: định nghĩa 2 mẫu tương tự nhau, biểu
diễn dữ liệu mức bit hợp lý, phương pháp đánh chỉ mục cùng với giải thuật truy vấn
tương ứng. Sau đó chúng tơi sẽ trình bày từng bước cách giải quyết các vấn đề trên.
Chương V là một số kết quả thực nghiệm.
Chương VI là một số kết luận và hướng mở rộng của đề tài.

9


CHƯƠNG 2: TỔNG THUẬT CÁC CƠNG TRÌNH
LIÊN QUAN
Chương 2 sẽ tổng thuật các cơng trình về độ đo tương tự, các phương pháp biểu
diễn dữ liệu chuỗi thời gian và các phương pháp lập chỉ mục.

2.1 Các cơng trình về độ đo tương tự
Trong mọi bài toán về chuỗi thời gian, vấn đề quan trọng nhất là phương pháp tính
khoảng cách của hai đối tượng O1, O2. Hai đối tượng được xem là giống nhau khi
khoảng cách giữa chúng là 0, là tương tự nhau khi khoảng cách giữa chúng nhỏ hơn
giá trị ε được quy ước trước đó. Để có thể tính tốn và so sánh thì khoảng cách này
được biểu diễn thành các số thực và phải thỏa các tính chất sau:
1. D(x, y) = 0 nếu và chỉ nếu x = y

2. D(x, y) = D(y, x)
3. D(x, y) >= 0 với mọi x, y
4. D(x, y) < D(x, z) + D(y, z)
Dễ thấy rằng tính chất 1 và 2 là rất trực quan. Tính chất 3 cần thiết trong trường
hợp khi tồn tại một số thành phần khác nhau có khoảng cách nhỏ hơn 0 nhưng tổng
khoảng cách của các thành phần có thể bằng 0 dẫn đến 2 đối tượng được xem là
giống nhau. Điều này là trái với tính chất 1. Tính chất 4 không bắt buộc thỏa đối với
các phép đo khoảng cách. Tuy nhiên, nó được sử dụng nhằm hỗ trợ kỹ thuật lập chỉ
mục, giảm thời gian tính tốn. Với kỹ thuật này, từ những kết quả tính tốn đã biết,
ta có thể bỏ qua những khơng gian tìm kiếm mà chắc chắn khơng có lời giải thỏa
mãn u cầu. Do đó, thời gian tính tốn sẽ giảm.
Đối với bài tốn tìm kiếm tương tự trên dữ liệu chuỗi thời gian thì dữ liệu được
biểu diễn thành các dãy số thực X = {x1 , x2 ,..., xn }, Y = {y1 , y 2 ,..., yn } . Ta cần phải tính

10


độ tương tự Sim(X,Y) của 2 mẫu này. Chúng ta sẽ xem xét những phương pháp đánh
giá mức độ tương tự phổ biến được đề nghị trong [1][2][3][18][19][33][44].

2.1.1 Độ đo Minkowski
Sim( X , Y ) =

n

p

∑ (x − y )
i =1


i

p

i

trong đó,
p = 1 (Độ đo Manhattan)
p = 2 (Độ đo Euclid)
p = ∞ (Độ đo Max)
Tuy p có thể có nhiều sự lựa chọn khác nhau, nhưng trong các nghiên cứu đối
với chuỗi thời gian thì thường sử dụng p = 2 (độ đo Euclid).
Ưu điểm
o Tính tốn dễ dàng.
o Có khả năng mở rộng cho nhiều bài tốn khác như phân loại, gom cụm…
Đặc biệt, độ đo này rất thích hợp khi ta sử dụng các phép biến đổi thu giảm
chiều như: DFT [10], DWT [6], PAA [19][44], hay APCA [20]...
Nhược điểm
o N hạy cảm với nhiễu.
o Không thích hợp khi dữ liệu có đường cơ bản (base line) khác nhau (Hình
2.1a): ví dụ như giá chứng khống của A và B thay đổi rất giống nhau nhưng
A dao động ở 100 còn B dao động ở mức 40. N hư vậy A và B là rất khác
nhau mặc dù hình dáng rất giống nhau.
o Khơng thích hợp khi dữ liệu có biên độ dao động khác nhau (Hình 2.1b):
Trong trường hợp giá chứng khốn của 2 cơng ty A và B thay đổi rất giống
nhau nhưng mà biên độ dao động của A là 20 và 80 còn biên độ dao động
của B là 30 và 50 thì độ tương tự của A và B là rất khác nhau.

11



(1) Đường cơ bản khác nhau

(2) Biên độ dao động khác nhau

Hình 2.1 Nhược điểm của độ đo Minkowski (nguồn [17])
Khắc phục
o Phương pháp chuẩn hóa dữ liệu (Data normalization)
a) Chuẩn hóa trung bình zero (Zero-Mean normalization) [22]
Chuỗi Q được biến đổi thành chuỗi Q’ dựa trên giá trị trung bình mean(Q) và
độ lệch chuNn var(Q) theo cơng thức sau:
Q’[i] = (Q[i]- mean(Q)) / var(Q)
b) Chuẩn hóa nhỏ nhất – lớn nhất (Min-Max normalization) [2]
Chuỗi Q được biến đổi thành chuỗi Q’ dựa trên giá trị lớn nhất Qmax và giá trị
nhỏ nhất Qmin theo công thức sau:

Q′[i ] =

Qmax + Qmin
2
Qmax − Qmin
2

Q[i ] −

12