構建知識圖譜過程中一個不可避免的算法問題

從谷歌最早提出知識圖譜的概念後，知識圖譜的火爆從美國一路燒到了國內，近幾年知識圖譜技術在國內已經得到了飛速的發展，我們對知識圖譜的概念及應用都不再陌生。大家可以看到知識圖譜技術的應用出現在越來越多的垂直領域中。從最早大家最為熟悉的在搜索引擎中的應用，逐漸地擴充到金融領域、醫藥領域等等。今天我們已經在各行各業中，都能夠看到知識圖譜的身影，更多的技術人員也加入了我們知識圖譜工程的大家庭。

那麼今天我們來就知識圖譜的技術問題進行更深層的探討。今天我將和大家分享一個，我在知識圖譜搭建中遇到的棘手問題，相信有不少小夥伴也會遇到這樣的問題。希望今天我分享的解決方案可以給大家一些幫助！

知識圖譜構建的過程中不可迴避的問題： 知識圖譜也屬於需要建立在海量數據之上的一種應用，在構建知識圖譜的圖關係時，基礎數據來自很多不同的數據源。常見的數據源有抓取的公開信息、業務數據、三方數據、用戶授權的數據等。

由於數據來源於不同的渠道，而中文又是一門博大精深的語言，同一種意義卻又有很多種表達。那麼這個棘手的問題就隨之而來：我們收集的數據中，有大量的表達方式所表達的是相同的意義。比如：阿里巴巴網絡技術有限公司和阿里巴巴集團是同一家公司麼？北京市國貿中心寫字樓和北京朝陽區建外大街1號國貿中心是同一個地址麼？在金融風控領域中，公司的名稱、地址是出現頻率非常高的詞彙，如果按照傳統的字符串比對的方式，就會認為以上信息表示的並不是相同的意義，那這樣，就會給知識圖譜的構建造成很大的麻煩，因為創建了很多無用的實體，並且很多本應該創建的關係，卻沒有創建出來。

這個時候，需要進行的工作就是實體消歧，也就是說把地址、公司名稱等信息經過處理後，變成同一個地址和公司名稱，讓他們表示同一種意義。只有這樣，才能夠將實體和關係成功的創建。

解決思路：

將這類容易造成歧義的字符串進行相似度計算，是解決這類問題的一種高效的手段。

那麼在知名的圖數據庫Neo4j中，如何實現相似度以計算如何滿足這種應用場景呢，就是我們接下來討論的主要話題。

我將會採用餘弦相似度計算來解決這個問題。大家都知道餘弦相似度是n維空間中兩個n維向量之間角度的餘弦。它是兩個向量的點積除以兩個向量的長度（或幅度）的乘積。

具體的計算方式可參見下面的公式：

以上公式計算的結果介於-1和1之間，其中-1完全不同，1完全相似。

那麼在圖數據庫Neo4j中如何進行餘弦相似度計算呢？下面我會簡單說明整個計算過程。不得不說我們非常幸運，Neo4j的插件提供了這樣的一個功能，讓我們能夠簡單、直接的在其上實現相似度計算。

首先我們來進行環境安裝：

環境的安裝其實非常的簡單，這裡你只需要一個jar包，就可以將其搞定。

下載鏈接：https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases

下載後，具體的操作步驟如下：

將下載的"graph-algorithms-algo-3.5.0.1.jar"包拷貝到"$NEO4J_HOME/plugins"目錄中

這裡需要注意的是：要修改Neo4j的配置將

添加到neo4j.conf文件當中，一定要做，要不然後邊的試驗會失敗。然後重啟Neo4j數據庫就可以了。

插件安裝成功後，打開你的Neo4j數據庫，在Cypher的輸入框中輸入 ：

RETURN algo.similarity.cosine([3,8,7,5,2,9], [10,8,6,6,4,5]) AS similarity

這個語句的意思就是調用Neo4j提供的算法計算庫中的函數，並且計算[3,8,7,5,2,9]和 [10,8,6,6,4,5]兩組數據的餘弦相似度，那麼返回的結果是（如下圖）：

那麼其結果已經非常的接近1了。這就是這兩個數字列表的餘弦相似度值。這個時候你會發現使用Neo4j庫中的插件來實現，非常的簡單，遠比自己開發一個這樣的功能要容易的多。

那麼下面，我們可以自己來根據公式進行推理一下，以便於進一步掌握這種算法。首先，我們創建一個圖關係，將下面的Cypher在輸入框中運行，就會創建好一個圖關係：

MERGE (french:Cuisine {name:'French'})

MERGE (italian:Cuisine {name:'Italian'})

MERGE (indian:Cuisine {name:'Indian'})

MERGE (lebanese:Cuisine {name:'Lebanese'})

