الگوریتم K-نزدیک‌ترین همسایه (KNN) و معیارهای فاصله

بسیاری از مسائل یادگیری ماشین را می‌توان بدون ساخت مدل‌های پیچیده یا صرف زمان طولانی برای آموزش، با تکیه بر تشابه میان داده‌ها حل کرد. الگوریتم K-نزدیک‌ترین همسایه (K-Nearest Neighbors یا KNN) ساده‌ترین رویکرد برای این کار است که مستقیماً با ذخیره‌سازی داده‌های آموزشی و مقایسه‌ی فاصله‌ها پیش‌بینی انجام می‌دهد.

درک سازوکار فاصله‌ها، انتخاب مقدار مناسب K و چالش‌هایی مانند نفرین ابعاد (Curse of Dimensionality)، زیربنای سیستم‌های مدرنی چون پایگاه‌های داده برداری (Vector Databases)، جستجوی معنایی و بازیابی اطلاعات در خطوط لوله‌ی RAG را شکل می‌دهد.

در این درس علاوه بر پیاده‌سازی الگوریتم طبقه‌بندی و رگرسیون KNN از صفر، روش‌های مختلف محاسبه‌ی فاصله (L1، L2، کسینوسی و مینکوفسکی) و ساختارهای درختی نظیر KD-Tree را برای بهینه‌سازی سرعت جستجو بررسی می‌کنیم.

همه‌چیز را ذخیره کن؛ با نگاه کردن به همسایه‌ها پیش‌بینی کن. ساده‌ترین الگوریتمی که واقعاً کار می‌کند.

اهداف یادگیری

• پیاده‌سازی طبقه‌بندی و رگرسیون KNN از صفر با مقدار K قابل تنظیم و رأی‌گیری وزن‌دار بر اساس فاصله
• مقایسه‌ی معیارهای فاصله‌ی L1، L2، کسینوسی و مینکوفسکی و انتخاب معیار مناسب برای هر نوع داده
• توضیح نفرین ابعاد (curse of dimensionality) و نشان دادن دلایل افت عملکرد KNN در فضاهای با ابعاد بالا
• ساخت یک درخت KD (یا KD-tree) برای جستجوی کارآمد نزدیک‌ترین همسایه و تحلیل شرایط برتری آن نسبت به جستجوی جامع (brute-force)

صورت مسئله

مجموعه‌داده‌ای در دست دارید و یک نقطه‌ی جدید وارد می‌شود. باید برچسب آن را مشخص یا مقدارش را پیش‌بینی کنید. به‌جای یادگیری پارامترها از داده‌ها (مثل رگرسیون خطی یا SVM)، کافی است K نقطه‌ی آموزشیِ نزدیک‌تر به این نقطه‌ی جدید را پیدا کنید و اجازه دهید رأی بدهند.

این سازوکار K-نزدیک‌ترین همسایه (K-nearest neighbors یا KNN) است. خبری از فاز آموزش نیست؛ هیچ پارامتری برای یادگیری وجود ندارد؛ هیچ تابع زیانی (loss) بهینه‌سازی نمی‌شود. کل داده‌های آموزشی را ذخیره می‌کنید و فاصله‌ها را درست در زمان پیش‌بینی به‌دست می‌آورید.

شاید بیش‌ازحد ساده به‌نظر برسد، اما KNN در بسیاری از مسائل، به‌ویژه با مجموعه‌داده‌های کوچک تا متوسط، به‌طور غافلگیرکننده‌ای رقابتی است. درک عمیق آن مفاهیم بنیادینی را آشکار می‌کند: انتخاب معیار فاصله (مرتبط با درس 14 از فاز 1)، نفرین ابعاد، و تفاوت میان یادگیری تنبل (lazy) و یادگیری مشتاق (eager).

