جلسهی 6: نزدیکترین همسایه Nearest Neighbour
اولین الگوریتم واقعی یادگیری ماشین: k-NN. میوهی ناشناس همان میوهای است که نزدیکترین مثالها به آن هستند.
در این جلسه یاد میگیری
- میتوانی فاصلهی دو نقطه را با قضیهی فیثاغورس حساب کنی.
- میتوانی نزدیکترین مثال به یک نقطهی تازه را پیدا کنی.
- میدانی k در k-NN یعنی چه و چرا رأیگیری بین چند همسایه بهتر است.
- میتوانی دقت الگوریتم را روی مثالهای تست بسنجی.
درس
یک میوه داری با وزن ۱۵۰ گرم و رنگ قرمز (رنگ را عدد میکنیم: ۰ سبز تا ۱۰ قرمز). سیب است یا لیمو؟ ایدهی نزدیکترین همسایه: به مثالهایی که داریم نگاه کن؛ میوهی تازه همان چیزی است که نزدیکترین مثال به آن است.
# (weight, redness, name)
fruits = [
(150, 9, "apple"), (160, 8, "apple"), (140, 10, "apple"),
(60, 1, "lime"), (70, 2, "lime"), (55, 0, "lime"),
]«نزدیک» یعنی فاصلهی کم. فاصلهی دو نقطه را با فیثاغورس حساب میکنیم: جذرِ (تفاوت اول² + تفاوت دوم²). در پایتون ** 0.5 جذر میگیرد.
def distance(w1, r1, w2, r2):
return ((w1 - w2) ** 2 + (r1 - r2) ** 2) ** 0.5
print(distance(150, 9, 160, 8))
print(distance(150, 9, 60, 1))نزدیکترین را پیدا کن: روی همهی مثالها حلقه بزن، فاصله را حساب کن و کمترین را نگه دار. اسم همان مثال، جواب ماست.
new_w, new_r = 145, 8
best = None
best_d = 10 ** 9
for w, r, name in fruits:
d = distance(new_w, new_r, w, r)
if d < best_d:
best_d = d
best = name
print("I think it is", best)یک همسایه ممکن است اشتباه ثبت شده باشد. بهتر است k همسایهی نزدیک را ببینیم و رأیگیری کنیم. مثلاً k=3: سه نزدیکترین، و اسمی که بیشتر تکرار شده برنده است. این الگوریتم k-NN است.
scored = []
for w, r, name in fruits:
scored.append((distance(new_w, new_r, w, r), name))
scored.sort()
top3 = scored[:3]
print(top3)برای شمردن رأیها از دیکشنری استفاده کن (مثل جلسهی ۳) و با max(votes, key=votes.get) برنده را بگیر.
votes = {}
for d, name in top3:
votes[name] = votes.get(name, 0) + 1
print(votes)
print("winner:", max(votes, key=votes.get))⚠️ مواظب مقیاس باش: وزن از ۵۰ تا ۲۰۰ است ولی رنگ از ۰ تا ۱۰. پس وزن در فاصله خیلی مهمتر میشود و رنگ تقریباً نادیده میماند! دانشمندان داده قبل از k-NN همهی ویژگیها را به یک مقیاس میبرند. در پروژهی جلسهی ۱۲ به این برمیگردیم.
مثالهای این جلسه
- مثال لیست (هوش مصنوعی با پایتون): fruits = [
- مثال تابع (هوش مصنوعی با پایتون): def distance(w1, r1, w2, r2):
- مثال حلقه for (هوش مصنوعی با پایتون): for w, r, name in fruits:
- مثال حلقه for (هوش مصنوعی با پایتون): for w, r, name in fruits: — نزدیکترین همسایه
- مثال دیکشنری (هوش مصنوعی با پایتون): votes[name] = votes.get(name, 0) + 1
چالشها
- Distance (آسان)
- All Distances (آسان)
- The Nearest One (متوسط)
- Three Neighbours (متوسط)
- k-NN Votes (سخت)
- Test the Model (سخت)