如何制作自己的网站链接教程,天津网站建设价格,网站建设属于哪个行业分类,响应是网站怎么做k-means 和层次聚类都属于划分聚类#xff0c;实际中最常用的是k-means#xff0c;k-means效果不好的情况下才会采用其他聚类
K-means算法
K-means算法#xff0c;也称为K-平均或者K-均值#xff0c;是一种使用广泛的最基础的聚类算法
假设输入样本为TX1,X2,…,Xm;则算法…k-means 和层次聚类都属于划分聚类实际中最常用的是k-meansk-means效果不好的情况下才会采用其他聚类
K-means算法
K-means算法也称为K-平均或者K-均值是一种使用广泛的最基础的聚类算法
假设输入样本为TX1,X2,…,Xm;则算法步骤为使用欧几里得距离公式
Step1随机选择初始化的k个类别中心a1,a2,…ak;Step2对于每个样本Xi将其标记位距离类别中心aj最近的类别j更新每个类别的中心点aj为隶属该类别的所有样本的均值然后更新中心点重复上面两步操作直到达到某个中止条件
中止条件
迭代次数、最小平方误差MSE(样本到中心的距离平方和)、簇中心点变化率结果相同
算法执行过程图 K-means算法
记K个簇中心分别为 每个簇的样本数量为;
使用平方误差作为目标函数(使用欧几里得距离)公式为 要获取最优解也就是目标函数需要尽可能的小对J函数求偏导数可以得到簇中心点a更新的公式为
K-means中的问题
1、K-means算法在迭代的过程中使用所有点的均值作为新的质点(中心点)如果簇中存在异常点将导致均值偏差比较严重
比如一个簇中有2、4、6、8、100五个数据那么新的质点为24显然这个质点离绝大多数点都比较远在当前情况下使用中位数6可能比使用均值的想法更好使用中位数的聚类方式叫做K-Mediods聚类(K中值聚类)
2、K-means算法是初值敏感(K值的给定和K个初始簇中心点的选择)的选择不同的初始值可能导致不同的簇划分规则
为了避免这种敏感性导致的最终结果异常性可以采用初始化多套初始节点构造不同的分类规则然后选择最优的构造规则
K-means算法的初值敏感示意图 K-means算法优缺点
缺点
K值是用户给定的在进行数据处理前K值是未知的不同的K值得到的结果也不一样对初始簇中心点是敏感的不适合发现非凸形状的簇或者大小差别较大的簇特殊值(离群值)对模型的影响比较大
优点
理解容易聚类效果不错处理大数据集的时候该算法可以保证较好的伸缩性和高效率当簇近似高斯分布的时候效果非常不错
K-means案例
基于scikit包中的创建模拟数据的API创建聚类数据使用K-means算法对数据进行分类操作并获得聚类中心点以及总的样本簇中心点距离和值 二分K-Means
解决K-Means算法对初始簇心比较敏感的问题二分K-Means算法是一种弱化初始质心的一种算法具体思路步骤如下
将所有样本数据作为一个簇放到一个队列中。从队列中选择一个簇进行K-means算法划分划分为两个子簇并将子簇添加到队列中。循环迭代第二步操作直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)。队列中的簇就是最终的分类簇集合。
从队列中选择划分聚簇的规则一般有两种方式分别如下
对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种)选择SSE最大的聚簇进行划分操作(优选这种策略)。 选择样本数据量最多的簇进行划分操作。K-Means算法
解决K-Means算法对初始簇心比较敏感的问题K-Means算法和K-Means算法的区别主要在于初始的K个中心点的选择方面K-Means算法使用随机给定的方式K-Means算法采用下列步骤给定K个初始质点
STEP1从数据集中任选一个节点作为第一个聚类中心STEP2对数据集中的每个点x计算x到所有已有聚类中心点的距离和D(X)D(x)比较大的点作为下一个簇的中心。STEP3重复2和3直到k个聚类中心被选出来STEP4利用这k个初始的聚类中心来运行标准的k-means算法
缺点由于聚类中心点选择过程中的内在有序性在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)
K-Means||算法
解决K-Means算法缺点而产生的一种算法主要思路是改变每次遍历时候的取样规则并非按照K-Means算法每次遍历只获取一个样本而是每次获取K个样本重复该取样操作O(logn)次然后再将这些抽样出来的样本聚类出K个点最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明一般5次重复采用就可以保证一个比较好的聚簇中心点。
Canopy算法
Canopy算法属于一种“粗”聚类算法执行速度较快但精度较低算法执行步骤如下
给定样本列表以及先验值 和 从列表L中获取一个节点P计算P到所有聚簇中心点的距离(如果不存在聚簇中心那么此时点P形成一个新的聚簇)并选择出最小距离 如果距离D小于 表示该节点属于该聚簇添加到该聚簇列表中如果距离D小于 表示该节点不仅仅属于该聚簇还表示和当前聚簇中心点非常近所以将该聚簇的中心点设置为该簇中所有样本的中心点并将P从列表L中删除如果距离D大于那么节点P形成一个新的聚簇并将P从列表L中删除直到列表L中的元素数据不再有变化或者元素数量为0的时候结束循环操作
Canopy算法得到的最终结果的值聚簇之间是可能存在重叠的但是不会存在某个对象不属于任何聚簇的情况 Canopy算法过程图形说明 Canopy算法常用应用场景
由于K-Means算法存在初始聚簇中心点敏感的问题常用使用CanopyK-Means算法混合形式进行模型构建
先使用canopy算法进行“粗”聚类得到K个聚类中心点
K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点进行“细”聚类
优点
执行速度快(先进行了一次聚簇中心点选择的预处理)不需要给定K值应用场景多能够缓解K-Means算法对于初始聚类中心点敏感的问题
Mini Batch K-Means算法
Mini Batch K-Means算法是K-Means算法的一种优化变种采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间同时试图优化目标函数Mini Batch K-Means算法可以减少K-Means算法的收敛时间而且产生的结果效果只是略差于标准K-Means算法
算法步骤如下
首先抽取部分数据集使用K-Means算法构建出K个聚簇点的模型继续抽取训练数据集中的部分数据集样本数据并将其添加到模型中分配给距离最近的聚簇中心点更新聚簇的中心点值(每次更新都只用抽取出来的部分数据集)循环迭代第二步和第三步操作直到中心点稳定或者达到迭代次数停止计算操作
K-Means和Mini Batch K-Means算法比较案例
基于scikit包中的创建模拟数据的API创建聚类数据使用K-means算法和MiniBatch K-Means算法对数据进行分类操作比较这两种算法的聚类效果以及聚类的消耗时间长度 聚类算法的衡量指标
均一性类似正确率
一个簇中只包含一个类别的样本则满足均一性其实也可以认为就是正确率(每个聚簇中正确分类的样本数占该聚簇总样本数的比例和)
完整性类似召回率
同类别样本被归类到相同簇中则满足完整性每个聚簇中正确分类的样本数占该类型的总样本数比例的和。
V-measure均一性和完整性的加权平均 调整兰德系数(ARI)
Rand index(兰德指数)(RI)RI取值范围为[0,1]值越大意味着聚类结果与真实情况越吻合。 其中C表示实际类别信息K表示聚类结果a表示在C与K中都是同类别的元素对数(也就是行)b表示在C与K中都是不同类别的元素对数也就是列表示数据集中可以组成的对数即从样本中取两个. 调整兰德系数(ARIAdjusted Rnd Index)ARI取值范围[-1,1]值越大表示聚类结果和真实情况越吻合。从广义的角度来将ARI是衡量两个数据分布的吻合程度的。 E[RI]表示均值
调整互信息(AMI)
调整互信息(AMIAdjusted Mutual Information)类似ARI内部使用信息熵 S 表示整个数据集U 表示整个预测的数据集V 实际数据集y值C 表示原始的R 表示预测的。一个样本只属于一个簇所以 ;一个样本只能预测出一种结果所以 ,表示实际和预测是相同的个数.
聚类算法的衡量指标-轮廓系数
簇内不相似度计算样本i到同簇其它样本的平均距离为 ; 越小表示样本i越应该被聚类到该簇簇C中的所有样本的 的均值被称为簇C的簇不相似度。
簇间不相似度计算样本i到其它簇 的所有样本的平均距离 越大表示样本i越不属于其它簇。
轮廓系数 值越接近1表示样本i聚类越合理越接近-1表示样本i应该分类到另外的簇中近似为0表示样本i应该在边界上所有样本的 的均值被称为聚类结果的轮廓系数 层次聚类方法
层次聚类方法对给定的数据集进行层次的分解或者合并直到满足某种条件为止传统的层次聚类算法主要分为两大类算法
凝聚的层次聚类AGNES算法(AGglomerative NESting)—采用自底向上的策略。最初将每个对象作为一个簇然后这些簇根据某些准则被一步一步合并两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定聚类的合并过程反复进行直到所有的对象满足簇数目。
分裂的层次聚类DIANA算法(DIvisive ANALysis)—采用自顶向下的策略。首先将所有对象置于一个簇中然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离)直到达到某个终结条件(簇数目或者簇距离达到阈值)。
AGNES和DIANA算法优缺点
简单理解容易合并点/分裂点选择不太容易合并/分裂的操作不能进行撤销大数据集不太适合(数据量大到内存中放不下)执行效率较低O(t*n2)t为迭代次数n为样本点数
AGNES算法中簇间距离 最小距离(SL聚类) 两个聚簇中最近的两个样本之间的距离(single/word-linkage聚类法) 最终得到模型容易形成链式结构 最大距离(CL聚类) 两个聚簇中最远的两个样本的距离(complete-linkage聚类法) 如果存在异常值那么构建可能不太稳定 平均距离(AL聚类) 两个聚簇中样本间两两距离的平均值(average-linkage聚类法) 两个聚簇中样本间两两距离的中值(median-linkage聚类法) 层次聚类优化算法
BIRCH算法(平衡迭代削减聚类法)重要聚类特征使用3元组进行一个簇的相关信息通过构建满足分枝因子和簇直径限制的聚类特征树来求聚类聚类特征树其实是一个具有两个参数分枝因子和类直径的高度平衡树分枝因子规定了树的每个节点的子女的最多个数而类直径体现了对这一类点的距离范围非叶子节点为它子女的最大特征值聚类特征树的构建可以是动态过程的可以随时根据数据对模型进行更新操作。
优缺点
适合大规模数据集线性效率只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数。
CURE算法(使用代表点的聚类法)该算法先把每个数据点看成一类然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是取消了使用所有点或用中心点距离来表示一个类而是从每个类中抽取固定数量、分布较好的点作为此类的代表点并将这些代表点乘以一个适当的收缩因子使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景而且收缩因子的使用可以减少噪音对聚类的影响。
优缺点
能够处理非球形分布的应用场景。采用随机抽样和分区的方式可以提高算法的执行效率。
BRICH算法案例 密度聚类
密度聚类方法的指导思想: 只要样本点的密度大于某个阈值则将该样本添加到最近的簇中。
这类算法可以克服基于距离的算法只能发现凸聚类的缺点可以发现任意形状的聚类而且对噪声数据不敏感。
计算复杂度高计算量大。
常用算法DBSCAN、密度最大值算法
DBSCAN算法
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
一个比较有代表性的基于密度的聚类算法相比于基于划分的聚类方法和层次聚类方法DBSCAN算法将簇定义为密度相连的点的最大集合能够将足够高密度的区域划分为簇并且在具有噪声的空间数据商能够发现任意形状的簇。
DBSCAN算法的核心思想是用一个点的ε邻域内的邻居点数衡量该点所在空间的密度该算法可以找出形状不规则的cluster而且聚类的时候事先不需要给定cluster的数量。
基本概念
ε邻域(ε neighborhood也称为Eps)给定对象在半径ε内的区域。
密度(density)ε邻域中x的密度是一个整数值依赖于半径ε。
MinPts定义核心点时的阈值也简记为M。
核心点(core point)如果 p(x)M ,那么称 x 为 X 的核心点记由X中所有核心点构成的集合为Xc并记XncX\Xc表示由X中所有非核心点构成的集合。直白来讲核心点对应于稠密区域内部的点。
边界点(border point): 如果非核心点x的ε邻域中存在核心点那么认为x为X的边界点。由X中所有的边界点构成的集合为Xbd。边界点对应稠密区域边缘的点。
噪音点(noise point)集合中除了边界点和核心点之外的点都是噪音点所有噪音点组成的集合叫做Xnoi噪音点对应稀疏区域的点。
直接密度可达(directly density-reachable)给定一个对象集合X如果y是在x的ε邻域内而且x是一个核心对象可以说对象y从对象x出发是直接密度可达的。
密度可达(density-reachable)如果存在一个对象链p1,p2…pm,如果满足pi1是从pi直接密度可达的那么称p1是从p1密度可达的。
密度相连(density-connected)在集合X中如果存在一个对象o使得对象x和y是从o关于ε和m密度可达的那么对象x和y是关于ε和m密度相连的。
簇(cluster)一个基于密度的簇是最大的密度相连对象的集合C满足以下两个条件
Maximality若x属于C而且y是从x密度可达的那么y也属于C。Connectivity若x属于Cy也属于C则x和y是密度相连的。
算法流程
如果一个点x的ε邻域包含多余m个对象则创建一个x作为核心对象的新簇寻找并合并核心对象直接密度可达的对象没有新点可以更新簇的时候算法结束。
算法特征描述:
每个簇至少包含一个核心对象。非核心对象可以是簇的一部分构成簇的边缘。·包含过少对象的簇被认为是噪声。DBSCAN算法总结
优点
不需要事先给定cluster的数目可以发现任意形状的cluster能够找出数据中的噪音且对噪音不敏感算法只需要两个输入参数聚类结果几乎不依赖节点的遍历顺序
缺点
DBSCAN算法聚类效果依赖距离公式的选取最常用的距离公式为欧几里得距离。但是对于高维数据由于维数太多距离的度量已变得不是那么重要。DBSCAN算法不适合数据集中密度差异很小的情况。密度最大值聚类算法(MDCA)
MDCA(Maximum Density Clustering Application)算法基于密度的思想引入划分聚类中使用密度而不是初始点作为考察簇归属情况的依据能够自动确定簇数量并发现任意形状的簇另外MDCA一般不保留噪声因此也避免了阈值选择不当情况下造成的对象丢弃情况。
MDCA算法的基本思路是寻找最高密度的对象和它所在的稠密区域MDCA算法在原理上来讲和密度的定义没有关系采用任意一种密度定义公式均可一般情况下采用DBSCAN算法中的密度定义方式。
MDCA相关概念
最大密度点
有序序列: 根据所有对象与pmax的距离对数据重新排序:
密度阈值density0当节点的密度值大于密度阈值的时候认为该节点属于一个比较固定的簇在第一次构建基本簇的时候就将这些节点添加到对应簇中如果小于这个值的时候暂时认为该节点为噪声节点。
簇间距离对于两个簇C1和C2之间的距离采用两个簇中最近两个节点之间的距离作为簇间距离。 聚簇距离阈值dist0当两个簇的簇间距离小于给定阈值的时候这两个簇的结果数据会进行合并操作。 M值初始簇中最多数据样本个数。
算法流程
MDCA算法聚类过程步骤如下
将数据集划分为基本簇
对数据集X选取最大密度点Pmax形成以最大密度点为核心的新簇Ci按照距离排序计算出序列Spmax,对序列的前M个样本数据进行循环判断如果节点的密度大于等于density0那么将当前节点添加Ci中循环处理剩下的数据集X选择最大密度点Pmax并构建基本簇Ci1直到X中剩余的样本数据的密度均小于density0。
使用凝聚层次聚类的思想合并较近的基本簇得到最终的簇划分
在所有簇中选择距离最近的两个簇进行合并合并要求是簇间距小于等于dist0,如果所有簇中没有簇间距小于dist0的时候结束合并操作
处理剩余节点归入最近的簇。
最常用、最简单的方式是将剩余样本对象归入到最近的簇。
密度聚类算法案例 谱聚类
谱聚类是基于谱图理论基础上的一种聚类方法与传统的聚类方法相比具有在任意形状的样本空间上聚类并且收敛于全局最优解的优点。
通过对样本数据的拉普拉斯矩阵的特征向量进行聚类从而达到对样本数据进行聚类的目的其本质是将聚类问题转换为图的最优划分问题是一种点对聚类算法。
谱聚类算法将数据集中的每个对象看做图的顶点V将顶点间的相似度量化为相应顶点连接边E的权值w这样就构成了一个基于相似度的无向加权图G(V,E)于是聚类问题就转换为图的划分问题。基于图的最优划分规则就是子图内的相似度最大子图间的相似度最小。 谱聚类的构建
谱聚类的构建过程主要包含以下几个步骤
构建表示对象相似度的矩阵W。构建度矩阵D(对角矩阵)。构建拉普拉斯矩阵L。计算矩阵L的前k个特征值的特征向量(k个列向量)。将k个列向量组成矩阵U。对矩阵U中的n行数据利用K-means或其它经典聚类算法进行聚类得出最终结果。
应用场景及存在的问题
应用场景图形聚类、计算机视觉、非凸球形数据聚类等。
存在的问题
相似度矩阵的构建问题业界一般使用高斯相似函数或者k近邻来作为相似度量一般建议 使用k近邻的方式来计算相似度权值。聚类数目的给定。如何选择特征向量。如何提高谱聚类的执行效率。
谱聚类应用案例
