Доброго времени суток всем читающим. Сначала изложу предысторию данного вопроса. Началось все с того что знакомый попросил меня по работе помочь ему сделать приложение (WinForm на C#), которая бы алгоритмом CART создавала бинарное дерево решений, исходя из статистических данных находящихся в таблице на форме. Суть в том, чтобы делить исходную таблицу на 2 части по вычисляемым критериям. Для того чтобы поделить исходную таблицу, мы должны найти среднее по каждому из столбцов:
//нахождение средних значений по столбцам
public static double[] GetAverageValue(DataTable table)
{
#region Расчет средних значений по столбцам
var sr = new double[14];
for (int j = 1; j < table.Columns.Count - 1; j++)
{
double sum = 0.0;
for (int i = 0; i < table.Rows.Count; i++)
{
sum = sum + Convert.ToDouble(table.Rows[i][j]);
}
sr[j - 1] = sum / table.Rows.Count;
}
#endregion
return sr;
}
Первый и последний столбцы в расчете не учитываются (в первом значение Год, в последнем значения 0 или 1). Данная функция вернет одномерный массив средних значений, обращение к которым будет идти согласно индексу.
Затем идет собственно поиск коэффициента Gini по каждому из столбцов, который покажет нам какой из столбцов брать для разделения нашей таблицы, среди них выбирается минимальное и соответственно индекс столбца с минимальным коэффициентом будет необходимым нам для разделения. Затем выбирается этот столбец и все значения больше среднего значения для данного столбца отправляются в одну таблицу, например 1.1, а все значения меньше среднего в таблицу 1.2. Ниже код. который отвечает за первое разделение исходной таблицы:
//нахождение значений больше либо равных среднему в столбце таблицы
public static int[] GetMoreAverageAndLessAverage(double average, double[] columns, int[] T)
{
int moreAverage = 0;
int valueTMoreAverage = 0;
int valueTInvertMoreAverage = 0;
int lessAverage = 0;
int valueTLessAverage = 0;
int valueTLessInvertAverage = 0;
var moreAverageValue = new int[6];
for (int i = 0; i < columns.Length; i++ )
{
if (columns[i] >= average)
{
moreAverage = moreAverage + 1;
if (T[i] == 1)
{
valueTMoreAverage = valueTMoreAverage + 1;
}
else
{
valueTInvertMoreAverage = valueTInvertMoreAverage + 1;
}
}
else
{
lessAverage = lessAverage + 1;
if (T[i] == 1)
{
valueTLessAverage = valueTLessAverage + 1;
}
else
{
valueTLessInvertAverage = valueTLessInvertAverage + 1;
}
}
}
moreAverageValue[0] = moreAverage;
moreAverageValue[1] = valueTMoreAverage;
moreAverageValue[2] = valueTInvertMoreAverage;
moreAverageValue[3] = lessAverage;
moreAverageValue[4] = valueTLessAverage;
moreAverageValue[5] = valueTLessInvertAverage;
return moreAverageValue;
}
//нахождение значения коэффициента Gini(T,param)
public static double GetValueGini(int[] currentCollumnsAndT, int lengthCollumns)
{
var gini = 0.0;
if (currentCollumnsAndT != null)
{
double gini1 = (Convert.ToDouble(currentCollumnsAndT.GetValue(0)) / lengthCollumns) *
(1 -
((Convert.ToDouble(currentCollumnsAndT.GetValue(1)) / Convert.ToDouble(currentCollumnsAndT.GetValue(0))) *
(Convert.ToDouble(currentCollumnsAndT.GetValue(1)) / Convert.ToDouble(currentCollumnsAndT.GetValue(0)))) -
((Convert.ToDouble(currentCollumnsAndT.GetValue(2)) / Convert.ToDouble(currentCollumnsAndT.GetValue(0))) *
(Convert.ToDouble(currentCollumnsAndT.GetValue(2)) / Convert.ToDouble(currentCollumnsAndT.GetValue(0)))));
double gini2 = (Convert.ToDouble(currentCollumnsAndT.GetValue(3)) / lengthCollumns) *
(1 -
((Convert.ToDouble(currentCollumnsAndT.GetValue(4)) / Convert.ToDouble(currentCollumnsAndT.GetValue(3))) *
(Convert.ToDouble(currentCollumnsAndT.GetValue(4)) / Convert.ToDouble(currentCollumnsAndT.GetValue(3)))) -
((Convert.ToDouble(currentCollumnsAndT.GetValue(5)) / Convert.ToDouble(currentCollumnsAndT.GetValue(3))) *
(Convert.ToDouble(currentCollumnsAndT.GetValue(5)) / Convert.ToDouble(currentCollumnsAndT.GetValue(3)))));
gini = gini1 + gini2;
}
return gini;
}
//расчет первичного разделения таблицы
public static double[] GetValueGiniIsPrimaryDivide(DataTable table)
{
var currentCollumn = new double[table.Rows.Count];
var average = GetAverageValue(table); //выкинуть в класс формы чтобы не изменялось, передавать параметром в GetValueGiniIsPrimaryDivide (возможно передавать)
var T = new int[table.Rows.Count];
var gini = new double[table.Columns.Count - 1];
for (int i = 0; i < table.Rows.Count; i++)
{
T[i] = Convert.ToInt16(table.Rows[i][table.Columns.Count - 1]);
}
for (int i = 1; i < table.Columns.Count - 1; i++)
{
for (int j = 0; j < table.Rows.Count; j++)
{
currentCollumn[j] = 0.0;
currentCollumn[j] = Convert.ToDouble(table.Rows[j][i].ToString());
}
var bufer = average[i - 1];
gini[i] = GetValueGini(GetMoreAverageAndLessAverage(bufer, currentCollumn, T), table.Rows.Count);
}
var min = Convert.ToDouble(gini.GetValue(0));
int indexMin = 0;
for (int i = 0; i < gini.Length; i++)
{
if (Convert.ToDouble(gini.GetValue(i)) <= min)
{
min = Convert.ToDouble(gini.GetValue(i));
indexMin = i;
}
}
var returnValue = new double[2];
returnValue[0] = min;
returnValue[1] = indexMin;
return returnValue;
}
}
Сама таблица, напомню, получается из DataGridView. И вызывается все вышеизложенное таким образом:
#region Создание из DataGrid DataTable
var table = new DataTable();
for (int j = 0; j < dataGridView1.Columns.Count; j++)
{
table.Columns.Add(dataGridView1.Columns[j].Name);
}
for (int i = 0; i < dataGridView1.Rows.Count - 1; i++)
{
table.Rows.Add();
for (int j = 0; j < dataGridView1.Columns.Count; j++)
{
table.Rows[i][j] = dataGridView1[j, i].Value.ToString();
}
}
#endregion
var giniIsMin = SeparationTable.GetValueGiniIsPrimaryDivide(table);
Затем каждая промежуточная таблица проходит все те же этапы. Сигналом к завершению деления таблицы служит то, что в последнем столбце (Т) все значения будут либо все равны 1 либо все равны 0. На каждом следующем этапе не участвует в вычислениях один столбец, для которого на предыдущем шаге коэффициент Gini был минимальным. Таким образом строится бинарное дерево решений. Так вот, а теперь собственно сам вопрос: каким образом можно организовать хранение промежуточных таблиц, так чтобы все их обсчитать и что немаловажно не потерять. Предлагали вариант хранить их в трехмерном массиве, укладывая все промежуточные таблицы на позиции 1, 11, 12, 111, 112 и так далее, но такой вариант мы отвергли ввиду его «прожорливости» к памяти. Если кто понял хоть что либо подскажите как такое организовать.
Автор: saphire13
