技术人生,  机器学习

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])

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

A WindRunner. VoyagingOne

留言

您的电子邮箱地址不会被公开。 必填项已用*标注