Methods of reduction intrastructural outliers in algorithms of comparing chainlike graphs

Nowadays preliminary clustering of initial data set is one of efficient methods, which is used for data visualization. Graph model is most appropriate for description data with formalized structure (i.e. measurement results obtained in predefined formats, reports about rendered services etc). In such case the idea of fragment (chains) of data similarity reduced to idea of similarity of graphs and choice of distance measure between graphs structures become the most complicated problem.

The analysis of opportunity to use methods of comparing weighted chainlike graphs for clustering data with formalized structure is given. Main techniques of comparing graphs and single elements of graphs, such as isomorphic method, Levenshtein distance (edit distance), maximum common subgraph search (MCS-method), statistical method (based on comparing of statistical characteristics of graph structure), method of g-model creating and iterative method were studied on data set of rendered medical services.

It was shown that usage of Levenshtein distance and modification of TF-IDF technique reduces the influence of intrastructural outliers. Modification of distance measure was suggested to reduce the influence of intrastructural outliers on clustering process.