Содержание к диссертации
Введение
1 Кластерные структуры 12
1.1 Определения 12
1.2 Свойства є -кластерных структур 15
1.3 Описание алгоритма V для выделения кластерной структуры 21
1.4 Параллельная реализация алгоритма V 22
1.5 Обоснование алгоритма V 24
1.6 Анализ сложности алгоритма V 29
2 Частично определенные метрики 33
2.1 Определения 34
2.2 Свойства частично определенных метрик 35
2.3 О множествах допустимых значений локализации 40
3 Синтез плоских представлений метрических конфигураций 46
3.1 Описание алгоритма W для синтеза плоского представления на основе выделения множества скелетных объектов 46
3.2 Сложность алгоритма W
3.3 Иерархический вариант алгоритма W 48
3.4 Параллельная реализация алгоритма W 48
3.5 Обоснование алгоритма W 49
Заключение 54
Список литературы 57
- Описание алгоритма V для выделения кластерной структуры
- Анализ сложности алгоритма V
- О множествах допустимых значений локализации
- Описание алгоритма W для синтеза плоского представления на основе выделения множества скелетных объектов
Введение к работе
Использование метрической информации является основой решения многих задач распознавания образов, прогнозирования и Data Mining. В частности, на обработке информации такого рода основаны алгоритмы вычисления оценок [21], [22], алгоритмы типа потенциальных функций [1], метод ближайшего соседа [50], метод k ближайших соседей [48], алгоритмы кластеризации [5,7] и многие другие. В теории распознавания [2, 9, 11-13, 18-23, 34-41], статистическим обоснованием которой служат [25-33], наряду с логическими конструкциями [15-17] разработаны метрические методы, например, [43,44], использующие матрицу расстояний до объектов обучения.
Дискретным аналогом метрики на множестве объектов является отношение соседства [3,4].
Введение метрики возможно и на самих задачах. В этом случае решается вопрос о получении оценок для так называемых радиусов регулярности и разрешимости, понимаемых как расстояния от данной регулярной (разрешимой) задачи до ближайшей нерегулярной (неразрешимой) [45,46].
Трудности работы с большими метрическими конфигурациями в значительной степени обусловлены квадратичным ростом числа расстояний между объектами с ростом числа объектов. В связи с этим большинство известных алгоритмов анализа метрических конфигураций применимы лишь для конфигураций, насчитывающих до нескольких тысяч объектов.
В то же время, в последние годы растет число практических задач, в которых метрические конфигурации имеют сотни тысяч или миллионы объектов. К таковым, в частности, относятся задачи анализа клиентских сред, где в качестве объектов рассматриваются клиенты некоторой компании (например, крупной розничной сети или сотового оператора), описаниями объектов служат протоколы действий клиентов, и вводятся различные метрики, характеризующие похожесть клиентов в том или ином смысле. Требуется, к примеру, сегментировать множество клиентов, руководствуясь заданной мерой сходства. Или, если задана метрика, отражающая совместную близость клиентов и предоставляемых им услуг, то требуется определить целевую аудиторию для заданной услуги, то есть группу клиентов, которыми эта услуга будет наиболее вероятно востребована.
Для больших метрических конфигураций любой алгоритм, который хотя бы один раз использует каждое расстояние между объектами, становится практически бесполезным. Поэтому поиск субквадратичных (имеющих сложность меньше 0(№) и, следовательно, использующих не все расстояния) алгоритмов решения проблем метрического анализа данных представляется весьма актуальным.
В качестве примера таких проблем можно указать хорошо известную в прикладном анализе данных задачу синтеза плоских представлений метрических конфигураций [6, S, 12, 14, 47, 49]. Она важна для визуализации и разведочного анализа данных и состоит в следующем. Объектам метрической конфигурации требуется сопоставить точки на координатной плоскости таким образом, чтобы евклидовы расстояния между точками на плоскости в том или ином смысле мало отличались от заданных исходной метрикой расстояний между соответствующими объектами.
Эта задача, вообще говоря, имеет более чем квадратичную сложность, однако при дополнительном допущении о том, что объекты конфигурации могут быть расположены на евклидовой плоскости без искажения расстояний, имеется очевидное решение линейной сложности: в этом случае для точного размещения каждого объекта достаточно использовать лишь расстояния от него до трех других объектов.
Многомерное шкалирование часто используют как средство разведочного анализа данных для наглядного представления метрической конфигурации на плоском точечном графике. Такое представление, несмотря на возможные искажения, как правило, отражает существенные особенности исходной конфигурации, в частности, ее кластерную структуру, если таковая имеется.
Обычно задачу многомерного шкалирования решают путём минимизации функционала стресса ([14]) и где суммирование ведется по всем парам точек (i,j), для которых заданы исходные расстояния p(J, wj]=p"J — веса объектов, dfj =2 ( - )2 — евклидовы расстояния между г -м и j-u объектами, х1к— искомые координаты 1-й точки, представляющей г -й объект в евклидовом пространстве. Показатель степени а позволяет ориентировать процесс размещения точек на более точное отражение далеких (при а -2) или близких (при а -2) расстояний. Принято считать, что наиболее адекватный результат достигается при а = -2. В этом случае функционал стресса приобретает смысл потенциальной энергии в системе точек,
связанных упругими связями, и задача минимизации имеет физический смысл поиска устойчивого равновесия.
Требование субквадратичности для алгоритмов метрического анализа данных означает, в частности, невозможность использования всех заданных расстояний между объектами. В то же время, имеется возможность выбирать те пары объектов, расстояния между которыми используются.
Поскольку значения метрики на различных парах объектов связаны неравенством треугольника, и задание части расстояний может накладывать различные ограничения на значения остальных расстояний, то предпочтительно, чтобы немногочисленные используемые расстояния оставляли по возможности меньшую неопределенность значений неиспользуемых расстояний, другими словами, чтобы отказ от использования значительной части расстояний приводил к малым потерям информации. Таким образом, возникает задача оптимального выбора используемых расстояний.
С решением задачи многомерного шкалирования (минимизации функционала стресса) связаны две проблемы. Во-первых, ни один из известных эффективных методов многомерного шкалирования не гарантирует достижения глобального минимума стресса. Предложенный в [12] описанный ниже алгоритм W не является исключением. В то же время, он ориентирован на поиск такого локального минимума, при котором сохраняются наиболее существенные структурные особенности исходной метрической конфигурации. Для разведочного анализа данных эта стратегия представляет даже больший интерес, чем борьба за глобальную минимизацию стресса. Во-вторых, большинство известных алгоритмов имеют квадратичную по числу объектов сложность, позволяя размещать до нескольких тысяч объектов за приемлемое время. Однако они практически бесполезны для сверхбольших конфигураций, насчитывающих сотни тысяч объектов ([49]). В [12] рассматриваются алгоритмы синтеза плоских представлений метрических конфигураций, имеющие субквадратичную сложность. Требование субквадратичности означает, в частности, что алгоритм уже «не имеет права» просматривать все попарные расстояния между объектами и должен обладать стратегией эффективного выбора используемых пар. Построение такой стратегии оказывается возможным за счет существенной эксплуатации важного свойства метрики — неравенства треугольника. Суть стратегии в том, что построение «проекции» сопровождается выявлением иерархической кластерной структуры метрической конфигурации. Заодно это решает проблему эффективной графической визуализации: вместо всего множества точек отображается только кластерная структура заданной глубины, и такая визуализация становится возможна еще до завершения размещения всех точек.
В алгоритме W использована та же, что и в [47], идея разделения всего множества объектов метрической конфигурации на «скелетные» и «массовые». Скелетные объекты как отдельная, существенно меньшая часть метрической конфигурации размещаются на плоскости с помощью трудоемкого, но обеспечивающего достаточное точное приближение к минимальному значению функционала стресса, алгоритма. Массовые же объекты затем размещаются более быстрым алгоритмом независимо друг от друга на основе информации об их удаленности лишь от «скелетных» объектов. Выигрыш в скорости такого комбинированного алгоритма достигается за счет того, что в качестве скелетных берется лишь малая часть всех объектов метрической конфигурации.
Первая попытка оптимизации выбора скелетных объектов была предпринята в работе [12], где в качестве алгоритма для выбора «скелетных» объектов использован быстрый алгоритм V, выделяющий е-кластерную структуру. Как показано в [5], этот алгоритм обладает свойством «представительного покрытия», то есть сначала выбирает по одному «скелетному» объекту (представителю) в каждом е-кластере, и лишь потом начинаются повторения.
Целью данного исследования, с одной стороны, является описание достаточно широких и содержательных классов задач метрического анализа (в частности, задач кластеризации и задач синтеза представлений), допускающих решение с помощью субквадратичных алгоритмов, с другой стороны - разработка и обоснование методов синтеза таких алгоритмов.
Описание алгоритма V для выделения кластерной структуры
Исследуется задача выделения в метрической конфигурации є -кластерной структуры при заданном є. Показывается, что эта задача имеет квадратичную сложность. В то же время указывается широкий класс метрических конфигураций, для которого сложность удается понизить. Описывается алгоритм V, восстанавливающий иерархическую є -кластерную структуру, и имеющий для задач из этого класса сложность O(N-lnN). Указывается способ эффективного распараллеливания алгоритма V. Показывается, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала выбирается по одному объекту в каждом є -кластере, и лишь потом начинаются повторения ([5]), В главе 2 вводятся понятия частично определенной метрики и локализации метрики, изучаются их свойства. Исследуется, к каким потерям информации (неопределенностям) приводит отказ от использования части расстояний. Приводится ряд точных оценок. В частности, показывается, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [atb] или (0,6], границы а,Ь которого имеют простое выражение через известные значения локализации. Вводится понятие неопределенности значения частично определенной метрики на паре объектов. Обосновывается процедура, вычисляющая эту неопределенность. Доказывается верхняя и нижняя оценки неопределенности ([6]).
В главе 3 исследуются быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Описывается субквадратичный алгоритм W, совмещающий размещение точек на плоскости на основе широко известного метода Ньютона-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической є -кластерной структуры ([12]).
Указывается способ распараллеливания алгоритма W. При помощи техники частично определенных метрик, описанной в главе 2, показывается, что для метрических конфигураций, имеющих достаточно выраженную є -кластерную структуру (е 2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению со всеми алгоритмами, не обладающими этим свойством ([6]). Алгоритм V, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций. и при этом число подмножеств ск минимально по всем наборам подмножеств, удовлетворяющим условиям (1) и (2). Обозначим С(є) минимальное по всем наборам подмножеств К, удовлетворяющим условиям (1) и (2), значение Ск. Подмножества Кх,...,КС{е), составляющие разбиение К метрической конфигурации на є -кластеры, будем называть є -кластерами. Отметим, что из условия минимальности Ск следует, что ЧИСЛО -кластеров во всех разбиениях заданной метрической конфигурации на -кластеры одинаково. Ниже в теореме 2 показано, что при е \ существует единственное разбиение заданной метрической конфигурации (S,p) на є -кластеры. Обозначим это разбиение Ke(S,p). Тогда однозначно определены следующие величины: Z,;in{S,/7) = Imin(K (S,p)) и Dem3X(S,p) = Dmm(K4S.P)). Метрическая конфигурация, число є -кластеров которой С(є) равно числу объектов N, называется є -неделимой, в противном случае — є-делимой. Для метрической конфигурации (S,p) ее є -кластеры будем также называть є -кластерами первого уровня. Каждый из є -кластеров первого уровня (которые также являются метрическими конфигурациями с той же метрикой р) либо є -неделим, либо, в свою очередь имеет -кластерную структуру, и тогда делится на е-кластеры второго уровня и т.д. Так как по определению все кластеры — непустые непересекающиеся множества, то число уровней в этом процессе деления конечно. Назовем его числом уровней иерархической е-кластерной структуры. Каждой иерархической Е -кластерной структуре соответствует дерево є -кластеров, вершинам которого соответствуют всевозможные є-кластеры различных уровней из этой иерархической є -кластерной структуры. Корневой вершине дерева соответствует вся заданная метрическая конфигурация. Из вершины, соответствующей некоторому є -кластеру К, выходят ребра в те и только те вершины, которые соответствуют є -кластерам следующего уровня, на которые делится К.
Анализ сложности алгоритма V
Момент останова i0 определяется как наименьшее і, при котором выполнено условие останова. Поскольку на каждом шаге в П, добавляется новый объект из SK с S, то процедура v конечна.
После останова процедуры v объекты S,,...,SV1 полагаются центрами «шаров». Остальные объекты приписываются к тому «шару», к центру которого они ближе. Полученные шары объявляются кластерами следующего уровня. К тем из них, что содержат больше одного объекта, снова применяется процедура v.
Предложенный алгоритм V выделяет в S иерархию подмножеств, свойства которой обсуждаются ниже в параграфе 1.5. 1.4 Параллельная реализация алгоритма V
В практических задачах метрические конфигурации, подлежащие исследованию с помощью алгоритмов кластерного анализа нередко достигают размеров, при которых их обработка даже при помощи субквадратичных алгоритмов на персональном компьютере занимает значительное время. Поэтому возможность параллельной реализации этих алгоритмов представляет существенный практический интерес.
Ниже приводится способ достаточно эффективного распараллеливания алгоритма V. Параллельная реализация алгоритма V выполняется в два этапа: начальный и основной. На начальном этапе распараллеливается применение самой процедуры v к отдельному кластеру. Затем, когда количество готовых к обработке кластеров следующих уровней становится не меньше, чем число доступных процессоров, наступает основной этап, при котором в каждый момент времени на каждом процессоре обрабатывается свой кластер. На основном этапе применение процедуры v к различным кластерам осуществляется независимо и в любом порядке, поэтому, как только в результате ее выполнения появляются кластеры очередного уровня, обработка каждого из них становится в очередь задач и выполняется любым освободившимся процессором.
При этом обработке любого кластера /-го уровня назначается приоритет / с тем, чтобы кластеры верхних уровней обрабатывались прежде, чем нижних. Поскольку результаты обработки алгоритмом V верхних уровней кластерной структуры не меняются в процессе дальнейшей обработки нижних уровней, то такая расстановка приоритетов позволяет работать с результатами обработки верхних уровней еще до завершения выполнения алгоритма V.
На начальном этапе выполнения алгоритма V, пока число готовых к обработке кластеров меньше, чем число доступных процессоров параллельное выполнение алгоритма V осуществляется за счет распараллеливания самой процедуры v, применяемой к очередному кластеру. А именно, задача выбора очередного объекта St є S \Cl,_l такого, чтобы p(S,,fiM)-»max разделяется между имеющимися т процессорами следующим образом. Множество исследуемых объектов SK\Q.t_x делится на т частей, и на каждом процессоре определялся максимум значения р лишь на соответствующей части объектов. Затем выбирается максимум из полученных результатов.
Благодаря применению распараллеливания процедуры v на начальном этапе, а также тому, что по мере перехода к обработке кластеров низших уровней время обработки каждого отдельного кластера сокращается, удается обеспечить достаточно равномерную загрузку процессоров. Таким образом, для достаточно больших метрических конфигураций параллельное выполнение алгоритма V на т процессорах обеспечивает асимптотически т -кратное сокращение времени выполнения. 1.5 Обоснование алгоритма V
В теореме 4 будет показано, что при заданном є 1 для метрической конфигурации, удовлетворяющей условию ( ), предложенный алгоритм V корректно восстанавливает иерархическую г-кластерную структуру, которая в этом случае, согласно теореме 2, единственна.
В теореме 5 будет показано, что задача выделения є -кластерной структуры для произвольной конфигурации имеет сложность не меньше, чем 0(N2). Согласно теореме б и следствиям из нее, для «существенно неравномерных» конфигураций предложенный алгоритм V также имеет сложность 0(N2). Однако, если конфигурация «равномерно» делится на кластеры всех уровней, то предложенный алгоритм V имеет сложность O(N-lnN).
В лемме 6 будет показано, что если условие ( ) не выполнено, то алгоритм V выделяет иерархию подмножеств множества объектов, на каждом уровне которой выполнено более слабое, чем (2), условие ПтахПтілїє ,гдеє є/(\-є).
В лемме 7 будет показано, что при Е \/2 каждое выделяемое предложенным алгоритмом V є -подмножество оказывается либо г-кластером, либо объединением нескольких є -кластеров.
Далее считается, что задана метрическая конфигурация (SK,p), є 1, и предложенная процедура v выполнила ее деление на кластеры, построив сеть п. .
О множествах допустимых значений локализации
Рассмотрим алгоритм W ([12]), в котором для минимизации функционала стресса используется итерационный процесс поочередного размещения точек. Размещение производится в три этапа. Выделение и начальное размещение S опорных точек (скелета). Итеративное уточнение скелета, не более / раз. Размещение основной массы точек относительно скелета. На первом этапе при помощи алгоритма V в метрической конфигурации выделяется є -кластерная структура (для заданного є). В процессе работы алгоритма V строится сеть объектов fl/o, содержащая представителей всех выделенных є -кластеров. Объекты, составляющие эту сеть и принимаются в качестве скелетных объектов. Затем строится первое приближение размещения скелетных объектов на плоскости. Сначала первым двум скелетным объектам, расстояние между которыми обозначим R, приписываются координаты (0,0) и (й,0). Затем, по одному добавляются остальные скелетные объекты в порядке убывания попарных расстояний. Их координаты определяются методом Ньютона-Раффсона по трем ближайшим уже размещенным скелетным объектам.
На втором этапе производится несколько «больших» итераций метода Ньютона-Раффсона, в которых поочередно уточняется размещение всех скелетных точек, пока значение стресса не перестанет существенно уменьшаться. Задача второго этапа — как можно точнее выстроить скелет, так как относительно него размещается основная масса точек.
На третьем этапе размещается основная масса точек. Каждая точка размещается методом Ньютона-Раффсона по трем ближайшим скелетным точкам. Очерёдность размещения не имеет значения, поскольку взаимные расстояния между массовыми точками не учитываются. 3.2 Сложность алгоритма W
Описанный порядок размещения точек ориентирован на сохранение наиболее существенных структурных особенностей исходной метрической конфигурации. Сначала выстраивается скелет конфигурации из небольшого количества опорных точек. Таких точек немного, поэтому скелет размещается с незначительными искажениями.
По мере измельчения сетки происходит плавный переход к размещению точек в тех областях, где уже имеется достаточно много локальных соседей. При выборе а 0 именно ближайшие соседи дают основной вклад в функционал стресса. Поэтому начальное приближение по трем ближайшим точкам позволяет практически сразу указать расположение точки, близкое к оптимальному. Это приводит к заметному повышению эффективности, поскольку при удачном начальном расположении требуется существенно меньшее число итераций.
Особенно эффективен данный метод при размещении конфигураций, изначально близких к двумерным евклидовым. Если исходная конфигурация в точности двумерна, она всегда размещается точно, даже при полном отключении уточняющих итераций по методу Ньютона-Рафсона.
На третьем этапе учитываются только расстояния между массовыми точками и точками скелета. Взаимные расстояния между массовыми точками даже не просматриваются, поэтому время размещения конфигурации из N точек имеет порядок 0(S2I) + 0(SN). Оно линейно по N, если размер скелета достаточно мал и фиксирован, и квадратично, если S имеет порядок N. При выборе размера скелета порядка InN, сложность размещения точек алгоритмом W имеет порядок O(NlnN).
Отбрасывание части информации существенно ускоряет работу алгоритма, но несколько ухудшает качество размещения. Однако если скелет отражает наиболее значимые особенности исходной метрической конфигурации (что призвано обеспечить применение алгоритма V), то ухудшение качества размещения будет незначительным.
На основе описанного базового алгоритма W в [12] предложен иерархический алгоритм размещения сверхбольших метрических конфигураций. После построения скелета на основе представителей є -кластеров первого уровня, размещается скелет второго уровня, затем скелет третьего уровня, и т.д. При этом скелет каждого уровня размещается только по точкам скелета предыдущего уровня. Это позволяет достичь субквадратичной эффективности при одновременном построении иерархической кластерной структуры метрической конфигурации.
Алгоритм W, как было описано, выполняется в три этапа. На первом этапе происходит выбор «скелетных» объектов с помощью алгоритма V, на втором этапе выполняется несколько итераций по уточнению положения точек евклидовой плоскости, соответствующих этим объектам относительно друг друга, на третьем этапе происходит размещение основной массы объектов независимо друг от друга. Предлагаются следующие способы распараллеливания каждого этапа.
Эффективная параллельность вычислений на первом этапе обеспечивается за счет распараллеливания алгоритма V (которое описано в гл.2). На втором этапе поиск локального минимума функционала стресса ведется с помощью одного из параллельных вариантов алгоритма Ньютона-Рафсона. Наконец, на третьем этапе оставшиеся объекты делятся между доступными процессорами и размещаются независимо друг от друга. 3.5 Обоснование алгоритма W
Описание алгоритма W для синтеза плоского представления на основе выделения множества скелетных объектов
В данной работе описаны некоторые классы задач метрического анализа (задач кластеризации и задач синтеза плоских представлений), допускающие решение с помощью субквадратичных алгоритмов, а также предложен и обоснован ряд таких алгоритмов.
В частности, введено понятие иерархической є-кластерной структуры, исследованы свойства таких структур. Показано, что во всякой метрической конфигурации для каждого Б \ существует единственная є-кластерная структура. Исследована задача выделения в метрической конфигурации є -кластерной структуры при заданном є. Показано, что эта задача имеет квадратичную сложность. В то же время указан широкий класс метрических конфигураций, для которого сложность удается понизить. Предложен алгоритм V, восстанавливающий иерархическую є-кластерную структуру, и имеющий для задач из этого класса сложность O(N-lnN). Указан способ эффективного распараллеливания алгоритма V. Показано, что алгоритм V обладает свойством «представительного покрытия», состоящим в том, что сначала он выбирает по одному объекту в каждом є -кластере, и лишь потом начинаются повторения.
Введены понятия частично определенной метрики, локализации метрики и неопределенности значения частично определенной метрики на паре объектов, изучены их свойства. Исследовано, к каким потерям информации приводит отказ от использования части расстояний. Приведен ряд точных оценок. В том числе, показано, что множество допустимых значений локализации на паре объектов, на которой она не определена, представляет собой отрезок [а,Ь] или (0,6], границы а,Ъ которого имеют простое выражение через известные значения локализации. Введено понятие неопределенности значения частично определенной метрики на паре объектов. Обоснована процедура, вычисляющая эту неопределенность. Получены верхняя и нижняя оценки неопределенности.
Исследованы быстрые алгоритмы синтеза плоских представлений метрических конфигураций. Предложен субквадратичный алгоритм W, совмещающий размещение точек на плоскости на основе широко известного метода Ньютон а-Рафсона с построением иерархии «скелетных» объектов на основе выделяемой алгоритмом V иерархической є-кластерной структуры. Указан способ распараллеливания алгоритма W. При помощи предложенной техники частично определенных метрик показано, что для метрических конфигураций, имеющих достаточно выраженную є -кластерную структуру (є 2/3), использование для выбора скелетных объектов алгоритма V, обладающего свойством представительного покрытия, является оптимальным по сравнению с алгоритмами, не обладающими этим свойством. Таким образом, решена задача оптимального выбора используемых расстояний.
Алгоритм К, по сравнению с любым другим алгоритмом, не обладающим свойством представительного покрытия, оставляет меньшую неопределенность для расстояний между «массовыми» объектами. Это означает, что любой алгоритм синтеза плоских представлений метрических конфигураций, использующий для выбора «скелетных» объектов алгоритм V, имеет заведомо меньше возможностей для ошибок при последующем «беглом» размещении «массовых» объектов.
Показано, что описанные результаты продолжаются и на иерархические варианты алгоритмов синтеза плоских представлений метрических конфигураций. Выполнена программная реализация предложенных алгоритмов. Полученные теоретические выводы подтверждены серией экспериментов на модельных и реальных данных.
Похожие диссертации на Субквадратичные алгоритмы метрического анализа данных
