Mining and Forecasting ofBig Time-series Data
Yasushi Sakurai

Sakurai Lab.
@ Kumamoto University

Sakurai Lab.

© 2016 Yasushi Sakurai

1

Big time-series data
Social/natural phenomena
climate
WebBig Data

EconomyEpidemic

IoT, sensors
Sakurai Lab.

© 2016 Yasushi Sakurai

2

Big time-series data
Social/natural phenomena
climateWeb
Environmental sensors- Temperature,- Air pressure, etc.
Application- Agriculture

Big Data

EconomyEpidemic

IoT, sensors
Sakurai Lab.

© 2016 Yasushi Sakurai

3

Big time-series data
Social/natural phenomena
climateWeb

EconomyOnline user activities- Web clicks,- Online reviews
Application- MarketIoT,analysis
sensors

Epidemic

Big Data

Sakurai Lab.

© 2016 Yasushi Sakurai

4

Big time-series data
Social/natural phenomena
climateWebEconomy

Sensor streams- Vibration,Acceleration
Application
Epidemic- Self-driving car- Structural healthmonitoring
IoT, sensors

Big Data
Sakurai Lab.

© 2016 Yasushi Sakurai

5Motivation• Given: Big time-series data
– Sensor data
– Web, online activities– Medical data

• Goal: Real-time forecasting• At-work:– Online marketing– Sensor monitoring– Forecasting future epidemicsSakurai Lab.

© 2016 Yasushi Sakurai

6

New challenges
Time-series data analysis

Indexing,
FeatureLinearSimilarity extraction modelingsearchDatastream

DFT, DWT,SVD, ICA

Correlation
monitoring
etc.

ED, DTW,SAM

AR, LDS,
ARIMA

X
Y

DTW

Sakurai Lab.

PCA

ICA

© 2016 Yasushi Sakurai

Data (X)

Model (M)7

New challenges
They cannot handle “Big” data, i.e.,Indexing,
FeatureLinearData
Automatic
Similarity
Non-linear
extraction modelingstreamparametersearchphenomena
Correlation
tuning
DFT, DWT,ED, DTW,
AR, LDS,SAM

X

XYDTWSakurai Lab.

SVD, ICA

Complexevents
PCA

ARIMA

monitoring
etc.

Real-time
forecasting
ICA© 2016 Yasushi Sakurai

Data (X)

Model (M)8

New challenges
They cannot handle “Big” data, i.e.,Indexing,
FeatureLinearData
Automatic
Similarity
Non-linear
extraction modelingstreamparametersearchphenomenatuning
AR,DFT, DWT,StatStream
ED, DTW
Correlation

X

X

Y

DTW

Sakurai Lab.

ARIMA,
Complex LDS
SVD, ICA

events

PCA

ICA© 2016 Yasushi Sakurai

etc…

Real-time
forecasting
Data (X)

Model (M)9New research directions• Time-series data analysis– Indexing and fast searching– Sequence matching– Clustering– etc.

• New research directions

TimeNO magic #1. Automatic mining
2. Non-linear modeling
3. Large-scale tensor analysis
XSakurai Lab.

© 2016 Yasushi Sakurai

≈

+...
10

(R1) Automatic mining
No magic numbers! ... because,

Manual- sensitive to the parameter tuning- long tuning steps (hours, days, …)

Automatic (no magic numbers)- no expert tuning required
Big data mining:-> we cannot afford human intervention!!
Sakurai Lab.

© 2016 Yasushi Sakurai

11

(R1) Automatic mining“Automatic” mining algorithm
Find: compact description of data X

Given

FindChicken dance

beaks

tail feathers
claps

wings
Sakurai Lab.

© 2016 Yasushi Sakurai

beaks

tail feathers
claps

wings
12

(R1) Automatic mining“Automatic” mining algorithm

Model beaks

claps

wings
RegimesSequences

Idea (1): Multi-level chain model–HMM-based probabilistic model–with “across-regime” transitions
Sakurai Lab.

© 2016 Yasushi Sakurai

13

(R1) Automatic mining“Automatic” mining algorithm
CostM

Idea(2): Minimize encoding cost!

CostC
CostT

min ( CostM(M) + Costc(X|M) )Model cost

