基于多目标进化算法的多距离聚类研究

传统的聚类算法通常基于单一的距离度量而设计,如何将多种距离度量有机融合在一起是当前面临的一个挑战。提出了一种基于多目标进化算法的多距离度量聚类框架(multiobjective evolutionary multiple distance measure clustering,MOMDC),并使用欧氏距离和Path距离来设计实际框架。该框架首先将数据集分别用两种距离测度预聚类,而后将预聚类结果做合并,以降低问题的规模;其次分别计算子类间的两种距离关系;最后使用多目标进化算法在两种距离空间中并行聚类。在多目标进化算法设计中,使用实数-标签的编码方式来设计染色体,并且设计了基于两种距离测度的两个适应度函数对染色体进行评估。最终将MOMDC与其他几种经典算法在大量的数据集上进行实验对比。实验表明,该框架对不同分布的数据集均能取得良好的结果。     

改进型RBF神经网络的多标签算法研究

针对已有的RBF神经网络多标签算法未充分考虑多个样本标签之间的关联性,从而导致泛化性能受到一定影响的问题,研究分析了一种改进型RBF神经网络的多标签算法.该算法首先优化隐含层RBF神经网络基函数中心求取算法——k-均值聚类.采用AP聚类自动寻找k值以获得隐含层节点数目,并构造Huff man树来选取初始聚类中心以防k-均值聚类结果陷入局部最优.然后构造体现标签类之间信息的标签计数向量C,并将其与由优化k-均值聚类得到的聚类中心进行线性叠乘,进而改进RBF神经网络基函数中心,建立RBF神经网络.在公共多标签数据集emotion上的实验表明了该算法能够有效地进行多标签分类.     

基于主动数据选取的半监督聚类算法

利用少量标签数据获得较高聚类精度的半监督聚类技术是近年来数据挖掘和机器学习领域的研究热点。但是现有的半监督聚类算法在处理极少量标签数据和多密度不平衡数据集时的聚类精度比较低。基于主动学习技术研究标签数据选取,提出了一个新的半监督聚类算法。该算法结合最小生成树聚类和主动学习思想,选取包含信息较多的数据点作为标签数据,使用类KNN思想对类标签进行传播。通过在UCI标准数据集和模拟数据集上的测试,结果表明提出的算法比其他算法在处理多密度、不平衡数据集时有更高精度且稳定的聚类结果。     

基于Pareto 解集关联与预测的动态多目标进化算法

针对动态多目标优化问题,提出一种基于Pareto解集关联与预测的动态多目标进化算法(LP-DMOEA),设计了基于超块的Pareto解集关联方法.该方法能够动态维护若干描述Pareto解变化规律的时间序列,通过对新环境下的Pareto解集进行预测来生成初始种群.将LP-DMOEA应用于非劣分类遗传算法(NSGA2),并对3类标准测试函数进行了实验,所得结果表明该方法能够有效求解动态优化问题.     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.     

进化数据流中基于密度的聚类算法

分析当前数据流聚类算法的优点及不足,提出一种新的进化数据流中基于密度的聚类算法——Sdstream算法,该算法能够分析并处理大规模进化数据流,利用真实数据集和仿真数据集对其进行性能测试,实验结果表明,该算法具有良好的适用性、有效性和可扩展性,能够取得较高的聚类效果。     

一种基于差分进化的社团检测算法

复杂网络的社团结构分析可抽象为一个优化问题,用进化算法求解。进化类算法的一个基本问题是如何把问题的候选解编码到进化个体中。本文将索引局部邻接表示法用于社团检测进化算法的个体表示,把社团结构分析转化为一个整数优化问题。在该个体表示方法的基础上,提出了一种基于差分进化的社团检测算法。在一组合成网络和真实网络上验证了算法性能,并与两种基于遗传算法的典型社团检测进化算法进行了对比。实验结果表明,当网络社团结构较为清晰时,基于差分进化的算法检测到的社团结构具有更好的质量。     

基于改进多目标萤火虫算法的模糊聚类

针对传统的模糊聚类算法大都针对单一目标函数的优化,而无法获得更全面、更准确的聚类结果的问题,提出一种基于改进多目标萤火虫优化算法的模糊聚类方法。首先在多目标萤火虫算法中引入一种动态调整的变异机制以获得更加均匀分布的非劣解,其中以动态减小的概率选择个体并采用类似于差分进化算法中变异算子的策略对其进行变异,通过自适应调整收缩因子以提高变异效率。然后当归档集中的最优解集充满时,从中选取一定量的解与当前种群组合进行下一次进化,使得算法具有更高的效率。最后将其运用到模糊聚类问题中,通过同时优化两个模糊聚类指标的目标函数并从最终的归档集中选取一个解确定聚类结果。采用5组数据进行实验的结果表明,相对于单目标聚类方法,所提方法对各种数据集的聚类有效性指标提高了2到8个百分点,具有更高的聚类准确性和更好的综合性能。     

一种基于遗传算法的分布式的模糊聚类算法

