一篇文章帶你認(rèn)識“高大上”的圖數(shù)據(jù)挖掘

互聯(lián)網(wǎng)發(fā)展至今，數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)結(jié)構(gòu)越來越復(fù)雜，而且對系統(tǒng)的需求越來越高。如果學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)，那么都知道圖是放在最后一個結(jié)構(gòu)，當(dāng)你學(xué)習(xí)了圖，那么應(yīng)該感知到前面的鏈表，隊列，樹都是在圖上面加了一些約束而派生出來的結(jié)構(gòu)。所以圖是一個一般性的結(jié)構(gòu)，可以適應(yīng)于任何結(jié)構(gòu)類型的數(shù)據(jù)。那么圖數(shù)據(jù)挖掘是干什么的呢？難道是開著挖掘機(jī)來進(jìn)行挖掘？還是扛著鋤頭？下面講講什么是圖數(shù)據(jù)挖掘。

一、什么是圖數(shù)據(jù)挖掘

這個話題感覺比較沉重，以至于我敲打每個字都要猶豫半天，這里我說說我對圖數(shù)據(jù)挖掘的理解。數(shù)據(jù)是一個不可數(shù)名字，那么說明數(shù)據(jù)是一個沒有邊界的東西。而挖掘是一個很形象化的動詞，一般意義上，挖掘是挖掘出對我們有用的東西，不然也不會閑著沒事刨個坑把自己放進(jìn)去，肯定是里面有寶貝，我們才挖掘。那么不難理解，數(shù)據(jù)挖掘就是挖掘數(shù)據(jù)里面的“寶貝”，圖數(shù)據(jù)挖掘，就是以圖的結(jié)構(gòu)來存儲、展示、思考數(shù)據(jù)，以達(dá)到挖掘出其中的“寶貝”。那這個“寶貝”是什么？這個有點主觀意識來理解了，“寶貝”這個詞本身就帶有主觀色彩，而沒有一個客觀的答案，不像是美女大胸、翹臀、高挑、皮膚白皙、臉蛋好看等一系列標(biāo)準(zhǔn)。那么如何理解圖數(shù)據(jù)里面的“寶貝”呢？舉個例子吧，例如：當(dāng)今互聯(lián)網(wǎng)產(chǎn)生了很多社交數(shù)據(jù)，某某關(guān)注了某某，那么某某和某某就有了關(guān)系，某某評論過某某，那么這又產(chǎn)生了關(guān)系，在這個里面某某就是圖中的節(jié)點，而評論過，關(guān)注了則是節(jié)點之間的關(guān)系，如果某某再多點，這就形成了一個無邊界的圖了。那么對這個圖進(jìn)行關(guān)系挖掘，那么會產(chǎn)生很多有用的數(shù)據(jù)，比如可以推薦你可能認(rèn)識的人，那就是朋友的朋友，甚至更深，這就形成了某空間好友推薦的功能。比如某寶的你可能喜歡的寶貝，可以通過圖數(shù)據(jù)挖掘來實現(xiàn)。這就是我認(rèn)為的圖數(shù)據(jù)挖掘。

從學(xué)術(shù)上講，圖數(shù)據(jù)挖掘分為數(shù)據(jù)圖，模式圖兩種。至于這兩個類型的區(qū)別，由于很久沒有關(guān)注這塊，所以只能給出一個字面意義上的區(qū)別。數(shù)據(jù)圖：則是以數(shù)據(jù)節(jié)點為基礎(chǔ)來進(jìn)行分析圖，模式圖：則是以數(shù)據(jù)整個關(guān)系模型來進(jìn)行分析數(shù)據(jù)?？赡芙忉尨嬖阱e誤，望指正。我之前主要是接觸數(shù)據(jù)圖一塊的東西，模式圖沒有太多了解。關(guān)于數(shù)據(jù)圖和模式圖在學(xué)術(shù)界存在幾個比較有參考意義的實現(xiàn)以及算法。數(shù)據(jù)圖有：BANKS,BLINKS,Object rank；模式圖有：DBXplorer（微軟）,DISCOVER(加利福尼亞大學(xué))，S-CBR（人民大學(xué)，就是在大學(xué)學(xué)數(shù)據(jù)庫都會知道的人：王珊）。下面主要對數(shù)據(jù)圖的幾種實現(xiàn)進(jìn)行簡單介紹，模式圖，可以找上面相關(guān)論文進(jìn)行了解。

二、數(shù)據(jù)圖典型實現(xiàn)介紹

1、BANK（Browsing and Keyword Searching in Relational Databases）

整體上說一下它的思想是通過關(guān)系數(shù)據(jù)庫進(jìn)行存儲圖結(jié)構(gòu)的數(shù)據(jù)加上Dijkstra算法來進(jìn)行數(shù)據(jù)的存儲和圖數(shù)據(jù)的搜索。該算法第一步先是先是匹配所有關(guān)鍵詞的關(guān)鍵節(jié)點，并且以每個關(guān)鍵節(jié)點為源節(jié)點進(jìn)行一次Dijkstra算法對圖進(jìn)行遍歷，因此可以形成和每個關(guān)鍵節(jié)點可達(dá)的節(jié)點堆，該堆是進(jìn)行了按照到關(guān)鍵節(jié)點距離進(jìn)行堆排序的堆。因此可以想想每個關(guān)鍵節(jié)點的節(jié)點堆的第一個元素則是到該關(guān)鍵節(jié)點最近的節(jié)點。利用這個，那么對每個節(jié)點堆一次遍歷，每次遍歷只取堆的第一個節(jié)點，可以得知，這個取出的節(jié)點和節(jié)點對對應(yīng)的關(guān)鍵詞是可達(dá)的，如果這個節(jié)點和所有關(guān)鍵節(jié)點可達(dá)，那么就可以這個節(jié)點為根節(jié)點形成一個結(jié)果樹，所以需要對這個取出的節(jié)點進(jìn)行標(biāo)記，標(biāo)記的目的就是說我這個關(guān)鍵節(jié)點來過這里了（有點類似到此一游的感覺）。這就是BANK的大體上的算法思想。下面提出一個流程圖，幫助大家理解一下。

