數(shù)據(jù)科學(xué)家需要知道的5種圖算法

作者：AI公園 2019-12-11 19:19:19

作為數(shù)據(jù)科學(xué)家，我們對(duì)pandas、SQL或任何其他關(guān)系數(shù)據(jù)庫(kù)非常熟悉。我們習(xí)慣于將用戶的屬性以列的形式顯示在行中。但現(xiàn)實(shí)世界真的是這樣嗎?

導(dǎo)讀

因?yàn)閳D分析是數(shù)據(jù)科學(xué)家的未來(lái)。

作為數(shù)據(jù)科學(xué)家，我們對(duì)pandas、SQL或任何其他關(guān)系數(shù)據(jù)庫(kù)非常熟悉。

我們習(xí)慣于將用戶的屬性以列的形式顯示在行中。但現(xiàn)實(shí)世界真的是這樣嗎?

在一個(gè)互聯(lián)的世界里，用戶不能被視為獨(dú)立的實(shí)體。它們之間有一定的關(guān)系，我們?cè)诮C(jī)器學(xué)習(xí)模型的時(shí)候，有時(shí)也會(huì)考慮這些關(guān)系。

現(xiàn)在，雖然在關(guān)系數(shù)據(jù)庫(kù)中，我們不能在不同的行(用戶)之間使用這樣的關(guān)系，但是在圖形數(shù)據(jù)庫(kù)中，這樣做非常簡(jiǎn)單。

在本文中，我將討論一些你應(yīng)該知道的最重要的圖算法，以及如何使用Python實(shí)現(xiàn)它們。

1. 連通組件

一個(gè)包含3個(gè)連通組件的圖

我們都知道聚類(lèi)是如何工作的。

你可以用外行人的術(shù)語(yǔ)來(lái)理解連通組件，它是一種硬聚類(lèi)算法，可以在相關(guān)/連接的數(shù)據(jù)中找到聚類(lèi)/島嶼

舉個(gè)具體的例子：假設(shè)你有連接世界上任何兩個(gè)城市的道路的數(shù)據(jù)。你需要找出世界上所有的大陸以及它們包含哪些城市

你將如何實(shí)現(xiàn)這一點(diǎn)?來(lái)想想吧。

我們使用的連通組件算法是基于BFS/DFS的特殊情況。我不會(huì)在這里過(guò)多地討論它是如何工作的，但是我們將看到如何使用Networkx編寫(xiě)和運(yùn)行代碼。

應(yīng)用

從零售的角度來(lái)看：假設(shè)我們有很多客戶，使用很多賬戶。使用連通組件算法的一種方法是在數(shù)據(jù)集中找出明顯不同的家族。

我們可以根據(jù)相同的信用卡使用情況、相同的地址或相同的移動(dòng)電話號(hào)碼等設(shè)定客戶ID之間的邊(路)。一旦我們有了這些連接，我們就可以運(yùn)行連通組件算法來(lái)創(chuàng)建單獨(dú)的簇，然后我們可以為其分配一個(gè)家族ID。

然后，我們可以使用這些家族ID根據(jù)家族需求提供個(gè)性化的推薦。我們還可以使用這個(gè)家族ID，通過(guò)創(chuàng)建基于家族的分組特征來(lái)支持我們的分類(lèi)算法。

從財(cái)務(wù)的角度來(lái)看：另一個(gè)用例是使用這些家族ID捕獲欺詐。如果一個(gè)賬戶在過(guò)去有過(guò)欺詐行為，關(guān)聯(lián)賬戶很可能也容易進(jìn)行欺詐。

可能性只受你自己想象力的限制。

代碼

我們將使用Python中的Networkx模塊來(lái)創(chuàng)建和分析圖。

讓我們從一個(gè)示例圖開(kāi)始，我們使用它來(lái)實(shí)現(xiàn)我們的目的。包含城市和城市之間的距離信息。

使用隨機(jī)距離的圖

我們首先創(chuàng)建一個(gè)帶有距離的邊的列表，我們把距離作為邊的權(quán)重：

