Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

OPTICS англ Ordering points to identify the clustering structure алгоритм знаходження кластерів у просторових даних на о

OPTICS

OPTICS

OPTICS (англ. Ordering points to identify the clustering structure) — алгоритм знаходження кластерів у просторових даних на основі щільності. Він був представлений Міхаелем Анкерстом, Маркусом Брюінгом, Хансом Крігелем і Йоргом Сандером. Його основна ідея схожа на DBSCAN, але він вирішує одну з основних слабостей DBSCAN: проблему визначення значущих кластерів в наборах даних різної щільності. Для цього об'єкти бази даних повинні бути впорядковані (лінійно) так, що об'єкти, які просторово близькі, будуть сусідами в упорядкуванні. Крім того, спеціальна відстань зберігається для кожної точки, яка являє собою щільність, яка повинна бути прийнятна для кластера, щоб мати обидві сусідні точки належали до тієї ж групи. Як це представлено в дендрограмі.

Ідея

Як і DBSCAN, OPTICS вимагає двох параметрів: image, що є максимальною відстанню (радіусом) і image, що показує мінімальну кількість об'єктів, необхідних для формування кластера. Точка (об'єкт) image є ядром, якщо хоча б image точок (об'єктів) знаходяться в межах image-відстані image. Всупереч DBSCAN, OPTICS також розглядає об'єкти, які є частиною більш «щільних» кластерів, так, щоб кожна точка була присвоєна основній відстані до imageth її найближчої точки:

image image

Досяжність до об'єкта image від об'єкта image знаходиться, як відстань між image і image, або, як основна відстань від image:

image image

Якщо image і image є найближчими сусідами, тобто image ми повинні припускати, що image і image належать до одного кластеру.

Обидва значення основної відстані і досяжності є невідомими, якщо недоступний кластер достатньої щільності (w.r.t. image). Якщо взяти велике значення image, то цього не станеться, проте тоді кожен запит image-сусідів може повертати навіть всю базу даних, що приведе до складності виконання image. Отже, параметр image потрібно вибрати, враховуючи щільність кластерів, які не представляють інтересу, щоб пришвидшити час виконання алгоритму.

Строго кажучи, параметр image не є необхідним. Він можу бути просто встановленим максимально можливого значення.

Псевдокод

Базова реалізація OPTICS схожа до реалізації DBSCAN, але використовується не множина відомих, але не кластеризованих даних, a черга з пріоритетом (з використанням індексації heap).

OPTICS(DB, eps, MinPts) 

 for each point p of DB p.reachability-distance = UNDEFINED for each unprocessed point p of DB N = getNeighbors(p, eps) mark p as processed output p to the ordered list if (core-distance(p, eps, Minpts) != UNDEFINED) Seeds = empty priority queue update(N, p, Seeds, eps, Minpts) for each next q in Seeds N' = getNeighbors(q, eps) mark q as processed output q to the ordered list if (core-distance(q, eps, Minpts) != UNDEFINED) update(N', q, Seeds, eps, Minpts)


В update(), черга з пріоритетом Seeds заповнена image-сусідами image і image, відповідно: 

 update(N, p, Seeds, eps, Minpts) coredist = core-distance(p, eps, MinPts) for each o in N if (o is not processed) new-reach-dist = max(coredist, dist(p,o)) if (o.reachability-distance == UNDEFINED) // o is not in Seeds o.reachability-distance = new-reach-dist Seeds.insert(o, new-reach-dist) else // o in Seeds, check for improvement if (new-reach-dist < o.reachability-distance) o.reachability-distance = new-reach-dist Seeds.move-up(o, new-reach-dist)

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

Визначення кластерів

image

Використовуючи графік досяжності (спеціальний вид дендрограми), легко отримати ієрархічну структуру кластерів. Це 2D графік, з упорядкуванням точок, оброблених OPTICS на осі Ох, а відстань досяжності на осі Oy. Так, як точки, що належать до одного кластера мають низьку досяжність для найближчих сусідів, кластери показують ділянки досяжності. Чим глибша ділянка, тим щільніший кластер.

Зображення вище ілюструє цю концепцію. У верхній лівій частині, показано штучний набір даних. Верхня права частина візуалізує сполучне дерево, створене за допомогою OPTICS, і нижня частина показує ділянку досяжності, обчислену OPTICS. Виявлення кластерів з допомогою цього графіку може бути зроблене вручну, вибравши діапазон на осі Ох після візуального огляду, вибравши поріг на осі Оу (результат буде схожий на результат DBSCAN кластеризації з тими ж image і minPts параметри, тут значення 0,1 може дати добрі результати), або за допомогою різних алгоритмів, які намагаються виявити ділянки, використовуючи крутизну, виявлення коліна або локальні максимуми. Кластери, отримані таким чином можуть мати ієрархічну структуру, чого не може бути досягнуто за допомогою DBSCAN.

