ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Partitioning Clustering Algorithms for Data Stream Outlier Detection

Dr. S. Vijayarani1, Ms.P.Jothi2
  1. Assistant Professor, Department of Computer Science, School of Computer Science and Engineering, Bharathiar University, Coimbatore, Tamilnadu, India
  2. M.Phil Research Scholar, Department of Computer Science, School of Computer Science and Engineering, Bharathiar University, Coimbatore, Tamilnadu, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Recently many researchers have focused on mining data streams and they proposed many techniques and algorithms for data streams. They are data stream classification, data stream clustering, and data stream frequent pattern items and so on. Data stream clustering techniques are highly helpful to cluster the similar data items in data streams and also to detect the outliers, so they are called cluster based outlier detection. The main objective of this research work is to perform the clustering process and detecting the outliers in data streams. In this research work, two partitioning clustering algorithms namely CLARANS and E-CLARANS (Enhanced Clarans) are used for clustering and detecting the outliers in data streams. Two performance factors such as clustering accuracy and outlier detection accuracy are used for observation. By examining the experimental results, it is observed that the proposed ECLARANS clustering algorithm performance is more accurate than the existing algorithm CLARANS.





Keywords

Data stream, Data stream clustering, Outlier detection, CLARANS, E-CLARANS

INTRODUCTION

A data stream is an unremitting, immediate, stream flow of sequence of items and it is not possible to control the order in which data item arrive, or not possible to store these entire data items. Some of the applications of areas in which data streams generated are sensor networks, traffic management, call detail records, blogging and twitter posts [1].Due to be short of resources where as this type of huge data, the modern data mining systems are not sufficient and equipped to deal with them. Data stream clustering is a well-known task in mining data stream, clustering is known as grouping related objects into a cluster. With the help of data stream clustering method [2], we can detect the outliers, and the outlier is nothing but it is an object that does not fulfil with the behaviour of normal data objects. Applications of outlier detection are web logs, fraud detection and click streams, communication of telecoms and web document. Clustering based outlier mining [14] methods are called as unsupervised in nature and its main objective is to find the outlier from the data stream using partitioning cluster based method. The object which does not belong to any cluster or belongs to a small cluster is affirmed as outlier, and the outlier detection process highly depends upon the clustering technique.
The remaining section of this paper is organized in the following way. Section 2 illustrates the review of literature. Section 3 describes how the CLARANS and E-CLARANS clustering algorithms are used to detect outliers in data streams. Section 4 discussed about the experimental results and Conclusions are given in Section 5.

RELATED WORK

In this paper [8] the author presented a clustering algorithm called CLARANS which is based on randomize search. The authors had developed two spatial data mining algorithms SD (CLARANS) and NSD (CLARANS). The experimental results and analysis indicated that both algorithms are effective, and can lead to discoveries that are difficult to obtain with existing spatial data mining algorithms. Finally, their experimental results showed that CLARANS is more efficient than existing clustering methods.
The paper [4] discussed a literature of several clustering procedures and multivariate outlier procedures. And also the features of multivariate outliers are also discussed, as well as the applications are highlighted in this survey. Finally the authors discussed about further research challenges on multivariate outliers.
In this paper [5] authors conversed about partitioning clustering based outlier detection for data streams. In this each and every data are entered into a specify size of window, and also they reported each and every data as outlier and also store the data. By using K means algorithm, they have been found small cluster, which is faraway to other clusters and termed as outlier.
In this paper [9] authors compared two partitioning clustering approaches namely CLARANS and FUZZY C MEANS. By measuring the clustering accuracy and outlier accuracy, the performance of clustering and outlier detection is better in CLARANS clustering algorithms.

METHODOLOGY

