毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc

上传人:仙人指路1688 文档编号:3979347 上传时间:2023-03-30 格式:DOC 页数:37 大小:3.67MB
返回 下载 相关 举报
毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc_第1页
第1页 / 共37页
毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc_第2页
第2页 / 共37页
毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc_第3页
第3页 / 共37页
毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc_第4页
第4页 / 共37页
毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc_第5页
第5页 / 共37页
点击查看更多>>
资源描述

《毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc》由会员分享,可在线阅读,更多相关《毕业设计(论文)基于Kmeans算法的平面点集聚类系统.doc(37页珍藏版)》请在三一办公上搜索。

1、基于K-means算法的平面点集聚类系统院 系北方软件学院专 业计算机科学与技术(软件工程)班 级学 号姓 名指导教师负责教师沈阳航空航天大学2011年6月摘 要聚类是数据挖掘领域中重要的技术之一,用于发现数据中未知的分类。聚类分析已经有了很长的研究历史,其重要性已经越来越受到人们的肯定。聚类算法是机器学习、数据挖掘和模式识别等研究方向的重要研究内容之一,在识别数据对象的内在关系方面,具有极其重要的作用。聚类主要应用于模式识别中的语音识别、字符识别等,机器学习中的聚类算法应用于图像分割,图像处理中,主要用于数据压缩、信息检索。聚类的另一个主要应用是数据挖掘、时空数据库应用、序列和异常数据分析等

2、。此外,聚类还应用于统计科学,同时,在生物学、地质学、地理学以及市场营销等方面也有着重要的作用。本文是对聚类算法K-means的研究。首先介绍了聚类技术的相关概念。其次重点对K-means算法进行了分析研究,K-means算法是一种基于划分的方法,该算法的优点是简单易行,时间复杂度为O(n),并且适用于处理大规模数据。本系统主要是对其进行算法和界面实现。关键词:数据挖掘;聚类分析;K-meansAbstractClustering is one of the most important technologies of data mining, which is used to discove

3、r unknown classification in data set. As it has a long history of research,the importance of clustering is affirmed by people. Clustering algorithms is one of the most important algorithms which is researched extensively in machine learning, data mining and pattern recognition. It has important effe

4、ct on identify intra-connection between objects. Clustering is applied in sound recognition, character recognition of pattern recognition and so on. Clustering algorithms in machine learning are applied in image segmentation and image processing which can be used to deal with data compression and in

5、formation search. Another important application is applied in data mining, space database, sequence and anomaly data analysis and other fields such as statistic, biology, geognosy, geography and market. This paper is about the research of K-means. At first,some related concepts of clustering are giv

6、en. The chief point of the paper is the research on K-means. K-means, O(n) time complexity, is a partition method that it is easy to use and can work well with large data set. The system is to achieve its algorithm and interface.Keywords: Data Mining; Clustering Analysis; K-means目 录1绪论11.1研究意义及背景11.

7、2系统设计要求21.3本文目的32研究现状及设计目标42.1国内外相关研究现状42.2现行研究存在的问题及解决办法52.2.1K-means的基本思想62.2.2K-means的优点62.2.3聚类分析中常用的距离计算函数62.2.4聚类方法分析72.2.5其他聚类算法82.2设计目标92.3 经济效益分析93关键问题及分析103.1研究设计中要解决的问题103.2前期工作123.3关键技术123.3.1K-means算法123.3.2相关技术介绍134需求分析154.1总体设计思想及设计原则154.1.1设计思想154.1.2设计原则164.2可行性分析164.3系统开发工具及环境165系统

8、设计及实现175.1系统构架175.2各模块的实现方法及关键代码185.2.1数据输入模块185.2.2K-means算法计算模块195.2.3结果输出模块195.2.4绘图模块205.3系统流程225.4界面设计235.4.1数据输入界面235.4.2结果输出界面235.4.3绘图界面246系统测试256.1测试实例的研究与选择256.2实例测试257结论与展望28参考文献29致 谢311 绪论随着计算机硬件和软件技术的飞速发展,尤其是数据库技术的普及,人们面临着日益扩张的数据海洋,原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识,从而形成一种独特的现象“丰富的数据,贫乏的

