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

VÕ THÀNH VINH

PHÂN LỚP BÁN GIÁM SÁT
DỮ LIỆU CHUỖI THỜI GIAN
Chuyên ngành: Khoa Học Máy Tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 06 năm 2014


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: PGS. TS. Dương Tuấn Anh ............................
(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: TS. Võ Đình Bảy ...................................................
(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: TS. Phạm Văn Chung ............................................
(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 14 tháng 07 năm 2014.
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. TS. Nguyễn Văn Minh Mẫn (Chủ tịch)....
2. TS. Huỳnh Tường Nguyên (Thư ký) ........
3. TS. Võ Đình Bảy (Phản biện 1) ...............

4. TS. Phạm Văn Chung (Phản biện 2) ........
5. PGS. TS. Dương Tuấn Anh (Ủy viên)......
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

TS. Nguyễn Văn Minh Mẫn

TRƯỞNG KHOA
KH & KT MÁY TÍNH


ĐẠI HỌC QUỐC GIA TP.HCM
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
Độ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: Võ Thành Vinh ........................................... MSHV: 12073138
Ngày, tháng, năm sinh: 09/06/1989 ............................................ Nơi sinh: Tp. Hồ Chí Minh
Chuyên ngành: Khoa Học Máy Tính .......................................... Mã số: 60.48.01
I.

TÊN ĐỀ TÀI: PHÂN LỚP BÁN GIÁM SÁT DỮ LIỆU CHUỖI THỜI GIAN ............
..........................................................................................................................................
..........................................................................................................................................
NHIỆM VỤ LUẬN VĂN: ..............................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................


II. NGÀY GIAO NHIỆM VỤ: 10/02/2014 .........................................................................
III. NGÀY HOÀN THÀNH NHIỆM VỤ: 20/06/2014 ........................................................
IV. CÁN BỘ HƯỚNG DẪN: PGS. TS. Dương Tuấn Anh ..................................................

CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

PGS. TS. Dương Tuấn Anh

Tp. HCM, ngày ….. tháng ….. năm 2014
TRƯỞNG KHOA KH & KT MÁY TÍNH
(Họ tên và chữ ký)


i

LỜI CẢM ƠN
Tôi xin chân thành cảm ơ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 quá trình từ đại học tới cao học và tạo điều kiện tốt nhất
để tơi hồn thành luận văn này.
Tơi xin cảm ơn q Thầy Cơ, những người đã tận tình hướng dẫn và truyền
đạt cho tơi những kiến thức q báu trong suốt q trình học tập.
Tơi xin cảm ơn gia đình đã độ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, 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à con mới có
được thành quả như ngày hơm nay.
Qua đây, tơi cũng xin chân thành cảm ơn các anh chị và các bạn đã giúp đỡ,
góp ý cho tơi trong q trình thực hiện luận văn.



ii

TÓM TẮT LUẬN VĂN
Trong lĩnh vực khai phá dữ liệu chuỗi thời gian, phân lớp là một vấn đề rất
quan trọng, đã thu hút nhiều nghiên cứu trong thập kỷ vừa qua. Tuy nhiên, hầu hết
các phương pháp phân lớp đều giả định rằng tập huấn luyện chứa một số lượng lớn
các mẫu đã được gán nhãn. Giả định này không phù hợp với thực tế, nơi mà số lượng
các mẫu đã được gán nhãn là rất ít. Trong hồn cảnh này, phân lớp bán giám sát là
một mơ hình thích hợp để giải quyết vấn đề trên.
Trong đề tài này, chúng tôi đề nghị hai cải tiến cho phân lớp bán giám sát dữ
liệu chuỗi thời gian: một kỹ thuật cải tiến cho tiêu chuẩn dừng dựa trên nguyên lý
Chiều dài Mô tả Nhỏ nhất (Minimum Description Length) và đề nghị thêm một bước
tinh chế (Refinement step) vào mô hình phân lớp bán giám sát trước đó, giúp cho bộ
phân lớp được chính xác hơn. Cải tiến thứ nhất áp dụng ánh xạ khơng tuyến tính (nonlinear alignment) giữa các cặp điểm trên hai chuỗi thời gian khi tính tốn Chiều dài
Mơ tả Thu giảm (Reduced Description Length). Cải tiến thứ hai là một bước hậu xử
lý, quá trình này cố gắng phát hiện những mẫu có nhãn sai ở khoảng biên giữa tập
các mẫu âm và tập các mẫu dương, sau đó phân loại lại các mẫu này cho đúng.
Các kết quả thực nghiệm cho thấy những cải tiến được chúng tôi đề xuất ở
trên giúp cho việc xây dựng bộ phân lớp bán giám sát dữ liệu chuỗi thời gian được
chính xác hơn những phương pháp trước đó.


iii

ABSTRACT
In time series data mining, classification is a crucial problem which has
attracted lots of researches in the last decade. However, most of the current methods
assume that the training set contains a great number of positive/labeled data. Such an
assumption is unrealistic in the real world where we have a small set of labeled data,

in addition to abundant unlabeled data. In such circumstances, semi-supervised
classification is a suitable paradigm.
In this work, we propose two novel improvements for semi-supervised
classification of time series: an improvement technique for Minimum Description
Length-based stopping criterion and a refinement step to make the classifier more
accurate. Our first improvement applies the non-linear alignment between two time
series when we compute Reduced Description Length of one time series exploiting
the information from the other. The second improvement is a post-processing step
that aims to identify the class boundary between positive and negative instances
accurately.
Experimental results show that our two improvements can construct more
accurate semi-supervised time series classifiers.


iv

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 20 tháng 06 năm 2014

Võ Thành Vinh


v

MỤC LỤC

LỜI CẢM ƠN .............................................................................................................. i
TÓM TẮT LUẬN VĂN .............................................................................................ii
ABSTRACT .............................................................................................................. iii
LỜI CAM ĐOAN ...................................................................................................... iv
MỤC LỤC ................................................................................................................... v
DANH MỤC HÌNH ................................................................................................... ix
DANH MỤC BẢNG .................................................................................................xii
CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI ............................................ 1
1.1. GIỚI THIỆU ĐỀ TÀI .......................................................................................1
1.1.1. Dữ liệu chuỗi thời gian ...............................................................................1
1.1.2. Bài toán phân lớp dữ liệu chuỗi thời gian ..................................................3
1.1.3. Bài toán phân lớp bán giám sát dữ liệu chuỗi thời gian .............................4
1.2. MỤC TIÊU VÀ GIỚI HẠN ĐỀ TÀI ...............................................................4
1.3. CÁC KẾT QUẢ ĐÃ ĐẠT ĐƯỢC ...................................................................5
1.4. CẤU TRÚC CỦA LUẬN VĂN .......................................................................6
CHƯƠNG 2. NHỮNG CƠNG TRÌNH LIÊN QUAN ............................................... 8
2.1. NHỮNG CƠNG TRÌNH VỀ ĐỘ ĐO TƯƠNG TỰ ........................................8
2.1.1. Độ đo Minkowski .......................................................................................9
2.1.2. Phương pháp xoắn thời gian động ............................................................10
2.1.3. Phương pháp chuỗi con chung dài nhất ...................................................12
2.2. NHỮNG CƠNG TRÌNH LIÊN QUAN ĐẾN THU GIẢM SỐ CHIỀU DỮ
LIỆU CHUỖI THỜI GIAN ...................................................................................13


vi
2.3. NHỮNG CƠNG TRÌNH LIÊN QUAN ĐẾN BÀI TỐN GOM CỤM........15
2.3.1. Giải thuật gom cụm K-means ...................................................................15
2.3.2. Giải thuật gom cụm X-means ...................................................................16
2.3.3. Gom cụm phân cấp ...................................................................................17
2.4. NHỮNG CÔNG TRÌNH LIÊN QUAN ĐẾN BÀI TỐN PHÂN LỚP DỮ

LIỆU CHUỖI THỜI GIAN ...................................................................................18
2.4.1. Phương pháp phân lớp có giám sát dựa trên tìm kiếm k-láng giềng-gần
nhất .....................................................................................................................18
2.4.2. Phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và
Keogh .................................................................................................................18
2.4.3. Tiêu chuẩn dừng trong phương pháp phân lớp bán giám sát dữ liệu chuỗi
thời gian của Wei và Keogh ...............................................................................19
2.4.4. Tiêu chuẩn dừng của Ratanamahatana và Wanichsan cho mơ hình của
Wei và Keogh .....................................................................................................19
2.4.5. Phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian LCLC và EnLCLC ..................................................................................................................20
2.4.6. Phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian dựa vào gom
cụm phân cấp của Marussy và Buza ..................................................................20
2.4.7. Tiêu chuẩn dừng dựa trên nguyên lý Chiều dài Mô tả Nhỏ nhất của
Begum cho mơ hình của Wei và Keogh .............................................................21
CHƯƠNG 3. CƠ SỞ LÝ THUYẾT ......................................................................... 22
3.1. ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG .............................................................22
3.2. RÀNG BUỘC ĐƯỜNG XOẮN TRONG ĐỘ ĐO XOẮN THỜI GIAN
ĐỘNG ....................................................................................................................26
3.2.1. Ràng buộc Sakoe-Chiba ...........................................................................27
3.2.2. Ràng buộc hình bình hành Itakura ...........................................................27


vii
3.3. THU GIẢM SỐ CHIỀU DỮ LIỆU BẰNG PHƯƠNG PHÁP XẤP XỈ GỘP
TỪNG ĐOẠN........................................................................................................28
3.4. GIẢI THUẬT GOM CỤM X-MEANS ..........................................................29
3.4.1. Chỉ số BIC trong giải thuật X-Means .......................................................31
3.4.2. Các phương pháp tăng tốc giải thuật X-means .........................................32
3.5. PHÂN LỚP CÓ GIÁM SÁT DỰA TRÊN TÌM KIẾM K-LÁNG GIỀNGGẦN NHẤT ...........................................................................................................35
3.6. PHÂN LỚP BÁN GIÁM SÁT DỮ LIỆU CHUỖI THỜI GIAN ...................37

3.6.1. Sơ lược về học bán giám sát .....................................................................37
3.6.2. Phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và
Keogh .................................................................................................................39
3.6.3. Phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian dựa vào gom
cụm phân cấp của Marussy và Buza ..................................................................42
3.7. TIÊU CHUẨN DỪNG TRONG PHÂN LỚP BÁN GIÁM SÁT DỮ LIỆU
CHUỖI THỜI GIAN THEO MƠ HÌNH CỦA WEI VÀ KEOGH .......................44
3.7.1. Tiêu chuẩn dừng của Wei và Keogh ........................................................44
3.7.2. Tiêu chuẩn dừng của Ratanamahatana và Wanichsan .............................45
3.7.3. Tiêu chuẩn dừng dựa trên nguyên lý Chiều dài Mô tả Nhỏ nhất .............47
CHƯƠNG 4. PHƯƠNG PHÁP ĐỀ NGHỊ ............................................................... 54
4.1. MƠ HÌNH PHÂN LỚP BÁN GIÁM SÁT .....................................................54
4.2. TIÊU CHUẨN DỪNG DỰA TRÊN NGUYÊN LÝ CHIỀU DÀI MƠ TẢ
NHỎ NHẤT ...........................................................................................................55
4.3. Q TRÌNH TINH CHẾ ...............................................................................60
CHƯƠNG 5. THỰC NGHIỆM ................................................................................ 63
5.1. MÔI TRƯỜNG THỰC HIỆN ........................................................................63


viii
5.2. CÁC TẬP DỮ LIỆU ......................................................................................63
5.3. PHƯƠNG PHÁP THỰC HIỆN......................................................................64
5.4. THỰC NGHIỆM SO SÁNH TIÊU CHUẨN DỪNG ....................................65
5.4.1. Bộ dữ liệu MIT-BIH Supraventricular Arrhythmia Database .................65
5.4.2. Bộ dữ liệu St. Petersburg Arrhythmia Database ......................................66
5.4.3. Tập dữ liệu Gun Point ..............................................................................66
5.4.4. Tập dữ liệu FISH ......................................................................................67
5.5. THỰC NGHIỆM QUÁ TRÌNH TINH CHẾ ..................................................68
5.5.1. Tiêu chuẩn dừng MDL cải tiến và quá trình tinh chế ..............................68
5.5.2. Tiêu chuẩn dừng SCC và quá trình tinh chế ............................................69

5.6. MỘT SỐ KẾT QUẢ THỰC NGHIỆM KHÁC .............................................70
5.6.1. Thực nghiệm so sánh phương pháp đề nghị với phương pháp của
Marussy và Buza ................................................................................................71
5.6.2. Phân lớp bán giám sát với X-means-Classifier.........................................72
5.6.3. Thời gian thực thi .....................................................................................73
CHƯƠNG 6. TỔNG KẾT......................................................................................... 76
6.1. TỔNG KẾT.....................................................................................................76
6.2. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI.............................................................78
6.3. HƯỚNG PHÁT TRIỂN .................................................................................79
DANH MỤC CƠNG TRÌNH KHOA HỌC CÔNG BỐ........................................... 80
TÀI LIỆU THAM KHẢO ......................................................................................... 81
PHỤ LỤC A. BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT ......................... A–1


ix

DANH MỤC HÌNH
Hình 1.1. Dữ liệu chuỗi thời gian................................................................................3
Hình 2.1. So sánh cách ánh xạ cặp điểm trong độ đo Euclid và độ đo DTW (nguồn
[11]) ...........................................................................................................................11
Hình 2.2. Hình ảnh minh họa việc từ bỏ sớm trong tính khoảng cách giữa hai chuỗi
thời gian (nguồn [21]) ...............................................................................................12
Hình 2.3. Phương pháp chuỗi con chung dài nhất (nguồn [1]) .................................13
Hình 2.4. Giải thuật gom cụm K-means (nguồn [36]) ..............................................16
Hình 2.5. Giải thuật gom cụm phân cấp đơn giản (nguồn [42]) ...............................17
Hình 3.1. Cách tính khoảng cách xoắn thời gian động. A) Cho hai chuỗi thời gian Q
và C. B) Ma trận tính DTW. C) Kết quả ánh xạ điểm trong DTW (nguồn [11]) .....23
Hình 3.2. Đồ thị biểu diễn hai chuỗi thời gian ..........................................................25
Hình 3.3. Ma trận tính DTW cho hai chuỗi thời gian ...............................................25
Hình 3.4. Ràng buộc Sakoe-Chiba (nguồn [6]) ........................................................27

