• Posts tagged "算法"

Blog Archives

算法,如何改变命运

架构师的信仰系列文章,主要介绍我对系统架构的理解,从我的视角描述各种软件应用系统的架构设计思想和实现思路。

从程序员开始,到架构师一路走来,经历过太多的系统和应用。做过手机游戏,写过编程工具;做过大型Web应用系统,写过公司内部CRM;做过SOA的系统集成,写过基于Hadoop的大数据工具;做过外包,做过电商,做过团购,做过支付,做过SNS,也做过移动SNS。以前只用Java,然后学了PHP,现在用R和Javascript。最后跳出IT圈,进入金融圈,研发量化交易软件。

架构设计就是定义一套完整的程序规范,坚持架构师的信仰,做自己想做的东西。

关于作者:

  • 张丹(Conan), 程序员R,Nodejs,Java
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/architect-algorithm/

前言

近年来,随着大数据的飞跃式的发展,已经越来越深地开始影响到我们的生活,社交有腾讯大数据,购物有阿里大数据,搜索有百度大数据,出行有滴滴大数据等等。当数据越来越多地被积累,就需要算法来挖掘出数据的价值。特别是进入到大数据时代,算法显得越来越重要。

让死的数据变得有价值,就是算法的力量。进入到全民大数据的时代后,数据已经不再是门槛儿,最重要的是算法,算法才是真正能够创造生产力的地方。算法工程师的价值也会越来越大,但是你们真的发掘出来你们的价值了吗?

目录

  1. 算法在各个行业的应用
  2. 投身于哪个行业好?
  3. 金融最靠谱

1. 算法在各个行业的应用

大数据的兴起冲击着各行各业,带来机遇也带来挑战,没有数据你就没有核心价值。当有了数据作为基础,你要继续需要思考如何让数据变的有价值。过去的2016年的投资市场很惨淡,唯有人工智能大火了一把。从深度挖掘(Deep Learning)技术在图像识别领域的精确识别,迭代决策树(GBDT)在数据挖掘算法比赛中频繁获奖,到AlphaGo在围棋领域打败在人类选手,百度小度机器人在最强大脑的舞台上挑战人类脑王等等,这些事件都是算法领域的突破。

算法,真的已经应用到了各行各业,在慢慢地改变着人们的生活和习惯,比如说图像识别,自动驾驶,用户行为,金融征信,量化投资等领域,都在发生着变化。

图像识别领域,深度学习算法异军突起,不仅可以进行准确的人脸识别、指纹识别,还可以进行复杂的图像对比。我深刻记得,2016年参加的光谷人工智能大会上,听西安电子科技大学公茂果教授分享的“深度神经网络稀疏特征学习与空时影像变化检测”主题,利用图像识别技术,对比汶川地震前后的卫星照片和光感照片,准确地找到了受到地震影响最严重的区域,即震前和震后地貌发生变化最大的区域,快速地为救援队定位到最需要帮助的地点,解救伤者,投放救援物资。

自动驾驶领域,可以通过识别路面的状况来实现自动驾驶、自动停车。Uber无人驾驶汽车已经在匹兹堡上路测试,自动驾驶汽车配备了各式传感器,包括雷达、激光扫描仪以及高分辨率摄像头,以便绘制周边环境的细节。自动驾驶汽车有望改善人类的生活质量,也可挽救数百万人的性命,为人们提供更多的出行方便。5年前,我在听Andrew Ng的斯坦福大学机器学习公开课的时候,就被当时的自动驾驶视频介绍所震撼,科幻电影中的世界就快变成现实了。

用户行为分析,人类有各种各样的行为和需求。衣食住行,吃喝玩乐,都是人的最基本的行为。大多数人的行为是共性的,商家可以收集这些行为数据,通过数据挖掘算法来找到人们行为共性的规律。根据用户的购物行为,商家可以为用户推荐喜欢的商品,这样就有了推荐系统; 根据用户对信息的查询行为,可以发现用户对信息的需求,这样就有了搜索引擎;根据用户位置的变化,可以发现用户的出行需求,这样就有了地图应用;针对用户个性化的行为,可以给用户打上标签,用来标注用户的特征或身份,这样就有了用户画像。用户行为分析,让商家了解用户习惯,同时也让用户了解自己,有巨大的商业价值。

在金融领域也有很多,算法应用的场景。

金融征信领域,传统信贷业务都是银行核心业务,但由于中国人数众多且小客户居多,银行无法负担为小客户服务的高成本,导致民间信贷的兴起。2014年底互联网金融P2P的开始爆发,贷款需求被满足的同时,却暴露出了违约风险。征信体系缺失,导致很多P2P公司坏账率很高,到2016年底P2P跑路的多达数千家。征信需求,变得非常迫切。比如,某个人想买车但现金不够,这时就需要进行贷款。商家给用户进行贷款时,通过信用风险的评级就能判断出这个用户的还款能力,从而来决定给他贷多少钱,以什么周期还款,减少违约风险。支付宝的芝麻信用分,是目前被市场一致认可的信用评分模型。

量化投资领域,我认为这个领域最复杂的,最有挑战性的,同时也是最有意思的。可以通过量化算法模型实现赚钱,是最容易变现的一种方法。在金融投资领域中,有各式各样的数据,反应的各种金融市场的规则,有宏观数据,经济数据,股票数据,债券数据,期货数据,还有新闻数据,情绪数据等等,金融宽客(Quant)通过分析各种各样的数据,判断出国家的经济形势和个股的走势,进行投资组合算法,实现投资的盈利。

看到这里,我想问问大家,你们脑子里那些聪明的想法,有没有被金融行业的魅力撩出些许的荷尔蒙?

2. 投身于哪个行业好?

从上面各个行业的算法应用来说,都有很广阔的应用前景。作为一个算法的研究者,那我们究竟投身到哪个行业更好呢?

这个其实要从多个方面进行考虑,我们的目标是个人价值最大化。那么,你要选择一个自己能够接触到的、完全竞争的、短流程的渠道,利用你的算法技术和对业务的理解实现变现的过程。

其实,满足个人可变现的渠道其实非常有限,你很难通过一个图像识别的算法,直接面向市场进行收钱,你需要有一个承载的产品,而产品研发的过程是非常漫长的。同样地,自动驾驶算法需要汽车生产场商的实验。用户行为分析算法,需要电子商务平台的以用户购买行为进行验证。

量化投资,可以用个人账号在中国二级投资交易市场,完成交易过程。这种方式没有很多的中间环节,你获得交易所的数据,自己编写算法模型,然后用自己的钱去交易,完全自己把握。只要算法有稳定的收益率,你就可以赚到钱。这种变现方法,其实就是量化投资,从金融的角度才是最靠谱的一种变现方法。

