周佳玉、丁慧、叶一、小鱼、钱天培编译

手把手:一张图看清编程语言发展史,你也能用Python画出来!

我们可以在这里看到从过去到现在的250多种编程语言之间的“设计影响”的关系,下面是该演示的截图:

接下来,就让我们一起来学做这个关系网络图吧!

在当今的超连接世界,网络在现代生活中无处不在。举个栗子,文摘菌的周末这样开启——通过北京的交通网络进城,然后去最喜欢的咖啡店的一家分店,并将笔记本连上他们的Wi-Fi。接下来,登录各种常用的社交网站。

众所周知,在过去几十年来最有影响力的公司中,有一部分是因为网络的力量而获得成功。

Facebook、Twitter、Instagram、LinkedIn以及一些其他的社交媒体平台都依赖社交网络的小世界特性。这使他们能有效地将用户彼此(以及和广告商)之间连接起来。

谷歌目前的成功主要归因于他们早期在搜索引擎市场上的主导地位——部分原因是他们有能力通过他们的Page Rank网络算法来返回相关的结果。

亚马逊的高效配送网络使他们能够在一些主要城市提供当天发货。

网络算法在人工智能和机器学习等领域也是非常重要的。神经网络领域的研究非常热门。计算机视觉中许多必不可少的特征检测算法,在很大程度上也是依赖于使用网络来对图像的不同部分进行建模。

网络模型也可以解释大量的科学现象,包括有量子力学、生化途径以及生态和社会经济系统等。

那么,鉴于它们不可否认的重要性,我们应该如何更好地理解网络及其属性呢?

网络的数学研究被称为“图论”,是数学中较易理解的分支之一。 本文会介绍简单的网络知识,即便你没有相关背景知识也能轻松学会。

此外,我们将使用Python 3.x和一款非常棒的开源软件Gephi,通过关系网络将过去和现在的一系列编程语言的网络可视化联系起来。

首先,究竟什么是网络呢?

其实上面文摘菌举的栗子已经给了一些线索。交通网络由目的和路径的连接组成。社交网络通过个人和个人之间的关系进行连接。Google的搜索引擎算法通过查看有哪些页面链接到其他页面,来评估不同网页的“顺序”。

更一般地说,网络是可以用节点和边描述的任何系统,或者通俗来讲,就是我们所说的“点和线”。

边连接节点(语言)的例子(该网络表示了编程语言相互影响的关系)

有些系统以这种方式建立网络比较容易。社交网络也许是最明显的例子。计算机文件系统则是另一种方式——文件夹和文件通过其“父”和“子”关系创建连接。

但是,网络的真正威力其实在于,许多系统都可以从网络的角度来建模,即使这起初并不明显。

代表网络

我们应该如何将点和线的图片转换成我们可以压缩的数字信号呢?

其中有一个解决方案是绘制一个邻接矩阵来表示我们的网络。

如果你不熟悉矩阵这个概念,这听起来可能有点吓人,但不要害怕。 把它们想象成可以一次执行许多计算的数字网格就好。下面是一个简单的例子:

在这个矩阵中,每个行和列的交集都是0或1,这取决于各个语言是否被链接。你也可以根据上面的插图观察到!

对于要解决的大多数问题而言,矩阵是以数学方式表示网络的好方法。然而从计算的角度来看,它有时可能会有点麻烦。

例如,即使节点数量相对较少(比如说有1000个),矩阵中的元素数目也会大得多(例如,1000^2 = 1,000,000)。

许多现实世界的系统会产生稀疏网络,在这些网络中,大多数节点只能连接其他所有节点中的一小部分。

如果我们将计算机内存中1000个节点的稀疏网络表示为邻接矩阵,那么我们将在RAM中存储1,000,000个字节的数据。大多数将会是零。这里有一个更为有效的方法可以解决这个问题。

这种方法是使用边列表来代替邻接矩阵。这些正是他们所说的,它们只是一个节点对相互链接的列表。

表示网络的另一种手段是邻接表,它列出了每个节点后面与它进行链接的节点。例如:

收集数据,建立连接

任何网络模型以及可视化的表现都取决于构建网络本身所用的数据质量好坏。除了确保数据是准确和完整的同时,我们也需要一种推断节点之间边的合理方法。

