• 1. Общие принципы индуктивного обучения
  • 2. Обнаружение знаний в базах данных
  • 3. Темпоральные базы данных
  • Список литературы [Matheus et al., 2003]
  • [Michalski,1983]
  • [Вагин и др. 2004]
  • [Torp et al.,1998]

  • Скачать 92.78 Kb.


    Дата21.08.2018
    Размер92.78 Kb.

    Скачать 92.78 Kb.

    Олег, извини за занудство, но я начала верстать свой доклад с Петровским и столкнулась с проблемами в этом шаблоне



    УДК 007:681.518.2

    ИНДУКТИВНОЕ ОБУЧЕНИЕ ДЛЯ ОБНАРУЖЕНИЯ ЗНАНИЙ В ОБЛАСТИ ТЕМПОРАЛЬНЫХ БАЗ ДАННЫХ

    М. М. Виньков1, И.Б. Фоминых2

    В работе рассматриваются аспекты применения существующих систем индуктивного обучения для обнаружения знаний в области темпоральных баз данных. Делается вывод о более важном (по сравнению с «обычными» базами данных) значении предварительных знаний, используемых в процессе формирования индуктивных гипотез.

    Введение

    Проблема обнаружения знаний в области баз данных, в иностранной литературе обозначаемая как KDD (Knowledge Discovery in Data Bases), давно и хорошо известна и важность ее не вызывает сомнений. К настоящему времени уже накоплен солидный опыт ее решения, воплощенный как в теоретических исследованиях, так и в созданных на их основе инструментальных средствах, причем некоторые из них достигли стадии коммерческой системы [Matheus et al., 2003]. Большое значение для KDD имеет индуктивное обучение, сущностью которого в данном случае является обобщение частных фактов, содержащихся в базах данных, для формирования индуктивной гипотезы, которая выражает скрытую в этих данных закономерность. В то же время, относительно малоисследованной остается задача обнаружения знаний в темпоральных базах данных (далее будем обозначать ее KDTDB – Knowledge Discovery in Temporal Data Bases), отражающих изменения предметной области, происходящие во времени. Эту задачу следует отличать от задачи обнаружения знаний в динамических базах данных, содержимое которых меняется во времени, обычно путем добавления новых записей к уже имеющимся. Далее речь пойдет о некоторых проблемах, связанных с KDTDB.


    1. Общие принципы индуктивного обучения

    Классическая общая постановка задачи индуктивного обучения, принадлежащая Р. Михальскому, была предложена в [Michalski et al., 1983].

    Дано.

    1. Наблюдаемые утверждения (факты) F, которые представляют собой частное знание относительно некоторых объектов – ситуаций, событий, явлений и т.п.



    2.(Необязательно). Пробное индуктивное предположение (гипотеза) Н0.

    3. Предварительное знание N, которое определяет допущения и ограничения, наложенные на наблюдаемые утверждения и возможные гипотезы, а также критерии предпочтения, характеризующие желательные свойства гипотез.

    Найти.

    Индуктивную гипотезу H, которая тавтологически или слабо имплицирует наблюдаемые утверждения F и согласуется с предварительным знанием N.



    Говорят, что индуктивная гипотеза H тавтологически имплицирует наблюдаемые утверждения F, если F логически следует из H.

    Индуктивная гипотеза H слабо имплицирует наблюдаемые утверждения F, если F не с необходимостью, а лишь с правдоподобием или частично является следствием H. Допуская слабую импликацию, системы индуктивного вывода включают методы порождения «мягких» гипотез, которые могут выражаться, например, вероятностно.

    Индуктивная гипотеза H представляет собой описание одного или нескольких классов объектов. В зависимости от соотношения между фактами F и гипотезой H индуктивное обучение разделяют на две категории: обучение по примерам и обучение на основе наблюдения. Категория задач обучения по примерам отличается тем, что наблюдаемые факты F, характеризующие какие-либо объекты произвольной природы, включают в себя информацию о принадлежности этих объектов к одному или нескольким классам. Число и имена этих классов известны заранее и потому объекты могут рассматриваться как примеры и контрпримеры тех классов, в которые они, соответственно, входят или не входят. Интенсиональное описание этих классов и составляет основное содержание индуктивной гипотезы H в задачах обучения по примерам. При обучении на основе наблюдения объекты предварительно не классифицированы, заранее неизвестно, обычно, и число классов наблюдаемых объектов, интенсиональное описание которых [Michalski,1983] и в этом случае составляет основное содержание индуктивной гипотезы H.

    Важной особенностью существующих алгоритмов индуктивного обучения являются выразительные возможности языка, на котором описаны факты F и индуктивная гипотеза H. В большинстве случаев эти возможности соответствуют языку классической логики высказываний. Это имеет место тогда, когда для описания фактов, относящихся к объектам, используется атрибутное представление, при котором описание каждого объекта с логической точки зрения представляет собой конъюнкцию высказываний о значениях атрибутов, характеризующих свойства данного объекта. Каждое такое высказывание будем называть дескриптором. Если выразительные возможности языка описания фактов превосходят выразительные возможности языка логики высказываний, это говорит о том, что объекты имеют внутреннюю структуру и/или находятся в каких-либо отношениях друг с другом. Такое описание фактов называется структурным. Лишь немногие известные алгоритмы допускают использование структурных описаний фактов [Добрынин, 2002]. Заметим, что любые структурные описания фактов могут быть преобразованы в атрибутные, однако в общем случае при этом наблюдается экспоненциальная зависимость числа необходимых атрибутов от сложности структуры. Дальнейшее обсуждение будет относиться в основном к атрибутному представлению.

    Для описания индуктивной гипотезы чаще всего используется подмножество множества дескрипторов, использованных для описания фактов. В этом случае говорят о селективной индукции. Если в описании гипотезы присутствуют дескрипторы, не использовавшиеся в описаниях фактов, то говорят, что в этом случае имеет место конструктивная индукция, встречающаяся намного реже.

    2. Обнаружение знаний в базах данных

    Современные технологии баз данных позволяют собирать и хранить информацию из большого числа различных источников в объеме, еще недавно казавшимся невозможным. Хотя эти технологии обеспечивают возможность весьма экономного хранения информации, ее анализ, который имеет целью осмысление имеющихся данных и поиск скрытых в них закономерностей, не является простой задачей. Индуктивное обучение уже показало себя как одно из эффективных средств такого анализа, однако его использование в этих целях сталкивается с рядом проблем [Вагин и др. 2004].

    Многие трудности объясняются тем обстоятельством, что современные базы данных создавались без учета возможности использования в дальнейшем существующих алгоритмов индуктивного обучения для анализа хранимой в них информации. Это приводит к тому, что постановка конкретной задачи индуктивного обучения часто оказывается весьма трудоемким процессом.

    В [Вагин и др., 2004] приведены этапы процесса обнаружения знаний. Рассмотрим их применительно к модели индуктивного обучения, принадлежащей Р. Михальскому.

    1. Исследование и осмысление прикладной области, к которой относятся первичные данные и формулировка целей пользователя. На этом этапе определяется, что, собственно, считать объектом и какого вида индуктивная гипотеза может быть интересна для пользователя.

    2. Формирования множества объектов, на которых планируется использовать один или несколько алгоритмов индуктивного обучения.

    3. Предварительная подготовка данных. На этом этапе производится устранение шумов и заведомо нерелевантных дескрипторов. По завершении этого этапа оказывается сформированным множество фактов F.

    4. Формирование предварительных знаний N. В частности, определяется подмножество дескрипторов, которые допускается использовать при описании индуктивной гипотезы, а также (в случае выбора категории индуктивного обучения на основе наблюдения) подмножество дескрипторов, влияющих на выбранные критерии предпочтения (которых может быть один или несколько).

    5. Собственно решение поставленной задачи индуктивного обучения.

    Последующие этапы: интерпретация полученных результатов и консолидация выявленных знаний уже не относятся к задаче индуктивного обучения.



    3. Темпоральные базы данных

    Данные, связанные с определенными датами (временными метками) или временными интервалами принято называть темпоральными. Темпоральные базы данных – это базы данных, хранящие темпоральные данные и имеющие средства специальной интерпретации временных меток и интервалов. В категорию темпоральных баз данных не попадают обычные реляционные базы данных, в которых поддерживаются связанные со временем типы данных, но интерпретацией и связью данных (или событий) между собой с учетом времени приходится заниматься разработчикам приложений. В «настоящей» темпоральной базе данных учитываются специфическая природа времени и изменчивость данных с течением времени. Реляционная модель данных дает ряд преимуществ для хранения данных, обработки и представления результатов запросов и поэтому почти все существующие темпоральные базы данных представляют собой надстройку над реляционной системой, так что темпоральное расширение является лишь одним из дополнительных признаков хранимых данных. Существуют различные способы дополнения и расширения обычных реляционных СУБД поддержкой темпоральной модели данных. Почти все такие способы сводятся к созданию специального функционального блока, отвечающего за разбор темпоральных запросов, подмену их некоторыми реляционными вычислениями, а потом обратное преобразование в требуемое темпоральное представление для возвращения результатов пользователю. С точки зрения реализации основным отличием является уровень «вмешательства» в реляционную СУБД, а также степень сложности темпоральных преобразований. Сравнение различных вариантов реализации промежуточного слоя представлено, например, в [Thorp et al.,1998].

    Однако, с точки зрения обнаружения знаний с помощью индуктивного обучения более важны отличия, которые проявляются на концептуальном уровне модели темпоральных данных. В первую очередь эти отличия относятся к выбору темпорального домена. При этом большое значение имеют ответы на следующие вопросы.

    1. Является ли время точечным или интервальным.

    2. Является ли время линейным или ветвящимся.

    3. Если время точечное, то является ли оно непрерывным или дискретным.

    4. Является ли время одномерным или многомерным.

    В настоящее время наиболее распространены темпоральные базы данных с точечным, линейным, дискретным, двумерным временем [Chomicki, 1994]. Однако, существуют и другие варианты темпральных доменов концептуальной модели темпоральных данных, что является одним из препятствий на пути создания универсальной системы индуктивного обучения в области темпоральных баз данных. Но и применительно к наиболее распространенной модели темпоральных данных индуктивное обучение с использованием известных алгоритмов сталкивается с трудностями. На наш взгляд, основная проблема здесь связана со сравнительно невысокой эффективностью селективной индукции для случая темпоральных данных (при любой конфигурации темпорального домена). Хотя и в этом случае описания объектов могут рассматриваться как конъюнкции (темпоральных) дескрипторов, эти темпоральные дескрипторы (при атрибутном представлении объектов) уже не могут быть выражены средствами классической логики высказываний, из-за появления дополнительного темпорального измерения. Такие темпоральные дескрипторы интерпретируются как высказывания примерно следующего содержания: «объект oi в момент времени tk имел свойство Pj», где oi и tk константы, а Pi – бинарный предикатный символ, именующий некоторое свойство, т.е. такой дескриптор можно представить как Pi (oi, tk). При использовании в индуктивной гипотезе, данный дескриптор будет интерпретироваться как описание класса всех объектов, имевших в некоторый конкретный момент времени tk свойство Pj. На этом возможности селективной индукции применительно к темпоральным данным исчерпываются. С ее помощью в рассматриваемом случае могут порождаться только весьма частные гипотезы и вероятность обнаружения полезных знаний относительно невелика.



    Представляется, что эффективность индуктивного обучения в области темпоральных баз данных можно повысить благодаря использованию конструктивной индукции. Наиболее распространенным ее применением в настоящее время является использование иерархии обобщений, заданной на множестве значений атрибутов. В этом случае при порождении дескрипторов, используемых для описания классов объектов, значения атрибутов, находящиеся на нижнем уровне иерархии и использованные для описания конкретных объектов заменяются на значения, находящиеся на более высоком уровне. Например, для атрибута «форма» значение «пятиугольник» может быть заменено на значение «многоугольник». Применительно к темпоральному случаю представляется возможным использовать грануляцию времени по аналогии с тем, как используется для этой цели иерархия обобщений значений атрибутов. Другим вариантом темпоральной конструктивной индукции можно считать порождение дескрипторов вида t Pi (oi, t). При использовании в индуктивной гипотезе данный дескриптор будет интерпретироваться как описание класса всех объектов, когда либо имевших свойство Pj. Автоматическое порождение новых темпоральных дескрипторов более сложной структуры, например, логически эквивалентных формулам темпоральной логики, включающим бинарные темпоральные связки, например, U (until) может привести к неприемлемому увеличению пространства поиска индуктивных гипотез. В этом случае в состав предварительных знаний должны быть включены ограничения, зависящие от конкретной предметной области.

    Список литературы

    [Matheus et al., 2003] Matheus C.J., Chan P.K. Systems for data discovery in databases, IEEE transactions for Knowledge and data Engeneering, Vol 5(6) 903-913.

    [Michalski, et al., 1983] Michalski R.S., Carbonell J.G., Mitchell T.M. Machine Learning. An Artificial Intelligence Approach. Palo Alto: Tioga Publishing Co., 1983.

    [Michalski,1983] Michalski R.S. Theory and methodology of inductive learning. Artificial Intelligence. 1983. – v. 20, N 1-2.

    [Добрынин, 2002] Представление пространственной структуры молекул химических соединений для интеллектуального анализа данных. Восьмая национальная конференция по искусственному интеллекту с международным участием. Труды конференции. Т. 1, 2002.

    [Вагин и др. 2004] Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах.- М.: Физматлит, 2004.

    [Torp et al.,1998] Torp K., Jensen C.S., Snodgrass R.T. Stratum approaches to Temporal DBMS Implementation. In Proceedings of the 1998 data base engineering and application symposium. Cardiff. Wales. UK. July, 1998.

    [Chomicki, 1994] Temporal Query Languages. In Proc. International Conference on Temporal Logics. Bonn. 1994.



     Работа выполнена при финансовой поддержке РФФИ


    1 129090, Москва, ул.Щепкина 22,ГУ РосНИИ ИТ и АП, vinkovmm@mail.ru


    2 129090, Москва, ул.Щепкина 22,ГУ РосНИИ ИТ и АП, fomin77@land.ru


    Коьрта
    Контакты

        Главная страница


    Олег, извини за занудство, но я начала верстать свой доклад с Петровским и столкнулась с проблемами в этом шаблоне

    Скачать 92.78 Kb.