トップ > Algorithm > 【実装コード有り】Elixirで近しいデータを予想するためにk近傍法を実装した

【実装コード有り】Elixirで近しいデータを予想するためにk近傍法を実装した

Algorithm Elixir

k近傍法とは

ざっと説明するとAというデータとBというデータが
どれだけ近しいかを予測するためのアルゴリズム
仕組みは超簡単で以下のようなデータがあったとする

size(大きさ)は1~5の5段階
is_red(見た目)は1~5の5段階
has_seed(種があるかないか)は0or1

apple = %{size: 2, is_red: 5, has_seed: 0}
water_melon = %{size: 5, is_red: 1, has_seed: 1}

まずこのappleとwater_melonの2つのデータの距離(どれだけ似ているか)を計算する
値が小さければ小さいほど距離が近いということになる
算出にはシンプルに三角比でお馴染みのピタゴラスの定理を使う
ユークリッド距離と呼ばれているらしい

Elixirで計算してみると以下のようになる

  • :math.pow() : 乗数を算出するErlangメゾット
  • :math.sqrt() : 平方根を算出するErlangメゾット
sum_val = :math.pow(2-5, 2) + :math.pow(5-1, 2) + :math.pow(0-1, 2)
dis = :math.sqrt(sum_val)

iex> dis
5.0990195135927845

試しに青リンゴのデータを用意して距離を算出してみる

blue_apple = %{size: 3, is_red: 1, has_seed: 0}
sum_val = :math.pow(2-3, 2) + :math.pow(5-1, 2) + :math.pow(0-0, 2)
dis = :math.sqrt(sum_val)

iex> dis
4.123105625617661

さきほどよりは小さくなったが色の特徴量の数値が値に大きく影響しているのが分かる
(特徴量選択や正規化には触れない)

appleとの距離の算出結果が複数個あるとする(label: 分類名, dis: 距離)

cal_res = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 5.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 2.5},
  %{label: :apple, dis: 1.5},
]

k近傍法では距離の値の小さいものからk個取得して多数決をとる
k = 3としてデータを取得する

fetch_data = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 1.5},
]

取得したデータのラベルをまとめると

[:apple, :water_melon, :apple]

となり、このデータで多数決を取ると最終的な予想結果はappleとなる

Elixirでの実装

与えるデータがappleとorangeのどちらに似ているかを予想させてみる

fruits = [
  %{size: 2, is_red: 2, label: :orange},
  %{size: 2, is_red: 3, label: :orange},
  %{size: 4, is_red: 4, label: :apple},
  %{size: 1, is_red: 1, label: :orange},
  %{size: 5, is_red: 5, label: :apple},
  %{size: 3, is_red: 4, label: :apple},
]

#このデータはapple? orange?
target_data = %{size: 4, is_red: 3}

#取得する値の数(k)
knn_neighbor_num = 3

まずは全体のコードと結果を表示

defmodule KNN do
  def main(target_data, datas, knn_neighbor_num) do
    calc_res = calc_distance(target_data, datas, knn_neighbor_num)
    count_res = count_common_val_in_lst(calc_res)
    Enum.reduce(Map.keys(count_res), fn x, accum -> 
      if count_res[x] > count_res[accum] do
        x
      else
        accum
      end
    end)
  end
  def calc_distance(target_data, datas, knn_neighbor_num) do
    datas
      |> Enum.map(fn row ->
          calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
          %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]}
        end)
      |> Enum.sort_by(&(&1.score))
      |> Enum.slice(0..knn_neighbor_num-1)
      |> Enum.map(&(&1.label))
  end

  def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
  defp _count_common_val_in_lst([], accum, _), do: accum
  defp _count_common_val_in_lst([head | tail], accum, labels) do
    case Enum.member?(labels, head) do
      true ->
        n_accum = Map.put(accum, head, accum[head]+1)
        _count_common_val_in_lst(tail, n_accum, labels)
      false -> 
        n_accum = Map.put(accum, head, 1)
        _count_common_val_in_lst(tail, n_accum, labels ++ [head])
    end
  end
end

IO.puts(KNN.main(target_data, fruits, knn_neighbor_num))
#apple

与えたデータはk近傍法ではappleと予想された
確かに、fruitsのデータと比べてみるとappleっぽい(適当

各関数について

calc_distance

ターゲットデータとその他(今回でいうとfruits)の距離の算出を行なっている
特徴量の数は変動するのでターゲットデータからkeyを生成するようにした
パイプとEnumめっさ使ってElixirっぽく書けた気がする

def calc_distance(target_data, datas, knn_neighbor_num) do
  datas
     |> Enum.map(fn row ->
        #列挙したデータとターゲットデータの距離を算出
        calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
        %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]} 
      end)
    |> Enum.sort_by(&(&1.score)) #scoreの順にリストinマップをソート
    |> Enum.slice(0..knn_neighbor_num-1) #上位k個だけを取得
    |> Enum.map(&(&1.label)) #keyがラベルの値(appleとかorange)を返す
end

count_common_val_in_lst

calc_distanceの戻り値を使って各ラベルがいくつあるのかをカウントする
[apple, apple, banana, orange, orange, apple]というデータからは

res = %{
  apple: 3,
  banana: 1,
  orange: 2
}

というようなマップを生成する

def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
defp _count_common_val_in_lst([], accum, _), do: accum
defp _count_common_val_in_lst([head | tail], accum, labels) do
  #labels(記入したラベルを保持するためのaccum)にheadが存在しているかどうか
  case Enum.member?(labels, head) do
    true ->
      n_accum = Map.put(accum, head, accum[head]+1) #指定のラベルがkeyの値を上書き
      _count_common_val_in_lst(tail, n_accum, labels)
    false -> 
      n_accum = Map.put(accum, head, 1) #新規のラベルをkeyとして作成して1をセット
      _count_common_val_in_lst(tail, n_accum, labels ++ [head])
  end
end

main

上の2つの関数を組み合わせてcountしたmapを作成して
その値から一番カウントが大きな値を返す

def main(target_data, datas, knn_neighbor_num) do
  calc_res = calc_distance(target_data, datas, knn_neighbor_num)
  count_res = count_common_val_in_lst(calc_res)
  Enum.reduce(Map.keys(count_res), fn x, accum -> 
    if count_res[x] > count_res[accum] do
      x
    else
      accum
    end
  end)
end

データはこんな感じで変化していく

#calc_distance
calc_res =[
  %{score: 1, labels: apple},
  %{score: 4, labels: orange},
  %{score: 2, labels: apple},
]

#count_common_val_in_lst
count_res = %{
  apple: 2
  orange: 1
}

#last return
--> apple

可能な限りEnum.reduceとかでやりたい反面、中々上手くいかずに再帰関数を使うハメになる
個人的にaccumを2つもてるEnum.reduce_neo()みたいなのを作ろうと思った