Книги по разным темам Pages:     | 1 |   ...   | 25 | 26 | 27 | 28 | 29 |   ...   | 41 |

Как выяснено выше, любая система определяется таким образом, что она хорошо согласуется с заданной системой данных и дополнительной информацией по маске и принятому типу описания ограничений. Таким образом, требование согласованности имеет более высокий приоритет, чем остальные требования. Теперь остается только применить условия 3) и 4) обычно называемые условием детерминированности и условием простоты, для вывода подмножества решений YQ ограниченного множества Yr.

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

В.5 Меры нечеткости Степень недетерминированности должна измеряться обобщенной нечеткостью, сопутствующей порождению данных. А значит, она должна быть определена через порождающие функции поведения fGB и fИGB для нейтральных и направленных систем с поведением. Если эти функции представляют собой функции распределения вероятностей, то мера обобщенной нечеткости хорошо известна - это шенноновская энтропия, введенная К. Шенноном в 1948 году.

Обозначим через Р множество всех распределений вероятностей, которые могут быть определены на конечных множествах альтернативных (взаимно исключающих) исходов. Тогда вероятностная мера нечеткости - это функция H : P [0,], обладающая некоторыми свойствами. Следующие свойства являются необходимыми свойствами любой содержательной меры нечеткости:

Н1 симметричность - нечеткость инвариантна относительно перестановки вероятностей;

Н2 расширяемость - нечеткость не меняется при добавлении к рассматриваемому множеству исходов с нулевой вероятностью;

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

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

Н5 непрерывность - нечеткость - это непрерывная функция на всех своих аргументах.

Известно, что только функции вида H( f (x)| x X )= -a f (x)logb f (x) xX обладают свойствами Н1-Н5;

( f (x)| x X ) P - это распределение вероятностей для определенного конечного множества X альтернативных исходов x, где a - произвольная положительная константа, а b- произвольное основание логарифмов. Если потребовать выполнения еще и нормализующего свойства H(0.5;0.5)=(нечеткость двух равновероятных исходов равна 1), то мера нечеткости определяется однозначно:

H( f (x)| x X )= H(x)= - f (x)log2 f (x). (В.37) xX Обычно функцию (В.37) называют шенноновской энтропией. Она измеряет нечеткость в единицах, называемых битами.

Рассмотрим теперь порождающую нечеткость в системах, описываемых с помощью функций распределения возможностей. Пусть П - это множество всех распределений возможностей, имеющих по крайней мере одно ненулевое значение, которые можно определить на конечных множествах альтернативных исходов. Тогда возможностная мера нечеткости представляет собой функцию U : П [0,], (В.48) обладающую определенными свойствами. Прежде чем рассматривать эти свойства, нужно сначала ввести некоторые понятия, связанные с распределениями возможностей.

1 Распределение возможностей f = ( | i N|X |) П, (В.51) определенное на конечном множестве X альтернативных исходов x называется нормализованным распределением возможностей тогда и только тогда, когда maxi = 1; (В.52) i понятно, что i = f (x) для некоторого взаимнооднозначного соответствия между N|X| и X.

2 Пусть для любого распределения возможностей f, например для распределения, определенного в (49), и для любого действительного l [0,1] c : П [0,1] P(N) (В.53) такая функция, что c( f,l)= {i N |i l}. (В.54) X Эта функция называется функцией l-уровня, а множество c( f,l)- множеством l- уровня от f.

3 Для заданного распределения возможностей (49) назовем (В.55) Lf = {l | (Ei N )(i = l) или l = 0} X уровневым множеством для f. Обозначим через Lf = {l1,l2,...,lq} уровневое множество для f, где l1=0, q = Lf, причем из i < j следует, что li < l. Пусть для удобства j l = maxi.

f i Понятно, что l = lq Lf. Кроме того, l =1 тогда и только тогда, когда f явf f ляется нормализованным распределением возможностей.

4 Для любого m N пусть 1 f =( i | i Nm) П, 2 f = ( i | i Nm) П, два распределения возможностей. Тогда f называется субраспределением f тогда и только тогда, когда для любого i Nm max1i =max2i и i 2i.

