圖形演算法增強機器學習模型效能

– 13 分鐘閱讀

圖形演算法在處理複雜關聯資料時展現出強大能力，能有效應用於航空路線分析、社群檢測和機器學習模型增強等場景。透過 TigerGraph 的 GSQL 語言，可以有效執行社群檢測演算法，並藉由@@cluster_member_map識別不同社群及其成員。文章以航空路線分析為例，示範如何使用圖形視覺化工具探索社群結構和成員間的飛行連線。此外，圖形特徵萃取能將圖形結構轉化為機器學習可用的特徵向量，進一步提升模型效能。文章也介紹了頻繁模式挖掘的應用，並提供程式碼範例說明如何根據邊緣型別及其端點頂點型別進行分組，以識別頻繁出現的模式。最後，文章探討了圖形強化機器學習的三種主要方法：無監督學習與圖形演算法、圖形特徵萃取和圖形神經網路，並提供 Python 程式碼示範如何使用 NetworkX 函式庫提取圖形特徵，例如度中心性。

圖形演算法在航空路線分析中的應用

社群檢測與分析

在前面的章節中，我們已經探討瞭如何使用圖形演算法來分析航空路線網路。在本文中，我們將深入研究社群檢測演算法的應用，並使用TigerGraph的GSQL語言來實作。

首先，我們需要執行tg_scc_modified查詢，並設定以下引數：

  • v_type_set = Airport
  • e_type_set = flight_to
  • rev_e_type_set = reverse_flight_to
  • top_k_dist = 100
  • print_limit = 10000
  • print_results = false
  • result_attr = score

執行後，我們可以檢視@@cluster_member_map的結果。這個結果顯示了不同的社群及其成員。例如，我們可能會看到一個社群1048630，其中包含四個成員：["AKB-7195", "DUT-3860", "KQA-6134", "IKO-7196"]，以及另一個社群3145861，其中包含八個成員：["CXH-5500", "LKE-6457", "WSX-8173", "RCE-8170", "FBS-8174", "LPS-6136", "YWH-4106", "DHB-9540"]。

程式碼實作

PRINT @@cluster_dist_heap;
PRINT @@cluster_member_map; // added

內容解密：

  1. PRINT @@cluster_dist_heap; 用於輸出叢集分佈的堆積積情況。
  2. PRINT @@cluster_member_map; 用於輸出叢整合員的對映關係，顯示每個社群包含的成員。

圖形視覺化

接下來，我們將視覺化一個包含10個成員的社群及其飛行連線。假設社群ID為1048774，我們可以按照以下步驟在GraphStudio中進行視覺化：

  1. 在搜尋組態面板中，點選Airport旁的篩選圖示，開啟“新增屬性篩選”彈出視窗。
  2. 在條件下拉選單中，選擇Expression1 == Expression2。
  3. 將Expression1設定為屬性score，將Expression2設定為實數1048774。
  4. 點選“新增”。
  5. 確保頂點數量至少為10，然後點選“選擇頂點”。
  6. 在探索模式垂直選單中，點選“從頂點展開”圖示。
  7. 取消選擇flight_route，只包含flight_to邊緣。
  8. 點選“展開”。
  graph LR
    A[AKB-7195] -->|flight_to|> B[DUT-3860]
    A -->|flight_to|> C[KQA-6134]
    A -->|flight_to|> D[IKO-7196]
    B -->|flight_to|> A
    C -->|flight_to|> A
    D -->|flight_to|> A

圖表翻譯： 此圖表顯示了社群1048774中的成員及其飛行連線。可以看到，這些機場之間存在著緊密的連線，形成了一個星形結構。

分析結果

透過上述步驟，我們可以看到這個社群中的機場主要集中在新喀裡多尼亞群島，其中包括首都努美阿。進一步分析，我們發現這些航班主要在群島內部進行，沒有飛往外部的航班。這可能與我們使用的OpenFlights.org資料集的完整性有關，但它仍然展示了圖形演算法在揭示網路結構和特性方面的強大能力。

圖形強化機器學習方法

機器學習流程

圖形資料和圖形分析可以顯著改善機器學習模型的效能。圖10-1展示了一個簡單的機器學習流程，包括資料擷取、資料準備、特徵擷取和模型訓練四個階段。在第一部分中，我們探討瞭如何使用圖資料函式庫來連線多個資料來源並進行實體解析。

圖形強化機器學習的三種方法

  1. 無監督學習與圖形演算法：使用圖形演算法進行社群檢測、中心性計算等。
  2. 圖形特徵擷取：提取根據圖形結構的特徵，以增強訓練資料。
  3. 圖形神經網路：直接在圖形上進行模型訓練，包括聚類別、嵌入和神經網路等技術。

