1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

s 遍历文件a,对每个url求取clip_image002,然后根据所取得的值将url分别存储到1000个小文件(记为clip_image004)中。这样每个小文件的大约为300M。

s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件(记为clip_image006)。这样处理后,所有可能相同的url都在对应的小文件(clip_image008)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

s 求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

2. 有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

方案1:

s 顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为clip_image010)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。

s 找一台内存在2G左右的机器,依次对clip_image010[1]用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为clip_image012)。

s 对clip_image012[1]这10个文件进行归并排序(内排序与外排序相结合)。

方案2:

一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

方案3:

与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

3. 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

方案1:顺序读文件中,对于每个词x,取clip_image014,然后按照该值存到5000个小文件(记为clip_image016)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,知道分解得到的小文件的大小都不超过1M。对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

4. 海量日志数据,提取出某日访问百度次数最多的那个IP。

方案1:首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有clip_image018个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

5. 在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。

方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存clip_image020内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

方案2:也可采用上题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

6. 海量数据分布在100台电脑中,想个办法高校统计出这批数据的TOP10。

方案1:

s 在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大。

s 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。

7. 怎么在海量数据中找出重复次数最多的一个?

方案1:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。

8. 上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。

方案1:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第6题提到的堆机制完成。

9. 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

方案1:这题用trie树比较合适,hash_map也应该能行。

10. 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

方案1:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。

11. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。

方案1:首先根据用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。

12. 100w个数中找出最大的100个数。

方案1:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。

方案3:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。

13. 寻找热门查询:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。

(1) 请描述你解决这个问题的思路;

(2) 请给出主要的处理流程,算法,以及算法的复杂度。

方案1:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

14. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到clip_image022个数中的中数?

方案1:先大体估计一下这些数的范围,比如这里假设这些数都是32位无符号整数(共有clip_image018[1]个)。我们把0到clip_image024的整数划分为N个范围段,每个段包含clip_image026个整数。比如,第一个段位0到clip_image028,第二段为clip_image026[1]clip_image030,…,第N个段为clip_image032clip_image024[1]。然后,扫描每个机器上的N个数,把属于第一个区段的数放到第一个机器上,属于第二个区段的数放到第二个机器上,…,属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下面我们依次统计每个机器上数的个数,一次累加,直到找到第k个机器,在该机器上累加的数大于或等于clip_image034,而在第k-1个机器上的累加数小于clip_image034[1],并把这个数记为x。那么我们要找的中位数在第k个机器中,排在第clip_image036位。然后我们对第k个机器的数排序,并找出第clip_image036[1]个数,即为所求的中位数。复杂度是clip_image038的。

方案2:先对每台机器上的数进行排序。排好序后,我们采用归并排序的思想,将这N个机器上的数归并起来得到最终的排序。找到第clip_image034[2]个便是所求。复杂度是clip_image040的。

15. 最大间隙问题

给定n个实数clip_image042,求着n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。

方案1:最先想到的方法就是先对这n个数据进行排序,然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法:

s 找到n个数据中最大和最小数据max和min。

s 用n-2个点等分区间[min, max],即将[min, max]等分为n-1个区间(前闭后开区间),将这些区间看作桶,编号为clip_image044,且桶clip_image046的上界和桶i+1的下届相同,即每个桶的大小相同。每个桶的大小为:clip_image048。实际上,这些桶的边界构成了一个等差数列(首项为min,公差为clip_image050),且认为将min放入第一个桶,将max放入第n-1个桶。

s 将n个数放入n-1个桶中:将每个元素clip_image052分配到某个桶(编号为index),其中clip_image054,并求出分到每个桶的最大最小数据。

s 最大间隙:除最大最小数据max和min以外的n-2个数据放入n-1个桶中,由抽屉原理可知至少有一个桶是空的,又因为每个桶的大小相同,所以最大间隙不会在同一桶中出现,一定是某个桶的上界和气候某个桶的下界之间隙,且该量筒之间的桶(即便好在该连个便好之间的桶)一定是空桶。也就是说,最大间隙在桶i的上界和桶j的下界之间产生clip_image056。一遍扫描即可完成。

16. 将多个集合合并成没有交集的集合:给定一个字符串的集合,格式如:clip_image058。要求将其中交集不为空的集合合并,要求合并完成的集合之间无交集,例如上例应输出clip_image060

(1) 请描述你解决这个问题的思路;

(2) 给出主要的处理流程,算法,以及算法的复杂度;

(3) 请描述可能的改进。

方案1:采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合,顺序合并将两个相邻元素合并。例如,对于clip_image062,首先查看aaa和bbb是否在同一个并查集中,如果不在,那么把它们所在的并查集合并,然后再看bbb和ccc是否在同一个并查集中,如果不在,那么也把它们所在的并查集合并。接下来再扫描其他的集合,当所有的集合都扫描完了,并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话,首先可以记录每个节点的根结点,改进查询。合并的时候,可以把大的和小的进行合,这样也减少复杂度。

17. 最大子序列与最大子矩阵问题

数组的最大子序列问题:给定一个数组,其中元素有正,也有负,找出其中一个连续子序列,使和最大。

方案1:这个问题可以动态规划的思想解决。设clip_image064表示以第i个元素clip_image066结尾的最大子序列,那么显然clip_image068。基于这一点可以很快用代码实现。

最大子矩阵问题:给定一个矩阵(二维数组),其中数据有大有小,请找一个子矩阵,使得子矩阵的和最大,并输出这个和。

方案1:可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素,那么在这个范围内,其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。代码详见我的博客。

引言

机器学习栏目记录我在学习Machine Learning过程的一些心得笔记,涵盖线性回归、逻辑回归、Softmax回归、神经网络和SVM等等,主要学习资料来自Standford Andrew Ng老师在Coursera的教程以及UFLDL Tutorial,同时也参考了大量网上的相关资料(在后面列出)。

本文主要记录我在学习神经网络过程中的心得笔记,共分为三个部分:

Neural network – Representation:神经网络的模型描述

Neural network – Learning:神经网络的模型训练

Neural network – Code:神经网络的代码实现。

前言

在本文中,我们将神经网络看作是一个分类算法,其输出是样本属于某类别的概率值 P(y==k|x;Θ),暂时不去考虑深度学习中用于特征学习的复杂卷积神经网络。因此,本文将按照一个分类模型的维度去安排文章结构,包括模型结构及数学描述、模型训练等,记录我在学习神经网络过程中的心得和思考。

本文是我在学习神经网络模型训练(Learning)时的笔记,主要以Andrew Ng老师在Coursera课程中以及UFLDL Tutorial中的关于神经网络模型训练的资料为主,文章小节安排如下:

1)神经网络的背景

2)代价函数(cost function)

3)优化(Optimization)/模型训练/参数学习

4)梯度检查(Gradient Checking)

5)随机初始化(Random Initialization)

6)Putting It Together

7)参考资料

8)结语

在阅读这部分笔记之前,请先阅读《Neural network – Representation:神经网络的模型描述》这一篇笔记,以了解神经网络的模型描述,激活函数,前向传播等基础知识。

《Neural network – Representation:神经网络的模型描述》

神经网络的背景

这里重复一遍神经网络的灵感来源,

实验证明大脑利用同一个学习算法实现了听觉、视觉等等所有的功能,这也是神经网络算法美好的愿景。

我认为一个好的算法,是具备自我学习、成长和进步能力的,可以不断的适应问题和环境变化。同样,一个好的人,一个好的公司,一个好的国家,也应该是具备这样的自我成长性,所谓好的事物是长出来的。

记得听过一个讲座,主讲人是国外大学的一位教授,他说:Deeplearning就是入侵其他领域的强有力武器,我们课题组是做图像的,半年前还一点都不懂 Natural language processing,但半年后我们就在该领域的顶级会议发了paper,因为我们只需要关心Raw data和深度网络模型,至于分词等技术我们并没有什么工作。

这位教授说的话也许有一定夸张成分,但也说明了神经网络是极具潜力的机器学习模型,可以用一套技术解决多个领域的问题,是不是非常类似于前述的人脑工作机制?并且现在大家也可以看到,深度神经网络目前基本上一统江湖,正在逐项碾压其他机器学习技术。

这是好事,也是坏事。

代价函数(cost function)

神经网络模型的代价函数取决于输出层是什么,也就是说不同的应用场景对应不同的代价函数,那么进一步的求导计算也就会有差异。

例如,在Autoencoder网络中,输出层等于输入层,此时采用均方误差(MSE)函数作为代价函数;在分类问题中,如果输出层采用Softmax回归进行分类,则可以直接采用Softmax回归的代价函数作为整个神经网络的代价函数。如果输出层采用Logistic regression进行分类,那么输出层其实就是K个Logistic regression,整个网络的代价函数就是这K个Logistic regression模型代价函数的加和。

1)输出层采用Logistic Regression

其实只要理解Cost function反映的就是预测值与实际值的误差,那么完全可以根据问题自定义一个Cost function表达式。在Coursera Machine Learning课程中将神经网络看作是输出层采用逻辑回归的分类器,因此其代价函数如下:

对比Logistic regression:

分析可以看出,

此时,神经网络里使用的代价函数是逻辑回归里中代价函数的一般化形式(generalization),也就是神经网络中不再是仅有一个逻辑回归输出单元,而是K个(就好像K个逻辑回归模型并行计算,也就是逻辑回归中的多分类问题)。

2)输出层采用Softmax Regression

其中,

θ 指的是Softmax Regression的参数矩阵。

3)Autoencoder(输出层=输入层)

自编码神经网络是一种无监督学习算法,学习一个 Hw,b (x) ≈ x 的函数。换句话说,它尝试逼近一个恒等函数,从而使得输出接近于输入。此时,自编码神经网络采用均方误差(MSE)作为代价函数,其代价函数形式如下:

实际上,

Autoencoder并不是用于分类,而是用于学习输入数据的压缩表示,可以发现输入数据中隐含着的一些特定结构。具体可以参考:Autoencoders and Sparsity

讨论:

1)代价函数的均值化问题

这里均值化指的是代价函数是否除以样本数,以及代价函数中哪一项应该除以样本数的问题。

首先对比Coursera ML课程中神经网络的代价函数公式:

细心的同学可以看到,

这里正则化项是除以样本数 m 的,而我给出的代价函数是没有除以样本数的,如下:

对于正则项是否除以样本数这个问题,我作为初学者还没有看到确切深入的讨论,并且看到的大多数资料中是没有均值化的。根据实验,在不同的问题中,正则项是否均值化对优化过程的影响也不一样的,有时候可能没有影响,有时候就会致使梯度无法收敛,这一点大家可以在代码中实验一下。

通过引入正则项是否均值化问题,我想讨论的其实是:代价函数是否除以样本数(均值化)?哪一项应该除以样本数?

这里我根据学习和实验中粗浅的经验总结如下:

其实代价函数是否除以样本数(均值化),是整体均值化?还是部分均值化?这在很多算法模型中都存在这个问题,比如在Sparse Autoencoder中,代价函数由误差项,权重衰减项(正则化项),稀疏惩罚项构成,如下:

Cost function = Error term + Sparsity penalty term + Weight decay term

那么,在具体实现时,到底应该如何均值化呢?

基本原则是这样,

如果某个term与整个训练样本集有关,那么就应该均值化(除以样本数),否则就不均值化。例如Sparse Autoencoder的代价函数,误差项是所有训练样本误差的总和,稀疏惩罚项是对所有样本的稀疏性惩罚,因此这两项应该均值化,而权重衰减项是针对参数的,所以不应该均值化。

2)什么时候采用逻辑回归作为分类?什么时候采用Softmax回归呢?

这里引用UFLDL的讲解:

Softmax Regression vs. k Binary Classifiers

如果你在开发一个音乐分类的应用,需要对k种类型的音乐进行识别,那么是选择使用 softmax 分类器呢,还是使用 logistic 回归算法建立 k 个独立的二元分类器呢?

这一选择取决于你的类别之间是否互斥,例如,如果你有四个类别的音乐,分别为:古典音乐、乡村音乐、摇滚乐和爵士乐,那么你可以假设每个训练样本只会被打上一个标签(即:一首歌只能属于这四种音乐类型的其中一种),此时你应该使用类别数 k = 4 的softmax回归。(如果在你的数据集中,有的歌曲不属于以上四类的其中任何一类,那么你可以添加一个“其他类”,并将类别数 k 设为5。)

现在我们来看一个计算视觉领域的例子,你的任务是将图像分到三个不同类别中。(i) 假设这三个类别分别是:室内场景、户外城区场景、户外荒野场景。你会使用sofmax回归还是 3个logistic 回归分类器呢? (ii) 现在假设这三个类别分别是室内场景、黑白图片、包含人物的图片,你又会选择 softmax 回归还是多个 logistic 回归分类器呢?

在第一个例子中,三个类别是互斥的,因此更适于选择softmax回归分类器 。而在第二个例子中,建立三个独立的logistic回归分类器更加合适。

3)是否惩罚偏置单元对应的参数?

当设置偏置单元=1,并在参数矩阵 Θ 中设置第 0 列对应为偏置单元的参数时,就存在一个问题:是否惩罚偏置单元对应的参数?

引用Andrew Ng老师对该问题的说明:

不应该把这些项加入到正规化项里去,因为我们并不想正规化这些项,但这只是一个合理的规定,即使我们真的把他们加进去了,也就是 i 从0 加到s(l),这个式子(代价函数)依然成立,并且不会有大的差异。这个“不把偏差项正规化”的规定可能只是更常见一些。

一般来说是不惩罚偏置项的,因为没什么意义。

补充:

1)均方误差

均方误差(MeanSquaredError,MSE)是衡量“平均误差”的一种较方便的方法,可以评价数据的变化程度。对于等精度测量来说,还有一种更好的表示误差的方法,就是标准误差。标准误差定义为各测量值误差的平方和的平均值的平方根。数理统计中均方误差是指参数估计值与参数真值之差平方的期望值,记为MSE。MSE是衡量“平均误差”的一种较方便的方法,MSE可以评价数据的变化程度,MSE的值越小,说明预测模型描述实验数据具有更好的精确度。与此相对应的,还有均方根误差RMSE、平均绝对百分误差等等。

