Phát hiện luật kết hợp liên kết chuỗi thời gian từ cơ sở dữ liệu định lượng có yếu tố thời gian

Bài viết này nghiên cứu phát hiện các luật kết hợp thể hiện được mối quan hệ theo thời gian của các thời điểm xảy ra các sự kiện từ các cơ sở dữ liệu định lượng có yếu tố thời gian. Thuật toán tìm các luật như vậy được đề xuất dựa trên việc phát triển thuật toán Apriori kết hợp với việc mờ hóa khoảng cách thời gian giữa các thời điểm xảy ra sự kiện cũng như mờ hóa các thuộc tính định lượng.
Nội dung trích xuất từ tài liệu:
Phát hiện luật kết hợp liên kết chuỗi thời gian từ cơ sở dữ liệu định lượng có yếu tố thời gian 66 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI PHÁT HIỆN LUẬT KẾT HỢP LIÊN KẾT CHUỖI THỜI GIAN TỪ CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG CÓ YẾU TỐTỐ THỜI GIAN Trương Đức Phương1 Trường Đại học Thủ ñô Hà Nội Tóm tắt: tắt: Bài báo này nghiên cứu phát hiện các luật kết hợp thể hiện ñược mối quan hệ theo thời gian của các thời ñiểm xảy ra các sự kiện từ các cơ sở dữ liệu ñịnh lượng có yếu tố thời gian. Thuật toán tìm các luật như vậy ñược ñề xuất dựa trên việc phát triển thuật toán Apriori kết hợp với việc mờ hoá khoảng cách thời gian giữa các thời ñiểm xảy ra sự kiện cũng như mờ hoá các thuộc tính ñịnh lượng. Từ khoá: khai phá dữ liệu, luật kết hợp, cơ sở dữ liệu. 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ừ cơ sở dữ liệu tác vụ (hay nhị phân) và không có yếu tố thời gian ñã ñược Rakesh Agrawal cùng cộng sự ñề xuất lần ñầu năm 1993 [1] và ñến nay ñã nhận ñược rất nhiều kết quả nghiên cứu [2, 7, 9, 10, 13, 14]. Vấn ñề phát hiện các luật kết hợp từ cơ sở dữ liệu tác vụ có yếu tố thời gian ñược giới thiệu năm 1995 [11]. Các luật kết hợp phát hiện ñược khi ñó ñược gọi là luật chuỗi. Các luật chuỗi cho biết mối quan hệ giữa các tác vụ (hay sự kiện) xảy ra theo thứ tự thời gian của từng ñối tượng gây ra các tác vụ (hay sự kiện) ñó. Việc phát hiện các luật chuỗi ñã ñược nghiên cứu theo nhiều cách tiếp cận khác nhau và cũng ñã ñạt ñược nhiều kết quả [18, 24]. Bằng cách sử dụng lí thuyết tập mờ [5-6, 16] ñể chuyển giá trị của các thuộc tính trong cơ sở dữ liệu ñịnh lượng thành các tập mờ nhằm khắc phục tính thiếu tự nhiên và không hợp lí của cách chuyển các thuộc tính nhận giá trị ñịnh lượng thành các thuộc tính nhận giá trị nhị phân tại các ñiểm nút phân chia khi tìm các luật kết hợp từ các cơ sở dữ liệu ñịnh 1 Nhận bài ngày 15.8.2016; gửi phản biện và duyệt ñăng ngày 15.09.2016 Liên hệ tác giả: Trương Đức Phương; Email: tdphuong@daihocthudo.edu.vn TẠP CHÍ KHOA HỌC − SỐ 8/2016 67 lượng, luật kết hợp mờ ñã ñược ñề xuất [5-6, 16]. Kết quả nghiên cứu về phát hiện luật kết hợp mờ là rất phong phú và có thể tham khảo trong [5-6, 16, 17, 19, 20, 22]… 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 tác vụ (hay sự kiện) [3, 4, 21, 25]. Phản ánh mối quan hệ về thời gian xảy ra của các tác vụ trong luật kết hợp ñã ñược Yen - Liang Chen và cộng sự ñề xuất lần ñầu vào năm 2003 [3] bằng việc phân khoảng thời gian xảy ra của các tác vụ thành các ñoạn và sau ñó phát triển tiếp bằng việc mờ hoá các thuộc tính ñược ñề cập trongchúng [4]. Ý tưởng chính của nghiên cứu [4] có thể tóm tắt như sau: − Sử dụng lí thuyết tập mờ ñể mờ hoá khoảng cách thời gian giữa tác vụ liên tiếp trong chuỗi. − Tìm các mẫu chuỗi thời gian mờ phổ biến dạng (A, I1, B, I2, C) trong ñó A, B, C là các mục dữ liệu (hay thuộc tính), I1, I2 là các giá trị mờ tương ứng khoảng cách thời gian của các tác vụ. − Đề xuất một số thuật toán khác nhau gồm FTI - Apriori, FTI-PrefixSpan ñể tìm các chuỗi thời gian mờ phổ biến. Tuy nhiên nghiên cứu [4] chỉ ñề cập ñến việc phát hiện luật chuỗi thời gian ñối với cơ sở dữ liệu tác vụ chuỗi khách hàng, các giao dịch ñược xem xét theo từng khách hàng và các sự kiện chỉ có thể là xuất hiện hay không, chứ không áp dụng cho cơ sở dữ liệu ñịnh lượng có yếu tố thời gian ở ñó mỗi giao dịch gắn với một thời ñiểm xảy ra và các sự kiện xảy ra ñều kèm theo số lượng hoặc giá trị phân loại tương ứng. Nói cách khác nghiên cứu nêu trên chỉ nhằm phát hiện các luật có dạng Nếu khách hàng C mua mặt hàng A trong ngày hôm nay thì khách hàng này sẽ mua mặt hàng B trong ÍT ngày kế tiếp. Mục ñích của bài báo này là phát hiện luật kết hợp liên kết chuỗi thời gian mờ từ cơ sở dữ liệu ñịnh lượng có yếu tố thời gian, không có yếu tố khách hàng trong giao dịch. Cụ thể bài báo tập trung nghiên cứu phát hiện các luật có dạng Nếu một mặt hàng A ñược mua một lượng Ít ở thời ñiểm ngày hôm nay thì mặt hàng B sẽ ñược mua NHIỀU ở ÍT ngày kế tiếp. Luật này là phù hợp và có ý nghĩa thực tiễn. Tương tự như quá trình phát hiện luật kết hợp dựa vào các thuật toán Apriori, Charm hay Aclose, … [1, 2, 12], quá trình phát hiện luật kết hợp liên kết chuỗi thời gian mờ cũng ñược chia thành 2 giai ñoạn: Giai ñoạn 1 tìm các mẫu chuỗi liên kết thời gian mờ phổ biến và giai ñoạn 2 sinh ra các luật kết hợp dựa trên tập các mẫu chuỗi liên kết thời gian mờ phổ biến tìm ñược trong giai ñoạn 1 theo cách tương tự như [1, 2, 12]. Thuật toán ñược ñề xuất ñể giải quyết vấn ñề ñặt ra trong bài báo này ñược gọi là FTIQ-ARM. Thuật toán ñược xây dựng dựa trên việc cải tiến thuật toán Apriori [2], một thuật toán tìm tập phổ biến thông qua liên kết 2 chuỗi ñộ dài n-1 thành chuỗi ñộ dài n. 68 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI Phần còn lại của bài báo ñược cấu trúc như sau: Phần hai sẽ giới thiệu và ñề xuất một số khái niệm cơ bản cần thiết cho nghiên cứu tiếp theo. Phần ba trình bày bài toán ñặt ra và thuật toán tìm các mẫu thời gian mờ phổ biến, FTIQ-ARM. Minh hoạ thuật toán cũng ñược trình bày trong phần này. Cuối cùng, phần kết luận trình bày những ñóng góp nghiên cứu chủ yếu của bài báo. 2. MỘT SỐ KHÁI NIỆM CƠ BẢN Định nghĩa 1 [7]: Giả sử S ={s1,s2,…su} là tập thuộc tính, Ti ={s1(i),s2(i),…,su(i)} (1≤ i≤ n) là tập các giá trị của S tại thời ñiểm i, sk (i) là giá trị của thuộc tính sk tại thời ñiểm i (1≤k≤u) và nó ñược xem là một sự kiện, sk(i) ...