13.3. АДАПТИВНАЯ ОЦИФРОВКА В СЛУЧАЕ ИЗВЕСТНОЙ ФИКСИРОВАННОЙ МЕРЫ СХОДСТВА

Адаптивную оцифровку определяют аналогично адаптивному расстоянию (см. гл. 12), следуя основным этапам метода динамических сгущений, определенным в гл. 1. Мы будем пользоваться подходом, описанным в [4], вытекающим из общего случая, представленного [17].

13.3.1. Выбор пространства покрытий

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

13.3.2. Структура представительства, пространство представительств

13.3.2.1. Пространство представительств

Пространство представительств определяется равенством где вводится в 13.2.3.1. Представительство некоторого имеет вид: вектор, координат которого являются центрами тяжести В по соответствующим переменным, с Наконец, раз).

13.3.2.2. Мера сходства между объектом и представительством

Вспомним, что множество можно рассматривать как подмножество векторного пространства где размерность, необходимая Для представления переменных. Степень годности представительства

для определения характеристик объекта может быть измерена с помощью расстояния

где вектор перекодированных значений переменных на объекте. Представительство нам подходит тем больше, чем меньше величина (1). Определим меру сходства между объектом и представительством следующим образом:

где весовой коэффициент, приписанный объекту.

13.3.3. Оптимизируемый критерий

Критерий представляет собой отображение определяемой формулой

где центр тяжести Таким образом, (3 можно представить в виде

где — весовой коэффициент, приписанный объекту х, а - вектор перекодированных значений переменных на объекте х. Выражение (4) эквивалентно

где — вектор перекодированных значений переменной на объектах

— вектор координатами которого являются значения центров тяжести классов по переменной матрица размера состоящая из нулей и единиц, причем элемент столбца равен 1, если объект принадлежит классу Этот критерий позволяет определить меру адекватности представительства разбиению

13.3.4. Задача оптимизации

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

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

Итак, ищется решение следующей задачи:

Здесь вектор-столбец из единиц; множество матриц для всевозможных разбиений из

13.3.5. Описание алгоритма

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

13.3.5.1. Функция назначения

Для каждого и является разбиением таким, что

равенство возможно лишь при

Поскольку где вес объекта, а вектор перекодированных значений переменных на объекте имеем

Если теперь вспомнить, что то станет очевидно, что класс состоит из тех элементов которые по мере сходства (2) ближе к представлению чем к любому другому

Замечание. Безразлично, искать ли разбиение или матрицу

При заданном известны В этом случае является решением задачи оптимизации 13.3.4.

13.3.5.2. функция представительства

Для каждого разбиения множества на классов значением является представительство где При этом является решением задачи (7), которая распадается на задач:

Нам придется рассмотреть задачу минимизации для всех трех типов переменных.

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

13.3.5.2.1. Оцифровка номинальных данных

Вектор перекодированных значений переменной можно записать в виде

где логическая таблица индикаторных переменных градаций признака вектор, координатами которого являются метки, приписываемые соответствующим градациям При этом

ется задача оптимизации (7), где индекс соответствует номинальной переменной Решение зависит от того, является ли нулевым вектором. Поэтому рассмотрим два случая:

а) g - нулевой вектор из Это вырожденный случай, (7) сводится к определению вектора который бы удовлетворял

решением являются векторы единичной длины в метрике, задаваемой матрицей расположенные на гиперплоскости, которая определяется вторым уравнением (8);

б) g - ненулевой вектор из Вектор известен, будем что он центрирован в метрике Покажем, что решение -центрировано и является решением (7).

Задача (9) эквивалентна (10):

Для (10) функция Лагранжа имеет вид

где а — неопределенный множитель. Для того чтобы существовало решение (10), необходимо выполнение следующих двух условий:

заметим, что Поскольку очевидно, что второе условие выполнено. Если выполнено первое условие, то

и, поскольку

где проектор на векторное подпространство В силу того, что

и решение (9) имеет вид

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

Предложение Если вектор центрирован в метрике то это справедливо и для Доказательство. Имеем

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

