Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat., 2020, Number 47, Pages 5–15 (Mi pdm690)  

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

Abstract: 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.

DOI: https://doi.org/10.17223/20710410/47/1

Full text: PDF file (640 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.14 + 519.23

Citation: 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
\Bibitem{Dro20}
\by S.~V.~Dronov
\paper A structure of the nearest neighbors collective in~a~family of partitions of a finite set
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 5--15
\mathnet{http://mi.mathnet.ru/pdm690}
\crossref{https://doi.org/10.17223/20710410/47/1}


Linking options:
  • http://mi.mathnet.ru/eng/pdm690
  • http://mi.mathnet.ru/eng/pdm/y2020/i1/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:83
    Full text:25
    References:4

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021