Khai Phá Mẫu Dãy Có Trọng Số Trong Cơ Sở Dữ Liệu Dãy

Chuyên khảo phân tích Khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Tác giả: Trần Huy Dương
• Người hướng dẫn: TS. Nguyễn Trường Thắng
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Khai Phá Mẫu Dãy Có Trọng Số Trong Cơ Sở Dữ Liệu Dãy
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng Quan Về Khai Phá Mẫu Dãy Có Trọng Số Giới Thiệu

Khai phá dữ liệu, một lĩnh vực then chốt, tập trung vào việc trích xuất thông tin giá trị từ lượng lớn dữ liệu. Trong đó, khai phá mẫu dãy là một nhánh quan trọng. Bài toán này, được giới thiệu bởi Agrawal và Srikant, hướng đến việc tìm ra các mẫu tuần tự (sequences) xuất hiện thường xuyên trong cơ sở dữ liệu dãy. Ví dụ, một mẫu tuần tự '{Máy in; Giấy}' cho thấy sự liên kết trong hành vi mua sắm. Các mẫu tuần tự hữu ích trong việc ra quyết định. Lĩnh vực này đã thu hút nhiều nhà nghiên cứu, dẫn đến sự phát triển của các kỹ thuật và mở rộng bài toán. Tuy nhiên, việc bỏ qua thứ tự các mục có thể dẫn đến việc bỏ lỡ các mẫu tuần tự quan trọng.

1.1. Lịch sử phát triển của khai phá mẫu dãy tuần tự

Từ khi ra đời, khai phá mẫu dãy đã thu hút sự quan tâm lớn. Nhiều công trình nghiên cứu liên tục được công bố để phát triển các kỹ thuật khai phá dữ liệu dãy cũng như mở rộng bài toán. Khai phá các mẫu dãy tiềm năng và hữu ích trong các cơ sở dữ liệu dãy là một trong những nội dung quan trọng trong khai phá dữ liệu cơ bản. Những năm gần đây, các xu hướng nghiên cứu các vấn đề khai phá dữ liệu là đề xuất các thuật toán khai phá mẫu dãy trong các loại CSDL dữ liệu dãy. Agrawal và Srikant đã đề xuất trong [2].

1.2. Ứng dụng thực tiễn của khai phá mẫu dãy

Khai phá mẫu dãy có rất nhiều ứng dụng khai phá mẫu dãy trong thực tiễn hiện nay vì dữ liệu thu thập được cơ bản đã được mã hóa thành các dãy dữ liệu trong nhiều lĩnh vực như tin sinh học, đào tạo trực tuyến, phân tích thị trường, phân tích mua bán, phân tích văn bản và phân tích thông tin nhấp chuột trên trang web. Mối quan tâm đến các kỹ thuật khai phá mẫu dãy đến từ khả năng phát hiện ra các mẫu dãy có thể ẩn bên trong cơ sở dữ liệu dãy lớn và con người có thể giải thích được và rất hữu ích cho việc hiểu dữ liệu và ra các quyết định phù hợp.

II. Vấn Đề Hạn Chế Khi Khai Phá Mẫu Dãy Không Trọng Số

Các kỹ thuật khai phá mẫu dãy truyền thống, như khai thác tập mục phổ biến thường xuyên, thường bỏ qua thứ tự tuần tự của các sự kiện. Điều này dẫn đến việc không thể khai phá ra các mẫu dãy quan trọng hoặc tìm kiếm các mẫu tuần tự không hữu ích. Trong nhiều lĩnh vực, thứ tự của các sự kiện là yếu tố quyết định. Ví dụ, trong phân tích văn bản, cần phải xem xét thứ tự của các từ trong câu. Trong phát hiện xâm nhập mạng, thứ tự của các sự kiện xảy ra rất quan trọng. Do đó, khai phá mẫu dãy có trọng số ra đời.

2.1. Tầm quan trọng của thứ tự các sự kiện trong khai phá dữ liệu

