Вычисление энтропии дискретной случайной величины

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 

Факультет прикладной математики и  информатики

 

 

ХВОРОВ  НИКИТА ВЛАДИМИРОВИЧ

 

Вычисление  энтропии дискретной случайной величины

 

Лабораторная  работа №1

Студента 3 курса 9 группы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Преподаватель                                      

Вечерко Егор Валентинович

 

 

 

 

 

 

Минск 2012

1. Код программы.

import java.awt.Graphics2D;

import java.awt.geom.Rectangle2D;

import java.awt.image.BufferedImage;

import java.io.File;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Map.Entry;

import java.util.Random;

 

import javax.imageio.ImageIO;

 

import org.apache.commons.io.*;

import org.jfree.chart.ChartFactory;

import org.jfree.chart.JFreeChart;

import org.jfree.chart.plot.PlotOrientation;

import org.jfree.data.category.DefaultCategoryDataset;

 

public class InformationTheory {

    private static List<String> lines = new ArrayList<String>();

    private static List<Double> possibilities = new ArrayList<Double>();

    private static List<Double> generation = new ArrayList<Double>();

    private static LinkedHashMap<Integer, Double> variations = new LinkedHashMap<Integer, Double>();

 

    private static int sizeOfSet;

    private static int sizeOfSequence;

    private static double entropyByData;

 

    private static final int k = 10000;

    private static final int[] sizes = { 350, 500, 650, 800, 950, 1100, 1250, 1400, 1550, 1700, 1850, 2000 };

    private static final String inputFileName = "input.txt";

    private static final String outputFileName = "output.txt";

    private static final String fileName1 = "BarChart.png";

    private static final String fileName2 = "Variation.png";

 

    private static enum Type {

        BAR, LINE

    };

 

    public static void main(String[] args) {

        readData();

        doTask1();

        doTask2();

    }

 

    private static void readData() {

        try {

            lines = FileUtils.readLines(new File(inputFileName));

            generation.add(Double.parseDouble(lines.get(2)));

            possibilities.add(Double.parseDouble(lines.get(2)));

            sizeOfSet = Integer.parseInt(lines.get(0));

            sizeOfSequence = Integer.parseInt(lines.get(1));

            for (int i = 3; i < sizeOfSet + 2; i++) {

                generation.add(Double.parseDouble(lines.get(i)) + generation.get(i - 3));

                possibilities.add(Double.parseDouble(lines.get(i)));

            }

            entropyByData = calculateEntropy(possibilities);

        } catch (IOException ex) {

            System.err.println(ex.toString());

        }

    }

 

    private static void doTask1() {

        List<Integer> sequence = generateSequence();

        List<Double> frequences = getFrequences(sequence);

        double entropyBySequence = calculateEntropy(frequences);

        try {

            FileUtils.writeStringToFile(new File(outputFileName), entropyByData + "\r\n" + entropyBySequence);

        } catch (IOException ex) {

            System.err.println(ex.toString());

        }

        LinkedHashMap<Integer, Double> frequencesMap = new LinkedHashMap<Integer, Double>();

        for (int i = 0; i < frequences.size(); i++) {

            frequencesMap.put(i, frequences.get(i));

        }

        buildChart(frequencesMap, Type.BAR, "Frequences", "i", "p", fileName1);

    }

 

    private static void doTask2() {

        for (int size : sizes) {

            sizeOfSequence = size;

            double variation = 0;

            for (int i = 0; i < k; i++) {

                List<Integer> sequence = generateSequence();

                List<Double> frequences = getFrequences(sequence);

                double entropy = calculateEntropy(frequences);

                variation += Math.pow(entropy - entropyByData, 2);

            }

            variation /= k;

            variations.put(sizeOfSequence, variation);

        }

        buildChart(variations, Type.LINE, "Variation chart", "n", "V", fileName2);

    }

 

