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

Nội dung tài liệu: 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

1. 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 Chuyên ngành: Hệ thống thông tin Mã số: 9 48 01 04 TÓM TẮT LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội – 2021
2. Công trình đƣợc hoàn thành 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 Ngƣời hƣớng dẫn khoa học 1: PGS.TS. Đỗ Văn Thành Ngƣời hƣớng dẫn khoa học 2: PGS.TS. Nguyễn Đức Dũng Phản biện 1: Phản biện 2: Phản biện 3: . Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp 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 vào hồi giờ ‟, ngày tháng năm 201 . Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
3. MỞ ĐẦU 1. Tính cấp thiết của luận án và động lực nghiên cứu (Phương and Thành, 2013) 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;.v.v Vấn đề phát hiện luật kết hợp trong các CSDL giao địch được đề xuất lần đầu vào năm 1993 (Agrawal, Imieliński and Swami, 1993) và đến nay đã có nhiều thuật toán được xây dựng theo rất nhiều cách tiếp cận khác nhau để phát hiện các luật này trong các CSDL giao dịch: APRIORI (Agrawal, Srikant and others, 1994), PARTITION (Savasere, Omiecinski and Navathe, 1995), A-CLOSE (Pasquier et al., 1999a), A-CLOSE+ (Shekofteh, Rahmani and Dezfuli, 2008), CLOSE (Pasquier et al., 1999b), CLOSET (Pei et al., 2000), CLOSET+ (Wang, Han and Pei, 2003), CHARM (Zaki and Hsiao, 2002), MAFIA (Burdick, Calimlim and Gehrke, 2001), GENMAX (Gouda and Zaki, 2005), ECLAT (Ogihara et al., 1997), DIC (Brin et al., 1997), FP-GROWTH (Han et al., 2004), CFPMINE (Qin, Luo and Shi, 2004), ETARM (Nguyen et al., 2018), LRM (Saravanan and Sree, 2011), PARM (Sumathi and Kirubakaran, 2012), NEGFIN (Aryabarzan, Minaei-Bidgoli and Teshnehlab, 2018). Tuy nhiên các CSDL trong thực tế thường có các thuộc tính nhận giá trị số hoặc giá trị phân loại. Những CSDL như vậy được gọi là CSDL định lượng. Việc phát hiện các luật kết hợp trong CSDL định lượng thường sử dụng một trong 2 cách đó là: rời rạc hóa (Srikant and Agrawal, 1996a; Lent, Swami and Widom, 1997; Fukuda et al., 1999; Rastogi and Shim, 2002) và mờ hóa các thuộc tính định lượng (Chan and Au, 1997; Kuok, Fu and Wong, 1998; T.-P. Hong, Kuo and Chi, 1999; Hong, Kuo and Chi, 2001; Hong, Chiang and Wang, 2002; Hong, 2003). Bản chất của cách tiếp cận thứ nhất là đưa CSDL định lượng về CSDL giao dịch bằng cách chuyển các thuộc tính định lượng thành một số mục (item) tương ứng và sau đó áp dụng một trong các thuật toán phát hiện các luật kết hợp trong các CSDL giao dịch đã biết. Cách tiếp cận thứ hai nhằm khắc phục nhược điểm của cách tiếp cận thứ nhất, nhưng khi đó các thuật toán phát hiện các luật kết hợp trong các CSDL cần được cải tiến và phát triển tiếp. CSDL có yếu tố thời gian (temporal database) là CSDL có lưu trữ thông tin về thời điểm xảy ra của các giao dịch (Tansel et al., 1993) (Aydin and Angryk, 2018). Năm 1998, Lu và các cộng sự (Lu, Han and Feng, 1998) đã đề xuất luật kết hợp có tính đến độ chênh lệch về thời điểm (gọi là khoảng cách thời gian) xảy ra giữa các giao dịch trong các CSDL giao dịch có yếu tố thời gian, luật có dạng → với a, b là các tập mục dữ liệu. Trong (Lu, Han and Feng, 1998), hai thuật toán E-Apriori và EH-Apriori được đề xuất để phát hiện các luật dạng này. Về ý tưởng chính, hai thuật toán E-Apriori, EH-Apriori dựa trên ý tưởng thuật toán Apriori và sử dụng cửa sổ trượt đối với khoảng cách thời gian. Để phát hiện các luật kết hợp có tính đến khoảng cách thời gian trong các CSDL giao dịch có yếu tố thời gian, nhiều thuật toán tiếp tục được đề xuất như: FITI (Tung et al., 2003), ITARM (Qin and Shi, 2006), ITP- Miner (Lee and Wang, 2007), IAR Miner (Nandagopal, Arunachalam and Karthik, 2012), CITP-Miner (Nguyen et al., 2019), NCITPS-MINER (Nguyen et al., 2020). Việc phát hiện luật kết hợp có tính đến khoảng cách thời gian mới chỉ dừng lại đối với CSDL giao dịch có yếu tố thời gian mà chưa được thực hiện đối với các CSDL định lượng có yếu tố thời gian. Đây là khoảng trống nghiên cứu mà luận án mong muốn giải quyết. Luật chuỗi, mẫu chuỗi như được hiểu từ trước đến nay còn được gọi là luật chuỗi, mẫu chuỗi cổ điển để phân biệt với một loại luật chuỗi, mẫu chuỗi mới được đề xuất trong những năm gần đây. Các mẫu chuỗi cổ điển (được gọi ngắn gọn là mẫu chuỗi) là các chuỗi cổ điển (nói gọn là chuỗi) phổ biến trong các CSDL chuỗi giao dịch. Các mẫu chuỗi này biểu diễn mối quan hệ có trình tự thời gian xảy ra giữa các giao dịch trong chuỗi. Phát hiện mẫu chuỗi 1
4. trong các CSDL chuỗi giao dịch được giới thiệu lần đầu năm 1995 (Agrawal, Srikant and others, 1995) và đến nay đã nhận được rất nhiều sự quan tâm. Hiện đã có nhiều thuật toán phát hiện các mẫu chuỗi trong các CSDL chuỗi giao dịch như GSP (Srikant and Agrawal, 1996b), SPIRIT (Garofalakis, Rastogi and Shim, 1999), SPADE (Zaki, 2001), SPAM (Ayres et al., 2002), FAST (Salvemini et al., 2011), CM-SPADE (Fournier-Viger, Gomariz, Campos, et al., 2014), MAXSP (Fournier-Viger, Wu and Tseng, 2013), GENMINER (Lo, Khoo and Li, 2008), FREESPAN (Han et al., 2000), PREFIXSPAN (Pei et al., 2004), CLOSPAN (Yan, Han and Afshar, 2003), MSPIC-DBV (Van, Vo and Le, 2018), HSPREC (Bhatta, Ezeife and Butt, 2019), Các CSDL chuỗi giao dịch có yếu tố thời gian là CSDL có lưu trữ thông tin về thời điểm xảy ra của các giao dịch. Năm 2000, Yoshida và các cộng sự (Yoshida et al., 2000) đã đề xuất mẫu chuỗi có tính đến khoảng cách thời gian trong CSDL chuỗi giao dịch có yếu tố thời gian, mẫu chuỗi này có dạng 〈 〉 với a, b, c là các tập mục, [1−4] và [5−9] là khoảng thời gian có thể xảy ra lần lượt giữa a, b và giữa b, c. Để phát hiện mẫu chuỗi có tính đến khoảng cách thời gian, thuật toán Delta-Pattern đã được đề xuất trong (Yoshida et al., 2000). Phát hiện mẫu chuỗi có tính đến khoảng cách thời gian như trong (Yoshida et al., 2000) tiếp tục được giải quyết bởi các thuật toán I-Apriori và I-PrefixSpan (Chen, Chiang and Ko, 2003), TAS (Giannotti et al., 2006). Năm 2005, để khắc phục hiện tượng “sắc nét” tại các điểm giáp danh của các khoảng chia đối với khoảng cách thời gian, Chen và Huang (Chen and Huang, 2005) đã đề xuất mẫu chuỗi có tính đến khoảng cách thời gian mà ở đó khoảng cách thời gian là các tập mờ, mẫu chuỗi khi đó có dạng 〈 〉 với Short, Long là các tập mờ, mỗi tập mờ có hàm thành viên tương ứng. Trong (Chen and Huang, 2005), hai thuật toán FTI-Apriori và FTI-PrefixSpan được đề xuất để phát hiện các mẫu chuỗi này. Mẫu chuỗi này tiếp tục được phát hiện bởi thuật toán FP Growth- PrefixSpan (Mukhlash, Yuanda and Iqbal, 2018). Khái niệm luật chuỗi chung mới được xuất hiện trong vài năm gần đây (Fournier-Viger et al., 2010, 2017) do Fournier-Viger và các cộng sự đề xuất. Luật chuỗi chung được phát hiện trong các CSDL chuỗi giao dịch biểu diễn mối quan hệ của 2 tập mục, ở đó các mục ở các phần tiền đề (bên trái) và hệ quả (bên phải) của luật không cần sắp thứ tự mà chỉ cần thỏa mãn điều kiện các mục ở phần tiền đề phải được xảy ra trước các mục ở phần hệ quả. Thuật toán phát hiện các luật chuỗi chung đầu tiên là CMRules (Fournier-Viger et al., 2010) sau đó tiếp tục được phát triển bởi Rule Growth (Fournier-Viger, Nkambou and Tseng, 2011), ERMiner (Fournier-Viger, Gueniche, et al., 2014). Các luật chuỗi chung thực sự là có ích và đã được ứng dụng trong thực tế (Çelebi et al., 2014). Luật chuỗi chung đến nay mới chỉ được phát hiện trong các CSDL chuỗi giao dịch mà chưa được áp dụng đối với CSDL chuỗi định lượng có yếu tố thời gian. Đây là khoảng trống thứ 3 được xác định trong vấn đề nghiên cứu của luận án. Luận án này nhằm giải quyết 3 khoảng trống được xác định ở trên. Việc nghiên cứu giải quyết những vấn đề đó là thực sự cần thiết không chỉ ở phương diện phát triển lý thuyết mà cả ở phương diện ứng dụng thực tế. Đó là động lực để tác giả luận án thực hiện nghiên cứu đề tài “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ể luận án đề xuất và giải quyết các vấn đề về phát hiện các luật kết hợp và mẫu chuỗi, luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao dịch tương ứng trong các CSDL định lượng có yếu tố thời gian và CSDL chuỗi định lượng có yếu tố thời gian. Luận án thực sự có đóng góp mới về mặt lý thuyết, cung cấp các giải pháp cho những vấn đề chưa được giải quyết trong hướng nghiên cứu về phát hiện các luật kết hợp và các mẫu chuỗi, luật chuỗi chung tương ứng trong CSDL định lượng và CSDL chuỗi định lượng cùng có yếu tố thời gian. 2. Mục tiêu, đối tƣợng và phạm vi nghiên cứu của luận án 2
5. 2.1. Mục tiêu của luận án Phát hiện các luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian. Các luật tìm được khi đó được gọi là các luật kết hợp mờ với khoảng cách thời gian mờ. Phát hiện các mẫu chuỗi có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Các mẫu chuỗi tìm được khi đó được gọi là mẫu chuỗi mờ với khoảng cách thời gian mờ. Phát hiện các luật chuỗi chung (là luật chuỗi ở dạng tổng quát và chung hơn so với các luật chuỗi (cổ điển) như được biết từ trước đến nay) có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Các luật tìm được được gọi là các luật chuỗi chung mờ với khoảng cách thời gian mờ. 2.2. Đối tượng nghiên cứu: là các thuật toán phát hiện các luật kết hợp, và các mẫu chuỗi, luật chuỗi chung có tính đến khoảng cách thời gian trong các CSDL định lượng và CSDL chuỗi định lượng cùng có yếu tố thời gian. 2.3. Phạm vi nghiên cứu: Luận án nghiên cứu các luật kết hợp, các mẫu chuỗi, các luật chuỗi chung, các CSDL định lượng và CSDL chuỗi định lượng cùng có yếu tố thời gian. Các tập mờ được sử dụng như các tham số cho trước làm đầu vào cho các thuật toán đề xuất, luận án không tập trung nghiên cứu sâu về lý thuyết mờ. Do các luật kết hợp, mẫu chuỗi, luật chuỗi chung được đề xuất trong luận án là mới, nên các phần thực nghiệm của luận án không so sánh kết quả với các thuật toán khác. 3. Phƣơng pháp nghiên cứu Luận án đã sử dụng các phương pháp nghiên cứu sau: Phương pháp tổng hợp, phân tích: được sử dụng để tổng hợp và phân tích các nghiên cứu về những vấn đề liên quan để phát hiện các khoảng trống nghiên cứu và xác định vấn đề nghiên cứu mà luận án cần giải quyết. Phương pháp phân tích cũng thường được sử dụng khi đề xuất các khái niệm mới liên quan đến vấn đề nghiên cứu của luận án sao cho những khái niệm mới được phát triển dựa trên nhiều nhất có thể các khái niệm đã có liên quan. Phương pháp so sánh: được sử dụng để so sánh các kỹ thuật, thuật toán đã được đề xuất để giải quyết những vấn đề nghiên cứu liên quan, từ đó hình thành ý tưởng cho thuật toán mới cho vấn đề nghiên cứu. Phương pháp thiết kế và đánh giá độ phức tạp thuật toán: được sử dụng để thiết kế thuật toán giải quyết bài toán cụ thể được đặt ra trong luận án và ước lượng độ phức tạp tính toán của các thuật toán này. Phương pháp thực nghiệm: Các thuật toán được đề xuất đều được thực nghiệm trên các tập dữ liệu thực để đánh giá sự đúng đắn và tính khả thi của thuật toán. 4. Các đóng góp chính của luận án Những đóng góp chính của luận án là đề xuất và giải quyết các vấn đề sau: Đề xuất vấn đề và thuật toán phát hiện luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian, ở đó các thuộc tính định lượng và khoảng cách thời gian xảy ra giữa các giao dịch được chuyển thành các thuộc tính mờ và khoảng cách thời gian mờ [CT4]. Đề xuất vấn đề và thuật toán phát hiện mẫu chuỗi (cổ điển) có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian, ở đó các thuộc tính định lượng và khoảng cách thời gian xảy ra giữa các giao dịch cũng được chuyển thành các thuộc tính mờ và khoảng cách thời gian mờ [CT5]. Đề xuất vấn đề và thuật toán phát hiện luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao địch trong các CSDL chuỗi định lượng có yếu tố thời gian, ở đó các 3
6. thuộc tính định lượng và khoảng cách thời gian cũng được chuyển thành các thuộc tính mờ và khoảng cách thời gian mờ [CT9]. 5. Bố cục luận án Luận án gồm phần mở đầu, 04 chương nội dung và phần kết luận: Phần mở đầu: Trình bày sự cần thiết và động lực nghiên cứu của đề tài; mục tiêu, đối tượng, phạm vi nghiên cứu; phương pháp nghiên cứu; những đóng góp chính và cấu trúc của luận án. Chương 1: Tổng quan về luật kết hợp và mẫu chuỗi, luật chuỗi chung. Chương 2: 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. Chương 3: 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. Chương 4: 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. Phần kết luận: Trình bày một số kết luận về ý nghĩa, đóng góp của luận án và định hướng nghiên cứu trong tương lai. CHƯƠNG 1. TỔNG QUAN VỀ LUẬT KẾT HỢP VÀ MẪU CHUỖI, LUẬT CHUỖI CHUNG Chương này trình bày tổng quan những vấn đề liên quan đến phát hiện các luật kết hợp và các mẫu chuỗi, luật chuỗi chung trong các CSDL giao dịch/định lượng không có hoặc có yếu tố thời gian. Chương này cũng chỉ ra các khoảng trống chưa được giải quyết để từ đó xác định vấn đề nghiên cứu của luận án. 1.1. Luật kết hợp 1.1.1. Phát hiện luật kết hợp trong các CSDL giao dịch Định nghĩa 1.1 CSDL giao dịch (Agrawal, Srikant and others, 1994): Giả sử I = { } là tập các mục, D = { } là tập các giao dịch, (1 j m) là tập các mục thỏa mãn  I, biểu diễn mục xuất hiện trong giao dịch (hay tương ứng nhận giá trị 1 nếu xuất hiện trong giao dịch này), nói cách. Khi đó, D được gọi là CSDL giao dịch. Định nghĩa 1.2 Luật kết hợp (Agrawal, Imieliński and Swami, 1993): Giả sử X là tập mục, giao dịch T được gọi là chứa X khi và chỉ khi XT. Luật kết hợp là luật có dạng X Y với XI, YI và XY=. Trong đó X được gọi là tiền đề, Y là hệ quả của luật. Định nghĩa 1.3 Độ hỗ trợ và độ tin cậy của luật kết hợp (Agrawal, Imieliński and Swami, 1993) Độ hỗ trợ (support) của tập mục X là tỉ lệ số giao dịch trong D chứa X, kí hiệu là sup(X) |{ | }| (1.1) | | Độ hỗ trợ của luật là tỉ lệ số giao dịch trong D chứa XY, kí hiệu là (1.2) | | Độ tin cậy (confidence) của luật là tỉ lệ số giao dịch trong D chứa X cũng chứa Y, kí hiệu là (1.3) 4
7. Việc phát hiện các luật kết hợp thường được chia làm 2 giai đoạn (Agrawal, Imieliński and Swami, 1993; Kotsiantis and Kanellopoulos, 2006): Giai đoạn 1: Tìm tất cả các tập phổ biến trong CSDL, ở đó các tập phổ biến là các tập có độ hỗ trợ không nhỏ hơn độ hỗ trợ cực tiểu (hay ngưỡng hỗ trợ) cho trước; Giai đoạn 2: Sinh ra các luật kết hợp có độ tin cậy không nhỏ hơn độ tin cậy cực tiểu (hay ngưỡng tin cậy) cho trước từ các tập phổ biến đã tìm được ở giai đoạn 1. 1.1.2. Phát hiện luật kết hợp trong các CSDL định lượng Định nghĩa 1.4 CSDL định lượng (Chan and Au, 1997): Giả sử I = { } là tập các thuộc tính, D = { } là tập các giao dịch, (1 j m) là tập các thuộc tính thỏa mãn  I, các giá trị tương ứng với thuộc tính (1 k n) trong giao dịch (1 j m) nhận giá trị là số hoặc phân loại. Khi đó, D được gọi là CSDL định lượng. 1.1.3. 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 Định nghĩa 1.5 CSDL có yếu tố thời gian là CSDL (giao dịch hoặc định lượng) ở đó có thuộc tính thời gian nhận giá trị là thời điểm (hay timestamp) xảy ra của mỗi giao dịch. Bảng 1.1. 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 Thuật toán Tập dữ liệu Tập phổ biến/luật Ý nghĩa EH-Apriori (Lu, Han and Feng, CSDL giao Nếu mặt hàng a được → 1998), dịch có yếu mua thì mặt hàng b FITI (Tung et al., 2003), tố thời gian cũng sẽ được mua sau ITARM (Qin and Shi, 2006), 2 ngày tiếp theo ITP-Miner (Lee and Wang, 2007), IAR Miner (Nandagopal, Arunachalam and Karthik, 2012), NCITPS-Miner (Nguyen et al., 2020) 1.2. Mẫu chuỗi 1.2.1. Phát hiện mẫu chuỗi trong các CSDL chuỗi giao dịch Định nghĩa 1.6 CSDL chuỗi giao dịch (Agrawal, Srikant and others, 1995): Giả sử I ={ } là tập các mục. Một chuỗi s =〈 〉 là danh sách có thứ tự các tập mục với  I (1 k m). Một CSDL chuỗi giao dịch SD là tập các chuỗi giao dịch SD = { }. Định nghĩa 1.7 Độ dài chuỗi (Agrawal, Srikant and others, 1995): Độ dài của chuỗi 〈 〉 là tổng số các tập mục của chuỗi. Một chuỗi có độ dài k được gọi là k- chuỗi. Định nghĩa 1.8 Chuỗi con (Agrawal, Srikant and others, 1995): Chuỗi 〈 〉 được gọi là chuỗi con của chuỗi 〈 〉 khi và chỉ khi tồn tại k số nguyên sao cho    và được kí hiệu là  . Nói cách khác, chuỗi là chuỗi con của chuỗi nếu có thể nhận được từ sau khi bỏ đi một số giao dịch hoặc một số mục trong các giao dịch của . Khi đó ta có thể gọi là chuỗi chứa chuỗi . Định nghĩa 1.9 Độ hỗ trợ của chuỗi (Agrawal, Srikant and others, 1995): Độ hỗ trợ của chuỗi trong CSDL chuỗi SDB, kí hiệu là sup( ), là tỷ số của số chuỗi trong SDB chứa và tổng số chuỗi trong CSDL này. Độ hỗ trợ của chuỗi được tính theo công thức: |{ |  }|/|SDB| (1.4) 5
8. Chuỗi được gọi là phổ biến hay là mẫu chuỗi khi và chỉ khi độ hỗ trợ của chuỗi s không nhỏ hơn độ hộ trợ cực tiểu min_sup cho trước, tức là sup( ) min_sup. 1.2.2. Phát hiện mẫu chuỗi trong các CSDL chuỗi định lượng Định nghĩa 1.10 CSDL chuỗi định lượng: Giả sử I = { } là tập các thuộc tính. Một chuỗi định lượng s = 〈 〉 là danh sách có thứ tự các tập thuộc tính  I (1 k m) và các thuộc tính a nhận giá trị là số hoặc phân loại. Một CSDL chuỗi định lượng là tập các chuỗi định lượng { }. 1.2.3. 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 Định nghĩa 1.11 CSDL chuỗi giao dịch/định lượng có yếu tố thời gian (Guyet, 2020): là CSDL chuỗi giao dịch/định lượng ở đó có thêm thuộc tính thời gian nhận giá trị là thời điểm xảy ra của mọi giao dịch trong các chuỗi giao dịch. { } 〈 〉 Giả sử I = là tập các mục. Một chuỗi , ở đây là thời điểm xuất hiện của mục I (1 n) trong chuỗi. Chuỗi giao dịch s cũng có thể được viết dưới dạng s = 〈 〉 (1≤ j≤ k) và tương ứng là thời điểm xảy ra của các giao dịch mua các mặt hàng trong Một CSDL chuỗi có yếu tố thời gian là tập tất cả các chuỗi có yếu tố thời gian { }. Trong CSDL trên, nếu các mục trong I được xem là các thuộc tính nhận giá trị 1 hoặc 0 tương ứng với mục đó xuất hiện hay không xuất hiện thì CSDL chuỗi giao dịch có yếu tố thời gian trở thành CSDL chuỗi nhị phân có yếu tố thời gian. Nếu các thuộc tính trong I nhận các giá trị số hoặc giá trị phân loại thì nhận được một CSDL được gọi là CSDL chuỗi định lượng có yếu tố thời gian. Bảng 1.2. 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 Thuật toán Tập dữ liệu Mẫu Ý nghĩa TAS (Giannotti et CSDL chuỗi 〈 〉 Nếu một khách hàng mua a và sau đó al., 2006) giao dịch có yếu mua b trong thời gian 3 ngày thì tố thời gian khách hàng đó sẽ mua c sau 5 ngày tiếp theo. Delta-Pattern CSDL chuỗi 〈 〉 Nếu một khách hàng mua a và sau (Yoshida et al., giao dịch có yếu đó mua b trong thời gian [0, 3 ngày] 2000) tố thời gian thì khách hàng đó sẽ mua c trong vòng [0, 5 ngày] tiếp theo. I-Apriori algorithm, CSDL chuỗi 〈 〉 Nếu một khách hàng mua a và sau đó I-PrefixSpan (Chen, giao dịch có yếu (khoảng cách thời mua b sau thời gian I1 thì khách hàng Chiang and Ko, tố thời gian gian là giá trị rõ) đó sẽ mua c sau thời gian I2. 2003) FTI-Apriori, FTI- CSDL chuỗi 〈 〉 Nếu một khách hàng mua a và mua b PrefixSpan (Chen giao dịch có yếu (Khoảng cách thời sau thời gian Short thì khách hàng đó and Huang, 2005) tố thời gian gian là giá trị mờ) sẽ mua c sau thời gian Long. FP-Growth- PrefixSpan (Mukhlash, Yuanda and Iqbal, 2018) SPFTI (Chang, CSDL chuỗi 〈 〉 Nếu một khách hàng mua a và mua b Chueh and Lin, giao dịch có yếu (Khoảng cách thời sau thời gian thì khách hàng đó 2009), tố thời gian gian là giá trị mờ) sẽ mua c sau thời gian 6
9. ISPFTI (Chang, Chueh and Luo, 2012) 1.3. Luật chuỗi chung 1.3.1. Khái niệm luật chuỗi chung Định nghĩa 1.12 Luật chuỗi chung (Fournier-Viger et al., 2012): Giả sử I = { } là tập các mục, SD là CSDL chuỗi giao dịch, một luật chuỗi chung có dạng X⟹Y, trong đó X, Y  I thỏa mãn X  Y=, X, Y ≠  và các mục trong Y phải xuất hiện sau các mục trong X. 1.3.2. Phát hiện luật chuỗi chung Luật chuỗi chung mới được xuất hiện trong vài năm gần đây (Fournier-Viger et al., 2010). Các thuật toán để phát hiện các luật chuỗi chung trong các CSDL chuỗi chưa nhiều. Bảng 1.3 sau đây giới thiệu các thuật toán như vậy. Bảng 1.3. Một số nghiên cứu về phát hiện luật chuỗi chung Thuật toán Dữ liệu Mẫu/Luật Mô tả CMRules (Fournier-Viger CSDL chuỗi Luật chuỗi chung: Nếu một khách hàng et al., 2010), giao dịch {a, b} ⟹ {c} mua a và mua b thì Rule Growth (Fournier- khách hàng đó sẽ mua Viger, Nkambou and c sau đó Tseng, 2011), ERMiner (Fournier-Viger, Gueniche, et al., 2014) Định nghĩa 1.13 Các lớp tương đương trái/phải (Fournier-Viger, Gueniche, et al., 2014): Cho CSDL chuỗi giao dịch, I là tập các mục trong CSDL này. Một lớp tương đương trái được kí hiệu là được xác định là = {W ⟹ Y | Y I |Y| = i} trong đó W I và i là số tự nhiên. Tương tự, một lớp tương đương phải kí hiệu là được xác định là = {X ⟹ W | X I |X| = i} trong đó W I và i là số nguyên. Định nghĩa 1.14 Các phép hợp nhất trái/phải (Fournier-Viger, Gueniche, et al., 2014): Giả sử là lớp tương đương trái và hai luật r = W ⟹ X và s = W ⟹ Y đều thuộc và |  | | – |. Một phép hợp trái của r và s là quá trình kết hợp r, s để nhận được luật ⟹  . Tương tự, gọi là lớp tương đương phải và hai luật r = ⟹ và s = ⟹ thỏa mãn r, s và |  | | – |. Một phép hợp phải của r và s là quá trình kết hợp r, s để được  ⟹ Kết luận Chương 1 Chương 1 đã trình bày một cách tổng quan, tóm tắt những vấn đề liên quan đến phát hiện các luật kết hợp và mẫu chuỗi, luật chuỗi chung tương ứng trong các CSDL (giao dịch, định lượng) và CSDL chuỗi (giao dịch, định lượng) có yếu tố thời gian. Luận án sẽ tập trung nghiên cứu đề xuất và giải pháp giải quyết triệt để 3 vấn đề sau đây: Vấn đề 1: Phát hiện các luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian. Vấn đề 2: Phát hiện các mẫu chuỗi có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Vấn đề 3: Phát hiện các luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Ba chương nội dung tiếp theo trong luận án sẽ trình bày cụ thể giải pháp tương ứng cho 3 vấn đề nghiên cứu đó. 7
10. CHƯƠNG 2. 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 Trong chương 1, luận án đã chỉ ra khoảng trống cần được nghiên cứu về phát hiện các luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian. Chương này, luận án sẽ trình bày giải pháp để giải quyết vấn đề nghiên cứu đó. Khi đó, một dạng luật kết hợp mới được gọi là luật kết hợp mờ với khoảng cách thời gian mờ sẽ được phát hiện. Kết quả nghiên cứu của Chương này đã được đăng trên tạp chí Indian Journal of Science and Technology [CT4]. Chương này chủ yếu tập trung trình bày vấn đề phát hiện luật kết hợp mờ với khoảng cách thời gian mờ trong các CSDL định lượng có yếu tố thời gian. 2.1. Giới thiệu Phát hiện luật kết hợp là hướng nghiên cứu và ứng dụng quan trọng trong lĩnh vực khai phá dữ liệu. Phát hiện luật kết hợp từ CSDL giao dịch đã được Rakesh Agrawal cùng cộng sự đề xuất lần đầu năm 1993 (Agrawal, Imieliński and Swami, 1993) và đến nay đã nhận được rất nhiều kết quả nghiên cứu (Agrawal, Srikant and others, 1994; Savasere, Omiecinski and Navathe, 1995; Zaki and Hsiao, 2002; Sumathi and Kirubakaran, 2012; Aryabarzan, Minaei- Bidgoli and Teshnehlab, 2018). Trong quá trình nghiên cứu phát hiện luật kết hợp người ta còn quan tâm đến khoảng cách thời gian xảy ra giữa các giao dịch (Lu, Han and Feng, 1998; Tung et al., 2003; Qin and Shi, 2006; Lee and Wang, 2007; Nandagopal, Arunachalam and Karthik, 2012) và khoảng cách thời gian giữa các giao dịch được mờ hóa trong nghiên cứu (Chen and Huang, 2005). Ý tưởng chính của nghiên cứu (Chen and Huang, 2005) là mờ hóa khoảng cách thời gian rồi sau đó phát hiện các mẫu chuỗi dạng 〈 〉, trong đó a, b, c là các mục, Short, Long là các khái niệm mờ liên tương ứng với khoảng cách thời gian; đề xuất hai thuật toán FTI- Apriori và FTI-Prefix Span cho việc phát hiện các mẫu chuỗi với khoảng cách thời gian mờ. Tuy nhiên nghiên cứu (Chen and Huang, 2005) chỉ đề cập đến việc mẫu chuỗi với khoảng cách thời gian đối với CSDL chuỗi giao dịch mà các thuộc tính ở đó không phải là thuộc tính định lượng mà không áp dụng được đối với CSDL định lượng, tức là chỉ có thể phát hiện các luật có dạng “Nếu một khách hàng mua a và mua b sau thời gian Short thì khách hàng đó sẽ mua c sau thời gian Long”. Nghiên cứu [CT2] đã đề xuất và giải quyết vấn đề phát hiện luật kết hợp với khoảng cách thời gian mờ trong CSDL giao dịch có yếu tố thời gian. Luật phát hiện dạng “Nếu mặt hàng a được mua hôm nay thì mặt hàng b sẽ được mua trong Ngắn ngày kế tiếp”. Thuật toán FTITS đã được đề xuất để phát hiện luật trong [CT2]. Thuật toán FTITS dựa trên ý tưởng thuật toán FTI-Apriori (Chen and Huang, 2005) để phát hiện các chuỗi với thời gian mờ phổ biến làm cơ sở để tìm luật đã đề xuất. Mục đích của chương này phát hiện luật dạng tổng quát đó là luật kết hợp mờ với khoảng cách thời gian mờ trong CSDL định lượng có yếu tố thời gian. 2.2. Một số khái niệm cơ bản Định nghĩa 2.1 Gọi I={ } là tập các thuộc tính, D = { }, trong đó (1 j p) là tập các thuộc tính thỏa mãn  I tại thời điểm ( ≥0), là giá trị định lượng của tại thời điểm (1≤k≤n). Khi đó, D được gọi là CSDL định lượng có yếu tố thời gian. Định nghĩa 2.2 Cho T là tập các giao dịch, I là tập các thuộc tính và { } là tập các tập mờ gắn với các thuộc tính trong I, { } là các tập mờ gắn với thuộc tính (k=1, , n), trong đó h là số k lượng tập mờ của thuộc tính , là tập mờ thứ j của thuộc tính (1≤ j≤ ). 8
11. DF = (T, I, FE) được gọi là CSDL mờ có yếu tố thời. Mỗi tập mờ đều có hàm thành viên tương ứng : X [0,1]. Như vậy, DF là CSDL mờ có yếu tố thời gian dựa trên CSDL định lượng có yếu tố thời gian D bằng cách mờ hóa các thuộc tính định lượng. Định nghĩa 2.3 : Một chuỗi giao dịch mờ P được biểu diễn dạng 〈 〉 trong đó là một thuộc tính mờ và là thời điểm xảy ra (1≤j≤n với 2≤j≤n), giá trị mờ của tại thời điểm là . Trong chuỗi giao dịch mờ P, nếu các mục xảy ra cùng thời điểm thì các thuộc tính mờ sẽ được sắp xếp theo trình tự bảng chữ cái. Giá trị khoảng cách thời gian giữa hai phần tử liên tiếp trong chuỗi được xác định là (1≤j≤n-1). Định nghĩa 2.4 (mở rộng từ (Chen and Huang, 2005)) Gọi FE là tập các tập mờ gắn với các thuộc tính định lượng trong CSDL định lượng có yếu tố thời gian và LT={ | j=1,2, ,p} là tập các tập mờ ứng với khoảng cách thời gian. Chuỗi β = là một chuỗi mờ với khoảng cách thời gian mờ nếu FE và LT với 1≤j≤r-1 và FE. Chuỗi β khi đó có độ dài r. Định nghĩa 2.5 (mở rộng từ (Chen and Huang, 2005)) Một chuỗi mờ với khoảng cách thời gian mờ = là chuỗi con của chuỗi mờ với khoảng cách thời gian mờ β = khi và chỉ khi tồn tại số nguyên w thỏa mãn với i|1≤i≤k-1 và . Trong trường hợp k=1 thì . Định nghĩa 2.6 (mở rộng từ (Chen and Huang, 2005)) Cho hai chuỗi mờ với khoảng cách thời gian mờ 1 = và 2 = . Khi đó, phép kết hợp 2 chuỗi 1 và 2 tạo thành chuỗi = . Định nghĩa 2.7 Một luật kết hợp mờ với khoảng cách thời gian mờ có dạng , trong đó X, Y là chuỗi mờ với khoảng cách thời gian mờ, LT. Ví dụ: → là một luật kết hợp mờ với khoảng cách thời gian mờ. Gọi P = 〈 〉 là một chuỗi giao dịch mờ và α = là một chuỗi mờ với khoảng cách thời gian mờ, với 1≤i≤r là giá trị của tại thời điểm . Khi đó, độ hỗ trợ của P đối với α được định nghĩa như sau: { (2.1) { } { } Cho CSDL mờ có yếu tố thời gian DF với N giao dịch, ta có các định nghĩa sau: Độ hỗ trợ của α trong DF được xác định là: ∑ (2.2) Độ tin cậy của luật trong DF được xác định là: ( ) (2.3) Độ hỗ trợ của luật được xác định là: 9
12. ( ) (2.4) Một chuỗi mờ với khoảng cách thời gian mờ được gọi là phổ biến khi có độ hỗ trợ không nhỏ hơn ngưỡng cực tiểu min_sup cho trước. Từ Định nghĩa 2.5 và Error! Reference source not found.ta thu được các tính chất sau: Tính chất 1: Chuỗi con của chuỗi mờ với khoảng cách thời gian mờ phổ biến thì cũng phổ biến. Tính chất 2: Mọi chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k đều là kết quả của phép kết hợp hai chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k-1. 2.3. 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ờ 2.3.1. Bài toán đặt ra Cho trước CSDL định lượng có yếu tố thời gian D, độ hỗ trợ cực tiểu và độ tin cậy cực tiểu tương ứng là min_sup và min_conf, tập mờ về khoảng cách thời gian LT cùng các hàm thành viên tương ứng, tập các tập mờ FE của các thuộc tính định lượng trong D cùng các hàm thành viên tương ứng. Bài toán đặt ra: Phát hiện các luật kết hợp mờ với khoảng cách thời gian mờ có độ hỗ trợ không nhỏ hơn độ hỗ trợ cực tiểu min_sup và độ tin cậy không nhỏ hơn độ tin cậy cực tiểu min_conf. 2.3.2. Ý tưởng thuật toán Đầu tiên, chuyển đổi CSDL định lượng có yếu tố thời gian D thành CSDL mờ có yếu tố thời gian DF dựa vào các tập mờ cùng các hàm thành viên gắn với thuộc tính của D. Tiếp theo, tìm tất cả các chuỗi mờ với khoảng cách thời gian mờ phổ biến. Quá trình tìm các chuỗi mờ với khoảng cách thời gian mờ phổ biến được phát triển dựa theo thuật toán Apriori: lặp lại 2 bước trong quá trình sinh chuỗi mờ với khoảng cách thời gian mờ phổ biến cho đến khi không thể sinh được. Ở bước 1, các chuỗi ứng cử viên độ dài k, kí hiệu là được sinh ra từ tập các chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k-1, kí hiệu là . Bước 2, các chuỗi ứng cử viên trong có độ hỗ trợ không nhỏ hơn min_sup được thêm vào tập các chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k, . Quá trình này dừng lại cho đến khi =. Tiếp theo, các luật kết hợp mờ với khoảng cách thời gian mờ được sinh ra từ các chuỗi mờ với khoảng cách thời gian mờ phổ biến có độ dài lớn hơn 1. Các luật này được tính độ tin cậy theo công thức Error! Reference source not found Kết quả trả lại của thuật toán là tất cả các luật có độ tin cậy thỏa mãn độ tin cậy cực tiểu min_conf. 2.3.3. Thuật toán FTQ Thuật toán FTQ được mô tả như trong Error! Reference source not found.: Thuật toán 2.1. Thuật toán FTQ Input: - CSDL định lượng có yếu tố thời gian D; - Độ hỗ trợ cực tiểu và độ tin cậy cực tiểu min_sup, min_conf; - Tập các tập mờ FE và các hàm thành viên tương ứng với các thuộc tính trong D; - Tập LT và các hàm thành viên tương ứng về khoảng cách thời gian. Output: Tất cả các luật kết hợp mờ với khoảng cách thời gian mờ có độ hỗ trợ không nhỏ hơn min_sup và độ tin cậy không nhỏ hơn min_conf. FTQ{ 1. Chuyển D thành CSDL mờ có yếu tố thời gian DF 10
13. 2. ={các thuộc tính trong DF} 3. ={α |Supp(α)≥min_sup} 4. =; 5. for each do 6. for each do 7. for each ltd LT do { 8. α= *ltd* ; 9. add α to ; 10. } 11. for each α do 12. α.count=Supp(α); 13. ={α |α.count ≥min_sup} 14. for (k>2; ≠;k++){ 15. =fuzzy_apriori_gen( ); 16. for each α do 17. α.count=Supp(α); 18. ={α |α.count ≥min_sup} 19. } 20. return Generating_rules(  ); 21.} 2.3.4. Tính đúng đắn và tính đầy đủ của thuật toán Định lý 2.1. Thuật toán FTQ là đúng đắn và đầy đủ. 2.3.5. 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ờ Định lý 2.2: Thuật toán FTQ có thể tìm được các luật và 2.4. Thử nghiệm thuật toán 2.4.1. Dữ liệu thử nghiệm Bảng 2.1. Dữ liệu thử nghiệm ISTANBUL STOCK EXCHANGE CSDL Số thuộc tính Số giao dịch ISTANBUL STOCK EXCHANGE 8 537 VNINDEX 11 1161 2.4.2. Kết quả thử nghiệm a) Thử nghiệm với CSDL ISTANBUL STOCK EXCHANGE Hình 2.1 biểu diễn 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 11
14. Hình 2.1. 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 Hình 2.2 và Hình 2.3 biểu diễn kết quả so sánh số luật và thời gian thực hiện của phương pháp mờ hóa khoảng cách thời gian (A) với phương pháp chia khoảng khoảng cách thời gian (B). Khoảng thời gian trong phương pháp chia khoảng (B) được chia đều thành 3 khoảng, các giá trị của khoảng cách thời gian nhận giá trị 1 nếu thuộc khoảng, ngược lại nhận giá trị 0. Hình 2.2. 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 Hình 2.3. 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 Kết luận Chƣơng 2 Trong chương này luận án đã trình bày giải pháp phát hiện các luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian bằng cách đề xuất 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ờ trong các CSDL như vậy. Thuật toán đó được gọi là FTQ. Theo thuật toán này, các thuộc tính định lượng và khoảng cách thời gian xảy ra giữa các giao dịch đều được mờ hóa . Thuật toán FTQ được phát triển từ ý tưởng thuật toán Apriori (Agrawal, Srikant and others, 1994), một chuỗi phổ biến độ dài k nhận được bằng cách liên kết hai chuỗi phổ biến độ dài k-1. Chương 12
15. này cũng trình bày kết quả thử nghiệm thuật toán FTQ trên các CSDL thực, so sánh với phương pháp chia khoảng tương ứng và phân tích ý nghĩa của luật thu được. Với việc lựa chọn các hàm thành viên một cách thích hợp, thuật toán FTQ trở thành thuật toán phát hiện luật kết hợp hoặc luật kết hợp mờ với khoảng cách thời gian là những số chính xác tương ứng trong các CSDL giao dịch hoặc CSDL định lượng cùng có yếu tố thời gian. Hơn nữa khi CSDL định lượng có yếu tố thời gian suy biến thành CSDL giao dịch có yếu tố thời gian, khi đó mỗi thuộc tính được mờ hóa thành 1 tập mờ tương ứng và các hàm thành viên chỉ nhận các giá trị là 1 hoặc 0, thuật toán này trở thành thuật toán phát hiện luật kết hợp với khoảng cách thời gian mờ. CHƯƠNG 3. 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 Trong chương 1, luận án đã xác định vấn đề cần được nghiên cứu về phát hiện mẫu chuỗi cố điển trong các CSDL chuỗi định lượng có yếu tố thời gian. Ở chương này, luận án sẽ trình bày giải pháp giải quyết vấn đề cần nghiên cứu đó. Cụ thể trong chương này, luận án sẽ trình bày thuật toán phát hiện mẫu chuỗi có 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 định lượng có yếu tố thời gian. Các mẫu chuỗi tìm được khi đó được gọi là mẫu chuỗi mờ với khoảng cách thời gian mờ. Vấn đề phát hiện mẫu chuỗi có 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 định lượng có yếu tố thời gian đã được giải quyết theo cách tiếp cận từ đơn giản đến phức tạp. Cách tiếp cận bắt đầu bằng việc nghiên cứu giải quyết bài toán phát hiện mẫu chuỗi với khoảng cách thời gian xác định [CT1] trong các CSDL giao dịch có yếu tố thời gian, tiếp theo là giải quyết bài toán phát hiện mẫu chuỗi mờ với khoảng cách thời gian xác định [CT6] trong các CSDL chuỗi định lượng có yếu tố thời gian và cuối cùng là phát hiện mẫu chuỗi cổ điền mờ với khoảng cách thời gian mờ trong các CSDL như vậy và kết quả nghiên cứu giải quyết bài toán này đã được đăng trên tạp chí Cybernetics and Information Technologies [CT5]. Chương này tập trung trình bày kết quả nghiên cứu của bài báo [CT5]. 3.1. Giới thiệu Phát hiện mẫu chuỗi là hướng nghiên cứu và ứng dụng quan trọng trong lĩnh vực khai phá dữ liệu. Phát hiện mẫu chuỗi từ CSDL chuỗi giao dịch được giới thiệu lần đầu vào năm 1995 (Agrawal, Srikant and others, 1995). Vấn đề phát hiện các mẫu chuỗi với khoảng cách thời gian xảy ra giữa các mục của cùng một đối tượng trong các CSDL chuỗi giao dịch đã được nghiên cứu trong (Yoshida et al., 2000; Chen, Chiang and Ko, 2003). Trong (Chen, Chiang and Ko, 2003), các mẫu chuỗi có dạng 〈 〉, trong đó a, b, c là mục, là các phạm vi thời gian của khoảng cách thời gian giữa các giao dịch trong chuỗi và được gọi là mẫu chuỗi với khoảng cách thời gian. Nhằm khắc phục hiện tượng “sắc nét” của việc chia khoảng thời gian (time range) tại các điểm gần ranh giới các khoảng chia như trong (Chen, Chiang and Ko, 2003), nghiên cứu (Chen and Huang, 2005) đã đề xuất và giải quyết vấn đề phát hiện các mẫu chuỗi với khoảng cách thời gian mờ từ các CSDL chuỗi giao dịch dựa trên việc chuyển khoảng cách thời gian thành các tập mờ. Các mẫu chuỗi trong nghiên cứu (Chen and Huang, 2005) đã biểu diễn mối quan hệ giữa các sự kiện dạng 〈 〉, trong đó a, b, c là các mục còn Short, Long là các tập mờ gắn với khoảng cách thời gian giữa các giao dịch trong chuỗi. Mục đích của chương này đề xuất và phát hiện mẫu chuỗi dạng tổng quát đó là mẫu chuỗi mờ với khoảng thời gian mờ. Đây là vấn đề thứ 2 đặt ra của luận án. Các mẫu chuỗi này có dạng 〈 〉, trong đó là các tập mờ gắn với các thuộc tính a, b, c và Short, Long là các tập mờ của khoảng cách thời gian. Từ các mẫu chuỗi này, ta có thể phát hiện các luật dạng “Nếu một khách hàng mua mặt hàng a với số lượng Ít và mặt hàng b với lượng Nhiều sau thời gian Short thì khách hàng đó sẽ mua mặt hàng c một lượng TB với thời gian Long”. Ý tưởng chính của thuật toán FSPFTIM được đề xuất trong chương 13
16. này là sử dụng lý thuyết mờ để chuyển đổi các thuộc tính định lượng, khoảng cách thời gian thành các khái niệm mờ; tìm chuỗi có độ dài k bằng cách liên kết 2 chuỗi phổ biến có độ dài k- 1 theo cách giống như thuật toán Apriori (Agrawal, Srikant and others, 1994; Chen and Huang, 2005) , từ đó tìm ra tất cả các mẫu chuỗi mờ với khoảng cách thời gian mờ. 3.2. Một số khái niệm cơ bản Định nghĩa 3.1 Gọi I={ } là tập các thuộc tính, s = 〈 〉 là một chuỗi định lượng có yếu tố thời gian, trong đó I là thuộc tính (1 k n), ( ≥0) là thời điểm tương ứng với xảy ra, với 2 k n và ( ) = , nhận giá trị số hoặc phân loại. Một CSDL chuỗi định lượng có yếu tố thời gian QSD là tập tất cả các chuỗi định lượng có yếu tố thời gian. Định nghĩa 3.2 Gọi { } là tập các tập mờ gắn với các thuộc tính của I, { } là tập các tập mờ gắn với thuộc tính (k=1, 2 , u), với là tập mờ thứ j (1≤ j≤ ), là số lượng tập mờ gắn với thuộc tính , được gọi là thuộc tính mờ. Mỗi tập mờ có một hàm thành viên tương ứng : X [0,1]. Chuỗi fs = 〈 〉 được gọi là chuỗi mờ có yếu tố thời gian, trong đó (1≤ i≤ n) là một tập mờ, là giá trị của hàm thành viên của ( ). CSDL chuỗi mờ có yếu tố thời gian FSD là tập các chuỗi mờ có yếu tố thời gian. Định nghĩa 3.3 Gọi LT={ | j=1,2, ,p} là tập các tập mờ gắn với khoảng cách thời gian, là hàm thành viên của tập mờ (Hu, Tzeng and Chen, 2004). Khi đó, α = 〈 〉 được gọi là chuỗi mờ với khoảng cách thời gian mờ nếu (1≤i≤r) là tập mờ và LT (1≤i≤r-1). Chuỗi α có độ dài r kí hiệu là r-chuỗi mờ với khoảng cách thời gian mờ (r-fuzzy sequential pattern with fuzzy time-intervals). Định nghĩa 3.4 Một chuỗi mờ với khoảng cách thời gian mờ = 〈 〉 là chuỗi con của chuỗi mờ với khoảng cách thời gian mờ β = 〈 〉 khi và chỉ khi tồn tại số nguyên w thỏa mãn với i|1≤i≤k-1 và . Trong trường hợp k=1 thì . Định nghĩa 3.5 Cho chuỗi mờ S = 〈 〉 và chuỗi mờ với khoảng cách thời gian mờ α = 〈 〉, ta có các định nghĩa sau: Độ hỗ trợ của chuỗi S đối với α, kí hiệu , được xác định như sau: { (3.1) (∏ ) { ( )} Chuỗi mờ B = 〈 〉 là chuỗi con của chuỗi mờ S=〈 〉 nếu tồn tại r số nguyên để | và . Độ hỗ trợ của chuỗi mờ S đối với α, kí hiệu SupS(α), là giá trị lớn nhất của các chuỗi B thuộc S đối với α: ( ) (3.2) Độ hỗ trợ của chuỗi mờ với khoảng cách thời gian mờ α, kí hiệu Sup(α), là giá trị trung bình của độ hỗ trợ của các chuỗi giao dịch mờ trong FSD đối với α. 14
17. ∑ ( ) (3.3) trong đó là chuỗi mờ thứ i trong FSD, NS là số lượng các chuỗi mờ của FSD. Một mẫu chuỗi mờ với khoảng cách thời gian mờ là chuỗi mờ với khoảng cách thời gian mờ có độ hỗ trợ không nhỏ hơn độ hỗ trợ cực tiểu min_sup cho trước. Tính chất 1: Chuỗi con của chuỗi mờ với khoảng cách thời gian mờ phổ biến thì cũng phổ biến. Tính chất 2: Mọi chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k đều là kết quả của phép kết hợp hai chuỗi mờ với khoảng cách thời gian mờ phổ biến độ dài k-1. 3.3. Thuật toán phát hiện mẫu chuỗi mờ với khoảng cách thời gian mờ 3.3.1. Bài toán đặt ra Cho trước CSDL định lượng có yếu tố thời gian QSD, độ hỗ trợ cực tiểu min_sup, tập mờ về khoảng cách thời gian LT cùng các hàm thành viên tương ứng, tập các tập mờ FE của các thuộc tính định lượng của QSD cùng các hàm thành viên tương ứng. Bài toán đặt ra: Phát hiện các mẫu chuỗi mờ với khoảng cách thời gian mờ trong CSDL định lượng có yếu tố thời gian QSD. 3.3.2. Ý tưởng thuật toán Đầu tiên, các thuộc tính định lượng trong QSD được chuyển thành các tập mờ. Tiếp theo, các chuỗi giao dịch trong QSD được chuyển đổi thành các chuỗi giao dịch mờ dựa trên các tập mờ và các hàm thành viên tương ứng để tạo ra CSDL chuỗi mờ FSD. Tiếp đến, thuật toán FSPFTIM được áp dụng để tìm các mẫu chuỗi mờ với khoảng cách thời gian mờ. Thuật toán này được phát triển dựa trên ý tưởng thuật toán Apriori. Thuật toán FSPFTIM thực hiện sinh tập các chuỗi ứng cử viên độ dài 1, , sau đó tính độ hỗ trợ cho các chuỗi thuộc và bổ sung các chuỗi ứng viên thỏa mãn độ hỗ trợ cực tiểu min_sup vào tập các mẫu chuỗi mờ với khoảng cách thời gian mờ độ dài 1, . Tiếp theo, lần lượt các tập chuỗi ứng viên và tập mẫu chuỗi mờ với khoảng cách thời gian mờ độ dài 2, , được sinh ra. Quá trình sinh như vậy được thực hiện cho đến khi tập chuỗi ứng cử viên là rỗng ( =) Kết quả trả lại là tập tất cả các chuỗi mờ với khoảng cách thời gian mờ thuộc các tập với k>1 3.3.3. Thuật toán FSPFTIM Thuật toán được mô tả như Error! Reference source not found Thuật toán 3.1. Thuật toán FSPFTIM Input: - CSDL chuỗi định lượng có yếu tố thời gian QSD; - Độ hỗ trợ cực tiểu min_sup; - Tập các tập mờ FE và các hàm thành viên tương ứng với các thuộc tính trong QSD; - Tập LT và các hàm thành viên tương ứng về khoảng cách thời gian. Output: Tập các mẫu chuỗi mờ với khoảng cách thời gian mờ. FSPFTIM { 1. Tạo CSDL chuỗi mờ có yếu tố thời gian FSD từ CSDL QSD 2. {fe| fe là thuộc tính mờ của FSD} 3. { |Sup( )≥min_sup} 4. ; 15
18. 5. for each do { 6. for each do { 7. for each ltd LT do { 8.  *ltd* ; 9. add to ; 10. } 11. } 12. } 13. for each do { 14. Tính độ hỗ trợ của (Sup( )); 15. } 16. { |Sup( ) ≥min_sup} 17. for (k>2; ≠;k++){ 18. fuzzy_apriori_gen( ); 19. for each do { 20. Tính độ hỗ trợ của (Sup( )); 21. } 22. { |Sup( ) ≥min_sup} 23. } 24. return ⋃ ; 25. } 3.3.4. Tính đúng đắn và tính đầy đủ của thuật toán Định lý 3.1. Thuật toán FSPFTIM là đúng đắn và đầy đủ. 3.3.5. Độ phức tạp thuật toán Theo cách tính như trong (Tan et al., 2005), độ phức tạp của thuật toán FSPFTIM là: 2 2 ∑ O(N.l.h +M.N.l.h + | | . ( ) |LT| + | | ( ) | |) 3.3.6. Trường hợp suy biến của mẫu chuỗi mờ với khoảng cách thời gian mờ Định lý 3.2: Thuật toán FSPFTIM có thể tìm được các mẫu chuỗi 〈 〉 và 〈 〉 3.4. Thử nghiệm thuật toán 3.4.1. Dữ liệu thử nghiệm Bảng 3.1. Dữ liệu thử nghiệm S100I1000T3D341K và Online Retail_France Số lƣợng Số lƣợng Số lƣợng Độ dài trung Độ dài trung CSDL thuộc tính giao dịch chuỗi bình giao dịch bình chuỗi (I) (D) (S) (T) S100I1000T3D341K 1000 341 100 29.3 3.41 Online Retail_France 1523 365 87 22.8 4.20 3.4.2. Kết quả thử nghiệm 3.4.2.1. 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 và giữa thời gian chạy của thuật toán với min_sup trong trường hợp số phân hoạch thuộc tính định lượng khác nhau. . 16
19. (a) (b) Online Retail_France Online Retail_France Hình 3.1. 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 3.4.2.2. 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 và giữa thời gian chạy của thuật toán với min_sup trong trường hợp số phân hoạch khoảng cách thời gian khác nhau (a) (b) S100I1000T3D341K S100I1000T3D341K Hình 3.2. 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 3.4.2.3. So sánh số luật và thời gian thực hiện của phương pháp mờ hóa với phương pháp chia khoảng của khoảng cách thời gian Hình 3.3. 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 Kết luận Chƣơng 3 Trong chương này luận án đã trình bày việc phát hiện các mẫu chuỗi mờ với khoảng cách thời gian mờ trong các CSDL chuỗi định lượng có yếu tố thời gian. Thuật toán phát hiện các 17
20. mẫu chuỗi như vậy được gọi là thuật toán FSPFTIM. Trong thuật toán này, các thuộc tính định lượng cũng như khoảng cách thời gian xảy ra giữa các giao dịch trong chuỗi đều được mờ hóa. Thuật toán được phát triển dựa trên thuật toán Apriori. Thuật toán là đúng đắn và đầy đủ. Độ phức tạp tính toán của thuật toán cũng được chỉ ra. Luận án cũng đã tiến hành thực nghiệm thuật toán trên tập dữ liệu thực. Kết quả thực nghiệm cho thấy tính đúng đắn và khả thi của thuật toán được đề xuất. Kết quả thực nghiệm được so sánh với phương pháp chia khoảng tương ứng. CHƯƠNG 4. 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. Chương 1 xác định vấn đề sẽ được nghiên cứu trong luận án này về phát hiện các luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Các luật được phát hiện khi đó được gọi là luật chuỗi chung mờ với khoảng cách thời gian mờ. Chương này sẽ trình bày chi tiết về thuật toán phát hiện các luật chuỗi chung như vậy. Thuật toán đó được gọi là IFERMiner. 4.1. Giới thiệu Luật chuỗi gồm 2 kiểu là luật chuỗi và luật chuỗi chung (Fournier-Viger et al., 2017). Ở kiểu luật thứ nhất, các phần tiền đề và hệ quả đều thuộc vào cùng một mẫu chuỗi (Agrawal, Srikant and others, 1995). Việc phát hiện các luật chuỗi kiểu tương tự như cách tiếp cận phát hiện các luật kết hợp, tức là cũng bao gồm 2 giai đoạn, ở giai đoạn đầu là tìm các mẫu chuỗi và ở giai đoạn 2 là sinh các luật chuỗi từ các mẫu chuỗi tìm được. Khác với các luật chuỗi, luật chuỗi chung được đề cập sau (Fournier-Viger et al., 2010; Fournier-Viger, Nkambou and Tseng, 2011; Fournier-Viger, Gueniche, et al., 2014). Các luật chuỗi chung biểu diễn mối quan hệ của 2 tập các mục không được sắp thứ tự (Fournier-Viger et al., 2010; Fournier-Viger, Nkambou and Tseng, 2011; Fournier-Viger, Gueniche, et al., 2014), ở đó các mục ở phần tiền đề phải xảy ra trước tất cả các mục ở phần hệ quả của luật. Luật chuỗi chung có dạng { } ⟹ { }, có nghĩa “Nếu một khách hàng đã mua mặt hàng a và mặt hàng b thì khách hàng đó sẽ mua mặt hàng c và d sau đó” với việc mua a và mua b không cần xảy ra theo trình tự thời gian, mua c và d cũng không cần xảy ra theo trình tự thời gian nhưng phải sau thời điểm mua a và mua b. Trong thực tế, việc phát hiện các luật chuỗi chung từ CSDL chuỗi định lượng có yếu tố thời gian là hết sức cần thiết. Nghiên cứu [CT8] đã đề xuất và giải quyết vấn đề phát hiện luật chuỗi chung mờ CSDL chuỗi định lượng. Luật phát hiện dạng { } ⟹ { } có nghĩa “Nếu một khách hàng mua mặt hàng a với lượng Ít và mua mặt hàng b một lượng Nhiều thì khách hàng đó sẽ mua c với lượng TB và d một lượng Ít sau đó”. Thuật toán FERMiner đã được đề xuất để phát hiện luật chuỗi chung mờ. Thuật toán FERMiner mờ hóa các thuộc tính định lượng, dựa trên ý tưởng thuật toán ERMiner (Fournier-Viger, Gueniche, et al., 2014) để phát hiện các luật chuỗi chung mờ. Mục đích của chương này đề xuất và phát hiện luật chuỗi chung dạng tổng quát đó là luật chuỗi chung có tính đến khoảng cách thời gian trong CSDL chuỗi định lượng có yếu tố thời gian, gọi là luật chuỗi chung mờ với khoảng cách thời gian mờ. Đây là vấn đề thứ 3 đặt ra của luận án. Các luật chuỗi chung mờ với khoảng cách thời gian mờ có dạng { } ⇒ { } , có nghĩa “Nếu một khách hàng mua mặt hàng a với lượng Ít và mua mặt hàng b một lượng Nhiều thì khách hàng đó sẽ mua c với lượng TB và d một lượng Ít sau khoảng thời gian Long”. Thuật toán IFERMiner được đề xuất để phát hiện các luật chuỗi chung mờ với khoảng cách thời gian mờ này. Trong thuật toán IFERMiner, lý thuyết mờ được sử dụng để mờ hóa các thuộc tính định lượng cũng như khoảng cách thời gian và dựa trên ý tưởng của 18
21. thuật toán ERMiner (Fournier-Viger, Gueniche, et al., 2014): sử dụng các lớp tương đương và tạo ra các luật chuỗi chung bằng cách hợp nhất 2 luật chuỗi chung đã tìm được. 4.2. Một số khái niệm cơ bản Định nghĩa 4.1 Gọi I={ } là tập các thuộc tính, là quan hệ thứ tự toàn phần trên các thuộc tính trong I và i1 i2 , iu, 〈 〉 s = là một chuỗi định lượng, trong đó I (1 k n), là giá trị của tại thời điểm ( nhận giá trị số hoặc phân loại), với 2 k n; ( , , ) được gọi là một phần tử của chuỗi định lượng s. Trong một chuỗi, các phần tử xảy ra cùng thời điểm được sắp theo quan hệ của các thuộc tính. Chuỗi định lượng s có thể được biểu diễn bằng dạng s = 〈 〉 , trong đó = {( , ), ( , ), ( , ), , ( , )} và tất cả các thuộc tính trong đều xảy ra tại thời điểm . gọi là một giao dịch. Error! Reference source not found. là ví dụ biểu diễn một CSDL chuỗi định lượng có yếu tố thời gian. Định nghĩa 4.2 Gọi FE = { } là tập các tập mờ gắn với các thuộc tính trong I, { } là tập các tập mờ của thuộc tính (k=1, 2 , u), trong đó là tập mờ thứ j (1≤ j≤ ), là số lượng các tập mờ của . Mỗi tập mờ có một hàm thành viên tương ứng : X [0,1]. Chuỗi fs = 〈 〉 được gọi là chuỗi giao dịch mờ, trong đó FE (1≤j≤n) là một tập mờ và được gọi là thuộc tính mờ; là giá trị của hàm thành viên của ứng với giá trị , tức là ; ( , , ) được gọi là phần tử của chuỗi mờ. Định nghĩa 4.3 Luật FCSI, kí hiệu ⇒ , là một luật chuỗi chung mờ với khoảng cách thời gian mờ nếu thỏa mãn: X Y = , trong đó X, Y là các tập thuộc tính và X, Y ≠ ; X và Y cùng xuất hiện trong cùng chuỗi giao dịch mờ; Y xuất hiện sau X một thời gian mờ lt (lt LT, LT là tập các tập mờ của khoảng cách thời gian) Định nghĩa 4.4 Giả sử rfs = 〈 〉 là chuỗi giao dịch mờ được viết gọn của chuỗi fs, tập thuộc tính mờ X xuất hiện hoặc được chứa trong chuỗi giao dịch mờ fs nếu X , ở đây . Luật FCSI r = X ⇒ Y được chứa trong fs nếu X , với , Y , h và g ≥ i hoặc nếu f ≥ h và g > i. Định nghĩa 4.6 Cho chuỗi giao dịch mờ fs = 〈 〉, luật FCSI r = ⇒ và . Độ hỗ trợ của fs đối với tập X được xác định như sau: ( ∏ ) (4.1) Độ hỗ trợ của tập X trong CSDL chuỗi mờ có yếu tố thời gian FSD được xác định bởi: 19
22. ∑ (4.2) | | Độ hỗ trợ của fs đối với r được xác định bởi: (4.3) ( ∏ ) ở đây và ( ), là giá trị hàm thành viên của tập mờ lt tại giá trị Độ hỗ trợ của luật r trong CSDL FSD được xác định là: ∑ (4.4) | | Độ tin cậy của luật FCSI r = X ⇒ Y được xác định bởi: (4.5) Định nghĩa 4.7 Gọi min_sup, min_conf [0,1] ([0%, 100%]) tương ứng là các ngưỡng độ hỗ trợ cực tiểu và độ tin cậy cực tiểu được xác định bởi người sử dụng, FSD là CSDL chuỗi mờ có yếu tố thời gian. Luật FCSI r được gọi là phổ biến nếu sup(r) ≥ min_sup; Luật FCSI r được gọi là tin cậy nếu conf(r) ≥ min_conf. Luật r được gọi là luật FCSI valid nếu nó là luật phổ biến và tin cậy. Các khái niệm tiếp theo được phát triển dựa trên các khái niệm trong (Fournier-Viger et al., 2010; Fournier-Viger, Nkambou and Tseng, 2011; Fournier-Viger, Gueniche, et al., 2014). Định nghĩa 4.8 (các lớp tương đương mờ trái/phải và các phép hợp nhất trái/phải): Cho CSDL chuỗi mờ FSD, là tập tất cả các luật FCSI phổ biến, tập tất cả các thuộc tính mờ của các thuộc tính trong FSD, LT là tập các tập mờ gắn với khoảng cách thời gian. Một lớp tương đương mờ trái với khoảng cách thời gian mờ lt trên , được kí hiệu là , được xác định như sau: = { ⇒ | W, Y | | , i là số tự nhiên, lt LT}. Một cách tương tự một lớp tương đương mờ phải với khoảng thời gian mờ lt trên , được kí hiệu là = { ⇒ | X, W | | , i là số tự nhiên, lt LT}. Giả sử hai luật FCSI , , = ⇒ , = ⇒ và | | | | hép hợp nhất trái của r1, r2 là một quá trình hợp nhất và để nhận được luật r = ⇒ . Một cách tương tự giả sử hai luật FCSI , , = ⇒ , = ⇒ và | | | | phép hợp nhất phải của , là một quá trình hợp nhất và để nhận được luật r = ⇒ . Tính chất 1: Giả sử luật FCSI = ⇒ là phổ biến khi đó nếu X Y và = ⇒ cũng là luật FCSI phổ biến. Một cách tương tự nếu ⇒ là luật FCSI phổ biến và X Y thì ⇒ cũng là luật FCSI phổ biến. 20
23. Tính chất 2: Mọi luật FCSI phổ biến r = ⇒ , | | đều là kết quả hợp nhất trái của 2 luật FCSI , – lớp tương đương mờ trái với khoảng cách thời gian mờ lt. Một cách tương tự, mọi luật FCSI mờ phổ biến r = ⇒ , | | đều là kết quả hợp nhất phải của 2 luật FCSI , – lớp tương đương mờ phải với khoảng cách thời gian mờ lt. Từ hai tính chất trên, ta có nhận xét sau: Nhận xét: 1) Độ hỗ trợ của luật FCSI r sinh ra từ phép hợp nhất và luôn nhỏ hơn hoặc bằng độ hỗ trợ của , 2) Nếu độ hỗ trợ của luật FCSI r nhỏ hơn min_sup thì luật này không thể tham gia hợp nhất để tạo ra luật FCSI phổ biến mới. Nhận xét này được sử dụng để giảm bớt không gian tìm kiếm các luật FCSI phổ biến. Tương tự (Fournier-Viger, Gueniche, et al., 2014), một số luật FCSI có thể được tìm bằng vài cách khác nhau thông qua các phép hợp trái/phải với các thuộc tính mờ khác nhau. Để tránh sinh trùng lặp về luật, tương tự như giải pháp trong (Fournier-Viger, Gueniche, et al., 2014), phép hợp phải không được thực hiện sau phép hợp trái và áp đặt thứ tự quan hệ toàn phần cho các thuộc tính mờ trong ở nguyên nhân và hệ quả của luật, chỉ thực hiện phép hợp trái (hoặc hợp phải nếu phần hệ quả có chung các thuộc tính cuối theo thứ tự quan hệ toàn phần (Fournier-Viger, Gueniche, et al., 2014). 4.3. Thuật toán phát hiện luật chuỗi chung mờ với khoảng cách thời gian mờ 4.3.1. Bài toán đặt ra Cho trước CSDL chuỗi định lượng có yếu tố thời gian QSD; min_sup, min_conf lần lượt là các độ hỗ trợ cực tiểu và độ tin cậy cực tiểu do người sử dụng xác định; tập mờ của khoảng cách thời gian LT cùng các hàm thành viên tương ứng; tập các tập mờ FE của các thuộc tính định lượng của QSD cùng các hàm thành viên tương ứng. Vấn đề: phát hiện các luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong CSDL QSD. 4.3.2. Thuật toán IFERMiner Thuật toán IFERMiner được mô tả trong Error! Reference source not found. Thuật toán 4.1. Thuật toán IFERMiner Input: - CSDL chuỗi định lượng có yếu tố thời gian QSD; - Độ hỗ trợ cực tiểu và độ tin cậy cực tiểu min_sup, min_conf; - Tập các tập mờ FE và các hàm thành viên tương ứng với các thuộc tính trong QSD; - Tập LT và các hàm thành viên tương ứng về khoảng cách thời gian. Output: Frules – tập tất cả các luật FCSI valid. IFERMiner{ 1. Frules 2. Duyệt QSD để tạo CSDL mờ có yếu tố thời gian FSD. 3. foreach lt LT do { 4. fleftStore_lt ; 5. Tính , tập các lớp tương đương trái với khoảng cách thời gian mờ lt có kích cỡ 1*1 và sinh các luật FCSI valid cỡ 1*1; 6. for each lớp tương đương trái với khoảng cách thời gian mờ lt, H do { 21
24. 7. fleftSearch(H, Frules) 8. } 9. for each lớp tương đương phải với khoảng cách thời gian mờ lt, J do { 10. frighSearch(J, Frules, fleftStore_lt) 11. } 12. for each lớp tương đương trái với khoảng cách thời gian mờ lt, K fleftStore_lt do { 13. fleftSearch(K, Frules) 14. } 15. } 16. return Frules 17. } 4.3.3. Tính đúng đắn và đầy đủ Định lý 4.1: Thuật toán IFERMiner là đúng đắn và đầy đủ. 4.3.4. Độ phức tạp của thuật toán IFERMiner Định lý 4.2: Độ phức tạp tính toán của thuật toán IFERMiner là đa thức phụ thuộc vào N: tổng số chuỗi trong CSDL chuỗi định lượng có yếu tố thời gian QSD, m: số lượng giao dịch trung bình của một chuỗi, d: độ dài trung bình của giao dịch trong QSD, h: số lượng tập mờ trung bình được liên kết với thuộc tính định lượng trong QSD và |LT|: số lượng tập mờ của các khoảng thời gian trong LT Chứng minh: Độ phức tạp tính toán của thuật toán IFERMiner C được phân tích như sau: | | Trong đó: : Độ phức tạp tính toán để tạo CSDL chuỗi mờ có yếu tố thời gian FSD từ CSDL chuỗi định lượng có yếu tố thời gian QSD. : Độ phức tạp tính toán để tính toán các lớp tương đương mờ trái/phải với khoảng cách thời gian mờ lt có kích thước 1*1 và để sinh ra các luật FCSI valid có kích thước 1*1. : Độ phức tạp tính toán của thủ tục fleftSearch trên - tập tất cả các lớp tương đương mờ trái với khoảng cách thời gian mờ lt có kích thước 1*1. : Độ phức tạp tính toán của thủ tục frightSearch trên - tập tất cả các lớp tương đương mờ phải với khoảng cách thời gian mờ lt có kích thước 1*1 : Độ phức tạp tính toán của thủ tục fleftSearch trên fleftStore - tập tất cả các lớp tương đương mờ trái với khoảng cách thời gian mờ lt được sinh ra bởi thủ tục frightSearch trên . 4.3.5. 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ờ Định lý 4.3: Thuật toán IFERMiner có thể tìm được các luật ⟹ với X, Y là các tập mục. 4.4. Thử nghiệm thuật toán 4.4.1. Dữ liệu thử nghiệm Bảng 4.1. Dữ liệu thử nghiệm thuật toán IFERMiner Số lƣợng Số lƣợng Số lƣợng Độ dài trung Độ dài trung thuộc tính giao dịch chuỗi giao bình giao bình của Dữ liệu thử nghiệm (I) (D) dịch dịch chuỗi giao (S) (T) dịch Online Retail_France 1523 365 87 21.38 95.88 22
25. QtyT40I10D100K 100 10000 100 4.26 420 4.4.2. Kết quả thử nghiệm 4.4.2.1. Mối quan hệ giữa số lượng các luật được sinh ra với độ hỗ trợ cực tiểu min_sup và độ tin cậy cực tiểu min_conf. Online Retail France (a) 1500 min_conf=70 1000 % min_conf=73 Số luật Số 500 % min_conf=76 % 0 min_conf=79 3.1% 3.3% 3.5% 3.7% 3.9% 4.1% 4.3% 4.5% % min_sup Hình 4.1. Mối quan hệ giữa số lượng các luật FCSI valid với min_sup và min_conf 4.4.2.2. Mối quan hệ giữa thời gian thực hiện thuật toán với độ hỗ trợ cực tiểu min_sup và độ tin cậy cực tiểu min_conf Online Retail France (a) 3 2.5 min_conf=70% 2 min_conf=73% 1.5 min_conf=76% 1 0.5 min_conf=79% Thời (giây) gian Thời 0 min_conf=82% 3.1% 3.3% 3.5% 3.7% 3.9% 4.1% 4.3% 4.5% min_conf=85% min_sup Hình 4.2. Mối quan hệ giữa thời gian thực hiện thuật toán với min_sup và min_conf 4.4.2.3. So sánh số luật và thời gian thực hiện của phương pháp mờ hóa với phương pháp chia khoảng của khoảng cách thời gian Hình 4.3. 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 Kết luận Chƣơng 4 Chương 4 tập trung trình bày thuật toán phát hiện các luật chuỗi chung mờ với các khoảng cách thời gian mờ trong các CSDL định lượng có yếu tố thời gian và được gọi là IFERMiner. Phương pháp mờ hóa các thuộc tính định lượng cũng như các khoảng cách thời gian là tương 23
26. tự như hai chương trước đó. Thuật toán IFERMiner được phát triển từ ý tưởng của thuật toán ERMiner để phát hiện các luật chuỗi chung trong các CSDL giao dịch không có yếu tố thời gian. Cụ thể thuật toán IFERMiner cũng được xây dựng dựa trên các lớp tương đương mờ trái, mờ phải của các luật chuỗi chung mờ phổ biến với khoảng cách thời gian mờ như nhau và các phép hợp nhất trái, phải trên các lớp tương đương này. Thuật toán IFERMiner là đúng đắn và đầy đủ. KẾT LUẬN VÀ KIẾN NGHỊ Luận án đã đạt đƣợc những kết quả chính sau: NCS đã hoàn thành mục tiêu của luận án. NCS đã tập trung nghiên cứu giải quyết các vấn đề về phát hiện các luật kết hợp và mẫu chuỗi, luật chuỗi chung có tính đến khoảng cách thời gian tương ứng trong các CSDL định lượng và CSDL chuỗi định lượng có yếu tố thời gian. Cụ thể luận án đã đề xuất nghiên cứu và giải pháp giải quyết 3 bài toán sau: 1. Đề xuất và giải quyết bài toán về phát hiện luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian. Các luật phát hiện được khi đó được gọi là luật kết hợp mờ với khoảng cách thời gian mờ. Thuật toán FTQ đã được NCS đề xuất nhằm phát hiện những luật như vậy. Thuật toán sử dụng phương pháp mờ hóa các thuộc tính định lượng sau đó thực hiện dựa trên ý tưởng của thuật toán Apriori. Việc thực nghiệm cho thấy thuật toán nó phù hợp với lý thuyết về luật kết hợp, trong đó nhất là tính chất đóng xuống (hay tính chất Apriori của các tập phổ biến). Các luật phát hiện được cho thấy ý nghĩa ứng dụng thực tiễn của chúng. 2. Đề xuất và giải quyết bài toán về phát hiện mẫu chuỗi có tính đến khoảng cách thời gian giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Các mẫu chuỗi như vậy được gọi là mẫu chuỗi mờ với khoảng cách thời gian mờ. Thuật toán phát hiện các mẫu chuỗi mờ với khoảng cách thời gian mờ được gọi là FSPFTIM. Thuật toán này là đúng đắn và đầy đủ. Độ phức tạp tính toán của nó đã được chỉ ra trong luận án. Việc thực nghiệm thuật toán trên các tập dữ liệu thực đã cho thấy thuật toán phù hợp với lý thuyết trong đó nhất là tính chất đóng xuống của các mẫu phổ biến. Các mẫu chuỗi phát hiện được là phù hợp và có ý nghĩa ứng dụng thực tiễn. 3. Đề xuất và giải quyết bài toán về phát hiện luật chuỗi chung có tính đến khoảng cách thời gian giữa các giao dịch trong CSDL chuỗi định lượng có yếu tố thời gian. Các luật chuỗi phát hiện được khi đó gọi là luật chuỗi chung mờ với khoảng cách thời gian mờ. Thuật toán được đề xuất để phát hiện các luật chuỗi chung như vậy được gọi là IFERMiner. Thuật toán này cũng là đúng đắn và đầy đủ. Độ phức tạp tính toán của thuật toán cũng được đưa ra và độ phức tạp là đa thức. Hƣớng nghiên cứu trong tƣơng lai: Các thuật toán phát hiện các luật kết hợp mờ và mẫu chuỗi mờ với khoảng cách thời gian mờ tương ứng trong các CSDL định lượng có yếu tố thờ gian và CSDL chuỗi định lượng có yếu tố thời gian đều được phát triển dựa trên thuật toán Apriori, một thuật toán được đánh giá có hiệu quả ở mức trung bình so với các thuật toán phát hiện luật kết hợp khác. Một trong nhưng hướng nghiên cứu sau luận án này của chúng tôi là phát triển các thuật toán hiệu quả hơn để phát hiện các luật kết hợp mờ cũng như mẫu chuỗi mờ với khoảng cách thời gian. Các mẫu chuỗi cũng như các luật chuỗi chung chỉ biểu diễn mối quan hệ của các giao dịch do một đối tượng thực hiện, một hướng nghiên cứu khác được chúng tôi ưu tiên hơn là nghiên cứu phát hiện một loại mẫu chuỗi mới cũng như loại luật chuỗi chung mới có thể biểu diễn được mối quan hệ giữa các giao địch được thực hiện bởi các đối tượng khác nhau miễn là các giao dịch đứng trước trong mẫu chuỗi hoặc trong phần tiền đề của luật phải được xảy ra tương ứng trước các giao địch đứng sau trong mẫu chuỗi hoặc phần hệ quả của luật chuỗi chung. 24
27. DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ [CT1] Trương Đức Phương, Đỗ Văn Thành, “Phát hiện luật chuỗi liên kết các giao dịch từ cơ sở dữ liệu thời gian”, Kỷ yếu hội nghị khoa học công nghệ quốc gia lần thứ VII (FAIR „7), 2014, pp. 488-495 [CT2] Trương Đức Phương, Đỗ Văn Thành, “Phát hiện luật kết hợp liên kết chuỗi thời gian”, hội thảo quốc gia lần thứ 17: Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, 2014, pp. 257-262 [CT3] Truong Duc Phuong, Do Van Thanh, Nguyen Duc Dung, “Mining fuzzy time-interval association rules from temporal quantitative databases”, International Conference on Information and Convergence Technology for Smart Society Vol.2 No.1, 2016, pp 52- 58. [CT4] Truong Duc Phuong, Do Van Thanh, Nguyen Duc Dung, “An Effective Algorithm for Association Rules Mining from Temporal Quantitative Databases”, Indian Journal of Science and Technology, Vol 9(17), 2016. (Scopus*) [CT5] Truong Duc Phuong, Do Van Thanh, Nguyen Duc Dung, "Mining Fuzzy Sequential Patterns with Fuzzy Time-Intervals in Quantitative Sequence Databases." Cybernetics and Information Technologies, Vol 18 (2), 2018, pp. 3-19. (Scopus) [CT6] Trương Đức Phương, Đỗ Văn Thành, Nguyễn Đức Dũng “Phát hiện mẫu chuỗi mờ với khoảng cách thời gian được xác định từ cơ sở dữ liệu chuỗi định lượng”, hội thảo quốc gia lần thứ 21: Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, 2018, pp. 280-287 (ch3) [CT7] Trương Đức Phương, “Xây dựng mô hình dự báo chỉ số VN30 của thị trường chứng khoán Việt Nam”, hội thảo quốc gia lần thứ 21: Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, 2018, pp. 383-389 [CT8] Thanh Do Van, Phuong Truong Duc, “Fuzzy Common Sequential Rules Mining In Quantitative Sequence Databases”, Journal of Computer Science and Cybernetics, Vol 35(3), 2019, pp. 217-232 [CT9] Thanh Do Van, Phuong Truong Duc, “Mining Fuzzy Common Sequential Rules with Fuzzy Time-Interval in quantitative sequence databases”, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol 28 (6), 2020, pp. 957. (SCIE) * 25