zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

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

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

Báo xấu

64
lượt xem 3
download

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

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ể.

Chủ đề:

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

Lưu

Nội dung Text: 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]. Trong khi thuật toán Apriori làm việc với các tập phần tử, các thuật toán FSM làm việc với các đồ thị. Trong bước đầu tiên, các ứng cử viên kích thước k được tạo ra từ các đồ thị con phổ biến kích thước k-1 và kiểm tra xem chúng có phổ biến hay không. Các thuật toán dựa trên Apriori thường sử dụng tính chất đóng đề giảm số lượng tập ứng viên, thu hẹp không gian tìm kiếm. Tính chất này cụ thể là: nếu một đồ thị con không phổ biến thì tất cả các đồ thị chứa nó cũng sẽ không phổ biến.Vì vậy, có thể cắt tỉa các tập ứng viên chứa đồ thị con này, điều này giúp thu hẹp không gian tìm kiếm đặc biệt trong trường hợp có các đồ thị con phổ biến kích thước lớn. Cách tiếp cận thứ hai là thực hiện tăng trưởng mẫu và cách tiếp cận này chính là phần mở rộng của thuật toán tăng trưởng FP [17]. Mục đích của các thuật toán dựa trên tăng trưởng mẫu [10, 11, 14, 15] là tìm tất cả các mẫu phổ biến mà không sinh ứng cử viên. Cách tiếp cận này dựa trên phương pháp chia để trị. Thay vì tạo ra tất cả các đồ thị con ứng cử viên, một cạnh mới được thêm vào mọi vị trí có thể của đồ thị con phổ biến hiện thời. Tuy nhiên, cách tiếp cận này có một nhược điểm là cùng một đồ thị con có thể được tạo ra nhiều lần trong khi thêm vào một cạnh mới. Vấn đề này được khắc phục bằng chiến lược mở rộng bên phải cùng (rightmost path) [10, 14]. Với mỗi ứng cử viên, thuật toán AGM [12] sẽ duyệt lại toàn bộ dữ liệu để xác định tần suất xuất hiện. Thuật toán FSG [13] sử dụng nhãn chính tắc để tạo xác định đồ thị con đẳng cấu. Để tạo nhãn chính tắc của đồ thị, thuật toán này sử dụng một số phương pháp heuristic. Tuy nhiên, các phương pháp heuristic này yêu cầu một số lượng lớn các nhãn cạnh khác nhau để xác định duy nhất một đồ thị bằng nhãn chính tắc. Thuật toán FSG vượt trội hơn thuật toán AGM về thời gian tính toán [13]. 438 P. V. Lai, …, P. V. Anh, “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 gSpan [14] xây dựng cây mã DFS thay thế việc sinh các tập ứng viên và sử dụng mã DFS tối thiểu để xác định đồ thị con đẳng cấu. Vì thế, thuật toán gSpan yêu cầu sử dụng ít bộ nhớ hơn so với FSG và vượt trội hơn FSG [14]. Thuật toán FFSM đề xuất hai phương thức mới để tạo ứng viên: FFSMjoin và FFSM-extension và sử dụng CAM để xác định đồ thị con đẳng cấu. FFSM chỉ nhanh hơn thuật toán gSpan trên tập dữ liệu IC93 [11]. Thuật toán MOFA [15] tạo ra nhiều bản sao. Vì thế, các đồ thị con phổ biến được tạo ra có thể không thực sự phổ biến. Thuật toán gSpan và FFSM vượt trội hơn thuật toán MOFA về thời gian tính toán[18]. Mặc dù đã có nhiều thuật toán được đề xuất nhưng các thuật toán khai phá đồ thị con phổ biến có một hạn chế nghiêm trọng, đó là người dùng thường khó chọn được một giá trị minSup phù hợp. Để giải quyết vấn đề này, bài toán khai phá Top-K đồ thị con phổ biến đã được đề xuất. Một số thuật toán điển hình khai phá Top-K đồ thị con phổ biến là: thuật toán TGP[6] và thuật toán TKG[7] - đây đều là các thuật toán tuần tự, do đó, đòi hỏi thời gian lớn để khai phá các bộ dữ liệu lớn. Với sự phát triển mạnh mẽ của phần cứng, các bộ xử lý (CPU) đa nhân, GPU và mô hình Map/Reduce đã trở thành những nền tảng cho tính toán song song [20]. Một số thuật toán song song đã được phát triển để giải quyết bài toán khai phá đồ thị con phổ biến. Năm 2014, Lin và các đồng nghiệp đã phát triển thuật toán song song khai phá đồ thị con phổ biến dựa trên mô hình Map/Reduce [23], Kessl và các đồng nghiệp [22] đã đề xuất thuật toán khai phá các mẫu cấu trúc con dựa trên đồ thị dựa trên nền tảng GPU và đã có khá nhiều các thuật toán song song khai phá đồ thị con phổ biến dựa trên kiến trúc song song sử dụng mô hình bộ nhớ chia sẻ được đề xuất [21, 24]. Vì là bài toán mới cho nên hiện nay chưa có nghiên cứu nào về song song hoá thuật toán khai phá Top-K đồ thị con phổ biến. Phần tiếp theo, bài báo sẽ trình bày chi tiết thuật toán TKG và đề 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. 3. THUẬT TOÁN TKG Trong phần này, bài báo trình bày tóm tắt thuật toán TKG (Top-K Graph miner) vì nó là thuật toán cơ sở để chúng tôi đề xuất thuật toán song song ParaTKG. Định nghĩa 1 (Đồ thị có gán nhãn). Một đồ thị có gán nhãn G là một bộ năm thành phần G = (V, E, LV, LE, φV và φE). Trong đó: V, E, LV và LE lần lượt là các tập cạnh, tập đỉnh, tập nhãn đỉnh và tập nhãn cạnh; φV và φE lần lượt là các hàm ánh xạ các đỉnh và cạnh tới nhãn của chúng (φV: V→ LV và φE: E→ LE). Định nghĩa 2 (Cơ sở dữ liệu đồ thị). Một cơ sở dữ liệu đồ thị GD = {G1, G2, ..., Gn} được định nghĩa là một tập hợp n đồ thị có gán nhãn. Định nghĩa 3 (Đồ thị đẳng cấu). Cho đồ thị có gán nhãn Gx = (Vx, Ex, LxV, LxE, φxV, φxE) và một đồ thị có gán nhãn khác Gy = (Vy, Ey, LyV, LyE, φyV, φyE). Người ta nói rằng, đồ thị Gx là đẳng cấu với Gy nếu tồn tại một ánh xạ f: Vx→Vy thoả mãn hai điều kiện sau: Điều kiện 1: Đối với bất kỳ đỉnh v∈Vx thì LxV(v) = LyV (f(v)). Điều kiện 2: Đối với cặp đỉnh (u, v)∈Ex bất kỳ thì (f (u), f (v)) ∈ Ey và LxE (u, v) = LyE (f (u), f (v)). Để kiểm tra xem một đồ thị con có xuất hiện trong một đồ thị hay không, mối quan hệ đồ thị con đẳng cấu và khái niệm hỗ trợ được định nghĩa như sau. Định nghĩa 4 (Đồ thị con đẳng cấu). Cho hai đồ thị Gx = (Vx, Ex, LxV, LxE, φxV, φxE) và Gz = (Vz, Ez, LzV, LzE, φzV, φzE). Đồ thị Gx được xác định là xuất hiện trong đồ thị Gz, hoặc Gx là một đồ thị con đẳng cấu của Gz, nếu Gx là đẳng cấu với một đồ thị con Gy ⊆ Gz. 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 439
Toán học – Công nghệ thông tin Mục tiêu của khai phá đồ thị con phổ biến là tìm ra tất cả các đồ thị con có độ hỗ trợ lớn hơn hoặc bằng minSup. Độ hỗ trợ được định nghĩa dựa trên khái niệm đồ thị đẳng cấu và đồ thị con đẳng cấu. Định nghĩa 5. Cho một cơ sở dữ liệu đồ thị GD. Độ hỗ trợ (tần suất xuất hiện) của một đồ thị con Gx trong GD được định nghĩa là sup(Gx) = |{g|g∈GD và Gx đẳng cấu với đồ thị g}|. Định nghĩa 6 (Khai phá đồ thị con phổ biến). Cho một giá trị ngưỡng minSup>0 do người dùng xác định và một cơ sở dữ liệu đồ thị GD. Bài toán khai phá đồ thị con phổ biến tìm tất cả các đồ thị con có độ hỗ trợ không nhỏ hơn minSup. Định nghĩa 7 (Khai phá Top-k đồ thị con phổ biến). Cho một giá trị tham số k ≥ 1 được người dùng xác định và một cơ sở dữ liệu đồ thị GD. Bài toán khai phá Top-k đồ thị con phổ biến là đi tìm một tập T gồm k đồ thị con sao cho độ hỗ trợ của chúng lớn hơn hoặc bằng với bất kỳ đồ thị con nào khác không có trong T. Định nghĩa 8 (Mở rộng đường dẫn bên phải cùng). Thực hiện tìm kiếm theo chiều sâu trên đồ thị bằng việc sử dụng một ngăn xếp. Các đỉnh trong ngăn xếp tạo thành đường dẫn bên phải cùng trong đồ thị và đỉnh hiện thời đang được xử lý được gọi là đỉnh bên phải cùng. Việc mở rộng đường dẫn bên phải cùng thực hiện hai loại mở rộng: mở rộng tiến (forward extensions) và mở rộng lùi (backword extensions). Mở rộng lùi được thực hiện trước mở rộng tiến. Đối với mở rộng tiến, đỉnh bên phải cùng được xem xét mở rộng trước, sau đó đến các đỉnh nằm trong đường dẫn bên phải cùng. Định nghĩa 9 (Cạnh mở rộng). Cho một cạnh giữa hai đỉnh vi, vj và một hàm gán nhãn φ. Một bộ 5 gồm (vi, vj, φ(vi), φ(vj), φ(vi vj)) biểu diễn cạnh, nhãn đỉnh của 2 đỉnh và nhãn của cạnh được gọi là cạnh mở rộng. Định nghĩa 10 (mã DFS). Mã DFS của một đồ thị là một chuỗi các cạnh mở rộng, được sắp xếp theo thứ tự tìm kiếm theo chiều sâu. Định nghĩa 11. (Thứ tự tổng thể của các cạnh mở rộng). Gọi t1 và t2 là hai cạnh mở rộng: t1 = (vi, vj, L(vi), L(vj), L(vi, vj)) t2 = (vx, vy, L (vx), L(vy), L(vx, vy)) Cạnh t1 được cho là nhỏ hơn t2 khi và chỉ khi: i) (vi, vj)
Nghiên cứu cứu khoa học công nghệ kiếm. ếm. Ban đầu Qk và Qc đều ều được đ ợc khởi tạo bằng k đồ thị con 1 cạnh đơn đơn có đđộộ hỗ trợ cao nhất. Tiếp theo, thuật toán TKG sẽ thực hiện lặp tr nhất. ên hàng đđợi trên ợi Qc. Cụ Cụ thể, trong khi mà mà đợi Qc khác rỗng, hàng đợi rỗng, đồ thị g có đđộ ộ hỗ trợ cao nhất trong Qc đượcđược lấy ra vvàà đđồ ồ thị mở rộng ộng g' được đ ợc mở rộng từ đồ thị g theo đỉnh thuộc đường đ ờng dẫn phải cùngcùng nhất, nhất, nếu đồ thị mở rộng ộng g' có độ hỗ trợ không nhỏ hhơn ơn minSup thì thì g' sẽ sẽ đđược ợc đẩy vào vào hàng đợi đợi Qk và Qc, ngưỡng minSup được ngưỡng đ ợc xác địnhđịnh lại. Bảng 1. Thuật Bảng Thuật toán TKG. Đầu vào : CSDL đồ ầu vào đồ thị GD, giá trị ng ngưưỡng ỡng k. ầu ra: k đồ Đầu đồ thị con phổ biến 1. Hàng đợiđợi ưu tiên Qk đểể lưu lưu tr trữ ữ k đồ thị con phổ biến, trong đó,đó đồồ thị con có độ hỗ trợ nhỏ hhơn trợ thì có độộ ưu tiên cao hơn. Qk đư ơn thì được ợc khởi tạo bằng k độ thị con có cạnh đđơn 1 cạnh ơn có độđộ hỗ trợ lớn nhất. 2. Hàng đợiđợi ưu tiên Qc đểể lưu lưu tr trữ ữ các đồ thị con ứng vi viên ên cho việc việc mở rộng tiếp theo, trong đó đó, đồ ồ thị con có độ hỗ trợ lớn hơnhơn thì có độộ ưu tiên cao hơn. Qc được ợc khởi tạo bằng k độ thị con có 1 cạnh đơn khởi đơn có đđộ ộ hỗ trợ lớn nhất. 3. được gán bằng độ hỗ trợ của đồ thị con trong đầu hhàng minSup được àng đợi đợi của Qc 4. while (Q(Qc is not empty) empty) { 5. g = Qc. pop(); 6. eps= rightMostP athExtensions(g, GD); 7. foreach (t; sup(t)) ∈ eps { 8. g'= g ∪ {t}; 9. sup(g’)=sup(t); 10. if (sup(g’) ≥ minsup and isCanonical(g’)) { 11. // Lưu g’ vào hàng đđợi ợi Qk 12. Insert g' into QK; 13. if (QK.size() ≥ k) { 14. if (QK.size() > k) Qk.pop();// Loại Loại bớt đồ thị con thừa 15. // Nâng ngưỡng ngưỡng minSup 16. minsup = sup(Qk.peek()); 17. } 18. // Lưu Lưu g’ vào hàng đợi đợi Qc 19. Insert g’ into Qc; 20. } 21. } 22. } return Qk; 4. ĐỀ ĐỀ XUẤT THUẬT TOÁN SONG SONG PARATKG 4.1. Thuật Thuật toán song song ParaTKG Thuật toán song song khai phá Top Thuật Top-KK đđồ ồ thị con phổ biến đđược trên ợc thiết kế dựa tr thuật ên thuật toán TKG, mô hình ccủa ủa thực hiện của thuật toán ParaTKG đđược trình bày trên hình và giả ợc trình giả mã ccủa ủa thuật toán đđư ược ợc tr trình ình bày trong bảng ảng 2. thuật Hình 1. Mô hình thu ParaTKG. ật toán ParaTKG Tạp ạp chí Nghiên Nghiên cứu cứu KH&CN quân sự, Số Đặc uân sự, ặc san Hội thảo Quốc gia FEE, 10 - 2020 20 441
Toán học – Công nghệ thông tin Bảng 2. Thuật toán ParaTKG. Đầu vào : CSDL đồ thị GD, giá trị ngưỡng k. Đầu ra: k đồ thị con phổ biến 1. Hàng đợi ưu tiên Qk để lưu trữ k đồ thị con phổ biến, trong đó, đồ thị con có độ hỗ trợ nhỏ hơn thì có độ ưu tiên cao hơn. Qk được khởi tạo bằng k đồ thị con có 1 cạnh đơn có độ hỗ trợ lớn nhất. 2. Hàng đợi ưu tiên Qc để lưu trữ các đồ thị con ứng viên cho việc mở rộng tiếp theo, trong đó, đồ thị con có độ hỗ trợ lớn hơn thì có độ ưu tiên cao hơn. Qc được khởi tạo bằng k đồ thị con có 1 cạnh đơn có độ hỗ trợ lớn nhất. 3. minSup được gán bằng độ hỗ trợ của đồ thị con trong đầu hàng đợi của Qc 4. while (Qc is not empty) { 5. foreach Processors { 6. Task ti = new Task(() { 7. synchronized (g = Qc. pop();); 8. eps= rightMostPathExtensions(g, GD); 9. foreach (t; sup(t)) ∈ eps { 10. g'= g ∪ {t}; 11. sup(g’)=sup(t); 12. if (sup(g’) ≥ minsup and isCanonical(g’)) { 13. // Lưu g’ vào hàng đợi Qk 14. synchronized (Insert g' into QK;); 15. if (QK.size() ≥ k) { 16. if (QK.size() > k) Qk.pop();// Loại bớt đồ thị con thừa 17. // Nâng ngưỡng minSup 18. synchronized (minsup = sup(Qk.peek());); 19. } 20. // Lưu g’ vào hàng đợi Qc 21. synchronized (Insert g’ into Qc;); 22. } 23. } 24. } 25. } return Qk; Dòng 1, 2, 3 thực hiện khởi tạo 02 hàng đợi Qk, Qc và xác định minSup ban đầu như trong thuật toán TKG. Tiếp theo, Qk và Qc là 02 hàng đợi dùng chung, chia sẽ giữa các nhân xử lý. Thuật toán ParaTKG được thiết kế theo phương pháp cân bằng tải động. Cụ thể, ở dòng 6, mỗi nhân sẽ nhận một đồ thị con g từ hàng đợi Qc, thực hiện mở thêm 01 cạnh theo đường dẫn phải cùng nhất để xác định đồ thị con phổ biến g' có nhiều hơn g một cạnh, sau đó cập nhật g' vào Qk, Qc và xác định lại minSup. Việc khai phá ra các đồ thị con g' từ đồ thị g được thực hiện trong các nhân một cách độc lập, riêng việc cập nhật g' vào Qk, Qc và xác định lại minSup phải thực hiện theo cơ chế cạnh tranh do Qk, Qc là các hàng đợi dùng chung. 4.2. Ví dụ minh hoạ Hình 3 minh hoạ một số bước thực hiện thuật toán song song ParaTKG với 2 luồng khai phá Top-K đồ thị con phổ biến với k=4 từ CSDL đồ thị gồm 02 đồ thị G1, G2 như trên hình 2. Ban đầu, có 04 đồ thị con 1 cạnh đơn được xác định: g1=(0,1,a,a) với sup(g1)=2; g2=(0,1,a,b) với sup(g2)=2; g3=(0,1,b,a) với sup(g3)=2; g4=(0,1,b,b) với sup(g4)=1; 442 P. V. Lai, …, P. V. Anh, “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ệ Loại g3 vì nó là một đẳng cấu của g2. Qk = {g4, g1, g2}; Qc={g1, g2, g4}; minSup=1; Tiếp theo, Thread1 sẽ nhận g1 từ Qc và Thread2 nhận g2 từ Qc để tiến hành khai phá. Hình 2. CSDL đồ thị. Thread1: từ g1 khai phá ra các đồ thị g5 và g6 đều có độ hỗ trợ bằng 2, tuy nhiên, g5 bị loại vì mã DFS của g5 không chuẩn tắc; g6 được thêm vào Qk, Qc. Như vậy, Qk= Qk = {g4, g1, g2, g6}; Qc={ g6, g4}; Thread2: từ g2 khai phá ra các đồ thị g7, g9 và g10 đều có độ hỗ trợ bằng 2 và g8 có độ hỗ trợ bằng 1. Tuy nhiên, g9 bị loại vì mã DFS của g9 không chuẩn tắc. G7 được thêm vào Qk, Qc. Như vậy, Qk= Qk = {g1, g2, g5, g7}; Qc={g7, g5, g4}; cập nhật minSup=2; Tiếp theo, loại g8 do độ hỗ trợ nhỏ hơn minSup,… Hình 3. Sơ đồ thực hiện thuật toán ParaTKG. 5. THỬ NGHIỆM VÀ ĐÁNH GIÁ Thuật toán TKG được lấy từ địa chỉ [19], thuật toán ParaTKG được cài đặt trên ngôn ngữ Java. Các thử nghiệm được tiến hành trên máy tính có bộ xử lý Intel Core i5-5300 tốc độ 2.3GHz, 8GB RAM và chạy hệ điều hành Windows 10 64bit. Bảng 3. Số liệu thống kê trên 02 bộ dữ liệu đồ thị. Bộ dữ liệu Số đồ thị Số đỉnh TB Số cạnh TB Số nhãn đỉnh Số nhãn cạnh Proteins_graph 1.113 39,06 72,82 3 1 Enzymes_graph 600 284,32 62,14 3 1 Để chứng minh tính hiệu quả của thuật toán song song đề xuất, chúng tôi đã so sánh thời gian thực hiện của thuật toán ParaTKG với thuật toán TKG. Bảng 4 và hình 4 là thông tin về giá trị minSup xác định được và so sánh thời gian chạy của hai thuật toán trên bộ dữ liệu Proteins_graph (CSDL đồ thị trong đó, các nút biểu thị các thành phần cấu trúc thứ cấp và các cạnh biểu thị vùng lân cận trong chuỗi axit amin hoặc trong không gian 3 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 443
học – Công ngh Toán học nghệệ thông tin chiều). chi và hình 5 là thông tin vvềề giá trị minSup xá ều). Bảng 5 và xácc đđịnh đ ợc và ịnh được thời và so sánh th ời gian chạy của hai thuật toán tr chạy trên ên bộ bộ dữ liệu Enzymes_graph (CSDL đồ đồ thị cấu trúc bậc ba được từ ccơ protein thu được ơ ssở ở dữ liệu BRENDA). Bảng 4. Giá tr Bảng trịị minSup xác định đđưược ợc trên trên Proteins_graph. Proteins_graph. trị ngưỡng Giá trị ỡng k Thuật Thuật toán TKG Thuật toán ParaTKG Thuật 100 0,671 (tương đương 747 đồ đồ thị) 0,671 (tương đương 747 đđồ ồ thị) 150 0,644 (tương đương 717 đồ đồ thị) 0,644 (tương đương 717 đđồ ồ thị) 200 0,627(tương đương 698 đồồ thị) 0,627 (tương đương 698 đồồ thị) 250 0,612(tương đương 682 đđồ ồ thị) 0,612 (tương đương 682 đđồ ồ thị) ảng 5. Giá tr Bảng trịị minSup xác định đđư ược ợc trên trên Enzymes_graph. Enzymes_graph. trị ngư Giá trị ngưỡng ỡng k Thuật Thuật toán TKG Thuật toán ParaTKG Thuật 100 0,807 (tương đương 484 đđồ ồ thị) 0,807 (tương đương 484 đđồ ồ thị) 150 0,782(tương đương 469 đđồ ồ thị) 0,782(tương đương 469 đđồ ồ thị) 200 0,763(tương đương 458 đđồ ồ thị) 0,763(tương đương 458 đđồ ồ thị) 250 0,752(tương đương 451 đđồ ồ thị) 0,752(tương đương 451 đđồ ồ thị) Hình 4. So sánh thời trên thời gian thực hiện giữa 2 thuật toán trên Proteins_graph. thời gian thực hiện Hình 5. So sánh thời trên ện giữa 2 thuật toán tr Enzymes_graph. ên Enzymes_graph Kết ảng 4 và bbảng ết quả thử nghiệm trong bảng ảng 5 cho thấy thấy thuật toán ParaTKG cho kết quả chính xác như thuật thuật toán TKG, trên thấy trên hình 4 và hình 5 cho th ấy thuật toán ParaTKG chạy nhanh hơn TKG trong ttấtất cả các thí nghiệm. Điều thuật Điều này là do thu ật toán song song có thể sử dụng ụng sức mạnh của kiến trúc bộ xử lý đa nhân. KẾT 6. KẾT LUẬN đã đềề xuất thuật toán song song ParaTKG dựa tr Bài báo đã trên thuật toán TKG triển khai ên thuật nền tảng kiến trúc bbộ trên nền ộ xử lý đa nhân, giảm chi phí đồng bộ hóa giữ giữaa các lu luồng ồng xử lý so với ới nền tảng kiến trúc cụm máy tính. 444 Thuật P. V. Lai, …, P. V. Anh, ““Thuật toán song song khai phá Top- Top-K K đồ đồ thị con phổ biến.” biến.”
Nghiên cứu khoa học công nghệ Ý tưởng cơ bản của thuật toán song song ParaTKG là phân chia công việc theo phương pháp cân bằng tải động, đảm bảo sử dụng tối đa tất cả các nhân của bộ xử lý. Để xác thực tính hiệu quả của thuật toán song song đề xuất ParaTKG, các thực nghiệm đã được tiến hành trên hai bộ dữ liệu Proteins_graph và Enzymes_graph. Kết quả thử nghiệm cho thấy, thuật toán đề xuất ParaTKG chạy ít thời gian hơn so với thuật toán tuần tự TKG. TÀI LIỆU THAM KHẢO [1]. Punin, J.R., Krishnamoorthy, M.S., Zaki, M.J.: LOGML: “Log markup language for web usage mining”. In: Kohavi, R., Masand, B., Spiliopoulou, M., Srivastava, J. (eds.) WebKDD 2001.LNCS (LNAI), vol. 2356, pp. 88–112. Springer, Heidelberg (2002) [2]. Eberle, W., Holder, L.: “Anomaly detection in data represented as graphs”. Intelligent Data Analysis 11, 663–689 (2007) [3]. Dehaspe, L., Toivonen, H., King, R.: “Finding Frequent Substructures in Chemical Compounds”. In: KDD, pp. 30–36 (1998) [4]. Nettleton, D.: “Data mining of social networks represented as graphs”. Computer Science Review 7, 1–34 (2013) [5]. Yan, X., Han, J.: gspan: “Graph-based substructure pattern mining”. In: Proc. 2nd IEEE Intern. Conf. on Data Mining (2002) [6]. Li, Y., Lin, Q., Li, R., Duan, D.: Tgp: “Mining top-k frequent closed graph pattern without minimum support”. In: Proc. 6th Intern. Conf. on Advanced Data Mining and Applications (2010). [7]. Philippe Fournier-Viger, Chao Cheng, Jerry Chun-Wei Lin, Unil Yun, and R. Uday Kiran TKG: “Efficient Mining of Top-K Frequent Subgraphs”, Big Data Analytics, 7th International Conference, BDA (2019) [8]. Casali, A., Ernst, C.: “Extracting Correlated Patterns on Multicore Architectures”. In: Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds.) CD-ARES 2013. LNCS, vol. 8127, pp. 118–133. Springer, Heidelberg (2013) [9]. Garey M. R., Johnson D. S., “Computers and Intractability”, New York: W.H. Freeman, 2002. [10]. Yan X., Han J., “Closegraph: mining closed frequent graph patterns”, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2003. [11]. Huan J., Wang W., Prins J., “Ecient mining of frequent subgraphs in the presence of isomorphism”, Proceedings of the 2003 International Conference on Data Mining, IEEE, 2003. [12]. Inokuchi A., Washio T., Motoda H., “An apriori-based algorithm for mining frequent substructures from graph data”, European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2000. [13]. Kuramochi M., Karypis G., “An ecient algorithm for discovering frequent subgraphs”, IEEE Transactions on Knowledge and Data Engineering, 2004. [14]. Yan X., Han J., “gSpan: graph-based substructure pattern mining”, Proceedings of International Conference on Data Mining, IEEE, 2002. [15]. Borgelt C., Berthold M. R., “Mining molecular fragments: Finding relevant substructures of molecules”, Proceedings of International Conference on Data Mining, IEEE, 2002. [16]. Agrawal R., Srikant R., “Fast algorithms for mining association rules”, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 1994.9 [17]. Han J., Pei J., Yin Y., “Mining frequent patterns without candidate generation”, ACM Sigmod Record, 2000. 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 445
Toán học – Công nghệ thông tin [18]. Wörlein M., Meinl T., Fischer I., Philippsen M., “A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston”, European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2005. [19]. https://www.philippe-fournier-viger.com/spmf/TKG.php. [20]. Zhang, F., Zhang, Y., Bakos, J.D.: “Accelerating frequent itemset mining on graphics processing units”. The Journal of Supercomputing 66, 94–117 (2013) [21]. Buehrer, G., Parthasarathy, S., Nguyen, A., Kim, D., Chen, Y.-K., Dubey, P.: “Parallel Graph Mining on Shared Memory Architectures”. Technical report, Columbus, OH, USA (2005). [22]. Kessl, R., Talukder, N., Anchuri, P., Zaki, M.: “Parallel Graph Mining with GPUs”. In: The 3rd International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, pp. 1–16 (2014). [23]. Lin, W., Xiao, X., Ghinita, G.: “Large-scale frequent subgraph mining in MapReduce”. In: The IEEE 30th International Conference on Data Engineering (ICDE 2014), pp. 844–855. [24]. Bay Vo, Dang Nguyen and Thanh-Long Nguyen, “A Parallel Algorithm for Frequent Subgraph Mining”, International Conference on Computer Science, Applied Mathematics and Applications (ICCSAMA 2015),pp. 163-173. ABSTRACT A PARALLEL ALGORITHM FOR MINING OF TOP-K FREQUENT SUBGRAPHS – PARATKG Graph mining is an important task of graph data mining, and it has many practical applications, for example: web link analysis, social media analytics, cheats and exceptions detection, chemical molecular analysis,etc. However, the common subgraph has a serious limitation when applied in practice, it is difficult to determine the appropriate minSup threshold value. If the minSup is set too high, then, only a few common subgraphs will be found and as such useful information can be missed. But if minSup is set too low, mining times can be very long and a huge number of common subgraphs can be found. Hence, determining a suitable minSup value to find just enough common subgraphs can be very time consuming. The proposed popular Top-K subgraph mining algorithm solves this limitation. Some popular Top-K subgraph mining algorithms have been proposed; however, most are sequential algorithms that cannot scale on large datasets. In this paper, we propose a parallel algorithm to overcome this weakness. The performance and scalability of the proposed algorithm are illustrated through experiments on two specific datasets. Keywords: Graph mining; Frequent Subgraphs mining; Top-K Frequent Subgraphs mining. Nhận bài ngày 30 tháng 07 năm 2020 Hoàn thiện ngày 05 tháng 10 năm 2020 Chấp nhận đăng ngày 05 tháng 10 năm 2020 Địa chỉ: 1Viện CNTT, Viện KH&CN quân sự; 2 Khoa CNTT, Học viện Kỹ thuật quân sự. *Email: laipv1984@gmail.com. 446 P. V. Lai, …, P. V. Anh, “Thuật toán song song khai phá Top-K đồ thị con phổ biến.”

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 © 2022-2032 TaiLieu.VN. All rights reserved.