Функции конкурентного сходства в задаче таксономии

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

Институт математики им. Соболева СО РАН

Функции конкурентного сходства в задаче таксономии

Борисова И.А.

Загоруйко Н.Г.

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

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

Позволяет получать таксоны произвольной формы.

Строит описание полученных таксонов в терминах эталонных образцов (столпов). Это повышает наглядность результатов таксономии и упрощает процедуру распознавания новых объектов.

Автоматически определяет наилучшее (с точки зрения эксперта) число таксонов.

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

Во многих задачах анализа данных используется понятие «похожести», «близости», «сходства». На меру «сходства» объекта с образом так или иначе опираются все правила распознавания. В группы по «похожести» объединяются объекты при таксономии. Но мера «сходства», как и всякое относительное понятие, даже при переходе в абсолютную шкалу не может определяться корректно без учета контекста. Так Москва и Новосибирск окажутся «близкими», если сравнивать расстояние между ними с расстоянием от Москвы до Солнца, и «далекими», если рассматривать два объекта, находящихся в пределах Садового кольца. Для учета контекста в некоторых мерах сходства рассматривается конкурентная ситуация. Так в правиле ближайшего соседа (kNN) решение о принадлежности объекта z к первому образу принимается не в том случае, когда расстояние r1 «мало», а когда оно меньше расстояния r2 до конкурирующего образа. Следовательно, чтобы оценить похожесть объекта z на первый образ, нужно знать расстояние не только до него, но и до ближайшего конкурента, и сравнивать эти расстояния в шкале порядка. Если же нас интересует мера конкурентного сходства, измеренная в абсолютной шкале, то можно использовать нормированную величину F_1/2 = (r2-r1)/( r2+r1). Именно ее мы называем функцией конкурентного сходства или FRiS-функцией (от Function of Rival Similarity).

Функция F хорошо согласуется с механизмами восприятия сходства и различия, которыми пользуется человек, сравнивая некий объект с двумя другими объектами. Величина F_i/j характеризует сходство объекта Z с эталоном образа S_i в конкуренции с эталоном образа S_j. Значения этой функции меняются в пределах от +1 до -1. Если контрольный объект Z совпадает с эталоном первого образа, то r1=0 и F_1/2 =1, а F_2/1 = -1. Это говорит об абсолютном сходстве объекта Z с эталоном первого образа и о максимальном его отличии от эталона второго образа. При расстояниях r1=r2 значения F_1/2 = F_2/1 = 0, что указывает на границу между образами.

Далее приводится формальное определение функции конкурентного сходства и ее модификации, которые используются в алгоритме таксономии, описываемом в данной статье. Рассматривается выборка А, состоящая из М объектов, разбитых на k образов. Каждый образ i описан множеством из n_i эталонных образцов (столпов) Si={s_i1, s_i2, …,s_ini}. Для любого объекта aA можно найти расстояние r(а,Si) до ближайшего столпа образа i. Тогда r1(а,S)=- расстояние до ближайшего образа i*, а r2(a,S)= - расстояние до ближайшего конкурента. FRiS-функция, вычисленная для объекта а, F(a,S)=(r2(a,S)-r1(a,S))/(r2(a,S)+r1(a,S)) является мерой сходства объекта а с образом i* в конкуренции с другими образами. Если же мы найдем среднее значение FRiS-функции при фиксированном наборе столпов S по всей выборке, то полученная величина:

F(S)= (1)

характеризует, насколько полно этот набор столпов описывает выборку. Чем больше F(S) , тем более подробное и точное описание выборки у нас имеется.

Особенностью задачи таксономии является то, что на начальном этапе принадлежность объектов выборки к тому или иному образу (классу) неизвестна. Все объекты множества А, как бы, принадлежат одному образу. Если зафиксировать набор столпов этого образа S={s1, s2, …, sk}, то для каждого объекта aA можно найти расстояние r1(а,S) (от объекта до ближайшего столпа из множества S). Но отсутствие образа-конкурента не позволяет определить расстояние r2 (от объекта до ближайшего столпа образа-конкурента). В связи с этим, на первом этапе вводится виртуальный образ-конкурент, ближайший столп которого удален от каждого объекта выборки на фиксированное расстояние, равное r2*. Таким образом, в задаче таксономии вместо обычной FRiS-функции мы будем использовать некую ее модификацию, которая для объекта aA имеет вид F*(a,S)=(r2*-r1(a,S))/(r2*+r1(a,S)). Далее в тексте эта модификация будет называться редуцированной FRiS-функцией. Помимо этого нас будет интересовать среднее значение редуцированной функции для всех M объектов множества А:

F*(S) = . (2)

