Программные продукты и системы

Ранее авторы уже анализировали однородность, сначала располагая правила, а затем наблюдения в зависимости от расположения правил (см. стр. 169–174 настоящего выпуска журнала). В данной работе сначала выделим группы, а затем разместим правила, определяющие эти группы. После вычисления расположения правил на плоскости выполним те же действия, как и в случае применения анализа однородности.

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

Для группировки наблюдений по классам требуется, чтобы Ui=Ui¢ для всех i, i¢Î{1, …, n}, таких, что Yi=Yi¢. Пусть  – позиция k-го класса, k={1, …, K}. Пусть также матрица-индикатор  размером K´m будет агрегатом матрицы G, где агрегирование проводится по K классам,

.                                                    (1)

При сделанных предположениях оптимизационная задача анализа однородности примет следующий вид:

                               (2)

при ограничениях

,                                           (3)

.                                                                 (4)

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

.                         (5)

Обозначим через  матрицу, состоящую из первых q собственных векторов матрицы .

Тогда решение (2) будет таким:

,                                                           (6)

.                                                         (7)

Выражение (7) определяет расположение правил R, после чего они запоминаются (фиксируются). Далее можно действовать, как и при вычислении положения наблюдений в анализе однородности, применив выражение U=diag(GGT)-1GR для вычисления расположения отдельных наблюдений.

Точность предсказания оценивается так же, как и при анализе однородности.

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

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

2.     Вычислить q-размерное вложение для правил R согласно (7).

3.     Вычислить позиции отдельных наблюдений U (для обучающих или тестовых данных) согласно выражению U=diag(GGT)-1GR.

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

Если применить метод секционирования к примеру, приведенному авторами при анализе однородности, получим результат, изображенный на рисунке 2. В данном случае точность определения ближайшего соседа составила 17 %, что несколько лучше, чем в случае применения анализа однородности. С другой стороны, существенно улучшена скорость вычислений: теперь разложение по собственным векторам осуществляется для матрицы размером K´m, где K=8, вместо прежней матрицы размером n´m, n=692. Это также превосходит по скорости метод наименьших квадратов, применяемый в анализе однородности в качестве альтернативного подхода для вычислений.

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

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

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

Силовая укладка на карте

Уникальной особенностью алгоритма секционирования является то, что наблюдения, принадлежащие одному классу, группируются при вычислении положения правил. Это дает свои вычислительные преимущества, но, что более важно, приводит к более хорошему визуальному представлению разделения наблюдений между классами. Тем не менее разделения по классам по-преж­нему не так точны, как в случае применения случайного леса, лежащего в основе алгоритма. Основной причиной является частичное перекрытие между классами, возникающее в процессе поиска расположения правил, поскольку дисперсионное ограничение (3) не штрафует перекрытия между классами.

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

В то время как целевая функция (2) имеет четкую геометрическую интерпретацию, ограничение (3) – немного менее четкую [1, 2]. Для достижения хорошего разделения между классами дисперсионные ограничения (3) не совсем подходят, поскольку в них нет штрафов для классов, занимающих одинаковое положение в (2).

В большинстве задач отрисовки графа широкое распространение получили так называемые силовые алгоритмы укладки. Они просты в реализации и понятны, поскольку могут рассматриваться как моделирование некоторой физической системы (см., например, [3–5] и ссылки в них). Основная идея этих алгоритмов в том, чтобы выбрать укладку графа, минимизирующую потенциальную энергию системы, состоящей в основном из сил притяжения (пружины) и отталкивания (электромагнитное взаимодействие). В случае с методом секционирования аналогия очевидна: целевая функция (2) может рассматриваться как потенциальная энергия пружин, соединяющих правила и наблюдения в двудольном графе. В модели (2) с ограничениями (3) и (4) нет сил отталкивания, поэтому предлагается заменить слегка искусственное ограничение (3) на ограничение, моделирующее силы отталкивания между классами. В таком случае потенциальная энергия между позициями  и  классов k и k¢ (k¹k¢) пропорциональна .

Таким образом, дисперсионное ограничение (3) заменяется ограничением следующего вида:

