Luận án tiến sĩ: Phát hiện luật kết hợp và luật chuỗi mờ trong cơ sở dữ liệu định lượng có yếu tố thời gian - Trương Đức Phương

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- TRƢƠNG ĐỨC PHƢƠNG PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT CHUỖI MỜ TRONG CƠ SỞ DỮ LIỆU ĐỊNH LƢỢNG CÓ YẾU TỐ THỜI GIAN LUẬN ÁN TIẾN SĨ MÁY TÍNH HÀ NỘI – 2021 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ …….***………… TRƢƠNG ĐỨC PHƢƠNG PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT CHUỖI MỜ TRONG CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG CÓ YẾU TỐ THỜI GIAN LUẬN ÁN TIẾN SĨ MÁY TÍNH Chuyên ngành : Hệ thống thông tin Mã số: 9 48 01 04 Ngƣời hƣớng dẫn khoa học: 1. Nguyễn Đức Dũng Hà Nội – 2021 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong các công trình nào khác.

Luận án được hoàn thành trong thời gian tôi làm Nghiên cứu sinh tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Tác giả luận án NCS. Trƣơng Đức Phƣơng ii LỜI CẢM ƠN Luận án Tiến sỹ “Phát hiện luật kết hợp và luật chuỗi mờ trong cơ sở dữ liệu định lượng có yếu tố thời gian” được thực hiện dưới sự hướng dẫn khoa học của PGS. Đỗ Văn Thành và PGS.

Nguyễn Đức Dũng. Trước tiên tôi xin được bày tỏ lòng biết ơn sâu sắc tới các thầy hướng dẫn PGS. Đỗ Văn Thành và PGS. Nguyễn Đức Dũng.

Trong quá trình thực hiện luận án, nghiên cứu sinh đã nhận được nhiều định hướng khoa học, những bài học quý báu, sự hướng dẫn nhiệt tình từ các thầy hướng dẫn. Các thầy cũng đã luôn tận tâm động viên, khuyến khích và chỉ dẫn giúp đỡ nghiên cứu sinh hoàn thành được bản luận án này. Tôi xin chân thành cảm ơn các thầy cô Học viện Khoa học và Công nghệ đã tạo điều kiện thuận lợi cho tôi trong suốt quá trình nghiên cứu và thực hiện luận án. Tôi xin cảm ơn Ban Giám hiệu, tập thể cán bộ, giảng viên khoa Khoa học Tự nhiên và Công nghệ, trường Đại học Thủ đô Hà Nội đã tạo điều kiện giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu.

Nhân dịp này, tôi cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và bạn bè đã cho tôi điểm tựa vững chắc, tạo động lực để tôi hoàn thành luận án này. Trương Đức Phương 1 MỤC LỤC DANH MỤC HÌNH VẼ. 4 DANH MỤC BẢNG BIỂU. 6 DANH MỤC CÁC TỪ VIẾT TẮT.

TỔNG QUAN VỀ LUẬT KẾT HỢP VÀ MẪU CHUỖI, LUẬT CHUỖI CHUNG. Luật kết hợp. Phát hiện luật kết hợp trong các CSDL giao dịch. Phát hiện luật kết hợp trong các CSDL định lượng.

Phát hiện luật kết hợp tính đến khoảng cách thời gian xảy ra của các giao dịch trong các CSDL có yếu tố thời gian. Phát hiện mẫu chuỗi trong các CSDL chuỗi giao dịch. Phát hiện mẫu chuỗi trong các CSDL chuỗi định lượng. Phát hiện mẫu chuỗi tính đến khoảng cách thời gian xảy ra của các giao dịch trong các CSDL chuỗi có yếu tố thời gian.

Luật chuỗi chung. Khái niệm luật chuỗi chung. Phát hiện luật chuỗi chung. 34 Kết luận Chương 1.

PHÁT HIỆN LUẬT KẾT HỢP CÓ TÍNH ĐẾN KHOẢNG CÁCH THỜI GIAN TRONG CÁC CSDL ĐỊNH LƯỢNG CÓ YẾU TỐ THỜI GIAN. Một số khái niệm cơ bản. Thuật toán phát hiện luật kết hợp mờ với khoảng cách thời gian mờ 52 2. Bài toán đặt ra.

