Взвешенный K-NN

Опубликовано: 24 Июля, 2021

Взвешенный kNN - это модифицированная версия k ближайших соседей. Одна из многих проблем, влияющих на производительность алгоритма kNN, - это выбор гиперпараметра k. Если k слишком мало, алгоритм будет более чувствителен к выбросам. Если k слишком велико, соседство может включать слишком много точек из других классов.
Другой вопрос - это подход к объединению меток классов. Самый простой способ - получить большинство голосов, но это может стать проблемой, если ближайшие соседи сильно различаются по своему расстоянию, а самые близкие соседи более надежно указывают класс объекта.

Интуиция:
Рассмотрим следующий обучающий набор

Красные метки обозначают баллы класса 0, а зеленые метки указывают баллы класса 1.
Считайте белую точку точкой запроса (точкой, метку класса которой необходимо предсказать)

Если мы передадим вышеуказанный набор данных классификатору на основе kNN, тогда классификатор объявит точку запроса принадлежащей классу 0. Но на графике ясно, что точка ближе к точкам класса 1 по сравнению с классом 0 баллов. Чтобы преодолеть этот недостаток, используются утяжеленные кНН. В взвешенном kNN ближайшим k точкам присваивается вес с использованием функции, называемой функцией ядра. Интуиция, лежащая в основе взвешенных kNN, заключается в том, чтобы придать больший вес точкам, которые находятся поблизости, и меньший вес - точкам, которые находятся дальше. Любая функция может использоваться как функция ядра для взвешенного классификатора knn, значение которого уменьшается с увеличением расстояния. Используемая простая функция - это функция обратного расстояния.

Алгоритм:

Пусть L = {(x _i , y _i ), i = 1,. . . , n} будет обучающим набором наблюдений x _i с заданным классом y _i, и пусть x будет новым наблюдением (точкой запроса), метка класса y которого должна быть предсказана.
Вычислить d (x _i , x) для i = 1,. . . , n, расстояние между точкой запроса и любой другой точкой в обучающем наборе.
Выберите D '⊆ D, набор из k ближайших точек обучающих данных к точкам запроса
Прогнозируйте класс точки запроса, используя взвешенное по расстоянию голосование. Буква v представляет метки классов. Используйте следующую формулу

Выполнение:
Считайте 0 как метку для класса 0 и 1 как метку для класса 1. Ниже представлена реализация алгоритма взвешенного kNN.

C / C ++

 // C++ program to implement the
 // weighted K nearest neighbour algorithm.
 #include <bits/stdc++.h>
 using namespace std;
 
struct Point
 {
    int val; // Class of point
    double x, y; // Co-ordinate of point
    double distance; // Distance from test point
 };
 
// Used to sort an array of points by increasing
 // order of weighted distance
 bool comparison(Point a, Point b)
 {
    return (a.distance < b.distance);
 }
 
// This function finds classification of point p using
 // weighted k nearest neighbour algorithm. It assumes only
 // two groups and returns 0 if p belongs to class 0, else
 // 1 (belongs to class 1).
 int weightedkNN(Point arr[], int n, int k, Point p)
 {
    // Fill weighted distances of all points from p
    for ( int i = 0; i < n; i++)
        arr[i].distance =
            ( sqrt ((arr[i].x - px) * (arr[i].x - px) +
                (arr[i].y - py) * (arr[i].y - py)));
 
    // Sort the Points by weighted distance from p
    sort(arr, arr+n, comparison);
 
    // Now consider the first k elements and only
    // two groups
    double freq1 = 0; // weighted sum of group 0
    double freq2 = 0; // weighted sum of group 1
    for ( int i = 0; i < k; i++)
    {
        if (arr[i].val == 0)
            freq1 += double (1/arr[i].distance);
        else if (arr[i].val == 1)
            freq2 += double (1/arr[i].distance);
    }
    return (freq1 > freq2 ? 0 : 1);
 }
 
