Презентация Компьютерный и интеллектуальный анализ данных. Теория вероятностей онлайн

Содержание слайда: Введение в компьютерный и интеллектуальный анализ данных

Содержание слайда: 0. Введение. Общие сведения. Объем курса – 18 часов лекции 16 часов лабораторные занятия Лабораторные занятия проводятся в классе ПЭВМ и выполняются в среде пакета R Форма отчетности – зачет Лектор – Воротницкая Татьяна Ивановна

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

Содержание слайда: 0. Введение. Основные разделы Статистический анализ данных (Statistical Data Analysis – SDA) Интеллектуальный анализ данных (Data Mining или Knowledge Discovery in Database - KDD) Анализ больших данных (Big Data Analysis - BDA)

Содержание слайда: 0. Введение. Литература. Ширяев А.Н. Вероятность. Москва, 1980. Вентцель Е.С. Теория вероятностей: Учеб. для вузов. — 6-е изд. стер. — М.: Высш. шк., 1999. Колмогоров А.Н. Основные понятия теории вероятностей. Москва, 1936. Хацкевич Г.А. Статистика. Описательный подход / Г.А. Хацкевич. – Минск: НИУП. – 2002. А. А. Барсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод Технологии анализа данных. Data Mining, Visual Mining, Text Mining, OLAP Елисеева И.И. Общая теория статистики / И.И. Елисеева, М.М. Юзбашев. – М. – 1996. Тюрин Ю.Н. Анализ данных на компьютере / Ю.Н. Тюрин, А.А. Макаров Torgo L. Data Mining with R: learning by case studies / L. Torgo - LIACC-FEP, University of Porto. – 2003.

Содержание слайда: 1. Основные понятия теории вероятностей

Содержание слайда: 1. Основные понятия теории вероятностей Примеры случайных явлений

Содержание слайда: 1. Основные понятия теории вероятностей Примеры случайных явлений

Содержание слайда: 1. Основные понятия теории вероятностей Примеры случайных явлений

Содержание слайда: 1. Основные понятия теории вероятностей Какие закономерности изучает теория вероятностей

Содержание слайда: 1. Основные понятия теории вероятностей Событие

Содержание слайда: 1. Основные понятия теории вероятностей Статистическая устойчивость

Содержание слайда: 1. Основные понятия теории вероятностей Статистическая устойчивость

Содержание слайда: 1. Основные понятия теории вероятностей. Пространство элементарных исходов. Пространством элементарных событий  называется множество, содержащее все возможные случайные результаты данного эксперимента, из которых в эксперименте происходит ровно один. Элементы этого множества называют элементарными исходами .  Событиями будем называть подмножества множества . Говорят, что в результате эксперимента произошло событие А, если в эксперименте произошел один из элементарных исходов, входящих в множество А.

Содержание слайда: 1. Основные понятия теории вероятностей. Пространство элементарных исходов. Пример: однократное подбрасывание игральной кости. Пространством элементарных событий  = {1,2,3,4,5,6}. Элементарное событие – число выпавших очков Примеры событий: А={1,2} – выпало одно или два очка; B={1,3,5} – выпало нечетное число очков. Достоверным называется событие, которое обязательно происходит в результате эксперимента, т.е. единственное событие, включающее все элементарные исходы Невозможным называется событие, которое не может произойти в результате эксперимента, т.е. событие не содержащее ни одного элементарного исхода – пустое множество.

Содержание слайда: 1. Основные понятия теории вероятностей. Вероятность на дискретном пространстве элементарных исходов Пространство элементарных событий  назовем дискретным, если оно конечно либо счётно. Чтобы определить вероятность любого события A на дискретном пространстве элементарных событий, достаточно присвоить вероятность каждому элементарному исходу i. Вероятность события A

Содержание слайда: 1. Основные понятия теории вероятностей. Свойства вероятности на дискретном пространстве элементарных исходов ; Если А и В несовместны(наступление события А не зависит от наступления события В и наоборот), то В общем случае Если АВ, то Когда А=, Р(А)=0.

