Using Genetic Algorithm in Clustering Problem for Weighted Oriented Graph

Full Text

Введение

Кластеризация – это важный процесс абстрагирования, который играет значимую роль как в распознавании образов, так и в поиске данных. Для кластеризации больших массивов информации часто используются условные алгоритмы [1: 24–34]. Алгоритм K-means – это самый популярный условный алгоритм кластеризации, также широко распространены нечеткий, грубый, вероятностный и нейросетевой алгоритмы [2]. Однако основная проблема обозначенных алгоритмов заключается в том, что они могут не достигать глобально оптимального решения соответствующей задачи кластеризации. В данном контексте для преодоления обозначенных трудностей очень привлекательными являются генетические алгоритмы.

Генетические алгоритмы (ГА) – это рандомизированные методы поиска и оптимизации, основанные на принципах эволюции и естественной генетики и обладающие большим количеством неявного параллелизма [3]. ГА выполняют поиск в сложных, больших и многомодальных ландшафтах (например, для оптимизации гиперпараметров, таких как скорость обучения, параметры регуляризации и сетевая архитектура в нейронных сетях, параметры фильтрации для шумоподавления сигналов, сохраняя при этом важную информацию) и предоставляют почти оптимальные решения для целевой функции или функции пригодности задачи оптимизации. Кроме того, ГА снижает чувствительность k-средних к случайно инициализированным центрам и уменьшает вероятность сходимости к локальным минимумам [4].

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

Анализ публикаций по теме исследования. Возможности использования ГА в различных контекстах, в которых либо непрактично, либо невозможно напрямую найти глобально оптимальное решение сложных числовых задач, рассматривают в своих трудах М.С. Германчук, Д.В. Лемтюжникова, В.А. Лукьяненко [5], Т.И. Петров, А.Р. Сафин, М.Ф. Низамиев [6], K.K. Gola, B.M. Singh [7], F. Houshmand-Nanehkaran, S.M. Lajevardi [8].

Над улучшением ГА кластеризации, который способен автоматически находить оптимальное количество кластеров и их разделов на основе числовых критериев трудятся Р.А. Аралбаев, А.А. Тарасов [9], Е.Л. Еремин, Е.А. Шеленок [10], O. Üstün, E. Bekiroğlu [11], Cao Jianli, Chen Zhikui [12], J. Chanu, M. Singh [13].

Экспериментальные результаты сравнения ГА кластеризации с алгоритмом K-means представлены для нескольких наборов искусственных и реальных данных в публикациях А.М. Минитаевой, Р.Д. Векшина, А.А. Шатилова [14], Ф.В. Безгачева, П.В. Галушина, Е.Н. Рудаковой [15], Е.Е. Бизянова, И.С. Козловой [16], Baodan Sun, Yun Zhou [17], B.N. Chebouba, M.A. Mellal [18].

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

Методология исследования

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

Задачи:

1) рассмотреть особенности использования ГА в задачах оптимизации;

2) предложить вариант решения задачи разбиения некоторого множества пользователей провайдера интернет-услуг на группы в соответствии с определенным набором характеристик с использованием ГА;

3) оценить эффективность предложенного ГА по сравнению с алгоритмом предельного перебора.

Методы: методы системного анализа для описания концептуальных моделей в задачах кластеризации; прикладной и вычислительной математики – для моделирования эволюционных процессов на основе ГА; экспериментальные исследования – при оценке эффективности ГА по сравнению с алгоритмом предельного перебора; компьютерного и имитационного моделирования с целью оценки эффективности предложенных в статье решению.

Результаты и обсуждение

Эволюция зарекомендовала себя как очень мощный механизм поиска хороших решений сложных задач. Можно рассматривать естественный отбор как метод оптимизации, который позволяет найти адекватные решения для конкретных условий [19]. Несмотря на большое количество применений ГА в различных типах оптимизационных задач, существует очень мало исследований по использованию такого подхода к проблеме кластеризации.

Гибкость, связанная с ГА, – один из важных аспектов, который следует иметь в виду. При одном и том же представлении генома, просто изменив фитнес-функцию, можно получить другой алгоритм [20]. В случае пространственного анализа это особенно важно, так как на этапе исследования можно попробовать различные фитнес-функции.

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

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

$d_{Eij}=\sum _{l=1}^m{\left({\left(x_i^l-x_j^l\right)}^2\right)}^{1/2}.$

