logo标签列表

从数据中删除行：重叠的时间间隔？

pythonperlrpowershell
6

编辑：我现在正在寻找其他编程语言的解决方案。

根据我提出的另一个问题，我有一个像这样的数据集（对于R用户，下面是dput），它表示用户计算机会话：

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 09:44:18 2011-01-03 09:47:27
2     user1 D5599.domain.com 2011-01-03 09:46:29 2011-01-03 10:09:16
3     user1 D5599.domain.com 2011-01-03 14:07:36 2011-01-03 14:56:17
4     user1 D5599.domain.com 2011-01-05 15:03:17 2011-01-05 15:23:15
5     user1 D5599.domain.com 2011-02-14 14:33:39 2011-02-14 14:40:16
6     user1 D5599.domain.com 2011-02-23 13:54:30 2011-02-23 13:58:23
7     user1 D5599.domain.com 2011-03-21 10:10:18 2011-03-21 10:32:22
8     user1 D5645.domain.com 2011-06-09 10:12:41 2011-06-09 10:58:59
9     user1 D5682.domain.com 2011-01-03 12:03:45 2011-01-03 12:29:43
10    USER2 D5682.domain.com 2011-01-12 14:26:05 2011-01-12 14:32:53
11    USER2 D5682.domain.com 2011-01-17 15:06:19 2011-01-17 15:44:22
12    USER2 D5682.domain.com 2011-01-18 15:07:30 2011-01-18 15:42:43
13    USER2 D5682.domain.com 2011-01-25 15:20:55 2011-01-25 15:24:38
14    USER2 D5682.domain.com 2011-02-14 15:03:00 2011-02-14 15:07:43
15    USER2 D5682.domain.com 2011-02-14 14:59:23 2011-02-14 15:14:47
>

同一用户名在同一台计算机上可能有多个并发会话（基于时间重叠）。我该如何删除这些行，以便只留下一个会话的数据？原始数据集约有500,000行。

预期输出结果为（第2行和第15行已被删除）

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 09:44:18 2011-01-03 09:47:27
3     user1 D5599.domain.com 2011-01-03 14:07:36 2011-01-03 14:56:17
4     user1 D5599.domain.com 2011-01-05 15:03:17 2011-01-05 15:23:15
5     user1 D5599.domain.com 2011-02-14 14:33:39 2011-02-14 14:40:16
6     user1 D5599.domain.com 2011-02-23 13:54:30 2011-02-23 13:58:23
7     user1 D5599.domain.com 2011-03-21 10:10:18 2011-03-21 10:32:22
8     user1 D5645.domain.com 2011-06-09 10:12:41 2011-06-09 10:58:59
9     user1 D5682.domain.com 2011-01-03 12:03:45 2011-01-03 12:29:43
10    USER2 D5682.domain.com 2011-01-12 14:26:05 2011-01-12 14:32:53
11    USER2 D5682.domain.com 2011-01-17 15:06:19 2011-01-17 15:44:22
12    USER2 D5682.domain.com 2011-01-18 15:07:30 2011-01-18 15:42:43
13    USER2 D5682.domain.com 2011-01-25 15:20:55 2011-01-25 15:24:38
14    USER2 D5682.domain.com 2011-02-14 15:03:00 2011-02-14 15:07:43
>

以下是数据集：

structure(list(username = c("user1", "user1", "user1",
"user1", "user1", "user1", "user1", "user1",
"user1", "USER2", "USER2", "USER2", "USER2", "USER2", "USER2"
), machine = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 3L,
3L, 3L, 3L, 3L, 3L, 3L), .Label = c("D5599.domain.com", "D5645.domain.com",
"D5682.domain.com", "D5686.domain.com", "D5694.domain.com", "D5696.domain.com",
"D5772.domain.com", "D5772.domain.com", "D5847.domain.com", "D5855.domain.com",
"D5871.domain.com", "D5927.domain.com", "D5927.domain.com", "D5952.domain.com",
"D5993.domain.com", "D6012.domain.com", "D6048.domain.com", "D6077.domain.com",
"D5688.domain.com", "D5815.domain.com", "D6106.domain.com", "D6128.domain.com"
), class = "factor"), start = structure(c(1294040658, 1294040789,
1294056456, 1294232597, 1297686819, 1298462070, 1300695018, 1307603561,
1294049025, 1294835165, 1295269579, 1295356050, 1295961655, 1297688580,
1297688363), class = c("POSIXct", "POSIXt"), tzone = ""), end =
structure(c(1294040847,
1294042156, 1294059377, 1294233795, 1297687216, 1298462303, 1300696342,
1307606339, 1294050583, 1294835573, 1295271862, 1295358163, 1295961878,
1297688863, 1297689287), class = c("POSIXct", "POSIXt"), tzone = "")),
.Names = c("username",
"machine", "start", "end"), row.names = c(NA, 15L), class = "data.frame")
5个回答
4
尝试使用intervals软件包：

