Chameleon算法的改进

结合Chameleon算法可以发现高质量的任意形状、大小和密度的自然簇及一趟聚类算法快速高效的特点,研究可以处理混合属性的高效聚类算法.首先简单改进Chameleon算法,使之可以处理含分类属性的数据;进而提出一种两阶段聚类算法.第一阶段使用一趟聚类算法对数据集进行初始划分,第二阶段利用改进的Chameleon算法归并初始划分而得到最终聚类.在真实数据集和人造数据集上的实验结果表明,提出的两阶段聚类算法是有效可行的.

海上油田群水域应急救援船舶路径规划方法研究

文中提出了基于Dijkstra-ACO算法的海上油田群水域应急救援船舶路径规划方法.根据油田群水域的环境特征,运用Maklink图论算法构建救援船舶路径规划的二维空间模型,并结合Dijkstra算法与ACO算法提出应急救援船舶的路径规划算法,以山东东营油田群水域为例进行模型验证.结果表明:基于Dijkstra-ACO的应急救援船舶路径规划方法优于传统路径规划方法.

Optimization of a Route Network in Dakar Airspace: Surface Navigation

In this paper, the map of a network of air routes was updated by removing the non-optimal routes and replacing them with the best ones. An integer linear programming model was developed. The aim was to find optimal routes in superspace based on performance-based navigation. The optimal routes were found from a DIJKSTRA algorithm that calculates the shortest path in a graph. Simulations with python language on real traffic areas showed the improvements brought by surface navigation. In this work, the conceptual phase and the upper airspace were studied.

基于改进教与学优化算法的最小断点集求解

对继电保护装置开展合理的整定计算工作是保障电网安全稳定运行的重中之重。环网继电保护整定过程中可能出现“死锁”问题导致整定无法进行,需要寻找网络最小断点集(Minimum Break Point Set,MBPS)以解开“死锁”。实际工程中,由于电网运行状态或评价角度的改变,被选作最优断点集的一组MBPS应当更新。针对该问题,致力于寻找一种能够快速高效地找到网络拓扑中尽可能多组MBPS的方法,为更新当前最优断点集提供可能。将寻找MBPS的问题归结为求解一个0-1整数二次规划问题,引入教与学优化算法,并对算法进行一定改进以提升搜索性能。与其他启发式算法相比,该算法只需要设置较少的超参数,可行性较高;并且收敛性好,能够以较少的迭代次数得到全局解;同时,该算法一次独立计算能够得到足够多组MBPS,为在工程实际中结合电网运行参数确定环网最优断点集提供条件。通过算例验证了该方法的有效性。

遗传优化的谱聚类方法研究

传统的谱聚类对初始化数据敏感,聚类结果随不同的初始输入数据而波动。针对上述问题,提出了一种基于遗传算法的谱聚类算法,该算法克服了谱聚类算法对初始数据的敏感性,得到较稳定的聚类结果。与遗传k均值和谱聚类算法相比,该算法在模拟数据和UCI数据集上获得了较好的聚类性能。

面向公共产品平台通用化的聚类分析方法研究

提出了一个平台体系结构的分层构造框架及一种平台元素的获取方式———基于图论的聚类分析方法 (GT BCA) 针对企业现有相似产品进行通用性和标准化分析 ,并以此作为构筑公共平台的基础 ,辅助设计人员对平台进行合理规划和设计 ,从而有效地开发产品族 ,满足大批量定制生产的要求 最后 。

改进的一种图论分割方法在舌像分割中的应用

由于人舌体的特殊性质,从舌像中直接分割舌体时常存在过分割和过合并现象。针对舌像特点提出了一种结合图论分割和多分辨率分割的图像分割算法,用一种图论分割算法让舌像在两种分辨率下分别进行分割,根据两种分割的结果把它们进行交或者并处理,从而有效地分割出舌体。实验结果表明这种方法能够有效避免直接使用图论分割时出现分割过度或者欠分割的情况。

层次聚类算法和基于图的分割算法相融合的图像分割算法

