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

今天，大量的數據是可用的網絡或圖形的形式。例如，萬維網，其網頁和超鏈接，社會網絡，語義網絡，生物網絡，科學文獻的引用網絡，等等。

36大數據專稿， 本文由36大數據翻譯組-云泥 ，任何不標明譯者和出處以及本文鏈接http://www.36dsj.com/archives/43411 的均為侵權。

數（數據結構名詞）

樹狀圖是一種數據結構，它是由n（n>=1）個有限節點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：每個節點有零個或多個子節點；沒有父節點的節點稱為根節點；每一個非根節點有且只有一個父節點；除了根節點外，每個子節點可以分為多個不相交的子樹；

樹是一種特殊類型的圖形，很自然地適合于表示多種類型的數據。樹木的分析是計算機和數據科學中的一個重要領域。在這篇文章中，我們將看看樹鏈接結構的分析。特別是，我們將專注于樹的內核，一種方法用來比較樹圖形彼此，使我們能夠量化的測量它們的相似性或差異。這是一個重要的過程，對于很多如分類和數據分析的現代應用。

結構化數據的無監督分類

分類是機器學習和數據分析的重要組成部分。在一般情況下，分類可以監督或無監督。在監督分類中，分類是已知的，一個分類模型是從訓練數據中構造的。這個訓練數據已經給了正確的分類。通過對比，無監督分類試圖找出分類，其中沒有已知的部分，分組數據分類基于一些相似性的措施。無監督分類法可以與圖的理論相結合去識別相似的樹網絡。樹數據結構用于幾個域模型對象。在自然語言處理（NLP），例如，解析樹被建模為有序，標記樹。在自動推理，許多問題都被搜索解決了，搜索空間被代表為一棵樹，其頂點與搜索狀態，和邊緣代表的推理步驟。另外，半結構化數據，如HTML和XML文檔，可以模擬為有序，標記的樹。

這些領域可以通過非監督分類技術進行有效的分析。在自然語言處理（NLP），分類可以用來自動將一組句子分成問題，命令和語句。同樣的，相似網站群可以通過HTML源識別分類方法識別。在每一種情況下，我們所需要的是一種衡量”相似”的兩個樹是彼此的方法。

維數災難

大多數分類算法需要將數據轉化成矢量形式，表示在特征空間中的數據的特征值，使數據可以在特征空間利用線性代數分析。在結構化或半結構化數據，如樹木，所得到的向量維數（即特征空間中的特征數）可能會很高，由于特征空間必須保留結構信息。

這可能是一個顯著的缺點，考慮到許多分類技術是不能夠有效地擴展維度輸入。換句話說，它們的分類能力隨著輸入維數的增加而降低。這個問題被稱為”維數災難”。

要想知道這個性能下降的原因，考慮維度D的一個空間X。假設X包含一組均勻分布的點。如果X的維度數量增加，必要的保持相同密度的點的數量必須成倍的增加。換句話說，輸入的維數越大，數據稀疏的可能性越大。一般情況下，稀疏的數據集并沒有給出足夠的信息，以建立一個良好的分類，因為對于檢測算法數據元素之間的相關性太弱。

維數災難

每個特征空間上面都包含了八個數據點。在一維空間上，很容易辨認出左邊一組5個點，和右邊一組3個點。在更高功能上（例如，維度）伸展這些點使它更難找到這些組。在實際應用中，特征空間可以很容易地擁有數百個維度。

一個結構化的數據矢量化是合適的，當有關該域的信息可以有效地用于選擇一個可管理的功能集時。當這些信息不可用時，它是可以用使用的技術直接處理結構化數據，不需要執行在向量空間中的操作。

核方法

核方法避免了將數據轉換成矢量形式的需要。它們所需要的唯一信息是一個集合數據中的每一對的相似性的度量。這種度量被稱為內核，并確定它的函數稱為內核函數。特征空間中的核方法尋找線性關系。在功能上，它們相當于特征空間中的點積的2個數據點，而真正的功能設計，在內核功能設計可能仍然是一個有用的步驟。然而，內核方法避免直接操作在特征空間，因為它可以表明以取代點產品的內核功能是可能的，只要核函數是對稱的，正定函數可以作為輸入的原始空間數據。

使用內涵函數的優點是，一個巨大的特征空間，可以分析與計算復雜度不依賴于特征空間的大小，但是內核功能的復雜性，這意味著內核的方法是沒有災難的維數。

如果我們考慮一個有限的數據集組成的氮的例子，我們可以得到一個通過生成一個內核矩陣，完整的在數據中的相似性表示，其大小始終是nxn。在每個個性化的例子，這個矩陣是獨立的大小。此屬性是有用的，當一個小的數據集的例子有一個大的特征空間進行分析。在一般情況下，內核的方法是基于對數據問題的不同答案。而不是映射到特征空間的輸入點，數據表示通過成對比較的內核矩陣，和所有相關的分析可以進行內在矩陣。

許多數據挖掘方法都可以核化。分類樹結構的數據情況下用內核的方法，如，支持向量機器，它可以定義一個有效（正定）核函數K：T×T→R，也被稱為樹核。在設計切實有用的樹的內核，一個將需要它們是可計算在多項式時間內的樹的大小，并能夠檢測同結構圖。這種樹的內核被稱為完全樹核。

樹核

