Nâng cao tính hiệu quả trong việc khai thác tập hữu ích cao hiếm trên cơ sở dữ liệu lớn

Bài viết đề xuất và áp dụng cấu trúc dữ liệu phù hợp để xây dựng một thuật toán khai thác tập hữu ích cao hiếm, hiệu quả hơn các thuật toán trước đây về cả không gian tìm kiếm và thời gian thực thi.
Nội dung trích xuất từ tài liệu:
Nâng cao tính hiệu quả trong việc khai thác tập hữu ích cao hiếm trên cơ sở dữ liệu lớn Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0064 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI THÁC TẬP HỮU ÍCH CAO HIẾM TRÊN CƠ SỞ DỮ LIỆU LỚN Vũ Văn Vinh*, Lâm Thị Họa Mi, Dương Thị Mộng Thùy Khoa Công nghệ thông tin, Trường Đại học Công nghiệp thực phẩm TP. HCM vinhvv@hufi.edu.vn, milth@hufi.edu.vn, thuydtm@hufi.edu.vn TÓM TẮT: Khai thác tập hữu ích cao có ý nghĩa to lớn trong hoạt động sản xuất kinh doanh. Trong nhiều tình huống thực tế, các trường hợp hiếm gặp được quan tâm nhiều hơn (ví dụ, trong y học, các triệu chứng hiếm gặp đặt ra thách thức và cung cấp những hiểu biết hữu ích cho các bác sĩ trong chuẩn đoán bệnh). Khai thác tập hữu ích cao hiếm đang là chủ đề được nhiều nhà khoa học quan tâm hiện nay. Một số thuật toán đã được đề xuất để giải quyết vấn đề này, nhưng chúng tiêu tốn nhiều thời gian và không gian lưu trữ. Trong bài báo này, chúng tôi sẽ đề xuất và áp dụng cấu trúc dữ liệu phù hợp để xây dựng một thuật toán khai thác tập hữu ích cao hiếm, hiệu quả hơn các thuật toán trước đây về cả không gian tìm kiếm và thời gian thực thi. Từ khóa: Khai phá luật kết hợp, tập hữu ích cao, tập hữu ích cao hiếm, RCUL. I. GIỚI THIỆU Khai thác dữ liệu được nghiên cứu để chuyển đổi dữ liệu thô thành những thông tin có ý nghĩa phục vụ cho nhiều mục đích khác nhau, đặc biệt hiện nay lại có ý nghĩa to lớn trong hoạt động sản xuất, kinh doanh. Các nhà sản xuất nhận ra rằng mục tiêu “đến gần hơn với khách hàng” là rất quan trọng đối với sự phát triển của một doanh nghiệp. Khai phá luật kết hợp (ARM - Association Rule Mining) là một trong những phương pháp được sử dụng rộng rãi nhất trong khai thác dữ liệu và khám phá tri thức. Tuy nhiên, ARM truyền thống chủ yếu tập trung vào việc khai thác tập mục phổ biến. Các tập mục này được sinh ra chỉ có thể đóng góp một phần nhỏ trên lợi nhuận tổng thể. Trong khi đó, các tập mục (mặt hàng) hiếm khi xuất hiện trong cơ sở dữ liệu, hay còn được gọi là các tập mục hiếm (hoặc không phổ biến) có thể mang lại một số lợi nhuận đặc biệt (hoặc rất lớn). Trong nhiều tình huống thực tế, những trường hợp hiếm gặp lại được quan tâm cao hơn (ví dụ: trong y học, những triệu chứng hiếm gặp đặt ra những thách thức và cung cấp những hiểu biết hữu ích cho bác sĩ trong điều trị bệnh) [1] Vì vậy, khai thác tập mục hiếm là một chủ đề hấp dẫn nhiều nhà khoa học ngày nay. Vào năm 2013, Jyothi và cộng sự đã nghiên cứu và đề xuất thuật toán HURI khai thác vật phẩm hiếm hữu ích cao [2]. HURI đã thực hiện tìm kiếm một cách hiệu quả các tập mục hiếm, có tính tiện ích cao theo người dùng. Các tập mục hiếm đã chứng minh là đáng được mong đợi hơn so với các mẫu phổ biến. Khai thác mẫu hiếm đã và đang được ứng dụng thực tế trong những lĩnh vực như: các bộ dữ liệu sinh học có thể được sử dụng để nhận dạng những bất thường và xác định được sự hiện diện của các gen hiếm, từ đó phát hiện các bệnh nguy hiểm hoặc những bất thường nghiêm trọng trong lĩnh vực tin sinh học; trong ngành dược phẩm, liều lượng và hàm lượng thuốc được nghiên cứu kỹ về hiệu quả trước khi phân phối ra thị trường. Khi đó, nghiên cứu những biểu hiện lâm sàng, giám sát những phản ứng bất lợi không mong muốn khi người bệnh sử dụng thuốc để chứng minh tính hiệu quả của thuốc có thể đáp ứng trong quá trình điều trị, mặc dù những phản ứng này là hiếm khi xảy ra nhưng là một quy trình không thể thiếu. Vấn đề bảo mật và phát hiện gian lận trong sử dụng internet là quan trọng trong việc tăng cường an ninh mạng cho một tổ chức, các hành vi đáng nghi ngờ nên được nghiên cứu và xử lý. Những hành vi này tuy là những hoạt động không phổ biến của người dùng nhưng nên được khai thác và nghiên cứu để tìm ra nghi phạm và cải thiện các chính sách bảo mật. Trong bài báo này, chúng tôi tiếp tục nghiên cứu vấn đề khai thác tập mục hiếm để có thể đề xuất một phương pháp khai thác tập hữu ích cao hiếm từ cơ sở dữ liệu giao dịch đã được thu thập nhằm tìm ra các thông tin hiệu quả phục vụ cho các hoạt động sản xuất kinh doanh trong thực tế. Cụ thể, chúng tôi sẽ đề xuất cấu trúc dữ liệu RCUL (Revised Compact Utility List) được cải tiến từ cấu trúc CUL [3] để có thể lưu trữ thông tin hiệu quả hơn phục vụ cho quá trình khai thác tập HURI, chúng tôi cũng áp dụng các chiến lược tỉa đã được đề xuất trong các nghiên cứu trước đây và tìm ra một phương pháp tỉa hiệu quả mới, cuối cùng chúng tôi áp dụng tất cả vào một thuật toán chúng tôi đề xuất có tên EHURI (Effcient High Utility Rare Itemsets) để nhanh chóng phát hiện được các tập HURI. Phần còn lại của bài báo được tổ chức như sau: Phần II trình bày các nghiên cứu liên quan đến bài toán khác tập mục hữu ích cao và tập mục hiếm hữu ích cao. Phần III trình bày thuật toán đóng góp của chúng tôi bao gồm những định nghĩa được sử dụng, cấu trúc lưu trữ dữ liệu, các chiến lược tỉa hiệu quả được áp dụng để loại bỏ những ứng viên không có tiềm năng nhằm thu gọn không gian sử dụng bộ nhớ và thời gian thực thi và thuật toán đề xuất. Môi trường, kết quả thực nghiệm và đánh giá thuật toán được trình bày trong Phần IV. Cuối cùng, Phần V sẽ trình bày kết luận và hướng phát triển của vấn đề được quan tâm. II. CÁC CÔNG TRÌNH LIÊN QUAN Khai thác luật kết hợp (ARM) đã và đang được nghiên cứu trong nhiều công trình nghiên cứu khoa học. Khai thác luật kết hợp là tìm ra mối liên hệ giữa các đối tượng trong cơ sở dữ liệu lớn. Từ năm 1994, Agrawal và cộng sự [4] đề xuất thuật toán Apriori. Ý tưởng chính của thuật toán này là dựa vào tập phổ biến (FI) và tính chất tỉa DCP để sinh 236 NÂNG CAO TÍNH HIỆU QUẢ TRONG VIỆC KHAI T ...