Витяев Е.Е. Извлечение знаний из данных. Компьютерное познание. Модели когнитивных процессов (2006)

Подождите немного. Документ загружается.

191

Перейдем к построению закономерной модели систематики. Ее закон

представим в виде таблицы, в каждой строке которой стоят название

классов и значения признаков. Для выбора минимальной определяющей

совокупности систематики, рассмотрим различные сочетания определяю-

щих совокупностей классов.

Максимальная по количеству признаков минимальная определяющая

совокупность у цифры 8 (минимальное количество признаков 3). Значит,

определяющая совокупность систематики состоит не меньше чем из трех

признаков.

Минимальные определяющие совокупности классов не всегда

позволяют выявить минимальную совокупность систематики. Например,

минимальные определяющие совокупности цифры 3 это {P

, P

}, {¬P

}, тогда как определяющие совокупности, состоящие из трех признаков,

для этого же класса не содержат 7-го признака. Следовательно, стоит рас-

сматривать не только все определяющие совокупности длины 2, но и оп-

ределяющие совокупности длиной не более 3 признаков для каждого клас-

са.

Так как 2

= 8 меньше, чем число классов, то трех признаков будет не-

достаточно для однозначного восстановления класса. Поэтому рассматри-

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

лучим, что минимальная определяющая совокупность признаков для сис-

тематики это {P

, P

} (см. таблица 12). В этом случае она определя-

ется единственным образом.

Систематика для классов цифр индекса – это закон систематики пред-

Таблица 12

Систематика цифр

192

ставленный в таблица 12, а так же наборы закономерностей для каждого

класса и набор признаков класса.

По значениям признаков определяется класс. А далее, с помощью ми-

нимальных совокупностей, для каждого класса по закономерностям вос-

станавливаются значения всех остальных признаков.

§ 79. Применение в биоинформатике

Предложен принципиально новый подход к построению классифика-

ций нуклеотидных последовательностей на основе понятия «естествен-

ной» классификации. «Естественная» классификация базируется на прин-

ципе: объекты одного класса должны подчиняться одной группе законо-

мерностей, объекты разных классов – разным группам закономерностей.

На этом принципе разработан метод построения классификации, алгоритм

и программная система

GeneNatClass.

Разработан метод построения классификации, алгоритм и программная

система

GeneNatClass, позволяющая выделять «естественные» классы

подпоследовательностей – мотивы.

В настоящее время известно много принципов построения классифика-

ций: на основе гипотезы компактности и различных мер близости в неко-

тором пространстве, по сходству с эталонами, по суперцелям, по различ-

ным критериям качества классификации и функционалам качества, разде-

ления смесей распределений и другие.

Однако эти

подходы, как правило, не дают устойчивых законоподоб-

ных результатов. Поэтому их надо использовать осторожно, четко пони-

мая ограничения в выводах, которые можно делать на основе этих класси-

фикаций.

В отличие от упомянутых классификаций, цель «естественной» клас-

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

тых, латентных отношений, понятий и

закономерностей, которые важны

для построения теории предметной области и обладают предсказательной

силой. В этом смысле, «естественной является та, и только та классифика-

ция, которая выражает закон природы» [46] и обеспечивает:

– предсказание максимума свойств объекта по его месту в класси-

фикации;

– максимум общих утверждений о каждом классе;

– сохранение структуры классов при смене классификационных

признаков;

– объективность, надежность, прогностическая сила.

Конструктивный критерий «естественной» классификации предложен в

работе [14]: «Разбиение объектов на классы должно производиться в соот-

ветствии с закономерностями, которым удовлетворяют объекты. Точнее,

193

объекты одного класса должны подчиняться одной группе закономерно-

стей, а объекты разных классов разным группам закономерностей. Объек-

ты одного класса также должны обладать некоторой целостностью. Цело-

стность – взаимная согласованность закономерностей каждой группы по

взаимопредсказанию свойств объектов. У групп закономерностей могут

быть, кроме того, общие закономерности, устанавливающие связь призна-

ков объектов

из разных классов».

Множества закономерностей каждого класса выявляют закономерную

