Pythonでの最近傍法の実装をしましたが，実行時間の短縮方法を教えて欲しいです．

Question

前提・実現したいこと

Pythonで機械学習を行う前の段階で，最近傍法を用いてクラスタリングをしてみました．しかし，このプログラムでは実行に時間がかかりすぎ使い物になりませんでした．実行時間を短縮するためにどこをどのように修正すれば良いか教えて欲しいです．

該当のソースコード

import numpy as np
import cv2
NL = 700
t=0
imgshape = (120, 100, 3)
D = np.prod(imgshape)
datL = np.empty((NL, D)) 
labL = np.empty(NL, dtype=int)
K = 3
with open ('listL.txt') as f: #学習データの読み込み
    for line in f:
        line = line.strip()
        i, s = line.split()
        img= cv2.imread(i)
        vec = img.reshape(-1)
        datL[t,:]=vec
        labL[t]=s
        t=t+1

d=np.empty((NL,))
count=0
cnt=0
with open ('listT.txt') as x: #テストデータの読み込み
    for line in x:
        count=count+1
        line = line.strip()
        i, s = line.split()
        img= cv2.imread(i)
        vec = img.reshape(-1)
        vec2= vec**2
        for n in range(NL): #テストデータと学習データの距離計算（ユークリッド距離）
            d[n]=np.sum((vec-datL[n,:])**2)
        no=d.argmin()
        if int(s)==labL[no]:
            cnt=cnt+1

print(cnt) #正解の数表示
print(cnt/count) #識別率の表示

試したこと

距離計算のところ d[n]=np.sum((vec-datL[n,:])**2)を変えようとしましたが，うまくいきません．

補足情報（FW/ツールのバージョンなど）

画像の読み込みのは時間がかかっていません．これは最短距離法を同じデータで実装した場合，約1〜2秒でできましたが，最近傍法は約30秒かかってしまします．そこで，距離計算に目をつけたのですが改善方法が見つからず苦戦しています．よろしくお願いします．

Answer 1

距離計算のところで時間がかかっていることを、時間を計測するなどして確認したのでしょうか？

上記のスクリプトの実行が完了するのに時間がかかるということを言っているのであれば、実行するたびに画像を全部読みこむ必要があるので、そこに時間がかかっていると思います。
画像の読み込みに時間がかかるのは、仕方ないと思います。一度読み込んで、メモリに展開してしまえば、スクリプトを終了するまではデータはメモリ上にあるので、推論に必要な処理は距離の計算だけになります。

Comments

[退会済みユーザー]

ご指摘ありがとうございます．最近傍法では約30秒かかります．このプログラムで使用するデータを最短距離法で使用したところ実行時間が約2秒程度でした．そのため，距離計算の改善が必要なのではと考えました．

[tiitoi]

画像サイズと最近傍法で登録したサンプル数がどのくらいなのかにもよりますが、それぞれそれなりに大きい場合は時間がかかりそうですね。
画像のすべての画素をそのまま特徴量として使用するとどうしても計算量がかなり多くなってしまうので、画像から特徴を抽出して次元数を削減するといいかもしれません。
特徴に何を使うかという問題がありますが、色の構成が似た画像を見つけたいのであれば、色のヒストグラムを特徴量にする、色以外にエッジとか総合的に特徴を見たい場合はCNNで特徴抽出するのがいいかもしれません。