Алгоритм FRiS-TDR для решения обобщенной задачи таксономии и распознавания

Размещено на http://www.allbest.ru/

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

Алгоритм FRiS-TDR для решения обобщенной задачи таксономии и распознавания Знания-Онтологии-Теории

Задачи таксономии и распознавания считаются близкими, но разными задачами [1]. Для их решения разработано большое количество специфичных методов. Рассмотрим различия и общность этих задач.

При построении решающих правил заданными считаются признаковое пространство Х, множество верифицированных (обучающих) объектов Vv=<a1, a2,…ai,…aMv>, разделенное на К классов, и семейство решающих правил D. Эти данные дополняются гипотезами о том, что обучающая выборка представительна и что объекты в пространстве признаков распределены компактно. Если эти гипотезы окажутся верными, то совместное распределение объектов обучающей и контрольной выборок будет также компактным. Требуется найти параметры решающего правила, по которому можно с заданной надежностью распознавать принадлежность к своим образам как объектов множества Vv, так и будущих неверифицированных (распознаваемых) объектов множества Vu=<a1, a2,…aj,…aMu>.

При таксономии программе задаются признаковое пространство Х, не классифицированные объекты множества Vu=<a1, a2,…aj,…aMu> и семейство правил D, по которым эти объекты должны делиться на классы. Эти данные также дополняются гипотезами о представительности и компактности образов, неявно представленных выборкой Vu. Если эти гипотезы подтвердятся, то совместное распределение, как имеющихся объектов, так и будущих контрольных объектов будет также компактным. Требуется найти параметры правил, по которым множество Vu делится на К классов, и по которым можно будет распознавать принадлежность к созданным классам и новых контрольных объектов.

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

Примером алгоритма, решающего задачи такого типа, является алгоритм ТPФ (таксономические решающие функции) [1]. Он основан на применении к смеси выборок методов таксономии и находит такое разбиение выборки на классы, которое с одной стороны удовлетворяет требованиям геометрической компактности (объекты одного класса должны быть похожими друг на друга и отличаться от объектов других классов) и однородности (в одном кластере должны преобладать объекты из множества Vv одного и того же образа). Основу алгоритма ТPФ составляет алгоритм таксономии KRAB [1], который формирует классы произвольной формы, что является его преимуществом и одновременно - недостатком: получаемые результаты не обладают наглядностью, что затрудняет их интерпретацию.

В данной работе для решения задач всех трех указанных типов предлагается использовать алгоритм автоматической классификации FRiS-TDF, основанный на функции конкурентного сходства (FRiS-функции), эффективность которой при решении задач распознавания и таксономии демонстрировалась нами в прошлых работах [2,3]. Ее определение в данной работе расширяется на случай смешанных выборок. Решающее правило, получаемое с помощью FRiS-функции, имеет вид набора эталонных объектов («столпов»), стоящих в центрах линейно разделимых кластеров, в составе которых преобладают верифицированные объекты одного и того же образа. Получаемые кластеры должны удовлетворять требованиям геометрической компактности и однородности. Каждый распознаваемый объект включается в состав того кластера, конкурентное сходство со столпом которого максимально.

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

Данная работа имеет следующую структуру. Определение FRiS-функции для смешанной выборки содержится во втором разделе, описание алгоритма построения решающего правила для смешанной выборки представлено в разделе 3, а описание экспериментов - в разделе 4.

1 Функция конкурентного сходства

Понятие функции конкурентного сходства [2] возникло из идеи, что для оценки близости между объектами необходимо учитывать конкурентную ситуацию. Так, при распознавании двух образов, для оценки конкурентного сходства объекта z с первым образом необходимо учитывать не только расстояние r1 от z до этого образа, но и расстояние r2 до ближайшего конкурирующего образа (в случае двух образов это будет расстояние от z до второго образа). Нормированная величина конкурентного сходства при этом вычисляется по следующей формуле:

Значения этой функции меняются в пределах от -1 до +1. Если контрольный объект z совпадает с объектом первого образа, то r1=0 и F1/2(z)=1. При расстояниях r1=r2 значение F1/2(z)=0. Это значит, что объект z одинаково похож (и не похож) на оба образа и лежит на границе между ними. Если же контрольный объект z совпадает с объектом второго образа, то r2=0 и F1/2(z)=-1. Определенная таким способом функция конкурентного сходства хорошо согласуется с механизмами восприятия сходства и различия, которыми пользуется человек. Кроме того она оказалась эффективным инструментом для оценки компактности разбиения выборки на образы (кластеры в случае задачи таксономии).

Вычисление FRiS-функции по классифицированной выборке

