Построение графа связности в алгоритме кластеризации сложных объектов - Статья

МІЖНАРОДНИЙ НАУКОВО-ТЕХНІЧНИЙ ЖУРНАЛ “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”В статье представлена модификация алгоритма Хамелеон. Алгоритм Хамелеон состоит из следующих этапов: построение графа, огрубление, разделение и восстановление. На каждом из этапов могут быть использованы различные подходы и алгоритмы. Рассмотрено 2 вида графов: симметричный k-nn граф и ассиметричный k-nn граф. Ключевые слова: кластеризация, алгоритм Хамелеон, построение графа, связность, k-ближайших соседей.Для улучшения разделения графа применяются следующие алгоритмы: Kernighan-Lin (KL), Boundary KL, Fiduccia-Mattheyses (FM), BOUNDARYFM. · Симметричный граф k ближайших соседей (symmetric k-nearest neighbor graph(k-nn)): две вершины x, y соединены, если x находится среди k ближайших соседей y и наоборот. · Ассиметричный граф k ближайших соседей (mutual k-nearest neighbor graph): две вершины x, y соединены, если x находится среди k ближайших соседей y или наоборот [2]. В данной работе рассмотрено 2 вида графов: симметричный k-nn граф и ассиметричный k-nn граф. Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины.

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

В последнее время ведутся активные разработки новых алгоритмов кластеризации, способных обрабатывать сверхбольшие базы данных. В них основное внимание уделяется масштабируемости. Разработаны алгоритмы, в которых методы иерархической кластеризации интегрированы с другими методами. К наиболее актуальным алгоритмам относятся: BIRCH, CURE, CHAMELEON, ROCK [1]. Главной целью работы является исследование и улучшение этапа построения графа посредством оптимизации алгоритма выбора k при построении графа k ближайших соседей.

1. Модифицированный алгоритм Хамелеон

Хамелеон - это новый иерархический алгоритм, который преодолевает ограничения существующих алгоритмов кластеризации. Данный алгоритм рассматривает динамическое моделирование в иерархической кластеризации. В нем можно выделить следующие стадии: 1. Построение графа. Граф может быть построен симметричный или ассиметричный. Различные виды расстояний могут быть применены при построении графа: Euclidian, Manhattan, Minkowski, SQUEUCLIDIAN.

2. Огрубление графа (Coarsening). Огрубление графа может быть выполнено следующими методами: Random Matching(RM), Heavy Edge Matching(HEM), Light Edge Matching(LEM).

3. Начальное разделение графа (Initial Partitioning). Существует несколько подходов к разделению графов: графические методы, комбинаторные методы и спектральные методы. Также алгоритмы могут быть выполнены в рамках рекурсивной бисекции, так как большинство методов выполняет деление графа пополам.

4. Восстановление графа (Uncoarsening) и усовершенствование разделения графа (Refinement). Для улучшения разделения графа применяются следующие алгоритмы: Kernighan-Lin (KL), Boundary KL, Fiduccia-Mattheyses (FM), BOUNDARYFM. Эти же алгоритмы могут быть применены на этапе разделения, взяв за начальное случайное разделение огрубленного графа.

5. Объединение схожих классов для получения финального разбиения.

Целью построения графа является соединение точек локальных соседей. Точки соединяются в зависимости от типа графа.

· Граф эпсилен-окрестности (Epsilon-neighborhood graph). Две вершины графа соединены, если расстояние между рассматриваемыми объектами меньше эпсилен. Данный граф может быть взвешенным и не взвешенным. В случае взвешенного графа вес ребра равняется значению схожести соседних точек (не расстоянию). Параметр данного графа - эпсилен - устанавливается пользователем.

· Полностью связный граф (completely connected graph). Граф может быть получен из графа эпсилен-окрестности установкой эпсилен в максимальное значение.

83

ISSN 1999-9941, “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”, 2014, № 1

· Симметричный граф k ближайших соседей (symmetric k-nearest neighbor graph(k-nn)): две вершины x, y соединены, если x находится среди k ближайших соседей y и наоборот.

