Выполнение «нечеткой» реализации индекса Jaccard

Question

Я пытаюсь вычислить нечеткий индекс Jaccard между двумя наборами с следующим обоснованием: как индекс Jaccard, я хочу рассчитать соотношение между количеством элементов, которые являются общими для обоих наборов и общего количества различных элементов в обоих наборах. Проблема заключается в том, что я хочу использовать функцию сходства с порогом, чтобы определить, что то, что имеет значение, как «же» пункта, находящегося в обоих наборах, так что элементы, которые похожи:

1. не учитываются дважды в союз
2. Учитываются на пересечении.

У меня есть рабочая реализация здесь (в Python):

def fuzzy_jaccard(set1, set2, similarity, threshold): 

    intersection_size = union_size = len(set1 & set2) 
    shorter_difference, longer_difference = sorted([set2 - set1, set1 - set2], key=len) 

    while len(shorter_difference) > 0:   
     item1, item2 = max(
      itertools.product(longer_difference, shorter_difference), 
      key=lambda (a, b): similarity(a, b) 
     ) 
     longer_difference.remove(item1) 
     shorter_difference.remove(item2) 

     if similarity(item1, item2) > threshold: 
      union_size += 1 
      intersection_size += 1 
     else: 
      union_size += 2 
    union_size = union_size + len(longer_difference) 

    return intersection_size/union_size 

Проблема вот это квадратичный по размеру множеств, потому что в itertools.product я итерацию во всех возможных пар элементов взято по одному из каждого набора (*). Теперь, я думаю, я должен это сделать, потому что хочу соответствовать каждому элементу a от set1 с максимально возможным кандидатом b от set2, который не похож на другой предмет a' от set1.

У меня такое ощущение, что должно быть O(n) способ сделать это, я не понимаю. Есть ли у вас какие-либо предложения?

Есть еще две проблемы, такие как пересчет подобия для каждой пары, как только я получу лучший матч, но я не очень-то о них беспокоюсь.

Answer 1

Я сомневаюсь, что в общем случае будет O (n), но вы, вероятно, можете сделать намного лучше, чем O (n^2), по крайней мере, для большинства случаев.

Является ли сходство транзитивным? Под этим я имею в виду: можете ли вы предположить, что расстояние (a, c) < = расстояние (a, b) + расстояние (b, c)? Если нет, этот ответ, вероятно, не поможет. Я рассматриваю сходство, такое как расстояния.

Попытка слипания данные:

Выберите радиус г. Основываясь на интуиции, я предлагаю установить r на одну треть среднего из первых 5 сходств, которые вы подсчитаете, или что-то еще.

Первое, что вы выбрали в set1, становится центром вашего первого скопления. Классифицируйте точки в set2 как находящиеся в скоплении (сходство с центральной точкой < = r) или вне кластера. Также отслеживайте точки, находящиеся в пределах 2r от центра клинка.

Вы можете потребовать, чтобы центральные точки скопления были как минимум на расстоянии 2r друг от друга; в этом случае некоторые точки могут отсутствовать в любом компе. Я предлагаю сделать их как минимум r друг от друга. (Может быть, меньше, если вы имеете дело с большим количеством измерений.) Вы можете рассматривать каждую точку как центр скопления, но тогда вы не сохранили бы время обработки.

Когда вы выбираете новую точку, сначала сравните ее с центральными точками скопления (хотя они находятся в одном наборе). Либо он находится в уже существующем скоплении, либо он становится новым центром скопления (или, возможно, ни одним, если он находится между r и 2r центра скопления). Если он находится внутри r центра скопления, то сравните его со всеми точками в другом наборе, которые находятся в пределах 2r от этого центра скопления. Возможно, вы сможете игнорировать точки, превышающие 2r, от центра скопления. Если вы не найдете подобную точку в компе (возможно, из-за того, что в компу не осталось точек), вам может потребоваться отсканировать все остальные точки для этого случая.Надеюсь, это произойдет в основном только тогда, когда в наборе осталось мало очков. Если это хорошо работает, то в большинстве случаев вы найдете самую схожую точку в компе и знаете, что это самая близкая точка.

Эта идея может потребовать некоторой настройки.

Если имеется большое количество измерений, то вы можете обнаружить, что при заданном радиусе r неудовлетворительно много точек находятся в пределах 2r друг от друга, в то время как немногие находятся внутри r друг от друга.

Вот еще один алгоритм. Чем более трудоемким является вычисление вашей функции сходства (по сравнению со временем, которое требуется для сохранения отсортированных списков точек), тем больше очков вы можете захотеть. Если вы знаете количество измерений, имеет смысл использовать это количество индексных точек. Вы можете отклонить точку в качестве точки индекса кандидата, если она слишком похожа на другую точку индекса.

Для каждого из первой точки вы используете, и любые другие, которые вы решили использовать в качестве точек индекса, создать список всех остальных точек в другом наборе, отсортированных в порядке расстояния от точки индекса,

Когда вы сравниваете точку P1 с точками в другом наборе, я думаю, вы можете пропустить множество по двум возможным причинам. Рассмотрим наиболее близкую точку P2, которую вы нашли для P1. Если P2 похож на индексную точку, вы можете пропустить все точки, которые в значительной степени отличаются от этой индексной точки. Если P2 не совпадает с точкой индекса, вы можете пропустить все точки, которые достаточно похожи на эту индексную точку. Я думаю, что в некоторых случаях вы можете пропустить некоторые из двух типов точек для одной и той же точки индекса.