Chương 1, luận văn giới thiệu tổng quan về dữ liệu dạng chuỗi, khai thác chuỗi tuần tự, các khái niệm liên quan; trình bày tổng quan các thuật toán khai thác chuỗi tuần tự, thuật toán theo hướng khai thác top-k chuỗi tuần tự đã được cộng đồng ở lĩnh vực khai phá dữ liệu trên thế giới nghiên cứu, đề xuất.1 Giới thiệu tổng quan Cơ sở dữ liệu chuỗi gồm các chuỗi chứa những phần tử {elements), những sự kiện {events) được sắp xếp theo thứ tự; được ghi lại bằng việc có hoặc không có gắn liền với ý niệm cụ thể về thời gian [10]. Dữ liệu chuỗi tồn tại nhiều trong cuộc sống thực tế xung quanh con người, tiêu biểu như: chuỗi dữ liệu sinh học (chuỗi DNA mã hóa gen di truyền, chuỗi Protein mô tả thành phần axit amin của Protein, mã hóa cấu trúc và chức năng của Protein), chuỗi dữ liệu lịch sử truy cập trình duyệt trang vveb, chuỗi dữ liệu về lịch sử mua hàng và bán hàng hóa [2]. Trong các dữ liệu dạng chuỗi, có khả năng chứa đựng những chuỗi ý nghĩa, mang thông tin hữu ích có tính quy luật, tính ràng buộc,. Vì vậy, đi tìm các chuỗi con phổ biến (tất cả hoặc chỉ một phần những chuỗi con được sắp xếp theo thứ tự) chứa đựng thông tin có giá trị hữu ích là kỹ thuật khám phá, khai thác dữ liệu được quan tâm nghiên cứu và ứng dụng rộng rãi trong thực tế.
Bài toán về khai thác chuỗi tuần tự được đưa ra lần đầu tiên bởi hai nhà nghiên cứu Ramakrishnan Srikant, Rakesh Agrawal vào năm 1995 [6], tiếp theo đó có nhiều kỹ thuật được công bố về khai thác chuỗi tuần tự. Trong đó, chuỗi tuần tự (sequential pattern) là chuỗi bao gồm những itemset xuất hiện phổ biến có thứ tự, mọi item trong một itemset được xem là có cùng thời điểm giao dịch. Những giao dịch của một khách hàng được sắp xếp gắn kết với nhau theo thứ tự thời gian và được xem là một chuỗi dữ liệu. Khai thác chuỗi tuần tự là thực hiện khám phá, tìm ra những chuỗi con phổ biến trong một CSDL chuỗi cụ thể.
Độ dài của mỗi bản ghi trong CSDL chuỗi là khác nhau, sự kiện trong một chuỗi có một hoặc nhiều item. 5 Khai thác chuỗi tuần tự là bài toán quan trọng, được ứng dụng sâu rộng trong các lĩnh vực như: Tối ưu hóa chiến dịch tiếp thị trong kinh doanh (phân tích thói quen, thị hiếu của người tiêu dùng trong mua sắm hàng hóa để dự báo xu hướng, nhu cầu của khách, đưa ra phưong án tiếp thị tối ưu); phát hiện gian lận và rủi ro (tìm ra các giao dịch tài chính bất thường, dự báo rủi ro tài chính để có biện pháp phòng ngừa, quản lý tài chính hiệu quả); chuẩn đoán, điều trị bệnh trong y khoa; tối ưu hóa quy trình sản xuất và vận hành để giảm lãng phí, tăng năng suất,.2 Khai thác chuỗi tuần tự 1.1 Phắt biểu bài toán Cho tập hợp ỉ = {ílf i2,., im} gồm có m phần tử (item). Itemset là một tập khác rỗng, không có thứ tự của những item. Itemset i ký hiệu là (ì\, i2,., im) với mỗi ij là một item.
Giả sử những item trong itemset được sắp xếp theo thứ tự tăng dần. Một chuỗi là một danh sách những itemset sắp xếp theo thứ tự. Cho chuỗi s được ký hiệu ($!, s2,., sn} hoặc fe ^ s2 -> ••• -> sn) với mỗi Si là một sự kiện, n là số lượng những sự kiện. Kích thước của chuỗi bằng số lượng itemset có trong chuỗi.
Tổng số item có mặt trong chuỗi chính là chiều dài của chuỗi l = 2ỹ=15? Vói những chuỗi có chiều dài là k được gọi là k-sequence. Ví dụ: s = ((a)bb) được gọi là 3-sequence kích thước là 2.,bn) ỉầ chuỗi con của chuỗi a = (alfa2, .,ữn)hay a là chuỗi cha của b, ký hiệu b Q a, nếu 3jị\i = 1.< jn < m sao cho bỵ Q CLji,^ Q dj2,. Ví dụ: {(e)(cdỴ) là chuỗi con của {(ab)(be)(acd)) vì e c be,cd C acd và không thay đổi thứ tự của những itemset. Tuy nhiên, chuỗi ((abc)) và ((ab)(c)) không là chuỗi con của nhau.2 Khái niệm liên quan Cơ sở dữ liệu chuỗi: Là một tập hợp những bộ dữ liệu có dạng (SID, s); vói SID là chỉ số định danh của chuỗi, 5 là chuỗi những itemset.
6 Tần số xuất hiện: Tần số xuất hiện của một chuỗi là số lần xuất hiện của chuỗi đó trong tập dữ liệu; dùng để xác định mức độ quan trọng của chuỗi trong quá trình khai thác dữ liệu. Độ ho trợ (support): Cho CSDL chuỗi D, mỗi chuỗi có một chỉ số định danh duy nhất. Độ hỗ trợ tuyệt đối của một chuỗi /là tổng số chuỗi trong D có chứa/ký hiệu supD(f) = |{SÍ € D \f C Sí}|. Độ hỗ trợ tương đối của f được định nghĩa là tỉ lệ phần trăm của số lượng chuỗi trong tập D chứa chuỗi f.
Trong đó, những khái niệm mức hỗ trợ tuyệt đối và tương đối có thể được chuyển đổi qua lại, được biểu diễn bằng ký hiệu sup(f). Chuỗi tuần tự: Giá trị ngưỡng hỗ trợ tối thiểu (minsup) được người dùng xác định. Một chuỗi / được xem là phổ biến khi và chỉ khi có độ hỗ trợ lớn hơn hoặc bằng minsup: sup(f) > minsup, khi đó/được gọi là chuỗi tuần tự. Ví dụ: Cho CSDL chuỗi D như Bảng 1.1 có tập những item phân biệt là (a, b, c}, với minsup = 2.
Xét chuỗi s2 = ((ab)bb), chuỗi s2 có 3 itemset là: (ab), b, ó và có 4 item. Vậy s2 có kich thước là 3 và có độ dài là 4. Trong chuỗi s2, item b xuất hiện 3 lần nhưng độ hỗ trợ của item b chỉ được tính là 1 đối với chuỗi s2 đó. Cho chuỗi a = {(ab)a); xét thấy là chuỗi a là chuỗi con của của chuỗi Sỉ, nên chuỗi con p cũng được gọi là chuỗi.
Trong D, chỉ có chuỗi Sỵf s5 có chứa chuỗi a nên độ hỗ trợ của chuỗi a là 2. Vì sup(a) = minsup nên a là một chuỗi tuần tự.1 Bảng CSDL chuỗi D SID Chuỗi 1 {(ab)bb(ab)ba) 2 {(ab)bb) 3 (b(ab)) 4 (bbb) 5 ((ab)(ab) (ab) (a) (bcỴ) 7 Khai thác chuỗi tuần tự: Quá trình tìm kiếm, xác định một tập hợp đầy đủ những chuỗi con phổ biến (chuỗi tuần tự) trong CSDL chuỗi. Những chuỗi này có độ hỗ trợ lớn hơn hoặc bằng ngưỡng minsup mà người dùng xác định.3 Các thuật toán liên quan Như phát biểu ở trên, các thuật toán khai thác chuỗi tuần tự cần có tham số đầu vào là giá trị ngưỡng hỗ trợ tối thiểu minsup do người dùng nhập vào để kết quả đầu ra của thuật toán là những chuỗi con phổ biến có độ hỗ trợ thỏa mãn điều kiện lớn hơn hoặc bằng với giá trị minsup đầu vào. Bài toán khai thác chuỗi tuần tự đầu tiên được đưa ra vào năm 1995 bởi hai nhà nghiên cứu Ramakrishnan Srikant và Rakesh Agrawal.
Tiếp theo, có nhiều thuật toán về khai thác chuỗi tuần tự được nghiên cứu đề xuất như: Prefixspan [8], GSP [11], SPAM [14],. Một số thuật toán tiêu biểu trong khai thác chuỗi tuần tự như sau: ỉ.1 AprìorìAll [6J Thuật toán AprioriAll [6] được hai nhà nghiên cứu Ramakrishnan Srikant, Rakesh Agrawal đề xuất vào năm 1995; là thuật toán khai thác dữ liệu chuỗi giao dịch khách hàng, được thực hiện theo 3 bước: Tìm itemset phổ biến, chuyển đổi CSDL, tìm chuỗi tuần tự trên CSDL chuyển đổi. - Tìm itemset phổ biến: Thuật toán thực hiện duyệt CSDL đầu vào để tìm ra các itemset phổ biến và ánh xạ chúng sang tập số nguyên nhằm tách các itemset phổ biến thành đối tượng riêng biệt và so sánh giữa 2 itemset phổ biến bất kỳ đều có thời gian là như nhau. Đồng thời, rút ngắn thời gian kiểm tra một chuỗi có là chuỗi con của chuỗi trong CSDL ban đầu.
- Chuyển đỏi CSDL: Tất các những chuỗi trong CSDL đầu vào được thay thế thành tập những itemset phổ biến mà chuỗi đó chứa. Trường hợp itemset không chứa item set con phổ biến thì loại item set đó khỏi tập các chuỗi. Trường hợp chuỗi trong CSDL không chứa itemset phổ biến thì loại chuỗi đó khỏi CSDL. Kết quả bước này là chuyển đổi thành CSDL bao gồm các itemset phổ biến.
8 - Tìm chuỗi tuần tự dựa trên CSDL đã chuyển đổi: Tìm chuỗi tuần tự dựa trên kết quả bước tìm itemset phổ biến, ta có được tập các chuỗi tuần tự kích thước là 1. Thuật toán thực hiện tìm chuỗi tuần tự từ tập các chuỗi ứng viên có chiều dài k được tạo ra bằng cách kết hợp những chuỗi có chiều dài k=l. Theo đó, thuật toán dựa trên nguyên lý Apriori (mọi tập con của tập phổ biến phải là tập phổ biến) và ngưỡng hỗ trợ tối thiểu minsup để loại những chuỗi không phổ biến. Để tìm được đầy đủ các chuỗi tuần tự, thuật toán AprioriAll cần phải duyệt CSDL nhiều lần bởi vì ứng với từng tập ứng viên thì thuật toán phải duyệt lại CSDL để tính độ hỗ trợ.
Bên cạnh đó, AprioriAll sinh ra tập những ứng viên vói số lượng lớn; cho chuỗi có chiều dài là n thì có thể tạo ra số ứng viên là xp=1 c^ = 2n — 1, dẫn đến không đủ dung lượng bộ nhớ để xử lý (được mô tả như tình trạng nghẽn cổ chai).2 Thuật toán GSP [11] Thuật toán GSP (Generalized Sequential Pattern) được hai nhà nghiên cứu Yu Hirate và Hayato Yamana đã đề xuất vào năm 2006, đây là thuật toán mở rộng từ mô hình Apriori. GSP giải quyết bài toán khai thác chuỗi tuần tự một cách tổng quát thông qua việc bổ sung các ràng buộc như khoảng thời gian cực đại, cực tiểu giữa các thành phần trong một chuỗi tuần tự. Những item của từng thành phần trong chuỗi có thể được lấy từ một hoặc nhiều thành phần khác nhau nhưng khoảng thời gian giữa những thành phần phải trong giới hạn “time window”. Ngoài ra, GSP hỗ trợ sự phân cấp trên những item, cho phép một chuỗi bao gồm những item thuộc mức phân cấp khác nhau.
GSP thực hiện tưong tự như AprioriAll, thực hiện duyệt CSDL nhiều lần. Cho một tập có k phần tử, Lkbiểu thị tất cả các chuỗi phổ biến, Ck biểu thị các tập ứng viên. Lần duyệt đầu tiên xác định tập hợp các chuỗi phổ biến độ dài 1. Trong những lần duyệt tiếp theo, thuật toán sinh tập ứng viên độ dài (k+1) (Ck) từ tập phổ biến độ dài k (Lk) ỏ lần duyệt trước, sau đó đếm độ hỗ trợ của từng ứng viên và tìm được tập phổ biến độ dài k.