参考:Bing网典 – 均方误差

2)标准误差

1,标准误差一般用来判定该组测量数据的可靠性,在数学上它的值等于测量值误差的平方和的平均值的平方根。

2,标准误差在正态分布中表现出正态分布曲线的陡峭程度,标准误差越小,曲线越陡峭,反之,曲线越平坦。

3,标准误差在实际的计算中使用的是标准误差估算值。

4,标准误差不是实际误差。

参考:Bing网典 – 标准误差

优化(Optimization)/模型训练/参数学习

前述已经给出了神经网络的代价函数,下面就可以通过最小化(minimize)该代价函数来求解神经网络模型的最优参数。

神经网络的优化依然可以采用梯度下降法(Gradient descent),而梯度下降法需要两方面的计算:

1)代价函数

2)梯度

即,

代价函数的计算公式前面已经给出,

J(Θ) 的梯度如何计算就需要请出大名鼎鼎的反向传播算法(Backpropagation Algorithm)

重点:反向传播(Backpropagation)

定义如下网络,输出层采用逻辑回归:

首先,我们引入符号 δ,解释如下:

代表了第 l 层的第 j 个节点的误差。

那么,各层各节点的error计算如下:

其中,

可以看出,与激励值(activation)计算类似,误差的计算也是层层传递的,δ3的计算依赖于δ4,δ2的计算依赖于δ3。这样一种误差计算方式,就称之为反向传播(backpropagation)

以上面的网络模型为例,反向传播算法从后往前(或者说从右往左)计算,即从输出层开始计算,并反向逐层向前计算每一层的 δ 。反向传播法这个名字源于我们从输出层开始计算 δ 项,然后我们返回到上一层计算第 3 个隐藏层的 δ 项,接着我们再往前一步来计算 δ2。所以说我们是类似于把输出层的误差反向传播给了第3层,然后是再传到第2层,这就是反向传播的意思。

通过反向传播计算的这些 δ 项,可以非常快速的计算出所有参数的偏导数项(J(Θ) 关于 所有θ的偏导数项)。

让我们将反向传播与前向传播对比一下:

直观地看,这个 δ 项在某种程度上捕捉到了在神经节点上的激励值的误差。反过来理解,一个神经节点的残差也表明了该节点对最终输出值的残差产生了多少影响。

因此可以说,

反向传播算法就是在逐层计算每个神经节点的激励值误差。

备注,

上面只是一种直观的解释,那么 δ 项到底是什么?其实 δ 本质上是代价函数 J 对加权和 z 的求导结果。

重点:反向传播的直观理解

这里引用Coursera ML课程中的描述:

重点:关于 δ(L) 的计算

这里重点讨论两个问题:

1)为何上面所讲的网络最后一层的 δ 与其他层计算不一致?

其实是一致的,

如前面所述,δ 本质上是代价函数 J 对加权和 z 的求导结果。这里 δ(4) 是 J 对 z(4) 的导数,δ(3) 是 J 对 z(3) 的导数,具体推导见后文。

2)在阅读资料时,为何最后一层(输出层)的 δ 有各种计算方式?

比如,

再比如,

那么是什么原因导致了上面不同的公式形式呢?其实原因就在于所采用的代价函数和输出层激励函数的形式。

不同形式的代价函数和输出层激励函数,会推导出不同的输出层误差计算公式!

下面我们可以利用两种形式的代价函数进行偏导数计算,验证上述结论,如下:

1)

Cost function采用:

输出层激励函数(也可以称为预测函数)采用:

则 δ(L) 推导如下:

2)

Cost function采用:

输出层激励函数(也可以称为预测函数)采用:

则 δ(L) 推导如下:

如果,

输出层激励函数(也可以称为预测函数)采用:

则 δ(L) 推导如下:

综上可以看出,

δ(L) 的形式与代价函数 J 和输出层激励函数 g 的形式直接相关。

备注,

Andrew Ng老师在课程中为了降低理解难度,并没有讲明上述的推演关系,而是给出一种直观的解释,即:δ(L) = 实际值 – 预测值。作为入门的话,这样理解也未尝不可。

至此,完成 δ(L) 计算的推导和讨论,也解答了神经网络最后一层误差计算出现不同公式形式的原因,希望可以为大家提供一定参考。

如果对于上述推导感兴趣,请参考:https://share.coursera.org/wiki/index.php/ML:Neural_Networks:_Learninghttp://deeplearning.stanford.edu/wiki/index.php/Backpropagation_Algorithm

重点:梯度计算(Gradient Computation)

在神经网络模型中,代价函数 J(Θ) 关于 参数 θ 的偏导数(partial derivative terms)/梯度计算如下:

向量化描述如下:

关于该计算公式的推导可以参考wiki ML中关于Neural Network: Learning一节(https://share.coursera.org/wiki/index.php/ML:Neural_Networks:_Learning)。

Andrew Ng老师给出的用于计算梯度的Backpropagation Algorithm如下:

Backpropagation Algorithm

写到这里想起来前阵子听讲座,主讲人的两句吐槽:

1)入门神经网络只要学会计算梯度就行了,其他什么概念都不需要了解,比SVM简单多了,并且想现在很多Toolbox连梯度都帮你计算了,你还需要做什么?你只需要配置下网络结构就可以了,代码都不用写,越来越没有门槛了。

2)算个梯度还搞出个什么反向传播(Backpropagation),说到底不就是链式法则(chain rule)么!现在人真会玩,换个名词就炒冷饭!

关于利用反向传播算法计算梯度,可以重点参考:

Backpropagation Algorithm

备注,

也许有人会有疑问,反向传播到底是用来计算梯度的?还是仅仅用来逐层计算误差的??,为何这里所写的反向传播只计算了误差,而没有计算梯度??

确实,在Coursera ML课程中,Andrew Ng老师的讲解一开始告诉你说,Backpropagation是用来反向逐层计算误差的。而后续的讲解,包括很多资料里所描述的BP算法又是是用来计算梯度的。这到底是咋回事呢?

如前所述,反向传播仅仅是计算过程的一个直观上的称呼罢了,更重要的是其背后的神经网络求导思想,所以,

无论说:反向传播是用来逐层计算(或称传递)误差的;又或者说:反向传播是用来计算梯度的。

其实所说所指的都是如何对神经网络的参数进行快速求导这个事情。

如果非要较真儿,也许可以这样理解前向传播、反向传播、梯度计算之间的关系:

前向传播和反向传播是一种计算过程的直观描述,而梯度是基于前向传播得到的Activation和反向传播得到的Error进行计算的。

为了更清晰更方便的记忆激励值、误差、前向传播、反向传播等概念,可以这样:

前向传播计算 a,反向传播计算 δ,基于 a 和 δ 计算梯度。

重点:梯度下降(Gradient Descent)

得到代价函数和梯度,就可以利用梯度下降算法来求解最优参数,描述如下:

补充:

1)梯度、偏导数、方向导数

方向导数:函数上某一点在某一方向上的导数值,偏导数就是沿着坐标轴的方向导数;

偏导数:一个多变量的函数的偏导数,就是它关于其中一个变量的导数而保持其他变量恒定(相对于全导数,在其中所有变量都允许变化),偏导数反映的是函数沿坐标轴正方向的变化率;

梯度:梯度即是某一点最大的方向导数,沿梯度方向函数有最大的变化率(正向增加,逆向减少);

参考:

方向导数和梯度

http://blog.csdn.net/wolenski/article/details/8030654

百度百科-梯度

http://baike.baidu.com/subview/454441/12503183.htm

梯度检查(Gradient Checking)

反向传播算法作为一个有很多细节的算法在实现的时候比较复杂,可能会遇到很多细小的错误。所以如果把BP算法和梯度下降法或者其他优化算法一起运行时,可能看起来运行正常,并且代价函数可能在每次梯度下降法迭代时都会减小,但是可能最后得到的计算结果误差较高,更要命的是很难判断这个错误结果是哪些小错误导致的。

解决该问题的方法是:梯度检查 (Gradient Checking)

梯度检查 (Gradient Checking)的思想就是通过数值近似(numerically approximately)的方式计算导数近似值,从而检查导数计算是否正确。虽然数值计算方法速度很慢,但实现起来很容易,并且易于理解,所以它可以用来验证例如BP算法等快速求导算法的正确性。

如前所述,机器学习中大部分算法的核心就是代价值计算和梯度计算,因此,在实现神经网络或者其他比较复杂的模型时候,利用Gradient Checking可以检查算法是否正确实现。

梯度检查 (Gradient Checking)的核心是导数的数值计算,公式如下:

多参数情况的公式如下:

梯度检查 (Gradient Checking)的实现,

其中,

DVec:利用反向传播算法得到的导数,BP是一个比较有效率的计算导数的方法;

gradApprox:利用数值近似得到的导数,数值计算法速度很慢;

如果两者相等或者近似,最多几位小数的差距,那么就可以确信所实现的BP算法是正确的。

随机初始化(Random Initialization)

当运行一个优化算法(例如梯度下降算法或者其他高级优化算法)时,需要给变量 θ 设置初始值。例如,在梯度下降法中,需要对 θ 进行初始化(通常为全0),然后使用梯度下降的方法不断最小化函数 J,最终代价函数 J 下降到最小。

但要注意的是,

将 θ 初始化为全 0 向量在逻辑回归时是可行的的,但在训练神经网络时是不可行的,这会使得神经网络无法学习出有价值的信息。

以第一层参数矩阵(权重矩阵)为例,假定有K个隐藏单元,那么神经网络的参数矩阵 Θ1 实质上对应着特征的K个映射函数(映射关系),如果参数全为 0,那就意味着所有映射关系都是相同的,即所有的隐藏单元都在计算相同的激励值,那么这样一个具有很多隐藏单元的网络结构就是完全多余的表达,最终该网络只能学到一种特征。

这种现象称为:对称权重(Symmetric ways)

解决办法其实很简单,即:随机初始化(Random Initialization)

描述如下:

所有权重相同的问题称为对称权重(Symmetric ways),随机初始化解决的就是如何打破这种对称性,需要做的就是对 θ 的每个值进行初始化,使其范围在 -ɛ 到 +ɛ 之间。

ɛ 的取值:

Θ 的初始化:

Putting It Together

上面已经讲解了神经网络训练的各个部分,综合起来就可以得到一个最基础神经网络学习算法的实现过程。

训练一个神经网络算法模型,第一件事就是设计网络结构,也就是搭建网络的大体框架(architecture),框架的意思是神经元之间的连接模式,包括,

· 网络层数,主要是隐层数量;

· 每一层的节点个数,主要是隐藏单元数量;

这里引用课程中的一张PPT来作说明:

下面总结网络结构设计的几点基本原则:

网络结构的选择规则:

神经网络搭建时,可能会从上面PPT中所示的几种结构中选择,一个默认的规则是只使用单个隐藏层,即PPT中最左边的结构,或者如果使用不止一个隐藏层的话,同样也有一个默认规则就是每一个隐藏层通常都应有相同的隐藏单元数。

通常来说,PPT中左边这个结构是较为合理的默认结构。

输入层与输出层:

对于一个用于分类的神经网络,输入层即特征,输出层即类别。

Number of input units = dimension of features x(i)

Number of output units = number of classes

隐藏单元的选择规则:

通常情况下隐藏单元越多越好,不过需要注意的是如果有大量隐藏单元,那么计算量一般会比较大。一般来说,每个隐藏层所包含的单元数量还应该和输入 x 的维度相匹配,也要和特征的数目匹配。

可能隐藏单元的数目和输入特征的数量相同,或者是它的二倍或者三倍、四倍。一般来说,隐藏单元的数目取为稍大于输入特征数目都是可以接受的。

完成上述理解,便可以得到神经网络的训练过程,如下。

神经网络的训练过程:

下面附一张Andrew Ng老师在Coursera ML课程中的PPT,来给出神经网络训练过程的直观描述:

(由于绘图所限,这里假定代价函数 J(Θ) 只有两个参数值)

说明:

神经网络的代价函数J(θ)是一个非凸函数,因此理论上是只能够停留在局部最小值的位置。

———————————————————————

实际上,梯度下降算法和其他一些高级优化方法理论上都只能使神经网络的代价函数收敛于局部最小值,不过一般来讲这个问题并不是什么要紧的事,因为尽管不能保证这些优化算法一定会得到全局最优值,但通常来讲这些算法在最小化代价函数 J(θ) 的过程中还是表现得很不错的,通常能够得到一个很小的局部最小值,虽然这不一定是全局最优值。

参考资料

UFLDL Tutorial

http://ufldl.stanford.edu/tutorial/

Coursera – Machine learning( Andrew Ng)

https://www.coursera.org/learn/machine-learning

Coursera -ML:Neural Networks: Representation

https://share.coursera.org/wiki/index.php/ML:Neural_Networks:_Representation

Coursera -ML:Neural Networks: Learning

https://share.coursera.org/wiki/index.php/ML:Neural_Networks:_Learning

结语

以上就是神经网络模型Learning的相关知识点和实现过程,其中重点讨论了神经网络的代价函数模型和参数学习中的Backpropagation算法,这也是我在学习NN时反复理解了好久的问题,希望可以为大家提供一些帮助,也欢迎交流讨论,谢谢!

本文的文字、公式和图形都是笔者根据所学所看的资料经过思考后认真整理和撰写编制的,如有朋友转载,希望可以注明出处:

[机器学习] Coursera ML笔记 – 神经网络(Learning)

http://blog.csdn.net/walilk/article/details/50504393

小礼物走一走,来简书关注


作者:hfk
链接:https://www.jianshu.com/p/c69cd43c537a
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Data-Mining试题

2011Alibaba数据分析师(实习)试题解析

一、异常值是指什么?请列举1种识别连续型变量异常值的方法?

异常值(Outlier) 是指样本中的个别值,其数值明显偏离所属样本的其余观测值。在数理统计里一般是指一组观测值中与平均值的偏差超过两倍标准差的测定值。
Grubbs’ test(是以Frank E.Grubbs命名的),又叫maximumnormed residual test,是一种用于单变量数据集异常值识别的统计检测,它假定数据集来自正态分布的总体。
未知总体标准差σ,在五种检验法中,优劣次序为:t检验法、格拉布斯检验法、峰度检验法、狄克逊检验法、偏度检验法。

