基于特征子图的异构信息网络节点相似性度量

为解决异构信息网络相似性度量的问题,提出了基于节点特征子图的节点相似性度量算法,通过节点特征子图的最大公共子图与最小公共超图之间的差异性,进行节点间的相似性度量.该算法以图理论为基础,根据连边的不同类型设定不同权值,在考虑节点信息相似的同时,加入节点在网络中的结构信息,最大程度地利用了异构信息网络所富含的信息.实验结果表明,提出的算法具有较好的性能和有效性.     

面向距离查询的属性加权图聚集算法

图聚集技术是在保留原始图的结构和属性信息的同时,将一个大规模图聚集成简洁的小规模图的技术.随着图的规模不断增加使得图数据变得难以查询和存储,而基于距离的查询,例如最短路径查询,非常依赖图的规模大小.本文提出了面向距离查询的属性加权图聚集算法,在保证节点之间结构和属性相似的同时,保护了节点之间的距离,并有效地减小了图规模.实验证明本文方法的有效性与在查询任务上的高效性.     

面向非合作目标识别的大规模类属超图建模

 针对大量不同成像条件下获得的多视图像,研究利用局部不变特征及其空间布局约束构建用于非合作目标识别的类属超图模型的方法.该方法首先将每一幅图像表示为使用选定的稳健SIFT特征构成的属性图,然后提出了一种属性图相似性传播聚类原理.在给定的F度量的约束下,利用该原理进行聚类,并根据熵函数最小化优化条件,可迭代得到特定目标属性图样本集合的最优聚类,进一步将所获得的聚类简化成以非冗余属性图作为节点的类属超图模型.本文用大量图像样本进行了试验测试.实验结果验证了模型的可扩展性和识别性能.     

一种ISPD98电路网表到超图的转换算法

以电路测试基准ISPD98的模型用例及对应的超图为例,阐述了ISPD98电路网表文件格式、超图的压缩存储格式和文件存储格式.提出了一种ISPD98电路网表到超图的转换算法.它读取ISPD98电路网表文件数据,将其映射到超图的压缩存储格式,并存储为指定的超图文件存储格式,从而有效地将电路划分问题转换为超图划分优化问题.实验表明,该转换算法能正确地将ISPD98电路网表转换为超图的文件存储格式,有效地避免了直接在ISPD98电路网表上进行划分,提高了电路划分的效率.     

一种度量图像相似性和计算图编辑距离的新方法

 由于在图编辑距离(GED)的计算中合理地为编辑操作定义代价函数相当困难,因此本文提出一种基于图结构的独立于代价函数定义的GED计算方法.它利用边缘方向直方图刻画图的结构,通过计算边缘方向直方图之间的距离来判断图的相异性,从而无需再定义代价函数.Earth Mover’s Distance(EMD)可以准确地计算直方图之间的距离,而且对于图在平面内的旋转所引起的直方图变化具有鲁棒性.为此,本文采用边缘方向直方图之间的EMD计算图编辑距离.将图像用图来表示,利用这种新的图编辑距离度量图像之间的相似性.实验结果表明本文提出的方法可以简单而有效地对图像进行聚类和分类,与基于谱序列计算图编辑距离的方法相比,可以更好地刻画图的结构差异.     

病案数据的XML存储模式研究

分析病案数据的特点,提出了一种基于XML存储半结构化数据的方法,设计并实现了相应存储与解析算法.鉴于OEM模型是一种图状模型,而通常的XML数据模型是树状模型,为此需解决图状模型数据映射为树状模型数据这一关键问题,利用XML元素和属性的语义信息可从语义级别解决该问题.     

基于梯度结构的星载红外图像和全色图像配准方法

针对红外图像与全色图像的不同的成像特性,提出了一种基于图像的梯度结构信息的匹配算法.首先对原始的红外和全色图像分别进行梯度计算,得到图像的梯度强度图;对梯度图进行结构相似性度量,获得图像间同名点对.然后采用RANSAC算法剔除误匹配的同名点.最后利用同名点对构建三角网小面元,并进行变换而得到配准图像.实验结果表明,算法可以有效地利用红外图像中地物的结构信息,匹配精度高.     

