Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Архив1 / doc200 / лаба4-андрик

.doc
Скачиваний:
17
Добавлен:
01.08.2013
Размер:
82.43 Кб
Скачать

Задание:

Реализовать on-line алгоритм обучения конъюнктивной концепции.

Описание алгоритма:

Пусть X – вектор признаков, размером N, элементы которого принимают значения [0,1]. Последний элемент вектора – это некий результат, который должен получиться у «обучающейся» программы, на основе данных предыдущих элементов.

Пусть L – вектор размера 2*N, все элементы которого сначала равны 1. Вектор L определяет, какие элементы из вектора X будут использоваться для прогнозирования результата. В нем ‘1' месте (2*i-1) указывает на то, что в прогнозе участвует x(i), '0' означает, что x(i) не используется в прогнозирующей конъюнкции. Далее, '1' на месте (2*i) указывает на то, что в прогнозе участвует отрицание ~x(i), '0' означает, что ~x(i) не используется в прогнозирующей конъюнкции.

Предсказание вычисляется по формуле:

С(x) = С (x1,..,xn) =

[x1|(1-L(1))]*[(1-x1)|(1-L(2))]*…*[xn|(1-L(2*n-1))]*[(1-xn)|(1-L(2*n))],

где Xn – элементы вектора X, Ln – элементы вектора L.

В случае, если предсказание не совпало с ожидаемым результатом, из рассмотрения исключаются все элементы вектора X, принявшие нулевые значения.

Докажем, что алгоритм завершит работу с не более чем (N+1) ошибок.

Ошибка может возникнуть, только если ожидаемое значение равно 1.

При первой ошибке, алгоритм исключит из вектора L N литер, т.к. в начальном состоянии вектор L целиком состоит из единиц и, следовательно, формула C содержит N нулевых значений. Т.е. после первой ошибки, число теоретически ошибочных литер равно N. Следовательно, общее число ошибок никогда не превысит N+1.

Пример работы программы:

Исходные данные:

1 1 1 0 1 0 0 0

1 1 0 0 1 1 1 0

1 0 1 0 0 1 1 0

0 0 1 1 1 0 1 0

1 1 1 0 0 0 0 0

0 0 0 1 0 1 0 1

0 1 1 1 1 0 1 0

0 1 0 0 1 1 1 0

0 1 0 1 0 0 1 0

1 0 0 1 1 0 1 0

1 0 0 0 0 1 1 0

0 1 0 1 0 0 0 1

0 1 1 1 1 1 1 0

0 1 0 0 0 0 1 0

0 1 1 1 0 1 1 0

0 1 0 1 1 1 0 1

0 0 1 1 0 1 0 1

1 0 0 1 0 1 0 1

1 0 1 0 0 0 1 0

0 1 1 0 0 1 1 0

1 1 1 0 1 0 1 0

1 1 1 0 0 1 0 0

0 0 0 0 0 1 0 0

1 1 1 0 0 0 1 0

0 1 1 0 0 1 0 0

0 0 1 0 0 1 1 0

0 0 0 1 0 0 1 0

1 0 0 0 1 1 0 0

1 1 0 1 0 0 1 0

1 0 0 0 1 1 1 0

1 1 0 1 1 1 0 1

0 0 0 1 0 0 0 1

0 0 1 1 1 1 0 1

1 0 0 0 0 1 0 0

0 1 1 0 1 1 0 0

1 1 0 1 0 0 0 1

0 1 0 0 1 0 0 0

0 0 1 1 0 0 0 1

0 1 0 0 1 1 0 0

0 1 0 1 0 1 0 1

0 1 1 1 0 1 0 1

1 0 1 0 1 0 1 0

1 0 1 0 0 0 0 0

0 0 1 0 0 0 1 0

0 1 0 1 1 0 0 1

0 1 0 1 1 0 1 0

0 1 1 0 0 0 0 0

0 0 1 0 1 1 0 0

1 1 0 0 1 1 0 0

0 1 1 1 1 1 0 1

1 1 1 1 1 0 0 1

1 1 1 1 0 1 1 0

1 1 1 1 0 0 1 0

1 1 1 1 0 1 0 1

1 0 1 1 0 0 1 0

0 1 1 1 1 0 0 1

1 1 0 1 1 0 1 0

0 0 0 1 1 1 0 1

0 0 0 0 0 1 1 0

0 1 1 0 1 0 0 0

1 0 0 1 1 1 1 0

0 1 0 0 0 0 0 0

1 1 0 1 1 0 0 1

1 0 1 1 1 1 1 0

1 1 1 1 1 0 1 0

0 1 0 0 0 1 0 0

0 1 1 0 1 1 1 0

0 0 0 0 1 1 0 0

1 1 1 1 1 1 0 1

0 1 1 0 0 0 1 0

1 0 1 1 0 1 1 0

0 0 1 1 1 1 1 0

1 1 1 0 1 1 1 0

1 0 1 1 1 0 0 1

1 1 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0

1 0 0 1 0 0 1 0

0 0 0 0 1 1 1 0

0 0 0 0 0 0 1 0

