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

17. Пример кластеризации в виде оптимального покрытия гипершарами61По построению, имеет место монотонность коэффициентов функции (2.1) иограничений (2.2):ni , j  ni , j 1 , cit, j  cit, j 1 .Пусть {zij* , i  1,2,..., l , j  1,2,..., ki } - решение задачи (2.1)- (2.4). В силу условий (2.3),положительности коэффициентов целевой функции (2.1) и свойств монотонностикоэффициентов, будут выполнены равенстваkizj 1*ij 1, i  1,2,..., l.

Тогда совокупностьшаров Rt11 , Rt22 ,..., Rtll , соответствующих всем единичным значениям z1*t1 , z2*t2 ,..., z2*tl , иобразует искомое решение. Окончательно, в качестве решения задачи кластерного анализапринимается совокупность подмножеств K1 , K 2 ,..., K l , K i  {x j : x j  Rtii , j  1,2,..., m} .На Рис. 17 приведен пример задачи кластеризации на три кластера, в котором двакластера имеют один общий объект. Максимальный радиус шаров с центром в y jограничивался сверху величиной max  (y j , y t ) .t j2.3.

Кластеризация, как задача поиска структур в данных.Классическим примером данной задачи является иерархическая группировка. Здесьзадача кластеризации на l кластеров решается последовательным объединениемближайших групп (существуют и подходы, основанные на последовательном разбиениигрупп объектов). На первом шаге считается, что каждый объект образует «одноточечный»кластер: K i1  {xi }, i  1,2,..., m . На втором шаге два ближайших кластера объединяются водин.

Процесс объединения повторяется до нахождения l кластеров. Приведем наиболеераспространенный алгоритм иерархической кластеризации.Пусть фиксирована метрика (или полуметрика (x,y)) на множестве векторовпризнаковых описаний x=(x1, x2, ..., xn), xi - действительные числа. Введем также мерурасстояния между группами объектов d(Ti, Tj). Примерами подобных функций являютсяфункции (2.5) - (2.8) .d min (Ti , T j )  min  (x , x  ),(2.5)d max (Ti , T j )  max  (x , x  ),(2.6)x Ti ,x  T jx Ti ,x  T jd avr (Ti , T j ) 1ni n j   (x , x ),(2.7)x Ti x  Tid mean (Ti , T j )   ( yi , y j ) ,где yi 1Ti x .x Ti(2.8)62Пусть заданы функция (x,y) и функции d(Ti, Tj) для групп объектов Ti и Tj .Рассмотрим задачу кластеризации на заданное число кластеров.

Пусть к шагу № k ,k=1,2,…, получены кластеры Tk1,, Tk2,,..., Tkm-k+1,, (при k=1, T1  {x },  1,2,..., m ). Отданных (m-k+1) кластеров осуществляется переход к (m-k) кластерам путем объединения водин той пары Tk, Tk, для которой d (Tk , Tk )  min d (Ti , Ti ) . Для нахождения разбиения ,исходной выборки на l кластеров требуется выполнение m-l шагов. Полученные кластерыявляются разбиением исходной выборки, причем каждый из кластеров имеет структурноепредставление в терминах расстояний объектов и кластеров.2.4.

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

Второй уровень состоит в построении окончательного оптимальногоколлективного решения в результате решения специальной дискретной оптимизационнойзадачи на перестановках. Интерпретация полученных результатов следующая: находитсяразбиение выборки объектов на такие подмножества, многие элементы каждого ихкоторых принадлежат “значительному” числу одних и тех же кластеров, полученныхисходными алгоритмами. Таким образом, кластеры коллективного решения образуютобъекты, «близкие» друг другу по нескольким подходам одновременно.В работах [51,52] разработана теория комитетного синтеза оптимальных решенийзадачи кластерного анализа коллективами алгоритмов кластеризации. Опишем краткоосновные идеи и алгоритм данного подхода.Пусть некоторым алгоритмом решена задача кластеризации для выборки объектовX  {x1 , x 2 ,..., x m } в виде разбиения или покрытия данной выборки l множествами-кластерами. Обозначим эти кластеры через T1,..., Tl .