模糊聚类是一种非监督的聚类算法,但不能保证找到全局最小值,因为是从一个给定的点开始通过迭代的方法找到一个目标函数的最小值。为了克服这个缺点,在模糊聚类算法中结合遗传算法从一个多点的概念去产生多个数据空间。直接将遗传算法应用到模糊聚类中是不合适的,因为数据集通常是巨大的,在这种情况下,染色体的长度会很长。鉴于此,提出了一种基于遗传算法的分布式的模糊聚类算法,将大的进化环境分成若干个小的进化环境。通过理论证明是可行的,且该算法能极大地提高聚类的速度。     

基于微粒群优化聚类数目的K–均值算法

K-均值算法是广泛使用的聚类算法,但该算法的聚类数目难以确定,且聚类结果对初始聚类中心比较敏感.本文提出一种基于微粒群优化聚类数目的K-均值算法,该算法采用聚类中心的坐标和通配符表示微粒位置,通过定义微粒更新公式中新的加减运算符,动态调整聚类中心的数目及坐标,此外,以改进的聚类有效性指标Davies-Bouldin准则作为适应度函数.5个人工和真实数据集的聚类结果验证了所提算法的优越性.     

Automatic clustering algorithm based on multi-objective Immunized PSO to classify actions of 3D human models

Multi-objective clustering algorithms are preferred over its conventional single objective counterparts as they incorporate additional knowledge on properties of data in the from of objectives to extract the underlying clusters present in many datasets. Researchers have recently proposed some standardized multi-objective evolutionary clustering algorithms based on genetic operations, particle swarm optimization, clonal selection principles, differential evolution and simulated annealing, etc. In many cases it is observed that hybrid evolutionary algorithms provide improved performance compared to that of individual algorithm. In this paper an automatic clustering algorithm MOIMPSO (Multi-objective Immunized Particle Swarm Optimization) is proposed, which is based on a recently developed hybrid evolutionary algorithm Immunized PSO. The proposed algorithm provides suitable Pareto optimal archive for unsupervised problems by automatically evolving the cluster centers and simultaneously optimizing two objective functions. In addition the algorithm provides a single best solution from the Pareto optimal archive which mostly satisfy the users' requirement. Rigorous simulation studies on 11 benchmark datasets demonstrate the superior performance of the proposed algorithm compared to that of the standardized automatic clustering algorithms such as MOCK, MOPSO and MOCLONAL. An interesting application of the proposed algorithm has also been demonstrated to classify the normal and aggressive actions of 3D human models.     

Non-dominated sorting genetic algorithm using fuzzy membership chromosome for categorical data clustering

In this research, a data clustering algorithm named as non-dominated sorting genetic algorithm-fuzzy membership chromosome (NSGA-FMC) based on K-modes method which combines fuzzy genetic algorithm and multi-objective optimization was proposed to improve the clustering quality on categorical data. The proposed method uses fuzzy membership value as chromosome. In addition, due to this innovative chromosome setting, a more efficient solution selection technique which selects a solution from non-dominated Pareto front based on the largest fuzzy membership is integrated in the proposed algorithm. The multiple objective functions: fuzzy compactness within a cluster (π) and separation among clusters (sep) are used to optimize the clustering quality. A series of experiments by using three UCI categorical datasets were conducted to compare the clustering results of the proposed NSGA-FMC with two existing methods: genetic algorithm fuzzy K-modes (GA-FKM) and multi-objective genetic algorithm-based fuzzy clustering of categorical attributes (MOGA (π, sep)). Adjusted Rand index (ARI), π, sep, and computation time were used as performance indexes for comparison. The experimental result showed that the proposed method can obtain better clustering quality in terms of ARI, π, and sep simultaneously with shorter computation time.     

节点相似度标签传播在社会网络中的应用研究

近年来,社会网络簇结构挖掘取得了长足的进展,广泛应用在社会网、生物网和万维网等领域中。针对当前研究社会网络簇结构挖掘的热点问题,重点研究基于局部信息的聚类算法,并进行分析总结;对标签传播算法（LPA）进行深入研究与分析,针对该算法中由于随机策略而导致网络划分并非最优的缺陷,引入节点属性相似度的概念,提出LPA-SNA算法;采用美国大学足球赛程网络、科学家合著网络作为数据集,分别实现LPA算法与LPA-SNA算法,并对它们的性能进行比较。实验结果表明LPA-SNA较之原始的LPA算法,提高了网络聚类的质量,优化了聚类效果,同时降低了算法的时间开销,提高了算法聚类速度。     

基于改进成对约束扩充的标签传播聚类算法

针对半监督聚类算法性能受到成对约束数量多寡的限制问题,现有的研究大都依赖于原始成对约束的数量。因此,首先提出了基于灰关联分析的成对约束初始化算法（initialization algorithm of pair constraints based on grey relational analysis,PCIG）。该算法通过均衡接近度计算数据对象间的相似度,并根据相似度的取值来确定可信区间,然后借鉴网络结构初始化方法来扩充数据对象间的成对关系。最后,将其应用于标签传播聚类算法。通过在五个基准数据集上进行实验,基于改进成对约束扩充的标签传播聚类算法与其他方法相比NMI值和ARI值有所提升。实验结果证明了改进成对约束扩充可以有效改善标签传播算法的聚类效果。     

