Średnia zmiana - Mean shift

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Przesunięcie średniej jest nieparametryczną techniką analizy przestrzeni cech , służącą do lokalizowania maksimów funkcji gęstości , tzw. algorytmem poszukiwania modów. Domeny aplikacji obejmują analizę skupień w wizji komputerowej i przetwarzaniu obrazów .

Historia

Procedura zmiany średniej jest zwykle przypisywana pracy Fukunagi i Hostetlerowi w 1975 roku. Przypomina jednak wcześniejsze prace Schnella z 1964 roku.

Przegląd

Przesunięcie średniej to procedura lokalizowania maksimów — trybów — funkcji gęstości przy danych dyskretnych próbkowanych z tej funkcji. Jest to metoda iteracyjna i zaczynamy od wstępnego oszacowania . Niech zostanie podana funkcja jądra . Funkcja ta określa wagę pobliskich punktów do ponownego oszacowania średniej. Zazwyczaj używa się jądra Gaussa na odległość do aktualnego oszacowania, . Średnia ważona gęstości w oknie wyznaczona przez wynosi ${\displaystyle x}$ ${\ Displaystyle K (x_ {i}-x)}$${\ Displaystyle K (x_ {i} -x) = e ^ {-c | | x_ {i} -x | | ^ {2}}}$${\ Displaystyle K}$

${\ Displaystyle m (x) = {\ Frac {\ suma _ {x_ {i} \ w N (x)} K (x_ {i}-x) x_ {i}} {\ suma _ {x_ {i} \in N(x)}K(x_{i}-x)}}}$

gdzie jest sąsiedztwo , zbiór punktów dla których . ${\ Displaystyle N (x)}$${\displaystyle x}$${\ Displaystyle K (x_ {i} -x) \ neq 0}$

Różnica nazywana jest średnim przesunięciem w Fukunaga i Hostetler. Algorytm średni-shift teraz ustawia i powtarza oszacowanie aż zbieżny. ${\displaystyle m(x)-x}$${\displaystyle x\leftarrow m(x)}$${\displaystyle m(x)}$

Chociaż algorytm przesunięcia średniej jest szeroko stosowany w wielu aplikacjach, sztywny dowód na zbieżność algorytmu wykorzystującego ogólne jądro w przestrzeni wielowymiarowej nadal nie jest znany. Aliyari Ghassabeh wykazał zbieżność algorytmu przesunięcia średniej w jednym wymiarze z różniczkowalną, wypukłą i ściśle malejącą funkcją profilu. Jednak jednowymiarowa obudowa ma ograniczone zastosowania w świecie rzeczywistym. Wykazano również zbieżność algorytmu w wyższych wymiarach ze skończoną liczbą (lub izolowanych) punktów stacjonarnych. Nie zapewniono jednak wystarczających warunków, aby ogólna funkcja jądra miała skończone (lub izolowane) punkty stacjonarne.

Gaussian Mean-Shift to algorytm maksymalizacji oczekiwań .

Detale

Niech dane będą zbiorem skończonym osadzonym w -wymiarowej przestrzeni euklidesowej, . Niech będzie płaskim jądrem, które jest funkcją charakterystyczną -kulki w , ${\displaystyle S}$${\ Displaystyle n}$${\ Displaystyle X}$${\ Displaystyle K}$${\ Displaystyle \ lambda}$${\ Displaystyle X}$

W każdej iteracji algorytmu wykonywane jest dla wszystkich jednocześnie. Pierwsze pytanie brzmi zatem, jak oszacować funkcję gęstości przy rzadkim zestawie próbek. Jednym z najprostszych podejść jest po prostu wygładzenie danych, np. poprzez splot ich ze stałym jądrem o szerokości , ${\displaystyle s\leftarrow m(s)}$${\displaystyle s\w S}$${\ Displaystyle h}$

gdzie są próbki wejściowe i jest funkcją jądra (lub oknem Parzen ). jest jedynym parametrem algorytmu i nazywa się przepustowością. Takie podejście jest znane jako szacowanie gęstości jądra lub technika okna Parzena. Po obliczeniu z powyższego równania możemy znaleźć jego lokalne maksima za pomocą gradientu lub innej techniki optymalizacji. Problem z tym podejściem „brute force” polega na tym, że dla wyższych wymiarów obliczeniowo niemożliwe staje się ocenianie w całej przestrzeni poszukiwań. Zamiast tego, mean shift wykorzystuje wariant tego, co jest znane w literaturze optymalizacyjnej jako wielokrotne opadanie gradientu restartu . Zaczynając od pewnego przypuszczenia dla lokalnego maksimum , które może być losowym punktem danych wejściowych , średnie przesunięcie oblicza gradient oszacowania gęstości przy i robi krok w górę w tym kierunku. ${\displaystyle x_{i}}$${\displaystyle k(r)}$${\ Displaystyle h}$${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle y_{k}}$${\displaystyle x_{1}}$${\displaystyle f(x)}$${\displaystyle y_{k}}$

Rodzaje jąder

Definicja jądra: Niech będzie -wymiarową przestrzenią euklidesową, . Normą jest liczba nieujemna, . Funkcja nazywa się jądro jeśli istnieje profil , tak, że ${\ Displaystyle X}$${\ Displaystyle n}$${\ Displaystyle \ mathbb {R} ^ {n}}$${\displaystyle x}$${\ Displaystyle \ | x \ | ^ {2} = x ^ {\ top} x \ geq 0}$${\displaystyle K:X\rightarrow \mathbb {R}}$${\displaystyle k:[0,\infty]\rightarrow \mathbb {R}}$

