Метод перекрестной проверки(Cross-validation) с примером реализации

Доброго времени суток! Речь пойдет о задаче классификации. А если быть точнее, то о способе оценить эффективность построенной модели, в частности, о методе перекрестной проверки. Что подразумевается под эффективностью? Конечно же, раз речь идет о классифицирующей модели, то оценивать нужно количество верных ответов.

Чем выше процент правильных ответов, тем больше вероятность, что модель адекватно себя поведет в «полевых условиях» — на реальных данных. Хорошо, когда размер обучающей выборки достаточно велик для того, чтобы выбрать оттуда процентов 30 элементов для тестирования. Но как быть, если данных для обучения очень мало?

На помощь приходит метод перекрестной проверки, в оригинале — Cross-validation.

Суть метода перекрестной проверки

читать далее «Метод перекрестной проверки(Cross-validation) с примером реализации»

Умножение больших чисел — реализация на C/C++

Третья часть из серии статей про реализацию больших чисел на C/C++, в начале по традиции ссылки на предыдущие части.

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

Умножение больших чисел

читать далее «Умножение больших чисел — реализация на C/C++»

Операторы сравнения больших чисел — реализация на C/C++

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

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

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

Важно! Дабы не растягивать и без того длинный листинг исходного кода, я не буду здесь публиковать сам класс BigNumber, его вместе с реализацией сложения, вычитания и нормализации вы можете найти в прошлой статье.

читать далее «Операторы сравнения больших чисел — реализация на C/C++»

Рекурсивное вычисление определителя квадратной матрицы на C/C++

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

Формулы вычисления определителя

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

Для матриц размера 1х1

Значением определителя является единственный элемент матрицы.

Для матриц размера 2х2

Легко посчитать по формуле через перестановки. det = M[0][0]*M[1][1] — M[0][1]*M[1][0], где M — матрица. В реализации алгоритма эта формула будет использована в условии выхода из рекурсии.

читать далее «Рекурсивное вычисление определителя квадратной матрицы на C/C++»

Пузырьковая сортировка — реализация на C/C++

Раз пошло такое дело и я опубликовал свою реализацию быстрой сортировки, с которой вы можете ознакомиться, то как можно обойти стороной самую популярную сортировку? Вообще, спроси у любого студента: «Какую сортировку ты знаешь?», и получишь ответ: «Пузырьком!». Нельзя просто взять и пройти мимо этого факта, мой святой долг стать одним из тысячи человек, которые опубликуют реализацию сортировки пузырьком. Поэтому усаживайтесь поудобнее, мы начинаем!

Суть пузырьковой сортировки

Алгоритм представляет собой проходы по сортируемому массиву, в которых сравниваются два соседних элемента, и, если порядок в них нарушен, то они меняются местами. За каждый проход минимум один элемент встает на свое место — «всплывает» в массиве.

Проход осуществляется двумя циклами: по i и по j. Внешний цикл по i идет от 0 до size-1, где size — размер массива. Важно заметить, что внутренний цикл достаточно прогнать от 0 до size-i-1 так как на i-ом шаге элементы после i-го индекса уже гарантированно отсортированы.

читать далее «Пузырьковая сортировка — реализация на C/C++»