Clustering in python

Pubblicato: 1 ottobre 2008 in Python, Tecnico
Tag:,

Premessa: non si parla di algoritmi di clustering, né viene data una soluzione per il clustering. Si parla di una forma microscopica di aggregazione che serve solo in alcune situazioni molto particolari.

Nei progetti che seguo succede spesso una situazione di questo genere: ho diverse collezioni di articoli caratterizzate dal fatto che gli articoli di ciascuna collezione sono correlati in qualche modo tra loro, ad esempio condividono almeno un tag o ricadono nella stessa categoria o sono correlati a causa dell’insindacabile giudizio del motore semantico.

Quello che succede, spesso, è che alcuni articoli compaiono ripetuti in diverse collezioni. I motivi possono essere ovvi: le collezioni rappresentano diversi tag oppure la metrica con cui sono state costruite queste collezioni ha una soglia che taglia in due la transitività: se A è vicino a B (e stanno nella stessa collezione) e B è vicino a C (e stanno in un’altra collezione) succede che B compare in due collezioni e che A e C risultano separati. Oppure i motivi possono essere anche più strani e non li spiegherò in dettaglio, ad esempio l’appartenere o meno ad una certa collezione può dipendere da motivi cronologici.

In alcune situazioni, quando si parla di “correlazioni” vere e proprie come si possono vedere in una pagina relativa ad un tag di Moltomoda, ad esempio questa, in basso dove ci sono, appunto, i “Tag correlati”, può essere necessario raggruppare tra loro le collezioni che condividono almeno un elemento per creare dei veri e propri clusters di articoli che siano semplicemente connessi e all’interno dei quali valga la proprietà transitiva AcB ^ BcC => AcC

Volevo allora condividere la soluzione che utilizzo in produzione, una funzione ricorsiva, che lungi dall’essere perfetta mi affascina perché è il mio personalissimo giardino dei sentieri che si biforcano ed è anche una forma di accostamento ad Almotasim, se qualcuno vuole contribuire è tutto ben accetto.

def estrai_correlati(correlati):
        # correlati e' una list di sets. I set sono set di ID
        # in uscita correlati sara' una lista di sets semplicemente connessi
        if len(correlati) == 0:
                # fine della ricorsione
                return
        temp = set()
        cluster = set()
        for c in correlati[:]:
                # c e' un set di ID gia' correlati tra loro
                # puo' essere un singoletto
                if len(temp) == 0:
                        # vedo se il primo della list (lol) si puo' estendere
                        temp = c
                        correlati.remove(c)
                        continue
                if len(temp & c) > 0:
                        # intersezione non vuota, lo estendo
                        cluster = temp | c
                        temp = cluster
                        correlati.remove(c)
        if len(cluster) > 0:
                # prima biforcazione, il primo della list e' cresciuto
                correlati.append(cluster)
                estrai_correlati(correlati)
        else:
                # seconda biforcazione, il primo della list non e' cresciuto
                estrai_correlati(correlati)
                correlati.append(temp)
        return

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...