Машинное обучение

Последним нерассмотренным полем структуры CvSVMParams является term_crit. Данная переменная содержит параметры итерационного метода, используемого для решения оптимизационной задачи на этапе обучения. Данные параметры указываются с помощью следующей структуры:

struct CvTermCriteria 
{ 
    int    type; 
    int    max_iter; 
    double epsilon; 
}; 

Рассмотрим поля данной структуры:

Для использования обученной ранее модели в классе CvSVM используются методы

float predict( const Mat< sample, 
               bool returnDFVal=false ) const; 
void predict( InputArray samples, 
              OutputArray results ) const; 
              

Рассмотрим их параметры.

Для сохранения обученной модели используется метод

void save( const char* filename, 
           const char* name=0 ) const;
            

Параметры данного метода:

Загрузка модели из файла осуществляется методом

void load( const char* filename, const char* name=0 ); 

Рассмотрим его параметры:

Также в классе CvSVM реализован метод, позволяющий получить количество опорных векторов:

int get_support_vector_count() const; 

и метод для получения опорного вектора с номером :

const float* get_support_vector(int i) const; 
 

Рассмотрим пример использования класса CvSVM для решения задачи классификации.

#include <stdlib.h> 
#include <stdio.h> 
#include <opencv2/core/core.hpp> 
#include <opencv2/ml/ml.hpp> 
 
using namespace cv; 
 
// размерность пространства признаков 
const int d = 2; 
 
// функция истинной зависимости целевого признака 
// от остальных 
int f(Mat sample) 
{ 
    return (int)((sample.at<float>(0) < 0.5f  
                  sample.at<float>(1) < 0.5f) || 
                 (sample.at<float>(0) > 0.5f  
                  sample.at<float>(1) > 0.5f)); 
} 
 
int main(int argc, char* argv[]) { 
    // объем генерируемой выборки 
    int n = 2000; 
    // объем обучающей части выборки 
    int n1 = 1000; 
     
    // матрица признаковых описаний объектов 
    Mat samples(n, d, CV_32F); 
    // номера классов (матрица значений целевой переменной) 
    Mat labels(n, 1, CV_32S); 
    // генерируем случайным образом точки 
    // в пространстве признаков 
    randu(samples, 0.0f, 1.0f); 
 
    // вычисляем истинные значения целевой переменной 
    for (int i = 0; i < n; ++i) 
    { 
        labels.at<int>(i) = f(samples.row(i)); 
    } 
 
    // создаем маску прецедентов, которые будут 
    // использоваться для обучения: используем n1 
    // первых прецедентов 
    Mat trainSampleMask(1, n1, CV_32S); 
    for (int i = 0; i < n1; ++i) 
    { 
        trainSampleMask.at<int>(i) = i; 
    } 
 
    // используем SVM типа C_SVC и радиальным ядром 
    CvSVMParams params; 
    params.svm_type = CvSVM::C_SVC; 
    params.kernel_type = CvSVM::RBF; 
    params.gamma = 1.0; 
    params.C = 1.0; 
 
    CvSVM svm; 
    svm.train(samples, labels, 
              Mat(), trainSampleMask, params); 
    svm.save("model.yml", "simpleSVMModel"); 
     
    // вычисляем ошибку на обучающей выборке 
    Mat predictions; 
    svm.predict(samples.rowRange(0, n1), predictions); 
    float trainError = 0.0f; 
    for (int i = 0; i < n1; ++i) 
    { 
        trainError += (labels.at<int>(i) !=  
                       (int)(predictions.at<float>(i))); 
    }     trainError /= float(n1); 
 
    // вычисляем ошибку на тестовой выборке 
    predictions = Mat(); 
    svm.predict(samples.rowRange(n1, n), predictions); 
    float testError = 0.0f; 
    for (int i = 0; i < n - n1; ++i) 
    { 
        testError += (labels.at<int>(n1 + i) !=  
                      (int)(predictions.at<float>(i))); 
    } 
    testError /= float(n - n1); 
 
    printf("train error = %.4f\ntest error = %.4f\n", 
           trainError, testError); 
     
    return 0; 
} 

Визуальное представление данных и построенной границы между точками разных классов приведено на рис. 10.1.

