ĐẠI
Đ HỌC QUỐC GIA TP.HCM
TRƯ
TRƯỜNG ĐẠI HỌC BÁCH KHOA

LÊ MINH NHỰT

PHÁT HIỆN
ỆN MƠ TÍP VỚI CHIỀU DÀI
DÀI KHÁC NHAU TRÊN
DỮ
Ữ LIỆU CHUỖI THỜI GIAN

CHUYÊN NGÀNH
NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ
S CHUYÊN NGÀNH: 60.48.01

LUẬN VĂN THẠC SĨ

TP.HCM, tháng 06 năm 2013


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG - HCM
Cán bộ hướng dẫn khoa học : ............................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 1 : ..................................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 2 : ..................................................................................
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)

Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM
ngày . . . . . tháng . . . . năm . . . . .
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ)
1. .......................................................................
2. .......................................................................
3. .......................................................................
4. .......................................................................
5. .......................................................................
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên
ngành sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA…………


ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
----------------

CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc
-----------------

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Lê Minh Nhựt………...................................Giới tính: Nam ฀/ Nữ ฀
Ngày, tháng, năm sinh: 02/06/1985..............................................Nơi sinh: TP.HCM.....................
Chuyênngành: Khoa học Máy tính……………………………….Mã số: 60.48.01…………………
1-TÊN ĐỀ TÀI:
PHÁT HIỆN MƠ TÍP VỚI CHIỀU DÀI KHÁC NHAU TRÊN DỮ LIỆU CHUỖI THỜI

GIAN
2-NHIỆM VỤ VÀ NỘI DUNG:
.........................................................................................................................................................
...............................................................................................................................................................
...............................................................................................................................................................
..................................................................................................................................................
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…………………………..
Tp.HCM, ngày. .. . tháng. .. . năm 2013
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ kí)

PGS.TS Dương Tuấn Anh

CHỦ NHIÊM BỘ MƠN ĐÀO TẠO
(Họ tên và chữ kí)


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

LỜI CẢM ƠN
Để hoàn thành luận văn này, tôi đã nhận được sự giúp đỡ và góp ý của nhiều
người. Đầu tiên, tơi xin gửi lời cảm ơn chân thành đến PGS TS. Dương Tuấn Anh,
người đã hướng dẫn tơi xun suốt q trình thực hiện luận văn. Với một sự tâm
huyết không quản thời gian, cơng sức, thầy đã tận tình chỉ bảo và góp ý cho đề tài
này của tôi.
Tiếp theo, tôi xin cảm ơn các q thầy, cơ trong khoa, những người đã cung cấp
cho tôi những kiến thức cần thiết để thực hiện luận văn này.
Cuối cùng, tôi xin cảm ơn các anh chị và các bạn trong lớp cũng như cùng nhóm

nghiên cứu đã giúp đỡ, góp ý cho tơi trong suốt q trình làm luận văn.
Một lần nữa tơi xin gửi lời cảm ơn chân thành đến tất cả mọi người.

Lê Minh Nhựt – 10070491

i


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

TÓM TẮT LUẬN VĂN
Ngày nay, với sự phát triển không ngừng của khoa học kỹ thuật thì việc lưu trữ,
khai phá và phân tích dữ liệu chuỗi thời gian trở nên quan trọng trong cuộc sống
con người.
Tìm kiếm mơ típ trên tập dữ liệu chuỗi thời gian là một trong những kỹ thuật
phổ biến trong việc khai phá dữ liệu chuỗi thời gian. Việc phát hiện mơ típ giúp
chúng ta xác định các đặc trưng của dữ liệu chuỗi thời gian, cũng như dự đoán sự
thay đổi của dữ liệu trong tương lai.
Thấy được tầm quan trọng của việc phát hiện mơ típ trên dữ liệu chuỗi thời
gian, các nhà khoa học đã có nhiều cơng trình nghiên cứu để giải bài tốn này. Họ
đã đưa ra nhiều giải thuật khác nhau, với cách tiếp cận khác nhau để giải quyết vấn
đề. Tuy nhiên, một hạn chế phổ biến trong các cơng trình nghiên cứu đã có là chỉ
tập trung phát hiện những mơ típ có chiều dài cố định. Điều này có nghĩa là chiều
dài của mơ típ cần tìm phải được xác định trước để cung cấp cho giải thuật hoạt
động. Do đó, các giải thuật đó chỉ có thể phát hiện ra các mơ típ có chiều dài đã
định trước trong chuỗi dữ liệu thời gian mà chúng không thể phát hiện những mơ típ
khác có thể có, với chiều dài khác chiều dài được cung cấp.
Với những hạn chế của những giải thuật phát hiện mơ típ dựa vào chiều dài cố
định, một nhu cầu được đặt ra là tìm một giải thuật có thể phát hiện mơ típ mà
khơng cần biết trước chiều dài của chúng. Đề tài này sẽ xem xét một giải thuật như

thế, nó có thể phát hiện hầu hết các mơ típ với chiều dài khác nhau trong chuỗi thời
gian. Giải thuật được nêu ra bởi Heng Tang và Stephen Liao [7] có khả năng phát
hiện mơ típ mà khơng cần biết trước thơng tin nào về dữ liệu đang xem xét. Giải
thuật dựa vào nền tảng giải thuật chiếu ngẫu nhiên và ma trận đụng độ của các
chuỗi con để giải quyết vần đề. Đề tài này sẽ tiến hành nghiên cứu, hiện thực và thử
nghiệm giải thuật trên và so sánh kết quả thực nghiệm với giải thuật phát hiện mơ
típ dựa vào điểm cực trị quan trọng.

Lê Minh Nhựt – 10070491

ii


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

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 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 Đại học Bách Khoa TP.HCM hay một trường nào khác.

Lê Minh Nhựt – 10070491

iii


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

MỤC LỤC
CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI .................................................................................. 1

