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