机器学习笔记之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值以及初始聚类质心，并合理处理数据中的异常值问题。