Клуб выпускников МГУ: ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ МЕДИЦИНСКИХ БАЗ ДАННЫХ

Введение
Что такое knowledge discovery in databases?
KDD и OLAP
Краткая история KDD
KDD как синтез разных областей знания
Типы задач и виды моделей
От сырых данных к полезным решениям
Верификация и оценка полезности моделей
Обзор алгоритмов data mining
Кластеризация
Ассоциация, или метод корзины покупателя
Деревья решений
Анализ с избирательным действием
Сети уверенности
Метод ближайших соседей
Нейронные сети
Нечеткая логика
Генетические алгоритмы
Регрессионные методы
Эволюционное программирование
Визуализация
Инструментальные средства KDD
KDD за работой
Заключение
Литература
Для первоначального ознакомления
Для углубленного изучения

ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ МЕДИЦИНСКИХ БАЗ ДАННЫХ

«Никакое человеческое исследование не может почитаться истинной наукой, если оно не изложено математическими способами выражения»

Эта глава посвящена проблеме обнаружения нового знания в хранилищах медицинских данных - knowledge discovery in databases (KDD, дословно - «обнаружение знаний в базах данных») - и основному этапу этого процесса - data mining (исследование данных или, дословно, «разработка данных»). После применения традиционных методов анализа, будь то анализ хода течения болезни и предполагаемого лечения или анализ эффективности работы медицинского учреждения, перед практическими врачами встает задача по дальнейшему увеличению эффективности лечения каждого пациента, а перед менеджерами - увеличения эффективности работы медицинского учреждения. Методы KDD, являющиеся, по сути, усилителем человеческой мысли, переводят процесс поиска нового знания на качественно иной уровень и могут облегчить и дополнить традиционные методы анализа человеком.

Введение

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

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

Первый этап - сбор; второй - обработка информации; третий - анализ информации (оценка и диагностика состояния организма и внешней среды); четвертый - выбор оптимального пути лечения или профилактического мероприятия и предсказание возможного риска при их проведении; наконец, пятый этап - это непосредственно проведение лечения, профилактического мероприятия и т.п. После чего цикл замыкается: начинается вновь сбор информации. В последние годы большое внимание было уделено автоматизации первых двух этапов медицинской деятельности - сбору и обработке информации (например, Амосов и др., 1975; Медицинская и научная информатика, 1987; Информатика в эпидемиологии, 1990). Мы же рассмотрим возможности применения компьютерных технологий для автоматизации собственно анализа уже накопленной медицинской информации - того самого процесса, который с древнейших пор и до самого недавнего времени полностью оставался прерогативой человека.

Первые системы накопления медицинской информации, по-видимому, появились при возникновении классового общества и рабовладельческих государств примерно 4-5 тысяч лет тому назад. В этот момент появляются первые искусственные накопители медицинской информации - библиотеки папирусов Древнего царства в Египте, плиток клинописей Месопотамии, хранящих советы и законы по врачеванию. С тех пор кардинальнейшим образом изменились и системы сбора, и объем накопленной информации. В конце XIX века появились первые баллисто-кардиограммы и электрокардиаграммы, получили развитие регистрация пульса и сердечного толчка, дыхательных движений грудной клетки. С началом XX века связано появление рентгенографии, фонокардиографии и поликардиографии. Дальнейший рост методов исследований и порождаемых ими объемов информации, особенно с появлением компьютерной техники, превзошел все самые смелые ожидания. Поистине гигантский объем первичной информации порождают трехмерные томографические исследования. Существующая система сбора информации приводит к избыточности данных, хотя в то же время и не обеспечивает максимального объема диагностической информации. Бурный рост объема накопленной информации привел к возникновению и распространению компьютерных систем сбора и первичной обработки информации.

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

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

Возникшие в самом конце XX века методы интеллектуального анализа данных, методы автоматизированного извлечения знаний непосредственно из исходных, или "сырых", данных, возможно, отчасти способны снять остроту этой проблемы. Эти методы уже активно используются при анализе рынка, маркетинге, прогнозе фондовых котировок и других бизнес-приложениях, также задыхающихся в тисках обширнейшего моря информации; их использованию посвящена монографическая литература (Goldberg, 1989; Bigus, 1996; Berry and Linoff, 1997; Фролов, 2000). Однако в медицинских исследованиях методы интеллектуальной поддержки анализа единичны и еще не нашли широкого применения. Отчасти это обстоятельство связано с отсутствием систематического изложения и популяризации этих методов в медицинской литературе. Настоящая глава призвана хотя бы отчасти исправить это положение.

Однако как соотносятся анализ данных Человеком и бездушной Машиной? На что мы можем рассчитывать в будущем - в самом ближайшей и в несколько отдаленной перспективе, привлекая методы машинного исследования для творческого анализа данных? Прогнозировать будущее - неблагодарное занятие, но чтобы составить самое общее впечатление о возможностях методов автоматизированного извлечения знаний из данных, нам надо понять, а что может человек, количественно оценить потенциальные возможности человеческого мозга при анализе информации.

По оценке Дж. Неймана объем памяти мозга человека (число нейронов) составляет ~10²⁰ бит. Хотя, строго говоря, однозначно не доказано, что искусственные нейронные сети (они будут подробнее рассмотрены ниже), созданные как модель нервной ткани и высшей нервной деятельности, верно отражают работу мозга человека, мы воспользуемся этим предположением для грубой оценки, вполне достаточной для наших целей. Воспользуемся также физической аналогией, конкретной физической реализацией нейросетевой системы, впервые предложенной в работах Дж. Хопфильда (Hopfield, 1982; Лоскутов и Михайлов, 1990). Эта модель основана на физических представлениях о спиновых стеклах. В приближении сильной связи, предполагая что спины (искусственные нейроны) находятся в состоянии близком к спиновому стеклу, можно оценить, что система, состоящая из 10²⁰ спинов, может записать примерно 5×10¹⁸ (порядка 5% от общего числа нейронов) различных ассоциативно связанных образов. Это число мы и примем в качестве максимальной оценки числа образов, которые человек в состоянии запомнить. Учитывая численность населения Земли, потенциальную емкость коллективного разума человечества можно оценить как 10²⁷ различных образов. Это фантастически высокие цифры! Ни одна реально существующая вычислительная машина, ни какая-либо мыслимая (основанная на тех же физических принципах, что и существующие сегодня машины) не в состоянии обработать такое количество информации.

В то же время, физическое быстродействие отдельного биологического нейрона чрезвычайно низко по сравнению быстродействием современной вычислительной техники. Нервная клетка способна находиться в одном из трех дискретных состояний: покое, возбуждении и рефрактерности (состояние невозбудимости). Переходы между состояниями управляются как процессами внутри самой клетки, так и "электрическими" сигналами, поступающими по отросткам от других нервных клеток. При переходе нейрона в возбужденное состояние в выходном отростке - аксоне - генерируется импульс возбуждения. Нейрон находится в возбужденном состоянии в течении определенного времени, а затем переходит в состояние рефрактерности, характеризующееся очень высоким порогом возбуждения. И только через некоторое время способность к возбуждению восстанавливается и нейрон переходит в состояние покоя. Между нейронами нет прямых электрических связей. Перенос возбуждения с аксона на входной отросток - дендрит - происходит электрохимическим путем в специальной области - синапсе, где окончания двух нервных клеток подходят близко друг к другу. Переключение между состояниями определяется медленными электрохимическими процессами, наиболее критичным является характерное время рефрактерности. Характерные времена распространения нервных импульсов составляют десятые доли секунды. Таким образом, быстродействие отдельных нейронов, ячеек памяти человека, на 8 порядков величины меньше быстродействия современного персонального компьютера и проигрывает суперкомпьютерам более десяти порядков величины.

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

Об объеме данных, с которыми приходится иметь дело в медицине, можно составить впечатление по следующим цифрам. В настоящее время в медицине известно свыше 10⁵ симптомов, более 10⁵ лекарственных препаратов, свыше 10⁴ болезней (Амосов и др., 1975). И это только те данные, с которыми практический врач встречается в процессе работы с историей болезни. Словарь международных клинических классификаций насчитывает 30 000 основных терминов, при этом для формулировки диагнозов также используется значительно большее число сочетаний из основных терминов. Очевидно, такое большое количество терминов - различных входных параметров с точки зрения систем KDD - не может быть непосредственно использовано для автоматизированного исследования; исходная информация должна быть предварительно обобщена. Успешное применение систем интеллектуального анализа невозможно без тесного взаимодействия медиков и математиков.

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

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

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

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

- накопление баз данных и сложность их непосредственного эмпирического анализа. Исследовательские базы данных отдельных врачей, ведущих наблюдения даже по очень узкой тематике, могут содержать сведения о нескольких десятках, а то и сотнях различных показателей, число записей - сведений о различных пациентах или об одном пациенте в различные моменты времени - может составлять несколько сотен или тысяч. Эмпирический анализ даже такого малого объема информации весьма сложен и трудоемок. Базы данных медицинских учреждений неизмеримо больше и сложнее. Об объеме этих данных, складированных сейчас на разных типах носителей, может говорить тот факт, что только одни научные учреждения за один день записывают, фиксируют информации примерно на 1 терабайт (по данным аналитического отдела американской компании GTE). При том надо учесть, что наука является не самым большим источником данных. Человек просто теряется в этом "море" сведений;

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

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

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

Использование методов knowledge discovery in databases (KDD) может выделить узкую группу показателей, от которых зависит интересующая исследователя характеристика, и представить обнаруженную закономерность в аналитической форме. Даже если впоследствии выяснится, что обнаруженная закономерность не является универсальной и характеризуется ограниченной областью использования, безусловная ценность полученного нового знания заключается в выделении группы наиболее чувствительных показателей, в привлечении внимания исследователя к более детальному анализу именно этих показателей и взаимозависимостей между ними, в предоставленной возможности сконцентрировать внимание на более узкой области исследований.

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

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

Что такое knowledge discovery in databases?

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

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

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

Knowledge discovery in databases (дословно, «обнаружение знаний в базах данных») - аналитический процесс исследования человеком большого объема информации с привлечением средств автоматизированного исследования данных с целью обнаружения скрытых в данных структур или зависимостей. Предполагается полное или частичное отсутствие априорных представлений о характере скрытых структур и зависимостей. KDD включает предварительное осмысление и неполную формулировку задачи (в терминах целевых переменных), преобразование данных к доступному для автоматизированного анализа формату и их предварительную обработку, обнаружение средствами автоматического исследования данных (data mining) скрытых структур или зависимостей, апробация обнаруженных моделей на новых, не использовавшихся для построения моделей данных и интерпретация человеком обнаруженных моделей.

