Robust linear separation of multiple finite sets.

摘要

Given K disjoint finite sets AkK k=1 in Euclidean n-space, a general problem with numerous applications is to find K simple nontrivial functions fk(x) which separate the sets {lcub} Ak{rcub} in the sense that fk( x) ≤ fi(x) for all a in Ak and i ≠ k, k = 1,...,K. Typically one seeks linear functions fk(x). When such linear functions exist we say that the sets {lcub}Ak{rcub} are simply separable. If the sets are simply separable, there are generally many functions that separate. In this case we seek a 'best' separator in the sense that a measure of Euclidean distance between the separator and the sets is as large as possible. That separator is referred as a robust separator. If the sets are not simply separable, we seek a function that separates the sets pairwise. In this case we are also looking for a robust pairwise separator. In general, the K sets AkK k=1 can always be separated with the piecewise linear function obtained by the Voronoi Partition defined for the points in ∪Kk=1Ak . This function provides the robust separator by definition.; Three distinct robust approaches are proposed in this dissertation: Simple Separation of multiple sets, Pairwise Separation, and separation via the Voronoi Partition. The Simple Separation procedure can be applied to sets that are simply separable. The second approach, Pairwise Separation, is used when the sets are not simply separable, but are separable pairwise. Finally, the Voronoi Partition can be applied to any collection of sets.; To test the efficiency of our methodology, two types of computational experiments were performed: one based on randomly generated data, and the other based on established databases. In both cases, we show that our methods are efficient and accurate.