Оптимизация планирования доставки грузов. Алгоритм кластеризации k-means (метод K-средних).
Разработка - Математика и алгоритмы
Взгляните на фото .. так выглядит бардак.. после того как дочка поиграла и бросила на полу в своей комнате вещи. При виде такого безобразия, ей тут же прилетает задача прибраться в комнате, а это значит что ей нужно произвести кластеризацию вещей по признаку, то есть игрушки отнести в одну группу, книжки– в другую, а карандаши в третью и т.д., чтобы затем убрать все на свои места.
Признак, по которому мы собираем одни предметы в одну группу, а другие в другую, называется метрикой. Грубо говоря, метрика – это просто способ отделить один предмет от другого. Самый распространненый вариант – это когда метрикой является расстояние.
Кластеризация (деление на кластеры) может быть и немного другой. Например, если поставить задачу разделить все вещи на четыре кучи (кластера), то при этом наверняка игрушки попадут в одну кучу с книжками или карандашами, т.е перемешаются. Такой метод называется алгоритм кластеризации К-средних, то есть мы заранее задаем количество кластеров, а алгоритм сам разделяет объекты на это количество.
Описание алгоритма кластеризации "для чайников"
Описание алгоритма кластеризации
Одно время были книжки из серии "для чайников", и там по-простому говорилось о "сложных материях". Попробую объяснить по-простому, как работает сам алгоритм кластеризации. Он итерационый, то есть повторяется несколько раз, пока не «сойдется». Сходимость в данном случае значит, что с каждой итерацией (повторением вычислений) мы все точнее приближаемся к правильному ответу. А «сошелся» в данном случае значит, что мы нашли правильный ответ или мы очень близко к нему (то есть нашлось число с небольшой погрешностью, на которую мы плюем и топчем ногами).
В данном случае мы будем работать с точками на плоскости размером 20 на 20 (не важно даже каких единиц). Например, дано 50 точек, расположенных случайным образом. Нужно распределить эти точки по кластерам алгоритмом К-средних (или K-means).
Действуем так:
Сначала случайным образом выставляем на этой же плоскости несколько центров кластеров, например 4. Центр кластера называется центроидом. Без начального положения центроидов не удастся запустить алгоритм (увидите, почему). Как их расставить – дело ваше, можно самостоятельно вводить координаты, можно применить еще какой-нибудь алгоритм. Далее начинается вычисление кластеров в цикле. Делается это так:
- Сначала мы «привязываем» каждую точку к тому центроиду, к которому она ближе, т.к. центроид является центром кластера, то можно сказать, что мы относим каждую точку к тому кластеру, к центру которого она ближе.
- Когда все точки привязаны и ни одна от нас не убежала, нужно пересчитать координаты центроидов. Для этого мысленно вписываем весь кластер в прямоугольник и ставим центроид туда, где пересекутся его диагонали (в середину, короче). Квадратики – это центры кластеров. Линии от точек до центров нужны просто для наглядности, чтобы сразу видеть, к какому центру принадлежит точка.
- Повторяем для нового центра действия с шага 1 до тех пор, пока центроиды не перестанут менять своего положения. Если они перестали менять положение, значит алгоритм сошелся и мы теперь крутые перцы. Кстати, как правило алгоритм сходится где-то за 2-6 итераций. Но в теории возможно, что алгоритм не сойдется вообще, поэтому на всякий случай нужно включить в него «защиту» – прервать его после например 30 итераций. Это гарантирует, что программа не зависнет.
Теперь для тех, кто все-таки добрался до этого места и не сбежал, приведу более строгое математическое описание метода и пример расчета.
Описание алгоритма кластеризации
Для выборки данных, содержащей n записей (объектов), задается число кластеров k , которое должно быть сформировано. Затем алгоритм разбивает все объекты выборки на k разделов (k < n), которые и представляют собой кластеры.
Одним из наиболее простых и эффективных алгоритмов кластеризации является алгоритм k-means (Mac-Queen, 1967) или в русскоязычном варианте k-средних (от англ. mean – среднее значение). Он состоит из четырех шагов, но сначала задается число кластеров k, которое должно быть сформировано из объектов исходной выборки.
1. Случайным образом выбирается k записей исходной выборки, которые будут служить начальными центрами кластеров μ. Такие начальные точки, из которых потом «вырастает» кластер, часто называют «семенами» (от англ. seeds – семена, посевы). Каждая такая запись будет представлять собой своего рода «эмбрион» кластера, состоящий только из одного элемента.
2. Для каждого центройда вычислить расстояния до всех точек
Ключевым моментом алгоритма k-means является вычисление на каждой итерации расстояния между записями и центрами кластеров, что необходимо для определения, к какому из кластеров принадлежит данная запись. Правило, по которому производится вычисление расстояния в многомерном пространстве признаков, называется метрикой. Наиболее часто в практических задачах кластеризации используются следующие метрики.
- Евклидово расстояние или метрика L2
Пример. Для лучшего понимания методики воспользуемся геометрической интерпретацией определения, к какому из центров кластеров ближе всего расположена та или иная запись. Границей между двумя кластерами является точка, равноудаленная от четырех центров. Из геометрии известно, что множество точек, равноудаленных от двух точек A и B, будут образовывать прямую, перпендикулярную отрезку AB и пересекающую его по середине. Принцип поиска границ будущих кластеров поясняется с помощью рисунке. Для простоты рассматривается 2-мерный случай, когда пространство признаков содержит всего два измерения (X1,X2). Пусть на первом шаге были отобраны три точки A, B и C. Тогда линия 1, проходящая перпендикулярно отрезку AB через его середину, будет состоять из точек, равноудаленных от точек A и B. Аналогично строится прямая 2 для точек A и C, а также прямая 3 для точек B и C.Используя данные линии можно определить, к какому из центров оказывается ближе та или иная точка.
Однако, такая «геометрическая» интерпретация определения того, в «сферу влияния» какого центра кластера входит та или иная запись, полезна только для лучшего понимания. На практике для этого вычисляется расстояние от каждой записи до каждого центра в многомерном пространстве признаков, и выбирается то «семя», для которого данное расстояние минимально (более подробно это рассмотрено ниже).
Например, если в кластер вошли три записи с наборами признаков , то координаты его центроида будут рассчитываться следующим образом:Затем старый центр кластера смещается в его центроид. На рисунке центры тяжести кластеров представлены в виде крестиков.Таким образом, центроиды становятся новыми центрами кластеров для следующей итерации.
Шаги 3 и 4 повторяются до тех пор, пока выполнение алгоритма не будет прервано либо не будет выполнено условие в соответствии с некоторым критерием сходимости.
Остановка алгоритма производится тогда, когда границы кластеров и расположения центроидов не перестанут изменяться от итерации к итерации, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор записей. На практике алгоритм k-means обычно находит набор стабильных кластеров за несколько десятков итераций.
Что касается критерия сходимости, то чаще всего используется критерий суммы квадратов ошибок между центроидом кластера и всеми вошедшими в него записями, т.е.
где - произвольная точка данных, принадлежащая кластеру - центроид данного кластера. Иными словами, алгоритм алгоритм остановится тогда, когда ошибка E достигнет достаточно малого значения.
Одним из основных недостатков, присущих этому алгоритму, является отсутствие четких критериев выбора числа кластеров, целевой функции их инициализации и модификации. Кроме этого, он является очень чувствительным к шумам и аномальным значениям в данных, поскольку они способны значительно повлиять на среднее значение, используемое при вычислении положений центроидов (см. рис. 1-4).
Чтобы снизить влияние таких факторов, как шумы и аномальные значения, иногда на каждой итерации используют не среднее значение признаков, а их медиану. Данная модификация алгоритма называется k-mediods (k-медиан).
Описанный метод используется в программе "Простое формирование маршрутов. Работа с картой. Расчет оптимальных вариантов доставки"
Специальные предложения
См. также
Регистры бухгалтерии. Общая информация 111
05.09.2019 6698 YPermitin 22
"Хочу универсально!" [Часть 1] 65
02.09.2019 4900 SeiOkami 35
Иерархия без "В ИЕРАРХИИ" 117
22.08.2019 4913 ildarovich 16
EnterpriseData – часть 3. Загрузка данных, идентификация объектов 62
22.08.2019 4230 ids79 7
Обработчики событий при записи объектов. Зачем и что за чем? 202
25.07.2019 12801 4 AlbinaAAA 23
Как проводятся документы в типовых конфигурациях от 1С 137
24.07.2019 16075 skv_79 32
FizzBuzz на 1С. Чем короче, тем веселее. Варианты принимаются... 8
24.07.2019 2863 vandalsvq 16
Управление качеством кода 136
22.07.2019 8233 Stepa86 29
Что делает "В ИЕРАРХИИ" в запросе? 94
16.07.2019 8182 YPermitin 34
Создание отчетов с помощью СКД - основные понятия и элементы 208
25.06.2019 20978 ids79 17
Реализуем Стек, Очередь и Приоритетную очередь в 1С 52
24.06.2019 7804 RonX01 63
Организация хранения промежуточных данных 3
29.05.2019 1953 scientes 1
Вычисление 200 тысяч знаков числа pi 73
28.05.2019 3983 Oleg_nsk 93
Регистры накопления. Виртуальные таблицы. Часть №1: Обороты 84
20.05.2019 11069 YPermitin 5
Даем названия переменным: как префиксы экономят наше время 10
06.05.2019 3213 Designer1C 69
Заметки по SQL: Срез последних - аналог запроса 15
15.01.2019 6318 IVC_goal 5
Разработка и сценарное тестирование с Vanessa-ADD. Концепция, теория и сквозной пример создания сценария 222
09.01.2019 27568 Vladimir Litvinenko 69
Многопоточное восстановление последовательностей 41
05.12.2018 7248 _ASZ_ 29
Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С 127
10.11.2018 22245 ids79 40
Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C 147
23.08.2018 22869 Rain88 42
Теорема номер тринадцать 15
15.03.2018 9358 vasilev2015 24
Введение в CI для 1С 87
21.11.2017 19331 real_MaxA 22
Как работает серверный вызов в 1С 459
18.11.2017 44243 pahich 77
#Область ВНЕШНИЕ_ВЫЗОВЫ или MVC в 1С, библиотечность и упрощение интеграции кода 43
12.10.2017 14809 for_sale 58
Групповая разработка конфигураций в крупном холдинге 68
15.08.2017 17545 stas_ganiev 15
Автоматизация процесса 1С-разработки 91
07.06.2017 23029 ekaruk 9
Пишем игру Минер. Обработка событий ActiveX в 1С 29
29.05.2017 12732 user621724_Dimav1979 11
Как я доступ на kb.1c.ru получал 91
01.05.2017 22534 ikekoval 33
Улучшение стандарта "Структура модуля" 6
26.03.2017 12325 o.nikolaev 23
"Распределение в запросе" или "избавляемся от перебора" 185
16.12.2016 28631 alexandersh 48
Планы обмена. Квитировать или гарантировать? 24
12.12.2016 14558 zhichkin 9
Некоторые принципы оптимизации запросов 1С (+SQL) 115
17.11.2016 8898 ture 40
Использование git для доработки типовых конфигураций 1С 230
11.10.2016 188457 pumbaE 31
Оптимизация запросов 1С:Предприятие – от теории к практике 116
07.10.2016 32080 bpc222 20
Регистры сведений 1С. Как это устроено. 729
05.08.2016 151049 Sergey.Noskov 155
Переводим расширения на 8.3.8. Памятка. 79
29.07.2016 39710 mrXoxot 12
Подобие Объектно-ориентированного программирования в 1С (ПООПс) 12
24.07.2016 10916 adam26 54
Опыт практического применения методики BDD на 1С. Написание сценариев 121
03.07.2016 20335 oleynik.dv 132
Заметки про запросы. Последовательность. 110
27.05.2016 29630 vasilev2015 31
Контур.EDI изнутри, или история командной разработки тиражного продукта на 1С 174
17.11.2015 36044 skif47 88
Порядок записи движений регистров при проведении документа 95
13.11.2015 80528 triton_tver 8
Три способа получить дерево элементов иерархического справочника 52
11.11.2015 63125 32ops 9
Распределение суммы по базе 48
08.11.2015 27731 starik-2005 19
Мультиинструментальный Brute Force 4
30.10.2015 10442 scientes 4
1С с "плюсами" 74
14.10.2015 19970 IntelInside 47
Знакомство с технологией Automation-сервер на примерах 33
28.09.2015 26192 niko11s 10
Критерии отбора 83
24.09.2015 49478 niko11s 13
По ссылке или по значению? Ключевое слово Знач и с чем его едят 196
12.08.2015 37186 Evil Beaver 239
Приемы обработки больших данных в 1С 258
07.08.2015 60324 tormozit 27