作為數(shù)據(jù)科學(xué)家，我們已經(jīng)對(duì) Pandas 或 SQL 等關(guān)系數(shù)據(jù)庫(kù)非常熟悉了。我們習(xí)慣于將用戶屬性以列的形式展示在行中。但現(xiàn)實(shí)世界的數(shù)據(jù)果真如此嗎?

在互聯(lián)世界中，用戶不能被視為獨(dú)立的實(shí)體。他們之間存在一定的關(guān)系，我們有時(shí)希望在構(gòu)建機(jī)器學(xué)習(xí)模型時(shí)考慮到這些關(guān)系。

在關(guān)系數(shù)據(jù)庫(kù)中，我們無(wú)法在不同的行(用戶)之間利用這種關(guān)系，但在圖數(shù)據(jù)庫(kù)中，這樣做非常簡(jiǎn)單。

在這篇文章中，我們將討論一些數(shù)據(jù)科學(xué)家應(yīng)該了解的非常重要的圖算法，以及如何使用 Python 實(shí)現(xiàn)它們。

連接組件

 

 

我們都知道聚類的工作機(jī)制，你可以將連接組件視為一種在關(guān)聯(lián)/連接數(shù)據(jù)中查找集群/個(gè)體的硬聚類算法。

舉個(gè)例子：假設(shè)你有連接世界上任何兩個(gè)城市道路的數(shù)據(jù)�，F(xiàn)在你需要找出世界上所有大洲以及它們所包含的城市。

你將如何實(shí)現(xiàn)這一目標(biāo)呢?

我們采用的連接組件算法是基于廣度優(yōu)先搜索算法(Breadth First Search，BFS)/深度優(yōu)先搜索算法(Depth First Search，DFS)的特殊情況。這里不再展開介紹工作原理，我們只看一下如何使用 Networkx 啟動(dòng)和運(yùn)行此代碼。

應(yīng)用

從零售角度看：假設(shè)我們有很多客戶使用大量賬戶。使用連接組件算法的一種方法是在這個(gè)數(shù)據(jù)集中找出不同的族。

我們可以根據(jù)相同的信用卡使用情況、相同地址、相同手機(jī)號(hào)碼來(lái)建立某些客戶 ID 之間的連接。一旦有這些連接，我們就可以運(yùn)行連接組件算法為有連接的客戶創(chuàng)建單個(gè)集群，然后為其分配一個(gè)家庭 ID。

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

從金融角度：另一個(gè)用例是利用這些家庭 ID 抓捕詐騙犯。如果某個(gè)帳戶有過(guò)被欺詐經(jīng)歷，那么關(guān)聯(lián)帳戶很容易再次受到欺詐。

實(shí)施的可能性僅僅受到自身想象力的限制。(想象力越豐富，算法的應(yīng)用越廣泛。)

代碼

我們將使用 Python 中的 Networkx 模塊來(lái)創(chuàng)建和分析圖。下面以包含城市和城市間距離信息的圖為例，實(shí)現(xiàn)我們的目的。

 

 

帶有隨機(jī)距離的圖

首先創(chuàng)建一個(gè)帶有城市名(邊)和距離信息的列表，距離代表邊的權(quán)重。

 

 

讓我們使用 Networkx 創(chuàng)建一個(gè)圖:

 

 

現(xiàn)在我們想從這張圖中找出不同的大洲及其城市，這可以使用連接組件算法來(lái)實(shí)現(xiàn)：

 

 

如你所見，只需要利用頂點(diǎn)和邊，我們就能夠在數(shù)據(jù)中找到不同的組件。該算法可以在不同的數(shù)據(jù)上運(yùn)行，從而滿足上面提到的各種用例。

最短路徑

繼續(xù)使用上述示例，現(xiàn)在我們有德國(guó)城市及城市之間距離的圖。如何找到從法蘭克福(起始節(jié)點(diǎn))到慕尼黑的最短距離?我們用來(lái)解決此問(wèn)題的算法被稱為 Dijkstra。用 Dijkstra 自己的話說(shuō)：

從鹿特丹到格羅寧根旅行的最短路線是什么?這就是最短路徑算法，我花了大約 20 分鐘設(shè)計(jì)了它。一天早上，我和我的未婚妻在阿姆斯特丹購(gòu)物，累了，我們便坐在咖啡館的露臺(tái)上喝咖啡，我只想著能否實(shí)現(xiàn)最短路徑算法，然后我成功了。

