1

© Journal of the Technical University at Plovdiv

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

Anniversary Scientific Conference’ 2006

BULGARIA

ON MODIFICATION OF THE ITERATIVE
SELF-ORGANIZING DATA ANALISYS TEACHINIQUE Algorithm

RADOSLAVA KRALEVA, VELIN KRALEV

Abstract.In the present paper one of the most popular classical self-organizing clustering methods – ISODATA (Iterative Self-Organizing Data Analysis Techniques Algorithm) is considered. It is proposed a modification implemented by changes in two of the restriction conditions of ISODATA algorithm. There are presented the received results of the work of the both algorithms on the same input data. The presented modification can be used for detailed distribution of samples in clusters.

Key words:pattern recognitions, self-organizing mode, clusters.

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

  1. Въведение

Човек може да разпознае сред тълпата свой приятел, символите в думите, да различи цветовете, да различи любима песен. Нашите сетива улавят сигнали - светлинни или звукови и след това ги модулират и съхраняват в нашата памет във вид на прости обекти. След което чрез тези прости обекти може да се възстанови приблизително запаметения сигнал или събитие. Животните и птиците, също като хората, могат да различат себеподобните си, храната си. Този процес на възприемане и познание, се нарича разпознаване. Класификацията (групирането) на изходните данни към определен клас, чрез определяне на съществени признаци или свойства характеризиращи тези данни измежду останалите несъществени детайли. Под понятието образобикновено се разбира модел, начин, стил закономерност, начин на действие. Основната цел на въвеждането на понятието е използуването му в процеса на установяване на съответствия, т.е при доказването на идентичността, аналогията, подобието и сходството на обектите по пътя на сравнението (съпоставянето).[1].

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

Основната задача на разпознаването на образи се състои в построяването на ефективни процедури на базата на систематични, теоретични и експериментални изследвания за класифициранена формализирани описания и обекти в съответстващите им класове [2]. При разпознаването на образите се използват два основни процеса – идентификация и класификация на обектите. При първия процес обектите се разпределят по отделни уникални класове, а при втория – се извършва разпределянето на обектите по класове в зависимост от техните прилики и свойства (това е същинското разпознаване). Класификацията се реализира по два начина или чрез обучение с учител или чрез самообучение (нарича се още обучение без учител). Една система се обучава (training), когато в резултат на изпълнението на опити е настъпило изменение във вътрешната й структура, е довело до промяна в поведението й като цяло[3].При самоорганизиращите методи за класификация, процесът на групиране на вектор-образите в класове се нарича кластеризация От това наименование произлиза наименованието клъстер, под което се разбирагрупа от обекти (образи), образуващи в пространството компактна област с център на определено разстояние от центровете на останалите области.Система (устройство), която служи за различаване на процеси, явления, обекти и т.н. се нарича разпознаваща система (устройство). Когато на входа на такава системапопадне нов образ, е необходимо тя да вземе решение за принадлежността му към определен клас (клъстер). Образът се отнася към този клас, за който разстоянието (най-често евклидовото разстояние) между неговия център и разглеждания образ е минимално. Центърът, e един или няколко идеализирани представители (еталони, прототипи), които могат да се разглеждат като представители на всеки клас.

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

Кластеризацията е мощен инструмент в съвременната обработка на изображения. Така например тя се прилага за изработването на топографски карти на земната повърхност, базирани на снимки от спътници; при анализ на фотографски изображения; при разработване на мултиспектрални анализи за химични изследвания и т.н. Алгоритми от този тип се прилагат върху оскъдни или трудно получени данни.

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

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

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

Алгоритъмът ИСОМАД се състои от следните стъпки (подробно описание може да се намери в [3]):

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

4. Нашата модификация

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

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

Ще илюстрираме само тези две стъпки от алгоритъма [3]:

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

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

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

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

Стъпка 10:Ако за някоемаксимално средно-квадратично отклонение на j-тия клъстер са изпълнени условията , т.е. максималното средно-квадратично отклонение е строго по-голямо от максималното стандартно отклонение за j-тия клъстер и

а) средната стойност на разстоянията между обектите е строго по-голямо от обобщеното средно разстояние , т.е. , и текущият брой на обектите попадащи в j-тия клъстер Nj е строгопо-голям от, където θNе минималния брой образи, които могат да принадлежат на един клъстер, т.е. ;

или

б) получения общ брой на клъстерите NСе по-малък от,то клъстерът с център zjсе разцепва на два нови клъстера с центрове zj+ и zj–, като съответно се добавя и изважда зададена константна величина γj към максималната компонента на вектора . За стойностна γjможе да се вземе максималната средно квадратична компонента, т.е.

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

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

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

Схематичното може да се представи така:

Фиг.1. Схематично представяне на стъпки 7 и 9 от ИСОМАД.

Стъпка 7 е стъпка на разклонение в алгоритъма, при която има три възможности: едната е да се премине към разцепване на клъстери; другата – към сливането им; третата – към безусловен изход от алгоритъма.

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

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

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

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

Таблица 1. Таблица на част от опитите с ИСОМАД и предложената модификация.

Задачата за разпознаванена образи се състои в построяването на ефективни изчислителни средства на базата на систематични теоретични и експериментални изследвания за класифициране на формализирани описания и обекти в съответствуващите им класове[4].Както може да се види от таблицата, след прилагането на ИСОМАД и на предложената модификациявърху едни и същи входни данни, резултатът (броя на получените клъстери) е различен. При първия алгоритъм броя на получените клъстери след провеждането на всички опити рядко надвишава половината от очаквания броя клъстери, и ако това стане то не е с повече от 1. От тук може да заключим, че за да получим желания брой от клъстери за съответната схема, трябва да въведем стойност, която да я надвишава, като трябва да се вземе предвид, че входните данни зависят от познанията на експерта, който ги въвежда.

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

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

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

6. Заключение

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

Литература

1.M. Todorova, D. Birov. „The Recognition as an Approach in the Learning of Computer Science”, Proceeding of the Thirty Fifth Spring Conference of the Union of Bulgaria Mathematicians Borovets, April 5-8 2006, p. 449-454

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.

4.М.Todorova, N.Siniagina, Interrelation of Teaching of the Pattern Recognition and Discrete Mathematics, 7-th International Conference on Discrete Mathematics and Applications, Proceedings of the Seventh International Conference, Vol. 7, стр.157 – 164, 2005,

Department of Informatics

South-West University "Neofit Rilsky" - Blagoevgrad

66, Ivan Mihailov Str.

2700 Blagoevgrad

BULGARIA

E-mail:

Copyright ©2006 by Technical University at Plovdiv, Plovdiv, BULGARIA. ISSN 1310 - 8271

[*] Изображение – обект подложен на процеса разпознаване.