Megjelent a REMOS osztályozási módszerről szóló cikkünk a JVS-ben

2019 novemberében írtam arról, hogy kitaláltunk egy új osztályozási módszert, amelynek a REMOS (REallocation of Misclassified Objects based on Silhouette width) nevet adtuk. A módszerről most csak annyit írnék, hogy ezzel meglévő (akár véletlenszerű) osztályozásokon lehet javítani azáltal, hogy a "félreosztályozott" elemeket lépésenként átpakolgatjuk egy megfelelőbbnek tűnő csoportba. A jóság kritériuma pedig az adott objektum sziluett indexe. A módszert először preprintként közöltük le, hogy azonnal használhassuk és hivatkozhassuk a lengyel gyepek jellegalapú osztályozásához. Közben benyújtottuk a Journal of Vegetation Science-be is közlésre, s némi átalakítás után most végre el is fogadták. A cikkben a REMOS két verzióját egy hasonló elven működő, OPTSIL nevű módszerrel vetjük össze. A bírálati idő kicsit hosszúra nyúlt, mert nehezen talált a szerkesztő bírálót a viszonylag szűk és elméleti témájú cikkhez (azt írta, 11 visszautasított felkérés után vállalta el valaki), de cserébe mi gyorsan javítottunk mindent, így összességében az átlagosnak mondható, egy év körüli átfutás jött ki. A cikk nyílt hozzáférésű, és a 123997 azonosítójú OTKA PD projektem első cikke.

A REMOS mindkét verziója sokkal gyorsabb az OPTSIL-nél

Lengyel, A, Roberts, DW, Botta‐Dukát, Z. 2021. Comparison of silhouette‐based reallocation methods for vegetation classification. Journal of Vegetation Science; 32:e12984. https://doi.org/10.1111/jvs.12984

Abstract

Aims: Vegetation classification seeks to partition the variability of vegetation into relatively homogeneous but distinct types. There are many ways to evaluate, and potentially improve, such a partitioning. One effective approach involves calculating silhouette widths which measure the goodness‐of‐fit of plots to their cluster. We introduce a new iterative reallocation clustering method — Reallocation of Misclassified Objects based on Silhouette width (REMOS) — and compare its performance with an existing algorithm — OPTimizing SILhouette widths (OPTSIL). REMOS reallocates misclassified objects to their nearest‐neighbour cluster iteratively. Of its two variants, REMOS1 reallocates only the object with the lowest silhouette width, while REMOS2 reallocates all objects with negative silhouette width in each iteration. We test how REMOS1, REMOS2 and OPTSIL perform in terms of: (a) cluster homogeneity and separation; (b) the number of diagnostic species; and (c) runtime.

Methods: We classified simulated data with the flexible‐beta algorithm for values of beta from −1 to 0. These classifications were subsequently optimized by REMOS1, REMOS2 and OPTSIL and compared for mean silhouette widths, misclassification rate, and runtime. We classified three vegetation data sets from two to ten clusters, optimized all outcomes with the three reallocation methods, and compared their mean silhouette widths, misclassification rate, and number of diagnostic species.

Results: OPTSIL achieved the highest mean silhouette width across the majority of the data sets. REMOS achieved zero or negligible misclassifications, outperforming OPTSIL on this criterion. REMOS algorithms were typically more than an order of magnitude faster to calculate than OPTSIL. There was no clear difference between REMOS and OPTSIL in the number of diagnostic species.

Conclusions: REMOS algorithms may be preferable to OPTSIL when: (a) the primary objective is to reduce the number of negative silhouette widths in a classification, as opposed to maximizing mean silhouette width; or (b) when the time efficiency of the algorithm is important.

REMOS - új módszer a numerikus osztályozásban