9、知识”。数据挖掘(Data Mining)又称为数据库中知识发现(Knowledge Discovery form Database,KDD),它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。目前是在大量的数据中发现人们感兴趣的知识。常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。由于数据库中收集了大量的数据,聚类分析已经成为数据挖掘领域的重要技术之一,本文中介绍的K-means算法就是聚类分析中应用最广泛的一种聚类算法。1.1 研究意义及背景面对信息技术的日新月异,人们利用信息技术生产和搜集数据的能力大幅度提高,大量的数据库被用于商业管

10、理、政府办公、科学研究和工程开发等等,要想使数据真正成为一个公司的资源,只有充分利用它为公司自身的业务决策和战略发展服务才行,否则大量的数据可能成为包袱,数据挖掘和知识发现技术应运而生,并得以蓬勃发展,越来越显示出其强大的生命力。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。人们把原始数据看作是形成知识的源泉,就像从矿石中采矿一样。原始数据可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形、图像数据,甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的,也可以是非数学的可以是演绎的

11、,也可以是归纳的。挖掘出的知识可以被用于信息管理。查询优化、决策支持、过程控制等,还可以用于数据自身的维护。因此,数据挖掘是一门交叉学科,涉及人工智能技术、统计技术与数据库技术等多种技术。它汇聚了不同领域的研究者,尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。聚类是数据挖掘技术研究中的重要技术的一种,能有效的通过分析数据并从中发现有用的信息。聚类将数据对象分组成为若干个类或簇,使得在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别很大,通过聚类,人们能够识别密集和稀疏的区域,发现全局的分布模式以及数据属性之间有趣的相互关系。聚类分析在客户分类、基因识别

12、、文本分类、空间数据处理、卫星照片分析、医疗图像自动检测等领域有着广泛的应用,而其本身的研究也是一个蓬勃发展的领域,数据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学的发展推动着聚类分析研究的进展,使它已成为数据挖掘研究中的一个热点,在市场分析中,通过聚类分析能帮助决策者识别不同特征的客户群以及各客户群的行为特征在生物工程研究中,聚类分析能够用于推导动植物的分类,按照功能对基因进行划分并获取种群中的固有结构特征在非关系数据库领域如空间数据库领域,聚类分析能够识别具有相同地理特征的区域以及该区域的环境和人的特征在信息检索领域,聚类分析能够对文档进行分类,提高检索效率。聚类分析将大量数据划

13、分为性质相同的子类,便于了解数据的分布情况。与其他数据挖掘方法不同,在进行聚类分析前用户一般并不知道数据集的特征。因此,从某种角度看,聚类分析是一种无监督的学习过程,是基于观察的学习而不是基于实例的学习。 1.2 系统设计要求本系统主要是通过对K-means算法的理解,实现利用K-means聚类技术对平面点集进行聚类。具体要求:(1)通过界面实现平面点集的输入输出;(2)利用K-means聚类技术对平面点集进行聚类;(3)通过平面图显示聚类结果。1.3 本文目的本文所研究的K-means聚类技术是聚类算法中划分方法里面应用最广泛的一种方案,通过对K-means聚类算法的理解应用,体会其优点和缺

14、点,并将其进行系统实现。2 研究现状及设计目标2.1 国内外相关研究现状聚类分析作为统计学的一个分支,己被广泛地研究了多年,主要集中在基于距离的聚类分析。基于K均值、k-medoids(k-中心点)和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中。在机器学习领域,聚类是无指导学习的一个例子。与分类不同,聚类和无指导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因,聚类是观察式学习,而不是示例式学习。在概念聚类中,一组对象只有当它们可以被一个概念描述时才形成一个簇,这不同于基于几何距离度量相似度的传统聚类。聚类分析的研究工作集中在为大型数据库的有效和实际的聚类分析寻求适

15、当的方法,目前的研究方向包括下列几个方面:(1)算法的可伸缩性:在很多聚类算法中,数据对象小于200个的小数据集合上鲁棒性执行多种数据模型;而对于包含几百万个数据对象的大规模数据库进行聚类时,将会导致有不同的偏差结果,这就需要聚类算法具有高度的可伸缩性,能有效地处理海量数据;(2)处理不同类型属性的能力:设计的很多算法是用于聚类数值类型的数据,但在实际应用中可能要求聚类其他类型的数据,如分类/标称类型(categoficalnominal),序数型(ordinal),二元(binary)数据,或者这些数据类型的混合;(3)发现任意形状的聚类:许多聚类算法是基于欧几里德距离,趋向于发现具有相近密

