Как рассчитать «похожесть» двух словарей?

Question

[pcdesign]

Вот, например, два словаря:

Апельсин 1
Яблоко 2
Банан 3

Апельсин 2
Яблоко 2
Инжир 1

На сколько одна накладная "похожа" на другую и получить коэффициент похожести?
Я понимаю, что скорее всего надо это решать с помощью https://ru.wikipedia.org/wiki/Коэффициент_Жаккара
На сколько долгий будет расчет просто с бумажкой и ручкой без компа?

Comments

[hint000]

Надо бы уточнить условия. Первая строка в двух словарях будет считаться сходством или различием?

[pcdesign]

hint000, да, считается сходством. Если и в первом и во втором словаре есть апельсин, то конечно это сходство.

[12rbah]

Вам стоит уточнить то, что вы понимаете под "похожестью", потому что из условия не совсем понятно что вы хотите, т.к. есть несколько методик по расчету таких коэфициентов,

На сколько долгий будет расчет просто с бумажкой и ручкой без компа?

на этот вопрос не ответить т.к. вы не выбрали метод для определения похожести.

[pcdesign]

12rbah, меня вполне устроит коэффициент Жаккара.

[12rbah]

pcdesign, тогда в чем пробема подставить значения в формулу и расчитать? (сначала с бумажкой и ручкой)

upd: как я понял вы хотите, чтобы значения ключей тоже учитывались тогда "a+b" у вас должно быть равно сумме значений ключей, а "c" кол-ву схожих элементов 3/(6+5-3) для вашего случая.

[pcdesign]

12rbah, в том что это словарь, а не список.

[12rbah]

pcdesign, алгоритм такой:
1) подсчитываете значение ключей в первом словаре
2) подсчитываете значение ключей во втором словаре
3) находите одинаковые ключи в словарях
4) берете меньше значение из 2 и суммируете с переменной, которая играет роль "c"
5) рассчитываете значение по формуле

[Александр Маджугин]

Не совсем понятно как вы собираетесь применить коэффициент Жаккарда в чистом виде, если у вас важно количество? Очевидно требуется какая-то модификация и вероятно их можно придумать несколько вопрос лишь в том, что именно вы в своем случае понимаете под похожестью и для чего собираетесь использовать.

Что более важно для похожести - наличие элемента или его количество?

Самое примитивное решение в лоб использовать "дробное" количество видов. Например считать за один вид максимальное количество по обеем накладным. В данном случае у вас 2 вида в первой накладоной, и 1,66 во второй, и разность 1,66

[pcdesign]

Александр Маджугин, Коэффициент сходства меня интересует, если слово "похожесть" смущает.

Наличие элемента - важнее кол-ва.

[Александр Маджугин]

pcdesign, ну я и предлагаю лобовое решение для такого случая.

Если бы количество было важнее, тогда вопросов вообще нет - просто Апельсин:1 и Апельсин:2 - можно бы было считать за два разных вида.

[pcdesign]

Александр Маджугин, спасибо, я нашел готовое решение. Вот если любопытно
https://stackoverflow.com/questions/35980910/retur...

[Александр Маджугин]

pcdesign, ну тут отсутствие элемента это фактически его наличие с нулевым количеством, а вы говорили, что вам важнее отсутствие/наличие чем количество.
Но можно взять среднее между Жаккадом и этим методом... не знаю как его назвать - нормализованной дистанции?

Answer 1

[o5a]

Если значения ключей не важны для сравнения, то достаточно использовать keys()

d1 = {'Апельсин': 1,
'Яблоко': 2,
'Банан': 3
}

d2 = {'Апельсин': 2,
'Яблоко': 2,
'Инжир': 1
}

print(d1.keys())
# общие ключи
print(d1.keys()&d2.keys())

Судя по ссылке, этого достаточно для расчета Вашего коэффициента.

Comments

[pcdesign]

Значения важны.
Иначе вопрос был бы как сравнить два списка и вычислить похожесть двух списков.
И вопрос стоит в коэффициенте похожести, а не в банальном сравнении ключей.

[o5a]

pcdesign, в таком случае видимо речь про расширенную формулу

Насколько я понимаю, она подразумевает это:

def coeffj(d1, d2):
    a = sum(d1.values())
    b = sum(d2.values())
    c = sum(min(d1.get(key,0), d2.get(key,0)) for key in d1.keys()|d2.keys())
    return c/(a + b - c)

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

[pcdesign]

o5a, спасибо, возможно это то что нужно :)
Я еще нашел вот этот пост:
https://stackoverflow.com/questions/35980910/retur...

Надо прикинуть теперь.

[pcdesign]

o5a, остановился на вашем варианте, он оказался самым точным для моей задачи. Спасибо еще раз!

Answer 2

[isol]

Посмотрите на Bloom Filter. Возможно пригодится. Если построить bloom filter для каждого множества, то можно сравнивать насколько похожи фильтры.

Answer 3

[Wataru]

Если отсутствие слова в словаре равносильно слову с весом в 0, то можно считать какую-угодно меру от векторов чисел. Хоть корень из суммы квадратов разностей по каждому слову.

В вашем примере это будет (1-2)^2+(2-2)^2+(3-0)^2+(1-0)^2 = 11.
Чем меньше это число, тем похожее словари. Можно ее еще как-то нормировать, поделив на, допустим количество уникальных ключей в обоих словарях. Или на количество всевозможных слов.

Если ваш язык/структура позволяет пройтись по словарю в лексикографическом порядке, то можно подсчитать такую меру за линейное время выполняя что-то вроде слияния сортированных списков. Изначально 2 указателя на минимальные элементы (по словарю) в каждом словаре. Если два элемента с одинаковым ключем, то считайте разность двух весов и двигайте оба указателья. Иначе считайте разность веса с минимальным ключем и 0 и двигайте только этот указатель. Случай, когда один из словарей уже пуст совпадает со вторым случаем.

В питоне позволяет обходить ключи по порядку OrderedDict.