算法

机器学习常见算法分类汇总

作者:王萌

机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里总结了一下常见的机器学习算法,以供您在工作和学习中参考。

机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。

学习方式

根据数据类型的不同,对一个问题的建模有不同的方式。在机器学习或者人工智能领域,人们首先会考虑算法的学习方式。在机器学习领域,有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法,这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。

监督式学习:

机器学习常见算法分类汇总

图像处理算法——图像常用格式

基本图像有主要的文件格式有BMP,JPG(JPEG),JPEG2000,PNG,GIF,TIFF,这些是我有过了解和有一定认识的就着重介绍,此外还有还有很多其他图像格式例如PSD,SWF,SVG等虽说也是用的很多的图像格式,但由于在我的工作中涉及不到或者涉及很少,这里就不谈了。

一、BMP格式

BMP是英文Bitmap(位图)的简写,它是Windows操作系统中的标准图像文件格式,能够被多种Windows应用程序所支持。随着Windows操作系统的流行与丰富的Windows应用程序的开发,BMP位图格式理所当然地被广泛应用。这种格式的特点是包含的图像信息较丰富,几乎不进行压缩,但由此导致了它与生俱生来的缺点--占用磁盘空间过大。

二、JPEG格式

基本图形的光栅化算法

如何在指定的输出设备上根据坐标描述构造基本二维几何图形(点、直线、圆、椭圆、多边形域、字符串及其相关属性等)。

图形生成的概念

图形的生成:是在指定的输出设备上,根据坐标描述构造二维几何图形。
图形的扫描转换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。

直线段的扫描转换

直线的绘制要求

(1)直线要直;
(2)直线的端点要准确,无定向性无断裂;
(3)直线的亮度、色泽要均匀;
(4)画线的速度要快;
(5)具有不同的色泽、亮度、线型等。
解决的问题:给定直线两端点P0(x0,y0)和P1(x1,y1),画出该直线。

逐点比较法:

数值微分法(DDA法):
增量算法
直观、易实现
不利于用硬件实现
x(i+1) = x(i) + 1
y(i+1) = y(i) + k

中点Bresenhan算法:

迁移学习:经典算法解析

一. 了解迁移学习

迁移学习(Transfer Learning)目标是将从一个环境中学到的知识用来帮助新环境中的学习任务。

入门推荐一篇公认的比较好的 【Survey】: A Survey on Transfer Learning,Sinno JialinPan, Qiang Yang,IEEE Trans

另外,戴文渊的硕士学位论文也可以看一下:基于实例和特征的迁移学习算法研究

Survey 作者归纳了 Transfer Learning 相关的知识域,有必要了解一下这些名词:

● Learning学习 - learning to learn
● 终身学习 - life-long learning
● 知识转移 - knowledge transfer
● 归纳迁移 - inductive transfer

人脸识别技术主要算法原理

主流的人脸识别技术基本上可以归结为三类,即:基于几何特征的方法、基于模板的方法和基于模型的方法。

1. 基于几何特征的方法是最早、最传统的方法,通常需要和其他算法结合才能有比较好的效果;
2. 基于模板的方法可以分为基于相关匹配的方法、特征脸方法、线性判别分析方法、奇异值分解方法、神经网络方法、动态连接匹配方法等。
3. 基于模型的方法则有基于隐马尔柯夫模型,主动形状模型和主动外观模型的方法等。

1. 基于几何特征的方法

人脸由眼睛、鼻子、嘴巴、下巴等部件构成,正因为这些部件的形状、大小和结构上的各种差异才使得世界上每个人脸千差万别,因此对这些部件的形状和结构关系的几何描述,可以做为人脸识别的重要特征。几何特征最早是用于人脸侧面轮廓的描述与识别,首先根据侧面轮廓曲线确定若干显著点,并由这些显著点导出一组用于识别的特征度量如距离、角度等。Jia 等由正面灰度图中线附近的积分投影模拟侧面轮廓图是一种很有新意的方法。

采用几何特征进行正面人脸识别一般是通过提取人眼、口、鼻等重要特征点的位置和眼睛等重要器官的几何形状作为分类特征,但Roder对几何特征提取的精确性进行了实验性的研究,结果不容乐观。

五大常用算法之——分支限界法

一、基本描述

类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

(1)分支搜索算法

所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。

选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。
1.FIFO搜索
2.LIFO搜索
3.优先队列式搜索

(2)分支限界搜索算法

二、分支限界法的一般过程

五大常用算法之——回溯法

1、概念

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

2、基本思想

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。

若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

3、用回溯法解题的一般步骤:

光线追踪算法—镜面反射

1.镜面-镜面光线传输计算

只涉及主光线计算而渲染出来的图像无法真实表现现实中的光线照射,通过增加能够反射光线的材质,进行空间中具有反射材质的对象之间的反射光线的追踪,可以更好地体现真实感。

2.光线镜面反射的计算

当光线与包含反射材质的物体进行碰撞后,计算反射方向,追踪计算得到的反射光线即可,因为光线可能在空间中无限的反射下去,为了避免这种情况,一般定义一个最大的追踪深度。根据反射光线与空间的交互可能存在的四种情况,分别返回相应的结果:

1. 反射光线没有碰撞到任何物体,直接返回背景颜色
2. 反射光线碰撞到漫反射材质对象,则返回漫反射材质对象上该点处的颜色
3. 反射光线碰撞到镜面反射材质对象,则继续追踪碰撞点产生的光线,将追踪的结果返回
4. 光线与光源碰撞,直接返回光源的颜色

3.一个典型的渲染结果

在场景中,一个水平面上放置两个球体,红色球体拥有镜面反射材质,另一个则为漫反射材质,渲染结果如图所示:

五大常用算法之——贪心算法

一、基本概念:

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路:

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解,得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题

贪心策略适用的前提是:局部最优策略能导致产生全局最优解。

实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

光线追踪算法—阴影绘制

1.阴影的作用

阴影效果在真实感图像生成中提供给图像更多的真实感,并且能够为场景提供某些定性分析,如光照的位置、光照的范围等信息。

阴影可以看为光源看不到的地方,即从光源往各个方向发送光线,则光线无法照射到的区域则为阴影。
在光线追踪中,从观察光线与物体的碰撞点向光源引一条光线,光线方向指向光源,若该光线在到达光源之前碰撞到某些物体,则该点位于阴影中。

2.阴影的生成实现

阴影的生成如同上述所讲一样,只需在碰撞点往光源方向引一条光线,然后判断光线是否与物体相交,然后根据相交与否产生相应的颜色。

具体的代码如下(c++实现):

Color Phong::Shade(const ShadeRecord& shade_rec) const
{
  Vector3f out_dir = -shade_rec.ray_.dir_;
  const std::vector<LightPtr>& lights = shade_rec.world_.lights_;
同步内容
--电子创新网--
粤ICP备12070055号