Расширенный анализ внутрисистемных взаимосвязей

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

РАСШИРЕННЫЙ АНАЛИЗ ВНУТРИСИСТЕМНЫХ ВЗАИМОСВЯЗЕЙ

Вероятностный реконструктивный анализ (PRA). Метод анализа зависимости (DA). Ограничения на размерность систем. Эвристика H2: нахождение перспективных множеств переменных. Эвристика H3: выбор дополнительных связанных переменных. Расширенный анализ зависимости для больших систем (EDA). Алгоритм DEDUCE. Статический анализ зависимости на основе EDA. Эвристики H4, H5, H6.

Метод расширенного анализа зависимостей разработан Конантом (Conant C.R., 1988) в развитие идей реконструктивного анализа, реализованных в проекте GSPS Дж. Клира. Главной задачей расширенного метода является ослабление ограничений размерности, свойственных GSPS, и обеспечение реальной возможности решения прикладных задач реконструкции систем с сотнями переменных.

На пути создания метода К. Конант разработал два алгоритма: PRA (вероятностный реконструктивный анализ) и DA (анализ зависимости). Оба эти алгоритма по своей сути аналогичны GSPS и, подобно GSPS, они неспособны обработать системы, имеющие более 10 переменных.

Алгоритмы PRA и DA декомпозируют вероятностную функцию, описывающую систему с n переменными, во множество более простых отношений с сохранением в упрощенной версии примерно того же объема информации, что и в исходной системе. Расширение PRA и DA состоит в дополнении этих алгоритмов специальными эвристиками (H2, H3, H4, H5, H6) и создании на этой основе новой аналитической технологии реконструкции больших систем.

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

Задача вероятностного реконструктивного анализа (PRA). Система представляется множеством V = {v1, v2,.., vn} базовых переменных. Предполагается, что переменные vi дискретны, и число значений таких переменных конечно. Система данных представляет собой выборку из глобального распределения вероятностей p(V) = p[v1, v2,.., vn]. Задача PRA состоит в разбиении распределения p(V) на множество вероятностных распределений SD ={p(E1), p(E2),..., p(Em)} таких, что:

m

Ej V; Ej = V; (Ej = Ek) (j = k)

j j = 1 j, k

композиция всех найденных распределений p(Ej) даст p(V) в рамках некоторого заранее принятого разрешения;

любая попытка декомпозиции какого-либо (любого) элемента полученного множества SD приведет к неприемлемой потере информации;

все связанные переменные вместе входят в одно или большее число распределений p[Ej1, Ej2,..., Ejk]. Несвязанные переменные входят только в разные распределения.

Задача анализа зависимостей (DA). Анализ начинается с получения условных распределений вероятностей p(r) = p(rV), r = 1(1)n базовых переменных vr,t, возникающих вследствие реализации Vt-1. Распределение p(r) заключает в себе все связи между переменными vr,t и всеми другими переменными системы vj,t-1, j = 1(1)n в предыдущий момент времени. Множество этих условных вероятностей характеризует динамическое поведение системы:

vr D[vr], r = 1(1)n. Эта запись Vt-1 Vt означает, что D[v(r)] Vt-1 может прогнозировать значения vr,t Vt. Именно эта способность реализуется в условном распределении p{vrD[vr]};

множество распределений {p{vrD[vr]}} = SD* аппроксимирует глобальное распределение p(V);

каждая условная вероятность p{vrD[vr]} порождает уже не условное распределение p{vr, D[vr]}, где p[vr] и p{D[vr]} известны из данных.

Результатами DA являются:

зависимости {vr D[vrvr = 1(1)n]}; каждая vr D[vr] воплощает условную зависимость, а D[vr] имеет тот же смысл, что и Ej в PRA;

SD* в DA имеет тот же смысл, что и SD в PRA. Множество распределений SD* уменьшается путем исключения избыточных и включенных распределений;

DA и PRA полностью совместимы. Совместимость методов допускает использование DA вместо PRA, применение которой связано с большими вычислительными затратами;

DA целесообразно использовать для нахождения тесно связанных переменных.

Ограничения на размерность систем. Для доверительного анализа глобального распределения p(V), а также доверительного анализа частных распределений p{vr, D[vr]} в DA или p(Ej) в PRA необходимо выполнить достаточное количество наблюдений. Необходимое число наблюдений задается степенной зависимостью, имеющей в качестве основания количество значений переменных, а в качестве показателя - число переменных. Поэтому даже при 10 переменных, принимающих каждая дискретные значения только на 5 уровнях, применение алгоритмов DA и PRA возможно, если в системе данных содержится около 50 миллионов наблюдений. При реконструкции систем на базе DA или PRA структуры систем из n переменных упорядочиваются, начиная от самых сложных (глобальные агрегаты), и заканчиваются структурами с несвязными элементами. Отношение порядка на множестве получаемых структур задает решетку, в которой структура S1 помещается выше структуры S2, если S1 сложнее S2. Такая решетка взрывным образом растет как двойная степенная зависимость с увеличением числа переменных n: Число структур = exp [exp(-0.78 + 0.59n)]

