Chương 1, Giới Thiệu: Chương này sẽ mô tả tổng quan về đề tài, mục tiêu nghiên cứu, giới hạn đề tài. • Chương 2, Nghiên Cứu Liên Quan: Chương này sẽ trình bày chi tiết về những nghiên cứu nổi bật về các kỹ thuật khai phá mẫu tuần tự, việc đánh giá các nghiên cứu này cũng được đưa ra. • Chương 3, Kiến Thức Nền: Chương này sẽ mô tả những kiến thức nền tảng được áp dụng trong luận văn. • Chương 4, Mô Hình Hệ Thống: Chương này sẽ đề xuất mô hình hệ thống cho việc khai phá.
• Chương 5, Thực Nghiệm: Chương này sẽ trình bày quá trình thu thập dữ liệu, quá trình xử lý và tiến hành thử nghiệm, đánh giá và báo cáo kết quả thu được. • Chương 6, Kết Luận, tổng kết lại đề tài và đề xuất những công việc trong tương lai. 3 CHƯƠNG 2: NGHIÊN CỨU LIÊN QUAN Kể từ khi đề xuất bởi Agrawal, Rakesh và Ramakrishnan Srikant đến nay bài toán này đã thu hút được nhiều nghiên cứu và nhiều kĩ thuật được đề xuất. Đầu tiên là thuật toán dựa trên Apriori, sau đó là các thuật toán được mở rộng phát triển cho các ứng dụng phức tạp.
Nội dung trong chương này tập trung phân tích các kỹ thuật khai phá mẫu tuần tự mang tính quan trọng hiện nay.1 Phương pháp tiếp cận dựa trên Apriori Các thuật toán dựa trên nguyên lý Apriori sử dụng phương pháp tạo-tỉa (Generating-Pruning). Trong đó, nếu một mẫu được kiểm tra không thoả mãn ngưỡng tối thiểu thì các mẫu chứa nó cũng bị loại. Một số thuật toán dựa trên Apriori như AprioriAll [1], AprioriSome [1], GSP [2], SPADE [3], SPAM [4] 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 [2] 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 ứng viên mới với mỗi ứng viên có ít nhất một item thuộc sequence khởi đầu, vì thế tất cả các ứ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 sequence ứng viên phổ biến và những sequence ứ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 sequence ứng viên nào cuối lần duyệt, hoặc khi không có sequence ứng viên nào sinh ra.
4 Frequent Candidate 4-Sequences 3-Sequences After Join After Pruning < (1, 2) (3) > < (1, 2) (3, 4) > < (1, 2) (3, 4) > < (1, 2) (4) > < (1, 2) (3) (5) > < (1) (3, 4) > < (1, 3) (5) > < (2) (3, 4) > < (2) (3) (5) > Bảng 2. 1 Quá trình sinh các ứng viên 2.2 Thuật toán SPAM (Sequential PAttern Mining using A Bitmap Representation) Ý tưởng thuật toán SPAM [4] 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 bit dọc, mỗi bitmap có một bit tương ứng với mỗi giao dịch (transaction) trong cơ sở dữ liệu. Nếu item i xuất hiện trong giao dịch j thì bit tương ứng trong bitmap cho item i được gán 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 (depth-first search) để sinh các ứng viên và nguyên tắc Apriori để tỉa (pruning) 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ả. 1: Biến đổi dữ liệu sang dạng nhị phân trong SPAM 2.2 Phương pháp tiếp cận dựa trên phát triển mẫu (Pattern growth based methods) Ý tưởng chính của phương pháp phát triển mẫu là để tránh việc sinh toàn bộ các ứng viên và tập trung vào tìm kiếm trên một phần được hạn chế của 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. Phương pháp 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 giảm không gian tìm kiếm. Một số thuật toán theo hướng tiếp cận này: FreeSpan, PrefixSpan, Wap-mine, Prism và các biến thể của chúng. Thuật toán FreeSpan [5], PrefixSpan [6]: Tiếp cận theo hướng chia nhỏ dữ liệu, FreeSpan 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.
Xuất phát từ tập sequence có độ dài 1, PrefixSpan tạo ra cơ sở dữ liệu được chiếu với mỗi sequence đó. Trong cơ sở dữ liệu quy chiếu, mỗi sequence 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ả 6 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. 2: Xây dựng cơ sở dữ liệu quy chiếu trong PrefixSpan 2.3 Khai phá mẫu tuần tự đóng (Closed Sequential Patterns) Các thuật toán khai phá mẫu tuần tự đượ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 mẫu phổ biến ngắn.
Tuy nhiên, khi khai thác các mẫu phổ biến dài, hoặc ngưỡng hỗ trợ thấp, hiệu suất các thuật toán trên giảm đáng kể. 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 phổ biến, chúng ta chỉ khai thác mẫu phổ biến đóng, nghĩa là chỉ lấy các tập mẫu sequence phổ biến mà chúng không được chứa trong sequence phổ biến khác có cùng độ hỗ trợ [7]. Kỹ thuật này sẽ tạo ra một số lượng sequence ít hơn đáng kể so với kỹ thuật truyền thống trong khi vẫn giữ được tính hiệu quả. Ngoài ra còn một số kỹ thuật khác: khai phá mẫu tuần tự tăng dần (Incremental Mining of Sequential Patterns), mở rộng vấn đề dựa trên việc trích xuất các mẫu tuần tự (Extended Problems Based on the Sequential Patterns Extraction).
7 CHƯƠNG 3: KIẾN THỨC NỀN 3.1 Các khái niệm cơ bản Cơ sở dữ liệu lưu trữ thông tin giao dịch mua bán hàng bao gồm các thông tin về mã khách hàng (Customer-ID), thời gian giao dịch (Transaction-Time) và các mặt hàng trong giao dịch (Items Bought). Một cơ sở dữ liệu khách hàng thể hiện trong bảng sau : Transaction Customer Items Time ID Bought June 10 '93 2 10,20 June 12 '93 5 90 June 15 '93 2 30 June 20 '93 2 40, 60, 70 June 25 '93 4 30 June 25 '93 3 30,50,70 June 25 '93 1 30 June 30 '93 1 90 June 30 '93 4 40, 70 July 25 '93 4 90 Bảng 3. 1: Cơ sở dữ liệu khách hàng Một itemset là một tập không rỗng các phần tử (item). Giả sử rằng mỗi itemset được ánh xạ tới một tập các số nguyên.
Ta biểu thị itemset i bởi (i1i2…im), trong đó ij là một phần tử (item). Một sequence là một danh sách có thứ tự các itemset. Ta biểu thị một sequence s bởi <s1s2…sn> , trong đó sj là một itemset. 8 Một sequence <a1 a2…an> được chứa trong sequence (b1 b2…bn) nếu tồn tại số nguyên i1<i2<…<in sao cho a1 Í bi1, a2 Í bi2,…, an Í bin.
Ví dụ, một sequence < (3) (4,5) (8) > được chứa trong <(7) (3 8) (9) (4 5 6) (8) >, vì 3 Í (3 8), (4 5) Í (4 5 6) và (8) Í (8). Tuy nhiên, dãy <(3) (5)> không được chứa trong <(3 5)> và ngược lại. Phần tử 3 và 5 trong dãy <(3) (5)> mô tả chúng không nằm trong cùng một lần giao dịch, trong khi phần tử 3 và 5 trong dãy <(3 5)> mô tả chúng nằm trong một lần giao dịch. Một sequence s không được chứa trong bất kỳ sequence nào khác được gọi là một sequence tối đa (maximal sequence).
Một customer sequence là một danh sách giao dịch khách hàng theo thứ tự tăng dần về thời gian giao dịch. Các giao dịch của một khách hàng được sắp xếp theo thứ tự tăng dần theo thời gian (T1, T2,. Tập các phần tử (item) trong Ti được biểu thị bởi itemset(Ti). Một customer-sequence của một khách hàng được biểu diễn như sau: < itemset(T1) itemset(T2).
Độ hỗ trợ của một sequence: một khách hàng hỗ trợ một sequence s nếu s được chứa trong customer sequence đối với khách hàng đó. Độ hỗ trợ của một sequence được định nghĩa là số khách hàng hỗ trợ sequence đó. Một sequence đáp ứng độ hỗ trợ tối thiểu được gọi là một sequence phổ biến (large sequence).2 Khai phá mẫu tuần tự Khai phá mẫu tuần tự được chia thành các giai đoạn sau đây: Giai đoạn sắp xếp (Short Phase): Cơ sở dữ liệu khách hàng ở bảng 4.1 được sắp xếp, với mã khách hàng là khoá chính và thời gian giao dịch là khoá phụ. Bước này chuyển đổi ngầm từ cơ sở dữ liệu giao dịch gốc thành cơ sở dữ liệu dạng sequence, kết quả sau khi sắp xếp như sau: 9 Customer ID Transaction Time Items Bought 1 June 25 '93 30 1 June 30 '93 90 2 June 10 '93 10,20 2 June 15 '93 30 2 June 20 '93 40,60,70 3 June 25 '93 30,50,70 4 June 25 '93 30 4 June 30 '93 40,70 4 July 25 '93 90 5 June 12 '93 90 Bảng 3.
2: Cơ sở dữ liệu khách hàng sau khi sắp xếp Cơ sở dữ liệu Bảng 3.2 được biểu diễn dạng sequence như sau: Customer ID Customer Sequence 1 < (30) (90) > 2 < (10 20) (30) (40 60 70) > 3 < (30 50 70) > 4 < (30) (40 70) (90) > 5 < (90) > Bảng 3. 3: Cơ sở dữ liệu khách hàng được biểu diễn dạng sequence Giai đoạn Litemset (Litemset Phase): Trong giai đoạn này, chúng ta tìm tập tất cả litemsets L, đồng thời cũng tìm kiếm tập tất cả các sequence phổ biến 1- sequence, vì tập này cũng là {<l>| l Î L}. Với giao dịch của một khách hàng, độ hỗ trợ được tính tăng lên chỉ một lần ngay cả khi khách hàng mua cùng một tập các sản phẩm trong hai hay nhiều giao dịch khác nhau. Tập hợp các litemsets 10 được ánh xạ tới một tập các số nguyên liên tiếp.
