Машинное обучение

Даны точки на координатной плоскости:

A(1, 1), B(2, 1), C(1, 2), D(8, 8), E(9, 8), F(8, 9)

Центры кластеров:
C1(1.5, 1.5) и C2(8.5, 8.5)

К какому кластеру относится точка G(5, 5)?

1. Кластер 1 (C1)
2. Кластер 2 (C2)
3. На границе кластеров (равные расстояния)
4. Не относится ни к одному кластеру

Какое расстояние чаще всего используется в k-means?

1. Расстояние на карте города
2. Евклидово расстояние
3. Время в пути
4. Количество шагов

В чём главный недостаток алгоритма k-means?

1. Слишком быстро работает
2. Результат зависит от начальной инициализации центров
3. Не может работать с числовыми данными
4. Всегда создаёт ровно 10 кластеров

Как выбрать оптимальное количество кластеров k?

1. Всегда использовать k=2
2. k должно быть равно количеству точек
3. Методом локтя (Elbow method) или другими эвристиками
4. Случайным образом

Сколько раз может измениться положение центра кластера в k-means?

1. Ровно один раз
2. Ровно k раз (где k — количество кластеров)
3. От 0 до бесконечности (зависит от данных)
4. Центр никогда не меняется после инициализации

Что такое центроид (центр кластера) в алгоритме k-means?

1) Самая первая точка в кластере
2) Точка со средними координатами всех точек кластера
3) Точка, которая находится дальше всего от других кластеров
4) Случайная точка из кластера

Алгоритм K-Means — это итеративный алгоритм кластеризации, который разбивает множество точек на K кластеров. Алгоритм работает следующим образом:

1. Инициализация: задаются начальные координаты K центров кластеров
2. Назначение: каждая точка относится к кластеру с ближайшим центром (по евклидову расстоянию)
3. Пересчёт: центр каждого кластера пересчитывается как среднее арифметическое координат всех точек, принадлежащих этому кластеру
4. Проверка сходимости: если центры не изменились — алгоритм завершается, иначе переход к шагу 2

Евклидово расстояние между точками \((x_1, y_1)\) и \((x_2, y_2)\)вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Реализуйте алгоритм K-Means и выведите результат его работы.

Формат входных данных

- Первая строка содержит два целых числа n и k (1 <= n <= 1000, 1 <= k <= 10, k <= n) — количество точек и количество кластеров.
- Следующие n строк содержат по два вещественных числа x_i и y_i (-10⁶ <= x_i, y_i <= 10⁶) — координаты точек.
- Следующие k строк содержат по два вещественных числа cx_j и cy_j (-10⁶ <= cx_j, cy_j <= 10⁶) — начальные координаты центров кластеров.


Формат выходных данных

- Первая строка должна содержать одно целое число — количество итераций, выполненных до сходимости.
- Следующие k строк должны содержать по два вещественных числа — финальные координаты центров кластеров (в том же порядке, что и во входных данных). Координаты выводить с точностью до 2 знаков после запятой.
- Следующие n строк должны содержать по одному целому числу — номер кластера для каждой точки (нумерация с 0, в том же порядке, что и точки во входных данных).
 

Примечания

- Сходимость достигается, когда координаты всех центров не изменяются между итерациями (с точностью до вычислительной погрешности 1e-9)
- При сравнении расстояний, если точка равноудалена от нескольких центров, она относится к кластеру с меньшим номером
- Если кластер оказался пустым (ни одна точка не была к нему отнесена), его центр остаётся на прежнем месте
- Гарантируется, что алгоритм сойдётся не более чем за 100 итераций

Напишите программу, которая пересчитывает координаты центров кластеров.

Формат входных данных:

Первая строка: n k — количество точек и кластеров
Следующие n строк: x y c — координаты точки и номер её кластера (числа x, y - вещественные, c - целое число)
 

Формат выходных данных:

k строк: новые координаты центров (округлённые до 2 знаков)

Дан набор точек и k центров кластеров. Для каждой точки определите номер ближайшего центра (нумерация с 0). Расстояние между точками считается евклидовым. Если точка имеет одинаковое минимальное расстояние для двух и более кластеров, то ее необходимо определить к кластеру с наименьшим номером.

