機械学習#k近傍法とその実装とその色々

#前書き

この記事はSentdexさま、偉大なプログラマーのVideoを勉強しながらとったメモです。
https://www.youtube.com/user/sentdex

まず、K-NNはなんですか？WIKIによりますと：
https://ja.wikipedia.org/wiki/K%E8%BF%91%E5%82%8D%E6%B3%95
>
k近傍法は、ほぼあらゆる機械学習アルゴリズムの中で最も単純である。あるオブジェクトの分類は、その近傍のオブジェクト群の投票によって決定される（すなわち、k 個の最近傍のオブジェクト群で最も一般的なクラスをそのオブジェクトに割り当てる）。k は正の整数で、一般に小さい。k = 1 なら、最近傍のオブジェクトと同じクラスに分類されるだけである。二項分類の場合、k を奇数にすると同票数で分類できなくなる問題を避けることができる。

うん、すごく民主的なやり方。まず下のグラフをみてください。6点のデータがありますね。
もしあなたがグループ分けするなら、どうしましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/dd4c078c-a73c-f23b-cdfe-31bdc151c8ae.png)

多分こうになりますね。ではなぜですか？だってお互いの距離が近いですもの。
私達やってのは”Cluster”と言います。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/20f42a88-6a1d-df50-0e96-c6797757a7e0.png)

よろしい。今度は＋とー、既にグループ分けしたものがあります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/148c4dfe-a0b0-a092-f5e2-cd393b604019.png)

いま赤点がでできました。さ、この赤点はどっちのグループに入るでしょうか？
恐らく＋のグループに入るでしょう。でもなぜ？頭の中にどんな思考回路で考えたですか？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/142d58b6-83d0-3eb6-1f9d-0a45fd26159b.png)

今度の赤点は恐らく－グループに入るでしょう。またなんぜですか？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/040c602c-2869-bb8c-22f6-5f7cddf50c15.png)

最後もし赤点ここにいるなら、どっちのグループなんでしょうか？
これはあなた選んでるアルゴリズムによります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/2872996b-1b57-0f76-8cae-f9246522b415.png)

さ、話戻りましょう。多分（少なくても私が）はこの赤点はーのグループより＋のグループのほうが距離近いから赤点が＋グループです！と判断してたはずです。
そして私たちこの”考え”をK-nearest neighbors(K-NN)と呼びます。
日本語だとk近傍法だと、思います。
K-NNやってる仕事はグループ分けしたいポイントをと他のポイントの距離を測り、どっちのグループに入るのかを判断するだけです。先みせた例ではグループは２しかないですが、もし課題が１００があるとしたら？もし課題１０００があるとしたら？うん、気を失いちゃいそう…
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/b36095bb-eb07-f390-fd13-0a34a1647414.png)

ですが、よく考えてください。本当にすべてのポイントも測らないといけないでしょうか？大体の場合は必要がないと思います。K-NNには”K"を定義するのです。じゃ、仮にK=2を設定しましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/d7d92592-651b-4be4-1cb3-1076cd4fc49e.png)

うんうん、なるほど。多分オレンジ丸しる書いてるのところは赤点に一番近いだね。
だから、私はこの赤点が＋グループと、判断します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/ab408af6-ef2e-5d98-43b8-8f71f3529986.png)


今度黒点が出てきました。K=2の場合、一番近いの点はどっちでしょうか？
うん、多分この２つですね。問題出ました！引き分けになった！それじゃ判断できません。
K-NNは基本的に、このkは偶数しちゃだめです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/32bd34cc-5878-faa8-ec2f-219b07b2bda1.png)

なので、K=3を設定します。K=3になると私たちもう一つの点が必要になります。
多分…ーのほうが近いかな？
この黒点がーのグループだと。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/89736408-17e6-2631-a12e-7e9106c981e1.png)

で、先の判断だとーが２つ、＋が１つ。２/３＝６６％
この６６％はこの判断に対するconfidence（信頼度）です。
そして先測った距離のこと、Euclidean Distanceだと言います。

#実装
まず流れを決めましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/6e9b7f63-49bd-9d32-4d6d-4705af15a76b.png)

##データ用意

ではsklearnを使って実装しましょう。

まずData-setを用意しなといけないので、今回使うのはこれです：
https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+%28original%29
乳がんに関するデータです。

##データ分析

ダウンロードされたものはこうなると思います。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/5e0467d9-a524-797e-8651-e99ec6fbfeaf.png)

breast-cancer-wisconsin.namesを開くとデータに関する説明が書いております。
7.のところに各データ値の”意味”が書いています。ここからみると1から10番まではFeaturesで11はLabelだそうですね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/9d7fe7a1-8da1-e7f1-5f54-5c3b44234536.png)
breast-cancer-wisconsin.dataにデータが入っています。ですが肝心なラベルが書いてません。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/09431e37-b525-3789-b5b3-080483c724f0.png)
プログラムで追加でもできますが、いまはとりあえず手で入力します…
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/5874b99f-602a-3220-564e-3bac99035fdc.png)


