Исследование свойств линейных метрических алгоритмов распознавания

ОГЛАВЛЕНИЕ
Введение ..................................................стр.З
ГЛАВА I.
§ I. Основные понятия и определения.Алгоритм Н...2.4
§ 2. О решающем правиле алгоритма Н..................3-5
§ 3. Сильная и слабая Н - разделимость...............43
§ 4. О погрешности распознавания алгоритма Н.........53.
ГЛАВА П.
§ I. Линейные метрические алгоритмы распознавания...^
§ 2. Сокращение признакового пространства.............Z.7
ГЛАВА Ш.
§ I. Реализация алгоритма классификации *?Н..........НО
§ 2. Решение задачи распознавания на примере задачи из
геологии и социально-экономической области......116
Ли т е р а т ур а............................................124
ПРИЛОЖЕНИЕ * -• ......................................................................
_ 3 _
ВВЕДЕНИЕ
Комбинаторно-логический подход к задачам классификации и распознавания привлекает в последнее время внимание многих исследователей. В последнее десятилетие идеи и методы комбинаторно-логического подхода с успехом используются при решении самых разнообразных задач распознавания из прикладной геологии, в медицине, возникающих в социально-экономической сфере и т.д. По каждой из областей применения уже накопилась большая научная литература. Большое количество прикладных вопросов, исследование которых сводится к решению задачи распознавания, обусловило и многообразие конкретных алгоритмов для их решения. Однако, основные применения теории распознавания связаны с плохо формализованными областями науки и практики, вследствие чего в предлагавшихся алгоритмах в лучшем случае находят математическое отражение лишь некоторые интуитивные принципы. Это обусловило на первом этапе развития теории использование на практике многих конкретных алгоритмов распознавания без какого-либо формального обоснования и предварительного исследования. Последнее обстоятельство и препятствует решению в полной мере одной из основных проблем распознавания: для заданной задачи (или класса задач) распознавания. Найти алгоритм (класс алгоритмов) с высоким качеством распознавания. Одним из путей, на котором эта проблема может быть удовлетворительно решена, является путь более детального теоретического изучения конкретных алгоритмов и классов алгоритмов распознавания и прежде всего тех наиболее узловых, в основе которых лежит та или иная принципиальная
_ 4 -
идея распознавания. Одной из таких естественных идей, положенных в основу различных конкретных алгоритмов известных на практике, является идея "близости" распознаваемого объекта к своему классу, причем допускаются и предлагаются разнообразные формальные уточнения этого понятия.
Одним из наиболее простых и естественных уточнений понятия "близости" является уточнение, основанное па метрике в пространстве признаков. Такое уточнение приводит к классу метрических алгоритмов распознавания, внутри которого выделяется важный подкласс - класс линейных метрических алгоритмов распознавания, одним из стандартных представителей которого является алгоритм Н, основанный на метрике Хемминга в пространстве бинарных признаков.
Исследованию теоретических свойств класса линейных метрических алгоритмов распознавания и посвящена настоящая диссертационная работа.
Диссертация состоит из оглавления, введения, трех глав, приложения и списка литературы.
В главе I для решения поставленной задачи классификации с эталонами вводится алгоритм И , для которого исследуется ряд его свойств. В частности, изучается решающее правило алгоритма Н - показывается, что в качестве разделяющей гиперповерхности в пространстве признаков алгоритм Н определяет гиперплоскость, уравнение которой может быть явно выписано. Важные характеристики качества распознавания алгоритма связаны с влиянием на распознавание выбора эталонных множеств, а также погрешности в их задании. Формальным уточнением этого являются понятия сильной и слабой Н -разделимости, а также устойчивости алгоритма, для которых получены характеризующие их результаты.
В главе П на основе проведенного в главе I изучения свойств алгоритма п , вводится для описания алгоритмов распознавания (классификации) модель метрических алгоритмов распознавания, важным подклассом которых является класс линейных метрических алгоритмов. Показывается, во-первых, что линейные метрические алгоритмы и (с некоторым дополнительным ограничением) только они в качестве разделяющей гиперповерхности строят гиперплоскость, а кроме того, что алгоритм Н является стандартным представителем этого класса, откуда следует справедливость результатов, полученных в главе I для алгоритма И , применительно к произвольному линейному метрическому алгоритму распознавания. Далее в этой главе в теоретическом аспекте исследуется вопрос о возможности сокращения множества признаков. Доказывается, что поставленная задача является
- 6 -
-полной. Для возникающих здесь приближенных алгоритмов, сокращающих поле признаков, даются оценки погрешности в их работе.
В главе Ш на основе исследования, проведенном в главах I и П, предлагается алгоритм классификации ЗН , который включает в себя кроме процедуры распознавания процедуры проверки и формирования свойств слабой и сильной разделимости эталонных множеств, определения числа ошибок для устойчивого распознавания, так же процедуру сокращения исходного множества признаков.
Работа алгоритма ЗН иллюстрируется двумя примерами из геологии и социально-экономической области.
В приложении приводится ФОРТРАН-программа алгоритма.
Перейдем к определениям и точным формулировкам полученных результатов.
Глава I состоит из §1, §2, §3 и §4.
В §1 вводятся основные понятия, определения и обозначения, используемые далее в работе.
Пусть £= {О, і]г $) ~ ^ = І], Z - множество
целых чисел, - множество действительных чисел; Е1 »
З)'1 , 5)^- /2-мерные кубы в пространстве Ш ■, вектор (Ы.,} <&Е)Є £ будем называть двоичным вектором или набором (а также вершиной куба Е ) и обозначать через или
оС'1’ , вектор &п)є^ будем обозначать через Л
или й- . Если &-'1' и & из ^ , то /дС&З &п') означает
метрику, порожденную нормой 10.^1 = 2Г (на кубе Е эта
г = і
метрика является метрикой Хемминга), евклидову норму вектора
- 7 -
А будем обозначать через llQ.ll , а скалярное произведение в $ через
Сформулируем в рамках комбинаторно-логического подхода задачу классификации с эталонами. Пусть имеются два класса объектов или явлений К1 и и некоторые представители (эталоны) этих классов, которые качественно изучались по ряду признаков. Пусть упорядоченное множество признаков есть множество [{,2,...л$. Тогда результаты изучения объекта X из К1 (или из ) является его описание - двоичный набор а. = <*л <*п.) »
где аС^ совпадает с 1 или О в зависимости от того, выражен или нет признак ъ у объекта 4 I ^ п. , Таким обра-
зом, информация о классах Лу и Кг , полученная при изучении некоторых их представителей (эталонов), скажем К,
и £п. ^ Кг. представлена множествами описаний
{ р } и / £*, , &п- / . Исходя из
этой информации, требуется указать решающее правило (алгоритм), которое по описанию произвольного объекта X £ К11/Кг. относило бы этот объект к тому из классов А/ или К г. , который его содержит. В описанной ситуации для алгоритма распознавания Ос. будем говорить о классификации объектов из класса К с эталонами А« = и Аг — / .
При правильной (при помощи алгоритма ^ ) классифика-
ции всех объектов из А" с эталонами и Аг будем говорить о слабой Ох. -разделимости классов А/ и Кг посредством эталонов Л, и А2 , В случае А# , Кг. классы А# и А1 будем называть слабо а -разделимыми, а если для любых (непустых) эталонных множеств £ К\ и Кг. классы Кл
- 8 -
и К являются слабо Ок. -разделимыми посредством и
Л2 , то будем говорить о сильной Ок. -разделимости классов К и Кг. . Введенные понятия разделимости классов характеризуют влияние выбора эталонных множеств на качество распознавания алгоритма Си . Будем считать кодирующую функцию ^ : К » сопоставляющую элементу класса К его опи-
сание, фиксированной, вследствие чего можно не различать классы Ау и Кг и их описания и, сохраняя введенную терминологию, говорить о слабой (сильной) Ок. -разделимости применительно к подмножествам /Ь -мерного куба.
Приведем описание алгоритма распознавания
Пусть ЕЗ и М. — / <К,, ... ^ <£/тг - произ-
вольные. Введем функционалы:
ПЪ
Описание работы алгоритма 0} сводится к следующему.
Даны £-6 К*' .
1. Вычисляются функционалы И К1г) •
2. Решающее правило (К - означает "относится к"):
Г * если У0/
^ € I М*- . если уЗ, >Д
^не определено, если
В терминах метрики Хемминта можно выделить следующие достаточные условия для Н -разделимости множеств.
Пусть М.1 , ^ ^7 , //%/— , IМг]и
- 9 -
(^1= ГПХХ,^ ((А,А"), где /П'О'Х. берется по всем оС , -Мг., -
диаметр множества
рде /ПМЬ берется ПО всем >уЬ&Мг.у - расстояние меж- •
ду множествами Я и мг . Справедяива
Т е о р е м а 1.1.1. При выполнении неравенств
множества Н, и мг слабо Н -разделимы; при выполнении неравенств
-|У < I ,*'“<2
множества М-1 и Мг СИЛЬНО и -разделиглы.
Заметим, что оценки, приведенные в теореме 1,1.1 усилить, вообще говоря, нельзя: при невыполнении условий как первой части теоремы, так и второй (даже при замене строгих неравенств на нестрогие) можно указать соответствующие контрпримеры.
Пусть С** = ’[£'и / 1£’1'1 > п-~к} и Ск/г -{<£'г'11£^14 к$ -соответствующие верхняя и нижняя части куба Е* .
Примером применения теоремы 1.1.1 может служить следующее
л Ау /1*
Следствие 1.1.2. Множества вершин С ' и сильно Я -разделиглы тогда и только тогда, когда одновременно выполняются неравенства:
зкл + К,. < П. р •
Отметим, что вопрос о слабой Я -разделимости этих множеств
к ^
с использованием теоремы 1.2.2 решается сразу: множества С *
- 10 -
ж Ск п, слабо Н -разделимы тогда и только тогда, когда
К, < f и К1<%- .
В §2 показывается, что алгоритм И в качестве разделяющей гиперповерхности строит гиперплоскость.
Для множества Ms£T информационным вектором будем называть вектор P=j^jT1 °С (очевидно, что вектор Р представляет собой координаты центра тяжести системы материальных точек из множества И с единичным распределением масс). Пусть Р ъ Рг. - информационные векторы множеств Мі и соответственно. Дадим такое
Определение . Вектор называется
характеризационным вектором для множеств М. і и Мг .
Обозначим набор из единиц ( I ) через і . Спра-
ведлива
Теорема 1.2.2. Решающее правило алгоритма И линейное; уравнение разделяющей гиперплоскости имеет вид (Ô.f (2x.-i))=0, где - характеризадионный вектор для раз-
деляемых алгоритмом множеств векторов Мі и Mz .
Шесто гиперкуба будет удобнее рассматривать гипер-
куб <^)П' , полученный из исходного линейным преобразованием (в пространстве ^ ), задаваемым формулой 2.3-і .
Вектор ^(х) Є будем обозначать через X . Формально,
переход от ^ к осуществляется заменой нулевых координат на - £ (что означает кодирование у объекта отсутствие признака - і , а не нулем). Сохраним для введенную тер-
минологию и обозначения. Отметим, что информационный вектор Р
для множества М. £ ^ вычисляется как и раньше : Р-.ттт 21 X .
т1 йен
- II -
Таким образом, уравнение разделяющей гиперплоскости в ги-перкубе принимает вид ~ О
Отметим одно геометрическое следствие, непосредственно вытекающее из теорем І.І.І и 1.2.2 (используются обозначения из теоремы І.І.І).
Следствие 1.2.3. При выполнении неравенства
/I ґгц-'І
множества вершин куба Я5 ^ можно отделить одно от другого при помощи гиперплоскости, проходящей через начало координат,
В §3 продолжается начатое в §1 исследование случаев сильной и слабой Н -разделимости. В этом параграфе в геометрических терминах найдены достаточное (для слабой И -разделимости) и необходимое и достаточное (для сильной И -разделимости) условия.
Пусть Кі= ҐПЛХ./ІЛ,- Р^Л , где тах. берется по всем сі-ЄМ-і, - радиус множества М.і - , Р-і - информационный вектор множества М. і , <-і, <2 ,а £ - характериза-
ционный вектор для множеств Мі и Нг_ .
Теорема 1.3.2, При выполнении неравенств
црлг-црлг о .„хи , т*-т1
($4 < #// + ТЩГ/ > + 4114,11
множества Мі и Мг слабо Н -разделимы.
В случае сильной И -разделимости справедлива Теорема 1.3.4. Множества А£* и из З)*' сильно
Н -разделимы тогда и только тогда, когда для любых одноэлементных подмножеств /А]гМ, , ІЇ]іМ 2. они слабо
- 12 -
Ц-разделимы посредством ■[й.]’ и .
Введем такие обозначения:
мг) , где-мг.{4|гемг] ;
М»{ж | ж=а-8 | а.е Н,, М.}.
__ ЮТ- выпуклый конус, порожденный множеством м(м) ,
X* - конус, двойственный к . Имеет место ^Утверждение 1*3.5. Множества Н< и //* из %) сильно И -разделимы тогда и только тогда, когда X*. Из утверждения 1.3.5 вытекает
Следствие 1.3.6. Если для диаметра (в евклидовой метрике) оЛ(М) множества М выполняется неравенство сС(М)< , то множества М< и Мг из 9)^ сильно Н -
разделимы.
В §4 исследуются вопросы, связанные с оценкой погрешности работы алгоритма Н на наборах из множеств -М* и Мг в случае, когда последние подвергаются некоторому возмущению <6 .
Пусть от - матричное задание множества М . Тогда возмущение <5= уI есть некоторая {-i, 1 )-матрица - каждое Зу = -1 символизирует единичную ошибку (замену 1 на -з и наоборот), которая происходит в пересечении -£ -ой строки и у-го столбца матрицы чЛЬ . Пусть Ц, = (0чг..., £л-)- хара-ктеризационный вектор для множеств М1 и Мз_ . Введем обозначения: ^ = пыгь/^ /_, 4*- sn-fLX.lq.il } = /тип,
- 13 -
£* = пиьх.а), где яш и гках берется по всем &£М =
- М, и(~Мг) (множества М.1 и Лх предполагаются слабо разделимыми). Получены следующие результаты (соответствующие определения для краткости опущены):
Теорема 1.4.2. Дяя погрешности А. распознавания множеств М.1 и , заданных с погрешностью & ,
справедливы оценки:
Ч*■"- ± < д 4 Ч*
т. б*
Следствие 1.4.3. ^Если в каждой строке матрицы <5 число ошибок меньше, чем 2^*: , то распознавание множеств
н, и пг устойчиво (относительно ).
Глава П состоит из §1 и §2 и содержит основные результаты о классе линейных метрических алгоритмов распознавания, дополняющие результаты, полученные в главе I.
В §1 вводится класс метрических алгоритмов распознавания и изучается строение подкласса линейных метрических алгоритмов. На протяжении этого параграфа рассматривается более общая постановка задачи распознавания (классификации), чем описанная в §1 главы I. Обобщение состоит в следующем: для объекта освХ подлежащего распознаванию, будет допускаться, что его описание 5 = 6(ос.) является точкой п. -мерного куба 3) Л". Таким образом, кодирующая функция к является функцией из множества К в множество §& -к: Ж—^5? , а признаки - чис-
ловыми. Содержательно, числовое значение признака ^ характеризует для объекта К меру выраженности в объекте
- 14 -
%
СС- признака ^ . В то же время по-прежнему считается, что на эталонах функция £ принимает значения из прежнего множества З)*' , что может быть проинтерпретировано как требование иметь в качестве эталонов лишь объекты с выраженным наличием или отсутствием рассматриваемых признаков. Для такого варианта постановки задачи классификации предлагается и изучается следующая модель алгоритмов, основанная на известной идее потенциальных функций.
Пусть (х) обозначает потенциал поля, создаваемого
— /X-
вершиной <£ в точке Ж- гиперкуба я) . Будем предполагать, что потенциал является
1) центрально-симметричным (относительно точки <*Г ),
где /<р - некоторая действительная функция, а степень б
равна 1 , если в качестве функции р выбирается метрика, порожденная нормой = 211&г1 и б* 2. , если выбирается
евклидова метрика;
2) аддитивным, т.е. потенциал (ъ-) , создаваемый в точке X множеством вершин М= сСугР) вычисляется
по формуле: гу,
%(*)=%%(£);
'Т' х
3) убыващим, т.е. функция из пункта I) является
(строго) убывающей.
Каждый такой потенциал Ф определяет метрический алго-
- 15 -
ритм распознавания (Хр со следующим решающим правилом :
а) объект С£ относится к классу K^ (или ), если
Д-Ф (сс.)>0 <«»» С,®<о>,
I МЛ п< *•
б) в случае ВоСё-)=0 решение не принимается, - где М1
и Мг описания эталонных множеств из и Кг соответственно.
Уравнение & (х)= О определяет в общем случае в гиперкубе некоторую разделяющую гиперповерхность.
Отметим, что многие алгоритмы распознавания, известные как на практике (например, алгоритм голосования по всем выборкам длины К ), так и в теории распознавания (например, алгоритмы, описываемые в рамках Г-моделей) могут быть описаны в терминах подходяще выбранных метрических алгоритмов распознавания.
Приведем необходимые для формулировок теорем определения. Будем говорить, что метрические алгоритмы *-*•/ и эквивалентны, если
Уде Я) Згдп Сво}С°0) = 8гдп.(в®ю) ,
т.е. для любого Хе^)^ алгоритмы бхн и работают одинаково (при одинаковых эталонных множествах).
Определение . Метрический алгоритм , по-
тенциал 5? которого определяется посредством линейной функции + б , будем называть линейным метрическим алго-рктмом распознавания.
- 16 -
Имеет место
Теорема 2.1.4. Любой линейный метрический алгоритм распознавания эквивалентен алгоритму Н .
Эта теорема позволяет автоматически распространить результаты главы I на линейные метрические алгоритмы. Выделим из них такой.
Определение. Метрический алгоритм, определяющий для любых двух множеств М.1 и Мг из %)п' в качестве разделяющей гиперповерхности гиперплоскость, будем называть метрическим алгоритмом линейного типа.
Это определение позволяет сформулировать следствие из теорем 2.1.4 и 1.2.2.
Следствие 2.1.5. Линейные метрические алгоритмы распознавания являются метрическими алгоритмами линейного типа.
Оказывается, что при некоторых дополнительных ограничениях, только линейные метрические алгоритмы в классе метрических алгоритмов обладают указанным свойством..
Теорема 2.1.6. Пусть П. >3 . Тогда любой метри-
ческий алгоритм линейного типа с дважды дифференцируемой функцией будет линейным метрическим алгоритмом.
Отметим, что в случае п - 2 можно указать такую нелинейную (и дважды дифференцируемую) функцию , для которой
метрический алгоритм &-<р будет алгоритмом распознавания линейного типа.
Замечание. Вместо свойства 2 потенциала *Р
- 17 -
мо^ет рассматриваться следующее:
где в качестве (пункции -L (х) могут выбираться, например,
-оСЭС. ~ Q{
Функции е »/ГУГГТ" и т.Д.
Кроме того, вместо решающего правила R0 может использоваться решающее правило Ri , определяющее разделяющую гиперповерхность уравнением R,(x)= (&) - Фц С*-) = О
Опираясь тогда на доказательство теоремы 2.1.4, нетрудно доказать, что в случае произвольной убывающей функции ^ алгоритм распознавания, определяемый потенциалом ф со свойствами 1,2,3 и правилом R0 , является алгоритмом линейного типа и по существу является линейным метрическим алгоритмом распознавания; в случае же правила R* разделяющая гиперповерхность в общем случае оказывается гиперсферической (для указанных выше функций ß ).
В §2 исследуется вопрос о возможности сокращения исходного множества признаков.
Пусть Mi и Мг эталонные множества из % и М-
-Mi U6"Мд)• Эти множества можно задавать в виде -
матриц, которые будем обозначать теш же буквами, что и соответствующие множества.
Пусть ci *51 cL _ вектор сумм столбцов матрицы Отметим, что в случае |М.»| = |MjJ вектор d коллинеарен характеризационному вектору Ц для множеств /1-, и -