edgelist = [['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250],["Mumbai", "Delhi",400],["Delhi", "Kolkata",500],["Kolkata", "Bangalore",600],["TX", "NY",1200],["ALB", "NY",800]]

使用Networkx構(gòu)建圖：

g = nx.Graph() 
 for edge in edgelist: 
 g.add_edge(edge[0],edge[1], weight = edge[2])

現(xiàn)在我們想從這張圖中找出不同的大陸及其包含的城市。

我們現(xiàn)在可以使用連通組件算法做到這一點(diǎn)：

for i, x in enumerate(nx.connected_components(g)): 
 print("cc"+str(i)+":",x) 
 ------------------------------------------------------------ 
 cc0: {'Frankfurt', 'Kassel', 'Munchen', 'Numberg', 'Erfurt', 'Stuttgart', 'Karlsruhe', 'Wurzburg', 'Mannheim', 'Augsburg'} 
 cc1: {'Kolkata', 'Bangalore', 'Mumbai', 'Delhi'} 
 cc2: {'ALB', 'NY', 'TX'}

正如你所看到的，我們能夠在數(shù)據(jù)中找到不同的部分。只需要使用邊和頂點(diǎn)。這個(gè)算法可以在不同的數(shù)據(jù)上運(yùn)行，以滿足我上面提到的任何用例。

2. 最短路徑

繼續(xù)上面的例子，我們得到了一個(gè)德國(guó)城市的圖以及它們之間的距離。

你想知道如何從法蘭克福(起始節(jié)點(diǎn))到慕尼黑的最短距離。

我們用來(lái)解決這個(gè)問(wèn)題的算法叫做Dijkstra。用Dijkstra自己的話來(lái)說(shuō)：

從鹿特丹到[格羅寧根的最短路線是什么?一般來(lái)說(shuō)，最短路徑的算法是這樣的，我花了大約20分鐘來(lái)設(shè)計(jì)它。一天早上我在阿姆斯特丹和我的年輕的未婚妻購(gòu)物，累了，我們坐在咖啡館露臺(tái)喝一杯咖啡，我就在想我能不能想出這個(gè)最短路徑算法，然后我就想出來(lái)了。正如我所說(shuō)，這是一個(gè)20分鐘的發(fā)明。事實(shí)上，它是在1959年出版的。三年后，還可以讀到，事實(shí)上，它相當(dāng)不錯(cuò)。它如此漂亮的原因之一是我不用鉛筆和紙來(lái)設(shè)計(jì)它。后來(lái)我了解到，不用鉛筆和紙?jiān)O(shè)計(jì)的好處之一是，你幾乎不得不避免所有可以避免的復(fù)雜性。最終，令我大為驚訝的是，這個(gè)算法成了我成名的基石之一。

- Edsger Dijkstra，在對(duì)Philip L. Frana的采訪中

應(yīng)用

Dijkstra算法的變體廣泛應(yīng)用于谷歌地圖中，用于尋找最短路徑。

你在沃爾瑪，你有不同的通道和所有通道之間的距離。你想要提供從A通道到D通道到客戶的最短路徑。

你可以看到LinkedIn如何顯示1級(jí)和2級(jí)的連接。幕后發(fā)生了什么?

代碼

print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight')) 
print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight')) 
-------------------------------------------------------- 
['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt'] 
503

你也可以找到所有的地點(diǎn)對(duì)之間的最短路徑：

for x in nx.all_pairs_dijkstra_path(g,weight='weight'): 
 print(x) 
 -------------------------------------------------------- 
 ('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']}) 
 ('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']}) 
 ....

3. 最小生成樹(shù)

現(xiàn)在我們有另一個(gè)問(wèn)題。我們?yōu)橐患宜茕佋O(shè)公司或互聯(lián)網(wǎng)光纖公司工作。我們需要用最少的電線/管道連接圖中所有的城市，我們?cè)撛趺醋?

一個(gè)無(wú)向圖，右邊是它的最小生成樹(shù)

應(yīng)用

最小生成樹(shù)直接應(yīng)用于網(wǎng)絡(luò)設(shè)計(jì)，包括計(jì)算機(jī)網(wǎng)絡(luò)、電信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、供水網(wǎng)絡(luò)和電網(wǎng)(它們最初是為這些網(wǎng)絡(luò)而發(fā)明的)
MST用于逼近旅行商問(wèn)題
聚類(lèi) — 首先構(gòu)造MST，然后使用簇間距離和簇內(nèi)距離確定MST中某些邊緣的分割閾值。
圖像分割 — 用于圖像分割，我們首先在一個(gè)圖上構(gòu)造一個(gè)MST，其中像素是節(jié)點(diǎn)，像素之間的距離基于一些相似性度量(顏色、強(qiáng)度等)。

代碼

# nx.minimum_spanning_tree(g) returns a instance of type graph 
nx.draw_networkx(nx.minimum_spanning_tree(g))

數(shù)據(jù)科學(xué)家需要知道的5種圖算法
我們的圖的最小生成樹(shù)

可以看到，上面就是我們需要鋪設(shè)的電線。

4. Pagerank