16、度和尺寸的球状簇。但一个簇可能是任意形状的,提出能发现任意形状簇的算法非常重要;(4)用于决定输入参数的领域知识最小化:在聚类分析中,许多聚类算法要求用户输入一定的参数,如希望簇的数目。聚类结果对于输入参数很敏感,通常参数较难确定,尤其是对于含有高维对象的数据集更是如此。要求入工输入参数不但加重了用户的负担,而且也使聚类质量难以控制;(5)对于输入记录顺序不敏感:一些聚类算法对于输入数据的顺序是敏感的。如对于同一个数据集合,以不同的顺序提交给同一个算法时,可能产生差别很大的聚类结果。研究和开发对数据输入顺序不敏感的算法具有重要的意义;(6)高维性:一个数据库可能含有若干维或者属性。很多聚类算法

17、擅长处理低维数据,一般只涉及两到三维。通常最多在三维的情况下能够很好地判断聚类的质量。聚类数据对象在高维空间是非常有挑战性的,尤其是考虑到这样的数据可能高度偏斜,非常稀疏;(7)处理噪声数据的能力:在现实应用中绝大多数的数据都包含了孤立点,空缺、未知数据或者错误的数据。有些聚类算法对于这样的数据敏感,将会导致质量较低的聚类结果;(8)基于约束的聚类:在实际应用中有可能需要在各种约束条件下进行聚类。既要找到满足特定的约束,又要具有良好聚类特性的数据分组是一项具有挑战性的任务;(9)可解释性和可用性:通常用户希望聚类结果是可解释的,可理解的和可用的。因此,应用目标如何影响聚类方法的选择也是一项重要

18、的研究课题。2.2 现行研究存在的问题及解决办法聚类就是根据最大化类内的相似性、最小化类间的相似性原则对数据对象进行分组的一个过程。其结果就是一个个由数据对象组成的簇,每个簇内的对象之间具有很高的相似性, 而簇间的对象则很不相似。 聚类的应用越来越广泛, 在经济学、 生物学、气象学、医药学、信息工程和工程技术等许多领域都有着十分重要的作用。因此,对聚类的要求也越来越高,提出准确且又高效的聚类算法刻不容缓。人们已经提出了很多聚类算法,比如有基于划分的K-MEANS算法、CLARANS 算法;基于层次的BIRCH算法、CURE算法;基于网格的STING算法、WaveCluster算法等。但是这些算

19、法都存在着不足,所以就存在如何选择参数的问题,不适当的选择将会大大影响算法的结果。2.2.1 K-means的基本思想给定类的个数k,随机挑选 k个对象为初始聚类中心,利用距离最近的原则, 将其余数据集对象分到k个类中去,聚类的结果由k个聚类中心来表达。算法采用迭代更新的方法,通过判定给定的聚类目标函数,每一次迭代过程都向目标函数值减少的方向进行。在每一轮中,依据k个参照点将其周围的点分别组成k个类,而每个类的几何中心将被作为下一轮迭代的参照点,迭代使得选取的参照点越来越接近真实的类几何中心,使得类内对象的相似性最大,类间对象的相似性最小。2.2.2 K-means的优点K- means 算法

20、有三个优点:(1) 是解决聚类问题的一种经典算法,简单、快捷;(2) 对处理大数据集,该算法是相对可伸缩和高效率的。因为它的复杂度是O(n k t),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常kn且tn;(3) 当结果簇是密集的,而簇与簇之间的区别明显时,它的效果较好。2.2.3 聚类分析中常用的距离计算函数当前聚类分析中常用距离计算算法有明氏距离、马氏距离、兰氏距离。1. 明氏(Minkowski)距离 (2.1)当q取1,2,。时,则分别得绝对距离、欧式(Euclid)距离、切比雪夫(Chebyshev)距离。本系统所应用的距离算法是欧氏距离。2. 马氏(Mahalanoi

21、s)距离 (2.2)是样本矩阵A的协方差阵,是总体分布的协差估计量。马氏距离是明氏距离的改进,它对于一切线性变换是不变的,克服了明氏距离受量纲影响的缺点;马氏距离也部分克服了多重相关性。3. 兰氏(Lance)距离 (2.3)兰氏距离克服了明氏距离受量纲影响的缺点,但没有考虑多重相关性。2.2.4 聚类方法分析聚类分析是直接比较各事物之间的性质, 将性质相近的归为一类, 将性质差别较大的归入不同的类。在医学实践中也经常需要做分类工作,如根据病人的一系列症状、体征和生化检查的结果,判断病人所患疾病的类型;或对一系列检查方法及其结果,将之划分成某几种方法适合用于甲类病的检查,另几种方法适合用于乙类

