數(shù)據(jù)科學(xué)家需要知道的5種圖算法
2019-12-30 來源：raincent
作者：AI公園
導(dǎo)讀
因?yàn)閳D分析是數(shù)據(jù)科學(xué)家的未來。
作為數(shù)據(jù)科學(xué)家，我們對pandas、SQL或任何其他關(guān)系數(shù)據(jù)庫非常熟悉。
我們習(xí)慣于將用戶的屬性以列的形式顯示在行中。但現(xiàn)實(shí)世界真的是這樣嗎?
在一個(gè)互聯(lián)的世界里，用戶不能被視為獨(dú)立的實(shí)體。它們之間有一定的關(guān)系，我們在建立機(jī)器學(xué)習(xí)模型的時(shí)候，有時(shí)也會考慮這些關(guān)系。
現(xiàn)在，雖然在關(guān)系數(shù)據(jù)庫中，我們不能在不同的行(用戶)之間使用這樣的關(guān)系，但是在圖形數(shù)據(jù)庫中，這樣做非常簡單。
在本文中，我將討論一些你應(yīng)該知道的最重要的圖算法，以及如何使用Python實(shí)現(xiàn)它們。
1. 連通組件
一個(gè)包含3個(gè)連通組件的圖
我們都知道聚類是如何工作的。
你可以用外行人的術(shù)語來理解連通組件，它是一種硬聚類算法，可以在相關(guān)/連接的數(shù)據(jù)中找到聚類/島嶼
舉個(gè)具體的例子：假設(shè)你有連接世界上任何兩個(gè)城市的道路的數(shù)據(jù)。你需要找出世界上所有的大陸以及它們包含哪些城市
你將如何實(shí)現(xiàn)這一點(diǎn)?來想想吧。
我們使用的連通組件算法是基于BFS/DFS的特殊情況。我不會在這里過多地討論它是如何工作的，但是我們將看到如何使用Networkx編寫和運(yùn)行代碼。
應(yīng)用
從零售的角度來看：假設(shè)我們有很多客戶，使用很多賬戶。使用連通組件算法的一種方法是在數(shù)據(jù)集中找出明顯不同的家族。
我們可以根據(jù)相同的信用卡使用情況、相同的地址或相同的移動電話號碼等設(shè)定客戶ID之間的邊(路)。一旦我們有了這些連接，我們就可以運(yùn)行連通組件算法來創(chuàng)建單獨(dú)的簇，然后我們可以為其分配一個(gè)家族ID。
然后，我們可以使用這些家族ID根據(jù)家族需求提供個(gè)性化的推薦。我們還可以使用這個(gè)家族ID，通過創(chuàng)建基于家族的分組特征來支持我們的分類算法。
從財(cái)務(wù)的角度來看：另一個(gè)用例是使用這些家族ID捕獲欺詐。如果一個(gè)賬戶在過去有過欺詐行為，關(guān)聯(lián)賬戶很可能也容易進(jìn)行欺詐。
可能性只受你自己想象力的限制。
代碼
我們將使用Python中的Networkx模塊來創(chuàng)建和分析圖。
讓我們從一個(gè)示例圖開始，我們使用它來實(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è)德國城市的圖以及它們之間的距離。
你想知道如何從法蘭克福(起始節(jié)點(diǎn))到慕尼黑的最短距離。
我們用來解決這個(gè)問題的算法叫做Dijkstra。用Dijkstra自己的話來說：
從鹿特丹到[格羅寧根的最短路線是什么?一般來說，最短路徑的算法是這樣的，我花了大約20分鐘來設(shè)計(jì)它。一天早上我在阿姆斯特丹和我的年輕的未婚妻購物，累了，我們坐在咖啡館露臺喝一杯咖啡，我就在想我能不能想出這個(gè)最短路徑算法，然后我就想出來了。正如我所說，這是一個(gè)20分鐘的發(fā)明。事實(shí)上，它是在1959年出版的。三年后，還可以讀到，事實(shí)上，它相當(dāng)不錯(cuò)。它如此漂亮的原因之一是我不用鉛筆和紙來設(shè)計(jì)它。后來我了解到，不用鉛筆和紙?jiān)O(shè)計(jì)的好處之一是，你幾乎不得不避免所有可以避免的復(fù)雜性。最終，令我大為驚訝的是，這個(gè)算法成了我成名的基石之一。
- Edsger Dijkstra，在對Philip L. Frana的采訪中
應(yīng)用
Dijkstra算法的變體廣泛應(yīng)用于谷歌地圖中，用于尋找最短路徑。
你在沃爾瑪，你有不同的通道和所有通道之間的距離。你想要提供從A通道到D通道到客戶的最短路徑。
你可以看到LinkedIn如何顯示1級和2級的連接。幕后發(fā)生了什么?
代碼
你也可以找到所有的地點(diǎn)對之間的最短路徑：
3. 最小生成樹
現(xiàn)在我們有另一個(gè)問題。我們?yōu)橐患宜茕佋O(shè)公司或互聯(lián)網(wǎng)光纖公司工作。我們需要用最少的電線/管道連接圖中所有的城市，我們該怎么做?
一個(gè)無向圖，右邊是它的最小生成樹
應(yīng)用
最小生成樹直接應(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用于逼近旅行商問題
聚類 — 首先構(gòu)造MST，然后使用簇間距離和簇內(nèi)距離確定MST中某些邊緣的分割閾值。
圖像分割 — 用于圖像分割，我們首先在一個(gè)圖上構(gòu)造一個(gè)MST，其中像素是節(jié)點(diǎn)，像素之間的距離基于一些相似性度量(顏色、強(qiáng)度等)。
代碼
我們的圖的最小生成樹
可以看到，上面就是我們需要鋪設(shè)的電線。
4. Pagerank
這就是長期以來支持谷歌的頁面排序算法。它根據(jù)輸入和輸出鏈接的數(shù)量和質(zhì)量為頁面分配一個(gè)分?jǐn)?shù)。
應(yīng)用
Pagerank可以用于任何我們想要估計(jì)任何網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的地方。
它被用來尋找最具影響力的論文使用引文。
被谷歌用來排列頁面
它可以用來把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圖，使用：
它是這樣的：
FaceBook用戶圖
現(xiàn)在我們想要找到具有高影響力的用戶。
直觀地說，Pagerank算法會給有很多朋友的用戶打高分，而這些朋友又有很多facebook上的朋友。
我們可以用PageRank得到最有影響力的用戶排序：
以上id適用于最有影響力的用戶。
我們可以看到最具影響力用戶的子圖：
最有影響力的用戶(黃色)
5. 中心度量
有許多中心度量，你都可以將其用作機(jī)器學(xué)習(xí)模型的特征。我將討論其中的兩個(gè)。
內(nèi)中心：重要的不僅是擁有最多朋友的用戶，將一個(gè)地理位置與另一個(gè)地理位置連接起來的用戶也很重要，因?yàn)檫@讓用戶可以看到來自不同地理位置的內(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)斷開將會將圖分成許多部分。
總結(jié)
在這篇文章中，我討論了一些最具影響力的圖算法，它們改變了我們的生活方式
隨著如此多的社會數(shù)據(jù)的出現(xiàn)，網(wǎng)絡(luò)分析可以在很大程度上幫助我們改進(jìn)模型和產(chǎn)生價(jià)值。
甚至更多地了解這個(gè)世界。
標(biāo)簽： 數(shù)據(jù) 蒲Ъ
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
