流式动态数据二分采样咨询：无预估值下的大小值划分及学习方向

Hey there! Let's work through your problem together.

Your task falls squarely into streaming data processing—specifically, it's about dynamic threshold partitioning or online two-clustering for streaming datasets. It also ties into areas like approximate algorithms and online order statistics, since you can't store all data upfront and need real-time, memory-efficient solutions.

Here are practical approaches tailored to your streaming scenario:

• Online Quantile Estimation (e.g., Greenwald-Khanna Algorithm)
  This is perfect for your use case because it lets you estimate percentiles (like the median, which is the 50th percentile) on the fly without keeping all data. For your first example, the median of [1,1,1,2,2,100] is 1.5, but since 100 is a clear outlier, you could adjust to use a higher percentile (like the 90th) to isolate it. The G-K algorithm maintains a small, compressed representation of the data stream to give you approximate percentiles with a guaranteed error bound—ideal for streaming.

• Sliding Window-Based Thresholding
  If your data distribution might shift over time (e.g., later data points are consistently larger than early ones), using a sliding window keeps you focused on recent data. Compute the median or percentile within the window (say, the last 50 data points) and update your threshold dynamically. This adapts to changes in the data stream.

• Streaming Outlier Detection
  For cases where one set is mostly normal values and the other is outliers (like your first example with 100), use streaming outlier detection methods:

  • Streaming Isolation Forest: A version of the popular isolation forest adapted for streaming data, which quickly identifies anomalies that are "isolated" from the rest.
  • Online 3σ Rule: Use Welford's algorithm to compute the mean and variance of the stream in real time. Any value outside mean ± 3*standard deviation gets flagged as an outlier and sent to set 2.

• Streaming Two-Clustering
  If your data naturally forms two distinct groups (like your second example [1,2,3,4,4]), initialize two cluster centers. For each new data point, assign it to the cluster whose center is closer, then update the center (e.g., using a moving average to avoid sudden jumps). This works well when the two groups have clear separation.

• Start with the basics of streaming data processing: Understand core constraints (limited memory, infinite data, real-time processing) and how it differs from batch processing.
• Learn online statistical computations: Master algorithms like Welford's (for mean/variance) and Greenwald-Khanna (for percentiles)—these are building blocks for most streaming solutions.
• Dive into streaming clustering and outlier detection: Start with simple two-clustering implementations, then explore more advanced methods. You can use libraries like river (previously creme) in Python to experiment with pre-built streaming algorithms quickly.
• Practice with small test cases: Try implementing a basic sliding window median or G-K algorithm on your example datasets to see how they perform.

内容的提问来源于stack exchange，提问作者Faisal Bahadur