K-均值聚类分析

1、1 案例题目：选取一组点（三维或二维），在空间内绘制出来，之后根据 K 均值聚类， 把这组点分为 n 类。此例中选取的三维空间内的点由均值分别为(0,0,0),(4,4,4),(-4,4,-4) ，300000300协方差分别为 030，030， 0 30 的 150 个由 mvnrnd 函数随机003003003生成。2 原理运用与解析：2.1 聚类分析的基本思想聚类分析是根据 “物以类聚” 的道理， 对样本或指标进行分类的一种多元统 计分析方法， 它们讨论的对象是大量的样本， 要求能合理地按各自的特性进行合 理的分类。 对于所选定的属性或特征， 每组内的模式都是相似的， 而与其他组的 模式

2、差别大。一类主要方法是根据各个待分类模式的属性或特征相似程度进行分 类，相似的归为一类， 由此将待分类的模式集分成若干个互不重叠的子集， 另一 类主要方法是定义适当的准则函数运用有关的数学工具进行分类。 由于在分类中 不需要用训练样本进行学习和训练，故此类方法称为无监督分类。聚类的目的是使得不同类别的个体之间的差别尽可能的大， 而同类别的个体 之间的差别尽可能的小。 聚类又被称为非监督分类， 因为和分类学习相比， 分类 学习的对象或例子有类别标记， 而要聚类的例子没有标记， 需要由聚类分析算法 来自动确定， 即把所有样本作为未知样本进行聚类。 因此，分类问题和聚类问题 根本不同点为：在分类问题

3、中，知道训练样本例的分类属性值， 而在聚类问题中， 需要在训练样例中找到这个分类属性值。聚类分析的基本思想是认为研究的样本或变量之间存在着程度不同的相似 性（亲疏关系）。研究样本或变量的亲疏程度的数量指标有两种：一种叫相似系 数，性质越接近的样本或变量， 它们的相似系数越接近 1 或-1 ，而彼此无关的变 量或样本它们的相似系数越接近 0，相似的为一类，不相似的为不同类。另一种 叫距离，它是将每一个样本看做 p维空间的一个点， 并用某种度量测量点与点之 间的距离，距离较近的归为一类，距离较远的点应属于不同的类。2.2 动态聚类法思想动态聚类方法、亦称逐步聚类法 .一类聚类法.属于大样本聚类法。

4、 具体作法 是: 先粗略地进行预分类，然后再逐步调整，直到把类分得比较合理为止。这种 分类方法较之系统聚类法， 具有计算量较小、 占用计算机存贮单元少、 方法简单 等优点，所以更适用于大样本的聚类分析， 是一种普遍被采用的方法。 这种方法 具有以下三个要素：(1) 选定某种距离度量作为样本间的相似性度量；(2) 确定某种可以评价聚类结果质量的准则函数；(3) 给定某个初始分类， 然后用迭代算法找出使得准则函数取极值的最好聚类结 果。动态聚类法在计算迭代过程中， 类心会随着迭代次数进行修正和改变。 动态 聚类法的基本步骤：(1) 选取初始聚类中心及有关参数，进行初始聚类。(2) 计算模式和聚类的

5、距离，调整模式的类别。(3) 计算各聚类的参数，删除，合并或分裂一些聚类。(4) 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心，使准 则函数取极值或设定的参数达到设计要求时停止。2.3K- 均值聚类算法的思想K-均值算法是一种基于划分的聚类算法，它通过不断的迭代过程来进行聚类，当算法收敛到一个结束条件时就终止迭代过程，输出聚类结果。由于其算法思想简便，又容易 实现，因此 K 一均值算法己成为一种目前最常用的聚类算法之一。K-均值算法解决的是将含有 n个数据点(实体)的集合 X x1, x2 ,., xn 划分 为 k 个类Cj 的问题，其中 j 1,2,., k ，算法首先随机

6、选取 k 个数据点作为 k 个 类的初始类中心，集合中每个数据点被划分到与其距离最近的类中心所在的类中， 形成了 k 个聚类的初始分布。 对分配完的每一个类计算新的类中心， 然后继续进 行数据分配的过程， 这样迭代若干次之后， 若类中心不再发生变化， 则说明数据 对象全部分配到自己所在的类中， 证明函数收敛。 在每一次的迭代过程中都要对 全体数据点的分配进行调整， 然后重新计算类中心， 进入下一次迭代过程， 若在 某一次迭代过程中， 所有数据点的位置没有变化， 相应的类中心也没有变化， 此 时标志着聚类准则函数已经收敛， 算法结束。 通常采用的目标函数形式为平方误 差准则函数：KExi ci

