Теорема включений-исключений

Теорема включений-исключений (TVI) используется, когда необходимо подсчитать количество элементов в объединении нескольких множеств, учитывая их пересечения. Это важно, когда элементы могут принадлежать нескольким группам одновременно, и простое сложение приведет к дублированию.

📌 Применение в реальных задачах

1️⃣ Анализ аудитории (маркетинг, соцсети, реклама)

💡 Задача: Подсчитать количество уникальных пользователей, которые взаимодействовали с разными рекламными кампаниями.
🔹 Пример:

  • 500 человек видели рекламу в Instagram
  • 600 человек видели рекламу в Facebook
  • 200 человек видели обе рекламы
    Сколько уникальных пользователей видели хотя бы одну рекламу?

500+600−200=900500 + 600 — 200 = 900500+600−200=900

2️⃣ Анализ пересечения данных в SQL (дубли клиентов, товары, сегменты)

💡 Задача: Найти количество уникальных клиентов в базе, если они могут принадлежать нескольким сегментам.
🔹 Пример: В интернет-магазине клиенты покупают:

  • Электронику – 3000 человек
  • Одежду – 4000 человек
  • Оба типа товаров – 1000 человек
    Общее число уникальных покупателей:

3000+4000−1000=60003000 + 4000 — 1000 = 60003000+4000−1000=6000

3️⃣ Обработка данных в дата-сайенсе и машинном обучении

💡 Задача: Подсчет количества уникальных записей при объединении нескольких датафреймов.
🔹 Пример: В датасете есть пересечения клиентов из разных источников данных. TVI позволяет корректно вычислить их общее количество, не учитывая повторяющиеся записи дважды.

4️⃣ Биология и медицина (анализ тестов, мутаций, заболеваний)

💡 Задача: Определение количества пациентов с определёнными симптомами.
🔹 Пример:

  • 500 человек имеют симптом А
  • 700 человек имеют симптом B
  • 200 человек имеют оба симптома
    Общее количество уникальных пациентов:

500+700−200=1000500 + 700 — 200 = 1000500+700−200=1000

Когда НЕ стоит применять?

❌ Когда множества не пересекаются – проще просто сложить их мощности.
❌ Когда порядок элементов важен – лучше использовать перестановки или размещения.
❌ Когда множества очень сложные – тогда лучше применять другие вероятностные методы.

📊 Итог

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

Теорема включений-исключений

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

Формулировка теоремы для двух и трех множеств:

  1. Для двух множеств:

Пусть есть два множества A и B. Количество элементов, принадлежащих хотя бы одному из этих множеств, вычисляется по формуле:
|A ∪ B| = |A| + |B| — |A ∩ B|
Где:

  • |A| — количество элементов в множестве A,
  • |B| — количество элементов в множестве B,
  • |A ∩ B| — количество элементов, которые принадлежат обоим множествам.
  1. Для трех множеств:

Пусть есть три множества A, B и C. Количество элементов, которые принадлежат хотя бы одному из этих множеств, вычисляется по формуле:
|A ∪ B ∪ C| = |A| + |B| + |C| — |A ∩ B| — |A ∩ C| — |B ∩ C| + |A ∩ B ∩ C|
Где:

  • |A|, |B|, |C| — количество элементов в множествах,
  • |A ∩ B|, |A ∩ C|, |B ∩ C| — количество элементов в пересечениях двух множеств,
  • |A ∩ B ∩ C| — количество элементов, принадлежащих всем трем множествам.

Пример 1: Подсчет количества студентов, которые изучают хотя бы один из предметов (математика, физика, химия)

Пусть:

  • 30 студентов изучают математику,
  • 25 студентов изучают физику,
  • 20 студентов изучают химию,
  • 15 студентов изучают и математику, и физику,
  • 10 студентов изучают и математику, и химию,
  • 5 студентов изучают и физику, и химию,
  • 3 студента изучают все три предмета.

По формуле теоремы включений-исключений можно подсчитать количество студентов, которые изучают хотя бы один из этих предметов.∣M∪F∪H∣=∣M∣+∣F∣+∣H∣−∣M∩F∣−∣M∩H∣−∣F∩H∣+∣M∩F∩H∣|M \cup F \cup H| = |M| + |F| + |H| — |M \cap F| — |M \cap H| — |F \cap H| + |M \cap F \cap H|∣M∪F∪H∣=∣M∣+∣F∣+∣H∣−∣M∩F∣−∣M∩H∣−∣F∩H∣+∣M∩F∩H∣

где:

  • MMM — студенты, изучающие математику,
  • FFF — студенты, изучающие физику,
  • HHH — студенты, изучающие химию.

Пример 2: Подсчет количества уникальных пользователей в аналитике данных

Предположим, что у нас есть данные о посещении трех веб-сайтов пользователями:

  • 100 пользователей посетили сайт A,
  • 150 пользователей посетили сайт B,
  • 200 пользователей посетили сайт C,
  • 50 пользователей посетили и сайт A, и сайт B,
  • 75 пользователей посетили и сайт A, и сайт C,
  • 60 пользователей посетили и сайт B, и сайт C,
  • 30 пользователей посетили все три сайта.

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

|A ∪ B ∪ C| = |A| + |B| + |C| — |A ∩ B| — |A ∩ C| — |B ∩ C| + |A ∩ B ∩ C|

Реализация на Python

Теперь рассмотрим, как мы можем применить теорему включений-исключений в Python, используя пример с пользователями веб-сайтов:

# Данные
A = 100  # пользователи сайта A
B = 150  # пользователи сайта B
C = 200  # пользователи сайта C

A_and_B = 50  # пользователи, посетившие A и B
A_and_C = 75  # пользователи, посетившие A и C
B_and_C = 60  # пользователи, посетившие B и C

A_and_B_and_C = 30  # пользователи, посетившие все три сайта

# Применение теоремы включений-исключений
unique_users = A + B + C - A_and_B - A_and_C - B_and_C + A_and_B_and_C

print(f"Количество уникальных пользователей: {unique_users}")

Этот код рассчитает количество уникальных пользователей, посетивших хотя бы один из трех сайтов.

Теги: