Link tải luận văn miễn phí cho ae Kết nối
Khai thác dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén = Time series data mining based on feature extraction with middle points and clipping method
TÓM TẮT
Để khắc phục đặc điểm khối lƣợng lớn của dữ liệu chuỗi thời gian, nhiều phƣơng
pháp thu giảm số chiều dựa vào rút trích đặc trƣng đã đƣợc đề xuất và sử dụng. Tuy
nhiên có không ít phƣơng pháp thu giảm số chiều mắc phải hai nhƣợc điểm quan
trọng: một số phƣơng pháp thu giảm số chiều không chứng minh đƣợc bằng toán học
thỏa mãn điều kiện chặn dƣới và một số phƣơng pháp khác không đề xuất đƣợc cấu
trúc chỉ mục thích hợp đi kèm để hỗ trợ việc tìm kiếm tƣơng tự hữu hiệu.
Đóng góp thứ nhất của luận án này là đề xuất một phƣơng pháp thu giảm số
chiều mới dựa vào điểm giữa và kỹ thuật xén, có tên là MP_C (Middle points and
Clipping), và kết hợp phƣơng pháp này với chỉ mục đƣờng chân trời hỗ trợ việc tìm
kiếm tƣơng tự một cách hữu hiệu. Qua lý thuyết và thực nghiệm, chúng tui chứng
minh đƣợc phƣơng pháp MP_C thỏa điều kiện chặn dƣới, là điều kiện nhằm đảm bảo
không để xảy ra lỗi tìm sót khi tìm kiếm tƣơng tự. Thực nghiệm còn cho thấy phƣơng
pháp MP_C hiệu quả hơn một phƣơng pháp đƣợc ƣa chuộng, phƣơng pháp xấp xỉ gộp
từng đoạn (PAA- Piecewise Aggregate Approximation), và phƣơng pháp xén dữ liệu
(Clipping) về cả ba tiêu chí: độ chặt chặn dƣới, tỉ lệ thu giảm truy xuất và thời gian
thực thi. Luận án còn cho thấy phƣơng pháp MP_C có thể sử dụng hiệu quả cho bài
toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng, một bài toán rất thời
sự, đã và đang đƣợc quan tâm nghiên cứu trong thời gian gần đây, dựa vào cách tính
toán gia tăng phƣơng pháp MP_C và chính sách cập nhật chỉ mục trì hoãn (deferred
update policy).
Đóng góp thứ hai của luận án này là việc ứng dụng thành công phƣơng pháp thu
giảm số chiều MP_C và cấu trúc chỉ mục đƣờng chân trời vào ba bài toán quan trọng
trong khai phá dữ liệu chuỗi thời gian: gom cụm, phát hiện motif và dự báo trên dữ
liệu chuỗi thời gian. Với bài toán gom cụm, chúng tui vận dụng tính chất đa mức phân
giải của phƣơng pháp MP_C để có thể sử dụng giải thuật I-k-Means gom cụm dữ liệu
chuỗi thời gian và đề xuất thêm cách sử dụng kd-tree để xác định các trung tâm cụm
ban đầu cho giải thuật I-k-Means nhằm khắc phục nhƣợc điểm của giải thuật này khi
chọn các trung tâm cụm ở mức khởi động một cách ngẫu nhiên. Với bài toán phát hiện
motif, chúng tui đề xuất hai giải thuật phát hiện motif xấp xỉ trên dữ liệu chuỗi thời
gian: (1) giải thuật sử dụng R*-tree kết hợp với ý tƣởng từ bỏ sớm khi tính toán
khoảng cách Euclid và (2) giải thuật vận dụng phƣơng pháp thu giảm số chiều MP_C
kết hợp với cấu trúc chỉ mục đƣờng chân trời. Trong hai giải thuật này, giải thuật thứ
hai tỏ ra có hiệu quả cao hơn. Với bài toán dự báo dữ liệu chuỗi thời gian, chúng tôi
vận dụng phƣơng pháp thu giảm số chiều MP_C kết hợp với cấu trúc chỉ mục đƣờng
chân trời vào trong phƣơng pháp dự báo “tìm kiếm k lân cận gần nhất” (k-NN) và thực
nghiệm cho thấy phƣơng pháp này cho ra kết quả dự báo chính xác cao hơn và thời
gian dự báo nhanh hơn so với mô hình mạng nơ ron nhân tạo (ANN) khi dự báo với dữ
liệu có tính mùa hay xu hƣớng.
ABSTRACT
To overcome high dimensionality of time series data, several dimensionality re
duction methods, which is based on feature extraction, have been proposed and used.
However, a number of these methods did not provide any formal proof that they satis
fy the lower bounding condition while many of them did not go with any multidimen
sional index structure which helps in fast retrieval.
The first contribution of this thesis is a new dimensionality reduction method
based on Middle points and Clipping, called MP_C, which performs effectively with
the support of Skyline index. Through formal proof and experiments on benchmark
datasets, we show that MP_C satisfies the lower bounding condition which guarantees
no false dismissals. Experimental results also reveal that MP_C is more effective than
the popular dimensionality reduction method, Piecewise Aggregate Approximation
(PAA) and the Clipping method in terms of tightness of lower bound, pruning ratio
and running time. We also proposed the extension of MP_C in Kontaki framework
which can be applied effectively for similarity search in streaming time series.
The second contribution of this thesis is the application of MP_C method to the
three important time series data mining tasks: clustering, motif detection and time se
ries prediction. As for clustering, we exploit the multi-resolution property of MP_C in
using I-k-Means algorithm for time series clustering and propose the use of kd-tree in
choosing initial centroids for I-k-Means algorithm in order to overcome the drawback
of randomly determining the initial centroids in the first level of I-k-Means. As for
motif discovery, we propose two algorithms for finding approximate motif in time se
ries data: (1) the algorithm that uses R*-tree combined with the idea of early abandon
ing in Euclidean distance computation and (2) the algorithm using MP_C associated
with Skyline index; and between the two algorithms, the latter is more effective than
the former. As for time series prediction, we propose the use of MP_C with Skyline
index in a prediction approach based on a “k-nearest-neighbors” algorithm and expe
riments show that the proposed method performs better than artificial neural network
model in terms of prediction accuracy and computation time, especially for seasonal
and trend time series
CHƢƠNG 1. GIỚI THIỆU..............................................................................................1
1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan. ..................1
1.2 Mục tiêu, đối tƣợng và phạm vi nghiên cứu. .....................................................4
1.3 Nhiệm vụ và hƣớng tiếp cận của luận án. ..........................................................6
1.4 Tóm tắt kết quả đạt đƣợc....................................................................................7
1.5 Cấu trúc của luận án. ..........................................................................................9
CHƢƠNG 2. CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN..............10
2.1 Các độ đo tƣơng tự. ..........................................................................................10
2.1.1 Độ đo Euclid. ...............................................................................................10
2.1.2 Độ đo xoắn thời gian động...........................................................................11
2.2 Thu giảm số chiều chuỗi thời gian. ..................................................................12
2.2.1 Điều kiện chặn dƣới. ....................................................................................12
2.2.2 Các phƣơng pháp thu giảm số chiều dựa vào rút trích đặc trƣng. ...............13
2.2.3 Về tính đúng đắn và tính khả chỉ mục của các phƣơng pháp thu giảm số
chiều. ............................................................................................................21
2.3 Rời rạc hóa chuỗi thời gian. .............................................................................22
2.4 Cấu trúc chỉ mục...............................................................................................23
2.4.1 R-tree............................................................................................................23
2.4.2 Chỉ mục đƣờng chân trời. ............................................................................25
2.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..............................................27
2.5.1 Ý tƣởng tổng quát. .......................................................................................27
2.5.2 So trùng toàn chuỗi và so trùng chuỗi con...................................................27
2.5.3 Độ đo khoảng cách nhóm và điều kiện chặn dƣới nhóm.............................28
2.5.4 Các phƣơng pháp tìm kiếm tƣơng tự liên quan. ..........................................28
2.6 Tìm kiếm tƣơng tự trên chuỗi thời gian dạng luồng. .......................................29
2.7 Phát hiện motif trên chuỗi thời gian.................................................................32
2.7.1 Các khái niệm cơ bản về motif. ...................................................................32
2.7.2 Tổng quan về một số phƣơng pháp phát hiện motif tiêu biểu. ....................36
2.8 Gom cụm dữ liệu chuỗi thời gian.....................................................................41
2.8.1 Giới thiệu. ....................................................................................................41
2.8.2 Giải thuật K-Means......................................................................................42
2.8.3 Gom cụm bằng thuật toán I-k-Means. .........................................................43
CHƢƠNG 3. THU GIẢM SỐ CHIỀU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP
MP_C.......................................................................................................46
3.1 Phƣơng pháp thu giảm số chiều MP_C (Middle Points_Clipping). ................46
3.2 Độ đo tƣơng tự trong không gian đặc trƣng MP_C. ........................................49
3.3 Độ phức tạp của giải thuật thu giảm số chiều theo phƣơng pháp MP_C.........52
3.4 Cấu trúc chỉ mục đƣờng chân trời cho các chuỗi thời gian đƣợc biểu diễn bằng
MP_C................................................................................................................53
3.4.1 Vùng bao MP_C (MP_C_BR). ....................................................................53
3.4.2 Hàm tính khoảng cách giữa chuỗi truy vấn Q và MP_C_BR.....................54
3.4.3 Chỉ mục đƣờng chân trời cho phƣơng pháp biểu diễn MP_C. ....................56
3.4.4 Xử lý các câu truy vấn có chiều dài khác nhau............................................58
3.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng dựa vào phƣơng
pháp MP_C và chỉ mục đƣờng chân trời..........................................................60
3.6 Kết quả thực nghiệm. .......................................................................................61
3.6.1 Thực nghiệm về bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..62
3.6.2 Thực nghiệm về tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng..
....................................................................................................................74
CHƢƠNG 4. PHÁT HIỆN MOTIF DỰA VÀO CẤU TRÚC CHỈ MỤC ĐA CHIỀU
HOẶC CHỈ MỤC ĐƢỜNG CHÂN TRỜI .............................................78
4.1 Phƣơng pháp phát hiện motif dựa vào cấu trúc chỉ mục đa chiều và kỹ thuật từ
bỏ sớm. .............................................................................................................78
4.2 Phát hiện motif xấp xỉ dựa trên phƣơng pháp MP_C với sự hỗ trợ của chỉ mục
đƣờng chân trời.................................................................................................84
4.3 Thực nghiệm về bài toán phát hiện motif.........................................................87
4.3.1 Thực nghiệm 1: So sánh ba giải thuật dùng R*-tree, RP và R*-tree kết hợp
với từ bỏ sớm. ..............................................................................................88
4.3.2 Thực nghiệm 2: So sánh ba giải thuật dùng R*-tree, RP và MP_C kết hợp
với chỉ mục đƣờng chân trời. .......................................................................91
CHƢƠNG 5. GOM CỤM CHUỖI THỜI GIAN ĐƢỢC THU GIẢM THEO PHƢƠNG
PHÁP MP_C BẰNG GIẢI THUẬT I-K-MEANS .................................97
5.1 Tóm tắt một số kỹ thuật chọn trung tâm cụm khởi động thuật toán k-Means. 97
5.2 Biểu diễn chuỗi thời gian ở nhiều mức xấp xỉ theo phƣơng pháp MP_C........99
5.3 Kd-tree..............................................................................................................99
5.4 Dùng kd-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means.
........................................................................................................................100
5.5 Dùng CF-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means.
........................................................................................................................103
5.5.1 Đặc trƣng cụm và CF-tree (Cluster Feature tree). .....................................103
5.5.2 Dùng CF-tree để tạo các trung tâm cụm cho thuật toán I-k-Means...........105
5.6 Thực nghiệm về bài toán gom cụm. ...............................................................106
5.6.1 Các tiêu chuẩn đánh giá chất lƣợng của giải thuật gom cụm. ...................106
5.6.2 Dữ liệu dùng trong thực nghiệm. ...............................................................108
5.6.3 Kết quả thực nghiệm về bài toán gom cụm. ..............................................109
CHƢƠNG 6. DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN CÓ TÍNH XU HƢỚNG
HOẶC MÙA BẰNG PHƢƠNG PHÁP SO TRÙNG MẪU.................115
6.1 Các công trình liên quan.................................................................................115
6.2 Xu hƣớng và tính mùa trong dữ liệu chuỗi thời gian. ....................................117
6.3 Hai phƣơng pháp dự báo dữ liệu chuỗi thời gian...........................................118
6.3.1 Dự báo chuỗi thời gian bằng mạng nơ ron nhân tạo..................................118
6.3.2 Phƣơng pháp đề xuất: k-lân cận gần nhất. .................................................121
6.4 Đánh giá bằng thực nghiệm............................................................................123
CHƢƠNG 7. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.............................................131
7.1 Các đóng góp chính của luận án.....................................................................131
7.2 Hạn chế của luận án........................................................................................132
7.3 Hƣớng phát triển.............................................................................................133
CÁC TÀI LIỆU CÔNG BỐ CỦA TÁC GIẢ..............................................................134
1. Các công trình liên quan trực tiếp đến luận án....................................................134
2. Các công trình liên quan gián tiếp đến luận án. ..................................................135
TÀI LIỆU THAM KHẢO ...........................................................................................136
Phụ lục A. Chứng minh độ đo DMP_C(Q’, C’) thỏa các tính chất của một không gian
metric .....................................................................................................148
CHƢƠNG 1. GIỚI THIỆU
Trong chƣơng này, chúng tui sẽ trình bày tổng quan về chuỗi thời gian và các bài
toán quan trọng trong khai phá dữ liệu chuỗi thời gian. Tiếp theo là mục tiêu, đối
tƣợng, phạm vi nghiên cứu của luận án và tóm tắt kết quả nghiên cứu đạt đƣợc. Cuối
cùng là cấu trúc của luận án này.
1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan.
Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu đƣợc đo theo
từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất. Hình 1.1 minh
họa một ví dụ về chuỗi thời gian biểu diễn tỉ giá chuyển đổi trung bình hàng tháng
giữa đô la Úc và đô la Mỹ (đơn vị đô la Úc) từ 7/1969 đến 8/1995.
Hình 1.1 Đường biểu diễn một chuỗi thời gian ( [1]).
Một chuỗi thời gian dạng luồng (streaming time series) C là một chuỗi thời gian
trong đó các giá trị mới tới một cách liên tục và đƣợc nối vào cuối chuỗi C theo thứ tự
thời gian. Vì một chuỗi thời gian dạng luồng bao gồm một số lớn các giá trị, sự tƣơng
tự giữa hai chuỗi thƣờng đƣợc tính dựa trên W giá trị cuối cùng (W là chiều dài cửa sổ
trƣợt). Cho nên, nếu W = 1024 thì mỗi chuỗi đƣợc coi nhƣ một điểm trong không gian
1024 chiều.
Các bài toán thƣờng đƣợc nghiên cứu trong khai phá dữ liệu chuỗi thời gian gồm
tìm kiếm tương tự (similarity search), gom cụm (clustering), phân lớp (classification),
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Khai thác dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén = Time series data mining based on feature extraction with middle points and clipping method
TÓM TẮT
Để khắc phục đặc điểm khối lƣợng lớn của dữ liệu chuỗi thời gian, nhiều phƣơng
pháp thu giảm số chiều dựa vào rút trích đặc trƣng đã đƣợc đề xuất và sử dụng. Tuy
nhiên có không ít phƣơng pháp thu giảm số chiều mắc phải hai nhƣợc điểm quan
trọng: một số phƣơng pháp thu giảm số chiều không chứng minh đƣợc bằng toán học
thỏa mãn điều kiện chặn dƣới và một số phƣơng pháp khác không đề xuất đƣợc cấu
trúc chỉ mục thích hợp đi kèm để hỗ trợ việc tìm kiếm tƣơng tự hữu hiệu.
Đóng góp thứ nhất của luận án này là đề xuất một phƣơng pháp thu giảm số
chiều mới dựa vào điểm giữa và kỹ thuật xén, có tên là MP_C (Middle points and
Clipping), và kết hợp phƣơng pháp này với chỉ mục đƣờng chân trời hỗ trợ việc tìm
kiếm tƣơng tự một cách hữu hiệu. Qua lý thuyết và thực nghiệm, chúng tui chứng
minh đƣợc phƣơng pháp MP_C thỏa điều kiện chặn dƣới, là điều kiện nhằm đảm bảo
không để xảy ra lỗi tìm sót khi tìm kiếm tƣơng tự. Thực nghiệm còn cho thấy phƣơng
pháp MP_C hiệu quả hơn một phƣơng pháp đƣợc ƣa chuộng, phƣơng pháp xấp xỉ gộp
từng đoạn (PAA- Piecewise Aggregate Approximation), và phƣơng pháp xén dữ liệu
(Clipping) về cả ba tiêu chí: độ chặt chặn dƣới, tỉ lệ thu giảm truy xuất và thời gian
thực thi. Luận án còn cho thấy phƣơng pháp MP_C có thể sử dụng hiệu quả cho bài
toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng, một bài toán rất thời
sự, đã và đang đƣợc quan tâm nghiên cứu trong thời gian gần đây, dựa vào cách tính
toán gia tăng phƣơng pháp MP_C và chính sách cập nhật chỉ mục trì hoãn (deferred
update policy).
Đóng góp thứ hai của luận án này là việc ứng dụng thành công phƣơng pháp thu
giảm số chiều MP_C và cấu trúc chỉ mục đƣờng chân trời vào ba bài toán quan trọng
trong khai phá dữ liệu chuỗi thời gian: gom cụm, phát hiện motif và dự báo trên dữ
liệu chuỗi thời gian. Với bài toán gom cụm, chúng tui vận dụng tính chất đa mức phân
giải của phƣơng pháp MP_C để có thể sử dụng giải thuật I-k-Means gom cụm dữ liệu
chuỗi thời gian và đề xuất thêm cách sử dụng kd-tree để xác định các trung tâm cụm
ban đầu cho giải thuật I-k-Means nhằm khắc phục nhƣợc điểm của giải thuật này khi
chọn các trung tâm cụm ở mức khởi động một cách ngẫu nhiên. Với bài toán phát hiện
motif, chúng tui đề xuất hai giải thuật phát hiện motif xấp xỉ trên dữ liệu chuỗi thời
gian: (1) giải thuật sử dụng R*-tree kết hợp với ý tƣởng từ bỏ sớm khi tính toán
khoảng cách Euclid và (2) giải thuật vận dụng phƣơng pháp thu giảm số chiều MP_C
kết hợp với cấu trúc chỉ mục đƣờng chân trời. Trong hai giải thuật này, giải thuật thứ
hai tỏ ra có hiệu quả cao hơn. Với bài toán dự báo dữ liệu chuỗi thời gian, chúng tôi
vận dụng phƣơng pháp thu giảm số chiều MP_C kết hợp với cấu trúc chỉ mục đƣờng
chân trời vào trong phƣơng pháp dự báo “tìm kiếm k lân cận gần nhất” (k-NN) và thực
nghiệm cho thấy phƣơng pháp này cho ra kết quả dự báo chính xác cao hơn và thời
gian dự báo nhanh hơn so với mô hình mạng nơ ron nhân tạo (ANN) khi dự báo với dữ
liệu có tính mùa hay xu hƣớng.
ABSTRACT
To overcome high dimensionality of time series data, several dimensionality re
duction methods, which is based on feature extraction, have been proposed and used.
However, a number of these methods did not provide any formal proof that they satis
fy the lower bounding condition while many of them did not go with any multidimen
sional index structure which helps in fast retrieval.
The first contribution of this thesis is a new dimensionality reduction method
based on Middle points and Clipping, called MP_C, which performs effectively with
the support of Skyline index. Through formal proof and experiments on benchmark
datasets, we show that MP_C satisfies the lower bounding condition which guarantees
no false dismissals. Experimental results also reveal that MP_C is more effective than
the popular dimensionality reduction method, Piecewise Aggregate Approximation
(PAA) and the Clipping method in terms of tightness of lower bound, pruning ratio
and running time. We also proposed the extension of MP_C in Kontaki framework
which can be applied effectively for similarity search in streaming time series.
The second contribution of this thesis is the application of MP_C method to the
three important time series data mining tasks: clustering, motif detection and time se
ries prediction. As for clustering, we exploit the multi-resolution property of MP_C in
using I-k-Means algorithm for time series clustering and propose the use of kd-tree in
choosing initial centroids for I-k-Means algorithm in order to overcome the drawback
of randomly determining the initial centroids in the first level of I-k-Means. As for
motif discovery, we propose two algorithms for finding approximate motif in time se
ries data: (1) the algorithm that uses R*-tree combined with the idea of early abandon
ing in Euclidean distance computation and (2) the algorithm using MP_C associated
with Skyline index; and between the two algorithms, the latter is more effective than
the former. As for time series prediction, we propose the use of MP_C with Skyline
index in a prediction approach based on a “k-nearest-neighbors” algorithm and expe
riments show that the proposed method performs better than artificial neural network
model in terms of prediction accuracy and computation time, especially for seasonal
and trend time series
CHƢƠNG 1. GIỚI THIỆU..............................................................................................1
1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan. ..................1
1.2 Mục tiêu, đối tƣợng và phạm vi nghiên cứu. .....................................................4
1.3 Nhiệm vụ và hƣớng tiếp cận của luận án. ..........................................................6
1.4 Tóm tắt kết quả đạt đƣợc....................................................................................7
1.5 Cấu trúc của luận án. ..........................................................................................9
CHƢƠNG 2. CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN..............10
2.1 Các độ đo tƣơng tự. ..........................................................................................10
2.1.1 Độ đo Euclid. ...............................................................................................10
2.1.2 Độ đo xoắn thời gian động...........................................................................11
2.2 Thu giảm số chiều chuỗi thời gian. ..................................................................12
2.2.1 Điều kiện chặn dƣới. ....................................................................................12
2.2.2 Các phƣơng pháp thu giảm số chiều dựa vào rút trích đặc trƣng. ...............13
2.2.3 Về tính đúng đắn và tính khả chỉ mục của các phƣơng pháp thu giảm số
chiều. ............................................................................................................21
2.3 Rời rạc hóa chuỗi thời gian. .............................................................................22
2.4 Cấu trúc chỉ mục...............................................................................................23
2.4.1 R-tree............................................................................................................23
2.4.2 Chỉ mục đƣờng chân trời. ............................................................................25
2.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..............................................27
2.5.1 Ý tƣởng tổng quát. .......................................................................................27
2.5.2 So trùng toàn chuỗi và so trùng chuỗi con...................................................27
2.5.3 Độ đo khoảng cách nhóm và điều kiện chặn dƣới nhóm.............................28
2.5.4 Các phƣơng pháp tìm kiếm tƣơng tự liên quan. ..........................................28
2.6 Tìm kiếm tƣơng tự trên chuỗi thời gian dạng luồng. .......................................29
2.7 Phát hiện motif trên chuỗi thời gian.................................................................32
2.7.1 Các khái niệm cơ bản về motif. ...................................................................32
2.7.2 Tổng quan về một số phƣơng pháp phát hiện motif tiêu biểu. ....................36
2.8 Gom cụm dữ liệu chuỗi thời gian.....................................................................41
2.8.1 Giới thiệu. ....................................................................................................41
2.8.2 Giải thuật K-Means......................................................................................42
2.8.3 Gom cụm bằng thuật toán I-k-Means. .........................................................43
CHƢƠNG 3. THU GIẢM SỐ CHIỀU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP
MP_C.......................................................................................................46
3.1 Phƣơng pháp thu giảm số chiều MP_C (Middle Points_Clipping). ................46
3.2 Độ đo tƣơng tự trong không gian đặc trƣng MP_C. ........................................49
3.3 Độ phức tạp của giải thuật thu giảm số chiều theo phƣơng pháp MP_C.........52
3.4 Cấu trúc chỉ mục đƣờng chân trời cho các chuỗi thời gian đƣợc biểu diễn bằng
MP_C................................................................................................................53
3.4.1 Vùng bao MP_C (MP_C_BR). ....................................................................53
3.4.2 Hàm tính khoảng cách giữa chuỗi truy vấn Q và MP_C_BR.....................54
3.4.3 Chỉ mục đƣờng chân trời cho phƣơng pháp biểu diễn MP_C. ....................56
3.4.4 Xử lý các câu truy vấn có chiều dài khác nhau............................................58
3.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng dựa vào phƣơng
pháp MP_C và chỉ mục đƣờng chân trời..........................................................60
3.6 Kết quả thực nghiệm. .......................................................................................61
3.6.1 Thực nghiệm về bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..62
3.6.2 Thực nghiệm về tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng..
....................................................................................................................74
CHƢƠNG 4. PHÁT HIỆN MOTIF DỰA VÀO CẤU TRÚC CHỈ MỤC ĐA CHIỀU
HOẶC CHỈ MỤC ĐƢỜNG CHÂN TRỜI .............................................78
4.1 Phƣơng pháp phát hiện motif dựa vào cấu trúc chỉ mục đa chiều và kỹ thuật từ
bỏ sớm. .............................................................................................................78
4.2 Phát hiện motif xấp xỉ dựa trên phƣơng pháp MP_C với sự hỗ trợ của chỉ mục
đƣờng chân trời.................................................................................................84
4.3 Thực nghiệm về bài toán phát hiện motif.........................................................87
4.3.1 Thực nghiệm 1: So sánh ba giải thuật dùng R*-tree, RP và R*-tree kết hợp
với từ bỏ sớm. ..............................................................................................88
4.3.2 Thực nghiệm 2: So sánh ba giải thuật dùng R*-tree, RP và MP_C kết hợp
với chỉ mục đƣờng chân trời. .......................................................................91
CHƢƠNG 5. GOM CỤM CHUỖI THỜI GIAN ĐƢỢC THU GIẢM THEO PHƢƠNG
PHÁP MP_C BẰNG GIẢI THUẬT I-K-MEANS .................................97
5.1 Tóm tắt một số kỹ thuật chọn trung tâm cụm khởi động thuật toán k-Means. 97
5.2 Biểu diễn chuỗi thời gian ở nhiều mức xấp xỉ theo phƣơng pháp MP_C........99
5.3 Kd-tree..............................................................................................................99
5.4 Dùng kd-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means.
........................................................................................................................100
5.5 Dùng CF-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means.
........................................................................................................................103
5.5.1 Đặc trƣng cụm và CF-tree (Cluster Feature tree). .....................................103
5.5.2 Dùng CF-tree để tạo các trung tâm cụm cho thuật toán I-k-Means...........105
5.6 Thực nghiệm về bài toán gom cụm. ...............................................................106
5.6.1 Các tiêu chuẩn đánh giá chất lƣợng của giải thuật gom cụm. ...................106
5.6.2 Dữ liệu dùng trong thực nghiệm. ...............................................................108
5.6.3 Kết quả thực nghiệm về bài toán gom cụm. ..............................................109
CHƢƠNG 6. DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN CÓ TÍNH XU HƢỚNG
HOẶC MÙA BẰNG PHƢƠNG PHÁP SO TRÙNG MẪU.................115
6.1 Các công trình liên quan.................................................................................115
6.2 Xu hƣớng và tính mùa trong dữ liệu chuỗi thời gian. ....................................117
6.3 Hai phƣơng pháp dự báo dữ liệu chuỗi thời gian...........................................118
6.3.1 Dự báo chuỗi thời gian bằng mạng nơ ron nhân tạo..................................118
6.3.2 Phƣơng pháp đề xuất: k-lân cận gần nhất. .................................................121
6.4 Đánh giá bằng thực nghiệm............................................................................123
CHƢƠNG 7. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.............................................131
7.1 Các đóng góp chính của luận án.....................................................................131
7.2 Hạn chế của luận án........................................................................................132
7.3 Hƣớng phát triển.............................................................................................133
CÁC TÀI LIỆU CÔNG BỐ CỦA TÁC GIẢ..............................................................134
1. Các công trình liên quan trực tiếp đến luận án....................................................134
2. Các công trình liên quan gián tiếp đến luận án. ..................................................135
TÀI LIỆU THAM KHẢO ...........................................................................................136
Phụ lục A. Chứng minh độ đo DMP_C(Q’, C’) thỏa các tính chất của một không gian
metric .....................................................................................................148
CHƢƠNG 1. GIỚI THIỆU
Trong chƣơng này, chúng tui sẽ trình bày tổng quan về chuỗi thời gian và các bài
toán quan trọng trong khai phá dữ liệu chuỗi thời gian. Tiếp theo là mục tiêu, đối
tƣợng, phạm vi nghiên cứu của luận án và tóm tắt kết quả nghiên cứu đạt đƣợc. Cuối
cùng là cấu trúc của luận án này.
1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan.
Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu đƣợc đo theo
từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất. Hình 1.1 minh
họa một ví dụ về chuỗi thời gian biểu diễn tỉ giá chuyển đổi trung bình hàng tháng
giữa đô la Úc và đô la Mỹ (đơn vị đô la Úc) từ 7/1969 đến 8/1995.
Hình 1.1 Đường biểu diễn một chuỗi thời gian ( [1]).
Một chuỗi thời gian dạng luồng (streaming time series) C là một chuỗi thời gian
trong đó các giá trị mới tới một cách liên tục và đƣợc nối vào cuối chuỗi C theo thứ tự
thời gian. Vì một chuỗi thời gian dạng luồng bao gồm một số lớn các giá trị, sự tƣơng
tự giữa hai chuỗi thƣờng đƣợc tính dựa trên W giá trị cuối cùng (W là chiều dài cửa sổ
trƣợt). Cho nên, nếu W = 1024 thì mỗi chuỗi đƣợc coi nhƣ một điểm trong không gian
1024 chiều.
Các bài toán thƣờng đƣợc nghiên cứu trong khai phá dữ liệu chuỗi thời gian gồm
tìm kiếm tương tự (similarity search), gom cụm (clustering), phân lớp (classification),
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links