ردپای KNN در سراسر هوش مصنوعی مدرن هم دیده می‌شود، فقط با نام‌هایی متفاوت. پایگاه‌های داده برداری (Vector databases) جستجوی KNN را روی امبدینگ‌ها اجرا می‌کنند. تولید تقویت‌شده با بازیابی (RAG) برای پیدا کردن K تکه متن نزدیک‌تر استفاده می‌شود. سیستم‌های پیشنهاددهنده کاربران یا آیتم‌های مشابه را می‌یابند. الگوریتم همان است؛ تنها مقیاس و ساختار داده‌ها تفاوت دارند.

مفاهیم پایه

سازوکار KNN

فرض کنید مجموعه‌داده‌ای از نقاط برچسب‌دار و یک نقطه‌ی پرس‌وجوی جدید (query point) دارید:

1. فاصله‌ی نقطه‌ی پرس‌وجو را با تک‌تک نقاط مجموعه‌داده حساب کنید
2. فاصله‌ها را مرتب کنید
3. K نقطه‌ی نزدیک‌تر را جدا کنید
4. برای طبقه‌بندی: رأی اکثریت بین این K همسایه را بگیرید
5. برای رگرسیون: میانگین (یا میانگین وزن‌دار) مقادیر این K همسایه را حساب کنید

کل الگوریتم همین است. بدون برازش، بدون گرادیان کاهشی، بدون دوره (epoch).

انتخاب K

تنها ابرپارامتر مدل K است که موازنه‌ی بایاس و واریانس (bias-variance trade-off) را کنترل می‌کند:

یک نقطه‌ی شروع رایج برای مجموعه‌داده‌ای با $N$ نقطه، $K = \sqrt{N}$ است. در مسائل طبقه‌بندی دودویی، K را عددی فرد انتخاب کنید تا کار به تساوی آرا نکشد.

معیارهای فاصله

تابع فاصله مشخص می‌کند «نزدیک» دقیقاً به چه معناست. معیارهای متفاوت به همسایه‌های متفاوت و در نتیجه به پیش‌بینی‌های متفاوتی ختم می‌شوند.

فاصله‌ی L2 (اقلیدسی): حالت پیش‌فرض و همان فاصله‌ی خط مستقیم است.

$$d(a, b) = \sqrt{\sum_i (a_i - b_i)^2}$$

این معیار به مقیاس ویژگی‌ها حساس است؛ بنابراین قبل از به‌کارگیری L2 در KNN، حتماً ویژگی‌ها را استانداردسازی کنید.

فاصله‌ی L1 (منهتن): مجموع قدر مطلق اختلاف‌ها را حساب می‌کند. چون اختلاف‌ها را به توان دو نمی‌رساند، نسبت به داده‌های پرت (outliers) مقاوم‌تر از L2 عمل می‌کند.

$$d(a, b) = \sum_i \lvert a_i - b_i \rvert$$

فاصله‌ی کسینوسی: زاویه‌ی بین بردارها را فارغ از اندازه‌ی آن‌ها اندازه می‌گیرد. برای داده‌های متنی و امبدینگ حیاتی است.

$$d(a, b) = 1 - \frac{a \cdot b}{\lVert a \rVert \, \lVert b \rVert}$$

فاصله‌ی مینکوفسکی: با استفاده از پارامتر $p$، دو معیار L1 و L2 را تعمیم می‌دهد.

$$\begin{aligned} & d(a, b) = \left( \sum_i \lvert a_i - b_i \rvert^p \right)^{1/p} \\[6pt] & p=1\text{: Manhattan} \\ & p=2\text{: Euclidean} \\ & p \to \infty\text{: Chebyshev (max absolute difference)} \end{aligned}$$

انتخاب معیار فاصله مستقیماً به نوع داده‌ها بستگی دارد:

مدل KNN وزن‌دار

در KNN استاندارد، همه‌ی K همسایه وزن یکسانی دارند. اما منطقی است همسایه‌ای در فاصله‌ی 0.1 تأثیر بسیار بیشتری نسبت به همسایه‌ای در فاصله‌ی 5.0 داشته باشد.

در KNN وزن‌دار بر اساس فاصله، وزن هر همسایه با عکس فاصله‌اش تعیین می‌شود:

