1. 聚类的基本概念

1.1 定义

聚类是数据挖掘中的概念,就是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起,不同类数据尽量分离。

1.2 聚类与分类的区别

Clustering (聚类),简单地说就是把相似的东西分到一组,聚类的时候,我们并不关心某一类是什么,我们需要实现的目标只是把相似的东西聚到一起。因此,一个聚类算法通常只需要知道如何计算相似度就可以开始工作了,因此 clustering 通常并不需要使用训练数据进行学习,这在Machine Learning中被称作unsupervised learning (无监督学习)。

Classification (分类),对于一个classifier,通常需要你告诉它“这个东西被分为某某类”这样一些例子,理想情况下,一个 classifier 会从它得到的训练集中进行“学习”,从而具备对未知数据进行分类的能力,这种提供训练数据的过程通常叫做supervised learning (监督学习)。
Continue reading

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

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

问题主要包括这几个:

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

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

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

1.1 关于模型组合​

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

贝叶斯判定准则:为最小化总体风险,只需在每个样本上选择能使条件风险R(c|x)最小的类别标记:

/——————————-极大似然估计———————————/

估计类的常用策略:先假定其具有某种确定的概率分布形式,再基于训练样本对概率分布的参数进行估计。即概率模型的训练过程就是参数估计过程。

参数估计两大学派:频率主义学派和贝叶斯学派。

(1)频率主义:参数虽然未知,但却是客观存在的固定值,因此,可通过优化似然函数等准则来确定参数值(最大似然)。(2)贝叶斯学派:参数是未观察到的随机变量,本身也可以有分布,因此,可假定参数服从一个先验分布,然后基于观察到的数据来计算参数的后验分布。

/*—————————–朴素贝叶斯————————————*/

朴素贝叶斯:

(1)思想:对于给定的待分类项x,通过学习到的模型计算后验概率分布,即:在此项出现的条件下各个目标类别出现的概率,将后验概率最大的类作为x所属的类别。后验概率根据贝叶斯定理计算。

(2)关键:为避免贝叶斯定理求解时面临的组合爆炸、样本稀疏问题,引入了条件独立性假设

(3)工作原理: 

(4)工作流程:1)准备阶段:确定特征属性,并对每个特征属性进行适当划分,然后由人工对一部分待分类项进行分类,形成训练样本。 2)训练阶段:对每个类别计算在样本中的出现频率p(y),并且计算每个特征属性划分对每个类别的条件概率p(yi | x); 3)应用阶段:使用分类器进行分类,输入是分类器和待分类样本,输出是样本属于的分类类别。

采用了属性条件独立性假设,

Continue reading

应聘数据挖掘工程师或机器学习工程师,面试官经常会考量面试者对SVM的理解。

以下是我自己在准备面试过程中,基于个人理解,总结的一些SVM面试常考问题(想到会再更新),如有错漏,请批评指正。(大神请忽视)

转载请注明出处:blog.csdn.net/szlcw1

SVM的原理是什么?

SVM是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。(间隔最大是它有别于感知机)

(1)当训练样本线性可分时,通过硬间隔最大化,学习一个线性分类器,即线性可分支持向量机;

(2)当训练数据近似线性可分时,引入松弛变量,通过软间隔最大化,学习一个线性分类器,即线性支持向量机;

(3)当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机。

注:以上各SVM的数学推导应该熟悉:硬间隔最大化(几何间隔)—学习的对偶问题—软间隔最大化(引入松弛变量)—非线性支持向量机(核技巧)。

Continue reading

5.1 神经元模型

神经网络中最基本的成分是神经元(neuron)模型,即上述定义中在生物神经网络中,每个神经元与与其他神经元链接,当它兴奋时就会向相链接的神经元发送化学物质,从而改变这些神经元内的点位:如果某个神经元的电位超过了一个阈值(threshold), 那么它就会被激活,即“兴奋”起,向其他神经元发送化学物质

MP 神经元模型: 在这个模型中神经元接受到来自n个其他神经元传递过来的输入信号,这些输入信号通过带权重的链接(connection)进行传递,神经元接收到总输入将与神经元的阈值进行比较,然后通过“激活函数”(activation function)处理以产生神经元的输出

Continue reading

