Structure mining
Structure mining or Structured data mining is the process of finding and extracting useful information from semi structured datasets. Graph mining is a special case of Structured Data Mining.
Description
The growth of the use of semi-structured data, such as can be represented in XML, has created new opportunities for data mining. Data mining has traditionally been concerned with tabular data sets, reflecting the strong association between data mining and relational databases. Much of the world's interesting and mineable data does not easily fold into relational databases, though a generation of software engineers have been trained to believe this is the only way to do things. Data mining algorithms have generally been developed only to cope with tabular data.
XML is the main way of representing semi-structured data.
XML, as well as being able to represent tabular data, can also represent arbitrary trees. Any particular representation of data to be exchanged between two applications in XML is normally described by a Schema often written in XSD. Practical examples of such Schemata (plural of schema), for instance NewsML, are normally very sophisticated, containing multiple optional subtrees, used for representing special case data. Frequently around 90% of the schema is concerned with the definition of these optional data items and sub-trees.
Messages and data, therefore, that are transmitted or encoded using XML and that conform to the same schema are liable to contain very different data depending on what is being transmitted.
Such data presents large problems for conventional data mining. Two messages that conform to the same schema may have little data in common. Building a training set from such data means that if one were to try to format it as tabular data for conventional data mining, large sections of the tables would or could be empty.
There is a tacit assumption made in the design of most data mining algorithms that the data presented will be complete. Many algorithms perform badly with incomplete data sets, for instance Neural Networks.
XPath is the standard mechanism used to reference nodes and data items within XML. It has similarities to standard techniques for navigating directory hierarchies used in operating systems user interfaces.
To data and structure mine XML data of any form at least two extensions are required to conventional data mining. These are the ability to associate an XPath statement with any data pattern and sub statements with each data node in the data pattern, and the ability to mine the presence and count of any node or set of nodes within the document.
As an example, if one were to represent a family tree in XML, using these extensions one could create a data set containing all the individuals in the tree, data items such as name and age at death, and counts of related nodes, such as number of children. More sophisticated searches could extract data such as grandparents' lifespans etc.
The addition of these data types related to the structure of a document or message facilitates structure mining.
The other desideratum is that the actual mining algorithms employed, whether supervised or unsupervised, must be able to handle sparse data. In practice the set of data mining algorithms that are best at handling sparse data are those that process the training set data into trees of related patterns. These are frequently descendants of or take their inspiration from Ross Quinlan's ID3 algorithm.
See also
Commercial software and applications
External links
- Structure mining XML data
- Mining structured data
- The 5th International Workshop on Mining and Learning with Graphs, Firenze, August 1-3, 2007
References
- Andrew N Edmonds, On data mining tree structured data in XML', Data mining UK conference, University of Nottingham, Aug 2003
- Gusfield, D., Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997. ISBN 0-521-58519-8
- R.O. Duda, P.E. Hart, D.G. Stork, Pattern Classification, John Wiley & Sons, 2001. ISBN 0-471-05669-3