K-Means ++ 算法
Kmeans算法的缺陷:
• 聚类中心的个数K 需要事先给定,但在实际中这个 K 值的选定是非常难以估计的,很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适
• Kmeans需要人为地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果。(可以使用Kmeans++算法来解决)
K-Means ++ 算法:
k-means++算法选择初始seeds的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。
1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
2. 对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3. 选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法
从上面的算法描述上可以看到,算法的关键是第3步,如何将D(x)反映到点被选择的概率上,一种算法如下:
1. 先从我们的数据库随机挑个随机点当“种子点”
2. 对于每个点,我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里,然后把这些距离加起来得到Sum(D(x))。
3. 然后,再取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在Sum(D(x))中的随机值Random,然后用Random -= D(x),直到其 =0,此时的点就是下一个“种子点”。
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法
可以看到算法的第三步选取新中心的方法,这样就能保证距离D(x)较大的点,会被选出来作为聚类中心了。至于为什么原因比较简单,如下图所示:
![](http://images2015.cnblogs.com/blog/966989/201606/966989-20160625180316906-283879404.png)
假设A、B、C、D的D(x)如上图所示,当算法取值Sum(D(x))*random时,该值会以较大的概率落入D(x)较大的区间内,所以对应的点会以较大的概率被选中作为新的聚类中心。
秒懂算法 | 基于K-Means算法的汽车行驶运动学片段的分类 汽车在行进过程中会产生连续的一组数据,包含加速度,速度等参数,汽车形式运动学片段是指是从一个怠速开始到下一个怠速开始之间的运动行程,通常包括一个怠速部分和一个行驶部分。而怠速指的是汽车停止运动,但发动机保持最低转速运转的连续过程。行驶部分通常包含加速、巡航和减速三种运动模式。
相关文章
- Java实现 蓝桥杯 算法训练 多阶乘计算
- Java实现 蓝桥杯VIP 算法训练 数列
- Java实现 蓝桥杯VIP 算法训练 ALGO-85进制转换
- Python聚类算法之基本K均值实例详解
- 大叔算法分享(7)最小二乘法
- 基于改进蚁狮AALO算法优化电网GIPFC研究【IEEE 30节点】(Matlab代码实现)
- 【图像处理】基于matlab萤火虫算法图像对比度增强
- 干货!机器学习中 5 种必知必会的回归算法!
- 基于决策树算法的病例类型诊断matlab仿真
- Python实现DE差分进化算法优化支持向量机回归模型(SVR算法)项目实战
- 一致性哈希算法——算法解决的核心问题是当slot数发生变化时,能够尽量少的移动数据
- 【python】面试常考数据结构算法
- 图像处理:均值滤波算法
- Keras之MLPR:利用MLPR算法(1to1+【Input(1)→8(relu)→O(mse)】)实现根据历史航空旅客数量数据集(时间序列数据)预测下月乘客数量问题
- 【最全最详细】常用十大排序算法
- 数据结构和算法 十二、红黑树
- 程序员内功:八大排序算法