Clustering of Data Represented by Pairwise Comparisons

Dvoenko, Sergey

doi:10.2478/candc-2022-0021

Abstract

In this paper, experimental data, given in the form of pairwise comparisons, such as distances or similarities, are considered. Clustering algorithms for processing such data are developed based on the well-known k-means procedure. Relations to factor analysis are shown. The problems of improving clustering quality and of finding the proper number of clusters in the case of pairwise comparisons are considered. Illustrative examples are provided.

References

Aivazyan, S. A. et al. (1989) Applied Statistics. Classification and Reduction of Dimensionality [in Russian]. FiS, Moscow.
Search in Google Scholar Back to article
Aizerman, M. A., Braverman, E. M. and Rozonoer, L. I. (1970) The Method of Potential Functions in Machine Learning Theory [in Russian]. Nauka, Moscow.
Search in Google Scholar Back to article
Bognar, J. (1974) Indefinite Inner Product Spaces. Springer-Verlag, New York.
Search in Google Scholar Back to article
Braverman, E. M. (1970) Methods of extremal grouping of parameters and problem of apportionment of essential factors [in Russian]. Avtomat. i Telemekh. 1, 123–132.
Search in Google Scholar Back to article
Braverman, E. M. et al. (1971) Diagonalization of the relation matrix and detecting hidden factors [in Russian]. Trans. Inst. of Control Sciences. 1st Issue ‘Problems of increasing of automata possibilities.” ICS, Moscow, 42–79.
Search in Google Scholar Back to article
Braverman, E. M. and Muchnik, I. B. (1983) Structured Methods of Empirical Data Processing [in Russian]. Nauka, Moscow.
Search in Google Scholar Back to article
Diday, E., Bochi, S., Brossier, G. and Celeux, G. (1979) Optimisation en Classification Automatique. 2. Institut national de recherche en informatique et en automatique (INRIA), Le Chesnay (in French).
Search in Google Scholar Back to article
Duda, R. O. and Hart, P. E. (1973) Pattern Classification and Scene Analysis. Wiley, New York.
Search in Google Scholar Back to article
Duda, R. O., Hart, P. E. and Stork, D. G. (2000) Pattern Classification.Wiley, New York.
Search in Google Scholar Back to article
Dvoenko, S. D. (2001) Restoration of spaces in data by the method of non-hierarchical decompositions. Automation and Remote Control. 62, 467– 473. //doi.org/10.1023/A:1002814429456
Search in Google Scholar Back to article
Dvoenko, S. D. (2009a) Clustering and separating of a set of members in terms of mutual distances and similarities. Trans. on MLDM. IBaI Publishing, 2(2), 80–99.
Search in Google Scholar Back to article
Dvoenko, S. D. (2009b) Clustering of a set described by paired distances and closeness between its elements [in Russian]. Sib. J. of Industr. Math. 12 (1), 61–73.
Search in Google Scholar Back to article
Dvoenko, S. D. (2011) On clustering of a set of members by distances and similarities. Proc. of 11th Int. Conf, on Pattern Recognition and Information Processing (PRIP’2011). BSUIR, 104–107.
Search in Google Scholar Back to article
Dvoenko, S. (2014) Meanless k-means as k-meanless clustering with the bipartial approach. Proc. of 12th Int. Conf. on Pattern Recognition and Information Processing (PRIP’2014). UIIP NASB, 50–54.
Search in Google Scholar Back to article
Dvoenko, S. and Owsinski, J. (2019) The permutable k-means for the bipartial criterion. Informatica. 43 (2), 253–262. //doi.org/10.31449/inf.v 43i2.2090
Search in Google Scholar Back to article
Dvoenko, S. D. and Pshenichny, D. O. (2018) On metric correction and conditionality of raw featureless data in machine learning. Pattern Recognit. Image Anal. 28, 595–604. //doi.org/10.1134/S1054661818040089
Search in Google Scholar Back to article
Dvoenko, S. D. and Pshenichny, D. O. (2021) Rank aggregation based on new types of the Kemeny’s median. Pattern Recognit. Image Anal. 31, 185–196. //doi.org/10.1134/S1054661821020061
Search in Google Scholar Back to article
Fisher, R. A. (1936) The use of multiple measurements in taxonomic problems. Ann. Eugenics. 7 (2), 179-188.
Search in Google Scholar Back to article
Friedman, H. P. and Rubin, J. (1967) On some invariant criteria for grouping data. Journal of the American Statistical Association 62 (320), 1159– 1178. //doi.org/10.1080/01621459.1967.10500923
Search in Google Scholar Back to article
Harman, H. H. (1976) Modern Factor Analysis. University of Chicago Press, Chicago.
Search in Google Scholar Back to article
Hartigan, J. A. and Wong, M. A. (1979) Algorithm AS 136: A k-means clustering algorithm. J. Roy. Soc. 28 (1), 100–108. //doi.org/10.2307/2346830
Search in Google Scholar Back to article
Kemeny, J. (1959) Mathematics without numbers. Daedalus, 88(4), 577–591.
Search in Google Scholar Back to article
Litvak, B. G. (1982) Expert Information: Methods of Acquisition and Analysis [in Russian]. Radio i Svyaz, Moscow.
Search in Google Scholar Back to article
Lumel’sky, V. Ya. (1970) Grouping of parameters on the basis of communication matrices [in Russian]. Avtomat. i Telemekh. 1, 133–143.
Search in Google Scholar Back to article
Luce, R. D. (1959) Individual Choice Behavior: A Theoretical Analysis. Wiley, New York.
Search in Google Scholar Back to article
Mercer, J. (1909) Functions of positive and negative type and their connection with the theory of integral equations. Philos. Trans. Roy. Soc., London.
Search in Google Scholar Back to article
Owsiński, J. W. (2020) Data Analysis in Bi-partial Perspective: Clustering and Beyond. SCI 818, Springer. //doi.org/10.1007/978-3-030-13389-4
Search in Google Scholar Back to article
Pekalska, E. AND Duin R. P. W. (2005) The Dissimilarity Representation for Pattern Recognition. Foundations and Applications. World Scientific, Sngapore.
Search in Google Scholar Back to article
Rosenblatt, F. (1962) Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan Books, Washington.
Search in Google Scholar Back to article
Schlesinger, M. (1965) About spontaneous recognition of patterns [in Russian]. Reading Automations. Kiev, 38–45.
Search in Google Scholar Back to article
Späth, H. (1983) Cluster-Formation und -Analyse: Theorie, FORTRAN-Programme und Beispiele [in German]. R. Oldenbourg Verlag, München– Wien.
Search in Google Scholar Back to article
Torgerson, W. S. (1958) Theory and Methods of Scaling. Wiley, New York.
Search in Google Scholar Back to article
Ward, J. (1963) Hierarchical grouping to optimize an objective function. J. American Statist. Ass. 58 (301), 236–244. //doi.org/10.1080/01621459.1963.10500845
Search in Google Scholar Back to article
Young, G. and Householder, A. S. (1938) Discussion of set of points in terms of their mutual distances. Psychometrica. 3, 19–22. //doi.org/10.1007/BF02287916
Search in Google Scholar Back to article
Zagoruiko, N. G. (1999) Applied Methods of Data and Knowledge Analysis [in Russian]. IM SBRAS, Novosibirsk.
Search in Google Scholar Back to article

Clustering of Data Represented by Pairwise Comparisons

Abstract

Paradigm

My account