Hình 3.5. Ràng buộc Itakura (nguồn [6]) ..................................................................28
Hình 3.6. Giải thuật thu giảm số chiều bằng phương pháp PAA..............................29
Hình 3.7. Giải thuật gom cụm X-means (nguồn [24]) ..............................................29
Hình 3.8. Ví dụ quá trình tách cụm trong giải thuật X-means (nguồn [24]) .............30
Hình 3.9. Giải thuật cập nhật trung tâm cụm trong X-means (nguồn [25]) ..............34
Hình 3.10. Phân lớp dựa trên k-láng giềng-gần nhất ................................................36
Hình 3.11. Lưu đồ thể hiện các bước tự huấn luyện trong phân lớp bán giám sát dữ
liệu chuỗi thời gian ....................................................................................................40


x
Hình 3.12. Giải thuật phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và
Keogh (nguồn [5]) .....................................................................................................41
Hình 3.13. A) Bộ dữ liệu với hai lớp dương và âm. B) Hiệu ứng dây chuyền của học
bán giám sát. C) Nếu phân lớp bằng cách tìm nhiều điểm gần nhất cùng lúc thì quá
trình phân lớp sẽ bị sai (nguồn [5]). ..........................................................................41
Hình 3.14. Thống kê khoảng cách nhỏ nhất trong tập đã gán nhãn sau mỗi bước
hiệu chỉnh tập này (nguồn [5]) ..................................................................................45
Hình 3.15. Những vấn đề trong tiêu chuẩn dừng của Wei và Keogh. (a) Khoảng
cách nhỏ nhất chỉ có một lần giảm; (b) Có quá nhiều điểm có thể chọn làm điểm
dừng; (c) Khơng có điểm dừng trong mơ hình; (d) Tiêu chuẩn dừng xảy ra q trễ
tại y thay vì tại x (nguồn [8]). ....................................................................................46
Hình 3.16. Các giá trị SCC trong mơ hình của Ratanamahatana và Wanichsan
(nguồn [8]).................................................................................................................47
Hình 3.17. Chuỗi thời gian A được biểu diễn bằng tổng của giả thuyết H và Véc-tơ
hiệu A' (nguồn [12]) ..................................................................................................49
Hình 3.18. A) Chuỗi thời gian gốc. B) chuỗi thời gian đã rời rạc hóa (nguồn [12]) 50
Hình 3.19. A) Một chuỗi thời gian được chọn làm chuỗi giả thuyết (Hypothesis). B)
Sáu chuỗi thời gian (có chiều dài 100) và các nhãn tương ứng của chúng (các nhãn
này đều là nhãn đúng của mỗi chuỗi) (nguồn [12]) ..................................................50

