Khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian

TỔNG QUAN VỀ LĨNH VỰC NGHIÊN CỨU VÀ CƠ SỞ LÝ THUYẾT

Giới thiệu

Khai thác dữ liệu là quá trình tìm kiếm các mẫu và thông tin tiềm ẩn trong khối lượng dữ liệu lớn, giúp dự đoán xu hướng tương lai và hỗ trợ các công ty trong việc ra quyết định kịp thời dựa trên sự kiện quá khứ Với những ưu điểm này, khai thác dữ liệu được ứng dụng rộng rãi trong nhiều lĩnh vực như thương mại, tài chính, y học và giáo dục Thuật ngữ khai thác dữ liệu còn được gọi là khai thác tri thức trong cơ sở dữ liệu (KDD), là việc tự động trích xuất tri thức chưa được nhận ra từ các tập dữ liệu lớn.

Trong khai thác dữ liệu, có nhiều phương pháp tiếp cận khác nhau, bao gồm khai thác luật kết hợp, khai thác mẫu phổ biến và khai thác mẫu có tính chu kỳ.

Khai thác luật kết hợp là một phần quan trọng trong khai thác dữ liệu, giúp xác định mối quan hệ giữa các sản phẩm trong cơ sở dữ liệu giao dịch Phương pháp này tập trung vào việc khách hàng có mua hay không mua sản phẩm, đồng thời nhận thức rằng mỗi sản phẩm có giá trị và trọng số khác nhau tùy thuộc vào từng cơ sở dữ liệu cụ thể Do đó, việc khai thác dữ liệu với trọng số thực tiễn mang lại hiệu quả cao hơn trong việc phân tích hành vi của khách hàng.

Năm 1998, Ramkumar và các cộng sự cùng với Cai và các cộng sự đã đề xuất một mô hình để mô tả khái niệm khai thác luật kết hợp có trọng số, dựa trên thuật toán Apriori nhằm tìm ra các mẫu phổ biến có trọng số Kể từ đó, nhiều kỹ thuật khai thác luật kết hợp có trọng số đã được giới thiệu, bao gồm các nghiên cứu của Wang và các cộng sự cũng như Tao và các cộng sự.

2.1.1 Tổng quan về khai thác luật kết hợp

Trong khai thác dữ liệu, mục đích của khai thác luật kết hợp (Assosiation Rule –

AR (Luật kết hợp) là phương pháp phân tích nhằm phát hiện các mối quan hệ giữa các đối tượng trong khối lượng dữ liệu lớn Nội dung chính của luật kết hợp tập trung vào việc xác định các mẫu và quy luật ẩn trong dữ liệu, giúp tối ưu hóa quá trình ra quyết định và nâng cao hiệu quả kinh doanh.

Cho CSDL gồm các giao dịch T = {t 1 , t 2 ,…, t n }

Cho I = {i 1 , i 2 ,…, i n } là một tập các item Mỗi tập con trong I được gọi là một itemset, số lượng các phần tử trong một itemset được gọi là kích thước của một itemset

Mục đích của luật kết hợp là tìm ra sự kết hợp hay tương quan giữa các items

Cho X và Y là hai itemsets, trong đó X và Y là hai tập không giao nhau khác rỗng Một luật kết hợp X → Y, thể hiện mối ràng buộc của tập Y với tập X theo nghĩa là sự xuất hiện của tập X sẽ kéo theo sự xuất hiện của tập Y trong các giao dịch, có thể hiểu rằng những người mua các mặt hàng trong tập X cũng thường mua các mặt hàng trong tập Y Ví dụ, nếu X= {Nhãn, Chôm Chôm} và Y= {Măng Cụt, Mít} và ta có luật kết hợp X → Y thì ta có thể nói rằng những người mua Nhãn và Chôm Chôm thì cũng thường mua Măng Cụt và Mít

Tập X được gọi là xuất hiện trong giao dịch t nếu như nó là tập con của T Độ hỗ trợ và độ tin cậy là hai tham số dùng để đo lường luật kết hợp

Thuật toán Apriori là phương pháp cơ bản để tìm kiếm các luật kết hợp nhị phân Theo định nghĩa, độ hỗ trợ (sup) của luật kết hợp X → Y được xác định là tần suất giao dịch chứa tất cả các item trong cả hai tập X và Y Chẳng hạn, nếu độ hỗ trợ của luật X → Y là 50%, điều này có nghĩa là 50% các giao dịch có chứa cả X và Y được mua cùng nhau.

Trong đó n (X∪Y)là số giao dịch có chứa X và Y, N là tổng số giao dịch trong

CSDL Định nghĩa 2.2: Độ tin cậy (conf) là xác xuất xảy ra Y khi đã biết X

Ví dụ độ tin cậy của {Nhãn} → {Chôm Chôm} là 90% có nghĩa là 90% khách hàng mua {Nhãn} cũng sẽ mua {Chôm Chôm}

Để thu được các luật kết hợp, chúng ta thường sử dụng hai tiêu chí quan trọng là độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf), đây là những giá trị ngưỡng tối thiểu được xác định trước.

Luật kết hợp X → Y được xem là một mẫu có giá trị nếu xảy ra đồng thời:

Sup (X → Y) ≥ minsup và Conf (X→Y) ≥ minconf

Một tập X có độ hỗ trợ vượt ngưỡng minsup được gọi là một tập phổ biến Định nghĩa 2.3: Lớp tương đương

Cho XI, ta định nghĩa hàm p(X,k)=X[1,k] gồm k phần tử đầu của X và quan hệ tương đương dựa vào tiền tố sau:

Tập hợp tất cả itemset có cùng tiền tố là X gọi là lớp tương đương và được ký hiệu là [X]

Trong mối quan hệ giữa hai ngôi δ I  T, với I là tập hợp các danh mục và T là tập hợp các giao dịch, ta có thể định nghĩa hai ánh xạ giữa P(I) và P(T) thông qua việc chọn X  I và Y  T.

