NGHIÊN CỨU THUẬT TOÁN KHAI THÁC TẬP HỮU ÍCH CAO TOP-K VÀ ỨNG DỤNG

NGHIÊN CỨU THUẬT TOÁN KHAI THÁC TẬP HỮU ÍCH CAO TOP-K VÀ ỨNG DỤNG

TÓM TẮT

Đề Tài này nhằm giới thiệu một cách tổng quan về phương pháp khai thác tập hữu ích cao top-k. Trong đó, hai thuật toán được nhóm tìm hiểu là thuật toán TKU_Base và TKO_Base. Thuật toán này dùng để giúp cho các cửa hàng, doanh nghiệp có thể thống kê, đánh giá được những sản phẩm nào mang lại lợi nhuận cao cho doanh nghiệp. Nhóm chúng em xây dựng một ứng dụng di động về mua bán sách để ứng dụng thuật toán.

CHƯƠNG 1:  TỔNG QUAN.. 1

1.1.      GIỚI THIỆU.. 1

1.1.1.  Thuật toán top-k.. 1

1.1.2.  Lý do chọn đề tài 1

1.1.3.  MỤC TIÊU VÀ PHẠM VI ĐỀ TÀI 1

CHƯƠNG 2:  TẬP HỮU ÍCH CAO.. 3

2.1.      TỔNG QUAN VỀ TẬP HỮU ÍCH CAO.. 3

2.2.      ỨNG DỤNG.. 3

2.3.      VẤN ĐỀ CỦA THUẬT TOÁN HUIs. 3

CHƯƠNG 3:  THUẬT TOÁN TOP-K.. 4

3.1.      TỔNG QUAN VỀ TOP-K.. 4

3.2.      ĐỊNH NGHĨA LIÊN QUAN.. 4

3.2.1.  Lợi nhuận của một mặt hàng trong giao dịch.. 4

3.2.2.  Lợi nhuận của một nhóm mặt hàng trong giao dịch.. 5

3.2.3.  Lợi nhuận của một nhóm mặt hàng trong cơ sở dữ liệu.. 5

3.2.4.  Lợi nhuận của giao dịch và tổng lợi nhuận.. 5

3.2.5.  Độ hữu ích của một nhóm mặt hàng trong cơ sở dữ liệu.. 5

3.2.6.  Tập phổ biến độ hữu ích cao.. 6

3.2.7.  TWU (Transaction weight utility). 6

3.2.8.  Tập hữu ích cao top-k.. 6

3.3.      THUẬT TOÁN.. 6

3.3.1.  Thuật toán TKU_Base. 6

3.3.1.1.   Phương pháp tiếp cận cơ bản TKU (TKU_Base). 6

3.3.1.2.   Xây dựng UP-Tree.. 7

3.3.1.3.   Khởi tạo các tập  hữu ích cao top-k tiềm năng từ UP-tree (PKHUIs)  8

3.3.1.4.   Xác định các tập hữu ích cao top-k từ PKHUIs. 11

3.3.2.  Thuật toán TKOBase.. 11

3.3.2.1.   Xây dựng cấu trúc danh sách độ hữu ích (utility-list). 11

3.3.2.2.   Thuật toán TKOBase.. 12

3.4.      Thực nghiệm... 13

CHƯƠNG 4:  PHÂN TÍCH THIẾT KẾ HỆ THỐNG.. 15

4.1.      GIỚI THIỆU.. 15

4.2.      MÔ HÌNH HÓA NGHIỆP VỤ.. 15

4.2.1.  Sơ đồ Use case nghiệp vụ.. 15

4.2.2.  Mô hình hóa quy trình nghiệp vụ.. 15

4.2.2.1.   Use case đăng ký.. 15

4.2.2.2.   Use case mua hàng.. 17

4.2.2.3.   Use case xác nhận đơn hàng.. 19

4.2.2.4.   Use case thanh toán.. 21

4.3.      MÔ HÌNH HÓA CHỨC NĂNG.. 23

4.3.1.  Sơ đồ use_case hệ thống.. 23

4.3.2.  Sơ đồ lớp ở mức phân tích.. 24

CHƯƠNG 5:  CÀI ĐẶT VÀ ỨNG DỤNG THUẬT TOÁN TKOBase.. 25

5.1.      Xây dựng database.. 25

5.2.      Xây dựng api 25

5.3.      Xây dựng ứng dụng mua hàng (sách) trên nền tảng đi động.. 29

5.4.      Áp dụng thuật toán TKO_Base vào ứng dụng.. 35

1. 1. GIỚI THIỆU
      1. Thuật toán top-k

Khai thác các tập phổ biến là vấn đề nhận được nhiều sự quan tâm, nghiên cứu trong thời gian gần đây. Có rất nhiều thuật toán được đưa ra để giải quyết bài toán này, tuy nhiên đa phần những thuật toán khai thác tập phổ biến sẽ dựa trên một ngưỡng cho trước, vì vậy không đáp ứng được các nhu cầu thực tế cũng như tính khách quan của việc đặt ngưỡng giá trị ngay ban đầu. Và để giải quyết vấn đề trên thì thuật toán Top-K ra đời.

Thuật toán Top-K giúp chúng ta tìm ra được k tập phổ biến một cách có hiệu quả, khách quan hơn thay vì việc phải đặt một ngưỡng giá trị cho trước.

1. 1. 2. Lý do chọn đề tài

Trong thời đại 4.0 ngày nay, số lượng ứng dụng hỗ trợ bán hàng trực tuyến ngày càng phát triển, và số lượng sản phẩm được bán trực tuyến cũng ngày càng tăng. Để các cửa hàng có thể đánh giá được những sản phẩm nào đem lại giá trị cao thì thuật toán top-k có thể ứng dụng vào các ứng dụng để giúp các cửa hàng có thể đánh giá một cách nhanh chóng cũng như hiệu quả hơn.

1. 1. 3. MỤC TIÊU VÀ PHẠM VI ĐỀ TÀI

Mục tiêu: Tìm hiểu về tập hữu ích cao (High Utility Itemset - HUI), khai thác tập hữu ích cao (High Utility Itemset Mining – HUIM),  các nghiên cứu liên quan đến khai thác tập hữu ích cao, thuật toán top-k để khai thác tập hữu ích cao. Cài đặt được thuật toán top-k và chạy thực nghiệm. Phân tích thiết kế hệ thống và ứng dụng thuật toán vào app bán sách. Ứng dụng thuật toán top-k vào ứng dụng di động bán sách giúp cho việc đánh giá hiệu quả kinh doanh hiệu quả hơn.

Phạm vi đề tài: Thuật toán được xây dựng để hỗ trợ việc thống kê, gợi ý cho cửa hàng về những sản phẩm mang lại lợi nhuận cao. Xây dựng app bán sách gồm có các chức năng:

➢ Hiển thị danh mục sách, loại sách.

➢ Thêm, xóa, sửa thông tin sách, loại sách

➢ Tìm kiếm, lựa chọn sách theo nhiều tiêu chí.

➢ Giỏ hàng

➢ Thanh toán

➢ Quản lý đơn đặt hàng

➢ Thống kê đơn hàng, sách bán.