close

Вход

Забыли?

вход по аккаунту

?

ИИ лаб2

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Дальневосточный федеральный университет"
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
Кафедра информационных систем управления
ОТЧЕТ по лабораторной работе № 2
Выполнили студенты гр. С-8527 _______________ Дронов А.Г.
_______________ Бурмистров В.Ю.
_______________ Лисенков В.О.Проверил доцент
_______________ Москаленко Ю.С.
_______________________ (оценка)
г. Владивосток
2013
Содержание
Краткая теория3
Табличная модель3
Элементарная предикатная матрица3
Тесты3
Процедура нахождения опорных множеств4
Связки4
Процедура нахождения множества связок5
Проблема валидации5
Процесс распознавания нового элемента6
Качество распознавания7
Аффинные преобразования8
Программная реализация12
Вывод14
Приложение15
Краткая теория
Табличная модель
Пусть задано множество описаний объектов представлено в таблице T_(m,n)^l, где m - число строк (описаний объектов), n - число столбцов (признаков, атрибутов, характеризующие рассматриваемые объекты ) и l - параметр, определяющий количество классов.
Элементарная предикатная матрица
Элементарной предикатной матрицей (ЭПМ) - называется такая матрица, строки которой соотвествуют парам сравниваемых примеров, а столбцы - именам предикатов соответсвуютщих признаков. ЭПМ называется структура следующего вида:
T_p^ = 〖{〖{µ_ij^ }〗_(j=1)^v}〗_(i=1)^n,
где µ_ij^ ∈{0,1}, n - число признаков, v- число строк матрицы, переопределяемое через произведение числа примеров, характеризующих каждый класс объектов. Например, при числе классов объектов равном 2, v = m_1^ ×m_2^ , где m_1^ и m_2^ - число примеров в первом и во втором классе объектов соответственно.
Тесты
Тестом называется совокумность признаков (атрибутов, свойств) h = x_(t_1^ )^ , x_(t_2^ )^ ,...,x_(t_g^ )^ , что после удаления из схемы понятия или дескриптора X признаков, не вошедших в эту совокупность, описания всех пар объектов, принадлежащим разным классам, остаются различимыми. В терминах табличной модели T_(m,n)^l этим шаблонам соотвествуют подмножества столбцов (атрибутов).
Тупиковым тестом h ̃ называется такой тест, никакая часть которого не является тестом.
Процедура нахождения опорных множеств
Процедура нахождения опорных множеств состоит в нахождении всех тупиковых тестов, поиск которых осуществляется с помощью метода раскрытия скобок или метода Петрик-Яблонского. Этот метод включает в себя последовательность следующих операций:
1) На множестве строк T_(m,n)^l построить элементарную предикатную матрицу (ЭПМ) - T_p^ .
2) Упростить T_p^ путем нахождения и вычеркивания строк расширений. Строка j называется строкой расширением строки i матрицы T_p^ , если:
а) -ая строка совпадает со строкой i
б) -ая строка совпадает со строкой i по единичным компонентам и содержит большее количество единиц;
В результате вычеркивания строк-расширений получится упрощенная ЭПМ - T_p^'.
3) На множестве строк T_p^' построить выражение ПΣ преобразовать в дизъюнктивную форму ПΣ→ ΣП путем логического перемножения и раскрытия скобок с последующим упрощением термов. В соотвествии с теоремой Нельсона-Яблонского упрощенное выражение ΣП представляет собой искомое множество тупиковых тестов, или, иначе - искомые опорные множества.
Связки
Основополагающий принцип, который заложен в методологию построения тестов, основан на введении при построении ЭПМ отношения различимости между описаниями объектов. Эта концепция не в полной мере соответствует целям принятия решений по опорным множествам, каждое из которых должно характеризовать логическую регулярность в виде взаимосвязи признаков (атрибутов, свойств) информационных объектов, входящих в описание класса.
Такую информацию можно извлечьпутем нахождения некоторых шаблонов, которые в дальнейшем будем называть логическими связками.
Каждая связка S может рассматриваться как атомарный, т. е. несжимаемый элемент, логически связывающий описания объектов хотя бы по одному признаку внутри одного класса.
Введенный шаблон соотвествует неизбыточному описанию информационных объектов, характеризующих каждый из рассматриваемых классов в целом. Эти конструкции определяются как тупиковые связки S ̃.
Процедура нахождения множества связок
1) На множестве строк T_(m,n)^l построить элементарную предикатную матрицу (ЭПМ) - T_p^ .
2) Инвертировать матрицу T_p^ Далее шаги идентичны шагам в процедуре нахождения множетсва тупиковых тестов, начиная с шага 2. Полученное множество и будет множеством тупиковых связок.
Проблема валидации
Простой анализ алгоритмической схемы получения тупоковых тестов с достаточной долей уверенности позволяет утверждать, что в общем случае многие найденные тупиковые тесты могут оказаться целиком совпадать с тупиковыми связками.
Утверждение. Для одной и той де T_(m,n)^l могут существовать h ̃_j^ ∈{h_i^ }_1^p и S ̃_k^ ∈{S_i^ }_1^r, p≠r,
такие что:
h ̃_j^ = S ̃_k^ .
Доказательство тривиально и следует из определения и процедур их нахождения. Действительно, для получения множества тупиковых связок в процедуре раскрытия скобок достаточно инвертировать элементарную предикатную матрицу. Таким образом, для опорных множеств в виде тупиковых тестов или тупиковых связок проблема валидации валидации в соответствии с:
h ̃_j^ = S ̃_k^ ,
решается путем сопоставления найденных множеств шаблонов {h ̃_i^ } и {S ̃_i^ } и удаления совпадающих, т. е. имеющих противоположную интерпритацию.
Процесс распознавания нового элемента
Процедура распознавания нового элемента сводится к построению таблицы вида:
Тупиковый тестКласс 1Класс 2...Класс nh_1l_11l_12...l_1nh_2l_21l_22...l_2n...............h_ml_m1l_m2...l_mnРезультаты голосования∑_(i=1)^m▒l_i1 ∑_(i=1)^m▒l_i2 ...∑_(i=1)^m▒l_in Где l_ij=1, если элемент совпадает по признакам (атрибутам) -го теста с элементом j-го класса из T_(m,n)^l, 0 в противном случае. Затем выбирается номер класса, сумма результатов "голосования" у которого наибольшая:
max(∑_(i=1)^m▒l_i1 , ∑_(i=1)^m▒l_i2 ,... , ∑_(i=1)^m▒l_in ).
Это и будет номер класса для распознаваемого элемента. В случае, если наибольшая сумма равна 0, результатом будет отказ от распознавания.
Качество распознавания
Для оценки качества распознавания будет использована процедура скользящего экзамена. Она заключается в следующих шагах:
Для всех элементов (строк) из T_(m,n)^l:
1) Удаляем i-ю строку из T_(m,n)^l
2) Находим множество валидных тупиковых тестов
3) На основе процедуры голосования, вычисляем номер класса
4) Проводим процедуру распознавания
5) Сравниваем распознанный номер класса с номером класса, из которого был удален элемент, если номера не совпадают, то увеличиваем количество ошибочных распознаваний на единицу.
Формула качества распознавания будет следующая:
1-e/m.
Где e - количество ошибочных распознаваний, m - количество элементов в T_(m,n)^l
Аффинные преобразования
Под преобразованием понимается отображение множества на себя. Другими словами, преобразование - это правило, в соответствии с которым каждому элементу множества ставится в соответствие элемент этого же множества.
Преобразование плоскости (пространства) называется аффинным, если существуют такие две аффинные системы координат, что координаты любой точки в первой системе координат совпадают с координатами ее образа во второй системе координат.
Аффинное преобразование можно рассматривать как последовательное применение (композицию) двух отображений:
Точке ставится в соответствие координаты относительно первой системы координат;
Полученным координатам ставится в соответствие точка относительно второй системы координат.
Пусть - аффинное преобразование. Рассмотрим вектор в первой системе координат и во второй. Так как кординаты вектора определяются как разность координат конца и начала, а координаты точек и , и равны в соответствующих системах координат, то вектор имеет те же координаты относительно второй системы координат, что и вектор относительно первой.
Таким образом в определении аффинного преобразования можно было рассматривать векторы вместо точек.
Пусть первая система координат задана своим репером . Базисные векторы, отложенные от точки определяют некоторые точки . Тогда, очевидно, вторая система координат определяется репером , где .
Преобразование координат точки
Рассмотрим две аффинные системы координат, заданных своими реперами и . Пусть координаты точки и базисных векторов второго репера относительно первой системы координат выражаются следующим образом:
(1)Рассмотрим произвольную точку . Пусть ее координаты в первой и второй системах координат и соответственно. Определим как связаны между собой эти координаты. Очевидно,
По определению
в первой системе координат
в первой системе координат
во второй системе координатТогда . Подставим выражение (1), после приведения подобных получим
Поскольку вектор однозначно представляется как линейная комбинация базисных векторов, то коэффициенты в левой и правой частях равенства должны быть одни и те же, то есть
Можно записать эту формулу в матричном виде
Аналогично можно вывести обратную формулу
Матрица
называется матрицей преобразования координат. Формулу (1) можно переписать в виде
(1')Поскольку базисные векторы линейно независимы, то матрица преобразования координат должна быть невырожденной (определитель не равен нулю).
Программная реализация
На рисунке 1 изображено главное окно программы, которое появляется при запуске программы и выборе страницы лабораторной работы №2 - "Распознавание образов".
Рисунок 1 - Главное окно программы
Наполнение словаря происходит путем ввода изображения на левом дисплее или же путем заполнения таблицы справа (рисунок 2). Ввод изображения или вектора для распознавания осуществляется там же.
Рисунок 2 - Ввод изображения и наполнение словаря
После того, как словарь был наполнен, можно приступать к распознаванию. Введя данные для распознавания, будут просчитаны тесты, если это еще не было сделано ранее, и будут отображены в правом верхнем углу (рисунок 3).
Рисунок 3 - Распознавание изображения
Качество распознавания производится путем нажатия кнопки "Анализ", после чего появляется новое с результатами анализа (рисунок 4).
Рисунок 4 - Определение качества распознавания
Вывод
В ходе выполнения лабораторной работы были реализованы метод нахождения всех тупиковых тестов, а также распознавание образов.
Приложение
using System;
using System.Collections.Generic;
using System.Linq; namespace AI_labs
{
public static class Lab2
{
public static int ComprareWithElements(List<int[]> Elem_list, int[][] Tests, int[] Classes, int Classes_count, int[] row)
{
List<List<int>> TestElemNumb = new List<List<int>>();
for (int i = 0; i < Tests.Length; i++)
{
TestElemNumb.Add(new List<int>());
for (int j = 0; j < Tests[0].Length; j++)
{
if (Tests[i][j] != 0)
{
TestElemNumb.Last().Add(j);
}
}
}
int[,] Marks = new int[Classes_count, Tests.Length];
int count = 0;
for (int i = 0; i < Elem_list.Count; i++)
{
for (int k = 0; k < TestElemNumb.Count; k++)
{
count = 0;
for (int j = 0; j < TestElemNumb[k].Count; j++)
{
if (Elem_list[i][TestElemNumb[k][j]] == row[TestElemNumb[k][j]])
count++;
else
break;
}
if (count == TestElemNumb[k].Count)
Marks[Classes[i] - 1, k] = 1;
}
}
int[] Counts = FindMaxMark(Marks);
int ClassNumber = 0;
count = Counts.Count(item => item == Counts.Max());
if (count > 1) return -1;
for (int i = 0; i < Counts.Length; i++)
{
if (Counts.Max() == Counts[i])
{
ClassNumber = i;
break;
}
}
return ClassNumber;
}
public static int ComprareWithElements(List<int[]> Elem_list, int[][] Tests, int[] Classes, int Classes_count, int[] row, out int[] Mark_massive)
{
List<List<int>> TestElemNumb = new List<List<int>>();
for (int i = 0; i < Tests.Length; i++)
{
TestElemNumb.Add(new List<int>());
for (int j = 0; j < Tests[0].Length; j++)
{
if (Tests[i][j] != 0)
{
TestElemNumb.Last().Add(j);
}
}
}
int[,] Marks = new int[Classes_count, Tests.Length];
int count = 0;
for (int i = 0; i < Elem_list.Count; i++)
{
for (int k = 0; k < TestElemNumb.Count; k++)
{
count = 0;
for (int j = 0; j < TestElemNumb[k].Count; j++)
{
if (Elem_list[i][TestElemNumb[k][j]] == row[TestElemNumb[k][j]])
count++;
else
break;
}
if (count == TestElemNumb[k].Count)
Marks[Classes[i] - 1, k] = 1;
}
}
int[] Counts = FindMaxMark(Marks);
Mark_massive = Counts;
int ClassNumber = 0;
count = Counts.Count(item => item == Counts.Max());
if (count > 1) return -1;
for (int i = 0; i < Counts.Length; i++)
{
if (Counts.Max() == Counts[i])
{
ClassNumber = i;
break;
}
}
return ClassNumber;
}
public static int[] ConvertInClassMassive(int[] Classes)
{
int position = 0;
List<int> L_Classes = new List<int>();
L_Classes.Add(0);
for (int i = 0; i < Classes.Length; i++)
{
if (Classes[i] == Classes[position])
continue;
else
{
L_Classes.Add(i);
position = i;
}
}
L_Classes.Add(Classes.Length);
return L_Classes.ToArray();
}
public static int[] FindMaxMark(int[,] Marks)
{
int[] Counts = new int[Marks.GetLength(0)];
for (int i = 0; i < Marks.GetLength(0); i++)
{
for (int j = 0; j < Marks.GetLength(1); j++)
{
Counts[i] += Marks[i, j];
}
}
return Counts;
}
public static string GetStrTests(int[][] Tests)
{
string strTests = "";
for (int i = 0; i < Tests.Length; i++)
{
for (int j = 0; j < Tests[0].Length; j++)
{
if (Tests[i][j] != 0)
{
strTests += "X" + Tests[i][j] + " ";
}
}
strTests += "\r\n";
}
return strTests;
}
public static int Calculate_EPM_rows(int[] Classes)
{
int EPM_rows = new int();
for (int i = 0; i < Classes.Length - 1; i++)
{
for (int j = i + 1; j < Classes.Length - 1; j++)
{
EPM_rows += (Classes[i + 1] - Classes[i]) * (Classes[j + 1] - Classes[j]);
}
}
return EPM_rows;
}
public static int[,] Calculate_EPM(object[] Matrix, int[] Classes)
{
int EPM_rows = Calculate_EPM_rows(Classes);
int[,] EPM = new int[EPM_rows, Matrix.Length];
int EPM_i = new int();
//Формирование ЭПМ
//Выбор 1-го класса
for (int i = 0; i < Classes.Length - 1; i++)
{
//Выбор элемента 1-го класса
for (int j = Classes[i]; j < Classes[i + 1]; j++)
{
//Выбор 2-го класса, с которым будет производиться сравнение
for (int k = i + 1; k < Classes.Length - 1; k++)
{
//Выбор элемента 2-го класса
for (int h = Classes[k]; h < Classes[k + 1]; h++)
{
//Сравнение ячеек элементов 1го и 2-го классов
for (int t = 0; t < Matrix.Length; t++)
{
switch (Matrix[t].GetType().Name)
{
case "String[]":
if ((Matrix[t] as string[])[j] != (Matrix[t] as string[])[h])
EPM[EPM_i, t] = 1;
break;
case "Int32[]":
int iA = (Matrix[t] as int[])[j];
int iB = (Matrix[t] as int[])[h];
if (iB != iA)
EPM[EPM_i, t] = 1;
break;
case "Single[]":
float fA = (Matrix[t] as float[])[j];
float fB = (Matrix[t] as float[])[h];
if (fB != fA)
EPM[EPM_i, t] = 1;
break;
default:
break;
}
}
EPM_i++;
}
}
}
}
return EPM;
}
public static int[,] DeleteRow(int[,] Matrix, int RowNumber)
{
int[,] Result = new int[Matrix.GetLength(0) - 1, Matrix.GetLength(1)];
for (int i = 0; i < Matrix.GetLength(0) - 1; i++)
{
for (int j = 0; j < Matrix.GetLength(1); j++)
{
Result[i, j] = i < RowNumber ? Matrix[i, j] : Matrix[i + 1, j];
}
}
return Result;
}
public static int[,] DeleteColumn(int[,] Matrix, int ColumnNumber)
{
int[,] Result = new int[Matrix.GetLength(0), Matrix.GetLength(1) - 1];
for (int i = 0; i < Matrix.GetLength(0); i++)
{
for (int j = 0; j < Matrix.GetLength(1) - 1; j++)
{
Result[i, j] = j < ColumnNumber ? Matrix[i, j] : Matrix[i, j + 1];
}
}
return Result;
}
public static int[,] DeleteRowColumn(int[,] Matrix, int RowNumber, int ColumnNumber)
{
int[,] Result = DeleteRow(DeleteColumn(Matrix, ColumnNumber), RowNumber);
return Result;
}
public static int IndexOf(int[] Array, int value)
{
for (int i = 0; i < Array.Length; i++)
{
if (Array[i] == value) return i;
}
throw new NotImplementedException("No such value");
}
public static int IndexOfMinExclude(int[] Array, int except_value)
{
int min = Array[0];
int index = 0;
for (int i = 0; i < Array.Length; i++)
{
if (Array[i] < min && Array[i] != except_value)
{
min = Array[i];
index = i;
}
}
return index;
}
public static int CountOneRow(int[,] Matrix, int RowNumber)
{
int sum = new int();
for (int i = 0; i < Matrix.GetLength(1); i++)
{
sum += Matrix[RowNumber, i];
}
return sum;
}
public static int CountOneColumn(int[,] Matrix, int ColumnNumber)
{
int sum = new int();
for (int i = 0; i < Matrix.GetLength(0); i++)
{
sum += Matrix[i, ColumnNumber];
}
return sum;
}
public static int[] CountOneRows(int[,] Matrix)
{
int[] Result = new int[Matrix.GetLength(0)];
for (int i = 0; i < Matrix.GetLength(0); i++)
{
Result[i] = CountOneRow(Matrix, i);
}
return Result;
}
public static int[] CountOneColumns(int[,] Matrix)
{
int[] Result = new int[Matrix.GetLength(1)];
for (int i = 0; i < Matrix.GetLength(1); i++)
{
Result[i] = CountOneColumn(Matrix, i);
}
return Result;
}
public static int[] DeleteElement(int[] Array, int ElementNubmer)
{
int[] Result = new int[Array.Length - 1];
for (int i = 0; i < Array.Length; i++)
{
Result[i] = i < ElementNubmer ? Array[i] : Array[i + 1];
}
return Result;
}
public static int[,] DeleteOneRows(int[,] Matrix, int ColumnNumber)
{
int[,] Result = Matrix.Clone() as int[,];
for (int i = 0; i < Result.GetLength(0); i++)
{
if (Result[i, ColumnNumber] == 1)
{
Result = DeleteRow(Result, i);
i--;
}
}
return Result;
}
public static int[,] DeleteOneColumns(int[,] Matrix, int RowNumber)
{
int[,] Result = Matrix.Clone() as int[,];
for (int i = 0; i < Result.GetLength(0); i++)
{
if (Result[RowNumber, i] == 1)
{
Result = DeleteRow(Result, i);
i--;
}
}
return Result;
}
public static int RowSum(int[,] Matrix, int RowNubmer)
{
int Result = new int();
for (int j = 0; j < Matrix.GetLength(1); j++)
{
if (Matrix[RowNubmer, j] >= 1)
Result++;
}
return Result;
}
public static int ColumnSum(int[,] Matrix, int ColumnNumber)
{
int Result = new int();
for (int i = 0; i < Matrix.GetLength(0); i++)
{
if (Matrix[i, ColumnNumber] >= 1)
Result++;
}
return Result;
}
public static int[] RowElementNumbers(int[,] Matrix, int RowNumber)
{
int length = RowSum(Matrix, RowNumber);
int[] Result = new int[length];
int k = new int();
for (int i = 0; i < Matrix.GetLength(1); i++)
{
if (Matrix[RowNumber, i] >= 1)
{
Result[k] = i;
k++;
}
}
return Result;
}
public static int[] ColumnElementNumbers(int[,] Matrix, int ColumnNumber)
{
int length = ColumnSum(Matrix, ColumnNumber);
int[] Result = new int[length];
int k = new int();
for (int i = 0; i < Matrix.GetLength(0); i++)
{
if (Matrix[i, ColumnNumber] >= 1)
{
Result[k] = i;
k++;
}
}
return Result;
}
public static int[] CopyRow(int[,] Matrix, int RowNumb)
{
int[] Result = new int[Matrix.GetLength(1)];
for (int j = 0; j < Matrix.GetLength(1); j++)
{
Result[j] = Matrix[RowNumb, j];
}
return Result;
}
public static int[] CountZeroColumns(int[,] Matrix)
{
int[] Result = new int[Matrix.GetLength(1)];
int Count = new int();
for (int j = 0; j < Matrix.GetLength(1); j++)
{
for (int i = 0; i < Matrix.GetLength(0); i++)
{
if (Matrix[i, j] == 0) Count++;
}
Result[j] = Count;
}
return Result;
}
public static int[,] CopyPasteColumnPart(int[,] Matrix)
{
int[] zeroCount = CountZeroColumns(Matrix);
int[][] B = new int[Matrix.GetLength(1) - 1][];
int COLUMNS = Matrix.GetLength(1);
int ROWS = Matrix.GetLength(0);
int[,] Result = Matrix.Clone() as int[,];
for (int i = 0; i < B.GetLength(0); i++)
{
B[i] = ColumnElementNumbers(Matrix, i);
}
for (int j = 0; j < COLUMNS - 1; j++)
{
int K = B[j].Length / B[0].Length;
for (int h = 0; h < B[0].Length; h++)
{
for (int i = 0; i < ROWS / B[0].Length - K; i++)
{
int Shift1 = h * ROWS / B[0].Length;
int Shift2 = h * B[j].Length / B[0].Length;
int row_index1 = i + K + Shift1;
int row_index2 = B[j][(i % (B[j].Length / B[0].Length)) + Shift2];
Result[i + K + Shift1, j] = Result[B[j][(i % (B[j].Length / B[0].Length)) + Shift2], j];
}
}
}
return Result;
}
public static List<int[]> MultiplyRows(int[] Row1, int[] Row2)
{
List<int[]> Result = new List<int[]>();
List<int> Row2ElemNumb = new List<int>();
List<List<int>> RowsElemNumb = new List<List<int>>();
for (int i = 0; i < Row2.Length; i++)
{
if (Row2[i] != 0) Row2ElemNumb.Add(i);
}
//Перемножение строк
for (int i = 0; i < Row2ElemNumb.Count; i++)
{
int[] temp = Row1.Clone() as int[];
temp[Row2ElemNumb[i]] = 1;
Result.Add(temp);
}
return Result;
}
public static List<int[]> DeleteSameRows(List<int[]> List_rows)
{
List<List<int>> RowsElemNumb = new List<List<int>>();
//Получение номеров значений всех получившихся строк
for (int k = 0; k < List_rows.Count; k++)
{
RowsElemNumb.Add(new List<int>());
for (int i = 0; i < List_rows[0].Length; i++)
{
if (List_rows[k][i] != 0) RowsElemNumb[k].Add(i);
}
}
qs_lists(List_rows, RowsElemNumb, 0, RowsElemNumb.Count - 1);
//Упрощение получившегося результата
List<int> RowsForDelete = new List<int>();
for (int i = 0; i < List_rows.Count; i++)
{
if (RowsForDelete.Contains(i)) continue;
for (int k = i + 1; k < List_rows.Count; k++)
{
if (RowsForDelete.Contains(k)) continue;
int Equals = 0;
for (int j = 0; j < RowsElemNumb[i].Count; j++)
{
if (List_rows[i][RowsElemNumb[i][j]] == List_rows[k][RowsElemNumb[i][j]]) Equals++;
}
if (Equals == RowsElemNumb[i].Count) RowsForDelete.Add(k);
}
}
RowsForDelete.Sort();
for (int i = RowsForDelete.Count - 1; i >= 0; i--)
{
List_rows.RemoveAt(RowsForDelete[i]);
}
return List_rows;
}
public static int[,] DeleteSameRows2(int[,] Matrix)
{
List<int> RowsForDelete = new List<int>();
List<int> CheckedMins = new List<int>();
int[] RowData = CountOneRows(Matrix);
do
{
int index = IndexOfMinExclude(RowData, -1);
int[] elemNums = RowElementNumbers(Matrix, index);
for (int i = 0; i < Matrix.GetLength(0); i++)
{
bool DeleteCase = true;
if (i == index || RowsForDelete.Exists(item => item == i) || CheckedMins.Exists(item => item == i)) continue;
for (int j = 0; j < elemNums.Length; j++)
{
DeleteCase &= Matrix[index, elemNums[j]] == Matrix[i, elemNums[j]];
if (!DeleteCase) continue;
}
if (DeleteCase)
{
RowsForDelete.Add(i);
RowData[i] = -1;
}
}
RowData[index] = -1;
CheckedMins.Add(index);
} while (Math.Abs(RowData.Count(item => item == -1)) < RowData.Length);
RowsForDelete.Sort();
int[,] Result = Matrix.Clone() as int[,];
//for (int i = RowsForDelete.Count - 1; i >= 0; i--)
//{
// Result = DeleteRow(Result, RowsForDelete[i]);
//}
return DeleteRow2(Result, RowsForDelete);
}
public static int[,] DeleteRow2(int[,] Matrix, List<int> Rows_numbers)
{
int ROWS = Matrix.GetLength(0);
int COLUMNS = Matrix.GetLength(1);
int[,] Result = new int[ROWS - Rows_numbers.Count, COLUMNS];
int new_row = 0;
for (int i = 0; i < Matrix.GetLength(0); i++)
{
if (Rows_numbers.Contains(i)) continue;
for (int j = 0; j < COLUMNS; j++)
{
Result[new_row, j] = Matrix[i, j];
}
new_row++;
}
return Result;
}
public static int[][] CalculateTests(int[,] EPM_min)
{
int ROWS = EPM_min.GetLength(0);
int COLUMNS = EPM_min.GetLength(1);
List<int[]> LeftSide = new List<int[]>();
List<int[]> RightSide = new List<int[]>();
//LeftSide.Add(CopyRow(EPM_min, 0));
int[] Elems = RowElementNumbers(EPM_min, 0);
for (int i = 0; i < Elems.Length; i++)
{
int[] temp = new int[EPM_min.GetLength(1)];
temp[Elems[i]] = 1;
LeftSide.Add(temp);
}
for (int i = 1; i < ROWS; i++)
{
RightSide.Add(CopyRow(EPM_min, i));
}
for (int i = 0; i < RightSide.Count; i++)
{
List<int[]> TempList = new List<int[]>();
for (int k = 0; k < LeftSide.Count; k++)
{
TempList.AddRange(MultiplyRows(LeftSide[k], RightSide[i]));
}
DeleteSameRows(TempList);
LeftSide = TempList;
}
int[][] Result = LeftSide.ToArray();
return Result;
}
public static int[,] CalculateElements(int[,] EPM_min)
{
List<int[]> oneCount = new List<int[]>();
int Sum = 1;
for (int i = 0; i < EPM_min.GetLength(0); i++)
{
oneCount.Add(RowElementNumbers(EPM_min, i));
Sum *= oneCount[i].Length;
}
int[,] Result = new int[Sum, EPM_min.GetLength(0)];
for (int h = 0; h < oneCount[0].Length; h++)
{
int Actions = 1;
Result[h * (Sum / oneCount[0].Length), 0] = oneCount[0][h] + 1;
for (int i = 1; i < EPM_min.GetLength(0); i++)
{
int position = 0;
for (int j = 0; j < oneCount[i].Length; j++)
{
for (int k = 0; k < Actions; k++)
{
Result[h * (Sum / oneCount[0].Length) + position, i] = oneCount[i][j] + 1;
position++;
}
}
Actions *= oneCount[i].Length;
}
}
Result = CopyPasteColumnPart(Result);
return Result;
}
public static void SwapRows(int[,] Matrix, int row1, int row2)
{
int length = Matrix.GetLength(1);
for (int j = 0; j < length; j++)
{
int temp = Matrix[row1, j];
Matrix[row1, j] = Matrix[row2, j];
Matrix[row2, j] = temp;
} }
public static void SwapRows(object[] Matrix, int row1, int row2)
{
int length = Matrix.Length;
for (int j = 0; j < length; j++)
{
object temp = (Matrix[j] as Array).GetValue(row1);
(Matrix[j] as Array).SetValue((Matrix[j] as Array).GetValue(row2), row1);
(Matrix[j] as Array).SetValue(temp, row2);
}
}
public static void qs(int[,] s_arr, int first, int last, int row_numb)
{
int i = first, j = last, x = s_arr[row_numb, (first + last) / 2];
do
{
while (s_arr[row_numb, i] < x) i++;
while (s_arr[row_numb, j] > x) j--;
if (i <= j)
{
if (i < j)
{
int temp = s_arr[row_numb, i];
s_arr[row_numb, i] = s_arr[row_numb, j];
s_arr[row_numb, j] = temp;
}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs(s_arr, i, last, row_numb);
if (first < j)
qs(s_arr, first, j, row_numb);
}
public static void qs_classes(int[,] s_arr, int[] classes, int first, int last)
{
int i = first, j = last, x = classes[(first + last) / 2];
do
{
while (classes[i] < x) i++;
while (classes[j] > x) j--;
if (i <= j)
{
if (i < j)
{
int temp = classes[i];
classes[i] = classes[j];
classes[j] = temp;
SwapRows(s_arr, i, j);
}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs_classes(s_arr, classes, i, last);
if (first < j)
qs_classes(s_arr, classes, first, j);
}
public static void qs_classes(object[] s_arr, int[] classes, int first, int last)
{
int i = first, j = last, x = classes[(first + last) / 2];
do
{
while (classes[i] < x) i++;
while (classes[j] > x) j--;
if (i <= j)
{
if (i < j)
{
int temp = classes[i];
classes[i] = classes[j];
classes[j] = temp;
SwapRows(s_arr, i, j);
}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs_classes(s_arr, classes, i, last);
if (first < j)
qs_classes(s_arr, classes, first, j);
}
public static void qs_down(int[] s_arr, int first, int last)
{
int i = first, j = last, x = s_arr[(first + last) / 2];
do
{
while (s_arr[i] > x) i++;
while (s_arr[j] < x) j--;
if (i <= j)
{
if (i < j)
{
int temp = s_arr[i];
s_arr[i] = s_arr[j];
s_arr[j] = temp;
}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs_down(s_arr, i, last);
if (first < j)
qs_down(s_arr, first, j);
}
public static void qs_lists(List<int[]> ArrList, List<List<int>> Lists, int first, int last)
{
int i = first, j = last, x = Lists[(first + last) / 2].Count;
do
{
while (Lists[i].Count < x) i++;
while (Lists[j].Count > x) j--;
if (i <= j)
{
if (i < j)
{
List<int> temp1 = Lists[i];
Lists[i] = Lists[j];
Lists[j] = temp1;
int[] temp2 = ArrList[i];
ArrList[i] = ArrList[j];
ArrList[j] = temp2;
}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs_lists(ArrList, Lists, i, last);
if (first < j)
qs_lists(ArrList, Lists, first, j);
}
public static int IsRowEqual(int[,] Matrix, int row1_n, int row2_n)
{
int[] row1_elem = RowElementNumbers(Matrix, row1_n);
int[] row2_elem = RowElementNumbers(Matrix, row2_n);
int[] min_row = row1_elem.Length < row2_elem.Length ? row1_elem : row2_elem;
int min_row_n = 0;
int max_row_n = 0;
if (row1_elem.Length < row2_elem.Length)
{
min_row_n = row1_n;
max_row_n = row2_n;
}
else
{
min_row_n = row2_n;
max_row_n = row1_n;
}
for (int i = 0; i < min_row.Length; i++)
{
if (Matrix[min_row_n, min_row[i]] != Matrix[max_row_n, min_row[i]]) return -1;
}
return max_row_n;
}
public static int[,] InverseEPM(int[,] EPM)
{
int Rows = EPM.GetLength(0);
int Columns = EPM.GetLength(1);
int[,] Result = new int[Rows, Columns];
for (int i = 0; i < Rows; i++)
{
for (int j = 0; j < Columns; j++)
{
Result[i, j] = EPM[i, j] == 0 ? 1 : 0;
}
}
return Result;
}
public static bool IsRowsEqual(int[][] Arr1, int[][] Arr2, int row1, int row2)
{
if (Arr1[0].Length != Arr2[0].Length) return false;
int Columns = Arr1[0].Length;
int Count = 0;
for (int j = 0; j < Columns; j++)
{
if (Arr1[row1][j] == Arr2[row2][j]) Count++;
}
return Count == Columns;
}
public static int[][] DeleteBunches(int[][] Tests, int[][] Bunches)
{
List<int> RowsNumb = new List<int>();
for (int i = 0; i < Tests.Length; i++)
{
for (int k = 0; k < Bunches.Length; k++)
{
if (IsRowsEqual(Tests, Bunches, i, k)) RowsNumb.Add(i);
}
}
int[][] Result = new int[Tests.Length - RowsNumb.Count][];
int Res_i = 0;
for (int i = 0; i < Tests.Length; i++)
{
if (RowsNumb.Contains(i)) continue;
Result[Res_i] = new int[Tests[i].Length];
for (int j = 0; j < Tests[i].Length; j++)
{
Result[Res_i][j] = Tests[i][j];
}
Res_i++;
}
return Result;
}
public static int[,] AllMinTestsMethod(object[] Matrix, int[] Classes, float[] E)
{
int[,] EPM = Calculate_EPM(Matrix, Classes);
if (EPM.GetLength(0) == 0) return null;
int[,] EPM_min = DeleteSameRows2(EPM);
//int[,] Result2 = CalculateElements2(Result);
int[,] AllCombinations = CalculateElements(EPM_min);
for (int i = 0; i < AllCombinations.GetLength(0); i++)
{
qs(AllCombinations, 0, AllCombinations.GetLength(1) - 1, i);
}
int[,] Result = new int[AllCombinations.GetLength(0), Matrix.Length];
for (int i = 0; i < AllCombinations.GetLength(0); i++)
{
for (int j = 0; j < AllCombinations.GetLength(1); j++)
{
Result[i, AllCombinations[i, j] - 1] = AllCombinations[i, j];
}
}
#region EqualsRowsDelete
int[] RowsForDelete = new int[Result.GetLength(0)];
for (int i = 0; i < RowsForDelete.Length; i++)
RowsForDelete[i] = -1;
int count = 0;
for (int i = 0; i < Result.GetLength(0); i++)
{
if (RowsForDelete.Contains(i)) continue;
for (int k = i + 1; k < Result.GetLength(0); k++)
{
if (RowsForDelete.Contains(k)) continue;
int rowForDelete = IsRowEqual(Result, i, k);
if (rowForDelete != -1)
{
RowsForDelete[count] = rowForDelete;
count++;
}
if (rowForDelete == i) break;
}
}
qs_down(RowsForDelete, 0, RowsForDelete.Length - 1);
for (int i = 0; i < RowsForDelete.Length && RowsForDelete[i] != -1; i++)
{
Result = DeleteRow(Result, RowsForDelete[i]);
}
#endregion
return Result;
}
public static int[][] AllMinTestsMethod_n(object[] Matrix, int[] Classes)
{
int[,] EPM = Calculate_EPM(Matrix, Classes);
if (EPM.GetLength(0) == 0) return null;
int[,] EPM_min_t = DeleteSameRows2(EPM);
int[,] EPM_min_b = InverseEPM(EPM_min_t);
int[][] Tests = CalculateTests(EPM_min_t);
int[][] Bunches = CalculateTests(EPM_min_b);
int[][] Tests_wo_Bunches = DeleteBunches(Tests, Bunches);
int[][] Result = new int[Tests_wo_Bunches.Length][];
for (int i = 0; i < Tests_wo_Bunches.Length; i++)
{
Result[i] = new int[Tests_wo_Bunches[0].Length];
for (int j = 0; j < Tests_wo_Bunches[0].Length; j++)
{
if (Tests_wo_Bunches[i][j] == 1) Result[i][j] = j + 1;
}
}
return Result;
}
public static int[] CloseToMinTestMethod(object[] Matrix, int[] Classes)
{
int[,] EPM = Calculate_EPM(Matrix, Classes);
while (EPM.GetLength(0) > 1)
{
int[] columnData = CountOneColumns(EPM);
int index = IndexOf(columnData, columnData.Max());
EPM = DeleteOneRows(EPM, index);
}
int[] Result = new int[EPM.GetLength(1)];
for (int i = 0; i < Result.Length; i++)
{
Result[i] = EPM[0, i];
}
return Result;
}
}
}
Документ
Категория
Рефераты
Просмотров
24
Размер файла
287 Кб
Теги
лаб2
1/--страниц
Пожаловаться на содержимое документа