Использование метрической информации является основой решения многих задач распознавания образов, прогнозирования и Data Mining. В частности, на обработке информации такого рода основаны алгоритмы вычисления оценок [21], [22], алгоритмы типа потенциальных функций [1], метод ближайшего соседа [50], метод к ближайших соседей [48], алгоритмы кластеризации [5,7] и многие другие.
В теории распознавания [2, 9, 11−13, 18−23, 34−41], статистическим обоснованием которой служат [25−33], наряду с логическими конструкциями [15−17] разработаны метрические методы, например, [43,44], использующие матрицу расстояний до объектов обучения.
Дискретным аналогом метрики на множестве объектов является отношение соседства [3,4].
Введение
метрики возможно и на самих задачах. В этом случае решается вопрос о получении оценок для так называемых радиусов регулярности и разрешимости, понимаемых как расстояния от данной регулярной (разрешимой) задачи до ближайшей нерегулярной (неразрешимой) [45,46].
Трудности работы с большими метрическими конфигурациями в значительной степени обусловлены квадратичным ростом числа расстояний между объектами с ростом числа объектов. В связи с этим большинство известных алгоритмов анализа метрических конфигураций применимы лишь для конфигураций, насчитывающих до нескольких тысяч объектов.
В то же время, в последние годы растет число практических задач, в которых метрические конфигурации имеют сотни тысяч или миллионы объектов. К таковым, в частности, относятся задачи анализа клиентских сред, где в качестве объектов рассматриваются клиенты некоторой компании (например, крупной розничной сети или сотового оператора), описаниями объектов служат протоколы действий клиентов, и вводятся различные метрики, характеризующие похожесть клиентов в том или ином смысле. Требуется, к примеру, сегментировать множество клиентов, руководствуясь заданной мерой сходства. Или, если задана метрика, отражающая совместную близость клиентов и предоставляемых им услуг, то требуется определить целевую аудиторию для заданной услуги, то есть группу клиентов, которыми эта услуга будет наиболее вероятно востребована.
Для больших метрических конфигураций любой алгоритм, который хотя бы один раз использует каждое расстояние между объектами, становится практически бесполезным. Поэтому поиск субквадратичных (имеющих сложность меньше 0(№) и, следовательно, использующих не все расстояния) алгоритмов решения проблем метрического анализа данных представляется весьма актуальным.
В качестве примера таких проблем можно указать хорошо известную в прикладном анализе данных задачу синтеза плоских представлений метрических конфигураций [6, 8, 12, 14, 47, 49]. Она важна для визуализации и разведочного анализа данных и состоит в следующем. Объектам метрической конфигурации требуется сопоставить точки на координатной плоскости таким образом, чтобы евклидовы расстояния между точками на плоскости в том или ином смысле мало отличались от заданных исходной метрикой расстояний между соответствующими объектами.
Эта задача, вообще говоря, имеет более чем квадратичную сложность, однако при дополнительном допущении о том, что объекты конфигурации могут быть расположены на евклидовой плоскости без искажения расстояний, имеется очевидное решение линейной сложности: в этом случае для точного размещения каждого объекта достаточно использовать лишь расстояния от него до трех других объектов.
Многомерное шкалирование часто используют как средство разведочного анализа данных для наглядного представления метрической конфигурации на плоском точечном графике. Такое представление, несмотря на возможные искажения, как правило, отражает существенные особенности исходной конфигурации, в частности, ее кластерную структуру, если таковая имеется.
Обычно задачу многомерного шкалирования решают путём минимизации функционала стресса ([14]). и где суммирование ведется по всем парам точек (i, j), для которых заданы исходные расстояния р0, wu = р" — веса объектов, dfj =YH=(xik ~xjk)2 — евклидовы расстояния между м и 7-м объектами, х1к— искомые координаты z-й точки, представляющей /-й объект в евклидовом пространстве. Показатель степени, а позволяет ориентировать процесс размещения точек на более точное отражение далеких (при а>-2) или близких (при а<-2) расстояний. Принято считать, что наиболее адекватный результат достигается при, а = -2. В этом случае функционал стресса приобретает смысл потенциальной энергии в системе точек, связанных упругими связями, и задача минимизации имеет физический смысл поиска устойчивого равновесия.
Требование субквадратичности для алгоритмов метрического анализа данных означает, в частности, невозможность использования всех заданных расстояний между объектами. В то же время, имеется возможность выбирать те пары объектов, расстояния между которыми используются.
Поскольку значения метрики на различных парах объектов связаны неравенством треугольника, и задание части расстояний может накладывать различные ограничения на значения остальных расстояний, то предпочтительно, чтобы немногочисленные используемые расстояния оставляли по возможности меньшую неопределенность значений неиспользуемых расстояний, другими словами, чтобы отказ от использования значительной части расстояний приводил к малым потерям информации. Таким образом, возникает задача оптимального выбора используемых расстояний.
С решением задачи многомерного шкалирования (минимизации функционала стресса) связаны две проблемы. Во-первых, ни один из известных эффективных методов многомерного шкалирования не гарантирует достижения глобального минимума стресса. Предложенный в [12] описанный ниже алгоритм W не является исключением. В то же время, он ориентирован на поиск такого локального минимума, при котором сохраняются наиболее существенные структурные особенности исходной метрической конфигурации. Для разведочного анализа данных эта стратегия представляет даже больший интерес, чем борьба за глобальную минимизацию стресса. Во-вторых, большинство известных алгоритмов имеют квадратичную по числу объектов сложность, позволяя размещать до нескольких тысяч объектов за приемлемое время. Однако они практически бесполезны для сверхбольших конфигураций, насчитывающих сотни тысяч объектов ([49]). В [12] рассматриваются алгоритмы синтеза плоских представлений метрических конфигураций, имеющие субквадратичную сложность. Требование субквадратичности означает, в частности, что алгоритм уже «не имеет права» просматривать все попарные расстояния между объектами и должен обладать стратегией эффективного выбора используемых пар. Построение такой стратегии оказывается возможным за счет существенной эксплуатации важного свойства метрики — неравенства треугольника. Суть стратегии в том, что построение «проекции» сопровождается выявлением иерархической кластерной структуры метрической конфигурации. Заодно это решает проблему эффективной графической визуализации: вместо всего множества точек отображается только кластерная структура заданной глубины, и такая визуализация становится возможна еще до завершения размещения всех точек.
В алгоритме W использована та же, что и в [47], идея разделения всего множества объектов метрической конфигурации на «скелетные» и «массовые». Скелетные объекты как отдельная, существенно меньшая часть метрической конфигурации размещаются на плоскости с помощью трудоемкого, но обеспечивающего достаточное точное приближение к минимальному значению функционала стресса, алгоритма. Массовые же объекты затем размещаются более быстрым алгоритмом независимо друг от друга на основе информации об их удаленности лишь от «скелетных» объектов. Выигрыш в скорости такого комбинированного алгоритма достигается за счет того, что в качестве скелетных берется лишь малая часть всех объектов метрической конфигурации.
Первая попытка оптимизации выбора скелетных объектов была предпринята в работе [12], где в качестве алгоритма для выбора «скелетных» объектов использован быстрый алгоритм V, выделяющий е-кластерную структуру. Как показано в [5], этот алгоритм обладает свойством «представительного покрытия», то есть сначала выбирает по одному «скелетному» объекту (представителю) в каждом е-кластере, и лишь потом начинаются повторения.
Целью данного исследования, с одной стороны, является описание достаточно широких и содержательных классов задач метрического анализа (в частности, задач кластеризации и задач синтеза представлений), допускающих решение с помощью субквадратичных алгоритмов, с другой стороны — разработка и обоснование методов синтеза таких алгоритмов.
СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ.
В главе 1 вводится понятие иерархической s-кластерной структуры, исследуются свойства таких структур. Показывается, что во всякой метрической конфигурации для каждого е< 1 существует единственная е-кластерная структура. Исследуется задача выделения в метрической конфигурации е-кластерной структуры при заданном е. Показывается, что эта задача имеет квадратичную сложность. В то же время указывается широкий класс метрических конфигураций, для которого сложность удается понизить. Описывается алгоритм V, восстанавливающий иерархическую sкластерную структуру, и имеющий для задач из этого класса сложность 0(N-nN). Указывается способ эффективного распараллеливания алгоритма V. Показывается, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала выбирается по одному объекту в каждом екластере, и лишь потом начинаются повторения ([5]).
В главе 2 вводятся понятия частично определенной метрики и локализации метрики, изучаются их свойства. Исследуется, к каким потерям информации (неопределенностям) приводит отказ от использования части расстояний. Приводится ряд точных оценок. В частности, показывается, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [а, Ь] или (0,6], границы а, Ъ которого имеют простое выражение через известные значения локализации. Вводится понятие неопределенности значения частично определенной метрики на паре объектов. Обосновывается процедура, вычисляющая эту неопределенность. Доказывается верхняя и нижняя оценки неопределенности ([6]).
В главе 3 исследуются быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Описывается субквадратичный алгоритм W, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической екластерной структуры ([12]).
Указывается способ распараллеливания алгоритма W. При помощи техники частично определенных метрик, описанной в главе 2, показывается, что для метрических конфигураций, имеющих достаточно выраженную екластерную структуру (е<2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению со всеми алгоритмами, не обладающими этим свойством ([6]). Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций.
1? -КЛАСТЕРНЫЕ СТРУКТУРЫ 1.1 Определения.
Для удобства ссылок приведем здесь аксиомы метрики. Функция p: S2->R+ называется метрикой ([24]), если удовлетворяет следующим трем аксиомам:
Аксиома 1. Для всех а, Ъ е S выполнено [p (atb) = 0 а = b ]. Аксиома 2. Для всех a, be S выполнено р{а, Ь) = р (Ъ, а). Аксиома 3. Для всех а, Ь, с е S выполнено р (а, Ъ) < р (а, с) + р (с, Ъ). Метрической конфигурацией (S, р) будем называть набор S из N объектов с введенной на них метрикой р, вообще говоря, неевклидовой. Будем рассматривать системы К = {АГ,., л: Ск} подмножеств множества.
S. Введем следующие обозначения:
D (Kt) = max p{sk, sl) —диаметр подмножестваsk, SieK, max (К) = шах D (K,) — максимальный диаметр системы подмножеств;
IS/SCK p (a, K) = mmp (a, s) — расстояние от объекта aeS до подмножества seK.
К cSр (К, М)= min p (s, t)—расстояние между двумя подмножествами;
Zmin (K)= min {KifKj) — минимальное расстояние между подмножествами системы К.
Разбиением на е-кластеры (при ?>0) метрической конфигурации (S, p) будем называть такой набор К = {К1,., КСк} непустых непересекающихся подмножеств К-и что выполнены следующие условия: seKjeM.
U.U/:Ck =s.
DmiX (K)fLmia (K).
1) (2) и при этом число подмножеств Ск минимально по всем наборам подмножеств, удовлетворяющим условиям (1) и (2).
Обозначим С (е) минимальное по всем наборам подмножеств К, удовлетворяющим условиям (1) и (2), значение Ск.
Подмножества Кх,., Кс{е), составляющие разбиение К метрической конфигурации на екластеры, будем называть £-кластерами.
Отметим, что из условия минимальности Ск следует, что число е-кластеров во всех разбиениях заданной метрической конфигурации на екластеры одинаково.
Ниже в теореме 2 показано, что при е < 1 существует единственное разбиение заданной метрической конфигурации (S, p) на екластеры. Обозначим это разбиение K*(S, p). Тогда однозначно определены следующие величины: L*mia (S, p) = Lmia (K*(S, p)) и D*max (S, p) = Dmax (K*(S,/>)).
Метрическая конфигурация, число екластеров которой С (е) равно числу объектов N, называется е-неделимой, в противном случае — е-делимой.
Для метрической конфигурации (S,/?) ее £-кластеры будем также называть екластерами первого уровня.
Каждый из sкластеров первого уровня (которые также являются метрическими конфигурациями с той же метрикой р) либо е-неделим, либо, в свою очередь имеет г—кластерную структуру, и тогда делится на s-кластеры второго уровня и т. д. Так как по определению все кластерынепустые непересекающиеся множества, то число уровней в этом процессе деления конечно. Назовем его числом уровней иерархической е-кластерной структуры.
Каждой иерархической екластерной структуре соответствует дерево е-кластеров, вершинам которого соответствуют всевозможные £-кластеры различных уровней из этой иерархической? -кластерной структуры. Корневой вершине дерева соответствует вся заданная метрическая конфигурация. Из вершины, соответствующей некоторому? -кластеру К, выходят ребра в те и только те вершины, которые соответствуют? -кластерам следующего уровня, на которые делится К. а е.
Рис. 1 Пример? -кластерной структуры.
Пример Пусть задана метрическая конфигурация, состоящая из 6 объектов — точек на плоскости (рис.1). При ?- = ½? -кластерами первого уровня будут {a}, {b, c, d} и {e, f}. При этом, Dmax = p (b, d), Lmm =p (d, c). £-кластерами второго уровня будут {Ь}, {с}, {d}, {.
ЗАКЛЮЧЕНИЕ
.
В данной работе описаны некоторые классы задач метрического анализа (задач кластеризации и задач синтеза плоских представлений), допускающие решение с помощью субквадратичных алгоритмов, а также предложен и обоснован ряд таких алгоритмов.
В частности, введено понятие иерархической е-кластерной структуры, исследованы свойства таких структур. Показано, что во всякой метрической конфигурации для каждого ?-<1 существует единственная е-кластерная структура. Исследована задача выделения в метрической конфигурации екластерной структуры при заданном s. Показано, что эта задача имеет квадратичную сложность. В то же время указан широкий класс метрических конфигураций, для которого сложность удается понизить. Предложен алгоритм V, восстанавливающий иерархическую екластерную структуру, и имеющий для задач из этого класса сложность O (N-lnN). Указан способ эффективного распараллеливания алгоритма V. Показано, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала он выбирает по одному объекту в каждом екластере, и лишь потом начинаются повторения.
Введены понятия частично определенной метрики, локализации метрики и неопределенности значения частично определенной метрики на паре объектов, изучены их свойства. Исследовано, к каким потерям информации приводит отказ от использования части расстояний. Приведен ряд точных оценок. В том числе, показано, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [а, Ь] или (0,6], границы а, Ъ которого имеют простое выражение через известные значения локализации. Введено понятие неопределенности значения частично определенной метрики на паре объектов. Обоснована процедура, вычисляющая эту неопределенность. Получены верхняя и нижняя оценки неопределенности.
Исследованы быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Предложен субквадратичный алгоритм tv, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической е-кластерной структуры. Указан способ распараллеливания алгоритма W. При помощи предложенной техники частично определенных метрик показано, что для метрических конфигураций, имеющих достаточно выраженную sкластерную структуру (е <2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению с алгоритмами, не обладающими этим свойством. Таким образом, решена задача оптимального выбора используемых расстояний.
Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Показано, что описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций.
Выполнена программная реализация предложенных алгоритмов. Полученные теоретические выводы подтверждены серией экспериментов на модельных и реальных данных.
