Рубрики

K-Ближайшие соседи

K-Nearest Neighbours является одним из самых основных, но важных алгоритмов классификации в машинном обучении. Он принадлежит к контролируемой области обучения и находит широкое применение в распознавании образов, интеллектуальном анализе данных и обнаружении вторжений.

Он широко доступен в реальных сценариях, так как он непараметрический, то есть он не делает каких-либо базовых предположений о распределении данных (в отличие от других алгоритмов, таких как GMM , которые предполагают гауссово распределение данных) ,

Нам даны некоторые предварительные данные (также называемые данными обучения), которые классифицируют координаты по группам, идентифицированным атрибутом.

В качестве примера рассмотрим следующую таблицу точек данных, содержащую две функции:

Теперь, учитывая другой набор точек данных (также называемых данными тестирования), распределите эти точки по группе, проанализировав обучающий набор. Обратите внимание, что несекретные точки отмечены как «Белые».

Интуиция
Если мы нанесем эти точки на график, мы сможем найти несколько кластеров или групп. Теперь, учитывая неклассифицированную точку, мы можем назначить ее группе, наблюдая, к какой группе принадлежат ее ближайшие соседи. Это означает, что точка, близкая к группе точек, классифицированных как «Красные», имеет более высокую вероятность быть классифицированной как «Красные».

Интуитивно понятно, что первая точка (2.5, 7) должна быть классифицирована как «зеленая», а вторая точка (5.5, 4.5) — как «красная».

Алгоритм
Пусть m будет количеством образцов обучающих данных. Пусть p неизвестная точка.

  1. Сохраните обучающие образцы в массиве точек данных arr []. Это означает, что каждый элемент этого массива представляет кортеж (x, y).
  2. for i=0 to m:
      Calculate Euclidean distance d(arr[i], p).
  3. Сделайте набор S из K наименьших полученных расстояний. Каждое из этих расстояний соответствует уже классифицированной точке данных.
  4. Верните ярлык большинства среди S.

K можно сохранить как нечетное число, чтобы мы могли вычислить явное большинство в случае, когда возможны только две группы (например, Red / Blue). С увеличением K мы получаем более гладкие, более четкие границы для разных классификаций. Кроме того, точность вышеупомянутого классификатора увеличивается по мере того, как мы увеличиваем количество точек данных в обучающем наборе.

Пример программы
Предположим, 0 и 1 в качестве двух классификаторов (групп).

C / C ++

// C ++ программа для поиска групп неизвестных
// Точки, использующие алгоритм K ближайшего соседа.
#include <bits/stdc++.h>

using namespace std;

  

struct Point

{

    int val;     // Группа точек

    double x, y;     // Координата точки

    double distance; // Расстояние от контрольной точки

};

  
// Используется для сортировки массива точек путем увеличения
// порядок расстояния

bool comparison(Point a, Point b)

{

    return (a.distance < b.distance);

}

  
// Эта функция находит классификацию точки p, используя
// k алгоритм ближайшего соседа. Предполагается только два
// группирует и возвращает 0, если p принадлежит группе 0, иначе
// 1 (принадлежит группе 1).

int classifyAPoint(Point arr[], int n, int k, Point p)

{

    // Заполняем расстояния всех точек от p

    for (int i = 0; i < n; i++)

        arr[i].distance =

            sqrt((arr[i].x - p.x) * (arr[i].x - p.x) +

                 (arr[i].y - p.y) * (arr[i].y - p.y));

  

    // Сортировка точек по расстоянию от p

    sort(arr, arr+n, comparison);

  

    // Теперь рассмотрим первые k элементов и только

    // две группы

    int freq1 = 0;     // Частота группы 0

    int freq2 = 0;     // Частота группы 1

    for (int i = 0; i < k; i++)

    {

        if (arr[i].val == 0)

            freq1++;

        else if (arr[i].val == 1)

            freq2++;

    }

  

    return (freq1 > freq2 ? 0 : 1);

}

  
// Код драйвера

int main()

