一种K-means聚类算法的实现及其算法改进-Read.docVIP

一种K-means聚类算法的实现及其算法改进 姓名：张金增 学号：200612017081202016 专业：计算机软件与理论 一、引言 数据挖掘技术(Data Mining)是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中 ,发现并提取隐含在其中未知的、可信的、有用的模式的过程 。目前 ,数据挖掘已广泛应用于大中型企业、商业、银行、保险、医学等领域。 聚类是数据挖掘中的一类重要技术 ,是分析数据并从中发现有用信息的一种有效手段。它将物理或抽象对象集合分成相似对象类的过程 ,这些对象与同一个簇中的对象彼此相似，而与其他簇中的对象相异。作为数据挖掘的一种一向功能，聚类分析可以用作独立的工具，获得数据分布的情况，观察每个簇的特征，集中对某些特定的簇做进一步的分析。作为统计学的一个分支和一种无监督的学习方法 ,聚类从数学分析的角度提供了一种准确、细致的分析工具。而K-means算法是属于聚类算法中一种基本的划分方法。 二、K-means算法的基本思想 1、相关定义 定义1 K均值算法 以k为输入参数，把n个对象的集合分为K个簇，使得结果簇内的相似度高，而簇间的相似度低。 定义2 欧几里得距离 它的定义如下： 其中i = (xi1, xi2, …, xip)和 j = (xj1, xj2, …, xjp) 是两个 p-维数据对象。 定义3 一个样本点与一个样本集的距离 定义为这个样本点与这个样本集中所有样本点当中最近的距离.则一个样本点X和一个样本集合V 之间的距离定义如下 d(X,V)=min(d(X,Y),Y∈V) 2．算法基本思想 K-means算法的过程： 输入: 簇的个数k以及包含n个数据对象的数据集 输出: 满足方差最小标准的K个聚类 处理流程 (1) 从 n个数据对象中任意选择k个对象作为初始聚类中心. (2)循环下述流程 (3) 到 (4)直到每个聚类不再发生变化为止. (3)根据每个聚类中所有对象的均值(中心对象)计算样本集中每个对象与这些中心对象的欧几里得距离,并根据最小距离重新对相应对象进行划分. (4)更新聚类均值，即计算每个(有变化)聚类的均值(中心对象). 在K-means算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,研究的目的是如何找到与数据在空间分布上相一致的初始聚类中心,对数据进行划分最根本的目的是使得一个聚类中的对象是相似的 ,而不同聚类中的对象是不相似的. 如果用距离表示对象间的相似程度相似的对象间的距离比不相似的对象间的距离要小。如果能够寻找到k个初始中心,它们分别代表了相似程度较大的数据集合, 那么就找到了与数据在空间分布上相一致的初始聚类中心. 算法描述 1、K-means算法描述如下： 输入：NumPattern个数据对象集合及簇的个数NumClusters 输出：NumClusters个聚类中心cluster[i].center[j]及NumClusters个聚类数据对象集合z[i]。 K-means.cpp源程序如下： #include stdio.h #include stdlib.h #include string.h #include conio.h #include math.h // DEFINES #define SUCCESS 1 #define FAILURE 0 #define TRUE 1 #define FALSE 0 #define MAXVECTDIM 20 #define MAXPATTERN 20 #define MAXCLUSTER 10 char *change(double x, int width)//把字符串x转换成字符串 { char cbuf[255]; char *cp; int i,k; int d,s; cp=fcvt(x,width,d,s);/*把浮点数x转换为字符串,d为小数点在串中的位置，s 为符号标志*/ if (s)//如果x为正数，s为0，如果x为负数，s为非0值 { strcpy(cbuf,-); } else { strcpy(cbuf, ); } /* endif */ if (d0) { for (i=0; id; i++) { cbuf[i+1]=cp[i]; } /* endfor */ cbuf