程式碼實作

# 示例程式碼：使用圖形特徵進行機器學習
import networkx as nx
import numpy as np

# 建立一個簡單的圖形
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# 提取圖形特徵
degree_centrality = nx.degree_centrality(G)

# 列印結果
print(degree_centrality)

內容解密：

  1. 使用networkx函式庫建立一個簡單的圖形。
  2. 提取每個節點的度中心性作為圖形特徵。
  3. 列印結果，以瞭解每個節點在圖形中的重要性。

本章重點

在本章中，我們將探討圖形強化機器學習的三種主要方法，並透過例項來說明如何使用圖形資料和圖形分析來改善機器學習模型的效能。我們將重點介紹無監督學習、圖形特徵擷取和圖形神經網路等技術，並比較不同的圖形強化機器學習方法的優缺點，以幫助讀者選擇適合自己的方法。

無監督學習與圖演算法

無監督學習是機器學習的三大主要分支之一，另外兩個是監督學習和強化學習。如果你希望你的AI系統能夠學習如何執行某項任務、按照你的分類別類別進行分類別，或是做出預測，你可能會使用監督學習和/或強化學習。然而，無監督學習具有自我完善和即刻可用的優勢。與監督學習不同，你不需要事先知道某些案例的正確答案。與強化學習不同，你不需要耐心並容忍透過試錯來學習的過程。無監督學習只需接收你所提供的資料並報告其學習成果。

無監督學習演算法可以分析你的客戶和銷售網路，並識別出實際的市場細分，這些細分可能不符合簡單的年齡和收入分類別。無監督學習演算法可以透過確定資料中的「正常」情況，而不是根據你的先入之見，指出哪些客戶行為是異常的或是遠離正常的。例如，異常值可以指出哪些客戶可能會流失（即停止使用你的產品或服務）。

透過相似性和社群結構學習

在第六章中，我們對五大類別演算法進行了詳細的概述。在本文中，我們將討論哪些演算法適合用於無監督學習。同時，我們還將介紹另一種圖分析任務：頻繁模式挖掘。

在五大類別演算法中，最後一類別——分類別和預測——通常被資料科學家視為機器學習領域的一部分。尤其是分類別，通常屬於監督學習。預測則有多種形式。如前所述，這兩項任務都依賴於某種相似性度量方法。因此，相似性演算法是機器學習的關鍵工具。

相似性演算法的應用

如果你找到了具有高Jaccard相似性的所有頂點，這可能不像是你在進行機器學習。你可以進一步思考：你找到的相似頂點的數量是否遠高於或遠低於你的預期？你可以根據一個頂點通常的連線數量，以及兩個隨機頂點具有共同鄰居的可能性來建立你的預期。這類別特徵可以告訴你關於你的圖和它所代表的真實世界事物的重要資訊。

例如，假設一家大公司將其員工和各種與工作相關的資料對映到一個圖中。經理可以搜尋與其當前團隊成員具有相似工作資格的其他員工。結果對於跨職能培訓、韌性和勞動力的冗餘度有何啟示？

社群結構的發現

當一個圖的結構是由許多獨立的參與者決定，而不是由中央計畫決定時，它的社群結構並不是先驗已知的；我們需要分析這個圖來發現這種結構。這種結構反映了實體及其相互關係，因此瞭解這種結構可以告訴我們一些關於這些實體及其動態的資訊。根據模組化的演算法，如Louvain和Leiden，就是自我學習的典型例子：透過觀察圖中連線的相對密度來確定社群成員。遞迴定義的SimRank和RoleSim度量也符合無監督學習的自我學習特徵。那麼，PageRank是否也是一種無監督學習的形式呢？

實際應用價值

這些演算法也非常有價值。許多金融機構發現，將中心性和社群演算法應用於交易圖，有助於更好地識別金融犯罪。

發現頻繁模式

正如我們在本文中所說，圖非常適合發現和分析根據連線的多重連線模式。在第二部分：分析中，我們討論瞭如何發現特定的模式，我們將在本章後面回到這個主題。在無監督學習的背景下，我們的目標是：

發現所有頻繁出現的模式

電腦科學家將此稱為頻繁子圖挖掘任務，因為連線模式本質上就是一個子圖。這項任務對於理解自然行為和結構（如消費者行為、社會結構、生物結構，甚至軟體程式碼結構）非常有用。然而，它也提出了一個更具挑戰性的問題。在一個大圖中，「所有」模式意味著需要檢查的可能出現次數非常龐大。救命稻草是閾值引數T。一個模式要被視為頻繁，必須至少出現T次。選擇一個合適的T值非常重要。我們希望它足夠高，以過濾掉小而不重要的模式——我們過濾得越多，需要做的整體工作就越少——但又不能太高，以至於排除了有趣的模式。選擇一個好的閾值本身可以是一個機器學習任務。

