PHP-ML k近傍法を分解してみた

#概要

以前から人工知能（AI）とは何者なのか、よくわかりませんでした。
機械が自分で考える？

調べてみると、「Python」という言語で作られることが多いらしい。

<font color="PaleVioletRed"><B>なんだ、プログラム言語で作ることができるものなんだ～。</B></font>:hugging:

じゃあ、怖くありません(笑)

最近では、メジャー言語なPHPなんかでも <B>機械学習ライブラリ</B> なるものが提供されていて、簡単なAIなら作れるらしい！

というわけでわたくしゼーゼマン(笑)は、

<font color="PaleVioletRed">　■さっそくその機会学習ライブラリ（php-ml）を使ってミタ</font>
<font color="PaleVioletRed">　■その中身がどうなっているのか分解してミタ</font>

そして、AIが何者なのか、その正体の一端をのぞいてみたいと思います。

#k近傍法のサンプルコード実行

これ、php-mlのREADMEに記載されているサンプルコードです。

k近傍法っていう機械学習アルゴリズムを呼び出して使っているそうです。:upside_down:kｷﾝﾎﾞｳ･･??

```php:k-demo.php 
<?php
require_once __DIR__ . '/vendor/autoload.php';

use Phpml\Classification\KNearestNeighbors;

$samples = [[1, 3], [1, 4], [2, 4], [3, 1], [4, 1], [4, 2]];
$labels = ['a', 'a', 'a', 'b', 'b', 'b'];

$classifier = new KNearestNeighbors();
$classifier->train($samples, $labels);

echo $classifier->predict([3, 2]);
// return 'b'
```

やってることは、
・[1, 3], [1, 4], [2, 4]を「a」と分類
・[3, 1], [4, 1], [4, 2]を「b」と分類
・そして、[3, 2]というデータがあった場合、「a」「b」どちらに分類するべきかを分析

実行すると、「b」が返ってきます。

<img width="422" alt="実行結果.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/554822/766900a0-f4b2-0eb6-4815-fbd49aabfa01.png">

対象データの[3, 2]が、「a」と「b」、どちらのグループの方により距離が近いかをプログラムが判定しているそうです。

図にしてみると、、、確かに「b」の方が近いな。。。

<img width="316" alt="参考１.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/554822/858c1fb5-84c4-9680-3687-19d47f652dc5.png">



これがk近傍法のサンプルプログラムです。

ではでは、どんな判定プロセスをたどったんでしょうか。

順を追って見ていきましょう:wink:

#k近傍法ステップ１．機械学習

まずこの部分。

```php:k-demo.php
$samples = [[1, 3], [1, 4], [2, 4], [3, 1], [4, 1], [4, 2]];
$labels = ['a', 'a', 'a', 'b', 'b', 'b'];
```

サンプルデータと、そのデータに分類を与えています。

ここは人間が定義します。

以後、このサンプルデータと分類を<font color="PaleVioletRed">教師データ</font>と呼びます。

これを、機械に学習させます。

```php:k-demo.php
// #クラスをインスタンス化する
$classifier = new KNearestNeighbors();
// #インスタンス化して生成したオブジェクトのtrainファンクションを実行し、サンプルデータとその分類を与える
$classifier->train($samples, $labels);
```

・・・といっても、インスタンス化して生成したオブジェクトにデータ持たせてあげるだけなんですけどね(笑)

次がその学習部分です。php-mlの中身になります。

```php:Trainable.php
    // #trainファンクション
    // サンプルデータと分類を受け取って、それぞれクラスのフィールドへ保存している
    public function train(array $samples, array $targets): void
    {
        $this->samples = array_merge($this->samples, $samples); // サンプルデータ
        $this->targets = array_merge($this->targets, $targets); // 分類
    }
```
<font color="PaleVioletRed">教師データが、メモリに蓄えられました。</font>

#k近傍法ステップ２．各教師データとの距離を算出

教師データをメモリに記憶した後、この教師データと、対象データの距離を算出します。

先ほど生成したオブジェクトの、<font color="PaleVioletRed">predictファンクション</font>を実行します。

