服务机构电子商务网站有哪些,有没有公司做农副产品网站的,wordpress xrea,网络运营主要做什么工作系列文章目录
第一章 Python 机器学习入门之线性回归 K-Means聚类算法 系列文章目录前言一、K-Means简介1、定义2、例子3、K-Means与KNN 二、 K-Means实现1、步骤2、优化2.1 初始化优化之K-Means2.2 距离优化之elkan K-Means 三、优缺点1、优点2、缺点 前言
学完K近邻算法2.2 距离优化之elkan K-Means 三、优缺点1、优点2、缺点 前言
学完K近邻算法让我们再来看看和它有一定相似程度的K-Means聚类算法
一、K-Means简介
1、定义
wiki定义 k-均值算法英文k-means clustering源于信号处理中的一种向量量化方法现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-均值聚类的目的是把n个点可以是样本的一次观察或一个实例划分到k个聚类中使得每个点都属于离他最近的均值此即聚类中心对应的聚类以之作为聚类的标准。
这里说下聚类和簇的概念使用上述算法会把训练中的数据划分成若干个组每个组就被称为簇而这种学习方式或者说分类过程就被称为聚类但是很多资料上往往也会把聚类视作簇就如上述定义一样。
2、例子
简单来说K聚类的核心点是找到K个中心点以此为中心辐射开来形成K个簇
举个例子有些大学在入学时会让学生填写一些个人作息和兴趣爱好来做宿舍分配其中就可以使用K-Means聚类算法假设要分配K个宿舍我们可以先随机出K个学生然后在此基础上分配剩下的学生剩下的学生找到与自己个人作息和兴趣爱好相近的K个学生之一最后我们就可以得到一个相对较好的宿舍环境熬夜打游戏的可以一起组团开黑早起学习的可以一起携手前去图书馆大家都获得了美好的未来。
3、K-Means与KNN
前言里提到K-Means和KNN有一定相似程度这是因为二者在运行过程中都用到了最近邻思想都是找到离某个点最近的点但是它们不能统一而论这是它们的区别点
KNN是有监督学习是有对应的类别输出的K-Means是无监督学习没有样本输出KNN是找离当前点最近的K个点K-Means是找离当前点最近的K个中心点之一
二、 K-Means实现
1、步骤 选取初始化的k个样本设为聚类中心aa1,a2,a3…ak; 对于数据集的每个数据点Xi计算它到k个聚类中心的距离这里通常采用我们在上一篇k近邻中提到的欧式距离来计算然后将它分到距离最小的聚类中心所对应的簇中 针对每个聚类中心aj,当有新的样本加入时重新计算它的质心中心点 重复上述2、3步直至达到终止条件
2、优化
2.1 初始化优化之K-Means
传统K-Means是随机选择中心点这样有很大概率会花费更多的时间因此在选择初始点上我们可以使用更好的方法那就是K-Means;
相比于传统K-MeansK-Means在选择新的初始点时都会参考之前选取得初始点因为我们知道最后得出的结果是K个簇我们希望每个簇之间的距离越远越好而这点就可以应用到初始点选择上我们在选择新的初始点希望找到离之前的初始点越远越好
步骤
随机选择一个初始点a1对于数据集中每一个点Xi计算它到之前每个聚类中心aj的距离D(xi)找到距离最大的那个但是这只适用于单个距离中心的情况当面对多个聚类中心我们使用概率的方式下式来找到最可能距离前j个聚类中心最远的点 重复第二步直至找到K个聚类中心
2.2 距离优化之elkan K-Means
传统K-Means中每次迭代都需要计算机所有样本到所有质心的位置这样运行时间过长elkan K-Means算法则是对这一步进行改进减少不必要的距离的计算它主要的使用的思想是利用两边之和大于等于第三边两边之差小于第三边的三角形的性质因此达到减少距离计算的目的。
对于一个样本点x和两个质心a1,a2;我们先计算出这两个质心的距离D(a1,a2)如果2D(a1,x)D(a1,a2)那么D(a2,x)D(a1,x)就可以不计算D(a2,x)减少一步计算距离对于一个样本点x和两个质心a1,a2我们可以得到D(a2,x)max(0,D(a1,x)-D(a1,a2))
第二条规律其实有点难懂我查阅了下资料大概是说利用两边之差小于第三边推导出来然后在此基础上来利用该公式能判断是否可以不用计算D(a2,x)
该方法可以一定程度上提升传统K-Means聚类算法的迭代速度但是如果样本的特征是稀疏的并具有缺失值由于有些距离无法计算则无法使用该算法。
三、优缺点
1、优点
简单易懂算法收敛速度快算法的可解释性强
2、缺点
k值的选取一般需要先验经验专家经验采用迭代的方法得到的结果只是局部最优由于需要计算质心到所有点的距离对噪音和异常点比较敏感如果各隐含类别的数据量严重失衡或者个各隐含类别的方差不同则聚类效果不佳