第四章: 决策树

4.1 基本流程

面试问题1:什么是决策树?

答:决策树是一种分类和回归的基本模型,可从三个角度来理解它,即:

  • 一棵树
  • if-then规则的集合,该集合是决策树上的所有从根节点到叶节点的路径的集合
  • 定义在特征空间与类空间上的条件概率分布,决策树实际上是将特征空间划分成了互不相交的单元,每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中,哪个类别有较高的条件概率,就把该单元中的实例强行划分为该类别。

 

面试问题2:和其他模型比,它的优点?

答:主要的优点有两个:

  • 模型具有可解释性,容易向业务部门人员描述。
  • 分类速度快

当然也有其他优点,比如可以同时处理类别数据和数值数据。在运用分类决策树分类时,我们的数据一般会进行离散化

面试问题3:如何学习一棵决策树?

答:决策树的学习本质上就是从训练数据集中归纳出一组分类规则,使它与训练数据矛盾较小的同时具有较强的泛华能力。从另一个角度看,学习也是基于训练数据集估计条件概率模型(至此,回答完了模型部分,下面接着说策略和算法)。
决策树的损失函数通常是正则化的极大似然函数,学习的策略是以损失函数为目标函数的最小化(说完了策略,该说算法了)。

由于这个最小化问题是一个NP完全问题,现实中,我们通常采用启发式算法(这里,面试官可能会问什么是启发式算法,要有准备,SMO算法就是启发式算法)来近似求解这一最优化问题,得到的决策树是次最优的。

该启发式算法可分为三步:

  • 特征选择
  • 模型生成
  • 决策树的剪枝

面试官此时心理活动:“嗯,看来这小子对决策树还是了解的,下面继续测测他的掌握深度,不信问不倒他!”

面试问题4:能具体谈谈这三个步骤吗?

答:从总体上看,这三个步骤就是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程,这个过程就是划分特征空间,构建决策树的过程。

面试官插问:如何选择最优特征呢?
简单讲,根据特征的分类能力去选择最优特征,特征分类能力的衡量通常采用信息增益或信息增益比。
面试官:谈谈你对信息增益和信息增益比的理解。
要理解信息增益,首先要理解熵这个概念。从概率统计的角度看,熵是对随机变量不确定性的度量,也可以说是对随机变量的概率分布的一个衡量。熵越大,随机变量的不确定性越大。对同一个随机变量,当它的概率分布为均匀分布时,不确定性最大,熵也最大。对有相同概率分布的不同的随机变量,取值越多的随机变量熵越大。(这是精华)。熵的公式如下:

shang.PNG

其次,要理解条件熵的概念。正如熵是对随机变量不确定性的度量一样,条件熵是指,有相关的两个随机变量X和Y,在已知随机变量X的条件下随机变量Y的不确定性。定义为X给定条件下Y的条件概率分布的熵对X的数学期望。公式如下:

tiaojianshang.PNG

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别为经验熵与经验条件熵。

所谓信息增益,也叫互信息,就是指集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,公式如下:

xinxizengyi.PNG

用信息增益去选择特征有一个问题,即偏向于选择取值较多的特征。解决思路就是对取值较多的特征进行适当的惩罚(这里如果面试官感兴趣,可以说说惩罚思想,如L1,L2都是一种惩罚的做法),这就是信息增益比所干的事。公式如下:

xinxizengyibi.PNG

面试官心理:“看来这小子还有两下子,且让我再往深里探探,幸好我准备很充分。”

面试官插问:递归的终止条件是什么呢?
通常有两个终止条件,一是所有训练数据子集被基本正确分类。二是没有合适的特征可选,即可用特征为0,或者可用特征的信息增益或信息增益比都很小了。

面试官提问:什么是决策树剪枝,怎么剪枝?
答:由于根据训练数据生成的决策树往往过于复杂,导致泛华能力比较弱,所以,实际的决策树学习中,会将已生成的决策树进行简化,以提高其泛华能力,这一过程叫做剪枝。具体说就是在已生成的决策树上裁掉一些子树或叶节点,并将其根节点或父节点作为新的叶节点。

具体剪枝时,有一般的剪枝算法和CART剪枝算法两种。下面分别叙述:

一般剪枝算法

