K近邻聚类算法

今天药忘吃喽~ 2022-04-05 04:20 220阅读 0赞

## 概述 ##

随机选择K个聚类中心，在每一次迭代中，先为每个点确定其最近的聚类中心，这一步称为集群分配(cluster assignment)，然后计算每个类中所有点的中心点，将该类的聚类中心移动到中心点，这一步称为中心移动(move centroid)，得到这k个聚类中心的新位置，进行下一次迭代，直到每个聚类中心点正确分布在每个类的中心。

算法的输入有两个参数：聚类中心的数量K和一系列训练集 X = \{ x 1 , x 2 , … , x m \} X=\\\{x^1,x^2,\\dots,x^m\\\} X=\{ x1,x2,…,xm\},聚类过程如图所示：

![94196164.jpg][]

伪代码如下：

*  随机初始化K个聚类中心 μ 1 , μ 2 , … , μ K \\mu \_1,\\mu\_2,\\dots ,\\mu\_K μ1,μ2,…,μK  
    
 *  重复此过程直到 μ 1 , μ 2 , … , μ K \\mu \_1,\\mu\_2,\\dots ,\\mu\_K μ1,μ2,…,μK不再改变 或者 到达最大迭代次数：
    
     *  for i=1:m //对训练集中的每个数据
        
         *   c i c^i ci=K个聚类中心中离i最近的一个中心 μ \\mu μ
     *  for k=1:K
        
         *   μ k \\mu\_k μk=所有划分到 μ k \\mu\_k μk的点的均值（对 μ k \\mu\_k μk进行更新）

## K近邻聚类与K近邻分类 ##

*  KNN聚类是非监督学习，KNN分类是监督学习
 *  KNN聚类是迭代的过程，KNN分类不需要迭代

## 关于随机初始化 ##

一个推荐的随机初始化的方法：  
  
随机选择K个训练集中的点 x 1 , x 2 , … , x K x\_1,x\_2,\\dots,x\_K x1,x2,…,xK,令他们为初始聚类中心 x 1 = μ 1 , x 2 = μ 2 , … , x K = μ K x\_1=\\mu\_1,x\_2=\\mu\_2,\\dots,x\_K=\\mu\_K x1=μ1,x2=μ2,…,xK=μK.

随机初始化的点会很大程度上影响到最终聚类的结果，如果初始化的不好，最终可能会陷入局部最优结果(local optima)，避免这种的方式是进行多次随机初始化和聚类（一般取50到1000次），分别计算distortion，取distortion最小的一次  
 d i s t o r t i o n = 1 m ∑ i = 1 m ∣ ∣ x i − c i ∣ ∣ 2 distortion=\\frac\{1\}\{m\}\\sum\_\{i=1\}^m ||x\_i - c\_i||^2 distortion=m1i=1∑m∣∣xi−ci∣∣2  
对于K比较小（2到10），进行多次随机初始化可能会很有用，但是对于K很大（如100），也许一次K聚类就能达到较好的效果。

## 关于选择聚类个数K ##

*  根据肘部法则(elbow method),将K/distortion函数画出来，图像会看上去像人的胳膊肘，选择肘部的地方所表示的K值会是很好的选择。  
    ![87152424.jpg][]
 *  根据业务需要，这是很多情况下的方法，在运行KNN聚类之前心里就有了想要分成多少类的需求。

[94196164.jpg]: /images/20220405/2ab95ab9909147298bcd325a2cb3f44f.png
[87152424.jpg]: /images/20220405/fe91641d8ff142b6aa079ef6e462a383.png