K-bedeutet Funktion in Python

Question

Ich habe eine k-means-Funktion in Python geschrieben, um die Methodik zu verstehen. Ich versuche, dies für einen komplexeren Datensatz mit einem größeren Wert für k zu verwenden, aber er läuft sehr langsam. Hat jemand Empfehlungen, wie ich das verbessern kann? Ich habe unten Code bereitgestellt, zusammen mit dem Laden eines Beispieldatensatzes und dem Anwenden des Algorithmus.

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)

Die Funktion gibt die Laufzeit des Algorithmus, die Toleranz in jeder Epoche (% der Änderungen der Clusterzuweisung), die endgültigen Clusterzuweisungen und die Gesamtzahl der Iterationen zurück. Ich habe bereits vier for-Schleifen entfernt, was es ziemlich beschleunigt hat. Ich befürchte jedoch, dass mein Mangel an Python-Programmierung mich davon abhält, dies effizienter zu gestalten. Jede Hilfe wird geschätzt!

Answer 1

Sie können dies an verschiedenen Stellen vektorisieren, um die Arithmetik nicht zeilenweise, sondern auf den gesamten Datenrahmen anzuwenden.

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

Beachten Sie, dass:

• Wo immer möglich, arbeiten wir mit Pandas-Serien oder Datenrahmen anstelle von Listen
• Ich berechne mean_clals Liste von Pandas-Serien anstelle einer Liste von Listen. Auf diese Weise vermeiden wir das Durchlaufen der Spalten- oder Zeilenindizes von TE, was langsamer ist. Es gibt möglicherweise eine Möglichkeit, dies durch Speichern mean_clals Datenrahmen weiter zu optimieren , aber ich sehe keine offensichtliche Möglichkeit, auf diese Weise damit zu arbeiten.
• Es ist nicht erforderlich, die Quadratwurzel für den euklidischen Abstand zu ziehen - die mit dem minimalen Abstand verbundenen Indizes sind dieselben wie bei den Quadratwerten
• o_aund n_awerden auch als Serie gespeichert. Wir können dann (o_a!= n_a).mean()die Ungleichheit zwischen ihnen berechnen.
• Die größte Optimierung hier ist wahrscheinlich die min_euclideanFunktion, die die Quadratdifferenz für den gesamten Datenrahmen auf optimierte Weise berechnet, anstatt sie zu durchlaufen.

Dies kann eine hilfreiche Erklärung für die Vektorisierung sein. Das optimale Arbeiten mit Pandas-Serien und Datenrahmen erfordert häufig eine etwas andere Denkweise als in normalem Python.

EDIT: Hier ist eine Version, die Numpy anstelle von Pandas verwendet. Dies vektorisiert alle Operationen vollständig und ist wieder wesentlich schneller. Es verwendet eine Optimierung aus dieser StackOverflow-Antwort .

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