Chromatic nearest neighbor searching: A query sensitive approach

The nearest neighbor problem is that of preprocessing a set P of n data points in so that, given any query point q, the closest point in P to q can be determined efficiently. In the chromatic nearest neighbor problem, each point of P is assigned a color, and the problem is to determine the color of the nearest point to the query point. More generally, given k1, the problem is to determine the color occurring most frequently among the k nearest neighbors. The chromatic version of the nearest neighbor problem is used in many applications in pattern recognition and learning. In this paper we present a simple algorithm for solving the chromatic k nearest neighbor problem. We provide a query sensitive analysis, which shows that if the color classes form spatially well separated clusters (as often happens in practice), then queries can be answered quite efficiently. We also allow the user to specify an error bound 0, and consider the same problem in the context of approximate nearest neighbor searching. We present empirical evidence that for well clustered data sets, this approach leads to significant improvements in efficiency.     

The complex band structure for armchair graphene nanoribbons

Using a tight binding transfer matrix method,we calculate the complex band structure of armchair graphene nanoribbons.The real part of the complex band structure calculated by the transfer matrix method fits well with the bulk band structure calculated by a Hermitian matrix.The complex band structure gives extra information on carrier’s decay behaviour.The imaginary loop connects the conduction and valence band,and can profoundly affect the characteristics of nanoscale electronic device made with graphene nanoribbons.In this work,the complex band structure calculation includes not only the first nearest neighbour interaction,but also the effects of edge bond relaxation and the third nearest neighbour interaction.The band gap is classified into three classes.Due to the edge bond relaxation and the third nearest neighbour interaction term,it opens a band gap for N=3M 1.The band gap is almost unchanged for N=3M + 1,but decreased for N=3M.The maximum imaginary wave vector length provides additional information about the electrical characteristics of graphene nanoribbons,and is also classified into three classes.     

Accelerating distributed average consensus by exploring the information of second-order neighbors

The problem of accelerating distributed average consensus by using the information of second-order neighbors in both the discrete- and continuous-time cases is addressed in this Letter. In both two cases, when the information of second-order neighbors is used in each iteration, the network will converge with a speed faster than the algorithm only using the information of first-order neighbors. Moreover, the problem of using partial information of second-order neighbors is considered, and the edges are not chosen randomly from second-order neighbors. In the continuous-time case, the edges are chosen by solving a convex optimization problem which is formed by using the convex relaxation method. In the discrete-time case, for small network the edges are chosen optimally via the brute force method. Finally, simulation examples are provided to demonstrate the effectiveness of the proposed algorithm.     

在计算机模拟试验中不同试验设计的比较

计算机模拟试验的设计与建模有许多方法,本文选择了四种不同类型的真模型,用四种试验设计方法,考虑了大小不同的试验方案,并选用了四种建模方法进行比较,给出一些经验性结论,相信这些结论在计算机试验中是有参考价值的。     

考虑客户满意度的同时收发车辆路径问题

当客户要求车辆一次性完成发送以及收集货物的任务时, 只需考虑车辆的路径安排即可.但若客户进一步提出在时间窗内完成的话,就必须考虑客户的等待时间--客户的满意度的衡量标准,等待时间越短满意度越高.因此问题的目标为最小化车辆路径总长度、最小化所有客户等待时间之和.本文通过加权转变为单目标函数,由最邻近法及最廉价插入法得到初始解后经过禁忌搜索算法可得到改进算法,解并通过实例对不同权参数的情况进行了比较.     

A boundary corrected expansion of the moments of nearest neighbor distributions

In this article, the moments of nearest neighbor distance distributions are examined. While the asymptotic form of such moments is well‐known, the boundary effect has this far resisted a rigorous analysis. Our goal is to develop a new technique that allows a closed‐form high order expansion, where the boundaries are taken into account up to the first order. The resulting theoretical predictions are tested via simulations and found to be much more accurate than the first order approximation obtained by neglecting the boundaries. While our results are of theoretical interest, they definitely also have important applications in statistics and physics. As a concrete example, we mention estimating Rényi entropies of probability distributions. Moreover, the algebraic technique developed may turn out to be useful in other, related problems including estimation of the Shannon differential entropy.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Evolutionary Design of Nearest Prototype Classifiers

In pattern classification problems, many works have been carried out with the aim of designing good classifiers from different perspectives. These works achieve very good results in many domains. However, in general they are very dependent on some crucial parameters involved in the design. These parameters have to be found by a trial and error process or by some automatic methods, like heuristic search and genetic algorithms, that strongly decrease the performance of the method. For instance, in nearest prototype approaches, main parameters are the number of prototypes to use, the initial set, and a smoothing parameter. In this work, an evolutionary approach based on Nearest Prototype Classifier (ENPC) is introduced where no parameters are involved, thus overcoming all the problems that classical methods have in tuning and searching for the appropiate values. The algorithm is based on the evolution of a set of prototypes that can execute several operators in order to increase their quality in a local sense, and with a high classification accuracy emerging for the whole classifier. This new approach has been tested using four different classical domains, including such artificial distributions as spiral and uniform distibuted data sets, the Iris Data Set and an application domain about diabetes. In all the cases, the experiments show successfull results, not only in the classification accuracy, but also in the number and distribution of the prototypes achieved.     

最近邻回归估计的正态逼近速度

本文利用Berry－Esseen定理，在一定的条件下，得到了最近邻回归估计逼近于正态分布的速度．