经典聚类算法Kmeans的基本原理及实现-CDA数据分析师官网

经典聚类算法Kmeans的基本原理及实现

2020-07-24

Kmeans算法，又叫做K均值聚类算法，可以说是无监督聚类算法中最具代表性，最经典的聚类算法了，这一算法的主要作用是将相似的样本自动归到一个类别中。小编特意整理了这一经典聚类算法的基本原理供大家参考，希望对大家有所帮助。

一、首先来看一下Kmeans算法的效果

#通过简单的例子来直接查看K均值聚类的效果
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline

#聚类前
X = np.random.rand(100,2)
plt.scatter(X[:,0],X[:,1], marker='o')

#聚类后
kmeans = KMeans(n_clusters=4).fit(X)
label_pred = kmeans.labels_
plt.scatter(X[:,0],X[:,1],c=label_pred)
plt.show()

二、Kmeans算法基本原理

假定给定数据样本X，包含了n个对象

其中每个对象都具有m个维度的属性。Kmeans算法的目标是将n个对象依据对象间的相似性聚集到指定的k个类簇中，每个对象属于且仅属于一个其到类簇中心距离最小的类簇中。对于Kmeans，首先需要初始化k个聚类中心{C1.C2.C3....,Ck},1<k≤n,然后通过计算每一个对象到每一个聚类中心的欧式距离，如下式所示

依次比较每一个对象到每一个聚类中心的距离，将对象分配到距离最近的聚类中心的类簇中，得到k个类簇{S1.S2.S3....,Sk}

Kmeans算法用中心定义了类簇的原型，类簇中心就是类簇内所有对象在各个维度的均值，其计算公式如下

代码实现

Kmeans算法
% 输入：
% data 输入的不带分类标号的数据
% K 数据一共分多少类
% iniCentriods 自行指定初始聚类中心
% iterations 迭代次数

% 输出：
% Idx 返回的分类标号
% centroids 每一类的中心
% Distance 类内总距离

 
function [Idx,centroids,Distance]=KMeans(data,K,iniCentriods,iterations)
[numOfData,numOfAttr]=size(data); % numOfData是数据个数，numOfAttr是数据维数
centroids=iniCentriods;
%% 迭代
for iter=1:iterations
    pre_centroids=centroids;% 上一次求得的中心位置
    
    tags=zeros(numOfData,K);
    %% 寻找最近中心，更新中心
    for i=1:numOfData
        D=zeros(1,K);% 每个数据点与每个聚类中心的标准差
        Dist=D;
        
        % 计算每个点到每个中心点的标准差
        for j=1:K
            Dist(j)=norm(data(i,:)-centroids(j,:),2);
        end
        
        [minDistance,index]=min(Dist);% 寻找距离最小的类别索引
        tags(i,index)=1;% 标记最小距离所处的位置（类别）
    end
    
    
    %% 取均值更新聚类中心点
    for i=1:K
        if sum(tags(:,i))~=0
            % 未出现空类，计算均值作为下一聚类中心
            for j=1:numOfAttr
                centroids(i,j)=sum(tags(:,i).*data(:,j))/sum(tags(:,i));
            end
        else % 如果出现空类，从数据集中随机选中一个点作为中心
            randidx = randperm(size(data, 1));
            centroids(i,:) = data(randidx(1),:);
            tags(randidx,:)=0;
            tags(randidx,i)=1;
        end
    end
    
   
    if sum(norm(pre_centroids-centroids,2))<0.001  % 不断迭代直到位置不再变化
        break;
    end
    
    
end

%% 计算输出结果
Distance=zeros(numOfData,1);
Idx=zeros(numOfData,1);
for i=1:numOfData
    D=zeros(1,K);% 每个数据点与每个聚类中心的标准差
    Dist=D;
    % 计算每个点到每个中心点的标准差
    for j=1:K
        Dist(j)=norm(data(i,:)-centroids(j,:),2);
    end
    
    [distance,idx]=min(Dist);% 寻找距离最小的类别索引
    distance=Dist(idx);
    
    Distance(i)=distance;
    Idx(i)=idx;
end
Distance=sum(Distance,1);% 计算类内总距离
end

二、Kmeans的优化算法

1.二分K-means算法