Заявка : в двумерном пространстве набор точек принадлежит одному кластеру, если (и только если) ОБА их проекции на OX кластеризованы, а их проекции на OY кластеризованы.
на OX, проекции A, B, C, D сгруппированы;на OY проекции A, B, C, E сгруппированы;в целом, A, B и C. кластеризованы.
Определение точек, которые кластеризованы в одномерном пространстве:
Давайте разберем несколько точек на действительной оси.Интуитивно понятно, что две точки принадлежат одному кластеру, если они разделены «небольшим расстоянием»;если они разделены «большим расстоянием», они принадлежат разным кластерам.Теперь мы должны определить, что такое «большое расстояние» и что такое «1016 *« небольшое расстояние ».
Давайте отсортируем все расстояния и поищем порог. Для набора точек с координатами OX, равного [0,1,3,4,14,15,16,19,29,30,31], расстояния между последовательными точками будут [1,2,1,10,1,1,3,10,1,1].Тот же набор расстояний при сортировке будет выглядеть как [1,1,1,1,1,1,2,3,10,10].Существует порог между 3 и 10, поэтому мы будем обозначать все расстояния <= 3 как «небольшие расстояния», а все остальные как «большие расстояния». </p>
Как мы выбираем порог? Делая разницу между двумя соседними элементами.В нашем примере 10-3 = 7 - это разница в величине.
Если есть несколько порогов равных значений, выберите самый правый;выбор самого правого порогового значения приводит к небольшому количеству «больших расстояний», в противном случае многие расстояния будут считаться большими, и, соответственно, будет много кластеров.Но это зависит от требований вашего бизнеса.Вы можете сгруппировать 30 местоположений в 3 кластера в каждом из 10 местоположений или в 10 кластеров по 3 местоположения в каждом.
Если отсортированные расстояния похожи на [2,4,6,8,10] (нет кандидата на пороговое значение), затем выберите какой-нибудь процентиль, например 75-процентиль: верхняя четверть будет «большим расстоянием», все остальные - «маленькими расстояниями»
Группировка точек в кластеры в соответствии с их прогнозами на OX:
Теперь, когда мы знаем, как группировать действительные числа, давайте возьмем OX-проекции точек и сгруппируем их.
Давайте получим следующие точки вместе с ихКоординаты OX: P1 (101), P2 (12), P3 (201), P4 (13), P5 (202), P6 (11), P7 (102);
Те же точки, отсортированные по ихКоордината OX: P6 (11), P2 (12), P4 (13), P1 (101), P7 (102), P3 (201), P5 (202);
Далее мы сделаем еще одингруппировка по проекциям OY.
Наблюдение 1 : Когда индексы точки сортируются, проекции OX - нет;когда мы сортируем проекции OX, теперь индексы не будут сортироваться.
Наблюдение 2 : при кластеризации с использованием проекций OX не следует ожидать получения тех же кластеров, что и примы группируем, используя проекции OY.Фактически мы будем пересекать полученные результаты.Результаты кластеризации отличаются, потому что координата OY точки полностью независима от ее координаты OX.Таким образом, совершенно другой набор значений на оси OY.
Определение фактических кластеров:
Ранее мы уже проводили некоторую кластеризацию как для проекций OX, так и для OY,получение разных группировок одинаковых точек.Теперь мы будем пересекать эти кластеры в поисках общих точек.
Возвращаясь к нашему первому изображению, кластеризация после того, как OX дает (A, B, C, D) кластер, после того, как OY мы получаем (A, B, C), E), пересечение этих множеств будет (A, B, C) - конечный кластер.Но это был простой пример.
Общая стратегия состоит в том, чтобы сделать картошное произведение кластеров на OX, с кластерами, полученными на OY.Для каждого такого элемента в картезианском произведении мы будем пересекать элементы в кластере OX с элементами в кластере OY.Если мы получим 3 кластера на OX и 4 кластера на OY, то в картезианском продукте будет 12 элементов.Давайте выберем один из них.Это пара из двух кластеров A и B: A - это кластер в OX, B - это кластер в OY.Если A и B имеют некоторые общие точки, то эти точки действительно являются кластером.
В приведенном выше примере из 7 точек мы получили только один кластер.Не впечатляетНо мы можем и дальше присоединяться к соседним кластерам.Давайте не будем забывать, что оранжевые сегменты представляют «небольшие расстояния», а черные сегменты представляют «большие расстояния».На изображении выше, от «кластера» P1 до кластеров P5 или P3 + P7, существует только одно «большое расстояние».От кластера P3 + P7 до кластера P4 есть два больших расстояния плюс одно небольшое расстояние.
отказ от ответственности : эта процедура рассматривает карту мира как прямоугольник (меридианы - это параллельные линии, которые никогда не пересекаются).Кроме того, вместо того, чтобы рассматривать меридианы в 1 градус и 179 градусов как можно ближе друг к другу, они будут выглядеть очень далеко друг от друга.(расстояние между ними будет 178 градусов, а не 2 градуса). Однако это не проблема, поскольку в большинстве случаев акт родоразрешения носит региональный характер или, в большинстве случаев, на уровне страны.Пока ваша страна не пройдена 180 меридианом, у вас все в порядке.