【作者】 曲建华；

【导师】 刘希玉；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2010， 博士

【摘要】 聚类是分析数据并从中发现有用信息的一种有效手段。聚类可以将对象数据分组成为若干个簇,使同一个簇中的对象之间的相似度较高,而不同簇中的对象之间差别很大。通过聚类,可以发现全局的分布模式以及数据属性之间有趣的相互关系。近几年来,聚类技术已经成为数据挖掘的主要方法之一。群体智能是一种新兴演化计算技术,用于数据分析时,会继承生物系统良好的处理机制和特征。它与人工生命,特别是进化策略和遗传算法有着极为特殊的联系,已完成的理论和应用研究表明群体智能方法是一种能够有效解决大多数全局优化问题的新方法。本论文主要是针对群体智能的特点,以传统的聚类分析问题为主要研究对象,对蚁群优化算法、粒子群优化算法的理论进行了研究和算法改进,并利用改进的算法来解决聚类分析问题。研究表明,基于群体智能优化的聚类分析方法收敛速度快、适应性强,比一般的聚类分析方法能更好地揭示数据之间的相关性,为提高数据聚类的质量和效率提供了有利保障。主要研究内容如下:1对蚁群聚类算法的参数设置、适应度函数进行了改进,引入了多主体的思想,提出了改进的多主体的蚂蚁聚类算法,并对算法的相似度函数和时间复杂性进行了分析。在算法中,一个主体蚂蚁代表一个数据对象,根据它与邻域空间中的主体蚂蚁的相似度函数和转换概率函数来确定下一个移动位置,同时依照聚类规则集合动态更新其类号。主体蚂蚁的移动使得它与邻域内的对象相互影响、相互作用,仅利用少量的局部邻域信息,经过一定次数的迭代后就可以较快较好的形成聚类。实验表明多主体的蚂蚁聚类算法具有较快的搜索速度,其聚类结果明显优于改进的K-Means聚类算法。2在介绍分析粒子群优化算法的基础上,吸收并借鉴当前的研究成果,提出了一种多种群协同进化的混合粒子群聚类算法。将协同进化思想引入粒子群聚类算法中。将整个种群分解为多个子种群,各子种群独立进化,间隔一定迭代次数后,实施子种群之间的信息交换:将一个子种群中的最好解发送至相邻子种群,取代其中适应值最差的粒子。算法充分利用了PSO全局寻优的优点和K-means局部寻优的特点,在找到最优划分的同时使得划分结果更精确。算法能够自动确定聚类数目,且聚类结果不受初始聚类中心的影响。通过以上的改进提高算法的性能。3为使聚类算法的结果更具有实际意义,提出了基于距离对称性的PSO聚类算法,用于对有对称性的数据集的聚类划分。在介绍了距离对称性的相关概念后,给出了基于距离对称性的相似度函数,在此基础上,提出了基于距离对称性的粒子群聚类算法。最后通过实验用不同的方法对四组数据集分别进行了测试。实验结果说明了算法的有效性,充分考虑到了对称性对聚类结果的影响,使得聚类结果更具有实际意义。本研究的主要创新点归纳如下:1提出一种多主体的改进的蚂蚁聚类算法,并对算法的相似度函数和算法复杂度进行了分析。在算法中引入多主体概念,提出了蚂蚁聚类的规则,对相似度函数的计算公式进行了改进和分析,另外在参数的选择和设置上也做了部分改进。通过该算法不仅可以提高聚类速度,同时会得到较好的聚类划分结果。2提出一种协同进化的混合粒子群聚类算法。主要是将多种群协同进化的思想引入粒子群聚类分析中,将PSO算法的随机搜索策略和K-means方法的局部优化能力有效结合起来。算法能够自动确定聚类数目,并且聚类结果不受初始聚类中心的影响。和其它算法相比,算法收敛速度有所提高,在聚类精度上也有很大的改善。3提出了基于距离对称性的粒子群聚类算法。该算法引入了距离对称性和基于距离对称性的适应度函数,能够发现传统聚类算法难以发现的一些特殊形状的聚类。特别是在对具有对称点的数据集进行聚类时,会使得聚类结果更具有实际意义。更多还原

【Abstract】 Data clustering is an effective method of analyzing data and finding out useful information from data. Clustering analysis is the organization of a collection of patterns into clusters based on similarity. By clustering analysis, people can discover the global distributed model and interesting correlation of data attributes. In recent years clustering analysis has been an important method in data mining domain.swarm intelligence is a novel simulated evolutionary computation technology. Its inspiration came from of some mechanism in biological system. It has special relationships with artificial life, evolution strategies and genetic algorithm. Much theory of research and application related to swarm intelligence proves that it is a kind of effective method to solve many global optimal problems.In view of the features of swarm intelligence, this paper focuses on the improvement of clustering algorithms based on ACO and PSO. The main research content of this paper includes:1 A multi-agent ant clustering algorithm is proposed. A novel multi-agent idea is introduced in the algorithm. The algorithm improved on the computation method of fitness and the value of some parameters. In the algorithm, each ant represents a data object. It will decide its next moving position according to similarity function and probability converting function between it and its neighbors. At the same time it will update its cluster number according to clustering rules. Each ant only depends on a little local information to find proper cluster. The experiment results demonstrated effectiveness of the algorithm.2 An improved method named PSO clustering algorithm based on cooperative evolution is proposed. Cooperative evolutionary strategy with multi-populations is introduced in the algorithm. The global optimum will be passed in all sub-populations. The whole clustering process is divided into two stages. The first stage uses the cooperative evolutionary PSO algorithm to search the initial clustering centers. The second stage uses the K-means algorithm. The algorithm can decide the number of cluster automatically. The clustering result is not influence by the iniatial clustering centers.3 A novel point symmetry-based PSO clustering algorithm is proposed. It could defect the number of clusters and the proper partitions from data sets when they possess the property of symmetry. In the proposed algorithm, assignment of points is done based on point symmetry based distance rather than the Euclid distance. A newly point symmetry based distance cluster fitness is used as a measure of the validity of the corresponding partitioning. The algorithm could make the clustering results more practical. The effectiveness of the algorithm compared to standard clustering algorithm is demonstrated for different data sets.Innovative viewpoints of this dissertation are summarized as follows:1 An improved multi-agent ant clustering algorithm is proposed. In the algorithm, multi-agents idea is introduced. The algorithm improved the computation method of fitness and the setting method of parameters. By the use of the algorithm, the clustering speed increased greatly.2 PSO clustering algorithm based on cooperative evolution is proposed. Cooperative evolution idea is introduced in the algorithm. The algorithm makes the best of the stochastic search strategy of PSO and the local optimized mechanism of K-means. The clustering result is not influenced by the initial cluster centers.3 Point symmetry based distance PSO clustering algorithm is proposed. It can decide the number of clusters and detect the proper partitions when they possess the property of symmetry. Assignment of points to different clusters is done based on point symmetry based distance. It makes the clustering results more practical.更多还原