基于聚类的快速多目标遗传算法

多目标遗传算法非常适合于求解多目标优化问题．讨论了进化个体之间的支配关系及有关性质，论证了可以用快速排序的方法对进化群体中的个体进行分类，同时探讨了用聚类方法来保持群体的多样性，具体讨论了基于层次凝聚距离的聚类，在此基础上提出了用分类和聚类的方法构造新的进化群体．理论分析与实验结果表明，所讨论的方法比较国际上已有的方法具有更快的收敛速度．     

精英遗传K-medoids聚类算法

针对K-medoids算法易陷入局部最优和聚类结果不稳定的问题,提出了一种精英遗传K-medoids聚类算法。该算法使用精英策略来控制遗传操作的整体进化方向;根据种群的平均适应度引入若干随机个体来提高种群多样性,从而在一定程度上减少了遗传算法的早熟现象。为了提高进化效率,该算法设计出一种新的交叉方式;为了保证交叉变异结果的优秀性,该算法引入了一种竞争机制。8个数据集的仿真实验表明,该算法在提高聚类准确率的同时,聚类结果的稳定性也有所提高。     

Evolutionary state-based novel multi-objective periodic bacterial foraging optimization algorithm for data clustering

Clustering divides objects into groups based on similarity. However, traditional clustering approaches are plagued by their difficulty in dealing with data with complex structure and high dimensionality, as well as their inability in solving multi-objective data clustering problems. To address these issues, an evolutionary state-based novel multi-objective periodic bacterial foraging optimization algorithm (ES-NMPBFO) is proposed in this article. The algorithm is designed to alleviate the high-computing complexity of the standard bacterial foraging optimization (BFO) algorithm by introducing periodic BFO. Moreover, two learning strategies, global best individual (gbest) and personal historical best individual (pbest), are used in the chemotaxis operation to enhance the convergence speed and guide the bacteria to the optimum position. Two elimination-dispersal operations are also proposed to prevent falling into local optima and improve the diversity of solutions. The proposed algorithm is compared with five other algorithms on six validity indexes in two data clustering cases comprising nine general benchmark datasets and four credit risk assessment datasets. The experimental results suggest that the proposed algorithm significantly outperforms the competing approaches. To further examine the effectiveness of the proposed strategies, two variants of ES-NMPBFO were designed, and all three forms of ES-NMPBFO were tested. The experimental results show that all of the proposed strategies are conducive to the improvement of solution quality, diversity and convergence.     

基于加权聚类集成的标签传播算法

标签传播算法（LPA）是一种高效地处理大规模网络的社区发现算法,由于其近乎线性的时间复杂度而受到广泛关注。然而,该算法每个节点的标签依赖于其邻居节点,其迭代速度和聚类有效性对标签信息的更新顺序非常敏感,影响了社区发现结果的准确性和稳定性。基于该问题,提出了一种基于加权聚类集成的标签传播算法。该算法利用多次标签传播算法的结果作为基聚类集,并用模块度评估每个基聚类的重要性,使其作为节点相似性度量的权值形成加权相似性矩阵,最后通过层次聚类得出最终的社区划分结果。在实验分析中,该算法和其他5个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较,展示了新算法能有效地提高标签传播算法的社区发现精度。     

近邻传播半监督聚类算法的并行计算

提出了一种基于近邻传播的半监督聚类算法的并行算法PSAP,给出了约束的转换过程并结合实例进行说明。在UCI数据集上的实验表明：PSAP算法的运行时间约为SAP算法运行时间的1/8~1/4,聚类结果同时有提高。     

MCEDA: A novel many-objective optimization approach based on model and clustering

To solve many-objective optimization problems (MaOPs) by evolutionary algorithms (EAs), the maintenance of convergence and diversity is essential and difficult. Improved multi-objective optimization evolutionary algorithms (MOEAs), usually based on the genetic algorithm (GA), have been applied to MaOPs, which use the crossover and mutation operators of GAs to generate new solutions. In this paper, a new approach, based on decomposition and the MOEA/D framework, is proposed: model and clustering based estimation of distribution algorithm (MCEDA). MOEA/D means the multi-objective evolutionary algorithm based on decomposition. The proposed MCEDA is a new estimation of distribution algorithm (EDA) framework, which is intended to extend the application of estimation of distribution algorithm to MaOPs. MCEDA was implemented by two similar algorithm, MCEDA/B (based on bits model) and MCEDA/RM (based on regular model) to deal with MaOPs. In MCEDA, the problem is decomposed into several subproblems. For each subproblem, clustering algorithm is applied to divide the population into several subgroups. On each subgroup, an estimation model is created to generate the new population. In this work, two kinds of models are adopted, the new proposed bits model and the regular model used in RM-MEDA (a regularity model based multi-objective estimation of distribution algorithm). The non-dominated selection operator is applied to improve convergence. The proposed algorithms have been tested on the benchmark test suite for evolutionary algorithms (DTLZ). The comparison with several state-of-the-art algorithms indicates that the proposed MCEDA is a competitive and promising approach.