ĐẠI HỌC QUỐC GIA TP HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA TĂNG THỊ THÚY DUYÊN KHAI PHÁ LUẬT TRÊN CHUỖI THỜI GIAN DỰA TRÊN TỈ SỐ THAY ĐỔI VÀ GIẢI THUẬT FP-GROWTH Chuyên ngành : Khoa học máy tính Mã số: 604801 LUẬN VĂN THẠC SĨ TP HỒ CHÍ MINH, tháng 06 năm 2012 CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM Cán hướng dẫn khoa học : TS Võ Thị Ngọc Châu Cán chấm nhận xét : Cán chấm nhận xét : Luận văn thạc sĩ bảo vệ Trường Đại học Bách Khoa, ĐHQG Tp HCM ngày 18 tháng 07 năm 2012 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: PGS TS Dương Tuấn Anh (CT) PGS TS Lê Hoài Bắc (PB1) TS Lê Thanh Vân (PB2) TS Võ Thị Ngọc Châu (UV) TS Bùi Hoài Thắng (TK) Xác nhận Chủ tịch Hội đồng đánh giá LV Trưởng Khoa quản lý chuyên ngành sau luận văn 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 HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự - Hạnh phúc - NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Tăng Thị Thúy Duyên MSSV : 09070430 Ngày, tháng, năm sinh : 10/07/1983 Nơi sinh : thành phố Hồ Chí Minh Chuyên ngành : Khoa học máy tính Mã số : 604801 I TÊN ĐỀ TÀI: Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth II NHIỆM VỤ VÀ NỘI DUNG: a Tìm hiểu lí thuyết liệu chuỗi thời gian; lĩnh vực khai phá liệu chuỗi thời gian: độ đo tương tự, so trùng chuỗi con, phát motif, toán khai phá luật chuỗi thời gian; giải thuật khai phá tập phổ biến khai phá luật; đại số thời gian Allen b Tìm hiểu cơng trình liên quan cho sở lý thuyết đề tài cho sở khoa học việc đánh giá kết đạt luận văn c Chuẩn bị liệu thực nghiệm, thực tiền xử lý để có liệu chuỗi thời gian dùng tỉ số thay đổi d Định nghĩa mơ hình luật kết hợp liệu chuỗi thời gian e Phát triển giải thuật khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth có cải tiến f Đánh giá giải thuật đề xuất dựa việc phân tích giải thuật kết thực nghiệm thu III NGÀY GIAO NHIỆM VỤ : 06/02/2012 IV NGÀY HOÀN THÀNH NHIỆM VỤ: 30/06/2012 V CÁN BỘ HƯỚNG DẪN: TS Võ Thị Ngọc Châu Tp HCM, ngày 30 tháng 06 năm 2012 CÁN BỘ HƯỚNG DẪN (Họ tên chữ ký) CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên chữ ký) Võ Thị Ngọc Châu TRƯỞNG KHOA….……… (Họ tên chữ ký) LỜI CẢM ƠN Tôi xin gửi lời cám ơn chân thành sâu sắc đến TS Võ Thị Ngọc Châu, người tận tình hướng dẫn tạo điều kiện để tơi hồn thành luận văn Xin chân thành cám ơn đến quý Thầy Cô khoa Khoa học máy tính tận tình truyền đạt kiến thức cho tơi suốt q trình học Tơi xin chân thành cảm ơn đến gia đình, người thân, bạn bè động viên tạo điều kiện thuận lợi để tơi hồn thành luận văn TÓM TẮT LUẬN VĂN THẠC SĨ Dữ liệu chuỗi thời gian xuất cách tự nhiên hầu hết lĩnh vực tự nhiên, xã hội, kinh tế, tài chính, … Lượng liệu chuỗi thời gian tích tụ ngày nhiều theo thời gian chứa nhiều thông tin tiềm ẩn, hữu ích cho nhà phân tích nghiên cứu lĩnh vực tương ứng Việc khai phá liệu chuỗi thời gian để khám phá luật biến đổi liệu chuỗi thời gian có ý nghĩa quan trọng lĩnh vực đầy thách thức với khó khăn thân loại liệu chuỗi thời gian toán khai phá luật liệu chuỗi thời gian Luận văn hướng đến giải thuật khai phá luật liệu chuỗi thời gian với mối quan tâm đặc biệt yếu tố hiệu thời gian trình khai phá luật dạng VTtVP (s, c); đó, VT VP mẫu thức thời gian xuất thường xuyên liệu chuỗi thời gian, t thời gian mối quan hệ thời gian Allen VT VP, s c giá trị độ đo hỗ trợ tin cậy luật Giải thuật đề xuất luận văn áp dụng liệu chuỗi thời gian qua trình biến đổi thành chuỗi tỉ số thay đổi theo thời gian Ngoài ra, giải pháp cải tiến linh hoạt giải thuật FP-Growth để khám phá mẫu thức luật dạng quan tâm đồng thời cải thiện hiệu suất trình khai phá luật cách nâng cao hiệu cho trình khai phá mẫu thường xuyên Cho phần đánh giá giải thuật đạt được, luận văn thực so sánh giải thuật đề xuất với giải thuật khai phá mẫu thức luật trực tiếp brute-force dựa phân tích giải thuật kết thực nghiệm thu Kết đánh giá cho thấy giải thuật đề xuất khám phá mẫu thức luật theo yêu cầu người sử dụng với ngưỡng tối thiểu độ hỗ trợ độ tin cậy đồng thời hiệu giải thuật brute-force ABSTRACT Time series data appear naturally in most of the fields of natural and social science, economics, and finance, etc Along the time, the amount of time series data keeps increasing and contains potential and useful hidden information that might be utilized by analysts and researchers in each corresponding field Rule mining on time series data to discover rules of changing behaviors is very significant in research and applications related to time series data Nevertheless, this research problem is full of challenges stemming from the nature of time series data and of time series rule mining itself In this thesis, we aim at a time series rule mining algorithm in special consideration on time efficiency of the mining process with rules in form of VTtVP (s, c), where VT and VP are frequent temporal patterns in time series data, t is a period of time in the Allen’s temporal relationship between VT and VP, s and c are the support and confidence of the rule, respectively Our proposed algorithm is applied on time series data which is transformed into a sequence of change ratios Moreover, we flexibly define an efficient algorithm of discovering frequent patterns and rules in time series data based on the well-known FP-growth algorithm The proposed algorithm is theoretically analyzed and compared to the brute-force algorithm in frequent patterns and rules from time series data through many experiments on real stock data The correctness and efficiency of the proposed work are positively confirmed with the evaluation results LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ kết tham khảo từ cơng trình khác ghi rõ luận văn, công việc trình bày luận văn tơi thực chưa có phần nội dung luận văn nộp để lấy cấp trường trường khác Ngày 30 tháng 06 năm 2012 Tăng Thị Thúy Duyên MỤC LỤC Chương 1: GIỚI THIỆU ĐỀ TÀI 10 1.1 Dữ liệu chuỗi thời gian 10 1.2 Khai phá luật liệu chuỗi thời gian 10 1.3 Mục tiêu đề tài 11 1.4 Phạm vi đề tài 11 1.5 Ý nghĩa đề tài 12 Chương 2: TỔNG QUAN VỀ CÁC CÔNG TRÌNH LIÊN QUAN 13 2.1 Tiền xử lý 13 2.2 Tìm kiếm tương tự 13 2.2.1 Độ đo tương tự 14 2.2.2 So trùng toàn so trùng chuỗi 16 2.3 Khai phá luật chuỗi thời gian 17 2.4 Khai phá mẫu 18 Chương 3: CƠ SỞ LÝ THUYẾT 20 3.1 Đại số thời gian Allen 20 3.1.1 Các quan hệ Allen 20 3.1.2 Các toán tử quan hệ 21 3.2 Cấu trúc liệu bảng băm 23 3.2.1 Hàm băm 24 3.2.2 Hàm nén 24 3.2.3 Đụng độ cách giải 24 3.3 Các dạng chuỗi 26 3.3.1 Chuỗi 26 3.3.2 So trùng 26 3.3.3 Motif 26 3.3.4 Discord 27 3.3.5 Mẫu thức khuynh hướng 27 3.4 Giải thuật khai phá mẫu thường xuyên 28 3.4.1 Giải thuật Apriori 28 3.4.2 Giải thuật FP-Growth 28 Chương 4: HƯỚNG TIẾP CẬN VÀ GIẢI QUYẾT VẤN ĐỀ 30 4.1 Đặt vấn đề 30 4.2 Hướng tiếp cận 30 4.3 Định nghĩa dạng luật 31 4.4 Giải vấn đề 31 4.4.1 Tiền xử lý liệu 31 4.4.2 Motif 32 4.4.3 Tìm tập thường xuyên 33 4.4.4 Khai phá luật 46 4.4.5 Độ phức tạp thuật tốn tìm tập thường xun 47 Chương 5: THỰC NGHIỆM 50 5.1 Tổng quan 50 5.2 Tiền xử lý 50 5.3 Lưu trữ liệu 51 5.4 Mô tả thực nghiệm 51 5.5 Kết thực nghiệm 52 5.5.1 Thực nghiệm 52 5.5.2 Thực nghiệm 58 5.5.3 Kết luật 66 5.6 Nhận xét 67 Chương 6: KẾT LUẬN 69 6.1 Tổng kết 69 6.2 Đóng góp đề tài 69 6.3 Hướng phát triển 69 TÀI LIỆU THAM KHẢO 71 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Chương 1: GIỚI THIỆU ĐỀ TÀI 1.1 Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian chuỗi giá trị hay kiện có cách lặp lại phép đo theo thời gian Các giá trị thường đo theo thời khoảng (mili giây, giây, phút, giờ, ngày, tuần, tháng, năm) Dữ liệu chuỗi thời gian phổ biến nhiều ứng dụng phân tích thị trường chứng khốn, phân tích ngân sách, tượng tự nhiên (nhiệt độ, gió, khí hậu, động đất, ), chữa bệnh,… Dữ liệu chuỗi thời gian thường có kích thước lớn, lên đến nhiều gigabyte vịng ngày (như liệu chứng khốn), chí vịng phút (dữ liệu từ khơng gian NASA) Như vậy, cách tìm mối liên hệ liệu chuỗi thời gian, cách phân tích lượng liệu lớn để tìm mẫu tương tự hay thường xuyên, xu hướng, bất thường cách hiệu quả? Điều trở thành vấn đề quan trọng đầy thử thách cho nhà phân tích liệu Hình 1.1: Biểu diễn loại liệu chuỗi thời gian [37] 1.2 Khai phá luật liệu chuỗi thời gian Dữ liệu chuỗi thời gian xuất cách tự nhiên hầu hết lĩnh vực tự nhiên, xã hội nhiều ngành khác Khối liệu chứa nhiều thơng tin hữu ích cho nhà nghiên cứu lĩnh vực tương ứng Trong nghiên cứu khí tượng, liệu chuỗi thời gian khai thác để dự báo khí hậu Trong kinh tế, nhà kinh tế muốn xác định xu hướng thay đổi thu nhập gia đình theo thời gian; nhà đầu tư muốn dự đoán giá loại cổ phiếu thay đổi theo thời gian… Từ ta thấy việc phân tích liệu chuỗi thời gian để khám phá luật biến đổi liệu chuỗi thời gian có ý nghĩa quan trọng nhiều lĩnh vực đời sống Khai phá luật liệu chuỗi thời gian công việc quan trọng khai phá liệu chuỗi thời gian đầu thường nhắm vào người, cung cấp cho người dùng nhìn sâu sắc liệu 10 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Bảng 5.10: Kết thực nghiệm thuật toán FP-Growth với min_sup = 0.1 chuỗi ACB chiều dài chuỗi thay đổi FP-Growth cải tiến 500 450 400 350 300 FP-Growth cải tiến 250 200 150 100 50 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 Hình 5.10: đồ thị biến đổi thời gian chạy (ms) giải thuật FP-Growth cải tiến cố định giá trị min_sup = 0.1 tăng dần chiều dài chuỗi thời gian c So sánh hai giải thuật Kết thực nghiệm chuỗi ACB cho thấy giải thuật mà luận văn đề xuất tìm tập thường xuyên đầy đủ với kết chạy giải thuật bruteforce Bảng sau minh họa kích thước tập thường xuyên sau chạy hai giải thuật qua bước thực nghiệm 60 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Bảng 5.11: Số lượng phần tử tập thường xuyên khai phá chạy giải thuật brute-force FP-Growth cải tiến chuỗi chứng khốn ACB Hình sau so sánh tốc độ hai giải thuật thực nghiệm thu 3000000 2500000 2000000 1500000 bruteforce 1000000 FPGrowth cải tiến 500000 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 Hình 5.11: Kết thực nghiệm giải thuật brute-force FP-Growth cải tiến chuỗi chứng khoán ACB cố định min_sup = 0.1 thay đổi chiều dài chuỗi Từ kết thực nghiệm ta thấy thời gian chạy hai giải thuật tăng chiều dài chuỗi thời gian tăng Tuy nhiên, tốc độ tăng giải thuật brute-force tăng nhanh so với tốc độ tăng giải thuật FP-Growth cải tiến Bảng so sánh tỉ lệ thời gian chạy thuật toán brute-force thuật toán FP-Growth cải tiến sau: 61 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Bảng 5.12: Tỉ lệ thời gian chạy giải thuật brute-force giải thuật FP-Growth cải tiến tương ứng với độ dài chuỗi khác chuỗi liệu ACB STB Chạy giải thuật brute-force giải thuật FP-Growth cải tiến liệu chứng khoán STB với chiều dài thay đổi từ 100 đến 2000, độ hỗ trợ tối thiểu min_sup = 0.1, bước ứng với độ dài chuỗi chạy 10 lần để đo thời gian chạy (ms) lấy giá trị trung bình làm thời gian chạy cho bước Ta thu kết sau: a Giải thuật brute-force Bảng 5.13: Kết thực nghiệm thuật toán brute-force với min_sup = 0.1 chuỗi STB chiều dài chuỗi thay đổi 62 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth brute-force 1600000 1400000 1200000 1000000 800000 bruteforce 600000 400000 200000 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 Hình 5.12: đồ thị biến đổi thời gian chạy (ms) giải thuật brute-force cố định giá trị min_sup = 0.1 tăng dần chiều dài chuỗi thời gian b Giải thuật FP-Growth Bảng 5.14: Kết thực nghiệm thuật toán FP-Growth cải tiến với min_sup = 0.1 chuỗi STB chiều dài chuỗi thay đổi 63 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth FP-Growth cải tiến 300 250 200 150 FP-Growth cải tiến 100 50 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 Hình 5.13: đồ thị biến đổi thời gian chạy (ms) giải thuật FP-Growth cải tiến cố định giá trị min_sup = 0.1 tăng dần chiều dài chuỗi thời gian c So sánh hai giải thuật Kết thực nghiệm chuỗi STB cho thấy giải thuật mà luận văn đề xuất tìm tập thường xuyên đầy đủ với kết chạy giải thuật bruteforce Bảng sau minh họa kích thước tập thường xuyên sau chạy hai giải thuật qua bước thực nghiệm Bảng 5.15: Số lượng phần tử tập thường xuyên khai phá chạy giải thuật brute-force FP-Growth cải tiến chuỗi chứng khốn STB Hình sau so sánh tốc độ hai giải thuật thực nghiệm thu 64 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth 1600000 1400000 1200000 1000000 bruteforce 800000 600000 FPGrowth cải tiến 400000 200000 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 Hình 5.14: Kết thực nghiệm giải thuật brute-force FP-Growth cải tiến chuỗi chứng khoán STB cố định min_sup = 0.1 thay đổi chiều dài chuỗi Từ kết thực nghiệm ta thấy nhìn chung thời gian chạy hai giải thuật tăng chiều dài chuỗi thời gian tăng Tuy nhiên, điểm với chiều dài chuỗi 900 thời gian chạy hai giải thuật giảm so với điểm với chiều dài chuỗi 800, điều xảy đặc điểm liệu điểm 900 tạo nhiều kết hợp mẫu thức với nhau, điều hoàn toàn phù hợp với độ phức tạp thuật toán phụ thuộc vào số motif khai phá số lần tạo kết hợp mẫu thức phân tích 4.4.5 Tốc độ tăng giải thuật brute-force tăng nhanh so với tốc độ tăng giải thuật FP-Growth cải tiến Bảng so sánh tỉ lệ thời gian chạy thuật toán brute-force thuật toán FP-Growth cải tiến sau: Bảng 5.16: Tỉ lệ thời gian chạy giải thuật brute-force giải thuật FP-Growth cải tiến tương ứng với độ dài chuỗi khác chuỗi liệu STB Kết so sánh giống với kết so sánh phần Thực nghiệm liệu ACB 65 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth 5.5.3 Kết luật Phần minh họa kết luật khai phá từ trình thực nghiệm Giả sử ta chọn Thực nghiệm chuỗi chứng khoán ACB với min_sup = 0.08 min_conf = 0.1, ta thu kết sau: Tập thường xuyên Tập thường xuyên từ thực nghiệm khai phá là: Bảng 5.17: Tập thường xuyên khai phá chuỗi chứng khoán ACB với min_sup = 0.08 Tập luật Tập luật khai phá từ thực nghiệm liệt kê bảng sau, ứng với luật sinh có độ tương quan lift, độ hỗ trợ sup độ tin cậy conf tương ứng 66 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Bảng 5.18: Tập luật khai phá chuỗi chứng khoán ACB với min_sup = 0.08 min_conf = 0.1 Ý nghĩa luật Tập luật thu Bảng 5.18 có ý nghĩa sau: giả sử ta xét luật thứ TG →525 TG [{lift = 100.42}{sup=0.1}{conf=0.16}] có nghĩa chuỗi thời gian chứng khốn ACB có kiện tăng (T) sau giảm (G) sau 525 đơn vị thời gian lại xảy kiện tăng (T) giảm (G) với độ hỗ trợ sup=0.1, độ tin cậy conf=0.16 độ tương quan lift=100.42 tương quan thuận, có nghĩa vế trái (VT) xuất nhiều vế phải (VP) xuất nhiều ngược lại Xét luật thứ 14 TTGTG →630 TG [{lift = 63.6}{sup=0.1}{conf=0.1}] có nghĩa có kiện tăng (T) tăng (T) giảm (G) sau 577 đơn vị thời gian lại tăng (T) giảm (G) sau 630 đơn vị thời gian xuất kiện tăng (T) giảm (G) với độ hỗ trợ sup=0.1, độ tin cậy conf=0.1 độ tương quan lift=63.6 tương quan thuận 5.6 Nhận xét Kết chứng minh thực nghiệm tính hiệu giải thuật cải tiến phân tích phần 4.4.5 Kết thực nghiệm cho thấy thuật giải FP-Growth cải tiến có thời gian chạy nhanh thuật tốn brute-force Khi lượng liệu lớn thời gian tìm mẫu thường xuyên sử dụng thuật giải brute-force tăng nhanh so với thuật giải FP-Growth cải tiến 67 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth mà luận văn đề xuất, bước thuật giải brute-force ta phải duyệt qua tập mẫu sau tạo kết hợp để thống kê số lần xuất mẫu Ở giải thuật FP-Growth cải tiến mà luận văn đề xuất, trình thực đồng thời tạo kết hợp thời gian duyệt lại tập liệu nên tiết kiệm nhiều chi phí cho trình Hơn nữa, kết thực nghiệm thu giúp thấy rõ vấn đề đánh đổi không gian lưu trữ thời gian thực thi việc thiết kế giải thuật Cụ thể giải thuật FP-growth cải tiến kết hợp với trình xây dựng FP cải tiến đó, tốn nhiều nhớ so với giải thuật brute-force nên phần hiệu suất giải thuật FPgrowth cải tiến cải thiện nhiều so với giải thuật brute-force 68 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Chương 6: KẾT LUẬN Chương trình bày tổng kết việc mà luận làm được, đóng góp luận văn hướng mở rộng cho luận văn sau 6.1 Tổng kết Luận văn thực tồn q trình khai phá luật từ định nghĩa dạng luật cần khai phá, định nghĩa độ hỗ trợ (support) độ tin cậy (confidence) luật, thu thập xử lý liệu, chuyển liệu ban đầu sang dạng ký tự, áp dụng phương pháp có sẵn để tìm mẫu thức thường xuyên (motif), tạo kết hợp mẫu thức để tìm tập thường xuyên suy luật Luận văn cải tiến thành công giải thuật FP-Growth để áp dụng vào q trình tìm mẫu thường xuyên sử dụng trình khai phá luật Hiện thực giải thuật khai phá trực tiếp (brute-force) để so sánh kết với giải thuật đề xuất tốc độ tính đắn giải thuật 6.2 Đóng góp đề tài Đề xuất phương pháp kết hợp mẫu thức (motif) sử dụng quan hệ thời gian Phương pháp giúp tìm luật xảy theo dạng chuỗi xảy theo thời gian Đề xuất cách tính độ hỗ trợ phù hợp với kết hợp mẫu thức Định nghĩa dạng luật có kèm theo kết hợp yếu tố thời gian, có ý nghĩa cho người dùng Các mẫu thường xuyên khai phá thể mối quan hệ chuỗi kiện, kiện xảy theo khoảng thời gian cụ thể Các mẫu có ý nghĩa so với mẫu trình bày phần 2.6 mẫu thể quan hệ trước sau kiện không quan tâm tới yếu tố thời gian xảy trước sau kiện Do luật khai phá từ mẫu thường xuyên mà luận văn thực tìm luật có ý nghĩa cho người dùng Cải tiến thành cơng giải thuật FP-Growth để sử dụng vào trình khai phá luật liệu chuỗi thời gian Nâng cao hiệu trình khai phá tập thường xun, góp phần nâng cao tốc độ trình khai phá luật 6.3 Hướng phát triển Luận văn dựa tính tăng, giảm ổn định chuỗi thời gian để biến đổi chuỗi thời gian sang dạng ký tự, nhiên cách chưa thể đặc trưng riêng q trình biến đổi liệu Do đó, phương pháp chuyển đổi thích hợp cần nghiên cứu thêm để diễn tả mức độ thay độ như: giá cổ phiếu tăng, ta xem xét giá tăng hay tăng vừa hay tăng cao Ứng với ngưỡng, ký tự khác cần chuyển đổi để thể mức độ biến đổi liệu 69 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth Quá trình khai phá luật thực từ giai đoạn tìm kiếm motif, tạo kết hợp tìm tập thường xuyên, duyệt toàn tập thường xuyên để suy luật Q trình trình duyệt tồn tập thường xun để suy luật nhiều thời gian số lượng phần tử tập thường xuyên tìm lớn, cần nghiên cứu phương pháp thích hợp để đánh mục tập thường xuyên để sử dụng cho lần khai phá sau đồng thời thu ngắn trình tìm luật thỏa mãn yêu cầu người sử dụng Tuy giải thuật FP-growth cải tiến thu ngắn thời gian khai phá tập thường xuyên trình xây dựng FP cải tiến sử dụng nhiều tài nguyên nhớ Do đó, phương pháp cần nghiên cứu để giảm bớt không gian nhớ sử dụng cho FP cải tiến việc lưu xuống đĩa, việc tối ưu hóa thơng tin lưu trữ cây, … 70 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth TÀI LIỆU THAM KHẢO [1] AYRES, J., FLANNICK, J.,GEHRKE, J., AND YIU, T 2002 Sequential pattern mining using a bitmap representation In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 429–435 [2] A Hyvarinen Survey on independent component analysis Neural Computing Surveys, 2:9-128,1999 [3] Agrawal, R.,Imielinski,T.,Swami,A.Mining association rules between sets of items in large databases In: Proceedings of the ACM SIGMOD Conferenceon Management of Data, pp.207–216,1993 [4] Berndt, D and Clifford J 1994, Using dynamic time warping to find patterns in time series In Proceedings of AAAI Workshop on Knowledge Discovery in Databases, KDD-94, Seattle, Washington, USA, pp 359-370 [5] AGRAWAL, R AND SRIKANT, R 1995 Mining sequential patterns In Proceedings of the 11th Conference on Data Engineering (ICDE’95), 3–14 [6] ANTUNES, C AND OLIVEIRA, A L 2004 Sequential pattern mining algorithms: Trade-offs between speed and memory In Proceedings of the Workshop on Mining Graphs, Trees and Sequences (MGTSECML/PKDD ’04) [7] CHIU, D.-Y., WU, Y.-H., AND CHEN, A L P 2004 An efficient algorithm for mining frequent sequences by a new strategy without support counting In Proceedings of the 20th International Conference on Data Engineering 375–386 [8] DUNHAM, M H 2003 Data Mining: Introductory and Advanced Topics Prentice Hall, Englewood Cliffs,NJ [9] Das, G., Lin,K.I., Mannila,H., Renganathan,G., Smyth,P., 1998 Rule discovery from time series In: Proceedings of the Fourth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.16–22 [10] EL-SAYED, M., RUIZ, C., AND RUNDENSTEINER, E A 2004 FS-Miner: Efficient and incremental mining of frequent sequence patterns in web logs In Proceedings of the 6th Annual ACM International Workshop on Web Information and Data Management ACM, New York, 128–135 [11] HUANG, J.-W., TSENG, C.-Y., OU, J.-C., AND CHEN, M.-S 2006 On progressive sequential pattern mining In Proceedings of the 15th ACM International Conference on Information and Knowledge Management ACM, New York, 850–851 [12] TANASA, D 2005 Web usage mining: contributions to intersites logs preprocessing and sequential pattern extraction with low support Ph.D dissertation, Universit´e De Nice Sophia-Antipolis 71 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth [13] F Hoppner, F Klawonn,.Finding informative rules in interval sequences In: Proceedings of the Fourth International Symposium on Intelligent Data Analysis, pp.123– 132, 2001 [14] PEI, J.,HAN, J.,MORTAZAVI-ASL, B., AND PINTO, H 2001 PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth In Proceedings of the International Conference on Data Engineering 215–224 [15] Tanaka, Y & Uehara, K Discover Motifs in Multi Dimensional Time-Series Using the Principal Component Analysis and the MDL Principle In proceedings of the 3rd International Conference on Machine Learning and Data Mining in Pattern Recognition, pp.252-265, 2003 [16] PEI, J.,HAN, J.,MORTAZAVI-ASL, B., AND ZHU, H 2000 Mining access patterns efficiently from web logs In Knowledge Discovery and Data Mining Current Issues and New Applications Lecture Notes Computer Science, vol 1805, Springer, Berlin, 396–407 [17] MASSEGLIA, F., PONCELET, O., AND CICCHETTI, R 1999 An efficient algorithm for web usage mining Network Inform Syst J 2, 571–603 [18] J F Allen: Maintaining knowledge about temporal intervals In: Communications of the ACM 26 November 1983 ACM Press pp 832–843, ISSN 0001-0782 [19] J Ting, T Fu, F Chung Mining of Stock Data: Intra- and Inter-Stock Pattern Associative Classification InProceedings of 2006 International Conference on Data Mining, Las Vegas, USA, 30-36, 2006 [20] J Han, M Kamber, “Data Mining: Concepts and Techniques”, Morgan Kaufmann, San Francisco, 2006 [21] NIZAR R MABROUKEH and C I EZEIFE, "A Taxonomy of Sequential Pattern Mining Algorithms", ACM Computing Surveys, Vol 43, No 1, Article 3, Publication date: November 2010 [22] L Sacchi, C Larizza, C Combi, R Bellazzi, “Data mining with temporal abstractions: learning rules from time series”, Data mining and Knowledge Discovery journal, pages 217247, 2007 [23] M Last, Y Klein, A Kandel Knowledge discovery in time series databases IEEE Transactions on Systems, Man, and Cybernetics—Part B:Cybernetics 31 (1), 160–169, 2001 [24] M.L Hetland and P Sætrom, "Evolutionary Rule Mining in Time Series Databases", presented at Machine Learning, 2005, pp.107-125 [25] P Cotofrei and K Stoffel, "Classification Rules + Time = Temporal Rules", in Proc International Conference on Computational Science (1), 2002, pp.572-581 72 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth [26] Rakesh Agrawal, Christos Faloutsos, anf Arun swami Efficient similarity search in sequence database In Procs of the Fourth International Conference on Foundations of Data Organization anf Algorithms, 1993 [27] S W Smith The Scientist and Engineer's Guide to Digital Signal Processing California Technical Publishing, 1997 [28] T Fu, "A review on time series data mining", Eng Appl of AI, 2011, pp.164-181 [29] T.F Gharib, H Nassar, M Taha, and A Abraham, "An efficient algorithm for incremental mining of temporal association rules", Data Knowl Eng., 2010, pp.800-815 [30] W Leigh, N Modani, R Purvis, T Roberts.Stock market trading rule discovery using technical charting heuristics Expert Systems with Applicatioddns 23,155–159, 2002 [31] Y Ha, S Park, S Kim, J Won, J Yoon, “A stock recommendation system exploiting rule discovery in stock databases”, Information and Software Technology, Vol 51, pages 1140-1149, July 2009 [32] Y.W Huang, P.S Yu Adaptive query processing for time-series data.In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and DataMining, pp.282–286,1999 [33] YANG, Z AND KITSUREGAWA, M 2005 LAPIN-SPAM: An improved algorithm for mining sequential pattern In Proceedings of the 21st International Conference on Data Engineering Workshops 1222 [34] ZAKI, M J 1998 Efficient enumeration of frequent sequences In Proceedings of the 7th International Conference on Information and Knowledge Management 68–75 [35] Keogh E., 2006, A Tutorial on Indexing and Mining Time Series Data, In Proceedings of the 32th International Conference on Very Large Databases, VLDB2006, Seoul, Korea [36] P Patel, E Keogh, J Lin, S Lonardi, “Mining Motifs in Massive Time Series Databases”, Second IEEE International Conference on Data Mining (ICDM’02), ISBN: 07695-1754-4, December 2002 [37] Mörchen, F., Ultsch, A.: Mining Hierarchical Temporal Patterns in Multivariate Time Series, Susanne Biundo, Thom W Frühwirth, Günther Palm (Eds), In KI 2004: Advances in Artificial Intelligence, Proceedings 27th Annual German Conference in AI, Ulm, Germany, Springer, Heidelberg, 2004, pp 127-140 [38] http://www.cophieu68.com 73 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP-Growth LÝ LỊCH TRÍCH NGANG Họ tên: Tăng Thị Thúy Duyên Ngày, tháng, năm sinh: 10/07/1983 Nơi sinh: TP Hồ Chí Minh Địa liên lạc: 83E, khu phố 2, phường Thạnh Xuân, Q12, TP HCM QUÁ TRÌNH ĐÀO TẠO Thời gian 2002 - 2006 2009 - 2012 Tên trường ĐH Khoa học tự nhiên ĐH Bách khoa Chuyên ngành Tốn – Tin học Khoa học máy tính Trình độ đào tạo Cử nhân Thạc sĩ Q TRÌNH CƠNG TÁC Thời gian 2006 - Hiện Đơn vị công tác Cơng ty iNet Solutions Vị trí cơng tác Lập trình viên 74 ... có liệu chuỗi thời gian dùng tỉ số thay đổi d Định nghĩa mơ hình luật kết hợp liệu chuỗi thời gian e Phát triển giải thuật khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP- Growth. .. k-itemsets khám phá cần kiểm tra tập liệu k+1 lần - 3.4.2 Giải thuật FP- Growth Mô tả giải thuật 28 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật FP- Growth Giải thuật FP- Growth xây dựng... 4.11: thuật tốn FP- Growth cải tiến 4.4.3.2.4 So sánh giải thuật FP- Growth FP- Growth cải tiến So sánh giải thuật xây dựng FP FP cải tiến 45 Khai phá luật chuỗi thời gian dựa tỉ số thay đổi giải thuật