 Open Access
 Total Downloads : 20
 Authors : C . Leela Krishna, Mr . Shaik Salam, Dr . T . V . Rao
 Paper ID : IJERTCONV2IS15017
 Volume & Issue : NCDMA – 2014 (Volume 2 – Issue 15)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Rough Sets in Spatiotemporal, Multimedia Outlier Detection
C . Leela Krishna
Dept. of CSE,
Sree Vidyanikethan Engg. College, Tirupati, A.P.
Mr . Shaik Salam Associate Professor, Dept. of CSE, Sree Vidyanikethan Engg. College,
Tirupati, A.P.
Dr . T . V . Rao
Head, Dept. of CSE, PVP Siddhartha Inst. of Tech.,
Vijayawada, A.P.
AbstractThe major issue that has drawn the attention of researchers on extracting knowledge from spatiotemporal data and multimedia data is the high availability of data gathered from multiple sources. Spatiotemporal data can be gathered from wireless sensor networks and other environmental monitoring systems. Multimedia data can be gathered from various audio, video files. The data collected from various data sources contain outliers, which are grossly different or exceptional when compared with others. Detection of outliers in the process of knowledge discovery is found to be challenging. In this paper, we are dealing the outlier detection problem to find the top outliers from both spatiotemporal and multimedia data by exploiting rough outlier set extraction (ROSE) method, which is based on the rough set theory in its lower and upper approximations, even with uncertainties in data sets.
Index TermsSpatiotemporal data, Multimedia data, Outliers, Rough sets, Uncertainty.

INRTODUCTION
Data mining can be referred to a process of discovering knowledge from data where the main emphasis is on uncovering interesting data patterns that are hidden in large data sets. Spatiotemporal and multimedia data mining are growing research areas involving the discovery of hidden knowledge in large spatiotemporal and multimedia databases, mainly by detecting periodic and frequent patterns. A database may contain data objects that do not comply with the general behavior or model of the data [4]. These objects are known as outliers. The major applications of outlier detection include credit card fraud detection, intrusion detection in computer networks, and detection of abnormal regions or detecting motion in images. The presence of outliers makes modeling and mining difficult due to the discordance of outliers that are introduced into the data [1]. The most important existing approaches for outlier detection are:

Distributionbased approaches [7] that make use of statistical distributions are used to model the data
and
outliers deviate from the model.

Depthbased approaches [8] that evaluate different layers of convex hulls are computed and the objects
belonging to the outer layers are declared as outliers.

Distancebased approaches [9] that compute distances of every object from a target object.

Densitybased approaches [10] that assign a weight to each sample based on the neighbourhood density.
The proposed method involves detection of outliers from both spatiotemporal and multimedia data through rough sets known as Rough Outlier Set Extraction (ROSE) [1], where rough set theory is used to define outliers in terms of its lower and upper approximations. This paper is organized as follows: Section 2 describes spatiotemporal data mining and Section 3 describes multimedia data mining. Section 4 gives the major concepts of rough set theory that are related to the work. Section 5 introduces the problem definitions. Section 6 gives the ROSE approach to extract spatiotemporal and multimedia outliers. Finally Section 7 concludes the ongoing work.


SPATIOTEMPORAL DATA MINING
A spatial data set is one that has its attributes containing land information or geographical locations on the earth. A temporal data set is one that has its attributes containing several events that are ordered by one or more dimensions of time. Data sets with attributes containing both location information constrained by time information are referred to as spatiotemporal data sets. Data relating to space and time together, having spatial extension along with temporal duration is also referred to as spatiotemporal data. Similarly, a spatial database that stores spatial objects that change with time is called a spatiotemporal database, from which interesting information can be mined [4]. Extraction of implicit knowledge, spatial and temporal relationships stored in spatiotemporal databases is also known as spatiotemporal data mining. For example, to group the trends of moving objects and identify some strangely moving vehicles, or distinguish a bioterrorist attack from a normal outbreak or the flu based on the geographic spread of a disease with time [4]. Spatiotemporal uncertainty is the lack of, or the error in, knowledge about either an objects position on the earth with respect to the latitudes and longitudes or an objects motion at various time intervals.

