Применение байесовых сетей в задачах анализа и прогнозирования спроса

Размещено на http://www.allbest.ru/

Применение байесовых сетей в задачах анализа и прогнозирования спроса

А.Г. Подвесовский, С.В. Ешин

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

Ключевые слова: прогнозирование спроса, байесовы сети, автоматизация рассуждений, вероятностный вывод.

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

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

На сегодняшний день существует множество методов прогнозирования, которые в своем большинстве могут быть отнесены к следующим классам [1; 2]: регрессионные модели, методы сглаживания временных рядов, методы декомпозиции временных рядов, методы, основанные на использовании систем одновременных уравнений и линейного программирования, а также класс экспертных методов прогнозирования. Сущность большинства количественных (эконометрических) методов заключается в подготовке исторических данных, выявлении в них закономерностей и продлении (экстраполяции) этих закономерностей в будущее (с допущением, что имеющиеся тенденции сохранятся). При этом данные методы не позволяют учесть в явном виде знания экспертов и многие субъективные факторы, прежде всего характеризующие сферу розничной торговли. Так, известно, что большое влияние на спрос оказывают факторы, действующие на покупателя непосредственно в магазине. Согласно статистике [3], примерно в 70% случаев они являются определяющими при выборе того или иного товара. К таким факторам обычно относятся [3; 4]: упаковка товара, наличие рекламных материалов, проведение акций (снижение цен, распродажи, подарки при покупке и др.), рекомендации продавца-консультанта, уровень и качество обслуживания, известность торговой марки. Для магазинов самообслуживания (супермаркеты, гипермаркеты, универсамы) важным параметром, влияющим на уровень продаж, является также выкладка товара [3]: глобальная позиция в торговом зале, расположение на основном либо дополнительном месте, вертикальная или горизонтальная выкладка на витрине. байесовая сеть потребительский запрос

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

Байесовы сети как модель вероятностных рассуждений. Байесовы сети (bayesian networks) - это графовые модели, отражающие вероятностные связи между событиями предметной области. Наибольшее развитие аппарат байесовых сетей (БС) получил в работах Дж. Пиэрла (Judea Pearl) [5; 6] в качестве альтернативного подхода к построению экспертных систем (ЭС). Как правило, аппарат БС применяется в следующей ситуации. Имеется набор событий, которые каким-либо образом связаны друг с другом. Эксперты высказывают суждения о вероятности этих событий. Задача байесовой сети состоит в объединении высказываний экспертов непротиворечивым образом и вычислении апостериорной вероятности (достоверности) гипотез с учетом поступающей в сеть информации о состоянии наблюдаемых переменных (свидетельств). Описанный процесс называется вероятностным выводом и несет тот же смысл, что и логический вывод в ЭС, основанных на продукционных правилах. Вероятностные модели имеют серьезное преимущество над другими адаптивными моделями, в частности регрессионными и нейросетевыми, являющимися моделями «черного ящика». БС дают понятное объяснение своих выводов, допускают логическую интерпретацию и модификацию структуры отношений между переменными, а также позволяют в явной форме учесть априорный опыт экспертов в соответствующей предметной области [7]. Байесовы сети широко используются в качестве экспертных моделей, средств обнаружения знаний и статистической обработки информации в таких областях, как медицина, эпидемиология, политика, биоинформатика, техническая диагностика, управление рисками, фильтрация нежелательной электронной почты и др. [8-10].

Введем основные определения, относящиеся к теории байесовых сетей [8].

Определение 1 (марковские родители). Пусть V = {X1, …, Xn} -- упорядоченное множество случайных переменных, P(v) - полное совместное вероятностное распределение над этими переменными. Множество переменных PAj называется марковскими родителями (markovian parents) переменной Xj, если PAj является минимальным множеством предшественников переменной Xj, которое делает переменную Xj независимой от всех других предшественников, т.е. PAj - это любое подмножество множества {X1, …, Xj-1}, удовлетворяющее равенству

P(xj | paj) = P(xj | x1, …, xj-1), (1)

где xj и paj - некоторые значения (реализации) Xj и PAj соответственно, при этом равенству (1) не удовлетворяет никакое подмножество множества PAj.

Теорема 1 (цепное правило). Любое полное совместное распределение P(v) = P(x1, …, xn), определенное над множеством V = {X1, …, Xn} произвольно упорядоченных дискретных случайных переменных, может быть представлено в виде произведения n условных распределений:

