K均值聚类及代码实现

KMeans聚类

在聚类算法中，最出名的应该就是k均值聚类(KMeans)了，几乎所有的数据挖掘/机器学习书籍都会介绍它，有些初学者还会将其与KNN等混淆。k均值是一种聚类算法，属于无监督学习的一种，而KNN是有监督学习/分类学习的一种。
聚类：顾名思义，就是讲某些相似的事物聚在一起，形成一个类。这里就涉及到几个概念
1.如何表示一个事物？通常我们会准备好一个数据集，里面是我们的数据，每一行代表的都是一个数据，每一列是一个数据的一种特征。比如经典的分类数据集 iris（鸢尾花数据），每一行代表的是每一朵花，每一朵花都有花萼长度，花萼宽度，花瓣长度，花瓣宽度 4个特征，即有4列特征。
2.如何度量事物间的距离？我们拿到每一个数据的特征值之后，需要根据实际情况来进行两种数据之间的计算，常用的方法是欧氏距离、马氏距离、余弦距离等。
3.按照什么样的过程进行聚类？这里就涉及到具体的算法了，目前聚类大致有几个比较流行的方法：基于划分、基于层次、基于密度、基于网络。这里的K均值就属于基于划分的方法，后续会继续写其余几种方法的代表算法。
4.如何能判断聚类过程结束呢？当每一种类别中的数据趋于稳定，即为完成聚类

KMeans过程

KMeans聚类过程

上图是截取别人blog中的图片(参考文献1)，这里讲的其实很清楚了。
上代码：

#!/usr/bin/python
# -*- coding:utf-8 -*-
"""
Author LiHao
Time 2018/11/26 9:21
"""
import os
import sys
import numpy as np
import scipy as sp
from sklearn.datasets import load_iris
# 欧式距离函数
from ml_learn.algorithm.distance import eculide
import matplotlib.pyplot as plt
def load_data():
    """
    导入iris标准数据集
    :return:
    """
    iris = load_iris()
    data = iris.data
    target = iris.target
    target_names = iris.target_names
    return data,target,target_names

class Group(object):
    """
    定义类簇的类 -- 后续也会使用
    """
    def __init__(self):
        self._name = ""
        self._no = None
        self._members = []
        self._center = None
    @property
    def no(self):
        return self._no
    @property
    def name(self):
        return self._name
    @name.setter
    def name(self,no):
        self._no = no
        self._name = "G"+str(self._no)
    @property
    def members(self):
        return self._members
    @members.setter
    def members(self,member):
        if member is None:
            raise TypeError("member is None,please set value")
        if isinstance(member,list):
            self.members.extend(member)
            return
        self._members.append(member)
    def clear_members(self):
        self._members = []
    @property
    def center(self):
        return self._center
    @center.setter
    def center(self,c):
        self._center = c

class KMeans(object):
    def __init__(self,k = 2):
        if (k <= 1) or (k is None):
            raise ValueError("k's num must not none and must > 1.")
        self._k = k
        # 类簇
        self._groups = self._make_groups(k)
        self._pre_mean_value = 0
        self._current_mean_value = 1

    def _make_groups(self,k):
        """
        生成类簇
        :param k:
        :return:
        """
        groups = []
        for i in range(k):
            g = Group()
            g.name = i+1
            groups.append(g)
        return groups

    def _random_x_index(self,xlen):
        indexes = np.random.randint(0,xlen,self._k).tolist()
        return indexes

    def _compute_mean_value(self):
        sum = 0
        for i in range(len(self._groups)):
            average = self._compute_members_mean(self._groups[i].members)
            self._groups[i].center = average
            sum += average
        return sum/(len(self._groups))

    def _compute_members_mean(self,members):
        np_members = np.array(members)
        average = np.average(np_members,axis=0)
        return average

    def _find_most_nearby_group(self,x):
        np_groups = np.array([group.center for group in self._groups])
        distances = eculide(x,np_groups)
        most_similarity_index = np.argmin(distances).squeeze()
        self._groups[most_similarity_index].members = x
        return most_similarity_index

    def _clear_groups_members(self):
        for group in self._groups:
            group.clear_members()

    def fit(self,X):
        rows,cols = X.shape
        # 1.首先选取k个点为初始聚类中心点
        init_indexes = self._random_x_index(rows)
        for i,index in enumerate(init_indexes):
            self._groups[i].center = X[index]
            self._groups[i].members = X[index]
        # 2.计算每个数据与聚类中心的距离，加入到最近那一个类
        while(True):
            for i in range(rows):
                #发现距离最近的group 并将数据加入至类簇中
                self._find_most_nearby_group(X[i])
            # 3.重新计算每个类簇的平均值
            # 计算各个类别的聚类中心并返回所有类簇的均值
            self._current_mean_value = self._compute_mean_value()
            epos = np.sum(self._current_mean_value-self._pre_mean_value,axis=0).squeeze()
            if epos <= 0.00001:
                break
            # 清除历史成员 并将计算得到的均值误差保存
            self._clear_groups_members()
            self._pre_mean_value = self._current_mean_value
            # 4.重复2-3的运算，直到每个类簇额均值不再发生变化
    def plot_example(self):
        figure = plt.figure()
        ax = figure.add_subplot(111)
        ax.set_title("KMeans Iris Example")
        plt.xlabel("first dim")
        plt.ylabel("third dim")
        legends = []
        cxs = []
        cys = []
        for i in range(len(self._groups)):
            group = self._groups[i]
            members = group.members
            x = [member[0] for member in members]
            y = [member[2] for member in members]
            ax.scatter(x,y,marker='o')
            cx = group.center[0]
            cy = group.center[2]
            cxs.append(cx)
            cys.append(cy)
            legends.append(group.name)
        plt.scatter(cxs, cys, marker='+', c='k')
        plt.legend(legends,loc="best")
        plt.show()
        
data,target,target_names = load_data()
kmeans = KMeans(k=3)
kmeans.fit(data)
kmeans.plot_example()

经过运行，可以得到类似下图的结果：选取的是iris数据集，展示的是第一维和第三维的二位平面图。iris真实数据是分为3类，每一类50个数据。
每次运行的结果可能不一样，因为我们选取的初始中心点是随机的，这样就会造成结果的不稳定性。因此，很多K均值的改进方法就会从初始点选取进行优化；还有的是优化了均值计算，变成了中位数计算（K_median算法）

示例

参考文献

1.各种聚类算法（原理+代码+对比分析）最全总结