如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的,常见的机器学习算法:
为了详细的理解这些原理,曾经看过西瓜书,统计学习方法,机器学习实战等书,也听过一些机器学习的课程,但总感觉话语里比较深奥,读起来没有耐心,并且理论到处有,而实战最重要, 所以在这里想用最浅显易懂的语言写一个白话机器学习算法理论+实战系列。
个人认为,理解算法背后的idea和使用,要比看懂它的数学推导更加重要。idea会让你有一个直观的感受,从而明白算法的合理性,数学推导只是将这种合理性用更加严谨的语言表达出来而已,打个比方,一个梨很甜,用数学的语言可以表述为糖分含量90%,但只有亲自咬一口,你才能真正感觉到这个梨有多甜,也才能真正理解数学上的90%的糖分究竟是怎么样的。如果算法是个梨,本文的首要目的就是先带领大家咬一口。另外还有下面几个目的:
学习算法的过程,获得的不应该只有算法理论,还应该有乐趣和解决实际问题的能力!
今天是白话机器学习算法理论+实战的第三篇,PageRank算法,通过今天的学习,快速Get到PageRank的原理,并最后运用PageRank算法实现一个项目:分析希拉里邮件里面的人物关系,在这能看到谁和希拉里交往最为活跃。
大纲如下:
Ok, let's go !
提到PageRank,好多人可能一上来一脸懵逼,不知道这是个什么东西,但是提到一个词?想必大家一定不陌生,那就是从众心理。大家一般都有从众心理,不信的话可以看看下面的场景:
★比如,当你某一家饭店,或者理发店,或者小吃店里面的顾客非常多,每天爆满的时候,心理一定会想,这家店想必不错,要不然不可能这么多人,我也进去试试。 或者,在淘宝上买某个商品的时候,肯定是喜欢挑人多的店铺,好评量高的店铺买的放心等等吧。 所以当我们在生活中遇到艰难选择的时候,往往喜欢看看别人是怎么做的,一般都会选大部分人的选择。这其实就是一种从众。 ”
这些店铺也好,选择也罢,其实都是通过很多人的投票进而提高了自己的影响力,再比如说,微博上如何去衡量一个人的影响力呢? 我们习惯看他的粉丝,如果他的粉丝多,并且里面都是一些大V,明星的话,很可能这个人的影响力会比较强。 再比如说,职场上如何衡量一个人的影响力呢?我们习惯看与他交往的人物, 如果和他交往的都是像马云,王健林,马化腾这样的人物,那么这个人的影响力估计也小不了。再比如说,如何判断一篇论文好?我们习惯看他的引用次数,或者影响因子,高的论文就比较好等等。
但是你只知道吗?其实我们的这种方式就在用PageRank算法的思想了,只不过我们没有发觉罢了,所谓的算法来源于生活,并服务于生活就是这个道理。
好了,通过上面的案例,相信已经对PageRank这个词有点感觉了吧。那么趁热打铁,说说它的来源吧。
想必大家上网的时候,都用过搜索引擎,现在已经非常好用了,基本上输入关键词,都能找到匹配的内容,质量还不错。但在 1998 年之前,搜索引擎的体验并不好。早期的搜索引擎,会遇到下面的两类问题:
基于这些缺陷,当时 Google 的创始人拉里·佩奇提出了 PageRank 算法,目的就是要找到优质的网页,这样 Google 的排序结果不仅能找到用户想要的内容,而且还会从众多网页中筛选出权重高的呈现给用户。其灵感就是论文影响力因子的启发。
假设一共有 4 个网页 A、B、C、D。它们之间的链接信息如图所示:
首先先知道两个概念:
★出链指的是链接出去的链接。入链指的是链接进来的链接。比如图中 A 有 2 个入链,3 个出链。 ”
那么我们如何计算一个网页的影响力或者重要程度呢?
★简单来说,一个网页的影响力 = 所有入链集合的页面的加权影响力之和,用公式表示为:
u 为待评估的页面,Bu 为页面 u 的入链集合。针对入链集合中的任意页面 v,它能给 u 带来的影响力是其自身的影响力 PR(v) 除以 v 页面的出链数量,即页面 v 把影响力 PR(v) 平均分配给了它的出链,这样统计所有能给 u 带来链接的页面 v,得到的总和就是网页 u 的影响力,即为 PR(u)。 ”
What? 这是在说什么? 只需要先明白两点:
所以你能看到,出链会给被链接的页面赋予影响力,当我们统计了一个网页链出去的数量,也就是统计了这个网页的跳转概率。
★在这个例子中,你能看到 A 有三个出链分别链接到了 B、C、D 上。那么当用户访问 A 的时候,就有跳转到 B、C 或者 D 的可能性,跳转概率均为 1/3。 B 有两个出链,链接到了 A 和 D 上,跳转概率为 1/2。 这样,我们可以得到 A、B、C、D 这四个网页的转移矩阵 M:
这个转移矩阵,每一行代表了每个节点入链上的权重(大家浏览别的页面的时候,有多大的概率能跳到我这来)。每一列代表了每个节点对其他页面的影响力的赋予程度(也就是大家浏览我这,有多大的概率跳到别的页面上去)。 ”
有了这个转移矩阵,我们就可以计算每个页面的影响力是多少了。
★比如上图A页面的影响力怎么计算呢?其实我们是通过他的入链点B、C的影响力去计算的,也就是我们的那个公式。开始我们假设四个页面的影响力相同,都是1/4。则A第一次的影响力这么想,B有两条出链,那么会给我传过它影响力的1/2。C有一条出链,那么会把它的影响力全传给A。 故:PR(A) = 1/4 * 1/2 + 1/4 这是一次迭代。你发现了吗?这其实就是转移矩阵M的第一行 * 一个全为1/4的列向量得到的(向量乘法) ”
所以如果我们利用向量的乘法原理的话,只需要一个向量乘法就可以计算出每个页面的影响力了。
我们假设 A、B、C、D 四个页面的初始影响力都是相同的,即:
当进行第一次转移之后,各页面的影响力 w1 变为:
然后我们再用转移矩阵乘以 w1 得到 w2 结果,直到第 n 次迭代后 wn 影响力不再发生变化,可以收敛到 (0.3333,0.2222,0.2222,0.2222),也就是对应着 A、B、C、D 四个页面最终平衡状态下的影响力。
你能看出 A 页面相比于其他页面来说权重更大,也就是 PR 值更高。而 B、C、D 页面的 PR 值相等。
至此,我们模拟了一个简化的 PageRank 的计算过程,也就是PageRank简化模型的原理了。
是不是计算起来很简单啊?那就再回去看看那个公式理解了没?
但是你发现了吗?虽然这个模型简单,但是有问题的,比如万一我有一个网页只有入链没有出链怎么办? 万一我有一个网页只有出链,没有入链怎么办?
上面的两个问题分别对应着等级泄露和等级沉没。
★这其实就和练功一样,如果其他所有人把功力传给一个人,而这个人只接收别人的功力并不传给其他人,那么这个人必定非常强大,其他人慢慢的就会功力丧失, 武侠小说里面的高手很多是这么炼成的吧(吸星大法这样的)。 如果一个人只往外传功力,不接收外来人的功力,比如给人疗伤的时候,那么这个人很快也就会功力丧失了。(武侠小说中疗伤的时候,某个大侠给人疗着疗着自己就昏过去了) ”
上面的两个例子可以很好的理解这两个问题。
那么如何有效解决呢?
为了解决简化模型中存在的等级泄露和等级沉没的问题,拉里·佩奇提出了 PageRank 的随机浏览模型。他假设了这样一个场景:用户并不都是按照跳转链接的方式来上网,还有一种可能是不论当前处于哪个页面,都有概率访问到其他任意的页面,比如说用户就是要直接输入网址访问其他页面,虽然这个概率比较小。
所以他定义了阻尼因子 d,这个因子代表了用户按照跳转链接来上网的概率,通常可以取一个固定值 0.85,而 1-d=0.15 则代表了用户不是通过跳转链接的方式来访问网页的,比如直接输入网址。
其中 N 为网页总数,这样我们又可以重新迭代网页的权重计算了,因为加入了阻尼因子 d,一定程度上解决了等级泄露和等级沉没的问题。
通过数学定理(这里不进行讲解)也可以证明,最终 PageRank 随机浏览模型是可以收敛的,也就是可以得到一个稳定正常的 PR 值。
这个算法有个好处,就是可以通过这个算法,给我们带来一点生活中的启示,会是什么启示呢? 啥?不要盲目从众? 这个就有点low了。
PageRank 可以说是 Google 搜索引擎重要的技术之一,在 1998 年帮助 Google 获得了搜索引擎的领先优势,现在 PageRank 已经比原来复杂很多,但它的思想依然能带给我们很多启发。
比如,如果你想要自己的媒体影响力有所提高,就尽量要混在大 V 圈中;如果想找到高职位的工作,就尽量结识公司高层,或者认识更多的猎头,因为猎头和很多高职位的人员都有链接关系。 这也就是很重要的理论:加人脉杠杆,搞定一人,撬动千人。(好吧,这个只是逆袭学习理论中的一小小部分,后面打算也会把逆袭学习理论整理出来,大家共勉。)
说了这么多,也知道了PageRank的原理了,那就让我们实战吧!
PageRank 算法工具在 sklearn 中并不存在,我们需要找到新的工具包。实际上有一个关于图论和网络建模的工具叫 NetworkX,它是用 Python 语言开发的工具,内置了常用的图与网络分析算法,可以方便我们进行网络数据分析。
上面举了一个网页权重的例子,假设一共有 4 个网页 A、B、C、D,它们之间的链接信息如图所示:
针对这个例子,我们看下用 NetworkX 如何计算 A、B、C、D 四个网页的 PR 值,具体代码如下:
import networkx as nx
# 创建有向图
G = nx.DiGraph()
# 有向图之间边的关系
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")]
for edge in edges:
G.add_edge(edge[0], edge[1])
pagerank_list = nx.pagerank(G, alpha=1)
print("pagerank值是:\n", pagerank_list)
结果如下:
pagerank值是:
{'A': 0.33333396911621094, 'B': 0.22222201029459634, 'C': 0.22222201029459634, 'D': 0.22222201029459634}
关键代码就nx.pagerank(G, alpha=1) 这一句话, 这里的alpha就是我们上面说的阻尼因子,代表用户按照跳转链接的概率。默认是0.85。这里是1,表示我们都是用跳转链接,不直接输入网址的那种。
好了,运行完这个例子之后,来看下 NetworkX 工具都有哪些常用的操作。
★
”
以上是关于图的基本操作,如果我们创建了一个图,并且对节点和边进行了设置,就可以找到其中有影响力的节点,原理就是通过 PageRank 算法,使用 nx.pagerank(G) 这个函数,函数中的参数 G 代表创建好的图。
数据集可以再这里下载:https://github.com/cystanford/PageRank先了解下数据集:
★整个数据集由三个文件组成:Aliases.csv,Emails.csv 和 Persons.csv,其中 Emails 文件记录了所有公开邮件的内容,发送者和接收者的信息。Persons 这个文件统计了邮件中所有人物的姓名及对应的 ID。因为姓名存在别名的情况,为了将邮件中的人物进行统一,我们还需要用 Aliases 文件来查询别名和人物的对应关系。 整个数据集包括了 9306 封邮件和 513 个人名,数据集还是比较大的。不过这一次我们不需要对邮件的内容进行分析,只需要通过邮件中的发送者和接收者(对应 Emails.csv 文件中的 MetadataFrom 和 MetadataTo 字段)来绘制整个关系网络。因为涉及到的人物很多,因此我们需要通过 PageRank 算法计算每个人物在邮件关系网络中的权重,最后筛选出来最有价值的人物来进行关系网络图的绘制。 ”
了解了数据集和项目背景之后,我们来设计到执行的流程步骤:
★
”
最终代码如下:
# -*- coding: utf-8 -*-
# 用 PageRank 挖掘希拉里邮件中的重要任务关系
import pandas as pd
import networkx as nx
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
# 数据加载
emails = pd.read_csv("./input/Emails.csv")
# 读取别名文件
file = pd.read_csv("./input/Aliases.csv")
aliases = {}
for index, row in file.iterrows():
aliases[row['Alias']] = row['PersonId']
# 读取人名文件
file = pd.read_csv("./input/Persons.csv")
persons = {}
for index, row in file.iterrows():
persons[row['Id']] = row['Name']
# 针对别名进行转换
def unify_name(name):
# 姓名统一小写
name = str(name).lower()
# 去掉, 和 @后面的内容
name = name.replace(",","").split("@")[0]
# 别名转换
if name in aliases.keys():
return persons[aliases[name]]
return name
# 画网络图
def show_graph(graph, layout='spring_layout'):
# 使用 Spring Layout 布局,类似中心放射状
if layout == 'circular_layout':
positions=nx.circular_layout(graph)
else:
positions=nx.spring_layout(graph)
# 设置网络图中的节点大小,大小与 pagerank 值相关,因为 pagerank 值很小所以需要 *20000
nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=True)]
# 设置网络图中的边长度
edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)]
# 绘制节点
nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4)
# 绘制边
nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2)
# 绘制节点的 label
nx.draw_networkx_labels(graph, positions, font_size=10)
# 输出希拉里邮件中的所有人物关系图
plt.show()
# 将寄件人和收件人的姓名进行规范化
emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)
emails.MetadataTo = emails.MetadataTo.apply(unify_name)
# 设置遍的权重等于发邮件的次数
edges_weights_temp = defaultdict(list)
for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText):
temp = (row[0], row[1])
if temp not in edges_weights_temp:
edges_weights_temp[temp] = 1
else:
edges_weights_temp[temp] = edges_weights_temp[temp] + 1
# 转化格式 (from, to), weight => from, to, weight
edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]
# 创建一个有向图
graph = nx.DiGraph()
# 设置有向图中的路径及权重 (from, to, weight)
graph.add_weighted_edges_from(edges_weights)
# 计算每个节点(人)的 PR 值,并作为节点的 pagerank 属性
pagerank = nx.pagerank(graph)
# 将 pagerank 数值作为节点的属性
nx.set_node_attributes(graph, name = 'pagerank', values=pagerank)
# 画网络图
show_graph(graph)
# 将完整的图谱进行精简
# 设置 PR 值的阈值,筛选大于阈值的重要核心节点
pagerank_threshold = 0.005
# 复制一份计算好的网络图
small_graph = graph.copy()
# 剪掉 PR 值小于 pagerank_threshold 的节点
for n, p_rank in graph.nodes(data=True):
if p_rank['pagerank'] < pagerank_threshold:
small_graph.remove_node(n)
# 画网络图,采用circular_layout布局让筛选出来的点组成一个圆
show_graph(small_graph, 'circular_layout')
运行结果:
针对代码中的几个模块个简单的说明:
★
”
今天用了一天的时间,学习PageRank算法的理论,并且通过理论做了一个实战,运用了一下,又抓紧记录,完成了一篇博客,心理还是很高兴的。学习知识的过程就是这样,如果只是单纯的输入,没有一点输出的话,那么很快就会忘记,输出一遍,至少在大脑里面停留了片刻,这里也留下了自己的踪迹,就像那就话说的:天空中没有鸟的痕迹,但是我已经飞过。
努力学习,快速感悟,敢于尝试,这样我们才能做到永远年轻,永远热泪盈眶。加油!
参考: