Numerous algorithms have been proposed to detect outliers. However, for this paper, the approach adopted is exclusive to the data-set under consideration. Since the approach is meant exclusively for the data-set, it may be termed as a data-oriented approach. This paper may be the first to use to a data-oriented approach for outlier analysis.

Data-set Description

The Data-set used in this paper was made available by Dr. Jean Paul Calbimonte who is an active researcher in the OpenSense project. Size of the data-set is more than 16 million rows. Around 100000 rows of this data-set were used to build machine learning models while other rows of this data-set were used to build a data stream that these machine learning models could use in prediction.

The attributes in the data-set are:

In OpenSense project, sensors were positioned on top of the buses (public transportation) to measure pollution levels in Lausanne city. The term LDSA stands for lung deposited surface area. It is a way to measure the quantity of particles

Table I: Data Attributes and their respective range of values

10 stations indicated in the table I include both static and mobile stations.

Uniform Random sampling is a method for summarizing multidimensional data streams [1]. Using this method, data-sets could be sampled. This sampling was applied on the data-set described in Table I. The data-set obtained from sampling (say data-set I) was treated in the following manner:

CODB Algorithm was applied over data-set I to detect outliers. Further, data-set I and outliers detected in this data were used for building machine learning models that could learn from a data stream and find outliers in it.

Station is a numerical attribute but it may be used as a class (nominal) attribute. The advantage of using Station attribute as a class attribute is that class labels may be assigned to each row in the original data-set and also data-set I (the data-set obtained from sampling). An instance in Data-set I is of the form (Station, Latitude, Longitude, LDSA) where Station is a nominal attribute and other attributes are numerical.

Class Outliers: Distance Based (CODB) Algorithm was applied over the data-set I in the following manner:

Table II: Paired Stations in Data-set I

Where T is the instance for which COF (T) (degree of being a class outlier) is evaluated and K is number of nearest neighbors. While evaluating Dev (T) and K-Dist (T), three numerical attributes within the data-set are used, namely, Latitude, Longitude and LDSA. The value of PCL (T, K) is a number between 0 and K and indicates nearest neighbors that belong to the same class (station attribute). CODB algorithm was applied over data values belonging to each of the five pairs of Stations in the manner described above. After running initial experiments on data-set I, maximum value of deviation (Dev (T))) was found to lie in thousands and maximum value of K-Dist (K-Dist (T)) was 0.0. Since maximum value of K-Dist was 0.0, corresponding parameter may be any arbitrary real number between 0 and 1 as suggested in [2]. Number of nearest neighbors (K) were set to 7 as suggested in [2]. The parameters with their corresponding values are shown in the table III below. Given the varying quality of measurements obtained from different sensors used in the OpenSense project, 10% of the data values in data-set were regarded as outliers.

Table III: Parameters with their respective values

IV Outlier Detection In Data Stream

For detecting outliers in the data stream (detailed description of the data stream may be found in data-set description), an algorithm should be chosen that should build machine learning models using a small sample of data and these machine learning models may be used for prediction. Further, the machine learning models should learn while carrying out prediction. Hoeffding tree (VFDT) provides a robust solution [3] for this requirement. Hoeffding tree was trained over data-set I and also over the outliers detected in data-set I. A separate Hoeffding tree algorithm was trained over five pair of stations shown in table (IV), therefore, five machine learning model were obtained. The efficiency of each model is shown in the table below.

Table IV: Efficiency for pairs of station

Since minority class (outlier class) is 10% of data-set I while majority class (i.e. non- outlier class) is 90% of data-set I, precision and recall must be used to verify the accuracy of the five machine learning models. In order to do so, 10 fold cross validation is applied. Table (V) shows the precision and recall for each pair of stations.

Table V: Precision and Recall value for each pair

This discussion is about the generalizability of the approach. Since, Uniform random sampling was applied to the-data-set, the complete data-set need not be inspected for discovering patterns in the data-set. As described in the methodology for outlier detection section, each row in data-set is independent of all other rows due to treatment of station attribute. Therefore, relation among attributes of the data-set are identified as shown in methodology for outlier detection section, thus making the approach data-oriented. This approach is contrary to the approach adopted by the authors in [4].The authors adopt an algorithmic approach where a novel algorithm, kernel k-means is used for unsupervised clustering rather than the traditional k-means method.

The approach shown in this paper is specific to OpenSense data. In order to come up with generalized approaches, it is necessary to find common properties in data obtained from various sensor networks. These common properties could be used to design generalized approaches.