  We present a clustering- and demotion-based algorithm called Kmeans-FOLD to
induce nonmonotonic logic programs from positive and negative examples. Our
algorithm improves upon-and is inspired by-the FOLD algorithm. The FOLD
algorithm itself is an improvement over the FOIL algorithm. Our algorithm
generates a more concise logic program compared to the FOLD algorithm. Our
algorithm uses the K-means based clustering method to cluster the input
positive samples before applying the FOLD algorithm. Positive examples that are
covered by the partially learned program in intermediate steps are not
discarded as in the FOLD algorithm, rather they are demoted, i.e., their
weights are reduced in subsequent iterations of the algorithm. Our experiments
on the UCI dataset show that a combination of K-Means clustering and our
demotion strategy produces significant improvement for datasets with more than
one cluster of positive examples. The resulting induced program is also more
concise and therefore easier to understand compared to the FOLD and ALEPH
systems, two state of the art inductive logic programming (ILP) systems.
