基于增强型kick策略的ILS算法求解一类聚类问题

提出一种新型的基于环交换邻域的迭代局部搜索算法(ILS),用于求解一类聚类问题.算法的主要特点是:1)基于环交换的邻域结构:环交换邻域与传统的Sw ap和Insert邻域相比,算法在一次迭代中允许多个点同时移动;2)针对聚类问题提出了增强型的k ick移动策略:根据每组内点的密度分布摄动聚类中心,对给定的解重新聚类.实验结果表明,基于环交换的迭代局部搜索算法对求解该类聚类问题是有效的.

求解聚类问题的混合粒子群优化算法

建立了聚类分析问题模型,结合遗传算法的思想提出的混合粒子群算法来解决聚类问题。该算法可 进一步改进,思路是利用K-均值方法的结果作为一个粒子。经过比较测试,4种粒子群算法的效果都比较 好,特别是交叉策略A和变异策略B的组合算法最好。

基于混合蛙跳算法的聚类问题研究

混合蛙跳算法(SFLA)是一种基于子群——种群进化模式的群智能优化算法,通过自身特有的分组算子实现不同解的合理分布,能够有效跳出局部最优;局部位置更新算子只对最差解进行更新,加快了算法的收敛速度。针对传统算法在解决聚类问题时存在聚类精度低和算法收敛速度较慢等缺点,本文提出了运用混合蛙跳算法来解决聚类问题,通过采用基于图像二维空间像素特征提取的方法构造青蛙个体解,设计青蛙进化的目标函数和青蛙位置更新策略,并通过数字,图形等验证了该算法解决聚类问题的有效性.

可靠性分析在边坡灰色聚类问题中的应用

选取了"过程降雨量"与"最大地震震级"作为可靠性分析的目标因素,将其可靠度引入到传统BP神经网络预测边坡灰色聚类问题的方法中,将5个典型边坡中的3个作为预测样本,对其余2个进行分析,得到了2个目标因素单独作用于边坡时边坡的可靠度以及在选取的9个因素共同作用下较精确的预测结果。

求解聚类问题的异构蝙蝠算法

为解决蝙蝠算法在较高精度要求下收敛速度慢且易于陷入局部最优等缺陷问题,在蝙蝠算法框架基础上,利用具有良好随机性的Lévy飞行来增强算法的全局搜索能力,结合单纯形法提高算法在局部开采时的性能,提出一种异构的蝙蝠算法。对聚类问题进行解的映射表示并且进行仿真实验。实验数据表明,该算法求解精度高、收敛速度快,具备有效性和可行性,为解决聚类问题提供了可参考的求解算法。

一种针对聚类问题的量子主成分分析算法

聚类问题中的离群点容易影响簇中心的选择,且样本数据量规模的扩大会造成样本点间的距离计算需要消耗大量计算资源.为了解决上述问题,从簇中心选取和最短距离搜索2个方面出发,提出了一种针对聚类问题的新型量子主成分分析算法.利用阈值更新奇异值并得到主成分,再通过势函数得到簇中心,从而减少异常值对簇中心选取的影响.此外,采用量子最小值搜索算法寻找距离样本点最近的簇中心,减少聚类所需迭代次数.以小规模数据集为例,采用Cirq量子编程框架对算法进行电路设计和仿真实验.实验结果表明,该算法与已有的量子聚类算法相比,在聚类准确度上有所提升.性能分析表明,与现有经典和量子算法比较,该算法在簇中心选取和最短距离搜索时间复杂度上有不同程度的改进,消耗资源有所降低.

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题.问题的定义是,给定图G=(V,E),每条边有两类权重,我们需要将点集V进行聚类,目标是最大相同性,即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和.该问题是NP-难的,我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进.算法的分析指出,改进的算法虽然不能将近似比0.75提高,但是对于大多数实例,可以获得更好的运行效果.

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中,单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题,其在线版本为:给定一个度量空间,其中的n个点会一个接一个的到达任何可能的位置,在点到达的时候必须给该点分配一个单位聚类,而此时未来点的相关信息都是未知的,问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题:在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理,接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法,最后证明了这个组合随机算法的期望竞争比不超过1.5。

可靠性分析在边坡灰色聚类问题中的应用

选取了"过程降雨量"与"最大地震震级"作为可靠性分析的目标因素,将其可靠度引入到传统BP神经网络预测边坡灰色聚类问题的方法中,将5个典型边坡中的3个作为预测样本对其余2个进行分析,得到了两个目标因素单独作用于边坡时边坡的可靠度以及在选取的9个因素共同作用下较精确的预测结果,可以为边坡工程提供参考。

近似骨架导向的归约聚类算法