Hình 3.20. Q trình thu giảm chiều dài mơ tả qua từng bước (nguồn [12]) ...........51
Hình 4.1. Mơ hình phân lớp bán giám sát dữ liệu chuỗi thời gian ...........................54
Hình 4.2. Giải thuật phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và
Keogh ........................................................................................................................55
Hình 4.3. Tìm số điểm khơng trùng khớp giữa hai chuỗi thời gian A và H. A) Ma
trận M dùng để tính khoảng cách DTW. B) Tìm điểm khơng trùng khớp (hai cặp
điểm được đánh dấu) .................................................................................................57


xi
Hình 4.4. Giải thuật đếm số điểm khơng trùng khớp giữa hai chuỗi thời gian sử
dụng ràng buộc dải Sakoe-Chiba ..............................................................................58
Hình 4.5. Giải thuật tìm thơng số dải Sakoe-Chiba ..................................................60
Hình 4.6. Giải thuật tinh chế tập huấn luyện (Refinement step) ...............................61
Hình 4.7. Ví dụ về bước tinh chế. A) Tập P và N sau khi áp dụng phương pháp của
Wei và Keogh với tiêu chuẩn dừng dựa trên MDL cải tiến. B) Xác định các mẫu
nghi ngờ (hai cặp mẫu được đánh dấu). C) Phân loại lại các mẫu nghi ngờ. D) Tiếp
tục xác định các mẫu nghi ngờ. E) Tập huấn luyện kết quả sau khi thực hiện bước
tinh chế ......................................................................................................................62
Hình 5.1. A) Tiêu chuẩn dừng MDL cải tiến (Phương pháp đề nghị) tại thời điểm
262 (gần như hoàn hảo). B) Tiêu chuẩn dừng dựa trên MDL (Phương pháp trước
đó) tại thời điểm 10 (q sớm) ..................................................................................65
Hình 5.2. A) Tiêu chuẩn dừng MDL cải tiến (Phương pháp đề nghị) tại thời điểm
121 (gần như hoàn hảo). B) Tiêu chuẩn dừng dựa trên MDL (Phương pháp trước
đó) tại thời điểm 28 (quá sớm) ..................................................................................66
Hình 5.3. A) Tiêu chuẩn dừng MDL cải tiến (Phương pháp đề nghị) tại thời điểm 15
(gần như hoàn hảo). B) Tiêu chuẩn dừng dựa trên MDL (Phương pháp trước đó) tại
thời điểm 3 (quá sớm). C) Tiêu chuẩn dừng SCC tại thời điểm 20 (quá trễ) ...........67
Hình 5.4. A) Tiêu chuẩn dừng MDL cải tiến (Phương pháp đề nghị) tại thời điểm 19
(gần như hoàn hảo). B) Tiêu chuẩn dừng dựa trên MDL (Phương pháp trước đó) tại

