Study And Implementation Of Uncertain Graph Classification Algorithm Based On ELM

With the wide application of bioinformatics,chemical informatics and Web analytics,as a kind of common data structures of graph,becomes increasingly important in terms of complex structure modeling.Compared to certain graph,uncertain graph not only can express rich semantic but also can express the uncertainty inherent in the data itself. Specifically,the uncertainty of uncertain graph is either edge or vertex with a certain probability.In recent years,along with the growth of demand for large amounts of structured data analysis,the classification of graph processing as an essential part of data mining,has become one of research hotspots in the realm of database and data mining.Because of the uncertainty,the existing classification algorithms cannot be directly applied to the classification problem of the uncertain graph.Aimed at this problem,this paper puts forward uncertain graph classification algorithm based on ELM (Extreme Learning Machine).The main research contents are as follows:Firstly,in this paper we systematically introduced characteristics,the significance and application background of graph data mining.Meanwhile,the related definitions of graph are presented.The classic frequent subgraph mining algorithm of gSpan and efficient machine learning algorithm of ELM are also introduced in this section,that laid a foundation for further research.Secondly,to resolve the problem that gSpan algorithm can only handle certain graph and cannot satisfy large-scale database,an improved gSpan algorithm is proposed.By mining all embedded graphs in uncertain graph Gi about subgraph s,we can organize all embedded graphs in Gi as a search tree and then we can calculate the support of s in D.We use three layer storage structure instead of the adjacency list storage structure in gSpan and then the extension frequent subgraph don’t need the entire database to memory every time.Afterwards,the result of improved version gSpan algorithm is used as a feature candidate set,to select a small set of non-redundant and discriminative patterns for classification from it,a method of selecting feature patterns is provided in this paper.Through frequent subgraph of the Apriori property and the score of the scoring function,the method of the classification feature is explained.Meawhile,The quality of improved version gSpan and the method of selecting feature patterns are verified by experiments.Finally,an ELM-based uncertain graph classification algorithm is provided.By analyzing the relationship between pattern frequency and its predictive power,a strategy for setting Min_Sup is put forward.The classifier is trained by the algorithm of ELM,and The performance of the classifier is verified by experiments.