ВЫБОР СИСТЕМЫ ИНФОРМАТИВНЫХ ПРИЗНАКОВ ДЛЯ КЛАССИФИКАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ НА ОСНОВЕ ЭВОЛЮЦИОННОГО ПОИСКА. - презентация

1 ВЫБОР СИСТЕМЫ ИНФОРМАТИВНЫХ ПРИЗНАКОВ ДЛЯ КЛАССИФИКАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ НА ОСНОВЕ ЭВОЛЮЦИОННОГО ПОИСКА

2

3 Недостатки классического эволюционного поиска для отбора информативных признаков: – высокая итеративность; – сильная зависимость от начальных условий поиска; – не позволяют отбирать заданное количество признаков. Предложенные методы и модификации: 1. Отбор заданного количества признаков. 2. Кэширование вычисленных значений фитнесс-функции. 3. Эволюционный метод с фиксацией части пространства поиска. 4. Методы эволюционного поиска с использованием априорной информации о значимости признаков Эволюционный поиск с группировкой признаков на основе индивидуальных оценок значимости признаков Эволюционный поиск с использованием энтропии как меры неопределенности состояния объекта Островная модель эволюционного поиска с учетом априорной информации о значимости признаков. 5. Полимодальный эволюционный поиск с кластеризацией хромосом.

4 ОТБОР КОМБИНАЦИИ ИНФОРМАТИВНЫХ ПРИЗНАКОВ ЗАДАННОГО РАЗМЕРА Способ поддержки ограничений в виде заданного количества признаков Критерий t kfkf k Присвоение максимально возможных значений фитнесс-функциям недопустимым хромосомам 331, ,0151 Использование предложенного подхода 297, ,0075 Таблица – Результаты отбора заданного количества признаков Используются модифицированные эволюционные операторы инициализации, скрещивания и мутации, которые генерируют новые решения, соответствующие определенному количеству признаков.

5 ОТБОР КОМБИНАЦИИ ИНФОРМАТИВНЫХ ПРИЗНАКОВ ЗАДАННОГО РАЗМЕРА Рис. Достигнутая ошибка классификации на различных итерациях при использовании различных подходов к отбору заданного количества признаков

6 КЭШИРОВАНИЕ ВЫЧИСЛЕННЫХ ЗНАЧЕНИЙ ФИТНЕСС- ФУНКЦИИ Таблица – Анализ эффективности применения кэширования вычисленных значений фитнесс-функции Используются два массива Н и Е. Н – массив для хранения значений оцененных хромосом. Е – массив со значениями фитнесс-функции, соответствующими хромосомам, представленным в массиве Н. Кэширование Критерий tkfkf k Не используется 297, ,0075 Используется 183, ,0075

7 КЭШИРОВАНИЕ ВЫЧИСЛЕННЫХ ЗНАЧЕНИЙ ФИТНЕСС- ФУНКЦИИ Рис. График суммарного количества вычисленных значений фитнесс-функции

8 ЭВОЛЮЦИОННЫЙ МЕТОД С ФИКСАЦИЕЙ ЧАСТИ ПРОСТРАНСТВА ПОИСКА Повышает эффективность эволюционного поиска за счет исключения на этапе инициализации признаков, незначительно влияющих на целевой параметр. Для оценки индивидуального влияния i-го признака на значение выходного параметра используются критерии: 1) для признаков, имеющих действительные значения: коэффициент парной корреляции: 2) для дискретных признаков: – коэффициент корреляции Фехнера: – коэффициент корреляции знаков:

9 МЕТОДЫ ЭВОЛЮЦИОННОГО ПОИСКА С ИСПОЛЬЗОВАНИЕМ АПРИОРНОЙ ИНФОРМАЦИИ О ЗНАЧИМОСТИ ПРИЗНАКОВ На основании рассчитанных на этапе инициализации индивидуальных оценок значимости признаков приближают начальную точку поиска к оптимальной. Показатели индивидуальной информативности признаков и тесноты связи признаков между собой используются не только на этапе инициализации, но и на всех последующих этапах эволюционного поиска. 1. Эволюционный поиск с группировкой признаков на основе индивидуальных оценок значимости признаков 2. Эволюционный поиск с использованием энтропии как меры неопределенности состояния объекта 3. Островная модель эволюционного поиска с учетом априорной информации о значимости признаков

10 ПОЛИМОДАЛЬНЫЙ ЭВОЛЮЦИОННЫЙ ПОИСК С КЛАСТЕРИЗАЦИЕЙ ХРОМОСОМ Позволяет получить несколько информативных комбинаций, расположенных в различных точках пространства признаков. Группирует наборы информативных признаков в зависимости от их расположения в пространстве признаков: – рассчитывается расстояние Хэмминга d между хромосомами H j и H l : – увеличиваются значения фитнесс-функций хромосом, не являющихся лучшими в кластере, по формуле:

11 РЕЗУЛЬТАТЫ ОТБОРА КОМБИНАЦИИ ПРИЗНАКОВ ПРИ ИСПОЛЬЗОВАНИИ РАЗЛИЧНЫХ ЭВОЛЮЦИОННЫХ МЕТОДОВ Таблица – Сравнительный анализ различных эволюционных методов для выделения системы информативных признаков Метод Критерий tkfkf k Классический эволюционный поиск (КЭП)183, ,0075 Эволюционный метод с фиксацией части пространства поиска (ЭМФЧПП) 133,495100,009 Эволюционный поиск с группировкой признаков на основе индивидуальных оценок значимости признаков (ЭПГПОИОЗ) 102,771100,0075 Эволюционный поиск с использованием энтропии (ЭПИЭ) 109,87590,0068 Островная модель эволюционного поиска (ОМЭП) 106,974100,0075 Полимодальный эволюционный поиск с кластеризацией хромосом (ПЭПКХ) 142, ,0083

12 РЕЗУЛЬТАТЫ ОТБОРА КОМБИНАЦИИ ПРИЗНАКОВ ПРИ ИСПОЛЬЗОВАНИИ РАЗЛИЧНЫХ ЭВОЛЮЦИОННЫХ МЕТОДОВ Рис. Достигнутая ошибка классификации на различных итерациях при использовании различных эволюционных методов