Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh công nghệ thông tin phát triển, khối lượng thông tin lưu trữ trên các thiết bị điện tử gia tăng nhanh chóng; theo số liệu được trích dẫn trong công trình, cứ sau khoảng 2 năm lượng thông tin lưu trữ trên toàn thế giới lại tăng gấp đôi. Sự bùng nổ về số lượng và kích cỡ của các cơ sở dữ liệu đặt ra yêu cầu cấp thiết về các kỹ thuật trích xuất thông tin tự động và hiệu quả. Khai phá dữ liệu đồ thị (Graph Data Mining) là một nhánh nghiên cứu giao thoa giữa khai phá dữ liệu và học máy, có phạm vi ứng dụng rộng rãi trong phân tích dữ liệu hóa học, sinh học, mạng máy tính và mạng xã hội.

Trong các bài toán của khai phá dữ liệu đồ thị (như phân lớp đồ thị, phân cụm đồ thị, học bán giám sát, tóm tắt đồ thị), khai phá đồ thị con phổ biến (Frequent Subgraph Mining) đóng vai trò nền tảng. Dựa trên cơ sở bài toán khai phá luật kết hợp, việc xác định các đồ thị con xuất hiện thường xuyên giúp xây dựng mô hình dự báo và phân tích cấu trúc phức tạp trong không gian dữ liệu đồ thị. Một trong những ứng dụng thực tiễn điển hình của hướng tiếp cận này là bài toán phát hiện cộng đồng trên mạng xã hội — cấu trúc mạng được mô hình hóa dưới dạng đồ thị có hướng hoặc vô hướng với các nút đại diện cho thực thể (người dùng, tổ chức) và các cạnh/cung đại diện cho mối quan hệ tương tác (bạn bè, giao dịch, trao đổi thông tin).

  • Mục tiêu nghiên cứu: Nghiên cứu cơ sở lý thuyết về các phương pháp khai phá đồ thị con phổ biến và tiến hành thử nghiệm ứng dụng vào việc giải quyết bài toán phát hiện cộng đồng trên mạng xã hội.
  • Đối tượng nghiên cứu: Các phương pháp, thuật toán và công cụ khai phá đồ thị con phổ biến; tập dữ liệu thử nghiệm thu thập từ mạng xã hội.
  • Phạm vi nghiên cứu: Tập trung vào bài toán khai phá đồ thị con phổ biến và thử nghiệm thực tế với bài toán phát hiện cấu trúc cộng đồng trên mạng xã hội Facebook.

Cơ sở lý thuyết và phương pháp

Khung lý thuyết và mô hình toán học

Luận văn tiếp cận bài toán dựa trên nền tảng lý thuyết phát hiện tri thức trong cơ sở dữ liệu (KDD), lý thuyết đồ thị và khai phá tập phổ biến:

  1. Khái niệm và quy trình KDD: Khai phá dữ liệu được xem là một giai đoạn cốt lõi trong quy trình khám phá tri thức gồm 7 bước:

    • Làm sạch dữ liệu (Data cleaning & preprocessing)
    • Tích hợp dữ liệu (Data integration)
    • Trích chọn dữ liệu (Data selection)
    • Chuyển đổi dữ liệu (Data transformation)
    • Khai phá dữ liệu (Data mining)
    • Ước lượng mẫu (Knowledge evaluation)
    • Biểu diễn tri thức (Knowledge presentation)

  2. Cơ sở lý thuyết đồ thị: Luận văn hệ thống hóa các dạng đồ thị $G = (V, E)$ gồm:

    • Đơn đồ thị vô hướng: $V$ là tập đỉnh, $E$ là tập các cặp không có thứ tự gồm hai phần tử khác nhau của $V$.
    • Đa đồ thị vô hướng: Cho phép tồn tại các cạnh lặp nối cùng một cặp đỉnh.
    • Giả đồ thị vô hướng: Cho phép tồn tại cạnh khuyên dạng $e = (u, u)$.
    • Đơn đồ thị có hướng: $E$ là tập các cặp có thứ tự gồm hai phần tử khác nhau của $V$.
    • Đa đồ thị có hướng: Cho phép tồn tại các cung lặp cùng hướng nối giữa hai đỉnh.

  3. Mô hình toán học khai phá đồ thị con phổ biến:

    • Cho tập dữ liệu đồ thị $D = {G_0, G_1, \dots, G_n}$ và ngưỡng hỗ trợ tối thiểu $\text{minFreq} \in (0, 1]$.
    • Hàm chỉ thị đẳng cấu $\delta(g, G_i) = 1$ nếu đồ thị $g$ đẳng cấu với một đồ thị con trong $G_i$, ngược lại bằng $0$.
    • Độ phổ biến của $g$ trong tập dữ liệu $D$ được xác định theo công thức: $$\sigma(g, D) = \sum_{G_i \in D} \delta(g, G_i)$$
    • Bài toán đặt ra là tìm tất cả các đồ thị con $g$ sao cho: $\sigma(g, D) \ge \text{minFreq}$.
    • Khái niệm cây phổ biến cực đại ($M$), cây phổ biến đóng ($C$) và tập các cây con phổ biến ($F$), thỏa mãn quan hệ bao hàm: $M \subseteq C \subseteq F$.

  4. Khai phá luật kết hợp và nguyên lý Apriori:

    • Quy tắc $A \Rightarrow B$ được đánh giá qua độ hỗ trợ ($\text{Support}$) và độ tin cậy ($\text{Confidence}$): $$\text{Supp}(A \Rightarrow B) = \frac{\text{Số lượng giao dịch gồm cả } A \text{ và } B}{\text{Tổng số lượng giao dịch}}$$ $$\text{Conf}(A \Rightarrow B) = \frac{\text{Số lượng giao dịch gồm cả } A \text{ và } B}{\text{Số lượng giao dịch chỉ gồm } A}$$
    • Tính chất Apriori (Anti-monotone): Mọi tập con không rỗng của một tập mục phổ biến đều phải là tập phổ biến. Nếu một tập mục không đạt ngưỡng hỗ trợ tối thiểu thì mọi tập cha mở rộng từ nó đều bị loại bỏ trong không gian tìm kiếm.

Phương pháp nghiên cứu và nguồn dữ liệu

  • Phương pháp nghiên cứu: Phương pháp phân tích - tổng hợp lý thuyết kết hợp với thực nghiệm tính toán trên mô hình đồ thị. Áp dụng các thuật toán khai phá đồ thị con phổ biến (như thuật toán FSG, Light-FSG, CMTMiner, HSIGRAM, VSIGRAM) và thuật toán phát hiện cộng đồng (Girvan-Newman, CONGA, FNCA).
  • Nguồn dữ liệu thực nghiệm: Dữ liệu tương tác thực tế từ các nhóm mạng xã hội Facebook. Dữ liệu thô được trích xuất thành 3 định dạng bảng tính (worksheets): quan hệ bạn bè (friends), lượt thích (likes) và lượt bình luận (comments). Dữ liệu sau đó được mã hóa/giải mã thông tin người dùng và xây dựng thành ma trận tương tác (như ma trận thích).

Nội dung chính theo từng chương

Chương 1: Tổng quan về khai phá dữ liệu đồ thị

