Fixed neighborhood sphere and pattern selection in SVDD

摘要

For the problem of a large dataset, we need to select a subset to represent the original dataset. Many scholars do pattern selection from the problem of the kNN (k-nearest neighbors). The distribution of a pattern's neighbors is usually uneven. In this paper, we define a fixed neighborhood sphere. When the pattern locates near the boundary of the data distribution, there will be fewer neighbors in the neighborhood sphere and when the pattern locates within the data distribution, there will be more neighbors in the neighborhood sphere. According to gather the statistic of the neighbors in a fixed neighborhood sphere, we can find those patterns locating near the boundary of the data distribution. In SVDD (Support Vector Data Description), those patterns are locating near the boundary of the data distribution have more information. They are those patterns which would be support vectors. We can use FNSPS (fixed neighborhood sphere pattern selection) algorithm to select those patterns, which locate near the boundary of the data distribution. The experimental results show that the performance of the SVDD will not go bad. The time complexity of the naive identifying the neighbors in the fixed neighborhood sphere is O(n2). And the time complexity of the SVDD is O(n3). If we set a lower threshold, the FNSPS algorithm can also be used to remove the noise in the targets.