Линейная регрессия: прямая, разделяющая плоскость на точки 2 классов / forpes.ru

Главная
Линейная регрессия: прямая, разделяющая плоскость на точки 2 классов

Линейная регрессия: прямая, разделяющая плоскость на точки 2 классов +3

17.07.2023 12:44

KindCat 4 1200 Источник

В этой статье мы напишем программу, которая будет проводить прямую так, чтобы красные точки были в одной полуплоскости, а зеленые — в другой. Мы будем использовать Python и библиотеку tkinter.

Как мы будем реализовывать это?

Пусть искомая прямая задается уравнением . Тогда нам нужно просто найти подходящие . В одной полуплоскости будут лежать точки положительного класса (для них предсказание модели, о котором мы поговорим позднее, будет равно , а для точек на прямой и в другой полуплоскости — )

Введем следующее обозначение:.

Тогда если , то предсказание модели — . Иначе — .

Введем функцию $f(x)=\begin{equation*}\begin{cases}1, x > 0; \\ -1, x \le 0 \end{cases}\end{equation*}$ , которая возвращает предсказанный класс по предсказанной характеристике .

Следующий раздел о том, как найти .

Как происходит обучение модели

Возьмем некоторые начальные значения. Например, $w_1=w_2=1,\ b=0$ .

Пройдемся по каждому объекту. У объекта есть параметры — координаты и класс, к которому он относится.
Сделаем предсказание для этого объекта.
Если , то модель сделала правильное предсказание, ничего не делаем. Смотрим следующий объект.
Если $f(p(x_i, y_i)) \ne p_i$ , то пересчитаем веса (включая ) по следующей формуле:

$w_j'=w_j+\lambda n_j (y_i - y_i')$ , где:
1. $\lambda$ — константа скорости обучения (на сколько сильно каждый объект влияет на параметры)
2. — значение фактора (или для параметра)
3. — предсказанное значение
После того, как прошлись по всем объектам, если мы сделали меньше максимального количества итераций и произошло хоть одно изменение весов, проходимся заново по всем и пересчитываем.

Подключение библиотек и параметры

import tkinter as tk 

WND_SIZE = 700   # Размер окна 
POINT_SIZE = 5   # Радиус точек
TRAIN_EVERY_TIME = False  # Обучать ли модель заново при добавлении новой точки
                          # (или ждать нажатия Enter)

MAX_STUDY = 1000 # Максимальное количество итераций обучения модели
LAMBDA = 0.1     # Влияние точки на параметры модели

# Создаем окно размера WND_SIZE x WND_SIZE
window = tk.Tk()
window.geometry(f"{WND_SIZE}x{WND_SIZE}")

# Создаем холст для рисования на все окно
cs = tk.Canvas(window, width=WND_SIZE, height=WND_SIZE)
cs.pack()

Параметр MAX_STUDY отвечает за максимальное возможное количество итераций обучения модели.

Параметр LAMBDA отвечает за то, насколько будут меняться параметры модели, если объект был классифицирован неправильно.

Переменные для обучения модели

type_ = [] # Точки

# Веса:
w1 = 1
w2 = 1
b = 0

Точка будет задаваться массивом: первый элемент — класс (1 или -1), второй и третий элементы — координаты.

Ввод точек

Обратите внимание, что точки мы будем хранить в системе координат, отличающейся от той, которая используется в tkinter'е:

Слева — используемая нами система координат, справа — используемая tkinter'ом

Поэтому мы будем вычитать $\frac{\operatorname{WND\_SIZE}}{2}$ при сохранении точек и прибавлять это значение при выводе точек и прямой.

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

Для этого создадим 4 функции: при нажатии ЛКМ, при нажатии ПКМ, при нажатии Escape и при нажатии Enter (Спасибо @IvaYan за идею вынести функционал type1_add и type2_add в отдельную функцию и о добавлении возможности обучать модель один раз после добавления всех точек)

def add_point(event, class_):
    # Считываем координаты точки нажатия (переводя их в нужную систему координат)
    x = event.x - WND_SIZE//2 
    y = event.y - WND_SIZE//2
    # Добавляем точку класса class_
    # (напоминаю, что первый элемент массива - класс объекта)
    type_.append([class_, x, y])
    # Обучаем модель заново (реализация ниже в статье)
    if TRAIN_EVERY_TIME:
        train()
    # Рисуем точки и прямую заново (реализация ниже в статье) 
    # Параметр функции redraw отвечает за то, будет ли нарисована прямая. Это зависит
    # от TRAIN_EVERY_TIME
    redraw(TRAIN_EVERY_TIME)

    
def type1_add(event):
    add_point(event, -1)


def type2_add(event):
    add_point(event, 1)


def clear(_e):
    global type_, w1, w2, b
    type_ = [] # Удаляем все точки
    # Возвращаем параметрам начальные значения
    w1 = 1 
    w2 = 1
    b = 0
    redraw() # Рисуем заново


def train_and_draw(_e):
    train()
    redraw()

Теперь укажем Tkinter'у, когда эти функции надо вызывать:

cs.bind_all("<Button-1>", type1_add) # Если нажата ЛКМ - вызвать type1_add
cs.bind_all("<Button-3>", type2_add) # Если нажата ПКМ - вызвать type2_add
cs.bind_all("<Escape>", clear) # Если нажата клавиша Escape - вызвать clear
cs.bind_all("<Return>", train_and_draw) # Если нажата клавиша Enter - обучить и нарисовать

Обучение модели. Функция train()

Реализуем обучение, как описано выше в статье:

def f(x):
    return 1 if x > 0 else -1

def train():
    global w1, w2, b
    for _ in range(MAX_STUDY): # Делаем MAX_STUDY итераций обучения
        another_iter = False # Флаг, показывающий, были ли изменены веса
        for i in type_: # Для каждой точки:
            predicted = f(w1 * i[1] + w2 * i[2] + b) # Вычислим предсказанное значение
            if predicted != i[0]: # Если предсказанное значение не совпадает с реальным:
                another_iter = True # Нам нужна еще одна итерация
                # Пересчет весов:
                w1 += LAMBDA * (i[0] - predicted) * i[1]
                w2 += LAMBDA * (i[0] - predicted) * i[2]
                b += LAMBDA * (i[0] - predicted)
        if not another_iter: # Если веса не были изменены, модель идеальна.
            return # Завершаем обучение

Показ результата обучения на экране. Функция redraw()

Реализуем функцию, показывающую точки и прямую на экране.