$$\begin{aligned} & \text{weight}_i = \frac{1}{\text{distance}_i + \epsilon} \\[6pt] & \text{For classification: weighted vote} \\ & \text{For regression: weighted average} = \frac{\sum_i w_i y_i}{\sum_i w_i} \end{aligned}$$

مقدار $\epsilon$ جلوی تقسیم بر صفر را در حالتی می‌گیرد که نقطه‌ی پرس‌وجو دقیقاً روی یکی از نقاط آموزشی بیفتد.

این رویکرد حساسیت کمتری به انتخاب K دارد؛ چون سهم همسایه‌های دوردست در هر صورت بسیار ناچیز است.

نفرین ابعاد

با افزایش ابعاد داده‌ها، عملکرد KNN افت می‌کند. این یک فرضیه‌ی مبهم نیست، واقعیتی ریاضی است.

مسئله‌ی اول: همگرایی فاصله‌ها. با افزایش بعد، نسبت بیشترین فاصله به کمترین فاصله به سمت 1 میل می‌کند. در نتیجه همه‌ی نقاط نسبت به پرس‌وجو تقریباً در فاصله‌ای یکسان قرار می‌گیرند.

In d dimensions, for random uniform points:

d=2:    max_dist / min_dist = varies widely
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

When all distances are nearly equal, "nearest" is meaningless.

مسئله‌ی دوم: انفجار حجم فضا. برای گنجاندن K همسایه درون کسری مشخص از کل داده‌ها، شعاع جستجو باید آن‌قدر باز شود که بخش بسیار بزرگی از فضای ویژگی را بپوشاند. در ابعاد بالا، مفهوم «همسایگی» کم‌کم کل فضا را در بر می‌گیرد.

مسئله‌ی سوم: حاکمیت گوشه‌ها. در یک ابرمکعب واحد با d بعد، بیشتر حجم در گوشه‌ها متمرکز است نه در مرکز. با رشد d، حجم کره‌ای که درون این مکعب محاط شده به سمت صفر میل می‌کند.

پیامد عملی این است که KNN تا حدود 20 الی 50 ویژگی کارایی خوبی دارد. بالاتر از این مقدار، باید پیش از اجرای KNN ابعاد را کاهش داد (با روش‌هایی مثل PCA، UMAP یا t-SNE)، یا از ساختارهای جستجوی درختی استفاده کرد که بعد ذاتیِ پایین‌تر داده‌ها را به کار می‌گیرند.

درخت‌های KD: جستجوی سریع نزدیک‌ترین همسایه

در روش جستجوی جامع، فاصله‌ی پرس‌وجو با تک‌تک نقاط آموزشی محاسبه می‌شود؛ یعنی پیچیدگی زمانی $O(n \cdot d)$ به‌ازای هر پرس‌وجو. این کار برای مجموعه‌داده‌های بزرگ بسیار کند است.

یک درخت KD فضا را به‌صورت بازگشتی و در امتداد محورهای ویژگی تقسیم‌بندی می‌کند. در هر سطح، تقسیم روی میانه‌ی داده‌ها در یکی از ابعاد انجام می‌شود.

برای پیدا کردن نزدیک‌ترین همسایه، درخت را تا رسیدن به برگِ حاوی پرس‌وجو پایین می‌رویم، سپس به عقب برمی‌گردیم (backtrack) و تنها بخش‌های مجاوری را بررسی می‌کنیم که شانس داشتن نقاط نزدیک‌تر را داشته باشند.

میانگین زمان پرس‌وجو در ابعاد پایین برابر با $O(\log n)$ است. اما درخت‌های KD در ابعاد بالا ($d > 20$) دچار افت عملکرد شده و پیچیدگی آن‌ها به $O(n)$ می‌رسد، چرا که بازگشت به عقب شاخه‌های (branches) کمتر و کمتری را حذف می‌کند.

درخت‌های بال (Ball Trees): گزینه‌ای بهتر برای ابعاد متوسط

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

مزایای آن در مقایسه با درخت KD:

