Организация хранения промежуточных таблиц для алгоритма CART

в 8:17, , рубрики: Алгоритмы, Песочница, метки: , ,

Доброго времени суток всем читающим. Сначала изложу предысторию данного вопроса. Началось все с того что знакомый попросил меня по работе помочь ему сделать приложение (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

Источник

Поделиться

* - обязательные к заполнению поля