Advanced search
1 file | 833.73 KB Add to list

Scalable approximate FRNN-OWA classification

Oliver Urs Lenz (UGent) , Daniel Peralta (UGent) and Chris Cornelis (UGent)
Author
Organization
Abstract
Fuzzy Rough Nearest Neighbour classification with Ordered Weighted Averaging operators (FRNN-OWA) is an algorithm that classifies unseen instances according to their membership in the fuzzy upper and lower approximations of the decision classes. Previous research has shown that the use of OWA operators increases the robustness of this model. However, calculating membership in an approximation requires a nearest neighbour search. In practice, the query time complexity of exact nearest neighbour search algorithms in more than a handful of dimensions is near-linear, which limits the scalability of FRNN-OWA. Therefore, we propose approximate FRNN-OWA, a modified model that calculates upper and lower approximations of decision classes using the approximate nearest neighbours returned by Hierarchical Navigable Small Worlds (HNSW), a recent approximative nearest neighbour search algorithm with logarithmic query time complexity at constant near-100% accuracy. We demonstrate that approximate FRNN-OWA is sufficiently robust to match the classification accuracy of exact FRNN-OWA while scaling much more efficiently. We test four parameter configurations of HNSW, and evaluate their performance by measuring classification accuracy and construction and query times for samples of various sizes from three large datasets. We find that with two of the parameter configurations, approximate FRNN-OWA achieves near-identical accuracy to exact FRNN-OWA for most sample sizes within query times that are up to several orders of magnitude faster.
Keywords
big data applications, classification algorithms, fuzzy rough sets, nearest neighbor searches, scalability

Downloads

  • 20191024 lenz et al preprint.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 833.73 KB

Citation

Please use this url to cite or link to this publication:

MLA
Lenz, Oliver Urs, et al. “Scalable Approximate FRNN-OWA Classification.” IEEE TRANSACTIONS ON FUZZY SYSTEMS, 2019.
APA
Lenz, O. U., Peralta, D., & Cornelis, C. (2019). Scalable approximate FRNN-OWA classification. IEEE TRANSACTIONS ON FUZZY SYSTEMS.
Chicago author-date
Lenz, Oliver Urs, Daniel Peralta, and Chris Cornelis. 2019. “Scalable Approximate FRNN-OWA Classification.” IEEE TRANSACTIONS ON FUZZY SYSTEMS.
Chicago author-date (all authors)
Lenz, Oliver Urs, Daniel Peralta, and Chris Cornelis. 2019. “Scalable Approximate FRNN-OWA Classification.” IEEE TRANSACTIONS ON FUZZY SYSTEMS.
Vancouver
1.
Lenz OU, Peralta D, Cornelis C. Scalable approximate FRNN-OWA classification. IEEE TRANSACTIONS ON FUZZY SYSTEMS. 2019;
IEEE
[1]
O. U. Lenz, D. Peralta, and C. Cornelis, “Scalable approximate FRNN-OWA classification,” IEEE TRANSACTIONS ON FUZZY SYSTEMS, 2019.
@article{8633099,
  abstract     = {Fuzzy Rough Nearest Neighbour classification with Ordered Weighted Averaging operators (FRNN-OWA) is an algorithm that classifies unseen instances according to their membership in the fuzzy upper and lower approximations of the decision classes. Previous research has shown that the use of OWA operators increases the robustness of this model. However, calculating membership in an approximation requires a nearest neighbour search. In practice, the query time complexity of exact nearest neighbour search algorithms in more than a handful of dimensions is near-linear, which limits the scalability of FRNN-OWA. Therefore, we propose approximate FRNN-OWA, a modified model that calculates upper and lower approximations of decision classes using the approximate nearest neighbours returned by Hierarchical Navigable Small Worlds (HNSW), a recent approximative nearest neighbour search algorithm with logarithmic query time complexity at constant near-100% accuracy. We demonstrate that approximate FRNN-OWA is sufficiently robust to match the classification accuracy of exact FRNN-OWA while scaling much more efficiently. We test four parameter configurations of HNSW, and evaluate their performance by measuring classification accuracy and construction and query times for samples of various sizes from three large datasets. We find that with two of the parameter configurations, approximate FRNN-OWA achieves near-identical accuracy to exact FRNN-OWA for most sample sizes within query times that are up to several orders of magnitude faster.},
  author       = {Lenz, Oliver Urs and Peralta, Daniel and Cornelis, Chris},
  issn         = {1063-6706},
  journal      = {IEEE TRANSACTIONS ON FUZZY SYSTEMS},
  keywords     = {big data applications,classification algorithms,fuzzy rough sets,nearest neighbor searches,scalability},
  language     = {eng},
  title        = {Scalable approximate FRNN-OWA classification},
  url          = {http://dx.doi.org/10.1109/TFUZZ.2019.2949769},
  year         = {2019},
}

Altmetric
View in Altmetric