22、病的检查,等等。聚类分析被广泛研究了许多年。基于聚类分析的工具已经被加入到许多统计分析软件包或系统中,如S-Plus、SPSS,以及SAS。大体上,聚类算法可以划分为如下几类:(1)划分方法。给定一个包含n个对象或数据行,划分方法将数据集划分为k个子集(划分)。其中每个子集均代表一个聚类 ( k=n )。代表算法为 K-means算法、K-medoids算法和CLARANS算法;(2)层次方法。该方法就是通过分解所给定的数据对象集来创建一个层次。它存在的缺陷就是在进行(组)分解或合并之后无法回溯。将循环再定位与层次方法结合起来使用常常是有效的,如 BIRCH和CURE,就是基于这种组合方法设计

23、的;(3)基于密度的方法。只要临近区域的密度(对象或数据点的数目)超过某个阈值,就继续聚类。DBSCAN是一个有代表性的基于密度的方法。它根据一个密度阈值来控制簇的增长;(4)基于网格的方法。基于网格方法将对象空间划分为有限数目的单元以形成网格结构。其主要优点是它的处理速度很快,其处理时间独立于数据对象的数目,只与量化空间中每一维的单元数目有关。STING 就是一个典型的基于网格的方法;(5)基于模型的方法。该方法就是为每个聚类假设一个模型,然后再去发现符合相应模型的数据对象。它根据标准统计方法并考虑到噪声或异常数据, 可以自动确定聚类个数; 因而它可以产生很多的聚类方法。2.2.5 其他聚类

24、算法1. K-medoid算法K-medoid算法和K-means算法是最典型的划分方法,算法的处理思路基本相同,K-medoid算法有三种实现方式PAM,CLARA和CLARANS。K-means算法后面我们会重点介绍。PAM(Partition Around Medoid)方法:对于一个数据库D,D中含有N个元素:作为参数需给出要生成的簇的个数K(1kN)。PAM方法首先随机选择k个对象作为簇的中心,对于每一个中心点Oj,PAM方法试图用所有Nk个非中心点替换它。如果平方-误差减小则替换发生。PAM方法对于小数据库处理能得到很好的结果,但是它的计算代价非常高。需要用Nk个点替换k个点,每次

25、替换都要检验Nk次代价函数,所以复杂度是O(N(Nk)2)。CLARA(Clustering LARge Application)方法:是PAM方法的增强版,专门用于处理大量数据。CLARA方法的思想是:从所有的数据中取出5组样本,对每个样本实行PAM算法。比较5组的平方-误差,选取最小的作为输出结果。CLARA方法的确在处理大数据量时提高了运算速度,但是它所得出来的结果只是关于样本点最优的,并不是所有数据的最优解。CLARA方法结果的优劣依赖于采样方法。CLARANS(Clustering Large Application based upon RANdomized Search)方法是C

26、LARA方法的加强版,用以提高结果的质量和伸缩性。CLARANS方法的思想是:任意从k个中心点中取出一个点,从Nk中任意取一个点去替换它,如果替换成功则重新开始。如果尝试几次(参数由人给出)没有发现更好的结果,就认为已经达到局部最优。CLARANS方法的复杂度是O(N2)。实验显示CLARANS方法比PAM和CLARA更有效。2. 层次聚类法层次聚类法也称系统聚类法,是目前实际工作中用得最多的一类算法。层次聚类是将类由多变少的一种方法,分类的步骤如下:(1)各样品各成一类,这时有n类;(2)计算各样品之间的距离,将最近的两个样品归为一类;(3)计算新类与其余各类的距离,再将距离最近的两类合并,

