申请专栏作者 参展
投稿发布
您的当前位置:主页 > 机器学习 > 正文

PageRank、最小生成树:ML开发者应该了解的五种图

来源: 时间:2019-09-11
请支持本站,点击下面的广告后浏览!

作为数据科学家,我们已经对 Pandas 或 SQL 等关系数据库非常熟悉了。我们习惯于将用户属性以列的形式展示在行中。但现实世界的数据果真如此吗?

可思数据-www.sykv.cn,sykv.com

在互联世界中,用户不能被视为独立的实体。他们之间存在一定的关系,我们有时希望在构建机器学习模型时考虑到这些关系。

内容来自可思数据sykv.com

在关系数据库中,我们无法在不同的行(用户)之间利用这种关系,但在图数据库中,这样做非常简单。

可思数据sykv.com,sykv.cn

在这篇文章中,我们将讨论一些数据科学家应该了解的非常重要的图算法,以及如何使用 Python 实现它们。

可思数据sykv.com,sykv.cn

连接组件 可思数据sykv.com,sykv.cn

 

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

可思数据-人工智能资讯平台sykv.com

我们都知道聚类的工作机制,你可以将连接组件视为一种在关联/连接数据中查找集群/个体的硬聚类算法。 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

举个例子:假设你有连接世界上任何两个城市道路的数据。现在你需要找出世界上所有大洲以及它们所包含的城市。

可思数据sykv.com,sykv.cn

你将如何实现这一目标呢?

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

我们采用的连接组件算法是基于广度优先搜索算法(Breadth First Search,BFS)/深度优先搜索算法(Depth First Search,DFS)的特殊情况。这里不再展开介绍工作原理,我们只看一下如何使用 Networkx 启动和运行此代码。

可思数据-人工智能资讯平台sykv.com

应用 可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

从零售角度看:假设我们有很多客户使用大量账户。使用连接组件算法的一种方法是在这个数据集中找出不同的族。 可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

我们可以根据相同的信用卡使用情况、相同地址、相同手机号码来建立某些客户 ID 之间的连接。一旦有这些连接,我们就可以运行连接组件算法为有连接的客户创建单个集群,然后为其分配一个家庭 ID。

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

然后,我们可以利用这些家庭 ID,根据家庭需求提供个性化推荐。我们还可以利用家庭 ID,通过创建基于家庭的分组功能来推进分类算法。

可思数据sykv.com,sykv.cn

从金融角度:另一个用例是利用这些家庭 ID 抓捕诈骗犯。如果某个帐户有过被欺诈经历,那么关联帐户很容易再次受到欺诈。

可思数据sykv.com,sykv.cn

实施的可能性仅仅受到自身想象力的限制。(想象力越丰富,算法的应用越广泛。)

本文来自可思数据(sykv.com),转载请联系本站及注明出处

代码

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

我们将使用 Python 中的 Networkx 模块来创建和分析图。下面以包含城市和城市间距离信息的图为例,实现我们的目的。

可思数据-www.sykv.cn,sykv.com

  可思数据sykv.com,sykv.cn

  可思数据-人工智能资讯平台sykv.com

带有随机距离的图 可思数据-人工智能资讯平台sykv.com

首先创建一个带有城市名(边)和距离信息的列表,距离代表边的权重。 内容来自可思数据sykv.com

 

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

  内容来自可思数据sykv.com

让我们使用 Networkx 创建一个图: 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

  内容来自可思数据sykv.com

 

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

现在我们想从这张图中找出不同的大洲及其城市,这可以使用连接组件算法来实现: 内容来自可思数据sykv.com

 

可思数据sykv.com,sykv.cn

 

内容来自可思数据sykv.com

如你所见,只需要利用顶点和边,我们就能够在数据中找到不同的组件。该算法可以在不同的数据上运行,从而满足上面提到的各种用例。 内容来自可思数据sykv.com

最短路径 可思数据sykv.com

继续使用上述示例,现在我们有德国城市及城市之间距离的图。如何找到从法兰克福(起始节点)到慕尼黑的最短距离?我们用来解决此问题的算法被称为 Dijkstra。用 Dijkstra 自己的话说:

内容来自可思数据sykv.com

从鹿特丹到格罗宁根旅行的最短路线是什么?这就是最短路径算法,我花了大约 20 分钟设计了它。一天早上,我和我的未婚妻在阿姆斯特丹购物,累了,我们便坐在咖啡馆的露台上喝咖啡,我只想着能否实现最短路径算法,然后我成功了。 可思数据sykv.com

正如我所说,这是一个二十分钟的发明。事实上,它发表于 1959 年,现在来看它的可读性也非常高。它之所以如此美妙,其中一个原因就是我没用笔纸就设计了它。后来我才知道,没有笔纸设计的有点之一是你不得不避免所有可避免的复杂问题。最终,令我惊讶的是,这个算法成为我的著名成果之一。 可思数据sykv.com

应用

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

Dijkstra 算法的变体在 Google 地图中有着广泛使用,用于寻找最短路线。

