Функция конкурентного сходства и алгоритм FRiS-СТОЛП

в 6:50, , рубрики: Песочница

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

FRiS-функция

FRiS — мера схожести двух объектов относительно некоторого третьего объекта. В отличие от упомянутых ранее классических мер расстояния, эта функция позволяет не просто сказать, похожи объекты друг на друга или нет, но и уточнить ответ на вопрос «по сравнению с чем?». Это позволяет большее количество факторов при классификации.

Пусть дано некоторое множество объектов М с заданной метрикой ρ(a, b). Функция конкурентного сходства объектов a, b ∈ M относительно x ∈ M задается так:

Функция конкурентного сходства и алгоритм FRiS СТОЛП

Легко заметить, что значения функции лежат в интервале [–1, 1], причем FRiS(a, a, x) = 1 и FRiS(a, b, a) = –1, В случае же равенства расстояний ρ(a, x) и ρ(b, x) функция примет значение 0.

Пример

Функция конкурентного сходства и алгоритм FRiS СТОЛП

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

FRiS-СТОЛП

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

Сам алгоритм заключается в следующем. Пусть на входе имеется некоторая обучающая выборка X = {(xi, ci )}, где xi — объекты, а ci ∈ C — классы, которым они принадлежат (естественно, число классов меньше, чем объектов).

Опишем две вспомогательные функции:

NearestNeighbour(m, M) — возвращает ближайший к m объект из множества M. Реализация близка к очевидной.

FindEtalon(Xс, E) — возвращает новый эталон для класса c исходя из уже имеющихся эталонов E и набора Xс элементов класса c. Для этого для каждого элемента x из Xс вычислим три характеристики:

  • Толерантность:
    Функция конкурентного сходства и алгоритм FRiS СТОЛП
  • Обороноспособность:
    Функция конкурентного сходства и алгоритм FRiS СТОЛП
  • Эффективность:
    Функция конкурентного сходства и алгоритм FRiS СТОЛП
    (параметр λ выбирается из интервала [0, 1] и задает относительный вес характеристик)

Функция FindEtalon(Xс, E) возвращает элемент x из Xс , имеющий максимальную эффективность Ex .

Теперь займемся собственно построением множества эталонов. Для начала проинициализируем начальные множества эталонов для всех классов c ∈ C:
Функция конкурентного сходства и алгоритм FRiS СТОЛП
и искомые множества:
Функция конкурентного сходства и алгоритм FRiS СТОЛП

1. Построим множество правильно классифицированных объектов U:
Функция конкурентного сходства и алгоритм FRiS СТОЛП

2. Выбросим классифицированные на предыдущем шаге объекты из дальнейшего рассмотрения:
Функция конкурентного сходства и алгоритм FRiS СТОЛП
Функция конкурентного сходства и алгоритм FRiS СТОЛП
(для всех c ∈ C)

3. Добавим новые эталоны для каждого класса c ∈ C:
Функция конкурентного сходства и алгоритм FRiS СТОЛП

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

Более подробно с FRiS-функцией можно познакомиться в работе Н.Г. Загоруйко и И.А. Борисовой Функции конкурентного сходства в задаче таксономии / Знания-Онтологии-Теории (ЗОНТ-07).

Автор: r4tz52

* - обязательные к заполнению поля