thời điểm 3 (quá sớm). C) Tiêu chuẩn dừng SCC tại thời điểm 18 ..........................67
Hình 6.1. Tổng thuật các cơng trình về phân lớp bán giám sát dữ liệu chuỗi thời
gian cùng với phương pháp đề nghị trong đề tài này ................................................77


xii

DANH MỤC BẢNG
Bảng 5.1. Tập dữ liệu được dùng để đánh giá các thực nghiệm ...............................64
Bảng 5.2. Thực nghiệm so sánh quá trình tinh chế dùng tiêu chuẩn dừng MDL cải
tiến .............................................................................................................................68
Bảng 5.3. Thực nghiệm so sánh quá trình tinh chế dùng tiêu chuẩn dừng SCC ......70
Bảng 5.4. So sánh phương pháp đề nghị với phương pháp SUCCESS của Marussy
và Buza ......................................................................................................................71
Bảng 5.5. Phân lớp bán giám sát dữ liệu chuỗi thời gian với X-means-Classifier ...72
Bảng 5.6. Thời gian thực thi các giải thuật khi có hay khơng áp dụng thu giảm số
chiều cho dữ liệu đầu vào của X-means (đơn vị: giây) .............................................74
Bảng 5.7. Thời gian thực thi phương pháp SUCCESS của Marussy và Buza (đơn vị:
giây) ...........................................................................................................................74


