数据科学一线DSFrontier转载

关于图算法 & 图分析的基础知识概览

本篇博文的主要内容来源于 O’Reilly 系列的《GraphAlgorithms》,对图算法进行了综述介绍,作者为 Amy E. Hodler & Mark Needham。

网址:https://learning.oreilly.com/library/view/graph-algorithms-/9781492060116/

你肯定没有读过这本书,因为这本书的发布日期是2019年5月。本文会覆盖该书的大部分内容,读完这篇,你能够了解图算法的基本概念。关于此书,作为市面上为数不多的面向数据科学应用的图算法书籍,写的比较全面系统和易懂。当然,书在细节上的提高空间还有很多。今天内容很多,坐稳~

目录

图算法 & 图分析

图基础知识

       连通图与非连通图

       未加权图与加权图

       有向图与无向图

       非循环图和循环图

图算法

       路径搜索算法

              DFS & BFS

              最短路径

              最小生成树

              随机游走

       中心性算法

              DegreeCentrality

              ClosenessCentrality

              BetweennessCentrality

              PageRank

       社群发现算法

              MeasuringAlgorithm

              ComponentsAlgorithm

              LabelPropagation Algorithm

              LouvainModularity Algorithm

结论

图算法 & 图分析

图分析使用基于图的方法来分析连接的数据。我们可以:查询图数据,使用基本统计信息,可视化地探索图、展示图,或者将图信息预处理后合并到机器学习任务中。图的查询通常用于局部数据分析,而图计算通常涉及整张图和迭代分析。

图算法是图分析的工具之一。图算法提供了一种最有效的分析连接数据的方法,它们描述了如何处理图以发现一些定性或者定量的结论。图算法基于图论,利用节点之间的关系来推断复杂系统的结构和变化。我们可以使用这些算法来发现隐藏的信息,验证业务假设,并对行为进行预测。

图分析和图算法具有广泛的应用潜力:从防止欺诈,优化呼叫路由,到预测流感的传播。下图是 Martin Grandjean 创建的航线网络图,这幅图清楚地展示了航空运输集群高度连接的结构,帮助我们了解航空运力如何流动。航线网络采用典型的辐射式结构(hub-and-spoke structure),这样的结构在有限运力的前提下,增大了航线的网络的始发-到达对(OD Pair),然而却也带来了系统级联延迟的可能。

图基础知识

我们已经在前一篇博文中介绍了属性图的概念。我们已经知道了节点、关系、属性(Property)、标签等概念。

子图(Subgraph)是一张图的一部分。当我们需要对图中的特定节点,特定关系,或者特定标签或者属性进行特定分析时,子图就会很有用。

路径(Path)是一组节点及他们的关系的集合。以上图为例,“Dan” 开过型号为 “Volvo V70” 的车,这辆车是属于 “Ann” 的。那么节点 “Dan” “Ann” “Car”和关系 “Drives” “Owns” 组成了一个简单的路径。

我们在介绍图算法前,先梳理一下图的不同属性(Attribute)。

连通图与非连通图

连通图(Connected Graphs)指图内任意两个节点间,总能找到一条路径连接它们,否则,为非连通图(Disconnected Graphs)。也就是说,如果图中包含岛(Island),则是非连通图。如果岛内的节点都是连通的,这些岛就被成为一个部件(Component,有时也叫 Cluster)。

有些图算法在非连通图上可能产生无法预见的错误。如果我们发现了未预见的结果,可以首先检查图的结构是否连通。

未加权图与加权图

未加权图(Unweighted Graphs)的节点和边上均没有权重。对于加权图(Weighted Graphs),所加权重可以代表:成本、时间、距离、容量、甚至是指定域的优先级。下图给出了示意图。

基本的图算法可以通过处理权重来代表关系的强度。许多算法通过计算指标,用作后续算法的权重。也有些算法通过更新权重值,来查找累计总数、最小值或最优化结果。

关于加权图的一个典型用途是路径寻找算法。这些算法支持我们手机上的地图应用程序,并计算位置之间最短/最便宜/最快的运输路线。例如,下图使用了两种不同的方法来计算最短路线。

