Автор: г-н Data Science

Краткий обзор:

k-Nearest Neighbor (KNN) - это алгоритм классификации, не путать с k-средними, это два очень разных алгоритма с очень разными применениями. k-Means - это неконтролируемый алгоритм кластеризации, при условии, что некоторые данные k-Means будут кластеризовать эти данные в k групп, где k - положительное целое число. k-Nearest Neighbor - это контролируемый алгоритм классификации, обратите внимание - контролируемый алгоритм использует обучающие данные, тогда как неконтролируемый алгоритм не имеет обучающих данных. Мы используем KNN, чтобы предсказать, к какой группе принадлежит точка данных, например, в этой статье мы будем использовать KNN для предсказать, есть ли у человека диабет, на основании ряда других показателей здоровья.

В ситуации, когда вам нужно классифицировать данные, алгоритм k-Nearest Neighbor является одной из возможностей, есть и другие, например:

  • Наивный байесовский
  • Древо решений
  • Стохастический градиентный спуск

Как работает KNN?

Чтобы увидеть, как работает KNN, давайте нанесем на график некоторые данные. Данные разделены на две группы: три синих точки данных в нижнем левом углу (группа 1) и три синих точки данных в правом верхнем углу (группа 2). Если мы добавим новую точку, красную точку, принадлежит ли она группе 1 или группе 2?

import matplotlib.pyplot as plt
ax = plt.subplot(1, 1, 1)
ax.scatter([1, 1.3, 1.25, 2.9, 3, 3.25], [1, 1.5, 1.0, 2.7, 3, 3.25])
ax.plot(1.7, 2, "or");

Если мы используем KNN для решения этой проблемы и установим k = 5, алгоритм будет искать пять точек данных, ближайших к красной точке. Представьте, что рисуете круг с красной точкой в ​​центре, радиус этого круга - это расстояние до пятой ближайшей синей точки. Круг будет заключать 3 точки в группе 1 и 2 точки в группе 2. Алгоритм подсчитывает «голоса» и решает, что красная точка данных принадлежит группе 1. Существует несколько различных способов вычисления расстояния, например:

Существуют и другие меры расстояния, такие как косинусное расстояние и расстояние Жаккара, но они чаще используются, скажем, в НЛП для измерения сходства или различия между двумя частями текста.

Справочная информация о K-ближайшем соседе и проблемах классификации:

Что такое проблема классификации?

Распространенная проблема науки о данных требует классификации или маркировки данных, например, в школе или колледже можем ли мы идентифицировать учащихся с повышенным риском неудачи, или по некоторым данным пациентов мы можем идентифицировать пациентов, у которых может развиться диабет. В этих случаях возникают проблемы с двоичной классификацией. В случае студентов класс A - это учащиеся, подверженные риску неуспеваемости, а класс B состоит из остальных студентов. Иногда задачи классификации могут иметь более двух классов.

Практическое применение KNN

Исследовательская статья [1], перечисленная ниже в разделе «Справочная информация», является примером использования KNN для выявления неуспевающих студентов. В этом случае студенты были зачислены на онлайн-курс слепой печати. На основе этих данных исследователи обнаружили, что алгоритм KNN хорошо обобщается и дает хорошие результаты. Во второй исследовательской статье [2] описывается использование энтропийно-взвешенной локальной гиперплоскости k-ближайшего соседа (EWHK) для раннего обнаружения опухолей и вводится один из специализированных вариантов KNN. В справочной статье [3] обсуждаются некоторые проблемы с KNN и некоторыми вариантами KNN. Существование этих вариантов KNN частично связано с недостатками алгоритма. У всех алгоритмов классификации есть свои плюсы и минусы. В случае с KNN к минусам можно отнести:

  • высокая стоимость вычислений,
  • большая потребность в памяти,
  • выбор подходящего значения входного параметра k

В этой статье мы будем использовать KNN для решения задачи классификации, обнаруживающей диабет.

Прежде чем мы начнем, давайте настроим вашу среду:

Чтобы использовать KNN, вам необходимо установить следующие библиотеки Python:

Использование алгоритма K-ближайшего соседа

Давайте посмотрим на несколько примеров:

Пример 1 - качество данных

Качество данных - выявление и устранение проблем

Прежде чем погрузиться в машинное обучение или глубокое обучение, может быть полезно немного изучить данные. Мы хотим выявить и, если возможно, исправить любые проблемы с самого начала.

Мы будем использовать набор данных по диабету. Этот набор данных хорошо известен и доступен из разных источников, просто выполните поиск по запросу Pima Diabetes Dataset. Я загрузил набор данных в тот же каталог, что и этот блокнот.

import pandas as pd
df = pd.read_csv('diabetes.csv')
df.head()

В наборе данных 9 функций (столбцов), последняя характеристика, Результат, - это та, которую мы попытаемся предсказать. Принимает одно из двух значений: 1 или 0. Где 1 означает, что у человека был диабет. Мы можем использовать функцию описания, чтобы получить некоторую статистику по данным:

df.describe()

Если мы посмотрим на минимальные значения для различных функций, имеют ли они смысл? По некоторым функциям ответ отрицательный, например, нулевое кровяное давление не кажется разумным, также ИМТ = 0 не имеет смысла. Таким образом, очевидно, что при составлении этого набора данных возникли некоторые проблемы со сбором и вводом данных. Следующий шаг - определить, сколько строк содержат проблемные данные. Мы определим данные о проблеме как BloodPressure = 0 или BMI = 0 или SkinThickness = 0.

У нас есть 768 строк в фрейме данных:

df.shape
(768, 9)

Мы можем определить проблемные строки:

df_problem_rows = df[(df['BloodPressure']==0) | (df['SkinThickness']==0) | (df['BMI']==0)]

С помощью pandas вы можете создавать меньшие фреймы данных, выбирая строки, которые соответствуют одному или нескольким условиям. В приведенном выше ‘|’ = OR вы также можете использовать ‘&’ = AND.

df_problem_rows.head()

df_problem_rows.shape
(231, 9)

У нас 231 проблемная строка, что составляет 30% от исходной строки набора данных.

Теперь, когда мы определили проблемы, нам нужно решить, что с ними делать. Возможны разные варианты:

  • игнорировать проблему
  • избавиться от всех проблемных строк
  • как-то исправить данные в проблемных строках.

Игнорирование проблем, особенно когда они затрагивают почти треть строк, может быть худшим вариантом. Из оставшихся вариантов: избавление от всех проблемных строк не только устраняет проблемы, но и значительно сокращает объем доступных обучающих данных. Третий вариант требует замены нулей ненулевыми значениями, например, с использованием среднего значения для столбца.

Давайте создадим два новых фрейма данных с именами df_reject и df_replace. В df_reject мы удалим все проблемные строки, а в df_replace мы заменим ноль на среднее значение столбца.

df_reject = df[(df['BloodPressure']!=0) & (df['SkinThickness']!=0) & (df['BMI']!=0)]
df_replace = df
columns = ['BloodPressure', 'SkinThickness', 'BMI']
for col in columns:
    val = df[col].mean()
    df_replace[col] = df[col].replace(0, val)
df_reject.head()

df_replace.head(10)

Теперь у нас есть три версии набора данных: исходная = df, версия со всеми удаленными проблемными строками = df_reject и версия со всеми замененными проблемными значениями, df_replaced. В примере 3 мы сравним оценки точности для df_replace и df_reject. В следующем примере мы рассмотрим проблему нормализации данных.

Пример 2 - Нормализация данных

from sklearn import preprocessing