3. 金融最靠谱

作为IT人,我们懂编程,懂算法,只要再了解金融市场的规则,就能去金融市场抢钱了。中国的金融二级投资交易市场,是一个不成熟的市场,同时又是情绪化的市场。市场中,每天都存在着大量的交易机会,每天都会有“乌龙指”。量化投资的技术,可以帮助我们发现这些由于信息不对称出现的机会,赚取超额的收益。

那么到底怎么做量化投资呢?。

下面举个例子,一个私募基金,募集了1亿资金准备杀入金融市场。基金经理决定按照投资组合的建模思路,对各类金融资产进行组合配置。下图就反应了各类资产,以均值-方差的标准来创建投资组合,符合资本资产定价模型(CAPM)的原理。关于资本资产定价模型详细介绍,请参考文章R语言解读资本资产定价模型CAPM

图中,x轴为收益率的标准差,y轴为收益率的均值,图中的点构建了可投资区域,每个点代表一个可投资产品,每条虚线连接的点的集合,就是一个有效的投资组合。

对于,图中近百个点来说,假设每次要配置5种资产做投资组合,那么就是75287520种组合方法;如果配置10种资产,可选方案就是一个非常大的数字了。

我可以用R语言来计算一下,投资组合的数量。


# 100个选5个,做组合
> choose(100,5) 
[1] 75287520

# 100个选10个,做组合
> choose(100,10) 
[1] 1.731031e+13

对于金融市场来说,有非常多的金融资产可供我们来选择。中国A股股票有3000多只,基金2000多支, 债券3000多支,期货100多支,还有大综商品,货币市场产品,汇率产品,海外投资市场等。如果把这个多种的资产进行组合,将有无限多的投资组合可以进行选择,是一个无限大的计算量。我们需要利用算法进行组合优化,从而找到市场上最优的投资组合。算法本身,才是最能体现价值的部分。

那么传统的基金是如何进行投资组合的?大多都是靠投资经理的主观投资经验来完成的。在金融市场里,每支基金都配置了不同的资产做组合,我们随便找支基金看看,它的投资组合是如何配置的。比如,华夏成长(000001.OF)基金,它是股债混合型的。数据来源于万得, 2017年2月8日的数据。

从业绩表现来看,这支基金最辉煌的时代在2006-2007年,连续6个月回报101.49%,那么最低1年表现就比较差,为仅落后于沪深300指数,整体排名也都在后面。今年以来收益率0.58%,同类排名144/507;1年收益率-1.45%,同类排名400/487;3年收益11.67%,同类排名378/426;5年收益39.96%,同类排名290/352。

我们再来看一下,这支基金的组合成分,主要是股票和债券。

债券占比 :

证券名称 占净值比 近3月涨跌
12石化01 2.34%↑ -0.49%
116国泰君安CP008 2.12%↑ -0.03%
116农发01 1.91%↑ -0.08%
110营口港 1.70%↑ -1.59%
109常高新 1.62%↑ -0.65%

股票占比:

证券名称 占净值比 近3月涨跌
中工国际 4.09%↑ -0.95%
中国医药 3.85%↑ 0.34%
神雾环保 3.81%↑ 2.56%
东方网络 2.89%↑ -13.00%
立讯精密 1.52%↑ -1.82%
高能环境 1.42%↑ -14.96%
上汽集团 1.38%↑ 7.88%
田中精机 1.31%↑ -12.28%
上海医药 1.25%↑ 5.39%
中牧股份 1.21%↑ -4.25%

从市场上几千支的股票和债券中进行选择,并配置不同的权重,之前都是基金经理干的活,那么我们用算法一样也可以干,说不定用算法模型构建的组合业绩会更好。如果我们用算法模型,取代了年薪几百万的基金经理,那么你就能够获得这个收益。最终实现个人价值,从而用算法改变命运。所以,通过金融变现才是最靠谱的。

转载请注明出处:
http://blog.fens.me/architect-algorithm/

打赏作者

R语言为量化而生

R的极客理想系列文章,涵盖了R的思想,使用,工具,创新等的一系列要点,以我个人的学习和体验去诠释R的强大。

R语言作为统计学一门语言,一直在小众领域闪耀着光芒。直到大数据的爆发,R语言变成了一门炙手可热的数据分析的利器。随着越来越多的工程背景的人的加入,R语言的社区在迅速扩大成长。现在已不仅仅是统计领域,教育,银行,电商,互联网….都在使用R语言。

要成为有理想的极客,我们不能停留在语法上,要掌握牢固的数学,概率,统计知识,同时还要有创新精神,把R语言发挥到各个领域。让我们一起动起来吧,开始R的极客理想。

关于作者:

  • 张丹(Conan), 程序员Java,R,Nodejs
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/r-finance/

r-finance

前言

做数据分析的朋友,一定听说过R语言。R语言是一门统计语言,在数据分析领域优势是非常明显的。

本文以 “R语言,为量化而生”为题,说明R语言真的很适合做金融做量化策略。金融本身是玩数据行业,R的最大的优势就是数据分析,所以用R来做量化投资的策略,真是很配,不仅顺手而且方便,用了你就会知识。

本文将由3个方面来介绍,R语言做量化是多么的适合。

目录

  1. 为什么是R语言?
  2. R语言的数据处理和时间序列
  3. R语言和金融模型

1. 为什么是R语言?

那么为什么是R语言,而不是其他的语言? 先简单介绍一下,我们的个人经历。

我是一个程序员,从2004年开始接触Java写了10多年的Java程序,期间还尝试过多种编程语言,VB、PHP、Python、SAS、R、Nodejs,最后把自己锁定在R,Nodejs和Java。谈不上对每一种语言都有很深的理解,但是每种语言的特点还是有点心得。

之所以选择R,Nodejs和Java这3种语言,有一部分情怀,更多的是理性。从技术发展来看,编程开发变得越来越简单,10年前用JavaEE做一个简单的web项目至少要2人月,现在用Nodejs新人边学边搞只需10人天。而且随着业务的多样化,单一的技术已经不足以支撑业务的发展,业务在从传统的软件开发向互联网和数据产品的方向在进化。根据不同语言的特点,每种都将在开发中占据一席之地,而很难在出现一种语言统一天下的情况。

R语言将在数据分析领域发挥着重要的作用。R语言的3个特性,数学计算、数据建模和数据可视化。R语言封装了多种基础学科的计算函数,我们在R语言编程的过程中只需要调用这些计算函数,就可以构建出面向不同领域、不同业务的、复杂的数学模型。

另外,R的知识体系结构是复杂的,要想学好R,就必须把多学科的知识综合运用,而最大的难点不在于R语言本身,在于使用者的知识基础和综合运用的能力。