Итак, пусть G = (V, E) – взвешенный граф, обозначающий критерий кластеризации, где V – множество вершин; E – множество взвешенных ребер, V × V → ℜ. Тогда для любых двух вершин u, v ∈ V мы можем определить внешнюю и внутреннюю значимость ребра (u; v):

$\begin{array}{c}{I}_{out}\left(u,v\right)=E\left(u,v\right)=\frac{{\displaystyle \sum _{x\in V}E\left(x,u\right)}}{\left|V\right|};\\ I_{in}\left(u,v\right)=E\left(u,v\right)=\frac{{\displaystyle \sum _{x\in V}E\left(u,x\right)}}{\left|V\right|}\end{array}$

соответственно.

Понятно, что

$\frac{{\displaystyle \sum _{x\in V}E\left(u,x\right)}}{\left|V\right|}$

обозначает средний вес ребер от u до других вершин графа, и, следовательно, I_out(u, v), т.е. разность между весом ребра и средним весом, измеряет относительную важность (u; v) среди всех исходящих из u ребер. Аналогично, I_in(u, v) измеряет относительную важность (u; v) среди всех входящих в v ребер. Следовательно, общую важность ребра (u; v) можно обозначить как I(u, v) = I_out(u, v) + I_in(u, v). Тогда, для кластеризации C = {C₁, C₂, … , C_k} степень C, удовлетворяющая критерию представленному G, которая обозначается как deg_G (C), определяется следующим образом:

$\begin{array}{c}{\mathrm{deg}}_G\left(C\right)=\\ =w_1\sum _{1\le i\le k}\sum _{u\in C_i}\sum _{v\in C_i}I\left(u,v\right)-w_2\sum _{1\le i\ne j\le k}\sum _{u\in C_i}\sum _{v\in C_i}I\left(u,v\right),\end{array}$

где w₁; w₂ ∈ (0; 1] – параметры, устанавливаемые в зависимости от реальных приложений и экспериментов.

Два слагаемых в deg_G (C) измеряют внутрикластерную и межкластерную плотность кластеризации соответственно. Таким образом, цель состоит в том, чтобы найти кластеризацию, которая максимизирует внутрикластерную плотность и минимизирует межкластерную. Пусть cis (G) обозначает множество всех возможных кластеризаций на основе G. Тогда задача кластеризации формулируется как следующая оптимизационная задача:

$\arg \underset{C\in cis\left(G\right)}{\max }{\mathrm{deg}}_G\left(C\right).$

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

1. Генерирование начальной популяции. Начальная популяция содержит n хромосом, сгенерированных случайным образом. При этом как последовательность генов, так и характер (форма) разбиения задается случайным образом. Для каждого из n полученных разбиений рассчитывается целевая функция, и начальная популяция записывается в рабочую матрицу, занимая ее элементы с индексами от 0 до n^–1.
2. Создание потомков:

а) двухточечное скрещивание (рис. 1): хромосома случайным образом разбивается на три части, как показано на рисунке. Меняя местами крайние участки хромосомы, получаем новое решение.

 

Рис. 1. Двухточечное скрещивание (с k-го гена основной составляющей начинается новый кластер)

Fig. 1. Two-point crossing (a new cluster begins with the k^th gene of the main component)

 

Хромосомы, полученные по механизму двухточечного скрещивания, записываются в рабочую матрицу с индексами от n до 2n – 1;

б) мутация 1: два случайно взятых гена одной хромосомы меняются местами (рис. 2).

 

Рис. 2. Мутация в пределах одной формы разбиения

Fig. 2. Mutation within one partition shape

 

Таким образом, изменяется положение только одного объекта относительно кластеров. Этот вид мутации обеспечивает изменчивость в пределах одной формы разбиения. Мутанты, полученные по первому виду, располагаются в рабочей матрице с индексами от 2n до 3n – 1;

в) мутация 2: для сформированной родительской хромосомы случайным образом генерируется новый массив маркеров разбиения, при этом порядок следования объектов остается неизменным (рис. 3).

 

Рис. 3. Мутация форм разбиения

Fig. 3. Mutation of partition forms

 

Этот вид мутации обеспечивает сменность форм разбиения и позволяет расширить область поиска оптимального решения. Мутанты по второму виду занимают позиции с 3n до 4n – 1 рабочей матрицы. Для каждого из полученных таким образом потомков также подсчитывается целевая функция.