現在，讓我們來介紹一些有用的樹核，用于測量樹的相似性。其主要思想是計算每一對樹的內核，以便建立一個內核矩陣，然后可用于分類組的樹。

字符串內核

首先，我們就愛你過要開始一個簡短的介紹字符串的內核，這將有助于我們引入另一個內核的方法，是基于轉換成字符串樹。

讓我們來定義numy（S）為一個字符串中的子串出現的次數與Y，|s|表示字符串的長度。我們將在這里描述的字符串內核被定義為：

其中F是在S1和S2出現的子字符串的集合，參數作為一個權重參數（如，強調重要的子字符串）。我們可以看到，這個內核對他們有許多共同的子字符串時提供了更高的價值。

基于樹轉換成字符串的樹核

我們可以使用這個字符串內核來構建一個樹內核。這個內核背后的想法是，將兩根樹轉換成2個字符串，用系統的方法將樹的結構編碼，然后將上面的字符串內核應用到它們中。

我們將兩根樹轉換成兩根弦：

讓T表示一個目標樹和標簽（NS）在T標簽節點。NS字符串標簽（NS）是指T扎根在NS的子樹的字符串表示。所以如果是T的根節點，tag（nroot）是整個樹T的字符串的表現形式。

接下來，讓字符串（t）=tag（nroot）表示T的字符串。我們將遞歸地應用下面的步驟，在一個自下而上的方式獲得字符串（T）：

?如果節點NS是一個葉狀結構，讓tag(ns) = “[” + label(ns) + “]”（在這里+是字符串串聯運算符）。

?如果節點NS不是葉狀結構，并且有C子n1, n2, … , nc, sort tag(n1), tag(n2), … , tag(nc)在詞匯以獲得tag(n1*), tag(n2*), … , tag(nc*), 讓let tag(ns) = “[” + label(ns) + tag(n1*) + tag(n2*) + … + tag(nc*) + “]”。

下面的圖，顯示了這課樹對字符串轉換的一個例子。其結果是一個字符串的起始開口分隔符如”[“和結束的結束一樣，”]”,每一個嵌套的雙對應子樹扎根在一個特定的節點的分隔符。

現在我們可以應用上述轉換的兩顆樹，T1和T2，獲得兩個字符串S1和S2.從那里，我們可以簡單地應用上面描述的字符串內核。

樹核的T1和T2之間通過兩個字符串S1和S2可以給予如下：

基于子路徑的樹核

上面的樹核使用了一個水平的，或者第一個寬度將樹轉換成字符串的方法。雖然這種方法很簡單，但這種轉換意味著它不能直接在其原始形式的樹上操作。

本節將定義一個在樹上操作的樹內核，允許內核在樹上直接操作。

一款一條路徑從根到眾多葉子之一的子路徑集，包含在樹所有子路徑的設置：

讓我們假設我們要定義一個樹核函數K（T1,T2）兩樹之間的T1和T2.利用子路徑集，我們可以定義這棵樹的內核：

在數量（T）是子路徑P數發生在樹T，P是P子節點的數目，和P是在T1和T2的所有子路徑的設置。W | P |是權重，類似于前一節介紹。

這里，我們提出了一個簡單的實現這一內核使用的深度有限搜索。雖然該算法那運行在二次時間，更有效的算法存在使用后綴樹和后綴數組，或延伸的多條快速排序算法，可以平均實現線性時間

（O(|T1|log|T2|)）

在這個例子中，我們使用的加權參數w|s| w|p| = 1。這給所有的子路徑并重。然而，在許多情況下使用K譜線的權重時，或一些動態分配的權重值，是適當的。

深挖網站

在我們結束之前，讓我們簡要地看一個真實的樹分類：分類網站。在許多數據挖掘的背景下，它是有益的，知道什么”類型”來自哪些數據網站。它從不同的網站的網頁上可以相當有效低分類使用樹，因為相似的網頁相似的服務是結構化的。

我們怎么做？HTML文檔的邏輯嵌套結構，它很像一棵樹。每一個文檔包含一個根元素，里面包含了其他元素嵌套。元素嵌套在HTML標簽在邏輯上相當于這個標簽的子節點。

讓我們看一些代碼，可以將一個HTML文檔放到樹上看：

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

實際上述利用幾個有用的Python庫：networkx，對復雜的圖形結構把數據從網絡上取下和操作文件。

我們要在1000個網站的主頁上找到組。通過將每個網頁變成這樣的一棵樹，我們可以相互比較，例如通過使用上一節給出的路徑樹核。通過這些測量的相似性我們可以發現，例如，電子商務網站，新聞網站，博客和教育網站是很容易確定他們的相似性的。

結論

在這篇文章中，我們介紹了樹結構數據元素的比較，并顯示了如何應用內核的方法，以獲得一個可量化的測量他們的相似性。內核的方法已被證明是一個很好的選擇時，在高維空間中一個共同情況下，與樹結構的工作。這些技術為進一步分析大套樹木，使用以及研究的方法，操作過的內核矩陣階段。

樹結構在現實世界中許多領域如XML和HTML文件，遇到化學化合物，自然語言處理，或某些類型的用戶行為。作為從HTML構建樹的例子證明，這些技術使我們能夠在這些領域進行有意義的分析。

原文地址： Tree Kernels: Quantifying Similarity Among Tree-Structured Data

End.

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com