r-basic

图中我将R语言知识体系结构分为3个部分:IT技术 + 业务知识 + 基础学科。

  • IT技术:是数据大发展时代必备的技术之一,R语言就是我们应该要掌握的一门技术。
  • 业务知识:是市场经验和法则,不管你在什么公司,你都了解业务是什么,产品是什么,用户是谁,公司的价值在哪里!
  • 基础学科:是我们在学校里学到的理论知识,虽然当初学的时候并不理解,工作中如果你还能掌握并实际运用,那么这将是你最有价值的竞争力。

关于R的知识体系,可以参考文章,R语言知识体系概览

对于金融量化投资来说,刚好是一个交叉学科,你需要懂IT技术,熟悉金融市场的规则,有数学建模的能力。R语言,正好可以帮我们来解决这样的问题,所以“R语言,为量化而生”!

对于做过数据分析的人来说,大家都了解什么是最费时间的!!无疑就是数据处理的部分。

2. R语言的数据处理和时间序列

第二部分,我们来介绍一下R语言的数据类型和数据处理的一些方法。当然,本文并没有介绍如何入门R语言,新手入门请参考文章R的极客理想系列文章

2.1 基本数据类型

在R语言中,数据类型包括向量类型,字符串类型,数字类型,布尔类型,矩阵类型,数据框类型,list类型等,通常我们在使用R语言里做数据处理的时候,大部分都会以数据框(data.frame)类型为一个主要的数据内存类型来使用。

数据框(data.frame)类型是R语言内置的一种数据类型,我们可以简单地把它理解为,与关系型数据库中表的结构是类似的,是一种二维的数据结构。


# 新建一个数据框
> data.frame(A=1:6,B=LETTERS[1:6])
  A B
1 1 A
2 2 B
3 3 C
4 4 D
5 5 E
6 6 F

正是由于R语言内置了这样的数据类型,使我们从数据库读取数据或导入CSV格式的数据时,与R语言有了一个很好的映射关系,直接加载到R语言的内存中变成标准化数据格式。

然后,就可以基于标准化的数据格式,用R语言的功能函数来处理数据了。比如,对于做数据库开发的人员来说,他可以使用sqldf包,在R语言中通过SQL语句对数据进行数据变换。同时,也可以按着数据框(data.frame)的标准方法进行数据处理,通过约定的向量索引下标的方式来按行按列来读取数据,或使用功能函数处理数据。


# sqldf包的使用
> library(sqldf)
> sqldf('select * from iris limit 6')
  Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1          5.1         3.5          1.4         0.2  setosa
2          4.9         3.0          1.4         0.2  setosa
3          4.7         3.2          1.3         0.2  setosa
4          4.6         3.1          1.5         0.2  setosa
5          5.0         3.6          1.4         0.2  setosa
6          5.4         3.9          1.7         0.4  setosa

# 向量索引
> iris[1:6,]
  Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1          5.1         3.5          1.4         0.2  setosa
2          4.9         3.0          1.4         0.2  setosa
3          4.7         3.2          1.3         0.2  setosa
4          4.6         3.1          1.5         0.2  setosa
5          5.0         3.6          1.4         0.2  setosa
6          5.4         3.9          1.7         0.4  setosa

# head函数使用
> head(iris)
  Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1          5.1         3.5          1.4         0.2  setosa
2          4.9         3.0          1.4         0.2  setosa
3          4.7         3.2          1.3         0.2  setosa
4          4.6         3.1          1.5         0.2  setosa
5          5.0         3.6          1.4         0.2  setosa
6          5.4         3.9          1.7         0.4  setosa

我们经常还会对数据进行转型处理,把数据框(data.frame)类型和其他数据类型的进行转化。我们有时会使用矩阵计算,R语言中默认供了矩阵(matrix)数据类型,可以很方便地把数据框转类型成矩阵类型,有时也需要把数据框的某一行或某一列转型为一个向量类型数据,或者把数据框变成一个list类型。通过数据的格式变换,用标准化的数据结构来满足数据分析的要求。

虽然R语言是统计语言,从性能上来说比C++/Java等语言慢不少。但对于数据分析的业务场景,用R语言来做数据处理的时候,你不用考虑程序如何架构,指针怎么定义,内存是否会泄露,只要关注你的数据和算法就行了。唯一需要注意的一点,不要直接用for循环的方式处理数据,尽量使用向量计算或矩阵计算的计算方法。当必须用循环的时候,你就需要用apply家族函数,代替for循环来做数据处理。关于apply家族函数的用法,请参考文章掌握R语言中的apply函数族

如果你的数据量比较大,1GB,10GB,甚至有100GB,对于这种规模比较大的数据集,apply的计算方式就不太能满足计算性能的要求了。你依然可以用data.table包, bigmemory包, ff包等,或者并行计算的包加速R语言在单机上的计算的性能。data.table的使用方法,请参考文章超高性能数据处理包data.table

那么再大规模的数据,超过1TB这个量级,不只是R语言,每种语言都会遇到计算性能的瓶颈。这个时候,我们需要把数据放到分布式系统中,如Hadoop或其他大数据的引擎中进行存储和计算。R语言与各种的大数据平台的通信接口都是通的,比如RHadoop,rhive, rhbase, rmongodb, rCassandra, SparkR, sparklyr等。如果你想了解hadoop的知识,请参考文章Hadoop家族系列文章RHadoop实践系列文章, R利剑NoSQL系列文章 之 Hive

2.2 时间序列类型

除了R语言的内置基础数据类型,对于金融的数据处理,一般我会把它变成标准的时间序列类型的数据,R语言中基本的时间序列的类型为 zoo 和 xts类型,当然还有一些其他包提供的数据类型。关于zoo和xts的详细介绍,请参考文章 R语言时间序列基础库zoo可扩展的时间序列xts

通过类型变换可以很方便地把的data.frame或者matrix等基础类型数据,变成xts时间序列类型的数据。时间序列类型的好处是它默认会以时间作为索引,对于量化策略来说,每条数据记录他都会有数据产生的时间,那这个时间就正好可以作为索引列的时间。


# 数据框
> df<-data.frame(A=1:6,B=rnorm(6))

# xts时间序列类型
> xdf<-xts(df,order.by=as.Date('2016-01-01')+1:6);xdf
           A           B
2016-01-02 1 -1.24013232
2016-01-03 2 -0.21014651
2016-01-04 3 -1.63251615
2016-01-05 4 -0.67279885
2016-01-06 5  0.01487863
2016-01-07 6  0.92012628

# 类型检查
> class(xdf)
[1] "xts" "zoo"

