Abstract
Abstract Semi-supervised clustering makes use of a small amount of supervised data to aid unsupervised learning. The method used to obtain the supervised information, and the way such information is integrated within the learning algorithm can greatly affect the final result. This paper introduces two different kernel-based semi-supervised clustering algorithms, and investigates the power of kernel methods in principle. Moreover, driven by practice, two methods to obtain supervised data are considered. We compare our kernel-based semisupervised clustering approaches with semi-supervised KMeans and unsupervised kernel KMeans. The experimental results show that both our methods can outperform the others, regardless of the technique used to generate the supervised data.

, and clustering of gene microarray data [4] , semi-supervised clustering has become a topic of significant research interest. Semi-supervised clustering uses a small amount of supervised data, under the form of class labels or pairwise constraints on some instances, to aid unsupervised learning [5] . The main approaches for semi-supervised clustering can be categorized into three general methods [6] : constrained-based [7, 8, 9, 10] , metric-based [11, 12, 13, 14] , and the combination of these two techniques.

The KMeans algorithm is the simplest and most commonly used algorithm for clustering. It minimizes the sum of the squared Euclidean distances between the samples and the corresponding centroids [15] . The assumption behind this measure is the belief that the data space consists of isolated spherical regions. However, this assumption is often violated in practice. To tackle this problem, one can investigate other measures, e.g., the cosine similarity used in information retrieval. An alternative idea is to map the data to a new space that satisfies the requirement of the optimization measure.

