【统计学习】K-Means

$J_e=\sum_i^c\sum_{x\in D_i }||x-m_i||^2\\m_i=\frac{1}{n_i}\sum_{x\in D_i}x$

该公式假设类别分布是球形的。否则可能和主观感觉不太一样

算法条件

K-Means算法的特点是类别的个数是人为给定的，如果让机器自己去找类别的个数，我们有AP聚类算法，
K-Means的一个重要的假设是：数据之间的相似度可以使用欧氏距离度量，如果不能使用欧氏距离度量，要先把数据转换到能用欧氏距离度量，这一点很重要。

算法简述

K-Means的著名解释

有四个牧师(指定类别个数-s1)去郊区布道，一开始牧师们随意选了几个布道点(随机初始化-s2)，并且把这几个布道点的情况公告给了郊区所有的居民，于是每个居民到离自己家最近的布道点去听课(计算欧氏距离-s3)。
听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的居民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置(布道点改变，向所有类别中心移动-s4)。
牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个居民又去了离自己最近的布道点(第二轮迭代)……
就这样，牧师每个礼拜更新自己的位置，居民根据自己的情况选择布道点，最终稳定了下来。

随机生成的类别(s1)

随机生成k个点，并对每个点进行分类(s2)

伪代码

function K-Means(输入数据，中心点个数K)
获取输入数据的维度Dim和个数N
随机生成K个Dim维的点
while(算法未收敛)
    对N个点：计算每个点属于哪一类。
    对于K个中心点：
        1，找出所有属于自己这一类的所有数据点
        2，把自己的坐标修改为这些数据点的中心点坐标
end
输出结果：
end

算法实现和优化

作用于数据压缩

比如图片，每一个点都可以视作是一个三维向量（点？）（RGB三通道图片），那么，使用K-Means算法对这些点进行聚类，我们就很容易得到几个中心点和几类，把同一类的数据点（像素点）用中心点表示就可以得到压缩后的图片，以上分别是把3通道×每通道8bit=24bit的像素点压缩为1bit，2bit，3bit和4bit的效果，可以看到，虽然信息损失了6倍，但是对画质的影响没有想象的大。