Интеллектуальный анализ данных
 Скачать 7.76 Mb.
|
|
n s t , где s – исправ- ленное выборочное среднее квадратическое отклонение, а t определяется по со- ответствующей таблице распределения Стьюдента ) , ( k S 3) Если случайная величина распределена по иному закону ) , a ( N F 2 , то при достаточно большом количестве испытаний (n > 30) можно использовать для оценки предыдущие формулы, так как при n распределе- ние Стьюдента стремится к нормальному N k S n ) , ( , и границы интервалов, полученные по ранее приведенным формулам, различаются незначительно. 5. Интегрирование методом Монте-Карло Предположим, необходимо взять интеграл от некоторой функции. Вос- пользуемся неформальным геометрическим описанием интеграла и будем пони- мать его как площадь под графиком этой функции. Для определения этой площади можно воспользоваться одним из обыч- ных численных методов интегрирования: разбить отрезок на подотрезки, подсчи- тать площадь под графиком функции на каждом из них и сложить. Предположим, что для некоторой функции достаточно разбиения на 25 отрезков и, следователь- но, вычисления 25 значений функции. Представим теперь, мы имеем дело с - мерной функцией. Тогда нам необходимо отрезков и столько же вычислений значения функции. При размерности функции больше 10 задача становится ог- ромной. Поскольку пространства большой размерности встречаются, в частности, в задачах теории струн, а также многих других физических задачах, где имеются системы со многими степенями свободы, необходимо иметь метод решения, вы- числительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло. Приложение. Справка: История метода. Рождение метода Монте-Карло в Лос-Аламосе Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использовать связь между стохастическими процессами и дифференциальными уравнениями «в обратную сторону». Они предложили использовать стохастический подход для аппроксимации мно- 94 гомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде. Идея была развита Уламом, который, по иронии судьбы, также, как и Фокс бо- ролся с вынужденным бездельем во время выздоровления после болезни, и, расклады- вая пасьянсы, задался вопросом, какова вероятность того, что пасьянс «сложится». Ему в голову пришла идея, что вместо того, чтобы использовать обычные для подобных задач соображения комбинаторики, можно просто поставить «эксперимент» большое число раз и, таким образом, подсчитав число удачных исходов, оценить их вероятность. Он же предложил использовать компьютеры для расчётов методом Монте-Карло. Появление первых электронных компьютеров, которые могли с большой скоро- стью генерировать псевдослучайные числа, резко расширило круг задач, для решения которых стохастический подход оказался более эффективным, чем другие математиче- ские методы. После этого произошёл большой прорыв и метод Монте-Карло применялся во многих задачах, однако его использование не всегда было оправдано из-за большого количества вычислений, необходимых для получения ответа с заданной точностью. Годом рождения метода Монте-Карло считается 1949 год, когда в свет выходит статья Метрополиса и Улама «Метод Монте-Карло».Название метода происходит от на- звания города в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известных генераторов слу- чайных чисел. Станислав Улам пишет в своей автобиографии «Приключения математи- ка», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком. Дальнейшее развитие и современность В 1950-х годах метод использовался для расчётов при разработке водородной бомбы. Основные заслуги в развитии метода в это время принадлежат сотрудникам ла- бораторий ВВС США и корпорации RAND. В 1970-х годах в новой области математики — теории вычислительной сложно- сти было показано, что существует класс задач, сложность (количество вычислений, не- обходимых для получения точного ответа) которых растёт с размерностью задачи экспо- ненциально. Иногда можно, пожертвовав точностью, найти алгоритм, сложность которого растёт медленнее, но есть большое количество задач, для которого этого нельзя сделать (например, задача определения объёма выпуклого тела в n-мерном евклидовом про- странстве) и метод Монте-Карло является единственной возможностью для получения достаточно точного ответа за приемлемое время. В настоящее время основные усилия исследователей направлены на создание эффективных Монте-Карло алгоритмов различных физических, химических и социальных процессов для параллельных вычислительных систем. Вопросы для самопроверки: 1. Что называется методом Монте-Карло? 2. Назовите типовые задачи метода Монте-Карло. 3. Какие вопросы исследует теория метода Монте-Карло? 4. Что называется разыгрыванием случайной величины? 5. Каким образом осуществляется разыгрывание дискретной случайной ве- личины? 6. Каким образом осуществляется разыгрывание противоположных собы- тий? 7. Каким образом осуществляется разыгрывание непрерывной случайной величины? 8. Опишите метод обратных функций. 9. Опишите метод суперпозиции. 10. Каким образом осуществляется приближенное разыгрывание нормаль- ной случайной величины? 95 11. Каким образом осуществляется оценка погрешности метода Монте- Карло? 12. Расскажите историю метода Монте-Карло. 96 ЛЕКЦИЯ 10 АНАЛИЗ ДАННЫХ МЕТОДАМИ ПРОВЕРКИ СТАТИСТИЧЕСКИХ ГИПОТЕЗ Вопросы: Введение. 1. Общая логическая схема статистического критерия; 2. Построение статистического критерия: принцип отношения правдоподо- бия; 3. Основные типы гипотез, проверяемых в ходе статистической обработки наблюдений. Заключение. Контрольные вопросы. Введение На разных стадиях формирования управленческих решений возникает не- обходимость в формулировке и экспериментальной проверке некоторых предпо- ложительных утверждений (гипотез) относительно величины или происхождения параметров анализируемой системы. Например, могут возникнуть предположения типа: "По данным наблюдений факторы экономической угрозы отсутствуют" или "Состояние контролируемого технического объекта изменилось". Будем в дальнейшем обозначать высказанное нами предположение (гипо- тезу) буквой H. Задача состоит в проверке непротиворечивости высказанной нами гипотезы имеющимся наблюдениям. Процедура обоснованного сопоставления высказанной гипотезы с имею- щимися выборочными данными (наблюдениями) X 1 , X 2 ,..., X n осуществляется с помощью того или иного статистического критерия и называется статистиче- ской проверкой гипотез. Результат подобного сопоставления может быть либо отрицательным (данные наблюдения противоречат высказанной гипотезе, и от этой гипотезы следует отказаться), либо неотрицательными (данные наблюдения не противоречат высказанной гипотезе, и, следовательно, ее можно принять в качестве одного из естественных и допустимых решений). При этом неотрицательный результат статистической проверки гипотез не означает, что высказанное предположительное утверждение является наилучшим, единственно подходящим: просто она не противоречит имеющимся наблюдениям. Однако такими же свойствами могут наряду с Н обладать и другие гипотезы. Таким образом, даже статистически проверенное предположение Н следует расценивать не как абсолютно достоверный факт, а лишь как достаточно правдоподобное, не противоречащее наблюдениям утверждение. 1. Общая логическая схема статистического критерия На разных стадиях формирования решений возникает необходимость в формулировке и статистической проверке утверждений (гипотез) относительно природы или величины неизвестных параметров объекта анализа (ОА). Например, необходимо установить факт наличия фактора системного сигнала в принимаемой смеси сигнал-шум или установить факт изменения состояния ОА по результатам последовательности наблюдений. 97 Процедура сопоставления истинности высказанной гипотезы с имеющимися выборочными данными X 1 , X 2 , …, X n осуществляется с помощью статистиче- ского критерия и называется статистической проверкой гипотез. В результате проверки гипотезы устанавливается либо отрицательный ре- зультат (данные противоречат высказанной гипотезе), либо неотрицательный (но не положительный!) - данные не противоречат гипотезе. Неотрицательный результат не означает оптимальности решения. Более того, он не означает, что утверждение верно. Логическая схема статистической проверки гипотезы представляет собой следующую последовательность. 1. Выдвигается гипотеза H o (например, ОА перешел из состояния исправно- сти в состояние неисправности 1). В тех случаях, когда это возможно, формирует- ся альтернатива (альтернативная гипотеза) H 1 (например, ОА не перешел в со- стояние неисправности 1). 2. Исходя из внешних (экзогенных) соображений, вытекающих из требова- ний гиперсистемы (например, требований технического отдела), задаются: - величиной уровня значимости критерия ( - вероятность ошибочного решения 1 рода - отвергнута H o , хотя на самом деле она верна, "пропуск цели", "пропуск неисправности"); - мощностью критерия 1- ( - вероятность ошибочного решения 2 рода - принята H o , хотя на самом деле она ошибочна, "ложная тревога"). формиру- ется лишь при наличии альтернативы H 1 При ограниченном n задается произвольно; при этом обычно задаются стандартные значения =0,1; 0,05; 0,025; 0,01; 0,005; 0,001, в зависимости от значимости последствий, к которым приводит ошибочное неприятие Ho; при n0 теоретически , 0 для H 1 3. Задаются критической статистикой (функцией от X) θ n = θ (X 1 , X 2 , ..., X n ), подчиненной известному табулированному закону распределения f(θ n ) и определяющей меру расхождения (X n , XϵH o ). 98 Из таблиц f(θ n , u) для заданного определяют критические точки: (1- /2) - ая точка θ min (/2) и /2-ая точка θ max (/2), разделяющие область возможных значений θ на область принятия гипотезы H o Г о () и область (двухсвязную) Г 1 ( ), попадание в которую означает неприятие H o 4. Вычисляется θ n = θ(X 1 , X 2 ,..., X n ) и в зависимости от принадлежности θ n Г о () (H o не противоречит наблюдениям X 1 , X 2 ,..., X n ) или θ n Г 1 () принимает- ся или не принимается гипотеза H o Гипотеза H o : x=x o называется простой; во всех остальных случаях она на- зывается сложной. 2. Построение статистического критерия. Принцип отношения правдо- подобия Рассмотрим общий принцип построения наилучших статистических крите- риев, т.е. критериев, обеспечивающих наибольшую мощность 1- =max (1) при заданном уровне значимости≤ о : Рис. 1. Проверка гипотезы без альтернатив с двумя критическими облас- тями Рис. 2. Проверка гипотезы c альтернативой 99 В качестве критической статистики используем отношение правдоподобия θ n =L H1 (X 1 , X 2 ,..., X n ¦ θ )/L H0 (X 1 , X 2 ,..., X n ¦ θ )= =L(X 1 , X 2 ,..., X n ¦ θ 1 )/L(X 1 , X 2 ,..., X n ¦ θ o ), (2) где L H0 , L H1 - функции правдоподобия X 1 , X 2 ,..., X n , определенные для гипотез, со- ответственно, H o : θ = θ o и H 1 : θ = θ 1 . (3) Достаточно понятно, что чем больше наблюдения соответствуют H o , тем больше будет значение L(X 1 , X 2 ,..., X n ¦ θ o ) и тем меньше будет величина θ n . Если θ n (X 1 ,X 2 ,..., X n )> θ , где θ - %-ая точка, определяемая из таблиц распределения f(θ n ) для уровня значимости , то гипотеза H o отвергается; в противном случае H o не отвергается. При этом вероятность ошибки "не признать" θ = θ o ( в то время, когда он та- ковым является) равна ( , ) т а z dz Известно, что в соответствии с леммой Неймана-Пирсона, критерий отно- шения правдоподобия (ОП) является наиболее мощным среди всех возможных критериев. Пример. ] L(X 1 , X 2 ,..., X n ; a j , 2 )= =[(2 ) n/2 n ] -1 exp{-(2 2 ) -1 n i 1 (X i -a j ) 2 }, j=0,1. Тогда критерий ОП имеет вид: θ n =L H1 /L Ho = exp{-(2 2 ) -1 n i 1 (X i -a 1 ) 2 -(X i -a o ) 2 } θ ,. Последнее выражение простым преобразованием приводится к соотноше- нию ˆ n ≥a o + Ф -1 (θ ) /n 1/2 , где Ф -1 (θ ) - θ -ая точка стандартного нормального распределенияN {0, 1}, θ 1- - (1-2 ) % -ая точка. Получившееся правило проверки гипотезы не зависит от альтернативного значения параметра a 1 и поэтому верен для a 1 >a o . Такой критерий называется равномерно наиболее мощным. В ряде случаев вместо критерия МП оказывается более удобным использо- вать критерий логарифма ОП: 1 2 0 1 2 ( , ,..., ) ˆ 2 ln{ } ( , ,..., ) n n n L X X X L X X X , (4) где ˆ - МП-оценка параметра θ по выборке X 1 , X 2 ,..., X n При общих (для ММП) условиях регулярности f{X; θ} и n величина 2 ˆ n n -распределению с n степенями свободы. Заметим, что для нормального распределения оценка МП параметра θ o представляет собой среднее значение n . Тогда 100 n = n i 1 -2 [ n i 1 (X i - θ o ) 2 - n i 1 (X i - n ) 2 ] ]= n -2 (X i - θ o ) 2 Поскольку XiN{ θ o ; 2 /n}, 2 ˆ n n 3. Основные типы гипотез, проверяемых в ходе статистической обра- ботки наблюдений 3.1. Гипотезы согласия. При обработке последовательностей наблюдений X 1 , X 2 ,..., X n очень важно понять механизм их формирования, т.е. подобрать мо- дельную функцию распределения F mod (X), адекватно описывающую истинное рас- пределение F(X). Это приводит к задаче проверки гипотезы вида H o : F(X)=F mod (X). (4) F mod (X) может быть задана однозначно или с точностью до принадлежности некоторому параметрическому семейству {F mod (X, x)}. Проверка гипотез (4) осуществляется с помощью критериев согласия и опирается на некоторую меру [F mod (X), ^ F n 0(X)] между гипотетическим и эмпири- ческим ^ F n (X) распределениями. |