Hàm K-mean trong Python

Question

Tôi đã viết một hàm k-mean bằng Python để hiểu phương pháp. Tôi đang cố gắng sử dụng điều này trên một tập dữ liệu phức tạp hơn với giá trị lớn hơn cho k, nhưng nó đang chạy siêu chậm. Có ai có bất kỳ khuyến nghị nào về cách tôi có thể cải thiện điều này không? Tôi đã cung cấp mã bên dưới, cùng với việc tải tập dữ liệu mẫu và áp dụng thuật toán.

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)

Hàm trả về thời gian chạy của thuật toán, dung sai tại mỗi kỷ nguyên (% thay đổi trong phép gán cụm), phép gán cụm cuối cùng và tổng số lần lặp. Tôi đã loại bỏ bốn vòng lặp for, điều này đã tăng tốc nó lên khá nhiều. Nhưng tôi sợ rằng việc thiếu lập trình Python của tôi đang cản trở tôi làm cho việc này hiệu quả hơn. Bất kỳ trợ giúp được đánh giá cao!

Answer 1

Bạn có thể vectơ hóa điều này ở nhiều điểm khác nhau để áp dụng số học cho toàn bộ khung dữ liệu thay vì từng hàng một.

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

Lưu ý rằng:

• bất cứ khi nào có thể, chúng tôi làm việc với chuỗi hoặc khung dữ liệu Pandas thay vì danh sách
• Tôi tính toán mean_clnhư một danh sách các chuỗi Gấu trúc thay vì một danh sách các danh sách. Bằng cách này, chúng tôi tránh lặp qua các chỉ số cột hoặc hàng, chỉ số TEnày chậm hơn. Có thể có một số cách để tối ưu hóa điều này hơn nữa bằng cách lưu trữ mean_cldưới dạng khung dữ liệu, nhưng tôi không thể thấy một cách rõ ràng để làm việc với nó theo cách đó.
• không cần lấy căn bậc hai cho khoảng cách Euclide - các chỉ số liên quan đến khoảng cách tối thiểu sẽ hoạt động giống nhau với các giá trị bình phương
• o_avà n_acũng được lưu trữ dưới dạng chuỗi. Sau đó chúng ta có thể (o_a!= n_a).mean()tính toán sự chênh lệch giữa chúng.
• Tối ưu hóa lớn nhất ở đây có lẽ là min_euclideanchức năng tính toán sự khác biệt bình phương cho toàn bộ khung dữ liệu theo cách được tối ưu hóa, thay vì lặp qua nó.

Đây có thể là một lời giải thích hữu ích về vectơ hóa. Làm việc với chuỗi và khung dữ liệu Pandas một cách tối ưu thường liên quan đến cách suy nghĩ hơi khác so với Python thông thường.

CHỈNH SỬA: Đây là một phiên bản sử dụng numpy thay vì gấu trúc. Điều này hoàn toàn vectơ hóa tất cả các hoạt động và nhanh hơn đáng kể một lần nữa. Nó sử dụng một tối ưu hóa từ câu trả lời StackOverflow này .

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