MERGE (portuguese:Cuisine {name:'Portuguese'})

MERGE (zhen:Person {name: "Zhen"})

MERGE (praveena:Person {name: "Praveena"})

MERGE (michael:Person {name: "Michael"})

MERGE (arya:Person {name: "Arya"})

MERGE (karin:Person {name: "Karin"})

MERGE (praveena)-[:LIKES {score: 9}]->(indian)

MERGE (praveena)-[:LIKES {score: 7}]->(portuguese)

MERGE (zhen)-[:LIKES {score: 6}]->(indian)

MERGE (michael)-[:LIKES {score: 8}]->(french)

MERGE (michael)-[:LIKES {score: 7}]->(italian)

MERGE (michael)-[:LIKES {score: 9}]->(indian)

MERGE (arya)-[:LIKES {score: 10}]->(lebanese)

MERGE (arya)-[:LIKES {score: 10}]->(italian)

MERGE (arya)-[:LIKES {score: 7}]->(portuguese)

MERGE (karin)-[:LIKES {score: 9}]->(lebanese)

MERGE (karin)-[:LIKES {score: 7}]->(italian)

下面我們再用這個數據進行一次計算，輸入以下Cypher：

MATCH (p:Person), (c:Cuisine) OPTIONAL MATCH (p)-[likes:LIKES]->(c) WITH {item:id(p), weights: collect(coalesce(likes.score, 0))} as userData WITH collect(userData) as data CALL algo.similarity.cosine.stream(data) YIELD item1, item2, count1, count2, similarity RETURN algo.getNodeById(item1).name AS from, algo.getNodeById(item2).name AS to, similarity ORDER BY similarity DESC

運行後的結果是：

我們從結果中可以看到得分為0.889的是最高分，那麼我們可以認為Arya和Karin的食物口味最相似。但結果當中還有很多數據是我們不關心的，因為他們的相似度為0，原因是我數據庫中原本有一些數據導致，那麼現在我們要把這些數據過濾掉，輸入以下Cypher：

MATCH (p:Person), (c:Cuisine)

OPTIONAL MATCH (p)-[likes:LIKES]->(c)

WITH {item:id(p), weights: collect(coalesce(likes.score, 0))} as userData

WITH collect(userData) as data

CALL algo.similarity.cosine.stream(data, {similarityCutoff: 0.0})

YIELD item1, item2, count1, count2, similarity

RETURN algo.getNodeById(item1).name AS from, algo.getNodeById(item2).name AS to, similarity

ORDER BY similarity DESC

運行結果如下：

我們可以看到那些沒有相似性的數據已被過濾掉了。如果我們正在實現k-Nearest Neighbors類型查詢，我們可能希望k為給定數據找到最相似的數據。我們可以通過傳入topK參數來進行條件控制。

使用以下Cypher將返回最相似的數據（即k=1）：

MATCH (p:Person), (c:Cuisine)

OPTIONAL MATCH (p)-[likes:LIKES]->(c)

WITH {item:id(p), weights: collect(coalesce(likes.score, 0))} as userData

WITH collect(userData) as data

CALL algo.similarity.cosine.stream(data, {topK:1, similarityCutoff: 0.0})

YIELD item1, item2, count1, count2, similarity

RETURN algo.getNodeById(item1).name AS from, algo.getNodeById(item2).name AS to, similarity

ORDER BY from

執行結果：

細心的同學會發現，以上的結果有一點問題，第一行的結果和第二行的結果其實是相同的。那麼我們現在要做的是為每個用戶找到最相似的用戶，並存儲這些用戶之間的關係：

下面在你的Cypher輸入框中輸入以下Cypher：

MATCH (p:Person), (c:Cuisine)

OPTIONAL MATCH (p)-[likes:LIKES]->(c)

WITH {item:id(p), weights: collect(coalesce(likes.score, 0))} as userData

WITH collect(userData) as data

CALL algo.similarity.cosine(data, {topK: 1, similarityCutoff: 0.1, write:true})

RETURN nodes, similarityPairs, write, writeRelationshipType, writeProperty, min, max, mean, p95

執行結果如下：

然後，我們可以寫一個查詢，以找出與我們相似的其他人可能喜歡的美食類型。

以下Cypher將找到與Praveena最相似的用戶

MATCH (p:Person {name: "Praveena"})-[:SIMILAR]->(other),

(other)-[:LIKES]->(cuisine)

WHERE not((p)-[:LIKES]->(cuisine))

RETURN cuisine.name AS cuisine

很幸運，我們已經找到了，下面就是執行結果：

以上就是整個的計算過程。解決相似度計算的思路我們已經有了。 在知識圖譜的構建中，還有更多的挑戰等著我們。

閱讀更多 勇灬敢的心 的文章

關鍵字: Google 圖譜 NoSQL