apply函数族

很多开发者都结合C++和R进行R包的开发,这也是Rcpp能够下载量第一的原因了。哎,要么说R是面向用户的呢?开发者去调试C++代码在R中优雅地运行,可见开发真的不是一件易事呀!

之前一直认为for循环并不算慢,现在终于有了觉悟,虽然apply函数族不能完全代替for,可这也是用C++写出来的函数呀!

apply function family

参考文章见:http://blog.fens.me/r-apply/

Genetic Algorithm

Genetic algorithm

遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

遗传算法的多变异性和遗传算子的设计能够有效时遗传算法跳出局部解而找到全局最佳解,并且合适的遗传算子选择设计能够缩短算法运行时间,使算法更加有效。遗传算法的局限性也相当明显,遗传算法最大的局限就在于算法自身的编码,对于一些问题来说遗传算法的编码过程很复杂,而且遗传算子的设计也是必须要参考到很多现实问题因素。R语言有遗传算法的包,一共两个。一个包叫作mcga包;另一个包叫做genalg包,下面我们分别使用两个包来求解。

一个非常有趣的故事:内存中的进化

Terminology

  • 基因型(genotype):性状染色体的内部表现;

  • 表现型(phenotype):染色体决定的性状的外部表现,或者说,根据基因型形成的个体的外部表现;

  • 进化(evolution):种群逐渐适应生存环境,品质不断得到改良。生物的进化是以种群的形式进行的。

  • 适应度(fitness):度量某个物种对于生存环境的适应程度。

  • 选择(selection):以一定的概率从种群中选择若干个个体。一般,选择过程是一种基于适应度的优胜劣汰的过程。

  • 复制(reproduction):细胞分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新细胞就继承了旧细胞的基因。

  • 交叉(crossover):两个染色体的某一相同位置处DNA被切断,前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交;

  • 变异(mutation):复制时可能(很小的概率)产生某些复制差错,变异产生新的染色体,表现出新的性状。

  • 编码(coding):DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

  • 解码(decoding):基因型到表现型的映射。

  • 个体(individual):指染色体带有特征的实体;

  • 种群(population):个体的集合,该集合内个体数称为种群的大小。

遗传算法中每一条染色体,对应着遗传算法的一个解决方案,一般我们用适应性函数(fitness function)来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。可以这样想象,这个多维曲面里面有数不清的“山峰”,而这些山峰所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的,那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰,而不是陷落在一些小山峰。(另外,值得注意的是遗传算法不一定要找“最高的山峰”,如果问题的适应度评价越小越好的话,那么全局最优解就是函数的最小值,对应的,遗传算法所要找的就是“最深的谷底”。)

不管袋鼠的黑白肥瘦高矮、不管它们喜欢吃什么食物,我们由始至终都只关心一件事情:袋鼠在哪里

把那些总是原地踏步和爱走下坡路的袋鼠射杀,这就是遗传算法的精粹!

Decision Trees and Rules

Decision trees

第三章依旧是分类,依旧很强大。决策树(decision trees)利用树形结构(tree structure)对特征和潜在结果之间的关系建立模型。比如要考虑工作机会从根节点(root nodes)开始,然后遍历决策节点(decision nodes),决策节点要求基于工作的属性做出选择,,这些选择通过用只是决策潜在结果的分枝(branches)来划分数据,可以用结果yes或no来描述。尽管在默写案例中,可能不只两种结果,在这种情况下,可以做出最终的决策,决策树在叶节点(leaf note, 也称终端节点)终止,业绩点表示因一系列决策而采取的行动。对于预测模型,叶节点提供了决策树中给定系列事件的预期结果。

decision trees

Divide and conquer

决策树的建立采用一种称为递归划分(recursive partitioning)的探索法。这种方法也通常称为分而治之(divide and conquer),因为它将数据分解为子集,然后反复分解成更小的子集,以此类推,直到当算法决定数据内的子集足够均匀或者另一种停止准则已经满足是,该过程才停止。

假设你受雇于好莱坞电影制片厂,拥有可以邀请到许多一线明星的能力。因为业务繁忙你的桌上常常堆放着一沓剧本。你决定研究一个决策树算法来预测一部有潜力的电影是否会落入:

  • Critical Success
  • Mainstream Hit
  • Box Office Bust

estimate buget

Particle Swarm Optimization, PSO

“Bees don’t swarm in a mango grove for nothing. Where can you see a wisp of smoke without a fire?”

– Hla Stavhana

PSO

粒子群优化Particle Swarm Optimization, PSO),又称微粒群算法,是由J. Kennedy和R. C. Eberhart等于1995年开发的一种演化计算技术,来源于对一个简化社会模型的模拟。其中“群(swarm)”来源于微粒群匹配M. M. Millonas在开发应用于人工生命(artificial life)的模型时所提出的群体智能的5个基本原则。“粒子(particle)”是一个折衷的选择,因为既需要将群体中的成员描述为没有质量、没有体积的,同时也需要描述它的速度和加速状态。

PSO算法最初是为了图形化的模拟鸟群优美而不可预测的运动。而通过对动物社会行为的观察,发现在群体中对信息的社会共享提供一个演化的优势,并以此作为开发算法的基础。通过加入近邻的速度匹配、并考虑了多维搜索和根据距离的加速,形成了PSO的最初版本。之后引入了惯性权重*w*来更好的控制开发(exploitation)和探索(exploration),形成了标准版本。

PSO算法采用实数求解,不要求目标函数可微,而且模型参数的数量还行,原理有趣,易于实现,可以解决大规模、非线性、不可微和多峰值的复杂优化问题。该算法和其它全局优化算法一样可能陷入局部最优,后期收敛速度较慢,但是这个算法的思想还是很有意思的,非常值得学习。

Principle

鸟群的运动给了J. Kennedy和R. C. Eberhart灵感。假设每只鸟的基本情况都是一样的,包括飞行速度(含区间)的调整、好的区域的趋向性以及经验和学习能力。它们唯一不同的地方就在于一开始在D维空间中分布的情况不同,因此可以简化为没有体积的“粒子”,在搜索空间中以一定的速度飞行,这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi = (xi1, xi2, ..., xiD),它经历过的最好位置(有最好的适应值)记为Pi = (pi1, pi2, ..., piD),也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示,即Pg,也称为gbest。微粒i的速度用Vi = (vi1, vi2, ..., viD)表示。对每一代,它的第d+1维(1 ≤ d+1 ≤ D)根据如下方程进行变化:

1
2
       vid+1 = w∙vid+c1∙rand()∙(pid-xid)+c2∙Rand()∙(pgd-xid)  
       xid+1 = xid+vid