3
$\begingroup$

I just want to know if its possible to cluster an univariate time series, in order , say, to detect anomalies?

and do you have any online version for denstream code, in Matlab?


here is the time series

+0003;+0004;+0004;+0005;+0004;+0004;+0004;+0003;+0003;+0004;+0003;+0002;+0004;+0002;+0002;+0002;+0002;+0002;+0002;+0005;+0004;+0004;+0004;+0004;+0004;+0004;+0004;+0004;+0004;+0004;+0004;+0005;+0004;+0004;+0004;+0004;+0003;+0003;+0000;+0002;+0004;+0002;+0004;+0004;+0004;+0004;+0003;+0003;+0004;+0003;+0002;+0000;+0003;+0002;+0003;+0002;+0002;+0002;+0002;+0002;+0003;+0002;+0002;+0003;+0000;+0003;+0003;+0002;+0003;+0002;+0003;+0002;+0004;+0004;+0004;+0003;+0004;+0004;+0004;+0004;+0004;+0005;+0004;+0002;+0003;+0002;+0005;+0004;+0003;+0003;+0001;+0005;+0003;+0003;+0005;+0005;+0004;+0005;+0002;+0005;+0005;+0006;+0005;+0005;+0004;+0003;+0003;+0005;+0002;+0002;+0001;+0003;+0004;+0002;+0002;+0002;+0001;+0001;+0003;+0004;+0004;+0004;+0005;+0004;+0005;+0002;+0002;+0005;+0003;+0002;+0003;+0002;+0001;+0002;+0003;+0005;+0004;+0005;+0004;+0004;+0003;+0003;+0004;+0005;+0003;+0004;+0005;+0004;+0005;+0003;+0003;+0005;+0005;+0005;+0003;+0002;+0004;+0004;+0004;+0005;+0005;+0004;+0005;+0005;+0004;+0004;+0003;+0003;+0005;+0005;+0005;+0005;+0004


First you should now @IrishStat, that i should use a datamining technique for clustering, an exemple of times serie dataset is presented in this : picture

What i'm using now , is a density base clustering, let's said that I have adapte the Dbscan for streaming Time series points, and its Should detect anomalies, and changes eacht time,

after your introdudction , i'll trying to explain to u by pictures what i'm doing,

thanks u ,

time data series sample :

     [,1]
V1    3.0
V2    4.0
V3    4.5
V4    5.0
V5    4.0
V6    4.0
V7    4.4
V8    3.0
V9    3.0
V10   4.0
V11   3.0
V12   2.0
V13   4.0
V14   2.0
V15   2.0
V16   2.0
V17   2.0
V18   2.0
V19   2.0
..... so on 
$\endgroup$
7
$\begingroup$

I would approach this problem from a robust filtering point of view, as is done for real time curve monitoring. There is a German team that has worked extensively on this and related problems such as filtering, shift detection ect.. --see these papers here,here and here for example--

They also have an R package were most of these algorithm are implemented in C++ and in their "on-line" versions. Check the codes in the robfilter package.

Fried, R., Gather, U. (2007), On Rank Tests for Shift Detection in Time Series, Computational Statistics and Data Analysis, Special Issue on Machine Learning and Robust Data Mining 52, 221- 233.

Schettlinger, K., Fried, R., Gather, U. (2006) Robust Filters for Intensive Care Monitoring: Beyond the Running Median, Biomedizinische Technik 51(2), 49-56.

Schettlinger, K., Fried, R., Gather, U. (2006) Robust Filters for Intensive Care Monitoring: Beyond the Running Median, Biomedizinische Technik 51(2), 49-56.

$\endgroup$
  • $\begingroup$ Thank you so much for this information, recently , i've tried to use , DBSCAN clustering algorithmg (with some modification in code) for detection anomalies in Times series signal, FYI : the anomalies in this signal is a jum from a normal stat to abnormal ) anyway! i WILL read this articals now, hoping, find what i'm looking for, $\endgroup$ – mcdani Jun 13 '12 at 11:02
2
$\begingroup$