1

CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
Phần đầu của chương điểm qua một số khái niệm cơ bản liên quan đến đề tài
như: dữ liệu chuỗi thời gian, bài toán phân lớp, bài toán phân lớp bán giám sát dữ liệu
chuỗi thời gian.
Phần thứ hai giới thiệu sơ lược về mục tiêu và nội dung của đề tài. Bên cạnh
đó, phần này cũng nêu lên những nội dung chính trong nghiên cứu và các kết quả đạt
được của luận văn.

Phần cuối chương trình bày tổng quan về cấu trúc tổng thể của toàn bộ luận
văn.
1.1. GIỚI THIỆU ĐỀ TÀI
1.1.1. Dữ liệu chuỗi thời gian

“Lấy mẫu ngẫu nhiên 4000 bức hình từ 15 tờ báo và tạp chí trên thế
giới xuất bản trong giai đoạn 1974 – 1989 cho thấy có hơn 75% là các
hình biểu diễn dữ liệu chuỗi thời gian.”
-- Theo khảo sát của tác giả Tufte, E. R. [40].

Trong thập kỷ vừa qua, với sự phát triển của nhiều loại thiết bị ghi nhận dữ
liệu, đặc biệt là sự phát triển của các cảm biến (sensors), gần như tất cả dữ liệu mà
con người dùng để phục vụ cho cuộc sống của mình đã được ghi nhận một cách tự
động. Các dữ liệu này được lưu trữ trong máy tính mà con người có thể truy xuất khi
cần thiết. Chúng tồn tại trong nhiều ứng dụng thực tế thuộc nhiều lĩnh vực khác nhau
như: kinh tế, tài chính, y tế, giáo dục, mơi trường, địa lý, sinh học,… và tồn tại ở
nhiều dạng thức khác như: số liệu, văn bản, hình ảnh, âm thanh, đoạn phim…


2
Trong các loại dữ liệu trên, dữ liệu chuỗi thời gian (Time series data) xuất
hiện trong nhiều ứng dụng thuộc nhiều lĩnh vực khác nhau. Trong đó, có thể kể đến
những lĩnh vực quan trọng sau đây:
 Kinh tế: tỉ lệ thất nghiệp hàng tháng, số lượng bệnh nhân nhập viện,…
 Tài chính: tỉ giá hối đối (Daily exchange rate), giá cổ phiếu (Share
price),…
 Môi trường: lượng mưa hàng ngày, khơng khí,…
 Y học: hoạt động của sóng não (ECG brain wave), nhịp tim (Heartbeat),…
Với những dẫn chứng và ví dụ nêu trên, chúng ta có thể thấy rằng tầm ảnh
hưởng của dữ liệu chuỗi thời gian là rất lớn và việc hiểu được ý nghĩa của loại dữ liệu

này là rất quan trọng, góp phần quyết định đến sự phát triển của nhiều lĩnh vực.
Xét về khái niệm dữ liệu chuỗi thời gian, nhiều tác giả đã đưa ra các khái
niệm dữ liệu chuỗi thời gian đều thống nhất rằng dữ liệu chuỗi thời gian là tập hợp
các giá trị được quan sát trong những thời điểm cách đều nhau. Ví dụ, giá chứng
khốn hàng ngày của một cơng ty, mực nước được đo mỗi ngày trên một con sơng,
số lượt truy cập một website trong một giây,… Hình 1.1 là một ví dụ về dữ liệu chuỗi
thời gian đo chỉ số giá chứng khốn của cơng ty Apple Inc1 với khoảng thời gian quan
sát khoảng hơn sáu năm.
Trong nghiên cứu, chuỗi thời gian được xem là tập hợp dữ liệu trong không
gian hai chiều, với bộ giá trị (T, V), trong đó T là thời điểm giá trị được xác định, V
là giá trị quan sát tương ứng. Vì khoảng thời gian quan sát là bằng nhau nên có thể
khơng quan tâm đến T. Do đó, chuỗi thời gian có thể được xem là dữ liệu n chiều, với
mỗi chiều là một giá trị được quan sát tại một thời điểm.
Trong đề tài này, chuỗi thời gian được nhìn dưới góc độ là dữ liệu n chiều
và được kí hiệu là 𝑋 = 𝑥1 𝑥2 𝑥3 … 𝑥𝑛 .

1

Nguồn: Từ khóa: Apple


3

Hình 1.1. Dữ liệu chuỗi thời gian
1.1.2. Bài toán phân lớp dữ liệu chuỗi thời gian
Phân lớp (hay phân loại, classification) dữ liệu chuỗi thời gian là việc xây
dựng một mơ hình (model) dự đốn nhãn cho các chuỗi thời gian chưa được phân
lớp (unlabeled time series), mơ hình này được xây dựng dựa trên các chuỗi thời gian
đã được phân lớp (labeled time series), tập các dữ liệu đã được phân lớp để phục vụ
cho việc xây dựng mô hình dự đốn nhãn này được gọi là tập huấn luyện (training

set). Ví dụ, phân lớp các dữ liệu nhịp tim của một bệnh nhân là bình thường (normal)
hay bất thường (abnormal), phân lớp một bài hát vào đúng thể loại của nó,…
Trong lĩnh vực khai phá dữ liệu nói chung và khai phá dữ liệu chuỗi thời
gian nói riêng, vấn đề phân lớp (Classification) là rất quan trọng và là bài toán nền
tảng trong lĩnh vực này. Việc phân lớp dữ liệu chuỗi thời gian có thể được thực hiện
dựa trên các kỹ thuật phân lớp truyền thống khá phổ biến như: k-láng giềng-gần nhất
(k-Nearest Neighbor), Mạng nơ-ron nhân tạo (Artificial Neural Networks), Véc-tơ hỗ
trợ (Support Vector Machine), Cây quyết định (Decision trees),… Đây đều là các kỹ
thuật phân lớp có giám sát, nghĩa là việc phân lớp dựa vào tập huấn luyện mà các đối
tượng trong đó đã được biết nhãn ngay từ đầu (tập huấn luyện đã được phân loại thủ
công bởi các chuyên gia trong lĩnh vực chuyên môn của họ).


