Semi-supervised single-link clustering method
Y. C. A. Padmanabha Reddy, P. Viswanath, B. Eswara Reddy · 2016
The single-link clustering method can find arbitrary shaped clusters. Single-link based semi-supervised clustering method in the presence of a few labeled data and constraints is presented in the paper. Based on the labeled data or constraints, the dissimilarity function is modified. Merging of clusters is done, as in the conventional singlelink method. The "must-link" constraints can easily be integrated in to the process, but "can-not link" constraints poses its own problems. Earlier attempts to overcome this problem, suggested the usage of the complete-link clustering method in place of the single-link method and the method thus derived is called the constrained complete-link (CCL) method. But, with a lesser number of constraints, the CCL method's working is very similar to that of the conventional complete-link method which cannot find arbitrary shaped clusters. The proposed semi-supervised singlelink (SSL) method can overcome this, also it can overcome the "noisy bridge" problem which is a well known problem present with the single-link method. The SSL method does not use the precomputed distance matrix alone, as the CCL method does, but, distance between clusters is computed by taking in to account both pre-computed distance matrix and constraints. Experimental studies are done using both standard and synthetic data sets. It is shown that the proposed SSL method is consistently superior than the CCL method and other conventional linkage based methods.