Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
ИИ - Урок 3 - Системы распознавания образов (идентификации). Часть 6

Автор: Сотник С.Л.

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

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

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

б) объекты разных групп должны быть далеки друг от друга;

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

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме¬тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж¬ду группами wl и wm


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

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

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

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

Функционалы качества и конкретные алгоритмы автомати¬ческой классификации доста-точно полно и подробно рассмот¬рены в специальной литературе. Эти функционалы и ал¬горитмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводитель-ных компьютеров. Раз¬нообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

Иерархическое группирование

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


Классификационные процедуры иерархического типа предназначены для получения на-глядного представления о стратификационной структуре всей исследуемой совокупности объек-тов. Эти процедуры основаны на последовательном объе¬динении кластеров (агломеративные процедуры) и на последо¬вательном разбиении (дивизимные процедуры). Наибольшее распро-странение получили агломеративные процедуры. Рас¬смотрим последовательность операций в таких процедурах.

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

Различные варианты определения расстояния между кла¬стерами дают различные вари-анты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета рас-стояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):


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

Проект Delphi World © Выпуск 2002 - 2024
Автор проекта: USU Software
Вы можете выкупить этот проект.