1.1 Dữ liệu chuỗi thời gian............................................................................................ 1
1.2 Phát hiện mơ típ trên dữ liệu chuỗi thời gian .......................................................... 2
1.3 Mục tiêu và giới hạn của đề tài ............................................................................... 3
1.4 Tóm lược những kết quả thu được .......................................................................... 4
1.5 Cấu trúc luận văn .................................................................................................... 5
CHƯƠNG 2: TỔNG QUAN CÁC CƠNG TRÌNH LIÊN QUAN ..................................... 6
2.1 Các độ đo tương tự .................................................................................................. 6
2.1.1
Độ đo Euclid .................................................................................................... 6
2.1.2
Độ đo xoắn thời gian động............................................................................... 7
2.1.3
Độ đo chuỗi con chung dài nhất ...................................................................... 8
2.2 Các phương pháp thu giảm số chiều ....................................................................... 8
2.2.1
Các phương pháp biến đổi sang miền tần số ................................................... 8
2.2.2
Các phương pháp xấp xỉ từng đoạn ............................................................... 10
2.3 Tổng quan về các cơng trình liên quan ................................................................. 12
2.3.1
Giải thuật EMMA .......................................................................................... 13
2.3.2
Giải thuật chiếu ngẫu nhiên ........................................................................... 14
2.3.3
Giải thuật Mueen-Keogh ............................................................................... 15
2.3.4
Kết luận .......................................................................................................... 17
CHƯƠNG 3: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ ..... 18
3.1 Định nghĩa ............................................................................................................. 18
3.2 Thu giảm số chiều ................................................................................................. 21

3.3 Rời rạc hóa dữ liệu ................................................................................................ 22
3.4 Độ đo tương tự ...................................................................................................... 25
3.5 Giải thuật chiếu ngẫu nhiên................................................................................... 27
3.6 Giải thuật nối mơ típ ............................................................................................. 29
3.7 Tìm mẫu chung của các mơ típ ............................................................................. 32
3.8 Kết luận ................................................................................................................. 33
CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM ............................................................. 34
4.1 Mơ hình hiện thực ................................................................................................. 34
4.1.1
Phát hiện mơ típ có chiều dài khác nhau ....................................................... 34
4.1.2
Phát hiện mơ típ dựa vào điểm cực trị quan trọng ......................................... 36
4.2 Kết quả thực nghiệm ............................................................................................. 37
4.2.1
Dữ liệu điện tâm đồ với kích thước 7900 điểm ............................................. 38
4.2.2
Dữ liệu Memory kích thước 6800 điểm......................................................... 43
4.2.3
Dữ liệu Power kích thước 35000 điểm .......................................................... 49
4.2.4
Dữ liệu điện tâm đồ kích thước 144000 điểm ............................................... 54
4.3 Nhận xét kết quả thực nghiệm .............................................................................. 60
CHƯƠNG 5: KẾT LUẬN ................................................................................................ 62
5.1 Tổng kết ................................................................................................................ 62
5.2 Những đóng góp của đề tài ................................................................................... 62
5.3 Hướng phát triển của đề tài ................................................................................... 63
TÀI LIỆU THAM KHẢO ................................................................................................... 64
PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH VIỆT.............................................i

Lê Minh Nhựt – 10070491


iv


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

DANH MỤC HÌNH
Hình 1-1: Dữ liệu chứng khốn Việt Nam được ghi nhận lại. .................................. 2
Hình 1-2: Một chuỗi thời gian có sự xuất hiện của 3 chuỗi con tương tự nhau
A,B,C (hình trên). Hình phóng to của 3 chuỗi con A,B,C (hình dưới) (nguồn [5]). .. 3
Hình 2-1: Khoảng cách Euclid giữa hai chuỗi thời gian Q và C (Từ nguồn [5]). ..... 6
Hình 2-2: Độ đo xoắn thời gian động (nguồn [17]). ................................................ 7
Hình 2-3: Các phương pháp biến đổi sang miền tần số (nguồn [17]). .................... 10
Hình 2-4: Các phương pháp xấp xỉ từng đoạn (nguồn [17]). ................................. 12
Hình 2-5: Minh họa ý tưởng giải thuật MK (nguồn [6]). ....................................... 15
Hình 2-6: Minh họa việc cập nhật best-so-far của giải thuật MK (nguồn [6]). ....... 16
Hình 3-1: Xác định các chuỗi con của chuỗi thời gian bằng cách dùng cửa sổ trượt
có kích thước w (Từ nguồn [7]). ............................................................................ 19
Hình 3-2: Minh họa chuỗi thời gian T, hai chuỗi con C (nét đậm) và M (nét xám),
M trùng với C (Từ nguồn [4]). ............................................................................... 19
Hình 3-3: Minh họa chuỗi thời gian T, chuỗi con C và hai chuỗi trùng tầm thường
của C lệch về bên trái và bên phải của C một vài điểm (Từ nguồn [4]). ................. 20
Hình 3-4: Sự trùng lắp các thể hiện của hai mơ típ với D(Ck,Ci) > R (hình trên) và
sự tách biệt các thể hiện của hai mơ típ với D(Ck,Ci) > 2R (hình dưới) (nguồn [5]).
.............................................................................................................................. 21
Hình 3-5: Thu giảm số chiều của chuỗi thời gian C về chuỗi . có hình dạng bậc
thang (nguồn [5]). .................................................................................................. 22
Hình 3-6: Sự phân bố xác suất của một chuỗi con chiều dài 128 có dạng phân bố
Gauss (nguồn [5]). ................................................................................................. 23
Hình 3-7: Chuỗi thời gian được rời rạc hóa sử dụng PAA và SAX. Từ thu được là

baabccbc (nguồn [5]). ........................................................................................... 25
Hình 3-8: Khoảng cách giữa hai chuỗi thời gian được biểu diễn dưới dạng từ....... 27
Hình 3-9: Xây dựng ma trận từ chuỗi thời gian T có chiều dài m = 1000, chiều dài
mơ típ có trong chuỗi thời gian là 16, chiều dài từ là 4, tập ký hiệu gồm 3 ký tự. Số
lượng chuỗi con là (1000 -16 + 1) = 985, đây cũng là số dòng của ma trận (nguồn
[4]). ....................................................................................................................... 28

Lê Minh Nhựt – 10070491

