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

Question

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

Как сгенерировать случайное подмножество (скажем, 100 пользователей), которые удовлетворяют этим условиям:

• 40% должны быть мужчины и 60% - суки
• 50% должен родиться в США, 20 %, рожденные в Великобритании, 20% рожденных в Канаде, 10% в Австралии
• 70% должны быть женаты и 30% нет.

Эти условия являются независимыми, что мы не можно сделать так:

• (0,4 * 0,5 * 0,7) * 100 = 14 пользователей, которые мужчины, родившиеся в США и женился
• (0,4 * 0,5 * 0,3) * 100 = 6 пользователей, которые являются мужчинами, родившимися в США и не состоящими в браке.

Есть ли алгоритм для этого поколения?

Answer 1

Вы могли бы попробовать что-то вроде этого:

• Выберите случайный начальный набор 100
• Пока вы не имеете право распределения (или отказаться):
  • Выберите случайную запись не набор и случайный, который равен
  • Если замена другой записи приближает вас к набору, вы хотите обменять их. В противном случае, не надо.

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

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

Answer 2

Неточная информация? Обычно, если вы создаете образец, подобный этому, вы делаете статистическое исследование, поэтому достаточно создать примерный образец.

Вот как это сделать:

имеют функцию genRandomIndividual().

Каждый раз, когда вы создаете индивидуальный, использовать случайную функцию, чтобы выбрать пол - мужчина с вероятностью 40%

Выберите местоположение рождения, используя случайную функцию снова (только генерировать реальные в интервале 0-1, а если он падает 0-.5, выбирает США, если .5-.7, то & K, если .7-.9 тогда Канада, в противном случае Австралия).

Выберите статус замужества, используя случайную функцию (снова сгенерируйте в 0-1, если 0-.7 затем вышла замуж, иначе нет).

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

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

Answer 3

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

Answer 4

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

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

Прежде всего, упорядочивайте исходные данные, чтобы вы могли легко получить доступ к каждой комбинации типов, то есть группы, состоящие в браке с американскими мужчинами в одной куче, не состоящие в браке американские мужчины в другой и т. Д. Тогда, при условии, что у вас есть р условия, и вы хотите, чтобы выбрать к элементов делают р массивов размера к каждый; один массив будет представлять одно условие. Сделать элементы каждого массива типами этого условия в необходимых пропорциях. Таким образом, в вашем примере в матрице пола будет 40 мужчин и 60 женщин.

Теперь перетасовывайте каждый из массивов p самостоятельно (на самом деле вы можете оставить один массив неповрежденным, если хотите). Затем для каждого индекса i возьмите тип выбранного элемента как комбинацию из перетасованного массива p с индексом i и выберите один из таких типов случайным образом из оставшихся в исходной группе, удалив выбранный элемент. Если элементов этого типа не осталось, алгоритм потерпел неудачу, поэтому перетасовать массивы и начать снова выбирать элементы.

Чтобы использовать это, вам необходимо сначала убедиться, что условия выполняются вообще, потому что в противном случае он будет просто контур бесконечно. Честно говоря, я не вижу простого способа проверить, что условия являются выполнимыми, но если количество элементов в ваших исходных данных велико по сравнению с k, и их распределение не слишком искажено, должны быть решения , Кроме того, если есть только несколько способов, в которых условия могут быть удовлетворены, может потребоваться много времени, чтобы найти их; хотя метод завершится с вероятностью 1, нет верхней границы, которую вы можете разместить на время выполнения.

Answer 5

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

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

Метод:

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

Для этого вы будете рассматривать каждое из своих правил столбцов (например, 40% мужчин, 60% женщин) в качестве отдельной цели (например, при желаемом размере подмножества 100, которое вы ищете 40 мужчин, 60 женщин). Сделайте счетчик для каждого.

Затем вы зацикливаете до тех пор, пока вы не создадите подмножество, или вы не проверили все строки в юниверсе выборки, не найдя соответствия (см. Ниже, что происходит тогда). Это петля в псевдокоде:

- Randomly select a row. 
- Mark the row examined. 
- For each column constraint: 
    * Get the value for the relevant column from the row 
    * Test for selectability: 
     If there's a value target for the value, 
     and if we haven't already selected our target number of incidences of this value, 
     then the row is selectable with respect to this column 
    * Else: the row fails. 
- If the row didn't fail, select it: add it to the subset 

В этом суть. Он предоставит подмножество, которое соответствует вашим правилам, или оно не сможет этого сделать ..., что подводит меня к тому, что происходит, когда мы не можем найти матч .

невыполнимости:

Как уже отмечалось, это не всегда возможно удовлетворить любой произвольный набор правил для произвольной выборки вселенной. Даже если предположить, что правила действительны (проценты для каждой суммы значений равны 100), размер подмножества меньше размера юниверса, а юниверс содержит достаточно людей с каждым выбранным значением для достижения целей, все равно можно сбой, если значения фактически не распределяются независимо.

Рассмотрите случай, когда все самцы в выборной вселенной являются австралийскими: в этом случае вы можете выбрать только столько мужчин, сколько сможете выбрать австралийцев, и наоборот. Таким образом, набор ограничений (размер подмножества: 100, мужчина: 40%, австралийский 10%) не может быть удовлетворен вообще из такой вселенной, даже если все австралийцы, которых мы выбираем, являются мужчинами.

Если мы сменим ограничения (размер подмножества: 100; мужчина: 40%, австралийский 40%), теперь мы можем создать соответствующее подмножество, но все австралийцы, которых мы выбираем, должны быть мужчинами. И если мы снова изменим ограничения (размер подмножества: 100, мужчина: 20%, австралийский 40%), теперь мы можем сделать соответствующее подмножество, но только если мы не заберем слишком много австралийских женщин (не более половины Это дело).

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

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

Пригодность

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

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

Но для ответа на вопрос о том, возможно ли сформировать подмножество, этот метод является недетерминированным и неэффективным. Было бы лучше использовать один из более сложных алгоритмов shuffle-and-sort, предложенных другими.

Pre-Validation:

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

Мое положение состоит в том, что, кроме первоначальной проверки правильности каждого из правил столбца (т. Е. Сумма процентов столбцов равна 100 или почти достаточно) и что размер подмножества меньше размера юниверса, валидация, которую стоит делать. Можно сделать аргумент, что вы можете проверить, что юниверс содержит достаточно людей с каждым выбранным значением (например, на самом деле на самом деле 40 мужчин и 60 женщин во вселенной), но я этого не реализовал.

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

Не совсем проблема подмножество сумма

Было высказано предположение, что эта проблема как subset sum problem. Я утверждаю, что это тонко и все же значительно отличается. Мое рассуждение таково: для проблемы суммы подмножества вы должны сформировать и протестировать подмножество, чтобы ответить на вопрос о том, соответствует ли оно правилам: невозможно (за исключением некоторых краевых условий) проверить отдельный элемент перед добавлением это подмножество.

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