私はN個の緑色の点とM個の赤色の点を持っています（3つは同一線上にありません）。そのような点を線で分けることが可能かどうかを知りたいのですが、すべての緑の点が一方の側に、赤の点が他方の側にあるようにします。そのような線があれば、私はそれの方程式を見つけたいと思います。ラインはこれらのポイントを通過することはできません。この問題を解決する最速のアルゴリズムは何ですか？これは宿題ではなく、私が最近考えた問題です。飛行機の点を線で分割する
ビルドconvex hulls両方のセット。彼らが交差する場合は、そのような分割ラインがない
二つのパターンが西とXjのは、船体が互いに素であるときは、その 凸包は
互いに素である場合には線形分離であると言われている設定します、線might be foundとrotating calipers
これはまさにSVMsです。より具体的には、SVMは、linearly separableである場合に、両方の点のセットからより遠い線を見つける。さもなければ、アルゴリズムは何らかの「ベストエフォート型」解決策を見つけるために調整することができる。
SVMについて詳しく読むことができるソースはたくさんありますが、基本的にはリニアカーネルを使用する必要があります。一例として、ここにはthe SVM implementation in scikit-learnがあり、いくつかの画像があります。
separating hyperplane（二次元の直線）を学習するには、問題をバイナリ分類の問題として提示します（単層）perceptronを使用します。
2つの点集合がlinearly separableである場合、そのような超平面が1つ存在すると、パーセプトロンアルゴリズムが収束することが保証され、解決策は2つのクラス（緑と青）を分離するhyperplane（2次元の直線） 。
解決策が存在しない場合、アルゴリズムは収束せず、有限回数の反復後に停止することができます。
いずれの場合も、アルゴリズムが停止した後（収束または最大反復を超えて）、出力ラインの両側のすべての点が単色であるかどうかを確認できます（つまり、もう一方の側には緑の点のみが含まれます）、そうであれば、線の方程式を返します。そうでなければ、そのような線は存在しません。
純粋な実装ではなく、perceptron pocket algorithmを使用することもできますが、私たちの目的のために純粋な実装も（https://en.wikipedia.org/wiki/Perceptron）動作します。