從數據中刪除行：重疊的時間間隔？

編輯：我正在尋找這個問題的解決方案現在也與其他編程語言。從數據中刪除行：重疊的時間間隔？

基於該other question I asked，我有一個這樣的數據集（對於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")

來源

2012-01-26 jrara

嘗試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

來源

2012-01-26 13:32:57

謝謝，這似乎是做我想要的！我將不得不檢查一下，如果這對我原始的data.frame來說足夠高效了，那麼就有500 000行。 – jrara

如果可以的話，我會給你+100！我沒有在我的主要數據中獲得這項工作，因爲它超出了我計算機的內存，但是我得到了它的一小部分數據（一個月）。沒關係對我來說。 – jrara

一種解決方案是第一分割間隔，使得它們有時相等，但從未部分重疊，並且他們刪除重複項。問題是，我們留下了許多小的鄰接間隔，合併它們看起來並不簡單。

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 
})

來源

2012-01-26 11:44:48

感謝您的貢獻。這似乎添加行，而不是刪除它們。這似乎是相當困難的任務來解決。 – 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之間的單個時間間隔）看起來更難。 –

我不確定我是否明白你的意思。我的想法是從具有重疊間隔的同一臺計算機中刪除用戶的行（除了其中一行）。例如，如果我的間隔時間爲8.30至9:30和8:45至10:00，則應刪除8:45至10:00，因爲它在數據中有一個重疊間隔行。 – jrara

使用interval類從lubridate備用溶液。

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

現在我們需要一個函數來測試重疊。請參閱Determine Whether Two Date Ranges Overlap。

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]。

來源

2012-01-26 14:02:17

謝謝，它與示例數據完美配合。用我的原始數據，我得到一個錯誤：> index < - combn（seq_along（int），2）矩陣錯誤（r，nrow = len.r，ncol = count）：無效'ncol'值NA）此外：警告消息：在combn（seq_along（int），2）中：強制引入NAs 我的數據集過於龐大嗎？ – jrara

@jrara：是的，回顧性地說，使用'combn'完全是矯枉過正，而不是一個好主意，因爲內存的使用。你仍然可以使用'lubridate'間隔，但在Hobb的答案中用算法嘗試它們。 –

僞代碼解：O（n log n），O（n）如果數據已知被正確排序。

首先按用戶，機器和開始時間對數據進行排序（以便給定計算機上給定用戶的所有行都組合在一起，並且每個組中的行都按照開始的升序排列時間）。

將「工作間隔」初始化爲null/nil/undef/etc。
對於每一行，以便：
- 如果工作間隔存在，並且屬於不同的用戶或不同的機器比當前行，輸出並清除工作間隔。
- 如果工作區間存在且其結束時間嚴格在當前行的開始時間之前，則輸出並清除工作區間。
- 如果工作間隔存在，則它必須屬於同一用戶和機器，並且與當前行的間隔重疊或鄰接，因此將工作間隔的結束時間設置爲當前行的結束時間。
- 否則，工作間隔不存在，所以將工作間隔設置爲當前行。
最後，如果工作區間存在，輸出它。

來源

2012-01-26 15:43:58 hobbs

簡單和語言不可知。雖然我認爲訂單/小組是由用戶和機器。 – runrig

哎呀，我完全錯過了「機器」。同樣的想法也適用，擴展到任何額外的領域。 – hobbs

不知道這是你所追求的還是不是，或者它會比你已有的更好。這是一個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}} 
     }

您將需要當它完成對用戶和計算機名稱背出鑰匙的分裂。

來源

2012-01-26 16:52:20 mjolinor

從數據中刪除行：重疊的時間間隔？

回答

相關問題