c均值算法c++实现实验报告

2025-09-19

模式识别实验二 c均值算法

1实验目的

熟悉c均值算法，通过程序语言实现该算法，比较每个聚类的初始均值不同时，算法结果的差

别。理解动态聚类算法的算法思想。

2实验内容和要求

写程序实现c均值算法，并用表中的三维数据进行测试，下面给出了每种测试的类别数目和初始值。不要求编程环境，可以使用C，MATLAB等。（1）c=2, m1(0)=(1,1,1)T, m2(0)=(-1,1,-1)T。（2）c=2, m1(0)=(0,0,0)T, m2(0)=(1,1,-1)T。

将（2）得到的结果与（1）中的结果进行比较，并解释差别，包括迭代次数的差别。（3）c=3, m1(0)=(0,0,0)T, m2(0)=(1,1,1)T, m3(0)=(-1,0,2)T。

（4）c=3, m1(0)=(-0.1,0,0.1)T, m2(0)=(0,-0.1,0.1)T, m3(0)=(-0.1,-0.1,0.1)T。

将（4）得到的结果与（3）中的结果进行比较，并解释差别，包括迭代次数的差别。

数据如下表所示：

样本编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 x1 -7.82 -6.68 4.36 6.72 -8.64 -6.87 4.47 6.73 -7.71 -6.91 6.18 6.72 -6.25 -6.94 8.09 6.18 -5.19 -6.38 4.08 6.27 x2 -4.58 3.16 -2.19 0.88 3.06 0.57 -2.62 -2.01 2.34 -0.49 2.81 -0.93 -0.26 -1.22 0.20 0.17 4.24 -1.74 1.30 0.93 x3 -3.97 2.71 2.09 2.80 3.50 -5.45 5.76 4.18 -6.33 -5.68 5.82 -4.04 0.56 1.13 2.25 -4.15 4.04 1.43 5.33 -2.78 3实验原理

K均值聚类，即众所周知的C均值聚类，已经应用到各种领域。它的核心思想如下：算法把n个向量xj(1,2…,n)分为c个组Gi(i=1,2,…,c)，并求每组的聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时，价值函数可定义为：

模式识别实验二 c均值算法

J??Ji??(i?1i?1cck,xk?Gi?||xk?ci||2) (6.2)

这里Ji??(?||xi?1k,xk?Gick?ci||2)是组i内的价值函数。这样Ji的值依赖于Gi的几何特性和ci的位置。

一般来说，可用一个通用距离函数d(xk,ci)代替组I中的向量xk，则相应的总价值函数可表示为：

J??Ji??(?d(xi?1i?1k,xk?Gicck?ci)) (6.3)

为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（6.2）式。划分过的组一般用一个c×n的二维隶属矩阵U来定义。如果第j个数据点xj属于组i，则U中的元素uij为1；否则，该元素取0。一旦确定聚类中心ci，可导出如下使式（6.2）最小uij：

?1?uij????0对每个k?i,如果xj?ci其它2?xj?ck，2 (6.4)

重申一点，如果ci是xj的最近的聚类中心，那么xj属于组i。由于一个给定数据只能属于一个组，

所以隶属矩阵U具有如下性质：

?ui?1cij?1，?j?1,?,n (6.5)

且

??ui?1j?1cnij?n (6.6)

另一方面，如果固定uij则使（6.2）式最小的最佳聚类中心就是组I中所有向量的均值：

ci?这里|Gi|是Gi的规模或Gi?1Gik,xk?Gi?xk， (6.7)

?nj?1uij。

为便于批模式运行，这里给出数据集xi（1，2…，n）的K均值算法；该算法重复使用下列步骤，确定聚类中心ci和隶属矩阵U：

步骤1：初始化聚类中心ci,i=1,…,c。典型的做法是从所有数据点中任取c个点。步骤2：用式（6.4）确定隶属矩阵U。

步骤3：根据式（6.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数质的改变量小于某个阀值，则算法停止。

步骤4：根据式（6.5）修正聚类中心。返回步骤2。

该算法本身是迭代的，且不能确保它收敛于最优解。K均值算法的性能依赖于聚类中心的初始位置。所以，为了使它可取，要么用一些前端方法求好的初始聚类中心；要么每次用不同的初始聚类中心，将该算法运行多次。此外，上述算法仅仅是一种具有代表性的方法；我们还可以先初始化一个任意的隶属矩阵，然后再执行迭代过程。

模式识别实验二 c均值算法

4实验结果与分析

