欢迎光临散文网 会员登陆 & 注册

机器学习算法归纳

2023-08-09 17:23 作者:请问您吃柚子嘛  | 我要投稿

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

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


监督学习(Supervised learning)


监督学习:训练含有很多特征的数据集,不过数据集中的样本都有一个标签目标(粗略地说,监督学习算法是给定一组输入x和输出y的训练集,学习如何关联输入和输出。在许多情况下,输出 y 很难自动收集,必须由人来提供 ‘‘监督’’)

监督学习分为分类回归两大类

分类:将输入数据划分到合适的类别(即标识对象所属的类别),预测的是离散值(例:预测天气情况,判断账号是否被盗,手写数字的自动识别等) 

程序需要指定某些输入属于k类中的哪一类,学习算法会输出一个函数:

f%3A%E2%84%9D%5En%20%5Crightarrow  {1%2C2....%2Ck} (%E2%84%9D%5En即n维实数集

y%3Df(x)时,模型会将向量x所代表的输入分类到y所属的类别

回归:依据输入数据预测与对象关联的连续值属性(即根据先前观察的数据预测数值),预测的是连续值(例:房价变化预测,股价预测等)

程序需要对给定输入预测数值,学习算法同样会输出函数:

f%3A%E2%84%9D%5En%5Crightarrow%20%E2%84%9D

y%3Df(x)时,模型会依据向量x所代表的输入值,输出y的值


1、分类算法

1.1 K近邻(K-Nearest Neighbor) 算法(又称KNN算法)

定义:如果⼀个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某⼀个类别,则该样本也属于这个类别

近朱者赤,近墨者黑

工作机制:

对未知类别的数据集中的每个样本进行以下操作:

①计算已知类别数据集中的样本点与当前样本点之间的距离

(距离度量特征空间中两个实例点之间的距离是二者相似程度的反应。人话翻译:两个点越靠近,则我们认为这两个样本越相似。有多种常见的距离衡量方法。 如欧几里得距离、曼哈顿距离、闵科夫斯基距离、切比雪夫距离及余弦距离)

②按照距离的递增关系进行排序;

③选取距离最小的K个样本;

④根据这K个样本的标签进行投票,K个样本中出现最多次的类别为预测结果


算法过程:

1) 输入训练数据集:T%20%3D {(x_1%2Cy_1)%2C(x_2%2Cy_2)%2C...%2C(x_i%2Cy_i)} ,x_i%3D{x_%7Bi1%7D%2Cx_%7Bi2%7D%2C...%2Cx_%7Bid%7D} (x_i是实例的特征向量,x_id个特征,y_i是实例的类别,y_i%5Cin%20(c_1%2Cc_2%2C...%2Cc_j)i%3D1%2C2%2C3%2C...%2CN%2Cj%3D1%2C2%2C...%2CK

2) 对给定测试样本实例X(x_%7B1%7D%2Cx_%7B2%7D%2C...%2Cx_%7Bd%7D),选择训练数据集样本Y(x_%7Bi1%7D%2Cx_%7Bi2%7D%2C...%2Cx_%7Bid%7D)

3) 通过选定的距离度量方法(此处使用欧式距离),计算样本点之间的距离:

dist_%7Bed%7D(X%2CY)%3D%5Csqrt%5B%5D%7B(x_1-x_%7Bi1%7D)%5E2%2B(x_2-x_%7Bi2%7D)%5E2%2B...%2B(x_d-x_%7Bid%7D)%5E2%7D%20

4) 依次计算距离得到距离集合distance,将集合distance从小到大进行排序

5) 根据集合distance选取最邻近的k个点

6) 将以测试样本实例点X为中心,周围涵盖K个点的邻域记作B_k(x)

7) 通过多数分类决策(即“投票法”,少数服从多数):y%3D%5Cunderset%7Bcj%7Dargmax%5Csum_%7Bx_i%5Cin%20B_k(x)%7D%5Cmathbb%20I(y_i%3Dc_j)%2Ci%3D1%2C2%2C...%2CN%2Cj%3D1%2C2%2C...%2CK

(%5Cmathbb%20I()为指示函数,当输入为True时返回1,输入为False时返回0)

8) 得到实例x所属的类别y


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样本不平衡的时候,对稀有类别的预测准确率低

3KD树,球树之类的模型建立需要大量的内存

4是懒散学习方法,基本上不学习,导致预测时速度比起逻辑回归之类的算法慢

5相比决策树模型,KNN模型的可解释性不强


1.2  Logistic回归算法(Logistic Regression)

未完待续....








机器学习算法归纳的评论 (共 条)

分享到微博请遵守国家法律