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

Алгоритм

1.1 Назначение алгоритма

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

1.2 Описание алгоритма

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

Требуется:

I) построить решающее правило D, позволяющее относить к одному из классов произвольный объект q генеральной совокупности, описанный в пространстве x;

2) из заданных m признаков пространства описаний x выбрать подсистему l признаков , обеспечивающих максимальную надежность распознавания.

Задача решается по следующей схеме:

I. Определяется мера близости  объекта q, генеральной совокупности к каждому из S_j клас­сов.

2. Объект q относится к тому классу S_j, для которого  было минимальным.

3. Определяется оценка информативности каждого признака x_i пространства описаний x.

 Из m признаков пространства описаний x исключаются такие  признаки, оценки информативности которых по величине меньше оценки каждого из l оставшихся признаков.

1.3 Математическая постановка и описание алгоритма

Дано:

- матрица исходных данных, где NO - число объектов, a NP - число признаков, характеризующих каждый объект; из числа NO объектов NE входят в экзаменационную выборку, NOE - в обучающую;

 - сведения о типе каждого признака (количественный -, качественный -);

- сведения об учете каждого признака (признак учитывается -, признак не учитывается -);

RR - число признаков, учитываемых в системе;

- информация об учете каждого объекта. Если i-й объект не учитывается, то NOB_i = 0, иначе i-й объект учитывается, причем если NOB_i=+l, то этот объект из обучающей выборки, а l - номер класса, к которому он относится. Если NOВ_i=-l, то это объект из экзаменационной выборки, a l - номер его класса.

- номера классов, на которые разделена обучающая выборка (классы могут нумероваться не обязательно от 1 до К).

K - число классов;

Требуется:

а) отнести к одному из классов s₁, s₂, …, s_k произвольный объект генеральной выборки, имеющий описание ;

б) определить l признаков пространства описаний , обеспечивающих максимальную надежность распознава­ния объектов.

Решение задачи выполнено двумя методами "0тсев I" и "Отсев 2". В методе "Отсев I" пространство описаний объектов в j-м классе совпадает с пространством описаний . Номер класса, к которому относится произвольный объект  генеральной выборки, определяется следующим образом. Находятся близости объекта  к каждому классу s₁, s₂,…, s_k по каждому признаку -.  Каждая последовательность величин , соответствующая признаку , упорядочивается по возрастанию значений : .

Для  каждого признака определяется последовательность величин:

, где  - характеризует место класса для объекта  по признаку . Далее определяется мера близости объекта  к каждому из классов по совокупности признаков:

,                                                                         (1)

Объект  относится к тому классу , для которого  наименьшее.

Близость объекта  к классу  по признаку  определяется по формуле

                                                                           (2)

где - значение i-го признака для объекта ;

      - значения i-го признака для объектов, входящих в класс ;

       - малая величина (=0,0001);

t - число объектов в классе ;

        - разности значений i-го признака для пар объектов класса ;

        - число таких разностей. Для качественного признака , если значения  и совпали, иначе .

Следует заметить, что число объектов t в классе  менее двух быть не может.

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

По первому критерию надежность правила оценивается путем сравнения истинного класса объекта с номером класса, присвоенного объекту в соответствии с правилом. Эффективность распознавания в этом случае определяется по формуле

,                                                                                                  (3)

где - эффективность распознавания, в процентах;

       - число правильно распознанных объектов выборки (та­ких, у которых истинный класс совпал с номером клас­са по правилу);

       - число объектов выборки.

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

Третий критерий оценки качества распознавания определяется по формуле

,                                                                                      (4)

где - эффективность распознавания объектов;

      - эффективность распознавания на обучающей выборке;

      - эффективность распознавания на экзаменационной выборке;

       - веса вероятностей правильного распознавания объек­тов обучающей и экзаменационной выборок соответственно (   ). Значения  и  априорно задаются.

Для выделения из системы  признаков  информативных определяется оценка, обратная информативности каждого признака по формуле

,   ,                                                                  (5)

где - число объектов обучающей выборки;

       - множество значений признака  для объектов обучающей выборки из класса .

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

Исключение признаков выполняется по одно­му.

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

В методе "Отсев 2" каждый класс s_j имеет свою подсистему признаков . Для отнесения произвольного объекта  генеральной выборки к одному из классов определяется мера близости этого объекта к каждому классу s_j по формуле

,  ,                                                                         (6)

где - количество признаков в подсистеме  .

Объект  относится к тому классу, для которого минимально.

Оценка, обратная информативности признака для каждого класса определяется по формуле

,  ,                                                             (7)

где  - количество объектов обучающей выборки из класса . Исключению подлежит такой , для которого максимальна. При этом число оставшихся признаков в классе   должно быть не менее одного. Максимально допустимое число удаляемых признаков  в этом случае также задается.