Функция K-средних в Python

Question

Я написал функцию k-средних на Python, чтобы понять методологию. Я пытаюсь использовать это в более сложном наборе данных с большим значением 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)

Функция возвращает время выполнения алгоритма, допуск в каждую эпоху (% изменений в назначении кластера), окончательные назначения кластера и общее количество итераций. Я уже удалил четыре цикла 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как список из серии Pandas, а не как список списков. Таким образом, мы избегаем повторения индексов столбца или строки TE, что происходит медленнее. Возможно, есть способ еще больше оптимизировать это, сохранив mean_clкак фрейм данных, но я не вижу очевидного способа работы с ним таким образом.
• нет необходимости извлекать квадратный корень для евклидова расстояния - индексы, связанные с минимальным расстоянием, будут такими же, как при работе с квадратами значений
• o_aи n_aтакже хранятся как серии. Затем мы можем (o_a!= n_a).mean()вычислить разницу между ними.
• Самая большая оптимизация здесь, вероятно, - это min_euclideanфункция, которая вычисляет квадратичную разницу для всего фрейма данных оптимизированным способом, а не повторяет его.

Это может быть полезным объяснением векторизации. Работа с сериями Pandas и фреймами данных в оптимальном режиме часто требует немного другого мышления, чем в обычном Python.

РЕДАКТИРОВАТЬ: вот версия, использующая numpy вместо pandas. Это полностью векторизует все операции и снова значительно быстрее. Он использует оптимизацию из этого ответа 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