机器学习：K-Means算法

机器学习：K-Means算法

任务描述

以竞品分析为背景，通过数据的聚类，为汽车提供聚类分类。对于指定的车型，可以通过聚类分析找到其竞品车型。通过这道赛题，鼓励学习者利用车型数据，进行车型画像的分析，为产品的定位，竞品分析提供数据决策。

数据处理

Encoder：

由于数据集中还有很多非数值型数据，这样我们无法分析，文字型数据不能进行数学计算，所以我们采用词嵌入（One -hot）的方式，将非数值型数据转换成数值型数据。
词嵌入的方式：One hot ，Word2Vec，deep learning。

归一化：

由于有的数据对很大，有的数据很小，如果没有归一化，在kmeans算法计算distance的时候，数据很大的feature会掩盖掉比较小的feature，造成权重偏移。

      x
     
     
      ‾
     
    
    
     =
    
    
     
      
       x
      
      
       −
      
      
       min
      
      
       ⁡
      
      
       
        (
       
       
        x
       
       
        )
       
      
     
     
      
       max
      
      
       ⁡
      
      
       
        (
       
       
        x
       
       
        )
       
      
      
       −
      
      
       min
      
      
       ⁡
      
      
       
        (
       
       
        x
       
       
        )
       
      
     
    
   
   
    \overline{x}=\dfrac{x-\min \left( x\right) }{\max \left( x\right) -\min \left( x\right) }
   
  
 x=max(x)−min(x)x−min(x)​

Kmeans

前置内容

k值：分类数，也叫做簇（cluster）的个数。
质心：簇内所有点的均值。（对每一维度区平均即可）
距离计算公式：
本次试验采用欧式距离（需要归一化）。
欧式距离：
设点

    A
   
   
    （
   
   
    
     x
    
    
     1
    
   
   
    ,
   
   
    
     y
    
    
     1
    
   
   
    ）
   
   
    B
   
   
    (
   
   
    
     x
    
    
     2
    
   
   
    ,
   
   
    
     y
    
    
     2
    
   
   
    )
   
  
  
   A（x_1,y_1）B(x_2,y_2)
  
 
A（x1​,y1​）B(x2​,y2​)
 
  
   
    
     D
    
    
     =
    
    
     
      
       (
      
      
       
        x
       
       
        2
       
      
      
       −
      
      
       
        x
       
       
        1
       
      
      
       
        )
       
       
        2
       
      
      
       +
      
      
       
        
         (
        
        
         
          y
         
         
          1
         
        
        
         −
        
        
         
          y
         
         
          2
         
        
        
         )
        
       
       
        2
       
      
     
    
   
   
    D=\sqrt{( x_{2}-x_{1}) ^{2}+\left( y_{1}-y_{2}\right) ^{2}}
   
  
 D=(x2​−x1​)2+(y1​−y2​)2​

从公式我们发现，如果其中一个维度的数据太大，我们不做归一化，则另一个维度数据特征会被忽略。
除了欧式距离，一般常用的还有：
余弦距离：

     D
    
    
     =
    
    
     1
    
    
     −
    
    
     c
    
    
     o
    
    
     s
    
    
     (
    
    
     A
    
    
     ,
    
    
     B
    
    
     )
    
   
   
    D=1-cos(A,B)
   
  
 D=1−cos(A,B)

曼哈顿距离：

     D
    
    
     =
    
    
     ∣
    
    
     
      x
     
     
      1
     
    
    
     −
    
    
     
      x
     
     
      2
     
    
    
     ∣
    
    
     +
    
    
     ∣
    
    
     
      y
     
     
      1
     
    
    
     −
    
    
     
      y
     
     
      2
     
    
    
     ∣
    
   
   
    D=|x_1-x_2|+|y_1-y_2|
   
  
 D=∣x1​−x2​∣+∣y1​−y2​∣

优化目标：

     min
    
    
     ⁡
    
    
     
      ∑
     
     
      
       i
      
      
       =
      
      
       1
      
     
     
      k
     
    
    
     
      ∑
     
     
      
       x
      
      
       ∈
      
      
       C
      
      
       i
      
     
    
    
     d
    
    
     i
    
    
     s
    
    
     t
    
    
     
      
       (
      
      
       
        c
       
       
        i
       
      
      
       ,
      
      
       x
      
      
       )
      
     
     
      2
     
    
   
   
    \min \sum ^{k}_{i=1}\sum _{x\in Ci}dist\left( c_{i},x\right) ^{2}
   
  
 mini=1∑k​x∈Ci∑​dist(ci​,x)2

遵循原则：高内聚松耦合

聚类

基础概念

本次采用的模型属于无监督学习。

无监督学习：现实生活中常常会有这样的问题：缺乏足够的先验知识，因此难以人工标注类别或进行人工类别标注的成本太高。很自然地，我们希望计算机能代我们完成这些工作，或至少提供一些帮助。根据类别未知(没有被标记)的训练样本解决模式识别中的各种问题，称之为无监督学习。

有监督学习，半监督学习。

Kmeans：
优点：
简单易懂，效果好，可解释性强。
缺点：
对超参数的选取难以确定。
离群值对模型影响较大。

模型运作方式

1.随机初始化质心。
2.计算所有点到质心的距离，把每个点分配到最近的质心所在簇内。
3.对簇内的所有点求平均值，生成新的质心。
重复 2，3操作，值到质心不在发生变化。

模型改进方式：

mini-batch K-means
K-means ++