Графовая наука данных для табличных данных

Графовые инструменты для анализа таблиц данных

Методы графов более общие, чем вы можете подумать

Фотография Алины Грубняк на Unsplash

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

Чтобы все было просто, в качестве примера я возьму набор данных Credit Approval. Цель состоит в том, чтобы предсказать значение Approval на основе значений одного или нескольких других атрибутов. Существует множество алгоритмов классификации, которые могут использоваться для этого, но давайте рассмотрим, как мы можем подойти к этому с использованием графов.

Набор данных Credit Approval, созданный автором

Представление в виде графа

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

Графическое представление набора данных Credit Approval. Изображение автора.

Передача сообщений

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

Процедура передачи сообщений

Инициировать сообщение со значением 1 на начальном узле и позволить этому узлу передавать сообщение каждому узлу, к которому он подключен. Пусть любой узел, который получает сообщение, затем передает сообщение (растянутое на коэффициент k, где 0 < k < 1) каждому другому узлу, к которому он подключен. Продолжать передачу сообщений до тех пор, пока либо не будет достигнут целевой узел (т.е. узел, соответствующий атрибуту, значение которого предсказывается), либо не останется узлов, к которым можно передать сообщение. Поскольку сообщение не может быть передано обратно на узел, с которого оно было получено, процесс гарантированно завершится.

Когда завершена передача сообщений, каждый узел в графе получит ноль или более сообщений различного значения. Суммируйте эти значения для каждого узла, принадлежащего к целевому атрибуту, а затем нормализуйте (суммируйте) эти значения, чтобы они сами суммировались до 1. Интерпретируйте нормализованные значения как вероятности. Эти вероятности затем могут быть использованы либо для прогнозирования неизвестного значения атрибута, либо для заполнения случайным значением, взятым из распределения. Растяжение значений сообщений на каждом шаге отражает идею, что более длинные пути должны оказывать меньшее влияние на оценку вероятности, чем более короткие пути.

Пример 1

Предположим, что мы хотим предсказать значение Approval при условии, что Income является Low. Стрелки на графике ниже иллюстрируют работу процедуры передачи сообщений, при этом толщина каждой стрелки представляет значение сообщения (растянутое на коэффициент k = 0,5 на каждом шаге).

Оценка распределения Одобрения при низком доходе. Изображение автора.

Сообщение инициируется в вершине Доход: Низкий (зеленого цвета). Эта вершина отправляет сообщения со значением 1 в Instance 1 и Instance 2, которые затем передают каждое сообщение (со значением 0,5) в вершины Образование: Колледж и Одобрение: Нет. Обратите внимание, что поскольку вершина Образование: Колледж получает сообщения как от Instance 1, так и от Instance 2, она должна передавать каждое из этих сообщений в Instance 3 со значением, уменьшенным до 0,25. Числа на каждой вершине целевой переменной показывают сумму значений сообщений, полученных и (в скобках) значения, нормализованные в процентах. У нас есть следующие вероятности для Одобрения при условии, что доход низкий:

  • Вероятность (Одобрение “Да” | Доход низкий) = 20%
  • Вероятность (Одобрение “Нет” | Доход низкий) = 80%

Эти вероятности отличаются от тех, которые мы получили бы при прогнозировании на основе подсчета из таблицы. Поскольку два из пяти экземпляров имеют низкий доход, и оба из них имеют Одобрение “Нет”, прогноз, основанный на подсчете, привел бы к вероятности 100% для Одобрение “Нет”.

Процедура передачи сообщений учитывает, что значение атрибута Образование Колледж, принадлежащее Instance 1 и Instance 2, также принадлежит Instance 3, который имеет Одобрение “Да”, внося таким образом свой вклад в общую сумму значений сообщений, полученных в вершине Одобрение: Да. Если бы мы включили дополнительные атрибуты Трудоустройство и История в наш граф, это, вероятно, привело бы к еще большему числу путей, соединяющих начальную вершину с целевыми вершинами, тем самым использовался бы дополнительный контекстуальный информация для улучшения оценки распределения вероятностей.

