Scalable Approximate FRNN-OWA Classification
| Autor: | Oliver Urs Lenz, Chris Cornelis, Daniel Peralta |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
nearest neighbor searches
Computer science Nearest neighbor search 02 engineering and technology Machine learning algorithms Fuzzy logic k-nearest neighbors algorithm Artificial Intelligence Robustness (computer science) 0202 electrical engineering electronic engineering information engineering Training Time complexity scalability big data applications Applied Mathematics ROUGH Approximation algorithm Fuzzy systems Rough sets Approximation algorithms Open wireless architecture Statistical classification ComputingMethodologies_PATTERNRECOGNITION Mathematics and Statistics Computational Theory and Mathematics Control and Systems Engineering classification algorithms FEATURE-SELECTION 020201 artificial intelligence & image processing Rough set Algorithm fuzzy rough sets |
| Zdroj: | IEEE TRANSACTIONS ON FUZZY SYSTEMS |
| ISSN: | 1941-0034 1063-6706 |
| DOI: | 10.1109/tfuzz.2019.2949769 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|