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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

МЕТОДОЛОГИЯ ПОИСКА ЛОГИЧЕСКИХ ЗАКОНОМЕРНОСТЕЙ В ПРЕДМЕТНОЙ ОБЛАСТИ С НЕЧЕТКОЙ СИСТЕМОЛОГИЕЙ (на примере клинико-экспернментальиых исследований)

05.13.01 - системный анализ, управление и обработка информации (по прикладной математике и процессам управления)

Направокрукописи

ДЮК Вячеслав Анатольевич

Автореферат

диссертации на соискание ученой степени

доктора технических наук

Санкт-Петербург 2005

Работа выполнена на кафедре информатики и управления в медицинских системах ГОУ ДПО "Санкт-Петербургская медицинская академия последипломного обрачования" Минздрава РФ

Официальные оппоненты:

доктор технических наук, старший научный сотрудник Марлей Владимир Евгеньевич, док-гор технических наук, профессор Поляков Александр Олегович, доктор технических наук, профессор Разоренов Генрих Иванович.

Ведущая организация: Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)

диссертационного совета Д-212.232.50 по защитам диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9, Менделеевский Центр.

С диссертацией можно ознакомиться в библиотеке имени А.М.Горького Санкт-Петербургского государственного университета.

Защита диссертации состоится

часов на заседании

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Г.И. Курбатова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В самом общем виде Data Mining - это задача обработки баз данных (БД) с целью перехода к базам знаний (БЗ). В БД накапливаются и хранятся эмпирические факты из исследуемой предметной области (фактические данные, примеры экспертных заключений, элементарные высказывания с некоторой оценкой и т.н.), представленные в виде троек <объскт-признак-значсние признаках В БЗ заносятся сведения, выражающие закономерности структуры множества эмпирических фактов, релевантные прикладному контексту. Контекст определяет отношения между объектами из БД. Он может задаваться извне БД (например, экспертом) и также продуциропаться признаком или совокупностью признаков из БД. Чаще всего на практике встречаются отношения эквивалентности и порядка. Отношения эквивалентности присущи, в частности, задачам классификации, диагностики и распознавания образов. Отношения порядка свойственны задачам шкалирования, прогнозирования и т.п.

Методы Data Mining имеют много общего с Методами решения упомянутых задач классификации, диагностики и распознавания образов. Но их одной из главных отличительных черт является функция интерпретации закономерностей, кладущихся в основу правил вхождения объектов в классы эквивалентности. Поэтому сегодня все большее распространите получают логические методы, например, "эмпирического предсказания" (Загоруйко Н.Г., 1979), "индуктивного формирования понятий" (Гладун В.П., 1977; Хант и др., 1970), "построения квазиаксиоматической теории" (Финн В К., 1991) и др. Еще одна важная причина, обусловившая приоритет логических методов, заключается в сложной системной организации областей, составляющих предмет приложения современных информационных технологий. Эти области относятся, как правило, к надкибсрнстичсскому уровню организации систем (Boulding K.E., 1956; Поляков А О. и др., 2000). закономерности которого не могут быть достаточно точно описаны на языке статистических или иных аналитических математических моделей (Дж. Ван Гик, 1981). Гибкость и многообразие логических конструкций индуктивного вывода позволяют нередко добиваться успешных результатов при описании таких сложных систем.

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

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

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

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

I СОМСфИЧССКИЙ и лошчсскнй ПОДХОДЫ СОСШВЛИЮ! оппозицию, коюрой СООIНС 1С!|1\СI ряд др\ г оппонщин. конкретное - абстрактное, параллельное - последовательное, сиптсч -аишш). дискрсшос- непрерывное, безусловное - условное, экстенсиональное-интенсноналыюе представление знаний, интуитивное - рациональное, правополушарный -лсиополушарный механизмы мышления и т.н. Пристальное внимание к отмеченным оппонщиям в контексте геометрического подхода отмечается в работах известных философов, математиков, физиков (Б. Паскаль, Л. Койре, О. Шпенглер, Ф. Клейн. Г. Вейль, И М Яглом и др). Во многих и I этих работ акцент делается на различиях оппозиций, которые проявляют», например, и стилях мышления известных ученых, в особенностях их творчества (Ньютон - Лейбниц. Декарт - Брауэр и др.).

Лишь ПСМН01ИС из исслсдоваюлсй ставили себе задачу наши связь, "ючку соприкосновения" отмеченных оппозиций, определить, как одна из оппозиций "перетекает" в дру|ую. Здесь, на наш в нляд. одной из наиболее интересных ньндядит нопьпка Готфрида Вильгельма Лейбница выразить логические конструкции на языке "геометрического исчисления". Но. как ошечал И.М. Яшом, к сожалению идеи Лейбница не были своевременно опубликованы и потому не оказали никакого влияния на развитие европейской научной мысли. Здесь 1акжс имеет смысл добавить, что |-рандиозность поставленных Лейбницем задач, во многом нерешенных и сегодня (сюда, в частности, относятся мысли о нсрспоручснии функций высшей нервной деятельности механизмам), вызвали сю охлаждение к ггой тематике, которое наступило, когда Лейбниц убедился в невоможности их реализации средствами науки XVII века.

В современном представлении логические закономерности, характерные для объектов определенною класса. ишсрпрс1ирую1ся как юометричсскис системы инциденгпостей в пространстве комбинаторных ситуаций типа "точка Р лежит на линии V или "линия I содержит ючку /'". Вместе с тем, прозрачность геометрической интерпретации комбинаторной проблемы поиска логических закономерностей в данных не привела к ясной и продуктивной методологии таш о поиска (Рыбников К.Л., 1985).

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

Для реализации поставленной цели в диссертации решались следующие задачи.

1. Разработка теоретических основ, методов и алгоритмов поиска логических закономерностей в данных на базе геометрических представлений.

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

3 Разработка и сравнительное исследование программной реализации технологии поиска логических закономерностей в данных на основе геометрических представлений.

4. Решение диагностических и прогностических задач из области клинико-эксперимснтальных исследований с помощью разработанной методоло! ии.

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

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

Положения, выносимые на защиту.

• Сформированы теоретические основы методологии поиска логических закономерностей в данных высокой размерности на основе представлений локальной геометрии.

• Разработана технология поиска ¡Мгсп правил в данных, основанная на комбинированном применении аппарат линейной алIсори и средств интерактивной графики.

• Исследован эффект информационного структурного резонанса в многомерных данных и предложена схема активного формирования и использования этого эффекта.

• Предложен подход, позволяющий исследовать совокупность if-then правил па основе геометрических представлений.

• Разработан подход, позволяющий оперировать анализируемыми объектами с нечётким описанием.

• Получены формулы для формироиания локального бинарного пространства, использование которых позволяет рсализовывать . правило обхода пропусков в многомерных данных.

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

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

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

Реализация. Компьютерная реализация разработанной методологии поиска логических закономерностей используется в ряде организаций. К ним относятся Санкт-Петербургская клиническая больница с поликлиникой Российской академии наук, Санкт-Петербургский государственный медицинский университет им. академика И.П.Павлова, Центральный научно-исследовательский рентгенорадиологический институт МЗ РФ, медико-санитарная часть № 22 ООО "Пстро" и др.

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

Апробация. Результаты работы докладывались и обсуждались на 26 международных и всероссийских конференциях, форумах и семинарах по техническим, медицинским и психологическим проблемам. В том числе, на международной конференции по бионическому моделированию БИОМОД-92, международной конференции "Статистическое образование в современном мире: идеи, ориентации, технологам" (Санкт-Петербург, 1996), 7-м Российско-Французском семинаре "Анализ данных и прикладная статистика" (Санкт-Петербург, 1994), международаой конференции "Интернет и современное общество" (СПбГУ, 1998), международной конференции "Informatics and Control - ICI&C97" (St. Petersburg, 1997), международной научной конференции "Интеллектуальные системы и информационные технологии управления" (Псков, 2000), 1-й международной конференции "Системные, информационные и технические средства и технологии в профессиональной деятельности, образовании, оздоровлении и профилактике" (Геленджик, 2003), всероссийском научно-практическом симпозиуме "Прогрессивные аналитические технологии и доказательная лабораторная медицина" (Москва - 2004), международных конференциях разных лет "Региональная Информатика" (Санкт-11стсрбург) и др.

Разработанная в диссертации методология поиска логических закономерностей в данных на основе представлений локальной геометрии отнесена к важнейшим результатам Российской академии наук в 1998 году и за период с 1997 по 2001 г.

Публикации. Основные результаты диссертации изложены самостоятельно и в соавторстве в 6 монографиях и 42 других публикациях (из них 7 опубликованы в периодических изданиях, рекомендованных ВАК).

Структура и обьем работ Диссертация состоит из введения, 5 глав, заключения и списка литературы, включающего 250 наименовании. Работа изложена на 309 страницах, содержит Кб рисунков и 32 таблицы.

СОДЕРЖАНИЕ РАБОТЫ Но введении обосновывается актуальность работы, формулируются цели и задачи исследования, кратко излагается содержание глав диссертации.

В первой главе показано, что практические разработки в сфере информационных технологий все более смещаются в сторону областей со сложной системной организацией, характеризующихся наличием так называемых I IE-факторов. Обобщение ПЕ-факторов с точки зрения целевых, дескриптивных и структурных особенностей позволило выделить следующие основные характеристики областей со сложной системной организацией, являющихся сегодня наиболее актуальным предметом исследования различных специалистов: нечеткость целевых показателей и критериев; неопределенность, неточность, разнотипность и неизвестная размерность описаний; полиморфность жвифшшльиых состояний исследуемых систем; наличие русел и джокеров разного, заранее не швестного формата с неизвестной локализацией. Содержание приведенных характеристик дало основание определить в целом указанные области, как предметные области с нечеткой системологией.

Для построения моделей предметных областей с нечеткой системологией в настоящее время вес большее значение приобретают технологии "обнаружения знаний в базах данных", использующие методы Data Mining. Аналитический обзор современных подходов и методов Data Mining, предназначенных для автоматического обнаружения закономерностей в базах данных, показал, что приоритет все более смещается в сторону алгоритмов поиска логических закономерностей. Во многом это обусловлено достаточной прозрачностью их результатов. R ■чтих алгоритмах подмножества значений какого-либо признака ж, в матрице данных рассматриваются как элементарные события. Наиболее

часто производится поиск if-then правил, которые имеют следующий вид1:

Н . i f (Условие 1) & (условие 2) &.. ■ (условие L) .y^g^ (условие М) до

A, В,

где "условие Г является логическим выражением (чаще всего конъюнкцией), включающим элементарные события на а "условие М", как правило, задает значение (область

значений) так называемого целевого показателя , не входящего в атттецедстгт А|.

С помощью алгоритмов поиска if-then правил решаются задачи прогнозирования, классификации, распознавать образов, сегментации БД, извлечения из данных "скрытых"" знаний, интерпретации данных, установления ассоциаций в БД и др.

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

Общая проблема - проблема "первого шага" (сегментация признаков). Известные алгоритмы поиска if-then правил допускают ошибку уже в самом начале своей работы, используя при сегментации эвристические допущения для ограничения дальнейшего перебора. В первой главе обоснован тезис, что первый шаг работы алгоритма, претендующего на "высокий результат", должен заключаться в максимально мелком

