The relative neighborhood graph for mixed feature variables (Q1057662)

Given a set of finite dimensional feature vectors (datapoints), the relative neighborhood graph (RNG) defined on this set connects relatively close neighbors. The RNG proves itself an efficient tool for analyzing the clustering of multidimensional feature vectors when all features are quantitative. In this paper, the rectangular influence graph (RIG) is presented as an extension of the RNG to sets of multidimensional feature vectors composed of mixed (quantitative as well as qualitative) feature variables. It is shown that the RIG is a superset of the Gabriel graph with respect to any Minkowski metric. The interclass RIG and the mutual neighborhood graph (MNG) are presented as tools to analyze interclass structures. 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.