那么以时间作为数据的索引列的好处是,可以很方便地把数据以时间维度进行对齐。比如,你设计了一个股票交易策略和一个期货交易策略,由于股票是T+1交易,今天买了明天才能卖;而期货是T+0交易,今天买了马上就可以卖出。针对不同的市场规则,在设计交易策略时,可能就会选择不同的交易周期,那么这时两个策略的交易周期就会不一样,那么时间维度可能也不是对齐的。如果这两个策略是对冲的,那么我们就需要把它们以时间维度进行对齐,才能进行实现对策略模型对冲的准确计算。

把不同时间的维度的数据转化成同一个时间维度,相当于做时间的标准化。通过标准化的操作,让数据变成同一时间维度,数据之间才能够进行计算。

举个简单的例子,我们做股票交易,在实盘交易过程中,你可能最关心的是每秒最新的价格数据,每一秒都会产生一条数据,这是属于日内交易策略。另外,我们再做一个周期稍微长一点的策略,以日线为基础的,那么这里一条记录就是一天收盘价。对比日内策略,1秒钟一条数据和1天一条数据,它们不同维度的数据,是不能直接进行计算。

我们要处理这种不同周期维度数据的时候,就需要把数据转成同一个维度的。比如,我们对日线和周线的数据进行合并的时候,可以是把周线数据拆成日线数据,就是把一周分成五天。反过来,也可以把日线数据合并为周线数据,把5天的数据合并成一周。

所以这个时候就需要一个统一的数据格式进行标准化的数据定义,zoo和xts就是我们作为时间序列基础数据类型。这两个包是由第三方开发的,提供了很丰富的时间序列处理函数,我们可以直接使用这些函数来操作金融数据。很多其他的第三方金融算法分析包,也都是以这两个包作为基础开发。

3. R语言和金融模型

当我们掌握了R语言处理数据的方法,了解了如何使用R语言的基础数据类型和时间序列数据类型,下面我们就可以构建金融的策略模型。

金融建模跟其他行业的数据建模是类似的,只是由于行业不一样,金融行业有很多背景知识和金融市场规则需要我们了解。金融本身就是一个玩数据的行业,你可以通过获得交易数据,财务数据,上市公司的各种事件数据,基本面数据,宏观数据,舆情数据,互联网数据等,来构建你自己的交易策略。

我们需要把这些数据进行组合整理,结合你自己对业务的理解,使用R语言从数据中发现规律,并构建交易模型。用程序对历史数据进行回测,来验证规律的可靠性,是否会长期有效,并控制风险,最后把验证过的规律变成算法模型,这个就是金融策略建模的过程。

从金融交易分析的角度,可以从3个维度进行分析 基本面分析,技术面分析和消息面分析。

  • 基本面:指对宏观经济、行业和公司基本情况的分析,包括公司经营理念策略、公司报表等的分析。长线投资一般用基本面分析,通过基本面可以判断是否值去交易。
  • 技术面:指通过技术指标变化,判断股票走势形态,进行K线组合等,通过技术面可以判断如何进行交易。
  • 消息面:指上市公司发布的利好和利空的消息,通过消息面可以判断市场的情绪。

对于量化模型,大部分都是基于技术指标的模型,通过技术指标建模,跟踪市场的表现。在不完全了解金融业务和金融市场的情况下,通过几个技术指标来监控市场的走势,发现市场的机会也是有可能的。

量化交易和主观交易并不是对立的,量化交易是对主观交易的补充,当我们以数据作为决策基础的时候,其实可以尽量减少拍脑袋过程,创建数据模型也可以给我们心里建立良好的信心。如果交易没有使用量化的方法,那就跟我们平时做事一样,你可能想到什么就是什么。没有数据基础,那完全就是感觉,这样子交易就是很容易赔钱。

对于中国很多的散户,听到一个消息就跟着风的买卖股票,或者凭自己感觉大盘该涨了就跟进去,这些操作其实都是很不理性的。如果你通过量化的方法,即使再简单,就靠几条均线来进行判断,这样也是能给自己一个数据的基础,建立信心,而不是完全拍脑袋的事儿。

量化交易模型主要是以技术指标为主,常用的技术指标有不少,虽然简单但还是很有用的。对于很多实盘上运行的量化策略,大都会基于这些基础的指标,但并不是把每个指标单独使用。而是把多个指标通过变换组合使用,比如说MACD是均线模型,大部分的趋势策略都以MACD做为基础指标,通过变换再生成新的衍生指标。

常用的技术指标还包括KDJ、Boll、RSI、CCI等,当你直接使用这些指标的时候,可能效果并不是太好。因为市场上普遍接受了这些技术指标,已经被大量使用。单纯地用一个指标,你掌握的信息并不比别人多,所以你可能抓不到市场上赚钱的机会。

我们需要把多种技术指标或者多个维度的指标进行结合,通过组合优化的方式来降低策略的不确定风险,同时提高收益率。如果你找到了一个只有你自己知道市场规律,你的策略产生的信号完全是跟别人有区别的,你抓住了别人看不到的机会,这个才是你的赚钱机会。你领先的越多,越少人知道这个规则,那你可能赚钱的机会就越多。

建立量化模型,其实和我们平时做数据分析的思考试是一样的。要把这件事做好,我们需要把IT技术,业务知识和基础学科知识做进一步的结合,当你发现这个结合是属于你自己特有一个知识体系,你才能更好的发挥你的才能。

我们为什么要用R来做这件事情?

首先,R语言本身提供了很多数学、统计的基础包,让数学计算变得非常容易。R语言提供了常用的数据结构,向量、数据框、矩阵等,把数据变成标准化的数据,你的关注点只在数据上就可以了。另外,R语言是免费开源的,很多的第三方开发者提供了丰富的数据挖掘包,让你可以方便的使用各种算法模型,短短几行代码,就可以搞定一个复杂的事情。

