Python 3: удалить наложения в таблице

Question

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

id   hit from   to value
A   hit1    56  102 0.00085
B   hit2    89  275 0.00034
B   hit3    240 349 0.00034
C   hit4    332 480 3.40E-15
D   hit5    291 512 3.80E-24
D   hit6    287 313 0.00098
D   hit7    381 426 0.00098
D   hit8    287 316 0.0029
D   hit9    373 422 0.0029
D   hit10   514 600 0.0021

Для каждого идентификатора df должен быть отсортирован по from и, если естьперекрывающиеся попадания, оставьте один с более низким value.

Пока что это мой код, который сначала выполняет from, а затем value:

import pandas
df = pandas.read_csv("table", sep='\s+', names=["id", "hit", "from", "to", "value"])
df.sort_values(['from', "value"]).groupby('id')

Но как я могу проверить перекрытие (from до to) и удалить одно с более высоким показателем?

Это мой ожидаемый результат:

id   hit from   to valu
A   hit1    56  102 0.00085
C   hit4    332 480 3.40E-15
D   hit5    291 512 3.80E-24
D   hit10   514 600 0.0021

Обратите внимание, что id B имеет два перекрывающихся попадания с одинаковым значением, поэтому обе записи должны быть исключены.

Answer 1

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

def strip(group):
    non_overlapping=[]
    overlapping = [list(group.itertuples())[0]]
    end = list(group.itertuples())[0].to
    for row in list(group.itertuples())[1:]:
        if row[3]<=end:
            overlapping.append(row)
            if row.to > end:
                end = row.to
        else:
            non_overlapping.append(reduce_overlap(overlapping))
            overlapping=[row]
    non_overlapping.append(reduce_overlap(overlapping))
    return non_overlapping

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

def reduce_overlap(overlapping):
    overlapping= sorted(overlapping,key=lambda x: x.value)
    if len(overlapping)==1 or overlapping[0].value != overlapping[1].value:
        return overlapping[0]
    else:
        return []

Чтобы найти возвращаемое значение, мы сортируем по значению, не возвращающему ничего, если случайно они имеют два одинаковых значения.

Редактировать: вот функция, которая применяет его ко всемукадр данных, который я не проверял.

def nonoverlapping(df):
  return df.Dataframe.from_records([strip(group) for name,group in df.sort_values(['from', "value"]).groupby('id')])

Answer 2

Сначала мы вводим уникальный ID и используем pd.Interval:

df['ID'] = range(df.shape[0])
df['Interval'] = df.apply(lambda x: pd.Interval(x['from'], x['to'], closed='both'), axis=1)

После этого мы присоединяем df к себе и вычисляем перекрывающиеся части:

columns = ['id', 'Interval', 'ID']
connected = df[columns].merge(df[columns], on='id')
connected['Overlap'] = connected.apply(lambda x: x['Interval_x'].overlaps(x['Interval_y']), axis=1) 
connected = connected.loc[connected['Overlap'] == True, ['id', 'ID_x', 'ID_y']]

Теперь мы знаем, какие идентификаторы перекрываются, но мы не знаем, какие из них создают связанный компонент.В общем, это не может быть сделано с помощью простого алгоритма, такого как повторное рендеринг, но немного теория графов помогает.Таким образом, мы строим график

graph = connected.groupby(['id', 'ID_x']).agg(list)

и вычисляем подключенные компоненты с помощью поиска в глубину

def connections(graph, id):
    def dict_to_df(d):
        df = pd.DataFrame(data=[d.keys(), d.values()], index=['ID', 'Subgraph']).T
        df['id'] = id
        return df[['id', 'Subgraph', 'ID']]

    def dfs(node, num):
        visited[node] = num
        for _node in graph.loc[node].iloc[0]:
            if _node not in visited:
                dfs(_node, num)

    visited = {}
    graph = graph.loc[id]
    for (num, node) in enumerate(graph.index):
        if node not in visited:
            dfs(node, num)

    return dict_to_df(visited)

dfs = []
for id in graph.index.get_level_values(0).unique():
    dfs.append(connections(graph, id))

conns = pd.concat(dfs)