二、什么是聚类分析?聚类算法有哪几种?请选择一种详细描述其计算原理和步骤。

聚类分析(clusteranalysis)是一组将研究对象分为相对同质的群组(clusters)的统计分析技术。 聚类分析也叫分类分析(classification analysis)或数值分类(numerical taxonomy)。聚类与分类的不同在于,聚类所要求划分的类是未知的。
聚类分析计算方法主要有: 层次的方法(hierarchical method)、划分方法(partitioning method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)、基于模型的方法(model-based method)等。其中,前两种算法是利用统计学定义的距离进行度量。

k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
其流程如下:
(1)从 n个数据对象任意选择 k 个对象作为初始聚类中心;     
(2)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;  
(3)重新计算每个(有变化)聚类的均值(中心对象);
(4)循环(2)、(3)直到每个聚类不再发生变化为止(标准测量函数收敛)。
优 点:本算法确定的K 个划分到达平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果较好。对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为 O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K<t=<{2},{3,6},{8}>
B、s=<{2,4},{3,5,6},{8}>t=<{2},{8}>
C、s=<{1,2},{3,4}>t=<{1},{2}>

D、s=<{2,4},{2,4}>t=<{2},{4}>
44. 在图集合中发现一组公共子结构,这样的任务称为 ( B )
A、频繁子集挖掘 B、频繁子图挖掘 C、频繁数据项挖掘 D、频繁模式挖掘
45. 下列度量不具有反演性的是(D)
A、 系数 B、几率 C、Cohen度量 D、兴趣因子
46. 下列__(A)__不是将主观信息加入到模式发现任务中的方法。
A、与同一时期其他数据对比
B、可视化
C、基于模板的方法
D、主观兴趣度量
47. 下面购物篮能够提取的3-项集的最大数量是多少(C)
ID 购买项
1 牛奶,啤酒,尿布
2 面包,黄油,牛奶
3 牛奶,尿布,饼干
4 面包,黄油,饼干
5 啤酒,饼干,尿布
6 牛奶,尿布,面包,黄油
7 面包,黄油,尿布
8 啤酒,尿布

9 牛奶,尿布,面包,黄油
10 啤酒,饼干
A、1 B、2 C、3 D、4
48. 以下哪些算法是分类算法,A,DBSCAN B,C4.5 C,K-Mean D,EM (B)
49. 以下哪些分类方法可以较好地避免样本的不平衡问题, A,KNN B,SVM C,Bayes D,神经网络 (A)
50. 决策树中不包含一下哪种结点,A,根结点(root node) B,内部结点(internal node) C,外部结点(external node) D,叶结点(leaf node) (C)
51. 不纯性度量中Gini计算公式为(其中c是类的个数) (A)
A, B, C, D, (A)
53. 以下哪项关于决策树的说法是错误的 (C)
A. 冗余属性不会对决策树的准确率造成不利的影响
B. 子树可能在决策树中重复多次
C. 决策树算法对于噪声的干扰非常敏感
D. 寻找最佳决策树是NP完全问题
54. 在基于规则分类器的中,依据规则质量的某种度量对规则排序,保证每一个测试记录都是由覆盖它的“最好的”规格来分类,这种方案称为 (B)
A. 基于类的排序方案
B. 基于规则的排序方案
C. 基于度量的排序方案
D. 基于规格的排序方案。
55. 以下哪些算法是基于规则的分类器 (A)
A. C4.5 B. KNN C. Na?ve Bayes D. ANN

56. 如果规则集R中不存在两条规则被同一条记录触发,则称规则集R中的规则为(C);
A, 无序规则 B,穷举规则 C, 互斥规则 D,有序规则
57. 如果对属性值的任一组合,R中都存在一条规则加以覆盖,则称规则集R中的规则为(B)

A, 无序规则 B,穷举规则 C,互斥规则 D,有序规则
58. 如果规则集中的规则按照优先级降序排列,则称规则集是 (D)
A, 无序规则 B,穷举规则 C, 互斥规则 D,有序规则
59. 如果允许一条记录触发多条分类规则,把每条被触发规则的后件看作是对相应类的一次投票,然后计票确定测试记录的类标号,称为(A)
A, 无序规则 B,穷举规则 C, 互斥规则 D,有序规则
60. 考虑两队之间的足球比赛:队0和队1。假设65%的比赛队0胜出,剩余的比赛队1获胜。队0获胜的比赛中只有30%是在队1的主场,而队1取胜的比赛中75%是主场获胜。如果下一场比赛在队1的主场进行队1获胜的概率为 (C)
A,0.75 B,0.35 C,0.4678 D, 0.5738
61. 以下关于人工神经网络(ANN)的描述错误的有 (A)
A,神经网络对训练数据中的噪声非常鲁棒 B,可以处理冗余特征 C,训练ANN是一个很耗时的过程 D,至少含有一个隐藏层的多层神经网络
62. 通过聚集多个分类器的预测来提高分类准确率的技术称为 (A)
A,组合(ensemble) B,聚集(aggregate) C,合并(combination) D,投票(voting)
63. 简单地将数据对象集划分成不重叠的子集,使得每个数据对象恰在一个子集中,这种聚类类型称作( B )

A、层次聚类 B、划分聚类 C、非互斥聚类 D、模糊聚类
64. 在基本K均值算法里,当邻近度函数采用( A )的时候,合适的质心是簇中各点的中位数。
A、曼哈顿距离 B、平方欧几里德距离 C、余弦距离 D、Bregman散度
65.( C )是一个观测值,它与其他观测值的差别如此之大,以至于怀疑它是由不同的机制产生的。
A、边界点 B、质心 C、离群点 D、核心点
66. BIRCH是一种( B )。
A、分类器 B、聚类算法 C、关联分析算法 D、特征选择算法
67. 检测一元正态分布中的离群点,属于异常检测中的基于( A )的离群点检测。

A、统计方法 B、邻近度 C、密度 D、聚类技术
68.( C )将两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度,它是一种凝聚层次聚类技术。
A、MIN(单链) B、MAX(全链) C、组平均 D、Ward方法
69.( D )将两个簇的邻近度定义为两个簇合并时导致的平方误差的增量,它是一种凝聚层次聚类技术。
A、MIN(单链) B、MAX(全链) C、组平均 D、Ward方法
70. DBSCAN在最坏情况下的时间复杂度是( B )。
A、O(m) B、O(m2) C、O(log m) D、O(m*log m)
71. 在基于图的簇评估度量表里面,如果簇度量为proximity(Ci , C),簇权值为mi ,那么它的类型是( C )。
A、基于图的凝聚度 B、基于原型的凝聚度 C、基于原型的分离度 D、基于图的凝聚度和分离度

72. 关于K均值和DBSCAN的比较,以下说法不正确的是( A )。
A、K均值丢弃被它识别为噪声的对象,而DBSCAN一般聚类所有对象。
B、K均值使用簇的基于原型的概念,而DBSCAN使用基于密度的概念。
C、K均值很难处理非球形的簇和不同大小的簇,DBSCAN可以处理不同大小和不同形状的簇。
D、K均值可以发现不是明显分离的簇,即便簇有重叠也可以发现,但是DBSCAN会合并有重叠的簇。
73. 以下是哪一个聚类算法的算法流程:①构造k-最近邻图。②使用多层图划分算法划分图。③repeat:合并关于相对互连性和相对接近性而言,最好地保持簇的自相似性的簇。④until:不再有可以合并的簇。( C)。
A、MST B、OPOSSUM C、Chameleon D、Jarvis-Patrick(JP)
74. 考虑这么一种情况:一个对象碰巧与另一个对象相对接近,但属于不同的类,因为这两个对象一般不会共享许多近邻,所以应该选择( D )的相似度计算方法。
A、平方欧几里德距离 B、余弦距离 C、直接相似度 D、共享最近邻
75. 以下属于可伸缩聚类算法的是(A )。
A、CURE B、DENCLUE C、CLIQUE D、OPOSSUM
76. 以下哪个聚类算法不是属于基于原型的聚类( D )。
A、模糊c均值 B、EM算法 C、SOM D、CLIQUE
77. 关于混合模型聚类算法的优缺点,下面说法正确的是( B )。
A、当簇只包含少量数据点,或者数据点近似协线性时,混合模型也能很好地处理。
B、混合模型比K均值或模糊c均值更一般,因为它可以使用各种类型的分布。
C、混合模型很难发现不同大小和椭球形状的簇。
D、混合模型在有噪声和离群点时不会存在问题。
78. 以下哪个聚类算法不属于基于网格的聚类算法( D )。

A、STING B、WaveCluster C、MAFIA D、BIRCH
79. 一个对象的离群点得分是该对象周围密度的逆。这是基于( C )的离群点定义。
A.概率 B、邻近度 C、密度 D、聚类
80. 下面关于Jarvis-Patrick(JP)聚类算法的说法不正确的是( D )。
A、JP聚类擅长处理噪声和离群点,并且能够处理不同大小、形状和密度的簇。
B、JP算法对高维数据效果良好,尤其擅长发现强相关对象的紧致簇。
C、JP聚类是基于SNN相似度的概念。
D、JP聚类的基本时间复杂度为O(m)。
二、 多选题
1. 通过数据挖掘过程所推倒出的关系和摘要经常被称为:(A B)
A. 模型 B. 模式 C. 模范 D. 模具
2 寻找数据集中的关系是为了寻找精确、方便并且有价值地总结了数据的某一特征的表示,这个过程包括了以下哪些步骤? (A B C D)
A. 决定要使用的表示的特征和结构
B. 决定如何量化和比较不同表示拟合数据的好坏
C. 选择一个算法过程使评分函数最优
D. 决定用什么样的数据管理原则以高效地实现算法。
3. 数据挖掘的预测建模任务主要包括哪几大类问题? (A B)
A. 分类 B. 回归 C. 模式发现 D. 模式匹配
4. 数据挖掘算法的组件包括:(AB C D)
A. 模型或模型结构 B. 评分函数 C. 优化和搜索方法 D. 数据管理策略
5. 以下哪些学科和数据挖掘有密切联系?(A D)
A. 统计 B. 计算机组成原理 C. 矿产挖掘 D. 人工智能

6. 在现实世界的数据中,元组在某些属性上缺少值是常有的。描述处理该问题的各种方法有: (ABCDE)
A忽略元组 C使用一个全局常量填充空缺值
B使用属性的平均值填充空缺值 D使用与给定元组属同一类的所有样本的平均值 E使用最可能的值填充空缺值
7.下面哪些属于可视化高维数据技术 (ABCE)
A 矩阵 B 平行坐标系 C星形坐标 D散布图 E Chernoff脸
8. 对于数据挖掘中的原始数据,存在的问题有: (ABCDE)
A 不一致 B重复 C不完整 D 含噪声 E 维度高   
9.下列属于不同的有序数据的有:(ABCE)
A 时序数据 B 序列数据 C时间序列数据 D事务数据 E空间数据
10.下面属于数据集的一般特性的有:( B C D)
A 连续性 B 维度 C稀疏性 D 分辨率 E 相异性        
11. 下面属于维归约常用的线性代数技术的有: (A C)
A 主成分分析 B 特征提取 C 奇异值分解 D特征加权 E 离散化
12. 下面列出的条目中,哪些是数据仓库的基本特征: (ACD)
A. 数据仓库是面向主题的 B. 数据仓库的数据是集成的
C. 数据仓库的数据是相对稳定的 D. 数据仓库的数据是反映历史变化的
E. 数据仓库是面向事务的

13. 以下各项均是针对数据仓库的不同说法,你认为正确的有(BCDE )。
A.数据仓库就是数据库
B.数据仓库是一切商业智能系统的基础
C.数据仓库是面向业务的,支持联机事务处理(OLTP)
D.数据仓库支持决策而非事务处理
E.数据仓库的主要目标就是帮助分析,做长期性的战略制定
14. 数据仓库在技术上的工作过程是: (ABCD)
A. 数据的抽取 B. 存储和管理 C. 数据的表现

D. 数据仓库设计 E. 数据的表现
15. 联机分析处理包括以下哪些基本分析功能? (BCD)
A. 聚类 B. 切片 C. 转轴 D. 切块 E. 分类
16. 利用Apriori算法计算频繁项集可以有效降低计算频繁集的时间复杂度。在以下的购物篮中产生支持度不小于3的候选3-项集,在候选2-项集中需要剪枝的是(BD)
ID 项集
1 面包、牛奶
2 面包、尿布、啤酒、鸡蛋
3 牛奶、尿布、啤酒、可乐
4 面包、牛奶、尿布、啤酒
5 面包、牛奶、尿布、可乐
A、啤酒、尿布 B、啤酒、面包 C、面包、尿布 D、啤酒、牛奶

17. 下表是一个购物篮,假定支持度阈值为40%,其中__(A D)__是频繁闭项集。
TID 项
1 abc
2 abcd
3 bce
4 acde
5 de
A、abc B、ad
C、cd D、de
18. Apriori算法的计算复杂度受__(ABCD)?__影响。
A、支持度阀值 B、项数(维度)
C、事务数 D、事务平均宽度
19. 非频繁模式__(AD)__
A、其支持度小于阈值 B、都是不让人感兴趣的
C、包含负模式和负相关模式 D、对异常数据项敏感
20. 以下属于分类器评价或比较尺度的有: A,预测准确度 B,召回率 C,模型描述的简洁度 D,计算复杂度 (ACD)
21. 在评价不平衡类问题分类的度量方法有如下几种,A,F1度量 B,召回率(recall) C,精度(precision) D,真正率(turepositive rate,TPR) (ABCD)
22. 贝叶斯信念网络(BBN)有如下哪些特点,A,构造网络费时费力 B,对模型的过分问题非常鲁棒 C,贝叶斯网络不适合处理不完整的数据 D,网络结构确定后,添加变量相当麻烦 (AB)
23. 如下哪些不是最近邻分类器的特点,A,它使用具体的训练实例进行预测,不必维护源自数据的模型 B,分类一个测试样例开销很大C,最近邻分类器基于全局信息进行预测 D,可以生产任意形状的决策边界 (C)
24. 如下那些不是基于规则分类器的特点,A,规则集的表达能力远不如决策树好 B,基于规则的分类器都对属性空间进行直线划分,并将类指派到每个划分 C,无法被用来产生更易于解释的描述性模型 D,非常适合处理类分布不平衡的数据集 (AC)
25. 以下属于聚类算法的是(ABD )。
A、K均值 B、DBSCAN C、Apriori D、Jarvis-Patrick(JP)
26.( CD )都属于簇有效性的监督度量。
A、轮廓系数 B、共性分类相关系数 C、熵 D、F度量
27. 簇有效性的面向相似性的度量包括( BC )。
A、精度 B、Rand统计量 C、Jaccard系数 D、召回率
28.( ABCD )这些数据特性都是对聚类分析具有很强影响的。
A、高维性 B、规模 C、稀疏性 D、噪声和离群点

