Метод когнитивной кластеризации или кластеризация на основе знаний (кластеризация в системно-когнитивном анализе и интеллектуальной системе "Эйдос")

Существуют и другие метрики, в частности: квадрат евклидова расстояния, расстояние городских кварталов (манхэттенское расстояние), расстояние Чебышева, степенное расстояние, процент несогласия, метрики Рао, Хемминга, Роджерса-Танимото, Жаккара, Гауэра, Воронина, Миркина, Брея-Кертиса, Канберровская и многие другие [2, 4]. Когда корреляции между переменными равны нулю, расстояние Махаланобиса эквивалентно квадрату евклидового расстояния [2]. Это означает, что метрику Махаланобиса можно считать обобщением евклидовой метрики для неортонормированных пространств.

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

Таким образом, первое требование к исходным данным порождает две проблемы:

Проблема 1.1 выбора метрики, корректной для неортонормированных пространств.

Проблема 1.2 ортонормирования пространства.

Второе требование (безразмерности показателей) вытекает из того, что выбор единиц измерения по осям существенно влияет на результаты кластеризации. Казалось бы, одного этого должно быть достаточно для того, чтобы не делать этого, т.к. выбор единиц измерения, по сути, произволен (определяется исследователем), вследствие чего и результаты кластеризации, вместо того чтобы объективно отражать структуру данных и описываемой ими объективной реальности, также становятся произвольными и зависящими не только от самой исследуемой реальности, но и от произвола исследователя (причем неизвестно от чего больше: от реальности или исследователя). По сути, автоматизированная система кластеризации превращается в этих условиях из инструмента исследования структуры объективной реальности в автоматизированный инструмент рисования таких дендрограмм, какие больше нравятся пользователю. Непонятно также, какой содержательный смысл могут иметь, например корни квадратные из сумм квадратов разностей координат объектов, классов или кластеров, измеряемых в различных единицах измерения. Разве корректно складывать величины даже одного рода, измеряемые в различных единицах измерения, а тем более разного рода? Даже если сложить величины одного рода, но измеренные в разных единицах измерения, например расстояния от школы до подъезда дома 1.2 (километра), и от подъезда дома до квартиры 25 (метров), то получится 26,2 непонятно чего. Если же сложить разнородные по смыслу величины, т.е. величины различной природы, такие, например, как квадрат разности веса студентов с квадратом разности их роста, возраста, успеваемости и т.д., а потом еще извлечь из этой суммы квадратный корень, то получится просто бессмысленная величина, которая в традиционном кластерном анализе почему-то называется «Евклидово расстояние». В школе на уроке физики в 8-м классе за подобные действия сразу бы поставили «Неуд». Однако, как это ни удивительно, то, что «не прошло бы» на уроке физики в средней школе является вполне устоявшейся практикой в статистике и ее научных применениях.

В подтверждение тому, что подобная практика действительно существует, авторы не могут удержаться от искушения и не привести пространную цитату из работы [4]: «Заметим, что евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным. Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. К примеру, если одна из осей измерена в сантиметрах, а вы потом переведете ее в миллиметры (умножая значения на 10), то окончательное евклидово расстояние (или квадрат евклидова расстояния), вычисляемое по координатам, сильно изменится, и, как следствие, результаты кластерного анализа могут сильно отличаться от предыдущих.» (выделено нами, авт.). В работе [4] просто констатируется факт этой ситуации, но ему не дается никакой оценки. Наша же оценка этой практике по перечисленным выше причинам отрицательная. Приведем еще цитату из той же работы [4]: «Степенное расстояние. Иногда желают (!!!?)прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Это может быть достигнуто с использованием степенного расстояния. Степенное расстояние вычисляется по формуле:

расстояние(x,y) = (i |xi - yi|p)1/r

где r и p - параметры, определяемые пользователем. Несколько примеров вычислений могут показать, как "работает" эта мера. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра - r и p, равны двум, то это расстояние совпадает с расстоянием Евклида». Мы считаем, что еще какие-то комментарии здесь излишни.

