Kmeans聚类算法详解

简介: Kmeans聚类算法详解

1. 前言


作为无监督聚类算法中的代表——K均值聚类(Kmeans)算法,该算法的主要作用是将相似的样本自动归到一个类别中。所谓的监督算法,就是输入样本没有对应的输出或标签。聚类(clustering)试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个“簇(cluster)”,聚类既能作为一个单独过程,用于找寻数据内在的分布结构,也可作为分类等其他学习任务的前去过程。——《Machine Learning》


聚类算法也许是机器学习中“新算法”出现最多、最快的领域,一个重要的原因是聚类不存在客观标准,给定数据集总能从某个角度找到以往算法未覆盖的某种标准从而设计出新算法。Kmeans算法十分简单易懂而且非常有效,但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。众多的论文基于此都提出了各自行之有效的解决方案,新的改进算法仍然不断被提出,此类文章大家可以在Web Of Science中搜索。

尽管Kmeans算法在MATLAB、Python等语言的工具箱函数中都有自带的函数可供调用,但作为机器学习的研究者新来说要设计出新的算法,有时就得“定制”自己的Kmeans函数了。自己动手编写无疑也更加能理解算法的具体过程,接下来就让我们进入正题吧


2. Kmeans算法的原理与理解


Kmeans算法是最常用的聚类算法,主要思想是:在给定K值和K个初始类簇中心点的情况下,把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中,所有点分配完毕之后,根据一个类簇内的所有点重新计算该类簇的中心点(取平均值),然后再迭代的进行分配点和更新类簇中心点的步骤,直至类簇中心点的变化很小,或者达到指定的迭代次数。

2.1 基本原理


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

dis(Xi,Cj)=t=1m(XitCjt)2dis(Xi,Cj)=∑t=1m(Xit−Cjt)2

上式中,XiXi表示第i个对象1in1≤i≤n,CjCj表示第j个聚类中心的1jk1≤j≤kXitXit表示第i个对象的第t个属性,1tm1≤t≤mCjtCjt表示第j个聚类中心的第t个属性。

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

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

Ct=XiSlXi|Sl|Ct=∑Xi∈SlXi|Sl|

式中,ClCl表示第l个聚类的中心,1lk1≤l≤k|Sl||Sl|表示第l个类簇中对象的个数,XiXi表示第l个类簇中第i个对象,1i|Sl|1≤i≤|Sl|


2.2 算法流程


输入:样本集D={x1,x2,x3,...,xm}D={x1,x2,x3,...,xm};聚类簇数k.

过程:

1:从D中随机选择k个样本作为初始均值向量{μ1,μ2,μ3,...,μk}{μ1,μ2,μ3,...,μk}

2:repeat

3: 令Ci=(1ik)Ci=∅(1⩽i⩽k)

4: forj=1,2,...,mdo

5: 计算样本xjxj与各均值向量μi(1ik)μi(1⩽i⩽k)的距离:dji=xjμi2dji=‖xj−μi‖2;

6: 根据距离最近的均值向量确定xjxj的簇标记:λj=argmini{1,2,3,...,k}djiλj=argmini∈{1,2,3,...,k}dji

7: 将样本xjxj划入相应的簇:Cλj=Cλj{xj}Cλj=Cλj∪{xj};

8: end for

9: for i=1,2,...,k do

10: 计算新均值向量:μi=1|Ci|xCixμi′=1|Ci|∑x∈Cix;

11: ifμiμiμi′≠μithen

12: 将当前均值向量 μiμi更新为μiμi′

13: else

14: 保持当前均值不变

15: end if

16: end for

17:until 当前均值向量均未更新

输出:簇划分C={C1,C2,...,Ck}C={C1,C2,...,Ck}


以上算法流程引自周志华《机器学习》,从流程来看K-means算法计算步骤基本上可以概括为两个部分:(1)计算每一个对象到类簇中心的距离;(2)根据类簇内的对象计算新的簇类中心。


3. 编程实现


