algoritme voor 'clusteren' van relaties

[MKe]

Hoi,
Ik heb een lijst van strings en een lijst van tuples die een relatie moet voorstellen. Nu wil ik groepen maken van alle items die steeds wat met elkaar te maken hebben. Ik heb wel een algoritme bedacht die werkt, maar hij schaalt erg slecht en is erg traag. Weet iemand een betere, efficientere en vooral snellere manier?

Ik heb het volgende bedacht (en misschien maakt dit voorbeeld het ook duidelijker):

Code: [Selecteer]

# Ik maak voor de duidelijkheid 3 lijsten als input
items1 = ['a{0}'.format(i) for i in range(10)]
items2 = ['b{0}'.format(i) for i in range(3)]
items3 = ['c{0}'.format(i) for i in range(3)]
relaties = [ # de lijst van relaties
        ('a0','b0'),
        ('a0','c0'),
        ('b0','c0'),
        ('a1','b1'),
        ('b1','c1'),
        ('a1','c1'),
        ('b2','c2'),
        ('a2','c2'),
        ]
# beginnen met elk item in zijn eigen groep, dit is dus een lijst van lists
groups = [[i,] for i in items1 + items2 + items3]

# een paar hulp functies
def findindex(group, item):
    """
    een functie om per item de index te vinden van de group waar hij inzit
    """
    for g in group:
        if item in g:
            return group.index(g)
    return None # return none als niet gevonden is

def optellen(group, index1, index2):
    # voegt groepen samen indien ze gevonden zijn en de items niet al in dezelfde groep zit
    if not index1 == index2 and index1!=None and index2!=None:
        group[index1]+=group[index2]
        del group[index2]
    return group

# nu uitvoeren
for i1, i2 in relaties:
    groups = optellen(groups, findindex(groups, l1), findindex(groups,l2))
Dit werkt (sorry voor de rare volgorde, het is geen script, maar ik heb het uit een ipython-notebook gekopieerd zoals ik aan het klooien was)

de uitkomst is:

Code: [Selecteer]

groups
[['a0', 'b0', 'c0'],
 ['a1', 'b1', 'c1'],
 ['a2', 'b2', 'c2'],
 ['a3'],
 ['a4'],
 ['a5'],
 ['a6'],
 ['a7'],
 ['a8'],
 ['a9']]je ziet dus dat niet alle items in een groep een relatie hoeven te hebben, maar dat de relatie ook indirect mag zijn.

[erik1984]

Lastig probleem. De complexiteit zit 'm in het stukje findindex() neem ik aan, dat voor elk item in een relatietupel steeds len(groups) moet worden nagelopen in het worst case scenario. Een directe algoritmische verbetering kan ik niet meteen bedenken maar je zou misschien wel winst kunnen halen door de datastructuur te veranderen.  Bijvoorbeeld een dictionary waar elk element een index is en die verwijst naar in welke groep dat element zit. De lookup zou dan theoretisch goedkoop moeten zijn omdat een dictionary de sleutel hasht als ik het goed heb begrepen.

Heb zelf iets geschreven met dictionary en in principe is het resultaat gelijk. Je hebt alleen niet zo'n mooi overzicht van de unieke groepen. Dat zou je weer uit de dictionary moeten filteren en dat zou bij grote datasets ook weer duur kunnen zijn dus misschien schiet je er wel niets mee op

Maar goed, voor wat het waard is:

Code: [Selecteer]

# Ik maak voor de duidelijkheid 3 lijsten als input
items1 = ['a{0}'.format(i) for i in range(10)]
items2 = ['b{0}'.format(i) for i in range(3)]
items3 = ['c{0}'.format(i) for i in range(3)]
relaties = [ # de lijst van relaties
        ('a0','b0'),
        ('a0','c0'),
        ('b0','c0'),
        ('a1','b1'),
        ('b1','c1'),
        ('a1','c1'),
        ('b2','c2'),
        ('a2','c2'),
        ]
# beginnen met elk item in zijn eigen groep, dit is dus een lijst van lists
groups = [[i,] for i in items1 + items2 + items3]

# woordenboek met voor elk item een groep
groupdict = dict()
for i in groups:
    groupdict[i[0]] = i

# voor
print(groupdict)

for i1, i2 in relaties:
    if groupdict[i1] != groupdict[i2]:
        # twee items zitten niet in zelfde groep
        list1 = groupdict[i1]
        list2 = groupdict[i2]
        # plak lijsten aan elkaar
        list3 = list1 + list2
        # laat elk item naar nieuwe lijst wijzen
        for item in list3:
            groupdict[item] = list3

