Bregman distances and Chebyshev sets

A closed set of a Euclidean space is said to be Chebyshev if every point in the space has one and only one closest point in the set. Although the situation is not settled in infinite-dimensional Hilbert spaces, in 1932 Bunt showed that in Euclidean spaces a closed set is Chebyshev if and only if the set is convex. In this paper, from the more general perspective of Bregman distances, we show that if every point in the space has a unique nearest point in a closed set, then the set is convex. We provide two approaches: one is by nonsmooth analysis; the other by maximal monotone operator theory. Subdifferentiability properties of Bregman nearest distance functions are also given.     

Approximating minimum-length-sequence metrics: a cautionary note

In numerical taxonomy one may wish to measure the dissimilarity of classifications S and T by computing the distance between them with an appropriate metric. A minimum-length-sequence (MLS) metric requires that the user identify a set X of meaningful transformations of classifications; the MLS metric μ_x is then defined by requiring that μ_x (S,T) be the length of a shortest sequence of transformations from X that carries S into T.For a given application it may be relatively easy to identify an appropriate set X of transformations, but it may be difficult or impossible to design an efficient algorithm to compute μ_x. In this case it is natural to restrict the definition to obtain an approximation ? to the original metric μ_x such that ? has an efficient algorithm for its computation. This restriction process must be performed carefully lest the approximation fail to satisfy the metric properties. We present a general result about this problem and apply it in two ways. First we prove that a published ‘metric’ on partitions of a set in fact violates the triangle inequality and so is merely a semimetric. Then we clarify the relationship between the nearest neighbor interchange metric on labeled binary trees and the closest partition distance measure proposed by Waterman and Smith (1978).     

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.     

A comparison of several nearest neighbor classifier metrics using Tabu Search algorithm for the feature selection problem

The feature selection problem is an interesting and important topic which is relevant for a variety of database applications. This paper utilizes the Tabu Search metaheuristic algorithm to implement a feature subset selection procedure while the nearest neighbor classification method is used for the classification task. Tabu Search is a general metaheuristic procedure that is used in order to guide the search to obtain good solutions in complex solution spaces. Several metrics are used in the nearest neighbor classification method, such as the euclidean distance, the Standardized Euclidean distance, the Mahalanobis distance, the City block metric, the Cosine distance and the Correlation distance, in order to identify the most significant metric for the nearest neighbor classifier. The performance of the proposed algorithms is tested using various benchmark datasets from UCI Machine Learning Repository.     

Identification and estimation of superposed Neyman–Scott spatial cluster processes

This paper proposes an estimation method for superposed spatial point patterns of Neyman–Scott cluster processes of different distance scales and cluster sizes. Unlike the ordinary single Neyman–Scott model, the superposed process of Neyman–Scott models is not identified solely by the second-order moment property of the process. To solve the identification problem, we use the nearest neighbor distance property in addition to the second-order moment property. In the present procedure, we combine an inhomogeneous Poisson likelihood based on the Palm intensity with another likelihood function based on the nearest neighbor property. The derivative of the nearest neighbor distance function is regarded as the intensity function of the rotation invariant inhomogeneous Poisson point process. The present estimation procedure is applied to two sets of ecological location data.     

AN UPPER BOUND ON AVERAGE TOUCHING NUMBER OF A VORONOI PARTITION

A Voronoi partition is decided bythe configurations of N centerepoints in n dimensional Euclidean space. The total number of nearest neighbor points for a given centerpoint in the partition is called its touching number. It is shown that the average touching number for all points in a Voronoi partition is not greater than the n dimensional kissing number, that is, the maximum uumber of unit spheres that can touch a given unit sphere without overlapping.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

Equivalence relations and distances between Hilbert frames

We study some equivalency relations between Hilbert frames and closed subspaces of . We define also a distance between frames and we establish the geometric meaning of this metric. Finally we find the closest and respectively the nearest tight frame to a given frame.

     

Distributions of rectilinear deviation distance to visit a facility

This paper deals with the deviation distance to visit a facility from pre-planned routes. Facilities are approximated by both points and lines on a continuous plane. To see the relationship between the deviation distance and the availability of facilities, we derive the distributions of the rectilinear deviation distance for regular and random patterns of facilities. These distributions demonstrate how the shortest distance and the relative position of origin and destination affect the deviation distance. We also show that the deviation distance is a generalization of the nearest neighbour distance.     

A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations

An algorithm for computing discrete, 2-dimensional, Euclidean Voronoi tessellations is presented. The algorithm combines a limiting sweep circle approach with a nearest neighbor cellular approach. It reduces the computational cost of the naïve approach while at the same time giving the Euclidean Voronoi tessellations that simple nearest neighbor algorithms are unable to produce. The algorithm is shown, through analytical methods, to produce good approximations to corresponding continuous Voronoi tessellations depending on the definition of neighbor used in the nearest neighbor step and the mesh size. The quality of different types of neighbor definitions are discussed as well as the computational cost. The algorithm is general enough to be easily extended to higher dimensions and nonuniform meshes. The analysis lays the groundwork for the computation of discrete centroidal Voronoi tessellations where some kind of numerical integration is required.     

On principle axis based line symmetry clustering techniques