// Driver code
 int main()
 {
    int n = 13; // Number of data points
    Point arr[n];
 
    arr[0].x = 0;
    arr[0].y = 4;
    arr[0].val = 0;
 
    arr[1].x = 1;
    arr[1].y = 4.9;
    arr[1].val = 0;
 
    arr[2].x = 1.6;
    arr[2].y = 5.4;
    arr[2].val = 0;
 
    arr[3].x = 2.2;
    arr[3].y = 6;
    arr[3].val = 0;
 
    arr[4].x = 2.8;
    arr[4].y = 7;
    arr[4].val = 0;
 
    arr[5].x = 3.2;
    arr[5].y = 8;
    arr[5].val = 0;
 
    arr[6].x = 3.4;
    arr[6].y = 9;
    arr[6].val = 0;
 
    arr[7].x = 1.8;
    arr[7].y = 1;
    arr[7].val = 1;
 
    arr[8].x = 2.2;
    arr[8].y = 3;
    arr[8].val = 1;
 
    arr[9].x = 3;
    arr[9].y = 4;
    arr[9].val = 1;
 
    arr[10].x = 4;
    arr[10].y = 4.5;
    arr[10].val = 1;
 
    arr[11].x = 5;
    arr[11].y = 5;
    arr[11].val = 1;
 
    arr[12].x = 6;
    arr[12].y = 5.5;
    arr[12].val = 1;
 
    /*Testing Point*/
    Point p;
    px = 2;
    py = 4;
 
    // Parameter to decide the class of the query point
    int k = 5;
    printf ( "The value classified to query point"
            " is: %d.
" , weightedkNN(arr, n, k, p));
    return 0;
 }

Python3

 # Python3 program to implement the
 # weighted K nearest neighbour algorithm.
 
import math
 
def weightedkNN(points,p,k = 3 ):
    '''
    This function finds classification of p using
    weighted k nearest neighbour algorithm. It assumes only two
    two classes and returns 0 if p belongs to class 0, else
    1 (belongs to class 1).
 
    Parameters -
        points : Dictionary of training points having two keys - 0 and 1
            Each key have a list of training data points belong to that
 
        p : A tuple ,test data point of form (x,y)
 
        k : number of nearest neighbour to consider, default is 3
    '''
 
    distance = []
    for group in points:
        for feature in points[group]:
 
            #calculate the euclidean distance of p from training points
            euclidean_distance = math.sqrt((feature[ 0 ] - p[ 0 ]) * * 2 + (feature[ 1 ] - p[ 1 ]) * * 2 )
 
            # Add a tuple of form (distance,group) in the distance list
            distance.append((euclidean_distance,group))
 
    # sort the distance list in ascending order
    # and select first k distances
    distance = sorted (distance)[:k]
 
    freq1 = 0 # weighted sum of group 0
    freq2 = 0 # weighted sum of group 1
 
    for d in distance:
        if d[ 1 ] = = 0 :
            freq1 + = ( 1 / d[ 0 ])
             
        elif d[ 1 ] = = 1 :
            freq2 + = ( 1 / d[ 0 ])
             
 
    return 0 if freq1>freq2 else 1
 
# Driver function
 def main():
 
    # Dictionary of training points having two keys - 0 and 1
    # key 0 have points belong to class 0
    # key 1 have points belong to class 1
 
    points = { 0 :[( 0 , 4 ),( 1 , 4.9 ),( 1.6 , 5.4 ),( 2.2 , 6 ),( 2.8 , 7 ),( 3.2 , 8 ),( 3.4 , 9 )],
            1 :[( 1.8 , 1 ),( 2.2 , 3 ),( 3 , 4 ),( 4 , 4.5 ),( 5 , 5 ),( 6 , 5.5 )]}
 
    # query point p(x,y)
    p = ( 2 , 4 )
 
    # Number of neighbours
    k = 5
 
    print ( "The value classified to query point is: {}" . format (weightedkNN(points,p,k)))
 
if __name__ = = '__main__' :
    main()

Выход:

Значение, отнесенное к точке запроса: 1

Внимание компьютерщик! Укрепите свои основы с помощью базового курса программирования Python и изучите основы.

Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS. А чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень.

Python Машинное обучение C++

Взвешенный K-NN

C / C ++

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