這就是長(zhǎng)期以來(lái)支持谷歌的頁(yè)面排序算法。它根據(jù)輸入和輸出鏈接的數(shù)量和質(zhì)量為頁(yè)面分配一個(gè)分?jǐn)?shù)。

應(yīng)用

Pagerank可以用于任何我們想要估計(jì)任何網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的地方。

它被用來(lái)尋找最具影響力的論文使用引文。
被谷歌用來(lái)排列頁(yè)面
它可以用來(lái)把tweets-用戶和以及tweets-tweets當(dāng)成節(jié)點(diǎn)進(jìn)行排序。如果用戶A關(guān)注了用戶B，那么創(chuàng)建用戶之間的鏈接，如果用戶tweet/retwets一條tweet，則創(chuàng)建用戶和tweet之間的鏈接。
推薦引擎

代碼

在這個(gè)練習(xí)中，我們將使用Facebook數(shù)據(jù)。我們有一個(gè)facebook用戶之間的邊/鏈接文件。我們首先創(chuàng)建FB圖，使用：

# reading the dataset 
fb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)

它是這樣的：

pos = nx.spring_layout(fb) 
 import warnings 
 warnings.filterwarnings('ignore') 
 plt.style.use('fivethirtyeight') 
 plt.rcParams['figure.figsize'] = (20, 15) 
 plt.axis('off') 
 nx.draw_networkx(fb, pos, with_labels = False, node_size = 35) 
 plt.show()

數(shù)據(jù)科學(xué)家需要知道的5種圖算法
FaceBook用戶圖

現(xiàn)在我們想要找到具有高影響力的用戶。

直觀地說(shuō)，Pagerank算法會(huì)給有很多朋友的用戶打高分，而這些朋友又有很多facebook上的朋友。

pageranks = nx.pagerank(fb) 
print(pageranks) 
------------------------------------------------------ 
{0: 0.006289602618466542, 
 1: 0.00023590202311540972, 
 2: 0.00020310565091694562, 
 3: 0.00022552359869430617, 
 4: 0.00023849264701222462, 
........}

我們可以用PageRank得到最有影響力的用戶排序：

import operator 
sorted_pagerank = sorted(pageranks.items(), key=operator.itemgetter(1),reverse = True) 
print(sorted_pagerank) 
------------------------------------------------------ 
[(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262), (698, 0.0013171153138368807), (483, 0.0012974283300616082), (3830, 0.0011844348977671688), (376, 0.0009014073664792464), (2047, 0.000841029154597401), (56, 0.0008039024292749443), (25, 0.000800412660519768), (828, 0.0007886905420662135), (322, 0.0007867992190291396),......]

以上id適用于最有影響力的用戶。

我們可以看到最具影響力用戶的子圖：

first_degree_connected_nodes = list(fb.neighbors(3437)) 
second_degree_connected_nodes = [] 
for x in first_degree_connected_nodes: 
 second_degree_connected_nodes+=list(fb.neighbors(x)) 
second_degree_connected_nodes.remove(3437) 
second_degree_connected_nodes = list(set(second_degree_connected_nodes)) 
subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes) 
pos = nx.spring_layout(subgraph_3437) 
node_color = ['yellow' if v == 3437 else 'red' for v in subgraph_3437] 
node_size = [1000 if v == 3437 else 35 for v in subgraph_3437] 
plt.style.use('fivethirtyeight') 
plt.rcParams['figure.figsize'] = (20, 15) 
plt.axis('off') 
nx.draw_networkx(subgraph_3437, pos, with_labels = False, node_color=node_color,node_size=node_size ) 
plt.show()

最有影響力的用戶(黃色)

5. 中心度量

有許多中心度量，你都可以將其用作機(jī)器學(xué)習(xí)模型的特征。我將討論其中的兩個(gè)。

內(nèi)中心：重要的不僅是擁有最多朋友的用戶，將一個(gè)地理位置與另一個(gè)地理位置連接起來(lái)的用戶也很重要，因?yàn)檫@讓用戶可以看到來(lái)自不同地理位置的內(nèi)容。內(nèi)中心度量了一個(gè)特定節(jié)點(diǎn)在另外兩個(gè)節(jié)點(diǎn)之間的最短路徑中出現(xiàn)的次數(shù)
度中心：它是節(jié)點(diǎn)的連接數(shù)。

應(yīng)用

中心度量可以作為任何機(jī)器學(xué)習(xí)模型的一個(gè)特征。

代碼

面的代碼用于查找子圖的內(nèi)中心。

pos = nx.spring_layout(subgraph_3437) 
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True) 
node_size = [v * 10000 for v in betweennessCentrality.values()] 
plt.figure(figsize=(20,20)) 
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False, node_size=node_size ) 
plt.axis('off')