In this paper, at first a new line symmetry (LS) based distance is proposed which calculates the amount of symmetry of a point with respect to the first principal axis of a data set. The proposed distance uses a recently developed point symmetry (PS) based distance in its computation. Kd-tree based nearest neighbor search is used to reduce the complexity of computing the closest symmetric point. Thereafter an evolutionary clustering technique is described that uses this new principal axis based LS distance for assignment of points to different clusters. The proposed GA with line symmetry distance based (GALS) clustering technique is able to detect any type of clusters, irrespective of their geometrical shape, size or convexity as long as they possess the characteristics of LS. GALS is compared with the existing genetic algorithm based K-means clustering technique, GAK-means, existing genetic algorithm with PS based clustering technique, GAPS, spectral clustering technique, and average linkage clustering technique. Five artificially generated data sets having different characteristics and seven real-life data sets are used to demonstrate the superiority of the proposed GALS clustering technique. In a part of experiment, utility of the proposed genetic LS distance based clustering technique is demonstrated for segmenting the satellite image of the part of the city of Kolkata. The proposed technique is able to distinguish different landcover types in the image. In the last part of the paper genetic algorithm is used to search for the suitable line of symmetry of each cluster.     

Multicriteria fuzzy classification procedure PROCFTN: methodology and medical application

In this paper, we introduce a new classification procedure for assigning objects to predefined classes, named PROCFTN. This procedure is based on a fuzzy scoring function for choosing a subset of prototypes, which represent the closest resemblance with an object to be assigned. It then applies the majority-voting rule to assign an object to a class. We also present a medical application of this procedure as an aid to assist the diagnosis of central nervous system tumours. The results are compared with those obtained by other classification methods, reported on the same data set, including decision tree, production rules, neural network, k nearest neighbor, multilayer perceptron and logistic regression. Our results are very encouraging and show that the multicriteria decision analysis approach can be successfully used to help medical diagnosis.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

END样本最近邻密度估计的强相合速度

本文研究了扩展负相依(END)样本最近邻密度估计的强相合性问题.利用END序列的Bernstein型不等式和截尾的方法,获得了END样本最近邻密度估计的强相合速度,推广了NA样本和ND样本最近邻密度估计的相应结果.     

Computing the minimum distance between two Bézier curves

A sweeping sphere clipping method is presented for computing the minimum distance between two Bézier curves. The sweeping sphere is constructed by rolling a sphere with its center point along a curve. The initial radius of the sweeping sphere can be set as the minimum distance between an end point and the other curve. The nearest point on a curve must be contained in the sweeping sphere along the other curve, and all of the parts outside the sweeping sphere can be eliminated. A simple sufficient condition when the nearest point is one of the two end points of a curve is provided, which turns the curve/curve case into a point/curve case and leads to higher efficiency. Examples are shown to illustrate efficiency and robustness of the new method.     

随机需求下多供应商和多零售商的生产-库存-运输联合优化模型

考虑随机需求下多供应商和多零售商的生产-库存-运输联合优化问题.在联合优化时,首先利用最近邻算法将各零售商分成不同区域,分区后问题转化为随机需求下单供应商对多零售商的生产-库存-运输联合优化问题.在每个分区内,由供应商统一决策其分区内各零售商的送货量和送货时间.利用粒子群算法和模拟退火算法相结合的两阶段算法求出最优送货量、最优运输路径和最大期望总利润.然后采用收入共享契约将增加的利润合理分配给各供应商和各零售商,使各方利润都得到增加,从而促使各方愿意合作.通过数值算例验证了联合优化模型优于独立决策模型.     

A comparative study of the effect of the position of outliers on classical and nontraditional approaches to the two-group classification problem

Popularity of nontraditional approaches to the statistical classification problem has resulted from the potential of these techniques to outperform the standard parametric procedures under conditions when nonnormality is present. Thus proponents of these nontraditional models have recommended these models when outliers are in the data. However, research showing that these nontraditional models' performances can vary widely depending on where the outlier data are located has not been fully illustrated. The research in this paper demonstrates how the mathematical programming approaches and the nearest neighbor discriminant models can be affected by the position of contaminated normal data and that each of the models studied in this paper may not be robust to all types of outliers in the data. The results of this paper are also important because the study compares two recently proposed mathematical programming models as well as two versions of the nearest neighbor model with the standard classical parametric models. This combination of classification models does not appear to have been studied together under conditions of contaminated normal data in which numerous positions of the outliers are considered.     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.     

Multidimensional scaling with constraints on the configuration

In this paper we determine a configuration in a constrained set such that the corresponding distance matrix is closest to a given (not necessarily Euclidean) one. We admit a wide class of appropriate matrix norms as measures of closeness. Majorization inequalities serve as basic tools.     

L2—cross—validation最近邻中位数估计的渐近最优性

本文研究固定设计点模型的最近邻中位数估计的光滑参数的选择问题。在一定的正则性条件下得到了Ｌ２－ｃｒｏｓｓ－ｖａｌｉｄａｔｉｏｎ最近邻中位数估计的渐近最优性。同时还得到了最近邻中位数估计的弱Ｂａｈａｄｕｒ表示。