Рассчитать подобие взвешенных деревьев

Question

Структура моего дерева проста, глубина - две, каждый дочерний узел является прямым потомком корня, а каждый узел имеет вес, за исключением корня. Есть ли хороший способ измерить сходство двух деревьев?
Оригинальный вопрос:
Предположим, у вас есть список данных о книгах, которые вы прочитали. Список содержит ключи и значения, такие как хэш-таблица. Ключи - это категории книг, а значения - это количество книг, которые вы прочитали в текущей категории. Поэтому у каждого человека есть этот список данных, я хочу сравнить сходство двух пользователей на основе этого списка данных. Я знаю, что совместная работа может это сделать, но я стараюсь так и сравниваю ее с cf.
Поэтому я рассматриваю список данных как взвешенное дерево. Категории - это дочерние узлы, вес каждого дочернего узла - это время, которое эта категория отображается в книгах пользователя.
Сходство аналогично сходству двух пользователей в совместной работе. Это номер.

Answer 1

Это можно сделать, используя операции установки.

Я однажды применил такую ​​метрику сходства в программном обеспечении Meta-CVS, много лет назад. Это было использовано для идентификации переименованных файлов при импорте снимков в ветку. Конечно, файлы можно переименовать и отредактировать между базовыми линиями, что означает, что вы не можете выполнять точные сравнения. Но я отвлекся.

Jaccard Index1

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

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

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

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

Как вы можете видеть, эта метрика дает 0.0, если у пользователей нет общих категорий, и 1.0, если они заинтересованы в сопоставлении категорий (независимо от веса), поэтому они жизнеспособны.

косинус Сходство2

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

Тогда вы можете рассчитать сходство, взяв точечный продукт этих векторов и разделив его на произведение их длины: (A.B)/| A || B |

Длина вектора представляет собой квадратный корень из суммы квадратов весов. (Опять же, наблюдайте за делением на ноль.)

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

Надеюсь, это даст вам некоторые идеи; но, как вы можете видеть, это открыто.