Research Of Heuristic Algorithm Based On Adjacent Pairs For Clustering Problems

Clustering usually aims at dividing the data into several clusters,to make the differences little in clusters and much between clusters.Given a goal function which can evaluate the clustered results and the amount of clusters,we can optimize goal function value by attempting disparate amount of clusters.Therefore,the goal function can directly affect the performance of clustering process.A large amount of literatures show that clustering algorithm apply the SSE to the goal function.Nevertheless,the SSE has some limitations.It needs to use the center of cluster in every iteration.In most cases,there exists difficulties to converge a satisfying goal value based on a poorer initial solution.It can only be applied to central-based clusters,and other data surrounds the centers.Otherwise,it can't effectively evaluate the quality of clustered results.Even if the global optimal value is obtained,the clustered performance may not be good.Hence,a fire-new goal function which counts the number of points between the boundaries of adjacent clusters puts forward through the theoretical and experimental analysis.Firstly,it wakes the concept of cluster center,and attach more significance to the boundary of cluster set.Secondly,when constructing the initial solution,an initial center set is selected based on the center selection strategy of weight.Thirdly,optimizing the objective function value by two basic meta operations: merging and splitting.The merging operation merges the two clusters with the largest adjacent logarithm into one cluster,and the splitting operation selects one cluster from the remaining clusters for splitting.Finally,the center of the cluster is tentatively exchanged in its neighborhood,and the condition of candidate center is satisfied,so that the center is slightly adjusted in its neighborhood.In this thesis,seven groups of different types of common benchmark data sets are tested.The performance of clustering is appraised by JC,FMI and accuracy rate respectively,to minimize the impact of the criteria itself on the clustering and make the experimental results more credible,it shows that the metric value of JC and FMI are more than 95%.Compared with k-means,k-means++ and maximin k-means algorithms,the convergence rate of three groups of examples reaches the first and equals to k-means++ in other examples.In the summary,the proposed goal function has conquered the boundedness of SSE and nicely integrated into the clustering process.It tested on disparate benchmark data.The result indicates that the proposed algorithm can be applied to disparate data,and the convergence rate is to some extent beyond expectation.