K-NN和K-means算法讲解

k-means算法k-means算法是无监督学习领域最为经典的算法之一。

接触聚类算法，首先需要了解k-means算法的实现原理和步骤。

本文将对k-means算法的基本原理和实现实例进行分析。

希望对喜欢机器学习的童鞋们，有一定的帮助和启发。

首先看看wiki上对k-means算法的基本阐述。

k-means clustering is a method of vectorquantization, originally from signalprocessing, that is popular for clusteranalysis in data mining. k-means clusteringaims to partition n observations into kclusters in which each observation belongs tothe cluster with the nearest mean, serving asa prototype of the cluster.可以看出，k-means算法就是将 n 个数据点进行聚类分析，得到 k 个聚类，使得每个数据点到聚类中心的距离最小。

而实际上，这个问题往往是NP-hard的，以此有许多启发式的方法求解，从而避开局部最小值。

值得注意的是，k-means算法往往容易和k-nearest neighbor classifier（k-NN）算法混淆。

后者是有监督学习的分类（回归）算法，主要是用来判定数据点属于哪个类别中心的。

A simple example for k-means clusteringk-means算法有很多应用：•图像分割（Image Segmentation）•基因分割数据聚类分析（Clustering GeneSegementation Data）•新闻聚类分析（News Article Clustering）•语言聚类分析（Clustering Languages）•物种分析（Species Clustering）•异常检测（Anomaly Detection）•\cdots数学描述给定数据集 X=\{x^{(1)},x^{(2)},\cdots,x^{(n)}\} ，其中每个数据样本 x^{(i)}\in \mathbb{R}^d . k-mean算法旨在将 n 个数据点划分为 k(k\leq n) 个聚类集合\bm{S}=\{S_1,S_2,\cdots,S_k\} ，使得每个聚类集合中的样本点与聚类中心的距离平方和最小（WCSS, within-cluster sum of squares），i.e. 方差最小。

knn与kmeans算法的区别
knn kmeans
1.knn是分类算法
2.监督学习
3.给它的数据是有label的，是已经事先分类好了的，类别数不变。

1.kmeans是聚类算法
2.⾮监督学习
3.给它的数据是没有label，是没有事先分类好的，以“物以类聚”原理进⾏聚集成簇。

没有明显的前期训练过程。

有明显的前期训练过程。

K的含义：来了⼀个样本x，要给它分类，即求出它的类别，就从数据集中，在x附近找离它最近的K个数据点，这K个数据点，类别c占的个数最多，
就把x的类别设为c K的含义：K是⼈⼯固定好的数字，假设数据集合可以分为K个簇，由于是依靠⼈⼯定好，需要⼀点先验知识
以上是knn与kmeans的不同点，相同点为：相似点：都包含这样的过程，给定⼀个点，在数据集中找离它最近的点。

即⼆者都⽤到了NN(Nears Neighbor)算法，⼀般⽤KD树来实现NN。

k-means 算法一．算法简介k -means 算法，也被称为k -平均或k -均值，是一种得到最广泛使用的聚类算法。

它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。

这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。

二．划分聚类方法对数据集进行聚类时包括如下三个要点：（1）选定某种距离作为数据样本间的相似性度量k-means 聚类算法不适合处理离散型属性，对连续型属性比较适合。

因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。

下面我给大家具体介绍一下欧式距离。

假设给定的数据集 ，X 中的样本用d 个描述属性A 1,A 2…A d 来表示，并且d 个描述属性都是连续型属性。

数据样本x i =(x i1,x i2,…x id ), x j =(x j1,x j2,…x jd )其中，x i1,x i2,…x id 和x j1,x j2,…x jd 分别是样本x i 和x j 对应d 个描述属性A 1,A 2,…A d 的具体取值。

样本xi 和xj 之间的相似度通常用它们之间的距离d(x i ,x j )来表示，距离越小，样本x i 和x j 越相似，差异度越小；距离越大，样本x i 和x j 越不相似，差异度越大。

欧式距离公式如下：（2）选择评价聚类性能的准则函数k-means 聚类算法使用误差平方和准则函数来评价聚类性能。

