20.500.12556/DiRROS-22530 Ground truth clustering is not the optimum clustering Data clustering is a fundamental yet challenging task in data science. The minimum sum-of-squares clustering (MSSC) problem aims to partition data points into k clusters to minimize the sum of squared distances between the points and their cluster centers (centroids). Despite being NP-hard, solvers exist that can compute optimal solutions for small to medium-sized datasets. One such solver is SOS-SDP, a branch-and-bound algorithm based on semidefinite programming. We used it to obtain optimal MSSC solutions (optimum clusterings) for various k across multiple datasets with known ground truth clusterings. We evaluated the alignment between the optimum and ground truth clusterings using six extrinsic measures and assessed their quality using three intrinsic measures. The results reveal that the optimum clusterings often differ significantly from the ground truth clusterings. Additionally, the optimum clusterings frequently outperform the ground truth clusterings, according to the intrinsic measures that we used. However, when ground truth clusters are well-separated convex shapes, such as ellipsoids, the optimum and ground truth clusterings closely align. Razvrščanje podatkov v skupine je temeljna, a zelo zahtevna naloga v podatkovni znanosti. Problem razvrščanja z minimalno vsoto kvadratov odklonov (MSSC) je osredotočen na razvrščanje podatkovnih točk v k skupin na način, da bila vsota kvadratov razdalj med točkami in centri skupin (centroidi) minimalna. Kljub temu, da je to NP-težek problem, obstajajo reševalniki za ta problem, ki lahko izračunajo optimalne rešitve za majhne in srednje velike nabore podatkov. Eden takšnih reševalnikov je SOS-SDP, ki temelji na razveji in omeji algoritmu in na semidefinitnem programiranju. Uporabili smo ga za pridobitev optimalnih rešitev MSSC (optimalnih razvrščanj) za različne vrednosti k preko več naborov podatkov z znanimi dejanskimi razvrstitvami. Ugotavljali smo skladnost med optimalnimi in dejanskimi razvrstitvami z uporabo šestih zunanjih mer ter ocenili njihovo kakovost z uporabo treh notranjih mer. Rezultati kažejo, da se optimalne razvrstitve pogosto znatno razlikujejo od dejanskih razvrstitev. Poleg tega optimalne razvrstitve pogosto presegajo dejanske razvrstitve glede na vrednosti notranjih mer, ki smo jih uporabili. Kadar pa so dejanske skupine dobro ločene in imajo konveksne oblike, kot so npr. elipsoidi, so optimalne in dejanske razvrstitve tesno usklajene. minimum sum-of-squares clustering ground truth clustering rxtrinsic measures intrinsic measures razvrščanje z minimalno vsoto kvadratov dejansko razvrščanje zunanje mere notranje mere true false false Angleški jezik Slovenski jezik Neznano 2025-05-29 12:57:38 2025-05-29 12:57:39 2025-10-24 03:51:28 0000-00-00 00:00:00 2025 0 0 Nasl. z nasl. zaslona; Opis vira z dne 22. 3. 2025; Soavtorji: Timotej Hrga, Janez Povh & Shudian Zhao; str. 1-17 article no. ǂ9223 Vol. 15 2025 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2025-01-01 519.85 2045-2322 10.1038/s41598-025-90865-9 229897731 https://www.nature.com/articles/s41598-025-90865-9 1 be1384b6-3c7b-11f0-963a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=32570 RAZ_Absalom_Bautista_Lucia_2025.pdf RAZ_Absalom_Bautista_Lucia_2025.pdf 1 B7E811F029090C6131103F8630717E70 18d0c7ccad4ede032c6b7023936411ab8872ceddda07e7f3e406959ea70cefc5 b155b317-3c7c-11f0-963a-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=32571 Rudolfovo – Znanstveno in tehnološko središče Novo mesto 0 0 0