Átlagos váltás

Az átlagos eltolás egy nem paraméteres jellemzőtér - elemzési technika a maximális valószínűségi sűrűség meghatározására, az úgynevezett módkeresési algoritmus [1] . A technika hatóköre a klaszteranalízis a számítógépes látásban és képfeldolgozásban [2] .

Történelem

Az átlagos eltolási eljárást 1975-ben vezette be Fukunaga és Hostetler [3] .

Áttekintés

Az átlagos eltolás egy eljárás, amely egy diszkrét minta által adott valószínűségi sűrűség maximumát ( módusait ) határozza meg ezen a függvényen [1] . A módszer iteratív, és a kezdeti becsléssel kezdjük . Legyen adott a kernel függvény . Ez a függvény meghatározza a legközelebbi pontok súlyát az átlag újrabecsléséhez. Általában a Gauss-kernelt a távolságtól az aktuális becslésig használják . A függvény által meghatározott ablakban a sűrűség súlyozott átlaga a $x$ $K(x_{i}-x)$ $K(x_{i}-x)=e^{-c||x_{i}-x||^{2))$ $K$

m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i)){\sum _{x_{i} \in N(x)}K(x_{i}-x)}}

ahol a pont szomszédsága , azaz olyan ponthalmaz, amelyre . $N(x)$ $x$ $K(x_{i})\neq 0$

Fukunaga és Hostetler papírjának különbségét átlagos eltolódásnak nevezzük [3] . $m(x)-x$

Az átlagos eltolási algoritmus most hozzárendeli és addig iterálja a becslést, amíg az konvergál. $x\leftarrow m(x)$ $m(x)$

Bár az átlagos eltolási algoritmust széles körben használják számos alkalmazásban, nincs szigorú bizonyíték egy általános kernelt használó algoritmus konvergenciájára nagy dimenziós terekben [4] . Aliyari Gassabeh differenciálható, konvex és szigorúan csökkenő profilfüggvénnyel mutatta meg az átlageltolási algoritmus konvergenciáját egydimenziós térben [5] . Az egyik dimenzió esete azonban csak korlátozottan használható valós problémák esetén. Az algoritmus konvergenciáját véges számú (vagy izolált) stacionárius pontú, nagydimenziós esetekre igazoltuk [4] [6] . Azonban nem adottak elegendő feltételeket ahhoz, hogy a kernelfüggvénynek véges számú (vagy izolált) stacionárius pontja legyen.

Részletek

Legyen az adat egy véges ponthalmaz egy n-dimenziós X euklideszi térben. Legyen K egy lapos kernel, amely a karakterisztikus függvény a -ballon X-ben, $S$ $\lambda$

$K(x)={\begin{cases}1&\ \|x\|\leqslant \lambda \\0&\ \|x\|>\lambda \\\end{cases))$

Az algoritmus minden iterációja során az összesre egyszerre kerül végrehajtásra . Az első kérdés tehát az, hogy egy adott térbeli ponthalmazból hogyan becsüljük meg a valószínűségi sűrűséget. A legegyszerűbb megközelítés az adatok egyszerű lapítása, azaz konvolválás egy fix szélességű kernellel , $s\leftarrow m(s)$ $s\in S$ $h$

$f(x)=\sum _{i}K(x-x_{i})=\sum _{i}k\left({\frac {\|x-x_{i}\|^{ 2}}{h^{2}}}}\jobbra)$

hol vannak a bemeneti pontok és a kernel függvény (vagy Parzen ablak ). A h paraméter az egyetlen paraméter az algoritmusban, és sávszélességnek hívják. Ez a megközelítés Kernel sűrűségbecslési technikának vagy Parzen Window néven ismert. Ha a fenti egyenletből kiszámoltuk, gradiens süllyedés vagy más optimalizálási technikák segítségével megtalálhatjuk a függvény lokális maximumát. A probléma ezzel a brute-force megközelítéssel az, hogy nagy dimenziók esetén számításilag lehetetlenné válik a teljes térre kiterjedő számítás. Ehelyett az átlagos eltolási algoritmus egy olyan változatot használ, amely az optimalizálási szakirodalomban több újraindítású gradiens süllyedés néven ismert . A lokális maximum helyére vonatkozó feltételezésből kiindulva , amely lehet egy véletlen bemeneti adatpont is , az átlageltolás kiszámítja a sűrűséggradiens becslését a pontban , és abba az irányba lép (növekszik) [7] . $x_{i}$ $k(r)$ $f(x)$ $f(x)$ $y_{k}$ $x_{1}$ $f(x)$ $y_{k}$

