圖形化實體解析技術Jaccard相似度實作

利用圖資料函式庫和 Jaccard 相似度進行實體解析，能有效地識別和合併代表相同真實世界實體的不同資料記錄。透過 TigerGraph 的 GSQL 查詢語言，我們可以建立帳戶與使用者之間的關聯，並計算其相似度。首先，初始化階段會為每個帳戶建立對應的使用者節點，並將其屬性連線到使用者。接著，利用 connect_jaccard_sim 查詢計算使用者之間的 Jaccard 相似度，並根據設定的閾值建立 Same_As 邊，將相似使用者連線起來。在 GraphStudio 中，可以透過視覺化功能觀察使用者社群的結構。更進一步，可以匯入屬性權重和近似匹配技術，提升實體解析的準確性。屬性權重讓不同屬性在相似度計算中扮演不同的角色，而近似匹配技術則能處理拼寫錯誤或微小差異的情況。這些技術的結合，能有效地解決實體解析中的挑戰，並為更深入的資料分析奠定基礎。

圖形化實體解析技術：以Jaccard相似度為基礎的實作方法

在實體解析的過程中，實體的相似度計算是至關重要的步驟。本文將詳細介紹如何利用Jaccard相似度進行實體解析，並透過TigerGraph的GraphStudio進行操作。

初始化階段

在我們的模型中，帳戶（Account）代表數位身份，而使用者（User）則代表真實的人。原始資料函式庫僅包含帳戶。初始化步驟為每個帳戶建立一個獨特的臨時使用者，並將該帳戶的所有屬性頂點連線到對應的使用者頂點。

具體步驟：

1. 執行GSQL查詢initialize_users。
2. 該查詢為每個沒有鄰近使用者的帳戶建立一個使用者頂點，並建立Has_Account邊連線帳戶和使用者。
3. 將帳戶的所有屬性頂點（例如IP、Email、Device等）連線到對應的使用者頂點。

CREATE QUERY initialize_users() FOR GRAPH Entity_Resolution SYNTAX v2 {
    // 為每個帳戶建立一個使用者頂點，並連線屬性
    Accounts = SELECT s FROM Account:s
               WHERE s.outdegree("Has_Account") == 0
               ACCUM
               INSERT INTO User VALUES(s.id),
               INSERT INTO Has_Account VALUES(s.id, s);
    
    // 連線使用者的屬性
    IPs = SELECT attr FROM Accounts:s -(Has_IP:e)- IP:attr
          ACCUM
          INSERT INTO User_IP VALUES(s.id, attr);
    
    Emails = SELECT attr FROM Accounts:s -(Has_Email:e)- Email:attr
             ACCUM
             INSERT INTO User_Email VALUES(s.id, attr);
    // 省略其他屬性型別的程式碼
}

內容解密：

1. 第一個SELECT區塊為每個沒有鄰近使用者的帳戶建立一個使用者頂點，並建立Has_Account邊。
2. 後續區塊將帳戶的屬性頂點連線到對應的使用者頂點，例如IP和Email。
3. 這樣每個使用者初始時具有與其帳戶相同的屬性鄰域。

相似度檢測

Jaccard相似度計算兩個實體共有的屬性數量，除以它們總共有的屬性數量。每個屬性比較結果為是或否，相似度範圍在0到1之間。

具體步驟：

1. 執行GSQL查詢connect_jaccard_sim，並可設定閾值（預設為0.5）。
2. 查詢計算每對使用者頂點的Jaccard相似度，若相似度達到或超過閾值，則建立Same_As邊連線兩個使用者。

圖表說明：

此圖示展示了使用者A和使用者B的Jaccard相似度計算範例。

  graph LR
    A[User A] -->|Has_Email|> Email65
    A -->|Has_Device|> Device87
    B[User B] -->|Has_Email|> Email65
    B -->|Has_Device|> Device87
    B -->|Has_Phone|> Phone23
    B -->|Has_Phone|> Phone99

