图的色数问题研究（续）

进一步研究发现,“图的色数问题研究”一文中的“算法”,实际上是构造图的着色方案的一种算法,也可能得到图的色数,也可能是一种近优值。为了完善该算法,在对不同的最大独立点集进行比较分析后,归纳出存在有多个最大独立点集时,从中选取色数分块的选优准则,并对最大独立点集的有关性质定理作了证明,从而使图的色数算法得以完善。     

一种海量数据快速聚类算法

为满足海量数据处理要求,提出了一种基于网格的K-means快速聚类算法（SPGK）.设计基于网格质心的聚类簇个数选取算法,对数据进行网格划分得到每个网格的质心,将质心作为K-means聚类的样本点,从而减少K-means的欧氏距离计算次数.该算法基于Spark平台实现并行计算,进一步地提高了算法的运行效率.SPGK不但能够获得良好的聚类效果,而且缩减了欧氏距离计算次数,适用于海量数据的快速聚类.在千万级数据集上的实验结果表明,SPGK的性能明显优于现有的K-means++和基于K均值聚类的递归划分方法.     

改进的关联规则并行算法

针对并行关联规则挖掘算法不能有效的解决负载平衡的问题,在CD算法的基础上,介绍了一种基于动态数据集划分的并行关联规则挖掘算法.它根据各个节点的反馈来决定向每个节点分配的数据集大小.与静态的数据集划分相比,它能更好地实现负载平衡,提高并行数据挖掘的效率.     

基于mean shift和图结构的GMPHD扩展目标跟踪

针对当前扩展目标跟踪算法中,量测划分数过多、计算量过大,目标交叉时刻易产生漏估等问题,提出一种基于mean shift和图结构的GMPHD扩展目标跟踪算法。首先,引入核密度估计剔除杂波量测;其次,采用mean shift算法对扩展目标量测集进行划分,并依据图结构更新后反馈回的信息判断是否需要进行子划分;然后,采用扩展目标GMPHD算法进行滤波处理;最后,对滤波结果进行一步预测,更新图结构,并使用更新后的图结构信息指导下一时刻的量测划分。matlab仿真表明,所提算法大幅减少了量测划分数,降低了运算量,解决了扩展目标交叉时刻的漏估问题。     

基于基因表达式编程的自动聚类方法

为了解决聚类算法不能自动聚类的问题,提出并实现了自动聚类算法GEP-Cluster算法。主要工作包括:1)研究了基于GEP进化的最优簇划分;2)提出了自动合并簇算法Auto Merge Cluster Algorithm;3)实现了不需预知簇个数的聚类;4)在合成数据集上的实验表明,采用GEP-Cluster算法在未知簇划分信息的情况下可对数据集自动进行聚类分析,聚类成功率达到96%。     

中国老鼠问题与G（p，q，f）的4着色

提出了中国老鼠问题.阐明了求解中国老鼠问题的基本思路.发现了基于森林Fi分解的对偶图的顶点4着色方法.提出了森林Fi分解的三种方法.介绍了对偶图G(p,q,f)的A区和B区的划分,森林Fi的分解,以及对偶图G′(f,q,p)的H路径Pi的分解和G(p,q,f)的顶点4着色.讨论了H路径Pi的个数,森林Fi的个数.G(p,q,f)的4着色方案数及A区和B区的划分方案数.     

适用于复杂结构的多路谱聚类算法的改进

为使多路谱聚类方法对复杂结构数据集有效地聚类,根据矩阵扰动理论,利用局部近邻关系更新谱聚类算法(NJW)中的初始相似度矩阵,得到最终的亲和矩阵.理论分析表明,数据集可划分时,该矩阵是理想块矩阵或接近理想块矩阵,保证了本文算法聚类划分的正确性.将本文算法和基于路径的谱聚类、密度敏感的谱聚类以及基于流平面排序的谱聚类进行了比较,结果表明,本文算法在数据集具有复杂分布结构时可以确定聚类个数,得到正确的聚类结果.进一步将本文算法用于真实数据集上的聚类分析,表明本文算法是有效的.     

基于关联图的频繁闭模式挖掘

将关联图的数据挖掘思想应用到频繁闭模式的挖掘中,使用位向量的技术简化项集支持度的计算,构造关联图表示项集间的频繁关系.在此基础上,提出一种频繁闭模式挖掘算法,针对频繁闭模式的特点,结合剪枝策略、子集检测策略、搜索策略等技术手段,优化算法性能.实验结果表明,该算法在时间性能上优于经典的频繁闭模式算法CLOSET.     

卷积记忆图协同过滤

针对推荐系统中用户和项目的向量表示问题,提出了一种端到端的具有记忆单元的图神经网络.在图神经网络中引入门控循环单元解决高阶连通节点间信息损失问题,可以使得用户和项目节点从高阶邻居获得更加完整的特征信息,然后利用卷积神经网络对网络输出层间的特征向量进行融合以获得不同阶段下用户的偏好.实验结果表明,与最优对比算法相比,采用所提卷积记忆图协同过滤推荐算法在4个数据集上的评分预测性能分别提升了1.98%,4.17%,9.27%和2.70%.     

一类复映射分形生成算法与分形图重构

