Методы классификации в анализе формальных понятий

Постановка задачи классификации

Задача классификации будет рассмотрена в следующей постановке: пусть задано некоторое непустое множество Х, разделенное на попарно непересекающиеся подмножества. Назовем эти множества классами. Только для подмножества объектов известна принадлежность к классам; данное подмножество является обучающей выборкой.

Каждый элемент может быть описан с помощью определенного набора признаков. Исходное признаковое пространство F — объединение всех признаков всех объектов.

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

Алгоритмы классификации

Многочисленные методы классификации могут быть найдены в анализе формальных понятий. Алгоритмы могут работать с данными, имеющими небинарные признаки, одним из двух перечисленных ниже способов:

• · Проведение шкалирования данных для перехода к бинарным данным;
• · Использование модификаций алгоритмов для работы с небинарными признаками.

Для того, чтобы работать напрямую с небинарными признаками, необходимо использовать узорные структуры, описанные в главе 1.3.

Ниже описаны основные типы алгоритмов классификации.

1. Алгоритмы, использующие всю решётку понятий.

Классификатор, построенный на входных данных, использует всю решетку понятий. Главный недостаток семейства данных алгоритмов — большая сложность построения всей решётки.

2. Алгоритмы, основанные на использовании гипотез.

Из обучающей выборки формируется три контекста — положительный, отрицательный, недоопределенный. Классификация основывается на некоторых формальных содержаниях понятий из положительного и отрицательного контекстов, называемые гипотезами.

3. Алгоритмы, основанные на использовании подмножеств решётки понятий.

Алгоритмы данного семейства используют только некоторое подмножество решетки понятий. Это способствует снижению сложности данных алгоритмов.

4. Алгоритмы, основанные на использовании покрытия контекста.

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

Опишем алгоритм классификации, основанный на построении гипотез.

Данные алгоритм также часто называют ДСМ-метод [10].

Пусть определены множества положительных и отрицательных примеров относительно некоторого целевого свойства z. Помимо этого, пусть задано множество недоопределённых примеров — объектов, не имеющих значение свойства z.

Такие данные задаются с помощью трёх контекстов:

— положительный контекст,.

— отрицательный контекст,.

— недоопределенный контекст.

Формальное понятие положительного контекста является положительным понятием, при этом принято называть положительным формальным объемом, — положительным формальным содержанием. Положительное формальное содержание называется:

• · положительной предгипотезой в случае, если оно также не является формальным содержанием ни одного отрицательного понятия;
• · положительной гипотезой в случае, если оно также не является подмножеством формального содержания какого-либо понятия вида ;
• · фальсифицированной положительной гипотезой в случае, если оно является также подмножеством формального содержания понятия некоторого отрицательного примера.

Аналогичные определения можно дать отрицательным предгипотезам, гипотезам и фальсифицированных гипотезам. Если в формальное содержание недоопределенного примера входит положительная (отрицательная) гипотеза, то эта гипотеза является гипотезой в пользу положительной (отрицательной) классификации g. Классификация недоопределенного объекта происходит следующим образом:

• · строятся множества положительных и отрицательных гипотез;
• · если содержит ни одну отрицательную гипотезу и хотя бы одну положительную, то относят к положительному классу;
• · если содержит и одну положительную гипотезу и хотя бы одну отрицательную, то относят к отрицательному классу;
• · если в не входит ни одна гипотеза из положительных и отрицательных множеств гипотез, или содержит гипотезы как из одного множества, так и из другого, то происходит отказ от классификации.

Обобщение ДСМ-метода на узорные структуры используется для классификации объектов, содержащих небинарные признаки. Пусть и — множества положительных и отрицательных примеров по отношению к целевому атрибуту w.

Узор называется положительной гипотезой, если.

.

Для недоопределенного примера положительная гипотеза h определяется как гипотеза в пользу положительной классификации объекта g, если. Отрицательные гипотезы определяются аналогично. Классификация проводится тем же способом, что и в случае бинарных контекстов.

Выводы по 1 главе

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