Моделирование принятия решения на основе анализа многомерных данных

Развитие технологий хранения и обработки данных все чаще находит свое отражение при решении задач поддержки принятия решений ^[1],[2]. Речь идет о таких системах, как Business Intelligence, OLAP и т. п. Использование в этих системах методов многомерной статистики накладывает ограничения на использование принципов, отражающих наше понимание связи явлений, получивших свое применение при анализе доминирующих мотиваций ^[3]. Формально эти принципы можно сформулировать следующим образом учет в ответе влияния фактора на ответ, что отражает уже существующую информацию о системе; факторы имеют разные веса в зависимости от того, в паре с чем они появляются. Выход видится в применении подходов анализа многомерных данных, главным отличием которого от многомерной статистики ^[4] является акцентирование внимание на содержательной части данных, а не на статистических погрешностях ^{[5, 6]}.

Еще ода проблема заключается в том, что разделы, использующие принципы анализа многомерных данных, зачастую используют свой уникальный аппарат для решения целого ряда задач из самых разных областей ^[7]–^[10]. Но в своей предметной области аппарат производственных функций (ПФ), активно применяемый в экономическом анализе, вводит величины, характеризующие взаимосвязь факторов и влияние фактора на ответ (эластичность замещения, эластичность выпуска, предельный продукт). В предлагаемом исследовании произведена попытка разрешить задачи анализа многомерных данных при принятии решения с использованием аппарата ПФ. Т. к. обозначенные принципы носят весьма общий характер, то видится возможность применения предлагаемого аппарата при решении любых задач, связанных с распознаванием образов.

Будем считать, что исследуемое решение/свойство зависит от известного набора переменных. Математически сформулируем это следующим образом ^{[4, с. 12]}: искомые решения (y-переменные) есть функция от наблюдаемых переменных (x-переменные), т. е. y = y(x), x_i ∈ X, y_i ∈ Y, i = 1,…, n, j = 1,…, m. X – множество всех x, Y – множество всех y. В результате серии наблюдений, каждой y-переменной ставится в соответствие вектор x-переменных. Пару (y, x) будем называть прецедентом ^{[11, с. 4]}.

В качестве x предлагается брать не непосредственное значение x_i-переменной, а количество ее появлений. Но данные, использованные в таком виде, не отражают тех принципов, которые обозначены выше. Для этого необходимо организовать x в виде особой структуры данных. Затем необходимо сформулировать правило, по которому каждому вновь выпавшему вектору x будет поставлена в соответствие y-переменная. Т. е. необходимо решить задачу построения классификатора (регрессии и предсказания). В качестве решающего правило далее используется обобщение ПФ, которое назовем функцией уверенности, имея в виду, что получаемое значение есть уверенность в выборе соответствующей y-переменной.

Пусть дано некоторое множество x-переменных X и множество y-переменных Y, на котором определено отношение предпочтения ≿. Тогда вещественная функция f: Y → ℝ называется функцией уверенности, если выполняется условие

`y_1>-=y_2 hArr f text((()y_1,bb"x" text()))>=ftext((()y_2,bb"x" text())), AAbb"x" in X, y_1,y_2 in Y.` (1)

x-переменные являются сочетаниями элементов x_k множества X из m по k, где m – количество элементов множества X, k = 1,…,m.

В частном случае, когда множество X совпадает с множеством Y и при этом k = 1, это определение ни чем не отличается от такового для функции полезности (производственной функции). Обозначим f((y,x)) = f(x), т. к. y-переменные однозначно определяются вектором x-переменных.

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

Предельный продукт есть мгновенная скорость изменения уверенности от частоты появления x_i-переменной. Ее вид:

`Mf_i(bb"x")=(Deltaf(bb"x"))/(Deltax_i)` (2)

Эластичность уверенности (выпуска) по отношению к количеству появлений x_i-переменной:

`varepsilon_i(bb"x")=(Mf_i(bb"x"))/(f(bb"x")/(x_i))` (3)

Если (2) есть мгновенная скорость, тогда знаменатель в (3) – средняя скорость изменения уверенности. Получается, что отношение (3) есть характеристика того, как изменяется уверенность: если ε(x) > 1, тогда мгновенная скорость больше средней до рассматриваемого момента, т. е. величина f(x) ускоряется (в среднем за весь период, т. к. в предшествующем опыте ситуация могла быть и другой); а если 0 < ε(x) < 1, тогда величина f(x) замедляется так же в среднем за весь период.

