Recognition of handwritten Chinese characters by elastic matching

A method was proposed to match handwritten Chinese character patterns. Two given patterns are iteratively deformed until they match. An energy function and a neighborhood of influence is defined for each iteration. Initially a large neighborhood is used such that the movements result in large features being coarsely aligned. The neighborhood size is gradually reduced in successive iterations so that finer and finer details are aligned. The amount of computation increases with the square of the number of moving parts which is quite favorable compared with other algorithms. Extensive testing was carried out to evaluate the performance of the algorithm under various parameter settings. The method was applied to the recognition of handwritten Chinese characters with satisfactory results.     

Improved k-nearest neighbor classification

k-nearest neighbor (k-NN) classification is a well-known decision rule that is widely used in pattern classification. However, the traditional implementation of this method is computationally expensive. In this paper we develop two effective techniques, namely, template condensing and preprocessing, to significantly speed up k-NN classification while maintaining the level of accuracy. Our template condensing technique aims at “sparsifying” dense homogeneous clusters of prototypes of any single class. This is implemented by iteratively eliminating patterns which exhibit high attractive capacities. Our preprocessing technique filters a large portion of prototypes which are unlikely to match against the unknown pattern. This again accelerates the classification procedure considerably, especially in cases where the dimensionality of the feature space is high. One of our case studies shows that the incorporation of these two techniques to k-NN rule achieves a seven-fold speed-up without sacrificing accuracy.     

半监督k近邻分类方法

加权KNN(k-nearest neighbor)方法,仅利用了k个最近邻训练样本所提供的类别信息,而没考虑测试样本的贡献,因而常会导致一些误判。针对这个缺陷,提出了半监督KNN分类方法。该方法对序列样本和非序列样本,均能够较好地执行分类。在分类决策时,还考虑了c个最近邻测试样本的贡献,从而提高了分类的正确性。在Cohn-Kanade人脸库上,序列图像的识别率提高了5.95%,在CMU-AMP人脸库上,非序列图像的识别率提高了7.98%。实验结果表明,该方法执行效率高,分类效果好。     

Reducing non-determinism of k-NN searching in non-ordered discrete data spaces

We propose a generalized version of the Granularity-Enhanced Hamming (GEH) distance for use in k-NN queries in non-ordered discrete data spaces (NDDS). The use of the GEH distance metric improves search semantics by reducing the degree of non-determinism of k-NN queries in NDDSs. The generalized form presented here enables the GEH distance to be used for a much greater variety of scenarios than was possible with the original form.     

Exact k-NN queries on clustered SVD datasets

Clustered SVD-CSVD, which combines clustering and singular value decomposition (SVD), outperforms SVD applied globally, without first applying clustering. Datasets of feature vectors in various application domains exhibit local correlations, which allow CSVD to attain a higher dimensionality reduction than SVD for the same normalized mean square error. We specify an exact method for processing k-nearest-neighbor queries for CSVD, which ensures 100% recall and is experimentally shown to require less CPU processing time than the approximate method originally specified for CSVD.     

The MinMax k-Means clustering algorithm

Applying k-Means to minimize the sum of the intra-cluster variances is the most popular clustering approach. However, after a bad initialization, poor local optima can be easily obtained. To tackle the initialization problem of k-Means, we propose the MinMax k-Means algorithm, a method that assigns weights to the clusters relative to their variance and optimizes a weighted version of the k-Means objective. Weights are learned together with the cluster assignments, through an iterative procedure. The proposed weighting scheme limits the emergence of large variance clusters and allows high quality solutions to be systematically uncovered, irrespective of the initialization. Experiments verify the effectiveness of our approach and its robustness over bad initializations, as it compares favorably to both k-Means and other methods from the literature that consider the k-Means initialization problem.     