Chương này trình bày toàn diện các khái niệm, quy trình và kỹ thuật nền tảng trong lĩnh vực phát hiện tri thức:

  • Khái niệm và định nghĩa khai phá dữ liệu: Tổng hợp định nghĩa của các nhà khoa học: Ferruzza (tìm kiếm sự khác biệt và mẫu chưa biết), Parsaye (trợ giúp quyết định từ cơ sở dữ liệu lớn), Fayyad (quá trình phi tầm thường nhằm nhận diện các mẫu hợp lệ, mới, hữu ích và có thể hiểu được).
  • Quy trình khai phá dữ liệu đồ thị gồm 5 bước:
    1. Hình thành và định nghĩa bài toán: Xác định mục tiêu ứng dụng và lựa chọn phương pháp phù hợp với bản chất dữ liệu.
    2. Thu thập và tiền xử lý dữ liệu: Xử lý dữ liệu khuyết thiếu, khử trùng lặp, giảm nhiễu, chuẩn hóa, rời rạc hóa, rút trích/xây dựng đặc trưng mới và giảm chiều dữ liệu.
    3. Khai phá dữ liệu và rút ra tri thức: Trích xuất các mẫu và mô hình ẩn dưới dữ liệu.
    4. Phân tích và kiểm định kết quả: Đánh giá mẫu thông qua kiểm định chéo (cross-validation), đo lường độ chính xác, tính mới lạ và tính hữu ích.
    5. Sử dụng các tri thức phát hiện được: Tích hợp mô hình vào các hệ thống hỗ trợ ra quyết định.
  • Các chức năng chính của khai phá dữ liệu: Mô tả khái niệm, khai phá luật kết hợp, phân lớp và dự đoán (sử dụng cây quyết định, mạng nơ-ron), phân cụm (học không giám sát) và khai phá chuỗi tuần tự.
  • Phân loại thành phần giải thuật: Mỗi giải thuật khai phá gồm ba thành phần chính: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm (tìm kiếm tham số, tìm kiếm mô hình bằng giải thuật tham lam hoặc heuristic).
  • Phạm vi ứng dụng: Ứng dụng khai phá dữ liệu trong sinh học (so sánh hệ gen), y học (chẩn đoán bệnh), tài chính - chứng khoán, viễn thông, bảo mật (phát hiện xâm nhập) và phân tích cấu trúc DOM trang web.

Chương 2: Thuật toán FSG và ứng dụng khai phá đồ thị con phổ biến phát hiện cộng đồng mạng xã hội

Chương này tập trung vào các giải thuật khai thác đồ thị con và bài toán mạng xã hội:

  • Cơ chế thuật toán Apriori và FSG (Frequent Subgraph Mining): Khảo sát kỹ thuật tìm kiếm theo cấp bậc (level-wise search). Thuật toán duyệt qua cơ sở dữ liệu để tìm các tập mục/đồ thị con 1 phần tử phổ biến, sau đó sinh ứng viên và cắt tỉa dựa trên tính chất chống đơn điệu để tìm các đồ thị con có kích thước lớn hơn.
  • Các thuật toán khai phá đồ thị con điển hình: Phân tích cơ chế của CMTMiner (duyệt cạnh phổ biến kết hợp xây dựng cây DFS), HSIGRAM và VSIGRAM (tìm kiếm đồ thị con phổ biến trên đồ thị đơn kích thước lớn).
  • Mô hình hóa mạng xã hội: Định nghĩa mạng xã hội theo Simmel (1955) và cấu trúc đồ thị tương tác. Mối liên kết giữa các cá nhân được lượng hóa bằng trọng số thể hiện độ mạnh tương tác (giao dịch, lượt tương tác).
  • Phân loại phương pháp phát hiện cộng đồng (theo Santo Fortunato):
    • Các phương pháp truyền thống
    • Thuật toán phân chia
    • Phương pháp dựa trên mô-đun hóa
    • Thuật toán động
    • Phương pháp phát hiện cộng đồng chồng chéo (overlapping community detection)
    • Các thuật toán tiêu biểu: Girvan-Newman, CONGA (Cluster Overlap Newman-Girvan Algorithm), FNCA (Fast Network Community Algorithm).

Chương 3: Thử nghiệm, đánh giá kết quả với bài toán phát hiện cộng đồng mạng xã hội

Chương này mô tả chi tiết quá trình triển khai thực nghiệm và đánh giá:

  • Quy trình xử lý dữ liệu nhóm Facebook: Thu thập dữ liệu tương tác thành viên trên nhóm Facebook; tiền xử lý và cấu trúc hóa thành 3 bảng dữ liệu quan hệ gồm danh sách bạn bè, tương tác thích và tương tác bình luận; tiến hành mã hóa định danh người dùng nhằm bảo đảm tính nhất quán của dữ liệu đồ thị.
  • Xây dựng ma trận tương tác: Dữ liệu sau giải mã được tổng hợp thành ma trận kề/ma trận thích (Like Matrix) biểu diễn cường độ liên kết giữa các nút người dùng.
  • Thực nghiệm thuật toán Light-FSG: Triển khai thuật toán Light-FSG để khai phá các cấu trúc đồ thị con phổ biến đại diện cho các nhóm liên kết chặt chẽ trong mạng.
  • Đánh giá và so sánh: Tiến hành so sánh hiệu năng của thuật toán Light-FSG với các thuật toán khai phá đồ thị khác; trực quan hóa mạng lưới đồ thị cộng đồng phát hiện được trên không gian biểu diễn 2D và 3D.