i i Пусть 1 f 2f означает, что 1 f является субраспределением f. Понятно, что отношение л1 f субраспределение f представляет собой частичное упорядочение, определенное на любом множестве распределений возможностей с m m числом элементов, равным m. Обозначим это множество П. Далее ( П, ) - это решетка с объединением и пересечением, определяемыми соответственно как 1 2 f f = (max[i,2i]| i Nm), 1 2 f f = (min[i,2i]| i Nm) для любых 1 f, f m П.

Теперь, располагая определенными понятиями, связанными с рапсределениями возможностей, можно вернуться к обсуждению главного вопроса - о мере возможностной нечеткости. Хотелось бы, чтобы возможностные аналоги свойств Н1 - Н5, которыми обладает шенноновская энтропия, также выполнялись бы и для возможностной меры нечеткости. Возможностные аналоги этих свойств можно сформулировать точно так же, как Н1-Н5, за тем только исключением, что слово вероятность нужно везде изменить на слово возможность. Функция вида (48), удовлетворяющая этим свойствам, известна. Ее можно представить в виде q-U( f )= (В.56) (l - lk )log c( f,lk+1), k+l k=f или в более простом виде l f U( f )= (В.57) log c( f,l)dl.

l f Эта функция называется U - нечеткостью. Помимо возможностных аналогов свойств Н1-Н2, U - нечеткость обладает некоторыми другими полезными свойствами. Важнейшим из них является монотонность: для лю1 бых 1 f,2f m П(m N), если 1 f 2f, то U( f ) U( f ).

В.6 Поиск подходящих систем с поведением Располагая теперь мерами нечеткости, через которые выражается степень детерминированности, вернемся в данном разделе к типу задач, введенному в разделе 6.4; дана система данных D с полностью упорядоченным параметрическим множеством и с наибольшей допустимой маской М, совместимой с D; требуется определить все системы с поведением, удовлетворяющие требованиям согласованности, детерминированности и простоты, причем требование согласованности более приоритетно, чем остальные два.

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

Для заданной функции fB, определенной через полные состояния неких выборочных переменных, любая из ее проекций также является функцией поведения, соответствующей fB в смысле субсостояний, основанных на определенном подмножестве выборочных переменных. Пусть sk (k N ) - выбоM рочные переменные, через которые определяются состояния fB; М - маска, через которую выбираются значения выборочных переменных. Пусть [fB Z]- проекция fB, где подмножество множества N|M| идентификаторов выборочных переменных, то есть Z N. Тогда [ fB Z]: Sk [0,1], (В.67) kZ так что [fB Z](x)= a({ f (c)| c f x}), (В.68) где а - некая агрегирующая функция, определяемая характером функции fB.

Например, [fB Z](x)= fB(c), (В.69) cfx где fB - распределение вероятностей; соответственно для распределения возможностей, [fB Z](x)= max fB(c). (В.70) cfx Будем в контексте любой конкретной задачи через 1 fB обозначать функi цию поведения для наибольшей приемлемой маски М. Через fB(i = 2,3,...), будем обозначать функции поведениядля ее различных осмысленных подмаi i сок M, каждая из которых связана с множеством Z N идентификатоM ров выборочныз переменных.

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

Пример В.4 Определим проекцию вероятностной функции поведения, приведенной в таблице В.1 и возможностной функции поведения, приведенной в таблице В.2 для Z ={1,2}.

Таблица В.S1 S2 S3 S4 f(c) С= 0 0 0 0 0.0 0 0 1 0.0 0 1 0 0.0 1 0 1 0.1 0 0 0 0.1 0 1 0 0.1 1 0 1 0.1 1 1 0 0.Таблица В.S1 S2 S3 f(c) С= 0 0 0 1.0 0 1 0.0 1 1 0.1 0 0 0.1 1 1 0.Применив формулу (В.58) для вероятностной функции, получим:

S1 S2 [f{1,2}](x) x= 0 0 0.5(=0.2+0.2+1) 0 1 0.1 0 0.2(=0.1+0.1) 1 1 0.2(=0/1+0/1) Для возможностной функции по формуле (В.59) имеем S1 S2 [f{1,2}](x) x= 0 0 1.0 1 0.1 0 0.1 1 0.Для заданной системы данных D и наибольшей допустимой маски М требование соответствия приводит к ограниченному множеству Yr ={iFB = (I,iM,if )| i =1,2,..., N(n,M )}, содержащему по одной системе с поведением для каждой осмысленной масi ки M M ; пусть для удобства 1M = M. Следующим шагом решения рассматриваемой задачи должно быть вычисление степеней недетерминированности и сложности для всех систем из множества Yr.

