ฟังก์ชัน K-mean ใน Python

Question

ฉันได้เขียนฟังก์ชัน k-mean ใน Python เพื่อทำความเข้าใจเกี่ยวกับระเบียบวิธี ฉันกำลังพยายามใช้สิ่งนี้กับชุดข้อมูลที่ซับซ้อนมากขึ้นโดยมีค่า k มากขึ้น แต่มันทำงานช้ามาก ใครมีคำแนะนำเกี่ยวกับวิธีปรับปรุงสิ่งนี้บ้าง? ฉันได้ให้โค้ดด้านล่างพร้อมกับการโหลดในชุดข้อมูลตัวอย่างและใช้อัลกอริทึม

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)

ฟังก์ชันจะส่งคืนรันไทม์ของอัลกอริทึมความอดทนในแต่ละยุค (% ของการเปลี่ยนแปลงในการกำหนดคลัสเตอร์) การกำหนดคลัสเตอร์สุดท้ายและจำนวนการทำซ้ำทั้งหมด ฉันได้ลบสี่ลูปออกไปแล้วซึ่งทำให้มันเร็วขึ้นเล็กน้อย แต่ฉันกลัวว่าการขาดการเขียนโปรแกรม Python ทำให้ฉันไม่สามารถทำให้สิ่งนี้มีประสิทธิภาพมากขึ้นได้ ขอความช่วยเหลือใด ๆ !

Answer 1

คุณสามารถกำหนดเวกเตอร์ได้ตามจุดต่างๆเพื่อนำเลขคณิตไปใช้กับดาต้าเฟรมทั้งหมดแทนที่จะเป็นทีละแถว

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

โปรดทราบว่า:

• ทุกที่ที่เป็นไปได้เราทำงานกับซีรีส์ Pandas หรือดาต้าเฟรมแทนรายการ
• ฉันคำนวณmean_clเป็นรายชื่อซีรีส์ Pandas แทนที่จะเป็นลิสต์ลิสต์ วิธีนี้เราจะหลีกเลี่ยงการวนซ้ำผ่านดัชนีคอลัมน์หรือแถวTEซึ่งช้ากว่า อาจมีวิธีเพิ่มประสิทธิภาพเพิ่มเติมโดยการจัดเก็บmean_clเป็น dataframe แต่ฉันไม่เห็นวิธีการทำงานที่ชัดเจนด้วยวิธีนี้
• ไม่จำเป็นต้องใช้รากที่สองสำหรับระยะทางแบบยุคลิด - ดัชนีที่เกี่ยวข้องกับระยะทางที่น้อยที่สุดจะเหมือนกับการทำงานกับค่ากำลังสอง
• o_aและn_aยังจัดเก็บเป็นชุด จากนั้นเราสามารถ(o_a!= n_a).mean()คำนวณความเหลื่อมล้ำระหว่างกันได้
• การเพิ่มประสิทธิภาพที่ใหญ่ที่สุดในที่นี้น่าจะเป็นmin_euclideanฟังก์ชันที่คำนวณความแตกต่างกำลังสองสำหรับดาต้าเฟรมทั้งหมดด้วยวิธีที่ดีที่สุดแทนที่จะทำซ้ำผ่านมัน

นี่อาจเป็นคำอธิบายที่เป็นประโยชน์ของการสร้างเวกเตอร์ การทำงานกับซีรีส์ Pandas และดาต้าเฟรมอย่างเหมาะสมมักจะมีวิธีคิดที่แตกต่างจาก Python ทั่วไปเล็กน้อย

แก้ไข: นี่คือเวอร์ชันที่ใช้ numpy แทนแพนด้า สิ่งนี้ทำให้การดำเนินการทั้งหมดเป็นเวกเตอร์อย่างสมบูรณ์และเร็วขึ้นมาก ใช้การเพิ่มประสิทธิภาพจากคำตอบ 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