R语言,在金融领域提供了很多交易框架或者计算模型,如果你了解了金融的理论知识以后,同时有一定的金融市场经验,你可以很方便的利用这些别人提供的这些技术框架,来构建自己的交易模型。CRAN上发布的金融项目,你可以去 R的官方网站 (https://cran.r-project.org/),找到Task Views 菜单里的 Finance标签。

task

通过调用第三方的程序包,自己的代码量就变的非常少。我们做一个R语言的策略,如果是很复杂的,你可能要写100-200行,但是如果你要实现同样复杂的策略,放到C++/Java去实现,这个策略就是没有1000-2000行是不可能实现的。在CRAN上面,简单数一下Finance标签下面列出的金融包就有141个,我相信没有哪种语言会比R语言对金融行业支持的更多了。

task2

虽然说R语言在性能上有些问题,但是我们会有多少了交易策略是基于一种高频的模型,对性能要求极高的呢?其实很少。就算是高频交易策略,几秒钟交易一次,R语言都可能满足要求。

海量金融数据我们怎么处理呢?

我们可以把基于海量数据的计算变成离线模型,金融行业每天都会产生大量的数据,像每日产生的交易数据,中国市场每天可能都是以GB的量来增长,跟互联网比起来不是很快,但对于你程序加载10年的数据,他要GB或TB的一个量级。

R语言本身真的很难处理这种量级的数据,但是这种量级数据对于其他语言来说同样是很难处理的。我们并不需要把这种体量的数据,都加载到内存中,进行实时数据计算。变成离线的计算模型,仅用于建模回测。把海量数据能变成离线的方式,放到hadoop或spark计算,用海量数据进行模型的训练。

我们用到的实时数据,一般就是一天或几天的数据,会不很大,每天从开盘到收盘可能也就1-2GB,对于这个大小,我们完全有能力放到内存中,进行各种各样的计算。

做量化交易难点还是在于如何发现市场机会,R语言可以很好的满足数据计算,建模,分析等的所有技术的部分。利用你的擅长,找到市场的机会,然后去实盘交易赚到钱,我们就完成了整个的交易过程。

本文并没有介绍,如何用R语言真正的去实现一个交易策略,你可以通过下面的列表找到对应的文章。

2015年我在创业,希望能推动R语言在金融量化领域的发展,但是由于种种原因项目没有持续发展。接下来,我还会以个人的方式继续努力,继续推动R在金融领域的发展。R对我们的影响和改变是非常大的,我认识R是非常好的一门语言,我会把推动R的发展,当成一项事业来做。希望也能和各位业界朋友,一起努力,把这份事业做下去。

转载请注明出处:
http://blog.fens.me/r-finance/

打赏作者

R语言中的遗传算法

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/algorithm-ga-r/

ga-r

前言

人类总是在生活中摸索规律,把规律总结为经验,再把经验传给后人,让后人发现更多的规规律,每一次知识的传递都是一次进化的过程,最终会形成了人类的智慧。自然界规律,让人类适者生存地活了下来,聪明的科学家又把生物进化的规律,总结成遗传算法,扩展到了更广的领域中。

本文将带你走进遗传算法的世界。

目录

  1. 遗传算法介绍
  2. 遗传算法原理
  3. 遗传算法R语言实现

1. 遗传算法介绍

遗传算法是一种解决最优化的搜索算法,是进化算法的一种。进化算法最初借鉴了达尔文的进化论和孟德尔的遗传学说,从生物进化的一些现象发展起来,这些现象包括遗传、基因突变、自然选择和杂交等。遗传算法通过模仿自然界生物进化机制,发展出了随机全局搜索和优化的方法。遗传算法其本质是一种高效、并行、全局搜索的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应的控制搜索过程,计算出全局最优解。

遗传算法的操作使用适者生存的原则,在潜在的种群中逐次产生一个近似最优解的方案,在每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近似解。这个过程会导致种群中个体的进化,得到的新个体比原来个体更能适应环境,就像自然界中的改造一样。

如果从生物进化的角度,我们可以这样理解。在一个种群中,个体数量已经有一定规模,为了进化发展,通过选择和繁殖产生下一代的个体,其中繁殖过程包括交配和突变。根据适者生存的原则,选择过程会根据新个体的适应度进行保留或淘汰,但也不是完全以适应度高低作为导向,如果单纯选择适应度高的个体可能会产生局部最优的种群,而非全局最优,这个种群将不会再进化,称为早熟。之后,通过繁殖过程,让个体两两交配产生下一代新个体,上一代个体中优秀的基因会保留给下一代,而劣制的基因将被个体另一半的基因所代替。最后,通过小概率事件发生基因突变,通过突变产生新的下一代个体,实现种群的变异进化。

经过这一系列的选择、交配和突变的过程,产生的新一代个体将不同于初始的一代,并一代一代向增加整体适应度的方向发展,因为最好的个体总是更多的被选择去产生下一代,而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复:每个个体被评价,计算出适应度,两个个体交配,然后突变,产生第三代。周而复始,直到终止条件满足为止。

遗传算法需要注意的问题:

  • 遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优,而不能达到全局最优。
  • 初始种群的数量很重要,如果初始种群数量过多,算法会占用大量系统资源;如果初始种群数量过少,算法很可能忽略掉最优解。
  • 对于每个解,一般根据实际情况进行编码,这样有利于编写变异函数和适应度函数。
  • 在编码过的遗传算法中,每次变异的编码长度也影响到遗传算法的效率。如果变异代码长度过长,变异的多样性会受到限制;如果变异代码过短,变异的效率会非常低下,选择适当的变异长度是提高效率的关键。
  • 变异率是一个重要的参数。
  • 对于动态数据,用遗传算法求最优解比较困难,因为染色体种群很可能过早地收敛,而对以后变化了的数据不再产生变化。对于这个问题,研究者提出了一些方法增加基因的多样性,从而防止过早的收敛。其中一种是所谓触發式超级变异,就是当染色体群体的质量下降(彼此的区别减少)时增加变异概率;另一种叫随机外来染色体,是偶尔加入一些全新的随机生成的染色体个体,从而增加染色体多样性。
  • 选择过程很重要,但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要,因为变异仅仅是保证不丢失某些可能的解;而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新,对于初期的种群来说,交叉几乎等效于一个非常大的变异率,而这么大的变异很可能影响进化过程。
  • 遗传算法很快就能找到良好的解,即使是在很复杂的解空间中。
  • 遗传算法并不一定总是最好的优化策略,优化问题要具体情况具体分析。所以在使用遗传算法的同时,也可以尝试其他算法,互相补充,甚至根本不用遗传算法。
  • 遗传算法不能解决那些“大海捞针”的问题,所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题,使得算法的进化失去导向。
  • 对于任何一个具体的优化问题,调节遗传算法的参数可能会有利于更好的更快的收敛,这些参数包括个体数目、交叉率和变异率。例如太大的变异率会导致丢失最优解,而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择,现在还没有实用的上下限。
  • 适应度函数对于算法的速度和效果也很重要。

遗传算法的应用领域包括计算机自动设计、生产调度、电路设计、游戏设计、机器人学习、模糊控制、时间表安排,神经网络训练等。然而,我准备把遗传算法到金融领域,比如回测系统的参数寻优方案,我会在以后的文章中,介绍有关金融解决方案。

2. 遗传算法原理

在遗传算法里,优化问题的解是被称为个体,它表示为一个变量序列,叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串,也有其他表示法,这一过程称为编码。首先要创建种群,算法随机生成一定数量的个体,有时候也可以人工干预这个过程进行,以提高初始种群的质量。在每一代中,每一个个体都被评价,并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序,适应度高的在前面。

接下来,是产生下一代个体的种群,通过选择过程和繁殖过程完成。

选择过程,是根据新个体的适应度进行的,但同时并不意味着完全的以适应度高低作为导向,因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解,我们称之为早熟。作为折中,遗传算法依据原则:适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。

繁殖过程,表示被选择的个体进入交配过程,包括交配(crossover)和突变(mutation),交配对应算法中的交叉操作。一般的遗传算法都有一个交配概率,范围一般是0.6~1,这个交配概率反映两个被选中的个体进行交配的概率。

例如,交配概率为0.8,则80%的“夫妻”个体会生育后代。每两个个体通过交配产生两个新个体,代替原来的“老”个体,而不交配的个体则保持不变。交配过程,父母的染色体相互交換,从而产生两个新的染色体,第一个个体前半段是父亲的染色体,后半段是母亲的,第二个个体则正好相反。不过这里指的半段並不是真正的一半,这个位置叫做交配点,也是随机产生的,可以是染色体的任意位置。

突变过程,表示通过突变产生新的下一代个体。一般遗传算法都有一个固定的突变常数,又称为变异概率,通常是0.1或者更小,这代表变异发生的概率。根据这个概率,新个体的染色体随机的突变,通常就是改变染色体的一个字节(0变到1,或者1变到0)。

遗传算法实现将不断的重复这个过程:每个个体被评价,计算出适应度,两个个体交配,然后突变,产生下一代,直到终止条件满足为止。一般终止条件有以下几种:

  • 进化次数限制
  • 计算耗费的资源限制,如计算时间、计算占用的CPU,内存等
  • 个体已经满足最优值的条件,即最优值已经找到
  • 当适应度已经达到饱和,继续进化不会产生适应度更好的个体
  • 人为干预

算法实现原理:

ga

  • 1. 创建初始种群
  • 2. 循环:产生下一代
  • 3. 评价种群中的个体适应度
  • 4. 定义选择的适应度函数
  • 5. 改变该种群(交配和变异)
  • 6. 返回第二步
  • 7. 满足终止条件结束

3. 遗传算法R语言实现

本节的系统环境

  • Win7 64bit
  • R: 3.1.1 x86_64-w64-mingw32/x64 (64-bit)

一个典型的遗传算法要求:一个基因表示的求解域, 一个适应度函数来评价解决方案。

遗传算法的参数通常包括以下几个:

  • 种群规模(Population),即种群中染色体个体的数目。
  • 染色体的基因个数(Size),即变量的数目。
  • 交配概率(Crossover),用于控制交叉计算的使用频率。交叉操作可以加快收敛,使解达到最有希望的最优解区域,因此一般取较大的交叉概率,但交叉概率太高也可能导致过早收敛。
  • 变异概率(Mutation),用于控制变异计算的使用频率,决定了遗传算法的局部搜索能力。
  • 中止条件(Termination),结束的标志。

在R语言中,有一些现成的第三方包已经实现的遗传算法,我们可以直接进行使用。

  • mcga包,多变量的遗传算法,用于求解多维函数的最小值。
  • genalg包,多变量的遗传算法,用于求解多维函数的最小值。
  • rgenoud包,复杂的遗传算法,将遗传算法和衍生的拟牛顿算法结合起来,可以求解复杂函数的最优化化问题。
  • gafit包,利用遗传算法求解一维函数的最小值。不支持R 3.1.1的版本。
  • GALGO包,利用遗传算法求解多维函数的最优化解。不支持R 3.1.1的版本。

本文将介绍mcga包和genalg包的遗传算法的使用。

3.1 mcga包

我们使用mcga包的mcga()函数,可以实现多变量的遗传算法。

mcga包是一个遗传算法快速的工具包,主要解决实值优化的问题。它使用的变量值表示基因序列,而不是字节码,因此不需要编解码的处理。mcga实现了遗传算法的交配和突变的操作,并且可以进行大范围和高精度的搜索空间的计算,算法的主要缺点是使用了256位的一元字母表。

首先,安装mcga包。


> install.packages("mcga")
> library(mcga)

查看一下mcga()函数的定义。


> mcga
function (popsize, chsize, crossprob = 1, mutateprob = 0.01, elitism = 1, minval, maxval, maxiter = 10, evalFunc) 

参数说明:

  • popsize,个体数量,即染色体数目
  • chsize,基因数量,限参数的数量
  • crossprob,交配概率,默认为1.0
  • mutateprob,突变概率,默认为0.01
  • elitism,精英数量,直接复制到下一代的染色体数目,默认为1
  • minval,随机生成初始种群的下边界值
  • maxval,随机生成初始种群的上边界值
  • maxiter,繁殖次数,即循环次数,默认为10
  • evalFunc,适应度函数,用于给个体进行评价

接下来,我们给定一个优化的问题,通过mcga()函数,计算最优化的解。

题目1:设fx=(x1-5)^2 + (x2-55)^2 +(x3-555)^2 +(x4-5555)^2 +(x5-55555)^2,计算fx的最小值,其中x1,x2,x3,x4,x5为5个不同的变量。

从直观上看,如果想得到fx的最小值,其实当x1=5,x2=55,x3=555,x4=5555,x5=55555时,fx=0为最小值。如果使用穷举法,通过循环的方法找到这5个变量,估计会很费时的,我就不做测试了。下面我们看一下遗传算法的运行情况。


# 定义适应度函数
> f<-function(x){} # 代码省略

# 运行遗传算法
> m <- mcga(  popsize=200, 
+             chsize=5, 
+             minval=0.0, 
+             maxval=999999, 
+             maxiter=2500, 
+             crossprob=1.0, 
+             mutateprob=0.01, 
+             evalFunc=f)

# 最优化的个体结果
> print(m$population[1,])
[1]  5.000317    54.997099   554.999873  5555.003120 55554.218695

# 执行时间
> m$costs[1]
[1] 3.6104556

我们得到的最优化的结果为x1=5.000317, x2=54.997099, x3=554.999873, x4=5555.003120, x5=55554.218695,和我们预期的结果非常接近,而且耗时只有3.6秒。这个结果是非常令人满意地,不是么!如果使用穷举法,时间复杂度为O(n^5),估计没有5分钟肯定算不出来。

当然,算法执行时间和精度,都是通过参数进行配置的。如果增大个体数目或循环次数,一方面会增加算法的计算时间,另一方面结果也可能变得更精准。所以,在实际的使用过程中,需要根据一定的经验调整这几个参数。

3.2 genalg包

我们使用genalg包的rbga()函数,也可以实现多变量的遗传算法。

genalg包不仅实现了遗传算法,还提供了遗传算法的数据可视化,给用户更直观的角度理解算法。默认图显示的最小和平均评价值,表示遗传算法的计算进度。直方图显出了基因选择的频率,即基因在当前个体中被选择的次数。参数图表示评价函数和变量值,非常方便地看到评价函数和变量值的相关关系。

首先,安装genalg包。


> install.packages("genalg")
> library(genalg)

查看一下rbga()函数的定义。


> rbga(stringMin=c(), stringMax=c(),
     suggestions=NULL,
     popSize=200, iters=100,
     mutationChance=NA,
     elitism=NA,
     monitorFunc=NULL, evalFunc=NULL,
     showSettings=FALSE, verbose=FALSE)

参数说明:

  • stringMin,设置每个基因的最小值
  • stringMax,设置每个基因的最大值
  • suggestions,建议染色体的可选列表
  • popSize,个体数量,即染色体数目,默认为200
  • iters,迭代次数,默认为100
  • mutationChance,突变机会,默认为1/(size+1),它影响收敛速度和搜索空间的探测,低机率导致更快收敛,高机率增加了搜索空间的跨度。
  • elitism,精英数量,默认为20%,直接复制到下一代的染色体数目
  • monitorFunc,监控函数,每产生一代后运行
  • evalFunc,适应度函数,用于给个体进行评价
  • showSettings,打印设置,默认为false
  • verbose,打印算法运行日志,默认为false

接下来,我们给定一个优化的问题,通过rbga()函数,计算最优化的解。

题目2:设fx=abs(x1-sqrt(exp(1)))+abs(x2-log(pi)),计算fx的最小值,其中x1,x2为2个不同的变量。

从直观上看,如果想得到fx的最小值,其实当x1=sqrt(exp(1))=1.648721, x2=log(pi)=1.14473时,fx=0为最小值。同样地,如果使用穷举法,通过循环的方法找到这2个变量,估计会很费时的,我也不做测试了。下面我们看一下rbga()函数的遗传算法的运行情况。


# 定义适应度函数
> f<-function(x){}  #代码省略

# 定义监控函数
> monitor <- function(obj){}  #代码省略

# 运行遗传算法
> m2 = rbga(c(1,1),
+           c(3,3),
+           popSize=100,
+           iters=1000,
+           evalFunc=f,
+           mutationChance=0.01,
+           verbose=TRUE,
+           monitorFunc=monitor
+           )

Testing the sanity of parameters...
Not showing GA settings...
Starting with random values in the given domains...
Starting iteration 1
Calucating evaluation values... ....................................................... done.
Sending current state to rgba.monitor()...
Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 2 mutations applied
Starting iteration 2
Calucating evaluation values... ...................... done.
Sending current state to rgba.monitor()...
Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 4 mutations applied
Starting iteration 3
Calucating evaluation values... ....................... done.

# 省略输出...

程序运行截图

rbga-run

需要注意的是,程序在要命令行界面运行,如果在RStudio中运行,会出现下面的错误提示。


Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 1 mutations applied
Starting iteration 10 
Calucating evaluation values... .......................... done.
Sending current state to rgba.monitor()...
Error in get(name, envir = asNamespace(pkg), inherits = FALSE) : 
  object 'rversion' not found
Graphics error: Error in get(name, envir = asNamespace(pkg), inherits = FALSE) : 
  object 'rversion' not found

我们迭代1000次后,查看计算结果。


# 计算结果
> m2$population[1,]
[1] 1.650571 1.145784

我们得到的最优化的结果为x1=1.650571, x2=1.145784,非常接近最终的结果。另外,我们可以通过genalg包的可视化功能,看到迭代过程的每次的计算结果。下面截图分为对应1次迭代,10次迭代,200次迭代和1000次迭代的计算结果。从图中可以看出,随着迭代次数的增加,优选出的结果集变得越来越少,而且越来越精准。

rbga-all

默认图输出,用于描述遗传过程的进展,X轴为迭代次数,Y轴评价值,评价值越接近于0越好。在1000迭代1000次后,基本找到了精确的结果。


> plot(m2)

rbga-ev

直方图输出,用于描述对染色体的基因选择频率,即一个基因在染色体中的当前人口被选择的次数。当x1在1.65区域时,被选择超过80次;当x2在1.146区域时,被选择超过了80次。通过直方图,我们可以理解为更优秀的基因被留给了后代。


> plot(m2,type='hist')

rbga-hist

参数图输出,用于描述评价函数和变量的值的相关关系。对于x1,评价值越小,变量值越准确,但相关关系不明显。对于x2,看不出相关关系。


> plot(m2,type='vars')

rbga-vars

对比mcga包和genalg包,mcga包适合计算大范围取值空间的最优解,而用genalg包对于大范围取值空间的计算就表现就不太好了。从另一个方面讲,genalg包提供了可视化工具,可以让我们直观的看遗传算法的收敛过程,对于算法的理解和调优是非常有帮助的。

在掌握了遗传算法后,我们就可以快度地处理一些优化的问题了,比如接下来我会介绍的金融回测系统的参数寻优方案。让我们远离穷举法,珍惜CPU的每一秒时间。

参考文章
http://zh.wikipedia.org/zh/遗传算法

转载请注明出处:
http://blog.fens.me/algorithm-ga-r/

打赏作者

PageRank算法R语言实现

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/algorithm-pagerank-r/

pagerank-r

前言

Google搜索,早已成为我每天必用的工具,无数次惊叹它搜索结果的准确性。同时,我也在做Google的SEO,推广自己的博客。经过几个月尝试,我的博客PR到2了,外链也有几万个了。总结下来,还是感叹PageRank的神奇!

改变世界的算法,PageRank!

目录

  1. PageRank算法介绍
  2. PageRank算法原理
  3. PageRank算法的R语言实现

1. PageRank算法介绍

PageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和 Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。

PageRank让链接来”投票”

一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

简单一句话概括:从许多优质的网页链接过来的网页,必定还是优质网页。

PageRank的计算基于以下两个基本假设:

  • 数量假设:如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要
  • 质量假设:指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A,则页面A越重要。

要提高PageRank有3个要点:

  • 反向链接数
  • 反向链接是否来自PageRank较高的页面
  • 反向链接源页面的链接数

2. PageRank算法原理

在初始阶段:网页通过链接关系构建起有向图,每个页面设置相同的PageRank值,通过若干轮的计算,会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行,网页当前的PageRank值会不断得到更新。

在一轮更新页面PageRank得分的计算中,每个页面将其当前的PageRank值平均分配到本页面包含的出链上,这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值,就完成了一轮PageRank计算。

1). 算法原理

