Transcript PPT

Vikramaditya R. Jakkula & Diane J. Cook
Washington State University
Index
•
•
•
•
•
•
•
Introduction
MavHome Project
Experimentation Environment
Temporal Relations
Experimentation Process
Results
Conclusion & Future Work
Smart Homes: Goals
Adapt to Needs
Cost Effective and
Reliable
Maximum Comfort
and Security
VJ
AI@WSU © 2007
3
MavHome: Smart Home Project
• Project Unique
– Focus on entire home
• House perceives and acts
– Sensors
– Controllers for devices
– Connections to the mobile user and Internet
• Unified project incorporating varied AI techniques,
cross disciplinary with mobile computing,
databases, multimedia, and others
VJ
AI@WSU © 2007
4
Experimentation Environment1
VJ
AI@WSU © 2007
5
Experimentation Environment2
MavHome Environment
MavLab
MavKitchen
MavPad
VJ
AI@WSU © 2007
6
Experimentation Environment3
MavLAB Argus Sensor Network
 around 100 Sensors.
 include Motion, Devices, Light, Pressure,
Humidity and more.
VJ
AI@WSU © 2007
7
What is a temporal relation?
Time Interval 
Food “Contains” Water
or
Water “Before” Pills
or
Food “Meets” Pills
or
Food “Contains” Water “before” Pills
Food
Water
Pills
“It is common to describe scenarios using time intervals rather than time points”
- James F. Allen
VJ
AI@WSU © 2007
8
Why Temporal Relations?
Reminder Assistance
• Reminder system based on temporal relations.
Anomaly Detection
• If Pills are to be taken “After” Food, we can notice violation of this activity!
Maintenance
• If Cooker is Spoiled should we call emergency or a normal repair?
Temporary Need Analysis
• If Oven used for Turkey, Is turkey at Home?
Improve Prediction
• Increase prediction accuracy with association rules!
VJ
AI@WSU © 2007
9
Temporal Relations (prediction)
TEMPORAL
RELATION
Y After X
VISUAL
DIAGRAM
X
Y
Y
X
Y
Y Met-by X
USABL
E
Start(X)<Start(Y); End(X)<Start(Y)

Start(X)>Start(Y); End(X)<End(Y)

Start(X)<Start(Y); Start(Y)<End(X);
End(X)<End(Y)

X
X During Y
YOverlapped-by X
CONSTRAINT
X
Start(Y) = End(X)

Start(X)≠Start(Y);
End(X) = End (Y)

Start(X)≠Start(Y);
End(X) = End (Y)

Y
XFinishesY
X
Y
YFinishedbyX
X
Y
XStarts Y
Start(X)=Start(Y); End(X)≠End(Y)
X
Y
YStartedby X
Start(X)=Start(Y); End(X)≠End(Y)
X

Before
X
After

During

Contains
X
Overlaps
X
Overlapped-By 
Meets
X
Met-by

Starts

Started-By 
Finishes

Finished-By 
Equals


Y
X Equals Y
Start(X)=Start(Y); End(X)=End(Y)

