Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/1163
Title: | Fast data reduction by space partitioning via convex hull and MBR computation |
Authors: | Giorginis, Thomas Ougiaroglou, Stefanos Evangelidis, Georgios Dervos, Dimitris A. |
Type: | Article |
Subjects: | FRASCATI::Natural sciences::Computer and information sciences |
Keywords: | Reduction by space partitioning RSP3 Classification Prototype generation Big training data Convex hull Minimum bounding rectangle (MBR) |
Issue Date: | 2022 |
Source: | Pattern Recognition |
Volume: | 126 |
First Page: | 108553 |
Abstract: | Large volumes of training data introduce high computational cost in instance-based classification. Data reduction algorithms select or generate a small (condensing) set of representative training prototypes from the available training data. The Reduction by Space Partitioning algorithm is one of the most well-known prototype generation algorithms that repetitively divides the original training data into subsets. This partitioning process needs to identify the diameter of each subset, i.e., its two farthest instances. This is a costly process since it requires the calculation of all distances between the instances in each subset. The paper introduces two new very fast variations that, instead of computing the actual diameter of a subset, choose a pair of distant-enough instances. The first variation uses instances belonging to an exact 3d convex hull of the subset, while the second one uses instances belonging to the minimum bounding rectangle of the subset. Our experimental study shows that the new variations vastly outperform the original algorithm without a penalty in classification accuracy and reduction rate. |
URI: | https://doi.org/10.1016/j.patcog.2022.108553 https://ruomo.lib.uom.gr/handle/7000/1163 |
ISSN: | 0031-3203 |
Other Identifiers: | 10.1016/j.patcog.2022.108553 |
Appears in Collections: | Department of Applied Informatics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2021_PR_RSPR3_with_Convex_hull.pdf | 553,44 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.