Таким образом, второе требование к исходным данным порождает следующую проблему 2.1:

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

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

Проблема 2.2 формализации описаний объектов, имеющих как количественные, так и качественные признаки.

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

Таким образом, 3-е требование к исходным данным порождает проблемы 3.1., 3.2. и 3.3.:

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

Проблема 3.2 нормализации исходных данных.

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

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

Таким образом, четвертое и пятое требования приводят к двум проблемам:

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

Проблема 5 разработки метода кластерного анализа, математическая модель и алгоритм и которого обеспечивали бы выявление «выбросов» (артефактов) в исходных данных и позволяли либо вообще не показывать их в дендрограммах, либо показывать, но так, чтобы было наглядно видно, что это артефакты.

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

Проблема 1.1 выбора метрики, корректной для неортонормированных пространств.

Проблема 1.2 ортонормирования пространства.

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

Проблема 2.2 формализации описаний объектов, имеющих как количественные, так и качественные признаки.

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

Проблема 3.2 нормализации исходных данных.

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

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

Проблема 5 разработки метода кластерного анализа, математическая модель и алгоритм и которого обеспечивали бы выявление «выбросов» (артефактов) в исходных данных и позволяли либо вообще не показывать их в дендрограммах, либо показывать, но так, чтобы было наглядно видно, что это артефакты.

Сделать это удобнее всего, рассматривая какие ответы предлагают классические методы кластерного анализа на сформулированные в в работе [2] вопросы:

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

- как вычислять расстояние до таких "полиобъектных" кластеров от "монокластеров" и между "полиобъектными" кластерами.

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

1. Каким методом вычислять координаты кластера, состоящего из одного и более объектов, т.е. каким образом объединять объекты в кластеры.

2. Каким методом сравнивать кластеры, т.е. как вычислять расстояния между кластерами, состоящими из различного количества объектов (одного и более).

3. Каким методом объединять кластеры, т.е. формировать обобщенные («многообъектные») кластеры.

Вопрос 1-й. Чаше всего ни в теории и математических моделях кластерного анализа, ни на практике между кластером, состоящим из одного объекта («моноообъектным» кластером) и самим объектом не делается никакого различия, т.е. считается, что это одно и тоже. «В агломеративно-иерархических методах (aggomerative hierarhical algorithms) … первоначально все объекты (наблюдения) рассматриваются как отдельные, самостоятельные кластеры состоящие всего лишь из одного элемента» [2]. В работе [4] также говорится, что древовидная «Диаграмма начинается с каждого объекта в классе (в левой части диаграммы)». Это решение сразу же порождает многие из вышеперечисленных проблем (1.1., 1.2., 2.1, 2.2), т.к. объекты могут быть описаны как количественными, так и качественными признаками различной природы, измеряемыми в различных единицах измерения, причем эти признаки взаимосвязаны (коррелируют) между собой.

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

Другое предложение по решению проблемы размерностей (2.1) основано на четком пожимании того, что изменение единиц измерения переменной меняет среднее ее значений и их разброс от этого среднего. Например, переход от сантиметров к миллиметрам увеличивает среднее и среднее отклонение от среднего в 10 раз. Речь идет о методе нормализации или стандартизации исходных данных, когда значения переменных заменяются их стандартизированными значения или z-вкладами [15]. Z-вклад показывает, сколько стандартных отклонений отделяет данное наблюдение от среднего значения:

,

где - значение данного наблюдения, - среднее, - стандартное

отклонение. Однако этот метод имеет серьезный недостаток, описанный в литературе [2, 4, 15]. Дело в том, что нормализация значений переменных приводит к тому, что независимо от значений их среднего и вариабельности до нормализации (т.е. значимости, измеряемой стандартным отклонением), после нормализации среднее становится равным нулю, а стандартное отклонение 1. Это значит, что нормализация выравнивает средние и отклонения по всем переменным, снижая, таким образом, вес значимых переменных, оказывающих большое влияние на объект, и завышая роль малозначимых переменных, оказывающих меньшее влияние и искажая, таким образом, картину. На взгляд авторов это на вряд ли приемлемо. Другой важный недостаток, который в отличие от первого не отмечается в специальной литературе, состоит в том, что стандартизированные значения сложно как-то содержательно интерпретировать, т.е. устранение влияния единиц измерения достигается ценой потери смысла переменных, который как раз и содержался в единицах их измерения. В результате нормализации все переменные становятся как бы «на одно лицо». Это также недопустимо. Таким образом, можно обоснованно сделать вывод о том, нормализация и стандартизация исходных данных - это весьма радикальное решение проблемы 2.1 «в лоб и в корне», но решение неприемлемо дорогой ценой.

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