def redraw(with_line=True):
    cs.delete("all")  # Очищаем холст
    for i in type_:  # Для каждой точки рисуем круг радиусом POINT_SIZE
        cs.create_oval(i[1] - POINT_SIZE + WND_SIZE // 2, i[2] - POINT_SIZE + WND_SIZE // 2,
                       i[1] + POINT_SIZE + WND_SIZE // 2, i[2] + POINT_SIZE + WND_SIZE // 2,
                       fill=('red' if i[0] == 1 else 'green'))
    if with_line: # Если нужно рисовать линию, ...
        if w1 == 0:
            cs.create_line(0, -b // w2 + WND_SIZE // 2, WND_SIZE, -b // w2 + WND_SIZE // 2)
        else:
            cs.create_line((-b + w2 * (WND_SIZE // 2)) // w1 + WND_SIZE // 2, 0,
                           (-b - w2 * (WND_SIZE // 2)) // w1 + WND_SIZE // 2, WND_SIZE)

Строки с 8 по 12 разберем подробнее:

Если , то уравнение, график которого нам нужно построить, имеет вид , т.е. $y = -\frac{b}{w_2}$ для любого .

Поэтому проводим линию от точки $\left(-\frac{\operatorname{WND\_SIZE}}{2}, -\frac{b}{w_2}\right)$ до точки $\left(\frac{\operatorname{WND\_SIZE}}{2}, -\frac{b}{w_2}\right)$ . (Не забываем про перевод координат!)

Если $w_1\ne0$ , то $x=\frac{-b-w_2y}{w_1}$ . Подставляя в эту формулу $y = \pm\frac{\operatorname{WND\_SIZE}}{2}$ , получим что:

$x_{y=-\operatorname{WND\_SIZE}/2}=\frac{-b+w_2*\frac{\operatorname{WND\_SIZE}}{2}}{w_1}$ , $x_{y=\operatorname{WND\_SIZE}/2}=\frac{-b-w_2*\frac{\operatorname{WND\_SIZE}}{2}}{w_1}$

(выразили при 2 разных ). Такую линию и рисуем.

Конец программы. Открытие окна

В конце программы нарисуем на холсте нашу прямую и запустим главный цикл окна.

redraw(TRAIN_EVERY_TIME)
tk.mainloop()

Исходный код

import tkinter as tk

WND_SIZE = 700  # Размер окна
POINT_SIZE = 5  # Радиус точек
TRAIN_EVERY_TIME = False  # Обучать ли модель заново при добавлении точки

MAX_STUDY = 1000  # Максимальное количество итераций обучения модели
LAMBDA = 0.1  # Влияние точки на параметры модели

# Создаем окно размера WND_SIZE x WND_SIZE
window = tk.Tk()
window.geometry(f"{WND_SIZE}x{WND_SIZE}")

# Создаем холст для рисования на все окно
cs = tk.Canvas(window, width=WND_SIZE, height=WND_SIZE)
cs.pack()

type_ = []  # Точки

# Веса:
w1 = 1
w2 = 1
b = 0


def f(x):
    return 1 if x > 0 else -1


def train():
    global w1, w2, b
    for _ in range(MAX_STUDY):  # Делаем MAX_STUDY итераций обучения
        another_iter = False  # Флаг, показывающий, были ли изменены веса
        for i in type_:  # Для каждой точки:
            predicted = f(w1 * i[1] + w2 * i[2] + b)  # Вычислим предсказанное значение
            if predicted != i[0]:  # Если предсказанное значение не совпадает с реальным:
                another_iter = True  # Нам нужна еще одна итерация
                # Пересчет весов:
                w1 += LAMBDA * (i[0] - predicted) * i[1]
                w2 += LAMBDA * (i[0] - predicted) * i[2]
                b += LAMBDA * (i[0] - predicted)
        if not another_iter:  # Если веса не были изменены, модель идеальна.
            return  # Завершаем обучение


def redraw(with_line=True):
    cs.delete("all")  # Очищаем холст
    for i in type_:  # Для каждой точки рисуем круг радиусом POINT_SIZE
        cs.create_oval(i[1] - POINT_SIZE + WND_SIZE // 2, i[2] - POINT_SIZE + WND_SIZE // 2,
                       i[1] + POINT_SIZE + WND_SIZE // 2, i[2] + POINT_SIZE + WND_SIZE // 2,
                       fill=('red' if i[0] == 1 else 'green'))
    if with_line:
        if w1 == 0:
            cs.create_line(0, -b // w2 + WND_SIZE // 2, WND_SIZE, -b // w2 + WND_SIZE // 2)
        else:
            cs.create_line((-b + w2 * (WND_SIZE // 2)) // w1 + WND_SIZE // 2, 0,
                           (-b - w2 * (WND_SIZE // 2)) // w1 + WND_SIZE // 2, WND_SIZE)


def add_point(event, class_):
    # Считываем координаты точки нажатия (переводя их в нужную систему координат)
    x = event.x - WND_SIZE // 2
    y = event.y - WND_SIZE // 2
    # Добавляем точку класса class_
    # (напоминаю, что первый элемент массива - класс объекта)
    type_.append([class_, x, y])
    # Обучаем модель заново (реализация ниже в статье)
    if TRAIN_EVERY_TIME:
        train()
    # Рисуем точки и прямую заново (реализация ниже в статье)
    redraw(TRAIN_EVERY_TIME)


def type1_add(event):
    add_point(event, -1)


def type2_add(event):
    add_point(event, 1)


def clear(_e):
    global type_, w1, w2, b
    type_ = []  # Удаляем все точки
    # Возвращаем параметрам начальные значения
    w1 = 1
    w2 = 1
    b = 0
    redraw(False)  # Рисуем заново


def train_and_draw(_e):
    train()
    redraw()


cs.bind_all("<Button-1>", type1_add)  # Если нажата ЛКМ - вызвать type1_add
cs.bind_all("<Button-3>", type2_add)  # Если нажата ПКМ - вызвать type2_add
cs.bind_all("<Escape>", clear)  # Если нажата клавиша Escape - вызвать clear
cs.bind_all("<Return>", train_and_draw)  # Если нажата клавиша Enter - обучить и нарисовать

redraw(TRAIN_EVERY_TIME)
tk.mainloop()

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

P.S. Я изучаю машинное обучение на Сириус.Курсах, эта статья — описание того, что я попытался сделать, используя то, что узнал.

Комментарии (4)

IvaYan
17.07.2023 13:31
#25760806
+3
Методы type1_add и type2_add отличаются только тем, в какой класс добавляется точка. Лучше выделить общее в отдельный метод и передавать номер класса через аргументы.

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

Обычно процесс обучения модели называют fit или train, а не study.

Ну и наконец, зачем вы используете линейную регрессию для задачи бинарной классификации? Чем не устроила логистическая регрессия, которая как раз для бинарной классификации и предназначена?

Странно выглядит сам процесс обучения. Почему бы не использовать градиентный спуск? Зачем корректировать веса для каждой точки отдельно?
1. KindCat Автор
  17.07.2023 13:31
  #25761098
  Спасибо. Теперь есть параметр, показывающий, надо ли обучать модель каждый раз, restudy я переименовал в train, добавил функцию add_point, которую вызывают type1_add и type2_add.

Vindicar
17.07.2023 13:31
#25760862
+1
Вообще для такой задачи - бинарная классификация линейно-разделимых данных - есть метод опорных векторов. Он как раз интересен тем, что находит "ближайшие" точки двух классов и строит прямую именно по ним, так как именно эти точки наиболее сложны для различения.
1. mikko_kukkanen
  17.07.2023 13:31
  #25765730
  Да, только не очень понятно, что у того самого метода опорных векторов "под капотом". По-моему, такая задача решается чисто геометрически: строятся выпуклые линейные оболочки двух разделяемых множеств. Если эти оболочки не пересекаются, то между ними существует полоса, опирающаяся на N+1 (или меньше) граничную точку при размерности пространства N. Соответственно, на 2-мерной плоскости существует 3 или меньше ( возможно, 2) "опорных векторов", задающих разделяющую полосу максимальной ширины.