Складність

OPTICS проходить кожну точку один раз, при цьому вираховує image-найближчих сусідів для кожної. Враховуючи використання просторового індексу, що повертає запит на сусідів в час image runtime, загальна складність алгоритму буде image.Автори оригінального OPTICS повідомили, що фактичний константний коефіцієнт уповільнення буде 1.6 в порівнянні з DBSCAN. Варто зауважити, що image може мати великий вплив на час виконання алгоритму, бо його велике значення може збільшувати складність запиту на найближчих сусідів до лінійної.

Вибір image (більшим, ніж максимальна відстань між даними в наборі даних) is але приведе до квадратичної складності алгоритму. Ось, чому image потрібно вибирати під кожен набір даних окремо.

Розширення

  • OPTICS-OF це алгоритм визначення аномалій, який базується на OPTICS. Це знаходження викидів в даному алгоритмі OPTICS, з затратами меншими, ніж за допомогою інших алгоритмів виявлення аномалій.
  • DeLi-Clu, (англ. Density-Link-Clustering) поєднує ідею однозв'язної кластеризація і OPTICS, усуваючи параметр image, покращуючи час виконання OPTICS.
  • HiSC метод ієрархічної кластеризації підпростору (паралельно осі), на основі OPTICS.
  • HiCO
  • DiSH — це покращення HiSC, з допомогою якого можна знаходити складніші ієрархії.
  • FOPTICS — це швидша реалізація з використанням випадкових проєкцій.

Реалізація

Реалізація OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO і DiSH доступна в фреймворку (з підтримкою індексів). Також, неповна і повільна імплементація доступна в розширеннях Weka. MRC (англ. The National Institute for Medical Research) забезпечує реалізацію без підтримки індексів.

Посилання

  1. Mihael Ankerst, Markus M. Breunig, , Jörg Sander (1999). . ACM SIGMOD international conference on Management of data. . с. 49—60. Архів оригіналу за 7 жовтня 2012. Процитовано 2 червня 2015.
  2. Martin Ester, , Jörg Sander, Xiaowei Xu (1996). Evangelos Simoudis, Jiawei Han, Usama M. Fayyad (ред.). . Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). . с. 226—231. ISBN . Архів оригіналу за 2 травня 2011. Процитовано 2 червня 2015.
  3. Markus M. Breunig, , Raymond T. Ng and Jörg Sander (1999). OPTICS-OF: Identifying Local Outliers. Principles of Data Mining and Knowledge Discovery. Springer-Verlag. с. 262—270. doi:10.1007/b72280. ISBN .
  4. DOI:10.1007/11731139_16
    Нема шаблону {{}}.заповнити вручну
  5. DOI:10.1007/11871637_42
    Нема шаблону {{}}.заповнити вручну
  6. DOI:10.1109/SSDBM.2006.35
    Нема шаблону {{}}.заповнити вручну
  7. DOI:10.1007/978-3-540-71703-4_15
    Нема шаблону {{}}.заповнити вручну
  8. DOI:10.1145/2505515.2505590
    Нема шаблону {{}}.заповнити вручну

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