структуру объектов класса. Как показано в работе [29], закономерная

структура точно отражает процесс идеализации, поэтому саму эту струк-

туру мы называем идеальным объектом класса, а процедуру классифика-

ции – идеализацией.

Метод «естественной» классификации [14] можно разбить на следую-

щие этапы:

― представление первичных знаний и формирование обучающей вы-

борки;

― формализация различных типов отношений, важных с точки зрения

эксперта для описания выделенных объектов;

― построение признакового пространства объектов. Построение пере-

менных высшего порядка через примитивные переменные;

― обнаружение закономерностей;

― опецификация системы вложенных Rule Types;

― генерация различного вида статистических гипотез на основе Rule

Types и проверка их на обучающей выборке; поиск закономерностей, зна-

чимых для распознавания различных типов объектов;

― поиск всех закономерных структур (идеальных объектов) классов.

В качестве исходных данных используются нуклеотидные последова-

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

задать спецификацию объектов и их свойств. Множество признаков, изме-

ренных на этих объектах, определяет различные отношения между нук-

леотидами, их позициями, отрезками последовательностей или полными

нуклеотидными последовательностями и т

. д.

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

понимаем такое сочетание нескольких нуклеотидов в различных позициях,

при котором наблюдаются значительные увеличения распределения частот

встречаемости целевого нуклеотида.

Необходимо сразу же отметить, что метод обнаружения

закономерностей в качестве обучающей выборки требует матрицу объект-

признак. Нуклеотидные последовательности превращаются в матрицу

объект-признак следующим образом.

Расположим исходные последова-

тельности друг над другом, каждую в отдельной строке матрицы. При

194

этом первый столбец будет образован стартовыми нуклеотидами всех

последовательностей, второй столбец – вторыми нуклеотидами и т.д.

Значение внутри клетки этой матрицы соответствует коду нуклеотида: 1 –

A, 2 – T, 3 – G, 4 – C. В этом случае набор последовательностей

преобразуется в матрицу, содержащую столько строк, сколько

последовательностей в обучающей выборке.

Для поиска закономерностей в качестве целевого признака мы

перебираем все

столбцы матрицы по порядку. Закономерность, кроме

целевого признака, содержит один или более признаков, образующих

посылку закономерности. Посылка играет роль фильтрующего запроса,

который выбирает из исходной таблицы только те строки, в которых все

признаки посылки совпадают с таковыми в таблице. Правда, необходимо

заметить, что слово «совпадают» надо понимать в несколько расширенном

смысле, так как наряду с положительными значениями признаки посылки

могут принимать и отрицательные. В этом случае совпадение

фиксируется, если признак в таблице принимает любое другое значение, за

исключением нуля.

В общем случае множество признаков, значения которых определены

для конкретных объектов, может меняться. Формально такие данные мож-

но представить в виде XML описания

или множества реляционных таблиц.

Алгоритм обнаружения закономерностей. Для обнаружения законо-

мерностей используется реляционный подход к

Data Mining методам [121],

апробированный в системе

Discovery, позволяющей обнаруживать и про-

верять практически любые типы гипотез в языке первого порядка. Система

вложенных

Rule Types реализует стратегию все более точного и детального

анализа теории предметной области. Этот подход позволяет: 1) обрабаты-

вать данные любого типа, измеренные в любых шкалах (частичного по-

рядка, решеток, наименований, порядка, лог-линейных, древовидных, се-

тей, графов и т. д., а также смеси всех этих величин); 2) обнаруживать за-

коноподобные правила в условиях

шумов и малых обучающих выборок.

Простейшие закономерности на символьных последовательностях

имеют вид

ЕСЛИ (Pos

(α) = {A | T | G | C})

ε1

& ... & (Pos

(α) = {A | T | G | C})

εk

ТО (Pos

(α) = {A | T | G | C})

ε0

, (1)

где (Pos

(α) = {A | T | G | C})

εj

означает, что в позиции ij объекта α нахо-

дится (при ε

= 1) или не находится (при ε

= 0) одно из значений

{A | T | G | C}. Обозначим посылку правила (1), стоящую после условия

