4 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 25, NO. 1, JANUARY 2014
if the FSA reaches a state from where there is no
outgoing edge corresponding to the last symbol of the
current subsequence. FSAs have been used for outlier
detection in [23], [35], [36], [37]. The methods to gen-
erate the state transition rules depend on particular
application domains.
Some Markov methods store conditional informa-
tion for a fixed history size=k, while others use a
variable history size to capture richer temporal depen-
dencies. Ye [38] proposes a technique where a Markov
model with k=1 is used. In [39], [40], the conditional
probability distribution (CPD) are stored in proba-
bilistic suffix trees (PSTs) for efficient computations.
Sparse Markovian techniques estimate the conditional
probability of an element based on symbols within the
previous k symbols, which may not be contiguous or
immediately preceding to the element [41], [42].
HMMs can be viewed as temporal dependency-
oriented mixture models, where hidden states and
transitions are used to model temporal dependencies
among mixture components. HMMs do not scale well
to real life datasets. The training process may require
judicious selection of the model, the parameters, and
initialization values of the parameters. On the other
hand, HMMs are interpretable and theoretically well
motivated. Approaches that use HMMs for outlier
detection include [23], [43], [44], [45], [46].
Unsupervised OLAP based Approach
Besides traditional uni-variate time series data,
richer time series are quite popular. For example, a
time series database may contain a set of time series,
each of which are associated with multi-dimensional
attributes. Thus, the database can be represented
using an OLAP cube, where the time series could
be associated with each cell as a measure. Li et
al. [47] define anomalies in such a setting, where given
a probe cell c, a descendant cell is considered an
anomaly if the trend, magnitude or the phase of its
associated time series are significantly different from
the expected value, using the time series for the probe
cell c.
Supervised Approaches
In the presence of labeled training data, the fol-
lowing supervised approaches have been proposed in
the literature: positional system calls features with the
RIPPER classifier [48], subsequences of positive and
negative strings of behavior as features with string
matching classifier [34], [49], neural networks [50],
[51], [52], [53], [54], Elman network [53], motion fea-
tures with SVMs [55], bag of system calls features
with decision tree, Na
¨
ıve Bayes, SVMs [56]. Sliding
window subsequences have also been used as features
with SVMs [57], [58], rule based classifiers [59], and
HMMs [44].
2.1.2 Window based Detection of Outlier Time Series
Given: A database of time series
Normal
or Abnormal
Windows
Database
Test Sequence s
Windows
!
"
Train Sequences
Optional Processing like DWT
Processed Sequence
Processed Sequences
Normal
Samples
Detectors
Length-w
windows
Fig. 2. Window Based Time Series Outlier Detection
Find: All anomalous time windows, and hence
anomalous time series
Compared to the techniques in the previous sub-
section, the test sequence is broken into multiple
overlapping subsequences (windows). The anomaly
score is computed for each window, and then the
anomaly score (AS) for the entire test sequence is
computed in terms of that of the individual windows.
Window-based techniques can perform better local-
ization of anomalies, compared to the techniques that
output the entire time series as outliers directly. These
techniques need the window length as a parameter.
Windows are called fingerprints, pattern fragments,
detectors, sliding windows, motifs, and n-grams in
various contexts. In this methodology, the techniques
usually maintain a normal pattern database, but some
approaches also maintain a negative pattern or a
mixed pattern database. Figure 2 shows a general
sketch of the method.
Normal Pattern Database Approach
In this approach, normal sequences are divided into
size w overlapping windows. Each such window sub-
sequence is stored in a database with its frequency. For
a test sequence, subsequences of size w are obtained,
and those subsequences that do not occur in normal
database are considered mismatches. If a test sequence
has a large number of mismatches, it is marked as
an anomaly [44], [49], [51], [53], [60]. Rather than
looking for exact matches, if a subsequence is not
in the database, soft mismatch scores can also be
computed [20], [61], [62], [63].
Besides contiguous window subsequences, a looka-
head based method can also be used for building
a normal database [64]. For every element in every
normal sequence, the elements occurring at distance
1,2,. . ., k in the sequence are noted. A normal database
of such occurrences is created. Given a new test
sequence, a lookahead of the same size k is used. Each
pair of element occurrence is checked with the normal
database, and the number of mismatches is computed.
Negative and Mixed Pattern Database Approaches
Besides the dictionaries for normal sequences,
anomaly dictionaries can also be created [34], [50],
[65], [66], [67]. All normal subsequences of length w
剩余19页未读，继续阅读
z6203271
- 粉丝: 0
- 资源: 2
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