Формат входных данных:
Первая строка: n — количество точек (1 ≤ n ≤ 1000). Следующие n строк: x_i y_i — координаты i-й точки (целые числа, |x_i|, |y_i| ≤ 10000) Следующая строка: k — количество центров (1 ≤ k ≤ 10) Следующие k строк: cx_i cy_i — координаты j-го центра (целые числа, |cx_i|, |cy_i| ≤ 10000)

Формат выходных данных:
Одна строка с n числами — номера ближайших центров для каждой точки (0 ≤ номер < k)

Вычислите среднее арифметическое всех порогов (threshold) во внутренних узлах дерева.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Одно число — среднее значение порогов с точностью до 4 знаков после запятой.

Дано дерево решений и вектор признаков объекта. Определите, какой класс предскажет дерево.

Правило обхода

Если x[feature_index] <= threshold, идём в left_child
Иначе идём в right_child
Когда достигли листа, возвращаем его class


Формат входных данных
Первая строка: JSON с деревом. Вторая строка: признаки объекта через пробел.

Формат выходных данных
Одно число — предсказанный класс.

После Великой паники директор понял: старая система слишком сложная и ошибается. Он собрал данные за целую неделю (не только тот понедельник):

№	Странные слова?	Избегает общения?	Пришёл до 9:00?	Оказался нечистью?
1	Да	Да	Да	✅ Да
2	Да	Да	Нет	✅ Да
3	Да	Нет	Да	❌ Нет
4	Да	Нет	Нет	❌ Нет
5	Нет	Да	Да	❌ Нет
6	Нет	Да	Нет	✅ Да
7	Нет	Нет	Да	❌ Нет
8	Нет	Нет	Нет	❌ Нет

Всего: 3 нечисти, 5 людей

---

Директор заметил: «Бледное лицо» больше не работает — зимой все бледные! Нужны новые признаки.

Ты получил задачу: Построй дерево глубины 2 и предскажи для новенького.
 

Новенький — Гриша:

• Странные слова: ДА (переехал из Германии, вставляет немецкие слова)
• Избегает общения: ДА (стесняется, ещё никого не знает)
• Пришёл до 9:00: ДА (родители привезли пораньше)

Что предскажет оптимальное дерево глубины 2?

• 1. Человек
• 2. Нечисть
• 3. 50/50 — дерево не может определить
• 4. Нужен третий уровень дерева

После карантина школа Ларево установила систему для определения зомби:

              [Бледное лицо?]
               /           \
             Да            Нет
             /               \
      [Странная походка?]   НЕ ЗОМБИ
         /          \
       Да           Нет
       /              \
[Издаёт стоны?]    НЕ ЗОМБИ
    /       \
  Да        Нет
  /           \
ЗОМБИ      НЕ ЗОМБИ

Понедельник, 8:00. Костя всю ночь писал код. Приходит в школу:

• Лицо бледное (не видел солнце 3 дня)
• Походка странная (врезался в две стены)
• Издаёт стоны («уууу....стены...кофеее....коодд»)

Система сработала и вызвала охрану! Костя хочет доказать, что он не зомби. Какой ОДИН признак ему проще всего изменить прямо сейчас, чтобы система изменила решение?

• 1. Бледное лицо — умыться холодной водой
• 2. Странная походка — выпить кофе и взбодриться
• 3. Издаёт стоны — просто замолчать
• 4. Любой из трёх сработает одинаково

Дерево отбора на олимпиаду по программированию:

              [Средний балл > 4.5?]
                /              \
              Да               Нет
              /                  \
     [Победил в прошлом году?]  НЕ ПУСТЯТ
          /           \
        Да            Нет
        /               \
    ПУСТЯТ        [Рекомендация учителя?]
                      /            \
                    Да             Нет
                    /                \
                ПУСТЯТ          НЕ ПУСТЯТ

Костя Багов: средний балл 4.2, но он трижды побеждал на олимпиадах, написал школьный сайт и учитель информатики его боготворит.

Пустят на олимпиаду?

• 1. Пустят — он же гений!
• 2. Не пустят
• 3. Пустят вне конкурса
• 4. Создаст свою олимпиаду