在基于图的分割(graph-based segmentation,GBS)算法的基础上引入层次聚类算法,构造出一种解决GBS算法欠分割的方法,同时采用多线程并行处理数据的方式,有效改善了传统层次聚类算法的处理速度。该方法首先在RGB彩色空间中使用GBS算法得到图像中每个像素点的初始分割结果,然后提取出每一类区域中的像素值,对其进行层次聚类,得到每一类区域中像素值的类别标签,再根据层次聚类所得到的类别标签和预设的类别范围,修改每个像素点的初始分割结果。根据区域合并准则,生成一个新的分割图。经实验表明,该方法与K-means-SLIC算法和GBS算法等相比,很好地解决了欠分割现象,并产生了分割精度较高的语义分割图。

结合图论的供水管网PMA分区方法

供水管网压力分区(PMA)以压力调控为主,兼顾区域计量,可有效地控制城市管网漏失,为此,提出结合图论的PMA分区方法,首先运用自适应AP聚类算法结合经济性计算对供水管网进行初步分区,确定分区数目;然后运用迪杰斯特拉(Dijkstra)算法计算各个聚类中心点到水源的最短路径,确定各个分区的供水管段;建立分区边界优化模型,运用模拟退火算法求解该模型;最后结合人工经验对部分分区进行适当合并,形成最终方案并运用于Y市供水管网实例,取得良好结果.该种分区方法是以计算机算法为主体并结合人工经验,很大程度降低分区的工作量,并且比传统的人工试错分区具有更大的搜索空间,可用于指导实际供水管网的PMA分区.

基于结构-属性的时空对象图聚类算法的研究

在现有的图聚类方法中,大多数聚类方法只关注图的拓扑结构或节点属性而忽略另一方面.为解决这一问题,相关文献中提出了基于图的结构与属性的图聚类方法.但这些聚类方法存在建立的图模型不准确、聚类效果不理想、算法执行效率低等缺点.针对上述图聚类方法中存在的问题,提出了一种基于结构-属性的时空对象图聚类方法(spatio-temporal object graph clustering algorithm based on structure and attribute,STSA).首先提出了属性加权图模型,在此基础上建立了结构-属性的统一度量方法,并采用随机游走模型技术将节点间结构与属性关系转换为相应的相似度矩阵,结合图结构-属性关系及相似度矩阵,采用信息传递算法对图进行聚类,解决了现有图聚类方法中所存在的问题,最后通过实验验证了提出的STSA方法的正确性和有效性.

基于图过滤的快速密度聚类双层网络推荐算法

信息过载问题使得推荐系统迅速发展并广泛应用,同时也出现不法商家将虚假消费记录定量地输入到系统数据库从而改变推荐系统的推荐结果以获利.因此,本文围绕3个问题展开,即:为了提高推荐系统对虚假评论的鉴别能力,首先需要准确标注虚假评论的类标,如何能获取大量准确标定的虚假评论信息;如何有效过滤虚假评论从而提高推荐的可靠性;如何实现一种高效可靠的推荐系统.针对虚假评论信息难以准确标定,本文提出了一种基于文本生成式对抗网络的自动点评技术,依据历史评论文本自动生成虚假评论文本,并依据情感分析确定生成文本的对应评分;为了提高推荐系统对包含虚假信息数据的推荐效果,本文提出了一种基于图过滤的快速密度聚类双层网络推荐算法.该算法首先提出了一种能快速确定节点执行度阈值的基于图的过滤器,有效过滤数据内虚假信息,并设计了一种快速密度聚类双层网络推荐算法,提高推荐效果.将所提出的推荐算法应用到Yelp数据集上展开试验,验证本文提出的推荐方法的有效性.

基于改进图着色理论的聚类算法

为有效解决由于数据规模的不断扩大,图规模显得更加复杂,从而影响聚类效率这一难题,提出了一种新的图着色理论,该理论在图着色理论的基础上进行改进,基本过程为:在运用贪心算法得到的着色图的基础上,重新对已经着色好的顶点进行颜色调整,以期达到更好的聚类效果。利用衡量聚类质量的指标DunnG对聚类结果进行分析。实验结果表明,新算法可达到更高的聚类质量。

中原城市群轨道交通干线选择研究——基于图论最小生成树Kruskal算法

中原城市群的发展是中部崛起的关键所在。中原城市群交通网络中轨道交通干线的构建,必将对其建设与发展起到巨大的推进作用。从计算机学科图论的角度入手,利用Kruskal求解最小生成树算法,对构建最小投资中原城市群快速干线进行了理论性研究。首先用无向图的概念对中原城市群九城市及其间距离进行图的抽象,然后给出算法过程以及实质求解意义并获得结论,最后论述了该算法的不足并对算法的结论进行了现实修正。该算法在油气干线、超高压电力干线等大型基础设施建设中亦存在一定应用前景。

