![](https://csdnimg.cn/release/download_crawler_static/15852204/bg5.jpg)
Effective semi-supervised document clustering 571
clustering algorithm and of computing the similarity between documents. Section 4 presents
our semi-supervised document clustering algorithm. In Sect. 5,wedescribeamethodfor
actively picking good constraints by asking queries of the form “Are these two examples in
same or different classes?”. Section 6 discusses the experimental results on several document
datasets. Finally, we present our conclusions and future work in Sect. 7.
2 Related work
2.1 Semi-supervised clustering
Existing methods for semi-supervised clustering fall into two general approaches: constraint-
based methods and metric-based methods. In constraint-based approaches, the clustering
algorithm itself is modified so that user-provided labels or constraints are used to get a more
appropriate clustering. Wagstaff et al. [11] enforced constraints to be satisfied during the
cluster assignment in the clustering process. Basu et al. [12] proposed two semi-supervised
variants of k-means clustering which use labeled data to generate initial seed clusters and
guide the clustering process. Davidson and Ravi [13] presented the feasibility of clustering
under different types of constraints. And a constrained version of the k-means algorithm was
developed in their paper.
In metric-based approaches, an existing clustering algorithm that used a particular distor-
tion measure is employed; however, the measure is first trained to satisfy the labels or con-
straints in the supervised data. Several typical algorithms have been proposed in this area.
Xing et al. [14] combined the Newton Raphson method and iterative projection together
to learn a Mahalanobis distance for k-means clustering. Screen proposed by Tang et al.
[15] firstly used the constraint-guided feature projection to reduce the dimensionality, which
is equivalent to learn a metric, and then applied the metric into the constrained spherical
k-means algorithm. Bar-Hillel et al. [16] presented an approach to learn a global Mahalan-
obis metric using relevant component analysis (RCA) algorithm. Chang and Yeung [17]
proposed a metric learning method, which performs non-linear transformation globally and
linear transformation locally. Kumar et al. [18] learned the underlying dissimilarity measure
while finding compact clusters in the given dataset. Yan and Domeniconi [19] addressed
the high-dimensionality problem by projecting the data and constraints in multiple subspac-
es and learning positive semi-definite similarity matrices therein. Hu et al. [20]integrated
the constraints into the k-means objective function, which is expressed as equivalent trace
formulation. Then, the objective function was optimized by eigen-decomposition.
Most existing semi-supervised clustering algorithms are k-means like methods, which are
not suitable for discovering clusters with non-convex shapes. Moreover, it needs to know the
real number of clusters in dataset, which is often not known in advance.
2.2 Active learning
Active learning in classification is a long-studied problem, where different principles of sam-
ple selection have been studied. Some approaches choose most uncertain samples, which are
closest to the current classification boundary [21]. Some methods select examples which
reduce the size of the version space [22]. Some methods choose the samples so that the
generalization error is minimized [23,24]. Some other approaches deal with active learning
in the feature level [25,26].
There has been little work on investigating active learning for semi-supervised docu-
ment clustering. Basu et al. [27] proposed a Pairwise Constrained K-Means (PCK-Means)
123