##ライブラリImport
```python

import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd
```
##pandasで先処理する
idはData-setの中にあまり関係がなさそうなのでDropします。
breast-cancer-wisconsin.namesの中に抜けたところは”？”を表示すると書いています。
NANは基本NGなのでここで仮に－99999に置き換えます。

```python
df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)
```
##X,Yデータ用意する
簡単にいうと、Xはラベル入ってないデータ。Yはラベルだけのデータ。
だからXは”class”がDropされたDataFrameを入れます。
Yは”Class"だけのDataFrameを入れます。

```python
#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])
```
##Test,Trainデータ分ける
80%のTrainデータと20%のテストデータが分けます。

```python
x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.2)
```

##Classifier用意する
K-NN使うから当然KNeighborsClassifierですね。

```python
clf=neighbors.KNeighborsClassifier()
```

##Train
```python
clf.fit(x_train,y_train)
```

##Testデータで検証する
うん～大体96%くらいかな。まぁまぁいい精度ですね。

```python
accuracy=clf.score(x_test,y_test)
print(accuracy)

>0.9642857142857143
```

##全体Code

```python
import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)

#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])

x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.2)
clf=neighbors.KNeighborsClassifier()
clf.fit(x_train,y_train)
accuracy=clf.score(x_test,y_test)
print(accuracy)
```

#深く掘りましょう
いまからsklearn頼れずに自力でKNNを書いてみます。
まずもう一度見ていきましょう。実際判黒点をどっちのグループにするのかを判断するには距離ですよね。
この距離私達”Euclidean Distance”と言います。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/89736408-17e6-2631-a12e-7e9106c981e1.png)

##計算式

計算式はこうになります。字が醜いすいません…
ここで、
i＝Diemensions
q＝点
p＝違う点
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/a95984b1-b7e2-1cbe-aa5b-892351bc097e.png)

例えばq=(1,3)、p=(2,5)。
Euclidean Distance＝2.236
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/2624bc8f-68a5-9a2a-1a52-c218e0768d06.png)


###実装

では、まずこの数式をpythonで書きましょう。

```python
from math import sqrt

plot1=[1,3]
plot2=[2,5]

euclidean_distance=sqrt( (plot1[0]-plot2[0])**2 + (plot1[1]-plot2[1])**2 )

print(euclidean_distance)
```
##Functionを作る

Functionを作る前にまず思想を考えましょう。
以下のコードはまずDatasetと新しいデータをPlotしてみます。
Functionの機能は、そうですね。
data:Train_dataだね。
predict:こっちはTest_dataだね。
k:何点を取るのか、たしかにsklearnにはDefaultでk＝5と気がします…
そして最後はなにかの魔法を起動させて結果出してくれる！

###実装

```python
from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings

style.use('fivethirtyeight')

data_set={'k':[[1,2],[2,3],[3,1]]
          ,'r':[[6,5],[7,7],[8,6]]} 

new_features=[5,7]

[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1])

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    #?make some magic
    
    return vote_result

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/76423174-c099-489a-1e7e-685233f0447b.png)

##魔法の仕掛を考える

実際このFunctionはなにか求めてるのか？
私達どうやって一つのData-pointと他のData-pointを比べ、そして一番近いPointを探します。
KNNにはPredictのPointをすべてのPointに比べないといけない、それはKNNの問題です。
確かに、Radiusを設定しある程度のPointしかみないという手法で計算の時間を節約することも、可能です。

###実装

1. For Loopの中に全てのeuclidean_distaneを計算し、配列に追加します。
2. たとえば[2.44,'r'],[1.4,'r'],[2.14,'k'],[4.4,'k'],[5.44,'k']..のように。
3. そしてvotesという配列を、先の配列に計算されたeuclidean_distane小さいから多きまでソートします。
4. そのeuclidean_distaneに対応するラベルを格納します。
5. Counter(votes).most_common(1)を使って一番頻度高い元素を取り出します。ここは仮に[('r', 3)]。
6. Counter(votes).most_common(1)[0][0]を使うことによって、’ｒ’が更に取り出せます。
7. 最後は結果をReturnします。

```python
from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings

style.use('fivethirtyeight')

data_set={'k':[[1,2],[2,3],[3,1]]
          ,'r':[[6,5],[7,7],[8,6]]} 

new_features=[5,7]

[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1])

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    for group in data:
        #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
        #iterating  ^                       ^
        for features in data[group]:
            #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
            #iterating      ^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^
            
            #not fast and just for 2-dimensions
            #euclidean_distacnce=sqrt(  (features[0]-predict[0])**2 + features[1]-predict[1]**2 )
            
            #better
            #euclidean_distane=np.sqrt( np.sum((np.array(features)-np.array(predict))**2))
            
            euclidean_distane=np.linalg.norm( np.array(features)-np.array(predict)  )
            distance.append([euclidean_distane,group])
    
    votes=[i[1] for i in sorted(distance)[:k]]
    
    print(Counter(votes).most_common(1))
    
    vote_result=Counter(votes).most_common(1)[0][0]
            
    return vote_result