如果没有权重,计算最短路径时,实则在计算关系(Relation,也称 Hop)的数量。那么在上图左边,我们找到 A 和 E 之间的最短距离为 2,经过 D 点。如果像上图右边所示,边被赋予了权重,用以代表节点之间的物理距离(单位:KM)。那么我们可以找到 A 和 E 之间的最短距离是 50 KM,需要经过 C 和 D 两个点。而此时,在未加权图中计算的最短路径 A-D-E 距离为 70 KM,比我们找到的路径 A-C-D-E 距离远。

有向图与无向图

在无向图(Undirected Graphs)中,节点的关系被认为是双向的(bi-directional),例如朋友关系。而在有向图(Directed Graphs)中,节点的关系可以指定方向。边如果指向了一个节点,我们称为 in-link,边如果从一个节点出发,我们称为 out-link。

边的方向加入了更多维度的信息,同样关系的边,却包含不同的方向,则代表了不同的语义信息。如下图所示,有向图绘制了一个简单的同学网络,边的方向代表着 “喜欢”。那么从图中,我们可以知道,同学中 “最受欢迎的” 的人是 “A” 和 “C”。

我们还可以用道路网络帮我们理解为什么需要有向图和无向图。例如,高速公路一般都是双向的,我们使用无向图即可。但是,在城市内部,经常会有单向车道,我们必须使用有向图。

非循环图和循环图

图论中,循环指一些特殊的路径,它们的起点和终点是同一个节点。在非循环图(Acyclic Graph)中,不存在循环路径,相反则为循环图(Cyclic Graphs)。如下图所示,有向图和无向图都可能包含循环,所不同的是,有向图的路径必须遵循边的方向。图中的 Graph 1 是一个典型的 DAG(Directed Acyclic Graph,有向无循环图),并且 DAG 通常有叶子节点(leaf node,也称 dead node)。

Graph 1 和 Graph 2 是无循环的,因为我们在不重复任何一条边的情况下,无法从任何一个点出发,再回到它。Graph 3 中有一个简单的循环 A-D-C-A。而 Graph 4 中,我们可以发现多个循环:B-F-C-D-A-C-B,C-B-F-C 等等。

循环在图中非常常见。有时,我们为了提高处理效率,会将循环图转化为非循环图(通过剪除一些关系)。DAG 在调度、版本控制等问题中十分常见。实际上,我们在数学或者计算机科学中经常遇见的树(Tree)就是一个典型的 DAG,只是对于树来说,只能拥有一个 Parent,而 DAG 没有这个限制。

图算法

我们关注三类核心的图算法:路径搜索(Pathfinding and Search)、中心性计算(Centrality Computation)和社群发现(Community Detection)。

路径搜索算法

图搜索算法(Pathfinding and Search Algorithms)探索一个图,用于一般发现或显式搜索。这些算法通过从图中找到很多路径,但并不期望这些路径是计算最优的(例如最短的,或者拥有最小的权重和)。图搜索算法包括广度优先搜索深度优先搜索,它们是遍历图的基础,并且通常是许多其他类型分析的第一步。

路径搜索(Pathfinding)算法建立在图搜索算法的基础上,并探索节点之间的路径。这些路径从一个节点开始,遍历关系,直到到达目的地。路径搜索算法识别最优路径,用于物流规划,最低成本呼叫或者叫IP路由问题,以及游戏模拟等。

下图是路径搜索类算法的分类:

DFS & BFS

图算法中最基础的两个遍历算法:广度优先搜索(Breadth First Search,简称 BFS)和深度优先搜索(Depth First Search,简称 DFS)。BFS 从选定的节点出发,优先访问所有一度关系的节点之后再继续访问二度关系节点,以此类推。DFS 从选定的节点出发,选择任一邻居之后,尽可能的沿着边遍历下去,知道不能前进之后再回溯。

下面是两张同样的图,分别采用 BFS 和 DFS 进行图的遍历,图上节点的数字标识这遍历顺序。

BFS

DFS

对于我们数据科学的角色来说,我们很少真正需要使用 BFS 和 DFS。这两个图搜索算法更多地作为底层算法支持其他图算法。例如,最短路径问题和 Closeness Centrality (在后文会有介绍)都使用了 BFS 算法;而 DFS 可以用于模拟场景中的可能路径,因为按照 DFS 访问节点的顺序,我们总能在两个节点之间找到相应的路径。感兴趣的话,可以猜一猜,后文介绍的算法是否使用了图搜索算法,并且分别使用了 DFS 还是 BFS。