· Ассиметричный граф k ближайших соседей (mutual k-nearest neighbor graph): две вершины x, y соединены, если x находится среди k ближайших соседей y или наоборот [2].

2. Введение в k-nn граф

Задача графа k ближайших соседей определена следующим образом: дано множество точек Р из n точек в Rd и положительное целое число k? n-1, рассчитать k ближайших соседей для каждой точки Р.

Более формально задача может быть представлена следующим образом: пусть Р={р1,р2,…рп} множество точек в пространстве R где d?3. Для каждой вершины рі є Р пусть N i k точек из P ближайших к рі. Граф k ближайших соседей (k-nearest neighbor graph (k-NNG)) - это граф где множество вершин {р1,р2,…pn} и множество ребер Е= {(рі, pj): pi є N i или pj є N i} [3]. Следует отметить, что это ассиметричный граф k ближайших соседей, так как отношения близости ассиметричны. Pi может быть среди ближайших соседей pj, но pj нет. В симметричном графе рі и pj будут соединены ребром только в том случае, если каждая из них находится среди k ближайших соседей другой вершины. d k k k

В данной работе рассмотрено 2 вида графов: симметричный k-nn граф и ассиметричный k-nn граф. При построении графа для каждой пары объектов измеряется «расстояние» между ними — степень похожести. В данном случае, чем больше сходство меду двумя объектами - тем тяжелее будет ребро между ними.

Еще одним важным параметром при построении графа является k - количество соседей, с которыми будет связанна каждая из вершин. Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины. При решении поставленной задачи для построения графа k должно быть выбрано таким образом, чтобы соблюдалось условие связности построенного графа. Но слишком большое значение k очень сильно увеличивает вычислительную дороговизну метода и время выполнения не только этапа построения графа, а и всех последующих этапов. Самым простым подходом для выбора k является (2.1), но и данный метод имеет вышеперечисленные недостатки. k = n

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

Поиск в ширину. Вначале все вершины помечаются как новые. Первой посещается вершина a, она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины x. Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину x с новой вершиной y, то вершина y посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной, и становится закрытой. Если на данном этапе остались незакрытые вершины - то граф несвязный.

Поиск в глубину. Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Основной алгоритм тот же, что и в случае поиска в ширину, только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.

Общая оценка трудоемкости для алгоритмов одинаковая - O(m n) .

3. Оптимизация выбора k для построения k-nn графа

Для оптимизации выбора начального параметра k при построении k-nn графа необходимо построить математическую модель зависимости k от характеристик обрабатываемой выборки. Построение математической модели выполнялось на наборе экспериментальных выборок. Набор выборок состоит из 132 выборок, среди них 33 уникальных выборки и 3 вариаций каждой из них полученной путем добавления 20%, 40% и 60% шума. Эксперимент так же проводился на наборах экспериментальных и реальных выборок полученных с ресурсов обмена наборами данных.

Целью данных экспериментов был выбор управляемых параметров данной модели зависимости, способных отобразить необходимые характеристики выборки данных. В рамках работы было проведено 3 эксперимента для выбора управляемых параметров.

· В первом эксперименте анализировались такие характеристики как: количество объектов в выборке, минимальные и максимальные значения математического ожидания, дисперсии и разброса. Зависимости между данными параметрами и значением k не выявлено.

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

84

МІЖНАРОДНИЙ НАУКОВО-ТЕХНІЧНИЙ ЖУРНАЛ “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”

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

· В третьем эксперименте в качестве характеристики использовались количество компонентов связности, максимальное расстояние между компонентами связности и количество элементов в компоненте связности.

В результате исследования была построена математическая модель для оптимизации выбора начального значения k при построении ассиметричного k-nn графа. Модель для ассиметричного k-nn графа имеет следующий вид и представлена на (рис. 1): k = a b? x1 c? x2 d ? x1 e? x2 f ? x1 ? x2 g ? x1 h? x2 i? x1 ? x2 j? x1 ? x2 , 2 2 3 3 2 2 где x1- коэффициент расстояния; x2 - количество компонент связности. Значения коэффициентов представлены в табл. 1.

