Методы, ориентированные на данные

В системе используются два математических метода,

ориентированных на данные:

Метод естественных ортогональных составляющих

Этот метод известен давно. Библиографию можно найти, например, в [160].

Именно в этом пространстве (F1,F2,...) следует проводить кластеризацию. Кластерами здесь будут группы объектов, локализованные вручную экспертом в одном или нескольких подпространствах. Эти подпространства строятся на парах векторов (Fi,Fj).

Метод построения дендрита

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

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

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

Назначение

Система Visual HCA предназначена для решения слабоформализованных задач на основе человеко-машинных процедур классификации.

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

Подготовка данных

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

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

Учет качественных данных

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

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

Описание опций программы

На рисунке показан набор опций задаваемых в программе:

Рис.

• Автосохранение векторов - сохранять вектора при расчете в файле.

• Автосохранение форм - сохранять формы объектов при сохранении файла, при чтении файла формы объектов будут прочитаны.

• Автосохранение цветов - сохранять цвета объектов при сохранении файла, при чтении файла цвета объектов будут прочитаны.

• Файл векторов - использовать существующий файл векторов при расчетах факторов.

• Файл для карты - указать файл для показа объектов в топо-окне.

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

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

• Экспоненциальная шкала - установить экспоненциальную шкалу показа минимальных расстояний на графе.

• Точность расчета - при расчете факторов.

• Шкала для эллипсов - размер эллипсов %.

Поиск кластеров в факторном пространстве

Предполагается, что в каком-либо подпространстве (Fi x Fj) удастся локализовать группы объектов, т.е. выделить кластер. Однако, заранее неизвестно, в какой паре (Fi x Fj) это разделение будет наиболее четким. Кроме того, заранее неизвестен также характер группировки: это могут быть линейные кластеры, кластеры с явно выраженным центром и т. п.

Поэтому эксперт просматривает различные подпространства, натянутые на вектора (Fi,Fj), и отыскивает те подпространства, где это разделение будет наиболее четким. В обнаруженном подпространстве эксперт отмечает точки выбранных кластеров различными цветами. В Visual HCA имеется окно “Факторный анализ”, где представляются кластеры в факторных пространствах. Название окна подчеркивает, что по осям откладываются координаты, имеющие смысл весов соответствующего фактора. На рис.8 показано окно “Факторный анализ” для факторов (F2,F4). Эти факторы играют роль ортов, по осям которых отложены весовые коэффициенты.

На этом же рисунке показаны объекты в факторном пространстве. Объекты, принадлежащие различным группам, окрашены в различные

цвета. На рисунке 8 видно, что выделяются 4 различные группы объектов. Естественно, количество атрибутов для объекта и фактора совпадают.

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

Рис. 8. Эллипсы рассеяния в факторном пространстве

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

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

Рис. 9. Объекты в 3D факторном пространстве

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

На рисунке 10 можно видеть величину значимости фактора (главное значение для данного фактора относительно максимального) - магнитуду. Если магнитуда фактора мала, влияние его незначительно и им можно пренебречь.

Рис. 10. Графики факторов и объектов

к началу нумерации.

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

Поиск кластеров на дендрите и графе

В окне на рисунке 11 показан дендрит, построенный по всему

множеству объектов. Расстояние между объектами здесь определяется в

Рис. 11. Граф-дендрит

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

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

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

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

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

Дерево кластеров

На нижнем рисунке 12 показаны способы объединения объектов в кластеры, предлагаемые в режиме ‘Дерево кластеров’.

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

быстро окрасить в любой цвет выбранный кластер объектов или конкретный

Рис. 12. Объединение объектов в группы

объект из кластера.

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

Уровень кластеризации показывает число шагов по объединению

Рис. 13. Дерево кластеров

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

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

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

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

учитываемого при объединении первичных кластеров, увеличивается (проявляются все более тонкие связи). В режиме 'УЧИТЫВАТЬ УСТОЙЧИВОСТЬ' объединение кластеров происходит только тогда, когда внутренний потенциал взаимосвязи меньше внешнего потенциала взаимосвязи ко всем другим кластерам. То есть решение об объединении принимается с учетом всех проявившихся (на данном уровне ползунка) связей. Кластеры объединяются по принципу максимального притяжения. После каждого акта объединения кластеров происходит полный перерасчет потенциалов взаимосвязи между всеми кластерами. Далее процедура повторяется, пока число устойчивых кластеров не станет постоянным.

Sij = 1∕(1+R(i,j)∕maxmin)

где Sij - ПОТЕНЦИАЛ ВЗАИМОСВЯЗИ, R(i,j) - расстояние между объектами i и j, Maxmin - граница максимального расстояния (положение ползунка).

S = S_in/(Sin+Sout)

где S - УСТОЙЧИВОСТЬ, S_In - ПОТЕНЦИАЛ ВЗАИМОСВЯЗИ объектов кластера между собой , S_out - ПОТЕНЦИАЛ ВЗАИМОСВЯЗИ объектов кластера и остальных объектов.

Регулируя параметр 'МИНИМАЛЬНАЯ УСТОЙЧИВОСТЬ', мы изменяем схемы объединения кластеров. Параметр 'МИНИМАЛЬНОЕ ЧИСЛО КЛАСТЕРОВ' служит для определения границы, после достижения которой, движение назад (разъединение кластеров при движении ползунка вниз) происходить не будет. Например, если число первичных кластеров = 100, а 'МИНИМАЛЬНОЕ ЧИСЛО КЛАСТЕРОВ'= 40 , то при движении ползунка вверх будет происходить объединение кластеров, но если их число

все еще больше 40, то при движении ползунка вниз разъединения кластеров происходить не будет.

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

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

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

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

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

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

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

Методика классификации и кластеризации

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

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

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

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

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

В общем случае все атрибуты могут быть разделены на 3 группы. К первой группе относятся атрибуты, сопоставимые по величине для всех объектов. Ко второй группе - атрибуты, существенные только для значительной части (не менее 10-30%) объектов. К третьей группе относятся редкие атрибуты(менее 1-5% объектов).Первая группа атрибутов появляется в связи с переходом от изучения системы в подсистему. Эти атрибуты полезно выделить в отдельную совокупность, поскольку по ним все объекты выглядят почти одинаково. Решение проблем, связанных с этими атрибутами лежит либо на верхнем уровне подсистемы, либо в системе более высокого уровня. Без выделения этих атрибутов они будут маскировать специфику каждого из объектов, затруднять разбиение на кластеры. В этом плане должны быть удалены и редкие атрибуты. В кластерах они проявляются своим расположением в окрестности нуля почти во всех факторных пространствах. Нулевые и малые значения редких атрибутов делают большинство объектов неразличимыми между собой в подпространстве этих атрибутов. Поэтому при решении задачи классификации и типизации, при выделении массовых свойств по которым

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

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

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

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

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

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

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

• различных метрик;

• с удалением малоинформативной части атрибутов;

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

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

Рис. 14. Матрица генетических измерений народов мира

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

Рис. 15. Объекты в топо-окне и в факторном пространстве

Наблюдение кластеров в топо-окне

Объекты, имеющие топографическую привязку, т.е. координаты на плоскости, могут быть представлены в окне 'Map'.

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

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

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

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

Приведенные примеры продемонстрировали возможности Visual HCA, как средства решения слабо-формализованных задач. Следует подчеркнуть, еще раз, что получение и осмысливание результатов в этих примерах потребовало от нескольких часов до 2 дней работы эксперта. Здесь, конечно, не учитывается время на сбор и ввод данных.

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

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

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

2.4.