Luận văn Thạc sĩ Công nghệ thông tin: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

32
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài là 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: 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

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ố ........................................ 24 Bảng 1.7. Cơ sở dữ liệu điều kiện với tiền tố ........................................ 24 Bảng 1.8. Cơ sở dữ liệu điều kiện với tiền tố ...................................... 25 Bảng 1.9. Cơ sở dữ liệu điều kiện với tiền tố .................................... 25 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ố ........................................ 36 Bảng 2.5. Cơ sở dữ liệu điều kiện với tiền tố .................................... 37 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ố ....................................... 48 Bảng 2.9. Cơ sở dữ liệu điều kiện với tiền tố ..................................... 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ợ : SC(X) Supp (X) = P (X) = (1.1) 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) supp(X∪Y) Conf (X→Y) = P (Y|X) = = (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 3 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
β đượ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ó: SC(Sa ) support(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