Формула шеннона в excel

Формула шеннона в excel

Вычисление количества энтропии по таблице вероятностей с помощью формулы Шеннона.

Энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P: , т. е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье «Математическая теория связи».

Минус используется из-за того, что логарифм числа меньшего единицы, величина отрицательная. Но так как
,
то формулу можно записать еще в виде

интерпретируется как частное количество информации, получаемое в случае реализации i-ого варианта ( ).

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

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

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

Формулу для вычисления количества информации в случае различных вероятностей событий предложил К. Шеннон в 1948 году. В этом случае количество информации определяется по формуле:

(2.2)

где I — количество информации;
N — количество возможных событий;
рi — вероятность i-го события.

Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:

Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле (2.2):

I = -(l/2 log2l/2 + l/4 log2l/4 + l/8 log2l/8 + l/8 log2l/8) = (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита.

Этот подход к определению количества информации называется вероятностным.

Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (pi= 1/N), величину количества информации I можно рассчитать по формуле:

Читайте также:  Как поставить пароль на зип архив
(2.3)

По формуле (2.3) можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:

I = log24 = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.

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

Выбор оптимальной стратегии в игре "Угадай число". На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй — должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).

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

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

Таблица 2.1. Информационная модель игры "Угадай число"
Вопрос второго участника Ответ первого участника Неопределенность знаний (количество возможных событий) Полученное количество информации
16
Число больше 8? Нет 8 1 бит
Число больше 4? Нет 4 1 бит
Число больше 2? Да 2 1 бит
Число 3? Да 1 1 бит

1.3. Вычислить с помощью электронного калькулятора количество информации, которое будет получено:

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

1.4. Вероятность первого события составляет 0,5, а второго и третьего — 0,25. Какое количество информации мы получим после реализации одного из них?

1.5. Какое количество информации получит второй игрок в игре "Угадай число" при оптимальной стратегии, если первый игрок загадал число: от 1 до 64? От 1 до 128?

Формула Шеннона (Информационная энтропия)

Данная формула также как и формула Хартли, в информатике применяется для высчитывания общего количество информации при различных вероятностях.

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

Для других же равновероятных событий, таких как подброс монеты (вероятность того что выпадет орёл или решка будет одинаковой — 50 %) используется формула Хартли.

Интересуешься информатикой? Читайте нашу новую лекцию системы счисления

Теперь, давайте рассмотрим применение этой формулы на конкретном примере:

В каком сообщений содержится меньше всего информации (Считайте в битах):

  1. Василий сьел 6 конфет, из них 2 было барбариски.
  2. В комьютере 10 папок, нужный файл нашелся в 9 папке.
  3. Баба Люда сделала 4 пирога с мясом и 4 пирога с капустой. Григорий сьел 2 пирога.
  4. В Африке 200 дней сухая погода, а 165 дней льют муссоны. африканец охотился 40 дней в году.

В этой задаче обратим внимания что 1,2 и 3 варианты, эти варианты считать легко, так как события равновероятны. И для этого мы будем использовать формулу Хартли I = log2N (рис.1) А вот с 4 пунком где видно, что распределение дней не равномерно(перевес в сторону сухой погоды), что же тогда нам в этом случае делать? Для таких событий и используется формула Шеннона или информационной энтропии: I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN), (рис.3)

  • I — количество информации
  • p — вероятность того что это события случиться
Читайте также:  Ноутбук asus rog strix scar edition gl703gm

Далее чтобы узнать p необходимо поделить количество интересующих нас событий на общее количество возможных вариантов.

Интересующие нас события в нашей задаче это

  1. Было две барбариски из шести (2/6)
  2. Была одна папка в которой нашлась нужный файл по отношению к общему количеству (1/10)
  3. Всего пирогов было восемь из которых сьедено григорием два (2/8)
  4. и последнее сорок дней охоты по отношению к двести засушливым дням и сорок дней охоты к сто шестидесяти пяти дождливым дням. (40/200) + (40/165)

таким образом получаем что:

Где K — это интересующие нас событие, а N общее количество этих событий, также чтобы проверить себя вероятность того или иного события не может быть больше единицы. (потому что вероятных событий всегда меньше)

Вернемся к нашей задаче и посчитаем сколько информации содержится.

Кстате, при подсчёте логарифма удобно использовать сайт — https://planetcalc.ru/419/#

  • Для первого случая — 2/6 = 0,33 = и далее Log2 0,33 = 1.599 бит
  • Для второго случая — 1/10 = 0,10 Log2 0,10 = 3.322 бит
  • Для третьего — 2/8 = 0,25 = Log2 0,25 = 2 бит
  • Для четвертого — 40/200 + 40/165 = 0.2 и 0,24 соотвественно, далее считаем по формуле -(0,2 * log2 0,2) +-(o.24 * log2 0.24) = 0.95856 бит

Таким образом ответ для нашей задачи получился 4.

Вот таким образом и используется формула Шеннона при подсчёте информации. Если у вас есть какие либо вопросы, или что то Вам не понятно можете задать вопросы в комментариях. (отвечаю оперативно)

Ссылка на основную публикацию
Adblock detector