One usually argues that clustering is an ill-posed problem [1]. The reason may be that there are several ways of addressing this issue. In constraint clustering, the way in which knowledge is integrated will result in transductive clustering if one is solely interested in the structuration of observed data, or it will result in semi-supervised clustering if one wants to build a function able to structure the whole description space.

This paper is an attempt to build a typology of clustering issues along two axes. On the first axis, the authors differentiate between two types of clustering: absolute (membership to a cluster does not depend on the other observations and clusters) and relative (there are dependencies that affect the clustering process). On the second axis, the authors differentiate between three types of clustering: transductive, semi-supervised, and fully supervised. The last two aim to build a function that is able to cluster any new observation; the difference between the two lies in the way constraints are taken into account.

The authors discuss the relationship between both axes and give some advice to the reader who wants to develop a new constraint clustering method. Some algorithms published in the literature usefully illustrate this theoretical contribution.