Общий подход в прогнозирующих методах

В системах, моделирующих мышление, обобщение [11] понимают как процесс получения знаний, объясняющих имеющиеся факты, и способных объяснять, классифицировать или предсказывать новые. В общем виде задача обобщения представлена следующим образом: по совокупности наблюдений (фактов) F, совокупности требований и допущений к виду результирующей гипотезы H и совокупности базовых знаний и предположений, включающих знания об особенностях предметной области, выбранном способе представленных знаний, допустимых операторов, эвристик и др., сформировать гипотезу H: (H «объясняет» F).

Форма представления и общий вид гипотезы H, а также выбранные модели обобщения зависят от цели обобщения и выбранного способа представления знаний. Можно выделить модели обобщения по выборкам и модели обобщения по данным. В первом случае совокупность фактов F имеет вид обучающей выборки – множества объектов, каждый из которых сопоставляется с именем некоторого класса. Целью обобщения в этом случае может быть:

- формирование понятий, то есть построение по данным обучающей выборки для каждого класса максимальной совокупности его общих характеристик;

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

- определение закономерности последовательного появления событий.

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

· получение гипотезы, обобщающей данные факты;

· выделение образов на множестве наблюдаемых данных, группировка данных по признакам;

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

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

Проблема формирования понятий по признаковым описаниям была сформулирована М.М. Бонгардом[1]. Процедура обучения по Бонгарду является сложным вариантом обучения «с учителем» и основывается на двух этапах: обучении и экзамене. Результатом процедуры обучения будет некоторое решающее правило (набор неких правил), которое должно позволять принять решение об отнесении конкретных примеров к понятию. После того, как распознающее правило на обучающей выборке построено, проводится экзамен – с помощью распознающего правила надо ответить на поставленный вопрос, т.е. отнести объекты новой, экзаменационной выборки к определенному классу. Результатом экзамена является процент достоверности решающего правила, то есть количество правильно распознанных объектов из числа экзаменационной выборки. Если этот процент окажется неприемлемым, то есть результат экзамена будет неудовлетворительным, то необходимо уточнить новое решающее правило, полностью или частично заменив обучающую выборку. В качестве обучающей выборки в данном случае может служить и та экзаменационная выборка, которая дала неудовлетворительные результаты.

Решающее правило является корректным, если оно в дальнейшем успешно распознает примеры (положительные) и контрпримеры (отрицательные) обучающей выборки.

Классификация алгоритмов качественного обобщения по признакам

Способы представления исходной информации в интеллектуальных системах

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

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

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

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

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

а) отображает характерные для этого множества логические отношения между значениями признаков;

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

Для описания объекта будем использовать признаки A₁, A₂, …, A_n. Каждый объект o O характеризуется набором конкретных значений этих признаков (атрибутов) o = { a₁, a₂, …, a_n }, где a_i – значение i-го признака.

Рассмотрим отдельные виды признаков. Значения, которые могут принимать признаки объекта, относятся к трем основным типам: количественные, или числовые, качественные и шкалированные. То, какие значения принимают признаки, может оказать большое влияние на процесс обобщения.

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

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

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

Варианты реализации систем обобщения

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

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

1.5.2.1 Обучение "без учителя": основные понятия

Главное отличие обучения «без учителя» от обучения «с учителем» в том, что исходная информация представлена в виде обучающего множества, не разделенного на классы. Это значит, что для объектов обучающего множества не задано, к каким классам они принадлежат. Задача обучения в этом случае сводится к разделению объектов выборки на группы объектов, «сходных» друг с другом по каким-либо общим признакам. Более точно задача алгоритмов данного типа формулируется следующим образом.

Пусть обучающая выборка содержит M объектов:

Каждый из этих объектов представляет собой n -мерный вектор Х_i значений признаков:

Где – значение j-го признака для i-го объекта, n – количество признаков, характеризующих объект.

Требуется в соответствии с заданным критерием разделить набор на классы, количество которых заранее не известно. Под критерием подразумевается мера близости всех объектов одного класса между собой. Будем считать, что работа алгоритма завершена успешно, если классы, сформированные в результате работы алгоритма, достаточно компактны и, возможно, выполнены некоторые дополнительные критерии.

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

1.5.2.2. Обучение "с учителем": постановка задачи

Пусть имеется множество объектов, состоящее из положительных и отрицательных примеров формируемых понятий. Назовем такое множество обучающей выборкой. На основании обучающей выборки необходимо построить понятие [11], разделяющее положительные и отрицательные объекты.

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

Пусть О – множество всех объектов, представленных в некоторой системе знаний, V – множество положительных объектов и W – множество отрицательных объектов. Будем рассматривать случай, когда О = V W, V W = 0, W = W_i и W_i W_j = 0 (i ≠ j). Пусть K – непустое множество объектов, такое, что K = K⁺K^–, где K⁺ V и K^– W. Будем называть K обучающей выборкой. На основании обучающей выборки надо построить правило, разделяющее положительные и отрицательные объекты обучающей выборки.

Понятие, таким образом, сформировано, если удалось построить решающее правило, которое для любого примера из обучающей выборки указывает, принадлежит ли этот пример понятию или нет. Алгоритмы, которые мы исследуем, формируют решение в виде правил типа «ЕСЛИ условие, ТО искомое понятие». Условие представляется в виде логической функции, в которой булевы переменные, отражающие значения признаков, соединены логическими операциями конъюнкции, дизъюнкции и отрицания. Решающее правило является корректным, если оно в дальнейшем успешно распознает объекты, не вошедшие первоначально в обучающую выборку.

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

 

 

Выводы

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

В результате, для изучения было выбрано направление обучения «с учителем». Алгоритмы обучения «с учителем» дают возможность строить решающие правила и с помощью них проводить классификацию новых объектов. В следующей главе будет дан обзор некоторых алгоритмов обобщения, таких как алгоритм ДРЕВ, ID3, AQ, ABCN2.