出品 | AI科技大本營（ID：rgznai100）作為數(shù)據(jù)科學(xué)家，我們已經(jīng)對 Pandas 或 SQL 等其他關(guān)系數(shù)據(jù)庫非常熟悉了,。我們習(xí)慣于將行中的用戶視為列,。但現(xiàn)實(shí)世界的表現(xiàn)真的如此嗎？在互聯(lián)世界中,，用戶不能被視為獨(dú)立實(shí)體,。他們之間具有一定的關(guān)系，在構(gòu)建機(jī)器學(xué)習(xí)模型時,，有時也希望包含這樣的關(guān)系,。在關(guān)系型數(shù)據(jù)庫中，我們無法在不同的行（用戶）之間使用這種關(guān)系,，但在圖形數(shù)據(jù)庫中,，這樣做是相當(dāng)簡單的。在這篇文章中將為大家介紹一些重要的圖算法，以及Python 的代碼實(shí)現(xiàn),。將上圖中的連通分量算法近似看作一種硬聚類算法，該算法旨在尋找相關(guān)數(shù)據(jù)的簇類,。舉一個具體的例子：假設(shè)擁有連接世界上任意城市的路網(wǎng)數(shù)據(jù)，我們需要找出世界上所有的大陸,，以及它們所包含的城市,。我們該如何實(shí)現(xiàn)這一目標(biāo)呢？基于BFS / DFS的連通分量算法能夠達(dá)成這一目的,，接下來,，我們將用 Networkx 實(shí)現(xiàn)這一算法。使用 Python 中的 Networkx 模塊來創(chuàng)建和分析圖數(shù)據(jù)庫,。如下面的示意圖所示,，圖中包含了各個城市和它們之間的距離信息。首先創(chuàng)建邊的列表,，列表中每個元素包含兩個城市的名稱,，以及它們之間的距離。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 創(chuàng)建圖：g = nx.Graph()for edge in edgelist: g.add_edge(edge[0],edge[1], weight = edge[2])
現(xiàn)在,，我們想從這張圖中找出不同的大陸及其包含的城市。我們可以使用使用連通分量算法來執(zhí)行此操作：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'}
從結(jié)果中可以看出,，只需使用邊緣和頂點(diǎn),，我們就能在數(shù)據(jù)中找到不同的連通分量。 該算法可以在不同的數(shù)據(jù)上運(yùn)行,，以滿足前文提到的兩種其他運(yùn)用,。零售：很多客戶使用大量賬戶，可以利用連通分量算法尋找數(shù)據(jù)集中的不同簇類,。假設(shè)使用相同信用卡的客戶 ID 存在連邊（edges）,，或者將該條件替換為相同的住址，或者相同的電話等,。一旦我們有了這些連接的邊,，就可以使用連通分量算法來對客戶 ID 進(jìn)行聚類，并對每個簇類分配一個家庭 ID,。然后,，通過使用這些家庭 ID，我們可以根據(jù)家庭需求提供個性化建議,。此外,，通過創(chuàng)建基于家庭的分組功能，我們還能夠提高分類算法的性能,。
繼續(xù)第一節(jié)中的例子,，我們擁有了德國的城市群及其相互距離的圖表,。為了計(jì)算從法蘭克福前往慕尼黑的最短路徑，我們需要用到 Dijkstra 算法,。Dijkstra 是這樣描述他的算法的：從鹿特丹到格羅寧根的最短途徑是什么,？或者換句話說：從特定城市到特定城市的最短路徑是什么？這便是最短路徑算法,，而我只用了二十分鐘就完成了該算法的設(shè)計(jì)。 一天早上,，我和未婚妻在阿姆斯特丹購物,，我們逛累了,，便在咖啡館的露臺上喝了一杯咖啡。而我,，就想著我能夠做到這一點(diǎn),，于是我就設(shè)計(jì)了這個最短路徑算法。正如我所說,，這是一個二十分鐘的發(fā)明。事實(shí)上,，它發(fā)表于1959年，也就是三年后,。它之所以如此美妙,，其中一個原因在于我沒有用鉛筆和紙張就設(shè)計(jì)了它,。后來我才知道，沒有鉛筆和紙的設(shè)計(jì)的一個優(yōu)點(diǎn)就是,，你幾乎被迫避免所有可避免的復(fù)雜性,。最終，這個算法讓我感到非常驚訝，而且也成為了我名聲的基石之一,。 ——Edsger Dijkstra 于2001年接受ACM通訊公司 Philip L. Frana 的采訪時的回答
print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight'))print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))--------------------------------------------------------['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']503
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']})....
- Dijkstra 算法的變體在 Google 地圖中廣泛使用,，用于計(jì)算最短的路線。
- 想象身處在沃爾瑪商店,，我們知道了各個過道之間的距離,，我們希望為從過道 A 到過道 D 的客戶提供最短路徑。
- 如下圖所示,，當(dāng)我們知道了領(lǐng)英中用戶的一級連接,、二級連接時，如何得知幕后的信息呢,？Dijkstra 算法可以幫到我們。
假設(shè)我們在水管工程公司或互聯(lián)網(wǎng)光纖公司工作,，我們需要使用最少的電線（或者管道）連接圖表中的所有城市。我們?nèi)绾巫龅竭@一點(diǎn),？# nx.minimum_spanning_tree(g) returns a instance of type graphnx.draw_networkx(nx.minimum_spanning_tree(g))
- 最小生成樹在網(wǎng)絡(luò)設(shè)計(jì)中有著最直接的應(yīng)用,，包括計(jì)算機(jī)網(wǎng)絡(luò)，電信網(wǎng)絡(luò),，運(yùn)輸網(wǎng)絡(luò),，供水網(wǎng)絡(luò)和電網(wǎng)。（最小生成樹最初就是為此發(fā)明的）
- 聚類——首先構(gòu)造最小生成樹,，然后使用類間距離和類內(nèi)距離來設(shè)定閾值,，從而破壞最小生成樹中的某些連邊，最終完成聚類的目的
- 圖像分割——首先在圖形上構(gòu)建最小生成樹,，其中像素是節(jié)點(diǎn),，像素之間的距離基于某種相似性度量（例如顏色，強(qiáng)度等）,，然后進(jìn)行圖的分割,。
4、網(wǎng)頁排序（Pagerank） 
Pagerank 是為谷歌提供長期支持的頁面排序算法,。根據(jù)輸入和輸出鏈接的數(shù)量和質(zhì)量,，該算法對每個頁面進(jìn)行打分。在本節(jié)中,，我們將使用 Facebook 數(shù)據(jù),。首先，利用 Facebook 用戶之間的連接,，我們使用以下方法創(chuàng)建圖：# reading the datasetfb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)
pos = nx.spring_layout(fb)import warningswarnings.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()
現(xiàn)在,，我們想要找到具有高影響力的用戶。直觀上來講，Pagerank 會給擁有很多朋友的用戶提供更高的分?jǐn)?shù),，而這些用戶的朋友反過來會擁有很多朋友,。pageranks = nx.pagerank(fb)print(pageranks)------------------------------------------------------{0: 0.006289602618466542, 1: 0.00023590202311540972, 2: 0.00020310565091694562, 3: 0.00022552359869430617, 4: 0.00023849264701222462,........}
使用如下代碼，我們可以獲取排序后 PageRank 值,，或者最具有影響力的用戶：import operatorsorted_pagerank = sorted(pagerank.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),......]
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()
黃色的節(jié)點(diǎn)代表最具影響力的用戶Pagerank 可以估算任何網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性,。- 它可以對推文進(jìn)行排名，其中,，用戶和推文作為網(wǎng)絡(luò)的節(jié)點(diǎn),。如果用戶 A 跟隨用戶 B，則在用戶之間創(chuàng)建連邊,；如果用戶推文或者轉(zhuǎn)發(fā)推文,，則在用戶和推文之間建立連邊。
一些中心性度量的指標(biāo)可以作為機(jī)器學(xué)習(xí)模型的特征,，我們主要介紹其中的兩個指標(biāo)，其余的指標(biāo)可以參考這個鏈接,。 https://networkx./documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness 介數(shù)中心性：擁有最多朋友的用戶很重要,，而起到橋梁作用、將一個領(lǐng)域和另一個領(lǐng)域進(jìn)行連接的用戶也很重要,，因?yàn)檫@樣可以讓更多的用戶看到不同領(lǐng)域的內(nèi)容,。介數(shù)中心性衡量了特定節(jié)點(diǎn)出現(xiàn)在兩個其他節(jié)點(diǎn)之間最短路徑集的次數(shù)。
使用下面的代碼可以計(jì)算子圖的介數(shù)中心性：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')
如上圖所示,，節(jié)點(diǎn)的尺寸大小和介數(shù)中心性的大小成正比。具有較高介數(shù)中心性的節(jié)點(diǎn)被認(rèn)為是信息的傳遞者,，移除任意高介數(shù)中心性的節(jié)點(diǎn)將會撕裂網(wǎng)絡(luò),，將完整的圖打碎成幾個互不連通的子圖。中心性度量的指標(biāo)可以作為機(jī)器學(xué)習(xí)模型的特征,。在這篇文章中,，我們介紹了了一些最有影響力的圖算法。隨著社交數(shù)據(jù)的出現(xiàn),，圖網(wǎng)絡(luò)分析可以幫助我們改進(jìn)模型和創(chuàng)造價值,，甚至更多地了解這個世界。最后,，貼上本文代碼地址,。https://www./mlwhiz/top-graph-algorithmshttps:///data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513(*本文為AI科技大本營編譯文章，轉(zhuǎn)載請聯(lián)系微信 1092722531)
|
