高校数学ではじめる機械学習 #3: 分類(その1): カテゴリを予測する - 私は志望校に受かる? 

[目次はこちら](https://qiita.com/tomo_t/items/25035a9487bd5014754b)
##今回の問題
前回は数値を予測する手法である回帰についてみていきました。
今回は、データの分類を予測する手法について解説していきます。

さて、あなたは大学受験を控えた大学生だとしましょう。
あなたは最近の模試で、英語71点、数学79点という点数をおさめました。志望校に受かるか気が気ではないあなたは、昨年同じ大学を受験した先輩に、同じ模試の成績と、最終的に合格したかを質問して回りました。その結果が以下の図です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/6a5d55e5-d363-4921-6338-b11b0b467a67.png)

緑が合格した先輩、赤が不合格になってしまった先輩、青があなたの点数です。模試の点数が高いほど、より合格しそうになっているので、このデータは直観的に意味がありそうです。
それでは機械学習の手法を使って、あなたが合格できるかどうかを予測してみましょう。はじめに宣言しておきますが、機械学習による分類の予測手法には様々あり、何が優れている、劣っていると一概に言うことはできません。

解説に進む前に、どのような予測手法があり得るかを考えてみてください。

##k-最近傍法
最も単純明快なのが、k-最近傍法(k-Nearest Neighbors)です。
アイデアはとてもシンプル、予測したい点に近いデータポイントをk個持ってきて、その多数決で決めます。
今回の例でいうと、k=1であれば一番近いのは緑色なので合格、と予測されます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/4c1353eb-576b-af1b-838d-cfc768c270db.png)

この方法はkの値によって結果が変わることが頻繁に起こりえて、例えば今回k=3ですと、緑が1つ赤が2つで、不合格、と予測されます。ではどのようにkを選ぶべきかというと、それはクロスバリデーション(CV)という手法があるのですが、これは次回以降で説明します。

また、k近傍法はデータの単位によっても影響をうけます。例えば、大人の人間を身長(m)体重(kg)でプロットすると、身長は1.4-2.0くらいの数字をとる一方、体重は20-200くらいの数字を取ります。
なので、(1.5, 45)と(1.8, 90)の間の距離を計算すると、体重による影響がほとんどすべてになってしまいます。
この問題を避けるため、k-最近傍法をするときはデータの__正規化__と言って、各変数が平均0、標準偏差1となるようにデータを変換します。例えば、体重が平均65kg、標準偏差が20kgなら、すべての体重のデータから65を引いて20で割ることで、体重という変数は平均0、標準偏差1になります。

##決定木
決定木(Decision Tree)という言葉を聞いたことがある方は多いのではないでしょうか。
これは、データをある一つの変数による条件で分割することを繰り返して、できるだけデータが「偏った」状態を作ろうという手法です。予測は、先ほどの最近傍法と同じように、データの多数決によります。一つの変数による条件、というのは「xが10より大きいか小さいか」といった条件でわけるということです。グラフを想像すればわかりますが、これは2次元でしたら縦線か横線で平面を分割することに相当します。

例えば今回のデータは、以下のように上下に分割すると、上半分が緑8赤2、下半分が緑2赤8となり、上であれば合格、下であれば不合格、と予測できます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/ac6c6353-1a46-26dd-f71f-425d2d9b1ec7.png)
さらにもう一段階分割することもできて、上下をそれぞれ2分割すると以下のようになります。こうすると、もともと上だった領域はいずれにせよ緑が多数派なので合格になりますが、右下の領域は緑が2点で赤がないので、合格と予測されます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/7a1bef61-6107-6840-b1b4-4610e3e3100e.png)

概念的には以上ですが、どのように引くべき線を選ぶのでしょうか。これには、(偏りの対義語としての)「乱雑さ」の指標を導入して、これが最小になるような分割をしようというアイデアを使います。乱雑さの指標として有名なのが、エントロピーとジニ係数(所得格差のジニ係数とは別物)です。ここでは手での計算が簡単なジニ係数を使います。

ジニ係数は、以下の式で定義されます。

```math
\frac{1}{N}\sum_k n_kp_k(1-p_k)
```
ここで添え字kは分割された領域それぞれを表していて、$n_k$がその領域の点の数、$p_k$がそのうち「合格」である割合です。($1-p_k$とかけているので、ここで$p_k$を「不合格」の割合と定義しても、結果が変わらないことに注目してください)。$N$が合計のデータポイントの数です。

スタート時点(分割前)では、$N=20$, $p=0.5$なので、ジニ係数は

```math
\frac{1}{20}\times20\times0.5\times(1-0.5)=0.25
```
です。
一つ目の分割では、上が緑:赤=8:2、下が2:8なので、ジニ係数は

```math
\frac{1}{20}\times(10 \times 0.8\times(1-0.8)+10 \times 0.2\times(1-0.2))=0.16
```
となり、たしかに「乱雑さ」の度合いであるジニ係数は減少しています。コンピューターは毎回の分割で、一回の分割でジニ係数を最小にできる方法を探します。

