Реализация K ближайших соседей

Опубликовано: 4 Января, 2022

Предпосылка: K ближайших соседей

Вступление

Скажем, нам дан набор данных элементов, каждый из которых имеет числовые характеристики (например, рост, вес, возраст и т. Д.). Если количество функций равно n , мы можем представить элементы как точки в n- мерной сетке. Учитывая новый элемент, мы можем рассчитать расстояние от элемента до всех остальных элементов в наборе. Мы выбираем k ближайших соседей и видим, куда классифицируется большинство из этих соседей. Мы классифицируем новый элемент там.

Таким образом, проблема заключается в том, как мы можем вычислить расстояния между элементами. Решение этой проблемы зависит от набора данных. Если значения реальны, мы обычно используем евклидово расстояние. Если значения категориальные или двоичные, мы обычно используем расстояние Хэмминга.

Алгоритм:

Given a new item:
    1. Find distances between new item and all other items
    2. Pick k shorter distances
    3. Pick the most common class in these k distances
    4. That class is where we will classify the new item

Чтение данных

Пусть наш входной файл будет в следующем формате:

Рост, вес, возраст, класс
1.70, 65, 20, Программист
1.90, 85, 33, Строитель
1.78, 76, 31, Строитель
1,73, 74, 24, Программист
1.81, 75, 35, Строитель
1,73, 70, 75, ученый
1.80, 71, 63, ученый
1,75, 69, 25, Программист

Каждый элемент представляет собой строку, и в разделе «Класс» мы видим, к какому элементу относится этот элемент. Значения под названиями элементов («Высота» и т. Д.) - это значение, которое элемент имеет для этой функции. Все значения и характеристики разделены запятыми.

Поместите эти файлы данных в рабочий каталог data2 и data. Выберите один и вставьте содержимое как есть в текстовый файл с именем data .

Мы будем читать из файла (с именем «data.txt») и разделим ввод по строкам:

f = open ('data.txt', 'r');
lines = f.read (). splitlines ();
f.close ();

Первая строка файла содержит имена функций с ключевым словом «Class» в конце. Мы хотим сохранить имена функций в списке:

# Разделить первую строку запятыми,
# удалить первый элемент и 
# сохраняем остальные в список. В
# list теперь содержит функцию 
# имена набора данных.
features = lines [0] .split (',') [: - 1];

Затем мы переходим к самому набору данных. Мы сохраним элементы в список с именами items , элементами которого являются словари (по одному для каждого элемента). Ключи к этим словарям элементов - это имена функций плюс «Класс» для хранения класса элементов. В конце мы хотим перемешать элементы в списке (это мера безопасности на случай, если элементы расположены в странном порядке).

 items = [];
 
for i in range ( 1 , len (lines)):
     
    line = lines[i].split( ', ' );
 
    itemFeatures = { "Class" : line[ - 1 ]};
 
    # Iterate through the features
    for j in range ( len (features)):
     
        # Get the feature at index j
        f = features[j];
        
        # The first item in the line
        # is the class, skip it
        v = float (line[j]);
         
        # Add feature to dict
        itemFeatures[f] = v;
     
    # Append temp dict to items
    items.append(itemFeatures);
     
shuffle(items);

Классификация данных

Теперь, когда данные хранятся в элементах , мы приступаем к созданию нашего классификатора. Для классификатора мы создадим новую функцию Classify . Он будет принимать в качестве входных данных элемент, который мы хотим классифицировать, список элементов и k , количество ближайших соседей.

Если k больше длины набора данных, мы не продолжаем классификацию, так как у нас не может быть ближайших соседей, чем общее количество элементов в наборе данных. (в качестве альтернативы мы могли бы установить k как длину элемента вместо того, чтобы возвращать сообщение об ошибке)

если (k> len (Items)):
        
        # k больше, чем список
        # length, abort
        вернуть «k больше, чем длина списка»;

Мы хотим вычислить расстояние между классифицируемым элементом и всеми элементами обучающего набора, в конечном итоге сохраняя k кратчайших расстояний. Чтобы сохранить текущих ближайших соседей, мы используем список, называемый соседями . Каждый элемент имеет как минимум два значения: одно для расстояния от объекта, который нужно классифицировать, а другое для класса, в котором находится сосед. Мы будем вычислять расстояние с помощью обобщенной формулы Евклида (для n измерений). Затем мы выберем класс, который большую часть времени появляется у соседей, и это будет наш выбор. В коде:

 def Classify(nItem, k, Items):
    if (k > len (Items)):
         
        # k is larger than list
        # length, abort
        return "k larger than list length" ;
     
    # Hold nearest neighbors.
    # First item is distance,
    # second class
    neighbors = [];
 
    for item in Items:
       
        # Find Euclidean Distance
        distance = EuclideanDistance(nItem, item);
 
        # Update neighbors, either adding
        # the current item in neighbors
        # or not.
        neighbors = UpdateNeighbors(neighbors, item, distance, k);
 
    # Count the number of each
    # class in neighbors
    count = CalculateNeighborsClass(neighbors, k);
 
    # Find the max in count, aka the
    # class with the most appearances.
    return FindMax(count); 

