K-Python'da işlev anlamına gelir

Question

Metodolojiyi anlamak için Python'da bir k-ortalamalı fonksiyon yazdım. Bunu k için daha büyük bir değere sahip daha karmaşık bir veri kümesinde kullanmaya çalışıyorum, ancak çok yavaş çalışıyor. Bunu nasıl iyileştirebileceğime dair herhangi bir tavsiyesi olan var mı? Örnek bir veri kümesini yükleme ve algoritmayı uygulama ile birlikte aşağıda kodu sağladım.

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)

İşlev, algoritmanın çalışma zamanını, her dönemdeki toleransı (küme atamasındaki değişikliklerin yüzdesi), son küme atamalarını ve toplam yineleme sayısını döndürür. Zaten dört döngüyü kaldırdım, bu da onu biraz hızlandırdı. Ancak Python programlama eksikliğimin beni bunu daha verimli hale getirmekten alıkoyduğundan korkuyorum. Herhangi bir yardım takdir edilmektedir!

Answer 1

Satır satır yerine tüm veri çerçevesine aritmetik uygulamak için bunu çeşitli noktalarda vektörleştirebilirsiniz.

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

Bunu not et:

• Mümkün olan her yerde, listeler yerine Pandas serisi veya veri çerçeveleri ile çalışıyoruz
• mean_clListe listesi yerine Pandalar dizisi olarak hesaplıyorum . Bu şekilde TE, daha yavaş olan sütun veya satır indekslerinde yinelemekten kaçınırız . Bunu mean_clbir veri çerçevesi olarak depolayarak daha fazla optimize etmenin bir yolu olabilir , ancak bu şekilde çalışmanın bariz bir yolunu göremiyorum.
• Öklid mesafesi için karekök almaya gerek yoktur - minimum mesafeyle ilişkili indisler, kare değerlerle aynı şekilde çalışır.
• o_ave n_aayrıca seri olarak saklanır. Sonra yapabiliriz (o_a!= n_a).mean()aralarındaki farkı hesaplamak için.
• Buradaki en büyük optimizasyon muhtemelen min_euclideantüm veri çerçevesi için kare farkını yinelemek yerine optimize edilmiş bir şekilde hesaplayan işlevdir.

Bu , vektörleştirmenin faydalı bir açıklaması olabilir. Pandalar serisi ve veri çerçeveleriyle en uygun şekilde çalışmak, genellikle normal Python'dakinden biraz farklı bir düşünme biçimini içerir.

DÜZENLEME: İşte pandalar yerine numpy kullanan bir sürüm. Bu, tüm işlemleri tamamen vektörleştirir ve yine önemli ölçüde daha hızlıdır. Bu StackOverflow yanıtından bir optimizasyon kullanır .

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