机器学习算法归纳
记忆力越来越差了(是不是要痴呆了abab),老是翻笔记找不到想要的,心血来潮写篇专栏供随时查阅(脖子好痒,好像要长脑子了.jpg >w<) 错误之处,欢迎指正。

机器学习的学习方式主要分为4大类:监督学习、无监督学习、半监督学习、强化学习

监督学习(Supervised learning)
监督学习:训练含有很多特征的数据集,不过数据集中的样本都有一个标签或目标(粗略地说,监督学习算法是给定一组输入x和输出y的训练集,学习如何关联输入和输出。在许多情况下,输出 y 很难自动收集,必须由人来提供 ‘‘监督’’)
监督学习分为分类和回归两大类
分类:将输入数据划分到合适的类别(即标识对象所属的类别),预测的是离散值(例:预测天气情况,判断账号是否被盗,手写数字的自动识别等)
程序需要指定某些输入属于类中的哪一类,学习算法会输出一个函数:
{
} (
即n维实数集)
当时,模型会将向量
所代表的输入分类到
所属的类别
回归:依据输入数据预测与对象关联的连续值属性(即根据先前观察的数据预测数值),预测的是连续值(例:房价变化预测,股价预测等)
程序需要对给定输入预测数值,学习算法同样会输出函数:
当时,模型会依据向量
所代表的输入值,输出
的值

1、分类算法
1.1 K近邻(K-Nearest Neighbor) 算法(又称KNN算法)
定义:如果⼀个样本在特征空间中的个最相似(即特征空间中最邻近)的样本中的大多数属于某⼀个类别,则该样本也属于这个类别
近朱者赤,近墨者黑
工作机制:
对未知类别的数据集中的每个样本进行以下操作:
①计算已知类别数据集中的样本点与当前样本点之间的距离
(距离度量:特征空间中两个实例点之间的距离是二者相似程度的反应。人话翻译:两个点越靠近,则我们认为这两个样本越相似。有多种常见的距离衡量方法。 如欧几里得距离、曼哈顿距离、闵科夫斯基距离、切比雪夫距离及余弦距离)
②按照距离的递增关系进行排序;
③选取距离最小的K个样本;
④根据这K个样本的标签进行投票,K个样本中出现最多次的类别为预测结果
算法过程:
1) 输入训练数据集: {
} ,
{
} (
是实例的特征向量,
有
个特征,
是实例的类别,
)
2) 对给定测试样本实例,选择训练数据集样本
3) 通过选定的距离度量方法(此处使用欧式距离),计算样本点之间的距离:
4) 依次计算距离得到距离集合,将集合
从小到大进行排序
5) 根据集合选取最邻近的k个点
6) 将以测试样本实例点为中心,周围涵盖K个点的邻域记作
7) 通过多数分类决策(即“投票法”,少数服从多数):
(为指示函数,当输入为True时返回1,输入为False时返回0)
8) 得到实例所属的类别
K值的选择:
近似误差:对现有训练集的训练误差
估计误差:对测试集的测试误差
过拟合:训练误差和测试误差之间的差距太大 ,对训练集的预测比较准确,但对未知的测试集的预测将出现较大误差
欠拟合:模型不能在训练集上获得足够低的误差,对训练集和测试集的预测都有较大误差
1) 选择较小的K值,就相当于用较小的领域中的训练实例进行预测
K值的减小就意味着整体模型变得复杂,近似误差减小,估计误差增大,容易发生过拟合
取极端最近邻情况K=1,此时最靠近测试样本点A的训练样本点B决定了A的类别,如果B恰好为训练样本中的噪声,我们将得出错误的结论,也就是说过小的k值增大了噪声的影响,产生了偏差
2) 选择较大的K值,就相当于用较大领域中的训练实例进行预测
K值的增大就意味着整体的模型变得简单,估计误差减小,近似误差增大,容易发生欠拟合
当k值过大时,此时距离测试样本点A非常远的训练样本点C也会对预测起作用,由于C离A点非常远,我们可以认为C与A不相似,所以同样会使得预测产生偏差。
3) K=N(N为训练样本个数),那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类,模型过于简单,忽略了训练实例中大量有用信息。
在实际应用中,K值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值
K应尽量选择奇数,在二分类问题中,容易防止平局
KD树
当使用KNN算法进行预测时,每预测一个点,都需要计算训练数据集里每个点到这个点的距离,然后选出距离最近的k个点进行投票。当数据集很大时,这个计算成本非常高。(即线性扫描,穷举搜索)
为了避免每次都重新计算⼀遍距离,算法会把距离信息保存在⼀棵树里,在计算之前从树里查询距离信息, 尽量避免重新计算。(如果A和B距离很远,B和C距离很近,那么A和C的距离也很远)
构造方法:
1)构造根结点,使根结点对应于K维空间中包含所有实例点的超矩形区域;
2)通过递归的方法,不断地对k维空间进行切分,生成子结点。
①对每个维度的数据进行方差计算,取最大方差的维度作为分割轴
②对当前数据按分割轴维度进行检索,找到中位数数据,作为切分点
③通过切分点并垂直于分割轴,就可以确定一个超平面,这个超平面就将超矩形中的实例分到了两个子区域(子结点),左子结点对应坐标小于切分点的子区域,右子结点对应坐标大于切分点的子区域
3)上述过程直到子区域内没有实例时终止(终止时的结点为叶结点)
K近邻算法总结
适用场景:多分类问题
稀有事件分类问题
文本分类问题
模式识别
聚类分析
样本数量较少的分类问题
优点:
1)简单,易于理解,易于实现,无需估计参数,无需训练,既可以用来做分类也可以用来做回归;
2)适合对稀有事件进行分类;
3)适合大样本自动分类,特别适合于多分类问题(multi-modal,对象具有多个类别标签)
缺点:
1)计算量大,尤其是特征数非常多的时候
2)样本不平衡的时候,对稀有类别的预测准确率低
3)KD树,球树之类的模型建立需要大量的内存
4)是懒散学习方法,基本上不学习,导致预测时速度比起逻辑回归之类的算法慢
5)相比决策树模型,KNN模型的可解释性不强

1.2 Logistic回归算法(Logistic Regression)
未完待续....