2.3. Дерево решений

Идея, лежащая в основе алгоритма обучения дерева решений, состоит в рекурсивном разбиении пространства признаков с помощью простых правил на непересекающиеся области. Полученная в результате обучения модель представляет собой дерево, где каждому внутреннему узлу соответствует некоторая область пространства признаков и правило ее разбиения на подобласти ($$x_j \leqslant c$$, если -й признак количественный и $$x_j \in L$$ , если признак категориальный). Каждой листовой вершине также соответствует область пространства $$\mathcal{X}$$ и приписано константное значение, которому принимается равной функция $$f$$ в данной области.

Алгоритм обучения дерева решений, осуществления с его помощью предсказаний, сохранения/загрузки модели, а также дополнительный функционал по работе с деревьями решений реализованы в библиотеке OpenCV в классе CvDTree. Остановимся подробнее на описании данного класса.

Для обучения дерева решений служит метод train.

bool train( const Mat< trainData, 
            int tflag, 
            const Mat< responses, 
            const Mat< varIdx=Mat(), 
            const Mat< sampleIdx=Mat(), 
            const Mat< varType=Mat(), 
            const Mat< missingDataMask=Mat(), 
            CvDTreeParams params=CvDTreeParams() ); 
            

Рассмотрим параметры метода.

Для представления параметров алгоритма обучения дерева решений используется структура CvDTreeParams:

struct CvDTreeParams 
{ 
    int   max_categories; 
    int   max_depth; 
    int   min_sample_count; 
    int   cv_folds; 
    bool  use_surrogates; 
    bool  use_1se_rule; 
    bool  truncate_pruned_tree; 
    float regression_accuracy; 
    const float* priors; 
 
    CvDTreeParams(); 
    CvDTreeParams( int max_depth, 
                   int min_sample_count, 
                   float regression_accuracy, 
                   bool use_surrogates, 
                   int max_categories, 
                   int cv_folds,                    bool use_1se_rule, 
                   bool truncate_pruned_tree, 
                   const float* priors ); 
}; 

Остановимся подробнее на описании данной структуры.

Предсказания с помощью предварительно обученной модели выполняются с помощью метода predict:

CvDTreeNode* predict( const Mat< sample, 
                      const Mat< missingDataMask=Mat(), 
                      bool preprocessedInput=false ) const; 
                      

Рассмотрим параметры данного метода:

Следует отметить, что метод CvDTree::predict возвращает указатель на структуру, описывающую узел дерева. Само предсказанное моделью значение целевого признака хранится в поле value данной структуры.

Сохранение модели дерева решений в файл и загрузка из него выполняется с помощью методов save и load, использование которых полностью совпадает с аналогичными методами класса CvSVM, описанными выше.

Следует отметить, что класс CvDTree также содержит дополнительный функционал, например, для определения значимости различных переменных для восстановления зависимости от , что, однако, выходит за рамки данной лабораторной работы и может быть предоставлено для самостоятельного изучения [7].

Приведем пример использования класса CvDTree для решения задачи бинарной классификации аналогичной, решаемой в примере для CvSVM.

#include <stdlib.h> 
#include <stdio.h> 
#include <opencv2/core/core.hpp> 
#include <opencv2/ml/ml.hpp> 
 
using namespace cv; 
 
// размерность пространства признаков 
const int d = 2; 
 
// функция истинной зависимости целевого признака 
// от остальных 
int f(Mat sample) 
{ 
    return (int)((sample.at<float>(0) < 0.5f  
                  sample.at<float>(1) < 0.5f) || 
                 (sample.at<float>(0) > 0.5f  
                  sample.at<float>(1) > 0.5f)); 
} 
 