最短路径

最短路径(Shortest Paths)算法计算给定的两个节点之间最短(最小权重和)的路径。算法能够实时地交互和给出结果,可以给出关系传播的度数(degree),可以快速给出两点之间的最短距离,可以计算两点之间成本最低的路线等等。例如:

  • 导航:谷歌、百度、高德地图均提供了导航功能,它们就使用了最短路径算法(或者非常接近的变种);

  • 社交网络关系:当我们在 LinkedIn、人人(暴露年龄了)等社交平台上查看某人的简介时,平台会展示你们之间有多少共同好友,并列出你们之间的关系。

最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点,也就是 “最临近的” 节点,然后比较 起点到第二临近的节点的权重 与 最临近节点的下一个最临近节点的累计权重和 从而决定下一步该如何行走。可以想象,算法记录的累计权重和 如同地理的 “等高线” 一样,在图上以 “波” 的形式传播,直到到达目的地节点。

最短路径算法有两个常用的变种:A (可以念作 A Star)algorithm和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息,优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果,同时给出了最好的 K 条路径。

所有节点对最短路径(All Pairs Shortest Path)也是一个常用的最短路径算法,计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法,All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息,并且这些信息在计算中可以被重用。

本文不打算再深入了,下图是从A节点开始的计算过程,看懂这张图,你就明白了。

All Pairs Shortest Path 算法通常用于,当最短路径受限或者变成了非最优时,如何寻找替代线路。其实算法非常常用:

  • 优化城市设施的位置和货物的分配:例如确定运输网格中不同路段上预期的交通负荷,例如快递线路设计,从而保证运输对突发事件的应对;

  • 作为数据中心设计算法的一部分:查找具有最大带宽和最小延迟的网络。

最小生成树

最小生成树(Minimum Spanning Tree)算法从一个给定的节点开始,查找其所有可到达的节点,以及将节点与最小可能权重连接在一起,行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点,避免了循环。

最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似,所不同的是, Prim 算法每次寻找最小权重访问到下一个节点,而不是累计权重和。并且,Prim 算法允许边的权重为负。

上图是最小生成树算法的步骤分解,算法最终用最小的权重将图进行了遍历,并且在遍历的过程中,不产生环。

算法可以用于优化连接系统(如水管和电路设计)的路径。它还用于近似一些计算时间未知的问题,如旅行商问题。虽然该算法不一定总能找到绝对最优解,但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如:

  • 旅行计划:尽可能降低探索一个国家的旅行成本;

  • 追踪流感传播的历史:有人使用最小生成树模型对丙型肝炎病毒感染的医院暴发进行分子流行病学调查

随机游走

随机游走(Random Walk)算法从图上获得一条随机的路径。随机游走算法从一个节点开始,随机沿着一条边正向或者反向寻找到它的邻居,以此类推,直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛,他可能知道自己大致要去哪儿,但是路径可能极其“迂回”,毕竟,他也无法控制自己~

随机游走算法一般用于随机生成一组相关的节点数据,作为后续数据处理或者其他算法使用。例如:

  • 作为 node2vec 和 graph2vec 算法的一部分,这些算法可以用于节点向量的生成,从而作为后续深度学习模型的输入;这一点对于了解 NLP (自然语言处理)的朋友来说并不难理解,词是句子的一部分,我们可以通过词的组合(语料)来训练词向量。那么,我们同样可以通过节点的组合(Random Walk)来训练节点向量。这些向量可以表征词或者节点的含义,并且能够做数值计算。这一块的应用很有意思,我们会找机会来详细介绍;

  • 作为 Walktrap 和 Infomap 算法的一部分,用于社群发现。如果随机游走总是返回同一组节点,表明这些节点可能在同一个社群;

  • 其他机器学习模型的一部分,用于随机产生相关联的节点数据。

中心性算法

中心性算法(Centrality Algorithms)用于识别图中特定节点的角色及其对网络的影响。中心性算法能够帮助我们识别最重要的节点,帮助我们了解组动态,例如可信度、可访问性、事物传播的速度以及组与组之间的连接。尽管这些算法中有许多是为社会网络分析而发明的,但它们已经在许多行业和领域中得到了应用。