這種方式存在幾個缺點：由于它的這個算法是需要把整個圖結(jié)構(gòu)加載到內(nèi)存中，所以當(dāng)節(jié)點數(shù)一大，那么可能會收到內(nèi)存的限制。第二個缺點是，它的搜索是單向的，這樣在效率上面存在一定的缺陷。這個算法也是我研究圖數(shù)據(jù)挖掘主要研究的對象，因為比較簡單，容易理解。下面針對上面兩個缺陷介紹另外兩個算法。

2、Bidirectional Expansion For Keyword Search on Graph Databases

這個算法則是在第一個基礎(chǔ)上面進(jìn)行了擴(kuò)展，支持雙向搜索。從而解決了上麥年的第二個缺陷。具體算法實現(xiàn)，很久沒接觸了，而且當(dāng)時也沒關(guān)注這方面的實現(xiàn)，所以我也不是很清楚，只是知道它實現(xiàn)了雙向遍歷。具體的可以點擊標(biāo)題，看它的論文。

3、BLINK BLINKS Ranked keyword searches on graphs

這個實現(xiàn)是解決了大圖問題，通過對圖進(jìn)行分割，形成超圖的概念，加載內(nèi)存只需要把超圖進(jìn)來，當(dāng)需要遍歷這個超圖節(jié)點的時候，再將超圖節(jié)點里面的明細(xì)節(jié)點加載到內(nèi)存，基于這個概念可以很好的解決節(jié)點數(shù)量大而受內(nèi)存的限制，這個算法有點類似地圖的放大鏡，當(dāng)需要展示某一塊（超圖節(jié)點）的時候，則加載當(dāng)前塊的內(nèi)容，用戶就會看到更加明細(xì)的地圖信息。具體算法，可以點擊標(biāo)題，看看它的論文。

既然說道圖，那么不得不提一下在圖數(shù)據(jù)庫方面最流行的neo4j.neo4j是在09年過年的時候接觸的，當(dāng)時是調(diào)研以何種方式來存儲圖數(shù)據(jù)，所以當(dāng)時弄了一下，后沒就沒關(guān)注了。當(dāng)時看neo4j真的很小，不像現(xiàn)在這么成熟。

三、NEO4J預(yù)覽

在NEO4J官方文檔里面會看到下面幾點介紹圖數(shù)據(jù)庫。

“A Graph —records data in→ Nodes —which have→ Properties”

上面很簡單明了的介紹了圖是什么，圖是以節(jié)點存儲記錄數(shù)據(jù)，而節(jié)點數(shù)據(jù)是以屬性形式關(guān)聯(lián)節(jié)點。

“Nodes —are organized by→ Relationships —which also have→ Properties”

這句話說明了關(guān)系在圖中的作用，可以理解節(jié)點是通過關(guān)系來進(jìn)行組織和管理，并且關(guān)系也可以包裹屬性信息。

“Nodes —are grouped by→ Labels —into→ Sets”

在圖中標(biāo)簽的作用就是對節(jié)點進(jìn)行分組，并且同一個標(biāo)簽的節(jié)點會放到一個集合中，這個有點類似上面說的對圖進(jìn)行分割。比如：給節(jié)點貼上一個“人”的標(biāo)簽，那么當(dāng)對圖進(jìn)行搜索的時候，當(dāng)指定“人”這個標(biāo)簽的時候，那么只會找到所有人的節(jié)點，而不會找到貓，狗等節(jié)點。這樣可以提高圖的遍歷速度，而且可以更好的管理圖的節(jié)點。

“A Traversal —navigates→ a Graph; it —identifies→ Paths —which order→ Nodes”

一個路徑的遍歷，它可以正確的導(dǎo)航整個圖的結(jié)構(gòu)遍歷，并且它可以對應(yīng)一系列路徑，這些路徑則是將所有節(jié)點串聯(lián)起來。這個解釋了搜索在圖中的定位，一條搜索可以對應(yīng)多條路徑，也就是多條結(jié)果，而每個結(jié)果包含一系列節(jié)點。

“An Index —maps from→ Properties —to either→ Nodes or Relationships”

圖中的建立索引的數(shù)據(jù)來自于節(jié)點和關(guān)系的屬性，并且索引會直接映射到節(jié)點和關(guān)系。這樣可以通過索引遍歷圖中的節(jié)點和關(guān)系，以得到結(jié)果。

“A Graph Database —manages a→ Graph and —also manages related→ Indexes”

這里明確的表示了圖數(shù)據(jù)是干什么的，同時也表達(dá)了NEO4J是干什么的。他是管理和維護(hù)圖數(shù)據(jù)CRUD，并且維護(hù)圖數(shù)據(jù)的索引建立和更新。是對圖數(shù)據(jù)操作的一個對外接口。