A structure of the nearest neighbors collective in a family of partitions of a finite set | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/1

In this paper, we study partitions of a finite set of some ob jects 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 ob jects 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 ob jects moves between the smallest sets of the main partition. Wherein, at least one of them must contain at least two ob jects. 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.