下图罗列了我们所有需要了解的中心性算法指标。

Degree Centrality

Degree Centrality (度中心性,以度作为标准的中心性指标)可能是整篇博文最简单的 “算法” 了。Degree 统计了一个节点直接相连的边的数量,包括出度和入度。Degree 可以简单理解为一个节点的访问机会的大小。例如,在一个社交网络中,一个拥有更多 degree 的人(节点)更容易与人发生直接接触,也更容易获得流感。

一个网络的平均度(average degree),是边的数量除以节点的数量。当然,平均度很容易被一些具有极大度的节点 “带跑偏” (skewed)。所以,度的分布(degree distribution)可能是表征网络特征的更好指标。

如果你希望通过出度入度来评价节点的中心性,就可以使用 degree centrality。度中心性在关注直接连通时具有很好的效果。应用场景例如,区分在线拍卖的合法用户和欺诈者,欺诈者由于尝尝人为太高拍卖价格,拥有更高的加权中心性(weighted centrality)。

Closeness Centrality

Closeness Centrality(紧密性中心性)是一种检测能够通过子图有效传播信息的节点的方法。紧密性中心性计量一个节点到所有其他节点的紧密性(距离的倒数),一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离最小值。

对于一个节点来说,紧密性中心性是节点到所有其他节点的最小距离和的倒数:

其中 u 是我们要计算紧密性中心性的节点,n 是网络中总的节点数,d(u,v) 代表节点 u 与节点 v 的最短路径距离。更常用的公式是归一化之后的中心性,即计算节点到其他节点的平均距离的倒数,你知道如何修改上面的公式吗?对了,将分子的 1 变成 n-1 即可。

理解公式我们就会发现,如果图是一个非连通图,那么我们将无法计算紧密性中心性。那么针对非连通图,调和中心性(Harmonic Centrality)被提了出来(当然它也有归一化的版本,你猜这次n-1应该加在哪里?):

Wasserman and Faust 提出过另一种计算紧密性中心性的公式,专门用于包含多个子图并且子图间不相连接的非连通图:

其中,N 是图中总的节点数量,n 是一个部件(component)中的节点数量。

当我们希望关注网络中传播信息最快的节点,我们就可以使用紧密性中心性。

Betweenness Centrality

中介中心性(Betweenness Centrality)是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于寻找连接图的两个部分的桥梁节点。因为很多时候,一个系统最重要的 “齿轮” 不是那些状态最好的,而是一些看似不起眼的 “媒介”,它们掌握着资源或者信息的流动性。

中间中心性算法首先计算连接图中每对节点之间的最短(最小权重和)路径。每个节点都会根据这些通过节点的最短路径的数量得到一个分数。节点所在的路径越短,其得分越高。计算公式:

其中,p 是节点 s 与 t 之间最短路径的数量,p(u) 是其中经过节点 u 的数量。下图给出了对于节点 D 的计算过程:

当然,在一张大图上计算中介中心性是十分昂贵的。所以我们需要更快的,成本更小的,并且精度大致相同的算法来计算,例如 Randomized-Approximate Brandes。我们不会对这个算法继续深入,感兴趣的话,可以去了解一下,算法如何通过随机(Random)和度的筛选(Degree)达到近似的效果。

中介中心性在现实的网络中有广泛的应用,我们使用它来发现瓶颈、控制点和漏洞。例如,识别不同组织的影响者,他们往往是各个组织的媒介,例如寻找电网的关键点,提高整体鲁棒性。

PageRank

在所有的中心性算法中,PageRank 是最著名的一个。它测量节点传递影响的能力。PageRank 不但节点的直接影响,也考虑 “邻居” 的影响力。例如,一个节点拥有一个有影响力的 “邻居”,可能比拥有很多不太有影响力的 “邻居” 更有影响力。PageRank 统计到节点的传入关系的数量和质量,从而决定该节点的重要性。

PageRank 算法以谷歌联合创始人拉里·佩奇的名字命名,他创建了这个算法来对谷歌搜索结果中的网站进行排名。不同的网页之间相互引用,网页作为节点,引用关系作为边,就可以组成一个网络。被更多网页引用的网页,应该拥有更高的权重;被更高权重引用的网页,也应该拥有更高权重。原始公式:

其中,u 是我们想要计算 PageRank 的网页,T1 到 Tn 是引用的网页。d 被称为阻尼系数(damping factor),代表一个用户继续点击网页的概率,一般被设置为 0.85,范围 0~1。C(T) 是节点 T 的出度。

从理解上来说,PageRank 算法假设一个用户在访问网页时,用户可能随机输入一个网址,也可能通过一些网页的链接访问到别的网页。那么阻尼系数代表用户对当前网页感到无聊,随机选择一个链接访问到新的网页的概率。那么 PageRank 的数值代表这个网页通过其他网页链接过来(入度,in-degree)的可能性。那你能如何解释 PageRank 方程中的 1-d 呢?实际,1-d 代表不通过链接访问,而是随机输入网址访问到网页的概率。

PageRank 算法采用迭代方式计算,直到结果收敛或者达到迭代上限。每次迭代都会分两步更新节点权重和边的权重,详细如下图:

当然,上图的计算并没有考虑阻尼系数,那为什么一定要阻尼系数呢?除了我们定义的链接访问概率,有没有别的意义呢?从上图的过程中,我们可能会发现一个问题,如果一个节点(或者一组节点),只有边进入,却没有边出去,会怎么样呢?按照上图的迭代,节点会不断抢占 PageRank 分数。这个现象被称为 Rank Sink,如下图:

解决 Rank Sink 的方法有两个。第一个,假设这些节点有隐形的边连向了所有的节点,遍历这些隐形的边的过程称为 teleportation。第二个,使用阻尼系数,如果我们设置 d 等于 0.85,我们仍然有 0.15 的概率从这些节点再跳跃出去。

尽管阻尼系数的建议值为 0.85,我们仍然可以根据实际需要进行修改。调低阻尼系数,意味着访问网页时,更不可能不断点击链接访问下去,而是更多地随机访问别的网页。那么一个网页的 PageRank 分数会更多地分给他的直接下游网页,而不是下游的下游网页。

PageRank 算法已经不仅限于网页排名。例如:

  • 寻找最重要的基因:我们要寻找的基因可能不是与生物功能联系最多的基因,而是与最重要功能有紧密联系的基因;

  • who to follow service at twitter:Twitter使用个性化的 PageRank 算法(Personalized PageRank,简称 PPR)向用户推荐他们可能希望关注的其他帐户。该算法通过兴趣和其他的关系连接,为用户展示感兴趣的其他用户;

  • 交通流量预测:使用 PageRank 算法计算人们在每条街道上停车或结束行程的可能性;

  • 反欺诈:医疗或者保险行业存在异常或者欺诈行为,PageRank 可以作为后续机器学习算法的输入。

社群发现算法

社群的形成在各种类型的网络中都很常见。识别社群对于评估群体行为或突发事件至关重要。对于一个社群来说,内部节点与内部节点的关系(边)比社群外部节点的关系更多。识别这些社群可以揭示节点的分群,找到孤立的社群,发现整体网络结构关系。社群发现算法(Community Detection Algorithms)有助于发现社群中群体行为或者偏好,寻找嵌套关系,或者成为其他分析的前序步骤。社群发现算法也常用于网络可视化。

下图是社群发现算法的分类。

Measuring Algorithm

三角计数(Triangle Count)和聚类系数(Clustering Coefficient)经常被一起使用。三角计数计算图中由节点组成的三角形的数量,要求任意两个节点间有边(关系)连接。聚类系数算法的目标是测量一个组的聚类紧密程度。该算法计算网络中三角形的数量,与可能的关系的比率。聚类系数为 1 表示这个组内任意两个节点之间有边相连。

有两种聚类系数:局部聚类系数(Local Clustering Coefficient)和全局聚类系数(Global Clustering Coefficient)。

局部聚类系数计算一个节点的邻居之间的紧密程度,计算时需要三角计数。计算公式:

其中,u 代表我们需要计算聚类系数的节点,R(u) 代表经过节点 u 和它的邻居的三角形个数,k(u) 代表节点 u的度。下图是三三角计数聚类系数计算示意图:

全局聚类系数是局部聚类系数的归一化求和。