4
Như vậy, các kỹ thuật phân lớp truyền thống được liệt kê ở trên không thể
áp dụng khi số lượng các mẫu đã được phân lớp là khá ít. Trong trường hợp này, kỹ
thuật phân lớp bán giám sát (Semi-Supervised Classification) được sử dụng. Phần
tiếp theo giới thiệu sơ lược về vấn đề phân lớp bán giám sát dữ liệu chuỗi thời gian.
1.1.3. Bài toán phân lớp bán giám sát dữ liệu chuỗi thời gian
Như đã trình bày ở trên, hầu hết các phương pháp phân lớp truyền thống đều
giả định rằng dữ liệu huấn luyện (training data) chứa một số lượng lớn các mẫu đã
được gán nhãn (labeled instance). Giả định này không phù hợp trong thực tế, nơi mà
các mẫu chưa được gán nhãn (unlabeled instance) chiếm số lượng rất lớn so với các
mẫu đã được gán nhãn. Do đó, các mơ hình phân lớp truyền thống khơng thể áp dụng
trong hoàn cảnh này.
Để giải quyết vấn đề trên, nhiều cơng trình nghiên cứu về phân lớp bán giám
sát (Semi-Supervised Classification) đã được công bố trong thập kỷ vừa qua. Trong
đó, trên dữ liệu chuỗi thời gian, mơ hình phân lớp bán giám sát được đề xuất bởi Wei
và Keogh (2006) [5] là mơ hình khá nổi tiếng trên loại dữ liệu này. Mơ hình của Wei
và Keogh đã đặt nền tảng cho việc phân lớp bán giám sát dữ liệu chuỗi thời gian và

đã được nhiều tác giả áp dụng, cải tiến trong các nghiên cứu đã được công bố gần
đây.
Đề tài này sẽ tập trung giải quyết các vấn đề liên quan đến phân lớp bán giám
sát dữ liệu chuỗi thời gian và đề nghị một số cải tiến nhằm làm tăng tính chính xác
của tập huấn luyện sau cùng. Các kết quả đạt được của đề tài được trình bày tóm lược
trong phần 1.3 và được trình bày chi tiết trong phần CHƯƠNG 5 và CHƯƠNG 6.
1.2. MỤC TIÊU VÀ GIỚI HẠN ĐỀ TÀI
Mục tiêu nghiên cứu đề tài tập trung vào các vấn đề sau:
 Nghiên cứu về độ đo xoắn thời gian động (Dynamic Time Warping) và
các vấn đề có liên quan đến độ đo này.
 Nghiên cứu về phân lớp bán giám sát chuỗi thời gian.


5
 Nghiên cứu phân lớp bán giám sát chuỗi thời gian dựa vào độ đo xoắn
thời gian động.
 Cải tiến tiêu chuẩn dừng trong phân lớp bán giám sát dữ liệu chuỗi thời
gian.
 Bổ sung quá trình tinh chế cho phân lớp bán giám sát dữ liệu chuỗi thời
gian nhằm làm cho tập huấn luyện kết quả sau cùng chính xác hơn.
1.3. CÁC KẾT QUẢ ĐÃ ĐẠT ĐƯỢC
Đề tài đã có những đóng góp đáng kể trong việc xây dựng bộ phân lớp bán
giám sát dữ liệu chuỗi thời gian được chính xác hơn, cụ thể là những kết quả như sau:
 Đề tài đã đề xuất một mơ hình mới cho phân lớp bán giám sát dữ liệu
chuỗi thời gian. Mơ hình này là sự kết hợp giữa mơ hình học bán giám sát
và các nghiên cứu về tiêu chuẩn dừng trước đó với q trình tinh chế
(Refinement step) được chúng tôi đề xuất. Kết quả thực nghiệm cho thấy
quá trình tinh chế làm cho tập huấn luyện sau cùng chính xác hơn một
cách rõ rệt.
 Đề tài cũng đề xuất một kỹ thuật cải tiến tiêu chuẩn dừng cho phân lớp

bán giám sát dữ liệu chuỗi thời gian dựa trên nguyên lý Chiều dài Mô tả
Nhỏ nhất (Minimum Description Length). Kết quả thực nghiệm cho thấy
tiêu chuẩn dừng cải tiến này chính xác hơn các tiêu chuẩn dừng trước đó.
 Đề tài cũng đã sử dụng giải thuật gom cụm X-means, một cải tiến của Kmeans, để tạo ra một phương pháp phân lớp bán giám sát mới gọi là Xmeans-Classifier. Các kết quả thực nghiệm cho thấy X-means-Classifier
