Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị

Trong bài báo này, các tác giả giới thiệu một thuật toán hiệu quả cho việc tìm kiếm các đồ thị con trong một cơ sở dữ liệu đồ thị, thuật toán FSG. Thuật toán này dựa trên tư tưởng của thuật toán Apriori nhưng pha sinh ứng viên đã được cải tiến để phù hợp với dữ liệu đồ thị. Chúng tôi đã cài đặt thuật toán này theo kỹ thuật lập trình hướng đối tượng bằng ngôn ngữ Java.
Nội dung trích xuất từ tài liệu:
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị JOURNAL OF SCIENCE OF HNUE Natural Sci., 2012, Vol. 57, No. 3, pp. 17-30 MỘT THUẬT TOÁN KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN TRONG DỮ LIỆU ĐỒ THỊ Giang Thành Trung Trường Đại học Tây Bắc Trần Đăng Hưng(∗) Trường Đại học Sư phạm Hà Nội (∗) E-mail: hungtd@hnue.edu.vn Tóm tắt. Bài toán tìm các cấu trúc con lặp lại nhiều lần trong dữ liệu có cấu trúc được ứng dụng trong rất nhiều lĩnh vực. Nhiều thuật toán khác nhau đã được đề xuất. Tuy nhiên, do sự phức tạp của dữ liệu có cấu trúc nên các thuật toán thường gặp phải các thách thức về tính toán. Trong bài báo này, chúng tôi giới thiệu một thuật toán hiệu quả cho việc tìm kiếm các đồ thị con trong một cơ sở dữ liệu đồ thị, thuật toán FSG. Thuật toán này dựa trên tư tưởng của thuật toán Apriori nhưng pha sinh ứng viên đã được cải tiến để phù hợp với dữ liệu đồ thị. Chúng tôi đã cài đặt thuật toán này theo kỹ thuật lập trình hướng đối tượng bằng ngôn ngữ Java. Từ khóa: Khai phá dữ liệu, đồ thị con phổ biến, Apriori, FSG. 1. Mở đầu Khai phá các mẫu hình (pattern) lặp lại nhiều lần trong dữ liệu có cấu trúc (như đồ thị, cây) thu hút được nhiều sự chú ý của các nhà nghiên cứu vì được ứng dụng trong nhiều lĩnh vực khác nhau [1-3]. Các mẫu hình lặp lại nhiều lần có thể giúp chúng ta hiểu sâu sắc hơn về mối quan hệ giữa các phần tử được mô hình hóa và đồng thời đây cũng là điểm khởi đầu cho các thuật toán khai phá dữ liệu cơ bản như phân cụm và phân lớp. Trong số các loại dữ liệu có cấu trúc, đồ thị được sử dụng trong nhiều lĩnh vực nhất. Chẳng hạn, trong sinh học đồ thị được dùng để mô tả mối quan hệ giữa các phần tử cơ bản (protein, gene, RNA). Trong hóa học phân tích, đồ thị được dùng để mô tả cấu trúc ba chiều của các phân tử. Ngoài ra, đồ thị còn được dùng để biểu diễn dữ liệu web, dữ liệu text, vv. Cho đến nay, có khá nhiều các thuật toán được đề xuất cho việc khai phá các đồ thị con phổ biến từ một cơ sở dữ liệu đồ thị (CSDLĐT). Đồ thị con là một đồ thị thu được từ đồ thị ban đầu bằng cách loại bỏ một số đỉnh và một số cạnh. Đồ thị con phổ biến là đồ thị con có số lần xuất hiện trong một CSDLĐT lớn hơn một ngưỡng cho trước. Hầu hết các thuật toán tìm đồ thị con phổ biến đều phải đối mặt với hai thách thức về tính toán: (1) đồ thị con đẳng cấu: xác định một đồ thị con 17 Giang Thành Trung và Trần Đăng Hưng của một đồ thị xuất hiện trong các đồ thị khác; (2) liệt kê một cách hiệu quả tất cả các đồ thị con phổ biến: vì số lượng các đồ thị con sẽ tăng lên theo kích thước của chính nó và kích thước của CSDLĐT, do vậy để làm việc được với các CSDLĐT lớn và có cấu trúc phức tạp cần phải có các thuật toán khai phá mẫu phổ biến hiệu quả. Nhìn chung, có thể chia các thuật toán khai phá đồ thị con phổ biến thành hai nhóm. Nhóm 1, gồm các thuật toán sử dụng chiến lược tìm kiếm theo chiều rộng theo kiểu thuật toán Apriori [4] để liệt kê các đồ thị con. Hai trong số các thuật toán này là AGM [5] và FSG [6]. AGM được đưa ra bởi Inokuchi và đồng nghiệp, FSG được đưa ra bởi Kuramochi và đồng nghiệp. Các thuật toán này đều dựa trên các đồ thị con phổ biến hiện có, rồi “sinh” ra các ứng viên tiếp theo bằng cách thêm cạnh hoặc đỉnh mới. Tại thời điểm xuất phát, thuật toán coi đồ thị con chỉ có 1 đỉnh hoặc 1 cạnh. Điểm khác nhau giữa các thuật toán này là phương thức “sinh” ra các ứng viên (candidate) mới từ các đồ thị con phổ biến hiện thời. Trong khi AGM sử dụng phương thức tạo ứng viên dựa trên các đỉnh và gia tăng kích thước của đồ thị con bằng cách thêm 1 đỉnh mới. FSG lựa chọn chiến lược tạo ứng viên dựa trên các cạnh để gia tăng kích thước của đồ thị con bằng cách thêm mới một cạnh. Chi tiết của các thuật toán này sẽ được chúng tôi trình bày trong các phần tiếp theo. Nhóm 2, gồm các thuật toán sử dụng chiến lược tìm kiếm theo chiều sâu để tìm các ứng viên đồ thị con phổ biến. Hai thuật toán tiêu biểu cho nhóm này là gSpan [7] và thuật toán của Borgelt [8]. Các thuật toán này đều tìm các đồ thị con liên thông phổ biến trong CSDLĐT nhưng khác nhau ở cách sinh ra các đồ thị con ứng viên. Trong gSpan [7], một đồ thị con phổ biến G được sử dụng để sinh ra các đồ thị con ứng viên G′ bằng cách chọn một đỉnh v thuộc G và thêm vào cạnh (v, w), trong đó w thuộc G hoặc không thuộc G. Ngược lại, thuật toán trình bày trong [8] không sinh ra các ứng viên mà thay vào đó là lưu giữ tất cả các đẳng cấu có thể có của đồ thị con phổ biến hiện thời. Trong bài báo này, chúng tôi đã tìm hiểu và trình bày một thuật toán hiệu quả của nhóm 1, thuật toán FSG [6]. Sau đó cài đặt và tiến hành thử nghiệm trên cơ sở dữ liệu đồ thị tự tạo, mỗi file dữ liệu mô tả một tập các đồ thị. Chương trình được chúng tôi cài đặt theo kỹ thuật lập trình hướng đối tượng với ngôn ngữ Java và có thể chạy được trên cả nền Windows và Linux. 2. Nội dung nghiên cứu 2.1. Một số khái niệm Để thuận lợi cho việc theo dõi các khái niệm về sau, trong phần này chúng tôi cung cấp một số khái niệm cơ bản, được dùng nhiều lần trong bài báo. Định nghĩa 2.1. Một đồ thị có nhãn G là một bộ gồm 5 phần tử G = (V, E, LV , LE , l) trong đó V là tập các đỉnh, E là tập các cạnh vô hướng, LV và LE là tập nhãn của các đỉnh và các cạnh, các ánh xạ l : V → LV và l : E → LE . 18 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Định nghĩa 2.2. Đồ thị có nhãn G = (V, E, LV , LE , l) là đồ thị con của đồ thị G′ = (V ′ , E ′ , L′V , L′E , l′ ) nếu và chỉ nếu: ◦V ⊆ V ′ ◦∀u ∈ V, (l(u) = l′ (u)), ◦E ⊆ E ′ , ◦∀(u, v) ∈ E, (l(u, v) = l′ (u, v)) Định nghĩa 2.3. Đồ ...