A numerikus osztályozás számos tudományterületen az alapvető statisztikai módszerek közé tartozik. A növényzeti típusok reprodukálható, objektív kritériumok alapján történő elkülönítése kapcsán én is rendszeresen írok róla. A legtöbb klasszifikációs módszer jellemzője, hogy akkor is adnak eredményt (vagyis csoportokat), ha a mintának nincs különösebb struktúrája. Emiatt az objektumok (mintavételi egységek, megfigyelések, felvételek, fajlisták... amiket osztályozunk) csoportjainak létrehozása mellett ugyanennyire fontos, hogy teszteljük, tényleg jók-e a csoportok. Ez a "jóság" temérdek kritérium szerint mérhető, Vendramin és társai (2010) például 40 módszert tekintenek át a review cikkükben. Azonban ha tudjuk, hogy a célunk egy olyan osztályozás elérése, amelyre majd egy ilyen, ún. validitási index alapján azt mondjuk, hogy ez egy "jó osztályozás", akkor miért nem keressük célirányosan már az osztályozás létrehozásakor azt a megoldást, amelynek a lehető legmagasabb a validitási indexe? A megközelítés teljesen valid, ahogyan Roberts (2015) cikkében is láthatjuk: két módszert is bemutat, amelyek valamilyen kezdeti (akár random, de inkább valami más klaszterező módszerrel legyártott) osztályozásból kiindulva addig-addig pakolgatják az objektumokat egyik csoportból a másikba, amíg az adott validitási index a lehető legmagasabb értéket el nem éri. Roberts módszerei ezt úgy érik el, hogy megvizsgálnak minden egyes lehetséges áthelyezést, majd végül azt az egyet hajtják végre, amely a legnagyobb növekedést okozza a validitási index értékében. Az egyik módszer neve OPTSIL, és a sziluett nevű indexet optimalizálja. Botta-Dukát Zoltánnal nem rég írtunk egy preprintet a sziluett index általánosításáról, amellyel különféle alakú clusterekre válik érzékennyé a módszer (azóta elfogadták az Ecology and Evolution lapban, hamarosan meg kéne jelennie). A sziluettben az a jó, hogy minden egyes objektumra ad egy értéket, ami kifejezi, hogy mennyire illik abba a csoportba, amelyikbe került, az alapján, hogy milyen átlagos távolságra (a távolságok az objektumok közti különbözőséget fejezik ki) van a csoport többi tagjától, illetve a legközelebbi másik csoport tagjaitól. Az index -1 és +1 közötti értékeket vehet fel. Ha az értéke pozitív, akkor az objektum jó helyen van, mert közelebb van a csoportja többi tagjához, mint a szomszédos csoport tagjaihoz. Ha 0 (vagy ahhoz nagyon közeli), akkor az objektum átmeneti helyzetű, ha negatív, akkor "félreosztályozott", egy másik csoport tagjaira jobban hasonlít, mint azokra, amelyekkel egy csoportba sorolták. Értelemszerűen minél kevesebb a félreosztályozott objektum, annál jobb egy osztályozás. Vegetációosztályozások "szakértői" ellenőrzésekor és értékelésekor is gyakori, hogy viszonylag szubjektív módon kijelentjük, hogy egyik vagy másik felvétel "rossz" helyen van abban a csoportban, ahová a numerikus módszer tette, néha felül is bíráljuk ezt a besorolást. Mivel a sziluett index alkalmas arra, hogy a félreosztályozott objektumokat objektív módon azonosítsa, semmi nem gátol meg minket abban, hogy csináljunk egy olyan módszert, amely egy meglévő osztályozást a félreosztályozott felvételek átsorolgatásával, iteratív módon javít egészen addig, amíg minden objektum a helyére nem kerül.

Ezt csináltuk meg, először csak Botta-Dukát Zoltánnal, amiből írtunk egy preprintet, amit felraktunk a bioRxiv szerverre. Az új módszernek a REMOS (REallocation of Misclassified Objects based on Silhouette width) nevet adtuk. A kéziratot elküldtem Dave Robertsnek, aki fontos elemzésekkel és gondolatokkal egészítette ki a munkákat, így a preprintet (immár hárman) újraírtuk. A javított verzió itt olvasható, a módszer R kódja az elektronikus függelékben, az összefoglalót alább bemásolom. Közben a kézirat bírálat alatt is áll egy folyóiratban.

