10种数据算法,数据科学家应该了解的5个图算法
在互联世界中,用户不是独立的实体,它们彼此之间具有一定的关系,我们有时在构建机器学习模型时就包括这些关系。
在关系数据库中,我们不能使用不同行(用户)之间的关系,而在图形数据库中,做到这一点相当简单。
在本文中,我将讨论一些我们应该了解的重要的图形算法,并且使用Python实现。
1. 连通分支有3个连通分支的图
我们都知道聚类的原理,可以将连通分支(Connected Components)视为一种硬聚类算法,然后在相关或连接的数据中查找聚类或孤岛。
举一个具体的例子:假设您有世界上连接任何两个城市的道路的数据,您需要找出世界上所有大洲及其所包含的城市。
应该如何实现?
该连通分支算法基于BFS / DFS的特殊情况。我不会讨论很多算法原理,但是会使用 Networkx 库来编写运行代码。
应用
比如在零售领域:假如有很多具有大量帐户的客户,我们就可以使用连通分支算法的找出不同的家庭。
我们可以根据相同的信用卡,相同的地址或相同的移动电话等作为客户ID之间的边(路)。有了这些连接,我们就可以运行连通分支算法,创建各个单独的家庭并且分配一个ID。
然后,我们可以利用家庭ID根据家庭需求提供个性化建议,还可以基于家庭来创建分组特征进一步分类。
从财务角度来看,另一个例子是使用这些家庭ID预防诈骗。如果某个帐户曾经进行过诈骗,则很有可能关联的帐户也容易受到诈骗。
代码
我们将使用 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("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算法变体在Google地图中广泛使用,用来找到最短的路线。
- 在沃尔玛商店中,有不同的过道以及过道之间的距离,您想找到从过道A到过道D的最短途径。
- 您LinkedIn可以显示1级关系,2级关系,背后的原理是什么?
代码
print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight'))print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))--------------------------------------------------------['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']503
您还可以使用以下命令找到所有对之间的最短路径:
for x in nx.all_pairs_dijkstra_path(g,weight='weight'): 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. 最小生成树(MST)
还有另一个问题。假如我们为水管铺设公司或互联网光纤公司工作。我们需要使用最少的水管或电线连接图中的所有城市,我们如何实现?
左侧为无向图,右侧为最小生成树
应用
- MST可应用于网络设计中,包括计算机网络,电信网络,运输网络,供水网络和电网(最初提出目的)。
- MST用于近似旅行商问题。
- 聚类 - 首先构造MST,然后使用群集间距离和群集内距离确定用于破坏MST中某些边的阈值。
- 图像分割 - 以像素为节点,像素之间的距离(基于某种相似性度量,颜色,强度等)的图形上构造一个MST。
代码
# nx.minimum_spanning_tree(g) 返回一个图类型的实例nx.draw_networkx(nx.minimum_spanning_tree(g))
图的最小生成树
如图所示,上面是我们的铺设电线方案。
4. Pagerank这是Google很长一段时间使用的页面排序算法。它根据传入和传出链接的数量和质量为页面分配分数。
应用
Pagerank可以在想要估计网络中节点重要性的地方使用。
- 它已被用于使用引文查找最具影响力的论文。
- 被Google用来对网页进行排名
- 它可以用来对tweets进行排名,User和Tweets作为节点。如果用户A关注用户B,则在用户之间创建链接;如果用户对某条推文进行推荐,则在用户和推文之间创建链接。
- 推荐引擎
代码
在本练习中,我们将使用Facebook数据。我们有一个Facebook用户之间的边/链接文件。我们首先使用以下方法创建FB图:
# 读取数据集fb = 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算法将为拥有很多朋友而他的朋友又拥有很多其他朋友的用户提供更高的分数。
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(pageranks.items(), key=operator.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_nodes =list(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_nodes second_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_color=node_color,node_size=node_size )plt.show()
最具影响力的用户(黄色)
5. Centrality Measures您可以将许多Centrality measures用作机器学习模型的特征。我将讨论其中的两个。
Betweenness Centrality::不仅有很多朋友的用户很重要,而且将一个地理位置连接到另一个地理位置的用户也很重要,因为这使用户可以查看来自不同地理位置的内容。Betweenness Centrality可量化特定节点进入其他两个节点之间最短选择路径的次数。
Degree Centrality:一个节点的连接数量。
应用
Centrality measures可用作任何机器学习模型的特征。
代码
这是用于找到子图的Betweenness centrality的代码。
pos = nx.spring_layout(subgraph_3437)betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)node_size = [v * 10000 for v in betweennessCentrality.values()]plt.figure(figsize=(20,20))nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False, node_size=node_size )plt.axis('off')
您可以在此处看到按其betweenness centrality值确定大小的节点。他们可以被认为是信息传递者。断开较高的betweenness Centrality的节点会将图分为很多部分。
总结
在本文中,我讨论了一些最有影响力的图算法,这些算法已经改变了我们的生活方式。
随着大量社交数据的到来,网络分析可以极大地改善我们的模型并创造价值,甚至更多地了解世界。
还有很多其他的图算法,如果你愿意,可以更详细地研究这些算法。
所有的代码Kaggle Kernel中(https://www.kaggle.com/mlwhiz/top-graph-algorithms)
- 02-21新兵下连后两年都是一样吗?新兵下连后干什么很多家长都弄不明白
- 11-23我愿守候这片天空 我愿栖身飞鱼服护你一世安好
- 12-01城市内涝水位监测安装:低洼路段积水水位监测方案
- 02-02一天到晚都没有排便怎么办?为什么几天没排便连便意都没有
- 03-19祖传藏品鉴宝骗局,手机鉴宝能排假难鉴真
- 05-05世界上出现的巨大不明生物:科学家在外星球发现奇特生物
- 12-18膝盖关节软骨磨损保守治疗方法:年纪轻轻膝盖软骨被完全磨损
- 04-13台风来袭暴风雨:阵雨,雷雨大雨
- 05-26高考压轴题数学求导技巧:高考数学突破压轴题策略之
- 01-19湖南的国资参与中车第二次重组:中车产投牵手天桥起重
- 11-13人性的阴暗面没有人看得见 人性的阴暗面
- 02-1572伏电动车要考什么驾驶证?你的电动车驾驶证考了吗
- 09-30马思纯的欢迎来到90年代:活色生香,的马思纯正在走上女演员的另一条大路
- 04-17梦见别人表白自己代表什么?梦见有人示爱就是幸福吗
- 03-15无下限知名品牌道歉下架:知名品牌紧急道歉月销10万
- 04-26城南旧事读书笔记 手抄报 简单:抄书打卡第2天城南旧事
热门
推荐
- 1如何使用干粉灭火器扑救初期火灾444
- 2六年级英语期中反思191
- 3公司运动会开幕式致辞150
- 4医院工伤证明书怎么写109
- 5食堂临时工人合同129
- 6我爱我的校园学生演讲稿172
- 7优秀数学手抄报的素材367
- 8世界上最大图书馆排行430