Дивизимные и агломеративные стратегии поиска альтернатив
В общей (нестрогой) постановке проблема автоматической классификации объектов заключается в том, чтобы всю анализируемую совокупность объектов разбить на сравнительно небольшое число (заранее известное или нет) однородных, в определенном смысле, групп или классов таким образом, чтобы объекты, принадлежащие одному классу, находились бы на сравнительно небольших расстояниях друг от друга в пространстве признаков, которыми описываются эти объекты. Предполагается, что геометрическая близость двух или нескольких точек в этом пространстве означает близость «физических» состояний соответствующих объектов, их однородность. Полученные в результате разбиения классы часто называют кластерами (таксонами, образами), а методы их нахождения соответственно кластерным анализом (распознаванием образов с самообучением).
Кластерный анализ – это многомерная статистическая процедура, упорядочивающая исходные данные (объекты) в сравнительно однородные группы. Особенностью кластерного анализа является то, что различия между единицами, входящими в выделенную группу, незначительны, а различия между группами существенны.
Наиболее трудным считается определение однородности объектов. Для этого вводится понятие расстояния d(Xi, Xj) между объектами Xi и Xj. Объекты будут считаться однородными в случае d(Xi, Xj) ≤ dпор, где dпор – заданное пороговое значение, определяемое в каждом конкретном случае по-своему.
Выбор метрики (меры близости) d является узловым моментом исследования, от которого решающим образом зависит окончательный вариант разбиения объектов на группы при заданном алгоритме разбиения. В задачах кластерного анализа часто используют обычное евклидово расстояние. Существуют и другие способы определения расстояния в признаковом пространстве, например, хеммингово расстояние, которое используется как мера различия объектов, задаваемых дихотомическими признаками; квадрат евклидова расстояния; расстояние городских кварталов (манхэттенское расстояние); расстояние Чебышева; расстояние Махаланобиса; степенное расстояние; процент несогласия; пиковое расстояние. Выбор метрики-расстояния определяется структурой признакового пространства и целью классификации.
При использовании процедур кластерного анализа расчленение объектов совокупности на качественно однородные группы производится одновременно по большому числу признаков, но при соблюдении условия, что ни один признак не выделяется по своей значимости так, что группировка на его основе является главной.
Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Используются такие подходы: расстояние, измеряемое по принципу «ближайшего соседа» (расстояние между ближайшими объектами кластеров); расстояние, измеряемое по принципу «дальнего соседа» (расстояние между самыми дальними объектами кластеров); расстояние, измеряемое по «центрам тяжести» кластеров (расстояние между средними арифметическими векторных наблюдений, входящих в кластеры).
Выбор той или иной меры расстояния между кластерами влияет, главным образом, на вид выделяемых алгоритмами кластерного анализа геометрических группировок объектов в пространстве признаков. Так, алгоритмы, основанные на расстоянии «ближайшего соседа», хорошо работают в случае группировок, имеющих сложную, в частности, цепочечную структуру. Расстояние «дальнего соседа» применяется, когда искомые группировки образуют в пространстве признаков шаровидные облака. И промежуточное место занимают алгоритмы, использующие расстояния «центров тяжести» и средней связи, которые лучше всего работают в случае группировок эллипсоидной формы.
Классификационные процедуры иерархического типа основаны на последовательном объединении кластеров (агломеративные процедуры) и на последовательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Эти алгоритмы отличаются друг от друга лишь способом вычисления расстояния между классами. Агломеративный алгоритм выполняется таким образом. На первом шаге все объекты считаются отдельными кластерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в результате все объекты объединяются в один кластер. Момент остановки этого процесса может задаваться указанием либо требуемого числа кластеров, либо максимального расстояния, при котором допустимо объединение. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предоставляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма. Для большого числа объектов разбиения такая визуализация классификации является единственным способом получить представление об общей конфигурации объектов.
Иерархические процедуры позволяют проследить процесс выделения группировок и иллюстрируют соподчиненность кластеров, образующихся на разных шагах какого-либо агломеративного или дивизимного алгоритма.
Выполнение кластерного анализа позволяет сгруппировать объекты в отдельные группы, а затем дать экспертную оценку этим группам.
Анализ геометрической структуры данных является творческой задачей, не имеющей штампов. Осмысление выделенных группировок на различных шагах работы того или иного дивизимного или агломеративного алгоритма дает возможность получить ответы на вопросы, что общего и в чем различаются группировки объектов. Это в свою очередь способствует построению системы понятий, определению метапонятий и установлению между ними семантических отношений, то есть проведению концептуального анализа знаний.
Использование методов проецирования данных на плоскость или в трехмерные объемы латентных переменных, полученных методами многомерного шкалирования, позволяет увидеть закономерности структуры множества эмпирических фактов с оптимизированными описаниями.
С одной стороны, увиденные закономерности могут составить основу для минимизации базы знаний, представленных в экстенсиональной форме (например, для определения композиции диагностических прецедентов минимального объема). С другой – выявленные закономерности способствуют разработке тех или иных интенсиональных правил вывода на знаниях.
Имеется еще одна ценная возможность использования визуальных отображений полученных геометрических структур данных. Ее предоставляют средства современной интерактивной графики, которые позволяют обосновывать принятие решения о принадлежности неизвестного объекта какому-либо классу эквивалентности, получая ответы на вопросы типа: «Что общего у данного объекта с другим объектом или группой объектов (например, визуально ближайших или наоборот удаленных) с известной классификацией?», «Чем отличается данный объект от другого объекта или группы объектов с известной классификацией?» и т.п.
Ответы даются в виде пересечения описания неизвестного объекта с описаниями объектов, которые оптимизированы привязкой контекстно-зависимых локальных метрик. Совокупность таких ответов, индивидуальных для каждого нового случая, обладает полиморфностью, свойственной нашему языку при описании явлений со сложной системной организацией, и обеспечивает объяснение принятых решений посредством аргументации.
Здесь нет дерева логического вывода. Ответы воспринимаются параллельно. Они как бы бросаются на чашу весов, и их множество может расширяться до довольно больших величин (в зависимости от количества привлекаемых для аргументации объектов и сочетаний объектов).