Multi-Scale Clustering Method Based On Granular Computing

Data mining refers to the process of discovering hidden and valuable knowledge and rules from massive data.As one of the important mining techniques,clustering analysis has been closely watched by researchers and has a wide range of applications in the pattern recognition,financial economic analysis,market decision,image processing and other fields.The introduction of multi-scale science which is a typical interdisciplinary subject opened up new ideas and directions for the research of data mining.Since the research of multi-scale scientific is mostly limited to space or image data in the field of data mining,this dissertation chooses clustering as the breakthrough point,mainly focusing on multi-scale features of general datasets and the theory and method of multi-scale clustering with the purpose of multilayer and multi-angle of data analysis and providing diversification decision support for users.Granular computing is a new way to solve complex problems and to exploit massive amounts of data.Granular computing simulates the way of human thinking which analyzes the problems from different levels so that it can dissect the macro features from the overall or find the the details of some part according to the actual needs.The thought of "divide and conquer" is very fit with multi-scale clustering.Therefore,this dissertation uses granular computing as the basis of methodology in the macro level to guide the design of multi-scale clustering algorithm,providing a new perspective for multi-scale clustering algorithm.This dissertation constructs the multi-scale data model based on the equivalent partition model in granular computing to provide the data preprocessing method for the multi-scale clustering algorithm.And it expounds the knowledge of scale conversion,scale effect and scale selection to perfect the multi-scale clustering theory.Then,the definition of multi-scale clustering is proposed as well as its essence from the perspective of granular.Ultimately,the multi-scale clustering architecture is built as guidance to design the corresponding algorithm.Meanwhile,this thesis improvs the similarity calculation method based on information granularity,and puts forword two algorithms named Upscaling Algorithm of Multi-scale Clustering and Downscaling Algorithm of Multi-scale Clustering.Based on the multi-scale clustering as the research core,this thesis manily completes the following works:1)The research of the multi-scale clustering theoretical principleIn view of the present problems of multi-scale clustering,multi-scale clustering theory iscompleted from four aspects as multi-scale data model,scale conversion,scale effect,scale selection.First of all,starting from the equivalence partition model of granular computing,this thesis analyzes the equivalence relation in dataset to put forward the method of scaling general datasets refering to granulating methods,and proposes the mathematical definition of Scale,Scale Partition,Multi-scale Dataset,Ancestor-Offspring Scale,Parent-Children Scale.Secondly,the definition and concrete reflection of scale effect is analyzed.Finally,three principles and three quantitative criteria of the scale selection are given,which are the precondition of the multi-scale clustering algorithm implementation.2)The construction of multiscale clustering algorithm architectureFirstly,the definition of multi-scale clustering is clarified by combining the knowledge of clustering and scale.Secondly,it sets forth that the essence of multi-scale clustering is the scale conversion of knowledge from the perspective of granular,and points out that the object of multi-scale clustering scaling should be feature descriptors able to represent the clusters such as cluster center,similarity within cluster,etc.Finally,the multi-scale clustering architecture is proposed,and three stages of multi-scale clustering are summarized as the multi-scale conversion of data,the multi-scale conversion of knowledge,multi-scale decision-making to provide guiding framework and implementation ideas.3)The proposal of multi-scale clustering algorithmFirst of all,an improved similarity calculation method based on information granularity is put forward.On this basis,according to the multi-scale clustering architecture,combining with the existing methods of scale conversion,it proposes multi-scale clustering algorithm called UAMC((?)pscaling (?)lgorithm of (?)ulti-scale (?)lustering)based on the mosaic upscaling scheme and DAMC((?)ownscaling (?)lgorithm of (?)ulti-scale (?)lustering)based on IDW interpolation.4)Verification experiments on the multi-scale clustering algorithmThis thesis applies five UCI public datasets and one real total population data of H province to analyze the multi-scale clustering algorithm.The results show that the UAMC and DAMC algorithms proposed in this dissertation prove higher accuracy and faster execution than the benchmark algorithms(K-Means,EM,LVQ).As the increase of the data size,the algorithms are stabler,indicating that it's effective and feasible.