K-means聚类是聚类分析中比较基础的算法，属于典型的非监督学习算法。
其定义为对未知标记的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据尽可能接近，类别间的数据相似度比较大。用于衡量距离的方法主要有曼哈顿距离、欧氏距离、切比雪夫距离，其中欧氏距离较为常用。
算法原理如下：
1.创建K个点作为初始质心（通常是随机选择） 2.当任意一个点的簇分类结果发生改变时 2.1对数据的每一个点，计算每一个质心与该数据点的距离，将数据点分配到距其最近的簇 2.2对于每一个簇，计算簇中所有点的均值并将均值作为质心
停止条件为：所有的点类别划分都不再改变为止
K均值聚类算法原理简单易懂，聚类效果较好，但是其缺陷也较为明显：
1、对离群值比较敏感； 2、聚类个数的选择会影响最终聚类效果； 3、初始化聚类中心的选择会影响聚类效果。
以下是K-means聚类的伪代码：
算法实现：
经典的K-means均值聚类代码算法实现并不复杂，以下给出R语言实现过程：
代码语言：javascript复制## !/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算法源码实现：
代码语言：javascript复制#!/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值以及初始聚类质心，并合理处理数据中的异常值问题。
