A two-stage clustering-based cold-start method for active learning

Abstract

The problem of initialization of active learning is considered in this paper. Especially, this paper studies the problem in an imbalanced data scenario, which is called as class-imbalance active learning cold-start. The novel method is two-stage clustering-based active learning cold-start (ALCS). In the first stage, to separate the instances of minority class from that of majority class, a multi-center clustering is constructed based on a new inter-cluster tightness measure, thus the data is grouped into multiple clusters. Then, in the second stage, the initial training instances are selected from each cluster based on an adaptive candidate representative instances determination mechanism and a clusters-cyclic instance query mechanism. The comprehensive experiments demonstrate the effectiveness of the proposed method from the aspects of class coverage, classification performance, and impact on active learning.

Keywords

Active learning imbalanced data initial training set clustering

1. Introduction

Active learning (AL) is an effective machine learning technique to achieve an accurate predictive model with fewer labeling costs. In the past few decades, many researchers focused on designing new AL algorithms. However, little attention has been paid to the initialization problem of AL. The initialization of AL will encounter an embarrassing dilemma that all the data is unlabeled, and particularly the unlabeled data is potentially imbalanced. In this paper, the above situation is termed as class-imbalance AL cold-start. In this circumstance, most of the existing AL algorithms are far from being satisfactory without a feasible initialization approach. On the one hand, the supervised AL approaches cannot start properly without an initial training set; on the other hand, the unsupervised AL approaches mostly seldom consider the class skewed distribution scenario, thus the instances in the minority classes tend to be left out in the AL process. Therefore, it is a crucial job to construct an effective initialization method to alleviate the dilemma of class-imbalance AL cold-start.

Supervised active learning is the most popular branch in the AL community, which includes uncertainty sampling [5], query-by-committee [18], expected error reduction [13], etc. A common feature of this kind of active learning is classifier dependence, i.e., they need some initial labeled instances to activate the basic classifiers. However, in practice, the few initially labeled instances are not always guaranteed. Random sampling is a common approach to start supervised active learning. But, it is not suitable for potentially imbalanced data. According to Lewis and Gale [5], it may be a long period of random selection before instances of the minority class are stumbled upon. Moreover, although a few clustering-based AL initialization methods have been designed [11, 19, 23, 25], they are not flexible and not applicable to potentially imbalanced data. The unsupervised active learning techniques, such as clustering-based active learning [21], experimental design methods [24, 14], etc., they typically query the representative instances by exploiting the intrinsic distribution of the data, thus can be used to populate the AL initial training set. However, those methods usually perform well on balanced data set and seldom consider the potentially class-imbalance scenario.

However, imbalanced data is common in many practical applications, such as anomaly detection, credit fraud recognition, and so on [9]. AL users may frequently suffer from the class-imbalance AL cold-start problem. Therefore, it is worthwhile to research how to populate a high-quality and representative initial training set with fewer queries in the class-imbalance AL cold-start scenario. This paper concentrates on this problem in pool-based AL setting and proposes a two-stage clustering-based AL cold-start method (ALCS). The so-called two stages are the pre-clustering stage and instances selection stage.

In our method, the first task is to separate the instances of minority classes from that of majority classes as much as possible and group them into different clusters. To accomplish this, in the pre-clustering stage, a multi-center clustering is built to group the data, which is based on a newly designed inter-cluster tightness measure and the density peak clustering algorithm (DPC, refers to [2]). The second task in our method is to populate the initial training set by selecting and labeling the critical representative instances in each cluster. Therefore, in the second stage, a cluster-adaptive candidate representative instance determination method is designed to find the most representative instances in each cluster. Besides, a clusters-cyclic instance query mechanism that combines an impure cluster splitting strategy is introduced to select the initial training instances sequentially from the candidate representative instance set. The main contributions of this paper are as follows:

•
A multi-center clustering is constructed to group the potentially imbalanced data. This promotes the instances selection procedure to achieve a higher class coverage with fewer queries.
•
A cluster-adaptive candidate representative instance determination method is designed, which enables our model to discover the most representative instances in an arbitrary cluster.
•
A clusters-cyclic instance query mechanism is built to label the critical representative instances sequentially, which avoids the sampling bias between the clusters. Besides, a strategy of impure cluster splitting is incorporated into this procedure to promote the model to label more instances close to the classification boundary.
•
The quality of the selected initial training set is evaluated comprehensively from the aspects of class coverage, classification performance, and impact on active learning.

The rest of this paper is organized as follows. Section 2 reviews the related work about active learning initialization. The proposed method is presented in Section 3. Section 4 presents the experimental results. Finally, conclusions and future work are discussed in Section 5.
2. Related work

In the community of AL, random sampling is the common initialization method to start the AL process [23, 25], owing to the assumption that random sampling is likely to build the initial training set with the same prior distribution as that of the whole original data. However, if the data is potentially skewed, it will be a long period of random selection to obtain a preferable AL initial training set. Besides, random sampling does not guarantee to select a most representative subset [19].

Clustering techniques have been utilized to populate the AL initial training set in a more target way [16, 11, 19, 23, 25]. In the related work, K-means type algorithms are commonly used and the instances located in the center of the clusters are selected as the initial training instances. Although the clustering-based initialization methods are more effective than random sampling, there are two inherent problems that prevent those methods from being widely used. On the one hand, the clustering-based methods do not support incremental initial training instances selection, whereas the selected single batch of instances does not necessarily guarantee to start the active learning process; on the other hand, the number of clusters is generally predefined subjectively and only the center instances of the clusters are selected, however, one single instance is generally not enough to represent a cluster well.

The unsupervised active learning techniques typically do not depend on classifiers, thus can be used to obtain the AL initial training set. Clustering-based AL is a branch of unsupervised AL techniques. However, the most existing clustering-based AL methods do not consider the class-imbalance scenario and lack a cluster-adaptive mechanism to determine how many representative instances need to query in an arbitrary cluster. Dasgupta and Hsu [22] built an active learning scheme based on the hierarchical clustering, in which the training instances are randomly selected from each cluster, but failed to consider the representativeness of the selected instances. The density peaks clustering based active learning (ALEC) by Wang et al. [21] is the recently proposed clustering-based AL method, in which the cluster centers in the DPC algorithm are selected as the training instances. However, ALEC assigns an identical fixed query budget to each cluster, which is inflexible and has no cluster-adaptive ability.

The experimental design method is another branch of unsupervised AL techniques and usually refers to as early active learning [7]. Yu et al. [14, 15] proposed a transductive experimental design (TED) from the perspective of data reconstruction. In the TED, the instance subset which enables to minimize the average expected square predictive error of the learned function is selected as the training set. Cai et al. [4] proposed the MAED method by introducing a manifold adaptive mechanism into the TED scheme and has yielded impressive results. Nie et al. [7] proposed a robust active learning approach (RRSS) by using the structured sparsity inducing norms to relax the TED’s NP-hard objective to a convex formulation. Much previous work has been done by researchers based on experimental design, however, most of the works do not solve the challenge of early active learning, i.e., the class-imbalance AL cold-start problem. Recently, Wang et al. [24] proposed a balanced active learning model (FISTA-LOCP) with an exclusive sparsity norm. To the best of our knowledge, FISTA-LOCP is the only experimental design method that takes into account the potentially imbalanced data.

3. The proposed two-stage clustering-based AL cold-start method