不管是一般剪枝算法还是CART剪枝算法,都基于同一个思想,即减小决策树模型的整体损失函数,前面提到过,这个整体损失函数是正则化的极大似然函数,其形式如下:

zhengtisunshihanshu.PNG

C(T)表示决策树T对训练数据集的预测误差,|T|表示决策树的叶节点个数,即模型复杂度。α是权衡因子。C(T)通常有两种衡量方法,一种用熵,一种用基尼指数(这里可先不展开,面试官如果问就再说)。

基尼指数也是一种衡量随机变量不确定性的指标,其公式如下:

jinizhishu.PNG

一般剪枝算法,给定α后,通过不断剪枝来减小决策树模型的整体损失。

核心步骤是:假设一组叶节点回缩到其父节点之前与之后的整体树分别为T_B与T_A,其对应的损失函数值分别是C_α(T_B)与C_α(T_A),如果

C_α(T_A) ≦C_α(T_B)

则进行剪枝,将父节点变为新的叶节点。

递归地进行以上步骤,知道不能继续为止,得到损失函数最小的子树T_α。

具体实现这个算法时可采用动态规划(说出动态规划,应当是加分项)。

CART剪枝算法

相比一般剪枝算法,CART剪枝算法的优势在于,不用提前确定α值,而是在剪枝的同时找到最优的α值。

下面简要叙述其数学过程,具体证明过程比较复杂,就不写了,感兴趣的可以参考其他资料。

对决策树T的每一个内部节点t,计算

cartjianzhi.PNG

T_t代表以内部节点t为根节点的子树。 这样计算出的值表示剪枝后整体损失函数减少的程度。

选择g(t)值最小的内部节点t进行剪枝,得到一棵新树T_g(t)。
然后,对这棵新树继续上面的剪枝过程,又得到一棵新树。
如此,一直到单节点树,可以得到一系列的树,它们互相嵌套。用交叉验证法从中选出最优的子树T_g(t),它对应的α值为g(t)。

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

Continue reading

第三章 : 线性模型

3.1 基本形式

给定由d个描述的示例 x= (x1,x2, x3 ….. xd) ,期中xi 是x 在 x 第i个属性的取值,线性模型(linear model)试图学得一个属性的线性组合来惊醒预测的函数即:

f(x) = w1x1 …. wdxd + b,

一般用向量形式写成

f(x) = w(矩阵) x + b

一下为几个经典的线性回归

3.2 线性回归

f(xi) = wxi + b 使得 (fxi) ≈ yi

如何确定 w 和 b 呢:我们求线性变换的均方误

Continue reading

第二章 模型评估与选择
2.1 经验误差与过拟合
错误率(Error rate): 分类错误占总样本数 E = a/m
精读(accuracy) : 1 – 错误率 = 1 – a/m
训练误差(training error).经验误差(empirical):机器学习在训练集上的误差称为训练误差 或者 经验误差
泛化误差(generalization): 机器学习在新样本(test)上的误差称为泛化误差

机器学习的目标就是让泛化误差最小化

机器学习主要是为了从训练样本红尽可能的学习出适用于所有潜在样本的“普遍规律”这样才能在遇到新样本的时候做出正确的判断,然而当学习器吧训练样本学得“太好”了的时候,很有可能已经把训练样本自身的一些特点当做了所有潜在样本都会具有的一般性质,这样就会导致泛化能力下降
这种现象叫做 “过拟合”(overfitting),于过拟合相对的是“欠拟合”(underfitting) 这是指对训练样本的一般性质尚未学习好
过拟合:最常见的情况是由于学习能力过于强大,以至于把训练样本所包含的一般特性都学到了
欠拟合:由于学习能力较低造成的,比较容易客服,例如在决策树学习中扩展分值,在神经网路学习中增加训练论述等
Continue reading

贝叶斯定
理由英国数学家贝叶斯 ( Thomas Bayes 1702-1761 ) 发展,用来描述两个条件概率之间的关系,比如 P(A|B) 和 P(B|A)。按照乘法法则,
可以立刻导出:P(A∩B) = P(A)*P(B|A)=P(B)*P(A|B)。如上公式也可变形为:P(B|A) = P(A|B)*P(B) / P(A)。

随机森林