Нам необходимо реализовать внешние функции: EuclideanDistance , UpdateNeighbors , CalculateNeighborsClass и FindMax .

Нахождение евклидова расстояния

Обобщенная формула Евклида для двух векторов x и y такова:

расстояние = sqrt {(x_ {1} -y_ {1}) ^ 2 + (x_ {2} -y_ {2}) ^ 2 + ... + (x_ {n} -y_ {n}) ^ 2}

В коде:

 def EuclideanDistance(x, y):
     
    # The sum of the squared
    # differences of the elements
    S = 0 ;
     
    for key in x.keys():
        S + = math. pow (x[key] - y[key], 2 );
 
    # The square root of the sum
    return math.sqrt(S); 

Обновление соседей

У нас есть список соседей (длина которого не должна превышать k ), и мы хотим добавить в список элемент с заданным расстоянием. Сначала мы проверим, имеют ли соседи длину k . Если его меньше, мы добавляем к нему элемент независимо от расстояния (так как нам нужно заполнить список до k, прежде чем мы начнем отклонять элементы). Если нет, мы проверим, находится ли элемент на меньшем расстоянии, чем элемент с максимальным расстоянием в списке. Если это правда, мы заменим элемент с максимальным расстоянием новым элементом.

Чтобы быстрее найти элемент максимального расстояния, мы сохраним список в порядке возрастания. Итак, последний элемент в списке будет иметь максимальное расстояние. Мы заменим его новым товаром и снова отсортируем.

Чтобы ускорить этот процесс, мы можем реализовать сортировку вставкой, при которой мы вставляем новые элементы в список без необходимости сортировать весь список. Код для этого довольно длинный и, хотя и простой, утомляет руководство.

 def UpdateNeighbors(neighbors, item, distance, k):
     
    if ( len (neighbors) > distance):
             
            # If yes, replace the last
            # element with new item
            neighbors[ - 1 ] = [distance, item[ "Class" ]];
            neighbors = sorted (neighbors);
 
    return neighbors; 

CalculateNeighborsClass

Здесь мы рассчитаем класс, который чаще всего встречается у соседей . Для этого мы будем использовать другой словарь, называемый count , где ключи - это имена классов, появляющиеся в соседях . Если ключа не существует, мы добавим его, иначе мы увеличим его значение.

 def CalculateNeighborsClass(neighbors, k):
    count = {};
     
    for i in range (k):
         
        if (neighbors[i][ 1 ] not in count):
         
            # The class at the ith index
            # is not in the count dict.
            # Initialize it to 1.
            count[neighbors[i][ 1 ]] = 1 ;
        else :
             
            # Found another item of class
            # c[i]. Increment its counter.
            count[neighbors[i][ 1 ]] + = 1 ;
 
    count; return 

FindMax

Мы введем в эту функцию счетчик словаря, который мы создаем в CalculateNeighborsClass, и вернем его максимальное значение.

 def FindMax(countList):
     
    # Hold the max
    maximum = - 1 ;
     
    # Hold the classification
    classification = "";
     
    for key in countList.keys():
       
        if (countList[key] > maximum):
            maximum = countList[key];
            classification = key;
 
    return classification, maximum; 

Заключение

На этом урок по kNN закончен.

Теперь вы можете классифицировать новые элементы, задав k по своему усмотрению. Обычно для k используется нечетное число, но это не обязательно. Чтобы классифицировать новый элемент, вам необходимо создать словарь с ключами, названиями функций и значениями, характеризующими элемент. Пример классификации:

newItem = {'Рост': 1,74, 'Вес': 67, 'Возраст': 22};
print Classify (newItem, 3, items);

Полный код вышеуказанного подхода приведен ниже: -

 # Python Program to illustrate
 # KNN algorithm
 
# For pow and sqrt
 import math
 from random shuffle import
 
