机器学习

大数据和机器学习部分的知识点整理。包括,决策树,贝叶斯分类,感知机perceptron和支持向量机SVM。


决策树

决策树是一种基本的分类与回归方法,它可以看作if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

对于决策树的定义

决策树十分贴近人在做决策时候的过程,难度是如何divide 每个 attribute,可能性太多。决策树的实现算法

贝叶斯分类

贝叶斯分类是一类分类算法的总称,都以贝叶斯定理为基础。这边介绍的是朴素贝叶斯。

贝叶斯公式如下:

换个表达形式:

对于一个新输入的例子,我们知道所有的特征,那么可以求各个类别的概率$Pr[类别 | 特征]$, 根据其中最大的给新输入的例子进行分类。

朴素贝叶斯之所以被叫做朴素贝叶斯,是因为这个算法假设各个特征之间相互独立。也就是

一个是否能够得到贷款的例子,已知的样本如下:

那么如果对一个新输入, 有 40+,undergrad, self-employed 这三个对应的特征,计算拿不到贷款的概率。

对于拼在一起的属性我们利用特征之间的相互独立拆开之后就能计算。

SVM(支持向量机)

线性可分与超平面

$D_0$和$D_1$ 是 n 维欧氏空间中的两个点集。如果存在 n 维向量 w 和实数 b,使得所有属于$D_0$的点$x_i$都有$wx_i + b > 0$, 而对于所有属于$D_1$的点$x_j$ 则有$wx_j + b < 0$,则我们称 $D_0$ 和 $D_1$线性可分。将$D_0$和$D_1$完全正确地划分开的$wx + b = 0$ 就成了一个超平面。

SVM的目的

找到一个超平面使得距离两个类别的最近的样本最远(margin最大),这个超平面也被称为最大间隔超平面。

支持向量

样本中距离超平面最近的一些点,这些点叫做支持向量。

软间隔

对于不能够完全线性可分的样本,我们允许部分样本点不满足约束条件, 也就是允许部分样本点出现在margin区域里面。

核函数

对于那些不线性可分的情况,我们需要将在目前维度线性不可分的样本映射到更高维空间中,让样本点在更高维空间线性可分。这就是非线性SVM。

这时候超平面可以表示为

求解非线性SVM的优化问题(关于利用拉格朗日乘数法和强对偶性强化的部分见参考链接)式子中,之前的$x_i \cdot x_j$变成了需要计算$\phi(x_i) \cdot \phi(x_j)$
。因为低维空间映射到高维空间后维度可能会很大,将全部样本的点乘全部计算好,计算量太大。

核函数就是达到了$k(x,y) = \phi(x) \cdot \phi(y)$, 使得高维空间的两点的内积等于它们在原始样本空间中通过函数$k(x,y)$。 常见的核函数有,线性核函数,多项式核函数,高斯核函数。

关于这部分的内容我推荐知乎上一个写的很好的回答。关于SVM的概念和SVM的数学推导过程里面都有。

知乎回答

Perceptron(感知机)

感知机是一个简单的监督学习的机器学习算法,也是最早的神经网络结构。作为一个二分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别。

感知机和SVM都是为了解决线性可分的,所以很多地方看上去会很像:

感知机追求最大程度的正确划分,最小化错误,很容易过拟合;支持向量机追求在大致正确分类的同时(因为有软间隔的概念),最大化margin,所以一定程度上避免了过拟合。

感知机的损失函数

感知机的损失函数是根据所有误分类点到超平面$S$的总距离来定的,假设超平面$S$的误分类点集合为$M$:

由于$w$的L2范数$|w|$ 本身就和 $w$有固定的倍数关系,并不会影响这个优化问题的最终求解。最终的损失函数定义为:

感知机的学习算法

原始形式:

感知机学习算法是误分类驱动的,采用随机梯度下降法 stochastic gradient descent。一次随机选取一个误分类点使其梯度下降。

根据上面的损失函数,简单求导一下,对应的梯度为:

随机选取一个误分类点$(x_i,y_i)$, 对 w,b 进行更新:

$\eta (0 < \eta \leq 1)$是步长,也就是学习率。

当一个实例点被误分类,即位于超平面的错误一侧,则调整$w,b$的值,使超平面向该误分类点的一侧移动,以减少该误分类点与超平面的距离,直至超平面越过该分类点使其被分类正确。

感知机的算法是可以证明其收敛性的,有限次数之后能对一个线性可分的数据集合完成分类。

假定$\gamma$ 是超平面margin最大值。$R = \max\limits_{1\leq i \leq N}| \hat{x_i} |$, 也就是点集里面离坐标原点的最大距离。那么这个有限次数k满足

流程如下