Рассмотрим задачу оценки компактности двух образов А и В по верифицированной выборке Vv. Для всех объектов выборки вычисляется величина их конкурентного сходства со «своим» образом, потому r1 - это расстояние до «своего» образа, а r2 - расстояние до «конкурирующего» образа. При этом в качестве расстояния от объекта z до образа берется расстояние от z до ближайшего объекта этого образа. Обозначим VA- множество объектов образа A, VB- множество объектов образа B, Vv=VAVB. Тогда для произвольного объекта zVA расстояния r1 и r2 вычисляются по формулам:

и .

Аналогично для объекта zVB:

, .

Теперь для каждого объекта z выборки Vv по формуле (1) можно вычислить величину F(z) конкурентного сходства этого объекта со своим образом и затем найти среднее значение сходства всех объектов со своими образами.

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

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

, ,

для zVB :

, .

Здесь SA - множество столпов первого образа, а SВ - множество столпов второго образа. По этим расстояниям по формуле (1) можно вычислить величины конкурентного сходства FS(z) всех объектов выборки Vv со своими столпами. При усреднении этих величин по формуле (2) мы получим интегральную характеристику , определяющую, насколько система столпов S полно описывает выборку. Чем больше эта величина, тем выше точность описания. Если же из всех возможных систем столпов заданного размера L мы каким-то образом отыщем оптимальную систему , то величина может использоваться и в качестве оценки компактности образов, составляющих выборку. А система столпов S* при удачном выборе величины L (обычно для этого используют L, равную минимальному числу столпов, необходимых для безошибочного распознавания обучающей выборки) представляет собой эффективное решающее правило, пригодное для распознавания новых объектов.

Вычисление FRiS-функции по неклассифицированной выборке

Особенностью этой задачи является то, что на начальном этапе принадлежность объектов выборки Vu к тому или иному образу (классу) неизвестна. Все объекты, как бы, принадлежат одному образу. Если задана система столпов S этого образа, то мы можем определить расстояние r1 от произвольного объекта z до «своего» образа, как расстояние от z до ближайшего столпа из множества S:

.

Но отсутствие образа-конкурента не позволяет определить расстояние r2 от объекта z до ближайшего чужого столпа. В этом случае в рассмотрение вводится виртуальный образ-конкурент, ближайший столп которого удален от каждого объекта выборки на фиксированное расстояние, равное r*. С учетом этого, вместо обычной FRiS-функции будем использовать некую ее модификацию, которая для произвольного объекта zVu имеет вид:

Эта модификация называется редуцированной функцией конкурентного сходства [3]. Если усреднить ее по всем объектам не классифицированной выборки Vu , то полученная величина:

характеризует то, насколько точно и полно система столпов S описывает не классифицированную выборку.

1.1 Вычисление FRiS-функции по смешанной выборке

Рассмотрим теперь, как будет меняться методика вычисления функции конкурентного сходства при переходе к смешанной выборке Vmix, состоящей как из классифицированной Vv так и не классифицированной Vu выборок. Под не классифицированной здесь и далее мы будем понимать выборку, имена образов для объектов которой неизвестны и должны быть восстановлены. В случае задачи распознавания двух образов A и B, все объекты такой смешанной выборки можно разделить на три класса Vmix=VAVBVC. К классу VA мы отнесем объекты образа А, к классу VB - объекты образа В, а к классу VC - объекты, имя образа которых неизвестно, то есть объекты не классифицированной выборки (VC =Vu) .

В простейшем случае в качестве расстояния от объекта z до образа мы будем использовать расстояние от z до ближайшего объекта этого образа. Появление объектов класса VC усложняет процесс определения этих расстояний, так как для произвольного объекта выборки ближайший «свой» и ближайший «чужой» объект могут оказаться среди множества не классифицированных объектов. Потому ближайший «свой» объект для zVA отыскивается по формуле:

,

для zVB - по формуле:

.

Что касается класса VC, то будем считать, что ближайший «свой» для произвольного объекта zVС может принадлежать любому классу, то есть:

.

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

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

,

для объекта zVB :

.

При нахождении расстояния r2 от zVС до ближайшего конкурента мы делаем выбор между расстоянием rA от z до ближайшего объекта образа А, расстоянием rВ от z до ближайшего объекта образа В и расстоянием r* до виртуального конкурента. Минимальное расстояние из первых двух - это расстояние от z до «своего» образа. Следовательно, расстоянием до конкурента может быть либо максимальное из этих двух расстояний (rA или rВ), либо расстояние r* до виртуального объекта. В итоге для объектов zVC: таксономия распознавание алгоритм

