https://virgool.ir/feed/@amirhoseinahmadloofa2026-11-12 07:53:48https://virgool.ir/images/default-avatar.jpghttps://virgool.ir/@amirhoseinahmadloohttps://virgool.ir/@amirhoseinahmadloo/مبانی-یادگیری-ماشین-الگوریتم-کِی-نزدیک-ترین-همسایهk-nearest-neighbors-ekk72mfbepqqالگوریتم "K-نزدیک‌ترین همسایه” یا (KNN)، یک الگوریتم ساده با پیاده سازی آسان است که در دسته الگوریتم های نظارت شده قرار میگیرد و میتوان آن را در حل مسائل طبقه بندی (Classification) و رگرسیون(Regression) استفاده کرد. که در ادامه، به زبان خیلی ساده به تشریح آن میپردازیم.یک الگوریتم یادگیری ماشین نظارت شده، الگوریتمی است که برای تولید خروجی مناسب با استفاده از داده های بدون برچسب به عنوان ورودی، بایستی با داده های ورودی برچسب دار آموزش ببیند.تصور کنید که رایانه یک کودک است و ما ناظر او هستیم (والدین، معلم یا ...) و میخواهیم کودک یاد بگیرد که یک خرگوش چه شکلی است. به کودک چندین تصویر نشان میدهیم که تعدادی از آنها تصویر خرگوش و بقیه تصاویر دیگر حیوانات است. زمانی که به تصویر یک خرگوش میرسیم با صدای بلند میگوییم "خرگوش"، و زمانی که به تصویر دیگر حیوانات میرسیم میگوییم "خرگوش نیست". بعد از اینکه این کار را چندین بار انجام بدهیم، کودک میتواند با دقت قابل توجهی تصویر یک خرگوش را از حیوانات دیگر تشخیص دهد. به این روش یادگیری نظارت شده میگویند.از الگوریتم های نظارت شده در یادگیری ماشین برای حل مسائل طبقه بندی و یا رگرسیون استفاده میشود.یک مسئله طبقه بندی دارای یک مقدار گسسته به عنوان خروجی است، به این معنی که "خرگوش است" و "خرگوش نیست" میتواند خروجی باشد و چیزی بین این دو وجود ندارد. یا به عنوان مثال داده هایی که مشخص میکند آیا افراد پیتزای آناناس "دوست دارند" یا "دوست ندارند".این تصویر مثالی ابتدائی از داده های مسائل طبقه بندی را نمایش میدهد. در اینجا ما یک یا دسته ای از "پیش بینی کننده‌ها" (predictor) و یک "برچسب"داریم و تلاش میکنیم با توجه به سن افراد، پیش بینی کنیم که آیا آنها پیتزای آناناس دوست دارند(1) یا خیر(0)، که سن فرد نقش predictor را دارد و معمولا خروجی (برچسب) را به صورت یک عدد صحیح مانند 1 یا 0 نشان میدهیم که البته در این مثال این اعداد کاملاً نمایشی هستند و عملیات ریاضی روی آنها انجام نمیشود. به این دلیل که ما این اعداد را به جای "دوست دارد" و "دوست ندارد" استفاده کردیم و نمیتوانیم این دو مفهوم را جمع ببندیم یا عملیات ریاضی دیگری روی آنها انجام دهیم.یک مسئله رگرسیون یک عدد حقیقی(عددی با قسمت اعشار) به عنوان خروجی دارد. به عنوان مثال، در جدول زیر میتوانیم با استفاده از داده های مربوط به قد افراد، وزن آنها را تخمین بزنیم.داده هایی که در یک تجزیه و تحلیل رگرسیونی داریم چیزی شبیه به داده های جدول بالا هستند. یک یا مجموعه ای از متغیر های مستقل داریم و یک متغیر وابسته یا نامستقل، که میخواهیم با استفاده از متغیر های مستقل، آنها را حدس بزنیم. در جدول بالا، قد یک متغیر مستقل و وزن یک متغیر وابسته یا نامستقل است.معمولا به هر سطر از داده، مثال، observation یا data point گفته میشود و به هر ستون (به جز برچسب و متغیر وابسته) یک پیش بینی کننده (predictor)، بُعد (dimension)، ویژگی (feature) یا متغیر مستقل (independent variable) گفته میشود.در یک الگوریتم بدون نظارت در یادگیری ماشین، از داده های بدون برچسب استفاده میکنیم، به زبان دیگر هیچ معلمی (برچسب) به کودک (رایانه) نمیگوید که او اشتباهی کرده است یا خیر.بر خلاف یادگیری نظارت شده که سعی میکند با استفاده از داده های ورودی ما، یاد بگیرد و زمانی که داده های بدون برچسب به آن دادیم بتواند پیش بینی هایی انجام دهد، یادگیری بدون نظارت سعی میکند ساختار اساسی داده ها را بیاموزد تا بتواند دید کلی بهتری به داده ها به ما بدهد.کِی-نزدیک‌ترین همسایه (k-nearest neighbors)الگوریتم KNN فرض را بر این میگذارد که موارد مشابه در مجاورت یکدیگر وجود دارد و به هم نزدیک هستند."کبوتر با کبوتر، باز با باز"این تصویر نشان میدهد که نقاط داده مشابه، چگونه در نزدیکی یکدیگر قرار دارندتوجه کنید که در تصویر بالا در اکثر مواقع نقاط داده مشابه به یکدیگر نزدیک‌تر هستند، برای اینکه این الگوریتم مفید واقع شود نیاز هست که این فرض تا حدی برقرار باشد. KNN میزان شباهت داده ها را با استفاده از عملیات های ریاضی میسنجد و فاصله بین نقاط را روی یک نمودار محاسبه میکند.نکته: قبل از خواندن ادامه این مقاله، لازم است درک خوبی از نحوه محاسبه فاصله بین نقاط روی گراف داشته باشید. اگر با نحوه انجام این محاسبه آشنایی ندارید و یا اینکه به نیاز به دوره کردن مطالب دارید پیشنهاد میشود “Distance Between 2 Points” را بخوانید و برگردید.روش های دیگری هم برای محاسبه فاصله وجود دارد که بسته به مسئله ای که قرار است حل کنیم از آنها استفاده میکنیم. با این حال، فاصله خط مستقیم( که فاصله اقلیدسی هم نامیده میشود) یکی از محبوب ترین انتخاب هاست.الگوریتم KNN1. داده ها را بارگیری کنید2. مقدار دهی اولیه K را انجام دهید3. به ازای هر مثال در داده ها اعمال زیر را انجام دهید:1.3. فاصله بین کوئری مثال، و مثال فعلی را از داده ها محاسبه کنید2.3. فاصله و اندیس مثال را به مجموعه ای مرتب شده اضافه کنید4. مجموعه مرتب شدۀ فاصله ها و اندیس ها را از کوچک به بزرگ (به ترتیب صعودی) بر اساس فاصله ها مرتب کنید.5. اولین ورودی های K را از مجموعۀ مرتب شده انتخاب کنید6. برچسب های ورودی های Kهای انتخاب شده را دریافت کنید.7. برای رگرسیون، میانگین برچسب های K را برگردانید.8. برای طبقه بندی، مُد (Mode) برچسب های Kرا برگردانید.پیاده سازی KNNfrom collections import Counter import math def knn(data, query, k, distance_fn, choice_fn): neighbor_distances_and_indices = [] # 3. For each example in the data for index, example in enumerate(data): # 3.1 Calculate the distance between the query example and the current # example from the data. distance = distance_fn(example[:-1], query) # 3.2 Add the distance and the index of the example to an ordered collection neighbor_distances_and_indices.append((distance, index)) # 4. Sort the ordered collection of distances and indices from # smallest to largest (in ascending order) by the distances sorted_neighbor_distances_and_indices = sorted(neighbor_distances_and_indices) # 5. Pick the first K entries from the sorted collection k_nearest_distances_and_indices = sorted_neighbor_distances_and_indices[:k] # 6. Get the labels of the selected K entries k_nearest_labels = [data[i][-1] for distance, i in k_nearest_distances_and_indices] # 7. If regression (choice_fn = mean), return the average of the K labels # 8. If classification (choice_fn = mode), return the mode of the K labels return k_nearest_distances_and_indices , choice_fn(k_nearest_labels) def mean(labels): return sum(labels) / len(labels) def mode(labels): return Counter(labels).most_common(1)[0][0] def euclidean_distance(point1, point2): sum_squared_distance = 0 for i in range(len(point1)): sum_squared_distance += math.pow(point1[i] - point2[i], 2) return math.sqrt(sum_squared_distance) def main(): ''' # Regression Data # # Column 0: height (inches) # Column 1: weight (pounds) ''' reg_data = [ [65.75, 112.99], [71.52, 136.49], [69.40, 153.03], [68.22, 142.34], [67.79, 144.30], [68.70, 123.30], [69.80, 141.49], [70.01, 136.46], [67.90, 112.37], [66.49, 127.45], ] # Question: # Given the data we have, what's the best-guess at someone's weight if they are 60 inches tall? reg_query = [60] reg_k_nearest_neighbors, reg_prediction = knn( reg_data, reg_query, k=3, distance_fn=euclidean_distance, choice_fn=mean ) ''' # Classification Data # # Column 0: age # Column 1: likes pineapple ''' clf_data = [ [22, 1], [23, 1], [21, 1], [18, 1], [19, 1], [25, 0], [27, 0], [29, 0], [31, 0], [45, 0], ] # Question: # Given the data we have, does a 33 year old like pineapples on their pizza? clf_query = [33] clf_k_nearest_neighbors, clf_prediction = knn( clf_data, clf_query, k=3, distance_fn=euclidean_distance, choice_fn=mode ) if __name__ == '__main__': main() انتخاب مقدار مناسب برای Kبرای اینکه مقداری که برای K در نظر میگیریم مناسب داده های ما باشد، باید الگوریتم را چندین بار و با مقادیر مختلف K اجرا کنیم و مقداری را انتخاب کنیم که تعداد خطاهایی که با آنها روبرو میشویم را کاهش دهد و در عین حال بتواند در زمان رویارویی با داده ها جدید، پیش بینی دقیقی انجام دهد.این چند نکته را باید بخاطر سپرد:1. هرچه مقدار K را به سمت 1 کاهش دهیم، پیش بینی ما ناپایدارتر میشود. تصور کنید که K=1 است و یک نقطه کوئری داریم که با چندین نقطه قرمز و یک سبز احاطه شده(گوشه سمت چپ بالای تصویری که در بالاتر مشاهده کردید) اما سبز یک نزدیکترین همسایه تنهاست. منطقی است که فکر کنیم این نقطه کوئری باید قرمز باشد اما به بخاطر اینکه k=1 است، الگوریتم KNN به اشتباه پیش بینی میکند که آن نقطه سبز است.2. برعکس، هنگامی که مقدار K را افزایش می دهیم ، پیش بینی های ما به دلیل رأی اکثریت/میانگین گیری، پایدارتر می شوند و بنابراین ، احتمال بیشتری برای پیش بینی دقیق تر (تا حدی خاص) وجود دارد. و در نهایت، شاهد افزایش تعداد خطاها میشویم. در این مرحله است که می دانیم مقدار K را بیش از حد بالا در نظر گرفته ایم.3. در مواردی که ما در میان برچسب ها رای اکثریت (به عنوان مثال انتخاب Modeدر یک مسئله طبقه بندی) را انتخاب می کنیم، معمولاً K را به یک عدد فرد تبدیل می کنیم تا برنده ای داشته باشیم.مزایا1. اجرای الگوریتم ساده و آسان است.2. نیازی به ساخت مدل، تنظیم پارامترهای مختلف و یا فرضیات اضافی نیست.3. این الگوریتم همه کاره است. می تواند برای طبقه بندی، رگرسیون و جستجو استفاده شود (در بخش بعدی به آن خواهیم پرداخت).معایب1. با افزایش تعداد مثال ها، predictor ها و متغیرهای مستقل، الگوریتم به طور قابل توجهی کندتر می شود.الگوریتم KNN در عملعیب اصلی KNN در کاهش سرعت با افزایش حجم داده، آن را به یک گزینه بی فایده در محیط هایی تبدیل میکند که پیش بینی ها باید سریع انجام شود. علاوه بر آن، الگوریتم های سریع تری وجود دارد که می تواند نتایج طبقه بندی و رگرسیون دقیق تری ایجاد کند.با این وجود، به شرط داشتن منابع کافی برای پردازش سریع داده هایی که برای پیش بینی استفاده میکنید، KNN همچنان میتواند در حل مسائلی که نیاز است در آن داده های شبیه به هم دسته بندی شوند مفید واقع شود. نمونه ای از استفاده از الگوریتم KNN در سیستم های توصیه گر (Recommender Systems)، کاربرد جستجوی KNN است.سیستم های توصیه گر (Recommender Systems)در مقیاس بزرگ، این سیستم ها مشابه سیستم های پیشنهاد کالا در فروشگاه های آنلاین مانند آمازون، پیشنهاد فیلم در نتفلیکس و یا پیشنهاد ویدئو در یوتیوب هستند. البته به دلیل حجم عظیمی از داده ها که در این مثال ها پردازش میشود، مطمئنا از روش های کارآمد تری برای این پیشنهادات استفاده میشود.اما با این حال میتوانیم نمونه ای از هسته اصلی این سیستم ها را در مقیاسی کوچک تر با استفاده از آنچه در این مقاله آموخته ایم بسازیم. در ادامه به ساخت سیستم پیشنهاد دهنده فیلم میپردازیم.قرار است به چه سوالی پاسخ دهیم؟با توجه به دیتاست (Dataset) ما، 5 تا از مشابه ترین فیلم ها به یک فیلم مشخص کدام اند؟جمع آوری داده های فیلم هااگر در شرکت هایی مانند Netflix، IMDb یا Hulu کار میکردیم میتوانستیم داده ها را از انبار داده های آنها بگیریم. اما از آنجا که هیچ یک در این شرکت ها کار نمی کنیم، باید داده ها را از روش های دیگری بدست بیاوریم. میتوانیم از داده های فیلم مخزن یادگیری ماشین UCI و یا دیتاست IMDb استفاده کنیم، یا به سختی دیتاست خودمان را بسازیم!کاوش، تمیز و آماده کردن داده هااز هر منبعی که داده های خود را به دست بیاوریم، ممکن است مواردی در آن اشتباه باشد که باید آنها را اصلاح کنیم تا برای الگوریتم KNN آماده شوند. به عنوان مثال، ممکن است داده ها در قالبی که الگوریتم انتظار دارد نباشند، یا مقادیری خالی باشد، که باید آنها را قبل از انتقال آنها به الگوریتم پر کنیم یا از داده ها حذف کنیم.پیاده سازی KNN ما در اینجا به داده های ساختار یافته (Structured Data) متکی است و باید در قالب جدول باشد. علاوه بر این، فرض بر این است که تمام ستون ها حاوی داده های عددی هستند و آخرین ستون داده های ما دارای برچسب هایی است که می توانیم عملکردهایی را روی آنها انجام دهیم. بنابراین ، از هر جایی که داده های خود را به دست آوردیم، باید آنها را مطابق با این محدودیت ها تنظیم کنیم.داده های زیر مثالی از داده های پاک شده است. این داده ها شامل 30 عدد فیلم، شامل داده هایی برای هر فیلم در هفت ژانر و رتبه بندی IMDB آنها است. ستون برچسب ها همه صفر است زیرا ما از این دیتاست برای طبقه بندی یا رگرسیون استفاده نمی کنیم.علاوه بر این، روابطی هم در این فیلم ها وجود دارد که هنگام استفاده از الگوریتم KNN به حساب نمی آیند (به عنوان مثال بازیگران ، کارگردانان و...) به این دلیل که داده هایی که این روابط را به دست میاورند در دیتاست ما وجود ندارد. در نتیجه، وقتی الگوریتم KNN را روی داده های خود اجرا کنیم، شباهت صرفاً براساس ژانرهای موجود و رتبه بندی IMDB فیلم ها خواهد بود.استفاده از الگوریتمتصور کنید در یک وبسایت پیشنهاد فیلم در حال دیدن لیست فیلم ها هستیم و به فیلم The Post بر میخوریم، مطمئن نیستیم که میخواهیم این فیلم را تماشا کنیم یا خیر، و بعد اسکرول میکنیم تا به قسمت "فیلم های مشابه" برسیم تا ببینیم وبسایت چه پیشنهادی برای ما دارد، اینجاست که الگوریتم به کار می افتد.وبسایت یک درخواست به بک اند خود میفرستد که 5 فیلم که بیشترین شباهت را به The Post دارند را ارسال کند. در بک اند یک دیتاست مانند دیتاست ما وجود دارد. یک feature vector برای فیلم The Post میسازد، سپس برنامه ای مانند برنامه زیر را اجرا میکند تا 5 فیلم که بیشترین شباهت را به The Post دارند را پیدا کند. و سپس نتایج را به وبسایت ارسال میکند.from knn_from_scratch import knn, euclidean_distance def recommend_movies(movie_query, k_recommendations): raw_movies_data = [] with open('movies_recommendation_data.csv', 'r') as md: # Discard the first line (headings) next(md) # Read the data into memory for line in md.readlines(): data_row = line.strip().split(',') raw_movies_data.append(data_row) # Prepare the data for use in the knn algorithm by picking # the relevant columns and converting the numeric columns # to numbers since they were read in as strings movies_recommendation_data = [] for row in raw_movies_data: data_row = list(map(float, row[2:])) movies_recommendation_data.append(data_row) # Use the KNN algorithm to get the 5 movies that are most # similar to The Post. recommendation_indices, _ = knn( movies_recommendation_data, movie_query, k=k_recommendations, distance_fn=euclidean_distance, choice_fn=lambda x: None ) movie_recommendations = [] for _, index in recommendation_indices: movie_recommendations.append(raw_movies_data[index]) return movie_recommendations if __name__ == '__main__': # feature vector for The Post the_post = [7.2, 1, 1, 0, 0, 0, 0, 1, 0] recommended_movies = recommend_movies(movie_query=the_post, k_recommendations=5) # Print recommended movie titles for recommendation in recommended_movies: print(recommendation[1])زمانی که این الگوریتم را اجرا کنیم، فیلم های12 Years A SlaveHacksaw Ridge Queen of KatweThe Wind RisesA Beautiful Mind به ما پیشنهاد میشود. حالا که کاملا درک کردیم الگوریتم KNN چگونه کار میکند میتوانیم بفهمیم که الگوریتم دقیقا چگونه به این پیشنهادات رسید. تبریک!!منبعAmirhosein AhmadlooAmirhosein AhmadlooMon, 24 May 2021 16:59:15 +0430