Univariate clustering is another way of looking at Intervention Detection. Unusual values (anomalies) can arise as Pulses , Seasonal Pulses or Level Shifts ( a contiguous sequence of anomalies having the same same sign and magnitude ). Consider the airline seriesenter image description here where the anomalies are not visually obvious. A histogram of the original series enter image description here and the histogram of the anomalie-cleansed series is informative.enter image description here . In order to detect the statistically significant anomalies enter image description here it was necessary to have a modelenter image description here (Note: There is no need for a logarithmic transformation as the variance of these errors is homogenous ) which yielded the following ACF for the error term enter image description here. In many cases there are level shifts ( distinctly different means ) waiting to be discovered. For example the Nile Series (annual data for 100 years) is a series that illustrates this enter image description here and enter image description here. The histogram of the original series is enter image description here naively suggests just two pulses (low values) while a model containing the empirically identified level (mean) shift generates the following analysisenter image description here with model enter image description here detailing the step (level ) shift and the one-time pulses . Bacon summarized this, writing in Novum Organum about 400 years ago said: "Errors of Nature, Sports and Monsters correct the understanding in regard to ordinary things, and reveal general forms. For whoever knows the ways of Nature will more easily notice her deviations; and, on the other hand, whoever knows her deviations will more accurately describe her ways." which I have paraphrased enter image description here. In summary detecting anomalies require a model which describes "typical behavior". Segmenting data into "typical and "atypical" is what Intervention Detection is all about http://www.unc.edu/~jbhill/tsay.pdf and elsewhere.

ADDITIONAL ANSWER TO ACTUAL 173 VALUES

Anomalies can be both one-time events (pulses) or they can be a contiguous sequence od pulses having the same sign and similar magnitude (Level/Step Shifts). You data has been identified as having an ARIMA structure ( simple AR(1) ; value .568 ) and with 12 pulses and 1 level/step shift at period 136. The identified pulses in chronological order; 1 time anomalies)enter image description here . The actual step-by-step analysis started with the ACF of the original series enter image description here which led to an automatically identified ARIMA model enter image description here which upon estimation was reduced to enter image description here . Using procedures called Intervention Detection detailed by Tsay and others http://www.unc.edu/~jbhill/tsay.pdf and a number of my previous posts here at SE led to enter image description here enter image description here . Now the final ACF of the errors suggesting sufficiency is enter image description here. The histogram of the original 173 values is of little help in detailing the anomalies and the level/step shift DUE to the auto-correlative structure in the 173 values. enter image description here .The Histogram of the final model residuals ( original series adjusted for memory, 1 level shift and the one-time pulses ) is shownenter image description here . The plot of actual and cleansed provides another view enter image description here. Summary: to find the exception , one needs to have an expectation.

$\endgroup$
0
$\begingroup$

I would suggest you PWCTools for MatLab from here:

Implementations of algorithms for noise removal from 1D piecewise constant signals, such as total variation and robust total variation denoising, bilateral filtering, K-means, mean shift and soft versions of the same, jump penalization, and iterated medians. It uses a range of solvers including interior-point optimization, adaptive step-size Euler integration and greedy knot placement.

It is simple to use and produces fast and robust results. In your case k-means clusterring would be the best choice although you can try other techniques depending on your needs.

$\endgroup$
  • $\begingroup$ Kmeans wont be effecient for the a time series clustering, because what i'm looking for is not clustering times serieS, but in one TS i should be able to detect an anomaly using a data mining or data driven approach, so, the number of clusters is undifined withing a TS, a, $\endgroup$ – mcdani Jul 17 '12 at 7:56
  • $\begingroup$ The toolbox provides functions for automatic estimation for number of clusters. K-means is just the simplest and strightforward approach. $\endgroup$ – Paul Jul 17 '12 at 8:02
  • $\begingroup$ @mcdani To detect an anomaly, one needs a model. If you post your time series or send it to me I will illustrate this. $\endgroup$ – IrishStat Jul 17 '12 at 12:58
  • $\begingroup$ @IrishStat, can you explain to me , what u mean by a model ? Up, you'll find the data series that u asked, regards $\endgroup$ – mcdani Jul 17 '12 at 14:56
  • $\begingroup$ @mcdani In this case the model is an ARIMA model of order AR(2) which simply means that the data requires a two period adjustment i.e there is auto-correlation suggesting that before you can detect unusual values are have to adjust the observed values by using values 1 period and two periods ago. See the analysis below. $\endgroup$ – IrishStat Jul 17 '12 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.