BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
Lê Duy Thảo
NGHIÊN CỨU KHAI PHÁ TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG CÁCH THỜI GIAN
LUẬN VĂN THẠC SĨ: CÔNG NGHỆ THÔNG TIN
Hà Nội – 2020
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
Lê Duy Thảo
NGHIÊN CỨU KHAI PHÁ TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG CÁCH THỜI GIAN
Chuyên ngành: Hệ thống thông tin
Mã số: 8480104
LUẬN VĂN THẠC SĨ: CÔNG NGHỆ THÔNG TIN
CÁN BỘ HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Việt Anh
Hà Nội – 2020
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn “Nghiên cứu khai phá Top-K mẫu dãy thường
xuyên trọng số với khoảng cách thời gian” được hoàn thành trên cơ sở nghiên
cứu, tổng hợp do tôi tự thực hiện. Các số liệu và trích dẫn trong luận văn có
nguồn gốc rõ ràng và trung thực.
Luận văn này là mới và không sao chép từ bất kỳ một luận văn nào khác.
TÁC GIẢ LUẬN VĂN
Lê Duy Thảo
LỜI CẢM ƠN
Trước hết, tôi xin bày tỏ sự cảm ơn đối với Học viện Khoa học và Công
nghệ và các thầy, cô giáo đã tạo mọi điều kiện giúp đỡ tôi hoàn thành chương
trình học tập và nghiên cứu tại Học viện Khoa học và Công nghệ. Có được kết
quả này, tôi vô cùng biết ơn và bày tỏ lòng kính trọng sâu sắc đối với
TS.Nguyễn Việt Anh - người đã tận tình hướng dẫn giúp đỡ tôi hoàn thành luận
văn này.
Mặc dù đã có nhiều nỗ lực cố gắng nhưng do khả năng, điều kiện và kinh
nghiệm của bản thân còn hạn chế nên luận văn không tránh khỏi còn những
thiếu sót. Tôi rất mong nhận được những đóng góp quý báu của các thầy, cô
giáo, các nhà khoa học, lãnh đạo, đồng nghiệp và các bạn để giúp cho luận văn
của tôi được hoàn thiện hơn.
Tôi xin chân thành cảm ơn!
TÁC GIẢ LUẬN VĂN
Lê Duy Thảo
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
CSDL Cơ sở dữ liệu
SBD Cơ sở dữ liệu dãy S
KDD Knowledge Discovery Data Mining
SQL Structured Query Language
Candicate Ứng viên
Element Thành phần dãy
Itemset Tập mục thường xuyên
Frequent item Tập mục thường xuyên
Sequence patent Mẫu dãy
Maximal sequence Dãy phổ biến nhất
Support Độ hỗ trợ
Support threshold Ngưỡng hỗ trợ
Subsequence Dãy con
DANH MỤC CÁC BẢNG
Trang
Bảng 1.1. Ví dụ về CSDL giao tác với 4 mục và 5 giao tác ............................. 7
Bảng 1.2. Cơ sở dữ liệu dãy SDB ................................................................... 10
Bảng 1.3. Cơ sở dữ liệu dãy SDB ví dụ thuật toán AprioriAll ....................... 15
Bảng 1.4. Cơ sở dữ liệu dãy SDB ví dụ thuật toán PrefixSpan ...................... 22
Bảng 1.5. Cơ sở dữ liệu điều kiện với tiền tố .......................................... 23
Bảng 1.6. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 1.7. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 1.8. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 1.9. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 1.10. Kết quả mẫu dãy thường xuyên theo thuật toán PrefixSpan ........ 26
Bảng 2.1. Cơ sở dữ liệu dãy S ......................................................................... 32
Bảng 2.2. Giá trị trọng số của các mục dữ liệu ............................................... 32
Bảng 2.3. Cơ sở dữ liệu điều kiện với tiền tố .......................................... 34
Bảng 2.4. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 2.5. Cơ sở dữ liệu điều kiện với tiền tố
Bảng 2.7. Giá trị trọng số ................................................................................ 46
Bảng 2.6. Cơ sở dữ liệu dãy S ......................................................................... 46
Bảng 2.8. Cơ sở dữ liệu điều kiện với tiền tố <0,a> ....................................... 48
Bảng 2.9. Cơ sở dữ liệu điều kiện với tiền tố <0,ab> ..................................... 50
Bảng 2.10. Cơ sở dữ liệu dãy .......................................................................... 54
Bảng 2.11. Trọng số của các mục ................................................................... 54
Bảng 3.1. Mô tả các dữ liệu thử nghiệm ......................................................... 63
Bảng 3.2. Giá trị ràng buộc thời gian .............................................................. 64
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Trang
Hình 1.1. Số lượng tập mục phải xét với 5 mục ban đầu. ................................. 9
Hình 1.2. Hàm Apriori-Generate tập L3 thành tập ứng viên C4 ...................... 16
Hình 1.3. CSDL dãy SDB và các tập kết quả L1, L2, L3, L4 ........................ 17
Hình 3.1. Thời gian chạy với bộ dữ liệu BMSWebView1 ............................. 65
Hình 3.2. Thời gian chạy với bộ dữ liệu Bible ............................................... 65
Hình 3.3. Thời gian chạy với bộ dữ liệu Fifa .................................................. 66
Hình 3.4. Thời gian chạy với bộ dữ liệu Leviathan ........................................ 66
Hình 3.5. Thời gian chạy với bộ dữ liệu Sign ................................................. 67
Hình 3.6. Bộ nhớ sử dụng với bộ dữ liệu BMSWebView1 ............................ 68
Hình 3.7. Bộ nhớ sử dụng với bộ dữ liệu Bible .............................................. 68
Hình 3.8. Bộ nhớ sử dụng với bộ dữ liệu Fifa ................................................ 69
Hình 3.9. Bộ nhớ sử dụng với bộ dữ liệu Leviathan ....................................... 69
Hình 3.10. Bộ nhớ sử dụng với bộ dữ liệu Sign ............................................. 70
MỤC LỤC
Trang
Danh mục các chữ viết tắt ............................................................................................ Danh mục các bảng ......................................................................................................
Danh mục các hình vẽ ..................................................................................................
MỤC LỤC ................................................................................................................... 1
MỞ ĐẦU ..................................................................................................................... 3
CHƯƠNG 1. TỔNG QUAN ....................................................................................... 6 1.1. TỔNG QUAN KHAI PHÁ DỮ LIỆU ................................................................. 6
1.1.1. Tập mục ...................................................................................................... 6
1.1.2. Định nghĩa luật kết hợp .............................................................................. 6
1.1.3. Độ hỗ trợ tập mục ....................................................................................... 7
1.1.4. Độ tin cậy của luật kết hợp ......................................................................... 8 1.1.5. Tập mục thường xuyên ............................................................................... 8
1.1.6. Quá trình tìm kiếm luật kết hợp ................................................................. 8
1.2. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG ......... 10
1.2.1. Bài toán khai phá mẫu dãy thường xuyên và một số khái niệm cơ bản
trong khai phá mẫu dãy thường xuyên ............................................................... 10
1.2.2. Mẫu dãy thường xuyên có trọng số .......................................................... 12
1.2.3. Mẫu dãy thường xuyên với khoảng cách thời gian .................................. 12
1.3. THUẬT TOÁN APRIORIALL ......................................................................... 13
1.4. THUẬT TOÁN PREFIXSPAN ......................................................................... 18
CHƯƠNG 2. TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG
CÁCH THỜI GIAN .................................................................................................. 29
2.1. GIỚI THIỆU ...................................................................................................... 29
2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN CÓ TRỌNG SỐ .... 30 2.2.1. Các thuật ngữ mô tả bài toán khai phá mẫu dãy thường xuyên với trọng
số chuẩn hóa ....................................................................................................... 30 2.2.2. CSDL điều kiện trong khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa ............................................................................................................ 31 2.2.3. Ví dụ khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố ............................................................................... 32 2.2.4. Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử
dụng CSDL điều kiện theo tiền tố (WPrefixSpan) ............................................ 39
1
2.3. BÀI TOÁN MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG
CÁCH THỜI GIAN .................................................................................................. 41
2.3.1. Mô tả bài toán ........................................................................................... 41
2.3.2. CSDL điều kiện trong khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian ............................................................................ 43 2.3.3. Ví dụ khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng
cách thời gian sử dụng CSDL điều kiện theo tiền tố .......................................... 45 2.3.4. Thuật toán WIPrefixSpan ......................................................................... 51
2.4. BÀI TOÁN TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI
KHOẢNG CÁCH THỜI GIAN ................................................................................ 54
2.4.1. Phát biểu bài toán ..................................................................................... 54 2.4.2. Mô tả thuật toán ........................................................................................ 55
2.4.3. Ví dụ thuật toán: ....................................................................................... 58
CHƯƠNG 3. THỬ NGHIỆM VÀ NHẬN XÉT ....................................................... 63
3.1. THỬ NGHIỆM .................................................................................................. 63
3.2. NHẬN XÉT ....................................................................................................... 70
CHƯƠNG 4. KẾT LUẬN VÀ KIẾN NGHỊ ............................................................ 71
4.1. KẾT LUẬN ........................................................................................................ 71
4.2. KIẾN NGHỊ ....................................................................................................... 72
TÀI LIỆU THAM KHẢO ......................................................................................... 73
2
MỞ ĐẦU
Khai phá dữ liệu là một quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng từ các nguồn dữ liệu đã có. Khai phá dữ liệu trích rút ra các mẫu có ích trong cơ sở dữ liệu và tìm ra mối liên hệ giữa các mẫu đó. Mục tiêu tổng thể của quá trình khai phá dữ liệu là trích xuất tri thức từ bộ dữ liệu hiện có, sau đó biến đổi chúng thành cấu trúc con người có thể hiểu được để tiếp tục sử dụng.
Khai phá luật kết hợp là một nội dung quan trọng của khai phá dữ liệu, khai phá luật kết hợp gồm 2 bước: Bước đầu tiên là tìm các tập mục thường xuyên. Bước 2 là sinh ra các luật kết hợp từ các tập mục thường xuyên đó. Bài toán khai phá tập mục thường xuyên [1, 2, 3, 4, 5] ra đời như là một bài toán con của khai phá luật kết hợp.
Khai phá mẫu dãy [6, 7, 8, 9, 10, 11, 12, 13] là một mở rộng của khai phá tập mục thường xuyên 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 Agrawal đề xuất [6], khai phá mẫu dãy thường xuyên đã thu hút được sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu được công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có.
Thuật toán AprioriAll [6] do Agrawal và cộng sự đề xuất năm 1995 dựa trên nguyên tắc duyệt dữ liệu của thuật toán Apriori theo chiều rộng khai phá các mẫu dãy thường xuyên có độ dài lớn nhất.
Các giải thuật khai phá mẫu dãy thường xuyên sử dụng một ngưỡng hỗ trợ nhằm thu nhỏ không gian tìm kiếm. Tuy nhiên, sau khi có mẫu dãy thường xuyên, không có cách nào để điều chỉnh số các mẫu dãy thường xuyên thông qua phản hồi của người sử dụng, ngoại trừ sự thay đổi ngưỡng hỗ trợ tối thiểu. Một trong những hạn chế chính của phương pháp tiếp cận truyền thống các thuật toán khai phá mẫu dãy thường xuyên là các mẫu dãy đều có giá trị và lợi
3
ích như nhau, tuy nhiên trong thực tế, các mẫu dãy lại có các mức độ quan trọng khác nhau.
Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thường xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phương pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có nhiều hướng mở rộng bài toán được quan tâm nghiên cứu. Một hướng mở rộng bài toán này là quan tâm đến cấu trúc dữ liệu, mức độ quan trọng và khoảng cách thời gian khác nhau của các mục dữ liệu, các thuộc tính trong cơ sở dữ liệu.
Trên thế giới có nhiều tác giả đã nghiên cứu về trọng số, khoảng cách thời gian, đưa các giá trị trọng số và khoảng cách thời gian khác nhau đến các mẫu dãy, có thể kể đến là các công trình khai phá mẫu dãy có trọng số và khoảng cách thời gian như [14, 15, 16, 17, 18, 19, 20], [21, 22].
Trong luận văn này sẽ tìm hiểu về một số thuật toán khai phá mẫu dãy thường xuyên có trọng số, có khoảng cách thời gian, khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian.
Mục tiêu của luận văn bao gồm:
- Tìm hiểu các kiến thức cơ bản về các phương pháp khai phá mẫu dãy thường xuyên, sau đó là các biến thể ràng buộc chi tiết về trọng số, thời gian với top-k mẫu dãy.
- Cài đặt thử nghiệm toán khai phá Top-k mẫu dãy thường xuyên trọng
số với khoảng cách thời gian
Đối tượng nghiên cứu của luận văn là các dữ liệu có giá trị về trọng số,
và khoảng cách thời gian của các mục dữ liệu.
Phạm vi nghiên cứu của luận văn tập trung nghiên cứu bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa, khai phá Top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian.
Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận văn đưa vào dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố.
4
Về nghiên cứu thực nghiệm: luận văn thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu.
Bố cục luận văn gồm 4 chương:
Chương 1. Tìm hiểu tổng quan về lĩnh vực khai phá mẫu dãy thường xuyên
và một số mở rộng.
Chương 2. Tìm hiểu bài toán khai phá Top-k mẫu dãy thường xuyên trọng
số với khoảng cách thời gian
Chương 3. Thử nghiệm và nhận xét.
Chương 4. Kết luận và kiến nghị
5
CHƯƠNG 1. TỔNG QUAN
1.1. TỔNG QUAN KHAI PHÁ DỮ LIỆU
Trong khai phá dữ liệu, tìm hiểu luật kết hợp [1] là một phương pháp nghiên cứu rất hiệu quả và thường xuyên được sử dụng trong việc tìm ra những mối liên kết hữu ích giữa các biến số trong những CSDL lớn. Các luật liên kết chặt chẽ tìm được trong CSDL được ứng dụng trong rất nhiều lĩnh vực khác nhau. Ví dụ như:
- Thu thập các loại mặt hàng mà người dùng thường mua cùng với nhau.
- Thu thập các trang web mà người dùng thường truy cập cùng nhau.
- Thu thập thông tin mặt hàng sẽ được mua tiếp theo sau khi đã mua mặt
hàng nào đó.
1.1.1. Tập mục
CSDL giao tác D gồm một tập các giao tác D = { t1, t2, … , tN }.
Tập I = { i1, i2, … , iM } là tập tất cả các mục (item) xuất hiện trong D.
Mỗi tập con X của I được gọi là một tập mục (itemset). Một tập mục X chứa k mục riêng biệt được gọi là tập mục cỡ k hoặc k-tập mục (k-itemset).
1.1.2. Định nghĩa luật kết hợp
Tìm kiếm luật kết hợp là tìm ra sự kết hợp hay mối tương quan giữa các
tập mục với nhau.
Những luật kết hợp này có dạng X → Y với X, Y I và X ∩ Y = ∅.
Để minh họa cho khái niệm, chúng ta sẽ sử dụng một ví dụ nhỏ trong lĩnh vực mua hàng, tập tất cả các mục là I = { sữa, bánh mỳ, bơ, bia } và CSDL giao tác nhỏ chứa các mục (1 - thể hiện mục xuất hiện trong giao dịch và 0 - thể hiện sự vắng mặt trong giao dịch) được thể hiện trong bảng dưới đây:
6
Bảng 1.1. Ví dụ về CSDL giao tác với 4 mục và 5 giao tác
ID giao dịch
Sữa
Bánh mỳ
Bơ
Bia
1
1
1
0
0
2
0
0
1
0
3
0
0
0
1
4
1
1
1
0
5
0
1
0
0
Một ví dụ về luật kết hợp cho CSDL trên sẽ có dạng {bánh mỳ, bơ} →{sữa}, có nghĩa là nếu người dùng mua bánh mỳ và bơ thì họ cũng sẽ mua sữa.
Tất nhiên, ví dụ trên là cực kỳ nhỏ. Trong ứng dụng thực tiễn, một luật kết hợp cần có sự nghiên cứu của hàng trăm giao dịch trước khi được coi là có ý nghĩa về mặt thống kê, và tập dữ liệu thường chứa tới hàng ngàn hoặc hàng triệu giao dịch.
Để có thể chọn ra được các luật kết hợp có ý nghĩa từ rất nhiều luật kết hợp có thể có với một CSDL giao tác, người ta thường sử dụng 2 ràng buộc rất phổ biến đó là độ hỗ trợ nhỏ nhất (minimum thresholds support - min_supp) và độ tin cậy nhỏ nhất (minimum thresholds confidence - min_conf).
1.1.3. Độ hỗ trợ tập mục
Tập mục X I, số các giao tác chứa tập mục X trong CSDL D gọi là số
đếm hỗ trợ (support count - SC) của X, ký hiệu là SC (X).
Độ hỗ trợ của một tập mục X - ký hiệu supp (X) – được định nghĩa là tỷ
lệ giao dịch trong tập dữ liệu có chứa tập mục X. Công thức tính độ hỗ trợ :
Supp (X) = P (X) = (1.1)
SC(X)
M
Trong CSDL ví dụ ở Bảng 1.1, tập mục {sữa, bánh mỳ, bơ} có độ hỗ trợ
7
là 1/5 = 0.2, nghĩa là tập mục X xuất hiện 20% trong toàn bộ tất cả các giao dịch.
1.1.4. Độ tin cậy của luật kết hợp
Độ tin cậy của luật kết hợp X→Y - ký hiệu conf (X→Y) - được định nghĩa là xác suất tất cả các giao dịch chứa tập mục Y trong khi đã có tập mục X. Công thức tính độ tin cậy :
SC(X∪Y)
Conf (X→Y) = P (Y|X) =
supp(X∪Y)
(1.2) =
SC(X)
supp(X)
Ở đây, supp (X ∪ Y) mang nghĩa độ hỗ trợ với giao dịch xuất hiện cả 2
tập mục X và Y chứ không phải độ hỗ trợ với giao dịch xuất hiện X hoặc Y.
Trong CSDL ví dụ ở Bảng 1.1, luật kết hợp {sữa, bánh mỳ}→{bơ} có độ tin cậy là 1/2 = 0.5 (hoặc 0.2/0.4 = 0.5), có nghĩa là 50% số lần người dùng mua sữa và bánh mỳ, họ sẽ mua luôn cả bơ.
1.1.5. Tập mục thường xuyên
Các tập mục có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu gọi là tập mục thường xuyên (frequent itemset). Tập các k-tập mục (k-itemset) là các tập mục thường xuyên ký hiệu là Lk.
Trong CSDL ví dụ ở Bảng 1.1, nếu cho ngưỡng hộ trợ nhỏ nhất là 30%, khi đó tập mục {sữa, bánh mỳ, bơ} có độ hỗ trợ 20% < 30% sẽ không là 1 tập mục thường xuyên, nhưng với tập mục {sữa, bánh mỳ} có độ hỗ trợ là 2/5 = 40% > 30% là một tập mục thường xuyên trong CSDL đã cho.
1.1.6. Quá trình tìm kiếm luật kết hợp
Một luật kết hợp có ý nghĩa phải được thỏa mãn cả 2 ngưỡng hỗ trợ và tin cậy nhỏ nhất do người dùng đặt ra. Việc tìm kiếm luật kết hợp được chia ra làm 2 bước riêng rẽ:
- Bước thứ nhất, ngưỡng độ hỗ trợ nhỏ nhất được sử dụng để tìm ra mọi
tập mục thường xuyên có trong CSDL.
- Bước hai, tất cả các tập mục thường xuyên kết hợp với ngưỡng tin cậy
nhỏ nhất để hình thành nên luật.
8
Ta có thể thấy rằng bước 2 thực hiện khá đơn giản, và bước một cần chú ý nhiều hơn. Tìm kiếm tất cả các tập mục thường xuyên là rất khó khăn vì nó liên quan tới việc tìm kiếm tất cả các mục kết hợp.
Đối với một CSDL giao tác có N mục thì có thể xuất hiện tới 2N-1 tập mục cần xét, trong một CSDL thực tế lại có thể có tới hàng trăm, hàng nghìn mục khác nhau. Do đó, có thể coi bước tìm tất cả các tập mục thường xuyên là bước quan trọng nhất của bài toán tìm kiếm luật kết hợp.
Hình 1.1. Số lượng tập mục phải xét với 5 mục ban đầu.
9
1.2. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG
1.2.1. Bài toán khai phá mẫu dãy thường xuyên và một số khái niệm
cơ bản trong khai phá mẫu dãy thường xuyên
1.2.1.1. Cơ sở dữ liệu dãy
Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu.
Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ
liệu dạng {s1, s2, …, sm} với sj I là một tập mục được gọi là thành phần của dãy. Khi đó, S = {s1, s2, …, sm} và sj có dạng (i1i2… ik) và it là một mục dữ liệu. Một dãy S bị loại nếu chỉ có duy nhất một mục dữ liệu. Một mục dữ liệu chỉ xuất hiện 1 lần trong 1 thành phần của một dãy sj, nhưng có thể xuất hiện nhiều lần trong các thành phần khác nhau của một dãy S.
Kích thước |S| của một dãy là số lượng của các thành phần 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. Một cơ sở dữ liệu dãy SDB={S1,S2,…,Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh của một dãy và Sk là một dãy dữ liệu.
Ví dụ về một cơ sở dữ liệu dãy:
Bảng 1.2. Cơ sở dữ liệu dãy SDB
SID Dãy dữ liệu
1
2 <(ad)c(bc)(ae)>
3 <(ef)(ab)(df)cb>
4
1.2.1.2. Dãy con
Cho 2 dãy dữ liệu α=< a1 a2 … an > và β=< 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
10
β được gọi là Dãy chứa α
Ví dụ. α=< (ab), d> và β=< (abc), (de)>
1.2.1.3. Độ hỗ trợ của một dãy
Cho một CSDL dãy SDB có M bản ghi. Số lượng các bản ghi trong SDB có chứa dãy Sa được gọi là số hỗ trợ (support count- SC) của dãy Sa . Ký hiệu là SC(Sa). Tỉ lệ các bản ghi trong SDB chứa Sa được gọi là độ hỗ trợ của Sa , ký hiệu là support (Sa)
Ta có:
support(Sa) =
SC(Sa) M
1.2.1.4. Mẫu dãy thường xuyên
Cho một CSDL dãy SDB có M bản ghi và một ngưỡng độ hỗ trợ tối thiểu
minsup. Sa được gọi là mẫu dãy thường xuyên nếu :
support(Sa) ≥ minsup
1.2.1.5. Luật dãy trong khai phá dữ liệu
Trong khai phá dữ liệu, tìm hiểu luật dãy là một phương pháp nghiên cứu rất hiệu quả và thường xuyên được sử dụng trong việc tìm ra những mối liên kết thú vị giữa các biến số trong những CSDL lớn. Các luật liên kết chặt chẽ (strong rule) tìm được trong CSDL được ứng dụng trong rất nhiều lĩnh vực khác nhau. Ví dụ như :
- Thu thập các loại mặt hàng mà người dùng thường mua cùng với nhau.
- Thu thập các trang web mà người dùng thường truy cập cùng nhau.
- Thu thập thông tin mặt hàng sẽ được mua tiếp theo sau khi đã mua mặt
hàng nào đó.
Luật dãy X=>Y là một quan hệ giữa 2 tập mục X và Y với X,Y I sao
cho X∩Y = Ø và X,Y ≠ Ø. Ý nghĩa của luật X=>Y là nếu một tập mục X xuất hiện trong một dãy Sx nào đó thì các mục trong Y cũng xuất hiện sau đó trong dãy này (Sx).
11
Quá trình khai phá luật dãy cũng được chia ra làm 2 bước:
- Bước thứ nhất, tìm tất cả các mẫu dãy thường xuyên thỏa mãn ngưỡng
hỗ trợ tối thiểu.
- Bước hai, sinh luật dựa trên các mẫu dãy thường xuyên tìm được thỏa
mãn ngưỡng tin cậy tối thiểu.
1.2.1.6. Bài toán khai phá mẫu dãy thường xuyên
Cho CSDL dãy SDB. Cho trước một ngưỡng hỗ trợ tối thiểu minsup. Tìm
tất cả các mẫu dãy thường xuyên trong SDB, tức là tìm tập L:
𝐿 = {𝑆𝑎 ⊆ 𝑆 |𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑆𝑎) ≥ 𝑚𝑖𝑛𝑠𝑢𝑝}
Với các khái niệm trên, bài toán khai phá mẫu dãy thường xuyên có thể chia thành 2 bài toán nhỏ: Tìm mẫu dãy ứng viên và tìm mẫy dãy thường xuyên. Mẫu dãy ứng viên được sinh ra trong quá trình duyệt cơ sở dữ liệu, mẫu dãy thường xuyên được tìm ra sau khi tính độ hỗ trợ của mẫu dãy ứng viên. Các mẫu dãy ứng viên có độ hỗ trợ lớn hơn ngưỡng hỗ trợ tối thiểu cho trước sẽ trở thành các mẫu dãy thường xuyên.
1.2.2. Mẫu dãy thường xuyên có trọng số
Các thuật toán khai phá mẫu dãy thường xuyên không quan tâm tới mức độ quan trọng của từng mẫu (trọng số của mẫu). Tuy nhiên trên thực tế, mỗi mẫu dữ liệu đều có độ quan trọng khác nhau.
Trọng tâm chính đối với khai phá mẫu dãy thường xuyên với trọng số là xây dựng giải thuật nhằm đảm bảo tính chất phản đơn điệu (downward closure property). Phương pháp tiếp cận là sử dụng tính chất ràng buộc giữa độ hỗ trợ và trọng số của dãy để sinh các tập ứng viên trong khi vẫn đảm bảo tính chất phản đơn điệu cho phép cân bằng độ hỗ trợ và trọng số của một dãy.
1.2.3. Mẫu dãy thường xuyên với khoảng cách thời gian
Các thuật toán khai phá mẫu dãy thường xuyên chỉ tính toán đến số lần xuất hiện (độ hỗ trợ). Các thuật toán này cơ bản không quan tâm đến khoảng cách thời gian giữa các dãy.
12
Trên thực tế, giữa các mẫu dãy có khoảng cách thời gian khác nhau. Do vậy mức độ quan trọng của các mẫu dãy cũng khác nhau. Có thể nói rằng các mẫu dãy có khoảng cách thời gian lớn thì ít quan trọng hơn các mẫu dãy có khoảng cách thời gian nhỏ.
Mục tiêu của khai phá mẫu dãy thường xuyên với khoảng cách thời gian là tìm ra được các mẫu dãy có ý nghĩa trong CSDL dãy với khoảng cách thời gian.
Khai phá mẫu dãy thường xuyên trong CSDL dãy là tìm ra các mẫu dãy xuất hiện nhiều lần trong 1 CSDL có thứ tự. Thuật toán cơ bản khai phá mẫu dãy thường xuyên là AprioriAll [6].
Thuật toán AprioriAll [6] tiêu biểu cho phương pháp dựa trên giải thuật Apriori theo nguyên tắc: tập ứng viên gồm các mẫu dãy độ dài k được phát sinh bằng cách kết hợp các mẫu dãy độ dài (k-1), sau đó dựa vào nguyên tắc Apriori và minsup để loại bỏ các mẫu dãy không thường xuyên.
1.3. THUẬT TOÁN APRIORIALL
Thuật toán AprioriAll [6] do Agrawal và cộng sự đề xuất năm 1995 dựa trên nguyên tắc duyệt dữ liệu của thuật toán Apriori [1] theo chiều rộng khai phá các mẫu dãy thường xuyên có độ dài lớn nhất.
Thuật toán AprioriAll:
Đầu vào : CSDL dãy SDB,
Ngưỡng hỗ trợ minsup,
Đầu ra : Tập các mẫy dãy thường xuyên lớn nhất L.
13
Ký hiệu :
SDB Cơ sở dữ liệu
Tập các k-mẫu dãy thường xuyên Lk
L Tập tất cả các mẫu dãy thường xuyên
Ck Tập các k-mẫu dãy ứng viên có thể là tập con của j-mẫu dãy thường xuyên, j > k
SC(c) Số đếm hỗ trợ của dãy trong SDB
minsup Ngưỡng hỗ trợ tối thiểu
Thủ tục AprioriAll:
L1 = {large 1-sequences}
for (k = 2; Lk-1 ≠ {}; k++) do
begin
Ck = New candidates generated from Lk-1 (Hàm Apriori_ Generate )
foreach customer-sequence c in the database do
Increment the count of all candidates in Ck that are contained in c.
Lk = Candidates in Ck with minimum support.
end
L = Maximal Sequences in ⋃ 𝐿𝑘𝑘
Trong mỗi lần duyệt, ta sử dụng các dãy thường xuyên từ lần duyệt trước đó để tạo ra các dãy ứng viên, sau đó tính độ hỗ trợ của chúng bằng cách duyệt toàn bộ CSDL. Tại lần duyệt cuối cùng tại mỗi bước, độ hỗ trợ của các ứng viên được sử dụng để xác định các dãy thường xuyên cho bước tiếp theo. Trong lần duyệt đầu tiên, đầu ra của giai đoạn l itemset được sử dụng để khởi tạo tập các dãy thường xuyên 1-sequences.
14
Ví dụ minh họa thuật toán AprioriAll:
Xét CSDL dãy SDB như trong Bảng 1.3 ở dưới. Giả sử ngưỡng hỗ trợ là
minsup = 0.4. Ta cần tìm tất cả các mẫu dãy thường xuyên trong SDB
Bảng 1.3. Cơ sở dữ liệu dãy SDB ví dụ thuật toán AprioriAll
SID Dãy dữ liệu
1 <(ae) (b) (c) (d)>
2 <(a) (c) (d) (ce)>
3 <(a) (b) (c) (d)>
4 <(a) (c) (e)>
5 <(d) (e)>
Bước thứ 1: (k = 1, k là độ dài dãy). Duyệt CSDL SDB, ta có số đếm hỗ
trợ mỗi mục riêng lẻ lần lượt là :
SC(a) = 4, SC(b) = 2, SC(c) = 4, SC(d) = 4, SC(e) = 4
Khởi đầu L = ∅.
Độ hỗ trợ của mỗi dãy là
support(a) = 0.8, support(b) = 0.4, support(c) = 0.8,
support(d) = 0.8, support(e) = 0.8
Với minsup đã cho là 0.4, ta thu được L1 = {(a), (b), (c), (d), (e)}.
Sau bước 1, ta có L = L ∪ L1 = ∅ ∪ {(a), (b), (c), (d), (e)} = {(a), (b), (c),
(d), (e)}
Bước thứ 2 : (k = 2, k là độ dài dãy) :
Thực hiện hàm Apriori-Generate: Kết nối mỗi tập mục thường xuyên trong L1 với mỗi mục để lập thành một tập dãy ứng viên C2, và thực hiện tỉa những dãy không có trong L1 thu được:
15
C2 = {(a)(b), (a)(c), (a)(d), (a)(e), (b)(c), (b)(d), (b)(e), (c)(d), (c)(e),
(d)(e),(ab), (ac), (ad), (ae), (bc), (bd), (be), (cd), (ce), (de)}.
Duyệt CSDL SDB, ta tính số đếm hỗ trợ mỗi mục trong C2 lần lượt là
SC((a)(b)) = 2, SC((a)(c)) = 4, SC((a)(d)) = 3 , SC((a)(e)) = 2
SC((b)(c)) = 2, SC((b)(d)) = 2, SC((b)(e)) = 0 , SC((c)(d)) =3
SC((c)(e)) = 2 , SC((d)(e)) = 2, SC((ab)) = 0, SC((ac)) = 0
SC((ad)) = 0, SC((ae)) = 1 , SC((bc)) = 0, SC((bd)) = 0
SC((be)) = 0, SC((cd)) = 0, SC((ce)) = 1, SC((de)) = 0
Với minsup đã cho là 0.4, ta thu được
L2 = {(a)(b), (a)(c), (a)(d), (a)(e), (b)(c),(b)(d),(c)(d),(c)(e),(d)(e)}.
Sau bước 2, ta có L = L ∪ L2 = {(a), (b), (c), (d), (e), (a)(b), (a)(c), (a)(d),
(a)(e), (b)(c),(b)(d),(c)(d),(c)(e),(d)(e)}
Các bước lặp tiếp theo : (k ++, k là độ dài dãy) :
Tiếp tục thực hiện hiện hàm Apriori-Generate: Kết nối mỗi tập mục thường xuyên trong Lk-1 với mỗi dãy để lập thành một tập dãy ứng viên Ck , và thực hiện tỉa những dãy không có trong Lk-1 thu được kết quả như sau:
Hình 1.2. Hàm Apriori-Generate tập L3 thành tập ứng viên C4
16
Hình 1.3. CSDL dãy SDB và các tập kết quả L1, L2, L3, L4
Thực hiện hàm Maximal_Sequences có dữ liệu đầu vào là tập L, thực hiện tìm các mẫu dãy thường xuyên có độ dài lớn nhất, tức là tỉa tất cả mẫu dãy thường xuyên là dãy con của một mẫu dãy thường xuyên.
Kết quả cuối cùng tập L sau khi kết thúc thuật toán AprioriAll [6] là:
L = {(a)(b)(c)(d), (a)(c)(e), (d)(e)}
Nhận xét về thuật toán AprioriAll:
Thuật toán AprioriAll là giải thuật dựa trên nguyên tắc Apriori: Mọi tập con của tập phổ biến phải là tập phổ biến, mọi tập cha của tập không phổ biến đều không phổ biến. Tập ứng viên gồm các mẫu dãy độ dài k được phát sinh bằng cách kết hợp các mẫu dãy độ dài (k-1), sau đó dựa vào nguyên tắc Apriori và minsup để loại bỏ các mẫu dãy không phổ biến.
Thuật toán gồm 3 giai đoạn chính: Tìm itemset phổ biến, biến đổi CSDL và tìm mẫu dãy trên dữ liệu đã biến đổi. Ở giai đoạn 1, thuật toán tiến hành duyệt toàn bộ CSDL ban đầu để tìm các itemset phổ biến. Sau đó, ánh xạ tập itemset phổ biến tìm được sang tập số nguyên. Việc ánh xạ nhằm mục đích coi một itemset phổ biến là một thực thể riêng biệt và thời gian so sánh hai itemset phổ biến bất kỳ đều như nhau. Hơn nữa, giúp giảm thời gian kiểm tra một dãy
17
có là dãy con của dãy dữ liệu trong CSDL ban đầu không.
Giai đoạn 2, trong CSDL dãy ban đầu, mỗi dãy được thay thế bởi tập tất cả các itemset phổ biến có chứa trong dãy đó. Nếu itemset không chứa itemset con phổ biến nào thì loại bỏ itemset đó khỏi tập dãy dữ liệu. Nếu dãy dữ liệu không chứa itemset phổ biến nào thì loại bỏ dãy đó khỏi CSDL. Sau khi biến đổi, mỗi dãy sẽ được đại diện bởi một dãy các itemset phổ biến.
Giai đoạn 3, tìm mẫu dãy dựa trên kết quả từ giai đoạn tìm itemset phổ biến, ta có được tập các mẫu dãy có kích thước là 1. Giải thuật dựa trên nguyên tắc Apriori: Mọi tập con của tập phổ biến phải là tập phổ biến, mọi tập cha của tập không phổ biến đều không phổ biến. Tập ứng viên gồm các mẫu dãy độ dài k được phát sinh bằng cách kết hợp các mẫu dãy độ dài (k-1), sau đó dựa vào nguyên tắc Apriori và minsup để loại bỏ các mẫu dãy không phổ biến.
1.4. THUẬT TOÁN PREFIXSPAN
Năm 2001, nhóm tác giả J. Pei, J. Han, B.M. Asi, H. Pinto đề xuất thuật toán PrefixSpan [9], một thuật toán dựa trên phương pháp phát triển mẫu dãy. Thuật toán không phải quét CSDL nhiều lần nên thời gian khai phá giảm đi đáng kể so với thuật toán AprioriAll [6].
Thuật toán PrefixSpan [9] dựa trên cấu trúc dữ liệu “FP – tree”, và sử dụng nguyên lý đệ quy “chia để trị” để phát triển các mẫu dãy trên cây FP. Cây FP được xây dựng dựa trên thuộc tính tăng cường mẫu như sau: α là một itemset thường xuyên trong CSDL, B là tập cơ sở điều kiện của α, và β là một itemset
trong B. Khi đó α∪β là một itemset thường xuyên trong cơ sở dữ liệu nếu và chỉ nếu β là thường xuyên ở trong B.
Ví dụ “abcdef” là một mẫu dãy nếu và chỉ nếu “abcde” là mẫu dãy và “f”
là thường xuyên trong tập các giao dịch có chứa “abcde”.
Định nghĩa 1. Tiền tố : Các mục dữ liệu trong một thành phần của dãy
đã sắp xếp theo thứ tự chữ cái.
Cho một dãy = < e1e2 …en>, một dãy =
là tiền tố của nếu:
18
- e’i = ei với (i≤m-1)
- e’m ⊆ em
- Mọi tập mục trong (em – e’m) được sắp xếp thứ tự trong e’m
Ví dụ: Cho dãy S =
Định nghĩa 2. Hậu tố : Cho một dãy =
… em-1 e’m> (m≤n) được gọi là tiền tố của . Dãy α=< e’’mem+1 … en> được
gọi là hậu tố của với tiền tố , hay α= / với e’’m = (em –e’m). Hay = . α.
Nếu không phải là dãy con của thì hậu tố của với tiền tố là rỗng.
Ví dụ: Cho dãy S =
Dựa trên ý tưởng tiền tố và hậu tố trên, vấn đề khai phá mẫu dãy thường
xuyên được chia thành vấn đề xử lý sau:
Mệnh đề 1:
- Cho {
- Cho là một mẫu dãy thường xuyên có độ dài là l và {1,2, …,m} là
tập toàn bộ mẫu dãy thường xuyên có độ dài là (l+1) với tiền tố . Thì toàn bộ
tập các mẫu dãy thường xuyên với tiền tố , trừ chính giá trị có thể được chia
trong m tập con phân biệt. Tập mẫu thứ j (1≤j≤m) là tập các mẫu dãy thường
xuyên với tiền tố j. Chứng minh:
Trường hợp 1 là trường hợp đặc biệt khi =.
Với mẫu dãy thường xuyên α có tiền tố , độ dài là l, thì tiền tố có độ
dài là (l+1) của α cũng bao gồm tiền tố theo cách định nghĩa Tiền tố. Vì vậy,
có thể tìm thấy các giá trị thứ j (1≤j≤m) như giá trị j có độ dài là (l+1) là tiền tố của α. Khi đó α nằm trong tập thứ j. Mặt khác, khi tiền tố của một dãy α có
19
độ dài k duy nhất, thì α chỉ thuộc 1 tập xác định. Đó là các tập con phân biệt. Vì vậy đó là điều chứng minh của mệnh đề.
Dựa vào tính chất của Mệnh đề 1, vấn đề cần giải quyết khi khai phá mẫu dãy thường xuyên là có thể thực hiện bằng cách phân vùng đệ quy. Đó là mỗi tập con của mẫu dãy thường xuyên có thể được chia tách ra khi cần thiết. Điều này cho phép thực hiện phương pháp chia để trị. Để thực hiện khai phá các tập con của mẫu dãy thường xuyên, cần xây dựng các CSDL điều kiện theo tiền tố.
Định nghĩa 3. CSDL điều kiện: Cho một dãy thường xuyên = …en> của một CSDL dãy S . Một CSDL điều kiện theo được định nghĩa là S|α, là các hậu tố của các dãy trong S với tiền tố . Định nghĩa 4. Độ hỗ trợ trong CSDL điều kiện: Cho một dãy = …en> của một CSDL dãy S và là một dãy với tiền tố . Độ hỗ trợ của trong CSDL điều kiện với tiền tố , ký hiệu là S| α gọi là support() trên S|α là số lượng các dãy α trong S|α sao cho ⊆. α Mệnh đề 2 : Cho và là hai mẫu dãy trong CSDL dãy S, với là một tiền tố của - S| = (S|α)| - Với mỗi dãy α với tiền tố , support (α) trên S = support (α) trên S|α - Kích thước của CSDL điều kiện với tiền tố không vượt quá S Thuật toán PrefixSpan
Đầu vào :
- CSDL dãy : S,
- Ngưỡng hỗ trợ : min_sup,
Đầu ra: Tập các mẫu dãy thường xuyên L 20 Thủ tục PrefixSpan (α,l,S|α )
Tham số: - α là một dãy thường xuyên
- l là độ dài của dãy α
- S|α là CSDL điều kiện với tiền tố α. S là trường hợp α = Bắt đầu: (1). Duyệt S|α, đếm độ hỗ trợ của mỗi mục và tìm các mục thường xuyên sao cho: Với mỗi : (a) có thể được ghép làm thành phần cuối cùng của α để tạo thành một mẫu dãy thường xuyên hoặc (b) <> có thể được nối vào với α để tạo thành một mẫu dãy thường xuyên - Kiểm tra các tập mục ứng viên trong Ck để tìm mẫu dãy
thường xuyên có trọng số chuẩn hóa thỏa mãn tính chất
support()*NW() wmin_sup, nạp vào L (2). Lặp với mỗi mẫu dãy thường xuyên - Ghép với α để tạo thành một mẫu dãy α’ và đầu ra là α’ (3). Lặp với mỗi α’ - Xây dựng CSDL điều kiện với tiền tố α’ là S|α’ . - Thực hiện đệ quy thủ tục PrefixSpan(α’,l+1,S|α’) Kết thúc. 21 Ví dụ thuật toán PrefixSpan
Cho một CSDL dãy SDB như Bảng 1.4, giá trị minsup =2. Khi đó việc
khai phá các mẫu dãy thường xuyên trong CSDL dãy S theo phương pháp
PrefixSpan được thực hiện theo các bước như sau: Bảng 1.4. Cơ sở dữ liệu dãy SDB ví dụ thuật toán PrefixSpan SID Dãy dữ liệu 1 <(a)(abc) (ac) d (cf)> 2 <(ad) c (bc) (ae) b c> 3 < (ef)(ab) (df) c b> 4 <(e) g (af) c b c> Bước 1: Tìm các dãy thường xuyên có độ dài 1
Duyệt CSDL dãy SDB lần đầu tiên để tìm tất cả các mẫu dãy thường xuyên có độ dài 1, đếm độ hỗ trợ của mỗi mục. Khi đó ta có các giá trị độ hỗ trợ của mỗi mục tương ứng như sau:
: 4, : 4, L = , , Bước 2: Chia không gian tìm kiếm
Toàn bộ các mẫu dãy thường xuyên được khai phá trong các phân vùng gồm 6 vùng tương ứng với 6 tiền tố như sau: 22 pháp đệ quy. Các bước thực hiện như sau: A. Tìm các các mẫu dãy thường xuyên với tiền tố
Trong một dãy có chứa , chỉ có các dãy bắt đầu bằng sự xuất hiện đầu
tiên của nên được lựa chọn. Ví dụ, trong chuỗi , chỉ có
dãy <(abc) (ac) d (cf)> được lựa chọn, tương tự với dãy <(ad) c (bc) (ae) bc>,
chỉ có dãy (~ d) c (bc) (ae) bc> được lựa chọn. Khi đó, CSDL điều kiện với tiền tố bao gồm 4 dãy sau Bảng 1.5. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(abc) (ac) d (cf)> 2 <(~d) c (bc) (ae) b c> 3 < (~b) (df) c b> 4 <(~f) c b c> Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ
liệu của nó tương ứng là a: 2, b: 4, c: 4, d: 2, e:1, f: 2, (~b): 2, (~c): 0 , (~d): 1,
(~ e): 0 và (~ f): 1. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup=2. Khi đó, ta có các mục dữ liệu bị tỉa là e, (~c), (~d), (~e), (~f). Các mục dữ liệu được phát hiện là a,b,c,d,f,(~b) L = L { Theo tính chất đệ quy, các mẫu dãy thường xuyên với tiền tố sẽ tiếp tục được chia thành 6 vùng tương ứng với 6 tiền tố gồm: (1) Mẫu dãy với tiền tố 23 (5) Mẫu dãy với tiền tố tiền tố Bảng 1.6. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(~bc) (ac) d (cf)> 2 < ~e> Bằng cách quét CSDL điều kiện với tiền tố Khi đó, không có dãy thường xuyên với tiền tố thực hiện đối với tiền tố A.2. Đối với mẫu dãy với tiền tố tiền tố Bảng 1.7. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(~c) (ac) d (cf)> 2 < (~c) (ae)> 3 < c> Bằng cách quét CSDL điều kiện với tiền tố Các mục dữ liệu được phát hiện là: a, c, (~c) L = L { Theo tính chất đệ quy, mẫu dãy thường xuyên với tiền tố được chia thành 3 vùng tương ứng với tiền tố gồm: (1) Mẫu dãy với tiền tố 24 (2) Mẫu dãy với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố Bảng 1.8. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(~c) d (cf)> 2 < (~e) > Bằng cách quét CSDL điều kiện với tiền tố Khi đó, không có dãy thường xuyên với tiền tố Dừng thực hiện đối với tiền tố A.2.2. Đối với mẫu dãy với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố Bảng 1.9. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(ac)d(cf)> 2 < (ae) > Bằng cách quét CSDL điều kiện với tiền tố Các mục dữ liệu được phát hiện là: a 25 L = L { <(a(bc)a>}
Theo tính chất đệ quy, mẫu dãy thường xuyên với tiền tố tục được chia thành 1 vùng tương ứng với tiền tố gồm: (1) Mẫu dãy với tiền tố kiện với tiền tố Khi đó CSDL điều kiện với tiền tố B. Tìm tương tự đối với các mẫu dãy thường xuyên với tiền tố , Đối với mẫu dãy với tiền tố , Bước 4: Kết quả là các mẫu dãy thường xuyên trong CSDL dãy S
Các mẫu dãy thường xuyên được khai phá lần lượt trong quá trình đệ quy đối với từng tiền tố. Bảng 1.10. Kết quả mẫu dãy thường xuyên theo thuật toán PrefixSpan CSDL điều kiện Mẫu dãy thường xuyên Tiền tố
(Prefix) theo tiền tố <(a)> <(abc)(ac)(d)(cf)> <(a)> <(~d)(c)(bc)(ae)> <(a) (a)> <(~b)(df)(c)(b)> <(~f)(c)(b)(c)> <(a)(b)>, <(a)(bc)>,
<(a)(b)(a)>, <(a)(b)(c)>,
<(a)(bc)(a)> <(ab>,<(ab)(c)>, <(ab)(d)>,
<(ab)(f)>, <(ab)(d)(c)> <(a)(c)>, <(a)(c)(a)>, 26 CSDL điều kiện Mẫu dãy thường xuyên Tiền tố
(Prefix) theo tiền tố <(a)(c)(b)>, <(a)(c)(c)> <(a)(d)>, <(a)(d)(c)> <(a)(f)> <(b)> <(~c)(ac)(d)(cf)> <(b)> <(~c)(ae)> <(b)(a)> <((df)(c)(b)> <(b)(c)> <(c)> <(bc)>, <(bc)(a)> <(b)(d)>, <(b)(d)(c)> <(b)(f)> <(c)> <(ac)(d)(cf)> <(c)> <(bc)(ae)> <(c)(a)> <(b)> <(c)(b)> <(b)(c)> <(c)(c)> <(d)> <(cf)> <(d)> <(c)(bc)(ae)> <(d)(b)>, <(d)(c)> <(~f)(c)(b)> <(d)(c)(b)> <(e)> <(~f)(ab)(df)(c)(b)> <(e)> <(af)(c)(b)(c)> <(e)(a)>, <(e)(a)(b)>,
<(e)(a)(c)>, <(e)(a)(c)(b)> <(e)(b)>, <(e)(b)(c)> <(e)(c)>, <(e)(c)(b)> <(e)(f)>, <(e)(f)(b)>, <(e)(f)(c)>, <(e)(f)(c)(b)> 27 CSDL điều kiện Mẫu dãy thường xuyên Tiền tố
(Prefix) theo tiền tố <(f)> <(ab)(df)(c)(b)> <(f)> <(c)(b)(c)> <(f)(b)>, <(f)(b)(c)> <(f)(c)>, <(f)(c)(b)> Nhận xét thuật toán PrefĩxSpan:
Thuật toán PrefixSpan [9]: Giải thuật dựa trên phương pháp phát triển
mẫu dãy, phát triển những mẫu dãy dài từ những mẫu dãy có độ dài ngắn
hơn đã có, đồng thời kết hợp với phương pháp chia nhỏ không gian tìm kiếm
theo tiền tố. Thuật toán phát triển mẫu dãy không cần phát sinh thêm ứng viên giống
như giải thuật AprioriAll [6]. Mặt khác thực hiện phép chiếu CSDL theo tiền
tố nên không gian tìm kiếm giảm đáng kể. Nhờ vậy tiết kiệm bộ nhớ và việc
thực hiện đếm độ hỗ trợ được nhanh hơn. 28 CHƯƠNG 2. TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI
KHOẢNG CÁCH THỜI GIAN 2.1. GIỚI THIỆU Mục tiêu của khai phá mẫu thường xuyên [6, 7, 8] là tìm ra các mẫu dãy
xuất hiện nhiều lần trong 1 CSDL dãy. Tuy nhiên, các mẫu dãy thường xuyên
không thể hiện được mức độ quan trọng của từng mục dữ liệu. Do đó, bài toán
khai phá mẫu dãy thường xuyên có trọng số ra đời để giải quyết vấn đề về mức
độ quan trọng của các mục. Một số thuật toán có thể kể tới là [19, 23, 24, 25,
17, 26, 27]. Trong các thuật toán này, không chỉ tần xuất mà mức độ quan trọng
của các mục trong mẫu dãy cũng được tính tới. Để thể hiện mức độ quan trọng của các mục, mỗi mục được gán 1 giá trị
thực dương (thường là trong khoảng 0-1). Tập các giá trị này được lưu vào 1
bảng gọi là bảng trọng số. Do trong các mẫu dãy có trọng số, độ hỗ trợ không
còn tính phản đơn điệu nên trong các thuật toán khai phá mẫu dãy với trọng số,
để duy trì tính phản đơn điệu, giá trị support*maxW được sử dụng làm cận trên
của các mẫu dãy có trọng số. Một vấn đề khác của các mẫu dãy thường xuyên là không chứa thông tin
về thời gian của các giao dịch. Tuy nhiên, dữ liệu trong thực tế thường có loại
thông tin này. Ví dụ: dữ liệu mua sắm có thời gian của các giao dịch mua hàng,
dữ liệu duyệt web lưu thời gian của các lần truy cập… Khai phá mẫu dãy thường xuyên sử dụng một ngưỡng tối thiểu để tìm ra
các mẫu dãy có giá trị. Ngưỡng này được đặt bởi người sử dụng như một giá
trị đầu vào. Tuy nhiên, không dễ để chọn 1 ngưỡng phù hợp, nếu đặt ngưỡng
quá cao sẽ tìm được ít mẫu dãy có giá trị, nếu đặt ngưỡng quá thấp sẽ dẫn tới
quá nhiều mẫu dãy được tìm ra. Vì vậy, bài toán top-k ra đời để giải quyết vấn
đề này. Trong bài toán top-k [28, 29, 30, 31, 32, 33], người sử dụng không cần
phải đặt ngưỡng tối thiểu mà chỉ cần đưa vào giá trị k. Ngưỡng tối thiểu sẽ được
tăng dần cho tới khi tìm ra được k mẫu dãy có giá trị nhất. 29 2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN CÓ TRỌNG SỐ 2.2.1. Các thuật ngữ mô tả bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij I được gán một trọng số wj, j = 1,.....,n. Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu {s1, s2, …, sm} với sj I là một tập mục được gọi là thành phần của dãy.
Khi đó, S = {s1, s2, …, sm} và sj có dạng (i1i2… ik) và it là một mục dữ liệu.
Một dãy S bị loại nếu chỉ có duy nhất một mục dữ liệu. Một mục dữ liệu chỉ
xuất hiện 1 lần trong 1 thành phần của một dãy sj, nhưng có thể xuất hiện nhiều
lần trong các thành phần của một dãy S. Kích thước |S| của một dãy là số lượng của các thành phần 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. Một cơ sở dữ liệu dãy
S = {S1, S2, …, Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh của
một dãy và Sk là một dãy dữ liệu. Định nghĩa 5. Độ hỗ trợ của một dãy: Độ hỗ trợ của dãy Sa trong cơ sở dữ liệu dãy S là số lượng các bản ghi trong S có chứa dãy Sa Định nghĩa 6. Trọng số chuẩn hóa của dãy: Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij I được gán một trọng số wj, j = 1,.....,n. Khi đó trọng số chuẩn hóa của một dãy = công thức 𝑁𝑊() = 1
𝑛 ∑ 𝑤𝑗
𝑖𝑗 ∈ Định nghĩa 7. Độ hỗ trợ với trọng số chuẩn hóa của dãy: Ta gọi đại lượng NWsupport() của dãy là độ hỗ trợ với trọng số chuẩn hóa của dãy 𝑁𝑊𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = 𝑁𝑊(𝛼) ∗ 𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = ( ) ∗ 𝑆𝐶(𝛼) 1
𝑛 ∑ 𝑤𝑗
𝑖𝑗 ∈𝛼 30 Định nghĩa 8. Mẫu dãy thường xuyên với trọng số chuẩn hóa:
Cho một CSDL dãy S, một ngưỡng hỗ trợ tối thiểu wmin_sup. Một dãy
α được gọi là mẫu dãy thường xuyên với trọng số chuẩn hóa nếu thỏa
mãn tính chất. NWSupport(α) wmin_sup Khi đó, bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố được phát biểu như sau: • Cho CSDL dãy S, mỗi mục ij ⊆ I được gán một trọng số wj , ngưỡng hỗ
trợ tối thiểu wmin_sup. Tìm tất cả các mẫu dãy thường xuyên với trọng số
chuẩn hóa trong S, tức là tìm tập L : L = {Sa ⊆ S | NWsupport(Sa ) wmin_sup}
• Mẫu dãy thường xuyên với trọng số chuẩn hóa không thỏa mãn tính
chất phản đơn điệu, nghĩa là tập con của một mẫu dãy thường xuyên với
trọng số chuẩn hóa không nhất thiết phải là mẫu dãy thường xuyên với trọng
số chuẩn hóa. 2.2.2. CSDL điều kiện trong khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa
WPrefixSpan [34] trong đó cách tiếp cận chính là đẩy các ràng buộc trọng
số và độ hỗ trợ trong thuật toán khai phá mẫu dãy và đảm bảo tính chất
phản đơn điệu. Để tránh phải thực hiện kiểm tra tất cả khả năng kết hợp của một dãy các
ứng viên tiềm năng, ta có thể thay thế các thứ tự của các mục dữ liệu trong từng
thành phần trong dãy. Khi đó, các mục trong một thành phần của một dãy có
thể được liệt kê theo 1 trật tự mà không mất tính tổng quát, ta có thể giả định
rằng thứ tự này luôn luôn được liệt kê theo thứ tự bảng chữ cái. Ví dụ như dãy thay vì . Với quy ước như vậy, sự biểu hiện của một dãy là duy nhất. Nếu ta theo thứ tự của các tiền tố của một dãy và CSDL điều kiện của tiền
tố đó chỉ có các hậu tố của một dãy, thì ta có thể kiểm tra các dãy con theo thứ 31 tự sắp xếp trên và CSDL điều kiện theo tiền tố đó. Định nghĩa 9. Mẫu dãy ứng viên: Cho một ngưỡng hỗ trợ tối thiểu
wmin_sup. Một dãy α được gọi là dãy ứng viên mẫu dãy thường xuyên với
trọng số chuẩn hóa nếu thỏa mãn tính chất Support(α) * MaxW wmin_sup Với MaxW là giá trị lớn nhất của trọng số trong các mục trong S. Mẫu
dãy ứng viên được xây dựng nhằm mục đích tỉa bớt không gian tìm kiếm mà
vẫn đảm bảo tính phản đơn điệu trong khai phá mẫu dãy thường xuyên với
trọng số chuẩn hóa. 2.2.3. Ví dụ khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố Cho một CSDL dãy S như Bảng 2.1, giá trị các trọng số của các mục dữ
liệu như Bảng 2.2, giá trị wmin_sup = 2. Khi đó việc khai phá các mẫu dãy
thường xuyên với trọng số chuẩn hóa trong CSDL dãy S theo phương pháp
WPrefixSpan [34] được thực hiện theo các bước như sau: Bảng 2.1. Cơ sở dữ liệu dãy S Bảng 2.2. Giá trị trọng số
của các mục dữ liệu Dãy dữ liệu Tên mục Trọng số <(ad) c (bc) (ae) b c> b 0.75 <(ef) (ab) (df) c b> c 0.8 g 0.85 h 0.8 32 Bước 1: Tìm các ứng viên của mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 Duyệt CSDL dãy S lần đầu tiên để tìm tất cả các ứng viên của mẫu dãy
thường xuyên có trọng số chuẩn hóa có độ dài 1, đếm độ hỗ trợ của mỗi mục. Một mục có độ dài 1 có thể không phải là một mẫu dãy thường xuyên có
trọng số chuẩn hóa nhưng có thể kết hợp với các mục khác có độ hỗ trợ lớn hơn
hoặc trọng số lớn hơn để trở thành mẫu dãy thường xuyên có trọng số trong các
mẫu có độ dài lớn hơn. Khi đó ta có các giá trị độ hỗ trợ của mỗi mục như sau: : 6, : 6, Giá trị trọng số là (a: 0,9 ; b: 0,75 ; c: 0,8 ; d: 0,85 ; e: 0,75 ; f: 0,7 ; g: 0,85 ; h: 0,8) Giá trị MaxW = 0.9 Kiểm tra theo Định nghĩa 9, loại mục g và h do giá trị: support(g)*MaxW = 2*0.9=1.8 < wmin_sup và support(h)*MaxW = 1*0.9=0.9 < wmin_sup Khi đó, ta có các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 là C1 = , , Kiểm tra theo Định nghĩa 8 với các ứng viên, Khi đó, ta có các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 là: NWsupport(a) = 6*0,9 = 5,4 NWsupport(b) = 6*0,75 = 4,5 NWsupport(c) = 6*0,8 = 4,8 NWsupport(d) = 5*0,85 = 4,25 NWsupport(e) = 4*0,75 = 3 NWsupport(f) = 3*0,7 = 2,1 Ta có: L = , , Bước 2: Chia không gian tìm kiếm Toàn bộ các ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa
được khai phá trong các phân vùng gồm 6 vùng tương ứng với 6 tiền tố gồm: 33 (1) Mẫu dãy với tiền tố
(2) Mẫu dãy với tiền tố
(3) Mẫu dãy với tiền tố Bước 3: Khai phá các tập con ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa Các tập con ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa
được khai phá bằng cách xây dựng các CSDL điều kiện tương ứng với các tiền
tố, và khai phá chúng bằng phương pháp đệ quy. Các bước thực hiện như sau:
A. Tìm các ứng viên và các mẫu dãy thường xuyên với trọng số chuẩn hóa Trong một dãy có chứa , chỉ có các dãy bắt đầu bằng sự xuất hiện đầu
tiên của nên được lựa chọn. Ví dụ, trong chuỗi , chỉ có
dãy <(abc) (ac) d (cf)> được lựa chọn, tương tự với dãy <(ad) c (bc) (ae) bc>,
chỉ có dãy (~ d) c (bc) (ae) bc> được lựa chọn. Khi đó, CSDL điều kiện với tiền tố bao gồm 6 dãy sau: Bảng 2.3. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(abc) (ac) d (cf)> 2 <(~d) c (bc) (ae) b c> 3 < (~b) (df) c b> 4 <(~f) c b c> 5 <(ab) (cd) e> 6 <(abd) b c > Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ
liệu của nó là a: 4, b: 6, c: 6, d: 4, e: 2, f: 2, (~b): 4, (~d): 1 , (~ e): 1 và (~ f): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 2 với tiền tố 34 support(a)*MaxW = 4*0.9 = 3.6 support(b)*MaxW = 6*0.9 = 5.4 support(c)*MaxW = 6*0.9 = 5.4 support(d)*MaxW = 4*0.9 = 3.6 support(e)*MaxW = 2*0.9 = 1.8 support(f)*MaxW = 2*0.9 = 1.8 support((~b))*MaxW = 4*0.9 = 3.6 support((~d))*MaxW =1*0.9= 0.9 support((~e))*MaxW = 1*0.9 = 0.9 support((~f))*MaxW =1*0.9= 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 2 với tiền tố là Kiểm tra theo Định nghĩa 8 với các ứng viên trong C2 , Khi đó, ta có
các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 2 với tiền tố
là: NWsupport(aa) = 4*(0,9+0,9)/2 = 5,4 NWsupport(ab) = 6*(0,9+0,75)/2 = 4,95 NWsupport(ac) = 6*(0,9+0,8)/2 = 5,1 NWsupport(ad) = 4*(0,9+0,85)/2 = 3,5 NWsupport((ab)) = 4*(0,9+0,9+0,75)/3 = 3,4 L = L { Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng
số chuẩn hóa với tiền tố sẽ tiếp tục được chia thành 5 vùng tương ứng với
5 tiền tố gồm: (1) Mẫu dãy với tiền tố A.1. Đối với mẫu dãy với tiền tố 35 tiền tố Bảng 2.4. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(~bc) (ac) d c> 2 < b c> 3 <(~b) (cd) > 4 <(~bd) b c > Bằng cách quét CSDL điều kiện với tiền tố dữ liệu của nó là a: 1, b: 2, c: 4, d: 2, (~b): 3, (~c): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 3 với tiền tố support(a)*MaxW = 1*0.9=0.9 support(b)*MaxW = 2*0.9=1.8 support(c)*MaxW = 4*0.9 = 3.6 support(d)*MaxW = 2*0.9 = 1.8 support((~b))*MaxW = 3*0.9 = 2.7 support((~c))*MaxW = 1*0.9 = 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là , , <(d)>, <(~c)> Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 3 với tiền tố C3 Kiểm tra theo Định nghĩa 8 với các ứng viên trong C3 NWsupport(aac) = 4*(0,9+0,9+0,8)/3 = 3,46 NWsupport(a(ab)) = 3*(0,9+0,9+0,75)/3 = 2,55 L = L { Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng
số chuẩn hóa với tiền tố 36 (1) Mẫu dãy với tiền tố A.1.1. Đối với mẫu dãy với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố A.1.2. Đối với mẫu dãy với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố Bảng 2.5. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 <(~c) (ac) c> 2 3 <(~d) b c > Bằng cách quét CSDL điều kiện với tiền tố dữ liệu của nó là a: 1, b: 1, c: 3, (~d): 1, (~c): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 4 với tiền tố support(a)*MaxW = 1*0.9 = 0.9 support(b)*MaxW = 1*0.9 = 0.9 support(c)*MaxW = 3*0.9 = 2.7 support((~d))*MaxW = 1*0.9 = 0.9 support((~c))*MaxW = 1*0.9 = 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là , , <(~d)>, <(~c)> Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 4 với tiền tố C4 Kiểm tra theo Định nghĩa 8 với các ứng viên trong C4 37 NWsupport(a(ab)c) = 3*(0,9+0,9+0,75+0,8)/4 = 2,51 L = L { Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng
số chuẩn hóa với tiền tố (1) Mẫu dãy với tiền tố A.1.2.1. Đối với mẫu dãy với tiền tố với tiền tố Khi đó CSDL điều kiện với tiền tố A.2. Đối với mẫu dãy với tiền tố B. Tìm tương tự với các ứng viên và các mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố , Đối với mẫu dãy với tiền tố , Bước 4: Kết quả là các mẫu dãy thường xuyên với trọng số chuẩn hóa trong CSDL dãy S Các mẫu dãy thường xuyên có trọng số chuẩn hóa được khai phá lần lượt
trong quá trình đệ quy đối với từng tiền tố. Trong phương pháp khai phá mẫu
dãy thường xuyên với trọng số chuẩn hóa này, kết quả sẽ ít hơn các mẫu dãy
thường xuyên khi không gắn thêm yếu tố trọng số của các mục dữ liệu. 38 2.2.4. Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố (WPrefixSpan) - Đầu vào : (1) CSDL dãy : S, (2) Ngưỡng hỗ trợ : wmin_sup, (3) Trọng số của các mục: wi, - Đầu ra: Tập các mẫu dãy thường xuyên với trọng số chuẩn hóa L Thuật toán WPrefixSpan Bắt đầu 1. Duyệt CSDL S lần đầu, tính độ hỗ trợ và tìm các mục
ứng viên có kích thước 1 thỏa mãn tính chất: Một tập mục
P là tập mục ứng viên nếu thỏa mãn điều kiện 1.1, P sẽ
được nạp vào Ck Điều kiện 1.1: support (P)* MaxW wmin_sup 2. Kiểm tra các tập mục ứng ứng viên trong Ck để tìm mẫu
dãy thường xuyên có trọng số chuẩn hóa thỏa mãn tính
chất support(P)*NW(P) wmin_sup, nạp vào L 3. Lặp với mỗi mục trọng số chuẩn hóa P, trong CSDL dãy S Thực hiện hàm đệ quy WPrefixSpan( ,l,S|P) Kết thúc lặp Kết thúc 39 Thủ tục WPrefixSpan (α,l,S|α ) Tham số: (1) α là một dãy ứng viên với trọng số chuẩn hóa thỏa điều kiện 1.1 (2) l là độ dài của α (3) S|α là CSDL điều kiện với tiền tố α. S là trường hợp α = Bắt đầu: 1. Duyệt S|α, đếm độ hỗ trợ của mỗi mục và tìm các mục ứng viên
trọng số chuẩn hóa trong các dãy. Một mục ứng viên trọng số
chuẩn hóa thỏa mãn tính chất 1.1, nạp vào Ck Điều kiện 1.1: support ()* MaxW wmin_sup - Với mỗi trong Ck : (a) có thể được ghép làm thành phần cuối cùng của α
để tạo thành ứng viên cho một mẫu dãy thường xuyên
với trọng số chuẩn hóa hoặc (b) <> có thể được nối vào với α để tạo thành ứng viên
cho một mẫu dãy thường xuyên với trọng số chuẩn hóa - Kiểm tra các tập mục ứng viên trong Ck để tìm mẫu dãy
thường xuyên có trọng số chuẩn hóa thỏa mãn tính chất
support()*NW() wmin_sup, nạp vào L 2. Lặp với mỗi ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa - Ghép với α để tạo thành ứng viên một mẫu dãy thường xuyên α’ và đầu ra là α’ 3. Lặp với mỗi α’ - Xây dựng CSDL điều kiện với tiền tố α’ là S|α’ . - Thực hiện đệ quy thủ tục WPrefixSpan(α’,l+1,S|α’) Kết thúc. 40 2.3. BÀI TOÁN MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG
CÁCH THỜI GIAN Phần này trình bày thuật toán WIPrefixSpan [35] khai phá mẫu dãy thường
xuyên trọng số với khoảng cách thời gian. Thuật toán WIPrefixSpan [35] không
chỉ quan tâm tới trọng số của các mục trong CSDL mà còn cả khoảng cách thời
gian giữa các tập mục. 2.3.1. Mô tả bài toán Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij I được gán một trọng số wj, j = 1,.....,n. Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu dạng { (t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)} với sj I trong đó (1 ≤ j ≤ m)
là một tập mục được gọi là thành phần của dãy và sj có dạng (i1i2… ik) và it là một mục dữ liệu thuộc I , và t, là khoảng cách thời gian giữa dãy s và s. Một dãy Sm bị loại nếu chỉ có duy nhất một mục dữ liệu it I . Một mục dữ liệu chỉ
xuất hiện 1 lần trong thành phần của một dãy sj, nhưng có thể xuất hiện nhiều
lần trong các thành phần của một dãy Sm. Kích thước |Sm| của một dãy là số lượng của các thành phần trong dãy Sm.
Độ dài l(Sm) của dãy là tổng số mục dữ liệu trong dãy Sm. Một cơ sở dữ liệu
dãy S = {S1, S2, …, Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh
của một dãy và Sk là một dãy dữ liệu có dạng {(t1,1,s1), (t1,2,s2), (t1,3,s3),...,
(t1,m,sm)}. Định nghĩa 1. (Dãy dữ liệu có khoảng cách thời gian) : Một dãy dữ liệu có
khoảng cách thời gian có dạng: Sm = <(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)> Với t,, là khoảng cách thời gian giữa dãy s và s có dạng: t, = s.time - s.time Định nghĩa 2. (Độ hỗ trợ của một dãy) : Độ hỗ trợ của một dãy Sa trong một
cơ sở dữ liệu dãy S là số lượng xuất hiện các bản ghi trong S có chứa dãy Sa . 41 Định nghĩa 3. (Trọng số chuẩn hóa của dãy): Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij I được gán một trọng số wj, j = 1,.....,n. Khi đó trọng số chuẩn hóa của một dãy = <(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)> có độ dài k và sj có dạng (i1i2… ik) được tính bằng công thức 𝑁𝑊() = 1
𝑘 ∑ 𝑤𝑗
𝑖𝑗 ∈ Định nghĩa 4. (Độ hỗ trợ với trọng số chuẩn hóa của dãy): Ta gọi đại lượng NWsupport() của dãy là độ hỗ trợ với trọng số chuẩn hóa của dãy 𝑁𝑊𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = 𝑁𝑊(𝛼) ∗ 𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = ( ) ∗ 𝑆𝐶(𝛼) 1
𝑘 ∑ 𝑤𝑗
𝑖𝑗 ∈𝛼 Định nghĩa 5. (Ràng buộc khoảng cách thời gian): Cho một dãy <(t1,1,s1),
(t1,2,s2), (t1,3,s3),..., (t1,m,sm)>, các ràng buộc khoảng cách thời gian giữa các dãy
được định nghĩa: • C1 = min_time_interval là giá trị nhỏ nhất giữa hai dãy liền kề, tức là ti,i+1 min_time_interval • C2 = max_time_interval là giá trị lớn nhất giữa hai dãy liền kề, tức là ti,i+1 ≤ min_time_interval • C3 = min_whole_interval là giá trị nhỏ nhất giữa dãy đầu và dãy cuối, tức là ti,m min_whole_interval • C4 = max_whole_interval là giá trị lớn nhất giữa dãy đầu và dãy cuối, tức là ti,m ≤ max_whole_interval Định nghĩa 6. (Mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách
thời gian): Cho một CSDL dãy S có khoảng cách thời gian giữa các dãy, mỗi
mục ij ⊆ I được gán một trọng số wj, một ngưỡng hỗ trợ tối thiểu wmin_sup,
các ràng buộc khoảng cách thời gian C1, C2, C3, C4. Một dãy α được gọi là mẫu
dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian nếu thỏa mãn
tính chất: 42 NWSupport(α) wmin_sup && t, thỏa mãn tính chất các ràng buộc C1, C2, C3, C4 Khi đó bài toán khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian được phát biểu như sau: • Cho một CSDL dãy S có khoảng cách thời gian giữa các dãy, mỗi mục
ij ⊆ I được gán một trọng số wj, một ngưỡng hỗ trợ tối thiểu wmin_sup,
các ràng buộc khoảng cách thời gian C1, C2, C3, C4. Tìm tất cả các mẫu
dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian trong S,
tức là tìm tập L: L = {Sa ⊆ S | NWsupport(Sa ) wmin_sup&& t, thỏa mãn tính chất các ràng buộc C1, C2, C3, C4} • Mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian
không thỏa mãn tính chất phản đơn điệu, nghĩa là tập con của một mẫu
dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian không
nhất thiết phải là mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng
cách thời gian. 2.3.2. CSDL điều kiện trong khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian Thuật toán khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng
cách thời gian (WIPrefixSpan [35]), trong đó các định nghĩa 7, 8, 9 dựa trên
giải thuật khai phá mẫu dãy thường xuyên PrefixSpan [9] và Hirate and
Yamana [21] với cách tiếp cận chính là đẩy các ràng buộc trọng số, ràng buộc
khoảng cách thời gian và độ hỗ trợ trong thuật toán khai phá mẫu dãy và đảm
bảo tính chất phản đơn điệu. Để tránh phải thực hiện kiểm tra tất cả khả năng kết hợp của một dãy các
ứng cử viên tiềm năng, ta có thể thay thế các thứ tự của các mục dữ liệu trong
từng thành phần trong dãy. Khi đó các mục trong một thành phần của một dãy
có thể được liệt kê theo 1 trật tự mà không mất tính tổng quát và có thể giả định
rằng thứ tự này luôn luôn được liệt kê theo thứ tự bảng chữ cái. 43 Ví dụ như dãy <(0,a) (1,abc) (2,ac) (3,d) (4,cf)> thay vì <(0,a) (1,acb)
(2,ac) (3,d) (4,fc)>. Với quy ước như vậy thì sự biểu hiện của một dãy là duy
nhất. Nếu ta theo thứ tự của các tiền tố của một dãy và CSDL điều kiện của tiền
tố đó chỉ có các hậu tố của một dãy thì ta có thể kiểm tra các dãy con theo thứ
tự sắp xếp trên và CSDL điều kiện theo tiền tố đó. Định nghĩa 7. (Tiền tố và Hậu tố trong dãy có khoảng cách thời gian): Các
mục dữ liệu trong một thành phần của dãy đã sắp xếp theo thứ tự chữ cái. Cho một dãy = <(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)>, một dãy s là một tập các mục ij ⊆ I. Khi đó tồn tại một giá trị j (1 ≤ j ≤ m) sao cho s ⊆ sj và t1, = t1, j . Ta định nghĩa tiền tố trong dãy có khoảng cách thời gian của với các giá trị s , t1, như sau: Prefix (,s, t1, ) = <(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,j,s)> Khi đó hậu tố trong dãy có khoảng cách thời gian của với các giá trị s , t1, được định nghĩa như sau: Postfix (,s, t1, ) = <(tj,j,s’j), (tj,j+1,sj+1), ..., (tj,m,sm)> Với s’j là một tập con của sj sau khi đã trừ đi tập s . Khi s’j = , thì hậu tố của với các giá trị s , t1, là: Postfix (,s, t1, ) = <(tj,j+1,sj+1), (tj,j+2,sj+2), ..., (tj,m,sm)> Mặt khác, khi không tồn tại một giá trị j thì hậu tố của với các giá trị s , t1, trở thành: Prefix (,s, t1, ) = Postfix (,s, t1, ) = Định nghĩa 8. (CSDL điều kiện trong dãy có khoảng cách thời gian): Cho một dãy = <(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)> của một CSDL dãy S có khoảng cách thời gian. Một CSDL điều kiện theo được định nghĩa là S|, là các hậu tố của các dãy trong S với tiền tố . 44 Định nghĩa 9. (Mẫu dãy ứng viên): Cho một ngưỡng hỗ trợ tối thiểu
wmin_sup. Một dãy α được gọi là dãy ứng viên mẫu dãy thường xuyên trọng
số chuẩn hóa với khoảng cách thời gian nếu thỏa mãn tính chất: Support(α) * MaxW wmin_sup và thỏa mãn các tính chất C1, C2, C3, C4 Với MaxW là giá trị lớn nhất của trọng số trong các mục trong S. Mẫu
dãy ứng viên được xây dựng nhằm mục đích tỉa bớt không gian tìm kiếm mà
vẫn đảm bảo tính phản đơn điệu trong khai phá mẫu dãy thường xuyên trọng
số chuẩn hóa với khoảng cách thời gian. Khi đó, bài toán khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian sử dụng CSDL điều kiện theo tiền tố được phát biểu như
sau: • Cho một CSDL dãy S có khoảng cách thời gian giữa các dãy, mỗi mục
ij ⊆ I được gán một trọng số wj, một ngưỡng hỗ trợ tối thiểu wmin_sup,
các ràng buộc khoảng cách thời gian C1, C2, C3, C4. Tìm tất cả các mẫu
dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian trong S,
tức là tìm tập L: L = {Sa ⊆ S | NWsupport(Sa ) wmin_sup&& t, thỏa mãn tính chất các ràng buộc C1, C2, C3, C4} • Mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian
không thỏa mãn tính chất phản đơn điệu, nghĩa là tập con của một mẫu
dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian không
nhất thiết phải là mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng
cách thời gian. 2.3.3. Ví dụ khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian sử dụng CSDL điều kiện theo tiền tố Cho một CSDL dãy S với khoảng cách thời gian như Bảng 2.6, giá trị các
trọng số của các mục dữ liệu như Bảng 2.7, giá trị wmin_sup =1.5, các giá trị
C1=1; C2=2; C3=2; C4=3. Khi đó việc khai phá các mẫu dãy thường xuyên trọng 45 số chuẩn hóa với khoảng cách thời gian trong CSDL dãy S theo phương pháp
WIPrefixSpan được thực hiện theo các bước như sau: iSID Dãy dữ liệu Tên mục Trọng
số 10 <(0,a),(1,abc),(3,ac)> a 0.9 20 <(0,ad),(3,c)> b 0.75 30 <(0,aef),(2,ab)> c 0.8 Bảng 2.7. Cơ sở dữ liệu dãy S d 0.85 e 0.75 f 0.7 Bảng 2.6. Giá trị trọng số của các mục dữ liệu Bước 1: Tìm các ứng viên của mẫu dãy thường xuyên với trọng số chuẩn
hóa có độ dài 1 Duyệt CSDL dãy S lần đầu tiên để tìm tất cả các ứng viên của mẫu dãy
thường xuyên trọng số chuẩn hóa với khoảng cách thời gian có độ dài 1, thực
hiện đếm độ hỗ trợ của mỗi mục. Một mục có độ dài 1 có thể không phải là một mẫu dãy thường xuyên có
trọng số chuẩn hóa nhưng có thể kết hợp với các mục khác có độ hỗ trợ lớn hơn
hoặc trọng số lớn hơn để trở thành mẫu dãy thường xuyên có trọng số trong các
mẫu có độ dài lớn hơn. Khi đó ta có các giá trị độ hỗ trợ của mỗi mục như sau: <0,a>: 3, <0,b>: 2, <0,c>: 2, <0,d>: 1, <0,e>: 1 , <0,f>: 1 46 Giá trị trọng số là (a: 0,9; b: 0,75; c: 0,8; d: 0,85; e: 0,75; f: 0,7) Giá trị MaxW = 0.9 Kiểm tra theo Định nghĩa 9, loại mục <0,d>, <0,e> và <0,f> do giá trị
support(<0,d)>*MaxW = 1*0,9=0,9 < wmin_sup; support(<0,e>)*MaxW =
1*0,9=0,9 < wmin_sup và support(<0,f>)*MaxW = 1*0,9=0,9 < wmin_sup Khi đó ta có các ứng viên mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian có độ dài 1 là: Q1 = <0,a>, <0,b>, <0,c> Kiểm tra theo Định nghĩa 6 với các ứng viên trong Q1, khi đó ta có các
mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian có độ dài
1 được nạp vào L là: NWsupport(<0,b>)= 2*0,75=1,5 NWsupport(<0,a>) = 3*0,9=2,7
NWsupport(<0,c>)= 2*0,8=1,6 L = <0,a>, <0,b>, <0,c> Bước 2: Chia không gian tìm kiếm Toàn bộ các ứng viên và mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian được khai phá trong các phân vùng gồm 03 vùng tương
ứng với 03 tiền tố gồm: (1) Mẫu dãy với tiền tố <0,a>
(2) Mẫu dãy với tiền tố <0,b>
(3) Mẫu dãy với tiền tố <0,c> Bước 3: Khai phá các tập con ứng viên và mẫu dãy thường xuyên trọng
số chuẩn hóa với khoảng cách thời gian Các tập con ứng viên và mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian được khai phá bằng cách xây dựng các CSDL điều kiện
tương ứng với các tiền tố và khai phá chúng bằng phương pháp đệ quy. Các
bước thực hiện như sau: 47 A. Tìm các ứng viên và các mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian với tiền tố <0,a> và các ràng buộc thời gian C1,
C2, C3, C4 Khi đó CSDL điều kiện với tiền tố <0,a> sẽ bao gồm các hậu tố được xây dựng theo định nghĩa 7: iSID Dãy dữ liệu 10 <(1,abc),(3,ac)> <(0,bc),(2,ac)> < (0,c)> <(0,d),(3,c)> 20 <(0,ef),(2,ab)> 30 <(0,b)> Bảng 2.8. Cơ sở dữ liệu điều kiện với tiền tố <0,a> Bằng cách quét CSDL điều kiện với tiền tố <0,a>, độ hỗ trợ của các mục dữ liệu của nó là: <1,a>: 1; <1,b>: 1; <1,c>: 1; <3,a>: 1; <3,c>: 2; <0,b>: 2; <0,c>: 1; <2,a>: 2; <2,c>: 1; <0,d>: 1; <0,e>: 1; <0,f>: 1; <2,b>: 1; Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 2 với tiền tố <0,a> support(<1,a>)*MaxW = 1*0,9=0,9 support(<1,b>)*MaxW = 1*0,9=0,9 support(<1,c>)*MaxW = 1*0,9=0,9 support(<3,a>)*MaxW = 1*0,9=0,9 support(<3,c>)*MaxW = 2*0,9=1,8 support(<0,b>)*MaxW = 2*0,9=1,8 support(<0,c>)*MaxW = 1*0,9=0,9 support(<2,a>)*MaxW = 2*0,9=1,8 support(<2,c>)*MaxW = 1*0,9=0,9 support(<0,d>)*MaxW = 1*0,9=0,9 48 support(<0,e>)*MaxW = 1*0,9=0,9 support(<0,f>)*MaxW = 1*0,9=0,9 support(<2,b>)*MaxW = 1*0,9=0,9 Các ứng viên có độ dài 2 với tiền tố <0,a> thỏa mãn độ hỗ trợ với trọng số lớn nhất là: <0,ab>, <(0,a),(2,a)>, <(0,a),(3,c)> - Kiểm tra các ứng viên trên với tính chất ràng buộc thời gian C1=1; C2=2; C3=2; C4=3 Khi đó, ứng viên <(0,a),(3,c)> bị loại do không thỏa mãn tính chất C2 = 2. Vì vậy: Q2 <0,a> = <0,ab>, <(0,a),(2,a)> Kiểm tra theo Định nghĩa 6 với các ứng viên trong Q2 <0,a>, khi đó ta có
các mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian có độ
dài 2 với tiền tố <0,a> được nạp vào L là: - Kiểm tra độ hỗ trợ với trọng số chuẩn hóa của các ứng viên <0,ab>, <(0,a),(2,a)> NWsupport(<0,ab>) = 2*(0,9+0,75)/2=1,65 NWsupport(<(0,a),(2,a)) = 2*(0,9+0,9)/2=1,8 L = L {<0,ab>, <(0,a),(2,a)>} Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên trọng số
chuẩn hóa với khoảng cách thời gian với tiền tố <0,a> sẽ tiếp tục được chia
thành 2 vùng tương ứng với 2 tiền tố gồm: (1) Mẫu dãy với tiền tố <0,ab >
(2) Mẫu dãy với tiền tố <(0,a),(2,a)> A.1. Đối với mẫu dãy với tiền tố <0,ab>, ta xây dựng CSDL điều kiện
với tiền tố <0,ab> với các mục dữ liệu trong tập ứng viên trong Q2 <0,a>. Khi đó CSDL điều kiện với tiền tố <0,ab> sẽ bao gồm các hậu tố được xây dựng theo định nghĩa 7: 49 SID Dãy dữ liệu 1 <(0,c),(2,ac)> Bảng 2.9. Cơ sở dữ liệu điều kiện với tiền tố <0,ab> Bằng cách quét CSDL điều kiện với tiền tố <0,ab>, độ hỗ trợ của các mục dữ liệu của nó là: <0,c>: 1; <2,a>: 1; <2,c>: 1 Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 3 với tiền tố <0,ab> support(<0,c>)*MaxW = 1*0,9=0,9 support(<2,a>)*MaxW= 1*0,9=0,9 support(<2,c>)*MaxW = 1*0,9=0,9 Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 3 với tiền tố <0,ab> là: Q3 <0,ab> = A.2. Đối với mẫu dãy với tiền tố <0,a),(2,a)>, ta xây dựng CSDL điều
kiện với các tiền tố tương ứng với các mục dữ liệu trong tập ứng viên
trong Q2 <0,a>. Cách khai phá mẫu dãy thường xuyên trọng số chuẩn
hóa với khoảng cách thời gian với mỗi tiền tố tương ứng cũng thực hiện
tương tự như bước A.1. B. Tìm các ứng viên và các mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian với các tiền tố <0,b>,<0,c> Đối với mẫu dãy với tiền tố <0,b>,<0,c>, ta xây dựng các CSDL điều
kiện với các tiền tố tương ứng với các mục dữ liệu trong tập ứng viên
trong Q1. Cách khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian với mỗi tiền tố tương ứng cũng thực hiện tương tự
như bước A và thực hiện đệ khai phá theo phương pháp đệ quy. 50 Bước 4: Kết quả là các mẫu dãy thường xuyên trọng số chuẩn hóa với
khoảng cách thời gian trong CSDL dãy S Các mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian
được khai phá lần lượt trong quá trình đệ quy đối với từng tiền tố. Trong phương
pháp khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời
gian này, kết quả sẽ ít hơn các mẫu dãy thường xuyên khi không gắn thêm yếu
tố trọng số của các mục dữ liệu. 2.3.4. Thuật toán WIPrefixSpan - Đầu vào : (1) CSDL dãy có khoảng cách thời gian: ISDB, (2) Ngưỡng hỗ trợ : wmin_sup, (3) Trọng số của các mục: wi W, (4) Ràng buộc khoảng cách thời gian C1, C2, C3, C4, - Đầu ra: Các mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời
gian L 51 Thuật toán WIPrefixSpan Bắt đầu 1) Đặt α = . 2) Đặt R = ; L = . 3) Duyệt lần đầu ISDB, tìm các mục ứng viên có độ dài =1 và thỏa mãn điều kiện support * MaxW wmin_sup Lặp với mọi mục i a) Đặt α =< (0, i) >, - Nạp R = {R, α}. - Kiểm tra điều kiện support(α)*NW(α) wmin_sup , nếu thỏa mãn L = {L, α}. b) Thực hiện R = WIPrefixSpan(ISDB|α,R,W,wmin_sup, C1, C2, C3, C4). Kết thúc lặp 4) Kết quả tập L. Kết thúc. 52 Thủ tục WIPrefixSpan (ISDB|α,R,W,wmin_sup, C1, C2, C3, C4) Bắt đầu: 1) Duyệt ISDB|α để tìm tất cả các cặp dãy với α và giá trị khoảng cách
thời gian giữa dãy đó với α trong cặp này, định nghĩa là (Δt,i) thỏa mãn điều kiện support (i)* MaxW wmin_sup, C1, và C2. 2) Đặt α =< α; (Δt; i)>. 3) Kiểm tra xem có thỏa mãn điều kiện C4 4) Chỉ khi thỏa mãn điều kiện C4 a) Thực hiện R = WIPrefixSpan (ISDB|α,R,W,wmin_sup, C1, C2, C3, C4). b) Khi α thỏa mãn điều kiện C3, R = {R, α}. c) Kiểm tra điều kiện support(α)*NW(α) wmin_sup, nếu thỏa mãn L = {L, α}., 5) Kết quả tập L. 53 2.4. BÀI TOÁN TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI
KHOẢNG CÁCH THỜI GIAN 2.4.1. Phát biểu bài toán Giả sử I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij I được
gán một giá trị trọng số w(j) với j=1,...,n. Dãy dữ liệu với khoảng cách thời
gian Si là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu dạng {(t1,1,Y1), (t1,2,Y2), (t1,3,Y3),..., (t1,m,Ym)} với Yj I trong đó (1 ≤ j ≤ m). CSDL
dãy với khoảng cách thời gian iSDB = {S1, S2, …, Sn} là một danh sách các cặp
(iSID,Sk) với iSID là định danh của một dãy và Sk là một dãy dữ liệu với khoảng
cách thời gian. Bảng 2.10 là một ví dụ về cơ sở dữ liệu dãy với khoảng cách thời gian. Bảng 2.11 là bảng trọng số của các mục trong CSDL iSDB. Bảng 2.10. Cơ sở dữ liệu dãy iSID Dãy dữ liệu 10 <(0, a),(1, abcdef)(2, aeg)> 20 <(0, ad), (1, abcdf), (2, bcef)> 30 <(0, a), (1, abcefh),(2, ad)> 40 <(0, a), (1, ac), (2, abd), (3, b), (4, c)> Bảng 2.11. Trọng số của các mục Tên mục Trọng số a 0.5 b 0.6 c 0.8 54 d 0.5 e 0.7 f 0.8 g 0.9 h 0.8 Bài toán khai phá top-k mẫu dãy thường xuyên có trọng số với khoảng cách thời gian được phát biểu như sau: Cho trước một CSDL với khoảng cách thời gian iSDB và một số tự nhiên
k, bài toán tìm tập các top-K mẫu dãy thường xuyên có trọng số với khoảng
cách thời gian tức là tìm k mẫu dãy có NWSupport lớn nhất thỏa mãn các ràng
buộc thời gian. 2.4.2. Mô tả thuật toán Phần này trình bày một phương pháp giải quyết bài toán Top-K mẫu dãy
dãy thường xuyên có trọng số với khoảng cách thời gian bằng cách áp dụng
thuật toán AprioriAll. Giải thuật như sau: Đầu vào : - Cơ sở dữ liệu dãy với khoảng cách thời gian iSDB - Các giá trị trọng số của các mục W(i) - Các ràng buộc thời gian C1, C2, C3, C4 - Giá trị k Đầu ra : Tập top-k mẫu dãy thường xuyên có trọng số với khoảng cách thời
gian.
[1] Start
[2] minsup =0;
[3] F1 = tập các ứng viên 1 phần tử; 55 [4] 𝐹 = ⋃ 𝐹𝑘𝑘
[5] L = tập các mẫu dãy sắp xếp theo thứ tự tăng dần của NWSupport; [6] Quét iSDB lần đầu để tìm ra các mẫu dãy ứng viên 1 phần tử đưa vào //F là tập tất cả các ứng viên [7] If support()*NW() minsup then [8] SAVE(,L,k,minsup); [9] End if;
[10] m=2;
[11] while Fm-1 ≠ null
[12] Sinh tập ứng viên Fm (tập ứng viên m phần tử) thỏa mãn các ràng F1; [13] Quét iSDB để tìm ra các ứng viên m phần tử a thỏa mãn buộc thời gian C1, C2, C3, C4; [14] Loại khỏi Fm các ứng viên không thỏa mãn Support(a)*maxW ≥ Support(a)*maxW ≥ minsup; [15] If support(a)*NW(a) ≥ minsup then
[16] SAVE(a,L,k,minsup); minsup; 56 Thủ tục SAVE [1] Start [2] L= L {r}; [3] If |L| > k then [4] If NWSupport(r) > wminsup then [5] While |L| > k Loại bỏ các mẫu dãy trong L có NWSupport Procedure SAVE (r,L,k,wminsup) [6] End while; [7] End if; [8] minsup = giá trị NWSupport nhỏ nhất trong L; [9] End if; [10] End; thấp nhất; Đầu tiên, đặt minsup=0. Sau đó tìm các mẫu dãy thường xuyên bằng cách
áp dụng phương pháp sinh mẫu dãy Apriori. Mỗi khi một mẫu dãy được tìm
thấy, nó sẽ được đưa vào một danh sách L các mẫu dãy được sắp xếp theo độ
hỗ trợ có trọng số NWSupport. Danh sách này được sử dụng để lưu các mẫu
dãy đã được tìm thấy. Khi có đủ k mẫu dãy trong danh sách L, giá trị minsup
sẽ được tăng lên bằng với NWSupport của mẫu dãy có giá trị NWSupport nhỏ
nhất trong L. Viêc tăng giá trị minsup sẽ giúp giảm bớt không gian tìm kiếm.
Sau khi tăng minsup, các mẫu dãy thường xuyên tìm được sẽ được đưa vào L,
các mẫu dãy trong L không thỏa mãn giá trị minsup mới sẽ bị loại ra khỏi L và
giá trị minsup sẽ được tiếp tục tăng lên bằng với giá trị NWSupport của mẫu
dãy có NWSupport nhỏ nhất trong L…. Thuật toán tiếp tục đến khi không thể
tìm ra được mẫu dãy nào nữa, khi đó thuật toán kết thúc và đưa ra top-k mẫu
dãy thường xuyên. Thủ tục SAVE thực hiện tăng giá trị minsup và cập nhật danh sách L mỗi
khi tìm thấy một mẫu dãy thường xuyên r. Đầu tiên, thêm r vào L, nếu L có
nhiều hơn k mẫu dãy và độ hỗ trợ có trọng số của r lớn hơn minsup thì loại bỏ
các mẫu dãy có NWSupport thấp nhất trong L sao cho L chỉ còn lại k mẫu dãy. 57 Cuối cùng, đặt giá trị minsup mới bằng với giá trị NWSupport nhỏ nhất trong
L. 2.4.3. Ví dụ thuật toán: Xét CSDL dãy với khoảng thời gian iSDB như trong Bảng 2.10. Mỗi mục
được gán 1 giá trị trọng số như trong Bảng 2.11. Đặt k=10, C1 = 0, C2= 3, C3=1,
C4 =3. Thuật toán thực hiện như sau: Bước thứ 1: Đặt minsup=0, m=1 (m là độ dài dãy). Duyệt CSDL iSDB lần đầu, ta có độ hỗ trợ của mỗi mục riêng lẻ trong CSDL lần lượt là: support(a) = 4, support(b) = 4, support(c) = 4, support(d) = 4 support(e) = 3, support(f) = 3, support(g) = 1, support(h) = 1 Khởi đầu L = ∅. Đưa các ứng viên 1 phần tử vào trong F1: F1= {a,b,c,d,e,f,g,h} Kiểm tra điều kiện độ hỗ trợ với trọng số, ta có: NWSupport(a) = support(a)*NW(a) = 4*0.5 = 2; NWSupport(b) = support(a)*NW(b) = 4*0.6 = 2.4; NWSupport(c) = support(a)*NW(c) = 4*0.8 = 3.2; NWSupport(d) = support(a)*NW(d) = 4*0.5 = 2; NWSupport(e) = support(a)*NW(e) = 3*0.7 = 2.1; NWSupport(f) = support(a)*NW(f) = 3*0.8 = 2.4; NWSupport(g) = support(a)*NW(g) = 1*0.9 = 0.9; NWSupport(h) = support(a)*NW(h) = 1*0.8 = 0.8; Vì minsup=0 nên không mẫu nào bị loại, gọi thủ tục SAVE: |L| = 8 < k (=10): không mẫu nào bị loại 58 Bước thứ 2 : Minsup = 0.8, m = 2 (m là độ dài dãy): Thực hiện hàm sinh mẫu dãy: Kết nối mỗi mẫu dãy ứng viên trong F1 với
nhau để lập thành một tập dãy ứng viên F2 thỏa mãn điều kiện các ràng buộc
thời gian C1, C2, C3, C4. Vì các mẫu dãy có thêm yếu tố thời gian, nên các mẫu
dãy sinh ra phải có đủ các khoảng thời gian khác nhau. F2={<(0,a)(1,a)>, <(0,a),(2,a)>, <(0,a),(3,a)> , <(0,a)(1,b)>, <(0,a),(2,b)>,
<(0,a),(3,b)>, <(0,a)(1,c)>, <(0,a),(2,c)>, <(0,a),(3,c)>, <(0,a)(1,d)>,
<(0,a),(2,d)>, <(0,a),(3,d)>, <(0,a)(1,e)>, <(0,a),(2,e)>, <(0,a),(3,e)>…. } Quét CSDL iSDB để tìm ra các mẫu dãy ứng viên α thỏa mãn điều kiện
support(α)*MaxW ≥ minsup, loại khỏi F2 các ứng viên không thỏa mãn điều
kiện support(α)*MaxW ≥ minsup. Support(<0,ae>)*MaxW = 2*0.9 =1.8 Support(<0,cd>)*MaxW = 2*0.9 =1.8 Support(<0,be>)*MaxW = 3*0.9 =2.7 Support(<0,bd>)*MaxW = 3*0.9 =2.7 Support(<0,ef>)*MaxW = 3*0.9 =2.7 Support(<0,af>)*MaxW = 3*0.9 =2.7 Support(<0,bf>)*MaxW = 3*0.9 =2.7 Support(<0,cf>)*MaxW = 3*0.9 =2.7 Support(<0,ce>)*MaxW = 3*0.9 =2.7 Support(<0,bc>)*MaxW = 4*0.9 =3.6 Support(<0,ad>)*MaxW = 4*0.9 =3.6 Support(<0,ac>)*MaxW = 4*0.9 =3.6 Support(<0,ab>)*MaxW = 4*0.9 =3.6 Support(<0,df>)*MaxW = 2*0.9 =1.8 59 ….. F2 sau bước này gồm 40 mẫu dãy là: F2={<0,ae>, <0,cd>, <0,be>, <0,bd>, <0,ef>, … <(0,a),(2,d)>, <(0,a),(3,d)>, <(0,b),(1,a)>, <(0,d),(1,a)>, <(0,a),(2,b)>, <(0,c),(1,d)>} Kiểm tra điều kiện support(a)*NW(a) ≥ minsup với 40 mẫu dãy trong F2, nếu thỏa mãn thì gọi thủ tục SAVE. Support(<0,ae>)*NW(<0,ae>) = 2*0.6 =1.2 Support(<0,cd>)*NW(<0,cd>) = 2*0.65 =1.3 Support(<0,be>)*NW(<0,be>) = 3*0.65 =1.95 Support(<0,bd>)*NW(<0,bd>) = 3*0.55 =1.65 Support(<0,ef>)*NW(<0,ef>) = 3*0.75 =2.25 Support(<0,af>)*NW(<0,af>) = 3*0.65 =1.95 Support(<0,bf>)*NW(<0,bf>) = 3*0.7 =2.1 Support(<0,cf>)*NW(<0,cf>) = 3*0.8 =2.4 Support(<0,ce>)*NW(<0,ce>) = 3*0.75 =2.25 Support(<0,bc>)*NW(<0,bc>) = 4*0.7 =2.1 Support(<0,ad>)*NW(<0,ad>) = 4*0.5 =2 Support(<0,ac>)*NW(<0,ac>) = 4*0.65 =2.6 Support(<0,ab>)*NW(<0,ab>) = 4*0.55 =2.2 Support(<0,df>)*NW(<0,df>) = 2*0.65 =1.3 …. Thủ tục SAVE thực hiện lưu k =10 mục có NWSupport lớn nhất và tăng ngưỡng hỗ trợ minsup bằng giá trị NWSupport nhỏ nhất trong L. Sau bước này, tập L có các mẫu dãy sau: L={<(0,c)>:3.2, <(0,ac)>:2.6, <(0,a)(1,c)>:2.6, <(0,g)>:2.4, <(0,b)>:2.4,
<(0,cg)>:2.4, <(0,eg)>:2.25, <(0,ce)>:2.25, <(0,ab)>:2.2, <(0,a),(1,b)>:2.2} 60 Và minsup = 2.2 Bước thứ 3 : Minsup = 2.2, m = 3 (m là độ dài dãy): Thực hiện hàm sinh mẫu dãy: Kết nối mỗi mẫu dãy ứng viên trong F2 với
nhau để lập thành một tập dãy ứng viên F3 thỏa mãn các ràng buộc thời gian C1,
C2, C3, C4. F3={<(0,ac)(1,c)>, <(0,acf)>, <(0,ace)> , <(0,abc)>, <(0,ac),(1,b)>, <(0,acd)>, <(0,a)(1,c)>, <(0,ac),(1,a)>,…. } Quét CSDL iSDB để tìm ra các mẫu dãy ứng viên α thỏa mãn điều kiện
support(α)*MaxW ≥ minsup, loại khỏi F3 các ứng viên không thỏa mãn điều
kiện support(α)*MaxW ≥ minsup. Support(<(0,a),(1,ad)>)*MaxW = 4*0.9 =3.6 Support(<(0,a),(1,ac)>)*MaxW = 4*0.9 =3.6 Support(<(0,a),(1,ab)>)*MaxW = 4*0.9 =3.6 Support(<0,bce>)*MaxW = 3*0.9 =2.7 Support(<0,cef>)*MaxW = 3*0.9 =2.7 Support(<(0,a),(1,a),(2,a)>)*MaxW = 3*0.9 =2.7 Support(<(0,a),(1,c),(2,a)>)*MaxW = 3*0.9 =2.7 Support(<(0,ad),(1,a)>)*MaxW = 2*0.9 =1.8 Support(<(0,ab),(1,a)>)*MaxW = 2*0.9 =1.8 ….. F3 sau bước này gồm 22 mẫu dãy là: F3= {< (0,a),(1,ad)>, <(0,a),(1,ac)>, <(0,a),(1,ab)>, <0,bce>, <0,cef>, … , <(0,a),(1,a),(2,a)>, <(0,a),(1,c),(2,a)>} Kiểm tra điều kiện support(a)*NW(a) ≥ minsup với các mẫu dãy trong F3, nếu thỏa mãn thì gọi thủ tục SAVE. Support(<(0,a),(1,ad)>)*NW(<(0,a),(1,ad)>) = 4*0.5 =2 61 Support(<(0,a),(1,ac)>)*NW(<(0,a),(1,ac)>) = 4*0.6 =2.4 Support(<(0,a),(1,ab)>)*NW(<(0,a),(1,ab)>) = 4*0.53 =2.13 Support(<0,bce>)*NW(<0,bce>) = 3*0.7 =2.1 Support(<0,cef>)*NW(<0,cef>) = 3*0.76 =2.3 Support(<(0,a),(1,a),(2,a)>)*NW(<(0,a),(1,a),(2,a)>) = 3*0.73 =2.2 Support(<(0,a),(1,c),(2,a)>)*NW(<(0,a),(1,c),(2,a)>) = 3*0.7 =2.1 ….. Thủ tục SAVE thực hiện lưu k =10 mục có NWSupport lớn nhất và tăng ngưỡng hỗ trợ minsup bằng giá trị NWSupport nhỏ nhất trong L. Sau bước này, tập L có các mẫu dãy sau: L={<(0,c)>:3.2, <(0,ac)>:2.6, <(0,a)(1,c)>:2.6, <(0,g)>:2.4, <(0,b)>:2.4,
<(0,cg)>:2.4, <(0,a),(1,ac)>:2.4, <(0,cef)>:2.3, <(0,eg)>:2.25, <(0,ce)>:2.25} Giá trị minsup được tăng lên thành 2.25. Các bước lặp tiếp theo: Tiếp tục thực hiện hiện hàm sinh mẫu dãy: Kết nối mỗi mẫu dãy ứng viên
trong Fk-1 với nhau để lập thành một tập mẫu dãy ứng viên Fk , và thực hiện
tương tự như các bước trên. Kết quả cuối cùng tập L sau khi kết thúc thuật toán là: L={<(0,c)>:3.2, <(0,ac)>:2.6, <(0,a)(1,c)>:2.6, <(0,g)>:2.4, <(0,b)>:2.4,
<(0,cg)>:2.4, <(0,a),(1,ac)>:2.4, <(0,cef)>:2.3, <(0,eg)>:2.25, <(0,ce)>:2.25} 62 CHƯƠNG 3. THỬ NGHIỆM VÀ NHẬN XÉT 3.1. THỬ NGHIỆM Phần này thử nghiệm so sánh thuật toán đề xuất trong 2 trường hợp: có sử dụng ràng buộc thời gian và không sử dụng ràng buộc thời gian. Các thuật toán được thực hiện trên ngôn ngữ lập trình Java và được thử
nghiệm trên một máy tính có bộ xử lý Intel core-i7, 16GB bộ nhớ trong và chạy
Windows 10. Các bộ dữ liệu thử nghiệm là các bộ dữ liệu thực được lấy trên trang web http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php
bao gồm: dài trung bình 1 dãy là 2,42. - Bộ dữ liệu Bible với 36369 dãy và 13905 mục khác nhau. Độ dài trung bình 1 dãy là 21,6. - Bộ dữ liệu Fifa với 20450 dãy và 2990 mục khác nhau. Độ dài trung bình 1 dãy là 34,74. trung bình 1 dãy là 33,8 1 dãy là 51,997. Bảng 3.1. Mô tả các dữ liệu thử nghiệm Bộ dữ liệu Số dãy Số mục Độ dài trung bình Phân loại BMSWebView1 59601 497 2,42 Web log 36369 13905 21,6 Văn bản Bible 20450 2990 34,74 Web log Fifa Leviathan 5834 9025 33,8 Văn bản Sign 800 267 51,997 Văn bản 63 Các bộ dữ liệu đưa vào nghiên cứu, thử nghiệm cài đặt với số lượng mẫu
dãy, số mục của dãy, độ dài trung bình khác nhau nhằm làm rõ hơn ảnh hưởng
của các tham số trọng số, khoảng cách thời gian, top-k đưa vào trong thuật toán. Các bộ dữ liệu trên không có giá trị trọng số của các mục, vì vậy để phù
hợp với bài toán khai phá mẫu dãy có trọng số, giá trị trọng số sẽ được sinh
ngẫu nhiên trong khoảng [0,2;0,8]. Trong thực tế, các mục có giá trị cao thường
sẽ ít xuất hiện trong CSDL. Vì vậy, trong thử nghiệm này, tôi sử dụng phân bố
chuẩn để sinh ngẫu nhiên trọng số. Các bộ dữ liệu cũng không có giá trị thời gian. Do vậy, dữ liệu thời gian sẽ
được sinh theo thứ tự tăng dần, mỗi mẫu dãy liền nhau sẽ cách nhau 1 khoảng
cách thời gian. Giá trị k được đưa vào lần lượt từ 1000 đến 10000. Do độ dài trung bình
của các dãy trong từng bộ dữ liệu là khác nhau, các ràng buộc thời gian được
đưa vào khác nhau theo từng bộ dữ liệu. Bảng dưới đây mô tả giá trị ràng buộc
thời gian của từng bộ dữ liệu. Bảng 3.2. Giá trị ràng buộc thời gian Bộ dữ liệu C1 C2 C3 C4 BMSWebView1 1 5 1 10 Bible 1 5 2 20 Fifa 1 5 1 30 Leviathan 1 5 1 30 Sign 1 5 5 40 Kết quả thử nghiệm thuật toán được thể hiện dưới đây: 64 Hình 3.1. Thời gian chạy với bộ dữ liệu BMSWebView1 Hình 3.2. Thời gian chạy với bộ dữ liệu Bible 65 Hình 3.3. Thời gian chạy với bộ dữ liệu Fifa Hình 3.4. Thời gian chạy với bộ dữ liệu Leviathan 66 Hình 3.5. Thời gian chạy với bộ dữ liệu Sign 67 Hình 3.6. Bộ nhớ sử dụng với bộ dữ liệu BMSWebView1 Hình 3.7. Bộ nhớ sử dụng với bộ dữ liệu Bible 68 Hình 3.8. Bộ nhớ sử dụng với bộ dữ liệu Fifa Hình 3.9. Bộ nhớ sử dụng với bộ dữ liệu Leviathan 69 Hình 3.10. Bộ nhớ sử dụng với bộ dữ liệu Sign 3.2. NHẬN XÉT Có thể thấy trong các thử nghiệm thuật toán chạy tốt hơn trong trường hợp
có sử dụng ràng buộc thời gian cả về thời gian chạy và bộ nhớ sử dụng. Điều
này cũng dễ hiểu vì khi đưa vào ràng buộc thời gian, số ứng viên phải sinh ra
sẽ giảm đi rất nhiều, do đó làm giảm không gian tìm kiếm và rút ngắn thời gian
thực hiện. Thời gian chạy của thuật toán lâu hơn khi chạy với bộ dữ liệu lớn hơn do thuật toán phải quét dữ liệu nhiều lần hơn. Thời gian chạy, bộ nhớ sử dụng bị ảnh hưởng nhiều với các tham số trọng
số, khoảng cách thời gian, topk khác nhau trên các bộ dữ liệu có số lượng mẫu
dãy, số mục của dãy, độ dài trung bình khác nhau. 70 CHƯƠNG 4. KẾT LUẬN VÀ KIẾN NGHỊ 4.1. KẾT LUẬN Khai phá mẫu dãy nói riêng hay khai phá dữ liệu nói chung được ứng dụng
rất rộng rãi trong thực tế, như phân tích thị trường, phân tích mẫu truy cập
website, phát hiện xâm nhập trong môi trường mạng, dự báo nhu cầu mua sắm
của khách hàng,… Luận văn này đã: - Nghiên cứu tìm hiểu về khai phá mẫu dãy thường xuyên và một số mở rộng. Nghiên cứu một số thuật toán liên quan như Apriori, Prefixspan. - Nghiên cứu tìm hiểu về khai phá Top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian. - Nghiên cứu về phát triển các mẫu dãy có độ hỗ trợ với trọng số cao trước,
số mẫu dãy ứng viên sinh ra sẽ giảm đi bớt làm giảm đáng kể không gian tìm
kiếm do đó tăng hiệu suất cho giải thuật. - Nghiên cứu cũng có ý nghĩa hơn khi xét tới các mẫu dãy xảy ra trong 1 khoảng thời gian nhất định. - Nghiên cứu lý thuyết và nghiên cứu thực nghiệm: + Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận văn đưa ra dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. + Về nghiên cứu thực nghiệm: luận văn thực hiện cài đặt các thuật
toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so
sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ
đó kết luận tính đúng đắn của kết quả nghiên cứu. - Nghiên cứu thử nghiệm thuật toán Top-K mẫu dãy thường xuyên trọng số với khoảng cách thời gian dựa trên giải thuật AprioriALL. - So sánh, đánh giá thuật toán Top-K mẫu dãy thường xuyên trọng số có và không có khoảng cách thời gian. 71 4.2. KIẾN NGHỊ Dữ liệu thực tế rất quan trọng và phức tạp, khai phá mẫu dãy ngoài việc
quan tâm đến độ hỗ trợ còn quan tâm cả đến trọng số và khoảng cách thời gian.
Để khai thác dữ liệu hiệu quả hơn, các nghiên cứu tiếp theo phải quan tâm đến
lợi ích,… của dãy. Trên thế giới hiện có một số công trình, ngoài quan tâm đến độ hỗ trợ,
trọng số và khoảng cách thời gian thì còn quan tâm đến cổ phần, lợi ích,… của
dãy, chẳng hạn như thuật toán Uspan của tác giả J.Yin và các cộng sự để giải
quyết bài toán về Khai phá mẫu dãy thường xuyên lợi ích cao. 72 TÀI LIỆU THAM KHẢO [1] R.Agrawal, T.Imielinski, and A.Swami, 1993, "Mining Association
Rules between Sets of Items in Large Databases," in Proceedings of
the 1993 ACM SIGMOD International Conference on Management of
Data. [2] J. Han, J. Pei, Y. Ying and R. Mao, 2004, "Mining frequent patterns
without candidate generation: a frequent-pattern tree approach," Data
Mining and Knowledge Discovery, vol. 8, p. 53–87. [3] M. Zaki, 2000, "Scalable algorithms for association mining," IEEE
Transactions on Knowledge and Data Engineering, vol. 12, p. 372–
390. [4] T. Uno, M. Kiyomi and H. Arimura, 2004, "LCM ver. 2: Efficient
mining algorithms for frequent/closed/maximal itemsets," in IEEE
International Conference on Data Mining Workshop on Frequent
Itemset Mining Implementations. [5] J. Pei, J. Han, H. Lu, S. Nishio, S. Tang and D. Yang, 2001, "H-mine:
Hyper-structure mining of frequent patterns in large databases," in
IEEE International Conference on Data Mining, p. 441–448. [6] R. Agrawal and R. Srikant, 1995, "Mining sequential patterns," in The International Conference on Data Engineering, p. 3–14. [7] S. Aseervatham, A. Osmani and E. Viennet, 2006, "bitSPADE: A
lattice-based sequential pattern mining algorithm using bitmap
representation," in The International Conference on Data Mining, p.
792–797. 73 [8] Ayres, J., Gehrke, J., Yiu, T. and Flannick, J, 2002, "Sequential Pattern
Mining using Bitmap Representation," in Proc. of ACM SIGKDD’02, [9] J. Pei, J. Han, B.M. Asi, H. Pino, 2001, "PrefixSpan: Mining
Sequential Patterns Efficiently by Prefix-Projected Pattern Growth," in
Proceedings of the Seventeenth International Conference on Data
Engineering. [10] M. Garofalakis, R. Rastogi and K. Shim, 1999, "SPIRIT: Sequential
in The pattern mining with regular expression constraints,"
International Conference on Very Large Databases, p. 223–234. [11] R. Agrawal, R.Srikant, 1996, "Mining sequential patterns:
Generallizations and performance improvements," Lecture Notes in
Computer Science, vol. 1057, pp. 3-17. [12] M. Zaki, 2001, "SPADE: An efficient algorithm for mining frequent sequences," Machine learning, vol. 42, p. 31–60. [13] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal and M. Hsu, 2000,
"FreeSpan: frequent patternprojected sequential pattern mining," in
ACM SIGKDD International Conference on Knowledge Discovery and
Data Mining, p. 355–359. [14] B. Vo, F. Coenen, B. Le, 2013, "A new method for mining Frequent
Weighted Itemsets based on WIT-trees," in Expert Systems with
Applications. [15] C.H.Cai, A.W.Chee Fu, C.H.Cheng, and W.W.Kwong, 1998, "Mining
Association Rules with Weighted Items," in Proceedings of the 1998
International Symposium on Database Engineering & Applications,
Cardiff, Wales. 74 [16] F. Tao, F. Murtagh, M. Farid, 2003, "Weighted Association Rule
Mining Using Weighted Support and Significance Framework," in
Proceedings of 9th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining. [17] G.C. Lan, T.P. Hong, H.Y. Lee, 2014, "An efficient approach for
finding weighted sequential patterns from sequence databases," in
Applied Intelligence. [18] M. S. Khan, M. Muyeba, F. Coenen, 2008, "Weighted Association
Rule Mining from Binary and Fuzzy Data," in Proceedings of 8th
Industrial Conference, ICDM 2008. [19] J. Ren, J. Yang and Y. Li, 2008, "Mining weighted closed sequential
patterns in large databases," in The International Conference on Fuzzy
Systems and Knowledge Discovery, p. 640–644. [20] U. Yun, 2008, "An efficient mining of weighted frequent patterns with
length decreasing support constraints," Knowledge-Based Systems,
Vols. Vol. 21,No. 8, p. 741–752. [21] H. Yu and H. Yamana, 2006, "Generalized sequential pattern mining with item intervals," Journal of Computers, vol. 1, p. 51–60. [22] J. Chang, 2011, "Mining weighted sequential patterns in a sequence
database with a time-interval weight," Knowledge-Based Systems, vol.
24, p. 1–9. [23] U. Yun, J.J. Leggett, 2005, "WFIM: weighted frequent itemset mining
with a weight range and a minimum weight," in 5th SIAM Int. Conf. on
Data Mining. 75 [24] W.Wang, J.Yang, and P.S.Yu, 2000, "Efficient Mining of Weighted
Association Rules (WAR)," in Proceedings of the Sixth ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining. [25] U. Yun and J. Leggett, 2006, "WSpan: Weighted Sequential pattern
mining in large sequence databases," in The International IEEE
Conference Intelligent Systems, p. 512–517. [26] U. Yun, K.H. Ryu, 2011, "Approximate weighted frequent pattern mining with/without noisy environments,". [27] U. Yun, G. Pyun, E. Yoon, 2015, "Efficient Mining of Robust Closed
Weighted Sequential Patterns Without Information Loss," Vols. Vol.
24, No. 1, p. 28 pages. [28] K. Chuang, J. Huang and M. Chen, 2008, "Mining Top-K Frequent
Patterns in the Presence of the Memory Constraint," VLDB Journal,
vol. 17, pp. 1321-1344. [29] P. Tzvetkov, X. Yan and J. Han, 2003, "TSP: Mining Top-K Closed Sequential Patterns," ICDM, pp. 347-354. [30] P. Fournier-Viger and V. Tseng, 2011, "Mining top-k sequential rules,"
in The International Conference on Advanced Data Mining and
Applications, p. 180–194. [31] J. Wang and J. Han, TFP, 2005, "An Efficient Algorithm for Mining
Top-K Frequent Closed Itemsets," TKDE, vol. 17, pp. 652-664. [32] P. Fournier-Viger, A. Gomariz, T. Gueniche, E. Mwamikazi and R.
Thomas, 2013, "TKS: Efficient Mining of Top-K Sequential Patterns,"
in The International Conference on Advanced Data Mining and
Applications, p. 109–120. 76 [33] P. Fournier-Viger, C.-W. Wu and V. Tseng, 2012, "Mining top-k
association rules," in The Canadian Conference on Artificial
Intelligence, p. 61–73. [34] Trần Huy Dương, Vũ Đức Thi, 2013, “WPrefixSpan: Thuật toán khai
phá mẫu dãy thường xuyên với trong số chuẩn hóa sử dụng CSDL tiền
tố,” trong Kỷ yếu hội nghị Khoa học Quốc gia lần thứ VI- Nghiên cứu
cơ bản và ứng dụng CNTT (FAIR). [35] V. Đ. T. Trần Huy Dương, 2015, "Thuật toán khai phá mẫu dãy thường
xuyên trọng số chuẩn hóa với khoảng cách thời gian," Chuyên san Tạp
chí Công nghệ thông tin và truyền thông, vol. 2, pp. 72-81. 77Kết thúc.
[17] End if;
[18] m=m+1;
[19] End while;
[20] Output L;
[21] End;
- L = {c:3.2, b:2.4, f:2.4, e:2.1, a:2, d:2, g:0.9, h:0,8}
-
- Minsup = 0.8 (=giá trị NWSupport của mẫu dãy nhỏ nhất trong L)
- Sau bước 1, ta có L = {c:3.2, b:2.4, f:2.4, e:2.1, a:2, d:2, g:0.9, h:0,8}
- Bộ dữ liệu BMSWebView1 với 59601 dãy và 497 mục khác nhau. Độ
- Bộ dữ liệu Leviathan với 5834 dãy và 9025 mục khác nhau. Độ dài
- Bộ dữ liệu Sign với 800 dãy và 267 mục khác nhau. Độ dài trung bình