给定数据集X ，其中只包含描述属性，不包含类别属性。

假设X 包含k 个聚类子集X 1,X 2,…X K ；{}|1,2,...,m X x m total ==(),i j d x x =各个聚类子集中的样本数量分别为n 1，n 2,…,n k ;各个聚类子集的均值代表点（也称聚类中心）分别为m 1，m 2,…,m k 。

机器学习知到章节测试答案智慧树2023年最新三亚学院第一章测试1.下面哪句话是正确的（）参考答案:增加模型的复杂度，总能减小训练样本误差2.评估模型之后，得出模型存在偏差，下列哪种方法可能解决这一问题（）参考答案:向模型中增加更多的特征3.以垃圾微信识别为例，Tom Mitchell的机器学习的定义中，任务T是什么？（）参考答案:T是识别4.如何在监督式学习中使用聚类算法（）？参考答案:在应用监督式学习算法之前，可以将其类别ID作为特征空间中的一个额外的特征;首先，可以创建聚类，然后分别在不同的集群上应用监督式学习算法5.想要训练一个ML模型，样本数量有100万个，特征维度是5000，面对如此大数据，如何有效地训练模型（）？参考答案:对训练集随机采样，在随机采样的数据上建立模型;使用PCA算法减少特征维度;尝试使用在线机器学习算法6.机器学习兴起于（）。

参考答案:1990年;1980年7.监督学习包括是（）。

参考答案:分类;回归8.机器学习可以对电子商务产品评价进行好评与差评分类。

（）参考答案:对9.机器学习必备知识包括数学基础、心理学基础、算法设计基础、商业模式基础。

（）参考答案:错10.机器学习是一门多学科交叉专业，涵盖____、____、近似理论知识和复杂算法知识，使用计算机作为工具并致力于真实实时的模拟人类学习方式，并将现有内容进行知识结构划分来有效提高学习效率。

参考答案:null第二章测试1.关于k-NN算法，以下哪个选项是正确的？参考答案:可用于分类和回归2.k-NN算法在测试时间而不是训练时间上进行了更多的计算。

参考答案:对3.假设算法是k最近邻算法，在下面的图像中，____将是k的最佳值。

参考答案:104.一个kNN分类器，该分类器在训练数据上获得100％的准确性。

而在客户端上部署此模型时，发现该模型根本不准确。

以下哪项可能出错了？注意：模型已成功部署，除了模型性能外，在客户端没有发现任何技术问题参考答案:可能是模型过拟合5.以下是针对k-NN算法给出的两条陈述，其中哪一条是真的？1、我们可以借助交叉验证来选择k的最优值2、欧氏距离对每个特征一视同仁参考答案:1和26.你给出了以下2条语句，发现在k-NN情况下哪个选项是正确的？1、如果k的值非常大，我们可以将其他类别的点包括到邻域中。

K-Means课前准备下载Anaconda软件。

课堂主题本次课讲解K-Means聚类算法与算法的改进与优化。

课堂目标学习本次课，我们能够达到如下目标：熟知K-Means算法的原理与步骤。

熟知K-Means++算法的原理与初始化方式。

熟知Mini Batch K-Means算法的原理与步骤。

能够选择最佳的值。

知识要点聚类之前我们接触的算法，都是监督学习，即训练数据是包含我们要预测的结果（训练数据中是含有样本的标签）。

我们对含有标签的训练集建立模型，从而能够对未知标签的样本进行预测。

与监督学习对应的，聚类属于无监督学习，即训练数据中是不含有标签的。

聚类的目的是根据样本数据内部的特征，将数据划分为若干个类别，每个类别就是一个簇。

结果为，使得同一个簇内的数据，相似度较大，而不同簇内的数据，相似度较小。

聚类也称为“无监督的分类”。

其样本的相似性是根据距离来度量的。

K-Means算法算法步骤K-Mean算法，即均值算法，是最常见的一种聚类算法。

顾名思义，该算法会将数据集分为个簇，每个簇使用簇内所有样本的均值来表示，我们将该均值称为“质心”。

具体步骤如下：1. 从样本中选择个点作为初始质心。