Для сравнения структур в DA и PRA используются значения кросс-энтропии (передачи):

p[vr,V]

T[vr,V] = p[vr,V] log2

r V p[vr] p(V)

Вычисление каждой передачи T [vr,V] связано с выполнением операций сложения и логарифмирования. Если считать, что все переменные принимают одинаковое число значений Q, то число необходимых сложений и логарифмирований будет равно соответственно A(n, Q) и L(n, Q), где:

n

A(n,Q) = Cn,k Qk ,

k=1

n

L(n,Q) = Cn,k-1 Qk ,

k=1

Cn, k - биномиальные коэффициенты.

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

Нахождение перспективных множеств переменных: эвристика H2. Алгоритм DA лучше всего использовать в совокупности с эвристическим алгоритмом H2. В этом случае DA отводится роль фильтра. На вход DA подаются переменные vr,t Vt и множество перспективных переменных CVt-1 Vt-1, сформированное на предыдущем шаге эвристикой H2. Какая-то часть CV может не нести информации о vr,t. Желательно избежать этого и включать в CV лишь те переменные vj,t-1, j{1,..,n}, которые содержат существенную информацию о vr,t.

В качестве индикатора объема информации, содержащегося в V и связанного с vr применяется кросс-энтропия T[vr,V]. Следует иметь ввиду, что в ряде случаев значение T[vr,V] может показывать слабую зависимость, хотя на самом деле влияние V на vr достаточно существенно. Этот факт обусловлен тем обстоятельством, что T[vr,V] оценивает только бинарные отношения переменных в системе.

На выходе DA определяется множество {vr,t D[vj,t-1]}. Если в качестве перспективного набора переменных выбран набор V' CVt-1, в состав которого вошли не все vj,t-1, влияющие на vr,t, то есть V' D[vj,t-1], тогда будет выполняться неравенство T[vr, V'] < T{vr,D[vr]}, что означает возможность появления грубых ошибок при реконструкции. Если же набор переменных V' выбран так, что V' D[vj,t-1], то будет иметь место примерное равенство оценок: T[vr, V'] T{vr,D[vr]}. Отсюда следует, что применение избыточного набора переменных в алгоритме DA не улучшит его результат.

Таким образом, DA, выступая как фильтр переменных из перспективного множества CV, отбросит те его элементы vj,t-1, которые сочтет несвязанными с vr,t, и оставит D[vr,t] CV - множество минимального размера, обладающее наиболее полной информацией о vr,t. Если при этом CV = V, то уже при n = 10 проявятся ограничения размерности, и DA станет непригодным. Задача состоит в нахождении для каждого vr,t подходящего CV, способного обеспечить результативность DA. Именно такие подходящие множества генерирует эвристический алгоритм H2.

Вычислительная сложность H2 - многочлен. Поэтому H2 может рассматриваться как эффективный инструмент ослабления ограничений размерности. H2 генерирует множества CVr достаточно малого размера такие, чтобы с ними успешно справлялся алгоритм DA. Эти множества являются надмножествами по отношению к D[vr]. Максимальное из них M = max{CV1, CV2,.., CVn} должно быть не меньше, чем max{D[v1], D[v2],..., D[vn]}. Если при этом M будет больше, чем это необходимо, то DA утратит эффективность из-за ограничений размерности.

Если M выбрана малой, в силу M < D[vr] для некоторых переменных, то установленные зависимости будут неадекватными. Рекомендации:

D[vr] < 10, например: M = 7.

vr

Идея алгоритма H2.

1. Найти силу стохастической взаимосвязи между vr,t и всеми парами переменных vj из Vt-1.

Всего пар: 0.5n(n-1).

Для оценки силы связи использовать кросс-энтропию T(r;j,k):

T(r;j,k) = T[vr,t; vj,t-1, vk,t-1]; 1 j < n, 1 < k n.

Если T(r;j,k) окажется статистически значимой по "хи-квадрат" при p = 0.95, то в списке LT появится тройка <j,k;T(r;j,k)>.

2. Если LT - пустой (Это означает, что vr не связана ни с какой парой переменных из множества Vt-1.), то СТОП, ИНАЧЕ 3.

3. Сортировать LT по убыванию силы связи.

4. Начиная от первой тройки списка LT, заносить в CV пары (j,k) до тех пор, пока:

а) LT исчерпан,

б) CV = M. В этом случае в CV войдут переменные, образующие с vr наиболее сильные парные связи.

Замечания к алгоритму H2. Эвристика H2 работает как генератор множества CVr. В силу этой своей единственной функции H2 может использовать малое значение тестовой вероятности p = 0.95 для "хи-квадрат". Поэтому значимость входящих в Cvr элементов, во обще говоря, сомнительна. CVr, поступающие на вход DA, отфильтровываются этим алгоритмом очень тщательно (p = 0.99). В CVr могут не войти некоторые значимые при p = 0.95 связи, "отрезанные" по признаку превышения разрешенной длины списка LT > M. H2 изучает отношения на множествах трех переменных. Если связь значима только для большего числа переменных, то эти связи H2 не выявляет.

