Cluster formation in a time-varying multi-agent system

We introduce time-varying parameters in a multi-agent clustering model and we derive necessary and sufficient conditions for the occurrence of clustering behavior with respect to a given cluster structure. For periodically varying parameters the clustering conditions may be formulated in a similar way as for the time-invariant model. The results require the individual weights assigned to the agents to be constant. For time-varying weights we illustrate with an example that the obtained results can no longer be applied.     

Pattern matching in the Hamming distance with thresholds

It has long been known that pattern matching in the Hamming distance metric can be done in time, where n is the length of the text, m is the length of the pattern, and Σ is the alphabet. The classic algorithm for this is due to Abrahamson and Kosaraju. This paper considers the following generalization, motivated by the situation where the entries in the text and pattern are analog, or distorted by additive noise, or imprecisely given for some other reason: in any alignment of the pattern with the text, two aligned symbols a and b contribute +1 to the similarity score if they differ by no more than a given threshold θ, otherwise they contribute zero. We give an time algorithm for this more general version of the problem; the classic Hamming distance matching problem is the special case of θ=0.     

A novel multiset integrated canonical correlation analysis framework and its application in feature fusion

Multiset canonical correlation analysis (MCCA) is difficult to effectively express the integrated correlation among multiple feature vectors in feature fusion. Thus, this paper firstly presents a novel multiset integrated canonical correlation analysis (MICCA) framework. The MICCA establishes a discriminant correlation criterion function of multi-group variables based on generalized correlation coefficient. The criterion function can clearly depict the integrated correlation among multiple feature vectors. Then the paper presents a multiple feature fusion theory and algorithm using the MICCA method. The detailed process of the algorithm is as follows: firstly, extract multiple feature vectors from the same patterns by using different feature extraction methods; then extract multiset integrated canonical correlation features using MICCA; finally form effective discriminant feature vectors through two given feature fusion strategies for pattern classification. The multi-group feature fusion method based on MICCA not only achieves the aim of feature fusion, but also removes the redundancy between features. The experiment results on CENPARMI handwritten Arabic numerals and UCI multiple features database show that the MICCA method has better recognition rates and robustness than the fusion methods based on canonical correlation analysis (CCA) and MCCA.     

A time-efficient pattern reduction algorithm for k-means clustering

This paper presents an efficient algorithm, called pattern reduction (PR), for reducing the computation time of k-means and k-means-based clustering algorithms. The proposed algorithm works by compressing and removing at each iteration patterns that are unlikely to change their membership thereafter. Not only is the proposed algorithm simple and easy to implement, but it can also be applied to many other iterative clustering algorithms such as kernel-based and population-based clustering algorithms. Our experiments—from 2 to 1000 dimensions and 150 to 10,000,000 patterns—indicate that with a small loss of quality, the proposed algorithm can significantly reduce the computation time of all state-of-the-art clustering algorithms evaluated in this paper, especially for large and high-dimensional data sets.     

From classifiers to discriminators: A nearest neighbor rule induced discriminant analysis

The current discriminant analysis method design is generally independent of classifiers, thus the connection between discriminant analysis methods and classifiers is loose. This paper provides a way to design discriminant analysis methods that are bound with classifiers. We begin with a local mean based nearest neighbor (LM-NN) classifier and use its decision rule to supervise the design of a discriminator. Therefore, the derived discriminator, called local mean based nearest neighbor discriminant analysis (LM-NNDA), matches the LM-NN classifier optimally in theory. In contrast to that LM-NNDA is a NN classifier induced discriminant analysis method, we further show that the classical Fisher linear discriminant analysis (FLDA) is a minimum distance classifier (i.e. nearest Class-mean classifier) induced discriminant analysis method. The proposed LM-NNDA method is evaluated using the CENPARMI handwritten numeral database, the NUST603 handwritten Chinese character database, the ETH80 object category database and the FERET face image database. The experimental results demonstrate the performance advantage of LM-NNDA over other feature extraction methods with respect to the LM-NN (or NN) classifier.     

A fast pattern matching algorithm with multi-byte search unit for high-speed network security

A signature-based intrusion detection system identifies intrusions by comparing the data traffic with known signature patterns. In this process, matching of packet strings against signature patterns is the most time-consuming step and dominates the overall system performance. Many signature-based network intrusion detection systems (NIDS), e.g., the Snort, employ one or multiple pattern matching algorithms to detect multiple attack types. So far, many pattern matching algorithms have been proposed. Most of them use single-byte standard unit for search, while a few algorithms such as the Modified Wu-Manber (MWM) algorithm use typically two-byte unit, which guarantees better performance than others even as the number of different signatures increases. Among those algorithms, the MWM algorithm has been known as the fastest pattern matching algorithm when the patterns in a rule set rarely appear in packets. However, the matching time of the MWM algorithm increases as the length of the shortest pattern in a signature group decreases.In this paper, by extending the length of the shortest pattern, we minimize the pattern matching time of the algorithm which uses multi-byte unit. We propose a new pattern matching algorithm called the L⁺¹-MWM algorithm for multi-pattern matching. The proposed algorithm minimizes the performance degradation that is originated from the dependency on the length of the shortest pattern. We show that the L⁺¹-MWM algorithm improves the performance of the MWM algorithm by as much as 20% in average under various lengths of shortest patterns and normal traffic conditions. Moreover, when the length of the shortest pattern in a rule set is less than 5, the L⁺¹-MWM algorithm shows 38.87% enhancement in average. We also conduct experiments on a real campus network and show that 12.48% enhancement is obtained in average. In addition, it is shown that the L⁺¹-MWM algorithm provides a better performance than the MWM algorithm by as much as 25% in average under various numbers of signatures and normal traffic conditions, and 20.12% enhancement in average with real on-line traffic.     

A structure-preserved local matching approach for face recognition

In this paper, a novel local matching method called structure-preserved projections (SPP) is proposed for face recognition. Unlike most existing local matching methods which neglect the interactions of different sub-pattern sets during feature extraction, i.e., they assume different sub-pattern sets are independent; SPP takes the holistic context of the face into account and can preserve the configural structure of each face image in subspace. Moreover, the intrinsic manifold structure of the sub-pattern sets can also be preserved in our method. With SPP, all sub-patterns partitioned from the original face images are trained to obtain a unified subspace, in which recognition can be performed. The efficiency of the proposed algorithm is demonstrated by extensive experiments on three standard face databases (Yale, Extended YaleB and PIE). Experimental results show that SPP outperforms other holistic and local matching methods.     

A novel Hough transform method for line detection by enhancing accumulator array

In this paper, an improved Hough transform (HT) method is proposed to robustly detect line segments in images with complicated backgrounds. The work focuses on detecting line segments of distinct lengths, totally independent of prior knowledge of the original image. Based on the characteristics of accumulation distribution obtained by conventional HT, a local operator is implemented to enhance the difference between the accumulation peaks caused by line segments and noise. Through analysis of the effect of the operator, a global threshold is obtained in the histogram of the enhanced accumulator to detect peaks. Experimental results are provided to demonstrate the efficiency and robustness of the proposed method.     

A quick tour on suffix arrays and compressed suffix arrays

Suffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in {1,2,…,n}, encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression.