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