v


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Hình 3-10: Các chuỗi con trong được băm vào các túi với mặt nạ được chọn là
cột 1,2 (hình bên trái) và trạng thái ma trận đụng độ với ô(1,58) và ô(2,985) được
tăng giá trị lên 1 (hình bên phải) (nguồn [4]). ........................................................ 29
Hình 3-11: Các chuỗi con trong được băm vào các túi với mặt nạ được chọn là
cột 2,4 (hình bên trái) và trạng thái ma trận đụng độ với ơ(1,58) có giá trị là 2 vì
được tăng giá trị thêm 1 (hình bên phải) (nguồn [4]).............................................. 29
Hình 3-12: Biểu diễn ma trận đụng độ của các chuỗi con. Các mơ típ nhỏ hơn tạo
thành các đoạn thẳng hướng lên trên (hình bên trái) và các mơ típ lớn thật sự của
chúng (hình bên phải) (nguồn [7]). ........................................................................ 30
Hình 3-13: Khu vực tìm kiếm được xác định bởi hằng số d (hình vng nét đứt),
hai vectơ là hai hệ số góc α1 và α2 giới hạn khu vực hợp lệ của hệ số góc (phần gạch
chéo) (nguồn [7]). .................................................................................................. 31
Hình 3-14: Sự trùng lắp các phân đoạn và sự đối xứng của chúng (nguồn [7])...... 32
Hình 3-15: Tìm mẫu tổng quát bằng cách cắt bỏ phần dư thừa và tính giá trị trung
bình của các phân đoạn (nguồn [7])....................................................................... 33
Hình 4-1: Mơ hình hoạt động của phương pháp phát hiện mơ típ có chiều dài khác
nhau. ..................................................................................................................... 35

Hình 4-2: Mơ hình hoạt động của phương pháp phát hiện mơ típ dựa vào điểm cực
trị quan trọng. ........................................................................................................ 36
Hình 4-3: Biểu diễn của dữ liệu điện tâm đồ có kích thước 7900 điểm. ................. 38
Hình 4-4: Kết quả hiển thị của chương trình sau khi chạy giải thuật MC trên dữ liệu
ECG 7900 điểm với w_PAA = 20, w = 20. ............................................................ 39
Hình 4-5: Các thể hiện của mơ típ dài nhất ứng với lớp tương đương 138 sau khi
chạy giải thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20. .......... 39
Hình 4-6: Mẫu chung thu được của mơ típ ứng với lớp 138sau khi chạy giải thuật
MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20. .................................. 40
Hình 4-7: Các thể hiện của mơ típ ứng với lớp tương đương 102 sau khi chạy giải
thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20........................... 40
Hình 4-8: Các thể hiện của mơ típ ứng với lớp tương đương 84 sau khi chạy giải
thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20........................... 41
Hình 4-9: Các thể hiện của mơ típ ứng với lớp tương đương 75 sau khi chạy giải
thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20........................... 41
Hình 4-10: Kết quả hiển thị của chương trình sau khi chạy giải thuật EP_C trên dữ
liệu ECG 7900 điểm. ............................................................................................. 42
Lê Minh Nhựt – 10070491

vi


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Hình 4-11: Biểu diễn mơ típ kết quả sau khi chạy giải thuật EP_C trên dữ liệu ECG
7900 điểm.............................................................................................................. 43
Hình 4-12: Biểu diễn của dữ liệu Memory có kích thước 6800 điểm. .................... 44
Hình 4-13: Kết quả hiển thị của chương trình sau khi chạy giải thuật MC trên dữ
liệu Memory 6800 điểm với w_PAA = 20, w = 20................................................. 45
Hình 4-14: Các thể hiện của mơ típ ứng với lớp tương đương 209 sau khi chạy giải
thuật MC trên dữ liệu Memory 6800 điểm với w_PAA = 20, w = 20. .................... 45

Hình 4-15: Các thể hiện của mơ típ ứng với lớp tương đương 132 sau khi chạy giải
thuật MC trên dữ liệu Memory 6800 điểm với w_PAA = 20, w = 20. .................... 46
Hình 4-16: Các thể hiện của mơ típ ứng với lớp tương đương 23 sau khi chạy giải
thuật MC trên dữ liệu Memory 6800 điểm với w_PAA = 20, w = 20. .................... 46
Hình 4-17: Các thể hiện của mơ típ ứng với lớp tương đương 21 sau khi chạy giải
thuật MC trên dữ liệu Memory 6800 điểm với w_PAA = 20, w = 20. .................... 47
Hình 4-18: Kết quả hiển thị của chương trình sau khi chạy giải thuật EP_C trên dữ
liệu Memory 6800 điểm......................................................................................... 48
Hình 4-19: Biểu diễn mơ típ kết quả sau khi chạy giải thuật EP_C trên dữ liệu
Memory 6800 điểm. .............................................................................................. 48
Hình 4-20: Biểu diễn của dữ liệu Power có kích thước 35000 điểm. ..................... 49
Hình 4-21: Kết quả hiển thị của chương trình sau khi chạy giải thuật MC trên dữ
liệu Power 35000 điểm với w_PAA = 20, w = 20. ................................................. 50
Hình 4-22: Các thể hiện của mơ típ ứng với lớp tương đương 385 sau khi chạy giải
thuật MC trên dữ liệu Power 35000 điểm với w_PAA = 20, w = 20. ..................... 51
Hình 4-23: Các thể hiện của mơ típ ứng với lớp tương đương 1302 sau khi chạy
giải thuật MC trên dữ liệu Power 35000 điểm với w_PAA = 20, w = 20. ............... 51
Hình 4-24: Các thể hiện của mơ típ ứng với lớp tương đương 1114 sau khi chạy
giải thuật MC trên dữ liệu Power 35000 điểm với w_PAA = 20, w = 20. ............... 52
Hình 4-25: Các thể hiện của mơ típ ứng với lớp tương đương 38 sau khi chạy giải
thuật MC trên dữ liệu Power 35000 điểm với w_PAA = 20, w = 20. ..................... 52
Hình 4-26: Kết quả hiển thị của chương trình sau khi chạy giải thuật EP_C trên dữ
liệu Power 35000 điểm. ......................................................................................... 53
Hình 4-27: Biểu diễn mơ típ kết quả sau khi chạy giải thuật EP_C trên dữ liệu
Power 35000 điểm. ............................................................................................... 54
Hình 4-28: Biểu diễn của dữ liệu ECG có kích thước 144000 điểm. ..................... 55
Lê Minh Nhựt – 10070491

