ck-NN: A Clustered k-Nearest Neighbours Approach for Large-Scale Classification

  • Rafi Ullah
    Karachi Institute of Economics and Technology
  • Ayaz H. Khan
    Karachi Institute of Economics and Technology ayaz.hassan[at]pafkiet.edu.pk
  • S.M. Emaduddin
    Karachi Institute of Economics and Technology

Abstract

k-Nearest Neighbor (k-NN) is a non-parametric algorithm widely used for the estimation and classification of data points especially when the dataset is distributed in several classes. It is considered to be a lazy machine learning algorithm as most of the computations are done during the testing phase instead of performing this task during the training of data. Hence it is practically inefficient, infeasible and inapplicable while processing huge datasets i.e. Big Data. On the other hand, clustering techniques (unsupervised learning) greatly affect results if you do normalization or standardization techniques, difficult to determine "k" Value. In this paper, some novel techniques are proposed to be used as pre-state mechanism of state-of-the-art k-NN Classification Algorithm. Our proposed mechanism uses unsupervised clustering algorithm on large dataset before applying k-NN algorithm on different clusters that might running on single machine, multiple machines or different nodes of a cluster in distributed environment. Initially dataset, possibly having multi dimensions, is pass through clustering technique (K-Means) at master node or controller to find the number of clusters equal to the number of nodes in distributed systems or number of cores in system, and then each cluster will be assigned to exactly one node or one core and then applies k-NN locally, each core or node in clusters sends their best result and the selector choose best and nearest possible class from all options. We will be using one of the gold standard distributed framework. We believe that our proposed mechanism could be applied on big data. We also believe that the architecture can also be implemented on multi GPUs or FPGA to take flavor of k-NN on large or huge datasets where traditional k-NN is very slow.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas

Agirrezabala JR, Aguado M, Aizpurua I, Albizuri M, Alfonso I, Armendáriz M, et al. Adherencia al Tratamiento Farmacológico en Patologías Crónicas. Infac [Internet]. 2011 [citado 19 dic 2016]; 19 (1): 1. Disponible en:

http://www.osakidetza.euskadi.eus/contenidos/informacion/cevime_infac/es_cevime/adjuntos/infac_v19_n1.pdf

Centro de Información Online de Medicamentos de la AEMPS [Internet]. [Citado 15 feb 2017]. Disponible en: https://www.aemps.gob.es/cima/fichasTecnicas.do?metodo=buscar

Dilla T, Valladares A, Lizán L y Sacristán JA. Adherencia y Persistencia Terapéutica: Causas, Consecuencias y Estrategias de Mejora. Aten Primaria [Internet]. 2009 [citado 21 dic 2016]. 41 (6): 342. Disponible en:

http://www.elsevier.es/es-revista-atencion-primaria-27-articulo-adherencia-persistencia-terapeutica-causas-consecuencias-S0212656709001504#bib1

Grupo de Trabajo de Sistemas Personalizados de Dosificación del Consejo General de Colegios Oficiales de Farmacéuticos. Sistemas Personalizados de Dosificación: Procedimiento Normalizado de Trabajo [Internet]. Versión No 12. Madrid: Consejo General de Colegios Oficiales de Farmacéuticos. 2013 [citado 20 ene 2017]. Disponible en:

http://www.portalfarma.com/profesionales/organizacionfcolegial/profesionfarma/planfuturofarmaciacomunitaria//Documents/2013_10_05_Documento_Procedimiento_SPD.PDF

Instituto de Mayores y Servicios Sociales (IMSERSO). Las Personas Mayores en España: Datos Estadísticos Estatales y por Comunidades Autónomas. Madrid: Ministerio de Sanidad, Servicios Sociales e Igualdad; 2014. Serie Documentos Estadísticos No22026.

Instituto Nacional de Estadística [Internet]. Madrid: INE; 2002 [actualizado 1 jul 2016, citado 3 ene 2017]. INEbase: series detalladas desde 2002 [1 pantalla]. Disponible en: http://www.ine.es/dynt3/inebase/es/index.htm?padre=1894&capsel=1895

Ley 29/2006, de 26 de julio, de garantías y uso racional de medicamentos y productos sanitarios. (Boletín Oficial del Estado, No178, de 27 de julio de 2016).

Ministerio de Sanidad y Consumo. Proyecto ap-21: Marco Estratégico para la mejora de la Atención Primaria en España: 2007-2012. Madrid: Ministerio de Sanidad y Consumo; 2007.

Unidad de Bioindustrias y Farmacia: Antares Consulting. Impacto Económico de la No Adherencia en los Costes Farmacéuticos. Biofarma Flash Track. 2013 [citado 1 feb 2017]; 3: 1. Disponible en:

https://www.antares-consulting.com/es_ES/main/detallepublicacion/Publicacion/79/apartado/B/idUnidad/1

Venalink [Internet]. Barcelona: BASIC Estudio; 1998 [citado 12 ene 2017]. Disponible en: http://www.venalink.es/

World Health Organization. Aherence to Long-term Therapies: Evidence for Action. [Internet]. 1ª ed. Suiza, National Library of Medicine; 2003 [citado 19 dic 2016]. Disponible en: https://books.google.es/books?id=kcYUTH8rPiwC&printsec=frontcover&hl=es&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false

ck-NN: A Clustered k-Nearest Neighbours Approach for Large-Scale Classification. (2019). ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 8(3), 67-77. https://doi.org/10.14201/ADCAIJ2019836777

Author Biography

Ayaz H. Khan

Karachi Institute of Economics and Technology

Computer Science Department

Assistant Professor

+ −