Tag Archives: 算法

技术面试要了解的算法和数据结构知识

目录

  • 在线练习
  • 在线编程面试
  • 数据结构
  • 算法
  • 贪心算法
  • 位运算
  • 复杂度分析
  • 视频教程
  • 面试宝典
  • 计算机科学资讯
  • 文件结构

在线练习

在线编程面试

数据结构

链表

  • 链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。
  • 单链表 :每个节点仅指向下一个节点,最后一个节点指向空(null)。
  • 双链表 :每个节点有两个指针p,n。p指向前一个节点,n指向下一个节点;最后一个节点指向空。
  • 循环链表 :每个节点指向下一个节点,最后一个节点指向第一个节点。
  • 时间复杂度:
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 栈是一个元素集合,支持两个基本操作:push用于将元素压入栈,pop用于删除栈顶元素。
  • 后进先出的数据结构(Last In First Out, LIFO)
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

队列

  • 队列是一个元素集合,支持两种基本操作:enqueue 用于添加一个元素到队列,dequeue 用于删除队列中的一个元素。
  • 先进先出的数据结构(First In First Out, FIFO)。
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 树是无向、联通的无环图。

二叉树

  • 二叉树是一个树形数据结构,每个节点最多可以有两个子节点,称为左子节点和右子节点。
  • 满二叉树(Full Tree) :二叉树中的每个节点有 0 或者 2 个子节点。

大数据

  • 完美二叉树(Perfect Binary) :二叉树中的每个节点有两个子节点,并且所有的叶子节点的深度是一样的。
  • 完全二叉树 :二叉树中除最后一层外其他各层的节点数均达到最大值,最后一层的节点都连续集中在最左边。

二叉查找树

  • 二叉查找树(BST)是一种二叉树。其任何节点的值都大于等于左子树中的值,小于等于右子树中的值。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))

大数据

字典树

  • 字典树,又称为基数树或前缀树,是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值,而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀,根节点则是空字符串。

大数据

树状数组

  • 树状数组,又称为二进制索引树(Binary Indexed Tree,BIT),其概念上是树,但以数组实现。数组中的下标代表树中的节点,每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和,在整个树更新的过程中,这些计算的值也同样会被更新。
  • 时间复杂度
    • 区间求和:O(log(n))
    • 更新:O(log(n))

大数据

线段树

  • 线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
  • 时间复杂度
    • 区间查找:O(log(n))
    • 更新:O(log(n))

大数据

  • 堆是一种基于树的满足某些特性的数据结构:整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中,父节点的键值永远大于等于所有子节点的键值,根节点的键值是最大的。最小堆中,父节点的键值永远小于等于所有子节点的键值,根节点的键值是最小的。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))
    • 删除最大值/最小值:O(1)

大数据