В наборе данных есть функция под названием Результат, это двоичная функция, значение 1 указывает на то, что у человека был диабет. Это функция, которую мы попытаемся предсказать. Все остальные функции являются числовыми, поэтому нам не нужно преобразовывать какие-либо текстовые данные, но может потребоваться их нормализация. Если вы посмотрите на различные функции в dataframe df, вы увидите, что они имеют разные диапазоны. Если бы мы не нормализовали данные, функции с более высокими значениями могли бы считаться алгоритмом более важными, что дало бы менее чем идеальный результат прогноза. Это обсуждение нормализации и KNN на Stackoverflow интересно. Помните, что с помощью KNN мы вычисляем расстояния, это означает, что функции с более высокими значениями могут иметь приоритет над функциями с более низкими значениями. Нормализация - это то, что мы можем исследовать. Итак, давайте создадим нормализованные версии двух фреймов данных: df_replace и df_reject.

Есть разные способы сделать это. Сначала мы воспользуемся функцией MinMaxScaler () из кода предварительной обработки Scikit Learn.

x = df.values 
min_max_scaler = preprocessing.MinMaxScaler()
x_scaled = min_max_scaler.fit_transform(x)
df_n1 = pd.DataFrame(x_scaled)
df_n1.head()

Мы можем добиться того же, используя только Pandas:

df_replace_n=(df_replace-df_replace.min())/(df_replace.max()-df_replace.min())
df_replace_n.head()

df_reject_n=(df_reject-df_reject.min())/(df_reject.max()-df_reject.min())
df_reject_n.head()

В дополнение к нормализации min-max мы также можем использовать среднюю нормализацию, мы назовем этот фрейм данных df_mn:

df_mn=(df-df.mean())/df.std()
df_mn.head()

Теперь у нас есть 2 версии нормализованного фрейма данных: df_replace_n и df_reject_n. В следующем примере мы применим KNN к двум фреймам данных. Примечание - в данных нет пропущенных значений.

Пример 3 - Применение KNN к данным

Затем мы разделим данные на X и y, где y - это функция результата, которую мы пытаемся предсказать, а X - это набор всех других функций. Мы должны сделать это как для фреймов данных df_replace_n, так и для фреймов данных df_reject_n.

X_replace_n = df_replace_n.drop("Outcome",axis = 1)
y_replace_n = df_replace_n.Outcome
X_reject_n = df_reject_n.drop("Outcome",axis = 1)
y_reject_n = df_reject_n.Outcome

KNN - это контролируемый алгоритм, поэтому нам нужно разделить данные на тестовые и обучающие данные:

from sklearn.model_selection import train_test_split
X_train_replace,X_test_replace,y_train_replace,y_test_replace = train_test_split(X_replace_n,y_replace_n,test_size=0.3,random_state=42, stratify=y_replace_n)
from sklearn.model_selection import train_test_split
X_train_reject,X_test_reject,y_train_reject,y_test_reject = train_test_split(X_reject_n,y_reject_n,test_size=0.3,random_state=42, stratify=y_reject_n)

Параметр стратификации обеспечивает сохранение пропорции значений при разбиении. Таким образом, если 75% неразделенных данных имели Результат = 1, тогда разделенные данные сохраняли бы это соотношение.

А как насчет k в KNN? Как узнать, какое значение K использовать? Давайте попробуем провести эксперимент, изменив значение k для одного из наших фреймов данных:

from sklearn.neighbors import KNeighborsClassifier

test_scores = []

for i in range(1,10):

    knn = KNeighborsClassifier(i)
    knn.fit(X_train_replace,y_train_replace)
    
    test_scores.append(knn.score(X_test_replace,y_test_replace))
print(test_scores)
[0.7402597402597403, 0.70995670995671, 0.7186147186147186, 0.70995670995671, 0.70995670995671, 0.7229437229437229, 0.7402597402597403, 0.7359307359307359, 0.7402597402597403]

Есть некоторые различия в точности в зависимости от значения k. Диапазон точности составляет от 70% до 75%. Теоретически низкие значения k дают низкое смещение, но высокая дисперсия и большое значение k будут иметь более гладкую границу принятия решения, что означает меньшую дисперсию, но более высокую смещение.

Значение k = 9 дает хороший показатель точности, давайте сравним результаты для df_reject_n и df_replace_n