Итак, (11) является центрированным вектором перекодированных значений номинальной переменной .

13.3.5.2.2. Оцифровка ординальных данных

В этом случае вектор перекодированных значений переменной вид

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

а) g - нулевой вектор из Обозначим через выпуклый конус в пространстве Требуется найти вектор , удовлетворяющий системе уравнений (8). Решением является любой вектор, имеющий единичную норму в метрике, определяемой матрицей и принадлежащей пересечению гиперплоскости, задаваемой уравнением (8) с конусом

б) - ненулевой вектор. Определим . Тогда задачу минимизации можно записать следующим образом:

Будем считать, что заданный вектор центрирован в метрике При решении (12) используются следующие три утверждения:

1. С помощью алгоритма Крускала (см. [5], [6]) можно найти

2. Вектор при котором достигается (13), центрирован (проекция на не нарушает центрированности).

3. С помощью теоремы 1, имея решение (13), можно получить решение (12) (см. [8]).

Теорема 1. Всякое нормированное в метрике решение (13) является решением (12).

Доказательство приводится в [8] и [13].

13.3.5.2.3. Оцифровка количественных данных

Множество всевозможных значений количественной переменной принадлежит Положим

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

1. Метод полиномиальной регрессии. Задача оптимизации имеет

или, что эквивалентно,

Как и для номинальной переменной, возможны два случая:

а) g - нулевой вектор пространства Всякий нормированный в метрике вектор принадлежащий гиперплоскости дает нам вектор меток удовлетворяющий (14) и являющийся решением (15);

б) g - ненулевой вектор. Вектор известен, как и прежде будем считать, что он центрирован в метрике Проекция а, на также будет Отцентрированной (согласно предложению 1). Таким образом, последнее уравнение (15) всегда будет выполнено. Решая (15) методом неопределенных множителей, получим

где -ортогональный проектор на пространство, порожденное столбцами матрицы

2. Второй подход основан на минимизации невязки. Будем считать, что вектор известен и Поскольку проекция на центрирована (согласно предложению 1), из теоремы 1 вытекает, что для решения (15) достаточно найти вектор реализующий

и пронормировать его в метрике С другой стороны, является суммой квадратов остатков следующей модели:

Решением задачи (16) является

и

где

Если это выражение представить в виде

то можно рассмотреть геометрическую интерпретацию при (рис. 13.3).

Рис. 13.3

Здесь (см. [12]). С другой стороны,

где единичная матрица размера оператор ортогонального проектирования на т. е. на -ортогональное дополнение. Квадрат нормы вектора имеет вид

Доказательство этого соотношения приводится в [12]. Кроме того,

Нормируя с в метрике можно получить решение задачи (15) (см. теорему 1).

Заключение. В случае, когда — количественная переменная, метками являются координаты вектора с, который получается после нормирования в метрике вектора

где вектор принадлежит гиперплоскости и удовлетворяет

13.3.6. Сходимость алгоритма

Здесь будет обозначать номер итерации. Предложение 2. Последовательность определяется в 13.3.5) является монотонно убывающей и имеет предел.

Доказательство. Имеем

Таким образом,

т. е. Последовательность монотонно убывает, и поскольку все ее члены положительны, она сходится.

13.3.7. Связь между каноническим анализом и оцифровкой номинальных данных

Введем следующие обозначения:

Задача (9) эквивалентна следующей: найти вектор Угол которого с подпространством минимален.

В самом деле, минимизировать расстояние между вектором из и некоторым вектором из равносильно минимизации угла между этими векторами. Положим оператор -ортогонального проектирования на

Пусть угол вектора

Для того чтобы сделать как можно меньше, надо решить задачу:

В силу того, что

(так как эта задача сводится к

Уравнение Лагранжа для (20) имеет вид

и

Учитывая (21) и условие задачи (20), имеем

т. е. к равно максимальному значению Если теперь обе части (22) умножить слева на положив получим

отсюда следует

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

так как

отсюда

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

Равенство (23) превращается в

Из условия нормировки вектора с, вытекает:

Следовательно,

Этот же результат был получен прямо (см.

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