Fonction K-means en Python

Question

J'ai écrit une fonction k-means en Python pour comprendre la méthodologie. J'essaie de l'utiliser sur un ensemble de données plus complexe avec une valeur plus grande pour k, mais cela fonctionne très lentement. Quelqu'un a-t-il des recommandations sur la façon dont je peux améliorer cela? J'ai fourni le code ci-dessous, ainsi que le chargement d'un exemple de jeu de données et l'application de l'algorithme.

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 fonction renvoie le temps d'exécution de l'algorithme, la tolérance à chaque époque (% des changements dans l'affectation de cluster), les affectations de cluster finales et le nombre total d'itérations. J'ai déjà supprimé quatre boucles for, ce qui l'a accéléré un peu. Mais je crains que mon manque de programmation Python ne me retienne de rendre cela plus efficace. Toute aide est appréciée!

Answer 1

Vous pouvez vectoriser cela à divers points pour appliquer l'arithmétique à l'ensemble de la trame de données plutôt que ligne par ligne.

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

Notez que:

• dans la mesure du possible, nous travaillons avec des séries Pandas ou des dataframes au lieu de listes
• Je calcule mean_clcomme une liste de séries de Pandas au lieu d'une liste de listes. De cette façon, nous évitons d'itérer dans les index de colonne ou de ligne de TE, qui est plus lent. Il existe peut-être un moyen d'optimiser davantage cela en stockant en mean_cltant que dataframe, mais je ne vois pas de manière évidente de travailler avec cela.
• il n'est pas nécessaire de prendre la racine carrée de la distance euclidienne - les indices associés à la distance minimale seront les mêmes en travaillant avec les valeurs au carré
• o_aet n_asont également stockés sous forme de séries. On peut alors faire (o_a!= n_a).mean()pour calculer la disparité entre eux.
• La plus grande optimisation ici est probablement la min_euclideanfonction qui calcule la différence carrée pour l'ensemble de la trame de données de manière optimisée, plutôt que de l'itérer.

Cela peut être une explication utile de la vectorisation. Travailler avec des séries et des dataframes Pandas de manière optimale implique souvent une façon de penser légèrement différente de celle du Python classique.

EDIT: Voici une version utilisant numpy au lieu de pandas. Cela vectorise entièrement toutes les opérations et est à nouveau sensiblement plus rapide. Il utilise une optimisation de cette réponse 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