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 n 2 obliczeń Jaccard.
(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))
Dwa pytania:
- Czy istnieje sposób, aby nadal używać indeksu Jaccard bez złożoności ?
- 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
źródło
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
źródło
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.
źródło