樹內核：量化樹結構數據之間的相似性

網絡或圖是一種節點形式的結構化數據，它們之間的關係由鏈接或邊描述。 圖中的節點和邊可能有幾個屬性，這些屬性可能是數字的或分類的，甚至更複雜。

如今，大量數據以網絡或圖表的形式提供。 例如，萬維網及其網頁和超鏈接、社交網絡、語義網絡、生物網絡、科學文獻的引用網絡等等。

樹是一種特殊類型的圖，自然適合表示多種類型的數據。 樹木分析是計算機和數據科學中的一個重要領域。 在本文中，我們將著眼於樹中鏈接結構的分析。 特別是，我們將關注樹核，這是一種將樹圖相互比較的方法，使我們能夠對它們的相似性或差異進行量化測量。 這是許多現代應用程序（例如分類和數據分析）的重要過程。

結構化數據的無監督分類

分類是機器學習和數據分析的重要組成部分。 一般來說，分類可以是有監督的，也可以是無監督的。 在監督分類中，類別是已知的，並且分類模型是根據已經給出正確類別的訓練數據構建的。 相比之下，無監督分類試圖識別未知的類別，根據某種相似性度量將數據分組。

無監督分類可以與圖論相結合來識別相似的樹網絡組。 樹數據結構用於對來自多個域的對象進行建模。 例如，在自然語言處理 (NLP) 中，解析樹被建模為有序的標記樹。 在自動推理中，許多問題是通過搜索來解決的，其中搜索空間表示為一棵樹，其頂點與搜索狀態相關聯，邊表示推理步驟。 此外，半結構化數據（例如 HTML 和 XML 文檔）可以建模為有序的、帶標籤的樹。

這些領域可以通過無監督分類技術進行有用的分析。 在 NLP 中，分類可用於自動將一組句子分組為問題、命令和語句。 同樣，可以通過將分類方法應用於其 HTML 源來識別相似網站組。 在每種情況下，我們所需要的只是一種衡量兩棵樹彼此“相似”程度的方法。

維度的詛咒

大多數分類算法都要求將數據轉化為向量化的形式，表示數據在特徵空間中的特徵值，以便在特徵空間中使用線性代數對數據進行分析。 在結構化或半結構化數據中，如樹，結果向量的維數（即特徵空間中的特徵數量）可能非常高，因為特徵空間必須保留有關結構的信息。

考慮到許多分類技術無法根據輸入的維度有效地擴展，這可能是一個重大缺陷。 換句話說，它們的分類能力隨著輸入維度的增加而降低。 這個問題被稱為維度災難。

要了解這種性能下降的原因，請考慮維度為d的空間X。 假設X包含一組均勻分佈的點。 如果X的維數增加，則保持相同密度所需的點數必須呈指數增加。 換句話說，輸入的維度越多，該數據就越有可能是稀疏的。 通常，稀疏數據集無法提供足夠的信息來構建良好的分類器，因為數據元素之間的相關性太弱以至於算法無法檢測到。

上面的每個特徵空間都包含八個數據點。 在一維空間上，很容易識別出一組左邊五個點，右邊三個點。 將這些點擴展到更多數量的特徵（即維度）上會使找到這些組變得更加困難。 在實際應用中，特徵空間很容易擁有數百個維度。

當有關域的信息可以有效地用於選擇一組可管理的特徵時，結構化數據的矢量化表示是合適的。 當此類信息不可用時，最好使用可以直接處理結構化數據的技術，而無需在向量空間中執行操作。

內核方法

內核方法避免了將數據轉換為向量形式的需要。 他們需要的唯一信息是測量數據集中每對項目的相似性。 這種測量稱為核，確定它的函數稱為核函數。 核方法在特徵空間中尋找線性關係。 在功能上，它們相當於在特徵空間中取兩個數據點的點積，確實特徵設計可能仍然是核函數設計中有用的一步。 然而，核方法避免直接對特徵空間進行操作，因為可以證明可以用核函數替換點積，只要核函數是可以將數據作為輸入的對稱正半定函數在它原來的空間裡。