29. 在聚类分析当中,( AD )等技术可以处理任意形状的簇。
A、MIN(单链) B、MAX(全链) C、组平均 D、Chameleon
30. ( AB )都属于分裂的层次聚类算法。
A、二分K均值 B、MST C、Chameleon D、组平均

1. 数据挖掘的主要任务是从数据中发现潜在的规则,从而能更好的完成描述数据、预测数据等任务。 (对)
2. 数据挖掘的目标不在于数据采集策略,而在于对于已经存在的数据进行模式的发掘。(对)3. 图挖掘技术在社会网络分析中扮演了重要的角色。(对)
4. 模式为对数据集的全局性总结,它对整个测量空间的每一点做出描述;模型则对变量变化空间的一个有限区域做出描述。(错)
5. 寻找模式和规则主要是对数据进行干扰,使其符合某种规则以及模式。(错)
6. 离群点可以是合法的数据对象或者值。    (对)
7. 离散属性总是具有有限个值。        (错)
8. 噪声和伪像是数据错误这一相同表述的两种叫法。     (错)
9. 用于分类的离散化方法之间的根本区别在于是否使用类信息。   (对)
10. 特征提取技术并不依赖于特定的领域。      (错)
11. 序列数据没有时间戳。      (对)
12. 定量属性可以是整数值或者是连续值。     (对)
13. 可视化技术对于分析的数据类型通常不是专用性的。    (错)
14. DSS主要是基于数据仓库.联机数据分析和数据挖掘技术的应用。(对)
15. OLAP技术侧重于把数据库中的数据进行分析、转换成辅助决策信息,是继数据库技术发展之后迅猛发展起来的一种新技术。(对)
16. 商业智能系统与一般交易系统之间在系统设计上的主要区别在于:后者把结构强加于商务之上,一旦系统设计完毕,其程序和规则不会轻易改变;而前者则是一个学习型系统,能自动适应商务不断变化的要求。(对)
17. 数据仓库中间层OLAP服务器只能采用关系型OLAP (错)
18.数据仓库系统的组成部分包括数据仓库,仓库管理,数据抽取,分析工具等四个部分. (错)

19. Web数据挖掘是通过数据库仲的一些属性来预测另一个属性,它在验证用户提出的假设过程中提取信息. (错)
21. 关联规则挖掘过程是发现满足最小支持度的所有项集代表的规则。(错)
22. 利用先验原理可以帮助减少频繁项集产生时需要探查的候选项个数(对)。
23. 先验原理可以表述为:如果一个项集是频繁的,那包含它的所有项集也是频繁的。(错
24. 如果规则 不满足置信度阈值,则形如的规则一定也不满足置信度阈值,其中 是X的子集。(对)
25. 具有较高的支持度的项集具有较高的置信度。(错)
26. 聚类(clustering)是这样的过程:它找出描述并区分数据类或概念的模型(或函数),以便能够使用模型预测类标记未知的对象类。 (错)
27. 分类和回归都可用于预测,分类的输出是离散的类别值,而回归的输出是连续数值。(对)

28. 对于SVM分类算法,待分样本集中的大部分样本不是支持向量,移去或者减少这些样本对分类结果没有影响。(对)
29. Bayes法是一种在已知后验概率与类条

件概率的情况下的模式分类方法,待分样本的分类结果取决于各类域中样本的全体。 (错)
30.分类模型的误差大致分为两种:训练误差(training error)和泛化误差(generalization error). (对)
31. 在决策树中,随着树中结点数变得太大,即使模型的训练误差还在继续减低,但是检验误差开始增大,这是出现了模型拟合不足的问题。(错)
32. SVM是这样一个分类器,他寻找具有最小边缘的超平面,因此它也经常被称为最小边缘分类器(minimal margin classifier) (错)
33. 在聚类分析当中,簇内的相似性越大,簇间的差别越大,聚类的效果就越差。(错)
34. 聚类分析可以看作是一种非监督的分类。(对)
35. K均值是一种产生划分聚类的基于密度的聚类算法,簇的个数由算法自动地确定。(错
36. 给定由两次运行K均值产生的两个不同的簇集,误差的平方和最大的那个应该被视为较优。(错)
37. 基于邻近度的离群点检测方法不能处理具有不同密度区域的数据集。(对)
38. 如果一个对象不强属于任何簇,那么该对象是基于聚类的离群点。(对)
39. 从点作为个体簇开始,每一步合并两个最接近的簇,这是一种分裂的层次聚类方法。(错)40. DBSCAN是相对抗噪声的,并且能够处理任意形状和大小的簇。(对)

普加搜索引擎面试题:

一、基本问答题:

1.冒泡和插入排序哪个快?快多少?

一样快(如果插入排序指的是直接插入排序的话)

一样快(如果插入排序指的是折半插入排序的话)

一样快(如果插入排序指的是二路插入排序的话)

一样快(如果插入排序指的是表插入排序的话)

插入排序快(如果插入排序指的是希尔插入排序的话)理论上快O(n^2)— O(n^1.3)。

2.请说明冒泡排序和插入排序的序列应用何种数据结构储存更好?分别对应着STL中哪个Tempelate?

冒泡排序用数组比较好,对应着template中的vector;

插入排序用链表比较好,对应着template中的deque。

3.在只有命令行的条件下,你喜欢怎样调试程序?

在linux平台下下用gcc进行编译,在windows平台下用cl.exe进行编译,用make工具根据目标文件上一次编译的时间和所依赖的源文件的更新时间自动判断应当编译哪些源文件,提高程序调试的效率。

4.数据的逻辑存储结构(如数组,队列,树等)对于软件开发具有十分重要的影响,试对你所了解的各种存储结构从运行速度、存储效率和适用场合等方面进行简要地分析。

运行速度

存储效率

适用场合

数组

比较适合进行查找操作,还有像类似于矩阵等的操作

链表

较快

较高

比较适合增删改频繁操作,动态的分配内存

队列

较快

较高

比较适合进行任务类等的调度

一般

较高

比较适合递归类程序的改写

二叉树(树)

较快

一般

一切具有层次关系的问题都可用树来描述

一般

一般

除了像最小生成树、最短路径、拓扑排序等经典用途。还被用于像神经网络等人工智能领域等等。

5.什么是分布式数据库?

分布式数据库系统是在集中式数据库系统成熟技术的基础上发展起来的,但不是简单地把集中式数据库分散地实现,它具有自己的性质和特征。集中式数据库系统的许多概念和技术,如数据独立性、数据共享和减少冗余度、并发控制、完整性、安全性和恢复等在分布式数据库系统中都有了不同的、更加丰富的内容。

6.写一段代码判断一个单向链表中是否有环。

给出如下结构

struct node

{

struct*next;

};

typedef stuct node Node;

算法说明:初始化两个指针,一个每次后移1个,一个后移2个。当第一个指针追上第二个指针时候就说明有环!

intfind_circle(Node* sll)

{

list fast = sll;

list slow = sll;

if (NULL == fast)

{

return -1;

}

while (fast && fast->next)

{

fast = fast->next->next;

slow = slow->next;

if (fast == slow)

{

return 1;

}

}

return 0;

}

7.谈谈HashMap和Hashtable的区别?

(1)HashTable的方法是同步的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。

(2)HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。

(3)HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。

(4)HashTable使用Enumeration,HashMap使用Iterator。

(5)HashTable中hash数组默认大小是11,增加的方式是old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。

(6)哈希值的使用不同,HashTable直接使用对象的hashCode。

8.#include和#include“filename.h”有什么区别?

用 #include 格式来引用标准库的头文件(编译器将从标准库目录开始搜索)。

用 #include “filename.h” 格式来引用非标准库的头文件(编译器将从用户的工作目录开始搜索)。

二、进阶问答题:

1.有以下两个文件,请写出一个你觉得比较标准的Makefile文件:

CHello.cpp

#include

using namespace std;

class CHello

{

public:

void printHello()

{

cout<<"Hello World"<

HMM 概念原理(Viterbi算法)
BEMS序列组合
P(E|B) = 0.851, P(M|B) = 0.149,说明当我们处于一个词的开头时,下一个字是结尾的概率
要远高于下一个字是中间字的概率,符合我们的直觉,因为二个字的词比多个字的词更常见

Viterbi算法

KNN 概念
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性

NLTK 中文进度

CF(协同过滤)

CW(模型概念)

PMI值 的计算
衡量两个词的共现程度:PMI (Point mutual information) .

问神经网络的实现机制、目标函数的选取、怎么优化的、怎么处理文本、自然语言处理的方法、tesorflow的细节问题等

机器学习和数据挖掘常用的模型和公式,比如回归、HMM等。

1.什么是机器学习

机器学习是为了应对系统程序设计,属于计算机科学类的学科,它能根据经验进行自动学习和提高。例如:一个由程序操纵的机器人,它能根据从传感器搜集到的数据,完成一系列的任务和工作。它能根据数据自动地学习应用程序。

2.机器学习与数据挖掘的区别

机器语言是指在没有明确的程序指令的情况下,给予计算机学习能力,使它能自主的学习、设计和扩展相关算法。数据挖掘则是一种从非结构化数据里面提取知识或者未知的、人们感兴趣的图片。在这个过程中应用了机器学习算法。

3.什么是机器学习的过度拟合现象

在机器学习中,当一个统计模型首先描述随机误差或噪声,而不是自身的基本关系时,过度拟合就会出现。当一个模型是过于复杂,过拟合通常容易被发现,因为相对于训练数据类型的数量,参数的数量过于五花八门。那么这个模型由于过度拟合而效果不佳。

4.过度拟合产生的原因

由于用于训练模型的标准并不等同于判断模型效率的标准,这导致了产生过度拟合的可能性。

5.如何避免过度拟合

当你使用较小的数据集进行机器学习时,容易产生过度拟合,因此使用较大的数据量能避免过度拟合现象。但是,当你不得不使用小型数据集进行建模时,可以使用被称为交叉验证的技术。在这种方法中数据集被分成两节,测试和训练数据集,测试数据集只测试模型,而在训练数据集中,数据点被用来建模。

在该技术中,一个模型通常是被给定有先验知识的数据集(训练数据集)进行训练,没有先验知识的数据集进行测试。交叉验证的思想是:在训练阶段,定义一个数据集用来测试模型。

6.什么是感应式的机器学习?

感应机器学习涉及由实践进行学习的过程,能从一组可观测到的例子的尝试推导出普遍性规则。

7.什么是机器学习的五个流行的算法?

决策树2. 神经网络(反向传播)3. 概率网络4.最邻近法5. 支持向量机
8.机器学习有哪些不同的算法技术?

在机器学习不同类型的算法技术是:

监督学习2.非监督学习3. 半监督学习4. 转导推理(Transduction)5.学习推理(Learning to Learn)。
9.在机器学习中,建立假设或者模型的三个阶段指的是什么?

1.建模2.模型测试3.模型应用。

10.什么是监督学习的标准方法?

监督学习的标准方法是将一组示例数据的分成训练数据集和测试数据集。

11.什么是训练数据集和测试数据集?

在类似于机器学习的各个信息科学相关领域中,一组数据被用来发现潜在的预测关系,称为“训练数据集”。训练数据集是提供给学习者的案例,而试验数据集是用于测试由学习者提出的假设关系的准确度。

12.下面列出机器学习的各种方法?

机器学习的各种方法如下“

1.概念与分类学习(Concept Vs Classification Learning)。

2.符号与统计学习(Symbolic Vs Statistical Learning)。

3.归纳与分析学习(Inductive Vs Analytical Learning)。

13.非机器学习有哪些类型?

人工智能、规则推理。

14.什么是非监督学习的功能?
1.求数据的集群2. 求出数据的低维表达3. 查找数据有趣的方向4. 有趣的坐标和相关性5.发现显著的观测值和数据集清理

15.什么是监督学习的功能?

1.分类、2.语音识别3.回归4.时间序列预测5. 注释字符串

16.什么是算法独立的机器学习?

机器学习在基础数学领域独立于任何特定分类器或者学习算法,被称为算法独立的机器学习。

17.人工智能与机器学习的区别?

基于经验数据的特性而设计和开发的算法被称为机器学习。而人工智能不但包括机器学习,还包括诸如知识表示,自然语言处理,规划,机器人技术等其它方法。

18.在机器学习中分类器指的是什么?

在机器学习中,分类器是指输入离散或连续特征值的向量,并输出单个离散值或者类型的系统。

19.朴素贝叶斯方法的优势是什么?

朴素贝叶斯分类器将会比判别模型,譬如逻辑回归收敛得更快,因此你只需要更少的训练数据。其主要缺点是它学习不了特征间的交互关系。

20.在哪些领域使用模式识别技术?

模式识别被应用在:

计算机视觉2.语言识别3.统计4.数据挖掘5. 非正式检索6. 生物信息学。
21.什么是遗传编程?

遗传编程的机器学习中两种常用的方法之一。该模型是基于测试,并在一系列的结果当中,获取最佳选择。

22.在机器学习中归纳逻辑程序设计是指什么?

归纳逻辑程序设计(ILP)是利用逻辑程序设计表达的背景知识和实例,它是机器学习的一个分支。

23.在机器学习中,模型的选择是指?

在不同的数学模型中,选择用于描述相同的数据集的模型的过程被称为模型选择。模型选择吧被应用于统计,机器学习和数据挖掘的等相关领域。
24.用于监督学习校准两种方法是什么?

在监督学习中,用于预测良好概率的两种方法是:

普拉特校准,2. 保序回归。
这些方法被设计为二元分类,而且有意义的。
25. 什么方法通常用于防止过拟合?

当有足够的数据进行等渗回归时,这通常被用来防止过拟合问题。

26.规则学习的启发式方法和决策树的启发式方法之间的区别是什么?

决策树的启发式方法评价的是一系列不相交的集合的平均质量;然而规则学习的启发式方法仅仅评价在候选规则覆盖下的实例集。

27.什么是感知机器学习?

在机器学习,感知器是一种输入到几个可能的非二进制输出的监督分类算法。

28.贝叶斯逻辑程序的两个组成部分是什么?

贝叶斯逻辑程序由两部分组成。第一成分由一组贝叶斯条款组成,能捕捉特定域的定性结构。第二组分是定量的,它能对域的量化信息进行编码。

29.什么是贝叶斯网络?

贝叶斯网络是用来表示一组变量之间为概率关系的图像模型。

30.为什么基于实例的学习算法有时也被称为懒惰学习算法?

基于实例的学习算法也被称为懒惰学习算法,因为它们延缓诱导或泛化过程,直到分类完成。

31.支持向量机能处理哪两种分类方法?

1.结合二分类法2. 修改二进制纳入多类学习法。

32.什么是集成学习?

为了解决特定的计算程序,如分类器或专家知识等多种模式,进行战略性生产和组合。这个过程被称为集成学习。

33.为什么集成学习被应用?

集成学习能提高模型的分类,预测,函数逼近等方面的精度。

34.什么使用集成学习?

当你构建一个更准确,相互独立的分类器时,使用集成学习。

35.什么是集成方法的两种范式?

集成方法的两种范式是:

连续集成方法2. 并行集成方法。
36.什么是集成方法的一般原则,在集成方法中套袋(bagging)和爆发(boosting)指的是什么?

集成方法的一般原则是要结合定的学习算法多种预测模型,相对于单一模型,其有更强的健壮性。套袋是一种能提高易变的预测或分类方案集成方法。爆发方法被依次用来减少组合模型的偏差。爆发和装袋都可以通过降低方差减少误差。

37.什么是集成方法分类错误的偏置方差分解?

学习算法的期望误差可以分解为偏差和方差。偏置项衡量由学习方法产生的平均分类器与目标函数是否匹配。

38.在集成方法中什么是增量合成方法?

增量学习方法是一种从新数据进行学习,并能应用于后续由现有的数据集生成的分类器的算法。

39.PCA,KPCA和ICE如何使用?

PCA(主成分分析),KPCA(基于内核主成分分析)和ICA(独立成分分析)是用于降维的重要特征提取技术。

40.在机器学习中降维是什么意思?

在机器学习和统计应用中,降维是指在计算时减少随机变量数目的处理过程,并且可以分为特征选择和特征提取。

41.什么是支持向量机?

支持向量机是一种监督学习算法,适用于分类和回归分析。

42.关系评价技术的组成部分是什么?

关系评价技术的重要组成部分如下:

1.数据采集2. 地面实况采集3. 交叉验证技术4. 查询类型5. 评分标准6. 显着性检验。

43.连续监督学习有什么不同方法?

连续监督学习问题的不同解决办法如下:

滑动窗口方法2. 复发性推拉窗3. 隐藏马尔科夫模型4. 最大熵马尔科夫模型5. 条件随机域6. 图变换网络。
44.在机器人技术和信息处理技术的哪些方面会相继出现预测问题?

在机器人技术和信息处理技术中,相继出现预测问题的是:

模仿学习2. 结构预测3. 基于模型的强化学习。
45.什么是批量统计学习?

统计学习技术允许根据一组观察到的数据进行学习功能和预测,这可以对无法观察和未知的数据进行预测。这些技术提供的学习预测器对未来未知数据的预测提供性能保证。

46什么是PAC学习?

可能近似正确模型 (PAC) 学习是一个已经被引入到分析学习算法和统计效率的学习框架。

47有哪些不同的类别可以分为序列学习过程?

序列预测2. 序列生成3. 序列识别4. 顺序决定.

48什么是序列学习?

序列学习是一种以合乎逻辑的方式进行教学和学习的方法。

49.机器学习的两种技术是什么?

机器学习的两种技术是:
1.遗传编程2.归纳学习

50.你在日常工作中看到的机器学习的一个流行应用是什么?

各大电商网站上已部署好的推荐引擎使用的是机器学习。

计算机科学典型问题

1.如何判断一个而链表中是否有环?

2.给定一棵二叉查找树中的两个元素,求它们的最近公共祖先。
给一个栈排序

3.基于比较的排序算法的时间复杂度是什么?证明?

4.如何求一个带权图中两个结点直接按的最短路径?如果有些权值是负的怎么办?

5.求一个字符串中所有的回文子串。

对这些问题你都要能够推导你的解法的时间和空间复杂度(大 O 表示法),并且尽量用最低的复杂度解决。

只有通过大量的练习才能将这些不同类型的问题烂熟于胸,从而在面试中迅速地给出一个高效的解法。常用的算法面试准备平台有 InterviewBit、LeetCode、Interview Cake、Pramp、interviewing.io 等。

概率论和统计典型问题

1.给出一个群体中男性和女性各自的平均身高,求整个群体的平均身高。

2.一次调查表明意大利三分之一的汽车都是法拉利,并且在那之中一半的车都是红色的。如果你在意大利的街头看到一辆红色的汽车驶来,请问它是法拉利的可能性有多大?

3.你试图找出在自己的网站上放置版头的最佳方案。变量包括版头的尺寸(大、中、小)以及放置的位置(顶部、中间、底部)。假定需要 95% 的置信水平,请问你至少需要多少次访问和点击来确定某个方案比其他的组合都要好?

很多机器学习算法都以概率论和统计作为理论基础。对于这些基础知识有清晰的概念是极为重要的。当然同时你也要能够将这些抽象的概念与现实联系起来。

数据建模和评估典型问题

1.一位农民想搞明白是什么因素影响了他的牛奶产量。他记录了每天的气温(30 – 40 度)、湿度(60 – 90%)、饲料消耗(2000 – 2500 千克)以及牛奶产量(500 – 1000 升)。
1-1.假设问题是要预测每天的牛奶产量,你会如何处理数据并建立模型?
1-2.这是一个什么类型的机器学习问题?

2.你的公司在开发一个面部表情识别系统。这个系统接受 1920 x 1080 的图片作为输入,并告诉用户图片中的人脸处于以下哪种情绪状态:平常、高兴、悲伤、愤怒和恐惧。当图片中没有人脸时系统要能够分辨这种情况。
2-1这是一个什么类型的机器学习问题?
2-2如果每个像素点由 3 个值来表示(RGB),那么输入数据的原始维度有多大?有办法降维吗?
2-3如何对系统的输出进行编码?为什么?

3.过去几个世纪的气象数据展现出一种循环的气温模式:一会升高一会下降。对于这样的数据(一个年平均气温的序列),你会如何建模并预测未来 5 年的平均气温?
4
4.你在一家在线新闻网站工作,需要从各处收集文本,并将不同来源的内容聚集成一篇报道。你会如何设计这样一个系统?会用到哪些机器学习技术?

应用机器学习算法和库

1.你用一个给定的数据集训练一个单隐层的神经网络,发现网络的权值在训练中强烈地震荡(有时在负值和正值之间变化)。为了解决这个问题你需要调整哪个参数?

2.支持向量机的训练在本质上是在最优化哪个值?

3.LASSO 回归用 L1-norm 作为惩罚项,而岭回归(Ridge Regression)则使用 L2-norm 作为惩罚项。这两者哪个更有可能得到一个稀疏(某些项的系数为 0)的模型?

4.在用反向传播法训练一个 10 层的神经网络时,你发现前 3 层的权值完全没有变化,而 4 ~ 6 层的权值则变化得非常慢。这是为什么?如何解决?

5.你手上有一个关于小麦产出的数据集,包括年降雨量 R、平均海拔 A 以及小麦产量 O。你经过初步分析认为产量跟年降雨量的平方以及平均海报的对数之间存在关系,即:O = β_0 + β_1 x R^2 + β_2 x log(A)。能用线性回归求出系数 β 吗?

你可以通过像 Kaggle 比赛那样的数据科学和机器学习挑战来了解各种各样的问题和它们之间的细微差别。多多参加这些比赛,并尝试应用不同的机器学习模型。

软件工程和系统设计典型问题

1.你有一个电商网站,当用户点击一个商品打开详情页面时,你想基于商品特征和用户的购买历史为用户推荐 5 个其他的商品显示在页面的底部。你需要哪些服务和数据表来实现这个功能?请写一个查询语句或一段过程式代码来返回所要推荐的 5 个商品。

2.对于 YouTube 那样的在线视频网站,你会收集哪些数据来衡量用户的参与度和视频的人气度?

3.一个简单的垃圾邮件检测系统是这样的:它每次处理一封邮件,统计不同单词的出现频率(Termfrequency),并将这些频率与之前已经被标注为垃圾 / 正常邮件的那些频率进行比较。现在需要对这系统进行拓展来处理海量的邮件流量,请设计一个 Map-Reduce 方案在一个集群上部署这个系统。

4.你要生成一个实时的热力图,来展示用户正在浏览和点击一个网页的哪些部分。在客户端和服务端分别需要哪些组件 / 服务 / API 来实现这个功能?

一、简答题
1.深度神经网络目前有哪些成功的应用?简述原因。(10分)

2 列举不同进程共享数据的方式(至少三种)。
管道(pipe)、命名管道(named pipe)、信号(signal)、信号量(semaphore)、套接字(socket)、消息队列(message queue)、共享内存和内存映射(mapped memeory)。

3 对于N个样本,每个样本为D维向量,采用欧式距离使用KNN做类预测。(10分)

1).给出预测时间复杂度。
2).当N很大时,有哪些方法可以降低复杂度?
3).k取值的大小对预测方差和偏差有何影响?
现在看来N应该是训练集的样本数,时间复杂度是指的分类一个样本需要的时间。

(1)KNN分类的的思想是,计算待分类样本与训练集中所有样本的距离,找出距离最小的k个,计算那个标签出现的次数最多,将出现最多的标签作为样本的标签。计算距离的复杂度是O(M*D),排序最快得是O(M*log(M)),找出现最多的标签的复杂度是K。因此总的时间复杂度是O(N*D+N*log(N)+K))。

