Byunghyun Baek, Seongyul Euh, Doosung Hwang

KIPS Transactions on Software and Data Engineering, Vol. 9, No. 3, pp. 83-90, Mar. 2020
https://doi.org/10.3745/KTSDE.2020.9.3.83,   PDF Download:
Keywords: Prototype Selection, Prototype, Hyper-Rectangle, Set Cover Optimization Algorithm
Abstract

Prototype selection offers the advantage of ensuring low learning time and storage space by selecting the minimum data representative of in-class partitions from the training data. This paper designs a new training data generation method using hyper-rectangles that can be applied to general classification algorithms. Hyper-rectangular regions do not contain different class data and divide the same class space. The median value of the data within a hyper-rectangle is selected as a prototype to form new training data, and the size of the hyper-rectangle is adjusted to reflect the data distribution in the class area. A set cover optimization algorithm is proposed to select the minimum prototype set that represents the whole training data. The proposed method reduces the time complexity that requires the polynomial time of the set cover optimization algorithm by using the greedy algorithm and the distance equation without multiplication. In experimented comparison with hyper-sphere prototype selections, the proposed method is superior in terms of prototype rate and generalization performance.

Statistics
Cite this article