Data mining (дословно, «разработка данных») - исследование и обнаружение "машиной" (алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых структур или зависимостей, которые

направленная на решение этих проблем - это технология knowledge discovery in databases (KDD). KDD - это синтетическая область, впитавшая в себя последние достижения искусственного интеллекта, численных математических методов, статистики и эвристических подходов. Цель технологии - нахождение моделей и отношений, скрытых в базе данных, таких моделей, которые не могут быть найдены обычными методами. Следует отметить, что на плечи Машины перекладываются не только "рутинные" операции (скажем, проверка статистической значимости гипотезы), но и операции, которые ранее было отнюдь не принято называть рутинными (выработка новой гипотезы). KDD позволяет увидеть такие взаимоотношения между данными, которые прежде даже не приходили в голову исследователю, а применение которых может способствовать увеличению эффективности лечения как отдельного пациента, так и функционирования медицинского учреждения в целом.

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

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

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

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

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

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

KDD и OLAP

Самый часто задаваемый вопрос, который возникает у людей, немного знакомых с обработкой данных, - это вопрос о разнице между средствами data mining и средствами OLAP (On-Line Analytical Processing), т.е. средствами оперативной аналитической обработки. OLAP - это часть технологий направленных на поддержку принятия решения. Обычные средства формирования запросов и отчетов описывают саму базу данных. Технология OLAP используется для ответа на вопрос, почему некоторые вещи являются такими, какими они есть на самом деле. При этом пользователь сам формирует модель - гипотезу о данных или отношениях между данными - и после этого использует серию запросов к базе данных для подтверждения или отклонения этих гипотез. Средства data mining отличаются от средств OLAP тем, что вместо проверки предполагаемых пользователем взаимозависимостей, они на основе имеющихся данных сами могут производить модели, позволяющие количественно оценить степень влияния различных исследуемых факторов на заданное свойство. Кроме того, средства data mining позволяют производить новые гипотезы о характере неизвестных, но реально существующих отношений в данных.

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

Краткая история KDD

Методы knowledge discovery in databases стали развиваться в течение последних 20 лет. До этого задачи компьютерного анализа баз данных выполнялись, в основном, при помощи различного рода статистических методик, использовавшихся и до появления компьютеров, так что компьютер просто облегчил и расширил возможности их применения. Те методы интеллектуального анализа данных, которые используются сейчас, есть результат эволюции в двух направлениях: с одной стороны - это углубленное развитие, "интеллектуализация", повышение уровня методов статистики, с другой стороны - попытки моделирования нервной ткани животных и человека, результатом которой стало построение искусственных систем, отчасти напоминающих эту нервную ткань и называемых искусственными нейронными сетями.

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

В настоящее время имеется уже много крупных исследовательских центров и коллективов, занимающихся разработкой методов и созданием систем KDD. Большинство из этих центров стали организовываться в 90-х годах (1992-93 гг.), и являются достаточно молодыми. Рост числа исследовательских групп сейчас, в 1996-2000 гг. выглядит экспоненциальным, так что исследовательских центров в ближайшем будущем станет, скорее всего, очень и очень много в самых разных фирмах, университетах, институтах и научных центрах.

Из крупных компаний, интенсивно занимающихся этой проблематикой, можно назвать таких гигантов как IBM и Microsoft. IBM полностью перепрофилировала свой крупнейший исследовательский центр в области технологий программного обеспечения в городе Альмаден на разработку алгоритмов KDD и на построение работающих систем KDD. Результатом этой работы явилось целое семейство систем KDD, как общего назначения, так и специализированных, предназначенных, в основном, для мэйнфреймов и мощных рабочих станций. Например, одна из специализированных систем, называемая Advanced Scout, применяется в Национальной ассоциации баскетбола США для анализа эффективности различных комбинаций игроков в командах, для анализа игровых ситуаций и для выработки игровой стратегии. Эта специализированная система стоит более миллиона долларов и используется несколькими командами МБА.

Фирма Microsoft создала центр KDD, находящийся непосредственно в здании штаб-квартиры фирмы в г. Редмонд, и пригласила работать известных специалистов, ранее занимавшихся этой проблематикой в университетах и академических научных центрах. Этот центр возглавляет профессор Усама Файадд, получивший в 1996 году одну из наиболее почетных американских премий за развитие науки, раньше работавший в лаборатории реактивного движения НАСА.

Пример Microsoft показывает, что самые крупные компьютерные компании придают большое значение этой новой технологии, а это не может не проявится в выпуске ими новых мощны продуктов для интеллектуального анализа данных. С другой стороны, существует также значительное количество небольших фирм, занимающихся продвижением технологий KDD. Их особенно много в США, но они есть и в Европе, в Англии, Франции. Одна из наиболее давно существующих таких фирм - это компания IntelligenceWare, которая производит одну из самых старых и известных коммерческих систем KDD - программу IDIS. Можно также назвать фирму Acknosoft (Франция), Integral Solutions (Англия) и много других.

Занимаются этими проблемами и в университетах. Одна из старейших исследовательских групп находится в Wichita State University в США, а в Германии - группа GMD. Сейчас уже имеется достаточно развитая информационная инфраструктура, обеспечивающая эти исследования, регулярно проводятся международные конференции, выпускается журнал, посвященный исключительно вопросам KDD. Большое внимание уделяется применению методов KDD в биологии и медицине. Наибольшее развитие получили, пожалуй, применения KDD, связанные с молекулярной биологией, а именно с расшифровкой макромолекул, и с созданием новых лекарственных препаратов. Следует упомянуть такие фирмы как Base4 Bioinformatics, BioDiscovery, DNA Star, Molecular Simulations и, соответственно, Anvil Informatics, Bioreason, Cellomics, Incyte Pharmaceuticals.

Приведенные факты свидетельствуют о том, что в настоящее время исследования KDD переживают бурный рост.

KDD как синтез разных областей знания

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

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

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

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

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

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

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

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

Типы задач и виды моделей

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

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

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

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

Обратимся к задаче построения моделей. Ее можно разбить на два важных подтипа. Во-первых, это задачи классификации. Имеются какие-то записи, или описания объектов (они могут быть заданы в разных формах), и о каждом из них заранее известно, что он принадлежит к некоторому классу из фиксированного конечного множества классов. Необходимо выработать правило или набор правил, в соответствии с которыми мы могли бы отнести описание любого нового объекта к одному из этих классов. Например, классическая задача такого типа - это медицинская диагностика. Пусть у нас есть описание пациентов (наших объектов) - данные каких-либо медицинских тестов, анкетные данные, данные анализов и т.д., а заранее известные классы - диагнозы болезней. Скажем, мы точно знаем, что некоторые пациенты больны диабетом, а другие не больны. Затем мы собираем данные тех же самых медицинских анализов для нового пациента и ставим задачу, как на основе проведенных анализов распознать, болен ли он диабетом или нет. Другой подтип составляют задачи прогноза какого-то непрерывного числового параметра. Это может быть, например, задача прогноза температуры отдельного больного или расходов и доходов клиники. Именно от этого прогноза зависит наше решение о продолжении или смене медикаментозного лечения, или покупке нового оборудования. И во многих других областях исключительно важно предсказывать именно непрерывные значения. Большинство из существующих сейчас коммерческих систем KDD решают главным образом задачи классификации. Но такая ситуация сложилась не потому, что задач классификации больше, чем задач прогноза непрерывных значений, а скорее потому, что методы классификации гораздо лучше изучены и могут быть проще реализуемы, чем методы прогноза непрерывного числового значения.

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

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

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

· Третьей задачей, относящейся к описанию данных, является нахождение исключений, исключительных ситуаций, записей (например, отдельных пациентов), которые резко отличаются чем-либо от основного множества записей (группы больных). Знание исключений может быть использовано двояким образом. Возможно эти записи образуют собой случайный сбой, например, ошибки операторов, вводивших данные в компьютер. Характерный случай, если оператор, ошибаясь, ставит десятичную точку не в том месте; такая ошибка сразу дает резкий отброс на порядок. Подобную "шумовую", случайную составляющую имеет смысл отбросить, исключить из дальнейших исследований, поскольку большинство методов, о которых пойдет речь в этой главе, очень чувствительно к наличию "выбросов" - резко отличающихся точек, редких, нетипичных случаев (рис. 3). С другой стороны, отдельные, исключительные записи могут представлять самостоятельный интерес для исследования, так как они могут указывать на некоторые редкие, но важные аномальные заболевания. Даже сама идентификация этих записей, не говоря об их последующем анализе и детальном рассмотрении, может оказаться очень полезной для понимания сущности изучаемых объектов или явления.

· Наконец, последняя, четвертая, разновидность задач, включаемая в рассматриваемый класс задач интеллектуального анализа данных, определяется английским термином data summarization, что можно передать как краткая итоговая характеристика данных. Что под этим имеется в виду? Скажем, если имеющийся у нас массив данных подчиняется некоторым жестким ограничениям на значения входящих в него параметров, возможно весьма сложного характера, и мы хотели бы выявить эти ограничения. Например, мы изучаем выборку данных по пациентам не старше тридцати лет, перенесшим инфаркт миокарда. Если мы вдруг обнаружим, что все пациенты, описанные в этой выборке, либо курят более 5 пачек сигарет в день, либо имеют вес не ниже 95 кг, это может быть для нас очень важно с точки зрения понимания наших данных, это практически ценное новое знание. Таким образом, data summarization - это нахождение каких-либо фактов, которые верны для всех или почти всех записей в изучаемой выборке данных, но которые достаточно редко встречались бы во всем мыслимом многообразии записей такого же формата и, например, характеризовались бы теми же распределениями значений полей. Если мы возьмем для сравнения информацию по всем пациентам, то процент либо сильно курящих, либо чрезмерно тучных людей будет весьма невелик. Можно сказать, что это как бы неявная задача классификации, но фактически нам задан только один класс, представленный имеющимися у нас данными. И они классифицируются путем сравнения с мыслимым множеством возможных записей, с множеством всех остальных мыслимых случаев.

От сырых данных к полезным решениям

Мы рассмотрели основные типы задач, которые решаются различными методами KDD. Есть методы KDD, которые применимы к разным задачам, есть методы, которые ориентированы на применение в каком-либо одном типе задач из рассмотренных. Теперь мы расскажем об основных этапах, или шагах, которые, как правило, входят в любое исследование данных с помощью методов KDD, рассмотрим основной цикл добычи нового знания и оценки его ценности (рис. 4). Некоторые из этих шагов могут в отдельных задачах отсутствовать или быть как-то редуцированы, но, в основном, все они необходимы и так или иначе присутствуют.

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

· Полученная прямоугольная таблица пока еще является слишком сырым материалом для применения методов KDD, и входящее в нее данные необходимо предварительно обработать. Во-первых, таблица может содержать параметры,

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

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

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

· Третий этап - это собственно применение методов KDD. Сценарии этого применения могут быть самыми различными и включать сложную комбинацию разных методов, особенно если используемые методы позволяют проанализировать данные с разных точек зрения. Собственно этот этап исследования и принято называть data mining (дословно, «разработка данных»). Следующие разделы посвящены более детальному рассмотрению этих методов.

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

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

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

Верификация и оценка полезности моделей

Автоматическая проверка достоверности добытого знания, оценка статистической значимости построенных моделей является необходимым и очень важным моментом любого исследования методами KDD. Проверка значимости определенных зависимостей, моделей может проводиться стандартными статистическими методами (например, Стентон, 1999).

При исследовании статистической надежности результата наиболее часто основываются на значениях стандартного отклонения и стандартной ошибки. Если значение зависимой переменной для i -ой записи есть p_i (1 i N ), а значение этой же переменной, предсказанное найденной моделью есть P_i , то стандартное отклонение определяется как

Здесь N - число записей, для которых посчитана регрессионная модель. Стандартная ошибка предсказанной данной моделью переменной определяется как

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

Значимость есть мера вероятности того, что найденная зависимость "истинна", действительно характеризует исследуемые данные. В качестве такой меры часто используется отрицательный логарифм вероятности того, что зависимость выведена чисто случайно, явилась результатом статистической флуктуации в данных. Чем ближе значение последней вероятности к нулю, тем выше значимость. Для вычисления индекса значимости сравнивается стандартное отклонение результата, полученного на реальных данных, со стандартным отклонением результата, полученного для искусственно созданных данных, в которых значение целевой переменной для разных записей случайным образом перемешано. Если стандартное отклонение, полученное на реальных данных s_real приблизительно равно стандартному отклонению случайных данных s_rand , то индекс значимости близок к к единице, то есть результат исследования не может рассматриваться как значимый. Если s_real много меньше, чем s_rand для всех случайно генерированных таблиц, то индекс значимости намного больше 1.0. В этом случае результат исследования может быть назван значимым. На практике имеет смысл называть значимыми только те модели, у которых индекс значимости больше 2.0.

Коэффициент корреляции r (1³ r ³-1) между значениями непрерывной целевой переменной и предсказываемыми значениями также характеризует значимость обнаруженной регрессионной модели. Чем ближе значение r ² к единице, тем больше значимость модели; если значения r ² небольшие, вблизи нуля, модель может быть отвергнута. Часто бывает полезно составить визуальное представление о значимости модели построив график зависимости предсказываемых значений целевой переменной от их реальных значений. Если бы предсказываемые значения совпадали с реально наблюдаемыми значениями, мы бы получили прямую, идущую под 45^о к оси абсцисс. Чем ближе к этой прямой ложатся точки на графике, тем точнее модель описывает данные. Ну, а если мы получим примерно сферическое облако, "модель" смело можно выбрасывать в корзину.

Для оценки значимости регрессионных моделей часто используется величина F ‑статистики ( F - ratio ), определяемой как квадрат частного от деления модуля соответствующего регрессионного коэффициента на величину его стандартного отклонения. Выполняя процесс линейной регрессии, система KDD может тестировать линейно-регрессионные модели, включающие в себя различные комбинации независимых переменных. Для каждой модели определяются значения ее регрессионных коэффициентов, их стандартных отклонений и величины F ‑статистики. Если регрессионная модель характеризуется значением F ‑статистики меньшим, чем заданное критическое значение, то эта модель отвергается. Использовать значение F ‑статистики меньшее двух в качестве критического, как правило, нецелесообразно.

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

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

Пусть клиника проводит целевую вакцинацию некоторой группы людей, состоящей из 10 000 человек. Большинство людей хорошо переносит вакцину, а у некоторых - назовем их группой риска - возникает нежелательная побочная реакция. Чтобы избежать ее, вакцинируемому необходимо одновременно с вакциной ввести некоторый редко используемый препарат. Пусть группа риска составляет 800 человек (эту величину можно экспериментально оценить, сделав контрольную вакцинацию в группе людей, равной величине репрезентативной выборки). Пусть найденная с помощью методов KDD модель умеет с некоторой вероятностью определять (по совокупности известных медицинских показателей), вызовет вакцинация у пациента негативную реакцию или нет. Если случайным образом выбрать 10% из общего списка, то есть 1000 человек, то в эту группу также попадет 10% от общего числа потенциальной группы риска, то есть 80 человек. Если же 1000 человек выбрать с помощью модели, предварительно проанализировав медицинские показатели всех 10 000 вакцинируемых, то количество людей, потенциально подверженных риску побочной реакции, в этой группе будет значительно больше. Разница между процентными величинами количества людей, попавших в группу риска при выборке по модели и при случайной выборке, называется "подъемом". Возможный график "подъема" в зависимости от величины выборки представлен на рис. 5а.

Рис. 5. График зависимости "подъема" (а) и "экономии" (б) от выборки

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

Обзор алгоритмов data mining

При исследовании данных средствами data mining используется большое число различных методов и их различные комбинации. Перечислим наиболее важные и часто используемые методы:

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

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

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

Кластеризация

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

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

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

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

На первом шаге разобьем все записи на K групп, наиболее близких к одному из центров. Мерой близости может быть расстояние в пространстве всех переменных (если переменным приписать геометрический смысл). Рис. 6 иллюстрирует разбиение на три кластера в плоскости двух переменных, обобщение на случай нескольких переменных несложно. Выбранные центры помечены крестиком. Множество точек, равноудаленных от двух заданных центров на плоскости - прямая (в пространстве n

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

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

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

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

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

Ассоциация, или метод корзины покупателя

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

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

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

Таблица 1. Диагнозы различных болезней условно помечены латинскими буквами

	A	B	C	D	E	…
A	41	13	18	26	11	…
B	13	24	15	16	2	…
C	18	15	22	4	1	…
D	26	16	4	48	15	…
E	11	2	1	15	25	…
….	…	…	…	…	…	…

В ячейках главной диагонали этой таблицы указано число пациентов, которым вынесен диагноз одной из болезней. Анализируя приведенную таблицу, легко определить, что заболевания A и D одновременно встречаются наиболее часто, что больные E , напротив, редко одновременно страдают болезнями B или C , а диагноз С редко сопровождается диагнозом D или E . Таким образом, таблица совпадений позволяет устанавливать на основании наблюдений правила типа

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

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

Ещё одной важной характеристикой ассоциации является усиление (improvement) ассоциации. Чем больше усиление, тем сильнее влияние, которое появление A оказывает на появление B . Усиление рассчитывается по формуле: (доверительность A к B ) / (распространенность B ).

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

Эти правила принято называть правилами ассоциации и диссоциации соответственно.

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

и легко воспринимаются человеком. Такие правила легко формулируются обычным языком и, соответственно, их можно непосредственно использовать. С другой стороны, генерируемое правило представляет собой оператор многих языков программирования, в частности языка SQL, и, следовательно, этот метод легко сопрягается с базами данных. Другими его достоинствами являются способность работать с записями различной длины и принципиальная (для понимания человеком) вычислительная простота. Наконец, его удобно использовать "для затравки" исследований, когда у Вас нет почти никаких начальных представлений о данных и Вы не знаете с какой стороны подступиться к задаче.

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

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

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

Деревья решений

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

Примем для простоты, что целевая переменная - булева переменная, принимающая только два значения - 0 и 1 и определенная для всех записей базы данных. Все множество записей в базе данных E мы можем разбить на 2 подмножества: Е+ (для которых целевая переменная Y имеет значение 1) и Е- (для которых ее значение равно 0). И теперь мы ищем классифицирующее правило, позволяющее разбить базу данных на эти два подмножества. В процессе поиска классифицирующего правила мы перебираем все независимые переменные и смотрим, какая из них может дать нам наиболее точное правило. Эти правила имеют обычно простой вид. Например, в случае действительной переменной это предикат вида x > A (или x < A ). После выбора дискриминирующей переменной мы разбиваем данные на две группы в соответствии со значением этого предиката. Для каждой из этих подгрупп опять находим свою независимую переменную, дающую наиболее точное классифицирующее правило. Процесс повторяется пока получающиеся подгруппы содержат в себе представителей обоих классов и включают в себя достаточно большое количество точек для того, чтобы статистически значимо быть разбитыми на меньшие подгруппы. В результате окончательное классифицирующее правило, построенное этим процессом, может быть представлено в виде бинарного дерева. Каждый (кроме конечных) узел этого дерева соответствует некоторому подмножеству данных и содержит найденное классифицирующее правило для этого подмножества. Узлы дерева маркируются 0 или 1 в зависимости от относительного числа записей каждого класса подмножества соответствующей ветви дерева, или же число записей каждого класса может быть представлено графически, например гистограммой (рис. 8). Попутно заметим, что аналогию с деревом не следует воспринимать слишком буквально. Как и на рисунке, в большинстве случаев деревья рисуются "вверх ногами".

С этой точки зрения было бы более естественно сравнивать классифицирующие схемы с корневой системой растений.

Одним из наиболее важных свойств деревьев решений является представление данных в виде иерархической структуры. Такая структура естественным образом может быть использована для классификации. Допустим, мы построили дерево, и у нас имеется запись, не включенная в число обучающих примеров, использованных для построения классифицирующих правил. Тогда, идя по этому дереву от корня (начального узла) к листьям (конечным узлам), проверяя каждый раз критерии, соответствующие узлам этого дерева, мы выбираем правую или левую ветвь дерева (правого или левого потомка) соответственно выполнению или невыполнению этого критерия. В конце концов, мы приходим к листу этого дерева (конечному узлу) и, соответственно, относим запись к одному из классов. За значение атрибута Y классифицируемой записи мы принимаем 0 или 1 в соответствии с меткой этого листа. Процесс классификации немного напоминает определение видов в ботанике или зоологии - отвечая на ряд вопросов, мы относим рассматриваемый объект к тому или иному классу.

Существует большое количество вариантов алгоритмов, строящих деревья решений. Многие из них состоят в рекурсивном применении некоторой процедуры расщепления первоначально ко всему множеству обучающих примеров, а затем к их подмножествам, получаемым в результате расщепления исходного множества записей. Для каждого множества записей эта процедура определяет непрерывный или дискретный атрибут, значение которого может быть наиболее точно использовано для прогноза значения атрибута Y и определяет критерий дробления. Если поля всех записей известны точно и полностью определяют значение поля Y , дробление должно идти до тех пор, пока оно дает хотя бы какой-то выигрыш в точности классификации. Эта процедура должна также уметь закончить процесс дробления - определить, что для некоторого множества записей уже не может быть построено статистически значимое классификационное правило, и таким образом это подмножество соответствует листу строимого дерева решений. Выбор атрибута и критерия, по которым производится расщепление множества, решение ситуации, когда не ясно к какому классу отнести некоторую запись, являются принципиальными моментами, различающими используемые алгоритмы построения деревьев решений. Также используется подход, где критерий расщепления данных реализуется в виде перцептрона. Можно отметить также интересный метод, основанный на превращении построенного дерева решений в эквивалентную ему нейронную сеть и ее до-обучение одним из стандартных методов (Sethi, 1990).

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

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

Ввиду того, что медицинское знание не является точным, по-видимому, перспективно использование нечетких критериев расщепления. Вместо определенного отнесения каждой записи, относящейся к узлу, к одному из его потомков, определяется непрерывная (в терминах нечетких множеств) мера принадлежности записи к разным подгруппам, так что в результате одна и та же запись может принадлежать к разным листьям, но с разной степенью уверенности. Примеры таких алгоритмов можно найти в литературе (Schuermann and Doster, 1984; Wang and Suen, 1987; Quinlan, 1993).

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

Алгоритмы деревьев - одни из самых быстрых и эффективно реализуемых в области KDD, поэтому они получили широкое распространение. Их вычислительная сложность определяется главным образом типом применяемого критерия расщепления. Во многих случаях время нахождения критерия расщепления линейно зависит от количества полей. Зависимость времени решения от количества записей n часто линейная или близкая к ней (как n × log( n )).

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

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

Рис. 9. Выбор критерия отсечения незначимых решений

Тесты показывают, что несмотря на наличие отсечения в большинстве существующих алгоритмов многие из них страдают "переобобщением" - построением слишком больших деревьев с малой статистической надежностью отдельных листьев (Kiselev et al . 1997). Если в дереве решений слишком много ветвей, конечным ветвям может соответствовать лишь небольшое число записей; следовательно высока вероятность, что разбиение сложилось в силу случайных факторов и не имеет естественного смысла.

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

Анализ с избирательным действием

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

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

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

Сети уверенности

Этот метод, как и многие другие методы KDD, также основан на давно существующих статистических подходах, таких как корреляционный и дисперсионный анализы. Это метод, основанный на сравнении распределений значений зависимых переменных для записей с разными значениями независимых переменных. Пусть мы решаем задачу классификации, и нам нужно найти правило, отличающее записи одного класса от записей другого класса. Если какая-либо из независимых переменных в одной группе имеет распределение, сильно отличающееся от распределения в другой группе, эта переменная может быть эффективно использована для различения записей в этих двух группах. В частности, так называемые байесовы сети уверенности (bayesian belief networks, BBN), основанные на нахождении в данных аномалий во взаимном распределении разных параметров, сыскали в последнее время довольно широкое распространение. Пусть база данных содержит два поля, X и Y , которые обладают тем свойством, что для большого числа записей со значениями параметра x большими, чем некоторая величина B , значения параметра y также превышают некую константу A . Сильное отличие вероятности того, что y > А , P ( y > A ), от условной вероятности P ( x > B / y > A ) дает основание для гипотезы о зависимости этих параметров. Системы BBN на основании различий условных и полных вероятностей выстраивают графы влияния параметров, наглядно показывающие их взаимосвязь.

Метод ближайших соседей

Этот метод очень близко примыкает к методам KDD, хотя, строго говоря, не относится к собственно извлечению знаний из данных. Этот метод называется методом "ближайших соседей" (nearest neighbour) или методом, основанным на рассуждении о случаях (case based reasoning). Идея метода очень проста. Пусть нам надо предсказать значение зависимой переменной для некоторой записи, и есть массив записей, для которых известны значения как зависимой, так и независимых переменных. Для этого в этом массиве записей (мы будем называть их обучающими записями), мы выбираем запись, в некотором смысле наиболее близкую к той, для которой нам надо сделать предсказание. И в наиболее простом варианте этого метода в качестве прогнозируемого значения независимой переменной мы выбираем значение прогнозируемой переменной этой наиболее близкой записи. Говоря более строгим языком, мы вводим метрику (расстояние) на пространстве всех возможных записей, определяем в этом пространстве точку, соответствующую записи, для которой надо сделать прогноз, находим в рамках этой метрики ближайшую к ней точку из точек, представляющих обучающие записи, и берем значение зависимой переменной этой записи в качестве прогнозируемого значения. Описанный здесь алгоритм очень прост - реально применяются некоторые его модификации. Обычно прогноз делается на основе нескольких ближайших точек, а не одной. В этом случае в качестве оценки значения целевого параметра берется взвешенное среднее по ближайшим записям, где весом служит величина, обратно пропорциональная расстоянию до них (при этом прогноз в наибольшей степени определялся наиболее близкими записями). Такой метод более устойчив, поскольку позволяет сгладить отдельные выбросы, случайный шум, всегда присутствующий в данных.

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

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

Нейронные сети

Нейросетевые методы условно можно отнести к области KDD. Эти методы успешно решают многие задачи прогноза, задачи нахождения зависимости одних переменных от других, но строимая зависимость не представляется в ясном для понимания человеком виде. Поэтому, строго говоря, к извлечению знаний из баз данных их можно и не относить. Но поскольку открытие нейронных сетей во многом определило возникновение и развитие методов KDD, поскольку нейросетевые методы очень популярны и широко применяются, в том числе при медицинских исследованиях (Амосов и др. 1975; Лукович, 1987; Гольцев, 1987; Кудряшев и др., 1996; Фролов и др., 1999; Фролов, 2000), а область их применения в значительной степени пересекается с методиками KDD, мы их также рассмотрим.

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

Основной идеей создания нейросетевых систем была попытка имитации структуры нервной ткани. Работа уже обученной системы напоминает распространение нервных импульсов. Каждому узлу (нейрону) сети приписывается некоторое числовое значение. Значение, приписываемое каждому узлу нижнего уровня, или рецептору, равно значению некоторого поля (переменной) из записи, которая в данный момент подается на вход нейронной сети. Значения, связываемые с нейронами более верхних уровней, определяются по следующему алгоритму. В обученной сети каждой связи между нейронами приписывается некоторый вес, действительное число, лежащее, как правило, в диапазоне от -1 до +1. Отдельный нейрон условно показан в нижней части рис. 10. Чтобы определить значение, связанное с каким-либо нейроном, вычисляется входной уровень нейрона - взвешенная сумма значений всех нейронов предыдущего уровня, связанных с данным нейроном; множители равны весам соответствующих связей. Если a_i - значение на нейроне, связанном с i -ым входом данного нейрона, а w_i - вес соответствующей связи, то входной уровень определяется как .

Рис. 10. Предсказание с помощью нейронной сети

Каждый нейрон имеет так называемую передаточную функцию f , которая для каждого значения порогового уровня возвращает некоторое число, приписываемое нейрону t = f ( p ). Обычно это монотонно возрастающая антисимметричная функция с f (-¥) = -1, f (0) = 0 и f (¥) = 1. Часто в качестве такой функции берут гиперболический тангенс

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

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

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

Рис. 11. Функция ошибок искусственной нейронной сети

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

Нейросетевые методы обладают рядом положительных свойств, определяющих области их использования:

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

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

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

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

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

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

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

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

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

Нечеткая логика

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

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

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

Нечеткая логика и алгебра применяются для анализа таких наборов данных, когда невозможно причислить данные к какой-либо группе. Мы можем только отнести данные к какой-либо группе с некоторой вероятностью (немного упрощая разницу между нечетким и вероятностным подходами) находящейся в интервале от 0 до 1, но не принимающей крайние значения. Четкая логика манипулирует результатами, которые могут быть либо истиной, либо ложью. Нечеткая логика применяется в тех случаях, когда необходимо манипулировать степенью "может быть" в дополнении к "да" и "нет".

С середины шестидесятых годов, после разработки Л. Заде теории нечетких множеств, было предложено несколько теорий, позволяющих формализовать неопределенность. Эта область знания интенсивно развивается в настоящее время. Естественной и простейшей альтернативой числу является соотнесение некоторому медицинскому показателю x не одного численного значения, а функции r_x(u) , представляющей собой распределение нечеткости величины x (Рис. 12a) и также называемой функцией принадлежности.

Второе название происходит оттого, что нечеткую величину x можно интерпретировать как нечеткое множество X . Происхождение второго названия связано с возможностью интерпретации нечеткой величины х как нечеткого множества Х . Функция r_x(u) есть мера того, что значение величины x находится вблизи u . Функция может быть как детерминированной взаимно-однозначной функцией, так и более сложной конструкцией (Klir, 1989; 1991). В первом случае это может быть, например, функция плотности вероятности f_x(u) , причем интеграл от этой функции по области всех возможных значений равен единице.

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

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

Генетические алгоритмы

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

Само название метода подчеркивает аналогию этого метода с процессом эволюции и естественного отбора в природе. Первоначально цель исследований, начатых в Мичиганском университете Джоном Холландом (Holland, 1975), формулировалась как, во-первых, строгое объяснение процессов приспособляемости, имеющих место в природе, и, во-вторых, создание искусственных систем, моделирующих основные принципы функционирования естественных систем. Центральной темой исследований генетических алгоритмов явился принцип устойчивости - приспособляемости. Действительно, если бы удалось радикально повысить степень устойчивости искусственных систем, то это при бы к значительному сокращению затрат на их ремонт или переработку применительно к изменяющейся ситуации. Чем выше уровень приспособляемости, тем дольше и лучше могут выполнять свои функции соответствующие системы. Секреты адаптации и выживания лучше изучать на биологических примерах. Создателям искусственных систем (как оборудования, так и программного обеспечения для него остается только восхищаться устойчивостью, гибкостью и эффективностью биологических систем. Такие присущие биологическим системам функции как воспроизводство, самовосстановление, самоуправление являются условием их существования, но эти же функции либо полностью отсутствуют, либо имеют место в зачаточных формах даже в самых сложных искусственных системах. Созданная в конце 80-х годов парадигма генетических алгоритмов в какой-то мере позволяет повысить адаптируемость искусственных систем.

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

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

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

Рис. 14 иллюстрирует одну из реализуемых в генетических алгоритмах моделей скрещивания и мутации. Обе генетических операции выполняются с определенной вероятностью. Вероятность скрещивания, которая определяется из расчета на одну хромосому, как правило, изменяется в пределах от 0,8 до 1,0. Вероятность мутации, отнесенная к одному гену, выбирается чаще всего из интервала 0,001 - 0,01.

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

Одним из последствий вероятностного отбора является быстрое увеличение наиболее ценных хромосом, и которые, соответственно, выбираются для скрещивания чаще других. Однако практика использования генетических алгоритмов показывает, что чрезмерно быстрая сходимость алгоритма не всегда эквивалентна глобальному решению задачи. Учитывая это, с особой осторожностью необходимо подходить к выбору стратегии элитной селекции [1], при которой ограниченному числу "избранных" хромосом, имеющих наилучшую целевую функцию, гарантировано участие в следующем поколении, минуя стадии скрещивания и мутации. Хотя идея сохранения элитных хромосом и привлекательна, в целях избежания вырождения популяции, полезно поддержать монотонное увеличение целевой функции. Для решения этой проблемы разработаны альтернативные схемы отбора хромосом, предотвращающие слишком поспешную сходимость. Одним из таких методов является нормализация целевых функций хромосом прежде, чем они начнут использоваться для выбора родительских пар. Методы нормализации рассмотрены в работе Л. Дэвиса (Davis., 1991г.). Другим методом, поддерживающим генетическое разнообразие популяции, является параллельный генетический алгоритм (Miihlenbein et al ., 1991). В некоторых генетических алгоритмах применяются более утонченные стратегии селекции. Например, потомкам разрешается входить в новую популяцию только в том случае, если они значительно отличаются от остальных членов популяции. С целью поддержания достаточного генетического разнообразия часть созданных (отобранных) хромосом может быть внедрена в следующее поколение до достижения популяцией заранее заданного желаемого размера. Однако методы, снижающие вероятность вырождения популяции и способствующие получению глобального решения, связаны с необходимостью вычисления степени подобия между индивидуумами. Для сложной задач такие расчеты выполнять, как правило, нежелательно. Поэтому разработаны более совершенные стратегии. Одна из них предполагает привлечение дополнительного, конкурирующего с основным, генетического алгоритма, который выводит так называемых "паразитов".

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

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

Регрессионные методы

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

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

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

Нахождение вида функции f и значений производится на основе минимизации некоторой функции С от величин e _j . В абсолютном большинстве подходов является используется сумма квадратов ошибок:

где M - количество записей. Выбор такого критерия определяется рядом причин. Строгое обоснование его оптимальности основывается на предположении о нормальном распределении ошибок e _j , что не всегда оправдано. Однако, если это предположение верно, то данный критерий позволяет получить несмещенные оценки Y с наименьшей дисперсией. Важную роль играет и тот факт, что для линейных относительно функций f существуют эффективные алгоритмы прямого вычисления регрессионных коэффициентов, тогда как для других функций С (e _j ) нахождение регрессионных коэффициентов пришлось бы производить различными численными методами минимизации функций многих переменных. Главный из недостатков такого выбора - его сильная чувствительность к существенным отличиям распределения e _j от нормального, в частности к наличию даже небольшого количества записей с очень большими значениями e _j . По этой причине используются и другие критерии, более устойчивые к наличию таких далеких отскоков. В частности, иногда суммируются модули величин e _j , а не их квадраты. Этот критерий более устойчив по отношению к наличию далеких отскоков, но используя его, мы теряем преимущество эффективной вычислимости регрессионных коэффициентов. В некоторых случаях выбор критерия С ( ) определяется особенностями задачи. Например, бывают ситуации, когда важно обеспечить, чтобы абсолютная величина ошибок не превышала некоего заданного уровня. В этом случае используется критерий .

Линейная регрессия

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

Класс методов, характеризуемый таким выбором функций f , называется методами линейной регрессии. Выбор линейной регрессионной функции имеет много преимуществ. Весьма существенно, что линейная зависимость между переменными легко интерпретируется человеком. Фактически линейная регрессионная модель разбивает зависимость целевой переменной Y от независимых переменных X_i на отдельные, не связанные между собой компоненты. Она позволяет оценить вклад каждой независимой переменной по отдельности, определив знак и силу этого влияния. Если используется критерий наименьших квадратов, то существует эффективный алгоритм вычисления значений регрессионных коэффициентов A_i . Алгоритм нахождения регрессионных коэффициентов линейной модели излагается в любом стандартном курсе статистики (например, Стентон, 1999). Скажем лишь, что он основан на проведении достаточно простых матричных операций. Одним из наиболее быстрых и устойчивых методов является алгоритм Холецкого, подробно изложенный Маиндональдом (Maindonald, 1984). Важно отметить, что результатом работы алгоритмов, решающих линейную регрессионную задачу является не только оценка точности полученной регрессионной модели, но также стандартные отклонения входящих в нее регрессионных коэффициентов. Поэтому мы можем судить о значимости (не случайности) вхождения отдельных переменных в регрессионную модель. Мерой этой значимости может служить значение F ‑статистики - квадрата отношения величины регрессионного коэффициента к величине его стандартного отклонения.

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

Один из самых популярных в настоящее время методов - многомерная линейная регрессия с автоматическим выбором независимых параметров - основан на применении алгоритма пошагового выбора независимых переменных. Первоначально список включенных в регрессионную модель независимых переменных пуст. Сначала рассматриваются все линейные модели, зависящие только от одной переменной, и для каждой из них вычисляется стандартная ошибка и значение F ‑статистики. Выбирается независимая переменная, имеющая минимальную ошибку, и включается в список. Далее аналогичным образом отбирается вторая переменная. Рассматриваются все возможные такие двумерные линейные модели, первая из переменных которой совпадает с уже включенной в список переменной, и среди них выбирается наилучшая модель. Вычисляется стандартная ошибка и достоверность определения регрессионных коэффициентов, или значения F ‑статистик всех входящих в модель коэффициентов, и в список добавляется вторая переменная, наиболее значимо влияющая на целевую переменную. И так на каждом шаге прибавляется новая независимая переменная. Этот процесс продолжается пока достоверность определения регрессионного коэффициента новой независимой переменной, добавляемой в список, не становится меньше некоторого заданного порогового значения. В принципе, когда мы включаем новый член в список независимых переменных, у нас может перестать выполняться критерий для величины F ‑статистики какой-нибудь уже включенной в список переменной. В такой ситуации мы удаляем из списка старую, не удовлетворяющую критерию переменную и добавляем новую, и если полученная регрессионная модель дает уменьшение стандартной ошибки по сравнению с предыдущей, то продолжаем итерации. Окончание процесса добавления новых переменных означает, что все переменные, значимо влияющие на зависимую переменную, уже включены в список (если, конечно, список не остался пустым).

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

Рис. 15. Зависимость стоимости анализов от квалификации врача

Нелинейная регрессия

Шагом в нахождении более сложных моделей является использование метода нелинейной регрессии. Этот метод заключается в том, что на основе имеющихся знаний об исследуемых данных выбирается некоторый вид регрессионной функции и требуется найти значения регрессионных коэффициентов . Нелинейная регрессия реализована в многих системах анализа данных. Однако его практическая ценность часто ограничивается тем обстоятельством, что пользователь должен a priori располагать довольно подробными знаниями об искомом решении. А именно, он должен задать вид регрессионной функции, примерные значения регрессионных коэффициентов и характерные масштабы их изменения. Знание двух последних моментов необходимо по следующей причине. При нахождении регрессионных коэффициентов линейной модели в нашем распоряжении имеется эффективный алгоритм их вычисления на основе матричной алгебры. В случае произвольной нелинейной модели задача нахождения регрессионных коэффициентов есть задача численной минимизации величины , рассматриваемой как функция регрессионных коэффициентов . А для всех численных методов нахождения минимума функции нескольких переменных существует опасность нахождения локального, а не глобального минимума, если или начальное приближение для точки минимума, или характерные масштабы изменения аргументов заданы неправильно (рис. 16).

Рис. 16. Зависимость функции ошибок от параметров нелинейной модели.

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

С вычислительной точки зрения, линейная регрессия хороша не столько тем, что в нее линейно входят независимые переменные, сколько тем, что в нее линейно входят регрессионные коэффициенты. Именно это дает возможность быстро и точно решать регрессионные задачи. Поэтому прямым и эффективным обобщением метода линейной регрессии является использование нелинейных регрессионных моделей обладающих свойством линейности относительно регрессионных коэффициентов. Одним из наиболее известных методов, использующих регрессионные модели такого типа является метод группового учета атрибутов, сокращенно МГУА (Farlow, 1984; Ивахненко и Мюллер, 1985), предложенный А.Г. Ивахненко в 1968 году и затем подробно исследованный Р. Шанкаром (Shankar, 1972). В этом методе регрессионная функция выбирается в виде

Различные варианты МГУА различаются выбором функций F и стратегий включения различных членов в сумму. Часто полагают F(x) = x . Выбор членов для введения их в модель может осуществляться пошаговым алгоритмом, аналогичным обсуждавшемуся выше алгоритму множественной линейной регрессии с автоматическим выбором независимых переменных. Другой подход основывается на механизме, часто применяемом для удаления незначимых ветвей деревьев решений. А именно, множество анализируемых записей делится на две части, и одна часть используется для получения максимально общей модели этого вида, а другая часть - для ее тестирования. При этом отдельные члены, входящие в выражение (8), отбрасывают так, чтобы рост стандартной ошибки был минимальным. Процесс отбрасывания членов останавливают после того как стандартная ошибка возрастает в некоторое заранее установленное количество раз (обычно не более 1.05 раз). В другой группе разновидностей МГУА процесс построения модели повторяют несколько раз, причем на каждом следующем этапе в качестве независимых переменных берут не только X_i , но и значения регрессионных функций, полученных на предыдущих этапах. Наконец, в ряде вариантов выбирается модель, которая минимизирует значение некоторой функции от стандартной ошибки прогноза и меры сложности модели (скажем, число членов в этой сумме).

Логистическая регрессия

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

Рассмотрим сначала булеву переменную. Применение регрессионных методов нахождения числовых зависимостей в этом случае основывается на том, что логические значения "ложь" и "истина" булевой переменной Y рассматриваются как числовые значения 0 и 1, соответственно. При этом мы можем воспользоваться одним из методов нахождения числовых зависимостей для построения регрессионной модели, наилучшей с точки зрения, например, критерия наименьшей среднеквадратичной ошибки (6). Значением полученной регрессионной функции будет, вообще говоря, действительное число, которое может рассматриваться как нечеткая мера принадлежности к множеству записей с Y = 1. Конечно найденная регрессионная функция не может служить точной мерой вероятности принадлежности к классу Y = 1. Например, ее значение не обязательно лежит в интервале [0, 1]. Тем не менее во многих случаях она дает приемлемую картину распределения записей с Y = 0 и Y = 1 в разных областях пространства независимых переменных.

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

Этот метод также может быть использован, если целевая переменная имеет категориальный тип, то есть когда должны быть получены классификационные правила, разбивающие множество записей на более чем два подмножества. Если целевая переменная принимает n разных значений ( n > 2), нужно решить n регрессионных задач, таких что в i -ой регрессионной задаче значение зависимой переменной равно 1 для записей, принадлежащих i -ому классу и 0 для остальных записей. В качестве результата получим n функций f_i выражающих меру принадлежности i -ому классу. Чтобы классифицировать новую запись, надо вычислить для нее значения всех этих функций, и если наибольшим окажется значение k -ой функции, отнести запись к k -ому классу.

Логистическая регрессия - это, с одной стороны, классификационный инструмент, который используется для предсказания значений категориальных переменных (проявится ли у пациента определенный диагноз или нет) и, с другой стороны, регрессионный инструмент, который используется для оценки степени влияния входных факторов (индивидуальных характеристик пациентов, факторов окружающей среды). Смысл применения линейной регрессии для классификации заключается в его эффективности (Kiselev et al ., 1997).

Эволюционное программирование

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

Все рассмотренные до этого методы отличались одной присущей им всем слабой стороной - а именно, выразительной слабостью используемого ими языка представления обнаруживаемых знаний и, как следствие, узостью класса зависимостей, которые в принципе могут быть этими методами обнаружены. Например, алгоритмы деревьев решений могут получать только классификационные правила в виде формул исчисления высказываний, включающих элементарные операторы отношений (>, <, =). Линейная регрессия может находить зависимости только в виде линейных формул. И так практически каждый метод KDD привязан к некоторому узкому языку представления знаний. Это существенное ограничение, и единственный кардинальный способ его преодолеть - это попробовать искать законы и правила не в виде формул некоторого фиксированного декларативного формализма, а в виде алгоритмов и программ, выражающих способ вычисления значение целевой переменной, исходя из значений независимых переменных.

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

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

Понятно, что поскольку пространство поиска чрезвычайно широко и внутренний язык поиска также может очень сильно различаться, число принципиально возможных реализаций эволюционного метода также практически неограниченно. Вместе с тем, ввиду сложности и ресурсоемкости метода, только одна из существующих коммерческих систем KDD, а именно программа PolyAnalyst фирмы "Мегапьютер Интеллидженс", предоставляет возможность использовать этот метод для анализа данных. В то же время популярность этого метода непрерывно растет, практически все ведущие научные форумы в области data mining и knowledge discovery in databases включают в программу работы секции по эволюционному программированию.

За возможность обнаружить и формализовать разнообразные многомерные нелинейные зависимости, естественно, приходится платить очень большим объемом производимых вычислений. Эти программы строят сложные формулы, выражающие зависимости в данных, комбинируя более простые формулы, и в конечном итоге находят достаточно точную формулу, выражающую искомое отношение. В качестве примера подобного рода систем мы можем упомянуть FAHRENHEIT (Zytkow and Zhu, 1991), ARE (Shen, 1990), 49er (Zembowicz and Zytkow, 1992). Вероятно одно из самых крайних положений в этом ряду в настоящее время занимает система интеллектуального анализа данных PolyAnalyst (Киселев 1994; Киселев и Арсеньев 1996; Киселев и др., 1997). Ниже мы рассмотрим эволюционное программирование и его возможности на ее примере систем 49er и PolyAnalyst.

Система 49er

Система 49er (читается fourty-niner) была создана исследовательской группой под руководством профессора Яна Жидкова в Университете города Вичита, США, одной из самых старых групп, занимающихся исследованиями в области KDD. Если исключить из рассмотрения PolyAnalyst, то данная система на настоящий момент способна автоматически обнаружить в данных наиболее широкий класс нелинейных зависимостей, в том числе сформулированных не в явном виде, а виде уравнений, включающих как зависимые, так и независимые переменные. Класс регрессионных моделей, которые она может отыскать, описывается следующей формулой:

где y - зависимая переменная, x - независимая переменная, A_i - регрессионные коэффициенты. Имеющаяся сейчас версия системы 49er может находить лишь одномерные модели. Левая часть в записи этого уравнения симметрична относительно переменных x и y , а после решения этого уравнения относительно y уравнение приобретает обычный вид. Например, если

Если мы разрешим это уравнение относительно y , то получим

то есть весьма сложную нелинейную регрессионную модель.

Существенным преимуществом системы 49er по сравнению с другими системами заключается в возможности учета точности измерения целевой переменной y для разных записей. Таким образом исследуемые этим методом данные представляют собой набор троек , где - ошибки измерения величин y_i . При знании точности измерения зависимой переменной критерий для нахождения регрессионных коэффициентов может учитывать неодинаковую ценность разных записей. А именно, вклад каждой записи в функцию (6) для должен быть учтен с весом, обратно пропорциональным точности измерения. Это рассуждение дает нам следующий критерий:

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

Рассмотрим теперь ключевой момент системы - автоматический выбор функций F(x, y) и f(x) . В процессе поиска наилучшей регрессионной модели система 49er перебирает разные функции F(x, y) и f(x) в порядке возрастания их сложности. Новые функции генерируются из уже построенных с помощью рекурсивного применения нескольких методов продукций. В начале этого процесса в качестве простейших функций берутся сами зависимая и независимая переменные y и x . На каждом шаге к уже имеющемуся набору функций применяются следующие методы продукций:

Этот стандартный набор продукций может быть автоматически расширен системой. Если получающаяся в результате такого процесса функция зависит от y - это кандидат на роль F(x, y) , если нет - будет использована в качестве f(x) . Таким образом поиск наилучшей модели (9) можно рассматривать как обход клеток бесконечной таблицы (рис. 17), начинающийся с левого верхнего угла и охватывающий сначала близкие, а затем все более и более далекие от этого угла клетки.

Рис. 17. Рекурсивное построение элементов функциональных зависимостей в системе 49er.

На примере системы 49er можно видеть общую закономерность - чем более общие модели может строить система, тем больше ее работа должна быть основана на поиске в пространствах формул определенного класса. При таком поиске возникают характерные проблемы - если процесс рекурсивного построения более сложных формул из более простых никак не ограничивать, он будет приводить к огромному количеству бессмысленных, либо эквивалентных формул. Поэтому в системе 49er используются специальные модули, упрощающие запись вновь построенных формул и приводящие их некоторому каноническому виду. Если в результате работы этих модулей обнаруживается, что построенная формула F(x, y) или f(x) эквивалента константе или какой-либо ранее построенной формуле, она отбрасывается. Поскольку для каждой пары ( F(x, y) , f(x) ) фактически решается линейная регрессионная задача, проверка удачности выбора пары занимает очень малое время, и система может дойти до весьма сложных регрессионных моделей за вполне разумное время.

Система PolyAnalyst

Главный модуль, составляющий ядро системы PolyAnalyst, формулирует и проверяет гипотезы об искомой зависимости в виде программ, автоматически создающихся на простом внутреннем функциональном языке программирования. Логическая структура этого модуля, упоминаемого далее в этом разделе для краткости просто как PolyAnalyst, довольно сложна. Модуль включает следующие четыре основных компоненты (Рис. 18): внутренний язык программирования, модуль отсеивания тривиальных зависимостей и эквивалентных уже найденным, модуль оценки найденных зависимостей и модуль, вырабатывающий стратегию поиска. В PolyAnalyst реализован универсальный механизм генерации и тестирования регрессионных моделей, который может работать с данными, имеющими произвольную структуру. Это возможно, поскольку программы, синтезируемые системой, имеют доступ к исследуемым данным через специальные примитивы доступа, обеспечивающие выборку элементов векторов, матриц, списков и других сколь угодно сложных структур данных.

Внутренний функциональный язык. Этот язык, составляющий фундамент PolyAnalyst и используется для формулирования гипотез о взаимосвязях в данных. Подобно другим языкам программирования, внутренний язык включает три основные составляющие (рис. 18): типы данных, функциональные примитивы и структуры управления. Последние также могут рассматриваться как методы конструирования более сложных программ из более простых. Функциональным примитивам соответствуют операторы и библиотечные функции, а конструкции управления - это всякого рода циклы и условные конструкции, такие как if , for или while .

Типы данных внутреннего языка образуют два класса: универсальные типы, которые определены для всех областей применения, и определяемые пользователем типы данных, специфичныее для конкретных областей применения. Если привести для сравнения язык программирования C, то типы данных внутреннего языка соответствуют целым и действительным числам языка C ( int и double ), а также типам, определяемым пользователем с помощью декларатора struct . Свойства каждого определенного пользователем типа данных определяются двумя характеристиками. Первая характеристика описывает свойства упорядоченности, а именно, определено ли для этого типа отношение "больше чем" или оператор "следующий". Вторая характеристика называется перечислимостью. Она определяет, а можно пересчитать все данные этого типа, может ли эта переменная быть переменной цикла, имеет ли смысл инструкция "для каждой величины этого типа осуществить некоторые действия".

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

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

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

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

Отсев тривиальных зависимостей и эквивалентных уже найденным .

Итак, применяя методы продукций к существующим программам, мы получаем новые программы. Однако нельзя гарантировать, что эти новые программы будут осуществлять какие-то осмысленные вычисления. Самые общие требования к правильности синтезируемых программ можно сформулировать следующим образом: программа не должна иметь входов (параметров), от которых возвращаемое ею значение не зависит; возвращаемое программой значение должно зависеть от записи базы данных, для которой ее вычисляют; программа не должна быть эквивалентна какой-либо из построенных ранее программ. Программы, не удовлетворяющие этим условиям отсеиваются. Этот модуль отсеивает 99% программ, синтезируемых процессом полного перебора программ.

Создаваемые программы рассматриваются как решения некоторой задачи. Например, если решается задача нахождения числовых зависимостей, то строимые программы трактуются как регрессионные функции и оцениваются в терминах стандартной ошибки соответствующих регрессионных моделей. Однако, не каждая программа рассматривается как потенциальное решение. Программы, которые не включают примитивов доступа к данным, и даже некоторые классы программ, включающие такие примитивы, служат только как компоненты других программ. Модуль, осуществляющий оценку программ, может, вообще говоря, реализовывать определяемый программой P функционал Ev [P] , который должен быть минимизирован. Эта черта дает системе гибкость и возможность быть примененной для решения широкого класса задач KDD и оптимизации. Для каждой построенной программы решается задача нахождения наилучшего (в терминах минимальности этого функционала) набора значений входных параметров. В зависимости от вида функционала и программы для решения задачи используются методы комбинаторики, численной оптимизации или другие подходы.

Этот модуль выбирает методы продукций и компоненты для построения новых программ. Синтез новых программ ведется двумя параллельными процессами. Первый, с более низким приоритетом, осуществляет полный перебор синтаксически и семантически правильных программ в порядке возрастания их сложности, которая примерно равна числу входящих в них примитивов. Другой процесс, имеющий более высокий уровень приоритета, создает новые программы, используя так называемые обобщающие преобразования (GT - generalizing transformations). Рис. 19 иллюстрирует взаимодействия этого модуля с другими модулями и процесс генерации нового знания. Когда PolyAnalyst находит статистически значимое решение, он генерирует отчет,

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

Применение обобщающих преобразований к существующей программе P порождает новую программу P ^gt , называемую GT-производной. Для каждой программы существует большое количество классов преобразований ее структуры, которые ведут к образованию ее GT-производной, не ухудшающей оценку программы Ev [P ^gt ] Ev [P]. Это свойство позволяет организовать GT-поиск в пространстве программ следующим образом. Когда процесс полного поиска находит программу для которой значение функционала Ev [P] достаточно мало, она становится "родителем" для поколения программ, создаваемых при помощи обобщающих преобразований из этой программы. Если одна из полученных программ показывает значительное уменьшение Ev [P], то она, в свою очередь, становится отправной точной для построения при помощи обобщающих преобразований новых программ, и так далее. Используя такой подход, можно построить довольно сложную программу за вполне разумный период времени. Этим описанием поиска обобщенных преобразований программ мы завершим обсуждение внутренних механизмов системы PolyAnalyst для случая произвольно организованных данных.

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

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

где A и B - многочлены. Основная, коммерческая версия PolyAnalyst использует два класса обобщающих преобразований:

1. Если Q - программа, возвращающая числовые значения, а C и D - многочлены, то программа

это GT-производная от P . В самом деле, если программа может быть представлена как многочлен, то коэффициенты этого многочлена являются ее входными переменными. Принимая все коэффициенты C и D равными нулю, мы получаем очевидное равенство R = P. А значит, варьируя коэффициенты полиномов C и D , скорее всего, удастся добиться лучшей оценки. В любом случае Ev [R] Ev [P];

2. Если мы умножим любой член в многочлене A или B на условную конструкцию if (S, a , b ), возвращающую либо a , либо b (в зависимости от булева значения, возвращаемого программой S; a и b - действительные параметры), то получившееся рациональное выражение будет GT-производной от P. Это справедливо, так как если a = b = 1, то if (S, a , b ) º 1.

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

Конечно же, как и любой другой метод, ядро PolyAnalyst не лишено недостатков. Во-первых, принятый алгоритм позволяет строить модели только для статических взаимосвязей в данных. Действительно, он ищет зависимости только между значением поля y_i целевой переменной и значениями полей x_ij той же самой записи. Реальные же данных часто определяются нелокальными динамическими связями - значениями некоторых из переменных в предыдущие моменты времени. Другими словами, значение y_i может зависеть не только от значений x той же самой записи, но и от значений x других записей. Если исследователь имеет представление о характерном для изучаемого явления времени, он может сдвинуть некоторые из параметров во времени на фиксированную величину (сдвинуть как целое соответствующие колонки исследуемой таблицы на несколько записей), однако в реальной жизни величины требуемых сдвигов практически всегда неизвестны. Во-вторых, алгоритмы PolyAnalyst ищут четко определенные, детерминистические связи. В реальной же жизни, как мы уже отмечали, неопределенность всегда присутствует и играет важную роль. Наконец, PolyAnalyst ищет простые аппроксимации зависимостей в "простых" данных (справедливости ради заметим, что это и есть область применения KDD). А найти зависимость для сложно структурированных данных, плохо аппроксимируемых рациональными выражениями (например, для спирали, типа показанной на рис. 7), - с подобными задачами PolyAnalyst может и не справиться. В подобной ситуации он, скорее всего, или вообще не найдет решения за разумный промежуток времени, или будет содержать большое число условных выражений, не характерных для существа задачи и потому трудно интерпретируемых исследователем. Другими словами, реальные возможности эволюционного программирования ограничены, и не ждите от него нереального.

Визуализация

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

Существует много способов графического представления модели, но избранный способ визуализации должен в максимальной степени облегчить процесс восприятия пользователем. Разные группы пользователей, специалисты в области data mining и специалисты в предметных областях, как правило, воспринимают модели с разных сторон, и потому системы KDD должны поддерживать разнообразные средства визуализации. Так, если пользователь - специалист в предметной области, а не в области моделирования и обработки данных, графические средства должны представлять информацию в максимально близкой ему форме, а, значит, в естественных, а не преобразованных в процессе исследования масштабах.

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

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

Инструментальные средства KDD

В настоящее время можно приобрести уже достаточно большое число отдельных систем и сопряженных с хранилищем данных аппаратно-технических комплексов, поддерживающих технологии KDD. Практически все коммерческие системы поддерживают архитектуру клиент-сервер, предоставляя пользователям возможность выполнять наиболее трудоемкие процедуры обработки данных на высокопроизводительном сервере. Следует отметить, что в основном это разработки западных компаний, главным образом, из США. Приятно отметить, что Российская компания "Мегапьютер Интеллидженс" прорвалась на этот сегмент рынка, во многом благодаря поддержке нетрадиционного для коммерческих систем метода data mining - эволюционного программирования, предоставляющего аналитику уникальные возможности. PolyAnalyst является одной из самых мощной систем data mining в мире, разработанных для Intel платформ и операционных систем Microsoft Windows NT, 95. Аналогичные системы data mining таких ведущих производителей, как IBM (Intelligent Miner, Data Miner), Silicon Graphics (SGI Miner), Integral Solutions (Clementine), SAS Institute (SAS) работают на средних и больших машинах и стоят от десятков до сотен тысяч долларов. Благодаря уникальной технологии эволюционного программирования, PolyAnalyst сочетает в себе высочайшую производительность "больших систем" с относительно низкой стоимостью, присущей программам для Windows.

Мы уже отмечали, что технологии KDD - бурно развивающаяся область. Поэтому подробно разбирать особенности отдельных систем не имеет большого смысла - к моменту, как эта книга дойдет до читателя, многое может измениться. Многие вопросы, связанные с возможностями использования любой конкретной системы, лучше разрешать в "режиме реального времени". Кроме того, большинство систем являют собой не одну программу, а семейство программ с разными возможностями. Системы KDD достаточно гибки и многообразны - заказчик может сам выбрать требующуюся ему конфигурацию системы. Чтобы помочь читателю сориентироваться в достаточно большом количестве различных аналитических систем KDD, мы приводим краткую сводку сравнительных характеристик семи наиболее распространенных и интересных, на наш взгляд, систем (табл. 2) - данные о производителе, диапазоне цен, архитектуре и поддерживаемых платформах, доступе к данным, услугах по поддержке и консультированию. Поддерживаемые этими системами методы data mining приведены в таблице 3. Более подробную информацию о этих системах можно получить на WEB-сайтах компаний (Табл. 4).

С другими системами заинтересованный читатель легко сможет ознакомиться, порывшись во всемирной паутине. Рекомендуем посетить сайты

KDD за работой

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

PolyAnalyst является системой data mining универсального назначения. Система включает набор математических модулей, называемых Машинами исследований (Exploration engines), реализующих большинство из рассмотренных выше data mining алгоритмов. В последней 4-й версии программы, выпущенной компанией «Мегапьютер» в 2000 году имеется 10 машин исследований- это:

· Поиск законов (FL) - эволюционное программирование

· Поиск зависимостей (FD) - универсальный препроцессор

· Классификация (CL) - на основе функции принадлежности

· Деревья решений (DS) - классификация на основе деревьев решений

· Кластеризация (FC) - многомерный кластеризатор

· PolyNet Predictor (PN) - полиномеальная нейронная сеть

· Многопараметрическая линейная регрессия (LR)

· Метод "ближайшего соседа" (MB) - гибрид алгоритма Nearest Neighbor и генетических алгоритмов

· Общая статистика (SS) - модуль суммарной статистики

Широкий спектр data mining алгоритмов позволяет анализировать данные «с разных сторон», используя в задачах те или иные математические модули или их комбинацию. Машины исследований работают совершенно автоматически, не требую вмешательства Человека. Вся сложная внутренняя математическая «кухня» скрыта от пользователя внутри модулей. Машины строят гипотезы о связях в данных, тестируют эти гипотезы на точность, значимость и простоту, выводят классификационные правила, находят многомерные кластеры, детектируют исключения, строят прогнозные модели.

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

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

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

Результаты работы системы легко интегрируются в системы поддержки решений и системы оперативной аналитической обработки. PolyAnalyst имеет свои собственные средства подготовки отчетов - так называемые Печатные формы (Print forms) Эти формы представляют собой настраиваемые пользователем шаблоны отчетов, в которые можно помещать различные объекты - графики, правила, тексты. Модели, выработанные PolyAnalyst, могут быть возвращаться в хранилища данных и применяться к новым данным для построения оперативных прогнозов.

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

Изначально Проект создается из внешних источников данных, которыми могут служить различные СУБД ( Oracle, DB2, Microsoft SQL Server итд), офисные приложения (Excel, Access) или плоские текстовые файлы с разными разделителями (CSV, TAB). Проект PolyAnalyst имеет внутренний формат представления и сохраняется в файле с расширением . prj . PolyAnalyst может работать с числовыми, целыми, логическими, категориальными и временными переменными.

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

Как уже отмечалось выше data mining является составной частью процесса KDD и представляет собой собственно анализ данных. Этапу data mining предшествуют этапы постановки задачи, сбора данных и предобработки данных. Если первые два этапа весьма специфичны для каждой конкретной задачи, то в отношении предобработки данных можно дать ряд универсальных рекомендаций.

1. Подготовка исходной таблицы. PolyAnalyst как практически и все существующие системы data mining работают с прямоугольными таблицами, в которых стоки или записи являются примерами для обучения программы, а столбцы содержат поля базы данных или атрибуты по терминологии, принятой в искусственном интеллекте. Программы data mining обучаются на исторических примерах, это означает, что в каждой строке таблицы должны содержаться «ответы» или значения целевых атрибутов, зависимость которых от входных переменных и является предметом изучения. На практике исходные данные могут храниться в исходной базе данных в виде нескольких таблиц, поэтому первым шагом в подготовке данных является сведение данных в единую таблицу и выделение целевых атрибутов.

2. Преобразование данных. Реальные данные зачастую представлены в совершенно непригодной для анализа форме. Так, например, наличие или отсутствие того или иного признака может кодироваться знаками «+» и «-», пропущенные значения могут обозначаться нулями, пол пациента - соответствующими буквами итд. Задача преобразования данных состоит в приведении значений каждого атрибута к единому типу данных. Если данный атрибут имеет только два вида значений, то он должен трактоваться как булевый, если это категориальный по смыслу атрибут, то он может кодироваться или числами, или текстом, но нельзя допускать смешения кодировок. Пропущенные значения нельзя кодировать каким-либо числом - эти клетки таблицы должны оставаться пустыми.

3. Очистка данных. Для эффективной работы любой системы data mining количество записей должно быть больше числа атрибутов, то есть таблица должна быть вытянута в длину. Медицинские базы данные часто содержат большое количество полей, сильно коррелирующих между собой. Необходимо, по возможности, уменьшить число входных переменных, оставляя только те, которые могут оказать наиболее сильное влияние на целевые атрибуты. Кроме этого необходимо исключить атрибуты, имеющие более 50% пропущенных значений, или маловариабильные или наоборот содержащие слишком много различных значений в случае категориального типа данных.

После такой предварительной подготовки данных можно приступить непосредственно к анализу данных или data mining. Рассмотрим несколько конкретных примеров.

Пример1. классификация на основе метода «деревья решений»:Цитологическая диагностика рака молочной железы (Данные предоставлены Dr. H. Wolberg, University of Wisconsin)

В задачах классификации требуется найти правила, позволяющие отнести записи базы данных к одному из двух или нескольких классов. Такого вида задачи характерны в диагностике заболеваний (здоров/болен), в дифференциальной диагностике (здоров/диагноз1/диагноз2) а также в задачах прогноза: Можно ли прогнозировать эффективность хирургического лечения, исходя из данных до операционного обследования? Можно ли спрогнозировать возникновение осложнений в послеоперационном периоде.

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

Табл. 5. Показатели цитологического обследования

Обозначение в таблице данных	наименование показателя	Шкала
ID	номер пробы	Число
Clump Thic	толщина аггрегации клеток	1 - 10
Us Size	однородность размера клеток	1 - 10
Us Shape	однороность формы клеток	1 - 10
MA	поверхностная адгезия	1 - 10
SECS	Размер единичной эпиталиальной клетки	1 - 10
Bari Nucl	обнаженные ядра	1 - 10
Bland Chrom	Хроматин	1 - 10
Normal Nucl	нормальные ядрышки	1 - 10
Mitos	Митоз	1 - 10
Class	Признак принадлежности к классу	(no-здоровая, yes-больная)

Работа с системой PolyAnalyst начинается с создания Проекта. Исходные данные храняться в текстовом файле с разделителям запятая (CSV формат). Запустив PolyAnalyst, выбираем пункт меню Project / New (Проект/Новый) и следуем указаниям Import Wizard (Мастера Импорта) (рис. 21). На этапе импорта данных важно внимательно следить за правильным назначением переменным типов данных. В нашем случае все атрибуты, кроме целевого «Class» являются числовыми, а целевой «Class» атрибут является булевым, то есть имеет значения «нет» (логический 0) для записей с неподтвержденным диагнозом «рак молочной железы» и «да» (логическая 1) для записей с подтвержденным диагнозом. После создания нового Проекта в окне дерева проекта появляется первый объект - корневая таблица данных, имеющая по умолчанию имя World (Мир) .

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

Для оценки качества получаемых моделей, кроме стандартных оценок, таких как ошибка классификации, статистическая значимость, обычно используют разбиение исходной таблице данных на обучающую и тестирующую выборки. Мы также воспользуемся этим приемом и, используя команду Sampling (Выборка) разобьем исходную таблицу случайным образом на две новых так, чтобы обучающая таблица составляла примерно 70 %, а таблица для тестирования классифицирующей модели - соответственно 30% от корневой таблицы. Теперь мы имеем три таблицы: исходную - World , для построения дерева решений - обучение и проверки результатов - тестирование .

Построение дерева решений на обучающей таблице

Рис.23. Запуск исследования из всплывающего меню

Рис. 24. Диалог запуска Машины исследований «деревья решений»

Для запуска исследования вызовем на обучающей таблице (рис. 23) всплывающее меню и выберем пункт Explore/ Decision Trees ( DT) (Исследовать/ Дерево решений). В диалоге запуска Машины исследований (рис.24) дважды щелкнем левой кнопкой мышки на атрибуте « Class» , сделав его целевым.

Деревья решений - достаточно быстрый алгоритм и для нашей небольшой таблицы результат получается практически мгновенно. В табл. 6 представлен текст отчета Машины исследований «Деревья решений» системы PolyAnalyst.

Текстовый отчет Машины ислледований «Деревья решений»

Результат для переменной: Class. Процесс запущен на таблице 'обучение' с включёнными атрибутами: Clump_Thic, Us_Size, Us_Shape, MA, SECS, Bari_Nucl, Bland_Chrom, Normal_Nucl, Mitos
Вычислительный процесс был запущен на локальном компьютере.

Общая ошибка классификации:	2.27%
% неопределенных предсказаний:	0.82%
Вероятность правильной классификации:	97.73%
Ошибка классификации для класса «Здоровая»:	3.47%
Ошибка классификации для класса «Больная»:	0.00%

реал./предск.	Нет	Да	Неопределено
Нет	306	11	2
Да	0	168	2

Мы видим, что найденное классификационное правило, характеризуется высокой точностью. Так, общая ошибка классификации слегка больше 2%. Менее 1% пациенток относятся к случаю неопределенной классификации (4 пацинтки). Ошибка классификации для пациенток с подтвержденным диагнозом составляет 0%, те все записи из базы данных, выделенные классификационным правилом, имеют признак подтвержденного диагноза. В 3. 5% случаев правило дает ошибку отнесения к классу «Здоровая». Это означает, что, используя найденное правило врач примерно в 3-х случаях из 100 может принять ошибочное решение о необходимости оперативного вмешательства. Иными словами классификационное правило обладает некоторой избыточностью, то есть пользуясь им клиницист в определенной степени перестраховывается.

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

Рассмотрим теперь суть самих правил, извлеченных из сырых данных методом «Деревья решений». На рис. 25 представлено дерево решений, полученное на обучающей таблице.

Рис. 25. Дерево решений для диагностики рака молочной железы

Как и обычное дерево, дерево решений имеет узлы ветвления (nodes) и конечные объекты - листья (leaves). Каждому узлу предписано условие разделения. Таким образом, дерево решений аналитически может быть представлено как совокупность неравенств, определяющих выбор пути по той или иной системе ветвей. Заметим, что дерево решений обычно рисуется в перевернутом виде, то есть корень находится сверху.

Рассмотрим в качестве примера правую систему ветвей дерева. Итак, в корне дерева у нас было 489 записей, из них 319 записей с неподтвержденным диагнозом и 170 - с подтвержденным диагнозом.

Условие Bari _ Nucl < 2 приводит к следующему узлу ветвления, в котором содержатся 308 записей ( 294 - здоровые и 14 - больные). Далее, если Us _ Size >=5, то это условие приводит териминальному листу, в который попадают 12 из 14 записей с подтвержденным диагнозом, причем выделение 12 записей происходит со 100% вероятностью (ошибка = 0%). Если же Us _ Size < 5 , то следующий узел содержит 296 записей (294- здоровые и 2 - больные), ошибка составляет 0.7%. И, наконец, этот узел приводит к двум терминальным листьям; если Clump _ Thic < =7 , то выделяются из 294 записей выделяются 292, все с неподтвержденным диагнозом, причем со 100% вероятностью. В противном случае, если Clump _ Thic > 7 , лист содержит 4 записи, которые данное дерево решений не способно отнести к тому или иному классу, те случаи неопределенности.

Проверка дерева решений на тестирующией таблице

Для окончательной проверки полученного правила воспользуемся тестирующей выборкой. Это важный момент исследования, так как позволяет провести независимую проверку полученных результатов и объективно оценить качество классификационного правила. В системе PolyAnalyst любое правило может быть непосредственно вычислено для каждой записи таблицы. Для этого на правиле DT _ Class правой кнопкой мышки вызовем всплывающее меню и выберем пункт Apply to /тестирование (Применить к таблице «тестирование») рис 26. Выполнение команды приводит к созданию в таблице тестирование новой колонки, содержащей логические значения, возвращаемые классификационным правилом для каждой записи тестирующей выборки.

Теперь остается подсчитать количество записей, для которых значения атрибута Class не совпадают со значениями вычисленного атрибута DT _ Class . Для этого воспользуемся Языком Символьных Правил (Symbolic Rule Language, SRL) программы PolyAnalyst и создадим новое логическое правило, возвращающее логическое значение «1», если значения атрибутов Class и DT _ Class не совпадают, и логическое значение «0» в противоположном случае. На языке SRL правило выглядит следующим образом (рис. 27). Теперь вычислим это правило командой Apply для табицы тестирование и запустим модуль Общей статистики ( Summary Statistics SS ) на таблице тестирование для посчета процента несовпадений значений атрибутов Class и DT _ Class (табл.7).

Таблица 7. Ошибки дерева решений на тестирующей выборке. Всего записей 210.

Дерево решений	Общая ошибка	Количество ошибочных случаев для класса «Здоровая»	Количество ошибочных случаев для класса «Больная»	Вероятность правильной классификации	Кол. Неопределенных случаев
Ошибки	5%	7	4	95%	2

Мы видим, что из 210 записей таблицы Правило DT _ Class вычислено для 208 записей, те две записи составляют неопределенные случаи. Общее количество несовпадений (случаи ошибочной классификации) составляет 11 (5%) записей. Процент ошибок для класса «Здоровые» составляет 3.8 %( 7 записей), а для класса «Больные» соответственно 1.2 % (4 записи).

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

Пример 2. Классификация на основе регрессионных методов

Рассмотрим теперь другой способ решения задач классификации также реализованный в системе PolyAnalyst. Он основан на построении линейных или нелинейных регрессионных моделей или функций принадлежности к классу. Для построения регрессионных моделей классификации в системе PolyAnalyst используются три разных математических модуля: Поиск Законов (FL), Множественныя Линейная Регрессия (LR) и рекурсивная (вложенная) полиномиальная сеть, PolyNet Predictor (PN).

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

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

Рассмотрим работу регрессионных методов классификации на том же примере диагностики рака молочной железы, а затем сравним результаты с деревом решений. Для запуска исследования на таблице «обучение» правой кнопкой мышки выберем пункт Explore / Classify ( CL ) (Исследовать/Классификация).

Рис. 28. Диалог запуска регрессионного метода классификации

В диалоге запуска метода выберем линейный процесс и дважды нажав левой кнопкой мышки на атрибуте Class пометим его как целевой (рис. 28). Линейные модули системы PolyAnalyst работают очень бысто. Практически мгновенно мы получим результат, представленный в таблице 8.

Табл. 8. Текстовый отчет модуля классификации системы PolyAnalyst

Текстовый отчет Машины ислледований «Классификация»

Если классификационная функция больше чем 0.3295, то Class ИСТИНА (class 1), иначе ЛОЖЬ (class 0).

Классификационная функция:
0.3295 < (-0.247871 +0.0335116*Clump_Thic +0.0210244*Us_Size +0.0152909*Us_Shape +0.00983962*SECS +0.0500264*Bari_Nucl +0.0223807*Bland_Chrom +0.0159002*Normal_Nucl)

Ошибка классификации для класса 0:				3.448 %
Ошибка классификации для класса 1:				0.5882 %
Общая ошибка классификации :				2.454 %
% неопределенных случаев:				0 %
Вероятность классификации:				97.55 %

дейст .\реальн.	0	1	Неопр.
0	308	11	0
1	1	169	0

R-квадрат	0.8376
Стандартное отклонение	0.1921
Количество записей	489
Индекс значимости	147.2

Имя	Коефф.	Стд. откл.	F - отношение	Вклад
Clump_Thic	0.03351	0.004239	62.51	0.5108
Us_Size	0.02102	0.007523	7.811	0.2106
Us_Shape	0.01529	0.007457	4.205	0.0192
SECS	0.00984	0.006506	2.287	0.004347
Bari_Nucl	0.05003	0.003717	181.1	0.0797
Bland_Chrom	0.02238	0.005981	14	0.007202
Normal_Nucl	0.0159	0.004585	12.03	0.004054

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

Табл. 9 Сравнение результатов классификации методом «Деревья решений» и «Линейной Регрессии» для обучающей выборки (всего 489 записей)

Дерево решений	Общая ошибка	Количество ошибочных случаев для класса «Здоровая»	Количество ошибочных случаев для класса «Больная»	Вероятность правильной классификации	Кол. Неопределенных случаев
Дерево решений	2.3%	11	0	97.7%	4
Регрессия	2.5%	11	1	97.6%	0

Для общей оценки достоверности классификационного правила в системе PolyAnalyst используется Индекс значимости. Индекс значимости - это безразмерная величина, вычисляемая как отношения стандартного отклонение результата, полученного для искусственно созданных данных в которых значения целевой переменной для разных записей случайным образом перемешаны к стандартному отклонению результата, полученного на реальных данных. Если стандартное отклонение, полученное на реальных данных приблизительно равно стандартному отклонению для случайно сгенерированных данных, то индекс значимости близок к 1, и такой результат исследования не может рассматриваться как значимый. Если же оно много меньше, чем для всех случайно сгенерированных таблиц, то индекс значимости намного больше 1 . В этом случае правило является значимым. На практике значимыми можно считать только те модели, для которых Индекс Значимости больше 2. Для нашего классификационного правила индекс значимости составляет 147. Это означает, что правило обладает очень высокой степенью достоверности.

Кроме общей оценки точности и достоверности классификационного правила текстовый отчет содержит и оценку вклада отдельных факторов (членов регрессионой модели). Вклад отдельных факторов оценивается как частичная сумма квадратов, вычисленная для данного члена регрессионной модели, а значимость вклада оценивается по его F-отношению. Чем больше обе эти величины, тем сильнее и достовернее данный фактор влияет на результат. Из отчета видно, что наиболее влияющими факторами для регрессионного правила являются Clump_ Thic, Us_ Size и Us_ Shape , что что согласуется с деревом решений. Наибольший по значимости вклад дает Bari_ Nucl, однако величина его невелика.

Проверка регрессионного классификационного правила таблице

Теперь воспользуемся описанной выше схемой проверки качества классификационной модели на тестирующей выборке. Для этого применим классификационное правило командой Apply (Применить) к таблице «тестирование», затем создадим и вычислим на для той же таблицы логическое правило, возвращающее логическую 1 в случае несовпадения значений классификационного правила со значениями целевой переменной Class и подсчитаем количество несовпадений, то есть количество ошибок. Теперь можно окончательно сравнить результаты обоих рассмотренных методов классификации (табл. 10).

Табл.10. Сравнение результатов классификации методом «Деревья решений» и «Линейной Регрессии» для тестирующей выборки (всего записей 210)

Метод	Общая ошибка	Количество ошибочных случаев для класса «Здоровая»	Количество ошибочных случаев для класса «Больная»	Вероятность правильной классификации	Кол. Неопределенных случаев
Дерево решений	5%	7	4	95%	2
Регрессия	3%	6	2	97%	0

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

Пример 3. Кластерный анализ: Продолжительность лечения в стационаре (Данные крупной ведомственной клиники)

В данном примере мы воспользуемся частью годового архивом крупной ведомственной клиники для того, чтобы проиллюстрировать работу модуля кластеризации ( Find Clusters FC ) системы PolyAanalyst. Исходный материал представляет собой небольшой фрагмент из истории болезни, включающий данные о поле и возрасте пациента, контингенте (работник ведомства, член семьи, пенсионер), код направившего учреждения, код отделения поступления, признак экстренной или плановой госпитализации, признак перевода в другое отделение и количество койко-дней в стационаре. (рис. 29).

Рис.29. Фрагмент таблицы World для задачи поиска кластеров

Модуль Find Clusters FC выделяет из исходной таблицы данных группы записей (кластеры, обладающих схожими свойствами и определяет набор переменных, для которого разделение на кластеры наиболее эффективно. Кластеризатор не требует задания целевой переменной, модуль запускается обычным способом из всплывающего меню на корневой таблице World командой Explore/ Cluster ( FC) (Исследовать/Кастеризация) .

Отчет метода представляет собой многомерную таблицу, в которой цветами закрашены области, отнесенные к разным кластерам (табл.11). Мы видим, что три переменных дают наилучшее разделение на два кластера. Это: возраст пациента, признак экстренной госпитализации и перевод из одного отделения в другое. Количество записей, отнесенных к обоим кластерам составляет 1461 из 3000 записей в таблице World , то есть практически 50 % всех записей. Значение P-value - вероятность того, что это случайный результат, исчезающе мала (8 e -111). Это говорит о высокой достоверности выделения кластеров.

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

Отчеты Summary Statistics для выделенных кластеров представлены соответственно в таблицах 12 и 13. Мы видим, что время пребывания в стационаре пациентов кластера 1 в среднем в 5 раз больше, чем в кластере 2 ( 32 +/- 7 против 6 +/- 2), это в основном пожилые люди (ср. возраст 66 лет против 36). Более 70% пациентов кластера 1 госпитализированы в плановом порядке, в то время как в кластере 2 почти 80% поступили экстренно. Только 3% записей в кластере 2 имеют признак перевода в другое отделение. Это косвенно свидетельствует о том, что эти пациенты поступили с правильным диагнозом и, по-видимому с острым характером заболевания.

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

Отчет Машины исследований «Кластеризация»

Процесс запущен на таблице World. С включенными атрибутами: пол, возр, конт, экстр, напр, рез, оп, перевод, дни

Вычислительный процесс был запущен на локальном компьютере.

Набор переменных, дающий наилучшее разделение на кластеры :	Возр экстр дни
P-value:	8.131e-111
Всего запсией в кластерах:	1461
Количество кластеров:	2

возр	экстр		Перевод

Row Heading				Column Heading

перевод\возр		(-, 33.5)			[33.5, 41.5)	[41.5, 47.5)	[47.5, 52.5)	[52.5, 62.5)	[62.5, +)
False points cluster		111 2			111 2	105 2	85 2	41 --	16 --
true points cluster		93 2			90 2	66 --	74 --	53 --	34 --
true points cluster		46 --			55 --	82 2	68 --	48 --	36 --
true points cluster		32 --			41 --	52 --	56 --	61 --	59 --
true points cluster		30 --			40 --	55 --	51 --	64 --	77 1
true points cluster		24 --			28 --	32 --	40 --	42 --	86 1

Числовые	Значений	Среднее	Ст. Откл.	Мин	Макс	Диапазон
возр	602	66.57	8.98	48	88	40
рез	602	2.958	0.2642	1	3	2
дни	602	32.03	7.3	16	206	190

Логические	Значений	Кол. 1	Кол. 0
пол	602	215 (35%)	387 (64%)
экстр	602	163 (27%)	439 (72%)
перевод	602	444 (73%)	158 (26%)

Категориальные:	Значений	Мода	Разл. Значений
конт		3	5
		1	112 (19.65%)
		2	209 (36.67%)
		3	236 (41.4%)
		4	8 (1.404%)
		5	5 (0.8772%)

напр	602	1	8
		1	358 (59.47%)
		12	1 (0.1661%)
		2	182 (30.23%)
		3	4 (0.6645%)
		4	10 (1.661%)
		5	12 (1.993%)
		6	31 (5.15%)
		7	4 (0.6645%)

Таблица 13. Общая статистика для кластера № 2

Числовые:	Значений	Среднее	Ст. Откл.	Мин	Макс	Диапазон
возр	859	36.05	9.176	15	52	37
рез	859	3	0	3	3	0
дни	859	6.001	2.08	1	15	14

Логические:	Значений	Кол. 1	Кол. 0
пол	859	235 (27%)	624 (72%)
экстр	859	677 (78%)	182 (21%)
перевод	859	27 (3%)	832 (96%)

Категориальные:	Значений	Мода	Разл. Значений
конт	832	1	5
		1	607 (72.96%)
		2	219 (26.32%)
		3	2 (0.2404%)
		4	3 (0.3606%)
		5	1 (0.1202%)

напр	859	2	7
		1	350 (40.75%)
		2	472 (54.95%)
		3	1 (0.1164%)
		4	14 (1.63%)
		5	2 (0.2328%)
		6	17 (1.979%)
		7	3 (0.3492%)

Пример 4. Использование метода «корзины покупателя» для выделение групп сопутствующих диагнозов в раннем послеоперационном периоде у кардиохирургических больных (Клинических данные для этого примера предоставлены Др. Е. Ройтманом из Научного Центра Хирургии РАМН)

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

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

Этап1

Этап2

Этап3

Этап4

Этап5

Этап6

Этап7

Поступление в отделение реанимации

Первые 3 часа после операции

3-6 часа

после операции

6-12 часов после операции

12-24

часов после операции

23-36 часов после операции

2-3 сутки
после операции

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

Битовая матрица, отражающая наличие или отсутствие того или иного признака (диагноз есть/нет, продукт куплен да/нет) является типовым представлением данных для алгоритма BA. Общая методика применения метода BA достаточно проста. Сначала на булевых данных выделяются группы совместно встречаемых признаков, а затем эти группы идентифицируются по внешним ,обычно числовым и категориальным данным.

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

Следующим шагом является создание из исходной таблицы World новых таблиц, содержащих только данные диагнозов соответственно для каждого из 7-ми этапов наблюдений. Для этого воспользуемся функцией создания новой таблицы. Вызовем правой кнопкой мышки на таблице World всплывающее меню и выберем пункт Create New (Создать Новую). В диалоге создания новой таблицы выделим только те переменные, которые относятся к данным диагнозов для 1-го этапа наблюдений (рис. 30). Аналогичным образом создадим таблицы диагнозов для остальных 6-ти этапов наблюдений. В результате этих операций в дереве проекта появятся 7 новых таблиц, содержащих только булевы переменные, соответствующие наличию или отсутствию того или иного диагностического признака отдельно для каждого этапа наблюдений (рис.31).

Рис. 30 Создание новой таблицы

Рис. 31. Дерево Проекта

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

В табл.15 представлен отчет модуля BA. Отчет содержит найденные группы совместно встречаемых диагнозов (группы совместно покупаемых продуктов в терминологии BA) и направленные ассоциативные правила, типа «если B1_t1 то и B5_t1». С помощью 3-х параметров настройки имеется возможность регулировать количество и размер групп, а также «силу» ассоциативных правил. Минимальная Поддержка ( Minimum Support) задает минимальный процент записей, в которых присутствует данная комбинация признаков. Минимальная достоверность ( Minimum Confidence) - это вероятность того, что если встречается данная комбинация признаков, то будет встречаться еще и другой признак или комбинация признаков. И, наконец, Усиление( Improvement) показывает во сколько раз вероятность ( Confidence) ассоциативного правила выше среднего уровня для всех записей.

Из отчета видно, что для таблицы Этап1 выделены 4 группы совместно встречаемых клинических диагнозов. Так, группа 1 (155 записей ) включает 2 диагноза:

D21 Сниженная дыхательная активность на вдохе;

Табл.15. Отчет модуля Basket Analysis (Корзина покупателя)

Последний результат был получен 18.07.2000, 15:14 для таблицы: этап1. 0 часов 0 минут прошло с момента старта. Процесс запущен на таблице 'этап1' с включёнными атрибутами: A1_t1, A2_t1, A3_t1, A4_t1, A5_t1, A6_t1, A7_t1, A8_t1, A9_t1, B1_t1, B2_t1, B3_t1, B4_t1, B5_t1, B6_t1, B7_t1, B8_t1, B9_t1, B10_t1, B11_t1, C1_t1, C2_t1, C3_t1, C4_t1, C5_t1, C6_t1, C7_t1, C8_t1, C9_t1, C10_t1, D1_t1, D2_t1, D3_t1, D4_t1, D5_t1, D6_t1, D7_t1, D8_t1, D9_t1, D10_t1, D11_t1, D12_t1, D13_t1, D14_t1, D15_t1, D16_t1, D18_t1, D19_t1, D20_t1, D21_t1, D22_t1, E1_t1, E2_t1, E3_t1, E4_t1, E5_t1, E6_t1, E7_t1, E8_t1, E9_t1, E10_t1, E11_t1

Вычислительный процесс был запущен на локальном компьютере.

Параметры процесса	Значение
Минимальная поддержка, %	10
Минимальное усиление	2
Минимальная достоверность, %	65

4 группы ассоциированных продуктов найдено.

группа #1 содержит 2 продукта
p_value: (log = -104.641081); поддержка 155
B5_t1
B1_t1

группа #2 содержит 5 продуктов
p_value: (log = -570.932275); поддержка 113
D2_t1
C8_t1
D7_t1
D11_t1
A1_t1

группа #3 содержит 3 продукта
p_value: (log = -86.857354); поддержка 178
C3_t1
B10_t1

группа #4 содержит 2 продукта
p_value: (log = -61.215857); поддержка 97
E8_t1
D21_t1

D1_t1

D6_t1

E11_t1

B1_t1

		Поддержка	Достоверность	Усиление
B1_t1	-> B5_t1	19.82%	79.08%	2.8630
B5_t1	-> B1_t1	19.82%	71.76%	2.8630
B10_t1	-> C3_t1	22.76%	76.07%	2.4379
C3_t1	-> B10_t1	22.76%	72.95%	2.4379

Важное новое знание могут содержать также и ассоциативные правила. В нашем примере мы видим, что в 20% случаев с вероятностью 80% анемия сопровождается дыхательным алкалозом. Метаболический алкалоз в почти 23% случаев с вероятностью более 75% сочетается с гипонатриемией.

Для каждой найденной группы автоматически создаются отдельные таблицы, которые подвергаются дальнейшему изучению в зависимости от поставленных задач другими Машинами исследований. Например, интересно посмотреть, имеются ли различия количестве случаев с осложненным течением послеопрационного периода между найденными группами. Используя команду Edit (Редактировать таблицу) , выключаем все поля с данными диагнозов и добавляем интересующие нас внешние данные (переменную, указывающую на осложненное течение послеоперационного периода), и запускаем модуль Общей статистики ( Summary Statistics ). В табл.16 приведена сводка результатов по осложнениям. Мы видим, что в группе наблюдается резкий всплеск осложнений, поэтому данная группа представляет особый интерес для дальнейшего изучения.

Таблица 16. Процент осложненных случаев для выделенных групп

№ группы	Коды диаг.	Неосл.	Осложн.
1	B5,B1	108 (70%)	47 (30%)
2	D2,C8, D7,D11,A1	65(57.5%)	48(42.5%)
3	C3,B10	133(57.5%)	45(25.3%)
4	E8,D21,D1,D6, E11,B1	17(15%)	96(85%)

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

Заключение

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

Повторим типовую схему применения рассмотренных методов KDD к реальным данным и перечислим ее основные стадии.

1. Постановка задачи. Анализируются задачи пользователя и особенности области приложения. Выбирается набор входных и выходных (целевых) параметров. Проводится анализ различных методов и систем KDD с точки зрения эффективности их применения к данной задаче.

2. Организация сбора и хранения данных. Создается хранилище данных, ориентированное на их анализ. Организуется схема сбора и обновления данных.

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

4. Собственно автоматический анализ данных (data mining). Применяются различные методы KDD, наиболее целесообразные для конкретной задачи. Возможно уточнение параметров найденной модели для достижения наилучших результатов.

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

6. Интеграция полученных знаний с другими компонентами информационной системы.

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

Литература

Для первоначального ознакомления

Амосов Н.М., Н.Г. Зайцев, В.Г. Мельников, А.А. Попов, В.П. Старчик, В.А. Шульга, В.М. Яненко. Медицинская информационная система. Киев, Наукова думка, 1975. 508 С.

Информатика в эпидемиологии. Сб. Отв.ред. В.И.Васильева. М., НИИЭМ им. Н.Ф. Гамалеи, 1990.

Медико-географическое районирование и прогнозирование здоровья популяций. Сб. Отв.ред. Н.Р. Деряпа. Новосибирск, Наука, 1981. 176 С.

Медицинская и научная информатика. Сб. Отв.ред. Н.М. Амосов. Киев, Институт кибернетики им. В.М. Глушкова, 1987. 108 С.

Стентон Г. Медико-биологическая статистика. М., Практика, 1999, 464С.

Фролов Ю.В. Интеллектуальные системы и управленческие решения. М., МГПУ, 2000, 294 С.

Berry M.J.A., G. Linoff. Data Mining Techniques. For Marketing, Sales and Customer Support. John Willey & Sons, Inc., 1997, 454 P.

Bigus J.P. Data mining with Neural Networks: Solving Business Problems - From Application Development to Decision Support. New York, McGraw-Hill, 1996.

Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. New York, Addison Wesley, 1989.

Introduction to Data Mining and Knowledge Discovery, 2nd edition. Two Crows Corp., 1998.

McNeill D. and P. Freiberger. Fuzzy Logic. Simon & Schuster, New York, 1993, 320

Для углубленного изучения

Гольцев А.Д. Функциональные свойства латерального торможения в слоях нейроподобных элементов. В сб.: Медицинская и научная информатика. Отв.ред. Н.М. Амосов. Киев, Институт кибернетики им. В.М. Глушкова, 1987, с. 16-20.

Ивахненко А.Г. и Мюллер Й.А., Самоорганизация прогнозирующих моделей. Киев, Наукова думка, 1985.

Кудряшев В.Э., Тарасов С.И., Пастухов Е.С. Нейросетевые технологии: основа прогностических медицинских систем будущего. В сб.: Клинико-инструментальная диагностика в хирургии. (IV симпозиум). М., 1996.

Лоскутов А.Ю. , А.С. Михайлов. Введение в синергетику: М. Наука, 1990, 272с.

Лукович В.В. О моделировании пороговой характеристики нейрона при стохастическом кодировании входных и выходных сигналов. В сб.: Медицинская и научная информатика. Отв.ред. Н.М. Амосов. Киев, Институт кибернетики им. В.М.Глушкова, 1987, с.10-15.

Статические и динамические экспертные системы. Учебное пособие. Э.В.Попов, И.Б.Фоминых, Е.Б.Кисель, М.Д.Шапот. - М., Финансы и статистика, 1995.

Факторный, дискриминантный и кластерный анализ. М., Финансы и статистика, 1989, 215 С.

Фролов Ю.В., Личко П.К., Буланова О.Е. Применение искусственных нейронных сетей для оценки психического состояния детей с отклонениями в развитии. В кн.: IX Международная конференция-выставка "Информационные технологии в образовании". Сборник трудов участников конференции. Часть III. М., МИФИ, 1999, С.197-199.

Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. Пер. с англ. М., Мир, 1992.

Farlow, S.J. (ed.) Self-organizing Method in Modelling: GMDH Type Algorithms. Statistics: Textbooks and Monographs, 54, 1984.

Holland J.H. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann.Arbor, MI, 1975.

Hopfield J.J. Neural networks and physical systems with emergent collective computation abilities. Proc.Nat.Acad.Sci. USA. 1982, v.79, pp.2554-2558.

Kiselev, M.V. (1994) PolyAnalyst - a machine discovery system inferring functional programs, In: Proceedings of AAAI Workshop on Knowledge Discovery in Databases'94, Seattle, pp. 237-249.

Kiselev, M.V., Ananyan, S. M., and Arseniev, S. B. (1997) Regression-Based Classification Methods and Their Comparison with Decision Tree Algorithms, In: Proceedings of 1st European Symposium on Principles of Data Mining and Knowledge Discovery, Trondheim, Norway, Springer, pp 134-144.

Kiselev, M.V., Arseniev, S.B. (1996) Discovery of numerical dependencies in form of rational expressions, in; Proceedings of ISMIS'96 (Ninth International Symposium on Methodologies for Intelligent Systems) poster session, Zakopane, Poland, pp. 134-145.

Klir, G. Is There More to Uncertainty Than Some Probability Theorists Might Have Us Believe. International Journal of General Systems, v.15, 1989, pp.347-78, V.17, 1991, pp.249-75.

Miihlenbein H., Schomisch M. and Born J. The parallel genetic algorithm as function optimizer. Proc. of the Fourth International conference on genetic algorithms. Morgan Kaufmann, San Mateo, CA, 1991, pp.53-60.

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

Schuermann J. and W. Doster. A decision-theoretic approach in hierarchical classifier design. Pattern Recognition, 17:359-369, 1984.

Sethi I. K. Entropy nets: From decision trees to neural networks. Proceeding of IEEE, 78(10), October 1990.

Shankar R. The GMDH. Master Thesis. Univ. of Delaware, 1972.Anderberg. D. Cluster Analysis for Applications. New York, Academic Press, 1973.

Shen Wei-Min (1990) Functional Transformations in AI Discovery Systems, Artif.Intell., v.41, pp 257-272.

Wang Q. R. and C. Y. Suen. Large tree classifier with heuristic search and global training. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(1):91-102, 1987.

Zembowicz, R., Zytkow, J. M. (1992) Discovery of Equations: Experimental Evaluation of Convergence, In: Proceedings of AAAI-92, AAAI Press, Menlo Park, CA, pp 70-75.

Zytkow J.M. and Zhu J. (1991) Application of Empirical Discovery in Knowledge Acquisition, In: Proceedings of Machine Learning - EWSL-91, pp 101-117.

ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ МЕДИЦИНСКИХ БАЗ ДАННЫХ

Содержание