Ý tưởng thuật toán. Thuật toán FTQ. Tính đúng đắn và tính đầy đủ của thuật toán. Độ phức tạp thuật toán.

Trường hợp suy biến của luật kết hợp mờ với khoảng cách thời gian mờ 62 2. Thử nghiệm thuật toán. Dữ liệu thử nghiệm. Kết quả thử nghiệm.

66 Kết luận Chương 2. PHÁT HIỆN MẪU CHUỖI CÓ TÍNH ĐẾN KHOẢNG CÁCH THỜI GIAN TRONG CÁC CSDL CHUỖI ĐỊNH LƯỢNG CÓ YẾU TỐ THỜI GIAN. Một số khái niệm cơ bản. Thuật toán phát hiện mẫu chuỗi mờ với khoảng cách thời gian mờ 84 3.

Bài toán đặt ra. Ý tưởng thuật toán. Thuật toán FSPFTIM. Tính đúng đắn và tính đầy đủ của thuật toán.

Độ phức tạp thuật toán. Trường hợp suy biến của mẫu chuỗi mờ với khoảng cách thời gian mờ 91 3. Minh họa thuật toán. Thử nghiệm thuật toán.

Dữ liệu thử nghiệm. Kết quả thử nghiệm. 95 Kết luận Chương 3. PHÁT HIỆN LUẬT CHUỖI CHUNG CÓ TÍNH ĐẾN KHOẢNG CÁCH THỜI GIAN TRONG CÁC CSDL CHUỖI ĐỊNH LƯỢNG CÓ YẾU TỐ THỜI GIAN.

Một số khái niệm cơ bản. Thuật toán phát hiện luật chuỗi chung mờ với khoảng cách thời gian mờ 108 4. Bài toán đặt ra. Thuật toán IFERMiner.

Tính đúng đắn và đầy đủ. Độ phức tạp của thuật toán IFERMiner. Trường hợp suy biến của luật chuỗi chung mờ với khoảng cách thời gian mờ. Thử nghiệm thuật toán.

Dữ liệu thử nghiệm. Kết quả thử nghiệm. 123 Kết luận Chương 4. 129 KẾT LUẬN VÀ KIẾN NGHỊ.

130 DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ. 132 TÀI LIỆU THAM KHẢO. 133 4 DANH MỤC HÌNH VẼ Hình 1. Các vấn đề liên quan đến nghiên cứu của luận án.

Các hàm thành viên của các tập mờ ứng với tỉ lệ tăng/giảm của các mã chứng khoán. Các hàm thành viên của các tập mờ của Tỉ lệ thay đổi chỉ số VN30. Các hàm thành viên của các tập mờ thời gian. Mối quan hệ giữa số lượng luật tìm được từ thuật toán FTQ và độ tin cậy cực tiểu min_conf trong các trường hợp khác nhau về độ hỗ trợ cực tiểu min_sup.

Mối quan hệ giữa số lượng luật tìm được và min_sup với min_conf khác nhau. Chi phí thời gian thực hiện khi min_conf=70%. So sánh số luật của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán FTQ 68 Hình 2. So sánh thời gian chạy của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán FTQ.

Các hàm thành viên của các tập mờ thuộc LT. Mối quan hệ giữa số lượng mẫu chuỗi mờ với khoảng cách thời gian mờ với min_sup (a) và giữa thời gian chạy của thuật toán với min_sup (b) trong trường hợp số phân hoạch thuộc tính định lượng khác nhau khi thực hiện trên tập dữ liệu S100I1000T3D341K. Mối quan hệ giữa số lượng mẫu chuỗi mờ với khoảng cách thời gian mờ với min_sup (a) và giữa thời gian chạy của thuật toán với min_sup (b) trong trường hợp số phân hoạch thuộc tính định lượng khác nhau khi thực hiện trên tập dữ liệu Online Retail_France. Mối quan hệ giữa số lượng mẫu chuỗi mờ với khoảng cách thời gian mờ với min_sup (a) và giữa thời gian chạy của thuật toán với min_sup (b) trong trường hợp số phân hoạch khoảng cách thời gian (Kt) khác nhau đối với tập dữ liệu S100I1000T3D341K.

