Research On Clustering Algorithm Based On Tabu Search Algorithm And Similarity Measurement

In the era of "information explosion", we are often faced with the massive data, such as the massive text data, Web data, multimedia data, and those data hide a lot of useful and important information. How to extract that potential information which can be used to support decision using some effective methods leads to the birth of data mining. As one of the important branch of data mining, clustering has a great impact on people’s daily life. The main technologies of existing clustering can be divided into these category:Partitioning method, hierarchical method, density-based method, grid-based method and model-based method.The main research work of this thesis includes the following two aspects:1. Starting from the theoretical basis of partition based K-medoids clustering algorithm and discussing the deficiency of K-medoids algorithm, we proposed an K-medoids clustering algorithm based on improved Tabu Search. Tabu search algorithm is an optimization algorithm simulating human short-term memory making it has a strong global searching ability. View of the shortcomings that tabu search comparatively relies on the initial solution, we combined the granular computing with maximum distance product method to improve tabu search, which improved the precision of K-medoids clustering with a strong stability. Through the experiment, we verified the feasibility of the method.2. According to the characteristics of high dimensional spatial data, and the distance similarity computing method in low dimensional is not suitable in the high dimension space, we proposed a new similarity measure method. Having gotten the similar matrix through computing the similarity between objects, we undertook clustering analysis inspired by hierarchical clustering bottom-up notion. Through the analysis on validity, we proved the feasibility of this method.