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

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].

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.

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.

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.

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.

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.

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.

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.

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.

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) đó.

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.

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.