Εξηγήσιμη Ομαδοποίηση σε Ευσταθή Στιγμιότυπα

Abstract

Αυτή η διπλωματική ασχολείται με το πρόβλημα της εξηγήσιμης ομαδοποίησης (explainable clustering) κάτω από παραδοχές "ευστάθειας" των εισόδων. Η εξηγήσιμη ομαδοποίηση είναι μια "ερμηνεύσιμη" διαδικασία που αναπτύχθηκε από τους Dasgupta κ.ά. και στοχεύει να παρέχει συνοπτικές εξηγήσεις για την συμπερίληψη κάθε σημείου στη συστάδα του (cluster). Το ερώτημα στο οποίο προσπαθούμε να απαντήσουμε είναι εάν το "Τίμημα της Εξηγησιμότητας", δηλαδή το εγγενές κόστος που προκύπτει εξαιτίας της περιορισμένης μορφής των λύσεων που εγγυώνται την εξηγησιμότητα, μπορεί να μειωθεί εάν υποθέσουμε ότι τα στιγμιότυπα ομαδοποίησης εισόδου ικανοποιούν είτε την ιδιότητα "εγγύτητας" είτε την ιδιότητα της "ευστάθειας σε διαταραχές". Αφού εισαγάγουμε διάφορες έννοιες ευστάθειας στο πλαίσιο της ομαδοποίησης και αναλύσουμε τους πιο σημαντικούς αλγόριθμους για την εξηγήσιμη ομαδοποίηση, αποδεικνύουμε ότι εάν τα στιγμιότυπα εισόδου ικανοποιούν την ιδιότητα της $a$-εγγύτητας με $a=\Omega\left(k d ^ {\frac{1}{p}}\right)$, μπορούμε να πάρουμε εξηγήσιμους αλγορίθμους σταθερού λόγου προσέγγισης. Στη συνέχεια, μελετάμε την ευστάθεια αρκετών δύσκολων στιγμιοτύπων της εξηγήσιμης ομαδοποίησης. Καταφέρνουμε να δείξουμε ότι αυτή η εξάρτηση στο πλήθος των διαστάσεων $d$ και στο πλήθος των clusters $k$ είναι αναγκαία, αφού υπάρχουν ορισμένα δύσκολα στιγμιότυπα ομαδοποίησης, των οποίων η συνάρτηση κόστους είναι η $\mathcal{l}_p$ αντικειμενική συνάρτηση, που ικανοποιούν την $a$-εγγύτητα με $a = \Omega\left(k d ^ {\frac{1}{p}}\right)$, ενώ υπάρχουν στιγμιότυπα που είναι $\Omega(\sqrt{d})$-ευσταθή σε διαταραχές στην περίπτωση του $k$-median clustering ($p = 1$). Για να δείξουμε το δεύτερο αποτέλεσμα, αποδεικνύουμε ότι εάν ένα στιγμιότυπο ομαδοποίησης ικανοποιεί την ιδιότητα της $a$-εγγύτητας μαζί με μια ιδιότητα που διασφαλίζει ότι όλες οι συστάδες στη βέλτιστη ομαδοποίηση έχουν περίπου το ίδιο κόστος, τότε αυτό το στιγμιότυπο είναι $\Omega(\sqrt{a})$-ευσταθές σε διαταραχές. Συμπεραίνουμε ότι δεν είναι εύλογο να υποθέσουμε ότι τα στιγμιότυπα ομαδοποίησης που συναντάμε στην πράξη είναι αρκετά ευσταθή (με την έννοια των παραπάνω παραδοχών), ώστε να μειωθεί το Τίμημα της Εξηγησιμότητας.