Методы добычи данных при построении локальной метрики в системах вывода по прецедентам

Л. Е. Карпов, В. Н. Юдин
Препринт ИСП РАН

Назад   Оглавление   Вперёд

6. Понятие контекстно-зависимой локальной метрики

Обычно в методе "ближайшего соседа" применяется простая евклидова метрика – сумма квадратов отклонений по разным параметрам. Это быстрый и часто неплохо работающий метод. Первый его минус заключается в том, что когда число анализируемых показателей, или количество полей записей, сравнимо с числом самих записей, получается пространство очень большого числа переменных с редким облачком точек. В этом случае соседство точек в терминах евклидовой метрики часто не означает естественной близости значений соответствующих записей, а в значительной степени обусловлено выбранным для анализа набором показателей. Когда же, как это довольно часто бывает, число параметров превышает число записей, облако точек становится настолько редким, что никаких разумных оценок этот метод, как правило, не дает. Другим слабым местом рассматриваемого метода, также как и у нейросетей, является удовлетворительный прогноз лишь достаточно непрерывных и гладких зависимостей.

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

Другая проблема возникает при работе с большими базами прецедентов, когда вероятность выбора близкого соответствия высока, а потребность в адаптации решения – низка, что ведет к дополнительным проблемам. Исследование в [Smyth 95] показало, что такие системы страдают от так называемого "заболачивания", которое происходит, когда стоимость поиска знания перевешивает выгоду от применения этого знания.

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

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

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

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

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

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

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

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

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

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

В работах Дюка [Дюк 94, Дюк 96] предложен подход к конструированию собственного пространства признаков и нахождению индивидуальной меры, который назван локальным преобразованием пространства признаков. Это пространство образуется путем перехода к новой векторной переменной, например,

∆ = X - X_i

где X_i – выбранный объект.

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

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

Здесь задача определения локальной метрики заключается в нахождении линейного преобразования новой векторной переменной. Для ее решения пригоден хорошо разработанный аппарат методов многомерного линейного анализа данных.

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

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

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

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

Назад   Оглавление   Вперёд