因此，使用核函數的優點是可以分析巨大的特徵空間，計算複雜度不取決於特徵空間的大小，而是取決於核函數的複雜度，這意味著核方法不會受到詛咒的維度。

如果我們考慮一個由n 個示例組成的有限數據集，我們可以通過生成一個大小始終為n × n的核矩陣來獲得數據內相似性的完整表示。 該矩陣與每個單獨示例的大小無關。 當要分析具有大特徵空間的小樣本數據集時，此屬性很有用。

一般來說，核方法基於對數據表示問題的不同回答。 不是將輸入點映射到特徵空間，而是通過核矩陣K中的成對比較來表示數據，並且所有相關分析都可以在核矩陣上執行。

許多數據挖掘方法可以被內核化。 要使用核方法（例如使用支持向量機）對樹結構數據實例進行分類，只需定義一個有效（對稱正定）核函數k : T × T → R ，也稱為樹核。 在實際有用的樹核的設計中，人們會要求它們在樹的大小上在多項式時間內是可計算的，並且能夠檢測同構圖。 這樣的樹核稱為完整樹核。

樹核

現在，讓我們介紹一些有用的樹核來測量樹的相似性。 主要思想是為數據集中的每對樹計算核，以構建核矩陣，然後可以將其用於對樹集進行分類。

字符串內核

首先，我們將從對字符串內核的簡短介紹開始，這將有助於我們介紹另一種基於將樹轉換為字符串的內核方法。

讓我們將num y (s)定義為字符串s中子字符串y的出現次數，其中| 小號| 表示字符串的長度。 我們將在這裡描述的字符串內核定義為：

K串(S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

其中F是同時出現在S 1和S 2中的子串集合，參數w s用作權重參數（例如，強調重要的子串）。 正如我們所看到的，當一對字符串共享許多公共子字符串時，該內核賦予它們更高的值。

基於樹轉字符串的樹核

我們可以使用這個字符串內核來構建一個樹內核。 這個內核背後的想法是以系統的方式將兩棵樹轉換為兩個字符串，對樹的結構進行編碼，然後將上述字符串內核應用於它們。

我們將兩棵樹轉換為兩個字符串，如下所示：

令T表示目標樹之一， label(n s )表示T中節點n s的字符串標籤。 tag(n s )表示以n s為根的T的子樹的字符串表示。 因此，如果n root是T的根節點，則tag(n root )是整個樹T的字符串表示形式。

接下來，讓string(T) = tag(n root )表示T的字符串表示。 我們將以自下而上的方式遞歸地應用以下步驟來獲得string(T) ：

• 如果節點n s是葉節點，讓tag(n s ) = “[” + label(n s ) + “]” （這裡的+是字符串連接運算符）。
• 如果節點n s不是葉節點並且有c個子節點 n 1 , n 2 , ... , n c , 對tag(n 1 ), tag(n 2 ), ... , tag(n c )進行詞法排序以獲得tag (n 1* ), tag(n 2* ), ... , tag(n c* )和 let tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + ... + 標籤(n c* ) + “]” 。

下圖顯示了這種樹到字符串轉換的示例。 結果是一個以“[”等開始分隔符開始並以“]”結尾的字符串，每個嵌套的分隔符對對應於以特定節點為根的子樹。

現在我們可以將上述轉換應用於兩棵樹T 1和T 2 ，以獲得兩個字符串S 1和S 2 。 從那裡，我們可以簡單地應用上面描述的字符串內核。

通過兩個字符串S 1和S 2在T 1和T 2之間的樹內核現在可以給出為：

K tree (T 1 , T 2 ) = K string ( string(T 1 ), string(T 2 ) ) = K string (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 ) w

在大多數應用中，權重參數變為w | 小號| ，根據長度對子字符串進行加權| 小號| . w |的典型加權方法小號| 是：

• 恆權重（ w | s | = 1 ）
• k -頻譜加權（ w | s | = 1 if | s | = k ， w | s | = 0否則）
• 指數加權（ w | s | = λ | s |其中0 ≤ λ ≤ 1是衰減率）

