Ядра дерева: количественная оценка сходства данных с древовидной структурой

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

Сегодня огромное количество данных доступно в виде сетей или графиков. Например, всемирная паутина с ее веб-страницами и гиперссылками, социальные сети, семантические сети, биологические сети, сети цитирования научной литературы и так далее.

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

Неконтролируемая классификация структурированных данных

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

Неконтролируемая классификация может быть объединена с теорией графов для выявления групп похожих древовидных сетей. Древовидные структуры данных используются для моделирования объектов из нескольких доменов. Например, в обработке естественного языка (NLP) деревья синтаксического анализа моделируются как упорядоченные помеченные деревья. В автоматизированных рассуждениях многие проблемы решаются путем поиска, где пространство поиска представлено в виде дерева, вершины которого связаны с состояниями поиска, а ребра представляют шаги вывода. Кроме того, полуструктурированные данные, такие как документы HTML и XML, можно моделировать в виде упорядоченных помеченных деревьев.

Эти домены можно с пользой проанализировать с помощью неконтролируемых методов классификации. В НЛП классификацию можно использовать для автоматической группировки набора предложений в вопросы, команды и утверждения. Точно так же группы похожих веб-сайтов можно идентифицировать, применяя методы классификации к их HTML-источнику. В каждом из этих случаев все, что нам нужно, — это способ измерить, насколько «похожи» два дерева друг на друга.

Проклятие размерности

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

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

Чтобы понять причину такого ухудшения производительности, рассмотрим пространство X размерности d . Предположим, что X содержит множество точек, равномерно распределенных. Если количество измерений X увеличивается, количество точек, необходимых для сохранения той же плотности, должно увеличиваться экспоненциально. Другими словами, чем больше размерность входных данных, тем больше вероятность того, что эти данные разрежены. Как правило, разреженный набор данных не дает достаточно информации для создания хорошего классификатора, потому что корреляции между элементами данных слишком слабы для обнаружения алгоритмами.

Каждое пространство признаков выше содержит восемь точек данных. В одномерном пространстве легко выделить группу из пяти точек слева и трех справа. Растягивание этих точек на большее количество признаков (т. е. измерений) затрудняет поиск этих групп. В реальных приложениях пространства признаков могут легко иметь сотни измерений.

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

Методы ядра

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

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

Если мы рассмотрим конечный набор данных, состоящий из n примеров, мы можем получить полное представление о сходстве данных, создав матрицу ядра , размер которой всегда равен n × n . Эта матрица не зависит от размера каждого отдельного примера. Это свойство полезно, когда необходимо проанализировать небольшой набор данных примеров с большим пространством признаков.

В общем, методы ядра основаны на другом ответе на вопрос о представлении данных. Вместо того, чтобы отображать входные точки в пространство признаков, данные представляются посредством попарных сравнений в матрице ядра K , и весь соответствующий анализ может быть выполнен по матрице ядра.

Многие методы интеллектуального анализа данных могут быть реализованы в виде ядра. Чтобы классифицировать экземпляры данных с древовидной структурой с помощью методов ядра, таких как машины опорных векторов, достаточно определить допустимую (симметричную положительно определенную) функцию ядра k: T × T → R , также называемую ядром дерева . При разработке практически полезных ядер деревьев требуется, чтобы они были вычислимы за полиномиальное время по размеру дерева и могли обнаруживать изоморфные графы. Такие ядра дерева называются полными ядрами дерева.

Ядра деревьев

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

Ядро строки

Во-первых, мы начнем с краткого введения в строковые ядра, которое поможет нам представить еще один метод ядра, основанный на преобразовании деревьев в строки.

Определим num y (s) как количество вхождений подстроки y в строку s с | с | обозначающий длину строки. Строковое ядро, которое мы опишем здесь, определяется как:

K строка (S 1 , S 2 ) = Σ s∈F число s (S 1 )число s (S 2 )w s

Где F — набор подстрок, которые встречаются как в S 1 , так и в S 2 , а параметр w s служит параметром веса (например, для выделения важных подстрок). Как мы видим, это ядро ​​дает более высокое значение паре строк, когда они имеют много общих подстрок.

Ядро дерева на основе преобразования деревьев в строки

Мы можем использовать это строковое ядро ​​для построения ядра дерева. Идея этого ядра состоит в том, чтобы систематически преобразовать два дерева в две строки, которые кодируют структуру дерева, а затем применить к ним указанное выше строковое ядро.

Мы преобразуем два дерева в две строки следующим образом:

Пусть T обозначает одно из целевых деревьев и label( ns ) строковую метку узла ns в T. tag( ns ) обозначает строковое представление поддерева T с корнем в ns . Таким образом, если n root является корневым узлом T , tag(n root ) является строковым представлением всего дерева T .

Далее, пусть string(T) = tag(n root ) обозначает строковое представление T . Мы будем рекурсивно применять следующие шаги снизу вверх, чтобы получить string(T) :

• Если узел ns является листом, пусть tag( ns ) = «[» + label( ns ) + «]» (где + здесь — оператор конкатенации строк).
• Если узел ns не является листом и имеет c дочерних элементов n 1 , n 2 , …, n c , отсортируйте тег (n 1 ), тег (n 2 ), … , тег (n c ) в лексическом порядке, чтобы получить тег (n 1* ), tag(n 2* ), … , tag(n c* ) , и пусть tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + тег(n c* ) + «]» .

