Geodesic
A structure of the nearest neighbors collective in~a~family of partitions of a finite set
Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 5-15.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we study partitions of a finite set of some objects into disjoint subsets closest to a given (main) partition. The distance between two partitions is taken equal to the sum of squares of numbers of the elements of sets that make up each of the partitions minus twice the sum of squares of the values of the sets forming the intersection of the partitions. For a fixed main partition, all the closest partitions and their number are found. The closest neighbors are always obtained by picking out one of the objects into a new set or by merging two single-element sets of the main partition (Theorem 1). The nearest neighbor here is $ 2 (m-1) $ from the main partition, where $ m $ is the number of objects of the minimum non-singleton of the main partition, if one exists. Otherwise, this distance equals $2$. Theorem 2 describes a situation where the number of elements of partitions must be the same. This happens, for example, when both partitions are constructed by the method of $ k $-means for the same $ k $. Here, to construct the nearest neighbor, one of the objects moves between the smallest sets of the main partition. Wherein, at least one of them must contain at least two objects. The corollaries of both theorems, obtained by accurately calculating the possible number of operations of the described type, give the exact quantities of nearest neighbors of the main partition, depending on its structure. We propose an application of the obtained results to the construction of a statistical criterion for the significance of the difference between two partitions. An example of medical data processing using this criterion is given.
Keywords: partitions of finite sets, cluster metric, statistical significance of differences of partitions. 
@article{PDM_2020_1_a0,
     author = {S. V. Dronov},
     title = {A structure of the nearest neighbors collective in~a~family of partitions of a finite set},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--15},
     publisher = {mathdoc},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_1_a0/}
}
TY  - JOUR
AU  - S. V. Dronov
TI  - A structure of the nearest neighbors collective in~a~family of partitions of a finite set
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 5
EP  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_1_a0/
LA  - ru
ID  - PDM_2020_1_a0
ER  - 
%0 Journal Article
%A S. V. Dronov
%T A structure of the nearest neighbors collective in~a~family of partitions of a finite set
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 5-15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_1_a0/
%G ru
%F PDM_2020_1_a0
S. V. Dronov. A structure of the nearest neighbors collective in~a~family of partitions of a finite set. Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 5-15. http://geodesic.mathdoc.fr/item/PDM_2020_1_a0/

[1] Brualdi R. A., Introductory Combinatorics, 5th ed., Pearson Prentice Hall, Upper Saddle River, NJ, 2017, 624 pp. | MR

[2] Bender E. A., Williamson S. G., Foundations of Combinatorics with Applications, Dover Publ., Mineola, NY, 2006, 480 pp. www.math.ucsd.edu/ẽbender/CombText/ch-11.pdf

[3] Birkhoff G., Lattice Theory, 3rd ed., AMS, Providence, Rhode Island, 1991, 420 pp. | MR

[4] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P., Numerical Recipes: The Art of Scientific Computing, 3rd ed., Cambridge University Press, 2007, 1235 pp. | MR | Zbl

[5] Yaglom A. M., Yaglom I. M., Probability and Information, 3rd ed., Nauka Publ., M., 1973, 513 pp. (in Russian) | MR

[6] Levenshteyn V. I., “Binary codes for correcting dropouts, inserts, and symbol substitutions”, Reports of the USSR Academy of Sciences, 163:4 (1965), 845–848 (in Russian) | Zbl

[7] Gasfild D., Lines, Trees, and Sequences in Algorithms. Computer Science and Computational Biology, Nevskiy Dialekt BVKh-Peterburg, St. Petersburg, 2003, 654 pp. (in Russian)

[8] Cohen W. W., Rawikumar P., Fienberg S. E., “A comparison of string distance metrics for name-matching tasks”, Proc. IIWEB'03 (Acapulco, Mexico), AAAI Press, 2003, 73–78

[9] Kagramanyan A. G., Mashtalir V. P., Sklyar E. V., Shlyakhov V. V., “Metric properties of partitions of sets of arbitrary nature”, Reports of the Academy of Sciences of Ukraine, 6 (2007), 35–39 (in Russian) | Zbl

[10] Dronov S. V., “One cluster metric and the stability of cluster algorythms”, Izvestiya AltGU, 69:1/2 (2011), 32–35 (in Russian)

[11] Dronov S. V., Evdokimov E. A., “Post-hoc cluster analysis of connection between forming characteristics”, Model Assisted Statistics Appl., 13:2 (2018), 183–192 | DOI

[12] Dronov S. V., “The shortest routes in the family of the cluster partitions”, Workshop on Geometry and Mathematical Modeling, 2017, no. 3, 4–12 (in Russian)

[13] Gribel D., Vidal T., “HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering”, Pattern Recognition, 88:1 (2019), 569–583 | DOI | MR

[14] Riordan J., Introduction to Combinatorial Analysis, Dover Publ., Mineola, NY, 2006, 256 pp. | MR