Luận án tiến sĩ: Khai thác tập mục hữu ích cao trên tính toán song song

BỘ CÔNG THƯƠNG TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH NGUYỄN ĐẮC DZỰ TRÌNH KHAI THÁC TẬP MỤC HỮU ÍCH CAO TRÊN MÔI TRƯỜNG TÍNH TOÁN SONG SONG LUẬN ÁN TIẾN SĨ THÀNH PHỐ HỒ CHÍ MINH, NĂM 2024 BỘ CÔNG THƯƠNG TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH NGUYỄN ĐẮC DZỰ TRÌNH KHAI THÁC TẬP MỤC HỮU ÍCH CAO TRÊN MÔI TRƯỜNG TÍNH TOÁN SONG SONG Chuyên ngành: Khoa học Máy tính Mã số chuyên ngành: 9480101 Phản biện độc lập 1:. Phản biện độc lập 2:. NGƯỜI HƯỚNG DẪN: 1. Nguyễn Thị Thuý Loan 2.

Phạm Thị Thiết BỘ CÔNG THƯƠNG CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP Độc lập - Tự do - Hạnh phúc THÀNH PHỐ HỒ CHÍ MINH NHIỆM VỤ LUẬN ÁN TIẾN SĨ Họ tên nghiên cứu sinh: Nguyễn Đắc Dzự Trình MSHV: 20126291 Ngày, tháng, năm sinh: 13/3/1979 Nơi sinh: TP. Hồ Chí Minh Ngành: Khoa học máy tính Mã ngành: 9480101 I. TÊN LUẬN ÁN: Khai thác tập mục hữu ích cao trên môi trường tính toán song song NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu định nghĩa, mục tiêu và ứng dụng của các tập mục hữu ích cao. - Tìm hiểu định dạng cơ sở dữ liệu có sự phân cấp các hạng mục.

- Khảo sát các tiếp cận khai thác tập mục hữu ích cao trên cơ sở dữ liệu có phân cấp hạng mục có áp dụng kỹ thuật xử lý song song. - Đề xuất phương pháp giải quyết bài toán khai thác tập mục hữu ích cao, tập mục hữu ích đa mức từ các cơ sở dữ liệu có sự phân cấp các hạng mục, áp dụng các chiến lược song song hoá. - Thực nghiệm, đánh giá hiệu năng của phương pháp được đề xuất dựa trên các tiêu chí như thời gian thực hiện, mức độ tiêu thụ bộ nhớ, tính khả mở. NGÀY GIAO NHIỆM VỤ: 13/8/2021 III.