1 Для характеристики ¡ЙЬсп правила в работе используются л на основных показателя - точмосп, и полнота. Точность правила Иц :кго доля случаев В] среди случаев А». Полнота правила но доля случаев А( среди случаев В^.

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

Вторая глава посвящена теоретическим основам технологии поиска логических закономерностей в дачных па базе геометрического подхода.

Общие положения геометрического подхода

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

Первая особенность состоит в том, что для поиска логических закономерностей в данных на основе геометрических представлений необходимо сначала перейти от первичных признаков л, = р) к бинарным переменным gi равно 0 или 1), кодирующим элементарные события Г вида {х, — а\ (а<я,<Ь), (х,<а\ и (лг,>д), где а и Ь —

возможпые значетм jc,. В главе проанализированы различные варианты кодирования (сегментации) исходных признаков в зависимости от их типа и даны соответствующие рекомендации.

Результатом перехода к бинарным неременным является пространство событий G (пространство комбинаторных ситуаций). В этом пространстве, с одной стороны, любой объект & изображается точкой, расположенной в какой-либо вершине л-мерного единичного гиперкуба g, ГДС (J - общее количество бинарных переменных. С другой

стороны, этот же объект представляет собой конъюнкцию элсмс1гтариых событий. Он заключает в себе логическое выражение (событие 1) и (событие 2) и ... и (событие L), являющееся ядром продукции ЕСЛИ (А) ТО (В). За счет такой двойственности представления объекта дальнейшая комбинаторная процедура поиска логических закономерностей получает геометрическое истолкование. Исходные комбинаторные ситуации выглядят как точки в бинарном пространстве, и задача поиска логических закономерностей может быть сведена к проецированию точек исходного пространства событий в подпространства событий меньшей размерности, где логические закономерности выглядят как точки этих подпространств, в которые попадает определенное количество объектов одинакового класса.

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

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

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

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

близостей (удаленности) объектов gj (] - \,Ы) относительно объекта ц.

В случае бинарных признаков наиболее естественной метрикой является локальная взвешенная метрика Хэмминга

= (2)

ще Дц = (I - Д11,1 На-На |. •■•. I «Ч 1)Т и "I= ("М. »'а. ••• > и'ч)Г - весовой веет ор.

Как следует из приведенною выражения, задача определения контекстно-зависимой локальной метрики заключается в нахождении линейного преобразования новой векторной переменной А = | В — й |- Ограничение на вид преобразования накладывается требованием неотрицательности компонент весового вектора так как различие объектов и

щ по какому-либо бинарному признаку gг, должно обязательно приводить к увеличению расстояния <1, (¡51, й)) либо в случае те» = 0 не сказываться на изменении расстояния (ц,, g^).

Свойства локального пространства

Свойство 1. Опорный объект располагается в начале координат локального пространства.

Свойство 2. Линейная функция в локальном пространстве с неотрицательными коэффициентами имеет смысл взвешенного расстояния (в нашем случае взвешенного расстояния Хэмминга) от оиорпо1 о объекта &.

Свойство 3. Если для некоторого подмножества объектов выполняется условие

