Pomiędzy bitami

Przy okazji projekciku^[1] trafiłem na interesujący problem. Chodzi o porównywanie zbiorów, a dokładnie liczenie ich podobieństwa. Marzyło mi się, by wyrazić je w zakresie 0 do 1, gdzie 0 to zbiory rozłączne, a 1 zbiory identyczne^[2].

Popełniłem następujący kawałek kodu, liczący, na ile set2 jest podobny do set1:

def count_similarity_percent(set1, set2):
    base_count = len(set1)
    if base_count == 0:
        base_count = 1
    matching = 0
    for element in set1:
        if element in set2:
            matching += 1
    perc = 100 * matching / base_count
    return perc

Niby działa, ale… Spójrzmy na przykłady.
Przykład 1:

A = [1, 2, 3, 4]
B = [3, 4, 5, 6]

Podobieństwo A do B wynosi 50% (2 z 4 elementów ze zbioru A występują w B).
Podobieństwo B do A także wynosi 50% (2 z 4 elementów ze zbioru B występują w A).
Wszystko fajnie. Podobieństwa są równe, niezależnie z której strony patrzeć.

Niestety, jeśli zbiory będą miały różną ilość elementów, to sprawa się komplikuje i podobieństwo A do B przestaje być równe podobieństwu B do A. Możemy to zobaczyć w kolejnym przykładzie.
Przykład 2:

A = [1, 2, 3, 4]
B = [3, 4]

Podobieństwo B do A to nadal 50%.
Podobieństwo A do B wynosi 100% – 2 z 2 elementów A występują w B.

Nie spodobało mi się to i zastanawiałem się, co można z tym zrobić. Z jednej strony chciałem, by wartości były przechodnie, tj. równe, niezależnie z które strony porównuję.

Przez głowę przeleciało mi szybko liczenie średniej z podobieństw i zapamiętywanie w obu przypadkach tego wyniku. Podobnie mógłbym zapamiętywać w obu wynikach większą – lub mniejszą – z wartości podobieństwa. Z drugiej strony kołatało mi się, że fajnie nie byłoby liczyć dwa razy.

Poszukałem, popytałem i okazało się, że są do tego miary. W tym przypadku miarą podobieństwa zbiorów jest indeks Jaccarda^[3] . Jest prosta i „przechodnia”, tj. nie ma znaczenia, który zbiór z którym się porównuje.

Znalazłem taki wpis o indeksie Jaccarda dla Pythona, ale przyznaję, że nie spodobała mi się implementacja. Po pierwsze, bez sensu importowane jest numpy, które w tym przypadku niczego nie robi. Po drugie, implementacja jest poprawna, ale nieco zakręcona. Lepiej implementować na setach, nie listach. I jak najbardziej można skorzystać z wbudowanego union, a następnie liczyć wprost, wg definicji.

def jaccard_index_percent(set1, set2):
    intersection_count = len(set1.intersection(set2))
    union_count = len(set1.union(set2))
    if union_count == 0:
        union_count = 1
    return 100 * intersection_count / union_count

Zapewne użyję ww. wersji do porównywania zbiorów. Chyba, że pokuszę się jeszcze kiedyś o optymalizację pod kątem prędkości działania. O ile zauważę taką potrzebę.

[1] Jeśli coś się z tego wykluje sensownego, to niebawem opiszę dokładniej.
[2] Od 0 do 1, od 0% do 100%, bez znaczenia, wartość jest taka sama. Choć IMO ludzie lepiej rozumieją procenty, a łatwiej kodować na float. Ale to wszystko nieistotny detal.
[3] Linkuję we wpisie polską wersję, która jest lakoniczna, ale prostsza. Jeśli ktoś jest bardziej zainteresowany tematem, to polecam wersję angielską, wraz z see also.