Radoslava kraleva, velin kralev

“Fundamental Sciences and Applications”, Vol. 13, 2006

Anniversary Scientific Conference’ 2006

BULGARIA

ВЪРХУ ЕДНА МОДИФИКАЦИЯ НА ИТЕРАТИВНИЯ САМООРГАНИЗИРАЩ СЕ МЕТОД ЗА АНАЛИЗ НА ДАННИ

1. 
   Въведение
   

2. 
   Терминология
   

3. 
   Итеративен СамоОрганизиращ се Метод за Анализ на Данни.
   

Един от алгоритмите за кластеризация (a clustering algorithm) е Итеративния СамоОрганизирац се Метод за Анализ на Данни – ИСОМАД (Iterative Self Organizing Data Analysis Techniques Algorithm – ISODATA). Той е предложен от Бел и Хол през 1965 г., с цел за дадено множество от N образа (точки) в n-мерното пространство, да се намерят K на брой центрове на клъстери с помощта на набор предварително дефинирани евристични характеристики. При този алгоритъм се изпълняват процедури за намиране на най-подходящите центрове на клъстерите, чрез итеративни приближения, докато не бъдат удовлетворени предварително зададените критерии.. ИСОМАД от своя страна е достатъчно гъвкав и позволява при необходимост параметрите на критериите да бъдат коригирани, с цел увеличаване на прецизността при изпълнение.

Тези параметри са:

• 
  N – параметър определящ броя на входните образи;
  
• 
  K – параметър определящ очаквания брой клъстери;
  
• 
  I – параметър определящ максималния брой итерации;
  
• 
  L – параметър определящ максималния брой двойки центрове, които могат да бъдат обединени (lumping)
  
• 
  _N – параметър определящ минималния брой елементи влизащи във всеки клъстер (използва се за ликвидиране на ненужните клъстери);
  
• 
  _S – параметър определящ максималното стандартно отклонение за всеки клъстер (използва се в операцията разцепване);
  
• 
  _C – параметър определящ минималното разстояние между два центъра на клъстери, т.е. това е параметър характеризиращ компактността (използва се в операцията сливане).
  

(Стъпка 1) Задават се центровете на клъстерите. (Стъпка 2) Разпределят се образите по клъстери. (Стъпка 3) Премахват се онези клъстери, чиито брой образи, влизащи в тях е по-малък от предварително зададен параметър. (Стъпка 4) Всички центрове на останалите клъстери се локализират и коригират. (Стъпка 5) Изчислява се средното разстояние между образите във всеки клъстер и съответният им център. (Стъпка 6) Пресмята се обобщеното средно разстояние. (Стъпка 7) Изпълнението на алгоритъма продължава с операциите сливане или разцепване на клъстери. В зависимост от получения и очаквания брой клъстери, както и от номера на текущата итерация и максималния брой итерации се определя дали алгоритъмът да премине към изпълнение на следващата стъпка, или да прескочи няколко стъпки. (Стъпка 8) За всеки клъстер се изчислява стандартното отклонение на образите, влизащи в него по всяка от координатните оси. (Стъпка 9) Намира се максималното средноквадратично отклонение. (Стъпка 10) Използвайки тази информация заедно с параметрите за максимално стандартно отклонение и текущия брой клъстери, се извършва разцепване на клъстера с максималното стандартно отклонение. Ако е извършено разцепване, алгоритъмът преминава към Стъпка 2. В противен случай, параметрите L и _C се използват за осъществяване на операцията сливане на двойки клъстери (Стъпки 11 - 13). На последния етап (Стъпка 14) се определя дали алгоритъмът ще приключи, или ще бъде увеличен номера на текущия цикъл на итерацията с единица и ще се премине към стъпка 1 или 2.

Предимствата на алгоритъма ИСОМАД се дължат на способността му да отстранява клъстерите с малък брой елементи, да разцепва онези от тях, които имат несъвместими свойства и да обединява други, които притежават сходни такива. Изходните резултати обаче зависят изцяло от входните параметри N, K, I, L, _N, _S, _C. Освен това този алгоритъм е неприложим при голям набор от клъстери и се прилага само върху образи разположени линейно в хиперпространството.

В резултат на много тестове достигнахме до извода, че разпределянето на образите по клъстери при класическия алгоритъм ИСОМАД, може да бъде подобрено. Ако разгледаме внимателно алгоритъма установяваме, че в 7 и 10 се съдържат еднакви условия за проверка, които се отнасят до това дали текущия брой на клъстерите (N_C), е два пъти по-малък от очаквания, т.е. N_C  K / 2.
Ще илюстрираме само тези две стъпки от алгоритъма [3]:

