» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:14

Báo xấu

53
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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. Đồ thị có nhãn G = (V, E, LV , LE , l) là đẳng cấu với đồ thị G′ = (V ′ , E ′ , L′V , L′E , l′ ) khi và chỉ khi tồn tại một song ánh f : V → V ′ thỏa mãn: ◦∀u ∈ V, (l(u) = l′ (f (u))), ◦∀u, v ∈ V, ((u, v) ∈ E ⇔ (f (u), f (v)) ∈ E ′ ), ◦∀(u, v) ∈ E, (l(u, v) = l′ (f (u), f (v))) Chúng ta nói rằng G đẳng cấu với G′ và ngược lại. Định nghĩa 2.4. Đồ thị có nhãn G là một đồ thị con đẳng cấu của đồ thị G′ , kí hiệu G ⊆ G′ nếu và chỉ nếu tồn tại một đồ thị con G′′ của G′ mà G đẳng cấu với G′′ . Định nghĩa 2.5. Cho tập các đồ thị D và một ngưỡng σ (0 < σ ≤ 1), độ hỗ trợ (support) của đồ thị G kí hiệu supG là tỉ số của số lượng đồ thị G′ (G′ ∈ D) mà G đồ thị con đẳng ′ ′ ⊆G}| cấu của G′ trên số lượng đồ thị có trong D: supG = |{G ∈D|GD Đồ thị G được gọi là đồ thị con phổ biến nếu và chỉ nếu supG ≥ σ Định nghĩa 2.6. Bài toán khai phá đồ thị con phổ biến là bài toán cho trước CSDLĐT D và ngưỡng hỗ trợ σ(0 < σ ≤ 1), tìm tất cả các đồ thị con phổ biến trong D. 2.2. Thuật toán FSG Thuật toán 2.1: fsg(D, σ) (Phát hiện các đồ thị con phổ biến) (1) F 1 ← xác định tất cả các đồ thị con phổ biến 1 cạnh trong D (2) F 2 ← xác định tất cả các đồ thị con phổ biến 2 cạnh trong D (3) k←3 (4) while F (k−1) 6= ∅ do (5) C k ← f sg − gen(F (k−1) ) (6) for each ứng viên Gk ∈ C k do (7) Gk .count ← 0 (8) for each giao dịch T ∈ D do (9) if ứng viên Gk nằm trong giao dịch T then (10) Gk .count ← Gk .count + 1 (11) F k ← Gk ∈ C k |Gk .count ≥ σ|D| (12) k ←k+1 (13) return F 1 , F 2 , . . . , F (k−2) Thuật toán FSG được trình bày trong Thuật toán 2.1. Hoạt động của thuật toán như sau: Đầu tiên thuật toán sẽ khởi tạo bằng cách liệt kê tất cả các đồ thị 1 và 2 cạnh phổ biến. Sau đó, dựa vào 2 bộ này, nó sẽ bắt đầu lặp việc tính toán 19
Giang Thành Trung và Trần Đăng Hưng chính. Trong mỗi lần lặp, đầu tiên nó tạo ra các đồ thị con ứng viên có kích thước lớn hơn các đồ thị ở bước trước 1 cạnh (dòng 5), điều này có nghĩa là thuật toán sẽ tăng kích thước của các đồ thị con phổ biến bằng cách thêm vào một cạnh tại một thời điểm. Tiếp theo, nó đếm tần suất của mỗi ứng viên đó (từ dòng 8-10) và chỉ giữ lại các ứng viên đáp ứng được độ hỗ trợ σ (dòng 11). Thuật toán chỉ dừng lại khi số lượng ứng viên được phát hiện bằng 0, nghĩa là không có đồ thị con phổ biến kích thước lớn hơn tại thời điểm đó. Để thực hiện Thuật toán 2.1 chúng ta cần xây dựng một số mô-đun hỗ trợ. Chúng tôi trình bày các mô-đun này trong các phần dưới đây. Thuật toán sinh ứng viên (fsg-gen) Sinh ứng viên là một mô-đun quan trọng trong thuật toán FSG, giúp xác định được các đồ thị con có kích thước lớn hơn từ các đồ thị con phổ biến được xác định từ bước trước trước đó. Từ tập ứng viên vừa tạo thuật toán tiếp tục loại bớt các ứng viên không phổ biến (có tần suất xuất hiện < σ|D|) và chỉ giữ lại những ứng viên phổ biến. Trong pha sinh ứng viên thuật toán sẽ tạo một tập các đồ thị con ứng viên kích thước k+1 từ các đồ thị con phổ biến kích thước k, các đồ thị con ứng viên kích thước k + 1 được tạo ra bằng cách ghép 2 đồ thị con phổ biến kích thước k. Hai đồ thị con đủ điều kiện để ghép chỉ khi chúng có cùng đồ thị con kích thước k–1 và 2 đồ thị con này được gọi là “nhân”. Các bước chính trong việc tạo ứng viên đó là: - Xác định nhân: Nhân giữa cặp đồ thị Gki và Gkj có thể xác định bằng cách tạo ra tất cả các đồ thị con kích thước k–1 của Gki bằng cách bỏ đi các cạnh và kiểm tra xem nó có phải đồ thị con của Gkj không. Nếu là đồ thị con của Gkj thì sẽ là nhân chung giữa 2 đồ thị. Lưu ý là giữa 2 đồ thị có thể có nhiều hơn 1 nhân. - Ghép nối : Tiến hành tạo tất cả các tự đẳng cấu có thể của nhân được lựa chọn rồi thực hiện nối 2 đồ thị Gki , Gkj để tạo ra đồ thị ứng viên kích thước k + 1 bằng cách từ nhân và các tự đẳng cấu của nhân ta ghép vào đó 2 cạnh, một của Gki và một của Gkj mà không nằm trong nhân. - Lược bớt: Sử dụng thuộc tính chặn dưới đóng của điều kiện hỗ trợ để loại bỏ một vài các ứng viên đã được tạo ra. Để làm được điều này, với mỗi ứng viên kích thước k + 1, thuật toán sẽ đưa ra các đồ thị con kích thước k bằng cách bỏ bớt một cạnh của đồ thị ứng viên, sau đó kiểm tra xem các đồ thị con đó đã tồn tại trong F k hay chưa. Thuật toán tạo các ứng viên được thể hiện trong Thuật toán 2.2 gồm các bước dưới đây: - Bước 1: Với mỗi cặp đồ thị con phổ biến, thuật toán fsg-gen đi xác định tất cả các nhân chung giữa chúng. - Bước 2: Sau đó với mỗi nhân chung và cặp đồ thị con sẽ gọi đến thuật toán fsg-join để tạo ra tất cả các ứng viên kích thước k + 1 có thể. - Bước 3: Với mỗi ứng viên được tạo ra, đầu tiên thuật toán sẽ kiểm tra ứng 20
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị viên đó đã có trong C (k+1) hay chưa. + Nếu chưa thì fsg-gen xác minh tất cả các đồ thị con k cạnh của nó xem có là đồ thị phổ biến hay không. + Nếu phổ biến, fsg-join sẽ chèn ứng viên được tạo ra vào C (k+1) + Nếu không nó sẽ loại bỏ ứng viên đó + Nếu đã có thì nó bỏ qua ứng viên đó. Thuật toán 2.2: fsg-gen(F k ) (Thuật toán tạo ứng viên) (1) C (k+1) ← ∅ (2) for each cặp Gki , Gkj ∈ F k , i ≤ j mà cl(Gki ≤ Gkj ) do (3) H(k−1) ←H (k−1) | một nhân H (k−1) chung giữa Gki và Gkj (4) for each H (k−1) ∈ H(k−1) do (5) {B (k+1) là một tập các ứng viên dự kiến} (6) B (k+1) ← f sg − join(Gki , Gkj , H (k−1) ) for each Gj ∈ B (k+1) do (k+1) (7) (8) {kiểm tra thuộc tính chặn dưới đóng} (9) f lag ← true for each cạnh el ∈ Gj do (k+1) (10) (k+1) (11) Hlk ← Gj − el (12) if Hlk liên thông và H k 6∈ F k then (13) f lag ← f alse (14) break (15) if f lag = true then (k+1) (16) C (k+1) ← C (k+1) ∪Gj (17) return C (k+1) Trong thuật toán khởi tạo các đồ thị ứng viên có một bước quan trọng đó là ghép nối 2 đồ thị có chung nhân. Không giống như việc ghép nối các tập mục phổ biến, 2 tập mục phổ biến kích thước k khi được ghép nối sẽ chỉ dẫn đến duy nhất một tập mục kích thước k + 1 thì việc ghép nối 2 đồ thị con kích thước k sẽ dẫn tới nhiều đồ thị con kích thước k + 1 bởi các nguyên nhân sau: - Đầu tiên đó là trường hợp sự khác nhau giữa các lõi chung và 2 đồ thị con có thể là một đỉnh có nhãn giống nhau trong cả 2 đồ thị con kích thước k. Khi đó nếu ghép nối nó sẽ tạo ra 2 đồ thị con kích thước k + 1 khác nhau. Ví dụ trong Hình 2.1 là khi đồ thị G4a và G4b kết nối sẽ tạo ra 2 đồ thị G5a và G5b tương ứng. Hình 2.1. Khi kết nối bởi các nhãn đỉnh - Thứ hai đó là có thể nhân của mỗi đồ thị con kích thước k có nhiều tự đẳng cấu, 21
Giang Thành Trung và Trần Đăng Hưng và mỗi tự đẳng cấu sẽ tạo ra một ứng viên k + 1 khác nhau. Trong trường hợp xấu nhất nếu nhân là một đồ thị clique không được gán nhãn thì số lượng tự đẳng cấu là k!. Ví dụ trong Hình 2.2, nhân là hình vuông có 4 đỉnh được gán nhãn sẽ có 4 tự đẳng cấu thể hiện trong 3 ứng viên kích thước 6. Hình 2.2. Kết nối khi có đa đẳng cấu của nhân - Thứ ba là khi 2 đồ thị con phổ biến có chung nhiều nhân. Ví dụ như trong Hình 2.3. Hình 2.3. Kết nối khi có đa nhân Thuật toán ghép nối các đồ thị con kích thước k được thể hiện trong Thuật toán 2.3. Cho 1 cặp đồ thị con kích thước k, Gk1 và Gk2 và một nhân kích thước k-1. Kết quả trả ra của thuật toán là một tập các đồ thị ứng viên kích thước k + 1. Hoạt động cụ thể của thuật toán như sau: - Bước 1: fsg-join tiến hành xác định 2 cạnh, 1 trong Gk1 và 1 trong Gk2 sao cho chúng không nằm trong nhân. - Bước 2: fsg-join tạo ra tất cả các tự đẳng cấu của nhân. - Bước 3: với mỗi tập 2 cạnh, nhân và tự đẳng cấu, fsg-join tích hợp 2 đồ thị con Gk1 và Gk2 vào một ứng viên kích thước k + 1. 22
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Thuật toán 2.3: fsg-join(Gk1 , Gk2 , H (k−1) ) (Thuật toán ghép nối 2 đồ thị) (1) e1 ← cạnh chỉ xuất hiện trong Gk1 ,nhưng không có trong H (k−1) (2) e2 ← cạnh chỉ xuất hiện trong Gk2 ,nhưng không có trong H (k−1) (3) M ← tạo tất cả các tự đẳng cấu của H (k−1) (4) B (k+1) = ∅ (5) for each tự đẳng cấu ϕ ∈ M do (6) B (k+1) ← B (k+1) ∪ tất cả các đồ thị ứng viên k+1 được tạo ra từ một tập của e1 , e2 , H (k−1) và ϕ (7) return B (k+1) Để giảm thiểu thời gian xác định nhân giữa 2 đồ thị con phổ biến chúng ta lưu giữ lại một số thông tin từ tập các đồ thị con phổ biến. Cụ thể, đối với mỗi đồ thị con phổ biến kích thước k chúng ta lưu trữ các nhãn định danh của đồ thị con phổ biến kích thước k-1 của nó, khi đó việc xác định nhân bằng cách xác định giao của các nhãn định danh. Độ phức tạp của phương pháp này là bình phương số lượng các đồ thị con phổ biến kích thước k. 2.3. Cài đặt và thử nghiệm thuật toán FSG Thuật toán được cài đặt hướng đối tượng bằng ngôn ngữ Java dựa trên việc xây dựng các lớp. Vì giới hạn của bài báo, nên phần này chúng tôi chỉ cung cấp một số thông tin về nội dung các lớp. Tổ chức dữ liệu vào/ra - Dữ liệu vào được lưu trong tệp tin văn bản và có cách tổ chức như sau: Loại dòng Định dạng Giải thích ý nghĩa Chú thích # Ký hiệu báo hiệu chú thích, chương trình sẽ bỏ qua những dòng có ký hiệu này ở đầu Số đỉnh vn Chứa số đỉnh có trong đồ thị Đỉnh v Mã của đỉnh và nhãn của đỉnh đó (mã là số nguyên không âm, nhãn là chuỗi ký tự không dấu) Giao dịch t Bắt đầu 1 giao dịch, là số cạnh trong giao dịch đó Cạnh u Mã của đỉnh đầu và đỉnh cuối của cạnh và nhãn của cạnh đó Ví dụ: Cho đồ thị được biểu diễn như hình bên trái, thì dữ liệu vào sẽ được biểu diễn như hình bên phải dưới đây 23
Giang Thành Trung và Trần Đăng Hưng Đồ thị mẫu Ví dụ về cách biểu diễn dữ liệu đồ thị - Tệp dữ liệu chứa kết quả thu được sau khi chạy thuật toán được lưu trong tệp tin văn bản và có cách tổ chức như sau: Loại dòng Định dạng Giải thích ý nghĩa Chú thích # Ký hiệu báo hiệu chú thích, chương trình sẽ bỏ qua những dòng có ký hiệu này ở đầu Kích thước size Kích thước của đồ thị con phổ biến tìm được Giao dịch sg - Bắt đầu 1 đồ thị con phổ biến bao gồm - các mã đỉnh đầu, cuối và nhãn cạnh. *- Các cạnh được phân biệt nhau bởi dấu - * *. . . Ví dụ về tệp biểu diễn danh sách các đồ thị con phổ biến tìm được 24
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Thiết kế các lớp chính - Gói Graph bao gồm các lớp để biểu diễn các đối tượng đồi thị. Gói này gồm các lớp VertexLabel, EgdeLabel, Graph và CandidateGraph. + Lớp VertexLabel : sử dụng để biểu diễn đối tượng đỉnh Các thuộc tính/phương thức Ý nghĩa - int ID Biểu diễn mã của đỉnh - String Label Biểu diễn nhãn của đỉnh + void setID(String pID) Phương thức thiết lập mã đỉnh + void setLabel(String pLabel) Phương thức thiết lập nhãn đỉnh + int getID() Phương thức đọc mã đỉnh + string getLabel() Phương thức đọc nhãn đỉnh + Lớp EdgeLabel : sử dụng để biểu diễn đối tượng cạnh Các thuộc tính/phương thức Ý nghĩa - int firstVertex Biểu diễn mã đỉnh thứ nhất - int lastVertex Biểu diễn mã đỉnh thứ hai - String Label Biểu diễn nhãn của cạnh Phương thức thiết lập mã đỉnh + void setFirstVertex(int pFV) thứ nhất Phương thức thiết lập mã đỉnh + void setLastVertex(int pLV) thứ hai + void setLabel(String pLabel) Phương thức thiết lập nhãn cạnh Phương thức đọc mã đỉnh thứ + int getFirstVertex() nhất + int getLastVertex() Phương thức đọc mã đỉnh thứ hai + String getLabel() Phương thức đọc nhãn cạnh + Lớp Graph: sử dụng để biểu diễn các đối tượng đồ thị Các thuộc tính/phương thức Ý nghĩa - Int numOfVer Biểu diễn số đỉnh của đồ thị - Int numOfEdge Số cạnh của đồ thị - VertexLabel[] lV = new Ver- Danh sách các nhãn đỉnh texLabel[1000] 25
Giang Thành Trung và Trần Đăng Hưng - EdgeLabel[] lE = new EdgeLa- Danh sách các nhãn cạnh bel[1000] - boolean[] fV = new Biến đánh dấu khi hoán vị các boolean[1000] đỉnh - String[][] Matrix = new Ma trận kề tương ứng của đồ thị String[100][100] Mã của đồ thị (hỗ trợ việc tạo - String code Canonical Label) - String cL Nhãn tiêu chuẩn của đồ thị + Graph() Phương thức khởi tạo đối tượng + Graph(int pNumOfVertex, int Phương thức khởi tạo đối tượng pNumOfEdge) với 2 tham số + void GenerateAdjacencyMa- Phương thức tạo ma trận kề trix() + void SetCode() Phương thức sinh mã của đồ thị Phương thức sinh Canonical La- + void SetCanonicalLabel() bel của đồ thị + Lớp CandidateGraph: kế thừa từ lớp Graph và được sử dụng để biểu diễn các đối tượng đồ thị ứng viên được sinh ra đồng thời biểu diễn các đồ thị phổ biến được xác định Các thuộc tính/phương thức Ý nghĩa Biểu diễn nhãn tiêu chuẩn của đồ - String cL1 thị con thứ nhất sinh ra đồ thị hiện tại Biểu diễn nhãn tiêu chuẩn của đồ - String cL2 thị con thứ hai sinh ra đồ thị hiện tại + void setCL1(String pCL1) Phương thức thiết lập cL1 + void setCL2(String pCL2) Phương thức thiết lập cL2 + String getCL1() Phương thức đọc giá trị của cL1 + String getCL2() Phương thức đọc giá trị của cL2 - Gói Process bao gồm các lớp xử lý đồ thị: + Lớp GetInput: đọc dữ liệu trong tệp tin ở bộ nhớ ngoài 26
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Các thuộc tính/phương thức Ý nghĩa Biểu diễn đường dẫn của tệp tin - String fileName chứa dữ liệu vào Phương thức thiết lập đường dẫn + void setfileName(String pFN) cho tệp tin vào Phương thức đọc dữ liệu trong + void ReadFile(String File- tệp tin và biểu diễn vào mảng các Name, Graph graph[], int[] tnum) đồ thị + Lớp ProcessGraph: đọc dữ liệu trong tệp tin ở bộ nhớ ngoài Các thuộc tính/phương thức Ý nghĩa + boolean isomorphism(Graph Xác định tính đẳng cấu của 2 đồ g1, Graph g2) thị + string compareCode(String So sánh 2 đoạn mã để xác định paraCode1, String paraCode2) mã có thứ tự từ điển lớn hơn Xác định các hoán vị đỉnh có thể + void PermuteIdentifier() của của 1 đồ thị để sinh ra mã tương ứng - Gói Main bao gồm các lớp sau: + Lớp FSG: bao gồm các phương thức cài đặt thuật toán FSG Các thuộc tính/phương thức Ý nghĩa Biểu diễn các đồ thị đọc được từ - Graph[] graph tệp tin vào - int[] tn Biểu diễn tổng số giao dịch Biểu diễn các tập đồ thị ứng viên - CandidateGraph[][] canGraph được sinh ra - CandidateGraph[][] fre- Biểu diễn các tập đồ thị phổ biến quentSubgraph được xác định Phương thức đọc dữ liệu từ tệp + void Input() tin đầu vào Phương thức chạy thuật toán + void FSG() FSG 27
Giang Thành Trung và Trần Đăng Hưng Phương thức khởi tạo tập ứng + void GenerateFirstCandidate() viên 1, 2 cạnh Phương thức khởi tạo tập ứng + void FSG_Gen(int k) viên kích thước k ≥ 3 + graph[] coreIdentifier(Graph Phương thức xác định nhân của 2 g1, Graph g2) đồ thị + void FSG_Join(Graph g1, Phương thức kết nối 2 đồ thị để Graph g2, Graph gcore) tạo ra 1 ứng viên Kết quả thực nghiệm Chúng tôi đã cài đặt hoàn chỉnh chương trình và thử nghiệm trên hai tập dữ liệu nhỏ với mục đích minh họa. Tập dữ liệu 1 : Gồm 3 đồ thị có cấu trúc như hình vẽ dưới đây: - Mô hình cơ sở dữ liệu đồ thị đầu - File dữ liệu vào tương ứng với vào: tập dữ liệu đồ thị 1 - File kết quả sau khi chạy chương trình với ngưỡng support σ=50 - Biểu diễn kết quả bằng mô hình: 28
Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị + Kích thước 3: + Kích thước 4: Tập dữ liệu 2 : Gồm 4 đồ thị có cấu trúc như hình vẽ dưới đây - Mô hình các đồ thị giao dịch đầu vào: - File dữ liệu vào tương ứng với tập dữ liệu đồ thị 2: - File kết quả sau khi chạy chương trình với ngưỡng support σ=70 - Biểu diễn bằng mô hình: + Kích thước 3: + Kích thước 4: 3. Kết luận Trong bài báo này chúng tôi đã tìm hiểu và cài đặt một thuật toán hiệu quả trong việc khai phá các đồ thị con phổ biến. Thuật toán này dựa trên tư tưởng của thuật toán Apriori tìm tập mục phổ biến. Tuy nhiên, khi thực hiện với dữ liệu đồ thị thì việc lưu trữ và xử lý dữ liệu khó khăn và phức tạp hơn. Chúng tôi đã đưa ra cách biểu diễn các đối tượng bằng lớp và sử dụng lập trình hướng đối tượng để cài 29
Giang Thành Trung và Trần Đăng Hưng đặt thuật toán. Chúng tôi cũng đã thử nghiệm chương trình trên hai bộ dữ liệu tự tạo với số lượng đồ thị tương đối nhỏ. Trong thời gian tới, chúng tôi sẽ tiến hành chạy thử nghiệm trên dữ liệu biểu hiện gien với số lượng lớn các đồ thị. TÀI LIỆU THAM KHẢO [1] Zaki M. J., 2002. Efficiently mining frequent trees in a forest. In Proc. of The 8th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 71-80. [2] Dehaspe L., Toivonen H., and King R. D., 1998. Finding frequent substructures in chemical componuds. Proc. of the 4th International Conference on Knowledge Discovery and Data Mining, 30–6. [3] Yan X., Philip S., Jiawei H., 2004. Graph indexing: a frequent structure-based approach. In Proc. of The 2004 ACM SIGMOD International conference on Man- agement of Data, 335-346. [4] Agrawal R. and Srikant R., 1994. Fast algorithms for mining association rules. In Proc. of the 20th International Conference on Very Large Databases (VLDB), 487–499. [5] Inokuchi A., Washio T., and Motoda H., 2000. An apriori-based algorithm for mining frequent substructures from graph data. In Proc. of the 4th European Conference on Principles and Practices of Knowledge Discovery in Databases (PKDD), 13–23. [6] Kuramochi M. and Karypis G., 2004. Frequent subgraph discovery. IEEE Trans- actions on Knowledge and Data Engineering, 16(9), 1038 – 1051. [7] Yan X. and Han J., 2002. gSpan: Graph-based substructure pattern mining. In Proc. of The 2002 IEEE International Conference on Data Mining, 120-125. [8] Borgelt C. and Berhold M. R., 2002. Mining molecular frag-ments: Finding rel- evant substructures of molecules. In Proc. of The 2002 IEEE International Con- ference on Data Mining, 51-58. ABSTRACT A frequent subgraph mining algorithm in graph databases The problem of finding frequent substructures in a structural dataset has been applied in many fields. Previously, several difference algorithms were proposed. However, due to the complexity of the structural data, these algorithms faced the challenge of computational cost. In this paper, we introduce an efficient algorithm for mining subgraphs from a graph database, namely FSG. This algorithm is an extension of the Apriori algorithm with some new modules added in the candidate generation step. We implemented FSG using Java programming language. 30

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.