Multiple-Instance Learning with Instance Selection via Constructive Covering Algorithm

Multiple-Instance Learning （MIL） is used to predict the unlabeled bags＇ label by learning the labeled positive training bags and negative training bags.Each bag is made up of several unlabeled instances.A bag is labeled positive if at least one of its instances is positive,otherwise negative.Existing multiple-instance learning methods with instance selection ignore the representative degree of the selected instances.For example,if an instance has many similar instances with the same label around it,the instance should be more representative than others.Based on this idea,in this paper,a multiple-instance learning with instance selection via constructive covering algorithm （MilCa） is proposed.In MilCa,we firstly use maximal Hausdorff to select some initial positive instances from positive bags,then use a Constructive Covering Algorithm （CCA） to restructure the structure of the original instances of negative bags.Then an inverse testing process is employed to exclude the false positive instances from positive bags and to select the high representative degree instances ordered by the number of covered instances from training bags.Finally,a similarity measure function is used to convert the training bag into a single sample and CCA is again used to classification for the converted samples.Experimental results on synthetic data and standard benchmark datasets demonstrate that MilCa can decrease the number of the selected instances and it is competitive with the state-of-the-art MIL algorithms.

MICkNN:Multi-Instance Covering kNN Algorithm

Mining from ambiguous data is very important in data mining. This paper discusses one of the tasks for mining from ambiguous data known as multi-instance problem. In multi-instance problem, each pattern is a labeled bag that consists of a number of unlabeled instances. A bag is negative if all instances in it are negative. A bag is positive if it has at least one positive instance. Because the instances in the positive bag are not labeled, each positive bag is an ambiguous. The mining aim is to classify unseen bags. The main idea of existing multi-instance algorithms is to find true positive instances in positive bags and convert the multi-instance problem to the supervised problem, and get the labels of test bags according to predict the labels of unknown instances. In this paper, we aim at mining the multi-instance data from another point of view, i.e., excluding the false positive instances in positive bags and predicting the label of an entire unknown bag. We propose an algorithm called Multi-Instance Covering kNN （MICkNN） for mining from multi-instance data. Briefly, constructive covering algorithm is utilized to restructure the structure of the original multi-instance data at first. Then, the kNN algorithm is applied to discriminate the false positive instances. In the test stage, we label the tested bag directly according to the similarity between the unseen bag and sphere neighbors obtained from last two steps. Experimental results demonstrate the proposed algorithm is competitive with most of the state-of-the-art multi-instance methods both in classification accuracy and running time.