Статистическое обучение в Джулии. Часть 2

Главы

И вот мы снова со 2ⁿᵈ частью серии. В первом посте мы говорили о линейной регрессии и о том, как ее реализовать с помощью алгоритма градиентного спуска. Для текущего поста я решил реализовать алгоритм K-ближайших соседей (KNN). Причина этого в том, что KNN легко и быстро реализовать, и это менее очевидный выбор по сравнению с другими. Логистическая регрессия — это было бы слишком похоже на предыдущий пост. С этого момента мы сосредоточимся только на проблемах классификации. Более того, идея состоит в том, чтобы поднять планку для каждого поста, поскольку это касается качества кода и сложности алгоритмов ML.

Спойлер: часть 3 будет посвящена машине опорных векторов.

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

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

По сути, алгоритм KNN при прогнозировании класса новой выборки x₀ ищет K ближайших выборок в наборе данных и присваивает x₀ классу с наибольшей вероятностью среди вышеупомянутой окрестности.

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

Реализация 🔨

Во-первых, убедитесь, что у вас установлена Julia. Для этой демонстрации я использую последнюю версию, то есть Julia 1.8.3. Затем откройте предпочитаемую IDE и установите необходимые пакеты.

using Pkg;
Pkg.add(["CSV", "PlotlyJS", "DataFrames", "Printf", "Random"])
using CSV, PlotlyJS, DataFrames, Printf, Random

CSV и DataFrames — две библиотеки для работы с табличными данными. PlotlyJS — известная библиотека для интерактивной визуализации данных. Printf — это библиотека для форматирования печати строк, и, наконец, Random предлагает вспомогательную функцию для перемешивания нашего набора данных.

Набор данных

Для этой демонстрации мы используем набор данных По умолчанию. Вы можете найти его, загрузив файл Все файлы .csv, как .zip на официальном сайте книги Введение в статистическое обучение».

Давайте посмотрим на данные:

data = DataFrame(CSV.File("data/ALL+CSV+FILES+-+2nd+Edition+-+corrected/ALL CSV FILES - 2nd Edition/Default.csv"))
first(data, 10)

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

Предварительная обработка

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

function splitTrainTest(data::DataFrame, ratio::Float64)

    # Get the number of rows
    datasetSize = size(data, 1)

    # Get the index where to split the data and round it
    trainIdx = floor(Int, datasetSize * ratio)

    # Split the data
    dataTrain = data[1:trainIdx, :]
    dataTest = data[trainIdx:datasetSize, :]
    
    return dataTrain, dataTest 
end

Алгоритм 🤖

Теперь мы можем начать определять некоторые функции для разработки нашего алгоритма KNN.

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

mutable struct KNN
    x::DataFrame
    y::DataFrame
    neighbors::Int
end

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

где t — наша целевая точка, а s — исходная точка. Вот функция для вычисления евклидова расстояния:

function euclideanDistance(source::Vector, target::Vector)

    # Compute the element-wise subtraction between point columns,
    # Raise to the power of 2 every element and then sum all the rows
    sqrtDist = sum((target .- source).^2, dims=1)[1]

    # Compute the square root of our distances
    dist = sqrt(sqrtDist)
    
    return dist
end

Хороший. Сейчас самое время реализовать функцию для вычисления расстояния между каждой парой точек. Эта функция будет вызывать вышеупомянутую функцию euclideanDistance.

function computeDistance(xTrain::DataFrame, xTest::DataFrame)

    # Pre-allocate an array of size n_te x n_tr,
    # where n_te is the number of rows in the test set and
    # n_tr the same for the training set
    distances = Array{Float64}(undef, size(xTest, 1), size(xTrain, 1))

    # Convert train and test set to Matrix
    xTrain = Matrix(xTrain)
    xTest = Matrix(xTest)

    # Loop every row in the test set
    for sTe in 1:size(xTest, 1)
        # Loop every row in the training set 
        for sTr in 1:size(xTrain, 1)
            # Compute the pairwise distance
            distances[sTe, sTr] = euclideanDistance(xTrain[sTr, :], xTest[sTe, :])
        end
    end
    
    return distances
end

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

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

function predict(classifier::KNN, xTest::DataFrame)

    # Get the distances between every pair of points
    distances = computeDistance(classifier.x, xTest)

    # Pre-allocate an array that will store the model predictions
    yPred = Array{String3}(undef, size(xTest, 1))

    # Loop all the distances
    for i in 1:size(distances, 1)
        
        # For every point, order the distances in descending order and 
        # take the K closest points 
        neighboursIdx = sortperm(distances[i, :])[1:classifier.neighbour]

        # Get a Matrix with the label of the K nearest neighbors
        neighboursLabels = Matrix(knn.y[neighboursIdx, :])

        # Count the appearance of every label
        labelsCount = [count(==(element),neighboursLabels) for element in unique(neighboursLabels)]

        # Get the index of the most frequent label
        majorityClass = argmax(labelsCount)

        # Assign that label to the new sample
        yPred[i] = unique(neighboursLabels)[majorityClass]
    end
    
    return yPred
end

Почти готово. Нам просто нужно определить функцию для оценки производительности нашего классификатора KNN.

function evaluateClassifier(yTrue::DataFrame, yPred::Vector{String3})

    # Encode the true labels with integers (1 if "Yes", 0 otherwise)
    correctPredictions = Matrix(ifelse.((xte[:, ["default"]] .== yPred) .== true, 1, 0))

    # Compute the accuracy and print the result
    accuracy = sum(correctPredictions, dims=1) / length(correctPredictions) * 100
    @printf("Classifier Accuracy: %0.2f%%", accuracy[1])
end

Потрясающий! Теперь мы готовы собрать все это вместе.

Собери все вместе 🤝

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

# Crate random number generator
rng = MersenneTwister(1234);

# Shuffle data
shuffle!(rng, data)

# Encode student variable
data."student" = ifelse.(data."student" .== "No", 0, 1)

# Split data to 70% training and 30% test
xTrain, xTest = splitTrainTest(data, 0.7)


# Plot the training set
layout = Layout(width=1000, height=1000,

    scene = attr(

        xaxis_title="Student",
        yaxis_title="Balance",
        zaxis_title="Income")
)
plot(xTrain, x=:student, y=:balance, z=:income, color=:default, type="scatter3d", mode="markers", layout)

Вот результат:

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

# Drop the ground truth label from training data
yTrain = xTrain[:, ["default"]]
xTrain = xTrain[:, ["student", "balance", "income"]]

# Create KNN classifier with K=3
knn = KNN(xTrain, yTrain, 3)

# Make predictions
yPred = predict(knn, xTest[:, ["student", "balance", "income"]])

# Evaluate the classifier
evaluateClassifier(xTest[:, ["default"]], yPred)

Olè!

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

Надеюсь, вам понравилось, увидимся в третьей части!

Статистическое обучение в Джулии. Часть 2 — K-ближайшие соседи