_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).doc), страница 11

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

2.2. Кластеризация, как задача поиска оптимального покрытия.

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

Рассмотрим один алгоритм решения данной задачи для заданного числа l кластеров. Считаем также предварительно заданными (или определенными) l векторов , которые являются центрами «сгущения» выборки и интерпретируются как центры кластеров. Они могут быть получены, например, как центры гипершаров после предварительной кластеризации выборки с помощью алгоритма Форель или с помощью метода k- внутригрупповых средних.

Введем в рассмотрение специальные семейства вложенных гипершаров.

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

Теперь можно поставить следующую задачу: «Найти l гипершаров , покрывающих все объекты из и имеющих минимальное число общих объектов ».

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

(2.1)

(2.2)

(2.3)

(2.4)

где

Ограничения (2.2) выражают требование покрытия каждого объекта хотя бы одним шаром, а (2.3) – присутствие в решении основной задачи хотя бы одного шара с центром в для каждого

Рис. 17. Пример кластеризации в виде оптимального покрытия гипершарами

По построению, имеет место монотонность коэффициентов функции (2.1) и ограничений (2.2):

.

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

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

2.3. Кластеризация, как задача поиска структур в данных.

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

Пусть фиксирована метрика (или полуметрика (x,y)) на множестве векторов признаковых описаний x=(x₁, x₂, ..., x_n), x_i - действительные числа. Введем также меру расстояния между группами объектов d(T_i, T_j). Примерами подобных функций являются функции (2.5) - (2.8) .

(2.5)

(2.6)

(2.7)

,где . (2.8)

Пусть заданы функция (x,y) и функции d(T_i, T_j) для групп объектов T_i и T_j . Рассмотрим задачу кластеризации на заданное число кластеров. Пусть к шагу № k , k=1,2,…, получены кластеры T^k_1,, T^k_2,,..., T^k_m-k+1,, (при k=1, ). От данных (m-k+1) кластеров осуществляется переход к (m-k) кластерам путем объединения в один той пары T^k_, T^k_, для которой . Для нахождения разбиения исходной выборки на l кластеров требуется выполнение m-l шагов. Полученные кластеры являются разбиением исходной выборки, причем каждый из кластеров имеет структурное представление в терминах расстояний объектов и кластеров.

2.4. Решение задачи кластерного анализа коллективами алгоритмов

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

В настоящем разделе рассматривается двухуровневый подход к решению задачи кластерного анализа. Первый уровень ее решения состоит в независимом применении набора различных алгоритмов для кластеризации данных и нахождения набора кластеризаций. Второй уровень состоит в построении окончательного оптимального коллективного решения в результате решения специальной дискретной оптимизационной задачи на перестановках. Интерпретация полученных результатов следующая: находится разбиение выборки объектов на такие подмножества, многие элементы каждого их которых принадлежат “значительному” числу одних и тех же кластеров, полученных исходными алгоритмами. Таким образом, кластеры коллективного решения образуют объекты, «близкие» друг другу по нескольким подходам одновременно.

В работах [51,52] разработана теория комитетного синтеза оптимальных решений задачи кластерного анализа коллективами алгоритмов кластеризации. Опишем кратко основные идеи и алгоритм данного подхода.

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

Определение 6: Информационные матрицы и называются эквивалентными, если они равны с точностью до перестановки столбцов.

Произвольная матрица определяет класс всех эквивалентных ей матриц.

Определение 7: Алгоритмом кластеризации называется алгоритм, переводящий описания объектов в класс эквивалентности , то есть:

.

Данное определение отражает факт свободы в обозначении полученных алгоритмом кластеров.

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

Пусть (для простоты будем считать, что . Оператор называется сумматором, если . Очевидно, что .

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

, где , .

Определение 8. Комитетным синтезом информационной матрицы на элементе называют ее вычисление: , при условии - сумматор, - решающее правило.

Таким образом, матрицы , поэлементно суммируются. Полученной числовой матрице ставится в соответствие бинарная матрица . Тогда коллективным решением можно считать . Данное решение определяется конкретным выбором матриц . Для оценивания коллективного решения вводится понятие контрастных матриц оценок , под которыми понимаются произвольные числовые матрицы со свойством . Контрастные матрицы соответствуют тому гипотетическому случаю, когда все исходные решения задач классификации оказались равными (вместе с обозначениями классов). Случаи контрастных матриц считаются наилучшими по множеству всевозможных наборов бинарных матриц и «потенциально наилучшими» по множеству допустимых наборов , . Тогда качество некоторой матрицы оценок определяется как ее расстояние до множества всех контрастных матриц той же размерности: , - множество всех контрастных матриц размерности . Задача построения оптимальной коллективной классификации сводится к минимизации , т.е. нахождению такого конкретного набора матриц , , по которому вычисляется матрица оценок, «максимально похожая» на одну из контрастных матриц. Для решения данной дискретной оптимизационной задачи на перестановках разработан эффективный метод /50/.