作者：
Gao, XiaofangLiang, JiyeShanxi Univ
Coll Comp & Informat Technol Taiyuan 030006 Shanxi Peoples R China Minist Educ
Key Lab Computat Intelligence & Chinese Informat Taiyuan 030006 Shanxi Peoples R China
Manifold learning has become a hot issue in the field of machine learning and data mining. There are some algorithms proposed to extract the intrinsic characteristics of different type of high-dimensional data by perf...
详细信息
Manifold learning has become a hot issue in the field of machine learning and data mining. There are some algorithms proposed to extract the intrinsic characteristics of different type of high-dimensional data by performing nonlinear dimensionality reduction, such as 1SOMAP, LLE and so on. Most of these algorithms operate in a batch mode and cannot be effectively applied when data are collected sequentially. In this paper, we proposed a new incremental version of ISOMAP which can use the previous computation results as much as possible and effectively update the low dimensional representation of data points as many new samples are accumulated. Experimental results on synthetic data as well as real world images demonstrate that our approaches can construct an accurate low-dimensional representation of the data in an efficient manner. (C) 2014 Elsevier B.V. All rights reserved.
Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an effici...
详细信息
Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an efficient algorithm is an outstanding issue. In this paper, we present a simple and practical string matching algorithm. The proposed algorithm is a hybrid that combines our modification of Horspool's algorithm with two observations on string matching. The algorithm scans the text from left to right and matches the pattern from right to left. Experimental results on natural language texts, genomes and human proteins demonstrate that the new algorithm is competitive with practical algorithms.
Face recognition with occlusion is one of the main problems countered in face recognition in practical application. The occlusion in the image will decline the performance of global-based methods, so most of existing ...
详细信息
Face recognition with occlusion is one of the main problems countered in face recognition in practical application. The occlusion in the image will decline the performance of global-based methods, so most of existing methods for this problem are block-based. Our method also divides image into modules. Considering that different modules have different discriminative information, we identify a new criterion to compute modular weight. The modular weight can not only depress the effect of low discriminant module but also can detect the occlusion module to some extent. The weighting function is based on the modular Fisher rate and the modular residual. The successful application of sparse representation-based classification (SRC) in image recognition inspires us to use SRC on the weighted dictionary and test image to perform the final identification. Experiments on the AR and extended Yale B database verify the effectiveness and robustness of the method. (C) 2015 Elsevier B.V. All rights reserved.
Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. ...
详细信息
Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations, in graphs, we obtain a (3 beta/4 + 3 beta(2)/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an insfance of beta-TSP, if it is a complete graph with edge weights c: E(G) -> Q >= 0 that are restricted as follows. For each triple of vertices u, v, w is an element of V (G), c({u, v}) <= beta(c({u, w}) + c ({w, v})). (C) 2015 Elsevier B.V. All rights reserved.
Principal Component Analysis (PCA) is a classical multivariate statistical algorithm for data analysis. Its goal is to extract principal features or properties from data, and to represent them as a set of new orthogon...
详细信息
Principal Component Analysis (PCA) is a classical multivariate statistical algorithm for data analysis. Its goal is to extract principal features or properties from data, and to represent them as a set of new orthogonal variables called principal components. Although PCA has obtained extensive successes across almost all the scientific disciplines, it is clear that PCA cannot incorporate the supervised information such as class labels. In order to overcome this limitation, we present a novel methodology to combine the supervised information with PCA by discriminatively selecting the components. Our method use the fisher criterion to evaluate the discriminative abilities of bases of original PCA and find the first n best ones to yield the new PCA projections. Clearly, the proposed method is general to all PCA family algorithms and even can be applied to other unsupervised multivariate statistical algorithms. Furthermore, another desirable advantage of our method is that it doesn't break the original structure of the PCA components and thereby keeps their visual interpretability. As two examples, we apply our method to incorporate the supervise information with PCA and Robust Sparse PCA (RSPCA) to improve their discriminative abilities. Experimental results on two popular databases demonstrate the effectiveness of our method. (C) 2015 Elsevier B.V. All rights reserved.
Consider a sequence X of n elements, where the number of inversions in X is Inv. We give a simple linear-time transformation that reduces the problem of counting the inversions in X to that of counting inversions with...
详细信息
Consider a sequence X of n elements, where the number of inversions in X is Inv. We give a simple linear-time transformation that reduces the problem of counting the inversions in X to that of counting inversions within disjoint subsequences of X of O(1 + (Inv/n)(2)) elements each. In accordance, we can apply our transformation for counting inversions adaptively in O (n lg (Inv/n))(1) time. Alternatively, if the elements are integers, we achieve a running time of O (n root lg (Inv/n)) in the Word-RAM model of computation. (C) 2015 Elsevier B.V. All rights reserved.
We present a new algorithm for synthesis of reversible circuits using totally controlled Toffoli gates with positive and negative controls. The idea behind our method is to explore properties of the cycle representati...
详细信息
One way to state the Load Coloring Problem (LCP) is as follows. Let G = (V, E) be graph and let f : V -> (red, blue) be a 2-coloring. An edge e is an element of E is called red (blue) if both end-vertices of e are ...
详细信息
One way to state the Load Coloring Problem (LCP) is as follows. Let G = (V, E) be graph and let f : V -> (red, blue) be a 2-coloring. An edge e is an element of E is called red (blue) if both end-vertices of e are red (blue). For a 2-coloring f, let r(f)' and b(f)' be the number of red and blue edges and let mu(f)(G)= min{r(f)', b(f)'}. Let mu(G) be the maximum of mu(f)(G) over all 2-colorings. We introduce the parameterized problem k-LCP of deciding whether mu(G) >= k, where k is the parameter. We prove that this problem admits a kernel with at most 7k. Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width t can be found in time O*(2(t)). We also show that either G is a Yes-instance of k-LCP or the treewidth of G is at most 2k. Thus, k-LCP can be solved in time O*(4(k)). (C) 2014 Elsevier B.V. All rights reserved.
Constantinescu and file [S. Constantinescu, L. Hie. Fine and Wilt's theorem for abelian periods, Bulletin of the European Association for Theoretical Computer Science 89 (2006) 167-170] introduced the notion of an...
详细信息
Constantinescu and file [S. Constantinescu, L. Hie. Fine and Wilt's theorem for abelian periods, Bulletin of the European Association for Theoretical Computer Science 89 (2006) 167-170] introduced the notion of an Abelian period of a word. A word of length n over an alphabet of size sigma can have Theta (n(2)) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n(2) x sigma) using O(n x sigma) space. We present an offline algorithm based on a select function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present online algorithms that also enable us to compute all the Abelian periods of all the prefixes of w. (C) 2013 Elsevier B.V. All rights reserved.
In this paper, we revisit a recent variant of the longest common subsequence (LCS) problem, the string-excluding constrained LCS (STR-EC-LCS) problem, which was first addressed by Chen and Chao (J Comb Optim 21(3):383...
详细信息
In this paper, we revisit a recent variant of the longest common subsequence (LCS) problem, the string-excluding constrained LCS (STR-EC-LCS) problem, which was first addressed by Chen and Chao (J Comb Optim 21(3):383-392, 2011). Given two sequences and of lengths and respectively, and a constraint string of length we are to find a common subsequence of and which excludes as a substring and the length of is maximized. In fact, this problem cannot be correctly solved by the previously proposed algorithm. Thus, we give a correct algorithm with time to solve it. Then, we revisit the STR-EC-LCS problem with multiple constraints We propose a polynomial-time algorithm which runs in time, where and thus it overthrows the previous claim of NP-hardness.
暂无评论