ConiVAT: Cluster Tendency Assessment and Clustering with Partial
  Background Knowledge
  The VAT method is a visual technique for determining the potential cluster
structure and the possible number of clusters in numerical data. Its improved
version, iVAT, uses a path-based distance transform to improve the
effectiveness of VAT for "tough" cases. Both VAT and iVAT have also been used
in conjunction with a single-linkage(SL) hierarchical clustering algorithm.
However, they are sensitive to noise and bridge points between clusters in the
dataset, and consequently, the corresponding VAT/iVAT images are often
in-conclusive for such cases. In this paper, we propose a constraint-based
version of iVAT, which we call ConiVAT, that makes use of background knowledge
in the form of constraints, to improve VAT/iVAT for challenging and complex
datasets. ConiVAT uses the input constraints to learn the underlying similarity
metric and builds a minimum transitive dissimilarity matrix, before applying
VAT to it. We demonstrate ConiVAT approach to visual assessment and single
linkage clustering on nine datasets to show that, it improves the quality of
iVAT images for complex datasets, and it also overcomes the limitation of SL
clustering with VAT/iVAT due to "noisy" bridges between clusters. Extensive
experiment results on nine datasets suggest that ConiVAT outperforms the other
three semi-supervised clustering algorithms in terms of improved clustering
accuracy.
