Semi-supervised Multi-instance Learning with Density Peaks Clustering

YANG Mei,ZHANG Yuxuan,MIN Fan

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

Abstract：The task of multi-instance learning (MIL) is to train a classifier to handle complicated data bags，among which many methods are developed based on different similarity measures between bags. Since a conspicuous feature of MIL is the inherent structures of bag, we propose the semi-supervised multi-instance learning with density peaks clustering (SMDP) algorithm with three steps for this issue. First, we select the most nc representative bags using a clustering-based technique coupled with the Gaussian kernel and five distance measures. Second, each bag is transformed into the nc-dimensional instance space using distances among bags. The value of the i-th feature of the new instance is the distance between the bag and the i-th representative bag. Third, the nc-dimensional data table is employed to build a classifier. The results on twenty-seven data sets show that our algorithm is superior to state-of-the-art MIL algorithms especially on text and image data sets.

Key words：density peaks clustering; Gaussian kernel; multi-instance learning; semi-supervised learning

0 Introduction

Multi-instance learning (MIL) was introduced by Dietterichetal.[1]in their investigation on drug activity prediction.A MIL data set consists of multiple bags, each of which consists of multiple instances. Hence MIL is more general than traditional supervised learning,i.e. single-instance learning (SIL). The basic assumption of MIL is that a bag receives a particular label if at least one of the instance in the bag possesses it. For binary classification, a bag is positive if it contains at least one positive instance; otherwise it is negative. Moreover, in most cases, we specify or predict the label of a bag instead of an instance. Due to its adaptability, MIL has been widely applied in diverse domains such as image classification[2-4], image annotation[5-6], image retrieval[7-9], text classification[10-12], biological function annotation[4], medical diagnosis[13-14], object tracking[15-16]and sentiment analysis[17-18].

Over these years, many MIL methods have been developed. The kernel-based approaches[19-21]focus on designing a set-kernel based on the conventional kernel (e.g. Gaussian kernel) or using an existing set-kernel (e.g. Fisher kernel). The SVM-based approaches[11]modify optimization objective function and make SVM suitable for MIL. The clustering-based approaches[22-23]treat the bags as atomic data items and use some form of distance measures to calculate distance between bags. All of these methods explicitly or implicitly convert MIL problems into SIL problems. The simplest method[11]is to treat all instances in a bag as the same label with the bag and solve it with SIL methods.

In this paper, we propose the semi-supervised multi-instance learning with density peaks clustering (SMDP) algorithm. Since the learning scenario is semi-supervised, the training set contains both labeled and unlabeled bags. We adopt the following algorithm framework with three stages. In the representative selection stage,ncrepresentative bags are selected from the training set. In the data conversion stage, each bag is converted to annc-dimensional instance according to its distance to each representative bag. To classify a bag, it is first converted to annc-dimensional instance, and its label is predicted bykNN according to labeled data. Naturally, this algorithm is able to classify both unlabeled training bags and new ones. In order to improve the accuracy of prediction, we focus on both how to find out more representative bags and how to calculate the distance for different data sets.

The first key issue of our algorithm is the selection of representatives. We design a technique inspired by the density peaks (DP) clustering algorithm[24]. The Gaussian kernel is employed to compute the density of each bag. The cutoff distance is set to a given ratio (e.g. 0.2) times of the diameter of the data set. The master of a bag is the closest bag with a higher density. The representativeness of each bag is then calculated as the pro-duct of its density and the distance to its master. For binary classification data sets, the set of representatives is the top-ncbags with high representativeness. For multi-class data sets, if we find representative bags based on all classes, some representative bags may come from the same class. This will disrupt the balance of the original class, and reduce final prediction accuracy. Our solution is to find a representative bag for each class and one for all unlabeled bags.

Experiments were undertaken on five benchmark data sets, twenty text data sets and two image data sets. Results show that SMDP is highly competitive to the eight state-of-the-art MIL methodsi.e. CCE[22], ISK[12], mi-FV[20], miGraph[10], MI-kernel[19], Mi-SVM & mi-SVM[11]and Simple-MI[25]in most MIL data sets, such as MUSK1, MUSK2, Fox, overwhelming majority of text data sets and image data sets. Especially, compared with the existing distance measures[23,26-27], the advantages of two new distance measures include: 1)dvircan get higher prediction accuracy on some benchmark data sets and text data sets; 2)dbiacan adapts well to image data sets; and 3) Bothdviranddbiahave lower time complexity.

