Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В інформатиці та електротехніці алгоритм Ллойда також відомий як ітерації Вороного чи релаксація. Цей алгоритм названий на честь Стюарта П. Ллойда, який знайшов спосіб знаходження рівномірного розподілу множин точок у підмножини Евклідових просторів і розділення цих підмножин на структуровані опуклі комірки рівномірного розміру. Як і кластеризація методом k-середніх, так і алгоритм Ллойда послідовно знаходять центри кожного набору розподілу, а тоді перерозподіляють вхідні дані відповідно до того, які з цих центрі знаходяться найближче. Відмінність між цими алгоритмами полягає в тому, що вхідними даними для алгоритму Ллойда є неперервна геометрична область, в той час, як для кластеризації методом k-середніх — дискретна множина точок. Тому під час перерозподілу вхідних даних алгоритм Ллойда використовує діаграми Вороного, а не просто визначає найближчий центр до кожної скінченної множини точок, як це відбувається під час кластеризації методом k-середніх.
Хоча даний алгоритм безпосередньо застосовується в Евклідовій площині, схожі алгоритми можна застосовувати та в багатовимірних просторах чи в просторах з неевклідовою метрикою. Алгоритм Ллойда можна використовувати для побудови наближень для центроїдальної мозаїки Вороного вхідних даних, яка, у свою чергу, може бути використана для квантування, згладжування і зображення пунктиром (зернистості). Інше застосування алгоритму Ллойда — згладжування трикутних сіток в методі скінченних елементів.
Опис алгоритму
Алгоритм Ллойда розпочинається введенням на вхід домену деяких k номерів точок. У програмах для згладжування сіток ці точки будуть вершинами сітки, яку треба згладити, в інших програмах ці точки можуть вибиратися навмання або за допомогою перетину узагальненої трикутної сітки необхідного розміру з тією, що є на вході домену.
Тоді повторювано виконуються наступні кроки:
- Утворюється діаграма Вороного для k точок;
- Кожна комірка діаграми Вороного інтегрується і знаходиться її центроїд;
- Тоді кожна точка зміщається до свого центроїда.
Оскільки алгоритм побудови діаграми Вороного може виявитись не тривіальним, особливо у тих випадках, коли вимір сітки на вході більший за два, то кроки обчислення цієї діаграми (схеми) і знаходження центроїд її комірок можна наблизити за допомогою відповідної дискретизації при якій для кожної комірки дрібної сітки, визначається найближчий вузол, після чого центроїда комірки наближено обчислюється за середнім значенням центрів комірок, що належать мережі і є присвоєними до неї. Як альтернатива, можна використовувати метод Монте-Карло, в якому випадкова вибірка точок генерується відповідно до розподілу деяких фіксованих основних імовірностей, присвоєних найближчим точкам, для яких знайдено середнє значення, щоб наближено обчислити центроїди для кожної точки
Збіжність
На кожному кроці релаксації розподіл точок стає кращим, тобто, ті точки, що були розміщені ближче одна до одної, віддаляються, в той час, як ті, що далі одна від одної, зближуються. В одновимірному просторі цей алгоритм, як було показано вище, збігається до центроїдальної діаграми Вороного, також відомої як центроїдальна теселяція Вороного. В багатовимірних (2 і більше) спостерігається слабша збіжність.
Алгоритм збігається повільно або відповідно до обмеження числової точності (може не збігатись взагалі). Саме тому у реальних програмах алгоритм Ллойда зазвичай зупиняється як тільки досягнуто «достатньо хорошого» розподілу. Один із загальноприйнятих критеріїв завершення алгоритму — це зупинка, якщо максимальна відстань, на яку під час ітерації переміщається будь-яка точка, стає меншою за попередньо встановлену межу. Збіжність може бути прискорена через надлишкову релаксацію точок, яка відбувається, якщо перемістити кожну точку на у ω разів більшу відстань, ніж відстань до центру скупчення, зазвичай, користуються значенням ω, меншим за 2.
Застосування
Метод Ллойда був створений для скалярного квантування, але, очевидно, що його можна розширити і для виконання векторного квантування. Розширений метод широко використовується у техніках стискання даних в теорії інформації. Метод Ллойда використовується також у комп'ютерній графіці, так як розподіл, отриманий в результаті його роботи, має характеристики голубого шуму, це означає, що є декілька компонентів з низькою частотою, які можуть інтерпретуватись як артефакти. Він особливо добре підходить для вибору позицій для згладжування. Алгоритм Ллойда також використовується для генерації точкових малюнків в стилі крапкового пунктиру. В такій програмі центроїдам присвоюється значення ваги відповідно до зображення, пунктирну ілюстрацію якого потрібно створити.
У методі скінченних елементів, вхід домену із складними геометричними фігурами розділяється на елементи з простішою формою. Наприклад, для двовимірного випадку (підмножини Евклідової площини чи поверхні у тривимірному просторі) фігури часто поділяються на трикутники. Для збіжності методу скінченних елементів важливо, щоб елементи були правильної форми. У випадку трикутників часто необхідно, щоб елементи були майже рівносторонніми трикутниками. Алгоритм Ллойда можна використати для згладжування згенерованої якимось іншим алгоритмом, переміщуючи їх вершини і змінюючи схему зв'язків між елементами, щоб утворити трикутники, які будуть майже рівносторонніми. Ці програми зазвичай не виконують усі ітерації алгоритму Ллойда і зупиняються до збіжності алгоритму, щоб зберегти деякі особливості сітки, такі як різниця в розмірі елементів у різних частинах сітки. На противагу іншим згладжувальним методам, таким як згладжування Лапласа (при якому вершини сітка переміщуються в середнє положення своїх сусідів), алгоритм Ллойда може змінити топологію сітки, що спричиняє приведення до майже рівносторонніх елементів і уникнення проблем з сплутуванням, що може виникнути при використанні згладжування Лапласа. Проте метод Лапласа є загальнішим, бо може використовуватись і для нетрикутних елементів.
Різні відстані
Зазвичай алгоритм Ллойда використовується в Евклідовому просторі. Евклідова відстань відіграє дві ролі в алгоритмі: вона використовується для задання комірок Вороного, але вона також відповідає за вибір центроїда як представницької точки для кожної комірки, так як центроїд — це точка, що мінімізує піднесену до квадрату середню Евклідову відстань до точок в її комірці. Альтернативні відстані і альтернативні центральні точки (не центроїди) також можуть використовуватись. Наприклад Хаузнер (2001) використав метрику Манхеттена (із змінюваними напрямами), щоб знайти покриття картинки майже квадратними плитками, чия орієнтація збігається з особливостями картинки, яку він використав для симуляції побудови плиткової мозаїки. У цій програмі, окрім зміни метрики, Хаузнер продовжував використовувати центроїди як представницькі точки комірок Вороного. Хоча для метрик, що значно відрізняються від Евклідової було б доречно замість центроїда за представницьку точку обрати мінімізатор піднесених до квадрату середніх значень відстані.
Примітки
- Lloyd, S. (1982-03). . 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici ta elektrotehnici algoritm Llojda takozh vidomij yak iteraciyi Voronogo chi relaksaciya Cej algoritm nazvanij na chest Styuarta P Llojda yakij znajshov sposib znahodzhennya rivnomirnogo rozpodilu mnozhin tochok u pidmnozhini Evklidovih prostoriv i rozdilennya cih pidmnozhin na strukturovani opukli komirki rivnomirnogo rozmiru Yak i klasterizaciya metodom k serednih tak i algoritm Llojda poslidovno znahodyat centri kozhnogo naboru rozpodilu a todi pererozpodilyayut vhidni dani vidpovidno do togo yaki z cih centri znahodyatsya najblizhche Vidminnist mizh cimi algoritmami polyagaye v tomu sho vhidnimi danimi dlya algoritmu Llojda ye neperervna geometrichna oblast v toj chas yak dlya klasterizaciyi metodom k serednih diskretna mnozhina tochok Tomu pid chas pererozpodilu vhidnih danih algoritm Llojda vikoristovuye diagrami Voronogo a ne prosto viznachaye najblizhchij centr do kozhnoyi skinchennoyi mnozhini tochok yak ce vidbuvayetsya pid chas klasterizaciyi metodom k serednih Priklad vikonannya algoritmu Llojda Dlya kozhnoyi iteraciyi pokazana diagrama Voronogo dlya potochnih tochok Znakom plyus pokazani centroyidi klitin Iteraciya 1Iteraciya 2Iteraciya 3Iteraciya 15Na ostannomu zobrazhenni tochki znahodyatsya duzhe blizko do centroyidiv klitin Voronogo Centroyidalna tesselyaciya Voronogo bula znajdena Hocha danij algoritm bezposeredno zastosovuyetsya v Evklidovij ploshini shozhi algoritmi mozhna zastosovuvati ta v bagatovimirnih prostorah chi v prostorah z neevklidovoyu metrikoyu Algoritm Llojda mozhna vikoristovuvati dlya pobudovi nablizhen dlya centroyidalnoyi mozayiki Voronogo vhidnih danih yaka u svoyu chergu mozhe buti vikoristana dlya kvantuvannya zgladzhuvannya i zobrazhennya punktirom zernistosti Inshe zastosuvannya algoritmu Llojda zgladzhuvannya trikutnih sitok v metodi skinchennih elementiv Opis algoritmuAlgoritm Llojda rozpochinayetsya vvedennyam na vhid domenu deyakih k nomeriv tochok U programah dlya zgladzhuvannya sitok ci tochki budut vershinami sitki yaku treba zgladiti v inshih programah ci tochki mozhut vibiratisya navmannya abo za dopomogoyu peretinu uzagalnenoyi trikutnoyi sitki neobhidnogo rozmiru z tiyeyu sho ye na vhodi domenu Todi povtoryuvano vikonuyutsya nastupni kroki Utvoryuyetsya diagrama Voronogo dlya k tochok Kozhna komirka diagrami Voronogo integruyetsya i znahoditsya yiyi centroyid Todi kozhna tochka zmishayetsya do svogo centroyida Oskilki algoritm pobudovi diagrami Voronogo mozhe viyavitis ne trivialnim osoblivo u tih vipadkah koli vimir sitki na vhodi bilshij za dva to kroki obchislennya ciyeyi diagrami shemi i znahodzhennya centroyid yiyi komirok mozhna nabliziti za dopomogoyu vidpovidnoyi diskretizaciyi pri yakij dlya kozhnoyi komirki dribnoyi sitki viznachayetsya najblizhchij vuzol pislya chogo centroyida komirki nablizheno obchislyuyetsya za serednim znachennyam centriv komirok sho nalezhat merezhi i ye prisvoyenimi do neyi Yak alternativa mozhna vikoristovuvati metod Monte Karlo v yakomu vipadkova vibirka tochok generuyetsya vidpovidno do rozpodilu deyakih fiksovanih osnovnih imovirnostej prisvoyenih najblizhchim tochkam dlya yakih znajdeno serednye znachennya shob nablizheno obchisliti centroyidi dlya kozhnoyi tochkiZbizhnistNa kozhnomu kroci relaksaciyi rozpodil tochok staye krashim tobto ti tochki sho buli rozmisheni blizhche odna do odnoyi viddalyayutsya v toj chas yak ti sho dali odna vid odnoyi zblizhuyutsya V odnovimirnomu prostori cej algoritm yak bulo pokazano vishe zbigayetsya do centroyidalnoyi diagrami Voronogo takozh vidomoyi yak centroyidalna teselyaciya Voronogo V bagatovimirnih 2 i bilshe sposterigayetsya slabsha zbizhnist Algoritm zbigayetsya povilno abo vidpovidno do obmezhennya chislovoyi tochnosti mozhe ne zbigatis vzagali Same tomu u realnih programah algoritm Llojda zazvichaj zupinyayetsya yak tilki dosyagnuto dostatno horoshogo rozpodilu Odin iz zagalnoprijnyatih kriteriyiv zavershennya algoritmu ce zupinka yaksho maksimalna vidstan na yaku pid chas iteraciyi peremishayetsya bud yaka tochka staye menshoyu za poperedno vstanovlenu mezhu Zbizhnist mozhe buti priskorena cherez nadlishkovu relaksaciyu tochok yaka vidbuvayetsya yaksho peremistiti kozhnu tochku na u w raziv bilshu vidstan nizh vidstan do centru skupchennya zazvichaj koristuyutsya znachennyam w menshim za 2 ZastosuvannyaMetod Llojda buv stvorenij dlya skalyarnogo kvantuvannya ale ochevidno sho jogo mozhna rozshiriti i dlya vikonannya vektornogo kvantuvannya Rozshirenij metod shiroko vikoristovuyetsya u tehnikah stiskannya danih v teoriyi informaciyi Metod Llojda vikoristovuyetsya takozh u komp yuternij grafici tak yak rozpodil otrimanij v rezultati jogo roboti maye harakteristiki golubogo shumu ce oznachaye sho ye dekilka komponentiv z nizkoyu chastotoyu yaki mozhut interpretuvatis yak artefakti Vin osoblivo dobre pidhodit dlya viboru pozicij dlya zgladzhuvannya Algoritm Llojda takozh vikoristovuyetsya dlya generaciyi tochkovih malyunkiv v stili krapkovogo punktiru V takij programi centroyidam prisvoyuyetsya znachennya vagi vidpovidno do zobrazhennya punktirnu ilyustraciyu yakogo potribno stvoriti U metodi skinchennih elementiv vhid domenu iz skladnimi geometrichnimi figurami rozdilyayetsya na elementi z prostishoyu formoyu Napriklad dlya dvovimirnogo vipadku pidmnozhini Evklidovoyi ploshini chi poverhni u trivimirnomu prostori figuri chasto podilyayutsya na trikutniki Dlya zbizhnosti metodu skinchennih elementiv vazhlivo shob elementi buli pravilnoyi formi U vipadku trikutnikiv chasto neobhidno shob elementi buli majzhe rivnostoronnimi trikutnikami Algoritm Llojda mozhna vikoristati dlya zgladzhuvannya zgenerovanoyi yakimos inshim algoritmom peremishuyuchi yih vershini i zminyuyuchi shemu zv yazkiv mizh elementami shob utvoriti trikutniki yaki budut majzhe rivnostoronnimi Ci programi zazvichaj ne vikonuyut usi iteraciyi algoritmu Llojda i zupinyayutsya do zbizhnosti algoritmu shob zberegti deyaki osoblivosti sitki taki yak riznicya v rozmiri elementiv u riznih chastinah sitki Na protivagu inshim zgladzhuvalnim metodam takim yak zgladzhuvannya Laplasa pri yakomu vershini sitka peremishuyutsya v serednye polozhennya svoyih susidiv algoritm Llojda mozhe zminiti topologiyu sitki sho sprichinyaye privedennya do majzhe rivnostoronnih elementiv i uniknennya problem z splutuvannyam sho mozhe viniknuti pri vikoristanni zgladzhuvannya Laplasa Prote metod Laplasa ye zagalnishim bo mozhe vikoristovuvatis i dlya netrikutnih elementiv Rizni vidstaniZazvichaj algoritm Llojda vikoristovuyetsya v Evklidovomu prostori Evklidova vidstan vidigraye dvi roli v algoritmi vona vikoristovuyetsya dlya zadannya komirok Voronogo ale vona takozh vidpovidaye za vibir centroyida yak predstavnickoyi tochki dlya kozhnoyi komirki tak yak centroyid ce tochka sho minimizuye pidnesenu do kvadratu serednyu Evklidovu vidstan do tochok v yiyi komirci Alternativni vidstani i alternativni centralni tochki ne centroyidi takozh mozhut vikoristovuvatis Napriklad Hauzner 2001 vikoristav metriku Manhettena iz zminyuvanimi napryamami shob znajti pokrittya kartinki majzhe kvadratnimi plitkami chiya oriyentaciya zbigayetsya z osoblivostyami kartinki yaku vin vikoristav dlya simulyaciyi pobudovi plitkovoyi mozayiki U cij programi okrim zmini metriki Hauzner prodovzhuvav vikoristovuvati centroyidi yak predstavnicki tochki komirok Voronogo Hocha dlya metrik sho znachno vidriznyayutsya vid Evklidovoyi bulo b dorechno zamist centroyida za predstavnicku tochku obrati minimizator pidnesenih do kvadratu serednih znachen vidstani PrimitkiLloyd S 1982 03 IEEE Transactions on Information Theory T 28 2 s 129 137 doi 10 1109 TIT 1982 1056489 ISSN 1557 9654 Arhiv originalu za 19 sichnya 2022 Procitovano 19 sichnya 2022 PORIVNYaNNYa YaKOSTI TA ShVIDKOSTI KLASTERIZACIYi ALGORITMOM LLOJDA ZALE webcache googleusercontent com Procitovano 19 sichnya 2022