在萬物相連的世界里，用戶并不是獨立的個體，彼此之間都有某種聯(lián)系。構(gòu)建機器學(xué)習(xí)模型時，有時也會將這種聯(lián)系放入模型中。
雖然關(guān)系數(shù)據(jù)庫中無法在不同數(shù)行(用戶)間使用這種關(guān)系，但在圖數(shù)據(jù)庫里，這樣做非常簡單。
本文將介紹一些數(shù)據(jù)科學(xué)家必知的重要的圖算法，并闡釋如何用Python來使用它們。
另外，強烈推薦先學(xué)習(xí)圖理論基礎(chǔ)。
圣地亞哥大學(xué)發(fā)布于Coursera上的大數(shù)據(jù)課程的圖分析課：https://www.coursera.org/learn/big-data-graph-analytics?ranMID=40328&ranEAID=lVarvwc5BD0&ranSiteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&siteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&utm_content=2&utm_medium=partners&utm_source=linkshare&utm_campaign=lVarvwc5BD0
1. 連通分支
包含3個連接組件的圖
大家都知道聚類算法如何工作吧?
簡單地說，就是將連通分支看作一種硬聚類算法，讓它在相關(guān)/相連數(shù)據(jù)中找到聚類/島。
舉個具體的例子：假設(shè)有一份連接世界上任意兩個城市的道路數(shù)據(jù)，而你需要借此找到世界上所有大洲和所包含的城市。
這要如何實現(xiàn)呢?開動腦筋吧。
此處使用的連通分支算法是基于BFS/DFS的特殊情況，此處不多贅述。以下會解釋如何使用Networkx啟動和運行代碼。
應(yīng)用
從零售的角度來看：假設(shè)有很多客戶使用很多的帳戶，連通分支算法可用于在數(shù)據(jù)集中找出不同的家庭。
根據(jù)相同的信用卡使用情況、相同的地址或相同的電話號碼等，可以假定客戶ID之間的聯(lián)系(路)。一旦有了這些聯(lián)系，就可以對其運行連通分支算法來創(chuàng)建單獨的集群，然后為其分配一個家庭ID。
接著就可以使用這些家庭ID根據(jù)家庭需求提供個性化推薦。還可以用它來創(chuàng)建基于家族的分組特性，從而不斷完善分類算法。
從金融角度來看：這些家庭ID還能用來捕獲欺詐。如果某個賬戶有過欺詐行為，關(guān)聯(lián)賬戶也很可能實施欺詐。
應(yīng)用的無限可能性全憑你的想象定奪。
編碼
此處將使用Python中的Networkx模塊來創(chuàng)建和分析圖表。
先看一個會用到的示例圖，其中包含城市和城市之間的距離信息。
隨機距離示意圖
首先，創(chuàng)建聯(lián)系列表和作為聯(lián)系權(quán)重的距離列表:
用 Networkx創(chuàng)建一個圖：
現(xiàn)在要從這張圖中找出不同的大陸及其城市。
可以這樣/(按如下方式)使用連通分支算法：
如上所示，只需要使用聯(lián)系和頂點就可以在數(shù)據(jù)中找到不同的組件。這個算法可以在不同的數(shù)據(jù)上運行來滿足以上提到的任何案例。
2. 最短路徑
上面已經(jīng)得到德國城市以及各城市距離的圖。
接著，要得出從法蘭克福(起始節(jié)點)到慕尼黑的最短距離。
解決此問題的算法叫Dijkstra算法。用Dijkstra本人的話來說：
從鹿特丹到格羅寧根的捷徑是什么?或者說，從任意一個城市到另一個城市。設(shè)計這個最短路徑的算法，我只花了20分鐘。一天早上，我和年輕的未婚妻在阿姆斯特丹購物。逛累了之后，我們坐在咖啡館露臺上喝了一杯咖啡，我就想能不能做到這一點，然后就設(shè)計了最短路徑算法。就像之前所說，這是一個20分鐘的發(fā)明。事實上，這本書在三年后的1959年出版，現(xiàn)在還能讀到。它是本很好的書，因為我當(dāng)時沒有用鉛筆和紙來設(shè)計。后來我發(fā)現(xiàn)，不用鉛筆和紙設(shè)計的好處之一是，設(shè)計時必須要化繁為簡。最終，我沒想到，這個算法竟然成了我的成名作之一。
—— Edsger Dijkstra, 和Philip L. Frana的一段采訪對話，美國計算機學(xué)會通訊，2001[3]
應(yīng)用
- Dijkstra算法的演變版本被廣泛應(yīng)用于谷歌地圖中用來尋找最短路徑
- 假設(shè)你在沃爾瑪工作，已知不同的通道和所有通道之間的距離，求出A通道到客戶所在的D通道的最短路徑。
- 領(lǐng)英上有很多一級聯(lián)系和二級聯(lián)系。這些聯(lián)系背后都是如何運作的呢?
編碼
還可以使用以下命令找到所有城市對之間的最短路徑：
3. 最小生成樹(MST)
現(xiàn)在另一個問題來了。假設(shè)你在水管鋪設(shè)公司或互聯(lián)網(wǎng)纖維公司工作，需要用最少的電線/管道連接圖中的所有城市，這該怎么做呢?
一個無向圖，它的MST在右邊
應(yīng)用
- MST被直接應(yīng)用于網(wǎng)絡(luò)設(shè)計中。其中包括電腦網(wǎng)絡(luò)、電訊網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)、供水網(wǎng)絡(luò)和電網(wǎng)(最初設(shè)計目的)
- MST還用于解決旅行商問題
- 聚類——首先建構(gòu)MST，接著用簇間距離和簇內(nèi)距離確定閾值，從而打破MST中的一些聯(lián)系
- 圖像分割——首先在圖中構(gòu)建MST，其中像素是節(jié)點，像素之間的距離基于一些相似性度量(顏色、強度等)
編碼
本圖中的MST
如圖所示，上圖中便是要鋪設(shè)的電線。
4. 網(wǎng)頁排名
上圖便是谷歌一直以來的網(wǎng)頁排名算法。它根據(jù)輸入和輸出連接的數(shù)量和質(zhì)量為頁面分配分?jǐn)?shù)。
應(yīng)用
網(wǎng)頁排名可用于需要估算網(wǎng)絡(luò)節(jié)點重要性的任何地方。
- 用于使用引文找到最有影響力的論文
- 在谷歌中用于網(wǎng)頁排名
- 還可用來給推特排序——以用戶和推特作為節(jié)點。如果用戶A關(guān)注了用戶B，就創(chuàng)建用戶間的連接。如果用戶發(fā)送或轉(zhuǎn)發(fā)一條推特，則創(chuàng)建用戶和推特之間的連接。
- 推薦引擎
編碼
此練習(xí)會使用Facebook數(shù)據(jù)。這里有facebook用戶之間的連接/鏈接文件。首先這樣創(chuàng)建Facebook圖形：
它是這樣運作的：
FB用戶圖
現(xiàn)在要找到影響力高的用戶。
直觀地說，網(wǎng)頁排名算法會給有很多朋友的用戶打高分，而這些用戶又有很多facebook上的朋友。
這樣可以得到排序后的網(wǎng)頁排名算法或最有影響力的用戶：
以上ID用于最有影響力的用戶。
這里可以看到很具影響力用戶的子圖：
最有影響力的用戶(黃點)
5.中心性度量
中心度量有很多可以用來做機器學(xué)習(xí)模型的特性。以下將介紹其中的兩種。這里可以看到一些其他的測量方法：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html
中介中心性：朋友最多的用戶很重要，連接兩個地理位置的用戶也很重要，因為它讓用戶可以看到來自不同地理位置的內(nèi)容。中介中心性量化了一個特定節(jié)點在其他兩個節(jié)點之間最短路徑中出現(xiàn)的次數(shù)。
度中心性：即節(jié)點的連接數(shù)。
應(yīng)用
中心性度量可以用作任何機器學(xué)習(xí)模型的特性。
編碼
以下代碼用于查找子圖的中介中心性。
如上可以看到按中介中心性值調(diào)整了節(jié)點的大小。這些節(jié)點可以看作是信息傳遞者。斷開高中介中心性的節(jié)點會將圖分成許多部分。
總結(jié)
本文介紹了一些很具影響力的圖算法，它們從各方面改變了人們的生活方式。
隨著社會數(shù)據(jù)的大量涌現(xiàn)，網(wǎng)絡(luò)分析可以在很大程度上幫助人們改進(jìn)模型，產(chǎn)生巨大價值，甚至還會增進(jìn)人類對世界的認(rèn)識。
現(xiàn)今圖算法層出不窮，以上這些是筆者最喜歡的。如果感興趣，歡迎對這些算法進(jìn)行深入研究。本文僅對該領(lǐng)域進(jìn)行了一定的介紹。
這里是本文中提到的所有算法的Kaggle Kernel：https://www.kaggle.com/mlwhiz/top-graph-algorithms
【責(zé)任編輯：華軒 TEL：（010）68476606】