Trong nhiều lĩnh vực, thứ tự của các sự kiện là đặc biệt quan trọng. Ví dụ, để phân tích các văn bản, cần phải xem xét thứ tự của các từ trong câu [8]. Trong phát hiện xâm nhập mạng, thứ tự của các sự kiện xảy ra rất quan trọng [9]. Một số phương pháp chính phân tích và khai phá dữ liệu dãy mẫu tuần tự [2], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23] trong các phương pháp này bao gồm việc khám phá các dãy con tiềm năng và có ý nghĩa trong một tập hợp các dãy, trong đó mức độ tiềm năng của một dãy con có thể được đo lường theo các tiêu chí khác nhau như tần suất xuất hiện, độ dài và lợi nhuận của dãy, khoảng cách thời gian.

2.2. Khai phá mẫu dãy có khoảng cách thời gian

Trong thực tế, khoảng cách thời gian giữa các thành phần trong dãy cũng đóng vai trò rất quan trọng. Dãy <ab,b> với khoảng cách thời gian là 1 ngày sẽ có ý nghĩa hơn rất nhiều dãy <ab,b> mà có khoảng cách là 1 năm. Cũng với ví dụ trên, một dãy dữ liệu <(0,ab), (1,b), (30,bc)> tương đương với tình huống khách hàng mua mặt hàng a và b, sau đó 1 ngày khách hàng mua mặt hàng b, và sau 30 ngày tiếp theo khách hàng mua mặt hàng b và c. Khi đó thông tin mở rộng của khai phá dãy có khoảng cách thời gian có ý nghĩa cho phép người quản lý bán hàng phân tích xem sau khoảng thời gian bao lâu, khách hàng sẽ mua các mặt hàng tiếp theo.

III. Cách Giải Thuật Toán Khai Phá Top K Mẫu Dãy Trọng Số

Để giải quyết vấn đề, các thuật toán khai phá mẫu dãy có trọng số ra đời. Trong đó, việc phát hiện top-k mẫu dãy thường xuyên được thực hiện bằng các thuật toán như TKS do Fournier-Viger và cộng sự đề xuất, sử dụng biểu diễn CSDL theo chiều dọc. Dương và cộng sự cũng đã đề xuất 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, cụ thể là thuật toán WIPrefixSpan. Các giải thuật này, kết hợp với phản hồi của người dùng, cho phép điều chỉnh số lượng mẫu dãy khai phá được.

3.1. Giới thiệu thuật toán TKS trong khai phá mẫu dãy

Việc phát hiện top-k mẫu dãy thường xuyên trên CSDL dãy được thực hiện bằng việc nghiên cứu giải quyết của thuật toán TKS [21] do Fournier-Viger và cộng sự đề xuất thực hiện khai phá top-k mẫu dãy thường xuyên trong CSDL dãy sử dụng biểu diễn CSDL theo chiều dọc.

3.2. Thuật toán WIPrefixSpan để khai phá mẫu dãy có trọng số

Dương và cộng sự [40] đã đề xuất 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 trong CSDL dãy có khoảng cách thời gian và thuật toán WIPrefixSpan để khai phá mẫu dãy này.

IV. Phương Pháp Mới Khai Phá Mẫu Dãy Lợi Ích Cao Khoảng Thời Gian

Khai phá mẫu dãy lợi ích cao là một mở rộng của bài toán khai phá mẫu dãy có trọng số. Trong đó, các mục có thể có các giá trị khác nhau trong các lần xuất hiện khác nhau. Các nghiên cứu như UL, US, Uspan, PHUS, HuspExt, HUS-Span, HUSPM đã được công bố. Tuy nhiên, vẫn còn thiếu các nghiên cứu về khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Luận án này đề xuất phát triển các thuật toán để khai phá loại mẫu tuần tự này, nhằm đáp ứng nhu cầu thực tế.

4.1. Điểm khác biệt của khai phá mẫu dãy lợi ích cao

Trong khai phá mẫu dãy lợi ích cao, các mục có thể có các giá trị khác nhau trong các lần xuất hiện khác nhau. Ví dụ, xét một dãy dữ liệu như sau <a[3] ><a[2] b[6] d[2]>, mẫu dãy a nhận 2 giá trị khác nhau (lần lượt là 3 và 2) trong 2 lần xuất hiện thể hiện mục a được mua với số lượng 3 và 2 trong 2 lần giao dịch liên tiếp. CSDL dãy có chứa các giá trị số lượng như vậy được gọi là CSDL dãy định lượng.

