Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

22.02.2017

Google
WWW CITForum.ru
С Новым годом!
2007 г.

Методы добычи данных при построении локальной метрики в системах вывода по прецедентам

Л. Е. Карпов, В. Н. Юдин
Препринт ИСП РАН
1

Содержание

1. Введение
2. Вывод на основе прецедентов в системах поддержки принятия решений
2.1. Концепция вывода
2.2. Декомпозиция метода (основные фазы)
2.3. Примеры систем вывода на основе прецедентов
3. Добыча данных в системах поддержки принятия решений и прогнозирования
3.1. Различные подходы к классификации области добычи данных
3.2. Классификация задач добычи данных
3.3. Классификация систем добычи данных
4. Интегрированный подход к построению систем поддержки принятия решений
4.1. Два подхода к интеграции вывода на основе прецедентов и добычи данных
4.2. Использование методов добычи данных в системах вывода по прецедентам
4.3. Использование прецедентов в системах добычи данных
5. Использование методов добычи данных для отбора прецедентов
5.1. Байесовские сети
5.2. Разбиение базы прецедентов на классы
5.3. Другие примеры систем, использующих интегрированный подход
6. Понятие контекстно-зависимой локальной метрики
7. Описание контекстно-зависимой локальной метрики
8. Заключение
Библиография

1. Введение

При современном уровне развития информационных технологий и, более конкретно, систем поддержки принятия решений различают два направления в развитии логического вывода знаний [Каменнова 95]:

  • развитие систем логического вывода, основанного на правилах;
  • развитие систем логического вывода, основанного на прецедентах.

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

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

Но окружающий мир сложен. Существует много слабо формализованных задач, для которых, возможно, будут найдены решения. Кроме того, существует ряд задач, для которых никогда не будет найдено формальное решение (судопроизводство, медицина). Актуальность проблемы обусловлена и многочисленностью таких задач, и практической потребностью найти хотя бы одно сколько-нибудь подходящее решение там, где из-за отсутствия строго формализованного метода нельзя найти все или самое оптимальное из всех.

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

Моделирование такого подхода к решению проблем, основанного на опыте прошлых ситуаций, привело к появлению технологии логического вывода, основанного на прецедентах (по-английски – Case-Based Reasoning, или CBR), и в дальнейшем – к созданию программных продуктов, реализующих эту технологию.

В ряде ситуаций метод вывода по прецедентам имеет серьезные преимущества по сравнению с выводом, основанным на правилах, и особенно эффективен, когда:

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

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

Системы вывода по прецедентам показывают очень хорошие результаты в самых разнообразных задачах, но обладают рядом существенных недостатков.

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

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

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

Еще один недостаток метода связан с конструкцией прецедентов и назначения уместных весов их атрибутам, что уменьшает применимость таких систем в разных предметных областях.

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

Обе проблемы – поиск прецедентов и адаптация выбранного решения – решаются (полностью или частично) с привлечением фонового знания, иными словами, знания о предметной области (domain knowledge). Существуют разные способы получения информации о предметной области:

  • Привлечение экспертного знания. Оно может выражаться, например, в ограничениях, накладываемых на диапазоны изменений признаков объектов, или же в формулировании набора правил для разбиения базы прецедентов на классы (построение классификатора).
  • Получение необходимых знаний из набора имеющихся данных методами добычи данных (по-английски – Data Mining). Сюда относятся все методы выявления отношений в данных, в частности, кластеризация, регрессия, поиск ассоциаций. Использование методов добычи данных может выделить узкую группу показателей, от которых зависит интересующая исследователя характеристика, и представить обнаруженную закономерность в аналитической форме.
  • Формирование знаний на основе обучающей выборки, представленной экспертом (обучение с учителем). Этот способ включает в себя оба первых.

    Изначально в системах вывода по прецедентам в качестве источников фонового знания выступали эксперты – высококвалифицированные специалисты предметных областей, а также текстовые материалы – от учебников до протоколов, и, разумеется, базы данных (имплицитные источники знаний). Роль эксперта (затратная по ресурсам и времени) заключалась в вербализации, то есть переводе таких источников в эксплицитную форму. Учитывая, что важнейшей задачей в процессе формализации извлечения знаний является минимизация роли эксперта, его роль должны взять на себя средства добычи данных.

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

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

    Предлагается ввести в базе прецедентов отношения эквивалентности, которые выражают принадлежность оцениваемых объектов к каким-либо классам, рассматриваемым как самостоятельные семантические единицы. Классы представляют номинальную шкалу (шкала наименований – не количественная, а строго качественная, она не приписывает классам никаких численно выражаемых атрибутов). Можно считать, что объекты, отнесенные к одному и тому же классу, эквивалентны с точки зрения данной номинальной шкалы. Такие классы (или основные понятия) в базе прецедентов могут быть построены различными способами: с помощью привлечения экспертного знания или путем предварительной кластеризации базы прецедентов. Эти классы, в свою очередь, предлагается использовать как основу для предлагаемой меры близости прецедентов.

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

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


    1 Работа поддержана грантами Российского фонда фундаментальных исследований № 06-07-89098 и № 06-01-00503

  • Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

    Подписка на новости IT-портала CITForum.ru
    (библиотека, CITKIT.ru, CitCity)

    Новые публикации:

    24 декабря

    CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...