Моделирование корреляционных зависимостей

Корреляционная зависимость – статистическое соотношение между двумя или более переменными, проявляющееся в совместном изменении их значений. В прикладной информатике корреляции используются для анализа таблиц, временных рядов, баз данных и массивов измерений; для отбора признаков и верификации гипотез о связи величин. Для ЕГЭ по информатике это важно по трём причинам:

1. требуется уверенно работать с массивами чисел/таблицами, уметь вычислять агрегаты и аккуратно обращаться с вещественной арифметикой;

2. распространены вопросы «информатического чтения данных» (распознавание направления/силы связи, корректная интерпретация диаграмм);

3. умение строить корректные алгоритмы подсчёта (в том числе однопроходные) и оценивать их сложность.

Ниже дана строгая теория, переносимые формулы (скопируемые без форматирования), алгоритмические схемы, правила корректности и 5 упражнений экзаменационного типа.

Базовые определения и величины

Пусть есть два числовых массива одинаковой длины n ≥ 2:
X = (x1, x2, ..., xn), Y = (y1, y2, ..., yn).

Средние значения:

x̄ = (1/n) * Σ_{i=1..n} xi

ȳ = (1/n) * Σ_{i=1..n} yi

Несмещённые оценки дисперсий и ковариации (стандарт в прикладной статистике и программировании):

VarX = (1/(n-1)) * Σ_{i=1..n} (xi - x̄)^2

VarY = (1/(n-1)) * Σ_{i=1..n} (yi - ȳ)^2

CovXY = (1/(n-1)) * Σ_{i=1..n} (xi - x̄)*(yi - ȳ)

Коэффициент корреляции Пирсона:

r = CovXY / (sqrt(VarX) * sqrt(VarY))

Свойства:

-1 ≤ r ≤ 1

r > 0 – прямая связь; r < 0 – обратная; r ≈ 0 – линейной связи нет (но может быть нелинейная).

Коэффициент Спирмена (монотонная ранговая зависимость):

1. заменяем значения рангами RgX_i, RgY_i (со средними при совпадениях),

2. считаем Пирсона на рангах:
   ρ = Corr_Pearson(RgX, RgY)

Для уникальных рангов есть удобная формула:

ρ = 1 - (6 * Σ d_i^2) / (n*(n^2 - 1)),  где d_i = RgX_i - RgY_i

Φ-коэффициент (для бинарных переменных) по частотной таблице [[n11, n10],[n01, n00]]:

φ = (n11*n00 - n10*n01) / sqrt( (n11+n10)*(n01+n00)*(n11+n01)*(n10+n00) )

Фактически это Пирсон для 0/1-признаков.

Алгоритмика вычислений

1. Однопроходный устойчивый алгоритм (вариант Вэлфорда/Ченга)
   

   Цель – считать x̄, ȳ, VarX, VarY, CovXY за один проход без потери точности.

   Псевдокод:

   n := 0

   meanX := 0; meanY := 0

   m2X := 0; m2Y := 0        # суммы для дисперсий: Σ (xi - meanX)^2 и Σ (yi - meanY)^2

   covXY := 0                 # сумма для ковариации

   
   

   for (x, y) in потокe пар:

       n := n + 1

       dx := x - meanX

       dy := y - meanY

       meanX := meanX + dx / n

       meanY := meanY + dy / n

       m2X := m2X + dx * (x - meanX)

       m2Y := m2Y + dy * (y - meanY)

       covXY := covXY + dx * (y - meanY)   # ключ к устойчивости

   # после цикла:

   VarX  := m2X / (n - 1)

   VarY  := m2Y / (n - 1)

   CovXY := covXY / (n - 1)

   r     := CovXY / (sqrt(VarX) * sqrt(VarY))

   Сложность: O(n) по времени, O(1) по памяти. Алгоритм численно устойчив, не требует хранения всего массива.

2. Корреляционная матрица для d признаков
   

   Пусть X – таблица n × d. Требуется матрица R (d×d), где R[a,b] = Corr(X_a, X_b).

   Схема:

   1. предварительно вычислить векторы средних и стандартных отклонений;

   2. вычислить ковариационную матрицу Σ (можно однопроходно блоками);

   3. нормировать:

   R[a,b] = Σ[a,b] / (sqrt(Σ[a,a]) * sqrt(Σ[b,b]))

   Сложность наивно O(n*d^2) по времени, O(d^2) по памяти. Для больших d применяют блочно-стриминговые методы.

Моделирование данных с заданной корреляцией

1. Построение пары (X, Y) с целевым r (простая конструкция)
   

   Пусть Z – независимый от X шум со средним 0 и дисперсией 1, X стандартизован: E[X]=0, Var[X]=1. Определим:

   Y = a*X + b*Z

   Тогда:

   Corr(X, Y) = a / sqrt(a^2 + b^2)

   Чтобы получить заданный r ∈ (-1,1), можно взять:

   a = r

   b = sqrt(1 - r^2)

   Если X не стандартизован, предварительно переходим к стандартизированным переменным:

   X' = (X - x̄) / sqrt(VarX)

   Z ~ N(0,1) независимая

   Y' = r * X' + sqrt(1 - r^2) * Z

   # затем денормируем Y' под нужные среднее и дисперсию, если требуется.

2. Многомерный случай (корреляционная структура d×d)
   

   Задан желаемый корреляционный симметричный положительно определённый R. Строим X ~ N(0, I), берём разложение Холецкого R = L * L^T, тогда:

   Y = X * L^T

   Колонки Y будут иметь корреляционную матрицу близкую к R (по закону больших чисел при достаточном n).

Правила корректности и интерпретации (информатика)