4.1当 c=2时, m1(0)=(1,1,1)T, m2(0)=(-1,1,-1)T current Je is: 352.554932 after recalculate mean by 2 steps class 0: (4.36, -2.19, 2.09) (6.72, 0.88, 2.80) (4.47, -2.62, 5.76) (6.73, -2.01, 4.18) (6.18, 2.81, 5.82) (6.72, -0.93, -4.04) (8.09, 0.20, 2.25) (6.18, 0.17, -4.15) (4.08, 1.30, 5.33) (6.27, 0.93, -2.78) class 1: (-8.64, 3.06, 3.50) (-6.87, 0.57, -5.45) (-7.71, 2.34, -6.33) (-6.91, -0.49, -5.68) (-6.25, -0.26, 0.56) (-6.94, -1.22, 1.13) (-5.19, 4.24, 4.04) (-6.38, -1.74, 1.43) m1(0)=(0,0,0)T, m2(0)=(1,1,-1)T current Je is: 352.554871 after recalculate mean by 10 steps class 0: (-8.64, 3.06, 3.50) (-6.87, 0.57, -5.45) (-7.71, 2.34, -6.33) (-6.91, -0.49, -5.68) (-6.25, -0.26, 0.56) (-6.94, -1.22, 1.13) (-5.19, 4.24, 4.04) (-6.38, -1.74, 1.43) class 1: (6.72, 0.88, 2.80) (6.18, 2.81, 5.82) (6.72, -0.93, -4.04) (8.09, 0.20, 2.25) (6.18, 0.17, -4.15) (6.27, 0.93, -2.78) (4.36, -2.19, 2.09) (4.47, -2.62, 5.76) (6.73, -2.01, 4.18) (4.08, 1.30, 5.33) 4.2当c=3时,

m1(0)=(0,0,0)T, m2(0)=(1,1,1)T, m3(0)=(-1,0,2)T current Je is: 225.847061 after recalculate mean by 3 steps class 0: (-6.91, -0.49, -5.68) class 1: m1(0)=(-0.1,0,0.1)T, m2(0)=(0,-0.1,0.1)T, m3(0)=(-0.1,-0.1,0.1)T current Je is: 225.847015 after recalculate mean by 9 steps class 0: (-6.94, -1.22, 1.13) (-5.19, 4.24, 4.04) (-6.38, -1.74, 1.43) (-6.87, 0.57, -5.45) (-7.71, 2.34, -6.33) (-8.64, 3.06, 3.50) (-6.25, -0.26, 0.56) (6.72, 0.88, 2.80) (4.47, -2.62, 5.76) class 1: (6.73, -2.01, 4.18) (6.18, 2.81, 5.82) (6.72, 0.88, 2.80) (4.47, -2.62, 5.76) (6.72, -0.93, -4.04) (8.09, 0.20, 2.25) (6.73, -2.01, 4.18) (6.18, 2.81, 5.82) (6.18, 0.17, -4.15) (4.08, 1.30, 5.33) (6.72, -0.93, -4.04) (8.09, 0.20, 2.25) (6.27, 0.93, -2.78) class 2: (6.18, 0.17, -4.15) (4.08, 1.30, 5.33) (6.27, 0.93, -2.78) (-8.64, 3.06, 3.50) (-6.25, -0.26, 0.56) class 2: (-6.94, -1.22, 1.13) (-5.19, 4.24, 4.04) (-6.91, -0.49, -5.68) (-6.87, 0.57, -5.45) (-6.38, -1.74, 1.43) (-7.71, 2.34, -6.33) 5实验体会

1．无论在聚类时，初始均值如何选取，在程序结果中总能得到相同的分类结果，同时Je的结果相

差很小。

2．当各聚类设定的初始均值不同时，程序结果经过的步骤不同，这里我选取的计数值为均值重新

计算的步骤。

模式识别实验二 c均值算法

6实验程序

//cmean.h #pragma once #include #include using namespace std; #define DATANUM 20 #define MAXDIST 333333 struct CData {

float x1; float x2; };

class CCMean { public:

CCMean(CData *pdata); ~CCMean(void); void init();

void work(int InitClassNum); private:

// calculate the mean of class i: void CalcuMean( int i ); // calculate the ERROR of class i: void CalcuJc(int i); void CalcuJe();

// step 1 of C-Mean algorithm void InitDeploy();

// step 4 and 5 of C-Mean algorithm // da is now in class i,

// return ture when moving da from class to class k // return false when we do not move da

bool MoveItoK( const CData& da, int i, int &k ); // calculate the distance of to data:

float dist( const CData& mean, const CData& da); // print result: void OutPut();

// iClassNum is the initial class number, in text book, iClassNum <==> C int iClassNum; // pointer to data array: CData *pData;

// store the mean of all classes. just ueses 0 to iClassNum - 1;

float x3;

模式识别实验二 c均值算法

// in text book is: m1, m2, m3, m4, ... , mc. CData mean[DATANUM];

// store the ERROR of each class, just ueses 0 to iClassNum - 1; // the sum of jc[0] to jc[iClassNum - 1] will be je defined following jc; float jc[DATANUM];

//the sum of jc[0] to jc[iClassNum - 1] float je;

// pcla[i] pointer class i which store in LIST list< CData >* pcla[DATANUM]; };

//*************************************************************************************** //cmean.cpp #include \#include \

CCMean::CCMean(CData *pdata) {

pData = pdata;

for(int i = 0; i < DATANUM; i ++ ) {

pcla[i] = new list< CData >; assert( pcla[i] != 0 ); } je = 0; }

CCMean::~CCMean() {

for(int i = 0; i < DATANUM; i ++ ) delete pcla[i]; }

void CCMean::init() {

for(int i = 0; i < DATANUM; i ++ ) {

pcla[i]->clear(); mean[i].x1 = 0; mean[i].x2 = 0;

mean[i].x3 = 0; } je = 0; }

void CCMean::CalcuMean(int ii)

int iCount;

iCount = 0;

c均值算法c++实现实验报告.doc 将本文的Word文档下载到电脑下载失败或者文档不完整，请联系客服人员解决！

下载这篇word文档