A REMOS-nak két verziója áll rendelkezésre. A REMOS1 mindig csak a legalacsonyabb sziluett értékű félreosztályozott objektumot rakja át a szomszédos csoportba, míg a REMOS2 az összes félreosztályozottat. Az áthelyezés után újraszámolják az összes objektumra a sziluetteket, és ha vannak félreosztályozott objektumok, akkor jön a következő áthelyezés, majd megint újraszámolás, megint áthelyezés, és így tovább addig, amíg el nem fogynak a negatív sziluett értékek. Fontos látni, hogy a REMOS alapvetően nem ellenőrzi az áthelyezések hatását az osztályozás egészére, szemben az OPTSIL-el. A REMOS csak azt tartja szem előtt, hogy az egyedi felvételek a helyükre kerüljenek, így inkább "lokális" perspektívájú, míg az OPTSIL "globális" kritérium szerint dolgozik. (Tapasztalatom szerint a gyakorlatban jobban szeretjük azokat az osztályozásokat, ahol minden objektum a helyén van, mint azokat, amelyekben átlagosan jó helyen van minden.) Mindkét REMOS verzió képes ciklusokba kerülni. Ez azt jelenti, hogy ismétlődően ide-oda pakolgatják az objektumokat a csoportok között, de mindig marad félreosztályozott, nem érnek soha a dolog végére. Ilyenkor az algoritmus automatikusan megáll és azt a megoldást fogadja el végsőként, amely a legkevesebb félreosztályozottat tartalmazza. Ha ebben egyenlőség van, akkor az lesz a végső, amely esetén a negatív sziluettek abszolút összege (az osztályozás "hibája") a legkisebb.

A félreosztályozott objektumok arányának (Misclassification rate) változása különböző béta-flexibilis osztályozással, különböző béta értékkel készített osztályozásokból indítva optimalizálás nélkül (Initial), illetve REMOS1, REMOS2 és OPTSIL módszerekkel történő optimalizálás után

A preprintben különböző adatsorokon és különböző kiindulási osztályozásokkal hasonlítottuk össze a REMOS-t és az OPTSIL-t. Az összehasonlítás kritériuma a végső osztályozás átlagos sziluett értéke, a negatív sziluettű objektumok aránya, valamint a diagnosztikus fajok száma volt. Emellett megnéztük a két módszer által igényelt futási időt is. Amikor már eleve "jó" osztályozásból indultunk ki, mindkét módszer jól teljesített, hasonlóan magas átlagos sziluettű és kevés félreosztályozott objektumot tartalmazó megoldásokat adott. Nyilván az átlagos sziluett tekintetében az OPTSIL, a félreosztályozottak arányát nézve a REMOS volt kicsivel jobb, de mivel ez a két dolog erősen összefügg, elhanyagolható volt a különbség. Amikor azonban a kiindulási osztályozás elég rossz volt, akár véletlenszerű, akkor a REMOS sokkal jobb volt, mint az OPTSIL, mindkét fenti kritérium tekintetében. Ez annak volt köszönhető, hogy az OPTSIL az iteráció során gyakran hamar "megrekedt" lokális optimumokban. A REMOS1 és a REMOS2 között ha volt különbség, akkor mindig az előbbi javára billent a mérleg. A fenti elemzéseket szimulált adatsorokon végeztük. Valós elemzési helyzeteket eljátszva, amikor "jó" osztályozásokból indultunk ki, a diagnosztikus fajok számában nem láttunk szisztematikus különbséget, hol az egyik, hol a másik módszer tűnt jobbnak. Nagy különbség volt azonban a futási időben. A REMOS nagyságrendekkel gyorsabb volt. Pl. míg egy 300 objektumot tartalmazó adatsoron "jó" osztályozásból indítva a REMOS1 századmásodpercek alatt futott le, az OPTSIL esetén ehhez kb. 10 másodperc kellett. Nyilván 10 másodperce mindenkinek van, de a tesztünk végletesen egyszerű volt. A valóságban ezres-tízezres adatsorok és "rosszabb" osztályozások is szerepelhetnek majd, ott pedig az OPTSIL (Dave tapasztalatai alapján) akár napokig vagy hetekig is futhat, míg a REMOS2 percek, a REMOS1 órák alatt is végezhet.

