Градиентная повышающая регрессия

Gradient Boosting — это метод ансамблевого обучения, который объединяет несколько слабых моделей (обычно деревьев решений), чтобы получить мощную и точную модель. Идея заключается в том, чтобы каждое следующее дерево исправляло ошибки предыдущего.

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

Каждое новое дерево учится на градиенте ошибки предыдущего, отсюда и название — градиентный бустинг.

Наивная байесовская классификация

Алгоритм машинного обучения, который основан на теореме Байеса. Он называется «наивным» потому, что предполагает независимость всех признаков друг от друга — даже если на практике это не всегда так. Несмотря на такое упрощение, алгоритм показывает отличные результаты в задачах классификации текста и фильтрации спама.

Основная идея — вычислить вероятность того, что объект принадлежит определенному классу, учитывая его признаки. Для этого используется формула Байеса.

Алгоритм наивного Байеса оценивает вероятность для каждого класса и выбирает тот, у которого вероятность выше.

Используется для фильтрация спама, анализа тональности или, например, классификации новостей.

Кластеризация k-средних — Группировка по схожести

Алгоритм k-средних (k-Means) — метод кластеризации без учителя, который делит набор данных на заранее заданное количество кластеров (k). Точки данных группируются вокруг центров кластеров на основе их схожести.

Цель алгоритма — минимизировать сумму квадратов расстояний от каждой точки до ближайшего центра кластера. Проще говоря, он старается сделать кластеры как можно более плотными и четко отделенными друг от друга.

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

DBSCAN — Кластеризация на основе плотности

Density-Based Spatial Clustering of Applications with Noise — алгоритм кластеризации, объединяющий точки данных в группы на основе их плотности. Если точки находятся близко друг к другу, они считаются частью одного кластера. Если точка сильно удалена от других, она считается выбросом (шумом).

Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".

Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.

Поиск самой длинной общей подпоследовательности (Longest Common Subsequence)

Используется для нахождения наибольшей общей подпоследовательности между двумя строками или последовательностями.

Алгоритм:

1. Создание таблицы. Создаем таблицу размером (n+1) на (m+1), где n и m - длины строк или последовательностей.

2. Итеративно проходимся по каждой ячейке таблицы слева направо и сверху вниз, сравнивая символы текущей позиции.
-Если символы совпадают, увеличиваем значение ячейки на 1 и переходим диагонально влево-вверх.
-Если символы не совпадают, выбираем максимальное значение из ячейки слева и сверху и записываем его в текущую ячейку.

3. Восстановление подпоследовательности. Начинаем с нижней правой ячейки таблицы и движемся влево или вверх, выбирая ячейки с максимальным значением. Если значения ячеек совпадают, добавляем символ к подпоследовательности и двигаемся диагонально влево-вверх. Повторяем этот процесс до тех пор, пока не достигнем левой верхней ячейки таблицы.

Сложность: O(n*m)

Поиск Фибоначчи

Метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.

Последовательность Фибоначчи начинается с чисел 0 и 1, а каждое следующее число равно сумме двух предыдущих чисел. Вот первые несколько чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.

Сложность: O(log n)

Судоку

Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е. i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.
⁃ Другой базовый случай — когда значение столбца равно N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.
4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е. i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.
5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е. i, j+1.

Сложность: O(9^(n*n)

Проверка строки-палиндрома

Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «abba» является палиндромом, потому что обратная сторона «abba» будет равна «abba».

Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.

Сложность: O(n)

Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)

LPS — это самая длинная последовательность символов, которая является палиндромом.

Алгоритм поиска LPS:
1. Создаем матрицу dp размером n x n, где n - длина исходной строки.
2. Заполняем главную диагональ матрицы значениями 1, так как каждый символ сам по себе является палиндромом длины 1.
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу dp с помощью следующих правил:
- Если символы на текущих позициях равны, увеличиваем значение dpij на 2 и переходим к следующим символам (i+1, j-1).
- Если символы не равны, выбираем максимальное значение из dpi+1j и dpij-1 и записываем его в dpij.
4. Возвращаем значение dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.

