Luận văn Khai thác tập mục lợi ích cao sử dụng phương pháp tối ưu đàn kiến

Nội dung tài liệu: Luận văn Khai thác tập mục lợi ích cao sử dụng phương pháp tối ưu đàn kiến

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN ĐỨC DŨNG KHAI THÁC TẬP MỤC LỢI ÍCH CAO SỬ DỤNG PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN Ngành: Khoa học máy tính Chuyên ngành: Khoa học máy tính Mã số: 8480101.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hoàng Xuân Huấn Hà Nội - 2019
2. LỜI CẢM ƠN Tôi xin gửi lời cảm ơn chân thành nhất tới PGS.TS Hoàng Xuân Huấn, người thầy đáng kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiên cứu và hoàn thiện luận văn. Với kiến thức sâu rộng, nhiều năm nghiên cứu trong lĩnh vực tối ưu hóa cũng như phương pháp tối ưu hệ kiến của thầy đã giúp tôi hiểu rõ, sâu sắc nhiều khó khăn gặp phải trong quá trình nghiên cứu. Thầy cũng đưa ra những góp ý chi tiết, tỉ mỉ hết sức quý báu giúp cho tôi có thể hoàn thành quyển luận văn này. Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể và cá nhân tôi nói riêng. Tôi xin cảm ơn tới các thầy và các anh chị đã thường xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn. Hà Nội, tháng 3 năm 2019 HỌC VIÊN Nguyễn Đức Dũng 2
3. LỜI CAM ĐOAN Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới sự hướng dẫn giúp đỡ của PGS.TS Hoàng Xuân Huấn. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được liệt kê tại mục tài liệu tham khảo. Hà Nội, tháng 3 năm 2019 HỌC VIÊN Nguyễn Đức Dũng 3
4. MỤC LỤC LỜI CẢM ƠN ...................................................................................................................... 2 LỜI CAM ĐOAN ................................................................................................................ 3 DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ...................................................................... 6 DANH SÁCH CÁC BẢNG ................................................................................................ 7 DANH SÁCH HÌNH VẼ ..................................................................................................... 8 MỞ ĐẦU ............................................................................................................................. 9 CHƯƠNG 1: TỐI ƯU TỔ HỢP VÀ BÀI TOÁN TỐI ƯU ĐÀN KIẾN .......................... 12 1.1. Giới thiệu bài toán tối ưu tổ hợp ............................................................................ 12 1.2. Giới thiệu bài toán người chào hàng ...................................................................... 13 1.3. Các cách tiếp cận giải quyết bài toán tối ưu tổ hợp ................................................ 13 1.3.1. Heuristic cấu trúc ............................................................................................. 13 1.3.2. Tìm kiếm địa phương ...................................................................................... 14 1.3.3. Phương pháp meta-heuristic ............................................................................ 15 1.3.4. Phương pháp memetic ..................................................................................... 15 1.4. Phương pháp tối ưu đàn kiến .................................................................................. 16 1.4.1. Từ kiến tự nhiên đến kiến nhân tạo ..................................................................... 16 1.4.1.1. Kiến tự nhiên ................................................................................................ 16 1.4.1.2. Kiến nhân tạo (Artificial Ant) ...................................................................... 19 1.4.2. Phương pháp tối ưu đàn kiến ............................................................................... 19 1.4.3. Mô tả thuật toán ACO tổng quát ......................................................................... 20 1.4.4. Các hệ kiến .......................................................................................................... 22 1.4.4.1. Hệ kiến AS ................................................................................................... 22 1.4.4.2. Hệ kiến ACS ................................................................................................. 23 1.4.4.3. Hệ kiến Max-Min ......................................................................................... 25 1.4.4.4. Hệ kiến Max-Min trơn .................................................................................. 26 CHƯƠNG 2: KHAI THÁC TẬP MỤC CAO TIỆN ÍCH BẰNG PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN ................................................................................................................. 27 2.1. Bài toán khai thác tập mục lợi ích cao.................................................................... 27 2.2. Một số phương pháp tiếp cận để giải bài toán ........................................................ 30 2.3. Thuật toán HUIM-ACS. ......................................................................................... 31 4
5. 2.3.1. Xây dựng đồ thị cấu trúc và khởi tạo vết mùi. ................................................ 31 2.3.2. Quy tắc cắt tỉa nút ............................................................................................ 35 2.3.3. Quy tắc cập nhật mùi ....................................................................................... 37 2.4. Thuật toán HUIM-SMMAS ................................................................................... 39 CHƯƠNG 3: KẾT QUẢ THỰC NGHIỆM, SO SÁNH VÀ ĐÁNH GIÁ ....................... 41 3.1. Bộ dữ liệu chuẩn ..................................................................................................... 41 3.2. Tiến hành chạy thực nghiệm .................................................................................. 41 3.3. Kết quả thực nghiệm và đánh giá ........................................................................... 42 KẾT LUẬN ....................................................................................................................... 44 TÀI LIỆU THAM KHẢO ................................................................................................. 45 5
6. DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ 1 ACO Ant Colony Optimization (Tối ưu hóa đàn kiến) 2 AS Ant System (Hệ kiến AS) 3 ACS Ant Colony System (Hệ kiến ACS) 4 MMAS Max-Min Ant System (Hệ kiến MMAS) 5 SMMAS Smooth-Max Min Ant System (Hệ kiến MMAS trơn) 6 TSP Travelling Salesman Problem (Bài toán người chào hàng) 7 TƯTH Tối ưu tổ hợp 8 HUI High-Utility Itemset 9 HUIM High-Utility Itemsets Mining 10 TWU Transaction-Weight Utility 11 FIM Frequence Itemset Mining 6
7. DANH SÁCH CÁC BẢNG Bảng 2.1: Danh sách giao dịch và bảng lợi nhuận của từng sản phẩm ................... 27 Bảng 3.1: Bộ dữ liệu chạy thử nghiệm ................................................................... 41 Bảng 3.2: Ngưỡng tiện ích thiết lập chạy thực nghiệm .......................................... 41 7
8. DANH SÁCH HÌNH VẼ Hình 1.1: Lời giải nhận được thông qua tìm kiếm địa phương............................... 15 Hình 1.2: Thể hiện hành vi của mỗi con kiến trong tự nhiên ................................. 17 Hình 1.3: Thực nghiệm trên cây cầu đôi ................................................................. 18 Hình 1.4: Thí nghiệm bổ sung ................................................................................. 19 Hình 1.5: Lựa chọn đỉnh đi tiếp theo ...................................................................... 21 Hình 2.3.1: Đồ thị cấu trúc định tuyến với 3 items ................................................. 32 Hình 2.3.2: Hàm heuristic trong trường hợp không có thông tin về TWU ............ 33 Hình 2.3.3: Hàm heuristic giữ lại tất cả TWU ........................................................ 34 Hình 2.3.4: Hàm heuristic tính toán các TWU ....................................................... 35 Hình 2.3.5: Quy tắc cắt tỉa tích cực ......................................................................... 36 Hình 3.3.1: So sánh số lượng HUI tìm được của 2 thuật toán ................................ 42 Hình 3.3.2: So sánh thời gian thực hiện của các thuật toán .................................... 43 Hình 3.3.3: So sánh tốc độ hội tụ của hai thuật toán .............................................. 43 8
9. MỞ ĐẦU Hiện nay, việc tính toán doanh số và tối ưu hóa lợi nhuận bán hàng là công việc cực kỳ quan trọng, nó ảnh hưởng trực tiếp đến doanh thu và chiến lược bán hàng của các công ty, siêu thị hay các đơn vị bán lẻ. Đặc biệt, với số lượng hàng hóa lớn, giá cả khác nhau, nên việc tính toán lợi nhuận tối ưu từ bán hàng càng có quan trọng. Trong khi số lượng giao dịch mỗi giờ có thể lên đến hàng chục nghìn giao dịch, việc tính toán xem mặt hàng nào đem lại doanh số cao, mặt hàng nào kinh doanh không hiệu quả dù bán với số lượng lớn càng trở nên khó khăn do dữ liệu quá lớn, liên tục. Bài toán khai thác tập mục lợi ích cao(High-Utility Itemsets Mining – HUIM) đã được nhóm tác giả R.C. Chan, Q. Yang, Y.D. Shen đề xuất vào năm 2003, để tìm ra các HUI(High-Utility Itemsets), là các tổ hợp đem lại lợi nhuận cao nhất từ cơ sở dữ liệu giao dịch được lưu lại. Từ đó, các công ty, siêu thị bán lẻ sẽ đưa ra các chiến lược kinh doanh cho phù hợp, nhằm tối đa hóa lợi nhuận. Trong các phương pháp đề xuất trước đó, hầu hết các nghiên cứu tập trung vào việc khai thác tần suất xuất hiện của các tập mục (FIM) và khai thác quy tắc liên kết (ARM). Các thuật toán này đã được phát triển để khai thác tập hợp các tập mục có tần suất xuất hiện không nhỏ hơn ngưỡng tối thiểu và để tìm ra các quy tắc liên kết mà độ tin cậy không thấp hơn ngưỡng tối thiểu[1, 2]. Vì chỉ có các tần suất xuất hiện của các tập mục được phát hiện trong FIM hoặc ARM, nó không đủ để xác định các tập dữ liệu có lợi nhuận cao, đặc biệt là khi các tập mục hiếm khi xuất hiện nhưng có các giá trị lợi nhuận cao. Ví dụ, một cửa hàng bách hóa có thể bán ít đồ trang sức hơn hầu hết các hàng hoá khác trong một tháng, nhưng đồ trang sức thường có thể có được lợi nhuận cao hơn các hàng hoá khác mua nhiều hơn trong cùng thời kỳ. Trên thực tế, thông tin cho các tập mục lợi ích cao (HUIs) có giá trị hơn các tập phổ biến. Khác với FIM hoặc ARM, vấn đề khai thác các tập mục lợi ích cao (HUIM) [3-6] đã được đề xuất để khám phá ra các tập “có ích” và “có lợi nhuận” từ một cơ sở dữ liệu định lượng. Một ngưỡng lợi ích tối thiểu cho người dùng cụ thể được sử dụng để ước tính liệu một tập thuộc tính là một tập mục lợi ích cao hay không (HUI). Tập dữ liệu là một HUI nếu giá trị lợi nhuận của tập này cao hơn ngưỡng. Trong thực tế, không chỉ “lợi nhuận” có thể được áp dụng như là giá trị tiện ích để khai thác các tập mục có ích, “trọng lượng”, “chi phí” và các yếu tố khác cũng có thể khai thác được các HUI. 9
10. Có nhiều thuật toán đã được đề xuất để khai thác tập hợp các HUI. Chan và cộng sự [7] lần đầu tiên đề xuất khái niệm về vấn đề khai thác hữu ích thay vì FIM. Yao và cộng sự [4] đề xuất khai thác các HUI theo số lượng các mặt hàng như là tiện ích nội bộ và lợi nhuận đơn vị của các mặt hàng là tiện ích bên ngoài. Liu và các cộng sự [8] đã đề xuất mô hình TWU (Transaction Weight Utility) hai giai đoạn và trọng số giao dịch giảm dần (TWDC) để khai thác các HUI. Lin và cộng sự [9] trình bày một cây HUP để khai thác HUIs. Lan và cộng sự[10] đã thiết kế các thuật toán khai thác dựa trên cơ chế thiết lập chỉ mục(Index) và phát triển chiến lược cắt tỉa để khai thác hiệu quả các HUI. Sau đó, Tseng [11] đã thiết kế thuật toán khai thác tăng trưởng để lấy các HUI dựa trên cấu trúc cây UP-develop. HUI-Miner [12] là một thuật toán hiệu quả được sử dụng nhiều để khai thác các HUI. Các thuật toán đề xuất để giải bài toán HUIM phải mất nhiều thời gian tính toán hơn cùng với một không gian tìm kiếm khổng lồ, trong khi số lượng các mục riêng biệt hoặc kích thước cơ sở dữ liệu là rất lớn. Các thuật toán tiến hóa là một cách hiệu quả và có thể tìm ra các giải pháp tối ưu sử dụng các nguyên tắc của sự tiến hóa tự nhiên [21]. Các điều kiện dừng nghiêm ngặt có thể được thiết lập để hạn chế thời gian tính toán cho một quá trình nhưng vẫn có được một giải pháp gần như tối ưu. Thuật toán di truyền (GA) [22], là một loại EC, một cách tiếp cận tối ưu để giải quyết các bài toán NP-hard và không tuyến tính, và được sử dụng để tìm kiếm trên các không gian tìm kiếm rất lớn để tìm ra các giải pháp tối ưu cho các hàm mục tiêu được thiết kế với các bài toán khác nhau như lựa chọn, chéo và đột biến. Trong quá khứ, Kannimuthu và Premalatha [20] đã thông qua thuật toán di truyền và phát triển sự khai thác các tập mục lợi ích cao bằng cách sử dụng các thuật toán di truyền với đột biến xếp hạng sử dụng ngưỡng tiện ích tối thiểu (HUPEumu-GRAM) để khai thác HUI. Một thuật toán di truyền khác gọi là HUPEwumu-GRAM cũng được đề xuất để khai thác HUIs với một ngưỡng tiện ích tối thiểu cụ thể. Đối với hai thuật toán này, việc di truyền chéo và đột biến được sử dụng để ngẫu nhiên tạo ra các lời giải tiếp theo trong quá trình tiến hóa. Tuy nhiên, nó cần một số lượng HUI khởi tạo ban đầu, trong khi số lượng các HUI còn lại trong cơ sở dữ liệu là rất lớn. Thuật toán tối ưu bầy đàn (Particle Swarm Optimization-PSO) là một trong những kỹ thuật tối ưu được sử dụng nhiều nhất [23]. Lin và cộng sự [24] đề xuất một kỹ thuật dựa trên PSO để khai thác các tập mục lợi ích cao dựa trên PSO nhị phân (BPSO). Nó được gọi là HUIM-BPSO và áp dụng mô hình TWU để tìm HUI hiệu quả. Ngoài ra, các thuật toán thuộc nhóm kiến hoặc các phép lai của ACO với các thuật toán meta-heuristic khác cũng được áp dụng trong lĩnh vực khai thác dữ liệu 10