Dhaka University Of Engineering & Technology, Gazipur

works have taken initiative to saving running time of K-Means clustering algorithm [29].Another problem of K-Means algorithm is that it‘s only forms the spherical clusters whichdegrade the accuracy of finding meaningful patterns of large data.Density-based spatial clustering of applications with noise (DBSCAN) is one of theprominent density-based clustering techniques to find the data patterns by means of nonspherical clusters. Density-Based Spatial Clustering of Applications with Noise (DBSCAN)is a density-based clustering algorithm because it finds a number of clusters starting from theestimated density distribution of corresponding nodes. It is challenging task to estimatedensity in advance. Some research works try to solve this difficulty [21]. Another problem ofDBSCAN technique, it is highly depends on two user-defined parameters, namely radius ofthe cluster (Eps) and minimum number of points required in the cluster (MinPts) whichdegrade its clustering performance. In the real world, it is very challenging task to find theoptimal value of Eps and MinPts in advance. Some research works have taken initiative tosolve this problem [23] [36] [37] [38] [39] [40]. However, these research works may notovercome the difficulty of setting the value of K, Eps and MinPts which is the main concernof this thesis.1.3 MotivationIn the last few decades, many studies have focused on the development of different clusteringalgorithms. The K-means algorithm is one of the familiar clustering techniques which havebeen widely used for data mining. The K-Means algorithm works on three different stages. Inthe first stage, this algorithm takes a specific number of clusters K as an input. In the secondstage, it chooses the number of K centroid for the given dataset. In the final stage, it forms theK number of clusters where each cluster represents a local minimum. In the real-worldproblem, it is challenging to find the optimal value of K in order to perform the clustering ofthe unknown dataset [1]. To remove this difficulty, some research works have taken initiativefor improving the cluster quality of large dataset. However, these research works may notovercome the difficulty of setting the value of K which is the main concern of this thesis.The K-Means algorithm is only forms the spherical clusters. It is another problem of The KMeans algorithm. However, many real-world data sets required non-spherical clusters toidentify the accurate data pattern.3

Density-based spatial clustering of applications with noise (DBSCAN) is one of theprominent density-based clustering techniques to find the data patterns by means of nonspherical clusters. DBSCAN mainly focusing on minimizing the number of input parameters,discovering clusters with arbitrary shapes, clustering large data efficiently, no need for priorknowledge of the number of clusters, and handling noise [2]. DBSCAN have severalapplications in different field like medical images, satellite images, anomaly detection intemperature data, and GPS data in the literature [2]. It has the ability to find the spherical aswell as non-spherical clusters from large datasets. To do this, DBSCAN technique highlydepends on two user-defined parameters, namely radius of the cluster (Eps) and minimumnumber of points required in the cluster (MinPts) which degrade its clustering performance.Because, if a larger value is chosen for Eps then DBSCAN forms the clusters havingdissimilar data. On the other hand, if a small value is chosen for Eps, then this techniqueforms the clusters having a small amount of similar data. In such cases, the exact value of Epsand MinPts are challenging to find which one of the concerns of this thesis is.By considering the above research gaps, this research aims to develop a dynamic K-meansalgorithm and DBSCAN algorithm so that the good quality clusters can be found with betteraccuracy.1.4 ObjectivesThe specific research objectives of this thesis are as follows:1. To identify the limitations of existing K-means and DBSCAN algorithms,specifically, optimal parameter selection problem.2. To design a new K-means and DBSCAN algorithm that can provide the good qualityclusters by means of overcoming the found limitations.3. To demonstrate the accuracy of the proposed K-means and DBSCAN algorithmscompared to other well-known clustering algorithm based on low sum of square error(SSE), low intra-cluster distance, and high inter-cluster distance.4

1.5 ContributionsThis study makes the following original research contributions in data mining techniques aswell as clustering algorithms.1. Propose a new K-means algorithm that can find good quality of spherical cluster andsolve the initial parameter selection problem of the traditional K-means algorithm.2. Propose a new DBSCAN algorithm that can find good quality of spherical cluster aswell as non-spherical cluster and solve the initial parameter selection problem of thetraditional DBSCAN algorithm.1.6 Outline of the ThesisThe remaining of this thesis is organized as follows. The background materials of this thesisare provided in Chapter 2. Chapter 3 contains overview of the proposed methodology andworking procedure. This chapter also contains performance evaluation of the proposed DKmeans clustering algorithm. In Chapter 4, a dynamic DBSCAN clustering algorithm isproposed. This chapter also contains overview of the proposed methodology, workingprocedure and performance evaluation of the proposed DDBSCAN clustering algorithm.Finally, Chapter 5 concludes this thesis.5

