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

简介: K-means聚类是聚类分析中比较基础的算法,属于典型的非监督学习算法。其定义为对未知标记的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据尽可能接近,类别间的数据相似度比较大。用于衡量距离的方法主要有曼哈顿距离、欧氏距离、切比雪夫距离,其中欧氏距离较为常用。

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

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

算法原理如下:

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

image

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

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

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

image

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

image

算法实现:

经典的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()
   }

image

image

以下是基于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)

image

image

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

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

相关文章
|
12天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】K-means算法与PCA算法之间有什么联系?
【5月更文挑战第15天】【机器学习】K-means算法与PCA算法之间有什么联系?
|
12天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】维度灾难问题会如何影响K-means算法?
【5月更文挑战第15天】【机器学习】维度灾难问题会如何影响K-means算法?
|
13天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】聚类算法中,如何判断数据是否被“充分”地聚类,以便算法产生有意义的结果?
【5月更文挑战第14天】【机器学习】聚类算法中,如何判断数据是否被“充分”地聚类,以便算法产生有意义的结果?
|
13天前
|
机器学习/深度学习 运维 算法
【机器学习】可以利用K-means算法找到数据中的离群值吗?
【5月更文挑战第14天】【机器学习】可以利用K-means算法找到数据中的离群值吗?
|
14天前
|
机器学习/深度学习 分布式计算 并行计算
【机器学习】怎样在非常大的数据集上执行K-means算法?
【5月更文挑战第13天】【机器学习】怎样在非常大的数据集上执行K-means算法?
|
14天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】列举几种情况,在这些情况下K-means算法难以取得较好效果
【5月更文挑战第13天】【机器学习】列举几种情况,在这些情况下K-means算法难以取得较好效果
|
14天前
|
机器学习/深度学习 传感器 算法
【机器学习】在聚类算法中,使用曼哈顿距离和使用欧式距离有什么区别?
【5月更文挑战第12天】【机器学习】在聚类算法中,使用曼哈顿距离和使用欧式距离有什么区别?
|
14天前
|
数据采集 机器学习/深度学习 人工智能
【机器学习】在使用K-means算法之前,如何预处理数据?
【5月更文挑战第12天】【机器学习】在使用K-means算法之前,如何预处理数据?
|
14天前
|
机器学习/深度学习 算法 数据可视化
【机器学习】比较分层聚类(Hierarchical Clustering)和K-means聚类算法
【5月更文挑战第12天】【机器学习】比较分层聚类(Hierarchical Clustering)和K-means聚类算法
|
14天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】在使用K-means聚类算法时,如何选择K的值?
【5月更文挑战第11天】【机器学习】在使用K-means聚类算法时,如何选择K的值?

热门文章

最新文章