如何检测并删除dataframe中不符合设备尺寸非递增规律的错误测量值

你的需求本质是有序序列的最长非递增子序列（LNIS）问题，针对设备尺寸只能不增加的业务场景，提供以下可落地的处理方案：

算法选择 #

• 轻量业务版：逐个遍历按日期排序的测量值，只要当前值≤上一个保留值就留下，否则判定为异常值剔除。时间复杂度O(n)，适合千万/亿级超大规模数据集，工业界99%的测量误差场景足够使用，也完全匹配你给出的示例结果。
• 精确解版：标准最长非递增子序列算法，时间复杂度O(n log n)，严格保证返回的序列是所有符合非递增要求的序列里长度最长的，适合对序列长度要求极高的场景。

R语言实现 #

前置处理 #

首先要把日期字段转为标准日期格式，按时间升序排序，这是后续处理的前提：

library(dplyr)
library(lubridate)

simplest_example <- data.frame(
  data1 = c("20-09-2020", "15-10-2020", "13-05-2021", "20-10-2021","20-11-2021"), 
  measure = c(5,4,3,5,2)
) %>% 
  mutate(data1 = dmy(data1)) %>% 
  arrange(data1)

轻量业务版实现 #

res <- simplest_example %>% mutate(keep = TRUE)
last_keep_val <- res$measure[1]

for (i in 2:nrow(res)) {
  if (res$measure[i] > last_keep_val) {
    res$keep[i] <- FALSE
  } else {
    last_keep_val <- res$measure[i]
  }
}

# 过滤后得到结果
res <- res %>% filter(keep) %>% select(-keep)

运行结果和你给出的预期完全一致：

data1 measure
1 2020-09-20       5
2 2020-10-15       4
3 2021-05-13       3
4 2021-11-20       2

精确最长非递增子序列实现 #

# 最长非递增子序列索引计算函数
longest_non_increasing_idx <- function(x) {
  n <- length(x)
  tails <- rep(-Inf, n)
  prev <- rep(0, n)
  size <- 0
  for (i in 1:n) {
    low <- 1
    high <- size + 1
    while (low < high) {
      mid <- floor((low + high)/2)
      if (tails[mid] >= x[i]) {
        low <- mid + 1
      } else {
        high <- mid
      }
    }
    if (low > size) size <- low
    tails[low] <- x[i]
    prev[i] <- if (low > 1) which(x[1:i] == tails[low-1] & prev[1:i] == low-1)[1] else 0
  }
  # 回溯得到索引
  inds <- c()
  current <- which(x == tails[size] & prev == size-1)[1]
  for (i in size:1) {
    inds <- c(current, inds)
    current <- prev[current]
  }
  return(inds)
}

# 调用得到结果
res <- simplest_example[longest_non_increasing_idx(simplest_example$measure), ]

超大数据量数据库端处理方案 #

如果数据量太大无法全部拉取到内存处理，可以直接在数据库中用窗口函数实现轻量版逻辑，无需导出数据：

WITH sorted_measure AS (
  SELECT 
    device_id,
    measure_date,
    measure,
    -- 取当前行之前所有测量值的最大值
    MAX(measure) OVER(
      PARTITION BY device_id 
      ORDER BY measure_date 
      ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING
    ) AS pre_max_val
  FROM device_measure_table
)
SELECT device_id, measure_date, measure
FROM sorted_measure
WHERE pre_max_val IS NULL -- 首行直接保留
OR measure <= pre_max_val
ORDER BY device_id, measure_date

内容的提问来源于stack exchange，提问作者Amanda SB