Таблица 1 - Значения коэффициентов модели для определения k в k-nn графе.

? 4,963024 f b 2,33E-02 g c 0,42939 h d -4,45E-05 i e -3,86E-03 j

4,18E-04 1,05E-08 1,14E-05 1,19E-05

-4,73E-07

Рисунок 1 - Графическое представление описания данных математической моделью

О качестве построенной модели можно судить, исходя из следующих характеристик: стандартная ошибка оценки равна 11,2986020522291, коэффициент множественной детерминации равен 0,6452864929, статистика Дублина-Ватсона составляет 1,24157318003058. Остатки при построении данной модели представлены на рис. 3.2.

Оценки и статистики качества данной модели не являются остаточными показателями эффективности применения полученной модели, так как модель является лишь одним из этапов выбора k. Применение подхода исследовалось на 285 выборках. Применение данной модели улучшили время выполнения этапа построения графа в 62,45% случаев. В 37,55% случаев время выполнения ухудшилось.

Время выполнения ухудшилось лишь в тех случаях, когда k было меньше или равно 3 и время выполнения мало, следовательно, ухудшение временного показателя несущественно сказывается на производительности метода в целом. Отрицательный результат применения модели получен в 7,71% случаев. В среднем время выполнения улучшилось на 161%. Отрицательным результат считается при получении k существенно большем минимально необходимого для соблюдения условия связности, даже если время построения графа уменьшилось.

85

ISSN 1999-9941, “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”, 2014, № 1

3

3

3

4

5

5

5

6

8

9

12

12

19

42

trialok 2 - Графическое представление остатков

Сравнение времени выполнения до и после применения модели в зависимости от количества элементов в обрабатываемой выборки представлено на рис 3, и в зависимости от полученного значения k представлено на рис. 4.

40000

30000

Run time

20000

Old time

New time

10000

0 k

Рисунок 3 - Зависимость времени построения ассиметричного графа в зависимости от количества элементов выборки для модифицированного и не модифицированного вариантов алгоритма

Рисунок 4 - Зависимость времени построения ассиметричного графа в зависимости от полученного значения k для модифицированного и не модифицированного вариантов алгоритма

Так же в результате исследования была построена математическая модель для оптимизации выбора начального значения k при построении симметричного k-nn графа. Модель для ассиметричного k-nn графа имеет следующий вид и представлена на (рис. 5): k = a b? x1 c? x1 d ? x1 e?x2 f ?x2 g ? x2 h ?x2 i? x2 , 2 3 2 3 4 5 где x1- коэффициент расстояния; x2 - количество компонентов связности. Значения коэффициентов представлены в табл. 2.

86

МІЖНАРОДНИЙ НАУКОВО-ТЕХНІЧНИЙ ЖУРНАЛ “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”

Рисунок 5 - Графическое представление описания данных математической моделью

Таблица 2 - Значения коэффициентов модели для определения k в k-nn графе.

? -0,547360564 b -7,46E-14 c 1,51E-29 d -6,56E-48 e 2,323285358 f -3,09E-02 g 1,55E-04 h -3,34E-07 i 2,61E-10

О качестве построенной модели можно судить, исходя из следующих характеристик: стандартная ошибка оценки равна 42,8805641130193, коэффициент множественной детерминации равен 0,15118817, статистика Дублина-Ватсона составляет 1,26055939255469. Остатки при построении данной модели представлены на рис. 6.

Рисунок 3.6 - Графическое представление остатков

Применение данной модели улучшило время выполнения этапа построения графа в 69,23% случаев. В 20,51% случаев время выполнения ухудшилось. Отрицательный результат применения модели получен в 5,12% случаев. В среднем время выполнения улучшилось на 169%.

Сравнение времени выполнения до и после применения модели в зависимости от количества элементов в обрабатываемой выборки представлено на рис 7, и в зависимости от полученного значения k представлено на рис. 8.

Использование модели особенно критично для больших выборок. Полученные результаты будут использованы для дальнейших исследований и модификаций алгоритма Хамелеон.

87

ISSN 1999-9941, “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”, 2014, № 1

3

5

7

10

12

13

18

31

68

8