The contributions of this paper are summarized as follows.

(1) The DP algorithm is applied to the selection of representative bags in MIL, which improves the efficiency of finding representative bags.

(2) The virtual Hausdorff distance and min-bias distance are exploited for text data sets and image data sets respectively. They possess higher applicability and lower time complexity.

(3) Compared with state-of-the-art algorithms, the proposed SMDP algorithm has better performance on the most MIL data sets.

The rest of the paper is organized as follows. Section 1 reviews related work. Section 2 introduces several crucial concepts. Section 3 proposes our algorithm. Section 4 reports our experiments. Section 5 presents conclusions and further work.

1 Related works

Many multi-instance learning (MIL) methods have been developed since the investigation of drug activity prediction[1]. These include boosting algorithms[28-30], comparative study[25,31], diverse density[8,32-33], decision tree[34], deep learning[35-37], fast bundle algorithm[38],k-nearest neighbor algorithms[27,39-40], logistic regression algorithms[41-43], neural network[14,44-45], rule learning algorithms[46-47], and SVM algorithms[11,48]. These MIL methods solve MIL problems in diverse ways. For example, Aueretal.[28]considered a boosting approach of MIL with balls as weak hypotheses in greater detail, and applied it to some multiple instance benchmark problems. Amoresetal.[25]analyzed the performance of the fourteen methods across a variety of well-known databases, and also studied their behavior in synthetic scenarios in order to highlight their characteristics. Maronetal.[32]described a new general frame work named Diverse Density. This framework is applied to learn a simple description of a person from a series of images containing that person, to a stock selection problem, and to the drug activity prediction problem.

A common approach for MIL is to map each bag into single vector which is handled by SIL methods. Gärtneretal.[19]proposed the MI-kernel algorithm which regarded each bag as a set of feature vectors and directly applied the set-kernel. Andrewsetal.[11]proposed the MI-SVM & mi-SVM algorithms. MI-SVM tries to generalized the notion of a margin to bags and aims at maximizing the bag margin directly; mi-SVM tries to maximized the usual pattern margin, or soft-margin, jointly over hidden label variables and a linear (or kernelized) discriminant function. Zhouetal.[22]proposed the CCE algorithm which collected all instances in the bags together and clustered them intongroups. Therefore each bag was re-represented bynbinary features and single-instance classifiers can be used to distinguish different classes of bags. Zhouetal.[10]proposed the miGraph algorithm which treated the instances in the bags with non-independent and non-identical distribution to obtained a better prediction accuracy. Amores[25]proposed the Simple-MI algorithm which showed that the extracted global bag-level information generally exhibits superior performance. It is the reason why some types of methods are more successful than others. Weietal.[20]proposed mi-FV algorithms based on the fisher vector which can deal the large-scale MIL problems. Xuetal.[12]proposed the ISK algorithm which investigated data-dependent kernels that are derived directly from data. It speeded up the set-kernel computation significantly.

There are many MIL methods with semi-supervised scenario. For example, Zhouetal.[49]established a bridge between two branches by showing that MIL can be viewed as a special case of semi-supervised learning. Base on this, the experiments of MissSVM showed that solving multi-instance problems from the view of semi-supervised learning is feasible. Wangetal.[50]proposed a novel single object tracking-by-detection tracker which combined semi-supervised learning, multiple instance learning and the Bayesian theorem. Cheplyginaetal.[51]gave an overview of semi-supervised, multiple instance and transfer learning in medical imaging, both in diagnosis and segmentation tasks.

In the single-instance learning, DP clustering algorithm[24]is widely used. Duetal.[52]proposed a DP clustering based onk-nearest neighbors, and provided another option for local density calculations. Wangetal.[53]developed the active learning through DP clustering, and got a higher classification accuracy using the same number of labeled data. Duetal.[54]integrated the speed of DP clustering algorithm with the robustness of fuzzy joint points algorithm, and identified the different values of the neighborhood membership degrees of the points.

2 Preliminaries

This section describes some basis of this work, including the data model in Section 2.1, the problem statement in Section 2.2, density peaks (DP) clustering algorithm in Section 2.3 and existing distance measures in Section 2.4. Table 1 lists some notations used throughout the paper.

2.1 The data model