Chapter-2Literature Review6

Chapter 2Literature Review2.1 IntroductionThis chapter contains the background materials that are used throughout this thesis.Particularly, the idea of data mining which can be applied to the large datasets for discoveringpatterns which id used to make decision for further development in the real-world problems.An overview of data mining and its key techniques are provided. The popular clusteringalgorithms that are related to this study are introduced. The basic idea of the K-means methodis introduced. An overview of existing K-means method is also discussed. Finally, densitybased clustering method and DBSCAN clustering method are explained.2.2 Data miningData mining is the process of finding uncovering patterns in a large dataset. The field offinding useful patterns in data has an innumerable of names including but not limited to datamining, knowledge extraction, information discovery, data archaeology and data patternprocessing. The term of ―Data Mining‖ use statisticians and it is very popular in the field ofdatabases. The terms of knowledge discovery in the databases were introduced at the firstKDD workshop in 1989 which has been used in the AI and machine-learning fields [3]. Theterm ―Data Mining‖ becomes visible in academic journals as early as 1970. But it becameinto widespread use in the 1990s, after the rise of the internet.The new interdisciplinary field of computer science is data mining. This is the process offinding data patterns automatically from the large database [4]. The necessity of data miningis increasing day by day since previous ten or fifteen years and so now in this time on themarketplace is a very challenging competition to the efficiency of information andinformation rapidly performed an important role to find out a decision of plan and provided agreat offer of information in industry, society and all together. In real-world, a large numberof data is available in which it is difficult to retrieve the useful information. Due to thepractical importance, it is important to retrieve the structure of data within the given timebudget. The data mining provides the way of eliminating unnecessary noises from data. Ithelps to provide necessary information from the large dataset and present it in the properform when it is necessary for a specific task. It's very helpful to analyze the market trend,7

search the new technology, production control based on the demand of customer and so on.In a word, the data mining is harvesting of knowledge from a large amount of data. We canpredict the type or behavior of any pattern using data mining.In the field of computer technology, using the increasing power of computers, we develop anessential tool for working with data. Such as, it can work with the large size of the datasetsand its complexity. And also need to refine the automatic data processing, which has beenhelped by further discoveries in computer science, means that our ability for data collectionstorage and manipulation of data has been increased. Among these discoveries of importance,are the neural networks, cluster analysis, genetic algorithm [5], decision trees [6] and supportvector machines [7].Data mining can help governments and various companies to know their increasing ordecreasing costs or revenue. For example, an early form of data mining was used bycompanies to analyze huge amounts of business data from supermarkets. This analysisrevealed when people were more likely to shop, and when they were most likely to buycertain products, like women or baby products. This enabled the retailer to maximize revenueby ensuring they always had enough products at the right time in the right place. One of thefirst best selling systems was A.C. Nielson‘s best-selling Spotlight, which broke downsupermarket sales data into multiple dimensions, including volume by region and producttype.Data mining or knowledge discovery in the database which is used to discover the importantinformation from the large data set. This is a powerful novel technology for Knowledgediscovery. Computational technology is an essential tool which is able to handle thechallenges posed by these new types of data sets.The area of data mining grows up day by day, to extract useful information from the fastgrowing volumes of data. It seeks information within the dataset that queries and reportscannot adequately express.Data mining is an essential part of the field of knowledge discovery in database (KDD). Theknowledge discovery in database refers to the whole process of discovering useful knowledgefrom the large data set, and data mining is a particular step in the process of discoveringuseful knowledge from the large data set. The KDD task is to convert raw data into usefulknowledge or useful information from a large data set, as shown in Figure 2.1:8

Figure 2.1: The process of knowledge discovery in database (KDD).The process of knowledge discovery in the database contains a series of transformation steps,from data reprocessing to data mining results [8]. The input data involve flat files,spreadsheets or relational tables, and may be residing in a centralized database [9] ordistributed across multiple sites.To transform raw data into the proper format, pre-processing phase has been done tosucceeding analysis. This step includes mixing data from multiple sources, removing noiseand duplicates observations to cleaning purpose, select relevant features and record of thedata mining task. This step is the most time-consuming because of the many different typesof data.The valid and useful results are integrated and incorporated into the decision support system,which ensures the post-processing phase. In this step use visualization, that allows theanalysts to explore the data and the data mining results from a variety of viewpoints.Statistical methods and probability can also be applied during this step to eliminate unreliabledata mining results.If the discover patterns do not meet the desired standard patterns, then it is necessary to reevaluate and change the pre-processing and data mining. If the discover patterns to achieve9

