Structure mining

Structure mining or structured data mining is the process of finding and extracting useful information from semi-structured data sets. Graph mining, sequential pattern mining and molecule mining are special cases of structured data mining.

The growth of the use of semi-structured data has created new opportunities for data mining, which 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 was the only way to handle data, and data mining algorithms have generally been developed only to cope with tabular data.

XML, being the most frequent way of representing semi-structured data, is able to represent both tabular data and 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, for instance NewsML, are normally very sophisticated, containing multiple optional subtrees, used for representing special case data. Frequently around 90% of a 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.

En el diseño de la mayoría de los algoritmos de minería de datos, se asume tácitamente que los datos presentados serán completos. Otra necesidad es que los algoritmos de minería empleados, ya sean supervisados ​​o no supervisados, sean capaces de manejar datos dispersos. Es decir, los algoritmos de aprendizaje automático tienen un rendimiento deficiente con conjuntos de datos incompletos donde solo se proporciona una parte de la información. Por ejemplo, los métodos basados ​​en redes neuronales , o el algoritmo ID3 de Ross Quinlan , son muy precisos con muestras buenas y representativas del problema, pero tienen un rendimiento deficiente con datos sesgados. La mayoría de las veces, una mejor presentación del modelo con una representación más cuidadosa e imparcial de la entrada y la salida es suficiente. Un área particularmente relevante donde encontrar la estructura y el modelo apropiados es la cuestión clave es la minería de texto .

XPath es el mecanismo estándar para referirse a nodos y elementos de datos en XML. Presenta similitudes con las técnicas estándar para navegar por jerarquías de directorios utilizadas en las interfaces de usuario de los sistemas operativos. Para analizar datos y estructuras XML de cualquier tipo, se requieren al menos dos extensiones a la minería de datos convencional: la capacidad de asociar una instrucción XPath con cualquier patrón de datos y subinstrucciones con cada nodo de datos dentro de dicho patrón, y la capacidad de analizar la presencia y el recuento de cualquier nodo o conjunto de nodos en el documento.

Por ejemplo, si se representara un árbol genealógico en XML, utilizando estas extensiones se podría crear un conjunto de datos que contuviera todos los nodos individuales del árbol, datos como el nombre y la edad al fallecer, y recuentos de nodos relacionados, como el número de hijos. Búsquedas más sofisticadas podrían extraer datos como la esperanza de vida de los abuelos, etc.

La incorporación de estos tipos de datos relacionados con la estructura de un documento o mensaje facilita la minería de estructuras.

• Núcleo gráfico
• Contenido estructurado
• Programación inductiva

• Andrew N Edmonds, Sobre la minería de datos con estructura de árbol en XML , Conferencia de minería de datos del Reino Unido, Universidad de Nottingham, agosto de 2003.
• Gusfield, D., Algoritmos sobre cadenas , árboles y secuencias: Informática y biología computacional , Cambridge University Press, 1997. ISBN 0-521-58519-8
• RO Duda, PE Hart, DG Stork, Clasificación de patrones , John Wiley & Sons, 2001. ISBN 0-471-05669-3
• F. Hadzic , H. Tan, TS Dillon, Minería de datos con estructuras complejas, Springer, 2010. ISBN 978-3-642-17556-5

• V Taller Internacional sobre Minería y Aprendizaje con Grafos, Florencia, 1-3 de agosto de 2007.