ЕСЛИ, через Premis(

£).

Реляционный подход к

Data Mining методам означает применение

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

угодно сложного уточнения проверяемой гипотезы. Например, для сим-

195

∑∑

−

)(

kjkj

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

признаки принадлежности нуклеотидов некоторому району, специфиче-

ские или допустимые расстояния между нуклеотидами, свойства самих

нуклеотидов и т. д. [33].

В качестве целевого признака закономерности перебираются все при-

знаки объектов. Посылка (Premis) играет роль фильтрующего запроса, ко-

торый выбирает из выборки те объекты, в которых все признаки посылки

имеют значения указанные в закономерности. Чтобы измерить силу зако-

номерности, мы сравниваем условное распределение значений целевого

при выполнении всех посылочных признаков с распределением значений

целевого признака на всех объектах. Чем сильнее закономерность, тем

больше отклонение условного распределения значений целевого признака

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

ния

является статистика χ

. Мы используем ее в варианте так называемого

нормированного Zχ

-отклонения:

N – всего строк в таблице; N

– число строк в таблице, где выполняется

(k = 1), не выполняется (k = 2) посылка; N

– число строк в таблице, где

встречаются значения целевого признака j

∈ {ATGC}; E

kj0

= N

/ N –

ожидаемое значение N

kj0

при условии независимости k и j

; N

kj0

– число

строк в таблице, где одновременно встречаются значения k и j

Проверка вероятностных неравенств (2) осуществляется данным

Zχ

-отклонением. Поиск закономерностей производится путем постепен-

ного наращивания посылки закономерности на один признак за каждый

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

мерность, чем короткая.

Построение идеальных объектов. Следующий этап анализа нуклео-

тидных последовательностей – построение идеальных образов реальных

последовательностей. Если объекты класса обладают некоторой целостно-

стью, то она проявится в структуре закономерных связей, связывающих

части / признаки объекта в единое целое. Структура закономерных связей

и будет определять связь частей / признаков объекта в единое целое.

Процедура идеализации сводится к тому, что

мы, используя все зако-

номерности, дополняем описание реального объекта дополнительными

значениями признаков, которые с высокой вероятностью предсказываются

по остальному набору признаков и сами хорошо предсказываются имею-

щимися, и, наоборот, удаляем те, которые не вписываются в общий ан-

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

−=

196

все необходимые значения и не будут отсеяны все случайные. Эта проце-

дура регулируется критерием взаимосогласованности закономерностей,

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

Программно процесс идеализации организован следующим образом:

для некоторой реальной последовательности создается матрица M, содер-

жащая столько строк, сколько нуклеотидов в последовательности, и 4

столбца, по одному для A, T, G и C. Просматривается

все множество зако-

номерностей R. Каждая применимая к последовательности закономер-

ность прибавляет свои 4 предсказания в виде Zχ

-отклонений (для A, T, G

и C) в 4 ячейки той строки, которая соответствует целевому признаку за-

кономерности. Если одно или больше из этих четырех значений содержат-

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

чает вклад, равный сумме предсказаний (Zχ

-отклонений) этих значений

(и только этих значений). Если же значение входит в последовательность с

отрицательным знаком, то и соответствующий вклад тоже берется с мину-

сом. Вхождение с отрицательным знаком означает, что в данной последо-

вательности соответствующего нуклеотида быть не должно. Ноль означа-

ет, что данный нуклеотид просто не входит в

последовательность, но при

этом не требуется его отсутствие.

Определим последовательности, являющиеся

идеальными объектами

классов

. Для этого введем критерий взаимной согласованности закономер-

ностей по предсказанию на этих объектах:

Γ(M) =

где R – множество закономерностей, δ(i

, j

) = 1 (-1), если в текущей пози-

ции i

последовательности состояние нуклеотида j

= {A | T | G | C} совпа-

дает (не совпадает при –1) со значением(ми) в самой последовательности.

Определение 38. Идеальным объектом класса будем называть такой

набор нуклеотидов <{A | T | G | C}{A | T | G | C}…{A | T | G | C}>, для ко-

торого критерий Γ(M) имеет локальный максимум (при удалении, добав-

лении любого из значений в этом наборе значение критерия строго

уменьшается). Запись {A|T|G|C} означает, что на некотором месте идеаль-

ного объекта может быть один или несколько нуклеотидов из указанных в

фигурных скобках.

Разработана программная система

GeneNatClass, реализующая описан-

ный выше подход к построению «естественных» классификаций. Разрабо-

танная система апробирована на задачах классификации сайтов сплайсин-

га и сайтов связывания транскрипционных факторов и показана ее эффек-

тивность.

),(Z

∑∑

197

Чтобы измерить силу закономерности, мы сравниваем распределение

значений целевого признака в таблице, просеянной сквозь сито

посылочных признаков, с распределением значений того же целевого

признака в исходной таблице данных. Чем сильнее закономерность, тем

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

простейших способов измерения такого отклонения является статистика

Хи-квадрат. Мы

ее и используем, но только в варианте нормированного,

так называемого Z-отклонения.

Что касается процедуры поиска и отбора закономерностей, то она

устроена по принципу естественного отбора – выживания наиболее

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

Для этого в программе выделяются три коллектора ограниченных

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

закономерностей. Причем эти коллекторы сортируют вставляемые в них

закономерности, так что наиболее сильные всегда оказывались наверху,

выталкивая из коллектора наиболее слабые. Z-отклонение самой слабой в

коллекторе закономерности является автоматически настраиваемым

Рис. 32

198

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

приспособленных.

Следующий этап анализа нуклеотидных последовательностей – по-

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

идеальные образы появляются как результат вероятностного логического

вывода из реальных последовательностей. Правила логического вывода,

которым следует метод естественной классификации, – это не что иное как

тот самый набор наиболее сильных

закономерностей, что возникли на

предыдущем шаге алгоритма.

Процесс превращения реальной последовательности в ее идеальный

образ протекает по шагам, заканчиваясь в том момент, когда никакое то-

чечное изменение последовательности уже не приводит к увеличению

критерия самосогласования закономерностей. Критерий самосогласования

закономерностей фиксирует, насколько хорошо предсказываются отдель-

ные нуклеотиды в текущей последовательности по остальным

нуклеоти-

дам той же самой последовательности. В процессе идеализации создается

матрица, содержащая столько строк, сколько нуклеотидов в последова-

тельности, и четыре столбца, по одному для A, T, G и C. Каждая примени-

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

ре предсказания в виде Z-отклонений (для A, T, G и C) в четыре ячейки

той строки, которая соответствует

целевому признаку. Если одно или

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

то суммарный критерий самосогласования получает вклад, равный сумме

предсказаний для всех этих значений. Если же значение входит в последо-

вательность с отрицательным знаком, то и соответствующий вклад тоже

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

данной последовательности соответствующего нуклеотида быть не долж-

но. Интерфейс программы естественной классификации приведен на Рис.

32. Программа применялась для классификации донорных сайтов

сплайсинга. Были обнаружены закономерности и классы, представленные

в третьем окне интерфейса программы.

199

ГЛАВА 9. ПРИНЦИПЫ РАБОТЫ МОЗГА

И МОДЕЛИ КОГНИТИВНЫХ ПРОЦЕССОВ

§ 80. Принципы и основания естественно-научных теорий.

Теории и принципы. Метод исследования

. Зададимся вопросом, ка-

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

рий, занимающихся исследованиями работы мозга? Так как работа мозга

многогранна, то в различных теориях она описывается с различных точек

зрения, в разных системах понятий и поэтому эти теории, как правило, не-

совместимы между собой. Например, такая ситуация имеет

место для тео-

рий восприятия. Достаточно образно она выражена А. Д. Логвиненко, в

предисловии к переводу книги [40]: «Первое знакомство с теориями вос-

приятия производит обескураживающее впечатление. Прежде всего, оше-

ломляют обилие теорий, их эклектическая пестрота и порой почти полная

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

вищно запутанном

нагромождении идей, подходов, направлений и т. п.,

ожидает еще один сюрприз. Оказывается, что никакой теории восприятия

нет, и никогда не было. Были более или менее удачные идеи, но не было

ни одной достаточно развитой теории».

Теории различны по вполне естественным причинам: у них различны

системы понятий, определяющие как бы «срез», «

точку зрения», сквозь

которую рассматривается объект исследования; у них различны априорные

предположения; различны методы исследования и используемые вспомо-

гательные теории и методы и т. д. Все это составляет исходный

базис ес-

тественно-научной теории (парадигму), определяющую предмет исследо-

вания, дальнейшие направления исследований и начальную естественно-

научную теорию. Дальнейшее развитие естественнонаучной теории осу-

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

тии этого базиса: выдвигаются и проверяются новые гипотезы, формули-

руемые в системе понятий; развивается теория добавлением подтвержден-

ных гипотез; делаются и экспериментально

проверяются новые следствия

теории и т. д. После накопления достаточного количества фактов делаются

обобщения в виде новых

постулатов, принципов, аксиом, уравнений и т. д.

Эти обобщения, как правило, делаются одновременно с введением новых

достаточно абстрактных понятий (теоретических терминов). Процесс

обобщения доходит в результате до достаточно абстрактных и, как прави-

ло, простых постулатов, принципов, аксиом или уравнений,

из которых

могут выводиться все остальные или основные утверждения теории. Такие

обобщения мы будем называть

принципами.

200

Принципами теории будем называть такие наиболее общие утвержде-

ния теории, из которых вытекают все остальные наиболее важные утвер-

ждения этой теории, т. е. принципом может быть только такое общее ут-

верждение (постулаты, аксиомы, уравнения) теории, из которого выводит-

ся почти вся теория. Если теория выводится из некоторого принципа, то

такую теорию будем

называть теорией-принципом.

Традиционно считается, что теория, развивающаяся в рамках некото-

рой парадигмы, является теорией («картиной», «срезом») своего базиса как

предмета исследований. При этом также считается, что принципы теории

являются принципами строения этого предмета исследований. Но это не

совсем так. Как правило, точный анализ принципа (в частности, математи-

ческий) вступает в противоречие с

базисом теории, и это не случайно. Де-

ло в том, что в принципах теории удается подняться над теми частностями

в предположениях, методах исследования, используемом аппарате и т. д.,

которые были сделаны в процессе создания теории, и тем самым прибли-

зиться к истине. В психологии, например, хорошо известно, что воспри-

ятие осуществляется

от целого к частному. Восприятие деталей и частно-

стей направляется и корректируется восприятием целого. То же самое

происходит и с теориями. Если теория развилась до теории-принципа, то

последняя ближе к «истине». Теоретические понятия, для того и вводятся

в теорию, чтобы углубить «точку зрения», «картину» объекта исследова-

ния и проникнуть

в глубь него, в его суть. Если при этом основания (базис)

теории вступает в противоречие с теорией-принципом, то надо менять ос-

нования, а не принципы. Однако никто не считает (за редчайшим исклю-

чением), что принципы важнее оснований

, поэтому найденное противоре-

чие не принимается научным сообществом, так как это требует пересмотра

оснований и, значит, существующей парадигмы. Но так как почти все счи-

тают, что существующая парадигма важнее принципов и ее пересмотр –

это целая «научная революция», то такой результат (вывод теории-

принципа) рассматривается просто как

парадокс, которому не придают

должного значения. Можно показать на множестве примеров, что надо

действовать как раз наоборот – пересматривать основания исходя из ре-

зультатов анализа принципа. Такой пересмотр действительно будет «

науч-

ной революцией

», но проведенной в направлении приближения к истине.

Такой путь развития теории, когда ищутся принципы, потом выводиться

теория-принцип, а затем производится «научная революция», путем пере-

смотра оснований, был бы регулярным методом развития теории, вклю-

чающим, как развитие теории в рамках одной парадигмы, так и смену па-

радигм.

Примерами принципов в

физике является принцип феноменологиче-

ской симметрии Ю. И. Кулакова, из которого выводятся практически все