论文部分内容阅读
聚类算法是一种广泛应用于数据挖掘、机器学习、图像处理等若干领域的重要技术。进化聚类算法是聚类算法中的重要分支,本文旨在提出两种新的进化聚类算法,即混合属性进化聚类算法和混合策略进化聚类算法。本文对聚类问题和进化计算做了简要的介绍,详细描述和讨论了提出的两种进化聚类算法,并在人工数据集和UCI数据集上对算法进行了性能测试和分析。本文在第二章提出了针对混合属性数据集的进化聚类算法。它基于K原型算法,应用进化计算的框架和算子求得混合属性数据集的合理划分,因此可以被看做是一种进化K原型算法。作为一种基于划分的聚类算法,K原型算法是针对混合属性数据集的著名算法。然而,由于它采用K均值的迭代方式,所以它对初始原型敏感且容易陷入局部最优。进化计算具有全局搜索能力,因此本文采用进化计算操作K原型算法以克服原始算法的缺陷。对人工数据集和UCI数据集的实验表明,本章提出的混合属性进化聚类算法比原始的K原型算法性能更优。本文在第三章提出了基于多种群的混合进化聚类算法,它属于混合策略进化聚类算法的一种。此算法采用多种群策略和一种新的抽取策略以传递父代个体的有用信息给子代。父代个体是从每个候选种群中选出的一个最好个体。整个数据集被建模成一幅无向图,因此本算法使用基于图的KWNC标准作为适应度函数选择个体。此外,进化中还使用了约简策略,以加快运行速度。对于进化收敛后的不同情形,本章设计了相应的终止方案以得到最终聚类结果。对人工数据集和UCI数据集的实验表明,本章算法能够找到比嵌入其中的候选算法和进化K均值算法更优的聚类结果。本文在第四章提出了基于多种群和图搜索的混合进化聚类算法,它也属于混合策略进化聚类算法的一种。此算法采用与第三章算法类似的框架,适应度函数,抽取策略以及终止策略。不同点在于本章用三种不同算法产生层级聚类候选种群,增大了其多样性；此外两种不同的基于图的搜索策略被用于寻找更合理的数据划分。这些方法都大大提高了算法的性能。对人工数据集和UCI数据集的实验表明,本章算法不仅具有第三章算法的优点,并且其对比于其它算法的优势大大增强。最后本章对重要的参数做了分析以更好地阐述算法的特点。本文工作得到国家自然科学基金(批准号：60703107)、国家863项目(批准号：2009AA122210)、教育部新世纪优秀人才支持计划(批准号：NCET-08-0811),陕西省青年科技新星支持计划(批准号：2010KJXX-03),和中央高校基本科研业务费重点项目(批准号：K50510020001)资助。