(2)KNN比较费时的步骤在于要计算与训练集中每一个样本的距离,为了减少计算量,可以每次从训练集中随机地选取一部分样本进行,作为分类的依据。假设每次取T个点,则时间复杂度变为O((T*D+T*log(T)+K))。当N很大时,选取的T可以远远小于N。
(3)记样本的真实标签为Y,分类结果记为X,X是随机变量,可以取训练集中所有出现的类标签。

如果K=N,则任意Y,X|Y=训练集中包含样本数最多的类的标签。

如果K=1,则分类结果是离待分类样本最近的训练集中的样本的类的标签。

现在,仍然没有梳理出这里的方差和偏差指的是什么?

二、算法和程序设计

1.给出一个数据A=[a_0, a_1, a-2, … a_n](其中n可变),打印出该数值元素的所有组合。(15分)
思路是,首先将从小到大排序,记包含k个元素组合的集合为G(k)。
如果知道G(k-1),则采用以下方式生成G(k):{s in G(k)} U{t,t in A且t 大于s中的最大值}。

2.有这样一个数组A,大小为n,相邻元素差的绝对值都是1,如A={4,5,6,5,6,7,8,9,10,9}。现在给定数组A和目标整数t,请找到t在数组中的位置。(15分)
思路是,用一指针p遍历数组,首先计算当前位置与t的绝对值s,然后移动到p+s处,比较p+s指的元素与t是否相等,若相等,输出当前下标,若不相等,重复计算绝对值、移动,比较步骤。

3. 在平面上有一组间距为d的平行线,将一根长度为l(l<d)的针任意掷在这个平面上,求此针与平行线中任意一根相交的概率,用高等数学(微积分、概率的方法)求解,基于布丰投针的结论,任选一种编程语言(C/C++, matlab, python, java),写出模拟投针实验(程序中允许把一个理想的Pi作为常量使用),求解圆周率
答案为2*l/(pi*d).

三、系统设计题(两题中任选一题作答,25分

2.关于K-means聚类算法,请回答以下问题:

1).写出将N个样本X=(x1, … xN)聚类成k类的k_means聚类算法的优化目标;
sum_{i=1到K} sum_{x in C_i} dist(x,c_i)
其中C_i表示属于第i簇的点的集合,c_i表示C_i的质心。

2).描述K-means终止的常用条件;
质心不再发生变化,或者只有1%的点属于的簇发生了变化。

3).以Kmeans算法为例,描述Expectation-Maximization(EM)算法的基本原理与步骤。
4).用伪代码给出基于MPI或者HADOOP的Kmeans并行算法

谈一下我今天参加完后的感受吧,首先神经网络很重要,他们也很关注这个方面的应用。还有就是很深厚的数学背景,对矩阵,线代,和概率论等知识考察的比较多。

一、简答题

1、目前深度神经网络有哪些成功的应用,简述其适用原因。
看图识别花朵 植物,机器翻译

2、不同进程之间进行通信的方式有哪些?(至少列出三种)

管道(pipe)、命名管道(named pipe)、信号(signal)、信号量(semaphore)、套接字(socket)、消息队列(message queue)、共享内存和内存映射(mapped memeory)。

3、有N个样本,每个样本都是D维的,使用KNN分类算法,采用欧式距离,(1)其时间复杂度为多少?(2)当N很大时,可以使用什么方法进行优化?(3)K的值对预测的方差和偏差的影响是什么?

现在看来N应该是训练集的样本数,时间复杂度是指的分类一个样本需要的时间。

