Structure mining

Введение

Поиск и извлечение информации из полуструктурированных наборов данных Структурный майнинг или добыча структурированных данных - это процесс поиска и извлечения полезной информации из полуструктурированных наборов данных. Графический майнинг, последовательный майнинг паттернов и молекулярный майнинг являются особыми случаями структурированного майнинга данных.

Описание

Рост использования полуструктурированных данных создал новые возможности для добычи данных, которая традиционно была связана с табличными наборами данных, что отражает сильную связь между добычей данных и реляционными базами данных. Большая часть интересных и добываемых данных в мире не легко складывается в реляционные базы данных, хотя поколение инженеров-программистов было обучено полагать, что это единственный способ обработки данных, и алгоритмы добычи данных, как правило, разрабатывались только для обработки табличных данных. XML, являясь наиболее распространенным способом представления полуструктурированных данных, способен представлять как табличные данные, так и произвольные деревья. Любое конкретное представление данных, которые должны быть обменены между двумя приложениями в XML, обычно описывается схемой, часто написанной в XSD. Практические примеры таких схем, например NewsML, обычно очень сложные, содержащие несколько дополнительных поддеревьев, используемых для представления данных специальных случаев. Обычно около 90% схемы касается определения этих необязательных элементов данных и подделок. Поэтому сообщения и данные, которые передаются или кодируются с использованием XML и соответствуют одной и той же схеме, могут содержать очень разные данные в зависимости от того, что передается. Такие данные представляют большие проблемы для обычного добычи данных. Два сообщения, соответствующие одной и той же схеме, могут иметь мало общего в данных. Создание учебного набора из таких данных означает, что если бы кто-то попытался отформатировать его в виде табличных данных для обычного добычи данных, большие разделы таблиц были бы или могли быть пустыми. В разработке большинства алгоритмов добычи данных существует молчаливое предположение, что представленные данные будут полными. Другая необходимость заключается в том, что фактические алгоритмы добычи, используемые, будь то контролируемые или не контролируемые, должны иметь возможность обрабатывать скудные данные. Например, алгоритмы машинного обучения плохо работают с неполными наборами данных, где предоставляется только часть информации. Например, методы, основанные на нейронных сетях. или алгоритм ID3 Росса Куинлана. высокой точности при использовании хороших и репрезентативных образцов проблемы, но плохо работают с предвзятыми данными. В большинстве случаев достаточно более качественной презентации модели с более тщательным и объективным представлением входных и выходных данных. Особенно важной областью, где поиск соответствующей структуры и модели является ключевым вопросом, является текстовое майнинг. XPath - это стандартный механизм, используемый для ссылки на узлы и элементы данных в XML. Он имеет сходство со стандартными методами навигации по иерархии каталогов, используемыми в пользовательских интерфейсах операционных систем. Для добычи и структурирования XML-данных любой формы требуется как минимум два расширения для обычного добычи данных. Это возможность ассоциировать инструкцию XPath с любым паттерном данных и подзаявлениями с каждым узлом данных в паттерне данных, а также возможность извлекать наличие и количество любого узла или набора узлов в документе. Например, если кто-то должен был представлять генеалогическое дерево в XML, используя эти расширения, можно создать набор данных, содержащий все отдельные узлы в дереве, элементы данных, такие как имя и возраст при смерти, и количество связанных узлов, таких как количество детей. Более сложные поиски могут получить данные, такие как продолжительность жизни бабушки и дедушки и т. д. Добавление этих типов данных, связанных со структурой документа или сообщения, облегчает извлечение структур.

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. There is a tacit assumption made in the design of most data mining algorithms that the data presented will be complete. The other necessity is that the actual mining algorithms employed, whether supervised or unsupervised, must be able to handle sparse data. Namely, machine learning algorithms perform badly with incomplete data sets where only part of the information is supplied. For instance methods based on neural networks. or Ross Quinlan's ID3 algorithm. are highly accurate with good and representative samples of the problem, but perform badly with biased data. Most of times better model presentation with more careful and unbiased representation of input and output is enough. A particularly relevant area where finding the appropriate structure and model is the key issue is text mining. XPath is the standard mechanism used to refer to 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 node 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.