среда, 4 марта 2009 г.

Пример использования метода box-counting [090304_1]



В примере рассмотрены несколько зависимостей.
Рассчитаны к ним коэффициенты корреляции и коэффициенты по методу box-counting.
В каждой зависимости было взято по 1000 примеров.
Для оценки методом box-counting производилось дробление диапазонов данных на 10 отрезков.

Самая низкая корреляция оказалась в случае с белым шумом (левый верхний график).
Самая высокая корреляция при прямой линейной зависимости (правый нижний график).
Такие-же данные дает метод box-counting.

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

Интересный результат получается в варианте с периодической функцией - синусом. Здесь коэффициент корреляции очень маленький и показывает отсутствие зависимости, а коэффициент рассчитанный по методу box-counting большой и показывает наличие зависимости.

В этом и заключается преимущество метода box-counting перед оценкой по корреляции. Метод box-counting показывает нелинейные зависимости, где метод линейной корреляции бессилен.

См. Метод box-counting

Метод box-counting

Определение.
Метод позволяет определить нелинейную значимость входов для предсказания выходов.

Описание метода.
http://www.intuit.ru/department/expert/neurocomputing/7/6.html
http://iissvit.narod.ru/rass/vip28.htm

Преимущества.
  1. По сравнению с линейными методами (по корреляции) определения значимости входов не требовательна к форме зависимости.
  2. Значение методики box-counting состоит в том, что не находя самого решения, она позволяет быстро предсказать качество этого прогноза.

Недостатки.


Перспективы.
Применение генетических алгоритмов совместно с методикой box-counting.

Примеры:
Пример использования метода box-counting
Влияние кол-ва разбиений на норму box-counting
Влияние на норму box-counting кол-ва тестов и разбиений

Ссылки:
Совершенствование метода box-counting

вторник, 3 марта 2009 г.

Генетические алгоритмы

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.


Алгоритм генетического поиска:

- создание популяции геномов
- цикл по эпохам
- - цикл по элементам популяции
- - - расшифровка текущего генома
- - - создание элемента из расшифрованного генома
- - - тестирование элемента и расчет его качества
- - - сравнение и отбор лучшего элемента по качеству
- - конец цикла
- - трансформация популяции согласно рассчитанному качеству
- конец цикла



Алгоритм трансформации популяции:

- деление популяции геномов на плохую и хорошую
- случайное перемешивание порядка геномов в этих частях
- цикл по половинам популяции
- - скрещивание двух хороших в два новых
- - мутация двух новых геномов
- - замена двух плохих новыми геномами
- конец цикла



Алгоритм скрещивания геномов:

- копирование двух хороших геномов в два новые генома
- цикл вдоль новых геномов по генам
- - запрос случайного с вероятностью 0,5
- - если сработало, то меняем местами текущие гены геномов
- конец цикла



Алгоритм мутации генома:

- цикл вдоль генома по генам
- - запрос случайного с вероятностью равной шоку
- - если сработало, то увеличиваем мутацию в 10 раз
- - добавляем к текущему гену случайное помноженное на мутацию
- - ограничиваем ген по максимуму и минимуму (если выскочил за диапазон)
- конец цикла



Ссылки:
- Материал из Википедии — свободной энциклопедии

Метод k-средних


Кластеризация


Классификация и распознавание


Главные компоненты