27、这时如果类的个数仍大于1,则再继续重复上述步骤,直到所有样品归为一类,则停止。样品之间的距离有不同的定义方法,类与类之间也同样有不同的距离的定义方法,这样就产生了不同的层次聚类方法。常用的层次聚类方法有最短距离法、最长距离法、中间距离法、重心法等。2.2设计目标基于K-means算法的平面点集聚类系统是对已知的多个平面点根据用户对聚类中心的数量设置后通过K-means聚类算法的分析后得出相应结果。通过数据测试能够充分体现出K-means算法的优点。以上是理论方面的目标,在实践方面要做到编码较优,运行程序耗时较短,占内存较少。2.3 经济效益分析本系统旨在通过对K-means算法的深入理解和使用

28、后,在亲身体验K-means算法的应用过程中深切体会K-means算法的优点和缺点,为以后不断完善此算法做好准备。3 关键问题及分析3.1 研究设计中要解决的问题本系统主要是根据K-means算法的基本思想,设计实现一个基于K-means算法下的平面点集聚类系统,并通过系统界面输入和输出结果。根据上述过程中,有一个关键问题,即K-means算法的运算过程以及K-means在C语言中的实现。下面重点介绍K-means算法的运算过程。J.B.MacQueen在1967年提出的K-means算法,是一种被广泛应用于科学研究和工业应用中的经典聚类算法。K-means算法的核心思想是把n个数据对象划分为

29、k个聚类,使每个聚类中的数据点到该聚类中心的平方和最小,算法处理过程:输入:聚类个数k,包含n个数据对象的数据集。输出:k个聚类。(1)从n个数据对象中任意选取k个对象作为初始的聚类中心。(2)分别计算每个对象到各个聚类中心的距离,把对象分配到距离最近的聚类中。(3)所有对象分配完成后,重新计算k个聚类的中心。(4)与前一次计算得到的k个聚类中心比较,如果聚类中心发生变化,转(2),否则转(5)。(5)输出聚类结果。首先从n个数据对象中任意选择k个对象作为初始聚类中心;而对于所剩下的其它对象,则根据他们与这些聚类中心的相似度(距离),分别将他们分配给与其最相似的(聚类中心所代表的)聚类。然后再

30、计算每个新聚类的聚类中心(该聚类中所有对象的均值)。不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数,具体定义如下: (3.1)其中E为数据库中所有对象的均方差之和;p为代表对象的空间中的一个点;m1为聚类c1的均值(p和m1均是多维的)。公式3.1所示聚类标准旨在使所获得的k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类间尽可能的分开。图3.1 K-means算法流程图K-means算法优点是可以处理大数据集,K-means算法是相对可伸缩的和高效率的,因为它的计算复杂度为O(nkt),其中n为对象个数,k为聚类个数,t为迭代次数,通常有rn,kn,因此它

31、的复杂度通常也用O(n)表示。3.2 前期工作在开发程序之前,首先大量翻阅K-means算法相关资料,以求达到充分理解K-means算法的整个运算流程,根据C+的相关技术实现公式3.1中所达到的要求。3.3 关键技术本系统是由C+和MFC技术在Microsoft Visual Studio环境下开发完成的,下面将分别予以介绍。3.3.1 K-means算法K-means 算法是划分聚类算法的典型代表,实质上该算法基于簇中对象的平均值。为了达到全局最优,基于划分的聚类会要求穷举所有可能的划分。算法的处理过程如下: 算法的输入:簇的数目k和数据库中的对象。 算法的输出:使得平方误差准则最小的k个簇

32、。方法如下: (1)从整个样本n中,任意选择k个对象作为初始的簇的中心mi(i=1,2,k); (2)利用公式3.2,计算数据集中的每个p 到k 个簇中心的距离d ( p , mi ); (3)找到每个对象p的最小的d(p, mi),将p归入到与mi相同的簇中; (4)遍历完所有对象之后,利用公式3.3重新计算 mi的值,作为新的簇中心; (5)重新将整个数据集中的对象赋给最类似的簇。这个过程反复进行直至平方误差准则最小。 (3.2)其中i=(xi1, xi2, xin)和j=(ji1, ji2,jin)是两个n维数据对象。 (3.3)其中的mk代表第k个簇的簇中心,N代表第k个簇中数据对象的

