机器学习笔记之K-means聚类

K-means聚类是聚类分析中比较基础的算法，属于典型的非监督学习算法。

其定义为对未知标记的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据尽可能接近，类别间的数据相似度比较大。用于衡量距离的方法主要有曼哈顿距离、欧氏距离、切比雪夫距离，其中欧氏距离较为常用。

算法原理如下：

1.创建K个点作为初始质心（通常是随机选择）
2.当任意一个点的簇分类结果发生改变时
2.1对数据的每一个点，计算每一个质心与该数据点的距离，将数据点分配到距其最近的簇
2.2对于每一个簇，计算簇中所有点的均值并将均值作为质心

停止条件为：所有的点类别划分都不再改变为止

K均值聚类算法原理简单易懂，聚类效果较好，但是其缺陷也较为明显：

1、对离群值比较敏感；
2、聚类个数的选择会影响最终聚类效果；
3、初始化聚类中心的选择会影响聚类效果。

以下是K-means聚类的伪代码：

算法实现：

经典的K-means均值聚类代码算法实现并不复杂，以下给出R语言实现过程：

## !/user/bin/env RStudio 1.1.423
## -*- coding: utf-8 -*-
## K-means Model

library("dplyr")
library('magrittr')
library('ggplot2')

rm(list = ls())
gc()

数据输入、标准化：

Data_Input <- function(file_path = "D:/R/File/iris.csv",p = .75){
    data = read.csv(file_path,stringsAsFactors = FALSE,check.names = FALSE)
    names(data) <- c('sepal_length','sepal_width','petal_length','petal_width','class')
    data[,-ncol(data)] <- scale(data[,-ncol(data)])
    x = data[,1:(ncol(data)-2)];y =  data$class_c
    return(
        list(
            data = data,
            train_data = x,
            train_target = y
            )
        )
   }

欧式距离计算：

DistEclud <- function(vecA, vecB){
    diff = rbind(vecA,vecB)
    euclidean = dist(diff) %>% as.numeric()
    return (euclidean)
   }

随机质心选择：

RandCentre <- function(dataSet, k){  
    n = ncol(dataSet)
    Centres = matrix(nrow = k,ncol = n)
    for(j in 1:n){
        minJ = min(dataSet[,j])
        rangeJ = max(dataSet[,j]) - minJ
        Centres[,j] = (minJ + rangeJ * runif(k)) 
    }
    return (Centres)
}

K-means聚类构建：

Kmeans_Cluster <- function(dataSet,k){
    m = nrow(dataSet)
    ClusterAssment = rep(0,times = 2*m) %>% matrix(nrow = m,ncol = 2)  
    Centres = RandCentre(dataSet,k)
    ClusterChanged = TRUE
    while(ClusterChanged){
        ClusterChanged = FALSE
        for(i in 1:m){
            minDist = Inf
            minIndex = 0
            for(j in 1:k){
                distJI = DistEclud(Centres[j,],dataSet[i,])
                if (distJI < minDist){
                    minDist = distJI
                    minIndex = j
                }
            }
            if(ClusterAssment[i,1] != minIndex){
                  ClusterChanged = TRUE
                  ClusterAssment[i,] = c(minIndex,minDist^2)
            } 
        }
        for(cent in 1:k){
            index = grep(cent,ClusterAssment[,1])
            ptsInClust = dataSet[index,]
            Centres[cent,] = apply(ptsInClust,2,mean)
        }
    print(Centres)
    }
    return (
        list(
            Centres = Centres,
            ClusterAssment = ClusterAssment
            )
        )
}

聚类模型执行与结果输出：

Show_Result <- function(k){
    data_source = Data_Input()
    dataSet = data_source$train_data
    y = data_source$train_target
    result = Kmeans_Cluster(dataSet,k)
    centroids = result$Centres
    clusterAssment = result$ClusterAssment
    ggplot() +
    geom_point(data = NULL,aes(x = dataSet[,1],y = dataSet[,2],fill = factor(clusterAssment[,1])),shape = 21,colour = 'white',size = 4) +
    geom_point(data = NULL,aes(x= centroids[,1],y = centroids[,2]),fill = 'Red',size = 10,shape = 23) +
    scale_fill_brewer(palette = 'Set1') +
    guides(fill=guide_legend(title=NULL)) +
    theme_void()
   }

以下是基于Python的K-means算法源码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy  as np
import pandas as pd
from sklearn import preprocessing
from sklearn.metrics import confusion_matrix
from matplotlib import pyplot as plt

数据输入与标准化：

def DataInput():
    data = pd.read_csv("D:/Python/File/iris.csv")
    data.columns = ['sepal_length','sepal_width','petal_length','petal_width','class']
    print(data.shape,'\n',data.head())
    data.iloc[:,0:-1] = preprocessing.scale(data.iloc[:,0:-1])
    data['class_c'] =  pd.factorize(data['class'])[0]
    return  data.iloc[:,0:-2],data.iloc[:,-1]

欧式距离计算：

def DistEclud(vecA, vecB)
    return np.sqrt(np.sum(np.power(vecA - vecB, 2)))
#随机质心选择函数：

def RandCentre(dataSet, k):     
    n = dataSet.shape[1]
    Centres = np.mat(np.zeros((k,n)))
    for j in range(n):
        minJ = np.min(dataSet.iloc[:,j])
        rangeJ = np.float(np.max(dataSet.iloc[:,j]) - minJ)
        Centres[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1)) 
    return Centres

聚类算法源码：

def kMeans(dataSet,k): 
    m = dataSet.shape[0]
    ClusterAssment = np.mat(np.zeros((m,2)))
    Centres = RandCentre(dataSet,k)
    ClusterChanged = True
    while ClusterChanged:
        ClusterChanged = False
            for i in range(m): 
            minDist = np.inf;minIndex = -1
            for j in range(k):
                distJI = DistEclud(Centres[j,:],dataSet.iloc[i,:].values)
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if ClusterAssment[i,0] != minIndex:
                ClusterChanged = True
                ClusterAssment[i,:] = minIndex,minDist**2
        print(Centres)
        for cent in range(k):
            index = np.nonzero(ClusterAssment[:,0].A== cent)[0].tolist()
            ptsInClust = dataSet.iloc[index,:]
            Centres[cent,:] = np.mean(ptsInClust,axis=0).values
            return Centres,ClusterAssment

聚类算法执行与结果输出：

def show(k): 
    dataSet,y = DataInput()
    centroids, clusterAssment = kMeans(dataSet,k)
    m,n = dataSet.shape  
    mark  = ['or', 'ob', 'og']
    for i in range(m):  
        markIndex = np.int(clusterAssment[i,0])  
        plt.plot(dataSet.iloc[i,0], dataSet.iloc[i,1],mark[markIndex])  
    for i in range(k):  
        plt.plot(centroids[i,0], centroids[i,1], mark[i], markersize = 12)  
    plt.show()
        return centroids,clusterAssment

show(k=3)

以上是原生k-means算法的简单实现，其中最为核心的聚类算法模块几乎高度还原了伪代码的核心思想，但是鉴于聚类分析中异常值、K值选择以及初始聚类中心的选择都会影响最终的聚类效果，所以在使用K-means聚类算法时要选择合适的K值以及初始聚类质心，并合理处理数据中的异常值问题。

原文发布时间为：2018-06-30
本文作者：杜雨
本文来自云栖社区合作伙伴“ 数据小魔方”，了解相关信息可以关注“ 数据小魔方”。