Содержание слайда: 1. Основные понятия теории вероятностей. Классическое определение вероятности Пусть пространство элементарных событий состоит из конечного числа N элементов: ={1, 2, …, N} и все элементарные события равновозможны. Тогда вероятность любого из этих событий принимается равной 1/N. Если событие А состоит из k элементарных равновозможных исходов А={}, то вероятность этого события равна отношению k/N. Пример 1. В урне имеется 10 шаров: 3 белых и 7 синих. Из урны наугад вынимается один шар. Какова вероятность, что этот шар белый? (3/10).

Содержание слайда: 1. Основные понятия теории вероятностей. Классическое определение вероятности Пример 2. В партии из 50 деталей 5 нестандартных. Определить вероятность того, что среди выбранных наудачу для проверки 6-ти деталей 2 окажутся нестандартными. Решение. A={из 6 выбранных наудачу деталей 2 - нестандартные}; Общее число всех возможностей выбора 6 деталей из 50 равно . Число способов выбрать 2 нестандартные детали из 5 нестандартных, находящихся в партии равно . Каждому такому выбору соответствует способов выбора стандартных деталей из 45, имеющихся в партии. По правилу произведения число случаев, благоприятствующих A равно Тогда .

Содержание слайда: 1. Основные понятия теории вероятностей. Вероятность и частота Формула для непосредственного подсчета вероятностей, исходя из классического определения, верна только для равновозможных исходов. В случае неравновозможных исходов (несимметричная игральная кость и т.п.) вероятность события p(A) необходимо определить по-другому. Если произведена серия из n опытов, в каждом из которых событие A произошло m раз, то частость события . Теорема Бернулли

Содержание слайда: 1. Основные понятия теории вероятностей. Геометрическое определение вероятности Для испытаний с бесконечным числом исходов классическое определение вероятности неприменимо. Тогда вводят понятие геометрической вероятности, как вероятности попадания точки в область (отрезок, часть плоскости, часть n-мерного пространства). Пример: случайное бросание точки в область G, причем все точки этой области равноправны. Событие A – попадание точки в область g. Геометрической вероятностью события A называют

Содержание слайда: 1. Основные понятия теории вероятностей. Геометрическое определение вероятности Пример. Два студента A и B условились встретиться в определенном месте во время перерыва между 13 ч и 13 ч 50 мин. Пришедший первым ждет другого в течение 10 мин., после чего уходит. Чему равна вероятность их встречи, если приход каждого из них в течение указанных 50 минут может произойти наудачу и моменты прихода независимы?

Содержание слайда: 1. Основные понятия теории вероятностей. Условная вероятность Пример. Игральная кость подбрасывается один раз. Известно, что выпало более трех очков. Какова при этом вероятность, что выпало четное число очков? Решение а)  = {4,5,6}, A={4,6}. p(A)=2/3. б)  = {1,2,3,4,5,6}; B = {4,5,6}. Вопрос: какова вероятность того, что при осуществлении B происходит А ={4,6}: p(A|B) ? p(A|B) = p(A ∩ B)/P(B) =(2/6)/(3/6)=2/3. Условной вероятностью события A по отношению к событию B p(A|B) называют вероятность события A, найденную при условии, что произошло событие B

Содержание слайда: 1. Основные понятия теории вероятностей. Правило умножения вероятностей событий Правило умножения вероятностей: Вероятность произведения двух событий равна произведению вероятности одного из этих событий на условную вероятность другого, найденную в предположении, что первое событие произошло, т.е. p(AB)=p(A)p(B|A) или p(AB)=p(B)p(A|B) События A и B называются независимыми, если p(A|B) = p(A) и p(B|A) = p(B). Для независимых событий p(AB)=p(A)p(B). Пример. В первом ящике 2 белых и 10 красных шаров, во втором ящике – 8 белых и 4 красных. Из каждого ящика вынули по шару. Какова вероятность, что оба шара белые? Решение. A={появление белого шара из первого ящика}, B={появление белого шара из второго ящика}. A и B – независимы. p(AB)=p(A)p(B)=2/12  8/12 = 1/9

