当前位置: 首页 > 科技观察

数据科学家需要知道的5个图算法

时间:2023-03-18 17:00:16 科技观察

介绍因为图分析是数据科学家的未来。作为数据科学家,我们对pandas、SQL或任何其他关系数据库都非常熟悉。我们习惯于在列中以行显示用户属性。但现实世界真的是这样吗?在互联世界中,用户不能被视为独立的实体。它们之间存在一定的关系,我们有时在构建机器学习模型时会考虑这些关系。现在,虽然在关系数据库中我们不能在不同行(用户)之间使用这种关系,但在图形数据库中这样做很容易。在本文中,我将讨论一些您应该了解的最重要的图算法以及如何使用Python实现它们。1.连通分量具有3个连通分量的图我们都知道聚类是如何工作的。你可以通俗的理解ConnectedComponents,它是一种hardclustering算法,在related/connecteddata中找到clusters/islands举个具体的例子:假设你在世界道路数据中有任意两个城市之间的连接。您需要找出世界上所有的大陆以及它们包含哪些城市。你打算怎么做?想一想。我们使用的连通分量算法是基于BFS/DFS的一个特例。我不会在这里过多地谈论它是如何工作的,但我们将看到如何使用Networkx编写和运行代码。应用程序从零售的角度来看:假设我们有很多客户,使用很多帐户。使用连通分量算法的一种方法是在数据集中找到截然不同的家族。我们可以根据相同的信用卡使用情况、相同的地址或相同的手机号码等设置客户ID之间的边(路)。一旦我们有了这些连接,我们就可以运行连接组件算法来创建单独的集群,这然后我们可以分配一个家庭ID。然后,我们可以使用这些家庭ID,根据家庭需求提供个性化推荐。我们还可以使用此家族ID通过创建基于家族的分组功能来支持我们的分类算法。从财务角度来看:另一个用例是使用这些家庭ID来捕捉欺诈行为。如果一个账户过去曾被欺诈,那么关联账户也很可能容易受到欺诈。可能性仅受您自己的想象力限制。代码我们将使用Python中的Networkx模块来创建和分析图形。让我们从我们用于我们目的的示例图开始。包含城市和城市之间的距离信息。具有随机距离的图我们首先创建一个具有距离的边列表,我们使用距离作为边权重: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','慕尼黑',84],['奥格斯堡','卡尔斯鲁厄',250],['卡塞尔','慕尼黑',502],['卡塞尔','法兰克福',173],['法兰克福','曼海姆',85],['法兰克福','维尔茨堡',217],['法兰克福','卡塞尔',173],['维尔茨堡','Numberg',103],['维尔茨堡','埃尔福特',186],['维尔茨堡','法兰克福',217],['卡尔斯鲁厄','曼海姆',80],['卡尔斯鲁厄','奥格斯堡',250],["孟买","德里",400],["德里","加尔各答",500],["加尔各答","班加罗尔",600],["TX","纽约",1200],["ALB","纽约",800]]使用Networkx构建图:g=nx.Graph()foredgeinedgelist:g.add_edge(edge[0],edge[1],weight=edge[2])现在我们要找出不同的大陆和红外线包含的城市我们现在可以使用连通分量算法来做到这一点:fori,xinenumerate(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'}如您所见,我们能够在数据中找到不同的部分。只需使用边和顶点。该算法可以在不同的数据上运行,以满足我上面提到的任何用例。2.最短路径继续上面的例子,我们有一张德国城市的地图和它们之间的距离。您想知道如何获得从法兰克福(起始节点)到慕尼黑的最短距离。我们用来解决这个问题的算法叫做Dijkstra。用Dijkstra自己的话来说:从鹿特丹到【格罗宁根的最短路线是什么?总的来说,最短路径的算法是这样的,我设计了大概20分钟。一天早上,我和我年轻的未婚妻在阿姆斯特丹购物,累了,我们坐在咖啡馆的露台上喝杯咖啡,我想知道我是否能想出这个最短路径算法,我来了。正如我所说,这是一个20分钟的发明。其实它是1959年出版的,三年过去了,还能读,其实还不错。它如此美丽的原因之一是我没有使用铅笔和纸来设计它。后来我了解到,不用纸笔进行设计的好处之一就是你几乎必须避免所有可以避免的复杂性。最终,令我惊讶的是,这个算法成为我成名的基石之一。-EdsgerDijkstra,在PhilipL.Frana的采访中应用Dijkstra算法的变体在Google地图中广泛用于寻找最短路径。你在沃尔玛,你有不同的过道和所有过道之间的距离。您想要为客户提供从通道A到通道D的最短路径。您可以看到LinkedIn如何显示一级和二级连接。幕后发生了什么?代码print(nx.shortest_path(g,'Stuttgart','Frankfurt',weight='weight'))print(nx.shortest_path_length(g,'Stuttgart','Frankfurt',weight='weight'))---------------------------------------------------['Stuttgart','Numberg','Wurzburg','Frankfurt']503你也可以找到所有位置对之间的最短路径:forxinnx.all_pairs_dijkstra_path(g,weight='weight'):print(x)---------------------------------------------------('曼海姆',{'曼海姆':['曼海姆'],'法兰克福':['曼海姆','法兰克福'],'卡尔斯鲁厄':['曼海姆'','卡尔斯鲁厄'],'奥格斯堡':['曼海姆','卡尔斯鲁厄','奥格斯堡'],'卡塞尔':['曼海姆','法兰克福','卡塞尔'],'维尔茨堡':['曼海姆','法兰克福','维尔茨堡'],'慕尼黑':['曼海姆','卡尔斯鲁厄','奥格斯堡','慕尼黑'],'埃尔福特':['曼海姆','法兰克福','维尔茨堡','埃尔福特'],'Numberg':['曼海姆','法兰克福','维尔茨堡','Numberg'],'斯图加特':['曼海姆','法兰克福','维尔茨堡','Numberg','斯图加特']})('法兰克福',{'法兰克福':['法兰克福'],'曼海姆':['法兰克福','曼海姆'],'卡塞尔:['法兰克福','卡塞尔'],'维尔茨堡':['法兰克福','维尔茨堡'],'卡尔斯鲁厄':['法兰克福','曼海姆','卡尔斯鲁厄'],'奥格斯堡':['法兰克福','曼海姆','卡尔斯鲁厄','奥格斯堡'],'慕尼黑':['法兰克福','维尔茨堡','Numberg','慕尼黑'],'爱尔福特':['法兰克福','维尔茨堡','Erfurt'],'Numberg':['Frankfurt','Wurzburg','Numberg'],'Stuttgart':['Frankfurt','Wurzburg','Numberg','Stuttgart']})...3.最小生成树现在我们有另一个问题我们为管道公司或互联网光纤公司工作。我们需要用最少的电线/管道连接图中的所有城市,我们该怎么做?最小生成树在右边的无向图应用最小生成树直接应用于网络设计,包括计算机网络、电信网络、交通网络、供水网络和电网(它们最初是为此而发明的)MST用于近似旅行商问题聚类——首先构建MST,然后使用簇间和簇内距离来确定MST中某些边的分割阈值。图像分割——对于图像分割,我们首先在图上构建一个MST,其中像素是节点,像素之间的距离基于某种相似性度量(颜色、强度等)。代码#nx.minimum_spanning_tree(g)returnsainstanceoftypegraphnx.draw_networkx(nx.minimum_spanning_tree(g))可以看到我们图的最小生成树,上面是我们需要铺的线。4.Pagerank这是谷歌长期支持的页面排名算法。它根据传入和传出链接的数量和质量为页面分配分数。ApplyingPagerank可以用在任何我们想要估计节点在任何网络中的重要性的地方。它用于使用引文查找最有影响力的论文。被谷歌用来对页面进行排名。它可用于将tweets-user和tweets-tweets作为节点进行排名。如果用户A关注用户B,则在用户之间创建链接,如果用户发布/转发推文,则在用户和推文之间创建链接。推荐引擎代码在本练习中,我们将使用Facebook数据。我们有一个facebook用户之间的边缘/链接文件。我们首先创建FB图,使用:#readingthedatasetfb=nx.read_edgelist('../input/facebook-combined.txt',create_using=nx.Graph(),nodetype=int)它看起来像这样:pos=nx。spring_layout(fb)importwarningswarnings.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()FaceBookUserGraph现在我们想找到具有高影响力的用户。直观上,Pagerank算法会给朋友多的用户打高分,而这些朋友在Facebook上有很多朋友。pageranks=nx.pagerank(fb)print(pageranks)-----------------------------------------------------{0:0.006289602618466542,1:0.00023590202311540972,2:0.00020310565091694562,3:0.00022552359869430617,4:0.000238492647012224562WecanuseRan...Getthemostinfluentialusersorting:importoperatorsorted_pa??gerank=sorted(pageranks.items(),key=operator.itemgetter(1),reverse=True)print(sorted_pa??gerank)------------------------------------------------------[(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),......]以上ids是给最有影响力的用户的。我们可以看到最具影响力用户的子图:first_degree_connected_nodes=list(fb.neighbors(3437))second_degree_connected_nodes=[]forxinfirst_degree_connected_nodes:second_degree_connected_nodes+=list(fb.neighbors(x))second_degree_connected_nodes=.remove7(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'ifv==3437else'red'forvinsubgraph_3437]node_size=[1000ifv==3437else34forvinsubgraph37]plt_3.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()最有影响力的用户(黄色)5.中心性度量有许多中心性度量可以用作机器学习模型的特征。我将讨论其中的两个。内部枢纽:重要的不仅是拥有最多朋友的用户,还有将一个位置连接到另一个位置的用户,因为这允许用户查看来自不同位置的内容。内中心性衡量一个特定节点出现在其他两个节点之间的最短路径中的次数度中心性:它是一个节点的连接数。应用中心性度量可以用作任何机器学习模型的特征。Codeface的代码用于查找子图的内点。pos=nx.spring_layout(subgraph_3437)betweennessCentrality=nx.betweenness_centrality(subgraph_3437,normalized=True,endpoints=True)node_size=[v*10000forvinbetweennessCentrality.values()]plt.figure(figsize=(20,20))nx.draw_networkx(subgraph_3437,pos=pos,with_labels=False,node_size=node_size)plt.axis('off')可以看到,这里根据节点的内中心值调整节点的大小。他们可以被认为是信使。断开任何具有高内中心的节点会将图形分成许多部分。总结在本文中,我讨论了一些最有影响力的图算法,它们改变了我们的生活方式。进一步了解这个世界。