PythonのK-means関数

Question

方法論を理解するために、Pythonでk-means関数を作成しました。kの値が大きい、より複雑なデータセットでこれを使用しようとしていますが、実行速度が非常に遅くなっています。これを改善する方法について誰かが何かアドバイスはありますか？サンプルデータセットをロードしてアルゴリズムを適用するとともに、以下のコードを提供しました。

def Euc(x,y):
    return math.sqrt(sum([(a - b) ** 2 for a,b in zip(x,y)]))

def K_means(TE,k):
    Iteration = 0
    R = []
    O_a = []
    Epoch = 0
    Tol = 1
    Old_Tol = 2
    Tol_r = []
    start_time = time.time()
    mean_cl = [[random.uniform(TE.iloc[i].min(),TE.iloc[i].max()) for i in range(len(TE.columns))] for c in range(0,k)]
    for n in range(len(TE)):
        D = [Euc(TE.iloc[n].tolist(),mean_cl[c]) for c in range(0,k)]  
        O_a.append(D.index(min(D)))
    while(abs(Old_Tol - Tol) > 0.005):
        Old_Tol = Tol
        Epoch = Epoch + 1
        mean_cl = [TE.iloc[[j for j, x in enumerate(O_a) if x == i]].mean() for i in range(0,k)]
        N_a = []
        for n in range(len(TE)):
            Iteration = Iteration + 1
            D = [Euc(TE.iloc[n].tolist(),mean_cl[c]) for c in range(0,k)] 
            N_a.append(D.index(min(D)))
       Tol = np.mean([x != y for x,y in zip(O_a,N_a)])
        Tol_r.append(Tol)
        O_a = N_a
    R.append(time.time() - start_time)
    R.append(Tol_r)
    R.append(N_a)
    R.append(Iteration)
    return R

def load_Pima():
    url = "http://www.stats.ox.ac.uk/pub/PRNN/pima.tr"
    Pima_training = pd.read_csv(url,sep = '\s+')
    url = "http://www.stats.ox.ac.uk/pub/PRNN/pima.te"
    Pima_testing = pd.read_csv(url,sep = '\s+')
    Pima_training = Pima_training.iloc[1:]
    Pima_testing = Pima_testing.iloc[1:]
    Pima_training.loc[:,"type"] = Pima_training.loc[:,"type"].apply(lambda x : 0 if x == 'Yes' else 1)
    Pima_testing.loc[:,"type"] = Pima_testing.loc[:,"type"].apply(lambda x : 0 if x == 'Yes' else 1)
    Features = Pima_training.loc[:,Pima_training.columns != "type"]
    Means = Features.mean()
    SDs = Features.std()
    for name in Features.columns:
        Pima_training[name] = (Pima_training[name]-Means[name])/SDs[name]
        Pima_testing[name] = (Pima_testing[name]-Means[name])/SDs[name]
    return Pima_training, Pima_testing

Pima_training, Pima_testing = load_Pima()

class_var = "type"
random.seed(2031)
k = 2
TE = Pima_testing
TE = TE.loc[:,TE.columns != class_var]
km = K_means(TE,k)

この関数は、アルゴリズムの実行時間、各エポックでの許容値（クラスター割り当ての変更の％）、最終的なクラスター割り当て、および反復の総数を返します。私はすでに4つのforループを削除しました。これにより、かなり高速になりました。しかし、Pythonプログラミングが不足しているために、これをより効率的にすることができなくなっているのではないかと心配しています。どんな助けでも大歓迎です！

Answer 1

これをさまざまなポイントでベクトル化して、行ごとではなくデータフレーム全体に算術演算を適用できます。

def min_euclidean(df, options):
    """ Returns the index of the series in iterable options for which df - row has minimum
    Euclidean distance """
    return pd.DataFrame(((df - series) ** 2).sum(axis=1, skipna=False) for series in options).idxmin()

def k_means(TE, k):
    iteration = 0
    epoch = 0
    tol = 1
    old_tol = 2
    tols = []
    start_time = time.time()
    mean_cl = [random.uniform(TE.min(), TE.max()) for _ in range(k)]
    o_a = min_euclidean(TE, mean_cl)
    while abs(old_tol - tol) > 0.005:
        old_tol = tol
        epoch += 1
        mean_cl = [TE[o_a == i].mean() for i in range(k)]
        n_a = min_euclidean(TE, mean_cl)
        iteration += len(TE)
        tol = (o_a != n_a).mean()
        tols.append(tol)
        o_a = n_a
    return time.time() - start_time, tols, n_a, iteration

ご了承ください：

• 可能な限り、リストの代わりにPandasシリーズまたはデータフレームを使用します
• mean_clリストのリストではなく、パンダシリーズのリストとして計算します。このようにして、TE速度が遅いの列または行のインデックスを反復処理することを回避します。mean_clデータフレームとして保存することでこれをさらに最適化する方法があるかもしれませんが、そのように操作する明確な方法がわかりません。
• ユークリッド距離の平方根を取る必要はありません-最小距離に関連付けられたインデックスは、2乗された値で機能するのと同じになります
• o_aそしてn_aまた、シリーズとして保存されます。次に(o_a!= n_a).mean()、それらの間の視差を計算するために行うことができます。
• ここでの最大の最適化は、おそらく、min_euclideanデータフレームを反復処理するのではなく、最適化された方法でデータフレーム全体の二乗の差を計算する関数です。

これは、ベクトル化の有用な説明になる可能性があります。Pandasシリーズとデータフレームを最適に操作するには、通常のPythonとは少し異なる考え方が必要になることがよくあります。

編集：これはパンダの代わりにnumpyを使用したバージョンです。これにより、すべての操作が完全にベクトル化され、再び大幅に高速化されます。このStackOverflowの回答からの最適化を使用します。

def k_means(TE, k):
    epoch = 0
    tol = 1
    old_tol = 2
    tols = []
    start_time = time.time()
    te = np.array(TE)
    rows, columns = te.shape
    te3 = te[:, np.newaxis]  # 3d version of te for calculating euclidean more easily
    k_range = np.arange(k)[:, np.newaxis]
    mean_cl = np.random.uniform(te.min(axis=0), te.max(axis=0), size=(k, columns))
    o_a = np.nanargmin(((te3 - mean_cl) ** 2).sum(axis=2), axis=1)
    while abs(old_tol - tol) > 0.005:
        old_tol = tol
        epoch += 1
        m = o_a == k_range     # masks for each value in range 0 to k-1
        mean_cl = m.dot(te) / m.sum(1, keepdims=True)
        n_a = np.nanargmin(((te3 - mean_cl) ** 2).sum(axis=2), axis=1)
        tol = (o_a != n_a).mean()
        tols.append(tol)
        o_a = n_a
    return time.time() - start_time, tols, n_a, epoch * rows