Ustaw podobieństwo - Oblicz indeks Jaccard bez kwadratowej złożoności

Mam grupę n zestawów, dla których muszę obliczyć wartość „unikatowości” lub „podobieństwa”. Jako odpowiedni wskaźnik zdecydowałem się na indeks Jaccard . Niestety indeks Jaccard działa tylko na dwóch zestawach na raz. Aby obliczyć podobieństwo między wszystkimi zbiorami, będzie to wymagało w kolejności obliczeń Jaccard. $n$ $n^2$

(Jeśli to pomaga, wynosi zwykle od 10 do 10000, a każdy zestaw zawiera średnio 500 elementów. Na koniec nie obchodzi mnie, jak podobne są dwa dowolne określone zestawy - zależy mi raczej na wewnętrznym podobieństwie całej grupy zbiorów jest (innymi słowy, średnia (lub przynajmniej wystarczająco dokładne przybliżenie średniej) wszystkich indeksów Jaccard w grupie)) $n$

Dwa pytania:

Czy istnieje sposób, aby nadal używać indeksu Jaccard bez złożoności ? $n^2$
Czy istnieje lepszy sposób obliczenia podobieństwa / wyjątkowości zestawu w grupie zbiorów niż sposób, który zasugerowałem powyżej?

algorithms time-complexity

— rinogo
źródło

Czy możesz najpierw wyjaśnić, co rozumiesz przez „wewnętrzne podobieństwo”?

— Suresh,

Innymi słowy, średnia (lub przynajmniej wystarczająco dokładne przybliżenie średniej) wszystkich indeksów Jaccard w grupie.

Jeśli chcesz zbliżyć się do odpowiedzi, możesz użyć skrótu minimalnego, aby oszacować przybliżoną odległość Jaccard, a następnie użyć wynikowej reprezentacji do obliczenia pożądanej średniej.

— Suresh

Nie wiem, co rozumiesz przez „wystarczająco dokładny”, ale jednym ze sposobów oszacowania średniej wielu rzeczy jest po prostu obliczenie kilku z nich (w tym przypadku indeksów Jaccard kilku par zestawów) i obliczenie ich średniej. Następnie możesz użyć granicy Chernoffa, aby uzyskać górną granicę prawdopodobieństwa, że ta ocena jest daleka od prawdziwej średniej.

— Tsuyoshi Ito,

Odpowiedzi:

Opcją może być zastosowanie schematu sygnatur [1], filtrowania opartego na rozmiarach : schematu, który wykorzystuje informacje o rozmiarze w celu zmniejszenia liczby par zestawów, które należy wziąć pod uwagę.

Eksperymentują także z formą ważoną; gdzie wagi są oparte na IDF.

[1] Arasu, Arvind, Venkatesh Ganti i Raghav Kaushik. „Skuteczne łączenie dokładnego podobieństwa zestawu”. W materiałach z 32. międzynarodowej konferencji na temat bardzo dużych baz danych, 918–929. VLDB '06. VLDB Endowment, 2006

— W
źródło

Wydaje się, że ten link umarł. Rozważ zaktualizowanie go do vldb.org/conf/2006/p918-arasu.pdf .

— j_random_hacker

Inną opcją byłoby zastosowanie linku wiki mieszającego lokalną wrażliwość . Widziałem, jak Wu i Zou używają go do wykrywania podobieństwa w społeczności ( Inkrementalna metoda wykrywania społeczności dla systemów tagowania społecznościowego wykorzystujących haszowanie wrażliwe na lokalizację , Neural Networks 58: 14–28; ACM DL ), który zasadniczo wykrywa podobieństwo między liczbami całkowitymi lub zestawy strun.

— dinos66
źródło

Proszę streścić zawartość linków i zacytować artykuł. Jeśli linki przestaną być aktualne, bieżąca odpowiedź stanie się bezużyteczna.

— vonbrand