Transcript ppt

Discovering Interesting Sub-paths in Spatiotemporal Datasets
Xun Zhou1, Shashi Shekhar1, Stefan Liess2, Peter K. Snyder2, Pradeep Mohan1
1 Department of Computer Science and Engineering, 2Department of Soil, Water and Climate, University of Minnesota
{xun, shekhar, mohan}@cs.umn.edu, {liess, pksnyder}@umn.edu
4. Approach
• The Sahel region in Africa is prone to severe drought due to climate change
• What is unique about the Sahel?
• Narrow transitional zone between rainforest and desert (ecotone)
• Environmental attributes (e.g., vegetation cover) change sharply
• Vulnerable to climate change
Vegetation cover of Africa from the GIMMS
• Are there other regions that share similar
NDVI dataset [6]
features in the world?
• Help understand and predict
possible severe climate impacts
• Find spatial intervals of abrupt
changes
W2
W1=[12N, 17N]
• We previously proposed a Sub-path Enumeration and Pruning (SEP) approach [8]
• Sub-path interestingness is measured by Sameness Degree (an algebraic aggregate function of slopes)
• Compute piecewise slope, flag top and bottom a percentile segments as abrupt units (user given a).
• Sameness degree (SD) ranging [0, 1] is a function of piecewise slopes in a sub-path
• Define a test of the pattern: SD≥θ(given threshold)
• Enumerate all the intervals in the data and test with the above criterion using SEP .
• Decompose the statistical function into simple functions (e.g., SUM, COUNT) and pre-compute.
• Row-wise strategy: For each end unit, examine longer intervals first. Need further pruning.
• Top-down strategy: For all the intervals, always examine longer ones before its subsets.
• Experiment Setup:
• Climate model forecast time series (WCRP-CHFP IRI ECHAM4p5-MOM3-DC2fmt2 ATM)
• Synthetic data sequences with piecewise slope generated using Gaussian distribution
• Variables:
• Pattern Length Ratio (PLR): ratio of interesting interval length against data length
• Data length
• We further proposed a SEP with Pruning Border (SEPPER) approach that further optimize the enumeration
• The strategy combines linear (row-wise) and top-down searching strategy
• Space-time complexity superior to both SEP row-wise and top-down approaches
• SEPPER’s Time complexity ≤ Min{SEP top-down, SEP row-wise}
• SEPPER’s Space complexity≤ Min{SEP top-down, SEP row-wise}
The change is persistently
abrupt
Vegetation cover (in NDVI) along 18.5E longitude
• Alternative example: a similar pattern can be found in time series
• Rapid increase/decrease of precipitation/temperature in a few years
• Help identify events such as droughts from historical data.
5. Case Study: Interesting Sub-path with Abrupt Change
1. Case study on Africa vegetation cover (NDVI) dataset[6]
• Major spatial abrupt changes (ecotones) found : the Sahel and the southern boundary of tropical rainforest
• Other ecotones with abrupt changes in vegetation cover in the world: the Gobi Desert (Asia), Western America, etc
• Hypothesis: these areas may also be vulnerable to Sahel-like eco-changes.
Vegetation cover in Africa, August 1-15, 1981.
Abrupt vegetation cover change in Africa, August 1-15,
1981.
Source: 1.Sahel rainfall index data, Joint Institute for the Study of the Atmosphere and
Ocean (JISAO). http://jisao.washington.edu/data/sahel/ 2. Foley et al, Regime Shifts in
the Sahara and Sahel: Interactions between Ecological and Climatic Systems in
Northern Africa. Ecosystems (2003) 6: 524–539
2. Challenges
• Related statistical methods (e.g., CUSUM[1, 5]) only find collections of
interesting time-points/spatial locations (e.g., with abrupt changes),
rather than long intervals of change.
• Some other work in climate research [2] are not completely automated.
Abrupt change in
a sample data
sequence found by
CUSUM[5] (left
figure, location 6)
and our work
(right figure,
interval 5-11)
Location in the data sequence
Location in the data sequence
70
60
SEP Top-down
SEPPER
150
100
50
0
50
40
30
20
SEP Row-wise
SEPPER
10
0
0.18
0.23
0.35
0.63
0.84
Pattern Length Ratio
1
0.18
0.23
0.35
0.63
0.84
Pattern Length Ratio
1
7. Conclusions
• Further, we developed the SEPPER approach which improved the computational efficiency
over SEP. Experimental evaluation verified the tradeoff between the two previous SEP design
decisions and show dominance of the new SEPPER algorithm over them.
Vegetation cover map (in NDVI) of Africa (left), abrupt change of vegetation cover in Africa in August 1981 (middle), and global analysis for the same period (right)
2. Case study on Sahel rainfall index data[7]
3. Novelty
350
300
250
200
• We developed a data mining approach named SEP to find intervals of abrupt change in ecoclimate data. Case studies on real datasets show that the proposed approach can discover major
spatial and temporal intervals of abrupt change.
Precipitation time series in the some region in Africa
• The length of the change intervals vary
• The interestingness of the sub-path may not exhibit monotonicity (e.g.,
a long decreasing interval may contain a short increasing part)
• The data volume can be very large.
Run time of SEP Top-down and SEPPER
Run time of SEP row-wise and SEPPER
Time (Sec)
W3
6. Computational Speedup
Time (Sec)
1. Motivation
• Major temporal abrupt changes found by the proposed approach
• Decreasing period in late 1960s and mid 1980s[2].
• Long decrease (1950-1980)[3] found when using larger
abruptness percentile parameter.
• We found long periods of persistently high/low precipitation
using a slightly modified interest measure.
Upper: Smoothed yearly Sahel rainfall index. Lower: (left): abrupt precipitation
change found when using a=0.25 and θ=0.5. (center): abrupt precipitation change
found when using a=0.25 and θ=0.3, (right): persistent high/low precipitation periods.
8. Acknowledgements and References
• Support for this research was provided by the following grants:
National Science Foundation under Grant No. 1029711, III-CXT IIS-0713214, IGERT DGE-0504195,
CRI:IAD CNS-0708604, USDOD under Grant No. HM1582-08-1-0017, HM1582-07-1-2035, and W9132V09-C-0009.
[1] D. Nikovski and A. Jain. Fast adaptive algorithms for abrupt change detection. Machine learning, 79(3):283-306,
2010.
[2] G. Narisma, J. Foley, R. Licker, and N. Ramankutty. Abrupt changes in rainfall during the twentieth century.
Geophysical Research Letters, 34(6):L06710, 2007.
[3] A. Dai, P. Lamb, K. Trenberth, M. Hulme, P. Jones, and P. Xie. The recent sahel drought is real. International
Journal of Climatology, 24(11):1323-1331, 2004.
[4] I. Noble. A model of the responses of ecotones to climate change. Ecological Applications, 3(3):396-403, 1993.
[5] E. Page. Continuous inspection schemes. Biometrika, 41(1/2):100-115, 1954.
[6] Tucker, C.J., J.E. Pinzon, M.E. Brown. Global inventory modeling and mapping studies. Global Land Cover
Facility, University of Maryland, College Park, Maryland, 1981-2006.
[7] Joint Institute for the Study of the Atmosphere and Ocean(JISAO). Sahel rainfall index.
http://jisao.washington.edu/data/sahel/.
[8] Xun Zhou et al, Discovering Interesting Sub-paths in Spatiotemporal Datasets: A Summary of Results. In Proc.
ACM SIGSPATIAL GIS (GIS’11) pp 44-53. Chicago, IL, USA, 2011.