输入:训练数据集 $T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$,其中$x_i \in \mathcal{X} = R^n$, $y_i \in \mathcal{Y} = \{+1,-1\}, i=1,2,…,N$;学习率 $\eta (0 < \eta \leq 1)$。

输出:$\mathbf{w},b$ ;感知机模型 $f(x)=sign(\mathbf{w} \cdot x + b)$,其中 $\mathbf{w} = (w_1, w_2, … , w_N)$

1.$\mathbf{w} \leftarrow 0$, $b \leftarrow 0$
2.在训练集中选取数据$(x_i,y_i)$
3.如果 $y_i(\mathbf{w} \cdot x_j + b) \leq 0$

4.转到2不断重复,直到训练集里面没有误分类的点。

感知机算法的对偶形式

对偶形式算是对上面算法的改进,流程如下

输入:训练数据集 $T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$,其中$x_i \in \mathcal{X} = R^n$, $y_i \in \mathcal{Y} = \{+1,-1\}, i=1,2,…,N$;学习率 $\eta (0 < \eta \leq 1)$。

输出:$\mathbf{w},b$ ;感知机模型 $f(x)=sign(\sum\limits^N_{j=1} w_{j} y_j x_j \cdot x + b)$,其中 $\mathbf{w} = (w_1, w_2, … , w_N)$

1.$\mathbf{w} \leftarrow 0$, $b \leftarrow 0$
2.在训练集中选取数据$(x_i,y_i)$
3.如果 $y_i(\sum\limits_{j=1}^{N} w_j y_j x_j \cdot x_{i} + b) \leq 0$

4.转到2不断重复,直到训练集里面没有误分类的点。

sign函数,符号函数,对于$x \geq 0$, $sign(x)=1$; 对于对于$x < 0$, $sign(x)=-1$;

第三个判断误分类的形式里面是计算两个样本$x_i$和$x_j$的内积,而且这个内积计算的结果在下面的迭代次数中可以重用。如果我们事先用矩阵运算计算出所有的样本之间的内积,即用矩阵存储实例间内积$ G = [x_i, x_j]_{N\times N}$ 那么在算法运行时,仅仅一次的矩阵内积运算比多次的循环计算省时。

参考:感知机(Perceptron)及python实现

SVM与Perceptron的区别

1.普通的感知机不能产生大间隔(margin),但是SVM可以。
2.加入了L2正则化的带margin的感知机基本就是SVM。

Perceptron对应的优化问题:

SVM(soft margin)对应的优化问题:

感知器是不能产生大间隔的,因为它只以分对为目的,不关心分界面离数据点有多远,从它的目标函数很容易看出来。

SVM和perceptron区别之一是SVM使用了hinge损失函数,而perceptron采用0/1损失函数,分对了就没损失。这个改进使得感知器具备了产生大间隔的潜质,hinge loss不仅要分类正确,而且置信度足够高的时候,损失才为0,对学习有更高的要求。其实这个道理和SVM中的margin是相符合的,不仅要分类正确,还要使得margin最大化。后面部分加上的是L2正则化,避免产生无意义的大函数间隔,而是产生大的几何间隔。

下面是hinge loss的图像,也叫合页损失函数:

参考链接:感知机(perceptron)和支持向量机(svm)是一种东西吗?
如果不是那他们的区别和关系是什么? - DeAlVe的回答 - 知乎

大数据知识点

minHash(最小哈希)和LSH(局部敏感哈希)

https://blog.csdn.net/liujan511536/article/details/47729721

数据挖掘基础

https://www.jianshu.com/p/a83a52da14a2?open_source=weibo_search

哈希表与哈希函数

https://blog.csdn.net/zhoujing_0424/article/details/50817468

apriori 算法

https://www.edureka.co/blog/apriori-algorithm/

https://www.jianshu.com/p/2ee0a247a8cc

bloomfilter

https://llimllib.github.io/bloomfilter-tutorial/zh_CN/

数据流挖掘_Flajolet-Martin算法

https://blog.csdn.net/llwszjj/article/details/25629009

各类距离

https://my.oschina.net/hunglish/blog/787596

几种聚类

https://blog.csdn.net/sherrylml/article/details/49363509

矩阵分解

https://blog.csdn.net/bitcarmanlee/article/details/52662518

SVD - 奇异值分解

https://zhuanlan.zhihu.com/p/26306568
https://www.cnblogs.com/bjwu/p/9358777.html

最大似然估计

https://zhuanlan.zhihu.com/p/26614750

PMF

https://blog.csdn.net/shenxiaolu1984/article/details/50372909

pagerank

https://blog.csdn.net/leadai/article/details/81230557
https://www.jianshu.com/p/153e2009393a

hadoop 集群部署

https://blog.csdn.net/u014253748/article/details/78221472

hdfs

https://www.cnblogs.com/lidhtdream/p/10091998.html