这是相当关键的一步,随后对网络进行的任何分析和推断都取决于“关联标准”的合理性。

例如,在社交网络分析中,你可能会根据人们是否在社交媒体上相互关联来创建人与人之间的联系。在分子生物学中,你可能会基于基因的共同表达建立连接。

通常,我们还可以给边分配权重,从而体现关系的“强度”。

例如,对于网上零售的情况,可以根据产品被同时购买的频率来计算权重。用高权重的边连接经常被同时购买的产品,用低权重的边连接偶尔被同时购买的产品。和偶尔被同时购买的产品相比,那些不会被同时购买的产品根本就不会被网络连接。

正如你想的那样,将节点彼此连接的方法有可能很复杂。

但是对于本教程,我们将使用更简单的方式连接编程语言。我们要依靠维基百科。

维基百科所取得的的成功证明了它的可靠性。文章写作的开源合作方法也应该保证一定程度的客观性。

而且,它的页面结构相对一致,使其成为试用网页抓取技术的便利场所。

另一个便利工具是覆盖面广泛的、有据可查的维基百科API,这使得信息检索更容易。接下来让我们一起开始吧。

第一步:安装Gephi

Gephi可在Linux、Mac和Windows的环境下进行安装。

对于这个项目,我使用了Lubuntu。如果你使用的是Ubuntu / Debian,那么你可以按照下面的步骤来启动和运行Gephi。如果不是,那么安装过程也不会差太多。

下载最新版本的Gephi到你的系统(在撰写本文时是v.0.9.1)。准备就绪后,你需要提取文件。

你可能需要检查你的Java JRE版本。Gephi需要最新版本。在我刚刚安装的Lubuntu上,我只安装了default-jre,下面的一切将建立在此基础上。

在你准备好进行安装之前还有一步。为了将图表导出到Web,你可以使用Gephi的Sigma.js插件。

从Gephi的菜单栏中选择“工具”选项,然后选择“插件”。

点击“可用插件”标签并选择“SigmaExporter”(我也安装了JSON导出器,因为它是另一个有用的插件)。

点击“安装”按钮,你将完成整个安装过程。安装结束后,你需要重新启动Gephi。

第二步:编写Python脚本

本教程将使用python 3.x以及一些模块来进行简化。使用pip模块安装程序,需运行一下命令:

现在,在一个新的目录中,创建一个名为script.py的文件,并在你最喜欢的代码编辑器/ IDE中打开它。以下是主要逻辑的大纲:

首先,你需要有一个编程语言的列表。

接下来,通过该列表并检索维基百科相关文章的HTML。

从中提取出每种语言所影响的编程语言列表。这是我们连接节点的粗略标准。

同时,我们可以抓取一些关于每种语言的元数据。

最后,将收集的所有数据写入一个.csv文件。

完整的脚本在这里:

