Алгоритм формирования матрицы абсолютных частот

Объекты обучающей выборки описываются векторами (массивами) имеющихся у них признаков:

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

Отметим, что уже при расчете матрицы абсолютных частот закладываются основы для решения проблем 4 и 5. Способ формирования матрицы абсолютных частот можно рассматривать как многоканальную систему выделения полезного сигнала из шума. Представим себе, что все объекты, предъявляемые для формирования обобщенного образа некоторого класса в действительности являются различными реализациями одного объекта — «Эйдоса» (в смысле Платона), по-разному зашумленного различными случайными обстоятельствами (по-разному, т.к. это шум). И наша задача состоит в том, чтобы подавить этот шум и выделить из него то общее и существенное, что отличает объекты данного класса от объектов других классов. Учитывая, что шум чаще всего является «белым» и имеет свойство при суммировании с самим собой стремиться к нулю, а сигнал при этом наоборот возрастает пропорционально количеству слагаемых, то увеличение объема обучающей выборки (в случае если сигнал эргодичный, т. е. закономерности в предметной области не меняются) приводит ко все лучшему отношению сигнал/шум в матрице абсолютных частот, т. е. к выделению полезной информации из шума. Примерно так мы начинаем постепенно понимать смысл фразы, которую мы сразу не расслышали по телефону и несколько раз переспрашивали. При этом в повторах шум не позволяет понять то одну, то другую часть фразы, но в конце-концов за счет использования памяти и интеллектуальной обработки информации мы понимаем ее всю. Так и объекты, описанные признаками, можно рассматривать как зашумленные фразы, несущие нам информацию об обобщенных образах классов: «Эйдосах» [22], к которым они относятся. И эту информацию мы выделяем из шума при синтезе модели.

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

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

где:

Александр Александрович Харкевич.

упрощеннее выражение для нормировочного коэффициента, переводящего количество информации в биты [21], предложенного в работе [17], обоснованного в [9] и названного автором коэффициентом эмерджентности А. А. Харкевича в честь этого выдающегося советского ученого, внесшего огромный в клад в создание семантической теории информации и фактически предложившего количественную меру знаний, директора Института проблем передачи информации АН СССР академика АН СССР.

Среднеквадратичное отклонение количества знаний во всех значениях факторов о переходе объекта в j-е состояние от среднего количества знаний об этом в этих значениях Среднее количество знаний во всех значениях факторов о переходе объекта в j-е состояние Среднеквадратичное отклонение значений вектора описания объекта от среднего этих значений Среднее значений вектора описания объекта В таблице 3 использованы обозначения:

Nij — суммарное количество наблюдений в исследуемой выборке факта: «действовало i-е значение фактора и объект перешел в j-е состояние» ;

Nj — суммарное количество встреч различных значений факторов у объектов, перешедших в j-е состояние;

Ni — суммарное количество встреч i-го значения фактора у всех объектов исследуемой выборки;

N — суммарное количество встреч различных значений факторов у всех объектов исследуемой выборки.

Pij — условная вероятность перехода объекта в j-е состояние при условии действия на него i-го значения фактора;

Pj — безусловная вероятность перехода объекта в j-е состояние (вероятность самопроизвольного перехода или вероятность перехода, посчитанная по всей выборке, т. е. при действии любого значения фактора).

Pi — безусловная вероятность встречи i-го значения фактора или вероятность его встречи по всей выборке.

Таблица 4 Матрица знаний.

Здесь — это среднее количество знаний в i-м значении фактора:

Количественные значения коэффициентов Iij таблицы 4 являются знаниями о том, что «объект перейдет в j-е состояние» если «на объект действует i-е значение фактора» .

Утверждение о том, что это именно знания, а не данные или информация (или что-либо еще), требует специального серьезного обоснования, которое дано автором в работах [8, 9] и ряде других работ, начиная с [17] и здесь не приводится в связи с доступностью этих работ в Internet и достаточно большого объема этого обоснования.

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

Когда количество информации Iij>0 — i-й фактор способствует переходу объекта управления в j-е состояние, когда Iij<0 — препятствует этому переходу, когда же Iij=0 — никак не влияет на это. В векторе i-го фактора (строка матрицы информативностей) отображается, какое количество информации о переходе объекта управления в каждое из будущих состояний содержится в том факте, что данный фактор действует. В векторе j-го состояния класса (столбец матрицы информативностей) отображается, какое количество информации о переходе объекта управления в соответствующее состояние содержится в каждом из факторов.