PageRank算法建立在随机冲浪者模型上,其基本思想是:网页的重要性排序是由网页间的链接关系所决定的,算法是依靠网页间的链接结构来评价每个页面的等级和重要性,一个网页的PR值不仅考虑指向它的链接网页数,还有指向’指向它的网页的其他网页本身的重要性。

PageRank具有两大特性:

  • PR值的传递性:网页A指向网页B时,A的PR值也部分传递给B
  • 重要性的传递性:一个重要网页比一个不重要网页传递的权重要多

2). 计算公式:

pagerank-formula

  • PR(pi): pi页面的PageRank值
  • n: 所有页面的数量
  • pi: 不同的网页p1,p2,p3
  • M(i): pi链入网页的集合
  • L(j): pj链出网页的数量
  • d:阻尼系数, 任意时刻,用户到达某页面后并继续向后浏览的概率。
    (1-d=0.15) :表示用户停止点击,随机跳到新URL的概率
    取值范围: 0 < d ≤ 1, Google设为0.85

3). 构造实例:以4个页面的数据为例

pagerank-sample

图片说明:

  • ID=1的页面链向2,3,4页面,所以一个用户从ID=1的页面跳转到2,3,4的概率各为1/3
  • ID=2的页面链向3,4页面,所以一个用户从ID=2的页面跳转到3,4的概率各为1/2
  • ID=3的页面链向4页面,所以一个用户从ID=3的页面跳转到4的概率各为1
  • ID=4的页面链向2页面,所以一个用户从ID=4的页面跳转到2的概率各为1