In data stream, the clustering technique is applied for grouping the data items and also detecting the outliers. Clustering and Outlier detection are most important problems in data streams. The main objective of this research work is to analyse the performance of the two partitioning clustering algorithms namely CLARANS and E-CLARANS for detecting the outliers. The system architecture of the research work is as follows as
A. DATASET
Dataset which have been used in this research work is Pima Indian data set; it contains 768 instances and 8 attributes. This dataset is taken from UCI machine learning repository [3]. Data stream is an abundant flawless sequence of data and it is not possible to store the complete data stream, due to this reason we divide the data into chunks of same size in different windows.
B. CLUSTERING
Cluster analysis is used in a various number of applications; they are stock market analysis, data analysis, image processing and financial market analysis 14]. In data streams the clustering is one of the sub-process areas which are used to group the objects as well as it is used to detect the outliers efficiently and also clustering is one of the unsupervised action in data streams. The data stream clustering are different types of approaches they are distance based, grid based, partition based, hierarchical based and so on.
C. OUTLIER DETECTION
Outlier detection over streaming data is active research area from data stream mining that aims to detect object which have different [5] behaviour, exceptional than normal object. An outlier is an item that is notably unrelated or incompatible to other data object whereas weblogs click stream telecommunication, fraud detection, documents of web are the application areas of outlier detection in data streams. The other specified names of outlier detection are termed as noise, anomalies, indifferent, not catchable to the related object, and unknown. The clustering based outlier detection is a best technique to manage this problem. For our research we have used partitioning cluster based outlier detection algorithms CLARANS and E-CLARANS.
D.CLARANS
This method involves partitioning clustering algorithm in data streams [9]. First the data’s are splitted into chunks of same size in different windows, after that consider each database(s) into data point (dp), partition of size=s/p, along with max neighbor of k=3. Then the minimum cost for each data point (dp) identifies the neighbor value, and it follows the condition i=1and j=1.Then the distance for each data point is calculated and also choose maximum distance (n) for each data points, if (s) has a lower cost, set current to(s), are increment j by 1.when j > max neighbor, compare the cost of current with minimum cost. If the cost value is less than (<) min cost, set minimum cost to current of cost value. Finally group the cluster, in order to satisfy the threshold value≤ min cost. Finally nodes are clustered and outliers are identified.
image
E. E-CLARANS (Enhanced Clarans)
In E-CLARANS, first the data are splitted into chunks of same size in different windows, after that consider each database(S) into data point (dp), partition of size=s/p, along with max neighbor of k=3. Then the minimum cost for each data point (dp) is identified the neighbor value, and it follows the condition i=1and j=1.Then calculate the distance for each data points and also choose maximum distance (n) for each data points. Set current to an arbitrary node in n: k, for each data point we have to set j to 1along with a random neighbor (s) of current value, and also calculate the cost differential of the two nodes. If (s) has a lower cost, set current to(s) is increment j by 1. when j > max neighbor, compare the cost of current with minimum cost. If the cost value is less than (<) min cost, set minimum cost to current of cost value. Finally group the cluster, in order to satisfy the threshold value≤ min cost. Then lastly nodes are clustered and detect outliers.
image

EXPERIMENTAL RESULTS

We have implemented these two partitioning clustering algorithms in MATLAB 7.10 (R2010a). In order to evaluate the performance of the algorithms, the two factors namely clustering accuracy and outlier accuracy are used. The different sizes of the window are 3 and 5.

A. CLUSTERING ACCURACY

From the above figure-2, it is observed that proposed E-CLARANS clustering algorithm performs better than CLARANS clustering algorithm.

B. OUTLIER ACCURACY

From the above figure-3, it is observed that proposed E-CLARANS clustering algorithm performs better than CLARANS clustering algorithm.

CONCLUSION

Data streams are fast and limitless arrival of ordered and unordered data, by using of data streams clustering technique we can handle those data. Detecting outliers in data stream is one of the challenging research problems. In this paper, we have analysed the performance of CLARANS and E-CLARANS clustering algorithm for detecting the outliers. In turn to find the best clustering algorithm for outlier detection two performance measures are used. From the experimental results it is come to know that the outlier detection and clustering accuracies are more efficient in proposed E-CLARANS while compared to CLARANS clustering.

Tables at a glance

Table icon Table icon
Table 1 Table 2

Figures at a glance

Figure 1 Figure 2 Figure 3
Figure 1 Figure 2 Figure 3

References