Kết quả và đóng góp

Bảng tổng hợp các thuật toán và mô hình trong luận văn

Nhóm kỹ thuật Tên thuật toán / Khái niệm Đặc điểm & Vai trò trong luận văn
Khai phá tập phổ biến Apriori (Agrawal & Srikant, 1993) Duyệt tìm kiếm theo cấp bậc (level-wise), sử dụng tính chất chống đơn điệu (anti-monotone) để cắt tỉa ứng viên
Khai phá đồ thị con FSG / Light-FSG Khai phá đồ thị con phổ biến dựa trên tần suất xuất hiện, ứng dụng rút trích mẫu liên kết nhóm
Khai phá đồ thị con CMTMiner Duyệt các cạnh phổ biến và xây dựng cây DFS để tìm đồ thị con phổ biến
Khai phá đồ thị con HSIGRAM / VSIGRAM Hai thuật toán xác định đồ thị con phổ biến trong cấu trúc một đồ thị lớn
Phát hiện cộng đồng Girvan-Newman Thuật toán phân chia phát hiện cấu trúc mạng cộng đồng xã hội
Phát hiện cộng đồng CONGA (Cluster Overlap Newman-Girvan Algorithm) Phát hiện các cấu trúc cộng đồng có sự chồng chéo giữa các thành viên
Phát hiện cộng đồng FNCA (Fast Network Community Algorithm) Thuật toán tối ưu hóa tốc độ phát hiện cấu trúc mạng cộng đồng

Kết quả chính và đóng góp của đề tài

  • Hệ thống hóa lý thuyết: Luận văn đã tổng hợp có hệ thống cơ sở toán học của khai phá dữ liệu đồ thị, phân loại rõ các cấu trúc đồ thị (đơn/đa đồ thị, có hướng/vô hướng, giả đồ thị), định nghĩa hình thức bài toán đồ thị con phổ biến thông qua hàm chỉ thị đẳng cấu và ngưỡng hỗ trợ $\text{minFreq}$.
  • Xây dựng quy trình xử lý dữ liệu mạng xã hội: Thiết lập quy trình trích xuất và tiền xử lý dữ liệu từ nhóm Facebook thành ma trận tương tác dựa trên ba hành vi: kết bạn, thích và bình luận.
  • Đánh giá thuật toán Light-FSG: Luận văn đã thử nghiệm giải thuật Light-FSG trên tập dữ liệu thực tế, thực hiện so sánh với các thuật toán liên quan và trực quan hóa cấu trúc mạng cộng đồng dưới dạng đồ thị 2D và 3D.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế:
    • Phạm vi dữ liệu thử nghiệm tập trung chủ yếu vào cấu trúc dữ liệu trích xuất từ một số nhóm Facebook cụ thể, chưa kiểm thử trên đa dạng các loại mạng xã hội có quy mô và cấu trúc tương tác khác biệt.
    • Khi kích thước tập dữ liệu đồ thị và số lượng thuộc tính tăng cao, không gian tìm kiếm đồ thị con gia tăng theo hàm mũ ($2^K$), gây áp lực lớn lên chi phí tính toán và bộ nhớ trong quá trình duyệt ứng viên.
  • Hướng nghiên cứu tiếp:
    • Nghiên cứu tối ưu hóa các giải thuật cắt tỉa không gian tìm kiếm nhằm tăng tốc độ xử lý trên các đồ thị có kích thước lớn và mật độ cạnh cao.
    • Mở rộng mô hình để phát hiện các dạng cộng đồng động biến đổi theo thời gian và cộng đồng có cấu trúc chồng chéo phức tạp trên các nền tảng mạng xã hội quy mô lớn.

Giá trị tham khảo