该文针对聚类问题上缺乏骨架研究成果的现状,分析了聚类问题的近似骨架特征,设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是:首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解,通过对局部最优解求交得到近似骨架,将近似骨架固定得到规模更小的搜索空间,最后在新空间上求解。在26个仿真数据集和3个实际数据集上的实验结果表明,骨架理论对提高聚类质量、降低初始解影响及加快算法收敛速度等方面均十分有效。

一种新的基于粒子群算法的聚类方法

建立了聚类分析问题的数学优化模型,提出了一种新的粒子群算法解决聚类问题。对基本粒子群优化算法作了改进,思路是将K-均值方法的结果作为一个粒子和利用新的分类中心调整粒子位置。对Iris植物样本数据的测试结果表明:4种粒子群算法的效果都比较好,特别是第3种改进的粒子群算法的效果更好,粒子群优化聚类技术很有潜力．

基于K均值的迭代局部搜索聚类算法

K均值聚类算法(KM)是解决聚类问题的一个常用的方法,该方法的主要缺点是其找到的局部极小值与全局最优值的偏差往往较大。论文构造一种基于KM算法的迭代局部搜索算法(称之为IKM)。该算法以KM算法所得到的解作为初始解,从该初始解开始作局部搜索,在搜索过程中接受部分劣解。当解无法改进时,算法对所得到的局部极小解做适当强度的扰动后进行下一次的迭代,以跳出局部极小,从而拓展了搜索的范围。试验结果表明IKM算法得到的聚类结果比KM算法得到的聚类结果有明显的改进,平均改进达100%以上。当数据集越大,簇的个数越多时,改进的效果越是显著,可以达到300%以上。因而,IKM算法是一个确实可行的有效的方法。

一种噪声启发式聚类算法

启发式聚类算法的搜索空间中布满了局部极小值"陷阱",从而使得算法容易过早收敛而无法获得高质量聚类结果。文章给出了一种噪声启发式聚类算法NHCA(Noising Heuristic Clustering Algorithm),该算法在搜索空间中增加一组由强至弱的噪声来扩大启发式搜索的局部范围,以保持搜索空间的多样性,达到避免局部极小值影响和提高聚类质量的目的。大量实验结果表明,噪声法对提高启发式聚类算法质量是十分有效的。

基于混合聚类算法的图像分割

本文将像素空间中的图像分割问题转化为特征空间中的数据聚类问题处理,并设计了一种基于遗传算法和模糊c均值算法的混合聚类算法,实现图像分割。实验表明,使用该算法能取得较好的图像分割效果。

聚类准则研究

介绍了聚类误差平方和准则,指出了误差平方和准则的不足,提出了误差绝对值和准则、最大误差准则以及误差p次方和准则。

多元宇宙优化算法应用于聚类分析（英文）

【目的】聚类是数据分析和数据挖掘技术中最重要的概念,其中,k-均值聚类算法是最常用的方法之一。然而,k-均值聚类算法高度依赖于初值,容易陷入局部最优解。为了克服k-均值聚类算法存在的不足,【方法】本研究提出一种利用多元宇宙算法(MVO)解决聚类分析问题的新算法,并进行一些数据集测试实验。【结果】数值模拟实验表明多元宇宙算法解决聚类问题效果优于人工蜂群(ABC)算法,布谷鸟搜索(CS)算法、粒子群优化(PSO)算法等。【结论】在大多数测试数据集的情况下多元宇宙算法解决聚类分析问题具有收敛速度快、聚类精度高和稳定性好的优点。

模糊目标函数聚类算法及其应用

聚类问题 客观对象是由它们的本质属性来确定的,也由它们的属性的异同来进行区分和归类。每一个个别属性可以用一维实数空间来表现,多个属性可用多维实数空间来表现。这样,一个对象就被看作高维空间中的一个点(或向量)。

评“半监督语义动态文本聚类算法”

说起聚类,第一反应是“物以类聚,人以群分”,同类的东西常聚在一起,志同道合的人相聚成群。在聚类问题场景描述中,我们通常认为参与聚类的这些数据是事先存在的、定量的。然而,在现实生活中,数据并不确定,而是动态的、增长的、变化的。

k-平均问题及其变形的算法综述

k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.

簇图编辑问题的研究进展

簇图编辑问题是一个重要的NP-难问题。作为相关性聚类问题的一个特例,它在计算生物等领域有着重要的应用。参数计算理论出现后,参数化的簇图编辑问题逐渐引起了很多人的注意。介绍了求解簇图编辑问题的近似算法、参数算法和它的一些变形,着重分析了参数化簇图编辑问题核心化和FPT算法的最新结果。最后提出了关于该问题的一些研究方向。