k均值聚类报告

K-均值聚类算法报告

摘要

K-均值是聚类方法中长用的一种划分方法，有很多优点，本文主要对K-均值是聚类方法的产生，工作原理，一般步骤，以及它的源码进行简单的介绍，了解K-均值是聚类！！！

（一）课题名称：K-均值聚类(K-means clustering)

（二）课题分析： J.B.MacQueen 在 1967 年提出的K-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为：

K-means 算法的特点——采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配：

① 指定聚类，即指定数据 到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。

② 修改聚类中心。

优点：本算法确定的K 个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，K<<N，t<<N 。

动态聚类方法是模式识别中一种普遍采用的方法，它具有以下3个要点： 1：选定某种距离度量作为样本间的相似性度量

2：确定某个评价聚类结果质量的准则函数

3：给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好的聚类结果

处理流程：

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；

（2） 循环（3）到（4）直到每个聚类不再发生变化为止；

（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（4） 重新计算每个（有变化）聚类的均值（中心对象）

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

（三）总体检索思路：

利用goole，百度，搜狗等搜索引擎及校内的一些数据库进行相关内容的检索。主要检索内容为K-均值聚类算法的工作原理，一般步骤，源码。

（四）检索过程记录：

关键词：K-均值聚类算法

搜索引擎：百度

检索内容：①K-均值聚类算法工作原理

②K-均值聚类算法的一般步骤

③K-均值聚类算法的源码

中文数据库检索：中国知网（http://wendang.chazidian.com/）

维普网 （http://wendang.chazidian.com/）

万方 （http://wendang.chazidian.com/）

学科范围：信息技术

检索词：K-均值聚类算法

（五）检索结果分析：

1. K-均值聚类算法的工作原理：

K-means算法的工作原理：算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数 已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着 已经收敛，因此算法结束。

2.K-means聚类算法的一般步骤：

处理流程：

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；

（2） 循环（3）到（4）直到每个聚类不再发生变化为止；

（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（4） 重新计算每个（有变化）聚类的均值（中心对象）

3.K-均值聚类算法代码

#include <stdio.h>

#include <math.h>

#define TRUE 1

#define FALSE 0

int N;//数据个数

int K;//集合个数

int * CenterIndex;//初始化质心数组的索引

double * Center;//质心集合

double * CenterCopy;//质心集合副本

double * AllData;//数据集合

double ** Cluster;//簇的集合

int * Top;//集合中元素的个数，也会用作栈处理

//随机生成k个数x(0<=x<=n-1)作为起始的质心集合

void CreateRandomArray(int n, int k,int * center)

{

int i=0;

int j=0;

srand( (unsigned)time( NULL ) );

for( i=0;i<k;++i)//随机生成k个数

{

int a=rand()%n;

//判重

for(j=0;j<i;j++)

{

if(center[j]==a)//重复

{

break;

}

}

if(j>=i)//如果不重复，加入

{

center[i]=a;

}

else

{

i--;

//如果重复，本次重新随机生成

}

}

}