Как было показано в разделе В.5, степень недетерминированности задается соответствующей мерой порождающей нечеткости, определяемой для вероятностных систем шенноновской энтропией, а для возможностных систем U - нечеткостью. Для определения порождающей нечеткости требуется, чтобы был определен порядок порождения (и соответствующее разбиение любой маски). Если допускается несколько порядков порождения, то для каждой маски мы берем порядок с наименьшей порождающей нечеткостью.

Что касается меры сложности, то тут возможно много вариантов.

Возьмем для примера простую, но содержательную меру - размер (мощi ность) маски. Пусть qu (i =1,2,...) - значение соответствующих порождающих i нечеткостей для систем с поведением FB из ограниченного множества Yr.

Поскольку любая система FB однозначно идентифицируется своей маской М, i i мощность которой M задает ее сложность, статус системы FB в смысле i порождающей нечеткости и сложности удобно описывать парой( M,iqu).

Теперь рассматриваемую задачу можно обсуждать в терминах масок iM, а не соответствующих систем с поведением iFB.

Численное упорядочение масок iM, идентифицирующих системы из Yr с по их мощности, задает упорядочение сложности на множестве Yr. Численное упорядочение значений iqu определяет упорядочение по нечеткости u на множестве Yr. В то время, как упорядочение по сложности полностью определяется самими масками, упорядочение по нечеткости может быть определено только после оценки масок. Для любого множества порождающих i j масок мы можем определить частичное упорядочение MG MG тогда и только тогда, когда i i i g=ig и g < g. (В.60) (или ie

Пример упорядоченности по сложности и упорядоченности подмасок для наибольшей допустимой маски М при n=3 u M=2 приведен далее... Из этого примера видно, что упорядочение по сложности - это связное квазиупорядочение (рефлексивное и транзитивное отношение, определенное для любой пары систем).

Упорядочение по подмаскам - это частичное упорядочение, но решетки оно не образует. Однако оно представляет собой набор решеток по одной для каждого множества порождаемых выборочных переменных (в нашем примере это крайние правые элементы масок).

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

Таким образом, на множестве Yr определены два связных квазиупорядочения - по сложности и по нечеткости. Было бы желательно объединить их неким подходящим образом. Поскольку для рассматриваемого типа задач требуется, чтобы и сложность и порождающая нечеткость систем во множестве решений YQ, были минимизированы. Соответствующее объединенное * упорядочение определяется следующим образом:

* i j FB FB тогда и только тогда, когда c u i j i j M M и qu qu, (В.61) i j где FB, FB Yr. Это упорядочение не является связным, поскольку пары i j i j j i j i j FB, FB, для которых M < M и iqu > qu или M > M и qu < qu (подобные пары, разумеется, могут существовать), несравнимы. Оно также неантисимметрично, так как не исключена возможность того, что i j j M = M и iqu = qu для некоторых i j. Следовательно объединенное упорядочение - это общего вида квазиупорядочение (рефлексивное и транзитивное отношение) на Yr.

Теперь множество решений YQ можно определить как множество всех систем из Yr, которые или эквивалентны, или несравнимы относительно объединенного упорядочения (В.61). Две системы из Yr, скажем системы iFB и j FB, несравнимы в смысле обединенного упорядочения, если выполнено одно из следующих условий:

i j i FB более сложна и менее детерминирована, чем FB или FB менее j сложна и более детерминирована, чем FB. Формально * * j j j YQ ={iFB Yr | ( FB Yr )( FB iFB iFB FB )}. (В.62) Системы из множества решений YQ будем называть подходящими системами с поведением для рассматриваемого типа задач.

Пример В.5 Чтобы пояснить различные вопросы, изучаемые в данном разделе, рассмотрим этологическую систему данных, описанную в примере В.2 (смотри также рисунок В.8). Определим все подходящие в смысле (В.62) системы с поведением для этой системы данных в предположении, что пользователь хочет получить описания вероятностных систем с поведением и использовать их для предсказания.

Pages:     | 1 |   ...   | 25 | 26 | 27 | 28 | 29 |   ...   | 41 |    Книги по разным темам