vii



Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Hình 4-29: Kết quả hiển thị của chương trình sau khi chạy giải thuật MC trên dữ
liệu ECG 144000 điểm với w_PAA = 40, w = 10. ................................................. 56
Hình 4-30: Các thể hiện của mơ típ dài nhất ứng với lớp tương đương 4323sau khi
chạy giải thuật MC trên dữ liệu ECG 144000 điểm với w_PAA = 40, w = 10........ 57
Hình 4-31: Các thể hiện của mơ típ ứng với lớp tương đương 4134sau khi chạy giải
thuật MC trên dữ liệu ECG 144000 điểm với w_PAA = 40, w = 10....................... 57
Hình 4-32: Các thể hiện của mơ típ ứng với lớp tương đương 2074sau khi chạy giải
thuật MC trên dữ liệu ECG 144000 điểm với w_PAA = 40, w = 10....................... 58
Hình 4-33: Các thể hiện của mơ típ ứng với lớp tương đương 2083sau khi chạy giải
thuật MC trên dữ liệu ECG 144000 điểm với w_PAA = 40, w = 10....................... 58
Hình 4-34: Kết quả hiển thị của chương trình sau khi chạy giải thuật EP_C trên dữ
liệu ECG kích thước 144000 điểm. ........................................................................ 59
Hình 4-35: Biểu diễn mơ típ kết quả sau khi chạy giải thuật EP_C trên dữ liệu ECG
144000 điểm. ......................................................................................................... 60

Lê Minh Nhựt – 10070491

viii


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
Chương này sẽ trình bày sơ lược về nội dung và mục tiêu của đề tài. Đồng thời
chương này cũng nêu lên động cơ nghiên cứu, tầm quan trọng của những ứng dụng
trong thực tiễn và hướng giải quyết vấn đề của đề tài.
1.1 Dữ liệu chuỗi thời gian
Ngày nay, với sự phát triển không ngừng của khoa học kỹ thuật, lượng dữ liệu

được lưu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ …) không ngừng
tăng lên. Qua thời gian, lượng dữ liệu này ngày càng phình to ra với tốc độ nhanh
chóng. Vấn đề đặt ra cho con người là làm sao để thu được những thơng tin hữu ích
từ khối dữ liệu khổng lồ này. Vì lý do đó, vấn đề khai phá dữ liệu để phục vụ nhu
cầu nghiên cứu và sử dụng của con người đã trở thành một vấn đề quan trọng và cần
thiết.
Một trong những loại dữ liệu quan trọng cần được khai phá là dữ liệu chuỗi thời
gian. Dữ liệu chuỗi thời gian được sinh ra từ các thí nghiệm khoa học cũng như hoạt
động sản xuất kinh doanh trong đời sống hằng ngày. Một số dạng dữ liệu chuỗi thời
gian mà ta có thể bắt gặp trong thực tế như giá của một mã chứng khoán qua các
ngày, giá cả của một mặt hàng trên thị trường qua từng ngày, doanh thu hoặc chi phí
kinh doanh của cơng ty qua các thời kỳ, lượng mưa đo đạt được từng ngày, dữ liệu
điện tâm đồ…Hình 1-1 minh họa một loại dữ liệu chuỗi thời gian được ghi nhận lại
là dữ liệu chứng khoán Việt Nam.
Một cách tổng quát, một dữ liệu chuỗi thời gian là một tập có thứ tự các số
thực, trong đó mỗi số thể hiện giá trị tại một thời điểm nào đó. Dữ liệu chuỗi thời
gian thường có kích thước rất lớn. Việc khai phá nó để rút trích những thơng tin có
ích ngày càng trở thành một nhu cầu cần thiết và được nhiều nhà khoa học tham gia
nghiên cứu, ứng dụng.
Mặc dù dữ liệu chuỗi thời gian là một đề tài hấp dẫn nhưng việc nghiên cứu nó
cũng gặp nhiều khó khăn và thách thức như dữ liệu quá lớn, phụ thuộc nhiều vào
cách đánh giá độ tương tự, dữ liệu thường không đồng nhất…
Lê Minh Nhựt – 10070491

Trang 1


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

Hình 1-1: Dữ liệu chứng khốn Việt Nam được ghi nhận lại.

1.2 Phát hiện mơ típ trên dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian tồn tại rất nhiều trong các ứng dụng thực tế, từ các lĩnh
vực khoa học kỹ thuật cho đến kinh tế, tài chính, sinh học và y học. Việc tìm kiếm
những chuỗi con truy vấn có xuất hiện trong dữ liệu chuỗi thời gian lớn hơn là một
công việc rất cần thiết. Đây là nền tảng cho việc phát triển cao hơn trong khai phá
dữ liệu chuỗi thời gian. Trong đó, việc phát hiện sự lặp đi lặp lại nhiều lần của một
chuỗi con (cịn gọi là mơ típ) trong một chuỗi thời gian lớn hơn đã trở thành một
nhu cầu thực tế. Hình 1-2 minh họa sự xuất hiện của 3 chuỗi con tương tự nhau trên
một dữ liệu chuỗi thời gian.
Một vài ứng dụng thực tế:
 Dự đoán giá vàng, tiền tệ hay chứng khốn dựa vào mơ hình biến động giá
của nó trong q khứ.
 Dự đốn diễn biến của một căn bệnh dựa vào dữ liệu diễn biến của nó trong
q khứ.
 Nhận dạng những cơng ty có kiểu mẫu tăng trưởng giống nhau.
 Xác định những chứng khốn có giá biến động theo một kiểu cách giống
nhau.

Lê Minh Nhựt – 10070491

Trang 2


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
 Phát hiện vi phạm bản quyền trong âm nhạc bằng cách tìm xem một đoạn
nhạc có tương tự với một đoạn nhạc nào trong tập hợp những bản nhạc đã có bản
quyền.

Hình 1-2: Một chuỗi thời gian có sự xuất hiện của 3 chuỗi con tương tự nhau
A,B,C (hình trên). Hình phóng to của 3 chuỗi con A,B,C (hình dưới) (nguồn [5]).