cho kết quả khá tốt và hồn tồn có thể sử dụng cho phân lớp bán giám
sát dữ liệu chuỗi thời gian. X-means-Classifier đã được sử dụng để hỗ trợ
quá trình tinh chế khá thành cơng.
 Đề tài đã sử dụng độ đo xoắn thời gian động cho phân lớp bán giám sát
kết hợp với ràng buộc Sakoe-Chiba nhằm tăng tốc q trình tính tốn và
giảm thiểu những đường xoắn khơng có nhiều ý nghĩa trên độ đo này.


6
Với những kết quả đạt được nêu trên, chúng tôi tin rằng những phương pháp
cải tiến được đề nghị trong đề tài đã góp phần xây dựng bộ phân lớp bán giám sát
chuỗi thời gian khá tốt.
1.4. CẤU TRÚC CỦA LUẬN VĂN
Luận văn được chia làm 6 phần chính như sau:
CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
Chương này giới thiệu sợ lược về đề tài cũng như giới thiệu các định
nghĩa, các vấn đề có liên quan như: Dữ liệu chuỗi thời gian, Bài toán
phân lớp, Bài toán phân lớp bán giám sát, Mục tiêu nghiên cứu của đề
tài, Tóm lược các kết quả đạt được của đề tài và Cấu trúc của luận văn.
CHƯƠNG 2. NHỮNG CÔNG TRÌNH LIÊN QUAN
Chương này trình bày sơ lược về các cơng trình có liên quan đến bài
tốn phân lớp bán giám sát dữ liệu chuỗi thời gian như: Các độ đo tương
tự trên dữ liệu chuỗi thời gian, Các phương pháp thu giảm số chiều trên
dữ liệu chuỗi thời gian, Các giải thuật gom cụm, Vấn đề phân lớp có
giám sát dựa trên k-láng giềng-gần nhất (k-NN), Các mơ hình phân lớp
bán giám sát dữ liệu chuỗi thời gian, Các cơng trình về tiêu chuẩn dừng

cho phân lớp bán giám sát dữ liệu chuỗi thời gian cho mơ hình của Wei
và Keogh.
CHƯƠNG 3. CƠ SỞ LÝ THUYẾT
Chương này trình bày chi tiết về các kỹ thuật được áp dụng trong đề tài
như: độ đo xoắn thời gian động, ràng buộc dải Sakoe-Chiba trong độ đo
xoắn thời gian động, thu giảm số chiều dữ liệu chuỗi thời gian bằng
phương pháp xấp xỉ gộp từng đoạn, giải thuật gom cụm X-means, mơ
hình phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và Keogh,
Các tiêu chuẩn dừng trong phân lớp bán giám sát dữ liệu chuỗi thời gian
cho mơ hình của Wei và Keogh, phương pháp phân lớp bán giám sát dữ
liệu chuỗi thời gian SUCCESS của Marussy và Buza. Chương này cũng


7
trình bày một số nhận xét về các phương pháp trước đây và đề xuất một
số hướng cải tiến.
CHƯƠNG 4. PHƯƠNG PHÁP ĐỀ NGHỊ
Chương này trình bày mơ hình phân lớp bán giám sát được sử dụng trong
đề tài, Một cải tiến trong tiêu chuẩn dừng dựa trên nguyên lý Chiều dài
Mơ tả Nhỏ nhất và trình bày đề xuất thêm một bước tinh chế cho tập
huấn luyện (Refinement step).
CHƯƠNG 5. THỰC NGHIỆM
Chương này trình bày hai kết quả thực nghiệm quan trọng là so sánh tiêu
chuẩn dừng MDL cải tiến (Phương pháp đề nghị) so với các tiêu chuẩn
dừng trước đó và thực nghiệm so sánh tập huấn luyện trước và sau khi
tinh chế (Phương pháp đề nghị). Bên cạnh đó cũng trình bày thêm một
số thực nghiệm khác như: so sánh phương pháp đề nghị với phương
pháp SUCCESS của Marussy và Buza, thực nghiệm phân lớp bán giám
sát dựa trên X-means (X-means-Classifier), thời gian thực thi của các
giải thuật. Kết quả các thực nghiệm cho thấy tiểu chuẩn dừng dựa trên

MDL cải tiến và quá trình tinh chế góp phần làm cho tập huấn luyện kết
quả trở nên tốt hơn.
CHƯƠNG 6. TỔNG KẾT
Chương này trình bày tóm lược về phân lớp bán giám sát dữ liệu chuỗi
thời gian, rút ra một số nhận xét, các kết quả đạt được của đề tài, rút ra
kết luận về các kết quả đã đạt được và hướng phát triển của đề tài.


8