頻繁子圖挖掘的基本方法

有很多先進的方法嘗試加速頻繁子圖挖掘，但基本方法是從單邊模式開始，保留至少出現T次的模式，然後嘗試連線這些模式以形成更大的模式：

  1. 根據邊緣型別及其端點頂點的型別對所有邊緣進行分組。例如，Shopper-(bought)-Product 是一種模式。

內容解密：

這段程式碼展示瞭如何根據邊緣的型別和端點的型別進行分組。假設我們有一個簡單的圖，其中包含購物者、產品和購買行為。我們的目標是識別出頻繁出現的購買模式。

from collections import defaultdict

# 定義一個簡單的圖結構
class Graph:
    def __init__(self):
        self.edges = []

    def add_edge(self, src, dst, edge_type):
        self.edges.append((src, dst, edge_type))

    def group_edges(self):
        edge_groups = defaultdict(list)
        for src, dst, edge_type in self.edges:
            key = f"{src.__class__.__name__}-({edge_type})-{dst.__class__.__name__}"
            edge_groups[key].append((src, dst))
        return edge_groups

# 示例使用
graph = Graph()
graph.add_edge("Shopper1", "Product1", "bought")
graph.add_edge("Shopper2", "Product1", "bought")
graph.add_edge("Shopper1", "Product2", "bought")

edge_groups = graph.group_edges()
for pattern, occurrences in edge_groups.items():
    print(f"Pattern: {pattern}, Occurrences: {len(occurrences)}")

內容解密：

這段程式碼首先定義了一個簡單的圖類別，用於新增和分組邊緣。add_edge 方法允許我們向圖中新增帶有特定型別的邊緣。group_edges 方法根據邊緣的型別和端點的型別對邊緣進行分組。最後，我們透過建立一個圖的例項並新增一些示例邊緣來展示如何使用這個類別。分組結果被列印出來，顯示了每種模式的出現次數。

圖形演算法在機器學習中的應用：無監督學習與圖形特徵萃取

在現代資料分析與機器學習領域中，圖形資料的處理與分析正變得越來越重要。圖形演算法能夠有效地對複雜的關聯資料進行建模，並從中萃取出有價值的特徵與洞察。本文將探討圖形演算法在無監督學習中的應用，以及如何從圖形資料中萃取特徵以增強機器學習模型的表現。

圖形演算法與無監督學習

無監督學習是一種機器學習方法，用於在沒有預先標記的情況下，從資料中發現隱藏的模式與結構。圖形演算法在無監督學習中扮演著關鍵角色，能夠處理複雜的關聯資料並發現其中的重要特徵。

常見的圖形演算法類別

圖形演算法主要分為以下幾大類別：

  1. 相似度分析（Similarity）

    • 用於衡量圖形中不同節點之間的相似程度。
    • 常見演算法包括Jaccard相似度、餘弦相似度等。

  2. 社群檢測（Community Detection）

    • 用於識別圖形中緊密相連的節點群組。
    • 常見演算法包括Louvain演算法、Girvan-Newman演算法等。

  3. 中心性分析（Centrality）

    • 用於評估節點在圖形中的重要程度。
    • 常見指標包括度中心性（Degree Centrality）、介數中心性（Betweenness Centrality）等。

  4. 預測（Prediction）

    • 利用圖形結構進行鏈路預測或節點分類別。
    • 常見演算法包括根據隨機遊走的演算法，如Node2Vec等。

  5. 頻繁模式挖掘（Frequent Pattern Mining）

    • 用於發現圖形中頻繁出現的子結構或模式。
    • 常見演算法包括gSpan、FPGrowth等。

頻繁模式挖掘詳解

頻繁模式挖掘旨在從圖形資料中找出重複出現的子圖結構，這些結構可能代表重要的模式或規則。以下是頻繁模式挖掘的基本步驟：

  1. 列舉所有可能的模式

    • 從圖形中提取所有可能的子圖結構。

  2. 計算每個模式出現的次數

    • 統計每個子圖結構在圖形中出現的頻率。

  3. 篩選頻繁模式

    • 設定一個門檻值（T），保留出現次數大於等於T的模式，淘汰其他不頻繁的模式。
    # 簡單的頻繁模式篩選範例
def filter_frequent_patterns(patterns, threshold):
    frequent_patterns = []
    for pattern, count in patterns.items():
        if count >= threshold:
            frequent_patterns.append(pattern)
    return frequent_patterns

  4. 合併相容的模式

    • 檢查不同頻繁模式之間的相容性，將具有相同節點的模式進行合併，形成更大的模式。

  5. 重複篩選與合併

    • 對新形成的較大模式重複進行頻率計算與篩選，直到無法形成新的頻繁模式為止。