LetX=Rdbe thed-dimensional instances space, andS={(B1,y1),…,(Bl,yl),Bl+1,…,BN} be a data set withllabeled bags and (N-l) unlabeled bags.Skis a set of bags from thek-th class, fork∈[1..c].Bi={xi1,…,xi,ni} is a bag withniinstances fori∈[1..N], wherexij=[xij1,…,xijd]∈X.yiis the label ofBifori∈[1..l]. For binary classification,yi∈{0,1}; otherwiseyi∈[1..c]. We also denote the labeled data set bySl={(B1,y1),…,(Bl,yl)}, and the unlabeled data set bySu={Bl+1,…,BN}.

2.2 Problem statement

In the close-world scenario, the learning task is to predict unlabeled bags. The problem is stated as follows.

Problem1: Semi-supervised multi-instance learning

Input:

S={(B1,y1),…,(Bl,yl),Bl+1,…,BN}.

Table 1 Notations

Optimization objective:

2.3 Density peaks (DP) clustering algorithm

There are two popular kernels for calculatingρi,i.e. cutoff kernel and Gaussian kernel. The cutoff kernel is defined as

(1)

wheref(x) is

(2)

The Gaussian kernel is defined as

(3)

The distance to master,i.e.δiis defined as

(4)

Especially, theδiis the instance with the highest density is the maximum one. Instances with both highρiand highδitend to be cluster centers. Therefore,λiis defined as

λi=ρi×δi.

(5)

2.4 Existing distance measures

There are three off-the-shelf distance measures,i.e. average Hausdorff distance(dave)[23], maximal Hausdorff distance (dmax)[26]and minimal Hausdorff distance(dmin)[27]. Formally, for each bag-pairBi={xi1,…,xi,ni} andBj={xj1,…,xi,nj}, the distancedijindave,dmaxanddminare

(6)

(7)

(8)

whered(xia,xjb) is the distance (e.q. Euclidean distance) betweenxiaandxjb. According to Eqs. (6) (7) (8), the time complexity isO(db2N2), whereb=maxni, which is rather high.

3 The algorithm

In this section, we first present the SMDP algorithm framework in Section 3.1. Two key issues of the algorithm are analyzed, including density peaks clustering for SMDP in Section 3.3 and two new distance measures in Section 3.3.

3.1 Algorithm description

Algorithm 1 lists the SMDP framework. The initialization is implemented in Line 1.Basing on the DP algorithm, finding the most representativencbags as cluster centers are implemented in Lines 2-19. Specifically, Lines 3-8 handle binary classification data sets. Line 4 calculates the number of clustering centers. Lines 5-8 find the index ofnccluster centers. Concretely, the index of largestλjis searched in entire data set, and merged intoC. Lines 10-18 is for multi-class data sets. Line 10 sets the number of clustering tocplus one. Lines 11-15 traverse each class to get a representative bag. Lines 16-18 find a representative bag in all unlabeled ones.

Therefore, Lines 20-24 transform each bag into thenc-dimensional instances spaceRnc. All bags are traversed again in the for loop. We explicitly map every bag to a feature vector,i.e.zi, whosei-th feature corresponds to the distance between the bagBiand thej-th clustering centerBcj, as indicated in Line 22. Obviously,ziis anc-di-mensional feature vector, which is merged intoS*, as indicated in Line 23.S*will be employed to build a classifier in last step.

Algorithm 1 Semi-supervised multi-instance learning with density peaks clustering (SMDP)Input: The data set S, r for dc ratio, the proportion p of nc to NOutput:y'i, i∈[l+1..N]1: C=Ø;∥The set of representative bags ∥Step 1. Find the most representative nc bags as cluster centers2: if (c==2) then3: dc=r×max{dij}, where Bi,Bj∈S;4: nc=p×N;5: for (i∈[1..nc])do6: ci=arg maxj∈[1..N]Cλj, where Bj∈S7: C=C∪{ci};8: end for9: else10: nc=c+1;11: for (k∈[1..c])do12: dc=r×max{dij},whereBi,Bj∈Sk;13: ck=arg max λ'k,where B'k∈Sk;14: C=C∪{ck};15: end for16: dc=r×max {dij}, where Bi,Bj∈Su;17: cnc=arg max λ'k, where B'k∈Su;18: C=C∪{cnc};19: end if∥Step 2. Transform each bag into the nc-dimensional instance space Rnc20: S*=Ø;21: for (i∈[1..N])do22: zi=[zi1,…,zi,nc], where zij=di,cj;∥The distance to each center23: S*=S*∪{zi};24: end for ∥Step 3. Classify25: Build a classifier using S*l={(z1,y1),…,(zl,yl)};26: Classify instances in S*u={zl+1,…,zN} to obtain y'l+1,…,y'N

