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 125 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à k- itemset. * 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à 1 n j j l s = =∑ . 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<j2<<jn<m sao cho b1⊆aj1, b2⊆aj2, , bm⊆ajm. Một cơ sở dữ liệu dãy là một tập hợp các bộ dữ liệu có dạng (sid, s), trong đó sid là định danh của dãy và s là dãy các itemset. Cho một cơ sở dữ liệu dãy D, độ hỗ trợ tuyệt đối của một mẫu tuần tự f là tổng số dãy trong D có chứa f, kí hiệu là supD(f)=|{Si∈D|f⊆Si}|. Độ hỗ trợ tương đối của f là tỉ lệ phần trăm dãy trong D chứa f. Ở đây, mức hỗ trợ tuyệt đối hoặc tương đối sẽ được sử dụng chuyển đổi qua lại, ký hiệu là sup(f). Như vậy vấn đề khai phá mẫu dãy là đi tìm tập toàn bộ các mẫu đối với một cơ sở dữ liệu dãy với một độ hỗ trợ tối thiểu min_sup cho trước. Một mẫu f được coi là phổ biến nếu độ hỗ trợ của nó lớn hơn hoặc bằng min_sup: sup(f)≥min_sup, khi đó f được gọi là mẫu dãy [12]. Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 126 CÁC PHƯƠNG PHÁP KHAI PHÁ MẪU DÃY Phát hiện các mẫu dãy phổ biến có thể được xem như là việc phát hiện luật kết hợp trên cơ sở dữ liệu thời gian. Các thuật toán khai phá mẫu dãy kế thừa nhiều từ các thuật toán khai phá luật kết hợp, trong đó sự khác biệt chính là trong khai phá mẫu dãy tìm kiếm các mẫu dãy liên tục (trong nhiều giao dịch) mà ở đó thứ tự của các item và itemset là rất quan trọng, trong khi luật kết hợp chỉ tìm kiếm các mẫu nội bộ (trong một giao dịch). Theo các nghiên cứu, các thuật toán khai phá mẫu dãy chủ yếu tập trung vào hai nội dung sau: (1) Cách thức mà dãy ứng viên được sinh ra và lưu trữ. Các thuật toán có thể có các cách khác nhau với mục tiêu là giảm thiểu số lượng dãy ứng viên để giảm chi phí I/O. (2) Cách mà độ hỗ trợ được tính và tần xuất dãy ứng viên được kiểm tra. Dựa vào các tiêu chí trên, thuật toán khai phá mẫu dãy có thể được nhóm thành hai hướng tiếp cận chính: thuật toán dựa trên Apriorri, thuật toán phát triển mẫu. Phương pháp tiếp cận dựa trên Apriori Nguyên lý Apriori ứng dụng cho dãy là nếu một dãy S không phải là dãy phổ biến thì mọi dãy cha của S cũng không phải là dãy phổ biến. Các thuật toán này dựa vào nguyên lý apriori để sinh và kiểm tra các dãy ứng viên, trong đó nếu một dãy được kiểm tra không thỏa mãn ngưỡng tối thiểu thì các dãy chứa nó cũng sẽ bị loại. Có một số thuật toán theo phương pháp tiếp cận dựa trên Apriori như AprioriAll, GSP, SPADE, SPAM... và các biến thể của chúng. (1) Thuật toán GSP: Cấu trúc cơ bản của thuật toán GSP [14] là thuật toán duyệt dữ liệu nhiều lần, lần duyệt đầu tiên xác định độ hỗ trợ của từng item. Kết thúc lần duyệt đầu tiên, thuật toán đưa ra được tập các 1-sequence phổ biến gọi là tập khởi đầu. Tập khởi đầu được sử dụng để sinh ra các dãy ứng viên mới với mỗi dãy ứng viên có ít nhất một item thuộc dãy khởi đầu, vì thế tất cả các dãy ứng viên trong một lần duyệt sẽ có cùng số item. Độ hỗ trợ của các dãy ứng viên này được tìm thấy trong quá trình duyệt dữ liệu. Kết thúc lần duyệt, thuật toán xác định các dãy ứng viên phổ biến và những dãy ứng viên phổ biến này trở thành tập khởi đầu cho lần duyệt tiếp theo. Thuật toán kết thúc khi không tìm được dãy ứng viên nào cuối lần duyệt, hoặc khi không có dãy ứng viên nào được sinh ra. Hình 1. Sinh các ứng viên và mẫu dẫy trong GSP (2) Thuật toán SPADE: thuật toán SPADE [17] tổ chức dữ liệu theo chiều dọc, trong đó ứng với mỗi item sẽ lưu danh sách định danh của các dãy dữ liệu và định danh của các itemset có chứa item đó. Độ hỗ trợ của item được tính trực tiếp từ danh sách các định danh. Mặt khác, SPADE còn dựa trên lý thuyết dàn để chia nhỏ không gian tìm kiếm và thao tác nối đơn giản để sinh ra tập các ứng viên. Thuật toán này gom nhóm các mẫu dãy dựa theo tiền tố thành các lớp tương đương. Thuật toán chỉ duyệt cơ sở dữ liệu ba lần: lần nhứ nhất và thứ hai thực hiện tìm các mẫu dãy có độ dài 1 và 2. Ở lần duyệt thứ ba, thuật toán phát triển mẫu độ dài k từ hai mẫu độ dài (k-1) có (k-2) item đầu giống nhau, tiến hành duyệt trên từng lớp tương đương do đó thuật toán giảm được khá nhiều chi phí tính toán và sử dụng bộ nhớ hiệu quả hơn; tuy nhiên thuật toán cũng cần một lượng thời gian để chuyển đổi một cơ sở dữ liệu theo chiều ngang sang định dạng theo chiều dọc. Hình 2. Tổ chức dữ liệu và chia nhỏ không gian tìm kiếm trong SPADE Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 127 (3) Thuật toán SPAM: thuật toán SPAM [3] kết hợp các giải pháp của các thuật toán GSP, SPADE, FreeSpan. Tương tự như SPADE, thuật toán này cũng tổ chức dữ liệu theo chiều dọc, thông tin của các mẫu ứng viên được biểu diễn dưới dạng bảng bit dọc, mỗi bit ứng với một itemset của một dãy trong cơ sở dữ liệu. Nếu item có mặt trong itemset j thì bit tương ứng được đánh dấu là 1, ngược lại là 0. Độ hỗ trợ của mẫu được xác định dựa trên bảng bit. SPAM sử dụng phương pháp duyệt cây theo chiều sâu để sinh các ứng viên và nguyên tắc apriori để tỉa các ứng viên nhằm giảm không gian tìm kiếm. Thuật toán này hiệu quả đối với các cơ sở dữ liệu lớn vì tổ chức và lưu trữ dữ liệu dưới dạng bit nên thao tác sinh ứng viên và đếm độ hỗ trợ rất hiệu quả. Hình 3. Biến đổi dữ liệu sang dạng nhị phân dọc trong SPAM Các thuật toán theo phương pháp tiện cận dựa Apriori về cốt lõi dựa trên các đặc điểm chính sau [10]: - Tìm kiếm theo chiều rộng: Khi thuật toán xây dựng tập tất cả các dãy k-sequence trong mỗi lần lặp thứ k, thuật toán duyệt qua toàn bộ không gian tìm kiếm - Sinh và kiểm tra ứng viên: Thuật toán sử dụng phương pháp tạo và tỉa các ứng viên, tuy nhiên phương pháp tạo ứng viên sinh ra một lượng lớn các dãy ứng viên và việc kiểm tra từng ứng viên thoả mãn ngưỡng cho phép làm tiêu tốn nhiều bộ nhớ trong giai đoạn đầu của quá trình. - Duyệt cơ sở dữ liệu nhiều lần: Cơ sở dữ liệu gốc sẽ được duyệt lặp lại nhiều lần để kiểm tra các ứng viên được tạo ra có phổ biến hay không. Đây là điểm hạn chế của hầu hết các phương pháp dựa trên apriori vì nó đòi hỏi nhiều thời gian xử lý và chi phí I/O. Phương pháp tiếp cận phát triển mẫu Ý tưởng chính của phương pháp tiếp cận hướng phát triển mẫu là để tránh việc sinh toàn bộ các ứng viên và tập chung vào tìm kiếm trên một phần được hạn chế trên cơ sở dữ liệu ban đầu, việc phân vùng không gian tìm kiếm là nội dung quan trọng trong hướng tiếp cận này. Các thuật toán phát triển mẫu là các thuật toán duyệt theo chiều sâu, kỹ thuật này tạo ra cơ sở dữ liệu quy chiếu cho mỗi mẫu có chiều dài k và lặp lại quá trình để tìm kiếm mẫu có chiều dài k+1. Hướng tiếp cận này sử dụng kỹ thuật chia để trị, việc tạo cơ sở dữ liệu quy chiếu là một giải pháp nhằm làm giảm không gian tìm kiếm. Có một số thuật toán theo phương pháp tiếp cận như FreeSpan, PrefixSpan, Wap-mine, Prism... và các biến thể của chúng (1) Thuật toán FreeSpan, PrefixSpan: Tiếp cận theo hướng chia nhỏ dữ liệu, FreSpan[6] là thuật toán đầu tiên thực hiện phép chiếu trên cơ sở dữ liệu để giảm chi phí dữ liệu. Sau đó, thuật toán này được phát triển thành PrefixSpan [11]. Xuất phát từ tập mẫu dãy có độ dài 1, PrefixSpan tạo ra cơ sở dữ liệu được chiếu với mỗi mẫu đó. Trong cơ sở dữ liệu quy chiếu, mỗi dãy dữ liệu chỉ giữ lại phần hậu tố, đối với tiền tố đã chiếu, mẫu được phát triển bởi những item phổ biến tìm được trong cơ sở dữ liệu được chiếu, quá trình này lặp đi lặp lại cho đến khi cơ sở dữ liệu chiếu không còn item phổ biến nào. Tuy nhiên khi phát triển mẫu cả FreeSpan, PrefixSpan đều phải thực hiện chiếu cơ sở dữ liệu và duyệt cơ sở dữ liệu quy chiếu để tìm item phổ biến. Hình 4. Xây dựng cơ sở dữ liệu quy chiếu trong PrefixSpan Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 128 (2) Thuật toán Wap-mine: Wap-mine [7] sử dụng kỹ thuật cấu trúc cây WAP-tree, trong kỹ thuật này cơ sở dữ liệu được duyệt hai lần để xây dựng cây WAP-tree từ các dãy phổ biến cùng với độ hỗ trợ của chúng. Một bảng được gọi là “header table” được sử dụng để chỉ sự xuất hiện lần đầu của item trong các tập phổ biến, nó được sử dụng để theo dõi các luồng trong khai phá cây. Wap-mine có hiệu quả trong việc hạn chế sinh các ứng viên, tuy nhiên lại phát sinh vấn đề tiêu thụ bộ nhớ do việc xây dựng lặp lại nhiều cây WAP-tree trung gian. Hình 5. Khai phá cây WAP – tree trong thuật toán WAP – Mine (3) Thuật toán Prism: Thuật toán Prism [2] sử dụng phương pháp mã hóa nguyên tố để biểu diễn thông tin của mẫu ứng viên và sử dụng cấu trúc dữ liệu cây từ điển để lưu trữ các mẫu dãy tuần tự. Thuật toán chỉ duyệt cơ sở dữ liệu đúng một lần để tìm tập mẫu dãy tuần tự có độ dài 1 cùng với khối mã hóa thông tin tương ứng cho các mẫu đó. Sau đó, phát triển mẫu bằng cách thêm vào mẫu một item phổ biến. Thông tin của mẫu mới được xác định dựa trên khối mã hóa của mẫu cũ và của item thêm vào, độ hỗ trợ của các ứng viên được xác định trực tiếp từ khối mã hóa nguyên tố. Như vậy, thuật toán Prism không phải duyệt cơ sở dữ liệu nhiều lần, đồng thời thuật toán làm giảm chi phí tính toán bằng cách sử dụng bảng tra cho khối mã hóa thông tin dựa trên lý thuyết mã hóa nguyên tố. Các thuật toán theo phương pháp tiện cận phát triển mẫu về cốt lõi dựa trên các đặc điểm chính sau [5]: - Phân vùng không gian tìm kiếm: Giải pháp cho phép phân vùng không gian tìm kiếm trong trường hợp số lượng lớn các dãy ứng viên được sinh ra giúp cho việc quản lý bộ nhớ hiệu quả hơn. Sau khi phân vùng không gian tìm kiếm, các phân vùng nhỏ có thể được khai phá song song. Hình 6. Không gian tìm kiếm mẫu dãy và mã hóa nguyên tố cho mẫu mở rộng trong Prism - Cây quy chiếu: Các thuật toán sử dụng cấu trúc dữ liệu cây để biểu diễn không gian tìm kiếm và sau đó sử dụng phương pháp duyệt theo chiều rộng hoặc duyệt theo chiều sâu để tìm kiếm các dãy phổ biến và tỉa các ứng viên dựa trên nguyên lý Apriori. - Duyệt theo theo chiều sâu: kỹ thuật duyệt cây theo chiều sâu được xem là một trong những tính chất quan trọng trong các thuật toán sử dựng mô hình cây. Theo một số nghiên cứu [2][15][1][4] nó được đánh giá cao và thực hiện rất hiệu quả vì sử dụng ít bộ nhớ hơn và định hướng không gian tìm kiếm do đó tạo ra số lượng ứng viên ít hơn kỹ thuật duyệt theo chiều rộng. - Tỉa các dãy ứng viên: Giải pháp tỉa trước các dãy ứng viên giúp việc biểu diễn không gian tìm kiếm nhỏ hơn và duy trì một thủ tục tìm kiếm có hướng và phạm vi hẹp hơn. Phần lớn các thuật toán này sử dụng kỹ thuật tìm kiếm theo chiều sâu và ứng dụng tính chất phản đơn điệu của nguyên lý Apriori. CÁC HẠN CHẾ VÀ MỘT SỐ VẤN ĐỀ MỞ RỘNG Thông qua một số vấn đề thảo luận ở trên, có rất nhiều các kỹ thuật hiệu quả và các biến thể của chúng được đề xuất, cung cấp cho chúng ta các giải pháp hiệu quả trong nhiều trường hợp. Tuy nhiên các kỹ thuật này vẫn còn một số hạn chế mà đến nay vẫn đang là những trở ngại và thách thức trong quá trình thực hiện khai phá mẫu dãy: Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 129 - Các thuật toán theo hướng tiếp cận dựa trên Apriori, với cơ sở dữ liệu dãy lớn nó sẽ tạo ra một lượng rất lớn các ứng viên. Mặt khác, trong quá trình khai phá kỹ thuật này đòi hỏi phải duyệt cơ sở dữ liệu gốc nhiều lần. - Trong hướng tiếp cận phát triển mẫu, chi phí chủ yếu của các kỹ thuật này là việc xây dựng cơ sở dữ liệu quy chiếu. Trong trường hợp xấu nhất, chúng ta phải xây dựng cơ sở dữ liệu quy chiếu cho mọi mẫu, với số lượng mẫu lớn thì chi phí này là không tầm thường. - Trong quá trình khai phá có thể tạo ra lượng lớn các mẫu dãy phổ biến, nhưng người sử dụng chỉ quan tâm một lượng nhỏ các mẫu có ích trong đó phù hợp với mục tiêu sử dụng, việc biểu diễn toàn bộ các mẫu gây khó khăn cho việc sử dụng. - Khó khăn trong quá trình khai phá các mẫu dãy dài bởi vì các mẫu này phải được phát triển từ một lượng lớn các mẫu ngắn, vì thế số lượng các ứng viên được sinh ra sẽ là cấp số nhân. Khai phá mẫu dãy đã được tập chung nghiên cứu mạnh mẽ trong những năm gần đây. Với các mục đích ứng dụng khác nhau tạo ra một lượng lớn sự đa dạng các thuật toán khai phá mẫu dãy, nhiều phần mở rộng của các định nghĩa ban đầu được đề xuất cho các mục đích đặc biệt như khai phá dãy mẫu với những rành buộc, mẫu dãy đóng, đa chiều, gia tăng Khai phá mẫu dãy đa chiều Mẫu dãy đơn chiều là chúng ta chỉ xem xét một thuộc tính cùng với các nhãn thời gian trong quá trình khai phá. Trong khi đó, với mẫu dãy đa chiều chúng ta có thể xem xét nhiều thuộc tính cùng một lúc. Khai phá mẫu dãy tuần tự đa chiều được giới thiệu bởi Helen Pinto và JiaweiHan [8] có thể cung cấp cho chúng ta các mẫu hữu ích và mang nhiều thông tin hơn. Khai phá mẫu dãy đóng Các thuật toán khai phá mẫu dãy được phát triển cho đến nay có hiệu suất tốt trong cơ sở dữ liệu có chứa các dãy phổ biến ngắn. Tuy nhiên, khi khai thác các dãy phổ biến dài, hoặc khi sử dụng ngưỡng hỗ trợ rất thấp, hiệu suất của các thuật toán trên thường giảm đáng kể. Ví dụ cơ sở dữ liệu chỉ chứa một dãy phổ biến , nó sẽ tạo ra 2100-1 dãy phổ biến nếu ngưỡng tối thiểu là 1, mặc dù tất cả các dãy phổ biến này ngoại trừ dãy dài nhất là không cần thiết. Vì vậy, một giải pháp đề xuất thay vì khai thác tập toàn bộ các mẫu dãy phổ biến, chúng ta chỉ khai thác dãy phổ biến đóng, nghĩa là chỉ lấy tập các mẫu dãy phổ biến mà chúng không được chứa dãy phổ biến khác có cùng độ hỗ trợ [15][16]. Kỹ thuật này sẽ tạo ra một số lượng dãy ít hơn đáng kể so với dãy kỹ thuật truyền thống trong khi vẫn giữ được tính hiệu quả. Khai phá mẫu dãy dựa vào các ràng buộc Mặc dù hiệu quả của việc khai phá tập toàn bộ các mẫu dãy đã được cải thiện đáng kể dựa trên nhiều kỹ thuật được đề xuất. Tuy nhiên, trong nhiều trường hợp khai phá mẫu dãy vẫn phải đối mặt với các thách thức trong cả hai vấn đề hiệu suất và tính hiệu quả. Mặt khác, trong số lượng lớn các mẫu dãy, người sử dụng có thể chỉ quan tâm đến một nhóm nhỏ các mẫu trong đó. Nếu biểu diễn toàn bộ các mẫu có thể làm cho kết quả khó hiểu và khó sử dụng. Để khắc phục vấn đề này Jian Pei, JiaweiHan, Weiwang [5] đã giới thiệu hệ thống các ràng buộc được đưa vào phương pháp phát triển mẫu để khai phá mẫu dãy. Những ràng buộc này có thể được xem như những bộ lọc được áp dụng cho việc trích xuất các mẫu dãy. Khai phá mẫu dựa vào ràng buộc có thể vượt qua những khó khăn về hiệu suất và tính hiệu quả khi tập trung khai phá các mẫu dựa vào các ràng buộc phù hợp với lợi ích người sử dụng, hạn chế số lượng các mẫu tìm được trong một tập con đáp ứng các điều kiện mạnh. Khai phá mẫu dãy gia tăng Các thuật toán khai khá dữ liệu có độ phức tạp tính toán cao, do đó nếu sử dụng các giải pháp truyền thống thì khi thêm bản ghi dữ liệu mới phải khai phá lại từ đầu sẽ tiêu tốn một lượng thời gian lớn. Vì thế, có một hướng tiếp cận mới cho nội dung này gọi là khai phá mẫu dãy gia tăng. Ý tưởng chính của hướng tiếp cận này là khi thêm một lượng dữ liệu vào cơ sở dữ liệu thì phần dữ liệu gia tăng này được duyệt qua và kết hợp với các Quách Xuân Trưởng và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 130 mẫu dãy phổ biến đã được phát hiện trong lần khai phá trước nhằm xác định các thành phần của cơ sở dữ liệu ban đầu cần duyệt lại. Do vậy không cần phải duyệt lại toàn bộ cơ sở dữ liệu gốc. Một số thuật toán khai phá mẫu dãy gia tăng [5] được phát triển dựa trên các thuật toán GSP, SPADE và một số thuật toán mới được đề xuất như IUS, ISE, KISP. KẾT LUẬN Hiện nay, khai phá mẫu dãy có vai trò quan trọng. Nó hỗ trợ hiệu quả trong việc tìm kiếm các mối quan hệ giữa các dữ liệu. Trong nội dụng bài báo này, chúng tôi đã khảo sát và tông hợp các vấn đề cơ bản về khai thác mẫu dãy và các phương pháp cơ bản được sử dụng trong khai phá mẫu dãy. Trong thực tế, dữ liệu luôn được bổ sung và cập nhật liên tục trong cơ sở dữ liệu, việc khai phá mẫu dãy phổ biến luôn được quan tâm nghiên cứu. Các thuật toán khác nhau được phát triển để khai phá mẫu dãy trong dữ liệu, chúng đã chứng minh được tính hiệu quả cho các cơ sở dữ liệu nhỏ nhưng khi kích thước của cơ sở dữ liệu liên tục tăng lên, hiệu suất của các thuật toán này có thể giảm đáng kể. Do đó các phương pháp phải được cải thiện hoặc đề xuất mới để thực hiện quá trình khai phá một cách tốt hơn. TÀI LIỆU THAM KHẢO [1]. ANTUNES, C. AND OLIVEIRA, A. L. 2004. Sequential pattern mining algorithms: Trade-offs between speed and memory. In Proceedings of the Workshop on Mining Graphs, Trees and Sequences (MGTSECML/PKDD ’04). [2]. AYRES, J., FLANNICK, J.,GEHRKE, J., AND YIU, T. 2002. Sequential pattern mining using a bitmap representation. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 429–435. [3]. Ayres, J., Gehrke, J.E., Yiu, T., Flannick, J. (2002), “Sequential Pattern Mining using a Bitmap Representaion”, in SIGKDD Conf., pp. 1–7. [4]. EZEIFE, C. I. AND LU, Y. 2005. Mining web log sequential patterns with position coded pre- order linked WAP-tree. Int. J. Data Mining Knowl. Discovery 10, 5–38. [5]. F. Masseglia, P. Poncelet, M. Teisseire (2000), "Incremental Mining of Sequential Patterns in Large Databases", BDA'OO, France [6]. Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., and Hsu, M.C., (2000), “Freespan: Frequent pattern-projected sequential pattern mining”, in Proc. 2000 Int. Conf. Knowledge Discovery and Data Mining (KDD’00), pp. 355–359. [7]. Han, J., Pei, J., Mortazavi-Asl, B. and Zhu, H., “Mining access patterns efficiently from web logs”, In Proceedings of the Pacific- Asia Conference on Knowledge Discovery and Data Mining (PAKDD’00) Kyoto Japan, 2000. [8]. Helen Pinto Jiawei Han Jian Pei Ke Wang, “Multidimensional Sequential Pattern Mining”, In Proc. 2001 Int. Conf. Information and Knowledge Management (CIKM’01), Atlanta, GA, Nov. 2001 pp. 81–88. [9]. Jian Pei, Jiawei Han, Wei Wang, “Constraint- based sequential pattern mining: the pattern growth methods”, J Intell Inf Syst , Vol. 28, No.2, ,2007, pp. 133 –160. [10]. NIZAR R. MABROUKEH and C. I. EZEIFE, “A Taxonomy of Sequential Pattern Mining Algorithms”, ACM Computing Surveys, Vol. 43, No. 1, Article 3, Publication date: November 2010. [11]. Pei, J., et al. (2004), “Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach”, in: IEEE Trans. Knowledge and Data Engineering 16(10), pp. 1424–1440. [12]. Qiankun Zhao. Sourav S.Bhowmick, “Sequential Pattern Mining: A Survey”, Technical report, CAIS, Nanyang Technological University, Singgapore, No. 2003118, 2003. [13]. Rakesh Agrawal Ramakrishna Srikant, “Mining Sequential Patterns” , 11th Int. Conf. on Data Engineering, IEEE Computer Society Press, Taiwan, 1995 pp. 3-14 [14]. Srikant R. and Agrawal R., “Mining sequential patterns: Generalizations and performance improvements”, Proceedings of the 5th International Conference Extending Database Technology, 1996, 1057, 3-17. [15]. Wang, J. and Han, J. 2004. BIDE: Efficient mining of frequent closed sequences. In Proceedings of the 20th International Conference on Data Engineering. 79–90. [16]. Yan, X., Han, J., and Afshar, R. (2003), “CloSpan: Mining Closed Sequential Patterns in Large Databases”, in: Proceedings of SIAM International Conference on Data Mining [17]. Zaki, M.J. (2000), “SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Machine Learning Journal 42(1/2), pp. 31–60. Quách Xuân Trường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 118(04): 125 - 131 131 SUMMARY RESEARCHES OF SEQUENTIAL PATTERN MINING ALGORITHMS IN SEQUENTIAL DATA Quach Xuan Truong*, Nguyen Van Su, Dinh Duc Hoang College of Information Technology and Communications – TNU Sequential pattern mining is an important data mining problem with broad applications such as market analysis, web access, pattern analysis, intrusion detection in network environment, in DNA research, and predicting the shopping needs of customers. Sequential pattern mining discovers frequent subsequences as patterns in sequence database. Since introduced by Agrawaland Srikant, now, this problem has attracted a lot of researchers and there are many techniques proposed. The very first was Apriori-based algorithm, later more scalable algorithms for complex applications were developed. This paper presents and analyzes the techniques by clustering techniques in three main groups: apriori-based, pattern-growth, early-pruning. This paper also compares different techniques based on the important key features and discusses some challenges in which existing research is focused Key words: Sequential patterns, apriori based, pattern growth, Sequence database, pattern analysis. Ngày nhận bài: 13/3/2014; Ngày phản biện: 15/3/2014; Ngày duyệt đăng: 25/3/2014 Phản biện khoa học: TS. Vũ Đức Thái – Trường ĐH CNTT&TT – ĐH Thái Nguyên * Tel: 0989090832; Email: qxtruong@ictu.edu.vn