II i:P(T) ↦ P(I),i(Y)={x ∈ 𝐼|∀𝑦 ∈ 𝑌, 𝑥𝛿𝑦} Ánh xạ t(X) là tập hợp tất cả các giao dịch có chứa X trong CSDL giao dịch, và ánh xạ i(Y) là tập hợp tất cả các items chứa trong tất cả giao dịch Y

Cho X, X 1 , X 2 ∈ P(I) và Y, Y 1 , Y 2 ∈ 𝑃(𝑇) Dựa theo kết nối Galois [6] ta có các tính chất sau:

Khai thác luật kết hợp chia làm hai giai đoạn:

- Khai thác mẫu phổ biến ( FPs - Frequent Partems)

- Khai thác luật từ các mẫu phổ biến (ARs – Association Rules) Định nghĩa 2.4: Luật kết hợp

Luật kết hợp là một phép kéo theo có dạng X→Y\X (p,q), với X và Y là các mẫu phổ biến, trong đó X và Y không rỗng, X là tập con của Y Độ tin cậy của luật được xác định bởi p = Sup(Y)/Sup(X) ≥ minconf, trong khi độ phổ biến của luật được thể hiện qua q = sup(Y) ≥ minsup.

Như vậy: Luật kết hợp là luật sinh ra giữa các mẫu phổ biến X, Y ∈ FPs trong đó X  Y

Thuật toán Apriori, được Agrawal và các đồng sự đề xuất vào năm 1993, dựa trên nguyên tắc rằng nếu một mẫu danh mục là phổ biến, thì tất cả các mẫu con của nó cũng phải phổ biến Điều này có nghĩa là không thể có một mẫu phổ biến mà lại có mẫu con không phổ biến; do đó, một mẫu phổ biến với nhiều danh mục hơn chỉ có thể được hình thành từ các mẫu phổ biến với ít danh mục hơn Vào năm 1994, Agrawal đã phát triển phương pháp sinh ứng viên Apriori, tập trung vào việc tạo ra các ứng viên dựa trên nguyên tắc này.

- Tìm tất cả các mẫu phổ biến có thể có trong CSDL: k-itemset (tập danh mục gồm k phần tử) được dùng để tìm (k+1)-itemset

- Đầu tiên tìm 1-itemset (ký hiệu L 1 ) L 1 dùng để tìm L 2 (2-itemset) L 2 dùng để tìm L 3 (3-itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy

- Từ mẫu phổ biến sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn minsup và minconf)

Phương pháp Apriori sử dụng cách tiếp cận lặp, được gọi là tìm kiếm theo mức, để khám phá các tập hợp dữ liệu Các tập có kích thước k, được gọi là k-itemset, được sử dụng để tìm kiếm các tập có kích thước k+1, hay còn gọi là (k+1)-itemset.

Tính chất 2.1: Mọi mẫu con của mẫu phổ biến đều phổ biến, nghĩa là XY, nếu 𝜎(Y) ≥ minsup thì 𝜎(X) ≥ minsup

Tính chất 2.2: Mọi mẫu cha của mẫu không phổ biến đều không phổ biến, nghĩa là YX, nếu 𝜎(X) < minsup thì 𝜎(Y) < minsup

Các bước của phương pháp Apriori

Tổng quan về khai thác luật kết hợp trên CSDL có xét đến trọng số

2.2.1 Định nghĩa và tính chất của mẫu có trọng số

Cơ sở dữ liệu giao dịch của tập mẫu được đánh số bao gồm tập các giao dịch

T = {t 1 , t 2 , , t m ); một tập các item I = {i 1 , i 2 ,…, i n } và tập các trọng số W = {w 1 , w 2 ,

…, w n } tương ứng với mỗi một item có trong I

Bảng 2.10 Cơ sở dữ liệu D1

Từ mức 3: d(PXY) = d(PY) – d(PX)

Hình 2.7 Cây IT-Tree dùng diffset với minsup = 50%

Bảng 2.11 Trọng số các items của CSDL D1

Trọng số giao dịch (transaction weight - tw) của một giao dịch t k được định nghĩa là tỷ số giữa tổng trọng số của các items trong giao dịch và số lượng item Cụ thể, công thức tính trọng số giao dịch là: tw(t k) = ∑ 𝑖𝑗∈𝑡𝑘 𝑤 𝑗.

Khai thác mẫu phổ biến có trọng số ta quan tâm đến trọng số (weight hay benefit) của các mặt hàng, ta chưa quan tâm đến số lượng mua

Dựa vào số liệu của CSDL D1 (Bảng 2.10) và định nghĩa 2.2.1 ta tính được trọng số giao dịch của giao dịch t 1 như sau:

Ta có t 1 = {A, B, D, E} tương ứng với W A =0.6, W B =0.1; W D =0.9, W E =0.2; ta suy ra tw(t 1 ) được tính như sau: tw(t1) = 𝑊 𝐴 +𝑊 𝐵 +𝑊 𝐷 +𝑊 𝐸

4 = 0.45 Tương tự với các giao dịch t2 đến t6 ta có:

Bảng 2.12 Trọng số của từng giao dịch của CSDL D1

4 0.3 Định nghĩa 2.2.2: Trọng số hỗ trợ được ký hiệu là ws của một mẫu phổ biến được định nghĩa như sau: ws(X) = ∑ 𝑡𝑘∈𝑡(𝑋) 𝑡𝑤(𝑡 𝑘 )

Trong đó t là danh sách của tất cả các giao dịch có trong CSDL

Dựa vào định nghĩa 2.2.2 và thông tin từ Bảng 2.12, chúng ta có thể tính toán trọng số hỗ trợ cho từng mẫu phổ biến Cụ thể, khi xem xét item A, nó xuất hiện trong các giao dịch t1, t3, t4 và t5 Do đó, trọng số hỗ trợ của item A được tính bằng công thức: ws(A) = tw(t1) + tw(t3) + tw(t4) + tw(t5).

