Системы data mining. Генетические алгоритмы
Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер.
Можно выделить следующие этапы генетического алгоритма:
1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию
(Начало цикла)
1. Размножение (скрещивание)
2. Мутирование
3. Вычислить значение целевой функции для всех особей
4. Формирование нового поколения (селекция)
5. Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
• нахождение глобального, либо субоптимального решения;
• исчерпание числа поколений, отпущенных на эволюцию;
• исчерпание времени, отпущенного на эволюцию.
Мутирование (мутация) и скрещивание (кроссовер) относятся к генетическим операторам, которые моделируют механизмы передачи наследственности живой природы.
На практике применяются и другие операторы. Например, так как размножение в генетических алгоритмах требует для производства потомка нескольких родителей, обычно двух, можно выделить несколько операторов выбора родителей:
• Панмиксия — оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной
• Инбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя
• Аутбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя
Генетические алгоритмы применяются для решения следующих задач:
• Оптимизация функций
• Оптимизация запросов в базах данных
• Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
• Настройка и обучение искусственной нейронной сети
• Задачи компоновки
• Составление расписаний
• Игровые стратегии
• Биоинформатика (фолдинг белков)
Обзор рынка data mining.
Класс систем Data Mining. Data Mining является мультидисциплинарной областью, возникшей и развивающейся на базе достижений прикладной статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. Многие из таких систем интегрируют в себе сразу несколько подходов. Тем не менее, как правило, в каждой системе имеется какая-то ключевая компонента, на которую делается главная ставка.
Ниже данные для наиболее популярных инструментов, отображающие для каждого инструмента процент людей, который когда-либо пользовался данным инструментом согласно данным опроса на популярном сайте по тематике анализа данных kdnuggets.com.
Как видно, наиболее популярными являются язык R и Python. R «заточен» под статистическую обработку данных, работу с графикой и алгоритмами машинного обучения. Python имеет шесть специализированных библиотек для анализа данных:
• Pandas – отвечает за обработку данных;
• Numphy – работает с матрицами;
• Statsmodels – содержит основные статистические функции и модели;
• Sklearn и Pybrain – специализируются на алгоритмах машинного обучения;
• Matplotlib отвечает за визуализацию.
Ниже результаты сравнения четырех инструментов из таблицы выше (R, Python, RapidMiner, KNIME) + инструмента Weka. Все эти инструменты либо полностью бесплатны, либо имеют бесплатные ограниченные версии (RapidMiner). Напротив функции отображен продукт, лучше всего с ней справляющийся.
Далее инструменты, делающие акцент на определенное направление data mining:
• Статистические пакеты – SAS, SPSS, STATGRAPICS (Manugistics), STATISTICA, STADIA и др
• Нейронные сети - BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic).
• Деревья решений - See5/C5.0, Clementine, SIPINA, IDIS, KnowledgeSeeker
• Генетические алгоритмы - GeneHunter. Его стоимость – около 1000 долл.