Пусть имеется некоторая система, опыт которой необходимо использовать для принятия последующих решений. Первое, что предстоит сделать – сформировать статистику в виде базы данных, а затем структурировать ее так, чтобы иметь возможность использовать предложенный аппарат. Для учета динамики системы, т. е. эластичности уверенности (скорости изменения уверенности в зависимости от опыта, в частности), потребуется в процессе конвертации данных из исходной базы в структурированную рассчитать параметр ε_i(x) по формуле (3). Начинать эту процедуру с самого начала может оказаться нецелесообразным, ведь первые расчеты «перекроются» последующими. К тому же если есть заданный аналитический вид функции уверенности, то и скорость функции f(x) должна однозначно определяться. Но коэффициенты, входящие в f(x) определяются по полученным данным, т. е. они будут изменяться с каждым следующим прецедентом. Чтобы первичные данные не пропал зря, рассчитанные по ним значения необходимо учесть, например, рассчитывая среднее между эластичностями на предыдущем шаге и на текущем.

Информация, которую необходимо обрабатывать – количество появлений x-переменных при каком-то выборе y-переменной (прецедент). Т. е. на входе необходим массив, состоящий из множества строк и несколькими столбцами, в которые будут записаны значения x-переменных и соответствующая им y-переменная. В первый столбец будут записываться y-переменные. Тогда, если в базе k столбцов, то за m = k – 1 обозначим количество x-переменных, c – количество строк в базе – количество прецедентов. Но массив, характеризующий данные о множестве значений, которые принимают x-переменные, не состоит из c строк, т. к. среди них много повторяющихся. Даже больше: большинство из них будут повторяющимися, а само множество значений не должно превышать нескольких десятков. Если составим массив p⁽¹⁾ с элементами `p_i^((1))` (i = 1,…,m), тогда его i-ый элемент будет говорить о количестве принимаемых значений каждой x-переменной. В дальнейшем верхний индекс у переменной, взятый в круглые скобки, будет говорить о мерности массива. Под суммой всех элементов `p_i^((1))` будет пониматься количество всевозможных значений, принимаемых x-переменными:

`P=sum_(i=1)^mp_i^((1)).`

Множество y-переменных запишем в массив d⁽¹⁾ с элементами `d_i^((1))` (i = 1,…,n). Здесь n – количество y-переменных.

Далее предлагается структура данных, в которую конвертируется исходная база. Для ее хранения необходимо два массива данных. Первый есть двумерный массив x⁽²⁾ с элементами `x_(i,j)^((2))` (i = 1,…,n, j = 1,…,P). Это информация о том, сколько раз встречалась x_j-переменная при выборе y_i-переменной. Но интересна не столько информация о количестве появлений, сколько о том, какие были условия для возникновения каждой x-переменной. И для такой информации двух осей мало. Поэтому, помимо массива x⁽²⁾ введем массив x⁽³⁾ с элементами `x_(i,j,k)^((3))` (i = 1,…,n, j = 1,…,P, k = 1,…,P), который говорит о том, сколько раз появлялась x_k-переменная вместе с x_j-переменной в ситуации, когда выбиралась y_i-переменная. Главным является x_j-переменная, т. к. в первую очередь важно, кто появляется вместе с ней. К примеру, пусть случилась ситуация, в которой была выбрана пятая y-переменная, чему способствовало появление трех x-переменных, первая из которых приняла третье значение из множества принимаемых ей значений, вторая – девятнадцатое, а третья – двадцать четвертое. В такой ситуации, если принять, что n = 10, m = 3, `p_i^((1))=const=10`, т. е. диапазон одинаков для каждой x-переменной, получим, что наибольшее После описанной ситуации инкрементированию подлежат: из массива x⁽²⁾ – `x_(5,3)^((2)),text( )x_(5,19)^((2)),text( )x_(5,24)^((2))`; из массива x⁽³⁾ – `x_(5,3,19)^((3)),text( )x_(5,3,24)^((3)),text( )x_(5,19,3)^((3)),text( )x_(5,19,24)^((3)),text( )x_(5,25,3)^((3)),text( )x_(5,24,19)^((3))` .

В элемент с индексом i,j,k не будет записана информация о факторе j. Это следствие того, что массив x⁽³⁾ хранит информацию только о k-ых элементах, которые выпали вместе с фактором j. Для хранения информации непосредственно о появлении фактора j служит массив x⁽²⁾. Но т. к. в x⁽³⁾ инкрементируются все сочетания факторов, то в конечном итоге появление всех факторов учтется. Псевдокод для формирования многомерной структуры данных выглядит следующим образом:

01 выбрать решение dec

02 for всех j-ых x-переменных

03 —инкрементировать `x_(dec,j)^((2))`

04 —for всех k-ых x-переменных

05 ——if j-ая x-переменная ≠ k-ой x-переменной

