El algoritmo K-means es un algoritmo de agrupamiento bien conocido y ampliamente utilizado debido a su simplicidad y propiedades de convergencia. Sin embargo, uno de los inconvenientes del algoritmo es su inestabilidad. Este artículo presenta mejoras al algoritmo K-means utilizando una estructura de datos de árbol K-dimensional (Kd-tree). El Kd-tree propuesto se utiliza como una estructura de datos para mejorar la elección de los centros iniciales de los clústeres y reducir el número de búsquedas del vecino más cercano requeridas por el algoritmo. El marco desarrollado también incluye una técnica eficiente de inserción de centros que conduce a una operación incremental que supera el problema de inestabilidad del algoritmo K-means. Los resultados del algoritmo propuesto se compararon con los obtenidos del algoritmo K-means, K-medoids y K-means++ en un experimento utilizando seis conjuntos de datos diferentes. Los resultados demostraron que el algoritmo propuesto proporciona soluciones de agrupamiento superiores y más estables.