① 决策树算法-原理篇
关于决策树算法,我打算分两篇来讲,一篇讲思想原理,另一篇直接撸码来分析算法。本篇为原理篇。
通过阅读这篇文章,你可以学到:
1、决策树的本质
2、决策树的构造过程
3、决策树的优化方向
决策树根据使用目的分为:分类树和回归树,其本质上是一样的。本文只讲分类树。
决策树,根据名字来解释就是,使用树型结构来模拟决策。
用图形表示就是下面这样。
其中椭圆形代表:特征或属性。长方形代表:类别结果。
面对一堆数据(含有特征和类别),决策树就是根据这些特征(椭圆形)来给数据归类(长方形)
例如,信用贷款问题,我根据《神奇动物在哪里》的剧情给银行造了个决策树模型,如下图:
然而,决定是否贷款可以根据很多特征,然麻鸡银行选择了:(1)是否房产价值>100w;(2)是否有其他值钱的抵押物;(3)月收入>10k;(4)是否结婚;这四个特征,来决定是否给予贷款。
先不管是否合理,但可以肯定的是,决策树做了特征选择工作,即选择出类别区分度高的特征。
由此可见, 决策树其实是一种特征选择方法。 (特征选择有多种,决策树属于嵌入型特征选择,以后或许会讲到,先给个图)即选择区分度高的特征子集。
那么, 从特征选择角度来看决策树,决策树就是嵌入型特征选择技术
同时,决策树也是机器学习中经典分类器算法,通过决策路径,最终能确定实例属于哪一类别。
那么, 从分类器角度来看决策树,决策树就是树型结构的分类模型
从人工智能知识表示法角度来看,决策树类似于if-then的产生式表示法。
那么, 从知识表示角度来看决策树,决策树就是if-then规则的集合
由上面的例子可知,麻鸡银行通过决策树模型来决定给哪些人贷款,这样决定贷款的流程就是固定的,而不由人的主观情感来决定。
那么, 从使用者角度来看决策树,决策树就是规范流程的方法
最后我们再来看看决策树的本质是什么已经不重要了。
决策树好像是一种思想,而通过应用在分类任务中从而成就了“决策树算法”。
下面内容还是继续讲解用于分类的“决策树算法”。
前面讲了决策树是一种 特征选择技术 。
既然决策树就是一种特征选择的方法,那么经典决策树算法其实就是使用了不同的特征选择方案。
如:
(1)ID3:使用信息增益作为特征选择
(2)C4.5:使用信息增益率作为特征选择
(3)CART:使用GINI系数作为特征选择
具体选择的方法网上一大把,在这里我提供几个链接,不细讲。
但,不仅仅如此。
决策树作为嵌入型特征选择技术结合了特征选择和分类算法,根据特征选择如何生成分类模型也是决策树的一部分。
其生成过程基本如下:
根据这三个步骤,可以确定决策树由:(1)特征选择;(2)生成方法;(3)剪枝,组成。
决策树中学习算法与特征选择的关系如下图所示:
原始特征集合T:就是包含收集到的原始数据所有的特征,例如:麻瓜银行收集到与是否具有偿还能力的所有特征,如:是否结婚、是否拥有100w的房产、是否拥有汽车、是否有小孩、月收入是否>10k等等。
中间的虚线框就是特征选择过程,例如:ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系数。
其中评价指标(如:信息增益)就是对特征的要求,特征需要满足这种条件(一般是某个阈值),才能被选择,而这一选择过程嵌入在学习算法中,最终被选择的特征子集也归到学习算法中去。
这就是抽象的决策树生成过程,不论哪种算法都是将这一抽象过程的具体化。
其具体算法我将留在下一篇文章来讲解。
而决策树的剪枝,其实用得不是很多,因为很多情况下随机森林能解决决策树带来的过拟合问题,因此在这里也不讲了。
决策树的优化主要也是围绕决策树生成过程的三个步骤来进行优化的。
树型结构,可想而知,算法效率决定于树的深度,优化这方面主要从特征选择方向上优化。
提高分类性能是最重要的优化目标,其主要也是特征选择。
面对过拟合问题,一般使用剪枝来优化,如:李国和基于决策树生成及剪枝的数据集优化及其应用。
同时,决策树有很多不足,如:多值偏向、计算效率低下、对数据空缺较为敏感等,这方面的优化也有很多,大部分也是特征选择方向,如:陈沛玲使用粗糙集进行特征降维。
由此,决策树的优化方向大多都是特征选择方向,像ID3、C4.5、CART都是基于特征选择进行优化。
参考文献
统计学习方法-李航
特征选择方法综述-李郅琴
决策树分类算法优化研究_陈沛玲
基于决策树生成及剪枝的数据集优化及其应用-李国和
② 文章自动打分算法
文章自动打分简称 AES (Automated Essay Scoring),AES 系统利用 NLP 技术自动对文章进行打分,可以减轻阅卷人员的负担。目前有不少大型的考试都采用了 AES 算法进行作文打分,例如 GRE 考试,GRE 考试会有一位阅卷老师和 AES 系统一起打分,如果 AES 的分数和阅卷老师的分数相差过大,才有再增加一位阅卷老师进行打分。本文主要介绍两种比较经典的自动打分算法。
自动打分算法从优化目标或者损失函数来说大致可以分为三种:
传统的自动打分算法通常会人工设置很多特征,例如语法错误,N 元组,单词数量,句子长度等,然后训练机器学习模型进行打分。目前也有很多使用了神经网络的方法,通过神经网络学习出文章的特征。
下面介绍两种打分算法:
出自论文《Regression based Automated Essay Scoring》。给定很多需要打分的文章后,首先需要构造出文章的特征,用到了人工设置特征和向量空间特征。
拼写错误 Spelling Errors :使用 pyenchant 包统计出拼写错误单词数量占总单词数量的比例。
统计特征 Statistical Features :统计字符数量,单词数量,句子数量,段落数量,停止词数量,命名实体数量,标点符号数量 (反映文章的组织情况),文本长度 (反映写作流畅程度),不同词汇的数量与总单词数的占比 (反映词汇量水平)。
词性统计 POS count :统计各种词性出现的频率,例如名词,动词,形容词,副词等,词性通过 nltk 包获取。
语法流畅特征 Grammatical Fluency :使用 link grammar (链语法) 解析句子,然后统计 links 的个数;统计 n 元组出现的概率;统计词性 n 元组出现的概率。
可读性 Readability :可读性分数是衡量文本组织以及文本句法和语义复杂程度的一个指标。采用了 Kincaid 可读性分数作为一个特征,计算公式如下
本体特征 Ontological Features :为每个句子打上标签,例如研究、假设、主张、引用、支持和反对等。
可以将一篇文章投影到一个向量空间模型中 (VSM),此时文章可以用向量空间中的一个特征向量表示,例如可以用 one-hot 编码表示一篇文章,长度等于词汇表长度,如果一个单词出现在文章中,则对应的位置置为 1,如下:
另外也可以使用 TF-IDF 向量表示文本,但是采用这种表示方式单词之间不存在任何关联,为了解决这个问题,文章中使用了一个单词相关性矩阵 W 加上线性变换从而引入单词之间的相关性。
单词的相关性矩阵 W 通过 word2vec 生成的词向量计算,即 W (i,j) = 单词 i 和单词 j 词向量的余弦相似度。
最后,为了考虑文章中单词的顺序问题,将文章拆分成 k 个段落,然后分别计算向量空间特征,融合在一起。
得到上述特征之后,采用 SVR 算法进行回归学习。数据集是 kaggle ASAP 比赛数据集,数据集包含 8 个集合的文章,评价指标采用 KAPPA 和相关系数,以下是一些实验效果。
这是在 8 个集合上分别使用 linear kernel 和 rbf kernel 的效果。
这是和人类打分者的对比。
以下内容出自论文《Neural Networks for Automated Essay Grading》,可以采用回归或者分类的方法进行训练,模型如下图所示。
论文中主要使用了三种方法构造出文章的特征向量:
论文中主要用了三种神经网络结构,NN (前向神经网络),LSTM 和 BiLSTM。所有的网络都会输出一个向量 h(out),根据 h(out) 构造出损失函数,下面分别是回归和分类的损失函数。
回归损失
分类损失
第一种模型:NN (前向神经网络)
使用了两层前向神经网络,网络输入的文章特征向量是 Glove 词向量的平均值或者训练的词向量平均值。h(out) 的计算公式如下。
第二种模型:LSTM
LSTM 模型接受的输入是文章所有单词的词向量序列,然后将 LSTM 最后输出的向量作为文章的特征向量 h(out)。
第三种模型:BiLSTM
因为文章通常比较长,单向的 LSTM 容易丢失前面的信息,因此作者也使用了 BiLSTM 模型,将前向 LSTM 和后向 LSTM 模型的输出加在一起作为 h(out)。
添加 TF-IDF 向量
以上模型的输出 h(out) 都可以再加上 TF-IDF 向量提升性能,首先需要对 TF-IDF 向量降维,然后和模型的输出拼接在一起,如下图所示 (BiLSTM 为例子)。
《Regression based Automated Essay Scoring》
《Neural Networks for Automated Essay Grading》
③ 机器学习算法之神经网络
在学习了机器学习的相关知识以后,我们知道其中的算法有很多种,比如回归算法、K近邻算法等等,这些都是需要大家掌握的算法,而神经网络算法是一个十分实用的算法,在这篇文章中我们就给大家介绍一下机器学习算法中的神经网络算法知识。
那么什么是神经网络算法呢?其实神经网络也称之为人工神经网络,简单就是ANN,而算法是80年代机器学习界非常流行的算法,不过在90年代中途衰落。现在,随着深度学习的发展,神经网络再次出现在大家的视野中,重新成为最强大的机器学习算法之一。而神经网络的诞生起源于对大脑工作机理的研究。早期生物界学者们使用神经网络来模拟大脑。机器学习的学者们使用神经网络进行机器学习的实验,发现在视觉与语音的识别上效果都相当好。
那么神经网络的学习机理是什么呢?简单来说,就是分解与整合。我们可以通过一个例子进行解答这个问题,比如说,我们可以把一个正方形分解为四个折线进入视觉处理的下一层中。四个神经元分别处理一个折线。每个折线再继续被分解为两条直线,每条直线再被分解为黑白两个面。于是,一个复杂的图像变成了大量的细节进入神经元,神经元处理以后再进行整合,最后得出了看到的是正方形的结论。这就是大脑视觉识别的机理,也是神经网络工作的机理。
那么神经网络的逻辑架构是什么呢?其实一个简单的神经网络的逻辑架构分成输入层,隐藏层,和输出层。输入层负责接收信号,隐藏层负责对数据的分解与处理,最后的结果被整合到输出层。每层中的一个圆代表一个处理单元,可以认为是模拟了一个神经元,若干个处理单元组成了一个层,若干个层再组成了一个网络,这就是所谓的神经网络知识。
当然,在神经网络中,其实每一个处理单元事实上就是一个逻辑回归模型,逻辑回归模型接收上层的输入,这样,把模型的预测结果作为输出传输到下一个层次。这些过程,神经网络可以完成非常复杂的非线性分类。在神经网络在图像识别领域的一个着名应用,而这个程序叫做LeNet,是一个基于多个隐层构建的神经网络。通过LeNet可以识别多种手写数字,并且达到很高的识别精度与拥有较好的鲁棒性。这也是神经网络中最着名的应用。
在这篇文章中我们给大家介绍了很多关于神经网络的相关知识,通过这些知识我们可以更好地了解神经网络算法。当然,我们要想了解机器学习还需要掌握更多的算法。
④ 嵌入式工程师面试中常出现的算法
嵌入式工程师面试中常出现的算法
嵌入式系统是以应用为中心,以计算机技术为基础,并且软硬件可裁剪,适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统。下面我为大家整理了关于嵌入式工程师面试中经常出现的算法文章,希望对你有所帮助。
二分查找的代码.
int bfind(int* a,int len,int val)
{
int m = len/2;
int l = 0;
int r = len;
while(l!=m && r!= m)
{
if(a[m] > val)
{
r = m;
m = (m+l)/2;
}
else if(a[m] < val)
{
l = m;
m = (m+r)/2;
}
else
return m;
}
return -1; //没有找到
}
写出在母串中查找子串出现次数的代码.
int count1(char* str,char* s)
{
char* s1;
char* s2;
int count = 0;
while(*str!='