Кластеры, центры и расстояния
Правила близости объектов, ограничение диаметра, медиана и различия между определениями центра.
У одного объекта может быть несколько характеристик: положение, скорость, масса, класс. Для объединения объектов в группы необходимо выбрать, какие характеристики сравниваются и что означает близость. Затем для полученных групп можно вычислять другие величины. Эти действия связаны общими данными, но не обязаны использовать одну и ту же формулу расстояния.
Объект, признак и расстояние
Признак описывает отдельное свойство объекта. Он бывает числовым, например масса, или категориальным, например класс частицы. Категориальные значения прежде всего позволяют проверять принадлежность к классу. Запись класса римскими цифрами сама по себе не означает, что разность этих чисел измеряет физическое сходство.
Числовая характеристика может быть вычислена из нескольких исходных полей. Например, кинетическая энергия частицы массы m с проекциями скорости v_x,v_y определяется формулой E=m(v_x^2+v_y^2)/2. После этого каждую частицу можно представить одной точкой на числовой прямой энергий. Её положение на этой прямой не связано напрямую с координатами в физическом пространстве.
Метрика задаёт способ измерять расстояние между точками выбранного пространства. Для двух числовых значений естественно расстояние |a-b|. На плоскости евклидово расстояние между точками A=(x_1,y_1) и B=(x_2,y_2) равно d(A,B)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.
Если сравниваются энергии, две разные частицы могут иметь нулевую разность энергий. Это означает совпадение выбранного признака, а не совпадение самих объектов. Поэтому вместе с вычисленной энергией сохраняется исходная запись: позднее могут потребоваться её координаты или класс.
Кластер и ограничение диаметра
Кластеризация означает разбиение множества объектов на группы по заданному правилу. При разбиении каждый объект относится ровно к одной группе, группы не пересекаются и не бывают пустыми. Само слово «кластер» ещё не определяет алгоритм: необходимо знать число групп, критерий их допустимости и возможные исключения.
Диаметр группы есть наибольшее расстояние между двумя её элементами. Для группы чисел с расстоянием через модуль разности диаметр равен E_{\max}-E_{\min}. Действительно, любая внутренняя пара лежит между крайними значениями и не может оказаться дальше них. Поэтому требование |E_i-E_j|\le R для любых двух элементов равносильно ограничению ширины всего диапазона.
Например, учебная группа с энергиями 2; 2{,}7; 3{,}9 имеет диаметр 1{,}9 и подходит для порога R=2. Если добавить энергию 4{,}2, новый диаметр станет 2{,}2. Близость добавленного значения к прежнему максимуму не спасает группу: ограничение должно выполняться и для пары с минимальной энергией.
Условие «можно пройти от одного объекта к другому по цепочке близких соседей» устроено иначе. В цепочке расстояние между крайними объектами может быть большим. Например, у энергий 1; 2{,}5; 4 оба соседних промежутка не превосходят двух, но диаметр равен трём. Алгоритм поиска связанных цепочек не решает автоматически задачу с ограничением диаметра.
В задании №27 из проекта демоверсии ФИПИ-2027 ограничивается именно разность энергий любых двух частиц. При этом расстояние для первой характеристики ответа измеряется уже на координатной плоскости. Один кластер может иметь малую ширину по энергии и большой геометрический диаметр: противоречия здесь нет.
Что означает центр
Слово центр обозначает выбранного представителя группы, но способ выбора требует определения. Можно искать точку с наименьшей суммой расстояний, с наименьшим максимальным расстоянием или среднее значение. Получаются разные задачи и, вообще говоря, разные ответы. Отдельно оговаривается, обязан ли центр быть одним из исходных объектов.
Если центром должна быть существующая частица, новая точка с усреднёнными координатами не подходит уже по этому ограничению. Даже совпадение такой точки с исходным объектом ещё не доказывает оптимальность: необходимо проверить именно требуемую сумму или другую величину.
Для энергий рассматривается сумма модулей отклонений от кандидата z:
S(z)=\sum_{i=1}^{n}|z-E_i|.
Каждое слагаемое показывает, насколько энергия одной частицы отличается от энергии кандидата. Все частицы имеют одинаковый вес в этой сумме. Масса уже участвует в вычислении энергии; дополнительно умножать слагаемые на массу означало бы изменить определение центра.
Почему сумма модулей приводит к медиане
Медиана есть среднее по положению значение упорядоченного ряда. Для нечётного числа элементов оно делит оставшиеся значения на две равные по количеству части. Медиана не обязана быть близка к среднему арифметическому: её положение определяется порядком, а не суммой чисел.
Пусть энергия кандидата находится между соседними различными значениями. При небольшом движении вправо каждое значение слева становится дальше на величину сдвига, а каждое значение справа ближе на ту же величину. Если справа больше частиц, сумма уменьшается; если слева больше, увеличивается. Минимум достигается там, где количество значений с обеих сторон уравновешено, то есть на медиане.
Для учебного ряда 1; 2; 9 медиана равна двум. Сумма модулей при этом равна 1+0+7=8. Среднее арифметическое равно четырём; соответствующая сумма равна 3+2+5=10. Кроме того, объекта с энергией четыре в ряду нет. Так различаются и критерий оптимальности, и требование выбирать существующий объект.
При чётном числе элементов любая точка между двумя средними значениями минимизирует сумму модулей. Если разрешены только исходные объекты, обе средние частицы подходят. Даже нечётное количество само по себе не гарантирует единственную частицу-центр: несколько объектов могут иметь одинаковую медианную энергию. Поэтому гарантия единственности центра относится к конкретному условию и не переносится на любые учебные данные.
Другие определения и итоговые характеристики
Среднее арифметическое минимизирует сумму квадратов отклонений чисел, если кандидат может быть любым числом. Для суммы модулей правильным ориентиром служит медиана. Если вместо одномерных значений заданы точки плоскости и требуется существующая точка с минимумом суммы евклидовых расстояний, такой представитель называется медоидом. Независимый выбор средних по положению координат не решает эту задачу с евклидовым расстоянием.
Центр также отличается от самой далёкой пары. Расстояние от центра до крайнего объекта характеризует удалённость от выбранного представителя. Диаметр сравнивает все допустимые пары между собой и не требует, чтобы одна из точек была центром. Если условие ограничивает пары определённым классом, диаметр вычисляется только среди объектов этого класса, но центр всей группы от такого ограничения автоматически не меняется.
Преобразования формул зависят от цели. При сравнении отдельных неотрицательных расстояний корень можно отложить: наибольший квадрат соответствует наибольшему расстоянию. Для суммы расстояний так поступать нельзя: замена каждого слагаемого его квадратом меняет оптимизируемую функцию и может изменить центр. Поэтому удобное преобразование проверяется вместе с операцией, внутри которой используется формула.
От определения к решению
Почему сравнение очередной энергии с минимумом группы контролирует все пары, а сравнение с предыдущей энергией не контролирует? Почему после выбора медианы по всем частицам всё ещё нужен отдельный перебор пар частиц II? В статье «Задание №27. Кластеры и характеристики объектов» эти вопросы связаны с полным алгоритмом, учебным файлом и вычислением ответа официального проекта.