Сложность: O(n^2), где n - длина исходной строки.

Ханойская башня

Головоломка, состоящая из трех стержней и набора дисков разного размера. Изначально диски располагаются на одном стержне в порядке убывания размера (больший диск находится ниже меньшего).
1. За один раз можно переместить только один диск.
2. Нельзя помещать больший диск на меньший.

Алгоритм:
1. Если на исходном стержне есть только один диск, переместите его на целевой стержень.
2. Если на исходном стержне есть больше одного диска, выполните следующие шаги:
- Переместите все диски, кроме самого большого, с исходного стержня на вспомогательный стержень.
- Переместите самый большой диск с исходного стержня на целевой стержень.
- Переместите все оставшиеся диски с вспомогательного стержня на целевой стержень.

Алгоритм: O(2^n), где n - количество дисков.

Алгоритмы замены страниц в операционных системах (FIFO)

Цель алгоритма: уменьшение количества ошибок страниц.

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

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

Сложность: O(n), где n — количество страниц.

🚗 Как найти кратчайший маршрут с помощью Apache Spark и GraphFrames

Разбираем кейс на реальных данных из OpenStreetMap — ищем оптимальный маршрут

🔍 Что делаем
1. Загружаем граф дорог города с помощью OSMnx
2. Сохраняем вершины и ребра с координатами, скоростями и геометрией
3. Загружаем всё в Spark
4. Находим кратчайший путь с помощью GraphFrames

📍 1. Скачиваем карту и строим граф улиц

import osmnx as ox

# Загрузка данных о дорогах Москвы
G = ox.graph.graph_from_place("Moscow", network_type="drive")

# Отображение дорог на карте
moscow_gdf = ox.geocoder.geocode_to_gdf("Moscow")
fig, ax = ox.plot.plot_graph(G, show=False, close=False, bgcolor="#111111", edge_color="#ffcb00", edge_linewidth=0.3, node_size=0)
moscow_gdf.plot(ax=ax, fc="#444444", ec=None, lw=1, alpha=1, zorder=-1)

# Настройка границ карты
margin = 0.02
west, south, east, north = moscow_gdf.union_all().bounds
margin_ns = (north - south) * margin
margin_ew = (east - west) * margin
ax.set_ylim((south - margin_ns, north + margin_ns))
ax.set_xlim((west - margin_ew, east + margin_ew))
plt.show()

📁 2. Сохраняем геометрическое описание города в формате GeoJSON и данные о вершинах и рёбрах в формате CSV

with open('Moscow.geojson', 'w') as file:
    file.write(moscow_gdf.to_json())

nodes = G.nodes(data=True)
with open('nodes.csv', 'a') as file:
    file.write("id,lat,lonn")
    for (node, data) in nodes:
        file.write("%d,%f,%fn" % (node, data.get("y"), data.get("x")))

edges = G.edges(data=True)
def decode_maxspeed(maxspeed):
    match maxspeed:
        case str():
            match maxspeed.lower():
                case "ru:urban": return 60
                case "ru:rural": return 90
                case "ru:living_street": return 20
                case "ru:motorway": return 110
                case _: return int(maxspeed)
        case list(): return min(list(map(decode_maxspeed, maxspeed)))
        case _: return maxspeed

with open('edges.csv', 'a') as file:
    file.write("src,dst,maxspeed,length,geometryn")
    for (src, dst, data) in edges:
        maxspeed = decode_maxspeed(data.get("maxspeed", 999))
        length = float(data.get("length"))
        geometry = shapely.wkt.dumps(data.get("geometry"))
        file.write("%d,%d,%d,%f,%sn" % (src, dst, maxspeed, length, geometry))

3. Используем библиотеку GraphFrames для обработки графов на Apache Spark

from pyspark.sql import SparkSession

spark = SparkSession.builder 
    .config("spark.jars.packages", "graphframes:graphframes:0.8.4-spark3.5-s_2.12") 
    .master("local[*]") 
    .appName("GraphFrames") 
    .getOrCreate()

nodes = spark.read.options(header=True).csv("nodes.csv")
edges = spark.read.options(header=True).csv("edges.csv")

