Optimal Selection of Reference Set for the NearestNeighbor Classification by Tabu Search

In this paper, a new approach is presented to find the reference set for the nearest neighbor classifier. The optimal reference set, which has minimum sample size and satisfies a certain error rate threshold, is obtained through a Tabu search algorithm. When the error rate threshold is set to zero, the algorithm obtains a near minimal consistent subset of a given training set. While the threshold is set to a small appropriate value, the obtained reference set may compensate the bias of the nearest neighbor estimate. An aspiration criterion for Tabu search is introduced, which aims to prevent the search process from the inefficient wandering between the feasible and infeasible regions in the search space and speed up the convergence. Experimental results based on a number of typical data sets are presented and analyzed to illustrate the benefits of the proposed method. Compared to conventional methods, such as CNN and Dasarathy's algorithm, the size of the reduced reference sets is much smaller, and the nearest neighbor classification performance is better, especially when the error rate thresholds are set to appropriate nonzero values. The experimental results also illustrate that the MCS (minimal consistent set) of Dasarathy's algorithm is not minimal, and its candidate consistent set is not always ensured to reduce monotonically. A counter example is also given to confirm this claim.

Image-Based Mobile Robot Guidance System by Using Artificial Ceiling Landmarks

This paper presents an image-based mobile robot guidance system in an indoor space with installed artificial ceiling landmarks. The overall system, including an omni-directional mobile robot motion control, landmark image processing and image recognition, is implemented on a single FPGA chip with one CMOS image sensor. The proposed feature representation of the artificial ceiling landmarks is invariant with respect to rotation and translation. One unique feature of the proposed ceiling landmark recognition system is that the feature points of landmarks are determined by topological information from both the foreground and background. To enhance recognition accuracy, landmark classification is performed after the mobile robot is moved to a position such that the ceiling landmark is located in the upright- top corner position of the robot’s camera image. The accuracy of the proposed artificial ceiling landmark recognition system using the nearest neighbor classification is 100% in our experiments.