2. 计算每个样本到各个质心的距离，将样本划分到距离最近的质心所对应的簇中。

3. 计算每个簇内所有样本的均值，并使用该均值更新簇的质心。

4. 重复步骤2与3，直到达到以下条件之一结束：质心的位置变化小于指定的阈值。

达到最大迭代次数。

过程演示下图给出了使用K-Means算法聚类的过程。

优化目标KMeans算法的目标就是选择合适的质心，使得在每个簇内，样本距离质心的距离尽可能的小。

这样就可以保证簇内样本具有较高的相似性。

我们可以使用最小化簇内误差平方和（within-cluster sum-of-squares ）来作为优化算法的量化目标（目标函数），簇内误差平方和也称为簇惯性（inertia）。

：簇的数量。

：第个簇含有的样本数量。

kmeans聚类算法简单例题讲解K-Means聚类算法是目前机器学习中最简单的一种聚类算法，通常用于将样本分到最合适的组中，其从概念上来看就是将相似的样本聚在一起。

K-Means聚类算法假设类内点的方差最小，这一假设称为最小化类内平方和（Within-Cluster Sum of Squares）。

这一算法简单实用，且结果往往受到较少影响，被广泛应用于聚类任务中。

本文将以一个简单的例子来讲解K-Means聚类算法的原理和实现方法，帮助读者更好的理解和使用K-Means聚类算法。

假设有一组包含5个样本的数据，在二维空间（X轴和Y轴）映射出来的结果如下：（2，4）、（3，2）、（1，1）、（0，3）和（5，6）K-Means聚类算法的基本流程为：1.先，我们需要指定类别的个数K，这里我们可以指定K=2，代表将样本分为两类2.下来，我们需要随机初始化每个类的中心点，这里我们分别将中心点定为（2，4）和（5，6），表示类1的中心点为（2，4），类2的中心点为（5，6）3.下来，每个样本将会和每个类的中心点比较，以距离最小的为准，依次划分到类1或类2中4.后，我们计算每个类的平均值，将其作为新的类中心点，重复步骤3，直到类中心点不再发生改变在本次任务中，我们共经历了四次计算：第一次：将样本划分为两个类，第一类的中心点为（2，4），第二类的中心点为（5，6），按照最小距离原则，（2，4）和（3，2）划分到第一类，（1，1）和（0，3）划分到第二类，（5，6）表示第二类的中心点，但也属于第二类：第二次：计算每个类的平均值，第一类为（2.5，3），第二类为（2.5，4），将其作为新的类中心点：第三次：按照最小距离原则，（2，4）、（3，2）划分到第一类，（1，1）、（0，3）和（5，6）划分到第二类：第四次：计算每个类的平均值，第一类为（2.3，3.3），第二类为（2.5，4.5），将其作为新的类中心点：从上述例子可以看出，K-Means聚类算法是一种有效的方法，可以将样本数据划分至最合适的类别中。

kmeans算法的原理
K-means算法是一种典型的基于划分的聚类算法，其原理是将数据集划分为K个簇，使得每个数据点都属于最近的簇，并且簇的中心是所有数据点的平均值。

K-means算法的原理可以分为以下几个步骤：
1. 初始化：选择要将数据集分成K个簇，并随机选择K个数据点作为初始簇中心。

2. 分配：将每个数据点分配到距离其最近的簇中心，每个数据点只能属于一个簇。

3. 更新：根据分配的数据点更新簇中心点，这是通过计算属于每个簇的数据点的平均值来实现的。

4. 重复：重复步骤2和3，直到簇中心点不再发生变化，或者达到预定的迭代次数。

K-means算法利用相似性度量方法来衡量数据集中所有数据之间的关系，将关系比较密切的数据划分到一个集合中。

该算法具有运算速度快，执行过程简单的优点，在很多大数据处理领域得到了广泛的应用。

以上是K-means算法的基本原理，可以咨询数学专业人士或查阅算法类书籍了解更多信息。

k-means参数详解K-Means 是一种常见的聚类算法，用于将数据集划分成K 个不同的组（簇），其中每个数据点属于与其最近的簇的成员。

