Existe uma maneira de testar a separabilidade linear de um conjunto de dados de duas classes em altas dimensões? Meus vetores de recursos têm 40 anos.
Eu sei que sempre posso executar experimentos de regressão logística e determinar a taxa de hitrato versus falso alarme para concluir se as duas classes são linearmente separáveis ou não, mas seria bom saber se já existe um procedimento padrão para fazer isso.
Respostas:
Bem, as máquinas de vetores de suporte (SVM) são provavelmente o que você está procurando. Por exemplo, o SVM com um kernel RBF linear, os mapas apresentam um espaço dimensional maior e tentam separar as classes por um hiperplano linear. Este é um belo vídeo SVM curto ilustrando a idéia.
Você pode agrupar o SVM com um método de pesquisa para seleção de recursos (modelo de wrapper) e tentar ver se algum de seus recursos pode poupar linearmente as classes que você possui.
Existem muitas ferramentas interessantes para usar o SVM, incluindo LIBSVM , MSVMPack e Scikit-learn SVM .
fonte
e1071pacotes (nomeados misteriosamente)svmcomkernel="linear"e ver a previsão versus a real.Computacionalmente, a maneira mais eficaz de decidir se dois conjuntos de pontos são separáveis linearmente é aplicando a programação linear . O GLTK é perfeito para esse propósito e praticamente todas as linguagens de alto nível oferecem uma interface para ele - R , Python, Octave, Julia, etc.
Com relação à resposta que sugere o uso de SVMs :
O uso de SVMs é uma solução subótima para verificar a separabilidade linear por dois motivos:
SVMs são classificadores de margem flexível. Isso significa que um SVM linear do kernel pode se contentar com um plano de separação que não está se separando perfeitamente, mesmo que seja realmente possível. Se você verificar a taxa de erro, ela não será 0 e concluirá falsamente que os dois conjuntos não são linearmente separáveis. Esse problema pode ser atenuado com a escolha de um coeficiente de custo C muito alto - mas isso tem um custo computacional muito alto.
SVMs são classificadores de margem máxima. Isso significa que o algoritmo tentará encontrar um plano de separação que esteja separando as duas classes enquanto tenta ficar longe das duas o máximo possível. Novamente, esse é um recurso que aumenta desnecessariamente o esforço computacional, pois calcula algo que não é relevante para responder à questão da separabilidade linear.
Digamos que você tenha um conjunto de pontos A e B:
Então você deve minimizar o 0 para as seguintes condições:
(O A abaixo é uma matriz, não o conjunto de pontos acima)
"Minimizar 0" efetivamente significa que você não precisa realmente otimizar uma função objetivo, porque isso não é necessário para descobrir se os conjuntos são linearmente separáveis.
No final (
) está definindo o plano de separação.
Caso você esteja interessado em um exemplo de trabalho em R ou nos detalhes matemáticos, verifique isso .
fonte
O Perceptron linear é garantido para encontrar uma solução, se houver. Essa abordagem não é eficiente para grandes dimensões. Computacionalmente, a maneira mais eficaz de decidir se dois conjuntos de pontos são linearmente separáveis é aplicando a programação linear conforme mencionado por @Raffael.
Uma solução rápida seria resolver um perceptron. Um código com um exemplo para resolver usando o Perceptron no Matlab está aqui
fonte