MICkNN: Multi-Instance Covering kNN Algorithm

Constructive Covering Algorithm (CCA) was proposed by Zhang and Zhang^{[ 35 ]} in 1999, as a constructive supervised learning algorithm for McCulloch-Pitts Neural Model^{[ 36 ]}. The main idea of CCA is mapping all patterns in the data set to a d-dimensional sphere $S^d$ at first. Then the sphere neighbors (Covers) are utilized to divide the patterns.

Given a classification data set $D=\{X_i|X_i=(x_i,y_i),i=1,2,\mathrm{\cdots },N,y_i=1,2,\mathrm{\cdots },m\}$ , where $x_i\in {\text{𝐑}}^d$ , $y$ represents $m$ classes. Let N and d be the size and dimension of $D$ , $X_i=(x_i,y_i)$ be a pattern in $D$ . Let $D_i$ be a subset of $D$ , which contains all the patterns of the $i$ -th class, $i=1,2,\mathrm{\cdots },m$ . The classification model created by CCA is a cover set: $C=\{C_i|C_i=(c,r),i=1,2,\mathrm{\cdots }\}$ , where $c$ is the center of a cover, $r$ is its radius.

Since the dimension of instances in MI data set is identical, all input vectors can be restricted to a $d$ -dimensional hyper-sphere $S^d$ . The input vector is a bounded set $D$ of the $d$ -dimensional space.

Define a transformation $T$ :

(1) $$T(x)=(x,\sqrt{R^2-{\Vert x\Vert }^2}),R⩾\max \{\Vert x\Vert |x\in D\}$$

Use $T$ to do a projection: $T$ : $D\to S^d$ , $S^d$ is a $d$ -dimensional sphere of the $(d+1)$ -dimensional space. $R$ is the radius of the $(d+1)$ -dimensional space, the value of $R$ must be greater or equal to the maximum value of the mold length of all the instances. $\sqrt{R^2-{\Vert x\Vert }^2}$ is the additional value of $x$ , i.e., the value of the $(d+1)$ -dimension after projection as shown in Fig. 2 .

10.1109/TST.2013.6574674.F002 Fig. 2Input vectors of instance x and their projections.

After all the instances in $D$ are projected upward on $S^d$ by transformation $T$ , construct a series of positive covers ( "positive sphere neighbors" ) that only consist of instances in the positive bags and a series of negative covers ( "negative sphere neighbors" ) that only consist of instances in the negative bags. This procedure is shown as follows.

To generate the sphere neighbors that only contain instances belonging to the same class, first of all, select an instance $x_i\in D$ , randomly. Let $X$ be the set of instances has the same label as $x_i$ . Therefore, the set of instances has the opposite label from $x_i$ can be denoted as $\tilde{X}$ .

Then, we compute the distance $d_1$ between $x_i$ and $\widetilde{x_j}$ , $\widetilde{x_j}$ is the nearest instance from $x_i$ which belongs to the set of $\tilde{X}$ and the distance $d_2$ between $x_i$ and $x_k$ , where $x_k$ is the furthest instance from $x_i$ which belongs to the set of $X$ . Note that in CCA, $d_2$ must be smaller than $d_1$ .

The above procedure can be expressed as Eqs. ( 2 ) and ( 3 ):

(2) $$d_1=\max \{<x_i,\widetilde{x_j}>|x_i\in X,x_j\in \tilde{X}\}$$

(3) $$d_2=\min \{<x_i,x_k>|x_i,x_k\in X,<x_i,x_k\gg d_1\}$$

where $⟨a,b⟩$ denotes the "inner product" between instances $a$ and $b$ . Note that the bigger "inner product" indicates the smaller distance.

Next, we calculate the radius of a sphere neighbor so that in this sphere neighbor there are only instances belonging to the same class (See Fig. 3 ). Let $r$ be the radius of a sphere neighbor. The following formula is utilized to calculate the value of $r$ :

(4) $$r=(d_1+d_2)/2$$

10.1109/TST.2013.6574674.F003 Fig. 3A sphere neighbor for classification.

The basic constructive covering algorithm is shown in Algorithm 1.

We are inspired by the inherent feature of CCA. That is, the learning results of CCA is a series of $Covers$ , each of which only contains samples belonging to the same class. It is this feature that makes CCA very suitable for breaking through and reorganizing the structure of MI data.

k-Nearest Neighbor (kNN) algorithm^{[ 37 ]} is one of the most popular learning algorithms in data mining. kNN is well known for its relatively simple implementation and decent results. The main idea of kNN algorithm is to find a set of k objects in the training data that are close to the test pattern, and base the assignment of a label on the predominance of a particular class in this neighbor. kNN is a lazy learning technique based on voting and distances of the k nearest neighbors. Given a training set $D$ and a test pattern $x$ , kNN computes the similarity (distance) between $x$ and the nearest k neighbors. The label of $x$ is assigned by voting from the majority of neighbors.