もちろん、領域をひたすら切って、各領域にデータが1つしか含まれないようにすることができます。これによって確かにジニ係数は小さくなりますが、このモデルが必ずしも精度が高いということではないことに注意してください。どれくらい細かく切るべきか、も先ほど少し名前を出したクロスバリデーションで確認することになります。

##線形に分離する方法 - ロジスティック回帰を中心に
ここまで2つの手法を解説してきましたが、斜めの線で領域を分割して、右上なら合格、左下なら不合格、と言いたいのが人情ではないでしょうか。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/6e331fa4-2a41-d120-4b46-1eb8c167daa5.png)
このように1本の直線(もしくは曲線)で領域を分割する方法は、自然な考えであるだけに色々あります。代表的なものに、<b>SVM(サポートベクターマシン)</b>や、<b>LDA(Linear Discriminant Analysis; 線形判別分析)</b>があります。しかしこういった手法の中でもっともポピュラーなのが<b>ロジスティック回帰</b>ではないでしょうか。

最初に数学を解説すると、ロジスティック回帰というのはある点$\vec{x}$が「合格」である確率$p(\vec{x})$を

```math
p(\vec{x}) = \frac{1}{1+\exp(-(\beta_0+\beta_1 x_1+\beta_2 x_2+\dots))}
```
で表そうとします。ここで$\beta_0+\beta_1 x_1+\beta_2 x_2+\dots$が前回説明した線形回帰と同じ形をしていて、ここにしか求めるパラメーター$\beta$が現れていないため、「回帰」の名前がついています。
$\beta_0+\beta_1 x_1+\beta_2 x_2+\dots$が大きいほど$\exp(-(\beta_0+\beta_1 x_1+\beta_2 x_2+\dots))$は0に近づき、結果として$p(\vec{x})$は1に近づきます。

さて、ロジスティック回帰はパラメーター$\beta$を求めたいわけですが、どういった基準でパラメーターの優劣を比較するのでしょうか。このために、<b>尤度</b>という概念を取り入れます。概念とは言いましたが、確率の出来損ないの弟のようなもので、尤度が大きいパラメーターほど優れている、つまり尤度を最大化するようなパラメーターを求めたいです。

では、尤度とはどのように計算するのでしょう。$\beta_0, \beta_1, \beta_2,\dots$が与えられたとしましょう。すると、各データ点$\vec{x_k}$について、「合格である確率」$p(\vec{x_k})$が求められます。その時尤度$L$を

```math
L=\prod_{合格} p(\vec{x_k}) \prod_{不合格} (1-p(\vec{x_k}))
```
で定義します。一瞬複雑な式な気がしますが、実際に合格であった点の合格な確率と、実際には不合格な点が不合格である確率をかけたもの、つまり、<b>与えられたパラメーターが正しいと仮定したとき、このデータが得られる確率</b>です。この意味が分かってしまえば、$L$が最大になるようなパラメーター$\beta$を探してきたいというアイデアがつかめるのではないでしょうか。この$\beta$を探してくるのは、手で解くのは大変で、コンピューターが数値的に解くことになります。

これはどうして直線で領域を分割することになるのでしょう。いったん、$p\geq0.5$なら合格、$p<0.5$なら不合格と予測することにしましょう。この時の境界線、$p=0.5$に対応するのは、$\beta_0+\beta_1 x_1+\beta_2 x_2+\dots=0$です(代入して確かめてみてください)。今回のケースでいうと、$\beta_0+\beta_1 x_{Eng}+\beta_2 x_{Math}=0$となる点たちです。これは平面における直線の方程式ですね。

このデータにロジスティック回帰を当てはめたところ、$p=0.5$の直線は以下のようになりました。どうやらあなたはかろうじて「不合格」と予測されてしまうようです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/528459/b4e0e7a6-0689-9fcf-e313-b6f4aa06cd77.png)

ここまで当然のように$p=0.5$を分割の条件としてきましたが、これは必ずしも0.5でなければいけないわけではありません。場合によっては0.2(楽観的)や0.8(悲観的)が嬉しい場合というのもあるかもしれません。これは次回以降で紙面があれば解説しますが、同じくクロスバリデーションで決めることが一般的です。

##今回のまとめと補遺
今回は、大きく分けて3つのデータ分類の予測の方法を解説しました。
これらの手法は何が優れていて何が優れていない、というわけではなく、いろいろ実験してみてそれぞれのデータに最もうまくいく手法を探すことになります(もしくはいくつかの手法を合わせて、それらの多数決で決めることもできます)。

今回は簡単のためデータが2変数、図にすると2次元でしたが、実際のデータはより多くの変数を持っていることが多いです。その場合、領域は直線ではなく、超平面(3次元なら平面)で分割されることになります。

今回は数値のデータの分類問題でしたが、次回は文章を分類する問題を取り扱います。