X
Y
VJ
AI@WSU © 2007
10
Datasets: Real vs. Synthetic
• Real Dataset and synthetic datasets consist timestamp of
the activity with the activity name and the state it is in.
Real Dataset (Sample):
3/2/2003 12:40:0 AM, (Studio E) E9 OFF
3/2/2003 2:40:0 AM, (Living Room) H9 ON
3/2/2003 2:40:0 AM, (Living Room) H9 OFF
3/2/2003 6:4:0 AM, (Living Room) H9 OFF
3/3/2003 3:43:0 AM, (Studio C) C14 ON
3/3/2003 3:43:0 AM, (Studio C) C15 ON
3/3/2003 3:43:0 AM, (Studio C) C13 ON
Datasets
Synthetic
Real
Synthetic Dataset (Sample):
2/1/2006 10:02:00 AM, off, oven
2/1/2006 11:00:00 AM, on, lamp
2/1/2006 11:11:00 AM, off, thermostat
2/1/2006 12:02:00 PM, off, lamp
2/1/2006 12:35:00 PM, off, cooker
2/1/2006 1:30:00 PM, on, lamp
2/1/2006 2:02:00 PM, off, fan
Parameter Setting
No of
Intervals
No of Days
No of Events Identified
60
8
1729
60
17
1623
VJ
AI@WSU © 2007
Size of
Data
106KB
104KB
11
Experimentation
• Current focus on enhanced prediction.
• Step 1: Temporal Interval analysis and
formulation.
• Step 2: Association rule generation using
Weka.
• Step 3: The run for prediction!
Step 1: Temporal Intervals
• Process raw data to form temporal intervals.
Raw Sensor Data
Temporal
Relations
Data
Interval Data
Raw Sensor Data
Timestamp
Sensor State
3/3/2003 11:18:00 AM OFF
3/3/2003 11:23:00 AM ON
3/3/2003 11:23:00 AM ON
3/3/2003 11:24:00 AM OFF
Identify Time Intervals
Date
Sensor ID
03/02/2003 G11
03/02/2003 G19
03/02/2003 G13
03/02/2003 G19
Start Time
01:44:00
02:57:00
04:06:00
04:43:00
Sensor ID
E16
G12
G11
G12
End time.
01:48:00
01:48:00
01:48:00
01:48:00
Associated Temporal Relations
Date time
Sensor ID Temporal Relation Sensor ID
3/3/2003 12:00:00 AM G12
DURING
E16
3/3/2003 12:00:00 AM E16
BEFORE
I14
3/2/2003 12:00:00 AM G11
FINISHESBY
G11
4/2/2003 12:00:00 AM J10
STARTSBY
J12
Temporal Interval Analyzer
Algorithm : Temporal Interval Analyzer
Input: data timestamp, event name and state
Repeat
While [Event && Event + 1 found]
Find paired “ON” or “OFF” events in data to determine temporal
range.
Read next event and find temporal range.
Identify relation type between event pair from possible relation types
(see Table 1).
Record relation type and related data.
Increment Event Pointer
Loop until End of Input.
Step 2: Association rule generation
using Weka
• Prediction requires strong rules to be formed.
• Use existing techniques such as Association
rule mining to find predictive rules.
• Use existing tool such as Weka.
• Use Apriori classifier in Weka for generating
best rules with a given support and
confidence.
Parameter settings for rules generation using Weka
in Real Datasets
RUN
MINIMUM
SUPPORT
MINIMUM
CONFIDENCE
Assosiation Rule Mining on Real Data
NO OF BEST
RULES
FOUND
1
0.00
0.5
100
2
0.01
0.5
006
3
0.02
0.5
002
4
0.05
0.5
001
100
90
80
70
60
50
40
30
20
10
0
No. Best Rules
Minimum Confidence
1
Minimum Support
2
3
4
1
0
2
0.01
3
0.02
4
0.05
Minimum Confidence
0.5
0.5
0.5
0.5
No. Best Rules
100
6
2
1
Minimum Support
Parameter settings for rules generation using Weka
in Synthetic Datasets
MINIMUM
SUPPORT
MINIMUM
CONFIDENCE
NO OF
BEST
RULES
FOUND
1
0.00
0.5
100
2
0.01
0.5
010
3
0.02
0.5
005
4
0.05
0.5
003
Axis Title
RUN
Assosiation Rule Mining on Synthetic
Data
100
90
80
70
60
50
40
30
20
10
0
1
No of Best rules found
Minimum Confidence
Minimum Support
2
3
4
1
0
2
0.01
3
0.02
4
0.05
Minimum Confidence
0.5
0.5
0.5
0.5
No of Best rules found
100
10
5
3
Minimum Support
Rule Generation
• Due to small datasets used, we use the top rules generated
with a minimum confidence of 0.5 and a minimum support
of 0.01.
• Confidence level above 0.5 and support above 0.05 could not
be used, as they could not result in any viable rules.
Sample of best rules observed in real datasets:
Activity=C11 Relation=CONTAINS 36 ==> Activity=A14 36
Activity=D15 Relation=FINISHES 32 ==> Activity=D9 32
Activity=D15 Relation=FINISHESBY 32 ==> Activity=D9 32
Activity=C14 Relation=DURING 18 ==> Activity=B9 18
ActiveLeZi: A sequential Predictor
• Model Useful for prediction of events with
previous history.
• Based on LZ78 text compression algorithm
• Employs Markov Models to optimally predict
the next event in the sequence.
Step 3: Temporal Rules Enhancement
to the Prediction.
Input: Output of ActiveLezi Predictor a, Best Rules r, Temporal Dataset
Repeat
If a! = null
Repeat
Set r1 to the first event in the relation rule
If (r1 ==a) Then
If (Relation! = “After”) Then Calculate evidence (use Equation 1)
If evidence > (Mean + 2 Std. Dev.) is noted Then Make event related to r1 in the best rule as next
predictor output;
Else
*Get next predicted event and look for there temporal relation in the temporal relations database
based on the frequency.
If again the relation is after Then goto *
Until no more “After” relations are found Calculate evidence
If evidence > (Mean + 2 Std. Dev.) Then predict;
Else
Calculate evidence and if evidence > (Mean + 2 Std. Dev.) Then predict this event based on the
relation;
End if.
Until end of rules.
End if.
Loop until End of Input.
Equation 1: Probability Model
• P(Z|Y) = |After(Y,Z)| + |During(Y,Z)|
+ |OverlappedBy(Y,Z)| + |MetBy(Y,Z)|
+ |Starts(Y,Z)| + |StartedBy(Y,Z)| +
|Finishes(Y,Z)| + |FinishedBy(Y,Z)| +
|Equals(Y,Z)| / |Y|
Experiment Results
• Comparing ActiveLezi based prediction with
and without temporal rules
DATA SET
ACCURACY% ERROR%
REAL
(WITHOUT RULES)
55
45
SYNTHETIC
(WITHOUT RULES)
64
36
REAL
(WITH RULES)
56
44
SYNTHETIC
(WITH RULES)
69
31
Accuracy
80
70
60
50
40
30
20
10
0
Real(Without Rules)
Real(With Rules)
Accuracy
Synthetic(Without
Synthetic(With
Rules)
Rules)
Experiment Results2
• 1.86% prediction performance improvement
in the real data and 7.81% improvement in
the synthetic data.
• Clear indications of larger datasets would
lead to drastic improvement in prediction.
Conclusion
• Unique and new Approach.
• Real data had 1.86% and synthetic data
had 7.81% improvement.
• Larger datasets would be incorporated and
experimented soon.
Future Direction
• Expansion of the temporal relations by
including more temporal relations, such as
until, since, next, and so forth, to create a
richer collections.
• Temporal Visualization problems.
• Pattern analysis for lifestyle and behavior
improvements.
Time for Discussions!
Thank You
VJ
AI@WSU © 2007
26