Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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ể. | 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. .
