網(wǎng)絡(luò)和圖形是一種節(jié)點(diǎn)形式的結(jié)構(gòu)化數(shù)據(jù)類型，它們之間的關(guān)系描述為鏈接，或邊緣。圖中的節(jié)點(diǎn)和邊可能有幾個(gè)屬性，可能是數(shù)字或分類，甚至更復(fù)雜。

今天，大量的數(shù)據(jù)是可用的網(wǎng)絡(luò)或圖形的形式。例如，萬(wàn)維網(wǎng)，其網(wǎng)頁(yè)和超鏈接，社會(huì)網(wǎng)絡(luò)，語(yǔ)義網(wǎng)絡(luò)，生物網(wǎng)絡(luò)，科學(xué)文獻(xiàn)的引用網(wǎng)絡(luò)，等等。

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

數(shù)（數(shù)據(jù)結(jié)構(gòu)名詞）

樹(shù)狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)；

樹(shù)是一種特殊類型的圖形，很自然地適合于表示多種類型的數(shù)據(jù)。樹(shù)木的分析是計(jì)算機(jī)和數(shù)據(jù)科學(xué)中的一個(gè)重要領(lǐng)域。在這篇文章中，我們將看看樹(shù)鏈接結(jié)構(gòu)的分析。特別是，我們將專注于樹(shù)的內(nèi)核，一種方法用來(lái)比較樹(shù)圖形彼此，使我們能夠量化的測(cè)量它們的相似性或差異。這是一個(gè)重要的過(guò)程，對(duì)于很多如分類和數(shù)據(jù)分析的現(xiàn)代應(yīng)用。

結(jié)構(gòu)化數(shù)據(jù)的無(wú)監(jiān)督分類

分類是機(jī)器學(xué)習(xí)和數(shù)據(jù)分析的重要組成部分。在一般情況下，分類可以監(jiān)督或無(wú)監(jiān)督。在監(jiān)督分類中，分類是已知的，一個(gè)分類模型是從訓(xùn)練數(shù)據(jù)中構(gòu)造的。這個(gè)訓(xùn)練數(shù)據(jù)已經(jīng)給了正確的分類。通過(guò)對(duì)比，無(wú)監(jiān)督分類試圖找出分類，其中沒(méi)有已知的部分，分組數(shù)據(jù)分類基于一些相似性的措施。無(wú)監(jiān)督分類法可以與圖的理論相結(jié)合去識(shí)別相似的樹(shù)網(wǎng)絡(luò)。樹(shù)數(shù)據(jù)結(jié)構(gòu)用于幾個(gè)域模型對(duì)象。在自然語(yǔ)言處理（NLP），例如，解析樹(shù)被建模為有序，標(biāo)記樹(shù)。在自動(dòng)推理，許多問(wèn)題都被搜索解決了，搜索空間被代表為一棵樹(shù)，其頂點(diǎn)與搜索狀態(tài)，和邊緣代表的推理步驟。另外，半結(jié)構(gòu)化數(shù)據(jù)，如HTML和XML文檔，可以模擬為有序，標(biāo)記的樹(shù)。

這些領(lǐng)域可以通過(guò)非監(jiān)督分類技術(shù)進(jìn)行有效的分析。在自然語(yǔ)言處理（NLP），分類可以用來(lái)自動(dòng)將一組句子分成問(wèn)題，命令和語(yǔ)句。同樣的，相似網(wǎng)站群可以通過(guò)HTML源識(shí)別分類方法識(shí)別。在每一種情況下，我們所需要的是一種衡量”相似”的兩個(gè)樹(shù)是彼此的方法。

維數(shù)災(zāi)難

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

這可能是一個(gè)顯著的缺點(diǎn)，考慮到許多分類技術(shù)是不能夠有效地?cái)U(kuò)展維度輸入。換句話說(shuō)，它們的分類能力隨著輸入維數(shù)的增加而降低。這個(gè)問(wèn)題被稱為”維數(shù)災(zāi)難”。

要想知道這個(gè)性能下降的原因，考慮維度D的一個(gè)空間X。假設(shè)X包含一組均勻分布的點(diǎn)。如果X的維度數(shù)量增加，必要的保持相同密度的點(diǎn)的數(shù)量必須成倍的增加。換句話說(shuō)，輸入的維數(shù)越大，數(shù)據(jù)稀疏的可能性越大。一般情況下，稀疏的數(shù)據(jù)集并沒(méi)有給出足夠的信息，以建立一個(gè)良好的分類，因?yàn)閷?duì)于檢測(cè)算法數(shù)據(jù)元素之間的相關(guān)性太弱。

