K-means is one of the most used clustering algorithms in many ap-plication domains including image segmentation, text mining, bioinformatics, machine learning and Artificial Intelligence. Its strength derives from its sim-plicity and efficiency. K-means clustering quality, though, usually is low due to its “modus operandi” and local semantics, that is its main ability to fine-tune a solution which ultimately depends on the adopted centroids’ initialization method. This paper proposes a novel approach and supporting tool named ADKM which improves K-means behavior through a new centroid initialization algorithm which exploits the concepts of agglomerative clustering and density peaks. ADKM is currently implemented in Java on top of parallel streams, which can boost the execution efficiency on a multi-core machine with shared memory. The paper demonstrates by practical experiments on a collection of benchmark datasets that ADKM outperforms, by time efficiency and reliable clustering, the standard K-means algorithm, although iterated a large number of times, and its behavior is comparable to that of more sophisticated clustering algorithms. Finally, conclusions are presented together with an indication of further work.