Группировка людей в семьи

Question

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

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

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

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

Для справки, меня устраивают главы 1-26 CLRS , но я не особо коснулся алгоритмов NP-полноты или аппроксимации.Не то чтобы вам не нужно поднимать эти темы, но если вы это сделаете, возможно, будьте осторожны со мной, потому что я, вероятно, не пойму все, о чем вы говорите, сразу.:) Я также ничего не знаю об эволюционных алгоритмах.

Редактировать: Я специально стремлюсь улучшить следующее:

1. Менее нелепые браки.
2. Меньше одиноких людей в конце.

Answer 1

Давайте попробуем подумать о вашей проблеме следующим образом (начиная с поиска соответствия супругов):
Если бы у вас была матрица, в которой каждая строка - это мужчина, а каждый столбец - женщина, а каждая ячейка в этой матрице - это возвращаемое значение функции сопоставления, то теперь вам нужно выбрать ячейки, чтобы не было строка или столбец, в котором выбрано более одной ячейки, а общая сумма всех выделенных ячеек должна быть максимальной. Это очень похоже на N проблему ферзей , с модификацией, согласно которой каждое выделение «ферзя» имеет награду (которую мы должны максимизировать).
Вы можете решить эту проблему, используя график где:
У вас есть рут,
каждое из значений первых необработанных ячеек является весом ребра, ведущим к первым вершинам глубины
каждое из значений ячеек второго необработанного кода является весом ребра, ведущим к вершинам второй глубины.
И т.д.
(Обратите внимание, что когда вы находите совпадение с первой женщиной, вы не должны больше ее рассматривать, и поэтому для каждой другой женщины, с которой вы находите совпадение) Тогда определение максимального распределения может быть выполнено с помощью BFS или, что еще лучше, с помощью A * (обратите внимание, что A * обычно ищет минимальная стоимость , поэтому вы получите изменить его немного).

Для соответствия между парами (или одиночками, подробнее об этом позже ...) и детьми, я думаю, KNN с некоторыми изменениями - ваш лучший выбор, но вам нужно оптимизировать его под свои нужды. Но теперь я должен относиться к вашему редактированию ..
Как вы оцениваете эффективность вашего алгоритма?
Вам нужна функция, которая получает ожидаемое распределение всех состояний (не замужем, замужем с одним ребенком, не замужем с двумя детьми и т. Д.), А также распределение всех состояний в вашем решении и соответствующим образом оценивает решение. , Как вы рассчитываете ожидаемое распределение? Это совсем немного статистики работы ..
Во-первых, вам нужно знать распределение всех штатов (одиноких, женатых, как указано выше) среди населения,
тогда вам нужно знать распределение возрастов и полов в популяции,
и последнее, что вам нужно знать, - распределение возрастов и полов в вашем населении. Только тогда, согласно этим трем, вы можете подсчитать, сколько людей вы ожидаете быть в каждом штате .. И затем вы можете измерить расстояние между тем, что вы ожидали, и тем, что вы получили ... Это много печатать .. Извините для общих частей ...

Answer 2

Возможно, вы ищете кластерный анализ ?