Оптимізація планування доставки вантажів

Подивіться на фото.. так виглядає бардак.. після того, як дочка пограла і кинула на підлозі у своїй кімнаті речі. Побачивши таке неподобство, їй тут же прилітає завдання прибратися в кімнаті, а це означає, що їй потрібно зробити кластеризацію речей за ознакою, тобто іграшки віднести в одну групу, книжки-в іншу, а олівці в третю і т.д., щоб потім прибрати все на свої місця.

Ознака, за якою ми збираємо одні предмети в одну групу, інші в іншу, називається метрикою. Грубо кажучи, метрика це просто спосіб відокремити один предмет від іншого. Найпоширеніший варіант – це коли метрикою є відстань. Кластеризація (розподіл на кластери) може бути і трохи іншою. Наприклад, якщо поставити завдання розділити всі речі на чотири купи (кластери), то при цьому, напевно, іграшки потраплять в одну купу з книжками або олівцями, тобто перемішаються. Такий метод називається алгоритм кластеризації К-середніх, тобто ми заздалегідь задаємо кількість кластерів, а алгоритм сам поділяє об'єкти на цю кількість.

У свій час були книжки із серії "для чайників", і там по-простому говорилося про "складні матерії". Спробую пояснити, як працює сам алгоритм кластеризації. Він ітераційний, тобто повторюється кілька разів, поки не зійдеться. Збіжність у разі означає, що з кожною ітерацією (повторенням обчислень) ми дедалі точніше наближаємося до правильної відповіді. А «зійшовся» в даному випадку означає, що ми знайшли правильну відповідь або ми дуже близько до неї (тобто знайшлося число з невеликою похибкою, на яку ми плюємо та топчемо ногами).

В даному випадку ми будемо працювати з точками наплощині розміром 20 на 20 (не важливо навіть якихось одиниць). Наприклад, дано 50 точок, розташованих випадковим чином. Потрібно розподілити ці точки за кластерами алгоритмом К-середніх (або K-means).

Спочатку випадково виставляємо на цій же площині кілька центрів кластерів, наприклад 4. Центр кластера називається центроїдом. Без початкового становища центроїдів не вдасться запустити алгоритм (побачите, чому). Як їх розставити - справа ваша, можна самостійно вводити координати, можна застосувати ще якийсь алгоритм. Далі починається обчислення кластерів у циклі. Робиться це так:

Спочатку ми «прив'язуємо» кожну точку до того центроїду, якого вона ближче, т.к. Центр є центром кластера, то можна сказати, що ми відносимо кожну точку до того кластера, до центру якого вона ближче.
Коли всі точки прив'язані і жодна від нас не втекла, треба перерахувати координати центроїдів. Для цього подумки вписуємо весь кластер у прямокутник і ставимо центроїд туди, де перетнуться його діагоналі (у середину, коротше). Квадратики – це центри кластерів. Лінії від точок до центрів потрібні просто для наочності, щоб бачити, до якого центру належить точка.
Повторюємо для нового центру дії з кроку 1 доти, доки центроїди не перестануть змінювати своє становище. Якщо вони перестали змінювати становище, то алгоритм зійшовся і ми тепер круті перці. До речі, зазвичай алгоритм сходиться десь за 2-6 ітерацій. Але в теорії можливо, що алгоритм не зійдеться взагалі, тому про всяк випадок потрібно включити в нього «захист» - перервати його після 30 ітерацій. Це гарантує, що програма не зависне.

Тепер для тих, хто таки дістався цього місця і не втік, наведу більшеСуворий математичний опис методу та приклад розрахунку.

Опис алгоритму кластеризації

Для вибірки даних, що містить n записів (об'єктів), задається число кластерів k, яке має бути сформовано. Потім алгоритм розбиває всі об'єкти вибірки на k розділів (k

Одним із найпростіших та найефективніших алгоритмів кластеризації є алгоритм k-means (Mac-Queen, 1967) або в українськомовному варіанті k-середніх (від англ. mean – середнє значення). Він складається з чотирьох кроків, але спочатку виникає число кластерів k, яке має бути сформоване з об'єктів вихідної вибірки.

1. Випадковим чином вибирається k записів вихідної вибірки, які будуть початковими центрами кластерівμ. Такі початкові точки, у тому числі потім «виростає» кластер, часто називають «насінням» (від англ. seeds – насіння, посіви). Кожна така запис буде свого роду «ембріон» кластера, що складається лише з одного елемента.

2. Для кожного центру вирахувати відстані до всіх точок

Ключовим моментом алгоритму k-means є обчислення кожної ітерації відстані між записами і центрами кластерів, що необхідно визначення, якого з кластерів належить цей запис. Правило, яким виробляється обчислення відстані в багатовимірному просторі ознак, називається метрикою. Найчастіше у практичних завданнях кластеризації використовуються такі метрики.

де - Набори (вектори) значень ознак двох записів.

Оскільки безліч точок, рівновіддалених від деякого центру при використанні евклідової метрики утворюватиме сферу (або коло у двовимірному випадку), то і кластери, отримані з використанням евклідової відстані, також матимуть форму, близьку досферичної.

Відстань Манхеттена (англ.: Manhattan distance)або метрика L1

Фактично це найкоротша відстань між двома точками, пройдена лініями, паралельним осям координатної системи (див рис. нижче).

Перевага метрики L1 у тому, що її використання дозволяє знизити вплив аномальних значень працювати алгоритмів. Кластери, побудовані з урахуванням відстані Манхеттена, прагнуть кубічної формі. Іноді відстань Манхеттена називають «відстань міських кварталів» (англ. city-block distance), через асоціації, що виникають з прямокутними формами забудови, яка характерна для сучасних міст.

Використовуючи дані лінії, можна визначити, до якого з центрів виявляється ближче та чи інша точка.

Проте така «геометрична» інтерпретація визначення того, до «сфери впливу» якого центру кластера входить той чи інший запис, корисний лише для кращого розуміння. На практиці для цього обчислюється відстань від кожного запису до кожного центру в багатовимірному просторі ознак, і вибирається те «насіння», для якого ця відстань мінімальна (докладніше це розглянуто нижче).

Кроки 3 і 4 повторюються до тих пір, поки виконання алгоритму не буде перервано або не буде виконано умову відповідно до деякого критерію збіжності.

Зупинка алгоритму проводиться тоді, коли межі кластерів та розташування центроїдів не перестануть змінюватися від ітерації до ітерації, тобто. на кожній ітерації в кожному кластері залишатиметься той самий набір записів. Насправді алгоритм k-means зазвичай знаходить набір стабільних кластерів кілька десятків ітерацій.

Що стосується критерію збіжності, то частішевсього використовується критерій суми квадратів помилок між центроїдом кластера і всіма записами, що увійшли до нього, тобто.

де – довільна точка даних, що належить кластеру – центроїд даного кластера. Інакше кажучи, алгоритм алгоритм зупиниться тоді, коли помилка E досягне досить малого значення.

Одним із основних недоліків, властивих цьому алгоритму, є відсутність чітких критеріїв вибору числа кластерів, цільової функції їхньої ініціалізації та модифікації. Крім цього, він є дуже чутливим до шумів та аномальних значень даних, оскільки вони здатні значно вплинути на середнє значення, що використовується при обчисленні положень центроїдів (див. рис. 1-4).

Щоб знизити вплив таких чинників, як шуми і аномальні значення, іноді кожної ітерації використовують середнє значення ознак, які медіану. Ця модифікація алгоритму називається k-mediods (k-медіан).