Fungsi K-means dengan Python

Question

Saya telah menulis fungsi k-means dengan Python untuk memahami metodologi. Saya mencoba menggunakan ini pada kumpulan data yang lebih kompleks dengan nilai yang lebih besar untuk k, tetapi ini berjalan sangat lambat. Apakah ada yang punya rekomendasi bagaimana saya bisa memperbaiki ini? Saya telah memberikan kode di bawah ini, bersama dengan memuat dalam contoh dataset dan menerapkan algoritme.

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)

Fungsi mengembalikan runtime algoritme, toleransi di setiap epoch (% perubahan dalam tugas cluster), tugas cluster akhir, dan jumlah total iterasi. Saya telah menghapus empat loop untuk, yang telah mempercepatnya. Tapi saya khawatir kurangnya pemrograman Python saya menahan saya untuk membuat ini lebih efisien. Setiap bantuan dihargai!

Answer 1

Anda dapat membuat vektor ini di berbagai titik untuk menerapkan aritmatika ke seluruh kerangka data daripada baris demi baris.

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

Perhatikan bahwa:

• sedapat mungkin kami bekerja dengan seri Pandas atau kerangka data alih-alih daftar
• Saya menghitung mean_clsebagai daftar seri Pandas, bukan daftar daftar. Dengan cara ini kami menghindari iterasi melalui indeks kolom atau baris TE, yang lebih lambat. Mungkin ada beberapa cara untuk mengoptimalkan ini lebih jauh dengan menyimpan mean_clsebagai kerangka data, tetapi saya tidak dapat melihat cara yang jelas untuk bekerja dengannya seperti itu.
• tidak perlu mengambil akar kuadrat untuk jarak Euclidean - indeks yang terkait dengan jarak minimal akan sama bekerja dengan nilai kuadrat
• o_adan n_ajuga disimpan sebagai seri. Kami kemudian (o_a!= n_a).mean()dapat menghitung perbedaan di antara mereka.
• Pengoptimalan terbesar di sini mungkin adalah min_euclideanfungsi yang menghitung selisih kuadrat untuk seluruh kerangka data dengan cara yang dioptimalkan, daripada mengulanginya.

Ini mungkin penjelasan yang membantu tentang vektorisasi. Bekerja dengan seri Pandas dan kerangka data secara optimal sering kali melibatkan cara berpikir yang sedikit berbeda dari pada Python biasa.

EDIT: Ini adalah versi yang menggunakan numpy, bukan panda. Ini sepenuhnya membuat vektorisasi semua operasi dan secara substansial lebih cepat lagi. Ini menggunakan pengoptimalan dari jawaban StackOverflow ini .

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