MULTIMEDIA DATA MINING
Multimedia is defined as a combination of more than one media [2]. Generally, the two types of media are static and
dynamic media [5]. Static media include text, graphics, and images. Dynamic media include animation, audio, video, etc. A multimedia database system stores and manages a large collection of multimedia data, such as audio, video, image, graphics, speech, text, document, and hypertext data, which contain text, text markups, and linkages [4]. Extraction of implicit knowledge stored in multimedia databases is also known as multimedia data mining. It is applicable in picture contentbased retrieval, voicemail systems, videoondemand systems, and speechbased user interfaces to recognize spoken commands [4].

ROUGH SET THEORY
Rough set theory [3] was first proposed by Z. Pawlak, which is used to deal with uncertain, vague and incomplete data. The main idea is based on the indiscernibility relation that describes the indistinguishability of objects. If one cannot represent an object in the form of a crisp set, then such object can be represented by a rough set with the approximate representation of knowledge. A rough set gives the lower and upper approximation of the set that has incompletely specified knowledge.

Information System
An information system is a table consisting of rows and columns, where each row represents an object and each column represents an attribute. Hence, the information system is shown as IS = (U, A) where U is the universe of discourse with a finite set of objects, U = {O1, O2, O3 … On} and A is a finite and nonempty set of attributes A = {a1, a2, a3… an}.

Indiscernibility Relation
The relation between two or more objects where all or some of the values of its attributes taken into consideration are identical is known as an indiscernibility relation. This relation gives the indistinguishability of objects through an equivalence relationship. A relation among various objects is said to be equivalence iff they are reflexive, symmetric and transitive. For B as a subset of A, B A, the indiscernibility relation ISB on U is given as
(1)

Lower and Upper Approximations
Approximations are fundamental to rough set theory, as every set is represented by means of its lower and upper approximations. The equivalence classes induced by the B indiscernibility relation is denoted by [x]B. For any set X, that is a subset of the universe U, XU,
the lower approximation is defined as follows:
B(X) = {x U : [x]B X}, (2)
the upper approximation is defined as follows:
(X) = {x U : [x]B X }, (3)
The lower approximation or positive region is the union of all equivalence classes [12] in [x]B which are aleady contained by the target set, where the objects excluding the target set cannot be included here. The upper approximation or the negative region is the union of all equivalence classes in [x]B that have nonempty intersection [12] with the target set, where the objects excluding the target set can also be included here. The objects in the lower approximation can be certainly classified as members of X on the basis of knowledge in B, and the objects in the upper approximation can only be classified as possible members of X on the basis of B. The boundary region consists of objects that can neither be ruled in nor ruled out [12] as members of the target set X.
BND(X) = (X) – B(X)
(4)

Example
The following table shows an information system containing a collection of multimedia data as a set of objects. The universe of discourse is U = {O1, O2, O3, O4, O5, O6, O7}. The set of attributes is represented as A = {Illustration, Timeline, Movement}. The possible values for both Illustration and Timeline are Yes, No and for Movement the possible values are Static and Dynamic [2].
TABLE I
Information System
Object
Condition Attribute
Illustration
Timeline
Movement
O1
Yes
Yes
Dynamic
O2
Yes
No
Static
O3
Yes
No
Dynamic
O4
No
Yes
Static
O5
Yes
Yes
Static
O6
No
Yes
Dynamic
O7
No
Yes
Dynamic
From the above table, it can be observed that for the Illustration attribute, the set regarding the indiscernibility relation is {O1, O2, O3, O5}, since the objects in the set are indistinguishable to each other as they possess same value of the mentioned attribute. Similarly, for the Timeline and Movement attributes, the sets showing indiscernibility relations are {O1, O4, O5, O6, O7} and {O1, O3, O6, O7} for
Dynamic and {O2, O4, O5} for Static.
For the subset B = {Illustration, Timeline}, the set with indiscernibility relation is {{O1, O5}, {O2, O3}, {O4, O6, O7}}, since the objects in the set have same attribute values based on the knowledge in B. If the target set is X = {O1, O2, O3}, then the corresponding lower and upper approximations are B(X) = {O2, O3} and (X) = {O1, O2, O3, O5} and the
boundary region is BND(X) = {O1, O5}, which is evaluated as
the set difference between upper and lower approximations. This region specifies the data objects that can neither be ruled in nor ruled out [12].


