Research Of Data Mining Based On Discrete Morse Theory

Data-mining is a technique which can extract some effective, valuable andunderstandable patterns from abundant, random, noisy, disordered and fuzzy data,and then find some information that is useful or potentially useful, obtain the timetrends and connections, and provide the decision support capability about theproblem solving for users. Today, data is overrunning, data-mining technology hasan important significance for us to refine effective information and manageknowledge efficiently. This paper introduces two important technologies indata-mining——association rules and cluster analysis, as well as the prominentdiscrete Morse Theory, and proposes two new algorithms which are the gridclustering algorithm based on discrete Morse Theory and a strong association rulesmining algorithm based on generalized discrete Morse Theory by using discreteMorse Theory in association rules mining and cluster analysis.Morse Theory is a tool which analyzing the topological structure of smoothmanifolds, which is put forward by Marton Morse firstly and analyzed therelationship between the critical point and the topology of manifold. Then Formanintroduced the discrete structure into Morse Theory and got the discrete MorseTheory, which created discrete Morse function and discrete gradient vector field onCW-complex and conducted analysis and researching, so as to get the topologicalinformation and attribute of CW-complex. Discrete Morse Theory is an powerfuloptimization tool, which conducts calculating and analysis by translating thetopological structure of the space graphics into mathematical functions.This paper applies the discrete Morse Theory to the grid clustering, bringsforward a new grid clustering algorithm——a grid clustering algorithm based on thediscrete Morse Theory. Firstly, this algorithm distributes large amounts of data to each grid by using grid clustering on the dataset, and regards every dense grid as adot and gives up the sparse grids, and then connects the dots between each other toform a CW-complex, in which the dense grids are the vertexes and the links betweendots are the edges. Constructing discrete Morse function on CW-complex, so as toachieve the purpose of clustering. The experiment shows that this algorithm hasbetter clustering results for the datasets with irregular shapes.In addition, this paper extends the discrete Morse Theory and association rule togeneralized discrete Morse Theory and strong association rule, gives the definitionof generalized discrete Morse Theory and strong association rule, and usesgeneralized discrete Morse Theory in strong association rules, getting a strongassociation rule mining algorithm based on generalized discrete Morse Theory. In thealgorithm, every item in transaction database is seen as a vertex and connecting thevertex to form a CW-complex, then constructing the generalized discrete gradient onthe CW-complex and producing strong association rules according to the direction ofarrows which stand for the confidence and support among items in discrete gradientfield, and verifying the algorithm by simulation experiment. The new algorithmmakes it more intuitive and simple to mine special association rules.In the end, the paper gives a summary of the whole text, listing the innovationpoints and the contents of each chapter, pointing the inadequacies of two newalgorithms, and giving the direction of further study.