Test liniowej separowalności

Czy istnieje sposób przetestowania liniowej separowalności zestawu danych dwóch klas w dużych wymiarach? Moje wektory cech mają 40 długości.

Wiem, że zawsze mogę przeprowadzać eksperymenty z regresją logistyczną i określać szybkość hitrate vs. fałszywego alarmu, aby stwierdzić, czy dwie klasy można rozdzielić liniowo, czy nie, ale dobrze byłoby wiedzieć, czy istnieje już standardowa procedura do wykonania tego.

machine-learning classification

— Nik
źródło

spójrz tutaj:

— user603 17.01.13

Przydatne jest wykreślanie separacji: x = błędnie sklasyfikowane punkty płaszczyzna normalna do separującej, y = łączna strata (x). (Aby uzyskać przykładowy wykres, wypróbuj nowe pytanie z tagami svm i wizualizacją danych.)

\cdot

$\cdot$

— denis

Co z problemem 3 klas? Czy wszystkie problemy klas 3+ są nieliniowe?

— Rosy,

Odpowiedzi:

Cóż, maszyny wektorów wsparcia (SVM) są prawdopodobnie tym, czego szukasz. Na przykład SVM z liniowym jądrem RBF mapy odwzorowują wyższą przestrzeń wymiarową i próbuje rozdzielić klasy liniową hiperpłaszczyzną. To jest ładny krótki film SVM ilustrujący ten pomysł.

Możesz owinąć SVM metodą wyszukiwania do wyboru funkcji (model opakowania) i spróbować sprawdzić, czy którakolwiek z twoich funkcji może liniowo rozdzielić posiadane klasy.

Istnieje wiele interesujących narzędzi do korzystania z SVM, w tym LIBSVM , MSVMPack i Scikit-learn SVM .

— soufanom
źródło

+1. To prawie tak, jakby Nik opisywał SVM, nie słysząc o nich. W R, można użyć (tajemniczo nazwany) e1071pakiet znajduje svmsię kernel="linear"i spojrzenie na przewidywaniu kontra rzeczywiste.

— Wayne,

Wiem o SVM. Po prostu nie wiedziałem, że mogę ich użyć do testowania liniowej separacji bez faktycznej klasyfikacji każdej próbki.

— Nik

@Wayne: Nik tak naprawdę nie prosi o SVM. W mojej odpowiedzi wyjaśniam, dlaczego nie jest to rozwiązanie jego problemu.

— Raffael

„ Jądro liniowe RBF ” nie istnieje.

— Marc Claesen

Oczywiście ! Chodziło o jądro RBF, które odwzorowuje dane na liniowo oddzielną przestrzeń.

— soufanom

Obliczeniowo najskuteczniejszym sposobem podjęcia decyzji, czy dwa zestawy punktów można rozdzielić liniowo, jest zastosowanie programowania liniowego . GLTK jest idealny do tego celu i prawie każdy język wysokiego poziomu oferuje do tego interfejs - R , Python, Octave, Julia itp.

W odniesieniu do odpowiedzi sugerującej użycie maszyn SVM :

Korzystanie z SVM jest nieoptymalnym rozwiązaniem do weryfikacji liniowej rozdzielności z dwóch powodów:

SVM są klasyfikatorami o miękkim marginesie. Oznacza to, że liniowy SVM jądra może zadowolić się płaszczyzną oddzielającą, która nie rozdziela się idealnie, nawet jeśli jest to faktycznie możliwe. Jeśli następnie sprawdzisz poziom błędu, nie będzie on wynosił 0, i fałszywie wnioskujesz, że tych dwóch zestawów nie da się rozdzielić liniowo. Problem ten można złagodzić, wybierając bardzo wysoki współczynnik kosztu C - ale wiąże się to z bardzo wysokimi kosztami obliczeniowymi.
SVM są klasyfikatorami o maksymalnym marginesie. Oznacza to, że algorytm spróbuje znaleźć płaszczyznę oddzielającą, która oddziela dwie klasy, jednocześnie starając się trzymać z daleka od nich tak daleko, jak to możliwe. Ponownie jest to cecha niepotrzebnie zwiększająca wysiłek obliczeniowy, ponieważ oblicza coś, co nie jest istotne dla odpowiedzi na pytanie o liniową separowalność.

Powiedzmy, że masz zestaw punktów A i B:

wprowadź opis zdjęcia tutaj

Następnie musisz zminimalizować 0 dla następujących warunków:

(A poniżej to macierz, a nie zbiór punktów z góry)

wprowadź opis zdjęcia tutaj

„Minimalizacja 0” skutecznie oznacza, że nie trzeba tak naprawdę optymalizować funkcji celu, ponieważ nie jest konieczne sprawdzanie, czy zbiory można rozdzielić liniowo.

Na końcu ( wprowadź opis zdjęcia tutaj ) definiuje płaszczyznę podziału.

wprowadź opis zdjęcia tutaj

Jeśli interesuje Cię działający przykład w języku R lub szczegóły matematyczne, sprawdź to .

— Raffael
źródło

SVM są klasyfikatorami z miękkim marginesem ... z wyjątkiem sytuacji, gdy używasz SVM z twardym marginesem. To powiedziawszy, używanie SVM byłoby jak strzelanie do muchy z armaty.

— Marc Claesen

to prawda - choć wiele (a może zdecydowana większość) bibliotek SVM nie oferuje tego wyboru

— Raffael

C

$C$

Gwarantujemy, że liniowy perceptron znajdzie rozwiązanie, jeśli takie istnieje. To podejście nie jest skuteczne w przypadku dużych wymiarów. Obliczeniowo najskuteczniejszym sposobem podjęcia decyzji, czy dwa zestawy punktów można rozdzielić liniowo, jest zastosowanie programowania liniowego, o którym wspomniał @Raffael.

Szybkim rozwiązaniem byłoby rozwiązanie perceptronu. Kod z przykładem rozwiązania przy użyciu Perceptron w Matlabie znajduje się tutaj

— Rishi Dua
źródło