要計算內核，確定所有公共子串F併計算它們在S 1和S 2中出現的次數就足夠了。 這個尋找公共子串的額外步驟是一個經過充分研究的問題，可以在O( | S 1 | + | S 2 | )中完成，使用後綴樹或後綴數組。 如果我們假設描述節點標籤所需的最大字母數（例如位、字節或字符）是恆定的，則轉換後的字符串的長度為| S 1 | = O( | T 1 | )和| S 2 | = O( | T 2 | ) 。 因此，計算核函數的計算複雜度為O( | T 1 | + | T 2 | ) ，是線性的。

基於子路徑的樹內核

上面的樹內核使用水平或廣度優先的方法將樹轉換為字符串。 雖然這種方法非常簡單，但這種轉換意味著它不能直接以原始形式對樹進行操作。

本節將定義一個對樹中的垂直結構進行操作的樹內核，允許內核直接對樹進行操作。

從根到其中一個葉子的路徑的子部分稱為子路徑，子路徑集是樹中包含的所有子路徑的集合：

假設我們要在兩棵樹T 1和T 2之間定義一個樹核K(T 1 , T 2 ) 。 通過使用子路徑集，我們可以將此樹內核定義為：

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | p |

其中num p (T)是子路徑p在樹T中出現的次數， | p | 是子路徑p中的節點數， P是T 1和T 2中所有子路徑的集合。 w | p | 是權重，與上一節介紹的類似。

在這裡，我們展示了一個使用深度優先搜索的內核的簡單實現。 儘管該算法以二次時間運行，但使用後綴樹或後綴數組或多鍵快速排序算法的擴展存在更有效的算法，平均可以達到線性時間（ O( | T 1 | log | T 2 | ) ）：

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

在這個例子中，我們使用了加權參數 w | 小號| w | p | = 1 。 這使所有子路徑具有相同的權重。 但是，在許多情況下，使用k譜加權或某些動態分配的權重值是合適的。

挖礦網站

在結束之前，讓我們簡要地看一下樹分類的一個實際應用：網站分類。 在許多數據挖掘環境中，了解某些數據來自什麼“類型”網站是有益的。 事實證明，由於類似服務的網頁結構相似，因此可以使用樹非常有效地對來自不同網站的頁面進行分類。

我們如何做到這一點？ HTML 文檔有一個邏輯嵌套結構，它非常像一棵樹。 每個文檔包含一個根元素，其中嵌套了其他元素。 HTML 標籤中的嵌套元素在邏輯上等同於該標籤的子節點：

讓我們看一些可以將 HTML 文檔轉換為樹的代碼：

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

這將產生一個看起來像這樣的樹數據結構：

上面的實現使用了幾個有用的 Python 庫：NetworkX，用於處理複雜的圖形結構，Beautiful Soup，用於從 Web 中提取數據和操作文檔。

調用html_to_dom_tree(soup.find("body"))將返回一個以網頁的<body>元素為根的 NetworkX 圖形對象。

假設我們想在一組 1,000 個網站主頁中查找組。 通過將每個主頁轉換成這樣的樹，我們可以比較每個主頁，例如使用上一節中給出的子路徑樹內核。 通過這些相似性測量，我們可以發現，例如，電子商務網站、新聞網站、博客和教育網站很容易通過它們彼此的相似性來識別。

結論

在本文中，我們介紹了將樹狀結構數據元素相互比較的方法，並展示瞭如何將核方法應用於樹，以獲得它們相似性的可量化度量。 核方法已被證明是在高維空間中操作時的絕佳選擇，這是使用樹結構時的常見情況。 這些技術使用經過充分研究的在核矩陣上運行的方法為進一步分析大量樹奠定了基礎。

在許多實際領域中都會遇到樹結構，例如 XML 和 HTML 文檔、化合物、自然語言處理或某些類型的用戶行為。 正如從 HTML 構建樹的示例中所展示的，這些技術使我們能夠在這些域中執行有意義的分析。