3.2 Density peaks clustering for SMDP

As shown in Lines 2-19 of the algorithm, we design a technique inspired by the DP clustering[24]to select thencrepresentatives. By regarding bags as atomic data items, the distancesdijbetween two bags are calculated in some form of distance measure. Bothρiandδiare calculated basing ondij. The cutoff kernel produces an integer value density. It may produce the same density for different bags and lead to different choices when sorting. This is rarely faced by the Gaussian kernel. Therefore, Eq. (3) was employed to calculate theρi.

The master of a bag is its closest bag with a higher density. The representativeness of the bag is calculated by multiplying its local densityρiby the distance to its masterδi,i.e.λi. For binary classification, the cutoff distancedcis set to a given ratio times the maximum distance between bags in entire data set. The representatives are recognized as the top-ncbags with high representativeness. For multi-class data sets, we find a representative bag for each class in which all bags have the same label. Simultaneously, we find a representative bag from all unlabeled ones. Therefore, thedcofi-th class is set to a given ratio times the maximum distance between bags in the class or unlabeled ones. In this way, we can maintain the characteristics of each class as much as possible. And it can effectively avoid that some representative bags may come from a same class and maximize the accuracy of the final predictions.

3.3 Two new distance measures

It is noteworthy that different distance measures are applicable to different data sets because of the geometric distribution inequality of instances in the bag. For text data sets, inspired by the Simple-MI algorithm[25], the center instance in a bag could be the representative of the bag, which is defined as

(9)

(10)

For the image data sets, we propose the min-bias distance (dbia), which is defined as

(11)

Experimentally,dviranddbiacan adapt well to text data sets and image data sets, respectively. Furthermore, compared with Eqs. (6) (7) (8), in the same data set and assumption, the time complexity of which is reduced toO(dbN2), whereb=maxni. These issues will be discussed in detail in Sections 4.3 and 4.4.

4 Experiments

In this section, we reported the results of experiments to analyze the effectiveness for SMDP algorithm. Through the experiments, we aimed to answer

1) Is the SMDP algorithm more efficient than some state-of-the-art MIL algorithms?

2) What is the benefits of multiple distance measures and new distance measures?

The experimental environment is a Windows 10 64-bit operating system, 4 GB memory, Intel (R) Core 2 Quad CPU Q9500@2.83 GHz. The source code with a graphical user interface (GUI) written in Java is available at github.com/InkiInki/Java/Multi-Instance.

4.1 Experimental setup

The experiments were undertaken on twenty-seven MIL data sets from different fields. These include five benchmark data sets[1](i.e. Musk1, Musk2, Elephant, Fox and Tiger), two image data sets[55-56](i.e. 2000-image and 1000-image) and twenty text data sets[10]commonly used in MIL. Since different distance measures were applicable to different data sets,dave[23]anddmax[26]were used in all data sets;dmin[27]was used in benchmark data sets and image data sets;dvirwas used in the benchmark data sets and text data sets;dbiawas used in the image data sets.

In benchmark data sets and image data sets, the compared algorithms were CCE[22], ISK[12], mi-FV[20], miGraph[10], MI-kernel[19], Mi-SVM & mi-SVM[11]and Simple-MI[25]. In text data set, the compared algorithms were ISK[12], miGraph[10],MI-kernel[19]and mi-FV[20]. The top-level properties of these methods are summarized in Table 2. Linear SVM denotes that a standard SVM with linear kernel and maps instances are used. SVM denotes that a standard SVM with a designed kernel and original instances are used. SVM* denotes that a modified optimization objective function is used.K-NN denote thatK-nearest neighbors is used.

The experiments were repeated ten times with different data sets. We reported the average prediction accuracy of 10-fold cross validation (10CV) and its standard deviation. The value following ‘±’ gives the standard deviation and the “best” results are shown in bold face.

4.2 Benchmark data sets

Table 3 lists the characteristics of five benchmark data sets. Detailed characteristics of these data sets are summarized in [1].

