Fuzzy-Citation-KNN: a fuzzy nearest neighbor approach for multi-instance classification

c 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Title: Fuzzy-Citation-KNN: a fuzzy nearest neighbor approach for multi-instance classification Authors: Pedro Villar, Rosana Montes, Ana Mar´ıa S´anchez, Francisco Herrera Event: IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2016), Vancouver (Canada), pp.946-952, july 24-29, 2016. DOI: 10.1109/FUZZ-IEEE.2016.7737790 Fuzzy-Citation-KNN: a fuzzy nearest neighbor approach for multi-instance classification Pedro Villara, Rosana Montesa, Ana Mar´ıa S´ancheza, Francisco Herrerab aDept. of Software Engineering; University of Granada 18071 - Granada, Spain. e-mail: pvillarc,rosana,amlop[email protected] bDept. of Computer Science and A.I.; University of Granada, 18071 - Granada, Spain. e-mail: ocordon,[email protected] Abstract This contribution deals with multi-instance classification, where the labeled data samples are bags composed on instances instead of labeled instances as in standard classification. Every bag contains a number of traditional instances (described by a number of attributes) and the number of instances is not usually the same in all the bags. So, the whole bag is labeled but the instances that compose the bag are not individually labeled. We propose a fuzzy sets based extension of the well known algorithm called Citation-KNN, a reference method in multi-instance classification. Citation-KNN uses two types of examples in the classification rule: neighbors and citers of the bag to be classified. We analyze two versions of our proposal, one of them using both neighbors and citers, and the other one using only neighbors. Our approach uses the Hausdorff distance and it is based on the FuzzyKNN algorithm. Several data-sets from KEEL data-set repository are used in the experimental study and we compare our proposals with the original Citation-KNN algorithm. 1 Introduction In multi-instance classification (MIC)[1], the data examples are unordered collections (bags) of instances. The instances are similar than the examples used in standard classification. So, all the instances have the same structure. On the other hand, the number of instances can vary among bags. The main characteristic of MIC is the absence of the classification label in each instance, the class label is assigned to the bag as a whole. Therefore, the data-sets used in MIC are more complex than the used in standard classification and it is necessary to use specific learning algorithms to classify unknown bags. There are several algorithms for dealing with MIC in the specialized literature [2] [3]. Many of them are based on algorithms proposed for standard classification. One example is the Citation-KNN algorithm [4], a MIC learning 2 method based on the well known k-nearest neighbor classification algorithm. Citation-KNN uses in its classification rule the ”citers” of the bag to be classified, apart from the neighbors of that bag. Citers are the bags that include the bag to be classified in their neighboring. When applying a k-nearest neighbor approach, a way to measure the distance between two examples is needed. In the context of MIC, an example is a bag that contains multiple instances. Therefore, it is necessary to characterize how the distance between two sets of instances could be measured. We will employ the same metric used in the description of Citation-KNN [4]: the Hausdorff distance. Fuzzy sets theory have been widely used in many traditional (single-instance) machine learning applications, specially in classification tasks, but so far not in MIC. In a recent contribution [5], a framework for multi-instance classifiers based on fuzzy set theory is presented. From the best of our knowledge, there are no proposals of fuzzy nearest neighbor approaches adapted to MIC. In [6], a fuzzy-based adaptation of the K-Nearest Neighbor algorithm is proposed (FuzzyKNN). This method is considered the major reference in the combination of fuzzy logic and K-nearest neighbor. A recent published review [7] in fuzzy nearest neighbors algorithms, performs a comparative study among many proposals and FuzzyKNN obtains very accurate results. The main purpose of this contribution is to extend the Citation-KNN algorithm, proposing a fuzzy-based adaptation of that method. We will use in our learning method some ideas used for designing the FuzzyKNN algorithm. Our proposal includes a preliminary phase in which membership values for each class are calculated for every example of the training data-set. For classifying a new example, a membership degree for each class is computed, considering the membership values obtained in the first phase weighted by the distance to the new example. The class with greater membership degree is assigned. We will analyze two variants depending on the examples used for calculating the class membership degree: one of them considers both neighbors and citers of the new example, and the other one only considers the neighbors. In order to illustrate the good performance of the proposed fuzzy citationKNN algorithm, we will compare the obtained results among the original CitationKNN method and the two versions of our proposal: with and without considering the citers in the classification rule. We have selected a collection of binary-class MIC data-sets from KEEL data-set repository [8] for developing our experimental analysis. Furthermore, we will perform a statistical analysis using non-parametric tests [9] [10] [11] to find significant differences among the obtained results. This paper is organized as follows. First, Section 2 introduces the preliminary concepts used in this paper: multi-instance classification, the distance metric used (Hausdorff distance) and the Citation-KNN algorithm. Next, in Section 3 we will describe our proposal, a fuzzy-based approach of the CitationKNN algorithm. The next section describes the experimental study. Finally, in Section 5, some conclusions will be pointed out. Figure 1: Hausdorff distance in a two-dimensional instance space 2 Preliminaries This section introduces the main concepts of multi-instance classification, defines the Hausdorff distance and describes the algorithm used for design our proposal: Citation-KNN. 2.1 Multi-instance classification Multi-instance classification(MIC) was originally described in [1] and it has received much attention since that seminal paper. There are several application areas where MIC have been used. The drug activity was the first problem trying to be solved by MIC [1]. Other examples are image classification [12], contentbased image retrieval [13] [14], web index page recomendation [15], robot control [16] and bioinformatics [17]. A multi-instance data-set for a MIC problem has the following structure: T={(X1, l1),(X2, l2),...,(Xn, ln)} Where Xi∈2χare labeled bags, that is, composed of non-labeled instances whose universe of discourse is χ, which corresponds to the feature set describing the instances. The value liis the class associated to the bag Xiand it is assumed to be drawn from a finite set L. A multi-instance classifier Γ try to predict the label of a new unlabeled bag, that is: Γ:2χ→L There are several ways to group the MIC algorithms. Usual taxonomies are based on the information level used to classify new bags. In [2], the multiinstance classifiers are divided into three groups. One of them is called the instance space paradigm, where the classification task rely on the instancelevel information. The other two groups use the bag-level information for the classification task: the bag-space paradigm and the embedded space paradigm. A brief description of each paradigm is presented next: •Instance space paradigm: In this paradigm, a instance-level classifier is build to discriminate the instances in positive bags from those in negative ones. The final bag-level classifier is obtained by aggregating instancelevel scores. The learning process considers the characteristic of individual instances, not the characteristics of the whole bag. Methods of this paradigm are Axis-Paralel Rectangle [1], Diverse Density [18] and miSVM [19]. •Bag space paradigm: In this case, the classification of a new bag rely on the information provided for the whole bag, not for the individual instances. Algorithms that follow this paradigm are Citation-KNN [4] and MI-Graph [20]. •Embedded space paradigm: this paradigm performs a mapping from the bag space to a single vector space. Next, a traditional single-instance classifier is trained. Examples are SimpleMI [21], YARDS [22], DD-SVM [23], MILES [24], GMIL [25] and BARTMIP [26]. Figure 2: 2-nearest citers of bag 6 2.2 Distance metric All methods that follow the nearest neighbor approach consider a subgroup of nearest elements in the classification process. Therefore, it is necessary to choose a distance value between two bags in a multi-instance framework. However, a bag is an unordered set of instances and two bags can contain different number of instances. There are some metrics proposed in the MIC literature: the Hausdorff distance (used in Citation-KNN algorithm) [4], the Earth Movers Distance (EMD) [27], the Chamfer distance [28], etc. Given two set of instances A={a1, . . . , an}and B={b1, . . . , bm}, the Hausdorff distance (H(A, B)) is defined as [4]: H(A, B) = max{h(A, B), h(B, A)} where h(A, B) = max a∈Amin b∈Bka−bk The Hausdorff distance is very sensitive to a single outlying point of A or B. To increase the robustness with respect to noise, a possible modification to the Hausdorff distance is to take the k-th ranked distance rather than the largest ranked one: hk(A, B) = kth a∈Amin b∈Bka−bk When k=m, the distance is the same as h(A, B) defined above and it is called the maximal Hausdorff distance. When k= 1, the minimal one of the m distances determines the value of the distance: h1(A, B) = min a∈Amin b∈Bka−bk=min b∈Bmin a∈Akb−ak=h1(B, A) In this case H(A, B) = H(B, A) = h1(A, B) = h1(B, A). We will use this minimal Hausdorff distance due to its better behavior than the original formulation (maximal Hausdorff distance), as it is shown in the experiments developed in [4]. A graphical example of the Hausdorff distance in a two-dimensional instance space is shown in Figure 1. 2.3 Citation-KNN algorithm This algorithm [4] was designed specifically for MIC and follows the nearest neighbor approach. For classifying a new bag b, Citation-KNN not only considers the neighbors of b(called references in [4]), but also considers the bags that count bas a neighbor (called citers). Therefore, the K-nearest references of bare the K-nearest neighbors of b. For setting up the C-nearest citers, the C-nearest neighbors of all bags are located. Next, every bag that includes bin his C-nearest neighboring is a citer of b. We must note that, given a Cvalue, the number of citers of a bag cannot be determined a priori. For example, given a data-set with five bags {b1, b2, b3, b4, b5}, their nearest neighbors are shown in Table 1. Therefore, if K= 3, the K-nearest neighbors of b3are {b4, b6, b1}. On the other hand, if C= 2, the C-nearest citers of b4is the set {b1, b3, b5, b6}, the C-nearest citers of b2is the set {b1}, the C-nearest citers of b6is the set {b3, b5} and there are no C-nearest citers for b5. Figure 2 shows graphically the process of calculating the 2-nearest citers of one bag. In the figure, a two dimensional distribution of bags is considered and the euclidean distance between two bags is equivalent to the minimal Hausdorff distance of these two bags, following the relationship shown in Table 1. In the original description of Citation-KNN [4], the value Cwas empirically set to K+ 2, reflecting that citers seem to be more important than neighbors. Therefore, Citation-KNN needs to give a distance metric and two parameters. The minimal Hausdorff distance is proposed in the definition paper. One Table 1: Nearest neighbors of six bags K= 1 K= 2 K= 3 K= 4 K= 5 b1b4b2b3b6b5 b2b1b3b4b6b5 b3b4b6b1b2b5 b4b1b3b6b2b5 b5b6b4b1b3b2 b6b4b3b5b1b2 µc(b) = K X i=1 µc(xi)(1/kb−xik2/(m−1)) + nc(b) X j=1 µc(xj)(1/kb−xjk2/(m−1)) K X i=1 (1/kb−xik2/(m−1)) + nc(b) X j=1 (1/kb−xjk2/(m−1)) (1) of the parameters is the number of references (or neighbors), the parameter K, and the other one is the parameter C, that determines the set of citers. Considering binary-class MIC problems, four values are calculated for deriving the class label of a new unseen bag b. Being Ne(b) the set of K-nearest neighbors of bkand Ci(b) the set of C-nearest citers of b, the values are: •Kp: Number of positive bags in Ne(b) •Kn: Number of negative bags in Ne(b) •Cp: Number of positive bags in Ci(b) •Cn: Number of negative bags in Ci(b) Once these values have been calculated, the classification rule is: if (Kp+Cp> Kn+Cn)then class =positive else class =negative end if return(class) Obviously, Kp+Kn=K, but the total number of citers (Cp+Cn) is not known a priori. Therefore, whether Kis odd or even and wether Cis odd or even, the sum Kp+Cp+Kn+Cncan be an even number. So, a tie between the number of positive bags and negative bags is possible. In the original CitationKNN algorithm [4], the tie is always solved assigning the negative class to the bag (as in the classification rule shown before). This decision was caused by the two data-sets used for testing the algorithm in the paper (musk1 and musk2). In the musk1 data-set, the authors found some contradictory cases of negative bags with majority of positive bags in their neighbors. We think that decision can be justified if there is some bonus information about a concrete data-set as in the previous case. When using Citation-KNN as a general purpose MIC learning algorithm, we think that the possible ties must be resolved by means of a more generic rule, as we will explain in the experimental section. 3 Fuzzy-based approach of Citation-KNN algorithm In this section we present our proposal, a new fuzzy-based algorithm for MIC that follows the structure of Citation-KNN. The method is composed of two stages: •A preliminary phase where class membership are derived, obtaining a value in [0,1] for each instance and class of the training data-set. In [6] three possibilities for computing these membership values was proposed, being the ’crisp’ option one of them. The best performing method needs, for each instance xiof the training data-set, to compute its kinit nearest neighbors. Then, the membership values are assigned according the following function: µc(xi) = (0.51 + (vc/kinit)×0.49 if c=ω (vc/kinit)×0.49 otherwise where vcis the number of neighbors belonging to class cand ωis the original class label of xi. The parameter kinit is usually set to a value between {3,...,10}[7]. The sum of all the membership values will always be 1. The effect of eq.3 is that bags close to the center of the class distribution keep their original crisp membership values (1.0 to the original class and 0.0 to the rest of classes). However, bags close to the boundaries among classes divide part of their membership values among the nearest classes. We must note that the coefficients ensure that the largest membership value will be assigned to the ωclass, regardless of the neighboring bags. •Classification rule. For a new unseen bag b, the K-nearest neighbors and the C-nearest citers are computed as well as described for the CitationKNN algorithm. Then, a membership degree of bin each class is calculated, where each neighbor of band each citer of bvotes for each class using their membership values previously computed. These votes are weighted over the inverse of the distance to b. Finally, all votes are added according the equation used (equation 1). In that equation, nc(b) is the number of citers of bag b. It can be seen that the neighbors of band the citers of bcontributes equally to the calculus. The parameter mdetermines how heavily the distance is weighted when calculating each neighbor or citer contribution to the membership value. As mincreases, the relative distances from bhave less effect. As mapproaches to one, the closer neighbors contribute much more than those farther away. Finally, the class with the greatest combined vote is assigned to b. In the unlikely case of a tie between combined votes, the class of the nearest neighbor to bis the final prediction. An advantage of using this fuzzy scheme is the level of assurance in the classification, provided for the class membership values [6]. Therefore, considering a binary-class MIC problem, the classification rule is: if (µp(b)> µn(b)) then class =positive else if (µp(b)< µn(b)) then class =negative else class = 1NN(b) end if end if return(class) Where µp(b) is the membership value obtained for the positive class, µn(b) is the membership value of the negative class and 1NN(b) is the class of the nearest neighbor of b. We denote this proposal as FuzzyCitation-KNN, since it is a fuzzy-based extension of the Citation-KNN algorithm. We are also interested in analyze the behavior of our proposal in a more classical nearest neighbor way, in that the classification rule ignores the citers and only uses the neighbors. In this case, the classification rule remains equal than FuzzyCitation-KNN but the calculus of the membership degree of bin each class is modified. So, the equation of figure 3 is simplified as it only considers the contribution of the neighbors: µc(b) = K X i=1 µc(xi)(1/kb−xik2/(m−1)) K X i=1 (1/kb−xik2/(m−1)) Therefore, this last approach can be considered a MIC adaptation of the FuzzyKNN method [6] and we have denoted this algorithm as FuzzyKNN-MIC. 4 Experimental Study In this section, we will first provide details of the binary class multi-instance problems chosen for the experimentation (subsection 4.1). Next, we will in- [28] S. Belongie, J. Malik and J. Puzicha, Shape matching and object recognition using shape contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4): 509–522, 2002.