Структурированные данные кластеризации дерева

Предположим, что нам даны данные в полуструктурированном формате в виде дерева. В качестве примера дерево может быть сформировано как допустимый XML-документ или как действительный документ JSON. Вы можете себе представить, что это lisp -подобное S-выражение или (G) -алгебраический тип данных в Haskell или Ocaml.

Нам дается большое количество "документов" в древовидной структуре. Наша цель - скопировать документы, которые похожи. К кластеризации мы подразумеваем способ разделить документы на j-группы, чтобы элементы в каждом виде выглядели друг с другом.

Я уверен, что есть документы, в которых описываются подходы, но поскольку я не очень известен в области AI/Clustering/MachineLearning, я хочу спросить кого-то, что искать и где копать.

Мой текущий подход выглядит примерно так:

  • Я хочу преобразовать каждый документ в N-мерный вектор, настроенный для кластеризации K-типа.
  • Чтобы сделать это, я рекурсивно прохожу дерево документа, и для каждого уровня я вычисляю вектор. Если я на вершине дерева, я возвращаюсь на все подвестры и затем суммирую их векторы. Кроме того, всякий раз, когда я повторяюсь, применяется коэффициент мощности, поэтому он все меньше и меньше влияет на дерево. Конечным вектором документов является корень дерева.
  • В зависимости от данных на дереве я применяю функцию, которая переносит данные в вектор.

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

Я полагаю, что есть решения в полнотекстовом поиске, но я хочу использовать полуструктуру, присутствующую в данных.

Функция расстояния

Как и было предложено, нужно определить функцию расстояния между документами. Без этой функции мы не можем применить алгоритм кластеризации.

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

Точка поиска с одним шагом назад:

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

Ответы

Ответ 1

Учитывая характер вашей проблемы (трассировку стека), я бы свести ее к проблеме, связанной с строкой. Представление трассировки стека как дерева - это немного накладных расходов: для каждого элемента в трассировке стека у вас есть ровно один родитель.

Если сопоставление строк действительно было бы более подходящим для вашей проблемы, вы можете пропустить ваши данные, нанести на карту каждый node на хэш и создать для каждого "документа" свои n-граммы.

Пример:

Mapping:

  • Исключение A → 0
  • Исключение B → 1
  • Исключение C → 2
  • Исключение D → 3

Док A: 0-1-2 Doc B: 1-2-3

2 грамма для документа A: X0, 01, 12, 2X

2 грамма для документа B: X1, 12, 23, 3X

Используя n-граммы, вы сможете группировать подобные последовательности событий независимо от корня node (в этом примере eventm event 12)

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

Вот несколько указателей:

Когда у вас есть частые поддеревья, вы можете использовать их так же, как вы использовали n-граммы для кластеризации.

Ответ 2

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

Из реферата:

This thesis presents Ixor, a system which collects, stores, and analyzes stack traces in distributed Java systems. When combined with third-party clustering software and adaptive cluster filtering, unusual executions can be identified.