スキップしてメイン コンテンツに移動

線形SVMの実装

Introduction


今日は線形SVMの実装をしました。
SVMはDeep learningが主流になる前、人気だったとどこかで拝見しました。
SVMの詳しい理論の説明は別の機会に必ず書きます。

# 第一弾書きました。
SVMの理論 part 1

computerはwindowsでOSはwindows10です。Python3で実装します。
このプログラムには内点法という最適化を使っています。

Dataset

次の二つのdastasetを使います。
一つは、完全に分離できるような分布のデータです・
もう一つは完全に分離できないような分布のデータです。
例えば、data1の分布はこのような形になります。
enter image description here
この分布ならきれいに二つのクラスを分けるような線が引けそうですね。
もう一つのデータは次のようなデータを使います。
enter image description here
このデータはきれいに分けるような線は引けなさそうです。
この二つのデータを用いて、線形SVMを使っていきましょう。

Implementation

  • data1
    enter image description here
この線が分離面になります。
きれいにいい感じのところに引けてます。
  • data2
    このデータについては様々なCを用いて計算してみました。
enter image description here
enter image description here
enter image description here
Cの値が小さければ小さいほど、誤分類を認めてしまうことになります。
このデータではCの影響を確認しずらいかもしれませんが、\(C=1\)　の時、よく見ると、赤色のデータが一つ境界面を飛び出しています。
線形でないSVMを使うとCの影響がもっとわかりやすいかもしれません。
非線形なSVMについては、別の記事で書こうと思います。

CODE

コードはすべてgithubに乗せています。
My SVM code is here
今回使ったファイルはgit_SVM_check.pyとgit_SVM_def.pyです。
git_SVM_check.py には次のようなコードが入ったメインファイルです。
if __name__ == '__main__':
git_SVM_def にはSVMのクラスと、内点法の実装が入っています。
次は非線形のSVMについても書きたいと思います。
もし、そちらの記事も見ていただけたらハッピーです。
Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。 カーネルは次のように定義されます。 $$K(x,y) = \phi(x)^T \phi(y)$$ $\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 プロトタイプは$\mu_i ~\forall k \in K$としま...
コメントを投稿
続きを読む

secure_file_priv

Introduction sorry, this page is Japanese only.   最近SQLを勉強し始めたので自分のメモ代わりに得た知識を書こうと思います。 OSはwindowsでMYSQL server 5.7を使っています。 LOAD DATA INFILE CSVファイルをLOAD DATA INFILEで取り込おうとしたらエラーが出ました。エラーメッセージではsecure_file_privがどうのこうの...... ではまずsecure_file_privとはなんなのか確認していきます。 secure_file_priv secure_file_privはデフォルトで設定される項目の一つです。 secure_file_privがデフォルトで設定されているときは、その設定されているディレクトリにあるファイルしか読み取れません。 secure_file_privの値の確認は mysql> SELECT @@global.secure_file_priv で確認できます。 windowsの場合はProgramData/MySQL server 5.7/uploadsが指定されているようです。 CSVファイルのIMPORT では実際にuploadsの中にあるcsv fileをimportするcodeは以下です。取り込みたいファイルをselect@@global.secure_file_privで得られたディレクトリに置いておくのを忘れないでください。 C:/ProgramData/MySQL/MySQL server 5.7/Uploads/に入っているfile.csvをdbというデータベースのtabというtableにimportします。 DATA LOAD INFILE 'C:/ProgramData/MySQL/MySQL Server 5.7/Uploads/ file.csv' INTO TABLE db.table selec @@global.secure_file_privで指定されているディレクトリ以外からファイルを取り込む方法は以下に記しておきます。 secure_file_privの変更 secure_file_privを変更したい、...
コメントを投稿
続きを読む

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む