.

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

Теперь рассмотрим случай, когда в качестве расстояния от объекта z до образа используется расстояние от z до ближайшего столпа этого образа. Система столпов S, описывающая выборку, в этом случае может быть разделена на две части: SA - множество столпов, описывающих образ А, SB - множество столпов, описывающих образ В. При этом не классифицированные объекты из множества VC могут выступать как в роли столпов образа А, так и в роли столпов образа В. Тогда, расстояние от объекта zVA до ближайшего «своего» и ближайшего конкурента из множества столпов S вычисляется по формулам:

и ,

для объекта zVB:

и ,

для объекта zVC:

и .

Вычисляя значения конкурентного сходства Fmix(z) для каждого zVmix по формуле (1) и усредняя их по всем объектам смешанной выборки V=Vv Vu , мы получаем величину:

,

которая является характеристикой качества описания этой выборки системой столпов S.

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

.

При этом при Vv=, данная задача сводится к задаче таксономии, а при Vu= - к задаче распознавания. Предложенный в следующем разделе алгоритм FRiS-TDR позволяет решить поставленную задачу.

2 Алгоритм FRiS-TDR

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

1. Объект аVА назначается единственным столпом образа А. При этом расстояния от произвольного объекта z до ближайшего «своего» и ближайшего «чужого» столпов отыскиваются по следующим правилам. Если объект zVA:

, ,

если объект zVB:

, .

Для объекта zVC мы вычисляем расстояние rA от z до ближайшего объекта образа А и расстояние rB от z до ближайшего объекта образа В. Если rA <rB , то с точки зрения гипотезы локальной компактности, объект z скорее принадлежит образу А, так что в качестве расстояния до своего образа нужно брать расстояние от z до объекта а. А расстоянием до столпа чужого образа будет служить величина rB, если она не превышает r*. Так что,

.

Если же rA>rB, то объект z не принадлежит образу А и своим столпом для него будет ближайший объект из множеств VB или VC , а чужим - объект а, если расстояние до него не превышает величины r* . В этом случае:

, ,

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

2. Процесс повторяется для всех объектов класса VА.

3. Объект bVB назначается единственным столпом образа В. При этом расстояния от произвольного объекта z до ближайшего «своего» и ближайшего «чужого» отыскиваются по следующим правилам. Если объект zVA:

, ,

если объект zVB:

, .

Для объекта zVC мы вычисляем расстояние rA от z до ближайшего объекта образа А и расстояние rB от z до ближайшего объекта образа В. Если rA <rB:

, ,

если же rA>rB:

, .

Опираясь на эти расстояния, мы вычисляем функцию конкурентного сходства Fmix(z) для всех объектов смешанной выборки и, усреднив ее, получаем величину пригодности b на роль столпа образа В.

4. Процесс повторяется для всех объектов класса VВ.

5. Так как для произвольного объекта c из класса VC его принадлежность к образам неизвестна, то он сначала пробуется на роль единственного столпа образа А и вычисляется его эффективность в данной роли. Для этого выполняется последовательность действий из п.1 описываемого алгоритма. Затем объект с назначается на роль единственного столпа образа В и по п.2 вычисляется величина .

6. Процесс повторяется для всех объектов класса VС.

7. В качестве первого столпа образа А выбирается объект s1VAVC, который обеспечил максимум величине . В качестве первого столпа образа В выбирается объект s2VBVC, который обеспечил максимум величине .

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

8. Поочередно каждый объект аVА добавляется в текущую систему столпов Si, состоящую из i столпов в качестве дополнительного столпа образа А. По формуле (3) вычисляется качество этой системы . Эта процедура повторяется для всех объектов класса VА.

9. Поочередно каждый объект bVB добавляется в текущую систему столпов Si в качестве дополнительного столпа образа В. По формуле (3) вычисляется качество этой системы . Эта процедура повторяется для всех объектов класса VB.

10. Поочередно каждый объект cVC добавляется в текущую систему столпов Si в качестве столпа образа А. По формуле (3) вычисляется качество этой системы . Затем этот же объект рассматривается как объект второго образа и для этого случая получается общее качество системы . Эта процедура повторяется для всех объектов класса VС.

12. Объект si+1 смешанной выборки Vmix, добавление которого в систему столпов Si максимально увеличивает ее качество, признается i+1-м столпом. Другими словами Si+1=Sisi+1, где .

13. Процесс наращивания системы столпов (повторение п. 8-12) происходит до достижения одного из условий остановки.

