Nghiên cứu các kỹ thuật khai phá mẫu dãy cho dữ liệu dãy

Bài báo giới thiệu và phân tích các kỹ thuật bằng cách phân loại các kỹ thuật theo hai nhóm tiếp cận chính: phương pháp tiếp cận dựa trên Apriori và phương pháp tiến cận phát triển mẫu. Trong bài báo cũng phân tích mở rộng các kỹ thuật khác nhau dựa trên các đặc tính quan trọng và thảo luận một số tồn tại đang được tập trung nghiên cứu.
Nội dung trích xuất từ tài liệu:
Nghiên cứu các kỹ thuật khai phá mẫu dãy cho dữ liệu dãy Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 NGHIÊN CỨU CÁC KỸ THUẬT KHAI PHÁ MẪU DÃY CHO DỮ LIỆU DÃY Quách Xuân Trưởng*, Nguyễn Văn Sự, Đinh Đức Hoàng Trường ĐH Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên TÓM TẮT Khai phá mẫu dãy là một nội dung quan trọng trong khai phá dữ liệu với nhiều ứng dụng rộng rãi như phân tích thị trường, phân tích mẫu truy cập web, phát hiện xâm nhập trong môi trường mạng, trong nghiên cứu DNA, dự đoán nhu cầu mua sắm của khách hàng,… Khai phá mẫu dãy là việc phát hiện các dãy con phổ biến trong cơ sở dữ liệu dãy. Kể từ khi được đề xuất bởi Agrawal và Srikant đến nay bài toán này đã thu hút được nhiều nghiên cứu và có nhiều kỹ thuật được đề xuất. Đầu tiên là thuật toán dựa trên nguyên lý Apriori, sau đó là các thuật toán mở rộng được phát triển cho các ứng dụng phức tạp. Bài báo giới thiệu và phân tích các kỹ thuật bằng cách phân loại các kỹ thuật theo hai nhóm tiếp cận chính: phương pháp tiếp cận dựa trên Apriori và phương pháp tiến cận phát triển mẫu. Trong bài báo cũng phân tích mở rộng các kỹ thuật khác nhau dựa trên các đặc tính quan trọng và thảo luận một số tồn tại đang được tập trung nghiên cứu. Từ khóa: Cơ sở dữ liệu dãy, khai phá mẫu dãy, phát triển mẫu, apriori, phân tích mẫu. GIỚI THIỆU* Khai phá mẫu dãy là phương pháp tìm kiếm các mẫu dãy có ích từ trong cơ sở dữ liệu lớn, nó phát hiện ra các dãy con phổ biến từ cơ sở dữ liệu dãy. Đây là một chủ đề thiết thực và quan trọng trong khai phá dữ liệu với nhiều ứng dụng như phân tích giao dịch mua bán của khách hàng, phân tích web-log, khai thác các dãy DNA, các dự báo khí tượng thủy văn hay phân tích các dữ liệu y học [12][13][14]. Khai phá mẫu dãy là xác định những mẫu mà sự xuất hiện của chúng trong cơ sở dữ liệu thỏa mãn mức hỗ trợ tối thiểu nào đó do người dùng định nghĩa. Với số lượng các mẫu có thể là rất lớn và với các yêu cầu và lợi ích khác nhau, bằng cách sử dụng ngưỡng tối thiểu thì các mẫu không thỏa mãn ngưỡng tối thiểu được xem là không có ý nghĩa và không cần xem xét đến làm cho quá trình khai phá sẽ hiệu quả hơn. MỘT SỐ KHÁI NIỆM CƠ BẢN Cho một tập I={i1, i2, …., im} gồm m phần tử và gọi là các item. Mỗi phần tử được kết hợp với một tập thuộc tính như giá trị, giá cả, lợi nhuận, thời gian,… giá trị trong thuộc tính A của phần tử i được kí hiệu bằng i.A. Một itemset là một tập con không rỗng các item và một itemset có lực lượng là k được gọi là kitemset. * Tel: 0989090832; Email: qxtruong@ictu.edu.vn Một dãy S= là một danh sách có thứ tự những itemset. Mỗi si (1≤i≤n) là một itemset, n là số lượng itemset. Kính thước của dãy bằng số lượng itemset có trong dãy. Chiều dài của dãy là tổng số item có trong dãy kí hiệu là l = n ∑s j =1 j . Dãy có chiều dài k còn gọi là k-sequence, ví dụ: S= là một 3-sequence có kính thước là 2. Chuỗi β= được gọi là dãy con của dãy ∝= hay chuỗi ∝ là dãy cha của dãy β, kĩ hiệu là β⊆∝, nếu tồn tại những số nguyên 1≤j1