Adv Syst Sci Appl 2019; 04; 25-44 Published online at http://ijassa.ipu.ru/index.php/ijassa/article/view/659 Improving Semi-Supervised Clustering Algorithms with Active Query Selection Walid Atwa*1, Mahmoud Emam2 1) Computer science department, Faculty of Computers and Information, Menoufia University, 32511, Egypt E-mail: walid.atwa@ci.menofia.edu.eg 2) Mathematics and computer science department, Faculty of Science, Menoufia University, 32511, Egypt E-mail: ma7moud_emam@yahoo.com Received October 30, 2018; Revised April 3, 2019; Published December 31, 2019 Abstract: Semi-supervised clustering algorithms use a small amount of supervised data in the form of pairwise constraints to improve the clustering performance. However, most current algorithms are passive in the sense that the pairwise constraints are provided beforehand and selected randomly. This may lead to the use of constraints that are redundant, unnecessary, or even harmful to the clustering results. In this paper, addressing the problem of constraint selection to improve the performance of semi- supervised clustering algorithms. Based on the concepts of Maximum Mean Discrepancy, proposed method selects a batch of most informative instances that minimize the difference in distribution between the labeled and unlabeled data. Then, querying these instances with the existing neighborhoods to determine which neighborhood they belong. The experimental results with state-of-the-art methods on different real-world dataset demonstrate the effectiveness and efficiency of the proposed method. Keywords: Semi-supervised clustering, Active Learning, Pairwise constraints. 1. INTRODUCTION Recently, Semi-supervised clustering (also known as constraint-based clustering) algorithms have become a topic of significant interest for many researchers. These algorithms aim to improve the clustering performance with the help of user-provided side information. There are several types of side information but pairwise constraints are the most used one. There are two types of pairwise constraints: Must-Link (ML) and Cannot-Link (CL) constraints. The must-link constraint indicates that the two objects must be grouped into the same cluster while the cannot-link constraint indicates that the two objects must be in different clusters. The existing constraint-based clustering algorithms assumed that they can improve the clustering performance with a suitable passively chosen set of constraints [1, 2]. However, if the constraints are selected improperly, they may also degrade the clustering performance [3, 4]. Moreover, selecting constraints typically requires a user to manually inspect the data instances that can be time consuming and costly. For those reasons, the proposed method optimize the selection of the constraints to improve the performance of semi-supervised clustering algorithms. * Corresponding author: walid.atwa@ci.menofia.edu.eg mailto:walid.atwa@ci.menofia.edu.eg mailto:ma7moud_emam@yahoo.com 26 W. ATWA, M. EMAM Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) Active learning is well motivated in many supervised learning scenarios where unlabeled instances are abundant and easy to retrieve but labeled instances are difficult, time-consuming and expensive to obtain. For example, it is easy to gather large amounts of unlabeled documents or images from the internet, whereas querying them requires manual effort from experienced human annotators. Hence there is a need to select an optimal set of instances from the pool of unlabeled data for querying. Randomly selection of unlabeled instances for querying is inefficient in many situations, since non-informative or redundant instances might be selected. Active learning algorithms select the most informative unlabeled instances from enormous amount of unlabeled data for querying. Specifically, the goal of active learning is to query data as little as possible to achieve a certain performance, thus saving considerable cost for generating good queries. In this paper, the active learning is applied in an iterative manner. In each iteration, set of queries are selected and queried with the existing neighborhoods to improve the clustering results. Specifically, selecting a batch of informative query instances such that the distribution represented by the selected query set and the available labeled data is closest to the distribution represented by the unlabeled data. In other words, the proposed method select a set of samples S from the unlabeled data, denoted by DU, such that the probability distributions represented by DL ∪ S and DU \ S, where DL is the set of available labeled data, are similar to each other. Then measuring the difference in the probability distribution between the two sets of data using the Maximum Mean Discrepancy (MMD) [5, 6]. Maximum Mean Discrepancy is a statistical test based on the fact that two distributions are different if and only if there exists at least one function in reproducing kernel Hilbert space (RKHS) [6] having different expectations on the two distributions. Once the batch of informative query instances are selected, the proposed method query them with the existing neighborhoods to determine which neighborhood they belong. A neighborhood contains a set of data instances that are known to belong to the same cluster (i.e., connected by must-link constraints) and different neighborhoods are known to belong to different clusters (i.e., connected by cannot-link constraints). Well-formed neighborhoods can provide valuable information regarding what the underlying clusters look like. We empirically evaluate the proposed method with baseline and state-of-the-art methods on UCI real datasets. The evaluation results demonstrate that the proposed method achieves consistent improvements over the baseline methods. The remainder of the paper is organized as follows. Section 2 presents a brief review of the related work. Section 3 introduces the proposed method. Experimental results are presented in Section 4. Finally, conclude the paper and discuss future directions in Section 5. 2. RELATED WORK Active learning has a long history in supervised learning algorithms [7, 8, 9, 10, 11]. Recently, few studies reported the result of using active learning in constrained-based clustering problems. The first study was conducted by Basu et al. [1] that proposed an active k-means clustering using the farthest-first strategy that has two-phases (Explore and Consolidate). The first phase (Explore) uses the farthest-first scheme to form appropriate queries for getting the required pairwise disjoint neighborhoods. At the end of Explore, at least one point has been obtained per cluster. The second phase (Consolidate) iteratively expands the neighborhoods. Where in each iteration it selects a random point outside any neighborhood and queries it against the existing neighborhoods until a must-link is found. An improvement version called Min-Max approach [12], which modifies the Consolidate phase by selecting the most uncertain point to query, instead of selecting the point IMPROVING SEMI-SUPERVISED CLUSTERING ALGORITHMS WITH ACTIVE QUERY SELECTION 27 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) randomly. The idea is to select the data point whose largest similarity to the skeleton is the smallest. By this way, data points with largest uncertainty in cluster membership are chosen first to express the user queries. However, both previous methods do not work well in the case of a dataset with a large number of clusters or unbalanced datasets with small clusters. Xu et al. [13] proposed an active constrained spectral clustering algorithm that examines the eigenvectors to identify the boundary points (of two classes) and sparse points; then it queries the oracle for constraints based on these points. It has shown limited applicability because it requires many queries to the oracle and assumes that errors in the clustering result only occur on the boundary points. Wang et al. [14] presented another spectral active clustering technique that identifies informative pairs according to the entropy of the pair example. But, these approaches have limited their work to two classes, and the direct generalizations to multi-classes cases are not known. Vu et al. [15, 16] proposed an active query selection method based on a constraint utility function called Ability to Separate between Clusters. This method relies on two aspects: (1) a k- nearest neighbors graph is used to determine the best candidate queries in the sparse regions of the dataset between the clusters, and (2) a propagation procedure allows each user query to generate several constraints which limits the user intervention. The propagation procedure discovers new constraints from the information stored in already chosen constraints using the notion of strong paths. Subsequently, the size of the candidate set is reduced by a refinement procedure that removes constraints between objects that are likely to be in the same cluster. Specifically, the refinement procedure removes candidate constraints that are linked by a strong path. Recently, Xiong et al. [17] proposed an active learning method based on the classic uncertainty- based principle. They studied the selection of constraints by selecting the most informative instance to form queries accordingly. The responses to the queries are then used to improve the clustering results. However, this method selects only single instance that can become very slow for retraining with each single instance being queried. Furthermore, if a parallel querying system is available, e.g., multiple annotators working in parallel, these methods would not be able to make the effective use of the resources. Li et al. [18] proposed an active learning method that makes embeddings of labeled examples to those of unlabeled ones and back via deep neural networks. The active scheme makes association cycles that end up at the same class from that the association was started, which considers both the informativeness and representativeness of examples. The above mentioned methods form arrange of studies performed in active selection of constraints. Each method considered a basic assumption on utility of constraints. Their applicability on a specific problem is highly dependent on correlation between their assumption and the actual structure of data. 3. ACTIVE CONSTRAINT SELECTION METHOD Semi-supervised clustering algorithms attempt to partition the unlabeled data into a set of clusters with the help of a small amount of pairwise constraints (must-link and cannot-link). In this section, addressing the problem of how to effectively choose pairwise constraints to produce accurate clustering results. The proposed method first selects a batch of most informative instances that minimize the difference in distribution between the labeled and unlabeled data. Then, querying these instances with the existing neighborhoods to determine which neighborhood they belong. 28 W. ATWA, M. EMAM Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) 3.1 Batch Instances Selection Traditional data mining and machine learning algorithms are based on the assumption that the training data (X, Y) represents the true underlying distributions of X and Y where X={x1, x2,…, xn} is the training data and their corresponding labels Y={y1, y2,…, yn}. Hence a model learned on this data works well for the test data (Xtest, Ytest) which is also drawn independently and identically distributed from the same distribution [5]. Thus, a batch of query instances can be selected from unlabeled data such that the distribution represented by the queried and labeled data is similar to the probability distribution of the unlabeled data set. In other words, selecting a batch of instances S from the unlabeled data (denoted by DU) such that the joint probability distribution represented by DL ∪ S and DU \ S are similar to each other, where DL is set of available labeled data. This function is summarized in Algorithm 1. To measure the difference between two distributions, Maximum Mean Discrepancy (MMD) has been shown to be an effective measure of the difference in their marginal probability distributions [5, 6]. The principal underlying the Maximum Mean Discrepancy is to find a function that assumes different expectations on two different distributions so that when evaluated empirically on samples drawn from the different distributions it would tell us whether the distributions are similar or not. Let ℱ be a class of functions𝑓: 𝒳 → ℝ.. Let p and q be probability distributions defined on a domain 𝒳, and let X = (x1, . . . , xm) and Z = (z1, . . . , zn) be samples composed of independent and identically distributed observations drawn from p and q, respectively. The maximum mean discrepancy (MMD) [5, 6] and its empirical estimate are defined as: MMD[ℱ, 𝑝, 𝑞] ≔ sup 𝑓∈ℱ (𝐸𝑝[𝑓(𝑥)] − 𝐸𝑞[𝑓(𝑧)]) (1) MMD[ℱ, 𝑋, 𝑍] ≔ sup 𝑓∈ℱ ( 1 𝑚 ∑ 𝑓𝑚 𝑖=1 (𝑥𝑖) − 1 𝑛 ∑ 𝑓𝑛 𝑖=1 (𝑧𝑖)) (2) There is a class of functions for which MMD may easily be computed, while retaining the ability to detect all discrepancies between p and q without making any simplifying assumptions. Let ℋ be a complete inner product space (i.e., a Hilbert space) of functions𝑓: 𝒳 → ℝ, where 𝒳 is a nonempty compact set. Then ℋ is termed a reproducing kernel Hilbert space if for all x ∈ 𝒳, the linear point evaluation functional mapping f → f(x) exists and continuous. In this case, f(x) can be expressed as an inner product via 𝑓(𝑥) = 〈𝑓𝜙(𝑥)〉ℋ (3) where 𝜙 : 𝒳 → ℋ is known as the feature space map from 𝒳 to ℋ. When ℱ is the unit ball in a characteristic RKHS [6], MMD is defined as the difference between the means of two distributions after mapping onto the characteristic RKHS. An empirical estimate of MMD is then obtained as follows: MMD[𝜙, 𝑋, 𝑍] ≔ ‖ 1 𝑚 ∑ Φ(𝑥𝑖) − 1 𝑛 ∑ Φ(𝑧𝑖) 𝑛 𝑖=1 𝑚 𝑖=1 ‖ ℋ 2 (4) Now, let us assume that we have u instances of unlabeled data DU and l instances of labeled data DL and we would like to select a batch S of b instances such that the distribution of DL ∪ S is similar to the distribution of DU \ S. Thus, the MMD between the sets DL ∪ S and DU \ S is defined by f(S), can be computed using the expression in Equation (4), as follows: 𝑓(𝑆) = ‖ 1 𝑙+𝑏 ∑ Φ(𝑥𝑗) − 1 𝑢−𝑏 ∑ Φ(𝑥𝑖)𝑖∈𝐷𝑈∖𝑆𝑗∈𝐷𝐿∪𝑆 ‖ ℋ 2 (5) IMPROVING SEMI-SUPERVISED CLUSTERING ALGORITHMS WITH ACTIVE QUERY SELECTION 29 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) Since we want to select a set S from unlabeled data set DU to minimize the mismatch between DL ∪ S and DU \ S. Defining a binary vector 𝛼 of size u where each entry 𝛼𝑖 indicates whether the data xi ∈ DU is selected or not. If a point is selected, the corresponding entry 𝛼𝑖 is 1 else 0. Thus the minimization problem reduces to finding 𝛼 that minimizes the cost function f(S): min 𝛼:𝛼𝑖∈{0,1},𝛼𝑇1=𝑏 ‖ 1 𝑙+𝑏 (∑ Φ(𝑥𝑗)𝑗∈𝐷𝐿 + ∑ αiΦ(𝑥𝑖)𝑖∈𝐷𝑈 ) − 1 𝑢−𝑏 ∑ (1 − αi)Φ(𝑥𝑖)𝑖∈𝐷𝑈 ‖ ℋ 2 (6) where 1 is a vector of the same dimension as 𝛼 with all entries 1 and symbol T is used to represent the matrix or vector transpose operation. Evidently, the cost function in Equation (6) is an alternative (equivalent) representation of the cost function f(S) in Equation (5). The first term denotes the mean of the mapped features of the labeled and selected points. Note that if a point xi is not selected in the current set then 𝛼𝑖 will be 0 and this term would not get added in the summation. The second term is mean of the mapped features of the unlabeled data set minus the selected query set. The first constraint ensures that each entry in 𝛼 is either 0 or 1 and the second constraint ensures that exactly b entries of 𝛼 are 1, meaning exactly b instances are selected from the unlabeled data set, where b is specified a priori by the user. Algorithm 1. QueryInstancesSelection(DL, DU, b); Input: A set of labeled instances DL; set of unlabeled instances DU; batch size b. Output: A batch of query instances S. Compute 𝛼 that minimize the distribution between the sets DL ∪ S and DU \ S (Eq. (6)) Sort DU in descending order of 𝛼 Select top b instances of DU as S Update DL and DU : DL← DL ∪ S, DU← DU \ S return S 3.2 A Neighborhood-based Active Learning Method Once the batch of most informative query instances are selected, the proposed method query them against the existing neighborhoods to determine which neighborhood they belong to. In this section, introducing the concept of neighborhood, which is instrumental in the design of many existing methods for active learning of pairwise constraints [1, 12, 17]. Then, explain how the proposed active learning method can expand the neighborhoods using the selected query instances. A neighborhood contains a set of data instances that are known to belong to the same cluster (i.e. connected by must-link constraints). Different neighborhoods are connected by cannot-link constraints and thus are known to belong to different clusters. For example, Figure 1 shows a set of must-link constraints (x1; x2), (x1; x3), (x4; x5), and (x4; x6), as well as a set of cannot-link constraints (x1; x4) and (x1; x5). Two neighborhoods N1 and N2 can be generated as shown in Figure 1. Neighborhood N1 includes three instances x1, x2, and x3 as described by must-link constraints (x1; x2) and (x1; x3). Similarly, x4, x5, and x6 should also be included in the same neighborhood. Indicated by cannot-link constraints (x1; x4) and (x1; x5), x1 should not be in the neighborhood to which x4 and x5 belong. Therefore, neighborhood N2 is discovered and it contains instances x4, x5, and x6. 30 W. ATWA, M. EMAM Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) Fig. 1: An example of neighborhoods A key advantage of using the neighborhood concepts is that by leveraging the knowledge of the neighborhoods, we can acquire a large number of pairwise constraints via a small number of queries. In particular, if we can identify the neighborhood of an instance x, we can infer its pairwise relationship with all other points that are currently confirmed to belong to any of the existing neighborhoods. This naturally encourages us to consider an active learning strategy that incrementally expands the neighborhoods by selecting the most informative instances and querying them against the known neighborhoods. We summarize the active learning method in Algorithm 2. We begin by initializing the neighborhoods by selecting a random point to be the initial neighborhood (line 1). A selection criterion is then applied to select the batch query instances S as explained in the previous section (line 2). Each selected instance 𝑠 ∈ 𝑆 is then queried against each existing neighborhood Ni to identify where s belongs, during which the constraint set C is updated (lines 5-13). To determine the neighborhood of s with the smallest number of queries, we go through the neighborhoods in decreasing order based on p(s ∈ Ni), i ∈ {1, · · · , k}, i.e. the probability of selected instance s belonging to the neighborhood Ni, which is assumed to be the average similarity between s and the instances in Ni . 𝑝(𝑠 ∈ 𝑁𝑖) = 1 |𝑁𝑖| ∑ 𝑀(𝑠,𝑥𝑗)𝑥𝑗∈𝑁𝑖 ∑ 1 |𝑁𝑝| ∑ 𝑀(𝑠,𝑥𝑗)𝑥𝑗∈𝑁𝑝 𝑘 𝑝=1 (7) where M(s, xj) denote the similarity between instance s and instance xj, |Ni| indicates the number of instances in neighborhood Ni, and k is the total number of existing neighborhoods. We should always start by querying s against the neighborhood that has the highest probability of containing s to minimize the total number of required queries. If a must-link is returned, we can stop with only one query. Otherwise, one should ask the next query against the neighborhood that has the next highest probability of containing s. This process is repeated until a must-link constraint is returned or we have a cannot-link constraint against all neighborhoods. If no must-link is achieved, a new neighborhood will be created using the instance s (lines 14-16). Finally, we apply the semi-supervised clustering algorithm using the selected active pairwise constraints to generate the final clusters (line 18). In this paper, we consider the semi-supervised clustering algorithm as a black-box and any existing algorithm can be used here. N1 N2 x1 x3 x2 x4 x5 x6 IMPROVING SEMI-SUPERVISED CLUSTERING ALGORITHMS WITH ACTIVE QUERY SELECTION 31 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) Algorithm 2. The Proposed Active Learning Method Input: A set of instances D (divided into labeled set DL and unlabeled set DU); total number of queries Q; batch size b. Output: A set of clusters. 1. Initialization: set N1 = {x}, where x is a random instance; C = ∅; q = 0; 2. while q