Kernelek típusai

Kerneldefiníció: Legyen X egy n-dimenziós euklideszi tér . Jelölje x i-edik komponensét . Az x vektor normája egy nem negatív szám . A K: függvényt kernelnek mondjuk, ha létezik olyan profil , amelyre ${\displaystyle R^{n))$ $x_i$ $\|x\|^{2}=x^{T}x$ $X\rightarrow R$ $k:[0,\infty ]\rightarrow R$

$K(x)=k(\|x\|^{2})$ és

k nem negatív.
k nem növekvő: ha . $k(a)\geqslant k(b)$ $a<b$
k darabonként folytonos és $\int _{0}^{\infty }k(r)\,dr<\infty \$

Két általánosan használt kernelprofil az átlagos eltolódáshoz:

lapos mag

$k(x)={\begin{cases}1&\ x\leqslant \lambda \\0&\ x>\lambda \\\end{cases))$

Gauss kernel

$k(x)=e^{-{\frac {x}{2\sigma ^{2))))),$

ahol a szórás paraméter szolgál sávszélesség paraméterként . $\sigma$ $h$

Alkalmazások

Klaszterezés

Tekintsünk egy ponthalmazt a kétdimenziós térben. Tekintsünk egy kör alakú ablakot, amelynek középpontja C, r sugarú kernel. Az átlagos eltolási módszer egy szélsőséges keresési algoritmus, amely iteratív módon tolja el ezt a kernelt egy nagyobb sűrűségű régióba, amíg a folyamat konvergál. Bármely eltolódást az átlag eltolási vektora határoz meg. Az átlagos eltolási vektor mindig a maximális sűrűségnövekedés irányába mutat. Minden iterációnál a kernel a súlypont vagy a benne lévő pontok átlagértéke felé tolódik el. Ennek az átlagnak a kiszámításának módja a kernel megválasztásától függ. Ha egy Gauss-kernelt választunk ki a lapos kernel helyett, akkor minden ponthoz hozzárendel egy súlyt, amely exponenciálisan csökken a kernel középpontjától való távolság növekedésével. Amikor a folyamat konvergál, nem lesz olyan irány, amelyben az eltolódás több pontot tudna befogadni a mag belsejében.

Követés

Az átlagos eltolás algoritmus használható vizuális követésre. Az ilyen típusú legegyszerűbb algoritmus konzisztenciatérképet hozna létre egy új képen az objektum előző képen szereplő színhisztogramja alapján, és egy átlagos eltolást használna a konzisztenciatérkép csúcsának megtalálásához az objektum régi pozíciójához közel. A konzisztenciatérkép egy valószínűségi sűrűség az új képen, amely az új kép minden pontjához olyan valószínűséget rendel, amely megegyezik az előző kép tárgypontjának színvalószínűségével. Számos algoritmus, mint például a kernel alapú követés [8] , az ensemble tracking [9] , a CAMshift [10] [11] kiterjeszti ezt az elképzelést.

Simítás

Legyen a d-dimenziós bemenet és a szűrt képpixelek a térbeli tartományokban. Minden pixelhez $x_{i}$ $z_{i},i=1,...,n,$

Kezdő értékeket rendelünk és $j=1$ ${\displaystyle y_{i,1}=x_{i))$
Számítása szerint, amíg konvergál, . $y_{i,j+1}$ $m(\cdot )$ ${\displaystyle y=y_{i,c))$
Hozzárendeljük . Az s és r felső indexek a vektor térbeli, illetve intervallumkomponenseit jelölik. A cél megadja, hogy a térben szűrt adatoknak a konvergenciapont intervallumkomponense lesz . $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ ${\displaystyle y_{i,c}^{r))$

Erősségek

A Mean shift egy alkalmazásfüggetlen eszköz, amely alkalmas valós adatelemzésre.
A módszer nem feltételezi a klaszterek alakjának előzetes beállítását.
Az algoritmus tetszőleges jellemzőterek feldolgozására képes.
Az eljárás egyetlen paraméter, a sávszélesség kiválasztásán alapul.
A h sávszélesség/ablakméret fizikai jelentése nem ugyanaz, mint a k -mean .

Hátrányok