# na
print(groupdict)


[MKe]

Hoi Erik,

Bedankt, ik zat ook al te denken aan een dictionary, maar hoopte dat er betere mogelijkheden zouden zijn, algoritmisch gezien dan. Dit ziet er wat knullig uit naar mijn mening
Het maakt trouwens enorm veel uit, dus het is een hele goede suggestie. De filterstap gaat redelijk snel, dus geen probleem daar.
 Ik heb het nog wat verbeterd, door de relaties ook in een dictionary te zetten. Hierdoor komen de clusters wel niet in de juiste volgorde terug, maar dat geeft niets. Ik vind het wel prettig dat ik daardoor meer controle heb over de indices. De keys in de cluster dictionary zijn rouwens onbelangrijk. Ze hoeven alleen maar uniek te zijn.
Hij doet nu 135000 items in een fractie van een seconde, en wat belangrijk is, zonder te crashen.
De nieuwe code:

Code: [Selecteer]

# input, veel groter dit keer:
items = ['a{0}'.format(i) for i in range(50000)]
items += ['b{0}'.format(i) for i in range(40000)]
items + = ['c{0}'.format(i) for i in range(45000)]
# dus ook een grote lijst relaties
relaties = [('a{0}'.format(i), 'b{0}'.format(i)) for i in xrange(40000)]
relaties  += [('c{0}'.format(i), 'b{0}'.format(i)) for i in xrange(40000)]
relaties += [('a{0}'.format(i), 'c{0}'.format(i)) for i in xrange(45000)]

# De belangrijkste functie, deze maakt de clusters
def plaatsen(i, ind, cl):
    try:
        p1 = ind[i[0]]
        p2 = ind[i[1]]
    except KeyError:
        return
    if p1 != p2:
        cl[p1]+=cl[p2]
        for item in cl[p2]:
            ind[item] = p1
        del cl[p2]

# nu de uitvoering, eerst cluster dictionary, hier komt het resultaat in
cluster = { i: [i,] for i in items } # dit is python 2.7 compatible, werkt niet in 2.6
index = { i: i for i in items } # dit is python 2.7 compatible, werkt niet in 2.6

# nu het loopje:
for r in relaties:
    plaatsen(r, index, cluster)

Zoals gezegd, dit is een gigantische versnelling. De eerdere code crashte na een half uur of zo.

of topic: Wel een geweldig systeem dan ipython notebook. Ik gebruik dat nu voor het eerst, maar het is de ideale manier om wat aan te klooien en te zien wat er gebeurt.

[SeySayux]

Wat jij wilt heet het connected component (verbonden subgraaf) probleem binnen de grafentheorie.

Ik zou hier ongeveer het volgende algoritme voor gebruiken (pseudocode):

Code: [Selecteer]

dict<node, list<node>> connections; // Datstructuur: dictionary met als key nodes en als value de lijst waarmee ze verbonden zijn

// Ga over je paren heen en steek deze in de dictionary
for(pair p : relations) {
    connections[p.1] += p.2; // voeg p.2 toe aan de verbindingen van p.1
}

list<list<node>> components; // Uitvoerlijst

list<node> currcomponent; // werklijst

while(!connections.empty()) {
    // Neem een key/value paar uit de dictionary
    node k = connections.firstKey();
    list<node> c = connections[k];
    connections.remove(k);

    // Voeg k toe aan onze huidige component
    currcomponent += k;
 
    // Zolang c niet leeg is
    while(!c.empty()) {
        // Neem het eerste element uit c:
        node n = c.first();
        c.remove(n);

        // Voeg n toe aan de component:
        if(n notin currcomponent) {
            currcomponent += n;
        }

        // Neem de verbindingenlijst van n, en steek deze ook bij c:
        list<node> nc = connections[n];
        connections.remove(nc);
        c += nc;
    }

    // We hebben onze component:
    components += currcomponent;
    currcomponent.clear();
}

// Klaar!
print(components);

Dit algoritme haalt de knopen die met elkaar zijn verbonden geleidelijk aan uit de dictionary totdat er geen knopen meer zijn die met de gegeven knoop en neemt dan een nieuwe. Wanneer de dictionary leeg is, hebben we alle verbonden subgrafen gevonden.

[MKe]

Geweldig, je hebt een naam waar ik op kan zoeken.  Het klopt inderdaad. Ik ga hier eens induiken. Ik moet zowiezo meer weten over de graphtheories.

Bedankt