Phần mở đầu của luận án giới thiệu chung về lĩnh vực khai thác dé liệu đồ thị, trong đó dé cập đến bài toán khai thác đồ thị con phố biến và các phương pháp tiếp cận dé giải bài toán này. Tiếp theo đó, luận án tập trung vào giới thiệu bài toán của luận án: khai thác đồ thị con phô biến trên đồ thị có trọng số và đề xuất các hướng tiếp cận dé giải quyết bài toán này. Phần mở dau cũng giới thiệu bố cục và các đóng góp chính của luận án. Khai thác đồ thị con phé biến 1.
Giới thiệu chung về khai thác dữ liệu đồ thị Trong thời gian gan đây, thuật ngữ dir liệu lớn (Big Data) đã không còn là một khái niệm mới mẻ và ngày càng được nhắc đến thường xuyên trong các lĩnh vực công nghệ cũng như việc ứng dụng công nghệ vào trong cuộc sông. Khai thác hiệu quả dữ liệu lớn tạo ra lợi thế rất lớn cho các tổ chức trong môi trường hoạt động đầy cạnh tranh hiện nay. Dữ liệu lớn có thể được hiểu theo nghĩa rộng là một thuật ngữ nói về việc lưu trữ, quản lý và xử lý một tập hợp dữ liệu với kích thước cực kỳ lớn và phức tạp mà các kỹ thuật xử lý dữ liệu theo các phương thức truyền thống không đủ khả năng dé thực hiện. Việc cố gắng tô chức và lưu trữ các tập dữ liệu không 16 với các cau trúc phức tạp bằng mô hình cơ sở dữ liệu truyền thống là không khả thi.
Do đó, cơ sở dữ liệu đồ thị được lựa chọn đề tổ chức và lưu trữ dữ liệu lớn. Tập trung vào mối quan hệ giữa các điểm đữ liệu thay vì vào bản thân các giá trị, đồ thị là sự lựa chọn hoan hảo cho các tập dữ liệu lớn, da dạng nhưng có kết nối. Với đồ thị, chúng ta dé dang thé hiện mối liên hệ giữa các dữ liệu cũng như ý nghĩa của các liên kết này, trên cơ sở đó thực hiện truy vấn những câu hỏi phức tạp và trừu tượng vượt ra ngoài những kết nối dữ liệu ban đầu. Trong số đó, mô hình đồ thị lớn có trọng số thường được sử dụng dé mô phỏng các mối quan hệ phức tạp giữa các đối tượng có mức độ quan trọng khác nhau trong nhiều ứng dụng: tầm quan trọng của tác nhân trong mạng xã hội, mức độ lưu thông của các giao điểm trên bản đồ, mức độ ảnh hưởng của các nút mạng máy tính và phân tích trang web dựa vào chỉ số ranking,.
Bài toán khai thác các đồ thị con có trọng số từ một đồ thị lớn đã dần trở nên là bài toán quan trọng trong nhiều lĩnh vực khoa học như phân tích mạng xã hội, hệ hỗ trợ ra quyết định, phân tích dữ liệu [10], phát sinh luật kết hợp [11, 36]. Trong một số trường hợp, chỉ có thé sử dụng đồ thị lớn có trọng số dé minh họa hoặc biểu diễn sự khác biệt giữa các đối tượng [22]. Vì thế, chủ đề này đã thu hút nhiều nghiên cứu trong các năm gần đây. Với mô hình dit liệu đồ thị, bài toán khai thác dit liệu đồ thị trở thành tâm điểm trong khai thác đữ liệu lớn.
Khai thác đồ thị con phô biến là một trong những nhánh của các kỹ thuật khai thác đữ liệu đồ thị. Bài toán khai thác đồ thị con phố biến Được dé xuất đầu tiên bởi Cook va Holder năm 1994, 2000 [51, 52], khai thác đồ thị con phố biến (FSM - Frequent Subgraph Mining) là bài toán tâm điểm trong lĩnh vực khai thác đữ liệu đồ thị và nhận được sự quan tâm của nhiều nhà nghiên cứu vì có thể ứng dụng nhiều trong thực 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 cơ sở đữ liệu đồ thị hoặc trong một đồ thị có kích thước lớn vượt một ngưỡng cho trước.
Giá trị ngưỡng cho trước đề xác định xem một đồ thị con có phô biến hay không được gọi là độ hỗ trợ tối thiểu (ký hiệu là min- sup). Bài toán khai thác đồ thi con phố biến nhằm mục đích khám phá tập dữ liệu đồ thị con thường xuyên xuất hiện trong một cơ sở dữ liệu đồ thị hoặc trong một đồ thị lớn. Cac hướng tiếp cận khai thác đồ thị con phố biến Hau hết các thuật toán tim đồ 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 dang cấu: xác định một đồ thị con của một đồ thi 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 đồ thị, do vậy dé xử lý được các cơ sở dit liệu đồ thị lớn và có cấu trúc phức tap cần phải có các thuật toán khai thác mẫu phô biến hiệu quả [6, 20]. Chiến lược phát sinh ứng viên: Phát sinh ứng viên là một phần quan trọng trong thuật toán khai thác đồ thị con phổ biến.
Việc phát sinh các đồ thị con ứng viên được thực hiện một cách hệ thong theo các chiến lược như sau: - _ Kết hợp ở cấp độ cùng kích thước: Hai đồ thị con có cùng kích thước k được kết hợp với nhau dé tạo thành một đồ thị con ứng viên có kích thước (k+/). - _ Mở rộng về phía bên phải: Trong chiến lược này, các đỉnh được thêm vào nhánh ngoài cùng bên phải của cây con có kích thước k dé tạo thành cây con kích thước (k + 1). Ngoài ra, có thé kể đến các chiến lược khác như “Mở rộng và kết hợp”, “Kết hợp cây ở cả hai hướng phải và trái”, “Mở rộng dựa trên lớp tương đương”. Nhìn chung, có thé chia các thuật toán khai thác đồ thị con phô biến thành hai nhóm dựa trên hai hướng tiếp cận chính: hướng tiếp cận dựa trên tính chất Apriori và hướng tiếp cận dựa trên phương pháp tăng trưởng mẫu.
Hướng tiếp cận dựa trên tính chất Apriori 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 kết hợp hai đồ thị con cùng kích thước G; va G2 thành đồ thi G› (kích thước lớn hơn một đỉnh so với G¡ và G2) và kiểm tra xem đồ thi kết quả G3 có phải là đồ thị phô biến không. Tại thời điểm xuất phát, thuật toán xem như đồ thị con chỉ có một đỉnh. Điểm khác nhau giữa các thuật toán này là phương thức “sinh” ứng viên (candidate) mới từ các đồ thị con phổ biến hiện thời. Các thuật toán thuộc nhóm này có thé kể đến là: AGM [13] được phát triển bởi Inokuchi, Washio, và Motoda vào năm 2000, sử dụng các chiến lược tìm kiếm theo mức thông minh; FSG [5, 17] được phát triển bởi Kuramochi và Karypis vào năm 2001, tạo ra ứng viên dựa trên các cạnh;.
Các thuật toán dựa trên tính chất Apriori thường kém hiệu quả vì chúng có hai nhược điểm chính sau: (1) sử dụng cách tiếp cận sinh và kiểm tra các ứng viên cũng như duy trì chúng trong bộ nhớ (số ứng viên được sinh ra trong trường hợp xấu nhất có thé tăng theo ham mũ; (2) duyệt co sở dt liệu nhiều lần đề tính toán độ hỗ trợ của các đô thị con ứng viên. Hướng tiếp cận dựa trên chiến lược tăng trưởng mẫu Đề tránh việc phát sinh ra quá nhiều ứng viên như trong hướng tiếp cận dựa trên tính chất Apriori và để tập trung tìm kiếm trên một không gian nhỏ hơn trong cơ sở dit liệu ban đầu, nhiều nghiên cứu sau nay đã sử dụng hướng tiếp cận dựa trên chiến lược tăng trưởng mẫu (Pattern Growth). Chiến lược tăng trưởng mẫu mở rộng một đồ thị con phô biến bằng cách thêm một cạnh phụ ở moi vi trí có thể. Phương pháp này giảm được chi phí so với việc kết hợp hai đồ thị con có kích thước ‘k’ dé tạo thành đồ thị kết quả có kích thước ‘k + 7”.
Nhưng hạn chế đáng ké ở đây là trong khi thêm một cạnh phụ ở mọi vi trí có thé, cùng một đồ thị con có thé được phát sinh nhiều lần, dẫn đến sự trùng lặp trong quá trình tạo ứng viên. Điều này có thể được loại bỏ bằng cách sử dụng kỹ thuật “mở rộng về phía bên phải”. Các thuật toán đại diện của nhóm nay là: MoFa (Molecular Fragments Identification Technique) [53] được phat triển bởi Borgelt va Berthold năm 2002; gSpan [47] được Yan và các cộng sự đề xuất năm 2002, là thuật toán đầu tiên sử dụng chiến lược tìm kiếm theo chiều sâu (DFS) trong khai thác đồ thị con phổ biến; FFSM (Fast Frequent Subgraph Mining) [11] phat trién boi Huan, Wang, Prins năm 2003, sử dụng chiến lược tim kiếm theo chiều dọc, để giảm số lượng các ứng viên phát sinh; Gaston [33], được đề xuất bởi Nijssen và Kok vào năm 2004, lưu trữ tat cả các bản nhúng, dé phát sinh ra duy nhất các mẫu đã được sảng lọc (thực sự xuất hiện trong tập dữ liệu đồ th) và dé kiểm tra dang cầu một cách nhanh chóng. Ưu điểm chung của các thuật toán khai thác đồ thị con phố biến theo hướng tiếp cận dựa trên chiến lược tăng trưởng mẫu là chỉ khai thác các đồ thị con xuất hiện trong cơ sở dir liệu đô thị.
Do đó, sô lượng các đô thi con ứng viên được sinh ra thường ít hơn so với các thuật toán dựa trên tính chất Apriori. Tuy nhiên, hạn chế chính của các thuật toán dựa trên tiếp cận này là duyệt và lưu trữ nhiều cơ sở dữ liệu trung gian, dẫn đến thời gian xử lý và bộ nhớ sử dụng có thê rất lớn. Khai thác đồ thị con pho biến trên đồ thị có trọng số 2. Bài toán khai thác đồ thị con phố biến trên đồ thị có trọng số Khái niệm trọng số trong khai thác mẫu phố biến được dé cập lần đầu bởi Cai Và các đồng sự vào năm 1998 [4].
Trọng số của đồ thị có thé được xem xét dưới dạng trọng số cạnh hoặc trọng số đỉnh. Khai thác đồ thị con phổ biến trên đồ thị có trọng số cũng dựa trên nền tang là bài toán khai thác d6 thị con phổ biến, nghĩa là vẫn xác định đồ thị con phổ biến dựa vào độ hỗ trợ tối thiểu (min-sup) đồng thời sử dụng thêm thông số là trọng số của đồ thị.