CHƯƠNG 2. NHỮNG CƠNG TRÌNH LIÊN QUAN
Phần đầu của chương trình bày những cơng trình về độ đo tương tự trên dữ
liệu chuỗi thời gian như độ đo Minkowski, độ đo xoắn thời gian động và độ đo chuỗi
con chung dài nhất.
Phần thứ hai trình bày về một số phương pháp thu giảm số chiều dữ liệu
chuỗi thời gian.
Phần thứ ba trình bày một số phương pháp gom cụm trong khai phá dữ liệu
như giải thuật K-means, giải thuật X-means, phương pháp gom cụm phân cấp.
Phần phần cuối cùng trình bày những cơng trình liên quan đến bài tốn phân
lớp trên dữ liệu chuỗi thời gian như phân lớp có giám sát dựa trên tìm kiếm k-láng
giềng-gần nhất, phân lớp bán giám sát dữ liệu chuỗi thời gian với mô hình của Wei
và Keogh cùng với những cơng trình về tiêu chuẩn dừng trong phân lớp bán giám sát
dữ liệu chuỗi thời gian theo mơ hình của Wei và Keogh, các phương pháp phân lớp
bán giám sát dữ liệu chuỗi thời gian dựa vào gom cụm như: LCLC và En-LCLC của
Nhut và các cộng sự, phương pháp SUCCESS của Murassy và Buza.
2.1. NHỮNG CƠNG TRÌNH VỀ ĐỘ ĐO TƯƠNG TỰ
Phần này trình bày một số nghiên cứu về cách đánh giá độ tương tự cho dữ
liệu chuỗi thời gian. Cho đến thời điểm hiện tại, nhiều tác giả đã đề nghị nhiều độ đo
tương tự khác nhau, mỗi độ đo tương tự thích hợp với từng loại dữ liệu trong từng
hồn cảnh khác nhau.

Vấn đề quan trọng của bài tốn phân lớp dựa vào sự tương tự là việc đánh
giá khoảng cách của hai đối tượng dữ liệu Oi, Oj. Trong trường hợp hai đối tượng này
hoàn toàn giống nhau thì khoảng cách này sẽ là 0 và ngược lại chúng càng khác nhau
thì khoảng cách càng lớn. Để có thể tính tốn và so sánh với nhau thì các khoảng cách
này được biểu diễn thành các số thực.


9
Độ đo khoảng cách giữa các đối tượng nên 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)
Độ đo tương tự có ý nghĩa quan trọng trong hầu hết các bài toán trên dữ liệu
chuỗi thời gian. Trong các mơ hình có dùng rút trích đặc trưng hay thu giảm số chiều,
độ đo tương tự phải thỏa mãn tính chất sau. Gọi Xf, Yf là biểu diễn của X,Y sau khi
trích xuất đặc trưng hay thu giảm số chiều, độ đo khoảng cách D phải đảm bảo: D(Xf,
Yf) ≤ D(X, Y).
Trong phần này, độ đo tương tự được định nghĩa trên hai chuỗi có chiều dài
bằng nhau X, Y và được ký hiệu Sim(X, Y) [1]. Sau đây là những phương pháp đánh
giá độ tương tự đã được một số tác giả đề nghị:
2.1.1. Độ đo Minkowski
Hầu hết các cơng trình đều dựa trên độ đo khoảng cách này. Khoảng cách
Minkowski được định nghĩa như sau:
𝑝

𝑆𝑖𝑚(𝑋, 𝑌) = √∑𝑛𝑖=1(𝑥𝑖 − 𝑦𝑖 )𝑝 , trong đó 𝑝 = 1 … ∞
Tuy p có thể có nhiều giá trị khác nhau nhưng trong các nghiên cứu p thường
nhận các giá trị 1 (khoảng cách Manhattan), 2 (khoảng cách Euclid),
Max). Giá trị p = 2 được dùng phổ biến nhất.

Một số ưu điểm và nhược điểm của phương pháp này:
 Ưu điểm
- Q trình tính toán đơn giản và dễ dàng.

 (khoảng

cách


10
- Phù hợp khi sử dụng các biến đổi: Discrete Fourier Tranform (DFT),
Discrete

Wavelet

Transform

(DWT),

Piecewise

Aggregate

Approximation (PAA), Adaptive Piecewise Constant Approximation
(APCA), SAX (Symbolic Aggregate approXimation).
 Nhược điểm
- Nhạy cảm với nhiễu.
- Không hiệu quả với dữ liệu được đo ở nhiều thang đo khác nhau.
Để khắc phục những nhược điểm trên, nhiều tác giả đã đưa ra những phương
pháp sau đây:

 Das, G. và các cộng sự (1997) [1] đề nghị nên chuẩn hóa dữ liệu chuỗi
thời gian trước khi áp dụng các giải thuật so trùng mẫu dựa trên giá trị
trung bình và độ lệch chuẩn X’ = X - mean(X) hoặc X’ = (X- mean(X)) /
var(X).
 Rafiei, D. và Mendelzon, A. O. (1998) [2] đề nghị áp dụng phương pháp
trung bình di chuyển (moving average) để làm trơn các đường biểu diễn
dữ liệu chuỗi thời gian theo công thức sau:
𝑘

𝑥𝑖 = ∑ 𝑥𝑗+𝑘 ⁄(2𝑘 + 1)
𝑗= −𝑘

 Chan, K. và Fu, A. W. (1999) [3] đề nghị cách tính độ tương tự có sự thay
đổi dựa trên khoảng cách Euclid như sau:
𝑆𝑖𝑚 (𝑋, 𝑌) = √∑((𝑦𝑖 − 𝑥𝑖 ) − (𝑦𝐴 − 𝑥𝐴 ))
1

1

𝑛

𝑛

2

𝑛−1
Trong đó: 𝑥𝐴 = ∑𝑛−1
𝑖=0 𝑥𝑖 , 𝑦𝐴 = ∑𝑖=0 𝑦𝑖

2.1.2. Phương pháp xoắn thời gian động

Phương pháp xoắn thời gian động (Dynamic Time Warping – DTW) tương
tự cách tính khoảng cách Minkowski nhưng thay vì so trùng hai đường biểu diễn dữ