The Permutable k-means for the Bi-Partial Criterion

Serge D. Dvoenko, Jan W Owsinski


The here applied objective function for clustering consists of two parts, where the first one takes into account intra-cluster relations, and the second – inter-cluster ones. In the case of k-means algorithm, such bi-partial objective function combines cluster dispersions with inter-cluster similarity, to be jointly minimized. The first part only of such objective function provides the “standard” quality of clustering based on distances between objects (the well-known classical k-means). To improve the clustering quality based on the bi-partial objective function, we need to develop the permutable version of k-means algorithm. This paper shows the permutable k-means that appears to be a new type of clustering procedure.

Full Text:



Jan W. Owsinski (2012). On the optimal division of an empirical distribution (and some related prob-lems). Przegląd Statystyczny, special issue, 1, 109-122.

Jan W. Owsinski (2013). On dividing an empirical distribution into optimal segments. Retrieved June 3, 2017 from

Jan W. Owsinski (2011). The bi-partial approach in clustering and ordering: the model and the algo-rithms. Statistica & Applicazioni. Special Issue, 43–59.

Sergey D. Dvoenko (2009). Clustering and separat-ing of a set of members in terms of mutual distances and similarities. Transactions on MLDM. IBaI Pub-lishing 2, 2 (Oct. 2009), 80-99.

Sergey Dvoenko (2014). Meanless k-means as k-meanless clustering with the bi-partial approach. In Proceedings of 12th Int. Conf. on Pattern Recogni-tion and Image Processing (PRIP’2014). UIIP NASB, Minsk, Belarus, 50-54.

W.S. Torgerson (1958). Theory and Methods of Scaling. Wiley, New York, NY.

Ronald A. Fisher (1936). The use of multiple mea-surements in taxonomic problems. Ann. Eugenics. 7, 2 (Sept. 1936), 179-188. DOI:

Sergey D. Dvoenko, and Denis O. Pshenichny (2016). A recovering of violated metric in machine learning. In Proceedings of 8th Int. Symposium on Information and Communication Technology (SoICT’2016). ACM NY, 15-21. DOI:


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.