Luận văn Thạc sĩ Công nghệ thông tin: Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian

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

Thêm vào BST

Báo xấu

55
lượt xem 4
download

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

Mục tiêu của luận văn "Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian" là tập trung nghiên cứu bài toán khai phá mẫu dãy thường xuyên, mẫu dãy lợi ích cao và mẫu dãy lợi ích cao với khoảng cách thời gian. Mời các bạn cùng tham khảo nội dung chi tiết.

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: Khai phá mẫu dãy lợi ích cao 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Ệ ----------------------------- Trần Thế Anh KHAI PHÁ MẪU DÃY LỢI ÍCH CAO 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Ệ ----------------------------- Trần Thế Anh KHAI PHÁ MẪU DÃY LỢI ÍCH CAO 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: Hướng dẫn 1 : TS. Đặng Thị Oanh Hướng dẫn 2 : PGS. TS. Phạm Thanh Giang Hà Nội – 2020
Lời cam đoan Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất cứ công trình nào. TÁC GIẢ LUẬN VĂN Trần Thế Anh
Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn sâu sắc tới TS. Đặng Thị Oanh và PGS. TS Phạm Thanh Giang đã tận tình giúp đỡ, hướng dẫn, định hướng tôi trong quá trình nghiên cứu và hoàn thành luận văn này. Tôi xin cảm ơn Khoa Công nghệ thông tin và Truyền thông - Học Viện khoa học và Công nghệ đã tạo điều kiện cho tôi hoàn thành chương trình học tập và nghiên cứu trong hai năm học vừa qua. Tôi cũng xin chân thành cảm ơn Lãnh đạo Viện Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận lợi cho quá trình học tập của mình, cảm ơn các các bộ của phòng Công nghệ phần mềm trong quản lý đã nhiệt tình trong công tác, giúp tôi dành thời gian hoàn thành luận văn. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn là nguồn động viên, ủng hộ, giúp tôi thêm động lực để hoàn thành tốt luận văn này. Trần Thế Anh
Danh mục các ký hiệu và chữ viết tắt STT Từ viết Tiếng Anh Tiếng Việt tắt 1 CSDL Cơ sở dữ liệu Khai phá mẫu dãy thường 2 SPM Sequential pattern mining xuyên 3 SDB Sequence Database Cơ sở dữ liệu dãy High utility sequential Khai phá mẫu dãy lợi ích 4 HUSPM pattern mining cao Quantitative Sequence Cơ sở dữ liệu dãy định 5 QSDB Database lượng Cơ sở dữ liệu dãy định Quantitative item interval 6 QiSDB lượng với khoảng cách thời Sequence Database gian
Danh mục các bảng Bảng 1.1 Cơ sở dữ liệu dãy SDB ................................................................ 7 Bảng 1.2 Cơ sở dữ liệu chiếu với tiền tố ........................................... 17 Bảng 1.3 Cơ sở dữ liệu chiếu với tiền tố ...................................... 17 Bảng 2.1 Cơ sở dữ liệu dãy định lượng QSDB ........................................ 23 Bảng 2.2 Bảng lợi ích ngoài ...................................................................... 24 Bảng 2.3 Sinh mẫu dãy ứng viên trong thuật toán UL ............................. 31 Bảng 2.4 Sinh mẫu dãy ứng viên trong thuật toán US ............................. 34 Bảng 2.5 Bảng lợi ích của các mẫu dãy 1 phần tử trong QSDB............... 37 Bảng 2.6 Bảng chỉ mục ............................................................................. 38 Bảng 2.7 Lợi ích của từng mục dữ liệu trong từng dãy Si ........................ 41 Bảng 2.8 Lợi ích của các dãy Si ................................................................ 41 Bảng 2.9 CSDL thu được sau khi loại bỏ ứng viên không tiềm năng ...... 42 Bảng 2.10 CSDL chiếu QSDB|a của mẫu dãy ................................... 42 Bảng 2.11 Lợi ích của các dãy trong QSDB|a ........................................... 43 Bảng 2.12 Bảng lợi ích của các mẫu dãy 2 phần tử với tiền tố ......... 43 Bảng 2.13 CSDL QSDB|a mới sau khi loại bỏ mục f ............................... 44 Bảng 2.14 CSDL chiếu QSDB|aa của mẫu dãy ............................... 44 Bảng 3.1 Cơ sở dữ liệu dãy lợi ích cao với khoảng cách thời gian QiSDB ......................................................................................................................... 48 Bảng 3.2 Bảng lợi ích ngoài ...................................................................... 49 Bảng 3.3 Bảng lợi ích của các mẫu dãy 1 phần tử trong QiSDB ............. 53 Bảng 3.4 Sinh mẫu dãy ứng viên trong UIL ............................................. 59 Bảng 3.5 Đặc điểm các tập dữ liệu thử nghiệm ........................................ 60 Bảng 3.6 Ràng buộc thời gian ................................................................... 61
Danh mục các hình vẽ, đồ thị Hình 1.1. Các bước sinh mẫu dãy của thuật toán GSP ............................. 12 Hình 3.1 Thời gian chạy Bộ dữ liệu BMSWebView1 .............................. 62 Hình 3.2 Thời gian chạy Bộ dữ liệu BMSWebView2 .............................. 62 Hình 3.3 Thời gian chạy Bộ dữ liệu Bible ................................................ 63 Hình 3.4 Thời gian chạy Bộ dữ liệu Fifa .................................................. 63 Hình 3.5 Bộ nhớ sử dụng trên bộ dữ liệu BMSWebView1 ...................... 64 Hình 3.6 Bộ nhớ sử dụng trên bộ dữ liệu BMSWebView2 ...................... 64 Hình 3.7 Bộ nhớ sử dụng trên bộ dữ liệu Bible ........................................ 65 Hình 3.8 Bộ nhớ sử dụng trên bộ dữ liệu Fifa ......................................... 65
MỤC LỤC MỞ ĐẦU .................................................................................................... 3 CHƯƠNG 1. TỔNG QUAN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG ................................................................ 5 1.1. GIỚI THIỆU ..................................................................................... 5 1.2. MỘT SỐ KHÁI NIỆM CƠ BẢN ............................................................ 6 1.3. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ............................................. 9 1.3.1. Thuật toán GSP:...................................................................... 10 1.3.2. Thuật toán PrefixSpan: ........................................................... 13 a) Một số định nghĩa: .............................................................................13 b) Mô tả thuật toán: ...............................................................................15 1.4. MỞ RỘNG BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ............ 17 1.5. KẾT LUẬN CHƯƠNG 1 ................................................................... 19 CHƯƠNG 2. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO ..................... 21 2.1. GIỚI THIỆU ................................................................................... 21 2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO .................................. 23 2.3. THUẬT TOÁN UL, US ................................................................... 28 2.3.1. Thuật toán UL: ........................................................................ 28 2.3.2. Thuật toán US: ........................................................................ 32 2.4. THUẬT TOÁN PHUS ..................................................................... 35 2.4.1. Bảng lợi ích:............................................................................ 36 2.4.2. Bảng chỉ mục: ......................................................................... 37 2.5. KẾT LUẬN CHƯƠNG 2 ................................................................... 44 CHƯƠNG 3. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN ................................................................... 46 3.1. GIỚI THIỆU ................................................................................... 46 3.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN 47 3.2.1. Một số định nghĩa: .................................................................. 47 1
3.2.2. Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian ...... 51 3.2.3. Thuật toán UIL: ...................................................................... 52 a) Ràng buộc thời gian:..........................................................................52 b) Bảng lợi ích: ......................................................................................52 c) Giảm dần cận trên lợi ích swu ...........................................................53 3.2.4. Thử nghiệm thuật toán UIL..................................................... 60 3.3. KẾT LUẬN CHƯƠNG 3 ................................................................... 66 CHƯƠNG 4. KẾT LUẬN VÀ KIẾN NGHỊ ...................................... 67 TÀI LIỆU THAM KHẢO ...................................................................... 69 2
MỞ ĐẦU Cùng với sự bùng nổ của ngành công nghệ thông tin trong vài thập kỷ qua, dữ liệu được sinh ra và lưu trữ trong các cơ sở dữ liệu ngày càng nhiều lên. Việc phân tích dữ liệu bằng phương pháp thủ công do vậy ngày càng khó khăn và tốn thời gian. Từ thực tế đó, một lĩnh vực nghiên cứu mới đã nổi lên để phát triển các kỹ thuật phân tích dữ liệu tự động: Khai phá dữ liệu. Mục tiêu của khai phá dữ liệu là tìm ra tri thức từ cơ sở dữ liệu. Khai phá dữ liệu gồm nhiều tác vụ khác nhau như: Phân loại dữ liệu (Classification), Gom cụm dữ liệu (Clustering), Khai phá luật kết hợp (Association Rule) … Khai phá tập mục thường xuyên là một bài toán con của bài toán khai phá luật kết hợp. Khởi nguồn là nghiên cứu của Agrawal [1] phân tích dữ liệu mua sắm của khách hàng trong siêu thị. Khai phá tập mục thường xuyên tập trung xác định các tập mục thường xuyên (frequent itemsets), nghĩa là các mục thường xuất hiện cùng nhau trong CSDL. Khai phá mẫu dãy thường xuyên là một bài toán mở rộng của khai phá tập mục thường xuyên. Các mẫu dãy là các phần tử được sắp xếp theo một thứ tự nhất định (thường là thứ tự thời gian). Mục tiêu của khai phá mẫu dãy thường xuyên là tìm ra các mẫu dãy thường xuyên (frequent sequence patterns), nghĩa là các mẫu dãy thường xuất hiện cùng nhau trong CSDL. Bài toán khai phá mẫu dãy thường xuyên cũng như tập mục thường xuyên sử dụng độ đo là tần xuất xuất hiện của dữ liệu (frequency). Tuy nhiên, tần xuất xuất hiện của dữ liệu không phải lúc nào cũng là độ đo tốt nhất để tìm ra các mẫu dãy có giá trị. Vì đôi khi một số mặt hàng có số lượng mua ít nhưng lại mang lại lợi nhuận cao. Từ thực tế này, một độ đo mới được đề xuất: lợi ích (utility) nhằm tìm ra các mẫu có giá trị. Bài toán khai phá mẫu dãy lợi ích cao được đặt ra để tìm ra các mẫu dãy có giá trị. Trong khai phá mẫu dãy lợi ích cao, các mục trong CSDL đều được gán 1 giá trị số lượng và 1 giá trị trọng số thể hiện mức độ quan trọng của mục đó. Các mẫu dãy trên thực tế ngoài các giá trị lợi ích của các mục còn có giá trị khoảng cách thời gian giữa các thành phần trong dãy. Các mẫu dãy với các 3
khoảng cách thời gian lớn thường có ít ý nghĩa hơn là các mẫu dãy với khoảng cách thời gian nhỏ. Do vậy bài toán khai phá mẫu dãy lợi ích cao với khoảng cách thời gian được đặt ra, bài toán không chỉ quan tâm tới giá trị lợi ích của các mục mà còn quan tâm tới giá trị khoảng cách thời gian giữa các mẫu dãy. Mục tiê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, mẫu dãy lợi ích cao và mẫu dãy lợi ích cao với khoảng cách thời gian. 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 về bài toán khai phá mẫu dãy lợi ích cao và một số giải thuật Chương 3. Tìm hiểu bài toán khai phá mẫu dãy lợi ích cao với khoảng cách thời gian và một số giải thuật Chương 4. Kết luận 4
Chương 1.TỔNG QUAN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG 1.1. Giới thiệu Khai phá dữ liệu là một quá trình trích xuất thông tin từ dữ liệu được lưu trữ trong các CSDL. Từ đó giúp phân tích và đưa ra các quyết định. Khai phá dữ liệu bao gồm các tác vụ chính như: phân cụm (clustering), phân lớp (classification), khai phá luật kết hợp… Khai phá tập mục thường xuyên là bài toán con của khai phá luật kết hợp. Mục tiêu là tìm ra các mẫu dữ liệu thú vị, hữu ích trong CSDL. Khai phá tập mục thường xuyên được giới thiệu lần đầu tiên bởi Agrawal và Srikant [1]. Nhóm tác giả cũng đề xuất thuật toán Apriori để tìm các tập mục thường xuyên, tức là một nhóm các mục (biểu tượng) thường xuyên xuất hiện cùng nhau trong một CSDL giao dịch. Ví dụ: Thuật toán Apriori có thể dùng để tìm ra các mẫu như {nước ép cam, cà chua, nho} trong CSDL giao dịch tại một siêu thị. Mẫu này thể hiện rằng các sản phẩm “nước ép cam”, “cà chua” và “nho” thường được mua cùng nhau trong siêu thị đó. Các tập mục thường xuyên được tìm ra có thể được sử dụng trong việc phân tích dữ liệu và ra quyết định. Ví dụ như từ các tập mục thường xuyên có thể hiểu được hành vi khách hàng, từ đó xây dựng các chiến lược quảng bá sản phẩm dựa trên hành vi. Mặc dù khai phá tập mục thường xuyên đã trở nên rất phổ biến và có thể ứng dụng trong nhiều lĩnh vực. Tuy nhiên, các tập mục trong khai phá tập mục thường xuyên không quan tâm tới thứ tự của các mục. Trong một số lĩnh vực, thứ tự của các mục là rất quan trọng. Ví dụ như trong phân tích văn bản, thứ tự của các từ trong câu là rất quan trọng. Hay trong phát hiện hành vi xâm nhập mạng trái phép, thứ tự của các sự kiện cũng rất quan trọng. Để có thể giải quyết vấn đề thứ tự của các mục, bài toán khai phá mẫu dãy thường xuyên đã được đề xuất. Khai phá mẫu dãy thường xuyên (SPM) [2, 3, 5
4, 5] là một tác vụ khai phá dữ liệu để phân tích dữ liệu dãy và tìm ra các mẫu dãy thường xuyên. Cụ thể là tìm ra các mẫu dãy con có giá trị trong tập các dãy dữ liệu. Trong đó giá trị của mẫu dãy được đo bằng tần xuất xuất hiện của mẫu dãy đó trong CSDL. Khai phá mẫu dãy thường xuyên có nhiều ứng dụng trong thực tế dựa trên một sự thật là dữ liệu trong tự nhiên là một dãy có thứ tự của các mục, ví dụ như dữ liệu trong lĩnh vực tin sinh học, phân tích giỏ hàng, phân tích văn bản, phân tích chuỗi truy cập web… Bài toán khai phá mẫu dãy thường xuyên lần đầu tiên được Agrawal và cộng sự [2] đề xuất với mục tiêu là tìm ra các mẫu dãy con phổ biến trong tập hợp các dãy dữ liệu. Một dãy là một danh sách có thứ tự của các giá trị hữu danh. Ví dụ: dãy các từ trong văn bản, dãy thứ tự các sản phẩm được mua của khách hàng trong siêu thị hay dãy thứ tự các trang web truy cập bởi người dùng. Khai phá mẫu dãy thường xuyên là một lĩnh vực nghiên cứu rất sôi động với hàng trăm bài báo mới mỗi năm, cùng với rất nhiều mở rộng cho từng mục tiêu cụ thể. Chương này sẽ trình bày các vấn đề cơ bản của bài toán khai phá mẫu dãy thường xuyên và một số hướng tiếp cận giải quyết bài toán cũng như một số mở rộng của bài toán. 1.2. Một số khái niệm cơ bản Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Một tập mục X là một tập hợp các mục 𝑖𝑗 ∈ 𝐼 , do vậy X  I. Lực lượng của tập mục X được ký hiệu là |X| là số mục trong X. Tập mục X được gọi là có độ dài k hay còn gọi là k-tập mục nếu nó có k mục (nghĩa là |X|=k). Ví dụ có tập I = {a,b,c,d,e,f,g} là tập các sản phẩm bán trong một siêu thị thì tập {a, b, c} là một 3-tập mục thể hiện các mặt hàng được mua bởi một khách hàng trong một thời điểm nào đó. 6
Không giảm tổng quát, giả sử các mục trong một tập mục được sắp xếp theo thứ tự từ điển. Một dãy S là một danh sách được sắp xếp theo thứ tự của các tập mục dữ liệu S={X1, X2, …, Xn} với Xj  I là một tập mục được gọi là thành phần của dãy. Một mục dữ liệu chỉ xuất hiện 1 lần trong 1 thành phần Xj của dãy, nhưng có thể xuất hiện nhiều lần trong các thành phần của dãy S. Ví dụ giả sử có dãy là một dãy dữ liệu thể hiện 5 giao dịch của một khách hàng trong siêu thị. Mỗi chữ cái thể hiện một mục. Mỗi thành phần giữa hai dấu ngoặc đơn () thể hiện một tập mục, với các tập mục chỉ có 1 phần tử thì có thể bỏ qua dấu ngoặc này. Dãy này chỉ ra rằng một khách hàng đã mua sản phẩm a sau đó mua 3 sản phẩm (a, b, c) cùng nhau, sau đó lại mua 2 sản phẩm (a, c) cùng nhau, tiếp đến mua sản phẩm d và cuối cùng mua 2 sản phẩm (c, f) cùng nhau Kích thước |S| của một dãy là số lượng của các thành phần (tập mục) trong dãy S. Độ dài l(S) của dãy là tổng số mục dữ liệu trong dãy S. Ví dụ dãy có kích thước 5 và độ dài 9. Một cơ sở dữ liệu dãy SDB={S1,S2,…,Sm} là một tập các dãy với các định danh (SID) là 1, 2, ..m Ví dụ về một cơ sở dữ liệu dãy: SID Dãy dữ liệu 1 2 3 4 Bảng 1.1 Cơ sở dữ liệu dãy SDB 7
Cơ sở dữ liệu này có 4 dãy với SID lần lượt là 1, 2, 3 và 4. CSDL này có thể thể hiện danh sách các mặt hàng mua bởi 4 khách hàng. Định nghĩa 3.1. Dãy con Cho 2 dãy dữ liệu α=< a1 a2 … an > and β=< b1 b2 … bm >. α được gọi là Dãy con của β (α⊆ β), nếu tồn tại một dãy số nguyên 1≤ j1 < j2
- Nếu một mẫu dãy X là mẫu dãy thường xuyên thì mọi tập con Z (Z≠ ∅) của nó (Z⊆ 𝑋) cũng là mẫu dãy thường xuyên Tính chất này của mẫu dãy thường xuyên gọi là tính chất đóng xuống (hay còn gọi là tính chất Apriori hoặc tính phản đơn điệu). 1.3. Khai phá mẫu dãy thường xuyên Phần này trình bày các hướng tiếp cận của các thuật toán trong khai phá mẫu dãy thường xuyên và giới thiệu 2 thuật toán kinh điển: GSP [3] và PrefixSpan [6] làm cơ sở cho các thuật toán ở các chương sau. Nhiệm vụ của khai phá mẫu dãy thường xuyên là tìm tập hợp tất cả các mẫu dãy thường xuyên trong CSDL dãy. Bài toán khai phá mẫu dãy thường xuyên là một bài toán liệt kê. Trọng tâm là liệt kê tất cả các mẫu dãy có độ hỗ trợ lớn hơn hoặc bằng với ngưỡng hỗ trợ tối thiểu đặt bởi người dùng. Tìm mẫu dãy thường xuyên là một bài toán khó. Để giải quyết nó, phương pháp tiếp cận tự nhiên nhất là tính độ hỗ trợ của tất cả các mẫu dãy con có thể có trong CSDL và liệt kê tất cả các mẫu dãy có độ hỗ trợ không nhỏ hơn ngưỡng tối thiểu. Tuy nhiên, cách tiếp cận ngây thơ như vậy không hiệu quả vì số lượng các mẫu dãy con có thể rất lớn. Một dãy chứa q mục trong CSDL có thể có tới 2q - 1 mẫu dãy con khác nhau. Vì vậy, việc áp dụng phương pháp tiếp cận ngây thơ như vậy thường không hiệu quả, do đó không thể áp dụng trong thực tế. Đã có rất nhiều thuật toán được thiết kế để giải quyết bài toán khai phá mẫu dãy thường xuyên. Một số thuật toán nổi tiếng có thể kể tới là GSP [3], PrefixSpan [6], Spade [5], Spam [4], bitSpade [7], Prims [8], FreeSpan [9]. Các thuật toán này có đầu vào là một cơ sở dữ liệu dãy và một ngưỡng hỗ trợ tối thiểu (được đặt bởi người dùng) và đầu ra là tập tất cả các mẫu dãy thường xuyên. Không gian tìm kiếm của tất cả mẫu dãy con có thể sinh ra trong một 9
cơ sở dữ liệu dãy có thể rất lớn, vì vậy các thuật toán cần phải sử dụng các kỹ thuật để tránh quét toàn bộ không gian tìm kiếm. Cơ chế cơ bản nhất để tỉa không gian tìm kiếm trong khai phá mẫu dãy thường xuyên là sử dụng tính chất đóng xuống. Tính chất này chỉ ra rằng với bất kỳ dãy sa và sb nào, nếu sa là dãy con của sb thì sb phải có độ hỗ trợ nhỏ hơn hoặc bằng với sa. Tính chất này rất hiệu quả để tỉa bớt không gian tìm kiếm, vì nếu một mẫu dãy không phải là mẫu dãy thường xuyên thì tất cả các mẫu dãy cha của nó đều sẽ có độ hỗ trợ nhỏ hơn ngưỡng tối thiểu nghĩa là không phải là mẫu dãy thường xuyên. Ví dụ, với cơ sở dữ liệu tại Bảng 1.1 và ngưỡng tối thiểu minsup =2, ta có dãy có độ hỗ trợ là 1 là một mẫu dãy không thường xuyên. Tất cả các dãy cha của nó ví dụ như đều không phải là mẫu dãy thường xuyên. Tính chất đóng xuống do đó có thể làm giảm đáng kể không gian tìm kiếm của các mẫu dãy. 1.3.1. Thuật toán GSP: Mỗi thuật toán sử dụng các chiến lược và cấu trúc dữ liệu khác nhau để tối ưu các bước xử lý. Thuật toán đầu tiên được đề xuất là AprioriAll [2]. Nhóm tác giả sau đó phát triển phiên bản tối ưu hơn gọi là GSP [3]. Hai thuật toán này được lấy cảm hứng từ thuật toán Apriori [1] khai phá mẫu dãy thường xuyên. Sau đây là giả thuật của thuật toán GSP: Input: Một CSDL dãy SDB, ngưỡng hỗ trợ tối thiểu minsup Output: Tập các mẫu dãy thường xuyên Start 1. Gọi L1 là tập các mẫu dãy thường xuyên 1 phần tử 2. Gọi L là tập tất cả các mẫu dãy thường xuyên: 𝐿 = ⋃ 𝐿𝑘 𝑘 10
3. Khởi tạo L = ∅; 𝐿1 = ∅ 4. Quét SDB lần 1 để tính độ hỗ trợ của tất cả các mẫu dãy a trong SDB. 5. If (support(a) ≥ minsup) then 𝐿1 = 𝐿1 ∪ 𝑎 End if; 6. for (k=2, Lk-1 ≠ NULL, k++) Gọi Ck là tập các mẫu dãy độ dài k, khởi tạo 𝐶𝑘 = ∅; Sinh các mẫu dãy độ dài k, nạp vào Ck; Quét SDB để tính support của các mẫu dãy α trong Ck.; If (support(a) ≥ minsup) then 𝐿𝑘 = 𝐿𝑘 ∪ 𝛼; End if; 𝐿 = 𝐿 ∪ 𝐿𝑘 ; End for; 7. Return L; End. GSP áp dụng phương thức biểu diễn cơ sở dữ liệu tiêu chuẩn theo chiều ngang (giống như Bảng 1.1). Thuật toán GSP đầu tiên quét cơ sở dữ liệu để tìm tất cả các mẫu dãy thường xuyên độ dài 1 và độ hỗ trợ của chúng. Ví dụ, với cơ sở dữ liệu trong Bảng 1.1 và ngưỡng hỗ trợ minsup =2. Các mẫu dãy thường xuyên độ dài 1 là , , , , , . Sau đó GSP sử dụng các mẫu dãy độ dài k để sinh ra tất cả các mẫu dãy độ dài k+1. Mẫu dãy độ dài k+1 được sinh ra bằng cách ghép các mẫu dãy độ dài k. Trở lại ví dụ trên, các mẫu dãy độ dài 2 được sinh ra là , , , 11
, , , , , , …, , , …. Sau khi sinh ra các ứng viên, GSP sẽ xác định xem một mẫu dãy ứng viên có phải là mẫu dãy thường xuyên không (có độ hỗ trợ không nhỏ hơn minsup). Việc này được thực hiện bằng 2 bước. Đầu tiên, với một mẫu dãy ứng viên sa độ dài k, GSP sẽ kiểm tra tất cả cá mẫu dãy con độ dài k-1 của nó. Nếu có một mẫu dãy con không phải là mẫu dãy thường xuyên thì sa không phải là mẫu dãy thường xuyên. Nếu không thì GSP sẽ quét CSDL để tính độ hỗ trợ của sa. GSP bắt đầu với các mẫu dãy độ dài 1, sau đó sinh ra các mẫu dãy ứng viên độ dài 2, 3, 4 và hơn nữa cho tới khi không có mẫu dãy nào có thể được sinh ra. Các bước sinh mẫu dãy ứng viên của thuật toán GSP được thể hiện trong Hình 1.1. Các bước sinh mẫu dãy của thuật toán GSPHình 1.1. . Level 4 Level 3 . Level 2 . . Level 1 Mẫu dãy không thường xuyên Mẫu dãy không tồn tại Hình 1.1. Các bước sinh mẫu dãy của thuật toán GSP 12
Thuật toán GSP có một số hạn chế sau: - Quét CSDL nhiều lần: Một trong những vấn đề chính của GSP là phải quét CSDL nhiều lần để tính độ hỗ trợ của ứng viên. Việc này rất tốn kém về mặt tài nguyên nếu CSDL lớn. - Sinh ra các ứng viên không tồn tại: Một vấn đề khác là GSP có thể sinh ra rất nhiều ứng viên không có trong CSDL. Nguyên nhân là do GSP sinh ứng viên bằng cách ghép các mẫu dãy nhỏ hơn mà không tìm trong CSDL. Ví dụ, mẫu dãy không có trong CSDL Bảng 1.1 nhưng vẫn được GSP sinh ra và xem xét. - Duy trì các ứng viên trong bộ nhớ: Một vấn đề nghiêm trọng nữa của GPS là vấn đề điển hình của các thuật toán tìm kiếm theo chiều rộng. Trong mọi thời điểm, cần phải lưu tất cả các mẫu dãy độ dài k trong bộ nhớ để có thể sinh ra các mẫu dãy độ dài k+1. Việc này sẽ tốn rất nhiều bộ nhớ. 1.3.2. Thuật toán PrefixSpan: Để giải quyết các vấn đề trên, một số thuật toán được phát triển theo phương pháp tăng trưởng mẫu dãy sử dụng tìm kiếm theo chiều sâu. Phương pháp tăng trưởng mẫu dãy tránh được việc sinh ra và kiểm tra các mẫu dãy không tồn tại bằng cách quét đệ quy CSDL để sinh ứng viên. Thuật toán phổ biến nhất sử dụng phương pháp tăng trưởng mẫu dãy là PrefixSpan [6], được phát triển dựa trên thuật toán FPGrowth khai phá mẫu dãy thường xuyên. a) Một số định nghĩa: Định nghĩa 3.4. Tiền tố: Giả sử các mục dữ liệu trong các tập mục thuộc dãy được sắp xếp theo thứ tự chữ cái. Cho một dãy  = < e1e2 …en>, một dãy = (m≤n) được gọi là tiền tố của  nếu và chỉ nếu: 13