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

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算法

二分KMeans特点：解决K-Means算法对初始簇心比较敏感的问题，二分K-Means算法是一种弱化初 始质心的一种算法

二分Kmeans 具体思路步骤：

(1) 将所有样本数据放回到一个蔟队列中

(2) 队列中的一个蔟进行 k = 2 的KMeans算法聚类形成两个子蔟，将他们放回到蔟队列中

(3)重复这个步骤，直到中止条件达到(主要是聚簇数量)

选取队列蔟二划分的条件：

(1)选取蔟距离平方和SSE 最大的蔟进行二划分(优先)。

(2)选取样本较多的蔟进行二划分。

2.Kmeans++算法

K-Means++算法就是对K-Means随机初始化质心的方法的优化。K-Means++的对于初始化质心的优化策略也很简单，如下：

(1)从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1

(2)

(3)选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大

(4)重复2和3直到选择出k个聚类质心

(5)利用这k个质心来作为初始化质心去运行标准的K-Means算法

简单的来说， Kmeans++ 就是选择离已选中心点最远的点。