Abstract
This paper presents an approach to detect outliers present in a data set, also called aberration. These outliers often cause problems to the learning algorithms by deviating their behavior, which makes them less efficient. It is therefore necessary to identify and remove them during the cleaning data step before the learning process. For this purpose, a method that detects if data is an outlier from its k nearest neighbors is proposed for multidimensional data sets. In order to make the method more accurate, the number of k nearest neighbors chosen is adaptive for each class present in the data set, and each neighbor has a different weight in the decision, depending on their respective proximity. The proposed method is called Makoto for Multidimensional Adaptative kNN Over Tracking Outliers. The effectiveness of this method is compared with four other known methods based on different principles: LOF (Local Outlier Factor), Isolation forest, One Class SVM and Inter Quartile Range (IQR). Thus, on the basis of 406 synthetic data sets and 17 real data sets with distinct characteristics, the Makoto method appears to be more efficient.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aggarwal, C.C.: Outlier Analysis. Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-47578-3
Amer, M., Goldstein, M., Abdennadher, S.: Enhancing one-class support vector machines for unsupervised anomaly detection. In: Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description, ODD 2013, pp. 8–15. Association for Computing Machinery, New York (Aug 2013). https://doi.org/10.1145/2500853.2500857
Baoli, L., Qin, L., Shiwen, Y.: An adaptive k-nearest neighbor text categorization strategy. ACM Trans. Asian Lang. Inform. Process. 3(4), 215–226 (2004). https://doi.org/10.1145/1039621.1039623
Breunig, M., Kriegel, H.P., Ng, R., Sander, J.: LOF: identifying density-based local outliers. In: ACM Sigmod Record, vol. 29, pp. 93–104 (Jun 2000). https://doi.org/10.1145/342009.335388
Chehreghani, M.H.: K-nearest neighbor search and outlier detection via minimax distances. In: Proceedings of the 2016 SIAM International Conference on Data Mining, p. 9. Society for Industrial and Applied Mathematics (2016). https://doi.org/10.1137/1.9781611974348.46
Dietterich, T., Wettschereck, D., Wettschereck, D., Dietterich, T.G.: Locally adaptive nearest neighbor algorithms. In: Advances in Neural Information Processing Systems 6, pp. 184–191. Morgan Kaufmann (1994)
Epanechnikov, V.A.: Non-parametric estimation of a multivariate probability density. Theory Probabil. Appli. 14(1), 153–158 (1969). https://doi.org/10.1137/1114019
Guyon, I., Gunn, S., Ben-Hur, A., Dror, G.: Design and Analysis of the NIPS2003 Challenge, vol. 207, pp. 237–263 (Nov 2008). https://doi.org/10.1007/978-3-540-35488-8_10
Hechenbichler, K., Schliep, K.: Weighted k-Nearest-Neighbor Techniques and Ordinal Classification. discussion paper 399 (Jan 2004)
Keller, F., Muller, E., Bohm, K.: HiCS: high contrast subspaces for density-based outlier ranking. In: 2012 IEEE 28th International Conference on Data Engineering, pp. 1037–1048 (Apr 2012). https://doi.org/10.1109/ICDE.2012.88
Kou, Y., Lu, C.T., Chen, D.: Spatial weighted outlier detection. In: Proceedings of the 2006 SIAM International Conference on Data Mining, p. 5. Proceedings, Society for Industrial and Applied Mathematics (Apr 2006). https://doi.org/10.1137/1.9781611972764.71
Liu, F.T., Ting, K.M., Zhou, Z.H.: Isolation-Based Anomaly Detection. ACM Trans. Knowl. Dis. Data 6(1), 3:1–3:39 (2012). https://doi.org/10.1145/2133360.2133363
Lu, C., Chen, D., Kou, Y.: Algorithms for spatial outlier detection. In: Third IEEE International Conference on Data Mining, pp. 597–600 (Nov 2003). https://doi.org/10.1109/ICDM.2003.1250986
Thung, F., Wang, S., Lo, D., Jiang, L.: An empirical study of bugs in machine learning systems. In: 2012 IEEE 23rd International Symposium on Software Reliability Engineering, pp. 271–280 (Nov 2012). https://doi.org/10.1109/ISSRE.2012.22
Whaley, D.L.: The Interquartile Range: Theory and Estimation (2005)
Zhang, S., Wan, J.: Weight-based method for inside outlier detection. Optik 154, 145–156 (2018). https://doi.org/10.1016/j.ijleo.2017.09.116
Zhao, Y., Nasrullah, Z., Li, Z.: Pyod: a python toolbox for scalable outlier detection. J. Mach. Learn. Res. 20(96), 1–7 (2019). http://jmlr.org/papers/v20/19-011.html
Acknowledgement
Work supported by the French National Research Agency (contract ANR-18-CE25-0013) and by the EIPHI Graduate School (contract ANR-17-EURE-0002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Colonval, J., Bouquet, F. (2023). Multidimensional Adaptative kNN over Tracking Outliers (Makoto). In: Yang, X., et al. Advanced Data Mining and Applications. ADMA 2023. Lecture Notes in Computer Science(), vol 14176. Springer, Cham. https://doi.org/10.1007/978-3-031-46661-8_36
Download citation
DOI: https://doi.org/10.1007/978-3-031-46661-8_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-46660-1
Online ISBN: 978-3-031-46661-8
eBook Packages: Computer ScienceComputer Science (R0)