The reduced nearest neighbor rule (Corresp.)

A further modification to Cover and Hart's nearest neighbor decision rule, the reduced nearest neighbor rule, is introduced. Experimental results demonstrate its accuracy and efficiency.     

New error bounds with the nearest neighbor rule (Corresp.)

A distribution-free lower bound on the Bayes error rate is formulated in terms of the asymptotic error rate of the nearest neighbor rule with a reject option. Next, a closed form expression for an upper bound of thekth nearest neighbor error rate in terms of the Bayes rate is established. These results are discussed in the framework of recent works on nonparametric estimation of the Bayes error rate.     

An algorithm for a selective nearest neighbor decision rule (Corresp.)

A procedure is introduced to approximate nearest neighbor (INN) decision boundaries. The algorithm produces a selective subset of the original data so that 1) the subset is consistent, 2) the distance between any sample and its nearest selective neighbor is less than the distance from the sample to any sample of the other class, and 3) the subset is the smallest possible.     

On the rate of convergence of nearest neighbor rules (Corresp.)

An erroneous method for maximizing the projected divergence between two Gaussian multivariate hypotheses appeared in a recent paper. The correct solution is given.     

基于压缩近邻的查重元数据去冗算法设计

随着重复数据删除次数的增加,系统中用于存储指纹索引的清单文件等元数据信息会不断累积,导致不可忽视的存储资源开销。因此,如何在不影响重复数据删除率的基础上,对重复数据删除过程中产生的元数据信息进行压缩,从而减小查重索引,是进一步提高重复数据删除效率和存储资源利用率的重要因素。针对查重元数据中存在大量冗余数据,提出了一种基于压缩近邻的查重元数据去冗算法Dedup2。该算法先利用聚类算法将查重元数据分为若干类,然后利用压缩近邻算法消除查重元数据中相似度较高的数据以获得查重子集,并在该查重子集上利用文件相似性对数据对象进行重复数据删除操作。实验结果表明,Dedup2可以在保持近似的重复数据删除比的基础上,将查重索引大小压缩50%以上。     

The two-to-one rule in data smoothing (Corresp.)

If a signal is estimated by a weighted average of the data in the interval(t - c, t + c ), then the variancesigma^{2}of the estimate decreases, but its bias b increases, with increasing c. It is shown that in high accuracy estimates, the mean-square error e is minimum ifcis such thatsigma = 2b, regardless of the formh (t)of the smoothing weight. Furthermore, the resultinge_{m}is minimum ifh(t)is a truncated parabola.     

Some convergence properties of a nearest neighbor decision rule

This paper focuses on the problem of the relationship between the risk incurred using a nearest neighbor rule and the size of the data base. Theoretical results include demonstrations of the facts that the proximity of the nearest neighbor to a new sample in a collection ofnsamples becomes (in probability) arbitrarily small asnis increased; that the convergence is often (but not always) with probability 1; that as a result of these convergences, the risk associated with a decision may be closely controlled; and that these facts and their demonstrations aid one in determining the size of a sample of data to be used as a nearest neighbor decision-making base. An example serves to demonstrate that the size of the data base required to meet performance criteria other than the relatively lax expected risk criterion can be unreasonably large.     

On neighbor distances and symmetry in group codes (Corresp.)

This correspondence provides counterexamples to two frequently proposed conjectures concerning group codes for the Gaussian channel. It is shown 1) that a code for which the list of distances from codewordito all other words is independent ofiis not necessarily a group code, and 2) a group code ofMwords need not possess a transitive symmetry group of orderM.     

An alternative expression of the mutual information for Gaussian processes (Corresp.)

The mutual information plays a central role in communication theory; its general expression for stochastic processes has already been derived. Based on this expression, this correspondence provides an alternative representation of the mutual information for Gaussian processes which is useful in estimation problems.     

The nearest-neighbor rule for small samples drawn from uniform distributions (Corresp.)

It is shown in the classification problem, when independent samples are taken from uniform distributions, that for small sample sizes the probability of misclassification when using the nearest-neighbor rule is "close" to its asymptotic value. It is also shown that when using this rule the probability of classification in many cases is close to its Bayes optimum even for small sample sizes. Moreover, if one is restricted to a small sample size from one population, it is shown that it is not necessary to "make up" this deficiency by taking a large sample from the other population; best results may be obtained when both sample sizes are small.     

Measures of mutual and causal dependence between two time series (Corresp.)

New measures are proposed for mutual and causal dependence between two time series, based on information theoretical ideas. The measure of mutual dependence is shown to be the sum of the measure of unidirectional causal dependence from the first time series to the second, the measure of unidirectional causal dependence from the second to the first, and the measure of instantaneous causal dependence. The measures are applicable to any kind of time series: continuous, discrete, or categorical.     

On compound state and mutual information in quantum information theory (Corresp.)

A quantum mechanical compound state of an input state and its output state generated through a communication channel is constructed. The mutual information of quantum communication theory is defined by using the compound state, and its fundamental properties are studied.     

A generalization of the near-optimum binary coherent state receiver concept (Corresp.)

The structure of a maximum {em a posteriori} decoder is derived for binary optical fields processed according to Kennedy's near-optimum scheme, but operating in the presence of random optical phase-error and interfering background fields. An exact expression is found for the error probability, and examples to illustrate decoder performance under various operating conditions of interest are provided.     

Nonparametric detection using dependent samples (Corresp.)

A new general approach to the formulation of a non-parametric detector using dependent samples is introduced and applied to a space-diversity system employing dc signaling. A comparison based on a form of asymptotic relative efficiency is made between the new detector and a Mann-Whitney detector. Under certain conditions the new procedure demonstrates an improvement in transmission efficiency.     

The sampling window (Corresp.)

The concept of the sampling window is introduced for the central interpolation of finite energy band-limited functions. The sampling window does not increase the rate of convergence of the truncation error series, as do various convergence factors, but does significantly reduce the truncation-error bound.     

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

It is shown thatsqrt[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Sincesqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, wheresqrt{2}is inGF(F_{2})=GF(17), is given.     

Decomposing and shortening codes using automorphisms (Corresp.)

Codes possessing certain types of automorphisms are examined. In one case, the code can be decomposed as a direct sum of two subcodes, which can be viewed as shorter length codes. In a second case, the code itself corresponds to a shorter length code. Related results and applications are given.     

Stable recursive filters using gradient techniques (Corresp.)

In this correspondence the "well known" necessary and sufficient stability conditions for a recursive filter are derived, and a new gradient algorithm is presented that guarantees the stability of a recursive filter. Recent interest in recursive filters is given in [1]-[5].