1.3 Mục tiêu và giới hạn của đề tài
Vấn đề phát hiện mơ típ trong dữ liệu chuỗi thời gian là một vấn đề thú vị và
mang tính thực tiễn cao. Nó thúc đẩy nhiều nhà khoa học tham gia nghiên cứu và họ
đã đưa ra nhiều cơng trình nghiên cứu giải quyết được bài tốn đặt ra. Các cơng
trình này đã nêu ra nhiều giải thuật khác nhau (EMMA [5], chiếu ngẫu nhiên [4],
Mueen-Keogh [6]…), với cách tiếp cận khác nhau để giải quyết vần đề. Tuy nhiên,
một hạn chế phổ biến trong các cơng trình nghiên cứu đã có là chỉ tập trung phát
hiện những mơ típ có chiều dài cố định. Điều này có nghĩa là chiều dài của mơ típ
cần tìm phải được xác định trước để cung cấp cho giải thuật hoạt động. Với cách
tiếp cận này, giải thuật chỉ có thể phát hiện ra các mơ típ có chiều dài đã định trước

Lê Minh Nhựt – 10070491

Trang 3


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
trong chuỗi dữ liệu thời gian. Chúng khơng thể phát hiện những mơ típ khác có thể
có, với chiều dài khác chiều dài được cung cấp.
Một hạn chế khác là việc xác định trước chiều dài mơ típ trong thực tế rất khó
khăn và có thể khơng chính xác. Nếu chiều dài mơ típ được cung cấp quá nhỏ so với
thực tế thì sẽ chỉ phát hiện ra những mơ típ nhỏ thuộc một mơ típ lớn hơn. Nếu
chiều dài mơ típ được cung cấp q lớn thì có khả năng giải thuật sẽ khơng phát
hiện được mơ típ.
Với những hạn chế của những giải thuật phát hiện mơ típ dựa vào chiều dài cố
định, một nhu cầu được đặt ra là tìm một giải thuật có thể phát hiện mơ típ mà
khơng cần biết trước chiều dài của nó. Đề tài này sẽ xem xét một giải thuật có khả
năng khắc phục hạn chế này, nó có thể phát hiện tất cả các mơ típ với chiều dài khác
nhau trong chuỗi thời gian. Giải thuật được nêu ra bởi Heng Tang và Stephen Liao
[7] có khả năng phát hiện mơ típ mà khơng cần biết trước thông tin nào về dữ liệu

đang xem xét. Giải thuật dựa vào nền tảng là giải thuật chiếu ngẫu nhiên và ma trận
đụng độ của các chuỗi con để giải quyết vần đề.
Trong luận văn này chúng tôi sẽ so sánh kết quả thực nghiệm thu được với giải
thuật nhận diện mơ típ dựa vào điểm cực trị quan trọng vì đây là giải thuật có thể
nhận thấy được các thể hiện khơng cùng chiều dài trong mơ típ và có biên độ dao
động khác nhau.
1.4 Tóm lược những kết quả thu được
Qua việc nghiên cứu, hiện thực đề tài này và sau đó thử nghiệm trên các tập dữ
liệu mẫu, chúng tôi thu được các kết quả sau:
 Giải thuật có khả năng phát hiện hầu hết các mơ típ có trong dữ liệu chuỗi
thời gian được thử nghiệm.
 Phát hiện được các mơ típ có chiều dài khác nhau, các thể hiện trong mơ típ
cũng có thể có chiều dài khác nhau.

Lê Minh Nhựt – 10070491

Trang 4


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
 Thời gian chạy tương đối nhanh trên các tập dữ liệu vừa và nhỏ (vài chục
ngàn điểm). Thời gian chạy chậm trên các tập dữ liệu lớn hoặc có hình thái biến đổi
giống nhau xun suốt chuỗi thời gian.
1.5 Cấu trúc luận văn
Phần còn lại của luận văn được tổ chức theo cấu trúc như sau:
Chương 2 trình bày tổng quan về các cơng trình liên quan đến bài tốn phát
hiện mơ típ trên dữ liệu chuỗi thời gian.
Chương 3 giới thiệu những lý thuyết sẽ được sử dụng để thực hiện đề tài, đồng
thời xác định hướng tiếp cận để giải quyết vấn đề của đề tài.
Chương 4 tiến hành hiện thực và thực nghiệm giải thuật trên các tập dữ liệu

chuỗi thời gian khác nhau. Sau đó, chúng tơi so sánh kết quả thu được với giải thuật
nhận diện mơ típ dựa vào điểm cực trị quan trọng về khả năng phát hiện mơ típ có
chiều dài khác nhau, độ chính xác, tốc độ của giải thuật.
Chương 5 nêu lên một số kết luận sau khi thực hiện đề tài.

Lê Minh Nhựt – 10070491

Trang 5


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian

CHƯƠNG 2: TỔNG QUAN CÁC CƠNG
TRÌNH LIÊN QUAN
Chương này sẽ trình bày các khái niệm căn bản và các lý thuyết liên quan đến
vấn đề tìm kiếm tương tự và phát hiện mơ típ trên dữ liệu chuỗi thời gian. Các khái
niệm này bao gồm một số định nghĩa, phương pháp và giải thuật được sử dụng để
xử lý chuỗi thời gian. Cuối chương là tổng hợp sơ bộ vài cơng trình liên quan đến
đề tài cùng những ưu điểm và nhược điểm của chúng.
2.1 Các độ đo tương tự
Vấn đề quan trọng nhất của bài tốn tìm kiếm tương tự trên dữ liệu chuỗi thời
gian là cách tính độ tương tự (thường là khoảng cách) của hai chuỗi con bất kỳ
trong tập các chuỗi con. Trong trường hợp hai chuỗi này giống nhau thì khoảng
cách này sẽ là 0 và ngược lại càng khác nhau thì khoảng cách sẽ càng lớn.
2.1.1 Độ đo Euclid
Để xác định độ tương tự của hai chuỗi thời gian, nhiều độ đo tương tự đã được
sử dụng. Trong đó, độ đo khoảng cách Euclid thường được sử dụng nhất.
Cho hai chuỗi thời gian Q = q1,…,qn và C = c1,…,cn độ đo khoảng cách Euclid
giữa hai chuỗi thời gian này được cho bởi cơng thức:
( , )=


(

− )

Hình 2-1: Khoảng cách Euclid giữa hai chuỗi thời gian Q và C (Từ nguồn [5]).
Lê Minh Nhựt – 10070491

Trang 6


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Hình 2-1 thể hiện một cách trực quan phương pháp tính độ tương tự của hai
chuỗi thời gian sử dụng độ đo khoảng cách Euclid.
Độ đo khoảng cách Euclid cho thấy sự đơn giản, dễ hiểu, dễ tính tốn, dễ mở
rộng cho nhiều bài tốn khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân
lớp và đủ tốt để tính độ tương tự của hai chuỗi thời gian. Độ đo khoảng cách Euclid
cũng có ưu điểm là nó phù hợp với các phương pháp thu giảm số chiều DFT, DWT,
PAA, APCA.
Độ đo khoảng cách Euclid có nhược điểm là nhạy cảm với nhiễu và khơng thích
hợp khi dữ liệu có đường cơ bản (base line) khác nhau.
2.1.2 Độ đo xoắn thời gian động
Khi hai chuỗi thời gian có hình dạng khơng hồn tồn giống nhau nhưng hình
dạng biến đổi của chúng rất giống nhau thì việc áp dụng khoảng cách Euclid sẽ
khơng cịn phù hợp nữa. Trong trường hợp này, độ đo xoắn thời gian động sẽ được
sử dụng.
Độ đo xoắn thời gian động (Dynamic Time Warping), hay còn gọi là DTW,
được đề xuất bởi Bernt và Clifford vào năm 1994 [8]. Trong độ đo xoắn thời gian
động, thay vì tính khoảng cách từng cặp điểm 1-1 (điểm thứ i của đường thứ nhất
so với điểm thứ i của đường thứ hai) thì một điểm có thể ánh xạ với nhiều điểm và

ánh xạ này khơng thẳng hàng. Chi tiết về DTW được trình bày trong [8].

Hình 2-2: Độ đo xoắn thời gian động (nguồn [17]).
Lê Minh Nhựt – 10070491

Trang 7


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Hình 2-2 thể hiện một cách trực quan phương pháp tính độ tương tự của hai
chuỗi thời gian sử dụng độ đo xoắn thời gian động.
Phương pháp DTW có ưu điểm là cho kết quả chính xác hơn so với độ đo
Euclid. DTW cho phép nhận dạng những mẫu có hình dạng biến đổi giống nhau
nhưng khơng hồn tồn giống nhau hoặc chiều dài hình dạng về mặt thời gian khác
nhau.
Tuy nhiên, phương pháp này cũng có nhược điểm là thời gian chạy lâu vì cách
tính phức tạp hơn độ đo Euclid. Để cải thiện vấn đề này, gần đây đã có các cơng
trình nghiên cứu nhằm cải thiện tốc độ tìm kiếm tương tự dùng độ đo DTW.
2.1.3 Độ đo chuỗi con chung dài nhất
Chuỗi con chung dài nhất (Longest Common Subsequence), còn gọi là LCS, là
một phương pháp khác để tính độ tương tự. Phương pháp này được giới thiệu bởi
Vlachos và các cộng sự vào năm 2004 [9].
Tư tưởng chính của phương pháp LCS là tìm những chuỗi con chung của hai
chuỗi dài hơn. Hai chuỗi có chuỗi con chung càng dài thì càng giống nhau. Chi tiết
của phương pháp này được trình bày trong [9].
Ví dụ, cho 2 chuỗi X, Y với X = 3, 2, 5, 7, 4, 8, 10, 7 và Y = 2, 5, 4, 7, 3, 10, 8, 6.
Chuỗi con chung là LCS = 2, 5, 7, 10 và độ tương tự của X, Y: Sim(X, Y) = |LCS| =
4.
Ưu điểm nổi bật của phương pháp LCS là nó cho phép bỏ qua những điểm bất
thường khi so sánh.

2.2 Các phương pháp thu giảm số chiều
Dữ liệu chuỗi thời gian thường là dữ liệu rất lớn. Việc tìm kiếm trên dữ liệu này
rất phức tạp, tốn chi phí và thường khơng hiệu quả. Do đó, để khắc phục vấn đề
này, chúng ta phải tiến hành thu giảm số chiều của dữ liệu. Chúng ta sẽ tìm hiểu hai
loại phương pháp thu giảm số chiều là phương pháp biến đổi sang miền tần số và
phương pháp xấp xỉ từng đoạn.
2.2.1 Các phương pháp biến đổi sang miền tần số
2.2.1.1Phương pháp biến đổi Fourier rời rạc
Lê Minh Nhựt – 10070491

Trang 8


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Phương pháp biến đổi Fourier rời rạc (Discrete Fourier Transform), còn gọi là
DFT, là một phương pháp được sử dụng rất phổ biến, đặc biệt là trong lĩnh vực xử
lý ảnh và xử lý tín hiệu số. Phương pháp này do Agrawal và các cộng sự đề xuất
vào năm 1993 [10].
Trong phương pháp biến đổi Fourier thì đường dữ liệu ban đầu được biểu diễn
bởi các đường cơ bản là sin và cosin.
( ) =

(AkCos(2πwkt)+BkSin(2πwkt ))

Trong đó C(t) là chuỗi dữ liệu kết quả, Ak, Bk là các hệ số biến đổi, được xem là
đặc trưng của chuỗi dữ liệu ban đầu. Phương pháp này được minh họa trong hình 23 (a).
Ưu điểm của phương pháp DFT là thích hợp với các loại đường biểu diễn dữ
liệu khác nhau. Nó có khả năng nén dữ liệu và chịu nhiễu tốt. Phương pháp này cho
phép so sánh gián tiếp 2 chuỗi X, Y thông qua khoảng cách của 2 chuỗi Xf, Yf đã
được biến đổi. DFT cũng hỗ trợ nhiều phương pháp lập chỉ mục như F-index, STindex …