{

    int n = 17; // Количество точек данных

    Point arr[n];

  

    arr[0].x = 1;

    arr[0].y = 12;

    arr[0].val = 0;

  

    arr[1].x = 2;

    arr[1].y = 5;

    arr[1].val = 0;

  

    arr[2].x = 5;

    arr[2].y = 3;

    arr[2].val = 1;

  

    arr[3].x = 3;

    arr[3].y = 2;

    arr[3].val = 1;

  

    arr[4].x = 3;

    arr[4].y = 6;

    arr[4].val = 0;

  

    arr[5].x = 1.5;

    arr[5].y = 9;

    arr[5].val = 1;

  

    arr[6].x = 7;

    arr[6].y = 2;

    arr[6].val = 1;

  

    arr[7].x = 6;

    arr[7].y = 1;

    arr[7].val = 1;

  

    arr[8].x = 3.8;

    arr[8].y = 3;

    arr[8].val = 1;

  

    arr[9].x = 3;

    arr[9].y = 10;

    arr[9].val = 0;

  

    arr[10].x = 5.6;

    arr[10].y = 4;

    arr[10].val = 1;

  

    arr[11].x = 4;

    arr[11].y = 2;

    arr[11].val = 1;

  

    arr[12].x = 3.5;

    arr[12].y = 8;

    arr[12].val = 0;

  

    arr[13].x = 2;

    arr[13].y = 11;

    arr[13].val = 0;

  

    arr[14].x = 2;

    arr[14].y = 5;

    arr[14].val = 1;

  

    arr[15].x = 2;

    arr[15].y = 9;

    arr[15].val = 0;

  

    arr[16].x = 1;

    arr[16].y = 7;

    arr[16].val = 0;

  

    / * Точка тестирования * /

    Point p;

    p.x = 2.5;

    p.y = 7;

  

    // Параметр для определения группы точек тестирования

    int k = 3;

    printf ("The value classified to unknown point"

            " is %d.\n", classifyAPoint(arr, n, k, p));

    return 0;

}

питон

# Python3 программа для поиска групп неизвестных
# Очки, используя алгоритм K ближайшего соседа.

  

import math

  

def classifyAPoint(points,p,k=3):

    «»»

     Эта функция находит классификацию р, используя

     k алгоритм ближайшего соседа. Предполагается только два

     групп и возвращает 0, если р принадлежит группе 0, иначе

      1 (принадлежит к группе 1).

  

      Параметры -

          очки: Словарь тренировочных очков, имеющий две клавиши - 0 и 1

                   Каждый ключ имеет список точек данных обучения, принадлежащих к этому

  

          p: кортеж, тестовая точка данных вида (x, y)

  

          k: количество ближайших соседей, по умолчанию 3

    «»»

  

    distance=[]

    for group in points:

        for feature in points[group]:

  

            # вычислить евклидово расстояние р от тренировочных точек

            euclidean_distance = math.sqrt((feature[0]-p[0])**2 +(feature[1]-p[1])**2)

  

            # Добавить кортеж формы (расстояние, группа) в список расстояний

            distance.append((euclidean_distance,group))

  

    # сортировка списка расстояний в порядке возрастания

    # и выберите первые k расстояний

    distance = sorted(distance)[:k]

  

    freq1 = 0 # частота группы 0

    freq2 = 0 # частота группы 1

  

    for d in distance:

        if d[1] == 0:

            freq1 += 1

        elif d[1] == 1:

            freq2 += 1

  

    return 0 if freq1>freq2 else 1

  
# функция драйвера

def main():

  

    # Словарь тренировочных точек, имеющий две клавиши - 0 и 1

    # ключ 0 имеет баллы, принадлежащие к классу 0

    # ключ 1 имеет баллы, принадлежащие к классу 1

  

    points = {0:[(1,12),(2,5),(3,6),(3,10),(3.5,8),(2,11),(2,9),(1,7)],

              1:[(5,3),(3,2),(1.5,9),(7,2),(6,1),(3.8,1),(5.6,4),(4,2),(2,5)]}

  

    # контрольная точка p (x, y)

    p = (2.5,7)

  

    Количество соседей

    k = 3

  

    print("The value classified to unknown point is: {}".\

          format(classifyAPoint(points,p,k)))

  

if __name__ == '__main__':

    main()

      
# Этот код предоставлен Атулом Кумаром (www.fb.com/atul.kr.007)


Выход:

The value classified to unknown point is 0.

Эта статья предоставлена Ананней Уберой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

K-Ближайшие соседи

0.00 (0%) 0 votes