ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY ĐÀN KHAI THÁC TOP-K MẪU HỮU ÍCH CAO
ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY ĐÀN KHAI THÁC TOP-K MẪU HỮU ÍCH CAO
Trương Quang Trung - CH1802063
Trong xu thế của nền kinh tế tri thức ngày nay, khi công nghệ thông tin có những bước tiến vượt bậc. Và đã góp mặt ở hầu hết các ngành nghề và không thể thiếu trong kinh doanh, nói đến kinh doanh là nói đến giao dịch mua bán hàng hoá,... Câu hỏi đặt ra là với dữ liệu bán hàng, dữ liệu lớn như vậy (phát sinh hàng ngày, hàng giờ) thì chúng ta có thể khai thác điều gì hữu ích làm cơ sở để hỗ trợ ra quyết định nhằm tối ưu lợi nhuận trong kinh doanh? Từ thực tế đó, khai thác dữ liệu (data mining) đã ra đời, mục tiêu là khai thác dữ liệu đã có, thực hiện quá trình phân loại, sắp xếp các tập hợp dữ liệu để xác định các mẫu và thiết lập các mối liên hệ nhằm giải quyết các vấn đề nhờ phân tích dữ liệu và hướng đi này đã có rất nhiều các công trình nghiên cứu khoa học, tiền đề là khai thác những mẫu xuất hiện thường xuyên trong dữ liệu giao dịch gọi là khai thác mẫu phổ biến.
Bài toán khai thác mẫu phổ biến vốn là một hướng nghiên cứu về khai thác dữ liệu [12] nhằm xác định tập các hạng mục có tần suất xuất hiện cao trong cơ sở dữ liệu giao dịch. Hạn chế là FIM không xét tới số lượng mua các mặt hàng và lợi nhuận của chúng [4]. Để giải quyết khăn của FIM, bài toán khai thác tập mục hữu ích cao (HUIM) được giới thiệu [3],[4]. HUIM không những là một chủ đề được nhiều nhà nghiên cứu quan tâm mà còn là sự quan tâm đặc biệt, nhất là trong khai thác dữ liệu khi đề cập đến việc khai thác các tập mục hữu ích đáp ứng.
Hiện nay nghiên cứu về HUI kết hợp meta-heuristics cũng có khá nhiều, ví dụ như: HUIF-PSO, HUIM-AF, HUIM-HC, HUIM-ACO, HUIF-PS. Tuy nhiên chưa có thuật toán nào áp dụng giải thuật tối ưu bầy đàn kết hợp với TKO (mining Top-k utility itemsets One phase) và TKU (Mining Top-k Utility itemsets) vào việc khai thác Top-k để tìm ra tập hữu ích cao. Lý do chính là do độ hữu ích không thỏa mãn tính chất Apriori (hay còn được biết với tên gọi tính chất bao đóng giảm). Vì vậy, việc tỉa bớt các ứng viên không tiềm năng là không đơn giản như FIM (độ phức tạp thấp) [5], [6]. Bên cạnh đó, khi thực hiện ứng dụng giải thuật tối ưu hoá bầy đàn (PSO) đang nghiên cứu vào khai thác HUIs lại tỏ ra khá hiệu quả để khai thác các tập mục hữu ích cao, khi không phải xử lý vấn đề theo cấp số nhân như thuật toán khai thác HUIs truyền thống, tiết kiệm được thời gian xử lý và bộ nhớ lưu trữ và đây cũng chính là lý do để đề xuất phương pháp mới.
Một trung tâm mua sắm có nhập một lượng mặt hàng rất lớn đến từ nhiều nhà sản xuất khác nhau. Các sản phẩm cửa hàng nhập về được sắp xếp ở nhiều vị trí khác nhau phục vụ cho chiến lược kinh doanh. Những giao dịch khi khách hàng mua sắm gọi là dữ liệu và được lưu dữ lại. Lượng dữ liệu của trung tâm mua sắm là rất lớn. Những nhà lãnh đạo trung tâm này muốn biết sản phẩm hay tập sản phẩm nào mà trung tâm bán ra thu về với nhiều lợi nhuận nhất, đóng góp lợi nhuận cho trung tâm nhiều nhất,… giúp nhà lãnh đạo hiểu rõ hơn về doanh thu và lợi nhuận từ từng nhóm sản phẩm. Dựa trên phân tích các sản phẩm có lợi nhuận cao, người lãnh đạo có thể nhận định được mức độ hiệu quả trong việc kinh doanh các sản phẩm và nhóm sản phẩm. Ngoài ra, tìm kiếm hướng kinh doanh để đạt lợi nhuận mong muốn. Mặt khác cũng giúp cho lãnh đạo nắm bắt được xu hướng thị trường và sự thay đổi trong nhu cầu của khách hàng. Với thông tin này, lãnh đạo có thể đưa ra những quyết định kinh doanh thông minh về việc mở rộng hoặc thu hẹp danh mục hàng hóa, xây dựng và phát triển danh mục các nhóm sản phẩm mang lại lợi nhuận cao.
Kết quả đạt được:
- Thuật toán tối ưu hóa bầy đàn là một trong những giải pháp đã được quan tâm rất nhiều khi ứng dụng một số bài toán cho kết quả rất tốt. Do đó, với ý tưởng khai thác Top-k mẫu hữu ích cao kết hợp với phương pháp tối ưu hóa PSO thì luận văn cũng đã đạt được kết quả nhất định.
- Thuật toán Top-k được giới thiệu để khai thác Top-k mẫu hữu ích cao và giới thiệu với hai thuật toán là TKU (TKUBASE) và TKO (TKOBASE). Luận văn thực hiện áp dụng theo thuật toán TKO (TKOBASE) do thuật toán TKO (TKOBASE) được đánh giá là có hiệu quả hơn.
- Kết quả thực nghiệm nói chung đã cho thấy thuật toán đề xuất cho kết quả rất khả quan, đã tối ưu được bộ nhớ so TKO. Tuy nhiên thuật toán đề xuất chưa thực sự vượt trội về tối ưu về thời gian. Về thuật toán TKU, tác giả trong bài viết [1] đã kết luận thuật toán TKU không cho kết quả tốt hơn so với TKO nên bài luận văn này tập trung so sánh với thuật toán TKO.
Trân trọng.