樹的內(nèi)核：量化樹結(jié)構(gòu)化數(shù)據(jù)之間的相似性_html/css

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

今天，大量的數(shù)據(jù)是可用的網(wǎng)絡(luò)或圖形的形式。例如，萬維網(wǎng)，其網(wǎng)頁和超鏈接，社會網(wǎng)絡(luò)，語義網(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ù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個節(jié)點(diǎn)有零個或多個子節(jié)點(diǎn)；沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)；除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可以分為多個不相交的子樹；

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

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

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

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

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

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

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

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

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

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

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

核方法

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

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

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

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

樹核

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

字符串內(nèi)核

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

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

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

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

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

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

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

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

?如果節(jié)點(diǎn)NS是一個葉狀結(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*) + “]”。

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

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

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

基于子路徑的樹核

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

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

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

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

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

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

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

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

深挖網(wǎng)站

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

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

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

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

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

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

結(jié)論

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

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

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

End.

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