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