UBICOMP '14 ADJUNCT, SEPTEMBER 13 - 17, 2014, SEATTLE, WA, USA

Improving Activity Recognition Via
Automatic Decision Tree Pruning
Abstract

Thomas PhanSamsung Research America - Silicon Valley
San Jose, CA
thomas.phan@samsung.com

Activity recognition enables many user-facing smartphone
applications, but it may suffer from misclassifications
when trained models attempt to classify previously-unseen
real-world behavior. Our system mitigates this problem by
first identifying spurious classifications and thenautomatically pruning a decision tree model to removelabels that tend to produce wrong inferences, resulting in
a 10% classification improvement based on our data set.

Author Keywords
Activity recognition; accelerometer; signal classification

ACM Classification Keywords
I.5.4 [Pattern recognition]: Applications.

Introduction

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
UbiComp’14 , September 13 - 17 2014, Seattle, WA, USA
Copyright c 2014 ACM 978-1-4503-3047-3/14/09...$15.00.
http://dx.doi.org/10.1145/2638728.2641310

827

Activity recognition is the process of determining user
physical behavior from sensor data [1, 5, 6, 4, 2]. In ourwork we are especially interested on recognizing humanmodes of transportation (comprising driving, walking,running, bicycling, and idling) using only a smartphone’s
accelerometer due to its low power consumption.
These physical activities are relevant because they enablea variety of user-facing smartphone applications; forexample, recognizing that the user is driving can trigger a

UBICOMP '14 ADJUNCT, SEPTEMBER 13 - 17, 2014, SEATTLE, WA, USA

reduced-distraction user interface, and recognizing long
periods of sedentary sitting can alert the user to get up toexercise. Because these applications perform a real-time,user-facing action (as opposed to simply life-logging theuser’s activity), it is important that misclassifications beminimized in order to prevent a degraded user experience.
We use supervised machine learning in our work, wheremisclassifications can occur due to two reasons. First, thetrained model may be overfit, incorporating noise from thetraining data. Second, the model may be insufficient,producing spurious classifications for real-world behavior.
Any training data from scripted behavior results in amodel that is able to accurately classify single activities
but has difficulty when users perform arbitrary, naturalistic
behavior that may involve either activity transitions orcompletely new activities. The problem stems from thedata collection, where gathering labelled mixed-activity
traces is prohibitively time-consuming. Some approaches
to treating naturalisitic activities include: labelling
videotaped user behavior [3]; labelling users performing
real-time multiple activities [5]; having users report theirown activities [8]; and defining a “null” class [2].
In this paper we apply a novel approach to handling suchspurious classifications. We first train an activityrecognition model using a C4.5 decision tree [7]; we use adecision tree because the model occupies under 10KB ofmemory and classifies quickly, requiring a number offloating-point operations proportional to the tree height.
We then judiciously and automatically prune the tree after
the model is built. We take advantage of the C4.5 tree’s
redundant labelled leaves and apply thresholding toremove the leaves that tend to produce misclassifications.
The result is an improvement of up to 10% classification
accuracy based on our collected data set.

828

Building the modelIn this paper we describe a non-commercialized prototype
of a low-power accelerometer-only activity recognition
component that generates a continuous stream of inferredhuman modes of transportation. We measured the system
to consume under 225 mW of power, which includes thebaseline CPU, on a Samsung Galaxy S III phone.
The activity recognition system runs in real-time on
Android phones and detects modes of transportation using
an accelerometer signal classifier. The end-to-end systemcomprises two distinct phases. First, in an offline training
phase, 20 test participants (15 male and 5 female)
performed fixed physical activities while wearing
data-collecting smartphones. After we extracted sensor
features, we trained a C4.5 decision tree model. Second,
we loaded the model into our Android activity recognition
software to perform real-time classification.
We sampled the accelerometer at 32 Hz and kept a
128-sample sliding window with 50% overlap. Because thephone can be oriented in different directions, wenormalized the readings into three orientation-independent
time series: Cartesian magnitude of the acceleration
vector; projection onto the true horizontal plane; andprojection onto the true vertical axis. For each of thethree time series, we computed the features: (i)time-domain mean, standard deviation, power, andentropy; and (ii) frequency-domain energy, average of the
top-5 highest-magnitude frequency, frequency with thehighest magnitude, the highest magnitude, and weightedvariance. In all, 9 features are extracted from each timeseries, resulting in 27 total features. Our systemdemonstrates a 98.1% per-window classification accuracy
with 10-fold cross-validation with our five activities:
W alking, Running, Driving, Biking, and Idling.

WORKSHOP: HASCA

