Алгоритм Ллойда
В інформатиці та електротехніці алгоритм Ллойда також відомий як ітерації Вороного чи релаксація. Цей алгоритм названий на честь Стюарта П. Ллойда, який знайшов спосіб знаходження рівномірного розподілу множин точок у підмножини Евклідових просторів і розділення цих підмножин на структуровані опуклі комірки рівномірного розміру. [1] Як і кластеризація методом k-середніх, так і алгоритм Ллойда послідовно знаходять центри кожного набору розподілу, а тоді перерозподіляють вхідні дані відповідно до того, які з цих центрі знаходяться найближче. Відмінність між цими алгоритмами полягає в тому, що вхідними даними для алгоритму Ллойда є неперервна геометрична область, в той час, як для кластеризації методом k-середніх — дискретна множина точок. Тому під час перерозподілу вхідних даних алгоритм Ллойда використовує діаграми Вороного, а не просто визначає найближчий центр до кожної скінченної множини точок, як це відбувається під час кластеризації методом k-середніх.
Хоча даний алгоритм безпосередньо застосовується в Евклідовій площині, схожі алгоритми можна застосовувати та в багатовимірних просторах чи в просторах з неевклідовою метрикою. Алгоритм Ллойда можна використовувати для побудови наближень для центроїдальної мозаїки Вороного вхідних даних, яка, у свою чергу, може бути використана для квантування, згладжування і зображення пунктиром (зернистості). Інше застосування алгоритму Ллойда — згладжування трикутних сіток в методі скінченних елементів.
Опис алгоритму[ред. | ред. код]
Алгоритм Ллойда розпочинається введенням на вхід домену деяких k номерів точок. [2] У програмах для згладжування сіток ці точки будуть вершинами сітки, яку треба згладити, в інших програмах ці точки можуть вибиратися навмання або за допомогою перетину узагальненої трикутної сітки необхідного розміру з тією, що є на вході домену.
Тоді повторювано виконуються наступні кроки:
- Утворюється діаграма Вороного для k точок;
- Кожна комірка діаграми Вороного інтегрується і знаходиться її центроїд;
- Тоді кожна точка зміщається до свого центроїда.
Оскільки алгоритм побудови діаграми Вороного може виявитись не тривіальним, особливо у тих випадках, коли вимір сітки на вході більший за два, то кроки обчислення цієї діаграми (схеми) і знаходження центроїд її комірок можна наблизити за допомогою відповідної дискретизації при якій для кожної комірки дрібної сітки, визначається найближчий вузол, після чого центроїда комірки наближено обчислюється за середнім значенням центрів комірок, що належать мережі і є присвоєними до неї. Як альтернатива, можна використовувати метод Монте-Карло, в якому випадкова вибірка точок генерується відповідно до розподілу деяких фіксованих основних імовірностей, присвоєних найближчим точкам, для яких знайдено середнє значення, щоб наближено обчислити центроїди для кожної точки
Збіжність[ред. | ред. код]
На кожному кроці релаксації розподіл точок стає кращим, тобто, ті точки, що були розміщені ближче одна до одної, віддаляються, в той час, як ті, що далі одна від одної, зближуються. В одновимірному просторі цей алгоритм, як було показано вище, збігається до центроїдальної діаграми Вороного, також відомої як центроїдальна теселяція Вороного. В багатовимірних (2 і більше) спостерігається слабша збіжність.
Алгоритм збігається повільно або відповідно до обмеження числової точності (може не збігатись взагалі). Саме тому у реальних програмах алгоритм Ллойда зазвичай зупиняється як тільки досягнуто «достатньо хорошого» розподілу. Один із загальноприйнятих критеріїв завершення алгоритму — це зупинка, якщо максимальна відстань, на яку під час ітерації переміщається будь-яка точка, стає меншою за попередньо встановлену межу. Збіжність може бути прискорена через надлишкову релаксацію точок, яка відбувається, якщо перемістити кожну точку на у ω разів більшу відстань, ніж відстань до центру скупчення, зазвичай, користуються значенням ω, меншим за 2.
Застосування[ред. | ред. код]
Метод Ллойда був створений для скалярного квантування, але, очевидно, що його можна розширити і для виконання векторного квантування. Розширений метод широко використовується у техніках стискання даних в теорії інформації. Метод Ллойда використовується також у комп'ютерній графіці, так як розподіл, отриманий в результаті його роботи, має характеристики голубого шуму, це означає, що є декілька компонентів з низькою частотою, які можуть інтерпретуватись як артефакти. Він особливо добре підходить для вибору позицій для згладжування. Алгоритм Ллойда також використовується для генерації точкових малюнків в стилі крапкового пунктиру. В такій програмі центроїдам присвоюється значення ваги відповідно до зображення, пунктирну ілюстрацію якого потрібно створити.
У методі скінченних елементів, вхід домену із складними геометричними фігурами розділяється на елементи з простішою формою. Наприклад, для двовимірного випадку (підмножини Евклідової площини чи поверхні у тривимірному просторі) фігури часто поділяються на трикутники. Для збіжності методу скінченних елементів важливо, щоб елементи були правильної форми. У випадку трикутників часто необхідно, щоб елементи були майже рівносторонніми трикутниками. Алгоритм Ллойда можна використати для згладжування згенерованої якимось іншим алгоритмом, переміщуючи їх вершини і змінюючи схему зв'язків між елементами, щоб утворити трикутники, які будуть майже рівносторонніми. Ці програми зазвичай не виконують усі ітерації алгоритму Ллойда і зупиняються до збіжності алгоритму, щоб зберегти деякі особливості сітки, такі як різниця в розмірі елементів у різних частинах сітки. На противагу іншим згладжувальним методам, таким як згладжування Лапласа (при якому вершини сітка переміщуються в середнє положення своїх сусідів), алгоритм Ллойда може змінити топологію сітки, що спричиняє приведення до майже рівносторонніх елементів і уникнення проблем з сплутуванням, що може виникнути при використанні згладжування Лапласа. Проте метод Лапласа є загальнішим, бо може використовуватись і для нетрикутних елементів.
Різні відстані[ред. | ред. код]
Зазвичай алгоритм Ллойда використовується в Евклідовому просторі. Евклідова відстань відіграє дві ролі в алгоритмі: вона використовується для задання комірок Вороного, але вона також відповідає за вибір центроїда як представницької точки для кожної комірки, так як центроїд — це точка, що мінімізує піднесену до квадрату середню Евклідову відстань до точок в її комірці. Альтернативні відстані і альтернативні центральні точки (не центроїди) також можуть використовуватись. Наприклад Хаузнер (2001) використав метрику Манхеттена (із змінюваними напрямами), щоб знайти покриття картинки майже квадратними плитками, чия орієнтація збігається з особливостями картинки, яку він використав для симуляції побудови плиткової мозаїки. У цій програмі, окрім зміни метрики, Хаузнер продовжував використовувати центроїди як представницькі точки комірок Вороного. Хоча для метрик, що значно відрізняються від Евклідової було б доречно замість центроїда за представницьку точку обрати мінімізатор піднесених до квадрату середніх значень відстані.
Примітки[ред. | ред. код]
- ↑ Lloyd, S. (1982-03). Least squares quantization in PCM. IEEE Transactions on Information Theory. Т. 28, № 2. с. 129—137. doi:10.1109/TIT.1982.1056489. ISSN 1557-9654. Архів оригіналу за 19 січня 2022. Процитовано 19 січня 2022.
- ↑ ПОРІВНЯННЯ ЯКОСТІ ТА ШВИДКОСТІ КЛАСТЕРИЗАЦІЇ АЛГОРИТМОМ ЛЛОЙДА ЗАЛЕ. webcache.googleusercontent.com. Процитовано 19 січня 2022.