```php:k-demo.php
// #predictファンクションを実行
// 対象データの[3, 2]は、果たして「a」「b」どちらのグループなのかを分析
echo $classifier->predict([3, 2]);
```

ここからまたphp-mlの中に潜り込んでいきますよ～！

要所を抜粋しながら紹介しますね。:smiley:

途中省略しますが、対象データの[3, 2]は、deltasというファンクションに渡されます。

ここで、対象データと、個々の教師データとの距離が算出されます。

例として、対象データ[3, 2]と、教師データ[1, 3]との距離算出の過程を見ていきましょう！

```php:Distance.php
    // $a = [3, 2] 
    // $b = 教師データ（[1, 3], [1, 4], [2, 4], [3, 1], [4, 1], [4, 2]）が順番に１つずつ渡される
    protected function deltas(array $a, array $b): array
    {
        $count = count($a);

        if ($count !== count($b)) {
            throw new InvalidArgumentException('Size of given arrays does not match');
        }

        $deltas = [];
        // #対象データと教師データの差が絶対値で算出される
        // ここでは $a = [3, 2] , $b = [1, 3] を例示
        for ($i = 0; $i < $count; $i++) {
            $deltas[] = abs($a[$i] - $b[$i]);
            // 1回目の計算：3-1=2
            // 2回目の計算：2-3=-1 ただしabs関数により絶対値を取得するので、ここでは「1」が得られる
        }
        // $deltas = [2,1]

        return $deltas;
    }
```

対象データと教師データのそれぞれ1個目、2個目同士を減算し、両者の絶対値による差を算出しています。

教師データ[1, 3]との距離を算出すると、[2, 1]が得られます。

ところで、この算出結果の[2, 1]。

数字２つに割れてますが、この後呼び出し元のdistanceファンクションで合算します。

ちとガチャガチャやってて、複雑ですよ。:frowning2:ﾑｰﾝ?

```php:Distance.php
    public function distance(array $a, array $b): float
    {
        $distance = 0;

        // 前述のdeltasファンクションの呼び出し元
        foreach ($this->deltas($a, $b) as $delta) {
            // 算出結果の[2,1]が$deltaの中に 2 ⇒ 1 の順で入ってくる
            $distance += $delta ** $this->norm;
            // $this->normは、「3.0」が定義されている
            // 2 の 3乗 = 8
            // 1 の 3乗 = 1 を順番に行い、都度$distanceに合算している
        }
        // $distance = 9

        return $distance ** (1 / $this->norm);
        // 最後に、9 の (1/3)乗 = 2.0800838230519 を算出
        // これが距離となる
    }
```

距離の絶対値を3乗したものを足し合わせ、最後に1/3乗しています。

このあたり、なぜ3乗なのか、わからないのですが。。(笑)

興味ある方は調べてみてくださいm()m

これで、<font color="PaleVioletRed">対象データ [3, 2]と、教師データ[1, 3]の距離は 2.0800838230519</font> と算出できました。:thumbsup:

#k近傍法ステップ３．距離情報の比較分析

さて、この「2.0800838230519」を受け取るのがさらに呼び出し元のkNeighborsDistancesファンクションです。

これ一つだけあっても比較が出来ませんね。:stuck_out_tongue_closed_eyes:ﾃﾍﾍﾟﾛ

同じようにして教師データの２番目、３番目・・・というふうに、順番に各教師データと対象データとの距離を取得していきます。

```php:KNearestNeighbors.php
    private function kNeighborsDistances(array $sample): array
    {
        $distances = [];

        foreach ($this->samples as $index => $neighbor) {
            // 前述のdistanceファンクションの呼び出し元
            // ↑の$this->samplesは、メモリに記憶した教師データ
            // ↓の引数の$sampleの中身は、対象データ[3, 2]
            // 　　　$neighborの中身は、各個別の教師データ
            $distances[$index] = $this->distanceMetric->distance($sample, $neighbor);
            // 最初の教師データ[1, 3]との距離がこれ
            // $distances[0] = 2.0800838230519
            // 残り5つの教師データとの距離については、以下の通り
            // [1, 4] $distances[1] = 2.5198420997897
            // [2, 4] $distances[2] = 2.0800838230519
            // [3, 1] $distances[3] = 1
            // [4, 1] $distances[4] = 1.2599210498949
            // [4, 2] $distances[5] = 1
        }

        // これを、距離の昇順（近い順）に並び替え
        asort($distances);
        // $distances[3] = 1
        // $distances[5] = 1
        // $distances[4] = 1.2599210498949
        // $distances[0] = 2.0800838230519
        // $distances[2] = 2.0800838230519
        // $distances[1] = 2.5198420997897

        // この6つの配列から、近い順に３つ（$this->k = 3）を取り出して返却
        return array_slice($distances, 0, $this->k, true);
    }
```