.                                       (8)

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

Таким образом, задачу (2) с ограничениями (8) можно записать в форме Лагранжа:

.

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

(9)

Ограничение (4) может быть применено после решения (9). Приведенную задачу оптимизации можно решить методом наименьших квадратов. Сначала фиксируются позиции правил R и проводится оптимизация относительно  затем фиксируются найденные значения  позиций классов и проводится оптимизация относительно R. Последняя задача тривиальна, так как R сразу же определяется формулой . Задача оптимизации по  при фиксированной R несколько сложнее, так как целевая функция в (9) не является выпуклой. Однако, поскольку значительно сокращена размерность задачи (в итоге получена K´q-мерная задача оптимизации), для ее решения вполне подойдут такие простые и хорошо изученные алгоритмы численной оптимизации, как метод наискорейшего спуска и ему подобные.

Сходимость авторского метода определяется следующим условием: считаем, что алгоритм сходится на итерации lÎ тогда и только тогда, когда евклидово расстояние между позициями  на итерациях l и l+1 менее заданной величины погрешности, определенной на уровне 10-6. Сходимость алгоритма достигается весьма быстро, поскольку, как уже отмечалось ранее, оптимизация проводится на матрице размерности K´q, где K – количество выделяемых классов, а q – размерность пространства для отображения; обычно оптимизация производится на матрице размером K´2. В последнем случае имеет смысл применять обычные градиентные методы. Начинаем с решения задачи секционирования (2), далее значения  пересчитываются в направлении градиента, используя шаг в 1/10 квадратного корня среднего расстояния между центрами классов в выражении (2), который постепенно сокращается. После каждого пересчета позиций центров классов  необходимо осуществлять пересчет позиций правил R, используя выражение  

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

1.     Обучить исходный метод на обучающей выборке и выделить все m правил/листьев графа в бинарную матрицу-индикатор G. Провести агрегирование матрицы G согласно выражению (1). В результате получим агрегированную матрицу

2.     Вычислить вложения размерности q (размерность пространства, используемого для отображения) для правил R, используя выражение (7).

3.     Выполнять последовательно следующие два шага, пока алгоритм не достигнет сходимости:

–      провести оптимизацию K позиций  центров классов, используя метод градиентного спуска для целевой функции (9), зафиксировав позиции правил R;

–      пересчитать позиции правил в соответствии с выражением

4.     Центрировать позиции наблюдений при помощи выражения  и снова пересчитать позиции правил

5.     Вычислить позиции всех наблюдений U при помощи выражения U=diag(GGT)-1GR.

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

Литература

1.     Michailidis G. and De Leeuw J., The Gifi System of escriptive Multivariate Analysis, Statistical Sc., 1998, no. 13 (4), pp. 307–336.

2.     De Leeuw J., Beyond Homogeneity Analysis, Technical Report, UCLA, 2009.

3.     Fruchterman T. and Reingold E., Graph Drawing by Force-Directed Placement, Software–Practice and Experience, 1991, no. 21, pp. 1129–1164.

4.     Di Battista G., Eades P., Tamassia R., and Tollis I., Graph Drawing: Algorithms for the Visualization of Graphs, Upper Saddle River, NJ, Prentice Hall, 1998.

5.     Kamada T. and Kawai S., An Algorithm for Drawing General Undirected Graphs, Information Processing Letters, 1989, no. 31, pp. 7–15.

References

1.     Michailidis G., De Leeuw J., Statistical Science, 1998, no. 13 (4), pp. 307–336.

2.     De Leeuw J., Beyond Homogeneity Analysis, Technical Report, UCLA, 2009.

3.     Fruchterman T., Reingold E., Software–Practice and Experience, 1991, no. 21, pp. 1129–1164.

4.     Di Battista G., Eades P., Tamassia R., Tollis I., Graph Drawing: Algorithms for the Visualization of Graphs, Upper Saddle River, NJ, Prentice Hall, 1998.

5.     Kamada, T., Kawai S., Information Processing Letters, 1989, no. 31, pp. 7–15.