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

作者：AI公园

导读

因为图分析是数据科学家的未来。

作为数据科学家，我们对pandas、SQL或任何其他关系数据库非常熟悉。

我们习惯于将用户的属性以列的形式显示在行中。但现实世界真的是这样吗?

在一个互联的世界里，用户不能被视为独立的实体。它们之间有一定的关系，我们在建立机器学习模型的时候，有时也会考虑这些关系。

现在，虽然在关系数据库中，我们不能在不同的行(用户)之间使用这样的关系，但是在图形数据库中，这样做非常简单。

在本文中，我将讨论一些你应该知道的最重要的图算法，以及如何使用Python实现它们。

1. 连通组件

一个包含3个连通组件的图

我们都知道聚类是如何工作的。

你可以用外行人的术语来理解连通组件，它是一种硬聚类算法，可以在相关/连接的数据中找到聚类/岛屿

举个具体的例子：假设你有连接世界上任何两个城市的道路的数据。你需要找出世界上所有的大陆以及它们包含哪些城市

你将如何实现这一点?来想想吧。

我们使用的连通组件算法是基于BFS/DFS的特殊情况。我不会在这里过多地讨论它是如何工作的，但是我们将看到如何使用Networkx编写和运行代码。

应用

从零售的角度来看：假设我们有很多客户，使用很多账户。使用连通组件算法的一种方法是在数据集中找出明显不同的家族。

我们可以根据相同的信用卡使用情况、相同的地址或相同的移动电话号码等设定客户ID之间的边(路)。一旦我们有了这些连接，我们就可以运行连通组件算法来创建单独的簇，然后我们可以为其分配一个家族ID。

然后，我们可以使用这些家族ID根据家族需求提供个性化的推荐。我们还可以使用这个家族ID，通过创建基于家族的分组特征来支持我们的分类算法。

从财务的角度来看：另一个用例是使用这些家族ID捕获欺诈。如果一个账户在过去有过欺诈行为，关联账户很可能也容易进行欺诈。

可能性只受你自己想象力的限制。

代码

我们将使用Python中的Networkx模块来创建和分析图。

让我们从一个示例图开始，我们使用它来实现我们的目的。包含城市和城市之间的距离信息。

使用随机距离的图

我们首先创建一个带有距离的边的列表，我们把距离作为边的权重：

使用Networkx构建图：

现在我们想从这张图中找出不同的大陆及其包含的城市。

我们现在可以使用连通组件算法做到这一点：

正如你所看到的，我们能够在数据中找到不同的部分。只需要使用边和顶点。这个算法可以在不同的数据上运行，以满足我上面提到的任何用例。

2. 最短路径

继续上面的例子，我们得到了一个德国城市的图以及它们之间的距离。

你想知道如何从法兰克福(起始节点)到慕尼黑的最短距离。

我们用来解决这个问题的算法叫做Dijkstra。用Dijkstra自己的话来说：

从鹿特丹到[格罗宁根的最短路线是什么?一般来说，最短路径的算法是这样的，我花了大约20分钟来设计它。一天早上我在阿姆斯特丹和我的年轻的未婚妻购物，累了，我们坐在咖啡馆露台喝一杯咖啡，我就在想我能不能想出这个最短路径算法，然后我就想出来了。正如我所说，这是一个20分钟的发明。事实上，它是在1959年出版的。三年后，还可以读到，事实上，它相当不错。它如此漂亮的原因之一是我不用铅笔和纸来设计它。后来我了解到，不用铅笔和纸设计的好处之一是，你几乎不得不避免所有可以避免的复杂性。最终，令我大为惊讶的是，这个算法成了我成名的基石之一。

- Edsger Dijkstra，在对Philip L. Frana的采访中

应用

Dijkstra算法的变体广泛应用于谷歌地图中，用于寻找最短路径。

你在沃尔玛，你有不同的通道和所有通道之间的距离。你想要提供从A通道到D通道到客户的最短路径。