پیاده‌سازی الگوریتم k-NN با پایتون

در این تمرین، می‌خواهیم به پیاده‌سازی الگوریتمی به نام «k نزدیک ترین همسایه» یا k-NN بپردازیم که از الگوریتم‌های رایج یادگیری ماشین به حساب می‌آید.

مجموعه داده‌ای که در این تمرین استفاده می‌کنیم، مجموعه‌داده‌ی گل‌های زنبق است. در این مجموعه داده مشخصات ۱۵۰ گل زنبق که در ۳ نوع دسته‌بندی می‌شوند، گردآوری شده است. این مشخصات عبارت‌اند از طول کاسبرگ، عرض کاسبرگ، طول گلبرگ و عرض گلبرگ که همگی به سانتی‌متر هستند. بنابراین با استفاده از این مشخصات، هر گل را می‌توان به‌صورت یک نقطه در فضایی چهاربعدی تصور کرد که این چهار کمیت مختصات آن نقطه را تعیین می‌کنند. همچنین انواع گل زنبق در این مجموعه داده را که عبارت‌اند از زنبق نوک‌زبر، زنبق رنگارنگ و زنبق ویرجینیا، به‌ترتیب با شناسه‌های 0، 1 و 2 نمایش می‌دهیم.

حال می‌خواهیم یک دسته‌بند بسازیم که پس از دیدن نمونه‌هایی از مشخصات گل‌ها و نوعشان (که آن‌ها را نمونه‌های آموزش می‌نامیم)، نوع گل‌های جدید را (که آن‌ها را نمونه‌های آزمون می‌نامیم)، از روی مشخصات‌شان پیش‌بینی کند. اگر همان فضای چهاربعدی گل‌ها را در نظر بگیریم، می‌توانیم حدس بزنیم که گل‌های هم‌نوع در این فضا نزدیک‌ به هم قرار می‌گیرند. حال اگر یک گل جدید ببینیم، می‌توانیم گل‌های نزدیک به آن در این فضا را پیدا کنیم و نوعی که بیشتر تکرار می‌شود را به‌عنوان نوع گل جدید معرفی کنیم.

این ایده‌ی ساده، مبنای دسته‌بند «k نزدیک‌ترین همسایه» یا k-NN است. این دسته‌بند، یک عدد ثابت k را در نظر می‌گیرد و به ازای هر نقطه جدید، k تا نزدیک‌ترین نقطه به آن را پیدا می‌کند و در بین آن‌ها برچسبی که بیشترین تکرار را داشته باشد به‌عنوان برچسب نقطه جدید پیش‌بینی می‌کند. در این تمرین به پیاده‌سازی این دسته‌بند برای مجموعه داده گل‌های زنبق می‌پردازیم.

مشخصات داده

مشخصات و نوع گل‌هایی که برای آموزش استفاده می‌کنیم، به‌ترتیب در آرایه‌های irises و types قرار دارند و مشخصات گل‌هایی که نوع‌شان را می‌خواهیم پیش‌بینی کنیم، در آرایه new_irises قرار دارد. در جدول زیر، ابعاد دقیق و توضیحات مربوط به آرایه‌ها آمده‌اند. در ادامه تعداد نمونه‌های آموزش را n، تعداد نمونه‌های آزمون را m و تعداد بُعدهای هر نمونه را s می‌نامیم.

به کمک کد زیر و با استفاده از کتابخانه‌ی کاربردی نامپای می‌توانیم نسبت به خوانش مجموعه داده‌ی خود اقدام کنیم.

import numpy as np
irises = np.load('irises.npy')
types = np.load('types.npy')
new_irises = np.load('new_irises.npy')
n, m = len(irises), len(new_irises)

فایل‌های مجموعه‌داده را می‌توانید از این لینک دریافت کنید.

محاسبه فاصله‌ها

برای تعیین نوع هر کدام از گل‌های زنبق آرایه‌ی new_irises با روش k-NN، باید فاصله‌ی آن را با تک‌‍تک گل‌های آرایه‌ی irises محاسبه کنیم. بنابراین در گام اول باید آرایه‌ی d با ابعاد (m, n) را مقداردهی کنیم که در خانه d[i, j] مجذور فاصله نقطه متناظر با new_irises[i] و نقطه متناظر با irises[j] قرار می‌گیرد.

def calc_two_loops(new_points, points):
    m, n = len(new_points), len(points)
    d = np.zeros((m, n))
    for i in range(m):
        for j in range(n):
            d[i, j] = np.sum(np.square(new_points[i] - points[j]))
    return d

پیدا کردن k نزدیک‌ترین همسایه (k-NN)

پس از به دست آوردن آرایه مجذور فاصله‌ها، در این بخش باید آرایه k_nearest با ابعاد (m, k) را بسازیم که در آن k_nearest[i] شامل شماره k تا نزدیک‌ترین گل به گلِ new_irises[i] در آرایه irises است (عدد j شماره گل irises[j] را نشان می‌دهد).

k = 10
k_nearest = np.argpartition(d, k, axis=1)[:, :k]
k_nearest

پیدا کردن نوع k نزدیک‌ترین همسایه

در انتها، باید آرایه k_nearest_types با ابعاد (m, k) را بسازیم که در آن k_nearest_types[i] شناسه نوع k تا نزدیک‌ترین گل به گلِ new_irises[i] در آرایه irises را شامل می‌شود.

k_nearest_types = types[k_nearest]

تعیین نوع گل‌ها

در این بخش، کدهای زیر را اجرا می‌کنیم تا آرایه predicted_types به طول m ساخته‌شود که predicted_types[i] شناسه نوع پیش‌بینی شده برای new_irises[i] را نشان می‌دهد و برابر با پرتکرارترین شناسه نوع در سطر k_nearest_types[i] است.

from scipy import stats
predicted_types = stats.mode(k_nearest_types, axis=1).mode.reshape(m)

پس از آن آرایه new_types به طول m را بارگیری می‌کنیم که در آن new_types[i] جواب درست برای گل new_irises[i] را نشان می‌دهد. حال در یک خط، کدی می‌نویسیم که دقت پیش‌بینی‌مان را که برابر با تعداد پیش‌بینی‌های درست تقسیم بر کل پیش‌بینی‌هاست، نمایش دهد.

new_types = np.load('new_types.npy')
accuracy = np.sum(new_types == predicted_types) / m
print('Accuracy:', accuracy)