构造邻接表:


链接源页面     链接目标页面
    1             2,3,4
    2             3,4
    3             4
    4             2

构造邻接矩阵(方阵):

  • 列:源页面
  • 行:目标页面

     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

转换为概率矩阵(转移矩阵)


     [,1] [,2] [,3] [,4]
[1,] 0      0    0    0
[2,] 1/3    0    0    1
[3,] 1/3  1/2    0    0
[4,] 1/3  1/2    1    0

通过链接关系,我们就构造出了“转移矩阵”。

3. R语言单机算法实现

创建数据文件:page.csv


1,2
1,3
1,4
2,3
2,4
3,4
4,2

分别用下面3种方式实现PageRank:

  • 未考虑阻尼系统的情况
  • 包括考虑阻尼系统的情况
  • 直接用R的特征值计算函数

1). 未考虑阻尼系统的情况

R语言实现


#构建邻接矩阵
adjacencyMatrix<-function(pages){
  n<-max(apply(pages,2,max))
  A <- matrix(0,n,n)
  for(i in 1:nrow(pages)) A[pages[i,]$dist,pages[i,]$src]<-1
  A
}

#变换概率矩阵
probabilityMatrix<-function(G){
  cs <- colSums(G)
  cs[cs==0] <- 1
  n <- nrow(G)
  A <- matrix(0,nrow(G),ncol(G))
  for (i in 1:n) A[i,] <- A[i,] + G[i,]/cs
  A
}