Теорема 2 (факторизация распределения). Любое полное совместное распределение P(v) = P(x1, …, xn), определенное над множеством V = {X1, …, Xn} произвольно упорядоченных дискретных случайных переменных, удовлетворяющее равенству (1), на основе цепного правила может быть представлено в виде произведения:

. (2)

Определение 2 (байесова сеть). Пусть G - ориентированный граф без направленных циклов, множеству вершин которого однозначно соответствует множество случайных переменных V = {X1, …, Xn}, а P(v) - полное совместное распределение над переменными V. Граф G называется байесовой сетью для распределения P(v) (иначе говорят, что граф G и распределение P(v) марковски-совместимы, или P(v) является марковским распределением по отношению к G), если P(v) допускает факторизацию относительно G в виде

где PAGi -- множество случайных переменных, соответствующее множеству вершин-родителей для вершины Xi в графе G, а paGi -- частная конфигурация PAGi. Иными словами, G является байесовой сетью для P(v), если для любой вершины Xi в графе G множество PAGi является марковскими родителями для случайной переменной Xi.

Байесова сеть представляет собой графический способ хранения информации об отношениях вероятностной зависимости/независимости между случайными переменными. Дуга, ведущая из вершины A в вершину B, означает, что между этими переменными имеется вероятностная зависимость, в то время как отношения условной/безусловной независимости задаются структурой сети неявно, и для определения того, что переменные в сети независимы, необходимо воспользоваться более сложным критерием, получившим название d-разделимости (d-separation criterion) [6]. Наиболее распространенной интерпретацией дуг в БС является понимание дуги как причинно-следственной связи между двумя переменными. В соответствии с данным принципом наличие дуги из A в B означает, что A является причиной B, однако подобная интерпретация структуры сети не всегда является верной. Для отношения условной зависимости направление дуги не имеет значения: фрагменты байесовых сетей A > B и A < B кодируют одно и то же отношение вероятностной зависимости между переменными A и B, но в то же время определяют разные отношения причинности между этими переменными. Разновидность БС, в которой дуги определяют отношения причинности между переменными, называется причинной байесовой сетью (causal bayesian network) [8]. Причинные БС помимо решения задач вероятностного вывода, т.е. получения ответов на вероятностные запросы (evidential queries), могут отвечать на более сложные типы запросов: запросы-вмешательства (interventional queries) и запросы c противоречием фактам (counterfactual queries) [8]. В настоящей статье рассматриваются только вероятностные запросы к БС.

Для БС характерно использование субъективного (байесовского) подхода к трактовке понятия «вероятность». Согласно байесовскому подходу [6; 8], под вероятностью понимается степень доверия (degree of belief) гипотезам, связанным с событиями реального мира, при этом информация о мире используется для подтверждения либо опровержения имеющихся степеней доверия. Степени доверия назначаются логическим выражениям, представленным в виде высказываний на некотором языке, и обрабатываются согласно правилам теории вероятностей. Обычно степень доверия к пропозиции А, полученную на основе совокупности знаний K субъекта, обозначают P(A | K). При проведении расчетов символ K опускают и записывают P(A). Поскольку, согласно байесовскому подходу, измерение и комбинирование степеней доверия подчиняется основным аксиомам вероятностного исчисления [8], то при расчетах имеется возможность совместного использования степеней доверия и вероятностей в классической (частотной) трактовке, что является важным преимуществом БС. В частности, это позволяет учесть как знания экспертов, так и вероятностные распределения, которые могут быть получены на основе статистических данных либо иных сведений о моделируемой системе.

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

, (3)

где H - гипотеза, e - свидетельство. Согласно теореме Байеса, степень доверия, которую мы можем присвоить гипотезе H при наступлении свидетельства e, может быть рассчитана путем умножения предыдущей степени доверия P(H) к гипотезе H на правдоподобие P(e | H), означающее наступление свидетельства e при условии, что гипотеза H истинна. Вероятность P(H | e) называется апостериорной вероятностью, а P(H) - априорной вероятностью. Знаменатель P(e) в выражении (3) используется для нормализации вероятностей P(H | e) и P(H | e) на единичную сумму.

Изначально байесовы сети были разработаны для решения задач диагностики и прогнозирования в системах искусственного интеллекта [6]. В подобных задачах требовалось найти логически верное объяснение поступающих наблюдений, которое было бы согласовано как с наблюдениями, так и с имеющейся априорной информацией. Математически данная задача сводится к вычислению вероятности P(y | x), где X - множество переменных-наблюдений, Y - множество переменных, вероятностные распределения которых считаются важными при прогнозировании или диагностике, x (свидетельство) и y (гипотеза) - интересующие исследователя конфигурации множеств X и Y. Имея полное совместное распределение P(v) над множеством случайных переменных V вероятностной модели, вычисляем P(y | x) путем маргинализации распределения P(v), т.е. суммирования вероятностей атомарных событий, с применением правила (3):