    private static List<Integer> generateSequence() {

        Random random = new Random();

        List<Integer> sequence = new ArrayList<Integer>();

        for (int i = 0; i < sizeOfSequence; i++) {

            Double next = random.nextDouble();

            for (int j = 0; j < sizeOfSet; j++) {

                if (next < generation.get(j)) {

                    sequence.add(j);

                    break;

                }

            }

        }

        return sequence;

    }

 

    private static List<Double> getFrequences(List<Integer> sequence) {

        List<Double> frequences = new ArrayList<Double>();

        for (int i = 0; i < sizeOfSet; i++) {

            frequences.add(1.0 * Collections.frequency(sequence, i) / sizeOfSequence);

        }

        return frequences;

    }

 

    private static double calculateEntropy(List<Double> frequences) {

        double entropy = 0;

        for (Double frequence : frequences) {

            entropy += -frequence * Math.log(frequence) / Math.log(2.0);

        }

        return entropy;

    }

 

    private static BufferedImage createImage(JFreeChart chart) {

        BufferedImage result = new BufferedImage(600, 400, BufferedImage.TYPE_INT_RGB);

        Graphics2D g = result.createGraphics();

        chart.draw(g, new Rectangle2D.Double(0, 0, 600, 400));

        g.dispose();

        return result;

    }

 

    private static void buildChart(LinkedHashMap<Integer, Double> frequences, Type type, String name,

                    String xAxisLabel, String yAxisLabel, String fileName) {

        DefaultCategoryDataset dataset = new DefaultCategoryDataset();

        for (Entry<Integer, Double> entry : frequences.entrySet()) {

            dataset.addValue(entry.getValue(), yAxisLabel, String.valueOf(entry.getKey()));

        }

        JFreeChart chart;

        if (type.equals(Type.LINE)) {

            chart = ChartFactory.createLineChart(name, xAxisLabel, yAxisLabel, dataset, PlotOrientation.VERTICAL,

                            false, false, false);

        } else {

            chart = ChartFactory.createBarChart3D(name, xAxisLabel, yAxisLabel, dataset, PlotOrientation.VERTICAL,

                            false, false, false);

        }

        BufferedImage image = createImage(chart);

        try {

            ImageIO.write(image, "png", new File(fileName));

        } catch (IOException ex) {

            System.err.println(ex.toString());

        }

    }

}

2. Постановка задачи и обозначения.

Дан дискретный закон распределения  случайной величины. Во входном файле  подается – мощность множества различных исходов , длина генерируемых последовательностей и значения вероятностей .

 

Задача  №1: вычислить теоритическую энтропию:

 

 

сгенерировать последовательность по данным из файла и вычислить эмпирическую энтропию:

 

 

 

где – частота встречаемости в сгенерированной последовательности, и вывести оба результата в выходной файл, а также построить гистограмму полученных частот.

 

Задача  №2: для различных длин последовательностей по этому же закону распределения сгенерировать последовательностей и вычислить значения вариации энтропии для каждой длины , по формуле:

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Примеры.

№1.

Входные данные:

4

500

0.1

0.4

0.2

0.3

Выходные данные:

Теоритическая энтропия: 1.8464393446710154

Эмпирическая  энтропия: 1.855269765003367

 

 

 

 

 

 

№2.

Входные данные:

7

500

0.05

0.1

0.2

0.25

0.2

0.15

0.05

Выходные данные:

Теоритическая энтропия: 2.6037016960573482

Эмпирическая  энтропия: 2.556668787692616

 

 

 

№3.

Входные данные:

5

1000

0.2

0.2

0.2

0.2

0.2

Выходные данные:

Теоритическая энтропия: 2.3219280948873626

Эмпирическая  энтропия: 2.320170264349863

 

 

 

 

 

 

 

№4.

Входные данные:

2

1000

0.2

0.8

Выходные данные:

Теоритическая энтропия: 0.7219280948873623

Эмпирическая  энтропия: 0.6951533369561015

 

 

 

 

 

 

 

 

№5.

Входные данные:

3

100

0.5

0.25

0.25

Выходные данные:

Теоритическая энтропия: 1.5

Эмпирическая  энтропия: 1.4854752972273344