${\ Displaystyle K (x) = k (\ | x \ | ^ {2})}$ oraz

• k jest nieujemne.
• k nie rośnie: jeśli .${\displaystyle k(a)\geq k(b)}$${\displaystyle a<b}$
• k jest odcinkowo ciągła i ${\ Displaystyle \ int _ {0} ^ {\ infty} k (r) \ dr < \ infty \}$

Dwa najczęściej używane profile jądra do zmiany średniej to:

Płaskie jądro

Jądro Gaussa

gdzie parametr odchylenia standardowego działa jako parametr przepustowości, . ${\displaystyle \sigma}$${\ Displaystyle h}$

Aplikacje

Grupowanie

Rozważ zbiór punktów w przestrzeni dwuwymiarowej. Załóżmy okrągłe okno wyśrodkowane w C i mające promień r jako jądro. Mean shift to algorytm wspinania się po wzgórzach, który polega na iteracyjnym przesuwaniu tego jądra do regionu o większej gęstości, aż do zbieżności. Każde przesunięcie jest zdefiniowane przez średni wektor przesunięcia. Wektor przesunięcia średniego zawsze wskazuje kierunek maksymalnego wzrostu gęstości. W każdej iteracji jądro przesuwane jest do środka ciężkości lub średniej punktów w jego obrębie. Sposób obliczenia tej średniej zależy od wyboru jądra. W tym przypadku, jeśli zostanie wybrane jądro Gaussa zamiast jądra płaskiego, to każdemu punktowi zostanie najpierw przypisana waga, która będzie zanikać wykładniczo wraz ze wzrostem odległości od środka jądra. Przy zbieżności nie będzie kierunku, w którym przesunięcie mogłoby pomieścić więcej punktów wewnątrz jądra.

Śledzenie

Algorytm zmiany średniej można wykorzystać do śledzenia wzrokowego. Najprostszy taki algorytm utworzyłby mapę ufności na nowym obrazie w oparciu o histogram koloru obiektu na poprzednim obrazie i wykorzystałby przesunięcie średniej do znalezienia szczytu mapy ufności w pobliżu starego położenia obiektu. Mapa ufności to funkcja gęstości prawdopodobieństwa na nowym obrazie, przypisująca każdemu pikselowi nowego obrazu prawdopodobieństwo, które jest prawdopodobieństwem wystąpienia koloru piksela w obiekcie na poprzednim obrazie. Kilka algorytmów, takich jak śledzenie obiektów oparte na jądrze, śledzenie zespołowe, CAMshift rozwija tę ideę.

Wygładzanie

Niech i będzie -wymiarowym wejściem i przefiltrowanymi pikselami obrazu we wspólnej domenie zakresu przestrzennego. Dla każdego piksela ${\displaystyle x_{i}}$${\displaystyle z_{i},i=1,...,n,}$${\displaystyle d}$

• Zainicjuj i${\displaystyle j=1}$${\ Displaystyle y_ {i, 1} = x_ {i}}$
• Oblicz według aż do zbieżności, .${\displaystyle y_{i,j+1}}$${\displaystyle m(\cdot)}$${\displaystyle y=y_{i,c}}$
• Przypisz . Indeksy górne s i r oznaczają odpowiednio składową przestrzenną i składową wektora. Przypisanie określa, że ​​filtrowane dane na osi lokalizacji przestrzennej będą miały składową zasięgu punktu zbieżności .${\ Displaystyle Z_ {i} = (x_ {i} ^ {s}, y_ {i, c} ^ {r})}$${\ Displaystyle y_ {i, c} ^ {r}}$

Silne strony

1. Mean shift to narzędzie niezależne od aplikacji, odpowiednie do analizy danych rzeczywistych.
2. Nie przyjmuje żadnego predefiniowanego kształtu na klastrach danych.
3. Jest w stanie obsługiwać dowolne przestrzenie funkcji.
4. Procedura polega na wyborze jednego parametru: przepustowości.
5. Szerokość pasma/rozmiar okna 'h' ma znaczenie fizyczne, w przeciwieństwie do k -średnich .

Słabości

1. Wybór rozmiaru okna nie jest trywialny.
2. Nieodpowiedni rozmiar okna może powodować łączenie trybów lub generowanie dodatkowych „płytkich” trybów.
3. Często wymaga zastosowania adaptacyjnego rozmiaru okna.

Dostępność

Warianty algorytmu można znaleźć w pakietach uczenia maszynowego i przetwarzania obrazu:

• ELKI . Narzędzie do eksploracji danych Java z wieloma algorytmami klastrowania.
• ObrazJ . Filtrowanie obrazu przy użyciu filtru przesunięcia średniego.
• mlpack . Wydajna implementacja oparta na algorytmach dwudrzewowych.
• OpenCV zawiera implementację zmiany średniej za pomocą metody cvMeanShift
• Przybornik Orfeo . Implementacja w C++.
• Implementacja Scikit-learn Numpy/Python wykorzystuje drzewo kulkowe do wydajnego wyszukiwania punktów sąsiednich

Zobacz też

• DBSCAN
• Algorytm OPTYKA
• Szacowanie gęstości jądra (KDE)
• Jądro (statystyki)

Bibliografia