Az ablakméret megválasztása nem triviális.
A nem megfelelő ablakméret a módok összeolvadásához vagy további "árnyék" módok kialakulásához vezethet.
Gyakran szükség van önbeálló ablakméret használatára.

Elérhetőség

Az algoritmus változatai megtalálhatók a gépi tanulási és képfeldolgozó csomagokban:

ELKI . Java adatbányászati eszközök sok klaszterezési algoritmussal.
ImageJ . Képek szűrése az átlagos eltolási szűrővel.
Az OpenCV tartalmazza az átlagos eltolás megvalósítását a cvMeanShift módszerrel
Szerszámkészlet Orfeo . Megvalósítás C++ nyelven.
scikit-learn . A Numpy/Python megvalósítás egy gömbfát [en] használ a szomszédos hatékony megkeresésére

Lásd még

Jegyzetek

↑ 12. Cheng , 1995 , p. 790–799.
↑ Comaniciu, Meer, 2002 , p. 603–619.
↑ 1 2 Fukunaga, Hostetler, 1975 , p. 32–40.
↑ Ghassabeh 12. , 2015 , p. 1–10.
↑ Ghassabeh, 2013 , p. 1423–1427
↑ Li, Hu, Wu, 2007 , p. 1756–1762
↑ Szeliski, 2011 .
↑ Comaniciu, Ramesh, Meer, 2003 , p. 564–575.
↑ Avidan, 2005 .
↑ Bradski, 1998 .
↑ Emami, 2013 , p. 180–183.

Irodalom

Yizong Cheng. Átlageltolás, módkeresés és klaszterezés // IEEE-tranzakciók a mintaelemzésről és a gépi intelligenciáról. - IEEE, 1995. - augusztus ( 17. kötet , 8. szám ). - doi : 10.1109/34.400568 .
Dorin Comaniciu, Peter Meer. Átlageltolás: Robusztus megközelítés a jellemzőterület-elemzés felé // IEEE-tranzakciók a mintaelemzésről és a gépi intelligenciáról. - IEEE, 2002. - május ( 24. kötet , 5. szám ). - doi : 10.1109/34.1000236 .
Keinosuke Fukunaga, Larry D. Hostetler. Sűrűségfüggvény gradiensének becslése mintafelismerési alkalmazásokkal // IEEE Transactions on Information Theory. - IEEE, 1975. - január ( 21. kötet , 1. szám ). - doi : 10.1109/TIT.1975.1055330 .
Fiatalság Aliyari Ghassabeh. Elegendő feltétel az átlagos eltolási algoritmus és a Gauss-kernellel való konvergenciához // Journal of Multivariate Analysis. - 2015. - T. 135 . - doi : 10.1016/j.jmva.2014.11.009 .
Fiatalság Aliyari Ghassabeh. Az átlagos eltolási algoritmus konvergenciájáról az egydimenziós térben // Pattern Recognition Letters. - 2013. - T. 34 , sz. 12 . - doi : 10.1016/j.patrec.2013.05.004 . - arXiv : 1407.2961 .
Xiangru Li, Zhanyi Hu, Fuchao Wu. Megjegyzés az átlagos eltolódás konvergenciájáról // Mintafelismerés. - 2007. - T. 40 , sz. 6 . - doi : 10.1016/j.patcog.2006.10.016 .
Szeliski Richárd. Számítógépes látás, algoritmusok és alkalmazások. - Springer, 2011. - ISBN 978-1-84882-934-3 .
Dorin Comaniciu, Visvanathan Ramesh, Peter Meer. Kernel alapú objektumkövetés // IEEE-tranzakciók a mintaelemzésről és a gépi intelligenciáról. - IEEE, 2003. - május ( 25. kötet , 5. szám ). - doi : 10.1109/tpami.2003.1195991 .
Shai Avidan. Ensemble Tracking // 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). - San Diego, California: IEEE, 2005. - Vol. 2. - ISBN 0-7695-2372-2 .
Gary Bradsky. Számítógépes látás arckövetés észlelési felhasználói felületen // Intel Technology Journal. - 1998. - Kiadás. Q2 . Archiválva az eredetiből 2012. október 21-én.
Ebrahim Emami. Online hibaészlelés és -javítás a CAMShift nyomkövető algoritmushoz // 2013. évi iráni konferencia a gépi látásról és képfeldolgozásról (MVIP). - IEEE, 2013. - V. 2 .

Gépi tanulás és adatbányászat
Feladatok	Osztályozási probléma Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellek együttesei Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-közép módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-Net Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG