Affiliations: [a] Orleans University, Laboratoire Prisme Orléans, Orléans, France | [b] PILA, Saint Jean de la Ruelle, France | [c] IRSTEA, UMR ITAP, Montpellier, France
Abstract: In this paper, a new instance selection algorithm is proposed in the context
of classification to manage non-trivial database sizes. The algorithm is
hybrid and runs with only a few parameters that directly control the balance
between the three objectives of classification, i.e. errors, storage
requirements and runtime. It comprises different mechanisms involving
neighborhood and stratification algorithms that specifically speed up the
runtime without significantly degrading efficiency. Instead of applying an
IS (Instance Selection) algorithm to the whole database, IS is applied to
strata deriving from the regions, each region representing a set of patterns
selected from the original training set. The application of IS is
conditioned by the purity of each region (i.e. the extent to which different
categories of patterns are mixed in the region) and the stratification
strategy is adapted to the region components. For each region, the number of
delivered instances is firstly limited via the use of an iterative process
that takes into account the boundary complexity, and secondly optimized by
removing the superfluous ones. The sets of instances determined from all the
regions are put together to provide an intermediate instance set that
undergoes a dedicated filtering process to deliver the final set.
Experiments performed with various synthetic and real data sets demonstrate
the advantages of the proposed approach.
