الگوریتم کی-نزدیک‌ترین همسایه

فرض کنید زوج مرتب‌های (X_n,Y_n),... ,(X₂,Y₂),(X₁,Y₁) از {۱٬۲} × R مقدار می‌گیرد. (Y نشان دهنده کلاس X است). در نتیجه خواهیم داشت: X|Y = r ~ P_r برای r = ۱٬۲ که P_r توزیع احتمال است.

با داشتن تعدادی اندازه (norm) ‖. ‖ در R_d و نقطه x، زوج مرتب‌های (X_(n),Y_(n)) ,... , (X₍₂₎,Y₍₂₎),(X₍₁₎,Y₍₁) را که ترتیب دیگری از داده‌های اولیه هستند با شرط ǁX_(n) ≤ xǁ ,... , ǁX₍₁₎ ≤ xǁ تعریف می‌کنیم.

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

فاز یادگیری (training phase) الگوریتم، شامل ذخیره‌سازی بردارهای ویژگی و برچسب دسته نمونه‌های اولیه است.

در فاز طبقه‌بندی، k یک ثابت توسط کاربر تعریف می‌شود و بردار بدون برچسب (نقطه تست) از دسته ای است که بیشترین تعداد را در k نزدیک‌ترین همسایه آن نقطه داشته باشد. به این ترتیب برچسب نقطه تست نیز مشخص می‌شود.

معیار فاصله برای متغیرهای پیوسته معمولاً فاصله اقلیدسی است.

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

اگر NN-${\displaystyle k}$

یک اشکال طبقه‌بندی پایه «رای اکثریت» (majority voting) زمانی اتفاق می‌افتد که توزیع دسته درهم شکسته شود. به این معنی که تعداد زیادی از نمونه‌های یک دسته در میان نزدیک‌ترین همسایه عضو جدید بوده‌است. یکی از راه‌های غلبه بر این مشکل، وزن دادن به طبقه‌بندی بر مبنای فاصله هر یک از نمونه‌های اولیه، از عضو جدید است. دسته (یا مقدار در مسائل رگرسیون) هرکدام از k نزدیک‌ترین نقاط در وزن خود که متناسب با معکوس فاصله آن‌ها از نقطه تست است، ضرب می‌شود.

یکی دیگر از راه‌های غلبه بر این مشکل، انتزاع در نمایش داده‌ها است. برای مثال، در یک نقشه‌های خودسازمان‌دهنده (SOM)، هر گره، صرف نظر از تراکم آن‌ها در داده‌های اولیه اصلی، یک نماینده (مرکز) از نقاط مشابه است. سپس NN-${\displaystyle k}$

مراحل الگوریتم knn شامل موارد زیر خواهد بود:

1. داده‌های را بارگیری کنید.
2. K به عنوان تعداد نزدیک‌ترین همسایگان انتخاب کنید.
3. برای هر یک از داده‌های اولیه:
   1. فاصله بین داده مورد سؤال و هر یک داده‌های اولیه را محاسبه کنید.
   2. فاصله و اندبس نمونه را به یک مجموعه اضافه کنید.
   3. مجموعه را بر اساس فاصله از کوچک به بزرگ مرتب کنید.
   4. نقاط K عضو اول مجموعه مرتب شده را انتخاب کنید.
   5. بسته به حالت یا حالت طبقه‌بندی، خروجی را اعلام کنید.

به این ترتیب، کد پایتون محاسبه فاصله اقلیدسی و NN-${\displaystyle k}$

 def EuclideanDistance(x1, x2, length):
    distance = 0
    for x in range(length):
        distance += np.square(x1[x] - x2[x])
    return np.sqrt(distance)

کد زیر مربوط به الگوریتم knn گفته شده در حالت دسته‌بندی است. داده‌های اولیه، trainingSet و داده مورد سؤال testInstance نامیده شده‌است.

 def knn(trainingSet, testInstance, k):
    distances = {}
    sort = {}

    length = testInstance.shape[1]

    for x in range(len(trainingSet)):
        dist = EuclideanDistance(testInstance, trainingSet.iloc[x], length)
        distances[x] = dist[0]
    sortdist = sorted(distances.items(), key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(sortdist[x][0])
    Votes = {} #to get most frequent class of rows
    for x in range(len(neighbors)):
        response = trainingSet.iloc[neighbors[x]][-1]
        if response in Votes:
            Votes[response] += 1
        else:
            Votes[response] = 1
    sortvotes = sorted(Votes.items(), key=operator.itemgetter(1), reverse=True)
    return(sortvotes[0][0], neighbors)

بهترین انتخاب ${\displaystyle k}$

دقت الگوریتم NN-${\displaystyle k}$

در دسته‌بندی‌های دو کلاس، بهتر است که k یک عدد فرد انتخاب شود؛ زیرا این امر از گره خوردن آرا جلوگیری می‌کند.

شهودی‌ترین نوع نزدیکترین همسایه در حالت طبقه‌بندی، تنها نزدیکترین همسایه است که یک نقطه را به کلاس نزدیکترین همسایه خوداختصاص می‌دهد؛ به این معنی که ₍₁₎C_n(x) = Y.

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

kNN یک مورد خاص از پهنای باند متغیر است.

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

NN-${\displaystyle k}$

برای طبقه‌بندی NN-${\displaystyle k}$

R نرخ خطای Bayes (حداقل نرخ خطا ممکن)، R_kNN نرخ خطای NN-${\displaystyle k}$

عملکرد ${\displaystyle k}$

در رگرسیون، الگوریتم NN-${\displaystyle k}$

1. محاسبه فاصله اقلیدسی یا فاصله Mahalanobis از نمونه مسئله داده شده به نمونه‌های علامت زده شده.
2. مرتب‌سازی مثال‌های علامت زده شده با افزایش فاصله.
3. بر اساس RMSD بهینه‌ترین ${\displaystyle k}$
   در ${\displaystyle k}$
   نزدیک‌ترین همسایه را پیدا کنید. این کار با استفاده از اعتبارسنجی متقابل انجام می‌شود.
4. محاسبه میانگین معکوس فاصله ${\displaystyle k}$
   نزدیکترین همسایه.

مزایا:

• هیچ پیش فرضی در مورد داده‌ها وجود ندارد - مثال برای داده‌های غیر خطی
• الگوریتم ساده
• دقت نسبتاً بالا
• مقایسه مدل‌های یادگیری تحت نظارت بهتر
• چند منظوره - برای طبقه‌بندی و رگرسیون

مضرات:

• محاسبه گران
• نیاز به حافظه بالا - چرا که الگوریتم، تمام داده‌های قبلی را ذخیره می‌کند.
• ذخیره تقریباً یا همه داده‌های اولیه
• مرحله پیش‌بینی ممکن است کند باشد (با N بزرگ)
• حساس به ویژگی‌های نامناسب و مقیاس داده

مشارکت‌کنندگان ویکی‌پدیا. «K-nearest_neighbors_algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۵ آوریل ۲۰۱۹.