A javaslatunk szerint az OPTSIL akkor jó megoldás, ha (1) kimondottan az átlagos sziluettet akarjuk optimalizálni; (2) van időnk megvárni a programot. Minden más esetben a REMOS a jobb választás.

Lengyel, A., Roberts, D.W. & Botta-Dukát, Z.: Comparison of silhouette-based reallocation methods for vegetation classification. bioRxiv, https://doi.org/10.1101/630384

Abstract

Aims: To introduce REMOS, a new iterative reallocation method (with two variants) for vegetation classification, and to compare its performance with OPTSIL. We test (1) how effectively REMOS and OPTSIL maximize mean silhouette width and minimize the number of negative silhouette widths when run on classifications with different structure; (2) how these three methods differ in runtime with different sample sizes; and (3) if classifications by the three reallocation methods differ in the number of diagnostic species, a surrogate for interpretability.

Study area: Simulation; example data sets from grasslands in Hungary and forests in Wyoming and Utah, USA.

Methods: We classified random subsets of simulated data with the flexible-beta algorithm for different values of beta.  These classifications were subsequently optimized by REMOS and OPTSIL and compared for mean silhouette widths and proportion of negative silhouette widths. Then, we classified three vegetation data sets of different sizes from two to ten clusters, optimized them with the reallocation methods, and compared their runtimes, mean silhouette widths, numbers of negative silhouette widths, and the number of diagnostic species. 

Results: In terms of mean silhouette width, OPTSIL performed the best when the initial classifications already had high mean silhouette width. REMOS algorithms had slightly lower mean silhouette width than what was maximally achievable with OPTSIL but their efficiency was consistent across different initial classifications; thus REMOS was significantly superior to OPTSIL when the initial classification had low mean silhouette width. REMOS resulted in zero or a negligible number of negative silhouette widths across all classifications. OPTSIL performed similarly when the initial classification was effective but could not reach as low proportion of misclassified objects when the initial classification was inefficient. REMOS algorithms were typically more than an order of magnitude faster to calculate than OPTSIL. There was no clear difference between REMOS and OPTSIL in the number of diagnostic species.

Conclusions: REMOS algorithms may be preferable to OPTSIL when (1) the primary objective is to reduce or eliminate negative silhouette widths in a classification, (2) the initial classification has low mean silhouette width, or (3) when the time efficiency of the algorithm is important because of the size of the data set or the high number of clusters.

Új preprint kézirat az osztályozások validációjáról

A többváltozós osztályozó módszereket rendkívül elterjedten használják, legyen szó vegetációs felvételek, génexpressziós profilok, pszichológiai karakterek vagy talajminták csoportosításáról, hiszen logikailag minden esetben ugyanaz történik: a több jellemzővel leírt objektumokat csoportokba rendezzük úgy, hogy a hasonló objektumok azonos csoportba kerüljenek. Az osztályozás igen fontos lépése, amelyről szerencsére talán egyre kevesebben feledkeznek el, a validáció, vagyis az osztályozás "jóságának" utólagos megítélése. Rengeteg validációs módszer létezik, mind egy kicsit más kritériumok alapján minősíti az objektumok csoportosítását. Az egyik legelterjedtebb validációs index a sziluett index ('silhouette width'), amely minden egyes objektumra megadja, hogy mennyire jól illik a csoportjába. Az értéke -1 és +1 között változik, minél nagyobb, annál jobban illik a csoportba az adott objektum. A 0-hoz közeli értékek kétes besorolást jelentenek, a pozitív értékek jelölik a megfelelően besorolt objektumokat. Ezzel azonosíthatók a csoportok tipikus, átmeneti és kiugró (félreosztályozott) elemei, továbbá az objektumok értékeit csoportonként vagy az egész osztályozásra átlagolva a csoportok, illetve az osztályozás jóságának mutatóit is megkaphatjuk. A sziluett index a hasonló belső variabilitású és kompakt, szférikus alakú csoportokat tekinti jónak, ami nem mindig előnyös, hiszen valós adatsorok esetén a gyakorlati szempontból jól értelmezhető csoportok más alakokat is felvehetnek a változók többdimenziós terében. Munkánkban a sziluett index egy általánosított formuláját mutatjuk be, amelynek szabályozható a kompaktság iránti érzékenysége, így megfelelő beállításokkal elnyújtott alakú csoportokat is jónak fogadhat el.