The basic kNN algorithm is shown in Algorithm 2.

An example of the original distribution of MI data in the two-dimensional space is given in Fig. 4 .

10.1109/TST.2013.6574674.F004 Fig. 4The original distribution of MI bags before preprocess.

Unfilled shapes represent feature vectors of positive bags and filled shapes represent feature vectors of negative bags. All points of the same shape denote feature vectors of the same bag. For example, the bag "unfilled regular hexagon" is a positive bag and it has four instances. As Fig. 4 depicts, from the distribution of instances in each positive bag, we cannot find the distribution pattern that the instances in each positive bag have got to abide due to the existence of the false positive instances in each positive bag. Specifically, it is difficult to find a linear or non-linear dividing line to separate the positive bags and the negative bags precisely. On the other hand, the distribution of instances in the same positive bag is random and discrete. From our perspective, it is precisely because of the irregular structural features of the positive bags, i.e., the ambiguity of the positive bags leads to the inherent difficulty of MI problem.

The learning result of CCA is a $\mathrm{𝐶𝑜𝑣𝑒𝑟}$ set and this feature that makes CCA very suitable for breaking through and restructuring the structure of MI data. By regarding the $\mathrm{𝐶𝑜𝑣𝑒𝑟}$ set as the new structure of MI bags, the original structure of bags is reorganized from irregular to regular, so that the false positive instances can be excluded.

In order to discriminate the noises in the positive bags, construct a set $\mathrm{PCover}=\{{\mathrm{PCover}}_i|i=1,2,\mathrm{\cdots },p\}$ that only contains instances from the positive bags and a set $\mathrm{NCover}$ = $\{{\mathrm{NCover}}_j|j=1,2,\mathrm{\cdots },n\}$ that only contains instances from the negative bags, respectively. Thus, the irregular discrete structure of bag can be broken through by converting the original data set into a set $\text{Cover}=\text{PCover}\bigcup \text{NCover}$ as depicted in Fig. 5 . The new structure $Cover$ is very convenient for excluding the false positive instances in the positive sphere neighbors by using kNN algorithm. The details are as follows.

10.1109/TST.2013.6574674.F005 Fig. 5The bag structure of MI data set after preprocess. Instances from negative bags are covered by "thick lines" ; instance from positive bags are covered by "thin lines" .

First, construct the set $\mathrm{Cover}$ by using CCA. After this procedure, kNN is utilized to exclude the false positive sphere neighbors that mainly consist of false positive instances. According to the kNN algorithm, a ${\mathrm{Cover}}_i$ obtained by CCA is considered as a whole. For each ${\mathrm{PCover}}_i$ , if the majority of its nearest neighbors are belong to the set $\mathrm{NCover}$ , we delete it from the set $\mathrm{PCover}$ and add it to the set $\mathrm{NCover}$ . The distance between ${\mathrm{Cover}}_i$ and ${\mathrm{Cover}}_j$ can be calculated by using Hausdorff distance. Edgar^{[ 38 ]} and Wang and Zucker^{[ 29 ]} pointed out two kinds of such Hausdorff distance, that is maximal Hausdorff distance (maxHD) and minimal Hausdorff distance (minHD ).

According to the definition, given two sets of instances $A=\{a_1,\mathrm{\cdots },a_m\}$ and $B=\{b_1,\mathrm{\cdots },b_n\}$ .

The maxHD is defined as

(5) $$\mathrm{maxHD}(A,B)=\max \{h(A,B),h(B,A)\}$$

where

(6) $$h(A,B)=\underset{a\in A}{\max }\underset{b\in B}{\min }\Vert a-b\Vert$$

The minHD is defined as

(7) $$\mathrm{minHD}(A,B)=\min \Vert a-b\Vert$$

where $\Vert a-b\Vert$ is the Euclidean distance between instance $a$ and instance $b$ .

The complete description of excluding the noises in positive bags is illustrated in Algorithm 3.

After preprocess the MI data in the first stage, the original structure of MI data set is converted into positive cover set $\mathrm{PCover}$ and negative cover set $\mathrm{NCover}$ . In addition, a fair amount of false positive instances in the set $\mathrm{PCover}$ are excluded.

In this stage, a ${\mathrm{PCover}}_i$ or an ${\mathrm{NCover}}_j$ is treated as the new structure of a bag, then the kNN algorithm at the bag-level is utilized to predict the real labels of the unknown bags. Because of a large number of noises in the positive bags are excluded during the procedures above. It is quite convenient to predict the labels of test bags by using kNN algorithm at the bag-level. We compute the similarity between each test bag and its nearest neighbors, if there are more negative $Covers$ around a test bag, the label of the test bag is negative, otherwise positive. The complete description of the predict algorithm is illustrated in Algorithm 4.