为了方便应用我们将其编写为一个M函数KMeans(),首先需要确定函数的输入输出。这里输入参数为:data,K,iniCentriods,iterations(其中data为输入的不带标号的数据集数据矩阵,大小为numOfDatanumOfAttributes,K为数据分的类簇数目,iniCentriods为自行指定的初始聚类中心矩阵,大小为KnumOfAttributes,iterations为算法迭代次数。)

输出参数为:Idx,centroids,DistanceIdx为返回的分类标号, centroids为每一类的中心,Distance为类内总距离)

根据前面2.2节中的算法流程编写Kmeans算法的MATLAB程序如下

matlab
%% 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


在以上代码中其最主要部分在于第18至58行,进行寻找最近中心和求取均值更新聚类中心点。值得注意的是,在聚类过程中可能会出现空类即代码第44行那样,为保证算法的继续运行,从数据集中随机选取一个点作为中心。


4. 聚类结果评价


为了验证编写的Kmeans函数的性能,这里对想用的UCI数据集Iris数据集进行聚类并计算聚类的准确率,Iris数据集可以在http://archive.ics.uci.edu/ml/index.php上下载得到。首先读取Iris数据集,自行指定初始聚类中心调用前面编写的KMeans函数进行聚类,然后计算聚类的准确率,其代码如下

matlab
clear 
data=load('Iris.txt');
data=data(:,2:end);
matrix=[5.9016,2.7484,4.3935,1.4339;6.8500,3.0737,5.7421,2.0711;5.0060,3.4280,1.4620,0.2460];
[Idx,C,distance]=KMeans(data,3,matrix,500);
Distance=sum(distance)
c1=Idx(1:50,1);c2=Idx(51:100,1);c3=Idx(101:150,1);
accuracy=(sum(c1==mode(Idx(1:50,1)))+sum(c2==mode(Idx(51:100,1)))+sum(c3==mode(Idx(101:150,1))))/150


为方便使用Iris数据集经过了一些整理,这里将最后一列的带字符串的标签Iris-setosa,Iris-versicolor,Iris-virginica分别用数字1,2,3代替并移到了第一列,所以第三行选取的是从第二列至最后一列的数据。第5行中的matrix是查阅论文得到的一个初始聚类中心,正好用来比对聚类结果。第6行则调用KMeans()函数进行聚类,得到聚类标号和类内距离。对每类的类内距离求和即得到总的距离Distance,如第7行。准确率的计算有点麻烦,因为不能直接用KMeans计算后得到的标号跟原数据集中的标号对比计算准确率,KMeans只需要也只能将那些“相似”的数据点聚集到一类中,而给这一类数据的标号却是可能跟原数据集不同的。

这里采用一个简单的方法,从原数据集的标签可以看出第1-50个数据点为一类(Iris-setosa),第51-100为一类(Iris-versicolor),第101-150为一类(Iris-virginica),因此只需确定每50个数据点中的聚类标号是不是一致。取它们之中数目最多的标号作为正确的个数,最终比上数据集的总数即为准确率。以上代码运行结果如下所示。



5. 类簇中心点的选取


KMeans算法本身思想比较简单,但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。最简单的确定初始类簇中心点的方法是随机产生数据大小范围内的K个点作为初始的簇类中心点。随机产生初始点并进行测试的程序代码如下


matlab
clear
data=load('Iris.txt');
data=data(:,2:end);
K=3;
%% 产生随机初始点
[numOfData,numOfAttr]=size(data);   % numOfData是数据个数,numOfAttr是数据维数
centroids=zeros(K,numOfAttr);       % 随机初始化,最终迭代到每一类的中心位置
maxAttr=zeros(numOfAttr);        % 每一维最大的数
minAttr=zeros(numOfAttr);        % 每一维最小的数
for i=1:numOfAttr
    maxAttr(i)=max(data(:,i));    % 每一维最大的数
    minAttr(i)=min(data(:,i));    % 每一维最小的数
    for j=1:K
        centroids(j,i)=maxAttr(i)+(minAttr(i)-maxAttr(i))*rand();  % 随机初始化,选取每一维[min max]中初始化
    end
