Кластеризация данных

Кластеризация — это процесс объединения множества объектов в группы на основе определённых критериев сходства. В геоинформационных системах и веб-картографии кластеризация чаще всего применяется для работы с большим количеством точек на карте.

Типичные задачи кластеризации:

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

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

Библиотека Turf.js предоставляет набор инструментов для пространственной кластеризации непосредственно в браузере или среде Node.js.

---

Подготовка данных

Большинство алгоритмов Turf.js работают с объектами формата GeoJSON.

Пример набора точек:

const points = turf.featureCollection([
    turf.point([37.6176, 55.7558]),
    turf.point([37.6200, 55.7560]),
    turf.point([37.6215, 55.7555]),
    turf.point([37.6500, 55.7700]),
    turf.point([37.6510, 55.7710])
]);

Каждый объект является элементом коллекции FeatureCollection.

Структура GeoJSON:

{
    type: "Feature",
    properties: {},
    geometry: {
        type: "Point",
        coordinates: [37.6176, 55.7558]
    }
}

---

Кластеризация по сетке: clustersDbscan

Одним из наиболее востребованных алгоритмов в Turf.js является DBSCAN (Density-Based Spatial Clustering of Applications with Noise).

Функция:

turf.clustersDbscan(points, maxDistance, options)

Параметры:

Параметр	Описание
points	Коллекция точек
maxDistance	Максимальное расстояние между соседними точками
options	Дополнительные настройки

Пример:

const clustered = turf.clustersDbscan(points, 0.5, {
    units: "kilometers"
});

После выполнения каждая точка получает дополнительные свойства:

{
    cluster: 0,
    dbscan: "core"
}

Возможные значения поля dbscan:

Значение	Описание
core	Центральная точка кластера
edge	Пограничная точка
noise	Шумовая точка

---

Принцип работы DBSCAN

Алгоритм строится на понятии плотности размещения объектов.

Для каждой точки выполняются шаги:

1. Поиск соседей в заданном радиусе.
2. Определение достаточной плотности окружения.
3. Формирование нового кластера.
4. Расширение кластера за счёт связанных соседей.
5. Выявление шумовых объектов.

Визуально:

Кластер 1

● ● ●
 ● ●

Кластер 2

     ● ●
      ●

Шум

           ●

Главное преимущество DBSCAN заключается в способности обнаруживать кластеры произвольной формы.

---

Настройка минимального количества точек

Параметр minPoints определяет минимальное число соседей, необходимое для создания кластера.

Пример:

const clustered = turf.clustersDbscan(points, 0.5, {
    units: "kilometers",
    minPoints: 3
});

Интерпретация:

• minPoints = 2 — образуется много небольших кластеров;
• minPoints = 5 — формируются только плотные группы;
• большие значения позволяют отсекать случайные скопления.

Подбор значения зависит от характера данных.

---

Анализ результатов кластеризации

Полученные данные можно просмотреть через свойства объектов.

Пример:

clustered.features.forEach(feature => {
    console.log(feature.properties.cluster);
});

Результат:

0
0
0
1
1

Здесь обнаружены два кластера:

• кластер №0;
• кластер №1.

---

Поиск количества кластеров

Часто требуется определить число сформированных групп.

Пример:

const clusters = new Set();

clustered.features.forEach(feature => {
    const id = feature.properties.cluster;

    if (id !== undefined) {
        clusters.add(id);
    }
});

console.log(clusters.size);

Результат:

2

---

Выделение объектов конкретного кластера

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

Пример:

const cluster0 = clustered.features.filter(
    feature => feature.properties.cluster === 0
);

Создание новой коллекции:

const clusterCollection = turf.featureCollection(cluster0);

Такой набор можно использовать для дальнейшего анализа.

---

Построение границ кластера

После нахождения группы объектов часто требуется определить её пространственные границы.

Для этого удобно использовать выпуклую оболочку.

const hull = turf.convex(clusterCollection);

Получается полигон:

{
    type: "Feature",
    geometry: {
        type: "Polygon",
        coordinates: [...]
    }
}

Такой подход позволяет визуализировать реальные области концентрации объектов.

---

Определение центров кластеров

Центральная точка помогает представить кластер одним объектом.

Для вычисления центра:

const center = turf.center(clusterCollection);

Результат:

{
    type: "Feature",
    geometry: {
        type: "Point",
        coordinates: [...]
    }
}

Центры широко используются при построении агрегированных карт.

---

Кластеризация методом K-Means

Turf.js также содержит реализацию алгоритма K-Means.

Функция:

turf.clustersKmeans(points, options)

Пример:

const result = turf.clustersKmeans(points, {
    numberOfClusters: 3
});

Основное отличие от DBSCAN заключается в необходимости заранее задавать количество кластеров.

---

Принцип работы K-Means

Алгоритм выполняет несколько итераций.

Этапы:

1. Создание начальных центроидов.
2. Распределение точек по ближайшим центрам.
3. Пересчёт положения центров.
4. Повторение шагов до стабилизации.

Упрощённая схема:

Шаг 1

X       X

    ●
 ●     ●

Шаг 2

X   ●   X
 ●     ●

Шаг 3

   X     X
 ● ●   ● ●

Где:

• ● — точки данных;
• X — центроиды.

---

Настройка количества кластеров

Параметр:

numberOfClusters

Пример:

const result = turf.clustersKmeans(points, {
    numberOfClusters: 5
});

Важно понимать особенности выбора значения:

Слишком маленькое количество:

Много различных групп
↓
Один большой кластер

Слишком большое количество:

Одна группа
↓
Несколько искусственных кластеров

Оптимальное значение зависит от предметной области и характера данных.

---

Получение номера кластера

После выполнения K-Means каждая точка получает свойство:

feature.properties.cluster

Пример:

result.features.forEach(feature => {
    console.log(feature.properties.cluster);
});

Возможный результат:

0
1
1
2
0

---

Получение центроидов кластеров

Каждая группа имеет собственный центр.

Получение центров:

const clusters = {};

result.features.forEach(feature => {
    const id = feature.properties.cluster;

    if (!clusters[id]) {
        clusters[id] = [];
    }

    clusters[id].push(feature);
});

Далее:

for (const id in clusters) {
    const collection = turf.featureCollection(clusters[id]);

    const centroid = turf.centroid(collection);

    console.log(id, centroid);
}

---

Сравнение DBSCAN и K-Means

Характеристика	DBSCAN	K-Means
Требует число кластеров	Нет	Да
Учитывает плотность	Да	Нет
Находит шум	Да	Нет
Подходит для произвольных форм	Да	Ограниченно
Скорость работы	Высокая	Очень высокая
Чувствительность к параметрам	Средняя	Высокая

Практические рекомендации:

• пространственный анализ реальных объектов — DBSCAN;
• сегментация данных по известному числу групп — K-Means;
• выявление аномалий — DBSCAN;
• быстрые статистические расчёты — K-Means.

---

Построение тепловых зон на основе кластеров

После кластеризации можно вычислить размеры групп.

Пример:

const clusterStats = {};

result.features.forEach(feature => {
    const id = feature.properties.cluster;

    clusterStats[id] ??= 0;
    clusterStats[id]++;
});

Результат:

{
    0: 45,
    1: 120,
    2: 78
}

На основе этих данных можно:

• изменять размер маркеров;
• окрашивать кластеры по плотности;
• строить тепловые карты;
• выделять зоны повышенной активности.

---

Кластеризация данных с дополнительными атрибутами

Точки могут содержать произвольные свойства.

const point = turf.point(
    [37.6176, 55.7558],
    {
        users: 150,
        city: "Москва"
    }
);

После кластеризации атрибуты сохраняются:

{
    city: "Москва",
    users: 150,
    cluster: 0
}

Это позволяет выполнять агрегацию показателей внутри групп.

Пример вычисления суммарного количества пользователей:

const totalUsers = clusterFeatures.reduce(
    (sum, feature) => sum + feature.properties.users,
    0
);

---

Анализ плотности кластеров

Плотность может определяться как отношение количества объектов к площади занимаемой территории.

Площадь кластера:

const hull = turf.convex(clusterCollection);

const area = turf.area(hull);

Количество объектов:

const count = clusterCollection.features.length;

Плотность:

const density = count / area;

Чем больше значение, тем более компактным является кластер.

---

Обнаружение выбросов

Одной из сильнейших сторон DBSCAN является автоматическое определение выбросов.

Поиск шумовых точек:

const outliers = clustered.features.filter(
    feature => feature.properties.dbscan === "noise"
);

Полученные объекты могут обозначать:

• ошибки измерений;
• редкие события;
• аномальное поведение пользователей;
• подозрительные транзакции;
• неисправные датчики.

---

Практический сценарий: анализ сети магазинов

Исходные данные:

const stores = turf.featureCollection(storePoints);

Кластеризация:

const clusters = turf.clustersDbscan(
    stores,
    2,
    {
        units: "kilometers",
        minPoints: 4
    }
);

Последующая обработка:

const denseAreas = [];

for (const id of clusterIds) {
    const features = getClusterFeatures(id);

    const collection =
        turf.featureCollection(features);

    denseAreas.push({
        center: turf.center(collection),
        border: turf.convex(collection),
        count: features.length
    });
}

Результат анализа:

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

---

Производительность при работе с большими наборами данных

При обработке десятков и сотен тысяч точек рекомендуется:

• выполнять кластеризацию на сервере;
• предварительно фильтровать данные по региону;
• использовать упрощённые геометрии;
• применять пакетную обработку;
• хранить результаты кластеризации в кэше.

Пример фильтрации по области:

const filtered = turf.pointsWithinPolygon(
    points,
    regionPolygon
);

После уменьшения объёма данных:

const clustered =
    turf.clustersDbscan(filtered, 1, {
        units: "kilometers"
    });

Такой подход существенно сокращает время вычислений и объём памяти, необходимой для пространственного анализа больших географических наборов данных.