同構問題的處理

在計算模式出現次數時，需要考慮同構（isomorphism）的問題，即相同的節點和邊可能以不同的方式匹配到模式範本上。例如，對於模式A-(friend_of)-B，如果Jordan是Kim的朋友，同時Kim也是Jordan的朋友，那麼這是算一個例項還是兩個？需要根據具體需求決定是否將這些對稱的模式視為獨立例項或合併為一個。

圖形特徵萃取

圖形特徵萃取是將圖形結構轉化為可用於機器學習的特徵向量的過程。這些特徵可以是區域性特徵（與單個節點或邊相關）或全域性特徵（與整個圖形或子圖相關）。

網域獨立特徵

網域獨立特徵是指那些不依賴於圖形具體意義的特徵，可以應用於任何圖形資料。常見的網域獨立特徵包括：

  1. 節點的入度與出度

    • 統計節點的入邊數與出邊數。

  2. 鄰近節點數量

    • 計算節點在特定跳數內的鄰近節點數量。

  3. 三角形計數

    • 統計節點參與形成的三角形數量。
    # 簡單的三角形計數範例
import networkx as nx

def count_triangles(G):
    triangles = nx.triangles(G)
    return triangles

網域相依特徵

網域相依特徵則是根據圖形所代表的具體領域知識提取的特徵。例如，在社交網路中，可能會考慮節點的互動頻率、關係親密度等。

圖形嵌入（Graph Embedding）

圖形嵌入是一種特殊的特徵向量，能夠將節點的鄰域結構進行壓縮與表示。常見的圖形嵌入方法包括DeepWalk、Node2Vec等。

圖形特徵的應用

圖形特徵可以單獨使用以提供對資料的洞察，也可以與傳統的機器學習特徵結合，增強模型的表現。在機器學習流程中，特徵萃取是關鍵步驟之一，將圖形資料轉化為適當的表示形式後，可以進一步應用於監督學習任務中。

隨著圖形資料的日益普及，圖形演算法與機器學習的結合將會越來越緊密。未來，我們可以期待更多創新性的圖形表示學習方法，以及更高效的圖形處理技術，以應對日益增長的資料規模與複雜度。

技術選型考量

在實際應用中，選擇合適的圖形演算法與特徵萃取方法需要根據具體的資料特性與業務需求進行綜合考量。例如，對於大規模圖形資料，可能需要採用分散式處理框架以提升計算效率；而對於特定領域的圖形資料，則可能需要結合領域知識設計專門的特徵萃取方法。

實踐建議

  1. 深入理解資料特性

    • 在進行圖形分析前，充分理解資料的來源、結構與特性。

  2. 選擇合適的演算法

    • 根據具體需求選擇適當的圖形演算法與特徵萃取方法。

  3. 結合領域知識

    • 將領域專家知識融入特徵萃取與模型設計中，提升模型的實用性。

  4. 持續最佳化與迭代

    • 根據實際應用效果，不斷最佳化和迭代圖形分析流程與模型引數。

透過上述方法，我們可以充分發揮圖形演算法與機器學習的優勢，從複雜的圖形資料中挖掘出更多有價值的資訊與洞察。以下是範例程式碼：

import networkx as nx
import matplotlib.pyplot as plt

# 建立一個簡單的有向圖
G = nx.DiGraph()
G.add_edges_from([('Alex', 'Bob'), ('Alex', 'Fiona'), ('Fiona', 'George'), ('Fiona', 'Ivy'), ('Fiona', 'Justin')])

# 繪製圖形
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='lightblue', edge_color='gray')
plt.title("簡單有向圖範例")
plt.show()

# 計算並輸出節點的入度與出度
for node in G.nodes():
    in_degree = G.in_degree(node)
    out_degree = G.out_degree(node)
    print(f"節點 {node}: 入度 = {in_degree}, 出度 = {out_degree}")

# #### 內容解密：
# 1. 首先，我們使用`networkx`函式庫建立了一個簡單的有向圖物件`G`。
# 2. 透過`add_edges_from`方法新增了多條有向邊，定義了節點之間的關係。
# 3. 使用`matplotlib`繪製了圖形，並設定節點顏色、邊顏色等視覺引數。
# 4. 計算並輸出了每個節點的入度與出度，這些是基本的圖形特徵。

圖表翻譯：

此圖示展示了一個簡單的有向圖結構，其中節點代表實體（如人物），有向邊代表實體間的關係（如Alex認識Bob）。透過分析節點的入度與出度，我們可以初步瞭解各個節點在圖形中的重要程度與連線特性。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。