Multi Objective Clustering and Optimization

Abstract

In many real world situations there may be several objectives that must be optimized simultaneously in order to solve a certain problem. In this thesis , the problem of clustering a data set has been posed as one of multiobjective optimization (MOO). Most of the existing clustering techniques are based on a single criterion which reflects a single measure of goodness of a partitioning. However, a single cluster quality measure is seldom equally applicable for different kinds of data sets with different characteristics. Hence, it may become necessary to simultaneously optimize several cluster quality measures that can capture different data characteristics. Additionally, optimization of clustering method has also been done. Hence in this thesis, optimization of validity indices along with optimization of clustering method defines the term MultiObjective optimization. This thesis proposes, experiments, demonstrates and evaluates the concept of MultiObjective optimization of clustering in terms of validation. Experimentation involves discussion and comparison of clustering methods over ill-structured datasets. The dataset used in this experiment has derived from the measures of sensors used in an urban waste water treatment plant(WWTP). Also it addressed an important issue of clustering process regarding the quality assessment of the clustering results. newlineThe objective of my work is to provide automatic monitoring of treated water released from waste water treatment plant. The current assessment of river quality by the E.P.A is based on a comprehensive index known as River Pollution Index (RPI). RPI is an integrated indicator used to determine the level of pollution of a river. The index value is calculated using the concentration of 4 parameters in water quality: Dissolved Oxygen (DO), Biochemical Oxygen Demand (BOD5), Suspended Solids (SS) and Ammonia Nitrogen (NH3-N).Experimentation involves calculating the value of above said parameters on the generated clusters and categorizing the clusters into lightly polluted, highly polluted or slightly polluted. Also based on the pollution level , decision can be made to choose the fields like irrigation , fisheries or domestic where the treated water can be used. newlineThe methodology is demonstrated with three implementations. All three implementations were evaluated and proved with results. The first implementation used single clustering method called K-means with multiple internal cluster validity indices like Xie-Beni index, Dunn index, silhouette index and optimization of clustering has been expressed in terms of number of clusters which result in a natural categorization of the dataset based on the quality parameters of the water. K-means algorithm is used for clustering the data set considering its simplicity and efficiency. Also K-Means algorithm is one of the most suitable algorithm for clustering numerical datasets. The Second implementation used multiple clustering methods like K-means, Hierarchical and PAM whose results are validated with same set of validity indices like connectivity, Dunn index, silhouette index and optimization deals with selection of best clustering method. At the end, experiment is done by varying the number of clusters and optimal newlinescores are calculated. Optimal score and optimal rank list are generated which reveals that the hierarchical clustering is the optimal clustering method. The optimum value of connectivity index should be minimum, silhouette should be maximum, Dunn should be maximum. Model Based Clustering with Density Estimation is used in final implementation and non-overlapping clusters are generated which categorizes exactly the different levels of pollution and leads to reach the objective of the work. newline newline newline