Блог

Например. можно было бы сказать, что «кит» — это «потомок» animal, но «кит» больше похож на «дельфина», чем на «собаку». В данном случае «кит», «дельфин», «собака» являются дочерними элементами animal, но «кит» и «дельфин» явно связаны.

Меня НЕ интересует простое определение дополнительных подклассов (например, «морские животные», «наземные животные») приведенный выше пример приведен только для иллюстрации … предположим, мы не можем «определить» наш выход из проблемы.

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

РЕДАКТИРОВАТЬ: Ряд людей попросили дополнительных разъяснений. Я буду использовать тот же пример, но, вероятно, остановлюсь на более подробных

Допустим, у нас есть следующие категории:

     Animals, Place, Object.
    The following sub categories: [land animals, sea animals], [country, state],
 [heavy object, light object]
    And we have the following entries: Whale, Dolphin, Dog, Cat, Hawaii, Japan,
 London, Stone, Rock, Leaf, Car.

    I have an isLike(entry x) function that I can call on any of the entries.

    for example say whale.isLike(dolphin) = 0.7, whale.isLike(dog) = 0.2 and
a table like the following one stores all the values for the isLike() function

            Whale dolphin dog cat hawaii japan london stone
    whale   1     0.7     0.2 0.2  0.01   0.01  0.01   0.008
    dolphin 0.7   1       0.2 0.2  0.01   0.01  0.01   0.008
    dog      etc
    cat      etc
    hawaii    etc 
    japan    etc
    london   etc
    stone    etc
  

Каков наилучший способ представления этих данных?

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

итак, просто спрашиваю, является ли стандартным использование структуры типа ориентированный граф (для дерева) взвешенный неориентированный граф (для отношений)? Это стандартно или есть более стандартный способ?

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

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

Ваше условие определения не имеет смысла. Единственный способ, которым мы можем определить расстояние, — это добавить некоторую структурную информацию в дерево, чтобы мы знали, как расположить узлы. Это то, что «подклассы» делают в иерархических отношениях. Ссылки, по сути, являются просто «ребрами», поскольку любое дерево может быть преобразовано в граф.

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

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

Чтобы представить здесь расстояние между объектами, вы можете понять, что на самом деле вы определяете координатное пространство по набору переменных (x = цвет глаз, y = вес, z = рост, isFurry = q). Таким образом, каждый отдельный узел фактически является вектором в координатном пространстве, определяемом набором общих атрибутов. Следовательно, вы можете вычислить евклидово расстояние, расстояние Махаболиса, расстояние Манхэттена, косинусное подобие или любую другую метрику расстояния, которую вы хотите.

Я думаю, что то, что вы пытаетесь сделать, — это иерархическая кластеризация, и то, что у вас есть, называется матрицей расстояний.