Если столпы расположены в центрах локальных сгустков объектов, то F*(S) имеет максимальное значение. Именно значение средней редуцированной функции конкурентного сходства мы использовали в качестве индикатора при поиске центров локальных сгустков.

Рис. 1. Использование редуцированной FRiS-функции в качестве индикатора локальных сгустков. Локальные максимумы этой функции располагаются в центрах локальных сгустков

На Рис. 1 представлена поверхность F*({x,y}), порожденная набором объектов А, показанных точками на плоскости.

Алгоритм FRiS-Tax

Перейдем к описанию алгоритма, который использует описанные выше полезные свойства FRiS-функции для построения автоматической классификации. Его работа состоит из двух этапов. На первом этапе, называемом FRiS-Cluster, отыскиваются центры локальных плотностей объектов. Каждый из них рассматривается как эталонный образец (столп) некоторого кластера. Все объекты выборки естественным образом распределяются между кластерами. Каждый объект a относится к тому кластеру, чей эталонный образец оказался к нему ближайшим. Полученное разбиение уже может рассматриваться как готовый результат, если эксперта устраивает его качество. В противном случае полученная кластеризация передается на второй этап работы алгоритма, называемый FRiS-Class. На этом этапе происходит процедура укрупнения таксонов, усложнения их формы. Соседние кластеры, удовлетворяющие определенным условиям, признаются принадлежащими одному классу. Это позволяет создавать таксоны произвольной формы, не обязательно линейно разделимые.

Кластеризация (этап FRiS-Cluster)

Предложенный алгоритм выбирает число кластеров автоматически. Пользователь задает лишь предельное число кластеров К., среди которых он хотел бы получить наилучший вариант кластеризации. Алгоритм последовательно ищет решения задачи кластеризации для всех значений k=1, 2,…,K, чтобы потом выбрать из них наиболее удачные. Происходит это следующим образом:

При k=1 произвольно выбранный объект а назначается столпом и для него по формуле (2) вычисляется средняя редуцированная FRiS-функция F*({a}).

П.1 повторяется при поочередном назначении столпами всех М объектов выборки. В качестве первого столпа s1 выбирается объект a*, для которого величина F*({a*}) оказывается максимальной.

После того, как первый столп зафиксирован, определяется, какой объект будет наилучшим в роли второго столпа. Произвольный объект a, не совпадающий с s1, назначается вторым столпом. Затем для набора из двух столпов {a, s1} вычисляется средняя редуцированная FRiS-функция F*({a, s1}).

На роль второго столпа поочередно назначаются все объекты выборки, не совпадающий с s1, и повторяется п. 3. В качестве второго столпа s2 выбирается тот объект а*, который в паре с s1 обеспечивает максимальное значение средней редуцированной функции конкурентного сходства F*({a*, s1}).

После того, как были найдены два столпа, вся выборка распределяется между ними по следующему правилу. Объект относится к тому кластеру, расстояние r1 до столпа которого минимально. Объекты, присоединенные к первому столпу s1, образуют кластер А1. Объекты, ближайшим для которых оказался столп s2, образуют кластер A2.

Если при k=1 в первый кластер A1 входили все М объектов, то теперь при k=2 часть объектов переходит в новый кластер A2. При этом может получиться так, что для описания кластера A1 наилучшим окажется не столп s1, а какой-то другой объект из этого кластера. Чтобы найти окончательное положение эталонных объектов этих двух кластеров мы выполняем следующую процедуру. По очереди каждый объект а1 кластера А1 назначается на роль столпа, и по формуле (1) вычисляется средняя FRiS-функция F({a1,s2}). В качестве столпа выбирается такой s12, который обеспечивает максимальную величину среднего значения FRiS-функции. Аналогично в кластере A2 определяется новое положение столпа s2 по максимуму функции F({s12,a2}). На этом этапе вместо редуцированной FRiS-функции мы используем обычную FRiS-функцию, отражающую процесс конкуренции между реальными столпами. Среднее значение FRiS-функции при описании всей выборки столпами {s12,s22} и используется в качестве оценки качества кластеризации при числе таксонов k=2: Fs2= F({s12,s22}).

Для дальнейшего расширения списка столпов мы снова используем исходные столпы {s1, s2} и редуцированную FRiS-функцию. Все объекты выборки поочередно «пробуются» на роль третьего столпа. Для каждого из вариантов вычисляется средняя редуцированная функция конкурентного сходства и выбирается тот из них, для которого эта величина максимальна. Этот объект и фиксируется в качестве очередного столпа. После этого описанное в пункте 6 переопределение столпов делается для всех трех кластеров и вычисляется качество кластеризации Fs3.