(1)KNN分类的的思想是,计算待分类样本与训练集中所有样本的距离,找出距离最小的k个,计算那个标签出现的次数最多,将出现最多的标签作为样本的标签。计算距离的复杂度是O(M*D),排序最快得是O(M*log(M)),找出现最多的标签的复杂度是K。因此总的时间复杂度是O(N*D+N*log(N)+K))。

(2)KNN比较费时的步骤在于要计算与训练集中每一个样本的距离,为了减少计算量,可以每次从训练集中随机地选取一部分样本进行,作为分类的依据。假设每次取T个点,则时间复杂度变为O((T*D+T*log(T)+K))。当N很大时,选取的T可以远远小于N。

(3)记样本的真实标签为Y,分类结果记为X,X是随机变量,可以取训练集中所有出现的类标签。

如果K=N,则任意Y,X|Y=训练集中包含样本数最多的类的标签。

如果K=1,则分类结果是离待分类样本最近的训练集中的样本的类的标签。

现在,仍然没有梳理出这里的方差和偏差指的是什么?

二、算法与程序设计题

1、给定数组A={a0,a1,a2,…,an}(n可变),请输出所有的组合。

思路是,首先将从小到大排序,记包含k个元素组合的集合为G(k)。

如果知道G(k-1),则采用以下方式生成G(k):{s in G(k)} U{t,t in A且t 大于s中的最大值}。

2、数组A中相邻两个数的差的绝对值为1,如{1,2,3,4,3,2,3,4,5,4,5,6,7},给定某一个数字t,求其在数组中的位置。

思路是,用一指针p遍历数组,首先计算当前位置与t的绝对值s,然后移动到p+s处,比较p+s指的元素与t是否相等,若相等,输出当前下标,若不相等,重复计算绝对值、移动,比较步骤。

3、布丰投针问题。平面上有一组距离为d的平行线,向其上任意地投一根长为l(l<d)的针,求该针与平行线相交的概率。

答案为2*l/(pi*d).

三、系统设计题

1、神经网络模型,要求计算1、2、3层的两个偏导数。

2、K-means聚类算法,

K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

(1)请写出目标优化函数。

sum_{i=1到K} sum_{x in C_i} dist(x,c_i)

其中C_i表示属于第i簇的点的集合,c_i表示C_i的质心。

(2)常用的终止条件有哪些?

质心不再发生变化,或者只有1%的点属于的簇发生了变化。

(3)结合K-means,描述EM算法的基本原理和步骤。

em算法,指的是最大期望算法(Expectation Maximization Algorithm,又译期望最大化算法),是一种迭代算法,在统计学中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计

最大期望算法经过两个步骤交替进行计算[2]  :
1)计算期望(E),利用概率模型参数的现有估计值,计算隐藏变量的期望;
2)最大化(M),利用E 步上求得的隐藏变量的期望,对参数模型进行最大似然估计。
3)M 步上找到的参数估计值被用于下一个 E 步计算中,这个过程不断交替进行。
总体来说,EM的算法流程如下:
1.初始化分布参数
2.重复直到收敛:
E步骤:估计未知参数的期望值,给出当前的参数估计。
M步骤:重新估计分布参数,以使得数据的似然性最大,给出未知变量的期望估计。

(4)使用MPI 或MapReduce,如何进行并行。

1. 实现归并排序。
插入排序:

def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

 

def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count: k = j - group key = lists[j] while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

 

def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

 

def quick_sort(lists, left, right):
    # 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

 

def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists

 

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)
 
def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)
 
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

 

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
 
def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

 

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

 


 


 

2. 二叉树的S型遍历。

第一层从左到右,第二层从左到右,第三层从左到右……

# -*- coding: utf-8 -*-

"""
Created on Mon Apr 03 19:58:58 2017

@author: Administrator
"""
class node(object):
    def __init__(self,data=None,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right
       
#深度
def depth(tree):
    if tree==None:
        return 0
    left,right=depth(tree.left),depth(tree.right)
    return max(left,right)+1
#前序遍历   
def pre_order(tree):
    if tree==None:
        return
    print tree.data
    pre_order(tree.left)
    pre_order(tree.right)
#中序遍历   
def mid_order(tree):
    if tree==None:
        return
    mid_order(tree.left)
    print tree.data
    mid_order(tree.right)    
#后序遍历   
def post_order(tree):
    if tree==None:
        return
    post_order(tree.left)
    post_order(tree.right)   
    print tree.data
    
#层次遍历    
def level_order(tree):
     if tree==None:
        return 
     q=[]
     q.append(tree)
     while q:
         current=q.pop(0)
         print current.data
         if current.left!=None:
            q.append(current.left)
         if current.right!=None:
            q.append(current.right)
#按层次打印
def level2_order(tree):
     if tree==None:
        return 
     q=[]
     q.append(tree)
     results={}
     level=0
     current_level_num=1
     nextlevelnum=0
     d=[]
     while q: 
         current=q.pop(0)
         current_level_num-=1
         d.append(current.data)
         if current.left!=None:
            q.append(current.left) 
            nextlevelnum+=1
         if current.right!=None:
            q.append(current.right) 
            nextlevelnum+=1   
         if current_level_num==0:
            current_level_num=nextlevelnum
            nextlevelnum=0
            results[level]=d
            d=[]
            level+=1
     print results    
     
if __name__=='__main__':  
    tree=node('D',node('B',node('A'),node('C')),node('E',right=node('G',node('F'))))  
    print'前序遍历:'  
    pre_order(tree)  
    print('\n')  
    print('中序遍历:')  
    mid_order(tree)  
    print('\n')  
    print '后序遍历:'  
    post_order(tree)  
    print('\n')  
    print "层次遍历"
    level2_order(tree)

 

3. 20亿url的存在一个文本中,一个url占一行,其中有重复,统计出url的频率。

这里写图片描述

一百个灯泡排成一排,第一轮将所有灯泡打开;第二轮每隔一个灯泡关掉一个,即排在偶数的灯泡都被关掉。第三轮每隔两个灯泡,将开着的灯泡关掉,关掉的灯泡打开。以此类推,第100轮结束的时候,还有几盏灯泡亮着。编写代码实现。(15分)

#include<stdio.h>
bool lights[100] = {0};
int main()
{
int n,step,i,numLighted = 0;
scanf("%i",&n);
for(step=1;step<=n;step++)
for(i=0;i<100;i+=step)
lights[i] ^= 1;
for(i=0;i<100;i++)
if(lights[i])
numLighted++;
printf("%i",numLighted);
return 0;
}

 

有一个百万级的字符串集合(worddic),worddict中每个字符串的长度为2~5个汉字。对任意一个查询串(query),定义该query对worddic模糊匹配的条件为:该query内部移除最多6个连续汉字后,与worddic中某个词完全匹配。例如:worddic中有”百度公司”这个字符串,query”北京百度网络技术有限公司”,该query即可通过移除6个连续字符(‘网络技术有限’)来匹配”百度公司”;

1.拼写纠错是搜索引擎具备的一个功能,指的是自动分析用户输入的查询(query),检查是否有拼写错误,如果有,则给出正确的拼写建议。例如:把”联想手机”输错为”联想手机”。这时候搜索引擎一般会给出提示”您要找的是不是:联想手机”。
一般来说,拼写纠错主要包括了两个重要的步骤:一是识别用户输入的错误的词语;二是把错误的词语修改成正确的词语。
问题:1)在中文中,常见的错误输入是同音不同字:例如,”苹果”输错为”平果”;在英文中,常见的错误输入时拼写错误,如”latest”错输为”latst”。针对以上两种在中文和英文输入中的错误,请分别给出一种解决方案。
2)用户输入的查询,常常还包含一些上下文的信息(如,”平果手机什么时候发布”),如何利用这些上下文改进纠错的效果?

现在各大流行的搜索引擎几乎都具备一个功能,那就是提供拼写纠错功能。用户将查询的关键词提交给搜索引擎之后,搜索引擎便开始分析用户的输入,检查用户的拼写是否有错误,如果有的话,给出正确的拼写建议。也就是说,搜索引擎的拼写纠错功能,要完成两部分的工作,首先,对用户输入的查询进行处理,判断是否有拼写错误,接着,对于有拼写错误的查询输入,给出正确词汇的提示。因为中文的拼写纠错涉及到中文分词等复杂逻辑,所以本文只对英文的拼写纠错进行讨论。
1 英文单词纠错法
常见的英文单词纠错法,主要有以下几种:误拼词典法、最小编辑距离法、词干法,N-gram法和基于规则的技术等,下面我们对这些英文单词纠错法逐个进行介绍。
(1)误拼字典法。这种方法可以理解成穷举法,通过收集大规模真实文本中拼写出错的英文单词并给出相应的正确拼写,建造一个无歧义的误拼字典。在进行英文单词拼写检查时,查找误拼字典,如命中,则说明该单词拼写有误,该词的正确拼写字段为纠错建议。比如在搜索引擎的实现中,通过记录日志的形式,把所有用户的输入都记录下来,提取有拼写错误的输入,形成误拼词典。该方法的特点是算法简单,效率高。但英文拼写错误具有随机性,很难保证误拼字典的无歧义性和全面性,因此查准率低、校对效果差;而且,对于搜索引擎用户海量的误拼输入,空间复杂度也是需要考虑的问题。
(2)最小编辑距离法。通过计算误拼字符串与词典中某个词间的最小编辑距离来确定纠错候选词。所谓最小编辑距离是指将一个词串转换为另一个词串所需的最少的编辑操作次数。在编辑操作中,可以将单次的编辑动作归纳为三种:插入字符、删除字符和替换字符;考虑到在实际计算机输入过程中,字符的颠倒异位也是常见的错误,我们将颠倒异位也算作一种编辑动作。还有人提出了反向最小编辑距离法,这种方法首先对每个可能的单个错误按照编辑距离进行搜索,生成一个候选集,然后,通过查词典看哪些是有效的单词,并将这些有效的单词作为误拼字符串的纠错建议。
(3)词干法。通过构建词干词典,在英文单词出现错误时,先抽取出该错误单词的词干,然后再去查词干词典,将词典中与该单词具有相同词干的正确单词作为该单词的纠错建议。这种方法主要的难度在于构建词干词典上,需要对几乎所有的英文单词都进行分析,提取出每个单词的词干,或者称为骨架词;这种实现的工作量是巨大的,而且词干的选择非常重要,每个词干要有很好的区分度,才能给用户给出良好的纠错建议。

(4)N-gram法。基于n元文法,通过对大规模英文文本的统计得到单词与单词问的转移概率矩阵。当检测到某英文单词不在词典中时。查转移概率矩阵,取转移概率大于某给定阈值的单词为纠错建议。

(5)基于规则的技术。利用规则的形式将通常的拼写错误模式进行表示,这些规则可用来将拼写错误的单词转换为正确有效的单词。对于一个误拼字符串,应用所有合适的规则从词典中找到一些与之对应的单词作为候选结果;然后,对每个结果根据事先赋予生成它的规则的概率估计计算一个数值,依据这个数值对所有候选结果进行排序,把将排序靠前的结果当成纠错结果返回给用户。

通过对这些现有的英文单词纠错法的分析,我们选定反向最小编辑距离法作为拼写纠错功能的实现方式,进行分析然后给出C++的实现。

2 拼写纠错功能的实现
搜索引擎如何判断用户的输入是否有拼写错误呢?通过分析现有的著名搜索引擎的行为,我想应该是查词典的方式。每个搜索引擎维护一个关键词的词典,对于用户的输入,检查它是否在词典中。如果词典中有这个词条,则直接返回搜索结果;如果发现这个用户输入的词并不包含在词典里边,那么它很有可能是一个错误的输入,于是马上触发拼写纠错功能,对用户提供拼写建议。我们很容易就能在Google或者百度这样的搜索引擎中验证这个猜想,在搜索框里输入一个正常的词,比如“Microsoft”,搜索引擎不会有错误提示;而你故意输入一个词典不包括的词,比如“Micorsoft”,搜索引擎会提示你正确的搜索词汇。

2.1 字典的数据结构
字典的数据结构,大多数情况下,比照C++ STL中的map,我们会想到两种实现途径,首先是二叉树,其次是哈希表。对于哈希表,在选取恰当的哈希函数的情况下,它的理论查找效率是O(1),这看起来是个不错的选择,事实上哈希表已经用作在一些搜索引擎中[1]。于是我们可以在训练搜索引擎的过程中,把所有的常用词都输入到这个词典中,然后就能够用很高的效率进行搜索。但是这种方法带来一个问题,词典里的单词量通常是非常巨大的,每一个单词都需要完整的存储,随着时间的推移,这种实现需要的内存空间也会变得越来越大。

在二叉树的实现中,我们可以把所有的单词都保存在二叉树的节点中,但这样需要的空间几乎可以肯定不会比哈希表的方式少,除了存储单词的空间,还需要额外的实现二叉树的空间,况且搜索的时间复杂度是O(logn),所以我们需要对这种方式进行优化。所有的单词还是存储在二叉树结构中,但是每个节点仅保存一个字符,每个节点可以有两个子节点,其中左子节点表示当前字符的兄弟(Sibling), 说明有多个单词存在相同的前缀,右子节点表示当前字符的后续字符(Next),图1说明了我们如何将“ape”、“apple”和“applet”这三个词存储起来。利用这种存储方法,我们可以高效率地将有相同前缀的词存储在同一棵子树中。

图1 字典的存储结构

2.2 二叉树的创建与查找
创建或者将新词插入这棵二叉树的算法,可以由递归来实现:

1.从根节点开始。
2.如果当前节点保存的字符和当前插入字符相同,则递归进入下一层,把后续节点作为当前节点,再处理下一个字符。
3.如果当前节点保存的字符和当前插入字符不相同,检查Sibling节点是否存在,如果存在则进入Sibling节点。否则,创建Sibling节点,把当前插入字符保存在Sibling中,同时进入下一层,把Sibling作为当前节点,再处理下一个字符。
4.如果当前节点没有Next节点,则创建一个节点作为Next节点,把当前插入字符保存在Next节点中,同时进入下一层,把Next作为当前节点,再处理下一个字符。
5.递归的结束条件是遇到了字符串结束符(\0),在插入\0之后返回。