Стъпка 7: Ако текущата итерация е последна, то параметърът определящ минималното разстояние между два клъстера _C = 0 и следва стъпка 11.

Ако текущия брой на клъстерите е по-малък от половината от очаквания брой, т.е. N_C  K / 2 (много малко клъстери), се преминава към стъпка 8.

Ако текущата итерация има четен пореден номер или броя на получените клъстери е по-голям от удвоената стойност на очаквания брой, т.е. N_C > 2K (твърде много клъстери), се преминава към стъпка 11.

В противен случай изпълнението на алгоритъма се преустановява.

или

Препоръчителна стойност за k е 0,5, тъй като стойността на γ_j трябва да бъде достатъчно голяма, за да се отличават разликите в разстоянията между образа и двата нови центъра, и същевременно да бъде достатъчно малка, за да не настъпят промени в общата структура на процеса на клъстеризация. След което се изтрива стария център z_j и N_C се увеличава с 1.

Ако разцепването е извършено на тази стъпка се преминава към Стъпка 2.

В противен случай се изпълнява следващата стъпка.

Модификация на алгоритъма се състои в промяната на условията в Стъпка 7 и в Стъпка 10. На местата в алгоритъма, в които се проверява дали текущия брой на клъстерите N_C е достигнал половината от очаквания резултат от потребителя, т.е. , да бъде заменено с условието: .

С тази промяна се запазва цялостната концепция на алгоритъма, т.е. получената модификация може да се прилага в процеса на идентификацията. С тази промяна се цели да се постигне по-детайлно разпределяне на образите с общи свойства по класове, което при първоначалния вариант на алгоритъма се достига трудно, тъй като ИСОМАД зависи изцяло от входните параметри, които имат евристичен характер. Не винаги е лесно определянето на броя на класовете (клъстерите), на които може да се разделят образите от едно изображение¹. От ограничителните условия се вижда, че преди да бъдат променени, броят на очакваните клъстери няма да бъде достигнат, защото алгоритъмът ще спре своето изпълнение след като са получени половината клъстери. В този случай, за да бъдат установени класовете на разпределение на образите, експертът ще трябва да въведе два пъти повече, от този които смята че има.

5. Експериментални резултати

Всички експерименти са проведени с помощта на специално разработен софтуер с графичен потребителски интерфейс, работещ под ОС Widows 98, NT, XP, за компилирането на продукта е използван компилатор на Borland. Последователността на стъпките на двата алгоритъма са програмирани на ниско ниво. Въвеждането на образите става посредством кликане на мишката върху координатната система или от клавиатурата, като нагледно се визуализират върху координатна система. След изпълнението на който и да е от двата алгоритъма, върху координатната система точките се разпределят по клъстери, като всеки клъстер формира единен обект. Тъй като целта на тази статия е да представи предложената модификация, то за тестване на ИСОМАД и на неговата модификация, тук ще разгледаме само опростени схеми от образи в Таблица 1 са представени малка част от използваните модели, както и резултата от изпълнението на двата алгоритъма.

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

На Фиг. 2 е представена съпоставката между очаквания брой на клъстерите и получения при двата алгоритъма съгласно схемите от Таблица 1.

Фиг. 2. Диаграма на очаквания и получения брой клъстери.
6. Заключение

В тази статия е разгледана модификация на самоорганизиращия се метод за анализ на данни (ИСОМАД), получен след промяна в две от ограничителните му условия. Представени са част от направените опити за изследване на поведението на двата алгоритъма при еднакви входни параметри. Изводът, който може да се направи след проведените експерименти, е че въведените промени доведждат до по-детайлно разпределяне на образите по клъстери.

2. Ю. И. Журавлев, И. Б. Гупенич. „Разпознавание, классификация, прогноз. Математичекие методы и примение”, Вып. 2, Москва, Наука, 1982, 302 с.

3. C. L. Looney. “Pattern Recognition Using Neural Networks – Theory and Algorithms for Engineers and Scientists”, Oxford University Press, New York, 1997, p 40-47.

Department of Informatics

South-West University "Neofit Rilsky" - Blagoevgrad

66, Ivan Mihailov Str.

2700 Blagoevgrad

BULGARIA