33、个数。3.3.2 相关技术介绍C+语言发展大概可以分为三个阶段:第一阶段从80年代到1995年。这一阶段C+语言基本上是传统类型上的面向对象语言,并且凭借着接近C语言的效率,在工业界使用的开发语言中占据了相当大份额;第二阶段从1995年到2000年,这一阶段由于标准模板库(STL)和后来的Boost等程序库的出现,泛型程序设计在C+中占据了越来越多的比重性。当然,同时由于Java、C#等语言的出现和硬件价格的大规模下降,C+受到了一定的冲击; 第三阶段从2000年至今,由于以Loki、MPL等程序库为代表的产生式编程和模板编程的出现,C+出现了发展历史上又一个新的高峰,这些新技术的出现以及和原

34、有技术的融合,使C+已经成为当今主流程序设计语言中最复杂的一员。MFC,微软基础类(Microsoft Foundation Classes),同VCL类似,是一种Application Framework,随微软Visual C+ 开发工具发布。目前最新版本为10.0(截止2011年3月),并且发布了中文版。该类库提供一组通用的可重用的类库供开发人员使用。大部分类均从CObject 直接或间接派生,只有少部分类例外。MFC是Win API与C+的结合,API,即微软提供的Windows下应用程序的编程语言接口,是一种软件编程的规范,但不是一种程序开发语言本身,可以允许用户使用各种各样的第三方

35、的编程语言来进行对Windows下应用程序的开发,使这些被开发出来的应用程序能在Windows下运行, MFC是微软对API函数的专用C+封装,这种结合一方面让用户使用微软的专业C+ SDK来进行Windows下应用程序的开发变得容易,因为MFC是对API的封装,微软做了大量的工作,隐藏了很多程序开发人员在Windows下用C+ & MFC编制软件时的大量内节,如应用程序实现消息的处理,设备环境绘图,这种结合是以方便为目的的,必定要付出一定代价,因此就造成了MFC对类封装中的一定程度的的冗余和迂回,但这是可以接受的。 Visual Studio 是微软公司推出的开发环境,Visual Stud

36、io 可以用来创建 Windows 平台下的 Windows 应用程序和网络应用程序,也可以用来创建网络服务、智能设备应用程序和 Office 插件。Visual Studio 是目前最流行的 Windows 平台应用程序开发环境。目前已经开发到 10.0 版本,也就是 Visual Studio 2010。Visual Studio 2008 包括各种增强功能,例如可视化设计器(使用 .NET Framework 3.5 加速开发)、对 Web 开发工具的大量改进,以及能够加速开发和处理所有类型数据的语言增强功能。Visual Studio 2008 为开发人员提供了所有相关的工具和框架支持

37、,帮助创建引人注目的、令人印象深刻并支持 AJAX 的 Web 应用程序。 开发人员能够利用这些丰富的客户端和服务器端框架轻松构建以客户为中心的 Web 应用程序,这些应用程序可以集成任何后端数据提供程序、在任何当前浏览器内运行并完全访问 ASP NET 应用程序服务和 Microsoft 平台。4 需求分析4.1 总体设计思想及设计原则4.1.1 设计思想本设计的主要设计思想是根据用户在界面中输入的中心点个数n以及样本点个数m初始化数据,在用户输入各个样本点的过程中前n个样本点默认选取为中心点,在数据输入结束后,将数据传递到K-means算法的计算模块中,在经过计算模块计算得出最后结果,再将

38、计算结果传递到输出模块中并显示计算结果,当用户点选绘图功能时,计算结果会被传递到绘图模块中,根据数据关系以坐标形式显示出来,并将在一个聚类中的数据用线连接起来,根据中心点的颜色和其他点颜色不同表现出其特征。图4.1为本系统流程图。图4.1 系统流程图在系统执行过程中每次输入数据会有相应提示,在输入样本点时会有一个列表来显示输入的数据的个数和已经输入的样本点。系统应符合用户要求,满足用户的需要,并达到操作过程中的直观、方便、实用等要求。系统采用整体化程序设计方法,程序一次性执行完成,显示结果简单明了。 4.1.2 设计原则系统主要实现内容为:通过输入中心点以及样本点后,系统将结果直观返回给用户,