int main(int argc, char* argv[]) 
{ 
    // объем генерируемой выборки 
    int n = 2000; 
    // объем обучающей части выборки 
    int n1 = 1000; 
     
    // матрица признаковых описаний объектов 
    Mat samples(n, d, CV_32F); 
    // номера классов (матрица значений целевой переменной)     Mat labels(n, 1, CV_32S); 
    // генерируем случайным образом точки 
    // в пространстве признаков 
    randu(samples, 0.0f, 1.0f); 
 
    // вычисляем истинные значения целевой переменной 
    for (int i = 0; i < n; ++i) 
    { 
        labels.at<int>(i) = f(samples.row(i)); 
    } 
 
    // создаем маску прецедентов, которые будут 
    // использоваться для обучения: используем n1 
    // первых прецедентов 
    Mat trainSampleMask(1, n1, CV_32S); 
    for (int i = 0; i < n1; ++i) 
    { 
        trainSampleMask.at<int>(i) = i; 
    } 
 
    // будем обучать дерево решений высоты не больше 10, 
    // после построения которого выполним отсечения 
    // с помощью пятикратного перекресного контроля 
    CvDTreeParams params; 
    params.max_depth = 10; 
    params.min_sample_count = 1; 
    params.cv_folds = 5; 
 
    CvDTree dtree; 
    Mat varIdx(1, d, CV_8U, Scalar(1)); 
    Mat varTypes(1, d + 1, CV_8U, Scalar(CV_VAR_ORDERED)); 
    varTypes.at<uchar>(d) = CV_VAR_CATEGORICAL; 
    dtree.train(samples, CV_ROW_SAMPLE, 
                labels, varIdx, 
                trainSampleMask, varTypes, 
                Mat(), params); 
    dtree.save("model-dtree.yml", "simpleDTreeModel"); 
     
    // вычисляем ошибку на обучающей выборке 
    float trainError = 0.0f; 
    for (int i = 0; i < n1; ++i) 
    { 
        int prediction = 
            (int)(dtree.predict(samples.row(i))->value); 
        trainError += (labels.at<int>(i) != prediction); 
    } 
    trainError /= float(n1); 
 
    // вычисляем ошибку на тестовой выборке 
    float testError = 0.0f;     for (int i = 0; i < n - n1; ++i) 
    { 
        int prediction =  
          (int)(dtree.predict(samples.row(n1 + i))->value); 
        testError += 
            (labels.at<int>(n1 + i) != prediction); 
    } 
    testError /= float(n - n1); 
 
    printf("train error = %.4f\ntest error = %.4f\n", 
           trainError, testError); 
     
    return 0; 
} 

Иллюстрацией разбиения пространства признаков обученным с помощью данного кода деревом решений служит рис. 10.2.

2.4. Случайный лес

Случайный лес является бэггинг алгоритмом, основная идея которого заключается в построении как можно менее зависимых друг от друга деревьев решений, с последующим принятием решения путем усреднения в случае регрессии и голосованием в случае классификации. Зависимость между деревьями снижается за счет использования случайной выборки с возвращением из исходных прецедентов и случайного подмножества признаков.

Алгоритм случайного леса реализован в библиотеке OpenCV в виде класса CvRTrees. Рассмотрим принципы работы с данным классом. Для обучения случайного леса предназначен метод train:

bool train( const Mat< trainData, 
            int tflag, 
            const Mat< responses, 
            const Mat< varIdx=Mat(), 
            const Mat< sampleIdx=Mat(), 
            const Mat< varType=Mat(), 
            const Mat< missingDataMask=Mat(), 
            CvRTParams params=CvRTParams() );

Назначение и формат параметров данного метода целиком совпадает с методом CvDTree::train, реализующим обучение одиночного дерева решений, за исключением параметров алгоритма обучения. Параметры случайного леса представляются в виде структуры CvRTParams:

struct CvRTParams : public CvDTreeParams 
{ 
    bool calc_var_importance; 
    int nactive_vars; 
    CvTermCriteria term_crit; 
 
    CvRTParams(); 
    CvRTParams( int max_depth, 
                int min_sample_count, 
                float regression_accuracy, 
                bool use_surrogates, 
                int max_categories, 
                const float* priors, 
                bool calc_var_importance, 
                int nactive_vars, 
                int max_num_of_trees_in_the_forest, 
                float forest_accuracy, 
                int termcrit_type ); 
}; 

Так как алгоритм случайного леса строит деревья решений, большинство параметров определяют настройки алгоритма обучения одиночных деревьев (см. описание структуры CvDTreeParams). Следует отметить, что в рамках модели случайного леса обучаются большие (оригинальный подход [4] не подразумевал ограничение высоты дерева как критерий останова его построения) деревья решений без последующего применения процедуры отсечения. Теперь рассмотрим параметры, имеющие отношение непосредственно к модели случайного леса:

Для осуществления предсказаний в классе CvRTrees предназначен метод predict:

float predict( const Mat< sample, 
               const Mat< missing=Mat() ) const;
               

Параметрами метода являются признаковое описание объекта и маска пропущенных значений в данном описании. Возвращаемое значение соответствует предсказанной величине целевого признака.

Методы save и load, осуществляющие сохранение и загрузку модели соответственно, применяются аналогично данным методам классов CvSVM и CvDTree.

Приведем пример использования класса CvRTrees для решения задачи бинарной классификации и иллюстрацию порождаемого обученной моделью разбиения пространства признаков (см. рис. 10.3).

#include <stdlib.h> 
#include <stdio.h> 
#include <opencv2/core/core.hpp> 
#include <opencv2/ml/ml.hpp> 
 
using namespace cv; 
 // размерность пространства признаков 
const int d = 2; 
 
// функция истинной зависимости целевого признака 
// от остальных 
int f(Mat sample) 
{ 
    return (int)((sample.at<float>(0) < 0.5f  
                  sample.at<float>(1) < 0.5f) || 
                 (sample.at<float>(0) > 0.5f  
                  sample.at<float>(1) > 0.5f)); 
} 
 
int main(int argc, char* argv[]) 
{ 
    // объем генерируемой выборки 
    int n = 2000; 
    // объем обучающей части выборки 
    int n1 = 1000; 
     
    // матрица признаковых описаний объектов 
    Mat samples(n, d, CV_32F); 
    // номера классов (матрица значений целевой переменной) 
    Mat labels(n, 1, CV_32S); 
    // генерируем случайным образом точки 
    // в пространстве признаков 
    randu(samples, 0.0f, 1.0f); 
 
    // вычисляем истинные значения целевой переменной 
    for (int i = 0; i < n; ++i) 
    { 
        labels.at<int>(i) = f(samples.row(i)); 
    } 
 
    // создаем маску прецедентов, которые будут 
    // использоваться для обучения: используем n1 
    // первых прецедентов 
    Mat trainSampleMask(1, n1, CV_32S); 
    for (int i = 0; i < n1; ++i) 
    { 
        trainSampleMask.at<int>(i) = i; 
    } 
 
    // будем обучать случайный лес из 250 деревьев 
    // высоты не больше 10 
    CvRTParams params; 
    params.max_depth = 10; 
    params.min_sample_count = 1; 
    params.calc_var_importance = false; 
    params.term_crit.type = CV_TERMCRIT_ITER;     params.term_crit.max_iter = 250; 
 
    CvRTrees rf; 
    Mat varIdx(1, d, CV_8U, Scalar(1)); 
    Mat varTypes(1, d + 1, CV_8U, Scalar(CV_VAR_ORDERED)); 
    varTypes.at<uchar>(d) = CV_VAR_CATEGORICAL; 
    rf.train(samples, CV_ROW_SAMPLE, 
             labels, varIdx, 
             trainSampleMask, varTypes, 
             Mat(), params); 
    rf.save("model-rf.yml", "simpleRTreesModel"); 
     
    // вычисляем ошибку на обучающей выборке 
    float trainError = 0.0f; 
    for (int i = 0; i < n1; ++i) 
    { 
        int prediction = 
            (int)(rf.predict(samples.row(i))); 
        trainError += (labels.at<int>(i) != prediction); 
    } 
    trainError /= float(n1); 
 
    // вычисляем ошибку на тестовой выборке 
    float testError = 0.0f; 
    for (int i = 0; i < n - n1; ++i) 
    { 
        int prediction =  
          (int)(rf.predict(samples.row(n1 + i))); 
        testError += 
            (labels.at<int>(n1 + i) != prediction); 
    } 
    testError /= float(n - n1); 
 
    printf("train error = %.4f\ntest error = %.4f\n", 
           trainError, testError); 
     
    return 0; 
}  

2.5. Градиентный бустинг деревьев решений

