范文一:机器学习十大算法之一
机器学习十大算法之一:EM算法。
一、最大似然 假设我们需要调查我们学校的男生和女生的身高分布。你怎么做啊?你说那么多人不可能一个一个去问吧,肯定是抽样了。假设你在校园里随便地活捉了100个男生和100个女生。他们共200个人(也就是200个身高的样本数据,为了方便表示,下面,我说“人”的意思就是对应的身高)都在教室里面了。那下一步怎么办啊?你开始喊:“男的左边,女的右边,其他的站中间!”。然后你就先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值u和2T方差?我们不知道,这两个参数就是我们要估计的。记作θ=*u, ?+。 用数学的语言来说就是:在学校那么多男生(身高)中,我们独立地按照概率密度p(x|θ)抽取100了个(身高),组成样本集X,我们想通过样本集X来估计出未知参数θ。这里概率密度p(x|θ)我们知道了是T高斯分布N(u,?)的形式,其中的未知参数是θ=*u, ?+。抽到的样本集是X={x1,x2,…,xN},其中xi表示抽到的第i个人的身高,这里N就是100,表示抽到的样本个数。 由于每个样本都是独立地从p(x|θ)中抽取的,换句话说这100个男生中的任何一个,都是我随便捉的,从我的角度来看这些男生之间是没有关系的。那么,我从学校那么多男生中为什么就恰好抽到了这100个人呢?抽到这100个人的概率是多少呢?因为这些男生(的身高)是服从同一个高斯分布p(x|θ)的。那么我抽到男生A(的身高)的概率是p(xA|θ),抽到男生B的概率是p(xB|θ),那因为他们是独立的,所以很明显,我同时抽到男生A和男生B的概率是p(xA|θ)* p(xB|θ),同理,我同时抽到这100个男生的概率就是他们各自概率的乘积了。用数学家的口吻说就是从分布是p(x|θ)的总体样本中抽取到这100个样本的概率,也就是样本集X中各个样本的联合概率,用下式表示:
这个概率反映了,在概率密度函数的参数是θ时,得到X这组样本的概率。因为这里X是已知的,也就是说我抽取到的这100个人的身高可以测出来,也就是已知的了。而θ是未知了,则上面这个公式只有θ是未知数,所以它是θ的函数。这个函数放映的是在不同的参数θ取值下,取得当前这个样本集的可能性,因此称为参数θ相对于样本集X的似然函数(likehood function)。记为L(θ)。 这里出现了一个概念,似然函数。还记得我们的目标吗?我们需要在已经抽到这一组样本X的条件下,估计参数θ的值。怎么估计呢?似然函数有啥用呢?那咱们先来了解下似然的概念。 直接举个例子: 某位同学与一位猎人一起外出打猎,一只野兔从前方窜过。只听一声枪响,野兔应声到下,如果要你推测,这一发命中的子弹是谁打的?你就会想,只发一枪便打中,由于猎人命中的概率一般大于这位同学命中的概率,看来这一枪是猎人射中的。 这个例子所作的推断就体现了极大似然法的基本思想。 再例如:下课了,一群男女同学分别去厕所了。然后,你闲着无聊,想知道课间是男生上厕所的人多还是女生上厕所的人比较多,然后你就跑去蹲在男厕和女厕的门口。蹲了五分钟,突然一个美女走出来,你狂喜,跑过来告诉我,课间女生上厕所的人比较多,你要不相信你可以进去数数。呵呵,我才没那么蠢跑进去数呢,到时还不得上头条。我问你是怎么知道的。你说:“5分钟了,出来的是女生,女生啊,那么女生出来的概率肯定是最大的了,或者说比男生要大,那么女厕所的人肯定比男厕所的人多”。看到了没,你已经运用最大似然估计了。你通过观察到女生先出来,那么什么情况下,女生会先出来呢?肯定是女生出来的
概率最大的时候了,那什么时候女生出来的概率最大啊,那肯定是女厕所比男厕所多人的时候了,这个就是你估计到的参数了。
从上面这两个例子,你得到了什么结论?
回到男生身高那个例子。在学校那么男生中,我一抽就抽到这100个男生(表示身高),而不是其他人,那是不是表示在整个学校中,这100个人(的身高)出现的概率最大啊。那么这个概率怎么表示?哦,就是上面那个似然函数L(θ)。所以,我们就只需要找到一个参数θ,其对应的似然函数L(θ)最大,也就是说抽到这100个男生(的身高)概率最大。这个叫做θ的最大似然估计量,记为:
有时,可以看到L(θ)是连乘的,所以为了便于分析,还可以定义对数似然函数,将其变成连加的:
好了,现在我们知道了,要求θ,只需要使θ的似然函数L(θ)极大化,然后极大值对应的θ就是我们的估计。这里就回到了求最值的问题了。怎么求一个函数的最值?当然是求导,然后让导数为0,那么解这个方程得到的θ就是了(当然,前提是函数L(θ)连续可微)。那如果θ是包含多个参数的向量那怎么处理啊?当然是求L(θ)对所有参数的偏导数,也就是梯度了,那么n个未知的参数,就有n个方程,方程组的解就是似然函数的极值点了,当然就得到这n个参数了。 最大似然估计你可以把它看作是一个反推。多数情况下我们是根据已知条件来推算结果,而最大似然估计是已经知道了结果,然后寻求使该结果出现的可能性最大的条件,以此作为估计值。比如,如果其他条件一定的话,抽烟者发生肺癌的危险时不抽烟者的5倍,那么如果现在我已经知道有个人是肺癌,我想问你这个人抽烟还是不抽烟。你怎么判断?你可能对这个人一无所知,你所知道的只有一件事,那就是抽烟更容易发生肺癌,那么你会猜测这个人不抽烟吗?我相信你更有可能会说,这个人抽烟。为什么?这就是“最大可能”,我只能说他“最有可能”是抽烟的,“他是抽烟的”这一估计值才是“最有可能”得到“肺癌”这样的结果。这就是最大似然估计。 好了,极大似然估计就讲到这,总结一下: 极大似然估计,只是一种概率论在统计学的应用,它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布,但是其中具体的参数不清楚,参数估计就是通过若干次试验,观察其结果,利用结果推出参数的大概值。最大似然估计是建立在这样的思想上:已知某个参数能使这个样本出现的概率最大,我们当然不会再去选择其他小概率的样本,所以干脆就把这个参数作为估计的真实值。 求最大似然函数估计值的一般步骤: (1)写出似然函数; (2)对似然函数取对数,并整理; (3)求导数,令导数为0,得到似然方程; (4)解似然方程,得到的参数即为所求; 二、EM算法 好了,重新回到上面那个身高分布估计的问题。现在,通过抽取得到的那100个男生的身高和已知的其身高服从高斯分布,我们通过最大化其似然函数,就可以得到了对应高斯分布的参数θ=*u, ?+T了。那么,对于我们学校的女生的身高分布也可以用同样的方法得到了。 再回到例子本身,如果没有“男的左边,女的右边,其他的站中间!”这个步骤,或者说我抽到这200个人中,某些男生和某些女生一见钟情,已经好上了,纠缠起来了。咱们也不想那么残忍,硬把他们拉扯开。那现在这200个人已经混到一起了,这时候,你从这200个人(的身高)
里面随便给我指一个人(的身高),我都无法确定这个人(的身高)是男生(的身高)还是女生(的身高)。也就是说你不知道抽取的那200个人里面的每一个人到底是从男生的那个身高分布里面抽取的,还是女生的那个身高分布抽取的。用数学的语言就是,抽取得到的每个样本都不知道是从哪个分布抽取的。 这个时候,对于每一个样本或者你抽取到的人,就有两个东西需要猜测或者估计的了,一是这个人是男的还是女的?二是男生和女生对应的身高的高斯分布的参数是多少? 只有当我们知道了哪些人属于同一个高斯分布的时候,我们才能够对这个分布的参数作出靠谱的预测,例如刚开始的最大似然所说的,但现在两种高斯分布的人混在一块了,我们又不知道哪些人属于第一个高斯分布,哪些属于第二个,所以就没法估计这两个分布的参数。反过来,只有当我们对这两个分布的参数作出了准确的估计的时候,才能知道到底哪些人属于第一个分布,那些人属于第二个分布。 这就成了一个先有鸡还是先有蛋的问题了。鸡说,没有我,谁把你生出来的啊。蛋不服,说,没有我,你从哪蹦出来啊。(呵呵,这是一个哲学问题。当然了,后来科学家说先有蛋,因为鸡蛋是鸟蛋进化的)。为了解决这个你依赖我,我依赖你的循环依赖问题,总得有一方要先打破僵局,说,不管了,我先随便整一个值出来,看你怎么变,然后我再根据你的变化调整我的变化,然后如此迭代着不断互相推导,最终就会收敛到一个解。这就是EM算法的基本思想了。 不知道大家能否理解其中的思想,我再来啰嗦一下。其实这个思想无处在不啊。 例如,小时候,老妈给一大袋糖果给你,叫你和你姐姐等分,然后你懒得去点糖果的个数,所以你也就不知道每个人到底该分多少个。咱们一般怎么做呢?先把一袋糖果目测的分为两袋,然后把两袋糖果拿在左右手,看哪个重,如果右手重,那很明显右手这代糖果多了,然后你再在右手这袋糖果中抓一把放到左手这袋,然后再感受下哪个重,然后再从重的那袋抓一小把放进轻的那一袋,继续下去,直到你感觉两袋糖果差不多相等了为止。呵呵,然后为了体现公平,你还让你姐姐先选了。 EM算法就是这样,假设我们想估计知道A和B两个参数,在开始状态下二者都是未知的,但如果知道了A的信息就可以得到B的信息,反过来知道了B也就得到了A。可以考虑首先赋予A某种初值,以此得到B的估计值,然后从B的当前值出发,重新估计A的取值,这个过程一直持续到收敛为止。 EM的意思是“Expectation Maximization”,在我们上面这个问题里面,我们是先随便猜一下男生(身高)的正态分布的参数:如均值和方差是多少。例如男生的均值是1米7,方差是0.1米(当然了,刚开始肯定没那么准),然后计算出每个人更可能属于第一个还是第二个正态分布中的(例如,这个人的身高是1米8,那很明显,他最大可能属于男生的那个分布),这个是属于Expectation一步。有了每个人的归属,或者说我们已经大概地按上面的方法将这200个人分为男生和女生两部分,我们就可以根据之前说的最大似然那样,通过这些被大概分为男生的n个人来重新估计第一个分布的参数,女生的那个分布同样方法重新估计。这个是Maximization。然后,当我们更新了这两个分布的时候,每一个属于这两个分布的概率又变了,那么我们就再需要调整E步……如此往复,直到参数基本不再发生变化为止。 这里把每个人(样本)的完整描述看做是三元组yi={xi,zi1,zi2},其中,xi是第i个样本的观测值,也就是对应的这个人的身高,是可以观测到的值。zi1和zi2表示男生和女生这两个高斯分布中哪个被用来产生值xi,就是说这两个值标记这个人到底是男生还是女生(的身高分布产生的)。这两个值我们是不知道的,是隐含变量。确切的说,zij在xi由第j个高斯分布产生时值为1,否则为0 。例如一个样本的观测值为1.8,然后他来自男生的那个高斯分布,那么我们可以将这个样本表示为{1.8, 1, 0}。如果zi1和zi2的值已知,也就是说每个人我已经标记为男生或者女生了,那么我们就可以利用上面说的最大似然算法来估计他们各自高斯分布的参数。但是它们未知,因此我们只能用EM算法。
知道是从哪个分布抽取的咱们现在不是因为那个恶心的隐含变量(抽取得到的每个样本都不求解不了吗。)使得本来简单的可以求解的问题变复杂了,题简单化。好,那么现在把这个复杂的问题逆回来,我假设已经知道这那怎么办呢?人类解决问题的思路都是想能否把复杂的问个隐含变量了,哎,那么求解那个分布的参数是不是很容易了,直接按上面说的最大似然估计就好了。你怎么就来一个假设说已知呢?你这种假设是没有根据的。那你就问我了,这个隐含变量是未知的,道,的期望,所以我们可以先给这个给分布弄一个初始值,然后求这个隐含变量呵呵,我知解那个分布的参数了吧,当成是这个隐含变量的已知值,
它更能表达真实的分布,那假设这个参数比之前的那个随机的参数要好,那么现在就可以用最大似然求隐含变量的期望,然后再最大化,得到另一个更优的参数,那么我们再通过这个参数确定的分布去求这个就能得到一个皆大欢喜的结果了。……迭代, 就比原来的好啊?为什么这种方法行得通呢?有没有失效的时候呢?这时候你就不服了,说你老迭代迭代的, 你咋知道新的参数的估计什么时候失效呢?用到这个方法需要注意什么问题呢?呵呵,出那么多问题,搞得我适应不过来了,一下子抛的潜质啊。呵呵,其实这些问题就是数学家需要解决的问题。在数学上不过这证明了你有很好的搞研究是可以稳当的证明的或者得出结论的。新描述下。那咱们用数学来把上面的问题重想,(在这里可以知道,不管多么复杂或者简单的物理世界的思而且,这里面蕴含的数学往往能带给你更多想象不到的东西,都需要通过数学工具进行建模抽象才得以使用并发挥其强大的作用,学的精妙所在啊)这就是数
三、EM算法推导
样本假设我们有一个样本集(1)(m)
需要估计概率模型i对应的类别z(i){x,…,x},包含m个独立的样本。但每个很难用最大似然求解,但如果p(x,z)是未知的(相当于聚类),也即隐含变量。故我们的参数θ,但是由于里面包含隐含变量z,所以 z知道了,那我们就很容易求解了。 个参数对于参数估计,
量大z,见下式(θ,现在与最大似然不同的只是似然函数式中多了一个未知的变我们本质上还是想获得一个使似然函数最大化的那
1)。也就是说我们的目标是找到适合的θ和z让L(θ)最
别对未知的。那我们也许会想,你就是多了一个未知的变量而已啊,我也可以分θ和z分别求偏导,再令其等于0,求解出来不也一样吗? 率密度下某个变量的边缘概率密度函数的求解,本质上我们是需要最大化(1)式(对(1)式,我们回忆下联合概量。对每一个样本注意这里
和,也就得到等式左边为随机变量i的所有可能类别z也是随机变数,但是可以看到里面有x的边缘概率密度),也就是似然函z求等式右边的联合概率密度函数以想象下未知参数log(f“和的对数”,求导后形式会非常复杂(自己可
z和1θ(x)+ f。那2OK(x)+ f,我们可否对3(x)+…)复合函数的求导),所以很难求解得到(1)式做一些改变呢?我们看(2)
式,(2)式只是分子分母同乘以一个相等的函数,还是有“和的对数”
啊,还是求解不了,那为什么要这么做呢?咱们先不管,看(3
)式,发现(3)式变成了“对数的和”,那这样求导就容易了。我们注意点,还发现等号变成了不等号,为什么能这么变呢?这就是Jensen不等式的大显神威的地方。 Jensen不等式: 设f是定义域为实数的函数,如果对于所有的实数x。如果对于所有的实数x,f(x)的二次导数大于等于0,那么f是凸函数。当x是向量时,如果其hessian矩阵H是半正定的,那么f是凸函数。如果只大于0,不等于0,那么称f是严格凸函数。Jensen不等式表述如下: 如果f是凸函数,X是随机变量,那么:E[f(X)]>=f(E[X]) 特别地,如果f是严格凸函数,当且仅当X是常量时,上式取等号。 如果用图表示会很清晰:
图中,实线f是凸函数,X是随机变量,有0.5的概率是a,有0.5的概率是b。(就像掷硬币一样)。X的期望值就是a和b的中值了,图中可以看到E[f(X)]>=f(E[X])成立。 当f是(严格)凹函数当且仅当-f是(严格)凸函数。 Jensen不等式应用于凹函数时,不等号方向反向。 回到公式(2),因为f(x)=log x 为凹函数(其二次导数为-1/x2
(2)式中
的期望,(考虑到E(X)=∑x*p(x),f(X)是X的函数,则E(f(X))=∑f(x)*p(x)),又,所以就可以得到公式(3)的不等式了:
OK,
到这里,现在式(3)就容易地求导了,但是式(2)和式(3)是不等号啊,式(2)的最大值不是式(3)的最大值啊,而我们想得到式(2)的最大值,那怎么办呢? 现在我们就需要一点想象力了,上面的式(2)和式(3)不等式可以写成:似然函数L(θ)>=J(z,Q),那么我们可以通过不断的最大化这个下界J,来使得L(θ)不断提高,最终达到它的最大值。
见上图,我们固定θ,调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等(绿色曲线到蓝色曲线),然后固定Q(z),调整θ使下界J(z,Q)tt+1达到最大值(θ到θ),然后再固定θ,调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ*。这里有两个问题:什么时候下界J(z,Q)与L(θ)在此点θ处相等?为什么一定会收敛? 首先第一个问题,在Jensen不等式中说到,当自变量X是常数的时候,等式成立。而在这里,即:
再推导下,由于(因为Q是随机变量z(i)的概率(i)密度函数),则可以得到:分子的和等于c(分子分母都对所有z求和:多个等式分子分母相加不变,这个认为每个样例的两个概率比值都是c),则:
至此,我们推出了在固定参数θ后,使下界拉升的
Q(z)的计算公式就是后验概率,解决了Q(z)如何选择的问题。这一步就是E步,建立L(θ)的下界。接下来的M步,就是在给定Q(z)后,调整θ,去极大化L(θ)的下界J(在固定Q(z)后,下界还可以调整的更大)。那么一般的EM算法的步骤如下: EM算法(Expectation-maximization): 期望最大算法是一种从不完全数据或有数据丢失的数据集(存在隐含变量)中求解概率模型参数的最大似然估计方法。 EM的算法流程: 初始化分布参数θ; 重复以下步骤直到收敛: E步骤:根据参数初始值或上一次迭代的模型参数来计算出隐性变量的后验概率,其实就是隐性变量的期望。作为隐藏变量的现估计值: M步骤:将似然函数最大化以获得新的参数值:
这个不断的迭代,就可以得到使似然函数L(θ)最大化的参数θ了。那就得回答刚才的第二个问题了,它会收敛吗? 感性的说,因为下界不断提高,所以极大似然估计单调增加,那么最终我们会到达最大似然估计的最大值。理性分析,就会得到下面的东西:
具体如何证明的,看推导过程参考:Andrew Ng 《The EM algorithm》 http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html 四、EM算法另一种理解 坐标上升法(Coordinate ascent):
图中的直线式迭代优化的路径,可以看到每一步都会向最优值前进一步,而且前进路线是平行于坐标轴的,因为每一步只优化一个变量。 这犹如在x-y坐标系中找一个曲线的极值,然而曲线函数不能直接求导,因此什么梯度下降方法就不适用了。但固定一个变量后,另外一个可以通过求导得到,因此可以使用坐标上升法,一次固定一个变量,对另外的求极值,最后逐步逼近极值。对应到EM上,E步:固定θ,优化Q;M步:固定Q,优化θ;交替将极值推向最大。 五、EM的应用 EM算法有很多的应用,最广泛的就是GMM混合高斯模型、聚类、HMM等等。具体可以参考JerryLead的cnblog中的Machine Learning专栏: (EM算法)The EM Algorithm 混合高斯模型(Mixtures of Gaussians)和EM算法 K-means聚类算法
范文二:机器学习十大经典算法简介2docx
5.最大期望(EM)算法
在统计计算中,最大期望(EM,Expectation–Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(LatentVariabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(DataClustering)领域。
6.PageRank
PageRank是Google算法的重要内容。2001年9月被授予美国专利,专利人是Google创始人之一拉里·佩奇(LarryPage)。因此,PageRank里的page不是指网页,而是指佩奇,即这个等级方法是以佩奇来命名的。
PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是,每个到页面的链接都是对该页面的一次投票,被链接的越多,就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多,一般判断这篇论文的权威性就越高。
7.AdaBoost
Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。
8.kNN:k-nearestneighborclassification
K最近邻(k-NearestNeighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
9.NaiveBayes
在众多的分类模型中,应用最为广泛的两种分类模型是决策树模型
(DecisionTreeModel)和朴素贝叶斯模型(NaiveBayesianModel,NBC)。朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。理论上,NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC模型的性能最为良好。
10.CART:分类与回归树
CART,ClassificationandRegressionTrees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法;第二个想法是用验证数据进行剪枝。
范文三:机器学习十大经典算法简介
不仅仅是选中的十大算法,其实参加评选的18种算法,实际上随便拿出一种来都可以称得上是经典算法,它们在数据挖掘领域都产生了极为深远的影响。
1.C4.5
C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算
法.C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:
1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
2)在树构造过程中进行剪枝;
3)能够完成对连续属性的离散化处理;
4)能够对不完整数据进行处理。
C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。
2.Thek-meansalgorithm即K-Means算法
k-meansalgorithm算法是一个聚类算法,把n的对象根据他们的属性分为k个分割,k 3.Supportvectormachines
支持向量机,英文为SupportVectorMachine,简称SV机(论文中一般简称SVM)。它是一种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大,分类器的总误差越小。一个极好的指南是
C.J.CBurges的《模式识别支持向量机指南》。vanderWalt和Barnard将支持向量机和其他分类器进行了比较。
4.TheApriorialgorithm
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。
范文四:机器学习十大算法C4.5中文翻译
1.什么是C4.5
C4.5是一套算法,这套算法主要用于对机器学习和数据挖掘中的分类问题。它是一种有监督的学习,也就是说对于该算法我们需要先给它提供一个数据集,这个数据集包含多个实例,每个实例都包含多个属性,该实例用这些属性进行描述,根据属性取值的不同被划分到不同的互斥类中,C4.5从提供的数据集中学习到如何将不同属性值的实例划分到不同类的映射,当我们提供全新的一套属性值的时候,它能够通过学到的映射对新的属性值进行分类。例如,查看图1-1这组训练数据,每一行对应于一个实例,属性值包括对天气的展望(对应于一个三值变量,也就是说该数据的取值只能是设置的三种情况的一种),温度(一个连续取值的变量),湿度(一个连续取值的变量)和是否有风(二进制值),所有的实例被划分为两类也就是是否适合打高尔夫。我们的目的就是从训练数据中学到一个映射,这个映射可以用于对在图中未出现的实例属性取值情况进行有效分类。
C4.5是由J.Ross Quinlan提出的,由于它是ID3(一种著名的决策树归纳算法)的后续版本,因此被如此命名。决策树的决策结点是一系列系统化安排的问题,这些问题用于测试某一具体属性(例如:对天气的展望outlook),对每个结点上问题的不同测试输出产生不同的分支,最后会达到叶子结点。叶子结点的值也就是最终的划分类别(如:是否打高尔夫)。决策树就像我们汽车的维修手册一样,我们对每一个检修问题进行排查最终确定我们的汽车什么出了问题。除了推演树,C4.5还可以将决策树用表示规则形式表示。然而对规则后剪枝操作将导致无法很好的将规则转化为决策树。
从C4.5的历史线索我们可以看出许多小团体或多或少的聚集在了一些解决思路相似的分类方法上。ID3的发展独立于Friedman设计的原始树归纳算法,这种原始树归纳算法经过Breiman,Olsen和Stone三人的改进之后变为我们熟知的CART算法。虽然上文中说ID3独立于原始树归纳算法,但是从诸多的有关CART的参考文献中我们可以看到在C4.5的设计决策的部分似乎受到了CART的影响或者由CART改进而来,例如处理特殊属性的部分。同时Quinlan本人也承认在设计ID3和C4.5的时候受到了概念学习系统CLS的影响。如今,C4.5已经完全由一种由Rulequest Reasearch,Inc提供的商业产品See5/C5.0取代。
10大算法中的两个算法是基于树的算法充分证实了这种机器学习算法在数据挖掘中的流行性。以前决策树被用于具有面值或分类数据的领域,然而如今决策树被用于具有数值的,
标记符号的以及混合类型的属性值的多种领域例如临床决策制定,制造业,文本分析,生物信息学,空间数据建模,和一些特定领域,这些领域的决策制定能够表示为一个决策树或规则的形式。
2.算法描述
C4.5并不是单单的指一个算法而是一套算法-C4.5,C4.5-no-pruning和C4.5-rules-具备很多功能。我们首先给出基本的C4.5算法,然后再讨论这些功能。
算法1.1给出了C4.5是如何运行的大体描述。该算法的框架表述还是比较清晰的,从根节点开始不断得分治,递归,生长,直至得到最后的结果。根节点代表整个训练样本集,通过在每个节点对某个属性的测试验证,算法递归得将数据集分成更小的数据集.某一节点对应的子树对应着原数据集中满足某一属性测试的部分数据集.这个递归过程一直进行下去,直到某一节点对应的子树对应的数据集都属于同一个类为止。
----------------------------------------------------------------------------------------------------------------- 算法1.1 C4.5(D)
----------------------------------------------------------------------------------------------------------------- 输入:一个属性值集合D
1:Tree={}
2:if D 无法继续划分为不同的子集 or 遇到其它停止的准则 then
3: 中止
4:end if
5:for all attribute a∈D do
6: 计算属性a的信息论度量
7:end for
8:a=根据度量值选择最适宜作为根结点的属性
9:Tree=建立一个以属性a作为决策结点的根结点
10:Dv=基于a从D中归纳出子数据集
11:for all Dv do
12: Treev=C4.5(Dv)
13: 将Treev连接到Tree的相应分支上
14:end for
15:return Tree
------------------------------------------------------------------------------------------------------------------
图1.1给出了Golf数据集,用于作为算法的输入。就如先前陈述的一样,我们的目标是预测一天的天气状况是否适宜打高尔夫。在图1.1中样本的部分属性取值是离散的,部分又是连续取值的。
图1.2是高尔夫数据集对应的决策树。下面就让我们来分析一下构造该决策树可能遇到的问题。
1.分类树中的测试是怎样的?
从如1.2可以看出,C4.5并没有对结点限制最多产生两条分支而是可以产生两种或更多种结果。如果属性是布尔类型的,将产生两条测试分支。对于属性取值为离散变量,这很简单,离散变量对应着多个值,每个值就对应着测试的一个分支,测试就是验证样本对应的属性值对应哪个分支。这样数据集就会被分成几个小组。对于连续变量,所有连续变量的测试分支都是2条,其测试分支分别对应着{=t?},t对应着分支阈值。
2.如何选择测试?
C4.5根据信息论标准来选择测试,比如增益(在信息论中,熵对应着某一分布的平均信息量,其值同时也对应着要完全无损表示该分布所需要的最小的比特数,本质上熵对应着不确定性,可能的变化的丰富程度。所谓增益,就是指在应用了某一测试之后,其对应的可能性丰富程度下降,不确定性减小,这个减小的幅度就是增益,其实质上对应着分类带来的好处)或者增益比(这个指标实际上就等于增益/熵,之所以采用这个指标是为了克服采用增益作为衡量标准的缺点,采用增益作为衡量标准会导致分类树倾向于优先选择那些具有比较多的分支的测试,这种倾向需要被抑制)。我们通常将增益比作为默认的标准。算法在进行Tree-Growth时,总是“贪婪得”选择那些信息论标准最高的那些测试。
3.如何选择连续变量的阈值?
就像前面所表述的那样,对于离散性和布尔型的属性,只需要对属性的所有可能取值进行测试就够了。然而连续型变量需要确定一个阈值,将其划分为两个范围。这阈值如何确定呢?很简单,把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序,假设该属性对应的不同的属性值一共有N个,那么总共有N-1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连
续元素的中点,那么我们的任务就是从这个N-1个候选分割阈值点中选出一个,使得前面提到的信息论标准最大。举个例子,对于Golf数据集,我们来处理温度属性,来选择合适的阈值。首先按照温度大小对对应样本进行排序如下:
----------------------------------------------------------------------------------
64 65 68 69 70 71 72 72 75 75 80 81 83 85
-----------------------------------------------------------------------------------
那么可以看到有13个可能的候选阈值点,比如middle[64,65], middle[65,68]….,middle[83,85]。那么最优的阈值该选多少呢?通过计算信息熵的方式计算每种候选阈值点的熵值,选取熵值最小的阈值点,熵值越小,增益越大,后面我们会详细的介绍熵与增益。对于临近的变量Vi与Vi+1如果取值为Vi的所有样本和取值Vi+1的所有样本属于相同的分类,选取他们之间的值作为阈值点将无法增加信息增益或增益比。通过这种方法可以减少阈值点的测试。
4.Tree-Growing如何终止?
前面提到Tree-Growing实际上是一个递归过程,那么这个递归什么时候到达终止条件退出递归呢?有两种方式,第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候,那么递归就可以终止,该分支就会产生一个叶子节点.还有一种方式就是,如果某一分支覆盖的样本的个数如果小于一个阈值,那么也可产生叶子节点,从而终止Tree-Growing。
5.如何确定叶子结点的类?
前面提到Tree-Growing终止的方式有2种,对于第一种方式,叶子节点覆盖的样本都属于同一类,那么这种情况下叶子节点的类自然不必多言。对于第二种方式,叶子节点覆盖的样本未必属于同一类,直接一点的方法就是,该叶子节点所覆盖的样本哪个类占大多数,那么该叶子节点的类别就是那个占大多数的类。
我们将现在来详细的介绍如何由图1.1得到图1.2中的树。这就涉及到测试的选择问题,前面《如何选择测试?》提到测试的选择是依据信息论标准,信息论标准有两种,一种是增益,一种是增益比。首先来看看增益Gain的计算。假设随机变量x,它可能属于c个类中
的任何一个,通过样本的统计,它分别属于各个类的概率分别为
想把某一样本进行归类所需要的熵就为:
,那么要
根据这个公式可以计算出playGolf?的熵:
所以它的熵值为0.940。它的信息论含义就是我要想把PlayGolf?这个信息传递给别人话,平均来讲我至少需要0.940个bit来传递这个信息。C4.5的目标就是经过分类来减小这个熵。那么我们来依次考虑各个属性测试,通过某一属性测试我们将样本分成了几个子集,这使得样本逐渐变得有序,那么熵肯定变小了。这个熵的减小量就是我们选择属性测试的依据。还是以Golf数据集为例,Outlook的增益Gain(Outlook),其公式如下:
它的实质是把数据集D根据某一属性测试分成v个子集,这使得数据集D变得有序,使得
数据集D的熵变小了。分组后的熵其实就是各个子集的熵的权重和。下面我们给出一个增益的具体计算过程:
通过计算我们得到Gain(Outlook)=0.940-0.694=0.246,依据同样的方法我们可以计算出其它属性对应的信息增益。可以得到第一个测试属性是Outlook。这是一个贪婪的选择只考虑眼前的最大并不考虑对将来决策的影响。,就像前面阐述的一样,当子数据集为空也就是说所有的子数据集属于同一类别落在同一叶子节点上时树的增长就停止了,我们观察到对于outlook等于overcast的样本对应的结果都是yes,所以在属性取值为overcast的方向上的树的增长就停止了。然而,对于另外两个分支,样本对应的结果并不唯一,所以需要继续递归,但是outlook属性不能再作为划分标准。对于不同的分支需要选择不同的测试属性。
到这里似乎一切都很完美,增益这个指标非常得make sense,但是其实增益这个指标有一个缺点。我们来考虑Golf数据集中的Day这个属性(我们假设它是一个真属性,实际上很可能大家不会把他当做属性),Day有14个不同的值,那么Day的属性测试节点就会有14个分支,很显然每个分支其实都覆盖了一个“纯”数据集(所谓“纯”,指的就是所覆盖的数据集都属于同一个类),那么其熵增益显然就是最大的,那么Day就默认得作为第一个属性。之所以出现这样的情况,是因为增益这个指标天然得偏向于选择那些分支比较多的属性,也就是那些具有的值比较多的那些属性。这种偏向性是我们希望克服的,我们希望公正地评价所有的属性。因此又一个指标被提出来了 Gain Ratio-增益比。某一属性A的增益比计算公式如下:
Entropy(A)实际上就是属性A的熵,只不过这个熵有所不同,他不是样本最终分类{PlayGolf?}的熵,而是对应属性分组{A?}的熵,它反映的是属性A本身的信息量。下面我给出一个计算增益比GainRatio(Outlook)的例子:
1:已知Gain(Outlook)=0.246
2:属性Outlook的熵Entropy:
Sunny概率:5/14 Overcast:4/14 Rainy:5/14
Entropy=-5/14log2(5/14) -4/14log2(4/14) -5/14log2(5/14) #注意与上面熵计算方法的不同
通过计算我们很容易得到GainRatio(Outlook)=0.246/1.577=0.156。增益比实际上就是对增益进行了归一化,这样就避免了指标偏向分支多的属性的倾向。
1.3 C4.5的功能
1.3.1 树的剪枝
决策树为什么要剪枝?原因就是避免决策树“过拟合”样本。前面的算法生成的决策树非常的详细而庞大,每个属性都被详细地加以考虑,决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话,你会发现对于训练样本而言,这个树表现堪称完美,它可以100%完美正确得对训练样本集中的样本进行分类(因为决策树本身就是100%完美拟合训练样本的产物)。但是这会带来一个问题,如果训练样本中包含了一些错误,按照前面的算法,这些错误也会100%一点不留得被决策树学习了,这就是“过拟合”。C4.5的缔造者昆兰教授很早就发现了这个问题,他作过一个试验,在某一个数据集中, 过拟合的决策树的错误率比一个经过简化了的决策树的错误率要高。那么现在的问题就来了,如何在原生的过拟合决策树的基础上,通过剪枝生成一个简化了的决策树?
第一种方法,也是最简单的方法,称之为基于误判的剪枝。这个思路很直接,完全的决策树不是过度拟合么,我再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树,我们尝试着把它替换成一个叶子节点,该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替,这样就产生了一个简化决策树,然后比较这两个决策树在测试数据集中的表现,如果简化决策树在测试数据集中的错误比较少,并且该子树里面没有包含另外一个具有类似特性的子树(所谓类似的特性,指的就是把子树替换成叶子节点后,其测试数据集误判率降低的特性),那么该子树就可以替换成叶子节点。该算法以bottom-up的方式遍历所有的子树,直至没有任何子树可以替换使得测试数据集的表现得以改进时,算法就可以终止。
第一种方法很直接,但是需要一个额外的测试数据集,能不能不要这个额外的数据集呢?为了解决这个问题,于是就提出了悲观剪枝。悲观剪枝是C4.5的一种创新。该方法剪枝的依据是训练样本集中的样本误判率。我们知道一颗分类树的每个节点都覆盖了一个样本集,根据算法这些被覆盖的样本集往往都有一定的误判率,因为如果节点覆盖的样本集的个数小于一定的阈值,那么这个节点就会变成叶子节点,所以叶子节点会有一定的误判率。而每个节点都会包含至少一个的叶子节点,所以每个节点也都会有一定的误判率。悲观剪枝就是递归得估算每个内部节点所覆盖样本节点的误判率。剪枝后该内部节点会变成一个叶子节点,该叶子节点的类别为原内部节点的最优叶子节点所决定。然后比较剪枝前后该节点的错误率来决定是否进行剪枝。该方法和前面提到的第一种方法思路是一致的,不同之处在于如何估计剪枝前分类树内部节点的错误率。
悲观剪枝的思路非常巧妙。把一颗子树(具有多个叶子节点)的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的(这是很显然的,同样的样本子集,如果用子树分类可以分成多个类,而用单颗叶子节点来分的话只能分成一个类,多个类肯定要准确一些)。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点,它覆盖了N个样本,其中有E个错误(也就是说本不应该划分到这个类的样本,样本中却将其划分到了该类,这就是错误),那么该叶子节点的错误率为(E+0.5)/N。这个0.5就是惩罚因子,那么一颗子树,它有L个叶子节点,那么该子树的误判率估计
为
。现在,假设我们用最优叶子节点替换掉了子树,我们
通过测试数据的测试发现它误判的次数为J,当J+0.5在范围内时,
悲观剪枝就用这个最优叶子节点替换掉子树。
这个方法可以被扩展为基于期望置信区间的剪枝。我们可以将叶子节点的误差率e建模成伯努利随机变量。对于一个给定的显著性因子CL,对于一个上界emax我们有e
那么一棵树错误分类一个样本值为1,正确分类一个样本值为0,该树错误分类的概率(误判率)为e(e为分布的固有属性,可以通过统计出来),那么树的误判次数就是伯努利分布,我们可以估计出该树的误判次数均值和标准差:
把子树替换成叶子节点后,该叶子的误判次数也是一个伯努利分布,其概率误判率e为(E+0.5)/N,因此叶子节点的误判次数均值为
使用训练数据,子树总是比替换为一个叶节点后产生的误差小,但是使用校正后有误差计算方法却并非如此,当子树的误判个数大过对应叶节点的误判个数一个标准差之后,就决定剪枝:
这个条件就是剪枝的标准。
当并不一定非要大一个标准差,可以给定任意的置信区间,我们设定一定的显著性因子,就可以估算出误判次数的上下界。
比如T4这棵子树的误差率:
子树误差率的标准误差:
子树替换为一个叶节点后,其误差率为:
因为,所以决定将子树T4替换这一个叶子节点。
1.3.2 连续值属性的改进
相对于那些离散值属性,分类树算法倾向于选择那些连续值属性,因为连续值属性会有更多的分支,熵增益也最大。算法需要克服这种倾向。还记得前面讲得如何克服分类树算法倾向于离散值较多的离散属性么?对了,我们利用增益率来克服这种倾向。增益率也可以用来克服连续值属性倾向。增益率作为选择属性的依据克服连续值属性倾向,这是没有问题的。但是如果利用增益率来选择连续值属性的分界点,会导致一些副作用。分界点将样本分成两个部分,这两个部分的样本个数之比也会影响增益率。根据增益率公式,我们可以发现,当分界点能够把样本分成数量相等的两个子集时(我们称此时的分界点为等分分界点),增益率的抑制会被最大化,因此等分分界点被过分抑制了。子集样本个数能够影响分界点,显然不合理。因此在决定分界点是还是采用增益这个指标,而选择属性的时候才使用增益率这个 指标。这个改进能够很好得抑制连续值属性的倾向。当然还有其它方法也可以抑制这种倾向,比如MDL,有兴趣的读者可以自己阅读相关文章。
1.3.3 处理缺失属性
如果有些训练样本或者待分类样本缺失了一些属性值,那么该如何处理?要解决这个问题,需要考虑个问题:i)当开始决定选择哪个属性用来进行分支时,如果有些训练样本缺失了某些属性值时该怎么办?ii)一个属性已被选择,那么在决定分支的时候如果有些样本缺失了该属性该如何处理?iii)当决策树已经生成,但待分类的样本缺失了某些属性,这些属性该如何处理?针对这三个问题,昆兰提出了一系列解决的思路和方法。
对于问题i),计算属性a的增益或者增益率时,如果有些样本没有属性a,那么可以有这么几种处理方式:(I)忽略这些缺失属性a的样本。(C)给缺失属性 a的样本赋予属性a一个均值或者最常用的的值。(R)计算增益或者增益率时根据缺失属性样本个数所占的比率对增益/增益率进行相应的“打折”。(S)根据 其他未知的属性想办法把这些样本缺失的属性补全。
对于问题ii),当属性a已经被选择,该对样本进行分支的时候,如果有些样本缺失了属性a,那么:(I)忽略这些样本。(C)把这些样本的属性a赋予一个均值或者最常出现的值,然后再对他们进行处理。(R)把这些属性缺失样本,按照具有属性a的样本被划分成的子集样本个数的相对比率,分配到各个子集中去。至于哪些缺失的样本被划分到子集1,哪些被划分到子集2,这个没有一定的准则,可以随机而动。(A)把属性缺失样本分配给所有的子集,也就是说每个子集都有这些属性缺失样本。(U)单独为属性缺失的样本划分一个分支子集。(S)对于缺失属性a的样本,尝试着根据其他属性给他分配一个属性a的值,然后继续处 理将其划分到相应的子集。
对于问题iii),对于一个缺失属性a的待分类样本,有这么几种选择:(U)如果有单独的确实分支,依据此分支。(c)把待分类的样本的属性a值分配一个 最常出现的a的属性值,然后进行分支预测。(S)根据其他属性为该待分类样本填充一个属性a值,然后进行分支处理。(F)在决策树中属性a节点的分支上,遍历属性a节点的所有分支,探索可能所有的分类结果,然后把这些分类结果结合起来一起考虑,按照概率决定一个分类。(H)待分类样本在到达属性a节点时就终止分类,然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。
1.3.4 推理规则
C4.5决策树能够根据决策树生成一系列规则集,我们可以把一棵决策树看成一系列规
则的组合。一个规则对应着从根节点到叶子节点的路径,该规则的条件是路径上的条件,结果是叶子节点的类别。C4.5首先根据决策树的每个叶子节点生成一个规则集,对于规则集中的每条规则,算法利用“爬山”搜索来尝试是否有条件可以移除,由于移除一个条件和剪枝一个内部节点本质上是一样的,因此前面提到的悲观剪枝算法也被用在这里进行规则简化。MDL准则在这里也可以用来衡量 对规则进行编码的信息量和对潜在的规则进行排序。简化后的规则数目要远远小于决策树的叶子节点数。根据简化后的规则集是无法重构原来的决策树的。规则集相比决策树而言更具有可操作性,因此在很多情况下我们需要从决策树中推理出规则集。C4.5有个缺点就是如果数据集增大了一点,那么学习时间会有一个迅速地增长。
范文五:机器学习工程师必知的十大算法
英文原文:http://www.kdnuggets.com/2016/08/10-algorithms-machine-learning-engineers.html/2
毫无疑问,机器学习/人工智能的子领域在过去几年越来越受欢迎。目前大数据在科技行业已经炙手可热,而基于大量数据来进行预测或者得出建议的机器学习无疑是非常强大的。一些最常见的机器学习例子,比如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有关,但是当这些经典方法完全失效时,它是一种更强大的技术,能够找出源的潜在因素。 其应用包括数字图像、文档数据库、经济指标和心理测量。
现在运用你对这些算法的理解去创造机器学习应用,为世界各地的人们带来更好的体验吧。
转载请注明出处范文大全网 » 机器学习十大算法之一