Research On Algorithm And Application Of Constraint-based Clustering

With the development of computer science, net communication and information processing technology, the war is more and more informationization the emergency maneuver equipment support in wartime tends to intelligentized. The choice and optimizing of equipment delivering path and setting of equipment maintaining point are very important to the speed, cost, benefit and security of emergency maneuver equipment support. In order to improve efficiency, reduce freight, increase the security and simplify the support procedure, we need to divide the maintenance area into several regions to implement equipment support. The clustering analysis of data mining provides a good solution for this problem.With deeply anatomizing the characteristics and requirements of the maintenance area partition and based on researching the existing clustering algorithms of data mining, this thesis uses graph-based clustering algorithm to solve the problem. In allusion to the issue that the regions may be arbitrary-shape and multi-resolution, it proposes a minimum spanning tree clustering algorithms named MSTClust by using the graph modeling method, which controls the processe of clustering through the ratio of the neighbor edges'weights. Based on the statistical information of the sub tree as a result of MSTClust and the control-parameters, it constructs a clustering result evaluating function, which indicates that the clustering result is the best when it reaches the minimum value. By using the function, it can make the parameters auto-setting by searching the minimum value of the function. There must be some constraints when parting the maintenance area, so it presents a constraint-based minimum spanning tree clustering algorithm called COP-MSTClust which takes the idea of MSTClust to reconstruct the kruskal algorithm. Then we take an experiment to prove the result and the performance of the algorithms using synthetic datasets and real datasets from UCI. At last it demonstrats the rationality and feasibility of using the COP-MSTClust to solve the problem of maintenance partition through analyzing and simulating on an instance.In this thesis, we adopted the clustering analysis method to solve the problem of maintenance area partition for the first time; it presents two effectible and great performable clustering algorithms, and especially, the COP-MSTClust can deal with multi-constraints problems; and it demonstrats the rationality and validity of using the COP-MSTClust to solve the problem by analyzing and simulating on an instance. It is a valuable reference for the emergency maneuver equipment support for our army.