Содержание к диссертации
Введение
1. Аналитический обзор методов поиска закономерностей в предметной области с нечеткой системологией 17
1.1. Специфика предметных областей с нечеткой системологией 17
1.2. Современные подходы к "обнаружению знаний в базах данных" 36
1.3. Методы поиска логических закономерностей в данных 56
1.4. Тестирование систем поиска логических закономерностей 67
1.5. Выводы 80
2. Поиск IF-Then правил в данных на основе представлений локальной геометрии 83
2.1. Используемые понятия и обозначения 83
2.2. Общие положения локальной геометрии 92
2.3. Построение локальной метрики как задача отбора переменных 110
2.4. Поиск логических закономерностей средствами линейной алгебры и интерактивной графики 118
2.5. Эффект информационного структурного резонанса 140
2.6. Возможности и перспективы разработанного подхода 156
2.7. Выводы 171
3. Исследование структуры множества логических закономерностей на основе геометрических представлений 175
3.1. Преобразование как мера расстояний между логическими правилами 175
3.2. Методы визуализации данных 181
3.3. Алгоритмы автоматического группирования 193
3.4. Примеры отображения структуры множества логических правил 200
3.5. Выводы 208
4. Алгоритмизация и программная реализация 210
4.1. Общие характеристики системы Deep Data Diver 210
4.2. Работа с системой 216
4.3. Подсистема поиска ассоциаций в данных 226
4.4. Результаты исследования алгоритма 243
4.5. Выводы 249
5. Практические примеры 251
5.1. Прогнозирования продолжительности жизни пациентов, перенесших сердечный приступ, по данным эхокардиограммы .251
5.2. Прогнозирование характера ремиссии у больных бронхиальной астмой по результатам исследования плазмы крови методом лазерной корреляционной спектроскопии 255
5.3. Диагностика заболеваний почек по данным ультразвукового исследования 270
5.4. Прогнозирование продолжительности ремиссий при алкоголизме 265
5.5. Исследование влияния экзогенных и эндогенных факторов на выраженность гемодепрессивного эффекта субтотального облучения тела у больных злокачественными лимфомами 281
5.6. Выводы 292
Заключение 293
- Специфика предметных областей с нечеткой системологией
- Построение локальной метрики как задача отбора переменных
- Преобразование как мера расстояний между логическими правилами
- Прогнозирования продолжительности жизни пациентов, перенесших сердечный приступ, по данным эхокардиограммы
Введение к работе
Развитие современных систем поддержки принятия решений в различных предметных областях со сложной системной организацией идет по пути наращивания возможностей аналитических инструментов баз и хранилищ данных. Важная роль здесь отводится системам "обнаружения знаний в базах данных", реализующим методы автоматического поиска закономерностей в данных, так называемые методы "раскопки данных" (Data Mining).
В самом общем виде Data Mining - это задача обработки баз данных (БД) с целью перехода к базам знаний (БЗ). В БД накапливаются и хранятся эмпирические факты из исследуемой предметной области (фактические данные, примеры экспертных заключений, элементарные высказывания с некоторой оценкой и т.п.), представленные в виде троек <объект-признак-значение признаках В БЗ заносятся сведения, выражающие закономерности структуры множества эмпирических фактов, релевантные прикладному контексту.
Контекст определяет отношения между объектами из БД. Он может задаваться извне БД (например, экспертом) и также продуцироваться признаком или совокупностью признаков из БД. Чаще всего на практике встречаются отношения эквивалентности и порядка. Отношения эквивалентности присущи, в частности, задачам классификации, диагностики и распознавания образов. Отношения порядка свойственны задачам шкалирования, прогнозирования и т.п.
Методы Data Mining имеют много общего с методами решения упомянутых задач классификации, диагностики и распознавания образов. Но их одной из главных отличительных черт является функция интерпретации закономерностей, кладущихся в основу правил вхождения объектов в классы эквивалентности. Поэтому сегодня все большее распространение получают логические методы, например, "эмпирического предсказания" (Загоруйко Н.Г.,
1979), "индуктивного формирования понятий" (Гладун В.П., 1977; Ханти др., 1970), "построения квазиаксиоматической теории" (Финн В.К., 1991) и др.
Есть еще одна важная причина, обусловившая приоритет логических методов. Она заключается в сложной системной организации областей, составляющих предмет приложения современных информационных технологий. Эти области относятся, как правило, к надкибернетическому уровню организации систем (Boulding К.Е., 1956; Поляков А.О. и др., 2000), закономерности которого не могут быть достаточно точно описаны на языке статистических или иных аналитических математических моделей (Дж. Ван Гик, 1981). Гибкость и многообразие логических конструкций индуктивного вывода позволяют нередко добиваться успешных результатов при описании таких сложных систем.
Вместе с тем, главной проблемой создания таких конструкций остается комбинаторная проблема в пространстве элементарных логических событий. При этом отмечается, что совершенно не ясно, как можно распараллелить символьную операцию логического вывода. Отсюда применение логических" методов часто вынуждено опираться на эвристические соображения, не имеющие строгого обоснования.
Описанными выше обстоятельствами обусловлена актуальность разработки новых подходов к поиску логических закономерностей в данных.
Альтернативу логическим символьным методам составляет геометрический подход, использующий язык геометрических соотношений между эмпирическими фактами, выступающими целостными информационными единицами и отображаемыми точками в пространстве признаков. Это, с одной стороны, делает более прозрачными критерии и принципы построения правил вхождения объектов в определенные классы эквивалентности, которые основываются на сравнении объектов с помощью мер, имеющих интерпретацию расстояний. С другой стороны, следует иметь в виду, что использование геометрического подхода при неограниченном
расширении множества эмпирических фактов автоматически приводит к минимальным теоретически достижимым ошибкам принятия решений. Кроме того, многие операции легко распараллеливаются, а визуализация геометрической структуры множества точек позволяет организовать исследование логических закономерностей в совокупности эмпирических фактов средствами интерактивной когнитивной графики. Важность геометрического подхода к решению задач искусственного интеллекта неоднократно подчеркивалась Д.А. Поспеловым.
В отличие от символьных логических методов, реализующих операции над
признаками (интенсиональный подход), в геометрическом подходе главными
элементами выступают объекты (экстенсиональный подход), а основным видом
операций является операция определения расстояния между объектами в
многомерном пространстве признаков. Геометрический и логический подходы
составляют оппозицию, которой соответствует ряд других оппозиций:
конкретное-абстрактное, параллельное-последовательное, синтез-анализ,
дискретное-непрерывное, безусловное-условное, экстенсиональное-
интенсиональное представление знаний, интуитивное—рациональное, правополушарный-левополушарный механизмы мышления и т.п.
В современном представлении логические закономерности, характерные для объектов определенного класса, интерпретируются как геометрические системы инцидентностей в пространстве комбинаторных ситуаций типа "точка Р лежит на линии L" или "линия L содержит точку Р". Простейшими геометрическими комбинаторными системами являются конечные плоскости (системы инцидентности двух конечных множеств линий и точек), подчиненных системе аксиом проективной геометрии. Вместе с тем, теория геометрических комбинаторных систем в настоящее время не разработана в достаточной мере. Прозрачность геометрической интерпретации комбинаторной проблемы поиска логических закономерностей в данных не привела к ясной и продуктивной методологии такого поиска.
Целью настоящей диссертации является разработка методологии обнаружения логических закономерностей в данных на основе геометрического подхода.
Для реализации поставленной цели в диссертации решались следующие задачи:
Разработка теоретических основ, методов и алгоритмов поиска логических закономерностей в данных на базе геометрических представлений.
Разработка методов исследования структуры множества логических закономерностей на основе геометрических представлений.
Разработка и сравнительное исследование программной реализации технологии поиска логических закономерностей в данных на основе геометрических представлений.
Решение диагностических и прогностических задач из области клинико-экспериментальных исследований с помощью разработанной методологии.
Методы исследования основаны на использовании аппарата прикладной статистики, теории нечетких множеств, теории распознавания образов, имитационного моделирования. Результаты исследований получены путем теоретических и компьютерных расчетов, ориентированы на создание конкретных алгоритмических и программных средств, их апробацию и внедрение.
Положения, выносимые на защиту. 1. Сформированы теоретические основы методологии поиска логических закономерностей в данных высокой размерности на основе представлений локальной геометрии. 2. Разработана технология поиска if then правил в данных, основанная на комбинированном применении аппарата линейной алгебры и средств интерактивной графики. 3. Исследован эффект информационного структурного резонанса в многомерных данных и предложена схема активного формирования и использования этого эффекта. 4. Предложен подход, позволяющий исследовать совокупность if-then правил на основе геометрических представлений.
Разработан подход, позволяющий оперировать анализируемыми объектами с нечётким описанием. 6. Получены специальные формулы для формирования локального бинарного пространства, использование которых позволяет реализовывать правило обхода пропусков в многомерных данных.
Разработан и исследован специализированный подход "данные + шум", использование которого улучшает сходимость процесса поиска закономерностей и повышает стабильность получаемых решений.
Научная новизна работы определяется практически полным отсутствием методологии поиска логических закономерностей на основе геометрических представлений в экспериментальных данных высокой размерности. Все выносимые на защиту положения имеют научную новизну.
В первой главе описывается специфика и дается определение предметных областей с нечеткой системологией, приводится обзор современных подходов и методов Data Mining, предназначенных для автоматического обнаружения закономерностей в базах данных, рассматриваются известные алгоритмы поиска логических закономерностей в данных, и с помощью специально разработанного комплекса тестов высвечиваются основные проблемы этих алгоритмов.
Делается вывод, что, несмотря на обилие методов Data Mining, приоритет постепенно все более смещается в сторону алгоритмов поиска в данных if-then правил. С их помощью решаются задачи прогнозирования, классификации, распознавания образов, сегментации БД, извлечения из данных "скрытых" знаний, интерпретации данных, установления ассоциаций в БД и др. Результаты таких алгоритмов эффективны и имеют прозрачную интерпретацию.
Описывается разработанный комплекс тестов для оценки алгоритмов поиска логических закономерностей в данных, включающий тесты на "умение решать очевидные задачи", тесты на "умение находить наиболее полные и точные правила" и тесты на "ложные закономерности".
Разработанный комплекс тестов показал, что наиболее популярные аналитические инструменты Data Mining, реализующие деревья решений или ограниченный перебор в пространстве комбинаторных ситуаций, в ряде случаев не способны решать даже простейшие очевидные задачи. Они выявляют лишь неточные фрагменты истинных логических закономерностей в данных и не могут отличать "ложные закономерности" от устойчивых регулярностей. Кроме того, известные системы для поиска if-then правил не поддерживают функцию обобщения найденных правил и функцию поиска оптимальной композиции таких правил. Вместе с тем, указанные функции являются весьма существенными для построения баз знаний, требующих умения вводить понятия, метапонятия и семантические отношения на основе множества фрагментов знаний о предметной области.
Выявлены и разобраны основные проблемы методов поиска логических закономерностей в данных. Общая проблема для традиционных методов — проблема "первого шага" (сегментация признаков). Известные алгоритмы поиска if-then правил допускают ошибку уже в самом начале своей работы, используя при сегментации эвристические допущения для ограничения дальнейшего перебора. В диссертации обоснован тезис, что первый шаг работы алгоритма, претендующего на "высокий результат", должен заключаться в максимально мелком (с учетом доступных вычислительных мощностей) разбиении исходных признаков на интервалы.
Кроме того, как показало проведенное исследование, в настоящее время до сих пор не разработан вопрос о критерии для оценки систем поиска логических закономерностей в данных. В главе сформулирован такой критерий. Он основан на том, что эффективность какой-либо системы для поиска if-then правил определяется способностью находить за приемлемое время наиболее полные при заданной точности правила для каждой записи базы данных.
Выявленные проблемы явились побудительным мотивом для разработки принципиально нового подхода к решению задачи поиска логических закономерностей данных.
Вторая глава посвящена теоретическим основам технологии поиска логических закономерностей в данных. Здесь даны представления о локальной геометрии и показано, что задача поиска логических закономерностей может быть сведена к задаче конструирования контекстно-зависимых локальных метрик для различных объектов выборки.
Описанные в главе свойства локального пространства позволяют использовать для определения локальных контекстно-зависимых метрик аппарат линейной алгебры, применяемый в ряде методов многомерного анализа данных. В выборе конкретного многомерного метода конструирования локальных взвешенных метрик для объектов обучающей выборки, который сводится к построению линейной модели с неотрицательными коэффициентами, исследователю на первый взгляд предоставляется большой простор. Однако, как показало специально проведенное исследование, наиболее продуктивной зарекомендовала себя процедура, основанная на комбинированном применении методов линейной алгебры и средств интерактивной графики. Одним из наиболее важных моментов в этой процедуре обработки данных является смещение акцента на манипулирование объектами выборки, часть из которых по результатам визуального анализа исключаются из текущей обработки.
Испытание разработанной процедуры поиска логических закономерностей с использованием представлений локальной геометрии и средств интерактивной графики на ряде высоразмерных тестовых задач показало, что данная процедура приводит к результатам, существенно превосходящим результаты известных алгоритмов построения деревьев решений и реализующих ограниченный перебор. Более того, показанные результаты оказались близкими или совпадающими по полноте и точности найденных
логических закономерностей с результатами, которые можно получить лишь полным комбинаторным перебором. Дальнейшее исследование предложенной процедуры показало, что ее высокая эффективность может быть объяснена с позиций резонансных явлений.
В главе сформулировано определение информационного структурного резонанса как явления резкого изменения значения показателя, характеризующего гомологию группировок объектов, на некотором шаге алгоритма агрегации многомерной информации. Описаны общие аспекты информационного резонанса - среда, возбудитель резонанса и наблюдаемое явление. С позиций информационного структурного резонанса предложена и детально описана схема активного формирования этого резонанса в локальной области пространства признаков.
В главе с позиций геометрического подхода рассмотрен и проанализирован вариант нечеткого представления логических правил. Его основное отличие заключается в том, что функции принадлежности строятся не на субъективных оценках и мнениях экспертов, а на эмпирических распределениях расстояний объектов выборки до логического правила. Другое важное отличие связано с интерпретацией нечеткости. Нечеткое логическое правило в представлениях локальной геометрии позволяет оперировать нечеткими интервалами -расстояние от объекта до логического правила для количественных признаков имеет смысл смещения границ интервалов, описываемых элементарными логическими событиями.
Кроме того, предложены специальные формулы формирования локального бинарного пространства, использование которых позволяет процедуре интерактивного поиска логических закономерностей реализовывать правило обхода пропусков в данных.
Предложен прием "данные + шум", использование которого, с одной стороны, способствует более "плавной" сходимости процедуры интерактивного поиска логических закономерностей. С другой стороны, "шумящие" объекты
выполняют важную функцию фальсификаторов, "столкновение" с которыми способствует повышению робастности получаемых решений.
Рассмотрены возможности поиска методами локальной геометрии сложных шаблонов с джокерами, имеющих переменный период в последовательностях чисел и символов, которые представляют интерес для целого ряда областей, например, в биологии и медицине. Особую ценность данные методы, по-видимому, имеют в современных молекулярно-генетических исследованиях, в которых наступил этап выяснения функционального смысла различных участков секвенированной ДНК. Кроме того, методы локальной геометрии продемонстрировали принципиальную возможность получения новых результатов при анализе электрофизиологических измерений.
В третьей главе рассмотрены вопросы исследования структуры множества логических закономерностей на основе геометрических представлений. Здесь привлекательным является использование мощного и хорошо развитого аппарата компьютерного анализа структур многомерных данных, опирающегося на геометрическую метафору. Единственным препятствием для этого служит лишь то, что каждому логическому правилу в разработанном подходе соответствует собственная, специально сконструированная локальная метрика (собственное описание), а не общее пространство признаков с одинаковыми для всех объектов метрическими свойствами.
Для преодоления отмеченного препятствия предложена специальная метрика, которая является мерой различия иерархий близости объектов обучающей выборки к сравниваемым логическим правилам. Иначе говоря, расстояние в предложенной метрике между двумя логическими правилами выражает различие отношений их сходства с объектами выборки. В главе показано, что эффективным приемом для перехода к этим расстояниям, не требующим подгоніси аддитивной константы для удовлетворения метрической аксиомы неравенства треугольника, является вариант, основанный на сравнении двух ранговых последовательностей.
В результате проведенного аналитического обзора сделан вывод, что после перехода к предложенным метрикам для исследования структуры множества логических правил наиболее пригодны методы многомерного шкалирования и иерархические агломеративные процедуры кластерного анализа. Эти методы позволяют получать наглядные визуальные представления о геометрической структуре совокупности логических закономерностей, их результаты дополняют друг друга. При этом деревья, получаемые с помощью агломеративных иерархических процедур кластерного анализа, отображают метаструктуру исследуемых логических закономерностей, в которой на нижнем уровне находятся ранее найденные логические правила, а на более высоких уровнях эти правила объединяются в понятия и метапонятия.
Четвертая глава посвящена алгоритмизации и программной реализации разработанной методологии поиска логических закономерностей на основе представлений локальной геометрии. Одной из главных решенных проблем явилась алгоритмизация действий оператора, участвующего в процессе интерактивного поиска логических закономерностей в данных. Алгоритм, составляющий ядро вычислительной процедуры автоматического поиска if-then правил, представляет собой формализацию действий оператора, преобразующего средствами интерактивной графики выборку объектов в соответствии с разработанной схемой активного формирования информационного структурного резонанса.
В главе описано программное воплощение разработанной технологии -система Deep Data Diver. Эта система содержит следующие структурные блоки: мастер создания нового проекта, мастер формирования задания на поиск логических закономерностей в данных, процедура поиска логических правил в данных, мастер отображения результатов и манипулирования найденными логическими правилами, мастер сохранения и экспорта результатов.
Показано, что уникальные свойства системы Deep Data Diver позволяют находить в данных высокоточные ассоциации элементов исходного множества
транзакций с заданным элементом. Множества ассоциаций с заданными элементами образуют корзины с высоким уровнем обеспечения (support) и длинным набором (long itemsets). На одних и тех же экспериментальных данных продемонстрировано, что система Deep Data Diver способна выявлять корзины с характеристиками обеспечения и длинами наборов в несколько раз превышающими результаты других известных систем. Этот факт послужил стимулом для разработки модификации системы Deep Data Diver, получившей название Big Basket.
В процессе многочисленных испытаний системы Deep Data Diver на экспериментальных данных из различных предметных областей было подтверждено важное свойство - способность находить лучшие или близкие к лучшим (наиболее полным при заданной точности) if-then правила для каждой записи базы данных. Такой вывод, с одной стороны, сделан на основании сравнения результатов с показателями других алгоритмов - каждый раз удавалось обнаруживать в данных существенно более полные логические правила (при заданной точности), чем выдавали известные программные продукты в области Data Mining. С другой стороны, для подтверждения указанного свойства было применено имитационное моделирование с применением разработанного и описанного ранее комплекса специальных тестов.
Одним из важнейших свойств любой программы, предназначенной для решения задач поиска логических закономерностей в данных, является его вычислительная сложность. Результаты тестирования системы Deep Data Diver продемонстрировали масштабируемость алгоритма поиска логической закономерности по отношению к отдельным параметрам таблицы данных, то есть линейную зависимость времени поиска от количества объектов или числа признаков в таблице анализируемых данных. Дальнейшие испытания алгоритма позволили дать оценку его сложности в задачах классификации как
0{pN2).
В пятой главе рассмотрены практические примеры применения разработанной методологии для решения диагностических и прогностических задач клинико-экспериментальных исследований. Представленные примеры затрагивают различные актуальные области медицины - сердечно-сосудистые заболевания, лечение бронхиальной астмы, диагностика заболеваний почек, лечение алкоголизма, методики проведения лучевой терапии при онкологических заболеваниях. Характерной общей чертой этих примеров является то, что традиционные методы статистического анализа здесь показывают маловыразительные результаты при решении задач диагностики и прогнозирования. Вместе с тем, алгоритмы поиска логических закономерностей в экспериментальных данных практически во всех случаях приводят к продуктивному в той или иной мере, полезному решению. Это, в первую очередь, конечно, связано со спецификой медицины как предметной области с нечеткой системологией.
Во всех рассмотренных примерах проводилось сопоставление трех
различных подходов к поиску логических закономерностей в данных -
деревьев решений, ограниченного перебора комбинаторных ситуаций и
разработанного нами подхода, основанного на представлениях локальной
геометрии и использующего схему активного формирования информационного
структурного резонанса. Система Deep Data Diver, реализующая
геометрический подход, продемонстрировала существенные преимущества
перед другими алгоритмами. Это выразилось, как в более высокой точности
обнаруженных в данных логических закономерностей, так и в их более высокой
полноте. Кроме того, в ряде случаев система Deep Data Diver выявила в данных
гораздо более сложные логические правила (включающие большое количество
элементарных логических событий), принципиально не доступные для их
обнаружений другими известными алгоритмами. В целом разработанная
методология поиска логических закономерностей в данных на основе
представлений локальной геометрии достаточно убедительно
продемонстрировала свою полезность и продуктивность в клинико-экспериментальных исследованиях.
Автор выражает глубокую признательность профессору, доктору технических наук Д.А. Поспелову, который в самом начале работы над проблематикой геометрического подхода к поиску логических закономерностей в данных отметил плодотворность этой разработки и поддержал автора ценными советами.
Специфика предметных областей с нечеткой системологией
Движущей силой современного информационного общества являются знания - интеллектуально-информационный ресурс (ИИР). Это новая и пока еще непривычная категория, активно включаемая сегодня в сферу деятельности человека. Относительно ИИР человеку неизвестны законы сохранения или ограничения, так характерные для вещественно-энергетической (материальной) субстанции. По многим параметрам ИИР имеет неоспоримые преимущества по сравнению с материальными ресурсами. Предпочтительность ИИР выражается [23]: в динамичности развития научного потенциала технологии и продукции, повышающего научно-технический уровень населения; в необычайно высокой эффективности производства; в легкости тиражирования найденных научно-технических решений на все множество потенциальных потребителей; в способствовании повсеместному внедрению высоконравственных отношений, как следствия нематериальности производственной сферы.
Общество, базирующееся на информационной экономике, уже по своей структуре избегает большинства социально-экономических и экологических проблем, ситуационно тяготеющих над нами сегодня, и в потенциале предполагается его экспоненциальное развитие по всем основным параметрам ("знания - порождают знания").
Существуют различные определения понятия "знания". В одном из наиболее емких определений [31] под знаниями понимают формализованную информацию, на которую ссылаются или которую используют в процессе решения задач интерпретации, распознавания, прогнозирования и других задач, связанных с поддержкой принятия решений. Знания о предметной области включают описание объектов, их окружения, необходимых явлений, фактов, а также отношений между ними [147].
Различают следующие основные виды знаний: фактические и стратегические знания; факты и эвристики; декларативные и процедурные знания; интенсиональные и экстенсиональные знания; глубинные и поверхностные знания; жесткие и мягкие знания.
Практические разработки в сфере информационных технологий все более смещаются в сторону областей с преобладанием глубинных и мягких знаний. В глубинных знаниях отражается понимание структуры предметной области, назначение и взаимосвязь отдельных понятий (глубинные знания в фундаментальных науках - это законы и теоретические основания). Мягкие знания допускают множественные, "размытые" решения и различные варианты рекомендаций.
К областям с преобладанием глубинных и мягких знаний относятся, например, медицина, экономика, бизнес, социология, метеорология, геология и др. Различные специалисты по-разному выделяют и формулируют особенности таких предметных областей. Ниже рассматриваются представления о специфике указанных областей, сложившиеся у специалистов по искусственному интеллекту, специалистов по моделированию технологических процессов на производстве, специалистов по нелинейной динамике сложных систем и специалистов по прикладному анализу данных. Представления специалистов по искусственному интеллекту Специалисты по искусственному интеллекту часто называют указанные области трудно формализуемыми [137, 149]. Здесь выделяют следующие особенности: ? Задача не может быть определена только в числовой форме (требуется символьное представление); ? Алгоритмическое решение задачи не известно (хотя, возможно, и существует) или не может быть использовано из-за ограниченных ресурсов (памяти компьютера, быстродействия); ? Цели задачи не могут быть выражены в терминах точно определенной целевой функции или не существует точной математической модели задачи. Другие исследователи [136, 159] описывают более широкий круг так называемых НЕ-факторов, характерных для знаний о реальном мире, но плохо представленных в формальных системах. Сюда относят неполноту, неточность, недоопределенность, некорректность и др. А.С. Нариньяни считает, что введение термина НЕ-факторы означает попытку осознать как целое ту область исследований, которая охватывает новые срезы системы знаний: ? совокупность форм знания, плохо поддающихся формализации традиционными методами (этих форм, вне всякого сомнения, гораздо больше, чем хорошо формализуемых), ? различных дефектов знания и возможных форм незнания, являющегося неотъемлемой и основной частью любого знания. НЕ-факторы, отмечает С.А. Нариньяни, - отнюдь не периферия науки о знаниях. "... Ввиду своей универсальности, они пронизывают саму ткань структуры знаний, играя ключевую роль не только в искусственном интеллекте, но и таких, казалось бы, далеких от него областях, как вычислительная математика". Недоопределенность в упоминавшейся выше работе была основательно исследована, что привело к созданию технологии обработки знаний, ассоциируемой с ключевым понятием constraint [86, 106, 137]. Недоопределенное значение является приблизительной, но корректной оценкой некоторой реальной величины, более точной по своей природе, чем позволяет нам установить текущая информация. Неточность является универсальным фактором, свойственным всем реальным параметрам. Для количественных атрибутов выделяют следующие пять базовых типов неточности: объективная, ситуационная, семантическая, методическая и генерализации. Объективная неточность связана с самим "устройством" нашего мира; сюда относятся: ? квантовая неточность, определяемая соотношением неопределенности Гейзенберга. ? тепловая - движение атомов и молекул в жидкости и газе, их колебание в твердом теле. ? релятивистская, связанная с относительностью системы координат. Ситуационная неточность определяется уровнем точности текущего использования значения того или иного параметра. Семантическая неточность "встроена" в само понятие, связанное с данным параметром; имеет место для любых реальных понятий. Методическая неточность определяется неточностью измерения, связанной с рядом факторов: ? физической природой приборов/инструментов, изготовленных с конечной точностью, "встроенным" в определение параметра сопоставлением с эталоном (неточность эталона), ? отсутствием идеальной процедуры замера значения: практически все такие процедуры опираются на понятия "равно", "больше" и т.п., программирующие неточное сравнение неточных величин, ? невозможностью замера в идеальной точке по времени и пространству (наличие обобщения или усреднения). Неточность генерализации имеет своим источником обобщение значения какого-либо параметра у объектов некоторого класса или выборки.
Построение локальной метрики как задача отбора переменных
Как следует из приведенного выражения, задача определения контекстно-зависимой локальной метрики заключается в нахождении линейного преобразования новой векторной переменной А = gj - g . Ограничение на вид преобразования накладывается требованием неотрицательности компонент весового вектора w (k = \,q), так как различие объектов gj и gj по какому-либо бинарному признаку gk должно обязательно приводить к увеличению расстояния di (gj, gj) либо в случае wik = 0 вообще не сказываться на изменении расстояния dt (gj, gj).
Индивидуально сконструированные локальные метрики обеспечивают каждому объекту, как представителю своего класса, максимально возможную "сферу действия", которой нельзя достигнуть при построении общего пространства признаков и использовании одинаковой метрики для всех объектов. Описание каждого эмпирического факта оказывается полностью избавленным от неинформативных элементов, что позволяет в дальнейшем иметь дело с чистыми "незашумленными" структурами данных. В этом описании остается только то, что действительно важно для отражения сходства и различия эмпирического факта с другими фактами в контексте решаемой задачи.
В свете представлений о контекстно-зависимых локальных метриках очевидно, что один и тот же объект может поворачиваться разными гранями своего многомерного описания сообразно заданному контексту. К любому объекту, запечатленному в памяти как целостная многомерная структура, "привязан" набор различных локальных метрик, каждая из которых оптимизирует иерархию его сходства (различия) с другими объектами соответственно целям определенной задачи отражения отношений между объектами реального или идеального мира.
Представление о контекстно-зависимых локальных метриках позволяет объяснить случаи нарушения метрических отношений между элементами матрицы данных, которые наблюдаются в отдельных экспериментах по изучению феноменов психического отражения с помощью техники парных сравнений. Например, в [119] описан эксперимент, где респондент, сравнивая "активную деятельную жизнь" (xi), "жизненную мудрость" (х2) и "здоровье" (х3), дал следующие оценки парных различий этих объектов: di2=2, сііз =1, 23=7. Содержательно это означает, что респондент считает близкими ценности "активная деятельная жизнь" и "жизненная мудрость", а также "активная деятельная жизнь" и "здоровье". Однако считает далекими "здоровье" и "жизненную мудрость". Тем самым, хотя данные оценки (каждая по отдельности) являются интуитивно приемлемыми, их нельзя интерпретировать как геометрические расстояния между ценностями (нарушено неравенство треугольника й?23 12 + 13) и соответственно, невозможно изобразить исследуемые объекты в виде точек в некотором статическом субъективном семантическом пространстве ценностных ориентации. Отмеченный факт объясняется существованием у испытуемого не одного, а нескольких субъективных подпространств с различными свойствами (локальными метриками). Так как внешние условия эксперимента являются постоянными, то смена локальных метрик может происходить вследствие изменения контекста, инициируемого различными парами сравниваемых объектов. Это влечет за собой разнокачественное восприятие сходства объектов объекту, запечатленному в памяти как целостная многомерная структура, "привязан" набор различных локальных метрик, каждая из которых оптимизирует иерархию его сходства (различия) с другими объектами соответственно целям определенной задачи отражения отношений между объектами реального или идеального мира. Представление о контекстно-зависимых локальных метриках позволяет объяснить случаи нарушения метрических отношений между элементами матрицы данных, которые наблюдаются в отдельных экспериментах по изучению феноменов психического отражения с помощью техники парных сравнений. Например, в [119] описан эксперимент, где респондент, сравнивая "активную деятельную жизнь" (xi), "жизненную мудрость" (х2) и "здоровье" (х3), дал следующие оценки парных различий этих объектов: di2=2, сііз =1, 23=7. Содержательно это означает, что респондент считает близкими ценности "активная деятельная жизнь" и "жизненная мудрость", а также "активная деятельная жизнь" и "здоровье". Однако считает далекими "здоровье" и "жизненную мудрость". Тем самым, хотя данные оценки (каждая по отдельности) являются интуитивно приемлемыми, их нельзя интерпретировать как геометрические расстояния между ценностями (нарушено неравенство треугольника й?23 12 + 13) и соответственно, невозможно изобразить исследуемые объекты в виде точек в некотором статическом субъективном семантическом пространстве ценностных ориентации. Отмеченный факт объясняется существованием у испытуемого не одного, а нескольких субъективных подпространств с различными свойствами (локальными метриками). Так как внешние условия эксперимента являются постоянными, то смена локальных метрик может происходить вследствие изменения контекста, инициируемого различными парами сравниваемых объектов. Это влечет за собой разнокачественное восприятие сходства объектов и выражается в нарушении метрической аксиомы неравенства треугольника, которого бы не произошло, если бы субъективное пространство оставалось неизменным в ходе всего эксперимента.
Учитывая приведенные выше соображения, нам представляется в целом непродуктивным широко используемый в настоящее время в области искусственного интеллекта подход, связанный с реконструкцией так называемого семантического пространства. Используемые здесь методики семантического дифференциала [231] и, как "вершина", техники репертуарных решеток [145, 181] используют в качестве математического аппарата методы многомерного шкалирования [244], отображающие понятия предметной области, которыми оперирует эксперт, в единое статическое семантическое пространство. Вместе с тем, не вызывает сомнений факт, что семантическое пространство человека является динамическим, неоднозначным, способным даже к кардинальному изменению в процессе мышления.
Преобразование как мера расстояний между логическими правилами
Показано, что геометрический подход составляет альтернативу логическим символьным методам. Он переводит задачу поиска логических закономерностей в данных на язык геометрических соотношений между эмпирическими фактами, выступающими целостными информационными единицами и отображаемыми точками в пространстве описания. 2. Обосновано положение о том, что в задачах обнаружения логических закономерностей, когда мы имеем дело с системами надкибернетического уровня сложности, каждый объект следует рассматривать как самостоятельный информационный факт (совокупность событий), имеющий ценные уникальные особенности. Указанные особенности раскрываются путем конструирования для любого объекта собственного локального пространства признаков и нахождения индивидуальной меры, определяющих иерархию его сходства с другими объектами, релевантную заданному контексту. 4. Проанализированы различные методы построения локальной контекстно-зависимой метрики, ориентированные на максимизацию заданного критерия. Рассмотрены варианты нахождения контекстно-зависимой локальной метрики под углом зрения задачи поиска группы информативных признаков. Показано, что здесь мы сталкиваемся с известными комбинаторными проблемами, и вынуждены прибегать к различным эвристическим допущениям, позволяющим уменьшить перебор вариантов. Единственное отличие от алгоритмов построения деревьев решений заключается в том, что на каждом шаге работы алгоритма ищется ifhen правило, которое обязательно покрывает заданный опорный объект. Таким образом, это один из путей решения проблемы поиска совокупности логических правил, покрывающих пересекающиеся, но обязательно отличающиеся друг от друга, множества объектов выборки. Данное свойство обеспечивается тем, что для поиска логического правила выбираются опорные объекты, не покрытые ранее найденной совокупность ifhen правил. 5. Сформулированы свойства локального пространства, которые позволяют использовать для поиска локальных контекстно-зависимых метрик аппарат линейной алгебры, применяемый в ряде методов многомерного анализа данных. 6. Предложена процедура поиска логических закономерностей в локальном пространстве, основанная на комбинированном применении методов линейной алгебры и средств интерактивной графики. Одним из наиболее важных моментов является смещение акцента в процедуре обработке данных на манипулирование объектами выборки, часть из которых по результатам визуального анализа исключаются из текущей обработки. Здесь просматривается параллель с концепцией "русел" и "джокеров", развиваемой специалистами по нелинейному анализу - манипуляции с объектами выборки позволяют в обработке массив данных, относящийся к определенному "руслу", для которого оказывается возможным построить достаточно точную линейную модель. При этом достигается высокая полнота модели. 7. Проведены испытания предложенной процедуры поиска логических закономерностей с использованием представлений локальной геометрии и средств интерактивной графики на ряде высоразмерных тестовых задач. Показано, что данная процедура приводит к результатам, значительно превосходящим результаты, показываемые известными алгоритмами построения деревьев решений и реализующими ограниченный перебор. Более того, показанные результаты оказались совпадающими по полноте и точности найденных логических закономерностей с результатами, которые можно получить лишь полным комбинаторным перебором. Дальнейшее исследование предложенной процедуры показало, что ее высокая эффективность может быть объяснена с позиций резонансных явлений. 8. Дано определение информационного структурного резонанса как явления резкого изменения значения показателя, характеризующего гомологию группировок объектов, на некотором шаге алгоритма агрегации многомерной информации. Описаны общие аспекты информационного резонанса - среда, возбудитель резонанса и наблюдаемое явление. 9. Построена схема активного формирования информационного структурного резонанса в локальной области пространства признаков. Эта схема заключается в следующем. Исходные многомерные данные проходят процедуру сегментирования признаков и, тем самым, исходное пространство признаков преобразуется в бинарное пространство комбинаторных ситуаций, в котором каждый объект изображается точкой, расположенной в какой-либо вершине -мерного единичного гиперкуба. Затем выбирается опорный объект, и для него формируется бинарное локальное пространство. Объекты выборки, подаваемые на математическую модель линейной множественной регрессии, выступающую в роли резонатора, на каждой итерации проходят через фильтр, который закрывает доступ объектам с высокими значениями невязок с учетом знака. Индикатор компактности класса опорного объекта служит для отображения итерационного процесса формирования информационного структурного резонанса и для подачи сигнала о завершении этого процесса. 10. Определены асимптотические вероятности ошибки множества логических правил в геометрическом представлении при решении задач классификации. С позиций геометрического подхода логическое правило имеет расширенную трактовку, обусловленную представлениями о расстоянии до (от) логического правила. Логическое правило может быть реализовано в четком и нечетком вариантах. Четкий вариант — это точка (объект gj) в пространстве комбинаторных ситуаций с локально оптимизированным описанием. В нечетком варианте объект g; с привязанной контекстно-зависимой локальной метрикой есть локально-оптимальный классификатор, работающий по принципу минимума расстояния.
Прогнозирования продолжительности жизни пациентов, перенесших сердечный приступ, по данным эхокардиограммы
Постановка задачи поиска ассоциаций в данных наиболее отчетливо конкретизируется в так называемой задаче анализа рыночной корзины. Рассмотрим ее классическую формулировку [215].
Рыночная корзина - это набор товаров (услуг), приобретенных покупателем в рамках одной отдельной транзакции. Сюда относятся, например, результаты визита покупателя в аптеку, интерактивная покупка в виртуальном магазине типа Amazon.com и пр. Регистрируя бизнес-операции в течение всего времени своей деятельности, торговые компании накапливают огромные собрания таких транзакций (базы данных).
Одна из наиболее распространенных задач статистического анализа подобных баз данных, состоит в поиске товаров или наборов товаров (itemset), которые одновременно встречаются во многих транзакциях. Шаблоны поведения покупателей, выявленные благодаря такому анализу, в общем виде характеризуются перечнем входящих в набор товаров и числом транзакций, содержащих эти наборы. Торговые компании используют эти шаблоны для того, чтобы более правильно разместить товары в магазинах, изменить структуру страниц товарных каталогов и Web страниц и т.п.
Набор, состоящий из і товаров, называется i-элементным набором (i-itemset). Процент транзакций, содержащих данный набор, называется "обеспечением" (support) набора. Принято считать, что для того чтобы набор представлял интерес, его обеспечение должно быть выше определенного пользователем минимума; такие наборы называют часто встречающимися (frequent). Для набора товаров часто используют характеристику "доверие" (confidence), связанную с точностью выявления набора тем или иным алгоритмом. Точность всегда определяется по отношению к одному из элементов набора. Она равна вероятности того, что при обязательном вхождении в набор (і - 1) элементов в него войдет также некоторый і-й элемент. Чем выше "доверие" у выделенного набора, тем более значимым для реальной практики является рассматриваемый набор.
Кроме того, важной характеристикой является длина набора і. Проблеме поиска в данных длинных наборов (long itemsets) является весьма актуальной. Она достаточно подробно рассматривается в работе [205].
Одним из первых алгоритмов анализа рыночной корзины был алгоритм Apriori [192]. Данный алгоритм определяет часто встречающиеся наборы за несколько этапов. Каждый этап состоит из двух шагов: формирование кандидатов (candidate generation) и подсчет кандидатов (candidate counting). На 1-м этапе выбранное множество наборов-кандидатов содержит все 1-элементные наборы. Алгоритм вычисляет их обеспечение во время шага подсчета кандидатов. Затем Apriori сокращает множество наборов-кандидатов, отсеивая тех кандидатов, которые не могут быть часто встречающимися. Отсев происходит на основе простого предположения о том, что если набор является часто встречающимся, все его подмножества также должны быть часто встречающимися. 2-й и последующие этапы используют аналогичные операции по отношению к наборам из 2-х, 3-х и т.д. элементов.
В настоящее время известно большое количество Apriori-подобных алгоритмов. Основным недостатком этих алгоритмов считается их неспособность находить длинные наборы. Поэтому исследователи предпринимали и предпринимают попытки изобрести новые подходы и алгоритмы для анализа рыночных корзин. Достаточно подробно указанные попытки описаны в [205], где акцент делается на свойстве масштабируемости алгоритмов (линейной зависимости времени поиска решения от размера анализируемой базы данных).
На наш взгляд, с учетом упомянутого выше аналитического обзора, проблема поиска длинных наборов данных за приемлемое время до сих пор не нашла своего решения. Требуются принципиально новые подходы к поиску ассоциативных правил в базах данных. Возможно, сюда относится подход, реализованный в разработанной нами системе Deep Data Diver. Характеристика иллюстративных данных Для иллюстрации возможностей системы Deep Data Diver мы воспользуемся примером, опубликованном в руководстве по работе с системой PolyAnalyst [233], которая входит в число лидеров на современном рынке инструментов Data Mining. В примере рассматривается конкретная компания -производитель более 250 продуктов, каждый из которых маркируется трехзначным кодом. Цель нашего анализа состоит в выяснении вопроса, какие из выпускаемых продуктов продаются вместе. Часть анализируемой таблицы данных приведена в табл. 4.1. В этой таблице каждая строка представляет транзакцию, а каждая колонка соответствует коду какого-либо продукта. Всего колонок - 255. Ячейки таблицы содержат значения "yes" или "по" в зависимости от того, совершена или нет покупка того или иного товара в определенной транзакции. Таблица содержит описание 1175 транзакций. Обычно в одной транзакции совершается порядка дюжины покупок. 229 Результаты анализа Poly Analyst
Прежде чем приступить к результатам анализа данных системой Deep Data Diver, рассмотрим решение, предоставляемое системой PolyAnalyst. Разработчики этой системы обращают внимание на превосходные свойства своего продукта. Это касается как быстродействия системы (используется подход, связанный с построением деревьев решений), так и качества получаемых решений (впрочем, аналогичные утверждения можно встретить у создателей практически любого программного продукта в области Data Mining).