conns удерживает подключенныекомпоненты, и мы можем собрать все вместе:

data = df.merge(conns[['Subgraph', 'ID']], on=['ID'])

Наша последняя задача - выбрать строки, которые мы хотим сохранить:

def select_min(x):
    m = x['value'].min()
    if len(x) > 1 and (x['value'] == m).all():
        return -1
    else:
        return x['value'].idxmin()

selected = data.groupby(['id', 'Subgraph'])['value', 'ID'].apply(select_min)
selected = selected[selected >= 0]

Теперь мы закончили:

print(df.loc[df.ID.isin(selected), :].drop(columns=['ID', 'Interval']))
  id    hit  from   to         value
0  A   hit1    56  102  8.500000e-04
3  C   hit4   332  480  3.400000e-15
4  D   hit5   291  512  3.800000e-24
9  D  hit10   514  600  2.100000e-03

Answer 3

Если вы не возражаете против нескольких строк в вашем коде, что-то вроде этого должно работать, я думаю ... (Python Newbie здесь ...) источник

df.sort_values(['from', "value"]).groupby('id')
df.drop_duplicates(subset=['id', 'value'], keep=False, inplace=True)

Параметр " keep " имеет значение false, потому что вы вообще не хотите дублировать строки.

Что приводит к:

  id    hit from   to     value
0  A   hit1   56  102   0.00085
3  C   hit4  332  480  3.40E-15
4  D   hit5  291  512  3.80E-24
9  D  hit10  514  600    0.0021

И избавиться от беспорядочного столбца индекса:

df.reset_index(drop=True, inplace=True)

Что приводит к:

  id    hit from   to     value
0  A   hit1   56  102   0.00085
1  C   hit4  332  480  3.40E-15
2  D   hit5  291  512  3.80E-24
3  D  hit10  514  600    0.0021

PS: Я впервые даю ответ, поэтому, пожалуйста, будьте осторожны.А еще я все еще учу английский.

Answer 4

df = pd.DataFrame({'id': ['A', 'B', 'B', 'C', 'D', 'D' ,'D', 'D', 'D', 'D', 'D'],
                  'hit': ['hit1', 'hit2', 'hit3','hit4', 'hit5','hit6', 'hit7','hit8', 'hit9','hit10', 'hit11'],
                  'from': [56,89,240,332,291,287,381,287,373,514, 599],
                  'to':[102,275,349,480,512,313,426,316,422,600, 602],
                  'value': [0.00085,0.00034,0.00034,3.40E-15,3.80E-24,0.00098,0.00098,0.0029,0.0029,0.0021, 0.002]})

overlapMask =  df.sort_values(by = 'from')\
                 .groupby('id')\
                 .apply(lambda x: np.where(x['from'] < x['to'].shift(), 0 , 1).cumsum())\
                 .reset_index()

df['Mask'] = np.concatenate((overlapMask[0].values))


df.drop_duplicates(subset = ['id','value'], keep = False, inplace = True)


df.sort_values(by = 'value')\
  .groupby(['id', 'Mask'])\
  .head(1)\
  .reset_index()\
  .drop(['Mask', 'index'],axis = 1)\
  .sort_values(by = 'id')


    id  hit    from  to    value
2   A   hit1    56  102 8.500000e-04
1   C   hit4    332 480 3.400000e-15
0   D   hit5    291 512 3.800000e-24
3   D   hit11   599 602 2.000000e-03

Так что мое решение использует маску для проверки перекрытия.Сортируя значения from и проверяя, является ли следующее значение from меньшим, чем предыдущее значение to.Np.inf должен просто убедиться, что первое значение всегда будет 0 в группе.

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

Answer 5

Если вы сортируете id == 'D'

    id  hit from    to  value
5   D   hit6    287 313 9.800000e-04
7   D   hit8    287 316 2.900000e-03
4   D   hit5    291 512 3.800000e-24
8   D   hit9    373 422 2.900000e-03
6   D   hit7    381 426 9.800000e-04
9   D   hit10   514 600 2.100000e-03

Перекрытие будет:

• попадание 6, 8 и 5 = сохранить 5 bc наименьшее значение

• хит 9 и 7 = kepp 7

• хит 10 один?