{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "NUM_POINTS = 150\n", "np.random.seed(42)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# функция рисования графиков\n", "def plot_clouds(data, clusters=None, line=None):\n", " plt.figure(figsize=(8, 6)) # Размер графика\n", " if clusters is not None:\n", " plt.scatter(data[:, 0], data[:,1], c=clusters, cmap='Set1', alpha=0.6)\n", " else: \n", " plt.scatter(data[:, 0], data[:,1], alpha=0.6)\n", "\n", " if line is not None:\n", " plt.plot(line[:, 0], line[:, 1], 'k--', linewidth=2)\n", " plt.xlim(data[:,0].min()-1, data[:,0].max()+1)\n", " plt.ylim(data[:,1].min()-1, data[:,1].max()+1)\n", "\n", " plt.xlabel('Ось X')\n", " plt.ylabel('Ось Y')\n", " plt.grid(True)\n", " plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 📌 **Теоретическая основа: разделение кластеров** \n", "\n", "В задачах **кластеризации** мы пытаемся разделить данные на группы (**кластеры**) без заранее известных меток. Один из базовых способов нахождения границы между двумя кластерами – это **серединный перпендикуляр** между их центрами. \n", "\n", "### **1. Центр кластера (Центроид)** \n", "Для простых случаев, когда данные распределены вокруг некоторых точек, можно вычислить **центр кластера** как среднее арифметическое всех его точек: \n", "\n", "$$\n", "C = \\left( \\frac{1}{N} \\sum_{i=1}^{N} x_i, \\frac{1}{N} \\sum_{i=1}^{N} y_i \\right)\n", "$$\n", "\n", "где $N$ – количество точек в кластере, а $x_i, y_i$ – их координаты. \n", "\n", "Если у нас два кластера с центрами $C_1(x_1, y_1)$ и $C_2(x_2, y_2)$, то мы можем провести **линию, которая их разделяет**. \n", "\n", "--- \n", "\n", "### **2. Разделяющая линия** \n", "\n", "Разделяющая линия – это **серединный перпендикуляр** к отрезку, соединяющему центры кластеров. \n", "\n", "1. **Находим середину отрезка между центроидами**: \n", " $$\n", " M = \\left( \\frac{x_1 + x_2}{2}, \\frac{y_1 + y_2}{2} \\right)\n", " $$\n", " \n", "2. **Вычисляем угловой коэффициент (наклон) перпендикуляра**: \n", " - Прямая, соединяющая центры, имеет наклон: \n", " $$\n", " k_{\\text{осн}} = \\frac{y_2 - y_1}{x_2 - x_1}\n", " $$\n", " - Перпендикуляр к ней имеет наклон: \n", " $$\n", " k = -\\frac{1}{k_{\\text{осн}}}\n", " $$\n", " \n", "3. **Записываем уравнение прямой в виде**: \n", " $$\n", " y = kx + b\n", " $$\n", " Чтобы найти $b$, подставляем координаты точки $M$: \n", " $$\n", " b = y_M - k x_M\n", " $$\n", "\n", "Таким образом, прямая, разделяющая кластеры, описывается уравнением: \n", "\n", "$$\n", "y = -\\frac{1}{k_{\\text{осн}}} x + \\left( y_M + \\frac{x_M}{k_{\\text{осн}}} \\right)\n", "$$\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "center_1 = (0,0)\n", "center_2 = (1,3)\n", "\n", "cloud_1 = np.random.normal(center_1, 0.5, (NUM_POINTS, 2)) # Первое облако\n", "cloud_2 = np.random.normal(center_2, (0.3,0.5), (NUM_POINTS, 2)) # Второе облако\n", "\n", "data = np.vstack([cloud_1, cloud_2])\n", "clusters = np.vstack([np.zeros(NUM_POINTS), np.ones(NUM_POINTS)])\n", "\n", "plot_clouds(data)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "k = -1/3\n", "b = 5/3\n", "\n", "x_values = np.linspace(data[:,0].min()-1, data[:,0].max()+1, 100)\n", "y_values = k*x_values + b\n", "line = np.column_stack([x_values, y_values])\n", "\n", "plot_clouds(data, line=line)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Задания\n", "\n", "### 1. Напишите функцию, которая вычисляет линию, разделяющую два облака по координатам их центров. \n", "эта линия является серединным перпендикуляром к отрезку, соединяющему центры облаков" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def find_line(c1: tuple[float, float], c2: tuple[float, float],\n", " x_min: float, x_max: float, count: int=100) -> np.array:\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2. Проверьте работу вашей функции.\n", "Выведите график точек и полученной прямой. Совпадает ли он с графиком выше? " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3. Примените вашу функцию к наборам данных из файлов `1.npy`..`5.npy`.\n", "Общий алгоритм:\n", "1. Выгрузить данные из файла\n", "2. Построить график точек\n", "3. Приблизительно определить центры облаков (кластеров)\n", "4. Вызвать функцию `find_line`\n", "5. Построить график с прямой" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Доп. Напишите улучшенную версию функции `find_line`, принимающий несколько центров (т.е. способный разделить более двух кластеров)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cloud_1 = np.random.normal((1,-3), 0.5, (NUM_POINTS, 2)) # Первое облако\n", "cloud_2 = np.random.normal((-2, 1), (0.3,0.5), (NUM_POINTS, 2)) # Второе облако\n", "cloud_3 = np.random.normal((3,1), (0.7,0.3), (NUM_POINTS, 2)) # Второе облако\n", "\n", "data = np.vstack([cloud_1, cloud_2, cloud_3])\n", "clusters = np.vstack([np.zeros(NUM_POINTS), np.ones(NUM_POINTS), np.ones(NUM_POINTS)*2])\n", "\n", "plot_clouds(data, clusters=clusters)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "aaa-ml", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.4" } }, "nbformat": 4, "nbformat_minor": 2 }