Процесс продолжается, пока не будут получены кластеризации для всех значений k = 1,2,.., К. При этом каждый раз список столпов {s1,s2,…,sk}, с одной стороны, используется для нахождения очередного столпа sk+1, а, с другой, - для получения окончательного разбиения и оценки его качества Fsk для этого k (см. рис. 2). Подчеркиваем, что переходить от редуцированной к обычной FRiS-функции, так же как и переустанавливать столпы, целесообразно лишь для получения окончательного результата разбиения на k кластеров.

Очевидно, что в случае, когда все объекты выборки используются в качестве столпов (всего М столпов), качество кластеризации FsM достигает своего максимального значения, равного 1. Однако на пути к этому главному экстремуму имеются локальные максимумы. Наши эксперименты показали, что достигаются локальные максимумы при таком числе кластеров, которое человеком-экспертом в двумерном случае «на глаз» признается «разумным». Под «разумностью» в данном случае понимается то, что объекты, отнесенные экспертом к разным таксонам, в результате проведения кластеризации нашим алгоритмом оказываются в разных кластерах.

Рис. 2. Схема работы алгоритма на этапе FRiS-Cluster. Движению по вертикали вниз соответствует процесс наращивания числа столпов с использованием rFRiS-функции. Движению по горизонтали - уточнение положения столпов и вычисление качества кластеризации с использованием FRiS-функции

Построение классификации (этап FRiS-Class)

Часто классы, выделяемые экспертами, оказываются достаточно сложной формы, которую не удается описать единственным эталонным объектом. Именно поэтому в алгоритме FRiS-Tax предусмотрена процедура FriS-Class для объединения нескольких кластеров в один класс, которая запускается для наиболее удачных вариантов кластеризации, полученных на первом этапе.

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

Каждую пару кластеров Аi и Аj проверяют на наличие объектов, которые находятся около разделяющей их границы (в зоне конкуренции). Объект а считается относящимся к зоне конкуренции кластеров Аi и Аj, если выполняются следующие условия:

а) столпы кластеров Аi и Аj являются двумя ближайшими к нему столпами;

б) абсолютная величина FRiS-функции для этого объекта меньше некоторого порога F*;

в) расстояние от a до «своего» столпа меньше, чем расстояние между столпами si и sj. Это условие необходимо в связи с тем, что большие расстояния могут означать общую удаленность объекта от всех эталонов.

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

Расстоянием Dij между кластерами Ai и Aj считается минимальное расстояние между двумя объектами а и b, попавшими в зону конкуренции и принадлежащими разным кластерам.

Для этих объектов а из Ai и b из Aj, определяются расстояния Da и Db от каждого из них до ближайшего своего соседа.

Кластеры Ai и Aj считаются принадлежащими одному классу, если значения этих трех величин Dij, Da и Db мало отличаются друг от друга. Например, может проверяться следующее условие: Da<бDb&Db<бDa& Dij<б(Da+Db)/2, где б>1.

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

Выбор оптимального числа таксонов

Напомним, что при запуске алгоритма пользователь задает диапазон, в котором варьируется число кластеров k. После окончания первого этапа мы имеем по одному варианту кластеризации для каждого k из заданного диапазона с вычисленным качеством кластеризации Fs(k). На втором этапе алгоритма мы уже работаем лишь с теми вариантами кластеризации, качество которых оказалось локально-максимальным, то есть Fs(k-1)<Fs(k)&Fs(k+1)<Fs(k).

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

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

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

Рис. 3. Результаты работы алгоритма FRiS-Class - объединение 7 кластеров на 2 класса. Столпы здесь помечены пунктирной обводкой, а классы - изменением тона объектов

Для усложнения задачи число классов, на которое требовалось разбить представленное множество объектов, не задавалось. Единственным ограничением, зафиксированным перед началом работы, было то, что число столпов, построенных на первом этапе, не должно превышать 15. После завершения 1-го этапа работы алгоритма и выбора локальных максимумов для FRiS-функции, из 14 вариантов кластеризации осталось два - разбиение на 7 и 11 кластеров (рис. 4).

Оба варианта после процедуры укрупнения кластеров на 2-ом этапе дали идентичные результаты: в один таксон выделилось кольцо, а в другой - сгусток в центре. Таким образом, наш алгоритм автоматически определил, на какое число таксонов требуется разбить выборку. При этом его вариант решения задачи совпал с решением, которое выбирают эксперты.

Рис. 4. Динамика изменения качества кластеризации (FRiS-функции) в зависимости от числа кластеров. Локальные максимумы на графике обведены

На рис. 5 показаны еще 4 различных тестовых примера, для которых с помощью FRiS-функций удалось определить оптимальное число кластеров и классов.

