K-Means K均值聚类算法

k均值聚类将样本集合划分为k个类，每个样本到其所属类的中心的距离最小。

其大致算法流程如下：

• 随机选择k个样本点作为k个类的初始聚类中心；
• 将每个样本分配到距离最近的中心的类中；
• 按照每个类内样本点的均值计算新的中心；
• 重复这一过程，停止条件为类收敛，即类中心不在发生变化。

算法需要事先决定分类数k，样本距离计算方式，类中心计算方式等。k均值聚类可能会局部收敛，不能保证全局最优，且初始中心点的选择会影响最终聚类结果。

前期准备和数据集的读入，使用鸢尾花数据集，分成3类。

import numpy as np
import random
from sklearn.datasets import load_iris

dataSet = load_iris().data
size = dataSet.shape
k = 3

归一化，防止某一特征主宰距离度量。

#归一化
mx = np.max(dataSet,axis=0)
mn = np.min(dataSet,axis=0)
dataSet = (dataSet - mn) / (mx - mn)

随机选择k个样本点作为初始聚类中心。

#随机选择k个样本点作为初始聚类中心
ran = np.arange(size[0])
ran = np.random.choice(ran, size=k, replace=False)
center = dataSet[ran[:]].copy()
categories = []
for i in range(k):
    categories.append([center[i],np.zeros((1,size[1]))])

对样本进行聚类，将每个样本分配到与其最近的中心的类中。距离衡量采用欧氏距离。

while True:
    #将每个样本加入到其最近的中心的类中
    for sample in dataSet:
        distance = []
        for i in range(k):
            c = categories[i]
            dis = np.linalg.norm(sample - c[0])
            distance.append((i,dis))
        distance.sort(key=lambda x: x[1])
        nearest = distance[0][0]
        categories[nearest][1] = np.row_stack((categories[nearest][1], sample))

由聚类结果计算新的类中心，采用类中所有样本的均值作为新的中心。

    #计算新的类中心
    for i in range(k):
        categories[i][1] = categories[i][1][1:]
        categories[i][0] = np.mean(categories[i][1], axis=0)

停止条件的判断，判断类中心较上一轮是否发生改变。

    #判断停止条件：类中心收敛
    for i in range(k):
        if not (categories[i][0] == center[i]).all():
            break
    else:
        break

若继续下一轮迭代，则保存该轮中心并重置类内样本点。

    #保存当前类中心，重置类内样本点
    for i in range(k):
        center[i] = categories[i][0]
        categories[i][1] = np.zeros((1,size[1]))

显示结果。

#显示类内样本点个数
for i in categories:
    print(i[1].shape[0])

48
52
50

结果出现了部分误差，但总体还是不错的。