基于蚁群算法的半导体生产线调度方法研究

为了解决具有可重入特性的半导体生产线调度问题,提出基于蚁群算法的半导体生产线调度模型(ASWFSM)。在模型中,利用图论的方法把调度方案的寻优过程转换为蚂蚁对有向图的搜索,并且,引入专家系统作为推理机避免了寻优过程中对可行节点判断的复杂性。仿真试验证明,此模型具有良好的调度效果和稳定性。

基于对象图的事例表示方法及其相似度计算

该文结合电力系统的特点,提出了一种通用的、结构化的事例表示法:对象图表示法。该表示法综合了面向对象技术和图论技术,在表达能力上具有通用性。该文首先给出了对象图的定义,在此基础上给出了相应的相似度计算方法。为解决相似度计算中的组合爆炸问题,引入了模拟退火遗传算法。然后设计了1000组算例以验证算法的有效性。最后,以一个调度运行管理专家系统为例,说明该文提出的事例表示方法具有直观、全面、通用的优点。

基于事件项语义图聚类的多文档摘要方法

基于事件的抽取式摘要方法一般首先抽取那些描述重要事件的句子,然后把它们重组并生成摘要。该文将事件定义为事件项以及与其关联的命名实体,并聚焦从外部语义资源获取的事件项语义关系。首先基于事件项语义关系创建事件项语义关系图并使用改进的DBSCAN算法对事件项进行聚类,接着为每类选择一个代表事件项或者选择一类事件项来表示文档集的主题,最后从文档抽取那些包含代表项并且最重要的句子生成摘要。该文的实验结果证明在多文档自动摘要中考虑事件项语义关系是必要的和可行的。

基于多项式核的结构化有向树数据聚类算法

各个点在数据内部的组织结构中自然地扮演着3种不同的结构性角色,分别是毂、质心和野值.在基于邻域的聚类算法中,邻域密度因子能够识别分离数据集中的毂、质心和野值.但是,邻域密度因子对有噪声和重叠的数据往往失效.为了解决该问题,引入了基于多项式核的邻域密度因子,并在有向树框架下,提出了一种结构化的数据聚类算法,其计算复杂度线性于输入数据的大小.对带有噪声和重叠的数据集,该算法能够找到所有显著的、任意形状的不均衡聚类.在人工和真实数据集上的实验结果都证实了该算法的有效性和快速性.

基于图论Gomory-Hu算法的快速图像分割

Gomory-Hu算法是图论中的经典算法,用于寻找图的最小流割等价树,具有最优解,但是该算法很难处理较大的图像,而且倾向于分割出孤立点集。为此,给出了孤立点的判定方法,并提出一种基于Gomory-Hu算法的图像分割方法。该算法首先通过快速聚类减少图中顶点数目,然后构造新的赋权图,并应用Gomory-Hu算法对图进行最优划分,得到分割结果。提出的算法对多幅自然图像进行了分割实验,平均分割时间在3 s内。实验结果证明了算法的有效性和快速性。

基于网格和图论的初始聚类中心确定算法

针对传统K-means算法随机选取初始聚类中心,易造成准则函数收敛速度慢、聚类结果陷入局部最优等问题,提出一种基于网格和图论的初始聚类中心确定算法。该算法将数据空间网格化,通过在网格单元上形成树的连通分支来选取初始中心点。采用模拟和真实数据集对该算法选取的初始中心进行测试,实验结果表明,改进后的K-means算法在降低时间复杂度、减少迭代次数以及提高聚类精度方面都取到了较好的效果。

蛋白质相互作用网络分析的图聚类方法研究进展

随着可获得的大规模蛋白质相互作用数据的迅速增长,从系统水平上对细胞机制的基本组件和结构的理解成为了一种可能。如今所面临的最大挑战是如何通过分析此类复杂的相互作用数据来反映细胞组织、进程以及功能的规律。基于图理论的聚类方法是分析蛋白质相互作用数据的有效手段。本文将从蛋白质相互作用网络(PPI网络)的图模型、聚类算法、评估方法及应用几个方面描述PPI网络聚类分析的最新研究进展。最后,讨论该方向研究所面临的挑战及进一步的研究方向。