Содержание слайда: 1. Основные понятия теории вероятностей. Формула полной вероятности Вероятность p(A) появления события A, которое может произойти только совместно с одним из событий B1, B2, …. Bn , образующих полную группу попарно несовместных событий: вычисляется по формуле полной вероятности: События Bi обычно называют гипотезами, a числа p(Bi) – вероятностями гипотез.

Содержание слайда: 1. Основные понятия теории вероятностей. Формула полной вероятности Пример. Имеется четыре одинаковых ящика с электрическими лампочками, причем первый ящик содержит 10 исправных и 2 бракованные лампочки, второй и третий ящики содержат по 5 исправных и по 5 бракованных лампочек, а четвертый ящик содержит только 10 исправных лампочек. Наудачу выбирается один ящик и из него одна лампочка. Какова вероятность того, что эта лампочка окажется исправной? Решение. Событие A={выбор исправной лампочки}. Гипотезы Bi={выбор i-го ящика}. События Bi образуют полную группу событий, p(Bi)=1/4. p(A|B1)=10/12=5/6; p(A|B2)= p(A|B3)=5/10=1/2; p(A|B4)=10/10=1. Тогда по формуле полной вероятности p(A)=p(B1)p(A|B1)+ p(B2)p(A|B2)+ p(B3)p(A|B3)+ p(B4)p(A|B4) = 1/4 5/6+ 1/4 1/2+ 1/4 1/2+ 1/4 1=17/24

Содержание слайда: 1. Основные понятия теории вероятностей. Формула Байеса Условная вероятность гипотезы Bi в предположении, что событие A уже имеет место, определяется по формуле Байеса: Пример. Три организации представили в контрольное управление счета для выборочной проверки: первая 15 счетов, вторая – 10, третья – 25. Вероятности правильного оформления счетов у этих организаций соответственно таковы: 0,9; 0,8; 0,85. Был выбран один счет, и он оказался правильным. Определить вероятность того, что этот счет принадлежит второй организации. Решение. Событие A={представлен правильно оформленный счет}, гипотезы Bi={правильно оформленный счет представила i-я организация}. События Bi образуют полную группу несовместных событий, при этом p(B1)=15/50=0,3, p(B2)=10/50=0,2, p(B3)=25/50=0,5. По условию p(A|B1)=0,9; p(A|B2)=0,8; p(A|B3)=0,85. По формуле полной вероятности p(A)=0,30,9+0,20,8+0,50,85=0,855. По формуле Байеса p(B2|A)=p(B2)p(A|B2)/p(A)=0,20,8/0,855 ≈0,19

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

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

Содержание слайда: 2. Случайные величины и их характеристики Функции распределения случайных величин Функцией распределения (или интегральной функцией распределения) случайной величины X называется функция F(x), которая для любого числа x∈ R равна вероятности события, состоящего в том, что случайная величина X примет значение, меньшее чем заданное х (аргумент функции).

Содержание слайда: 2. Случайные величины и их характеристики Свойства функции распределения F(x) – неубывающая функция своего аргумента, т.е. если x2>x1, то F(x2)>F(x1) F(x) – непрерывна слева в любой точке:

Содержание слайда: 2. Случайные величины и их характеристики Плотность распределения непрерывной случайной величины Плотностью распределения непрерывной случайной величины называется функция

Содержание слайда: 2. Случайные величины и их характеристики Дискретное равномерное распределение

Содержание слайда: 2. Случайные величины и их характеристики Непрерывное равномерное распределение

Содержание слайда: 2. Случайные величины и их характеристики Основные характеристики случайных величин Математическое ожидание (среднее значение): ; ; Для непрерывной случайной величины

Содержание слайда: 2. Случайные величины и их характеристики Основные характеристики случайных величин Дисперсия Среднее квадратичное отклонение

Содержание слайда: 2. Случайные величины и их характеристики Нормальное распределение

Содержание слайда: 2. Случайные величины и их характеристики Нормальное распределение