OPTICS angl Ordering points to identify the clustering structure algoritm znahodzhennya klasteriv u prostorovih danih na osnovi shilnosti Vin buv predstavlenij Mihaelem Ankerstom Markusom Bryuingom Hansom Krigelem i Jorgom Sanderom Jogo osnovna ideya shozha na DBSCAN ale vin virishuye odnu z osnovnih slabostej DBSCAN problemu viznachennya znachushih klasteriv v naborah danih riznoyi shilnosti Dlya cogo ob yekti bazi danih povinni buti vporyadkovani linijno tak sho ob yekti yaki prostorovo blizki budut susidami v uporyadkuvanni Krim togo specialna vidstan zberigayetsya dlya kozhnoyi tochki yaka yavlyaye soboyu shilnist yaka povinna buti prijnyatna dlya klastera shob mati obidvi susidni tochki nalezhali do tiyeyi zh grupi Yak ce predstavleno v dendrogrami IdeyaYak i DBSCAN OPTICS vimagaye dvoh parametriv e displaystyle varepsilon sho ye maksimalnoyu vidstannyu radiusom i MinPts displaystyle MinPts sho pokazuye minimalnu kilkist ob yektiv neobhidnih dlya formuvannya klastera Tochka ob yekt p displaystyle p ye yadrom yaksho hocha b MinPts displaystyle MinPts tochok ob yektiv znahodyatsya v mezhah e displaystyle varepsilon vidstani Ne p displaystyle N varepsilon p Vsuperech DBSCAN OPTICS takozh rozglyadaye ob yekti yaki ye chastinoyu bilsh shilnih klasteriv tak shob kozhna tochka bula prisvoyena osnovnij vidstani do MinPts displaystyle MinPts th yiyi najblizhchoyi tochki core diste MinPts p displaystyle text core dist varepsilon MinPts p UNDEFINEDif Ne p lt MinPtsMinPts th smallest distance to Ne p otherwise displaystyle begin cases text UNDEFINED amp text if N varepsilon p lt MinPts MinPts text th smallest distance to N varepsilon p amp text otherwise end cases Dosyazhnist do ob yekta o displaystyle o vid ob yekta p displaystyle p znahoditsya yak vidstan mizh o displaystyle o i p displaystyle p abo yak osnovna vidstan vid p displaystyle p reachability diste MinPts o p displaystyle text reachability dist varepsilon MinPts o p UNDEFINEDif Ne p lt MinPtsmax core diste MinPts p dist p o otherwise displaystyle begin cases text UNDEFINED amp text if N varepsilon p lt MinPts max text core dist varepsilon MinPts p text dist p o amp text otherwise end cases Yaksho p displaystyle p i o displaystyle o ye najblizhchimi susidami tobto e lt e displaystyle varepsilon lt varepsilon mi povinni pripuskati sho p displaystyle p i o displaystyle o nalezhat do odnogo klasteru Obidva znachennya osnovnoyi vidstani i dosyazhnosti ye nevidomimi yaksho nedostupnij klaster dostatnoyi shilnosti w r t e displaystyle varepsilon Yaksho vzyati velike znachennya e displaystyle varepsilon to cogo ne stanetsya prote todi kozhen zapit e displaystyle varepsilon susidiv mozhe povertati navit vsyu bazu danih sho privede do skladnosti vikonannya O n2 displaystyle O n 2 Otzhe parametr e displaystyle varepsilon potribno vibrati vrahovuyuchi shilnist klasteriv yaki ne predstavlyayut interesu shob prishvidshiti chas vikonannya algoritmu Strogo kazhuchi parametr e displaystyle varepsilon ne ye neobhidnim Vin mozhu buti prosto vstanovlenim maksimalno mozhlivogo znachennya PsevdokodBazova realizaciya OPTICS shozha do realizaciyi DBSCAN ale vikoristovuyetsya ne mnozhina vidomih ale ne klasterizovanih danih a cherga z prioritetom z vikoristannyam indeksaciyi heap OPTICS DB eps MinPts for each point p of DB p reachability distance UNDEFINED for each unprocessed point p of DB N getNeighbors p eps mark p as processed output p to the ordered list if core distance p eps Minpts UNDEFINED Seeds empty priority queue update N p Seeds eps Minpts for each next q in Seeds N getNeighbors q eps mark q as processed output q to the ordered list if core distance q eps Minpts UNDEFINED update N q Seeds eps Minpts V update cherga z prioritetom Seeds zapovnena e displaystyle varepsilon susidami p displaystyle p i q displaystyle q vidpovidno update N p Seeds eps Minpts coredist core distance p eps MinPts for each o in N if o is not processed new reach dist max coredist dist p o if o reachability distance UNDEFINED o is not in Seeds o reachability distance new reach dist Seeds insert o new reach dist else o in Seeds check for improvement if new reach dist lt o reachability distance o reachability distance new reach dist Seeds move up o new reach dist Otzhe OPTICS vidaye ob yekti tochki v pevnomu poryadku anotovanih z yih najmenshoyu dosyazhnistyu v originalnomu algoritmi osnovna vidstan tezh vrahovuyetsya ale ce ne potribno dlya podalshoyi obrobki Viznachennya klasterivVikoristovuyuchi grafik dosyazhnosti specialnij vid dendrogrami legko otrimati iyerarhichnu strukturu klasteriv Ce 2D grafik z uporyadkuvannyam tochok obroblenih OPTICS na osi Oh a vidstan dosyazhnosti na osi Oy Tak yak tochki sho nalezhat do odnogo klastera mayut nizku dosyazhnist dlya najblizhchih susidiv klasteri pokazuyut dilyanki dosyazhnosti Chim glibsha dilyanka tim shilnishij klaster Zobrazhennya vishe ilyustruye cyu koncepciyu U verhnij livij chastini pokazano shtuchnij nabir danih Verhnya prava chastina vizualizuye spoluchne derevo stvorene za dopomogoyu OPTICS i nizhnya chastina pokazuye dilyanku dosyazhnosti obchislenu OPTICS Viyavlennya klasteriv z dopomogoyu cogo grafiku mozhe buti zroblene vruchnu vibravshi diapazon na osi Oh pislya vizualnogo oglyadu vibravshi porig na osi Ou rezultat bude shozhij na rezultat DBSCAN klasterizaciyi z timi zh e displaystyle varepsilon i minPts parametri tut znachennya 0 1 mozhe dati dobri rezultati abo za dopomogoyu riznih algoritmiv yaki namagayutsya viyaviti dilyanki vikoristovuyuchi krutiznu viyavlennya kolina abo lokalni maksimumi Klasteri otrimani takim chinom mozhut mati iyerarhichnu strukturu chogo ne mozhe buti dosyagnuto za dopomogoyu DBSCAN SkladnistOPTICS prohodit kozhnu tochku odin raz pri comu virahovuye e displaystyle varepsilon najblizhchih susidiv dlya kozhnoyi Vrahovuyuchi vikoristannya prostorovogo indeksu sho povertaye zapit na susidiv v chas O log n displaystyle O log n runtime zagalna skladnist algoritmu bude O n log n displaystyle O n cdot log n Avtori originalnogo OPTICS povidomili sho faktichnij konstantnij koeficiyent upovilnennya bude 1 6 v porivnyanni z DBSCAN Varto zauvazhiti sho e displaystyle varepsilon mozhe mati velikij vpliv na chas vikonannya algoritmu bo jogo velike znachennya mozhe zbilshuvati skladnist zapitu na najblizhchih susidiv do linijnoyi Vibir e gt maxx yd x y displaystyle varepsilon gt max x y d x y bilshim nizh maksimalna vidstan mizh danimi v nabori danih is ale privede do kvadratichnoyi skladnosti algoritmu Os chomu e displaystyle varepsilon potribno vibirati pid kozhen nabir danih okremo RozshirennyaOPTICS OF ce algoritm viznachennya anomalij yakij bazuyetsya na OPTICS Ce znahodzhennya vikidiv v danomu algoritmi OPTICS z zatratami menshimi nizh za dopomogoyu inshih algoritmiv viyavlennya anomalij DeLi Clu angl Density Link Clustering poyednuye ideyu odnozv yaznoyi klasterizaciya i OPTICS usuvayuchi parametr e displaystyle varepsilon pokrashuyuchi chas vikonannya OPTICS HiSC metod iyerarhichnoyi klasterizaciyi pidprostoru paralelno osi na osnovi OPTICS HiCO DiSH ce pokrashennya HiSC z dopomogoyu yakogo mozhna znahoditi skladnishi iyerarhiyi FOPTICS ce shvidsha realizaciya z vikoristannyam vipadkovih proyekcij RealizaciyaRealizaciya OPTICS OPTICS OF DeLi Clu HiSC HiCO i DiSH dostupna v frejmvorku z pidtrimkoyu indeksiv Takozh nepovna i povilna implementaciya dostupna v rozshirennyah Weka MRC angl The National Institute for Medical Research zabezpechuye realizaciyu bez pidtrimki indeksiv PosilannyaMihael Ankerst Markus M Breunig Jorg Sander 1999 ACM SIGMOD international conference on Management of data s 49 60 Arhiv originalu za 7 zhovtnya 2012 Procitovano 2 chervnya 2015 Martin Ester Jorg Sander Xiaowei Xu 1996 Evangelos Simoudis Jiawei Han Usama M Fayyad red Proceedings of the Second International Conference on Knowledge Discovery and Data Mining KDD 96 s 226 231 ISBN 1 57735 004 9 Arhiv originalu za 2 travnya 2011 Procitovano 2 chervnya 2015 Markus M Breunig Raymond T Ng and Jorg Sander 1999 OPTICS OF Identifying Local Outliers Principles of Data Mining and Knowledge Discovery Springer Verlag s 262 270 doi 10 1007 b72280 ISBN 978 3 540 66490 1 DOI 10 1007 11731139 16 Nema shablonu zapovniti vruchnu DOI 10 1007 11871637 42 Nema shablonu zapovniti vruchnu DOI 10 1109 SSDBM 2006 35 Nema shablonu zapovniti vruchnu DOI 10 1007 978 3 540 71703 4 15 Nema shablonu zapovniti vruchnu DOI 10 1145 2505515 2505590 Nema shablonu zapovniti vruchnu

Дата публікації:
Топ