Нейросеть школы Ларево предсказывает, проспит ли Тимоха урок:

        [Урок до 10:00?]
         /           \
       Да            Нет
       /               \
   ПРОСПИТ         НЕ ПРОСПИТ

Сейчас урок информатики, начало в 8:30. Что предскажет модель?

• 1. Проспит
• 2. Не проспит
• 3. Зависит от предмета
• 4. Нужно проверить, выпил ли он кофе

Добро пожаловать в школу Ларево — место, где ученики строят ML-модели, чтобы предсказать, кого вызовут к доске, а учителя используют нейросети для распознавания тех, кто не сделал домашку.

---

🌟 ГЕРОИ ШКОЛЫ ЛАРЕВО:

• Тимофей «Тимоха» Лапшин — засыпает на любом уроке за 3 минуты
• Алиса Кактусова — рисует мемы в тетради вместо конспектов
• Данил «Данон» Йогуртов — всегда голодный, ест на уроках
• Вика Вайфайная — не может жить без телефона больше 5 минут
• Костя Багов — гений программирования, но забывает надеть разные носки
• Маша Мемасова — знает все тренды, но не знает, кто такой Пушкин

Готовы к викторине?
1. Да
2. Нет



---
Все имена и события выдуманы. Любые совпадения случайны (честно)
За ответ на этот вопрос тоже дают балл :)

ИИ-система школы Ларево научилась распознавать котов на фото (для важных научных целей):

            [Есть усы?]
            /         \
          Да          Нет
          /             \
    [Говорит «мяу»?]   НЕ КОТ
       /        \
     Да         Нет
     /            \
   КОТ        [Ловит мышей?]
                /        \
              Да         Нет
              /            \
            КОТ        НЕ КОТ

Ситуация: На перемене Вика нарисовала Тимохе усы маркером пока он спал. Тимоха проснулся, увидел себя в камере телефона и от неожиданности издал звук «мяяяу?!». В этот момент школьная система распознавания сфоткала его для пропуска.

Что выдаст система?

• 1. Кот 🐱
• 2. Не кот 👦
• 3. Ошибка распознавания
• 4. Тимофей Лапшин, 10-Б класс

Данные о том, выйдет ли человек на пробежку:

№	Дождь?	Температура	Выходной?	Бегал?
1	Нет	Тепло	Да	✅
2	Нет	Тепло	Нет	✅
3	Нет	Холодно	Да	✅
4	Нет	Холодно	Нет	❌
5	Да	Тепло	Да	❌
6	Да	Тепло	Нет	❌
7	Да	Холодно	Да	❌
8	Да	Холодно	Нет	❌

Новый человек — Саша: Дождь=Нет, Температура=Холодно, Выходной=Нет.

Что предскажет дерево с оптимальным корнем?
 

1. Побежит (100% уверенность)
2. Не побежит (100% уверенность)
3. Побежит (но есть неопределённость)
4. Не побежит (но есть неопределённость)

Данные: кто пойдёт на школьную дискотеку?

№	Есть пара?	Друзья идут?	Домашка сделана?	Пошёл?
1	Да	Да	Да	✅
2	Да	Да	Нет	✅
3	Да	Нет	Да	✅
4	Да	Нет	Нет	✅
5	Нет	Да	Да	✅
6	Нет	Да	Нет	✅
7	Нет	Нет	Да	❌
8	Нет	Нет	Нет	❌

Какой признак лучше поставить в корень?

• 1. Есть пара
• 2. Друзья идут
• 3. Домашка сделана
• 4. Все одинаково хороши

В школе Ларево пятничная мафия — священная традиция. Дерево предсказывает участие:

              [Пятница?]
              /        \
            Да          Нет
            /             \
     [Домашки много?]   НЕ ПРИДЁТ
        /        \
      Да         Нет
      /            \
[Мафия или домашка?] ПРИДЁТ
    /        \
 Мафия     Домашка
   /          \
ПРИДЁТ    НЕ ПРИДЁТ

Пять учеников в пятницу:

Ученик	Много домашки?	Выбор
Тимоха	Да	Мафия
Алиса	Нет	—
Данон	Да	Домашка
Вика	Да	Мафия
Костя	Нет	—

Сколько придут на мафию?

• 1. 2
• 2. 3
• 3. 4
• 4. 5