Table 4 lists the empirical results on benchmark data sets. For each data sets, the best classification accuracy of SMDP are obtained in different distance measures and proportionpofnctoNrespectively. As the empirical results shown,phas little effect on classification accuracy, distance measures has large effect on prediction accuracy. In detail,daveperforms best on MUSK1 and MUSK1,dvirperforms best on elephant anddminperforms best on fox and tiger. Finally, we use the best classification accuracy to compare with other algorithms.

Table 2 Properties of MIL methods

Table 3 Characteristics of the benchmark data sets

Table 4 Experimental results (10CV) of SMDP on benchmark data with different bag

Table 5 Accuracy (%) on five benchmark data sets

Table 5 compares SMDP with eight popular algorithms. SMDP achieves the best accuracy in MUSK1, MUSK2 and Fox data sets, and the relatively better accuracy than the remaining data sets.

4.3 Text data sets

Twenty text data sets were derived from the 20 Newsgroups corpus[10]. For each data set, the size of bags is 100, the number of positive bags is the same as the number of negative bags.

Figure 1 shows the empirical results for twenty text data sets using SMDP withdave(ave),dmax(max) anddvir(vir). Each subgraph shows the performance in a text data set. The ordinate is average accuracy, and the abscissa is the proportionpofnctoN. Solid line, dashed line and dotted line are the performance of SMDP withdave,dmaxanddvir, respectively. The maximum accuracy and standard deviation corresponding each distance measure are shown in the legend. In particular,davehas a relatively large advantage in the data set of comp.window.x,dmaxin the data set of rec.autos,dvirin the data set of comp.sys.ibm and so on.

Table 6 compares SMDP with four methods (i.e. ISK, miGraph, MI-Kernel and miFV). Concretely, SMDP achieves the best accuracy in most of these text data sets. SMDP is better than MI-Kernel and miFV on all 20 data sets, and better than ISK on 14 out of 20 data sets, and better than miGraph on 17 out of 20 data sets. In the end, the number of win/tie/lose of SMDP versus other methods is 11/0/9.

4.4 Image data sets

The data sets 2000-image and 1000-image[55-56]contain twenty and ten categories of COREL images, respectively. There are 100 images in each category. Each image is regarded as a bag and the regions of interest in an image are regarded as instances described by nine features.

Table 7 lists the empirical results on image data sets. The results show thatdbiacan adapt well to image data sets and the others cannot.

Table 8 compares SMDP with eight popular algorithms. SMDP achieves the best accuracy on 2000-image and 1000-image.

4.5 Runtime comparison of different distance mea-sures

We compared the runtime of five distance measures on five benchmark data sets. As shown in Fig. 2, the abscissa of each subgraph is the distance measures. The ordinate is the runtime (ms) of different distance measures. The results show that the time cost of bothdviranddbiais lower than the other distance measures.

Fig.1 Experimental results of SMDP on the text data sets with different distance measures anddifferent number of clustered groups (=p×N)

Table 6 Accuracy (%) on text data sets

Table 7 Experimental results (10CV) of SMDP on the image data sets with different distance measures

4.6 Discussions

Now we can answer the questions raised at the beginning of this section.

1) SMDP is more accurate than state-of-the-art methods on several MIL data sets, including three benchmark data sets, more than half text data sets and two image data sets. This is validated by Tables 5, 6 and 7. Unfortunately, it is significantly worse than some other algorithms such as ISK on the elephant and tiger data sets. The reason may be that DP clustering techniques and five distance measures do not perform well on those data sets.

2) Different distance measures are appropriate for different data sets, which can be validated by Tables 4, 7 and Fig. 1. Two new distance meas-ures have the lower time cost than existing distance measures, which can be validated by Fig. 2.

5 Conclusions and further work

This study has proposed the SMDP algorithm to handle the MIL classification problem. In the semi-supervised scenario, DP clustering algorithm and distance measure strategies were investigated. We also proposed two new distance measures,i.e.dviranddbia. Experimental results verify the effectiveness of the algorithm.

The following research topics deserve further investigation:

1) More distance measures for the algorithm framework. Currently, SMDP only employs some distance measures. Other distance measures can be adopted or designed to accommodate data with different distribution structures between bag-level or instance-level. In addition, these measures should be fine-tuned or modified to fit the MIL problem.

Fig.2 Runtime comparison of different distance measures on the benchmark data sets (nc=0.4 N)

2) Dynamic selection of appropriate distance measures in the process of finding clustering center. SMDP only employed the currently “best” distance measure basing on the empirical results.

In summary, SMDP is a comprehensive algorithm framework that can be enriched in the future.