Положение узла в дереве как векторный элемент?

Question

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

Моя проблема Я представляю все функции как вектор чисел. Любые мысли о том, как я могу представить положение в дереве как вектор? Так что расстояние б / п двух векторов соответствует расстоянию между узлами в дереве? (У меня небольшое дерево глубиной около 5-7 и ветвями около 2-3)

Что я пробовал Постскриптум Я читал об алгоритмах, чтобы найти кратчайшее расстояние между двумя узлами (нахождение расстояния каждого из них до их ближайшего общего предка). Одна идея, которую я нашел, состояла в том, чтобы иметь вектор x, где каждый индекс соответствует возможным предкам в дереве. Затем установите x [i] = количество уровней от этого предка. Проблема в том, что я не знаю, что делать с узлами, которые не являются предками.

Answer 1

Так что на самом деле есть очень хороший способ получить нужные функции;Вы можете сделать это с MDS .

Что делает MDS, так это то, что она принимает матрицу N на N (здесь N - количество узлов), где запись a_ {i, j} - это расстояние между элементом i и элементом j (узлом i и узлом j)и для каждого элемента i он вернет D (предварительно заданный) вектор положения D_i, так что расстояние между D_i и D_j составляет приблизительно a_ {i, j}.

Таким образом, мы можем получить ваш вектор объектов с небольшой предварительной обработкой.Сначала найдите кратчайшее расстояние (в прыжках) для каждой пары узлов (вы можете использовать Floyd-Warshall ), затем используйте матрицу расстояний в качестве входных данных для MDS и укажите количество измерений для вашего вектора положения, и MDS выведет векторы положения указанных размеров.

Если вы будете искать в Интернете, я уверен, что вы сможете найти реализации с открытым исходным кодом для Floyd-Warshall и MDS.

Answer 2

просто укажите путь к дереву как вектор.затем просто рассчитайте длину разницы между двумя путями.так например.2,3,1,5,3 это один путь.и 2,3,3,5,9,5 другой путь.так что 2,3 они имеют общее.таким образом, длина разницы составляет 1,5,3 и 3,5,9,5, что составляет 7. удачи