Результат кластеризации можно63записать в виде информационной матрицы I   ijml, где  ij  {0,1} ,  ij  1 , если S i  T j , ij  0 , если S i  T j . Наличие нескольких единиц в одной строке соответствуетпринадлежности объекта сразу нескольким кластерам. Нулевая строка означает отказ откластеризации соответствующего объекта.Определение 6: Информационные матрицы I   ijm lи I    ijmlназываютсяэквивалентными, если они равны с точностью до перестановки столбцов.Произвольная матрица  ijОпределениеопределяет класс K  ijmlАлгоритмом7:m l всех эквивалентных ей матриц.кластеризацииназываетсяAcпереводящий описания объектов x1 ,..., x m в класс эквивалентности K  ijAc (x1 ,..., x m )  K  ijmlm l.алгоритм,, то есть:Данное определение отражает факт свободы в обозначении полученныхалгоритмом кластеров.ПустьданоAc (x1 ,..., x m )  K  ijкластеризацииK  ij1ml, K  mlкластеризацийn на,..., K  алгоритмамиA1c ,..., Anc :l кластеров.

Задача построения оптимальной коллективнойсостоит2ij mlвыборкивnij mlвычислениинекоторогопомножествуновогоK cijmlизрешенийn(гдеc ij  {0,1} ),обоснованного с содержательной стороны и оптимального с формальной.Пусть I  K  ijB( I1 ,..., I n )  B  bijmlml(для простоты будем считать, что I   ijназываетсясумматором,еслиnbij   ij .ml. ОператорОчевидно,что 10  bij  n .Матрицу, полученную в результате применения сумматора к некоторому наборуинформационных матриц, будем называть матрицей оценок. Оператор r называетсярешающим правилом, еслиr ( B)  cij1, bij  bik , k  j, k  1,..., lc ij  {0,1} , cij  ,где.ml0, иначе.64Определение 8.

Комитетным синтезом информационной матрицы C на элементе~~I  ( I1 ,..., I n ) называют ее вычисление: C  r (B( I )) , при условии B - сумматор, r решающее правило.Таким образом, матрицы I ,  1,2,..., n , поэлементно суммируются.

Полученнойчисловой матрице ставится в соответствие бинарная матрица C . Тогда коллективнымрешением можно считать K С  . Данное решение определяется конкретным выборомматриц I ,  1,2,..., n . Для оценивания коллективного решения K С  вводится понятиеконтрастных матриц оценок bijматрицысоml, под которыми понимаются произвольные числовыеbij  {0, n } .свойствомКонтрастныематрицысоответствуюттомугипотетическому случаю, когда все исходные решения задач классификации оказалисьравными (вместе с обозначениями классов). Случаи контрастных матриц считаются~наилучшими по множеству всевозможных наборов бинарных матриц I  ( I1 ,..., I n ) и«потенциальноI  K  ijmlрасстояние.наилучшими»множестваl( B)  min  bij  bij* ,Β*размерностимножествудопустимыхнаборовТогда качество некоторой матрицы оценокдоmповсехконтрастных*  { bij* }-матрицмножество~I  ( I1 ,..., I n ) ,B определяется как еетойвсехжеразмерности:контрастныхматрицi 1 j 1m  l .

Задача построения оптимальной коллективной классификациисводится к минимизации  (B ) , т.е. нахождению такого конкретного набора матрицI/ ,  1,2,..., n , I/  K  ijml , по которому вычисляется матрица оценок, «максимальнопохожая» на одну из контрастных матриц. Для решения данной дискретнойоптимизационной задачи на перестановках разработан эффективный метод /50/.65I1  A1 ( X )0 1 0 0 …0 00 0 0 1 …0 10 1 0 01…00 0 00 …1 00 0 0 10…00 1 10 … 0 000 1 0 0 …0 0 1 0 1 00…1010…000000…010 0 0 1 …0 10010…000010…001 0 1 0 …1 00010…000001…100000…00….………….0010…00010…100 0 1 00 … 0 0….………….0000…000 0 1 0 … 1 00 0 0 1 … 0 1….………….0000…01~B  B(I )1 5 0 0 …2 00 2 0 4 …0 63 0 4 0 …6 10531…120120…230012…210640…20….………….0013…17~C  r (B( I ))0 1 0 0 …0 00 0 0 0 …0 10 0 0 0 …1 00100…000000…000000…000100…00….………….0000…01I 2  A2 ( X )I n  An ( X )Рис.18.