06 ———then инкрементировать `x_(dec,j,k)^((3))`

//Расчет функции f(x) для текущего состояния

07 for всех j-ых x-переменных

08 —`f_(dec,j)^((2))=0`

09 —for всех k-ых x-переменных

10 ——`f_(dec,j)^((2))+=x_(dec,j,k)^((3))xx(x_(dec,j,k)^((3)))/(x_(dec,j)^((2)))`

//Расчет функции f(x) для следующего состояния

11 for всех j-ых x-переменных

12 —for всех k2-ых x-переменных

13 ——`f2_(dec,j)^((2))=0`

14 ——for всех k-ых x-переменных

15 ———if k-ая x-переменная ≠ k2-ой x-переменной

16 ————`f2_(dec,j)^2+=(x_(dec,j,k)^((3))+1)xx(x_(dec,j,k)^((3))+1)/(x_(dec,j)^((2)))`

17 ———else

18 ————`f2_(dec,j)^((2))+=x_(dec,j,k)^((3))xx(x_(dec,j,k)^((3)))/(x_(dec,j)^((2)))`

19 ——if `varepsilon_(dec,j,k2)^((3))!=0`

20 ———`varepsilon_(dec,j,k2)^((3))=[(f2_(dec,j)^((2))-f_(dec,j)^((2)))xx(x_(dec,j,k2)^((3))^((3))+1)text(/)f2_(dec,j)^((2))+varepsilon_(dec,j,k2)^((3))]text(/)2`

21 ——else

22 ———`varepsilon_(dec,j,k2)^((3))=(f2_(dec,j)^((2))-f_(dec,j)^((2)))xx(x_(dec,j,k2)^((3))^((3))+1)text(/)f2_(dec,j)^((2))`

Алгоритм 1. Формирование данных и расчет эластичности

Сформировав данные можно приступить к обработке новых. Если прецеденты представляли собой пары (y, x), то новая ситуация характеризуется только набором x-переменных. В соответствии с этим набором необходимо выяснить, в какой из y-переменных мы можем быть более уверены. Для этого для каждой из них необходимо произвести расчет функции уверенности.

Вся функция уверенности будет являться суммой своих слагаемых, каждое из которых есть функция уверенности для отдельной x-переменной. Если ситуация состоит из m x-переменных, тогда функция уверенности состоит из m слагаемых, каждое из которых в свою очередь состоит из m – 1 слагаемого (для функции Кобба-Дугласа это будут множители).

В результате этих действий формируется одномерный массив f(x), состоящий из элементов f_i(x) (i = 1,…,n). Те y-переменные, в которых уверенность больше, имеют бóльшие значения функции f(x). Не составляет труда упорядочить y-переменные в порядке уверенности в них. Первые из получившихся можно использовать для принятия решения. Псевдокод расчета функции уверенности приведен ниже.

01 for всех i-ых y-переменных

02 —for всех j-ых x-переменных

03 ——инкрементировать `x_(i,j)^((2))`

04 ——for всех k-ых x-переменных

05 ———if j-ая x-переменная ≠ k-ой x-переменной

06 ————then инкрементировать `x_(i,j,k)^((3))`

07 —`f_i^((1))=0,text( )varepsilon_i^((1))=0`

08 —for всех j-ых x-переменных

09 ——for всех k-ых x-переменных

10 ———`f_i^((1))+=x_(i,j,k)^((3))xxx_(i,j,k)^((3))/x_(i,j,k)^((3))/x_(i,j)^((2))`

11 ———`varepsilon_i^((1))+=varepsilon_(i,j,k)^((3))`

12 ——`f_i^((1))=(f_i^((1)))^(varepsilon_i^((1)))`

Алгоритм 2. Расчет функции уверенности

В приведенном алгоритме в качестве функции уверенности выступает функция Солоу.

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

`f(x)=sum_(i=1)^ma_ix_i,text( )f(x)=b_0prod_(i=1)^mx_i^(b_i),text( )f(x)=A(sum_(i=1)^ma_ix_i^(beta_i))^h` (4)

Известно, что коэффициент замещения β_i связан с эластичностью замещения. Его численное значение получают из экономического анализа задачи. В нашем численном анализе исследованы два случая: β_i = 1 и β_i = 2.

За основу алгоритма расчета функции уверенности была взята работа ^[7], в которой авторами предлагалось в начале расчета использовать более «простые» функции.

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

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

Один расчет представляет собой следующую последовательность действий:

1. Генерация заданного количества случайных чисел и выбор среди них максимального.

Будем считать операцию 1 прецедентом.

2. Проведение заданного количества опытов.

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

