K-Nearest Neighbors (KNN) դասակարգում

Երբ նոր բան եք տեսնում, ինչպե՞ս կարող եք կռահել դրա պիտակը կամ արժեքը՝ նայելով ձեզ արդեն ծանոթ նմանատիպ օրինակներին։ KNN ալգորիթմը փորձում է կանխատեսել նոր օբյեկտի պիտակը՝ հիմնվելով K ամենամոտ հարևանների պիտակների վրա։ Այս ալգորիթմի միջոցով հավելվածները կարող են գտնել նմանատիպ ապրանքներ, հայտնաբերել սպամը՝ նոր նամակները համեմատելով հների հետ, տեխնիկական հարցումները դասակարգել ըստ հայտնի կատեգորիաների և կանխատեսել թվային արժեքներ, օրինակ՝ ֆիլմի վարկանիշ կամ տան գին։ Այն հարմար է որպես սկզբնական գործիք, քանի որ հեշտ է հասկանալ և արագ է կիրառվում։

Օրինակ, եթե ունենանք գունավոր կետերով այս ցանցը և ցանկանանք կանխատեսել նոր ավելացվող կետի գույնը, ապա որոշում կայացնելու համար կարող ենք դիտարկել դրա ամենամոտ հարևաններին։

Ամենամոտ համը

Մի հետաքրքրասեր մեղու ուսումնասիրում է նոր այգի։ Նա գիտի, թե որտեղ են գտնվում որոշ պիտակավորված ծառեր և ինչ համ ունեն դրանք՝ խնձորի, թե տանձի։ Երբ մեղուն վայրէջք է կատարում որևէ տեղ, նա ցանկանում է իմանալ իրեն ամենամոտ գտնվող հայտնի ծառի համը։

Ձեր խնդիրն է օգնել մեղվին կայացնել որոշում։

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n՝ հայտնի ծառերի քանակը։

Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y, որոնց հաջորդում է համը նշող բառ՝ apple կամ pear։ Այս տվյալները նկարագրում են մեկ ծառի դիրքն ու համը։

Այնուհետև հաջորդ տողում տրված է մեկ ամբողջ թիվ q՝ ստուգման ենթակա վայրէջքի դիրքերի քանակը։

Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y՝ որոնք մեղվի վայրէջքի դիրքերն են։

Յուրաքանչյուր վայրէջքի դիրքի համար անհրաժեշտ է տպել ամենամոտ գտնվող հայտնի ծառի համը։ Եթե մի քանի հայտնի ծառեր գտնվում են վայրէջքի կետից միևնույն հեռավորության վրա, տպեք այն ծառի համը, որը մուտքային տվյալներում ավելի շուտ է հանդիպում։