FOREL АЛГОРИТМІ

Таксономияның мақ саты: объектілердің жиынтығ ын алдын ала белгісіз параметрлерді берілген критерий бойынша топтарғ а (таксондар, кластерлер) бө лу.

Объектілерді бір немесе бірнеше жиынтық тарғ а бө лу ө згешелену мү мкін, сондық тан ең жақ сы топтастырылғ ан жиынды анық тау ү шін таксономияның сапа критериі енгізіледі.

Анық тамаларды енгізейік:

- топторғ а бө лінетін объект жиынтық тарының саны;

- таксондар саны ();

- таксономияның сапа критерийі.

FOREL алгоритмінің класс таксономиясы тығ ыздық гипотезасында негізделгенкритерийін қ олданады. Бір таксонғ а қ асиеттері " ұ қ сас" объекттер жиналып „орталық ” объектке ө тіп, бір таксон қ ұ ру қ ажет. Нә тижесінде сфера тә різді таксондар пайда болады.

- -нші таксонның центр координаталары,

- -нші таксондағ ы объектілердің саны,

, - -нші таксонның объектілері,

- -элемент центрімен -нші таксон арасындағ ы арақ ашық тық,

сонда -таксонына деиінгі арақ ашық тық центрінің сомасы

мынағ ан тең.

таксондарының арасындағ ы арақ ашық тық сомасы:

Критерийдің мақ саты объекттілерінің таксондарына бө лінгенде, жоғ арыда кө рсетілген кө лемі минималды болу керек. Бұ л шарттардың орындалуы FOREL алгоритмі арқ ылы жү зеге асады. Алгоритмнің базалық версиясымен кейбір модификацияларын қ арастырайық.

Осы алго ырғ ақ тан алынатын таксондары шар секілді кө лем қ абылдайды. Таксондардың саны радиусттың ортасына байланысты болады: радиус аз болғ ан сайын таксондар кө п болып шығ ады. Басында объекттің тү рлері осындай болып тұ рақ талады, барлық тү рлердің диапазоны ноль мен бірдің арасында болуы тиіс. Содан кейін радиусттың минималды гиперсферасы қ ұ рылады, ол барлық нү ктелерді қ амтиды (барлық объект бір таксонғ а кіреді). Ары қ арай радиусттың сферасы бара-бара кішірей береді. Радиустты береміз жә не сфераның ортасын кез-келген бар нуктемен араластырамыз. Ара қ ашық тығ ы радиусқ а дейін аз нү кте табамыз жә не осы «ішкі» нү ктенің орта координаттарын табамыз. Сфераның ортасын ауырлық тың ортасына апарамыз жә не тағ ыда ішкі нү ктелерді табамыз. Сфера локальды тұ йық талғ ан нү ктенің бағ ытына қ арай жү зген секілді болады. Бұ ндай процедура анық ішкі нү кте жә не сфераның ортағ а ауыстыруын сфера тоқ тағ анша дейін тоқ татылмай істеліне береді, яғ ни біз келесі қ адамда мынаны тапқ анымызша, ішкі нү ктенің қ ұ рамы, сонымен қ атар олардың орта ауырлығ ы ауыспайды. Осы жерден біз кө ре аламыз, сфераның локальдың максимумның тығ ыздық нү ктесінің кең істік белгісінде.

Толқ алғ ан сфераның ішінде қ алғ ан нү кте, біз оны номер 1-ші таксонғ а жатады жә не оларды алдағ ы іздеуден алыптастаймыз. Қ ағ ан айттылғ ан жә не кө рсетілген нү ктелер ү шін процедура барлық нү ктелер таксонның қ ұ рамына кіргенше жалғ аса береді.

Алгоритмнің соң ғ ы сандырдың қ адамдарының ұ қ састық тары дә лелденген, бірақ бә рімізге оң ай мә лім болып тұ рғ ан ол яғ ни шешімнің жалғ ыз болмауы. Ол 1 суретте кө рініп тұ рғ андай таксонның шешімі оның бірінші қ андай нү ктеден басталу керектігіне баланысты болады.

Егер бастапқ ы нү ктені кез-келген мен ауыстырсақ, онда бірнеше кез-келген тү рлі таксондадың тү рлері шығ уы мү мкіндігі бар жә не сол кезі минималды ең ү лкен жауаптың варианттында тоқ талуы керек.