Nhược điểm lớn nhất của phương pháp này là khó giải quyết khi các chuỗi thời
gian có chiều dài khác nhau.
2.2.1.2Phương pháp biến đổi Wavelet rời rạc
Phương pháp biến đổi Wavelet rời rạc (Discrete Wavelet Transform), còn gọi là
DWT, là một phương pháp thu giảm số chiều do K. Chan và W. Fu đề xuất năm
1999 [11]. Thay vì sử dụng các đường lượng giác sin hay cosin như phương pháp
DFT, DWT dùng đường Haar hoặc một số đường cơ bản khác như Daubechies,
Coiflet, Symmlet…Phương pháp này được minh họa trong hình 2-3 (b).
Đường Haar ψif được biểu diễn theo công thức sau:
1
-1
(
)
ψf t =
0
i

với 0≤t<0.5
với 0.5≤t<1
các trường hợp khác

Phương pháp biến đổi Wavelet rời rạc có ưu điểm là nó rất hiệu quả bởi vì nó
mã hóa đơn giản và nhanh. Độ phức tạp của giải thuật là tuyến tính. Một ưu điểm
Lê Minh Nhựt – 10070491

Trang 9


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
khác là nó có khả năng khử nhiễu rất cao, thích hợp với những dữ liệu tĩnh ít thay

đổi do đường Haar cũng khơng thay đổi liên tục.
Phương pháp DWT có nhược điểm là chỉ thực hiện hiệu quả với chuỗi dữ liệu
ban đầu có chiều dài là lũy thừa 2. Đồng thời, chiều dài của chuỗi con truy vấn cũng
nên là lũy thừa 2 thì giải thuật mới thực hiện hiệu quả.

Hình 2-3: Các phương pháp biến đổi sang miền tần số (nguồn [17]).
2.2.2 Các phương pháp xấp xỉ từng đoạn
2.2.2.1Phương pháp xấp xỉ tuyến tính từng đoạn
Phương pháp xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation),
còn gọi là PLA, do E. Keogh và các cộng sự đề nghị [12] [13].Trong phương pháp
này, dữ liệu ban đầu được biểu diễn lại bằng chuỗi các đoạn thẳng tuyến tính. Mỗi
đoạn thẳng tuyến tính nối cặp điểm ở hai đầu đoạn thẳng xấp xỉ tốt nhất (best-fit)
những điểm có trong phân đoạn chuỗi thời gian đó. Các đoạn thẳng này có thể rời
nhau hoặc liên tục. Hình 2-4 (a) minh họa việc thu giảm số chiều sử dụng phương
pháp PLA.
Lê Minh Nhựt – 10070491

Trang 10


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Ưu điểm của phương pháp PLA là biểu diễn rất trực quan và phù hợp để nén tất
cả các loại dữ liệu chuỗi thời gian. Một ưu điểm khác của phương pháp này là nó
cho phép thực hiện tìm kiếm các chuỗi đoạn thẳng nhanh chóng trong thời gian
tuyến tính.
2.2.2.2Phương pháp xấp xỉ gộp từng đoạn
Phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation), còn
gọi là PAA, do E. Keogh và cộng sự đề xuất năm 2001 [3].
Phương pháp này rất đơn giản, k điểm liền kề nhau sẽ được ánh xạ thành cùng
một giá trị bằng cách tính trung bình cộng của k điểm đó. Q trình cứ tiếp tục như

thế từ trái sang phải. Kết quả ta thu được một đường thẳng có dạng bậc thang. Hình
2-4 (b) minh họa việc thu giảm số chiều sử dụng phương pháp PAA.
Ưu điểm lớn nhất của phương pháp này là thời gian tính tốn nhanh. PAA hỗ
trợ nhiều độ đo tương tự khác nhau như Euclid, DTW…
Nhược điểm của PAA là khó xây dựng lại chuỗi ban đầu và thường sinh lỗi lớn.
Phương pháp này không quan tâm đến những điểm đặc biệt, chẳng hạn như điểm
cực trị, trong từng đoạn xấp xỉ.
2.2.2.3Phương pháp xấp xỉ hằng số từng đoạn thích nghi
Phương pháp xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise
Constant Approximation), cịn gọi là APCA, do E. Keogh và các cộng sự nêu ra vào
năm 2001 [14]. Phương pháp APCA giống như phương pháp PAA là xấp xỉ dữ liệu
ban đầu thành những đoạn thẳng nằm ngang. Tuy nhiên, phương pháp này khác với
PAA là các đoạn ở PAA có kích thước bằng nhau, cịn ở APCA thì kích thước của
các đoạn là khác nhau tùy theo dữ liệu. Những vùng nào trên chuỗi thời gian có
biến động nhấp nhơ nhiều thì được phân thành những đoạn ngắn, cịn những vùng
nào ít biến động thì được phân thành những đoạn dài hơn. Hình 2-4 (c) minh họa
việc thu giảm số chiều sử dụng phương pháp APCA.
Ưu điểm của phương pháp APCA là tỷ lệ nén cao hơn so với phương pháp
PAA. Tỷ lệ lỗi khi khôi phục lại dữ liệu cũng nhỏ hơn so với phương pháp PAA.

Lê Minh Nhựt – 10070491

Trang 11


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
Nhược điểm của phương pháp APCA là thời gian tính tốn lâu hơn. Độ phức
tạp của phương pháp này là O(nlog(n)).

Hình 2-4: Các phương pháp xấp xỉ từng đoạn (nguồn [17]).

2.3 Tổng quan về các công trình liên quan
Vấn đề phát hiện mơ típ trên dữ liệu chuỗi thời gian là một bài toán thú vị và thu
hút sự quan tâm của nhiều người. Nhiều nhà khoa học trên thế giới đã có nhiều cơng
trình nghiên cứu để giải quyết bài toán này. Họ đưa ra nhiều giải thuật khác nhau,
cùng với nhiều cách tiếp cận khác nhau để đi tìm lời giải. Tuy nhiên, đa số các cơng
trình nghiên cứu chỉ tập trung vào việc tìm sự xuất hiện của một mơ típ đã biết
trước trong một chuỗi thời gian hoặc phát hiện sự xuất hiện của một mơ típ có chiều
dài cố định trong chuỗi thời gian. Chúng ta sẽ điểm sơ qua một vài giải thuật phát
hiện mơ típ đã có: giải thuật EMMA [5], giải thuật chiếu ngẫu nhiên [4], giải thuật
Mueen-Keogh [6].

