بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 22: k-NN با چند ویژگی k-NN with Several Features

نزدیک‌ترین همسایه را با چند ویژگی پیدا می‌کنیم: فاصله در چند بُعد، رأی‌گیری بین k همسایه، و انتخاب k خوب.

در این جلسه یاد می‌گیری

درس

در فاز قبل k-NN را با یک ویژگی دیدی: «نزدیک‌ترین مثال را پیدا کن و برچسبش را کپی کن». با یک ویژگی، فاصله فقط abs(a - b) بود. حالا هر میوه دو عدد دارد: وزن و قرمزی. فاصله‌ی دو میوه یعنی چه؟

هر میوه را یک نقطه روی کاغذ شطرنجی تصور کن: وزن روی محور افقی، قرمزی روی محور عمودی. فاصله‌ی دو نقطه همان قانون فیثاغورس است: جذرِ (اختلاف اول به توان ۲ + اختلاف دوم به توان ۲). با سه ویژگی هم همین است، فقط یک جمله اضافه می‌شود؛ کامپیوتر برایش فرقی ندارد چند بُعد باشد.

import math

def distance(a, b):
    total = 0
    for i in range(len(a)):
        total = total + (a[i] - b[i]) ** 2
    return math.sqrt(total)

print(distance([0, 0], [3, 4]))        # 5.0
print(distance([1, 2, 3], [1, 2, 3]))  # 0.0

یک مشکل: وزن حدود ۱۵۰ است و قرمزی حدود ۰.۵. در فاصله، اختلاف وزن (مثلاً ۲۰) همیشه از اختلاف قرمزی (مثلاً ۰.۶) خیلی بزرگ‌تر است، پس قرمزی عملاً نادیده گرفته می‌شود! راه حل: هر ویژگی را به بازه‌ی ۰ تا ۱ بیاور: (x - min) / (max - min). به این نرمال‌سازی می‌گوییم.

weights = [150, 170, 140, 180]
lo, hi = min(weights), max(weights)
scaled = [(w - lo) / (hi - lo) for w in weights]
print(scaled)   # [0.25, 0.75, 0.0, 1.0]

نزدیک‌ترین همسایه: فاصله‌ی نقطه‌ی جدید تا همه‌ی مثال‌ها را حساب کن و کوچک‌ترین را بردار. این دقیقاً همان الگوی «بهترین تا حالا» است که بارها نوشته‌ای.

def nearest(point, X, y):
    best_i = 0
    for i in range(len(X)):
        if distance(point, X[i]) < distance(point, X[best_i]):
            best_i = i
    return y[best_i]

X = [[0.25, 0.9], [0.75, 0.2], [0.0, 0.8], [1.0, 0.3]]
y = ["apple", "orange", "apple", "orange"]
print(nearest([0.3, 0.7], X, y))   # apple

چرا k؟ اگر فقط به یک همسایه نگاه کنیم و آن یکی اشتباه برچسب خورده باشد، ما هم اشتباه می‌کنیم. بهتر است k همسایه‌ی نزدیک را پیدا کنیم و بین برچسب‌هایشان رأی‌گیری کنیم. برای این کار همه‌ی فاصله‌ها را با برچسبشان در یک لیست می‌گذاریم، مرتب می‌کنیم و k تای اول را برمی‌داریم.

def knn(point, X, y, k):
    pairs = []
    for i in range(len(X)):
        pairs.append((distance(point, X[i]), y[i]))
    pairs.sort()
    votes = {}
    for d, label in pairs[:k]:
        votes[label] = votes.get(label, 0) + 1
    return max(votes, key=votes.get)

k را چطور انتخاب کنیم؟ k=1 حساس به یک مثال اشتباه است. k خیلی بزرگ (مثلاً به اندازه‌ی کل داده) همیشه برچسب پرتعدادتر را می‌دهد و اصلاً به نقطه‌ی جدید نگاه نمی‌کند. معمولاً k فرد و کوچک (۳ یا ۵) خوب است؛ فرد، تا رأی‌ها مساوی نشود. راه درست: چند k را امتحان کن و دقت را بشمار.

اشتباه رایج: فراموش کردن math.sqrt؛ البته برای «کدام نزدیک‌تر است» جذر لازم نیست چون ترتیب عوض نمی‌شود، ولی عدد فاصله غلط می‌شود. اشتباه دوم: مقایسه‌ی ویژگی‌های نرمال‌نشده، که عملاً یعنی فقط وزن را می‌بینی.

مثال‌های این جلسه

چالش‌ها

  1. Distance in 2D (آسان)
  2. Scale to 0..1 (آسان)
  3. Any Number of Features (متوسط)
  4. Nearest Neighbour (متوسط)
  5. k-NN Voting (سخت)
  6. Choosing k (سخت)

بیشتر بخوان

← جلسه‌ی 21: ویژگی و برچسب جلسه‌ی 23: آموزش / آزمون →