Để khai thác các mẫu phổ biến có trọng số, cần xác định tất cả các trọng số hỗ trợ tương ứng với từng mẫu phổ biến, đáp ứng yêu cầu của ngưỡng trọng hỗ trợ tối thiểu (minws) mà người dùng đặt ra Theo định lý 2.2.1, mọi mẫu con khác rỗng của mẫu phổ biến cũng sẽ là mẫu phổ biến, trong khi mọi mẫu chứa mẫu không phổ biến sẽ là mẫu không phổ biến Điều này có nghĩa là nếu X là tập con của Y, thì ws(X) sẽ lớn hơn hoặc bằng ws(Y), đảm bảo thuộc tính bao đóng.

2.2.2 Thuật toán khai thác mẫu phổ biến dựa trên WIT-Tree

2.2.2.1 Tìm hiểu về cấu trúc WIT-tree

Sum 2.25 item Weight support (ws)

Khi nghiên cứu khai thác luật kết hợp có trọng số, bước đầu tiên là xác định tất cả các mẫu có trọng số thỏa mãn ngưỡng trọng số tối thiểu Quá trình khai thác các mẫu phổ biến có trọng số được coi là yếu tố quan trọng nhất trong việc phát triển luật kết hợp có trọng số Năm 1998, Ramkumar và các cộng sự đã đề xuất một thuật toán khai thác mẫu phổ biến có trọng số dựa trên thuật toán Apriori.

Một trong những nhược điểm lớn nhất của các thuật toán dựa trên Apriori là yêu cầu quét cơ sở dữ liệu nhiều lần để xác định các mẫu phổ biến, điều này dẫn đến chi phí cao.

Năm 2003, Tao và đồng sự [5] đã đề xuất phương pháp khai thác WAR

The Weighted Association Rule algorithm employs a variant of the Apriori algorithm to mine transaction databases while considering the weights of items This approach enhances the relevance of recommendations by incorporating item significance into the analysis, ultimately improving the quality of insights derived from transactional data.

In 2013, Vo and colleagues introduced a rapid mining method for Frequent Weighted Itemsets (FWI) utilizing WIT-tree, enhancing various properties associated with this approach.

WIT-tree để tính nhanh ws của các tập mẫu itemsets

Giải thuật khai thác mẫu phổ biến có trọng số dựa trên cấu trúc WIT-tree

The Weighted Itemset Tidset (WIT-tree) is an extension of the IT-tree structure discussed in section 2.1.4 Each node in the WIT-tree comprises three components, enhancing its functionality and efficiency in data representation.

1) X: đại diện cho tập mẫu phổ biến

2) t(X): Tidset tập hợp các giao dịch có chứa X

3) ws: trọng số hỗ trợ của X

Mỗi một nút được ký hiệu như là một bộ ba

Giá trị của mỗi node được xác định thông qua công thức trọng số hỗ trợ, dựa trên các Tidset Việc tính toán trọng số hỗ trợ liên quan đến các liên kết giữa các nút ở mức k (gọi là X) và các nút ở mức k+1 (gọi là Y).

Nút gốc “root” của cây WIT-tree chứa tất cả các nút có kích thước là 1 gọi là