(https://gist.github.com/anonymous/2a6c841fe04ebc6d55acc259b4ac4f72)。

导入模块

在script.py中,首先导入一些模块。

准备好后——从创建一个节点的列表开始。这是Wikipedia模块派上用场的地方。它使得访问维基百科API非常容易。

添加下面的代码:

保存并运行上面的脚本,将看到打印出“List of programming languages”维基百科文章中的所有链接。

另外,还需要手动检查自动收集的数据。快速浏览后我们可以发现,除了许多实际的编程语言之外,该脚本还提供了一些额外的链接。

如:可能会看到“List of markup languages”,“Comparison of programming languages”等。

虽然Gephi允许你移除不想包含的节点,但为了节省时间,还是让我们先进行一轮数据清洗。

这些代码定义了要从数据中移除的子字符串列表。运行该脚本时遍历数据,移除所有包含不需要的子字符串的元素。

在Python语言中,完成这些只需要一行代码!

其他辅助函数

现在我们可以开始从wikipedia抓取数据并建立一个边列表(并收集所有元数据)。为了更简便,让我们首先定义一些函数。

抓取HTML

第一个函数使用BeautifulSoup模块来获取每种语言的Wikipedia页面的HTML。

这个函数使用urllib.request模块来获取“https://en.wikipedia.org/wiki/”+“编程语言”页面的HTML。

然后传给BeautifulSoup,它将读取HTML并解析为一个可以用来搜索信息的对象。

接下来,使用find_all()方法抓取感兴趣的HTML元素。

下面,是每种编程语言文章顶部的汇总表。该如何识别呢?

最简单的方法是访问其中一个编程语言页面。在这里,可以简单地使用浏览器的开发工具来检查感兴趣的元素。汇总表有HTML标记<table>和CSS类“infobox”和“vevent”,因此可以使用这些来标识HTML中的表格。

参数指定它:

find_all()返回符合标准的所有元素列表。为了指定感兴趣的元素,需要添加索引[0]。如果函数执行成功,则返回table对象,否则,返回None。

在使用了自动数据收集程序的情况下,全面的异常处理是非常重要的。如果没有,那么在最好的情况下如果脚本崩溃了,数据抓取程序需要重新开始执行。

在最坏的情况下,你获得数据集将包含不一致性和错误,这将为你后续的工作买下隐患。

检索元数据

下一个函数使用table对象来查找一些元数据。下面给出在表格中搜索语言第一次出现的年份的代码。

这个简短的函数以table对象作为参数,并调用BeautifulSoup的get_text()函数生成一个字符串。

下一步是创建一个名为year的子字符串。该字符串存储了在“appear”这个词首次出现之后的30个字符。这个字符串应该包含语言第一次出现的年份。

为了仅提取年份,使用正则表达式(通过re模块)来匹配任何以1到3之间的数字开头、并紧邻三个数字的字符串。

如果执行成功,函数将返回一个整数的year。否则,我们会得到“Could not determine”。你可能还想进一步挖掘元数据,例如范例,设计者或打字规律。

收集链接

我们还需要一个函数–该函数读入给定语言的table对象,输出一个包含其他编程语言的列表。

仔细观察上面代码中嵌套部分,到底是怎么回事呢?

这个函数利用了table对象具有结构一致性的事实。表中的信息存储在行中(相关的HTML标签是<tr>)。其中一行包含文字“\ nInfluenced \ n”。函数的第一部分查找这是哪一行。

一旦找到这一行,就可以确定下一行包含了被当前行影响的每种编程语言的链接。使用find_all(“a”)便可查找这些链接 - 其中参数“a”对应于HTML标签<a>。

对于每个链接j,将其[“title”]属性添加到名为out的列表。对[“title”]属性感兴趣的原因是因为它将完全匹配存储在节点中的语言名称。

例如,Java作为“Java(编程语言)”存储在节点中,因此需要在整个数据集中使用这个确切的名称。

如果执行成功,getLinks()将返回一组编程语言。该函数的其余部分进行了异常处理,以防程序在某一阶段出现问题。

收集数据

最后,在一切准备就绪后执行脚本,收集数据并将其存储在两个列表对象中。

现在编写一个循环,将先前定义的函数应用于nodes中的每个词条,并将输出存储在edgeList和meta中。

该函数使用节点中的每种语言,并尝试从维基百科页面检索汇总表。

然后,该函数将检索表中列出的与目标语言所关联的全部语言。

对于同时出现在节点列表中的每种语言,将一个元素以[“source,target”]的形式添加到edgeList。通过这种方式,建立一个边的列表传给Gephi。

出于调试的目的,打印添加到edgeList的每个元素——这样做仅仅为了确保一切都工作。如果想要更彻底地调试,也可以添加打印语句到except语句中。

接下来,获取语言的名称和年份,并将其添加到元列表中。

写进CSV文件

一旦循环运行,最后一步是将edgeList和meta的内容写入到CSV文件。通过使用前面导入的csv模块,完成上一步骤就容易多了。


完成了!保存脚本,并从终端运行:

$ python3 script.py

当构建边列表时,你可以看到脚本输出了source-target对。确保网络连接的稳定性后,你就可以坐等结果了,此时脚本将发挥其魔力。

第三步:用Gephi建立图形

希望你已经安装并运行了Gephi。现在你可以创建一个新项目,并使用你收集的数据来构建有向图。有向图将显示不同的编程语言是如何相互影响的!

首先在Gephi中创建一个新项目,然后切换到“数据实验室”窗口。Gephi中提供了一个扩展式的接口来处理数据。首先要导入列表。

点击“导入电子表格”。

选择由Python脚本生成的edge_list.csv文件。确保Gephi中使用逗号作为分隔符。

从列表类型中选择“边列表”

点击“下一步”,导入源和目标列作为字符串,并检查。

用一个节点列表来更新数据实验室。现在,导入 metadata.csv文件。这一次,从列表类型中选择“节点列表”。

切换到“Preview”选项卡,查看网络的外观。

这时的图形看起来颜色十分单一,而且杂乱无章,就像一盘意大利面。所以我们接下来要进行图像美化。

图像美化

我们可以通过各种方式来演示图像,也可以尽情发挥自己的创意。另外,关于网络可视化还要考虑以下三件事情:

节点定位:生成网络布局模式的算法有很多,比较流行的是fruchterman - reingold算法,而且Gephi支持该算法。

节点大小:图中节点的大小可以用来表示一些有趣的属性。通常,这是一个中心性度量。度量中心性的方法有很多,但它们都反映了给定节点的“重要性”,即它与网络的其他部分关联的紧密程度。

节点着色:我们还可以使用颜色来显示节点的某些属性。通常,颜色用来表示群落结构,广泛定义为“与图的其余部分相比关联更紧密的一组节点”。在社交网络中,群落结构可以揭示个人的友情、家庭或专业团体之间的关联。有几种算法可以检测群落结构,Gephi自带的检测算法是Louvain方法。

要执行上述步骤,还需要计算一些统计数据。切换到“Overview”窗口。在这里你可以看到右侧的一个面板。它包含一个“Statistics”选项卡。打开它,你将看到一系列选项。

Gephi具有许多内置的统计功能。对于每种功能,点击“Run”将生成一个报告,该报告揭示了关于网络的一些洞见。

如果要修改网络的外观,我们可以转向左边的面板。

在“Layout”选项卡中,可以选择要使用的布局算法。点击“运行”,实时观看图表的变化!看看你认为哪种布局算法效果最好。

在Layout选项卡之上是“Appearance”选项卡。在这里,你可以为节点和各条边的颜色、大小和标签进行设置,也可以根据数据的属性来配置(包括你要计算的数据)。

一个建议:

根据模块化属性将节点着色。着色的根据是节点的群落成员关系。

根据节点的平均程度来确定节点的大小。关联紧密的节点会比关联稀疏的节点显得大。

不过,也可以尝试设计一个最喜欢的布局。一旦对图形外观感到满意,就可以进入最后一个步骤——将图形导出至网页!

第四步:使用Sigma.js插件

既然已经构建了一个可以在Gephi中查看的网络可视化,接下来可以选择使用屏幕截图,或者以SVG、PDF或PNG格式保存图形。

如果已经安装了Sigma.js插件,也可以把图形导出到HTML,这将会创建一个交互式可视化,不仅可以在线上发布,也可以上传到GitHub,与他人分享。

可从Gephi的菜单栏选择“Export >Sigma.js模板…”。

按要求填写详细信息。确保选择导出项目所在的目录。你也可以更改图形的标题、图例、描述、悬停和许多其他细节。当你准备好了,点击“确定”。

现在,如果你打开导出项目所在的目录,你将看到一个文件夹,其中包含Sigma.js生成的所有文件。

在你最喜欢的浏览器打开index.html文件。哈!你的网络!如果你知道一些CSS和JavaScript,可以载入各种生成的文件到你的网络中,以便按照你的意愿调整输出的网络。

脑洞开一开,网络画起来

许多系统可以作为网络进行建模和可视化。图论是数学的一个分支,它提供了帮助理解网络结构和属性的工具。

使用Python从Wikipedia获取数据,构建编程语言影响图。关联标准是一种给定的语言是否能被列为对设计另一种语言的影响。

Gephi和Sigma.js是分析和可视化网络的开源工具。它们可以让你以图像、PDF或Web格式导出网络。

模仿本文的方法,你还可以为很多其他的关系建模并做出可视化。脑洞开一开,网络画起来。

入门
1
相关数据
神经网络技术
Neural Network

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

计算机视觉技术
Computer Vision

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

图论技术
Graph theory

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

逻辑技术
Logic

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

信息检索技术
Information Retrieval

信息检索(IR)是基于用于查询检索信息的任务。流行的信息检索模型包括布尔模型、向量空间模型、概率模型和语言模型。信息检索最典型和最常见的应用是搜索引擎。

机器学习技术
Machine Learning

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

参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

权重技术
Weight

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

返回顶部