Посмотрите на эти два набора точек и подумайте: какой из них кажется вам более «случайным»? Распределение на левом рисунке явно неравномерно.
Есть места, где точки сгущены, а есть места, где точек почти нет: из-за этого может даже показаться, что левый график темнее.
На правом рисунке локальные сгущения и разрежения также присутствуют, но менее заметны.
Между тем именно левый график был получен с помощью «честного» генератора случайных чисел.
Правый график также содержит совершенно случайные точки; но эти точки генерируются так, что все маленькие квадраты содержат одинаковое количество точек.
Стратификация - метод выделения подмножества объектов из генеральной совокупности, разделенной на подмножества (страты).
При расслоении объекты выбираются таким образом, чтобы в итоговой выборке сохранялись соотношения размеров стратов (или нарушаются контролируемым образом эти соотношения см.
в пункте 3).
Скажем, в рассмотренном примере популяция состоит из точек внутри единичного квадрата; страты — это наборы точек внутри меньших квадратов.
Стратификацию целесообразно использовать в любой выборке.
Например, в социологических исследованиях необходимо соблюдать стратификацию хотя бы по возрасту и месту жительства респондентов.
В машинном обучении стратификация полезна как на этапе сбора данных, так и во время процесса.
1. Простой пример: вычисление площади фигуры
Во-первых, чтобы продемонстрировать силу стратификации, я использую наборы точек, созданные во введении, для расчета площади пятна — четверти круга с радиусом 0,4. Случайные точки будут брошены внутрь единичного квадрата и увеличат счетчик, когда они попадут внутрь круга.
Отношение полученного числа к общему количеству бросков и будет оценкой площади фигуры по Метод Монте-Карло .
Самый простой (нестратифицированный) способ создания случайных точек для этой задачи: осуществлять Так:
Стратификацию можно реализовать разными способами, я выбрал следующий : все квадратики пронумерованы, и при их генерации следующая точка попадает в квадрат со следующим номером; цифры зациклены.import random random.seed(100) for i in range(500): x, y = random.random(), random.random() print x, y
Этот метод хорошо работает только в том случае, если общее количество точек кратно количеству страт, но, к счастью, в данном случае это так.
import random
random.seed(100)
cellsCount = 10
cellId = 0
for i in range(500):
cellVerticalIdx = (cellId / cellsCount) % cellsCount
cellHorizontalIdx = cellId % cellsCount
cellId += 1
left = float(cellVerticalIdx + 0) / cellsCount
right = float(cellVerticalIdx + 1) / cellsCount
top = float(cellHorizontalIdx + 1) / cellsCount
bottom = float(cellHorizontalIdx + 0) / cellsCount
x, y = random.random(), random.random()
x = left + x * (right - left)
y = bottom + y * (top - bottom)
print x, y
Теперь мы будем повторно генерировать наборы точек и отслеживать расхождение — величину отклонения полученной оценки площади от истинного значения.
Код простого алгоритма: Здесь , а для стратифицированных - Здесь .
Видно, что оценка, полученная стратифицированным методом, превосходит точность и имеет меньшую дисперсию.
На этом этапе вы можете возразить, что нужно было просто взять регулярную сетку и таким образом сделать дисперсию равной нулю.
Однако такая оценка не будет несмещенный ! Кроме того, рассматриваемая задача является модельной, и никакую регулярную сетку нельзя использовать для множества людей или, скажем, поисковых запросов.
2. Перекрестная проверка
Следующие примеры взяты из области машинного обучения.Ситуация первая: в задаче существуют объективные зависимости, которые необходимо учитывать для адекватной оценки качества моделей.
Например, в задачах кластеризации функция близости двух объектов может зависеть от размера кластера, и необходимо добиться равномерного распределения размеров кластеров между обучающей и тестовой выборками.
Если этого не сделать, оценки качества будут занижены.
Ситуация вторая: нестационарность восстанавливаемых зависимостей, т.е.
их изменчивость во времени.
Таким образом, прогнозирование посещаемости торговых центров существенно зависит от того, является ли выбранный день выходным.
Чтобы получить адекватные оценки способности к обобщению, все дни в обучающем наборе должны предшествовать дням, включенным в тестовый набор.
Если этого не сделать, оценки качества будут завышены, обычно чрезвычайно.
Я продемонстрирую стратификацию на модельной задаче первого типа.
Рассмотрим эту зависимость: 
Пусть эта зависимость аппроксимируется одномерной линейной моделью.
Лишь небольшая часть примеров отклоняется от простой линейной аппроксимации, и именно эти примеры внесут основной вклад в величину ошибки модели.
По сути, чем больше таких «выбросов» окажется в тестовой выборке, тем меньше их будет в обучающей выборке, тем выше ошибка в тестовой выборке.
Можно даже сказать, что каждый раз измеряется не метод обучения, а степень равномерности распределения выбросов между обучающей и тестовой выборками! Генерация выборки, обучение одномерной линейной модели, процесс множественной перекрестной проверки, в т.ч.
стратифицированный, а также построение вариационного ряда я реализовал так .
Я не буду сейчас вдаваться в подробности реализации (тем более, что она не очень точна), а сразу приведу графики вариационного ряда полученных оценок: 
Действительно, без стратификации оценки имеют большую дисперсию и, кроме того, занижены.
Однако необходимо понимать, что стратифицированная оценка будет правильной только в том случае, если доля выбросов в выборке репрезентативна для доли выбросов в генеральной совокупности.
3. Немного математики
Методы стратификации часто используются в онлайн-экспериментах; для веб-сервисов это вполне естественно: поведение пользователей зависит от характеристик устройств, операционных систем, версий браузеров, особенностей самих пользователей и так далее.Поэтому без стратификации в A/B-тестах легко столкнуться с тем, что, скажем, доли мобильных пользователей в сплитах различаются на 0,5% и интегральные метрики измеряют эффект этого дисбаланса, а не изменения, которое происходит. сделал.
Стратифицированный подход в данном случае требует разделения наблюдений на страты (по версиям устройств, ОС, браузеров и т.д.), расчета метрик внутри стратов, их взвешивания по размерам этих стратов и получения таким образом значений интегральных показателей.
.
Классической работой в этой области является статья Стратифицированная онлайн-выборка: оценка классификаторов в веб-масштабе от Microsoft Research, которую я настоятельно рекомендую прочитать.
В общем, мы будем предполагать, что нам дана популяция размером 
, из которых выбираются без повторов 
представители для оценки вероятности 
принадлежность элемента коллекции к определенному классу 
.
Население делится на 
непересекающиеся подмножества – страты.
Внутри 
слой размером го размера 
можно посчитать смету 
вероятность принадлежности элемента страты к классу
.
Тогда стратифицированная оценка вероятности будет рассчитываться как 
Дисперсия этой величины, обусловленная независимостью выборов внутри каждой из страт, рассчитывается просто: 
Интересно, что для минимизации дисперсии требуется выборка из слоев, непропорциональных их размеру! Если выбрано
объекты из общей популяции, кол-во 
объекты из
страты для минимизации дисперсии оказывается пропорциональным произведению размера страты и стандартного отклонения значения внутри этой страты: 
Единственная трудность здесь состоит в том, что для реализации оптимального выборка необходимо заранее знать отклонения внутри страт. Однако на практике они зачастую известны с достаточной точностью.
Теперь понятно, что делать с систематическими отклонениями в данных: их можно нивелировать стратификацией и последующим перевзвешиванием.
Например, если данные по социально-демографическим показателям существенно смещены, можно провести стратификацию по ним, а веса страт взять из соответствующей официальной статистики.
Выводы и прагматика
При работе с данными, как и в социологических исследованиях, потребность в хорошей стратификации может быть острой.
При анализе логов веб-панелей вроде LikeWeb или Alexa можно получить неверные результаты из-за нерепрезентативности множества пользователей, установивших расширение.
Клиентские части сервисов теряют часть информации при логировании, чаще у пользователей со слабым сетевым подключением.
Ошибки такого типа могут испортить аналитику и в конечном итоге привести к неверным решениям в разработке продукта и бизнеса.
Всякий раз, когда вы обрабатываете новый набор данных, полезно спросить себя: репрезентативен ли он? Не нуждается ли она в дальнейшей стратификации и переоценке? Что известно о его происхождении и возможных искажениях? Если ответов нет или они неудовлетворительны, вполне возможно, что данные вас обманут. Теги: #Машинное обучение #математика #Алгоритмы #статистика #стратификация
-
Дайджест Игровой Индустрии: Март
19 Oct, 24 -
Еженедельный Подкаст №60
19 Oct, 24
