设为首页 - 加入收藏 大兴安岭网 (http://www.0457zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 联通 时代 关于 升级
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

大势所趋!数据科学家必知的5种图算法

发布时间:2019-09-27 07:31 所属栏目:[优化] 来源:读芯术
导读:在万物相连的世界里,用户并不是独立的个体,彼此之间都有某种联系。构建机器学习模型时,有时也会将这种联系放入模型中。 虽然关系数据库中无法在不同数行(用户)间使用这种关系,但在图数据库里,这样做非常简单。 本文将介绍一些数据科学家必知的重要的

在万物相连的世界里,用户并不是独立的个体,彼此之间都有某种联系。构建机器学习模型时,有时也会将这种联系放入模型中。

大势所趋!数据科学家必知的5种图算法

虽然关系数据库中无法在不同数行(用户)间使用这种关系,但在图数据库里,这样做非常简单。

本文将介绍一些数据科学家必知的重要的图算法,并阐释如何用Python来使用它们。

另外,强烈推荐先学习图理论基础。

圣地亚哥大学发布于Coursera上的大数据课程的图分析课:https://www.coursera.org/learn/big-data-graph-analytics?ranMID=40328&ranEAID=lVarvwc5BD0&ranSiteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&siteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&utm_content=2&utm_medium=partners&utm_source=linkshare&utm_campaign=lVarvwc5BD0

1. 连通分支

大势所趋!数据科学家必知的5种图算法

包含3个连接组件的图

大家都知道聚类算法如何工作吧?

简单地说,就是将连通分支看作一种硬聚类算法,让它在相关/相连数据中找到聚类/岛。

举个具体的例子:假设有一份连接世界上任意两个城市的道路数据,而你需要借此找到世界上所有大洲和所包含的城市。

这要如何实现呢?开动脑筋吧。

此处使用的连通分支算法是基于BFS/DFS的特殊情况,此处不多赘述。以下会解释如何使用Networkx启动和运行代码。

应用

从零售的角度来看:假设有很多客户使用很多的帐户,连通分支算法可用于在数据集中找出不同的家庭。

根据相同的信用卡使用情况、相同的地址或相同的电话号码等,可以假定客户ID之间的联系(路)。一旦有了这些联系,就可以对其运行连通分支算法来创建单独的集群,然后为其分配一个家庭ID。

接着就可以使用这些家庭ID根据家庭需求提供个性化推荐。还可以用它来创建基于家族的分组特性,从而不断完善分类算法。

从金融角度来看:这些家庭ID还能用来捕获欺诈。如果某个账户有过欺诈行为,关联账户也很可能实施欺诈。

应用的无限可能性全凭你的想象定夺。

编码

此处将使用Python中的Networkx模块来创建和分析图表。

先看一个会用到的示例图,其中包含城市和城市之间的距离信息。

大势所趋!数据科学家必知的5种图算法

随机距离示意图

首先,创建联系列表和作为联系权重的距离列表:

  1. 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创建一个图:

  1. g?=?nx.Graph()?
  2. for?edge?in?edgelist:?
  3. g.add_edge(edge[0],edge[1],?weight?=?edge[2])?

现在要从这张图中找出不同的大陆及其城市。

可以这样/(按如下方式)使用连通分支算法:

  1. for?i,?x?in?enumerate(nx.connected_components(g)):?
  2. print("cc"+str(i)+":",x)?
  3. ------------------------------------------------------------?
  4. cc0:?{'Frankfurt',?'Kassel',?'Munchen',?'Numberg',?'Erfurt',?'Stuttgart',?'Karlsruhe',?'Wurzburg',?'Mannheim',?'Augsburg'}?
  5. cc1:?{'Kolkata',?'Bangalore',?'Mumbai',?'Delhi'}?
  6. cc2:?{'ALB',?'NY',?'TX'}?

如上所示,只需要使用联系和顶点就可以在数据中找到不同的组件。这个算法可以在不同的数据上运行来满足以上提到的任何案例。

2. 最短路径

上面已经得到德国城市以及各城市距离的图。

接着,要得出从法兰克福(起始节点)到慕尼黑的最短距离。

解决此问题的算法叫Dijkstra算法。用Dijkstra本人的话来说:

从鹿特丹到格罗宁根的捷径是什么?或者说,从任意一个城市到另一个城市。设计这个最短路径的算法,我只花了20分钟。一天早上,我和年轻的未婚妻在阿姆斯特丹购物。逛累了之后,我们坐在咖啡馆露台上喝了一杯咖啡,我就想能不能做到这一点,然后就设计了最短路径算法。就像之前所说,这是一个20分钟的发明。事实上,这本书在三年后的1959年出版,现在还能读到。它是本很好的书,因为我当时没有用铅笔和纸来设计。后来我发现,不用铅笔和纸设计的好处之一是,设计时必须要化繁为简。最终,我没想到,这个算法竟然成了我的成名作之一。

—— Edsger Dijkstra, 和Philip L. Frana的一段采访对话,美国计算机学会通讯,2001[3]

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章