И^Д(=0, где № - весовой вектор с неотрицательными элементами, то на этом подмножестве истинно следующее логическое высказывание:

г д7((/ = |,г)-Цексы при ненулевых компонентах весового вектора те; - элемент бинарного вектора

Свойство 4. Обратный переход от бинарных векторов gx. в (3) к элементарным логическим условиям Т^ , заданным на исходных признаках х, осуществляется по следующему правилу

Поиск if-then правил в данных на основе представлений локальной геометрии

Для построения локальной метрики могут использоваться различные методы, ориентированные на максимизацию заданного критерия. Наиболее тривиальный путь заключается в том, чтобы ограничиться только поиском группы информативных признаков Л, = | — gjh | и (2). В главе рассмотрены варианты нахождения контекстно-зависимой локальной метрики как задачи поиска группы информативных признаков: последовательное увеличение и уменьшение группы признаков, алгоритмы "плюс / минус г", случайный поиск с адаптацией и др. Показано, что в этом случае реализуется алгоритм построения дерева решений, который отличается от известных алгоритмов тем, что в данном случае дерево решений обязательно покрывает заданный опорный объект. Таким образом, это один из способов решения проблемы поиска совокупности логических правил, покрывающих пересекающиеся, но обязательно отличающиеся друг от друга, множества объектов выборки.

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

На рис. 1 приведена графическая иллюстрация разработанной технологии. К исследуемым объектам привязывается целевая переменная, которая в локальном пространстве в классе опорного объекта принимает значение "О", а в альтернативном классе - значение "С" (в рассматриваемом случаев С = 1). Далее линейными алгебраическими методами ищется новая ось в локальном пространстве (весовой вектор w с неотрицательными элементами). Используемый при этом критерий выражает стремление сгруппировать около нулевой огметки локального пространства как можно больше объектов того же класса, к которому принадлежит опорный объект. Объекты альтернативного класса в соответствии с критерием должны выражать стремление сконцентрироваться около значения "С на искомой оси. В качестве математической процедуры построения новой координатной оси в локальном пространстве в соответствии с приведенным критерием хороню себя зарекомендовал метод наименьших квадратов.

Л

J

Рис. 1. Иллюстрация процедуры интерактивного поиска логической закономерности (разброс объектов но оси ординат введен искусственно)

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

Во-первых, на каждом шаге итерации из анализа исключаются признаки с отрицательными весами меньшими определенного порогового значения. И, во-вторых, так как основной интерес представляет только сравнительно небольшая область около нулевой отметки локального пространства, то удаленные от данной отмеаки объекты исключаются ич анализа с помощью средств интерактивной графики. При этом приоритет в таком исключении отдастся объектам альтернативного класса (справа от значения "С") -желательно, чтобы как можно больше объектов опорного класса оставалось в анализе и претендовало на смешение в точку "0". После каждой итерации параметры оси (весовой ЯСКюр) псрсрасчитываются, и визуальный анализ весов признаков и полученного распределения даст основание для проведения еще одного акта исключетгия объектов и признаков, либо для останова процедуры поиска логической закономерности. Иногда требуется окончательная доводка итерационной процедуры, которая заключается в удалении из модели признаков с относительно малыми весами.

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

Эффект информационного структурного резонанса в многомерных данных

Определение: Информационный структурный резонанс2 (ИСР) есть эффект резкого изменения значения показателя, характеризующего гомологию группировок объектов, на некотором таге алгоритма агрегации многомерной информации.

Общие аспекты явления ИСР представлены в табл. 1. Выраженность явления ИСР зависит, с одной стороны, от среды - множества исходных многомерных данных, подлежащих фуппированию. С другой стороны, на эту выраженность самым существенным образом влияют тип и параметры алгоритма группирования данных.

Таблица I. Общие аспекты информациотюго структурного резонанса

Аспект Содержание

Среда Совокупность значений множества исходных показателей

Возбудитель резонанса Алгоритм агрегации многомерных объектов в гомологичные группы

Наблюдаемое явление Скачкообразное изменение показателя компактности одной или нескольких грунп

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

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

Особый интерес представляет собой возможность активного формирования эффекта ИСР, которая реализуется при интерактивном поиске логических закономерностей в данных. Предлагаемая технология поиска логических закономерностей в данных на основе представлений локальной геометрии использует обучающую информацию при построении контекстно-зависимой локальной метрики для выбранного опорного объекта. Пои этом применяемая математическая модель метода наименьших квадратов — (С^С^) ^¿У^ (У/.- бинарный вектор значений целевой переменной в локальном пространстве, О^ -матрица бинарных данных в локальном пространстве) выступает в роли своеобразного резонатора, усиливающего эффект информационного структурного резонанса. С помощью модели в локальном пространстве определяется ракурс, относительно которого около опорного объекта стремятся сгруппироваться объекты только его собственного класса. Применяемая итерационная процедура изменения указанного ракурса, основанная на исключении из анализа объектов с относительно высокими значениями невязки, способствует увеличению жесткости модели-резонатора. Это выражается в ухудшении обусловлстюсти матрицы вЬвЬ И приводит в копечном итоге к известному феномену, когда незначительные возмущения в данных дают скачкообразные изменения значений весовых коэффициентов в уравнении множественной регрессии. Указанный эффект в традиционном понимании является негативным и разработано достаточно большое число подходов для борьбы с ним (например, метод гребневой регрессии). Однако в нашем случае все манипуляции с выборкой данных в процессе интерактивного, поиска логической закономерности наоборот направлигы на получение этого эффекта, усиливающего выраженность явления информационного структурного резонанса. При этом конечно, должны быть приняты специальные меры для обеспечения стабильности матричных операций на границе устойчивости.

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

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

Рис. 2. Схема активного формирования информационного структурного резонанса

В использованном для иллюстрации тесте таблица данных имеет следующие хараюеристики: количество объектов 400 (из них 100 объектов принадлежит Ь классу и 100 - второму классу К, 200 объектов - случайным образом распределенные значения - класс М), 100 бинарных признаков, принимающих значения Л или В. Требуется найти 4 известных логических правила, по 2 правила на каждый класс. Эти правила представляют собой комбинации от 7 до 15 элементарных логических событий.

Из рис. 3 видно, как сначала постепенно, а затем (ближе к концу процедуры) скачком объекты "нижнего облака" стягиваются к опорному объекту в точку 0 по оси абсцисс. Удобной характеристикой этого процесса может служить, например, ширина на уровне 0,7 функции плотности распределения объектов класса опорного объекта или значение максимума этой функции. Указанная функция для каждого шага процедуры показана на рис. 4. Как следует из данного рисунка, начиная с 12 шага работы процедуры интерактивного поиска логической закономерности, наблюдается быстрый рост значения максимума функции плотности распределения объектов. Этот рост сопровождается скачкообразным изменением к нулю или к единице значений весовых коэффициентов модели-резонатора.

Рис 3 Иллюстрация технологии интерактивного поиска логической закономерности и эффекта информационного структурного резонанса в тестовом примере

Для иллюстративного тестового примера было найдено 4 логических правила, которыми покрываются вес объекты выборки Точность найденных логических правил составляет 100%, а полнота равна 0,5, что отвечает требованиям тестовой задачи Аналогичные резульгагы получены с помощью предлагаемой технологии для большого количества других тестовых задач па "умение находить паиболее полные и точные правила" Вместе с тем, известные подходы к поиску логических закономерностей в данных (алгоритмы построения деревьев решений, методы ограниченного перебора) не справляются с указанными тестовыми задачами и, более того, нередко их результаты оказываются весьма далекими о г предъявляемых требовании

•0,2 -0,1 0.0 0.1 0.2 03 0.4 0.3

Рис. 4. Функция плотности распределения объектов класса опорного объекта

Возможности и перспективы разработанного подхода

В главе с позиций геометрического подхода рассмотрен и проанализирован вариант нечеткого представления лошческих правил. Ею основное отличие заключается в том, что функции принадлежности строятся не на субъективных оценках и мнениях эксперюв, а на эмпирических распределениях расстояний объектов выборки до логического правила. Другое важное отличие связано с интерпретацией нечеткости. Нечеткое логическое правило в представлениях локальной геометрии позволяет оперировать нечеткими интервалами -расстояние от объекта до логического правила для количественных признаков имеет смысл смешения границ интервалов, описываемых элементарными логическими событиями. Па рис. 5 показан пример эмпирического распределения расстояний от опорного объекта с привязанной к нему локальной метрикой, задаваемой вектором веса У/„ ДО объектов обучающей выборки (класс 0 - класс опорного объекта, класс I - альтернативный класс объектов выборки).

0 12 3 4 6

Расстояние до опорного объекта

Рис. 5. Распределение расстояний до опорного объекта в его локальном пространстве

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

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

Проблеме пропусков в данных посвящено много литературы. Тривиальный подход к ее решению заключается в исключении некомплектных объектов из анализируемой выборки. Это, конечно, не выход из ситуации, особенно когда в медико-биологических исследованиях за каждой полученной цифрой (значением переменной) стоит дорогостоящий и трудоемкий эксперимент. Другие подходы связаны с заполнением пропущенных значений в таблицах данных. Развитие этих подходов обусловлено стремлением специалистов уменьшить смещение основных статистических характеристик, таких как математическое ожидание или дисперсия, которое возрастает прямо пропорционально числу пропусков. Наиболее, распространенные методы восстановления пропущенных значений реализованы в известных статистических пакетах, например SPSS, STATISTICA, и используют заполнение пропусков средними значениями и заполнение с помощью регрессии. Другие подходы используют более изощренные приемы, например, основанные на применении метода главных компонент, принципа прецедентности и др.

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

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

опорного объекта gj до g. (у = и выглядят следующим образом:

0 при g,, =0,

0 при (glt=gA)*(glll,gli = 0),

1 пРИ(^=0)Л(Ял = 0)Л

1 прИ((£,(=0)л(£,, = 0)л{А>А',).

где Кт - номер класса, к которому принадлежит объект gr

С помощью формул (5). во-первых, отфильтровываются бинарные признаки с пропусками у опорного объекта, и, во-вторых, объекты с пропусками в той или иной позиции вектора признаков gm = 0, для которой элемент весового вектора wm4 не равен О,

никогда не попадут и точку "О" локальною пространства, где реализуется логическое правило.

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

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

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

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

Методы анализа последовательностей - временных или иных рядов чисел и символов -в настоящее время испытывают определенные затруднения. Специалисты отмечают, что несколько основных моделей, используемых при таком анализе, оказались плохо совместимыми друг с другом по базовым посылкам. Например, для числовых рядов Фурье-анализ требует отсутствия непериодических составляющих, методы Бокса чувствительны к виду одномерных распределений и т.д. Алгоритмы поиска закономерностей в последовательностях символов основываются на переборах, которые можно реализовать только в очень ограниченных вариантах, либо опираются на сильные эвристические допущения.

Продуктивным направлением анализа временных рядов сегодня является подход, связанный с преобразованием временного ряда в матрицу с помощью однопараметрической сдвиговой процедуры "Гусеница". Этот подход независимо разрабатывался в России (Санкт-Петербург, Москва) и США (там его аналог получил название SSA - Singular Spectrum Analysis) и показал себя мощным средством исследования временных рядов (в основном в метеорологии, гидрологии, климатологии). Алгоритм преобразования временного ряда в матрицу данных состоит в следующем .

Анализу подвергается временной ряд { Xt , образованный последовательностью N равноотстоящих значений некоторой (возможно, случайной) функции f(t)

x,=f((i-l)At, i = l,N.

(6)

Ныбирают некоторое число М <N, называемое длиной гусеницы, и первые М значений последовательности/представляют в качестве первой строки матрицы X . В качестве второй строки матрицы берут знамения последовательности с дъ но дчы- Последнюю строку с номером к = N-M + I соаавляют последние М элсмсшов последовательное!и.

Построенную матрицу, элементы которой равны хч = x,+j \, можно рассматривать как Af-мерную выборку объема к или ^/-мерный пременной ряд, которому соответствует Л/-мерная траектория (ломаная в М-мерном пространстве) из Ы звена. Матрица X (ее называют матрицей ряда) представлена в традиционном для прикладной статистики виде "строка - объект, столбец - признак". Для се дальнейшей обработки теперь можно применять различные методы из богатого арсенала математического аппарата многомерного анализа.

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

Вместе с тем, сегодня для анализа закономерностей временного ряда вес чаще стали применяться методы Data Mining, предназначенные для обнаружения различных шаблонов (паттернов) во временном ряде. При этом особую ценность в обнаружении таких шаблонов имеют логические методы. Эти методы позволяют находить логические if-then правила, характерные для строк N-мсриой временной матрицы и не характерные для случайно сгенерированной N-мсрной матрицы данных. Они пригодны для анализа как числовых, так и символьных последовательностей, и их результаты имеют прозрачную интерпретацию. В то же время при выборе того или иного метода поиска следует опираться на сформулированный нами в первой главе критерий, отражающий его способность выявлять наиболее полные и точные if-then правила для каждой строчки временной матрицы за приемлемое время. К сожалению, известные методы в слабой степени способны удовлетворять этому критерию но описанным ранее причинам.

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

На рис. 6 приведен сравнительно несложный, но показательный пример результатов поиска шаблона методами локальной геометрии в небольшом фрагменте ДНК e-coli (кишечной палочки). Этому фрагменту соответствует первая строка таблицы. Правая часть таблицы (выделенный прямоугольник), обозначенный как "область поиска", -N-мсрная матрица ряда (М =23). К этой части была также присоединена не показанпая па рисунке случайно сгенерированная таблица такого же размера (в ней вероятности появления каждого из четырех символов А, С, Т, G одинаковы и равны 0,25).

В рассмотренном примере во фрагменте ДНК удалось найти шаблон АХААХА, где в позиции X может стоять любой из четырех символов А, С, Т, G. Обращает на себя внимание то, что найденный шаблон появляется в последовательности ДНК через различные по длине интервалы (8, 8, 7, 8).

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

Т*А Т*Тс Т

С А А Л С

А С А А Т V Т А С А А Т Г А СА А Т А С А

Т А

Г'Г

О АС АО тТоТХ аТос то а т т Т О а С А О С Т О А т

СТОАСАОТ\ОЪА,ААОСТОА X С ГО А С А О Т X О х \ А \ о С Т О

т*стоасаотХо*\а\ост ат^стоасаотА,о ^\а А(0 с А А Т % С Т О А С А О Т А» А^А А О С А А т\сТ О А С А О Т А,0Ъ А СА А т\с ТОАСАОТА О^Х А Т А С А А Т \С Т О А С А О Т АкО АД Т А С А А Т А С Т О Л С А О Т А^О Ъ тасаат^стоасаотХо тасаатХстоасаотХ 1 ТАСААТ^СТОАСАОТ | ГАСААТ^СТОАСАО ТАОААТ А, С Т О А С А

I Л С 4 А 7 0 4 С

Г А С А А Т А.СТ О А - .., 1, ЛСААТА^СТО

_ _ Т А С А А Т А, С Т

__¡^ I ТАСААТ А^С

_ Т А С А АД А

ТАСААТ

_____ Т А С А А

^ _ _ Т А С А

! ' П ТАС

' 1 ¿_1 1 I та

' жк.-' I Ц\т

-чт*'-

—фг-'— 7 м

ТТТАС СИ* ТА <с\тт ^ *»с X т г\*,с А.

Ь Т А «\С ТАА

г о\ т Ъ г т о\ т

Т Т о\ ) А Т Т О Г О А Т Т СТОАТ ) С Т О А

к ОС Т О 0° ст

1,А А,0 С ^ «А ¡>,0 АСА0 14» ,0

Г *,0 А X

оТтТХс > ► ►

Т ОПА Т ^ *

Т Т А

атто'ат

О А Т Т«У Т О А Т т о С Т О А т Т О С Т О А Т Х^О СТО А а Хос т с Ха Хо с т

\\Дв с

о *\а\О т Д« А\д

А 0 Т Д.0 Д

с А о т 4*0

о А С А О т т О А С А О СТО АСА Я т *ч0 X X СТ О АС

Т АСТ О А А Т X. С Т О А А Т Х.СТ С А А Т А» С А С А А Т А, ТАСААТ

~Г1 г

Т А С А А

Т А С А

Т А С Т А

« А тТГтТХсТс а т с о с с лТГ СА А тПгМ^ПсА Т СО ССА АСААТАТ ААСАСА Т С О С С

тасаататаасасатсос

ТТАСААТАТААСАСАТСО 1ттАСААТАТААСАСАТС ,СД,ТТАСААТАТААСАСАТ А р А»Т 1Л.Г ПТАДАА Г1ХА

Т X А«С Ьтт А С А А Т А Т А А С

\ т X а с*7г тл 0%А Т К&Ч 4

к О т » о С А О Т к СА О Т ) А С А О Г О А е А ВТ О А О СТО А

Ерто

»Тлст

к А Т А С С А А Т А

ААТАТААС ТТАСААТАТАД Т о\т ^¿Х *(ТТАСААТАТА Т Т О *А Т А,А'£ ¿»ТТАСААТАТ А Т Г О Ъ Т А. А' ^ ^ Т Т А С А А Т А о а т т оИтЦЦ|сИт тАсаат ТОАТТОАТААСАТТАСА СТОАТТОАТААСАТТАСА ОСТОАТТОАТААСАТТАС ХОСТОАТТОАТААСАТТА

аДостоаттоатаасатт

Л>А ХОСТОАТТОАТААС ХДчАД,ОСТОАТТОАТААСА

%оХА>аА.остоаттоата а»о К а,а Ач0 СТОАТТОАТ Т ¿0 А, АХА А, О СТОАТТОА О Т ¿.ОАч0 СТОАТТОАТ А О Т Д,0\^А * О С Т О А Т Т О е А О Т 4,0 АЛА 1о С ТОАТТО А О А о т|мв|а|а|а|а|о С т о а т т ОАСАОТАОААААОСТОАТ ТОАСАОТАОААААОСТОА СТОАСАОТАОААААОСТО

Рис 6 Методами локальной геометрии во фрагменте ДНК найден шаблон с джокерами и изменяющимся периодом

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

Для преодоления отмеченного препятствия предложены специальные Л-метрики, которые являются мерами различия иерархий близости объектов обучающей выборки к сравниваемым логическим правилам Иначе говоря, расстояния в предложенных метриках между двумя логическими правилами выражают различие отношений их сходства с объектами выборки В главе показано, что эффективным приемом для перехода к этим расстояниям, не требующим подгонки аддитивной константы для удовлетворения метрической аксиомы неравенства треугольника, является вариант, основанный на сравнении двух ранговых последовательностей («/"-метрика)

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

Ниже приведена иллюстрации геометрического представления структуры множества логических закономерностей на примере экспериментально-психологических данных (задача распознавания психологических типов по Юнгу с использованием проективного теста "Рисунок несуществующего животного").

Рассматривалось множество из 25 найденных логических правил: а1 -а8 (1-й тип); Ы -Ь7 (2-й тип); с1 - сб (3-й тип) и ё1 - (14 (4-й тип). Нумерация типов является условной. Для каждого логического правила определялось число несовпадений элементарных условий ил каждом из 371 объекте (тестируемом). Эти числа составили таблицу, где колонки -количество несовпадений с найденными логическими правилами (расстояния от логического правила), строки - объекты.

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

В первом способе сначала вычислялась матрица коэффициентов ранговой корреляции Кспдадла. Затем эта матрица преобразовывалась в матрицу л"-расстояний, которая выступала в роли исходных данных для алгоритма многомерного шкалирования по Торгерсону. Множество логических правил, отображенное на плоскость виртуальных главных компонент, изображено на рис.7. Во втором способе использовалось прямое вычисление расстояний между столбцами таблицы в городской метрике, и затем применялась иерархическая агломератнвная процедура кластерного анализа по методу Уорда (рис. 8).

Рис. 7. Отображение логических правил, описывающих психологические типы, на плоскость

главных компонент

Рис. 8. Дсидрограмма логических правил

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

Четвертая глава посвящена алгоритмизации и программной реализации разработанной методологии поиска логических закономерностей на основе представлений локальной геометрии. Одной из главных решенных проблем явилась алгоритмизация действий оператора, участвующего в процессе интерактивного поиска логических закономерностей в данных. Алгоритм, составляющий ядро вычислительной процедуры автоматического поиска if-then правил, представляет собой формализацию действий оператора, преобразующего средствами интерактивной графики выборку объектов в соответствии с разработанной схемой активного формирования информационного структурного резонанса.

В главе описано программное воплощение разработанной технологии - система Deep Data Diver (www.datadivcr.nw.ru). Эта система содержит следующие структурные блоки: мастер создания нового проекта, мастер формирования задания на поиск логических закономерностей в данных, процедура поиска логических правил в данных, мастер отображения результатов и манипулирования найдеттыми логическими правилами, мастер сохранения и экспорта результатов.

Функциональная схема системы Deep Data Diver, автоматизирующей технологию интерактивного поиска логических закономерностей в данных на основе представлений локальной геометрии, представлена на рис. 9.

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

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

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

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

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

Рис. 9. Функциональная схема системы Deep Data Diver

Рис 10 Графическое отображение найденной корзины элементов

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

В процессе многочисленных испытаний системы Deep Data Diver на экспериментальных данных из различных предметных областей было подтверждено важное свойство - способность находить лучшие или близкие к лучшим (наиболее полным при

заданной точности) if-then правила для каждой записи базы данных. Такой пынод, с одной стороны, сделан на основании сравнения результатов с показателями других алгоритмов -каждый раз удавалось обнаруживать в данных существенно более полные логические правила (при заданной точности, чем иыдавали извесшыс программные продукт в облает Data Mining. С другой стороны, для подтверждения указанного свойства было применено имитационное моделирование с применением разработанного и описанного ранее комплекса специальных тестов.

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

Тестовые данные представляли собой таблицы, заполненные нулями и единицами. Количество признаков р начиналось с 25 признаков и заканчивалось 200 признаками с шагом 25 признаков. Число объектов в таблицах данных принимало следующие значения: 250, 500. 750. 1000, 1500, 2000, 3000 и 4000. Данные генерировались с использованием генератора случайных чисел (распределение Бернулли с равными 0.5 вероятностями для пулей и единиц). Случайное распределение данных выбиралось из соображений, то для этого варианта работа алгоритма поиска логических закономерностей требует наибольшего времени (здесь отсутствует эффект информационного структурного резонанса и алгоритму требуется наибольшее количество шагов). В целом объем данных в тестовых таблицах колебался от 6250 до 800000 чисел.

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

3,8 4.2 ■ 4,6 5 5.4 5,8 6,2 Логарифм объема данных

Рис. 6. Зависимость времени решения задачи от логарифма общего объема данных

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

правил имеет сложность O(pN2).

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

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

Ниже приведен пример построения базы знаний для прогнозирования продолжительности жизни пациентов, перенесших сердечный приступ, по данным эхокардиограммы. Выбор этого гримера для представления в авюрсферате обусловлен тем, что исходные данные широко известны специалистам, так как размещены в популярном рспозитории UCI (http://wwwJcs.uci.edu/MTilcani/MLRcpository.html; University of California, Irvine). Они имеют следующие характеристики.

1. Количество объектов (пациентов): 131

2. Количество признаков: 8

3. Информация о признаках:

• age-at-heart-attack - возраст сердечного приступа;

• pcricardial-cffusion - иерикардиальный выпот (бинарный признак);

• fractional-shortening - фракция укорочения (измерение сократимости);

• E-point septal separation - расстояние от Е-пика движения передней створки митрального клапана до межжелудочковой перегородки;

• left ventricular end-diastolic dimension - диастолический размер левого желудочка;

• wall-motion-score - оценка движения сегментов левого желудочка;

• wall-motion-index - индекс движения стенок левого желудочка;

• alivc-at-l - годовая выживаемость (целевой признак). Значение "Dead" говорит о том, что пациент умер в течение года после сердечного приступа; "Alive" означает, что пациент живет больше года после сердечного приступа.

4. Информация о классах: 88 пациентов относятся к классу "Dead", 53 - к классу "Alive".

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

Для обработки описанных данных с целью поиска if-then правил для прогнозирования времени жизни применялись три системы Daia Mining: See5 (деревья решений), WizWhy (частично ограниченный перебор) и Deep Data Diver (нахождение логических закономерностей на основе представлений локальной геометрии).

Система Sec5 обнаружила в экспериментальных данных всего два правила: Rule I: wall-motion-index > 1.3 -> Класс "alive" Rule 2: wall-molion-index <= 1.3 -> Класс "dead"

Ошибка предсказания с помощью этих правил составляет 31,3 %

Система WizWhy при выставленных по умолчанию настройках нашла в данных 48 if-then правил. Пример одного из правил системы WizWhy представлен ниже. If pericardia! effusion is ().(K)

and fractional shortening is 0,27 ... 0,61 (average = 0,35 ) Then

Alive at 1 year is dead Точность правила: 0,964 Правило покрывает 27 объектов.

В совокупности найденное множество логических правил системы Wi7Why обеспечивает сравнительно невысокую точность прогноза. Так, точность прогноза для класса "Dead" составляет 0,83; для класса "Alive" - 0,73. Для системы Deep Data Diver оказалось достаточно всего 19 if-then правил, чтобы полностью покрыть множество объектов класса "Dead". Примеры наиболее полных и точных правил приведены в табл. 2.

_Таблица 2. Примеры логических правил, обнаруженных системой Deep Data Diver_

if age at heart attack < 73,33 and left ventricular end-diastolic dimension < 4,72 and 8,83 1. >= wall-moiion-score < 15,5 and wall-moiion-index < 2,22 then Alive at 1 year = Dead

_ (Точность - 0,95: Полнота - 0,42)_

^ if left ventricular end-diastoiic dimension < 4,42 and wall-motion-index < 1,29 then Alive

at 1 year = Dead (Точность - 1,0; Полнота - 0,27)_

^ if fractional shortening >= 0,27 and 11 >= wall-motion-score < 17 and wall-motion-index

< 2,3 then Alive at 1 year = Dead (Точность - 1,0; Полнота - 0,24) _

if pericardial effusion = 0 and E-poinl septal separation < 8,58 and 9,5 >= wall-motion-4. score < 17 and wall-motion-index < 2,3 then Alive at 1 year s Dead _ (Точность - 0,92: Полпота - 0,25)_

Полученное множество логических правил составило основу базы знаний экспертной системы для прогнозирования продолжительности жизни пациента после сердечного приступа по данных эхокардиограммы. Алгоритм принятия решения о принадлежности пациента к прогнозируемым классам работает по следующему принципу. Если "срабатывает" хотя бы одно из 19 выявленных правил, то пациент принадлежит к классу "Dead". В противном случае - к классу "Alive". Точность прогноза данного алгоритма составляет 91,6 %. При этом вес ошибки приходятся на неправильное отнесение объектов класса "Alive" к классу "Dead". Тем самым, экспертная система, использующая данный алгоритм, функционирует с "перестраховкой", делая ошибки типа "ложная тревога".

Как видно из табл. 2, найденные правила включают в себя достаточно большое число элементарных логических собьггий, что, конечно, затрудняет их понимание специалистом. Для улучшения смыслового восприятия система Deep Data Diver предлагает специалисту

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

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

1. диастолический размер левого желудочка < 4,72 & индекс движения стенок левого желудочка < 2,29;

2. возраст сердечного приступа < 60;

3. фракция укорочения > 0 & оценка движения сегментов левого желудочка >= 9,5;

4. оценка движения сегментов левого желудочка < 20;

5.9,15 >= оценка движения сегментов левого желудочка < 16,08 & 1,1 >= индекс движения стенок левого желудочка < 2,1.

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

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

ОСПОВИЫЕ РЕЗУЛЬТАТЫ ГАВОТЫ

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

2. Разработан комплекс тестов для испытания алгоритмов поиска логических закономерностей в данных и сформулированы основные проблемы известных подходов.

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

4. Разработаны теоретические основы технологии поиска логических закономерностей в данных на базе представлений локальной геометрии, в которых задача поиска логических закономерное гей в данных сводится к конструированию локальных контекстно-зависимых метрик для объектов выборки.

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

6. Дано определение информационного структурного резонанса и предложена схема активного формирования этого резонанса в локальном пространстве признаков.

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

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

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

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

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

12. Разработана программная реализация (система Deep Data Diver), в которой автоматизирована технология интерактивного поиска логических закономерностей в данных па основе представлений локальной геометрии.

13. Проведено сравнительное исследование эффективности разработанной методологии на ряде практических примеров из области клинико-экспериментальных исследований. Система Deep Data Diver продемонстрировала существенные преимущества перед другими алгоритмами.

ОСПОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

Монографии

1. Дюк В.А Компьютерная психодиагностика. - СПб: "Братство", 1994. - 364 с.

2. Вассерман Л.И., Дюк В.Л., Иовлев Б.В., Червинская К.Р. Психологическая диагностика и нопые информационные технологии. - СПб: "СЛП". 1997. - 203 с.

3. Дюк В.А Обработка данных па ПК в примерах. - СПб: "Питер", 1997. - 240 с.

4. Блажнс А.К., Дюк В.А Тслсмсдицина. - СПб: "СпсцЛит", 2000. - 154 с.

5. Дюк В.А., Самойленко А.П. Data Mining : учебный курс. - Изд-во "11нтер", 2001. - 368 с.

6. Дюк В.А., Эмануэль В.Л. Информационные технологии в медико-биологаческнх исследованиях. - Изд-во: "Питер", 2003. - 525 с.

Другие публикации

1. Воробьев В.М.. Дюк В.А., Иовлев Б.В., Сснопалышков Е.В., Чигирев В.А. Разработка автоматизированной системы массоного обследования в профилактических целях // Журнал неврологии и психиатрии им. С.С. Корсакова. - Л.: Психоневрологии, ин-т им.

B.М.Бехтерева, 1981.-С. 137-141.

2. Воробьев В.М., Дюк В.А. Адаптивные свойства дичтюсти и принципы их машинной дпагностики//Тсз. докл. VI Всссоюзн. Съезда психологов. - М.: 1983. - С. 223-224.

3. Аккерман Р.И., Далсцкий К.П., Дюк ВА, Ефимов Ю.С., Полянкин Г.А. Диагностирование состояния колец ЦПГ ДГ14-10 виброакустическим методом/УМорской транспорт, 7(555), 1983.-С. 12-16.

4. Акксрмап Р.И., Далсцкий К.П., Дюк В.А. Виброакустическое диагностирование топливной аппаратуры дизеля. — Двигатслсстросние, 1984, № 2. С. 23-26.

5. Дюк В.А., Воробьев В.М. Совершенствование автоматизированных методов обработки психологических мзмсрснийУ/Тсз. докл. Всссоюзн. конф. по инженерной психологии. -Л.: ЛГУ им. А.А. Жданова, 1984. - С. 58-60.

6. Воробьев В.М., Буров В.В., Дюк В.А. Опыт медико-психологического обследования некоторых контингентов молодсжи/Дцравоохранение РСФСР, 1982, № 2. - С. 37-39.

7. Воробьев В.М., Дрызго Н.Н., Дюк В.А., Саввин Ю.Б., Чигирев В.Л. Научно-методические рекомендации по применению стандартизироватюго личностного вопросника для медико-психологического обследования кандидатов в ввузы. - Л.: МО СССР, 1984. — 32 с.

8. Воробьев В.М., Дюк В.Л. Применение стандартизированных вопросников для экспресс-диапюстики нервно-психических расстройств // Журнал неврологии и психиатрии им.

C.С. Корсакова. - Л.: Психоневрология, ин-т им. В.М. Бехтерева, 1985. - С. 27-29.

9. Дюк В.Л. Проблемы применения формальных методов формирования метапонятий при концептуальном анализе знаггий//Мстоды и средства принятия решений. Системы поддержки процессов проектирования на основе знаний. - Рига: Рижск. техн. ун-т, 1991. - С. 90-95.

10. Дюк В.Л. Новый класс метрик/Яез. докл. международн. конф. по бионическому моделированию. "Биомод-92", СПб, 1992.-С. 231-233.

11. Дюк В.А. Современные информационные технологии в психодиагностике: экстенсиональный подход - альтернатива традиционной мстодологии//Тр. IV Мсжд. конф. "Региональная информатика-95", СПб, 1995. - С. 175-176.

12. Дюк В.А., Мирошпиков А.И. Эволюция Statgraphics. - Мир ПК, 1995, № 12. - С. 32-34.

13. Дюк ВА, Миропшиков А.И. Statgraphics Plus for Windows - учебное пособие по прикладной статнстике//Мсждународная конф. "Статистическое образование в современном мире: идеи, ориентации, технологии", тез. докл, 3-5 июля 1996 г. - Санкт-Петербург, 1996.-С. 190-196.

14. Дюк В.А. Поимс информационные технологии в психодиагностике// Тр. V Межд. конф. "Региональная ипформатика-%". СПб, 1996. - С. 261-267.

15. Дюк В.Л. Формирование знании в системах искусственного интеллекта: геометрический ||одход//Всстаик академии технического творчеава. - СПб.: изд-во С1161ТУ, 1996, Л» 2.

- С. 46-67.

16. Дюк В.А., Паронько А.В. Раскрытие взаимосвязей психологического и биологического на основе методов акупунктуры: возможности и перспективы применения в телемедишше (ч. 3, глава 4)/В кн. Телемедицина. Новые информационные технологии на пороге XXI иска. - СПб: СГПШРАП. 1998. С. 273-302.

17. Дюк В.А. Формирование знаний в системах искусственного интеллекта: геометрический подход (ч. 4, глава 2)/В кн. Тслсмеднцина. Новые информационные технологии на пороге XXI века. - СПб: СПИИРАН, 1998. С. 367-389.

18. Дюк А.В., Дюк ВА Технологии Data Mining в социальных исслсдопаннях/Информагнка

- Исследования и Инновации. Выпуск 3. Межвузовский сборник научных трудов. - СПб: РГПУ им. А.И. Герцена, 1999. - С. 171-172.

19. Дюк В.Л. Data Mining - интеллектуальный анализ данных//Ву1е (Россия), №9, 1999. -С. 18-24.

20. Дюк В.А.. Епьяшсвич A.M.. Коваленко АА, Петрова Е.Ю., Рейиин Г.Р., Филимонов А.В. О разработке типологического теста с применением методов распознавания образов//Соционичсскис чтения, № 7(28), 1999. - С. 1-2.

21. Дюк В.Л. Разработка базы знаний экспертной системы для прогнозирования продолжительности ремиссий при алкоголизмс//ма1сриалы научно-практического семинара "Тслсмсдицниа - становление и развитие", Санкт-Петербург, 2000. - С. 64-75.

22. Дюк В.А. Ключевые вопросы психологической диагностикнЛТр. Мсжд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков, 19-23 нюня 2000 г.). - СПб.: Изд-во СНбГТУ, 2000. - С. 399-403.

23. Дюк В.А. От данных к знаниям - новые возможности обработки баз ланных//Тр. Мсжд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков, 19-23 июня 2000 г.). - СПб.: Изд-во СПбГТУ, 2000. - С. 438-440.

24. Дюк В.Л. Сравнение структуры интеллекта "физиков" и "лириков"// Тр. Межжд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков. 19-23 июня 2000 г.). - СПб.: Им-во СП6ТТУ, 2000. - С. 403-406.

25. Дюк В.А. Поиск сложных непериодических шаблонов в последовательностях числе и символов методами локальной геометрии // Тр. СПИИРЛН. - 2002. - Т.2, № 1. - С. 263268.

26. Асеев М.Г., Баллюзек М.Ф.. Дюк В.Л. Разработка медицинских экспертных систем средствами технологий Data Mining//C6opnnK докладов Международной научно-практической конференции, 15 октября 2002г. / Под ред. д.м.н. Б.А.Кобринского, к.ф.-м.н. Ю.А.Прокопчука. к.б.н. О.А.Харчспко /. - Днепропетровск: ИПК ИнКомЦснтра УГХТУ.2002.-С.5-14.

27. Дюк В.Л. Тестирование систем для поиска if-then правил в данных // Материалы VIII Санкт-Петербургской международной конференции "Региональная информатика-2002". Часть 2,2002.-С. 42.

28. Дюк В.А. Осколки знаний// Экспресс- Электроника, 2002, № 6. - С. 60-65.

29. Дюк В.Л., Русаков Ю.М. Телемедицина// Экспресс-Электроника, № 9,2002. - С. 52-57.

30. Дюк В.А. Обнаружение знаний в базах данных: проблемы и перспективы // Мат. конф. "Инфокоммуникации. Подготовка кадров и кадровая политика", Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А.Бонч-Брусвича. - 2003. 26-28.

31.Дюк В. Л., Кыркуион Е. Л., Подход к выявлению общих характеристик oajhi знаний // Мат. конф. "Инфокоммуникашш. Подготовка кадров и кадровая политика", Санкт-Петербургский государственным университет телекоммуникаций им. проф. М.Л.Бонч-Врусвича. - 2003. - ар. 21-25

32. Дюк ВА. Рулнипкий СП. Особенности анализа информации к дисташшошюй биомстрш 'психического состояния // Сб. докладов 1 й Мсжд. конф. "Системные, информационные и технические средства и технологии в профессиональной деятельности, образовании, ощоровлении и профилактике. - Санш-Петербург - Новороссийск - Геленджик. - нзд-ио: СПбГТУ. 2003. - С. 55-67.

33. Дюк В.А., Рудницкий СП. Дистанционное распознавание психического состояния биологических объектов - проблемы, поиски решения // Международная дистанционная научно-практическая конференция "Информационные Технологии и Кибернетика на Службе Здравоохранения' 2003" НТК Здравоохранение' 2003. - С. 39—47.

34. Дюк В.А. Обнаружение знании в базах данных: проблемы и перспективы (заказной доклад) // Сб. трудов 1-го Регионального молодежного форума "Информационные технологии в XXI веке", 23-24 апреля 2003 г., Днепропетровск. - С. 13-18.

35. Корыюва Л.И., Бланк М.Л., Дюк В.Л., Соколовский В.В., Бланк О.Л. .Экзогенные и эндогенные факторы, влияющие на гсмодспрсссивный эффект субтотального облучения тела у больных злокачественными лимфомами // В кн. Современные технологии в клинической медицине. - Мат. научной конференции, посвященной 85-лстию со дня основания ЦНИРРИ РФ МЗ. 2003. - С. 207.

36. Бланк М.А., Бланк О.А.. Дюк В.А. Гсмодспрсссивный эффект облучения человека // Доклады Академии Наук. - 2003, том 393, № 3. - С. 1-3.

37. Дюк В.А. Медицина как предметная область с нечеткой систсмологисй // Сб. трудов П-я Международная дистанционная научно-практическая конференция "Информационные Технологии и Кибернетика на Службе Здравоохранения' 2004" НТК. Здравоохранение' 2004. - С. 66-75.

38. Дюк В.А., Калягина Л. Современные технологии "обнаружения знаний в базах данных". -Вестник КрасГЛУ, Научно-технический журнал. Выпуск 4. - Красноярск 2004. -С. 27-33.

39. Дюк В.А. Технологии Data Mining в медико-биолошческих исследованиях. - "Ноности Ш1".№ 3.2004.-С. 15-23.

40 Дюк В.А.,. Красильников И.А, Эмануэль В.Л. Информационные технологии в клинической лабораторной диагностике // Клиническая лабораторная диагностика, № 9, 2004.-С. 16.

41. Blank M. A.. Blank О. A., and Duke V. A. The Hemodepressive Effect of Irradiation in Humans // DOKLADY BIOLOGICAL SCIENCES, Vol. 393. - 2003. - P. 1-3.

42. Duke V.A. Latent knowledge extraction by methods of local geometry: development of expert system for keen appendicitis diagnostics№roc. Int. Conf. On Informatics and Control (ICI&C 97), St. Petersburg, Russia, vol.2, p.p. 663-668.

Подписано в печать 16.03.05. Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,86. Тираж 100 экз. Заказ № 21.

Типография Издательства СПбГУ. 199061, С-Петсрбург, Средний пр., 41.

O&Z-fäß

2 2 MAP 2005

.....хч

/ L i \

Ч-11/1179

ВВЕДЕНИЕ.

1. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ ПОИСКА ЗАКОНОМЕРНОСТЕЙ В ПРЕДМЕТНОЙ ОБЛАСТИ С НЕЧЕТКОЙ СИСТЕМО ЛОГИЕЙ.

1.1. Специфика предметных областей с нечеткой системологией.

1.2. Современные подходы к "обнаружению знаний в базах данных". 1.3. Методы поиска логических закономерностей в данных. 1.4. Тестирование систем поиска логических закономерностей.

1.5. Выводы.

2. ПОИСК IF-THEN ПРАВИЛ В ДАННЫХ НА ОСНОВЕ ПРЕДСТАВЛЕНИЙ ЛОКАЛЬНОЙ ГЕОМЕТРИИ.

2.1. Используемые понятия и обозначения.

2.2. Общие положения локальной геометрии.

2.3. Построение локальной метрики как задача отбора переменных

2.4. Поиск логических закономерностей средствами линейной алгебры и интерактивной графики.

2.5. Эффект информационного структурного резонанса.

2.6. Возможности и перспективы разработанного подхода.

• 2.7. Выводы.

3. ИССЛЕДОВАНИЕ СТРУКТУРЫ МНОЖЕСТВА ЛОГИЧЕСКИХ ЗАКОНОМЕРНОСТЕЙ НА ОСНОВЕ ГЕОМЕТРИЧЕСКИХ ПРЕДСТАВЛЕНИЙ.

3.1. D '-преобразование как мера расстояний между логическими правилами

3.2. Методы визуализации данных.

3.3. Алгоритмы автоматического группирования.

3.4. Примеры отображения структуры множества логических правил . 200 Ф 3.5. Выводы.

4. АЛГОРИТМИЗАЦИЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.

4.1. Общие характеристики системы Deep Data Diver.

4.2. Работа с системой.

4.3. Подсистема поиска ассоциаций в данных.

4.4. Результаты исследования алгоритма.

4.5. Выводы.

5. ПРАКТИЧЕСКИЕ ПРИМЕРЫ. ф 5.1. Прогнозирования продолжительности жизни пациентов, 251 перенесших сердечный приступ, по данным эхокардиограммы

5.2. Прогнозирование характера ремиссии у больных бронхиальной астмой по результатам исследования плазмы крови методом лазерной корреляционной спектроскопии.

5.3. Диагностика заболеваний почек по данным ультразвукового 262 исследования.

5.4. Прогнозирование продолжительности ремиссий при алкоголизме

5.5. Исследование влияния экзогенных и эндогенных факторов на выраженность гемодепрессивного эффекта субтотального облучения тела у больных злокачественными лимфомами. ф 5.6. Выводы.

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

В самом общем виде Data Mining - это задача обработки баз данных (БД) с целью перехода к базам знаний (БЗ). В БД накапливаются и хранятся эмпирические факты из исследуемой предметной области (фактические данные, примеры экспертных заключений, элементарные высказывания с некоторой оценкой и т.п.), представленные в виде троек собъект-признак-значение признаках В БЗ заносятся сведения, выражающие закономерности структуры множества эмпирических фактов, релевантные прикладному контексту.

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

Методы Data Mining имеют много общего с методами решения упомянутых задач классификации, диагностики и распознавания образов. Но их одной из главных отличительных черт является функция интерпретации закономерностей, кладущихся в основу правил вхождения объектов в классы эквивалентности. Поэтому сегодня все большее распространение получают логические методы, например, "эмпирического предсказания" (Загоруйко Н.Г.,

1979), "индуктивного формирования понятий" (Гладун В.П., 1977; Ханти др., 1970), "построения квазиаксиоматической теории" (Финн В.К., 1991) и др.

Есть еще одна важная причина, обусловившая приоритет логических методов. Она заключается в сложной системной организации областей, составляющих предмет приложения современных информационных технологий. Эти области относятся, как правило, к надкибернетическому уровню организации систем (Boulding К.Е., 1956; Поляков А.О. и др., 2000), закономерности которого не могут быть достаточно точно описаны на языке статистических или иных аналитических математических моделей (Дж. Ван Гик, 1981). Гибкость и многообразие логических конструкций индуктивного вывода позволяют нередко добиваться успешных результатов при описании таких сложных систем.

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

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

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

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

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

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

Для реализации поставленной цели в диссертации решались следующие задачи:

1. Разработка теоретических основ, методов и алгоритмов поиска логических закономерностей в данных на базе геометрических представлений.

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

3. Разработка и сравнительное исследование программной реализации технологии поиска логических закономерностей в данных на основе геометрических представлений.

4. Решение диагностических и прогностических задач из области клинико-экспериментальных исследований с помощью разработанной методологии.

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

Положения, выносимые на защиту. 1. Сформированы теоретические основы методологии поиска логических закономерностей в данных высокой размерности на основе представлений локальной геометрии. 2. Разработана технология поиска if then правил в данных, основанная на комбинированном применении аппарата линейной алгебры и средств интерактивной графики. 3. Исследован эффект информационного структурного резонанса в многомерных данных и предложена схема активного формирования и использования этого эффекта. 4. Предложен подход, позволяющий исследовать совокупность if-then правил на основе геометрических представлений.

5. Разработан подход, позволяющий оперировать анализируемыми объектами с нечётким описанием. 6. Получены специальные формулы для формирования локального бинарного пространства, использование которых позволяет реализовывать правило обхода пропусков в многомерных данных.

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(/?N2).

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

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

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

Основные результаты диссертационной работы

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

2. Разработан комплекс тестов для испытания алгоритмов поиска логических закономерностей в данных и сформулированы основные проблемы известных подходов.

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

4. Разработаны теоретические основы технологии поиска логических закономерностей в данных на базе представлений локальной геометрии, в которых задача поиска логических закономерностей в данных сводится к конструированию локальных контекстно-зависимых метрик для объектов выборки.

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

6. Дано определение информационного структурного резонанса и предложена схема активного формирования этого резонанса в локальном пространстве признаков.

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

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

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

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

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

12. Разработана программная реализация (система Deep Data Diver), в которой автоматизирована технология интерактивного поиска логических закономерностей в данных на основе представлений локальной геометрии.

13. Проведено сравнительное исследование эффективности разработанной методологии на ряде практических примеров из области клинико-экспериментальных исследований. Система Deep Data Diver продемонстрировала существенные преимущества перед другими алгоритмами.

Разработанная в диссертации методология поиска логических закономерностей в данных на основе представлений локальной геометрии отнесена к важнейшим результатам Российской академии наук в 1998 году и за период с 1997 по 2001 г.

ЗАКЛЮЧЕНИЕ

1. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. -М.: Статистика, 1974.

2. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Основы моделирования и первичная обработка данных. М.: Финансы и статистика, 1983.

3. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Статистическое оценивание зависимостей. М.: Финансы и статистика, 1985.

4. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерности. -М.: Статистика, 1989.

5. Аккерман Р.И., Далецкий К.П., Дюк В.А., Ефимов Ю.С., Полянкин Г.А. Диагностирование состояния колец ЦПГ ДГ14-10 виброакустическим методом//Морскойтранспорт, 7(555), 1983.-С. 12-16.

6. Аккерман Р.И., Далецкий К.П., Дюк В.А. Виброакустическое диагностирование топливной аппаратуры дизеля. Двигателестроение, 1984, № 2. С. 23-26.

7. Александров В.В., Алексеев А.И., Горский Н.Д. Анализ данных на ЭВМ (на примере системы СИТО). М.: Финансы и статистика, 1990.

8. Александров В. В., Лачинов В.И., Поляков А.О. Рекурсивная алгоритмизация кривой, заполняющей многомерный интервал // Изв. АН СССР: Техн. кибернетика, 1978, № 1. С. 192-197.

9. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях: Монография. Тюмень: Издательство Тюменского государственного университета, 2000.

10. Алтунин А.Е., Чуклеев С.Н., Семухин М.В., Крел Л.Д. Методическое руководство по технологическим расчетам сложных систем газодобычи при неточных параметрах, Тюмень, 1984.

11. Альтшулер С.А., Козырев Б.М. Электронный парамагнитный резонанс. — М.: Наука, 1972.

12. Андрианов И.В., Маневич Л.И. Асимптология: идеи, методы, результаты. М: Аслан, 1994.

13. Аркадьев А. Г. Браверманн Э.М. Обучение машины классификации объектов. -М.: Наука, 1971.

14. Барабаш Б.А. Минимизация описания в задачах автоматического распознавания образов // Изв. АН СССР. Техн. кибернетика, № 3, 1964.

15. Беллман Р., Заде JI. Принятие решений в расплывчатых условиях // В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976.

16. Блажис А.К., Дюк В.А. Телемедицина. СПб: "СпецЛит", 2000.

17. Бланк М.А., Бланк О.А., Дюк В.А. Гемодепрессивный эффект облучения человека // Доклады Академии Наук. 2003, том 393, № 3. - С. 1-3

18. Бланк М. А., Бланк О. А. Мониторирование основных показателей у онкологических больных // Вестник РАМН, №8. 2000. - С. 33-35.

19. Блишун А.Ф. Сравнительный анализ методов измерения нечеткости //Изв. АН СССР. Техн. кибернетика. 1988. N 5.- С. 152-175.

20. Блишун А.Ф., Знатнов С.Ю. Обоснование операций теории нечетких множеств. В кн.: Нетрадиционные модели и системы с нечеткими знаниями. -М.: Энергоатомиздат, 1991. С. 21-33.

21. Бодякин В.И. "Каждый выбирает сам как ему поступать и это его право священно" http://nicst.ipu.rssi.ru/stran/bod/every.htm.

22. Бонгард М.М. Проблема узнавания. М.: Наука, 1967.

23. Боннер Р.Б. Некоторые методы классификации // Автоматический анализ изображений. -М.: Мир, 1969. С. 205-234.

24. Борисов А.Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей. Примеры использования. Рига: Зинатне, 1990.

25. Браверманн Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. — М.: Наука, 1983.

26. Будущее искусственного интеллекта // Под ред. К.Е. Левитина и Д.А. Поспелова. М.: Наука, 1991.

27. Букатова И. Л. Эволюционное моделирование и его приложения М.: Наука, 1979.

28. Варакин Л.Е. Системы связи с шумоподобными сигналами. М.: Радио и связь, 1985.

29. Вассерман Л.И., Дюк В.А., Иовлев Б.В., Червинская К.Р. Психологическая диагностика и новые информационные технологии. СПб: "СЛП", 1997.

30. Вейль Г. Математическое мышление. -М., 1989.

31. Вейр Б. Анализ генетических данных: Пер. с англ. М.: Мир, 1995.

32. Вертхейм Г. Эффект Мессбауэра. М.: Мир, 1966.

33. Викторов В.А. О развитии медико-технической науки // Журнал "Вестник РАМН" N5, 2001 г.-С. 3-7.

34. Воробьев В.М., Дюк В.А., Иовлев Б.В., Сенопальников Е.В., Чигирев В.А. Разработка автоматизированной системы массового обследования в профилактических целях // Журнал неврологии и психиатрии им.

35. С.С. Корсакова. JL: Психоневрологии, ин-т им. В.М. Бехтерева, 1981.• С. 137-141.

36. Воробьев В.М., Дюк В.А. Адаптивные свойства личности и принципы их машинной диагностики//Тез. докл. VI Всесоюзн. Съезда психологов. М.: 1983. - С. 223-224.

37. Воробьев В.М., Буров В.В., Дюк В.А. Опыт медико-психологического обследования некоторых контингентов молодежи//Здравоохранение РСФСР, 1982, №2.-С. 37-39.

38. Г.С.Осипов. Приобретение знаний интеллектуальными системами. М.: Наука. Физматлит, 1997.

39. Генкин А.А. Новая информационная технология анализа медицинских данных (программный комплекс ОМИКС). СПб: Политехника, 1999.

40. Гик Дж., ван. Прикладная общая теория систем. М.: Мир, 1981.

41. Главные компоненты временных рядов: метод "Гусеница" (Под ред. Д.Л.Данилова и А.А.Жиглявского). Санкт-Петербург Государственный университет, 1997.

42. Гласс Дж., Стэнли Дж. Статистические методы в педагогике и психологии. -М.: Прогресс, 1976.

43. Горский Н. Д. Рекурсивный метод отображения многомерного ф пространства при решении задач хранения и обработки данных вавтоматизированных системах научных исследований. — Автореф. на соиск. уч. степ. канд. техн. наук. Л., 1981.

44. Десять лет спустя (интервью с Д. Мичи) // Будущее искусственного интеллекта. М.: Радио и связь. 1991. - С. 213-216.

45. Диксон Р.К., Широкополосные системы: пер. с англ./Под ред.

46. B.И.Журавлева. М., Связь, 1979 .

47. Дрейпер Н., Смит Г. Прикладной регрессионый анализ. Т. 1. М.: Машиностроение, 1988.

48. Дрейпер Н., Смит Г., Прикладной регрессионный анализ. Т.2. М.: Финансы и статистика, 1986.

49. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

50. Дэйвисон М. Многомерное шкалирование: Методы наглядного представления данных. -М.: Финансы и статистика, 1988.

51. Дюк В.А. Data Mining интеллектуальный анализ данных/ZByte (Россия), №9, 1999.-С. 18-24.

52. Дюк В.А. Data Mining технология золотых воротничков // Образование и карьера в Санкт-Петербурге, № 2, 2000. - С. 42-45.

53. Дюк В.А.Дюк А.В., Технологии Data Mining в социальных исследованиях/Информатика Исследования и Инновации. Выпуск 3, Межвузовский сборник научных трудов. - СПб: РГПУ им. А.И. Герцена, 1999. -С. 171-172.

54. Дюк В.А. Ключевые вопросы психологической диагностики//Тр. Межд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков, 19-23 июня 2000 г.). СПб.: Изд-во СПбГТУ, 2000.1. C. 399-403.

55. Дюк В.А. Компьютерная психодиагностика. СПб: "Братство", 1994.

56. Дюк В.А. Новые информационные технологии в психодиагностике// Тр. V Межд. конф. "Региональная информатика-96", СПб, 1996. С. 261-267.

57. Дюк В.А. Новый класс метрик//Тез. докл. международн. конф. по бионическому моделированию. "Биомод-92", СПб, 1992. С. 231-233.

58. Дюк В.А. Обнаружение знаний в базах данных: проблемы и перспективы (заказной доклад) // Сб. трудов 1-го Регионального молодежного форума "Информационные технологии в XXI веке", 23-24 апреля 2003 г., Днепропетровск. С. 13-18.

59. Дюк В.А. Обнаружение знаний в базах данных: проблемы и перспективы // Мат. конф. "Инфокоммуникации. Подготовка кадров и кадровая политика", Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А.Бонч-Бруевича. 2003. 26-28.

60. Дюк В.А. Обработка данных на ПК в примерах. СПб: Питер, 1997.

61. Дюк В.А. Осколки знаний// Экспресс-Электроника, 2002, № 6. С. 60-65.

62. Дкж В.А. От данных к знаниям новые возможности обработки баз данных//Тр. Межд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков, 19-23 июня 2000 г.). - СПб.: Изд-во СПбГТУ, 2000. - С. 438-440.

63. Дкж В.А. Поиск сложных непериодических шаблонов в последовательностях числе и символов методами локальной геометрии // Тр. СПИИРАН. 2002. - Т.2, № 1. - С. 263-268.

64. Дкж В.А. Проблемы применения формальных методов формирования метапонятий при концептуальном анализе знаний//Методы и средства принятия решений. Системы поддержки процессов проектирования на основе знаний. -Рига: Рижск. техн. ун~т, 1991. С. 90-95.

65. Дюк В.А. Разработка базы знаний экспертной системы для прогнозирования продолжительности ремиссий при алкоголизме // Материалы научно-практического семинара "Телемедицина становление и развитие", Санкт-Петербург, 2000. - С. 64-75.

66. Дюк В.А. Современные информационные технологии в психодиагностике: экстенсиональный подход альтернатива традиционной методологии//Тр. IV Межд. конф. "Региональная информатика-95", СПб, 1995. - С. 175-176.

67. Дюк В.А. Сравнение структуры интеллекта "физиков" и "лириков"// Тр. Межд. научн. конф. "Интеллектуальные системы и информационные технологии управления (Псков, 19-23 июня 2000 г.). СПб.: Изд-во СПбГТУ, 2000. - С. 403-406.

68. Дюк В.А. Тестирование систем для поиска if-then правил в данных // Материалы VIII Санкт-Петербургской международной конференции "Региональная информатика-2002", Часть 2, 2002. С. 42.

69. Дюк В.А. Технологии Data Mining в медико-биологических исследованиях. "Новости ИИ", № 3, 2004. - С. 15-23.

70. Дюк В.А. Формирование знаний в системах искусственного интеллекта: геометрический подход // Вестник академии технического творчества. СПб.: изд-во СПбГТУ, 1996, № 2. - С. 46-67.

71. Дюк В.А. Формирование знаний в системах искусственного интеллекта: геометрический подход (ч. 4, глава 2)/В кн. Телемедицина. Новые информационные технологии на пороге XXI века. СПб: "Анатолия", 1998. С. 367-389.

72. Дюк В.А., Воробьев В.М. Совершенствование автоматизированных методов обработки психологических измерений//Тез. докл. Всесоюзн. конф. по инженерной психологии. — JI.: ЛГУ им. А.А. Жданова, 1984. С. 58-60.

73. Дюк В.А., Ельяшевич A.M., Коваленко А.А., Петрова Е.Ю., Рейнин Г.Р., Филимонов А.В. О разработке типологического теста с применением методов распознавания образов//Соционические чтения, № 7(28), 1999. С. 1-2.

74. Дюк В.А., Калягина JI. Современные технологии "обнаружения знаний в базах данных". Вестник КрасГАУ, Научно-технический журнал, Выпуск 4. -Красноярск 2004.79. С. 27-33.

75. Дюк В.А., Мирошников А.И. Эволюция Statgraphics. Мир ПК, 1995, № 12. - С. 32-34.

76. Дюк В.А., Русаков Ю.М. Телемедицина // Экспресс-Электроника, № 9, 2002. С. 52-57.

77. Дюк В.А., Самойленко А.П. Data Mining: учебный курс. Изд-во "Питер", 2001.

78. Дюк В.А.,. Красильников И.А, Эмануэль B.JI. Информационные технологии в клинической лабораторной диагностике // Клиническая лабораторная диагностика, № 9, 2004. С. 16.

79. Дюк В.А., Эммануэль B.JI. Информационные технологии в медико-биологических исследованиях. Изд-во: "Питер", 2003.

80. Елисеева И.И., Рукавишников В.О. Группировка, корреляция, распознавание образов (Статистические методы классификации и измерения связи).-М.: Статистика, 1977.

81. Енюков И.С. Методы, алгоритмы, программы многомерного статистического анализа: Пакет 1111С А. -М.: Финансы и статистика, 1986.

82. Житков Г.Н. Некоторые методы автоматической классификации //Структурные методы опознавания и автоматическое чтение. М.: ВИНИТИ, 1970.-С. 68-85.

83. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.

84. Загоруйко Н.Г. Методика оценки информационной эффективности независимых параметров речевого сигнала // Тр. ИМ Сиб. отд. АН СССР: Вычислительные системы, 1964, вып. 10. С. 77-89.

85. Загоруйко Н.Г., Ёлкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985.

86. Загоруйко Н.Г. К вопросу об определении понятия закономерность. -Вычислительные системы, 1979, вып. 79. С. 3-6.

87. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений. М: Мир, 1976.

88. Злоба Е., Яцкив И. Статистические методы восстановления пропущенных данных // Computer Modelling & New Technologies, 2002, v. 6, N.l. P. 51-61.

89. Ивахненко А.Г. Долгосрочное прогнозирование и управление сложными системами.//К.: "Техника", 1975.

90. ЮО.Ивахненко А.Г. Самообучающиеся системы распознавания и автоматического регулирования-Киев: Техника, 1969.

91. Искусственный интеллект. В 3-х кн. Кн.1. Системы общения и экспертные системы: Справочник // Под ред. Э.В. Попова. - М.: Радио и связь, 1990.

92. Искусственный интеллект. В 3-х кн. Кн.2. Модели и методы: Справочник // Под ред. Д.А. Поспелова. - М.: Радио и связь, 1990 - 304 с.

93. Искусственный интеллект. В 3-х кн. Кн.З. Программные и аппаратные средства: Справочник // Под ред. В.Н. Захарова, В.Ф. Хорошевского. - М.: Радио и связь, 1990.

94. Капица С.П., Курдюмов С.П., Малинецкий Г.Г. Синергетика и прогнозы будущего. -М: Наука, 1997.

95. Кендалл М. Методы ранговой корреляции. -М.: Статистика, 1974. Юб.Кендалл М., Стъюарт А., Статистические выводы и связи. М.: Наука, 1973.

96. Киевский институт кибернетики, домашняя страничка разработчиков МГУА http://inf.kiev.ua/GMDH-home/.

97. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы, № 4, 1997, С. 41-44.

98. Клайн М. Математика. Поиск истины. -М.: Мир, 1988.

99. Классификация и кластер // Под ред. Дж. Вэн Райзин. М.: Мир, 1980.

100. П.Клейн Ф. Лекции о развитии математики в XX столетии. М.-Л., 1937, ч. 1.

101. Койре А. Очерки истории философской мысли. Москва, 1985.

102. Колесов В.В. Отражение русского менталитета в слове // Человек в зеркале наук. Л.: ЛГУ, 1991. С. 106-124.

103. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.

104. Кофман А., Хил Алуха X. Введение теории нечетких множеств в управлении предприятиями. Минск: Вышэйшая школа, 1992.

105. Кречетов Н. Продукты для интеллектуального анализа данных. Рынок программных средств, № 14-15, 1997. - С. 32-39.

106. Крылов В.Ю. Метод многомерной геометризации психологических данных. Системный подход в математической психологии // Принцип системности в психологических исследованиях. М.: Наука, 1990. - С. 33-48.

107. Кузнецов А.С. Методы поиска оптимальных групп признаков при статистическом распознавании образов Л.: ВИКИ им. А. Ф. Можайского, 1982.-С. 14-23.

108. Кучин Б.Л., Алтунин А.Е. Информационные системы управления объектами газоснабжения. М: Недра, 1989.

109. Лбов Г. С. Выбор эффективной системы зависимых признаков // Труды Сиб. отд. АН СССР: Вычислительные системы.- Новосибирск, 1965, вып. 19. -С. 87-101.

110. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. — Новосибирск: Наука, 1981.

111. Лбов Г.С., Котюков В.И., Манохин А.Н. Об одном алгоритме распознавания в пространстве разнотипных признаков. Вычислительные системы, 1973, вып. 55. - С. 98-107.

112. Литтл Р. Дж. А., Рубин Д.Б. Статистический анализ данных с пропусками. -М.: Финансы и статистика, 1991.

113. Лоули Д., Максвелл А. Факторный анализ как статистический метод. М.: Мир, 1967.

114. Малинецкий Г.Г. Нелинейная динамика и историческая механика. // Общественные науки и современность, 1997, N2. С. 99-111.

115. Малинецкий Г.Г. Синергетика. Король умер. Да здравствует король! -http://sky.kuban.ru/socioetno/iphrRAS/~mifs/index.htm.

116. Малинецкий Г.Г. "Историческая механика" и нелинейная динамика // Изв. ВУЗов, сер. Прикладная нелинейная динамика, 1997, т.5, N4. С. 76-88.

117. Манохин А.Н. Методы прогнозирования перспективности объектов, основанные на логических решающих функциях. Дисс. на соиск. учен. степ, канд. тех. наук. Новосибирск, Ин-т математики СО АН СССР, 1978.

118. Математические методы для анализа последовательностей ДНК: Пер. с англ. // Под ред. М.С. Уотермена М.: Мир, 1999.

119. Математические предвестники единства (Беседа члена-корреспондента Академии наук СССР С.П. Курдюмова с К. Левитиным) // "ЗС" № 10, 11/1988.

120. Миркин Б.Г. Анализ качественных признаков и структур. М.: Статистика, 1980.

121. Налимов В.В. Теория эксперимента. М.: Наука, 1971.

122. Нариньяни А.С. Недоопределенные модели и операции с недоопределенными значениями. Препринт ВЦ СО АН СССР, N 400, 1982.

123. Нариньяни А. С. Недоопределённость в системах представления и обработки знаний//Изв. АН СССР. Техн.кибернетика. 1986. №5. С.3-28.

124. Нечёткие множества в моделях управления и искусственного интеллекта // Под ред. Поспелова Д.А. М.: Наука, 1986.

125. Никифоров A.M., Фазылов Ш.Х. Методы и алгоритмы преобразования типов признаков в задачах анализа данных. Ташкент: Фан, 1988.

126. Онтология и эпистемология синергетики. М.: Институт философии РАН, 1997.

127. Орлов А.И. // Заводская лаборатория. 1990. Т.56. № 3. С.76-83

128. Орлов А.И. // Заводская лаборатория. 1995. Т.61. № 3. С.43-52.

129. Орлов А.И. Задачи оптимизации и нечеткие переменные. М.: Знание, 1980.

130. Орлов А.И. Общий взгляд на статистику объектов нечисловой природы: Анализ нечисловой информации в социологических исследованиях М.: Наука, 1985.

131. Паскаль Б. О геометрическом уме и об искусстве убеждать // Приложение к кн.: Стрельцова "Г.Я. Паскаль и европейская культура. Москва, 1994".

132. Поляков А.О. Технология интеллектуальных систем: Учебное пособие. СПб: СПбГТУ, 1995.

133. Попечителев Е. П., Романов С.В. Анализ числовых таблиц в биотехнических системах обработки экспериментальных данных. Л.: Наука, 1987.

134. Попов Э.В. Экспертные системы,- М: Наука, 1987.

135. Поппер К. Логика и рост научного знания. М.: Прогресс, 1983.

136. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии: Сер. Академические чтения. -М.: Наука, 1988.

137. Поспелов Г.С., Ириков В.А. Системно-программное планирование. М.: Советское радио, 1975.

138. Поспелов Д.А. Логико-лингвистические модели в системахуправления-М.: Энергоиздат, 1981.

139. Поспелов Д.А. Моделирование рассуждений-М.: Радио и связь, 1989.

140. Поспелов Д.А. Моделирование человеческих рассуждений в интеллектуальных системах: Лекции Всесоюзной школы по основным проблемам искусственного интеллекта и интеллектуальным системам. Ч. 1. -Тверь: Центр программных систем, 1990.

141. Поспелов Д.А. Ситуационное управление: теория и практика М. Наука, 1986.

142. Поспелов Д.А. Искусственный интеллект: фантазии и реальность // "Наука и жизнь", 1995, № 6.

143. Представление и использование знаний // Под ред. X. Уэно, М. Исидзука. -М.: Мир, 1989.

144. Проблемы представления и обработки не полностью определённых знаний // Под ред. Нариньяни А. С. М.: РосНИИ ИИ, 1996.

145. Прокис Дж. Цифровая связь. М.: Радио и связь, 2000.

146. Пфанцагль И. Теория измерений. М.: Мир, 1976.

147. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика-М.: Мир, 1980.

148. Ростовцев П.С., Костин B.C., Олех А.Л. Множественные сравнения в детерминационном и типологическом анализе. // Анализ и моделирование экономических процессов переходного периода в России. Выпуск 3. — Новосибирск, ИЭиОПП СО РАН, 1998. С. 209-222.

149. Ростовцев П.С., Костин B.C., Олех А.Л. Множественные сравнения в таблицах для неальтернативных вопросов // Анализ и моделирование экономических процессов переходного периода в России. Выпуск 4.-Новосибирск, ИЭиОПП СО РАН, 1999. С. 148-164.

150. Русско-русский современный толковый словарь изд. "Большая Советская Энциклопедия", OCR Палек, 1998.

151. Рыбников К.А. Комбинаторный анализ // Энциклопедия кибернетики. -Главная редакция Украинской советской энциклопедии, т. 1, 1975. С. 471-475.

152. Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. -М.: Диалог-МГУ, 1998.

153. Григорьев С.Г., Перфилов A.M., Левандовский В.В., Юнкеров В.И. STATGRAPHICS на персональном компьютере. Санкт Петербург, 1992.

154. Соложенцев Е.Д., Карасев В.В., Соложенцев Е.В. Логико-вероятностные модели риска в банках, бизнесе и качестве. СПб: Наука, 1999.

155. Справочник по прикладной статистике. В 2-х т. Т. 2 // Под ред. Э. Ллойда, У. Ледермана, С.А. Айвазяна, Ю.Н. Тюрина. М.: Финансы и статистика. -1990.

156. Статистические методы анализа информации в социологических исследованиях // под ред. Осипова Г. В. -М.: Наука, 1979.

157. Суппес П., Зинес Дж. Основы теории измерений. В кн.: Психологические измерения. - М.: Мир, 1967. - С. 9-110.

158. Тараканов А.О. Математические модели ключевых молекулярно-биологических механизмов обработки информации. СПб: Изд-во СПИИРАН, 1998.

159. Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ. М.: Финансы и статистика, 1990.

160. Терехина А.Ю. Анализ данных методами многомерного шкалирования. -М.: Наука, 1986.

161. Трухаев Р.И. Модели принятия решений в условиях неопределенности. — М.: Наука, 1981.

162. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

163. Тьюки Дж. Анализ результатов наблюдений. Разведочный анализ. — М.: Мир, 1981.

164. Фогель Л., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. -М.: Мир, 1969.

165. Франселла Ф., Баннистер Д. Новый метод исследования личности. М.: Прогресс, 1987.

166. Хитрова А. Н., Дифференциальная диагностика кист почечного синуса и гидронефрозов методом комплексного ультразвукового обследования. Диссертация на соискание ученой степени кандидата медицинских наук. Москва, 1996.

167. Черепанов В.И. Резонансные методы исследования вещества. // Соросовский Образовательный журнал, №9, 1997.

168. Шапошникова В.И., Нарциссов Р.П., Барбараш Н.А. Многолетние и годовые циклы // Хронобиология и хрономедицина / Под ред. Комарова Ф.И., Раппопорта С.И., 2 е изд. М.: Триада-Х, 2000. - С.115-139

169. Шахмаев Н.М. Физика. Ч. 2: Колебания и волны. Оптика. Строение атома. -М.: Высш. шк., 1977.

170. Шпенглер О. Закат Европы, 2 т. Москва, 1993. - С. 487.

171. Электрические эффекты в радиоспектроскопии // Под ред. М.Ф. Дейгена. -М.: Наука, 1981.

172. Яглом И.М. Почему высшую математику открыли одновременно Ньютон и Лейбниц? // Число и мысль. Вып. 6. М; 1983. - С. 99-125.

173. Яглом И.М. Различие путей творческого поиска (создание векторного исчисления Г. Грассманом и У. Гамильтоном) // В кн. Человек в зеркале наук. Л.: ЛГУ, 1991.-С. 130-146.

174. Agraval R., Imielinski Т., Swami A. Mining Association Rules between Sets of Items in Very Large Databases. ACM SIGMOD Conference Proceedings, 1993. - P 207-216.

175. Backer E., Shipper J.A. On the max-min approach for feature ordering and selection//Proc. Seminar on Pattern Recognition, Liege, Nov., 1977.

176. BakP., Tang C., Weisenfeld K. Self-organized criticality. Phys. Rev. A, 1988, v.38, N1. P. 364-374.

177. Banzhaf W., Nordin P., Keller R. E., Francone F.D. Genetic programming. An Introduction. // Morgan Kaufmann Publishers, Inc. San Francisco, California, 1998.

178. Bellachhok L, Malinetskii G. Tricks of Jokers on one-dimensional maps. Proc. 5 Int. Specialist Workshop Nonlinear Dynamics of Electronic Systems, Moscow, 1997.-P. 40-45.

179. Bezdek J.C. Pattern recognition with fuzzy objective function algorithms. New York: Plenum Press, 1981.

180. Blank M. A., Blank O. A., Duke V.A. The Hemodepressive Effect of Irradiation in Humans // Doklady biological sciences, v. 393. 2003. - P. 1-3.

181. Bonissone P.P., Tong R.M. Editorial: reasoning with uncertainty in expert systems."Int. J. Man-Mach. Stad.", 1985, N3. P. 241-250.

182. Boulding К. E. General Systems Theory The Skeleton of Science // Management Science, 2, 1956.

183. Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. -1984.

184. Bronzino J.D. The Biomedical Engineering Handbook. Second Edition, IEEE Press, 2000.

185. Carrol J.D., Chang J.J. Analysis of Individual Differences in Multidimensional Scaling via an Generalization of Ecart-Young Decomposition // Psychometrica,1970, v. 35, N 5. P. 283-319.

186. Chang C. Y. Dinamic programming as applied to feature selection in pattern recognition systems/ЛЕЕЕ Trans., v. SMC-3, 1973. P. 166-171.

187. Charu C. Aggarwal. Towards Long Pattern Generation in Dense Databases. — SIGKDD Explorations, v. 3, Issue 1, 2001. P. 20-26.

188. Cover T. The best two independent measurement are not the two best // IEEE Trans, v. SMC-4, 1974.-P. 116-117.

189. Cover T, Hart P. Nearest neighbour pattern classification // IEEE Trans. Inform. Theory, v. IT-13, 1967. P. 21-27.

190. Devroye L. Some properties of the k-nearest neighbour rule // Proc. 5th Conf. Pattern Recogn. Miami Beach, Fla, v. 1-2, 1980. - P. 103-105.

191. Doyle, P. The use of Automatic Interaction Detection and similar search procedures. Operational Research Quarterly, 24. 1973. - P. 465-466.

192. Fayyad U.M, Piatetsky-Shapiro G, Smyth P, Uthrsamy R. Advances in knowledge discovery and data mining. -Menlo Park, California: AAAI Press, 1996.

193. Ganti V, Gehrke J, Ramakrisnan R. Mining Very Large Databases. IEEE Computer, August 1999. P. 38-45

194. Glass G. V. Note on rank-biserial correlation//Educational and Psychological Measurement, 26, 1966. P. 332-337.

195. Hoerl, A. E., Kennard, R. W. Ridge regression: Applications to nonorthogonal problems. Technometrics, 12, 1970. - P. 69-82.

196. Hunt E.B., Marin J., Stone P.J. Experiments in Induction. New York: Academic Press, 1966.

197. Kan, G., Visser, C., Kooler, J., & Dunning, A. Short and long term predictive value of wall motion score in acute myocardial infarction. British Heart Journal, 56, 1986.-P. 422-427

198. Kittler J. A. Feature set search algorithms // Proc. Conf. om Pattern Recogn. and Signal Processing Paris, France, 25 June - 4 July, 1978. - P. 41-60

199. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? -Tandem Computers Inc., 1996.

200. Koza, J.R. Hierarchical genetic algorithms operating on populations of computer programs. //Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, volume 1, Morgan Kaufmann, San Francisco, CA, 1989. P. 768-774.

201. Lewis P. M. The characteristics selection problem in recognition systems // IRE Trans, v. IT-8, 1962, N2.

202. Lim, T.S, Loh, W.Y., Shih, Y.S. An emprical comparison of decision trees and other classification methods. Technical Report 979, Department of Statistics, University of Winconsin, Madison. 1997.

203. Loh, W.Y, Shih, Y.S. Split selection methods for classification trees. Statistica Sinica, 7.-1997. P. 815-840.

204. Loh, W.Y, Vanichestakul, N. Tree-structured classification via generalized discriminant analysis (with discussion). Journal of the American Statistical Association, 83. 1988. - P. 715-728.

205. Mamdani E.H, Efstathion H.J. Higher-order logics for handling uncertainty in expert systems. "Int. J. Man-Mach. Stud.", 1985, N3. -P.243-259.

206. Marill T, Green D. M. On the effectivness of receptors in recognition systems//IEEE Trans, v. IT 9, 1963. - P. 11-17.

207. Michael M, Lin W.C. Experimental study of information measures and inter-intra class distance rations of features selection and ordering // IEEE Trans, v. SMC -3, 1973.-P. 172-181.

208. Narendra P.M., Fukunaga K.A. A branch and bound algorithm for feature subset selection/ZProc. Cybernetic and Society Inf. Conf. Washington, D.C, 1976.

209. Osgood Ch. E, Susi G.E, Tannenbaum P.N. The Measurement of Meaning. Urbana: 111, press, 1957.

210. Pettis K.W, Bailey T.A, Jain A.K, Dubes R.C. An intrinsic dimensionality estimator from nearneighbour information. // IEEE Trans. Pattern Anal, and Mach. Intel, v. 1, N 1, 1979. P. 25-37.

211. Poly Analyst Tutorials. Megaputer Intelligence Inc., http://www.megaputer.com.

212. Quinlan J.R. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufinann, 1993.

213. Quinlan J.R. Generating production rules from decision trees // In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87).

214. Morgan Kaufinann, 1987. P. 304-307.

215. Quinlan J.R. Induction of decision trees // Machine Learning. 1986. - 1. - P. 81-106.

216. Quinlan J.R. Simplifying decision trees // International Journal of Man-Machine Studies. 1987. - 27. - P. 221-234.

217. Quinlan, J.R., Cameron-Jones, R.M. Oversearching and layered search in empirical learning. Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal (Vol. 2). Morgan Kaufinan. 1995. - P. 1019-1024.

218. Saito T. The problem of the additive Constante and eigenvalues in metric multidimsional scaling/ZPsychometrika, v. 43, N 2, 1978.

219. Salzberg, S. Exemplar-based learning: Theory and implementation (Technical Report TR-10-88). Harvard University, Center for Research in Computing Technology, Aiken Computation Laboratory, 1988.

220. Sammon J.W. A nonlinear mapping for Data Structure Analysis//IEEE Trans. Comput. v. C-18, N 5, 1969. - P. 401-409.

221. Schwan H.P. Biomedical Engineering. A 20th Century Interscience. Journal of International Federation for Medical & Biological Engineers, v. 37, 1999.

222. Torgerson W.S. Multidimensional Scaling. Theory and Method // Psychometrika, v. 17, № 4, 1952.

223. Toussaint G.T. Note on optimal selection of independed binary features for pattern recognition // IEEE Trans., v. IT-17, 1971. P. 618-620.

224. Tukey J.W. The Future of Data Analysis, Ann. Math. Stat. 33, 1, 1962. P. 1-67.

225. Wolberg W.H., Street W.N., Heisey D.M., Mangasarian O.L. Computer-derived nuclear "grade" and breast cancer prognosis. Analytical and Quantitative Cytology and Histology, Vol. 17, 1995. P. 257-264.

226. XELOPES Library. Prudential Systems. Software GmbH. - Chemnitz, 2002.

227. Zadeh L.A. Personal Internet homepage. http://http.cs.berkeley.edu/People /Faculty /Homepages/zadeh.html.

228. Zadeh L.A. Fuzzy sets as a basis for a theory of possibility // Fuzzy Sets and Systems. 1978. - Vol.1, №1.