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

2020-04-20 來源：raincent

作者：AI公園

導讀

因為圖分析是數(shù)據(jù)科學家的未來。

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

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

在一個互聯(lián)的世界里，用戶不能被視為獨立的實體。它們之間有一定的關系，我們在建立機器學習模型的時候，有時也會考慮這些關系。

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

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

1. 連通組件

一個包含3個連通組件的圖

我們都知道聚類是如何工作的。

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

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

你將如何實現(xiàn)這一點?來想想吧。

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

應用

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

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

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

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

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

代碼

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

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

使用隨機距離的圖

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

使用Networkx構建圖：

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

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

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

2. 最短路徑

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

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

我們用來解決這個問題的算法叫做Dijkstra。用Dijkstra自己的話來說：

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

- Edsger Dijkstra，在對Philip L. Frana的采訪中

應用

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

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