DIASTowards Continuous Monitoring of Environment under Uncertainty: A Fuzzy Granular Decision Tree ApproachPreetham N. Reddyf2015174@goa.bits-pilani.ac.in1Sahith N. Dambekodif2015192@goa.bits-pilani.ac.in1Tirtharaj Dashtirtharaj@goa.bits-pilani.ac.in0Data Science Research Group, BITS Pilani
,
Goa Campus, Goa 403726
,
IndiaDepartment of EEE, BITS Pilani
,
Goa Campus, Goa 403726
,
India20175
Smart monitoring of environment has been an essential area of research where decision-making process is inevitable. Reliability of the whole system depends on the stability and consistency of its decision-making unit. Real-time decision making is another challenge in the eld on which the research community has been focusing on improving the performance of the underlying models. e underlying models are usually the learning models, that act as a smart engine aer being suciently trained for the process. In this paper, we propose to use a decision tree model that has the capability of handling uncertainty in the acquired data from the environment. e resulting model is called as Fuzzy Granular Decision Tree (FGDT). Series of evaluation of FGDT shows that the model is stable and powerful for the presently considered problem.
Towards advancing the eld forward, a research was carried out
very recently by Huerta et al.[
2
] that focused on online
decorrelation of humidity and temperature in chemical sensors for
continuous monitoring. e work focused on automated processing of data
from simultaneous and continuous readings of the variations in
humidity and temperature in the targeted environment. eir work
included eight(8) metal-oxide sensors (MOX) sensors that were
continuously sensing the environment for 537 days with a
sampling rate of 1 sample per second [
2
]. ey estimated the eects of
variations in air humidity and temperature on the chemical sensors
signals by using standard energy band model with an assumption
that the variations in sensor conductivity can be expressed as a
nonlinear function of changes in the energy bands in the presence
of external humidity and temperature. eir study showed that
the major factors that were aecting the environment were the
changes in humidity and the correlated changes in temperature and
humidity. To visualize the process, they used a gas discrimination
system that could discriminate among banana, wine, and baseline
response. ey had used a variant of Support Vector Machine (SVM)
algorithm to build the discriminatory model for the process.
In the process of continuous environment monitoring, there lies
a certain degree of uncertainty in the acquired data. An uncertainty
in the acquired data could lead to the failure or adverse functioning
of the system. e uncertainty could arise due to the following
situations such as failures of sensors, a sudden change in
environment due to additional and unknown factors. In such a case, the
discriminatory model that was built may not be trustworthy and
hence the results should, in turn, be imprecise. is impreciseness
or degree of uncertainty in the acquired data or desired outcome
is called ‘fuzziness’. An adaptive system that is meant to serve
for the purpose of continuous environment monitoring should not
only just adapt to the environmental changes with time but also
should be robust with respect to the uncertainties as read through
its sensors. To solve the purpose of handling uncertainty or the
fuzziness present in the acquired data, and to make a robust decision
based on the data, we propose a granular method – that specically
captures the uncertain inputs – to be induced within an adaptive
system. e research carried out by [
2
] was experimentally sound
and our present work mainly serves the purpose of embedding the
uncertainty aspect of the work. In our present work, we redesign a
discriminatory model that also incorporates possible uncertainty
in the acquired data. It should be noted that our work is validated
with the experimental data from [
2
], further information of which
has been presented in the following sections.
e rest of the paper is organized as follows. e proposed
and implemented model has been discussed in the section 2. e
results that have been obtained for the present problem has been
elaborated in section 3. e obtained results are discussed in the
section 4 and the paper has been concluded in the section 5.
2
METHODOLOGY
Our proposed work has following major phases: data acquisition
phase, uncertainty handling phase, discrimination phase.
2.1
Data acquisition phase
In the data acquisition phase, the sensors acquire the data from
the environment for further processing in later phases. For more
information, one could refer [
2
].
2.2
Handling uncertainty in acquired data
In this work, uncertainty in the acquired data has been taken care
with the use of feature transformation using a special fuzzy
membership function [
3, 4
]. e membership function transforms a
single sensor reading (datum) to granules containing the
information of dierent belongingness. For example, a temperature reading
of 38° can be called as a low temperature, medium temperature or
high temperature. Hence, it can have some degree of belongingness
to each of low, medium and high temperature. In this work, we
chose to use the Gaussian fuzzy membership function that is given
in equation (1) where a is the maximum value of the membership
function, σ is the standard deviation of the readings obtained by
a sensor. e value of xˆ is dierent for each of the low, medium
and high belongingness. For transformation to low degree of
belongingness, xˆ = minfxg; for transformation to medium degree
of belongingness xˆ = meanfxg; and for transformation to higher
degree of belongingness xˆ = max fxg. Please note that x is a vector
that contains all the sensor readings for any particular feature. For
ith feature (alternatively, for ith sensor), x should be represented
as xi.
μ¹x º = a exp
¹x
xˆº2
2σ 2
(1)
e full transformation can be visualized in Figure 1 that
represents the curve for low, medium and high membership function
(from le to right). e belongingness can have a maximum value
of 1 (a = 1) and a minimum value of 0. So, for a single datum, the
transformation function generates three dierent granules. At a
particular time t , if there are n sensors, there can be n sensor
readings, called features. Aer the transformation, the feature vector
gets transformed to a higher dimension of 3n.
A major intuition behind such a high dimensional transformation
is that a discriminatory model is expected to perform beer with
high dimension than in low dimension. is is as per Cover’s
theorem on the separability of paerns [
5
]. Since this work is
focused on discrimination of the sensor readings into dierent
classes, the transformation should make the paerns separable in
higher dimensional space, if they are not easily separable in a lower
dimension. In a further section, we shall see that this is indeed the
case for this specic problem.
Discrimination is the process of assigning a class level to a set of
inputs i.e. a set of sensor readings at a particular time. Consider
a set of sensor readings at any particular time be represented as
fx1; x2; : : : ; xn g whose class is unknown. It should be noted that
there are three classes in the present work: banana, wine, and
baseline response. Aer the fuzzy transformation, the vector can
be represented as
(2)
x = fx1low ; x1medium ; x1high ; x2low ; x2medium ; x2high ; : : : ;
xnlow ; xnmedium ; xnhigh g
e discrimination phase works with a model that has been built
with prior knowledge, called training data, to discriminate the
sensor readings in the real time, called test data. In this work,
we implement a decision tree (DT) classier that works with the
transformed fuzzy granular feature space that has been obtained
from the second phase. erefore, the whole model can be known as
Fuzzy Granular Decision Tree (FGDT). e principal reason behind
choosing DT over other machine learning models is that it is
nonparametric that can learn from the training data in a supervised
manner. More specically, we implement CART that is very similar
to C4.5 decision tree [
6
]. e FGDT predicts the class of a set of
sensor readings by learning simple decision rules inferred from the
features. For completeness and clarity of the readers, we present
the working principle of the FGDT as follows.
Given a training dataset in fuzzy granular input feature space
where each of the features is represented as xi 2 R3n . Note that
each xi is a vector in 3n dimension represented as equation (2). Let
the class labels be represented as d. e FGDT recursively partitions
the training paern space such that the paerns with same class
labels are grouped together. e following Algorithm 1 explains
the generic steps of the FGDT that take the fuzzy granular sensor
readings training instances (Det r ain ) and generates a decision tree
from that (eT).1
1eesymbol is used to represent uncertainty in input data and the tree is generated
from this fuzzy granular data.
Data: A transformed training set, Det r ain
Result: A decision tree, eT
if All the instances belong to same class then
Return a eT with a leaf node labelled with the class;
end
end
if Det r ain = fϕ g then
Return eT = ϕ with warning;
if If there is no feature in Det r ain then
Returns a leaf labeled with the most frequent class or the
disjunction of all the classes)
end
while Until stopping condition is not met do
Find the feature j 2 Det r ain with highest informational
gain or lowest impurity;
Based on feature j, Split the present node of eT to form
sub-trees eTl ef t , eTr ight ;
Repeat for eTl ef t , eTr ight ;
end
Algorithm 1: FGDT algorithm (e rst three if statements are
called base cases. An impurity function can also be used for the
information gain: lower the impurity, higher the information gain
and vice versa.)
m
Õ
e stopping conditions while generating the eT from Det r ain
could be one of the following. A fully grown most generalized
tree has been obtained, the training paern space has been well
partitioned into multiple sub-spaces based on classes, the generated
tree returns lowest error on validation data2. For measuring the
impurity, an ‘entropy’ estimate is used which is given in equation
(3).
H ¹X; eTº =
P¹Xi º log2¹P¹Xi ºº
i=1
Here, P¹ º is the probability estimate. Based on the estimation in
equation (3), the entropy before split and entropy aer spliing a
node is computed for each feature. e feature which would provide
lowest entropy aer split is considered to be split up based on some
condition, usually a threshold. Entropy aer split is computed from
the entropy estimate of each of the new sub-trees as
(3)
k
Õ
i=1
Haf t er Split ¹X; eTº =
P¹Xº log2¹Hi ¹Xi º; eTi º;
(4)
where, k is number of splits at a node of the tree, Hi ¹Xi º; eTi º is the
entropy measure for the sub-tree that would be produced aer split.
By using these entropy estimates that is entropy before split and
entropy aer split, the information gain which is denoted as G can
be computed as
G = Hbef or eSplit ¹X; eTº
Haf t er Split ¹X; eTº
(5)
e feature that would produce the highest information gain should
be used to split at a particular node in the tree eT. It should be noted
that the discussion and algorithm implemented in this work splits a
2A set of instances that were not used during the training process but are used to
check the performance of the generated model aer training. ese are not test data.
node of the tree into two sub-trees (binary split). It is also possible
to split a node into multiple sub-trees (multiple splits) based on
more than one thresholds at the node [
6
].
Eect on computational complexity? – It is quite obvious that the
size of the feature set is increased by the transformation into the
fuzzy feature space under the three membership functions such
as low, medium and high. If we consider that there are ninput
number of features in the original data, aer the transformation
into the fuzzy paern space, the size becomes 3 ninput . If the time
complexity for the classical decision tree learning is T ¹ninput º, the
FGDT has a time complexity of T ¹3 ninput º. However, it should
be noted that a fuzzy granular decision tree learner would have to
learn once with the available training data; and the learned model
is just deployed for its testing. So, this cost over time would occur
just once. Moreover, with the availability of high-performance
computing architectures, this complexity could be lowered and
scalability of the proposed model could be improved. Moreover,
although a decision tree learner learns from the data by partitioning
the space into multiple subspaces with conditions, it is already
shown that the decision tree scales well with higher dimensional
data [
7
].
3
RESULTS
An adaptive system should not only just adapt to the environmental
changes but also should be robust with respect to the uncertainties
as reading through the sensors. is could be done via robust
modeling of the environment or via robust decision making withing
the system. However, our present work demonstrates the former
category where the implemented model adapts to the changes in
the environment by also incorporating the possible uncertainties by
transforming the problem into an imprecise problem. To support
our claim about the improvement, we used the experimental data
available from the work of Huerta et al. [
2
] to study the
performance of our proposed fuzzy granular model, FGDT. To elaborate,
to evaluate the impact on discrimination performance of our
proposed FGDT due to decorrelation of signals from temperature and
humidity sensors, four dierent feature sets were used. e rst
set of features is a set of raw sensor time series (RS); the second
feature set is a set of raw sensor data with humidity and
temperature (RS, T, H); the third set of features is a set of ltered data (FS)
by decorrelating sensors; the fourth set of features is a set of raw
sensor data with ltered sensor data (RS, FS). We used these same
feature set for a proper evaluation of our proposed model. However,
additionally, we also use a new dataset that also contains ‘t0’ and
‘dt’ along with ltered sensor data (FS) for evaluation.
To properly estimate the generalization ability of the proposed
FGDT model, we used the standard procedures in machine learning
to evaluate the performance of FGDT when discriminating
samples not used for training the classier so as to remove evaluation
bias during the testing phase. ere are 919438 number of
sensorreading instances in the dataset. e available data was randomly
partitioned into 80% and 20%. e partition with 20% of data was
used for the independent test. e 80% partition was used for 5-fold
cross validation (5CV). For a fair comparison, we used accuracy as
the performance evaluation measure for this work as the same was
also used in [
2
], although accuracy should not be always considered
reliable [
8
]. However, as the number of instances in the dataset is
very large, at the order of 9 105, it would not have a large eect on
the accuracy measure. We considered the fold-wise performance in
5CV along with independent test performance for the evaluation
purpose. e results have been noted and depicted in Table 1. To
have a beer evaluation of the model, the 20% partition was not
made xed from the beginning, rather, with each fold evaluation,
the test partition has been chosen.
A comparison of the result obtained by our proposed FGDT
with the results obtained by Huerta et al.[
2
], as shown in Table 2,
suggests that the proposed FGDT model is superior to the ISVM
model for this problem for most of the datasets with selected
features. However, for the dataset with only FS as feature set, the
performance of FGDT is far lower than the ISVM model. is is
probably because of the fact that the FS dataset is quite dicult to
be separable which could be revealed from a sample plot between
F1 vs F2 of the FS feature set (see Figure 2).
DISCUSSION
e FGDT algorithm does handle uncertainty in the acquired data
by transforming it to a feature space that is higher in dimension
than that of the original data. is could led the decision tree
classier capture the underlying relationship between the inputs
and outputs in a beer way. is is evident from the fact that
the higher dimension of the transformed data makes the visibility
sparse and hence drawing a clear boundary between two dierent
classes becomes easy [
5
], which could not have been possible by
using SVM classier as used in [
2
]. More specically, when a lower
dimensional input space is projected onto a higher dimensional
space, the sparsity in the projected space increases and thereby
increasing the chance of learning a possibly-optimal hyperplane
that would be serving as the boundary among various resulting
groups or classes of paerns. Technically, the distance between
any paern in the project space and the learned hyperplane does
improve which makes a strong impact on the training of the decision
tree learner. is interpretation could probably be true because of
the fact that a more generalized model that is built aer training and
validation would possess a higher capability of generating accurate
results during independent real-time tests. Moreover, the number
of instances in a training set and the number of features do also play
crucial roles in the process. With a higher number of instances with
a small set of features might not generate an adequate function that
would generate output from the inputs. Aer transformation to
fuzzy space and hence increasing the dimension of the input space,
such a function would be possible for the purpose. is could lead to
the proper generalization of the FGDT and hence the independent
test performance. One should note that the present work uses the
CART algorithm available in Scikit-learn [
9
]. However, one could
try many other machine learning approaches for the same task
aer incorporating our proposed fuzzy granular transformation
approach as a step in feature engineering before training of the
learning model.
5
CONCLUSIONS
e uncertainty arising in the acquired data from the environment
in the process of continuous home monitoring has been handled by
developing a new fuzzy granular approach that has been combined
with a decision tree for decision making. e proposed model FGDT
has been evaluated with regard to experimentally validated data
from continuous monitoring environment. e performance of our
FGDT model is found to be superior to a recently published work
on the same problem. Moreover, the statistical results also show
that FGDT has not only beer discrimination capability but also it
is quite stable and consistent.
Although the present work discusses the applicability of fuzzy
modeling towards the uncertainty handling in the aspect of
environmental monitoring systems; there are numerous possible
applications of such techniques in real-world problems such as medical
diagnosis [
10
], robotic navigation control mechanisms [
11, 12
],
handling uncertainty in soware testing [
13
]. All these mentioned
real-world problems may not always be subject to precise
computation, and hence uncertainty handling methods such as fuzzy
granular decision tree (FGDT) approach would aid to achieve greater
performance of the intended adaptive systems.
[1]
JoeyFBoatman and Bryan S Reichel
.
Environment monitoring system
,
April 6 1999. US Patent 5
,
892
,
690
.
[2]
RamonHuerta
, iago Mosqueiro, Jordi Fonollosa, Nikolai F Rulkov, and
Irene
Rodriguez-Lujan.
Online decorrelation of humidity and temperature in chemical sensors for continuous monitoring
.
Chemometrics and Intelligent Laboratory Systems
,
157
:
169
-
176
,
2016
.
[3]
SushmitaMitra
, Rajat K De, and
Sankar K Pal
.
Knowledge-based fuzzy mlp for classication and rule generation
.
IEEE Transactions on Neural Networks
,
8
(
6
):
1338
-
1350
,
1997
.
[4]
TirtharajDash
, Sanjib Kumar Nayak, and
HSBehera
.
Hybrid gravitational search and particle swarm based fuzzy mlp for medical data classication
.
In Computational Intelligence in Data Mining-Volume1
, pages
35
-
43
. Springer,
2015
.
[5] omas
MCover
.
Geometrical and statistical properties of systems of linear inequalities with applications in paern recognition
.
IEEE transactions on electronic computers
, (
3
):
326
-
334
,
1965
.
[6]
LeoBreiman
, Jerome Friedman,
Charles J Stone
, and Richard A Olshen. Classi
- cation and regression trees
. CRC press,
1984
.
[7]
GuoshengLin
,
ChunhuaShen
, Qinfeng Shi, Anton van den Hengel, and
DavidSuter
.
Fast supervised hashing with decision trees for high-dimensional data
.
In Proceedings of the IEEE Conference on Computer Vision
and Pa
ern Recognition
, pages
1963
-
1970
,
2014
.
[8]
SiddharthDinesh
and
TirtharajDash
.
Reliable evaluation of neural network for multiclass classication of real-world data
.
arXiv preprint arXiv:1612.00671
,
2016
.
[9]
FabianPedregosa
, Gae¨l Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand irion, Olivier Grisel, Mathieu Blondel, Peter Preenhofer, Ron Weiss,
Vincent Dubourg
, et al.
Scikit-learn: Machine learning in python
.
Journal of Machine Learning Research
,
12
(Oct):
2825
-
2830
,
2011
.
[10]
TanisthaNayak
,
TirtharajDash
,
D ChandrasekharRao
, and
Prabhat K Sahu
.
Evolutionary neural networks versus adaptive resonance theory net for breast cancer diagnosis
.
In Proceedings of the International Conference on Informatics and Analytics, page 97. ACM
,
2016
.
[11]
TirtharajDash
, Tanistha Nayak, and Rakesh Ranjan Swain.
Controlling wall following robot navigation based on gravitational search and feed forward neural network
.
In Proceedings of the 2nd international conference on perception and machine intelligence
, pages
196
-
200
. ACM,
2015
.
[12]
TirtharajDash
.
Automatic navigation of wall following mobile robot using adaptive resonance theory of type-1
. Biologically Inspired Cognitive Architectures,
12
:
1
-
8
,
2015
.
[13]
SalmanAbdulMoiz
.
Uncertainty in soware testing
.
In Trends in Soware Testing
, pages
67
-
87
. Springer,
2017
.