維數(shù)災(zāi)難

每個(gè)特征空間上面都包含了八個(gè)數(shù)據(jù)點(diǎn)。在一維空間上，很容易辨認(rèn)出左邊一組5個(gè)點(diǎn)，和右邊一組3個(gè)點(diǎn)。在更高功能上（例如，維度）伸展這些點(diǎn)使它更難找到這些組。在實(shí)際應(yīng)用中，特征空間可以很容易地?fù)碛袛?shù)百個(gè)維度。

一個(gè)結(jié)構(gòu)化的數(shù)據(jù)矢量化是合適的，當(dāng)有關(guān)該域的信息可以有效地用于選擇一個(gè)可管理的功能集時(shí)。當(dāng)這些信息不可用時(shí)，它是可以用使用的技術(shù)直接處理結(jié)構(gòu)化數(shù)據(jù)，不需要執(zhí)行在向量空間中的操作。

核方法

核方法避免了將數(shù)據(jù)轉(zhuǎn)換成矢量形式的需要。它們所需要的唯一信息是一個(gè)集合數(shù)據(jù)中的每一對(duì)的相似性的度量。這種度量被稱為內(nèi)核，并確定它的函數(shù)稱為內(nèi)核函數(shù)。特征空間中的核方法尋找線性關(guān)系。在功能上，它們相當(dāng)于特征空間中的點(diǎn)積的2個(gè)數(shù)據(jù)點(diǎn)，而真正的功能設(shè)計(jì)，在內(nèi)核功能設(shè)計(jì)可能仍然是一個(gè)有用的步驟。然而，內(nèi)核方法避免直接操作在特征空間，因?yàn)樗梢员砻饕匀〈c(diǎn)產(chǎn)品的內(nèi)核功能是可能的，只要核函數(shù)是對(duì)稱的，正定函數(shù)可以作為輸入的原始空間數(shù)據(jù)。

使用內(nèi)涵函數(shù)的優(yōu)點(diǎn)是，一個(gè)巨大的特征空間，可以分析與計(jì)算復(fù)雜度不依賴于特征空間的大小，但是內(nèi)核功能的復(fù)雜性，這意味著內(nèi)核的方法是沒(méi)有災(zāi)難的維數(shù)。

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

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

樹(shù)核

現(xiàn)在，讓我們來(lái)介紹一些有用的樹(shù)核，用于測(cè)量樹(shù)的相似性。其主要思想是計(jì)算每一對(duì)樹(shù)的內(nèi)核，以便建立一個(gè)內(nèi)核矩陣，然后可用于分類組的樹(shù)。

字符串內(nèi)核

首先，我們就愛(ài)你過(guò)要開(kāi)始一個(gè)簡(jiǎn)短的介紹字符串的內(nèi)核，這將有助于我們引入另一個(gè)內(nèi)核的方法，是基于轉(zhuǎn)換成字符串樹(shù)。

讓我們來(lái)定義numy（S）為一個(gè)字符串中的子串出現(xiàn)的次數(shù)與Y，|s|表示字符串的長(zhǎng)度。我們將在這里描述的字符串內(nèi)核被定義為：

其中F是在S1和S2出現(xiàn)的子字符串的集合，參數(shù)作為一個(gè)權(quán)重參數(shù)（如，強(qiáng)調(diào)重要的子字符串）。我們可以看到，這個(gè)內(nèi)核對(duì)他們有許多共同的子字符串時(shí)提供了更高的價(jià)值。

基于樹(shù)轉(zhuǎn)換成字符串的樹(shù)核

我們可以使用這個(gè)字符串內(nèi)核來(lái)構(gòu)建一個(gè)樹(shù)內(nèi)核。這個(gè)內(nèi)核背后的想法是，將兩根樹(shù)轉(zhuǎn)換成2個(gè)字符串，用系統(tǒng)的方法將樹(shù)的結(jié)構(gòu)編碼，然后將上面的字符串內(nèi)核應(yīng)用到它們中。

我們將兩根樹(shù)轉(zhuǎn)換成兩根弦：

讓T表示一個(gè)目標(biāo)樹(shù)和標(biāo)簽（NS）在T標(biāo)簽節(jié)點(diǎn)。NS字符串標(biāo)簽（NS）是指T扎根在NS的子樹(shù)的字符串表示。所以如果是T的根節(jié)點(diǎn)，tag（nroot）是整個(gè)樹(shù)T的字符串的表現(xiàn)形式。

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

