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

 

Бекмуратов Дилшод Касимович,

ассистент Самаркандского филиала Ташкентского университета информационных технологий, Узбекистан.

 

В [4] получен теоретический результат, смысл которого состоит в том, что если из N решающих правил выбирается одно, которое безошибочно разделяет обучающую выборку длины , то с вероятностью  можно утверждать, что вероятность ошибочной классификации с помощью этого правила составит величину, меньшую , где

                                                                                                      (1)

 

В работах [1, 2] показаны принципы получения признаков первого, второго и третьего типа относительно конкретного образа и приведены отношения эквивалентности .

В данной статье, в отличие от [1-3], сначала выбираются признаки первого, второго и третьего типов из обучающей выборки, далее из сочетаний выбранных однотипных признаков формируются определенные числа пространств, каждый из которых имеет одинаковую размерность. При этом заранее определяются числа признаковых пространств и их размерность. Это приводит к резкому уменьшению объема вычислений на ЭВМ, так как каждое пространство формируется не из первоначаль­ного свойства объектов обучающей выборки, а из сочетаний однотипных признаков, выбранных из обучающей выборки по заранее найденным значениям размерности пространства.

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

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

Согласно [2] первый тип признаков определяется свойством , которым обязательно должны обладать все объекты образа  и не должны обладать все объекты образа , т.е.

.                                                     (2)

 

Второй тип признаков определяется свойством , которым обязательно должны обладать все объекты образа , но этими же свойствами могут обладать и некоторые объекты образа , т.е.

 .                                                    (3)

 

Третий тип признаков определяется свойством , которым могут обладать некоторые объекты образа , а все объекты образа этим свойством обладать не будут, т.е.

 ,                                                    (4)

где соответственно признаки первого, второго и третьего типа.

Обозначим через соответственно признаки первого, второго и третьего типа относительно образа , а через  - соответственно образа .

В работе [2] получены предельные значения размерности признакового пространства

 ,                                                                                                   (6)

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

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

 

Таблица 1.

, , .
	0,01	0,02	0,03	0,04	0,05
	1	2	3	4	5

 

Анализ приведенных в таблице 1 данных показывает, что увеличение вероятности ошибки  при классификации новых объектов , приводит к увеличению размерности  пространства признаков - го типа.

Если зафиксировать , , , , то из соотношения (6) можно найти требуемое количество объектов , удовлетворяющих заданную вероятность ошибки  при классификации новых объектов (Таблица 2).

 

Таблица 2.

, , .
	1	2	3	4	5
	0,02	0,03	0,04	0,05	0,06
	294	297	298	298	299

 

Анализ приведенных в таблице 2 данных показывает, что с увеличением вероятности ошибки  при классификации новых объектов  и размерности  пространства признаков - го типа, приводит к увеличению требуемых количеств объектов .

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

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

 В отличие от предыдущих алгоритмов [1-3], в данном алгоритме:

- из заданных свойств объектов обучающей выборки  выбирается набор признаков - го типа  относительно образа ;

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

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

- формируются пространства одинаковой размерности  из сочетаний выбранных признаков - го типа ;

- резко уменьшается объем вычислений на ЭВМ, так как .

Отсюда видно, что в этом алгоритме сильно сокращаются первоначаль­ные наборы свойств, т.е. из первоначаль­ного набора свойств , относительно конкретного образа выбираются лишь несколько признаков , которые входят в найденное пространство .

Алгоритм включает в себя следующие основные этапы:

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

2. В оперативную память заносятся объекты , их свойства  в виде контрольной выборки .

3.  Из оперативной памяти отбирается свойство  объектов , рассматриваемое как претендент на признак -го типа.

4. Проверяется для свойства  соотношение (2-4). Если для свойства  выполняется (2-4), то  является признаком -го (1-го либо 2-го либо 3-го) типа относительно образа  и этот признак вводится в массив , как признак -го типа и алгоритм переходит к шагу 5, в противном случае свойство  исключается из дальнейшего рассмотрения.

5.  Если , то алгоритм переходит к шагу 3, в противном случае к шагу 6.

6. Формируются массив , и  соответственно для признаков первого, второго и третьего типов.

7.  Вычисляются предельные значения размерности пространства  для признаков  - го типа  соотношением (5).

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

9.  Если , то алгоритм переходит к шагу 7, в противном случае к шагу 11.

11. Формируется пространства одинаковой размерности  () из сочетания признаков -го типа .

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

13. В качестве решающего правила  используется

.

 

 

Создан комплекс программ работающих по разработанному алгоритму. Функциональная структура комплекса программ состоит из 3 основных и 13 дополнительных модулей (Рис.-1).

 

Рис. 1.

 

Общий вид интерфейсного окна программы имеет следующий вид (рис. 2).

 

Рис. 2. Общий вид интерфейсного окна.

 

Модуль выбора, вычисления, группирования и распознавания объектов по признакам второго типа представлен на рис. 3.

 

Рис. 3. Результаты вычислительного эксперимента.

 

С помощью программы можно получать аналогичные результаты для признаков первого и третьего типов.

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

 

Литература

 

1.                  Бекмуродов К.А., Васильев В.И., Бекмуратов Д.К. Нахождение предельно-допустимых значений размерности признаковых пространств из обучающей выборки // Академия Наук Республики Узбекистан. Институт математики и информационных технологий. Современное состояние и перспективы развития информационных технологий. Том 2. Ташкент, 2011. 309-312 с.

2.                  Бекмуродов Қ.А., Бекмуратов Д.Қ. Последовательный выбор признаков, обладающих требуемой разделяющей силой. XI - Международная научно-практическая конференция. «Научные перспективы XXI века. Достижения и перспективы нового столетия». Ежемесячный научный журнал №4(11) / 2015, часть 4. Россия, г. Новосибирск, 22-23.05, 2015 г. 9-13 с. ISSN 34567-1769.

3.                  Васильев В.И. Проблема обучения распознаванию образов. Прин­ципы, алгоритмы, реализация. Киев: Выща школа, 1989. - 64с.

4.                  Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.:Наука, 1974. - 412 с.

 

Поступила в редакцию 22.07.2015 г.