Đặt vấn đề Bài toán khai thác tập phổ biến (FIM) được Agrawal và đồng sự đề xuất vào năm 1993 [1] nhằm phân tích hành vi khách hàng, phân tích giỏ hàng trong các cửa hàng bán lẻ, các sàn giao dịch thương mại điện tử, v.v… Mỗi khi khách hàng mua sắm tại cửa hàng và thanh toán tại quầy thu ngân, một giao dịch giữa khách hàng và cửa hàng sẽ được phát sinh. Các giao dịch này thường được quản lý bên trong một CSDL giao dịch. Qua thời gian, lượng giao dịch tích lũy trong CSDL sẽ ngày càng lớn. Mục tiêu của bài toán FIM là thực hiện phân tích các giao dịch giữa khách hàng và cửa hàng bán lẻ trong CSDL để có thể tìm ra các tri thức ẩn chứa bên trong nguồn dữ liệu này.
Cụ thể, FIM có thể xác định được những mặt hàng hoặc những kết hợp giữa các mặt hàng nào thường hay được người dùng chọn mua. Các kết hợp này nếu có tần suất xuất hiện thỏa mãn một ngưỡng tối thiểu cho trước, thì được gọi là “phổ biến”. Ngưỡng tối thiểu cho trước này được gọi là ngưỡng độ hỗ trợ tối thiểu, và thường được ký hiệu là 𝑚𝑖𝑛𝑠𝑢𝑝 hoặc 𝜎. Để không làm mất tính tổng quát của bài toán, các mặt hàng được thống nhất sử dụng thông qua thuật ngữu hạng mục và kết hợp giữa các mặt hàng là tập mục.
Kết quả thu được từ bài toán FIM được sử dụng để sinh ra tập các luật kết hợp, giúp cho nhà quản lý có thể nắm được các quy luật kết hợp nào giữa các hạng mục hoặc tập mục có độ tin cậy cao để thúc đẩy việc kinh doanh hiệu quả hơn [1]. Kể từ khi được đề xuất vào năm 1993 [1], FIM dần thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu về khai thác dữ liệu nói chung và khai thác mẫu nói riêng. Bài toán này nhận hai tham số đầu vào. Tham số đầu vào thứ nhất của bài toán là một CSDL giao dịch như đã nêu, tham số đầu vào thứ hai là ngưỡng 𝑚𝑖𝑛𝑠𝑢𝑝.
Kết quả nhận được của bài toán FIM là tập đầy đủ các tập mục có tần suất xuất hiện không bé hơn ngưỡng 𝑚𝑖𝑛𝑠𝑢𝑝 đã cho, và được gọi là các tập mục phổ biến. Nhiều tiếp cận, 1 mô hình, giải thuật đã được đề xuất nhằm hướng đến việc giải quyết hiệu quả bài toán này [2–12]. Nhược điểm lớn nhất của bài toán FIM là chỉ quan tâm đến tần suất xuất hiện của các hạng mục và tập mục trong CSDL đang xét. Các hạng mục này được FIM xem như có tầm quan trọng như nhau.
Đối với bài toán FIM, tại mỗi giao dịch, các hạng mục chỉ có thể thuộc một trong hai trạng thái đó là tồn tại hoặc không tồn tại trong giao dịch đó. Do đó, các thông tin hữu ích khác trong CSDL giao dịch không được xem xét. Trong thực tế, các thông tin này cũng mang lại nhiều tri thức quan trọng và hữu ích cho quá trình khai thác dữ liệu. Một loại thông tin không kém phần quan trọng đối với quá trình khai thác dữ liệu từ CSDL giao dịch, đó là mức độ quan trọng của các hạng mục trong mỗi giao dịch.
Xét ví dụ, với một giao dịch được phát sinh khi khách hàng tiến hành mua sắm tại một cửa hàng bán lẻ, giao dịch này thường chứa các thông tin như số lượng mỗi mặt hàng đã được chọn mua, đơn giá, mức thuế tương ứng của chúng, v.v… Các tiếp cận đã đề xuất trong bài toán khai thác tập phổ biến đều bỏ qua các thông tin này. Kết quả là các giải thuật FIM thường tạo ra các tập mục có tần suất xuất hiện lớn (mức độ phổ biến cao). Tuy nhiên, doanh thu mà chúng mang lại là không được xem xét đến. Một ví dụ cụ thể, tại một sàn giao dịch điện tử có kinh doanh nhiều mặt hàng liên quan đến lĩnh vực Tin học.
Trong số các mặt hàng kinh doanh, các sản phẩm mang lại giá trị doanh thu thấp như bàn phím, chuột, thẻ nhớ hoặc các linh kiện khác thường được người dùng chọn mua nhiều; các sản phẩm có giá trị doanh thu cao như hệ thống máy trạm, máy chủ, v.v… lại thường ít được người dùng thông thường chọn mua. Khi ta đưa CSDL giao dịch của sàn giao dịch điện tử này làm đầu vào của vào bài toán FIM, kết quả thu được sẽ không chứa các mặt hàng hoặc sản phẩm có giá trị doanh thu cao mà chỉ chứa các sản phẩm thường được khách hàng lựa chọn mua nhiều. Các mặt hàng này mặc dù thường hay xuất hiện trong các giao dịch của CSDL, nhưng doanh thu của chúng mang lại cho đơn vị kinh doanh là không nhiều. 2 Có thể nhận thấy, khi áp dụng bài toán FIM vào trong một số ứng dụng thực tế, hạn chế của bài toán này được bộc lộ rõ.
Từ đó, một bài toán khác mở rộng dựa trên bài toán FIM đã được giới thiệu. Bài toán này có tên gọi là bài toán khai thác tập mục hữu ích cao (HUIM) [13]. Tương tự như FIM, bài toán HUIM cũng nhận được nhiều sự quan tâm, khảo sát từ các nhà nghiên cứu [14–21]. Nhược điểm quan trọng đã nêu của bài toán FIM được xác định là mục tiêu chính của bài toán HUIM.
Thay vì chỉ là liệt kê danh sách các hạng mục được chọn mua dưới dạng giao dịch, bài toán HUIM mở rộng CSDL giao dịch để chứa thêm các dữ liệu thực tế mà bài toán quan tâm. Khi đó, số lượng của mỗi hạng mục và đơn giá của chúng sẽ được HUIM xem xét. Tích của hai đại lượng này cung cấp một giá trị biểu thị trọng số, doanh thu hoặc tầm quan trọng mà hạng mục đó mang lại. Và để không làm mất tính tổng quát của bài toán HUIM, các khái niệm này ta gọi chung là mức độ hữu ích (utility) của các hạng mục/tập mục trong giao dịch.
Tương tự bài toán FIM, bài toán HUIM cũng xem xét hai tham số đầu vào. Tham số đầu tiên một CSDL giao dịch với đầy đủ các thông tin cần thiết của mỗi hạng mục như số lượng và đơn giá của hạng mục đó. Tham số thứ hai là một ngưỡng biểu thị độ hữu ích tối thiểu (𝑚𝑖𝑛𝑢𝑡𝑖𝑙) mà các tập mục cần phải thoả để trở thành tập mục hữu ích cao (HUI). Ngoài mục đích chính là áp dụng trong bài toán phân tích hành vi khách hàng, hiện nay HUIM cũng được đưa vào các ứng dụng khác như phục vụ khảo sát thị trường, sinh tin học, phát hiện xâm nhập, v.v… Bài toán FIM tồn tại một tính chất quan trọng mà có thể tận dụng để giảm chi phí thực hiện giải thuật, đó là tính chất Apriori hay còn gọi là tính chất bao đóng giảm DCP.
Tính chất này có thể phát biểu ngắn gọn như sau: “nếu một tập mục là phổ biến, các tập con của nó cũng là các tập mục phổ biến” [22]. Các tiếp cận giải quyết bài toán FIM đều áp dụng một cách triệt để tính chất quan trọng này lược bỏ bớt các tập mục không có tiềm năng trở thành tập phổ biến khỏi không gian tìm kiếm của bài toán; giảm chi phí tính toán không cần thiết để xét các tập ứng viên này. Từ đó, cải thiện được hiệu năng của giải thuật khai thác [2–12]. 3 Không như độ hỗ trợ của bài toán FIM, độ đo mức độ hữu ích của các hạng mục/tập mục trong bài toán HUIM không thoả tính chất DCP [22].
Do đó, các chiến lược tỉa ứng viên dựa trên độ đo độ hỗ trợ mà trước đó có thể hoạt động hiệu quả với các tiếp cận FIM thì lại hoàn toàn không khả dụng đối với bài toán HUIM. Điều này làm tăng số lượng ứng và không gian tìm kiếm của bài toán HUIM so với FIM. Đồng thời, làm tăng độ phức tạp của bài toán HUIM so với FIM. Các tiếp cận, giải thuật khai thác HUI vì vậy mà có thời gian khai thác dài, yêu cầu không gian bộ nhớ lớn.
Vì vậy, các nghiên cứu tập trung tìm kiếm một độ đo thỏa tính chất DCP để giúp loại bỏ các tập ứng viên không tiềm năng trong quá trình khai thác, cải thiện thời gian khai thác của bài toán và giảm thiểu mức độ sử dụng bộ nhớ. Trong thực tế, hàng loạt các nghiên cứu đã giới thiệu nhiều giải thuật để giải quyết hiệu quả bài toán này [14– 21]. Tương tự bài toán FIM, HUIM cũng tồn tại một đặc điểm là phát sinh một lượng lớn các tập mục kết quả. Do đó, cần nhiều thời gian để phân tích đầy đủ tập kết quả thu được.
Ngoài ra, việc phải lưu trữ một lượng lớn các tập mục kết quả sẽ làm tăng không gian bộ nhớ và chi phí tính toán. Điều này dẫn đến việc cần có một biểu diễn thu gọn của các tập mục HUI nhằm giảm thiểu số lượng tập mục, chi phí tính toán, cũng như lượng bộ nhớ cần để lưu trữ chúng. Để thu gọn tập kết quả của bài toán, có hai dạng biểu diễn chính thường được sử dụng trong các bài toán khai thác mẫu nói chung và bài toán HUIM nói riêng: biểu diễn tập mục tối đại [23–26] và biểu diễn tập mục đóng [18,25,27–31]. Khái niệm các tập mục hữu ích cao đóng (CHUI), tập mục hữu ích cao tối đại (MHUI) cũng được mở rộng từ khái niệm tập mục phổ biến đóng [32] và tối đại [33] trong bài toán FIM.
Ngoài ra, trong thực tế các cửa hàng bán lẻ thường tổ chức các mặt hàng dưới dạng các nhóm mặt hàng hoặc chủng loại mặt hàng. Ví dụ, một cửa hàng bán thiết bị Tin học có kinh doanh nhiều mặt hàng như đĩa cứng, bộ nhớ RAM, card đồ họa, máy in, máy scan, máy tính cá nhân, máy chủ, laptop, v.v… Các mặt hàng này được cửa hàng phân thành các nhóm ở mức tổng quát cao hơn như thiết bị ngoại vi bao gồm máy in, 4 máy scan; linh kiện, bao gồm đĩa cứng, bộ nhớ RAM, card đồ họa; máy điện toán bao gồm máy tính cá nhân, máy chủ, laptop thuộc nhiều nhãn hiệu khác nhau, v.v… Các nhóm mặt hàng tổng quát này lại có thể được tổng quát hóa ở mức cao hơn nữa. Các tiếp cận phục vụ cho bài toán HUIM trước đó đều chỉ quan tâm đến các mặt hàng chuyên biệt trong quá trình khai thác mà chưa quan tâm đến nhóm mặt hàng ở các mức tổng quát cao hơn. Năm 2017, kế thừa từ bài toán khai thác FIM tổng quát của các nghiên cứu trước đó [34–40], bài toán khai thác tập mục hữu ích cao tổng quát từ CSDL có sự phân cấp các hạng mục được đề xuất [41].