草庐IT

机器学习经典算法总结

armcvai 2023-03-28 原文

一，KNN 算法

K 近邻算法（KNN）是一种基本分类和回归方法。KNN 算法的核心思想是如果一个样本在特征空间中的 k 个最相邻的样本中的大多数属于一个类别，那该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。 如下图：

在 KNN 中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离，公式如下：

同时，KNN通过依据 k 个对象中占优的类别进行决策，而不是单一的对象类别决策，这两点就是KNN算法的优势。

1.1，k 值的选取

  • k 值较小，模型会变得复杂，容易发生过拟合
  • k 值较大，模型比较简单，容易欠拟合

所以 k 值得选取也是一种调参？

1.2，KNN 算法思路

KNN 思想就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前 K 个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

  1. 计算测试数据与各个训练数据之间的距离；
  2. 按照距离的递增关系进行排序；
  3. 选取距离最小的 K 个点；
  4. 确定前 K 个点所在类别的出现频率；
  5. 返回前 K 个点中出现频率最高的类别作为测试数据的预测分类。

二，支持向量机算法

机器学习中的算法(2)-支持向量机(SVM)基础

2.1，支持向量机简述

  • 支持向量机（Support Vector Machines, SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使其成为实质上的非线性分类器。
  • SVM 的学习策略是找到最大间隔（两个异类支持向量到超平面的距离之和 \(\gamma = \frac{2}{||w}\) 称为“间隔”），可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。
  • SVM 的最优化算法是求解凸二次规划的最优化算法。

2.2，SVM 基本型

\[min \frac{1}{2}||w||^2 \\ s.t. y_{i}(w^Tx_i + b) \geq 1, i = 1,2,...,m \]

SVM 的最优化算法是一个凸二次规划（convex quadratic programming）问题，对上式使用拉格朗日乘子法可转化为对偶问题，并优化求解。

2.3，对偶问题求解

对 SVM 基本型公式的每条约束添加拉格朗日乘子 \(\alpha_i \geq 0\)，则式子的拉格朗日函数如下：

\[L(w,b,a) = \frac 1 2||w||^2 - \sum{i=1}{n} \alpha_i (y_i(w^Tx_i+b) - 1) \]

经过推导（参考机器学习西瓜书），可得 SVM 基本型的对偶问题：

\[\max\limits_{\alpha} \sum_{i=1}^{m}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x^{T}\_{i} x_j \]

\[s.t. \sum_{i=1}^{m} = \alpha_{i}y_{i} = 0 \]

\[\alpha_{i}\geq 0, i=1,2,...,m \]

继续优化该问题，有 SMO 方法，SMO 的基本思路是先固定 \(\alpha_i\) 之外的的所有参数，然后求 \(\alpha_i\) 上的极值。

三，K-means 聚类算法

3.1，分类与聚类算法

  • 分类简单来说，就是根据文本的特征或属性，划分到已有的类别中。也就是说，这些类别是已知的，通过对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。
  • 聚类，就是你压根不知道数据会分为几类，通过聚类分析将数据或者说用户聚合成几个群体，那就是聚类了。聚类不需要对数据进行训练和学习。
  • 分类属于监督学习，聚类属于无监督学习。常见的分类比如决策树分类算法、贝叶斯分类算法等聚类的算法最基本的有系统聚类，K-means 均值聚类。

3.2，K-means 聚类算法

聚类的目的是找到每个样本 \(x\) 潜在的类别 \(y\)，并将同类别 \(y\) 的样本 \(x\) 放在一起。在聚类问题中，假定训练样本是 \({x^1,...,x^m}\)，每个 \(x^i \in R^n\)，没有 \(y\)。K-means 算法是将样本聚类成 \(k\) 个簇（cluster），算法过程如下：

  1. 随机选取 \(k\) 个聚类中心（cluster centroids）为 \(\mu_1, \mu_1,...,\mu_k \in R^n\)。
  2. 重复下面过程，直到质心不变或者变化很小：
    • 对于每一个样例 \(i\) ，计算其所属类别：$$c^i = \underset{j}{argmin}||x^i - \mu_j||^2$$
    • 对于每一个类 \(j\)，重新计算该类的质心：$$\mu_j = \frac {\sum_{i=1}^{m} 1{c^i} = jx^{i}} { \sum_{i=1}^{m}1 c^{i} = j}$$

\(K\) 是我们事先给定的聚类数，\(c^i\) 代表样例 \(i\) 与 \(k\) 个类中距离最近的那个类，\(c^i\) 的值是 \(1\) 到 \(k\) 中的一个。质心 \(\mu_j\) 代表我们对属于同一个类的样本中心点的猜测。

参考资料

K-means聚类算法

机器学习机器spancodeclass人工智能

有关机器学习经典算法总结的更多相关文章

  1. ruby - 在 Windows 机器上使用 Ruby 进行开发是否会适得其反？ - 2

    这似乎非常适得其反，因为太多的gem会在window上破裂。我一直在处理很多mysql和ruby​​-mysqlgem问题(gem本身发生段错误，一个名为UnixSocket的类显然在Windows机器上不能正常工作，等等)。我只是在浪费时间吗？我应该转向不同的脚本语言吗？ 最佳答案 我在Windows上使用Ruby的经验很少，但是当我开始使用Ruby时，我是在Windows上，我的总体印象是它不是Windows原生系统。因此，在主要使用Windows多年之后，开始使用Ruby促使我切换回原来的系统Unix，这次是Linux。Rub

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  4. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  5. SPI接收数据异常问题总结 - 2

    SPI接收数据左移一位问题目录SPI接收数据左移一位问题一、问题描述二、问题分析三、探究原理四、经验总结最近在工作在学习调试SPI的过程中遇到一个问题——接收数据整体向左移了一位（1bit）。SPI数据收发是数据交换，因此接收数据时从第二个字节开始才是有效数据，也就是数据整体向右移一个字节（1byte）。请教前辈之后也没有得到解决，通过在网上查阅前人经验终于解决问题，所以写一个避坑经验总结。实际背景：MCU与一款芯片使用spi通信，MCU作为主机，芯片作为从机。这款芯片采用的是它规定的六线SPI，多了两根线：RDY和INT，这样从机就可以主动请求主机给主机发送数据了。一、问题描述根据从机芯片手

  6. CAN协议的学习与理解 - 2

    最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  7. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  8. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  9. ruby - 我的 Ruby IRC 机器人没有连接到 IRC 服务器。我究竟做错了什么？ - 2

    require"socket"server="irc.rizon.net"port="6667"nick="RubyIRCBot"channel="#0x40"s=TCPSocket.open(server,port)s.print("USERTesting",0)s.print("NICK#{nick}",0)s.print("JOIN#{channel}",0)这个IRC机器人没有连接到IRC服务器，我做错了什么？ 最佳答案 失败并显示此消息::irc.shakeababy.net461*USER:Notenoughparame

  10. ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2

    我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or

随机推荐