k-Nearest Neighbor Classification on First-Order Logic Descriptions

Classical attribute-value descriptions induce a multi-dimensional geometric space. One way for computing the distance between descriptions in such a space consists in evaluating an Euclidean distance between tuples of coordinates. This is the ground on which a large part of the Machine Learning literature has built its methods and techniques. However, the complexity of some domains require the use of First-Order Logic as a representation language. Unfortunately, when First-Order Logic is considered, descriptions can have different length and multiple instance of predicates, and the problem of indeterminacy arises. This makes computation of the distance between descriptions much less straight forward, and hence prevents the use of traditional distance-based techniques. This paper proposes the exploitation of a novel framework for computing the similarity between relational descriptions in a classical instance-based learning technique, k-Nearest Neighbor classification. Experimental results on real-world datasets show good performance, comparable to that of state-of-the-art conceptual learning systems, which supports the viability of the proposal.