Содержание слайда: 2. Случайные величины и их характеристики Понятие случайного процесса Случайный процесс – семейство случайных величин , заданных на вероятностном пространстве и некотором промежутке T. Если множество T дискретно, то X(t) образуют случайную последовательность. Стационарный процесс – все конечномерные характеристики последовательности инвариантны относительно сдвигов по времени. Если при определении характеристик процесса усреднение по статистическому ансамблю можно заменить усреднением по времени, процесс называется эргодическим. Случайный процесс называется Марковским, если величины X(t) в любой момент времени принимают значения в конечном или счетном множестве S и состояние, которое примет система в момент при заданных состояниях в предшествующие моменты времени, зависит только от одного ее состояния, предшествовавшего этому моменту.

Содержание слайда: 2. Случайные величины и их характеристики Основные задачи статистики Предмет математической статистики – разработка методов регистрации, описания и анализа статистических экспериментальных данных, получаемых в результате наблюдения массовых случайных явлений. Основные задачи математической статистики: Задача определения закона распределения случайной величины (или системы случайных величин) по статистическим данным Задача проверки правдоподобия гипотез Задача нахождения неизвестных параметров распределения

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

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейный конгруэнтный (рекурсивный) метод (Lehmer, 1949): m > 0, 0 < a ≤ m, 0 ≤ c ≤ m, начальное значение X0: 0 < X0 ≤ m. Модуль m должен быть достаточно большим, т.к. период не больше m. Удобно связать m с длиной слова компьютера и использовать m=2e – 1, либо m=2e + 1 для e-разрядной машины, а еще лучше – m наибольшее простое, меньшее 2e. Длина периода равна m в следующем случае: c и m – взаимно простые числа, b = a – 1 кратно p для любого p, являющегося множителем m, b кратно 4, если m кратно 4.

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Генератор MS FORTRAN: m = 231-1, c=0, a=48271 Xn+1 = 48271Xn mod (231-1) Генератор Парка-Миллера: m = 231-1, c=0, a=75 Xn+1 = 75Xn mod (231-1) Нелинейные генераторы: Xn+1 = (aXn3 + bXn2 + cXn +d)mod m Суперпозиция нескольких конгруэнтных генераторов посредством нелинейной функции.

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Алгоритм работы линейного регистра с обратной связью: Прочитать бит из ячейки L-1 и направить его в выходную последовательность Вычислить новое значение для ячейки 0 с помощью заданной функции обратной связи F, используя текущие значения ячеек Выполнить сдвиг вправо (содержимое каждой i-й ячейки перемещается в ячейку i+1) Записать в ячейку 0 бит, ранее вычисленный функцией обратной связи F Чаще всего, … Периодичность: . Для того, чтобы период был максимальным, необходимо (но не достаточно), чтобы число отводов было четным, их номера, взятые все вместе (не попарно) были взаимно простыми.

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей XOR - Исключающее ИЛИ (сложение по модулю 2);

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Линейные регистры с обратной связью

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Недостатки генераторов псевдослучайных чисел: Конечный период Последовательные значения не являются независимыми. Некоторые биты «менее случайны», чем другие. Неравномерное одномерное распределение. Обратимость.

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

Содержание слайда: 2. Случайные величины и их характеристики Генерация псевдослучайных последовательностей Примеры тестов генераторов псевдослучайных последовательностей Частотный тест (равновероятность 0 и 1 в последовательности) Блочный тест на частоту (последовательность разбивается на блоки длиной M бит и для каждого рассчитывается, насколько вероятность появления 1 близка к ½) Тест распределения на плоскости. Последовательность чисел группируется парами, которые рассматриваются как координаты на двумерном графике. Отображение этих точек на плоскости является результатом теста. Для случайной последовательности расположение точек на плоскости будет хаотичным, а при росте выборки плоскость полностью будет заполнена точками. Признаком неслучайной последовательности является наличие на полученном изображении «узоров» (явно выраженных вертикальных либо горизонтальных линий, периодических рисунков и т.д.).