正如我所說(shuō)，這是一個(gè)二十分鐘的發(fā)明。事實(shí)上，它發(fā)表于 1959 年，現(xiàn)在來(lái)看它的可讀性也非常高。它之所以如此美妙，其中一個(gè)原因就是我沒(méi)用筆紙就設(shè)計(jì)了它。后來(lái)我才知道，沒(méi)有筆紙?jiān)O(shè)計(jì)的有點(diǎn)之一是你不得不避免所有可避免的復(fù)雜問(wèn)題。最終，令我驚訝的是，這個(gè)算法成為我的著名成果之一。

應(yīng)用

Dijkstra 算法的變體在 Google 地圖中有著廣泛使用，用于尋找最短路線。

假設(shè)你有沃爾瑪商店中各個(gè)過(guò)道位置和過(guò)道之間距離的數(shù)據(jù)。您希望為從 A 到 D 的顧客提供最短路徑。

 

 

你已經(jīng)看到 LinkedIn 顯示一級(jí)連接和二級(jí)連接的方式。而這背后的機(jī)制是什么呢?

 

 

代碼

 

 

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

 

 

最小生成樹(Minimum Spanning Tree，MST)

現(xiàn)在我們面臨另一個(gè)問(wèn)題。假設(shè)我們?cè)谒�管鋪設(shè)公司或電線公司工作。我們需要使用最少的電線/管道來(lái)連接圖中所有城市。我們?nèi)绾巫龅竭@一點(diǎn)?

 

 

左：無(wú)向圖;右：對(duì)應(yīng) MST

應(yīng)用

最小生成樹在網(wǎng)絡(luò)設(shè)計(jì)中有直接應(yīng)用，包括計(jì)算機(jī)網(wǎng)絡(luò)、電信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、供水網(wǎng)絡(luò)和電網(wǎng)(最初是為它們發(fā)明的)。

MST 用于近似旅行商問(wèn)題。

聚類：首先構(gòu)建 MST，然后使用類間距離和類內(nèi)距離確定閾值，用于打破 MST 中某些邊。

圖像分割：首先在圖上構(gòu)建 MST，其中像素是節(jié)點(diǎn)，像素之間的距離基于某種相似性度量(顏色、強(qiáng)度等)

代碼

 

 

左：無(wú)向圖;右：對(duì)應(yīng) MST.

Pagerank

 

 

上圖為谷歌提供長(zhǎng)期支持的頁(yè)面排序算法(page sorting algorithm)。它根據(jù)輸入和輸出鏈接的數(shù)量和質(zhì)量為頁(yè)面打分。

應(yīng)用

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

它已被用于查找影響力最高的論文;

它已被 Google 用于網(wǎng)頁(yè)排名;

它可用于將推文-用戶和推文排序?yàn)楣?jié)點(diǎn)。如果用戶 A 跟帖用戶 B，則在用戶之間創(chuàng)建鏈接;如果用戶發(fā)推/轉(zhuǎn)推，則在用戶和推文之間建立鏈接;

推薦引擎。

代碼

在本次練習(xí)中，我們將使用 Facebook 數(shù)據(jù)。我們?cè)?facebook 用戶之間有一個(gè)邊/鏈接文件。首先通過(guò)以下方法創(chuàng)建 Facebook 圖：

 

 

它是這樣的：

 

 

現(xiàn)在我們想要找出具有高影響力的用戶。直觀地說(shuō)，Pagerank 算法會(huì)給擁有很多朋友的用戶打高分，而這些朋友又擁有很多 Facebook 朋友。

 

 

利用以下代碼可以得到排序的 PageRank 或最具影響力的用戶：

 

 

以上 ID 即為最有影響力的用戶。最具影響力用戶的子圖如下所示：

 

 

 

 

黃色為最具影響力用戶

中心性度量

你可以將許多中心性度量用作機(jī)器學(xué)習(xí)模型的特征，這里只談其中的兩個(gè)。

其他度量鏈接：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。

介數(shù)中心性：不僅擁有眾多朋友的用戶很重要，將一個(gè)地理位置連接到另一個(gè)位置的用戶也很重要，因?yàn)檫@樣可以讓用戶看到不同地點(diǎn)的內(nèi)容。

介數(shù)中心性量化了一個(gè)特定節(jié)點(diǎn)在其他兩個(gè)節(jié)點(diǎn)之間最短路徑中出現(xiàn)的次數(shù)。

點(diǎn)度中心性：它只是節(jié)點(diǎn)的連接數(shù)。

代碼

以下是查找子圖介數(shù)中心性的代碼：

 

 

 

你可以在此處查看按介數(shù)中心性值確定大小的節(jié)點(diǎn)。他們可以被認(rèn)為是信息傳遞者。打破任何具有高介數(shù)中心性的節(jié)點(diǎn)將會(huì)將圖形分成許多部分。

原文地址：https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513

標(biāo)簽： 數(shù)據(jù) 蒲Ъ

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。