周志华 《机器学习》笔记七 集成学习

面试问题-集成学习,KMP,AC自动机,两道算法题目,逻辑回归的复习

转载2015-09-15 08:36:30

问题主要包括这几个:

为什么若干个弱分类器组合的效果会增强​;使用KMP在一段文档中查找单词,词典用什么数据结构最好;两道算法题目;逻辑回归的相关内容;特征很多时,用哪个模型做预测好。

1 为什么若干个弱分类器组合的效果会增强

​这个属于集成学习方法的内容,前面已经大致说过一些,包括随机森林、GBDT等,其主要思想就是将若干个基础模型组合,形成一个强大的模型。下面说明其中包含的一些细节内容。

1.1 关于模型组合​

要清楚,组合所用的基础模型,一定要保证其多样性,差异性(这个特性也解释了为什么随机森林里,每次建立决策树都是抽样数据,抽样特征)。假如使用的基础模型没有差异性,例如比较极端的情况,是多个完全一样的模型,就相当于同一个人在不停的做重复的思考和判断,不会产生集体智慧的效应。这个差异性体可以有如下几种选择:​

 

1)使用的数据不完全相同

bagging方法中,每次都会对原样本进行重复抽样,​保证每次建立基础模型时使用的数据不完全相同,保证数据的多样性。​

boosting方法中,GBDT序列建立基础模型过程中,每次使用的数据都是之前一次的误差,数据不同。​

2)使用的​基础模型不同

有两种解释,一个是可以将使用了不同前提假设的基础模型组合起来,还有一个是选用的基础模型不是很强大,比较敏感,当数据发生变化时,训练出的模型就会有加大的变动。例如使用决策树作为基础模型,由于决策树本身对数据很敏感,当使用不同数据建模时,得到的基础决策树会有较大不同,保证了基础模型的多样性,差异性。

那为什么组合起来后效果会比单一基础模型好?​

举个更具体的例子,公司需要做出一项决策,询问公司中不同部门、不同领域的几位专家,这些专家基于自己的知识作出判断是否要进行这项决策。每个人会有不同的判断准确率,假设分别是79%,75%,70%,60%,75%,65%。最理想的情况是他们的判断是相互独立的,不会相互干扰,这种情况下,组合起来的准确率为:

​1 – 30%*25%*30%*40%*25%*35%= 1 – 0.07875 = 99.92125%

当然在具体应用中,可能无法做到不同基础模型之间完全独立,没有干扰。​​

从另一个角度解释,就是​在集体智慧中,哪怕其中有少数几个基础模型效果很差,最后投票时并不会对最终的结果造成很坏的影响。

决策树是一种对于数据比较敏感的基础模型,很适合用来作为集成方法的基础模型,所以随机森林、GBDT的效果会很好。此外,在这篇总结中还提到,​决策树对于非均衡数据集的效果不错,不要求数据集一定是均衡的。

​1.2 关于方差、偏差

之前大致介绍过方差和偏差的内容。模型中的误差,在数学上可以转化成如下形式

所以偏差衡量的是预测值与实际值差异的平均值,方差衡量的是基于同一观测值,预测值之间的差异。

​bagging方法可以降低方差,因为这个过程使用了不同的数据集;boosting可以降低方差和偏差。

2 使用KMP算法在一段话中进行单词查找,词典使用什么数据结构效率高​

​面试的时候理解有误,其实问题是这么个意思:KMP算法每次匹配的是一段话和一个单词,当单词不止一个的时候,怎样存储单词能够同时将多个单词高效的套用到KMP算法中。

2.1 ​KMP算法

​关于KMP算法的介绍,看这篇http://blog.csdn.net/v_JULY_v/article/details/6111565。

假设现在有要匹配的单词(或者说是一个字符串)pattern,要在其中查找pattern的一段文字target,KMP算法包含两个步骤实现模式匹配。首先,计算pattern的自身覆盖度,pattern的每个元素都对应一个这样的值,over[i]=k表示从第i个元素向前的k个元素,与pattern[0]到pattern[k]是匹配的。例图如下:

​得到pattern的覆盖度后,从左向右进行匹配,当发生失配后,不在把target_index往回移动,因为target中当前可以匹配的长度可以从pattern的覆盖度中体现出来,只要将pattern_index移动到可以匹配长度的后一个index即可。

​计算覆盖度的代码:

​#include

#include

using namespace std;

void compute_overlay(const string& pattern)

{

const int pattern_length = pattern.size();

int *overlay_function = new int[pattern_length];

int index;

overlay_function[0] = -1;

for(int i=1;i

{

index = overlay_function[i-1];

//store previous fail position k to index;

while(index>=0 && pattern[i]!=pattern[index+1])

{

index = overlay_function[index];

}

if(pattern[i]==pattern[index+1])

{

overlay_function[i] = index + 1;

}

else

{

overlay_function[i] = -1;

}

}

for(i=0;i

{

cout<<overlay_function[i]<<endl;

}

delete[] overlay_function;

}

int main()

{

string pattern = “abaabcaba”;

compute_overlay(pattern);

return 0;

}

对应上图的覆盖度为:​-1,-1,0,0,1,-1,0,1,2。

​得到覆盖度后,匹配时,当在长度j时发生失配时,只要将pattern整体向右移动j-over(j)就可以了。如果失配时pattern_index==0,相当于pattern第一个字符就不匹配,这时就应该把target_index加1,向右移动1位就可以了。

匹配过程的代码如下:

int pattern_index = 0;

int target_index = 0;

while(pattern_index

{

if(target[target_index]==pattern[pattern_index])

{

++target_index;

++pattern_index;

}

else if(pattern_index==0)

{

++target_index;

}

else

{​

pattern_index = overlay_value[pattern_index-1]+1;

}

}

if(pattern_index==pattern_length)

{

return target_index-pattern_index;

}

else

{

return -1;

}

​2.2 字典树

​字典树,又称单词查找树,Trie树,是哈希树的一种变型,典型应用是用于统计,排序和保存大量字符串,经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。​这样,整个查找路径上各节点存储的数据就构成了一个单词。

数据结构定义如下:

typedef struct Trie

{

Trie *next[MAX];

int v;   //根据需要变化

};

Trie *root;

​根据需求,每个节点包含的子节点数目可以变化,如果只是小写字母,则26即可,若改为大小写字母,则是52,若再加上数字,则是62了,这里根据题意来确定。v可以表示一个字典树到此有多少相同前缀的数目,这里根据需要应当学会自由变化。

利用Trie进行查找的过程大致如下:

​(1) 每次从根结点开始一次搜索;

​(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;

(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

​(4) 迭代过程……

​(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

Trie的构建过程也比较简单,针对n个单词构建时,每次取一个单词,从根节点查看有没有和单词第一个字母匹配的子节点,​有就继续查下去,没有就添加新的节点。

除了单词查找,字典树可以解决的问题还包括:

  • 1)、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
  • 2)、1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?
  • 3)、 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
  • 4)、寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。(1) 请描述你解决这个问题的思路;(2) 请给出主要的处理流程,算法,以及算法的复杂度。

​2.3 AC自动机

http://blog.csdn.net/niushuai666/article/details/7002823​

http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

​我的理解就是在一棵字典树上进行KMP,用失配指针体现覆盖数的作用,表示匹配失败时下一步应当移动到字典树的什么位置。

​使用AC自动机时,首先根据要匹配的各个词构建传统的字典树,然后采用广度优先的方式为每个节点构建对应的失配指针。所谓失配指针,是指当利用字典树进行匹配时,匹配到某个节点now,在向now的子节点匹配时发生失配,就根据失配指针决定下一步跳转到哪个节点。

​对应失配指针比较直观的解释是,当对目标文字进行匹配时,顺着字典树走到了节点now,说明路径上的字母组成的字符串和某个模式的s[1,2,…m]是匹配的。再继续向下匹配时,发现now的所有子节点都无法与目标文字中的下一个字母匹配,即发生了失配。此时,失配指针应当指向字典树中的另一个节点f,该节点满足这样的性质,从根节点到f的路径上的字母,能够匹配s[i,i+1,…m],而这个s的后缀,是其他某个单词的前缀,即t[1,2,3,…n], 然后从f节点开始继续匹配。若继续失配,则继续遵循上述原则,根据失配指针依次跳转,直到出现匹配或者目标序列为空。

由于now和f实际对应的都是s[m]这项,所以这两个节点对应的字母是不会发生变化的。如果now的失配指针没有指向root(root是一个虚节点,其中不包括字符),说明当前字符串中的某个后缀(即s[i,i+1,…m])是某个要查找单词的前缀(即不同于单词s的另一个单词的前几个字母,t[1,2,3,…,n])​。若指向root,则说明当前序列中,不存在某个单词的前缀。

这就是为什么说AC自动机是在一棵字典树上进行的KMP算法,这里失配指针起到了KMP中覆盖数的作用,指明了到当前节点时已经匹配的字符串中包含了哪些单词的一部分前缀,避免了从头开始匹配。

​每个节点n的失配指针都是根据父节点f的失配指针指向的节点t决定的,即先根据父节点f的失配指针找到节点t(此时可以知道f节点的路径中中包含的其它单词的前缀),然后看这个节点t的子节点中,是否有和当前节点字符相同的节点,有则将n的支配指针指向t的这个子节点,没有则根据t的失配指针继续跳转。这样,f的路径中包含了t的路径中的字符串,那如果t的子节点中有和n相同的字符,这个匹配的长度就加一,没有就是失配,再次跳转。

根节点的失配指针指向NULL,然后根节点入队。根节点出队,开始处理根节点的子节点,处理完一个入队一个,当然根节点的子节点的失配指针指向根节点,因为如果第一个字母就不批评,肯定是要重新开始匹配的。后续节点,根据队列中的顺序出队,并根据上面叙述的原则,找到其对应的失配节点位置。

​3 两道算法题目

​3.1 有一个数组a包含若干个整数,找到这样两个坐标m,n,其中m

​这道题的思路是,希望前一个数尽量小,后一个数尽量大,所以可以保持从头开始到当前坐标时,最小的元素,然后计算当前元素与最小元素只差,是否比原有的差大,大则进行更新,然后查看当前元素是否小于原有的最小元素,是则更新,大致的代码如下:

int min_index=0;//最小元素所在坐标,也是取得最大差值时,对应的a

int max=-INF;//差值的最大值

​int right=-1;//取得最大差值时,对应的b

for(int i=1;i

tmp=a[i]-a[min_index];

if(tmp>max){

max=tmp;

right=i;
}

min_index=a[i]
}​​​​​​​

3.2有一个矩形的网格,横向有m个点,纵向有n个点,从最下角的点走到右上角的点,每次只能向上走或者向右走,一共有多少中走法?

​首先,从左下角走到右上角,一共要走m+n步,其中m步向上,n步向右,所以这就变成了排列组合问题,m+n中有m次选择向上,n次选择向右,即C(m,m+n)。

4 特征很多时,使用什么模型

这个没有找到很权威的说法,虽然我的第一反应是进行特征选择,然后降维。不过在复习回归模型相关内容时,在这篇对几种不同回归模型的介绍中,最后有这么一句

​Regression regularization methods(Lasso, Ridge and ElasticNet) works well in case of high dimensionality and multicollinearity among the variables in the data set.​

带有正则项的回归模型对于高维数据和特征之间存在多重共线性的数据效果会很好,看来应该回答的是这个。

Leave a Reply

Your email address will not be published. Required fields are marked *