Garis memisahkan dua set titik

Jika ada cara untuk mengidentifikasi apakah dua set poin dapat dipisahkan oleh garis?

Kami memiliki dua set titik dan jika ada garis yang memisahkan dan sehingga semua titik dan hanya di satu sisi garis, dan semua titik dan hanya di sisi lainnya.$A$$B$$A$$B$$A$$A$$B$$B$

Algoritma yang paling naif yang saya buat adalah membangun poligon cembung untuk dan B dan mengujinya untuk persimpangan. Kelihatannya waktu kompleksitas waktu untuk ini harus O ( n log h ) seperti untuk membangun poligon cembung. Sebenarnya saya tidak mengharapkan ada perbaikan dalam kompleksitas waktu, saya tidak yakin itu bisa diperbaiki sama sekali. Tetapi setidaknya harus ada cara yang lebih indah untuk menentukan apakah ada garis seperti itu.$A$$B$$O(n\log h)$

Baik uli dan Dave Clarke benar mengamati bahwa ini adalah masalah pemrograman linier, bahkan dalam dimensi yang lebih tinggi (dapatkah dua set titik ini dipisahkan oleh hyperplane?) Dan sehingga dapat diselesaikan dalam waktu polinomial. Tetapi karena poin Anda terletak di pesawat, masalah Anda sebenarnya dapat diselesaikan dalam waktu $O(n)$ , di mana $n$ adalah jumlah total poin.

Solusi paling sederhana mungkin adalah algoritma acak Seidel. Pilih titik input secara seragam secara acak, dan hitung secara terpisah garis pemisah ℓ untuk semua titik kecuali p .$p$$\ell$ $p$

• Jika tidak ada garis seperti itu, maka titik-titik aslinya tidak dapat dipisahkan.

• Jika berada di sisi yang benar dari ℓ , maka ℓ memisahkan titik-titik aslinya.$p$$\ell$$\ell$

• Jika berada di sisi yang salah dari ℓ , maka titik asli dapat dipisahkan oleh garis melalui p , atau titik asli tidak dapat dipisahkan sama sekali. Kondisi ini mudah dicek pada O ( n ) waktu [latihan].$p$$\ell$$p$$O(n)$

Algoritma ini berjalan dalam waktu dengan probabilitas tinggi (sehubungan dengan pilihan acak algoritma). Untuk lebih jelasnya, lihat kertas asli atau sejumlah catatan kuliah online.$O(n)$

Properti dari dua set data Anda adalah keterpisahan linear , sederhananya, bahwa ada garis yang memisahkannya. Banyak pembelajaran mesin dikhususkan untuk menemukan pengklasifikasi linier , yang merupakan garis yang melakukan pemisahan yang Anda minati.

Ketika Anda berbicara tentang garis, saya akan berasumsi bahwa poin Anda ada di pesawat. Apa yang ingin Anda lakukan adalah menemukan nilai , w 2 dan w 3 , sehingga untuk semua titik ( a 1 , a 2 ) di set A , w 1 a 1 + w 2 a 2 ≥ w 3 dan untuk semua poin ( b 1 , b 2 ) dalam 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$ . Dengan demikian, ketimpangan w 1 x + w 2 y ≥ w 3 dapat dilihat sebagai classifier untuk set A .$w_1 b_1+w_2b_2<w_3$$w_1 x+w_2y\ge w_3$$A$

Ada banyak algoritma pembelajaran mesin untuk menentukan garis yang optimal (regresi linier, regresi logistik, dan sebagainya). Ini akan menemukan nilai untuk berdasarkan beberapa metrik kesalahan. Kemudian Anda dapat menguji apakah semua poin diklasifikasikan dengan benar. Artinya, apakah semua nilai-nilai di A memuaskan persamaan di atas dan juga untuk B .$w_1,w_2,w_3$$A$$B$

Karena Anda hanya tertarik pada apakah garis tersebut ada, Anda perlu menggunakan teknik yang ada (meskipun itu mungkin akan lebih sederhana). Cukup setel kumpulan persamaan berikut dalam hal variabel bebas .$w_1,w_2,w_3$

untuk setiap i = 1 , . . , | A | , di mana A = { ( a 1 1 , a 1 2 ) , ... , ( a | A | 1 , a | A | 2 ) } .$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)\}$

untuk setiap j = 1 , . . , | B | , di mana B = { ( b 1 1 , b 1 2 ) , ... , ( b | B | 1 , b | B | 2 ) } .$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)\}$

Jika kendala ini konsisten, maka ada garis.

Jika saya ingat benar mendukung mesin vektor membangun memisahkan pesawat terbang. Jika Anda memilih dimensi hyperplane tentu saja menjadi garis. Anda mungkin harus memeriksa apakah ada asumsi tambahan yang harus dipenuhi. Dalam dua dimensi seluruh pendekatan mungkin sangat disederhanakan sehingga runtime mungkin lebih baik daripada pendekatan umum.$2$