Lê Minh Nhựt – 10070491

Trang 12


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
2.3.1 Giải thuật EMMA
Giải thuật EMMA được Jessica Lin và các cộng sự đưa ra vào năm 2002 [5]
nhằm cải tiến giải thuật Brute Force trong việc tìm kiếm mơ típ. Để giải thuật hoạt
động ta cần phải cung cấp một số thông số đầu vào sau: chuỗi thời gian T, chiều dài
n của cửa sổ trượt cũng là chiều dài của mơ típ, một hằng số dương R thể hiện phạm
vi lân cận của một chuỗi con, chiều dài chuỗi ký tự w khi ánh xạ chuỗi con sang
dạng ký tự sử dụng giải thuật SAX [1], độ lớn a của bảng chữ cái sử dụng cho SAX.
Đầu tiên, chuỗi thời gian ban đầu sẽ được chia thành nhiều chuỗi con sử dụng
cửa sổ trượt. Sau đó các chuỗi con được giảm số chiều sử dụng phương pháp PAA
và chuyển về dạng chuỗi ký tự bằng phương pháp SAX.
Sau khi đã có tập các chuỗi con chuẩn hóa biểu diễn dưới dạng các chuỗi ký tự,
một hàm băm (công thức 11 trong [5]) được sử dụng để ánh xạ các chuỗi con này
vào từng nhóm riêng. Nhóm chứa nhiều chuỗi con nhất sẽ là ứng cử viên số một

cho việc tìm mơ típ.
Giải thuật sẽ tìm mơ típ trong nhóm có nhiều chuỗi con nhất bằng cách tính
tốn khoảng cách giữa các chuỗi con sử dụng khoảng cách Euclid. Nếu tìm thấy mơ
típ thì giải thuật kết thúc. Ngược lại, nếu khơng tìm thấy mơ típ trong nhóm này thì
nhóm có số lượng các chuỗi con nhiều thứ hai sẽ được xem xét. Quá trình cứ lặp lại
như thế cho đến khi mơ típ được tìm thấy.
Ưu điểm của giải thuật EMMA là sử dụng khoảng cách Euclid đơn giản để tính
độ tương tự của các chuỗi con, sử dụng hàm băm để chia nhóm nhằm giảm bớt
được số lần tính khoảng cách giữa các chuỗi con. EMMA tốt hơn so với giải thuật
Brute Force.
Hạn chế của giải thuật EMMA là cần xác định trước chiều dài của mơ típ. Việc
dự đốn trước chiều dài của mơ típ ln là một cơng việc khó khăn. Để thực thi giải
thuật ta cũng cần cung cấp hằng số R. Tốc độ của giải thuật phụ thuộc vào hằng số
này. Do đó, nếu chúng ta chọn giá trị khơng tốt sẽ làm chậm tốc độ tìm ra lời giải.
Một hạn chế khác của giải thuật là nó chỉ có thể phát hiện một mơ típ mà khơng thể
phát hiện tất cả các mơ típ trong chuỗi thời gian đang xét.
Lê Minh Nhựt – 10070491

Trang 13


Phát hiện mơ típ với chiều dài khác nhau trên dữ liệu chuỗi thời gian
2.3.2 Giải thuật chiếu ngẫu nhiên
Bill Chiu, Eamonn Keogh và các cộng sự sử dụng giải thuật chiếu ngẫu nhiên
(Random Projection) để tìm mơ típ trên dữ liệu chuỗi thời gian vào năm 2003 [4].
Giải thuật dựa vào cơng trình [5] để phát triển một phương pháp mới giúp tìm mơ
típ trong trường hợp có sự xuất hiện của nhiễu.
Giải thuật cũng sử dụng phương pháp PAA để thu giảm số chiều của chuỗi thời
gian, sử dụng phương pháp SAX để rời rạc hóa chuỗi con thành chuỗi ký tự. Các
chuỗi con sau khi được ký hiệu hóa sẽ được đặt vào một ma trận . Mỗi chuỗi con

sẽ là một dòng của ma trận này.
Sau khi có được ma trận , q trình chiếu ngẫu nhiên sẽ được thực hiện nhằm
xây dựng một ma trận đụng độ gọi là CM. Ma trận đụng độ sẽ có các dịng và cột là
các chuỗi con trong . Ban đầu giá trị các ô trong ma trận CM được gán giá trị 0.
Giải thuật sẽ thực hiện k lần lặp. Tại mỗi lần lặp, chọn một số cột ngẫu nhiên
trong ma trận

làm mặt nạ. Sau đó, giá trị của các chuỗi con ứng với mặt nạ (các

ký tự ở các cột trong mặt nạ) này sẽ được tính tốn bởi một hàm băm. Các chuỗi
con có giá trị giống nhau sẽ được băm vào cùng một túi. Nếu hai chuỗi con i và j
được băm vào cùng một túi thì giá trị của ơ ứng với hai chuỗi con đó ơ(i,j) trong ma
trận CM sẽ được tăng giá trị lên 1. Quá trình cứ như thế cho đến khi kết thúc k lần
lặp, ta sẽ thu được ma trận đụng độ kết quả cuối cùng. Chi tiết về giải thuật chiếu
ngẫu nhiên sẽ được trình bày trong chương 3.
Hai chuỗi con ứng với ơ có giá trị lớn nhất trong CM sẽ là ứng cử số 1 cho mơ
típ. Để xác định hai chuỗi con đó có là mơ típ hay khơng giải thuật sẽ tính khoảng
cách Euclid của hai chuỗi con ban đầu để đưa ra kết luận. Các ơ có giá trị lớn tiếp
theo có thể được xem xét để tìm các mơ típ kế tiếp.
Ưu điểm của giải thuật chiếu ngẫu nhiên là có khả năng phát hiện mơ típ trong
trường hợp có nhiễu. Theo các tác giả thì giải thuật có khả năng phát hiện mơ típ
với tốc độ rất nhanh và tương đối chính xác.
Nhược điểm chính của giải thuật này là cũng phải cung cấp chiều dài của mơ
típ. Giải thuật khơng thể phát hiện những mơ típ có chiều dài khác. Ngoài ra giải
Lê Minh Nhựt – 10070491

Trang 14