the desired standard patterns, then the final step is to interpret the discovered learned patternsand turn them into knowledge.2.3 Positions of Data MiningThe traditional data analysis techniques have challenges because always new types ofdatasets. To handle these new types of challenges, researchers have developed more efficientand scalable tools that can more easily handle different types of data.Data mining has been accepting from other areas, such as optimization, signal processing,evolutionary computing, information theory, visualization and information retrieval [10].Another area, also supporting this field of research, is the use of databases, indexing andquery processing. Figure 2.2 represents the relationship of data mining with other areas.Figure 2.2: The relationship of data mining with other areas.2.4 Data Mining TasksData mining tasks are usually divided into two primary categories, as shown in Figure 2.3:2.4.1 Predictive TasksThe predictive task objective is to predict the value of one specific attribute, based on otherattribute values. The attributes used for making the prediction is named the independentvariable, and the other value which is to be predicted is commonly known as the dependentvalue.2.4.2 Descriptive TaskThe descriptive task objective is to assume underlying relations in data. This task of datamining, values are independent and frequently require post-processing to validate results.10

Figure 2.3: Data mining task.There are six essence includes in the data mining task. These are given in the followingsections.2.4.3 Classification and RegressionThe predictive modeling task divided into two types. First one is Classification, that is used toevaluate discrete target variable, and the second one is regression, which manages continuestarget variables. The primary goal of Classification and Regression is to build a model, andthis model produces minimum error between predict and real value. An example ofclassification is the classification of an email as primary or social. On the other hand, predictthe future price of a product is a Regression task because the price is a continues-valueattribute.2.4.4 Association RuleAssociation rule is a method that describes associated features in data and findingrelationships between variables. As an example, Web pages that are accessed together can beidentified by association analysis.11

2.4.5 Anomaly DetectionThis class identifies anomalies data records; this anomaly data make an error in the data files,or might be of interest and requires further investigation.2.4.6 ClusteringThis class discovers groups and structures from a large data set, which in some aspect issimilar or dissimilar, without using known structures in the large data set.2.4.7 SummarizationThis class attempts to provide a more compact representation of the data set, includingvisualization and report generation.2.5 ClusteringCluster evaluation of data is an important task in knowledge finding and data mining. Clusterformation is the process of creating data group based on the data similarities from largedataset. The clustering process is done by supervised, semi-supervised or unsupervisedmanner [11].Clustering is the method used to divide data into groups, where the object within a group issimilar to one another and dissimilar with objects in other groups according to specificsimilarity measurements. Clustering techniques are categorized into a number of methods.These methods are different from one another on the way clusters are formed. However, theperformance of these clustering methods is evaluated based on the several requirements, suchas, Minimizing the number of input parameters, discovering clusters with arbitrary shapes,Clustering large data efficiently, Handling noise and No prior knowledge of the number ofclusters.The clustering algorithms are powerful meta-learning tools for analyzing the data producedby modern applications. The purpose of clustering is to classify the data into groupsaccording to similarities, traits, and behavior of data [12].Many clustering algorithms have been proposed for classification of data. Most of thesealgorithms are based on the assumption that the number of clusters in a large data is fixed.The problem with this assumption is that if the assumed number of clusters is small then thereis a higher chance of adding dissimilar items into the same group. On the other hand, if the12

number of clusters is large, then there is a higher chance of adding similar data placed intodifferent groups [13].Figure 2.4 shows the different types of clustering methods with their well-known algorithms.Given below briefly describe how these methods work, along with their main algorithms, andmore description of the partitioning method and density-based clustering method since it isthe focus of this study.Figure 2.4: Clustering Methods with their Well-known Algorithms.2.6 Clustering MethodsThe section provides the necessary background of existing clustering methods.2.6.1 Hierarchical Clustering MethodsHierarchical Clustering Method produces a multi-level clustering in which data is groupedinto a sequence of partitions where the sub-cluster belongs to the super-cluster. Hierarchicalclustering method consists of two algorithms are agglomerative "bottom-up" and divisive"top-down" [2]. The similar

Department of Computer Science and Engineering Dhaka University of Engineering & Technology, Gazipur Gazipur-1700, Bangladesh. Member 5. ( Dr. Kaushik Deb) Professor Department of Computer Science & Engineering Chittagong University of Engineering and Technology,