###_Reading_### def ReadData(fileName):
 
    # Read the file, splitting by lines
    f = open (fileName, 'r' )
    lines = f.read().splitlines()
    f.close()
 
    # Split the first line by commas,
    # remove the first element and save
    # the rest into a list. The list
    # holds the feature names of the
    # data set.
    features = lines[ 0 ].split( ', ' )[: - 1 ]
 
    items = []
 
    for i in range ( 1 , len (lines)):
         
        line = lines[i].split( ', ' )
 
        itemFeatures = { 'Class' : line[ - 1 ]}
 
        for j in range ( len (features)):
             
            # Get the feature at index j
            f = features[j]
 
            # Convert feature value to float
            v = float (line[j])
             
             # Add feature value to dict
            itemFeatures[f] = v
         
        items.append(itemFeatures)
 
    shuffle(items)
 
    return items
 
 
###_Auxiliary Function_### def EuclideanDistance(x, y):
     
    # The sum of the squared differences
    # of the elements
    S = 0
     
    for key in x.keys():
        S + = math. pow (x[key] - y[key], 2 )
 
    # The square root of the sum
    return math.sqrt(S)
 
def CalculateNeighborsClass(neighbors, k):
    count = {}
 
    for i in range (k):
        if neighbors[i][ 1 ] not in count:
 
            # The class at the ith index is
            # not in the count dict.
            # Initialize it to 1.
            count[neighbors[i][ 1 ]] = 1
        else :
 
            # Found another item of class
            # c[i]. Increment its counter.
            count[neighbors[i][ 1 ]] + = 1
 
    count return
 
def FindMax( Dict ):
 
    # Find max in dictionary, return
    # max value and max index
    maximum = - 1
    classification = ''
 
    for key in Dict .keys():
         
        if Dict [key] > maximum:
            maximum = Dict [key]
            classification = key
 
    return (classification, maximum)
 
 
###_Core Functions_### def Classify(nItem, k, Items):
 
    # Hold nearest neighbours. First item
    # is distance, second class
    neighbors = []
 
    for item in Items:
 
        # Find Euclidean Distance
        distance = EuclideanDistance(nItem, item)
 
        # Update neighbors, either adding the
        # current item in neighbors or not.
        neighbors = UpdateNeighbors(neighbors, item, distance, k)
 
    # Count the number of each class
    # in neighbors
    count = CalculateNeighborsClass(neighbors, k)
 
    # Find the max in count, aka the
    # class with the most appearances
    return FindMax(count)
 
 
def UpdateNeighbors(neighbors, item, distance,
                                          k, ):
    if len (neighbors) < k:
 
        # List is not full, add
        # new item and sort
        neighbors.append([distance, item[ 'Class' ]])
        neighbors = sorted (neighbors)
    else :
 
        # List is full Check if new
        # item should be entered
        if neighbors[ - 1 ][ 0 ] > distance:
 
            # If yes, replace the
            # last element with new item
            neighbors[ - 1 ] = [distance, item[ 'Class' ]]
            neighbors = sorted (neighbors)
 
    return neighbors
 
###_Evaluation Functions_### def K_FoldValidation(K, k, Items):
     
    if K > len (Items):
        return - 1
 
    # The number of correct classifications
    correct = 0
     
    # The total number of classifications
    total = len (Items) * (K - 1 )
     
    # The length of a fold
    l = int ( len (Items) / K)
 
    for i in range (K):
 
        # Split data into training set
        # and test set
        trainingSet = Items[i * l:(i + 1 ) * l]
        testSet = Items[:i * l] + Items[(i + 1 ) * l:]
 
        for item in testSet:
            itemClass = item[ 'Class' ]
 
            itemFeatures = {}
 
            # Get feature values
            for key in item:
                if key ! = 'Class' :
 
                    # If key isn't "Class", add
                    # it to itemFeatures
                    itemFeatures[key] = item[key]
 
            # Categorize item based on
            # its feature values
            guess = Classify(itemFeatures, k, trainingSet)[ 0 ]
 
            if guess = = itemClass:
 
                # Guessed correctly
                correct + = 1
 
    accuracy = correct / float (total)
    accuracy return
 
 
def Evaluate(K, k, items, iterations):
 
    # Run algorithm the number of
    # iterations, pick average
    accuracy = 0
     
    for i in range (iterations):
        shuffle(items)
        accuracy + = K_FoldValidation(K, k, items)
 
    accuracy print / float (iterations)
 
 
###_Main_### def main():
    items = ReadData( 'data.txt' )
 
    Evaluate( 5 , 5 , items, 100 )
 
if __name__ = = '__main__' :
    main()

Выход:

0,9375

Производительность может варьироваться от машины к машине. Код включает функцию Fold Validation, но она не связана с алгоритмом, она предназначена для расчета точности алгоритма.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Машинное обучение Алгоритмы

Реализация K ближайших соседей

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