Neighborhood Linear Discriminant Analysis

Abstract Linear Discriminant Analysis (LDA) assumes that all samples from the same class are independently and identically distributed (i.i.d.). LDA may fail in the cases where the assumption does not hold. Particularly when a class contains several clusters (or subclasses), LDA cannot correctly depict the internal structure as the scatter matrices that LDA relies on are defined at the class level. In order to mitigate the problem, this paper proposes a neighborhood linear discriminant analysis (nLDA) in which the scatter matrices are defined on a neighborhood consisting of reverse nearest neighbors. Thus, the new discriminator does not need an i.i.d. assumption. In addition, the neighborhood can be naturally regarded as the smallest subclass, for which it is easier to be obtained than subclass without resorting to any clustering algorithms. The projected directions are sought to make sure that the within-neighborhood scatter as small as possible and the between-neighborhood scatter as large as possible, simultaneously. The experimental results show that nLDA performs significantly better than previous discriminators, such as LDA, LFDA, ccLDA, LM-NNDA, and l 2 , 1 -RLDA.