Вычислительный эксперимент и результаты
Целью вычислительного эксперимента является определение степени влияния на результат кластеризации априорных нормировочных значений и способа нормировки выборки молниевых разрядов, соответствующих временному интервалу один час (c 07:15 по 08:15 UTC).
При проведении кластерного анализа объектов исследования необходимо задание априорных нормировочных параметров dA - линейные размеры грозовой конвективной ячейки и tA - среднее время существования грозовой конвективной ячейки, которые показывают, что грозовые разряды расстояние между которыми меньше dA и разница во времени регистрации меньше tA должны образовывать одну группу. Выше было указано, что линейные размеры грозовой конвективной ячейки могут быть от 25 до 100 км и время существования - от 20 до 60 минут. С учетом точности определения места возникновения молниевого разряда сетью WWLLN, которая в среднем составляет 5.4 км, при кластеризации грозовых разрядов целесообразно использовать следующие значения априорных нормировочных параметров dA= 50 км, 75 км, 100 км и tA= 20 мин, 30 мин, 40 мин, 50 мин, 60 мин.
Нормирование априорными параметрами производится двумя способами. Первый способ подразумевает, что значения нормировочных параметров (dA,dA,tA) задаются в явном виде [6]. Во втором способе значения нормировочных параметров задаются как (1,1,C), где C определяется по формуле C = dA / tA и является коэффициентом связывающим расстояние в пространстве между событиями (грозовыми разрядами) и временем их регистрации [20]. Отметим, что вычисление расстояния между нормированными характеристиками объектов производится с помощью евклидовой метрики.
Результаты группировки молниевых разрядов для первого и второго способа задания априорных нормировочных параметров совпали. Таким образом, способ нормировки ([6] или [20]) не влияет на результаты кластеризации.
В таблице 1 для каждого набора априорных нормировочных параметров (dA,dA,tA), (1,1,C) и для каждого алгоритма приведены полученные в результате кластеризации количество кластеров (k) и величина индекса качества asw. Для алгоритма dbscan дополнительно указано количество разрядов, определенных как «шум» (noise).
Значения индекса asw для всех нормировочных параметров и для всех алгоритмов попадают в интервал от 0.71 до 1, что свидетельствует о наличии сильной (strong) структуры кластеров [10].
Таблица 1 - Результаты кластеризации данных о грозовых разрядах, зарегистрированных WWLLN 7 августа 2017 года на территории Республики Алтай
|
Иерархический алгоритм single |
|||||||||||
|
tA = 20 min |
tA = 30 min |
tA = 40 min |
tA = 50 min |
tA = 60 min |
|||||||
|
k |
asw |
k |
asw |
k |
asw |
k |
asw |
k |
asw |
||
|
50 км |
15 |
0.82 |
3 |
0.85 |
4 |
0.87 |
4 |
0.88 |
4 |
0.89 |
|
|
75 км |
15 |
0.84 |
15 |
0.82 |
3 |
0.83 |
3 |
0.85 |
4 |
0.87 |
|
|
100 км |
15 |
0.86 |
15 |
0.84 |
15 |
0.82 |
3 |
0.83 |
3 |
0.85 |
|
|
Иерархический алгоритм complete |
|||||||||||
|
50 км |
3 |
0.80 |
3 |
0.85 |
4 |
0.87 |
4 |
0.88 |
4 |
0.89 |
|
|
75 км |
19 |
0.82 |
3 |
0.81 |
3 |
0.83 |
3 |
0.85 |
4 |
0.87 |
|
|
100 км |
19 |
0.83 |
19 |
0.82 |
3 |
0.80 |
3 |
0.83 |
3 |
0.85 |
|
|
Иерархический алгоритм average |
|||||||||||
|
50 км |
3 |
0.80 |
3 |
0.85 |
4 |
0.87 |
4 |
0.88 |
4 |
0.89 |
|
|
75 км |
15 |
0.84 |
3 |
0.81 |
3 |
0.83 |
3 |
0.85 |
4 |
0.87 |
|
|
100 км |
19 |
0.83 |
19 |
0.82 |
3 |
0.80 |
3 |
0.83 |
3 |
0.85 |
|
|
Иерархический алгоритм ward.D2 |
|||||||||||
|
50 км |
3 |
0.80 |
3 |
0.85 |
4 |
0.87 |
4 |
0.88 |
4 |
0.89 |
|
|
75 км |
19 |
0.83 |
3 |
0.81 |
3 |
0.83 |
3 |
0.85 |
4 |
0.87 |
|
|
100 км |
20 |
0.83 |
19 |
0.82 |
3 |
0.80 |
3 |
0.83 |
3 |
0.85 |
|
|
kmeans |
|||||||||||
|
50 км |
3 |
0.80 |
3 |
0.85 |
3 |
0.86 |
3 |
0.87 |
3 |
0.88 |
|
|
75 км |
3 |
0.75 |
3 |
0.81 |
3 |
0.83 |
3 |
0.85 |
3 |
0.86 |
|
|
100 км |
4 |
0.72 |
3 |
0.78 |
3 |
0.80 |
3 |
0.83 |
3 |
0.85 |
|
|
dbscan |
|||||||||||
|
50 км |
7 noise=5 |
0.78 |
6 noise=2 |
0.76 |
6 noise=2 |
0.78 |
6 noise=2 |
0.78 |
6 noise=2 |
0.78 |
|
|
75 км |
7 noise=5 |
0.78 |
6 noise=2 |
0.72 |
6 noise=2 |
0.74 |
6 noise=2 |
0.76 |
6 noise=2 |
0.78 |
|
|
100 км |
8 noise=3 |
0.76 |
7 noise=0 |
0.66 |
7 noise=0 |
0.70 |
6 noise=0 |
0.69 |
6 noise=0 |
0.70 |
Для используемых в работе [6] нормировочных параметров dA = 50 км и tA = 30 мин все рассматриваемые алгоритмы, кроме dbscan, разбивают выборку на три «крупных» кластера, разнесенных в пространстве друг от друга на большое расстояние. При этом пространственно полученные кластеры, объединили в себе все разряды в северной, западной и восточной частях рассматриваемой территории (например, рис.2). Таким образом, в один кластер были отнесены достаточно удаленные друг от друга разряды.
Алгоритм k-means только для параметров dA = 100 км и tA = 20 мин разбивает выборку на четыре кластера, при всех других параметрах нормировки - на три кластера. Это свидетельствует о малой зависимости результатов кластеризации от нормировочных параметров. Пространственно три выделенных кластера соответствуют группам разрядов в северной, западной и восточной частях территории республики (рис. 2).
В целом для всех рассматриваемых иерархических алгоритмов выявлена зависимость результатов кластеризации от нормировочных параметров, так как для разного набора нормировочных параметров получено различное количество кластеров. При этом набольшую зависимость от нормировочных параметров показал метод single (метод ближайшего соседа).
Иерархические алгоритмы при tA = 20 минут и dA =75 км и 100 км выделяют более 15 кластеров, что не является приемлемым результатом для рассматриваемой выборки. При tA = 30 минут и dA = 75 км и 100 км результаты группировки аналогичны результатам алгоритма k-means (3 кластера, аналогичных представленным на рисунке 2). Близким к результатам экспертной оценки группировки грозовых разрядов можно считать выделение 4 кластеров при нормировочных параметрах dA = 50 км и tA = 40, 50 и 60 минут.
При этом в один кластер объединяются два кластера в западной части и три кластера в северной части территории республики (эти кластеры можно отнести к одному многоячейковому грозовому облаку), восточные кластеры полностью согласуются с экспертной оценкой (рис.3).
Рисунок 2. Пример разбиения на кластеры молниевых разрядов с помощью алгоритма k-means и их соответствие грозовым облакам
Иерархические агломеративные алгоритмы рассматривались в работе на предмет их использования для группировки грозовых разрядов в виде иерархической структуры, с целью определения одноячейковых и многоячейковых грозовых облаков. Экспериментально выявлено, что иерархические агломеративные алгоритмы не подходят для таких целей. Кроме этого необходимо отметить и основные недостатки этих алгоритмов: высокая вычислительная сложность (порядка O(N3) ) и, следовательно, их неприменимость для обработки больших массивов данных, а также неспособность выделять кластеры разной структуры.
Рисунок 3. Пример разбиения на кластеры молниевых разрядов с помощью алгоритма average (метод средней связи) и их соответствие грозовым облакам
Алгоритм dbscan выделяет разное количество кластеров (от 6 до 8 кластеров) при tA = 20 минут для всех рассматриваемых значений параметра dA и при dA = 100 км для всех параметров tA. Количество выделяемых алгоритмом dbscan кластеров близко к экспертной оценке в 5-7 кластеров. Следовательно, наблюдается слабая зависимость результатов кластеризации грозовых разрядов от параметров нормировки.
Алгоритм dbscan выделил соответственно экспертной оценке по два отдельных кластера в восточной части территории республики Алтай (рис. 4 а,б). Северный кластер разбивается на 3 кластера, что, в принципе соответствует возможности определения многоячейковой грозовой области. В западной части разряды одного из кластеров определены как «шум» при dA = 50 и 75 км и tA не менее 30 минут (рис. 4а). «Шумовые» разряды не выделяются при нормировочных параметрах dA = 100 км и tA не менее 30 минут (рис. 4 б), что наилучшим образом согласуется с экспертной оценкой.
А) при = 50 км и = 30 минут
Б) при = 100 км и = 30
Рисунок 4. Пример разбиения на кластеры молниевых разрядов с помощью алгоритма dbscan и их соответствие грозовым облакам
В ходе проведения кластерного анализа грозовых разрядов с помощью представленных в работе алгоритмов, авторы пришли к выводу о том, что процесс группировки грозовых разрядов должен предполагать два этапа: на первом этапе выделяются небольшие достаточно плотные кластеры и на втором этапе близкие кластеры объединяются в сложный кластер. При этом результаты вычислительного эксперименты показали, что для вычисления межкластерного расстояния лучше использовать метод средней связи (average method) или метод Уорда (Ward method).
Также, по мнению авторов, метод кластеризации должен учитывать «естественный процесс» образования групп грозовых разрядов во времени и в пространстве: каждый следующий по времени разряд инициирует новую группу разрядов (грозовую конвективную ячейку) или происходит близко к уже существующей группе разрядов. Для этого представляется перспективным развитие подхода таксономии данных основанных на понятии конкурентного сходства [21].
Заключение
Исследовано влияние нормировочных параметров на результаты кластеризации данных о грозовых разрядах иерархическими агломеративными алгоритмами и алгоритмами k-means, dbscan.
На примере рассматриваемой выборки грозовых разрядов и алгоритмов кластеризации k-means, dbscan и иерархических алгоритмов продемонстрировано, что, несмотря на положительный опыт использования нормировочных параметров, соответствующих линейным размерам грозовой конвективной ячейки 50 км и времени ее существования 30 минут [6], эти параметры не позволили получить количество кластеров, согласующееся с экспертной оценкой.
Экспериментально показано, что выбор значений нормировочных параметров имеет существенное влияние на количество выделяемых кластеров с помощью иерархических алгоритмов кластеризации (особенно для метода ближайшего соседа). При этом иерархические алгоритмы имеют ряд недостатков и не могут быть использованы дл выделения иерархической структуры молниевых разрядов (одноячейковые или многоячейковые грозы). Выбор нормировочных параметров практически не влияет на результаты кластеризации грозовых разрядов с помощью алгоритмов k-means и dbscan. При этом количество кластеров молниевых разрядов, полученных в результате кластеризации алгоритмом k-means, не согласуется с их экспертной оценкой. Наилучшее согласование результатов кластеризации с экспертной оценкой получено алгоритмом dbscan при нормировочных параметрах соответствующих линейным размерам грозовой конвективной ячейки 100 км и времени существования от 30 минут до часа.
Дальнейшее повышение эффективности кластеризации данных о грозовых разрядах с целью получения информации о грозах, которые определяются как группа гро-зовых разрядов, близких в пространстве и незначительно различающихся по времени регистрации, возможно с привлечением методов кластерного анализа основанных на понятии конкурентного сходства.
Библиография
1.Кононов И.И., Юсупов И.Е. Кластерный анализ грозовой активности // Радиотехника и электроника, 2004, том 49, № 3, C.283-291.
2.Аджиева А.А, Шаповалов В.А. Кластерный анализ в автоматическом выявлении и сопровождении грозовых очагов по данным грозопеленгационной сети // Инже-нерный вестник Дона. 2016. №2 URL: ivdon.ru/ru/magazine/archive/n2y2016/3559
3.Mezuman, K., C. Price, and E. Galanti, 2014: On the spatial and temporal distribution of global thunderstorm cells. Environ. Res. Lett., 9, 124023, DOI: https://doi.org/10.1088/1748-9326/9/12/124023.
4.Богушов А.К., Панюков А.В. Размещение взаимосвязанных объектов в условиях неопределенности // IV Всероссийская конференция Проблемы оптимизации и экономические приложения : Материалы конференции (Омск, 29 июня - 4 июля, 2009) / Омский филиал Института математики СО РАН. - Омск: Полиграф. Центр КАН, 2009. - С.113.