3. Реализация механизма естественного отбора в пределах популяции. Используем стратегию элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантированно переходят в новую популяцию. Применение элитизма позволяет ускорить сходимость ГА [21: 201–205]. Поэтому среди 4n особей популяции, хромосомы которых хранятся в рабочей матрице, отбираем n по критерию минимальности целевой функции. Они формируют следующее поколение.
4. Если не выполняется условие остановки, очищаем рабочую матрицу и повторяем предыдущую процедуру, начиная с шага 2. Итерационный процесс считаем завершенным, когда текущая сумма значений целевой функции для лучших n особей перестает уменьшаться.

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

Для того, чтобы проверить эффективность предложенного ГА проведем эксперимент. Для этого были взяты данные интерне-провайдера BIC. В рамках проводимого анализа изучалась статистика доступа за сутки 22.02.2024 для 150 пользователей. В качестве основных показателей, характеризующих абонентов были выбраны следующие:

• скорость передачи данных;
• полный объем входящего трафика за заданный период времени;
• полный объем исходящего трафика за заданный период времени.

В результате работы программы был получен вариант разбиения набора входных векторов на 4 однородные группы (табл. 1).

 

Таблица 1

Результат разбиения множества абонентов на кластеры [Result of dividing a set of subscribers into clusters]

Номер кластера [Cluster number]	Количество пользователей [Number of users]	Скорость доступа [Access speed]	Соотношение входящего и исходящего трафика [Ratio of incoming and outgoing traffic]
1	18	1–15 М
2	69	130 k – 2 M	Входящий > Исходящий [Incoming > Outgoing]
3	36	130 k – 1,5 M	Входящий >> Исходящий [Incoming >> Outgoing]
4	27	130 k – 1 M	Входящий ≤ Исходящий [Incoming ≤ Outgoing]

 

Анализ данных табл. 1 позволяет констатировать следующее:

• кластер 1 – это небольшой сегмент пользователей с самой высокой по выборке скоростью доступа;
• кластер 2 – это самый массовый кластер, в него вошли пользователи со средней скоростью доступа, у которых входящий трафик превышает исходящий;
• кластер 3: в этот кластер попали преимущественно абоненты у которые скорость соединения невысокая, они используют преимущественно только входящее направление передачи данных;
• кластер 4 состоит из абонентов, для которых характерно преобладание объема исходящего трафика над входящим, скорость доступа преимущественно невысокая.

Данное разбиение является приблизительным, однако несмотря на это, в полученных данных можно четко проследить наличие компактных скоплений объектов, и на их основе делать выводы о характере логических закономерностей, которые заложены в исходных данных. Сравним время работы предложенного ГА по сравнению со временем выполнения алгоритма предельного перебора для разного количества объектов в исходном множестве.

Результаты сравнения изображены на рис. 4. По оси абсцисс обозначено количество объектов в исходном множестве, по оси ординат – время работы программы.

 

Рис. 4. Сравнение алгоритмов по времени выполнения

Fig. 4. Comparison of algorithms by execution time

 

График, показанный на рис. 4, свидетельствует о том, что в задачах небольшой размерности (до 150 пользователей) ГА по времени выполнения показывает результат, несоизмеримо малый по сравнению с алгоритмом предельного перебора. Время выполнения последнего начинает стремительно расти уже при количестве n = 120 пользователей. При этом в задачах большей размерности ГА ведет себя таким образом, как показано на рис. 5: заметный рост времени выполнения программы наблюдается только тогда, когда количество пользователей превышает 350. Однако даже для значительно большего объема входных данных (390 пользователей и более) время выполнения чрезвычайно мало по сравнению с аналогичным показателем для алгоритма предельного перебора.

 

Рис. 5. Зависимость времени выполнения ГА от размерности задачи

Fig. 5. Dependence of GA execution time on problem dimension

 

Поиск оптимальных кластеров – сложная задача. Большинство методов кластеризации требуют предварительного задания количества кластеров, а иерархические методы обычно выдают набор кластеров. В обоих случаях пользователю приходится выбирать количество кластеров. В данной работе предлагается усовершенствование ГА кластеризации, способное находить оптимальное количество кластеров и их разбиений на основе числовых критериев. В качестве примера использовалась задача кластеризации пользователей интернета.

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

Заключение

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

About the authors

Alexander A. Kulikov

MIREA – Russian Technological University; Financial University under the Government of the Russian Federation

Author for correspondence.
Email: tibult41@gmail.com
ORCID iD: 0000-0002-8443-3684

Cand. Sci. (Eng.), associate professor, Department of Instrumental and Application Software, associate professor, Department of Digital and Additive Technologies

Russian Federation, Moscow; Moscow

References

Supplementary files