1-itemset Tất cả các nút ở mức 1 sẽ trở thành lớp tương đương với tiền tố là {} (hay

Mỗi nút ở mức 1 sẽ chuyển thành một lớp tương đương mới, sử dụng các items như tiền tố Những nút có cùng tiền tố sẽ kết hợp với các nút phía sau để tạo ra các lớp tương đương mới Quá trình này được thực hiện đệ quy để xác định các lớp tương đương ở các mức cao hơn.

Bước 1: Tạo tập L chứa tất cả các mẫu có trọng số và kích thước 1, với trọng số hỗ trợ của chúng đáp ứng điều kiện ngưỡng trọng số hỗ trợ tối thiểu minws.

Bước 2: Các nút chứa trong L r được sắp xếp theo thứ tự tăng dần dựa trên trọng số hỗ trợ

Bước 3: Khởi tạo tập FWI và gán nhãn “null”

Bước 4: Gọi hàm FWI-EXTEND để khai thác các mẫu có trọng số Hàm này xem xét từng nút L i trong L r cùng với các nút phía sau để tạo ra tập hợp mới L i Đầu tiên, xác định X = l i.itemset ∪ l j.itemset và tính toán Y = t(X) = t(l i) ∩ t(l j) Nếu ws(X) được tính qua t(X) thỏa mãn điều kiện minws, nút mới sẽ được thêm vào tập L i Sau khi hoàn thành, hàm sẽ trả về kết quả.

Hàm FWI-EXTEND sẽ được gọi đệ qui với biến đầu vào là L i, khi số lượng nút trong tập L i lớn hơn 1 Hàm COMUTE-WS(Y) được sử dụng để tính toán trọng số hỗ trợ của mẫu X dựa trên giá trị trong Bảng 2.12, với Y = t(X) Đầu vào bao gồm cơ sở dữ liệu D1 và minws (ngưỡng trọng số hỗ trợ tối thiểu), trong khi đầu ra là tập FWI chứa tất cả các mẫu phổ biến có trọng số thỏa mãn minws.

1 L r = tất cả các item mà ws thỏa minws

2 Sắp xếp các nút trong L r tăng dần theo ws

4 Gọi hàm FWI-EXTEND với tham số là L r FWI-EXTEND( L r )

6 Chèn (l i itemset, l i ws) vào trong FWI

7 Tạo một tập L i bằng cách nối l i với l j theo sau trong L r

10 Nếu ws(X) thỏa minws khi đó

11 Chèn nút vào trong L i

12 Nếu số lượng nút trong L i ≥ 2, khi đó

13 Gọi đệ qui hàm FWI-EXTEND với biến L i

Quá trình khai thác các mẫu phổ biến có trọng số trong cơ sở dữ liệu D1 được thực hiện theo Bảng 2.10 và sử dụng Bảng 2.11 với ngưỡng trọng số hỗ trợ tối thiểu là minws = 0.5, được trình bày một cách chi tiết.

Trong bước đầu tiên, trọng số hỗ trợ của các mẫu có kích thước 1 được tính toán và khởi tạo L r, với các giá trị cụ thể là ws(A)=0.72, ws(B)=1, ws(C)=0.6, ws(D)=0.78, và ws(E)=0.81 Tất cả các mẫu kích thước 1 đều đạt giá trị trọng số hỗ trợ thỏa mãn điều kiện minws, tạo thành một tập hợp nhất định.

Tiếp theo ta tiến hành sắp xếp L r theo thứ tự tăng dần của trọng số hỗ trợ, chúng ta có L r = {, , , ,

Ta tiến hành khởi tạo lớp {} chứa các tập có kích thước là 1

Bước 2: Thực hiện tạo ra lớp tương đương mới dựa trên lớp tương đương cũ

Phương pháp khai thác mẫu có tính chu kỳ

Trong những năm gần đây, khai thác mẫu tuần tự đã trở thành một lĩnh vực nghiên cứu quan trọng trong khai thác thông tin Khái niệm này lần đầu tiên được giới thiệu bởi Agrawal, Faloutsos và Swami vào năm 1993, sau đó được phát triển thêm bởi Agrawal và Srikant vào năm 1994 Kể từ đó, đã có nhiều nghiên cứu sâu rộng về lĩnh vực này.

Khai thác mẫu có tính chu kỳ là một vấn đề quan trọng trong lĩnh vực khai thác dữ liệu, nhờ vào các ứng dụng đa dạng của nó Một chuỗi dữ liệu chu kỳ bao gồm sự kết hợp giữa các sự kiện có tính chu kỳ và không chu kỳ, được sắp xếp theo thứ tự thời gian lặp lại với tần suất cao trong một chuỗi sự kiện.

Khai thác mẫu có tính chu kỳ, khác với phương pháp khai thác mẫu tuần tự truyền thống, cho phép phân tích và phát hiện các mẫu chu kỳ trong chuỗi sự kiện Phương pháp này được chia thành hai loại: khai thác đầy đủ mẫu có tính chu kỳ và khai thác một phần mẫu có tính chu kỳ.

Ví dụ: Giả sử một chuỗi sự kiện “ababbbabacab” được đưa ra, chiều dài chu

0.59 Hình 2.11 Cây WIT-tree hoàn chỉnh của CSDL D1 với minws =0.5 kỳ là 2 và ngưỡng tối thiểu là 70% Đầu tiên, vì chiều dài đưa ra là 2 lên chuỗi sự kiện được chia thành sáu trình tự chu kỳ là: “ab”, “ab”, “bb”, “ab”, “ac”, “ab” Ngoài ra, chuỗi con “ab” xuất hiện ở các vị trí 1,2,4,6 trong các trình tự chu kỳ, đạt 4/6 được tính thành 66.67% Trong ví dụ này, ứng viên “ab” không phải là mẫu có tính chu kỳ trong khai thác đầy đủ mẫu có tính chu kỳ với chiều dài chu kỳ là 2

Khai thác đầy đủ mẫu có tính chu kỳ gặp hạn chế khi tất cả các sự kiện trong mẫu phải xuất hiện theo một thứ tự và thời gian nhất định với tỷ lệ cao Một số ứng viên có tính chu kỳ trong chuỗi sự kiện có thể không đạt ngưỡng hỗ trợ tối thiểu, dẫn đến việc không thể phát hiện bằng phương pháp này Để giải quyết vấn đề này, khai thác một phần mẫu có tính chu kỳ đã được đề xuất, cho phép các sự kiện không xác định được đại diện bởi ký hiệu “*” Ví dụ, ứng viên “a*” với chiều dài chu kỳ 2 trong sáu phân đoạn có độ phổ biến 83.33% và thỏa mãn mức hỗ trợ tối thiểu 70% Ngoài “a*”, “*b” cũng là mẫu có tính chu kỳ thỏa mãn điều kiện Nghiên cứu đã chỉ ra rằng tính chu kỳ có thể liên kết với một tập con của các điểm thời gian, cho thấy chuỗi dữ liệu có tính chu kỳ là sự kết hợp của các sự kiện có tính chu kỳ và không chu kỳ theo thứ tự thời gian Ví dụ, “Giá của chứng khoán tăng vào thứ tư” là một chu kỳ vì chỉ đề cập đến thứ tư mà không xét đến biến động giá trong tuần Trong khai thác mẫu dữ liệu có tính chu kỳ, “Giá tăng” và “một tuần” có thể được định nghĩa là sự kiện và khoảng thời gian tương ứng của chu kỳ.

Trong khai thác dữ liệu, việc xem xét lợi ích và tầm quan trọng của từng sản phẩm là rất cần thiết, đặc biệt khi người dùng quan tâm đến giá trị trọng số của chúng Ví dụ, lợi nhuận từ việc bán một ổ bánh mì chỉ là 200 đồng, trong khi bán một chai sữa có thể mang lại 400 đồng Mỗi sản phẩm và mục trong cơ sở dữ liệu giao dịch đều có trọng số khác nhau, do đó khai thác dữ liệu này có tính thực tiễn cao Năm 1998, Cai, Fu, Cheng và Kwong đã đề xuất mô hình khai thác luật kết hợp có trọng số dựa trên thuật toán Apriori để tìm ra các tập phổ biến có trọng số Nhiều kỹ thuật khai thác luật kết hợp có trọng số đã được phát triển, như của Wang, Yang, và Yu, cũng như Tao, Murtagh, và Farid Đến năm 2013, Vo, Coenen, và Le đã giới thiệu thuật toán khai thác mẫu có trọng số sử dụng WIT-tree và chiến lược Diffset.

Năm 2013, Jang và các cộng sự đã đề xuất một phương pháp khai thác mẫu có tính chu kỳ, tuy nhiên phương pháp này không xem xét đến trọng số.

Thuật toán khai thác mẫu có tính chu kỳ

Thuật toán khai thác mẫu có tính chu kỳ PPA được thiết kế để xử lý chuỗi sự kiện S với n sự kiện, chiều dài chu kỳ l và độ hỗ trợ tối thiểu minsup Kết quả của thuật toán này là một tập hợp đầy đủ các mẫu phổ biến có tính chu kỳ, gọi là PPPs.

Bước 1: Chia chuỗi sự kiện S với chiều dài chu kỳ l thành nhiều đoạn có tính chu kỳ, S=

Bước 2: Mã hóa từng sự kiện trong ps j thành bộ sự kiện et jk, kết hợp với vị trí của sự kiện trong ps j để tạo ra phân đoạn chu kỳ mã hóa eps j Tất cả các phân đoạn đã được mã hóa sẽ được tập hợp thành cơ sở dữ liệu của các phân đoạn chu kỳ mã hóa, gọi là EPSD.

Bước 3: Với mỗi k th thì bộ sự kiện et jk trong ep sj như bộ mẫu ứng viên, tìm giá trị hỗ trợ: sup ctp m fc ctp

; với sup ctp là độ phổ biến của bộ mẫu ứng viên và m là số đoạn có tính chu kỳ được mã hóa trong EPSD

Bước 4: Đối với mỗi bộ mẫu ứng viên CTP trong EPSD, nếu giá trị hỗ trợ thực tế lớn hơn hoặc bằng độ hỗ trợ tối thiểu minsup, hãy đưa nó vào tập bộ phổ biến mẫu một phần tử, FTP 1.

Bước 5: Thu thập các bộ sự kiện xuất hiện trong FTP 1 và loại bỏ những bộ sự kiện không có trong FTP 1 của EPSD

Bước 6: Đặt r=1, là đại diện cho số của bộ sự kiện trong các mẫu được xử lý

Bước 7: Xử lý mỗi bộ sự kiện X trong tập FTP 1 với vị trí số và thứ tự chữ cái của nó bởi các bước nhỏ sau:

Tìm kiếm các đoạn có tính chu kỳ trong EPSD, bao gồm cả X, và đưa các phân đoạn chu kỳ mã hóa vào cơ sở dữ liệu phân đoạn mã hóa EPSD X.

Tìm tất cả các bộ mẫu phổ biến với X là mẫu tiền tố bằng thủ tục finding-FTP(X, epsd X, r) Tập hợp các bộ mẫu được mã hóa lại thành FTP X.

Bước 8: Xuất ra tập tất cả các mẫu có tính chu kỳ một phần trong FTP X

Thủ tục finding-FTP(X, epsd X, r) nhận đầu vào là một mẫu tiền tố X với r phần tử và phân đoạn cơ sở dữ liệu đã được mã hóa tương ứng eps X Kết quả đầu ra của thủ tục này là các bộ mẫu phổ biến của mẫu tiền tố X, được ký hiệu là FTP X.

Bước đầu tiên là khởi tạo bộ mẫu tạm thời TTP X, tương tự như một bảng rỗng Mỗi bộ mẫu bao gồm hai trường: một trường chứa giá trị mẫu (value) và một trường chứa số lượng mẫu đếm được (count).

Bước 2: Với mỗi jth của phân đoạn esp j trong espd X , thực hiện các bước nhỏ sau:

(a) Lấy với mỗi bộ sự kiện et j tại vị trí sau X trong ps j

Khởi tạo bộ sự kiện X’ gồm các tiền tố của r phần tử X và et j, sau đó lưu X’ vào bảng TTP X (value) và tăng giá trị 1 trong trường (count) tương ứng của bảng TTP X.

Bước 3: Với mỗi bộ (r+1) sự kiện X’ trong TTP X , thực hiện các bước nhỏ sau:

(a) Tính giá trị hỗ trợ sup X’ của mẫu X’ với (r+1) sự kiện như sau: sup X’ m count X '

, với count X’ là giá trị trường count của X’ trong bảng

(b) Nếu giá trị hỗ trợ sup X’ của X’ lớn hơn hoặc bằng ngưỡng hỗ trợ tối thiểu  , đặt X’ vào tập bộ mẫu phổ biến (r+1)-pattern, FTP (r+1).X’

Bước 4: Đặt r=r+1, với r là số bộ sự kiện trong mẫu xử lý

Bước 5: Xử lý với mỗi mẫu X’ trong tập FTP r, X ở vị trí và thứ tự chữ cái của chúng bằng các bước nhỏ sau:

Kết luận chương

Chương này trình bày lý thuyết và phương pháp khai thác mẫu phổ biến có trọng số, bao gồm một thuật toán khai thác mẫu có tính chu kỳ Các thuật toán truyền thống thường giả định rằng tất cả các sự kiện trong chuỗi đều quan trọng như nhau, điều này không thực tế trong nhiều tình huống Khai thác mẫu có tính chu kỳ xét đến trọng số là một lĩnh vực nghiên cứu còn mới mẻ Giải pháp đề xuất là kết hợp khai thác mẫu có trọng số với khai thác mẫu có tính chu kỳ, nhằm xem xét trọng số của từng sự kiện trong chuỗi Chương tiếp theo sẽ đi sâu vào chi tiết giải pháp này.

THUẬT TOÁN KHAI THÁC MẪU CÓ TÍNH CHU KỲ XÉT ĐẾN TRỌNG SỐ TỪ DỮ LIỆU HƯỚNG THỜI GIAN

Mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian

3.1.1 Khái niệm về thời gian

Thời gian được mô tả qua một hệ thống lịch với nhiều độ chi tiết như giây, phút, giờ và ngày Chúng ta coi thời gian như một dòng thời gian tuyệt đối, trong đó mỗi mốc thời gian được biểu diễn bằng số tự nhiên, tương ứng với các khoảng thời gian thực Điều này cho phép ánh xạ các mốc thời gian của hệ thống lịch đến các khoảng liên tiếp của số thực, từ đó tạo điều kiện cho việc mô hình hóa dữ liệu theo thời gian và khai thác thông tin hữu ích.

Dữ liệu chứa các khoảng thời gian mà kỹ thuật khai thác luật kết hợp được áp dụng, với nhiều độ chi tiết thời gian khác nhau như giờ, ngày, tháng và quý Những thông tin này có thể mang lại giá trị hữu ích Nếu thời gian được biểu diễn bằng giây, một phút sẽ tương ứng với 60 giây, một giờ sẽ là 3600 giây, và các đơn vị thời gian khác cũng được quy đổi tương tự.

3.1.2 Khái niệm về cơ sở dữ liệu hướng thời gian

Thời gian là khái niệm diễn tả trình tự và khoảng kéo dài của các sự kiện Nó được xác định qua các chuyển động lặp lại và thường gắn liền với một thời điểm mốc Các loại thời gian khác nhau như thời gian có hiệu lực, thời gian giao dịch, và thời gian sự kiện cho phép chúng ta hiểu rõ hơn về các biến cố Cơ sở dữ liệu thời gian có thể chứa một hoặc nhiều khái niệm thời gian, và thời gian có thể được bổ sung vào bộ dữ liệu cũng như các thuộc tính quan hệ Các yếu tố như điểm thời gian, khoảng thời gian và bộ thời điểm có thể được sử dụng làm nhãn để đại diện cho thời gian tham khảo các giá trị.

Dữ liệu hướng thời gian là loại dữ liệu có thuộc tính mang yếu tố thời gian

Mô hình dữ liệu hướng thời gian cho phép tổ chức và phân tích các sự kiện hoặc dữ liệu theo chuỗi có trật tự thời gian Ví dụ như chuỗi mua sắm của khách hàng, chuỗi truy cập web, sự kiện khoa học, dữ liệu điều trị y tế, mẫu gọi điện thoại, thị trường chứng khoán, biến động giá dầu và tai nạn giao thông Đặc điểm nổi bật của dữ liệu hướng thời gian là tính thứ tự, giúp thể hiện rõ mối quan hệ xuyên suốt giữa các dữ liệu qua thời gian.

Chu kỳ được định nghĩa là khoảng thời gian giữa hai lần lặp lại liên tiếp của một sự việc hoặc thời gian để hoàn thành một vòng quay Đơn vị đo chu kỳ là đơn vị đo thời gian, và thời gian tại một điểm cụ thể trong chu kỳ được gọi là mốc thời gian (time slot) Mỗi chu kỳ sẽ có các mốc thời gian khác nhau tùy thuộc vào đơn vị đo thời gian được sử dụng.

Trong chu kỳ tuần, nếu tính theo ngày trong tuần, sẽ có bảy mốc thời gian: Thứ Hai, Thứ Ba, Thứ Tư, Thứ Năm, Thứ Sáu, Thứ Bảy và Chủ Nhật Tuy nhiên, khi phân loại thời gian đo theo ngày làm việc và ngày cuối tuần, chu kỳ tuần chỉ còn hai mốc thời gian chính là Ngày làm việc và Cuối tuần.

Mon Tue Wed Thu Fri Sat Sun

3.1.4 Khái niệm mẫu trong khai thác mẫu có tính chu kỳ

Trong khai thác mẫu có tính chu kỳ, một mẫu có thể chứa một hoặc nhiều sự kiện (item) Mỗi item bao gồm hai thành phần chính: giá trị của item và giá trị mốc thời gian (time slot).

Hình 3.2 Mô tả một item của mẫu trong khai thác mẫu có tính chu kỳ

CSDL click stream là các file log ghi lại thông tin về khách hàng khi họ truy cập và xem sản phẩm trên website của cửa hàng điện tử Những thông tin này bao gồm thời gian truy cập, địa chỉ IP của người dùng và các trang mà họ đã truy cập.

Chu kỳ được định nghĩa là các ngày trong tuần từ thứ Hai đến Chủ Nhật, với tổng cộng 29 trang truy cập Từ đó, chúng ta có thể xây dựng một bộ gồm 203 items (7 X 29) Dưới đây là bảng giá trị mô tả một số item.

Bảng 3.1 Ví dụ về các Item trong khai thác mẫu có tính chu kỳ

1 Sun Sun_dt, sun_lt, sun_df, sun_findf, sun_findp, …

2 Mon Mon_dt, mon_lt, …

7 Sat Sat_dt, sat_lt, …

Một chu kỳ “Tuần” với hai quy định thời gian khác nhau

Mốc thời gian (time slot)

Hình 3.1 Mô tả một chu kỳ

Phương pháp khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian đề xuất

từ dữ liệu hướng thời gian đề xuất

Nghiên cứu khai thác mẫu có tính chu kỳ cho thấy rằng tất cả các mục đều có giá trị như nhau, điều này có thể dẫn đến việc bỏ qua những mẫu quan trọng mà thuật toán PPA không thể xử lý Do đó, việc khai thác mẫu có tính chu kỳ với trọng số là cần thiết để nâng cao hiệu quả trong khai thác dữ liệu.

Nghiên cứu gần đây của Vo và đồng sự [6] đã giới thiệu một phương pháp khai thác mẫu phổ biến có trọng số dựa trên WIT-tree Từ những kết quả này, luận văn đề xuất một phương pháp khai thác mẫu chu kỳ, chú trọng đến trọng số từ dữ liệu hướng thời gian Tổng quan về giải pháp được trình bày một cách rõ ràng và chi tiết.

Giai đoạn 1 – Giai đoạn mã hóa: Chuyển đổi dữ liệu đầu vào theo hướng thời gian thành kiểu dữ liệu giao tác, giúp tận dụng các thuật toán khai thác mẫu phổ biến có trọng số hiện có.

Giai đoạn 2 – Khai thác mẫu sử dụng thuật toán WIT-FWI, một phương pháp hiệu quả để phân tích dữ liệu đã được chuyển đổi, với trọng số từ các mẫu phổ biến.

Giai đoạn 3, hay còn gọi là giai đoạn giải mã, là bước quan trọng trong quá trình phân tích dữ liệu Tại đây, từ tập mẫu phổ biến, chúng ta tiến hành diễn dịch để xác định những mẫu có tính chu kỳ trong bộ dữ liệu hướng thời gian ban đầu.

Giải pháp đề xuất trong luận văn tập trung vào giai đoạn 1 và giai đoạn 3 (Encode và Decode), thể hiện tính mới của nghiên cứu Trong giai đoạn 2, để khai thác mẫu phổ biến có trọng số từ dữ liệu giao dịch, có thể sử dụng bất kỳ thuật toán nào, nhưng thuật toán WIT-FWI được lựa chọn do hiệu quả cao trong việc thực hiện khai thác mẫu này.

Luận văn này đề xuất một quy trình tổng quát để khai thác mẫu có tính chu kỳ từ dữ liệu hướng thời gian, sử dụng các giải thuật khai thác mẫu phổ biến có trọng số và kết hợp với quy trình mã hóa dữ liệu thành dữ liệu giao dịch Quy trình này bao gồm việc diễn dịch mẫu phổ biến thành mẫu có tính chu kỳ thông qua các bước Encode và Decode Để minh họa rõ hơn về quy trình khai thác mẫu có tính chu kỳ, hình ảnh bên dưới sẽ trình bày chi tiết quá trình thực hiện giải pháp đề xuất Phần tiếp theo sẽ trình bày cụ thể các bước trong quy trình khai thác mẫu có tính chu kỳ này.

Hình 3.3 Quy trình khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian

Dữ liệu hướng thời gian

Tập mẫu có tính chu kỳ

Khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian

3.3.1 Mã hóa dữ liệu có tính thời gian thành dữ liệu giao tác

Giai đoạn này chuyển đổi dữ liệu đầu vào từ dạng dữ liệu hướng thời gian thành dữ liệu giao tác.

Ta gọi giai đoạn này là Encode

Giả sử ta có cấu trúc dữ liệu đầu vào (temporal data) như sau:

Id1 Id2 Id3 Idn t1 t1 t2 tn link1 link2 link 3 link 1

Hình 3.4 Mô tả kiểu dữ liệu hướng thời gian

Dữ liệu hướng thời gian được mô phỏng từ cơ sở dữ liệu là các file log ghi lại thông tin khách hàng khi truy cập vào trang web của cửa hàng bán đồ điện tử Mỗi ID trong file đại diện cho một khách hàng, kèm theo time stamp ghi lại thời gian truy cập Thuộc tính Attribute chứa các giá trị link1 đến link10, phản ánh các trang sản phẩm mà khách hàng đã truy cập trên website.

Giá trị "Time stamp" được xác định dựa trên định nghĩa chu kỳ, với các giá trị cụ thể là các Time slot Nếu chu kỳ được định nghĩa là các ngày trong tuần, thì các Time slot sẽ bao gồm Chủ nhật, Thứ hai, đến Thứ bảy, tương ứng với các giá trị số từ 1 đến 7.

Giá trị Atribute giả sử có mười giá trị khác nhau, tương ứng với giá trị số từ

Khi kết hợp "Time slot" và "Attribute", chúng ta sẽ tạo ra 70 hạng mục khác nhau, tương ứng với 70 Items trong dữ liệu hướng thời gian ban đầu.

Các thành phần dữ liệu được mô tả như các bảng dưới:

Bảng 3.2 Mô tả Time slot trong dữ liệu hướng thời gian

Bảng 3.3 Mô tả Attribute trong dữ liệu hướng thời gian

Attribute A.value Weight Detail of Attribute

Findf 6 3 Fulltext search for product and accesories

Znacka 8 4 List of brand names or brand detail

Kantakt 9 5 Textual information; contact info

Kosik 10 5 Shopping card; detail of contact; submitting order

Bảng 3.4 Mô tả Items của dữ liệu hướng thời gian

Time slot+Attribute Sunday Home Sunday Ct Saturday Kosik

Từ các trường T.value và A.value trong mô tả dữ liệu đầu vào, chúng ta có thể tính toán các Items cụ thể Để có được các Items có chiều dài 3 con số từ giá trị của T.value và A.value, ta thực hiện theo công thức đã định.

Items đầu vào được chuyển theo kiểu Items có giá trị kiểu số (Bảng 3.5)

Bảng 3.5 Mô tả cách xây dựng Items cho dữ liệu giao tác

Time slot+Attribute Sunday Home Sunday CT Saturday Kosik

Bước này giúp tạo danh mục các Items có giá trị số, thuận lợi cho quá trình khai thác dữ liệu Tuy nhiên, dữ liệu đầu vào cần có tính chu kỳ và mỗi Item cần có một trọng số hỗ trợ cụ thể Có nhiều phương pháp để gán trọng số cho các Items, và dưới đây là một cách gán trọng số cho danh sách này.

Trong quy trình gán trọng số cho các Items, trọng số được tính bằng tổng trọng số của T.value và A.value Để thực hiện điều này, cần xác định giá trị trọng số cho từng T.value và A.value Theo mô tả dữ liệu đã nêu, giá trị trọng số cho từng Items được trình bày trong Bảng 3.6.

Bảng 3.6 Mô tả Items và trọng số tương ứng của dữ liệu

Item (String) Sun_Home Sun_Ct Mon_Findf Mon_Setp Sat_Kosik

Quá trình chuyển đổi dữ liệu thành công dẫn đến việc tạo ra một bộ dữ liệu giao dịch có trọng số Từ bộ dữ liệu này, chúng ta có thể áp dụng các thuật toán hiện có để khai thác mẫu phổ biến có trọng số Trong phần tiếp theo, chúng ta sẽ khám phá chi tiết về thuật toán khai thác mẫu có trọng số.

3.3.2 Thuật toán khai thác mẫu phổ biến có trọng số Để khai thác mẫu phổ biến có trọng số có nhiều giải thuật để thực hiện Tuy nhiên với giải pháp của Vo và đồng sự trong [6] ứng dụng WIT-tree vào khai thác mẫu phổ biến có nhiều ưu điểm vượt trội Để thực hiện giải pháp đề xuất về khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian, giải thuật WIT-FWI trong [6] được chọn để khai thác mẫu có trọng số

Trong giai đoạn mã hóa, dữ liệu đầu vào từ các chuỗi thời gian được chuyển đổi thành dữ liệu giao tác, tạo nền tảng cho thuật toán khai thác mẫu phổ biến có trọng số dựa trên WIT-tree.

Thuật toán WIT-FWI sử dụng cơ sở dữ liệu D1 và ngưỡng trọng số hỗ trợ tối thiểu (minws) để tạo ra tập FWI Tập FWI này bao gồm các mẫu phổ biến có trọng số đáp ứng tiêu chí minws.

1 Lr = tất cả các item mà ws thỏa minws

2 Sắp xếp các nút trong Lr tăng dần theo ws

4 Gọi hàm FWI-EXTEND với tham số là Lr

5 Với mỗi nút li trong Lr

6 Chèn (li.itemset, li.ws) vào trong FWI

7 Tạo một tập Li bằng cách nối li với lj theo sau trong Lr:

8 Tập X = li.itemset ∪ lj.itemset và Y = t(li) ∩ t(lj)

10 Nếu ws(X) thỏa minws khi đó

11 Chèn nút vào trong Li

12 Nếu số lượng nút trong Li ≥ 2, khi đó

13 Gọi đệ qui hàm FWI-EXTEND với biến Li

Từ thuật toán trên, ta tiến hành khai thác với CSDL D1 (Bảng 2.10) và bảng trọng số của từng item trong (Bảng 2.11) với ngưỡng trọng số tối thiểu minws = 0.4

Từ CSDL D1 và bảng (Bảng 2.11) áp dụng công thức: tw(t k ) = ∑ 𝒊𝒋∈𝒕𝒌 𝒘 𝒋

|𝒕 𝒌 | (Trong định nghĩa 2.2.1) ta tính ra được trọng số của từng giao dịch như bảng sau:

Bảng 3.7 Trọng số giao dịch của từng giao dịch trong CSDL D1 Áp dụng công thức: ws(X) = ∑ 𝒕𝒌∈𝒕(𝑿) 𝒕𝒘(𝒕 𝒌 )

∑ 𝒕𝒌∈𝑻 𝒕𝒘(𝒕 𝒌 ) (Trong định nghĩa 2.2.2) ta tính được bảng trọng số hỗ trợ cho các mẫu phổ biến một phần tử như sau:

Bảng 3.8 Bảng trọng số hỗ trợ của mẫu phổ biến 1 phần tử

Dựa vào dữ liệu từ Bảng 2.10 và Bảng 3.7, thuật toán WIT-FWI được thực hiện với các bước sau: Đầu tiên, chúng ta tính trọng số hỗ trợ cho các mẫu có kích thước 1 và khởi tạo L r Kết quả thu được là ws(A)=0.72, ws(B)=1, ws(C)=0.6, ws(D)=0.78, ws(E)=0.81 (xem Bảng 3.8) Tất cả các giá trị trong các tập này đều đáp ứng điều kiện minws.

Suy ra ra có tập: L r = {, , ,

Sau đó ta tiến hành sắp xếp L r theo thứ tự tăng dần của trọng số hỗ trợ, ta có:

} Tiến hành khởi tạo lớp {} chứa các tập có kích thước là 1

Kế tiếp: Tiến hành tạo ra lớp tương đương mới dựa trên lớp tương đương cũ

Tạo tập L C và tiến hành nối C với A để tạo mẫu mới CA với t(CA) = 45 và ws(CA) = 0.32 Tuy nhiên, vì ws(CA) không đạt yêu cầu tối thiểu, nên không được phép thêm CA vào tập L C.

Tiếp tục tiến hành ghép C với D, mẫu mới CD với t(CD) = 56 và ws(CA) = 0.38 cũng không thỏa minws Tiếp tục ghép C với E ta có t(CE) = 245 và ws(CE) =0.41 > minws

Thêm CE vào tập L C và tiến hành ghép C với B, ta có t(CB) = 2456 và ws(CB) = 0.6 Kết quả cuối cùng sau khi ghép nút C với các nút còn lại là tập L C = {, } Do số lượng các nút trong L C nhiều hơn 1, ta gọi đệ quy hàm FWI-EXTEND để tạo ra các nút con của tập L C Khi ghép CE với CB, ta có t(CEB) = 245 và ws(CEB) = 0.41, thỏa mãn minws, do đó ta thêm mẫu CEB vào tập L CE, tạo thành L CE = {}.

Hình 3.5 Khởi tạo lớp tương đương rỗng cho WIT-tree

Hình 3.6 WIT-tree với tập L C cùng tập con của nó L CE

Tiếp Theo: Ta tiến hành thực hiện tiếp đối với các nút còn lại để tìm ra tất cả các tập

FWI thỏa điều kiện minws

Quá trình khai thác cơ sở dữ liệu từ Bảng 2.10 và Bảng 3.7 đã cho ra tập kết quả FWI với minws=0.4, bao gồm các phần tử: FWI = {C, CE, CEB, CB, A, AD, ADE, ADEB, ADB, AE, AEB, AB, D, DE, DEB, DB, E, EB, B}.

Kết luận chương

Chương này trình bày các định nghĩa cần thiết cho việc khai thác mẫu có tính chu kỳ xét đến trọng số từ dữ liệu hướng thời gian, khái quát hóa các giai đoạn của giải pháp đề xuất Những điểm mới trong nghiên cứu bao gồm giai đoạn Encode và Decode, đồng thời kế thừa các giải pháp khai thác mẫu có trọng số đã được công bố Nội dung chi tiết hóa các giai đoạn khai thác mẫu có tính chu kỳ xét đến trọng số, với thuật toán khai thác mẫu phổ biến dựa trên WIT-tree, kết hợp quá trình mã hóa dữ liệu đầu vào và giải mã dữ liệu kết quả để phát hiện các mẫu có tính chu kỳ, đạt được mục tiêu của đề tài này.

THỰC NGHIỆM VÀ ĐÁNH GIÁ