当需要计算一个组的稳定性或者聚类系数时,我们可以使用三角计数。三角计数在社交网络分析中有广泛的应用,通航被用来检测社区。聚类系数可以快速评估特定组或整个网络的内聚性。这些算法可以共同用于特定网络结构的寻找。例如,探索网页的主题结构,基于网页之间的相互联系,检测拥有共同主题的 “网页社群”。

Components Algorithm

强关联部件(Strongly Connected Components,简称 SCC)算法寻找有向图内的一组一组节点,每组节点可以通过关系 互相 访问。在 “Community Detection Algorithms” 的图中,我们可以发现,每组节点内部不需要直接相连,只要通过路径访问即可。

关联部件(Connected Components)算法,不同于 SCC,组内的节点对只需通过一个方向访问即可。

关联类算法作为图分析的早期算法,用以了解图的结构,或确定可能需要独立调查的紧密集群十分有效。对于推荐引擎等应用程序,也可以用来描述组中的类似行为等等。许多时候,算法被用于查找集群并将其折叠成单个节点,以便进一步进行集群间分析。对于我们来说,先运行以下关联类算法查看图是否连通,是一个很好的习惯。

Label Propagation Algorithm

标签传播算法(Label Propagation Algorithm,简称 LPA)是一个在图中快速发现社群的算法。在 LPA 算法中,节点的标签完全由它的直接邻居决定。算法非常适合于半监督学习,你可以使用已有标签的节点来种子化传播进程。

LPA 是一个较新的算法,由 Raghavan 等人于 2007 年提出。我们可以很形象地理解算法的传播过程,当标签在紧密联系的区域,传播非常快,但到了稀疏连接的区域,传播速度就会下降。当出现一个节点属于多个社群时,算法会使用该节点邻居的标签与权重,决定最终的标签。传播结束后,拥有同样标签的节点被视为在同一群组中。

下图展示了算法的两个变种:Push 和 Pull。其中 Pull 算法更为典型,并且可以很好地并行计算:

我们不再继续深入,看完上图,你应该已经理解了算法的大概过程。其实,做过图像处理的人很容易明白,所谓的标签传播算法,不过是图像分割算法的变种,Push 算法是区域生长法(Region Growing)的简化版,而 Pull 更像是分割和合并(divide-and-merge,也有人称 split-merge)算法。确实,图像(image)的像素和图(graph)的节点是十分类似的。

Louvain Modularity Algorithm

Louvain Modularity 算法在给节点分配社群是,会比较社群的密度,而不仅仅是比较节点与社群的紧密程度。算法通过查看节点与社群内关系的密度与平均关系密度的比较,来量化地决定一个节点是否属于社群。算法不但可以发现社群,更可以给出不同尺度不同规模的社群层次,对于理解不同粒度界别的网络结构有极大的帮助。

算法在 2008 年被提出以后,迅速成为了最快的模块化算法之一。算法的细节很多,我们无法一一覆盖,下图给出了一个粗略的步骤,帮助我们理解算法如何能够多尺度地构建社群:

Louvain Modularity 算法非常适合庞大网络的社群发现,算法采用启发式方式从而能够克服传统 Modularity 类算法的局限。算法应用:

  • 检测网络攻击:该算可以应用于大规模网络安全领域中的快速社群发现。一旦这些社群被发现,就可以用来预防网络攻击;

  • 主题建模:从 Twitter 和 YouTube 等在线社交平台中提取主题,基于文档中共同出现的术语,作为主题建模过程的一部分。

结论

本文更像是一篇综述,算法很干,我们会在后续继续分享图分析相关内容,敬请期待。

入门图算法
12
相关数据
拉里·佩奇人物

美国计算机科学家和互联网企业家,1998年与谢尔盖·布林创造了Google,现为Alphabet公司CEO。他是Google最著名的搜索排名算法发明者,2004年获得马可尼奖。

深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

图像分割技术

图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类:基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。从数学角度来看,图像分割是将数字图像划分成互不相交的区域的过程。图像分割的过程也是一个标记过程,即把属于同一区域的像索赋予相同的编号。

数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

广度优先搜索技术

广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。

半监督学习技术