K-Means 算法的参数包括聚类数K，初始化方法，迭代次数等。

以下是一些常见的K-Means 参数及其详细解释：1. 聚类数K (n_clusters)：-说明：K-Means 算法需要预先指定聚类的数量K，即希望将数据分成的簇的个数。

-选择方法：通常通过领域知识、实际问题需求或通过尝试不同的K 值并使用评估指标（如轮廓系数）来确定。

2. 初始化方法(init)：-说明：K-Means 需要初始的聚类中心点，初始化方法决定了这些初始中心点的放置方式。

-选择方法：常见的初始化方法包括"k-means++"（默认值，智能地选择初始中心点以加速收敛）和"random"（从数据中随机选择初始中心点）。

3. 最大迭代次数(max_iter)：-说明：K-Means 算法是通过迭代优化来更新聚类中心的。

max_iter 参数定义了算法运行的最大迭代次数。

-调整方法：如果算法没有收敛，你可以尝试增加最大迭代次数。

4. 收敛阈值(tol)：-说明：当两次迭代之间的聚类中心的变化小于阈值tol 时，算法被认为已经收敛。

-调整方法：如果算法在较少的迭代后就收敛，可以适度增加tol 以提高效率。

5. 随机种子(random_state)：-说明：用于初始化算法的伪随机数生成器的种子。

指定相同的种子将使得多次运行具有相同的结果。

-调整方法：在调试和复现实验时，可以使用相同的随机种子。

这些参数通常是实现K-Means 算法时需要关注的主要参数。

在实际应用中，还可以根据数据的特性和问题的需求来选择合适的参数值。

通常，通过尝试不同的参数组合并使用评估指标（如轮廓系数）来评估聚类结果的质量。

一、K 近邻算法1.算法思想取未知样本的x 的k 个近邻,看这k 个近邻中多数属于哪一类，就把x 归于哪一类。

具体说就是在N 个已知的样本中,找出x 的k 个近邻。

设这N 个样本中，来自1w 类的样本有1N 个，来自2w 的样本有2N 个，...，来自c w 类的样本有c N 个，若c k k k ,,,21⋯分别是k 个近邻中属于c w w w ,,,21⋯类的样本数，则我们可以定义判别函数为：ci k x g i i ,,2,1,)(⋯==决策规则为：若i ij k x g max )(=，则决策j w x ∈2.程序代码%KNN 算法程序function error=knn(X,Y,K)%error 为分类错误率data=X;[M,N]=size(X);Y0=Y;[m0,n0]=size(Y);t=[123];%3类向量ch=randperm(M);%随机排列1—Merror=0;for i=1:10Y1=Y0;b=ch(1+(i-1)*M/10:i*M/10);X1=X(b,:);X(b,:)=[];Y1(b,:)=[];c=X;[m,n]=size(X1);%m=15,n=4[m1,n]=size(c);%m1=135,n=4for ii=1:mfor j=1:m1ss(j,:)=sum((X1(ii,:)-c(j,:)).^2);end[z1,z2]=sort(ss);%由小到大排序hh=hist(Y1(z2(1:K)),t);[w,best]=max(hh);yy(i,ii)=t(best);%保存修改的分类结果enderror=error+sum(Y0(b,:)~=yy(i,:)');X=data;enderror=error/M;%算法主程序：clcclear allload iris.mat%iris.mat中存放X为150*4的iris数据，Y为150*1的分类结果，以下均使用该数据n=0;for i=1:10error=knn(X,Y,1);n=n+error;endcorrect=1-n/103.程序运行结果做十折交叉验证得到：当K=1时，正确分类概率为：0.9587当K=3时，正确分类概率为：0.9613当K=5时，正确分类概率为：0.9640当K=7时，正确分类概率为：0.9653当K=10时，正确分类概率为：0.9667当K=30时，正确分类概率为：0.9480当K=60时，正确分类概率为：0.90274.结果分析从以上的结果我们可以看出当k较小时，随着k的增加，其正确分类的概率也逐渐增加；然而当k增加到一定的值时，即k取较大的值时，随着k的增加，其正确率并没有随之增加，反而大大降低了。