Алгоритм дискретной метрики подобия

Question

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

Пример:

A = {Джон,Мэри, Кейт, Питер} и B = {Питер, Джеймс, Мэри, Кейт}

Насколько похожи эти два списка?Обратите внимание, что я не знаю всех элементов общего надмножества.

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

Я мог бы даже добавить дополнительное измерение, что более низкие индексы имеют большую ценность, поэтому aa [1] == b [1] стоитбольше, чем a [9] == b [9], но это в основном потому, что мне любопытно.

Answer 1

Индекс Жакара ( он же коэффициент Танимото) используется именно для случая использования, изложенного в вопросе ОП.

Коэффициент Танимото тау равен Nc , деленному на Na + Nb - Nc , или

tau = Nc / (Na + Nb - Nc)

• Na , количество предметов в первом наборе

• Nb , количество предметов во втором наборе

• Nc , пересечение двух наборов или количество уникальных предметов общий для a и b

Вот Tanimoto, закодированный как функция Python:

def tanimoto(x, y) :
  w = [ ns for ns in x if ns not in y ]
  return float(len(w) / (len(x) + len(y) - len(w)))

Answer 2

Я бы изучил две стратегии:

1. Рассматривать списки как наборы и применять набор операций (пересечение, разность)
2. Обрабатывать списки как строки символов и применять алгоритм Левенштейна

Answer 3

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

Если у вас есть (или вы можете получить) счетчики и / или более двух из них, вы можете сделать немного лучше, чем что-то вроде косинус симлиарности или TFIDF (термин частота * инвертированная частота документа).

Последний пытается дать более низкий вес словам, которые встречаются во всех (или почти) всех «документах», то есть наборах слов.

Answer 4

Если заказ имеет значение, вы можете использовать Расстояние Левенштейна или другой вид Изменить расстояние .

Answer 5

Как вы определяете «измерение сходства»?Если все, что вам нужно, это то, сколько предметов в наборе являются общими друг с другом, вы можете найти количество элементов A и B, сложить количество элементов вместе и вычесть из количества элементов объединения A и B.