Tài liệu này là nguồn tài liệu hữu ích cho:

  • Sinh viên, học viên ngành Công nghệ thông tin và Khoa học máy tính: Tham khảo phương pháp luận và cách tiếp cận hình thức hóa các khái niệm lý thuyết đồ thị, quy trình KDD và các thuật toán khai phá luật kết hợp / đồ thị con phổ biến.
  • Người nghiên cứu về Phân tích mạng xã hội (SNA): Tham khảo mô hình chuyển đổi hành vi tương tác mạng xã hội (kết bạn, tương tác thích, bình luận) thành ma trận trọng số và phương pháp ứng dụng thuật toán Light-FSG để phân cụm/phát hiện cộng đồng.
  • Phần đáng tham khảo nhất: Mục định nghĩa toán học về đồ thị con phổ biến, cây phổ biến đóng/cực đại (Chương 1) và quy trình tiền xử lý, cấu trúc hóa dữ liệu từ nhóm Facebook (Chương 3).

Câu hỏi thường gặp

1. Quy trình khám phá tri thức trong cơ sở dữ liệu (KDD) được trình bày gồm những bước nào?

Theo luận văn, quy trình KDD bao gồm 7 bước tuần tự: (1) Làm sạch dữ liệu (Data cleaning & preprocessing); (2) Tích hợp dữ liệu (Data integration); (3) Trích chọn dữ liệu (Data selection); (4) Chuyển đổi dữ liệu (Data transformation); (5) Khai phá dữ liệu (Data mining); (6) Ước lượng mẫu (Knowledge evaluation); (7) Biểu diễn tri thức (Knowledge presentation).

2. Điều kiện toán học để một đồ thị con $g$ được coi là đồ thị con phổ biến trong tập dữ liệu $D$ là gì?

Một đồ thị $g$ là đồ thị con phổ biến nếu độ phổ biến $\sigma(g, D)$ của nó không nhỏ hơn ngưỡng hỗ trợ tối thiểu $\text{minFreq}$ cho trước ($\sigma(g, D) \ge \text{minFreq}$), trong đó $\sigma(g, D) = \sum_{G_i \in D} \delta(g, G_i)$ và $\delta(g, G_i) = 1$ khi $g$ đẳng cấu với một đồ thị con trong $G_i$, ngược lại bằng $0$.

3. Tính chất Apriori (Anti-monotone property) được định nghĩa và có ý nghĩa như thế nào trong khai phá dữ liệu?

Tính chất Apriori quy định rằng: Tất cả các tập con không rỗng của một tập mục phổ biến cũng phải là tập phổ biến. Về mặt thuật toán, tính chất chống đơn điệu này cho phép loại bỏ sớm các tập ứng viên không đạt ngưỡng $\text{min_sup}$ mà không cần duyệt kiểm tra các tập cha mở rộng của chúng, từ đó giảm đáng kể không gian tìm kiếm.

4. Dữ liệu thực nghiệm mạng xã hội trong luận văn được thu thập từ đâu và gồm những thông tin tương tác nào?

Dữ liệu được thu thập từ các nhóm người dùng trên mạng xã hội Facebook, sau đó phân tách thành 3 định dạng trang tính (worksheets) tương ứng với 3 loại quan hệ/hành vi tương tác: danh sách bạn bè (friends), lượt thích (likes) và lượt bình luận (comments).

5. Luận văn đã đề cập đến những thuật toán phát hiện cộng đồng mạng xã hội tiêu biểu nào?

Văn bản nêu rõ các thuật toán phát hiện cộng đồng tiêu biểu gồm: thuật toán Girvan-Newman, thuật toán phát hiện cộng đồng chồng chéo CONGA (Cluster Overlap Newman-Girvan Algorithm) và thuật toán mạng nhanh FNCA (Fast Network Community Algorithm).

Kết luận

Luận văn thạc sĩ của tác giả Hoàng Việt Dũng đã hệ thống hóa cơ sở lý thuyết về khai phá dữ liệu đồ thị, trọng tâm là bài toán khai phá đồ thị con phổ biến và các biến thể cây phổ biến. Đề tài đã xây dựng quy trình trích xuất, mô hình hóa tương tác người dùng trên mạng xã hội Facebook thành ma trận kề có trọng số. Thông qua việc thử nghiệm thuật toán Light-FSG và trực quan hóa cấu trúc 2D/3D, công trình đã chứng minh tính khả thi của việc ứng dụng kỹ thuật khai phá đồ thị con vào bài toán phân tích và phát hiện cộng đồng mạng xã hội.