IRJET- Performance Analysis of Optimization Techniques by using Clustering

IRJET- Performance Analysis of Optimization Techniques by using Clustering

• 1.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 06 Issue: 06 | June 2019 www.irjet.net p-ISSN: 2395-0072 © 2019, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 1465 PERFORMANCE ANALYSIS OF OPTIMIZATION TECHNIQUES BY USING CLUSTERING K. Vijayakumari1, Dr V. Baby Deepa2 1Research Scholar, Department of Computer Science, Government Arts College, Karur, Tamilnadu, India 2Assistant Professor, Department of Computer Science, Government Arts College, Karur, Tamilnadu, India ---------------------------------------------------------------------***---------------------------------------------------------------------- Abstract - the Bee Colony Optimization algorithm shows the new path in the field of swarm intelligent family, it has the capability to avoid the local minimaproblemand itovercomes the difficulties in Particleswarmoptimizationalgorithms. BCO are motivated by the principles of natural genetic activities and spread common behaviour of social colonies has shown authority in production with complex optimization problems. In this paper, Fuzzy Bee Colony Optimization (FBCO) algorithm gives better result to match up with other swarm algorithms such as Fuzzy C- Means and Fuzzy Particle Swarm Optimization. Key Words: Clustering, Optimization, Fuzzy C-Means, Fuzzy Particle Swarm Optimization, Fuzzy Bee Colony Optimization 1. INTRODUCTION The data will available in unusual format for that suitable action to be taken by the user, by preserve the data and by making good decision. Consumers will essential to retrieve the data from database by making better decision, this refer to Data mining or Knowledge Discoveryprocess[1].Thedata mining [3] is important tools for data analysis and it is a computational intelligence discipline is very practical and new knowledge discoveryandindependentdecisionmaking. Data mining is one of the most fundamental study in the field that are due to the development of both computer hardware and software technologies, Clustering is essential in data analysis and data mining appliance. In Data Mining there are two forms of data analysis there are classification and prediction.Thisassessmentcanhelpto make obtainable enhanced considerate of the data at huge. Classification predicts definite (discrete, unordered) labels, prediction models permanent valued functions. A. Applications of clustering  Biology, computational biology and bio informatics  Medicine  Business and marketing  World wide web  Pattern Recognition  Image segmentation  Spatial Data analysis The aim of Clustering is to represent large datasets by a smaller number of clusters. It gets simplicity in demonstrating information and thus acts as essential role in the method of knowledge discovery and data mining. The result of the clustering process and competence of its field request are generally determined through algorithms [2], there are various algorithms which are used to solve this problem. 2. UNSUPERVISED CLASSIFICATION Unsupervised clustering technique were developed byJar dine and Sibson in 1968. Its goal to discover group of similar instance within the dataset limited of group label. The aspiration of clustering is to collection of sets of bits and pieces into classes such that similarobjectsarelocatedinthe same cluster while dissimilar objects are in break up into various clusters [8]. Clustering techniques are generally unsupervised classification without predefined classes it can be used to classify data into groups based on resemblance along with the being data objects. An expert clustering method will create high superiority clusters in which the intra-class resemblance is high and the inter-class resemblance is low [7]. One of the capable algorithms in clustering [4] is Fuzzy C- Means, its job as arbitrary collection of centre points create iterative development declining into the limited best clarification without complication. 2.1 Fuzzy C-Means Algorithm (FCM) FCM is section of position of n substance 1 2{ , ,...... }nO O O O in Rd dimensional hole into c (1 < c < n) fuzzy clusters with 1 2{ , ,...., }nz z z z cluster centersor centroids. The clustering of fuzzy objects is explained by a fuzzy matrix μ with n rows and c columns in which n is the
• 2.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 06 Issue: 06 | June 2019 www.irjet.net p-ISSN: 2395-0072 © 2019, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 1466 amount of information and c is the figure of clusters. µij , the part within the ith row and jth column in μ, point out the degree of association or membership function of the ith object with the jth come together. The typescript of μ is as go behind: i [0, 1] i =1, 2…n j =1, 2…c (2.1) 1 µ 1 c ij j  i =1, 2…n (2.2) 1 µ c ij j o n    j =1, 2…c (2.3) The objective function of FCM is to reduce the Eq. (2.4): 1 1 c n m ij ij j i J d      (2.4) Where ijd =│ i jo z │ (2.5) In which, m (m>1) is a scalar phrase the weighting exponent and controls the fuzziness of the resulting clusters and ijd is the Euclidian distance from object 1 2{ , ,...., }nz z z z to the cluster center jz . The jz , centroids of the jth cluster, is get clutch of using under equation 1 1 n m ij i i j n m ij i o z       (2.6) Algorithm 1: Fuzzy C Means Step 1: Initialize the membership function values µij Step 2: Compute the cluster centers jz Step 3: Compute Euclidian distance ijd Step 4: Update the membership functionµij , 2 1 1 1 ( ) ij c ij m k ik d d      (2.7) Step 5: If not satisfied, go to step 2. 2.2 Particle Swarm Optimization (PSO) It is projected by Eberhart and kennedy in 1995. It is an optimization algorithm stimulated by the commonactivities of birds and used to resolve all kinds of optimization problem. Particle swarm optimization is a type of swarm intelligence algorithm where the agents known as particles attempt to optimize a fitness function by moving through a explore hole. In PSO, the inhabitant’s dynamics resembles the progress of a bird’s flock pointed for food, here information distributiontakesplaceandindividualscangain from the discoveries and previous experience from all other particles. The speed of particles determines the direction and distance of particle movement, while the velocity of the particle is adjusted dynamically with the movement of its own and other particles so as to recognize optimization of the individual in the solution space of optimization. Particles renew their velocity and position through two kinds of ‘best‘value. One is its personal best (p best), which is the location of its highest fitness value.Anotheristheglobal best (g best), which is the location of overall best value, obtained by any particles population. The positions and velocities of the elements are given in the equations V (t+1) = w. V (t). 1 1c r (pbest(t)-X(t)+ 2 2c r (gbest(t)-X(t)) k=1,2…P (2.8) X (t+1) =X (t) +V (t+1) (2.9) where X and V are position and velocity of component respectively, w is inaction weight, c1 and c2 are optimistic constants, called acceleration coefficients which control the influence of pbest and gbest on the search process, P is the number of elements in the swarm, r1 and r2 are random values range between 0 and 1. A. Fuzzy particle swarm optimization for fuzzy clustering In FPSO algorithm X [11], the location of element, finds the fuzzy family member from set of data objects, 1 2{ , ,...., }no o o o to set of cluster centers [10], 1 2{ , ,...., }nz z z z , X Can be expressed as follows:
• 3.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 06 Issue: 06 | June 2019 www.irjet.net p-ISSN: 2395-0072 © 2019, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 1467 11 1 1 c n nc X                (2.10) Where μij is the membership task of the ith point with the jth cluster with condition in Eq. (2.1) and Eq. (2.2) therefore we can able to see that the location matrix of each particle is the same as fuzzy matrix μ in FCM algorithm. Also the velocity of each particle is stated using a matrix withthesize n rows and c columns the elements of which are in range between -1 and 1. We get the Eq. (2.11) and Eq. (2.12) for updating the positions and velocities of the particles based on the matrix. V (t+1) = w V (t) 1 1c r (pbest(t) X(t) 2 2c r (gbest(t)- X(t)) k=1,2…P (2.11) X (t+1) =X (t) V (t+1) (2.12) After updating the position matrix,itmaygoagainstto the conditions given in Eq. (2.1) and Eq. (2.2). So it is essential to stabilize the position matrix. First we mark zero to all the negative elements in matrix. If all elements in a row of the matrix are zero, they need to be re-evaluated using series of random numbers within the interval between 0 and 1, and then the matrix performs the following transformation with its constraints: 11 1 1 1 1 1 1 1 1 / / / / c c j c j j j c c n nj nc nj j j Xnormal                                 (2.13) In FPSO algorithm the same as other evolutionary algorithms, we needa functionfor evaluatingthegeneralized solutions called fitness function. ( ) m K f X J  (2.14) This above equation is used for solution evaluation. Here K is a constant and mJ is the objective function of FCM algorithm (Eq. (2.4)). The smaller is mJ , the better is the clustering effect and the higher is the individual fitness f (X). The FPSO algorithm for fuzzy clustering problem can be stated as follows: Algorithm 2: Fuzzy PSO for fuzzy clustering Step 1: Initialize the parameters including population size P, c1, c2, w, and the maximum iterative count. Step 2: Create a swarm with P particles (X,pbest,gbestandV are n× c matrices). Step 3: Initialize X, V, pbest for each particleandgbestforthe swarm. Step 4: Calculate the cluster centers for every particle Step 5: Calculate the fitness value of each particle Step 6: Calculate pbest for each particle. Step 7: Calculate gbest for the swarm. Step 8: Update the velocity matrix for every particle Step 9: Update the position matrix for every particle Step 10: If terminating condition not satisfied, go to step 4. The condition in proposed method is the highest number of iterations or no development in gbest in a number of iterations. 2.3 Bee Colony Optimization (BCO) The Bees Algorithm is a new search algorithm, first residential in 2005 by Pham DT etc.and Karaboga.D [9]. The algorithms replicate the food foraging behaviour of swarms of honey bees. In fundamental version, the algorithm performs a kind of neighbourhood search combined with random search and can be used for optimization problems. Bee Colony Optimization algorithm proposed byTeodorovic and Dell’Orco [13, 14]. Fuzzy Bee Colony Optimization The bee colony integrate with fuzzysystemiscalledFuzzy Bee Colony Optimization (FBCO) which all constraint are based Fuzzy PSO such as 2.13 and fitness value is based on 2.14. Algorithm 3: Fuzzy BCO for fuzzy clustering
• 4.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 06 Issue: 06 | June 2019 www.irjet.net p-ISSN: 2395-0072 © 2019, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 1468 Step 1 Initialization Phase • Initialize the number of clusterasc,thereal number m, the population size N, • Generate initial population zi, • Calculate the membership matrix by randomly • Evaluate the population • Set cycle to 1 Step 2 Repeat Step 3 for Employed Bee • Produce new solution ui • Calculate the membership matrix • Calculate the fitness • Apply the greedy selection process • Calculate the probability values pi for the results Step 4 for Onlooker Bee and Scout Bee • Choose a solution zi depending on pi • Produce new solution ui • Calculate the membership matrix • Calculate center and distance value • Calculate the fitness using • Apply the greedy selection process • If the solution is discarded then replace that solution with a new random solution for the scout • Allocate cycle to cycle + 1 • Remember the best solution (best cluster centers) achieved yet • Calculate objective value Step 5 Until cycle reach converges Table -1: Performances analysis of objective values S.N o FPSO FBCO 1 Weakness of search with local search Strength is local and global search 2 It has a slow convergence rate, Fast convergence 3. RESULT AND EXPERIMENTAL ANALYSIS WITH DISCUSSIONS There are many research papers have been used in Bee colony optimization with clustering methods for solving many problems. The UCI database, which is a well-known directory storehouse are used to estimate the concert of the algorithm. The number of object is 150, dimension is 4 and cluster is K = 3 in Fisher’s Iris plants dataset.Thisdatasetare implemented by using MATLAB. Table -2: Performances analysis of statics parameter Methods Accuracy Sensitivity Specificity FCM 0.42 0.78 0.72 FPSO 0.53 0.86 0.77 FBCO 0.55 0.89 0.81 The table 2 give a picture of make out the presentation of fuzzy clustering problem and from that table be well-known with the FBCO is best concert based on their objective values. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 FCM FPSO FBCO Accuracy Sensitivity Specificity Fig 1 Performance Analysis of their Parameter Fig 1 illustrate to categorize the performance analysis of all algorithms and each algorithm have a lot of demerits and merits, FBCO overwrite the demerit of existing and created improved performance than others. 4. CONCLUSION In this paper, the bee colony optimization is integral with fuzzy theory, along with the Fuzzy Bee Colony Optimization is construction offered to efficient conclusion for fuzzy with clustering in data mining equivalent up with other algorithms. This normal method of effort providesa number of ways for solving the real world problems more effectively and quickly with accuracy. REFERENCES [1] Neelamadhab Padhy, Dr. Pragnyaban Mishra , and Rasmita Panigrahi, “The Survey of Data Mining Application And Feature Scope”,International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol.2, No.3, June 2012
• 5.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 06 Issue: 06 | June 2019 www.irjet.net p-ISSN: 2395-0072 © 2019, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 1469 [2] Malwinder singh and Meenakshi bansal, “Survey On Clustering And Optimization Techniques To Develop Hybrid Clustering Technique”, International Journal of Computer Engineering and Applications, Volume VII, Issue I, July 14 www.ijcea.com ISSN 23213469. [3] Tiwari, Manu Bhai Jha, and OmPrakash Yadav, “Performance analysis of Data Mining algorithms in Weka”, IOSRJournal ofComputerEngineering(IOSRJCE) ISSN: 2278-0661, ISBN: 2278-8727 Volume 6, Issue 3 (Sep-Oct. 2012), PP 32-41. [4] Amreen Khan, Prof. Dr. N.G.Bawane and Prof. Sonali Bodkhe, “An Analysis of Particle Swarm Optimization with Data Clustering-TechniqueforOptimizationinData Mining”, Amreen Khan et. al. / (IJCSE) International Journal on Computer Science and Engineering Vol. 02, No. 04, 2010, 1363-1366. [5] Asha Gowda Karegowda and Seema Kumari, “Particle Swarm Optimization Algorithm Based k-means and Fuzzy c-means clustering”, Volume 3, Issue 7, July 2013 ISSN: 2277 128X International Journal of Advanced Research in Computer Science and Software Engineering. [6] Soumi Ghosh and Sanjay Kumar Dubey, “Comparative Analysis of K-Means and Fuzzy C-Means Algorithms”,((IJACSA)International Journal ofAdvanced Computer Science and Applications, Vol. 4, No.4, 2013. [7] Makhalova Elena, “Fuzzy C - Means Clustering In Matlab”, The 7th International Days of Statistics and Economics, Prague, September 19-21, 2013. [8] Ren Jingbiao,YinShaohong,“ResearchandImprovement of Clustering Algorithm in Data Mining”, 2010 2nd International Conference on Signal Processing Systems (ICSPS) 978-1-4244-6893-5/$26.00 C 2010 IEEE. [9] Li-Pei Wong, ii Malcolm Yoke Hean Low, iii Chin Soon Chong, “Bee Colony Optimization with Local Search for Traveling Salesman Problem”,www.informatik.uniheidelberg.de/groups/co mopt/software/TSPLIB95. [10] Esmaeil Mehdizadeh, “A fuzzy clustering PSO algorithm for supplier base management”, ISSN 1750-9653, England, UK International Journal of Management Science and Engineering Management Vol. 4 (2009) No. 4, pp. 311-320. [11] Chia-Feng Juang Che-Meng Hsiao and Chia-Hung Hsu, “Hierarchical Cluster-Based Multispecies Particle- Swarm Optimization for Fuzzy-System Optimization” IEEE Transactions on Fuzzy Systems, Vol. 18, No. 1, February 2010. [12] Chen Yanyun , Qiu Jianlin, Gu Xiang,Chen Jianping, JiDan, Chen Li, “Advances In Research of Fuzzy C-means ClusteringAlgorithm”,2011 International Conferenceon Network Computing and Information Security. 978-0- 7695-4355-0/11 $26.00 © 2011 IEEE DOI 10.1109/NCIS.2011.104. [13] Dusan TEODOROVIC, Mauro DELL ORCO” Bee Colony Optimization – A Cooperative Learning Approach To Complex TransportationProblems”AdvancedORandAI Methods in Transportation [14] K. Velusamy andR.Manavalan,“PerformanceAnalysisof Unsupervised Classification based on Optimization,” International Journal of Computer Applications (0975 – 8887, Volume 42– No.19, March 2012.