Для Xiaobai: Введение в алгоритм K-ближайших соседей

Автор: Филипп Муэнс

Перевод: Лао Ци

Рекомендация книги, связанная с этой статьей: «Подготовка данных и разработка функций» (доступна во флагманском магазине Tmall Electronic Industry Press)

Код этой статьи опубликован на онлайн-платформе Baidu AI Studio, обратите внимание на паблик-аккаунт WeChat»Класс Лао Ци", и ответил:#真实姓名+手机号+‘案例’#, подайте заявку на участие в курсе «Машинное обучение», содержащем случай с бензолом, и получите больше случаев машинного обучения, включая этот случай.Уведомление:Ответное сообщение (1) должно начинаться с#Начало и конец (2) должны быть настоящим именем и номером мобильного телефона.

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

Давайте подробнее рассмотрим математику, лежащую в основе основных идей, и процесс их превращения в код.

принцип

Представьте, что мы приглашаем 100 владельцев собак привести своих собак для проведения статистического эксперимента, который мы хотим провести. Каждая собака, участвовавшая в эксперименте, была 1 из 4 интересующих нас разных пород. В сотрудничестве с этими собаками и их владельцами мы измерили 3 различных атрибута каждой собаки:

вес: вес (кг)
высота: высота (см)
бдительность: бдительность (от 0 до 1 [1 = очень бдительный, 0 = почти бдительный])

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

После сбора данных для каждой собаки мы получили 100 измерений, каждое из которых было помечено соответствующей породой собаки.

Ниже приведен пример:

\begin{pmatrix}0.5\\0.8\\0.1\end{pmatrix}=Podenco

Чтобы лучше понять данные, лучше всего их пометить. Поскольку мы собрали 3 разных измерения (вес, рост и бдительность), можно спроецировать все 100 точек данных в трехмерное пространство и раскрасить каждую точку данных в соответствии с ее меткой (например, поставить «Podenco» окрашен в коричневый цвет).

К сожалению, у нас возникли проблемы с нанесением этих данных на график, потому что мы забыли пометить одно из измерений. У нас есть вес, рост и настороженность собаки, но мы почему-то забыли указать породу собаки.

Теперь, когда у нас есть измерения для других собак, можно ли сделать вывод о породе этой собаки? Мы по-прежнему можем добавлять немаркированные данные в существующее трехмерное пространство, где находятся все остальные цветные точки данных. Но как нам раскрасить эту спекулятивную точку данных?

Возможное решение состоит в том, чтобы посмотреть на 5 соседей вокруг проблемной точки данных и посмотреть, какого они цвета. Если большинство этих точек данных помечены как «Podenco», то вполне вероятно, что наши измерения были взяты и из Podenco.

Это именно то, что делает алгоритм K-NN (алгоритм k-ближайших соседей). Алгоритм предсказывает класс невидимой точки данных на основе ее K ближайших соседей и подавляющего большинства этих K ближайших соседей. Рассмотрим подробнее эту задачу с математической точки зрения.

две концепции

Чтобы классифицировать данные с помощью K-NN, нам нужно реализовать только две концепции.

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

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

функция расстояния

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

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

Выражается в математической записи следующим образом:

d(x, y)=d(y, x)=\sqrt{\sum_{i=1}^N(x_i-y_i)^2}

Поясним эту формулу на примере. Пусть есть два вектора $\overrightarrow{a}$ и $\overrightarrow{b}$ , евклидово расстояние между ними рассчитывается следующим образом:

\overrightarrow{a}=\begin{pmatrix}1\\2\\3\\4\end{pmatrix} \overrightarrow{b}=\begin{pmatrix}5\\6\\7\\8\end{pmatrix}

d(\overrightarrow{a},\overrightarrow{b})=d(\overrightarrow{b},\overrightarrow{a})=\sqrt{(1-5)^2+(2-6)^2+(3-7)^2+(4-8)^2}??=\sqrt{64}=8

Результат перевода этого в код выглядит следующим образом:

def distance(x: List[float], y: List[float]) -> float:
    assert len(x) == len(y)
    interim_res: float = 0
    for i, _ in enumerate(x):
        interim_res += (x[i] - y[i]) ** 2
    return sqrt(interim_res)

assert distance([1, 2, 3, 4], [5, 6, 7, 8]) == 8

Очень хороший. Мы только что реализовали нашу первую сборку: функцию евклидова расстояния.

функция голосования

Далее нам нужно реализовать функцию голосования. Функция голосования принимает список меток в качестве входных данных и возвращает «наиболее распространенную» метку для этого списка. Хотя это кажется легко достижимым, мы должны сделать шаг назад и рассмотреть потенциальные краеугольные случаи, с которыми мы можем столкнуться.

Один из таких случаев — когда у нас есть два или более «наиболее распространенных» ярлыка:

# Do we return `a` or `b`?
labels: List[str] = ['a', 'a', 'b', 'b', 'c']

Для этих сценариев нам необходимо реализовать механизм принятия решений.

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

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

Ниже показан этот процесс на основе приведенного выше примера с этикеткой:

# Do we return `a` or `b`?
labels: List[str] = ['a', 'a', 'b', 'b', 'c']

# Remove one entry. We're still unsure if we should return `a` or `b`
labels: List[str] = ['a', 'a', 'b', 'b']

# Remove another entry. Now it's clear that `a` is the "winner"
labels: List[str] = ['a', 'a', 'b']

Преобразуем этот алгоритм в функцию и назовем ееmajority_vote:

def majority_vote(labels: List[str]) -> str:
    counted: Counter = Counter(labels)
    winner: List[str] = []
    max_num: int = 0
    most_common: List[Tuple[str, int]]
    for most_common in counted.most_common():
        label: str = most_common[0]
        num: int = most_common[1]
        if num < max_num:
            break
        max_num = num
        winner.append(label)
    if len(winner) > 1:
        return majority_vote(labels[:-1])
    return winner[0]

assert majority_vote(['a', 'b', 'b', 'c']) == 'b'
assert majority_vote(['a', 'b', 'b', 'a']) == 'b'
assert majority_vote(['a', 'a', 'b', 'b', 'c']) == 'a'

Тесты показывают, что нашаmajority_voteФункция способна надежно обрабатывать вышеуказанные крайние случаи (пограничные случаи).

Алгоритм K-NN

Теперь, когда мы исследовали и написали обе функции, пришло время их объединить. Функция knn, которую мы собираемся реализовать, принимает в качестве входных данных список размеченных данных, новую метрику (точки данных, которые мы хотим классифицировать) и параметр k. Параметр k определяет: после прохожденияmajority_voteСколько соседей мы хотим учитывать, когда функция голосует за новую метку.

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

Преобразование описанных шагов в код дает следующую функцию knn:

def knn(labeled_data: List[LabeledData], new_measurement, k: int = 5) -> Prediction:
    class Distance(NamedTuple):
        label: str
        distance: float
    distances: List[Distance] = [Distance(data.label, distance(new_measurement, data.measurements))
                                         for data in labeled_data]
    distances = sorted(distances, key=attrgetter('distance'))
    labels = [distance.label for distance in distances][:k]
    label: str = majority_vote(labels)
    return Prediction(label, new_measurement)

Вот и все. Это алгоритм k-ближайших соседей, реализованный с нуля!

Классификация ирисов

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

Набор данных состоит из 50 образцов трех разных ирисов:

Iris Setosa
Iris Virginica
Iris Versicolor

Для каждого образца были собраны 4 различных измерения: ширина и длина чашелистика и ширина и длина лепестка.

Ниже приведен пример строки из набора данных, где первые 4 числа — это длина чашелистика, ширина чашелистика, длина лепестка, ширина лепестка, а последняя строка представляет метки для этих измерений.

6.9,3.1,5.1,2.3,Iris-virginica

Лучшим способом изучения этих данных является визуализация. К сожалению, трудно построить и проверить данные 4D. Однако мы можем выбрать две функции (например, длину лепестка и ширину лепестка) и нарисовать двухмерную диаграмму рассеяния.

fig = px.scatter(x=xs, y=ys, color=text, hover_name=text, labels={'x': 'Petal Length', 'y': 'Petal Width'})
fig.show()

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

Теперь предположим, что у нас есть новая немаркированная точка данных:

new_measurement: List[float] = [7, 3, 4.8, 1.5]

Добавление этой точки данных к существующей диаграмме рассеивания приводит к следующему:

fig = px.scatter(x=xs, y=ys, color=text, hover_name=text, labels={'x': 'Petal Length', 'y': 'Petal Width'})
fig.add_annotation(
    go.layout.Annotation(
            x=new_measurement[petal_length_idx],
            y=new_measurement[petal_width_idx],
            text="The measurement we want to classify")
)
fig.update_annotations(dict(
            xref="x",
            yref="y",
            showarrow=True,
            arrowhead=7,
            ax=0,
            ay=-40,
            borderwidth=2,
            borderpad=4,
            bgcolor="#c3c3c3"
))
fig.show()

Даже если бы мы просто отображали длину и ширину лепестков в 2D, кажется вероятным, что новые измерения могли быть получены от Iris Variegata.

Получим четкий ответ с помощью функции knn:

knn(labeled_data, new_measurement, 5)

Конечно же, мы получили результаты, показывающие, что мы имеем дело с «хроматической радужкой»:

Prediction(label='Iris-versicolor', measurements=[7, 3, 4.8, 1.5])

в заключении

Алгоритм классификации k-ближайших соседей — это очень мощный алгоритм классификации, который может маркировать данные отсутствующими метками на основе данных с существующими метками. Основная идея k-NN состоит в том, чтобы использовать K ближайших соседей новой точки данных, «подлежащей классификации», чтобы «проголосовать» за ее правильную метку.

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

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

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

Оригинальная ссылка:Philipp Moons.com/can-nearest-you…

Найдите общедоступный номер технических вопросов и ответов: класс Лао Ци

Ответ в публичном аккаунте:Лао Ципросмотреть все статьи, книги, курсы.

Если вы думаете, что это выглядит хорошо, пожалуйста, поставьте лайк и перешлите его