Рис. 5. Примеры задач, успешно решенных алгоритмом FRiS-Class

Экспериментальная проверка алгоритма FRiS-Tax, сравнение с существующими аналогами

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

Всего в тестировании участвовало 5 алгоритмов. Все они оперируют понятием центра таксона, и после окончания своей работы предоставляют пользователю не только само разбиение, но и набор эталонных образцов - столпов. Это конечно же:

самый популярный на западе алгоритм k-means [3,4],

алгоритм Forel, «раскатывающий» множество исследуемых объектов на таксоны сферической формы с фиксированным радиусом [5],

алгоритм Scat, который из сферических таксонов, созданных алгоритмом Forel, конструирует таксоны более сложной формы [5],

алгоритм FRiS-Cluster, который создает линейно разделимые кластеры, и каждому кластеру ставит в соответствие один эталонный образец.

Алгоритм FRiS-Tax, который создает таксоны сложной формы, объединяя несколько кластеров в один таксон.

Рассмотрение нового алгоритма в двух вариациях объясняется тем, что каждая из них позволяет решать свой класс задач. FRiS-Cluster корректнее сравнивать с алгоритмами k-means и Forel, создающими таксоны простой формы, а FRiS-Class позволяет находить решения одинакового порядка сложности с алгоритмом Scat.

Рис. 6. Сравнение качества пяти алгоритмов таксономии

На Рис. 6 приводятся оценки качества таксономии (определяемого мерой однородности таксонов), полученной этими пятью алгоритмами для разного числа таксонов от 2 до 15. Нетрудно увидеть, что результаты алгоритма FRiS-Cluster сопоставимы с результатами конкурентов, а результаты FRiS-Tax превышают результаты конкурентов. Однако основное преимущество предложенного алгоритма состоит даже не в этом. Только использование FRiS-функции позволяет нам довольно четко определить, какой вариант таксономии следует предпочесть, на каком числе таксонов, следует остановиться. На Рис. 7. приводится динамика изменения качества кластеризации после этапа FRiS-Cluster. При изменении числа кластеров от 2 до 20 на графике проявляются 4 локальных максимума - при разбиении на 2, 5, 8 и 19 кластеров.

Рис. 7. Зависимость качества кластеризации (FRiS-функции) от числа кластеров

После запуска второго этапа алгоритма FRiS-Tax для этих четырех случаев были получены 4 варианта таксономии, характеристики которых приводятся в Таблице 1. Здесь среднее значение FRiS-функции, подсчитанное для таксонов сложной формы (классов), позволяет выбрать наиболее удачный варианты таксономии. Им оказался вариант, когда 8 кластеров образуют 5 классов.

Таблица 1

Так как величина однородности изначально не может использоваться для сравнения качества разбиений с разным числом таксонов, то единственным более или менее объективным критерием в данном случае может считаться экспертная оценка. А для ее понимания необходимо чуть глубже вникнуть в природу задачи. Представленные в обучающей выборке образцы по химическому составу состояли из железа с относительно небольшой долей тех или иных примесей (Fe+Pb, Fe+Tl, Fe+Mo, Fe+S, Fe+Ni, Fe+Ni+Mn, Fe+Ni+Co). В случае разбиения на 5 таксонов в одной группе оказались образцы, содержащие никель (Fe+Ni, Fe+Ni+Mn, Fe+Ni+Co), а оставшиеся четыре типа веществ образовали каждое свой таксон. Более подробный анализ никелевых смесей показал, что добавки кобальта (Со) и марганца (Mn) в них составляют не более одного процента. И вклад их в спектральный портрет образца был настолько незначителен, что он не проявлялся и при анализе спектров вручную. Поэтому можно считать, что разбиение, выбранное нашим алгоритмом на роль оптимального, действительно является наилучшим, которое можно было достигнуть на представленном материале.

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

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

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

Литература

конкурентный сходство автоматический информация

1. Борисова И., Загоруйко Н., Кутненко О.: Критерии информативности и пригодности подмножества признаков: Proceedings of the 8^th International Conf. KDS-2007, ITHEA Sofia, 2007, Vol. 2, p. 567-571.

2. Борисова И., Дюбанов В., Загоруйко Н., Кутненко О.: Использование FRiS-функции для построения решающего правила и выбора признаков (задача DX). (Данный сборник).

3. М.И. Шлезингер. О самопроизвольном разделении образов // Читающие автоматы и распознавание образов. Изд. «Наукова думка», Киев, 1965. СС. 46-61.

4. MacQueen J.: Some methods for classification and analysis of multivariate observations: Proceedings of the 5th Berkley Symposium on Mathematical Statistic and Probability, University of California Press, 1967, Vol.1, p. 281-297.

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

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