الگوریتم کی-نزدیکترین همسایه: تفاوت میان نسخهها
نجات ۱ منبع و علامتزدن ۰ بهعنوان مرده.) #IABot (v2.0.9.2 |
اضافه کردن بخشهای استخراج ویژگی، مرز تصمیمگیری، کاهش ابعاد، کاهش دادهها و اعتبار سنجی نتایج |
||
خط ۱۱۵: | خط ۱۱۵: | ||
== یادگیری متریک == |
== یادگیری متریک == |
||
عملکرد <math>k</math> نزدیکترین همسایه، اغلب میتواند بهطور قابل توجهی، از طریق یادگیری متریک بهبود یابد. الگوریتمهای مشهور، تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیکترین همسایه (Large Margin Nearest Neighbor) هستند. الگوریتمهای یادگیری متریک، از اطلاعات نمونه، برای یادگیری متریک جدید یا شبه متریک استفاده میکنند. |
عملکرد <math>k</math> نزدیکترین همسایه، اغلب میتواند بهطور قابل توجهی، از طریق یادگیری متریک بهبود یابد. الگوریتمهای مشهور، تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیکترین همسایه (Large Margin Nearest Neighbor) هستند. الگوریتمهای یادگیری متریک، از اطلاعات نمونه، برای یادگیری متریک جدید یا شبه متریک استفاده میکنند. |
||
== استخراج ویژگی == |
|||
هنگامی که داده های ورودی یک الگوریتم برای پردازش بیش از حد بزرگ باشد و دادهها مشکوک به بیاستفاده و یا تکراری بودن باشند (به عنوان مثال اندازه گیری یکسان یک ویژگی با دو واحد متفاوت) آنگاه دادههای ورودی به یک مجموعه با ابعاد کاهش یافته از ویژگی ها تبدیل می شوند (همچنین بردار ویژگی ها نامیده می شود). تبدیل داده های ورودی به مجموعه ویژگی ها را [[استخراج ویژگی]] می گویند. اگر ویژگیهای استخراجشده با دقت انتخاب شوند، انتظار میرود که مجموعه ویژگیها اطلاعات مربوطه را از دادههای ورودی استخراج کند تا با استفاده از این نمایش کاهشیافته به جای ورودی با اندازه بزرگ الگوریتم را اجرا کرد و به نتیجه رسید. استخراج ویژگی بر روی داده های خام قبل از اعمال الگوریتم k-NN انجام میشود تا الگوریتم بر روی داده های تبدیل شده در فضای ویژگی جدید اجرا شود. |
|||
== مرز تصمیمگیری == |
|||
قواعد مربوط به نزدیکترین همسایه در عمل به طور ضمنی مرز تصمیم را محاسبه می کنند. همچنین می توان مرز تصمیم را به طور صریح محاسبه کرد و این کار را به طور کارآمد انجام داد، به طوری که پیچیدگی محاسباتی در مجموع تابعی از پیچیدگی مرزی خواهد بود.<ref>{{cite journal |doi=10.1007/s00454-004-1152-0 |last1=Bremner |first1=David |author-link2=Erik Demaine |last2=Demaine |first2=Erik |last3=Erickson |first3=Jeff |author-link4=John Iacono |last4=Iacono |first4=John |author-link5=Stefan Langerman |last5=Langerman |first5=Stefan |author-link6=Pat Morin |last6=Morin |first6=Pat |author-link7=Godfried Toussaint |last7=Toussaint |first7=Godfried T. |title=Output-sensitive algorithms for computing nearest-neighbor decision boundaries |journal=Discrete and Computational Geometry |volume=33 |issue=4 |year=2005 |pages=593–604 |doi-access=free }}</ref> |
|||
== کاهش ابعاد == |
|||
برای داده های با ابعاد بالا (به عنوان مثال، با تعداد ابعاد بیش از 10)، [[کاهش ابعاد]] معمولاً قبل از اعمال الگوریتم k-NN انجام می شود تا از اثرات [[مشقت بعدچندی]] جلوگیری شود. <ref>{{cite journal | last1 = Beyer | first1 = Kevin | display-authors = etal | title = When is "nearest neighbor" meaningful? | url = https://minds.wisconsin.edu/bitstream/handle/1793/60174/TR1377.pdf?sequence=1 | journal = Database Theory—ICDT'99 | volume = 1999 | pages = 217–235 }}</ref> |
|||
مشقت بعدچندی در زمینه k-NN اساساً به این معنی است که [[فاصله اقلیدسی]] در ابعاد بالا مفید نیست، زیرا همه بردارها تقریباً با بردار پرسوجو(query) فاصله دارند (تصور کنید چندین نقطه تقریبا بر روی یک دایره به مرکز نقطه پرسوجو قرار دارند. فاصله نقطه پرسوجو تا تمام نقاط داده در فضای جستجو تقریباً یکسان است). |
|||
[[استخراج ویژگی]] و کاهش ابعاد را می توان در یک مرحله با استفاده از [[تحلیل مؤلفههای اصلی|تحلیل مؤلفه اصلی]] (PCA)، [[آنالیز افتراقی خطی|تجزیه و تحلیل متمایز خطی]] (LDA)، یا تجزیه و تحلیل همبستگی متعارف (CCA) به عنوان یک مرحله پیش پردازش، و پس از خوشه بندی توسط k-NN بر روی بردارهای ویژگیها در فضا با بعد کاهش یافته انجام داد. به این فرآیند [[نشاندن (ریاضیات)|تعبیه]] با ابعاد کم نیز می گویند.<ref>{{citation |last1=Shaw |first1=Blake |last2=Jebara |first2=Tony |title=Structure preserving embedding |work=Proceedings of the 26th Annual International Conference on Machine Learning |year=2009 |pages=1–8 | publication-date=June 2009 |url=http://www.cs.columbia.edu/~jebara/papers/spe-icml09.pdf |doi=10.1145/1553374.1553494 |isbn=9781605585161 |s2cid=8522279 }}</ref> |
|||
برای مجموعه دادههای با ابعاد بسیار بالا (به عنوان مثال هنگام انجام جستجوی تشابه در جریانهای ویدیویی زنده، دادههای DNA یا [[سری های زمانی|سریهای زمانی]] با ابعاد بالا) یک جستجوی سریع و تقریبی k-NN با استفاده از درهمسازی حساس محلی(LSH)، "پیشبینیهای تصادفی"، <ref>{{cite book|doi=10.1145/502512.502546|chapter=Random projection in dimensionality reduction |title=Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '01 |year=2001 |last1=Bingham |first1=Ella |last2=Mannila |first2=Heikki |pages=245–250 |isbn=158113391X |s2cid=1854295 }}</ref> "طرحها" <ref>Ryan, Donna (editor); ''High Performance Discovery in Time Series'', Berlin: Springer, 2004, {{ISBN|0-387-00857-8}}</ref> یا سایر تکنیکهای جستجوی شباهت با ابعاد بالا از جعبه ابزار VLDB ممکن است تنها گزینه ممکن باشد. |
|||
== کاهش دادهها == |
|||
کاهش دادهها یکی از مهم ترین مسائل در کار با مجموعه دادههای عظیم است. معمولاً فقط برخی از نقاط داده برای طبقه بندی دقیق مورد نیاز است. این دادهها نمونههای اولیه نامیده میشوند و میتوان آنها را با استفاده از سه مرحله زیر یافت: |
|||
# پیدا کردن دادههای پرت: پیدا کردن دادههایی که در زمان آموزش به اشتباه توسط k-NN طبقه بندی شده اند. |
|||
# تقسیم بقیه دادهها به دو دسته: بقیه داده ها را دودسته تقسیم میکنیم. یک دسته نمونههای اولیه که برای تصمیمگیریهای طبقهبندی استفاده میشوند و دسته دیگر نقاط جذب (نقاطی که میتوانند به درستی توسط k-NN با استفاده از نمونههای اولیه طبقهبندی شوند.) |
|||
# در انتها نقاط جذب شده را میتوان از مجموعه دادههای آموزش حذف کرد. |
|||
== <math>k</math> نزدیکترین همسایه در حالت رگرسیون == |
== <math>k</math> نزدیکترین همسایه در حالت رگرسیون == |
||
خط ۱۲۲: | خط ۱۴۴: | ||
# بر اساس [[:en:Root-mean-square deviation|RMSD]] بهینهترین <math>k</math> در <math>k</math> نزدیکترین همسایه را پیدا کنید. این کار با استفاده از اعتبارسنجی متقابل انجام میشود. |
# بر اساس [[:en:Root-mean-square deviation|RMSD]] بهینهترین <math>k</math> در <math>k</math> نزدیکترین همسایه را پیدا کنید. این کار با استفاده از اعتبارسنجی متقابل انجام میشود. |
||
# محاسبه میانگین معکوس فاصله <math>k</math> نزدیکترین همسایه. |
# محاسبه میانگین معکوس فاصله <math>k</math> نزدیکترین همسایه. |
||
== اعتبارسنجی نتایج == |
|||
یک [[ماتریس درهمریختگی]] یا "ماتریس تطبیق" اغلب به عنوان ابزاری برای تأیید صحت طبقه بندی k-NN استفاده می شود. روشهای آماری قویتری مانند [[آزمون نسبت درستنمایی]] نیز میتواند استفاده شود. |
|||
== مزایا و معایب == |
== مزایا و معایب == |
نسخهٔ ۳۰ ژانویهٔ ۲۰۲۳، ساعت ۱۸:۱۵
یادگیری ماشین و دادهکاوی |
---|
در بازشناخت الگو کی-نزدیکترین همسایه (انگلیسی: k-nearest neighbors algorithm) یک متد آمار ناپارامتری است که برای طبقهبندی آماری و رگرسیون استفاده می شود. در هر دو حالت کی شامل نزدیک ترین مثال آموزشی در فضای داده ای می باشد و خروجی آن بسته به نوع مورد استفاده در طبقه بندی و رگرسیون متغیر است. در حالت طبقه بندی با توجه به مقدار مشخص شده برای کی، به محاسبه فاصله نقطه ای که میخواهیم برچسب آن را مشخص کنیم با نزدیک ترین نقاط میپردازد و با توجه به تعداد رای حداکثری این نقاط همسایه، در رابطه با برچسب نقطه مورد نظر تصمیم گیری میکنیم. برای محاسبه این فاصله میتوان از روش های مختلفی استفاده کرد که یکی از مطرح ترین این روش ها، فاصله اقلیدسی است. در حالت رگرسیون نیز میانگین مقادیر بدست آمده از کی خروجی آن می باشد. از آنجا که محاسبات این الگوریتم بر اساس فاصله است نرمالسازی دادهها میتواند به بهبود عملکرد آن کمک کند.[۱][۲]
تنظیمات آماری
فرض کنید زوج مرتبهای (Xn,Yn),... ,(X2,Y2),(X1,Y1) از {۱٬۲} × Rd مقدار میگیرد. (Y نشان دهنده کلاس X است). در نتیجه خواهیم داشت: X|Y = r ~ Pr برای r = ۱٬۲ که Pr توزیع احتمال است.
با داشتن تعدادی اندازه (norm) ‖. ‖ در Rd و نقطه x، زوج مرتبهای (X(n),Y(n)) ,... , (X(2),Y(2)),(X(1),Y(1) را که ترتیب دیگری از دادههای اولیه هستند با شرط ǁX(n) ≤ xǁ ,... , ǁX(1) ≤ xǁ تعریف میکنیم.
الگوریتم
دادههای اولیه، بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته میباشند.
فاز یادگیری (training phase) الگوریتم، شامل ذخیرهسازی بردارهای ویژگی و برچسب دسته نمونههای اولیه است.
در فاز طبقهبندی، k یک ثابت توسط کاربر تعریف میشود و بردار بدون برچسب (نقطه تست) از دسته ای است که بیشترین تعداد را در k نزدیکترین همسایه آن نقطه داشته باشد. به این ترتیب برچسب نقطه تست نیز مشخص میشود.
معیار فاصله برای متغیرهای پیوسته معمولاً فاصله اقلیدسی است.
برای متغیرهای گسسته، مانند دستهبندی متون، میتوان از یک معیار دیگر مانند فاصله همینگ استفاده کرد.
اگر NN- را با استفاده از الگوریتمهای تخصصی مانند تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیکترین همسایه (Large Margin Nearest Neighbor) پیادهسازی کرد، میتوان دقت اندازهگیری را به شدت بهبود داد.
یک اشکال طبقهبندی پایه «رای اکثریت» (majority voting) زمانی اتفاق میافتد که توزیع دسته درهم شکسته شود. به این معنی که تعداد زیادی از نمونههای یک دسته در میان نزدیکترین همسایه عضو جدید بودهاست.[۳] یکی از راههای غلبه بر این مشکل، وزن دادن به طبقهبندی بر مبنای فاصله هر یک از نمونههای اولیه، از عضو جدید است. دسته (یا مقدار در مسائل رگرسیون) هرکدام از k نزدیکترین نقاط در وزن خود که متناسب با معکوس فاصله آنها از نقطه تست است، ضرب میشود.
یکی دیگر از راههای غلبه بر این مشکل، انتزاع در نمایش دادهها است. برای مثال، در یک نقشههای خودسازماندهنده (SOM)، هر گره، صرف نظر از تراکم آنها در دادههای اولیه اصلی، یک نماینده (مرکز) از نقاط مشابه است. سپس NN- به SOM اعمال میشود.
مراحل الگوریتم knn شامل موارد زیر خواهد بود:[۴]
- دادههای را بارگیری کنید.
- K به عنوان تعداد نزدیکترین همسایگان انتخاب کنید.
- برای هر یک از دادههای اولیه:
- فاصله بین داده مورد سؤال و هر یک دادههای اولیه را محاسبه کنید.
- فاصله و اندبس نمونه را به یک مجموعه اضافه کنید.
- مجموعه را بر اساس فاصله از کوچک به بزرگ مرتب کنید.
- نقاط K عضو اول مجموعه مرتب شده را انتخاب کنید.
- بسته به حالت یا حالت طبقهبندی، خروجی را اعلام کنید.
به این ترتیب، کد پایتون محاسبه فاصله اقلیدسی و NN- را در ادامه میبینید:
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)
انتخاب پارامتر
بهترین انتخاب بستگی به دادهها دارد؛ بهطور کلی، مقادیر بزرگ باعث کاهش خطا در طبقهبندی میشود، اما وضوح مرز بین کلاسها را کمتر میکند.[۵] مناسب را میتوان با استفاده از تکنیکهای مختلف انتخاب کرد. مورد خاص زمانی است که دسته پیشبینی شده برای عضو جدید، همان دسته نزدیکترین نمونه باشد. (به ازای k = ۱). در این صورت، الگوریتم نزدیکترین همسایه نامیده میشود.
دقت الگوریتم NN- میتواند در نتیجه وجود خطا، یا ویژگیهای غیر مرتبط یا اگر مقیاس دادهها با اهمیت آنها تطابق نداشته باشد، به شدت تضعیف میشود. برای بهبود طبقهبندی، تلاشهای زیادی در زمینه انتخاب یا مقیاس بندی دادهها شدهاست. یک رویکرد بسیار مشهور، استفاده از الگوریتمهای تکاملی برای بهینهسازی مقیاس بندی دادهها است.
در دستهبندیهای دو کلاس، بهتر است که k یک عدد فرد انتخاب شود؛ زیرا این امر از گره خوردن آرا جلوگیری میکند.
نزدیکترین همسایه
شهودیترین نوع نزدیکترین همسایه در حالت طبقهبندی، تنها نزدیکترین همسایه است که یک نقطه را به کلاس نزدیکترین همسایه خوداختصاص میدهد؛ به این معنی که (1)Clnnn(x) = Y.
هر چه تعداد دادههای اولیه به بینهایت نزدیک میشود، نزدیکترین همسایه در حالت طبقهبندی تضمین میکند که میزان خطا بیشتر از دو برابر خطای بایاس (حداقل خطا قابل دستیابی با توجه به توزیع دادهها) نخواهد بود.
خصوصیات
kNN یک مورد خاص از پهنای باند متغیر است.[۶][۷]
نسخهٔ ساده این الگوریتم از محاسبه فاصلهٔ نمونه مورد سؤال با تمامی نمونههای اولیه، بدست میآید؛ اما برای مجموعه اولیههای بزرگ، این محاسبات بسیار سنگین خواهد بود. با استفاده از الگوریتم تقریبی جستجوی نزدیکترین همسایه، میتوان از شدت این محاسبات، حتی برای مجموعه اولیههای بزرگ، کاست. در طول سالها، بسیاری از الگوریتمهای جستجوی نزدیکترین همسایه پیشنهاد شدهاند که به دنبال کاهش تعداد محاسبههای انجام شده بودهاند.
NN- نتایجی با سازگاری(consistency) قوی دارد. هر چه تعدا دادهها به بینهایت نزدیک میشود، الگوریتم NN- با دو دسته، تضمین میکند که نرخ خطا بیشتر از دو برابر نرخ خطای Bayes(حداقل خطا قابل دستیابی با توجه به توزیع دادهها) نباشد.[۸] هم چنین میتوان با استفاده از گرافهای مجاورت، سرعت kNN را بهبود بخشید.[۹]
برای طبقهبندی NN- چند کلاس، کاور و هارت (۱۹۶۷) ثابت میکنند که حد بالای نرخ خطا برابر است با:
R* ≤ RkNN ≤ R* (2 - MR* ⁄ M-1 )
*R نرخ خطای Bayes (حداقل نرخ خطا ممکن)، RkNN نرخ خطای NN- و M تعداد دستهها در مسئله است. برای M = ۲ خطای بیزین *R به صفر میل میکند؛ این حد، حداکثر به میزان دو برابر خطای بیزین کاهش مییابد.
یادگیری متریک
عملکرد نزدیکترین همسایه، اغلب میتواند بهطور قابل توجهی، از طریق یادگیری متریک بهبود یابد. الگوریتمهای مشهور، تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیکترین همسایه (Large Margin Nearest Neighbor) هستند. الگوریتمهای یادگیری متریک، از اطلاعات نمونه، برای یادگیری متریک جدید یا شبه متریک استفاده میکنند.
استخراج ویژگی
هنگامی که داده های ورودی یک الگوریتم برای پردازش بیش از حد بزرگ باشد و دادهها مشکوک به بیاستفاده و یا تکراری بودن باشند (به عنوان مثال اندازه گیری یکسان یک ویژگی با دو واحد متفاوت) آنگاه دادههای ورودی به یک مجموعه با ابعاد کاهش یافته از ویژگی ها تبدیل می شوند (همچنین بردار ویژگی ها نامیده می شود). تبدیل داده های ورودی به مجموعه ویژگی ها را استخراج ویژگی می گویند. اگر ویژگیهای استخراجشده با دقت انتخاب شوند، انتظار میرود که مجموعه ویژگیها اطلاعات مربوطه را از دادههای ورودی استخراج کند تا با استفاده از این نمایش کاهشیافته به جای ورودی با اندازه بزرگ الگوریتم را اجرا کرد و به نتیجه رسید. استخراج ویژگی بر روی داده های خام قبل از اعمال الگوریتم k-NN انجام میشود تا الگوریتم بر روی داده های تبدیل شده در فضای ویژگی جدید اجرا شود.
مرز تصمیمگیری
قواعد مربوط به نزدیکترین همسایه در عمل به طور ضمنی مرز تصمیم را محاسبه می کنند. همچنین می توان مرز تصمیم را به طور صریح محاسبه کرد و این کار را به طور کارآمد انجام داد، به طوری که پیچیدگی محاسباتی در مجموع تابعی از پیچیدگی مرزی خواهد بود.[۱۰]
کاهش ابعاد
برای داده های با ابعاد بالا (به عنوان مثال، با تعداد ابعاد بیش از 10)، کاهش ابعاد معمولاً قبل از اعمال الگوریتم k-NN انجام می شود تا از اثرات مشقت بعدچندی جلوگیری شود. [۱۱]
مشقت بعدچندی در زمینه k-NN اساساً به این معنی است که فاصله اقلیدسی در ابعاد بالا مفید نیست، زیرا همه بردارها تقریباً با بردار پرسوجو(query) فاصله دارند (تصور کنید چندین نقطه تقریبا بر روی یک دایره به مرکز نقطه پرسوجو قرار دارند. فاصله نقطه پرسوجو تا تمام نقاط داده در فضای جستجو تقریباً یکسان است).
استخراج ویژگی و کاهش ابعاد را می توان در یک مرحله با استفاده از تحلیل مؤلفه اصلی (PCA)، تجزیه و تحلیل متمایز خطی (LDA)، یا تجزیه و تحلیل همبستگی متعارف (CCA) به عنوان یک مرحله پیش پردازش، و پس از خوشه بندی توسط k-NN بر روی بردارهای ویژگیها در فضا با بعد کاهش یافته انجام داد. به این فرآیند تعبیه با ابعاد کم نیز می گویند.[۱۲]
برای مجموعه دادههای با ابعاد بسیار بالا (به عنوان مثال هنگام انجام جستجوی تشابه در جریانهای ویدیویی زنده، دادههای DNA یا سریهای زمانی با ابعاد بالا) یک جستجوی سریع و تقریبی k-NN با استفاده از درهمسازی حساس محلی(LSH)، "پیشبینیهای تصادفی"، [۱۳] "طرحها" [۱۴] یا سایر تکنیکهای جستجوی شباهت با ابعاد بالا از جعبه ابزار VLDB ممکن است تنها گزینه ممکن باشد.
کاهش دادهها
کاهش دادهها یکی از مهم ترین مسائل در کار با مجموعه دادههای عظیم است. معمولاً فقط برخی از نقاط داده برای طبقه بندی دقیق مورد نیاز است. این دادهها نمونههای اولیه نامیده میشوند و میتوان آنها را با استفاده از سه مرحله زیر یافت:
- پیدا کردن دادههای پرت: پیدا کردن دادههایی که در زمان آموزش به اشتباه توسط k-NN طبقه بندی شده اند.
- تقسیم بقیه دادهها به دو دسته: بقیه داده ها را دودسته تقسیم میکنیم. یک دسته نمونههای اولیه که برای تصمیمگیریهای طبقهبندی استفاده میشوند و دسته دیگر نقاط جذب (نقاطی که میتوانند به درستی توسط k-NN با استفاده از نمونههای اولیه طبقهبندی شوند.)
- در انتها نقاط جذب شده را میتوان از مجموعه دادههای آموزش حذف کرد.
نزدیکترین همسایه در حالت رگرسیون
در رگرسیون، الگوریتم NN- برای تخمین زدن متغیرهای پیوسته استفاده میشود. یکی از این الگوریتمها از میانگین وزنی k نزدیکترین همسایه بدست میآید (میانگین وزنی از معکوس فاصله آنها محاسبه میشود). این الگوریتم به شرح زیر عمل میکند:
- محاسبه فاصله اقلیدسی یا فاصله Mahalanobis از نمونه مسئله داده شده به نمونههای علامت زده شده.
- مرتبسازی مثالهای علامت زده شده با افزایش فاصله.
- بر اساس RMSD بهینهترین در نزدیکترین همسایه را پیدا کنید. این کار با استفاده از اعتبارسنجی متقابل انجام میشود.
- محاسبه میانگین معکوس فاصله نزدیکترین همسایه.
اعتبارسنجی نتایج
یک ماتریس درهمریختگی یا "ماتریس تطبیق" اغلب به عنوان ابزاری برای تأیید صحت طبقه بندی k-NN استفاده می شود. روشهای آماری قویتری مانند آزمون نسبت درستنمایی نیز میتواند استفاده شود.
مزایا و معایب
[۱۵] مزایا:
- هیچ پیش فرضی در مورد دادهها وجود ندارد - مثال برای دادههای غیر خطی
- الگوریتم ساده
- دقت نسبتاً بالا
- مقایسه مدلهای یادگیری تحت نظارت بهتر
- چند منظوره - برای طبقهبندی و رگرسیون
مضرات:
- محاسبه گران
- نیاز به حافظه بالا - چرا که الگوریتم، تمام دادههای قبلی را ذخیره میکند.
- ذخیره تقریباً یا همه دادههای اولیه
- مرحله پیشبینی ممکن است کند باشد (با N بزرگ)
- حساس به ویژگیهای نامناسب و مقیاس داده
منابع
- ↑ Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-06). "Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems". Journal of Transportation Engineering, Part B: Pavements. 146 (2): 04020022. doi:10.1061/jpeodx.0000175. ISSN 2573-5438.
{{cite journal}}
: Check date values in:|date=
(help) - ↑ Hastie, Trevor. (2001). The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Tibshirani, Robert., Friedman, J. H. (Jerome H.). New York: Springer. ISBN 0-387-95284-5. OCLC 46809224.
- ↑ D. Coomans; D.L. Massart: نزدیکترین همسایه با استفاده از قوانین رایگیری جایگزین
- ↑ The KNN Algorithm
- ↑ Everitt, B. S. , Landau, S. , Leese, M. and Stahl, D
- ↑ D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation"
- ↑ Mills, Peter. "Efficient statistical classification of satellite measurements"
- ↑ Cover TM .Hart PE , Nearest neighbor pattern classification بایگانیشده در ۲۳ دسامبر ۲۰۱۸ توسط Wayback Machine
- ↑ "Toussaint GT (April 2005). "Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining
- ↑ Bremner, David; Demaine, Erik; Erickson, Jeff; Iacono, John; Langerman, Stefan; Morin, Pat; Toussaint, Godfried T. (2005). "Output-sensitive algorithms for computing nearest-neighbor decision boundaries". Discrete and Computational Geometry. 33 (4): 593–604. doi:10.1007/s00454-004-1152-0.
- ↑ Beyer, Kevin; et al. "When is "nearest neighbor" meaningful?" (PDF). Database Theory—ICDT'99. 1999: 217–235.
- ↑ Shaw, Blake; Jebara, Tony (2009), "Structure preserving embedding" (PDF), Proceedings of the 26th Annual International Conference on Machine Learning (published June 2009), pp. 1–8, doi:10.1145/1553374.1553494, ISBN 9781605585161, S2CID 8522279
- ↑ Bingham, Ella; Mannila, Heikki (2001). "Random projection in dimensionality reduction". Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '01. pp. 245–250. doi:10.1145/502512.502546. ISBN 158113391X. S2CID 1854295.
- ↑ Ryan, Donna (editor); High Performance Discovery in Time Series, Berlin: Springer, 2004, شابک ۰−۳۸۷−۰۰۸۵۷−۸
- ↑ : A Quick Introduction to K-Nearest Neighbors Algorithm
مشارکتکنندگان ویکیپدیا. «K-nearest_neighbors_algorithm». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۱۵ آوریل ۲۰۱۹.