Chương I : Giới thiệu về ý tưởng dé tài, mục tiêu, phạm vi nghiên cứu và tóm tắt vé các kết quả đã đạt được của luận văn. Chương II : Trình bảy về các công trình nghiên cứu có liên quan. Các công trình nay trình bay những giải thuật gom cụm dữ liệu chuỗi thời gian, và những nghiên cứu dé ứng dụng các giải thuật gom cum ứng dung trong phân tích dữ liệu kinh doanh, tài chính và dữ liệu thị trường chứng khoán. Chương TIT : Giới thiệu một số cơ sở lý thuyết về dữ liệu chuỗi thời gian, các phương pháp tính trung bình trượt, độ tương tự, các phương pháp gom cụm, và đánh giá giải thuật gom cụm Chương IV : Trình bày cách thức tiếp cận chỉ mục bitmap trong kỹ thuật gom cụm và dự đoán xu hướng của dữ liệu chuỗi thời gian.
Dé xuất áp dụng các tiếp cận nay dé phân tích dữ liệu thị trường chứng khoán tại Việt Nam va dé xuất kỹ thuật gom cụm theo xu hướng biến động giá của chuỗi đữ liệu thời gian giá chứng khoán. Chương V : Trình bay một số kết quả thực nghiệm và danh giá. Chương VI : Trình bày các kết luận của nghiên cứu và hướng phát triển mở rộng của đê tài. CHƯƠNG 2: CÁC CÔNG TRÌNH CÓ LIÊN QUAN Chương 2 sẽ tóm lược các công trình nghiên cứu về các phương pháp tiếp cận dữ liệu chuỗi thời gian, các phương pháp gom cụm và các nghiên cứu ứng dụng gom cụm dé khai phá dữ liệu chuỗi thời gian trong lĩnh vực tài chính.1 Các hướng tiếp cận chính trong gom cum dữ liệu chuỗi thời gian Theo Liao (2005) [14].
đối với dữ liệu chuỗi thời gian, thường có 3 hướng tiếp cận chính là (1) dựa trên dtr liệu thô, (2) dựa trên đặc trưng. (3) dựa trên mô hình.1) Dữ liệu Dữ liệu chuôi thời gian chuôi thời gian Rut trích Rời rạc hóa | |Mô hình hóa đặc trưng (discretization) (modeling) (feature extraction) Dữ liệu Ấ: KL as: Ỷ các hệ số chuôi thời gian “£ tet _ ; hoặc phan dư rút trích [Mô hình hóa | (modeling) v ` Gom cụm Gom cụm Gom cụm (clustering) (clustering) (clustering) | | Các thông số Các cụm và có thé là của mô hình Các cụm ` £ F4 ` (1) các trọng tâm cụm 4 (3) | và có thê là các trọng tâm cụm Các cụm ` Fà Ä ` và có thê là (2) các trọng tâm cụm Hình 2.1 - Ba cách tiếp cận gom cụm dữ liệu chuối thời gian - (1) Dựa trên dữ liệu thô (Raw-data-based approaches) Dữ liệu chuỗi thời gian sẽ được sử dụng trực tiếp trong giải thuật gom cụm. Lúc này hai chuỗi dữ liệu thời gian được so sánh thường lay mẫu tại các khoảng thời gian như nhau, nhưng chiều dài (số thời điểm) có thé giống hoặc khác nhau. Hướng tiếp cận trên dit liệu thô chủ yếu cải tiến các độ đo trên dit liệu thường thành độ đo hữu hiệu cho đữ liệu chuỗi thời gian.
Có nhiều giải thuật gom cụm trên dữ liệu chuỗi thời gian thô nhưng chủ yếu chỉ áp dung cho các dữ liệu ít chiều, khôi lượng dữ liệu nhỏ. (2) Dựa trên rút trích đặc trưng (Feature-based approaches) Dữ liệu chuỗi thời gian sẽ qua giai đoạn r trich đặc trưng (feature axtraction) nhằm thu giảm số chiều trước khi đưa vào quá trình gom cụm nhăm loại bé những đặc trưng của chuỗi không cần thiết cho mục tiêu gom cụm, giảm kích thước chuỗi giúp quá trình gom cụm hiệu quả hơn. Có nhiều giải thuật được đề nghị áp dụng cho gom cụm dựa trên đặc trưng. tuy nhiên đa số các phương pháp rút trích đặc trưng thì có đặc điểm tự nhiên, các đặc trưng được rút trích thường phụ thuộc vào yêu cầu của ứng dụng (nghĩa là một tập đặc trưng làm việc tốt cho ứng dụng này có thể không thích hợp cho ứng dụng khác) - (3) Dựa trên mô hình (Model-based approaches) Dữ liệu sẽ đưa qua tiến trình nhận dạng và xác định các thông số mô hình trước khi thực hiện mô hình hóa.
Hướng tiếp cận dựa trên mô hình sẽ xem mỗi chuỗi thời gian dược tao ra bởi một số mô hình hay bởi sự pha trộn của phân bố xác suất cơ bản. Các chuỗi thời gian được xem là tương tự khi các mồ hình biểu thị đặc điểm cho mỗi chuỗi tương tự. Có nhiều cách tiếp cận gom cum dựa trên mô hình như ARIMA, ARMA, HISMOOTII, Markov Chain, ARMA mixture, Gaussian nixture,. trong đó các tiép cận dùng mô hình ARIMA là phé biến nhất.
Tổng hợp các giải thuật gom cụm và ứng dụng theo từng hướng tiếp cận xem thêm tại phụ lục A.2_ Gom cụm dựa trên hình dạng của chuỗi thời gian Xiaohang Zhang (2011) [16] đã dé xuất thuật toán dé gom cụm dựa trên hình dạng của chuỗi thời gian. Hướng tiếp cận này có thé làm giảm kích thước của dữ liệu. cải thiện hiệu quả và không làm giảm tác dụng bằng cách sử dụng các nguyên tắc mạng lưới phúc tap (principle of complex network). Theo nghiên cứu, dit liệu chuỗi thời gian có thé tương tự theo các dang: /ương fir theo thời gian (similarity in time) (hình 2.2) — ví dụ như gom cụm dữ liệu giá cố phiếu dé tìm ra sự quan hệ qua lại của chúng trong thay dỗi gid, (ương tu theo hình dang (similarity in shape) (hình 2.3) — ví dụ như gom cụm những cô phiếu thé hiện theo những mẫu tương tự nhau và tìm ra sự phụ thuộc hay độc lập giữa chúng trong bién đổi, và tương tự theo sự thay đổi (similarity in change) — ví dụ như gom cụm những cổ phiếu có xu hướng tăng giá trong ngày hôm sau.
(1) Một mạng lưới láng giềng gần nhất được xây dựng dựa trên sự giống nhau giữa bất kỳ cặp chuỗi thời gian nào. Trong bước này, tam giác khoảng cách được sử dụng để do lường sự giống nhau, mỗi nút dại diện cho một chuỗi thời gian và mỗi liên kết biểu thị mỗi quan hệ láng giềng gần nhất giữa các nút. (2) Các nút với số lượng láng giéng nhiều được chọn làm đối tượng có thé sử dụng để gom cụm. Irong quá trình gom cum, ham khoảng cách xoắn thời gian động (dynamic time warping distance function) và thudt toán gom cum phân cap (hierarchical clustering algorithm) được áp dụng với từng dối tượng dược lựa chọn.
vali se [vette 0 LO 20 30 10 50 60 70 0 10 20 30 t0 90 60 70 Hình 2.2 - Các cụm dữ liệu chuỗi thời gian là trơng tự theo thời gian 10 ¬ Cylinder 10 + Bell 10 + Funel 8+ 6 + Vj Mn 4. | › vy Lh 03 \ 7 T T T rer"?. 27 ANH FREE BAG AN SASHA 44 Hình 2.3 - Các cụm dữ liệu chuỗi thời gian là tương tw theo hình dang 2. Gom cụm dựa trên hướng tiếp cận bitmap Jong P.
Yoon, Yixin Luo và Junghyun Nam (2001) [8] đã nghiên cứu cach thức tiến hành chuyển đổi giá tri đữ liệu của chuỗi thời gian sang dạng nhị phân dé thực hiện gom cụm và dự doán xu hướng: Nghiên cứu thực hiện gom cụm và dự đoán xu hướng dựa trên các mẫu xu hướng tương tự được rút trích ra từ co sở dit liệu chuỗi thời gian, chứ không dựa trên các mau dữ liệu tương tự. - _ Giải quyết vẫn đề gom cụm, Yoon xem xét 4 cách thức so trùng là: (1) So tring Chính xác (exact match), (2) So trùng tương tir (similarity match), (3) So frùng 9 chính xác có tịnh tiễn (exact match by shift), (4) So ràng tương tự có tinh tiễn (similarity match by shift). Yoon sử dụng các khát niệm: (1) Dé /ương tie (sim) dé xác định các cặp dữ liệu chuỗi thời gian là tương tự nhau hay không : (2) Trung tâm (center): nhằm cải thiện hiệu suất của quá trình gom cụm ; (3) Bán kính (radius): dễ xác dịnh xem một dữ liệu chuỗi thời gian đã cho là thuộc về cụm đó. Ngoài ra, Yoon đề nghị một khái niệm mới là độ khác biệt (disim) để làm cho kết quả gom cụm chính xác hơn.
Các khái niệm này sẽ được trình bày cụ thể ở phần sau. - Gilải quyết vấn đề dự đoán, Yoon đề xuất một phương pháp mới để dự đoán xu hướng tiếp theo của chuỗi xu hướng, phương pháp này gồm 2 dạng: (1) Du đoán xu hướng trong cum (Intra-cluster Trend Prediction), và (2) Du đoán xu hướng liên cum (Inter-cluster Trend Prediction) Với nhận định, van dé tìm kiếm tương tự chuỗi thời gian (chuỗi con) là một trình tự nhất định dé có thé tìm thay tất cả các cặp chuỗi tương tự, Yoon đã khảo sát và dánh giá 3 phương pháp tiếp cận để tìm kiếm tương tự chuỗi thời gian bao gồm: - Phuong pháp tiếp cận trong miễn thời gian (Time-domain approach) : Cách tiếp cận này xử lý dữ liệu chuỗi thời gian trong miễn thời gian bằng các kỹ thuật như tinh tién (shifting), co giãn biên độ (scaling), làm tron (smoothing), xoắn trục thời gian (time warping),. Sử dung các kỹ thuật này, các mau tương tự có thé được rút trích hoặc gom cụm. Phương pháp này phức tạp và kết quả có hiệu suất thấp vì tập trung vào tat cả các điểm dữ liệu don.
LẠ A - Phương pháp tiếp cận trong miền tan số (Frequency-domain approach): Phương pháp này sử dụng phép biến đôi fourier rời rac (Discrete Fourier Tranform — DFT) dé ánh xạ trật tự thời gian trên miễn tần số, lay ra tan s6 dau tiên, sau dó mô tả giá tri các tần số theo thứ tự trên một cấu trúc cây R* (R*- tree). Đặt trên chuỗi dữ liệu một cửa số trượt co giãn biên độ tỉ lệ với độ lớn của chuỗi, và xác định độ nhiễu trong chuỗi. Chỉ có một vài tần số được xem xét dé khai phá dữ liệu. Các tần số này ít bị điều khiến bởi người dùng, do đó nó không thích hợp cho việc tìm kiếm các mẫu giống nhau bang các truy van của người sử dụng hoặc gom cụm chuỗi dữ liệu chuỗi thời gian.
- Phương pháp tiếp cận định tính (Qualitative approach): Để giải quyết những hạn chê đã nêu trong hai cách tiếp cận trên, đây cũng là một cách tiép cận trong I0 miền thời gian, nhưng phương pháp sẽ tập trung vào các điểm dữ liệu có ý nghĩa thay vi xem xét tat cả các điểm dữ liệu. Với những cơ sở như trên, Yoon đã chọn sử dụng phương pháp tiếp cận định tính này trong gom cụm chuỗi theo xu hướng và dự báo xu hướng tiếp theo. Bằng cách sử dụng phương pháp nay, Yoon dé xuất khái niệm xu #ướng (trend) của các chuỗi dữ liệu chuỗi thời gian. Xuhướng của chuỗi dữ liệu chuỗi thời gian: mô tả mức độ cao hơn về hướng di chuyên của chuỗi dữ liệu chuỗi thời gian ban dau.