knn_9 = KNeighborsClassifier(9)
knn_9.fit(X_train_reject,y_train_reject)
print(knn_9.score(X_test_reject,y_test_reject))
0.7962962962962963
knn_9.fit(X_train_replace,y_train_replace)
print(knn_9.score(X_test_replace,y_test_replace))
0.7402597402597403

Таким образом, отказ от проблемных строк создал меньший обучающий фрейм данных, но он обеспечил более высокие оценки точности, чем фрейм данных, в котором мы заменили нули средним значением для столбца.

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

from sklearn.metrics import confusion_matrix
y_pred_reject = knn_9.predict(X_test_reject)
confusion_matrix(y_test_reject,y_pred_reject,normalize='true')
array([[0.93518519, 0.06481481],
       [0.27777778, 0.72222222]])
y_pred_replace = knn_9.predict(X_test_replace)
confusion_matrix(y_test_replace,y_pred_replace,normalize='true')
array([[0.86666667, 0.13333333],
       [0.49382716, 0.50617284]])

Сверху мы можем видеть пропорции истинных и ложных прогнозов для обоих ярлыков: Результат = 1 (положительный) и Результат = 0 (отрицательный). Поместим данные в более презентабельную таблицу:

Таким образом, в случае df_reject_n KNN смог обеспечить точность 94% для отрицательных результатов (не было диабета), в случае df_replace_n результаты для истинно отрицательных результатов все еще были хорошими на уровне 87%. Разница в производительности была более очевидной в способности предсказать Результат = 1 (люди с диабетом). В этом случае данные df_replace_n управляли только точностью 51%. Поскольку есть только две метки результата (1 или 0), мы ожидаем около 50% точности, просто предполагая. У df_reject_n точность 72% лучше, чем у 94% для отрицательных результатов.

Оба набора данных лучше справлялись с прогнозированием отрицательных результатов. Можем ли мы объяснить, почему это произошло?

Нам нужно вернуться и посмотреть на исходный фрейм данных df.

df['Outcome'].value_counts().plot(kind='bar');

Мы видим, что в исходных данных была некоторая предвзятость, было больше примеров Результат = 0 (отрицательные результаты). Это могло быть причиной того, что KNN было труднее предсказывать положительные результаты с помощью этих данных. Теоретически существует прямая корреляция между количеством и качеством данных и точностью прогнозирования данного алгоритма.

Подводя итог: точность, которую мы можем достичь, может зависеть от нескольких факторов, в том числе:

  • используемый алгоритм
  • любые дисбалансы / предвзятости в данных
  • качество данных
  • как мы решаем вопросы качества
  • мы нормализуем данные
  • в случае KNN значение k может повлиять на оценку точности

Краткий обзор того, что вы узнали:

Если вы зашли так далеко, вы должны хорошо понимать:

  • Как подобрать и использовать алгоритм KNN
  • Как заменить проблемные значения в кадре данных средними значениями
  • Как нормализовать данные в фрейме данных, используя либо подход минимума / максимума, либо подход среднего значения
  • Несмотря на то, что это простой алгоритм с ограничениями, у него есть несколько успешных реальных приложений, некоторые примеры см. В справочном разделе ниже.

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

Использованная литература:

  1. Таннер, Т., Прогнозирование и предотвращение неуспеваемости учащихся - использование k-ближайшего соседа, дата извлечения: 14.03.2021, https://core.ac.uk/download/pdf/14920734.pdf
  2. Цинбо Ли, Усовершенствованный метод k-ближайшего соседа для диагностики рака груди, дата получения: 14.03.2021, https://pubs.rsc.org/en/content/articlelanding/2018/an/c8an00189h#!divAbstract
  3. Паскаль В., Алгоритмы K-локальной гиперплоскости и выпуклого ближайшего соседа по расстоянию, дата извлечения: 14.03.2021, https://www.researchgate.net/publication/2539168_K-Local_Hyperplane_and_Convex_Distance_Nearest_Neighbor_Algorithms

Свяжитесь с г-ном Data Science:

MrDataScience.com, GitHub, Средний,