Публикация: Труды Всероссийской Конференции «Знания-Онтологии-Теории» (ЗОНТ-09), Новосибирск, 2009, Том I, с. 93-102.

Знания-Онтологии-Теории (ЗОНТ-09)

Меры сходства, компактности, информативности и однородности обучающей выборки

Загоруйко Н. Г.¹, Борисова И. А.¹, Дюбанов В. В.², Кутненко О. А.¹

'Институт математики им. С.Л. Соболева СО РАН, ²Новосибирский Государственный

Университет

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

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

1 Мера конкурентного сходства

Сходство S (a, b) двух объектов a и b обычно оценивается величиной, которая зависит от расстояния R(a, b) между этими объектами и обладает свойствами симметричности, рефлексивности и неравенства треугольника. Однако, при распознавании образов нас интересует мера сходства с другими свойствами. Будем рассматривать сходство контрольного объекта z с объектами a и b , которые являются представителями (ближайшими объектами или эталонами) образов A и B, так что слова «сходство с объектом» будут означать то же, что и слова «сходство с образом». Для принятия решения о принадлежности контрольного объекта z к образу A недостаточно знать расстояние R(z, a). Нужно знать также расстояние R(z, b) и определить, что расстояние R(z, a) является наименьшим из них. Следовательно, нужно иметь не абсолютную, а относительную меру сходства, величина которой зависит от расстояний до представителей конкурирующих образов. Если оценивается сходство между тремя объектами — a, b и c, то при оценке похожести объекта a на объект b должны учитываться расстояния R(a, b) и R(a, c), а при оценке похожести объекта b на объект a должны учитываться расстояния R(b, a) и R(b, c) . Следовательно, относительная мера сходства S не обладает свойством симметричности: S (a, b) Ф S (b, a) . Не всегда выполняется для этой меры и неравенство треугольника: сумма сходств S (a, b) + S (a, c)

может быть меньше сходства S (b, c) . Так что сходство, в отличие от расстояния, не образует метрического пространства. Относительная мера сходства, учитывающая конкурентную ситуацию, образует пространство, которое мы называем конкурентным.

Некоторые известные алгоритмы распознавания используют относительную меру сходства. Например, в известном методе к ближайших соседей (kNN) новый объект z распознается как объект образа A, если расстояние R(z, A) до к ближайших объектов этого образа не только мало, но меньше, чем расстояние R(z, B) до к ближайших объектов конкурирующего образа

B . Оценка сходства в этом алгоритме делается в шкале порядка.

Более сложная мера сходства используется в алгоритме RELIEF [1]. Чтобы определить сходство объекта z с образом A в конкуренции с образом B используется величина

/B(z) = ^R(z.^B) - R(z.^A) ,

где R_max и R_min — максимальное и минимальное расстояния между всеми парами объектов.

Нормализация разности расстояний по величине (R_max — R_min) представляется неудачной.

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

Сформулируем следующие требования, которым должна удовлетворять мера F_a / b (z)

сходства объекта z с объектом a в конкуренции с объектом b .

1. Мера сходства должна зависеть не от характера распределения всего множества объектов, а от особенностей распределения объектов в окрестности объекта z .

2. Если оценивается мера сходства объекта z с объектом a, и ближайшим соседом z

является объект b , b Ф a, то при совпадении объектов z и a мера F_a/b(z) должна иметь

максимальное значение, равное +1, а при совпадении z с b — минимальное значение, равное — 1. Во всех остальных случаях мера конкурентного сходства принимает значения от — 1 до 1.

3. При одинаковых расстояниях R(z, a) и R(z, b) объект z в равной степени будет

похожим на объекты a и b , и меры сходства F_a /b (z) и F_b / a (z) должны быть равны 0 .

Предлагаемая нами функция конкурентного сходства FRiS («Function of Rival Similarity») удовлетворяет всем этим требованиям [2]:

_F = R( z, b) — R( z, a) ^{a /} b R(z, b) + R(z, a). Абсолютная мера сходства S = 1 — R (здесь R — нормированное от 0 до 1 расстояние) дает трудно интерпретируемый ответ на вопрос: «Насколько объект z похож на эталон образа A ?». Сходство в шкале порядка, используемое в методе kNN, отвечает на вопрос: «На эталон какого образа объект z похож больше всего?». Конкурентное сходство в шкале отношений, измеряемое с помощью FRiS-функции, отвечает на эти вопросы и, кроме того, на такой вопрос: «Насколько величина сходства объекта z с эталоном образа A больше сходства z с самым сильным конкурентом - эталоном образа B ?»

