Вопрос или проблема
У меня следующая проблема:
Есть большой набор записей. У каждой записи в наборе есть атрибут. Для некоторых значений атрибута существует только одна запись, для других значений есть много записей с этим значением. Я хочу составить распределение количества атрибутов с определенным количеством записей. Например, миллиарды значений атрибута имеют ровно одну запись, полмиллиарда — две записи, …, и наконец, одно значение атрибута с пятью миллионами записей. Представьте список всех собак в мире с именем владельца в качестве атрибута. Мне нужно знать, сколько людей имеют одну собаку, сколько имеют две собаки и так далее. Для малых наборов это распределение легко вычислить, но для большого набора требуется много памяти. Меня интересуют приблизительные методы, которые используют какой-то вид выборки для получения результатов с ограниченной точностью. Я уверен, что эта проблема должна быть хорошо изучена, но я не знаю, что искать.
Не могли бы вы дать мне какие-то указания, где искать и как это называется в литературе?
Я думаю, вы можете использовать этот ответ или упомянутые там ссылки, чтобы отобрать определенное количество N различных имен и еще один скан, чтобы вычислить количество и построить приближенный гистограмму.
Я не проверял, так ли это, но простой идеей может быть сначала использовать резервуарную выборку для выбора M > N случайных записей (отбрасывая те, которые содержат дублирующиеся значения), а затем сохранить $i$-ую запись только в том случае, если она оказывается первой записью с этим значением в вашем массиве.
Ответ или решение
Ваш вопрос относится к известной задаче в области обработки данных и статистического анализа. Основная идея вашей проблемы заключается в необходимости построения распределения частот для значений определенного атрибута в большом наборе данных.
Теория
Эта задача является типичной для анализа частот встречаемости в статистике и обработки больших данных, и часто решается с использованием методов, таких как построение гистограмм и оценка плотности распределения. В контексте распределения частот, вам необходимо определить, как часто встречается каждый уровень частоты значений атрибута. Например, сколько людей имеют одну собаку, сколько — две и так далее. Как правило, такая задача требует значительных вычислительных ресурсов, особенно на больших наборах данных.
Пример
Для небольших наборов данных распределение частот может быть построено напрямую, обходя каждый запись и подсчитывая встречаемость значений атрибута. Однако, для больших наборов данных, как в вашем случае, данный подход не является эффективным с точки зрения использования памяти и времени выполнения. Допустим, вы имеете записи о владельцах собак во всем мире. Вы можете собрать данные для построения гистограммы, чтобы понять распределение частоты владения собаками.
Применение
Для решения вашей задачи с учетом ограничений на память и вычислительную мощность, стоит обратить внимание на методы оценки и аппроксимации, такие как резервуарная выборка (reservoir sampling). Этот метод позволяет сохранять случайные подвыборки из потоков данных фиксированного размера, что позволяет оценить распределение без необходимости хранения всех данных.
-
Резервуарная выборка для уникальных значений: одна из техник заключается в выборке уникальных значений атрибута с помощью резервуарной выборки. Вы выбираете небольшую фиксированную подвыборку уникальных значений, а затем уже на основе их частот строите приближённую гистограмму.
-
Гистограмма частот: на основе полученных данных можно построить приближённую гистограмму распределения частот. Это может быть выполнено с помощью одного прохода через данные, что делает метод достаточно эффективным для применения в условиях ограниченной памяти.
Вам также могут быть полезны исследование и применение методов из области вероятностных данных структур, таких как Count-Min Sketch, которые позволяют компромиссно хранить и обрабатывать информацию о частотах.
Таким образом, применяя эти методы, вы сможете эффективно оценить распределение частот атрибутов в больших наборах данных с минимальными требованиями к памяти, и при этом сохранить приемлемую точность.