2.3. Алгоритм SKAT.

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

Каждый очередной таксон находился нами в условиях, когда точки, попавшие в предыдущие таксоны, исключались из рассмотрения. А что происходит, если таксоны формируются в присутствии всех  точек? Может случиться, что некоторые из более поздних таксонов включат в свой состав точки, ранее вошедшие в другие таксоны, и не останутся на месте, а станут скатываться в сторону соседнего сгустка точек и сольются с одним из своих предшественников. Такая ситуация изображена на рис. 6: таксон 2 начнет смещаться и сольется с таксоном 1. Другие же таксоны останутся на прежнем месте и с прежним составом своих внутренних точек. Будем считать таксоны 1, 3 и 4 устойчивыми, самостоятельными, а таксон 2 — неустойчивым, случайным. Случайные таксоны могут появляться из-за помех в данных или из-за неудачного выбора радиуса сфер.

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

Рис. 6.

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

, где