Goodcompression
Sakurai Lab.

Coding cost

1 2 3 4 5 6 7 8 9 10

Gooddescription© 2016 Yasushi Sakurai(# of r, m)

14

(R1) Automatic mining“Automatic” mining algorithm

AutoPlait (NO magic numbers)
Sakurai Lab.

© 2016 Yasushi Sakurai

15

(R2) Non-linear (gray-box) modeling• Gray-box mining

Gray-box– If we know the equations• Non-linear (differential) equations– Epidemic– Biology– Physics, Economics, etc.

• Modeling non-linear social phenomena– Non-linear analysis for Web online activities(e.g., information diffusion, interaction)
Sakurai Lab.

© 2016 Yasushi Sakurai

16(R2) Non-linear (gray-box) modelingNews spread in social media# of mentions

Number of mentions in blogs/Twitter200# of mentions

Newsspread

Decay(power law)

100
0

Sakurai Lab.

Breaking
news

20406080100Time (hours)

120

140

160

140160(per hour, 1 week)

100
50
0

20

4060

80
100
Time (hours)© 2016 Yasushi Sakurai

12017

(R2) Non-linear (gray-box) modelingNews spread in social media
1. Un-informed
bloggers

Time n=0
Sakurai Lab.

2. Externalshock

3. Infection(word-of-mouth)

Time n=nb

Time n=nb+1© 2016 Yasushi Sakurai

β18

(R2) Non-linear (gray-box) modelingNews spread in social media
1. Un-informedbloggers

2. External
shock

Decay function:f (n)LinearTime n=0(word-of-mouth)

βf (n) = β * nf (n)© 2016 Yasushi Sakurai−1.5LogTime n=nbn
Sakurai Lab.

Powerlaw
3. Infection

Time n=nb+1n19

(R2) Non-linear (gray-box) modelingNews spread in social media
Memes in social media/blogs

020402040

Sakurai Lab.

60 80 100 120
Time2040500204060 80 100 120
Time© 2016 Yasushi Sakurai

Value

50060 80 100 120
TimeOriginal
SpikeM

100
Value

Value

500060 80 100 120
TimeOriginal
SpikeM

10050Original
SpikeM100

204060 80 100 120
Time

Original
SpikeM

100
Value

Value

50

Original
SpikeM

100
Value

Original
SpikeM100

500204060 80 100 120
Time20(R2) Non-linear (gray-box) modeling
Forecast tail-part and rise-part!
(1) First spike(2) Release date(3) Two weeks before release

Given (1) first spike,(2) release date of two sequel movies(3) access volume before the release date
KDD 2012

Y. Matsubara et al.

21

(R2) Non-linear (gray-box) modeling
Online competition
Interactions
between keywords
PlayStation AndroidWiiXboxSakurai Lab.

© 2016 Yasushi Sakurai

22

(R2) Non-linear (gray-box) modeling
Online competition(Google Search volume)
PlayStation Wii

AndroidXbox

Sakurai Lab.

© 2016 Yasushi Sakurai

23

(R2) Non-linear (gray-box) modeling
The Web as a Jungle !
Ecosystemon theWeb
Ecosystemin theJungle
Sakurai Lab.

© 2016 Yasushi Sakurai

24

(R2) Non-linear (gray-box) modeling
The Web as a Jungle !
Ecosystem--- Non-Linear equations ---on theWebd),#&aP(t)∑iji+.
%(j=1Ecosystem
Pi (t +1) = Pi (t)+1+ ri %1−.
(in theKi%(+*$'.Jungle
Sakurai Lab.

© 2016 Yasushi Sakurai

25

Ecosystem on the WebJungle

Web

Biologicalspecies

Onlineactivities

Food
resources

User
resources

Population

Popularity

Climate/season

Annual events(e.g., Xmas)

Sakurai Lab.

© 2016 Yasushi Sakurai

26

(R2) Non-linear (gray-box) modeling
The Web as a Jungle !
Interactions
between keywords
PlayStation AndroidWiiXbox

Sakurai Lab.

© 2016 Yasushi Sakurai27

(R2) Non-linear (gray-box) modeling
The Web as a Jungle !
Seasonality
PlayStation AndroidWiiXbox

Sakurai Lab.

© 2016 Yasushi Sakurai

28

(R3) Large-scale tensor analysis
X• Time-stamped events– e.g., web clicks
TimeURL

User

08-01-12:00

CNN.comSmith

08-02-15:00

YouTube.com

Brown

08-02-19:00

CNET.comSmith

08-03-11:00

CNN.com

Johnson…

…

…

Represent as
Mth order tensor (M=3)

Sakurai Lab.

URL uxuser vnTime

Element x: # of eventse.g., ‘Smith’, ‘CNN.com’,‘Aug 1, 10pm’; 21 times© 2016 Yasushi Sakurai29

(R3) Large-scale tensor analysis
Complex time-stamped events{time, URL, user ID, access devices, http referrer,…}

TimestampURL

2012-08-01-12:00

CNN.com

Smithiphone

2012-08-02-15:00

YouTube.com

Brown

iphoneCNET.com

Smithmac

2012-08-03-11:00

CNN.com

Johnson

ipad

…

…

…

…

2012-08-05-12:00

CNN.comSmithiphone2012-08-05-19:00

CNET.comSmithiphoneForecast
2012-08-02-19:00

Sakurai Lab.

© 2016 Yasushi Sakurai

User Device

30

(R3) Large-scale tensor analysis
Complex time-stamped events
Object/
URLActor/
userWeb clicks
TimeObjectTimeActor(business)
Sakurai Lab.

…
(news)© 2016 Yasushi Sakurai(media)31

(R3) Large-scale tensor analysis
Complex time-stamped events
Object/topic vectors
URL e.g., businessWeb clicks
Actor/
Higher value:user
Highly related
topic

Sakurai Lab.

Object/
URLActor
Object /user
Time
Smith
JohnsonActor(business)Time

Money.com
CNN.comTime…

Mon-Fri

Sat-Sun(news)(media)© 2016 Yasushi Sakurai

32

(R3) Large-scale tensor analysis
Complex time-stamped events
Noisy L

URL matrix

Sakurai Lab.

(Original data)

User matrix© 2016 Yasushi SakuraiSparse L

Time matrix

33

Putting it all together
New research directions
1. Automatic mining
2. Non-linear (gray-box) modeling
3. Large-scale tensor analysis

MT
M AA NN T

Put alltogether

X

3h-Tutorials
SIGMOD’15
WWW’16
NO magic !

≈+...

New challenge: MANT analysis
Multi-Aspect Non-linear Time-series
Sakurai Lab.

© 2016 Yasushi Sakurai

34

New challenge: MANT analysis
Non-Linear tensor analysis

P2 Vaccination
P1P4
P5
Sakurai Lab.

Seasonality
External shocks
Mistakes, errors

w/ Sakurai, Panhuis, Faloutsos

P3© 2016 Yasushi Sakurai

Local patterns
35New challenge: MANT analysis
Non-Linear tensor analysis
Given:
Tensor X (disease x location x time)

X

Find:
Compact description of X, “automatically”
FUNNEL
X

Sakurai Lab.

=N

B

R

P1

P2P3

© 2016 Yasushi Sakurai

M

E

P4P536

New challenge: MANT analysis
Non-Linear tensor analysis
Given:
X
Tensor Seasonality
X (disease x location xDiscontinuities
time)
Find:
Compact description of X, “automatically”
FUNNEL
X

Sakurai Lab.

=N

B

R

P1

P2P3© 2016 Yasushi Sakurai

MEP4P537

New challenge: MANT analysis
Non-Linear mining & forecastingof local competition

Sakurai Lab.

© 2016 Yasushi Sakurai

38

New challenge: MANT analysis
Time-stamped events:{activity, location, time}

XActivity

md

Time (weekly)
Sakurai Lab.

© 2016 Yasushi Sakurain39

New challenge: MANT analysis
Given: Tensor X(activity x location x time)X

Find: Compact description of X
CompCubeX=B
Sakurai Lab.

C© 2016 Yasushi Sakurai

SD40

New challenge: MANT analysis
Given: Tensor X(activity x locationxtime)
Competition Seasonality
BasicsX

DeltasFind: Compact description of X
CompCubeX=B
Sakurai Lab.

C
© 2016 Yasushi Sakurai

SD41

Modeling power of CompCube
Google search for Kindle, Nexus
Weak/Average/StrongCAUSITJPCNBR
ZA

AU

Local Competition
strength
Sakurai Lab.

© 2016 Yasushi Sakurai

42Modeling power of CompCube
Google search for Kindle, Nexus
Weak/Average/StrongCAUS

ITJP
CNBR
ZA

AU

Local Competition
strength
Sakurai Lab.

© 2016 Yasushi Sakurai

43Modeling power of CompCube
Local seasonality for iPod

Component #1
Sakurai Lab.

Component #2© 2016 Yasushi Sakurai

44Modeling power of CompCube
Local seasonality for iPodDec.
XmasFeb.

ChineseNew
Year
Component #1
Sakurai Lab.

Component #2© 2016 Yasushi Sakurai

45Modeling power of CompCube
Fitting for News resources
Fitting result − RMSE=0.056# of clicks @ time

Detected!

1
0.8
0.6
0.4
0.20
2004

2006

Sakurai Lab.

2008
2010
Time (weekly)2012© 2016 Yasushi Sakurai

2014

1CNN
2Fox_News
3TIME
4Google_News
5BBC
6Yahoo_News
7AP
8Huffington_Post
9MSN_News
10Al_Jazeera
Wikipedia

46

Modeling power of CompCubeFitting for News resources
Weak/StrongLocal attention toUS election
US election
Nov. 2008

Wikipedia

Sakurai Lab.

© 2016 Yasushi Sakurai

47

New challenge: MANT analysis
Non-Linear mining & forecastingof local competition
3. Forecast future
activities
FutureTime

Sakurai Lab.

?
© 2016 Yasushi Sakurai

48

Putting it all together
New research directions
1. Automatic mining
2. Non-linear (gray-box) modeling
3. Large-scale tensor analysis

M
TM AA NN T

Put alltogether

X

3h-Tutorials
SIGMOD’15
WWW’16
NO magic !

≈+...

New challenge: MANT analysis
Multi-Aspect Non-linear Time-series
Sakurai Lab.

© 2016 Yasushi Sakurai

49

Industrial contribution

BRAID@SIGMODʼ05• Bridge structural health monitoring– Structural monitoring using vibration/shock sensors– Keep track of lag correlations for sensor data
streams

Sakurai Lab.

© 2016 Yasushi Sakurai

50

Industrial contribution

BRAID@
SIGMOD’05• Bridge structural health monitoring– Goal: real-time anomaly detection for disasterprevention– Several thousands readings (per sec) fromseveral hundreds sensor nodes• Uses BRAID• Metropolitan Expressway(Tokyo, Japan)
Vibration/shock sensor
Structural health monitoring
Sakurai Lab.

© 2016 Yasushi Sakurai

51

Industrial contribution

BRAID@SIGMOD’05• Bridge structural health monitoring with BRAID

Metropolitan Expressway(Tokyo, Japan)

Tokyo Gate Bridge(Tokyo, Japan)

Can Tho Bridge (Vietnam)
Sakurai Lab.

© 2016 Yasushi Sakurai

52

Industrial contribution WebDBFʼ15
Best paper– Automobile sensor data
{ trip ID, zone ID, object}

TrailMarker
Original tensor XTripdw

nSakurai Lab.

ZoneObject（sensors）
velocity
Longitudinal/lateral acceleration© 2016 Yasushi Sakurai

53Industrial contribution WebDBFʼ15Best paper– Automobile sensor data
{ trip ID, zone ID, object}

TrailMarker
Original tensor XTripdTrip 1zone

Trip 2w
nSakurai Lab.

Zone
© 2016 Yasushi Sakurai

zone

Trip 3zone
54

Industrial contribution WebDBFʼ15
Best paper– Automobile sensor data
{ trip ID, zone ID, object}

TrailMarker

Sakurai Lab.

© 2016 Yasushi Sakurai

55

Thank you
Code/Data/Tutorial:

Sakurai Lab.

http://www.cs.kumamoto-u.ac.jp/~yasushi/
M
T
M AA NN T

NO magic !

XSakurai Lab.

© 2016 Yasushi Sakurai≈+...

56