• عملکرد بهتر در ابعاد متوسط (تا حدود 50 بعد)
• مدیریت مناسب ساختارهایی که با محورها هم‌راستا نیستند
• حجم‌های محاط‌کننده‌ی فشرده‌تر که هرس کردن شاخه‌های بیشتری را هنگام جستجو امکان‌پذیر می‌کند

هر دو درخت KD و بال الگوریتم‌های دقیق هستند. برای جستجوهای واقعاً بزرگ‌مقیاس (میلیون‌ها نقطه با صدها بعد)، روش‌های تقریبی نزدیک‌ترین همسایه (مانند HNSW، IVF و کوانتیزاسیون ضربی یا product quantization) به کار می‌روند؛ موضوعاتی که در درس 14 از فاز 1 به آن‌ها پرداخته شده است.

یادگیری تنبل در مقایسه با یادگیری مشتاق

الگوریتم KNN یک یادگیرنده‌ی تنبل است: در زمان آموزش هیچ کاری انجام نمی‌دهد و همه‌ی محاسبات را به زمان پیش‌بینی موکول می‌کند. در مقابل، بیشتر الگوریتم‌ها (مانند رگرسیون خطی، SVMها و شبکه‌های عصبی) یادگیرنده‌های مشتاق هستند؛ آن‌ها در زمان آموزش محاسبات سنگینی انجام می‌دهند تا مدلی جمع‌وجور بسازند و در عوض پیش‌بینی‌های سریعی ارائه دهند.

یادگیری تنبل در شرایط زیر گزینه‌ای ایده‌آل است:

• داده‌ها مرتب تغییر می‌کنند (افزودن یا حذف نقاط بدون نیاز به بازآموزی)
• به تعداد بسیار کمی پیش‌بینی نیاز است
• به دنبال زمان آموزش صفر هستید
• مجموعه‌داده آن‌قدر کوچک است که جستجوی جامع پاسخ‌گوی نیاز است

رگرسیون با KNN

در رگرسیون با KNN، به‌جای رأی اکثریت، میانگین مقادیر هدف (target) در K همسایه محاسبه می‌شود.

$$\begin{aligned} & \text{prediction} = \frac{1}{K} \sum_{i \in K \text{ nearest neighbors}} y_i \\[6pt] & \text{Or with distance weighting:} \\ & \text{prediction} = \frac{\sum_i w_i y_i}{\sum_i w_i} \quad \text{where } w_i = \frac{1}{\text{distance}_i + \epsilon} \end{aligned}$$

پیش‌بینی‌های رگرسیون KNN به شکل پله‌ای-ثابت (یا در صورت وزن‌دهی، هموارِ تکه‌تکه) خواهد بود. این مدل توانایی برون‌یابی (extrapolation) فراتر از محدوده‌ی داده‌های آموزشی را ندارد؛ اگر مقادیر هدف آموزشی بین 0 و 100 باشند، KNN هرگز عددی مثل 200 را پیش‌بینی نخواهد کرد.

پیاده‌سازی از صفر

گام 1: توابع فاصله

توابع فاصله‌ی L1، L2، کسینوسی و مینکوفسکی را پیاده‌سازی می‌کنیم. این بخش مستقیماً با درس 14 از فاز 1 مرتبط است.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

گام 2: طبقه‌بند و رگرسیون KNN

پیاده‌سازی کامل KNN با امکان تنظیم K، انتخاب معیار فاصله و قابلیت اختیاریِ وزن‌دهی فاصله‌ای:

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

گام 3: پیاده‌سازی درخت KD برای جستجوی کارآمد

ساخت درخت KD از صفر که فضا را به‌صورت بازگشتی حول میانه‌ی هر بعد خرد می‌کند.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # افراز بازگشتی داده‌ها
        self.axis = depth % len(X[0])
        # تقسیم بر اساس میانهٔ محور فعلی
        ...

    def query(self, point, k=1):
        # پیمایش تا برگ، سپس بازگشت به عقب (backtrack)
        ...

پیاده‌سازی کامل به همراه توابع کمکی و مثال‌ها در فایل code/knn.py در دسترس است.

گام 4: مقیاس‌بندی ویژگی‌ها