就经典M-J集或广义M-J集的构造算法进行了较详细的探讨.实验表明所提出的区域分裂逃逸时间算法具有普适性,并能较大地提高M分形图构图速度,成倍减少成图时间.利用周期函数调制复动力系统,构造整体有序而局部混沌的分形图,展示周期复现分形图的结构特征、整体的周期性和局部的无限细节.     

基于蚁群系统的聚类算法研究

针对传统聚类算法在对复杂密集型数据集聚类时不能取得较好聚类结果的问题,利用进化聚类算法对复杂密集型数据集进行聚类,提出一种基于蚁群系统的聚类算法(clustering algorithm based on ant colony system,CAACS),利用蚂蚁在行进路径中释放信息素且追求浓信息素的原理来实现蚂蚁的随机搜索,并引入近邻函数值的概念来确定样本数据之间的相似性,通过蚂蚁在行走过程中不断建立样本数据之间的最相似连接来形成各个子连通图,各个子连通图中的样本数据构成一个类。实验采用随机产生的不规则数据集以及一系列合成的数据集将CAACS算法与DBSCAN算法(density-based spatial clustering of application with noise)及面向非规则非致密空间分布数据的蚁群聚类方法进行比较。实验结果表明CAACS算法对复杂密集型数据集能达到较好的聚类结果。     

并行最小割算法及其在金融社交网络中的应用

有效实施金融监管已成为金融健康发展的必要保证. 若能够在金融社交网络中,找到一部分承载网络中所有信息流动的关键节点,便能实现整个金融社交网络的有效监管. 金融社交网络图规模通常较大,须开发大规模图处理并行算法. 本文提出基于分布式图处理平台Pregel的并行最小割算法. 实验基于Apache Spark平台开展,所用数据均来自BoardEx数据库. 实验结果表明,在大规模社交网络图的处理中,该算法具有良好性能. 利用该并行算法得到金融社交网络图的最小割,便可有效实施金融监管.     

平面测试问题的一种新型的神经网络算法

给出了平面测试问题的一种新型的神经网络算法。该算法不仅能够测试可平面图、寻找非平面的最大可平面子图，而且能够把一个可平面图嵌入在一条直线上。并通过实验验证了算法的可行性。这个算法可用于印刷板电路及大规模集成电路的布线。     

一类超大规模集成电路分割算法的改进

提出了一个超大规模集成电路分割算法 ,从流图中最小截之间的等价关系出发 ,寻找新的电路割集 .与同类分割算法 ,如FBB算法、DMC算法相比 ,新算法充分利用了流图拓扑结构的特点 ,分割结果更好 .     

无向赋权图最短通路的矩阵算法

Dijkstra算法是求赋权图最短通路中最著名的算法.但其数学的表达式却非常复杂,而且只求出起点到各点的最短通路的权.通过对赋权图进行矩阵定义以及定义相应的矩阵运算法则,就可以求出任意两点间的最短通路的权.这一算法为求赋权图的最短通路及权的编程提供了算法模型.     

基于等距随机游走图的三维动态曲面对准

为了提高三维动态曲面在噪声和遮挡下的对准精度,提出时空等距随机游走图算法. 该算法根据相邻两帧采样点的乘积空间定义图节点,通过时空相邻性进行节点裁剪处理. 以测地距离定义图边约束,将等距映射转化为图稳定性节点选择的随机游走问题. 通过马尔可夫链理论,计算得到最终的对应结果. 通过对不同动态曲面数据库的实验分析表明,该算法针对具有明显噪声和空洞的三维动态曲面能够得到一致性对准关系,性能优于已有算法.     

基于改进易辛模型的图加密新算法

直接设计对于图的加密算法比较困难,为此,提出了2种解决方案.一是借鉴二维易辛模型简单高效和局部化的优点;二是将图的加密问题转换成较简单问题的组合.通过改进基本的易辛模型设计了用于一维数据、二维数据、树结构的加密算法,最终实现了图的加密.分析和实验结果表明,该方法可以实现图加密所要求的可逆性、多样性、高效性、随机性和扩散性等.     

一种新的最短路径算法

定义了有向图的代价邻接矩阵和最短路径矩阵,给出了称为"乘位加比小"的一种代价邻接矩阵间的新运算。基于该矩阵运算,证明了一种称为"代价邻接矩阵乘位加比小算法"新的最短路径算法。其结果可实现有向图全局最短寻径,并且对于任意类型的有向图,总是可准确求得其最短路径。E.W.Dijkstra提出的标号法是一种公认的求最短路径的较好算法,但在某些情况下寻径结果并非最优,文中提出的新算法克服了其缺点。     

基于表象式语义网络的图匹配算法

提出了一种在表象式语义网络中的查找方法,表象式语义网络问题的求解一般都是通过图匹配实现的,首先根据待求解的问题的要求构造一个带变量节点的语义网络,然后与计算机视觉系统中己存储的语义网络进行图匹配。当语义网络中的询问部分与系统中的语义网络图匹配后,则与询问部分匹配的事实就是问题的解。图匹配问题可以通过构造一个图的附属数据结构来完成,这个附属数据结构也称为相连图(association graph),对于两个图G=(V,A)以及G′=(V′,A′),构造相联图G″=(V″,A″),也就是说,V″是所有可能节点匹配对的集合,A″是所有相容节点匹配的集合。这相当于在相联图中寻求一个最大的基团(clique),其中基团定义为G″的完全连通的一个子图。最大基团满足其节点集合不是任何其他基团节点集的适当子集。