A linha separa dois conjuntos de pontos

Se existe uma maneira de identificar se dois conjuntos de pontos podem ser separados por uma linha?

Temos dois conjuntos de pontos e B se houver uma linha que separa A e B, de modo que todos os pontos de A e apenas A de um lado da linha e todos os pontos de B e apenas B do outro lado.$A$$B$$A$$B$$A$$A$$B$$B$

O algoritmo mais ingênuo que criei é a construção de polígonos convexos para e B e testá-los quanto à interseção. Parece que a complexidade do tempo para isso deve ser O ( n log h ) como para a construção de um polígono convexo. Na verdade, não estou esperando nenhuma melhoria na complexidade do tempo, não tenho certeza de que possa ser melhorada. Mas pelo menos deve haver uma maneira mais bonita de determinar se existe essa linha.$A$$B$$O(n\log h)$

Tanto uli quanto Dave Clarke observam corretamente que este é um problema de programação linear, mesmo em dimensões mais altas (esses dois conjuntos de pontos podem ser separados por um hiperplano?) E, portanto, podem ser resolvidos em tempo polinomial. Mas como seus pontos estão no plano, seu problema pode ser resolvido em tempo, onde n é o número total de pontos.$O(n)$$n$

A solução mais simples é provavelmente o algoritmo aleatório de Seidel. Escolha um ponto de entrada uniformemente aleatoriamente e calcule recursivamente uma linha de separação ℓ para todos os pontos, exceto p .$p$$\ell$ $p$

• Se essa linha não existir, os pontos originais não serão separáveis.

• Se estiver no lado correto de ℓ , ℓ separará os pontos originais.$p$$\ell$$\ell$

• Se estiver no lado errado de ℓ , os pontos originais podem ser separados por uma linha até p , ou os pontos originais não são separáveis. É fácil verificar esta condição em O ( n ) tempo [exercício].$p$$\ell$$p$$O(n)$

Esse algoritmo é executado em tempo com alta probabilidade (com relação às escolhas aleatórias do algoritmo). Para mais detalhes, consulte o documento original ou qualquer número de anotações de aula on-line.$O(n)$

A propriedade dos seus dois conjuntos de dados é a da separabilidade linear , simplesmente, que existe uma linha que os separa. Muito aprendizado de máquina é dedicado a encontrar classificadores lineares , que são linhas que realizam a separação na qual você está interessado.

Enquanto você está falando de linhas, presumo que seus pontos estejam no avião. O que você deseja fazer é encontrar os valores , w 2 e w 3 , de modo que, para todos os pontos ( a 1 , a 2 ) no conjunto A , w 1 a 1 + w 2 a 2 ≥ w 3 e para todos os pontos ( b 1 , b 2 ) em B , w 1 b 1$w_1$$w_2$$w_3$$(a_1,a_2)$$A$$w_1 a_1+w_2a_2\ge w_3$$(b_1,b_2)$$B$ . Assim, a desigualdade w 1 x + w 2 y ≥ w 3 pode ser visto como um classificador para o conjunto A .$w_1 b_1+w_2b_2<w_3$$w_1 x+w_2y\ge w_3$$A$

Existem muitos algoritmos de aprendizado de máquina para determinar uma linha ideal (regressão linear, regressão logística etc.). Eles encontrarão valores para com base em alguma métrica de erro. Depois, você pode testar se todos os pontos estão classificados corretamente. Isto é, se todos os valores em A satisfazem a equação acima e similarmente para B .$w_1,w_2,w_3$$A$$B$

Como você só está interessado em saber se essa linha existe, é necessário usar técnicas existentes (embora isso provavelmente seja mais simples). Simplesmente configure a seguinte coleção de igualdades em termos de variáveis ​​livres .$w_1,w_2,w_3$

para cada i = 1 , . . , | Um | , onde A = { ( a 1 1$w_1 a^i_1+w_2a^i_2\ge w_3$$i=1,..,|A|$ .$A=\{(a^1_1,a^1_2),\ldots,(a^{|A|}_1,a^{|A|}_2)\}$

para cada j = 1 , . . , | B | , onde B = { ( b 1 1$w_1 b^j_1+w_2b^j_2< w_3$$j=1,..,|B|$ .$B=\{(b^1_1,b^1_2),\ldots,(b^{|B|}_1,b^{|B|}_2)\}$

Se essas restrições forem consistentes, existe uma linha.

Se bem me lembro do suporte correto, as máquinas vetoriais constroem hiperplanos separados. Se você escolher a dimensão o hiperplano se tornará, obviamente, uma linha. Pode ser necessário verificar se há premissas adicionais a serem atendidas. Em duas dimensões, toda a abordagem pode simplificar consideravelmente, portanto o tempo de execução pode ser melhor do que na abordagem geral.$2$