Классификации и анализа данных

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

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

Более подробно описаны основные подходы и алгоритмы комбинаторно-логических методов распознавания (модели вычисления оценок или алгоритмы, основанные на принципе частичной прецедентности), разработанные в ВЦ РАН им. А.А. Дородницына. В основе данных моделей лежит идея поиска важных частичных прецедентов в признаковых описаниях исходных данных (информативных фрагментов значений признаков, или представительных наборов). Для вещественных признаков находятся оптимальные окрестности информативных фрагментов. В другой терминологии, данные частичные прецеденты называют знаниями или логическими закономерностями, связывающими значения исходных признаков с распознаваемой или прогнозируемой величиной. Найденные знания являются важной информацией об исследуемых классах (образах) объектов. Они непосредственно используются при решении задач распознавания или прогноза, дают наглядное представление о существующих в данных взаимозависимостях, что имеет самостоятельную ценность для исследователей и может служить основой при последующем создании точных моделей исследуемых объектов, ситуаций, явлений или процессов. По найденной совокупности знаний вычисляются также значения таких полезных величин, как степень важности (информативности) признаков и объектов, логические корреляции признаков и логические описания классов объектов, и решается задача минимизации признакового пространства.

2. Методы решения основной задачи кластерного анализа (классификации без учителя) – нахождение группировок объектов (кластеров) в заданной выборке многомерных данных. Приведен краткий обзор основных подходов для решения задачи кластерного анализа и описание комитетного метода синтеза коллективных решений.

3. Программная система интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ. В основу требований к системе положены идеи универсальности и интеллектуальности. Под универсальностью системы понимается возможность ее применения к максимально широкому кругу задач (по размерностям, по типу, качеству и структуре данных, по вычисляемым величинам). Под интеллектуальностью понимается наличие элементов самонастройки и способности успешного автоматического решения задач неквалифицированным пользователем. В рамках Системы РАСПОЗНАВАНИЕ разработана библиотека программ, реализующих линейные, комбинаторно-логические, статистические, нейросетевые, гибридные методы прогноза, классификации и извлечения знаний из прецедентов, а также коллективные методы прогноза и классификации.

1. Алгоритмы распознавания, основанные на вычислении оценок. Распознавание осуществляется на основе сравнения распознаваемого объекта с эталонными по различным наборам признаков, и использования процедур голосования. Оптимальные параметры решающего правила и процедуры голосования находятся из решения задачи оптимизации модели распознавания - определяются такие значения параметров, при которых точность распознавания (число правильных ответов на обучающей выборке) является максимальной.

2. Алгоритмы голосования по тупиковым тестам. Сравнение распознаваемого объекта с эталонными осуществляется по различным «информативным» подмножествам признаков. В качестве подобных подсистем признаков используются тупиковые тесты (или аналоги тупиковых тестов для вещественнозначных признаков) различных случайных подтаблиц исходной таблицы эталонов.

3. Алгоритмы голосования по логическим закономерностям.

По обучающей выборке вычисляются множества логических закономерностей каждого класса – наборы признаков и интервалы их значений, свойственные каждому классу. При распознавании нового объекта вычисляется число логических закономерностей каждого класса, выполняющихся на распознаваемом объекте. Каждое отдельное «выполнение» считается «голосом» в пользу соответствующего класса. Объект относится в тот класс, нормированная сумма «голосов» за который является максимальной. Настоящий метод позволяет оценивать веса признаков, логические корреляции признаков, строить логические описания классов, находить минимальные признаковые подпространства.

4. Алгоритмы статистического взвешенного голосования.

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

5. Линейная машина.

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

6. Линейный дискриминант Фишера.

Классический статистический метод построения кусочно-линейных поверхностей, разделяющих классы. Благоприятными условиями применимости линейного дискриминанта Фишера являются выполнение следующих факторов: линейная отделимость классов, дихотомия, «простая структура» классов, невырожденность матриц ковариаций, отсутствие выбросов. Созданная модификация линейного дискриминанта Фишера позволяет успешно использовать его и в «неблагоприятных» случаях.

7. Метод к-ближайших соседей.

Классический статистический метод. Распознаваемый объектотносится в тот класс, из которого он имеет максимальное число соседей. Оптимальное число соседей и априорные вероятности классов оцениваются по обучающей выборке.

8. Нейросетевая модель распознавания с обратным распространением

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

9. Метод опорных векторов.

Метод построения нелинейной разделяющей поверхности с помощью опорных векторов. В новом признаковом пространстве (спрямляющем пространстве) строится разделяющая поверхность, близкая к линейной. Построение данной поверхности сводится к решению задачи квадратичного программирования.

10. Алгоритмы решения задач распознавания коллективами различных распознающих алгоритмов.

Задача распознавания решается в два этапа. Сначала применяются независимо различные алгоритмы Системы. Далее находится автоматически оптимальное коллективное решение с помощью специальных методов-«корректоров». В качестве корректирующих методов используются различные подходы.

11. Методы кластерного анализа (автоматической классификации или обучения без учителя).

Используются следующие известные подходы:

- алгоритмы иерархической группировки;

- кластеризация c критерием минимизации суммы квадратов отклонений;

- метод к-средних.

Возможно решение задачи классификации как при заданном, так и неизвестном числе классов.

12. Алгоритм построения коллективных решений задачи классификации.

Задача классификации решается в два этапа. Сначала находится набор различных решений (в виде покрытий или разбиений) при фиксированном числе классов с помощью различных алгоритмов Системы. Далее находится оптимальная коллективная классификация в результате решения специальной дискретной оптимизационной задачи.