4. Повторение операции 3 заданное количество раз (в программе имеется возможность изменять это число, но нет смысла для предлагаемого эксперимента выставлять разные числа).

5. Повтор операций 1–4 для одинакового количества прецедентов.

6. Расчет среднего арифметического из числа правильных ответов.

Результатом всех этих действий будет одно число – количество правильных ответов для следующих заданных показателей: количество прецедентов, количество x-переменных (количество случайных чисел), количество y-переменных (если диапазон изменения случайных чисел не совпадает с диапазоном y-переменных, то последнее надо нормировать первым), количество значений, которые могут принимать x-переменные.

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

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

На (рис. 1)–(рис. 3) представлены расчеты зависимости количества правильных ответов s от количества прецедентов k и от количества x-переменных m, количества y-переменных n, количества принимаемых значений каждой x-переменной p. Базовым будем считать следующий набор значений: n = 10, m = 10, p = 20. Т. е. при варьировании одного из указанных значений, величина оставшихся двух фиксируется одним из указанных.

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

а			б
в		г

Рис. 2. Зависимость величин s и k в задаче поиска среднего арифметического значения при n = 10 и p = 20: для одного наибольшего значения при m = 3 (а) и m = 20 (б); для двух наибольших значений при m = 3 (в) и m = 20 (г)

а			б
в		г

Рис. 3. Зависимость величин s и k в задаче поиска среднего арифметического значения при m = 10 и p = 20: для одного наибольшего значения при n = 3 (а) и n = 20 (б); для двух наибольших значений при n = 4 (в) и n = 20 (г)

а			б
в		г

Рис. 4. Зависимость величин s и k в задаче поиска среднего арифметического значения при n = 10 и m = 10: для одного наибольшего значения при p = 10 (а) и p = 100 (б); для двух наибольших значений при p = 10 (в) и p = 100 (г)

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

Второй закономерностью является высокая сходимость вероятности. По большинству графиков видно, что результаты, полученные по формуле Байеса, резко увеличиваются до своей асимптоты. Это свойство положительно проявляет себя для первой задачи. Это и не удивительно, т. к. ее можно отнести к классу «классических», когда известны вероятности появления событий и вычисляется, какое из них наиболее вероятно. В таких ситуациях множество факторов совпадает с множеством альтернатив, что как раз характерно для задачи поиска максимального значения. Поэтому вероятность порой и дает результаты лучшие, чем функция уверенности. Но из таких результатов следуют странные выводы: сколь много мы не узнавали бы о системе, эти данные не дают возможности лучше понять ее поведение. Только в первой серии экспериментов (рис. 2, в), ввиду малого числа прецедентов, не виден резкий скачок правильных ответов для вероятности, по отношению к функции уверенности. Во всех же остальных случаях это не так. В то же время функция уверенности почти ни на одном из графиков (за исключением тех, где достигнута отметка в 100% правильных ответов) не достигает своей асимптоты. Она замедляет свой рост, но не выполажывается. Этот результат соответствует нашему пониманию того, что чем больше известно о поведении системы, тем лучше можно предсказать ее поведение. Но с каждым следующим прецедентом уверенность растет все в меньшей степени, поэтому при большом числе прецедентов количество правильных ответов растет не так быстро, как в самом начале.

С физической точки зрения прослеживается интересная закономерность: с ростом числа учитываемых x-переменных растет количество правильных ответов. То же наблюдается при росте числа прецедентов. Это отражает естественное предположение, что чем больше мы знаем про систему, тем точнее мы можем предсказать ее поведение. Но при этом с ростом количества y-переменных наблюдается уменьшение правильных ответов, что тоже соответствует нашей интуиции.

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

Для экспериментальной оценки предложенных методов была проведена серия экспериментов, заключающаяся в выборе одной из y-переменных на основании x-переменных в той ситуации, когда множество Y не совпадает с множеством X. Сформированные данные обрабатывались тремя функциями: линейной, Кобба-Дугласа, Солоу. Не обработанные исходные данные так же анализировались в рамках вероятностного подхода с использованием теоремы Байеса. В процессе тестирования получены графики зависимости количества правильных ответов от определяющих параметров: количество прецедентов, количество x-переменных, количество y-переменных, количество принимаемых значений каждой x-переменной. Анализ экспериментов позволил установить, что в качестве функции, обрабатывающей сформулированные данные, наиболее подходящей по критерии количества правильных ответов оказалась функция Солоу при коэффициенте β_i = 1. Однако эти отличия от функции Кобба-Дугласа и функции Солоу при β_i = 2 оказались не столь существенными. В свою очередь, Байесовский подход показал результаты, уступающие предложенным подходам.