Нахождение дополнительных переменных: эвристика H3. (H2, DA) - недостаточно адекватная процедура. Ее целесообразно дополнить еще одним более тонким алгоритмом, следующим за (H2, DA) и имеющим своей задачей более глубокое исследование возможных, но пропущенных существенных зависимостей. Согласно идее расширения (H2, DA), алгоритм H2 рассматривается в качестве генератора первого приближения CV1r перспективного множества CVr, а DA - в качестве фильтра, формирующего лишь первое приближение D1[vr] множества D[vr]. После генерации множества D1[vr] алгоритм DA начинает работать в цикле с эвристикой H3, продуцируя одно за другим множества Dk[vr], k=2(1)K. При первом запуске цикла (DA, H3) в качестве начальных условий принимаются:

k=1, CVr = CV1r, D[vr]= D1[vr],

n

UV1 = V - CV1r.

r=1

H3 - быстрая процедура. Она заканчивается, когда завершится проверка всех vi из UV1 или когда CVK+1 = CVK = DK[vr]. Здесь VK+1 - перспективное множество переменных (K+1)-го цикла. Все Dk[vr], k=2(1)K, должны входить в CVK+1.

Идея алгоритма H3.

1. Найти сильные связи между отдельными переменными vi из UV1 и множеством {vr}Dk[vr] путем вычисления передач T(i,rDk) = T[vi, vrDk[vr]] для всех vi из UV1. Если какая-то передача будет значима по "хи-квадрат" при p = 0.95, то в список LP занести соответствующую ей пару i,T(i,rDk). Уточнить, связана ли дополнительная переменная vi c vr или с переменными из множества Dk[vr].

2. Если LP - пусто, то СТОП, ИНАЧЕ 3.

3. Сортировать LP по убыванию значений передач.

4. Начиная с первой пары в LP, добавлять переменные в CVk+1 до того момента, как:

а) LP исчерпан,

б) CVk+1 = M.

Замечания к алгоритму H3. Передача T(i,rDk) измеряет связь между vi и переменными из Dk[vr]. Если D[vr] Dk[vr]\vi, то T - мало. Если D[vr] Dk[vr] vi, то T - значима. Этот ключевой шаг в H3 позволяет найти переменные vi, имеющие с vr связь выше третьего порядка. В данном случае причинность (временной сдвиг) не учитывается. Процесс (H2,DA)+{(H3,DA)} образует в совокупности метод EDA - расширенный метод анализа зависимости.

Расширенный метод анализа зависимости (EDA). Метод EDA находит:

множество зависимостей каждой из n переменных;

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

значимость предсказывающей связи для каждой переменной vr. Если T[r,D[vr]] = H(r), где H(r) - r - энтропия, то vr полностью определяется переменными из D[vr]. Если T[r,D[vr]] чуть превышает критерий значимости по "хи-квадрат" при p = 0.99, то прогноз ненадежный;

если D[vr] обнаружено, то необходимо найти данные для переменных из D[vr] {vr} и построить таблицу наблюдений, по которой определить частоты (распределение частот);

в некоторых случаях EDA выдает D[v(r)], в состав, которого входят переменные, едва преодолевшие тест на значимость передачи. Такие переменные могут быть исключены в результате моделирования (алгоритм DEDUCE), дополняющего процедуру EDA.

Общая оценка EDA. Метод EDA эффективен в задачах динамического и статического анализа. Для упорядоченных по параметру систем данных найденная EDA структура является одновременно функциональной структурой динамических зависимостей в системе. Для неупорядоченных систем данных найденная структура является декомпозицией глобального вероятностного распределения на более простые распределения (задача PRA).

зависимость анализ метод автоматизированный

Рис. 1 - EDA с дополнительными эвристиками H4, H5, H6

В динамическом анализе выявляются независимые причинные связи между vr и D[vr] CVt-1. Независимость множеств типа {vr D[vr]}, характерная для DA, в статической задаче не выполняется. Это обстоятельство - осложняющий фактор в задаче реконструкции. Системы с такими связями представляются графами с петлями, если перейти к так называемым системным графам, где вершинами считаются связи, а ребра - переменными.

Алгоритм EDA для статического анализа содержит чистый метод EDA и две эвристических процедуры:

для каждой vr алгоритм H2 находит множество зависимости {vr} то есть {vr D[vr]vr из V};

запускается цикл (DA,H3) до достижения установленного критерия;

получаются наименьшие множества D[vr], обладающие максимальной информативностью по отношению к vr; обычно v(r) не принадлежит D[vr];

можно предположить, что существует многоместное отношение R(vr, D[vr]), поэтому множество {vr D[vr]} также может быть элементом структуры;

структуру системы описывают n множеств переменных {vr D[vr]vr V}; весьма вероятно, что они избыточны;

строится граф, вершинами которого являются переменные системы, ребрами соединяются пары переменных из одного и того же множества D[vr];

находятся клики графа; каждая клика рассматривается как один элемент искомой структуры системы;

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

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

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

Литература

1. Conant C.R. //Intern. J. General Systems. Vol. 14. - 1988. pp. 97 - 123.

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