1. Вообще не формировать обобщенных классов или кластеров из объектов, а на всех этапах кластеризации рассматривать только сами первичные объекты.

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

О 1-м варианте ответа в работе [4] говорится: «Диаграмма начинается с каждого объекта в классе (в левой части диаграммы). Теперь представим себе, что постепенно (очень малыми шагами) вы "ослабляете" ваш критерий о том, какие объекты являются уникальными, а какие нет. Другими словами, вы понижаете порог, относящийся к решению об объединении двух или более объектов в один кластер. В результате, вы связываете вместе всё большее и большее число объектов и агрегируете (объединяете) все больше и больше кластеров, состоящих из все сильнее различающихся элементов». Этот подход, когда кластеры реально не формируются, т.к. им не соответствуют какие-либо конструкции математической модели, представляется авторам сомнительным, т.к., во-первых, как было показано выше, это порождает проблемы 1.1., 1.2., 2.1, 2.2, а во-вторых, никак не решает проблемы 3.1, 3.2, 3.3, 4 и 5. Между тем сам способ формирования кластеров из объектов, по мнению авторов, призван стать средством решения всех этих проблем.

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

Вопрос 2-й. В работах [2, 3, 4] и других по кластерному анализу описывается большое количество различных мер и методов, которые можно применить как для измерения расстояний между кластерами, так и расстояний от объекта до кластеров. Например, в невзвешенном центроидном методе при определении расстояния от объекта до кластера, по сути, определяется расстояние до его центра [4]. В методе невзвешенного попарного среднего расстояние между двумя кластерами вычисляется как среднее расстояние между всеми парами объектов в них [4]. При этом, как правило, не решаются перечисленные выше проблемы, т.к. не устраняются их причины: а именно средние вычисляются на основе мер расстояния, корректных только для ортонормированных пространств и при этом часто используются размерные или нормализованные формы представления признаков объектов, не формализуется описание объектов, обладающих как количественными, так и качественными признаками. Ответ на 3-й вопрос является продолжением ответа на 2-й вопрос.

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

Далее рассмотрим вариант решения некоторых из сформулированных выше проблем кластерного анализа, предлагаемый в АСК-анализе и реализованный в интеллектуальной системе «Эйдос».

Обратимся к эпиграфам к данной статье: «Мышление - это обобщение, абстрагирование, сравнение, и классификация» (Патанджали, II в. до н. э.), «Истинное знание - это знание причин» (Френсис Бэкон, 1561-1626 гг.). Итак, мышление, как процесс это [в том числе] классификация, результатом же мышления является знание, причем истинное знание есть знание причин. Истинное мышление есть мышление, дающее истинное знание. Соответственно ложное мышление - это мышление, приводящее к заблуждениям. Поэтому истинное мышление - это [в том числе] истинная (правильная, адекватная) классификация объектов по причинам их поведения, т.е. по системе их детерминации. Правильной классификацией будем считать ту, которая совпадает с классификацией экспертов, основанной на их высоком уровне компетенции, профессиональной интуиции и большом практическом опыте.

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

В свою очередь классификация (в т.ч. кластерный анализ) как процесс основана на обобщении и сравнении. В монографии 2002 года [9] предлагается пирамида иерархической структуры процесса познания, входящая в базовую когнитивную концепцию (рисунок 1):

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

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

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

Первоначально в матрице абсолютных частот все значения равны нулю. Затем организуется цикл по объектам обучающей выборки. Если предъявленного объекта относящегося к 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 Матрица знаний