各教師データとの距離を取得し、比較を行っています。

対象データと距離の近いほうから上位3つだけを残します。

そして、この上位３つの教師データの分類をみて、「a」「b」どちらが多数を占めるか、というのをこの後判定する事になります。

なぜ３つなのか。。。

についても、私には説明できないのでググってみてください:sweat_smile:ｻｰｾﾝ

呼び出し元のpredictSampleファンクションで、教師データの分類別に集計を行っています。

```php:KNearestNeighbors.php
    protected function predictSample(array $sample)
    {
        // 前述のkNeighborsDistancesファンクションの呼び出し元
        // 引数の$sampleの中身は、対象データ[3, 2]
        $distances = $this->kNeighborsDistances($sample);
        // $distancesの中身
        // $distances[3] = 1
        // $distances[5] = 1
        // $distances[4] = 1.2599210498949

        // 教師データの分類集計用の配列を用意
        $predictions = (array) array_combine(array_values($this->targets), array_fill(0, count($this->targets), 0));
        /*predictions：
         Array
        (
            [a] => 0
            [b] => 0
        )*/

        // $distancesのkeyが順番に取り出される
        // $index =「3」,「5」,「4」
        foreach (array_keys($distances) as $index) {
            // $this->targetsの中には、最初にメモリに蓄えた教師データの分類が入っている
            // targets[3] = b
            // targets[5] = b
            // targets[4] = b
            ++$predictions[$this->targets[$index]];
        }
        // 集計結果
        /*predictions：
        Array
        (
            [a] => 0
            [b] => 3
        )*/
        // 集計結果を、値の降順に並び替え
        arsort($predictions);
        /*predictions：
        Array
        (
            [b] => 3
            [a] => 0
        )*/
        // reset関数で配列の最初の要素にポインタを戻す
        /*Array
        (
            [b] => 3　◄
            [a] => 0
        )*/
        reset($predictions);
        // key関数で現在のポインタのキーを取得
        // key($predictions) = b
        return key($predictions);
    }
```

３つとも分類が「b」でしたね。

したがって、分析結果は「b」となります。

ちなみに上記predictSampleファンクションの呼び出し元は、最初に実行した<font color="PaleVioletRed">predictファンクション</font>です。

```php:Predictable.php
   public function predict(array $samples)
    {
        if (!is_array($samples[0])) {
            // 前述のpredictSampleファンクションの呼び出し元
            // 引数の$samplesの中身は、対象データ[3, 2]
            return $this->predictSample($samples);
        }

        $predicted = [];
        foreach ($samples as $index => $sample) {
            $predicted[$index] = $this->predictSample($sample);
        }

        return $predicted;
    }
```

全部繋がりましたね！＼(^o^)／ﾔｯﾎｰ

#最後に

というわけで、一通りk近傍法を分解してみました。

最も単純といわれる機械学習ロジックでしたが、仕組みの一端がわかったので、AIにちょっと親しみが持てたんじゃないでしょうか(*´ω｀*)ﾜﾀｼﾀﾞｹ?

私が初めてAIに接したのは、30年くらい前です。

なんと、<font color="PaleVioletRed">FC版ドラクエ4</font>で導入されたAIシステム:robot:でした。

それはそれは、ちょっと残念なAIとして有名でしたが、逆にあれくらいならこのphp-mlでも作れるのかな？

どうやって作ってたのかな、似たようなの作ってみようかな:thinking:

AIプログラミング、興味の持てるテーマでアプローチしたら相当面白そうですよね！:hugging:ﾜｰﾊﾟﾁﾊﾟﾁ