1 1 1 1 0 0 0 1

0 0 1 0 0 1 0 0

0 0 0 1 1 0 1 0

1 0 0 0 0 0 0 0

1 0 1 1 0 1 0 1

1 0 1 0 1 1 0 0

0 1 0 1 1 1 1 0

0 1 1 0 1 0 1 0

0 1 1 1 0 0 0 1

1 1 0 0 1 0 0 0

0 0 0 1 0 1 1 0

1 0 0 1 0 1 1 0

0 0 1 1 1 0 0 1

1 1 0 0 1 0 1 0

1 0 1 1 0 0 0 1

1 1 0 1 0 1 1 0

1 1 0 1 1 1 1 0

1 0 1 1 1 1 0 1

1 0 0 0 1 0 1 0

1 0 1 0 1 1 1 0

1 1 1 0 0 1 1 0

0 1 0 0 1 0 1 0

0 0 0 0 1 0 1 0

1 1 0 0 0 1 1 0

0 0 1 1 0 1 1 0

1 0 1 0 1 0 0 0

1 0 1 0 0 1 0 0

1 0 0 1 1 1 0 1

1 1 1 0 1 1 0 0

0 1 0 0 0 1 1 0

0 0 1 1 0 0 1 0

0 0 1 0 1 0 1 0

1 1 1 1 1 1 1 0

1 1 0 1 0 1 0 1

0 1 1 1 0 0 1 0

1 1 0 0 0 0 0 0

1 1 0 0 0 0 1 0

1 0 0 1 0 0 0 1

1 0 0 0 1 0 0 0

0 0 1 0 1 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 1

0 1 0 1 0 1 1 0

1 0 1 1 1 0 1 0

0 0 1 0 1 1 1 0

1 0 0 1 1 0 0 1

0 0 0 1 1 1 1 0

1 0 0 0 0 0 1 0

Результат работы программы:

Пример № 1

Вектор признаков Х = (1, 1, 1, 0, 1, 0, 0)

Ожидаемый результат: 0

Ошибок: 0

Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Пример № 2

Вектор признаков Х = (1, 1, 0, 0, 1, 1, 1)

Ожидаемый результат: 0

Ошибок: 0

Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Пример № 3

Вектор признаков Х = (1, 0, 1, 0, 0, 1, 1)

Ожидаемый результат: 0

Ошибок: 0

Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Пример № 4

Вектор признаков Х = (0, 0, 1, 1, 1, 0, 1)

Ожидаемый результат: 0

Ошибок: 0

Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Пример № 5

Вектор признаков Х = (1, 1, 1, 0, 0, 0, 0)

Ожидаемый результат: 0

Ошибок: 0

Вектор L = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Пример № 6

Вектор признаков Х = (0, 0, 0, 1, 0, 1, 0)

Ожидаемый результат: 1

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 7

Вектор признаков Х = (0, 1, 1, 1, 1, 0, 1)

Ожидаемый результат: 0

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 8

Вектор признаков Х = (0, 1, 0, 0, 1, 1, 1)

Ожидаемый результат: 0

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 9

Вектор признаков Х = (0, 1, 0, 1, 0, 0, 1)

Ожидаемый результат: 0

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 10

Вектор признаков Х = (1, 0, 0, 1, 1, 0, 1)

Ожидаемый результат: 0

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 11

Вектор признаков Х = (1, 0, 0, 0, 0, 1, 1)

Ожидаемый результат: 0

Ошибок: 1

Вектор L = (0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1)

Пример № 12

Вектор признаков Х = (0, 1, 0, 1, 0, 0, 0)

Ожидаемый результат: 1

Ошибок: 2

Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)

Пример № 13

Вектор признаков Х = (0, 1, 1, 1, 1, 1, 1)

Ожидаемый результат: 0

Ошибок: 2

Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)

Пример № 14

Вектор признаков Х = (0, 1, 0, 0, 0, 0, 1)

Ожидаемый результат: 0

Ошибок: 2

Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)

Пример № 15

Вектор признаков Х = (0, 1, 1, 1, 0, 1, 1)

Ожидаемый результат: 0

Ошибок: 2

Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)

Пример № 16

Вектор признаков Х = (0, 1, 0, 1, 1, 1, 0)

Ожидаемый результат: 1

Ошибок: 3

