Função K-means em Python

Question

Eu escrevi uma função k-means em Python para entender a metodologia. Estou tentando usar isso em um conjunto de dados mais complexo com um valor maior para k, mas está muito lento. Alguém tem alguma recomendação de como posso melhorar isso? Forneci o código abaixo, juntamente com o carregamento de um conjunto de dados de exemplo e a aplicação do algoritmo.

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)

A função retorna o tempo de execução do algoritmo, a tolerância em cada época (% de mudanças na atribuição do cluster), as atribuições finais do cluster e o número total de iterações. Já removi quatro loops for, o que o acelerou um pouco. Mas temo que minha falta de programação Python esteja me impedindo de tornar isso mais eficiente. Qualquer ajuda é apreciada!

Answer 1

Você pode vetorizar isso em vários pontos para aplicar a aritmética a todo o dataframe, em vez de linha por linha.

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

Observe que:

• sempre que possível, trabalhamos com séries Pandas ou dataframes em vez de listas
• Eu calculo mean_clcomo uma lista de séries Pandas em vez de uma lista de listas. Dessa forma, evitamos iterar pelos índices de coluna ou linha de TE, que é mais lento. Pode haver alguma maneira de otimizar isso ainda mais armazenando mean_clcomo um dataframe, mas não consigo ver uma maneira óbvia de trabalhar com isso dessa forma.
• não há necessidade de tirar a raiz quadrada da distância euclidiana - os índices associados à distância mínima serão os mesmos trabalhando com os valores quadrados
• o_ae n_atambém são armazenados em série. Podemos então fazer (o_a!= n_a).mean()para calcular a disparidade entre eles.
• A maior otimização aqui é provavelmente a min_euclideanfunção que calcula a diferença quadrada para todo o dataframe de uma forma otimizada, em vez de iterar por meio dela.

Esta pode ser uma explicação útil da vetorização. Trabalhar com séries e dataframes do Pandas de forma otimizada geralmente envolve uma maneira de pensar ligeiramente diferente do que no Python normal.

EDIT: Aqui está uma versão usando numpy em vez de pandas. Isso vetoriza totalmente todas as operações e é substancialmente mais rápido novamente. Ele usa uma otimização desta resposta 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