, (4)

где - множество переменных модели за исключением X и Y, а x, y, s - частные конфигурации X, Y, S.

Вероятностный вывод с помощью выражения (4) обычно называют выводом на основе грубой силы, поскольку маргинализация такого распределения, которое велико даже для множества переменных небольшого размера, крайне неэффективна с вычислительной точки зрения. Применение БС позволяет повысить эффективность вычисления выражения (4), так как любая байесова сеть определяет факторизованное полное совместное распределение P(v), представляющее собой произведение локальных (условных) распределений (2), называемых также таблицами условных вероятностей (ТУВ). Идея, связанная с тем, чтобы использовать для проведения вывода графическую структуру сети, была положена в основу множества алгоритмов точного вероятностного вывода, вычислительная эффективность которых намного выше по сравнению с маргинализацией как полного совместного распределения (4), так и факторизованного распределения (2). Примерами таких алгоритмов являются алгоритмы устранения переменных и символьные вычисления, кластеризация, передача сообщений между узлами сети и др. Тем не менее в общем случае задача точного вероятностного вывода в БС является NP-сложной [11], поэтому получили распространение и алгоритмы приближенного вероятностного вывода, большинство из которых основаны на методах Монте-Карло (алгоритмы формирования выборок с исключением, метод оценки выборок с учетом правдоподобия, алгоритм МСМС и др.).

Основные задачи, решаемые с помощью байесовых сетей. Байесовы сети обычно используются для получения ответов на следующие виды вероятностных запросов [9]: нахождение вероятности свидетельства, определение априорных и апостериорных маргинальных вероятностей, вычисление наиболее вероятного объяснения наблюдаемого события, вычисление апостериорного максимума, поиск причин наблюдаемых событий. Рассмотрим перечисленные запросы более подробно.

Под свидетельством в БС понимается множество наступивших событий. Фактически это некоторая наблюдаемая конфигурация e множества переменных свидетельства E. Нахождение вероятности свидетельства (probability of evidence) Pev(e) заключается в маргинализации полного совместного распределения и не требует применения правила Байеса. Формула имеет вид

,

где S = V \ E -- множество переменных сети за исключением переменных свидетельства, V - множество переменных сети, - множество переменных свидетельства, e и s - конфигурации E и S. Примером такого запроса применительно к задаче прогнозирования спроса может быть определение вероятности события «товар куплен И качество товара - низкое И цена товара - высокая».

Определение априорных маргинальных вероятностей (prior-marginal query) заключается в нахождении вероятности наступления события P(Xi = xi) ? P(xi), где Xi -- одна из переменных сети, xi -- одно из значений этой переменной. Другое название этого процесса - априорный вывод либо вывод без свидетельства. Вычисление априорной маргинальной вероятности заключается в маргинализации полного совместного распределения P(v) и также не требует применения правила Байеса. Соответствующая формула имеет вид

,

где S = V \ Xi. Примером может быть запрос следующего вида: «Какова вероятность того, что товар купят?».

Определение апостериорных маргинальных вероятностей (posterior-marginal query) заключается в нахождении вероятности наступления события P(xi | e), где e - наблюдаемое свидетельство. Этот процесс также называют апостериорным выводом либо выводом со свидетельством. Вычисление апостериорной маргинальной вероятности заключается в маргинализации полного совместного распределения и требует применения правила Байеса:

,

где , E - множество переменных свидетельства.

Частными случаями определения апостериорных маргинальных вероятностей являются следующие типы запросов:

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

Диагностирование, или обратный вывод (абдукция), - определение вероятности причины при наблюдаемых следствиях. В этом случае множество переменных свидетельства E является подмножеством вершин-последователей Xi. Пример такого запроса: «Какова вероятность того, что цена товара высокая, если товар куплен?».

Межпричинный (смешанный) вывод (intercausal inference) или трансдукция, - определение вероятности одной из причин наступившего события при условии наступления одной или нескольких других причин этого события. Для данного типа вывода характерен феномен, получивший в искусственном интеллекте название попутного объяснения (explaining away), а в статистике - парадокса Берксона. Попутное объяснение заключается в опровержении старой гипотезы под воздействием поступившей в сеть новой информации. Это еще одно преимущество БС, поскольку механизм попутного объяснения характерен для мышления человека и не может быть реализован в системах, основанных на продукционных правилах.

