Luận án Tiến sĩ Khoa học máy tính: Khai phá 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

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA<br /> <br /> NGUYỄN THÀNH SƠN<br /> <br /> KHAI PHÁ 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)<br /> <br /> LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH<br /> <br /> i<br /> <br /> TP. HỒ CHÍ MINH, NĂM 2014<br /> <br /> ii<br /> <br /> Công trình được hoàn thành tại khoa Khoa học và Kỹ thuật Máy tính trường Đại học Bách khoa, ĐHQG TP. HCM.<br /> <br /> Người hướng dẫn khoa học: PGS. TS Dương Tuấn Anh<br /> <br /> Phản biện 1: PGS. TS. Nguyễn Thị Kim Anh Phản biện 2: PGS. TS. Đỗ Phúc Phản biện 3: PGS. TS. Quản Thành Thơ<br /> <br /> Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp trường họp tại .......................................................................... ................................................................................................. Vào hồi giờ ngày tháng năm 2014.<br /> <br /> Có thể tìm hiểu luận án tại thư viện trường Đại học Bách khoa, ĐHQG TP. HCM<br /> <br /> iii<br /> <br /> MỤC LỤC 1. Giới thiệu. ............................................................................1 1.1. Tổng quan về đề tài......................................................1 1.2. Động cơ, mục tiêu, đối tượng và phạm vi nghiên cứu. 1 1.3. Nhiệm vụ và hướng tiếp cận của luận án. ....................2 2. Cơ sở lý thuyết và các công trình liên quan. .......................2 2.1. Các độ đo tương tự. .....................................................2 2.2. Thu giảm số chiều chuỗi thời gian...............................2 2.3. Rời rạc hóa chuỗi thời gian. .........................................3 2.4. Cấu trúc chỉ mục. .........................................................3 2.5. Tìm kiếm tương tự trên chuỗi thời gian. ......................3 2.6. Tìm kiếm tương tự trên chuỗi thời gian dạng luồng. ...4 2.7. Phát hiện motif trên chuỗi thời gian. ...........................4 2.8. Gom cụm dữ liệu chuỗi thời gian. ...............................4 3. Thu giảm số chiều chuỗi thời gian bằng phương pháp MP_C. .................................................................................5 3.1. Phương pháp MP_C (Middle Points_Clipping). .........5 3.2. Độ đo tương tự trong không gian MP_C. ....................6 3.3. Vùng bao MP_C (MP_C_BR). ....................................7 3.4. Hàm tính khoảng cách giữa chuỗi truy vấn Q và MP_C_BR. ..................................................................8 3.5. Cấu trúc chỉ mục đường chân trời cho phương pháp biểu diễn MP_C. ..........................................................8 3.6. Tìm kiếm tương tự trên chuỗi thời gian dạng luồng dựa vào MP_C và chỉ mục đường chân trời. ...............8 3.7. Kết quả thực nghiệm. .................................................10 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..........................................................12 4.1. Phát hiện motif dựa vào cấu trúc chỉ mục đa chiều và ý tưởng từ bỏ sớm. ........................................................12 iv<br /> <br /> 4.2. Phát hiện motif xấp xỉ dự trên phương pháp MP_C với sự hỗ trợ của chỉ mục đường chân trời. ..................... 14 4.3. Kết quả thực nghiệm. ................................................ 15 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. ..................................... 16 5.1. Biểu diễn chuỗi thời gian ở nhiều mức xấp xỉ theo phương pháp MP_C .................................................. 16 5.2. Dùng kd-tree tạo trung tâm các cụm cho thuật toán Ik-Means. .................................................................... 17 5.3. Dùng cây đặc trưng cụm để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means.......................... 18 5.4. Thực nghiệm về bài toán gom cụm ........................... 19 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. ...................................... 20 7. Kết luận và hướng phát triển. ............................................ 23 7.1. Các đóng góp chính của luận án. ............................... 23 7.2. Hạn chế của luận án................................................... 23 7.3. Hướng phát triển........................................................ 24 CÁC TÀI LIỆU CÔNG BỐ CỦA TÁC GIẢ ........................ 25<br /> <br /> v<br /> <br />