As mentioned in Section 1, the proposed method ALCS consists of two stages, i.e., the pre-clustering stage and the instances selection stage, which are shorted as stage 1 and stage 2, respectively. In the pre-clustering stage, a multi-center clustering is built based on the DPC algorithm and a newly designed inter-clusters tightness measure to obtain a partition of the potentially imbalanced data. In the instances selection stage, a cluster-adaptive representative instance determination method is designed to obtain the candidate representative instances from each cluster. Then, the critical representative instances are sequentially selected based on a clusters-cyclic query mechanism.

Figure 1.

Framework of the proposed ALCS.

The framework of ALCS is depicted in Fig. 1. Suppose $\mathbf{U}=\{\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\}(\mathbf{x}_{i}\in{\mathbb{% R}^{d}})$ is the input unlabeled data set, and $\mathbf{D}=\emptyset$ is the labeled instance set at the beginning. Let $L$ be the number of data classes, and $q$ be the allowable maximal number of inquires for obtaining the AL initial training set. In the pre-clustering stage, the unlabeled data are grouped into a collection of clusters $\mathbf{C}=\{C_{1},\cdots,C_{|\mathbf{C}|}\}$ . By taking advantage of the partition $\mathbf{C}$ , the candidate representative instances subsets $CR_{r}(1\leqslant r\leqslant|\mathbf{C}|)$ are obtained from each cluster via the cluster-adaptive representative instances determination method. Thus, all the candidate representative instances $\mathbf{CR}=\bigcup_{1\leqslant r\leqslant|\mathbf{C}|}CR_{r}$ in the data set can be obtained. Then, the critical instances are gradually selected from $\mathbf{CR}$ . Finally, the ALCS outputs the labeled training set $\mathbf{D}=\{\mathbf{z}_{1},\cdots,\mathbf{z}_{q}\}$ , here each instance $\mathbf{z}_{j}(1\leqslant j\leqslant q)$ is associated with a class label $y_{j}\in[1,\cdots,L]$ . After the training set is obtained, it can be used to start any active learning task. The detailed process of stage 1 and stage 2 are described in Subsections 3.1 and 3.2, respectively.

3.1 Pre-clustering stage

In this stage, the input unlabeled data is clustered by applying a multi-center clustering strategy. Therefore, the instances of the minority classes can be separated from that of the majority classes as much as possible [17, 27], which enables the subsequent instances selection procedure to achieve a higher class coverage as soon as possible. In the multi-center clustering, the data is first grouped into $N_{\textit{init}}$ separate sub-clusters, and then the sub-clusters are agglomerated into some larger clusters based on a newly designed inter-cluster tightness measure.

In the construction of multi-center clustering, the DPC algorithm is employed to obtain the multiple clusters, owing to the DPC algorithm has the advantages of finding clusters of any shape, grouping instances without iteration, and having few input parameters. The key idea of the DPC is that each instance $\mathbf{x}_{i}(i=1,\cdots,n)$ except the cluster centers has a corresponding $\textit{leader}_{i}$ , and each non-center instance is grouped into one cluster with its leader. The leader of an instance is its nearest neighbor with higher local density. For each instance, there are two criteria: local density $\rho$ and distance to its leader $\delta$ , which are defined as follows [2]:

