Structure mining

El crecimiento en el uso de datos semi-estructurados ha creado nuevas oportunidades para el minado de datos, el cual tradicionalmente ha trabajado con conjuntos de datos tabulares, reflejando la fuerte asociación entre la minería de datos y las bases de datos relacionales. Gran parte de los datos interesantes y minables del mundo no cuadran fácilmente en bases de datos relacionales, aunque una generación de ingenieros de software han sido entrenados para creer que es la única manera de manejar datos y los algoritmos de minería de datos han sido desarrollados generalmente para trabajar solo con datos tabulares.

XML, la manera más frecuente de presentar datos semi-estructurados, es capaz de representar tanto datos tabulares como árboles arbitrarios. Cualquier representación particular de datos a ser intercambiados entre 2 aplicaciones en XML se describe normalmente usando un esquema generalmente escrito en XSD. Los ejemplos prácticos de tales esquemas, por ejemplo NewsML, normalmente son muy sofisticados, conteniendo múltiples subárboles opcionales, usados para representar datos de casos especiales. Frecuentemente alrededor del 90% del esquema está abocado a la definición de esos datos y subárboles opcionales.

Por lo tanto, los mensajes y los datos que son transmitidos o codificados usando XML y que conforman al mismo esquema pueden contener datos muy diferentes según lo que se transmita.

Estos datos presentan grandes problemas para el minado de datos tradicional. Dos mensajes que conforman al mismo esquema pueden tener pocos datos en común. Construir un conjunto de entrenamiento para tales datos significa que si uno intenta formatearlos tabularmente, grandes secciones de las tablas estarían o podrían estar vacías.

Hay un supuesto tácito hecho en el diseño de la mayoría de los algoritmos de minería de datos que es que los datos presentados estarán completos. Los algoritmos de aprendizaje automático funcionan mal con conjuntos de datos incompletos donde solo se suministra parte de la información. La mayoría de las veces es mejor una mejor presentación del modelo con una representación más cuidadosa e imparcial de las entradas y salidas. Un área particularmente relevante donde encontrar la estructura y el modelo adecuados es en la minería de textos.

XPath es el mecanismo estándar usado para referir a nodos y elementos de datos dentro de un XML. Tiene similitudes con las técnicas estándar para la navegación de jerarquías de directos usadas en las interfaces de usuario de los sistemas operativos. Para minería de datos y estructuras de datos XML de cualquier forma, se requieren al menos dos extensiones para la minería de datos convencional. Estos son: (1) la habilidad de asociar un enunciado XPath con cualquier patrón de datos y sub enunciados con cada nodo de datos en el patrón y (2) la habilidad de minar la presencia y la cantidad de nodos o conjuntos de nodos dentro del documento.

Como ejemplo, si uno representara un árbol familiar en XML usando estas extensiones uno podría crear un conjunto de datos conteniendo todos los individuos en el árbol, los ítems de datos tales como el nombre y la edad de muerte tanto como nodos relacionados tales como el número de hijos. Búsquedas más sofisticadas podrían extraer datos como cuánto vivieron los abuelos, etc.

La suma de estos tipos de datos relacionados con la estructura de un documento o mensaje facilita el minado de estructuras.

• Andrew N Edmonds, On data mining tree structured data in XML', Data mining UK conference, University of Nottingham, Agosto 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
• F. Hadzic, H. Tan, T.S. Dillon, Mining of Data with Complex Structures, Springer, 2010. ISBN 978-3-642-17556-5

• 5to Taller Internacional en Minería y Aprendizaje con Grafos, Firenza, 1-3 de agosto de 2007 Archivado el 4 de agosto de 2020 en Wayback Machine.