Вопрос 100. Методы поиска логических закономерностей

Первые попытки применения математических методов в отечественной социологии были сделаны новосибирскими учеными из Института экономики и организации промышленного производства и Института математики Сибирского отделения АН СССР, создавшими к началу 70-х гг. подлинную школу математической социологии, существующую до настоящего времени. Группа ученых ИМ, руководимая Н.Г. Загоруйко и Г.С. Лбовым, разработала оригинальную теорию поиска закономерностей, задаваемых всевозможными логическими сочетаниями значений признаков, измеренных по шкалам произвольных типов. Решаемые при этом задачи схожи с теми, решение которых достигается с помощью известных алгоритмов типа AID (Automatic Interaction Detector), направленных на поиск взаимодействий. Эти алгоритмы очень часто используются в западной социологии и содержатся, в частности, в известном пакете SPSS. Алгоритмы AID позволяют искать сочетания значений рассматриваемых признаков, детерминирующие определенное "поведение" респондента. С помощью разработок новосибирцев можно рассматривать более разнообразные виды "поведения" и учитывать разные логические функции от значений признаков.

Логическая закономерность в задачах классификации — легко интерпретируемое правило, выделяющее из выборки достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов. Логические закономерности являются элементарными «строительными блоками» для широкого класса логических алгоритмов классификации, называемых также алгоритмами индукции правил.

Методы поиска закономерностей позволяют выявлять логические функции от сочетаний значений разных признаков, истинные для рассматриваемых совокупностей объектов: Стохастический локальный поиск; Алгоритм КОРА (поиск в глубину или метод ветвей и границ); Алгоритм ТЕМП (поиск в ширину); Генетический алгоритм (поиск правил).

Для поиска коротких информативных наборов признаков подходят различные методы отбора признаков, в том числе: Add-Del; МГУА (метод группового учёта аргументов); Генетический алгоритм (отбор признаков); Случайный поиск с адаптацией.

Рассмотрим метод Генети́ческий алгори́тм - основатель Джон Холланд — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Генетические алгоритмы применяются для решения следующих задач: 1. Оптимизация функций; 2. Оптимизация запросов в базах данных; 3. Разнообразные задачи на графах (задача коммивояжёра, раскраска, нахождение паросочетаний); 4. Настройка и обучение искусственной нейронной сети; 5. Задачи компоновки; 6. Составление расписаний; 7. Игровые стратегии; 8. Теория приближений; 9. Искусственная жизнь; 10. Биоинформатика (свёртывание белков). Блоки как в паскале.