NGÀY HOÀN THÀNH NHIỆM VỤ: 01/06/2024 IV. NGƯỜI HƯỚNG DẪN KHOA HỌC: - PGS. Nguyễn Thị Thuý Loan (Trường Đại học Quốc tế, ĐHQG TP. Phạm Thị Thiết (Trường Đại học Công nghiệp TP.

Hồ Chí Minh, ngày … tháng … năm 20 … NGƯỜI HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRƯỞNG KHOA/VIỆN….……… (Họ tên và chữ ký) LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân tôi. Các kết quả nghiên cứu và các kết luận trong luận án là trung thực, không sao chép từ bất kỳ một nguồn nào và dưới bất kỳ hình thức nào. Việc tham khảo các nguồn tài liệu (nếu có) đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định. Tác giả luận án NCS.

Nguyễn Đắc Dzự Trình i TÓM TẮT LUẬN ÁN TIẾN SĨ Khai thác tập mục hữu ích cao (HUIM) là bài toán tìm kiếm các tập mục mang lại độ hữu ích thỏa một ngưỡng cho trước. Mỗi hạng mục trong giao dịch có một giá trị biểu thị số lượng. Chúng còn có một giá trị biểu thị đơn giá trong toàn bộ CSDL. Tích của hai đại lượng này biểu thị tầm quan trọng, trọng số, hay nói chung là độ hữu ích của hạng mục tương ứng.

Nhiều kỹ thuật và giải thuật đã được giới thiệu để tối ưu hoá không gian tìm kiếm dựa trên các chiến lược tỉa ứng viên, giảm chi phí quét CSDL, tăng tốc quá trình tính độ hữu ích, v.v… Ngày nay, các vi xử lý đa nhân dần phổ biến với chi phí phù hợp với người dùng. Các tác vụ tính toán cũng vì thế được mở rộng để tận dụng sức mạnh tính toán này nhằm cải thiện hiệu năng. Tuy nhiên, đối với bài toán khai thác dữ liệu, các tiếp cận kết hợp mô hình xử lý song song đa nhân hiện này vẫn còn rất hạn chế. Vì vậy, luận án nghiên cứu và đề xuất các đóng góp chính sau: Đóng góp thứ nhất: đề xuất mô hình cho phép khai thác hiệu quả các tập mục hữu ích cao đóng từ CSDL có chứa các hạng mục với độ hữu ích động trong quá trình khai thác nhằm phản ánh sát hơn nữa các CSDL trong thực tế.

Đóng góp này áp dụng mô hình độ hữu ích động kết hợp với phương pháp để giảm chi phí quét CSDL nhằm cải thiện hiệu năng của quá trình khai thác tập mục hữu ích cao đóng. Chương 2 trình bày nghiên cứu và mô hình đề xuất thông qua giải thuật iEFIM-Closed. Đóng góp thứ hai: mở rộng bài toán để áp dụng với dạng CSDL có sự phân cấp các hạng mục dựa trên các nghiên cứu từ Đóng góp thứ nhất, và đề xuất mô hình xử lý song song đa nhân để giải quyết bài toán này thông qua việc tận dụng năng lực xử lý của các CPU đa nhân để giảm chi phí về mặt thời gian. Nội dung của đóng góp được trình bày tại Chương 3.

Thực nghiệm cho thấy mô hình đề xuất có sự cải thiện rõ rệt về thời gian khai thác. Đóng góp thứ ba: dựa trên các kết quả nghiên cứu từ Đóng góp thứ 2 và Đóng góp thứ nhất, đóng góp này triển khai việc áp dụng mô hình xử lý song song trên nhiều giai đoạn khác nhau của quá trình khai thác, triển khai sâu hơn nữa mô hình song song trong quá trình khai thác. Ngoài ra, một chiến lược điều phối cũng được đề xuất ii để giảm thời gian chờ giữa các tác vụ song song. Toàn bộ đóng góp thứ ba nhắm đến việc tận dụng triệt để hơn nữa sức mạnh xử lý của các CPU đa nhân với chi phí phù hợp vào bài toán khai thác tập mục hữu ích cao từ định dạng CSDL phân cấp, có độ hữu ích động.

Thực nghiệm cho thấy với mô hình được đề xuất trong Đóng góp thứ ba, hiệu năng khai thác của bài toán được nâng lên đáng kể so với tiếp cận không song song, đặc biệt trên các CSDL có kích thước lớn. iii ABSTRACT High Utility Itemset Mining (HUIM) aims to extract itemsets that have utility to satisfy a user-specified threshold. Each item in the transaction is linked with a value denoted by its quantity. In addition, each item has another value denoted by its unit profit in the whole transaction database.

The product of the values of an item yields its weight, importance, or utility. Several strategies and algorithms were proposed to enhance the mining performance of this task, focusing on optimizing search space, reducing the cost of database scans, speeding up utility calculations, etc. Nowadays, multi-core processors are widely available at a reasonable price to users. Many computing tasks are also extended using multi-core processors to boost performance.

However, approaches that adopt parallelism into the HUIM task still need to be improved. Thus, the main contributions of this dissertation are as follows. Contribution #1: proposed a model to efficiently extract closed high-utility itemset from databases containing items with dynamic utility values, to reflect real-world databases better. The contribution adopts the dynamic utility framework and a method to significantly reduce the cost of database scans while mining closed high- utility itemsets.

Chapter 2 presents the studies of this contribution as well as the proposed model, resulting in the iEFIM-Closed algorithm. Contribution #2: extend the mining task studied in Contribution #1 to work with hierarchical databases. A parallel computing model is also proposed to utilize the multicore processor in the mining task, reducing mining time. Chapter 3 presents the studies and the proposed method to solve the task efficiently.

Evaluations clearly show that the proposed model boosted mining performance regarding mining time. Contribution #3: In addition to the results from Contribution #1 and Contribution #2, this contribution extends the parallel computing model into other phases of the mining algorithm, not just the mining phase. A deeper level of parallelism is also applied to the mining phase. A scheduling task is also proposed to minimize the average waiting time among threads.

The overall focus of this contribution is to extensively utilize the iv computing power provided by the multicore processors in the mining task on dynamic profit hierarchical databases. Experiments on several databases also show that the proposed model and the algorithms perform better than the serial, non-parallel approach. The performance boost is clearly demonstrated on large databases. v LỜI CẢM ƠN Tôi bắt đầu con đường nghiên cứu và học thuật khi đã là một người trưởng thành, có công việc và một gia đình ổn định.

Vì vậy, việc theo đuổi công việc nghiên cứu, đặc biệt là thực hiện luận án tiến sĩ là một thử thách rất lớn. Công việc nghiên cứu lại đòi hỏi sự tập trung và kiên trì trong một quãng thời gian dài. Với các kết quả đạt được trong đề tài nghiên cứu của mình, có phần hỗ trợ rất lớn từ tập thể cán bộ hướng dẫn, cơ sở đào tạo, đồng nghiệp và từ phía gia đình. Là những người đã luôn đồng hành, sát cánh cùng tôi vượt qua các khó khăn, thử thách và trở ngại trong quá trình nghiên cứu, thực hiện luận án để thu được những kết quả nghiên cứu như hiện nay.

Qua luận án này, tôi muốn bày tỏ lòng biết ơn đến những người hỗ trợ cho tôi. Trước hết, tôi xin bày tỏ lòng biết ơn đến PGS. Nguyễn Thị Thúy Loan, cán bộ hướng dẫn chính của luận án. Cô đã luôn theo sát, động viên, truyền đạt các kiến thức chuyên môn trong quá trình thực hiện luận án, cũng như trong quá trình thực hiện các nghiên cứu của luận án này.

Tôi cũng xin gửi lời cảm ơn chân thành đến TS. Phạm Thị Thiết, cán bộ đồng hướng dẫn luận án. Cô luôn đôn đốc, nhắc nhở và hướng dẫn các kiến thức hữu ích trong quá trình nghiên cứu cũng như trong quá trình thực hiện luận án. Tôi cũng muốn bày tỏ lòng biết ơn đến Nhóm Seminar Bảy- Loan, đã cố vấn và đưa ra nhiều góp ý quan trọng liên quan đến định hướng học thuật cũng như quá trình thực hiện luận án.

Kế đến, tôi cũng xin gửi lời cảm ơn đến tập thể cán bộ, giảng viên khoa Công nghệ thông tin, Trường Đại học Công nghiệp TP.HCM nói riêng và Trường Đại học Công nghiệp TP.HCM nói chung, đặc biệt là TS. Lê Nhật Duy, đã luôn tận tâm hỗ trợ, đóng góp các ý kiến thiết thực và quan trọng, tạo mọi điều kiện thuận lợi để tôi có thể hoàn thành luận án này. Bên cạnh đó, tôi xin cảm ơn tập thể cán bộ Viện đào tào quốc tế và Sau đại học đã hỗ trợ và tạo mọi điều kiện để tôi có thể hoàn thành được quá trình học tập và nghiên cứu tại Trường Đại học Công nghiệp TP. vi Ngoài ra, tôi cũng muốn gửi lời cảm ơn đến các đồng nghiệp trong nhóm nghiên cứu, cũng như tại Khoa Công nghệ thông tin thuộc Trường đại học HUTECH đã chia sẻ các buồn vui, kinh nghiệm và hỗ trợ tôi trong suốt hành trình tham gia nghiên cứu khoa học và thực hiện luận án này.

Cuối cùng, tôi cũng muốn gửi đến gia đình yêu quý của mình lời cảm ơn sâu sắc.