One-sided Median

Local Algorithm - One-Dimensional Algorithm

One-sided Median algorithm computes the median

\[m_n^Y = \text{Median}\{Y_{n-2k}, \ldots, Y_{n-1}\}\]

and the median

\[m_n^Z = \text{Median}\{Z_{n-2k}, \ldots, Z_{n-1}\}\]

with

\[Z_n = Y_n - Y_{n-1}.\]

\(2k\) is the size of the neighborhood window. Defining

\[\hat{m}_n = m_n^Y + k m_n^Z \, \text{,}\]

\(Y_n\) is treated as a value outside the region of interest if \(|Y_n - \hat{m}_n| \geq \tau\).

Input Parameters

Parameter	Type	Constraint	Description	Remarks
\(Y\)	\(Y \in \mathbb R^N\)	\(N \in \mathbb{N}\)	Input data sequence of length \(N\)
\(\tau\)	\(\tau \in \mathbb R^+\)		User-specified threshold

Output Parameters

Parameter	Type	Constraint	Description	Remarks
\(\hat{Y}\)	\(\hat{Y} \in \mathbb R^N\)		Values in the \(Y\) list which are outside the region of interest are marked

Single Steps using the Algorithm

• Outlier Detection with One-sided Median

References

• S. Basu, M. Meckesheimer, Automatic outlier detection for time series: an application to sensor data, Knowledge and Information Systems, vol. 11, Issue 2, pp 137-154, 2007.