$\displaystyle\rho_{i}=\sum_{j(j\neq i)}\exp\left(-\frac{{d_{ij}^{2}}}{{d_{% \textit{cut}}^{2}}}\right),$ (1) $\displaystyle\delta_{i}=\left\{\begin{array}[]{ll}{\max}_{0\leqslant j% \leqslant n}(d_{ij}),&{\rho_{i}=\max\{\rho_{1},\cdots,\rho_{n}\}}\\ {\min}_{j:\rho_{j}>\rho_{i}}(d_{ij}),&\text{otherwise}.\\ \end{array}\right.$ (2)

In Eq. (1), $d_{ij}$ is the distance between instances $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ , and $d_{\textit{cut}}$ is the input parameter cutoff distance. In order to find the cluster centers, another criterion $\gamma$ corresponding to each instance is defined as:

$\displaystyle\gamma_{i}=\rho_{i}\times\delta_{i}.$ (3)

Based on the “larger $\gamma$ value principle” in the DPC, the top $N_{\textit{init}}$ instances with larger $\gamma$ values are regarded as the cluster centers. Then, the non-center instances are grouped into $N_{\textit{init}}$ clusters based on the leading relation among the instances.

Since the DPC algorithm is sensitive to the input parameter $d_{\textit{cut}}$ , Liu et al. [26] proposed an adaptive density peak clustering based on K-nearest neighbors with aggregating strategy, and $d_{\textit{cut}}$ is redefined as [26]:

$\displaystyle d_{\textit{cut}}=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{K}+\sqrt{% \frac{1}{{n-1}}\sum_{i=1}^{n}{\left(\sigma_{i}^{K}-\frac{1}{n}\sum_{i=1}^{n}% \sigma_{i}^{K}\right)^{2}}},$ (4)

where $n$ is the number of instances in the data set, $\sigma_{i}^{K}={\max}_{j\in\textit{KNN}_{i}}(d_{ij})$ is the distance between $\mathbf{x}_{i}$ to its $K^{\text{th}}$ nearest neighbor, and the user only needs to determine a suitable $K$ value depend on the data. In this paper, the modified DPC based on Eq. (4) is employed in the pre-clustering stage, and the distances between instances are computed by Euclidean distance metric.

It should be noted that calculate the optimal number of initial multiple cluster centers $N_{\textit{init}}$ is a complex job. Readers can refer to the methods in [17, 1]. Since the goal of pre-clustering is not to obtain an accurate clustering result, in this paper the $N_{\textit{init}}$ is set as $3L$ for simplicity. Moreover, in order to avoid the outliers from being selected as cluster centers, the non-leader instances will not be selected as cluster centers in the above DPC process.

After obtaining $N_{\textit{init}}$ initial sub-clusters, some of the sub-clusters need to be agglomerated according to the tightness between them.

.

The tightness measure between two clusters $C_{r}$ and $C_{s}(r\neq s)$ , namely, the connectivity close degree $\textit{Con}(r,s)$ , is defined as follows:

$\displaystyle\textit{Con}(r,s)=\sum_{\mathbf{x}_{i}\in C_{r}}\sum_{\mathbf{x}_% {j}\in C_{s}}\chi(d_{ij}-d_{\textit{cut}}).$ (5)

In Eq. (5), $d_{ij}$ is the distance between instances $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ , the cutoff distance $d_{\textit{cut}}$ is from the DPC clustering process by Eq. (4). The function $\chi(x)=1$ if $x<0$ , and $\chi(x)=0$ otherwise. The cluster pair with the largest connectivity close degree will first be merged into one cluster. Then, the connectivity close degrees between the current clusters are updated. And subsequently, the next closest cluster pair will be merged. The agglomeration process is stopped in case the number of clusters equal to the number of classes $L$ or the connectivity close degrees between the rest clusters are all 0. The pseudo-code of pre-clustering is shown in Algorithm 1.

[htp] Pre-clustering algorithm[1] Dataset $\mathbf{U}=\{\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\}$ , the number of neighbors $K$ , the number of classes $L$ , the number of initial cluster centers $N_{\textit{init}}$ . The result of pre-clustering $\mathbf{C}=\{C_{1},\cdots,C_{|\mathbf{C}|}\}$ . Initial $\mathbf{C}=\emptyset$ ; compute $d_{\textit{cut}}$ based on Eq. (4); Obtain the initial cluster set $\mathbf{C}=\{C_{1},\cdots,C_{N_{\textit{init}}}\}$ by applying the DPC on $\mathbf{U}$ ; Calculate $\textit{Con}(r,s),(1\leqslant r<s\leqslant N_{\textit{init}})$ based on Eq. (5); $|\mathbf{C}|>L$ and $\sum_{0\leqslant r<s\leqslant|\mathbf{C}|}\textit{Con}(r,s)>0$ Merge the cluster pair with largest connectivity close degree; Update the connectivity close degree between current clusters; $\mathbf{C}=\{C_{1},\cdots,C_{|\mathbf{C}|}\}$

3.2 Instances selection stage

3.2.1 Candidate representative instances determination for each cluster

In this subsection, a cluster-adaptive representative instance determination mechanism is built. Through this mechanism, the most representative instances in each cluster can be found. Generally, the cluster centers (the instances with larger $\gamma$ value) in the DPC algorithm are naturally regarded as the most representative instances in the data. Inspired by this, the “larger $\gamma$ value principle” in the DPC is adopted here to find the representative instances in each cluster. However, it is necessary to construct a method to determine how many candidate representative instances are exactly needed in an arbitrary cluster adaptively rather than the manual way in the DPC algorithm. To this end, three new criteria are designed based on the characteristic of $\gamma$ values to determine the number of candidate representative instances automatically in each cluster.

Figure 2.

An example of candidate representative instances determination. (a) is a original 2-dimensional dataset from the reference [2]; (b) presents the $\gamma$ value curve of top 50 instances with $\gamma$ in descending order; (c) shows the $\gamma_{\textit{gain}}$ curve by Eq. (6); (d) is the $\gamma_{\textit{gainG}}$ curve by Eq. (7), and the biggest diversity of $\gamma_{\textit{gainG}}(k)$ and $\gamma_{\textit{gainG}}(k+1)$ can be found when $k$ is the target value; (e) is the $\gamma_{\textit{gainGD}}$ curve by Eq. (8), and the target $k=5$ can be found by searching the maximum value of $\gamma_{\textit{gainGD}}(k)$ ; (f) displays the candidate representative instances obtained by the above process.

Suppose there are $m$ instances in an arbitrary cluster $C_{r}$ . Let $\gamma^{r}=[\gamma_{1}^{r},\cdots,\gamma_{m}^{r}]$ denotes the $\gamma$ value list corresponding to $C_{r}$ , where $\gamma_{i}^{r}$ corresponds to the $i^{\text{th}}$ instances in the cluster. First, $\gamma^{r}$ is ranked in descending order to reveal $\gamma^{r}$ ’s numerical distribution characteristic. the ranked $\gamma^{r}$ is denoted as $\widehat{\gamma}^{r}$ , in which $\widehat{\gamma}_{i}^{r}\geqslant\widehat{\gamma}_{i+1}^{r}$ , $\widehat{\gamma}_{i}^{r}\in\widehat{\gamma}^{r}=[\widehat{\gamma}_{1}^{r},% \cdots,\widehat{\gamma}_{m}^{r}]$ , such as the case in Fig. 2b. Hence, the first criterion $\gamma$ gain ( $\gamma_{\textit{gian}}$ ) is designed to establish the relationship between the number of representative instances $k$ and $\gamma^{r}$ , which is defined as:

$\displaystyle\gamma_{\textit{gain}}(k)=\sum_{i=1}^{k}{\widehat{\gamma}_{i}^{r}% }-\sum_{i=1}^{k}{\widehat{\gamma}_{k+i}^{r}}=\sum_{i=1}^{k}{(\widehat{\gamma}_% {i}^{r}-\widehat{\gamma}_{k+i}^{r}}).$ (6)

For example, $\gamma_{\textit{gain}}(k=2)=(\widehat{\gamma}_{1}^{r}+\widehat{\gamma}_{2}^{r}% )-(\widehat{\gamma}_{3}^{r}+\widehat{\gamma}_{4}^{r})$ . From the curve in Fig. 2c, one can observe that $\gamma_{\textit{gain}}(k)$ is always in ascending order. When $k$ is larger than a certain value, the growth of $\gamma_{\textit{gain}}$ will slow down. Therefore, the target can be transformed into finding the inflection point in the $\gamma_{\textit{gain}}$ curve. The $k$ value corresponds to the inflection point is usually a relatively reasonable number of representative instance points. In order to find the inflection point in $\gamma_{\textit{gain}}$ curve, the second criterion $\gamma_{\textit{gain}}$ growth ( $\gamma_{\textit{gainG}}$ ) is designed as follows:

$\displaystyle\gamma_{\textit{gainG}}(k)=\gamma_{\textit{gain}}(k)-\gamma_{% \textit{gain}}(k-1),(k\geqslant 2)$ (7)

The $\gamma_{\textit{gainG}}(k)$ quantifies the growth of $\gamma_{\textit{gain}}$ corresponding to $k$ . From Fig. 2d, one can find that the value of $\gamma_{\textit{gainG}}(k)$ becomes relatively stable and small behind a certain $k$ value (the target $k$ value). Thus, the target $k$ can be found by examining the diversity between $\gamma_{\textit{gainG}}(k)$ and its successor $\gamma_{\textit{gainG}}(k+1)$ . Consequently, the third criterion $\gamma_{\textit{gainG}}$ diversity ( $\gamma_{\textit{gainGD}}$ ) is defined as:

$\displaystyle\gamma_{\textit{gainGD}}(k)=\gamma_{\textit{gainG}}(k)-\gamma_{% \textit{gainG}}(k+1),(k\geqslant 2)$ (8)

Based on Eq. (8), the $k$ is the target value with which the $\gamma_{\textit{gainGD}}(k)$ is largest, such as the case in Fig. 2e. In the final, a relatively reasonable number of candidate representative instances $RN^{r}={\arg}_{2\leqslant k\leqslant N^{*}}\max\{\gamma_{\textit{gainGD}}(k)\}$ in a cluster can be determined, where $N^{\ast}\leqslant\left\lfloor m/2\right\rfloor-2$ . In case $2\leqslant m<8$ , $RN^{r}$ is directly set as 2, due to the size of the cluster is too small. Through the above process, the candidate representative instance set $CR_{r}(1\leqslant r\leqslant|\mathbf{C}|)$ can be determined in each cluster. The pseudo-code of candidate representative instances determination algorithm is summarized in Algorithm 2.

[htbp] Candidate representative instances determination algorithm[1] Current cluster $C_{r}=\{\mathbf{x}_{1}^{r},\cdots,\mathbf{x}_{m}^{r}\}\in\{C_{1},\cdots,C_{|% \mathbf{C}|}\}$ , the local density $\rho^{r}=[\rho_{1}^{r},\cdots,\rho_{m}^{r}]$ . The number of candidate representative instances $RN^{r}$ ; candidate representative instance set $CR_{r}$ . $2\leqslant m<8$ Set $RN^{r}=2$ directly; [ $m\geqslant 8$ ] Calculate $\delta^{r}=[\delta_{1}^{r},\cdots,\delta_{m}^{r}]$ and $\gamma^{r}=[\gamma_{1}^{r},\cdots,\gamma_{m}^{r}]$ based on $\rho^{r}$ and Eqs (2) and (3); Calculate $RN^{r}$ based on Eqs (6)–(8); Select the top $RN^{r}$ instances to form the $CR_{r}$ based on $\gamma^{r}$ in descending order; $RN^{r}$ , $CR_{r}$

3.2.2 Initial training instances selection procedure

After the candidate representative instances in each cluster are determined, the procedure of initial training instances selection is conducted through a clusters-cyclic instances query mechanism. In this mechanism, at each round, in each cluster, only one unlabeled candidate representative instance with the largest $\gamma$ value, as shown in Eq. (9), is selected to query.

$\displaystyle\mathbf{x}^{\ast}={\arg}_{\mathbf{x}}\max\{\mathbf{x}\in CR_{r}|g% (\mathbf{x})\}$ (9)

In Eq. (9), $g(\mathbf{x})$ is the $\gamma$ value of instance $\mathbf{x}$ . During this process, the clusters with all candidate representative instances labeled will be removed from the clusters-cyclic query loop. This mechanism is designed to avoid sampling bias between the clusters. Since the query budget is usually limited, the strategy that all the candidate representative instances in one cluster are labeled then dealing with the next cluster may result in no chance for the clusters at the end position to be queried.

Furthermore, to improve the classification performance of the learning model based on the selected initial training set, an impure cluster splitting strategy is incorporated into the clusters-cyclic instance query mechanism. Such that, once a cluster is found to be impure, i.e., the cluster in which the labeled instances belong to different classes, it will be split into two smaller clusters. Then, the candidate representative instances corresponding to the split clusters will be recalculated via Algorithm 2. This promotes the model to select more training instances close to the classification boundary. The impure cluster is split by applying the DPC algorithm with the labeled instances as the cluster centers, and the sub-clusters with the same cluster index are merged. The procedure of instances selection is summarized in Algorithm 3.2.2.

[htp] Instances selection algorithm[1] Cluster set $\mathbf{C}=\{C_{1},\cdots,C_{|\mathbf{C}|}\}$ , candidate representative instance set $CR_{r}(r=1,\cdots,|\mathbf{C}|)$ , query budget $q$ ; $//$ $\mathbf{CR}=\bigcup_{1\leqslant r\leqslant|\mathbf{C}|}CR_{r}$ The labeled instance set $\mathbf{D}$ . Initial the labeled instance set $\mathbf{D}\leftarrow\emptyset$ ; ( $|\mathbf{D}|<q$ and $|\mathbf{D}|<|\mathbf{CR}|$ ) $r=1$ ; $r\leqslant|\mathbf{C}|$ ; $r$ ++ $|CR_{r}|>0$ Select a representative instance $\mathbf{x}^{\ast}$ from $CR_{r}$ based on Eq. (9) and inquire $\mathbf{x}^{\ast}$ ’s label; $\mathbf{D}\leftarrow\mathbf{D}\cup\{\mathbf{x}^{\ast}\}$ ; $CR_{r}\leftarrow CR_{r}\setminus{\mathbf{x}^{\ast}}$ ; there are impure clusters in $\mathbf{C}$ Split the impure clusters via the DPC algorithm and recalculate the candidate representative instances set of the split clusters via Algorithm 2 ; Update the cluster set $\mathbf{C}$ and the candidate representative instance set $CR_{r}(r=1,\cdots,|\mathbf{C}|)$ ; $\mathbf{D}$

3.3 Complexity analyses

Suppose there are $n$ instances and $L(L\ll n)$ classes in the data set. The space complexity of ALCS is analyzed as follows. First, in the pre-clustering stage: (a) storing the similarity matrix $(d_{ij})_{n\times n}$ is $O(n^{2})$ ; (b) storing $\rho$ , $\delta$ , $\gamma$ , leader, cluster index and $d_{\textit{cut}}$ is $O(n)$ ; (c) storing the connectivity close degree between clusters needs $C^{2}_{N_{\textit{init}}}$ space, where $N_{\textit{init}}=3L$ , thus the space complexity is $O(L^{2})$ ; Second, in the instances selection stage: (d) storing $\gamma_{\textit{gain}}$ , $\gamma_{\textit{gainG}}$ and $\gamma_{\textit{gainGD}}$ totally need about $3\left\lfloor{n/2}\right\rfloor-3$ space, so the space complexity is $O(n)$ ; (e) storing the candidate representative instances index and the number of candidate representative instances in each cluster is $O(n)$ . Hence the total space complexity of ALCS is $O(n^{2})$ .

The time complexity of ALCS depends on the following aspects: First, in the pre-clustering stage: (a) obtain the initial clusters by DPC takes $O(n^{2})$ time; (b) sub-clusters agglomeration costs $O(n^{2})$ time. Second, in the instances selection stage: (c) suppose the total number of times of instances involved in cluster splitting is $n^{\ast}$ (usually $n^{\ast}\ll n$ ), thus re-calculating the $\gamma$ and sorting the $\gamma$ of every cluster take $O((n+n^{\ast})^{2})=O(n^{2})$ time; (d) obtaining the number of candidate representative instances $R N$ of every cluster cost $O(n)$ time; (e) clusters splitting cost $O(n^{\ast})$ time. Combining both stages, the total time complexity of ALCS is $O(n^{2})$ .

4. Experiments

In this section, the experiments are conducted on a bunch of public data sets. The information of the used data sets is summarized in Table 1. The imbalance ratio “IR” represents the ratio of the number of instances in the most majority class to the number of instances in the most minority class. The IR of the nine data sets ranges from 1.00 to 439.60. Obviously, there are 7 imbalanced data sets and 2 balanced data sets. R15 and Aggregation are from the reference [2], Jain is from the reference [10], and the other six data sets are from UCI repository [12]. There are both binary classification and multi-classification in the data sets, and the information of class distribution is also shown in Table 1. For simplicity, the names of Wine Quality, Robot Navigation, and Electrical Grid are abbreviated as Wine, Robot, and Electrical in the following. It should be noted that the experiments do not involve discrete features encoding and dimension reduction, and all the data sets were not normalized or standardized.

Table 1
Information of the nine data sets used in the experiments

No.	Dataset	Instance	Attribute	Class	IR	Character	Class distribution
1	Glass	214	9	6	8.44	Real	[70, 76, 17, 13, 9, 29]
2	Ecoli	366	7	8	71.50	Real	[143, 52, 35, 77, 2, 20, 2, 5]
3	Jain	373	2	2	2.85	Real	[276, 97]
4	R15	600	2	15	1.00	Real	[40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
							40, 40, 40, 40, 40, 40, 40]
5	Aggregation	788	2	7	8.03	Real	[45, 170, 102, 273, 34, 130, 34]
6	Wine Quality	4898	11	7	439.60	Real	[5, 175, 880, 20, 163, 1457, 2198]
7	Robot Navigation	5456	24	4	6.72	Real	[826, 2205, 328, 2097]
8	Electrical Grid	10000	13	2	1.76	Real	[6380, 3620]
9	Pendigits	10992	16	10	1.08	Integer	[1143, 1143, 1144, 1055, 1144, 1055, 1056, 1142,
							1055, 1055]

In the experiments, five methods are compared with the proposed method ALCS:

•

Random (random sampling) is the baseline method, which arbitrarily selects a subset of instances from the unlabeled instances pool to inquire labels.

•

HSAL [22] is the hierarchical clustering-based active learning method, which selects and labels the instances based on the hierarchical cluster structure and the error estimation of the pruning.

•

ALEC [21] is the density peak clustering-based active learning method, in which the critical instances are selected and labeled based on the master tree and the clustering structure.

•

MAED [4] is an experimental design method, which incorporates a manifold adaptive mechanism into the TED scheme, and tends to select the most representative and discriminative data points for labeling.

•

FISTA-LOCP [24] is an experimental design method based on structure sparsity, which leverages an exclusive sparsity norm to cope with the problem of instances selection in imbalanced data.

In order to verify the effectiveness of the proposed method, the quality of the selected initial training set is evaluated comprehensively from the aspects of class coverage, classification performance, and impact on active learning.

The class coverage of the selected initial training set is critical to active learning initialization. Generally, a higher class coverage of the initial training set leads to a better active learning effect. In this paper, the class coverage is measured by the following two metrics DCC and MNIC.

.

The degree of class coverage (DCC) for initial instances selection is defined as:

$\displaystyle\textit{DCC}(q)=\frac{{N_{\textit{class}}(q)}}{L}\times 100\%.$ (10)

In Eq. (10), $N_{\textit{class}}(q)$ denotes the number of classes covered in the labeled instance set through $q$ times query. The metric DCC is the ratio of the number of classes in the labeled instances to the number of data classes $L$ under a given query budget. The larger this metric value, the better performance of the method on initial training set selection.

.

The minimal number of label inquiries for all classes covered (MNIC) in the set of initial selected instances is defined as:

$\displaystyle\textit{MNIC}={\arg}_{q}\min\{q|N_{\textit{class}}(q)=L\}.$ (11)

The metric MNIC represents the minimal number of label inquiries when all of the classes are covered in the selected initial training set. The smaller this metric value, the better the method on initial training set selection.

Furthermore, the metrics classification accuracy (Acc) and F1-macro (F1) score are involved in the experiments, since it makes sense to evaluate the quality of the selected initial training set from the perspective of classification performance. To measure the impact of the selected initial training set on the active learning process, the area under the learning curve (ALC) is a feasible metric [6]. The metric ALC is usually used to measure the performance of an active learning algorithm, which is also applicable to measure the initialization impact on standard active learning. Thus the metrics ALC on Acc (ALC-Acc) and ALC on F1-macro-score (ALC-F1-macro) are involved in the experiments.

4.1 Comparative experiments

4.1.1 Experimental results on class coverage

Figure 3.

Curves of the metric DCC in initial training instances selection based on the proposed ALCS and five competing methods with the number of queries ranges from $L$ to $5L$ .

To compare the performance of the different methods on metric DCC, for each data set, all the data is used as the input to execute each method 10 times. The initial instances are selected with the number of inquires $q$ ranges from $L$ to $5L$ . The results of the mean degree of class coverage (DCC) are pictured in Fig. 3. One can be observed that the initial training set by ALCS can always cover more classes earlier than that of the competing methods on more data sets, Particularly, ALCS has a distinct advantage to deal with the imbalanced data sets, such as Glass and Ecoli.

Table 2

Minimum number of label inquiries under all classes covered (MNIC) on the nine data sets based on the six different methods

Dataset	Random	HSAL [22]	ALEC [21]	MAED [4]	FISTA-LOCP [24]	ALCS
Glass (IR $=$ 8.44)	29.96 $\pm$ 17.61	22.48 $\pm$ 8.52	17.00 $\pm$ 0.00	22.00 $\pm$ 0.00	15.00 $\pm$ 0.00	12.00 $\pm$ 0.00
Ecoli (IR $=$ 71.50)	40.9 $\pm$ 28.86	29.00 $\pm$ 13.77	17.00 $\pm$ 0.00	11.00 $\pm$ 0.00	60.00 $\pm$ 0.00	10.00 $\pm$ 0.00
Jain (IR $=$ 2.85)	4.64 $\pm$ 3.39	4.10 $\pm$ 2.84	2.00 $\pm$ 0.00	3.00 $\pm$ 0.00	2.00 $\pm$ 0.00	2.00 $\pm$ 0.00
R15 (IR $=$ 1)	48.69 $\pm$ 16.32	33.45 $\pm$ 7.48	21.00 $\pm$ 0.00	15.00 $\pm$ 0.00	28.00 $\pm$ 0.00	15.00 $\pm$ 0.00
Aggregation (IR $=$ 8.03)	38.62 $\pm$ 21.16	29.31 $\pm$ 16.77	8.00 $\pm$ 0.00	7.00 $\pm$ 0.00	10.00 $\pm$ 0.00	7.00 $\pm$ 0.00
Wine (IR $=$ 439.60)	37.75 $\pm$ 26.18	22.00 $\pm$ 10.00	21.00 $\pm$ 0.00	15.00 $\pm$ 0.00	21.00 $\pm$ 0.00	7.00 $\pm$ 0.00
Robot (IR $=$ 6.72)	19.07 $\pm$ 15.10	14.30 $\pm$ 7.92	6.00 $\pm$ 0.00	63.00 $\pm$ 0.00	9.00 $\pm$ 0.00	5.00 $\pm$ 0.00
Electrical (IR $=$ 1.76)	3.49 $\pm$ 2.08	3.55 $\pm$ 2.13	2.00 $\pm$ 0.00	2.00 $\pm$ 0.00	2.00 $\pm$ 0.00	2.00 $\pm$ 0.00
Pendigits (IR $=$ 1.08)	31.30 $\pm$ 11.49	25.77 $\pm$ 5.42	32.00 $\pm$ 0.00	72.00 $\pm$ 0.00	21.00 $\pm$ 0.00	15.00 $\pm$ 0.00
Avg Rank	5.44	4.67	2.61	3.00	2.83	1.00
p-value	5.12E-05

In the comparison on the metric MNIC, each method is conducted 10 times on the whole data of each data set. The results are shown in Table 2 (with the best results in boldface). Needs to note that, Ecoli and Wine Quality are high imbalanced data sets, where Ecoli includes two small classes with each contains only 2 instances (proportion is 0.5%). Wine Quality also includes two small classes with 5 and 20 instances (proportions are 0.1% and 0.4%) insides, respectively. Since none of the six methods can achieve class cover on Ecoli and Wine with a reasonable number of queries, thus the MNIC results on these two data sets are obtained at $L=6$ and $L=5$ , respectively. From Table 2, it can be seen that the proposed ALCS method outperforms Random Sampling and HSAL on all the 9 data sets, and superior to the other three competing methods on most data sets. In summary, the proposed ALCS is more effective than the competitors whether on metrics DCC or MNIC, which indicates that ALCS is likely to provide a higher quality initial training set from the perspective of class coverage.

4.1.2 Experimental results on classification

The quality of the initial training sets selected by different methods is further compared in the task of classification. The selected initial training sets are utilized to train classifiers and compared based on the results of Acc and F1-macro-score. In the experiment, the basic learner logistics regression model from the Python toolbox “Scikit-Learn” with $l_{2}$ regularization is employed to train the classifier, and the “one-versus-rest” strategy is used for the multi-classification. The stratified 10-fold cross-validation is used in the evaluation. The 9 folds data is regarded as the unlabeled instances pool, and the rest 1 fold data is the testing set. For each compared methods, $5L$ instances are selected from the unlabeled instances pool to form the initial training set. The basic learner is trained on the selected initial training set and tested on the testing set.

The experimental results are summarized in Table 3 (with the best results in boldface). The comprehensive results, i.e., the average results (Mean) and the average rank (Avg Rank) are also shown in the table. From the results in Table 3, it can be observed that ALCS outperforms the competing methods on most data sets except Ecoli and Wine quality. But, ALCS still performs better on the comprehensive result. The reason for ALCS not outstanding on Ecoli and Wine quality is that ALCS tends to assign almost the same sampling opportunities to majority and minority classes, while the classification performance in imbalanced data is likely to be dominated by the number of labeled majority class instances. In summary, ALCS can not only perform well in class coverage but also classification on both imbalanced and balanced data for initial training set selection.

4.1.3 Experimental results on initialization impact on active learning

In this subsection, the impact of the selected initial training set on standard active learning is compared based on the metric area under the learning curve (ALC). In the experiment, each compared method offers $2L$ initial training instances to start a standard active learning approach and subsequent the standard active learning approach query additional $3L$ instances with the point-wise instance selection scheme. The results of ALC on classification accuracy (ALC-Acc) and ALC on F1-macro-score (ALC-F1-macro) which produced by the standard active learning approach are recorded. In the above process, Uncertainty Sampling [3] is employed as the standard active learning approach, in which the base classifier is logistic regression and the uncertainty measure is entropy. Uncertainty Sampling is employed based on the consideration that it is one of the most commonly used AL schemes and among the top performers in earlier extensive benchmark experiments [28]. The stratified 10-fold cross-validation is also used in this experiment, where the 9 fold data is regarded as the unlabeled instances pool, the classifier obtained by the standard active learning is tested on the remainder 1 fold testing set. The experimental results are reported in Table 4.

The results show that different initialization methods bring different impacts on standard active learning, and the proposed ALCS does provide a better initialization effect for active learning on most data sets. For data set Wine, since ALCS tends to label more instances of minority classes, which leads the uncertainty sampling approach labels more instances of minority classes, thus ALCS does not perform outstandingly on this data set. The comprehensive results, i.e., Mean and Avg Rank, further demonstrate that ALCS is a more effective solution to cope with the class-imbalance AL cold-start problems.

4.2 Statistical analysis of the experimental results

In order to detect whether there are significant differences in performance among the results of the different methods, the Friedman test [20] is conducted on each performance measure, i.e., MNIC, Acc, F1-macro, ALC-Acc, and ALC-F1-macro, at a confidence level of $\alpha=0.05$ . The p-values of the Friedman tests on the corresponding performance measures are shown in the last row of Tables 2 to 4. Since the p-values are all less than the confidence level $\alpha$ , there exist statistically significant differences between at least two methods on each performance measure.

Furthermore, to detect whether a competing method performs equivalently or significantly different from the control method (i.e., the proposed method ALCS), the Wilcoxon signed-rank test [8] is conducted on each performance measure at a confidence level of $\alpha=0.05$ . The p-values of Wilcoxon signed-rank tests are reported in Table 5. For metric MNIC, the $p$ -values are all less than $\alpha$ , which demonstrates that there are significantly different between ALCS and the competing methods on the class coverage of

Table 3
Classification performance (Acc and F1-macro) of the logistic regression classifiers which were trained on the selected $5L$ initial training set by the six different methods (%)

Dataset	Acc						F1-macro
	Random	HSAL [22]	ALEC [21]	MAED [4]	FISTA-LOCP [24]	ALCS	Random	HSAL [22]	ALEC [21]	MAED [4]	FISTA-LOCP [24]	ALCS
Glass	50.84 $\pm$ 7.45	49.09 $\pm$ 12.37	53.26 $\pm$ 3.48	49.61 $\pm$ 13.27	51.92 $\pm$ 8.55	54.22 $\pm$ 4.81	30.46 $\pm$ 6.69	35.53 $\pm$ 13.54	43.27 $\pm$ 8.55	36.62 $\pm$ 14.15	36.39 $\pm$ 12.21	46.13 $\pm$ 11.64
Ecoli	60.10 $\pm$ 6.04	64.48 $\pm$ 6.09	62.34 $\pm$ 8.98	61.93 $\pm$ 5.93	60.12 $\pm$ 6.16	63.08 $\pm$ 7.31	28.02 $\pm$ 7.42	33.73 $\pm$ 8.34	29.80 $\pm$ 9.91	27.82 $\pm$ 5.38	26.42 $\pm$ 5.09	29.12 $\pm$ 9.49
Jain	87.91 $\pm$ 6.09	91.96 $\pm$ 4.32	86.31 $\pm$ 6.84	93.29 $\pm$ 6.40	91.95 $\pm$ 4.16	94.09 $\pm$ 2.90	81.98 $\pm$ 11.80	88.67 $\pm$ 5.68	84.28 $\pm$ 6.90	90.28 $\pm$ 10.08	88.46 $\pm$ 6.34	91.69 $\pm$ 4.26
R15	61.83 $\pm$ 4.43	70.33 $\pm$ 7.88	65.17 $\pm$ 5.40	74.83 $\pm$ 7.28	68.00 $\pm$ 8.39	99.33 $\pm$ 1.11	55.26 $\pm$ 3.70	61.48 $\pm$ 6.30	58.48 $\pm$ 5.49	71.23 $\pm$ 6.87	62.34 $\pm$ 8.71	99.32 $\pm$ 1.12
Aggregation	88.70 $\pm$ 3.93	91.75 $\pm$ 2.61	92.77 $\pm$ 2.11	93.15 $\pm$ 2.42	89.59 $\pm$ 4.04	95.18 $\pm$ 2.45	69.11 $\pm$ 8.36	73.17 $\pm$ 8.81	81.86 $\pm$ 5.97	82.14 $\pm$ 5.82	70.53 $\pm$ 11.46	93.73 $\pm$ 2.86
Wine	37.40 $\pm$ 2.08	42.89 $\pm$ 1.86	42.73 $\pm$ 5.67	44.36 $\pm$ 4.48	41.32 $\pm$ 1.59	38.30 $\pm$ 2.45	18.84 $\pm$ 2.20	18.09 $\pm$ 2.10	15.77 $\pm$ 2.64	16.03 $\pm$ 2.05	17.85 $\pm$ 2.44	19.59 $\pm$ 2.33
Robot	49.28 $\pm$ 4.87	52.89 $\pm$ 2.67	53.61 $\pm$ 1.50	51.35 $\pm$ 4.74	48.17 $\pm$ 4.32	54.47 $\pm$ 2.98	37.83 $\pm$ 7.46	38.92 $\pm$ 2.77	42.29 $\pm$ 6.05	33.50 $\pm$ 4.56	38.67 $\pm$ 6.44	42.43 $\pm$ 2.99
Electrical	63.14 $\pm$ 9.39	64.92 $\pm$ 2.96	68.55 $\pm$ 3.04	62.47 $\pm$ 5.68	67.69 $\pm$ 4.61	69.90 $\pm$ 2.19	58.77 $\pm$ 9.23	54.26 $\pm$ 8.50	62.73 $\pm$ 3.91	61.48 $\pm$ 5.08	60.63 $\pm$ 6.43	63.55 $\pm$ 3.89
Pendigits	76.63 $\pm$ 3.51	72.18 $\pm$ 4.84	72.29 $\pm$ 0.58	48.14 $\pm$ 2.85	74.77 $\pm$ 2.64	78.23 $\pm$ 2.17	75.47 $\pm$ 4.34	70.00 $\pm$ 5.94	67.76 $\pm$ 0.60	44.74 $\pm$ 4.34	21.76 $\pm$ 3.09	77.74 $\pm$ 1.98
Mean	63.98	66.72	66.33	64.35	65.95	71.88	50.63	52.65	54.03	51.54	47.01	62.59
Avg Rank	5.00	3.44	3.33	3.56	4.11	1.56	4.67	3.56	3.44	3.67	4.44	1.22
p-value	5.40E-03						1.70E-03

Table 4

Results of ALC on classification accuracy and F1-macro-score based on the standard active learning models (Uncertainty Sampling) initialized by the six different methods

Dataset	ALC-Acc						ALC-F1-macro
	Random	HSAL [22]	ALEC [21]	MAED [4]	FISTA-LOCP [24]	ALCS	Random	HSAL [22]	ALEC [21]	MAED [4]	FISTA-LOCP [24]	ALCS
Glass	8.83 $\pm$ 1.53	8.84 $\pm$ 2.43	9.22 $\pm$ 1.25	9.25 $\pm$ 1.13	9.16 $\pm$ 1.72	9.76 $\pm$ 1.28	5.25 $\pm$ 1.29	5.56 $\pm$ 2.49	6.03 $\pm$ 1.34	6.53 $\pm$ 1.50	6.21 $\pm$ 2.08	6.77 $\pm$ 1.79
Ecoli	14.59 $\pm$ 1.83	15.22 $\pm$ 2.08	15.70 $\pm$ 1.95	15.35 $\pm$ 0.86	15.79 $\pm$ 1.65	15.81 $\pm$ 1.65	7.83 $\pm$ 1.75	8.14 $\pm$ 1.97	8.06 $\pm$ 1.28	8.27 $\pm$ 1.46	8.31 $\pm$ 1.29	8.68 $\pm$ 1.93
Jain	4.91 $\pm$ 1.78	3.21 $\pm$ 1.97	5.99 $\pm$ 0.77	3.85 $\pm$ 1.97	5.93 $\pm$ 0.49	6.40 $\pm$ 0.22	4.69 $\pm$ 1.81	3.06 $\pm$ 1.92	5.79 $\pm$ 0.78	3.72 $\pm$ 2.00	5.72 $\pm$ 0.53	6.19 $\pm$ 0.30
R15	26.69 $\pm$ 3.34	26.60 $\pm$ 2.36	29.70 $\pm$ 1.04	31.15 $\pm$ 0.75	28.92 $\pm$ 2.22	31.36 $\pm$ 0.82	23.34 $\pm$ 3.56	23.24 $\pm$ 2.18	26.44 $\pm$ 1.06	28.40 $\pm$ 0.78	25.71 $\pm$ 2.62	28.65 $\pm$ 0.82
Aggregation	18.77 $\pm$ 0.98	18.48 $\pm$ 1.36	20.23 $\pm$ 0.36	19.98 $\pm$ 0.51	18.74 $\pm$ 1.35	20.32 $\pm$ 0.83	14.93 $\pm$ 1.98	13.77 $\pm$ 2.20	17.71 $\pm$ 0.41	16.74 $\pm$ 1.18	14.56 $\pm$ 1.47	19.74 $\pm$ 0.95
Wine	8.78 $\pm$ 0.85	8.95 $\pm$ 0.67	9.81 $\pm$ 1.79	9.18 $\pm$ 0.59	8.78 $\pm$ 0.59	8.74 $\pm$ 0.77	4.09 $\pm$ 0.52	3.92 $\pm$ 0.51	3.96 $\pm$ 0.80	3.39 $\pm$ 0.57	4.02 $\pm$ 0.59	3.85 $\pm$ 0.75
Robot	6.15 $\pm$ 0.75	6.05 $\pm$ 0.57	6.68 $\pm$ 0.33	6.13 $\pm$ 0.46	6.40 $\pm$ 0.67	6.93 $\pm$ 0.27	4.55 $\pm$ 0.62	4.53 $\pm$ 0.65	4.78 $\pm$ 0.24	4.25 $\pm$ 0.61	4.58 $\pm$ 0.63	5.42 $\pm$ 0.62
Electrical	3.96 $\pm$ 0.68	3.19 $\pm$ 0.98	4.44 $\pm$ 0.81	4.11 $\pm$ 0.66	4.45 $\pm$ 0.38	4.79 $\pm$ 0.14	3.48 $\pm$ 0.78	2.95 $\pm$ 0.93	4.09 $\pm$ 0.87	3.89 $\pm$ 0.65	4.09 $\pm$ 0.36	4.24 $\pm$ 0.17
Pendigits	21.91 $\pm$ 1.23	21.60 $\pm$ 0.91	23.32 $\pm$ 0.58	15.02 $\pm$ 1.59	22.28 $\pm$ 1.15	24.04 $\pm$ 0.47	21.18 $\pm$ 1.54	20.88 $\pm$ 0.85	22.61 $\pm$ 0.87	13.84 $\pm$ 1.90	21.65 $\pm$ 1.35	23.80 $\pm$ 0.61
Mean	12.73	12.46	13.89	12.67	13.28	14.24	9.93	9.56	11.05	9.89	10.54	11.93
Avg Rank	4.50	5.22	2.33	3.56	3.16	1.56	4.44	4.89	2.94	4.11	3.17	1.44
p-value	9.37E-05						3.43E-04

Table 5

$P$ -values of the Wilcoxon signed-rank tests using ALCS as the control method

Method	MNIC	Acc	F1-macro	ALC-Acc	ALC-F1-macro
Random	0.0117	0.0117	0.0117	0.0173	0.0173
HSAL [22]	0.0117	0.0929	0.0499	0.0173	0.0173
ALEC [21]	0.0273	0.0687	0.0251	0.1235	0.0173
MAED [4]	0.0422	0.0687	0.0117	0.0357	0.0117
FISTA-LOCP [24]	0.0277	0.0499	0.0117	0.0251	0.0251

Figure 4.

Initial training instances selection results based on ALCS on three 2-dimensional datasets.

initial training instances selection. For metric Acc, only the p-values with respect to Random Sampling and FISTA-LOCP are less than $\alpha$ . Therefore, ALCS only significantly outperforms Random Sampling and FISTA-LOCP on metric Acc. But, the p-values on metric F1-macro are all less than $\alpha$ , which shows that ALCS has significant advantages on initial training instances selection on imbalanced data. The p-values on ALC-Acc are all less than $\alpha$ expect for ALEC, while the p-values are all less than $\alpha$ on metric ALC-F1-macro, which demonstrate that there are significantly different between ALCS and the competing methods in improving the standard active learning process through initial training instances selection.

4.3 Visualized results of initial training set selection

In this subsection, in order to visually display the ability of initial training set selection of ALCS on imbalanced data, the initial instances selection results on three 2-dimensional imbalanced data sets (Jain [10], Aggregation [2] and Three Blobs) based on ALCS are exhibited. For the data set Three Blobs, the class distribution is [800, 50, 50]. The results are shown in Fig. 4, with each data set displays the queried instances on the number of queries $q=[L,3L,5L]$ . The queried instances are marked as yellow “ $\star$ ”.

Evidently, when $q=L$ , one instance of each class can be selected for all the three data sets, and both the majority class and the minority class can obtain the same number of labeled instances in Jain an Aggregation when $q=3L$ and $q=5L$ , which is benefit from the good performance of the pre-clustering and the instances selection method. The results of instances selection on these 2-dimensional data sets further illustrate the effectiveness of our method on dealing with the class-imbalance AL cold-start problem.

5. Conclusion and future work

Aiming at the class-imbalance AL cold-start problem, this paper proposes a two-stage clustering-based AL cold-start method (ALCS). In the pre-clustering stage, a multi-center clustering is constructed based on a new inter-clusters tightness measure and the DPC algorithm to separate the instances of minority classes from that of majority classes in potentially imbalanced data. In the instances selection stage, an adaptive mechanism is designed to find the candidate representative instances in each cluster. Then, a clusters-cyclic instance query mechanism and an impure clusters splitting strategy are introduced to select the initial training instances from the candidate representative instance set. Experiments verify the effectiveness of our method on both imbalanced data sets and balanced data sets from the perspectives of class coverage, classification performance, and impact on active learning.

There are three works merit further investigation: (1) Incorporate a distance metric learning into ALCS is expected to achieve a more effective initial training set selection method. (2) The ALCS method depends on the number of nearest neighbor $k$ , thus how to automatically choose the $k$ value is a meaningful research work. (3) In real applications, the class-imbalance AL cold-start problem may occur in high-dimensional data. Therefore, initial training set selection in high-dimensional data is a worthwhile research topic.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 61876027, 61533020 and 61751312.

References

Likas

Vlassis

and Verbeek

J.J.

, The global K-means clustering algorithm, Pattern Recognition 36(2) (2003), 451–461.

Rodriguez

and Laio

, Clustering by fast search and find of density peaks, Science 344(6191) (2014), 1492–1496.

Settles

, Active learning literature survey, University of Wisconsin, Madison 52 (2010), 55–66.

Cai

and He

, Manifold adaptive experimental design for text categorization, IEEE Transactions on Knowledge and Data Engineering 24(4) (2011), 707–719.

Lewis

D.D.

and Gale

W.A.

, A sequential algorithm for training text classifiers. In: Proceedings of the 17th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, Springer, Ireland, 1994, pp. 3–12.

Cook

D.J.

and Krishnan

N.C.

, Activity learning: discovering, recognizing, and predicting human behavior from sensor data, John Wiley & Sons, 2015.

Nie

Wang

Huang

and Ding

, Early active learning via robust representation and structured sparsity, in: Proceedings of the 23th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Chambery, 2013, pp. 1572–1578.

Wilcoxon

, Individual comparisons by ranking methods, Biometrics Bulletin (6) (1945), 80–83.

Guo

Jennifer

Huang

and Gong

, Learning from class-imbalanced data: review of methods and applications, Expert Systems with Applications 73 (2017), 220–239.

10.

Chen

J.Y.

and He

H.H.

, A fast density-based data stream clustering algorithm with cluster centers self-determined for mixed data, Information Sciences 345 (2016), 271–293.

11.

Kang

Ryu

K.R.

and Kwon

H.C.

, Using cluster-based sampling to select initial training set for active learning in text classification, in: Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, 2004, pp. 384–388.

12.

Bache

and Lichman

, UCI machine learning repository, University of California, School of Information and Computer Science, 2013.

13.

Konyushkova

Sznitman

and Fua

, Learning active learning from data, in: Proceedings of the 31th Advances in Neural Information Processing Systems, MIT Press, Cambridge, 2017, pp. 4225–4235.

14.

and Tresp

, Active learning via transductive experimental design, in: Proceedings of the 23rd International Conference on Machine Learning, ACM, New York, 2006, pp. 1081–1088.

15.

Zhu

and Gong

, Non-greedy active learning for text categorization using convex ansductive experimental design, in: Proceedings of the 31st annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, New York, 2008, pp. 635–642.

16.

Kaufman

and Rousseeuw

, Finding groups in data: an introduction to cluster analysis, John Wiley & Sons, 1990.

17.

Liang

Bai

Dang

and Cao

, The K-means-type algorithms versus imbalanced data distributions, IEEE Transactions on Fuzzy Systems 20(4) (2012), 728–745.

18.

Vandoni

Aldea

and Le Hegarat-Mascle

, Evidential query-by-committee active learning for pedestrian detection in high-density crowds, International Journal of Approximate Reasoning 104 (2019), 166–184.

19.

Zhu

Wang

Yao

and Tsou

B.K.

, Active Learning with Sampling by Uncertainty and Density for Word Sense Disambiguation and Text Classification, in: Proceedings of the 22nd International Conference on Computational Linguistics, ACM, Stroudsburg, 2008, pp. 1137–1144.

20.

Friedman

, A comparison of alternative tests of significance for the problem of m rankings, The Annals of Mathematical Statistics 11(1) (1940), 86–92.

21.

Wang

Min

Zhang

Z.H.

and Wu

Y.X.

, Active learning through density clustering, Expert Systems with Applications 85 (2017), 305–317.

22.

Dasgupta

and Hsu

, Hierarchical sampling for active learning, in: Proceedings of the 25th International Conference on Machine Learning (ICML), ACM, New York, 2008, pp. 208–215.

23.

Namee

B.M.

and Delany

S.J.

, Off to a good start: using clustering to select the initial training set in active learning, in: Proceedings of the 23rd Florida Artificial Intelligence Research Society Conference (FLAIRS), Florida, 2010, pp. 26–31.

24.

Wang

Huang

Liu

and Huang

, New balanced cctive learning model and optimization algorithm, in: Proceedings of the 27th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Chambery, 2018, pp. 2826–2832.

25.

Leng

Wang

and Li

, Combining clustering and voting scheme to select initial training set for active learning, Advanced Materials Research 926–930 (2014), 3008–3011.

26.

Liu

and Yu

, Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy, Knowledge-Based Systems 133 (2017), 208–220.

27.

Wang

and Chen

, Multi-exemplar based clustering for imbalanced data, in: Proceedings of the 13th International Conference on Control Automation Robotics & Vision (ICARCV), IEEE, Piscateway, 2014, pp. 1068–1073.

28.

Yang

and Loog

, A benchmark and comparison of active learning for logistic regression, Pattern Recognition 83 (2018), 401–415.

A two-stage clustering-based cold-start method for active learning

Abstract

Keywords

1. Introduction

3. The proposed two-stage clustering-based AL cold-start method

.

3.2.1 Candidate representative instances determination for each cluster

4. Experiments

Table 1 Information of the nine data sets used in the experiments

.

.

4.1.1 Experimental results on class coverage

4.1.3 Experimental results on initialization impact on active learning

4.2 Statistical analysis of the experimental results

Table 3 Classification performance (Acc and F1-macro) of the logistic regression classifiers which were trained on the selected 5 ⁢ L initial training set by the six different methods (%)

5. Conclusion and future work

Footnotes

Acknowledgments

References

Table 1
Information of the nine data sets used in the experiments

Table 3
Classification performance (Acc and F1-macro) of the logistic regression classifiers which were trained on the selected $5L$ initial training set by the six different methods (%)