圖表翻譯： 此圖表示兩個使用者A和B的屬性連線。使用者A具有Email65和Device87兩個屬性，而使用者B具有Email65、Device87、Phone23和Phone99四個屬性。兩個使用者共有的屬性是Email65和Device87，因此Jaccard相似度為2/4 = 0.5。

如何視覺化使用者社群

在TigerGraph的GraphStudio中，可以使用「Explore Graph」頁面來視覺化使用者社群。

具體步驟：

1. 選擇頂點：選取User頂點型別，並輸入要查詢的頂點ID。
2. 展開頂點：選取多個頂點後，使用「Expand from vertices」功能。
3. 設定擴充套件步驟：選擇要遍歷的邊和目標頂點型別，並設定遍歷的跳數。
4. 調整佈局：使用佈局選單調整視覺化結果。

未來可以進一步最佳化Jaccard相似度的計算方法，例如結合其他相似度指標，或是利用更高效的圖演算法來提升實體解析的準確性和效率。

參考資料

• TigerGraph官方檔案
• GraphStudio使用手冊

程式碼補充說明

上述GSQL查詢展示瞭如何初始化使用者頂點並計算Jaccard相似度。透過這些查詢，我們可以有效地建立實體之間的關聯，並進行進一步的分析和處理。

CREATE QUERY connect_jaccard_sim(FLOAT threshold) FOR GRAPH Entity_Resolution SYNTAX v2 {
    // 計算每對使用者的Jaccard相似度
    Users = SELECT s FROM User:s;
    
    // 省略相似度計算和邊建立的程式碼
}

內容解密：

1. connect_jaccard_sim查詢接受一個閾值引數，用於決定是否建立Same_As邊。
2. 查詢計算每對使用者頂點的Jaccard相似度，並根據閾值建立相應的邊。
3. 這樣可以將相似的使用者聚類別在一起，形成社群。

透過上述步驟和程式碼，我們可以實作根據Jaccard相似度的實體解析，並視覺化結果以便進一步分析和應用。

圖形化實體解析技術詳解：根據GSQL的實作與最佳化

在現代資料分析與圖資料函式庫技術中，實體解析（Entity Resolution）是一項關鍵任務，旨在識別和合並代表相同真實世界實體的不同資料記錄。本文將探討如何利用圖資料函式庫技術與GSQL查詢語言實作高效的實體解析，並詳細解析其背後的技術原理與實作細節。

實體解析的核心挑戰

實體解析的主要挑戰在於如何準確識別不同資料來源中代表相同實體的記錄。傳統方法通常依賴於精確匹配或簡單的相似性度量，但在處理複雜、異構資料時，這些方法往往無法滿足需求。圖形化實體解析技術透過構建實體間的關聯圖譜，能夠更有效地捕捉實體之間的複雜關係。

GSQL查詢語言簡介

GSQL（Graph Query Language）是一種專為圖資料函式庫設計的查詢語言，它提供了強大的圖遍歷和資料處理能力。在實體解析任務中，GSQL能夠高效地處理複雜的圖查詢和資料聚合操作，為實體解析提供了堅實的技術基礎。

connect_jaccard_sim查詢詳解

connect_jaccard_sim查詢的主要功能是計算不同實體之間的Jaccard相似度，並根據相似度閾值建立實體間的關聯。以下是該查詢的核心程式碼片段：

Others = SELECT B FROM 
    Start:A -()- (IP|Email|Phone|Last_Name|Address|Device):n -()- User:B
WHERE B != A
ACCUM 
    A.@intersection += (B -> 1), 
    @@path_count += 1;

程式碼解析

1. 圖遍歷模式：FROM子句定義了一個雙跳圖遍歷模式，從起始頂點A出發，經過任意型別的邊到達中間頂點n，再經過任意型別的邊到達目標頂點B。
2. 條件過濾：WHERE子句確保A和B不是同一個頂點，避免自環的情況。
3. 累積操作：ACCUM子句進行兩項累積操作：
   • A.@intersection += (B -> 1)：記錄A與B的共同鄰居數量。
   • @@path_count += 1：統計總路徑數，用於後續的統計分析。