end
[Idx,C,distance]=KMeans(data,K,centroids,500);% 调用KMeans
Distance=sum(distance)% 计算类内距离之和
%% 计算准确率
c1=Idx(1:50,1);c2=Idx(51:100,1);c3=Idx(101:150,1);
Accuracy=(sum(c1==mode(Idx(1:50,1)))+sum(c2==mode(Idx(51:100,1)))+sum(c3==mode(Idx(101:150,1))))/numOfData


可以多运行几次以上代码,可以看出由于初始点事随机选取的每次运行得到的结果有所差异。这也是基本Kmeans算法的一个缺点,随着众多改进算法的提出Kmeans算法的这一问题也得到改善,深入了解的朋友可以查阅相关论文。

相关文章
|
3月前
|
数据采集 机器学习/深度学习 算法
【优秀设计案例】基于K-Means聚类算法的球员数据聚类分析设计与实现
本文通过K-Means聚类算法对NBA球员数据进行聚类分析,旨在揭示球员间的相似性和差异性,为球队管理、战术决策和球员评估提供数据支持,并通过特征工程和结果可视化深入理解球员表现和潜力。
107 1
【优秀设计案例】基于K-Means聚类算法的球员数据聚类分析设计与实现
|
3月前
|
数据采集 算法 数据可视化
基于Python的k-means聚类分析算法的实现与应用,可以用在电商评论、招聘信息等各个领域的文本聚类及指标聚类,效果很好
本文介绍了基于Python实现的k-means聚类分析算法,并通过微博考研话题的数据清洗、聚类数量评估、聚类分析实现与结果可视化等步骤,展示了该算法在文本聚类领域的应用效果。
|
1月前
|
算法 数据挖掘
基于粒子群优化算法的图象聚类识别matlab仿真
该程序基于粒子群优化(PSO)算法实现图像聚类识别,能识别0~9的数字图片。在MATLAB2017B环境下运行,通过特征提取、PSO优化找到最佳聚类中心,提高识别准确性。PSO模拟鸟群捕食行为,通过粒子间的协作优化搜索过程。程序包括图片读取、特征提取、聚类分析及结果展示等步骤,实现了高效的图像识别。
|
3月前
|
数据采集 资源调度 算法
【数据挖掘】十大算法之K-Means K均值聚类算法
K-Means聚类算法的基本介绍,包括算法步骤、损失函数、优缺点分析以及如何优化和改进算法的方法,还提到了几种改进的K-Means算法,如K-Means++和ISODATA算法。
108 4
|
3月前
|
数据采集 自然语言处理 数据可视化
基于Python的社交媒体评论数据挖掘,使用LDA主题分析、文本聚类算法、情感分析实现
本文介绍了基于Python的社交媒体评论数据挖掘方法,使用LDA主题分析、文本聚类算法和情感分析技术,对数据进行深入分析和可视化,以揭示文本数据中的潜在主题、模式和情感倾向。
131 0
|
3月前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】聚类算法中的距离度量有哪些及公式表示?
聚类算法中常用的距离度量方法及其数学表达式,包括欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、余弦相似度等多种距离和相似度计算方式。
226 1
|
3月前
|
数据采集 算法 数据可视化
基于K-Means聚类算法对球员数据的聚类分析,可以自主寻找最优聚类数进行聚类
本文介绍了一个基于K-Means聚类算法的NBA球员数据分析项目,该项目通过采集和分析球员的得分、篮板、助攻等统计数据,使用轮廓系数法和拐点法确定最优聚类数,将球员分为不同群组,并提供了一个可视化界面以便直观比较不同群组的球员表现。
基于K-Means聚类算法对球员数据的聚类分析,可以自主寻找最优聚类数进行聚类
|
3月前
|
人工智能 算法 数据可视化
DBSCAN密度聚类算法(理论+图解+python代码)
DBSCAN密度聚类算法(理论+图解+python代码)
|
4月前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
3月前
|
算法 数据可视化 搜索推荐
基于python的k-means聚类分析算法,对文本、数据等进行聚类,有轮廓系数和手肘法检验
本文详细介绍了基于Python实现的k-means聚类分析算法,包括数据准备、预处理、标准化、聚类数目确定、聚类分析、降维可视化以及结果输出的完整流程,并应用该算法对文本数据进行聚类分析,展示了轮廓系数法和手肘法检验确定最佳聚类数目的方法。