Chương 1.TỔNG QUAN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG 1. Giới thiệu Khai phá dữ liệu là một quá trình trích xuất thông tin từ dữ liệu được lưu trữ trong các CSDL. Từ đó giúp phân tích và đưa ra các quyết định. Khai phá dữ liệu bao gồm các tác vụ chính như: phân cụm (clustering), phân lớp (classification), khai phá luật kết hợp… Khai phá tập mục thường xuyên là bài toán con của khai phá luật kết hợp.
Mục tiêu là tìm ra các mẫu dữ liệu thú vị, hữu ích trong CSDL. Khai phá tập mục thường xuyên được giới thiệu lần đầu tiên bởi Agrawal và Srikant [1]. Nhóm tác giả cũng đề xuất thuật toán Apriori để tìm các tập mục thường xuyên, tức là một nhóm các mục (biểu tượng) thường xuyên xuất hiện cùng nhau trong một CSDL giao dịch. Ví dụ: Thuật toán Apriori có thể dùng để tìm ra các mẫu như {nước ép cam, cà chua, nho} trong CSDL giao dịch tại một siêu thị.
Mẫu này thể hiện rằng các sản phẩm “nước ép cam”, “cà chua” và “nho” thường được mua cùng nhau trong siêu thị đó. Các tập mục thường xuyên được tìm ra có thể được sử dụng trong việc phân tích dữ liệu và ra quyết định. Ví dụ như từ các tập mục thường xuyên có thể hiểu được hành vi khách hàng, từ đó xây dựng các chiến lược quảng bá sản phẩm dựa trên hành vi. Mặc dù khai phá tập mục thường xuyên đã trở nên rất phổ biến và có thể ứng dụng trong nhiều lĩnh vực.
Tuy nhiên, các tập mục trong khai phá tập mục thường xuyên không quan tâm tới thứ tự của các mục. Trong một số lĩnh vực, thứ tự của các mục là rất quan trọng. Ví dụ như trong phân tích văn bản, thứ tự của các từ trong câu là rất quan trọng. Hay trong phát hiện hành vi xâm nhập mạng trái phép, thứ tự của các sự kiện cũng rất quan trọng.
Để có thể giải quyết vấn đề thứ tự của các mục, bài toán khai phá mẫu dãy thường xuyên đã được đề xuất. Khai phá mẫu dãy thường xuyên (SPM) [2, 3, 5 4, 5] là một tác vụ khai phá dữ liệu để phân tích dữ liệu dãy và tìm ra các mẫu dãy thường xuyên. Cụ thể là tìm ra các mẫu dãy con có giá trị trong tập các dãy dữ liệu. Trong đó giá trị của mẫu dãy được đo bằng tần xuất xuất hiện của mẫu dãy đó trong CSDL.
Khai phá mẫu dãy thường xuyên có nhiều ứng dụng trong thực tế dựa trên một sự thật là dữ liệu trong tự nhiên là một dãy có thứ tự của các mục, ví dụ như dữ liệu trong lĩnh vực tin sinh học, phân tích giỏ hàng, phân tích văn bản, phân tích chuỗi truy cập web… Bài toán khai phá mẫu dãy thường xuyên lần đầu tiên được Agrawal và cộng sự [2] đề xuất với mục tiêu là tìm ra các mẫu dãy con phổ biến trong tập hợp các dãy dữ liệu. Một dãy là một danh sách có thứ tự của các giá trị hữu danh. Ví dụ: dãy các từ trong văn bản, dãy thứ tự các sản phẩm được mua của khách hàng trong siêu thị hay dãy thứ tự các trang web truy cập bởi người dùng. Khai phá mẫu dãy thường xuyên là một lĩnh vực nghiên cứu rất sôi động với hàng trăm bài báo mới mỗi năm, cùng với rất nhiều mở rộng cho từng mục tiêu cụ thể.
Chương này sẽ trình bày các vấn đề cơ bản của bài toán khai phá mẫu dãy thường xuyên và một số hướng tiếp cận giải quyết bài toán cũng như một số mở rộng của bài toán. Một số khái niệm cơ bản Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Một tập mục X là một tập hợp các mục 𝑖𝑗 ∈ 𝐼 , do vậy X I. Lực lượng của tập mục X được ký hiệu là |X| là số mục trong X.
Tập mục X được gọi là có độ dài k hay còn gọi là k-tập mục nếu nó có k mục (nghĩa là |X|=k). Ví dụ có tập I = {a,b,c,d,e,f,g} là tập các sản phẩm bán trong một siêu thị thì tập {a, b, c} là một 3-tập mục thể hiện các mặt hàng được mua bởi một khách hàng trong một thời điểm nào đó. 6 Không giảm tổng quát, giả sử các mục trong một tập mục được sắp xếp theo thứ tự từ điển. Một dãy S là một danh sách được sắp xếp theo thứ tự của các tập mục dữ liệu S={X1, X2, …, Xn} với Xj I là một tập mục được gọi là thành phần của dãy.
Một mục dữ liệu chỉ xuất hiện 1 lần trong 1 thành phần Xj của dãy, nhưng có thể xuất hiện nhiều lần trong các thành phần của dãy S. Ví dụ giả sử có dãy <a(abc)(ac)d(cf)> là một dãy dữ liệu thể hiện 5 giao dịch của một khách hàng trong siêu thị. Mỗi chữ cái thể hiện một mục. Mỗi thành phần giữa hai dấu ngoặc đơn () thể hiện một tập mục, với các tập mục chỉ có 1 phần tử thì có thể bỏ qua dấu ngoặc này.
Dãy này chỉ ra rằng một khách hàng đã mua sản phẩm a sau đó mua 3 sản phẩm (a, b, c) cùng nhau, sau đó lại mua 2 sản phẩm (a, c) cùng nhau, tiếp đến mua sản phẩm d và cuối cùng mua 2 sản phẩm (c, f) cùng nhau Kích thước |S| của một dãy là số lượng của các thành phần (tập mục) trong dãy S. Độ dài l(S) của dãy là tổng số mục dữ liệu trong dãy S. Ví dụ dãy <a(abc)(ac)d(cf)> có kích thước 5 và độ dài 9. Một cơ sở dữ liệu dãy SDB={S1,S2,…,Sm} là một tập các dãy với các định danh (SID) là 1, 2, .m Ví dụ về một cơ sở dữ liệu dãy: SID Dãy dữ liệu 1 <(ab)c(fg)g(e)> 2 <(ad)cb(abef)> 3 <ab(fg)e> 4 <b(fg)> Bảng 1.1 Cơ sở dữ liệu dãy SDB 7 Cơ sở dữ liệu này có 4 dãy với SID lần lượt là 1, 2, 3 và 4.
CSDL này có thể thể hiện danh sách các mặt hàng mua bởi 4 khách hàng. Dãy con Cho 2 dãy dữ liệu α=< a1 a2 … an > and β=< b1 b2 … bm >. α được gọi là Dãy con của β (α⊆ β), nếu tồn tại một dãy số nguyên 1≤ j1 < j2 <…< jn ≤m sao cho a1 ⊆ bj1, a2 ⊆ bj2,…, an ⊆ bjn. β được gọi là Dãy chứa của α Ví dụ.
Độ hỗ trợ của một dãy Độ hỗ trợ của một dãy sa trong CSDL dãy SDB được định nghĩa là số dãy có chứa sa trong SDB và được ký hiệu là sup(sa). Nghĩa là: 𝑠𝑢𝑝(𝑠𝑎 ) = |{𝑠|𝑠𝑎 𝑠 ᴧ s ∈ SDB}| Ví dụ, độ hỗ trợ của dãy <b(fg)> trong Bảng 1.1 là 3 vì dãy này xuất hiện 3 lần trong CSDL (trong dãy 1, 2 và 4). Mẫu dãy thường xuyên Một dãy s được gọi là mẫu dãy thường xuyên nếu và chỉ nếu: sup(s) ≥ minsup. Trong trường hợp ngược lại thì s được gọi là mẫu dãy không thường xuyên.
Trong đó minsup là ngưỡng hỗ trợ tối thiểu được đặt bởi người dùng. Ví dụ: Nếu đặt minsup =2 thì dãy <a> trong CSDL Bảng 1.1 là một mẫu dãy thường xuyên với độ hỗ trợ là 3. Tính chất của mẫu dãy thường xuyên: - Nếu một mẫu dãy X là mẫu dãy không thường xuyên thì mọi tập cha Y của nó (X ⊆ 𝑌) cũng là các mẫu dãy không thường xuyên 8 - Nếu một mẫu dãy X là mẫu dãy thường xuyên thì mọi tập con Z (Z≠ ∅) của nó (Z⊆ 𝑋) cũng là mẫu dãy thường xuyên Tính chất này của mẫu dãy thường xuyên gọi là tính chất đóng xuống (hay còn gọi là tính chất Apriori hoặc tính phản đơn điệu). Khai phá mẫu dãy thường xuyên Phần này trình bày các hướng tiếp cận của các thuật toán trong khai phá mẫu dãy thường xuyên và giới thiệu 2 thuật toán kinh điển: GSP [3] và PrefixSpan [6] làm cơ sở cho các thuật toán ở các chương sau.
Nhiệm vụ của khai phá mẫu dãy thường xuyên là tìm tập hợp tất cả các mẫu dãy thường xuyên trong CSDL dãy. Bài toán khai phá mẫu dãy thường xuyên là một bài toán liệt kê. Trọng tâm là liệt kê tất cả các mẫu dãy có độ hỗ trợ lớn hơn hoặc bằng với ngưỡng hỗ trợ tối thiểu đặt bởi người dùng. Tìm mẫu dãy thường xuyên là một bài toán khó.
Để giải quyết nó, phương pháp tiếp cận tự nhiên nhất là tính độ hỗ trợ của tất cả các mẫu dãy con có thể có trong CSDL và liệt kê tất cả các mẫu dãy có độ hỗ trợ không nhỏ hơn ngưỡng tối thiểu. Tuy nhiên, cách tiếp cận ngây thơ như vậy không hiệu quả vì số lượng các mẫu dãy con có thể rất lớn. Một dãy chứa q mục trong CSDL có thể có tới 2q - 1 mẫu dãy con khác nhau. Vì vậy, việc áp dụng phương pháp tiếp cận ngây thơ như vậy thường không hiệu quả, do đó không thể áp dụng trong thực tế.
Đã có rất nhiều thuật toán được thiết kế để giải quyết bài toán khai phá mẫu dãy thường xuyên. Một số thuật toán nổi tiếng có thể kể tới là GSP [3], PrefixSpan [6], Spade [5], Spam [4], bitSpade [7], Prims [8], FreeSpan [9]. Các thuật toán này có đầu vào là một cơ sở dữ liệu dãy và một ngưỡng hỗ trợ tối thiểu (được đặt bởi người dùng) và đầu ra là tập tất cả các mẫu dãy thường xuyên. Không gian tìm kiếm của tất cả mẫu dãy con có thể sinh ra trong một 9 cơ sở dữ liệu dãy có thể rất lớn, vì vậy các thuật toán cần phải sử dụng các kỹ thuật để tránh quét toàn bộ không gian tìm kiếm.
Cơ chế cơ bản nhất để tỉa không gian tìm kiếm trong khai phá mẫu dãy thường xuyên là sử dụng tính chất đóng xuống. Tính chất này chỉ ra rằng với bất kỳ dãy sa và sb nào, nếu sa là dãy con của sb thì sb phải có độ hỗ trợ nhỏ hơn hoặc bằng với sa. Tính chất này rất hiệu quả để tỉa bớt không gian tìm kiếm, vì nếu một mẫu dãy không phải là mẫu dãy thường xuyên thì tất cả các mẫu dãy cha của nó đều sẽ có độ hỗ trợ nhỏ hơn ngưỡng tối thiểu nghĩa là không phải là mẫu dãy thường xuyên. Ví dụ, với cơ sở dữ liệu tại Bảng 1.1 và ngưỡng tối thiểu minsup =2, ta có dãy <c,g> có độ hỗ trợ là 1 là một mẫu dãy không thường xuyên.
Tất cả các dãy cha của nó ví dụ như <c,g,e> đều không phải là mẫu dãy thường xuyên. Tính chất đóng xuống do đó có thể làm giảm đáng kể không gian tìm kiếm của các mẫu dãy.