TY - JOUR AU - Pérez Ortega, Joaquín AU - Almanza Ortega, Nelva Nely AU - Ruiz-Vanoye, Jorge A. AU - Pazos R., Rodolfo A. AU - Sáenz Sánchez, Socorro AU - Rodríguez Lelis, José María AU - Martínez Rebollar, Alicia PY - 2018/02/23 Y2 - 2024/03/28 TI - A-means: improving the cluster assignment phase of k-means for Big Data JF - International Journal of Combinatorial Optimization Problems and Informatics JA - Int. Journal of COP and Infor. VL - 9 IS - 2 SE - Articles DO - UR - https://ijcopi.org/ojs/article/view/91 SP - 3-10 AB - <p>This paper proposes a new criterion for reducing the processing time of the assignment of data points to clusters for algorithms of the k-means family, when they are applied to instances where the number <em>n</em> of points is large. Our criterion allows a point to be classified in an early stage, excluding it from distance calculations to cluster centroids in subsequent iterations. The proposed criterion uses knowledge of the distance of a point to its two closest centroids and their shifts in the last two iterations. By computer experimentation using synthetic and real instances, we found that this criterion reduces execution time to approximately 2/100 of the time by k-means and generates solutions whose quality is approximately reduced by less than 3%. These findings suggest the usefulness of our criterion for problems like those found in Big Data. The NP-hardness of k-means motivates the use of this heuristics.</p> ER -