Правило 1. Предобработка данных.
Единицы измерения, пропуски, выбросы, дубликаты – фиксируйте явно. Пропуски либо удаляются синхронно по паре (списочное исключение), либо заполняются корректно; смешивать стратегии нельзя.

Правило 2. Используйте устойчивые алгоритмы.
Однопроходные схемы (см. §2.1) предотвращают катастрофическую потерю значащих разрядов при больших n.

Правило 3. Выбор коэффициента.
Пирсон – для линейной связи и числовых шкал интервал/отношение; Спирмен – для монотонной связи и рангов/несимметричных распределений; φ – для бинарных.

Правило 4. Масштабирование и центровка.
Для корректного моделирования задавайте стандартные формы (среднее 0, дисперсия 1), далее денормируйте.

Правило 5. Корреляция ≠ причинность.
Алгоритмически сильная |r| не означает причинной связи; на ЕГЭ требуются корректные формулировки: «наблюдается прямая/обратная линейная связь», без выводов о причине.

Правило 6. Многомерность и мультиколлинеарность.
Высокая корреляция признаков означает избыточность. В задачах отбора признаков избегайте почти коллинеарных столбцов (численно неустойчивые вычисления).

Правило 7. Контроль точности вывода.
Для ЕГЭ округляйте в соответствии с требованием задачи; в алгоритмах– храните двойную точность (float64).

Связь с ЕГЭ по информатике

• Работа с таблицами/массивами: аккуратный подсчёт сумм, средних, отклонений.

• Правильная обработка пропусков и граничных случаев (n=2, одинаковые значения).

• Интерпретация знака и относительной величины корреляции по словесным/графическим описаниям.

• Программные фрагменты: распознавание корректных и некорректных вычислительных схем (двупроходные vs однопроходные, стабильность).

• Оценка сложности и памяти для матриц корреляций.

Мини-шпаргалка (копируемые формулы)

x̄ = (1/n) * Σ xi

ȳ = (1/n) * Σ yi

VarX = (1/(n-1)) * Σ (xi - x̄)^2

VarY = (1/(n-1)) * Σ (yi - ȳ)^2

CovXY = (1/(n-1)) * Σ (xi - x̄)*(yi - ȳ)

r = CovXY / (sqrt(VarX) * sqrt(VarY))

ρ = 1 - (6 * Σ d_i^2) / (n*(n^2 - 1))   (для уникальных рангов)

φ = (n11*n00 - n10*n01) / sqrt( (n11+n10)*(n01+n00)*(n11+n01)*(n10+n00) )

Пять упражнений (академический формат)

Упражнение 1. Пирсон и устойчивый подсчёт
Дан набор пар значений (xi, yi), n=8, с большими абсолютными величинами и малым разбросом.
a) Реализуйте однопроходный алгоритм из §2.1 (псевдокод), укажите, какие переменные инициализируются нулём и почему.
b) Сравните результат с наивной двупроходной схемой (сначала средние, затем суммы квадратов). Объясните расхождение при ограниченной точности.
c) Оцените асимптотику обеих схем по времени/памяти, назовите преимущества однопроходной реализации для потоков данных.

Упражнение 2. Выбор коэффициента и интерпретация
Рассмотрите три набора данных одинакового размера n:
1)    линейная зависимость с шумом; 2) строго монотонная нелинейная; 3) U-образная (парабола).

a) Для каждого набора обоснуйте выбор Пирсона или Спирмена.
b) Предскажите знак и относительную величину коэффициента (высокая/средняя/низкая связь).
c) Объясните, почему для U-образного набора Пирсон может дать r ≈ 0, хотя зависимость «сильная» визуально.

Упражнение 3. Моделирование заданного r
Пусть требуется сгенерировать пару (X, Y) с целевой корреляцией r = 0.8.
a) Предложите процедуру стандартизации X и построения Y вида Y = a*X + b*Z, указав a и b (см. §3.1).
b) Покажите, как денормировать Y до желаемых E[Y] = μ и Var[Y] = σ^2.
c) Обсудите, как изменится метод, если целевой r отрицателен.

Упражнение 4. Корреляционная матрица и мультиколлинеарность
Дана таблица n × d, d=6.
a) Опишите алгоритм вычисления корреляционной матрицы R с использованием предварительного подсчёта средних/СКО по столбцам.
b) Предложите критерий обнаружения мультиколлинеарности через порог по |R[a,b]| (например, ≥ 0.95) и объясните, почему это важно для последующих вычислений.
c) Оцените время и память алгоритма при n=10^5, d=10^3; предложите блочную (стриминговую) модификацию.

Упражнение 5. Дискретные признаки и φ-коэффициент
Есть бинарные признаки A и B с частотами: n11 = 120, n10 = 30, n01 = 20, n00 = 230

a) Вычислите φ по формуле из §1.
b) Интерпретируйте знак и силу связи.
c) Сравните φ с корреляцией Пирсона, если закодировать признаки как 0/1 и посчитать r напрямую; объясните эквивалентность.

Заключение

Моделирование корреляционных зависимостей в информатике – это сочетание строгих статистических формул, численно устойчивых алгоритмов и дисциплины предобработки данных. Для задач уровня ЕГЭ важно:

• корректно и точно вычислять средние, дисперсии, ковариации и корреляции;

• осознанно выбирать коэффициент (Пирсон/Спирмен/φ) под тип данных;

• понимать разницу между линейной и монотонной связью, а также ограничения интерпретации r;

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

Следование приведённым правилам и проработка упражнений формируют устойчивые навыки точного анализа данных и корректной реализации алгоритмов – те самые навыки, которые требуются для уверенного решения экзаменационных задач.