Пример 2

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

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

Экземпляр 4 имеет значение Образования “Высшее”, и поэтому дополнительно вносит свой вклад в сумму значений сообщений, полученных в вершине Одобрение: Да. Еще один вклад в Одобрение: Да вносит Экземпляр 5, который имеет высокий доход, как и Экземпляр 4.

[Примечание: В каждом из этих примеров мы использовали Одобрение в качестве целевой переменной; однако мы могли бы таким же образом оценить распределение вероятностей для Дохода или Образования].

Эти примеры демонстрируют, что простая идея передачи сообщений (фундаментальная операция на основе графа), совместно с соответствующим представлением графа, позволяет выполнять вывод обобщенного и гибкого характера. Конкретно, она может быть использована для оценки распределения вероятностей ЛЮБОГО атрибута при условии значений ОДНОГО или БОЛЕЕ атрибутов.

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

Из наших примеров мы можем сделать еще одно интересное наблюдение. В анализе выше мы не делали никаких ссылок на сумму значений сообщений, полученных на узлах экземпляров (т.е. на узлах, расположенных по левой стороне графов). Посмотрим, что эти значения могут нам показать. В Примере 1, по завершении передачи сообщений, сумма значений сообщений на узлах Экземпляров 1 до 5 составляет соответственно 1.0, 1.0, 0.5, 0.0 и 0.0. Нормализация этих значений, чтобы суммировались в единице, дает 40%, 40%, 20%, 0% и 0%. Первые два экземпляра имеют Одобрение “Нет”, и сумма их нормализованных значений составляет 80%. Последние три экземпляра имеют Одобрение “Да”, и сумма их нормализованных значений составляет 20%. Но это всего лишь вероятности, которые мы получили для атрибута Одобрение в исходном анализе. (Вы можете проверить то же самое для Примера 2). Это не случайность. Сумма значений сообщений на узле экземпляра может быть интерпретирована как мера сходства этого экземпляра с значениями атрибутов, на которые мы основываемся. Таким образом, процедуру вывода можно рассматривать как форму взвешенного ближайшего соседа, при которой мера сходства подразумевается в процедуре передачи сообщений.

Фреймворк UNCRi

В Skanalytix мы разработали графовый вычислительный фреймворк под названием Unified Numerical/Categorical Representation and Inference (UNCRi). Данный фреймворк объединяет уникальное графовое представление данных с гибкой процедурой вывода и может использоваться для оценки и сэмплирования условного распределения любой категориальной или числовой переменной. Он может применяться для задач таких, как классификация и регрессия, заполнение пропущенных значений, обнаружение аномалий и генерация синтетических данных из полного совместного распределения или некоторого условного распределения. Фреймворк устойчив к крайним значениям в данных: категориальные переменные могут быть двоичными или иметь высокую кардинальность; числовые переменные могут быть многомодальными, сильно скошенными и иметь произвольный масштаб; а отношение пропущенных значений может быть высоким. Более подробную информацию о UNCRi вы можете найти на сайте http://skanalytix.com. (Исходный код UNCRi закрыт).

Вывод

Дисциплины распознавания образов и машинного обучения с самого начала были охвачены методами, работающими с векторами. Векторы были настолько всеобщими, что иногда сложно было представить себе другой подход. Графовые методы предоставляют мощную и гибкую альтернативу. При применении к табличным данным графовые методы могут использоваться не только для предсказания значения атрибута или заполнения атрибута случайным значением из его оцененного распределения, но и — с использованием правила цепи вероятности — для генерации целых синтетических наборов данных экземпляров, распределенных таким же образом, как исходные данные. И все это с использованием одного графа и одной процедуры вывода! Хотя в этой статье мы рассмотрели только категориальные переменные, возможно расширить эти идеи на наборы данных, содержащие смесь числовых и категориальных атрибутов.