Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ГЛАВА 2. ИНЖЕНЕРИЯ ЗНАНИЙ
Одной из важнейших проблем при создании интеллектуальных информационных систем является адекватное отображение знаний экспертов в памяти компьютера. Инженерия знаний изучает и разрабатывает вопросы, связанные с получением знаний, их анализом и формализацией для дальнейшей реализации в интеллектуальной системе. Необходимая для работы интеллектуальной системы модель действительности должна содержать описания основных объектов действительности, их имена, описания устойчивых связей и зависимостей между объектами и их совокупностями, информацию об их важности, сведения о том, каким образом эти связи, зависимости и иные когнитивные структуры могут быть использованы.
Существует несколько стратегий получения знаний. Наиболее распространенные [17]:
– приобретение;
– извлечение;
– формирование.
Под приобретением знаний понимается способ автоматизированного построения базы знаний посредством диалога эксперта и специальной программы (при этом структура знаний заранее закладывается в программу). Эта стратегия требует существенной предварительной проработки предметной области. Системы приобретения знаний действительно приобретают готовые фрагменты знаний в соответствии со структурами, заложенными разработчиками систем. Большинство этих инструментальных средств специально ориентировано на конкретные экспертные системы с жестко обозначенной предметной областью и моделью представления знаний, т.е. не являются универсальными. Например, система TEIRESIAS, ставшая прародительницей всех инструментариев для приобретения знаний, предназначена для пополнения базы знаний системы MYCIN или ее дочерних ветвей, построенных на "оболочке" EMYCIN в области медицинской диагностики с использованием продукционной модели представления знаний.
Термин извлечение знаний касается непосредственного живого контакта инженера по знаниям с источником знаний (экспертом, специальной литературой и др.) без использования вычислительной техники.
Термин формирование знаний традиционно закрепился за чрезвычайно перспективной и активно развивающейся областью инженерии знаний, которая занимается разработкой моделей, методов и алгоритмов анализа данных для получения знаний и обучения. Данный процесс получения из «сырых» данных новой, потенциально полезной информации о предметной области назван “обнаружением знаний в базах данных” (knowledge discovery in databases – KDD) Эта область включает индуктивные модели формирования гипотез на основе обучающих выборок, обучение по аналогии и многие другие методы.
2.1. Приобретение знаний
Основные этапы реализации системы приобретения знаний включают:
– Интервью для определения актуальной области, в которой происходит процесс решения интересующей проблемы, и расчленение ее на автономные области.
– Автоматизированное интервью для выявления и формирования декларативной модели предметной области.
– Протокольный анализ к выявленным на предыдущем этапе понятиям и отношениям предметной области для пополнения модели процедурными знаниями.
– Протокольный анализ для пополнения декларативных знаний модели.
– Проверка полноты модели.
2.1.1. Имена, свойства, связи
Задачей методов автоматизированного приобретения знаний является выявление имен объектов предметной области, их свойств, связей на множестве объектов, приемов и правил рассуждений.
Имена. Имя – единица языка, соответствующая со стороны семантики отражению отдельного предмета, объекта или явления объективного мира, со стороны синтаксиса – субъекту или объекту высказывания, индивидной константе или переменной в предложении, месту в предикате или в структурной схеме предложения.
Индивидное имя – имя существительное, являющееся именем объекта наинизшего типа, объекта, не являющегося множеством. Общее имя – имя, обозначающее неопределенный объект или множество объектов.
Метаимя – имя в той части языка, которая выступает как метаязык по отношению к другой части того же языка. Метаименам не соответствует никакие множества объектов. Они являются средствами внутриязыковой классификации и служат целям самого языка в сфере лексики (примеры: слова типа совокупность, множество, часть и т.д.). Метаименами по большей части представляют предикаты.
Индивидные имена обозначают конкретные объекты действительности. Общие имена соотносят предложения с множеством понятий. Понятие включает отработанную обществом совокупность признаков, хотя в разных употреблениях слова эта совокупность выступает в разных своих частях. В случае употребления имени в функции субъекта высказывания реализуется минимальный набор признаков, достаточный для отождествления имени с предметом действительности.
Построение модели действительности должно предполагать выделение в источниках знаний не только имен – индивидных и общих – но и содержания тех понятий, которые этими именами представлены. Набор признаков содержания каждого понятия должен быть достаточен как для различения его от других понятий, так и для соотнесения с действительностью.
Выступая в качестве имени понятия, т.е. являясь именем множества, общее имя определяет объем понятия. В отличие от этого совокупность свойств характеризует вторую сторону понятия – его содержание.
Свойства. В общем случае, среди свойств понятия могут присутствовать: адресат (признак, характеризующий компонент или лицо к которому обращено воздействие); дестинатив (компонент, выражающий назначение); дименсив (размер, исчисляемая мера величины); квантитатив (количественные характеристики); квалитатив (качественные характеристики, свойства предмета); локатив (признак местонахождения) и др.;
Разумеется, фиксация проблемной области вносит в этот список коррективы.
Виды семантических связей. Под семантической связью в общем случае будем понимать отношение понятий в понятийной системе предметной области. При этом мы полагаем, что каждый носитель знаний о предметной области обладает некоторой концептуальной моделью области, по крайней мере, ее фрагментом, и свойства семантических связей согласуются с этой моделью. Рассмотрим виды этих связей:
– генеративная связь Gen, один компонент которой обозначает лицо или предмет, принадлежащий некоторой совокупности, категории, обозначаемой вторым компонентом;
– директивная связь Dir, в которой один компонент обозначает путь, направление второго компонента;
– инструментальная связь Ins, один компонент которой обозначает орудие действия, обозначаемого другим компонентом;
– каузальная связь Cous, один компонент которой обозначает причину проявления другого компонента спустя какое-то время;
– комитативная связь Com, один компонент которой обозначает сопровождающее другой компонент действие, сопутствующий предмет, сопровождающее лицо;
– коррелятивная связь Cor, один компонент которой выражает возможность наблюдения другого компонента или соответствия предмета другому предмету, назначению;
– негативная связь Neg, один компонент которой отрицает, исключает возможность проявления другого компонента;
– лимитативная связь Lim, один компонент которой обозначает сферу применения, назначения другого компонента;
– потенсивная связь Pot, в которой один компонент приводит к увеличению возможности появления другого спустя некоторое время;
– результативная связь Res, в которой один компонент выражает следствие действия второго;
– ситуативная связь Sit, в которой один компонент обозначает ситуацию, определяющую состояние или область действия второго компонента;
– финитивная связь Fin, в которой один компонент имеет значение цели, назначения другого.
Разумеется, этот список нельзя считать исчерпывающим. Кроме того, связи обладают свойствами транзитивности (Tr), нетранзитивности (Ntr), антитранзитивности (Atr), симметричности (Sm), антисимметричности (Ans), асимметричности (As), несимметричности (Ns), рефлексивности (Rf), антирефлексивности (Arf), нерефлексивности (Nrf).
2.1.2. Стратегии и сценарии автоматизированного интервью
Введем понятия стратегии и сценария интервью. Приемы интервью, направленные на выявление каких-либо элементов модели мира, будем называть стратегиями. Схему применения тех или иных стратегий будем называть сценарием.
Если интервью не имеет сценария, то оно называется неструктурированным, в противном случае – структурированным. Разумеется, если имеется ввиду автоматизированное интервью, то оно всегда структурированное.
Выявление базиса понятий и их свойств
Стратегия разбиения на ступени предназначена для выявления таксонометрической структуры событий предметной области, а также их структурных и классификационных свойств. Сценарий выбирается экспертом. Возможны комбинированные сценарии.
Сценарий "Имя – свойство".
1.1. Вопрос системы об имени события.
– Сообщение эксперта об имени события.
1.2. Вопрос системы об имени признака события.
– Сообщение эксперта об имени признака.
1.3. Вопрос системы о существовании множества значений признака.
– Ответ эксперта (Да/Нет).
В случае отрицательного ответа имя признака воспринимается как имя события. При этом:
а) пара (имя события, введенного на шаге 1.1, имя события, образованного на шаге 1.3) считается принадлежащей отношению R1;
б) если имя события, образованного на шаге 1.3, отсутствовало в базе знаний, то это событие рассматривается как новое и выполняется переход к п.1.2.
1.4. Вопрос системы о типе множества значений признака (непрерывное / дискретное).
– Соответствующий ответ эксперта.
1.5. Вопрос системы о единице измерения признака.
– Сообщение эксперта о единице измерения.
1.6. Вопрос системы о множестве значений признака (границы непрерывного множества/элементы дискретного).
– Сообщения эксперта о множестве значений признака.
В процессе выполнения шагов 1.2–1.6 создается глобальный объект: имя атрибута и область его значений. Совокупность таких объектов будем называть базисом области.
1.7. Вопрос системы о подмножестве значений атрибута, характерного для описываемого события.
– Сообщения эксперта о подмножестве значений атрибута.
В результате выполнения шага 1.7 с описываемым объектом связывается один из элементов базиса области с указанием подмножества области значений элемента базиса, характеризующего описываемый объект, т.е. формируется признак объекта.
Сценарий "Множество имен – свойство".
При работе сценария «Множество имен – свойство» шаг 1.1 повторяется многократно, а затем для каждого события выполняются шаги 1.2 – 1.7.
Стратегия репертуарной решетки для выявления свойств объектов.
Стратегия репертуарной решетки использует механизм преодоления когнитивной защиты эксперта, основанный на методах когнитивной психологии.
Он состоит в выявлении системы личностных психологических конструктов эксперта. Каждый конструкт формируется в результате некоторой факторизации множества шкал, каждая из которых, в свою очередь, образуется оппозицией свойств. Наиболее эффективный способ выявления оппозитных свойств – предъявление эксперту триад семантически связанных событий с предложением назвать свойство, отличающее одно событие от двух других.
На следующем шаге эксперту предлагается назвать имя оппозитного свойства. Таким образом, выявляются элементы множества личностных психологических конструктов конкретного эксперта.
С другой стороны, свойства, различающие события, это как раз те свойства, которые влияют на формирование решения. Эта процедура также используется для формирования базиса области. Пополнение базиса области осуществляется путем повторения этой процедуры с другими триадами.
Выявление семантических связей.
Выявление и представление в системе семантических связей основано на использовании их свойств, описанных выше (табл. 1).
Таблица 1
|
Тип связи |
Каноническая форма |
Свойства |
|
I. Gen(X,Y) Sit(X,Y) Neg(X,Y) II. Ins(X,Y) III. Com(X,Y) Cor(X,Y) IV. Fin(X,Y) Cous(X,Y) Pot(X,Y) |
«X является элементом Y» «X находится в ситуации Y» «X отрицает Y» «X является средством Y» «X сопровождается Y» «X иногда увеличивает возможность Y» «X является целью Y» «X вызывает Y» "X может вызывать Y" |
Ntr Arf Ns Tr Arf As Ntr Arf Sm Ntr Nrf Ns Tr Rf Ans Ntr Rf Sm Ntr Arf Ns Tr Nrf Ns Ntr Nrf Ns |
Для этой цели может быть использована стратегия выявления сходства.
Стратегия выявления сходства основана на установлении в интерактивном режиме некоторых свойств высказываний (и, тем самым, предикатных слов), а именно, сохранения или изменения истинности высказывания при перестановке имен событий; сохранения или изменения истинности высказывания при подстановке имен совпадающих событий; сравнении истинности двух высказываний, отличающихся одно от другого модальностью; на изменении формулировки высказывания путем уточнения предикатного слова, и порождении на этом основании гипотез о принадлежности пар событий тем или иным семантическим связям.
Стратегия выявления сходства реализуется с помощью некоторых критериев. Каждый критерий – интерактивная процедура, строящая минимальный универсум, обладающий определенным свойством, соответствующим «метафорическому» свойству исследуемого высказывания.
Для выявления свойств Rf, Nrf или Arf используется критерий подстановки.
Критерий подстановки. Эксперту предъявляется высказывание, полученное из канонической формы, в которой вместо имен обоих событий подставлено одно из них с призывом к эксперту сообщить свое мнение относительно истинности этого высказывания. В зависимости от ответа эксперта высказыванию приписывается то или иное значение Rf, Nrf или Arf.
Пусть, например, речь идет о поиске типа семантической связи между событиями "вегетативные расстройства"(X) и "головная боль"(Y) и исследуется следующее высказывание "вегетативные расстройства сопровождаются головной болью».
Тогда из списка канонических форм (табл. 1) выбирается форма "X сопровождается Y", далее, стратегия выполняет подстановки: "вегетативные расстройства" – вместо X и "вегетативные расстройства" вместо Y и предъявляет эксперту следующие вопросы:
– Считаете ли Вы высказывание "вегетативные расстройства сопровождаются вегетативными расстройствами" утверждением, которое:
1) является тавтологией;
2) не исключено;
3) невозможно.
Если эксперт указывает первый ответ, то высказыванию "вегетативные расстройства сопровождаются головной болью" приписывается свойство Rf, второй – Nrf; третий – Arf.
Опишем теперь три процедуры, интерпретирующие ответы эксперта: [L], 1([L]) и 2([L]) и строящие множества, которые для простоты будут иметь те же обозначения, что и процедуры.
Пусть высказывание Li = "A <предикатное слово> B" – из некоторого множества высказываний L.
а) положим [Li]= {(A,B)}; через [Li] обозначим множество, полученное на i-ом шаге процесса; [L0]= ;
тогда [Li]=[Li-1][ Li]; иначе говоря, процедура [Li] состоит в пополнении множества [Li-1] парой (A,B);
б) положим 1[Li]= {(A,B)} {(A,A)} {(B,B)};
1[Li] = 1[Li-1] 1[Li] – т.е. для каждого высказывания Li = множество [Li] пополняется парой (A,B) и парами (A,A) и (B,B);
в) 2[Li] = 2[Li-1] [ Li] если и только если AB;
Лемма 1. Отношение 1[L] рефлексивно, 2[L] антирефлексивно, [L] нерефлексивно.
Для определения свойства Sm или отсутствия такового используется критерий перестановки.
Критерий перестановки. Вместе с высказыванием "A<предикатное слово>B", эксперту предъявляется высказывание, в котором объект A заменен на B, а B – на A. В рассмотренном выше примере ему будет предложено ответить, справедливо ли утверждение, что "головная боль всегда сопровождается вегетативными расстройствами?"
– ДА / НЕТ
В случае утвердительного ответа, высказыванию приписывается свойство Sm, в случае отрицательного – Ns.
С критерием перестановки свяжем следующую процедуру 3(Li) пополнения множества Mi-1:для каждого высказывания Li="A <предикатор> B" из L: в множество Mi-1 помещаются пары (A,B) и (B,A).
Положим 3(L)= 3(L\Li) 3(Li).
Лемма 2. Отношение 3(L) симметрично.
В том случае, если высказывание антирефлексивно и не оказывается симметричным, для идентификации его типа необходимо уточнить характер несимметричности – возможную асимметричность.
Для установления асимметричности используется критерий обращения.
Критерий обращения. Для некоторого конкретного высказывания "A <предикатор> B", эксперту предлагается подтвердить принадлежность высказывания "B <предикатор> A" какому-либо высказыванию из последней графы таблицы. Если эксперт подтвердил, и высказывания "A <предикатор> B" и "B <предикатор> A" оказались в разных таблицах, то высказыванию "A <предикатор> B" приписывается свойство As.
Для выявления транзитивности используется критерий трансформации.
Критерий трансформации. Стратегия заключается в предъявлении эксперту новой формулировки высказывания, такой, которая, с одной стороны, исключает неоднозначное толкование экспертом, с другой – уточняет формулировку высказывания. Так, для каузального типа такой трансформацией (уточнением) является "Если A то необходимо появится B".
В случае подтверждения ее экспертом, высказыванию приписывается свойство Tr, иначе связь – Ntr. Этот критерий основан на том, что в четвертой части приведенной выше таблицы две похожие канонических формы Cоus и Pot отличаются друг от друга тем, что в Pot участвует модальность возможности, в отличие от Cous, в образовании которой участвует модальность необходимости. Что касается формы Fin, то она отличается от них своей антирефлексивностью.
Если рассмотреть процесс 4(Li), который для каждого высказывания "A <предикатор> B" из L высказывания "B <предикатор> C" (или высказывания "D <предикатор> A") помещает в Mi-1 пары (A,B) и (A,C) (или (D,B)), соответственно, то легко видеть, что имеет место
Лемма 3. Отношение 4(L) транзитивно. (Как и ранее, полагаем 4(L)= 4(L\Li) 4(Li)).
И, наконец, процедура 0(Li,M), которая для пары (A,B) высказывания Li ="A<предикатор>B" из L и бинарного отношения Mi-1 строит в Mi-1 все цепи вида (A1,A2),...(Ak,A) и образует множество Mi-1(A,B) если и только если BAk ни для какого k, т.е., если пара (A,B) не превращает никакую цепь из Mi-1 в цикл.
Лемма 4. 3(2(Q))= 2(3(Q)); 3(1(Q)= 1(3(Q ))
Лемма 5. Если в Q нет циклов, то 4(2(Q))=2(4(Q)); 4(1(Q))=1(4(Q)).
Используем введенные критерии и установленные факты для описания метода установления типов тех или иных высказываний.
Стратегию выявления сходства опишем как систему правил. Через Li будем обозначать текущее высказывание.
Введем вначале метаправило, определяющее дисциплину выполнения выписанных ниже правил:
0. Во всех тех случаях, когда в приведенных ниже правилах переход явно не определен, запускается ближайшее следующее в порядке возрастания номеров правило, условие которого к этому моменту оказалось выполненным.
1. Эксперту предъявляется множество имен событий и предлагается указать в этом множестве пару имен таких событий, которые, на его взгляд, связаны между собой.
2. Если эксперт отказывается указать такую пару, то сценарий заканчивает; если указывает, например, A и B, то эта пара имен событий подставляется в канонические формы высказываний вначале всюду вместо X – A и вместо Y – B (первая часть списка), затем, всюду вместо X – B, вместо Y – A (вторая часть списка), формируя тем самым некоторый список (в указанном порядке).
3. Полученные в результате высказывания предъявляются эксперту в виде указанного списка с предложением выбрать из них высказывание, наиболее соответствующее связи между A и B.
4. Если эксперт отказывается указать какую-либо из них, стратегия заканчивает работу; если указывает какое-либо из высказываний, то формируется признак F, если высказывание указано в первой половине списка, и признак S, если во второй;
5. Для указанного в п.4. высказывания Li (пусть, для определенности, "A<предикатор>B" ), эксперту предлагается уточнить, появляются ли оба события A и B этого высказывания одновременно или в разные моменты времени;
6. Если ответ– одновременно, то формируется признак J, иначе, формируется признак D.
7. Запускается работа Критерия подстановки применительно к указанному экспертом высказыванию "A<предикатор>B".
8. Если сформирован признак J и один из признаков Rf или Arf, то применительно к высказыванию "A<предикатор>B" запускается Критерий перестановки;
9. Если сформирован признак J и не сформирован признак Sm, то применительно к высказыванию "A<предикатор>B" запускается Критерий обращения;
10. Если сформирован признак J, не сформирован признак Sm и сформирован признак Rf или Arf, то применительно к высказыванию "A<предикатор>B" запускается Критерий трансформации;
11. Если сформирован признак D и признак Nrf, то применительно к высказыванию "A<предикатор>B" запускается Критерий трансформации;
12. Если сформированы признаки F,J,Arf и не сформирован признак Sm, то Li относится к типу связи Gen(A,B); Q10 :=Q10 Li ; выполняется процедура 2(Q10);
13. Если сформированы признаки F,J,Arf,As,Tr то Li относится к типу связи Sit(A,B);Q6 := 0(Q6,Li);выполняется процедура 4(2(Q6));
14. Если сформированы признаки F,J,Arf,Sm то Li относится к типу связи Neg(A,B); Q4 :=Q4 Li; выполняется процедура 3(2(Q4));
15. Если сформированы признаки F,J,Nrf и не сформирован признак Sm, то тип связи Ins(A,B); Q5:=Q5 Li; выполняется процедура [Q5];
16. Если сформированы признаки F,J,Rf,Tr и не сформирован признак Sm,то тип связи Com(A,B);Q1 := 0(Q1,Li);выполняется процедура 4(1(Q1));
17. Если сформированы признаки F,J,Rf,Ntr и не сформирован признак Sm, то тип связи Mcom(A,B); Q2:=Q2Li; выполняется процедура 1(Q2));
18. Если сформированы признаки F,J,Rf,Sm, то тип связи Cor(A,B);Q3 :=Q3 Li ; выполняется процедура 3(1(Q3));
19.Если сформированы признаки F,D,Ntr,Arf, то тип связи Fin(A,B);Q9 :=Q9 Li ; выполняется процедура 2(Q9));
20.Если сформированы признаки F,D,Tr,Nrf, то тип связи Cous(A,B);Q7 :=Q7 Li; выполняется процедура 4(Q7));
21.Если сформированы признаки F,D,Ntr,Nrf, то тип связи Pot(A,B);Q8 :=Q8 Li; выполняется процедура [Q8].
Приведем следующие утверждения.
Теорема 1. (О корректности стратегии). Если высказыванию Li "A<предикатор>B" (где A и B – имена конкретных событий) стратегией приписан некоторый тип семантической связи, то этот тип – единственный.
Теорема 2. Каждое высказывание, отнесенное стратегией к некоторому типу, однозначным образом преобразуется в элемент некоторого бинарного отношения на множестве событий, обладающего следующими свойствами:
а) нетранзитивное, антирефлексивное, несимметричное – 2(Q10);
б) транзитивное, антирефлексивное, несимметричное – 4(2(Q6));
в) нетранзитивное, антирефлексивное, симметричное – 3(2(Q4));
г) нетранзитивное, нерефлексивное и несимметричное – [Q5];
д) транзитивное, рефлексивное и антисимметричное – 4(1(Q1));
е) нетранзитивное, нерефлексивное, и несимметричное – 1(Q2);
ж) нетранзитивное, рефлексивное, симметричное – 3(1(Q3));
з) нетранзитивное, антирефлексимное, несимметричное – 2(Q9));
и) транзитивное, нерефлексивное, несимметричное – 4(Q7));
к) нетранзитивное, нерефлексивное, несимметричное – [Q8].
Таким образом, стратегия выявления сходства каждое высказывание превращает в элемент некоторого отношения, которое задается своими свойствами. Причем это отнесение выполняется в полном соответствии с такими неформальными свойствами высказываний, как Ntr, Rf, Ns, Sm, Arf и другими, которые выявляются в процессе работы стратегии выявления сходства.
2.2. Извлечение знаний
Извлечение знаний – это процедура взаимодействия эксперта с источником знаний, в результате которой становятся явными процесс рассуждений специалистов при принятии решения и структура их представлений о предметной области [8].
В настоящее время большинство разработчиков экспертных систем отмечают, что процесс извлечения знаний остается самым "узким" местом при построении промышленных систем. Для того, чтобы ответить на вопросы, в чем заключаются трудности извлечения экспертных знаний и каким образом их разрешать, специалисты в области инженерии знаний обращаются к психологическим и психолингвистическим исследованиям, касающимся таких проблем, как проведение экспертизы опытными специалистами и понимание природы экспертизы, применение теоретических знаний на практике и специфика практического мышления, характеристика системы обработки информации человеком и поведение человека, решающего профессиональные задачи, а также взаимосвязь естественного языка и мыслительного процесса человека. Исследование этих проблем, а также практическая работа по извлечению знаний, позволяет отметить ряд эффектов или явлений, наблюдаемых при работе с экспертами и оказывающий существенное влияние на процесс извлечения знаний:
– существование так называемых молчаливых или подразумеваемых знаний (tacit knowledge), обусловленное тремя причинами: неосознаваемым характером экспертного умения, трудностью процесса вербализации и недооценкой экспертом важности некоторых знаний, используемых при решении профессиональных задач;
– особая форма организации знаний экспертов по сравнению с организацией знаний новичков;
– достаточно высокая скорость решения экспертом профессиональных задач;
– ограниченность объема кратковременной памяти человека;
– некорректность некоторых способов получения информации (присвоение весов признаков, присвоение вероятностей и т.д.);
– существование механизма когнитивной защиты;
– наличие психолингвистических проблем, в частности, различие между коммуникативным языком и языком мыслительного процесса приводит в процессе общения инженера по знаниям с экспертом к значительной потере информации.
Для преодоления описанных выше проблем в рамках инженерии знаний (как в теоретическом плане, так и в результате практических разработок конкретных систем) создаются так называемые методы извлечения знаний или техники (knowledge elicitation techniques), представляющие собой некоторую процедуру или форму взаимодействия инженера по знаниям с экспертом.
2.2.1. Практические методы извлечения знаний
В классификации методов извлечения знаний (рис. 6) основной принцип деления связан с источником знаний [17]. Коммуникативные методы охватывают все виды контактов с живым источником знаний – экспертом, а текстологические касаются методов извлечения знаний из документов (методик, пособий, руководств) и специальной литературы (статей, монографий, учебников).
Рис.6. Классификация методов извлечения знаний
Разделение этих групп методов на верхнем уровне классификации не означает их антагонистичности, обычно инженер по знаниям комбинирует различные методы, например, сначала изучает литературу, затем беседует с экспертами, или наоборот.
В свою очередь, коммуникативные методы можно также разделить на две группы: активные и пассивные. Пассивные методы подразумевают, что ведущая роль в процедуре извлечения знаний как бы передается эксперту, а инженер по знаниям только протоколирует рассуждения эксперта во время его реальной работы по принятию решений или записывает то, что эксперт считает нужным самостоятельно рассказать в форме лекции. В активных методах, напротив, инициатива полностью в руках инженера по знаниям, который активно контактирует с экспертом различными способами – в играх, диалогах, беседах за "круглым столом" и т.д.
Активные методы можно разделить на две группы в зависимости от числа экспертов, отдающих свои знания. Если их число больше одного, то целесообразно помимо серии индивидуальных контактов с каждым применять и методы групповых обсуждений предметной области.
Название "пассивные" не должно вызывать иллюзий, поскольку этот термин введен как противовес к "активным" методам. В реальности же пассивные методы требуют от инженера по знаниям не меньшей отдачи, чем такие активные методы, как игры и диалог. Отсутствие обратной связи (пассивность инженера по знаниям) значительно ослабляет эффективность этих методов, чем и объясняется их обычно вспомогательная роль при активных методах.
В процессе наблюдений инженер по знаниям находится непосредственно рядом с экспертом во время его профессиональной деятельности или имитации этой деятельности; При подготовке к сеансу извлечения эксперту необходимо объяснить цель наблюдений и попросить максимально комментировать свои действия.
Во время сеанса аналитик записывает все действия эксперта, его реплики и объяснения. Может быть сделана и видеозапись в реальном масштабе времени. Непременное условие этого метода – невмешательство аналитика в работу эксперта хотя бы на первых порах.
Существуют две разновидности проведения наблюдений:
– наблюдение за реальным процессом;
– наблюдение за имитацией процесса.
Обычно используют обе разновидности.
Сеансы наблюдений могут потребовать от инженера по знаниям:
– овладения техникой стенографии для фиксации действий эксперта в реальном масштабе времени;
– ознакомления с методиками хронометрирования для четкого структурирования производственного процесса по времени,
– развития навыков "чтения по глазам", наблюдательности к жестам, мимике и другим невербальным компонентам общения;
– серьезного предварительного знакомства с предметной областью, так как из-за отсутствия "обратной связи" иногда многое непонятно в действиях экспертов. Протоколы наблюдений после сеансов в ходе домашней работы тщательно расшифровываются, а затем обсуждаются с экспертом. Таким образом, наблюдения – один из наиболее распространенных методов извлечения знаний на начальных этапах разработки. Обычно он применяется не самостоятельно, а в совокупности с другими методами.
Протоколирование "мыслей вслух" отличается от наблюдений тем, что эксперта просят не просто прокомментировать свои действия и решения, но и объяснить, как это решение было найдено, т.е. продемонстрировать всю цепочку своих рассуждений. Во время рассуждения эксперта все его слова протоколируются инженером по знаниям.
Основной трудностью при протоколировании "мыслей вслух" является принципиальная сложность для любого человека объяснить, как он думает. При этом существуют экспериментальные психологические доказательства, что люди не всегда в состоянии достоверно описать мыслительные процессы. Кроме того, часть знаний, хранящихся в невербальной форме (например, различные процедурные знания типа "как завязывать шнурки"), вообще слабо коррелируют с их словесным описанием.
Расшифровка полученных протоколов производится инженером по знаниям самостоятельно с коррекциями на следующих сеансах извлечения знаний. Удачно проведенное протоколирование "мыслей вслух" является одним из наиболее эффективных методов извлечения, поскольку в нем эксперт ничем не скован и может проявить себя максимально ярко.
Лекция – самый старый способ передачи знаний. В лекции эксперту предоставлено много степеней свободы для самовыражения; при этом необходимо сформулировать эксперту тему и задачу лекции. При такой постановке опытный лектор может заранее структурировать свои знания, ход рассуждении. От инженера по знаниям в этой ситуации требуется лишь грамотно законспектировать лекцию и в конце задать необходимые вопросы.
Продолжительность лекции стандартная – от 40 до 50 мин и через 5-10 мин – еще столько же. Курс – от двух до пяти лекций.
Метод извлечения знаний в форме лекций, как и все пассивные методы, используют в начале разработки как эффективный способ быстрого погружения инженера по знаниям в предметную область.
Активные индивидуальные методы
Анкетирование – наиболее жесткий метод, т.е. наиболее стандартизованный. Инженер по знаниям заранее составляет вопросник или анкету, размножает ее и использует для опроса нескольких экспертов. Это основное преимущество анкетирования.
Сама процедура может проводиться двумя способами:
– аналитик вслух задает вопросы, и сам заполняет анкету по ответам эксперта;
– эксперт самостоятельно заполняет анкету после предварительного инструктирования.
Выбор способа зависит от конкретных условий. Второй способ нам кажется предпочтительнее, так как у эксперта появляется неограниченное время на обдумывание ответов.
Вопросник (анкета) заслуживает отдельного разговора. Существует несколько общих рекомендаций при составлении анкет. Эти рекомендации универсальны, т.е. не зависят от предметной области. Наибольший опыт работы с анкетами накоплен в социологии и психологии.
Под интервью понимаем специфическую форму общения инженера по знаниям и эксперта, в которой инженер по знаниям задает эксперту серию заранее подготовленных вопросов с целью извлечения знаний о предметной области. Наибольший опыт в проведении интервью накоплен также в журналистике и социологии.
Интервью очень близко к анкетированию, когда аналитик сам заполняет анкету, занося туда ответы эксперта. Основное отличие в том, что интервью позволяет аналитику опускать ряд вопросов в зависимости от ситуации, вставлять новые вопросы в анкету, изменять темп, разнообразить ситуацию общения. Кроме того, у аналитика появляется возможность "взять в плен" эксперта своим обаянием, заинтересовать его самой процедурой и тем самым увеличить эффективность сеанса извлечения.
Теперь подробнее о центральном звене активных индивидуальных методов – о вопросах. Инженеры по знаниям редко задумываются: умеют ли они задавать вопросы? В философии и математике эта проблема обсуждается с давних пор. Существует даже специальная ветвь математической логики – логика вопросов.
Укажем три основные характеристики вопросов [17, 31], которые влияют на качество интервью:
– стиль вопроса (понятность, лаконичность, терминология);
– порядок вопросов (логическая последовательность и немонотонность);
– уместность вопросов (этика, вежливость).
Вопрос в интервью – это не просто средство общения, но и способ передачи мыслей и позиции аналитика. Отсюда необходимость фиксировать в протоколах не только ответы, но и вопросы, предварительно отработав их форму и содержание.
Свободный диалог – это метод извлечения знаний в форме беседы инженера по знаниям и эксперта, в которой нет жестко регламентированного плана и вопросника. Это определение не означает, что к свободному диалогу не надо готовиться. Напротив, внешне свободная и легкая форма этого метода требует высочайшей профессиональной и психологической подготовки.
В свободном диалоге важно выбрать правильный темп или ритм беседы: без больших пауз, так как эксперт может отвлечься, но и "без гонки", иначе быстро утомляются оба участника и нарастает напряженность; кроме того, некоторые люди говорят и думают очень медленно. Умение чередовать разные темпы; напряжение и разрядку существенно влияет на результат беседы.
Подготовка к диалогу так же, как и к другим активным методам извлечения знаний, включает план сеанса извлечения, в котором необходимо предусмотреть следующие стадии:
– начало беседы (знакомство, создание у эксперта "образа" аналитика, объяснение целей и задач работы);
– диалог по извлечению знаний;
– заключительная стадия (благодарность эксперту, подведение итогов, договор о последующих встречах).
Игрой называют такой вид деятельности, который отражает (воссоздает) другие ее виды. Понятие экспертной игры, или игры с экспертами, в целях извлечения знаний восходит к трем источникам – это понятие деловой игры, широко используемое при подготовке специалистов и моделировании, и понятие диагностической игры, а также компьютерные игры, все чаще применяемые в обучении.
Под деловой игрой чаще всего понимают эксперимент, где участникам предлагается производственная ситуация, а они на основе своего жизненного опыта, общих и специальных знаний и представлений принимают решения. Решения анализируются, и вскрываются закономерности мышления участников эксперимента. Именно эта анализирующая часть деловой игры полезна для получения знаний. И если участниками такой игры становятся эксперты, то игра из деловой превращается в экспертную. Из трех основных типов деловых игр (учебных, планово-производственных и исследовательских) к экспертным ближе всего исследовательские, которые используются для анализа систем, проверки правил принятия решений.
Диагностическая игра – это та же деловая игра, но применяемая конкретно для диагностики методов принятия решения в медицине (диагностика методов диагностики). Эти игры возникли при исследовании способов передачи опыта от квалифицированных врачей новичкам. В нашем понимании диагностическая игра – это игра, безусловно, экспертная без всяких оговорок, только с жестко закрепленной предметной областью – медициной.
Основное достоинство групповых методов – это возможность одновременного поглощения знаний от нескольких экспертов, взаимодействие которых вносит элемент принципиальной новизны от наложения разных взглядов и позиций.
Метод круглого стола (термин заимствован из журналистики) предусматривает обсуждение какой-либо проблемы из выбранной предметной области, в котором принимают участие с равными правами несколько экспертов. Обычно вначале участники высказываются в определенном порядке, а затем переходят к живой свободной дискуссии. Число участников дискуссии колеблется от трех до пяти-семи. Существует и специфика, связанная с поведением человека в группе.
Во-первых, от инженера по знаниям подготовка круглого стола потребует дополнительных усилий, как организационных (место, время, обстановка, минеральная вода, чай, кворум и т.д.), так и психологических (умение вставлять уместные реплики, чувство юмора, память на имена и отчества, способность гасить конфликтные ситуации и т.д.).
Во-вторых, большинство участников будут говорить под воздействием "эффекта фасада" совсем не то, что они сказали бы в другой обстановке, т.е. желание произвести впечатление на других экспертов будет существенно "подсвечивать" их высказывания.
Задача дискуссии – коллективно, с разных точек зрения, под разными углами исследовать спорные гипотезы предметной области. Обычно эмпирические области богаты таким дискуссионным материалом. Для остроты на круглый стол приглашают представителей разных научных направлений и разных поколений, это также уменьшает опасность получения односторонних знаний.
Мозговой штурм или мозговая атака – один из наиболее распространенных методов раскрепощения и активизации творческого мышления. Впервые этот метод был использован в США как способ получения новых идей в условиях запрещения критики. Замечено, что боязнь критики мешает творческому мышлению, поэтому основная идея штурма – это отделение процедуры генерирования идей в замкнутой группе специалистов от процесса анализа и оценки высказанных идей.
Как правило, штурм длится около 40 мин. Участникам (до 10 человек) предлагается высказывать любые идеи (шутливые, фантастические, ошибочные) на заданную тему (критика запрещена). Обычно высказывается более 50 идей. Регламент до двух минут на выступление. Самый интересный момент штурма – это наступление пика (ажиотажа), когда идеи начинают "фонтанировать", т.е. происходит непроизвольная (бессознательная) генерация гипотез участниками. При последующем анализе всего лишь 10 – 15% идей оказываются разумными, но среди них бывают весьма оригинальные. Оценивает результаты обычно группа экспертов, не участвовавшая в генерации.
Ведущий мозгового штурма – инженер по знаниям – должен свободно владеть аудиторией, подобрать активную группу экспертов – "генераторов", не зажимать плохие идеи – они могут служить катализатором хороших. Искусство ведущего – это искусство задавать вопросы аудитории, "подогревая" генерацию. Основной девиз штурма – "чем больше идей, тем лучше". Фиксация сеанса – традиционная (протокол или магнитофон).
Групповые игры предусматривают участие в игре нескольких экспертов. К такой игре обычно заранее составляется сценарий, распределяются роли, к каждой роли готовится портрет-описание и разрабатывается система оценивания игроков.
Существует несколько способов проведения ролевых игр. В одних играх игроки придумывают себе новые имена и играют под ними; в других – игроки переходят на "ты"; в третьих роли выбирают игроки, в четвертых роли вытягивают по жребию. Роль – это комплекс образцов поведения. Роль связана с другими ролями. Поскольку в нашем случае режиссером и сценаристом является инженер по знаниям, то ему и предоставляется полная свобода в выборе формы проведения игры.
Группа текстологических методов объединяет методы извлечения знаний, основанные на изучении специальных текстов из учебников, монографий, статей, методик и других носителей профессиональных знаний.
Задачу извлечения знаний из текстов можно сформулировать как задачу понимания и выделения смысла текста. Сам текст на естественном языке является лишь проводником смысла, а замысел и знания автора лежат во вторичной структуре (смысловой структуре или макроструктуре текста), настраиваемой над естественным текстом [17].
При этом можно выделить две такие смысловые структуры: M1 – смысл, который пытался заложить автор, это его модель мира, и М2 – смысл, который постигает читатель, в данном случае инженер по знаниям (рис. 7) в процессе интерпретации I. При этом Т – это словесное одеяние М1, т.е. результат вербализации V.
Сложность процесса заключается в принципиальной невозможности совпадения знаний, образующих М1 и M2, из-за того, что М1 образуется за счет совокупности представлений, потребностей, интересов и опыта автора, лишь малая часть которых находит отражение в тексте Т. Соответственно и М2 образуется в процессе интерпретации текста Т за счет привлечения всей совокупности научного и человеческого багажа читателя.
Встает задача выяснить, за счет чего можно достичь максимальной адекватности М1 и М2, помня о том, что понимание всегда относительно. Рассмотрим подробнее, какие источники питают модель М1 и создают текст Т. Это первичный материал наблюдений и система научных понятий в момент создания текста. В дополнение к этому, помимо объективных данных экспериментов и наблюдений, в тексте обязательно присутствуют субъективные взгляды автора, результат его личного опыта, а также некоторые "общие места", или "вода". Кроме того, любой научный текст содержит заимствования из других источников (статей, монографий) и.т.д.
Рис. 7. Извлечение знаний из текстов
При извлечении знаний аналитику, интерпретирующему текст, приходится решать задачу декомпозиции этого текста на перечисленные выше компоненты для выделения истинно значимых для реализации базы знаний фрагментов. Сложность интерпретации научных и специальных текстов заключается еще и в том, что любой текст приобретает смысл только в контексте, где под контекстом понимается окружение, в которое "погружен" текст.
Основными моментами понимания текста являются [17]:
– выдвижение предварительной гипотезы о смысле всего текста (предугадывание);
– определение значения непонятных слов (т.е. специальной терминологии);
– возникновение общей гипотезы о содержании текста (о знаниях);
– уточнение значения терминов и интерпретация отдельных фрагментов текста под влиянием общей гипотезы (от целого к частям);
– формирование некоторой смысловой структуры текста за счет установления внутренних связей между отдельными важными (ключевыми) словами и фрагментами, а также за счет образования абстрактных понятий, обобщающих конкретные фрагменты знаний;
– корректировка общей гипотезы относительно содержащихся в тексте фрагментов знаний (от частей к целому);
– принятие основной гипотезы, т.е. формирование М2.
Следует отметить наличие как дедуктивной (от целого к частям), так и индуктивной (от частей к целому) составляющей процесса понимания.
Центральными моментами процесса I являются шаги формирования смысловой структуры или выделения "опорных", или ключевых, слов, а также заключительное охватывание "смысловых вех" в единую семантическую структуру. В качестве ключевого слова может служить любая часть речи (существительное, прилагательное, глагол и т.д.) или их сочетание. Существует гипотеза лингвостатистики о том, что наиболее употребляемые слова являются наиболее важными с точки зрения содержания текста, т.е. отражают его тематическую структуру.
Подготовкой к прочтению специальных текстов является выбор совместно с экспертами некоторого "базового" списка литературы, который постепенно введет аналитика в предметную область. В этом списке могут быть учебники для начинающих, главы и фрагменты из монографий, популярные издания. Только после ознакомления с "базовым" списком целесообразно приступать к чтению специальных текстов.
Наиболее простым методом является анализ учебников, в которых логика изложения обычно соответствует логике предмета, и поэтому макроструктура такого текста будет, наверное, более значима, чем структура текста какой-нибудь специальной статьи. Анализ методик затруднен как раз сжатостью изложения и практическим отсутствием комментариев, т.е. фоновых знаний, облегчающих понимание для неспециалистов. Поэтому можно рекомендовать для практической работы комбинацию перечисленных методов.
2.2.2. Структурирование знаний
Одна из наиболее творческих процедур при построении экспертных систем – процедура концептуального анализа полученных знаний, или структурирование.
Под концептуальным анализом знаний понимается процесс анализа информации, полученной от источника знаний, и синтез ее (или кодирование) в некоторые структуры, независящие от какой-либо программной реализации.
Извлечение и структурирование знаний – это единый процесс взаимодействия инженера по знаниям с экспертом, различающийся лишь своими аспектами. Если проблема извлечения знаний заключается в выборе формы взаимодействия инженера по знаниям с экспертом, то проблема концептуального анализа знаний предполагает рассмотрение собственно предмета, ради которого такое взаимодействие организовано, а именно той информации, смысл которой в процессе преобразования от представлений эксперта к представлению в компьютере должен остаться неизменным.
В процессе структурирования создается полуформализованное описание предметной области, называемое полем знаний. Обычно оно изображается в графической форме.
Поле знаний Рz можно описать следующим образом:
Pz=<Sk,Sf>,
где Sk – концептуальная структура предметной области;
Sf – функциональная структура предметной области,
Концептуальная структура, или модель предметной области, служит для описания ее объектов и отношений между ними, т.е. можно сказать, что концептуальная модель Sk представляет собой следующее:
Sk = <A, R>,
где А – множество объектов предметной области;
R – множество отношений, связывающих объекты.
Множество отношений представляет собой связи между объектами. При помощи этих отношений инженер по знаниям фиксирует концептуальное устройство предметной области, иерархию понятий, свойства и структуру объектов. Разработка концептуальной структуры имеет самостоятельное значение, не зависимое от конечной цели – разработки экспертных систем. Эта структура может служить для целей обучения, повышения квалификации, для прогнозирования, объяснения, реструктурирования и т.п.
Основными из них являются АКО, A-part-of, Has-attribute, Value и др.
– АКО (A-Kind-OF) – "это есть", например, [Macll] (АКО) [ПК]. АКО отражает родовидовые отношения и иерархию понятий предметной области. Обязательно присутствует в любой концептуальной структуре.
– A-part-of – "часть от", например, [процессор] (A-part-of) [компьютер]. Это отношение служит для отражения физической структуры и декомпозиции сложных объектов на составляющие.
– Has-attribute – "имеет свойство", например, [память] (Has-attribute) [объем памяти].
– Value – "значение", например, [объем памяти] (Value) [16 Мбайт].
Поле знаний может напоминать семантическую сеть, но оно менее формализовано. Если в сети жестко оговорены возможные виды связей, то в поле знаний они произвольны.
Краткий алгоритм формирования концептуальной структуры.
Шаг 1. Определить все результирующие понятия, или выходы системы. Это может быть набор диагнозов, рекомендаций, советов системы.
Шаг 2. Определить все входные понятия, или факторы, от которых зависит результат работы системы.
Шаг 3. Установить промежуточные понятия, участвующие в рассуждениях экспертов, если они есть.
Шаг 4. Для всех понятий найти обобщающие и уточняющие понятия, т.е. установить иерархии объектов
Шаг 5. Для объектов, участвующих в рассуждениях, определить свойства и их значения.
Шаг 6. Попытаться определить другие связи, и все в целом отразить графически.
Шаг 7. Убрать лишние связи, объекты, обсудить структуру с экспертом, дополнить, если надо, с возвратом к шагам 1 – 6.
Функциональная структура предметной области отражает модель рассуждений и принятия решений, которой пользуется эксперт при решении задачи. Обычно функциональная структура представляется в виде каузальных отношений (cause) и может быть позднее формализована в виде коротких правил "если – то", или в виде семантических сетей. Представить функциональную структуру можно в виде таблицы, графа или предложений на естественном языке. Наглядные формы предпочтительны.
Часто в моделях рассуждении присутствуют нечеткие понятия – "часто", "много", "очень", "высокий", "большой" и др. Для их представления базе знаний используется так называемая нечеткая логика, автор которой – Л.Заде, предложил простой формализм для таких понятий. Этот формализм использует понятие нечеткой функции принадлежности, которая отражает численно на шкале [0,10] или [0,1] степень уверенности эксперта в том, что конкретное значение можно отнести к данному нечеткому понятию (см. гл.3).
Также степени уверенности используются при множественных рекомендациях. Например, эксперт советует "покупать акции компании Х со степенью уверенности 9, а компании Y со степенью уверенности 6".
Процесс преобразования знаний от представлений эксперта к представлению в компьютере можно рассматривать как проблему преобразования информации, осуществляемой путем перехода от одного материального носителя знаний к другому. В зависимости от вида материального носителя знаний можно выделить следующие уровни представлений знаний:
– представление знаний в памяти человека (эксперта);
– концептуальное или полуформализованное представление знаний как результат взаимодействия эксперта и инженера по знаниям (возможно на бумаге);
– формализованное представление знаний на специализированных языках искусственного интеллекта (на бумаге или в компьютере);
– представление знаний на машинных носителях информации (база знаний).
В этом отношении концептуальный анализ знаний – это переход от представления знаний в памяти эксперта к некоторым концептуальным, полуформализованным представлениям или структурам, отражающим понимание экспертом предметной области в целом и стратегий рассуждений при решении профессиональных задач.
2.3. Формирование знаний
Специфика современных требований к обработке данных с целью обнаружения знаний следующая:
– данные имеют неограниченный объем;
– данные являются разнородными (количественными, качественными, категориальными);
– данные должны быть конкретны и понятны;
– инструменты для обработки “сырых” данных должны быть просты в использовании.
Knowledge Discovery in Databases (KDD) – (обнаружение знаний в базах данных) включает в себя вопросы подготовки данных, выбора информативных признаков, очистки данных, применения методов интеллектуального анализа данных (Data Mining – раскопки данных), постобработки данных, интерпретации полученных результатов. Безусловно, сердцем всего этого процесса являются методы Data Mining, позволяющие обнаруживать знания. Этими знаниями могут быть правила, описывающие связи между свойствами данных (деревья решений), часто встречающиеся шаблоны (ассоциативные правила), а также результаты классификации (нейронные сети) и кластеризации данных (карты Кохонена) и т.д.
Процесс KDD, состоит из следующих шагов (рис. 8):
1. Подготовка исходного набора данных. Этот этап заключается в создании набора данных, в том числе из различных источников, выбора обучающей выборки и т.д. Для этого должны существовать развитые инструменты доступа к различным источникам данных.
2. Предобработка данных. Для того, чтобы эффективно применять методы ИАД, следует обратить серьезное внимание на вопросы предобработки данных. Данные могут содержать пропуски, шумы, аномальные значения и т.д. Кроме того, данные могут быть избыточны, недостаточны и т.д. В некоторых задачах требуется дополнить данные некоторой априорной информацией. Наивно предполагать, что если подать данные на вход системы в существующем виде, то на выходе получим полезные знания. Данные должны быть качественны и корректны с точки зрения используемого метода ИАД. Поэтому первый этап KDD заключается в предобработке данных. Более того, иногда размерность исходного пространства может быть очень большой, и тогда желательно применение специальных алгоритмов понижения размерности. Это как отбор значимых признаков, так и отображение данных в пространство меньшей размерности.
Рис. 8. Иллюстрация процесса KDD.
3. Трансформация, нормализация данных. Этот шаг необходим для тех методов, которые требуют, чтобы исходные данные были в каком-то определенном виде. Нейронные сети, скажем, работают только с числовыми данными, причем они должны быть нормализованы.
4. Интеллектуальный анализ данных (Data Mining). На этом шаге применяются различные алгоритмы для нахождения знаний. Это нейронные сети, деревья решений, алгоритмы кластеризации и установления ассоциаций и т.д.
5. Постобработка данных. Интерпретация результатов и применение полученных знаний в бизнес приложениях.
2.3.1. Задачи и стадии интеллектуального анализа данных
Выделяют пять стандартных типов закономерностей (задач), которые позволяют выявлять методы ИАД: ассоциация, последовательность, классификация, кластеризация и прогнозирование.
Классификация. Наиболее распространенная задача (ИАД). Она позволяет выявить признаки, характеризующие однотипные группы объектов – классы, – для того чтобы по известным значениям этих характеристик можно было отнести новый объект к тому или иному классу. Ключевым моментом выполнения этой задачи является анализ множества классифицированных объектов. Наиболее типичный пример использования классификации – конкурентная борьба между поставщиками товаров и услуг за определенные группы клиентов. Классификация способна помочь определить характеристики неустойчивых клиентов, склонных перейти к другому поставщику, что позволяет найти оптимальную стратегию их удержания от этого шага (например, посредством предоставления скидок, льгот или даже с помощью индивидуальной работы с представителями "групп риска"). В качестве методов решения задачи классификации могут использоваться алгоритмы типа Lazy-Learning, в том числе известные алгоритмы ближайшего соседа (Nearest Neighbor) и k-ближайшего соседа (k-Nearest Neighbor), байесовские сети (Bayesian Networks) , индукция деревьев решений, индукция символьных правил, нейронные сети.
Кластеризация. Логически продолжает идею классификации на более сложный случай, когда сами классы не предопределены. Результатом использования метода, выполняющего кластеризацию, как раз является определение (посредством свободного поиска) присущего исследуемым данным разбиения на группы. Так, можно выделить родственные группы клиентов или покупателей с тем, чтобы вести в их отношении дифференцированную политику. В приведенном выше примере "группы риска" – категории клиентов, готовых уйти к другому поставщику – средствами кластеризации могут быть определены до начала процесса ухода, что позволит производить профилактику проблемы, а не экстренное исправление положения. В большинстве случаев кластеризация очень субъективна; будучи основанным на измерении "информационного расстояния" между примерами обучающего множества (подобно использованному в методе k-ближайшего соседа), любой вариант разбиения на кластеры напрямую зависит от выбранной меры этого расстояния. В качестве примера используемых методов можно привести обучение "без учителя" особого вида нейронных сетей – сетей Кохонена, а также индукцию правил.
Выявление ассоциаций. В отличие от двух предыдущих типов, ассоциация определяется не на основе значений свойств одного объекта или события, а имеет место между двумя или несколькими одновременно наступающими событиями. При этом производимые правила указывают на то, что при наступлении одного события с той или иной степенью вероятности наступает другое. Количественно сила ассоциации определяется несколькими величинами, например, следующими характеристиками:
а) предсказуемость (predictability) определяет, как часто события X и Y случаются вместе, в виде доли от общего количества событий X; например, в случае покупки телевизора (X) одновременно покупается видеомагнитофон в 65% случаев (Y);
б) распространенность (prevalence) показывает, как часто происходит одновременное наступление событий X и Y относительно общего числа моментов зафиксированных событий; иными словами, насколько часто производится одновременная покупка телевизора и видеомагнитофона среди всех сделанных покупок;
в) ожидаемая предсказуемость (expected predictability) показывает ту предсказуемость, которая сложилась бы при отсутствии взаимосвязи между событиями; например, как часто покупался бы видеомагнитофон безотносительно к тому, покупался ли телевизор. Рассмотренный пример является типичной иллюстрацией задачи анализа покупательской корзины (basket analysis). Цель его выполнения – определение пар товаров, при совместной покупке которых покупателю может быть предоставлена скидка ради увеличения значения предсказуемости и, следовательно, повышения объема продаж.
Выявление последовательностей. Подобно ассоциациям, последовательности имеют место между событиями, но наступающими не одновременно, а с некоторым определенным разрывом во времени. Таким образом, ассоциация есть частный случай последовательности с нулевым временным лагом. Так, если видеомагнитофон не был куплен вместе с телевизором, то в течение месяца после покупки нового телевизора покупка видеомагнитофона производится в 51% случаев.
Прогнозирование. Это особая форма предсказания, которая на основе особенностей поведения текущих и исторических данных оценивает будущие значения определенных численных показателей. Например, может быть сделан прогноз объема продукции, который ожидается в предприятиях текстильной отрасли Волгоградской области в ближайшие месяцы, на основе данных. Использование выявленных закономерностей для предсказания неизвестных значений (прогностическое моделирование). В задачах подобного типа наиболее часто используются традиционные методы математической статистики, а также нейронные сети.
Классификация стадий ИАД
Процесс ИАД может быть представлен следующими стадиями и выполняемыми в их рамках действиями (рис. 9) . В этом контексте некоторые задачи ИАД оказываются разбитыми на два или три последовательных этапа, соответствующих стадиям ИАД.
Рис. 9. Стадии ИАД.
Свободный поиск (Discovery).
Свободный поиск определяется как процесс исследования исходной БД на предмет поиска скрытых закономерностей без предварительного определения гипотез относительно вида этих закономерностей. Другими словами, сама программа берет на себя инициативу в деле поиска интересных аномалий, или шаблонов, в данных, освобождая аналитика от необходимости обдумывания и задания соответствующих запросов. Этот подход особенно ценен при исследовании больших баз данных, имеющих значительное количество скрытых закономерностей, большинство из которых было бы упущено при непосредственном поиске путем прямых запросов пользователя к исходным данным.
В качестве примера свободного поиска по инициативе системы рассмотрим исследование реестра физических лиц. Если инициатива принадлежит пользователю, он может построить запрос типа "Каков средний возраст директоров предприятий отрасли промышленности строительных материалов, расположенных в Волгограде и находящихся в собственности субъекта Федерации?" и получить ответ – 48. В системе, обеспечивающей стадию свободного поиска, пользователь может поступить иначе и запросить у системы найти что-нибудь интересное относительно того, что влияет на атрибут Возраст. Система начнет действовать так же, как и аналитик-человек, т. е. искать аномалии в распределении значений атрибутов, в результате чего будет произведен список логических правил типа "ЕСЛИ ..., ТО ...", в том числе, например:
ЕСЛИ Профессия="Программист", ТО Возраст<=30 в 61% случаев;
ЕСЛИ Профессия="Программист", ТО Возраст<=60 в 98% случаев.
Аналогично, при исследовании реестра юридических лиц аналитика может заинтересовать атрибут Форма_собственности. В результате свободного поиска могут быть получены правила:
ЕСЛИ Основной_вид_деятельности="Общеобразовательные детские школы",
ТО Форма_собственности="Муниципальная собственность" в 84% случаев;
ЕСЛИ Вид_деятельности="Наука и научное обслуживание",
ТО Форма_собственности="Частная собственность" в 73% случаев.
Стадия свободного поиска может выполняться посредством:
– индукции правил условной логики (как в приведенных примерах) – с их помощью, в частности, могут быть компактно описаны группы похожих обучающих примеров в задачах классификации и кластеризации;
– индукции правил ассоциативной логики – то есть того, что было определено в рамках классификации задач ИАД по типам извлекаемой информации как выявление ассоциаций и последовательностей;
– определения трендов и колебаний в динамических процессах, то есть исходного этапа задачи прогнозирования.
Стадия свободного поиска, как правило, должна включать в себя не только генерацию закономерностей, но и проверку их достоверности на множестве данных, не принимавшихся в расчет при их формулировании. Прием разделения исходных данных на обучающее множество (training set) и проверочное множество (test set) хорошо описан в методах обучения нейронных сетей.
Прогностическое моделирование (Predictive Modeling)
Здесь, на второй стадии ИАД, используются плоды работы первой, то есть найденные в БД закономерности применяются для предсказания неизвестных значений:
– при классификации нового объекта мы можем с известной уверенностью отнести его к определенной группе результатов рассмотрения известных значений его атрибутов;
– при прогнозировании динамического процесса результаты определения тренда и периодических колебаний могут быть использованы для вынесения предположений о вероятном развитии некоторого динамического процесса в будущем.
Возвращаясь к рассмотренным примерам, применим их к данной стадии. Зная, что некто Иванов – программист, можно быть на 61% уверенным, что его возраст <=30 годам, и на 98% – что он <=60 годам. Аналогично, можно сделать заключение о 84% вероятности того, что некоторое новое юридическое лицо будет находиться в муниципальной собственности, если его основной вид деятельности – "Общеобразовательные детские школы".
Следует отметить, что свободный поиск раскрывает общие закономерности, т. е. индуктивен, тогда как любой прогноз выполняет догадки о значениях конкретных неизвестных величин, следовательно, дедуктивен. Кроме того, результирующие конструкции могут быть как прозрачными, т. е. допускающими разумное толкование (как в примере с произведенными логическими правилами), так и нетрактуемыми – "черными ящиками" (например, про построенную и обученную нейронную сеть никто точно не знает, как именно она работает).
Анализ исключений (Forensic Analysis)
Предметом данного анализа являются аномалии в раскрытых закономерностях, то есть необъясненные исключения. Чтобы найти их, следует сначала определить норму (стадия свободного поиска), вслед, за чем выделить ее нарушения. Так, определив, что 84% общеобразовательных школ отнесены к муниципальной форме собственности, можно задаться вопросом – что же входит в 16%, составляющих исключение из этого правила? Возможно, им найдется логическое объяснение, которое также может быть оформлено в виде закономерности. Но может также статься, что мы имеем дело с ошибками в исходных данных, и тогда анализ исключений может использоваться в качестве инструмента очистки сведений в хранилище данных.
2.3.2. Технологические методы ИАД
Все методы ИАД подразделяются на две большие группы по принципу работы с исходными обучающими данными.
– В первом случае исходные данные могут храниться в явном детализированном виде и непосредственно использоваться для прогностического моделирования и/или анализа исключений; это так называемые методы рассуждений на основе анализа прецедентов. Главной проблемой этой группы методов является затрудненность их использования на больших объемах данных, хотя именно при анализе больших хранилищ данных методы ИАД приносят наибольшую пользу.
Рис. 10. Классификация технологических методов ИАД.
– Во втором случае информация вначале извлекается из первичных данных и преобразуется в некоторые формальные конструкции (их вид зависит от конкретного метода). Согласно предыдущей классификации, этот этап выполняется на стадии свободного поиска, которая у методов первой группы в принципе отсутствует. Таким образом, для прогностического моделирования и анализа исключений используются результаты этой стадии, которые гораздо более компактны, чем сами массивы исходных данных. При этом полученные конструкции могут быть либо "прозрачными" (интерпретируемыми), либо "черными ящиками" (нетрактуемыми).
Две эти группы и входящие в них методы представлены на рис. 10.
Системы рассуждений на основе аналогичных прецедентов
Идея систем case based reasoning – CBR – на первый взгляд крайне проста. Для того, чтобы сделать прогноз на будущее или выбрать правильное решение, эти системы находят в прошлом близкие аналоги наличной ситуации и выбирают тот же ответ, который был для них правильным. Поэтому этот метод еще называют методом "ближайшего соседа" (nearest neighbour). В последнее время распространение получил также термин memory based reasoning, который акцентирует внимание, что решение принимается на основании всей информации, накопленной в памяти.
Системы CBR показывают неплохие результаты в самых разнообразных задачах. Главным их минусом считают то, что они вообще не создают каких-либо моделей или правил, обобщающих предыдущий опыт, – в выборе решения они основываются на всем массиве доступных исторических данных, поэтому невозможно сказать, на основе каких конкретно факторов CBR системы строят свои ответы.
Алгоритмы К-ближайших соседей лучше всего подходят для кластеризации и классификации. При выявлении кластеров алгоритм сначала представляет каждую запись как точку в многомерном пространстве. Затем он подбирает веса по каждой размерности так, чтобы точки, изображающие данные со сходными целевыми признаками, оказались в тесном соседстве. Предположим, например, что для банка целевая характеристика такова: "люди, обратившиеся за второй закладной". Если параметрами являются возраст, сумма первой закладной, задолженность и доход, то алгоритм последовательно перебирает различные веса для этих размерностей до тех пор, пока все точки, изображающие данные о лицах, обратившихся за второй закладной, не окажутся на графике рядом друг с другом, т.е. соседями. После того как К-ближайшие соседи использованы для кластеризации, они могут помочь произвести классификацию. Например, финансовая организация может очертить круг потенциальных покупок закладных, используя модель К-ближайших соседей. Если К-ближайшие соседи какого-то лица приобретут вторую закладную с некоторой вероятностью, то это лицо приобретет ее с той же самой вероятностью. Финансовая организация может решить предлагать вторые закладные только людям, для которых вероятность покупки составляет, скажем, 66% или выше.
Методы кросс-табуляции
Кросс-табуляция является простой формой анализа, широко используемой в генерации отчетов средствами систем оперативной аналитической обработки (OLAP). Двумерная кросс-таблица представляет собой матрицу значений, каждая ячейка которой лежит на пересечении значений атрибутов. Расширение идеи кросс-табличного представления на случай гиперкубической информационной модели является основой многомерного анализа данных, поэтому эта группа методов может рассматриваться как симбиоз многомерного оперативного анализа и интеллектуального анализа данных.
Статистика
Последние версии почти всех известных статистических пакетов включают наряду с традиционными статистическими методами также элементы Data Mining. Основное внимание в них уделяется классическим методикам – корреляционному, регрессионному, факторному анализу и другим.
Временной ряд – это расположение во времени статистических показателей, которые в своих последовательных изменениях отражают ход развития изучаемых социально-экономических процессов.
Временные ряды исследуются с различными целями. В одном ряде случаях бывает достаточно получить описание характерных особенностей ряда, а в другом ряде случаев требуется не только предсказывать будущие значения временного ряда, но и управлять его поведением. Метод анализа временного ряда определяется, с одной стороны, целями анализа, а с другой стороны, вероятностной природой формирования его значений.
– Спектральный анализ. Позволяет находить периодические составляющие временного ряда
– Корреляционный анализ. Позволяет находить существенные периодические зависимости и соответствующие им задержки (лаги) как внутри одного ряда (автокорреляция), так и между несколькими рядами (кросскорреляция).
– Модели авторегрессии и скользящего среднего. Модели ориентированы на описание процессов, проявляющих однородные колебания, возбуждаемые случайными воздействиями. Позволяют предсказывать будущие значения ряда.
Нейронные сети
Нейронные сети представляют собой большой класс систем, архитектура которых пытается имитировать построение нервной ткани из нейронов. В одной из наиболее распространенных архитектур, многослойном персептроне с обратным распространением ошибки, эмулируется работа нейронов в составе иерархической сети, где каждый нейрон более высокого уровня соединен своими входами с выходами нейронов нижележащего слоя. На нейроны самого нижнего слоя подаются значения входных параметров, на основе которых нужно принимать какие-то решения, прогнозировать развитие ситуации и т.д.
Эти значения рассматриваются как сигналы, передающиеся в вышележащий слой, ослабляясь или усиливаясь в зависимости от числовых значений (весов), приписываемых межнейронным связям. В результате на выходе нейрона самого верхнего слоя вырабатывается некоторое значение, которое рассматривается как ответ, реакция всей сети на введенные значения входных параметров. Для того чтобы сеть можно было применять в дальнейшем, ее прежде надо «натренировать» на полученных ранее данных, для которых известны и значения входных параметров, и правильные ответы на них. Эта тренировка состоит в подборе весов межнейронных связей, обеспечивающих наибольшую близость ответов сети к известным правильным ответам.
Алгоритмы нейросетей обычно используются для задач прогнозирования, кластеризации и классификации. Имитируя деятельность человеческого мозга, они включают в себя много простых устройств обработки, связанных адаптивными весами. Они создают прогнозирующую модель путем рассмотрения "обучающего множества" настоящих записей.
Теоретически формирование нейросети аналогично формированию пути нервного импульса в мозгу, когда человек все время решает одну и ту же задачу. Например, если человек, играя в теннис, набирается опыта, то со временем он может начать автоматически учитывать воздействие таких факторов, как ветер, усталость, натяжение струн ракетки и положение солнца. Аналогично этому, нейросеть совершенствует свою модель с каждой новой записью, которую она изучает. Чтобы алгоритм нейросети смог предсказывать объем продаж фотоаппаратов в сети магазинов, ему будет предложено обучающее множество, содержащее записи одного-двух предыдущих лет с данными о продажах в зависимости от времени года, цены, величины скидки, локальной экономической ситуации и географического положения. Он использует обучающее множество для построения модели. После того как модель будет построена, торговое предприятие с ее помощью сможет предсказывать объем продаж, вводя новые множества записей.
Методы логической индукции
Методы данной группы являются, пожалуй, наиболее выразительными, в большинстве случаев оформляя найденные закономерности в максимально "прозрачном" виде. Кроме того, производимые правила, в общем случае, могут включать как непрерывные, так и дискретные атрибуты. Результатами применения логической индукции могут быть построенные деревья решений или произведенные наборы символьных правил.
Индукция правил создает неиерархическое множество условий, которые могут перекрываться. Индукция правил осуществляется путем генерации неполных деревьев решений, а для того чтобы выбрать, какое из них будет применено к входным данным, используются статистические методы. Алгоритмы индукции ассоциативных правил лучше всего подходят для последовательностей и ассоциаций или для задач анализа сходства, таких, как анализ корзины.
Деревья решения являются одним из наиболее популярных подходов к решению задач ИАД. Они создают иерархическую структуру классифицирующих правил типа «ЕСЛИ... ТО...», имеющую вид дерева.
Деревья решений являются упрощенной формой индукции логических правил. Основная идея их использования заключается в последовательном разделении обучающего множества на основе значений выбранного атрибута, в результате чего строится дерево, содержащее:
– терминальные узлы (узлы ответа), задающие имена классов;
– нетерминальные узлы (узлы решения), включающие тест для определенного атрибута с ответвлением к поддереву решений для каждого значения этого атрибута.
В таком виде дерево решений определяет классификационную процедуру естественным образом: любой объект связывается с единственным терминальным узлом. Эта связь начинается с корня, проходит путь по дугам, которым соответствуют значения атрибутов, и доходит до узла ответа с именем класса.
Область применения деревьев решений в настоящее время широка, но все задачи, решаемые этим аппаратом, могут быть объединены в следующие три класса:
1. Описание данных. Деревья решений позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов.
2. Классификация. Деревья решений отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения.
3. Регрессия. Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых (входных) переменных. Например, к этому классу относятся задачи численного прогнозирования (предсказания значений целевой переменной).
2.3.3. Деревья решений
Как уже отмечалось, деревья решений (decision trees) являются самым распространенным в настоящее время подходом к выявлению и изображению логических закономерностей в данных. Видные представители этого подхода – процедуры CHAID (chi square automatic interaction detection), CART (classification and regression trees) и ID3 (Interactive Dichotomizer – интерактивный дихотомайзер). Пример дерева решений проиллюстрирован на рис. 11.
Рис. 11. Построение дерева решений
Таблица 2
Основные понятия из теории деревьев решений
|
Название |
Описание |
|
Объект |
Пример, шаблон, наблюдение |
|
Атрибут |
Признак, независимая переменная, свойство |
|
Метка класса |
Зависимая переменная, целевая переменная, признак определяющий класс объекта |
|
Узел |
Внутренний узел дерева, узел проверки |
|
Лист |
Конечный узел дерева, узел решения |
|
Проверка (test) |
Условие в узле |
Раасмотрим классический вариант top – down индукции для построения деревьев решений (TDIDT). В его основе лежит принцип «разделяй и властвуй». Строится дерево решений, рекурсивно разделяющее области пространства примеров на подобласти, таким образом, что каждая вершина дерева соответствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потомки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждая такая вершина (лист) помечается меткой, которая обозначает множество примеров, принадлежащих соответствующей области. Каждая внутренняя вершина класса (т.е. вершина, не обозначающая ничего, кроме самой себя) соответствует какому-либо значению некоторого атрибута.
TDIDT обычно включает два шага – построение новых ветвей и редукцию, т.е. удаление ветвей. На первом шаге дерево решений строится так, чтобы в максимальной степени соответствовать обучающей выборке. На втором шаге этот «изоморфизм» превращается в «гомоморфизм», так редукция дерева приводит к уменьшению числа его вершин
Алгоритм построения новых ветвей.
Пусть S – полное множество примеров.
Шаг 1. Поиск «лучшего» атрибута Ai;
Шаг 2.Расщепление множества S на подмножества S1, S2, …, Sn, так, чтобы все примеры из подмножества Sj имели одинаковые значения vij атрибута Ai;
Шаг 3. Для каждого множества Sj: если все примеры в Sj принадлежат одному и тому же классу Ck (имеющему ту же метку класса), то создать лист дерева решений и пометить меткой этого класса. Иначе перейти к 1, положив S = Sj.
Алгоритм заканчивает работу, когда все подмножества помечены, либо отсутствуют атрибуты, разделяющие непомеченные множества.
Что такое лучший атрибут и как его найти? Достаточно разумный критерий основан на подсчете количества классов Ck в каждом из подмножеств, порожденных различными значениями атрибутов. Более точно, функция, используемая для выбора каждого очередного атрибута – кандидата Ai, должна увеличивать (по сравнению с исходной ситуацией) информацию о классах, помечающих обучающие выборки при разбиении рассматриваемого множества S на подмножества S1, S2, …, Sn в соответствии со значением атрибута Ai. Эта функция реализуется некоторой индуктивной процедурой. Общая цель этих действий состоит в том, чтобы построенное дерево было минимальным, насколько это возможно без потери точности.
Для оценки «качества» признака можно использовать информационную функцию полезности.
Пусть вероятность того, что случайно взятый из Sj пример есть Ck. Она может быть оценена относительной частотой , где – число примеров Ck в Sj и nj – число классов в Sj. Энтропия (по Шеннону) подмножества Sj вычисляется по следующей формуле:
.
Пусть значения атрибута Ai расщепляют множество S примеров на подмножества Sj. Тогда энтропия семейства подмножеств Sj порожденных значениями Ai есть:
,
где P(Sj) есть вероятность принадлежности некоторого примера Sj и оценивается отношением мощностей подмножеств Sj к мощности S:
.
Увеличение информации при таком расщеплении происходит благодаря уменьшению энтропии:
,
где H(S) есть априорная (до расщепления) энтропия S.
Таким образом, вариант TDIDT алгоритма для численных значений признаков выглядит следующим образом:
1. Использовать величину энтропии для поиска оптимального расщепления для каждого числового атрибута;
2. Определить такой атрибут, расщепление посредством которого максимизирует энтропию при делении множества примеров на два подмножества;
3. Если критерий окончания не выполняется, повторить процедуру для каждого из подмножеств.
Отсечение ветвей.
Ряд проблем может существенно снизить качество полученного решения. Одна из них связана с тем, что часть дерева, заканчивающаяся меткой класса, может быть порождена примерами, являющимися «шумными» в том смысле, что значимость признака выбрана ошибочным образом. Вторая связана с тем, что если число признаков велико, дерево может содержать ветви, порожденные случайными свойствами, являющиеся нерелевантными корректной классификации. Наконец, очень большие деревья трудно интерпретировать, и для пользователя они будут «черными ящиками».
Для решения вышеописанной проблемы часто применяется так называемое отсечение ветвей (pruning). В принципе, возможны два подхода к отсечению ветвей: он-лайновый (интерактивный) и постсокращение. Онлайновое отсечение ветвей не позволяет дереву расти, когда значение функции полезности, связанное с разделением набора примеров, падает ниже некоторого порога. Постсокращение позволяет отсечь некоторые ветви дерева после завершения его построения.
Один из наиболее известных подходов к сокращению был разработан И.Братко в 1986 году. Он предложил отсекать ветви таким образом, чтобы минимизировать полную ожидаемую ошибку классификации на новых примерах. Для этой цели ошибка классификации подсчитывается для каждого узла в дереве. В листьях дерева для оценки ошибки используются методы теории вероятности. Для узлов, не являющихся листьями дерева решения, ошибка классификации вычисляется как взвешенная сумма ошибок классификации поддеревьев каждого из узлов. Вес полагается равной относительной частоте примеров, «передаваемых» из узла в соответствующие поддеревья. Далее ошибка классификации в «нелиственном» узле оценивается для случая отсечения ветвей, исходящих из него так что он становится листом. Если эта оценка меньше, чем предыдущая, то соответствующие поддеревья отсекаются. Этот процесс распространяется от основания дерева к его листьям до тех пор, пока оценки ошибки уменьшаются.
PAGE 81