Градиентный бустинг, как и любой бустинг алгоритм, последовательно строит базовые модели так, что каждая следующая улучшает качество всего ансамбля. Градиентный бустинг деревьев решений строит модель в виде суммы деревьев $$f(x)=h_0+v \cdot \sum^M_{j=1} h_j(x)$$ , где $$h_0$$ – некоторая константная модель (начальное приближение), $$v \in (0,1]$$ – параметр, регулирующий скорость обучения и влияние отдельных деревьев на всю модель, $$h_j(x)$$ – регрессионные деревья решений. Новые слагаемые-деревья добавляются в сумму путем жадной минимизации эмпирического риска, заданного некоторой функцией потерь $$L(y,y')=L(y,f(x))$$ . Данный метод без серьезной модификации может применяться для любой дифференцируемой функции потерь.

Метод градиентного бустинга деревьев решений в библиотеке OpenCV реализован в виде класса CvGBTrees. Для запуска обучения модели реализован метод train:

bool train( const Mat< trainData, 
            int tflag, 
            const Mat< responses, 
            const Mat< varIdx=Mat(), 
            const Mat< sampleIdx=Mat(), 
            const Mat< varType=Mat(),             const Mat< missingDataMask=Mat(), 
            CvGBTreesParams params=CvGBTreesParams(), 
            bool update=false );
            

Использование данного метода аналогично рассмотренным ранее алгоритмам за исключением следующих моментов: параметр update на настоящий момент является фиктивным, не поддерживается задание используемых прецедентов с помощью маски, по умолчанию обучается регрессионная модель (для обучения классификатора необходимо явно задать категориальный тип целевого признака и выбрать соответствующую функцию потерь). Параметры алгоритма обучения модели градиентного бустинга деревьев решений представляются структурой CvGBTreesParams:

struct CvGBTreesParams : public CvDTreeParams 
{ 
    int weak_count; 
    int loss_function_type; 
    float subsample_portion; 
    float shrinkage; 
 
    CvGBTreesParams(); 
    CvGBTreesParams( int loss_function_type, 
                     int weak_count, 
                     float shrinkage, 
                     float subsample_portion, 
                     int max_depth, 
                     bool use_surrogates ); 
}; 

Рассмотрим значения ее полей:

enum  {SQUARED_LOSS=0,  ABSOLUTE_LOSS,  HUBER_LOSS=3, 
DEVIANCE_LOSS}; 

Предсказания с помощью модели градиентного бустинга деревьев решений выполняет метод predict:

float predict( const Mat sample, 
               const Mat missing=Mat(), 
               const Range slice=Range::all(), 
               int k=-1 ) const; 
               

Рассмотрим параметры данного метода:

Сохранение и загрузка модели выполняется так же, как и в рассмотренных ранее алгоритмах.

Ниже приведен пример использования класса CvGBTrees для решения задачи бинарной классификации и иллюстрация полученного классификатора (см. рис. 10.4)

#include <stdlib.h> 
#include <stdio.h> 
#include <opencv2/core/core.hpp> 
#include <opencv2/ml/ml.hpp> 
 
using namespace cv;  
// размерность пространства признаков 
const int d = 2; 
 
// функция истинной зависимости целевого признака 
// от остальных 
int f(Mat sample) 
{ 
    return (int)((sample.at<float>(0) < 0.5f  
                  sample.at<float>(1) < 0.5f) || 
                 (sample.at<float>(0) > 0.5f  
                  sample.at<float>(1) > 0.5f)); 
} 
 
int main(int argc, char* argv[]) 
{ 
    // объем генерируемой выборки 
    int n = 2000; 
    // объем обучающей части выборки 
    int n1 = 1000; 
     
    // матрица признаковых описаний объектов 
    Mat samples(n, d, CV_32F); 
    // номера классов (матрица значений целевой переменной) 
    Mat labels(n, 1, CV_32S); 
    // генерируем случайным образом точки 
    // в пространстве признаков 
    randu(samples, 0.0f, 1.0f); 
 
    // вычисляем истинные значения целевой переменной 
    for (int i = 0; i < n; ++i) 
    { 
        labels.at<int>(i) = f(samples.row(i)); 
    } 
 
    // создаем маску прецедентов, которые будут 
    // использоваться для обучения: используем n1 
    // первых прецедентов 
    Mat trainSampleMask(1, n1, CV_32S); 
    for (int i = 0; i < n1; ++i) 
    { 
        trainSampleMask.at<int>(i) = i; 
    } 
 
    // будем обучать модель градиентного бустинга 
    // деревьев решений из 250 деревьев высоты 3 и 
    // скоростью обучения 0.5,без использования подвыборок. 
    // Т.к. решается задача классификации используем 
    // функцию потерь DEVIANCE_LOSS 
    CvGBTreesParams params;     params.max_depth = 3; 
    params.min_sample_count = 1; 
    params.weak_count = 250; 
    params.shrinkage = 0.5f; 
    params.subsample_portion = 1.0f; 
    params.loss_function_type = CvGBTrees::DEVIANCE_LOSS; 
 
    CvGBTrees gbt; 
    Mat varIdx(1, d, CV_8U, Scalar(1)); 
    Mat varTypes(1, d + 1, CV_8U, Scalar(CV_VAR_ORDERED)); 
    varTypes.at<uchar>(d) = CV_VAR_CATEGORICAL; 
    gbt.train(samples, CV_ROW_SAMPLE, 
              labels, varIdx, 
              trainSampleMask, varTypes, 
              Mat(), params); 
    gbt.save("model-gbt.yml", "simpleGBTreesModel"); 
     
    // вычисляем ошибку на обучающей выборке 
    float trainError = 0.0f; 
    for (int i = 0; i < n1; ++i) 
    { 
        int prediction = 
            (int)(gbt.predict(samples.row(i))); 
        trainError += (labels.at<int>(i) != prediction); 
    } 
    trainError /= float(n1); 
 
    // вычисляем ошибку на тестовой выборке 
    float testError = 0.0f; 
    for (int i = 0; i < n - n1; ++i) 
    { 
        int prediction =  
          (int)(gbt.predict(samples.row(n1 + i))); 
        testError += 
            (labels.at<int>(n1 + i) != prediction); 
    } 
    testError /= float(n - n1); 
 
    printf("train error = %.4f\ntest error = %.4f\n", 
           trainError, testError); 
     
    return 0; 
}  

3. Обзор возможностей библиотеки OpenCV для решения задач обучения без учителя

3.1. Задача кластеризации

Задача кластеризации заключается в разбиении выборки $$\lbrace x^{(i)},i=\overline{1,N} \rbrace$$ на непересекающиеся подмножества таким образом, чтобы схожие точки (обычно близкие в некоторой метрике) попали в одно подмножество (кластер), а точки из разных кластеров сильно друг от друга отличались (были далеки). Для решения данной задачи в библиотеки OpenCV реализован метод центров тяжести (k-means) и EM-алгоритм. В данной лабораторной работе рассматривается использование программной реализации метод центров тяжести, как одного из наиболее популярных алгоритмов кластеризации на настоящий момент.

3.2. Метод центров тяжести (k-means)

Метод центров тяжести разбивает выборку на заданное количество кластеров K путем выбора их центров. Поиск центров кластеров производится из соображений минимизации суммарного расстояния от каждой точки до ближайшего центра с помощью метода локальной оптимизации. Так как алгоритм не гарантирует достижения глобального минимума, ключевую роль играет начальная инициализация центров кластеров. Распространенным методом является случайный (с равной вероятностью) выбор K точек из имеющегося множества $$\lbrace x^{(i)},i=\overline{1,N} \rbrace$$. Однако алгоритм центров тяжести, запущенный на таких начальных данных может выдать в результате локальный минимум сколь угодно хуже глобального. Альтернативой является метод k-means++ [5], предложенный Д. Артуром и С. Вассильвицким, основанный на последовательном выборе K точек из выборки случайным образом, но с вероятностью пропорциональной квадрату расстояния от точки до ближайшего уже выбранного центра. В данном случае, математическое ожидание отношения найденного минимума к глобальному является величиной $$O(log K)$$.

Метод центров тяжести с евклидовой метрикой реализован в библиотеке OpenCV в виде функции kmeans модуля core:

double kmeans( InputArray data, 
               int K, 
               InputOutputArray bestLabels, 
               TermCriteria criteria, 
               int attempts, 
               int flags, 
               OutputArray centers=noArray() ); 
               

Рассмотрим параметры данной функции:

Данная функция возвращает сумму квадратов расстояний от каждой точки до ближайшего к ней центра.

Рассмотрим пример использования функции kmeans для кластеризации точек на плоскости. Результат полученной кластеризации приведен на рис. 10.5.

#include <opencv2/core/core.hpp> 
 
using namespace cv; 
 
Mat generateDataset() 
{ 
    int n = 300; 
    Mat data(3 * n, 2, CV_32F); 
     
    randn(data(Range(0, n), Range(0, 1)), 0.0, 0.05); 
    randn(data(Range(0, n), Range(1, 2)), 0.5, 0.25); 
 
    randn(data(Range(n, 2 * n), Range(0, 1)), 0.7, 0.25); 
    randn(data(Range(n, 2 * n), Range(1, 2)), 0.0, 0.05); 
 
    randn(data(Range(2 * n, 3 * n), Range(0, 1)), 
          0.7, 0.15); 
    randn(data(Range(2 * n, 3 * n), Range(1, 2)), 
          0.8, 0.15); 
     
    return data; 
} 
 
int main(int argc, char* argv[]) 
{ 
    Mat samples = generateDataset(); 
 
    Mat labels; 
    Mat centers; 
    kmeans(samples, 
        3, 
        labels, 
        TermCriteria(TermCriteria::COUNT + 
                     TermCriteria::EPS, 10000, 0.001),         10, 
        KMEANS_PP_CENTERS, 
        centers); 
     
    return 0; 
} 

4. Программная реализация

4.1. Разработка приложения для решения задач классификации

4.1.1. Требования к приложению

В рамках данной лабораторной работы предлагается разработать приложение для решения задач классификации, предусматривающее возможность применения рассмотренных выше алгоритмов машинного обучения. К приложению предъявляются следующие требования:

4.1.2. Структура приложения

Приложение будет состоять из набора модулей (cvsvm.cpp/h, cvdtree.cpp/h, cvrtrees.cpp/h, cvgbtrees.cpp/h), каждый из которых предназначен для работы (запрос у пользователя параметров, обучение и предсказание) рассматриваемых алгоритмов обучения, модуля вычисления ошибки классификации (errorMetrics.cpp/h), модуля визуализации данных (drawingFunctions.cpp/h) и основного модуля (main.cpp), содержащего общую логику работы программы. Основной модуль и модуль визуализации предоставляются в реализованном виде, следовательно, необходимо реализовать непосредственно работу с различными алгоритмами обучения с учителем. Далее рассматриваются интерфейсы готовых функций, а также функционал, который предлагается реализовать самостоятельно.

Модуль визуализации данных содержит функцию рисования точек из двумерного пространства признаков drawPoints:

void drawPoints(Mat  img, 
                const Mat  data, 
                const Mat  classes, 
                const Mat  ranges, 
                std::map<int, Scalar>  classColors, 
                int drawingMode = 0); 
                

В качестве аргументов данная функция принимает:

Функция drawPartition позволяет отображать разбиение пространства признаков на области, соответствующие разным классам, путем вычисления предсказаний на равномерной сетке:

void drawPartition(Mat  img, 
                   map<int, Scalar>  classColors, 
                   const Mat  dataRanges, 
                   const Size stepsNum, 
                   const CvStatModel  model, 
                   getPredictedClassLabel * predictLabel); 
                   

Параметры функции:

Функция getRanges предназначена для поиска матрицы минимальных и максимальных значений каждого признака в выборке data:

 
Mat getRanges(const Mat  data); 

Функция readDatasetFromFile позволяет считать данные (обучающую и тестовую выборки) из XML- или YAML-файла.

 
void readDatasetFromFile(Mat  featuresTrain, 
                         Mat  classesTrain, 
                         Mat  featuresTest, 
                         Mat  classesTest); 
                         

Файл должен содержать матрицы признаков объектов обучающей ("featuresTrain") и тестовой ("featuresTest") выборок и соответствующих им классов ("classesTrain" и "classesTest") в формате OpenCV. Матрицы classesTrain и classesTest должны иметь тип CV_32S, featuresTrain и featuresTest – CV_32F.

Основная логика программы сосредоточена в модуле main.cpp и выглядит следующим образом:

Перейдем к рассмотрению функций, которые предлагается реализовать самостоятельно. Прежде всего, это функции, запускающие обучение моделей:

void trainSVM(const Mat  trainSamples, 
              const Mat  trainClasses, 
              const CvSVMParams  params, 
              CvSVM  svm); 
void trainDTree(const Mat  trainSamples, 
                const Mat  trainClasses, 
                const CvDTreeParams  params, 
                CvDTree  dtree); 
void trainRTrees(const Mat  trainSamples, 
                 const Mat  trainClasses, 
                 const CvRTParams  params, 
                 CvRTrees  rtrees); 
void trainGBTrees(const Mat  trainSamples, 
                  const Mat  trainClasses, 
                  const CvGBTreesParams  params, 
                  CvGBTrees  gbtrees); 
                  

Данные функции находятся в файлах cvsvm.cpp, cvdtree.cpp, cvrtrees.cpp, cvgbtrees.cpp соответственно. В теле каждой функции требуется вызвать метод переданного в нее объекта для обучения модели на данных trainSamples (матрица признаковых описаний объектов) и trainClasses (матрица номеров классов) с параметрами params. Также требуется реализация функций для предсказания:

int getSVMPrediction(const Mat  sample, 
                     const CvStatModel  model); 
int getDTreePrediction(const Mat  sample, 
                       const CvStatModel  model); 
int getRTreesPrediction(const Mat  sample, 
                        const CvStatModel  model); 
int getGBTreesPrediction(const Mat  sample, 
                         const CvStatModel  model); 
                         

Функции, принимают признаковое описание объекта sample и обученную модель model, возвращая номер предсказанного класса. Интерфейс данных функций унифицирован для более простого подсчета ошибок на обучающей и тестовой выборках. Функции принимают объекты базового типа CvStatModel, однако, фактичеси это должны быть объекты соответствующих классов: для getSVMPrediction объект класса CvSVM, для getDTreePrediction – CvDTree и т.д.

Также предлагается реализовать функцию getSupportVectors (файл cvsvm.cpp), принимающую обученную машину опорных векторов svm и возвращающую матрицу, где каждая строка соответствует опорному вектору:

Mat getSupportVectors(const CvSVM  svm); 

Функции запроса параметров каждого из рассматриваемых алгоритмов обучения предоставляются в готовом виде и рекомендуются для самостоятельного разбора.

Также в рамках лабораторной работы предлагается реализовать функцию вычисления ошибки классификации (долю неправильно классифицированных объектов выборки) getClassificationError:

float getClassificationError(const Mat  samples, 
      const Mat  classes, 
      const CvStatModel  model, 
      int (*predict) (const Mat  sample, 
                      const CvStatModel  model)); 
                      

Параметры функции:

Данная функция должна вычислять доля неправильно классифицированных объектов выборки.

После того, как описанные функции будут реализованы, предлагается применить рассмотренные алгоритмы классификации к наборам данных из файлов dataset1.yml, dataset2.yml, dataset3.yml, dataset4.yml, datasetMulticlass.yml и datasetHighDim.yml. А также проанализировать, на каких данных лучше/хуже работает тот или иной подход и какое влияние на конечную модель оказывают параметры алгоритма обучения.

4.2. Разработка приложения для решения задач кластеризации

4.2.1. Требования к приложению

Также в рамках данной лабораторной работы предлагается разработать приложение для кластеризации точек методом центров тяжести. К приложению предъявляются следующие требования:

4.2.2. Структура приложения

Приложение будет состоять из двух модулей: основной (main.cpp) и модуль визуализации (drawingFunctions.cpp/h). Функции визуализации предоставляются в готовом виде и аналогичны описанным в разделе 4.1.2.

В основном модуле должна выполняться следующая последовательность действий:

Код, необходимый для загрузки и визуализации предоставляется в готовом виде, следовательно, требуется лишь написать вызов функции кластеризации kmeans.

После того, как код основного модуля будет дописан, предлагается запустить программу на предоставленных наборах данных (dataset1.yml, dataset2.yml, dataset3.yml, dataset4.yml) и проанализировать полученные результаты.

Контрольные вопросы

6. Дополнительные задания