聚类算法属于无监督的一种算法,不需要标签就可以进行处理0
K -means家族(K-means算法是聚类算法中最常用的)
给定一个有M个对象的数据集,构建一个具有k个簇(组)的模型,其中k<=M。满足以下条件:
每个簇至少包含一个对象
每个对象属于且仅属于一个簇
将满足上述条件的k个簇成为一个合理的聚类划分
基本思想:对于给定的类别数目k,首先给定初始划分,通过迭代改变样本和簇的隶属关系,使的 每次处理后得到的划分方式比上一次的好(总的数据集之间的距离和变小了),(K不是一次性就得到最好的,要不断迭代来进行改良)
历史渊源
虽然其思想能够追溯到1957年的Hugo Steinhaus,术语“k-均值”于1967年才被James MacQueen首次使用。标准算法则是在1957年被Stuart Lloyd作为一种脉冲码调制的技术所提出, 但直到1982年才被贝尔实验室公开出版。在1965年,E.W.Forgy发表了本质上相同的方法,所以这 一算法有时被称为Lloyd-Forgy方法。更高效的版本则被Hartigan and Wong提出(1975/1979)
介绍
K-Means(K均值)算法是无监督的聚类算法,算法简单,聚类效果好,即使是在巨大的数据集上也 非常容易部署实施。正因为如此,它在很多领域都得到的成功的应用,如市场划分、机器视觉、 地 质统计学、天文学和农业等。K-Means算法有大量的变体,包括初始化优化K-Means++以及大数据 应用背景下的k-means||和Mini Batch K-Means
通过不断求样本的均值来更新质心从而得到新的K簇,最终样本的均值更新完后就是质心更新的最终位置,K簇可能不会变但是质心的位置会达到最优(K均值停止迭代是在质心不能进行变化的时候)
算法流程
K-means算法,也称为K-平均或者K-均值,是一种使用广泛的最基础的聚类算法,一般作为掌握聚 类算法的第一个算法
假设输入样本为T=X1,X2,…,Xm;则算法步骤为(使用欧几里得距离公式):
选择初始化的k个类别中心(质心)a1,a2,…ak(a为质心,k为样本个数);
对于每个样本Xi,将其标记位距离类别中心aj最近的类别j(i为几个簇,j为某个样本)
更新每个类别的中心点aj为隶属该类别的所有样本的均值
重复上面两步操作,直到达到某个中止条件(1、质心位置不变化 2、循环到达最大迭代次数)
哪个质心距离某样本最近,某样本就属于那个质心的类别
终止条件
迭代次数、最小平方误差MSE、簇中心点变化率
K-Means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划 分为K个簇。处理形式:”让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大“。
如果用数学表达式表示,假设簇划分为(C1,C2,…Ck),则我们的目标是最小化平方误差E(得到的数值越小,数据处理的性能就越强):
其中 μi 是簇 Ci 的均值向量,有时也称为质心,表达式为:
K-means底层实现
处理前效果演示
质心位置为随机样本点