Boolean kernels and clustering with pairwise constraints

Clustering is a method to group given data into clusters. In this research, we focus on data sets with nominal attributes. For such nominal data sets, it is important to pursue clusters having simple logical representations (patterns) as well as gathering similar objects and separate dissimilar ones. However, conventional clustering methods do not explicitly deal with patterns of clusters. In this paper, we propose a class of kernel functions to approach that problem. For each data point, we associate a Boolean function which expresses the set of patterns covering the point. Hence, the feature space of the proposed kernel is the space of Boolean functions. Using background knowledge, which is also given by a Boolean function, some of patterns are ruled out to obtain appropriate clusters. We call the kernel function restricted by the Boolean function as Boolean kernel or RDF (restricted downward function) kernel. We apply RDF kernel functions to clustering with pairwise constraints. By a numerical experiment, we demonstrate usefulness of RDF kernel functions.