?如果節(jié)點(diǎn)NS是一個(gè)葉狀結(jié)構(gòu)，讓tag(ns) = “[” + label(ns) + “]”（在這里+是字符串串聯(lián)運(yùn)算符）。

?如果節(jié)點(diǎn)NS不是葉狀結(jié)構(gòu)，并且有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*) + “]”。

下面的圖，顯示了這課樹(shù)對(duì)字符串轉(zhuǎn)換的一個(gè)例子。其結(jié)果是一個(gè)字符串的起始開(kāi)口分隔符如”[“和結(jié)束的結(jié)束一樣，”]”,每一個(gè)嵌套的雙對(duì)應(yīng)子樹(shù)扎根在一個(gè)特定的節(jié)點(diǎn)的分隔符。

現(xiàn)在我們可以應(yīng)用上述轉(zhuǎn)換的兩顆樹(shù)，T1和T2，獲得兩個(gè)字符串S1和S2.從那里，我們可以簡(jiǎn)單地應(yīng)用上面描述的字符串內(nèi)核。

樹(shù)核的T1和T2之間通過(guò)兩個(gè)字符串S1和S2可以給予如下：

基于子路徑的樹(shù)核

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

本節(jié)將定義一個(gè)在樹(shù)上操作的樹(shù)內(nèi)核，允許內(nèi)核在樹(shù)上直接操作。

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

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

在數(shù)量（T）是子路徑P數(shù)發(fā)生在樹(shù)T，P是P子節(jié)點(diǎn)的數(shù)目，和P是在T1和T2的所有子路徑的設(shè)置。W | P |是權(quán)重，類似于前一節(jié)介紹。

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

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

在這個(gè)例子中，我們使用的加權(quán)參數(shù)w|s| w|p| = 1。這給所有的子路徑并重。然而，在許多情況下使用K譜線的權(quán)重時(shí)，或一些動(dòng)態(tài)分配的權(quán)重值，是適當(dāng)?shù)摹?/p>

深挖網(wǎng)站

在我們結(jié)束之前，讓我們簡(jiǎn)要地看一個(gè)真實(shí)的樹(shù)分類：分類網(wǎng)站。在許多數(shù)據(jù)挖掘的背景下，它是有益的，知道什么”類型”來(lái)自哪些數(shù)據(jù)網(wǎng)站。它從不同的網(wǎng)站的網(wǎng)頁(yè)上可以相當(dāng)有效低分類使用樹(shù)，因?yàn)橄嗨频木W(wǎng)頁(yè)相似的服務(wù)是結(jié)構(gòu)化的。

我們?cè)趺醋觯縃TML文檔的邏輯嵌套結(jié)構(gòu)，它很像一棵樹(shù)。每一個(gè)文檔包含一個(gè)根元素，里面包含了其他元素嵌套。元素嵌套在HTML標(biāo)簽在邏輯上相當(dāng)于這個(gè)標(biāo)簽的子節(jié)點(diǎn)。

讓我們看一些代碼，可以將一個(gè)HTML文檔放到樹(shù)上看：

這將產(chǎn)生一個(gè)樹(shù)的數(shù)據(jù)結(jié)構(gòu)，可能看起來(lái)像這樣的：

實(shí)際上述利用幾個(gè)有用的Python庫(kù)：networkx，對(duì)復(fù)雜的圖形結(jié)構(gòu)把數(shù)據(jù)從網(wǎng)絡(luò)上取下和操作文件。

我們要在1000個(gè)網(wǎng)站的主頁(yè)上找到組。通過(guò)將每個(gè)網(wǎng)頁(yè)變成這樣的一棵樹(shù)，我們可以相互比較，例如通過(guò)使用上一節(jié)給出的路徑樹(shù)核。通過(guò)這些測(cè)量的相似性我們可以發(fā)現(xiàn)，例如，電子商務(wù)網(wǎng)站，新聞網(wǎng)站，博客和教育網(wǎng)站是很容易確定他們的相似性的。

結(jié)論

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

樹(shù)結(jié)構(gòu)在現(xiàn)實(shí)世界中許多領(lǐng)域如XML和HTML文件，遇到化學(xué)化合物，自然語(yǔ)言處理，或某些類型的用戶行為。作為從HTML構(gòu)建樹(shù)的例子證明，這些技術(shù)使我們能夠在這些領(lǐng)域進(jìn)行有意義的分析。

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

End.

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com