查找一个词是否在字典中的算法则很简单:

1. 比较当前节点和当前检查的字符,如果相同则进入Next节点子树,当前检查字符的指针加一,否则,判断是否有Sibling,如果有则进入Sibling子树,否则说明不存在这个单词,直接返回。
2.结束的条件是遇到了字符串结束符,且当前检查字符为\0。
3. 为了实现模式匹配,我们还支持?号作为通配符的查找,用以返回所有符合模式的单词。

2.3 给出拼写建议
前面我们提到最小编辑距离法中,需要对用户输入的误拼字符串按照编辑距离进行搜索并形成候选集,然后在字典中查找后选的单词。如果存在,则说明是个有效的单词,可以作为拼写建议提供给用户。我们只考虑编辑距离为1的情况,如果编辑距离更大的话,返回的结果太多,反而影响拼写建议的准确度。

我们按照编辑操作来枚举生成候选集模式。比如对于误拼字符串abc,删除字符可以产生ab、ac和bc;插入字符可以产生?abc、a?bc、ab?c和abc?;替换字符可以产生?bc、a?c和ab?;将字符颠倒可以产生bac和acb。然后,我们将这些候选模式放到二叉树中去搜索,就可以返回匹配的候选单词集合。
候选单词集中包含有我们需要提供给用户的拼写建议,但是我们不能这样直接给用户。首先,候选单词集中可能存在重复的单词,其次存在多个单词的情况下,如何才能把最准确的拼写建议返回给用户。第一个问题,我们可以通过过滤逻辑去除重复;而第二个问题,我想不同的搜索引擎都有自己不同的实现,比如可以按照单词的优先级返回,分析用户查询日志,查询次数越多的单词优先级越高。
3 结论
本文对搜索引擎的拼写纠错功能进行了讨论,然后选择最小编辑距离法来进行用户误拼输入的纠错,提供了一个可行的方法和具体的实现逻辑。
 

1.自然语言处理中的前向匹配常被用于分词。如
遥远的古巴比伦
前向匹配分词结果为
遥远的|古巴|比伦
前向匹配分词结果为:
遥|远的|古|巴比伦
要求写出前向匹配的接口及实现方法。

  1. BP算法中,输出层节点的误差计算与隐层节点的误差计算是不同的,输出层节点的误差计算公式为 1,隐层节点的误差计算公式为 2 。

 

2.   学校图书馆共有300万册图书,想统计其中Computer,Science,计算机,科学这几个词出现的次数,并按照自然年度分类,如2016年出版的书籍中这几个词各自出现的次数,2015年······依次类推。

将每本书都存在hdfs里作为一个文件,文件名为 时间(4位年份)+书的id+书的名称。
使用mapreduce进行运算,map输出为<日期,computer次数;science次数;计算机次数;科学次数>,reduce输出同样,不过作为value的字符串中的次数为总次数。代码如下:
    public static class MyMapper extends Mapper<LongWritable,Text,Text,Text>{       
        
        private static Text outputKey = new Text();
        private static Text outputValue = new Text();
   
        @Override
        protected void map(LongWritable key, Text value, Context context)
                throws IOException, InterruptedException { 
        //得到hdfs文件名
        String filename = ((FileSplit) context.getInputSplit()).getPath().getName();
        String date = filename.substring(0, 4);
       
        //分别统计computer,science,计算机,科学出现的次数
        int computer = 0;
        int science = 0;
        int jisuanji = 0;
        int kexue = 0;
       
        String line = value.toString();
        String[] words = line.split(" ");
        for(String s:words){
        if(s.equals("computer")) computer++;
        if(s.equals("science")) science++;
        if(s.equals("计算机")) jisuanji++;
        if(s.equals("科学")) kexue++;
        }
       
        String outputVal = "" + computer + ";" + science + ";" + jisuanji + ";" + kexue;
        outputKey.set(date);
        outputValue.set(outputVal);
        context.write(outputKey, outputValue);
                             
        }
  }
    
    public static class MyReducer extends Reducer<Text, Text, Text, Text> {

    @Override
protected void reduce(Text key, Iterable<Text> values,Context context)
throws IOException, InterruptedException {
    int allComputer = 0;
    int allScience = 0;
    int allJisuanji = 0;
    int allKexue = 0;
   
    for(Text value:values){
    String val = value.toString();
    String[] str = val.split(";");
    allComputer += Integer.parseInt(str[0]);
    allScience += Integer.parseInt(str[1]);
    allJisuanji += Integer.parseInt(str[2]);
    allKexue += Integer.parseInt(str[3]);
    }
   
    String finalVal = "" + allComputer + ";" + allScience + ";" + allJisuanji + ";" + allKexue;
    context.write(key, new Text(finalVal));    
    } 
  }

以下描述错误的是:

  • SVM是这样一个分类器,他寻找具有最小边缘的超平面,因此它也经常被称为最小边缘分类器(minimal margin classifier)
  • 在聚类分析当中,簇内的相似性越大,簇间的差别越大,聚类的效果就越差。
  • 在决策树中,随着树中结点数变得太大,即使模型的训练误差还在继续减低,但是检验误差开始增大,这是出现了模型拟合不足的问题。
  • 聚类分析可以看作是一种非监督的分类。
1、SVM的策略就是最大间隔分类器
2、簇内的相似性越大,簇间的差别越大,聚类的效果就越好。你想啊,分类或者聚类效果的好坏其实就看同一类中的样本相似度,当然是越高越好,说明你分类越准确。
3、训练误差减少与测试误差逐渐增大,是明显的过拟合的特征。

SPSS中,数据整理的功能主要集中在( )等菜单中

  • 数据
  • 直销
  • 分析
  • 转换
数据和转换

在某些规划的分类器中,依据规划质量的某种度量对规划排序,保证每一个测试记录都是由覆盖它的‘最好的’规格来分类,这种方案称为()

  • 基于规格的排序方案
  • 基于度量的排序方案
  • 基于规则的排序方案 C
  • 基于类的排序方案

 

宽度优先算法中,新生成的节点会怎样处理(            )

  • 插入OPEN表的前端
  • 插入OPEN表的末端
  • 计算估价函数值
  • 继续扩展出后继节点

    a

 

假定某同学使用Naive Bayesian(NB)分类模型时,不小心将训练数据的两个维度搞重复了,那么关于NB的说法中正确的是:

  • 这个被重复的特征在模型中的决定作用会被加强
  • 模型效果相比无重复特征的情况下精确度会降低
  • 如果所有特征都被重复一遍,得到的模型预测结果相对于不重复的情况下的模型预测结果一样。
  • 当两列特征高度相关时,无法用两列特征相同时所得到的结论来分析问题
  • NB可以用来做最小二乘回归
  • 以上说法都不正确
朴素贝叶斯是对于给定训练数据集,训练得出联合概率分布,再通过x利用贝叶斯定理求出后验概率最大的输出y。
B:维度重复时,习得的联合概率分布有误,所以精确度会降低。
D:不太明白
决定神经网络的三个主要因素是 1 、 2 和 3 。
阈值,隐藏层层数,节点数

在spss的基础分析模块中,作用是“以行列表的形式揭示数据之间的关系”的是( )

  • 数据描述
  • 相关
  • 交叉表
  • 多重相应

    spss中交叉分析主要用来检验两个变量之间是否存在关系,或者说是否独立,其零假设为两个变量之间没有关系。在实际工作中,经常用交叉表来分析比例是否相等。例如分析不同的性别对不同的报纸的选择有什么不同。

 

 

Apriori算法的计算复杂度受()影响

  • 项数(维度)
  • 事务平均宽度
  • 事务数
  • 支持度阀值
    D,较低支持度阈值会使得频繁项变多,从而增加计算复杂度

    ABCD是会影响复杂度,但是如果单选感觉D更正确。 因为例如A,维度变多其实存在于是存储变大,但是如果支持度阀值本来很大,多余的维度可能在第一次就被剔除掉,感觉之后就并不会影响计算量了。而且支持度阀值的改变,是直接影响存在频繁项的多少问题。  当然这只是个人看法,感觉应该ABCD更为合理。

 

 

输入图片大小为200×200,依次经过一层卷积(kernel size 5×5,padding 1,stride 2),pooling(kernel size 3×3,padding 0,stride 1),又一层卷积(kernel size 3×3,padding 1,stride 1)之后,输出特征图大小为:

  • 95
  • 96
  • 97  C
  • 98
  • 99
  • 100

输出尺寸=(输入尺寸-filter尺寸+2*padding)/stride+1
宽和高都是这么计算的;结果是97,答案应该有问题的

1层卷积:
(200-5+2)/2+1=99
池化:
(99-3)+1=97
2层卷积:
(97-3+2)/1+1=97

 

隐马尔可夫模型三个基本问题以及相应的算法说法正确的是( )

  • 评估—前向后向算法
  • 解码—维特比算法
  • 学习—Baum-Welch算法
  • 学习—前向后向算法

正确答案:A B C

针对以下三个问题,人们提出了相应的算法
*1 评估问题: 前向算法
*2 解码问题: Viterbi算法
*3 学习问题: Baum-Welch算法(向前向后算法)

 

 

链接:https://www.nowcoder.com/questionTerminal/e4094a58079c43b7b7b233134c6aee6a?mutiTagIds=645_631&orderByHotValue=1
来源:牛客网

考虑如下数据集,其中Customer ID(顾客id),Transaction ID(事务id),Items Bought(购买项)。如果将每个事务id看成一个购物篮,计算项集{e}, {b, d}, {b, d, e}的支持度:

  • s({e}) =0.8s({b, d})= 0.2s({b, d, e})= 0.2
  • s({e}) =0.7s({b, d})= 0.3s({b, d, e})= 0.3
  • s({e}) =0.6s({b, d})= 0.4s({b, d, e})= 0.3
  • s({e}) =0.8s({b, d})= 0.1s({b, d, e})= 0.1
    正确答案:A

 

一般,k-NN最近邻方法在( )的情况下效果较好

  • 样本较多但典型性不好
  • 样本较少但典型性好
  • 样本呈团状分布
  • 样本呈链状分布
    正确答案:B

某学校对入学的新生进行性格问卷调查,没有心理学家的参与,根据学生对问题的回答,把学生的性格分成了 8 个类别。请说明该数据挖掘任务是属于分类任务还是聚类任务?为什么?并利用该例说明聚类分析和分类分析的异同点。

聚类任务,因为没有明确的标签说明这8类性格具体是什么性格,所以是按照相关性聚成8种不同的类的聚类任务,分类与聚类之间的区别是所得的类是否有明确标签(教师信号),若是有明确的标签则为分类,去明确属性标签仅根据其相关性得到所需类别结果则为聚类。(个人理解是这样的)

 

 

链接:https://www.nowcoder.com/questionTerminal/a58dd8a14a2b41c3ab650a727028e99d?mutiTagIds=645_631&orderByHotValue=1
来源:牛客网

如下表所示的数据集。请写出按属性A和B划分时的信息增益的计算表达式。不需要计算出最后结果。并回答计算信息增益在分类算法中的作用。

A B 类标号
T F *
T T *
T T *
T F #
T T *
F F #
F F #
F F #
T #
T F #

 

 

 

信息增益表示特征X使得类y的不确定性减少的程度
SPSS的界面中,以下是主窗口是( )

  • 语法编辑窗口
  • 数据编辑窗口
  • 结果输出窗口
  • 脚本编辑窗口

    正确答案:B

 

 

 

 

 

画出如下数据的FP树,并按支持度阈值是2找到频繁项集。

序号

事务
1 M,O,N,K,E,Y
2 D,O,N,K,E,Y
3 M,A,K,E
4 M,U,C,K,Y
5 C,O,K,I,E
6 Y,M,K,O

 

 
classprogram
 {
     staticvoidMain(string[] args)
     {
         inti;
         i = x(x(8));
     }
     staticintx(intn)
     {
         if(n <= 3)
             return1;
         else
             returnx(n - 2) + x(n - 4) + 1;
     }
 }
递归算法x(x(8))需要调用几次函数x(int n)?
 18 次
选C: 18次
根据题意,易得x(3) = x(2) = x(1) = x(0) = 1
x(8) = x(6) +x(4) +1
       = x(4) + x(2) +1 + x(2) + x(0) +1 + 1
       = x(2) + x(0) +1 + 1 + 1 +1 + 1 +1 + 1
       = 9
x(8)  这个就调用了9次函数x(int n)
同理可得x(9)也是调用了9次函数x(int n)
所以总共18次。
下列关于树的宽度优先搜索算法描述错误的是?
从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止
常采用先进后出的栈来实现算法
空间的复杂度为O(V+E),因为所有节点都必须被储存,其中V是节点的数量,E是边的数量
时间复杂度为O(V+E),因为必须寻找所有到可能节点的所有路径,其中V是节点的数量,E是边的数量

正确答案: B   你的答案: 空 (错误)

在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数是多少?
2

下面关于B-和B+树的叙述中,不正确的是
B-树和B+树都能有效地支持顺序检索

具有3个结点的二叉树有几种形态?
5

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为多少?
DGEBHFCA

已知数据表A中每个元素距其最终位置不远,为节省时间排序,应采用什么方法排序?
插入排序

将N条长度均为M的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为()?
O(N * M * logN)

有2n个人排队进电影院,票价是50美分。在这2n个人当中,其中n个人只有50美分,另外n个人有1美元(纸票子)。愚蠢的电影院开始卖票时1分钱也没有。
问: 有多少种排队方法 使得 每当一个拥有1美元买票时,电影院都有50美分找钱
注:
1美元=100美分
拥有1美元的人,拥有的是纸币,没法破成2个50美分
(2n)!/[n!(n+1)!]

T(n) = 25T(n/5)+n^2的时间复杂度?
O(n^2*(lgn))

连续整数之和为1000的共有几组?(m,n都为整数,单独1个数也算作“连续整数”)
4

一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,这个序列的初始值从1开始,但是1并不在这个数列中。求第1500个值是多少?
2045

写出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式。
abcd*-*e+fg/hij*+k-*-