Per-class summary statistics and the confusion matrix are
shown in Tables 1 and 2, respectively.
ClassTP RateFP RatePrec

RecallAUC

Walking
Idling
Running
Driving
BikingWeighted Avg.

0.99
0.987
0.971
0.97
0.966
0.981

0.004
0.011
0.00
0.01
0.003
0.007

0.988
0.983
0.997
0.971
0.966
0.981

0.99
0.987
0.971
0.97
0.966
0.981

0.996
0.998
0.996
0.995
0.996
0.996

ActualTable 1: Activity recognition results showing per-class true
positive rate, false positive rate, precision, recall, and area
under the ROC curve.

Walking
Idling
Running
Driving
BikingWalking
98.97%
0.00%
2.88%
0.29%
0.28%

Idling0.25%
98.73%
0.00%
2.20%
0.56%

Predicted
Running
0.06%
0.02%
97.12%
0.00%
0.00%

Driving
0.47%
1.14%
0.00%
96.99%
2.51%

Biking
0.25%
0.12%
0.00%
0.52%
96.65%

Table 2: Activity recognition confusion matrix.

Pruning the model
We augmented our classifier with an algorithm that
improves classification for real-world usage. As weshowed, the system achieves a 10-fold cross-validatedaccuracy of 98.1% on windowed data over our fiveactivities (with no null class). While this result isappealing and is in line with prior work (e.g. [6, 4]), it ismisleading because it applies only to the single-activity,
scripted activity behavior recorded during training. Even
with cross-validation, two problems arise: (1) the built
model may be overfit to the data; and (2) mixed-activity,
naturalistic human behavior contains many motions andtransitions that were not captured during training. As aresult, the model can return spurious classifications inreal-world use. Indeed, we later show that the model
achieves only 87.8% accuracy when applied to a hold-out

829

set of real-world naturalistic behavior.
Consider the following output of our system that
illustrates the problem stemming from a user walking up
to a car, getting keys out of his pocket containing his
smartphone, and then driving off, where “getting keys outof pocket” is one of an infinite number of naturalistic
behaviors. Let W, I, R, and D be the output classification
labels for walking, idling, running, and driving,respectively, in the following left-to-right sequence:
WWWWWWDWDIIRDDDDDD
The underlined labels in the above sequence are thespurious classifications that occurred from getting keys
out of the pocket. Ideally, the system should output thelabels for walking to driving without the interruption of
the unknown physical act. Such choppiness can be
avoided by applying smoothing (e.g. with a Markovmodel), but our belief is that it is better to remove
misclassifications at the source as early as possible inorder to reduce pollution of any smoothing window.
Looking back to the sequence above, it is important tounderstand why the underlined labels may be considered
spurious while other instances of the same label are not;for example, D appears to occur in both spurious and valid
subsequences. Here we leverage a characteristic of activity
recognition generally not found in other domains, namely
the sequential, periodic nature of emitted classifications.
We define a classification Ct at time t to be spurious if ina window Lpre before Ct and in a window Lpost after Ct ,there are labels that differ from Ct . In this example, if we
assume both Lpre and Lpost have a width of 5, then theunderlined labels match this definition but thenon-underlined labels do not. In our work we empiricallychose a width of 10, which is 20 seconds of real time.

UBICOMP '14 ADJUNCT, SEPTEMBER 13 - 17, 2014, SEATTLE, WA, USA

Now that such spurious classifications can be identified,
we apply an automated scheme to remove the problem
from the model itself with judicious pruning after themodel has been built. The spurious classifications stemfrom the nature of the C4.5 algorithm; unlike othertree-building approaches like Hunt’s algorithm, C4.5
allows the same label to occur at multiple leaves in thetree, resulting in high accuracy at the cost of potential
overfitting as the training space becomes progressively
partitioned along each feature dimension axis. Our
approach takes advantage of this fact by finding andremoving the leaves that tend to cause misclassifications.

in this table, we can prune all labels whose validity isbelow a threshold. For example, in the bottom half ofFigure 1, we show the label Driving-34 (or D34 ) being
pruned out of the tree. If a pruned leaf is reached duringclassification, no output is emitted.

Looking at the decision tree leaves provides the intuition
that we can uniquely amend each leaf label with a simple
monotonically-increasing integer suffix, as shown in the
top half of Figure 1. This simplified illustration shows only
6 out of the total 46 leaves in our built decision tree.
Further, out of the 46 leaves in the complete decision tree,
there are 15 leaves with the “Driving” label; after applying
suffixes, these leaves then take the labels “Driving-17” (orD17 ), “Driving-34” (or D34 ), and so forth.
Figure 1: Illustrations of a simplified decision tree with only 6 out

With this amended tree in hand, we then observe its
output on a hold-out data set taken from three users,
each performing self-labelled naturalistic activities overthree days each, totalling 4473 minutes. All three users
previously participated in the scripted training. We ran
this hold-out data through the classifier to let it emit theuniquely-identified labels, and in Table 3 we show theresults for some of the 15 unique “Driving” labels. For
example, the classifier emitted Driving-17 11,684 times
during this trace, and of those, 242 were spurious
according to the definition we provided earlier, resulting invalid (that is, non-spurious) occurrences 97.9% of thetime. By looking at the validity percentages such as those830

of the 46 leaves in the complete tree. The top half shows the treewith uniquely-identified leaf labels. The bottom half shows thepruning of a leaf whose validity percentage fell below a threshold.

Figure 2 shows the classification accuracy from applying
pruned models to the self-labelled, naturalistic behavior
hold-out data set. Without any pruning, our classifierachieves an accuracy of 87.8%. With a pruning threshold
set at 80%, the classification accuracy increases to 96.8%,
an improvement of 10.3%. However, this increase does
not come for free. Figure 3 shows the fraction of the144,639 possible classifications that we actually emitted.
At the 80% threshold, only 123,624 (or 85.4%)classifications were emitted; the remaining classifications

WORKSHOP: HASCA

were suppressed. At the 95% threshold, we retained only
11 of 46 leaf labels, producing only 64,564 classifications.
We thus observe the tradeoff between increased accuracy
and decreased number of emissions.
Leaf label# of total
occurrences# of spurious
occurrences% valid
occurrences

Driving-5
Driving-17
Driving-25
Driving-34
Driving-37
Driving-39
Driving-40
Driving-42

154
11684
227
1482
213
22380
238
1683

131
242
120
1017
107
900
95195

14.9%
97.9%
47.1%
31.4%
49.8%
96.0%
60.0%
88.4%

Table 3: Spurious classification counts of “Driving” leaves in a
hold-out data set with the percentage of valid (non-spurious)
occurrences.

Classiﬁca(on	  Accuracy	  1	  0.98	  0.96	  0.94	  0.92	  0.9	  0.88	  0.86	  0	  0.1	  0.2	  0.3	  0.4	  0.5	  0.6	  0.7	  0.8	  0.9	  1	  Pruning	  Threshold	  Frac%on	  of	  Classiﬁca%ons	  Emi1ed	  Figure 2: Classification accuracy at various pruning thresholds.
1	  0.9	  0.8	  0.7	  0.6	  0.5	  0.4	  0.3	  0.2	  0.1	  0	  0	  0.1	  0.2	  0.3	  0.4	  0.5	  0.6	  0.7	  0.8	  0.9	  1	  Pruning	  Threshold	  Figure 3: Fraction of the 144,639 classifications that were actuallyemitted at various pruning thresholds.

831

Conclusion
Activity recognition may produce misclassifications whentrained models attempt to classify real-world behavior. In
our work, we looked to mitigate this problem by pruning a
trained decision tree model by removing leaf labels thattend to produce misclassifications using a thresholding
technique. This automated pruning produces up to 10%
improvement in classification using our data set.

References[1] L. Bao and S. Intille. “Activity Recognition from
User-Annotated Acceleration Data,” In Proceedingsof Pervasive, 2004.
[2] A. Bulling, U. Blanke, and B. Schiele. “A Tutorial on
Human Activity Recognition Using Body-Worn
Inertial Sensors,” ACM Computing Surveys, 46(3),January 2014.
[3] T. Hyunh, U. Blanke, and B. Schiele. “Scalable
Recognition of Daily Activities with Wearable
Sensors,” In Proceedings of LOCA, 2007.
[4] J. Kwapisz, G. Weiss, and S. Moore. “ActivityRecognition Using Cell Phone Accelerometers,” In
Proceedings of SensorKDD, 2010.
[5] J. Lester, T. Choudhury, and G. Borriello. “APractical Approach to Recognizing PhysicalActivities,” In Proceedings of Pervasive, 2006.
[6] H. Lu, J. Yang, Z. Liu, N. Lane, T. Choudhury, andA. Campbell. “The Jigsaw Continuous Sensing
Engine for Mobile Phone Applications,” In
Proceedings of ACM SenSys, 2010.
[7] J. Quinlan. C4.5: Programs for Machine Learning.
Morgan Kaufmann, 1993.
[8] S. Reddy, M. Mun, J. Burke, D. Estrin, M. Hansen,and M. Srivastava. “Using Mobile Phones toDetermine Transportation Modes,” ACM
Transactions on Sensor Networks, 6(2), Feb. 2010.