Вектор L = (0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 17

Вектор признаков Х = (0, 0, 1, 1, 0, 1, 0)

Ожидаемый результат: 1

Ошибок: 4

Вектор L = (0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 18

Вектор признаков Х = (1, 0, 0, 1, 0, 1, 0)

Ожидаемый результат: 1

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 19

Вектор признаков Х = (1, 0, 1, 0, 0, 0, 1)

Ожидаемый результат: 0

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 20

Вектор признаков Х = (0, 1, 1, 0, 0, 1, 1)

Ожидаемый результат: 0

Ошибок: 5

………………………………………………………………………………………………………………

Пример № 124

Вектор признаков Х = (1, 0, 1, 1, 1, 0, 1)

Ожидаемый результат: 0

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 125

Вектор признаков Х = (0, 0, 1, 0, 1, 1, 1)

Ожидаемый результат: 0

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 126

Вектор признаков Х = (1, 0, 0, 1, 1, 0, 0)

Ожидаемый результат: 1

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 127

Вектор признаков Х = (0, 0, 0, 1, 1, 1, 1)

Ожидаемый результат: 0

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Пример № 128

Вектор признаков Х = (1, 0, 0, 0, 0, 0, 1)

Ожидаемый результат: 0

Ошибок: 5

Вектор L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Окончательная версия вектора L = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)

Прогнозирующая функция С = x4 & ~x7

Текст программы:

namespace AI_lab4

{

public partial class Form1 : Form

{

Stream fileStream;

int[,] matrix;

int n = 0, height = 0, errorsCount = 0;

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

openFileDialog1.Filter = "Текстовые файлы (*.txt)|*.txt|Все файлы (*.*)|*.*";

openFileDialog1.FilterIndex = 2;

string str = "";

ConjunctionMethodTeaching CMT;

if (openFileDialog1.ShowDialog() == DialogResult.OK)

{

int i = 0, j = 0;

fileStream = openFileDialog1.OpenFile();

while ((i = fileStream.ReadByte()) != 0x0A) if (i == 48 || i == 49) n++; //определить кол-во символов в строке

if (checkBox1.Checked) //загрузить файл целиком в двумерный массив

{

matrix = new int[(height = (int)fileStream.Length / (n * 3 + 1)) + 2, n];

CMT = new ConjunctionMethodTeaching();

fileStream.Seek(0, SeekOrigin.Begin);

i = 0;

richTextBox1.Text = "";

for (int k = 0; k < fileStream.Length; k++)

{

matrix[i, j] = fileStream.ReadByte();

if (matrix[i, j] == 0x30 || matrix[i, j] == 0x31) { matrix[i, j] -= 0x30; j++; };

if (j == n) { i++; j = 0; }

}

richTextBox1.Text = "";

i = 0;

foreach (int[] l in CMT.ConjunctionConceptionTeachingMatrix(matrix, n, height))

{

if (checkBox2.Checked)

{

str = "Пример № " + ++i + "\nВектор признаков Х = (";

for (int k = 0; k < n - 1; k++)

str += matrix[i - 1, k] + ", ";

str = str.Remove(str.Length - 2) + ")\n";

str += "Ожидаемый результат: " + matrix[i - 1, n - 1] + "\n";

str += "Ошибок: " + CMT.GetErrorsCount + "\nВектор L = (";

foreach (int c in CMT.GetL)

str += c + ", ";

str = str.Remove(str.Length - 2) + ")\n";

richTextBox1.Text += str;

str = "";

}

}

}

i = 0;

str = "";

string str2 = "";

richTextBox1.Text += "\n\nОкончательная версия вектора L = (";

foreach (int l in CMT.GetL)

{

i++;

if (l == 1) str2 += (i % 2 != 0 ? "x" + (i / 2 + 1) : "~x" + i / 2) + " & ";

str += l + ", ";

}

str = str.Remove(str.Length - 2) + ")\nПрогнозирующая функция С = " + str2.Remove(str2.Length - 2);

richTextBox1.Text += str;

}

}

private void Form1_Load(object sender, EventArgs e)

{

checkBox1.Checked = checkBox2.Checked = true;

}

}

public class ConjunctionMethodTeaching

{

int[,] matrix;

int[] L;

int length, height, errorsCount;

public int[] GetL

{

get { return L; }

}

public int GetErrorsCount

{

get { return errorsCount; }

}

public ConjunctionMethodTeaching()

{

errorsCount = 0;

}

public ConjunctionMethodTeaching(int length)

{

this.length = length;

L = new int[2 * (length - 1)];

for (int i = 0; i < L.Length; i++)

L[i] = 1;

height = errorsCount = 0;

}

public ConjunctionMethodTeaching(int[,] matrix, int length, int height)

{

this.length = length;

this.height = height;

// this.matrix = new Matrix(matrix);

this.matrix = matrix;

errorsCount = 0;

L = new int[2 * (length - 1)];

for (int i = 0; i < L.Length; i++)

L[i] = 1;

}

public IEnumerable<int[]> ConjunctionConceptionTeachingMatrix(int[,] matrix, int length, int height)

{

L = new int[2 * (length - 1)];

for (int i = 0; i < L.Length; i++)

L[i] = 1;

int C;

errorsCount = 0;

for (int i = 0; i < height; i++)

{

C = 1;

for (int j = 0; j < length - 1; j++)

{

if (L[2 * j] == 1) C &= matrix[i, j];

if (L[2 * j + 1] == 1) C &= Convert.ToInt32(!Convert.ToBoolean(matrix[i, j]));

}

if (C == matrix[i, length - 1])

yield return L;

else

{

errorsCount++;

for (int k = 0; k < length - 1; k++)

{

if (matrix[i, k] == 0) L[2 * k] = 0;

if (!Convert.ToBoolean(matrix[i, k]) == false) L[2 * k + 1] = 0;

}

i--;

}

}

}

}

}

Соседние файлы в папке doc200