Czy „przekleństwo wymiarowości” naprawdę istnieje w rzeczywistych danych?


17

Rozumiem, co to jest „klątwa wymiarowości”, i zrobiłem kilka problemów związanych z optymalizacją wymiarów i znam wyzwanie możliwości wykładniczych.

Wątpię jednak, czy „przekleństwo wymiarowości” istnieje w większości danych rzeczywistych (odłóżmy na chwilę zdjęcia lub filmy, myślę o danych takich jak dane demograficzne klientów i dane dotyczące zachowań zakupowych).

Możemy gromadzić dane z tysiącami funkcji, ale jest mniej prawdopodobne, że nawet niemożliwe, że funkcje mogą w pełni obejmować przestrzeń o tysiącach wymiarów. Dlatego techniki redukcji wymiarów są tak popularne.

Innymi słowy, jest bardzo prawdopodobne, że dane nie zawierają wykładniczego poziomu informacji, tj. Wiele cech jest silnie skorelowanych i wiele cech spełnia reguły 80-20 (wiele instancji ma tę samą wartość).

W takim przypadku uważam, że metody takie jak KNN nadal będą działać dość dobrze. (W większości książek „przekleństwo wymiarowości” mówi, że wymiar> 10 może być problematyczny. W swoich demach używają równomiernego rozkładu we wszystkich wymiarach, gdzie entropia jest naprawdę wysoka. Wątpię, czy w prawdziwym świecie to się kiedykolwiek wydarzy.)

Moje osobiste doświadczenie z rzeczywistymi danymi jest takie, że „klątwa wymiarowości” nie wpływa zbytnio na metodę szablonów (np. KNN) i w większości przypadków wymiary ~ 100 nadal działałyby.

Czy to prawda dla innych ludzi? (Pracowałem z prawdziwymi danymi w różnych branżach przez 5 lat, nigdy nie zauważyłem, że „wszystkie pary odległości mają podobne wartości” jak opisano w książce).


1
Ponieważ specjalnie wykluczyłeś obrazy i analizę obrazów, po prostu wstawię wtyczkę w komentarzach, mówiąc, że to pole dość regularnie radzi sobie z przekleństwem wymiarowości. Bardzo łatwo jest znaleźć rozwiązanie typu overfit.
Ashe

7
Binarne / obojętne / zakodowane na gorąco cechy
jakościowe

2
Mój kolega pracował przy sprzedaży okularów przeciwsłonecznych. Sporo funkcji miało charakter kategoryczny z dużą liczbą możliwych poziomów (np. Marki, materiały różnych części okularów itp.). Zdecydowanie obawiałem się CoD, ale zawsze trudno powiedzieć, czy jest on obecny w określonym zbiorze danych, a ponadto prawdopodobnie nie zrobiliśmy wielu standardowych sztuczek, nie będąc ekspertami w tym konkretnym typie analizy.
S. Kolassa - Przywróć Monikę

@StephanKolassa Czy zatem metody oparte na odległości działały w przypadku użycia szkła słonecznego?
Haitao Du

Niezbyt dobrze. To nie był bardzo udany projekt.
S. Kolassa - Przywróć Monikę

Odpowiedzi:


15

Ten artykuł (1) omawia błogosławieństwo niejednorodności jako kontrapunkt dla przekleństwa wymiarowości. Główną ideą jest to, że dane nie są równomiernie rozproszone w przestrzeni cech, dzięki czemu można uzyskać przyczepność, identyfikując sposoby ich organizacji.

(1) Pedro Domingos, „Kilka przydatnych rzeczy na temat uczenia maszynowego”


7

Klątwa wymiarowości w uczeniu maszynowym jest częściej problemem eksplozji pustej przestrzeni między kilkoma punktami danych, które masz. Niska różnorodność danych może nawet pogorszyć sytuację. Oto przykładowa konfiguracja z 10000 próbkami, w których próbuję wykonać kNN z 1 sąsiadem.

from numpy.random import normal
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_score
import matplotlib.pyplot as plt
import numpy as np
from math import sqrt
from scipy.special import gamma

N=10000
N_broad=2
scale=20

dims=[]
precs=[]


def avg_distance(k):
    return sqrt(2)*gamma((k+1)/2)/gamma(k/2)

for dim in range(N_broad+1,30):
    clf = KNeighborsClassifier(1, n_jobs=-1)

    X_train=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_train=(X_train[:,N_broad]>0).astype(int)
    clf.fit(X_train, y_train)

    X_test=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_test=(X_test[:,N_broad]>0).astype(int)
    y_test_pred=clf.predict(X_test)

    prec=precision_score(y_test, y_test_pred)
    dims.append(dim)
    precs.append(prec)
    print(dim, prec)

plt.plot(dims, precs)
plt.ylim([0.5,1])
plt.xlabel("Dimension")
plt.ylabel("Precision")
plt.title("kNN(1) on {} samples".format(N))
plt.show()

Nie podobały ci się w pełni jednorodne rozkłady, dlatego stworzyłem to kolektor 2D o mniejszych wymiarach (zmniejszonych o scale) rozsianych wokół płaszczyzny 2D dwóch pierwszych współrzędnych. Tak się składa, że ​​jeden z mniejszych wymiarów ma charakter predykcyjny (etykieta ma wartość 1, gdy wymiar ten jest dodatni).

Precyzja spada szybko wraz ze wzrostem wymiarów.precyzja kNN

Oczywiście precyzja = 0,5 byłaby przypadkowym zgadywaniem. Z powierzchnią decyzyjną, która jest bardziej skomplikowana niż samolot, byłoby jeszcze gorzej.

To tak, jakby kule kNN były zbyt rzadkie, aby były pomocne w badaniu gładkiej hiperpłaszczyzny. Przy wyższych wymiarach czują się coraz bardziej samotni.

Z drugiej strony metody takie jak SVM mają widok globalny i radzą sobie znacznie lepiej.


5

Rozważmy na przykład szeregi czasowe (i obrazy oraz audio). Odczyty czujników (Internet przedmiotów) są bardzo powszechne.

Klątwa wymiarowości jest o wiele bardziej powszechna niż myślisz. Jest tam duża redundancja, ale także dużo hałasu.

Problem polega na tym, że wiele osób po prostu unika tych wyzwań związanych z rzeczywistymi danymi i używa tylko tych samych zestawów danych UCI, które zostały odświeżone.


Tak, zgadzam się. Powiedz model sekwencjiP.(X)=P.(X1)n=2)N.P.(Xn|Xn-1). Właściwość Markowa jest sposobem na uregulowanie i pokonanie przekleństwa wymiarowości. Ale szeregi czasowe przypominają obraz lub wideo.
Haitao Du

1
Może większość rzeczywistych danych pochodzi z czujników, takich jak obrazy, wideo i szeregi czasowe?
Anony-Mus-Przywróć Monikę

2
@ hxd1011 Właściwość markov to abstrakcja, która może nie mieć nic wspólnego z prawdziwymi danymi!
Sycorax mówi Przywróć Monikę

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.