4.2. Các thuật toán khai phá mẫu dãy lợi ích cao hiện có

Một số công bố tiêu biểu như UL, US [42], Uspan [43], PHUS [44], HuspExt [45], HUS-Span [46], HUSPM [47] . Tuy nhiên, đến nay chưa có nhiều các nghiên cứu về khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi mục trong dãy dữ liệu, giá trị định lượng của các mục xuất hiện và khoảng cách thời gian giữa các dãy trong CSDL dãy định lượng có khoảng cách thời gian.

V. Ứng Dụng Phân Tích Hành Vi Khách Hàng Chi Tiết Hơn

Khai phá mẫu dãy có trọng số và lợi ích cao có nhiều ứng dụng, đặc biệt trong phân tích hành vi khách hàng. Ví dụ, trong bài toán mua sắm, thông tin về khoảng cách thời gian mua hàng và giá trị của các mặt hàng giúp nhà quản lý bán hàng hiểu rõ hơn về xu hướng tiêu dùng. Việc đưa trọng số vào các mục, ví dụ như máy in (giá trị cao) so với giấy in (giá trị thấp), cho phép cân bằng độ hỗ trợ và mức độ quan trọng của các mặt hàng. Từ đó, doanh nghiệp có thể đưa ra các quyết định chiến lược hiệu quả hơn.

5.1. Ví dụ thực tế về phân tích hành vi mua sắm

Một dãy dữ liệu <ab,b,bc> tương đương với tình huống khi khách hàng mua mặt hàng b sau khi đã mua mặt hàng a và b, sau đó họ mua tiếp mặt hàng b,c sau khi mua mặt hàng b. Tuy nhiên, người quản lý bán hàng không biết được thời gian mà khách hàng đã mua các sản phẩm trên nếu chỉ thực hiện khai phá mẫu dãy thường xuyên mà không có thêm các thông tin mở rộng khác.

5.2. Cân bằng độ hỗ trợ và mức độ quan trọng của mặt hàng

Với một dãy dữ liệu có thông tin khoảng cách thời gian <(0,ab), (1,b), (30,bc)>, việc người sử dụng đưa thêm các giá trị trọng số của từng mục a, b, c khác nhau phản ánh mức độ quan trọng của mục dữ liệu trong dãy đó, bởi vì nếu mục a là mặt hàng máy in (có giá trị cao, thông thường có số lượng mua ít) và mục b là mặt hàng giấy in (có giá trị ít hơn, thông thường có số lượng mua nhiều) và mục c là mặt hàng hộp mực in (có giá trị trung bình, có số lượng mua trung bình) thì việc đưa trọng số của a (máy in) cao hơn trọng số của c (hộp mực in) và trọng số của b (giấy in) cho phép người sử dụng cân bằng được độ hỗ trợ (tần suất mua) và trọng số (mức độ quan trọng) của các mục (mặt hàng) đó.

VI. Kết Luận Hướng Nghiên Cứu Mở Rộng và Triển Vọng Tương Lai

Luận án này tập trung vào việc giải quyết các vấn đề về khai phá mẫu dãy có trọng số, có tính đến cả khoảng cách thời gian và giá trị định lượng của các mục. Các mục tiêu chính bao gồm phát hiện các mẫu dãy trọng số trong CSDL dãy có khoảng cách thời gian và trong CSDL dãy định lượng có khoảng cách thời gian. Nghiên cứu này không chỉ phát triển lý thuyết mà còn mang lại nhiều ứng dụng thực tế. Các thuật toán mới được đề xuất, chứng minh tính đúng đắn và phân tích độ phức tạp tính toán, hứa hẹn sẽ mở ra nhiều hướng nghiên cứu mới trong lĩnh vực này.

6.1. Mục tiêu chính của luận án

Mục tiêu của luận án là đề xuất giải pháp khai phá các mẫu dãy có trọng số có khoảng cách thời gian giữa các dãy trong các CSDL dãy có khoảng cách thời gian và CSDL dãy định lượng có khoảng cách thời gian. Cụ thể luận án tập trung đề xuất các giải pháp nhằm: Phát hiện các mẫu dãy có trọng số trong các CSDL dãy khoảng cách thời gian. Các mẫu dãy tìm được khi đó được gọi là mẫu dãy thường xuyên trọng số với khoảng cách thời gian.