#递归计算矩阵特征值
eigenMatrix<-function(G,iter=100){
  iter<-10
  n<-nrow(G)
  x <- rep(1,n)
  for (i in 1:iter) x <- G %*% x
  x/sum(x)
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-probabilityMatrix(A);G
          [,1] [,2] [,3] [,4]
[1,] 0.0000000  0.0    0    0
[2,] 0.3333333  0.0    0    1
[3,] 0.3333333  0.5    0    0
[4,] 0.3333333  0.5    1    0

> q<-eigenMatrix(G,100);q
          [,1]
[1,] 0.0000000
[2,] 0.4036458
[3,] 0.1979167
[4,] 0.3984375

结果解读:

  • ID=1的页面,PR值是0,因为没有指向ID=1的页面
  • ID=2的页面,PR值是0.4,权重最高,因为1和4都指向2,4权重较高,并且4只有一个链接指向到2,权重传递没有损失
  • ID=3的页面,PR值是0.19,虽有1和2的指向了3,但是1和2还指向的其他页面,权重被分散了,所以ID=3的页面PR并不高
  • ID=4的页面,PR值是0.39,权重很高,因为被1,2,3都指向了

从上面的结果,我们发现ID=1的页面,PR值是0,那么ID=1的页,就不能向其他页面输出权重了,计算就会不合理!所以,增加d阻尼系数,修正没有链接指向的页面,保证页面的最小PR值>0,。

2). 包括考虑阻尼系统的情况

增加函数:dProbabilityMatrix



#变换概率矩阵,考虑d的情况
dProbabilityMatrix<-function(G,d=0.85){
  cs <- colSums(G)
  cs[cs==0] <- 1
  n <- nrow(G)
  delta <- (1-d)/n
  A <- matrix(delta,nrow(G),ncol(G))
  for (i in 1:n) A[i,] <- A[i,] + d*G[i,]/cs
  A
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-dProbabilityMatrix(A);G
          [,1]   [,2]   [,3]   [,4]
[1,] 0.0375000 0.0375 0.0375 0.0375
[2,] 0.3208333 0.0375 0.0375 0.8875
[3,] 0.3208333 0.4625 0.0375 0.0375
[4,] 0.3208333 0.4625 0.8875 0.0375

> q<-eigenMatrix(G,100);q
          [,1]
[1,] 0.0375000
[2,] 0.3738930
[3,] 0.2063759
[4,] 0.3822311

增加阻尼系数后,ID=1的页面,就有值了PR(1)=(1-d)/n=(1-0.85)/4=0.0375,即无外链页面的最小值。

3). 直接用R的特征值计算函数

增加函数:calcEigenMatrix


#直接计算矩阵特征值
calcEigenMatrix<-function(G){
  x <- Re(eigen(G)$vectors[,1])
  x/sum(x)
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-dProbabilityMatrix(A);G
          [,1]   [,2]   [,3]   [,4]
[1,] 0.0375000 0.0375 0.0375 0.0375
[2,] 0.3208333 0.0375 0.0375 0.8875
[3,] 0.3208333 0.4625 0.0375 0.0375
[4,] 0.3208333 0.4625 0.8875 0.0375

> q<-calcEigenMatrix(G);q
[1] 0.0375000 0.3732476 0.2067552 0.3824972

直接计算矩阵特征值,可以有效地减少的循环的操作,提高程序运行效率。

在了解PageRank的原理后,使用R语言构建PageRank模型,是非常容易的。实际应用中,我们也愿意用比较简单的方式建模,验证后,再用其他语言语言去企业应用!

下一篇文章,将介绍如何用MapReduce分步式算法来实现PageRank模型,PageRank算法并行实现

参考文章

转载请注明出处:
http://blog.fens.me/algorithm-pagerank-r/

打赏作者