packages feed

kenshou-diagnose-0.1.0.0: src/Kenshou/Diagnose/Stats.hs

module Kenshou.Diagnose.Stats
  ( SlopeEstimate (..),
    theilSen,
    slopeWithInterval,
    windowMinima,
    windowMedians,
  )
where

import Data.List (sort)
import Data.Vector (Vector)
import Data.Vector qualified as Vector
import Data.Word (Word64)
import System.Random.SplitMix (SMGen, mkSMGen, nextWord64)

data SlopeEstimate = SlopeEstimate
  { slope :: !Double,
    intercept :: !Double,
    low :: !Double,
    high :: !Double,
    points :: !Int,
    resamples :: !Int,
    blockLength :: !Int
  }
  deriving stock (Eq, Show)

theilSen :: Vector (Double, Double) -> Maybe (Double, Double)
theilSen original
  | Vector.length samples < 2 = Nothing
  | null slopes = Nothing
  | otherwise = Just (estimate, median [y - estimate * x | (x, y) <- Vector.toList samples])
  where
    samples = capPoints original
    indexed = Vector.toList (Vector.indexed samples)
    slopes =
      [ (y2 - y1) / (x2 - x1)
      | (index, (x1, y1)) <- indexed,
        (_, (x2, y2)) <- drop (index + 1) indexed,
        x2 /= x1
      ]
    estimate = median slopes

slopeWithInterval :: Word64 -> Int -> Double -> Vector (Double, Double) -> Maybe SlopeEstimate
slopeWithInterval seed requested confidence values = do
  (estimate, intercept) <- theilSen values
  let count = Vector.length values
      block = max 1 (ceiling (sqrt (fromIntegral count :: Double)))
      iterations = max 1 requested
      residuals = Vector.map (\(x, y) -> (x, y - (estimate * x + intercept))) values
      estimates = take iterations (bootstrapSlopes block estimate intercept residuals (mkSMGen seed))
      alpha = max 0 (min 0.5 ((1 - confidence) / 2))
  pure
    SlopeEstimate
      { slope = estimate,
        intercept,
        low = quantile alpha estimates,
        high = quantile (1 - alpha) estimates,
        points = count,
        resamples = iterations,
        blockLength = block
      }

windowMinima :: Double -> Vector (Double, Double) -> Vector (Double, Double)
windowMinima width = windowBy width minimumPoint
  where
    minimumPoint values = minimumByValue values

windowMedians :: Double -> Vector (Double, Double) -> Vector (Double, Double)
windowMedians width = windowBy width medianPoint
  where
    medianPoint values =
      let ordered = sortOnValue values
       in ordered !! ((length ordered - 1) `div` 2)

windowBy :: Double -> ([(Double, Double)] -> (Double, Double)) -> Vector (Double, Double) -> Vector (Double, Double)
windowBy width choose values
  | width <= 0 = values
  | Vector.null values = Vector.empty
  | otherwise = Vector.fromList (fmap choose (groups (Vector.toList values)))
  where
    origin = fst (Vector.head values)
    bucket (time, _) = floor ((time - origin) / width) :: Int
    groups [] = []
    groups (first : rest) =
      let key = bucket first
          (same, remaining) = span ((== key) . bucket) rest
       in (first : same) : groups remaining

capPoints :: Vector (Double, Double) -> Vector (Double, Double)
capPoints values
  | Vector.length values <= 2000 = values
  | otherwise =
      let width = fromIntegral (Vector.length values) / 2000 :: Double
          groups = chunk (ceiling width) (Vector.toList values)
       in Vector.fromList (fmap medianPoint groups)
  where
    medianPoint group = sortOnValue group !! ((length group - 1) `div` 2)

bootstrapSlopes :: Int -> Double -> Double -> Vector (Double, Double) -> SMGen -> [Double]
bootstrapSlopes _ _ _ values _ | Vector.length values < 2 = []
bootstrapSlopes block baseEstimate intercept values generator =
  let (sampledResiduals, next) = movingBlockSample block values generator
      sample = Vector.map (\(x, residual) -> (x, baseEstimate * x + intercept + residual)) sampledResiduals
      bootstrapEstimate = maybe 0 fst (theilSen sample)
   in bootstrapEstimate : bootstrapSlopes block baseEstimate intercept values next

movingBlockSample :: Int -> Vector (Double, Double) -> SMGen -> (Vector (Double, Double), SMGen)
movingBlockSample block values initial =
  let count = Vector.length values
      blockCount = ceiling (fromIntegral count / fromIntegral block :: Double)
      (starts, final) = drawStarts blockCount count initial []
      sampledY = take count [snd (values Vector.! ((start + offset) `mod` count)) | start <- starts, offset <- [0 .. block - 1]]
      sampledX = fmap fst (Vector.toList values)
   in (Vector.fromList (zip sampledX sampledY), final)

drawStarts :: Int -> Int -> SMGen -> [Int] -> ([Int], SMGen)
drawStarts 0 _ generator accumulated = (reverse accumulated, generator)
drawStarts remaining count generator accumulated =
  let (word, next) = nextWord64 generator
      start = fromIntegral (word `mod` fromIntegral count)
   in drawStarts (remaining - 1) count next (start : accumulated)

quantile :: Double -> [Double] -> Double
quantile _ [] = 0
quantile fraction values =
  let ordered = sort values
      position = max 0 (min 1 fraction) * fromIntegral (length ordered - 1)
      lowerIndex = floor position
      upperIndex = ceiling position
      weight = position - fromIntegral lowerIndex
   in ordered !! lowerIndex * (1 - weight) + ordered !! upperIndex * weight

median :: [Double] -> Double
median = quantile 0.5

minimumByValue :: [(Double, Double)] -> (Double, Double)
minimumByValue = foldl1 \left@(_, leftValue) right@(_, rightValue) -> if rightValue < leftValue then right else left

sortOnValue :: [(Double, Double)] -> [(Double, Double)]
sortOnValue = sortByValue

sortByValue :: [(Double, Double)] -> [(Double, Double)]
sortByValue [] = []
sortByValue (pivot@(_, pivotValue) : rest) =
  sortByValue [value | value@(_, item) <- rest, item <= pivotValue]
    <> [pivot]
    <> sortByValue [value | value@(_, item) <- rest, item > pivotValue]

chunk :: Int -> [value] -> [[value]]
chunk _ [] = []
chunk size values = let (prefix, suffix) = splitAt (max 1 size) values in prefix : chunk size suffix