算法过程:
- 随机选取K个种子点
- 求所有点到种子点的距离,将点纳入距离最近的种子点群
- 所有点均被纳入群内后,将种子点移动到种子群中心
- 重复上述2、3过程,直至种子点没有移动
优缺点:
- 优点:容易实现
- 缺点:可能收敛到局部最小值,在大规模数据上收敛较慢
思考:
- k值如何确定?
- ISODATA算法针对这个问题进行了改进:当属于某个类别的样本数过少时把这个类别去除,当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别(类的自动合并和分裂)
- Elbow Method:通过绘制K-means代价函数与聚类数目K的关系图,选取直线拐点处的K值作为最佳的聚类中心数目
- 从实际问题出发,人工指定比较合理的K值,通过多次随机初始化聚类中心选取比较满意的结果
- 初始随机种子如何确定
- K-means++选取K个聚类中心的思想:假设已经选取了n个初始聚类中心(0<n<K),则在选取第n+1个聚类中心时:距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心(n=1)时同样通过随机的方法(聚类中心互相离得越远越好)
- 度量方式
- 传统K-means采用欧式距离进行样本间的相似度度量,显然并不是所有的数据集都适用于这种度量方式。kernel k-means参照支持向量机中核函数的思想,将所有样本映射到另外一个特征空间中再进行聚类,就有可能改善聚类效果
代码:
地址:https://github.com/AaronX121/Clustering,使用方式非常简单,目前支持三种形式的输入,分别对应着上面的三种算法:
- [centroid, result] = Clustering(data, ‘kmeans’, k , iteration);
- [centroid, result] = Clustering(data, ‘kmeans++’, k , iteration);
- [centroid, result] = Clustering(data, ‘isodata’, desired_k , iteration, minimum_n, maximum_variance, minimum_d);
其中的输入data是一个矩阵,每一行代表数据集中的一个样本。其他输入的意义与上面的算法描述中一一对应。输出的centroid是聚类中心的位置,result是每个样本所对应的类别索引。
应用:
k-means不仅局限于坐标点的计算,现实世界里的物体属性只要能抽象成向量,都可以用k-means来归类
上述论述摘自:http://www.cnblogs.com/yixuan-xu/p/6272208.html