內容解密：

此段程式碼透過圖遍歷計算每對使用者之間的共同屬性數量，為後續的Jaccard相似度計算奠定基礎。Jaccard相似度是一種衡量兩個集合相似程度的指標，其計算公式為兩個集合交集的大小除以並集的大小。在此處，交集的大小即為共同鄰居的數量，而並集的大小則是兩個使用者鄰居集合大小之和減去交集的大小。

Jaccard相似度計算與實體關聯建立

在完成共同鄰居計算後，接下來的查詢步驟負責計算Jaccard相似度並建立實體間的關聯：

Result = SELECT A FROM User:A
ACCUM 
    FOREACH (B, overlap) IN A.@intersection DO
        FLOAT score = overlap * 1.0 / (@@deg.get(A) + @@deg.get(B) - overlap),
        IF score > threshold THEN
            INSERT INTO EDGE SameAs VALUES (A, B, score),
            @@insert_count += 1,
            IF score != 1 THEN
                @@jaccard_heap += SimilarityTuple(A, B, score)
        END
    END
END;

程式碼解析

1. 相似度計算：對於每個使用者A，遍歷其關聯使用者B及共同鄰居數量overlap，計算Jaccard相似度分數score。
2. 關聯建立：若score超過預設閾值，則在A和B之間建立SameAs邊，表示兩者被識別為相同實體。
3. 統計資訊更新：更新插入計數@@insert_count，並將相似度資訊存入@@jaccard_heap堆積疊中。

內容解密：

此段程式碼完成了實體解析的核心步驟：根據Jaccard相似度建立實體間的關聯。透過SameAs邊的建立，不同資料記錄之間的關聯得以明確標示，為後續的資料整合與分析提供了基礎。

實體合並與社群檢測

在完成實體關聯建立後，merge_connected_users查詢負責合並相關的實體社群：

WHILE (Updated_users.size() > 0) DO
    Updated_users = SELECT t
    FROM Updated_users:s -(SameAs:e)- User:t
    ACCUM 
        t.@min_user_id += s.@min_user_id
    HAVING 
        t.@min_user_id != t.@min_user_id'
    ;
    iteration = iteration + 1;
END;

程式碼解析

1. 最小ID傳播：透過SameAs邊，將最小使用者ID在相關聯的使用者之間傳播。
2. 迭代更新：重複執行傳播過程，直到所有使用者的最小ID不再變化。
3. 結果收斂：當沒有使用者的最小ID發生變化時，迴圈結束，實體合並完成。

內容解密：

此段程式碼透過最小ID傳播機制，實作了相關實體的合並。最終，每個實體社群都會選出一個代表性的主實體，其他實體將被重定向到該主實體，從而實作實體解析的最終目標。

1. 效能最佳化：進一步最佳化GSQL查詢效能，提升大規模資料處理能力。
2. 多源資料融合：探索將多源異構資料納入實體解析框架，提高實體解析的全面性和準確性。
3. 應用拓展：將圖形化實體解析技術應用於更多領域，如金融風控、社交網路分析等。

透過不斷最佳化和拓展，圖形化實體解析技術將在資料驅動的決策支援系統中扮演更加關鍵的角色。

圖形化實體解析技術的進階應用

在前一節中，我們探討了一種簡單的根據圖的實體解析技術。然而，這種方法過於基礎，無法滿足現實世界的需求。它依賴於屬性值的精確匹配，而我們需要允許幾乎相同的值，這些值是由於無意的和有意的拼寫變化而產生的。在本文中，我們將引入權重來調整不同屬性的相對重要性，並提供一種用於字串值近似匹配的技術。

初始化設定

