Кіріспе
Параметрлік емес жіктеу әдісі – бақыланатын жіктеу/регрессия, бірақ кластерлік алгоритм емес. Статистикада k жақын көршілер алгоритмі (k NN) – Эвелин Фикс және Джозеф Ходжес 1951 жылы бірінші рет әзірлеген, кейін Томас Ковер кеңейткен параметрлік емес бақыланатын оқыту әдісі. Жіктеу және регрессия үшін де көршілердің үлесіне салмақ қою пайдалы техника болып табылады, сондықтан жақын көршілер алыс көршілерге қарағанда орташа есепке көбірек үлес қосады. Мысалы, кең таралған салмақтау схемасы әрбір көршіге 1/d салмағын беруден тұрады, мұнда d – көршіге дейінгі қашықтық. Көршілер сыныбы белгілі (k NN жіктеу үшін) немесе объектінің қасиеттері белгілі (k NN регрессия үшін) объектілер жиынтығынан алынады. Бұл алгоритм үшін оқу жиынтығы ретінде қарастырылуы мүмкін, бірақ нақты оқу қадамы қажет емес. k NN алгоритмінің ерекшелігі – ол деректердің жергілікті құрылымына сезімтал.
In statistics, the k nearest neighbors algorithm (k NN) is a non parametric supervised learning method first developed by Evelyn Fix and Joseph Hodges in 1951, and later expanded by Thomas Cover. Both for classification and regression, a useful technique can be to assign weights to the contributions of the neighbors, so that the nearer neighbors contribute more to the average than the more distant ones. For example, a common weighting scheme consists in giving each neighbor a weight of 1/d, where d is the distance to the neighbor. The neighbors are taken from a set of objects for which the class (for k NN classification) or the object property value (for k NN regression) is known. This can be thought of as the training set for the algorithm, though no explicit training step is required. A peculiarity of the k NN algorithm is that it is sensitive to the local structure of the data.
Статистикалық жағдай
Егер бізде Y, X-тің сынып белгісі болатын, мәндерін қабылдайтын жұптар болса, онда (және ықтималдық таратулары) үшін . норманы және нүктені ескере отырып, оқу деректерін шартты түрде реттейік, осылайша .
Алгоритм
Оқу үлгілері – әрқайсысы сынып белгісімен бірге көп өлшемді белгі кеңістігіндегі векторлар болып табылады. Алгоритмді оқыту кезеңі тек оқу үлгілерінің белгі векторларын және сынып белгілерін сақтаудан тұрады. Сыныптау кезеңінде k – пайдаланушы анықтаған тұрақты шама, ал белгіленбеген вектор (сұрау немесе сынақ нүктесі) осы сұрау нүктесіне ең жақын k оқу үлгісінің арасында ең көп кездесетін белгімен жіктеледі. Ұдайы айнымалылар үшін жиі қолданылатын қашықтық метрикасы – Евклид қашықтығы. Дискретті айнымалылар үшін, мысалы, мәтінді жіктеу үшін, басқа метриканы қолдануға болады, мысалы, жапсарлылық метрикасын (немесе Хамминг қашықтығын). Гендік экспрессия микромассивтерінің деректерінде, мысалы, k NN Пирсон және Спирман сияқты корреляциялық коэффициенттермен метрика ретінде қолданылған. Көбінесе, қашықтық метрикасы Large Margin Nearest Neighbor немесе Neighborhood Components Analysis сияқты арнайы алгоритмдермен оқытылса, k NN-нің жіктеу дәлдігін айтарлықтай жақсартуға болады. Негізгі "көпшілік дауыс беру" жіктеуінің кемшілігі – сыныптардың таралуы бұрыс болғанда пайда болады. Яғни, жиі кездесетін сыныптың үлгілері жаңа үлгіні болжауда басымдық алады, себебі олар үлгінің k ең жақын көршісінің арасында көптеп кездеседі. Бұл мәселені шешудің бір жолы – жіктемені сынақ нүктесінен оның k ең жақын көршілеріне дейінгі қашықтықты ескере отырып салмақтау. k ең жақын нүктенің әрқайсысының сыныбы (немесе регрессиялық есептерде мәні) осы нүктеден сынақ нүктесіне дейінгі қашықтыққа кері пропорционалды салмаққа көбейтіледі. Бұрыстылықты жоюдың тағы бір жолы – деректерді ұсынуда абстракция қолдану. Мысалы, өзін-өзі ұйымдастыратын картада (SOM) әр түйін – бастапқы оқу деректерінің тығыздығына қарамастан, ұқсас нүктелердің кластерінің өкілі (орталығы) болып табылады. Содан кейін K NN-ді SOM-ға қолдануға болады.
Параметрді таңдау
Деректерге байланысты k-ның ең жақсы таңдауы жасалады; әдетте, k-ның үлкен мәндері сыныптаудағы шудың әсерін азайтады, бірақ сыныптар арасындағы шекараларды нашарлайтады. Жақсы k-ны әр түрлі эвристикалық тәсілдермен таңдауға болады (гиперпараметрлік оптимизацияны қараңыз). Сыныпты ең жақын оқу үлгісінің класы деп болжаудың ерекше жағдайы (яғни k = 1 болғанда) – ең жақын көрші алгоритмі деп аталады. k NN алгоритмінің дәлдігі шулы немесе маңызсыз белгілердің болуынан, немесе белгілердің масштабтары олардың маңыздылығына сәйкес келмесе, айтарлықтай төмендеуі мүмкін. Сыныптауды жақсарту үшін белгілерді таңдау немесе масштабтау бойынша көптеген зерттеулер жүргізілді. Әсіресе танымал тәсіл – белгілердің масштабын оңтайландыру үшін эволюциялық алгоритмдерді қолдану. Тағы бір танымал тәсіл – оқу кластарымен оқу деректерінің өзара ақпаратын пайдаланып белгілерді масштабтау. Бинарлық (екі сыныпты) жіктеу мәселелерінде k-ны тақ сан ретінде таңдау тиімді, себебі бұл тең дауыс беруді болдырмайды. Осы жағдайда k-ны эмпирикалық жағынан оңтайлы таңдаудың бір танымал тәсілі – бутстрап әдісі арқылы.
Ең жақын көрші жіктеуіші
Ең интуитивті жақын көрші типті жіктегіш – бұл бір жақын көрші жіктегіші, ол x нүктесін ерекшелік кеңістігіндегі ең жақын көршісінің класына жатқызады, яғни оқу деректер жинағының мөлшері шексіздікке жақындағанда, бір жақын көрші жіктегіші Байес қателік деңгейінен екі еседен артық емес қателік деңгейін кепілдік береді (деректердің таралуына байланысты қол жеткізілетін ең төменгі қателік деңгейі).
As the size of training data set approaches infinity, the one nearest neighbour classifier guarantees an error rate of no worse than twice the Bayes error rate (the minimum achievable error rate given the distribution of the data).
Қателік деңгейі
K жақын көрші сыныптаушылардың қателік деңгейі туралы көптеген нәтижелер бар. K ең жақын көрші жіктеуіш, егер дивергенцияланса және нөлге жақындасса, кез келген бірлескен таралу үшін қатаң түрде (яғни) сәйкес келеді. n өлшемді оқу жиынтығына негізделген k ең жақын көрші жіктеуішін деп белгілейік. Белгілі бір реттелілік шарттарында, артық тәуекел келесі асимптотикалық кеңеюді береді:
Let denote the k nearest neighbour classifier based on a training set of size n. Under certain regularity conditions, the excess risk yields the following asymptotic expansion
кейбір тұрақтылар және үшін. таңдауы жоғарыда көрсетілген екі мүше арасындағы компромисті ұсынады, олар үшін ең жақын көрші қатесі оңтайлы (минимальді) жылдамдықпен Бейес қатесіне жақындайды.
The choice offers a trade off between the two terms in the above display, for which the nearest neighbour error converges to the Bayes error at the optimal (minimax) rate .
Метрикалық оқыту
K жақын көрші классификациясының нәтижесін (бақыланатын) метрикалық оқыту арқылы көбінесе айтарлықтай жақсартуға болады. Танымал алгоритмдер – көршілік компоненттерді талдау және үлкен шеттік ең жақын көрші. Бақыланатын метрикалық оқыту алгоритмдері жаңа метриканы немесе псевдометриканы үйрену үшін белгілер туралы ақпаратты қолданады.
Өлшемін азайту
Жоғары өлшемді деректер үшін (мысалы, өлшемдер саны 10-нан асып кетсе) k NN алгоритмін қолдану алдында өлшемді азайту жүргізіледі, бұл өлшемдік қарғыстың әсерінен сақтану үшін қажет. k NN контекстінде өлшемдік қарғыс дегеніміз – Евклидтік қашықтық жоғары өлшемдерде тиімсіз болады, себебі барлық векторлар іздеу сұранысы векторынан шамамен бірдей қашықтықта жатады (ойыңызға келсін, іздеу нүктесі ортада орналасқан шеңберде көптеген нүктелер шамамен бірдей жерде жатыр; іздеу кеңістігіндегі барлық дерек нүктелерінен сұранысқа дейінгі қашықтық дерлік бірдей). Белгілерді іздеу және өлшемді азайтуды бір қадамда негізгі компоненттік талдау (PCA), сызықтық дискриминанттық талдау (LDA) немесе каноникалық корреляциялық талдау (CCA) сияқты әдістерді алдын ала өңдеу ретінде біріктіруге болады, содан кейін k NN арқылы кластерлеуді азайтылған өлшемді кеңістіктегі белгілер векторларында жүргізуге болады. Бұл процеске төмен өлшемді енгізу делінеді. Өте жоғары өлшемді деректер жиынтықтары үшін (мысалы, тікелей бейне ағындары, ДНК деректері немесе жоғары өлшемді уақыт қатарларында ұқсастық іздеуді орындау кезінде) жергілікті сезімтал хэштеу, "көп рет проекциялар", "эскиздер" немесе VLDB құралдар жиынтығынан басқа жоғары өлшемді ұқсастық іздеу әдістерін пайдаланып, жылдам шамамен k NN іздеуін жүргізу – жалғыз мүмкін шешім болуы мүмкін.
Шешімнің шекарасы
Ең жақын көрші ережелері шешім шекарасын тікелей есептеп шығарады. Сондай-ақ, шешім шекарасын нақты және тиімді түрде есептеуге болады, осылайша есептеу күрделілігі шекараның күрделілігіне байланысты болады.
Нәтижелерді растау
Шатасу матрицасы немесе "сәйкестік матрицасы" k NN жіктемесінің дәлдігін бағалау үшін жиі қолданылады. Ықтималдық қатынасы тесті сияқты, көбірек сенімді статистикалық әдістерді де қолдануға болады.