Funzione K-significa in Python

Question

Ho scritto una funzione k-means in Python per comprendere la metodologia. Sto cercando di usarlo su un set di dati più complesso con un valore maggiore per k, ma funziona molto lentamente. Qualcuno ha qualche consiglio su come posso migliorarlo? Ho fornito il codice di seguito, insieme al caricamento in un set di dati di esempio e all'applicazione dell'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)

La funzione restituisce il runtime dell'algoritmo, la tolleranza in ogni epoca (% di modifiche nell'assegnazione del cluster), le assegnazioni finali del cluster e il numero totale di iterazioni. Ho già rimosso quattro cicli for, il che lo ha velocizzato un po '. Ma temo che la mia mancanza di programmazione Python mi stia trattenendo dal renderlo più efficiente. Qualsiasi aiuto è apprezzato!

Answer 1

Puoi vettorializzarlo in vari punti per applicare l'aritmetica all'intero dataframe piuttosto che riga per riga.

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

Notare che:

• ove possibile lavoriamo con serie Pandas o dataframe invece che con elenchi
• Calcolo mean_clcome un elenco di serie Panda invece di un elenco di elenchi. In questo modo evitiamo di scorrere gli indici di colonna o riga di TE, che è più lento. Potrebbe esserci un modo per ottimizzarlo ulteriormente archiviandolo mean_clcome dataframe, ma non riesco a vedere un modo ovvio di lavorarci in questo modo.
• non è necessario prendere la radice quadrata per la distanza euclidea - gli indici associati alla distanza minima saranno gli stessi lavorando con i valori al quadrato
• o_ae n_asono anche memorizzati come serie. Possiamo quindi fare (o_a!= n_a).mean()per calcolare la disparità tra di loro.
• La più grande ottimizzazione qui è probabilmente la min_euclideanfunzione che calcola la differenza quadrata per l'intero dataframe in modo ottimizzato, piuttosto che iterare attraverso di esso.

Questa può essere un'utile spiegazione della vettorizzazione. Lavorare con le serie Pandas e i dataframe in modo ottimale spesso implica un modo di pensare leggermente diverso rispetto al normale Python.

EDIT: ecco una versione che usa numpy invece di panda. Ciò vettorizza completamente tutte le operazioni ed è nuovamente sostanzialmente più veloce. Utilizza un'ottimizzazione da questa risposta 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