OUTLIER DETECTION PROBLEM
Data objects that are grossly different from others or inconsistent with the remaining objects in the data set are known as outliers [4]. Outliers can be caused by measurement or execution error [4]. The process of extraction of outliers from a data set is known as outlier mining. Outliers present in spatiotemporal data and multimedia data are to be detected by means of rough set theory. The proposed approach finds both spatiotemporal and multimedia outliers.

Problem Definitions
Consider an information system IS = (U, A) with U being the universe of discourse with a data set containing normalized values (between 0 and 1) for all of its objects, and A containing the set of attributes. U can be written as follows:
(5)
where pi represents a set of data objects with i=1,2,…,N is a mdimensional vector and A = {a1, a2, …, am} is the attribute set. When the universe of discourse is given, for an integer n>0 the number of outliers to be evaluated, the degree of dissimilarity for each object with others for every pi U, given as is to be evaluated.
The outlier detection problem consists of finding objects such that
(6)
An noutlier set consists of with the set of objects
+1… N (7)
From the above formulae, the outlierness threshold is considered as which is defined as the minimum value among the n maximum measures computed in U, that belongs to the noutlier set.
The threshold value for the noutlier set is
(8)
The following definitions are applicable in the outlier detection problem from both spatiotemporal and multimedia along with their respective notations given below:
Definition 1. A spatial outlier is an object whose spatial attribute value is different from its closer objects in its neighbourhood.
Definition 2. An object that belongs to the spatial noutlier set is referred to as a Spatial Outlier (Os).
Definition 3. A Temporal outlier is an object whose temporal attribute value is different from its closer objects in its neighbourhood.
Definition 4. An object that belongs to the temporal noutlier set is referred to as a Temporal Outlier (Ot).
Definition 5. A Spatiotemporal Outlier is an object that contains both spatial and temporal outliers (Os,t).
Definition 6. A Multimedia Outlier is an object whose multimedia attribute value is significantly different from its closer objects in the neighbourhood.
Definition 7. A Multimedia Outlier is an object that belongs to the multimedia noutlier set (Om).
An object p U is said to be an outlier and belongs to n outlier set iff . To obtain the degree of dissimilarity, an appropriate measure used is the euclidean distance computed between each object and all the others belonging to U. Euclidean distance between two data objects O1(x1,x2,..,xn) and O2(y1,y2,…yn) in an ndimensional space is calculated by the following formula:
(9)
The real world applications with huge amount of data is found to be unfeasible due to its high computational complexity O (N2) with N = U [1], the cardinality of the data set which gives the number of objects in the data set, as it is obvious from (9). To reduce the complexity, two strategies can be approached by making use of:

knearest neighbors [11] rather than the entire N objects where k<<N.

a pruning strategy to remove all objects that cannot be in the noutlier set.


Spatiotemporal Outlier Detection
In a spatiotemporal context, the measure associated with each object is based on the distances from its spatial knearest neighbors and its temporal knearest neighbors which can be given as:
(10)
where
(11)
(12)
where k>0 is the number of nearest neighbors and NNs(p,pj) specifies the jth nearest spatial neighbor and NNt(p,pj) specifies the jth nearest temporal neighbor. and are chosen in such that + = 1. Definition 3 defines the spatiotemporal outlier detection problem by evaluating a measure in (10).

Multimedia Outlier Detection
In a multimedia context, the measure associated with each
object is based on the distances from its multimedia knearest neighbors which can be given as:
A 4Temporal Outlier Set Ot U gives the set of objects that deviate from the rest with respect to temporal component only and the result is Ot = { p1, p2, p17, p18 }.
A 4Spatiotemporal Outlier Set Os,t U gives the set of objects that deviate from the rest with respect to both spatial and temporal components and the result is Os,t = { p7, p8, p17, p18 }.
(13)
where k>0 is the number of nearest neighbors and NNm(p,pj) specifies the jth nearest multimedia neighbor. Definition 6 defines the multimedia outlier detection problem by evaluating a measure in (13).


ROUGH OUTLIER SET EXTRACTION

Theory
Exploitation of the rough set theory in defining the Outlier Set is rferred to as Rough Outlier Set. For an information system IS = (U, A) with U being a normalized data set consisting of data objects and A being the attribute set. If n > 0 are the required outliers, then an nOutlier Set is described as ) with the BLower and BUpper approximations respectively. The BLower approximation defines the set of objects that can be certainly classified as members of the set O, on the basis of knowledge in B. The BUpper approximation defines the set of possible members of O, on the basis of knowledge in B. The formulae for evaluating both lower and upper approximations are already mentioned in (2) and (3).
To better illustrate the definitions given in Section 5, an example spatiotemporal data set is taken from [6]. It contains
where pi is a normalized three dimensional data set with A = {a1, a2, a3}, with a1, a2 are the spatial attributes and a3 being the temporal attribute. U contains 18 data objects as plotted in Fig. 1. When the values of k and n are fixed as 3 and 4, the outlier sets are computed based on euclidean distance and the resultant outlier sets are computed as follows:
A 4Spatial Outlier Set Os U gives the set of objects that deviate from the rest with respect to spatial component only and the result is Os = {p7, p8, p17, p18}.
Fig. 1. The example data set U
Spatial Outliers can be evaluated by making reduction based on temporal attribute, then the Bindiscernibility relation of U with B = {zi3} will contain the following indiscernibility relation [6]:
IB={{p1,p2},{p3,p9},{p4},{p5},{p6},{p7,p8},
{p10},{p11},{p12},{p13},{p14},{p15},{p16}, {p17},{p18}}.
From the Bindiscernibility relation all the equivalent objects have been obtained and the Blower approximation of the Spatial Outlier Set Os is given as = {{p7, p8}, {p17},
{p18}} and the Bupper approximation of the Spatial Outlier Set Os is given as = {{p7, p8}, {p17}, {p18}}.
Temporal Outliers can be evaluated by making reduction based on spatial attribute, then the Bindiscernibility relation of U with B = {zi1, zi2} will contain the following indiscernibility relation [6]:
IB={{p1,p12},{p2,p13},{p3},{p4},{p5},{p6},{p7},
{p8},{p9},{p10},{p11},{p14},{p15},{p16}, {p17},{p18}}.
From the Bindiscernibility relation all the equivalent objects have been obtained and the Blower approximation of the Temporal Outlier Set Ot is given as = {{p17}, {p18}} and the Bupper approximation of the Temporal Outlier Set Ot is given as = {{p1, p12}, {p2, p13},{p17}, {p18}}.
The following figure shows the spatial, temporal and spatiotemporal outliers detected from the example data set U [6]:
Fig. 2. Detected outlier sets