4

534

782

950

1125

1286

1552

1913

2313

2928

21184

9

18

28

36

74

100

200

722

1000

1294

6520

12182

Run time

70000 20000

65000 trial

55000

15000

50000

45000

40000

Run time

Run time

35000 Old time 10000

New time 30000

25000

20000 5000 15000

10000

5000

0 0

Old time

New time

Entry number

Рисунок 7 - Зависимость времени построения симметричного графа в зависимости от количества элементов выборки для модифицированного и не модифицированного вариантов алгоритма k

Рисунок 8 - Зависимость времени построения симметричного графа в зависимости от полученного значения k для модифицированного и не модифицированного вариантов алгоритма

4. Математическая модель выбора алгоритмов

Управляемые параметры - характеристики выборки (максимальные и минимальные значения математического ожидания, дисперсии, разброса и вычисляемый параметр).

Составляющими целевого параметра являются: - алгоритм построения графа; - мера расстояния;

- алгоритм огрубления графа;

- алгоритм начального разделения графа;

- мера сходства классов;

- алгоритм восстановления графа. На основании имеющихся алгоритмов составлено 14784 комбинаций для анализа.

Математическая модель, полученная на основании этих данных имеет вид:

800000

700000

600000

500000

Worth time 400000 Best time

300000

200000

100000

0

Element number

Рисунок 9 - Зависимость времени построения симметричного графа в зависимости от количества элементов выборки для лучшего и худшего вариантов алгоритма.

88

МІЖНАРОДНИЙ НАУКОВО-ТЕХНІЧНИЙ ЖУРНАЛ “ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА КОМП’ЮТЕРНА ІНЖЕНЕРІЯ”

Y = a*x1 b*x2 c*x3 d*x4 e*x5 f*x6 g*x7 h*x8 i*x9 j, где x1- x9 соответствуют характеристикам выборок, на основании которых построена модель.

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

В данной статье разработана математическая модель для выбора алгоритмов в рамках модифицированного алгоритма Хамелеон, построена математическая модель для выбора k при построении k-nn графа в рамках модифицированного алгоритма Хамелеон, приведены результаты применения разработанных методов на реальных данных.

Была разработана математическая модель для выбора k при построении k-nn графа в рамках модифицированного алгоритма Хамелеон. Приведены результаты, полученные как на экспериментальных, так и на реальных данных.

Результаты работы позволили усовершенствовать этап построения графа путем модификации алгоритма Хамелеон с целью улучшения процессов кластеризации, ориентированных на работу с очень большими базами данных.

1. Чубукова И.А. Data Mining БИНОМ / А.И. Чубукова // Лаборатория знаний. Интернет-университет информационных технологий. - ИНТУИТ.ру. - 2008.

2. Brian Read Advances in Databases : 18th British National Conference on Databases, BNCOD 18 Chilton, UK, July 9 - 11. - 2001.

3. Karypis G. Multilevel k-way Partitioning Scheme for Irregular Graphs / G. Karypis, V. Kumar // Journal of parallel and distributed computing. - 1998. - № 48. - P. 96-129

4. Karypis G. A fast and highly quality multilevel scheme for partitioning irregular graphs / G. Karypis, V. Kumar // SIAM J. Sci. Comput., to appear. [Also available on WWW at URL http://www.cs.umn.edu/_karypis]. - 1995.

5. Karypis G. Multilevel k-way Partitioning Scheme for Irregular Graphs / G. Karypis, V. Kumar // Society of Industrial and Applied mathematics. - 1999.

6. Karypis G. Chameleon: Hierarchical Clustering Using Dynamic Modeling / G. Karypis, E.-H. (Sam) Han, V. Kumar // Computer. - 1999. - Vol. 32, № 8. - P. 68-75.

Статья поступила: 20.02.14. trialмация об авторах

Шатовская Татьяна Борисовна - к.т.н. доцент кафедры Программной инженерии, Харьковский Национальный университет радиоэлектроники.

Каменева Ирина Витальевна - к.т.н. старший преподаватель кафедры Программной инженерии, Харьковский Национальный университет радиоэлектроники.

89