基于过程结构树的流程间差别检测算法

流程模型差别检测是业务流程管理的关键技术之一.针对流程模型大多是由图结构建模,而流程图模型中有多种类型节点,因此经典的图编辑距离方法无法直接应用于流程差别检测的问题,提出了基于过程结构树的流程间差别检测算法.算法首先将流程模型转化为基于任务节点的过程结构树;然后采用分治思想快速获得流程间的最佳对等节点映射集合;最后基于节点映射集合生成一个近似最小代价编辑操作序列来表示两个流程的差别.实验结果表明,本文算法在准确率和效率两方面都能满足实际的应用需求.     

基于超图正则化受限的概念分解算法

针对概念分解(Concept Factorization, CF)算法没有同时考虑样本中存在的类别信息及数据间多元几何结构信息的问题,该文提出一种基于超图正则化受限的概念分解(Hyper-graph regularized Constrained Concept Factorization, HCCF)算法。HCCF算法通过构建一个无向加权的拉普拉斯超图正则项,提取数据间的多元几何结构信息,克服了传统图模型只能表达数据间成对关系的缺陷;同时采用硬约束的方式使样本的类别信息在低维空间中保持一致,充分利用了标记样本的类别信息。该文采用乘性迭代的方法求解HCCF算法的目标函数并证明了其收敛性。在TDT2库、Reuters库和PIE库上的实验结果表明,HCCF算法提高了聚类的准确率和归一化互信息,验证了算法的有效性。     

加权SimRank算法在超常规用药检测中的应用

异常医疗数据的挖掘是一个很有价值的领域,针对就诊时用药的规律性,在图结构的相似度算法SimRank的基础上提出了加权SimRank(WSimRank),并基于WSimRank算法提出了用药异常的检测模型。该模型利用WSimRank算法挖掘药品相似性,对相似的药品构建使用时长的交集,以此构造用药规则库,将待检用药行为与规则库进行比对从而确定异常。实验结果显示,在检测用药异常时,WSimRank算法的各项评价指标都比原始的SimRank算法更优秀。     

基于整数线性规划重构抽象语义图结构的语义摘要算法

针对利用抽象语义(AMR)图来预测摘要子图存在的语义结构不完整问题,该文提出一种基于整数线性规划(ILP)重构AMR图结构的语义摘要算法。首先将数据预处理生成一个AMR总图;然后基于统计特征从AMR总图中抽取出摘要子图重要节点信息;最后利用ILP的方法来对摘要子图中节点关系进行重构,利用完整的摘要子图恢复生成语义摘要。实验结果表明,相比其他语义摘要方法,所提方法的ROUGE值和Smatch值都有显著提高,最多分别提高了9%和14%,该方法有利于提高语义摘要的质量。     

一种改进的分布式最大权独立集算法

能快速准确寻找给定图中的最大权独立集的分布式算法,对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架,假设所有节点了解自己邻居节点之间的局部拓扑信息,启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明,所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求,且权和性能优于已有的分布式算法。     

基于均值漂移滤波及谱分类的海面舰船红外目标分割

提出了一种有效的海面舰船红外目标分割方法.利用均值漂移方法的不连续保持性滤波特性,滤除海面的强杂波干扰,同时又不损失舰船目标的信息.根据滤波得到的区域构建区域邻接图,采用基于最大最小SST图划分算法对区域邻接图的节点进行划分.划分结果最终将图像分为天空背景、海面背景以及舰船目标3个部分.由于采用区域节点来表征图像,较之采用原始图像象素节点表示,其节点个数大大减少,从而使算法的计算效率得到很大提高.实验结果也表明提出两步算法具有优越的性能,能够在海面强杂波干扰的情况下有效提取舰船红外目标.     