# Вычисление времени прохождения рёбер
edgesT = edges.withColumn("time", edges["length"] / edges["maxspeed"])

# Построение графа
from graphframes import *

g = GraphFrame(nodes, edgesT)

🧭 4. Ищем кратчайший путь по времени
например, от Измайлово до ЖК Зиларт

src = "257601812"
dst = "5840593081"

paths = g.shortestPaths(landmarks=[dst])
paths.filter(F.col("id") == src).show(truncate=False)

💡 Результат: 40 шагов от точки A до точки B.

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

🚀 Хотите прокачаться в работе с Big Data? Изучайте Spark! Записывайтесь на курс Spark Developer от OTUS — учитесь на реальных данных и продвинутых кейсах: https://otus.pw/he60/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Алгоритм оптимальной замены страниц

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

Идея проста: для каждой ссылки мы делаем:
⁃ Если указанная страница уже существует, увеличьте количество обращений.
⁃ Если нет, найдите страницу, на которую никогда не будут ссылаться в будущем. Если такая страница существует, замените ее новой страницей. Если такой страницы не существует, найдите страницу, на которую в будущем будут чаще всего ссылаться. Замените эту страницу новой страницей.

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

Сложность: O(n × f), где n — количество страниц, а f — количество кадров.

Что общего между хакерской атакой и защитой от неё?

И то, и другое сегодня используют нейросети и автоматизированные системы. Узнайте, как начать карьеру в сфере кибербезопасности на дне открытых дверей онлайн-магистратуры УрФУ и Нетологии «Современные технологии безопасных систем».

На встрече вы узнаете:

– кто такой аналитик SOC и специалист по безопасной разработке;
– какие навыки нужны, чтобы стать востребованным на рынке;
– что нужно для поступления и обучения онлайн.

📅 19 июня, 18:00 (Мск)
🔗 [Регистрация]

Реклама. ООО "Нетология", ИНН: 7726464125, erid: 2W5zFJhXajA

Least Recently Used алгоритм замены страниц

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

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

Авторский канал инженера, который публикует свои практические Linux заметки. Ключевые слова и темы канала: Open Source, Dotfiles, Debian, Software, Linux, Scripts, Notes, Terminal, Shell, Gnu, Tools, Fun, Free Software Movement.

Подписывайтесь и узнавайте много полезного!

Most Recently Used алгоритм замены страниц

Используется в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.

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

Матрица

Двумерная структура данных, состоящая из набора элементов, расположенных в строках и столбцах.

Каждый элемент матрицы идентифицируется индексами строки и столбца.

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

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

Новые модели обучаются быстрее, учитывают больше контекста пользователя. Алгоритмы анализируют только обезличенные данные. Всё это улучшает качество рекомендаций не только для слушателей и покупателей, но и для создателей контента — музыкантов, авторов, продавцов, которым важно найти свою аудиторию.

Первым сервисом, где внедрили новые алгоритмы, стала Яндекс Музыка. Туда внедрили трансформеную модель с 126 млн параметров и длиной истории пользователей 8192 (события в жизни пользователей). Прирост получился значительный, раньше максимальная конфигурация имела лишь 19 млн в энкодере. Затем технология распространилась на Яндекс Маркет и сейчас тестируется в других сервисах.

По результатам: в Яндекс Музыке пользователи стали на 20% чаще ставить лайки и добавлять в коллекции новые треки и исполнителей, а разнообразие рекомендаций выросло. . Кроме того, «Мою волну» стали слушать дольше и чаще.

Поворот элементов матрицы

Идея состоит в том, чтобы поочередно вращать все кольца элементов, начиная с самого дальнего.

Чтобы повернуть кольцо, нам нужно сделать следующее.
1. Переместить элементы верхнего ряда.
2. Переместить элементы последнего столбца.
3. Переместить элементы нижнего ряда.
4. Переместите элементы первого столбца.

Повторить вышеуказанные шаги для внутреннего кольца, пока оно есть.

Сложность: O(m*n), где m — количество строк, а n — количество столбцов.