Prikl. Diskr. Mat., 2020, Number 47, Pages 5–15
Theoretical Backgrounds of Applied Discrete Mathematics
A structure of the nearest neighbors collective in a family of partitions of a finite set
S. V. Dronov
Altai State University, Barnaul, Russia
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.
partitions of finite sets, cluster metric, statistical significance of differences of partitions.
PDF file (640 kB)
519.14 + 519.23
S. V. Dronov, “A structure of the nearest neighbors collective in a family of partitions of a finite set”, Prikl. Diskr. Mat., 2020, no. 47, 5–15
Citation in format AMSBIB
\paper A structure of the nearest neighbors collective in~a~family of partitions of a finite set
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|