На рисунке ниже показан пример преобразования дерева в строку. Результатом является строка, начинающаяся с открывающего разделителя, такого как «[», и заканчивающаяся его закрывающим аналогом, «]», причем каждая вложенная пара разделителей соответствует поддереву с корнем в конкретном узле.

Теперь мы можем применить приведенное выше преобразование к двум деревьям, T 1 и T 2 , чтобы получить две строки S 1 и S 2 . Оттуда мы можем просто применить строковое ядро, описанное выше.

Ядро дерева между T 1 и T 2 через две строки S 1 и S 2 теперь может быть задано как:

K дерево (T 1 , T 2 ) = K строка ( строка (T 1 ), строка (T 2 )) = K строка (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )в с

В большинстве приложений весовой параметр принимает вид w | с | , взвешивание подстроки на основе ее длины | с | . Типичные методы взвешивания для w | с | являются:

• постоянное взвешивание ( w | s | = 1 )
• k - взвешивание спектра ( w | s | = 1 , если | s | = k , и w | s | = 0 в противном случае)
• экспоненциальное взвешивание ( w | s | = λ | s | где 0 ≤ λ ≤ 1 — скорость затухания)

Чтобы вычислить ядро, достаточно определить все общие подстроки F и подсчитать, сколько раз они встречаются в S 1 и S 2 . Этот дополнительный шаг поиска общих подстрок является хорошо изученной проблемой и может быть выполнен в O( | S 1 | + | S 2 | ) , используя деревья суффиксов или массивы суффиксов. Если мы предположим, что максимальное количество букв (например, битов, байтов или символов), необходимое для описания метки узла, является постоянным, длины преобразованных строк равны | С 1 | = O( | T 1 | ) и | С 2 | = О( | Т 2 | ) . Таким образом, вычислительная сложность вычисления функции ядра составляет O( | T 1 | + | T 2 | ) , что является линейным.

Ядро дерева на основе подпутей

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

В этом разделе будет определено ядро ​​дерева, которое работает с вертикальными структурами в деревьях, позволяя ядру работать с деревом напрямую.

Подсекция пути от корня до одного из листьев называется подпутью , а набор подпутей — это множество всех подпутей, входящих в дерево:

Предположим, что мы хотим определить ядро ​​дерева K(T 1 , T 2 ) между двумя деревьями T 1 и T 2 . Используя набор подпутей, мы можем определить это ядро ​​дерева как:

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | р |

Где num p (T) — количество раз, когда подпуть p встречается в дереве T , | р | — количество узлов в подпути p , а P — множество всех подпутей в T 1 и T 2 . ш | р | - вес, аналогичный введенному в предыдущем разделе.

Здесь мы представляем простую реализацию этого ядра с использованием поиска в глубину. Хотя этот алгоритм работает за квадратичное время, существуют более эффективные алгоритмы, использующие деревья суффиксов или массивы суффиксов, или расширение алгоритма быстрой сортировки с несколькими ключами, которое может достигать линейного времени ( O( | T 1 | log | T 2 | ) ) в среднем:

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

В этом примере мы использовали весовой параметр w | с | ш | р | = 1 . Это дает всем подпутям равный вес. Однако во многих случаях уместно использование взвешивания k -спектра или какого-либо динамически назначаемого значения веса.

Сайты майнинга

Прежде чем мы закончим, давайте кратко рассмотрим одно реальное применение древовидной классификации: категоризацию веб-сайтов. Во многих контекстах интеллектуального анализа данных полезно знать, с какого «типа» веб-сайта поступают некоторые данные. Оказывается, страницы с разных веб-сайтов можно довольно эффективно классифицировать с помощью деревьев из-за сходства в том, как устроены веб-страницы для аналогичных сервисов.

Как мы это делаем? HTML-документы имеют логическую вложенную структуру, очень похожую на дерево. Каждый документ содержит один корневой элемент, внутри которого вложены дополнительные элементы. Вложенные элементы в теге HTML логически эквивалентны дочерним узлам этого тега:

Давайте взглянем на некоторый код, который может преобразовать HTML-документ в дерево:

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

Это создаст древовидную структуру данных, которая может выглядеть примерно так:

В приведенной выше реализации используется несколько полезных библиотек Python: NetworkX для работы со сложными структурами графов и Beautiful Soup для извлечения данных из Интернета и управления документами.

Вызов html_to_dom_tree(soup.find("body")) вернет объект графика NetworkX с корнем в элементе <body> веб-страницы.

Допустим, мы хотим найти группы в наборе из 1000 домашних страниц веб-сайтов. Преобразовав каждую домашнюю страницу в такое дерево, мы можем сравнить каждую, например, используя ядро ​​дерева подпутей, приведенное в предыдущем разделе. С помощью этих измерений подобия мы могли бы обнаружить, что, например, сайты электронной коммерции, новостные сайты, блоги и образовательные сайты легко идентифицируются по их сходству друг с другом.

Заключение

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

Древовидные структуры встречаются во многих областях реального слова, таких как документы XML и HTML, химические соединения, обработка естественного языка или определенные типы поведения пользователей. Как показано на примере построения деревьев из HTML, эти методы позволяют нам выполнять осмысленный анализ в этих областях.