下列关于线性表,二叉平衡树,哈希表存储数据的优劣描述错误的是?
平衡二叉树的插入节点比较快

void perm(int list[], int k, int m)
{
if ( )
{
copy(list,list+m,ostream_iterator(cout,” “));
cout<

每个技术

工作中的技术需求 的技术场景
帮助小白用户 和 在考试成绩遇到瓶颈 , 以及 效率底下的用户

用到的算法
模型
seq2seq

深度学习
RNN
构建RNN 代码:

def create_rnn_cell():
    encoDecoCell = tf.contrib.rnn.BasicLSTMCell(  # Or GRUCell, LSTMCell(args.hiddenSize)
        self.args.hiddenSize,
    )
    if not self.args.test:  # TODO: Should use a placeholder instead
        encoDecoCell = tf.contrib.rnn.DropoutWrapper(
            encoDecoCell,
            input_keep_prob=1.0,
            output_keep_prob=self.args.dropout
        )
    return encoDecoCell

encoDecoCell = tf.contrib.rnn.MultiRNNCell(
    [create_rnn_cell() for _ in range(self.args.numLayers)],
)

 

 

LSTM

算法原理

算法的输入 输出(输入如何得到,输出如何评价,输出如何应用到现实场景里面)

原始输入: 平时积累的预料回答内容, 网站拍取的习题问答 和 做题经验内容
数据第一阶段输出: Cornell数据集

定义输入值 接着定义网络的输入值,根据标准的seq2seq模型,一共四个:
1. encorder的输入:人物1说的一句话A,最大长度10 2. decoder的输入:人物

2回复的对话B,因为前后分别加上了go开始符和end结束符,最大长度为12

3. decoder的target输入:decoder输入的目标输出,与decoder的输入一样但只有end标示符号,可以理解为decoder的输入在时序上的结果,比如说完这个词后的下个词的结果。

4. decoder的weight输入:用来标记target中的非padding的位置,即实际句子的长度,因为不是所有的句子的长度都一样,在实际输入的过程中,各个句子的长度都会被用统一的标示符来填充(padding)至最大长度,weight用来标记实际词汇的位置,代表这个位置将会有梯度值回传。

算法伪代码实现
seq2seq 伪代码

with tf.name_scope('placeholder_encoder'):
    self.encoderInputs = [tf.placeholder(tf.int32, [None, ]) for _ in
                          range(self.args.maxLengthEnco)]  # Batch size * sequence length * input dim

with tf.name_scope('placeholder_decoder'):
    self.decoderInputs = [tf.placeholder(tf.int32, [None, ], name='inputs') for _ in
                          range(self.args.maxLengthDeco)]  # Same sentence length for input and output (Right ?)
    self.decoderTargets = [tf.placeholder(tf.int32, [None, ], name='targets') for _ in
                           range(self.args.maxLengthDeco)]
    self.decoderWeights = [tf.placeholder(tf.float32, [None, ], name='weights') for _ in
                           range(self.args.maxLengthDeco)]

 

封装Embedding seq2seq模型

Tensorflow把常用的seq2seq模型都封装好了,比如embedding_rnn_seq2seq,这是seq2seq一个最简单的模型,一般的文本任务都会加上attention机制,但这里都用的短句子,所以attention并考虑,若想加上attention也很简单,直接修改模型名字为embedding_attention_seq2seq即可,这种封装虽然使用起来很方便,但是对于用户来说就是个黑匣子,想要自己去实现一些功能,还得去看代码。

 

decoderOutputs, states = tf.contrib.legacy_seq2seq.embedding_rnn_seq2seq(
    self.encoderInputs,  # List<[batch=?, inputDim=1]>, list of size args.maxLength
    self.decoderInputs,  # For training, we force the correct output (feed_previous=False)
    encoDecoCell,
    self.textData.getVocabularySize(),
    self.textData.getVocabularySize(),  # Both encoder and decoder have the same number of class
    embedding_size=self.args.embeddingSize,  # Dimension of each word
    output_projection=outputProjection.getWeights() if outputProjection else None,
    feed_previous=True if bool(self.args.test) and not bool(self.args.beam_search) else False

    # When we test (self.args.test), we use previous output as next input (feed_previous)
)

 

 

RNN输出一个句子的过程,其实是对句子里的每一个词来做整个词汇表的softmax分类,取概率最大的词作为当前位置的输出词,但是若词汇表很大,计算量会很大,那么通常的解决方法是在词汇表里做一个下采样,采样的个数通常小于词汇表,例如词汇表有50000个,经过采样后得到4096个样本集,样本集里包含1个正样本(正确分类)和4095个负样本,然后对这4096个样本进行softmax计算作为原来词汇表的一种样本估计,这样计算量会小不少。

在这里,具体的操作是定义一个全映射outputProjection对象,把隐藏层的输出映射到整个词汇表,这种映射需要参数w和b,也就是out=w*h+b,h是隐藏层的输出,out是整个词汇表的输出,可以理解为一个普通的全连接层。假设隐藏层的输出是512,那么w的shape就为50000*512,我们采样词汇表的操作可以看作是对w和b参数的采样,也就是采样出来的w为4096*512,用这个w带入上式计算,能得出4096个输出,然后计算softmax loss,这个sampled softmax loss是原词汇表softmax loss的一种近似。outputProjection的定义请看model.py。

 

 

outputProjection = ProjectionOp(
    (self.textData.getVocabularySize(), self.args.hiddenSize),
    scope='softmax_projection',
    dtype=self.dtype
)

def sampledSoftmax(labels, inputs):
    labels = tf.reshape(labels, [-1, 1])  # Add one dimension (nb of true classes, here 1)

    # We need to compute the sampled_softmax_loss using 32bit floats to
    # avoid numerical instabilities.
    localWt = tf.cast(outputProjection.W_t, tf.float32)
    localB = tf.cast(outputProjection.b, tf.float32)
    localInputs = tf.cast(inputs, tf.float32)

    return tf.cast(
        tf.nn.sampled_softmax_loss(
            localWt,  # Should have shape [num_classes, dim]
            localB,
            labels,
            localInputs,
            self.args.softmaxSamples,  # The number of classes to randomly sample per batch
            self.textData.getVocabularySize()),  # The number of classes
        self.dtype)

 

2.4 定义损失函数和更新方法

下面定义seq2seq模型的损失函数sequence_loss,其中sequence_loss需要softmax_loss_function参数,这个参数若不指定,那么就是默认对整个词汇表的做softmax loss,若需要采样来加速计算,则要传入上面定义的sampledSoftmax方法,这个方法的返回值是TF定义的sampled_softmax_loss。更新方法采用默认参数的Adam。

 

# Finally, we define the loss function
self.lossFct = tf.contrib.legacy_seq2seq.sequence_loss(
    decoderOutputs,
    self.decoderTargets,
    self.decoderWeights,
    self.textData.getVocabularySize(),
    softmax_loss_function=sampledSoftmax if outputProjection else None  # If None, use default SoftMax
)
tf.summary.scalar('loss', self.lossFct)  # Keep track of the cost

# Initialize the optimizer
opt = tf.train.AdamOptimizer(
    learning_rate=self.args.learningRate,
    beta1=0.9,
    beta2=0.999,
    epsilon=1e-08
)
self.optOp = opt.minimize(self.lossFct)

 

在测试模型的时候,比如我输入问一句话“How are you?“以及一个go开始符,那么模型就开始输出第一个词的候选集,这个候选集里的每一个词都有一个概率,一般采用贪婪的思想,就取概率最大的那个词作为当前输出,然后把这个词作为预测第二个词的输入再feed进网络,如此循环,直到模型输出end结束符,那么这句话就输出完毕。

这种把上一个时刻的输出当作下一个时刻的输入的过程在TF模型中由feed_previous参数决定:在训练模型的时候,我们是知道每一时刻的正确输入和输出的,并不需要这个过程,因此feed_previous=False,而只有在测试的时候,才会需要这种过程feed_previous=True

而Beam Search是这种贪婪的思想的扩展,前面是选择最大的Top 1概率的词作为当前输出,而Beam Search是选择当前Top k得分的词,当然这个得分也就是概率,那么采用这种思想,对一个问题,模型最后的输出就应该有好几种回答,这些回答根据得分排序,最终选择得分最高的句子作为最终输出。相对于前面贪婪的回答,这种搜索机制能让机器人选择更好的回答。

那么在DeepQA的基础上,我们来自己实现一下Beam Search(目前DeepQA并不支持),网上有很多实现的方法,大都是自己编写decoder,比较复杂。那么本文就采用一种非常直接的方法,依照Beam Search的思想:feed in上一时刻产生的Top k答案来产生本时刻的候选答案集,然后排序本时刻的候选答案集再选择Tok k作为本时刻的最终答案,并作为下一时刻输入,如此循环。每一时刻需要记录当前选择词的id,从第一个词到最后一个词,这些词的id构成一种选择路径。最后根据参数k,得出k条路径,每条路径有一个概率得分。这种情况下,我们是手动feed in各个候选答案,因此feed_previous=False

 

def beamSearchPredict(self, question, questionSeq=None):

    # question为输入的句子,这里先把每个词转为id,再加上padding和go标示符构成一个batch,这个batch就包含一个句子
    batch = self.textData.sentence2enco(question)

    if not batch:
        return None
    if questionSeq is not None:  # If the caller want to have the real input
        questionSeq.extend(batch.encoderSeqs)

    # feedDict为TF的placeholder变量以及对应的数据
    # ops为TF的需要计算的网络图
    ops, feedDict = self.model.step(batch)

    # 定义softmax操作
    def softmax(x):
        return np.exp(x) / np.sum(np.exp(x), axis=0)

    # path储存搜索的路径,probs里储存每个路径对应的得分(log概率)
    # beam_size对应路径的个数,储存的位置越靠后,得分越高 
    beam_size = self.args.beam_size
    path = [[] for _ in range(beam_size)]
    probs = [[] for _ in range(beam_size)]

    # 计算第一个词的output
    output = self.sess.run(ops[0][0], feedDict)
    for k in range(len(path)):
        # 计算输出的softmax概率分布
        prob = softmax(output[-1].reshape(-1, ))
        # 用对数表示这些概率分布
        log_probs = np.log(np.clip(a=prob, a_min=1e-5, a_max=1))

        # 根据概率大小排序,取前Top-beam_size的词,记录log概率和词的id
        top_k_indexs = np.argsort(log_probs)[-beam_size:]
        path[k].extend([top_k_indexs[k]])
        probs[k].extend([log_probs[top_k_indexs[k]]])

    # 计算第二个词到最后一个词
    for i in range(2, self.args.maxLengthDeco):
        tmp = []
        for k in range(len(path)):
            for j in range(len(path[k])):
                # feedDict种加入前面的词的id数据
                feedDict[self.model.decoderInputs[j + 1]] = [path[k][j]]
            # 输入feedDict至网络图,计算当前句子的output
            output = self.sess.run(ops[0][0:i], feedDict)
            # 取最后一个output(当前词的输出)做softmax和log
            prob = softmax(output[-1].reshape(-1, ))
            log_probs = np.log(np.clip(a=prob, a_min=1e-5, a_max=1))
            # 计算概率得分:P(a,b)=P(a|b)*P(b)
            # a为当前要选择的词,b为上一个已选择的词
            # Log表示: log P(a,b)=log P(a|b)+ log P(b)
            tmp.extend(list(log_probs + probs[k][-1]))

        # 假设上一个词的候选集有三个元素a,b,c
        # 那么分别把这个三个元素作为输入feed进网络里,会得出三个output的结果
        # 将这些output的概率串联到一个tmp里排序,依然取出前Top-beam_size的词作为当前的词的候选集
        top_k_indexs = np.argsort(tmp)[-beam_size:]
        indexs = top_k_indexs % self.textData.getVocabularySize()

        # 记录当前选择词的id和log概率得分
        for k in range(len(path)):
            probs[k].extend([tmp[top_k_indexs[k]]])
            path[k].extend([indexs[k]])
    return path

4.运行

使用python main来训练模型,使用python main --test interactive --beam-search --beam-size 3来实时测试对话,下面是loss的图,混乱度为以loss为自变量的e的指数函数

使用python main --test来生成对话,在save/model/model_predictions.txt中查看结果

 

5. 结果

deepQA是基于python 3.5的项目,用python 2.7也可以跑,但是需要稍微修改一些地方,另外项目还提供了训练好的参数,不想训练的可以直接导入训练好的模型。但是那些模型都是用python 3.5训练的,如果用python 2.7会导入不了这些预训练的模型。我用的是python 2.7,因此只能自己训练,由于显存的限制,训练的参数很小,效果不太好,这里给出官方的对话例子:

6. 分析

通过Beam search,有的问题能够举例多种回答,但是有的问题的后面的回答直接就失败了。有以下方面可以还可以提高:

  1. 更大的训练集:训练效果强烈依赖于训练集的质量,甚至可以把几个数据集在同一个RNN网络上训练,猜想可能效果会更好
  2. 一些参数的调整:如词频过滤的大小,词汇表大小,word embedding的维度大小,RNN的stack层数,输入输出句子最大长度,softmax的采样的大小,以及导入预训练的word2vec来加速训练过程等
  3. 增加attention机制,对于长句子
  4. 输入多个问题,只给出一个答案:这样能让网络稍微记住当前答案与前几个问题有关,目前是当前答案只与当前问题有关,问题与问题之间相互独立
  5. 更高级一点,增加记忆网络,显性将特征记忆到外部储存器,然后在记忆中搜索答案返回,这样可以使记忆长期保留,是目前比较火的研究方向
  6. 再高级就是增加知识图谱和一些启发函数,让模型自己去外部获取信息处理,然后返回答案,类似你问一个问题,即使机器人不知道,但是它可以去上网查资料然后返回你答案,这种level是最高级的。

 

 

原始地址: http://blog.csdn.net/ppp8300885/article/details/74905828

 

算法的真确率 召回率 评价值

简历修改 所有ios 前段工作内容都去掉
完善优化 底层核心工作内容

词相似度计算

句子相似度计算

文章分类(文章相似度计算)

QA场景设计