【概念】圖數(shù)據(jù)挖掘淺析

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

這個(gè)話題感覺(jué)比較沉重，以至于我敲打每個(gè)字都要猶豫半天，這里我說(shuō)說(shuō)我對(duì)圖數(shù)據(jù)挖掘的理解。數(shù)據(jù)是一個(gè)不可數(shù)名字，那么說(shuō)明數(shù)據(jù)是一個(gè)沒(méi)有邊界的東西。而挖掘是一個(gè)很形象化的動(dòng)詞，一般意義上，挖掘是挖掘出對(duì)我們有用的東西，不然也不會(huì)閑著沒(méi)事刨個(gè)坑把自己放進(jìn)去，肯定是里面有寶貝，我們才挖掘。那么不難理解，數(shù)據(jù)挖掘就是挖掘數(shù)據(jù)里面的“寶貝”，圖數(shù)據(jù)挖掘，就是以圖的結(jié)構(gòu)來(lái)存儲(chǔ)、展示、思考數(shù)據(jù)，以達(dá)到挖掘出其中的“寶貝”。

那這個(gè)“寶貝”是什么?這個(gè)有點(diǎn)主觀意識(shí)來(lái)理解了，“寶貝”這個(gè)詞本身就帶有主觀色彩，而沒(méi)有一個(gè)客觀的答案，不像是美女大胸、翹臀、高挑、皮膚白皙、臉蛋好看等一系列標(biāo)準(zhǔn)。那么如何理解圖數(shù)據(jù)里面的“寶貝”呢?舉個(gè)例子吧，例如：當(dāng)今互聯(lián)網(wǎng)產(chǎn)生了很多社交數(shù)據(jù)，某某關(guān)注了某某，那么某某和某某就有了關(guān)系，某某評(píng)論過(guò)某某，那么這又產(chǎn)生了關(guān)系，在這個(gè)里面某某就是圖中的節(jié)點(diǎn)，而評(píng)論過(guò)，關(guān)注了則是節(jié)點(diǎn)之間的關(guān)系，如果某某再多點(diǎn)，這就形成了一個(gè)無(wú)邊界的圖了。那么對(duì)這個(gè)圖進(jìn)行關(guān)系挖掘，那么會(huì)產(chǎn)生很多有用的數(shù)據(jù)，比如可以推薦你可能認(rèn)識(shí)的人，那就是朋友的朋友，甚至更深，這就形成了某空間好友推薦的功能。比如某寶的你可能喜歡的寶貝，可以通過(guò)圖數(shù)據(jù)挖掘來(lái)實(shí)現(xiàn)。這就是我認(rèn)為的圖數(shù)據(jù)挖掘。

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

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

1、BANK

整體上說(shuō)一下它的思想是通過(guò)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)圖結(jié)構(gòu)的數(shù)據(jù)加上Dijkstra算法來(lái)進(jìn)行數(shù)據(jù)的存儲(chǔ)和圖數(shù)據(jù)的搜索。該算法第一步先是先是匹配所有關(guān)鍵詞的關(guān)鍵節(jié)點(diǎn)，并且以每個(gè)關(guān)鍵節(jié)點(diǎn)為源節(jié)點(diǎn)進(jìn)行一次Dijkstra算法對(duì)

圖進(jìn)行遍歷，因此可以形成和每個(gè)關(guān)鍵節(jié)點(diǎn)可達(dá)的節(jié)點(diǎn)堆，該堆是進(jìn)行了按照到關(guān)鍵節(jié)點(diǎn)距離進(jìn)行堆排序的堆。因此可以想想每個(gè)關(guān)鍵節(jié)點(diǎn)的節(jié)點(diǎn)堆的第一個(gè)元素則是到該關(guān)鍵節(jié)點(diǎn)最近的節(jié)點(diǎn)。利用這個(gè)，那么對(duì)每個(gè)節(jié)點(diǎn)堆一次遍歷，每次遍歷只取堆的第一個(gè)節(jié)點(diǎn)，可以得知，這個(gè)取出的節(jié)點(diǎn)和節(jié)點(diǎn)對(duì)對(duì)應(yīng)的關(guān)鍵詞是可達(dá)的，如果這個(gè)節(jié)點(diǎn)和所有關(guān)鍵節(jié)點(diǎn)可達(dá)，那么就可以這個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)形成一個(gè)結(jié)果樹，所以需要對(duì)這個(gè)取出的節(jié)點(diǎn)進(jìn)行標(biāo)記，標(biāo)記的目的就是說(shuō)我這個(gè)關(guān)鍵節(jié)點(diǎn)來(lái)過(guò)這里了(有點(diǎn)類似到此一游的感覺(jué))。這就是BANK的大體上的算法思想。下面提出一個(gè)流程圖，幫助大家理解一下。

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

2、算法

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

3、BLINK

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

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

三、NEO4J預(yù)覽

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

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

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

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

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

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

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

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

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

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

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

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

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