result=k_nearest_neighbors(data_set,new_features,k=3)
print(result)
[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1],color=result)
```
うん、赤組だね！
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/80a444a2-7516-3831-ff70-ce0fedac8d71.png)

##もう少し先に進もう

今度は本物のデータを使って、scikit-learnとどっちか精度高いかを比べて見ましょう。
1. full_data=df.astype(float).values.tolist()でDataの順をランダムに入れ替えます。
2. train_setとtest_setのData-setを用意します。辞書で2と4で先の乳がんのデータにあるClassに合わせます。
3. train_data=full_data[:-int(test_size*len(full_data))]、例えばfull_dataが100個あれば、test_sizeは0.2なので、100＊0.2＝20になります。train_data=full_data[:-20]は80個のデータセットがtrain_data格納します。
4. test_data=full_data[-int(test_size*len(full_data)):]、例えばfull_dataが100個あれば、test_sizeは0.2なので、100＊0.2＝20になります。train_data=full_data[-20:]は最後の20個データセットがtest_data格納します。
5. 最後のFor loopはTrain_dataとtest_setを使って、test_setはグループ2なのに、voteが4帰ってきたら間違えたと言えますし、逆にtest_setはグループ2で、voteが4帰ってきたら正しいとわかり、correctを＋１にします。そして正確数/Totalは正解率に言えます。

###自力Function

```python
from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings
import pandas as pd
import random

style.use('fivethirtyeight')

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    for group in data:
        #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
        #iterating  ^                       ^
        for features in data[group]:
            #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
            #iterating      ^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^
            
            #not fast and just for 2-dimensions
            #euclidean_distacnce=sqrt(  (features[0]-predict[0])**2 + features[1]-predict[1]**2 )
            
            #better
            #euclidean_distane=np.sqrt( np.sum((np.array(features)-np.array(predict))**2))
            
            euclidean_distane=np.linalg.norm( np.array(features)-np.array(predict)  )
            distance.append([euclidean_distane,group])
    
    votes=[i[1] for i in sorted(distance)[:k]]
    
    print(Counter(votes).most_common(1))
    
    vote_result=Counter(votes).most_common(1)[0][0]
            
    return vote_result

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)
full_data=df.astype(float).values.tolist()

#random sort your data
random.shuffle(full_data)

test_size=0.2
train_set={2:[],4:[]}
test_set={2:[],4:[]}

train_data=full_data[:-int(test_size*len(full_data))]#first 80%
test_data=full_data[-int(test_size*len(full_data)):] #last 20%

'''
for i in train_data:
    #train_set[i[-1]] is the class data from train_set:2 or 4.
    #.append(i[:-1]) is the function to take all the data (unless the class) to the list 
    train_set[i[-1]].append(i[:-1])

for i in test_data:
    test_set[i[-1]].append(i[:-1])
'''
correct=0
total=0

for group in test_set:
    #loop the class'2' and '4'
    for data in test_set[group]:
        #take the data from set'2' and '4'
        vote=k_nearest_neighbors(train_set,data,k=5)
        if group == vote:
            correct+=1
        total+=1
        

print('Accuracy:',correct/total)

>Accuracy: 0.9640287769784173

```

###sklearn Function

いつも通りのコード。

```python
import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)

df.drop(['id'],1,inplace=True)

#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])

x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.4)

clf=neighbors.KNeighborsClassifier()
clf.fit(x_train,y_train)

accuracy=clf.score(x_test,y_test)

>Accuracies: 0.9671428571428571
```

##結論
…正解率あまり変わらないですが、計算Speedは明らかにsklearnの方が早いです。

#最後に
うんーKNNを使わずに分類できる方法他にはまだたくさんあると思います。
例えばこういうLinear的なデータがあるとしましょう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/dd89637f-ed7c-c3d2-dbe3-bff33406b30e.png)
多分？こういう線を先に書いておいて…
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/5bbd9e45-2a3f-c202-fb3d-0b63fd0b9a99.png)
そして新しい赤点が出てきます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/a2f103eb-ead1-2b78-74d4-144edf27331b.png)
Square Errorでなんらかの計算でもいけるのかな？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/ef04ce53-752e-d91f-e6f9-d6069ad18fbb.png)
今度はこのようなNon-linearデータがあるとしよう。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/cf5f731b-efbb-3ace-aa13-3bf3c7502dfb.png)
無理やり線を引くのなら、多分こんな感じかな？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/36c965bb-65b3-1019-1483-447cb2d47861.png)
そういう場合はKNNを使えばすぐわかるじゃないかな？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154661/8f653b75-6737-4b83-c7a5-f349dc544d53.png)

やっばり難しいねー
最後まで付き合って頂いてありがとうございます！
またよろしくおねがいします！