哈希

  • 哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值,则发生了冲突。
  • Hash Maphash map  是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标,从而便于指定值的查找。
  • 冲突解决
    • 链地址法( Separate Chaining :在链地址法中,每个桶(bucket)是相互独立的,每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间(常量)与遍历列表元素的时间之和。
    • 开放地址法( Open Addressing :在开放地址方法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

大数据

  • 图是G =(V,E)的有序对,其包括顶点或节点的集合 V 以及边或弧的集合E,其中E包括了两个来自V的元素(即边与两个顶点相关联 ,并且该关联为这两个顶点的无序对)。
  • 无向图 :图的邻接矩阵是对称的,因此如果存在节点 u 到节点 v 的边,那节点 v 到节点 u 的边也一定存在。
  • 有向图 :图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。

大数据

算法

排序

快速排序

  • 稳定:否
  • 时间复杂度
    • 最优:O(nlog(n))
    • 最差:O(n^2)
    • 平均:O(nlog(n))

大数据

合并排序

  • 合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。
  • 稳定:是
  • 时间复杂度:
    • 最优:O(nlog(n))
    • 最差:O(nlog(n))
    • 平均:O(nlog(n))

桶排序

  • 桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序,或递归调用桶排序。
  • 时间复杂度
    • 最优:Ω(n + k)
    • 最差: O(n^2)
    • 平均:Θ(n + k)

大数据

基数排序

  • 基数排序类似于桶排序,将元素分发到一定数目的桶中。不同的是,基数排序在分割元素之后没有让每个桶单独进行排序,而是直接做了合并操作。
  • 时间复杂度
    • 最优:Ω(nk)
    • 最差: O(nk)
    • 平均:Θ(nk)

图算法

深度优先 搜索

  • 深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

广度优先 搜索

  • 广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

拓扑排序

  • 拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边,u 的下标先于 v。
  • 时间复杂度:O(|V| + |E|)

Dijkstra算法

  • Dijkstra 算法是一种在有向图中查找单源最短路径的算法。
  • 时间复杂度:O(|V|^2)

大数据

Bellman-Ford算法

  • Bellman-Ford  是一种在带权图中查找单一源点到其他节点最短路径的算法。
  • 虽然时间复杂度大于 Dijkstra 算法,但它可以处理包含了负值边的图。
  • 时间复杂度:
    • 最优:O(|E|)
    • 最差:O(|V||E|)

大数据

Floyd-Warshall 算法

  • Floyd-Warshall  算法是一种在无环带权图中寻找任意节点间最短路径的算法。
  • 该算法执行一次即可找到所有节点间的最短路径(路径权重和)。
  • 时间复杂度:
    • 最优:O(|V|^3)
    • 最差:O(|V|^3)
    • 平均:O(|V|^3)

最小生成树算法

  • 最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之,最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
  • 时间复杂度:O(|V|^2)

Kruskal 算法

  • Kruskal  算法也是一个计算最小生成树的贪心算法,但在 Kruskal 算法中,图不一定是连通的。
  • 时间复杂度:O(|E|log|V|)

贪心算法

  • 贪心算法总是做出在当前看来最优的选择,并希望最后整体也是最优的。
  • 使用贪心算法可以解决的问题必须具有如下两种特性:
    • 最优子结构
      • 问题的最优解包含其子问题的最优解。
    • 贪心选择
      • 每一步的贪心选择可以得到问题的整体最优解。
  • 实例-硬币选择问题
  • 给定期望的硬币总和为 V 分,以及 n 种硬币,即类型是 i 的硬币共有 coinValue[i] 分,i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个,求解为使和为 V 分最少需要多少硬币?
  • 硬币:便士(1美分),镍(5美分),一角(10美分),四分之一(25美分)。
  • 假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币,然后从 V 中减掉该硬币的值,如此重复进行。
    • V = 41 | 使用了0个硬币
    • V = 16 | 使用了1个硬币(41 – 25 = 16)
    • V = 6 | 使用了2个硬币(16 – 10 = 6)
    • V = 1 | 使用了3个硬币(6 – 5 = 1)
    • V = 0 | 使用了4个硬币(1 – 1 = 0)

运算

  • 位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
  • 测试第 k 位:s & (1 << k);
  • 设置第k位:s |= (1 << k);
  • 关闭第k位:s &= ~(1 << k);
  • 切换第k位:s ^= (1 << k);
  • 乘以2n:s << n;
  • 除以2n:s >> n;
  • 交集:s & t;
  • 并集:s | t;
  • 减法:s & ~t;
  • 提取最小非0位:s & (-s);
  • 提取最小0位:~s & (s + 1);
  • 交换值:x ^= y; y ^= x; x ^= y;

运行时分析

大 O 表示

  • 大 O 表示用于表示某个算法的上界,用于描述最坏的情况。

大数据

小 O 表示

  • 小 O 表示用于描述某个算法的渐进上界,二者逐渐趋近。

大 Ω 表示

  • 大 Ω 表示用于描述某个算法的渐进下界。

大数据

小 ω 表示

  • 小 ω 表示用于描述某个算法的渐进下界,二者逐渐趋近。

Theta Θ 表示

  • Theta Θ 表示用于描述某个算法的确界,包括最小上界和最大下界。

大数据

视频教程

面试宝典

 

技术面试要了解的算法和数据结构知识

机器学习工程师必知的十大算法

毫无疑问,机器学习/人工智能的子领域在过去几年越来越受欢迎。目前大数据在科技行业已经炙手可热,而基于大量数据来进行预测或者得出建议的机器学习无疑是非常强大的。一些最常见的机器学习例子,比如Netflix的算法可以根据你以前看过的电影来进行电影推荐,而Amazon的算法则可以根据你以前买过的书来推荐书籍。

所以如果你想了解更多有关机器学习的内容,那么你该如何入门?对于我来说,我的入门课程是我在哥本哈根出国留学时参加的人工智能课。当时我的讲师是丹麦技术大学(Technical University of Denmark)的应用数学和计算机科学的全职教授,他的研究方向是逻辑与人工智能,侧重于使用逻辑学来对人性化的规划、推理和解决问题进行建模。这个课程包括对理论/核心概念的讨论和自己动手解决问题。我们使用的教材是AI经典之一:Peter Norvig的Artificial Intelligence—A Modern Approach(中文译本:《人工智能:一种现代的方法》),这本书主要讲了智能体、搜索解决问题、对抗搜索、概率论、多智能体系统、社会AI和AI的哲学/伦理/未来等等。在课程结束时,我们三个人的团队实现了一个简单的编程项目,也就是基于搜索的智能体解决虚拟环境中的运输任务问题。

在那门课程上我已经学到了很多知识,并决定继续学习相关的课题。在过去的几个星期里,我在旧金山参加了多次相关的技术讲座,涉及到深度学习、神经网络和数据结构,并且参加了一个有很多该领域的知名专家学者参加的机器学习会议。最重要的是,我在6月初参加了Udacity上的Intro to Machine Learning(机器学习入门)在线课程,前几天才完成。在这篇文章中,我想分享一下我从课程中学到的一些最常用的机器学习算法。

机器学习算法可以分为三大类:监督学习、无监督学习和强化学习。监督学习可用于一个特定的数据集(训练集)具有某一属性(标签),但是其他数据没有标签或者需要预测标签的情况。无监督学习可用于给定的没有标签的数据集(数据不是预分配好的),目的就是要找出数据间的潜在关系。强化学习位于这两者之间,每次预测都有一定形式的反馈,但是没有精确的标签或者错误信息。因为这是一个介绍课程,我没有学习过强化学习的相关内容,但是我希望以下10个关于监督学习和无监督学习的算法足以让你感兴趣。

监督学习

1.决策树(Decision Trees)

决策树是一个决策支持工具,它使用树形图或者决策模型以及可能性序列,包括偶然事件的结果、资源成本和效用。下图是其基本原理:

从业务决策的角度来看,决策树是人们必须了解的最少的是/否问题,这样才能评估大多数时候做出正确决策的概率。作为一种方法,它允许你以结构化和系统化的方式来解决问题,从而得出合乎逻辑的结论。

2.朴素贝叶斯分类(Naive Bayesian classification)

朴素贝叶斯分类器是一类简单的概率分类器,它基于贝叶斯定理和特征间的强大的(朴素的)独立假设。图中是贝叶斯公式,其中P(A|B)是后验概率,P(B|A)是似然,P(A)是类先验概率,P(B)是预测先验概率。

一些应用例子:

  • 判断垃圾邮件
  • 对新闻的类别进行分类,比如科技、政治、运动
  • 判断文本表达的感情是积极的还是消极的
  • 人脸识别

3.最小二乘法(Ordinary Least Squares Regression)

如果你懂统计学的话,你可能以前听说过线性回归。最小二乘法是一种计算线性回归的方法。你可以将线性回归看做通过一组点来拟合一条直线。实现这个有很多种方法,“最小二乘法”就像这样:你可以画一条直线,然后对于每一个数据点,计算每个点到直线的垂直距离,然后把它们加起来,那么最后得到的拟合直线就是距离和尽可能小的直线。

线性指的是你用来拟合数据的模型,而最小二乘法指的是你最小化的误差度量。

4.逻辑回归(Logistic Regression)

逻辑回归是一个强大的统计学方法,它可以用一个或多个解释变量来表示一个二项式结果。它通过使用逻辑函数来估计概率,从而衡量类别依赖变量和一个或多个独立变量之间的关系,后者服从累计逻辑分布。

总的来说,逻辑回归可以用于以下几个真实应用场景:

  • 信用评分
  • 计算营销活动的成功率
  • 预测某个产品的收入
  • 特定的某一天是否会发生地震

5.支持向量机(Support Vector Machine,SVM)

SVM是二进制分类算法。给定N维坐标下两种类型的点,SVM生成(N-1)维的超平面来将这些点分成两组。假设你在平面上有两种类型的可以线性分离的点,SVM将找到一条直线,将这些点分成两种类型,并且这条直线尽可能远离所有这些点。

从规模上看,使用SVM(经过适当的修改)解决的一些最大的问题包括显示广告、人类剪切位点识别(human splice site recognition)、基于图像的性别检测,大规模图像分类……

6.集成方法(Ensemble methods)

集成方法是学习算法,它通过构建一组分类器,然后通过它们的预测结果进行加权投票来对新的数据点进行分类。原始的集成方法是贝叶斯平均,但是最近的算法包括纠错输出编码、Bagging和Boosting。

那么集成方法如何工作?并且为什么它们要优于单个模型?

  • 它们平均了单个模型的偏差:如果你将民主党的民意调查和共和党的民意调查在一起平均化,那么你将得到一个均衡的结果,不偏向任何一方。
  • 它们减少了方差:一组模型的总体意见比其中任何一个模型的单一意见更加统一。在金融领域,这就是所谓的多元化,有许多股票的组合比一个单独的股票的不确定性更少,这也为什么你的模型在数据多的情况下会更好的原因。
  • 它们不太可能过拟合:如果你有单个的模型没有过拟合,那么把这些模型的预测简单结合起来(平均、加权平均、逻辑回归),那么最后得到的模型也不会过拟合。

无监督学习

7.聚类算法(Clustering Algorithms)

聚类是将一系列对象分组的任务,目标是使相同组(集群)中的对象之间比其他组的对象更相似。

每一种聚类算法都不相同,下面是一些例子:

  • 基于质心的算法
  • 基于连接的算法
  • 基于密度的算法
  • 概率
  • 降维
  • 神经网络/深度学习

8.主成分分析(Principal Component Analysis,PCA)

PCA是一个统计学过程,它通过使用正交变换将一组可能存在相关性的变量的观测值转换为一组线性不相关的变量的值,转换后的变量就是所谓的主分量。

PCA的一些应用包括压缩、简化数据便于学习、可视化等。请注意,领域知识在选择是否继续使用PCA时非常重要。 数据嘈杂的情况(PCA的所有成分具有很高的方差)并不适用。

9.奇异值分解(Singular Value Decomposition,SVD)

在线性代数中,SVD是复杂矩阵的因式分解。对于给定的m * n矩阵M,存在分解使得M=UΣV,其中U和V是酉矩阵,Σ是对角矩阵。

实际上,PCA是SVD的一个简单应用。在计算机视觉中,第一个人脸识别算法使用PCA和SVD来将面部表示为“特征面”的线性组合,进行降维,然后通过简单的方法将面部匹配到身份,虽然现代方法更复杂,但很多方面仍然依赖于类似的技术。

10.独立成分分析(Independent Component Analysis,ICA)

ICA是一种统计技术,主要用于揭示随机变量、测量值或信号集中的隐藏因素。ICA对观测到的多变量数据定义了一个生成模型,这通常是作为样本的一个大的数据库。在模型中,假设数据变量由一些未知的潜在变量线性混合,混合方式也是未知的。潜在变量被假定为非高斯分布并且相互独立,它们被称为观测数据的独立分量。

ICA与PCA有关,但是当这些经典方法完全失效时,它是一种更强大的技术,能够找出源的潜在因素。 其应用包括数字图像、文档数据库、经济指标和心理测量。

现在运用你对这些算法的理解去创造机器学习应用,为世界各地的人们带来更好的体验吧。

查看英文原文:The 10 Algorithms Machine Learning Engineers Need to Know

from:http://www.infoq.com/cn/articles/10-algorithms-machine-learning-engineers-need-to-know

ML 工程师需了解的 10 大算法

那么如果你想进一步了解机器学习,你应该怎样开始呢?对我来说,我的入门是我在哥本哈大学留学时,参加的一个人工智能的课程。我的讲师是丹麦科技大学的一个全职的应用数学和计算机科学的教授,他主要研究逻辑学和人工智能,主要致力于使用逻辑学来对人类的计划,推理,和求解问题的过程进行建模。这个课程是针对理论/核心概念和动手解决问题的讨论。我们所用的课本是人工智能的经典之一: Peter Norvig’s Artificial Intelligence — A Modern Approach,其中涵盖的主题主要包括:智能代理,问题求解,敌对搜索,概率论,多智能体系统,社会AI,哲学/伦理学/人工智能的未来。课程的最后,三个人一组,我们实现了一个简单的基于搜索的代理,能够在虚拟环境下解决运输任务来作为编程项目。

多亏这个课,我学会了大量的知识,并决定继续学习这个专业的主题。在过去的几周里,我参加了旧金山的多个技术讲座,主要是关于深度学习,神经网络,数据结构的。还有一个机器学习的会议,很多该领域的专业人士都在场。最重要的是,我六月初的时候参加了Udacity的介绍机器学习(Intro to Machine Learning )的在线课程,并在前几天刚刚完成。在这篇文章中,我想分享一些我从课程中学习到的最常见的机器学习算法。

机器学习算法可以被分为三大类—监督学习,非监督学习,和强化学习。有监督的学习在数据集(训练集)的属性(标签)已知的条件下是有用的,但是在没有标签时,就失去作用了,需要使用其他方法来进行预测。当我们面临的是没有标记的数据(属性没有预先赋值),并且需要我们发现其中隐含的关系时,非监督学习就会很有用。增强学习介于这两个极端之间——对于每一个预测步骤或动作,都会有某种形式的反馈,但是没有确切的标签或着错误信息。因为这是一个入门课,我并不了解强化学习。但我希望这10个有监督和无监督学习算法就足够引起你的兴趣。

 

有监督的学习

1.决策树:决策树是一个使用类树图形,或者决策模型和其可能结果的决策支持工具,包括偶然事件的结果,资源成本和效用。看一下下面的图片感受一下它是什么样的。

 

从商业决策的角度来看,大多数时候,一个决策树就是使用最小数量的必须要问的是或不是的问题,来评估做出正确决策的可能性。作为一个方法,它允许你以一个结构化的和系统的方式来处理这个问题,从而得到一个合乎逻辑的结论。

 

2. 朴素贝叶斯分类:朴素贝叶斯分类是一族基于贝叶斯定理和特征之间的强独立性(朴素)的简单分类器。显著特点是方程式—— P(A|B) 是后验概率,P(B|A)  是似然概率,P(A) 是类的先验概率,P(B) 是预测的先验概率。

 

一些现实中的例子:

  • 标记一个电子邮件为垃圾邮件或非垃圾邮件
  • 将新闻文章分为技术类、政治类或体育类
  • 检查一段文字表达积极的情绪,或消极的情绪?
  • 用于人脸识别软件

 

3. 普通的最小二乘回归:如果你了解统计学,你以前可能听说过线性回归。最小二乘法是一种进行线性回归的方法。你可以把线性回归当作使用一条直线来拟合一系列的点的任务。有多种可能的方法来做到这一点,最小二乘的策略是这样的——你可以画一条线,然后对于每一个数据点,计算数据点和这条线的垂直距离,然后把它们加起来;拟合的线就是那个总和的距离尽可能小的线。

线性是指你用来拟合数据的模型,而最小二乘指的是你正在最小化的误差的度量。

4. 逻辑回归:逻辑回归是一种强大的统计方法,它使用一个或者更多的解释变量对一个二项式结果建模。它通过使用logistic 函数估计概率,这是累积 logistic  分布,来度量分类变量和一个或者更多的自变量之间的关系。

 

通常,回归可以被用于在现实世界的应用,如:

  • 信用评分
  • 度量营销活动的成功率
  • 预测某一产品的收入
  • 在一个特定的日子里会发生地震吗?

5. 支持向量机(SVM):支持向量机是一个二分类算法。给出N维空间的一组二分类的点,支持向量机产生一个 N-1 维的超平面将这些点分成两组。假设你在一张纸上有一些线性可分的二分类的点,支持向量机将会找到一条直线,将这些点分成两类,并位于离所有这些点尽可能远的位置。

就规模而言,其中一些最主要的问题已经使用支持向量机解决了(通过适当的修改),如,入广告显示,人类的剪接位点识别,基于图像的性别检测,大规模图像分类等等。

 

6. 集成方法:集成方法是构建一组分类器,然后通过对预测结果进行加权投票来对新的数据点进行分类。原始的集成方法是贝叶斯平均,但最近的算法包括纠错输出编码,bagging, 和boosting。

那么集成方法是怎样工作的,为什么他们会优于单个的模型?

  • 他们拉平了输出偏差:如果你将具有民主党倾向的民意调查和具有共和党倾向的民意调查取平均,你将得到一个中和的没有倾向一方的结果。
  • 它们减小了方差:一堆模型的聚合结果和单一模型的结果相比具有更少的噪声。在金融领域,这被称为多元化——多只股票的混合投资要比一只股票变化更小。这就是为什么数据点越多你的模型会越好,而不是数据点越少越好。
  • 它们不太可能产生过拟合:如果你有一个单独的没有过拟合的模型,你是用一种简单的方式(平均,加权平均,逻辑回归)将这些预测结果结合起来,然后就没有产生过拟合的空间了。

 

非监督学习

7. 聚类算法:聚类是将一组对象进行分组,使得同一组(簇)内的对象相似性远大于不同组之间的相似性。

每一种聚类算法都不太一样,这里有一些:

  • 基于质心的算法
  • 基于连通性的算法
  • 基于密度的算法
  • 概率聚类
  • 降维
  • 神经网络/深度学习

 

8. 主成分分析(PCA):主成分分析是一个统计过程,它使用正交变换,将一组可能相关的变量的一组观测值变换成线性不相关的变量,这些变量称为主成分。

PCA的应用包括压缩,简化数据使它们更容易学习,可视化。注意,选择是否使用主成分分析,领域知识是非常重要的。当数据充满噪声时,主成分分析是不合适的(主成分分析的所有成分都有很高的方差)。

 

9. 奇异值分解(SVD):在线性代数中,SVD是分解一个实数的比较复杂的矩阵。对于一个给定的m*n的矩阵M,存在一个分解M = UΣV,这里U和V是酉矩阵,Σ是一个对角矩阵。

PCA 是 SVD 的一个简单应用,在计算机视觉中,第一个人脸识别算法,就运用了 PCA 和 SVD 算法。使用这两个算法可以将人脸表示为 “特征脸”线性组合,降维,然后通过简单的方法匹配人脸的身份;虽然现代的方法复杂得多,但许多仍然依赖于类似的技术。

10. 独立成分分析(ICA):独立成分分析是一种统计方法,用来揭示随机变量集测试,信号集中的隐藏因素。独立成分分析为观测到的多变量的集合定义生成模型,它通常作为大型的样本数据数据库。在这个模型中,数据变量被假定为与一些潜在的未知变量的线性混合,混合系统也不知道。潜在变量被假设为非高斯并且相互独立的,它们被称为所观察到的数据的独立成分。

ICA 和 PCA 是相关的,但是它是一种更强大的技术,当那些经典的方法完全失效的时候,它能够从数据源中发现潜在的因素。它的应用包括数字图像,文档数据库,经济指标和心理测量。

英文出处:James Le

from:http://blog.jobbole.com/104457/