时间约束NMF算法及其在脑动态功能网络降维中的应用

为了保证高维数据中的时间属性在降维过程中得以保持,提出了一种时间约束非负矩阵分解算法（Time constraint Non-negative Matrix Factorization,TNMF）。该算法通过融合时间序列信息、数据维度,分解误差等约束条件,共同构建时间属性约束模型,计算最优基矩阵维度,能在降维的同时最大限度地保留原始高维数据的空间结构和时间序列信息。将其用于脑动态功能网络降维的实验结果表明,该算法在时间特征提取、聚类可视化效果和聚类指标上明显优于目前常用的降维聚类算法。      

一种基于实体描述和知识向量相似度的跨语言实体对齐模型

跨语言实体对齐旨在找到不同语言知识图谱中指向现实世界同一事物的实体.传统的跨语言实体对齐方法通常仅依靠知识图谱内部的结构信息,但实际上一些知识图谱提供的实体描述信息也可以被利用.本文提出了一种结合知识图谱的内部结构和实体描述信息共同进行跨语言实体对齐的模型.该模型首先通过训练基于知识图谱结构信息的知识向量找到可能被对齐的实体对,再结合实体描述信息利用改进后的共享参数模型选出最终的对齐实体,最后通过迭代对齐的方法重复前两个步骤找到更多的对齐实体直到训练结束.实验结果表明,与基准算法相比,本文所提模型在跨语言实体对齐任务上可以取得相对不错的结果.     

基于频繁闭图的图包含查询算法

 交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.     

基于图论的单线激光雷达数据匹配方法

针对传统的基于单线激光雷达的匹配方法在多障碍物环境下匹配精度低的问题,提出了一种基于图论的匹配方法。该方法从数据点集中提取出具有凹凸性质的特征点,提取对应的线段并构建属性图模型,将点集配准问题转化为属性图匹配问题。与传统的基于线段的匹配算法相比,所提方法基于图模型引入了更多的线段之间的几何关系,使算法可以适用于多障碍物环境以及动态多障碍物环境;与传统的基于点的匹配方法相比,该方法依据特征点组成的线段进行几何意义上的匹配,通过属性图模型快速找到局部观测数据与全局数据的最佳匹配,提升了运算效率,同时也避免了传统方法易陷入局部最优解的缺点。     

Single-step creation of localized Delaunay triangulations

A localized Delaunay triangulation owns the following interesting properties for sensor and wireless ad hoc networks: it can be built with localized information, the communication cost imposed by control information is limited, and it supports geographical routing algorithms that offer guaranteed convergence. This paper presents two localized algorithms, fast localized Delaunay triangulation 1 (FLDT1) and fast localized Delaunay triangulation 2 (FLDT2), that build a graph called planar localized Delaunay triangulation, PLDel, known to be a good spanner of the Unit Disk Graph, UDG. Our algorithms improve previous algorithms with similar theoretical bounds in the following aspects: unlike previous work, FLDT1 and FLDT2 build PLDel in a single communication step, maintaining a communication cost of O(n log n), which is within a constant of the optimal. Additionally, we show that FLDT1 is more robust than previous triangulation algorithms, because it does not require the strict UDG connectivity model to work. The small signaling cost of our algorithms allows us to improve routing performance, by efficiently using the PLDel graph instead of sparser graphs, like the Gabriel or the Relative Neighborhood graphs.     

基于采样的大规模图聚类分析算法

针对当前聚类方法（例如经典的GN算法）计算复杂度过高、难以适用于大规模图的聚类问题，本文首先对大规模图的采样算法展开研究，提出了能够有效保持原始图聚类结构的图采样算法（Clustering-structure Representative Sampling，CRS），它能在采样图中产生高质量的聚类代表点，并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次，提出快速的整体样本聚类推断（Population Clustering Inference，PCI）算法，它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率，能够很好地完成大规模图的聚类任务.