网络爬虫抓取微信好友总数量和微信好友男女性别的分布情况。
代码实现蛮简单的,可以自定义一个函数,获取性别信息,也可以直接调用value_counts()方法,可以更方便统计各项出现的次数。小编的微信好友男女数量情况如下图所示,在这里,1代表男士,2代表女士,0代表未知性别(因为有的好友并没有设置性别这一项)。
对于社交系统与电商网站,推荐系统占有很重要的位置,当数据量越来越大的时候,用户无法确定该选择什么商品,因此在电商系统中需要按照兴趣或者相似度给用户推荐相应的商品。相应的,在一个大型社交网络平台中,对于一些用户,我们希望推荐一些知名度较高,活跃度较高或者感兴趣的用户,比如一些明星,歌手,演员等等。在社交网络中,PageRank算法有着广泛的应用,因此,本篇文章主要介绍其原理。
对于大部分社交系统来说,如果只是简单的获取好友的信息远远不够,我们可以通过获取好友的好友的信息来扩展用户的朋友圈,使得信息量更加丰富,本项目中使用PageRank算法来完成二级邻居,然后按照Rank排序,选择Top5用户实现用户的好友的好友的推荐。
PageRank算法由Google的创始人拉里·佩奇和谢尔·布林于1998年发明.这项技术设计之初是为了体现网页的相关性和重要性,在搜索引擎优化 *** 作中经常被用来评估网页优化的成效因素之一.
从技术上看,搜索引擎需要解决以下三个问题:
本质就是一个爬虫问题,通过爬虫获取整个互联网的数据
关键在于快速找到.
它的实现方式有: 倒排索引,签名文件,后缀树等。我们最熟悉的是 倒排索引 。(并不熟悉,以后有机会再看)
排序是Google的搜索引擎能够兴起的一个决定性因素。
对网页排序有很多种方式,我们来看三种:
就是原封不懂地把索引到的链接直接返回给用户,缺点就不说了,想找自己感兴趣的内容估计要费不少功夫。
这种方式是一种只从关键词出现的次数和位置进行排序的方法。该方法以一个关键词与网页的相关度大小作为排序标准,而关键词在网页的相关度大小作为排序标准,而关键词在网页中的相关度则由它在网页中出现的频次和位置两方面加权计算得出。
缺点也很明显,容易出现刷分的情况,整篇文章中大量地刷关键词就能提高排名。
真正找到计算网页自身质量的完美的数学模型是Google的创始人拉里佩奇和谢尔盖布林。 下一节讲一下原理。
我们模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网页上的概率,这个概率就代表这个网页的重要性.
PageRank主要基于两个重要的假设:
如果一篇文章被越来越多的人引用,那么这篇文章可能就是一篇经典之作,如果这篇文章引用了其他的论文,那么一定程度上这篇被引用的文章也是一篇很好的文章。应用到社交网络中,如果一个好友被更多的人关注,那么说明该好友有很高的知名度和活跃度,那么,我们可以将该好友推荐给用户。
基于这两个假设,我们可以总结出PageRank算法的核心:
如下图,可以更好的表达PageRank算法的思想:
由上图可知,每个页面将自己的一部分rank传递给某个页面,我们可以通过计算传递给某个页面的所有rank值的和来计算出它的rank值,当然,不可能是通过一次计算完成,我们刚开始可以给每个页面赋予一个初始rank值,比如 1/N(N为页面总数) ,通过迭代计算得到该页面的rank值。
迭代计算停止的条件为:
使用有向图表示:
这个例子中只有四个网页,如果当前在A网页,那么悠闲的上网者将会各以1/3的概率跳转到B、C、D,这里的3表示A有3条出链,如果一个网页有k条出链,那么跳转任意一个出链上的概率是1/k,同理D到B、C的概率各为1/2,而B到C的概率为0。
我们在做计算的时候会将该图表示成一个二维的矩阵,我们做一个转换,就会变成下图的矩阵形式。 M(i,j) 表示j节点指向i节点的概率 ,一般来说每列和为1。
生成的 转移矩阵 非常简单, 矩阵的每一列代表该顶点所代表的页面除以对应页面的出链数得到的 。
有了转移矩阵,我们可以来定义行向量 V , V 的第i个分量记录 对应的Rank值,因此一次Rank的更新可以表示为:
在算法的第一轮计算中,我们假设上网者在每一个网页的概率都是相等的,即1/n,于是初试的概率分布就是一个所有值都为1/n的n维列向量 ,用 去右乘转移矩阵M,就得到了第一步之后上网者的概率分布向量 ,得到一个nX1的矩阵 , 这个 一轮迭代计算出来的PageRank值 。下面是 的计算过程:
得到了 后,再用 去右乘M得到 ,一直下去,即 , 最终V会收敛 .
不断的迭代,最终得到结果.
但是在迭代计算中,我们需要考虑如下两大阻力: Dead End 和 Spider Trap :
Dead End就是指一个页面只有入链但是没有出链,这时转移矩阵M的一列为零,导致最后结果为零。这时web不是强连通的,即存在某一类节点不指向别人,如下图的D。这个时候我们的算法就会出问题了,它不满足收敛性了。
为什么不满足收敛性了?
Spider Trap指页面的所有出链都指向自己,这样会使迭代结果中只有自己的页面的Rank值很高。其他页面的Rank值为零。
要克服上面两个问题,我们需要将迭代计算公式做如下转变。我们可以加入一个 随机跳转 机制.
即假设每个页面有很小概率拥有一个指向其他页面的链接。
表现出来就是:其他页面本来传递给一个页面的Rank值需要做一个折扣,作为补偿,可能需要一个页面指向该页面并且传递Rank值给该页面,该跳转的概率为β,因此表达式变为:
其中,N为页面总数 e 为一个N维且各个分量都是1的向量β通过经验得知一般设为0.15.
此时的计算结果过程为:
有机会再写,先空着
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)