Thuật toán song song khai phá Top-K đồ thị con phổ biến

Khai phá đồ thị là một nhiệm vụ quan trọng của khai phá dữ liệu đồ thị và nó có rất nhiều ứng dụng trong thực tiễn, ví dụ như: phân tích liên kết web, phân tích mạng xã hội, phát hiện gian lận, phát hiện ngoại lệ, phân tích phân tử hóa học,... Bài viết đề xuất một thuật toán song song để khắc phục điểm yếu này. Hiệu suất và khả năng mở rộng của thuật toán đề xuất được minh họa thông qua các thực nghiệm trên hai bộ dữ liệu cụ thể.
Nội dung trích xuất từ tài liệu:
Thuật toán song song khai phá Top-K đồ thị con phổ biến Nghiên cứu khoa học công nghệ THUẬT TOÁN SONG SONG KHAI PHÁ TOP-K ĐỒ THỊ CON PHỔ BIẾN Phạm Văn Lai1*, Nguyễn Mạnh Hùng2, Nguyễn Doãn Cường1, Phan Việt Anh2 Tóm tắt: Khai phá đồ thị là một nhiệm vụ quan trọng của khai phá dữ liệu đồ thị và nó có rất nhiều ứng dụng trong thực tiễn, ví dụ như: phân tích liên kết web, phân tích mạng xã hội, phát hiện gian lận, phát hiện ngoại lệ, phân tích phân tử hóa học,... Tuy nhiên, khai phá đồ thị con phổ biến có một hạn chế nghiêm trọng khi áp dụng vào thực tế, đó là khó xác định được giá trị ngưỡng minSup phù hợp. Nếu đặt minSup quá cao thì chỉ một ít đồ thị con phổ biến được tìm thấy và như vậy thông tin hữu ích có thể bị bỏ lỡ. Nhưng nếu đặt minSup quá thấp, thời gian khai phá có thể rất lâu và một số lượng rất lớn các đồ thị con phổ biến có thể được tìm thấy. Do đó, việc xác định một giá trị minSup phù hợp để tìm các đồ thị con phổ biến vừa đủ có thể rất tốn thời gian. Thuật toán khai phá Top-K đồ thị con phổ biến đã được đề xuất đề giải quyết hạn chế này. Một số thuật toán khai phá Top-K đồ thị con phổ biến đã được đề xuất; tuy nhiên, hầu hết đều là các thuật toán tuần tự không thể mở rộng trên các bộ dữ liệu lớn. Trong bài báo này, chúng tôi đề xuất một thuật toán song song để khắc phục điểm yếu này. Hiệu suất và khả năng mở rộng của thuật toán đề xuất được minh họa thông qua các thực nghiệm trên hai bộ dữ liệu cụ thể. Từ khóa: Khai phá đồ thị; Khai phá đồ thị con phổ biến; Khai phá Top-K đồ thị con phổ biến. 1. ĐẶT VẤN ĐỀ Khai phá đồ thị con phổ biến là một chủ đề quan trọng trong lĩnh vực khai phá đồ thị. Bài toán này có nhiều ứng dụng trong thực tiễn như: phân tích liên kết web [1], phân tích mạng xã hội [4], phát hiện ngoại lệ [2], phân tích phân tử hoá học [3],... Mục tiêu của khai phá đồ thị con phổ biến (FSM) là tìm ra tất cả các đồ thị con có tần suất xuất hiện lớn hơn hoặc bằng giá trị ngưỡng minSup do người dùng chỉ định. Tuy nhiên, hạn chế của các thuật toán khai phá đồ thị con phổ biến là người dùng thường khó chọn được một giá trị minSup phù hợp. Nếu ngưỡng minSup quá cao, chỉ một vài đồ thị con phổ biến được tìm thấy và như vậy, người dùng có thể bỏ lỡ thông tin có giá trị. Mặt khác, nếu ngưỡng quá thấp, một lượng rất lớn đồ thị con phổ biến được tìm thấy đồng thời yêu cầu thời gian tính toán cao và tốn bộ nhớ. Vì người dùng thường chỉ quan tâm một lượng thông tin nhất định để phân tích, nên họ thường quan tâm đến việc tìm đủ một số đồ thị con phổ biến nào đó. Việc xác định một giá trị minSup phù hợp để tìm ra đủ số lượng các đồ thị con phổ biến rất khó vì nó phụ thuộc vào từng bộ dữ liệu mà người dùng thường không biết. Do đó, người dùng phải tốn rất nhiều thời gian để chạy thuật toán nhiều lần với các giá trị minSup khác nhau đến khi đạt được kết quả mong muốn. Để giải quyết vấn đề này, Li et al. [6] đã đề xuất thuật toán TGP để tìm trực tiếp k đồ thị con đóng phổ biến nhất trong cơ sở dữ liệu đồ thị, trong đó giá trị k do người dùng chọn. Cách tiếp cận này có ưu điểm là trực quan cho người dùng vì người ta có thể chỉ định trực tiếp số lượng đồ thị con phổ biến cần tìm. Tuy nhiên, một vấn đề lớn là TGP tạo ra tất cả các đồ thị con phổ biến và sau đó tìm ra k đồ thị con đóng phổ biến nhất. Việc số lượng đồ thị con phổ biến có thể tăng theo cấp số nhân theo kích thước của đồ thị, dẫn đến cách tiếp cận này không hiệu quả. Để giải quyết các nhược điểm trên, thuật toán TKG[7] đã được đề xuất để khai phá ra chính xác k đồ thị con phổ biến. Đã có một số thuật toán khai phá Top-K đồ thị con phổ biến được đề xuất. Tuy nhiên, Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Hội thảo Quốc gia FEE, 10 - 2020 437 Toán học – Công nghệ thông tin đều là các thuật toán tuần tự, do đó, mất nhiều thời gian tính toán để khai phá các bộ dữ liệu lớn. Cùng với sự phát triển của phần cứng hiện đại, bộ xử lý đa nhân trở thành xu hướng chủ đạo khi Intel và AMD đều đã giới thiệu các chip đa nhân thương mại của họ vào năm 2008 [8], cho phép tính toán song song thuận tiện, dễ dàng hơn. Do đó, bài báo nhằm mục đích đề xuất một thuật toán song song khai phá Top-K đồ thị con phổ biến trên kiến trúc tính toán đa nhân. Phần còn lại của bài báo như sau: Phần 2 trình bày các nghiên cứu liên quan; Phần 3 trình bày thuật toán TKG làm cơ sở cho thuật toán đề xuất; Phần 4 đề xuất thuật toán song song khai phá k đồ thị con phổ biến ParaTKG; Phần 5 trình bày các thực nghiệm nhằm minh chứng hiệu suất của thuật toán đề xuất; Kết luận được trình bày trong phần 6. 2. CÁC NGHIÊN CỨU LIÊN QUAN Khai phá đồ thị con phổ biến là một nhiệm vụ quan trọng trong khai phá dữ liệu đồ thị, mục đích của việc khai phá đồ thị con phổ biến là để tìm ra tất cả đồ thị con có số lần xuất hiện ít nhất là bằng với giá trị ngưỡng tối thiểu do người dùng quy định. Hầu hết các thuật toán FSM bao gồm hai giai đoạn quan trọng: tạo các tập ứng viên và xác định tần suất xuất hiện. Để tính tần suất xuất hiện của một đồ thị con, cần phải xác định số đồ thị trong CSDL có đồ thị con đẳng cấu với đồ thị con này. Bài toán tìm đồ thị con và bài toán duyệt các tập ứng viên là 02 bài toán nền tảng của các thuật toán khai phá đồ thị con phổ biến vì đều có độ phức tạp là NP-khó [9]. Các thuật toán khai phá đồ thị con phổ biến có 02 hướng tiếp cận để sinh tập ứng viên: phương pháp Apriori [11- 13] và phương pháp tăng trưởng mẫu [10, 11, 14, 15]. Để xác định đồ thị con đẳng cấu các thuật toán thường sử dụng canonical adjacency matrix (CAM) [11] and min DFS code [14]. Các thuật toán dựa trên Apriori [11-13] nói chung bao gồm hai bước: tạo ứng viên và kiểm tra đẳng cấu. Các thuật toán dựa trên Apriori là một phần mở rộng của thuật toán Apriori [16]. T ...