网站设建设,wordpress函数讲解,常州网站排名推广,wordpress设置水印作者#xff1a;Rahul Agarwal编译#xff1a;刘静图灵联邦编辑部出品本文作者Rahul Agarwal是一位数据科学家#xff0c;近期#xff0c;他在Medium上分享了常用的5种图算法的介绍和代码实现。以下是具体博文内容#xff1a;作为数据科学家#xff0c;我们已经对Pandas或… 作者Rahul Agarwal编译刘静图灵联邦编辑部出品本文作者Rahul Agarwal是一位数据科学家近期他在Medium上分享了常用的5种图算法的介绍和代码实现。以下是具体博文内容作为数据科学家我们已经对Pandas或SQL或任何其他关系数据库非常熟悉了。我们习惯于将在行中看到用户并且将他们的属性在列中展示。但现实世界真的是这样吗?在一个互联的世界里用户不能被视为独立的实体。他们之间有一定的关系我们在建立机器学习模型的时候有时也会考虑这些关系。现在虽然在关系数据库中我们不能在不同的行(用户)之间使用这样的关系但是在图数据库中这样做是相当简单的。在这篇文章中我将讨论一些您应该知道的最重要的图算法以及如何使用Python实现它们。此外这里是UCSanDiego关于Coursera的大数据图表分析课程我强烈建议您学习图理论的基础知识。课程链接https://www.coursera.org/learn/big-data-graph-analytics1、Connected Components(连通域)一张包含3个Connected Components的图大家应该都知道聚类是如何工作的吧您可以将非常接近的Connected Components视为一种在相关/连接数据中查找群集/孤岛的硬聚类算法。举一个具体的例子假设您有关于连接世界上任何两个城市的道路的数据。你的任务是需要找出世界上所有大陆以及它们所包含的城市。你将如何实现这一目标来想一想吧。我们用于执行此操作的Connected Components算法是基于BFS / DFS的特殊情况。我不会在这里谈论它是如何工作的但我们将看到如何使用Networkx启动和运行代码。应用从零售角度来看假设我们有很多客户使用大量账户。我们可以使用Connected Components算法的一种方法是在我们的数据集中找出不同的家庭。我们可以根据相同的信用卡使用情况、相同的地址或相同的移动电话号码等假定customer id之间的边(路)。一旦我们有了这些连接我们就可以运行Connected Components算法来创建单独的集群然后我们可以为其分配一个家庭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, Munchen, 84], [Augsburg, Karlsruhe, 250], [Kassel, Munchen, 502], [Kassel, Frankfurt, 173], [Frankfurt, Mannheim, 85], [Frankfurt, Wurzburg, 217], [Frankfurt, Kassel, 173], [Wurzburg, Numberg, 103], [Wurzburg, Erfurt, 186], [Wurzburg, Frankfurt, 217], [Karlsruhe, Mannheim, 80], [Karlsruhe, Augsburg, 250],[Mumbai, Delhi,400],[Delhi, Kolkata,500],[Kolkata, Bangalore,600],[TX, NY,1200],[ALB, NY,800]]我们用 Networkx创建一个图:g nx.Graph()for edge in edgelist:g.add_edge(edge[0],edge[1], weight edge[2])现在我们想从这张图中找出不同的大陆及其城市。可以使用连接组件算法执行此操作for i, x in enumerate(nx.connected_components(g)):print(ccstr(i):,x)------------------------------------------------------------cc0: {Frankfurt, Kassel, Munchen, Numberg, Erfurt, Stuttgart, Karlsruhe, Wurzburg, Mannheim, Augsburg}cc1: {Kolkata, Bangalore, Mumbai, Delhi}cc2: {ALB, NY, TX}如您所见我们能够在数据中找到不同的Components。只需使用边缘和顶点。该算法可以在不同的数据上运行以满足我上面提到的任何用例。2、Shortest Path(最短路径)继续上述示例我们将获得德国的城市及其相应距离的图。您想找到从法兰克福(起始节点)前往慕尼黑的最短距离。我们用来解决这个问题的算法叫做Dijkstra算法。用Dijkstra自己的话来说从鹿特丹到格罗宁根的最短途径是什么从特定城市到特定城市。这是最短路径的算法我花了大约20分钟设计。一天早上我和年轻的未婚妻在阿姆斯特丹购物累了我们坐在咖啡馆的露台上喝了一杯咖啡我只想着能否做到这一点然后我设计了最短路径的算法。正如我所说这是一个20分钟的发明。事实上它是在1959年出版的三年后。该出版物仍然可读事实上它相当不错。它之所以如此美妙其中一个原因就是我没用铅笔和纸张就设计了它。后来我才知道没有铅笔和纸的设计的一个优点是你不得不避免所有可避免的复杂性。最终令我大为惊讶的是这个算法成了我成名的基石之一。- Edsger Dijkstra接受ACM通讯公司Philip L. Frana的采访2001年应用Dijkstra算法的变体在Google地图中广泛使用以找到最短的路线。You are in a Walmart Store. You have different Aisles and distance between all the aisles. You want to provide the shortest pathway to the customer from Aisle A to Aisle D.您在沃尔玛商店。你知道不同的过道和所有过道之间的距离信息。您想要为客户提供从A通道到D通道的最短路径。你已经看到LinkedIn如何显示一级连接二级连接。幕后发生了什么代码print(nx.shortest_path(g, Stuttgart,Frankfurt,weightweight))print(nx.shortest_path_length(g, Stuttgart,Frankfurt,weightweight))--------------------------------------------------------[Stuttgart, Numberg, Wurzburg, Frankfurt]503您还可以使用以下命令找到所有对之间的最短路径for x in nx.all_pairs_dijkstra_path(g,weightweight):print(x)--------------------------------------------------------(Mannheim, {Mannheim: [Mannheim], Frankfurt: [Mannheim, Frankfurt], Karlsruhe: [Mannheim, Karlsruhe], Augsburg: [Mannheim, Karlsruhe, Augsburg], Kassel: [Mannheim, Frankfurt, Kassel], Wurzburg: [Mannheim, Frankfurt, Wurzburg], Munchen: [Mannheim, Karlsruhe, Augsburg, Munchen], Erfurt: [Mannheim, Frankfurt, Wurzburg, Erfurt], Numberg: [Mannheim, Frankfurt, Wurzburg, Numberg], Stuttgart: [Mannheim, Frankfurt, Wurzburg, Numberg, Stuttgart]})(Frankfurt, {Frankfurt: [Frankfurt], Mannheim: [Frankfurt, Mannheim], Kassel: [Frankfurt, Kassel], Wurzburg: [Frankfurt, Wurzburg], Karlsruhe: [Frankfurt, Mannheim, Karlsruhe], Augsburg: [Frankfurt, Mannheim, Karlsruhe, Augsburg], Munchen: [Frankfurt, Wurzburg, Numberg, Munchen], Erfurt: [Frankfurt, Wurzburg, Erfurt], Numberg: [Frankfurt, Wurzburg, Numberg], Stuttgart: [Frankfurt, Wurzburg, Numberg, Stuttgart]})....3、Minimum Spanning Tree(最小生成树)现在我们有另一个问题。我们在水管铺设公司或互联网光纤公司工作。我们需要使用最少量的电线/管道连接我们所拥有的图中的所有城市。我们如何做到这一点无向图及其右边的MST。应用最小生成树在网络设计中具有直接应用包括计算机网络电信网络运输网络供水网络和电网(这个算法最初是为它们发明的)MST用于近似商旅问题聚类 - 首先构造MST然后使用群集间距离和群集间距确定用于破坏MST中某些边缘的阈值。图像分割 - 它用于图像分割我们首先在图形上构建MST其中像素是节点像素之间的距离基于某种相似性度量(颜色强度等)代码# nx.minimum_spanning_tree(g) returns a instance of type graphnx.draw_networkx(nx.minimum_spanning_tree(g))我们图的MST。正如你所看到的上面是我们要铺设的电线。4、Pagerank(网页排名)这就是长期以来支持谷歌的页面排序算法。它根据输入和输出链接的数量和质量为每个网页分配分数。应用Pagerank可用于我们想要估算任何网络中节点重要性的任何地方。它已被用于使用引文找到最有影响力的论文。已被谷歌用于页面排名它可以用来给tweet排序——用户和tweet作为节点。如果用户A跟随用户B创建用户之间的链接如果用户tweet / retwets一条tweet则创建用户和tweet之间的链接推荐引擎代码在本练习中我们将使用Facebook数据。我们在facebook用户之间有一个边缘/链接文件。我们首先使用以下方法创建FB图# reading the datasetfb nx.read_edgelist(../input/facebook-combined.txt, create_using nx.Graph(), nodetype int)它是这样运作的:pos nx.spring_layout(fb)import warningswarnings.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()FB 用户图现在我们想要找到具有高影响力的用户。直观地说Pagerank算法会给有很多朋友的用户打高分而这些朋友又有很多facebook上的朋友。pageranks nx.pagerank(fb)print(pageranks)------------------------------------------------------{0: 0.006289602618466542,1: 0.00023590202311540972,2: 0.00020310565091694562,3: 0.00022552359869430617,4: 0.00023849264701222462,........}我们可以使用以下方式获取已排序的PageRank或最有影响力的用户import operatorsorted_pagerank sorted(pagerank.items(), keyoperator.itemgetter(1),reverse True)print(sorted_pagerank)------------------------------------------------------[(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),......]以上ID适用于最有影响力的用户。我们可以看到最有影响力的用户的子图first_degree_connected_nodes list(fb.neighbors(3437))second_degree_connected_nodes []for x in first_degree_connected_nodes:second_degree_connected_nodeslist(fb.neighbors(x))second_degree_connected_nodes.remove(3437)second_degree_connected_nodes list(set(second_degree_connected_nodes))subgraph_3437 nx.subgraph(fb,first_degree_connected_nodessecond_degree_connected_nodes)pos nx.spring_layout(subgraph_3437)node_color [yellow if v 3437 else red for v in subgraph_3437]node_size [1000 if v 3437 else 35 for v in subgraph_3437]plt.style.use(fivethirtyeight)plt.rcParams[figure.figsize] (20, 15)plt.axis(off)nx.draw_networkx(subgraph_3437, pos, with_labels False, node_colornode_color,node_sizenode_size )plt.show()我们最有影响力的用户(黄色)5、 Centrality Measures(中心度量)您可以将许多centrality measure算法用作机器学习模型的功能。我将谈谈其中两个。Betweenness Centrality:不仅拥有最多朋友的用户是重要的将一个地理位置连接到另一个地理位置的用户也很重要因为这样可以让用户看到来自不同地理位置的内容。Betweenness Centrality量化特定节点在两个其他节点之间的最短选择路径中的次数。Degree Centrality: 它只是节点的连接数。应用Centrality measures可以用作任何机器学习模型中的特征。代码以下是查找子图的Betweenness centrality的代码。pos nx.spring_layout(subgraph_3437)betweennessCentrality nx.betweenness_centrality(subgraph_3437,normalizedTrue, endpointsTrue)node_size [v * 10000 for v in betweennessCentrality.values()]plt.figure(figsize(20,20))nx.draw_networkx(subgraph_3437, pospos, with_labelsFalse,node_sizenode_size )plt.axis(off)您可以在此处查看按其betweenness centrality值确定大小的节点。他们可以被认为是信息传递者。打破任何具有高betweenness Centrality的节点将会将图形分成许多部分。结论在这篇文章中我谈到了一些改变了我们生活方式的最有影响力的图算法。随着社交数据的出现网络分析可以帮助我们改进模型和创造价值。甚至更多地了解这个世界。有很多图算法但这些是我最喜欢的算法。如果您愿意请更详细地研究算法。这是带有整个代码的Kaggle Kernel。https://www.kaggle.com/mlwhiz/top-graph-algorithms参考链接https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513觉得不错点个在看呗