2 Выбор эталонов

Для выбора эталонных образцов (столпов), на основании сходства с которыми будет оцениваться конкурентное сходство контрольных объектов с образами, нами предлагается алгоритм FRiS-Stolp. Этот алгоритм выбирает эталоны следующим способом.

Для произвольного объекта aj, i е {1,...,Ma} , образа A вычисляются две характеристики

C¹ и C² эффективности этого объекта в роли единственного столпа данного образа. В качестве столпов конкурирующего образа B используются все его Mb объектов.

1. Для произвольного объекта aj, j Ф i, образа A находим расстояние R(aj, aj) до столпа aj и расстояние R(a,j, b) до ближайшего к нему объекта b образа B . По этим расстояниям вычисляем значение функции сходства:

₎ ^R(aj^{, b})^— R(aj^, aj)

^Fa_t / b ^(aj ⁾ = -„ , _D,-T .

^j R(aj, b) + R(aj, aj)

Чем больше эта величина, тем лучше объект aj защищает объект aj от включения его в состав

образа B . Если величина F' _/b (a^) больше порога F*, например, больше 0, то будем считать,

что объект aj входит в состав кластера, образуемого объектом ai, а величину F' _/b (aj) добавим

к счетчику C¹.

2. Повторив шаг 1 для всех объектов образа A, получим в счетчике C¹ сумму оценок сходства тех Mi объектов образа A, которые вошли в состав кластера, образованного объектом a. Разделив эту сумму на m_j, получим оценку F¹ «обороноспособности» объекта aj:

г¹

-¹ = 'г-. ^г т

3. Теперь нужно проверить объект аг на толерантность к объектам образа В. Для этого оценим сходство с аг всех объектов Ъц, д = 1, к,Мв , образа В в предположении, что роль столпа этого образа будет играть объект Ъ₅ , который является ближайшим соседом объекта Ъд.

- > т-1 /и \ , аг) - ЖЪд, Ъ_я)

4. Для произвольного объекта Ъ_д вычислим величину -_а / ъ (Ъ_д) =-----

^г К(Ъд, аг) + Я(Ъд, Ъ₈)

его сходства со своим столпом Ъ₅ в конкуренции со столпом аг и добавим эту величину в

счетчик С². Если эта величина положительна, то это повышает шансы объекта аг стать столпом образа А . И наоборот.

5. Повторив шаг 4 для в аг по отношению к объектам образа В :

V + w

Чем больше величина , тем меньше будет ошибок первого рода (пропуск цели). Чем

₂

больше величина —г , тем меньше будет ошибок второго рода (ложная тревога). Так что их совместный учет должен отражать соотношение цен этих ошибок.

6. Повторяя шаги 1-5, получим такие оценки для всех Ма объектов образа А . В качестве столпа первого кластера образа А выбираем тот объект аг, которому соответствует наибольшая величина —].

7. Если не все М_А объектов вошли в этот кластер, то для остальных объектов повторяем шаги 1-6 до тех пор, пока все объекты обучающей выборки образа А не окажутся включенными в свои кластеры. В итоге образ А будет представлен Ьа столпами, Ьа >=1 .

8. Затем выполним шаги 1-7 для объектов Ъ₅ , 5 = 1,к,Мв , образа В, в результате чего

получим к_В столпов образа В, к_В >=1.

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

Если количество образов К > 2, то задача сводится к предыдущей следующим способом. При выборе столпов последовательно для каждого образа ( А ) объекты всех остальных образов объединяются в один конкурирующий образ (В).

Алгоритм РШ8-81о1р обладает следующими свойствами. При нормальных распределениях в первую очередь будут выбраны столпы, расположенные в точках математического ожидания. Если распределения полимодальны и образы линейно неразделимы, столпы будут стоять в центрах мод. Количество столпов зависит от компактности образов.

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

3 Оценка компактности и информативности

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

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