Таким образом, матрица информативностей (таблица 4) является обобщенной таблицей решений, в которой входы (факторы) и выходы (будущие состояния объекта управления) связаны друг с другом не с помощью классических (Аристотелевских) импликаций, принимающих только значения: «Истина» и «Ложь», а различными значениями истинности, выраженными в битах и принимающими значения от положительного теоретически-максимально-возможного («Максимальная степень истинности»), до теоретически неограниченного отрицательного («Степень ложности»).

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

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

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

Нормировать частные критерии к нулю при отсутствии связи (когда условная вероятность наблюдения признака у объектов класса равно безусловной вероятности его наблюдения по всей выборке: Pij=Pi) необходимо, чтобы их было удобно использовать в аддитивном интегральном критерии. Это можно сделать разными способами. Например, в ROI (СИМ-4) из отношения условной вероятности к безусловной просто вычитается 1.

Критерий А. Харкевича тесно связан с критерием хи-квадрат. Рассмотрим выражение для частного критерия через абсолютные частоты в первой семантической информационной модели (СИМ-1):

Преобразуем это выражение, учитывая, что логарифм отношения равен разности логарифмов:

Сравнивая полученное выражение с выражением для частного критерия на основе хи-квадрат в СИМ-3 из таблицы 3.

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

— теоретически ожидаемое в соответствии с критерием хи-квадрат число таких наблюдений.

Также и логарифм отношения условной и безусловной вероятности СИМ-1 и СИМ-2 является разностью их логарифмов:

и отличается от разности этих вероятностей (СИМ-5) только постоянным для каждой модели множителем и применением логарифмической шкалы вместо линейной.

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

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

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

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

Рассмотрим предлагаемый алгоритм когнитивной кластеризации в графической и текстовой форме (рисунок 3):

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

• 1. Если не соответствуют размерности баз данных (БД) классов, признаков и информативностей, то выдать сообщение о необходимости пересинтеза модели.
• 2. Создать БД абсолютных частот: ABS_KLAS, информативностей: INF_KLAS, сходства классов: MSK_KLAS, а также БД учета объединения классов IterObj1. dbf и занести в них начальную информацию по текущей модели.

Данный режим реализован в модуле _5126 системы «Эйдос» и обеспечивает работу с любой из четырех моделей или со всеми этими моделями по очереди, поддерживаемых системой и приведенных в таблице 3. При этом в базах данных этих моделей ничего не изменяется.

• 3. Цикл по моделям до тех пор, пока есть похожие классы.
• 4. Рассчитать матрицу сходства классов MSK_KLAS в текущей модели.

Эта матрица рассчитываемся на основе матрицы знаний модели, заданной при запуске режима (СИМ-1 — СИМ-4), путем расчета корреляции обобщенных образов классов (т.е. векторов или профилей классов).

5. Найти пару наиболее похожих классов в матрице сходства.

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

6. Объединить 2 класса с наибольшим уровнем сходства.

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

• 7. Отразить информацию об объединении классов в БД IterObj1.dbf.
• 8. Конец цикла итераций. Проверить критерий остановки и перейти на продолжение итераций (п.9) или на окончание работы (п.10).
• 9. Пересчитать в базе данных сходства классов (MSK_KLAS) только изменившиеся столбцы и строки. Конец цикла по моделям.
• 10. Нарисовать дерево объединения классов, псевдографическое: /TXT/AgKlastK.txt и графическое: /PCX/AGLKLAST/TrK-#-##.GIF.

Далее рассмотрим работу предлагаемой математической модели и реализующего ее алгоритма когнитивной кластеризации на простом численном примере.

Численный пример основан на варианте той же задачи из работы [7], которая использовалась в статье [8]. В книге Д. Мичи и Р. Джонстона «Компьютер — творец» [7] эта задача приводится (на страницах: 205−208) в качестве примера задачи, решаемой методами искусственного интеллекта. Авторами этой задачи являются Рышард Михальски и Джеймс Ларсон. Суть этой задачи сводится к тому, чтобы выработать правила, обеспечивающие идентификацию и классификацию железнодорожных составов на основе их формализованных описаний (рисунок 2).

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

Этапы АСК-анализа предметной области В работе [9] предложены следующие этапы АСК-анализа предметной области:

• 1. Когнитивная структуризация предметной области, при которой определяется, что мы хотим прогнозировать и на основе чего (конструирование классификационных и описательных шкал).
• 2. Формализация предметной области:
  • — разработка градаций классификационных и описательных шкал (номинального, порядкового и числового типа);
  • — использование разработанных на предыдущих этапах классификационных и описательных шкал и градаций для формального описания (кодирования) исходных данных (исследуемой выборки).
• 3. Синтез и верификация (оценка степени адекватности) модели.
• 4. Если модель адекватна, то ее использование для решения задач идентификации, прогнозирования и принятия решений, а также для исследования моделируемой предметной области.

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