Предположим, нам даны данные в полуструктурированном формате в виде дерева. Например, дерево может быть сформировано как действительный документ XML или как действительный документ JSON. Вы можете вообразить, что это S-выражение типа lisp или (G) алгебраический тип данных в Haskell или Ocaml.
Нам дано большое количество «документов» в древовидной структуре. Наша цель - объединить похожие документы. Под кластеризацией мы подразумеваем способ разделения документов на j группы, чтобы элементы в каждой выглядели как один.
Я уверен, что есть документы, описывающие подходы, но, поскольку я не очень известен в области искусственного интеллекта / кластеризации / машинного обучения, я хочу спросить кого-то, что искать и где копать.
Мой нынешний подход выглядит примерно так:
- Я хочу преобразовать каждый документ в N-мерный вектор, настроенный для кластеризации K-средних.
- Для этого я рекурсивно обхожу дерево документов и для каждого уровня вычисляю вектор. Если я нахожусь в вершине дерева, я повторяюсь на всех подвершинах и затем суммирую их векторы. Кроме того, всякий раз, когда я повторяюсь, применяется коэффициент мощности, так что это имеет значение все меньше и меньше, чем дальше по дереву я иду. Конечный вектор документов - корень дерева.
- В зависимости от данных на листе дерева я применяю функцию, которая переносит данные в вектор.
Но, конечно, есть лучшие подходы. Одним из недостатков моего подхода является то, что это будут только деревья кластеров сходства, которые имеют верхнюю структуру, очень похожую друг на друга. Если сходство присутствует, но происходит дальше вниз по дереву, то мой подход, вероятно, не будет работать очень хорошо.
Я полагаю, что в полнотекстовом поиске также есть решения, но я хочу воспользоваться преимуществами полуструктуры, присутствующей в данных.
Функция расстояния
Как и предполагалось, необходимо определить функцию расстояния между документами. Без этой функции мы не можем применить алгоритм кластеризации.
На самом деле, возможно, речь идет об этой самой функции расстояния и ее примерах. Я хочу документы, где элементы рядом с корнем одинаковы для кластеризации близко друг к другу Чем дальше мы идем вниз по дереву, тем меньше это имеет значение.
Точка обзора на один шаг назад:
Я хочу кластеризовать трассировки стека от программ. Это правильно сформированные древовидные структуры, где функции, близкие к корню, являются внутренней функцией, которая не работает. Мне нужна приличная функция расстояния между трассировками стека, которая, вероятно, происходит, потому что то же самое событие произошло в коде.