Самым распространенным условием остановки алгоритма построения решающего правила в виде системы столпов является достижение того количества столпов, которое позволяет с заданным уровнем точности распознавать обучающую выборку. Чаще всего требуют безошибочного распознавания, хотя это требование может приводить к переобучению. Другим вариантом является задание максимального допустимого количества столпов в системе. Мы же в качестве критерия остановки алгоритма использовали ту же методику, что была использована в задаче таксономии для определения оптимального числа кластеров [3]. Для этого, для произвольного объекта z находился ближайший столп на роль «своего» и следующий по близости на роль «конкурента». Среднее значение FRiS-функции Fi, вычисленное по этим правилам, сравнивалось с аналогичной величиной, полученной на меньшем и на большем числе столпов. Выполнение условия Fi-1<Fi и Fi+1<Fi считалось индикатором того, что число столпов равное i соответствует одному из наиболее предпочтительных разбиений множества объектов на кластеры.

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

Предложенный алгоритм является линейным. Его трудоемкость имеет порядок сложности , где M - количество объектов в смешанной выборке, N - размерность признакового пространства, а kmax - максимальное количество столпов.

5 Примеры работы алгоритма

Для наглядности мы приводим результаты работы предложенного алгоритма на простейших двумерных задачах с небольшим числом объектов, которые человек может решать «на глаз» и, как следствие, сравнивать свое решение с решением, предложенным алгоритмом. На первых трех рисунках демонстрируется универсальность алгоритма FRiS-TDR, который решает задачу универсальной классификации для верифицированной выборки (Рис.1), для смешанной выборки (Рис.2) и для неверифицированной выборки (Рис.3). Здесь и далее объекты класса А обозначаются на рисунках кружками, объекты образа В - квадратиками, а объекты, классовая принадлежность которых неизвестна, - крестиками. Объекты, выбранные алгоритмом на роль столпов, обведены пунктиром, разделяющие границы для кластеров представлены пунктирными ломаными линиями.

Рис.1. Результаты работы алгоритма FRiS-TDR на задаче распознавания

Рис.2. Результаты работы алгоритма FRiS-TDR при классификации смешанной выборки



Рис.3. Результаты работы алгоритма FRiS-TDR на задаче таксономии

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

Для иллюстрации того факта, что построение решающего правила на основе смешанной выборки может улучшать качество распознавания, решалась задача, аналогичная представленной на Рис.2, но информация из неверифициорванной выборки в процессе построения решающего правила не использовалась. Результаты этого эксперимента представлены на Рис.4. На нем разделяющая граница, построенная по смешанной выборке, представлена пунктирной линией, а разделяющая граница, построенная только по обучающей выборке - сплошной линией.

Рис.4. Решающие правила, построенные по смешанной (пунктирная линия), и обучающей (сплошная линия) выборкам.

На Рис.5 представлены результаты работы предложенного алгоритма на более сложной тестовой задаче. Число столпов определялось автоматически. При этом было выделено два кластера, в которые не попал ни один представитель обучающей выборки. Эти кластеры могут рассматриваться как кандидаты на принадлежность к неизвестному образу.

Рис.5. Результаты работы алгоритма FRiS-TDR на сложной смешанной выборке.

Заключение

Проведенные исследования позволяют сделать следующие выводы:

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

2. Критерием для выбора наилучшего варианта решения служит оценка FRiS-компактности формируемых кластеров

3. Использование FRiS-функций позволяет выбирать столпы, сходство с которыми максимально полно и точно описывает выборку в-целом (как объекты, представленные для обучения, так и объекты, предназначенные для распознавания), а также определять оптимальное число столпов.

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

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

3 Благодарности

Данная работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, Грант № 08-01-00040.

Литература

[1] Загоруйко Н.Г.: Прикладные методы анализа данных и знаний.: Изд. ИМ СО РАН, Новосибирск, 1999.

[2] Борисова И.А., Дюбанов В. В., Загоруйко Н.Г., Кутненко О.А.: Использование FRiS-функции для построения решающего правила и выбора признаков(задача комбинированного типа DX) // Материалы Всерос. Конф. ЗОНТ-2007, Новосибирск, 2007, том 1, стр. 37-44.

[3] Борисова И.А., Загоруйко Н.Г.: Функция конкурентного сходства в задаче таксономии // Материалы Всерос. Конф. ЗОНТ-2007, Новосибирск, 2007, том 2, стр. 67-76.

[4] Загоруйко Н.Г., Борисова И.А., Дюбанов В.В., Кутненко О.А.: Меры сходства, компактности, информативности и однородности обучающей выборки // (данный сборник)

Аннотация

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

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

Размещено на Allbest.ru