可思数据sykv.com,sykv.cn

假设你有沃尔玛商店中各个过道位置和过道之间距离的数据。您希望为从 A 到 D 的顾客提供最短路径。 可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

可思数据-www.sykv.cn,sykv.com

你已经看到 LinkedIn 显示一级连接和二级连接的方式。而这背后的机制是什么呢? 可思数据sykv.com,sykv.cn

  内容来自可思数据sykv.com

 

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

代码 内容来自可思数据sykv.com

  可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

  可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

你也可以找到所有对之间的最短路径: 可思数据sykv.com

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

可思数据-人工智能资讯平台sykv.com

最小生成树(Minimum Spanning Tree,MST) 可思数据sykv.com

现在我们面临另一个问题。假设我们在水管铺设公司或电线公司工作。我们需要使用最少的电线/管道来连接图中所有城市。我们如何做到这一点? 可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

左:无向图;右:对应 MST 可思数据sykv.com,sykv.cn

应用 可思数据sykv.com,sykv.cn

最小生成树在网络设计中有直接应用,包括计算机网络、电信网络、交通网络、供水网络和电网(最初是为它们发明的)。 可思数据sykv.com,sykv.cn

MST 用于近似旅行商问题。 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

聚类:首先构建 MST,然后使用类间距离和类内距离确定阈值,用于打破 MST 中某些边。 可思数据sykv.com

图像分割:首先在图上构建 MST,其中像素是节点,像素之间的距离基于某种相似性度量(颜色、强度等) 可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

代码 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

 

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

  可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

左:无向图;右:对应 MST. 可思数据-人工智能资讯平台sykv.com

Pagerank 可思数据sykv.com

  可思数据-人工智能资讯平台sykv.com

 

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

上图为谷歌提供长期支持的页面排序算法(page sorting algorithm)。它根据输入和输出链接的数量和质量为页面打分。

可思数据-www.sykv.cn,sykv.com

应用

可思数据sykv.com

Pagerank 可用于任何我们想要估算网络节点重要性的地方。 可思数据sykv.com,sykv.cn

它已被用于查找影响力最高的论文;

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

它已被 Google 用于网页排名;

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

它可用于将推文-用户和推文排序为节点。如果用户 A 跟帖用户 B,则在用户之间创建链接;如果用户发推/转推,则在用户和推文之间建立链接;

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

推荐引擎。 可思数据sykv.com,sykv.cn

代码 可思数据sykv.com

在本次练习中,我们将使用 Facebook 数据。我们在 facebook 用户之间有一个边/链接文件。首先通过以下方法创建 Facebook 图:

可思数据-人工智能资讯平台sykv.com

 

可思数据sykv.com,sykv.cn

  可思数据-www.sykv.cn,sykv.com

它是这样的:

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

可思数据-人工智能资讯平台sykv.com

  内容来自可思数据sykv.com

现在我们想要找出具有高影响力的用户。直观地说,Pagerank 算法会给拥有很多朋友的用户打高分,而这些朋友又拥有很多 Facebook 朋友。 可思数据sykv.com,sykv.cn

  可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

 

可思数据-人工智能资讯平台sykv.com

利用以下代码可以得到排序的 PageRank 或最具影响力的用户: 可思数据-www.sykv.cn,sykv.com

 

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

  可思数据-人工智能资讯平台sykv.com

以上 ID 即为最有影响力的用户。最具影响力用户的子图如下所示:

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

  可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

  可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

 

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

  可思数据-www.sykv.cn,sykv.com

黄色为最具影响力用户 可思数据sykv.com,sykv.cn

中心性度量

可思数据-人工智能资讯平台sykv.com

你可以将许多中心性度量用作机器学习模型的特征,这里只谈其中的两个。 可思数据-人工智能资讯平台sykv.com

其他度量链接:https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。 可思数据sykv.com,sykv.cn

介数中心性:不仅拥有众多朋友的用户很重要,将一个地理位置连接到另一个位置的用户也很重要,因为这样可以让用户看到不同地点的内容。 可思数据sykv.com

介数中心性量化了一个特定节点在其他两个节点之间最短路径中出现的次数。 可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

点度中心性:它只是节点的连接数。

可思数据sykv.com,sykv.cn

代码

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

以下是查找子图介数中心性的代码:

可思数据-www.sykv.cn,sykv.com

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

 

 

内容来自可思数据sykv.com

你可以在此处查看按介数中心性值确定大小的节点。他们可以被认为是信息传递者。打破任何具有高介数中心性的节点将会将图形分成许多部分。

内容来自可思数据sykv.com

原文地址:https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513

可思数据sykv.com,sykv.cn


转发量:

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片

关于我们   免责声明   广告合作   版权声明   联系方式   原创投稿   网站地图  

Copyright©2005-2019 Sykv.com 可思数据 版权所有    ICP备案:京ICP备14056871号

人工智能资讯   人工智能资讯   人工智能资讯   人工智能资讯

扫码入群
咨询反馈
扫码关注

微信公众号

返回顶部
关闭