Одна из мер такого рода предложена в [4] и состоит в вычислении профиля компактности. Пусть для всех М объектов а обучающей выборки все остальные (М — 1) объектов упорядочиваются по их расстоянию до а. При движении вдоль этих упорядоченных списков от первой позиции ] = 1 до последней ] = М — 1 в каждой порядковой ] -той позиции

определяется количество объектов т■, которые не принадлежат тому образу, которому

принадлежит объект а. Усредненные по всей выборке величины У_}- = т^!М,

3 = 1,к,М — 1, и формируют профиль компактности. Чем компактнее образы, тем для

большего числа первых порядковых номеров ] профиля выполнено равенство У_}- = 0.

Переход от профиля к количественной оценке компактности может делаться разными способами. В работе [4] описывается связь между профилем компактности и функционалом полного скользящего контроля, который является естественной количественной оценкой компактности для метода кМЫ".

Для получения количественной оценки компактности мы предлагаем использовать описанную выше РШ8-функцию. Будем оценивать компактность образа А в задаче распознавания К образов. При выборе столпов образа А для всех его объектов были получены оценки / , которые тем больше, чем больше сходство с ними остальных объектов своего

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

значения величин / будут стремиться к 1. Если образы будут приближаться друг к другу,

величины / будут уменьшаться. Если образы начнут пересекаться, то компактность начнет разрушаться и некоторые объекты окажутся в окружении чужих объектов. Они получат отрицательное значение величины / . Если образы будут наложенными друг на друга так, что их объекты будут перемешанными по типу «губка-вода», то это означает, что компактность разрушена полностью и значения / почти у всех объектов будут отрицательными.

Мы видим, что величины / хорошо коррелируют с интуитивными представлениями о

компактности (разделимости) образов: чем выше компактность, тем больше величины /, и тем выше ожидаемые результаты распознавания. И, наоборот. На этом основании компактностью 0_А образа А будем считать величину, зависящую от среднего значения оценок /^ :

1 М_л _

°А =

^МлТ1

Общая оценка О компактности К образов в данном признаковом пространстве может быть получена путем арифметического или геометрического усреднения. Для минимизации ошибок всех образов в среднем следует использовать арифметическое усреднение:

1 К

о' =¹ у о .

к£ ³

Если нужно, чтобы компактность самого «некомпактного» образа была максимально возможной, тогда нужно использовать среднегеометрическую величину:

G = ^f П G

V j=

Наши эксперименты показывают, что критерий G обычно дает лучший результат по сравнению с критерием G'. Описанная мера компактности тем больше, чем выше плотность объектов внутри образов и чем дальше образы отстоят друг от друга. Таким же свойством обладает и мера, предложенная Фишером для оценки информативности признаков. Различие состоит в том, что мера Фишера предназначена для образов с нормальным распределением объектов, а мера компактности применима для произвольных распределений. Вполне естественным является использование компактности в качестве критерия информативности признакового пространства. Она используется в этом качестве в алгоритме FRiS-GRAD [5]. Наши эксперименты с этим критерием показали его существенное преимущество по сравнению с широко используемым критерием минимума ошибок при распознавании тестовой выборки методами Cross Validation или One Leave Out[2].

4 Оценка однородности и цензурирование выборки

Найденные в процессе выбора столпов оценки F каждого объекта позволяют анализировать однородность обучающей выборки. В качестве меры однородности выборки объектов образа будем использовать дисперсию d значений F их сходства со своими столпами. Оценка

F у объекта, находящегося в центре локального сгустка своих объектов, будет больше, чем у периферийных объектов. Для объектов, оказавшихся в окружении чужих объектов, величина F может иметь отрицательное значение. Такие объекты (выбросы — «outliers») будут приводить к увеличению числа столпов и ухудшению последующего качество распознавания. По этой причине их целесообразно исключить из дальнейшего рассмотрения («цензурировать»).

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

значением величины F. После пересчета можно увидеть, что дисперсия d уменьшилась.

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

Если этот процесс не останавливать, то минимальная дисперсия d = 0 будет достигнута, когда в выборке останутся только объекты-столпы. Цензурирование должно остановиться на шаге, при котором достигает максимума критерий Qd , отражающий два противоречивых желания: добиться минимального значения дисперсии d и максимального сохранения количества объектов обучающей выборки:

^Qd = ^{f œ} d^M ].

Здесь Mc/M - доля объектов обучаю.щей выборки, оставшихся в составе выборки после очередного шага цензурирования. В настоящее время исследуются разные варианты критерия остановки процесса цензурирования. В работающих программах распознавания пока используется простой вариант цензурирования: столпы строятся на полной выборке, выделяются «единичные» столпы, которые защищают только самих себя, и эти столпы игнорируются (исключаются из списка столпов) в процессе распознавания контрольных объектов.

5 Примеры решения реальных задач

Описанные выше меры сходства, компактности, информативности и однородности обучающей выборки позволяют унифицировать подходы к решению разных задач распознавания образов. На их основе разработаны алгоритмы построения решающих правил ^Ш8-81о1р) и таксономии (FRiS-C1ass [5]), алгоритм комбинированного типа БХ для одновременного построения решающих правил и выбора признаков (FRiS-GRAD [6]) и алгоритм универсальной классификации, решающий задачу таксономии-распознавания при любом соотношении классифицированных и не классифицированных объектов в анализируемой выборке [7]. Ниже показаны примеры применения некоторых из этих алгоритмов при решении реальных задач. Их общая особенность состоит в том, что количество признаков на порядки превышает количество объектов.

5.1 Диагностика рака простаты по масс-спектрам белков

Анализируются данные о масс-спектре белковых форм, полученные с помощью спектрометра типа SELDI-MS-TOF [8]. Количество признаков (спектральных полос) — 15153. Представлены четыре класса пациентов с разным уровнем индекса PSA, характеризующего степень развития рака простаты: 63 здоровых пациента класса B имеют PSA < 1 ng/mL, 26 пациентов класса C имеют PSA = 4 -^10 ng/mL, 43 пациента класса D меют PSA > 10 ng/mL и 190 пациентов класса A имеют PS A > 4 ng/mL. Малое количество пациентов не позволяет разделить выборку на обучающую и контрольную. По этой причине воспользуемся тем обстоятельством, что целевая характеристика (PSA), указывающая на принадлежность пациентов к тому или иному классу, позволяет установить между классами отношение частично-линейного порядка.

Если упорядочить классы пациентов по степени проявления симптомов рака от самого здорового до самого больного, то класс B должен находиться в начале списка, за ним должен следовать класс C , и затем — класс D . Пациенты класса A должны оказаться среди пациентов классов C и D. Следовательно, если построить правила для распознавания класса здоровых пациентов B от любого класса больных (например, класса C ), то пациенты других классов больных ( A и D ) должны быть больше похожими на класс C , чем на B . В результате можно обучаться на двух классах, а на контроль предъявлять объекты третьего класса. Перебирая разные составы конкурирующих классов и фиксируя выбираемые при этом информативные характеристики, можно выделить подмножество характеристик, по которым классы будут отличаться друг от друга.

На первом этапе были сформированы две группы классов: первую группу представлял класс здоровых пациентов B , а во вторую группу были включены все три класса больных пациентов — классы A, C и D. С помощью алгоритма FRiS-GRAD в режиме Cross-Validation (10 этапов по 10% выборки на контроль) из 15153 признаков в состав 10 решающих правил было включено 24 признака. По этим правилам правильно распознано 275 объектов из 322 (85,4%). Надежность распознавания здоровых пациентов была равна 43 из 63 (68,3%), а больных — 232 из 259 (89,6%).

На следующем этапе делалась попытка из 24 найденных признаков выбрать информативные подсистемы для распознавания всех классов друг от друга. Результаты решения некоторых из этих задач представлены в таблице 1, из которой видно следующее. Если правила построены для различения класса B (здоровые) от класса C , класса D или их смеси, а на контроль подавать классы больных, не участвовавших в обучении, то класс B хорошо отличается от всех классов больных пациентов (эксперименты 1-5). После обучения на классах C и D выяснилось, что в большом классе A пациентов с признаками принадлежности к классу C («слабо больные») существенно больше, чем пациентов класса D («сильно больные») (эксперимент 6). Если ставить вопрос о том, на какой из классов больных — C или D — больше похожи здоровые люди (эксперимент 7), то ответ будет в пользу класса C («слабо больные»), что вполне естественно.

Таблица 1. Результаты экспериментов