Dataframe — выберите минимальный набор строк, чтобы охватить все возможные значения каждого столбца
Я работаю над вариантом использования, в котором мне нужно получить минимальную выборку строк из кадра данных, содержащего хотя бы одну строку для каждого уникального значения, найденного во всех столбцах.
Упрощенным примером может быть:
Здесь я хотел бы сохранить строки с идентификаторами 1, 4 и 5, чтобы иметь хотя бы одну строку со значениями D, E и F из A; G, H и I из B и X, Y и Z из C. Мне не нужны все комбинации, только все уникальные значения из каждого столбца:
Каким может быть эффективный способ сделать это?
Спасибо
(1) Это также необходимо будет включить: да, уникальность должна учитываться в каждом столбце. (2) Данные в настоящее время находятся в таблице sql, но я загрузил их в фрейм данных pandas, чтобы провести первое тестирование да
Возможно, я слишком много думаю об этом, но мне это представляется в первую очередь математической задачей, а уже потом — проблемой программирования. Я предполагаю, что проблему можно было бы переформулировать так: для данного набора S и n разделов S – P_1,…, P_n – выберите минимальное количество элементов из S так, чтобы для каждого подмножества в каждом P_i был выбран хотя бы один элемент. Здесь S — строки (т. е. каждый элемент является строкой), n — количество столбцов, а каждый P_i определяется уникальными значениями соответствующего столбца (строки с одинаковым значением в i-м столбце находятся в то же подмножество P_i). Не уверен, что это поможет.
В частности, я понятия не имею, как эффективно решить эту проблему, но, возможно, у кого-то есть. Возможно, было бы также неплохо сформулировать это как вопрос на Mathematics Stack Exchange.
Я надеялся, что, возможно, существует библиотека, предназначенная для выборки таких данных, но, возможно, этот случай немного специфичен. Спасибо за ваш вклад, я рассмотрю это с математической точки зрения.
Похоже, это тот случай, когда есть жадный алгоритм, дающий почти оптимальное решение, и алгоритм динамического программирования, дающий оптимальное решение.
Подумав еще немного об этом, я думаю, что прибегну к действительно приблизительному решению, упорядочив значения всех столбцов по частоте, выбрав случайную строку с наименее частой строкой и каждый раз циклически перебирая все значения. если мои уже выбранные строки содержат это значение, и если я не добавляю еще одну строку случайных чисел (пытаясь максимизировать содержащиеся в ней «новые» значения) с этим значением в мое подмножество
Ответы 2
вот минимальный пример, который поможет вам начать работу.
USING: # (tab separated !)
ID COLA COLB COLC COLD
1 D G X
2 D G K
3 E G M
4 E H L
5 F I Z L
6 O Z P
#this code
import pandas as pd
df = pd.read_csv('input1.csv', sep='\t')
# get the columns - skipping the first
# remove 'nan', then get unique values using 'set' sorted
for col in list(df)[1:]:
wk=[ member for member in df[col] if not(pd.isnull(member)) == True]
print(f'{col} {sorted(set(wk))}')
#produces
COLA ['D', 'E', 'F', 'O']
COLB ['G', 'H', 'I', 'Z']
COLC ['M', 'X', 'Z']
COLD ['K', 'L', 'P']
надеюсь, это чем-то поможет
Я не думаю, что проблема ОП заключается в поиске уникальных элементов каждого столбца. Вместо этого проблема состоит в том, чтобы найти минимальный набор строк, в котором будет охвачен каждый уникальный элемент каждого столбца. Таким образом, просмотра отдельных столбцов недостаточно.
@simon, возможно, вы правы, сообщение является/было двусмысленным, последнее предложение ... """ Мне не нужны все комбинации, только все уникальные значения из каждого столбца.""" - вот что подсказало мне это опубликовать, конечно, запрашивающий может проигнорировать, но спасибо за отзыв.
Как объяснил @simon, спасибо за попытку, извините, пост был немного двусмысленным.
@JojoDolo, np, поэтому, учитывая набор данных, которые вы опубликовали в своем вопросе, можете ли вы опубликовать, каким должен быть ожидаемый результирующий набор данных (в таблице, аналогичной вашему первоначальному сообщению) - спасибо, это поможет (по крайней мере, уточните для меня ) , кроме того, если вы нашли решение, опубликуйте этот код. спасибо
Это уже написано в вопросе: Здесь я хотел бы сохранить строки с идентификаторами 1, 4 и 5. Также указывается причина: иметь хотя бы одну строку со значениями D, E и F из A; G, H и I от B и X, Y и Z от C.
@simon, еще раз спасибо за ваш отзыв, однако мне все еще неясно (английский у меня не первый), отсюда и просьба. Опять же, если интерпретация... тогда объединение всех столбцов даст единый результат всех отдельных элементов во всех столбцах, тривиально: un=list( set(df.COLA) | set(df.COLB) | set(df .COLC) | set(df.COLD) ) un=[mbr для mbr в un if str(mbr) != 'nan'] print( sorted(un) ). опять же, если автор откликнется на мою просьбу... в противном случае я оставлю это в покое. спасибо
Английский также не является моим родным языком, поэтому извините, если мое объяснение не очень понятно. Я обновил свой пост с ожидаемым результатом. Чтобы прояснить, чего я пытаюсь достичь, я не хочу собирать все отдельные комбинации по всем столбцам (чего и достигнет ваш код), но я пытаюсь собрать подмножество строк, для которых каждое значение из каждого столбец появится хотя бы один раз. Допустим, у меня есть строки A, B, C; A, B, D и B, B, D, все три имеют разные комбинации, но если я выберу только A, B, C и B, B, D, будут выбраны все уникальные значения, и мне не нужны A, B, D. ряд.
Надеюсь, теперь это ясно. Я все еще работаю над своим решением (опубликовал очень приблизительный алгоритм в комментарии к другому ответу), я обязательно обновлю сообщение, если решение будет удовлетворительным.
@JojoDolo, НП, очевидно, я упускаю суть твоего поста, так что прошу прощения за потерянное время. к вашему сведению, запустите код с вашими входными данными, он даст ожидаемый результат, но сейчас я оставлю других, чтобы помочь.
Вот что у меня в итоге получилось:
- Подсчитайте количество вхождений каждого значения в каждом столбце и упорядочите их по возрастанию.
- Выберите случайную строку, содержащую наименее встречающееся значение из всех, и добавьте это значение и все остальные из выбранной строки в словарь.
- Просматривая мой упорядоченный список значений, подсчитайте количество «новых значений» для каждой строки, содержащей текущее значение списка, в котором находится цикл. Выберите строку с наибольшим количеством «новых значений».
- Повторяйте, пока не будут выбраны все значения.
Это далеко не оптимальное решение, поскольку я лишь минимизирую количество строк на каждом шаге, но оно довольно эффективно и выполняет свою работу. Вероятно, можно было бы использовать рекурсивный алгоритм для проверки всех решений, но у меня нет больших требований к окончательному набору строк, за исключением того, что для этого нужны все возможные значения.
Спасибо всем за участие, они помогли мне найти это решение.
Два вопроса: (1) Предполагая, что строка 3 будет (E, G, D), а не (E, G, Y), мне также нужно будет включить ее, даже если D уже появился в строке 1, потому что он не появился в строке 1. столбец C, это правильно? Или, альтернативно, могу ли я предположить, что значения уникальны в своих столбцах (т.е. значение D уникально для столбца A, поэтому не может появляться в столбце C)? (2) Хотя проблема носит скорее общий характер, и поэтому этот аспект менее важен, я предполагаю, что под «Dataframe» вы имеете в виду Pandas Dataframe?