Algorithm
begin ROSE(U, n, k)
UpperSet = null; LowerSet = null; weight(q)=0;
=0;_prev=0;
WorkingSet = ExtractElements(U);
while (WorkingSet ! = null) do for p U do
for q WorkingSet do
if (LowerSet == null and UpperSet == null) or _prev)then
ds(p,q) = CalculateSpDistance(p,q) dt(p,q) =CalculateTempDistance(p,q) EvaluateKNN(p,q,ds,dt,k)
else
AddNegativeRegion(p)
end if end for
end for
for WorkingSet do
weight(q) = CalculateWeight(q)
UpperSet = UpdUpperApp( _prev,n,weight(q)) LowerSet = UpdLowerApp( ,n,weight(q))
end for
= LowerWeight(UpperSet)
if(!=0) then
_prev=;
end if
U = UWorkingSet
WorkingSet = ExtractElements(U)
end while
return Rough Outlier Set end ROSE()
The Rough Outlier Set Extraction Algorithm receives input the universe U, the number k of nearest neighbors, and the number n of outliers to detect. The output of the (iterative) procedure is the Rough Outlier Set with its Upper, Lower Approximation, and Negative Region. The algorithm selects a small subset of objects, called WorkingSet, from the overall data set U. For all selected objects, the algorithm computes euclidean distances among the objects in the WorkingSet and all the objects of U, considering the spatial components, the
temporal components or both of them depending upon the chosen attribute subset B with respect to the Rough Outlier Set. UpdUpperApp and UpdLowerApp at first iteration create the same set of n top outliers at that step, i.e., the n objects that have a measure higher than the others. Then, at next iterations, UpdUpperApp and UpdLowerApp compute the Lower and Upper approximation of Rough Outlier Set, using the (computed by LowerWeight) threshold. At each iteration i, the pruning strategy selects objects from U with their measure under the computed threshold to build the Negative Region. The LowerWeight function computes the threshold, which is computed as the weight minimum value among the weight maximum n values.


CONCLUSIONS
This paper provides a rough set approach as a solution to the outlier detection problem in both spatiotemporal and multimedia data. The detected outlier set through rough sets is named as rough outlier set. The computational benefit of using euclidean distance on only some of the nearest neighbours instead of all data objects is also considered. We hope this work will attain further interest in various problems.
ACKNOWLEDGEMENTS
The authors would like to acknowledge A. Albanese, S. K. Pal and A. Petrosino for their valuable discussions.
REFERENCES

A. Albanese, S. K. Pal, A. Petrosino, Rough Sets, Kernel Set, and Spatiotemporal Outlier Detection, IEEE Trans. Knowledge and Data Eng., vol. 26, no. 1, pp. 194207, Jan. 2014.

M. A. Rahman, M. Lazim, F. Mohamed, Applying Rough Set Theory in Multimedia Data Classification, Intl Journal on New Computer Architectures and Their Applications, pp 633693, 2011.

Z. Pawlak, Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer, 1991.

J. Han and M. Kamber, Data Mining Concepts and Techniques, Elsevier.

J. Griffioen, B. Seales, R. Yavatkar, Content Based Multimedia Data Management and Efficient Remote Access, Extrait de la Revue Informatique et Statistique dens les Sciences Humanies. Vol 1(4), pp. 213233 (1997).

The Computer Society Digital Library, http://doi.ieeecomputersociety.org/10.1109/TKDE.2012.234

V. Barnett and T. Lewis, Outliers in Statistical Data. John Wiley & Sons, 1994.

M. Breunig, HP. Kriegel, R.T. Ng, and J. Sander,LOF: Identifying Density Based Local Outliers, Proc. ACM SIGMOD Intl Conf. Management of Data, pp. 93104, 2000.

A. K. Ghosh and P. Chaudhuri, On Maximum Depth Classifiers,
Scandinavian J. Statistics, vol. 32, no. 2, pp. 7384, 1998.

E. Knorr and R. Ng, Algorithms for Mining DistanceBased Outliers in Large Data Sets, Proc. 24th Intl Conf. Knowledge Discovery and Data Mining, pp. 224228, 1998.

S. Ramaswamy, R. Rastogi, and K. Shim, Efficient Algorithms for Mining Outliers from Large Data Sets, Proc. ACM SIGMOD Intl Conf. Management Data, pp. 427438, 2000.

Rough set, http://en.wikipedia.org/wiki/Rough_set