Нахождение вероятности свидетельства и определение маргинальных вероятностей являются частными случаями вероятностного вывода в БС. Теперь рассмотрим более сложные классы запросов к БС, одним из которых является вычисление наиболее вероятного объяснения (most probable explanation, MPE) при заданном свидетельстве e. Решение этой задачи заключается в нахождении наиболее вероятной конфигурации всех переменных в сети при условии наблюдения свидетельства. Формально расчет MPE заключается в максимизации вероятности:

,

где X = V \ E, x -- возможная конфигурация X.

Вычисление апостериорного максимума (maximum a-posteriori probability, MAP) при заданном свидетельстве e заключается в нахождении наиболее вероятной конфигурации некоторого целевого подмножества переменных Z в сети при условии наблюдения свидетельства e. Расчет MAP является более общим случаем по сравнению с вычислением MPE и заключается в максимизации вероятности:

, (5)

где . Пример запроса с вычислением MPE/MAP: «К каким наиболее вероятным последствиям приведет высокая цена товара и его низкое качество?».

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

, (6)

где . Пример такого запроса: «Какие причины приведут к наиболее вероятному отказу от покупки товара?».

Построение байесовой сети для вероятностного моделирования спроса. Для построения БС, описывающей некоторую проблемную область, необходимо выполнить следующие действия [7]:

сформулировать проблему в терминах вероятностей значений целевых переменных;

выбрать понятийное пространство задачи, определить переменные, имеющие отношение к целевым переменным, описать возможные значения этих переменных;

выбрать на основе опыта и имеющейся информации априорные вероятности значений переменных;

описать причинно-следственные отношения между переменными (прямые и косвенные) в виде ориентированных ребер графа;

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

С учетом перечисленных этапов и указанных ранее факторов, влияющих на спрос, была построена вероятностная модель анализа и прогнозирования спроса на потребительские товары, в основе которой лежит байесова сеть (рис. 1). Разработанная модель позволяет частично избавиться от недостатков классических методов прогнозирования и дает возможность совместно учитывать объективную информацию (например, информацию о прошлых продажах) и субъективную информацию, т.е. знания и предположения экспертов. Специфическим свойством предложенной модели является результат прогнозирования, представленный в виде вероятностного распределения целевой случайной переменной «Покупка товара». В табл.1 приведена спецификация случайных переменных и принимаемых ими значений. На рис.2 показан фрагмент таблиц условных вероятностей.

Рис.1. Граф байесовой сети для вероятностной модели анализа и прогнозирования спроса

Рис.2. Фрагмент таблиц условных вероятностей

Примеры вывода с использованием разработанной модели. В табл.2 приведены примеры вероятностного прогнозирования спроса на основе разработанной модели с различными свидетельствами (e1-e6). e1=Ш - пример априорного вывода без свидетельства. e2-e4 - пример попутного объяснения в сети: e2={Покупка товара = ЛОЖЬ} - товар не покупается, e3={Покупка товара = ЛОЖЬ; Цена = Заниженная} - товар не покупается и цена товара низкая, e4 = {Покупка товара = ЛОЖЬ; Цена = Заниженная; Срок годности = В порядке} - товар не покупается, цена низкая и срок годности в порядке. В данном случае опровергается гипотеза «Состав = Подходит»: вероятность гипотезы изменилась с P=0,7 (априорный вывод) до P=0,26 (при свидетельстве e4). Вывод со свидетельством e5 = {Цена = Заниженная, Реклама = ЛОЖЬ, Известность торговой марки = Неизвестная, Факторы = Торговая марка} демонстрирует то, что покупатель не купит товар при условии низкой цены, если ему важен другой фактор (в данном случае этим фактором является торговая марка), P{Покупка товара = ЛОЖЬ | e5}=0,888 (табл.2).

Таблица 1

Фрагмент множества случайных переменных модели анализа и прогнозирования спроса