A Fan-type result on k-ordered graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a ⌊3k/2⌋-connected graph of order n?100k, and d(u)+d(v)?n for any two vertices u and v with d(u,v)=2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255] [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart.     

笔迹图像中的单个汉字字符分割

提出了一套完整的针对单字的笔迹图像分割算法,选用不同的笔迹样本作了验证实验,对实现单字分割做了全面的阐述论证。将模板分割算法中的行分割、字分割、单字图像库建立和基于模板匹配的分割算法结合在一起,提高了算法的运算速度和精确度。利用50幅笔迹样本进行测试,92%的单字分割样本可以作为单字模板,应用模板匹配分割算法92%的样本可以实现单字提取。     

Almost k-wise independence versus k-wise independence

We say that a distribution over {0,1}ⁿ is (ε,k)-wise independent if its restriction to every k coordinates results in a distribution that is ε-close to the uniform distribution. A natural question regarding (ε,k)-wise independent distributions is how close they are to some k-wise independent distribution. We show that there exist (ε,k)-wise independent distributions whose statistical distance is at least n^O(k)·ε from any k-wise independent distribution. In addition, we show that for any (ε,k)-wise independent distribution there exists some k-wise independent distribution, whose statistical distance is n^O(k)·ε.     

k-Anonymous data collection

To protect individual privacy in data mining, when a miner collects data from respondents, the respondents should remain anonymous. The existing technique of Anonymity-Preserving Data Collection partially solves this problem, but it assumes that the data do not contain any identifying information about the corresponding respondents. On the other hand, the existing technique of Privacy-Enhancing k-Anonymization can make the collected data anonymous by eliminating the identifying information. However, it assumes that each respondent submits her data through an unidentified communication channel. In this paper, we propose k-Anonymous Data Collection, which has the advantages of both Anonymity-Preserving Data Collection and Privacy-Enhancing k-Anonymization but does not rely on their assumptions described above. We give rigorous proofs for the correctness and privacy of our protocol, and experimental results for its efficiency. Furthermore, we extend our solution to the fully malicious model, in which a dishonest participant can deviate from the protocol and behave arbitrarily.     

Recognition of handwritten Bengali characters: a novel multistage approach

A multistage scheme for the recognition of handwritten Bengali characters is introduced. An analysis of the Bengali character set has been carried out to isolate specific high-level features that can help in forming smaller sub-groups within the character set. This analysis demonstrates how detection of these various high-level features might help formulate successful multistage OCR design. A multiple expert decision combination hierarchy has been exploited to achieve higher performance from the proposed multi-stage framework.     

Upper signed k-domination in a general graph

Let k be a positive integer, and let G=(V,E) be a graph with minimum degree at least k−1. A function f:V→{−1,1} is said to be a signed k-dominating function (SkDF) if _∑u∈N[v]f(u)?k for every v∈V. An SkDF f of a graph G is minimal if there exists no SkDF g such that g≠f and g(v)?f(v) for every v∈V. The maximum of the values of _∑v∈Vf(v), taken over all minimal SkDFs f, is called the upper signed k-domination numberΓkS(G). In this paper, we present a sharp upper bound on this number for a general graph.     

Improved approximation algorithms for minimum AND-circuits problem via k-set cover

Arpe and Manthey [J. Arpe, B. Manthey, Approximability of minimum AND-circuits, Algorithmica 53 (3) (2009) 337-357] recently studied the minimum AND-circuit problem, which is a circuit minimization problem, and showed some results including approximation algorithms, APX-hardness and fixed parameter tractability of the problem. In this note, we show that algorithms via the k-set cover problem yield improved approximation ratios for the minimum AND-circuit problem with maximum degree three. In particular, we obtain an approximation ratio of 1.199 for the problem with maximum degree three and unbounded multiplicity.     

The global k-means clustering algorithm

We present the global k-means algorithm which is an incremental approach to clustering that dynamically adds one cluster center at a time through a deterministic global search procedure consisting of N (with N being the size of the data set) executions of the k-means algorithm from suitable initial positions. We also propose modifications of the method to reduce the computational load without significantly affecting solution quality. The proposed clustering methods are tested on well-known data sets and they compare favorably to the k-means algorithm with random restarts.     

An algorithm for computing simple k-factors

A k-factor of graph G is defined as a k-regular spanning subgraph of G. For instance, a 2-factor of G is a set of cycles that span G. 2-factors have multiple applications in Graph Theory, Computer Graphics, and Computational Geometry. We define a simple 2-factor as a 2-factor without degenerate cycles. In general, simple k-factors are defined as k-regular spanning subgraphs where no edge is used more than once. We propose a new algorithm for computing simple k-factors for all values of k?2.     

Recognition of handwritten Chinese characters by critical region analysis

The problem of recognizing offline handwritten Chinese characters has been investigated extensively. One difficulty is due to the existence of characters with very similar shapes. In this paper, we propose a “critical region analysis” technique which highlights the critical regions that distinguish one character from another similar character. The critical regions are identified automatically based on the output of the Fisher's discriminant. Additional features are extracted from these regions and contribute to the recognition process. By incorporating this technique into the character recognition system, a record high recognition rate of 99.53% on the ETL-9B database is obtained.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

A k-populations algorithm for clustering categorical data

In this paper, the conventional k-modes-type algorithms for clustering categorical data are extended by representing the clusters of categorical data with k-populations instead of the hard-type centroids used in the conventional algorithms. Use of a population-based centroid representation makes it possible to preserve the uncertainty inherent in data sets as long as possible before actual decisions are made. The k-populations algorithm was found to give markedly better clustering results through various experiments.     

Design-based approach to k-nearest neighbours technique for coupling field and remotely sensed data in forest surveys

The statistical properties of the k-NN estimators are investigated in a design-based framework, avoiding any assumption about the population under study. The issue of coupling remotely sensed digital imagery with data arising from forest inventories conducted using probabilistic sampling schemes is considered. General results are obtained for the k-NN estimator at the pixel level. When averages (or totals) of forest attributes for the whole study area or sub-areas are of interest, the use of the empirical difference estimator is proposed. The estimator is shown to be approximately unbiased with a variance admitting unbiased or conservative estimators. The performance of the empirical difference estimator is evaluated by an extensive simulation study performed on several populations whose dimensions and covariate values are taken from a real case study. Samples are selected from the populations by means of simple random sampling without replacement. Comparisons with the generalized regression estimator and Horvitz-Thompson estimators are also performed. An application to a local forest inventory on a test area of central Italy is considered.