半监督学习属于无监督学习(没有任何标记的训练数据)和监督学习(完全标记的训练数据)之间。许多机器学习研究人员发现,将未标记数据与少量标记数据结合使用可以显着提高学习准确性。对于学习问题的标记数据的获取通常需要熟练的人类代理(例如转录音频片段)或物理实验(例如,确定蛋白质的3D结构或确定在特定位置处是否存在油)。因此与标签处理相关的成本可能使得完全标注的训练集不可行,而获取未标记的数据相对便宜。在这种情况下,半监督学习可能具有很大的实用价值。半监督学习对机器学习也是理论上的兴趣,也是人类学习的典范。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

调度技术

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。 进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态,允许多位用户有效地同时共享系统资源,或达到指定的服务质量。 see planning for more details

最小生成树技术

最小生成树是一副连通加权无向图中一棵权值最小的生成树。一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树。以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低。简单点说有几个城市你要设计一个路线,这个路线能走完所有的这几个城市,而且路程最短,这个路线就会是最小生成树。

深度优先搜索技术

深度优先搜索算法是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

数据科学技术

数据科学,又称资料科学,是一门利用数据学习知识的学科,其目标是通过从数据中提取出有价值的部分来生产数据产品。它结合了诸多领域中的理论和技术,包括应用数学、统计、模式识别、机器学习、数据可视化、数据仓库以及高性能计算。数据科学通过运用各种相关的数据来帮助非专业人士理解问题。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

社会网络分析技术

社会网络分析方法是由社会学家根据数学方法﹑图论等发展起来的定量分析方法,近年来,该方法在职业流动、城市化对个体幸福的影响、世界政治和经济体系、国际贸易等领域广泛应用,并发挥了重要作用。社会网络分析是社会学领域比较成熟的分析方法,社会学家们利用它可以比较得心应手地来解释一些社会学问题。许多学科的专家如经济学、管理学等领域的学者们在新经济时代——知识经济时代,面临许多挑战时,开始考虑借鉴其他学科的研究方法,社会网络分析就是其中的一种。

图搜索技术

在计算机科学中,图遍历(也称为图搜索)是指在图中访问(检查/或更新)每个顶点的过程。这样的遍历是按访问顶点的顺序进行分类的。比如,树遍历就是图遍历的一个特例。 与树遍历不同,图遍历可能需要多次访问某些顶点,因为在转换到一个已经被探索的顶点之前,它并不一定是已知的。随着图形变得越来越密集,这种冗余变得更加普遍,导致计算时间增加;随着图形变得越来越稀疏,相反的情况也成立。 因此,通常需要记住哪些顶点已经被算法探索过了,这样就可以尽可能少地重新访问顶点(或者在最坏的情况下,防止遍历无限延续)。这可以通过将图中的每个顶点与在遍历期间的“颜色”或“访问”状态相关联来完成,然后在算法访问每个顶点时检查和更新。如果顶点已经被访问过,它就被忽略了,路径就不再被继续了;否则,算法会检查/更新顶点,并继续它当前的路径。

图论技术

图论是以“图”为研究对象的一个数学分支,是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构,由“顶点”(又称“节点”或“点”)以及连接这些顶点的“边”(又称“弧”或“线”)组成。值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

图像处理技术

图像处理是指对图像进行分析、加工和处理,使其满足视觉、心理或其他要求的技术。 图像处理是信号处理在图像领域上的一个应用。 目前大多数的图像均是以数字形式存储,因而图像处理很多情况下指数字图像处理。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

百度机构

百度(纳斯达克:BIDU),全球最大的中文搜索引擎、最大的中文网站。1999年底,身在美国硅谷的李彦宏看到了中国互联网及中文搜索引擎服务的巨大发展潜力,抱着技术改变世界的梦想,他毅然辞掉硅谷的高薪工作,携搜索引擎专利技术,于 2000年1月1日在中关村创建了百度公司。 “百度”二字,来自于八百年前南宋词人辛弃疾的一句词:众里寻他千百度。这句话描述了词人对理想的执着追求。 百度拥有数万名研发工程师,这是中国乃至全球最为优秀的技术团队。这支队伍掌握着世界上最为先进的搜索引擎技术,使百度成为中国掌握世界尖端科学核心技术的中国高科技企业,也使中国成为美国、俄罗斯、和韩国之外,全球仅有的4个拥有搜索引擎核心技术的国家之一。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

暂无评论
暂无评论~