Теперь приведем пример расчета апостериорного максимума. Пусть Z={Срок годности, Состав, Цена, Известность торговой марки} - множество поиска, e ={Покупка товара = ИСТИНА} (товар покупается). Тогда, используя процедуру максимизации (5), получим MAP={Срок годности = В порядке, Состав = Подходит, Цена = Заниженная, Известность торговой марки = Известная}. Таким образом, наиболее вероятной конфигурацией Z при условии наступления свидетельства e (товар покупается) служит полученная конфигурация MAP переменных множества Z, что соответствует действительности. Определим причины свидетельства e = {Покупка товара = ЛОЖЬ} (товар не покупается) с таким же набором переменных поиска Z. В результате, используя процедуру (6), получим = e6 = {Срок годности = Вышел, Состав = Не подходит, Цена = Завышенная, Известность торговой марки = Неизвестная}, что также соответствует действительности. При такой конфигурации вероятность свидетельства максимальна: P{Покупка товара = ЛОЖЬ | e6}=0,863 (табл.2).

Таблица 2

Результаты вероятностного вывода

Автоматизированная система анализа и прогнозирования спроса. Все расчеты проводились с помощью разработанной авторами автоматизированной системы [12]. Система имеет следующие функциональные характеристики: поддержка аппарата байесовых сетей для вероятностного моделирования спроса, наличие готовых шаблонов сетей, использование сервера баз данных для хранения моделей, возможность извлечения информации из клиентской базы данных, предоставление аналитических отчетов для поддержки принятия решений. С целью обеспечения многопользовательского доступа к экспертным моделям информационная система построена на основе клиент-серверной архитектуры (рис.3). Байесова сеть для моделирования продаж создается аналитиком на основе информации о предметной области и знаний экспертов. Вершины сети соответствуют различным факторам, влияющим на спрос: уровень рекламы товара, упаковка, цена, расположение в торговом зале и др. Необходимые вероятностные распределения получаются в результате запросов к базе данных торгового предприятия или же, при недостатке информации, задаются экспертным путем. Выводы, полученные в результате моделирования, могут служить основой для формирования стратегий повышения уровня продаж (изменение цен и размеров заказов, совершенствование выкладки товаров и др.). Система разработана на основе технологии Microsoft .Net с использованием среды разработки Microsoft Visual Studio 2008 и языка программирования C#. Для хранения байесовых сетей используется сервер баз данных MS SQL Server 2000.

Рис.3. Общая архитектура программной системы анализа и прогнозирования спроса

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

СПИСОК ЛИТЕРАТУРЫ

1. Писарева, О.М. Методы прогнозирования развития социально-экономических систем: учеб. пособие / О.М. Писарева. - М.: Высш. шк., 2007. - 591 с.

2. Официальный сайт компании BaseGroup [Электронный ресурс] / BaseGroup. - Режим доступа: http://www.basegroup.ru.

3. Рамазнов, И. Мерчендайзинг в розничном торговом бизнесе / И. Рамазнов.- М.: Деловая литература, 2002. - 375 с.

4. Armstrong, J. Forecasting for Marketing. Quantitative Methods in Marketing / J. Scott Armstrong, Rod Brodie; G. J. Hooley and M. K. Hussey. eds. - London: International Thompson Business Press, 1999. - P. 92-119.

5. Pearl, J. Fusion, Propagation and Structuring in Belief Networks / J. Pearl // UCLA Computer Science Department Technical Report 850022 (R-42); Artificial Intelligence. - 1986. - Vol. 29. - №3. - P. 241-288.

6. Pearl, J. Probabilistic Reasoning in Intelligent Systems / J. Pearl. - San Francisco: Morgan Kaufmann, 1988. - 520 р.

7. Терехов, С. Введение в байесовы сети / С. Терехов // Лекции по нейроинформатике. - М.: МИФИ, 2003. - Ч.1. - С. 149-187.

8. Pearl, J. Causality: Models, Reasoning and Inference / J. Pearl. - Cambridge University Press, 2009. -- 464 p.

9. Darwiche, A. Modeling and Reasoning with Bayesian Networks / A. Darwiche. - Cambridge University Press, 2009. - 526 p.

10. Рассел, С. Искусственный интеллект: современный подход (AIMA): [пер. с англ.] / С. Рассел, П. Норвиг. - 2-е изд. - М.: Вильямс, 2005. - 1424 с.

11. Cooper, G.F. Computational Complexity of Probabilistic Inference using Bayesian Belief Networks / G.F. Cooper // Artificial Intelligence. - 1990. - №42. - P. 393-405.

12. Ешин, С.В. Автоматизация прогнозирования спроса на потребительские товары на основе применения байесовых сетей доверия / С.В. Ешин //Информационные системы и технологии 2009: тез. докл. II Науч. -техн. конф. студентов, аспирантов и молодых специалистов. - Обнинск, 2009. - С. 101-103.

Размещено на Allbest.ru