6.2. Đóng góp và ý nghĩa của nghiên cứu

NCS tập trung vào nghiên cứu đề xuất các thuật toán mới để khai phá các mẫu dãy thường xuyên; chứng minh tính đúng đắn và tính đầy đủ, phân tích độ phức tạp tính toán của các thuật toán; thử nghiệm và phân tích ý nghĩa của mẫu dãy thường xuyên khai phá được.

Trích đoạn nội dung tài liệu

đặt vấn đề và đề xuất thuật toán khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Tính đúng đắn và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên các bộ dữ liệu thực và so sánh với các nghiên cứu trước đó.  Phần kết luận: Trình bày một số kết luận những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của NCS. TỔNG QUAN KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY Chương này trình bày tổng quan tình hình nghiên cứu và những định nghĩa cơ bản những vấn đề khai phá các mẫu dãy có trọng số trong các CSDL dãy, mẫu dãy có trọng số trong CSDL dãy có khoảng cách thời gian, mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian.

Chương này cũng chỉ ra các khoảng trống chưa được giải quyết để từ đó xác định vấn đề nghiên cứu của luận án. Tổng quan tình hình nghiên cứu Khai phá mẫu dãy là nhiệm vụ thực hiện tìm kiếm tất cả các mẫu dãy con thường xuyên trong cơ sở dữ liệu dãy. Một dãy s được cho là một mẫu dãy thường xuyên nếu và chỉ khi độ hỗ trợ sup (s) ≥ minsup, vì ngưỡng minsup do người dùng đặt [10]. Nhiệm vụ khai phá mẫu dãy là một bài toán liệt kê nhằm mục đích liệt kê tất cả các mẫu dãy con có độ hỗ trợ không thấp hơn ngưỡng hỗ trợ tối thiểu do người dùng đặt ra.

Do đó, luôn có một kết quả đúng duy nhất cho một bài toán khai phá mẫu dãy thường xuyên. Để thực hiện khai phá các mẫu dãy thường xuyên, cách tiếp cận đơn giản là tính toán hỗ trợ của tất cả các mẫu dãy con có thể có trong cơ sở dữ liệu dãy để sau đó chỉ đưa ra những mẫu dãy đáp ứng ràng buộc hỗ trợ tối thiểu do người dùng đặt ra. Tuy nhiên, với cách tiếp cận như vậy sẽ ít hiệu quả vì thông thường số lượng dãy con tìm được có thể rất lớn. Ví dụ như một dãy chứa q mục dữ liệu trong một CSDL dãy có thể có tối đa 2q-1 các mẫu dãy con riêng biệt.

Do đó, để giải quyết vấn đề khai phá các mẫu dãy con đối với hầu hết các cơ sở dữ liệu dãy có trong thực tế là phức tạp và khó khăn. Vì vậy, các nghiên cứu và phát triển các thuật toán hiệu quả khai phá mẫu dãy cần hạn chế phải khai phá không gian tìm kiếm của tất cả các dãy con có thể có trong CSDL dãy. Hiện nay có nhiều thuật toán đã được đề xuất để khai phá các mẫu dãy trong cơ sở dữ liệu dãy. Một số thuật toán phổ biến nhất là GSP [10], Spade [11], PrefixSpan [31], Spam [30], Lapin [18], CM-Spam và CM-Spade [17].

Tất cả các thuật toán khai thác mẫu dãy này lấy đầu vào là cơ sở dữ liệu dãy và ngưỡng hỗ trợ tối thiểu (do người dùng chọn) và trả kết quả là tập hợp các mẫu dãy thường xuyên và luôn chỉ có một 16 kết quả đúng cho nhiệm vụ khai phá mẫu dãy (đối với cơ sở dữ liệu dãy và giá trị ngưỡng). Do đó, tất cả các thuật toán khai phá mẫu dãy luôn trả về cùng một kết quả là tập hợp các mẫu dãy nếu chúng được chạy với cùng một tham số trên cùng một cơ sở dữ liệu. Sự khác biệt giữa các thuật toán khác nhau không phải là đầu ra của chúng, mà là cách mỗi thuật toán thực hiện khai phá ra các mẫu dãy. Các thuật toán khác nhau sử dụng các chiến lược và cấu trúc dữ liệu khác nhau để tìm kiếm và khai phá các mẫu dãy một cách hiệu quả, một số thuật toán hiệu quả hơn những thuật toán khác trong cùng mục đích khai phá mẫu dãy.

Hiện nay, các thuật toán khai phá mẫu dãy có thể được phân thành 02 loại là thuật toán tìm kiếm theo chiều sâu hoặc thuật toán tìm kiếm theo chiều rộng. AprioriAll là thuật toán khai phá mẫu dãy đầu tiên được đề xuất [2]. Các tác giả của AprioriAll sau đó đã đề xuất một phiên bản cải tiến được gọi là GSP [10]. Các thuật toán AprioriAll và GSP được đề xuất theo phương pháp của thuật toán Apriori nhằm khai phá tập mục thường xuyên [1].

Đối với các thuật toán tìm kiếm theo chiều rộng như GSP tiến hành như sau. Đầu tiên duyệt cơ sở dữ liệu để tìm mẫu dãy thường xuyên có độ dài 1 (các mẫu dãy chứa một mục). Sau đó, sẽ thực hiện sinh ra mẫu dãy có độ dài 2 bằng cách thực hiện phần ghép cặp của các mẫu dãy độ dài 1. Sau đó mẫu dãy có độ dài 3 tiếp tục được tạo ra từ việc ghép cặp các mẫu dãy có độ dài 2.

cho đến khi không còn mẫu dãy nào có thể được tạo ra nữa. Có thể thấy rằng với phương pháp tìm kiếm theo chiều rộng này thì không gian tìm kiếm có thể rất lớn. Giả sử rằng dãy dài nhất trong cơ sở dữ liệu chứa m mục thì các thuật toán khai phá mẫu dãy thực hiện tìm kiếm theo chiều rộng trong trường hợp xấu nhất là tất cả các mẫu dãy có thể chứa m mục hoặc ít hơn. Nếu một cơ sở dữ liệu dãy chứa m mục, thì các mẫu dãy phải khai phá có thể thể lớn hơn 2m.

Trong những năm gần đây, nhiều thuật toán đã được chứng minh là hiệu quả hơn GSP do GSP thực hiện nhiều lần duyệt cơ sở dữ liệu để tính toán sự hỗ trợ của các mẫu dãy ứng viên. Điều này có thể rất tốn kém tài nguyên đối với các cơ sở dữ liệu lớn, ngay cả khi một số tối ưu hóa có thể được thực hiện để giảm chi phí đó (ví dụ: bằng cách sắp xếp các dãy theo kích thước của chúng để tránh so sánh các mẫu dài với các dãy ngắn). Mặt khác GSP có thể tạo ra các mẫu không tồn tại trong cơ sở 17 dữ liệu do việc tạo ra các ứng viên bằng cách kết hợp các mẫu nhỏ hơn mà không cần truy cập cơ sở dữ liệu. GSP có thể tốn nhiều thời gian kiểm tra nhiều mẫu không tồn tại trong cơ sở dữ liệu.

Một vấn đề khác của thuật toán GSP là phải sử dụng bộ nhớ lớn vì tại bất kỳ thời điểm nào thuật toán cũng phải giữ tất cả các mẫu dãy thường xuyên có độ dài k trong bộ nhớ để có thể tạo ra các mẫu dãy có độ dài k + 1. Các thuật toán tìm kiếm theo chiều sâu như Spade [11], PrefixSpan [31], Spam [30], Lapin [18], CM-Spam và CM-Spade [17] thực hiện khai phá không gian tìm kiếm của các mẫu dãy bằng các cách khác nhau. Bắt đầu từ các mẫu dãy chứa các mục đơn lẻ, sau đó thực hiện đệ quy đối với các mở rộng của các mẫu dãy này để tạo ra các mẫu dãy lớn hơn. Sau đó, khi một mẫu dãy không thể được mở rộng nữa, thuật toán sẽ quay trở lại để tạo các mẫu dãy khác.

Thuật toán Spade [11] là một thuật toán sử dụng phương pháp tìm kiếm theo chiều sâu và tránh một số nhược điểm của thuật toán GSP. Thuật toán Spade được thực hiện theo phương pháp từ thuật toán Eclat [4] để khai phá tập mục thường xuyên. Spade sử dụng biểu diễn cơ sở dữ liệu dọc thay thế biểu diễn cơ sở dữ liệu ngang ban đầu. Biểu diễn theo chiều dọc của cơ sở dữ liệu dãy cho biết các tập hợp mục mà mỗi mục i xuất hiện trong cơ sở dữ liệu dãy.

Đối với một mặt hàng nhất định, thông tin này được gọi là IDList của mặt hàng đó. Bằng cách sử dụng biểu diễn CSDL dọc, các thuật toán như Spade [11], Spam [30], CM-Spam và CMSpade [17] khai phá toàn bộ không gian tìm kiếm của các mẫu dãy bằng cách đọc cơ sở dữ liệu chỉ một lần để tạo IDLists duy nhất mặt hàng. Sau đó, các IDLists của bất kỳ mẫu dãy nào gặp phải khi duyệt không gian tìm kiếm thu được bằng cách thực hiện phép nối các IDLists, cho phép tính toán hỗ trợ của mẫu dãy. Vì vậy tất cả các mẫu dãy thường xuyên có thể được liệt kê mà không cần duyệt liên tục cơ sở dữ liệu và không cần duy trì một số lượng lớn các mẫu dãy trong bộ nhớ (trái ngược với các thuật toán tìm kiếm theo chiều rộng).

Cách tiếp cận này được xem là một trong những cách hiệu quả để khai thác mẫu dãy hơn so với các thuật toán theo tiếp cận tìm kiếm theo chiều rộng. Bên cạnh thuật toán tìm kiếm theo chiều rộng và thuật toán khai thác theo chiều sâu sử dụng CSDL dọc, một phương pháp quan trọng khác để khai phá mẫu dãy là các thuật toán tăng trưởng mẫu dãy. Các thuật toán tăng trưởng mẫu dãy thực hiện tìm 18 kiếm theo chiều sâu, được thiết kế để giải quyết một hạn chế của các thuật toán được mô tả trước đó vì có thể tạo ra các mẫu ứng cử viên không tồn tại trong cơ sở dữ liệu ban đầu. Lý do là các thuật toán theo phương pháp tìm kiếm theo chiều rộng và thuật toán khai thác theo chiều sâu sử dụng CSDL dọc có thể tạo ra các mẫu dãy không xuất hiện trong cơ sở dữ liệu vì việc thực hiện tạo ra các mẫu dãy ứng viên bằng cách kết hợp các mẫu dãy nhỏ hơn nhưng quá trình này không liên quan đến việc truy cập cơ sở dữ liệu.

Các thuật toán theo phương pháp tăng trưởng mẫu dãy bằng cách duyệt đệ quy cơ sở dữ liệu để tìm các mẫu dãy lớn hơn, vì vậy chỉ thực hiện khai phá các mẫu dãy thực sự tồn tại trong cơ sở dữ liệu. Tuy nhiên, việc thực hiện duyệt cơ sở dữ liệu nhiều lần có thể gây tốn kém tài nguyên. Để giảm chi phí duyệt cơ sở dữ liệu, thuật toán tăng trưởng mẫu dãy có đưa ra khái niệm cơ sở dữ liệu chiếu theo tiền tố nhằm mục đích giảm kích thước của cơ sở dữ liệu vì các mẫu lớn hơn được tìm kiếm theo chiều sâu. Thuật toán khai phá mẫu dãy tăng trưởng đầu tiên được đề xuất là FreeSpan [13], sau đó cùng một nhóm nghiên cứu đề xuất thuật toán PrefixSpan [31] theo phương pháp của thuật toán FPGrowth cho khai thác tập mục thường xuyên.

PrefixSpan thực hiện khai phá không gian tìm kiếm của các mẫu dãy bằng cách sử dụng phương pháp tìm kiếm theo chiều sâu. Bắt đầu từ các mẫu dãy chứa một mục và khai phá các mẫu dãy lớn hơn bằng cách nối đệ quy các mục vào các mẫu dãy này để tạo ra các mẫu dãy lớn hơn.