作者：AI公園

導(dǎo)讀

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

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

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

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

現(xiàn)在，雖然在關(guān)系數(shù)據(jù)庫(kù)中，我們不能在不同的行(用戶(hù))之間使用這樣的關(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è)我們有很多客戶(hù)，使用很多賬戶(hù)。使用連通組件算法的一種方法是在數(shù)據(jù)集中找出明顯不同的家族。

我們可以根據(jù)相同的信用卡使用情況、相同的地址或相同的移動(dòng)電話號(hào)碼等設(shè)定客戶(hù)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è)賬戶(hù)在過(guò)去有過(guò)欺詐行為，關(guān)聯(lián)賬戶(hù)很可能也容易進(jìn)行欺詐。

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

代碼

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

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

 

 

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

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

 

 

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

 

 

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

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

 

 

正如你所看到的，我們能夠在數(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通道到客戶(hù)的最短路徑。

 

 

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

 

 

代碼

 

 

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

 

 

3. 最小生成樹(shù)

 

 

現(xiàn)在我們有另一個(gè)問(wèn)題。我們?yōu)橐患宜�管鋪設(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)度等)。

代碼

 

 

 

 

我們的圖的最小生成樹(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-用戶(hù)和以及tweets-tweets當(dāng)成節(jié)點(diǎn)進(jìn)行排序。如果用戶(hù)A關(guān)注了用戶(hù)B，那么創(chuàng)建用戶(hù)之間的鏈接，如果用戶(hù)tweet/retwets一條tweet，則創(chuàng)建用戶(hù)和tweet之間的鏈接。

推薦引擎

代碼

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

 

 

它是這樣的：

 

 

 

 

FaceBook用戶(hù)圖

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

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

 

 

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

 

 

以上id適用于最有影響力的用戶(hù)。

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

 

 

 

 

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

5. 中心度量

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

內(nèi)中心：重要的不僅是擁有最多朋友的用戶(hù)，將一個(gè)地理位置與另一個(gè)地理位置連接起來(lái)的用戶(hù)也很重要，因?yàn)檫@讓用戶(hù)可以看到來(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)中心。

 

 

 

 

可以看到，在這里按它們的內(nèi)中心值調(diào)整節(jié)點(diǎn)的大小。他們可以被認(rèn)為是信息傳遞者。將具有高內(nèi)中心的任何節(jié)點(diǎn)斷開(kāi)將會(huì)將圖分成許多部分。

總結(jié)

在這篇文章中，我討論了一些最具影響力的圖算法，它們改變了我們的生活方式

隨著如此多的社會(huì)數(shù)據(jù)的出現(xiàn)，網(wǎng)絡(luò)分析可以在很大程度上幫助我們改進(jìn)模型和產(chǎn)生價(jià)值。

甚至更多地了解這個(gè)世界。

標(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)系。