我們仍然使用相同的圖模型，其中 User 頂點代表真實的人，而 Account 頂點代表數字賬戶。因此，我們仍然使用 initialize_users 查詢來設定初始的 User 頂點集合。

// 初始化使用者資料
CALL initialize_users();

我們增加了 util_set_weights 查詢作為另一個初始化步驟。該查詢接受六個屬性（IP、Email、Phone、Address、Last_Name 和 Device）的權重並儲存它們。如果這是一個關聯式資料函式庫，我們會將這些權重儲存在一個表中。由於這是一個圖，我們將它們儲存在一個頂點中。我們只需要一個頂點，因為一個頂點可以有多個屬性。然而，我們將使用一個 map 型別的屬性，它將有六個鍵值對。這允許我們像查詢表一樣使用 map：告訴我鍵（屬性名稱），我將告訴你值（權重）。

// 設定屬性權重
CALL util_set_weights(
  {IP: 0.1, Email: 0.3, Phone: 0.2, Address: 0.1, Last_Name: 0.2, Device: 0.1}
);

內容解密：

• util_set_weights 查詢允許我們為不同的屬性設定不同的權重，這些權重將用於後續的相似度計算。
• 權重的設定取決於屬性的重要性，例如，如果兩個使用者具有相同的 Email，這可能比他們具有相同的 IP 更能表明他們是同一個人。
• 我們使用 map 型別來儲存這些權重，這使得我們可以靈活地根據屬性名稱檢索對應的權重。

加權精確匹配

在加權精確匹配中，我們在 User 之間建立加權連線，其中更高的權重表示更強的相似性。連線的淨權重是兩個 User 共有的每個屬性的貢獻之和。

// 執行加權匹配連線
CALL connect_weighted_match();

內容解密：

• connect_weighted_match 查詢計算 User 之間的相似度，並根據共有的屬性建立加權的 Same_As 邊。
• 在這個過程中，首先從 User 到 Attribute 的連線被記錄，並且每個屬性的權重被累積。
• 然後，從 Attribute 到 User 的連線被聚合，以計算兩個 User 之間的總權重，從而建立加權的 Same_As 邊。

圖示解析

Figure11-10 展示了加權匹配計算的兩個階段。在第一階段，我們查詢從 User 到 Attribute 的連線，並在每個屬性上為每個 User 的連線記錄一個權重。在第二階段，我們查詢相同的連線，但方向相反，以 User 為目的地。兩個 User 之間的權重被用來建立一條加權的 Same_As 邊。

圖表翻譯： 此圖示展示了加權匹配的計算過程，包括兩個階段：第一階段是從 User 到 Attribute 的連線記錄，第二階段是從 Attribute 到 User 的連線聚合，最終建立加權的 Same_As 邊。

近似匹配技術

在某些情況下，我們希望允許屬性值之間的近似匹配，例如 Last_Name 和 Address。這可以透過使用字串相似度度量（如 Jaro-Winkler 距離或 Levenshtein 距離）來實作。

// 執行近似匹配連線
CALL connect_approximate_match();

內容解密：

• connect_approximate_match 查詢用於建立 User 之間的近似匹配連線，根據字串相似度度量。
• 這種方法允許我們捕捉由於拼寫錯誤或小變化導致的不完全匹配，從而提高實體解析的準確性。

內容解密：

• util_print_vertices 查詢用於列印 User 頂點的資訊，包括他們的屬性和連線。
• 這有助於我們驗證實體解析的結果，並根據需要進行調整。

未來，我們可以進一步探索使用機器學習技術來自動學習屬性的最佳權重，從而進一步提高實體解析的準確性和效率。此外，我們還可以研究如何將這種方法應用於更大規模的資料集，並探索其在不同領域的應用潛力。

參考資料

• Graph-Based Entity Resolution
• Entity Resolution Techniques

透過結合圖形化實體解析技術和機器學習方法，我們可以開發出更為先進的實體解析系統，以滿足日益增長的資料整合和分析需求。