加权分治与皇冠技术求解最大加权独立集

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度。针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法。     

基于最大主子图分解的贝叶斯网络等价类学习算法

针对基于约束方法学习贝叶斯网络(BN)结构的不足,以及随着条件集的增大,利用统计方法进行条件独立(CI)测试不稳定等问题,提出一种基于最大主子图分解(MPD)的BN等价类学习算法.该算法首先通过MPD分解技术对BN的道德图进行分解;然后利用0阶和1阶CI测试识别部分子图中的V结构,对于初步未定的V结构利用局部评分搜索确定,从而避免了冗余检验,有效地减小了条件集的维数,并且提高了算法的效率.理论证明和实验结果均表明了所提出算法的有效性和合理性.     

局部敏感非负矩阵分解

非负矩阵分解是一种新的基于部分学习的矩阵分解方法,反映了人类思维中局部构成整体的概念。算法只将非负矩阵近似地分解成两个非负矩阵的积,忽略了数据几何结构和判别信息。提出了一个局部敏感非负矩阵分解降维算法来克服这一缺点。该算法既保持了数据非负性,又保持了数据的几何结构和判别信息。构造了一个有效的乘积更新算法并且在理论上证明了算法的收敛性。ORL和Yale人脸数据库实验表明该算法性能超过许多已存在的方法。     

基于PS-EM算法和BP神经网络的影响图模型选择

影响图模型选择中存在数据依赖性、计算复杂性和非概率关系问题.通过对影响图结构进行分解,提出PS-EM算法对影响图的概率结构部分进行模型选择.给出一种BP神经网络,通过对局部效用函数的学习实现效用结构部分的模型选择,并引入权重阈值来避免过拟合.PS-EM算法是在SEM算法中引入一种融合先验知识的MDL评分标准来降低传统MDL评分对数据的依赖性,并通过将参数学习和结构评分分开计算提高计算效率.算法比较的结果显示PS-EM比标准SEM的时间性能好、对数据依赖性小,且效用部分的结构选择易于实现.     

基于图正则化的半监督非负矩阵分解

提出了一种基于图正则化的半监督非负矩阵分解算法（GSNMF）,克服了非负矩阵分解（NMF）、约束非负矩阵分解（CNMF）和图正则化非负矩阵分解（GNMF）方法忽略样本数据的局部几何结构或标签信息不足的缺陷,且NMF、CNMF和GNMF均为GSNMF的特例。也从理论上证明了GSNMF算法的收敛性。该算法对样本数据进行低维非负分解时,在图框架下既保持数据的几何结构,又利用已知样本的标签信息,在进行半监督学习时,同类样本能更好地聚集而类间距离尽可能大。在人脸数据库ORL、FERET和手写体数据库USPS上的仿真结果表明,相对于NMF及其一些改进算法,GSNMF均具有更高的聚类精度。     

抗强剪切和涂抹攻击零水印算法

为了增强现有水印算法抵抗存在信息量丢失的各种攻击(如剪切、涂抹、行列移除等),提出一种基于NMF(Non-negative factorization)和Radon变换不变矩抗强剪切和涂抹攻击零水印算法。算法首先将原始图像V矩阵进行非负矩阵分解(NMF)得到基矩阵W和系数矩阵H。由NMF部分感知全局的特性可知,利用部分V矩阵图像信息和对应的系数矩阵H可以重构出完整的W矩阵;然后计算非负矩阵分解后W矩阵的Radon变换不变矩,最后利用有限个Radon变换不变矩来设计和构建零水印信息。实验结果表明:当剪切和涂抹的面积达到87.5%时,水印检测正确率为100%,同时对于加噪、滤波、JPEG压缩等攻击,该算法也具有良好的鲁棒性。     

一种基于结构分解的影响图模型选择算法

针对概率网络模型选择的数据依赖性和计算复杂性,以及影响图模型的非概率关系学习问题,通过对影响图结构进行分解,提出一种PS-EM算法实现影响图概率结构部分的模型选择,给出一种利用BP神经网络学习每个效用结点的局部效用函数来实现效用结构部分的模型选择方法。PS-EM算法对N．Firedman的SEM算法进行改进,提出一种引入融合先验知识的MDL评分标准来降低传统MDL评分对数据的依赖性;通过将参数学习和结构评分分开计算提高计算效率。最后,在石油投机商模型上的结果显示,PS-EM比SEM的时间性能要好,对数据依赖性要小,且效用部分的结构选择易于实现。     

线性投影非负矩阵分解方法及应用

针对线性投影结构非负矩阵分解迭代方法比较复杂的问题,提出了一种线性投影非负矩阵分解方法.从投影和线性变换角度出发,将Frobenius范数作为目标函数,利用泰勒展开式,严格导出基矩阵和线性变换矩阵的迭代算法,并证明了算法的收敛性.实验结果表明:该算法是收敛的;相对于非负矩阵分解等方法,该方法的基矩阵具有更好的正交性和稀疏性;人脸识别结果说明该方法具有较高的识别率.线性投影非负矩阵分解方法是有效的.     

广义二型模糊逻辑系统降型及其采样离散Nie-Tan算法