الگوریتم KNN به مقیاس‌بندی ویژگی‌ها (feature scaling) نیاز دارد، زیرا فاصله‌ها به‌شدت به اندازه‌ی عددی ویژگی‌ها وابسته‌اند. ویژگی‌ای در بازه‌ی 0 تا 1000، اثر ویژگی دیگری در بازه‌ی 0 تا 1 را به‌کلی خنثی خواهد کرد.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

استفاده از ابزارهای واقعی

پیاده‌سازی با کتابخانه‌ی scikit-learn:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")

کتابخانه‌ی scikit-learn اگر حجم داده‌ها کافی و تعداد ابعاد کم باشد، به‌طور خودکار از درخت‌های KD یا بال استفاده می‌کند. برای داده‌های با ابعاد بالا، روش جستجوی جامع جایگزین می‌شود. این سازوکار از طریق پارامتر algorithm قابل کنترل است.

برای جستجوی نزدیک‌ترین همسایه در مقیاس‌های بزرگ (میلیون‌ها بردار)، از FAISS، Annoy یا پایگاه‌های داده برداری استفاده کنید:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

تمرین‌ها

1. طبقه‌بندی KNN را روی داده‌ای 2D با 3 کلاس پیاده‌سازی کنید. مرز تصمیم‌گیری را برای مقادیر $K=1$، $K=5$، $K=15$ و $K=N$ رسم کنید و روند گذار از بیش‌برازش به کم‌برازش را بررسی کنید.

2. تعداد 1000 نقطه‌ی تصادفی در ابعاد 2، 5، 10، 50، 100 و 500 بسازید. در هر بعد، نسبت بیشترین فاصله‌ی دوتایی به کمترین فاصله‌ی دوتایی را حساب کنید. این نسبت را در برابر بعد رسم کنید تا نفرین ابعاد به‌صورت بصری نمایش داده شود.

3. در یک مسئله‌ی طبقه‌بندی متن با بردارهای TF-IDF، معیارهای فاصله‌ی L1، L2 و کسینوسی را با هم مقایسه کنید. کدام معیار دقت بالاتری به‌دست می‌دهد؟ چرا معیار کسینوسی معمولاً برای متن گزینه‌ی بهتری است؟

4. یک درخت KD پیاده‌سازی کنید و زمان پرس‌وجوی آن را در مقایسه با روش جامع روی مجموعه‌داده‌های 1k، 10k و 100k نقطه‌ای در ابعاد 2D، 10D و 50D بسنجید. درخت KD از چه بعدی به بعد برتری سرعتی خود را نسبت به جستجوی جامع از دست می‌دهد؟

5. یک مدل رگرسیون KNN وزن‌دار برای $y = \sin(x) + \text{noise}$ بسازید. آن را با KNN بدون وزن برای مقادیر $K=3, 10, 30$ مقایسه کنید و نشان دهید وزن‌دهی چگونه پیش‌بینی‌های هموارتری، به‌ویژه برای Kهای بزرگ، تولید می‌کند.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Cover & Hart: Nearest Neighbor Pattern Classification (1967) — مقاله‌ی بنیادین KNN که ثابت می‌کند نرخ خطای آن حداکثر دو برابر خطای بهینه‌ی بیز (Bayes optimal) است.
• Friedman, Bentley, Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) — مقاله‌ی اصلی درخت KD برای یافتن بهترین تطابق‌ها در زمان میانگین لگاریتمی.
• Beyer et al.: When Is "Nearest Neighbor" Meaningful? (1999) — تحلیلی فرموله‌شده و دقیق پیرامون اثر نفرین ابعاد بر مسئله‌ی نزدیک‌ترین همسایه.
• مستندات الگوریتم‌های همسایگی در scikit-learn — راهنمای کاربردی همراه با معیارهای انتخاب الگوریتم.
• FAISS: A Library for Efficient Similarity Search — کتابخانه‌ی متا (Meta) برای جستجوی تقریبی نزدیک‌ترین همسایه در مقیاس میلیارد بردار.