Информатика

Как изменение параметра minPts влияет на форму k-distance графика и выбор εε?

1. При увеличении minPts k-расстояния уменьшаются, и локоть смещается к нулю
2. minPts влияет только на итоговые кластеры и никак не связан с k-distance графиком
3. При увеличении minPts k-расстояния, как правило, возрастают, и локоть смещается вправо и вверх
4. Изменение minPts вообще не рекомендуется, он всегда фиксирован

Как выбор параметра k (количество соседей для k-distance) связан с параметром minPts в DBSCAN?

1. Часто выбирают k=minPts или k=minPts−1
2. Обычно выбирают k=1, независимо от minPts
3. Связи между k и minPts нет, они подбираются совершенно независимо
4. k всегда должен быть намного больше minPts

Зачем сортировать k-расстояния по возрастанию перед построением k-distance графика?

1. Чтобы разнесённые во времени наблюдения шли подряд
2. Чтобы визуально выделить резкий переход от плотных областей к шуму
3. Чтобы получить симметричный график относительно середины
4. Чтобы можно было напрямую прочитать индексы кластеров

На k-distance графике по оси абсцисс отложены отсортированные объекты датасета. Что обычно показывается по оси ординат?

Выберите верный вариант ответа

1. Расстояние до ближайшего соседа k=1 для каждого объекта
2. Индекс объекта в исходном порядке выборки
3. Среднее расстояние от объекта до всех других объектов
4. Расстояние до k-го ближайшего соседа для каждого объекта

Реализуйте полный алгоритм DBSCAN. Напишите программу

 

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

n eps minPts : n - число точек (натуральное число не больше 100, eps - положительное вещественное число не больше 3, minPts - натуральное число не больше 5)

n строк: x y (координаты точек, вещественные числа, по модулю меньше 10**5 )

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

n строк: номер кластера для каждой точки:

• -1 для шума
• нумерация кластеров с 0

Дан набор точек. Напишите программу, которая считает количество соседей у заданной точки в радиусе eps

Формат входных данных
Первая строка: n eps — количество точек и радиус (n - натуральное, не превышает 100 , eps - вещественное)
Следующие n строк: x y — координаты точек (целые числа, по модулю не превышают 100)
Последняя строка: qx qy — точка запроса (целые числа, по модулю не превышают 100). 
Гарантируется, что заданная точка находится в заданном наборе точек.

Формат выходных данных
Одно число — количество соседей (не считая саму точку)

Дано: eps = 2, minPts = 3
Точки: A(1, 1),  B(2, 1),  C(3, 1),  D(10, 10)

Какой тип у точки D?

Выберите верный вариант ответа

1. Ядровая точка
2. Граничная точка
3. Шумовая точка
4. Невозможно определить

Посмотрите на эти данные:

Данные:

   ●●●●●●●●●

  ●●●●●●●●●●●

 ●●●●     ●●●●

●●●●        ●●●●

 ●●●        ●●●

  ●●        ●●

   ●        ●

(форма буквы "C")

Если применить k-means с k=2, какой результат наиболее вероятен?

Выберите верный вариант ответа:

1. K-means правильно найдёт кластер в форме "C"
2. K-means разделит "C" на левую и правую части
3. K-means не сможет работать с такими данными
4. K-means найдёт только один кластер

Реализуйте алгоритм k-means для одномерных данных (только координата x).

Для одномерных данных расстояние между точками вычисляется как модуль разности: |x₁ - x₂|

При равном расстоянии до нескольких центров точка присваивается кластеру с меньшим номером.

 

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

- Первая строка: два целых числа n и k (1 ≤ k ≤ n ≤ 1000) — количество точек и кластеров

- Вторая строка: n целых чисел через пробел — значения точек (−10⁶ ≤ xᵢ ≤ 10⁶)

- Третья строка: k вещественных чисел через пробел — начальные центры кластеров

 

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

- Первая строка: k вещественных чисел — финальные центры кластеров (округлённые до 1 знака после запятой)

- Вторая строка: n целых чисел — номер кластера (0-индексация) для каждой точки в порядке их появления во входных данных

Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек), лежащих внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит ровно одному кластеру. Центроид кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Расстояние между звёздами вычисляется по формуле Евклида: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Вам дан список координат звёзд и количество кластеров k. Известно, что все кластеры имеют размер \(H \times W\) и чётко разделены (расстояние между кластерами значительно больше их размера).

Необходимо:

1. Разделить звёзды на k кластеров

2. Найти центроид каждого кластера

3. Вычислить \(P_x\) — среднее арифметическое x-координат всех центроидов

4. Вычислить \(P_y\) — среднее арифметическое y-координат всех центроидов

5. Вывести результат в заданном формате

 

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

- Первая строка содержит два целых числа n и k (\(1 \le n \le 1000\), \(1 \le k \le 10\)) — количество звёзд и количество кластеров.

- Вторая строка содержит два вещественных числа H и W — размеры каждого кластера.

- Следующие n строк содержат по два вещественных числа \(x_i\)и \(y_i\) (\(-10^6 \le x_i, y_i \le 10^6\)) — координаты звёзд.

 

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

Выведите два целых числа через пробел:

- Целую часть от \(|P_x \times 10000|\)

- Целую часть от \(|P_y \times 10000|\)

где |x| обозначает абсолютное значение числа x.

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

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)

Даны два массива чисел. Найдите количество уникальных чисел, которые встречаются в обоих массивах (размер пересечения множеств).

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

В первой строке — число N (1 ≤ N ≤ 100000).

Во второй строке — N целых чисел первого массива (1 ≤ число ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000).

В четвёртой строке — M целых чисел второго массива.

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

Одно число — количество общих уникальных элементов.