39、并且能够根据结果绘图形象反映计算结果。系统界面的总体设计原则为界面之间风格朴素、简洁大方、方便易操作。4.2 可行性分析K-means聚类技术作为聚类算法中划分方法里面应用最广泛的一种方案,其发展相当成熟,大量数据和研究结果保证本系统能够顺利开发完成。本系统主要运用MFC技术,充分的利用了在大学期间所学课程。同时数学公式的算法清晰明了。4.3 系统开发工具及环境本系统是由C+和MFC技术在Microsoft Visual Studio环境下开发完成的。5 系统设计及实现5.1 系统构架本系统主要由4个系统模块组成。图5.1为系统模块图,下面将介绍各个模块功能。图5.1 系统模块图数据输入模块:

40、本模块主要做为用户输入数据接口,根据提示输入中心点个数、样本点个数及具体样本点数据。K-means算法计算模块:本模块为本系统核心模块。根据数据输入模块中传递的样本点及中心点数据进行K-means算法的聚类计算,并将计算结果返回给主系统。结果输出模块:在计算模块计算结束后,自动进入结果输出模块,主系统将计算模块返回的数据结果传递给输出模块,本模块根据数据通过列表输出最后的中心点信息以及每个样本的数据和所属中心点。绘图模块:本模块的入口在结果输出模块中,当用户点选绘图后,主系统将数据传递给该模块,该模块根据数据二维平面坐标中绘出各个样本点以及中心点,并将同一个所属的样本点与中心点通过直线连接起来

41、,以使结果更加直观。5.2 各模块的实现方法及关键代码5.2.1 数据输入模块本模块主要做为用户输入数据接口,根据提示输入中心点个数、样本点个数及具体样本点数据。本模块为分段实现主要分为中心点样本点个数输入和样本点数据输入。以下是该模块流程图和关键代码。图5.2 输入模块流程图 UpdateData(TRUE); Xm_edybdz-1=m_edybdX; UpdateData(FALSE); UpdateData(TRUE); Ym_edybdz-1=m_edybdY; UpdateData(FALSE); m_listCtrl.InsertItem(m_edybdz-1,j, m_edyb

42、dz-1); m_listCtrl.SetItemText(m_edybdz-1, 1, x); m_listCtrl.SetItemText(m_edybdz-1, 2, y); if(m_edybdz=M) m_listCtrl.SetItemText(m_edybdz-1, 3, *);5.2.2 K-means算法计算模块本模块为本系统核心模块。根据数据输入模块中传递的样本点及中心点数据进行K-means算法的聚类计算,并将计算结果返回给主系统。该模块流程完全按照K-means算法的主要计算流程设计,主要功能代码如下。 for(;Q=0;)/判断中心点是否稳定 Q=1; for(i=0

43、;iM;i+)/计算各样本点与新中心点的欧氏距离 for(j=0;jN;j+) dij=sqrt(XN+i-Xj)*(XN+i-Xj)+(YN+i-Yj)*(YN+i-Yj); for(j=0;jN;j+) for(i=0;iM;i+) c=0; for(int p=0;pdpj) break; c+; if(c=M) if(nj!=i+1) nj=i+1; Q=0; for(i=0;iM;i+) xx=0,yy=0,c=0; for(j=0;jN;j+) if(nj=i+1) xx+=Xj; yy+=Yi; c+;5.2.3 结果输出模块在计算模块计算结束后,自动进入结果输出模块,主系统将计

44、算模块返回的数据结果传递给输出模块,本模块根据数据通过列表输出最后的中心点信息以及每个样本的数据和所属中心点。其关键代码如下。 for(int i=0;iM;i+) j.Format(第%d中心点,i+1); m_list1.InsertItem(i,j, i); x.Format(%.2f,XN+i); m_list1.SetItemText(i, 1, x); y.Format(%.2f,YN+i); m_list1.SetItemText(i, 2, y); for(i=0;iN;i+) j.Format(第%d样本点,i+1); m_list2.InsertItem(i,j, i); x.Format(%.2f,Xi); m_list2.SetItemText(i, 1, x); y.Format(%.2f,Yi); m_list2.SetItemText(i, 2, y); a.Format(第%d中心点,ni); m_list2.SetItemText(i, 3, a); 5.2.4

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公文档 > 其他范文


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号