Mối quan hệ giữa số lượng mẫu chuỗi mờ với khoảng cách thời gian mờ với min_sup (a) và giữa thời gian chạy của thuật toán với min_sup (b) trong trường hợp số phân hoạch khoảng cách thời gian (Kt) khác nhau đối với tập dữ liệu Online Retail_France. So sánh số mẫu chuỗi của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán FSPFTIM. So sánh thời gian chạy của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán FSPFTIM. Mối quan hệ giữa số lượng các luật FCSI valid với min_sup và min_conf.

Mối quan hệ giữa thời gian thực hiện thuật toán với min_sup và min_conf. So sánh số luật của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán IFERMiner. So sánh thời gian chạy của phương pháp mờ hóa (A) và phương pháp chia khoảng (B) đối với khoảng cách thời gian khi thực hiện thuật toán IFERMiner. 127 6 DANH MỤC BẢNG BIỂU Bảng 1.

Ví dụ về CSDL giao dịch. Ví dụ về CSDL định lượng. Ví dụ về CSDL giao dịch mua hàng có yếu tố thời gian. Một số nghiên cứu về phát hiện luật kết hợp có tính đến khoảng cách thời gian.

Ví dụ về CSDL chuỗi giao dịch. Ví dụ CSDL chuỗi định lượng. Ví dụ CSDL chuỗi giao dịch có yếu tố thời gian. Một số nghiên cứu về phát hiện mẫu chuỗi có tính đến khoảng cách thời gian.

Một số nghiên cứu về phát hiện luật chuỗi chung. Ví dụ về CSDL định lượng có yếu tố thời gian. CSDL mờ có yếu tố thời gian DF. Dữ liệu thử nghiệm ISTANBUL STOCK EXCHANGE.

Kết quả thử nghiệm thuật toán FTQ với min_sup=7% và min_con=70%. Ý nghĩa các luật thu được đối với CSDL VNINDEX. Ví dụ về CSDL chuỗi định lượng có yếu tố thời gian QSD. CSDL chuỗi mờ có yếu tố thời gian FSD.

Dữ liệu thử nghiệm S100I1000T3D341K và Online Retail_France. Các mẫu chuỗi mờ với khoảng cách thời gian mờ tìm được từ Online Retail_France. Dữ liệu thử nghiệm thuật toán IFERMiner. Các luật FCSI valid có độ hỗ trợ cao nhất tương ứng với min_sup = 3% và min_conf = 75%.

128 8 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Nội dung NCS Nghiên cứu sinh CSDL Cơ sở dữ liệu FITARM Fuzzy Inter-Transaction Asociation Rules Mining FTITS Fuzzy Time-Interval in Time Series FTQ Fuzzy Time-interval in temporal Quantitative database algorithm FSPFTIM Fuzzy Sequential Patterns with Fuzzy Time-Intervals Mining FGBSPMA Fuzzy Grids Based Sequential Patterns Mining Algorithm FQSP-MMS Fuzzy Quantitative Sequential Pattern with Multiple Minimum Supports GSP Generalized Sequential Pattern IQSP Incremental mining of Quantitative Sequential Pattern FSPFTI Fuzzy Sequential Patterns with Fixed Time-Intervals BFS Breadth First Search DFS Depth First Search FCSI Fuzzy Common Sequence with time – Interval TAS Temporally-Annotated Sequences 9 MỞ ĐẦU 1. Tính cấp thiết của luận án và động lực nghiên cứu Phát hiện luật kết hợp và mẫu chuỗi, luật chuỗi nằm trong số những vấn đề quan trọng trong lĩnh vực khai phá dữ liệu. Đến nay, rất nhiều công trình nghiên cứu liên quan đến các lĩnh vực này. Các luật kết hợp và mẫu chuỗi, luật chuỗi được đề xuất là rất đa dạng, chúng có thể là các luật, mẫu chuỗi giao dịch/định lượng; có trọng số/không trọng số; có yếu tố thời gian/không có yếu tố thời gian;.