処理速度を上げるためのプログラムの書き方

Question

pythonで距離関数DTWを使用したk-means法を実装したのですが，実行するのにすごく時間がかかってしまうため，実用的ではないのですが、どこを変えれば処理内容は変わらず処理速度を上げることができるのかアドバイスいただきたいと思っております。

import numpy as np
import pandas as pd
from scipy.spatial.distance import euclidean
from fastdtw import fastdtw
import glob
import random

d = glob.glob('*_m.csv')
df = pd.DataFrame()
df7 = pd.DataFrame()
df8 = pd.DataFrame()
df9 = pd.DataFrame()
df11 = pd.DataFrame()
v = 3
k = 546
l = k*v
r = np.random.randint(0,v,k)
print(r)
for n in range(v):
    n += 1
    for x in range(k):
        x += 1
        a = d[x-1]
        df1 = pd.read_csv(f'{a}',index_col=0)
        df1 = df1.groupby(df1.index // 60).mean()
        for i in range(24):
            i += 1
            df7.loc[i-1,x] = df1.iloc[i-1,0] + df1.iloc[i-1,1]
            df11.loc[i-1,0] = i-1
            df11.loc[i-1,1] = df1.iloc[i-1,0] + df1.iloc[i-1,1]
            if r[x-1] == n-1:
                df8.loc[i-1,x-1] = df7.iloc[i-1,x-1]
            df9.loc[i-1,0] = i-1
        df9['1'] = df8.mean(axis=1)
        distance, path = fastdtw(df11,df9,dist=euclidean)
        df.loc[n-1,x-1] = distance
        d1 = []
        d1 = df.idxmin(axis=0)
        for s in range(10):
            for i in range(24):
                i += 1
                df7.loc[i-1,x] = df1.iloc[i-1,0] + df1.iloc[i-1,1]
                df11.loc[i-1,0] = i-1
                df11.loc[i-1,1] = df1.iloc[i-1,0] + df1.iloc[i-1,1]
                if d1[x-1] == n-1:
                    df8.loc[i-1,x-1] = df7.iloc[i-1,x-1]
                df9.loc[i-1,0] = i-1
            df9['1'] = df8.mean(axis=1)
            distance, path = fastdtw(df11,df9,dist=euclidean)
            df.loc[n-1,x-1] = distance
            d1 = []
            d1 = df.idxmin(axis=0)            
for n in range (v):
    df12 = pd. DataFrame()
    n += 1
    for x in range(k):
        x += 1
        if d1[x-1] == n-1:
            for  i in range(24):
                i += 1
                df12.loc[i-1,x-1] = df7.iloc[i-1,x-1]
            df12.to_csv(f'dtw20070701_{n-1}_{v}.csv')

乱数を使っているためたまにエラーは出ますが，基本的には正常に動作します。
ちなみに使用しているデータは，546軒分の1分値のデータです。

Answer 1

for をがっつり使うアルゴリズムを書きたいなら、C++ で作成して、Python から呼び出したほうがいいです。
ただ規則性がある計算は大抵 for を回さなくても numpy の indexing を使えばすむので、高速に計算できます。

numpy で k平均法の実装サンプル

fastdtw は知らないのですが、k平均法の距離関数を fastdtw に変えるだけではダメなのでしょうか？

サンプルの作成

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# データを作成する。
X, Y = make_blobs(centers=3, n_samples=500)
print(X.shape)  # (500, 2)
print(y.shape)  # (500,)

# サンプル結果描画
##################################################
fig, axes = plt.subplots(figsize=(6, 6))
axes.scatter(X[:,0], X[:,1], alpha=0.5, s=10)
axes.set_xlabel('$x_1$')
axes.set_ylabel('$x_2$')

num_cluster = 3
maxiter = 50

k平均法の numpy による実装例

# ランダムにクラスタの中心を選択する。
centroids = X[np.random.randint(X.shape[0], size=num_cluster)]

# 各データとクラスタの中心との距離を格納する変数
distances = np.zeros([X.shape[0], num_cluster], dtype=np.float64)

for i in range(maxiter):
    # すべての点と各クラスタの中心を計算する。
    for i, c in enumerate(centroids):
        distances[:, i] = np.linalg.norm(X - c, axis=1)
        
    # 最も近いクラスタの中心のクラスに割り当てる。
    classes = np.argmin(distances, axis=1)

    # クラスタの中心を更新する。
    for c in range(k):
        centroids[c] = np.mean(X[classes == c], axis=0)

クラスタリング結果

# クラスタリング結果描画
##################################################
cluster_colors = ['skyblue', 'coral', 'lightgreen']
colors = [cluster_colors[c] for c in classes]

fig, axes = plt.subplots(figsize=(6, 6))
# 各クラスタを描画する。
axes.scatter(X[:, 0], X[:, 1], color=colors, alpha=0.5)
# 各クラスタの中心を描画する。
axes.scatter(centroids[:, 0], centroids[:, 1], color=[
             'blue', 'darkred', 'green'], marker='o', lw=2)

axes.set_xlabel('$x_0$')
axes.set_ylabel('$x_1$')

Answer 2

万が一ご存知でないと大変なので、念の為に申し上げておきますが、実用的なk-meansが使いたいだけならsklearn等にあります。

---

まず基本的に、pandasは速くはないです。

データの読み込み・書き出しだけpandasで行い、中間処理はすべてnumpyを使うのがpythonの場合はおそらくベターです。

また、データをループでなめてインデックスでアクセスするような処理も速くはないです。というか、そもそも算術演算的な処理が遅いです。

numpy・scipyの色々なテクニック、関数を活用し、できるだけベクトル演算にするか、numpy・scipyの内部で処理させるのがベターです。これらのライブラリは内部的には高速なコンパイル言語で実装されており、様々な最適化の工夫がなされているため、pythonで素直に同じアルゴリズムを書くより数桁以上速く処理できることが多いです。

---

余談ですが、そのコードは入出力の記述とアルゴリズムの記述が混ざっていてとても読みづらいです。

モジュール化して、綺麗にしましょう。既存のライブラリのインターフェースを参考にしてください。

---

以上のようなことをコードに反映させた上で、まだ速度に不満があればプロファイリングして高速化していけば良いかと思います。

Comments

[wpspring0300]

丁寧な回答ありがとうございました
教えていただいたことをやってみた結果実用的な速さになりました。
ありがとうございました

Answer 3

処理速度に関係ないとは思いますが、ヒントになりそうなことを。

インクリメントによるインデックス指定を行っている部分は以下のように書き直せそうです。

lista = [0, 1, 2, 4, 6, 10]
for d in lista:
    a = d * 2

また、リストデータのインデックスが欲しい場合は、 enumerate() 関数を使うと、インデックスと値を返してくれますので、以下のように書けます。

a = []
lista = [0, 1, 2, 4, 6, 10]
for i, d in enumerate(lista):
    a[i] = d * 2

更に、内包表記を使うと読みにくくなるかもしれませんが、速度は上がります。
こんな感じで書きます。

lista = [0, 1, 2, 4, 6, 10]
listb = [i * 2 for i in lista]
print(listb)
#=> [0, 2, 4, 8, 12, 20]

参考資料

• 2. 組み込み関数 — Python 3.6.5 ドキュメント
• 内包表記 - Dive Into Python 3 日本語版
• Pythonでenumerateを賢く使う。 - やるだけPython競プロ日誌
• クラスとイテレータ - Dive Into Python 3 日本語版

Answer 4

時系列データのクラスタリングにはtslearnを使うといいようです。

参考URL
https://techblog.nhn-techorus.com/archives/6452
https://blog.brains-tech.co.jp/entry/tslearn-time-series-clustering

私は利用経験はないので何ともわかりませんが、DTWもサポートしているのでないでしょうか。