intervals软件包：

library(intervals)

f <- function(dd) with(dd, {
    r <- reduce(Intervals(cbind(start, end)))
    data.frame(username = username[1],
         machine = machine[1],
         start = structure(r[, 1], class = class(start)),
         end = structure(r[, 2], class = class(end)))
})

do.call("rbind", by(d, d[1:2], f))

通过使用示例数据，将原始数据框中的15行缩减为以下13行（通过合并原始数据框中的第1行和第2行以及第12行和第13行）：

   username          machine               start                 end
1     user1 D5599.domain.com 2011-01-03 02:44:18 2011-01-03 03:09:16
2     user1 D5599.domain.com 2011-01-03 07:07:36 2011-01-03 07:56:17
3     user1 D5599.domain.com 2011-01-05 08:03:17 2011-01-05 08:23:15
4     user1 D5599.domain.com 2011-02-14 07:33:39 2011-02-14 07:40:16
5     user1 D5599.domain.com 2011-02-23 06:54:30 2011-02-23 06:58:23
6     user1 D5599.domain.com 2011-03-21 04:10:18 2011-03-21 04:32:22
7     user1 D5645.domain.com 2011-06-09 03:12:41 2011-06-09 03:58:59
8     user1 D5682.domain.com 2011-01-03 05:03:45 2011-01-03 05:29:43
9     USER2 D5682.domain.com 2011-01-12 07:26:05 2011-01-12 07:32:53
10    USER2 D5682.domain.com 2011-01-17 08:06:19 2011-01-17 08:44:22
11    USER2 D5682.domain.com 2011-01-18 08:07:30 2011-01-18 08:42:43
12    USER2 D5682.domain.com 2011-01-25 08:20:55 2011-01-25 08:24:38
13    USER2 D5682.domain.com 2011-02-14 07:59:23 2011-02-14 08:14:47
谢谢，这似乎是我想要的！我需要检查一下这是否对我的原始数据框（有 500,000 行）足够高效。 - jrara
如果可以的话，我会给你+100分！由于超出了我的计算机内存，我无法在主数据中完成这项工作，但是我使用了较小的数据子集（一个月）来完成它。对我来说这已经足够了。 - jrara
1
一个解决方案是首先分割区间，使它们有时相等但从不部分重叠，然后删除重复项。 问题在于我们留下了许多小的相邻区间，将它们合并看起来并不直观。
library(reshape2)
library(sqldf)
d$machine <- as.character( d$machine ) # Duplicated levels...
ddply( d, c("username", "machine"), function (u) {
  # For each username and machine, 
  # compute all the possible non-overlapping intervals
  intervals <- sort(unique( c(u$start, u$end) ))
  intervals <- data.frame( 
    start = intervals[-length(intervals)], 
    end   = intervals[-1] 
  )
  # Only retain those actually in the data
  u <- sqldf( "
    SELECT DISTINCT u.username, u.machine, 
                    intervals.start, intervals.end
    FROM  u, intervals 
    WHERE       u.start <= intervals.start 
    AND   intervals.end <=         u.end
  " )
  # We have non-overlapping, but potentially abutting intervals:
  # ideally, we should merge them, but I do not see an easy 
  # way to do so.
  u
} )

编辑： 另一个在概念上更清晰的解决方案，可以解决未合并相邻间隔的问题，就是计算每个用户和机器的开放会话数：当它不再为零时，用户已登录（具有一个或多个会话），当它降至零时，用户已关闭所有他/她的会话。

ddply( d, c("username", "machine"), function (u) {
  a <- rbind( 
    data.frame( time = min(u$start) - 1, sessions = 0 ),
    data.frame( time = u$start, sessions = 1 ), 
    data.frame( time = u$end,   sessions = -1 ) 
  )
  a <- a[ order(a$time), ]
  a$sessions <- cumsum(a$sessions)
  a$previous <- c( 0, a$sessions[ - nrow(a) ] )
  a <- a[ a$previous == 0 & a$sessions  > 0 | 
          a$previous  > 0 & a$sessions == 0, ]
  a$previous_time <- a$time
  a$previous_time[-1] <- a$time[ -nrow(a) ]
  a <- a[ a$previous > 0 & a$sessions == 0, ]
  a <- data.frame( 
    username = u$username[1],
    machine  = u$machine[1],
    start = a$previous_time,
    end   = a$time
  )
  a
} )
感谢您的贡献。这似乎是添加行而不是删除它们。这似乎是一个相当困难的任务要解决。 - jrara
如果一个用户在同一台机器上有两个会话，比如从08:00到10:00和从09:00到12:00，那么这些重叠的时间段将被分成08:00到09:00、09:00到10:00和10:00到12:00。没有更多的重叠时间段，也没有重复的时间段，但由于时间段被切成了更小的片段，所以它们的数量更多。当它们相接时（在这里，合并为单个时间段09:00到12:00）看起来更难。 - Vincent Zoonekynd
我不确定我是否理解你的意思。我的想法是删除那些在数据中与同一台计算机的用户存在重叠时间间隔的行（除了其中的一行）。例如，如果我有时间间隔8:30到9:30和8:45到10:00，则应删除8:45到10:00，因为它在数据中有一个重叠的时间间隔行。 - jrara
我在我的问题中添加了预期输出。 - jrara
我已经找到了一种合并时间间隔的方法，并编辑了我的答案。如果你真的想只保留第一个连接并丢弃其他连接（不知何故，我不喜欢丢弃数据），你可以在“用户名”、“机器”和“开始”列上将结果与初始数据连接起来，以获取第一个会话的结束时间而不是最后一个。 - Vincent Zoonekynd
谢谢，是的，在这种情况下我想要删除那些行，我的想法只是获取用户计数，因此如果用户有多个会话打开，只需丢弃那些会话并计算一个会话。我的原始数据框有500,000行。 - jrara
1

使用 lubridate 中的 interval 类的备选解决方案。

library(lubridate)
int <- with(d, new_interval(start, end))

现在我们需要一个函数来测试重叠。请参见确定两个日期范围是否重叠。
int_overlaps <- function(int1, int2)
{
  (int_start(int1) <= int_end(int2)) & 
  (int_start(int2) <= int_end(int1))
}

现在对所有区间对调用此函数。

index <- combn(seq_along(int), 2)
overlaps <- int_overlaps(int[index[1, ]], int[index[2, ]])

重叠的行：

int[index[1, overlaps]]
int[index[2, overlaps]]

需要删除的行只是 index[2, overlaps]。

谢谢，它在示例数据中完美运行。但是在我的原始数据中，我遇到了一个错误：> index <- combn(seq_along(int), 2) 错误信息为：Error in matrix(r, nrow = len.r, ncol = count) : invalid 'ncol' value (too large or NA)。此外，还有一个警告信息：In combn(seq_along(int), 2) : NAs introduced by coercion。我猜我的数据集太大了？ - jrara
@jrara：没错，回头看来，使用combn是完全过度的，由于内存使用，这并不是一个好主意。你仍然可以使用lubridate间隔，但请尝试使用Hobb答案中的算法。 - Richie Cotton
1

不知道这是否符合您的要求，或者它是否比您已经拥有的更好。这是一个使用哈希表的PowerShell解决方案，其键是用户名和计算机名的组合。值是开始和结束时间的哈希。

如果一个键（会话）已经存在，则更新结束时间。如果不存在，则创建一个并设置开始时间和初始结束时间。当它在日志中遇到该用户/计算机的新会话记录时，它会更新会话键的结束时间。

 $ht = @{}
 import-csv <logfile> |
    foreach{
      $key = $_.username + $_.computername
      if ($ht.ContainsKey($key)){$ht.$key.end = $_.end}
      else{$ht.add("$key",@{start=$_.start;end=$_.end}}
       }

完成后，您需要从键中分离出用户和计算机名称。

1

伪代码解决方案：O(n log n)，如果数据已经按正确顺序排序，则为O(n)。

首先按用户、机器和开始时间对数据进行排序（这样给定用户在给定机器上的所有行都会被分组在一起，并且每个组内的行按开始时间升序排列）。

  1. 将“工作区间”初始化为null/nil/undef/etc。

  2. 对于每个按顺序的行：

    • 如果工作区间存在并且属于与当前行不同的用户或不同的机器，则输出并清除工作区间。
    • 如果工作区间存在并且其结束时间严格早于当前行的开始时间，则输出并清除工作区间。
    • 如果工作区间存在，则它必须属于相同的用户和机器，并且与当前行的区间重叠或相邻，因此将工作区间的结束时间设置为当前行的结束时间。
    • 否则，工作区间不存在，因此将工作区间设置为当前行。

  3. 最后，如果工作区间存在，则输出它。

简单且不与特定编程语言相关。我认为order/group by应该是按用户和机器排序/分组。 - runrig
哎呀，我完全忘记了“机器”这个词。同样的想法适用于任何额外的字段。 - hobbs
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接