A sziluett index "viselkedése" különböző beállításokkal három elnyújott csoport esetén. A p paramétert változtatjuk az általánosított formulánkban, a keresztek az objektumok két változó (vízszintes és függőleges tengely) dimenziójában, a bekarikázottakat az index félreosztályozottnak tekinti. MR a félreosztályozottnak tekintett objektumok aránya, MSW az áltagos sziluett index. A p=1 eset a "hagyományos" sziluett index. Látható, hogy a csoportok szélső objektumait, a pontok 11%-át félreosztályozottnak tekinti, míg alacsonyabb p értékekkel ez nem történik meg.

A cikk jelenleg bírálat alatt áll egy folyóiratban, de a szerzői kéziratot már feltöltöttem a bioRxiv nevű preprint szerverre. A preprint publikálás lényege, hogy a felfedezések gyakorlatilag azonnal, még a folyóiratok szakmai bírálata előtt nyilvánossá és hivatkozhatóvá válnak, így megspóroljuk azt a több hónapot, vagy akár évet, ami egy cikk első beküldése és a nyilvános megjelenés között eltelik. A preprint kéziratok szabadon kommentelhetők, folyamatosan javíthatók, viszont utólag nem törölhetők.

A kézirat elérhetősége és összefoglalója:

Lengyel, A. & Botta-Dukát, Z.: Silhouette width using generalized mean - a flexible method for assessing clustering efficiency. bioRxiv 434100; doi: https://doi.org/10.1101/434100

Abstract

Cluster analysis plays vital role in pattern recognition in several fields of science. Silhouette width is a widely used measure for assessing the fit of individual objects in the classification, as well as the quality of clusters and the entire classification. This index uses two clustering criteria, compactness (average within-cluster distances) and separation (average between-cluster distances), which implies that spherical cluster shapes are preferred over others - a property that can be seen as a disadvantage in the presence of clusters with high internal heterogeneity, which is common in real situations. We suggest a generalization of the silhouette width using the generalized mean. By changing the p parameter of the generalized mean between −∞ and +∞, several specific summary statistics, including the minimum, maximum, the arithmetic, harmonic, and geometric means, can be reproduced. Implementing the generalized mean in the calculation of silhouette width allows for changing the sensitivity of the index to compactness vs. connectedness. With higher sensitivity to connectedness instead of compactness the preference of silhouette width towards spherical clusters is expected to reduce. We test the performance of the generalized silhouette width on artificial data sets and on the Iris data set. We examine how classifications with different numbers of clusters prepared by single linkage, group average, and complete linkage algorithms are evaluated, if p is set to different values. When p was negative, well separated clusters achieved high silhouette widths despite their elongated or circular shapes. Positive values of p increased the importance of compactness, hence the preference towards spherical clusters became even more detectable. With low p, single linkage clustering was deemed the most efficient clustering method, while with higher parameter values the performance of group average and complete linkage seemed better. The generalized silhouette width is a promising tool for assessing clustering quality. It allows for adjusting the contribution of compactness and connectedness criteria to the index value, thus avoiding underestimation of clustering efficiency in the presence of clusters with high internal heterogeneity.