The relative neighborhood graph for mixed feature variables

摘要

The rectangular influence graph (RIG) is presented as an extension of the relative neighborhood graph (RNG). The RNG is an efficient tool for analyzing the clustering of multidimensional feature vectors when all the features are quantitative. The RIG is a similar tool that can accommodate feature vectors some of whose components are qualitative. We show that the RIG is a superset of the Gabriel graph with respect to any Minkowski metric.As tools to analyze interclass structure, the interclass RIG (IRIG) and the mutual neighborhood graph (MNG) are presented. These graphs can be used to reduce the training set in the design of piecewise linear classifiers. The MNG leads also to a sufficient condition for the linear separability between classes.