7、2i 1 xi ci其中， xi 为数据对象， ci 表示类 Ci 的质心， E 则表示数据集中所有对象的 误差平方和。该目标函数采用欧氏距离。K-均值聚类算法的过程描述如下：(1) 任选 k 个模式特征矢量作为初始聚类中心： z1(0) , z2(0) ,., z(c0) ，令 k=0.(2) 将待分类的模式识别特征矢量集 xuri 中的模式逐个按最小距离原则分划给(k 1) lk 类中的某一类，即如果di(lk) min dij(k) ，i 1,2,., N ，则判 xi式中， di(jk) 表示 xi 和 (jk) 的中心 z(jk) 的距离，上标表示迭代次数， 于是产生新的聚类(jk

8、1), j 1,2,., k(3) 计算重新分类后的各类心(k 1) zj1n(jk1) xixi , j(k 1)1,2,., k式中， n(jk 1)为 j(k 1)类中所含模式的个数(4) 如果 z(jk 1) z(jk)( j 1,2,., k) ，则结束；否则， k k 1 ，转至步骤( 2)3.结果分析在二维和三维空间里， 原样本点为蓝色， 随机选取样本点中的四个点作为中 心，用 *表示，其他对象根据与这四个聚类中心(对象)的距离，根据最近距离 原则，逐个分别聚类到这四个聚类中心所代表的聚类中， 每完成一轮聚类， 聚类 的中心会发生相应的改变， 之后更新这四个聚类的聚类中心， 根据

9、所获得的四个 新聚类中心， 以及各对象与这四个聚类中心的距离， 根据最近距离原则， 对所有 对象进行重新归类。再次重复上述过程就可获得聚类结果， 当各聚类中的对象 (归属) 已不再变 化，整个聚类操作结束。经过 K 均值聚类计算，样本点分为红，蓝，绿，黑四个聚类，计算出新的四 个聚类中心，用 * 表示。该算法中， 一次迭代中把每个数据对象分到离它最近的聚类中心所在类， 这 个过程的时间复杂度 O(nkd) ，这里的 n指的是总的数据对象个数， k 是指定的聚 类数，d 是数据对象的位数：新的分类产生后需要计算新的聚类中心，这个过程 的时间复杂度为 O(nd) 。因此，这个算法一次迭代后所需要的

10、总的时间复杂度为 O(nkd).通过实验可以看出， k 个初始聚类中心点的选取对聚类结果有较大的影响， 因为在该算法中是随机地任意选取 k 个点作为初始聚类中心， 分类结果受到取定 的类别数目和聚类中心初始位置的影响， 所以结果只是局部最优。 K-均值算法常 采用误差平方和准则函数作为聚类准则函数 (目标函数 ). 目标函数在空间状态是 一个非凸函数， 非凸函数往往存在很多个局部极小值， 只有一个是全局最小。 所 以通过迭代计算，目标函数常常达到局部最小而难以得到全局最小。聚类个数 k 的选定是很难估计的， 很多时候我们事先并不知道给定的数据集 应该分成多少类才合适。关于 K-均值聚类算法中聚

11、类数据 k 值得确定，有些根 据方差分析理论， 应用混合 F 统计量来确定最佳分类树， 并应用了模糊划分熵来 验证最佳分类的准确性。将类的质心（均值点） 作为聚类中心进行新一轮聚类计算， 将导致远离数据 密集区的孤立点和噪声点会导致聚类中心偏离真正的数据密集区，所以K-均值算法对噪声点和孤立点非常敏感。图 1 为未聚类前初始样本及中心，图 2 为聚类后的样本及中心。图 1 未聚类前初始样本及中心4 程序：clear;clc;TH= 0.001;N =20;n =0;th =1;%第一类数据mu1=0 0 0;% 均值S1=3 0 0;0 3 0;0 0 3;% 协方差矩阵X1=mvnrnd(m

12、u1,S1,50);%产生多维正态随机数， mul 为期望向量， s1为协方差矩阵， 50 为规模%第一类数据% 协方差矩阵% 协方差矩阵mu2=4 4 4; % 均值S2=0 0 0;0 3 0;0 0 3;X2=mvnrnd(mu2,S2,50);%第一类数据mu3=-4 4 -4;% 均值S3=3 0 0;0 3 0;0 0 3;X3=mvnrnd(mu3,S3,50);X=X1;X2;X3;%三类数据合成一个不带标号的数据类plot3(X(:,1),X(:,2),X(:,3), + ); %显示holdongridontitle( 初始聚类中心 );k=4;count,d = size

13、(X);centers=X(round(rand(k,1)*count),:);id = zeros(count,1);%会出聚类中心kxkoplot3(centers(:,1),centers(:,2),centers(:,3), MarkerSize,10, LineWidth,2)plot3(centers(:,1),centers(:,2),centers(:,3), MarkerSize,10, LineWidth,2)dist = zeros(k,1);newcenters = zeros(k,d);while ( n TH)%while nNfor ix = 1:countfor

14、 ik = 1:kdist(ik) = sum(X(ix,:)-centers(ik,:).2);end,tmp=sort(dist);%离哪个类最近则属于那个类id(ix) =tmp(1);endth = 0;for ik = 1:kidtmp = find(id = ik);if length(idtmp) = 0returnendnewcenters(ik,:)= sum(X(idtmp,:),1)./length(idtmp); th = th + sum(newcenters(ik,:) - centers(ik,:).2);end centers = newcenters; n = n+1;end figure(2)plot3(X(find(id=1),1),X(find(id=1),2),X(find(id=1),3),r* ),hold onplot3(X(find(id=2),1),X(find(id=2),2),X(find(id=2),3),g* ),hold on plot3(X(find(id=3),1),X(find(id=3),2),X(find(id=3),3),b* ),hold onplot3(