Fast k-nearest neighbors for Big Data and Smart Data

Abstract

In this thesis, we have presented an extensive study of the kNN algorithm in Big Data problems and its application to transform Big Data into Smart Data. The objective has been to the design, implementation, analysis and evaluation of the proposed algorithms. This thesis started by enabling the original kNN classifier to tackle Big Data problems, and then we extended that proposal to allow its fuzzy variation, in order to improve the scalability and accuracy. Afterwards, the implication of the kNN algorithm in obtaining Smart Data is analysed, highlighting the proposal as an imputation of MVs. Finally, two specific complexity and density metrics for Big Data problems are proposed in order to study the redundancy information in large scale datasets.

En esta tesis hemos presentado un amplio estudio sobre el algoritmo kNN en problemas Big Data y su uso para transformar grandes conjuntos de datos en Smart Data. Como objetivo se ha planteado el diseño, implementación, análisis y evaluación de los algoritmos propuestos. Comienza con la propuesta escalable y exacta del algoritmo kNN y se extiende con la mejora aproximada de FkNN. Posteriormente, se ha analizado la implicación del algoritmo kNN en la obtención de Smart Data, destacando la propuesta como imputador de MVs. Finalmente, se han propuesto dos métricas de complejidad y densidad específicas para problemas Big Data con el propósito de estudiar la redundancia de información en conjuntos de datos de gran escala.