A number of kernel-based learning methods have been proposed in recent years [16, 17, 18] . All these methods employ kernel functions to increase the separability of data. Generally speaking, a kernel function implicitly defines a non-linear transformation that maps the data from the original space to a high dimensional space ( [5] . We illustrate, using both simulated and real data, the effect of using supervised data generated by these two techniques. 3 [24] with width parameter q throughout this paper:

= exp(-q xi -xj The (squared) Euclidean distance between points xi and jin feature space is written as:

Let MA be the centroid of cluster Ck in feature space: 

The above three equations can be rewritten using the kernel trick as:

The Kernel KMeans locally minimizes the objective function:

Since A, is common to every cluster, we can avoid calculating it, while BAA must be calculated once for each iteration.

III. SEMI-SUPERVISED FRAMEWORK Suppose the dataset X is structured into K clusters {C } K In a semi-supervised setting, usually there are two ways to obtain a small amount of labeled data S, called the seed set ScX [5] . In one case, the seed set S is given as prior knowledge, and we assume that for each cluster C1 of x, there is at least one seed point X, S. Note that we get a disjoint K partitioning {S } of the seed set S . In the second case, we can access a noiseless oracle, and ask queries regarding pairwise points in the dataset. The oracle assigns constraints of the kind "must-link" or "cannot-link" on a given pair of points. A fixed number of queries can be posed to the oracle, depending on the resources available. In order to improve the clustering performance with as few queries as possible, we wish to consult the oracle on the most informative pairwise constraints. In order to achieve this goal, we use an active learning scheme, the Explore algorithm [5] , to select the pairwise constraints. The Explore algorithm uses a farthest-first traversal scheme to ask more informative queries, and keeps discovering new clusters as fast as possible to form the seed set SaX when the number of clusters K is unknown. The details of the Explore algorithm can be found in [5] .
IV. OUR APPROACH
A. Seeded-Kernel-KMeans In seeded-Kernel-KMeans, the seed set is used to initialize Kernel KMeans. Unlike the Seeded-KMeans algorithm [5] , in which the centroid of the I th cluster is initialized with the centroid of the I th partition S, of the seed set, the points of the th partition S, ofthe seed set are now directly used as the initial points for the I th cluster. The seed set is only used for initialization, and it is not used in the following steps of the algorithm. Therefore the labels of the points in the seed set may change during the execution of the algorithm. If the seed set is noisy, or if the user allows the seed set to change labels during the execution of the algorithm, Seeded-Kernel-KMeans is more appropriate than the constrained approach (see below). The details of the Seeded-Kernel-KMeans algorithm are given in Figure 1 . Compared with Seeded-KMeans, where only the centroids of different partitions of the seed set are used, Seeded-Kemel-KMeans utilizes the whole seed set, and thus leverages more information from the prior knowledge. Fig. 1 . Algorithm Seeded-Kemel-KMeans B. Constrained-Kernel-KMeans In Constrained-Kernel-KMeans, the seed set is used to initialize the Kernel-KMeans algorithm as described for the Seeded-Kernel-KMeans algorithm. However, in the subsequent steps, the cluster membership of the data points in the seed set is not re-computed -the cluster labels of the seed set are kept unchanged, and only the labels of the non-seed data are re-estimated. When the seed set is noise-free, Constrained-Kernel-kMeans is the appropriate choice. In this case, in fact, Constrained-Kernel-KMeans can leverage more information from the seed set. Since the kernel function increases the separability of data, and the cluster membership of the seeds does not change, the algorithm can find a smooth surface in feature space that properly separates the supervised data. The algorithm is given in details in Figure 2 .
V. EXPERIMENTAL EVALUATION
In our experiments we use one synthetic datasets and four real datasets. The synthetic dataset has two uniformly distributed concentric clusters: the radius of the innermost cluster is 1.0 (100 points); the radius of the outer ring is 4.0 (150 points). Three of four real datasets are from the UCI (Iris, Liver, Spectf); the Vowel dataset is orobles@example.com/-tibs/ElemStatLearn/ (for our experiments three clusters are used, corresponding to the vowels "i", "I" and "E".). Their characteristics are as follows. Iris: 150 points, 4 features and 3 clusters; Liver: 345 points, 6 features, and 2 clusters; Spectf: 267 points, 44 features, and 2 clusters; Vowel: 126 points, 10 features, and 3 clusters. All real data are normalized in our experiments. For both the synthetic and real datasets, we used the class labels to compute error rates according to the confusion matrices. That is: each cluster is assigned the label corresponding to the class which has the largest number of points among those in the cluster. The number of non-majority-class points in all clusters (normalized by the total number of data points) gives the error rate. This computation is carried out for all algorithms being compared in our experiments.
V. EXPERIMENTAL EVALUATION
We compare the following clustering algorithms: (1) Seeded-Kernel-KMeans, (2) Seeded-KMeans,
V. EXPERIMENTAL EVALUATION
Constrained-Kernel-KMeans, (4) Constrained-KMeans and (5) Kernel-KMeans without any supervised information. For the first four algorithms, the seed set is obtained either via prior knowledge, or by means of an oracle. We simulate the prior knowledge approach by randomly selecting points from the dataset, according to the corresponding seed set percentage. The generation of queries by means of an oracle is achieved via the Explore algorithm [2] . The unsupervised Kernel-KMeans algorithm is initialized by choosing well-scattered points among the given data. For each dataset, and for each method of producing the seed set, we run each algorithm five times, and report the average error rates and standard deviations. Seeds are generated either randomly or using the Explore algorithm. Clearly, when seeds are generated randomly, each of the five runs in our experiments will have (in general) a different seed set. Likewise, the Explore algorithm has a stochastic component, since the first seed point is chosen randomly. Therefore, different runs of the Explore algorithm will generate different seed sets as well.
V. EXPERIMENTAL EVALUATION
The Explore algorithm is used to generate both seed sets and pairwise constraints. The procedure is the same in the two cases: at each step, the farthest point from the previously chosen ones is selected. At and translated to must-link or cannot link constraints, depending on whether their class labels match or not. We set the kernel width parameter value to q 0.1 for the synthetic dataset. For the real datasets, we fix the width parameter to q -5.0. Figures 3 and 4 show the results for the synthetic dataset. Seeded-Kernel-KMeans, Constrained-Kemel-KMeans, and unsupervised Kernel-KMeans give 0.0% error rate in all cases for q = 0.1. For lack of space, we omit these plots. Figures 3(a)-(b) show the results of Seeded-and Constrained-KMeans, respectively, using 20 queries obtained via the Explore algorithm. Similarly, Figures 4(a)-(b) show the corresponding results when the seed set is randomly chosen. In all four cases, the error rate of both Seeded-and Constrained-KMeans is 40%. Clearly, KMeans (both Seeded and Constrained versions) fails to detect the underlying structure of the clusters for this dataset.
V. EXPERIMENTAL EVALUATION
The results on the real datasets are shown in Figures  5-8 [25] . Two new semi-supervised variants of Kernel KMeans clustering are introduced: Seeded-and ConstrainedKernel-KMeans. We exploit two different methods to generate supervised data (random selection and the Explore algorithm), and perform experiments using both synthetic and real data. The results show the performance improvements achieved by our semi-supervised Kernel KMeans approaches. In our future work, we plan to study mechanisms to automatically set the width parameter of the Gaussian kernel based on the knowledge of the seed sets. In addition, we will combine our semi-supervised approaches with efficient implementations of Kernel KMeans [25] to reduce computation and storage costs when dealing with large corpuses of data.

{'paper_id': '8632012', 'title': 'Exploration of Different Constraints and Query Methods with Kernel-based Semi-supervised Clustering', 's2_url': 'https://api.semanticscholar.org/CorpusID:8632012', 'source': 'S2ORC'}