K-means 算法 Kmeans++ 二分Kmeans

曾经终败给现在 2022-03-11 11:38 345阅读 0赞

### 文章目录 ###

*   *   *   *  1. K-means 算法原理（距离度量采用欧式距离）
             *   *  中止条件：
             *  2. Kmean算法推导
             *  3. kmeans的优缺点
             *   *  缺点：
                 *  优点：
             *  4. 二分Kmeans算法 K-means++
             *   *  Kmeans++ :
                 *  二分Kmeans算法

#### 1. K-means 算法原理（距离度量采用欧式距离） ####

1.  随机选取k个簇中心点
2.  遍历所有数据，将每个数据划分到**欧式距离**最近的中心点中
3.  计算每个聚类的**平均值**，并作为新的簇中心点
4.  重复2-3，直到某个**中止条件**

##### 中止条件： #####

*  簇中心变化率收敛
 *  足够多的迭代
 *  最小平方误差MSE，非凸，采用迭代逼近局部最优。

**注意**，若不是采用欧式距离，簇中心的更新方式也随之不同，比如采用**曼哈顿距**离（绝对值），则不采用平均值，采用**中值**。

#### 2. Kmean算法推导 ####

注意：使用不同的距离度量，簇中心 的跟新公式便不一样。推导如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Byb21pc2VqaWE_size_16_color_FFFFFF_t_70]

#### 3. kmeans的优缺点 ####

##### 缺点： #####

*  K值是用户给定的，且对聚类结果影响很大（一般交叉验证选取）。
 *  对初始的簇中心敏感（由此提出 [**二分K-means、Kmeans++**][K-means_Kmeans]进行改进）
 *  利群值对模型影响很大（如2，4，6，8，100；这种数据样本可采用**K中值算法**，即选取中间值作为更新簇）
 *  不适合发现大小差别很大的簇

##### 优点： #####

*  簇类似高斯分布时，效果会不错
 *  简单，容易理解

#### 4. 二分Kmeans算法 K-means++ ####

[**二分K-means、Kmeans++**][K-means_Kmeans]

##### Kmeans++ : #####

*  并不是随机给定簇中心点，而是先随机选取一个初始簇中心，然后选一个离**前k个簇中心较远的另一个点**成为下一个簇中心，具体为计算 每一个样本 x i x\_i xi，离k个簇中心的最短距离  d m i n i d\_\{min\}^i dmini，然后找出最大的 d m i n i d\_\{min\}^i dmini .

##### 二分Kmeans算法 #####

*  每次从队列中出来一个簇，分成两个字簇，再进队；循环至簇数等于K

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Byb21pc2VqaWE_size_16_color_FFFFFF_t_70]: /images/20220311/78005ad63a08494cad17143b75188df8.png
[K-means_Kmeans]: https://blog.csdn.net/loveliuzz/article/details/78783773