广义二型模糊逻辑系统在近年来成为学术研究的热点问题,而降型是该系统中的核心模块。最近的研究证明了连续Nie-Tan(CNT)算法是计算区间二型模糊集质心的准确方法。发现了离散Nie-Tan(NT)算法中的求和运算和CNT算法中的求积分运算的内在联系,用2类算法完成基于广义二型模糊集α-平面表达理论的广义二型模糊逻辑系统质心降型。3个计算机仿真实验表明,当适当增加主变量采样点个数时,所提出的基于主变量采样的离散NT算法计算出的广义二型模糊逻辑系统质心降型集和解模糊化值结果可以精确地逼近基准的CNT算法,且采样离散NT算法的计算效率远远高于CNT算法的效率。     

基于L21范式的多图正则化非负矩阵分解方法

针对非负矩阵分解方法对原始数据的单图约束导致的结果未知性大、满足需求单一,以及大多非负矩阵分解方法存在对噪声、离群点较敏感导致的稀疏度和鲁棒性较差等问题,提出基于L21范式的多图正则化非负矩阵分解方法。采用L21范式,提升分解结果的稀疏度和鲁棒性。构建多图约束的算法模型更好地保持数据的流形结构。构建目标函数并给出乘性迭代规则。通过在多个数据库上的实验表明,该方法在识别效果上有明显的提升。     

Optimal Graph Constraint Reduction for Symbolic Layout Compaction

The compaction problem in VLSI layout can be formulated as a linear program. To reduce the execution time and memory usage in compaction, it is important to reduce the size of the linear program. Since most constraints in compaction are derived directly or indirectly from physical separation and electrical connectivity requirements which can be expressed in the form of graph constraints, we study the graph constraint reduction problem. That is the problem of producing, for a given system of graph constraints, an equivalent system with the fewest graph constraints. After observing that the problem as previously formulated is NP-hard and overrestrictive in that the maximum possible reduction is not always attainable, we propose a new formulation in which the maximum possible reduction is guaranteed. We further present a polynomial-time algorithm for the new formulation. Received September 13, 1994; revised December 4, 1995.     

Saving Space by Fully Exploiting Invisible Transitions

Checking that a given finite state program satisfies a linear temporal logic property suffers from the state explosion problem. Often the resulting lack of available memory is more significant than any time limitations. One way to cope with this is to reduce the state graph used for model checking. We present an algorithm for constructing a state graph that is a projection of the program's state graph. The algorithm maintains the transitions and states that affect the truth of the property to be checked. Especially in conjunction with known partial order reduction algorithms, we show a substantial reduction in memory over using partial order methods alone, both in the precomputation stage, and in the result presented to a model checker. The price of the space reduction is a single additional traversal of the graph obtained with partial order reduction. As part of our space-saving methods, we present a new way to exploit Holzmann's Bit Hash Table, which assists us in solving the revisiting problem.     

Crown Structures for Vertex Cover Kernelization

Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.     

基于扩展门限的软件水印研究与实现

AB算法的门限方案原本用于密钥分存,不限制子密钥的强度,从而导致水印数据扩张,而扩展门限定义可限制子密钥的数据位宽。为此,提出基于扩展门限的水印算法,采用动态图方法在Java平台实现水印系统。实验结果证明,该水印算法能有效控制水印数据扩张,加快水印恢复速度,适于构建方便实用的软件水印系统。     

完全支配集的规约算法

完全支配集是一个著名的NP难解问题,在无线传感器网络中具有重要应用。主要研究了能降低问题规模的规约化算法设计。通过对问题结构进行深入分析并对图中顶点进行着色,得到图中顶点之间的新的组合特性,在此基础上提出一系列高效的多项式时间的局部规约规则。证明了规约规则的正确性,并通过仿真实验验证了规约规则的有效性。     

Z-H算法正确性证明第四次改写

提出多级图简单路径求解问题,我们称之为MSP问题。给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性。最后通过将HC问题（哈密顿图判定问题）多项式归结成MSP问题,证明MSP问题的NP完全性质。本文极大地简化文献[6,7]中αβ引理的证明,特别是对证明过程中的各种情形进行分割,将一个巨大的证明分成系列引理。     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

Tensor rank one differential graph preserving analysis for facial expression recognition

This paper presents a new dimensionality reduction algorithm for multi-dimensional data based on the tensor rank-one decomposition and graph preserving criterion. Through finding proper rank-one tensors, the algorithm effectively enhances the pairwise inter-class margins and meanwhile preserves the intra-class local manifold structure. In the algorithm, a novel marginal neighboring graph is devised to describe the pairwise inter-class boundaries, and a differential formed objective function is adopted to ensure convergence. Furthermore, the algorithm has less computation in comparison with the vector representation based and the tensor-to-tensor projection based algorithms. The experiments for the basic facial expressions recognition show its effectiveness, especially when it is followed by a neural network classifier.     

A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

The probabilistic packet marking (PPM) algorithm is a promising way to discover the Internet map or an attack graph that the attack packets traversed during a distributed denial-of-service attack. However, the PPM algorithm is not perfect, as its termination condition is not well defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the rectified PPM (RPPM) algorithm. The most significant merit of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct, with a specified level of confidence. We carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising means of enhancing the reliability of the PPM algorithm.